IfConversion.cpp | Explore in Territory

//===- IfConversion.cpp - Machine code if conversion pass -----------------===//
//
// 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 file implements the machine instruction level if-conversion pass, which
// tries to convert conditional branches into predicated instructions.
//
//===----------------------------------------------------------------------===//

#include "BranchFolding.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/ScopeExit.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SparseSet.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/ProfileSummaryInfo.h"
#include "llvm/CodeGen/LivePhysRegs.h"
#include "llvm/CodeGen/MBFIWrapper.h"
#include "llvm/CodeGen/MachineBasicBlock.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/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.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 <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <memory>
#include <utility>
#include <vector>

usingnamespacellvm;

#define DEBUG_TYPE …

// Hidden options for help debugging.
static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
static cl::opt<bool> DisableSimple("disable-ifcvt-simple",
                                   cl::init(false), cl::Hidden);
static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false",
                                    cl::init(false), cl::Hidden);
static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle",
                                     cl::init(false), cl::Hidden);
static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev",
                                      cl::init(false), cl::Hidden);
static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false",
                                      cl::init(false), cl::Hidden);
static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",
                                    cl::init(false), cl::Hidden);
static cl::opt<bool> DisableForkedDiamond("disable-ifcvt-forked-diamond",
                                        cl::init(false), cl::Hidden);
static cl::opt<bool> IfCvtBranchFold("ifcvt-branch-fold",
                                     cl::init(true), cl::Hidden);

STATISTIC(NumSimple,       "Number of simple if-conversions performed");
STATISTIC(NumSimpleFalse,  "Number of simple (F) if-conversions performed");
STATISTIC(NumTriangle,     "Number of triangle if-conversions performed");
STATISTIC(NumTriangleRev,  "Number of triangle (R) if-conversions performed");
STATISTIC(NumTriangleFalse,"Number of triangle (F) if-conversions performed");
STATISTIC(NumTriangleFRev, "Number of triangle (F/R) if-conversions performed");
STATISTIC(NumDiamonds,     "Number of diamond if-conversions performed");
STATISTIC(NumForkedDiamonds, "Number of forked-diamond if-conversions performed");
STATISTIC(NumIfConvBBs,    "Number of if-converted blocks");
STATISTIC(NumDupBBs,       "Number of duplicated blocks");
STATISTIC(NumUnpred,       "Number of true blocks of diamonds unpredicated");

namespace {

  class IfConverter : public MachineFunctionPass { … };

} // end anonymous namespace

char IfConverter::ID = …;

char &llvm::IfConverterID = …;

INITIALIZE_PASS_BEGIN(IfConverter, DEBUG_TYPE, "If Converter", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
INITIALIZE_PASS_END(IfConverter, DEBUG_TYPE, "If Converter", false, false)

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

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

/// Reverse the condition of the end of the block branch. Swap block's 'true'
/// and 'false' successors.
bool IfConverter::reverseBranchCondition(BBInfo &BBI) const { … }

/// Returns the next block in the function blocks ordering. If it is the end,
/// returns NULL.
static inline MachineBasicBlock *getNextBlock(MachineBasicBlock &MBB) { … }

/// Returns true if the 'true' block (along with its predecessor) forms a valid
/// simple shape for ifcvt. It also returns the number of instructions that the
/// ifcvt would need to duplicate if performed in Dups.
bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
                              BranchProbability Prediction) const { … }

/// Returns true if the 'true' and 'false' blocks (along with their common
/// predecessor) forms a valid triangle shape for ifcvt. If 'FalseBranch' is
/// true, it checks if 'true' block's false branch branches to the 'false' block
/// rather than the other way around. It also returns the number of instructions
/// that the ifcvt would need to duplicate if performed in 'Dups'.
bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
                                bool FalseBranch, unsigned &Dups,
                                BranchProbability Prediction) const { … }

/// Count duplicated instructions and move the iterators to show where they
/// are.
/// @param TIB True Iterator Begin
/// @param FIB False Iterator Begin
/// These two iterators initially point to the first instruction of the two
/// blocks, and finally point to the first non-shared instruction.
/// @param TIE True Iterator End
/// @param FIE False Iterator End
/// These two iterators initially point to End() for the two blocks() and
/// finally point to the first shared instruction in the tail.
/// Upon return [TIB, TIE), and [FIB, FIE) mark the un-duplicated portions of
/// two blocks.
/// @param Dups1 count of duplicated instructions at the beginning of the 2
/// blocks.
/// @param Dups2 count of duplicated instructions at the end of the 2 blocks.
/// @param SkipUnconditionalBranches if true, Don't make sure that
/// unconditional branches at the end of the blocks are the same. True is
/// passed when the blocks are analyzable to allow for fallthrough to be
/// handled.
/// @return false if the shared portion prevents if conversion.
bool IfConverter::CountDuplicatedInstructions(
    MachineBasicBlock::iterator &TIB,
    MachineBasicBlock::iterator &FIB,
    MachineBasicBlock::iterator &TIE,
    MachineBasicBlock::iterator &FIE,
    unsigned &Dups1, unsigned &Dups2,
    MachineBasicBlock &TBB, MachineBasicBlock &FBB,
    bool SkipUnconditionalBranches) const { … }

