1 //===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// \brief This file implements a CFG stacking pass.
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.
16 /// This is sufficient to convert arbitrary CFGs into a form that works on
17 /// WebAssembly, provided that all loops are single-entry.
19 //===----------------------------------------------------------------------===//
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"
36 #define DEBUG_TYPE "wasm-cfg-stackify"
39 class WebAssemblyCFGStackify final : public MachineFunctionPass {
40 StringRef getPassName() const override { return "WebAssembly CFG Stackify"; }
42 void getAnalysisUsage(AnalysisUsage &AU) const override {
44 AU.addRequired<MachineDominatorTree>();
45 AU.addPreserved<MachineDominatorTree>();
46 AU.addRequired<MachineLoopInfo>();
47 AU.addPreserved<MachineLoopInfo>();
48 MachineFunctionPass::getAnalysisUsage(AU);
51 bool runOnMachineFunction(MachineFunction &MF) override;
54 static char ID; // Pass identification, replacement for typeid
55 WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
57 } // end anonymous namespace
59 char WebAssemblyCFGStackify::ID = 0;
60 FunctionPass *llvm::createWebAssemblyCFGStackify() {
61 return new WebAssemblyCFGStackify();
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.
69 static 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)
78 /// Insert a BLOCK marker for branches to MBB (if needed).
79 static 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))
105 assert(&MBB != &MF.front() && "Header blocks shouldn't have predecessors");
106 MachineBasicBlock *LayoutPred = &*std::prev(MachineFunction::iterator(&MBB));
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));
116 // We found a scope level at an appropriate depth.
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)
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)
146 MachineInstr *Begin = BuildMI(*Header, InsertPos, DebugLoc(),
147 TII.get(WebAssembly::BLOCK))
148 .addImm(int64_t(WebAssembly::ExprType::Void));
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())
156 MachineInstr *End = BuildMI(MBB, InsertPos, DebugLoc(),
157 TII.get(WebAssembly::END_BLOCK));
158 BlockTops[End] = Begin;
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;
167 /// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
168 static 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)
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);
186 Iter = std::next(MachineFunction::iterator(Bottom));
188 MachineBasicBlock *AfterLoop = &*Iter;
190 // Mark the beginning of the loop (after the end of any existing loop that
192 auto InsertPos = MBB.begin();
193 while (InsertPos != MBB.end() &&
194 InsertPos->getOpcode() == WebAssembly::END_LOOP)
196 MachineInstr *Begin = BuildMI(MBB, InsertPos, DebugLoc(),
197 TII.get(WebAssembly::LOOP))
198 .addImm(int64_t(WebAssembly::ExprType::Void));
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;
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;
213 GetDepth(const SmallVectorImpl<const MachineBasicBlock *> &Stack,
214 const MachineBasicBlock *MBB) {
216 for (auto X : reverse(Stack)) {
221 assert(Depth < Stack.size() && "Branch destination should be in scope");
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.
232 static void FixEndsAtEndOfFunction(
234 const WebAssemblyFunctionInfo &MFI,
235 DenseMap<const MachineInstr *, MachineInstr *> &BlockTops,
236 DenseMap<const MachineInstr *, MachineInstr *> &LoopTops) {
237 assert(MFI.getResults().size() <= 1);
239 if (MFI.getResults().empty())
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");
255 for (MachineBasicBlock &MBB : reverse(MF)) {
256 for (MachineInstr &MI : reverse(MBB)) {
257 if (MI.isPosition() || MI.isDebugValue())
259 if (MI.getOpcode() == WebAssembly::END_BLOCK) {
260 BlockTops[&MI]->getOperand(0).setImm(int32_t(retType));
263 if (MI.getOpcode() == WebAssembly::END_LOOP) {
264 LoopTops[&MI]->getOperand(0).setImm(int32_t(retType));
267 // Something other than an `end`. We're done.
273 // WebAssembly functions end with an end instruction, as if the function body
275 static void AppendEndToFunction(
277 const WebAssemblyInstrInfo &TII) {
278 BuildMI(MF.back(), MF.back().end(), DebugLoc(),
279 TII.get(WebAssembly::END_FUNCTION));
282 /// Insert LOOP and BLOCK markers at appropriate places.
283 static 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);
294 // For each LOOP_END, the corresponding LOOP.
295 DenseMap<const MachineInstr *, MachineInstr *> LoopTops;
297 // For each END_BLOCK, the corresponding BLOCK.
298 DenseMap<const MachineInstr *, MachineInstr *> BlockTops;
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);
304 // Place the BLOCK for MBB if MBB is branched to from above.
305 PlaceBlockMarker(MBB, MF, ScopeTops, BlockTops, LoopTops, TII, MLI, MDT, MFI);
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");
318 case WebAssembly::LOOP:
319 assert(Stack.back() == &MBB && "Loop top should be balanced");
322 case WebAssembly::END_BLOCK:
323 Stack.push_back(&MBB);
325 case WebAssembly::END_LOOP:
326 Stack.push_back(LoopTops[&MI]->getParent());
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) {
336 MO = MachineOperand::CreateImm(GetDepth(Stack, MO.getMBB()));
337 MI.addOperand(MF, MO);
344 assert(Stack.empty() && "Control flow should be balanced");
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);
350 // Add an end instruction at the end of the function body.
351 if (!MF.getSubtarget<WebAssemblySubtarget>()
352 .getTargetTriple().isOSBinFormatELF())
353 AppendEndToFunction(MF, TII);
356 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
357 DEBUG(dbgs() << "********** CFG Stackifying **********\n"
358 "********** Function: "
359 << MF.getName() << '\n');
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();
368 // Place the BLOCK and LOOP markers to indicate the beginnings of scopes.
369 PlaceMarkers(MF, MLI, TII, MDT, MFI);