LLVM  8.0.1
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/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/MachineModuleInfo.h"
#include "llvm/CodeGen/MachinePostDominators.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/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 <algorithm>
#include <cassert>
#include <cstdint>
#include <iterator>
#include <memory>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
Include dependency graph for MachineBlockPlacement.cpp:

Go to the source code of this file.

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. More...
 
static BranchProbability getAdjustedProbability (BranchProbability OrigProb, BranchProbability AdjustedSumProb)
 The helper function returns the branch probability that is adjusted or normalized over the new total AdjustedSumProb. More...
 
static bool hasSameSuccessors (MachineBasicBlock &BB, SmallPtrSetImpl< const MachineBasicBlock *> &Successors)
 Check if BB has exactly the successors in Successors. More...
 
static bool greaterWithBias (BlockFrequency A, BlockFrequency B, uint64_t EntryFreq)
 Compare 2 BlockFrequency's with a small penalty for A. More...
 
static BranchProbability getLayoutSuccessorProbThreshold (const MachineBasicBlock *BB)
 
 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."), 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)."), 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< 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)
 
cl::opt< unsignedStaticLikelyProb
 
cl::opt< unsignedProfileLikelyProb
 
cl::opt< GVDAGType > ViewBlockLayoutWithBFI
 
cl::opt< std::string > ViewBlockFreqFuncName
 
 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 74 of file MachineBlockPlacement.cpp.

Function Documentation

◆ 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 663 of file MachineBlockPlacement.cpp.

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

Referenced by getLayoutSuccessorProbThreshold(), and greaterWithBias().

◆ getBlockName()

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

◆ getLayoutSuccessorProbThreshold()

static BranchProbability getLayoutSuccessorProbThreshold ( const MachineBasicBlock BB)
static

Definition at line 1244 of file MachineBlockPlacement.cpp.

