LLVM  10.0.0svn
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"
22 #include "WebAssemblySubtarget.h"
23 #include "WebAssemblyUtilities.h"
24 #include "llvm/ADT/PriorityQueue.h"
25 #include "llvm/ADT/SetVector.h"
30 #include "llvm/CodeGen/Passes.h"
31 #include "llvm/Support/Debug.h"
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "wasm-cfg-sort"
36 
37 // Option to disable EH pad first sorting. Only for testing unwind destination
38 // mismatches in CFGStackify.
40  "wasm-disable-ehpad-sort", cl::ReallyHidden,
41  cl::desc(
42  "WebAssembly: Disable EH pad-first sort order. Testing purpose only."),
43  cl::init(false));
44 
45 namespace {
46 
47 // Wrapper for loops and exceptions
48 class Region {
49 public:
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;
55  virtual iterator_range<block_iterator> blocks() const = 0;
56  virtual bool isLoop() const = 0;
57 };
58 
59 template <typename T> class ConcreteRegion : public Region {
60  const T *Region;
61 
62 public:
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);
67  }
68  unsigned getNumBlocks() const override { return Region->getNumBlocks(); }
69  iterator_range<block_iterator> blocks() const override {
70  return Region->blocks();
71  }
72  bool isLoop() const override { return false; }
73 };
74 
75 template <> bool ConcreteRegion<MachineLoop>::isLoop() const { return true; }
76 
77 // This class has information of nested Regions; this is analogous to what
78 // LoopInfo is for loops.
79 class RegionInfo {
80  const MachineLoopInfo &MLI;
81  const WebAssemblyExceptionInfo &WEI;
82  std::vector<const Region *> Regions;
85 
86 public:
88  : MLI(MLI), WEI(WEI) {}
89 
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);
94  if (!ML && !WE)
95  return nullptr;
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();
102  } else {
103  // If the smallest region containing MBB is an exception
104  if (ExceptionMap.count(WE))
105  return ExceptionMap[WE].get();
106  ExceptionMap[WE] =
107  std::make_unique<ConcreteRegion<WebAssemblyException>>(WE);
108  return ExceptionMap[WE].get();
109  }
110  }
111 };
112 
113 class WebAssemblyCFGSort final : public MachineFunctionPass {
114  StringRef getPassName() const override { return "WebAssembly CFG Sort"; }
115 
116  void getAnalysisUsage(AnalysisUsage &AU) const override {
117  AU.setPreservesCFG();
125  }
126 
127  bool runOnMachineFunction(MachineFunction &MF) override;
128 
129 public:
130  static char ID; // Pass identification, replacement for typeid
131  WebAssemblyCFGSort() : MachineFunctionPass(ID) {}
132 };
133 } // end anonymous namespace
134 
135 char WebAssemblyCFGSort::ID = 0;
136 INITIALIZE_PASS(WebAssemblyCFGSort, DEBUG_TYPE,
137  "Reorders blocks in topological order", false, false)
138 
140  return new WebAssemblyCFGSort();
141 }
142 
144 #ifndef NDEBUG
145  bool AnyBarrier = false;
146 #endif
147  bool AllAnalyzable = true;
148  for (const MachineInstr &Term : MBB->terminators()) {
149 #ifndef NDEBUG
150  AnyBarrier |= Term.isBarrier();
151 #endif
152  AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
153  }
154  assert((AnyBarrier || AllAnalyzable) &&
155  "AnalyzeBranch needs to analyze any block with a fallthrough");
156  if (AllAnalyzable)
157  MBB->updateTerminator();
158 }
159 
160 namespace {
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:
165 //
166 // bb0:
167 // call @foo // If this throws, unwind to bb2
168 // bb1:
169 // call @bar // If this throws, unwind to bb3
170 // bb2 (ehpad):
171 // handler_bb2
172 // bb3 (ehpad):
173 // handler_bb3
174 // continuing code
175 //
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:
179 // try
180 // try
181 // call @foo
182 // call @bar // This should unwind to bb3, not bb2!
183 // catch
184 // handler_bb2
185 // end
186 // catch
187 // handler_bb3
188 // end
189 // continuing code
190 //
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.
193 
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())
200  return false;
201  if (!A->isEHPad() && B->isEHPad())
202  return true;
203  }
204 
205  return A->getNumber() > B->getNumber();
206  }
207 };
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())
214  return false;
215  if (!A->isEHPad() && B->isEHPad())
216  return true;
217  }
218 
219  return A->getNumber() < B->getNumber();
220  }
221 };
222 /// Bookkeeping for a region to help ensure that we don't mix blocks not
223 /// dominated by the its header among its blocks.
224 struct Entry {
225  const Region *TheRegion;
226  unsigned NumBlocksLeft;
227 
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;
231 
232  explicit Entry(const class Region *R)
233  : TheRegion(R), NumBlocksLeft(R->getNumBlocks()) {}
234 };
235 } // end anonymous namespace
236 
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.
240 /// Explore them.
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.
246  MF.RenumberBlocks();
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))
254  --N;
255  NumPredsLeft[MBB.getNumber()] = N;
256  }
257 
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
265  // from both queues.
267  CompareBlockNumbers>
268  Preferred;
270  CompareBlockNumbersBackwards>
271  Ready;
272 
273  RegionInfo RI(MLI, WEI);
274  SmallVector<Entry, 4> Entries;
275  for (MachineBasicBlock *MBB = &MF.front();;) {
276  const Region *R = RI.getRegionFor(MBB);
277  if (R) {
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
280  // region.
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)
291  Entries.pop_back();
292  }
293  // The main topological sort logic.
294  for (MachineBasicBlock *Succ : MBB->successors()) {
295  // Ignore backedges.
296  if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
297  if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
298  continue;
299  // Decrement the predecessor count. If it's now zero, it's ready.
300  if (--NumPredsLeft[Succ->getNumber()] == 0)
301  Preferred.push(Succ);
302  }
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();
308  Preferred.pop();
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);
314  Next = nullptr;
315  continue;
316  }
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())) {
322  Ready.push(Next);
323  Next = nullptr;
324  continue;
325  }
326  break;
327  }
328  // If we didn't find a suitable block in the Preferred list, check the
329  // general Ready list.
330  if (!Next) {
331  // If there are no more blocks to process, we're done.
332  if (Ready.empty()) {
334  break;
335  }
336  for (;;) {
337  Next = Ready.top();
338  Ready.pop();
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);
344  continue;
345  }
346  break;
347  }
348  }
349  // Move the next block into place and iterate.
350  Next->moveAfter(MBB);
352  MBB = Next;
353  }
354  assert(Entries.empty() && "Active sort region list not finished");
355  MF.RenumberBlocks();
356 
357 #ifndef NDEBUG
359 
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
362  // executes once.
363  OnStack.insert(nullptr);
364 
365  for (auto &MBB : MF) {
366  assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
367  const Region *Region = RI.getRegionFor(&MBB);
368 
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())
374  assert(
375  (Pred->getNumber() < MBB.getNumber() || Region->contains(Pred)) &&
376  "Loop header predecessors must be loop predecessors or "
377  "backedges");
378  } else {
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");
383  }
384  assert(OnStack.insert(Region) &&
385  "Regions should be declared at most once.");
386 
387  } else {
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");
394  }
395  while (OnStack.size() > 1 && &MBB == WebAssembly::getBottom(OnStack.back()))
396  OnStack.pop_back();
397  }
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.");
402 #endif
403 }
404 
405 bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {
406  LLVM_DEBUG(dbgs() << "********** CFG Sorting **********\n"
407  "********** Function: "
408  << MF.getName() << '\n');
409 
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.
415 
416  // Sort the blocks, with contiguous sort regions.
417  sortBlocks(MF, MLI, WEI, MDT);
418 
419  return true;
420 }
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
FunctionPass * createWebAssemblyCFGSort()
void RenumberBlocks(MachineBasicBlock *MBBFrom=nullptr)
RenumberBlocks - This discards all of the MachineBasicBlock numbers and recomputes them...
size_type size() const
Determine the number of elements in the SetVector.
Definition: SetVector.h:77
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
void push_back(const T &Elt)
Definition: SmallVector.h:211
INITIALIZE_PASS(WebAssemblyCFGSort, DEBUG_TYPE, "Reorders blocks in topological order", false, false) FunctionPass *llvm
void moveAfter(MachineBasicBlock *NewBefore)
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:128
This file contains the entry points for global functions defined in the LLVM WebAssembly back-end...
iterator_range< succ_iterator > successors()
AnalysisUsage & addRequired()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
#define DEBUG_TYPE
iterator_range< iterator > terminators()
void pop_back()
Remove the last element of the SetVector.
Definition: SetVector.h:221
block_range blocks()
Returns a range view of the basic blocks in the region.
Definition: RegionInfo.h:624
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, Region *Parent=nullptr)
Definition: RegionInfo.cpp:63
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they&#39;re not in a MachineFuncti...
This file implements WebAssemblyException information analysis.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
Definition: SetVector.h:210
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
This file contains the declaration of the WebAssembly-specific utility functions. ...
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file provides WebAssembly-specific target descriptions.
Represent the analysis usage information of a pass.
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))
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:284
static void sortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI, const WebAssemblyExceptionInfo &WEI, const MachineDominatorTree &MDT)
Sort the blocks, taking special care to make sure that regions are not interrupted by blocks not domi...
iterator_range< pred_iterator > predecessors()
WebAssemblyException * getExceptionFor(const MachineBasicBlock *MBB) const
This file declares the WebAssembly-specific subclass of TargetSubtarget.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
bool dominates(const MachineDomTreeNode *A, const MachineDomTreeNode *B) const
void updateTerminator()
Update the terminator instructions in block to account for changes to the layout. ...
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:301
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
unsigned pred_size() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
A range adaptor for a pair of iterators.
static void maybeUpdateTerminator(MachineBasicBlock *MBB)
Representation of each machine instruction.
Definition: MachineInstr.h:64
bool contains(const BlockT *BB) const
Check if the region contains a BasicBlock.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
bool isEHPad() const
Returns true if the block is a landing pad.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
#define N
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
block_iterator_wrapper< false > block_iterator
Definition: RegionInfo.h:608
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:145
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineBasicBlock * getBottom(const T *Unit)
Return the "bottom" block of an entity, which can be either a MachineLoop or WebAssemblyException.
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
PriorityQueue - This class behaves like std::priority_queue and provides a few additional convenience...
Definition: PriorityQueue.h:27
#define LLVM_DEBUG(X)
Definition: Debug.h:122
RegionT * getRegionFor(BlockT *BB) const
Get the smallest region that contains a BasicBlock.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...