BranchFolding.cpp | Explore in Territory

//===- BranchFolding.cpp - Fold machine code branch instructions ----------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This pass forwards branches to unconditional branches to make them branch
// directly to the target block.  This pass often results in dead MBB's, which
// it then removes.
//
// Note that this pass must be run after register allocation, it cannot handle
// SSA form. It also must handle virtual registers for targets that emit virtual
// ISA (e.g. NVPTX).
//
//===----------------------------------------------------------------------===//

#include "BranchFolding.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/CodeGen/Analysis.h"
#include "llvm/CodeGen/MBFIWrapper.h"
#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MachineSizeOpts.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugInfoMetadata.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include <cassert>
#include <cstddef>
#include <iterator>
#include <numeric>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
STATISTIC(NumBranchOpts, "Number of branches optimized");
STATISTIC(NumTailMerge , "Number of block tails merged");
STATISTIC(NumHoist     , "Number of times common instructions are hoisted");
STATISTIC(NumTailCalls,  "Number of tail calls optimized");

static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge",
                              cl::init(cl::BOU_UNSET), cl::Hidden);

// Throttle for huge numbers of predecessors (compile speed problems)
static cl::opt<unsigned>
TailMergeThreshold("tail-merge-threshold",
          cl::desc("Max number of predecessors to consider tail merging"),
          cl::init(150), cl::Hidden);

// Heuristic for tail merging (and, inversely, tail duplication).
static cl::opt<unsigned>
TailMergeSize("tail-merge-size",
              cl::desc("Min number of instructions to consider tail merging"),
              cl::init(3), cl::Hidden);

namespace {

  /// BranchFolderPass - Wrap branch folder in a machine function pass.
  class BranchFolderPass : public MachineFunctionPass { … };

} // end anonymous namespace

char BranchFolderPass::ID = …;

char &llvm::BranchFolderPassID = …;

INITIALIZE_PASS(…)

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

BranchFolder::BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist,
                           MBFIWrapper &FreqInfo,
                           const MachineBranchProbabilityInfo &ProbInfo,
                           ProfileSummaryInfo *PSI, unsigned MinTailLength)
    : … { … }

void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { … }

bool BranchFolder::OptimizeFunction(MachineFunction &MF,
                                    const TargetInstrInfo *tii,
                                    const TargetRegisterInfo *tri,
                                    MachineLoopInfo *mli, bool AfterPlacement) { … }

//===----------------------------------------------------------------------===//
//  Tail Merging of Blocks
//===----------------------------------------------------------------------===//

/// HashMachineInstr - Compute a hash value for MI and its operands.
static unsigned HashMachineInstr(const MachineInstr &MI) { … }

/// HashEndOfMBB - Hash the last instruction in the MBB.
static unsigned HashEndOfMBB(const MachineBasicBlock &MBB) { … }

/// Whether MI should be counted as an instruction when calculating common tail.
static bool countsAsInstruction(const MachineInstr &MI) { … }

/// Iterate backwards from the given iterator \p I, towards the beginning of the
/// block. If a MI satisfying 'countsAsInstruction' is found, return an iterator
/// pointing to that MI. If no such MI is found, return the end iterator.
static MachineBasicBlock::iterator
skipBackwardPastNonInstructions(MachineBasicBlock::iterator I,
                                MachineBasicBlock *MBB) { … }

/// Given two machine basic blocks, return the number of instructions they
/// actually have in common together at their end. If a common tail is found (at
/// least by one instruction), then iterators for the first shared instruction
/// in each block are returned as well.
///
/// Non-instructions according to countsAsInstruction are ignored.
static unsigned ComputeCommonTailLength(MachineBasicBlock *MBB1,
                                        MachineBasicBlock *MBB2,
                                        MachineBasicBlock::iterator &I1,
                                        MachineBasicBlock::iterator &I2) { … }

void BranchFolder::replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
                                           MachineBasicBlock &NewDest) { … }