References llvm::AnalysisUsage::addRequired(), llvm::CodeGenOpt::Aggressive, llvm::AMDGPU::HSAMD::Kernel::Arg::Key::Align, AlignAllBlock, AlignAllNonFallThruBlocks, llvm::TargetLoweringBase::alignLoopsWithOptSize(), llvm::SpecificBumpPtrAllocator< T >::Allocate(), llvm::TargetInstrInfo::analyzeBranch(), assert(), llvm::MachineBasicBlock::back(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::begin(), llvm::SmallVectorTemplateCommon< T >::begin(), llvm::MachineBasicBlock::begin(), llvm::MachineFunction::begin(), llvm::LoopBase< BlockT, LoopT >::block_begin(), llvm::LoopBase< BlockT, LoopT >::block_end(), BranchFoldPlacement, llvm::MachineBasicBlock::canFallThrough(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::SmallVectorImpl< T >::clear(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::count(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dbgs(), llvm::SpecificBumpPtrAllocator< T >::DestroyAll(), E, llvm::SmallVectorImpl< T >::emplace_back(), llvm::SmallVectorBase::empty(), llvm::SmallPtrSetImplBase::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::empty(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::SmallVectorTemplateCommon< T >::end(), llvm::MachineFunction::end(), llvm::StringRef::equals(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::SmallVectorImpl< T >::erase(), ExitBlockBias, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), llvm::find(), for(), ForceLoopColdBlock, ForcePreciseRotationCost, llvm::MachineFunction::front(), getAdjustedProbability(), llvm::MachineFunctionPass::getAnalysisUsage(), getBlockName(), llvm::LoopBase< BlockT, LoopT >::getBlocks(), llvm::BranchProbability::getCompl(), llvm::MachineBranchProbabilityInfo::getEdgeProbability(), llvm::TargetPassConfig::getEnableTailMerge(), llvm::BlockFrequency::getFrequency(), llvm::MachineFunction::getFunction(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::TargetSubtargetInfo::getInstrInfo(), llvm::MachineLoopInfo::getLoopFor(), llvm::BlockFrequency::getMaxFrequency(), llvm::Value::getName(), llvm::MachineBasicBlock::getNumber(), llvm::LoopBase< BlockT, LoopT >::getNumBlocks(), llvm::TargetPassConfig::getOptLevel(), llvm::MachineBasicBlock::getParent(), llvm::PassRegistry::getPassRegistry(), llvm::TargetLoweringBase::getPrefLoopAlignment(), llvm::TargetSubtargetInfo::getRegisterInfo(), llvm::MachineFunction::getSubtarget(), llvm::MachineFunction::getTarget(), llvm::TargetSubtargetInfo::getTargetLowering(), llvm::BranchProbability::getZero(), llvm::GVDT_None, llvm::Function::hasProfileData(), I, llvm::initializeMachineBlockPlacementStatsPass(), llvm::TailDuplicator::initMF(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::TargetInstrInfo::insertBranch(), llvm::MachineBasicBlock::isEHPad(), llvm::MachineBasicBlock::isLayoutSuccessor(), llvm::TailDuplicator::isSimpleBB(), llvm::MachineBasicBlock::isSuccessor(), JumpInstCost, LLVM_DEBUG, llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::lookup(), LoopToColdBlockRatio, llvm::max(), MisfetchCost, llvm::Function::optForMinSize(), llvm::Function::optForSize(), llvm::BranchFolder::OptimizeFunction(), PreciseRotationCost, llvm::MachineBasicBlock::pred_begin(), llvm::MachineBasicBlock::pred_size(), llvm::MachineBasicBlock::predecessors(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::remove_if(), llvm::MachineLoopInfo::removeBlock(), llvm::TargetInstrInfo::removeBranch(), llvm::TargetMachine::requiresStructuredCFG(), llvm::TargetInstrInfo::reverseBranchCondition(), rotate, llvm::MachinePostDominatorTree::runOnMachineFunction(), llvm::MachineBasicBlock::setAlignment(), llvm::AnalysisUsage::setPreservesAll(), llvm::SmallVectorBase::size(), llvm::MachineFunction::size(), llvm::MachineBasicBlock::succ_begin(), llvm::succ_size(), llvm::MachineBasicBlock::succ_size(), llvm::MachineBasicBlock::successors(), llvm::TailDuplicator::tailDuplicateAndUpdate(), TailDupPlacementAggressiveThreshold, TailDupPlacementThreshold, TailMergeSize, and llvm::MachineBasicBlock::updateTerminator().

◆ greaterWithBias()

static bool greaterWithBias ( BlockFrequency  A,
BlockFrequency  B,
uint64_t  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 711 of file MachineBlockPlacement.cpp.

References llvm::sys::path::append(), assert(), B, llvm::MachineBasicBlock::back(), llvm::sys::path::begin(), llvm::TailDuplicator::canTailDuplicate(), llvm::count(), llvm::dbgs(), llvm::MachinePostDominatorTree::dominates(), llvm::sys::path::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::erase(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::find(), getAdjustedProbability(), getBlockName(), llvm::MachineBranchProbabilityInfo::getEdgeProbability(), llvm::BranchProbability::getZero(), hasSameSuccessors(), llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::insert(), llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::MachineBasicBlock::isSuccessor(), LLVM_DEBUG, llvm::max(), P, llvm::MachineBasicBlock::predecessors(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::reverse(), llvm::SmallVectorBase::size(), llvm::MachineBasicBlock::succ_begin(), llvm::MachineBasicBlock::succ_end(), llvm::MachineBasicBlock::succ_size(), llvm::MachineBasicBlock::successors(), std::swap(), TailDupPlacementPenalty, TriangleChainCount, and llvm::DenseMapBase< DenseMap< KeyT, ValueT, KeyInfoT, BucketT >, KeyT, ValueT, KeyInfoT, BucketT >::try_emplace().

◆ 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 ( NumCondBranches  ,
"Number of conditional branches  
)

◆ STATISTIC() [2/4]

STATISTIC ( NumUncondBranches  ,
"Number of unconditional branches  
)

◆ STATISTIC() [3/4]

STATISTIC ( CondBranchTakenFreq  ,
"Potential frequency of taking conditional 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."), 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)."), cl::init(0), cl::Hidden)
static

◆ BranchFoldPlacement

cl::opt<bool> BranchFoldPlacement("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 544 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)
static

◆ false

block placement Basic Block Placement false

Definition at line 544 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)
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)
static

◆ JumpInstCost

cl::opt<unsigned> JumpInstCost("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)
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)
static

◆ Placement

Branch Probability Basic Block Placement

Definition at line 544 of file MachineBlockPlacement.cpp.

◆ 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)
static

◆ ProfileLikelyProb

cl::opt<unsigned> ProfileLikelyProb

◆ StaticLikelyProb

cl::opt<unsigned> StaticLikelyProb

◆ stats

void IFOrdering::stats

Definition at line 2885 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)
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)
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)
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)
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)
static

Referenced by greaterWithBias().

◆ ViewBlockFreqFuncName

cl::opt<std::string> ViewBlockFreqFuncName

◆ ViewBlockLayoutWithBFI

cl::opt<GVDAGType> ViewBlockLayoutWithBFI

Referenced by getGVDT().