llvm/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

//===-- WebAssemblyCFGStackify.cpp - CFG Stackification -------------------===//
//
// 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 CFG stacking pass.
///
/// This pass inserts BLOCK, LOOP, TRY, and TRY_TABLE markers to mark the start
/// of scopes, since scope boundaries serve as the labels for WebAssembly's
/// control transfers.
///
/// This is sufficient to convert arbitrary CFGs into a form that works on
/// WebAssembly, provided that all loops are single-entry.
///
/// In case we use exceptions, this pass also fixes mismatches in unwind
/// destinations created during transforming CFG into wasm structured format.
///
//===----------------------------------------------------------------------===//

#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "Utils/WebAssemblyTypeUtilities.h"
#include "WebAssembly.h"
#include "WebAssemblyExceptionInfo.h"
#include "WebAssemblyMachineFunctionInfo.h"
#include "WebAssemblySortRegion.h"
#include "WebAssemblySubtarget.h"
#include "WebAssemblyUtilities.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/BinaryFormat/Wasm.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/WasmEHFuncInfo.h"
#include "llvm/MC/MCAsmInfo.h"
#include "llvm/Target/TargetMachine.h"
usingnamespacellvm;
SortRegionInfo;

#define DEBUG_TYPE …

STATISTIC(NumCallUnwindMismatches, "Number of call unwind mismatches found");
STATISTIC(NumCatchUnwindMismatches, "Number of catch unwind mismatches found");

namespace {
class WebAssemblyCFGStackify final : public MachineFunctionPass { … };
} // end anonymous namespace

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

FunctionPass *llvm::createWebAssemblyCFGStackify() { … }

/// Test whether Pred has any terminators explicitly branching to MBB, as
/// opposed to falling through. Note that it's possible (eg. in unoptimized
/// code) for a branch instruction to both branch to a block and fallthrough
/// to it, so we check the actual branch operands to see if there are any
/// explicit mentions.
static bool explicitlyBranchesTo(MachineBasicBlock *Pred,
                                 MachineBasicBlock *MBB) { … }

// Returns an iterator to the earliest position possible within the MBB,
// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
// contains instructions that should go before the marker, and AfterSet contains
// ones that should go after the marker. In this function, AfterSet is only
// used for validation checking.
template <typename Container>
static MachineBasicBlock::iterator
getEarliestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet,
                     const Container &AfterSet) { … }

// Returns an iterator to the latest position possible within the MBB,
// satisfying the restrictions given by BeforeSet and AfterSet. BeforeSet
// contains instructions that should go before the marker, and AfterSet contains
// ones that should go after the marker. In this function, BeforeSet is only
// used for validation checking.
template <typename Container>
static MachineBasicBlock::iterator
getLatestInsertPos(MachineBasicBlock *MBB, const Container &BeforeSet,
                   const Container &AfterSet) { … }

void WebAssemblyCFGStackify::registerScope(MachineInstr *Begin,
                                           MachineInstr *End) { … }

// When 'End' is not an 'end_try' but a 'delegate', EHPad is nullptr.
void WebAssemblyCFGStackify::registerTryScope(MachineInstr *Begin,
                                              MachineInstr *End,
                                              MachineBasicBlock *EHPad) { … }

void WebAssemblyCFGStackify::unregisterScope(MachineInstr *Begin) { … }

/// Insert a BLOCK marker for branches to MBB (if needed).
// TODO Consider a more generalized way of handling block (and also loop and
// try) signatures when we implement the multi-value proposal later.
void WebAssemblyCFGStackify::placeBlockMarker(MachineBasicBlock &MBB) { … }

/// Insert a LOOP marker for a loop starting at MBB (if it's a loop header).
void WebAssemblyCFGStackify::placeLoopMarker(MachineBasicBlock &MBB) { … }

void WebAssemblyCFGStackify::placeTryMarker(MachineBasicBlock &MBB) { … }

void WebAssemblyCFGStackify::placeTryTableMarker(MachineBasicBlock &MBB) { … }

void WebAssemblyCFGStackify::removeUnnecessaryInstrs(MachineFunction &MF) { … }

// When MBB is split into MBB and Split, we should unstackify defs in MBB that
// have their uses in Split.
static void unstackifyVRegsUsedInSplitBB(MachineBasicBlock &MBB,
                                         MachineBasicBlock &Split) { … }

// Wrap the given range of instruction with try-delegate. RangeBegin and
// RangeEnd are inclusive.
void WebAssemblyCFGStackify::addNestedTryDelegate(
    MachineInstr *RangeBegin, MachineInstr *RangeEnd,
    MachineBasicBlock *UnwindDest) { … }

bool WebAssemblyCFGStackify::fixCallUnwindMismatches(MachineFunction &MF) { … }

bool WebAssemblyCFGStackify::fixCatchUnwindMismatches(MachineFunction &MF) { … }

void WebAssemblyCFGStackify::recalculateScopeTops(MachineFunction &MF) { … }

/// In normal assembly languages, when the end of a function is unreachable,
/// because the function ends in an infinite loop or a noreturn call or similar,
/// it isn't necessary to worry about the function return type at the end of
/// the function, because it's never reached. However, in WebAssembly, blocks
/// that end at the function end need to have a return type signature that
/// matches the function signature, even though it's unreachable. This function
/// checks for such cases and fixes up the signatures.
void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) { … }

// WebAssembly functions end with an end instruction, as if the function body
// were a block.
static void appendEndToFunction(MachineFunction &MF,
                                const WebAssemblyInstrInfo &TII) { … }

/// Insert BLOCK/LOOP/TRY/TRY_TABLE markers at appropriate places.
void WebAssemblyCFGStackify::placeMarkers(MachineFunction &MF) { … }

unsigned WebAssemblyCFGStackify::getBranchDepth(
    const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) { … }

unsigned WebAssemblyCFGStackify::getDelegateDepth(
    const SmallVectorImpl<EndMarkerInfo> &Stack, const MachineBasicBlock *MBB) { … }

unsigned WebAssemblyCFGStackify::getRethrowDepth(
    const SmallVectorImpl<EndMarkerInfo> &Stack,
    const SmallVectorImpl<const MachineBasicBlock *> &EHPadStack) { … }

void WebAssemblyCFGStackify::rewriteDepthImmediates(MachineFunction &MF) { … }

void WebAssemblyCFGStackify::cleanupFunctionData(MachineFunction &MF) { … }

void WebAssemblyCFGStackify::releaseMemory() { … }

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