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 Loop->contains( 199 MLI.getLoopFor(prev(MachineFunction::iterator(&MBB))))) && 200 "Loop isn't contiguous"); 201 } else { 202 // Assert that non-loops have no backedge predecessors. 203 for (auto Pred : MBB.predecessors()) 204 assert(Pred->getNumber() < MBB.getNumber() && 205 "CFG still has multiple-entry loops"); 206 } 207 #endif 208 } 209 210 /// Insert BLOCK markers at appropriate places. 211 static void PlaceBlockMarkers(MachineBasicBlock &MBB, MachineBasicBlock &Succ, 212 MachineFunction &MF, const MachineLoopInfo &MLI, 213 const WebAssemblyInstrInfo &TII) { 214 // Backward branches are loop backedges, and we place the LOOP markers 215 // separately. So only consider forward branches here. 216 if (Succ.getNumber() <= MBB.getNumber()) 217 return; 218 219 // Place the BLOCK for a forward branch. For simplicity, we just insert 220 // blocks immediately inside loop boundaries. 221 MachineLoop *Loop = MLI.getLoopFor(&Succ); 222 MachineBasicBlock &Header = *(Loop ? Loop->getHeader() : &MF.front()); 223 MachineBasicBlock::iterator InsertPos = Header.begin(), End = Header.end(); 224 if (InsertPos != End) { 225 if (InsertPos->getOpcode() == WebAssembly::LOOP) 226 ++InsertPos; 227 int SuccNumber = Succ.getNumber(); 228 // Position the BLOCK in nesting order. 229 for (; InsertPos != End && InsertPos->getOpcode() == WebAssembly::BLOCK; 230 ++InsertPos) { 231 int N = InsertPos->getOperand(0).getMBB()->getNumber(); 232 if (N < SuccNumber) 233 break; 234 // If there's already a BLOCK for Succ, we don't need another. 235 if (N == SuccNumber) 236 return; 237 } 238 } 239 240 BuildMI(Header, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK)) 241 .addMBB(&Succ); 242 } 243 244 /// Insert LOOP and BLOCK markers at appropriate places. 245 static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI, 246 const WebAssemblyInstrInfo &TII) { 247 for (auto &MBB : MF) { 248 // Place the LOOP for loops. 249 if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) 250 if (Loop->getHeader() == &MBB) { 251 // The operand of a LOOP is the first block after the loop. If the loop 252 // is the bottom of the function, insert a dummy block at the end. 253 MachineBasicBlock *Bottom = Loop->getBottomBlock(); 254 auto Iter = next(MachineFunction::iterator(Bottom)); 255 if (Iter == MF.end()) { 256 MF.push_back(MF.CreateMachineBasicBlock()); 257 Iter = next(MachineFunction::iterator(Bottom)); 258 } 259 BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP)) 260 .addMBB(Iter); 261 } 262 263 // Check for forward branches and switches that need BLOCKS placed. 264 for (auto &Term : MBB.terminators()) 265 for (auto &MO : Term.operands()) 266 if (MO.isMBB()) 267 PlaceBlockMarkers(MBB, *MO.getMBB(), MF, MLI, TII); 268 } 269 } 270 271 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 272 DEBUG(dbgs() << "********** CFG Stackifying **********\n" 273 "********** Function: " 274 << MF.getName() << '\n'); 275 276 const auto &MLI = getAnalysis<MachineLoopInfo>(); 277 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 278 279 // RPO sorting needs all loops to be single-entry. 280 EliminateMultipleEntryLoops(MF, MLI); 281 282 // Sort the blocks in RPO, with contiguous loops. 283 SortBlocks(MF, MLI); 284 285 // Place the BLOCK and LOOP markers to indicate the beginnings of scopes. 286 PlaceMarkers(MF, MLI, TII); 287 288 return true; 289 } 290