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