llvm/llvm/lib/Target/WebAssembly/WebAssemblyCFGSort.cpp

//===-- WebAssemblyCFGSort.cpp - CFG Sorting ------------------------------===//
//
// 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 sorting pass.
///
/// This pass reorders the blocks in a function to put them into topological
/// order, ignoring loop backedges, and without any loop or exception being
/// interrupted by a block not dominated by the its header, with special care
/// to keep the order as similar as possible to the original order.
///
////===----------------------------------------------------------------------===//

#include "MCTargetDesc/WebAssemblyMCTargetDesc.h"
#include "WebAssembly.h"
#include "WebAssemblyExceptionInfo.h"
#include "WebAssemblySortRegion.h"
#include "WebAssemblySubtarget.h"
#include "WebAssemblyUtilities.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/WasmEHFuncInfo.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
usingnamespacellvm;
SortRegion;
SortRegionInfo;

#define DEBUG_TYPE …

// Option to disable EH pad first sorting. Only for testing unwind destination
// mismatches in CFGStackify.
static cl::opt<bool> WasmDisableEHPadSort(
    "wasm-disable-ehpad-sort", cl::ReallyHidden,
    cl::desc(
        "WebAssembly: Disable EH pad-first sort order. Testing purpose only."),
    cl::init(false));

namespace {

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

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

FunctionPass *llvm::createWebAssemblyCFGSort() { … }

static void maybeUpdateTerminator(MachineBasicBlock *MBB) { … }

namespace {
// EH pads are selected first regardless of the block comparison order.
// When only one of the BBs is an EH pad, we give a higher priority to it, to
// prevent common mismatches between possibly throwing calls and ehpads they
// unwind to, as in the example below:
//
// bb0:
//   call @foo      // If this throws, unwind to bb2
// bb1:
//   call @bar      // If this throws, unwind to bb3
// bb2 (ehpad):
//   handler_bb2
// bb3 (ehpad):
//   handler_bb3
// continuing code
//
// Because this pass tries to preserve the original BB order, this order will
// not change. But this will result in this try-catch structure in CFGStackify,
// resulting in a mismatch:
// try
//   try
//     call @foo
//     call @bar    // This should unwind to bb3, not bb2!
//   catch
//     handler_bb2
//   end
// catch
//   handler_bb3
// end
// continuing code
//
// If we give a higher priority to an EH pad whenever it is ready in this
// example, when both bb1 and bb2 are ready, we would pick up bb2 first.

/// Sort blocks by their number.
struct CompareBlockNumbers { … };
/// Sort blocks by their number in the opposite order..
struct CompareBlockNumbersBackwards { … };
/// Bookkeeping for a region to help ensure that we don't mix blocks not
/// dominated by the its header among its blocks.
struct Entry { … };
} // end anonymous namespace

/// Sort the blocks, taking special care to make sure that regions are not
/// interrupted by blocks not dominated by their header.
/// TODO: There are many opportunities for improving the heuristics here.
/// Explore them.
static void sortBlocks(MachineFunction &MF, const MachineLoopInfo &MLI,
                       const WebAssemblyExceptionInfo &WEI,
                       MachineDominatorTree &MDT) { … }

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