Line data Source code
1 : //===-- WebAssemblyCFGSort.cpp - CFG Sorting ------------------------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : ///
10 : /// \file
11 : /// This file implements a CFG sorting pass.
12 : ///
13 : /// This pass reorders the blocks in a function to put them into topological
14 : /// order, ignoring loop backedges, and without any loop or exception being
15 : /// interrupted by a block not dominated by the its header, with special care
16 : /// to keep the order as similar as possible to the original order.
17 : ///
18 : ////===----------------------------------------------------------------------===//
19 :
20 : #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
21 : #include "WebAssembly.h"
22 : #include "WebAssemblyExceptionInfo.h"
23 : #include "WebAssemblySubtarget.h"
24 : #include "WebAssemblyUtilities.h"
25 : #include "llvm/ADT/PriorityQueue.h"
26 : #include "llvm/ADT/SetVector.h"
27 : #include "llvm/CodeGen/MachineDominators.h"
28 : #include "llvm/CodeGen/MachineFunction.h"
29 : #include "llvm/CodeGen/MachineLoopInfo.h"
30 : #include "llvm/CodeGen/MachineRegisterInfo.h"
31 : #include "llvm/CodeGen/Passes.h"
32 : #include "llvm/Support/Debug.h"
33 : #include "llvm/Support/raw_ostream.h"
34 : using namespace llvm;
35 :
36 : #define DEBUG_TYPE "wasm-cfg-sort"
37 :
38 : namespace {
39 :
40 : // Wrapper for loops and exceptions
41 : class Region {
42 : public:
43 : virtual ~Region() = default;
44 : virtual MachineBasicBlock *getHeader() const = 0;
45 : virtual bool contains(const MachineBasicBlock *MBB) const = 0;
46 : virtual unsigned getNumBlocks() const = 0;
47 : using block_iterator = typename ArrayRef<MachineBasicBlock *>::const_iterator;
48 : virtual iterator_range<block_iterator> blocks() const = 0;
49 : virtual bool isLoop() const = 0;
50 : };
51 :
52 0 : template <typename T> class ConcreteRegion : public Region {
53 : const T *Region;
54 :
55 : public:
56 98 : ConcreteRegion(const T *Region) : Region(Region) {}
57 646 : MachineBasicBlock *getHeader() const override { return Region->getHeader(); }
58 272 : bool contains(const MachineBasicBlock *MBB) const override {
59 272 : return Region->contains(MBB);
60 : }
61 206 : unsigned getNumBlocks() const override { return Region->getNumBlocks(); }
62 206 : iterator_range<block_iterator> blocks() const override {
63 : return Region->blocks();
64 66 : }
65 66 : bool isLoop() const override { return false; }
66 : };
67 196 :
68 0 : template <> bool ConcreteRegion<MachineLoop>::isLoop() const { return true; }
69 0 :
70 : // This class has information of nested Regions; this is analogous to what
71 0 : // LoopInfo is for loops.
72 0 : class RegionInfo {
73 : const MachineLoopInfo &MLI;
74 0 : const WebAssemblyExceptionInfo &WEI;
75 0 : std::vector<const Region *> Regions;
76 : DenseMap<const MachineLoop *, std::unique_ptr<Region>> LoopMap;
77 0 : DenseMap<const WebAssemblyException *, std::unique_ptr<Region>> ExceptionMap;
78 :
79 : public:
80 0 : RegionInfo(const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI)
81 : : MLI(MLI), WEI(WEI) {}
82 :
83 : // Returns a smallest loop or exception that contains MBB
84 : const Region *getRegionFor(const MachineBasicBlock *MBB) {
85 : const auto *ML = MLI.getLoopFor(MBB);
86 : const auto *WE = WEI.getExceptionFor(MBB);
87 : if (!ML && !WE)
88 : return nullptr;
89 : if ((ML && !WE) || (ML && WE && ML->getNumBlocks() < WE->getNumBlocks())) {
90 : // If the smallest region containing MBB is a loop
91 : if (LoopMap.count(ML))
92 2983 : return LoopMap[ML].get();
93 5966 : LoopMap[ML] = llvm::make_unique<ConcreteRegion<MachineLoop>>(ML);
94 : return LoopMap[ML].get();
95 : } else {
96 3541 : // If the smallest region containing MBB is an exception
97 3541 : if (ExceptionMap.count(WE))
98 3541 : return ExceptionMap[WE].get();
99 3541 : ExceptionMap[WE] =
100 : llvm::make_unique<ConcreteRegion<WebAssemblyException>>(WE);
101 204 : return ExceptionMap[WE].get();
102 : }
103 249 : }
104 84 : };
105 81 :
106 81 : class WebAssemblyCFGSort final : public MachineFunctionPass {
107 : StringRef getPassName() const override { return "WebAssembly CFG Sort"; }
108 :
109 61 : void getAnalysisUsage(AnalysisUsage &AU) const override {
110 22 : AU.setPreservesCFG();
111 : AU.addRequired<MachineDominatorTree>();
112 17 : AU.addPreserved<MachineDominatorTree>();
113 17 : AU.addRequired<MachineLoopInfo>();
114 : AU.addPreserved<MachineLoopInfo>();
115 : AU.addRequired<WebAssemblyExceptionInfo>();
116 : AU.addPreserved<WebAssemblyExceptionInfo>();
117 : MachineFunctionPass::getAnalysisUsage(AU);
118 : }
119 305 :
120 : bool runOnMachineFunction(MachineFunction &MF) override;
121 305 :
122 305 : public:
123 : static char ID; // Pass identification, replacement for typeid
124 : WebAssemblyCFGSort() : MachineFunctionPass(ID) {}
125 : };
126 : } // end anonymous namespace
127 :
128 : char WebAssemblyCFGSort::ID = 0;
129 305 : INITIALIZE_PASS(WebAssemblyCFGSort, DEBUG_TYPE,
130 305 : "Reorders blocks in topological order", false, false)
131 :
132 : FunctionPass *llvm::createWebAssemblyCFGSort() {
133 : return new WebAssemblyCFGSort();
134 : }
135 :
136 305 : static void MaybeUpdateTerminator(MachineBasicBlock *MBB) {
137 : #ifndef NDEBUG
138 : bool AnyBarrier = false;
139 : #endif
140 : bool AllAnalyzable = true;
141 199030 : for (const MachineInstr &Term : MBB->terminators()) {
142 : #ifndef NDEBUG
143 : AnyBarrier |= Term.isBarrier();
144 305 : #endif
145 305 : AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
146 : }
147 : assert((AnyBarrier || AllAnalyzable) &&
148 3541 : "AnalyzeBranch needs to analyze any block with a fallthrough");
149 : if (AllAnalyzable)
150 : MBB->updateTerminator();
151 : }
152 :
153 6987 : namespace {
154 : // EH pads are selected first regardless of the block comparison order.
155 : // When only one of the BBs is an EH pad, we give a higher priority to it, to
156 : // prevent common mismatches between possibly throwing calls and ehpads they
157 3799 : // unwind to, as in the example below:
158 : //
159 : // bb0:
160 : // call @foo // If this throws, unwind to bb2
161 3541 : // bb1:
162 467 : // call @bar // If this throws, unwind to bb3
163 3541 : // bb2 (ehpad):
164 : // handler_bb2
165 : // bb3 (ehpad):
166 : // handler_bb3
167 : // continuing code
168 : //
169 : // Because this pass tries to preserve the original BB order, this order will
170 : // not change. But this will result in this try-catch structure in CFGStackify,
171 : // resulting in a mismatch:
172 : // try
173 : // try
174 : // call @foo
175 : // call @bar // This should unwind to bb3, not bb2!
176 : // catch
177 : // handler_bb2
178 : // end
179 : // catch
180 : // handler_bb3
181 : // end
182 : // continuing code
183 : //
184 : // If we give a higher priority to an EH pad whenever it is ready in this
185 : // example, when both bb1 and bb2 are ready, we would pick up bb2 first.
186 :
187 : /// Sort blocks by their number.
188 : struct CompareBlockNumbers {
189 : bool operator()(const MachineBasicBlock *A,
190 : const MachineBasicBlock *B) const {
191 : if (A->isEHPad() && !B->isEHPad())
192 : return false;
193 : if (!A->isEHPad() && B->isEHPad())
194 : return true;
195 :
196 : return A->getNumber() > B->getNumber();
197 : }
198 : };
199 : /// Sort blocks by their number in the opposite order..
200 : struct CompareBlockNumbersBackwards {
201 0 : bool operator()(const MachineBasicBlock *A,
202 : const MachineBasicBlock *B) const {
203 0 : // We give a higher priority to an EH pad
204 0 : if (A->isEHPad() && !B->isEHPad())
205 0 : return false;
206 0 : if (!A->isEHPad() && B->isEHPad())
207 : return true;
208 0 :
209 : return A->getNumber() < B->getNumber();
210 : }
211 : };
212 : /// Bookkeeping for a region to help ensure that we don't mix blocks not
213 0 : /// dominated by the its header among its blocks.
214 : struct Entry {
215 : const Region *TheRegion;
216 0 : unsigned NumBlocksLeft;
217 0 :
218 0 : /// List of blocks not dominated by Loop's header that are deferred until
219 0 : /// after all of Loop's blocks have been seen.
220 : std::vector<MachineBasicBlock *> Deferred;
221 0 :
222 : explicit Entry(const class Region *R)
223 : : TheRegion(R), NumBlocksLeft(R->getNumBlocks()) {}
224 : };
225 : } // end anonymous namespace
226 0 :
227 : /// Sort the blocks, taking special care to make sure that regions are not
228 : /// interrupted by blocks not dominated by their header.
229 : /// TODO: There are many opportunities for improving the heuristics here.
230 : /// Explore them.
231 : static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
232 : const WebAssemblyExceptionInfo &WEI,
233 : const MachineDominatorTree &MDT) {
234 : // Prepare for a topological sort: Record the number of predecessors each
235 98 : // block has, ignoring loop backedges.
236 : MF.RenumberBlocks();
237 : SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0);
238 : for (MachineBasicBlock &MBB : MF) {
239 : unsigned N = MBB.pred_size();
240 : if (MachineLoop *L = MLI.getLoopFor(&MBB))
241 : if (L->getHeader() == &MBB)
242 : for (const MachineBasicBlock *Pred : MBB.predecessors())
243 2983 : if (L->contains(Pred))
244 : --N;
245 : NumPredsLeft[MBB.getNumber()] = N;
246 : }
247 :
248 2983 : // Topological sort the CFG, with additional constraints:
249 5966 : // - Between a region header and the last block in the region, there can be
250 6524 : // no blocks not dominated by its header.
251 : // - It's desirable to preserve the original block order when possible.
252 165 : // We use two ready lists; Preferred and Ready. Preferred has recently
253 165 : // processed successors, to help preserve block sequences from the original
254 269 : // order. Ready has the remaining ready blocks. EH blocks are picked first
255 188 : // from both queues.
256 105 : PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
257 7082 : CompareBlockNumbers>
258 : Preferred;
259 : PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
260 : CompareBlockNumbersBackwards>
261 : Ready;
262 :
263 : RegionInfo SUI(MLI, WEI);
264 : SmallVector<Entry, 4> Entries;
265 : for (MachineBasicBlock *MBB = &MF.front();;) {
266 : const Region *R = SUI.getRegionFor(MBB);
267 : if (R) {
268 : // If MBB is a region header, add it to the active region list. We can't
269 : // put any blocks that it doesn't dominate until we see the end of the
270 2983 : // region.
271 : if (R->getHeader() == MBB)
272 : Entries.push_back(Entry(R));
273 2983 : // For each active region the block is in, decrement the count. If MBB is
274 : // the last block in an active region, take it off the list and pick up
275 5966 : // any blocks deferred because the header didn't dominate them.
276 2983 : for (Entry &E : Entries)
277 : if (E.TheRegion->contains(MBB) && --E.NumBlocksLeft == 0)
278 3541 : for (auto DeferredBlock : E.Deferred)
279 3541 : Ready.push(DeferredBlock);
280 : while (!Entries.empty() && Entries.back().NumBlocksLeft == 0)
281 : Entries.pop_back();
282 : }
283 204 : // The main topological sort logic.
284 196 : for (MachineBasicBlock *Succ : MBB->successors()) {
285 : // Ignore backedges.
286 : if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
287 : if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
288 455 : continue;
289 251 : // Decrement the predecessor count. If it's now zero, it's ready.
290 109 : if (--NumPredsLeft[Succ->getNumber()] == 0)
291 11 : Preferred.push(Succ);
292 524 : }
293 98 : // Determine the block to follow MBB. First try to find a preferred block,
294 : // to preserve the original block order when possible.
295 : MachineBasicBlock *Next = nullptr;
296 4306 : while (!Preferred.empty()) {
297 : Next = Preferred.top();
298 283 : Preferred.pop();
299 471 : // If X isn't dominated by the top active region header, defer it until
300 : // that region is done.
301 : if (!Entries.empty() &&
302 1320 : !MDT.dominates(Entries.back().TheRegion->getHeader(), Next)) {
303 558 : Entries.back().Deferred.push_back(Next);
304 : Next = nullptr;
305 : continue;
306 : }
307 3541 : // If Next was originally ordered before MBB, and it isn't because it was
308 3571 : // loop-rotated above the header, it's not preferred.
309 558 : if (Next->getNumber() < MBB->getNumber() &&
310 : (!R || !R->contains(Next) ||
311 : R->getHeader()->getNumber() < Next->getNumber())) {
312 : Ready.push(Next);
313 698 : Next = nullptr;
314 140 : continue;
315 11 : }
316 11 : break;
317 11 : }
318 : // If we didn't find a suitable block in the Preferred list, check the
319 : // general Ready list.
320 : if (!Next) {
321 547 : // If there are no more blocks to process, we're done.
322 21 : if (Ready.empty()) {
323 8 : MaybeUpdateTerminator(MBB);
324 19 : break;
325 19 : }
326 19 : for (;;) {
327 : Next = Ready.top();
328 : Ready.pop();
329 : // If Next isn't dominated by the top active region header, defer it
330 : // until that region is done.
331 : if (!Entries.empty() &&
332 3541 : !MDT.dominates(Entries.back().TheRegion->getHeader(), Next)) {
333 : Entries.back().Deferred.push_back(Next);
334 3013 : continue;
335 2983 : }
336 2983 : break;
337 : }
338 : }
339 30 : // Move the next block into place and iterate.
340 : Next->moveAfter(MBB);
341 : MaybeUpdateTerminator(MBB);
342 : MBB = Next;
343 41 : }
344 11 : assert(Entries.empty() && "Active sort region list not finished");
345 0 : MF.RenumberBlocks();
346 :
347 : #ifndef NDEBUG
348 : SmallSetVector<const Region *, 8> OnStack;
349 :
350 : // Insert a sentinel representing the degenerate loop that starts at the
351 : // function entry block and includes the entire function as a "loop" that
352 558 : // executes once.
353 558 : OnStack.insert(nullptr);
354 558 :
355 558 : for (auto &MBB : MF) {
356 : assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
357 2983 : const Region *Region = SUI.getRegionFor(&MBB);
358 :
359 : if (Region && &MBB == Region->getHeader()) {
360 : if (Region->isLoop()) {
361 : // Loop header. The loop predecessor should be sorted above, and the
362 : // other predecessors should be backedges below.
363 : for (auto Pred : MBB.predecessors())
364 : assert(
365 : (Pred->getNumber() < MBB.getNumber() || Region->contains(Pred)) &&
366 : "Loop header predecessors must be loop predecessors or "
367 : "backedges");
368 : } else {
369 : // Not a loop header. All predecessors should be sorted above.
370 : for (auto Pred : MBB.predecessors())
371 : assert(Pred->getNumber() < MBB.getNumber() &&
372 : "Non-loop-header predecessors should be topologically sorted");
373 : }
374 : assert(OnStack.insert(Region) &&
375 : "Regions should be declared at most once.");
376 :
377 : } else {
378 : // Not a loop header. All predecessors should be sorted above.
379 : for (auto Pred : MBB.predecessors())
380 : assert(Pred->getNumber() < MBB.getNumber() &&
381 : "Non-loop-header predecessors should be topologically sorted");
382 : assert(OnStack.count(SUI.getRegionFor(&MBB)) &&
383 : "Blocks must be nested in their regions");
384 : }
385 : while (OnStack.size() > 1 && &MBB == WebAssembly::getBottom(OnStack.back()))
386 : OnStack.pop_back();
387 : }
388 : assert(OnStack.pop_back_val() == nullptr &&
389 : "The function entry block shouldn't actually be a region header");
390 : assert(OnStack.empty() &&
391 : "Control flow stack pushes and pops should be balanced.");
392 : #endif
393 : }
394 :
395 : bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {
396 : LLVM_DEBUG(dbgs() << "********** CFG Sorting **********\n"
397 : "********** Function: "
398 : << MF.getName() << '\n');
399 :
400 : const auto &MLI = getAnalysis<MachineLoopInfo>();
401 : const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
402 : auto &MDT = getAnalysis<MachineDominatorTree>();
403 : // Liveness is not tracked for VALUE_STACK physreg.
404 : MF.getRegInfo().invalidateLiveness();
405 2983 :
406 : // Sort the blocks, with contiguous sort regions.
407 2983 : SortBlocks(MF, MLI, WEI, MDT);
408 :
409 : return true;
410 : }
|
