TailDuplicator.cpp | Explore in Territory

//===- TailDuplicator.cpp - Duplicate blocks into predecessors' tails -----===//
//
// 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 utility class duplicates basic blocks ending in unconditional branches
// into the tails of their predecessors.
//
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/TailDuplicator.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/MachineSSAUpdater.h"
#include "llvm/CodeGen/MachineSizeOpts.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.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 <algorithm>
#include <cassert>
#include <iterator>
#include <utility>

usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumTails, "Number of tails duplicated");
STATISTIC(NumTailDups, "Number of tail duplicated blocks");
STATISTIC(NumTailDupAdded,
          "Number of instructions added due to tail duplication");
STATISTIC(NumTailDupRemoved,
          "Number of instructions removed due to tail duplication");
STATISTIC(NumDeadBlocks, "Number of dead blocks removed");
STATISTIC(NumAddedPHIs, "Number of phis added");

// Heuristic for tail duplication.
static cl::opt<unsigned> TailDuplicateSize(
    "tail-dup-size",
    cl::desc("Maximum instructions to consider tail duplicating"), cl::init(2),
    cl::Hidden);

static cl::opt<unsigned> TailDupIndirectBranchSize(
    "tail-dup-indirect-size",
    cl::desc("Maximum instructions to consider tail duplicating blocks that "
             "end with indirect branches."), cl::init(20),
    cl::Hidden);

static cl::opt<unsigned>
    TailDupPredSize("tail-dup-pred-size",
                    cl::desc("Maximum predecessors (maximum successors at the "
                             "same time) to consider tail duplicating blocks."),
                    cl::init(16), cl::Hidden);

static cl::opt<unsigned>
    TailDupSuccSize("tail-dup-succ-size",
                    cl::desc("Maximum successors (maximum predecessors at the "
                             "same time) to consider tail duplicating blocks."),
                    cl::init(16), cl::Hidden);

static cl::opt<bool>
    TailDupVerify("tail-dup-verify",
                  cl::desc("Verify sanity of PHI instructions during taildup"),
                  cl::init(false), cl::Hidden);

static cl::opt<unsigned> TailDupLimit("tail-dup-limit", cl::init(~0U),
                                      cl::Hidden);

void TailDuplicator::initMF(MachineFunction &MFin, bool PreRegAlloc,
                            const MachineBranchProbabilityInfo *MBPIin,
                            MBFIWrapper *MBFIin,
                            ProfileSummaryInfo *PSIin,
                            bool LayoutModeIn, unsigned TailDupSizeIn) { … }

static void VerifyPHIs(MachineFunction &MF, bool CheckExtra) { … }

/// Tail duplicate the block and cleanup.
/// \p IsSimple - return value of isSimpleBB
/// \p MBB - block to be duplicated
/// \p ForcedLayoutPred - If non-null, treat this block as the layout
///     predecessor, instead of using the ordering in MF
/// \p DuplicatedPreds - if non-null, \p DuplicatedPreds will contain a list of
///     all Preds that received a copy of \p MBB.
/// \p RemovalCallback - if non-null, called just before MBB is deleted.
bool TailDuplicator::tailDuplicateAndUpdate(
    bool IsSimple, MachineBasicBlock *MBB,
    MachineBasicBlock *ForcedLayoutPred,
    SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds,
    function_ref<void(MachineBasicBlock *)> *RemovalCallback,
    SmallVectorImpl<MachineBasicBlock *> *CandidatePtr) { … }

/// Look for small blocks that are unconditionally branched to and do not fall
/// through. Tail-duplicate their instructions into their predecessors to
/// eliminate (dynamic) branches.
bool TailDuplicator::tailDuplicateBlocks() { … }

static bool isDefLiveOut(Register Reg, MachineBasicBlock *BB,
                         const MachineRegisterInfo *MRI) { … }

static unsigned getPHISrcRegOpIdx(MachineInstr *MI, MachineBasicBlock *SrcBB) { … }

