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

#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"
#include "WebAssemblySubtarget.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/Support/Debug.h"

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 fix up multi-entry loops 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. After ensuring all the loops in a region are reducible, we recurse into them. The total time complexity of this pass is:

O(NumBlocks * NumNestedLoops * NumIrreducibleLoops + NumLoops * NumLoops)

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.