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
19#include "WebAssembly.h"
20#include "WebAssemblyExceptionInfo.h"
21#include "WebAssemblySortRegion.h"
22#include "WebAssemblyUtilities.h"
23#include "llvm/ADT/PriorityQueue.h"
24#include "llvm/ADT/SetVector.h"
25#include "llvm/CodeGen/MachineDominators.h"
26#include "llvm/CodeGen/MachineFunction.h"
27#include "llvm/CodeGen/MachineLoopInfo.h"
28#include "llvm/CodeGen/MachineRegisterInfo.h"
29#include "llvm/CodeGen/Passes.h"
30#include "llvm/CodeGen/WasmEHFuncInfo.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/raw_ostream.h"
33using namespace llvm;
34using WebAssembly::SortRegion;
35using WebAssembly::SortRegionInfo;
36
37#define DEBUG_TYPE "wasm-cfg-sort"
38
39// Option to disable EH pad first sorting. Only for testing unwind destination
40// mismatches in CFGStackify.
41static cl::opt<bool> WasmDisableEHPadSort(
42 "wasm-disable-ehpad-sort", cl::ReallyHidden,
43 cl::desc(
44 "WebAssembly: Disable EH pad-first sort order. Testing purpose only."),
45 cl::init(Val: false));
46
47namespace {
48
49class WebAssemblyCFGSort final : public MachineFunctionPass {
50 StringRef getPassName() const override { return "WebAssembly CFG Sort"; }
51
52 void getAnalysisUsage(AnalysisUsage &AU) const override {
53 AU.setPreservesCFG();
54 AU.addRequired<MachineDominatorTreeWrapperPass>();
55 AU.addPreserved<MachineDominatorTreeWrapperPass>();
56 AU.addRequired<MachineLoopInfoWrapperPass>();
57 AU.addPreserved<MachineLoopInfoWrapperPass>();
58 AU.addRequired<WebAssemblyExceptionInfo>();
59 AU.addPreserved<WebAssemblyExceptionInfo>();
60 MachineFunctionPass::getAnalysisUsage(AU);
61 }
62
63 bool runOnMachineFunction(MachineFunction &MF) override;
64
65public:
66 static char ID; // Pass identification, replacement for typeid
67 WebAssemblyCFGSort() : MachineFunctionPass(ID) {}
68};
69} // end anonymous namespace
70
71char WebAssemblyCFGSort::ID = 0;
72INITIALIZE_PASS(WebAssemblyCFGSort, DEBUG_TYPE,
73 "Reorders blocks in topological order", false, false)
74
75FunctionPass *llvm::createWebAssemblyCFGSort() {
76 return new WebAssemblyCFGSort();
77}
78
79static void maybeUpdateTerminator(MachineBasicBlock *MBB) {
80#ifndef NDEBUG
81 bool AnyBarrier = false;
82#endif
83 bool AllAnalyzable = true;
84 for (const MachineInstr &Term : MBB->terminators()) {
85#ifndef NDEBUG
86 AnyBarrier |= Term.isBarrier();
87#endif
88 AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
89 }
90 assert((AnyBarrier || AllAnalyzable) &&
91 "analyzeBranch needs to analyze any block with a fallthrough");
92
93 // Find the layout successor from the original block order.
94 MachineFunction *MF = MBB->getParent();
95 MachineBasicBlock *OriginalSuccessor =
96 unsigned(MBB->getNumber() + 1) < MF->getNumBlockIDs()
97 ? MF->getBlockNumbered(N: MBB->getNumber() + 1)
98 : nullptr;
99
100 if (AllAnalyzable)
101 MBB->updateTerminator(PreviousLayoutSuccessor: OriginalSuccessor);
102}
103
104namespace {
105// EH pads are selected first regardless of the block comparison order.
106// When only one of the BBs is an EH pad, we give a higher priority to it, to
107// prevent common mismatches between possibly throwing calls and ehpads they
108// unwind to, as in the example below:
109//
110// bb0:
111// call @foo // If this throws, unwind to bb2
112// bb1:
113// call @bar // If this throws, unwind to bb3
114// bb2 (ehpad):
115// handler_bb2
116// bb3 (ehpad):
117// handler_bb3
118// continuing code
119//
120// Because this pass tries to preserve the original BB order, this order will
121// not change. But this will result in this try-catch structure in CFGStackify,
122// resulting in a mismatch:
123// try
124// try
125// call @foo
126// call @bar // This should unwind to bb3, not bb2!
127// catch
128// handler_bb2
129// end
130// catch
131// handler_bb3
132// end
133// continuing code
134//
135// If we give a higher priority to an EH pad whenever it is ready in this
136// example, when both bb1 and bb2 are ready, we would pick up bb2 first.
137
138/// Sort blocks by their number.
139struct CompareBlockNumbers {
140 bool operator()(const MachineBasicBlock *A,
141 const MachineBasicBlock *B) const {
142 if (!WasmDisableEHPadSort) {
143 if (A->isEHPad() && !B->isEHPad())
144 return false;
145 if (!A->isEHPad() && B->isEHPad())
146 return true;
147 }
148
149 return A->getNumber() > B->getNumber();
150 }
151};
152/// Sort blocks by their number in the opposite order..
153struct CompareBlockNumbersBackwards {
154 bool operator()(const MachineBasicBlock *A,
155 const MachineBasicBlock *B) const {
156 if (!WasmDisableEHPadSort) {
157 if (A->isEHPad() && !B->isEHPad())
158 return false;
159 if (!A->isEHPad() && B->isEHPad())
160 return true;
161 }
162
163 return A->getNumber() < B->getNumber();
164 }
165};
166/// Bookkeeping for a region to help ensure that we don't mix blocks not
167/// dominated by the its header among its blocks.
168struct Entry {
169 const SortRegion *TheRegion;
170 unsigned NumBlocksLeft;
171
172 /// List of blocks not dominated by Loop's header that are deferred until
173 /// after all of Loop's blocks have been seen.
174 std::vector<MachineBasicBlock *> Deferred;
175
176 explicit Entry(const SortRegion *R)
177 : TheRegion(R), NumBlocksLeft(R->getNumBlocks()) {}
178};
179} // end anonymous namespace
180
181/// Sort the blocks, taking special care to make sure that regions are not
182/// interrupted by blocks not dominated by their header.
183/// TODO: There are many opportunities for improving the heuristics here.
184/// Explore them.
185static void sortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
186 const WebAssemblyExceptionInfo &WEI,
187 MachineDominatorTree &MDT) {
188 // Remember original layout ordering, so we can update terminators after
189 // reordering to point to the original layout successor.
190 MF.RenumberBlocks();
191
192 // Prepare for a topological sort: Record the number of predecessors each
193 // block has, ignoring loop backedges.
194 SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0);
195 for (MachineBasicBlock &MBB : MF) {
196 unsigned N = MBB.pred_size();
197 if (MachineLoop *L = MLI.getLoopFor(BB: &MBB))
198 if (L->getHeader() == &MBB)
199 for (const MachineBasicBlock *Pred : MBB.predecessors())
200 if (L->contains(BB: Pred))
201 --N;
202 NumPredsLeft[MBB.getNumber()] = N;
203 }
204
205 // Topological sort the CFG, with additional constraints:
206 // - Between a region header and the last block in the region, there can be
207 // no blocks not dominated by its header.
208 // - It's desirable to preserve the original block order when possible.
209 // We use two ready lists; Preferred and Ready. Preferred has recently
210 // processed successors, to help preserve block sequences from the original
211 // order. Ready has the remaining ready blocks. EH blocks are picked first
212 // from both queues.
213 PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
214 CompareBlockNumbers>
215 Preferred;
216 PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
217 CompareBlockNumbersBackwards>
218 Ready;
219
220 const auto *EHInfo = MF.getWasmEHFuncInfo();
221 SortRegionInfo SRI(MLI, WEI);
222 SmallVector<Entry, 4> Entries;
223 for (MachineBasicBlock *MBB = &MF.front();;) {
224 const SortRegion *R = SRI.getRegionFor(MBB);
225 if (R) {
226 // If MBB is a region header, add it to the active region list. We can't
227 // put any blocks that it doesn't dominate until we see the end of the
228 // region.
229 if (R->getHeader() == MBB)
230 Entries.push_back(Elt: Entry(R));
231 // For each active region the block is in, decrement the count. If MBB is
232 // the last block in an active region, take it off the list and pick up
233 // any blocks deferred because the header didn't dominate them.
234 for (Entry &E : Entries)
235 if (E.TheRegion->contains(MBB) && --E.NumBlocksLeft == 0)
236 for (auto *DeferredBlock : E.Deferred)
237 Ready.push(x: DeferredBlock);
238 while (!Entries.empty() && Entries.back().NumBlocksLeft == 0)
239 Entries.pop_back();
240 }
241 // The main topological sort logic.
242 for (MachineBasicBlock *Succ : MBB->successors()) {
243 // Ignore backedges.
244 if (MachineLoop *SuccL = MLI.getLoopFor(BB: Succ))
245 if (SuccL->getHeader() == Succ && SuccL->contains(BB: MBB))
246 continue;
247 // Decrement the predecessor count. If it's now zero, it's ready.
248 if (--NumPredsLeft[Succ->getNumber()] == 0) {
249 // When we are in a SortRegion, we allow sorting of not only BBs that
250 // belong to the current (innermost) region but also BBs that are
251 // dominated by the current region header. But we should not do this for
252 // exceptions because there can be cases in which, for example:
253 // EHPad A's unwind destination (where the exception lands when it is
254 // not caught by EHPad A) is EHPad B, so EHPad B does not belong to the
255 // exception dominated by EHPad A. But EHPad B is dominated by EHPad A,
256 // so EHPad B can be sorted within EHPad A's exception. This is
257 // incorrect because we may end up delegating/rethrowing to an inner
258 // scope in CFGStackify. So here we make sure those unwind destinations
259 // are deferred until their unwind source's exception is sorted.
260 if (EHInfo && EHInfo->hasUnwindSrcs(MBB: Succ)) {
261 SmallPtrSet<MachineBasicBlock *, 4> UnwindSrcs =
262 EHInfo->getUnwindSrcs(MBB: Succ);
263 bool IsDeferred = false;
264 for (Entry &E : Entries) {
265 if (UnwindSrcs.count(Ptr: E.TheRegion->getHeader())) {
266 E.Deferred.push_back(x: Succ);
267 IsDeferred = true;
268 break;
269 }
270 }
271 if (IsDeferred)
272 continue;
273 }
274 Preferred.push(x: Succ);
275 }
276 }
277 // Determine the block to follow MBB. First try to find a preferred block,
278 // to preserve the original block order when possible.
279 MachineBasicBlock *Next = nullptr;
280 while (!Preferred.empty()) {
281 Next = Preferred.top();
282 Preferred.pop();
283 // If X isn't dominated by the top active region header, defer it until
284 // that region is done.
285 if (!Entries.empty() &&
286 !MDT.dominates(A: Entries.back().TheRegion->getHeader(), B: Next)) {
287 Entries.back().Deferred.push_back(x: Next);
288 Next = nullptr;
289 continue;
290 }
291 // If Next was originally ordered before MBB, and it isn't because it was
292 // loop-rotated above the header, it's not preferred.
293 if (Next->getNumber() < MBB->getNumber() &&
294 (WasmDisableEHPadSort || !Next->isEHPad()) &&
295 (!R || !R->contains(MBB: Next) ||
296 R->getHeader()->getNumber() < Next->getNumber())) {
297 Ready.push(x: Next);
298 Next = nullptr;
299 continue;
300 }
301 break;
302 }
303 // If we didn't find a suitable block in the Preferred list, check the
304 // general Ready list.
305 if (!Next) {
306 // If there are no more blocks to process, we're done.
307 if (Ready.empty()) {
308 maybeUpdateTerminator(MBB);
309 break;
310 }
311 for (;;) {
312 Next = Ready.top();
313 Ready.pop();
314 // If Next isn't dominated by the top active region header, defer it
315 // until that region is done.
316 if (!Entries.empty() &&
317 !MDT.dominates(A: Entries.back().TheRegion->getHeader(), B: Next)) {
318 Entries.back().Deferred.push_back(x: Next);
319 continue;
320 }
321 break;
322 }
323 }
324 // Move the next block into place and iterate.
325 Next->moveAfter(NewBefore: MBB);
326 maybeUpdateTerminator(MBB);
327 MBB = Next;
328 }
329 assert(Entries.empty() && "Active sort region list not finished");
330 MF.RenumberBlocks();
331
332#ifndef NDEBUG
333 for (auto &MBB : MF) {
334 assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
335 const SortRegion *Region = SRI.getRegionFor(&MBB);
336
337 if (Region && &MBB == Region->getHeader()) {
338 // Region header.
339 if (Region->isLoop()) {
340 // Loop header. The loop predecessor should be sorted above, and the
341 // other predecessors should be backedges below.
342 for (auto *Pred : MBB.predecessors())
343 assert(
344 (Pred->getNumber() < MBB.getNumber() || Region->contains(Pred)) &&
345 "Loop header predecessors must be loop predecessors or "
346 "backedges");
347 } else {
348 // Exception header. All predecessors should be sorted above.
349 for (auto *Pred : MBB.predecessors())
350 assert(Pred->getNumber() < MBB.getNumber() &&
351 "Non-loop-header predecessors should be topologically sorted");
352 }
353 } else {
354 // Not a region header. All predecessors should be sorted above.
355 for (auto *Pred : MBB.predecessors())
356 assert(Pred->getNumber() < MBB.getNumber() &&
357 "Non-loop-header predecessors should be topologically sorted");
358 }
359 }
360
361 SmallSet<const SortRegion *, 8> Regions;
362 for (auto &MBB : MF) {
363 const SortRegion *Region = SRI.getRegionFor(&MBB);
364 if (Region)
365 Regions.insert(Region);
366 }
367
368 SmallVector<std::pair<int, int>, 8> RegionIntervals(Regions.size(), {-1, -1});
369
370 unsigned RegionIdx = 0;
371 for (auto *Region : Regions) {
372 assert(Region->getHeader() != &MF.front() &&
373 "The function entry block shouldn't actually be a region header");
374
375 auto *Header = Region->getHeader();
376 auto *Bottom = SRI.getBottom(Region);
377
378 assert(Header && "Regions must have a header");
379 assert(Bottom && "Regions must have a bottom");
380
381 std::pair<int, int> Interval = {Header->getNumber(), Bottom->getNumber()};
382 assert(Interval.first <= Interval.second &&
383 "Region bottoms must be sorted after region headers");
384
385 RegionIntervals[RegionIdx++] = Interval;
386
387 for (auto *MBB : Region->blocks()) {
388 assert(MBB->getNumber() >= Interval.first &&
389 MBB->getNumber() <= Interval.second &&
390 "All blocks within a region must have numbers within the region's "
391 "interval");
392 }
393 }
394
395 for (const auto &IntervalA : RegionIntervals) {
396 for (const auto &IntervalB : RegionIntervals) {
397 auto AContainsB = IntervalA.first <= IntervalB.first &&
398 IntervalA.second >= IntervalB.second;
399 auto BContainsA = IntervalB.first <= IntervalA.first &&
400 IntervalB.second >= IntervalA.second;
401 auto Disjoint = IntervalA.second < IntervalB.first ||
402 IntervalA.first > IntervalB.second;
403 assert((AContainsB || BContainsA || Disjoint) &&
404 "Regions must be fully contained within their parents and not "
405 "overlap their siblings");
406 }
407 }
408#endif
409}
410
411bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {
412 LLVM_DEBUG(dbgs() << "********** CFG Sorting **********\n"
413 "********** Function: "
414 << MF.getName() << '\n');
415
416 const auto &MLI = getAnalysis<MachineLoopInfoWrapperPass>().getLI();
417 const auto &WEI = getAnalysis<WebAssemblyExceptionInfo>();
418 auto &MDT = getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
419 // Liveness is not tracked for VALUE_STACK physreg.
420 MF.getRegInfo().invalidateLiveness();
421
422 // Sort the blocks, with contiguous sort regions.
423 sortBlocks(MF, MLI, WEI, MDT);
424
425 return true;
426}
427