LLVM
8.0.1
|
#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>
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< unsigned > | AlignAllBlock ("align-all-blocks", cl::desc("Force the alignment of all " "blocks in the function."), cl::init(0), cl::Hidden) |
static 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 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 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 cl::opt< bool > | ForceLoopColdBlock ("force-loop-cold-block", cl::desc("Force outlining cold blocks from loops."), cl::init(false), cl::Hidden) |
static 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 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 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 cl::opt< unsigned > | JumpInstCost ("jump-inst-cost", cl::desc("Cost of jump instructions."), cl::init(1), cl::Hidden) |
static 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 cl::opt< bool > | BranchFoldPlacement ("branch-fold-placement", cl::desc("Perform branch folding during placement. " "Reduces code size."), cl::init(true), cl::Hidden) |
static 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 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 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 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) |
cl::opt< unsigned > | StaticLikelyProb |
cl::opt< unsigned > | ProfileLikelyProb |
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 |
#define DEBUG_TYPE "block-placement" |
Definition at line 74 of file MachineBlockPlacement.cpp.
|
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().
|
static |
Helper to print the name of a MBB.
Only used by debug logging.
Definition at line 551 of file MachineBlockPlacement.cpp.
References llvm::dbgs(), llvm::raw_ostream::flush(), llvm::MachineBranchProbabilityInfo::getEdgeProbability(), llvm::MachineBasicBlock::getName(), llvm::BranchProbability::getOne(), LLVM_DEBUG, llvm::printMBBReference(), llvm::SmallVectorTemplateBase< T >::push_back(), and llvm::MachineBasicBlock::successors().
Referenced by getLayoutSuccessorProbThreshold(), and greaterWithBias().
|
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().
|
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().
|
static |
Check if BB
has exactly the successors in Successors
.
Definition at line 678 of file MachineBlockPlacement.cpp.
References llvm::SmallPtrSetImpl< PtrType >::count(), llvm::TailDuplicator::isSimpleBB(), llvm::TailDuplicator::shouldTailDuplicate(), llvm::SmallPtrSetImplBase::size(), llvm::MachineBasicBlock::succ_size(), and llvm::MachineBasicBlock::successors().
Referenced by greaterWithBias().
INITIALIZE_PASS_BEGIN | ( | MachineBlockPlacement | , |
DEBUG_TYPE | , | ||
"Branch Probability Basic Block Placement" | , | ||
false | , | ||
false | |||
) |
INITIALIZE_PASS_BEGIN | ( | MachineBlockPlacementStats | , |
"block-placement-stats" | , | ||
"Basic Block Placement Stats" | , | ||
false | , | ||
false | |||
) |
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" | |||
) |
|
static |
Referenced by getLayoutSuccessorProbThreshold().
|
static |
Referenced by getLayoutSuccessorProbThreshold().
|
static |
Referenced by getLayoutSuccessorProbThreshold().
DEBUG_TYPE |
Definition at line 544 of file MachineBlockPlacement.cpp.
|
static |
Referenced by getLayoutSuccessorProbThreshold().
block placement Basic Block Placement false |
Definition at line 544 of file MachineBlockPlacement.cpp.
|
static |
Referenced by getLayoutSuccessorProbThreshold().
|
static |
Referenced by getLayoutSuccessorProbThreshold().
|
static |
Referenced by getLayoutSuccessorProbThreshold().
|
static |
Referenced by getLayoutSuccessorProbThreshold().
|
static |
Referenced by getLayoutSuccessorProbThreshold().
Branch Probability Basic Block Placement |
Definition at line 544 of file MachineBlockPlacement.cpp.
|
static |
Referenced by getLayoutSuccessorProbThreshold().
void IFOrdering::stats |
Definition at line 2885 of file MachineBlockPlacement.cpp.
block placement Basic Block Placement Stats |
Definition at line 2885 of file MachineBlockPlacement.cpp.
Referenced by assertBranchOrSelectConditionHoisted(), llvm::createControlHeightReductionLegacyPass(), llvm::pdb::PDBSymbol::dumpChildStats(), dumpScopes(), getBranchInsertPoint(), llvm::coverage::LineCoverageIterator::getEnd(), llvm::pdb::PDBSymbol::getSession(), llvm::coverage::LineCoverageIterator::operator*(), and llvm::coverage::LineCoverageIterator::operator++().
|
static |
|
static |
Referenced by getLayoutSuccessorProbThreshold().
|
static |
Referenced by greaterWithBias().
|
static |
Referenced by getLayoutSuccessorProbThreshold().
|
static |
Referenced by greaterWithBias().
cl::opt<std::string> ViewBlockFreqFuncName |