blob: a3a256d63f2e6097a6e1b1dd1fef9e457ec30a64 [file] [log] [blame]
Dan Gohmand7a2eea2016-03-09 02:01:14 +00001//=- WebAssemblyFixIrreducibleControlFlow.cpp - Fix irreducible control flow -//
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
Heejin Ahn777d01c2019-01-03 23:10:11 +000011/// This file implements a pass that transforms irreducible control flow into
12/// reducible control flow. Irreducible control flow means multiple-entry
Dan Gohmand7a2eea2016-03-09 02:01:14 +000013/// loops; they appear as CFG cycles that are not recorded in MachineLoopInfo
14/// due to being unnatural.
15///
Dan Gohmanddfa1a62016-03-09 04:17:36 +000016/// Note that LLVM has a generic pass that lowers irreducible control flow, but
17/// it linearizes control flow, turning diamonds into two triangles, which is
18/// both unnecessary and undesirable for WebAssembly.
19///
Heejin Ahn777d01c2019-01-03 23:10:11 +000020/// The big picture: Ignoring natural loops (seeing them monolithically), we
21/// find all the blocks which can return to themselves ("loopers"). Loopers
22/// reachable from the non-loopers are loop entries: if there are 2 or more,
23/// then we have irreducible control flow. We fix that as follows: a new block
24/// is created that can dispatch to each of the loop entries, based on the
25/// value of a label "helper" variable, and we replace direct branches to the
26/// entries with assignments to the label variable and a branch to the dispatch
27/// block. Then the dispatch block is the single entry in a new natural loop.
28///
29/// This is similar to what the Relooper [1] does, both identify looping code
30/// that requires multiple entries, and resolve it in a similar way. In
31/// Relooper terminology, we implement a Multiple shape in a Loop shape. Note
32/// also that like the Relooper, we implement a "minimal" intervention: we only
33/// use the "label" helper for the blocks we absolutely must and no others. We
34/// also prioritize code size and do not perform node splitting (i.e. we don't
35/// duplicate code in order to resolve irreducibility).
36///
37/// The difference between this code and the Relooper is that the Relooper also
38/// generates ifs and loops and works in a recursive manner, knowing at each
39/// point what the entries are, and recursively breaks down the problem. Here
40/// we just want to resolve irreducible control flow, and we also want to use
41/// as much LLVM infrastructure as possible. So we use the MachineLoopInfo to
42/// identify natural loops, etc., and we start with the whole CFG and must
43/// identify both the looping code and its entries.
44///
45/// [1] Alon Zakai. 2011. Emscripten: an LLVM-to-JavaScript compiler. In
46/// Proceedings of the ACM international conference companion on Object oriented
47/// programming systems languages and applications companion (SPLASH '11). ACM,
48/// New York, NY, USA, 301-312. DOI=10.1145/2048147.2048224
49/// http://doi.acm.org/10.1145/2048147.2048224
Dan Gohmand7a2eea2016-03-09 02:01:14 +000050///
51//===----------------------------------------------------------------------===//
52
Dan Gohmand7a2eea2016-03-09 02:01:14 +000053#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000054#include "WebAssembly.h"
Dan Gohmand7a2eea2016-03-09 02:01:14 +000055#include "WebAssemblyMachineFunctionInfo.h"
56#include "WebAssemblySubtarget.h"
57#include "llvm/ADT/PriorityQueue.h"
58#include "llvm/ADT/SCCIterator.h"
59#include "llvm/ADT/SetVector.h"
60#include "llvm/CodeGen/MachineDominators.h"
61#include "llvm/CodeGen/MachineFunction.h"
62#include "llvm/CodeGen/MachineInstrBuilder.h"
63#include "llvm/CodeGen/MachineLoopInfo.h"
64#include "llvm/CodeGen/MachineRegisterInfo.h"
65#include "llvm/CodeGen/Passes.h"
66#include "llvm/Support/Debug.h"
67#include "llvm/Support/raw_ostream.h"
68using namespace llvm;
69
70#define DEBUG_TYPE "wasm-fix-irreducible-control-flow"
71
72namespace {
Dan Gohmand7a2eea2016-03-09 02:01:14 +000073
Heejin Ahn777d01c2019-01-03 23:10:11 +000074class LoopFixer {
Dan Gohmand7a2eea2016-03-09 02:01:14 +000075public:
Heejin Ahn777d01c2019-01-03 23:10:11 +000076 LoopFixer(MachineFunction &MF, MachineLoopInfo &MLI, MachineLoop *Loop)
77 : MF(MF), MLI(MLI), Loop(Loop) {}
Dan Gohmand7a2eea2016-03-09 02:01:14 +000078
Heejin Ahn777d01c2019-01-03 23:10:11 +000079 // Run the fixer on the given inputs. Returns whether changes were made.
80 bool run();
Jacob Gravelle40926452018-03-30 20:36:58 +000081
Heejin Ahn777d01c2019-01-03 23:10:11 +000082private:
83 MachineFunction &MF;
84 MachineLoopInfo &MLI;
85 MachineLoop *Loop;
Dan Gohmand7a2eea2016-03-09 02:01:14 +000086
Heejin Ahn777d01c2019-01-03 23:10:11 +000087 MachineBasicBlock *Header;
88 SmallPtrSet<MachineBasicBlock *, 4> LoopBlocks;
Dan Gohmand7a2eea2016-03-09 02:01:14 +000089
Heejin Ahn777d01c2019-01-03 23:10:11 +000090 using BlockSet = SmallPtrSet<MachineBasicBlock *, 4>;
91 DenseMap<MachineBasicBlock *, BlockSet> Reachable;
Dan Gohmand7a2eea2016-03-09 02:01:14 +000092
Heejin Ahn777d01c2019-01-03 23:10:11 +000093 // The worklist contains pairs of recent additions, (a, b), where we just
94 // added a link a => b.
95 using BlockPair = std::pair<MachineBasicBlock *, MachineBasicBlock *>;
96 SmallVector<BlockPair, 4> WorkList;
Dan Gohmand7a2eea2016-03-09 02:01:14 +000097
Heejin Ahn777d01c2019-01-03 23:10:11 +000098 // Get a canonical block to represent a block or a loop: the block, or if in
99 // an inner loop, the loop header, of it in an outer loop scope, we can
100 // ignore it. We need to call this on all blocks we work on.
101 MachineBasicBlock *canonicalize(MachineBasicBlock *MBB) {
102 MachineLoop *InnerLoop = MLI.getLoopFor(MBB);
103 if (InnerLoop == Loop) {
104 return MBB;
105 } else {
106 // This is either in an outer or an inner loop, and not in ours.
107 if (!LoopBlocks.count(MBB)) {
108 // It's in outer code, ignore it.
109 return nullptr;
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000110 }
Heejin Ahn777d01c2019-01-03 23:10:11 +0000111 assert(InnerLoop);
112 // It's in an inner loop, canonicalize it to the header of that loop.
113 return InnerLoop->getHeader();
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000114 }
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000115 }
116
Heejin Ahn777d01c2019-01-03 23:10:11 +0000117 // For a successor we can additionally ignore it if it's a branch back to a
118 // natural loop top, as when we are in the scope of a loop, we just care
119 // about internal irreducibility, and can ignore the loop we are in. We need
120 // to call this on all blocks in a context where they are a successor.
121 MachineBasicBlock *canonicalizeSuccessor(MachineBasicBlock *MBB) {
122 if (Loop && MBB == Loop->getHeader()) {
123 // Ignore branches going to the loop's natural header.
124 return nullptr;
125 }
126 return canonicalize(MBB);
127 }
128
129 // Potentially insert a new reachable edge, and if so, note it as further
130 // work.
131 void maybeInsert(MachineBasicBlock *MBB, MachineBasicBlock *Succ) {
132 assert(MBB == canonicalize(MBB));
133 assert(Succ);
134 // Succ may not be interesting as a sucessor.
135 Succ = canonicalizeSuccessor(Succ);
136 if (!Succ)
137 return;
138 if (Reachable[MBB].insert(Succ).second) {
139 // For there to be further work, it means that we have
140 // X => MBB => Succ
141 // for some other X, and in that case X => Succ would be a new edge for
142 // us to discover later. However, if we don't care about MBB as a
143 // successor, then we don't care about that anyhow.
144 if (canonicalizeSuccessor(MBB)) {
145 WorkList.emplace_back(MBB, Succ);
146 }
147 }
148 }
149};
150
151bool LoopFixer::run() {
152 Header = Loop ? Loop->getHeader() : &*MF.begin();
153
154 // Identify all the blocks in this loop scope.
155 if (Loop) {
156 for (auto *MBB : Loop->getBlocks()) {
157 LoopBlocks.insert(MBB);
158 }
159 } else {
160 for (auto &MBB : MF) {
161 LoopBlocks.insert(&MBB);
162 }
163 }
164
165 // Compute which (canonicalized) blocks each block can reach.
166
167 // Add all the initial work.
168 for (auto *MBB : LoopBlocks) {
169 MachineLoop *InnerLoop = MLI.getLoopFor(MBB);
170
171 if (InnerLoop == Loop) {
172 for (auto *Succ : MBB->successors()) {
173 maybeInsert(MBB, Succ);
174 }
175 } else {
176 // It can't be in an outer loop - we loop on LoopBlocks - and so it must
177 // be an inner loop.
178 assert(InnerLoop);
179 // Check if we are the canonical block for this loop.
180 if (canonicalize(MBB) != MBB) {
181 continue;
182 }
183 // The successors are those of the loop.
184 SmallVector<MachineBasicBlock *, 2> ExitBlocks;
185 InnerLoop->getExitBlocks(ExitBlocks);
186 for (auto *Succ : ExitBlocks) {
187 maybeInsert(MBB, Succ);
188 }
189 }
190 }
191
192 // Do work until we are all done.
193 while (!WorkList.empty()) {
194 MachineBasicBlock *MBB;
195 MachineBasicBlock *Succ;
196 std::tie(MBB, Succ) = WorkList.pop_back_val();
197 // The worklist item is an edge we just added, so it must have valid blocks
198 // (and not something canonicalized to nullptr).
199 assert(MBB);
200 assert(Succ);
201 // The successor in that pair must also be a valid successor.
202 assert(MBB == canonicalizeSuccessor(MBB));
203 // We recently added MBB => Succ, and that means we may have enabled
204 // Pred => MBB => Succ. Check all the predecessors. Note that our loop here
205 // is correct for both a block and a block representing a loop, as the loop
206 // is natural and so the predecessors are all predecessors of the loop
207 // header, which is the block we have here.
208 for (auto *Pred : MBB->predecessors()) {
209 // Canonicalize, make sure it's relevant, and check it's not the same
210 // block (an update to the block itself doesn't help compute that same
211 // block).
212 Pred = canonicalize(Pred);
213 if (Pred && Pred != MBB) {
214 maybeInsert(Pred, Succ);
215 }
216 }
217 }
218
219 // It's now trivial to identify the loopers.
220 SmallPtrSet<MachineBasicBlock *, 4> Loopers;
221 for (auto MBB : LoopBlocks) {
222 if (Reachable[MBB].count(MBB)) {
223 Loopers.insert(MBB);
224 }
225 }
226 // The header cannot be a looper. At the toplevel, LLVM does not allow the
227 // entry to be in a loop, and in a natural loop we should ignore the header.
228 assert(Loopers.count(Header) == 0);
229
230 // Find the entries, loopers reachable from non-loopers.
231 SmallPtrSet<MachineBasicBlock *, 4> Entries;
232 SmallVector<MachineBasicBlock *, 4> SortedEntries;
233 for (auto *Looper : Loopers) {
234 for (auto *Pred : Looper->predecessors()) {
235 Pred = canonicalize(Pred);
236 if (Pred && !Loopers.count(Pred)) {
237 Entries.insert(Looper);
238 SortedEntries.push_back(Looper);
239 break;
240 }
241 }
242 }
243
244 // Check if we found irreducible control flow.
245 if (LLVM_LIKELY(Entries.size() <= 1))
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000246 return false;
247
Heejin Ahn777d01c2019-01-03 23:10:11 +0000248 // Sort the entries to ensure a deterministic build.
249 llvm::sort(SortedEntries,
250 [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {
251 auto ANum = A->getNumber();
252 auto BNum = B->getNumber();
253 assert(ANum != -1 && BNum != -1);
254 assert(ANum != BNum);
255 return ANum < BNum;
256 });
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000257
Heejin Ahn777d01c2019-01-03 23:10:11 +0000258 // Create a dispatch block which will contain a jump table to the entries.
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000259 MachineBasicBlock *Dispatch = MF.CreateMachineBasicBlock();
260 MF.insert(MF.end(), Dispatch);
261 MLI.changeLoopFor(Dispatch, Loop);
262
263 // Add the jump table.
264 const auto &TII = *MF.getSubtarget<WebAssemblySubtarget>().getInstrInfo();
265 MachineInstrBuilder MIB = BuildMI(*Dispatch, Dispatch->end(), DebugLoc(),
266 TII.get(WebAssembly::BR_TABLE_I32));
267
268 // Add the register which will be used to tell the jump table which block to
269 // jump to.
270 MachineRegisterInfo &MRI = MF.getRegInfo();
271 unsigned Reg = MRI.createVirtualRegister(&WebAssembly::I32RegClass);
272 MIB.addReg(Reg);
273
Heejin Ahn777d01c2019-01-03 23:10:11 +0000274 // Compute the indices in the superheader, one for each bad block, and
275 // add them as successors.
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000276 DenseMap<MachineBasicBlock *, unsigned> Indices;
Heejin Ahn777d01c2019-01-03 23:10:11 +0000277 for (auto *MBB : SortedEntries) {
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000278 auto Pair = Indices.insert(std::make_pair(MBB, 0));
Heejin Ahn777d01c2019-01-03 23:10:11 +0000279 if (!Pair.second) {
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000280 continue;
Heejin Ahn777d01c2019-01-03 23:10:11 +0000281 }
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000282
Dan Gohmanf4562902016-04-26 01:40:56 +0000283 unsigned Index = MIB.getInstr()->getNumExplicitOperands() - 1;
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000284 Pair.first->second = Index;
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000285
286 MIB.addMBB(MBB);
287 Dispatch->addSuccessor(MBB);
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000288 }
289
Heejin Ahn777d01c2019-01-03 23:10:11 +0000290 // Rewrite the problematic successors for every block that wants to reach the
291 // bad blocks. For simplicity, we just introduce a new block for every edge
292 // we need to rewrite. (Fancier things are possible.)
293
294 SmallVector<MachineBasicBlock *, 4> AllPreds;
295 for (auto *MBB : SortedEntries) {
296 for (auto *Pred : MBB->predecessors()) {
297 if (Pred != Dispatch) {
298 AllPreds.push_back(Pred);
299 }
300 }
301 }
302
303 for (MachineBasicBlock *MBB : AllPreds) {
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000304 DenseMap<MachineBasicBlock *, MachineBasicBlock *> Map;
305 for (auto *Succ : MBB->successors()) {
Heejin Ahn777d01c2019-01-03 23:10:11 +0000306 if (!Entries.count(Succ)) {
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000307 continue;
Heejin Ahn777d01c2019-01-03 23:10:11 +0000308 }
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000309
Heejin Ahn777d01c2019-01-03 23:10:11 +0000310 // This is a successor we need to rewrite.
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000311 MachineBasicBlock *Split = MF.CreateMachineBasicBlock();
312 MF.insert(MBB->isLayoutSuccessor(Succ) ? MachineFunction::iterator(Succ)
313 : MF.end(),
314 Split);
315 MLI.changeLoopFor(Split, Loop);
316
317 // Set the jump table's register of the index of the block we wish to
318 // jump to, and jump to the jump table.
319 BuildMI(*Split, Split->end(), DebugLoc(), TII.get(WebAssembly::CONST_I32),
320 Reg)
321 .addImm(Indices[Succ]);
322 BuildMI(*Split, Split->end(), DebugLoc(), TII.get(WebAssembly::BR))
323 .addMBB(Dispatch);
324 Split->addSuccessor(Dispatch);
325 Map[Succ] = Split;
326 }
327 // Remap the terminator operands and the successor list.
328 for (MachineInstr &Term : MBB->terminators())
329 for (auto &Op : Term.explicit_uses())
330 if (Op.isMBB() && Indices.count(Op.getMBB()))
331 Op.setMBB(Map[Op.getMBB()]);
332 for (auto Rewrite : Map)
333 MBB->replaceSuccessor(Rewrite.first, Rewrite.second);
334 }
335
336 // Create a fake default label, because br_table requires one.
337 MIB.addMBB(MIB.getInstr()
338 ->getOperand(MIB.getInstr()->getNumExplicitOperands() - 1)
339 .getMBB());
340
341 return true;
342}
343
Heejin Ahn777d01c2019-01-03 23:10:11 +0000344class WebAssemblyFixIrreducibleControlFlow final : public MachineFunctionPass {
345 StringRef getPassName() const override {
346 return "WebAssembly Fix Irreducible Control Flow";
347 }
348
349 void getAnalysisUsage(AnalysisUsage &AU) const override {
350 AU.setPreservesCFG();
351 AU.addRequired<MachineDominatorTree>();
352 AU.addPreserved<MachineDominatorTree>();
353 AU.addRequired<MachineLoopInfo>();
354 AU.addPreserved<MachineLoopInfo>();
355 MachineFunctionPass::getAnalysisUsage(AU);
356 }
357
358 bool runOnMachineFunction(MachineFunction &MF) override;
359
360 bool runIteration(MachineFunction &MF, MachineLoopInfo &MLI) {
361 // Visit the function body, which is identified as a null loop.
362 if (LoopFixer(MF, MLI, nullptr).run()) {
363 return true;
364 }
365
366 // Visit all the loops.
367 SmallVector<MachineLoop *, 8> Worklist(MLI.begin(), MLI.end());
368 while (!Worklist.empty()) {
369 MachineLoop *Loop = Worklist.pop_back_val();
370 Worklist.append(Loop->begin(), Loop->end());
371 if (LoopFixer(MF, MLI, Loop).run()) {
372 return true;
373 }
374 }
375
376 return false;
377 }
378
379public:
380 static char ID; // Pass identification, replacement for typeid
381 WebAssemblyFixIrreducibleControlFlow() : MachineFunctionPass(ID) {}
382};
383} // end anonymous namespace
384
385char WebAssemblyFixIrreducibleControlFlow::ID = 0;
386INITIALIZE_PASS(WebAssemblyFixIrreducibleControlFlow, DEBUG_TYPE,
387 "Removes irreducible control flow", false, false)
388
389FunctionPass *llvm::createWebAssemblyFixIrreducibleControlFlow() {
390 return new WebAssemblyFixIrreducibleControlFlow();
391}
392
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000393bool WebAssemblyFixIrreducibleControlFlow::runOnMachineFunction(
394 MachineFunction &MF) {
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000395 LLVM_DEBUG(dbgs() << "********** Fixing Irreducible Control Flow **********\n"
396 "********** Function: "
397 << MF.getName() << '\n');
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000398
399 bool Changed = false;
400 auto &MLI = getAnalysis<MachineLoopInfo>();
401
Heejin Ahn777d01c2019-01-03 23:10:11 +0000402 // When we modify something, bail out and recompute MLI, then start again, as
403 // we create a new natural loop when we resolve irreducible control flow, and
404 // other loops may become nested in it, etc. In practice this is not an issue
405 // because irreducible control flow is rare, only very few cycles are needed
406 // here.
407 while (LLVM_UNLIKELY(runIteration(MF, MLI))) {
408 // We rewrote part of the function; recompute MLI and start again.
409 LLVM_DEBUG(dbgs() << "Recomputing loops.\n");
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000410 MF.getRegInfo().invalidateLiveness();
411 MF.RenumberBlocks();
412 getAnalysis<MachineDominatorTree>().runOnMachineFunction(MF);
413 MLI.runOnMachineFunction(MF);
Heejin Ahn777d01c2019-01-03 23:10:11 +0000414 Changed = true;
Dan Gohmand7a2eea2016-03-09 02:01:14 +0000415 }
416
417 return Changed;
418}