WebAssemblyCFGStackify.cpp revision 321369
144743Smarkm//===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===// 244743Smarkm// 344743Smarkm// The LLVM Compiler Infrastructure 444743Smarkm// 544743Smarkm// This file is distributed under the University of Illinois Open Source 644743Smarkm// License. See LICENSE.TXT for details. 744743Smarkm// 844743Smarkm//===----------------------------------------------------------------------===// 944743Smarkm/// 1044743Smarkm/// \file 1144743Smarkm/// \brief This file implements a CFG stacking pass. 1244743Smarkm/// 1344743Smarkm/// This pass inserts BLOCK and LOOP markers to mark the start of scopes, since 1444743Smarkm/// scope boundaries serve as the labels for WebAssembly's control transfers. 1544743Smarkm/// 1656977Sshin/// This is sufficient to convert arbitrary CFGs into a form that works on 1756977Sshin/// WebAssembly, provided that all loops are single-entry. 1844743Smarkm/// 1944743Smarkm//===----------------------------------------------------------------------===// 2044743Smarkm 2144743Smarkm#include "MCTargetDesc/WebAssemblyMCTargetDesc.h" 2244743Smarkm#include "WebAssembly.h" 2344743Smarkm#include "WebAssemblyMachineFunctionInfo.h" 2444743Smarkm#include "WebAssemblySubtarget.h" 2544743Smarkm#include "WebAssemblyUtilities.h" 2644743Smarkm#include "llvm/CodeGen/MachineDominators.h" 2744743Smarkm#include "llvm/CodeGen/MachineFunction.h" 2844743Smarkm#include "llvm/CodeGen/MachineInstrBuilder.h" 2944743Smarkm#include "llvm/CodeGen/MachineLoopInfo.h" 3044743Smarkm#include "llvm/CodeGen/MachineRegisterInfo.h" 3144743Smarkm#include "llvm/CodeGen/Passes.h" 3244743Smarkm#include "llvm/Support/Debug.h" 3344743Smarkm#include "llvm/Support/raw_ostream.h" 3444743Smarkmusing namespace llvm; 35146187Sume 3663158Sume#define DEBUG_TYPE "wasm-cfg-stackify" 3756977Sshin 3856977Sshinnamespace { 3944743Smarkmclass WebAssemblyCFGStackify final : public MachineFunctionPass { 4044743Smarkm StringRef getPassName() const override { return "WebAssembly CFG Stackify"; } 4144743Smarkm 4244743Smarkm void getAnalysisUsage(AnalysisUsage &AU) const override { 4344743Smarkm AU.setPreservesCFG(); 4444743Smarkm AU.addRequired<MachineDominatorTree>(); 4544743Smarkm AU.addPreserved<MachineDominatorTree>(); 4644743Smarkm AU.addRequired<MachineLoopInfo>(); 4744743Smarkm AU.addPreserved<MachineLoopInfo>(); 4844743Smarkm MachineFunctionPass::getAnalysisUsage(AU); 4944743Smarkm } 5044743Smarkm 5144743Smarkm bool runOnMachineFunction(MachineFunction &MF) override; 5244743Smarkm 5344743Smarkmpublic: 5444743Smarkm static char ID; // Pass identification, replacement for typeid 5544743Smarkm WebAssemblyCFGStackify() : MachineFunctionPass(ID) {} 5644743Smarkm}; 5744743Smarkm} // end anonymous namespace 5844743Smarkm 5944743Smarkmchar WebAssemblyCFGStackify::ID = 0; 6044743SmarkmFunctionPass *llvm::createWebAssemblyCFGStackify() { 6144743Smarkm return new WebAssemblyCFGStackify(); 6244743Smarkm} 6344743Smarkm 6444743Smarkm/// Test whether Pred has any terminators explicitly branching to MBB, as 6544743Smarkm/// opposed to falling through. Note that it's possible (eg. in unoptimized 6644743Smarkm/// code) for a branch instruction to both branch to a block and fallthrough 6744743Smarkm/// to it, so we check the actual branch operands to see if there are any 6844743Smarkm/// explicit mentions. 6944743Smarkmstatic bool ExplicitlyBranchesTo(MachineBasicBlock *Pred, 7044743Smarkm MachineBasicBlock *MBB) { 7144743Smarkm for (MachineInstr &MI : Pred->terminators()) 7244743Smarkm for (MachineOperand &MO : MI.explicit_operands()) 7344743Smarkm if (MO.isMBB() && MO.getMBB() == MBB) 7444743Smarkm return true; 7544743Smarkm return false; 7644743Smarkm} 7744743Smarkm 7844743Smarkm/// Insert a BLOCK marker for branches to MBB (if needed). 7944743Smarkmstatic void PlaceBlockMarker( 8044743Smarkm MachineBasicBlock &MBB, MachineFunction &MF, 8156977Sshin SmallVectorImpl<MachineBasicBlock *> &ScopeTops, 8256977Sshin DenseMap<const MachineInstr *, MachineInstr *> &BlockTops, 8356977Sshin DenseMap<const MachineInstr *, MachineInstr *> &LoopTops, 8456977Sshin const WebAssemblyInstrInfo &TII, 8544743Smarkm const MachineLoopInfo &MLI, 8644743Smarkm MachineDominatorTree &MDT, 8756977Sshin WebAssemblyFunctionInfo &MFI) { 8844743Smarkm // First compute the nearest common dominator of all forward non-fallthrough 8944743Smarkm // predecessors so that we minimize the time that the BLOCK is on the stack, 9044743Smarkm // which reduces overall stack height. 9144743Smarkm MachineBasicBlock *Header = nullptr; 9244743Smarkm bool IsBranchedTo = false; 9344743Smarkm int MBBNumber = MBB.getNumber(); 9444743Smarkm for (MachineBasicBlock *Pred : MBB.predecessors()) 9544743Smarkm if (Pred->getNumber() < MBBNumber) { 9644743Smarkm Header = Header ? MDT.findNearestCommonDominator(Header, Pred) : Pred; 9744743Smarkm if (ExplicitlyBranchesTo(Pred, &MBB)) 9844743Smarkm IsBranchedTo = true; 9944743Smarkm } 10044743Smarkm if (!Header) 10144743Smarkm return; 10244743Smarkm if (!IsBranchedTo) 10344743Smarkm return; 10444743Smarkm 10544743Smarkm assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors"); 10644743Smarkm MachineBasicBlock *LayoutPred = &*std::prev(MachineFunction::iterator(&MBB)); 10744743Smarkm 10844743Smarkm // If the nearest common dominator is inside a more deeply nested context, 10944743Smarkm // walk out to the nearest scope which isn't more deeply nested. 11044743Smarkm for (MachineFunction::iterator I(LayoutPred), E(Header); I != E; --I) { 11144743Smarkm if (MachineBasicBlock *ScopeTop = ScopeTops[I->getNumber()]) { 11244743Smarkm if (ScopeTop->getNumber() > Header->getNumber()) { 113123895Sceri // Skip over an intervening scope. 11444743Smarkm I = std::next(MachineFunction::iterator(ScopeTop)); 11544743Smarkm } else { 11656977Sshin // We found a scope level at an appropriate depth. 11756977Sshin Header = ScopeTop; 11856977Sshin break; 11944743Smarkm } 12056977Sshin } 12144743Smarkm } 12244743Smarkm 12344743Smarkm // Decide where in Header to put the BLOCK. 12444743Smarkm MachineBasicBlock::iterator InsertPos; 12544743Smarkm MachineLoop *HeaderLoop = MLI.getLoopFor(Header); 12644743Smarkm if (HeaderLoop && MBB.getNumber() > LoopBottom(HeaderLoop)->getNumber()) { 12744743Smarkm // Header is the header of a loop that does not lexically contain MBB, so 12844743Smarkm // the BLOCK needs to be above the LOOP, after any END constructs. 12944743Smarkm InsertPos = Header->begin(); 13044743Smarkm while (InsertPos->getOpcode() == WebAssembly::END_BLOCK || 13144743Smarkm InsertPos->getOpcode() == WebAssembly::END_LOOP) 13244743Smarkm ++InsertPos; 13356977Sshin } else { 13456977Sshin // Otherwise, insert the BLOCK as late in Header as we can, but before the 13556977Sshin // beginning of the local expression tree and any nested BLOCKs. 13644743Smarkm InsertPos = Header->getFirstTerminator(); 13756977Sshin while (InsertPos != Header->begin() && 13844743Smarkm WebAssembly::isChild(*std::prev(InsertPos), MFI) && 13944743Smarkm std::prev(InsertPos)->getOpcode() != WebAssembly::LOOP && 14044743Smarkm std::prev(InsertPos)->getOpcode() != WebAssembly::END_BLOCK && 14144743Smarkm std::prev(InsertPos)->getOpcode() != WebAssembly::END_LOOP) 14244743Smarkm --InsertPos; 14344743Smarkm } 14444743Smarkm 14556977Sshin // Add the BLOCK. 14656977Sshin MachineInstr *Begin = BuildMI(*Header, InsertPos, DebugLoc(), 14763158Sume TII.get(WebAssembly::BLOCK)) 14856977Sshin .addImm(int64_t(WebAssembly::ExprType::Void)); 14956977Sshin 15056977Sshin // Mark the end of the block. 15163158Sume InsertPos = MBB.begin(); 15263158Sume while (InsertPos != MBB.end() && 15356977Sshin InsertPos->getOpcode() == WebAssembly::END_LOOP && 15463158Sume LoopTops[&*InsertPos]->getParent()->getNumber() >= Header->getNumber()) 15563158Sume ++InsertPos; 15663158Sume MachineInstr *End = BuildMI(MBB, InsertPos, DebugLoc(), 15763158Sume TII.get(WebAssembly::END_BLOCK)); 158146187Sume BlockTops[End] = Begin; 15963158Sume 16044743Smarkm // Track the farthest-spanning scope that ends at this point. 16144743Smarkm int Number = MBB.getNumber(); 16244743Smarkm if (!ScopeTops[Number] || 16344743Smarkm ScopeTops[Number]->getNumber() > Header->getNumber()) 16456977Sshin ScopeTops[Number] = Header; 16544743Smarkm} 16644743Smarkm 16744743Smarkm/// Insert a LOOP marker for a loop starting at MBB (if it's a loop header). 16844743Smarkmstatic void PlaceLoopMarker( 16944743Smarkm MachineBasicBlock &MBB, MachineFunction &MF, 17044743Smarkm SmallVectorImpl<MachineBasicBlock *> &ScopeTops, 17144743Smarkm DenseMap<const MachineInstr *, MachineInstr *> &LoopTops, 17256977Sshin const WebAssemblyInstrInfo &TII, const MachineLoopInfo &MLI) { 17356977Sshin MachineLoop *Loop = MLI.getLoopFor(&MBB); 17463158Sume if (!Loop || Loop->getHeader() != &MBB) 17563158Sume return; 17663158Sume 17763158Sume // The operand of a LOOP is the first block after the loop. If the loop is the 17863158Sume // bottom of the function, insert a dummy block at the end. 17963158Sume MachineBasicBlock *Bottom = LoopBottom(Loop); 18063158Sume auto Iter = std::next(MachineFunction::iterator(Bottom)); 18163158Sume if (Iter == MF.end()) { 18263158Sume MachineBasicBlock *Label = MF.CreateMachineBasicBlock(); 18363158Sume // Give it a fake predecessor so that AsmPrinter prints its label. 18463158Sume Label->addSuccessor(Label); 18563158Sume MF.push_back(Label); 18663158Sume Iter = std::next(MachineFunction::iterator(Bottom)); 18756977Sshin } 18863158Sume MachineBasicBlock *AfterLoop = &*Iter; 18963158Sume 19063158Sume // Mark the beginning of the loop (after the end of any existing loop that 19163158Sume // ends here). 19263158Sume auto InsertPos = MBB.begin(); 19363158Sume while (InsertPos != MBB.end() && 19463158Sume InsertPos->getOpcode() == WebAssembly::END_LOOP) 19563158Sume ++InsertPos; 19663158Sume MachineInstr *Begin = BuildMI(MBB, InsertPos, DebugLoc(), 19763158Sume TII.get(WebAssembly::LOOP)) 19863158Sume .addImm(int64_t(WebAssembly::ExprType::Void)); 19963158Sume 20063158Sume // Mark the end of the loop. 20163158Sume MachineInstr *End = BuildMI(*AfterLoop, AfterLoop->begin(), DebugLoc(), 20263158Sume TII.get(WebAssembly::END_LOOP)); 20363158Sume LoopTops[End] = Begin; 20463158Sume 20563158Sume assert((!ScopeTops[AfterLoop->getNumber()] || 20663158Sume ScopeTops[AfterLoop->getNumber()]->getNumber() < MBB.getNumber()) && 20763158Sume "With block sorting the outermost loop for a block should be first."); 20863158Sume if (!ScopeTops[AfterLoop->getNumber()]) 20963158Sume ScopeTops[AfterLoop->getNumber()] = &MBB; 210146187Sume} 21163158Sume 21263158Sumestatic unsigned 21363158SumeGetDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack, 21463158Sume const MachineBasicBlock *MBB) { 21563158Sume unsigned Depth = 0; 21666329Sume for (auto X : reverse(Stack)) { 21766329Sume if (X == MBB) 21866329Sume break; 21966329Sume ++Depth; 22066329Sume } 22179249Skris assert(Depth < Stack.size() && "Branch destination should be in scope"); 22266329Sume return Depth; 22366329Sume} 22466329Sume 22566329Sume/// In normal assembly languages, when the end of a function is unreachable, 22666329Sume/// because the function ends in an infinite loop or a noreturn call or similar, 22766329Sume/// it isn't necessary to worry about the function return type at the end of 22866329Sume/// the function, because it's never reached. However, in WebAssembly, blocks 22966329Sume/// that end at the function end need to have a return type signature that 23066329Sume/// matches the function signature, even though it's unreachable. This function 23166329Sume/// checks for such cases and fixes up the signatures. 23266329Sumestatic void FixEndsAtEndOfFunction( 23363158Sume MachineFunction &MF, 23463158Sume const WebAssemblyFunctionInfo &MFI, 23563158Sume DenseMap<const MachineInstr *, MachineInstr *> &BlockTops, 23663158Sume DenseMap<const MachineInstr *, MachineInstr *> &LoopTops) { 23763158Sume assert(MFI.getResults().size() <= 1); 23863158Sume 23963158Sume if (MFI.getResults().empty()) 24063158Sume return; 24163158Sume 24263158Sume WebAssembly::ExprType retType; 24363158Sume switch (MFI.getResults().front().SimpleTy) { 24463158Sume case MVT::i32: retType = WebAssembly::ExprType::I32; break; 24563158Sume case MVT::i64: retType = WebAssembly::ExprType::I64; break; 24663158Sume case MVT::f32: retType = WebAssembly::ExprType::F32; break; 24763158Sume case MVT::f64: retType = WebAssembly::ExprType::F64; break; 24863158Sume case MVT::v16i8: retType = WebAssembly::ExprType::I8x16; break; 24963158Sume case MVT::v8i16: retType = WebAssembly::ExprType::I16x8; break; 25063158Sume case MVT::v4i32: retType = WebAssembly::ExprType::I32x4; break; 25163158Sume case MVT::v4f32: retType = WebAssembly::ExprType::F32x4; break; 25263158Sume default: llvm_unreachable("unexpected return type"); 25363158Sume } 25463158Sume 25563158Sume for (MachineBasicBlock &MBB : reverse(MF)) { 25663158Sume for (MachineInstr &MI : reverse(MBB)) { 25763158Sume if (MI.isPosition() || MI.isDebugValue()) 25863158Sume continue; 25963158Sume if (MI.getOpcode() == WebAssembly::END_BLOCK) { 26063158Sume BlockTops[&MI]->getOperand(0).setImm(int32_t(retType)); 26166297Sume continue; 26266297Sume } 26363158Sume if (MI.getOpcode() == WebAssembly::END_LOOP) { 26463158Sume LoopTops[&MI]->getOperand(0).setImm(int32_t(retType)); 26563158Sume continue; 26663158Sume } 26763158Sume // Something other than an `end`. We're done. 26863158Sume return; 26963158Sume } 27063158Sume } 27163158Sume} 27266297Sume 27366297Sume// WebAssembly functions end with an end instruction, as if the function body 27463158Sume// were a block. 27563158Sumestatic void AppendEndToFunction( 27663158Sume MachineFunction &MF, 27763158Sume const WebAssemblyInstrInfo &TII) { 27863158Sume BuildMI(MF.back(), MF.back().end(), DebugLoc(), 27963158Sume TII.get(WebAssembly::END_FUNCTION)); 28063158Sume} 28163158Sume 28263158Sume/// Insert LOOP and BLOCK markers at appropriate places. 28363158Sumestatic void PlaceMarkers(MachineFunction &MF, const MachineLoopInfo &MLI, 28463158Sume const WebAssemblyInstrInfo &TII, 28563158Sume MachineDominatorTree &MDT, 28663158Sume WebAssemblyFunctionInfo &MFI) { 28763158Sume // For each block whose label represents the end of a scope, record the block 28863158Sume // which holds the beginning of the scope. This will allow us to quickly skip 28963158Sume // over scoped regions when walking blocks. We allocate one more than the 29063158Sume // number of blocks in the function to accommodate for the possible fake block 29163158Sume // we may insert at the end. 29266329Sume SmallVector<MachineBasicBlock *, 8> ScopeTops(MF.getNumBlockIDs() + 1); 29366329Sume 29466329Sume // For each LOOP_END, the corresponding LOOP. 29566329Sume DenseMap<const MachineInstr *, MachineInstr *> LoopTops; 29666329Sume 29763158Sume // For each END_BLOCK, the corresponding BLOCK. 29863158Sume DenseMap<const MachineInstr *, MachineInstr *> BlockTops; 29963158Sume 30063158Sume for (auto &MBB : MF) { 30163158Sume // Place the LOOP for MBB if MBB is the header of a loop. 30263158Sume PlaceLoopMarker(MBB, MF, ScopeTops, LoopTops, TII, MLI); 30363158Sume 30463158Sume // Place the BLOCK for MBB if MBB is branched to from above. 30563158Sume PlaceBlockMarker(MBB, MF, ScopeTops, BlockTops, LoopTops, TII, MLI, MDT, MFI); 30663158Sume } 30763158Sume 30863158Sume // Now rewrite references to basic blocks to be depth immediates. 30963158Sume SmallVector<const MachineBasicBlock *, 8> Stack; 31063158Sume for (auto &MBB : reverse(MF)) { 31163158Sume for (auto &MI : reverse(MBB)) { 31263158Sume switch (MI.getOpcode()) { 31363158Sume case WebAssembly::BLOCK: 31463158Sume assert(ScopeTops[Stack.back()->getNumber()]->getNumber() <= MBB.getNumber() && 315146187Sume "Block should be balanced"); 31663158Sume Stack.pop_back(); 31766297Sume break; 31866297Sume case WebAssembly::LOOP: 31963158Sume assert(Stack.back() == &MBB && "Loop top should be balanced"); 32063158Sume Stack.pop_back(); 32163158Sume break; 32263158Sume case WebAssembly::END_BLOCK: 32363158Sume Stack.push_back(&MBB); 32463158Sume break; 32544743Smarkm case WebAssembly::END_LOOP: 32644743Smarkm Stack.push_back(LoopTops[&MI]->getParent()); 32744743Smarkm break; 32844743Smarkm default: 32944743Smarkm if (MI.isTerminator()) { 33044743Smarkm // Rewrite MBB operands to be depth immediates. 33144743Smarkm SmallVector<MachineOperand, 4> Ops(MI.operands()); 33244743Smarkm while (MI.getNumOperands() > 0) 33344743Smarkm MI.RemoveOperand(MI.getNumOperands() - 1); 33444743Smarkm for (auto MO : Ops) { 33544743Smarkm if (MO.isMBB()) 33644743Smarkm MO = MachineOperand::CreateImm(GetDepth(Stack, MO.getMBB())); 33744743Smarkm MI.addOperand(MF, MO); 33844743Smarkm } 33944743Smarkm } 34044743Smarkm break; 34144743Smarkm } 34244743Smarkm } 34344743Smarkm } 34444743Smarkm assert(Stack.empty() && "Control flow should be balanced"); 34544743Smarkm 34644743Smarkm // Fix up block/loop signatures at the end of the function to conform to 34744743Smarkm // WebAssembly's rules. 34844743Smarkm FixEndsAtEndOfFunction(MF, MFI, BlockTops, LoopTops); 34944743Smarkm 35044743Smarkm // Add an end instruction at the end of the function body. 35144743Smarkm if (!MF.getSubtarget<WebAssemblySubtarget>() 35244743Smarkm .getTargetTriple().isOSBinFormatELF()) 35344743Smarkm AppendEndToFunction(MF, TII); 35444743Smarkm} 35544743Smarkm 35644743Smarkmbool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) { 35744743Smarkm DEBUG(dbgs() << "********** CFG Stackifying **********\n" 35844743Smarkm "********** Function: " 35944743Smarkm << MF.getName() << '\n'); 36044743Smarkm 36144743Smarkm const auto &MLI = getAnalysis<MachineLoopInfo>(); 36244743Smarkm auto &MDT = getAnalysis<MachineDominatorTree>(); 36344743Smarkm // Liveness is not tracked for VALUE_STACK physreg. 36444743Smarkm const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo(); 36544743Smarkm WebAssemblyFunctionInfo &MFI = *MF.getInfo<WebAssemblyFunctionInfo>(); 36644743Smarkm MF.getRegInfo().invalidateLiveness(); 36744743Smarkm 36844743Smarkm // Place the BLOCK and LOOP markers to indicate the beginnings of scopes. 36944743Smarkm PlaceMarkers(MF, MLI, TII, MDT, MFI); 37044743Smarkm 37144743Smarkm return true; 37244743Smarkm} 37344743Smarkm