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 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
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.
21 /// This is sufficient to convert arbitrary CFGs into a form that works on
22 /// WebAssembly, provided that all loops are single-entry.
24 /// [0] https://en.wikipedia.org/wiki/Depth-first_search#Vertex_orderings
26 //===----------------------------------------------------------------------===//
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"
40 #define DEBUG_TYPE "wasm-cfg-stackify"
43 class WebAssemblyCFGStackify final : public MachineFunctionPass {
44 const char *getPassName() const override {
45 return "WebAssembly CFG Stackify";
48 void getAnalysisUsage(AnalysisUsage &AU) const override {
50 AU.addRequired<MachineLoopInfo>();
51 AU.addPreserved<MachineLoopInfo>();
52 MachineFunctionPass::getAnalysisUsage(AU);
55 bool runOnMachineFunction(MachineFunction &MF) override;
58 static char ID; // Pass identification, replacement for typeid
59 WebAssemblyCFGStackify() : MachineFunctionPass(ID) {}
61 } // end anonymous namespace
63 char WebAssemblyCFGStackify::ID = 0;
64 FunctionPass *llvm::createWebAssemblyCFGStackify() {
65 return new WebAssemblyCFGStackify();
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);
73 const std::vector<MachineBasicBlock *> &CurrentSCC = *I;
76 if (CurrentSCC.size() == 1)
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))
89 // TODO: Implement multiple-entry loops.
90 report_fatal_error("multiple-entry loops are not supported yet");
93 assert(MLI.isLoopHeader(Header));
100 /// Post-order traversal stack entry.
101 struct POStackEntry {
102 MachineBasicBlock *MBB;
103 SmallVector<MachineBasicBlock *, 0> Succs;
105 POStackEntry(MachineBasicBlock *MBB, MachineFunction &MF,
106 const MachineLoopInfo &MLI);
108 } // end anonymous namespace
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;
120 Succs.begin(), Succs.end(),
121 [=, &MLI](const MachineBasicBlock *A, const MachineBasicBlock *B) {
125 // Keep loops contiguous by preferring the block that's in the same
127 MachineLoop *LoopA = MLI.getLoopFor(A);
128 MachineLoop *LoopB = MLI.getLoopFor(B);
129 if (LoopA == Loop && LoopB != Loop)
131 if (LoopA != Loop && LoopB == Loop)
134 // Minimize perturbation by preferring the block which is the immediate
141 // TODO: More sophisticated orderings may be profitable here.
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;
157 MachineBasicBlock *Entry = &*MF.begin();
158 Visited.insert(Entry);
159 Stack.push_back(POStackEntry(Entry, MF, MLI));
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));
171 // Put the block in its position in the MachineFunction.
172 MachineBasicBlock &MBB = *Entry.MBB;
173 MBB.moveBefore(&*MF.begin());
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())
180 "Non-branch terminator with fallthrough cannot yet be rewritten");
181 if (MBB.empty() || !MBB.back().isTerminator() || MBB.back().isBranch())
182 MBB.updateTerminator();
189 // Now that we've sorted the blocks in RPO, renumber them.
194 if (MachineLoop *Loop = MLI.getLoopFor(&MBB)) {
195 // Assert that loops are contiguous.
196 assert(Loop->getHeader() == Loop->getTopBlock());
197 assert((Loop->getHeader() == &MBB ||
199 MLI.getLoopFor(&*prev(MachineFunction::iterator(&MBB))))) &&
200 "Loop isn't contiguous");
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");
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())
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)
227 int SuccNumber = Succ.getNumber();
228 // Position the BLOCK in nesting order.
229 for (; InsertPos != End && InsertPos->getOpcode() == WebAssembly::BLOCK;
231 int N = InsertPos->getOperand(0).getMBB()->getNumber();
234 // If there's already a BLOCK for Succ, we don't need another.
240 BuildMI(Header, InsertPos, DebugLoc(), TII.get(WebAssembly::BLOCK))
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));
259 BuildMI(MBB, MBB.begin(), DebugLoc(), TII.get(WebAssembly::LOOP))
263 // Check for forward branches and switches that need BLOCKS placed.
264 for (auto &Term : MBB.terminators())
265 for (auto &MO : Term.operands())
267 PlaceBlockMarkers(MBB, *MO.getMBB(), MF, MLI, TII);
271 bool WebAssemblyCFGStackify::runOnMachineFunction(MachineFunction &MF) {
272 DEBUG(dbgs() << "********** CFG Stackifying **********\n"
273 "********** Function: "
274 << MF.getName() << '\n');
276 const auto &MLI = getAnalysis<MachineLoopInfo>();
277 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
279 // RPO sorting needs all loops to be single-entry.
280 EliminateMultipleEntryLoops(MF, MLI);
282 // Sort the blocks in RPO, with contiguous loops.
285 // Place the BLOCK and LOOP markers to indicate the beginnings of scopes.
286 PlaceMarkers(MF, MLI, TII);