|
LLVM 20.0.0git
|
#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>Go to the source code of this file.
Macros | |
| #define | DEBUG_TYPE "branch-folder" |
Functions | |
| 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") | |
| INITIALIZE_PASS (BranchFolderPass, DEBUG_TYPE, "Control Flow Optimizer", false, false) bool BranchFolderPass | |
| static unsigned | HashMachineInstr (const MachineInstr &MI) |
| HashMachineInstr - Compute a hash value for MI and its operands. | |
| static unsigned | HashEndOfMBB (const MachineBasicBlock &MBB) |
| HashEndOfMBB - Hash the last instruction in the MBB. | |
| static bool | countsAsInstruction (const MachineInstr &MI) |
| Whether MI should be counted as an instruction when calculating common tail. | |
| static MachineBasicBlock::iterator | skipBackwardPastNonInstructions (MachineBasicBlock::iterator I, MachineBasicBlock *MBB) |
Iterate backwards from the given iterator I, towards the beginning of the block. | |
| static unsigned | ComputeCommonTailLength (MachineBasicBlock *MBB1, MachineBasicBlock *MBB2, MachineBasicBlock::iterator &I1, MachineBasicBlock::iterator &I2) |
| Given two machine basic blocks, return the number of instructions they actually have in common together at their end. | |
| static unsigned | EstimateRuntime (MachineBasicBlock::iterator I, MachineBasicBlock::iterator E) |
| EstimateRuntime - Make a rough estimate for how long it will take to run the specified code. | |
| static void | FixTail (MachineBasicBlock *CurMBB, MachineBasicBlock *SuccBB, const TargetInstrInfo *TII, const DebugLoc &BranchDL) |
| static unsigned | CountTerminators (MachineBasicBlock *MBB, MachineBasicBlock::iterator &I) |
| 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 bool | blockEndsInUnreachable (const MachineBasicBlock *MBB) |
| A no successor, non-return block probably ends in unreachable and is cold. | |
| 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) |
| ProfitableToMerge - Check if two machine basic blocks have a common tail and decide if it would be profitable to merge those tails. | |
| static void | mergeOperations (MachineBasicBlock::iterator MBBIStartPos, MachineBasicBlock &MBBCommon) |
| static bool | IsEmptyBlock (MachineBasicBlock *MBB) |
| static bool | IsBranchOnlyBlock (MachineBasicBlock *MBB) |
| static bool | IsBetterFallthrough (MachineBasicBlock *MBB1, MachineBasicBlock *MBB2) |
| IsBetterFallthrough - Return true if it would be clearly better to fall-through to MBB1 than to fall through into MBB2. | |
| static DebugLoc | getBranchDebugLoc (MachineBasicBlock &MBB) |
| getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block. | |
| static void | copyDebugInfoToPredecessor (const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &PredMBB) |
| static void | copyDebugInfoToSuccessor (const TargetInstrInfo *TII, MachineBasicBlock &MBB, MachineBasicBlock &SuccMBB) |
| static void | salvageDebugInfoFromEmptyBlock (const TargetInstrInfo *TII, MachineBasicBlock &MBB) |
| static MachineBasicBlock * | findFalseBlock (MachineBasicBlock *BB, MachineBasicBlock *TrueBB) |
| findFalseBlock - BB has a fallthrough. | |
| template<class Container > | |
| static void | addRegAndItsAliases (Register Reg, const TargetRegisterInfo *TRI, Container &Set) |
| static MachineBasicBlock::iterator | findHoistingInsertPosAndDeps (MachineBasicBlock *MBB, const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, SmallSet< Register, 4 > &Uses, SmallSet< Register, 4 > &Defs) |
| findHoistingInsertPosAndDeps - Find the location to move common instructions in successors to. | |
Variables | |
| static cl::opt< cl::boolOrDefault > | FlagEnableTailMerge ("enable-tail-merge", cl::init(cl::BOU_UNSET), cl::Hidden) |
| static cl::opt< unsigned > | TailMergeThreshold ("tail-merge-threshold", cl::desc("Max number of predecessors to consider tail merging"), cl::init(150), cl::Hidden) |
| static cl::opt< unsigned > | TailMergeSize ("tail-merge-size", cl::desc("Min number of instructions to consider tail merging"), cl::init(3), cl::Hidden) |
| #define DEBUG_TYPE "branch-folder" |
Definition at line 65 of file BranchFolding.cpp.
|
static |
Definition at line 1806 of file BranchFolding.cpp.
References llvm::MCRegAliasIterator::isValid(), and TRI.
Referenced by findHoistingInsertPosAndDeps().
|
static |
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.
Definition at line 519 of file BranchFolding.cpp.
References llvm::MachineBasicBlock::back(), llvm::MachineBasicBlock::empty(), llvm::MachineInstr::isIndirectBranch(), llvm::MachineInstr::isReturn(), MBB, and llvm::MachineBasicBlock::succ_empty().
Referenced by ProfitableToMerge().
|
static |
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.
Definition at line 329 of file BranchFolding.cpp.
References llvm::MachineBasicBlock::end(), llvm::MachineInstr::NoMerge, and skipBackwardPastNonInstructions().
Referenced by ProfitableToMerge().
|
static |
Definition at line 1280 of file BranchFolding.cpp.
References llvm::dbgs(), llvm::MachineBasicBlock::getFirstTerminator(), llvm::MachineBasicBlock::instrs(), LLVM_DEBUG, MBB, MI, and TII.
Referenced by salvageDebugInfoFromEmptyBlock().
|
static |
Definition at line 1292 of file BranchFolding.cpp.
References llvm::MachineBasicBlock::begin(), llvm::dbgs(), llvm::MachineBasicBlock::instrs(), LLVM_DEBUG, MBB, MI, llvm::MachineBasicBlock::SkipPHIsAndLabels(), and TII.
Referenced by salvageDebugInfoFromEmptyBlock().
|
static |
Whether MI should be counted as an instruction when calculating common tail.
Definition at line 305 of file BranchFolding.cpp.
References MI.
Referenced by EstimateRuntime(), mergeOperations(), and skipBackwardPastNonInstructions().
|
static |
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.
Definition at line 500 of file BranchFolding.cpp.
References llvm::MachineBasicBlock::begin(), llvm::MachineBasicBlock::end(), I, and MBB.
Referenced by ProfitableToMerge().
|
static |
EstimateRuntime - Make a rough estimate for how long it will take to run the specified code.
Definition at line 441 of file BranchFolding.cpp.
References countsAsInstruction(), and I.
|
static |
findFalseBlock - BB has a fallthrough.
Find its 'false' successor given its 'true' successor.
Definition at line 1797 of file BranchFolding.cpp.
References llvm::MachineBasicBlock::successors().
|
static |
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.
Definition at line 1824 of file BranchFolding.cpp.
References addRegAndItsAliases(), llvm::MachineBasicBlock::begin(), llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::getFirstTerminator(), llvm::HexagonInstrInfo::isPredicated(), MBB, llvm::prev_nodbg(), SubReg, TII, TRI, and Uses.
|
static |
Definition at line 461 of file BranchFolding.cpp.
References llvm::HexagonInstrInfo::analyzeBranch(), Cond, llvm::MachineFunction::end(), llvm::MachineBasicBlock::findBranchDebugLoc(), llvm::MachineBasicBlock::getParent(), I, llvm::HexagonInstrInfo::insertBranch(), llvm::HexagonInstrInfo::removeBranch(), llvm::HexagonInstrInfo::reverseBranchCondition(), TBB, and TII.
|
static |
getBranchDebugLoc - Find and return, if any, the DebugLoc of the branch instructions on the block.
Definition at line 1273 of file BranchFolding.cpp.
References llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::getLastNonDebugInstr(), I, and MBB.
|
static |
HashEndOfMBB - Hash the last instruction in the MBB.
Definition at line 296 of file BranchFolding.cpp.
References llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::getLastNonDebugInstr(), HashMachineInstr(), I, and MBB.
|
static |
HashMachineInstr - Compute a hash value for MI and its operands.
Definition at line 256 of file BranchFolding.cpp.
References MI, llvm::MachineOperand::MO_ConstantPoolIndex, llvm::MachineOperand::MO_ExternalSymbol, llvm::MachineOperand::MO_FrameIndex, llvm::MachineOperand::MO_GlobalAddress, llvm::MachineOperand::MO_Immediate, llvm::MachineOperand::MO_JumpTableIndex, llvm::MachineOperand::MO_MachineBasicBlock, and llvm::MachineOperand::MO_Register.
Referenced by HashEndOfMBB().
| INITIALIZE_PASS | ( | BranchFolderPass | , |
| DEBUG_TYPE | , | ||
| "Control Flow Optimizer" | , | ||
| false | , | ||
| false | |||
| ) |
Definition at line 119 of file BranchFolding.cpp.
References llvm::TargetPassConfig::getEnableTailMerge(), and llvm::BranchFolder::OptimizeFunction().
|
static |
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.
Definition at line 1250 of file BranchFolding.cpp.
References assert(), llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::getLastNonDebugInstr(), and llvm::MachineBasicBlock::isSuccessor().
|
static |
Definition at line 1240 of file BranchFolding.cpp.
References assert(), llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::getFirstNonDebugInstr(), I, and MBB.
|
static |
Definition at line 1234 of file BranchFolding.cpp.
References llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::getFirstNonDebugInstr(), and MBB.
Referenced by llvm::LoopVectorizationCostModel::collectValuesToIgnore(), and salvageDebugInfoFromEmptyBlock().
|
static |
Definition at line 761 of file BranchFolding.cpp.
References assert(), countsAsInstruction(), llvm::MachineBasicBlock::end(), llvm::MachineBasicBlock::getParent(), I, llvm::MachineOperand::isReg(), llvm::MachineOperand::isUndef(), MBB, MBBI, llvm::MachineBasicBlock::rbegin(), llvm::MachineBasicBlock::rend(), and llvm::MachineOperand::setIsUndef().
|
static |
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.
Definition at line 544 of file BranchFolding.cpp.
References assert(), llvm::MachineBasicBlock::back(), llvm::MachineBasicBlock::begin(), llvm::MachineFunction::begin(), blockEndsInUnreachable(), llvm::MachineBasicBlock::canFallThrough(), ComputeCommonTailLength(), CountTerminators(), llvm::dbgs(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::empty(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::MachineBasicBlock::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::MachineBasicBlock::getParent(), I, llvm::MachineInstr::isBarrier(), llvm::MachineBasicBlock::isLayoutSuccessor(), LLVM_DEBUG, MBB, llvm::printMBBReference(), llvm::shouldOptimizeForSize(), llvm::skipDebugInstructionsForward(), llvm::MachineBasicBlock::succ_empty(), and llvm::MachineBasicBlock::succ_size().
|
static |
Definition at line 1311 of file BranchFolding.cpp.
References assert(), copyDebugInfoToPredecessor(), copyDebugInfoToSuccessor(), IsEmptyBlock(), MBB, llvm::MachineBasicBlock::pred_size(), llvm::MachineBasicBlock::predecessors(), llvm::MachineBasicBlock::succ_size(), llvm::MachineBasicBlock::successors(), and TII.
|
static |
Iterate backwards from the given iterator 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.
Definition at line 313 of file BranchFolding.cpp.
References llvm::MachineBasicBlock::begin(), countsAsInstruction(), llvm::MachineBasicBlock::end(), I, and MBB.
Referenced by ComputeCommonTailLength().
| STATISTIC | ( | NumBranchOpts | , |
| "Number of branches optimized" | |||
| ) |
| STATISTIC | ( | NumDeadBlocks | , |
| "Number of dead blocks removed" | |||
| ) |
| STATISTIC | ( | NumHoist | , |
| "Number of times common instructions are hoisted" | |||
| ) |
| STATISTIC | ( | NumTailCalls | , |
| "Number of tail calls optimized" | |||
| ) |
| STATISTIC | ( | NumTailMerge | , |
| "Number of block tails merged" | |||
| ) |
|
static |
Referenced by llvm::BranchFolder::BranchFolder().
|
static |
Referenced by llvm::BranchFolder::OptimizeFunction().
1.9.6