LLVM 20.0.0git
WebAssemblyCFGSort.cpp
Go to the documentation of this file.
1//===-- WebAssemblyCFGSort.cpp - CFG Sorting ------------------------------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10/// This file implements a CFG sorting pass.
11///
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.
16///
17////===----------------------------------------------------------------------===//
18
20#include "WebAssembly.h"
26#include "llvm/ADT/SetVector.h"
31#include "llvm/CodeGen/Passes.h"
33#include "llvm/Support/Debug.h"
35using namespace llvm;
38
39#define DEBUG_TYPE "wasm-cfg-sort"
40
41// Option to disable EH pad first sorting. Only for testing unwind destination
42// mismatches in CFGStackify.
44 "wasm-disable-ehpad-sort", cl::ReallyHidden,
46 "WebAssembly: Disable EH pad-first sort order. Testing purpose only."),
47 cl::init(false));
48
49namespace {
50
51class WebAssemblyCFGSort final : public MachineFunctionPass {
52 StringRef getPassName() const override { return "WebAssembly CFG Sort"; }
53
54 void getAnalysisUsage(AnalysisUsage &AU) const override {
55 AU.setPreservesCFG();
63 }
64
65 bool runOnMachineFunction(MachineFunction &MF) override;
66
67public:
68 static char ID; // Pass identification, replacement for typeid
69 WebAssemblyCFGSort() : MachineFunctionPass(ID) {}
70};
71} // end anonymous namespace
72
73char WebAssemblyCFGSort::ID = 0;
74INITIALIZE_PASS(WebAssemblyCFGSort, DEBUG_TYPE,
75 "Reorders blocks in topological order", false, false)
76
78 return new WebAssemblyCFGSort();
79}
80
82#ifndef NDEBUG
83 bool AnyBarrier = false;
84#endif
85 bool AllAnalyzable = true;
86 for (const MachineInstr &Term : MBB->terminators()) {
87#ifndef NDEBUG
88 AnyBarrier |= Term.isBarrier();
89#endif
90 AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
91 }
92 assert((AnyBarrier || AllAnalyzable) &&
93 "analyzeBranch needs to analyze any block with a fallthrough");
94
95 // Find the layout successor from the original block order.
97 MachineBasicBlock *OriginalSuccessor =
98 unsigned(MBB->getNumber() + 1) < MF->getNumBlockIDs()
99 ? MF->getBlockNumbered(MBB->getNumber() + 1)
100 : nullptr;
101
102 if (AllAnalyzable)
103 MBB->updateTerminator(OriginalSuccessor);
104}
105
106namespace {
107// EH pads are selected first regardless of the block comparison order.
108// When only one of the BBs is an EH pad, we give a higher priority to it, to
109// prevent common mismatches between possibly throwing calls and ehpads they
110// unwind to, as in the example below:
111//
112// bb0:
113// call @foo // If this throws, unwind to bb2
114// bb1:
115// call @bar // If this throws, unwind to bb3
116// bb2 (ehpad):
117// handler_bb2
118// bb3 (ehpad):
119// handler_bb3
120// continuing code
121//
122// Because this pass tries to preserve the original BB order, this order will
123// not change. But this will result in this try-catch structure in CFGStackify,
124// resulting in a mismatch:
125// try
126// try
127// call @foo
128// call @bar // This should unwind to bb3, not bb2!
129// catch
130// handler_bb2
131// end
132// catch
133// handler_bb3
134// end
135// continuing code
136//
137// If we give a higher priority to an EH pad whenever it is ready in this
138// example, when both bb1 and bb2 are ready, we would pick up bb2 first.
139
140/// Sort blocks by their number.
141struct CompareBlockNumbers {
142 bool operator()(const MachineBasicBlock *A,
143 const MachineBasicBlock *B) const {
145 if (A->isEHPad() && !B->isEHPad())
146 return false;
147 if (!A->isEHPad() && B->isEHPad())
148 return true;
149 }
150
151 return A->getNumber() > B->getNumber();
152 }
153};
154/// Sort blocks by their number in the opposite order..
155struct CompareBlockNumbersBackwards {
156 bool operator()(const MachineBasicBlock *A,
157 const MachineBasicBlock *B) const {
159 if (A->isEHPad() && !B->isEHPad())
160 return false;
161 if (!A->isEHPad() && B->isEHPad())
162 return true;
163 }
164
165 return A->getNumber() < B->getNumber();
166 }
167};
168/// Bookkeeping for a region to help ensure that we don't mix blocks not
169/// dominated by the its header among its blocks.
170struct Entry {
171 const SortRegion *TheRegion;
172 unsigned NumBlocksLeft;
173
174 /// List of blocks not dominated by Loop's header that are deferred until
175 /// after all of Loop's blocks have been seen.
176 std::vector<MachineBasicBlock *> Deferred;
177
178 explicit Entry(const SortRegion *R)
179 : TheRegion(R), NumBlocksLeft(R->getNumBlocks()) {}
180};
181} // end anonymous namespace
182
183/// Sort the blocks, taking special care to make sure that regions are not
184/// interrupted by blocks not dominated by their header.
185/// TODO: There are many opportunities for improving the heuristics here.
186/// Explore them.
187static void sortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
188 const WebAssemblyExceptionInfo &WEI,
190 // Remember original layout ordering, so we can update terminators after
191 // reordering to point to the original layout successor.
192 MF.RenumberBlocks();
193 MDT.updateBlockNumbers();
194
195 // Prepare for a topological sort: Record the number of predecessors each
196 // block has, ignoring loop backedges.
197 SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0);
198 for (MachineBasicBlock &MBB : MF) {
199 unsigned N = MBB.pred_size();
200 if (MachineLoop *L = MLI.getLoopFor(&MBB))
201 if (L->getHeader() == &MBB)
202 for (const MachineBasicBlock *Pred : MBB.predecessors())
203 if (L->contains(Pred))
204 --N;
205 NumPredsLeft[MBB.getNumber()] = N;
206 }
207
208 // Topological sort the CFG, with additional constraints:
209 // - Between a region header and the last block in the region, there can be
210 // no blocks not dominated by its header.
211 // - It's desirable to preserve the original block order when possible.
212 // We use two ready lists; Preferred and Ready. Preferred has recently
213 // processed successors, to help preserve block sequences from the original
214 // order. Ready has the remaining ready blocks. EH blocks are picked first
215 // from both queues.
217 CompareBlockNumbers>
218 Preferred;
220 CompareBlockNumbersBackwards>
221 Ready;
222
223 const auto *EHInfo = MF.getWasmEHFuncInfo();
224 SortRegionInfo SRI(MLI, WEI);
225 SmallVector<Entry, 4> Entries;
226 for (MachineBasicBlock *MBB = &MF.front();;) {
227 const SortRegion *R = SRI.getRegionFor(MBB);
228 if (R) {
229 // If MBB is a region header, add it to the active region list. We can't
230 // put any blocks that it doesn't dominate until we see the end of the
231 // region.
232 if (R->getHeader() == MBB)
233 Entries.push_back(Entry(R));
234 // For each active region the block is in, decrement the count. If MBB is
235 // the last block in an active region, take it off the list and pick up
236 // any blocks deferred because the header didn't dominate them.
237 for (Entry &E : Entries)
238 if (E.TheRegion->contains(MBB) && --E.NumBlocksLeft == 0)
239 for (auto *DeferredBlock : E.Deferred)
240 Ready.push(DeferredBlock);
241 while (!Entries.empty() && Entries.back().NumBlocksLeft == 0)
242 Entries.pop_back();
243 }
244 // The main topological sort logic.
245 for (MachineBasicBlock *Succ : MBB->successors()) {
246 // Ignore backedges.
247 if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
248 if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
249 continue;
250 // Decrement the predecessor count. If it's now zero, it's ready.
251 if (--NumPredsLeft[Succ->getNumber()] == 0) {
252 // When we are in a SortRegion, we allow sorting of not only BBs that
253 // belong to the current (innermost) region but also BBs that are
254 // dominated by the current region header. But we should not do this for
255 // exceptions because there can be cases in which, for example:
256 // EHPad A's unwind destination (where the exception lands when it is
257 // not caught by EHPad A) is EHPad B, so EHPad B does not belong to the
258 // exception dominated by EHPad A. But EHPad B is dominated by EHPad A,
259 // so EHPad B can be sorted within EHPad A's exception. This is
260 // incorrect because we may end up delegating/rethrowing to an inner
261 // scope in CFGStackify. So here we make sure those unwind destinations
262 // are deferred until their unwind source's exception is sorted.
263 if (EHInfo && EHInfo->hasUnwindSrcs(Succ)) {
265 EHInfo->getUnwindSrcs(Succ);
266 bool IsDeferred = false;
267 for (Entry &E : Entries) {
268 if (UnwindSrcs.count(E.TheRegion->getHeader())) {
269 E.Deferred.push_back(Succ);
270 IsDeferred = true;
271 break;
272 }
273 }
274 if (IsDeferred)
275 continue;
276 }
277 Preferred.push(Succ);
278 }
279 }
280 // Determine the block to follow MBB. First try to find a preferred block,
281 // to preserve the original block order when possible.
282 MachineBasicBlock *Next = nullptr;
283 while (!Preferred.empty()) {
284 Next = Preferred.top();
285 Preferred.pop();
286 // If X isn't dominated by the top active region header, defer it until
287 // that region is done.
288 if (!Entries.empty() &&
289 !MDT.dominates(Entries.back().TheRegion->getHeader(), Next)) {
290 Entries.back().Deferred.push_back(Next);
291 Next = nullptr;
292 continue;
293 }
294 // If Next was originally ordered before MBB, and it isn't because it was
295 // loop-rotated above the header, it's not preferred.
296 if (Next->getNumber() < MBB->getNumber() &&
297 (WasmDisableEHPadSort || !Next->isEHPad()) &&
298 (!R || !R->contains(Next) ||
299 R->getHeader()->getNumber() < Next->getNumber())) {
300 Ready.push(Next);
301 Next = nullptr;
302 continue;
303 }
304 break;
305 }
306 // If we didn't find a suitable block in the Preferred list, check the
307 // general Ready list.
308 if (!Next) {
309 // If there are no more blocks to process, we're done.
310 if (Ready.empty()) {
312 break;
313 }
314 for (;;) {
315 Next = Ready.top();
316 Ready.pop();
317 // If Next isn't dominated by the top active region header, defer it
318 // until that region is done.
319 if (!Entries.empty() &&
320 !MDT.dominates(Entries.back().TheRegion->getHeader(), Next)) {
321 Entries.back().Deferred.push_back(Next);
322 continue;
323 }
324 break;
325 }
326 }
327 // Move the next block into place and iterate.
328 Next->moveAfter(MBB);
330 MBB = Next;
331 }
332 assert(Entries.empty() && "Active sort region list not finished");
333 MF.RenumberBlocks();
334 MDT.updateBlockNumbers();
335
336#ifndef NDEBUG
338
339 // Insert a sentinel representing the degenerate loop that starts at the
340 // function entry block and includes the entire function as a "loop" that
341 // executes once.
342 OnStack.insert(nullptr);
343
344 for (auto &MBB : MF) {
345 assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
346 const SortRegion *Region = SRI.getRegionFor(&MBB);
347
348 if (Region && &MBB == Region->getHeader()) {
349 // Region header.
350 if (Region->isLoop()) {
351 // Loop header. The loop predecessor should be sorted above, and the
352 // other predecessors should be backedges below.
353 for (auto *Pred : MBB.predecessors())
354 assert(
355 (Pred->getNumber() < MBB.getNumber() || Region->contains(Pred)) &&
356 "Loop header predecessors must be loop predecessors or "
357 "backedges");
358 } else {
359 // Exception header. All predecessors should be sorted above.
360 for (auto *Pred : MBB.predecessors())
361 assert(Pred->getNumber() < MBB.getNumber() &&
362 "Non-loop-header predecessors should be topologically sorted");
363 }
364 assert(OnStack.insert(Region) &&
365 "Regions should be declared at most once.");
366
367 } else {
368 // Not a region header. All predecessors should be sorted above.
369 for (auto *Pred : MBB.predecessors())
370 assert(Pred->getNumber() < MBB.getNumber() &&
371 "Non-loop-header predecessors should be topologically sorted");
372 assert(OnStack.count(SRI.getRegionFor(&MBB)) &&
373 "Blocks must be nested in their regions");
374 }
375 while (OnStack.size() > 1 && &MBB == SRI.getBottom(OnStack.back()))
376 OnStack.pop_back();
377 }
378 assert(OnStack.pop_back_val() == nullptr &&
379 "The function entry block shouldn't actually be a region header");
380 assert(OnStack.empty() &&
381 "Control flow stack pushes and pops should be balanced.");
382#endif
383}
384
385bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {
386 LLVM_DEBUG(dbgs() << "********** CFG Sorting **********\n"
387 "********** Function: "
388 << MF.getName() << '\n');
389
390 const auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
391 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
392 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
393 // Liveness is not tracked for VALUE_STACK physreg.
395
396 // Sort the blocks, with contiguous sort regions.
397 sortBlocks(MF, MLI, WEI, MDT);
398
399 return true;
400}
MachineBasicBlock & MBB
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
This file defines the PriorityQueue class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
static void sortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI, MachineDominatorTree &MDT)
Sort the blocks, taking special care to make sure that regions are not interrupted by blocks not domi...
static void maybeUpdateTerminator(MachineBasicBlock *MBB)
#define DEBUG_TYPE
static cl::opt< bool > WasmDisableEHPadSort("wasm-disable-ehpad-sort", cl::ReallyHidden, cl::desc("WebAssembly: Disable EH pad-first sort order. Testing purpose only."), cl::init(false))
This file implements WebAssemblyException information analysis.
This file provides WebAssembly-specific target descriptions.
This file implements regions used in CFGSort and CFGStackify.
This file declares the WebAssembly-specific subclass of TargetSubtarget.
This file contains the declaration of the WebAssembly-specific utility functions.
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:256
std::enable_if_t< GraphHasNodeNumbers< T * >, void > updateBlockNumbers()
Update dominator tree after renumbering blocks.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:310
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
unsigned pred_size() const
bool isEHPad() const
Returns true if the block is a landing pad.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
void updateTerminator(MachineBasicBlock *PreviousLayoutSuccessor)
Update the terminator instructions in block to account for changes to block layout which may have bee...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< iterator > terminators()
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
void moveAfter(MachineBasicBlock *NewBefore)
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
MachineBasicBlock * getBlockNumbered(unsigned N) const
getBlockNumbered - MachineBasicBlocks are automatically numbered when they are inserted into the mach...
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
const WasmEHFuncInfo * getWasmEHFuncInfo() const
getWasmEHFuncInfo - Return information about how the current function uses Wasm exception handling.
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them.
const MachineBasicBlock & front() const
Representation of each machine instruction.
Definition: MachineInstr.h:69
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
PriorityQueue - This class behaves like std::priority_queue and provides a few additional convenience...
Definition: PriorityQueue.h:28
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:98
const value_type & back() const
Return the last element of the SetVector.
Definition: SetVector.h:149
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:264
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
void pop_back()
Remove the last element of the SetVector.
Definition: SetVector.h:279
value_type pop_back_val()
Definition: SetVector.h:285
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:435
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:502
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
const SortRegion * getRegionFor(const MachineBasicBlock *MBB)
MachineBasicBlock * getBottom(const SortRegion *R)
@ Entry
Definition: COFF.h:826
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ ReallyHidden
Definition: CommandLine.h:138
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FunctionPass * createWebAssemblyCFGSort()
#define N