Use discriminator information in sample profiles.

Summary:
When the sample profiles include discriminator information,
use the discriminator values to distinguish instruction weights
in different basic blocks.

This modifies the BodySamples mapping to map <line, discriminator> pairs
to weights. Instructions on the same line but different blocks, will
use different discriminator values. This, in turn, means that the blocks
may have different weights.

Other changes in this patch:

- Add tests for positive values of line offset, discriminator and samples.
- Change data types from uint32_t to unsigned and int and do additional
  validation.

Reviewers: chandlerc

CC: llvm-commits

Differential Revision: http://llvm-reviews.chandlerc.com/D2857

llvm-svn: 203508

1 files changed, 85 insertions, 40 deletions

diff --git a/llvm/lib/Transforms/Scalar/SampleProfile.cpp b/llvm/lib/Transforms/Scalar/SampleProfile.cpp
index d48e43d47c5..ab26fa5b23e 100644
--- a/llvm/lib/Transforms/Scalar/SampleProfile.cpp
+++ b/llvm/lib/Transforms/Scalar/SampleProfile.cpp
@@ -64,12 +64,51 @@ static cl::opt<unsigned> SampleProfileMaxPropagateIterations(
              "sample block/edge weights through the CFG."));
 
 namespace {
+/// \brief Represents the relative location of an instruction.
+///
+/// Instruction locations are specified by the line offset from the
+/// beginning of the function (marked by the line where the function
+/// header is) and the discriminator value within that line.
+///
+/// The discriminator value is useful to distinguish instructions
+/// that are on the same line but belong to different basic blocks
+/// (e.g., the two post-increment instructions in "if (p) x++; else y++;").
+struct InstructionLocation {
+  InstructionLocation(int L, unsigned D) : LineOffset(L), Discriminator(D) {}
+  int LineOffset;
+  unsigned Discriminator;
+};
+}
 
