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 being interrupted
15 /// by a block not dominated by the loop header, with special care to keep the
16 /// order as similar as possible to the original order.
17 ///
18 ////===----------------------------------------------------------------------===//
19 
20 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
21 #include "WebAssembly.h"
22 #include "WebAssemblySubtarget.h"
23 #include "WebAssemblyUtilities.h"
24 #include "llvm/ADT/PriorityQueue.h"
25 #include "llvm/ADT/SetVector.h"
26 #include "llvm/CodeGen/MachineDominators.h"
27 #include "llvm/CodeGen/MachineFunction.h"
28 #include "llvm/CodeGen/MachineLoopInfo.h"
29 #include "llvm/CodeGen/MachineRegisterInfo.h"
30 #include "llvm/CodeGen/Passes.h"
31 #include "llvm/Support/Debug.h"
32 #include "llvm/Support/raw_ostream.h"
33 using namespace llvm;
34 
35 #define DEBUG_TYPE "wasm-cfg-sort"
36 
37 namespace {
38 class WebAssemblyCFGSort final : public MachineFunctionPass {
39   StringRef getPassName() const override { return "WebAssembly CFG Sort"; }
40 
41   void getAnalysisUsage(AnalysisUsage &AU) const override {
42     AU.setPreservesCFG();
43     AU.addRequired<MachineDominatorTree>();
44     AU.addPreserved<MachineDominatorTree>();
45     AU.addRequired<MachineLoopInfo>();
46     AU.addPreserved<MachineLoopInfo>();
47     MachineFunctionPass::getAnalysisUsage(AU);
48   }
49 
50   bool runOnMachineFunction(MachineFunction &MF) override;
51 
52 public:
53   static char ID; // Pass identification, replacement for typeid
54   WebAssemblyCFGSort() : MachineFunctionPass(ID) {}
55 };
56 } // end anonymous namespace
57 
58 char WebAssemblyCFGSort::ID = 0;
59 INITIALIZE_PASS(WebAssemblyCFGSort, DEBUG_TYPE,
60                 "Reorders blocks in topological order", false, false)
61 
62 FunctionPass *llvm::createWebAssemblyCFGSort() {
63   return new WebAssemblyCFGSort();
64 }
65 
66 static void MaybeUpdateTerminator(MachineBasicBlock *MBB) {
67 #ifndef NDEBUG
68   bool AnyBarrier = false;
69 #endif
70   bool AllAnalyzable = true;
71   for (const MachineInstr &Term : MBB->terminators()) {
72 #ifndef NDEBUG
73     AnyBarrier |= Term.isBarrier();
74 #endif
75     AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
76   }
77   assert((AnyBarrier || AllAnalyzable) &&
78          "AnalyzeBranch needs to analyze any block with a fallthrough");
79   if (AllAnalyzable)
80     MBB->updateTerminator();
81 }
82 
83 namespace {
84 /// Sort blocks by their number.
85 struct CompareBlockNumbers {
86   bool operator()(const MachineBasicBlock *A,
87                   const MachineBasicBlock *B) const {
88     return A->getNumber() > B->getNumber();
89   }
90 };
91 /// Sort blocks by their number in the opposite order..
92 struct CompareBlockNumbersBackwards {
93   bool operator()(const MachineBasicBlock *A,
94                   const MachineBasicBlock *B) const {
95     return A->getNumber() < B->getNumber();
96   }
97 };
98 /// Bookkeeping for a loop to help ensure that we don't mix blocks not dominated
99 /// by the loop header among the loop's blocks.
100 struct Entry {
101   const MachineLoop *Loop;
102   unsigned NumBlocksLeft;
103 
104   /// List of blocks not dominated by Loop's header that are deferred until
105   /// after all of Loop's blocks have been seen.
106   std::vector<MachineBasicBlock *> Deferred;
107 
108   explicit Entry(const MachineLoop *L)
109       : Loop(L), NumBlocksLeft(L->getNumBlocks()) {}
110 };
111 } // end anonymous namespace
112 
113 /// Sort the blocks, taking special care to make sure that loops are not
114 /// interrupted by blocks not dominated by their header.
115 /// TODO: There are many opportunities for improving the heuristics here.
116 /// Explore them.
117 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
118                        const MachineDominatorTree &MDT) {
119   // Prepare for a topological sort: Record the number of predecessors each
120   // block has, ignoring loop backedges.
121   MF.RenumberBlocks();
122   SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0);
123   for (MachineBasicBlock &MBB : MF) {
124     unsigned N = MBB.pred_size();
125     if (MachineLoop *L = MLI.getLoopFor(&MBB))
126       if (L->getHeader() == &MBB)
127         for (const MachineBasicBlock *Pred : MBB.predecessors())
128           if (L->contains(Pred))
129             --N;
130     NumPredsLeft[MBB.getNumber()] = N;
131   }
132 
133   // Topological sort the CFG, with additional constraints:
134   //  - Between a loop header and the last block in the loop, there can be
135   //    no blocks not dominated by the loop header.
136   //  - It's desirable to preserve the original block order when possible.
137   // We use two ready lists; Preferred and Ready. Preferred has recently
138   // processed successors, to help preserve block sequences from the original
139   // order. Ready has the remaining ready blocks.
140   PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
141                 CompareBlockNumbers>
142       Preferred;
143   PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
144                 CompareBlockNumbersBackwards>
145       Ready;
146   SmallVector<Entry, 4> Loops;
147   for (MachineBasicBlock *MBB = &MF.front();;) {
148     const MachineLoop *L = MLI.getLoopFor(MBB);
149     if (L) {
150       // If MBB is a loop header, add it to the active loop list. We can't put
151       // any blocks that it doesn't dominate until we see the end of the loop.
152       if (L->getHeader() == MBB)
153         Loops.push_back(Entry(L));
154       // For each active loop the block is in, decrement the count. If MBB is
155       // the last block in an active loop, take it off the list and pick up any
156       // blocks deferred because the header didn't dominate them.
157       for (Entry &E : Loops)
158         if (E.Loop->contains(MBB) && --E.NumBlocksLeft == 0)
159           for (auto DeferredBlock : E.Deferred)
160             Ready.push(DeferredBlock);
161       while (!Loops.empty() && Loops.back().NumBlocksLeft == 0)
162         Loops.pop_back();
163     }
164     // The main topological sort logic.
165     for (MachineBasicBlock *Succ : MBB->successors()) {
166       // Ignore backedges.
167       if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
168         if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
169           continue;
170       // Decrement the predecessor count. If it's now zero, it's ready.
171       if (--NumPredsLeft[Succ->getNumber()] == 0)
172         Preferred.push(Succ);
173     }
174     // Determine the block to follow MBB. First try to find a preferred block,
175     // to preserve the original block order when possible.
176     MachineBasicBlock *Next = nullptr;
177     while (!Preferred.empty()) {
178       Next = Preferred.top();
179       Preferred.pop();
180       // If X isn't dominated by the top active loop header, defer it until that
181       // loop is done.
182       if (!Loops.empty() &&
183           !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
184         Loops.back().Deferred.push_back(Next);
185         Next = nullptr;
186         continue;
187       }
188       // If Next was originally ordered before MBB, and it isn't because it was
189       // loop-rotated above the header, it's not preferred.
190       if (Next->getNumber() < MBB->getNumber() &&
191           (!L || !L->contains(Next) ||
192            L->getHeader()->getNumber() < Next->getNumber())) {
193         Ready.push(Next);
194         Next = nullptr;
195         continue;
196       }
197       break;
198     }
199     // If we didn't find a suitable block in the Preferred list, check the
200     // general Ready list.
201     if (!Next) {
202       // If there are no more blocks to process, we're done.
203       if (Ready.empty()) {
204         MaybeUpdateTerminator(MBB);
205         break;
206       }
207       for (;;) {
208         Next = Ready.top();
209         Ready.pop();
210         // If Next isn't dominated by the top active loop header, defer it until
211         // that loop is done.
212         if (!Loops.empty() &&
213             !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
214           Loops.back().Deferred.push_back(Next);
215           continue;
216         }
217         break;
218       }
219     }
220     // Move the next block into place and iterate.
221     Next->moveAfter(MBB);
222     MaybeUpdateTerminator(MBB);
223     MBB = Next;
224   }
225   assert(Loops.empty() && "Active loop list not finished");
226   MF.RenumberBlocks();
227 
228 #ifndef NDEBUG
229   SmallSetVector<MachineLoop *, 8> OnStack;
230 
231   // Insert a sentinel representing the degenerate loop that starts at the
232   // function entry block and includes the entire function as a "loop" that
233   // executes once.
234   OnStack.insert(nullptr);
235 
236   for (auto &MBB : MF) {
237     assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
238 
239     MachineLoop *Loop = MLI.getLoopFor(&MBB);
240     if (Loop && &MBB == Loop->getHeader()) {
241       // Loop header. The loop predecessor should be sorted above, and the other
242       // predecessors should be backedges below.
243       for (auto Pred : MBB.predecessors())
244         assert(
245             (Pred->getNumber() < MBB.getNumber() || Loop->contains(Pred)) &&
246             "Loop header predecessors must be loop predecessors or backedges");
247       assert(OnStack.insert(Loop) && "Loops should be declared at most once.");
248     } else {
249       // Not a loop header. All predecessors should be sorted above.
250       for (auto Pred : MBB.predecessors())
251         assert(Pred->getNumber() < MBB.getNumber() &&
252                "Non-loop-header predecessors should be topologically sorted");
253       assert(OnStack.count(MLI.getLoopFor(&MBB)) &&
254              "Blocks must be nested in their loops");
255     }
256     while (OnStack.size() > 1 && &MBB == LoopBottom(OnStack.back()))
257       OnStack.pop_back();
258   }
259   assert(OnStack.pop_back_val() == nullptr &&
260          "The function entry block shouldn't actually be a loop header");
261   assert(OnStack.empty() &&
262          "Control flow stack pushes and pops should be balanced.");
263 #endif
264 }
265 
266 bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {
267   LLVM_DEBUG(dbgs() << "********** CFG Sorting **********\n"
268                        "********** Function: "
269                     << MF.getName() << '\n');
270 
271   const auto &MLI = getAnalysis<MachineLoopInfo>();
272   auto &MDT = getAnalysis<MachineDominatorTree>();
273   // Liveness is not tracked for VALUE_STACK physreg.
274   MF.getRegInfo().invalidateLiveness();
275 
276   // Sort the blocks, with contiguous loops.
277   SortBlocks(MF, MLI, MDT);
278 
279   return true;
280 }
281