// Remember which registers are used by phis in this block. This is
// used to determine which registers are liveout while modifying the
// block (which is why we need to copy the information).
static void getRegsUsedByPHIs(const MachineBasicBlock &BB,
                              DenseSet<Register> *UsedByPhi) { … }

/// Add a definition and source virtual registers pair for SSA update.
void TailDuplicator::addSSAUpdateEntry(Register OrigReg, Register NewReg,
                                       MachineBasicBlock *BB) { … }

/// Process PHI node in TailBB by turning it into a copy in PredBB. Remember the
/// source register that's contributed by PredBB and update SSA update map.
void TailDuplicator::processPHI(
    MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB,
    DenseMap<Register, RegSubRegPair> &LocalVRMap,
    SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies,
    const DenseSet<Register> &RegsUsedByPhi, bool Remove) { … }

/// Duplicate a TailBB instruction to PredBB and update
/// the source operands due to earlier PHI translation.
void TailDuplicator::duplicateInstruction(
    MachineInstr *MI, MachineBasicBlock *TailBB, MachineBasicBlock *PredBB,
    DenseMap<Register, RegSubRegPair> &LocalVRMap,
    const DenseSet<Register> &UsedByPhi) { … }

/// After FromBB is tail duplicated into its predecessor blocks, the successors
/// have gained new predecessors. Update the PHI instructions in them
/// accordingly.
void TailDuplicator::updateSuccessorsPHIs(
    MachineBasicBlock *FromBB, bool isDead,
    SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    SmallSetVector<MachineBasicBlock *, 8> &Succs) { … }

/// Determine if it is profitable to duplicate this block.
bool TailDuplicator::shouldTailDuplicate(bool IsSimple,
                                         MachineBasicBlock &TailBB) { … }

/// True if this BB has only one unconditional jump.
bool TailDuplicator::isSimpleBB(MachineBasicBlock *TailBB) { … }

static bool bothUsedInPHI(const MachineBasicBlock &A,
                          const SmallPtrSet<MachineBasicBlock *, 8> &SuccsB) { … }

bool TailDuplicator::canCompletelyDuplicateBB(MachineBasicBlock &BB) { … }

bool TailDuplicator::duplicateSimpleBB(
    MachineBasicBlock *TailBB, SmallVectorImpl<MachineBasicBlock *> &TDBBs,
    const DenseSet<Register> &UsedByPhi) { … }

bool TailDuplicator::canTailDuplicate(MachineBasicBlock *TailBB,
                                      MachineBasicBlock *PredBB) { … }

/// If it is profitable, duplicate TailBB's contents in each
/// of its predecessors.
/// \p IsSimple result of isSimpleBB
/// \p TailBB   Block to be duplicated.
/// \p ForcedLayoutPred  When non-null, use this block as the layout predecessor
///                      instead of the previous block in MF's order.
/// \p TDBBs             A vector to keep track of all blocks tail-duplicated
///                      into.
/// \p Copies            A vector of copy instructions inserted. Used later to
///                      walk all the inserted copies and remove redundant ones.
bool TailDuplicator::tailDuplicate(bool IsSimple, MachineBasicBlock *TailBB,
                          MachineBasicBlock *ForcedLayoutPred,
                          SmallVectorImpl<MachineBasicBlock *> &TDBBs,
                          SmallVectorImpl<MachineInstr *> &Copies,
                          SmallVectorImpl<MachineBasicBlock *> *CandidatePtr) { … }

/// At the end of the block \p MBB generate COPY instructions between registers
/// described by \p CopyInfos. Append resulting instructions to \p Copies.
void TailDuplicator::appendCopies(MachineBasicBlock *MBB,
      SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
      SmallVectorImpl<MachineInstr*> &Copies) { … }

/// Remove the specified dead machine basic block from the function, updating
/// the CFG.
void TailDuplicator::removeDeadBlock(
    MachineBasicBlock *MBB,
    function_ref<void(MachineBasicBlock *)> *RemovalCallback) { … }
llvm/llvm/lib/CodeGen/TailDuplicator.cpp