-typedef DenseMap<uint32_t, uint32_t> BodySampleMap;
-typedef DenseMap<BasicBlock *, uint32_t> BlockWeightMap;
+namespace llvm {
+template <> struct DenseMapInfo<InstructionLocation> {
+  typedef DenseMapInfo<int> OffsetInfo;
+  typedef DenseMapInfo<unsigned> DiscriminatorInfo;
+  static inline InstructionLocation getEmptyKey() {
+    return InstructionLocation(OffsetInfo::getEmptyKey(),
+                               DiscriminatorInfo::getEmptyKey());
+  }
+  static inline InstructionLocation getTombstoneKey() {
+    return InstructionLocation(OffsetInfo::getTombstoneKey(),
+                               DiscriminatorInfo::getTombstoneKey());
+  }
+  static inline unsigned getHashValue(InstructionLocation Val) {
+    return DenseMapInfo<std::pair<int, unsigned> >::getHashValue(
+        std::pair<int, unsigned>(Val.LineOffset, Val.Discriminator));
+  }
+  static inline bool isEqual(InstructionLocation LHS, InstructionLocation RHS) {
+    return LHS.LineOffset == RHS.LineOffset &&
+           LHS.Discriminator == RHS.Discriminator;
+  }
+};
+}
+
+namespace {
+typedef DenseMap<InstructionLocation, unsigned> BodySampleMap;
+typedef DenseMap<BasicBlock *, unsigned> BlockWeightMap;
 typedef DenseMap<BasicBlock *, BasicBlock *> EquivalenceClassMap;
 typedef std::pair<BasicBlock *, BasicBlock *> Edge;
-typedef DenseMap<Edge, uint32_t> EdgeWeightMap;
+typedef DenseMap<Edge, unsigned> EdgeWeightMap;
 typedef DenseMap<BasicBlock *, SmallVector<BasicBlock *, 8> > BlockEdgeMap;
 
 /// \brief Representation of the runtime profile for a function.
@@ -81,17 +120,18 @@ class SampleFunctionProfile {
 public:
   SampleFunctionProfile()
       : TotalSamples(0), TotalHeadSamples(0), HeaderLineno(0), DT(0), PDT(0),
-        LI(0) {}
+        LI(0), Ctx(0) {}
 
   unsigned getFunctionLoc(Function &F);
   bool emitAnnotations(Function &F, DominatorTree *DomTree,
                        PostDominatorTree *PostDomTree, LoopInfo *Loops);
-  uint32_t getInstWeight(Instruction &I);
-  uint32_t getBlockWeight(BasicBlock *B);
+  unsigned getInstWeight(Instruction &I);
+  unsigned getBlockWeight(BasicBlock *B);
   void addTotalSamples(unsigned Num) { TotalSamples += Num; }
   void addHeadSamples(unsigned Num) { TotalHeadSamples += Num; }
-  void addBodySamples(unsigned LineOffset, unsigned Num) {
-    BodySamples[LineOffset] += Num;
+  void addBodySamples(int LineOffset, unsigned Discriminator, unsigned Num) {
+    assert(LineOffset >= 0);
+    BodySamples[InstructionLocation(LineOffset, Discriminator)] += Num;
   }
   void print(raw_ostream &OS);
   void printEdgeWeight(raw_ostream &OS, Edge E);
@@ -103,7 +143,7 @@ public:
                            SmallVector<BasicBlock *, 8> Descendants,
                            DominatorTreeBase<BasicBlock> *DomTree);
   void propagateWeights(Function &F);
-  uint32_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
+  unsigned visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
   void buildEdges(Function &F);
   bool propagateThroughEdges(Function &F);
   bool empty() { return BodySamples.empty(); }
@@ -168,6 +208,9 @@ protected:
 
   /// \brief Successors for each basic block in the CFG.
   BlockEdgeMap Successors;
+
+  /// \brief LLVM context holding the debug data we need.
+  LLVMContext *Ctx;
 };
 
 /// \brief Sample-based profile reader.
@@ -276,7 +319,8 @@ void SampleFunctionProfile::print(raw_ostream &OS) {
   for (BodySampleMap::const_iterator SI = BodySamples.begin(),
                                      SE = BodySamples.end();
        SI != SE; ++SI)
-    OS << "\tline offset: " << SI->first
+    OS << "\tline offset: " << SI->first.LineOffset
+       << ", discriminator: " << SI->first.Discriminator
        << ", number of samples: " << SI->second << "\n";
   OS << "\n";
 }
@@ -364,10 +408,6 @@ void SampleModuleProfile::dump() {
 /// b- [OPTIONAL] Discriminator. This is used if the sampled program
 ///    was compiled with DWARF discriminator support
 ///    (http://wiki.dwarfstd.org/index.php?title=Path_Discriminators)
-///    This is currently only emitted by GCC and we just ignore it.
-///
-///    FIXME: Handle discriminators, since they are needed to distinguish
-///           multiple control flow within a single source LOC.
 ///
 /// c- Number of samples. This is the number of samples collected by
 ///    the profiler at this source location.
@@ -408,7 +448,7 @@ void SampleModuleProfile::loadText() {
   // mentioned more than once, and we are collecting flat profiles,
   // accumulate samples as we parse them.
   Regex HeadRE("^([^:]+):([0-9]+):([0-9]+)$");
-  Regex LineSample("^([0-9]+)(\\.[0-9]+)?: ([0-9]+)(.*)$");
+  Regex LineSample("^([0-9]+)\\.?([0-9]+)?: ([0-9]+)(.*)$");
   while (!LineIt.is_at_eof()) {
     // Read the header of each function. The function header should
     // have this format:
@@ -439,11 +479,10 @@ void SampleModuleProfile::loadText() {
             LineIt.line_number(),
             "Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found " + *LineIt);
       assert(Matches.size() == 5);
-      unsigned LineOffset, NumSamples;
+      unsigned LineOffset, NumSamples, Discriminator = 0;
       Matches[1].getAsInteger(10, LineOffset);
-
-      // FIXME: Handle discriminator information (in Matches[2]).
-
+      if (Matches[2] != "")
+        Matches[2].getAsInteger(10, Discriminator);
       Matches[3].getAsInteger(10, NumSamples);
 
       // FIXME: Handle called targets (in Matches[4]).
@@ -454,7 +493,7 @@ void SampleModuleProfile::loadText() {
       // avoid the confusion later on.
       if (NumSamples == 0)
         NumSamples = 1;
-      FProfile.addBodySamples(LineOffset, NumSamples);
+      FProfile.addBodySamples(LineOffset, Discriminator, NumSamples);
       ++LineIt;
     }
   }
@@ -471,14 +510,19 @@ void SampleModuleProfile::loadText() {
 /// \param Inst Instruction to query.
 ///
 /// \returns The profiled weight of I.
-uint32_t SampleFunctionProfile::getInstWeight(Instruction &Inst) {
-  unsigned Lineno = Inst.getDebugLoc().getLine();
+unsigned SampleFunctionProfile::getInstWeight(Instruction &Inst) {
+  DebugLoc DLoc = Inst.getDebugLoc();
+  unsigned Lineno = DLoc.getLine();
   if (Lineno < HeaderLineno)
     return 0;
-  unsigned LOffset = Lineno - HeaderLineno;
-  uint32_t Weight = BodySamples.lookup(LOffset);
-  DEBUG(dbgs() << "    " << Lineno << ":" << Inst.getDebugLoc().getCol() << ":"
-               << Inst << " (line offset: " << LOffset
+
+  DILocation DIL(DLoc.getAsMDNode(*Ctx));
+  int LOffset = Lineno - HeaderLineno;
+  unsigned Discriminator = DIL.getDiscriminator();
+  unsigned Weight =
+      BodySamples.lookup(InstructionLocation(LOffset, Discriminator));
+  DEBUG(dbgs() << "    " << Lineno << "." << Discriminator << ":" << Inst
+               << " (line offset: " << LOffset << "." << Discriminator
                << " - weight: " << Weight << ")\n");
   return Weight;
 }
@@ -492,7 +536,7 @@ uint32_t SampleFunctionProfile::getInstWeight(Instruction &Inst) {
 /// \param B The basic block to query.
 ///
 /// \returns The computed weight of B.
-uint32_t SampleFunctionProfile::getBlockWeight(BasicBlock *B) {
+unsigned SampleFunctionProfile::getBlockWeight(BasicBlock *B) {
   // If we've computed B's weight before, return it.
   std::pair<BlockWeightMap::iterator, bool> Entry =
       BlockWeights.insert(std::make_pair(B, 0));
@@ -500,9 +544,9 @@ uint32_t SampleFunctionProfile::getBlockWeight(BasicBlock *B) {
     return Entry.first->second;
 
   // Otherwise, compute and cache B's weight.
-  uint32_t Weight = 0;
+  unsigned Weight = 0;
   for (BasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
-    uint32_t InstWeight = getInstWeight(*I);
+    unsigned InstWeight = getInstWeight(*I);
     if (InstWeight > Weight)
       Weight = InstWeight;
   }
@@ -520,7 +564,7 @@ bool SampleFunctionProfile::computeBlockWeights(Function &F) {
   bool Changed = false;
   DEBUG(dbgs() << "Block weights\n");
   for (Function::iterator B = F.begin(), E = F.end(); B != E; ++B) {
-    uint32_t Weight = getBlockWeight(B);
+    unsigned Weight = getBlockWeight(B);
     Changed |= (Weight > 0);
     DEBUG(printBlockWeight(dbgs(), B));
   }
@@ -572,8 +616,8 @@ void SampleFunctionProfile::findEquivalencesFor(
       // during the propagation phase. Right now, we just want to
       // make sure that BB1 has the largest weight of all the
       // members of its equivalence set.
-      uint32_t &BB1Weight = BlockWeights[BB1];
-      uint32_t &BB2Weight = BlockWeights[BB2];
+      unsigned &BB1Weight = BlockWeights[BB1];
+      unsigned &BB2Weight = BlockWeights[BB2];
       BB1Weight = std::max(BB1Weight, BB2Weight);
     }
   }
@@ -659,7 +703,7 @@ void SampleFunctionProfile::findEquivalenceClasses(Function &F) {
 /// \param UnknownEdge  Set if E has not been visited before.
 ///
 /// \returns E's weight, if known. Otherwise, return 0.
-uint32_t SampleFunctionProfile::visitEdge(Edge E, unsigned *NumUnknownEdges,
+unsigned SampleFunctionProfile::visitEdge(Edge E, unsigned *NumUnknownEdges,
                                           Edge *UnknownEdge) {
   if (!VisitedEdges.count(E)) {
     (*NumUnknownEdges)++;
@@ -693,7 +737,7 @@ bool SampleFunctionProfile::propagateThroughEdges(Function &F) {
     // only case we are interested in handling is when only a single
     // edge is unknown (see setEdgeOrBlockWeight).
     for (unsigned i = 0; i < 2; i++) {
-      uint32_t TotalWeight = 0;
+      unsigned TotalWeight = 0;
       unsigned NumUnknownEdges = 0;
       Edge UnknownEdge, SelfReferentialEdge;
 
@@ -737,7 +781,7 @@ bool SampleFunctionProfile::propagateThroughEdges(Function &F) {
       // all edges will get a weight, or iteration will stop when
       // it reaches SampleProfileMaxPropagateIterations.
       if (NumUnknownEdges <= 1) {
-        uint32_t &BBWeight = BlockWeights[BB];
+        unsigned &BBWeight = BlockWeights[BB];
         if (NumUnknownEdges == 0) {
           // If we already know the weight of all edges, the weight of the
           // basic block can be computed. It should be no larger than the sum
@@ -764,7 +808,7 @@ bool SampleFunctionProfile::propagateThroughEdges(Function &F) {
                 printEdgeWeight(dbgs(), UnknownEdge));
         }
       } else if (SelfReferentialEdge.first && VisitedBlocks.count(BB)) {
-        uint32_t &BBWeight = BlockWeights[BB];
+        unsigned &BBWeight = BlockWeights[BB];
         // We have a self-referential edge and the weight of BB is known.
         if (BBWeight >= TotalWeight)
           EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
@@ -857,14 +901,13 @@ void SampleFunctionProfile::propagateWeights(Function &F) {
       continue;
 
     DEBUG(dbgs() << "\nGetting weights for branch at line "
-                 << TI->getDebugLoc().getLine() << ":"
-                 << TI->getDebugLoc().getCol() << ".\n");
-    SmallVector<uint32_t, 4> Weights;
+                 << TI->getDebugLoc().getLine() << ".\n");
+    SmallVector<unsigned, 4> Weights;
     bool AllWeightsZero = true;
     for (unsigned I = 0; I < TI->getNumSuccessors(); ++I) {
       BasicBlock *Succ = TI->getSuccessor(I);
       Edge E = std::make_pair(B, Succ);
-      uint32_t Weight = EdgeWeights[E];
+      unsigned Weight = EdgeWeights[E];
       DEBUG(dbgs() << "\t"; printEdgeWeight(dbgs(), E));
       Weights.push_back(Weight);
       if (Weight != 0)
@@ -970,6 +1013,7 @@ bool SampleFunctionProfile::emitAnnotations(Function &F, DominatorTree *DomTree,
   DT = DomTree;
   PDT = PostDomTree;
   LI = Loops;
+  Ctx = &F.getParent()->getContext();
 
   // Compute basic block weights.
   Changed |= computeBlockWeights(F);
@@ -991,6 +1035,7 @@ INITIALIZE_PASS_BEGIN(SampleProfileLoader, "sample-profile",
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
+INITIALIZE_PASS_DEPENDENCY(AddDiscriminators)
 INITIALIZE_PASS_END(SampleProfileLoader, "sample-profile",
                     "Sample Profile loader", false, false)