1 //===-- WebAssemblyCFGSort.cpp - CFG Sorting ------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
10 /// This file implements a CFG sorting pass.
12 /// This pass reorders the blocks in a function to put them into topological
13 /// order, ignoring loop backedges, and without any loop or exception being
14 /// interrupted by a block not dominated by the its header, with special care
15 /// to keep the order as similar as possible to the original order.
17 ////===----------------------------------------------------------------------===//
19 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
20 #include "WebAssembly.h"
21 #include "WebAssemblyExceptionInfo.h"
22 #include "WebAssemblySubtarget.h"
23 #include "WebAssemblyUtilities.h"
24 #include "llvm/ADT/PriorityQueue.h"
25 #include "llvm/ADT/SetVector.h"
26 #include "llvm/CodeGen/MachineDominators.h"
27 #include "llvm/CodeGen/MachineFunction.h"
28 #include "llvm/CodeGen/MachineLoopInfo.h"
29 #include "llvm/CodeGen/MachineRegisterInfo.h"
30 #include "llvm/CodeGen/Passes.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/raw_ostream.h"
35 #define DEBUG_TYPE "wasm-cfg-sort"
37 // Option to disable EH pad first sorting. Only for testing unwind destination
38 // mismatches in CFGStackify.
39 static cl::opt
<bool> WasmDisableEHPadSort(
40 "wasm-disable-ehpad-sort", cl::ReallyHidden
,
42 "WebAssembly: Disable EH pad-first sort order. Testing purpose only."),
47 // Wrapper for loops and exceptions
50 virtual ~Region() = default;
51 virtual MachineBasicBlock
*getHeader() const = 0;
52 virtual bool contains(const MachineBasicBlock
*MBB
) const = 0;
53 virtual unsigned getNumBlocks() const = 0;
54 using block_iterator
= typename ArrayRef
<MachineBasicBlock
*>::const_iterator
;
55 virtual iterator_range
<block_iterator
> blocks() const = 0;
56 virtual bool isLoop() const = 0;
59 template <typename T
> class ConcreteRegion
: public Region
{
63 ConcreteRegion(const T
*Region
) : Region(Region
) {}
64 MachineBasicBlock
*getHeader() const override
{ return Region
->getHeader(); }
65 bool contains(const MachineBasicBlock
*MBB
) const override
{
66 return Region
->contains(MBB
);
68 unsigned getNumBlocks() const override
{ return Region
->getNumBlocks(); }
69 iterator_range
<block_iterator
> blocks() const override
{
70 return Region
->blocks();
72 bool isLoop() const override
{ return false; }
75 template <> bool ConcreteRegion
<MachineLoop
>::isLoop() const { return true; }
77 // This class has information of nested Regions; this is analogous to what
78 // LoopInfo is for loops.
80 const MachineLoopInfo
&MLI
;
81 const WebAssemblyExceptionInfo
&WEI
;
82 std::vector
<const Region
*> Regions
;
83 DenseMap
<const MachineLoop
*, std::unique_ptr
<Region
>> LoopMap
;
84 DenseMap
<const WebAssemblyException
*, std::unique_ptr
<Region
>> ExceptionMap
;
87 RegionInfo(const MachineLoopInfo
&MLI
, const WebAssemblyExceptionInfo
&WEI
)
88 : MLI(MLI
), WEI(WEI
) {}
90 // Returns a smallest loop or exception that contains MBB
91 const Region
*getRegionFor(const MachineBasicBlock
*MBB
) {
92 const auto *ML
= MLI
.getLoopFor(MBB
);
93 const auto *WE
= WEI
.getExceptionFor(MBB
);
96 if ((ML
&& !WE
) || (ML
&& WE
&& ML
->getNumBlocks() < WE
->getNumBlocks())) {
97 // If the smallest region containing MBB is a loop
98 if (LoopMap
.count(ML
))
99 return LoopMap
[ML
].get();
100 LoopMap
[ML
] = std::make_unique
<ConcreteRegion
<MachineLoop
>>(ML
);
101 return LoopMap
[ML
].get();
103 // If the smallest region containing MBB is an exception
104 if (ExceptionMap
.count(WE
))
105 return ExceptionMap
[WE
].get();
107 std::make_unique
<ConcreteRegion
<WebAssemblyException
>>(WE
);
108 return ExceptionMap
[WE
].get();
113 class WebAssemblyCFGSort final
: public MachineFunctionPass
{
114 StringRef
getPassName() const override
{ return "WebAssembly CFG Sort"; }
116 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
117 AU
.setPreservesCFG();
118 AU
.addRequired
<MachineDominatorTree
>();
119 AU
.addPreserved
<MachineDominatorTree
>();
120 AU
.addRequired
<MachineLoopInfo
>();
121 AU
.addPreserved
<MachineLoopInfo
>();
122 AU
.addRequired
<WebAssemblyExceptionInfo
>();
123 AU
.addPreserved
<WebAssemblyExceptionInfo
>();
124 MachineFunctionPass::getAnalysisUsage(AU
);
127 bool runOnMachineFunction(MachineFunction
&MF
) override
;
130 static char ID
; // Pass identification, replacement for typeid
131 WebAssemblyCFGSort() : MachineFunctionPass(ID
) {}
133 } // end anonymous namespace
135 char WebAssemblyCFGSort::ID
= 0;
136 INITIALIZE_PASS(WebAssemblyCFGSort
, DEBUG_TYPE
,
137 "Reorders blocks in topological order", false, false)
139 FunctionPass
*llvm::createWebAssemblyCFGSort() {
140 return new WebAssemblyCFGSort();
143 static void maybeUpdateTerminator(MachineBasicBlock
*MBB
) {
145 bool AnyBarrier
= false;
147 bool AllAnalyzable
= true;
148 for (const MachineInstr
&Term
: MBB
->terminators()) {
150 AnyBarrier
|= Term
.isBarrier();
152 AllAnalyzable
&= Term
.isBranch() && !Term
.isIndirectBranch();
154 assert((AnyBarrier
|| AllAnalyzable
) &&
155 "AnalyzeBranch needs to analyze any block with a fallthrough");
157 MBB
->updateTerminator();
161 // EH pads are selected first regardless of the block comparison order.
162 // When only one of the BBs is an EH pad, we give a higher priority to it, to
163 // prevent common mismatches between possibly throwing calls and ehpads they
164 // unwind to, as in the example below:
167 // call @foo // If this throws, unwind to bb2
169 // call @bar // If this throws, unwind to bb3
176 // Because this pass tries to preserve the original BB order, this order will
177 // not change. But this will result in this try-catch structure in CFGStackify,
178 // resulting in a mismatch:
182 // call @bar // This should unwind to bb3, not bb2!
191 // If we give a higher priority to an EH pad whenever it is ready in this
192 // example, when both bb1 and bb2 are ready, we would pick up bb2 first.
194 /// Sort blocks by their number.
195 struct CompareBlockNumbers
{
196 bool operator()(const MachineBasicBlock
*A
,
197 const MachineBasicBlock
*B
) const {
198 if (!WasmDisableEHPadSort
) {
199 if (A
->isEHPad() && !B
->isEHPad())
201 if (!A
->isEHPad() && B
->isEHPad())
205 return A
->getNumber() > B
->getNumber();
208 /// Sort blocks by their number in the opposite order..
209 struct CompareBlockNumbersBackwards
{
210 bool operator()(const MachineBasicBlock
*A
,
211 const MachineBasicBlock
*B
) const {
212 if (!WasmDisableEHPadSort
) {
213 if (A
->isEHPad() && !B
->isEHPad())
215 if (!A
->isEHPad() && B
->isEHPad())
219 return A
->getNumber() < B
->getNumber();
222 /// Bookkeeping for a region to help ensure that we don't mix blocks not
223 /// dominated by the its header among its blocks.
225 const Region
*TheRegion
;
226 unsigned NumBlocksLeft
;
228 /// List of blocks not dominated by Loop's header that are deferred until
229 /// after all of Loop's blocks have been seen.
230 std::vector
<MachineBasicBlock
*> Deferred
;
232 explicit Entry(const class Region
*R
)
233 : TheRegion(R
), NumBlocksLeft(R
->getNumBlocks()) {}
235 } // end anonymous namespace
237 /// Sort the blocks, taking special care to make sure that regions are not
238 /// interrupted by blocks not dominated by their header.
239 /// TODO: There are many opportunities for improving the heuristics here.
241 static void sortBlocks(MachineFunction
&MF
, const MachineLoopInfo
&MLI
,
242 const WebAssemblyExceptionInfo
&WEI
,
243 const MachineDominatorTree
&MDT
) {
244 // Prepare for a topological sort: Record the number of predecessors each
245 // block has, ignoring loop backedges.
247 SmallVector
<unsigned, 16> NumPredsLeft(MF
.getNumBlockIDs(), 0);
248 for (MachineBasicBlock
&MBB
: MF
) {
249 unsigned N
= MBB
.pred_size();
250 if (MachineLoop
*L
= MLI
.getLoopFor(&MBB
))
251 if (L
->getHeader() == &MBB
)
252 for (const MachineBasicBlock
*Pred
: MBB
.predecessors())
253 if (L
->contains(Pred
))
255 NumPredsLeft
[MBB
.getNumber()] = N
;
258 // Topological sort the CFG, with additional constraints:
259 // - Between a region header and the last block in the region, there can be
260 // no blocks not dominated by its header.
261 // - It's desirable to preserve the original block order when possible.
262 // We use two ready lists; Preferred and Ready. Preferred has recently
263 // processed successors, to help preserve block sequences from the original
264 // order. Ready has the remaining ready blocks. EH blocks are picked first
266 PriorityQueue
<MachineBasicBlock
*, std::vector
<MachineBasicBlock
*>,
269 PriorityQueue
<MachineBasicBlock
*, std::vector
<MachineBasicBlock
*>,
270 CompareBlockNumbersBackwards
>
273 RegionInfo
RI(MLI
, WEI
);
274 SmallVector
<Entry
, 4> Entries
;
275 for (MachineBasicBlock
*MBB
= &MF
.front();;) {
276 const Region
*R
= RI
.getRegionFor(MBB
);
278 // If MBB is a region header, add it to the active region list. We can't
279 // put any blocks that it doesn't dominate until we see the end of the
281 if (R
->getHeader() == MBB
)
282 Entries
.push_back(Entry(R
));
283 // For each active region the block is in, decrement the count. If MBB is
284 // the last block in an active region, take it off the list and pick up
285 // any blocks deferred because the header didn't dominate them.
286 for (Entry
&E
: Entries
)
287 if (E
.TheRegion
->contains(MBB
) && --E
.NumBlocksLeft
== 0)
288 for (auto DeferredBlock
: E
.Deferred
)
289 Ready
.push(DeferredBlock
);
290 while (!Entries
.empty() && Entries
.back().NumBlocksLeft
== 0)
293 // The main topological sort logic.
294 for (MachineBasicBlock
*Succ
: MBB
->successors()) {
296 if (MachineLoop
*SuccL
= MLI
.getLoopFor(Succ
))
297 if (SuccL
->getHeader() == Succ
&& SuccL
->contains(MBB
))
299 // Decrement the predecessor count. If it's now zero, it's ready.
300 if (--NumPredsLeft
[Succ
->getNumber()] == 0)
301 Preferred
.push(Succ
);
303 // Determine the block to follow MBB. First try to find a preferred block,
304 // to preserve the original block order when possible.
305 MachineBasicBlock
*Next
= nullptr;
306 while (!Preferred
.empty()) {
307 Next
= Preferred
.top();
309 // If X isn't dominated by the top active region header, defer it until
310 // that region is done.
311 if (!Entries
.empty() &&
312 !MDT
.dominates(Entries
.back().TheRegion
->getHeader(), Next
)) {
313 Entries
.back().Deferred
.push_back(Next
);
317 // If Next was originally ordered before MBB, and it isn't because it was
318 // loop-rotated above the header, it's not preferred.
319 if (Next
->getNumber() < MBB
->getNumber() &&
320 (!R
|| !R
->contains(Next
) ||
321 R
->getHeader()->getNumber() < Next
->getNumber())) {
328 // If we didn't find a suitable block in the Preferred list, check the
329 // general Ready list.
331 // If there are no more blocks to process, we're done.
333 maybeUpdateTerminator(MBB
);
339 // If Next isn't dominated by the top active region header, defer it
340 // until that region is done.
341 if (!Entries
.empty() &&
342 !MDT
.dominates(Entries
.back().TheRegion
->getHeader(), Next
)) {
343 Entries
.back().Deferred
.push_back(Next
);
349 // Move the next block into place and iterate.
350 Next
->moveAfter(MBB
);
351 maybeUpdateTerminator(MBB
);
354 assert(Entries
.empty() && "Active sort region list not finished");
358 SmallSetVector
<const Region
*, 8> OnStack
;
360 // Insert a sentinel representing the degenerate loop that starts at the
361 // function entry block and includes the entire function as a "loop" that
363 OnStack
.insert(nullptr);
365 for (auto &MBB
: MF
) {
366 assert(MBB
.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
367 const Region
*Region
= RI
.getRegionFor(&MBB
);
369 if (Region
&& &MBB
== Region
->getHeader()) {
370 if (Region
->isLoop()) {
371 // Loop header. The loop predecessor should be sorted above, and the
372 // other predecessors should be backedges below.
373 for (auto Pred
: MBB
.predecessors())
375 (Pred
->getNumber() < MBB
.getNumber() || Region
->contains(Pred
)) &&
376 "Loop header predecessors must be loop predecessors or "
379 // Not a loop header. All predecessors should be sorted above.
380 for (auto Pred
: MBB
.predecessors())
381 assert(Pred
->getNumber() < MBB
.getNumber() &&
382 "Non-loop-header predecessors should be topologically sorted");
384 assert(OnStack
.insert(Region
) &&
385 "Regions should be declared at most once.");
388 // Not a loop header. All predecessors should be sorted above.
389 for (auto Pred
: MBB
.predecessors())
390 assert(Pred
->getNumber() < MBB
.getNumber() &&
391 "Non-loop-header predecessors should be topologically sorted");
392 assert(OnStack
.count(RI
.getRegionFor(&MBB
)) &&
393 "Blocks must be nested in their regions");
395 while (OnStack
.size() > 1 && &MBB
== WebAssembly::getBottom(OnStack
.back()))
398 assert(OnStack
.pop_back_val() == nullptr &&
399 "The function entry block shouldn't actually be a region header");
400 assert(OnStack
.empty() &&
401 "Control flow stack pushes and pops should be balanced.");
405 bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction
&MF
) {
406 LLVM_DEBUG(dbgs() << "********** CFG Sorting **********\n"
407 "********** Function: "
408 << MF
.getName() << '\n');
410 const auto &MLI
= getAnalysis
<MachineLoopInfo
>();
411 const auto &WEI
= getAnalysis
<WebAssemblyExceptionInfo
>();
412 auto &MDT
= getAnalysis
<MachineDominatorTree
>();
413 // Liveness is not tracked for VALUE_STACK physreg.
414 MF
.getRegInfo().invalidateLiveness();
416 // Sort the blocks, with contiguous sort regions.
417 sortBlocks(MF
, MLI
, WEI
, MDT
);