LLVM  8.0.1
WebAssemblyCFGSort.cpp
Go to the documentation of this file.
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 
21 #include "WebAssembly.h"
23 #include "WebAssemblySubtarget.h"
24 #include "WebAssemblyUtilities.h"
25 #include "llvm/ADT/PriorityQueue.h"
26 #include "llvm/ADT/SetVector.h"
31 #include "llvm/CodeGen/Passes.h"
32 #include "llvm/Support/Debug.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;
48  virtual iterator_range<block_iterator> blocks() const = 0;
49  virtual bool isLoop() const = 0;
50 };
51 
52 template <typename T> class ConcreteRegion : public Region {
53  const T *Region;
54 
55 public:
56  ConcreteRegion(const T *Region) : Region(Region) {}
57  MachineBasicBlock *getHeader() const override { return Region->getHeader(); }
58  bool contains(const MachineBasicBlock *MBB) const override {
59  return Region->contains(MBB);
60  }
61  unsigned getNumBlocks() const override { return Region->getNumBlocks(); }
62  iterator_range<block_iterator> blocks() const override {
63  return Region->blocks();
64  }
65  bool isLoop() const override { return false; }
66 };
67 
68 template <> bool ConcreteRegion<MachineLoop>::isLoop() const { return true; }
69 
70 // This class has information of nested Regions; this is analogous to what
71 // LoopInfo is for loops.
72 class RegionInfo {
73  const MachineLoopInfo &MLI;
74  const WebAssemblyExceptionInfo &WEI;
75  std::vector<const Region *> Regions;
78 
79 public:
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  return LoopMap[ML].get();
93  LoopMap[ML] = llvm::make_unique<ConcreteRegion<MachineLoop>>(ML);
94  return LoopMap[ML].get();
95  } else {
96  // If the smallest region containing MBB is an exception
97  if (ExceptionMap.count(WE))
98  return ExceptionMap[WE].get();
99  ExceptionMap[WE] =
100  llvm::make_unique<ConcreteRegion<WebAssemblyException>>(WE);
101  return ExceptionMap[WE].get();
102  }
103  }
104 };
105 
106 class WebAssemblyCFGSort final : public MachineFunctionPass {
107  StringRef getPassName() const override { return "WebAssembly CFG Sort"; }
108 
109  void getAnalysisUsage(AnalysisUsage &AU) const override {
110  AU.setPreservesCFG();
118  }
119 
120  bool runOnMachineFunction(MachineFunction &MF) override;
121 
122 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 INITIALIZE_PASS(WebAssemblyCFGSort, DEBUG_TYPE,
130  "Reorders blocks in topological order", false, false)
131 
133  return new WebAssemblyCFGSort();
134 }
135 
137 #ifndef NDEBUG
138  bool AnyBarrier = false;
139 #endif
140  bool AllAnalyzable = true;
141  for (const MachineInstr &Term : MBB->terminators()) {
142 #ifndef NDEBUG
143  AnyBarrier |= Term.isBarrier();
144 #endif
145  AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
146  }
147  assert((AnyBarrier || AllAnalyzable) &&
148  "AnalyzeBranch needs to analyze any block with a fallthrough");
149  if (AllAnalyzable)
150  MBB->updateTerminator();
151 }
152 
153 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 // unwind to, as in the example below:
158 //
159 // bb0:
160 // call @foo // If this throws, unwind to bb2
161 // bb1:
162 // call @bar // If this throws, unwind to bb3
163 // 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  bool operator()(const MachineBasicBlock *A,
202  const MachineBasicBlock *B) const {
203  // We give a higher priority to an EH pad
204  if (A->isEHPad() && !B->isEHPad())
205  return false;
206  if (!A->isEHPad() && B->isEHPad())
207  return true;
208 
209  return A->getNumber() < B->getNumber();
210  }
211 };
212 /// Bookkeeping for a region to help ensure that we don't mix blocks not
213 /// dominated by the its header among its blocks.
214 struct Entry {
215  const Region *TheRegion;
216  unsigned NumBlocksLeft;
217 
218  /// List of blocks not dominated by Loop's header that are deferred until
219  /// after all of Loop's blocks have been seen.
220  std::vector<MachineBasicBlock *> Deferred;
221 
222  explicit Entry(const class Region *R)
223  : TheRegion(R), NumBlocksLeft(R->getNumBlocks()) {}
224 };
225 } // end anonymous namespace
226 
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  // 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  if (L->contains(Pred))
244  --N;
245  NumPredsLeft[MBB.getNumber()] = N;
246  }
247 
248  // Topological sort the CFG, with additional constraints:
249  // - Between a region header and the last block in the region, there can be
250  // no blocks not dominated by its header.
251  // - It's desirable to preserve the original block order when possible.
252  // We use two ready lists; Preferred and Ready. Preferred has recently
253  // processed successors, to help preserve block sequences from the original
254  // order. Ready has the remaining ready blocks. EH blocks are picked first
255  // from both queues.
257  CompareBlockNumbers>
258  Preferred;
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  // region.
271  if (R->getHeader() == MBB)
272  Entries.push_back(Entry(R));
273  // 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  // any blocks deferred because the header didn't dominate them.
276  for (Entry &E : Entries)
277  if (E.TheRegion->contains(MBB) && --E.NumBlocksLeft == 0)
278  for (auto DeferredBlock : E.Deferred)
279  Ready.push(DeferredBlock);
280  while (!Entries.empty() && Entries.back().NumBlocksLeft == 0)
281  Entries.pop_back();
282  }
283  // The main topological sort logic.
284  for (MachineBasicBlock *Succ : MBB->successors()) {
285  // Ignore backedges.
286  if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
287  if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
288  continue;
289  // Decrement the predecessor count. If it's now zero, it's ready.
290  if (--NumPredsLeft[Succ->getNumber()] == 0)
291  Preferred.push(Succ);
292  }
293  // 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  while (!Preferred.empty()) {
297  Next = Preferred.top();
298  Preferred.pop();
299  // If X isn't dominated by the top active region header, defer it until
300  // that region is done.
301  if (!Entries.empty() &&
302  !MDT.dominates(Entries.back().TheRegion->getHeader(), Next)) {
303  Entries.back().Deferred.push_back(Next);
304  Next = nullptr;
305  continue;
306  }
307  // If Next was originally ordered before MBB, and it isn't because it was
308  // loop-rotated above the header, it's not preferred.
309  if (Next->getNumber() < MBB->getNumber() &&
310  (!R || !R->contains(Next) ||
311  R->getHeader()->getNumber() < Next->getNumber())) {
312  Ready.push(Next);
313  Next = nullptr;
314  continue;
315  }
316  break;
317  }
318  // If we didn't find a suitable block in the Preferred list, check the
319  // general Ready list.
320  if (!Next) {
321  // If there are no more blocks to process, we're done.
322  if (Ready.empty()) {
324  break;
325  }
326  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  !MDT.dominates(Entries.back().TheRegion->getHeader(), Next)) {
333  Entries.back().Deferred.push_back(Next);
334  continue;
335  }
336  break;
337  }
338  }
339  // Move the next block into place and iterate.
340  Next->moveAfter(MBB);
342  MBB = Next;
343  }
344  assert(Entries.empty() && "Active sort region list not finished");
345  MF.RenumberBlocks();
346 
347 #ifndef NDEBUG
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  // executes once.
353  OnStack.insert(nullptr);
354 
355  for (auto &MBB : MF) {
356  assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
357  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.
405 
406  // Sort the blocks, with contiguous sort regions.
407  SortBlocks(MF, MLI, WEI, MDT);
408 
409  return true;
410 }
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:24
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:78
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID&#39;s allocated.
void push_back(const T &Elt)
Definition: SmallVector.h:218
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:129
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
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< iterator > terminators()
void pop_back()
Remove the last element of the SetVector.
Definition: SetVector.h:222
block_range blocks()
Returns a range view of the basic blocks in the region.
Definition: RegionInfo.h:625
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:142
Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo *RI, DominatorTree *DT, Region *Parent=nullptr)
Definition: RegionInfo.cpp:64
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:211
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
This file contains the declaration of the WebAssembly-specific utility functions. ...
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.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
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:298
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:286
void invalidateLiveness()
invalidateLiveness - Indicates that register liveness is no longer being tracked accurately.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
A range adaptor for a pair of iterators.
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:56
#define N
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:73
block_iterator_wrapper< false > block_iterator
Definition: RegionInfo.h:609
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:171
static void MaybeUpdateTerminator(MachineBasicBlock *MBB)
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:49
PriorityQueue - This class behaves like std::priority_queue and provides a few additional convenience...
Definition: PriorityQueue.h:28
#define LLVM_DEBUG(X)
Definition: Debug.h:123
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...