Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 1 | //=- 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 Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 11 | /// This file implements a pass that transforms irreducible control flow into |
| 12 | /// reducible control flow. Irreducible control flow means multiple-entry |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 13 | /// loops; they appear as CFG cycles that are not recorded in MachineLoopInfo |
| 14 | /// due to being unnatural. |
| 15 | /// |
Dan Gohman | ddfa1a6 | 2016-03-09 04:17:36 +0000 | [diff] [blame] | 16 | /// 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 Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 20 | /// 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 Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 50 | /// |
| 51 | //===----------------------------------------------------------------------===// |
| 52 | |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 53 | #include "MCTargetDesc/WebAssemblyMCTargetDesc.h" |
Chandler Carruth | 6bda14b | 2017-06-06 11:49:48 +0000 | [diff] [blame] | 54 | #include "WebAssembly.h" |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 55 | #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" |
| 68 | using namespace llvm; |
| 69 | |
| 70 | #define DEBUG_TYPE "wasm-fix-irreducible-control-flow" |
| 71 | |
| 72 | namespace { |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 73 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 74 | class LoopFixer { |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 75 | public: |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 76 | LoopFixer(MachineFunction &MF, MachineLoopInfo &MLI, MachineLoop *Loop) |
| 77 | : MF(MF), MLI(MLI), Loop(Loop) {} |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 78 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 79 | // Run the fixer on the given inputs. Returns whether changes were made. |
| 80 | bool run(); |
Jacob Gravelle | 4092645 | 2018-03-30 20:36:58 +0000 | [diff] [blame] | 81 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 82 | private: |
| 83 | MachineFunction &MF; |
| 84 | MachineLoopInfo &MLI; |
| 85 | MachineLoop *Loop; |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 86 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 87 | MachineBasicBlock *Header; |
| 88 | SmallPtrSet<MachineBasicBlock *, 4> LoopBlocks; |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 89 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 90 | using BlockSet = SmallPtrSet<MachineBasicBlock *, 4>; |
| 91 | DenseMap<MachineBasicBlock *, BlockSet> Reachable; |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 92 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 93 | // 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 Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 97 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 98 | // 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 Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 110 | } |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 111 | assert(InnerLoop); |
| 112 | // It's in an inner loop, canonicalize it to the header of that loop. |
| 113 | return InnerLoop->getHeader(); |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 114 | } |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 115 | } |
| 116 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 117 | // 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 | |
| 151 | bool 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 Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 246 | return false; |
| 247 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 248 | // 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 Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 257 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 258 | // Create a dispatch block which will contain a jump table to the entries. |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 259 | 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 Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 274 | // Compute the indices in the superheader, one for each bad block, and |
| 275 | // add them as successors. |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 276 | DenseMap<MachineBasicBlock *, unsigned> Indices; |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 277 | for (auto *MBB : SortedEntries) { |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 278 | auto Pair = Indices.insert(std::make_pair(MBB, 0)); |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 279 | if (!Pair.second) { |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 280 | continue; |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 281 | } |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 282 | |
Dan Gohman | f456290 | 2016-04-26 01:40:56 +0000 | [diff] [blame] | 283 | unsigned Index = MIB.getInstr()->getNumExplicitOperands() - 1; |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 284 | Pair.first->second = Index; |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 285 | |
| 286 | MIB.addMBB(MBB); |
| 287 | Dispatch->addSuccessor(MBB); |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 288 | } |
| 289 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 290 | // 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 Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 304 | DenseMap<MachineBasicBlock *, MachineBasicBlock *> Map; |
| 305 | for (auto *Succ : MBB->successors()) { |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 306 | if (!Entries.count(Succ)) { |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 307 | continue; |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 308 | } |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 309 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 310 | // This is a successor we need to rewrite. |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 311 | 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 Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 344 | class 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 | |
| 379 | public: |
| 380 | static char ID; // Pass identification, replacement for typeid |
| 381 | WebAssemblyFixIrreducibleControlFlow() : MachineFunctionPass(ID) {} |
| 382 | }; |
| 383 | } // end anonymous namespace |
| 384 | |
| 385 | char WebAssemblyFixIrreducibleControlFlow::ID = 0; |
| 386 | INITIALIZE_PASS(WebAssemblyFixIrreducibleControlFlow, DEBUG_TYPE, |
| 387 | "Removes irreducible control flow", false, false) |
| 388 | |
| 389 | FunctionPass *llvm::createWebAssemblyFixIrreducibleControlFlow() { |
| 390 | return new WebAssemblyFixIrreducibleControlFlow(); |
| 391 | } |
| 392 | |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 393 | bool WebAssemblyFixIrreducibleControlFlow::runOnMachineFunction( |
| 394 | MachineFunction &MF) { |
Nicola Zaghen | d34e60c | 2018-05-14 12:53:11 +0000 | [diff] [blame] | 395 | LLVM_DEBUG(dbgs() << "********** Fixing Irreducible Control Flow **********\n" |
| 396 | "********** Function: " |
| 397 | << MF.getName() << '\n'); |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 398 | |
| 399 | bool Changed = false; |
| 400 | auto &MLI = getAnalysis<MachineLoopInfo>(); |
| 401 | |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 402 | // 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 Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 410 | MF.getRegInfo().invalidateLiveness(); |
| 411 | MF.RenumberBlocks(); |
| 412 | getAnalysis<MachineDominatorTree>().runOnMachineFunction(MF); |
| 413 | MLI.runOnMachineFunction(MF); |
Heejin Ahn | 777d01c | 2019-01-03 23:10:11 +0000 | [diff] [blame^] | 414 | Changed = true; |
Dan Gohman | d7a2eea | 2016-03-09 02:01:14 +0000 | [diff] [blame] | 415 | } |
| 416 | |
| 417 | return Changed; |
| 418 | } |