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

diff --git a/include/llvm/CodeGen/Passes.h b/include/llvm/CodeGen/Passes.h
index 7d0c412a1bd5f73a53c35827875061fee35d03b9..bf440f4ccf274878d92a9dbb798008a02b059631 100644 (file)
--- a/include/llvm/CodeGen/Passes.h
+++ b/include/llvm/CodeGen/Passes.h
@@ -159,6 +159,11 @@ namespace llvm {
   /// probabilities.
   FunctionPass *createMachineBlockPlacementPass();
 
   /// 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();
   /// 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 b5344fccf8bddac3a509495100bc42005bfc8d84..47a77796082cee6471f4c242287bfc5696a792b5 100644 (file)
--- 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 initializeLowerSwitchPass(PassRegistry&);
 void initializeMachineBlockFrequencyInfoPass(PassRegistry&);
 void initializeMachineBlockPlacementPass(PassRegistry&);

+void initializeMachineBlockPlacementStatsPass(PassRegistry&);

 void initializeMachineBranchProbabilityInfoPass(PassRegistry&);
 void initializeMachineCSEPass(PassRegistry&);
 void initializeMachineDominatorTreePass(PassRegistry&);
 void initializeMachineBranchProbabilityInfoPass(PassRegistry&);
 void initializeMachineCSEPass(PassRegistry&);
 void initializeMachineDominatorTreePass(PassRegistry&);

diff --git a/lib/CodeGen/CodeGen.cpp b/lib/CodeGen/CodeGen.cpp
index a911534b2fc04e846b83a3ad337a4706c09d8eea..899baad4ce11fdd8d1b0271c8617f468f4dcc52b 100644 (file)
--- 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);
   initializeLiveVariablesPass(Registry);
   initializeMachineBlockFrequencyInfoPass(Registry);
   initializeMachineBlockPlacementPass(Registry);

+  initializeMachineBlockPlacementStatsPass(Registry);

   initializeMachineCSEPass(Registry);
   initializeMachineDominatorTreePass(Registry);
   initializeMachineLICMPass(Registry);
   initializeMachineCSEPass(Registry);
   initializeMachineDominatorTreePass(Registry);
   initializeMachineLICMPass(Registry);

diff --git a/lib/CodeGen/LLVMTargetMachine.cpp b/lib/CodeGen/LLVMTargetMachine.cpp
index 268584c06c132e0ab9aaeb37212ba7d04de63117..3e69069fa9568cb6b4f4292bd928d20c52b57942 100644 (file)
--- a/lib/CodeGen/LLVMTargetMachine.cpp
+++ b/lib/CodeGen/LLVMTargetMachine.cpp
@@ -55,6 +55,8 @@ static cl::opt<bool> DisableEarlyTailDup("disable-early-taildup", cl::Hidden,
     cl::desc("Disable pre-register allocation tail duplication"));
 static cl::opt<bool> EnableBlockPlacement("enable-block-placement",
     cl::Hidden, cl::desc("Enable probability-driven block placement"));
     cl::desc("Disable pre-register allocation tail duplication"));
 static cl::opt<bool> EnableBlockPlacement("enable-block-placement",
     cl::Hidden, cl::desc("Enable probability-driven block placement"));

+static cl::opt<bool> EnableBlockPlacementStats("enable-block-placement-stats",
+    cl::Hidden, cl::desc("Collect probability-driven block placement stats"));

 static cl::opt<bool> DisableCodePlace("disable-code-place", cl::Hidden,
     cl::desc("Disable code placement"));
 static cl::opt<bool> DisableSSC("disable-ssc", cl::Hidden,
 static cl::opt<bool> DisableCodePlace("disable-code-place", cl::Hidden,
     cl::desc("Disable code placement"));
 static cl::opt<bool> DisableSSC("disable-ssc", cl::Hidden,


@@ -499,6 +501,12 @@ bool LLVMTargetMachine::addCommonCodeGenPasses(PassManagerBase &PM,
       PM.add(createCodePlacementOptPass());
       printNoVerify(PM, "After CodePlacementOpt");
     }
       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))
   }
 
   if (addPreEmitPass(PM, OptLevel))

diff --git a/lib/CodeGen/MachineBlockPlacement.cpp b/lib/CodeGen/MachineBlockPlacement.cpp
index 21582b94c5320a9318ed2397172c9038f5bb8459..53a8779c10e78656faf1e4b413b91b36ce3177ce 100644 (file)
--- a/lib/CodeGen/MachineBlockPlacement.cpp
+++ b/lib/CodeGen/MachineBlockPlacement.cpp
@@ -48,6 +48,13 @@
 #include <algorithm>
 using namespace llvm;
 
 #include <algorithm>
 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.
 ///
 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;
 }
   // 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<MachineBranchProbabilityInfo>();
+    AU.addRequired<MachineBlockFrequencyInfo>();
+    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<MachineBranchProbabilityInfo>();
+  MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
+
+  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;
+}
+