MachineBasicBlock *BranchFolder::SplitMBBAt(MachineBasicBlock &CurMBB,
                                            MachineBasicBlock::iterator BBI1,
                                            const BasicBlock *BB) { … }

/// EstimateRuntime - Make a rough estimate for how long it will take to run
/// the specified code.
static unsigned EstimateRuntime(MachineBasicBlock::iterator I,
                                MachineBasicBlock::iterator E) { … }

// CurMBB needs to add an unconditional branch to SuccMBB (we removed these
// branches temporarily for tail merging).  In the case where CurMBB ends
// with a conditional branch to the next block, optimize by reversing the
// test and conditionally branching to SuccMBB instead.
static void FixTail(MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB,
                    const TargetInstrInfo *TII, const DebugLoc &BranchDL) { … }

bool
BranchFolder::MergePotentialsElt::operator<(const MergePotentialsElt &o) const { … }

/// CountTerminators - Count the number of terminators in the given
/// block and set I to the position of the first non-terminator, if there
/// is one, or MBB->end() otherwise.
static unsigned CountTerminators(MachineBasicBlock *MBB,
                                 MachineBasicBlock::iterator &I) { … }

/// A no successor, non-return block probably ends in unreachable and is cold.
/// Also consider a block that ends in an indirect branch to be a return block,
/// since many targets use plain indirect branches to return.
static bool blockEndsInUnreachable(const MachineBasicBlock *MBB) { … }

/// ProfitableToMerge - Check if two machine basic blocks have a common tail
/// and decide if it would be profitable to merge those tails.  Return the
/// length of the common tail and iterators to the first common instruction
/// in each block.
/// MBB1, MBB2      The blocks to check
/// MinCommonTailLength  Minimum size of tail block to be merged.
/// CommonTailLen   Out parameter to record the size of the shared tail between
///                 MBB1 and MBB2
/// I1, I2          Iterator references that will be changed to point to the first
///                 instruction in the common tail shared by MBB1,MBB2
/// SuccBB          A common successor of MBB1, MBB2 which are in a canonical form
///                 relative to SuccBB
/// PredBB          The layout predecessor of SuccBB, if any.
/// EHScopeMembership  map from block to EH scope #.
/// AfterPlacement  True if we are merging blocks after layout. Stricter
///                 thresholds apply to prevent undoing tail-duplication.
static bool
ProfitableToMerge(MachineBasicBlock *MBB1, MachineBasicBlock *MBB2,
                  unsigned MinCommonTailLength, unsigned &CommonTailLen,
                  MachineBasicBlock::iterator &I1,
                  MachineBasicBlock::iterator &I2, MachineBasicBlock *SuccBB,
                  MachineBasicBlock *PredBB,
                  DenseMap<const MachineBasicBlock *, int> &EHScopeMembership,
                  bool AfterPlacement,
                  MBFIWrapper &MBBFreqInfo,
                  ProfileSummaryInfo *PSI) { … }

unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
                                        unsigned MinCommonTailLength,
                                        MachineBasicBlock *SuccBB,
                                        MachineBasicBlock *PredBB) { … }

void BranchFolder::RemoveBlocksWithHash(unsigned CurHash,
                                        MachineBasicBlock *SuccBB,
                                        MachineBasicBlock *PredBB,
                                        const DebugLoc &BranchDL) { … }

bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
                                             MachineBasicBlock *SuccBB,
                                             unsigned maxCommonTailLength,
                                             unsigned &commonTailIndex) { … }

static void
mergeOperations(MachineBasicBlock::iterator MBBIStartPos,
                MachineBasicBlock &MBBCommon) { … }

void BranchFolder::mergeCommonTails(unsigned commonTailIndex) { … }

