Profile: set branch weight metadata with data generated from profiling.

This patch implements ProfileDataLoader which loads profile data generated by
-insert-edge-profiling and updates branch weight metadata accordingly.

Patch by Alastair Murray.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@162799 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 377 insertions, 26 deletions

diff --git a/lib/Analysis/Analysis.cpp b/lib/Analysis/Analysis.cpp
index 0ba6af93b5..87a75fd3b1 100644
--- a/lib/Analysis/Analysis.cpp
+++ b/lib/Analysis/Analysis.cpp
@@ -61,6 +61,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializePathProfileLoaderPassPass(Registry);
   initializeProfileVerifierPassPass(Registry);
   initializePathProfileVerifierPass(Registry);
+  initializeProfileMetadataLoaderPassPass(Registry);
   initializeRegionInfoPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index 96e68b4199..e461848e86 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -44,6 +44,8 @@ add_llvm_library(LLVMAnalysis
   ProfileInfoLoader.cpp
   ProfileInfoLoaderPass.cpp
   ProfileVerifierPass.cpp
+  ProfileDataLoader.cpp
+  ProfileDataLoaderPass.cpp
   RegionInfo.cpp
   RegionPass.cpp
   RegionPrinter.cpp
diff --git a/lib/Analysis/ProfileDataLoader.cpp b/lib/Analysis/ProfileDataLoader.cpp
new file mode 100644
index 0000000000..000649228a
--- /dev/null
+++ b/lib/Analysis/ProfileDataLoader.cpp
@@ -0,0 +1,186 @@
+//===- ProfileDataLoader.cpp - Load profile information from disk ---------===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The ProfileDataLoader class is used to load raw profiling data from the dump
+// file.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Module.h"
+#include "llvm/InstrTypes.h"
+#include "llvm/Analysis/ProfileDataLoader.h"
+#include "llvm/Analysis/ProfileDataTypes.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cstdio>
+#include <cstdlib>
+using namespace llvm;
+
+namespace llvm {
+
+template<>
+char ProfileDataT<Function,BasicBlock>::ID = 0;
+
+raw_ostream& operator<<(raw_ostream &O, const Function *F) {
+  return O << F->getName();
+}
+
+raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB) {
+  return O << BB->getName();
+}
+
+raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E) {
+  O << "(";
+
+  if (E.first)
+    O << E.first;
+  else
+    O << "0";
+
+  O << ",";
+
+  if (E.second)
+    O << E.second;
+  else
+    O << "0";
+
+  return O << ")";
+}
+
+} // namespace llvm
+
+/// ByteSwap - Byteswap 'Var' if 'Really' is true.  Required when the compiler
+/// host and target have different endianness.
+static inline unsigned ByteSwap(unsigned Var, bool Really) {
+  if (!Really) return Var;
+  return ((Var & (255U<< 0U)) << 24U) |
+         ((Var & (255U<< 8U)) <<  8U) |
+         ((Var & (255U<<16U)) >>  8U) |
+         ((Var & (255U<<24U)) >> 24U);
+}
+
+/// AddCounts - Add 'A' and 'B', accounting for the fact that the value of one
+/// (or both) may not be defined.
+static unsigned AddCounts(unsigned A, unsigned B) {
+  // If either value is undefined, use the other.
+  // Undefined + undefined = undefined.
+  if (A == ProfileDataLoader::Uncounted) return B;
+  if (B == ProfileDataLoader::Uncounted) return A;
+
+  // Saturate to the maximum storable value.  This could change taken/nottaken
+  // ratios, but is presumably better than wrapping and thus potentially
+  // inverting ratios.
+  unsigned long long tmp = (unsigned long long)A + (unsigned long long)B;
+  if (tmp > (unsigned long long)ProfileDataLoader::MaxCount)
+    tmp = ProfileDataLoader::MaxCount;
+  return (unsigned)tmp;
+}
+
+/// ReadProfilingData - Load 'NumEntries' items of type 'T' from file 'F'
+template <typename T>
+static void ReadProfilingData(const char *ToolName, FILE *F,
+                              std::vector<T> &Data, size_t NumEntries) {
+  // Read in the block of data...
+  if (fread(&Data[0], sizeof(T), NumEntries, F) != NumEntries) {
+    errs() << ToolName << ": profiling data truncated!\n";
+    perror(0);
+    exit(1);
+  }
+}
+
+/// ReadProfilingNumEntries - Read how many entries are in this profiling data
+/// packet.
+static unsigned ReadProfilingNumEntries(const char *ToolName, FILE *F,
+                                        bool ShouldByteSwap) {
+  std::vector<unsigned> NumEntries(1);
+  ReadProfilingData<unsigned>(ToolName, F, NumEntries, 1);
+  return ByteSwap(NumEntries[0], ShouldByteSwap);
+}
+
+/// ReadProfilingBlock - Read the number of entries in the next profiling data
+/// packet and then accumulate the entries into 'Data'.
+static void ReadProfilingBlock(const char *ToolName, FILE *F,
+                               bool ShouldByteSwap,
+                               std::vector<unsigned> &Data) {
+  // Read the number of entries...
+  unsigned NumEntries = ReadProfilingNumEntries(ToolName, F, ShouldByteSwap);
+
+  // Read in the data.
+  std::vector<unsigned> TempSpace(NumEntries);
+  ReadProfilingData<unsigned>(ToolName, F, TempSpace, (size_t)NumEntries);
+
+  // Make sure we have enough space ...
+  if (Data.size() < NumEntries)
+    Data.resize(NumEntries, ProfileDataLoader::Uncounted);
+
+  // Accumulate the data we just read into the existing data.
+  for (unsigned i = 0; i < NumEntries; ++i) {
+    Data[i] = AddCounts(ByteSwap(TempSpace[i], ShouldByteSwap), Data[i]);
+  }
+}
+
+/// ReadProfilingArgBlock - Read the command line arguments that the progam was
+/// run with when the current profiling data packet(s) were generated.
+static void ReadProfilingArgBlock(const char *ToolName, FILE *F,
+                                  bool ShouldByteSwap,
+                                  std::vector<std::string> &CommandLines) {
+  // Read the number of bytes ...
+  unsigned ArgLength = ReadProfilingNumEntries(ToolName, F, ShouldByteSwap);
+
+  // Read in the arguments (if there are any to read).  Round up the length to
+  // the nearest 4-byte multiple.
+  std::vector<char> Args(ArgLength+4);
+  if (ArgLength)
+    ReadProfilingData<char>(ToolName, F, Args, (ArgLength+3) & ~3);
+
+  // Store the arguments.
+  CommandLines.push_back(std::string(&Args[0], &Args[ArgLength]));
+}
+
+const unsigned ProfileDataLoader::Uncounted = ~0U;
+const unsigned ProfileDataLoader::MaxCount = ~0U - 1U;
+
+/// ProfileDataLoader ctor - Read the specified profiling data file, exiting
+/// the program if the file is invalid or broken.
+ProfileDataLoader::ProfileDataLoader(const char *ToolName,
+                                     const std::string &Filename)
+  : Filename(Filename) {
+  FILE *F = fopen(Filename.c_str(), "rb");
+  if (F == 0) {
+    errs() << ToolName << ": Error opening '" << Filename << "': ";
+    perror(0);
+    exit(1);
+  }
+
+  // Keep reading packets until we run out of them.
+  unsigned PacketType;
+  while (fread(&PacketType, sizeof(unsigned), 1, F) == 1) {
+    // If the low eight bits of the packet are zero, we must be dealing with an
+    // endianness mismatch.  Byteswap all words read from the profiling
+    // information.  This can happen when the compiler host and target have
+    // different endianness.
+    bool ShouldByteSwap = (char)PacketType == 0;
+    PacketType = ByteSwap(PacketType, ShouldByteSwap);
+
+    switch (PacketType) {
+      case ArgumentInfo:
+        ReadProfilingArgBlock(ToolName, F, ShouldByteSwap, CommandLines);
+        break;
+
+      case EdgeInfo:
+        ReadProfilingBlock(ToolName, F, ShouldByteSwap, EdgeCounts);
+        break;
+
+      default:
+        errs() << ToolName << ": Unknown packet type #" << PacketType << "!\n";
+        exit(1);
+    }
+  }
+
+  fclose(F);
+}
diff --git a/lib/Analysis/ProfileDataLoaderPass.cpp b/lib/Analysis/ProfileDataLoaderPass.cpp
new file mode 100644
index 0000000000..2a61a0b6ed
--- /dev/null
+++ b/lib/Analysis/ProfileDataLoaderPass.cpp
@@ -0,0 +1,188 @@
+//===- ProfileDataLoaderPass.cpp - Set branch weight metadata from prof ---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass loads profiling data from a dump file and sets branch weight
+// metadata.
+//
+// TODO: Replace all "profile-metadata-loader" strings with "profile-loader"
+// once ProfileInfo etc. has been removed.
+//
+//===----------------------------------------------------------------------===//
+#define DEBUG_TYPE "profile-metadata-loader"
+#include "llvm/BasicBlock.h"
+#include "llvm/InstrTypes.h"
+#include "llvm/Module.h"
+#include "llvm/LLVMContext.h"
+#include "llvm/MDBuilder.h"
+#include "llvm/Metadata.h"
+#include "llvm/Pass.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/Analysis/ProfileDataLoader.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Format.h"
+#include "llvm/ADT/Statistic.h"
+#include <vector>
+using namespace llvm;
+
+STATISTIC(NumEdgesRead, "The # of edges read.");
+STATISTIC(NumTermsAnnotated, "The # of terminator instructions annotated.");
+
+static cl::opt<std::string>
+ProfileMetadataFilename("profile-file", cl::init("llvmprof.out"),
+                  cl::value_desc("filename"),
+                  cl::desc("Profile file loaded by -profile-metadata-loader"));
+
+namespace {
+  /// This pass loads profiling data from a dump file and sets branch weight
+  /// metadata.
+  class ProfileMetadataLoaderPass : public ModulePass {
+    std::string Filename;
+  public:
+    static char ID; // Class identification, replacement for typeinfo
+    explicit ProfileMetadataLoaderPass(const std::string &filename = "")
+        : ModulePass(ID), Filename(filename) {
+      initializeProfileMetadataLoaderPassPass(*PassRegistry::getPassRegistry());
+      if (filename.empty()) Filename = ProfileMetadataFilename;
+    }
+
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+      AU.setPreservesAll();
+    }
+
+    virtual const char *getPassName() const {
+      return "Profile loader";
+    }
+
+    virtual void readEdge(unsigned, ProfileData&, ProfileData::Edge,
+                          std::vector<unsigned>&);
+    virtual unsigned matchEdges(Module&, ProfileData&, std::vector<unsigned>&);
+    virtual void setBranchWeightMetadata(Module&, ProfileData&);
+
+    virtual bool runOnModule(Module &M);
+  };
+}  // End of anonymous namespace
+
+char ProfileMetadataLoaderPass::ID = 0;
+INITIALIZE_PASS_BEGIN(ProfileMetadataLoaderPass, "profile-metadata-loader",
+              "Load profile information from llvmprof.out", false, true)
+INITIALIZE_PASS_END(ProfileMetadataLoaderPass, "profile-metadata-loader",
+              "Load profile information from llvmprof.out", false, true)
+
+char &llvm::ProfileMetadataLoaderPassID = ProfileMetadataLoaderPass::ID;
+
+/// createProfileMetadataLoaderPass - This function returns a Pass that loads
+/// the profiling information for the module from the specified filename,
+/// making it available to the optimizers.
+ModulePass *llvm::createProfileMetadataLoaderPass() { 
+    return new ProfileMetadataLoaderPass();
+}
+ModulePass *llvm::createProfileMetadataLoaderPass(const std::string &Filename) {
+  return new ProfileMetadataLoaderPass(Filename);
+}
+
+/// readEdge - Take the value from a profile counter and assign it to an edge.
+void ProfileMetadataLoaderPass::readEdge(unsigned ReadCount,
+                                         ProfileData &PB, ProfileData::Edge e,
+                                         std::vector<unsigned> &Counters) {
+  if (ReadCount < Counters.size()) {
+    unsigned weight = Counters[ReadCount];
+    assert(weight != ProfileDataLoader::Uncounted);
+    PB.addEdgeWeight(e, weight);
+
+    DEBUG(dbgs() << "-- Read Edge Counter for " << e
+                 << " (# "<< (ReadCount) << "): "
+                 << PB.getEdgeWeight(e) << "\n");
+  }
+}
+
+/// matchEdges - Link every profile counter with an edge.
+unsigned ProfileMetadataLoaderPass::matchEdges(Module &M, ProfileData &PB,
+                                             std::vector<unsigned> &Counters) {
+  if (Counters.size() == 0) return 0;
+
+  unsigned ReadCount = 0;
+
+  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+    if (F->isDeclaration()) continue;
+    DEBUG(dbgs() << "Loading edges in '" << F->getName() << "'\n");
+    readEdge(ReadCount++, PB, PB.getEdge(0, &F->getEntryBlock()), Counters);
+    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
+      TerminatorInst *TI = BB->getTerminator();
+      for (unsigned s = 0, e = TI->getNumSuccessors(); s != e; ++s) {
+        readEdge(ReadCount++, PB, PB.getEdge(BB,TI->getSuccessor(s)),
+                 Counters);
+      }
+    }
+  }
+
+  return ReadCount;
+}
+
+/// setBranchWeightMetadata - Translate the counter values associated with each
+/// edge into branch weights for each conditional branch (a branch with 2 or
+/// more desinations).
+void ProfileMetadataLoaderPass::setBranchWeightMetadata(Module &M,
+                                                        ProfileData &PB) {
+  for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
+    if (F->isDeclaration()) continue;
+    DEBUG(dbgs() << "Setting branch metadata in '" << F->getName() << "'\n");
+
+    for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
+      TerminatorInst *TI = BB->getTerminator();
+      unsigned NumSuccessors = TI->getNumSuccessors();
+
+      // If there is only one successor then we can not set a branch
+      // probability as the target is certain.
+      if (NumSuccessors < 2) continue;
+
+      // Load the weights of all edges leading from this terminator.
+      DEBUG(dbgs() << "-- Terminator with " << NumSuccessors
+                   << " successors:\n");
+      std::vector<uint32_t> Weights(NumSuccessors);
+      for (unsigned s = 0 ; s < NumSuccessors ; ++s) {
+          ProfileData::Edge edge = PB.getEdge(BB, TI->getSuccessor(s));
+          Weights[s] = (uint32_t)PB.getEdgeWeight(edge);
+          DEBUG(dbgs() << "---- Edge '" << edge << "' has weight "
+                       << Weights[s] << "\n");
+      }
+
+      // Set branch weight metadata.  This will set branch probabilities of
+      // 100%/0% if that is true of the dynamic execution.
+      // BranchProbabilityInfo can account for this when it loads this metadata
+      // (it gives the unexectuted branch a weight of 1 for the purposes of
+      // probability calculations).
+      MDBuilder MDB(TI->getContext());
+      MDNode *Node = MDB.createBranchWeights(Weights);
+      TI->setMetadata(LLVMContext::MD_prof, Node);
+      NumTermsAnnotated++;
+    }
+  }
+}
+
+bool ProfileMetadataLoaderPass::runOnModule(Module &M) {
+  ProfileDataLoader PDL("profile-data-loader", Filename);
+  ProfileData PB;
+
+  std::vector<unsigned> Counters = PDL.getRawEdgeCounts();
+
+  unsigned ReadCount = matchEdges(M, PB, Counters);
+
+  if (ReadCount != Counters.size()) {
+    errs() << "WARNING: profile information is inconsistent with "
+           << "the current program!\n";
+  }
+  NumEdgesRead = ReadCount;
+
+  setBranchWeightMetadata(M, PB);
+
+  return ReadCount > 0;
+}
diff --git a/lib/Analysis/ProfileInfo.cpp b/lib/Analysis/ProfileInfo.cpp
index 173de2c027..b5b7ac1e50 100644
--- a/lib/Analysis/ProfileInfo.cpp
+++ b/lib/Analysis/ProfileInfo.cpp
@@ -1016,40 +1016,14 @@ void ProfileInfoT<Function,BasicBlock>::repair(const Function *F) {
   }
 }
 
-raw_ostream& operator<<(raw_ostream &O, const Function *F) {
-  return O << F->getName();
-}
-
 raw_ostream& operator<<(raw_ostream &O, const MachineFunction *MF) {
   return O << MF->getFunction()->getName() << "(MF)";
 }
 
-raw_ostream& operator<<(raw_ostream &O, const BasicBlock *BB) {
-  return O << BB->getName();
-}
-
 raw_ostream& operator<<(raw_ostream &O, const MachineBasicBlock *MBB) {
   return O << MBB->getBasicBlock()->getName() << "(MB)";
 }
 
-raw_ostream& operator<<(raw_ostream &O, std::pair<const BasicBlock *, const BasicBlock *> E) {
-  O << "(";
-
-  if (E.first)
-    O << E.first;
-  else
-    O << "0";
-
-  O << ",";
-
-  if (E.second)
-    O << E.second;
-  else
-    O << "0";
-
-  return O << ")";
-}
-
 raw_ostream& operator<<(raw_ostream &O, std::pair<const MachineBasicBlock *, const MachineBasicBlock *> E) {
   O << "(";