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 inserts BLOCK and LOOP markers to mark the start of scopes, since 14 /// scope boundaries serve as the labels for WebAssembly's control transfers. 15 /// 16 /// This is sufficient to convert arbitrary CFGs into a form that works on 17 /// WebAssembly, provided that all loops are single-entry. 18 /// 19 //===----------------------------------------------------------------------===// 20 21 #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" 22 #include "WebAssembly.h" 23 #include "WebAssemblyMachineFunctionInfo.h" 24 #include "WebAssemblySubtarget.h" 25 #include "WebAssemblyUtilities.h" 26 #include "llvm/CodeGen/MachineDominators.h" 27 #include "llvm/CodeGen/MachineFunction.h" 28 #include "llvm/CodeGen/MachineInstrBuilder.h" 29 #include "llvm/CodeGen/MachineLoopInfo.h" 30 #include "llvm/CodeGen/MachineRegisterInfo.h" 31 #include "llvm/CodeGen/Passes.h" 32 #include "llvm/Support/Debug.h" 33 #include "llvm/Support/raw_ostream.h" 34 using namespace llvm; 35 36 #define DEBUG_TYPE "wasm-cfg-stackify" 37 38 namespace { 39 class WebAssemblyCFGStackify final : public MachineFunctionPass { 40 StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } 41 42 void getAnalysisUsage(AnalysisUsage &AU) const override { 43 AU.setPreservesCFG(); 44 AU.addRequired<MachineDominatorTree>(); 45 AU.addPreserved<MachineDominatorTree>(); 46 AU.addRequired<MachineLoopInfo>(); 47 AU.addPreserved<MachineLoopInfo>(); 48 MachineFunctionPass::getAnalysisUsage(AU); 49 } 50 51 bool runOnMachineFunction(MachineFunction &MF) override; 52 53 public: 54 static char ID; // Pass identification, replacement for typeid 55 WebAssemblyCFGStackify() : MachineFunctionPass(ID) {} 56 }; 57 } // end anonymous namespace 58 59 char WebAssemblyCFGStackify::ID = 0; 60 INITIALIZE_PASS(WebAssemblyCFGStackify, DEBUG_TYPE, 61 "Insert BLOCK and LOOP markers for WebAssembly scopes", 62 false, false) 63 64 FunctionPass *llvm::createWebAssemblyCFGStackify() { 65 return new WebAssemblyCFGStackify(); 66 } 67 68 /// Test whether Pred has any terminators explicitly branching to MBB, as 69 /// opposed to falling through. Note that it's possible (eg. in unoptimized 70 /// code) for a branch instruction to both branch to a block and fallthrough 71 /// to it, so we check the actual branch operands to see if there are any 72 /// explicit mentions. 73 static bool ExplicitlyBranchesTo(MachineBasicBlock *Pred, 74 MachineBasicBlock *MBB) { 75 for (MachineInstr &MI : Pred->terminators()) 76 for (MachineOperand &MO : MI.explicit_operands()) 77 if (MO.isMBB() && MO.getMBB() == MBB) 78 return true; 79 return false; 80 } 81 82 /// Insert a BLOCK marker for branches to MBB (if needed). 83 static void PlaceBlockMarker( 84 MachineBasicBlock &MBB, MachineFunction &MF, 85 SmallVectorImpl<MachineBasicBlock *> &ScopeTops, 86 DenseMap<const MachineInstr *, MachineInstr *> &BlockTops, 87 DenseMap<const MachineInstr *, MachineInstr *> &LoopTops, 88 const WebAssemblyInstrInfo &TII, 89 const MachineLoopInfo &MLI, 90 MachineDominatorTree &MDT, 91 WebAssemblyFunctionInfo &MFI) { 92 // First compute the nearest common dominator of all forward non-fallthrough 93 // predecessors so that we minimize the time that the BLOCK is on the stack, 94 // which reduces overall stack height. 95 MachineBasicBlock *Header = nullptr; 96 bool IsBranchedTo = false; 97 int MBBNumber = MBB.getNumber(); 98 for (MachineBasicBlock *Pred : MBB.predecessors()) 99 if (Pred->getNumber() < MBBNumber) { 100 Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 101 if (ExplicitlyBranchesTo(Pred, &MBB)) 102 IsBranchedTo = true; 103 } 104 if (!Header) 105 return; 106 if (!IsBranchedTo) 107 return; 108 109 assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors"); 110 MachineBasicBlock *LayoutPred = &*std::prev(MachineFunction::iterator(&MBB)); 111 112 // If the nearest common dominator is inside a more deeply nested context, 113 // walk out to the nearest scope which isn't more deeply nested. 114 for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 115 if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 116 if (ScopeTop->getNumber() > Header->getNumber()) { 117 // Skip over an intervening scope. 118 I = std::next(MachineFunction::iterator(ScopeTop)); 119 } else { 120 // We found a scope level at an appropriate depth. 121 Header = ScopeTop; 122 break; 123 } 124 } 125 } 126 127 // Decide where in Header to put the BLOCK. 128 MachineBasicBlock::iterator InsertPos; 129 MachineLoop *HeaderLoop = MLI.getLoopFor(Header); 130 if (HeaderLoop && MBB.getNumber() > LoopBottom(HeaderLoop)->getNumber()) { 131 // Header is the header of a loop that does not lexically contain MBB, so 132 // the BLOCK needs to be above the LOOP, after any END constructs. 133 InsertPos = Header->begin(); 134 while (InsertPos->getOpcode() == WebAssembly::END_BLOCK || 135 InsertPos->getOpcode() == WebAssembly::END_LOOP) 136 ++InsertPos; 137 } else { 138 // Otherwise, insert the BLOCK as late in Header as we can, but before the 139 // beginning of the local expression tree and any nested BLOCKs. 140 InsertPos = Header->getFirstTerminator(); 141 while (InsertPos != Header->begin() && 142 WebAssembly::isChild(*std::prev(InsertPos), MFI) && 143 std::prev(InsertPos)->getOpcode() != WebAssembly::LOOP && 144 std::prev(InsertPos)->getOpcode() != WebAssembly::END_BLOCK && 145 std::prev(InsertPos)->getOpcode() != WebAssembly::END_LOOP) 146 --InsertPos; 147 } 148 149 // Add the BLOCK. 150 MachineInstr *Begin = 151 BuildMI(*Header, InsertPos, Header->findDebugLoc(InsertPos), 152 TII.get(WebAssembly::BLOCK)) 153 .addImm(int64_t(WebAssembly::ExprType::Void)); 154 155 // Mark the end of the block. 156 InsertPos = MBB.begin(); 157 while (InsertPos != MBB.end() && 158 InsertPos->getOpcode() == WebAssembly::END_LOOP && 159 LoopTops[&*InsertPos]->getParent()->getNumber() >= Header->getNumber()) 160 ++InsertPos; 161 MachineInstr *End = BuildMI(MBB, InsertPos, MBB.findPrevDebugLoc(InsertPos), 162 TII.get(WebAssembly::END_BLOCK)); 163 BlockTops[End] = Begin; 164 165 // Track the farthest-spanning scope that ends at this point. 166 int Number = MBB.getNumber(); 167 if (!ScopeTops[Number] || 168 ScopeTops[Number]->getNumber() > Header->getNumber()) 169 ScopeTops[Number] = Header; 170 } 171 172 /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header). 173 static void PlaceLoopMarker( 174 MachineBasicBlock &MBB, MachineFunction &MF, 175 SmallVectorImpl<MachineBasicBlock *> &ScopeTops, 176 DenseMap<const MachineInstr *, MachineInstr *> &LoopTops, 177 const WebAssemblyInstrInfo &TII, const MachineLoopInfo &MLI) { 178 MachineLoop *Loop = MLI.getLoopFor(&MBB); 179 if (!Loop || Loop->getHeader() != &MBB) 180 return; 181 182 // The operand of a LOOP is the first block after the loop. If the loop is the 183 // bottom of the function, insert a dummy block at the end. 184 MachineBasicBlock *Bottom = LoopBottom(Loop); 185 auto Iter = std::next(MachineFunction::iterator(Bottom)); 186 if (Iter == MF.end()) { 187 MachineBasicBlock *Label = MF.CreateMachineBasicBlock(); 188 // Give it a fake predecessor so that AsmPrinter prints its label. 189 Label->addSuccessor(Label); 190 MF.push_back(Label); 191 Iter = std::next(MachineFunction::iterator(Bottom)); 192 } 193 MachineBasicBlock *AfterLoop = &*Iter; 194 195 // Mark the beginning of the loop (after the end of any existing loop that 196 // ends here). 197 auto InsertPos = MBB.begin(); 198 while (InsertPos != MBB.end() && 199 InsertPos->getOpcode() == WebAssembly::END_LOOP) 200 ++InsertPos; 201 MachineInstr *Begin = BuildMI(MBB, InsertPos, MBB.findDebugLoc(InsertPos), 202 TII.get(WebAssembly::LOOP)) 203 .addImm(int64_t(WebAssembly::ExprType::Void)); 204 205 // Mark the end of the loop (using arbitrary debug location that branched 206 // to the loop end as its location). 207 DebugLoc EndDL = (*AfterLoop->pred_rbegin())->findBranchDebugLoc(); 208 MachineInstr *End = BuildMI(*AfterLoop, AfterLoop->begin(), EndDL, 209 TII.get(WebAssembly::END_LOOP)); 210 LoopTops[End] = Begin; 211 212 assert((!ScopeTops[AfterLoop->getNumber()] || 213 ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) && 214 "With block sorting the outermost loop for a block should be first."); 215 if (!ScopeTops[AfterLoop->getNumber()]) 216 ScopeTops[AfterLoop->getNumber()] = &MBB; 217 } 218 219 static unsigned 220 GetDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack, 221 const MachineBasicBlock *MBB) { 222 unsigned Depth = 0; 223 for (auto X : reverse(Stack)) { 224 if (X == MBB) 225 break; 226 ++Depth; 227 } 228 assert(Depth < Stack.size() && "Branch destination should be in scope"); 229 return Depth; 230 } 231 232 /// In normal assembly languages, when the end of a function is unreachable, 233 /// because the function ends in an infinite loop or a noreturn call or similar, 234 /// it isn't necessary to worry about the function return type at the end of 235 /// the function, because it's never reached. However, in WebAssembly, blocks 236 /// that end at the function end need to have a return type signature that 237 /// matches the function signature, even though it's unreachable. This function 238 /// checks for such cases and fixes up the signatures. 239 static void FixEndsAtEndOfFunction( 240 MachineFunction &MF, 241 const WebAssemblyFunctionInfo &MFI, 242 DenseMap<const MachineInstr *, MachineInstr *> &BlockTops, 243 DenseMap<const MachineInstr *, MachineInstr *> &LoopTops) { 244 assert(MFI.getResults().size() <= 1); 245 246 if (MFI.getResults().empty()) 247 return; 248 249 WebAssembly::ExprType retType; 250 switch (MFI.getResults().front().SimpleTy) { 251 case MVT::i32: retType = WebAssembly::ExprType::I32; break; 252 case MVT::i64: retType = WebAssembly::ExprType::I64; break; 253 case MVT::f32: retType = WebAssembly::ExprType::F32; break; 254 case MVT::f64: retType = WebAssembly::ExprType::F64; break; 255 case MVT::v16i8: retType = WebAssembly::ExprType::I8x16; break; 256 case MVT::v8i16: retType = WebAssembly::ExprType::I16x8; break; 257 case MVT::v4i32: retType = WebAssembly::ExprType::I32x4; break; 258 case MVT::v4f32: retType = WebAssembly::ExprType::F32x4; break; 259 case MVT::ExceptRef: retType = WebAssembly::ExprType::ExceptRef; break; 260 default: llvm_unreachable("unexpected return type"); 261 } 262 263 for (MachineBasicBlock &MBB : reverse(MF)) { 264 for (MachineInstr &MI : reverse(MBB)) { 265 if (MI.isPosition() || MI.isDebugValue()) 266 continue; 267 if (MI.getOpcode() == WebAssembly::END_BLOCK) { 268 BlockTops[&MI]->getOperand(0).setImm(int32_t(retType)); 269 continue; 270 } 271 if (MI.getOpcode() == WebAssembly::END_LOOP) { 272 LoopTops[&MI]->getOperand(0).setImm(int32_t(retType)); 273 continue; 274 } 275 // Something other than an `end`. We're done. 276 return; 277 } 278 } 279 } 280 281 // WebAssembly functions end with an end instruction, as if the function body 282 // were a block. 283 static void AppendEndToFunction( 284 MachineFunction &MF, 285 const WebAssemblyInstrInfo &TII) { 286 BuildMI(MF.back(), MF.back().end(), 287 MF.back().findPrevDebugLoc(MF.back().end()), 288 TII.get(WebAssembly::END_FUNCTION)); 289 } 290 291 /// Insert LOOP and BLOCK markers at appropriate places. 292 static void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI, 293 const WebAssemblyInstrInfo &TII, 294 MachineDominatorTree &MDT, 295 WebAssemblyFunctionInfo &MFI) { 296 // For each block whose label represents the end of a scope, record the block 297 // which holds the beginning of the scope. This will allow us to quickly skip 298 // over scoped regions when walking blocks. We allocate one more than the 299 // number of blocks in the function to accommodate for the possible fake block 300 // we may insert at the end. 301 SmallVector<MachineBasicBlock *, 8> ScopeTops(MF.getNumBlockIDs() + 1); 302 303 // For each LOOP_END, the corresponding LOOP. 304 DenseMap<const MachineInstr *, MachineInstr *> LoopTops; 305 306 // For each END_BLOCK, the corresponding BLOCK. 307 DenseMap<const MachineInstr *, MachineInstr *> BlockTops; 308 309 for (auto &MBB : MF) { 310 // Place the LOOP for MBB if MBB is the header of a loop. 311 PlaceLoopMarker(MBB, MF, ScopeTops, LoopTops, TII, MLI); 312 313 // Place the BLOCK for MBB if MBB is branched to from above. 314 PlaceBlockMarker(MBB, MF, ScopeTops, BlockTops, LoopTops, TII, MLI, MDT, MFI); 315 } 316 317 // Now rewrite references to basic blocks to be depth immediates. 318 SmallVector<const MachineBasicBlock *, 8> Stack; 319 for (auto &MBB : reverse(MF)) { 320 for (auto &MI : reverse(MBB)) { 321 switch (MI.getOpcode()) { 322 case WebAssembly::BLOCK: 323 assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= MBB.getNumber() && 324 "Block should be balanced"); 325 Stack.pop_back(); 326 break; 327 case WebAssembly::LOOP: 328 assert(Stack.back() == &MBB && "Loop top should be balanced"); 329 Stack.pop_back(); 330 break; 331 case WebAssembly::END_BLOCK: 332 Stack.push_back(&MBB); 333 break; 334 case WebAssembly::END_LOOP: 335 Stack.push_back(LoopTops[&MI]->getParent()); 336 break; 337 default: 338 if (MI.isTerminator()) { 339 // Rewrite MBB operands to be depth immediates. 340 SmallVector<MachineOperand, 4> Ops(MI.operands()); 341 while (MI.getNumOperands() > 0) 342 MI.RemoveOperand(MI.getNumOperands() - 1); 343 for (auto MO : Ops) { 344 if (MO.isMBB()) 345 MO = MachineOperand::CreateImm(GetDepth(Stack, MO.getMBB())); 346 MI.addOperand(MF, MO); 347 } 348 } 349 break; 350 } 351 } 352 } 353 assert(Stack.empty() && "Control flow should be balanced"); 354 355 // Fix up block/loop signatures at the end of the function to conform to 356 // WebAssembly's rules. 357 FixEndsAtEndOfFunction(MF, MFI, BlockTops, LoopTops); 358 359 // Add an end instruction at the end of the function body. 360 if (!MF.getSubtarget<WebAssemblySubtarget>() 361 .getTargetTriple().isOSBinFormatELF()) 362 AppendEndToFunction(MF, TII); 363 } 364 365 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 366 DEBUG(dbgs() << "********** CFG Stackifying **********\n" 367 "********** Function: " 368 << MF.getName() << '\n'); 369 370 const auto &MLI = getAnalysis<MachineLoopInfo>(); 371 auto &MDT = getAnalysis<MachineDominatorTree>(); 372 // Liveness is not tracked for VALUE_STACK physreg. 373 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 374 WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 375 MF.getRegInfo().invalidateLiveness(); 376 377 // Place the BLOCK and LOOP markers to indicate the beginnings of scopes. 378 PlaceMarkers(MF, MLI, TII, MDT, MFI); 379 380 return true; 381 } 382