//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "block-placement2"
#include "llvm/CodeGen/Passes.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
#include <algorithm>
using namespace llvm;
+#define DEBUG_TYPE "block-placement2"
+
STATISTIC(NumCondBranches, "Number of conditional branches");
STATISTIC(NumUncondBranches, "Number of uncondittional branches");
STATISTIC(CondBranchTakenFreq,
"blocks in the function."),
cl::init(0), cl::Hidden);
+static cl::opt<bool> OnlyHotBadCFGConflictCheck(
+ "only-hot-bad-cfg-conflict-check",
+ cl::desc("Only check that a hot successor doesn't have a hot predecessor."),
+ cl::init(false), cl::Hidden);
+
+static cl::opt<bool> NoBadCFGConflictCheck(
+ "no-bad-cfg-conflict-check",
+ cl::desc("Don't check whether a hot successor has a more important "
+ "predecessor."),
+ cl::init(false), cl::Hidden);
+
// FIXME: Find a good default for this flag and remove the flag.
static cl::opt<unsigned>
ExitBlockBias("block-placement-exit-block-bias",
void markChainSuccessors(BlockChain &Chain,
MachineBasicBlock *LoopHeaderBB,
SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
- const BlockFilterSet *BlockFilter = 0);
+ const BlockFilterSet *BlockFilter = nullptr);
MachineBasicBlock *selectBestSuccessor(MachineBasicBlock *BB,
BlockChain &Chain,
const BlockFilterSet *BlockFilter);
const BlockFilterSet *BlockFilter);
void buildChain(MachineBasicBlock *BB, BlockChain &Chain,
SmallVectorImpl<MachineBasicBlock *> &BlockWorkList,
- const BlockFilterSet *BlockFilter = 0);
+ const BlockFilterSet *BlockFilter = nullptr);
MachineBasicBlock *findBestLoopTop(MachineLoop &L,
const BlockFilterSet &LoopBlockSet);
MachineBasicBlock *findBestLoopExit(MachineFunction &F,
initializeMachineBlockPlacementPass(*PassRegistry::getPassRegistry());
}
- bool runOnMachineFunction(MachineFunction &F);
+ bool runOnMachineFunction(MachineFunction &F) override;
- void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<MachineBranchProbabilityInfo>();
AU.addRequired<MachineBlockFrequencyInfo>();
AU.addRequired<MachineLoopInfo>();
const BlockFilterSet *BlockFilter) {
const BranchProbability HotProb(4, 5); // 80%
- MachineBasicBlock *BestSucc = 0;
+ MachineBasicBlock *BestSucc = nullptr;
// FIXME: Due to the performance of the probability and weight routines in
// the MBPI analysis, we manually compute probabilities using the edge
// weights. This is suboptimal as it means that the somewhat subtle
continue;
}
- // Make sure that a hot successor doesn't have a globally more important
- // predecessor.
- BlockFrequency CandidateEdgeFreq
- = MBFI->getBlockFreq(BB) * SuccProb * HotProb.getCompl();
- bool BadCFGConflict = false;
- for (MachineBasicBlock::pred_iterator PI = (*SI)->pred_begin(),
- PE = (*SI)->pred_end();
- PI != PE; ++PI) {
- if (*PI == *SI || (BlockFilter && !BlockFilter->count(*PI)) ||
- BlockToChain[*PI] == &Chain)
+ if (!NoBadCFGConflictCheck) {
+ // Make sure that a hot successor doesn't have a globally more
+ // important predecessor.
+ BlockFrequency CandidateEdgeFreq =
+ OnlyHotBadCFGConflictCheck
+ ? MBFI->getBlockFreq(BB) * SuccProb
+ : MBFI->getBlockFreq(BB) * SuccProb * HotProb.getCompl();
+ bool BadCFGConflict = false;
+ for (MachineBasicBlock::pred_iterator PI = (*SI)->pred_begin(),
+ PE = (*SI)->pred_end();
+ PI != PE; ++PI) {
+ if (*PI == *SI || (BlockFilter && !BlockFilter->count(*PI)) ||
+ BlockToChain[*PI] == &Chain)
+ continue;
+ BlockFrequency PredEdgeFreq =
+ MBFI->getBlockFreq(*PI) * MBPI->getEdgeProbability(*PI, *SI);
+ if (PredEdgeFreq >= CandidateEdgeFreq) {
+ BadCFGConflict = true;
+ break;
+ }
+ }
+ if (BadCFGConflict) {
+ DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb
+ << " (prob) (non-cold CFG conflict)\n");
continue;
- BlockFrequency PredEdgeFreq
- = MBFI->getBlockFreq(*PI) * MBPI->getEdgeProbability(*PI, *SI);
- if (PredEdgeFreq >= CandidateEdgeFreq) {
- BadCFGConflict = true;
- break;
}
}
- if (BadCFGConflict) {
- DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb
- << " (prob) (non-cold CFG conflict)\n");
- continue;
- }
}
DEBUG(dbgs() << " " << getBlockName(*SI) << " -> " << SuccProb
}),
WorkList.end());
- MachineBasicBlock *BestBlock = 0;
+ MachineBasicBlock *BestBlock = nullptr;
BlockFrequency BestFreq;
for (SmallVectorImpl<MachineBasicBlock *>::iterator WBI = WorkList.begin(),
WBE = WorkList.end();
return *BlockToChain[I]->begin();
}
}
- return 0;
+ return nullptr;
}
void MachineBlockPlacement::buildChain(
<< getBlockName(L.getHeader()) << "\n");
BlockFrequency BestPredFreq;
- MachineBasicBlock *BestPred = 0;
+ MachineBasicBlock *BestPred = nullptr;
for (MachineBasicBlock::pred_iterator PI = L.getHeader()->pred_begin(),
PE = L.getHeader()->pred_end();
PI != PE; ++PI) {
// header and only rotate if safe.
BlockChain &HeaderChain = *BlockToChain[L.getHeader()];
if (!LoopBlockSet.count(*HeaderChain.begin()))
- return 0;
+ return nullptr;
BlockFrequency BestExitEdgeFreq;
unsigned BestExitLoopDepth = 0;
- MachineBasicBlock *ExitingBB = 0;
+ MachineBasicBlock *ExitingBB = nullptr;
// If there are exits to outer loops, loop rotation can severely limit
// fallthrough opportunites unless it selects such an exit. Keep a set of
// blocks where rotating to exit with that block will reach an outer loop.
// Without a candidate exiting block or with only a single block in the
// loop, just use the loop header to layout the loop.
if (!ExitingBB || L.getNumBlocks() == 1)
- return 0;
+ return nullptr;
// Also, if we have exit blocks which lead to outer loops but didn't select
// one of them as the exiting block we are rotating toward, disable loop
// rotation altogether.
if (!BlocksExitingToOuterLoop.empty() &&
!BlocksExitingToOuterLoop.count(ExitingBB))
- return 0;
+ return nullptr;
DEBUG(dbgs() << " Best exiting block: " << getBlockName(ExitingBB) << "\n");
return ExitingBB;
// If we selected just the header for the loop top, look for a potentially
// profitable exit block in the event that rotating the loop can eliminate
// branches by placing an exit edge at the bottom.
- MachineBasicBlock *ExitingBB = 0;
+ MachineBasicBlock *ExitingBB = nullptr;
if (LoopTop == L.getHeader())
ExitingBB = findBestLoopExit(F, L, LoopBlockSet);
BE = L.block_end();
BI != BE; ++BI) {
BlockChain &Chain = *BlockToChain[*BI];
- if (!UpdatedPreds.insert(&Chain))
+ if (!UpdatedPreds.insert(&Chain).second)
continue;
assert(Chain.LoopPredecessors == 0);
// the exact fallthrough behavior for.
for (;;) {
Cond.clear();
- MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch.
+ MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
if (!TII->AnalyzeBranch(*BB, TBB, FBB, Cond) || !FI->canFallThrough())
break;
DEBUG(dbgs() << "Pre-merging due to unanalyzable fallthrough: "
<< getBlockName(BB) << " -> " << getBlockName(NextBB)
<< "\n");
- Chain->merge(NextBB, 0);
+ Chain->merge(NextBB, nullptr);
FI = NextFI;
BB = NextBB;
}
for (MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
MachineBasicBlock *BB = &*FI;
BlockChain &Chain = *BlockToChain[BB];
- if (!UpdatedPreds.insert(&Chain))
+ if (!UpdatedPreds.insert(&Chain).second)
continue;
assert(Chain.LoopPredecessors == 0);
// than assert when the branch cannot be analyzed in order to remove this
// boiler plate.
Cond.clear();
- MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch.
+ MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
if (!TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) {
// The "PrevBB" is not yet updated to reflect current code layout, so,
// o. it may fall-through to a block without explict "goto" instruction
PrevBB->updateTerminator();
needUpdateBr = false;
Cond.clear();
- TBB = FBB = 0;
+ TBB = FBB = nullptr;
if (TII->AnalyzeBranch(*PrevBB, TBB, FBB, Cond)) {
// FIXME: This should never take place.
- TBB = FBB = 0;
+ TBB = FBB = nullptr;
}
}
// Fixup the last block.
Cond.clear();
- MachineBasicBlock *TBB = 0, *FBB = 0; // For AnalyzeBranch.
+ MachineBasicBlock *TBB = nullptr, *FBB = nullptr; // For AnalyzeBranch.
if (!TII->AnalyzeBranch(F.back(), TBB, FBB, Cond))
F.back().updateTerminator();
if (F.getFunction()->getAttributes().
hasAttribute(AttributeSet::FunctionIndex, Attribute::OptimizeForSize))
return;
- unsigned Align = TLI->getPrefLoopAlignment();
- if (!Align)
- return; // Don't care about loop alignment.
if (FunctionChain.begin() == FunctionChain.end())
return; // Empty chain.
if (!L)
continue;
+ unsigned Align = TLI->getPrefLoopAlignment(L);
+ if (!Align)
+ continue; // Don't care about loop alignment.
+
// If the block is cold relative to the function entry don't waste space
// aligning it.
BlockFrequency Freq = MBFI->getBlockFreq(*BI);
if (std::next(F.begin()) == F.end())
return false;
+ if (skipOptnoneFunction(*F.getFunction()))
+ return false;
+
MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
MLI = &getAnalysis<MachineLoopInfo>();
- TII = F.getTarget().getInstrInfo();
- TLI = F.getTarget().getTargetLowering();
+ TII = F.getSubtarget().getInstrInfo();
+ TLI = F.getSubtarget().getTargetLowering();
assert(BlockToChain.empty());
buildCFGChains(F);
initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry());
}
- bool runOnMachineFunction(MachineFunction &F);
+ bool runOnMachineFunction(MachineFunction &F) override;
- void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<MachineBranchProbabilityInfo>();
AU.addRequired<MachineBlockFrequencyInfo>();
AU.setPreservesAll();