1 //===-- WebAssemblyCFGSort.cpp - CFG Sorting ------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// \brief This file implements a CFG sorting pass.
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.
18 ////===----------------------------------------------------------------------===//
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"
35 #define DEBUG_TYPE "wasm-cfg-sort"
38 class WebAssemblyCFGSort final : public MachineFunctionPass {
39 StringRef getPassName() const override { return "WebAssembly CFG Sort"; }
41 void getAnalysisUsage(AnalysisUsage &AU) const override {
43 AU.addRequired<MachineDominatorTree>();
44 AU.addPreserved<MachineDominatorTree>();
45 AU.addRequired<MachineLoopInfo>();
46 AU.addPreserved<MachineLoopInfo>();
47 MachineFunctionPass::getAnalysisUsage(AU);
50 bool runOnMachineFunction(MachineFunction &MF) override;
53 static char ID; // Pass identification, replacement for typeid
54 WebAssemblyCFGSort() : MachineFunctionPass(ID) {}
56 } // end anonymous namespace
58 char WebAssemblyCFGSort::ID = 0;
59 FunctionPass *llvm::createWebAssemblyCFGSort() {
60 return new WebAssemblyCFGSort();
63 static void MaybeUpdateTerminator(MachineBasicBlock *MBB) {
65 bool AnyBarrier = false;
67 bool AllAnalyzable = true;
68 for (const MachineInstr &Term : MBB->terminators()) {
70 AnyBarrier |= Term.isBarrier();
72 AllAnalyzable &= Term.isBranch() && !Term.isIndirectBranch();
74 assert((AnyBarrier || AllAnalyzable) &&
75 "AnalyzeBranch needs to analyze any block with a fallthrough");
77 MBB->updateTerminator();
81 /// Sort blocks by their number.
82 struct CompareBlockNumbers {
83 bool operator()(const MachineBasicBlock *A,
84 const MachineBasicBlock *B) const {
85 return A->getNumber() > B->getNumber();
88 /// Sort blocks by their number in the opposite order..
89 struct CompareBlockNumbersBackwards {
90 bool operator()(const MachineBasicBlock *A,
91 const MachineBasicBlock *B) const {
92 return A->getNumber() < B->getNumber();
95 /// Bookkeeping for a loop to help ensure that we don't mix blocks not dominated
96 /// by the loop header among the loop's blocks.
98 const MachineLoop *Loop;
99 unsigned NumBlocksLeft;
101 /// List of blocks not dominated by Loop's header that are deferred until
102 /// after all of Loop's blocks have been seen.
103 std::vector<MachineBasicBlock *> Deferred;
105 explicit Entry(const MachineLoop *L)
106 : Loop(L), NumBlocksLeft(L->getNumBlocks()) {}
108 } // end anonymous namespace
110 /// Sort the blocks, taking special care to make sure that loops are not
111 /// interrupted by blocks not dominated by their header.
112 /// TODO: There are many opportunities for improving the heuristics here.
114 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
115 const MachineDominatorTree &MDT) {
116 // Prepare for a topological sort: Record the number of predecessors each
117 // block has, ignoring loop backedges.
119 SmallVector<unsigned, 16> NumPredsLeft(MF.getNumBlockIDs(), 0);
120 for (MachineBasicBlock &MBB : MF) {
121 unsigned N = MBB.pred_size();
122 if (MachineLoop *L = MLI.getLoopFor(&MBB))
123 if (L->getHeader() == &MBB)
124 for (const MachineBasicBlock *Pred : MBB.predecessors())
125 if (L->contains(Pred))
127 NumPredsLeft[MBB.getNumber()] = N;
130 // Topological sort the CFG, with additional constraints:
131 // - Between a loop header and the last block in the loop, there can be
132 // no blocks not dominated by the loop header.
133 // - It's desirable to preserve the original block order when possible.
134 // We use two ready lists; Preferred and Ready. Preferred has recently
135 // processed successors, to help preserve block sequences from the original
136 // order. Ready has the remaining ready blocks.
137 PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
140 PriorityQueue<MachineBasicBlock *, std::vector<MachineBasicBlock *>,
141 CompareBlockNumbersBackwards>
143 SmallVector<Entry, 4> Loops;
144 for (MachineBasicBlock *MBB = &MF.front();;) {
145 const MachineLoop *L = MLI.getLoopFor(MBB);
147 // If MBB is a loop header, add it to the active loop list. We can't put
148 // any blocks that it doesn't dominate until we see the end of the loop.
149 if (L->getHeader() == MBB)
150 Loops.push_back(Entry(L));
151 // For each active loop the block is in, decrement the count. If MBB is
152 // the last block in an active loop, take it off the list and pick up any
153 // blocks deferred because the header didn't dominate them.
154 for (Entry &E : Loops)
155 if (E.Loop->contains(MBB) && --E.NumBlocksLeft == 0)
156 for (auto DeferredBlock : E.Deferred)
157 Ready.push(DeferredBlock);
158 while (!Loops.empty() && Loops.back().NumBlocksLeft == 0)
161 // The main topological sort logic.
162 for (MachineBasicBlock *Succ : MBB->successors()) {
164 if (MachineLoop *SuccL = MLI.getLoopFor(Succ))
165 if (SuccL->getHeader() == Succ && SuccL->contains(MBB))
167 // Decrement the predecessor count. If it's now zero, it's ready.
168 if (--NumPredsLeft[Succ->getNumber()] == 0)
169 Preferred.push(Succ);
171 // Determine the block to follow MBB. First try to find a preferred block,
172 // to preserve the original block order when possible.
173 MachineBasicBlock *Next = nullptr;
174 while (!Preferred.empty()) {
175 Next = Preferred.top();
177 // If X isn't dominated by the top active loop header, defer it until that
179 if (!Loops.empty() &&
180 !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
181 Loops.back().Deferred.push_back(Next);
185 // If Next was originally ordered before MBB, and it isn't because it was
186 // loop-rotated above the header, it's not preferred.
187 if (Next->getNumber() < MBB->getNumber() &&
188 (!L || !L->contains(Next) ||
189 L->getHeader()->getNumber() < Next->getNumber())) {
196 // If we didn't find a suitable block in the Preferred list, check the
197 // general Ready list.
199 // If there are no more blocks to process, we're done.
201 MaybeUpdateTerminator(MBB);
207 // If Next isn't dominated by the top active loop header, defer it until
208 // that loop is done.
209 if (!Loops.empty() &&
210 !MDT.dominates(Loops.back().Loop->getHeader(), Next)) {
211 Loops.back().Deferred.push_back(Next);
217 // Move the next block into place and iterate.
218 Next->moveAfter(MBB);
219 MaybeUpdateTerminator(MBB);
222 assert(Loops.empty() && "Active loop list not finished");
226 SmallSetVector<MachineLoop *, 8> OnStack;
228 // Insert a sentinel representing the degenerate loop that starts at the
229 // function entry block and includes the entire function as a "loop" that
231 OnStack.insert(nullptr);
233 for (auto &MBB : MF) {
234 assert(MBB.getNumber() >= 0 && "Renumbered blocks should be non-negative.");
236 MachineLoop *Loop = MLI.getLoopFor(&MBB);
237 if (Loop && &MBB == Loop->getHeader()) {
238 // Loop header. The loop predecessor should be sorted above, and the other
239 // predecessors should be backedges below.
240 for (auto Pred : MBB.predecessors())
242 (Pred->getNumber() < MBB.getNumber() || Loop->contains(Pred)) &&
243 "Loop header predecessors must be loop predecessors or backedges");
244 assert(OnStack.insert(Loop) && "Loops should be declared at most once.");
246 // Not a loop header. All predecessors should be sorted above.
247 for (auto Pred : MBB.predecessors())
248 assert(Pred->getNumber() < MBB.getNumber() &&
249 "Non-loop-header predecessors should be topologically sorted");
250 assert(OnStack.count(MLI.getLoopFor(&MBB)) &&
251 "Blocks must be nested in their loops");
253 while (OnStack.size() > 1 && &MBB == LoopBottom(OnStack.back()))
256 assert(OnStack.pop_back_val() == nullptr &&
257 "The function entry block shouldn't actually be a loop header");
258 assert(OnStack.empty() &&
259 "Control flow stack pushes and pops should be balanced.");
263 bool WebAssemblyCFGSort::runOnMachineFunction(MachineFunction &MF) {
264 DEBUG(dbgs() << "********** CFG Sorting **********\n"
265 "********** Function: "
266 << MF.getName() << '\n');
268 const auto &MLI = getAnalysis<MachineLoopInfo>();
269 auto &MDT = getAnalysis<MachineDominatorTree>();
270 // Liveness is not tracked for VALUE_STACK physreg.
271 MF.getRegInfo().invalidateLiveness();
273 // Sort the blocks, with contiguous loops.
274 SortBlocks(MF, MLI, MDT);