// See if any of the blocks in MergePotentials (which all have SuccBB as a
// successor, or all have no successor if it is null) can be tail-merged.
// If there is a successor, any blocks in MergePotentials that are not
// tail-merged and are not immediately before Succ must have an unconditional
// branch to Succ added (but the predecessor/successor lists need no
// adjustment). The lone predecessor of Succ that falls through into Succ,
// if any, is given in PredBB.
// MinCommonTailLength - Except for the special cases below, tail-merge if
// there are at least this many instructions in common.
bool BranchFolder::TryTailMergeBlocks(MachineBasicBlock *SuccBB,
                                      MachineBasicBlock *PredBB,
                                      unsigned MinCommonTailLength) { … }

bool BranchFolder::TailMergeBlocks(MachineFunction &MF) { … }

void BranchFolder::setCommonTailEdgeWeights(MachineBasicBlock &TailMBB) { … }

//===----------------------------------------------------------------------===//
//  Branch Optimization
//===----------------------------------------------------------------------===//

bool BranchFolder::OptimizeBranches(MachineFunction &MF) { … }

// Blocks should be considered empty if they contain only debug info;
// else the debug info would affect codegen.
static bool IsEmptyBlock(MachineBasicBlock *MBB) { … }

// Blocks with only debug info and branches should be considered the same
// as blocks with only branches.
static bool IsBranchOnlyBlock(MachineBasicBlock *MBB) { … }

/// IsBetterFallthrough - Return true if it would be clearly better to
/// fall-through to MBB1 than to fall through into MBB2.  This has to return
/// a strict ordering, returning true for both (MBB1,MBB2) and (MBB2,MBB1) will
/// result in infinite loops.
static bool IsBetterFallthrough(MachineBasicBlock *MBB1,
                                MachineBasicBlock *MBB2) { … }

/// getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch
/// instructions on the block.
static DebugLoc getBranchDebugLoc(MachineBasicBlock &MBB) { … }

static void copyDebugInfoToPredecessor(const TargetInstrInfo *TII,
                                       MachineBasicBlock &MBB,
                                       MachineBasicBlock &PredMBB) { … }

static void copyDebugInfoToSuccessor(const TargetInstrInfo *TII,
                                     MachineBasicBlock &MBB,
                                     MachineBasicBlock &SuccMBB) { … }

// Try to salvage DBG_VALUE instructions from an otherwise empty block. If such
// a basic block is removed we would lose the debug information unless we have
// copied the information to a predecessor/successor.
//
// TODO: This function only handles some simple cases. An alternative would be
// to run a heavier analysis, such as the LiveDebugValues pass, before we do
// branch folding.
static void salvageDebugInfoFromEmptyBlock(const TargetInstrInfo *TII,
                                           MachineBasicBlock &MBB) { … }

bool BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) { … }

//===----------------------------------------------------------------------===//
//  Hoist Common Code
//===----------------------------------------------------------------------===//

bool BranchFolder::HoistCommonCode(MachineFunction &MF) { … }

/// findFalseBlock - BB has a fallthrough. Find its 'false' successor given
/// its 'true' successor.
static MachineBasicBlock *findFalseBlock(MachineBasicBlock *BB,
                                         MachineBasicBlock *TrueBB) { … }

template <class Container>
static void addRegAndItsAliases(Register Reg, const TargetRegisterInfo *TRI,
                                Container &Set) { … }

/// findHoistingInsertPosAndDeps - Find the location to move common instructions
/// in successors to. The location is usually just before the terminator,
/// however if the terminator is a conditional branch and its previous
/// instruction is the flag setting instruction, the previous instruction is
/// the preferred location. This function also gathers uses and defs of the
/// instructions from the insertion point to the end of the block. The data is
/// used by HoistCommonCodeInSuccs to ensure safety.
static
MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
                                                  const TargetInstrInfo *TII,
                                                  const TargetRegisterInfo *TRI,
                                                  SmallSet<Register, 4> &Uses,
                                                  SmallSet<Register, 4> &Defs) { … }

bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) { … }
llvm/llvm/lib/CodeGen/BranchFolding.cpp
