1 //===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===// 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 /// \brief This file implements a CFG stacking pass. 12 /// 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 16 /// split backedges. 17 /// 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. 20 /// 21 /// This is sufficient to convert arbitrary CFGs into a form that works on 22 /// WebAssembly, provided that all loops are single-entry. 23 /// 24 /// [0] https://en.wikipedia.org/wiki/Depth-first_search#Vertex_orderings 25 /// 26 //===----------------------------------------------------------------------===// 27 28 #include "WebAssembly.h" 29 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" 30 #include "WebAssemblySubtarget.h" 31 #include "llvm/ADT/SCCIterator.h" 32 #include "llvm/CodeGen/MachineFunction.h" 33 #include "llvm/CodeGen/MachineInstrBuilder.h" 34 #include "llvm/CodeGen/MachineLoopInfo.h" 35 #include "llvm/CodeGen/Passes.h" 36 #include "llvm/Support/Debug.h" 37 #include "llvm/Support/raw_ostream.h" 38 using namespace llvm; 39 40 #define DEBUG_TYPE "wasm-cfg-stackify" 41 42 namespace { 43 class WebAssemblyCFGStackify final : public MachineFunctionPass { 44 const char *getPassName() const override { 45 return "WebAssembly CFG Stackify"; 46 } 47 48 void getAnalysisUsage(AnalysisUsage &AU) const override { 49 AU.setPreservesCFG(); 50 AU.addRequired<MachineLoopInfo>(); 51 AU.addPreserved<MachineLoopInfo>(); 52 MachineFunctionPass::getAnalysisUsage(AU); 53 } 54 55 bool runOnMachineFunction(MachineFunction &MF) override; 56 57 public: 58 static char ID; // Pass identification, replacement for typeid 59 WebAssemblyCFGStackify() : MachineFunctionPass(ID) {} 60 }; 61 } // end anonymous namespace 62 63 char WebAssemblyCFGStackify::ID = 0; 64 FunctionPass *llvm::createWebAssemblyCFGStackify() { 65 return new WebAssemblyCFGStackify(); 66 } 67 68 static void EliminateMultipleEntryLoops(MachineFunction &MF, 69 const MachineLoopInfo &MLI) { 70 SmallPtrSet<MachineBasicBlock *, 8> InSet; 71 for (scc_iterator<MachineFunction *> I = scc_begin(&MF), E = scc_end(&MF); 72 I != E; ++I) { 73 const std::vector<MachineBasicBlock *> &CurrentSCC = *I; 74 75 // Skip trivial SCCs. 76 if (CurrentSCC.size() == 1) 77 continue; 78 79 InSet.insert(CurrentSCC.begin(), CurrentSCC.end()); 80 MachineBasicBlock *Header = nullptr; 81 for (MachineBasicBlock *MBB : CurrentSCC) { 82 for (MachineBasicBlock *Pred : MBB->predecessors()) { 83 if (InSet.count(Pred)) 84 continue; 85 if (!Header) { 86 Header = MBB; 87 break; 88 } 89 // TODO: Implement multiple-entry loops. 90 report_fatal_error("multiple-entry loops are not supported yet"); 91 } 92 } 93 assert(MLI.isLoopHeader(Header)); 94 95 InSet.clear(); 96 } 97 } 98 99 namespace { 100 /// Post-order traversal stack entry. 101 struct POStackEntry { 102 MachineBasicBlock *MBB; 103 SmallVector<MachineBasicBlock *, 0> Succs; 104 105 POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF, 106 const MachineLoopInfo &MLI); 107 }; 108 } // end anonymous namespace 109 110 POStackEntry::POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF, 111 const MachineLoopInfo &MLI) 112 : MBB(MBB), Succs(MBB->successors()) { 113 // RPO is not a unique form, since at every basic block with multiple 114 // successors, the DFS has to pick which order to visit the successors in. 115 // Sort them strategically (see below). 116 MachineLoop *Loop = MLI.getLoopFor(MBB); 117 MachineFunction::iterator Next = next(MachineFunction::iterator(MBB)); 118 MachineBasicBlock *LayoutSucc = Next == MF.end() ? nullptr : &*Next; 119 std::stable_sort( 120 Succs.begin(), Succs.end(), 121 [=, &MLI](const MachineBasicBlock *A, const MachineBasicBlock *B) { 122 if (A == B) 123 return false; 124 125 // Keep loops contiguous by preferring the block that's in the same 126 // loop. 127 MachineLoop *LoopA = MLI.getLoopFor(A); 128 MachineLoop *LoopB = MLI.getLoopFor(B); 129 if (LoopA == Loop && LoopB != Loop) 130 return true; 131 if (LoopA != Loop && LoopB == Loop) 132 return false; 133 134 // Minimize perturbation by preferring the block which is the immediate 135 // layout successor. 136 if (A == LayoutSucc) 137 return true; 138 if (B == LayoutSucc) 139 return false; 140 141 // TODO: More sophisticated orderings may be profitable here. 142 143 return false; 144 }); 145 } 146 147 /// Sort the blocks in RPO, taking special care to make sure that loops are 148 /// contiguous even in the case of split backedges. 149 static void SortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI) { 150 // Note that we do our own RPO rather than using 151 // "llvm/ADT/PostOrderIterator.h" because we want control over the order that 152 // successors are visited in (see above). Also, we can sort the blocks in the 153 // MachineFunction as we go. 154 SmallPtrSet<MachineBasicBlock *, 16> Visited; 155 SmallVector<POStackEntry, 16> Stack; 156 157 MachineBasicBlock *Entry = MF.begin(); 158 Visited.insert(Entry); 159 Stack.push_back(POStackEntry(Entry, MF, MLI)); 160 161 for (;;) { 162 POStackEntry &Entry = Stack.back(); 163 SmallVectorImpl<MachineBasicBlock *> &Succs = Entry.Succs; 164 if (!Succs.empty()) { 165 MachineBasicBlock *Succ = Succs.pop_back_val(); 166 if (Visited.insert(Succ).second) 167 Stack.push_back(POStackEntry(Succ, MF, MLI)); 168 continue; 169 } 170 171 // Put the block in its position in the MachineFunction. 172 MachineBasicBlock &MBB = *Entry.MBB; 173 MBB.moveBefore(MF.begin()); 174 175 // Branch instructions may utilize a fallthrough, so update them if a 176 // fallthrough has been added or removed. 177 if (!MBB.empty() && MBB.back().isTerminator() && !MBB.back().isBranch() && 178 !MBB.back().isBarrier()) 179 report_fatal_error( 180 "Non-branch terminator with fallthrough cannot yet be rewritten"); 181 if (MBB.empty() || !MBB.back().isTerminator() || MBB.back().isBranch()) 182 MBB.updateTerminator(); 183 184 Stack.pop_back(); 185 if (Stack.empty()) 186 break; 187 } 188 189 // Now that we've sorted the blocks in RPO, renumber them. 190 MF.RenumberBlocks(); 191 192 #ifndef NDEBUG 193 for (auto &MBB : MF) 194 if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) { 195 // Assert that loops are contiguous. 196 assert(Loop->getHeader() == Loop->getTopBlock()); 197 assert(Loop->getHeader() == &MBB || 198 MLI.getLoopFor(prev(MachineFunction::iterator(&MBB))) == Loop); 199 } else { 200 // Assert that non-loops have no backedge predecessors. 201 for (auto Pred : MBB.predecessors()) 202 assert(Pred->getNumber() < MBB.getNumber() && 203 "CFG still has multiple-entry loops"); 204 } 205 #endif 206 } 207 208 /// Insert BLOCK markers at appropriate places. 209 static void PlaceBlockMarkers(MachineBasicBlock &MBB, MachineBasicBlock &Succ, 210 MachineFunction &MF, const MachineLoopInfo &MLI, 211 const WebAssemblyInstrInfo &TII) { 212 // Backward branches are loop backedges, and we place the LOOP markers 213 // separately. So only consider forward branches here. 214 if (Succ.getNumber() <= MBB.getNumber()) 215 return; 216 217 // Place the BLOCK for a forward branch. For simplicity, we just insert 218 // blocks immediately inside loop boundaries. 219 MachineLoop *Loop = MLI.getLoopFor(&Succ); 220 MachineBasicBlock &Header = *(Loop ? Loop->getHeader() : &MF.front()); 221 MachineBasicBlock::iterator InsertPos = Header.begin(), End = Header.end(); 222 if (InsertPos != End) { 223 if (InsertPos->getOpcode() == WebAssembly::LOOP) 224 ++InsertPos; 225 int SuccNumber = Succ.getNumber(); 226 // Position the BLOCK in nesting order. 227 for (; InsertPos != End && InsertPos->getOpcode() == WebAssembly::BLOCK; 228 ++InsertPos) { 229 int N = InsertPos->getOperand(0).getMBB()->getNumber(); 230 if (N < SuccNumber) 231 break; 232 // If there's already a BLOCK for Succ, we don't need another. 233 if (N == SuccNumber) 234 return; 235 } 236 } 237 238 BuildMI(Header, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK)) 239 .addMBB(&Succ); 240 } 241 242 /// Insert LOOP and BLOCK markers at appropriate places. 243 static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI, 244 const WebAssemblyInstrInfo &TII) { 245 for (auto &MBB : MF) { 246 // Place the LOOP for loops. 247 if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) 248 if (Loop->getHeader() == &MBB) 249 BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP)) 250 .addMBB(Loop->getBottomBlock()); 251 252 // Check for forward branches and switches that need BLOCKS placed. 253 for (auto &Term : MBB.terminators()) 254 for (auto &MO : Term.operands()) 255 if (MO.isMBB()) 256 PlaceBlockMarkers(MBB, *MO.getMBB(), MF, MLI, TII); 257 } 258 } 259 260 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 261 DEBUG(dbgs() << "********** CFG Stackifying **********\n" 262 "********** Function: " 263 << MF.getName() << '\n'); 264 265 const auto &MLI = getAnalysis<MachineLoopInfo>(); 266 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 267 268 // RPO sorting needs all loops to be single-entry. 269 EliminateMultipleEntryLoops(MF, MLI); 270 271 // Sort the blocks in RPO, with contiguous loops. 272 SortBlocks(MF, MLI); 273 274 // Place the BLOCK and LOOP markers to indicate the beginnings of scopes. 275 PlaceMarkers(MF, MLI, TII); 276 277 return true; 278 } 279