/// RescanInstructions - Run ScanInstructions on a pair of blocks.
/// @param TIB - True Iterator Begin, points to first non-shared instruction
/// @param FIB - False Iterator Begin, points to first non-shared instruction
/// @param TIE - True Iterator End, points past last non-shared instruction
/// @param FIE - False Iterator End, points past last non-shared instruction
/// @param TrueBBI  - BBInfo to update for the true block.
/// @param FalseBBI - BBInfo to update for the false block.
/// @returns - false if either block cannot be predicated or if both blocks end
///   with a predicate-clobbering instruction.
bool IfConverter::RescanInstructions(
    MachineBasicBlock::iterator &TIB, MachineBasicBlock::iterator &FIB,
    MachineBasicBlock::iterator &TIE, MachineBasicBlock::iterator &FIE,
    BBInfo &TrueBBI, BBInfo &FalseBBI) const { … }

#ifndef NDEBUG
static void verifySameBranchInstructions(
    MachineBasicBlock *MBB1,
    MachineBasicBlock *MBB2) {
  const MachineBasicBlock::reverse_iterator B1 = MBB1->rend();
  const MachineBasicBlock::reverse_iterator B2 = MBB2->rend();
  MachineBasicBlock::reverse_iterator E1 = MBB1->rbegin();
  MachineBasicBlock::reverse_iterator E2 = MBB2->rbegin();
  while (E1 != B1 && E2 != B2) {
    skipDebugInstructionsForward(E1, B1, false);
    skipDebugInstructionsForward(E2, B2, false);
    if (E1 == B1 && E2 == B2)
      break;

    if (E1 == B1) {
      assert(!E2->isBranch() && "Branch mis-match, one block is empty.");
      break;
    }
    if (E2 == B2) {
      assert(!E1->isBranch() && "Branch mis-match, one block is empty.");
      break;
    }

    if (E1->isBranch() || E2->isBranch())
      assert(E1->isIdenticalTo(*E2) &&
             "Branch mis-match, branch instructions don't match.");
    else
      break;
    ++E1;
    ++E2;
  }
}
#endif

/// ValidForkedDiamond - Returns true if the 'true' and 'false' blocks (along
/// with their common predecessor) form a diamond if a common tail block is
/// extracted.
/// While not strictly a diamond, this pattern would form a diamond if
/// tail-merging had merged the shared tails.
///           EBB
///         _/   \_
///         |     |
///        TBB   FBB
///        /  \ /   \
///  FalseBB TrueBB FalseBB
/// Currently only handles analyzable branches.
/// Specifically excludes actual diamonds to avoid overlap.
bool IfConverter::ValidForkedDiamond(
    BBInfo &TrueBBI, BBInfo &FalseBBI,
    unsigned &Dups1, unsigned &Dups2,
    BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const { … }

/// ValidDiamond - Returns true if the 'true' and 'false' blocks (along
/// with their common predecessor) forms a valid diamond shape for ifcvt.
bool IfConverter::ValidDiamond(
    BBInfo &TrueBBI, BBInfo &FalseBBI,
    unsigned &Dups1, unsigned &Dups2,
    BBInfo &TrueBBICalc, BBInfo &FalseBBICalc) const { … }

/// AnalyzeBranches - Look at the branches at the end of a block to determine if
/// the block is predicable.
void IfConverter::AnalyzeBranches(BBInfo &BBI) { … }

/// ScanInstructions - Scan all the instructions in the block to determine if
/// the block is predicable. In most cases, that means all the instructions
/// in the block are isPredicable(). Also checks if the block contains any
/// instruction which can clobber a predicate (e.g. condition code register).
/// If so, the block is not predicable unless it's the last instruction.
void IfConverter::ScanInstructions(BBInfo &BBI,
                                   MachineBasicBlock::iterator &Begin,
                                   MachineBasicBlock::iterator &End,
                                   bool BranchUnpredicable) const { … }

/// Determine if the block is a suitable candidate to be predicated by the
/// specified predicate.
/// @param BBI BBInfo for the block to check
/// @param Pred Predicate array for the branch that leads to BBI
/// @param isTriangle true if the Analysis is for a triangle
/// @param RevBranch true if Reverse(Pred) leads to BBI (e.g. BBI is the false
///        case
/// @param hasCommonTail true if BBI shares a tail with a sibling block that
///        contains any instruction that would make the block unpredicable.
bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
                                      SmallVectorImpl<MachineOperand> &Pred,
                                      bool isTriangle, bool RevBranch,
                                      bool hasCommonTail) { … }

