Repository: llvm/llvm-project
File: llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp (C++)

Code before:
///
/// \file
/// 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:
///
///   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
///
//===----------------------------------------------------------------------===//

#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"

Review comment (performance):
I'm actually not sure what the big-O time complexity ends up being then.

We calculate SCCs (which itself is `O(N+E)`) in each region at the start, then each time we encounter an irreducible SCC we fix it, then recalculate the SCCs (which will now have 1 - 3(?) additional blocks to process). We fix each irreducible loop found then recurse into the natural loops we find.

Code after:
///
/// \file
/// 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
///
//===----------------------------------------------------------------------===//

#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"
#include "WebAssemblySubtarget.h"
#include "llvm/ADT/SCCIterator.h"