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