This file implements a pass that removes irreducible control flow. More...

#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"
#include "WebAssemblySubtarget.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/Support/Debug.h"
#include <limits>

Classes
struct	llvm::GraphTraits< ReachabilityGraph * >

Namespaces
namespace	llvm
	This is an optimization pass for GlobalISel generic memory operations.

Macros
#define	DEBUG_TYPE "wasm-fix-irreducible-control-flow"

Functions
	INITIALIZE_PASS (WebAssemblyFixIrreducibleControlFlow, DEBUG_TYPE, "Removes irreducible control flow", false, false) FunctionPass *llvm
static bool	hasArgumentDef (unsigned Reg, const MachineRegisterInfo &MRI)
static void	addImplicitDefs (MachineFunction &MF)

Detailed Description

This file implements a pass that removes irreducible control flow.

Irreducible control flow means multiple-entry loops, which this pass transforms to have a single entry.

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: We recursively process each "region", defined as a group of blocks with a single entry and no branches back to that entry. A region may be the entire function body, or the inner part of a loop, i.e., the loop's body without branches back to the loop entry. In each region we identify all the strongly-connected components (SCCs). We fix up multi-entry loops (SCCs) by adding a new block 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 the loop containing the previous multiple entries. Each time we fix some irreducibility, we recalculate the SCCs. After ensuring all the SCCs in a region are reducible, we recurse into them. The total time complexity of this pass is roughly: O((NumBlocks + NumEdges) * (NumNestedLoops + NumIrreducibleLoops))

This pass 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 duplicate code in order to resolve irreducibility. The graph algorithms for finding loops and entries and so forth are also similar to the Relooper. The main differences between this pass and the Relooper are:

We just care about irreducibility, so we just look at loops.
The Relooper emits structured control flow (with ifs etc.), while we emit a CFG.

[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.