LLVM  10.0.0svn
Macros | Functions
WebAssemblyFixIrreducibleControlFlow.cpp File Reference

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

#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"
#include "WebAssemblySubtarget.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/Support/Debug.h"
Include dependency graph for WebAssemblyFixIrreducibleControlFlow.cpp:

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 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:

[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 62 of file WebAssemblyFixIrreducibleControlFlow.cpp.

Function Documentation

◆ INITIALIZE_PASS()

INITIALIZE_PASS ( WebAssemblyFixIrreducibleControlFlow  ,
DEBUG_TYPE  ,
"Removes irreducible control flow"  ,
false  ,
false   
)