1 //===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//
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 stacking pass.
13 /// This pass reorders the blocks in a function to put them into a reverse
14 /// post-order [0], with special care to keep the order as similar as possible
15 /// to the original order, and to keep loops contiguous even in the case of
18 /// Then, it inserts BLOCK and LOOP markers to mark the start of scopes, since
19 /// scope boundaries serve as the labels for WebAssembly's control transfers.
21 /// This is sufficient to convert arbitrary CFGs into a form that works on
22 /// WebAssembly, provided that all loops are single-entry.
24 /// [0] https://en.wikipedia.org/wiki/Depth-first_search#Vertex_orderings
26 //===----------------------------------------------------------------------===//
28 #include "WebAssembly.h"
29 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
30 #include "WebAssemblySubtarget.h"
31 #include "llvm/ADT/SCCIterator.h"
32 #include "llvm/CodeGen/MachineDominators.h"
33 #include "llvm/CodeGen/MachineFunction.h"
34 #include "llvm/CodeGen/MachineInstrBuilder.h"
35 #include "llvm/CodeGen/MachineLoopInfo.h"
36 #include "llvm/CodeGen/Passes.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/raw_ostream.h"
41 #define DEBUG_TYPE "wasm-cfg-stackify"
44 class WebAssemblyCFGStackify final : public MachineFunctionPass {
45 const char *getPassName() const override {
46 return "WebAssembly CFG Stackify";
49 void getAnalysisUsage(AnalysisUsage &AU) const override {
51 AU.addRequired<MachineDominatorTree>();
52 AU.addPreserved<MachineDominatorTree>();
53 AU.addRequired<MachineLoopInfo>();
54 AU.addPreserved<MachineLoopInfo>();
55 MachineFunctionPass::getAnalysisUsage(AU);
58 bool runOnMachineFunction(MachineFunction &MF) override;
61 static char ID; // Pass identification, replacement for typeid
62 WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
64 } // end anonymous namespace
66 char WebAssemblyCFGStackify::ID = 0;
67 FunctionPass *llvm::createWebAssemblyCFGStackify() {
68 return new WebAssemblyCFGStackify();
71 static void EliminateMultipleEntryLoops(MachineFunction &MF,
72 const MachineLoopInfo &MLI) {
73 SmallPtrSet<MachineBasicBlock *, 8> InSet;
74 for (scc_iterator<MachineFunction *> I = scc_begin(&MF), E = scc_end(&MF);
76 const std::vector<MachineBasicBlock *> &CurrentSCC = *I;
79 if (CurrentSCC.size() == 1)
82 InSet.insert(CurrentSCC.begin(), CurrentSCC.end());
83 MachineBasicBlock *Header = nullptr;
84 for (MachineBasicBlock *MBB : CurrentSCC) {
85 for (MachineBasicBlock *Pred : MBB->predecessors()) {
86 if (InSet.count(Pred))
92 // TODO: Implement multiple-entry loops.
93 report_fatal_error("multiple-entry loops are not supported yet");
96 assert(MLI.isLoopHeader(Header));
103 /// Post-order traversal stack entry.
104 struct POStackEntry {
105 MachineBasicBlock *MBB;
106 SmallVector<MachineBasicBlock *, 0> Succs;
108 POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF,
109 const MachineLoopInfo &MLI);
111 } // end anonymous namespace
113 static bool LoopContains(const MachineLoop *Loop,
114 const MachineBasicBlock *MBB) {
115 return Loop ? Loop->contains(MBB) : true;
118 POStackEntry::POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF,
119 const MachineLoopInfo &MLI)
120 : MBB(MBB), Succs(MBB->successors()) {
121 // RPO is not a unique form, since at every basic block with multiple
122 // successors, the DFS has to pick which order to visit the successors in.
123 // Sort them strategically (see below).
124 MachineLoop *Loop = MLI.getLoopFor(MBB);
125 MachineFunction::iterator Next = next(MachineFunction::iterator(MBB));
126 MachineBasicBlock *LayoutSucc = Next == MF.end() ? nullptr : &*Next;
128 Succs.begin(), Succs.end(),
129 [=, &MLI](const MachineBasicBlock *A, const MachineBasicBlock *B) {
133 // Keep loops contiguous by preferring the block that's in the same
135 bool LoopContainsA = LoopContains(Loop, A);
136 bool LoopContainsB = LoopContains(Loop, B);
137 if (LoopContainsA && !LoopContainsB)
139 if (!LoopContainsA && LoopContainsB)
142 // Minimize perturbation by preferring the block which is the immediate
149 // TODO: More sophisticated orderings may be profitable here.
155 /// Sort the blocks in RPO, taking special care to make sure that loops are
156 /// contiguous even in the case of split backedges.
157 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI) {
158 // Note that we do our own RPO rather than using
159 // "llvm/ADT/PostOrderIterator.h" because we want control over the order that
160 // successors are visited in (see above). Also, we can sort the blocks in the
161 // MachineFunction as we go.
162 SmallPtrSet<MachineBasicBlock *, 16> Visited;
163 SmallVector<POStackEntry, 16> Stack;
165 MachineBasicBlock *EntryBlock = &*MF.begin();
166 Visited.insert(EntryBlock);
167 Stack.push_back(POStackEntry(EntryBlock, MF, MLI));
170 POStackEntry &Entry = Stack.back();
171 SmallVectorImpl<MachineBasicBlock *> &Succs = Entry.Succs;
172 if (!Succs.empty()) {
173 MachineBasicBlock *Succ = Succs.pop_back_val();
174 if (Visited.insert(Succ).second)
175 Stack.push_back(POStackEntry(Succ, MF, MLI));
179 // Put the block in its position in the MachineFunction.
180 MachineBasicBlock &MBB = *Entry.MBB;
181 MBB.moveBefore(&*MF.begin());
183 // Branch instructions may utilize a fallthrough, so update them if a
184 // fallthrough has been added or removed.
185 if (!MBB.empty() && MBB.back().isTerminator() && !MBB.back().isBranch() &&
186 !MBB.back().isBarrier())
188 "Non-branch terminator with fallthrough cannot yet be rewritten");
189 if (MBB.empty() || !MBB.back().isTerminator() || MBB.back().isBranch())
190 MBB.updateTerminator();
197 // Now that we've sorted the blocks in RPO, renumber them.
202 if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) {
203 // Assert that all containing loops are contiguous.
204 for (MachineLoop *L = Loop; L; L = L->getParentLoop()) {
205 if (&MBB == L->getHeader()) {
206 assert(&MBB == L->getTopBlock());
208 assert(&MBB != L->getTopBlock());
210 MLI.getLoopFor(&*prev(MachineFunction::iterator(&MBB)))) &&
211 "Loop isn't contiguous");
215 // Assert that non-loops have no backedge predecessors.
216 for (auto Pred : MBB.predecessors())
217 assert(Pred->getNumber() < MBB.getNumber() &&
218 "CFG still has multiple-entry loops");
223 static unsigned GetLoopDepth(const MachineLoop *Loop) {
224 return Loop ? Loop->getLoopDepth() : 0;
227 /// Insert a BLOCK marker for branches to MBB (if needed).
228 static void PlaceBlockMarkers(MachineBasicBlock &MBB,
229 const WebAssemblyInstrInfo &TII,
230 MachineDominatorTree &MDT,
231 const MachineLoopInfo &MLI) {
232 // Place the BLOCK for forward non-fallthrough branches. Put it at the nearest
233 // common dominator of all preceding predecesors so that we minimize the time
234 // that it's on the stack, which reduces overall stack height.
235 MachineBasicBlock *Header = nullptr;
236 bool IsBranchedTo = false;
237 int MBBNumber = MBB.getNumber();
238 for (MachineBasicBlock *Pred : MBB.predecessors())
239 if (Pred->getNumber() < MBBNumber) {
240 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred;
241 if (!Pred->isLayoutSuccessor(&MBB) ||
242 !(Pred->empty() || !Pred->back().isBarrier()))
250 MachineBasicBlock::iterator InsertPos;
251 MachineLoop *HeaderLoop = MLI.getLoopFor(Header);
252 unsigned MBBLoopDepth = GetLoopDepth(MLI.getLoopFor(&MBB));
253 unsigned HeaderLoopDepth = GetLoopDepth(HeaderLoop);
254 if (HeaderLoopDepth > MBBLoopDepth) {
255 // The nearest common dominating point is more deeply nested. Insert the
256 // BLOCK just above the LOOP.
257 for (unsigned i = 0; i < HeaderLoopDepth - 1 - MBBLoopDepth; ++i)
258 HeaderLoop = HeaderLoop->getParentLoop();
259 Header = HeaderLoop->getHeader();
260 InsertPos = Header->begin();
261 // Don't insert a BLOCK if we can reuse a loop exit label though.
262 if (InsertPos != Header->end() &&
263 InsertPos->getOpcode() == WebAssembly::LOOP &&
264 InsertPos->getOperand(0).getMBB() == &MBB)
267 // Insert the BLOCK as late in the block as we can, but before any existing
269 InsertPos = Header->getFirstTerminator();
270 while (InsertPos != Header->begin() &&
271 std::prev(InsertPos)->getOpcode() == WebAssembly::BLOCK)
275 BuildMI(*Header, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK))
279 /// Insert LOOP and BLOCK markers at appropriate places.
280 static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI,
281 const WebAssemblyInstrInfo &TII,
282 MachineDominatorTree &MDT) {
283 for (auto &MBB : MF) {
284 // Place the LOOP for MBB if MBB is the header of a loop.
285 if (MachineLoop *Loop = MLI.getLoopFor(&MBB))
286 if (Loop->getHeader() == &MBB) {
287 // The operand of a LOOP is the first block after the loop. If the loop
288 // is the bottom of the function, insert a dummy block at the end.
289 MachineBasicBlock *Bottom = Loop->getBottomBlock();
290 auto Iter = next(MachineFunction::iterator(Bottom));
291 if (Iter == MF.end()) {
292 MachineBasicBlock *Label = MF.CreateMachineBasicBlock();
293 // Give it a fake predecessor so that AsmPrinter prints its label.
294 Label->addSuccessor(Label);
296 Iter = next(MachineFunction::iterator(Bottom));
298 BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP))
301 // Emit a special no-op telling the asm printer that we need a label
302 // to close the loop scope, even though the destination is only
303 // reachable by fallthrough.
304 if (!Bottom->back().isBarrier())
305 BuildMI(*Bottom, Bottom->end(), DebugLoc(),
306 TII.get(WebAssembly::LOOP_END));
309 // Place the BLOCK for MBB if MBB is branched to from above.
310 PlaceBlockMarkers(MBB, TII, MDT, MLI);
316 IsOnStack(const SmallVectorImpl<std::pair<MachineBasicBlock *, bool>> &Stack,
317 const MachineBasicBlock *MBB) {
318 for (const auto &Pair : Stack)
319 if (Pair.first == MBB)
325 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
326 DEBUG(dbgs() << "********** CFG Stackifying **********\n"
327 "********** Function: "
328 << MF.getName() << '\n');
330 const auto &MLI = getAnalysis<MachineLoopInfo>();
331 auto &MDT = getAnalysis<MachineDominatorTree>();
332 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
334 // RPO sorting needs all loops to be single-entry.
335 EliminateMultipleEntryLoops(MF, MLI);
337 // Sort the blocks in RPO, with contiguous loops.
340 // Place the BLOCK and LOOP markers to indicate the beginnings of scopes.
341 PlaceMarkers(MF, MLI, TII, MDT);
344 // Verify that block and loop beginnings and endings are in LIFO order, and
345 // that all references to blocks are to blocks on the stack at the point of
347 SmallVector<std::pair<MachineBasicBlock *, bool>, 0> Stack;
348 for (auto &MBB : MF) {
349 while (!Stack.empty() && Stack.back().first == &MBB)
350 if (Stack.back().second) {
351 assert(Stack.size() >= 2);
355 assert(Stack.size() >= 1);
359 switch (MI.getOpcode()) {
360 case WebAssembly::LOOP:
361 Stack.push_back(std::make_pair(&MBB, false));
362 Stack.push_back(std::make_pair(MI.getOperand(0).getMBB(), true));
364 case WebAssembly::BLOCK:
365 Stack.push_back(std::make_pair(MI.getOperand(0).getMBB(), false));
368 for (const MachineOperand &MO : MI.explicit_operands())
370 assert(IsOnStack(Stack, MO.getMBB()));
374 assert(Stack.empty());