From 37efc9fe42a4867c81526cac7fca9fe0ea04a484 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Wed, 2 Nov 2011 07:17:12 +0000 Subject: [PATCH] Begin collecting some of the statistics for block placement discussed on the mailing list. Suggestions for other statistics to collect would be awesome. =] Currently these are implemented as a separate pass guarded by a separate flag. I'm not thrilled by that, but I wanted to be able to collect the statistics for the old code placement as well as the new in order to have a point of comparison. I'm planning on folding them into the single pass if / when there is only one pass of interest. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143537 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/Passes.h | 5 ++ include/llvm/InitializePasses.h | 1 + lib/CodeGen/CodeGen.cpp | 1 + lib/CodeGen/LLVMTargetMachine.cpp | 8 +++ lib/CodeGen/MachineBlockPlacement.cpp | 83 +++++++++++++++++++++++++++ 5 files changed, 98 insertions(+) diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h index 7d0c412a1bd..bf440f4ccf2 100644 --- a/include/llvm/CodeGen/Passes.h +++ b/include/llvm/CodeGen/Passes.h @@ -159,6 +159,11 @@ namespace llvm { /// probabilities. FunctionPass *createMachineBlockPlacementPass(); + /// MachineBlockPlacementStats Pass - This pass collects statistics about the + /// basic block placement using branch probabilities and block frequency + /// information. + FunctionPass *createMachineBlockPlacementStatsPass(); + /// Code Placement Pass - This pass optimize code placement and aligns loop /// headers to target specific alignment boundary. FunctionPass *createCodePlacementOptPass(); diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index b5344fccf8b..47a77796082 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -147,6 +147,7 @@ void initializeLowerInvokePass(PassRegistry&); void initializeLowerSwitchPass(PassRegistry&); void initializeMachineBlockFrequencyInfoPass(PassRegistry&); void initializeMachineBlockPlacementPass(PassRegistry&); +void initializeMachineBlockPlacementStatsPass(PassRegistry&); void initializeMachineBranchProbabilityInfoPass(PassRegistry&); void initializeMachineCSEPass(PassRegistry&); void initializeMachineDominatorTreePass(PassRegistry&); diff --git a/lib/CodeGen/CodeGen.cpp b/lib/CodeGen/CodeGen.cpp index a911534b2fc..899baad4ce1 100644 --- a/lib/CodeGen/CodeGen.cpp +++ b/lib/CodeGen/CodeGen.cpp @@ -29,6 +29,7 @@ void llvm::initializeCodeGen(PassRegistry &Registry) { initializeLiveVariablesPass(Registry); initializeMachineBlockFrequencyInfoPass(Registry); initializeMachineBlockPlacementPass(Registry); + initializeMachineBlockPlacementStatsPass(Registry); initializeMachineCSEPass(Registry); initializeMachineDominatorTreePass(Registry); initializeMachineLICMPass(Registry); diff --git a/lib/CodeGen/LLVMTargetMachine.cpp b/lib/CodeGen/LLVMTargetMachine.cpp index 268584c06c1..3e69069fa95 100644 --- a/lib/CodeGen/LLVMTargetMachine.cpp +++ b/lib/CodeGen/LLVMTargetMachine.cpp @@ -55,6 +55,8 @@ static cl::opt DisableEarlyTailDup("disable-early-taildup", cl::Hidden, cl::desc("Disable pre-register allocation tail duplication")); static cl::opt EnableBlockPlacement("enable-block-placement", cl::Hidden, cl::desc("Enable probability-driven block placement")); +static cl::opt EnableBlockPlacementStats("enable-block-placement-stats", + cl::Hidden, cl::desc("Collect probability-driven block placement stats")); static cl::opt DisableCodePlace("disable-code-place", cl::Hidden, cl::desc("Disable code placement")); static cl::opt DisableSSC("disable-ssc", cl::Hidden, @@ -499,6 +501,12 @@ bool LLVMTargetMachine::addCommonCodeGenPasses(PassManagerBase &PM, PM.add(createCodePlacementOptPass()); printNoVerify(PM, "After CodePlacementOpt"); } + + // Run a separate pass to collect block placement statistics. + if (EnableBlockPlacementStats) { + PM.add(createMachineBlockPlacementStatsPass()); + printNoVerify(PM, "After MachineBlockPlacementStats"); + } } if (addPreEmitPass(PM, OptLevel)) diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp index 21582b94c53..53a8779c10e 100644 --- a/lib/CodeGen/MachineBlockPlacement.cpp +++ b/lib/CodeGen/MachineBlockPlacement.cpp @@ -48,6 +48,13 @@ #include using namespace llvm; +STATISTIC(NumCondBranches, "Number of conditional branches"); +STATISTIC(NumUncondBranches, "Number of uncondittional branches"); +STATISTIC(CondBranchTakenFreq, + "Potential frequency of taking conditional branches"); +STATISTIC(UncondBranchTakenFreq, + "Potential frequency of taking unconditional branches"); + namespace { /// \brief A structure for storing a weighted edge. /// @@ -481,3 +488,79 @@ bool MachineBlockPlacement::runOnMachineFunction(MachineFunction &F) { // differs from the original order. return true; } + +namespace { +/// \brief A pass to compute block placement statistics. +/// +/// A separate pass to compute interesting statistics for evaluating block +/// placement. This is separate from the actual placement pass so that they can +/// be computed in the absense of any placement transformations or when using +/// alternative placement strategies. +class MachineBlockPlacementStats : public MachineFunctionPass { + /// \brief A handle to the branch probability pass. + const MachineBranchProbabilityInfo *MBPI; + + /// \brief A handle to the function-wide block frequency pass. + const MachineBlockFrequencyInfo *MBFI; + +public: + static char ID; // Pass identification, replacement for typeid + MachineBlockPlacementStats() : MachineFunctionPass(ID) { + initializeMachineBlockPlacementStatsPass(*PassRegistry::getPassRegistry()); + } + + bool runOnMachineFunction(MachineFunction &F); + + void getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.addRequired(); + AU.setPreservesAll(); + MachineFunctionPass::getAnalysisUsage(AU); + } + + const char *getPassName() const { return "Block Placement Stats"; } +}; +} + +char MachineBlockPlacementStats::ID = 0; +INITIALIZE_PASS_BEGIN(MachineBlockPlacementStats, "block-placement-stats", + "Basic Block Placement Stats", false, false) +INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo) +INITIALIZE_PASS_DEPENDENCY(MachineBlockFrequencyInfo) +INITIALIZE_PASS_END(MachineBlockPlacementStats, "block-placement-stats", + "Basic Block Placement Stats", false, false) + +FunctionPass *llvm::createMachineBlockPlacementStatsPass() { + return new MachineBlockPlacementStats(); +} + +bool MachineBlockPlacementStats::runOnMachineFunction(MachineFunction &F) { + // Check for single-block functions and skip them. + if (llvm::next(F.begin()) == F.end()) + return false; + + MBPI = &getAnalysis(); + MBFI = &getAnalysis(); + + for (MachineFunction::iterator I = F.begin(), E = F.end(); I != E; ++I) { + BlockFrequency BlockFreq = MBFI->getBlockFreq(I); + Statistic &NumBranches = (I->succ_size() > 1) ? NumCondBranches + : NumUncondBranches; + Statistic &BranchTakenFreq = (I->succ_size() > 1) ? CondBranchTakenFreq + : UncondBranchTakenFreq; + for (MachineBasicBlock::succ_iterator SI = I->succ_begin(), + SE = I->succ_end(); + SI != SE; ++SI) { + // Skip if this successor is a fallthrough. + if (I->isLayoutSuccessor(*SI)) + continue; + + BlockFrequency EdgeFreq = BlockFreq * MBPI->getEdgeProbability(I, *SI); + ++NumBranches; + BranchTakenFreq += EdgeFreq.getFrequency(); + } + } + + return false; +} + -- 2.34.1