/// Analyze the structure of the sub-CFG starting from the specified block.
/// Record its successors and whether it looks like an if-conversion candidate.
void IfConverter::AnalyzeBlock(
    MachineBasicBlock &MBB, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) { … }

/// Analyze all blocks and find entries for all if-conversion candidates.
void IfConverter::AnalyzeBlocks(
    MachineFunction &MF, std::vector<std::unique_ptr<IfcvtToken>> &Tokens) { … }

/// Returns true either if ToMBB is the next block after MBB or that all the
/// intervening blocks are empty (given MBB can fall through to its next block).
static bool canFallThroughTo(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB) { … }

/// Invalidate predecessor BB info so it would be re-analyzed to determine if it
/// can be if-converted. If predecessor is already enqueued, dequeue it!
void IfConverter::InvalidatePreds(MachineBasicBlock &MBB) { … }

/// Inserts an unconditional branch from \p MBB to \p ToMBB.
static void InsertUncondBranch(MachineBasicBlock &MBB, MachineBasicBlock &ToMBB,
                               const TargetInstrInfo *TII) { … }

/// Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all
/// values defined in MI which are also live/used by MI.
static void UpdatePredRedefs(MachineInstr &MI, LivePhysRegs &Redefs) { … }

/// If convert a simple (split, no rejoin) sub-CFG.
bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) { … }

/// If convert a triangle sub-CFG.
bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) { … }

/// Common code shared between diamond conversions.
/// \p BBI, \p TrueBBI, and \p FalseBBI form the diamond shape.
/// \p NumDups1 - number of shared instructions at the beginning of \p TrueBBI
///               and FalseBBI
/// \p NumDups2 - number of shared instructions at the end of \p TrueBBI
///               and \p FalseBBI
/// \p RemoveBranch - Remove the common branch of the two blocks before
///                   predicating. Only false for unanalyzable fallthrough
///                   cases. The caller will replace the branch if necessary.
/// \p MergeAddEdges - Add successor edges when merging blocks. Only false for
///                    unanalyzable fallthrough
bool IfConverter::IfConvertDiamondCommon(
    BBInfo &BBI, BBInfo &TrueBBI, BBInfo &FalseBBI,
    unsigned NumDups1, unsigned NumDups2,
    bool TClobbersPred, bool FClobbersPred,
    bool RemoveBranch, bool MergeAddEdges) { … }

/// If convert an almost-diamond sub-CFG where the true
/// and false blocks share a common tail.
bool IfConverter::IfConvertForkedDiamond(
    BBInfo &BBI, IfcvtKind Kind,
    unsigned NumDups1, unsigned NumDups2,
    bool TClobbersPred, bool FClobbersPred) { … }

/// If convert a diamond sub-CFG.
bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
                                   unsigned NumDups1, unsigned NumDups2,
                                   bool TClobbersPred, bool FClobbersPred) { … }

static bool MaySpeculate(const MachineInstr &MI,
                         SmallSet<MCPhysReg, 4> &LaterRedefs) { … }

/// Predicate instructions from the start of the block to the specified end with
/// the specified condition.
void IfConverter::PredicateBlock(BBInfo &BBI,
                                 MachineBasicBlock::iterator E,
                                 SmallVectorImpl<MachineOperand> &Cond,
                                 SmallSet<MCPhysReg, 4> *LaterRedefs) { … }

/// Copy and predicate instructions from source BB to the destination block.
/// Skip end of block branches if IgnoreBr is true.
void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
                                        SmallVectorImpl<MachineOperand> &Cond,
                                        bool IgnoreBr) { … }

/// Move all instructions from FromBB to the end of ToBB.  This will leave
/// FromBB as an empty block, so remove all of its successor edges and move it
/// to the end of the function.  If AddEdges is true, i.e., when FromBBI's
/// branch is being moved, add those successor edges to ToBBI and remove the old
/// edge from ToBBI to FromBBI.
void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) { … }

FunctionPass *
llvm::createIfConverter(std::function<bool(const MachineFunction &)> Ftor) { … }
llvm/llvm/lib/CodeGen/IfConversion.cpp
