llvm/llvm/lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow.cpp

//=- WebAssemblyFixIrreducibleControlFlow.cpp - Fix irreducible control flow -//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// \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 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
///
//===----------------------------------------------------------------------===//

#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"
usingnamespacellvm;

#define DEBUG_TYPE …

namespace {

BlockVector;
BlockSet;

static BlockVector getSortedEntries(const BlockSet &Entries) { … }

// Calculates reachability in a region. Ignores branches to blocks outside of
// the region, and ignores branches to the region entry (for the case where
// the region is the inner part of a loop).
class ReachabilityGraph { … };

// Finds the blocks in a single-entry loop, given the loop entry and the
// list of blocks that enter the loop.
class LoopBlocks { … };

class WebAssemblyFixIrreducibleControlFlow final : public MachineFunctionPass { … };

bool WebAssemblyFixIrreducibleControlFlow::processRegion(
    MachineBasicBlock *Entry, BlockSet &Blocks, MachineFunction &MF) { … }

// Given a set of entries to a single loop, create a single entry for that
// loop by creating a dispatch block for them, routing control flow using
// a helper variable. Also updates Blocks with any new blocks created, so
// that we properly track all the blocks in the region. But this does not update
// ReachabilityGraph; this will be updated in the caller of this function as
// needed.
void WebAssemblyFixIrreducibleControlFlow::makeSingleEntryLoop(
    BlockSet &Entries, BlockSet &Blocks, MachineFunction &MF,
    const ReachabilityGraph &Graph) { … }

} // end anonymous namespace

char WebAssemblyFixIrreducibleControlFlow::ID = …;
INITIALIZE_PASS(…)

FunctionPass *llvm::createWebAssemblyFixIrreducibleControlFlow() { … }

// Test whether the given register has an ARGUMENT def.
static bool hasArgumentDef(unsigned Reg, const MachineRegisterInfo &MRI) { … }

// Add a register definition with IMPLICIT_DEFs for every register to cover for
// register uses that don't have defs in every possible path.
// TODO: This is fairly heavy-handed; find a better approach.
static void addImplicitDefs(MachineFunction &MF) { … }

bool WebAssemblyFixIrreducibleControlFlow::runOnMachineFunction(
    MachineFunction &MF) { … }