This file implements a pass that transforms irreducible control flow into reducible control flow. More...
#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"#include "WebAssembly.h"#include "WebAssemblyMachineFunctionInfo.h"#include "WebAssemblySubtarget.h"#include "llvm/ADT/PriorityQueue.h"#include "llvm/ADT/SCCIterator.h"#include "llvm/ADT/SetVector.h"#include "llvm/CodeGen/MachineDominators.h"#include "llvm/CodeGen/MachineFunction.h"#include "llvm/CodeGen/MachineInstrBuilder.h"#include "llvm/CodeGen/MachineLoopInfo.h"#include "llvm/CodeGen/MachineRegisterInfo.h"#include "llvm/CodeGen/Passes.h"#include "llvm/Support/Debug.h"#include "llvm/Support/raw_ostream.h"
Go to the source code of this file.
Macros | |
| #define | DEBUG_TYPE "wasm-fix-irreducible-control-flow" |
Functions | |
| INITIALIZE_PASS (WebAssemblyFixIrreducibleControlFlow, DEBUG_TYPE, "Removes irreducible control flow", false, false) FunctionPass *llvm | |
Detailed Description
This file implements a pass that transforms irreducible control flow into reducible control flow.
Irreducible control flow means multiple-entry loops; they appear as CFG cycles that are not recorded in MachineLoopInfo due to being unnatural.
Note that LLVM has a generic pass that lowers irreducible control flow, but it linearizes control flow, turning diamonds into two triangles, which is both unnecessary and undesirable for WebAssembly.
The big picture: Ignoring natural loops (seeing them monolithically), we find all the blocks which can return to themselves ("loopers"). Loopers reachable from the non-loopers are loop entries: if there are 2 or more, then we have irreducible control flow. We fix that as follows: a new block is created that can dispatch to each of the loop entries, based on the value of a label "helper" variable, and we replace direct branches to the entries with assignments to the label variable and a branch to the dispatch block. Then the dispatch block is the single entry in a new natural loop.
This is similar to what the Relooper [1] does, both identify looping code that requires multiple entries, and resolve it in a similar way. In Relooper terminology, we implement a Multiple shape in a Loop shape. Note also that like the Relooper, we implement a "minimal" intervention: we only use the "label" helper for the blocks we absolutely must and no others. We also prioritize code size and do not perform node splitting (i.e. we don't duplicate code in order to resolve irreducibility).
The difference between this code and the Relooper is that the Relooper also generates ifs and loops and works in a recursive manner, knowing at each point what the entries are, and recursively breaks down the problem. Here we just want to resolve irreducible control flow, and we also want to use as much LLVM infrastructure as possible. So we use the MachineLoopInfo to identify natural loops, etc., and we start with the whole CFG and must identify both the looping code and its entries.
[1] Alon Zakai. 2011. Emscripten: an LLVM-to-JavaScript compiler. In Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion (SPLASH '11). ACM, New York, NY, USA, 301-312. DOI=10.1145/2048147.2048224 http://doi.acm.org/10.1145/2048147.2048224
Definition in file WebAssemblyFixIrreducibleControlFlow.cpp.
Macro Definition Documentation
◆ DEBUG_TYPE
| #define DEBUG_TYPE "wasm-fix-irreducible-control-flow" |
Definition at line 70 of file WebAssemblyFixIrreducibleControlFlow.cpp.
Function Documentation
◆ INITIALIZE_PASS()
| INITIALIZE_PASS | ( | WebAssemblyFixIrreducibleControlFlow | , |
| DEBUG_TYPE | , | ||
| "Removes irreducible control flow" | , | ||
| false | , | ||
| false | |||
| ) |
Definition at line 397 of file WebAssemblyFixIrreducibleControlFlow.cpp.
References llvm::dbgs(), llvm::MachineFunction::getName(), llvm::MachineFunction::getRegInfo(), llvm::MachineRegisterInfo::invalidateLiveness(), LLVM_DEBUG, LLVM_UNLIKELY, and llvm::MachineFunction::RenumberBlocks().
