LLVM 20.0.0git
Namespaces | Macros | Functions | Variables
MachineBlockPlacement.cpp File Reference
#include "BranchFolding.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/DenseMap.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/Analysis/BlockFrequencyInfoImpl.h"
#include "llvm/Analysis/ProfileSummaryInfo.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/MachineLoopInfo.h"
#include "llvm/CodeGen/MachinePostDominators.h"
#include "llvm/CodeGen/MachineSizeOpts.h"
#include "llvm/CodeGen/TailDuplicator.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetLowering.h"
#include "llvm/CodeGen/TargetPassConfig.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/PrintPasses.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/CodeGen.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Transforms/Utils/CodeLayout.h"
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <memory>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

Go to the source code of this file.

Namespaces

namespace  llvm
 This is an optimization pass for GlobalISel generic memory operations.
 

Macros

#define DEBUG_TYPE   "block-placement"
 

Functions

 STATISTIC (NumCondBranches, "Number of conditional branches")
 
 STATISTIC (NumUncondBranches, "Number of unconditional branches")
 
 STATISTIC (CondBranchTakenFreq, "Potential frequency of taking conditional branches")
 
 STATISTIC (UncondBranchTakenFreq, "Potential frequency of taking unconditional branches")
 
 INITIALIZE_PASS_BEGIN (MachineBlockPlacement, DEBUG_TYPE, "Branch Probability Basic Block Placement", false, false) INITIALIZE_PASS_END(MachineBlockPlacement
 
Branch Probability Basic Block static false std::string getBlockName (const MachineBasicBlock *BB)
 Helper to print the name of a MBB.
 
static BranchProbability getAdjustedProbability (BranchProbability OrigProb, BranchProbability AdjustedSumProb)
 The helper function returns the branch probability that is adjusted or normalized over the new total AdjustedSumProb.
 
static bool hasSameSuccessors (MachineBasicBlock &BB, SmallPtrSetImpl< const MachineBasicBlock * > &Successors)
 Check if BB has exactly the successors in Successors.
 
static bool greaterWithBias (BlockFrequency A, BlockFrequency B, BlockFrequency EntryFreq)
 Compare 2 BlockFrequency's with a small penalty for A.
 
static BranchProbability getLayoutSuccessorProbThreshold (const MachineBasicBlock *BB)
 
static uint64_t countMBBInstruction (MachineBasicBlock *MBB)
 
 INITIALIZE_PASS_BEGIN (MachineBlockPlacementStats, "block-placement-stats", "Basic Block Placement Stats", false, false) INITIALIZE_PASS_END(MachineBlockPlacementStats
 

Variables

static cl::opt< unsignedAlignAllBlock ("align-all-blocks", cl::desc("Force the alignment of all blocks in the function in log2 format " "(e.g 4 means align on 16B boundaries)."), cl::init(0), cl::Hidden)
 
static cl::opt< unsignedAlignAllNonFallThruBlocks ("align-all-nofallthru-blocks", cl::desc("Force the alignment of all blocks that have no fall-through " "predecessors (i.e. don't add nops that are executed). In log2 " "format (e.g 4 means align on 16B boundaries)."), cl::init(0), cl::Hidden)
 
static cl::opt< unsignedMaxBytesForAlignmentOverride ("max-bytes-for-alignment", cl::desc("Forces the maximum bytes allowed to be emitted when padding for " "alignment"), cl::init(0), cl::Hidden)
 
static cl::opt< unsignedExitBlockBias ("block-placement-exit-block-bias", cl::desc("Block frequency percentage a loop exit block needs " "over the original exit to be considered the new exit."), cl::init(0), cl::Hidden)
 
static cl::opt< unsignedLoopToColdBlockRatio ("loop-to-cold-block-ratio", cl::desc("Outline loop blocks from loop chain if (frequency of loop) / " "(frequency of block) is greater than this ratio"), cl::init(5), cl::Hidden)
 
static cl::opt< boolForceLoopColdBlock ("force-loop-cold-block", cl::desc("Force outlining cold blocks from loops."), cl::init(false), cl::Hidden)
 
static cl::opt< boolPreciseRotationCost ("precise-rotation-cost", cl::desc("Model the cost of loop rotation more " "precisely by using profile data."), cl::init(false), cl::Hidden)
 
static cl::opt< boolForcePreciseRotationCost ("force-precise-rotation-cost", cl::desc("Force the use of precise cost " "loop rotation strategy."), cl::init(false), cl::Hidden)
 
static cl::opt< unsignedMisfetchCost ("misfetch-cost", cl::desc("Cost that models the probabilistic risk of an instruction " "misfetch due to a jump comparing to falling through, whose cost " "is zero."), cl::init(1), cl::Hidden)
 
static cl::opt< unsignedJumpInstCost ("jump-inst-cost", cl::desc("Cost of jump instructions."), cl::init(1), cl::Hidden)
 
static cl::opt< boolTailDupPlacement ("tail-dup-placement", cl::desc("Perform tail duplication during placement. " "Creates more fallthrough opportunites in " "outline branches."), cl::init(true), cl::Hidden)
 
static cl::opt< boolBranchFoldPlacement ("branch-fold-placement", cl::desc("Perform branch folding during placement. " "Reduces code size."), cl::init(true), cl::Hidden)
 
static cl::opt< unsignedTailDupPlacementThreshold ("tail-dup-placement-threshold", cl::desc("Instruction cutoff for tail duplication during layout. " "Tail merging during layout is forced to have a threshold " "that won't conflict."), cl::init(2), cl::Hidden)
 
static cl::opt< unsignedTailDupPlacementAggressiveThreshold ("tail-dup-placement-aggressive-threshold", cl::desc("Instruction cutoff for aggressive tail duplication during " "layout. Used at -O3. Tail merging during layout is forced to " "have a threshold that won't conflict."), cl::init(4), cl::Hidden)
 
static cl::opt< unsignedTailDupPlacementPenalty ("tail-dup-placement-penalty", cl::desc("Cost penalty for blocks that can avoid breaking CFG by copying. " "Copying can increase fallthrough, but it also increases icache " "pressure. This parameter controls the penalty to account for that. " "Percent as integer."), cl::init(2), cl::Hidden)
 
static cl::opt< unsignedTailDupProfilePercentThreshold ("tail-dup-profile-percent-threshold", cl::desc("If profile count information is used in tail duplication cost " "model, the gained fall through number from tail duplication " "should be at least this percent of hot count."), cl::init(50), cl::Hidden)
 
static cl::opt< unsignedTriangleChainCount ("triangle-chain-count", cl::desc("Number of triangle-shaped-CFG's that need to be in a row for the " "triangle tail duplication heuristic to kick in. 0 to disable."), cl::init(2), cl::Hidden)
 
static cl::opt< boolRenumberBlocksBeforeView ("renumber-blocks-before-view", cl::desc("If true, basic blocks are re-numbered before MBP layout is printed " "into a dot graph. Only used when a function is being printed."), cl::init(false), cl::Hidden)
 
static cl::opt< unsignedExtTspBlockPlacementMaxBlocks ("ext-tsp-block-placement-max-blocks", cl::desc("Maximum number of basic blocks in a function to run ext-TSP " "block placement."), cl::init(UINT_MAX), cl::Hidden)
 
static cl::opt< boolApplyExtTspForSize ("apply-ext-tsp-for-size", cl::init(false), cl::Hidden, cl::desc("Use ext-tsp for size-aware block placement."))
 
cl::opt< boolllvm::EnableExtTspBlockPlacement
 
cl::opt< boolllvm::ApplyExtTspWithoutProfile
 
cl::opt< unsignedllvm::StaticLikelyProb
 
cl::opt< unsignedllvm::ProfileLikelyProb
 
 DEBUG_TYPE
 
Branch Probability Basic Block Placement
 
Branch Probability Basic Block false
 
block placement stats
 
block placement Basic Block Placement Stats
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "block-placement"

Definition at line 78 of file MachineBlockPlacement.cpp.

Function Documentation

◆ countMBBInstruction()

static uint64_t countMBBInstruction ( MachineBasicBlock MBB)
static

Definition at line 3272 of file MachineBlockPlacement.cpp.

References InstrCount, MBB, and MI.

◆ getAdjustedProbability()

static BranchProbability getAdjustedProbability ( BranchProbability  OrigProb,
BranchProbability  AdjustedSumProb 
)
static

The helper function returns the branch probability that is adjusted or normalized over the new total AdjustedSumProb.

Definition at line 769 of file MachineBlockPlacement.cpp.

References llvm::BranchProbability::getNumerator(), and llvm::BranchProbability::getOne().

◆ getBlockName()

Branch Probability Basic Block static false std::string getBlockName ( const MachineBasicBlock BB)
static

Helper to print the name of a MBB.

Only used by debug logging.

Definition at line 657 of file MachineBlockPlacement.cpp.

References llvm::raw_ostream::flush(), llvm::MachineBasicBlock::getName(), OS, and llvm::printMBBReference().

◆ getLayoutSuccessorProbThreshold()

static BranchProbability getLayoutSuccessorProbThreshold ( const MachineBasicBlock BB)
static

◆ greaterWithBias()

static bool greaterWithBias ( BlockFrequency  A,
BlockFrequency  B,
BlockFrequency  EntryFreq 
)
static

Compare 2 BlockFrequency's with a small penalty for A.

In order to be conservative, we apply a X% penalty to account for increased icache pressure and static heuristics. For small frequencies we use only the numerators to improve accuracy. For simplicity, we assume the penalty is less than 100% TODO(iteratee): Use 64-bit fixed point edge frequencies everywhere.

Definition at line 817 of file MachineBlockPlacement.cpp.

References A, B, and TailDupPlacementPenalty.

◆ hasSameSuccessors()

static bool hasSameSuccessors ( MachineBasicBlock BB,
SmallPtrSetImpl< const MachineBasicBlock * > &  Successors 
)
static

◆ INITIALIZE_PASS_BEGIN() [1/2]

INITIALIZE_PASS_BEGIN ( MachineBlockPlacement  ,
DEBUG_TYPE  ,
"Branch Probability Basic Block Placement"  ,
false  ,
false   
)

◆ INITIALIZE_PASS_BEGIN() [2/2]

INITIALIZE_PASS_BEGIN ( MachineBlockPlacementStats  ,
"block-placement-stats"  ,
"Basic Block Placement Stats"  ,
false  ,
false   
)

◆ STATISTIC() [1/4]

STATISTIC ( CondBranchTakenFreq  ,
"Potential frequency of taking conditional branches"   
)

◆ STATISTIC() [2/4]

STATISTIC ( NumCondBranches  ,
"Number of conditional branches"   
)

◆ STATISTIC() [3/4]

STATISTIC ( NumUncondBranches  ,
"Number of unconditional branches"   
)

◆ STATISTIC() [4/4]

STATISTIC ( UncondBranchTakenFreq  ,
"Potential frequency of taking unconditional branches"   
)

Variable Documentation

◆ AlignAllBlock

cl::opt< unsigned > AlignAllBlock("align-all-blocks", cl::desc("Force the alignment of all blocks in the function in log2 format " "(e.g 4 means align on 16B boundaries)."), cl::init(0), cl::Hidden) ( "align-all-blocks"  ,
cl::desc("Force the alignment of all blocks in the function in log2 format " "(e.g 4 means align on 16B boundaries).")  ,
cl::init(0)  ,
cl::Hidden   
)
static

◆ AlignAllNonFallThruBlocks

cl::opt< unsigned > AlignAllNonFallThruBlocks("align-all-nofallthru-blocks", cl::desc("Force the alignment of all blocks that have no fall-through " "predecessors (i.e. don't add nops that are executed). In log2 " "format (e.g 4 means align on 16B boundaries)."), cl::init(0), cl::Hidden) ( "align-all-nofallthru-blocks"  ,
cl::desc("Force the alignment of all blocks that have no fall-through " "predecessors (i.e. don't add nops that are executed). In log2 " "format (e.g 4 means align on 16B boundaries).")  ,
cl::init(0)  ,
cl::Hidden   
)
static

◆ ApplyExtTspForSize

cl::opt< bool > ApplyExtTspForSize("apply-ext-tsp-for-size", cl::init(false), cl::Hidden, cl::desc("Use ext-tsp for size-aware block placement.")) ( "apply-ext-tsp-for-size"  ,
cl::init(false)  ,
cl::Hidden  ,
cl::desc("Use ext-tsp for size-aware block placement.")   
)
static

◆ BranchFoldPlacement

cl::opt< bool > BranchFoldPlacement("branch-fold-placement", cl::desc("Perform branch folding during placement. " "Reduces code size."), cl::init(true), cl::Hidden) ( "branch-fold-placement"  ,
cl::desc("Perform branch folding during placement. " "Reduces code size.")  ,
cl::init(true ,
cl::Hidden   
)
static

◆ DEBUG_TYPE

DEBUG_TYPE

Definition at line 650 of file MachineBlockPlacement.cpp.

◆ ExitBlockBias

cl::opt< unsigned > ExitBlockBias("block-placement-exit-block-bias", cl::desc("Block frequency percentage a loop exit block needs " "over the original exit to be considered the new exit."), cl::init(0), cl::Hidden) ( "block-placement-exit-block-bias"  ,
cl::desc("Block frequency percentage a loop exit block needs " "over the original exit to be considered the new exit.")  ,
cl::init(0)  ,
cl::Hidden   
)
static

◆ ExtTspBlockPlacementMaxBlocks

cl::opt< unsigned > ExtTspBlockPlacementMaxBlocks("ext-tsp-block-placement-max-blocks", cl::desc("Maximum number of basic blocks in a function to run ext-TSP " "block placement."), cl::init(UINT_MAX), cl::Hidden) ( "ext-tsp-block-placement-max-blocks"  ,
cl::desc("Maximum number of basic blocks in a function to run ext-TSP " "block placement.")  ,
cl::init(UINT_MAX)  ,
cl::Hidden   
)
static

◆ false

block placement Basic Block Placement false

Definition at line 651 of file MachineBlockPlacement.cpp.

◆ ForceLoopColdBlock

cl::opt< bool > ForceLoopColdBlock("force-loop-cold-block", cl::desc("Force outlining cold blocks from loops."), cl::init(false), cl::Hidden) ( "force-loop-cold-block"  ,
cl::desc("Force outlining cold blocks from loops.")  ,
cl::init(false)  ,
cl::Hidden   
)
static

◆ ForcePreciseRotationCost

cl::opt< bool > ForcePreciseRotationCost("force-precise-rotation-cost", cl::desc("Force the use of precise cost " "loop rotation strategy."), cl::init(false), cl::Hidden) ( "force-precise-rotation-cost"  ,
cl::desc("Force the use of precise cost " "loop rotation strategy.")  ,
cl::init(false)  ,
cl::Hidden   
)
static

◆ JumpInstCost

cl::opt< unsigned > JumpInstCost("jump-inst-cost", cl::desc("Cost of jump instructions."), cl::init(1), cl::Hidden) ( "jump-inst-cost"  ,
cl::desc("Cost of jump instructions.")  ,
cl::init(1)  ,
cl::Hidden   
)
static

◆ LoopToColdBlockRatio

cl::opt< unsigned > LoopToColdBlockRatio("loop-to-cold-block-ratio", cl::desc("Outline loop blocks from loop chain if (frequency of loop) / " "(frequency of block) is greater than this ratio"), cl::init(5), cl::Hidden) ( "loop-to-cold-block-ratio"  ,
cl::desc("Outline loop blocks from loop chain if (frequency of loop) / " "(frequency of block) is greater than this ratio")  ,
cl::init(5)  ,
cl::Hidden   
)
static

◆ MaxBytesForAlignmentOverride

cl::opt< unsigned > MaxBytesForAlignmentOverride("max-bytes-for-alignment", cl::desc("Forces the maximum bytes allowed to be emitted when padding for " "alignment"), cl::init(0), cl::Hidden) ( "max-bytes-for-alignment"  ,
cl::desc("Forces the maximum bytes allowed to be emitted when padding for " "alignment")  ,
cl::init(0)  ,
cl::Hidden   
)
static

◆ MisfetchCost

cl::opt< unsigned > MisfetchCost("misfetch-cost", cl::desc("Cost that models the probabilistic risk of an instruction " "misfetch due to a jump comparing to falling through, whose cost " "is zero."), cl::init(1), cl::Hidden) ( "misfetch-cost"  ,
cl::desc("Cost that models the probabilistic risk of an instruction " "misfetch due to a jump comparing to falling through, whose cost " "is zero.")  ,
cl::init(1)  ,
cl::Hidden   
)
static

◆ Placement

Branch Probability Basic Block Placement

◆ PreciseRotationCost

cl::opt< bool > PreciseRotationCost("precise-rotation-cost", cl::desc("Model the cost of loop rotation more " "precisely by using profile data."), cl::init(false), cl::Hidden) ( "precise-rotation-cost"  ,
cl::desc("Model the cost of loop rotation more " "precisely by using profile data.")  ,
cl::init(false)  ,
cl::Hidden   
)
static

◆ RenumberBlocksBeforeView

cl::opt< bool > RenumberBlocksBeforeView("renumber-blocks-before-view", cl::desc( "If true, basic blocks are re-numbered before MBP layout is printed " "into a dot graph. Only used when a function is being printed."), cl::init(false), cl::Hidden) ( "renumber-blocks-before-view"  ,
cl::desc( "If true, basic blocks are re-numbered before MBP layout is printed " "into a dot graph. Only used when a function is being printed.")  ,
cl::init(false)  ,
cl::Hidden   
)
static

◆ stats

void IFOrdering::stats

Definition at line 3813 of file MachineBlockPlacement.cpp.

◆ Stats

block placement Basic Block Placement Stats

◆ TailDupPlacement

cl::opt< bool > TailDupPlacement("tail-dup-placement", cl::desc("Perform tail duplication during placement. " "Creates more fallthrough opportunites in " "outline branches."), cl::init(true), cl::Hidden) ( "tail-dup-placement"  ,
cl::desc("Perform tail duplication during placement. " "Creates more fallthrough opportunites in " "outline branches.")  ,
cl::init(true ,
cl::Hidden   
)
static

◆ TailDupPlacementAggressiveThreshold

cl::opt< unsigned > TailDupPlacementAggressiveThreshold("tail-dup-placement-aggressive-threshold", cl::desc("Instruction cutoff for aggressive tail duplication during " "layout. Used at -O3. Tail merging during layout is forced to " "have a threshold that won't conflict."), cl::init(4), cl::Hidden) ( "tail-dup-placement-aggressive-threshold"  ,
cl::desc("Instruction cutoff for aggressive tail duplication during " "layout. Used at -O3. Tail merging during layout is forced to " "have a threshold that won't conflict.")  ,
cl::init(4)  ,
cl::Hidden   
)
static

◆ TailDupPlacementPenalty

cl::opt< unsigned > TailDupPlacementPenalty("tail-dup-placement-penalty", cl::desc( "Cost penalty for blocks that can avoid breaking CFG by copying. " "Copying can increase fallthrough, but it also increases icache " "pressure. This parameter controls the penalty to account for that. " "Percent as integer."), cl::init(2), cl::Hidden) ( "tail-dup-placement-penalty"  ,
cl::desc( "Cost penalty for blocks that can avoid breaking CFG by copying. " "Copying can increase fallthrough, but it also increases icache " "pressure. This parameter controls the penalty to account for that. " "Percent as integer.")  ,
cl::init(2)  ,
cl::Hidden   
)
static

Referenced by greaterWithBias().

◆ TailDupPlacementThreshold

cl::opt< unsigned > TailDupPlacementThreshold("tail-dup-placement-threshold", cl::desc("Instruction cutoff for tail duplication during layout. " "Tail merging during layout is forced to have a threshold " "that won't conflict."), cl::init(2), cl::Hidden) ( "tail-dup-placement-threshold"  ,
cl::desc("Instruction cutoff for tail duplication during layout. " "Tail merging during layout is forced to have a threshold " "that won't conflict.")  ,
cl::init(2)  ,
cl::Hidden   
)
static

◆ TailDupProfilePercentThreshold

cl::opt< unsigned > TailDupProfilePercentThreshold("tail-dup-profile-percent-threshold", cl::desc("If profile count information is used in tail duplication cost " "model, the gained fall through number from tail duplication " "should be at least this percent of hot count."), cl::init(50), cl::Hidden) ( "tail-dup-profile-percent-threshold"  ,
cl::desc("If profile count information is used in tail duplication cost " "model, the gained fall through number from tail duplication " "should be at least this percent of hot count.")  ,
cl::init(50)  ,
cl::Hidden   
)
static

◆ TriangleChainCount

cl::opt< unsigned > TriangleChainCount("triangle-chain-count", cl::desc("Number of triangle-shaped-CFG's that need to be in a row for the " "triangle tail duplication heuristic to kick in. 0 to disable."), cl::init(2), cl::Hidden) ( "triangle-chain-count"  ,
cl::desc("Number of triangle-shaped-CFG's that need to be in a row for the " "triangle tail duplication heuristic to kick in. 0 to disable.")  ,
cl::init(2)  ,
cl::Hidden   
)
static