Mark BB as annotated if its weight is > 0

[danielcdh]

Summary

Mark BB as annotated if its weight is > 0, otherwise the propagation algorithm will not be able to propagate edge weights.

[dnovillo]

LGTM with a test case.

Thanks.

[danielcdh]

Update reviewer

[danielcdh]

Add reviewers.

[danielcdh]

Add unittest to fix propagation. This equivalence class based method is still incorrect. I will have a separate patch to fix equivalence class bug.

[davidxl]

lib/Transforms/IPO/SampleProfile.cpp

253–254

I think it is clearer to rename this method 'setBlockWeight' -- what it does is to read from the samples and set the cached weight for BB and mark it as annotated.

604

Should use annotated EC's weight.

698

There seems to be a missing step to propagate weights from annotated BBs to their equivalence classes -- the later should be used in Edge propagation

[danielcdh]

lib/Transforms/IPO/SampleProfile.cpp

253–254

In another patch http://reviews.llvm.org/D13231, I changed getBlockWeight as a const member function and removed the caching (because there is no reuse), and move the setting of BlockWeights outside this function.

604

That's correct. I'll have a separate patch to fix the EC's propagation.

[dnovillo]

Let me back up a little bit. If getBlockWeight() marks the block visited all the time, then how can propagation work? getBlockWeight is only used when computing the *initial* weight of the blocks (I agree with David, it should be renamed to setBlockWeight()).

But, in looking at the code again, it doesn't seem correct to mark the block visited there. We mark them visited when we are assigning equivalence classes.

I think I'm missing something here.

[danielcdh]

computeBlockWeights assigns weights to basic blocks that has profile data and mark them as annotated. But after this step, there will still be basic blocks that are not annotated. So the propagation step works on 3 things:

• set edge weights and mark it as annotated
• set basic block weights for those unannotated basic blocks and mark them as annotated
• adjust basic block weights for those annotated basic blocks which has apparently incorrect weights

Equivalence class is not the place to set the annotated flag, it just sets the equivalence class for each basic block. In later propagation algorithm, instead of checking "IsAnnotated(BB)", we should check "IsAnnotated(BB->equivalence_class)".

Dehao

[dnovillo]

lib/Transforms/IPO/SampleProfile.cpp

439–440

clang-format this? I think it will now fit on the same line.

[danielcdh]

clang-format

[danielcdh]

rerun clang-format.

[dnovillo]

LGTM

[danielcdh]

This change exposed many errors in the original test input. Thus I integrated the EC related change into this patch so that I only need to update the test input once.

Diego and David, please help take another look at the patch. With this patch, the propagation should be very robust now.

[dnovillo]

Patch looks fine. Just a couple of final questions.

include/llvm/ProfileData/SampleProf.h

221

Sadly, I don't think there is a test case for this check I had added. With your new changes, we can now distinguish 0 from missing sample all the time, right?

lib/Transforms/IPO/SampleProfile.cpp

505

Not sure why we don't process blocks post-dominated by BB1 anymore?

[danielcdh]

include/llvm/ProfileData/SampleProf.h

221

Yes, now GetBlockCount will return std::error_code if there is no profile.

lib/Transforms/IPO/SampleProfile.cpp

505

Processing dominators should be able to cover all ECs, this is because if BB1 dominates BB2, and BB1 and BB2 are in the same EC, then BB2 also post-dominates BB1.

[danielcdh]

submitted

include/llvm/ProfileData/SampleProf.h

 class FunctionSamples {
 public:
   FunctionSamples() : TotalSamples(0), TotalHeadSamples(0) {}
   void print(raw_ostream &OS = dbgs());
   void addTotalSamples(unsigned Num) { TotalSamples += Num; }
   void addHeadSamples(unsigned Num) { TotalHeadSamples += Num; }
   void addBodySamples(int LineOffset, unsigned Discriminator, unsigned Num) {
     assert(LineOffset >= 0);
-    // When dealing with instruction weights, we use the value
-    // zero to indicate the absence of a sample. If we read an
-    // actual zero from the profile file, use the value 1 to
-    // avoid the confusion later on.
-    if (Num == 0)
-      Num = 1;
     BodySamples[LineLocation(LineOffset, Discriminator)].addSamples(Num);
   }
   void addCalledTargetSamples(int LineOffset, unsigned Discriminator,
                               std::string FName, unsigned Num) {
     assert(LineOffset >= 0);
     BodySamples[LineLocation(LineOffset, Discriminator)].addCalledTarget(FName,
                                                                          Num);
   }

lib/Transforms/IPO/SampleProfile.cpp

 }
 
 /// \brief Compute the weight of a basic block.
 ///
 /// The weight of basic block \p BB is the maximum weight of all the
 /// instructions in BB.
 ///
 /// \param BB The basic block to query.
 ///
 /// \returns the weight for \p BB.
 ErrorOr<unsigned>
 SampleProfileLoader::getBlockWeight(const BasicBlock *BB) const {
   bool Found = false;
   unsigned Weight = 0;
   for (auto &I : BB->getInstList()) {
     const ErrorOr<unsigned> &R = getInstWeight(I);
     if (R && R.get() >= Weight) {
       Weight = R.get();

 /// \param F The function to query.
 bool SampleProfileLoader::computeBlockWeights(Function &F) {
   bool Changed = false;
   DEBUG(dbgs() << "Block weights\n");
   for (const auto &BB : F) {
     ErrorOr<unsigned> Weight = getBlockWeight(&BB);
     if (Weight) {
       BlockWeights[&BB] = Weight.get();
+      VisitedBlocks.insert(&BB);
       Changed = true;
     }
     DEBUG(printBlockWeight(dbgs(), &BB));
   }
 
   return Changed;
 }
 

 /// \param BB1  Block to check.
 /// \param Descendants  Descendants of \p BB1 in either the dom or pdom tree.
 /// \param DomTree  Opposite dominator tree. If \p Descendants is filled
 ///                 with blocks from \p BB1's dominator tree, then
 ///                 this is the post-dominator tree, and vice versa.
 void SampleProfileLoader::findEquivalencesFor(
     BasicBlock *BB1, SmallVector<BasicBlock *, 8> Descendants,
     DominatorTreeBase<BasicBlock> *DomTree) {
+  const BasicBlock *EC = EquivalenceClass[BB1];
+  unsigned Weight = BlockWeights[EC];
   for (const auto *BB2 : Descendants) {
     bool IsDomParent = DomTree->dominates(BB2, BB1);
     bool IsInSameLoop = LI->getLoopFor(BB1) == LI->getLoopFor(BB2);
-    if (BB1 != BB2 && VisitedBlocks.insert(BB2).second && IsDomParent &&
-        IsInSameLoop) {
-      EquivalenceClass[BB2] = BB1;
+    if (BB1 != BB2 && IsDomParent && IsInSameLoop) {
+      EquivalenceClass[BB2] = EC;
 
       // If BB2 is heavier than BB1, make BB2 have the same weight
       // as BB1.
       //
       // Note that we don't worry about the opposite situation here
       // (when BB2 is lighter than BB1). We will deal with this
       // 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.
-      unsigned &BB1Weight = BlockWeights[BB1];
-      unsigned &BB2Weight = BlockWeights[BB2];
-      BB1Weight = std::max(BB1Weight, BB2Weight);
+      Weight = std::max(Weight, BlockWeights[BB2]);
     }
   }
+  BlockWeights[EC] = Weight;
 }
 
 /// \brief Find equivalence classes.
 ///
 /// Since samples may be missing from blocks, we can fill in the gaps by setting
 /// the weights of all the blocks in the same equivalence class to the same
 /// weight. To compute the concept of equivalence, we use dominance and loop
 /// information. Two blocks B1 and B2 are in the same equivalence class if B1
for (auto &BB : F) {
     //
     // If all those conditions hold, it means that BB2 is executed
     // as many times as BB1, so they are placed in the same equivalence
     // class by making BB2's equivalence class be BB1.
     DominatedBBs.clear();
     DT->getDescendants(BB1, DominatedBBs);
     findEquivalencesFor(BB1, DominatedBBs, PDT.get());
 
-    // Repeat the same logic for all the blocks post-dominated by BB1.
-    // We are looking for every basic block BB2 such that:
-    //
-    // 1- BB1 post-dominates BB2.
-    // 2- BB2 dominates BB1.
-    // 3- BB1 and BB2 are in the same loop nest.
-    //
-    // If all those conditions hold, BB2's equivalence class is BB1.
-    DominatedBBs.clear();
-    PDT->getDescendants(BB1, DominatedBBs);
-    findEquivalencesFor(BB1, DominatedBBs, DT.get());
-
     DEBUG(printBlockEquivalence(dbgs(), BB1));
   }
 
   // Assign weights to equivalence classes.
   //
   // All the basic blocks in the same equivalence class will execute
   // the same number of times. Since we know that the head block in
   // each equivalence class has the largest weight, assign that weight

 /// count of the basic block, if needed.
 ///
 /// \param F  Function to process.
 ///
 /// \returns  True if new weights were assigned to edges or blocks.
 bool SampleProfileLoader::propagateThroughEdges(Function &F) {
   bool Changed = false;
   DEBUG(dbgs() << "\nPropagation through edges\n");
-  for (auto &BI : F) {
-    BasicBlock *BB = &BI;
+  for (const auto &BI : F) {
+    const BasicBlock *BB = &BI;
+    const BasicBlock *EC = EquivalenceClass[BB];
 
     // Visit all the predecessor and successor edges to determine
     // which ones have a weight assigned already. Note that it doesn't
     // matter that we only keep track of a single unknown edge. The
     // only case we are interested in handling is when only a single
     // edge is unknown (see setEdgeOrBlockWeight).
     for (unsigned i = 0; i < 2; i++) {
       unsigned TotalWeight = 0;
for (unsigned i = 0; i < 2; i++) {
       //   known. In this case, this edge can be based on BB's weight.
       //   We add up all the other known edges and set the weight on
       //   the self-referential edge as we did in the previous case.
       //
       // In any other case, we must continue iterating. Eventually,
       // all edges will get a weight, or iteration will stop when
       // it reaches SampleProfileMaxPropagateIterations.
       if (NumUnknownEdges <= 1) {
-        unsigned &BBWeight = BlockWeights[BB];
+        unsigned &BBWeight = BlockWeights[EC];
         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
           // of all edge weights.
           if (TotalWeight > BBWeight) {
             BBWeight = TotalWeight;
             Changed = true;
             DEBUG(dbgs() << "All edge weights for " << BB->getName()
                          << " known. Set weight for block: ";
                   printBlockWeight(dbgs(), BB););
           }
-          if (VisitedBlocks.insert(BB).second)
+          if (VisitedBlocks.insert(EC).second)
             Changed = true;
-        } else if (NumUnknownEdges == 1 && VisitedBlocks.count(BB)) {
+        } else if (NumUnknownEdges == 1 && VisitedBlocks.count(EC)) {
           // If there is a single unknown edge and the block has been
           // visited, then we can compute E's weight.
           if (BBWeight >= TotalWeight)
             EdgeWeights[UnknownEdge] = BBWeight - TotalWeight;
           else
             EdgeWeights[UnknownEdge] = 0;
           VisitedEdges.insert(UnknownEdge);
           Changed = true;
           DEBUG(dbgs() << "Set weight for edge: ";
                 printEdgeWeight(dbgs(), UnknownEdge));
         }
-      } else if (SelfReferentialEdge.first && VisitedBlocks.count(BB)) {
+      } else if (SelfReferentialEdge.first && VisitedBlocks.count(EC)) {
         unsigned &BBWeight = BlockWeights[BB];
         // We have a self-referential edge and the weight of BB is known.
         if (BBWeight >= TotalWeight)
           EdgeWeights[SelfReferentialEdge] = BBWeight - TotalWeight;
         else
           EdgeWeights[SelfReferentialEdge] = 0;
         VisitedEdges.insert(SelfReferentialEdge);
         Changed = true;

 ///
 /// - If there is a self-referential edge, and the weight of the block is
 ///   known, the weight for that edge is set to the weight of the block
 ///   minus the weight of the other incoming edges to that block (if
 ///   known).
 void SampleProfileLoader::propagateWeights(Function &F) {
   bool Changed = true;
   unsigned i = 0;
 
   // Add an entry count to the function using the samples gathered
   // at the function entry.
   F.setEntryCount(Samples->getHeadSamples());
 
   // Before propagation starts, build, for each block, a list of
   // unique predecessors and successors. This is necessary to handle
   // identical edges in multiway branches. Since we visit all blocks and all
   // edges of the CFG, it is cleaner to build these lists once at the start

test/Transforms/SampleProfile/Inputs/branch.prof

 main:15680:0
- 0: 0
- 4: 0
- 7: 0
+ 1: 2500
+ 4: 1000
+ 5: 1000
+ 6: 800
+ 7: 500
  9: 10226
  10: 2243
  16: 0
  18: 0

test/Transforms/SampleProfile/Inputs/propagate.prof

 _Z3fooiil:58139:0
  0: 0
  1: 0
  2: 0
  4: 1
  5: 10
- 6: 0
+ 6: 2
  7: 5
  8: 3
  9: 0
  10: 0
  11: 6339
  12: 16191
  13: 8141
  16: 1
  18: 0
  19: 0

test/Transforms/SampleProfile/branch.ll

 ; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/branch.prof | opt -analyze -branch-prob | FileCheck %s
 
 ; Original C++ code for this test case:
 ;
 ; #include <stdio.h>
 ; #include <stdlib.h>
-;
+
 ; int main(int argc, char *argv[]) {
 ;   if (argc < 2)
 ;     return 1;
 ;   double result;
 ;   int limit = atoi(argv[1]);
 ;   if (limit > 100) {
-;     double s = 23.041968;
+;     double s = 23.041968 * atoi(argv[2]);
 ;     for (int u = 0; u < limit; u++) {
 ;       double x = s;
 ;       s = x + 3.049 + (double)u;
 ;       s -= s + 3.94 / x * 0.32;
 ;     }
 ;     result = s;
 ;   } else {
-;     result = 0;
+;     result = atoi(argv[2]);
 ;   }
 ;   printf("result is %lf\n", result);
 ;   return 0;
 ; }
 
 @.str = private unnamed_addr constant [15 x i8] c"result is %lf\0A\00", align 1
 
-; Function Attrs: nounwind uwtable
-define i32 @main(i32 %argc, i8** nocapture readonly %argv) #0 {
+; Function Attrs: uwtable
+define i32 @main(i32 %argc, i8** %argv) #0 {
 ; CHECK: Printing analysis 'Branch Probability Analysis' for function 'main':
 
 entry:
-  tail call void @llvm.dbg.value(metadata i32 %argc, i64 0, metadata !13, metadata !DIExpression()), !dbg !27
-  tail call void @llvm.dbg.value(metadata i8** %argv, i64 0, metadata !14, metadata !DIExpression()), !dbg !27
-  %cmp = icmp slt i32 %argc, 2, !dbg !28
-  br i1 %cmp, label %return, label %if.end, !dbg !28
-; CHECK: edge entry -> return probability is 0x00000000 / 0x80000000 = 0.00%
-; CHECK: edge entry -> if.end probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+  %retval = alloca i32, align 4
+  %argc.addr = alloca i32, align 4
+  %argv.addr = alloca i8**, align 8
+  %result = alloca double, align 8
+  %limit = alloca i32, align 4
+  %s = alloca double, align 8
+  %u = alloca i32, align 4
+  %x = alloca double, align 8
+  store i32 0, i32* %retval, align 4
+  store i32 %argc, i32* %argc.addr, align 4
+  call void @llvm.dbg.declare(metadata i32* %argc.addr, metadata !16, metadata !17), !dbg !18
+  store i8** %argv, i8*** %argv.addr, align 8
+  call void @llvm.dbg.declare(metadata i8*** %argv.addr, metadata !19, metadata !17), !dbg !20
+  %0 = load i32, i32* %argc.addr, align 4, !dbg !21
+  %cmp = icmp slt i32 %0, 2, !dbg !23
+  br i1 %cmp, label %if.then, label %if.end, !dbg !24
+; CHECK:  edge entry -> if.then probability is 0x4ccccccd / 0x80000000 = 60.00%
+; CHECK:  edge entry -> if.end probability is 0x33333333 / 0x80000000 = 40.00%
+
+if.then:                                          ; preds = %entry
+  store i32 1, i32* %retval, align 4, !dbg !25
+  br label %return, !dbg !25
 
 if.end:                                           ; preds = %entry
-  %arrayidx = getelementptr inbounds i8*, i8** %argv, i64 1, !dbg !30
-  %0 = load i8*, i8** %arrayidx, align 8, !dbg !30, !tbaa !31
-  %call = tail call i32 @atoi(i8* %0) #4, !dbg !30
-  tail call void @llvm.dbg.value(metadata i32 %call, i64 0, metadata !17, metadata !DIExpression()), !dbg !30
-  %cmp1 = icmp sgt i32 %call, 100, !dbg !35
-  br i1 %cmp1, label %for.body, label %if.end6, !dbg !35
-; CHECK: edge if.end -> for.body probability is 0x00000000 / 0x80000000 = 0.00%
-; CHECK: edge if.end -> if.end6 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
-
-for.body:                                         ; preds = %if.end, %for.body
-  %u.016 = phi i32 [ %inc, %for.body ], [ 0, %if.end ]
-  %s.015 = phi double [ %sub, %for.body ], [ 0x40370ABE6A337A81, %if.end ]
-  %add = fadd double %s.015, 3.049000e+00, !dbg !36
-  %conv = sitofp i32 %u.016 to double, !dbg !36
-  %add4 = fadd double %add, %conv, !dbg !36
-  tail call void @llvm.dbg.value(metadata double %add4, i64 0, metadata !18, metadata !DIExpression()), !dbg !36
-  %div = fdiv double 3.940000e+00, %s.015, !dbg !37
-  %mul = fmul double %div, 3.200000e-01, !dbg !37
-  %add5 = fadd double %add4, %mul, !dbg !37
-  %sub = fsub double %add4, %add5, !dbg !37
-  tail call void @llvm.dbg.value(metadata double %sub, i64 0, metadata !18, metadata !DIExpression()), !dbg !37
-  %inc = add nsw i32 %u.016, 1, !dbg !38
-  tail call void @llvm.dbg.value(metadata i32 %inc, i64 0, metadata !21, metadata !DIExpression()), !dbg !38
-  %exitcond = icmp eq i32 %inc, %call, !dbg !38
-  br i1 %exitcond, label %if.end6, label %for.body, !dbg !38
-; CHECK: edge for.body -> if.end6 probability is 0x00000000 / 0x80000000 = 0.00%
-; CHECK: edge for.body -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
-
-if.end6:                                          ; preds = %for.body, %if.end
-  %result.0 = phi double [ 0.000000e+00, %if.end ], [ %sub, %for.body ]
-  %call7 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i64 0, i64 0), double %result.0), !dbg !39
-  br label %return, !dbg !40
-; CHECK: edge if.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
-
-return:                                           ; preds = %entry, %if.end6
-  %retval.0 = phi i32 [ 0, %if.end6 ], [ 1, %entry ]
-  ret i32 %retval.0, !dbg !41
+  call void @llvm.dbg.declare(metadata double* %result, metadata !26, metadata !17), !dbg !27
+  call void @llvm.dbg.declare(metadata i32* %limit, metadata !28, metadata !17), !dbg !29
+  %1 = load i8**, i8*** %argv.addr, align 8, !dbg !30
+  %arrayidx = getelementptr inbounds i8*, i8** %1, i64 1, !dbg !30
+  %2 = load i8*, i8** %arrayidx, align 8, !dbg !30
+  %call = call i32 @atoi(i8* %2) #4, !dbg !31
+  store i32 %call, i32* %limit, align 4, !dbg !29
+  %3 = load i32, i32* %limit, align 4, !dbg !32
+  %cmp1 = icmp sgt i32 %3, 100, !dbg !34
+  br i1 %cmp1, label %if.then.2, label %if.else, !dbg !35
+; CHECK: edge if.end -> if.then.2 probability is 0x66666666 / 0x80000000 = 80.00%
+; CHECK: edge if.end -> if.else probability is 0x1999999a / 0x80000000 = 20.00%
+
+if.then.2:                                        ; preds = %if.end
+  call void @llvm.dbg.declare(metadata double* %s, metadata !36, metadata !17), !dbg !38
+  %4 = load i8**, i8*** %argv.addr, align 8, !dbg !39
+  %arrayidx3 = getelementptr inbounds i8*, i8** %4, i64 2, !dbg !39
+  %5 = load i8*, i8** %arrayidx3, align 8, !dbg !39
+  %call4 = call i32 @atoi(i8* %5) #4, !dbg !40
+  %conv = sitofp i32 %call4 to double, !dbg !40
+  %mul = fmul double 0x40370ABE6A337A81, %conv, !dbg !41
+  store double %mul, double* %s, align 8, !dbg !38
+  call void @llvm.dbg.declare(metadata i32* %u, metadata !42, metadata !17), !dbg !44
+  store i32 0, i32* %u, align 4, !dbg !44
+  br label %for.cond, !dbg !45
+
+for.cond:                                         ; preds = %for.inc, %if.then.2
+  %6 = load i32, i32* %u, align 4, !dbg !46
+  %7 = load i32, i32* %limit, align 4, !dbg !48
+  %cmp5 = icmp slt i32 %6, %7, !dbg !49
+  br i1 %cmp5, label %for.body, label %for.end, !dbg !50
+
+for.body:                                         ; preds = %for.cond
+  call void @llvm.dbg.declare(metadata double* %x, metadata !51, metadata !17), !dbg !53
+  %8 = load double, double* %s, align 8, !dbg !54
+  store double %8, double* %x, align 8, !dbg !53
+  %9 = load double, double* %x, align 8, !dbg !55
+  %add = fadd double %9, 3.049000e+00, !dbg !56
+  %10 = load i32, i32* %u, align 4, !dbg !57
+  %conv6 = sitofp i32 %10 to double, !dbg !57
+  %add7 = fadd double %add, %conv6, !dbg !58
+  store double %add7, double* %s, align 8, !dbg !59
+  %11 = load double, double* %s, align 8, !dbg !60
+  %12 = load double, double* %x, align 8, !dbg !61
+  %div = fdiv double 3.940000e+00, %12, !dbg !62
+  %mul8 = fmul double %div, 3.200000e-01, !dbg !63
+  %add9 = fadd double %11, %mul8, !dbg !64
+  %13 = load double, double* %s, align 8, !dbg !65
+  %sub = fsub double %13, %add9, !dbg !65
+  store double %sub, double* %s, align 8, !dbg !65
+  br label %for.inc, !dbg !66
+
+for.inc:                                          ; preds = %for.body
+  %14 = load i32, i32* %u, align 4, !dbg !67
+  %inc = add nsw i32 %14, 1, !dbg !67
+  store i32 %inc, i32* %u, align 4, !dbg !67
+  br label %for.cond, !dbg !68
+
+for.end:                                          ; preds = %for.cond
+  %15 = load double, double* %s, align 8, !dbg !69
+  store double %15, double* %result, align 8, !dbg !70
+  br label %if.end.13, !dbg !71
+
+if.else:                                          ; preds = %if.end
+  %16 = load i8**, i8*** %argv.addr, align 8, !dbg !72
+  %arrayidx10 = getelementptr inbounds i8*, i8** %16, i64 2, !dbg !72
+  %17 = load i8*, i8** %arrayidx10, align 8, !dbg !72
+  %call11 = call i32 @atoi(i8* %17) #4, !dbg !74
+  %conv12 = sitofp i32 %call11 to double, !dbg !74
+  store double %conv12, double* %result, align 8, !dbg !75
+  br label %if.end.13
+
+if.end.13:                                        ; preds = %if.else, %for.end
+  %18 = load double, double* %result, align 8, !dbg !76
+  %call14 = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i32 0, i32 0), double %18), !dbg !77
+  store i32 0, i32* %retval, align 4, !dbg !78
+  br label %return, !dbg !78
+
+return:                                           ; preds = %if.end.13, %if.then
+  %19 = load i32, i32* %retval, align 4, !dbg !79
+  ret i32 %19, !dbg !79
 }
 
-; Function Attrs: nounwind readonly
-declare i32 @atoi(i8* nocapture) #1
+; Function Attrs: nounwind readnone
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
 
-; Function Attrs: nounwind
-declare i32 @printf(i8* nocapture readonly, ...) #2
+; Function Attrs: nounwind readonly
+declare i32 @atoi(i8*) #2
 
-; Function Attrs: nounwind readnone
-declare void @llvm.dbg.value(metadata, i64, metadata, metadata) #3
+declare i32 @printf(i8*, ...) #3
 
-attributes #0 = { nounwind uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
-attributes #1 = { nounwind readonly "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
-attributes #2 = { nounwind "less-precise-fpmad"="false" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
-attributes #3 = { nounwind readnone }
+attributes #0 = { uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind readnone }
+attributes #2 = { nounwind readonly "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #3 = { "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
 attributes #4 = { nounwind readonly }
 
 !llvm.dbg.cu = !{!0}
-!llvm.module.flags = !{!25, !42}
-!llvm.ident = !{!26}
+!llvm.module.flags = !{!13, !14}
+!llvm.ident = !{!15}
 
-!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, producer: "clang version 3.4 (trunk 192896) (llvm/trunk 192895)", isOptimized: true, emissionKind: 0, file: !1, enums: !2, retainedTypes: !2, subprograms: !3, globals: !2, imports: !2)
-!1 = !DIFile(filename: "branch.cc", directory: ".")
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 3.8.0 (trunk 248211) (llvm/trunk 248217)", isOptimized: false, runtimeVersion: 0, emissionKind: 1, enums: !2, retainedTypes: !3, subprograms: !5)
+!1 = !DIFile(filename: "test.cc", directory: "/ssd/llvm_commit")
 !2 = !{}
 !3 = !{!4}
-!4 = distinct !DISubprogram(name: "main", line: 4, isLocal: false, isDefinition: true, virtualIndex: 6, flags: DIFlagPrototyped, isOptimized: true, scopeLine: 4, file: !1, scope: !5, type: !6, function: i32 (i32, i8**)* @main, variables: !12)
-!5 = !DIFile(filename: "branch.cc", directory: ".")
-!6 = !DISubroutineType(types: !7)
-!7 = !{!8, !8, !9}
-!8 = !DIBasicType(tag: DW_TAG_base_type, name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
-!9 = !DIDerivedType(tag: DW_TAG_pointer_type, size: 64, align: 64, baseType: !10)
-!10 = !DIDerivedType(tag: DW_TAG_pointer_type, size: 64, align: 64, baseType: !11)
-!11 = !DIBasicType(tag: DW_TAG_base_type, name: "char", size: 8, align: 8, encoding: DW_ATE_signed_char)
-!12 = !{!13, !14, !15, !17, !18, !21, !23}
-!13 = !DILocalVariable(name: "argc", line: 4, arg: 1, scope: !4, file: !5, type: !8)
-!14 = !DILocalVariable(name: "argv", line: 4, arg: 2, scope: !4, file: !5, type: !9)
-!15 = !DILocalVariable(name: "result", line: 7, scope: !4, file: !5, type: !16)
-!16 = !DIBasicType(tag: DW_TAG_base_type, name: "double", size: 64, align: 64, encoding: DW_ATE_float)
-!17 = !DILocalVariable(name: "limit", line: 8, scope: !4, file: !5, type: !8)
-!18 = !DILocalVariable(name: "s", line: 10, scope: !19, file: !5, type: !16)
-!19 = distinct !DILexicalBlock(line: 9, column: 0, file: !1, scope: !20)
-!20 = distinct !DILexicalBlock(line: 9, column: 0, file: !1, scope: !4)
-!21 = !DILocalVariable(name: "u", line: 11, scope: !22, file: !5, type: !8)
-!22 = distinct !DILexicalBlock(line: 11, column: 0, file: !1, scope: !19)
-!23 = !DILocalVariable(name: "x", line: 12, scope: !24, file: !5, type: !16)
-!24 = distinct !DILexicalBlock(line: 11, column: 0, file: !1, scope: !22)
-!25 = !{i32 2, !"Dwarf Version", i32 4}
-!26 = !{!"clang version 3.4 (trunk 192896) (llvm/trunk 192895)"}
-!27 = !DILocation(line: 4, scope: !4)
-!28 = !DILocation(line: 5, scope: !29)
-!29 = distinct !DILexicalBlock(line: 5, column: 0, file: !1, scope: !4)
-!30 = !DILocation(line: 8, scope: !4)
-!31 = !{!32, !32, i64 0}
-!32 = !{!"any pointer", !33, i64 0}
-!33 = !{!"omnipotent char", !34, i64 0}
-!34 = !{!"Simple C/C++ TBAA"}
-!35 = !DILocation(line: 9, scope: !20)
-!36 = !DILocation(line: 13, scope: !24)
-!37 = !DILocation(line: 14, scope: !24)
-!38 = !DILocation(line: 11, scope: !22)
-!39 = !DILocation(line: 20, scope: !4)
-!40 = !DILocation(line: 21, scope: !4)
-!41 = !DILocation(line: 22, scope: !4)
-!42 = !{i32 1, !"Debug Info Version", i32 3}
+!4 = !DIBasicType(name: "double", size: 64, align: 64, encoding: DW_ATE_float)
+!5 = !{!6}
+!6 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 4, type: !7, isLocal: false, isDefinition: true, scopeLine: 4, flags: DIFlagPrototyped, isOptimized: false, function: i32 (i32, i8**)* @main, variables: !2)
+!7 = !DISubroutineType(types: !8)
+!8 = !{!9, !9, !10}
+!9 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!10 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !11, size: 64, align: 64)
+!11 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !12, size: 64, align: 64)
+!12 = !DIBasicType(name: "char", size: 8, align: 8, encoding: DW_ATE_signed_char)
+!13 = !{i32 2, !"Dwarf Version", i32 4}
+!14 = !{i32 2, !"Debug Info Version", i32 3}
+!15 = !{!"clang version 3.8.0 (trunk 248211) (llvm/trunk 248217)"}
+!16 = !DILocalVariable(name: "argc", arg: 1, scope: !6, file: !1, line: 4, type: !9)
+!17 = !DIExpression()
+!18 = !DILocation(line: 4, column: 15, scope: !6)
+!19 = !DILocalVariable(name: "argv", arg: 2, scope: !6, file: !1, line: 4, type: !10)
+!20 = !DILocation(line: 4, column: 27, scope: !6)
+!21 = !DILocation(line: 5, column: 8, scope: !22)
+!22 = distinct !DILexicalBlock(scope: !6, file: !1, line: 5, column: 8)
+!23 = !DILocation(line: 5, column: 13, scope: !22)
+!24 = !DILocation(line: 5, column: 8, scope: !6)
+!25 = !DILocation(line: 6, column: 6, scope: !22)
+!26 = !DILocalVariable(name: "result", scope: !6, file: !1, line: 7, type: !4)
+!27 = !DILocation(line: 7, column: 11, scope: !6)
+!28 = !DILocalVariable(name: "limit", scope: !6, file: !1, line: 8, type: !9)
+!29 = !DILocation(line: 8, column: 8, scope: !6)
+!30 = !DILocation(line: 8, column: 21, scope: !6)
+!31 = !DILocation(line: 8, column: 16, scope: !6)
+!32 = !DILocation(line: 9, column: 8, scope: !33)
+!33 = distinct !DILexicalBlock(scope: !6, file: !1, line: 9, column: 8)
+!34 = !DILocation(line: 9, column: 14, scope: !33)
+!35 = !DILocation(line: 9, column: 8, scope: !6)
+!36 = !DILocalVariable(name: "s", scope: !37, file: !1, line: 10, type: !4)
+!37 = distinct !DILexicalBlock(scope: !33, file: !1, line: 9, column: 21)
+!38 = !DILocation(line: 10, column: 13, scope: !37)
+!39 = !DILocation(line: 10, column: 34, scope: !37)
+!40 = !DILocation(line: 10, column: 29, scope: !37)
+!41 = !DILocation(line: 10, column: 27, scope: !37)
+!42 = !DILocalVariable(name: "u", scope: !43, file: !1, line: 11, type: !9)
+!43 = distinct !DILexicalBlock(scope: !37, file: !1, line: 11, column: 6)
+!44 = !DILocation(line: 11, column: 15, scope: !43)
+!45 = !DILocation(line: 11, column: 11, scope: !43)
+!46 = !DILocation(line: 11, column: 22, scope: !47)
+!47 = distinct !DILexicalBlock(scope: !43, file: !1, line: 11, column: 6)
+!48 = !DILocation(line: 11, column: 26, scope: !47)
+!49 = !DILocation(line: 11, column: 24, scope: !47)
+!50 = !DILocation(line: 11, column: 6, scope: !43)
+!51 = !DILocalVariable(name: "x", scope: !52, file: !1, line: 12, type: !4)
+!52 = distinct !DILexicalBlock(scope: !47, file: !1, line: 11, column: 38)
+!53 = !DILocation(line: 12, column: 15, scope: !52)
+!54 = !DILocation(line: 12, column: 19, scope: !52)
+!55 = !DILocation(line: 13, column: 12, scope: !52)
+!56 = !DILocation(line: 13, column: 14, scope: !52)
+!57 = !DILocation(line: 13, column: 32, scope: !52)
+!58 = !DILocation(line: 13, column: 22, scope: !52)
+!59 = !DILocation(line: 13, column: 10, scope: !52)
+!60 = !DILocation(line: 14, column: 13, scope: !52)
+!61 = !DILocation(line: 14, column: 24, scope: !52)
+!62 = !DILocation(line: 14, column: 22, scope: !52)
+!63 = !DILocation(line: 14, column: 26, scope: !52)
+!64 = !DILocation(line: 14, column: 15, scope: !52)
+!65 = !DILocation(line: 14, column: 10, scope: !52)
+!66 = !DILocation(line: 15, column: 6, scope: !52)
+!67 = !DILocation(line: 11, column: 34, scope: !47)
+!68 = !DILocation(line: 11, column: 6, scope: !47)
+!69 = !DILocation(line: 16, column: 15, scope: !37)
+!70 = !DILocation(line: 16, column: 13, scope: !37)
+!71 = !DILocation(line: 17, column: 4, scope: !37)
+!72 = !DILocation(line: 18, column: 20, scope: !73)
+!73 = distinct !DILexicalBlock(scope: !33, file: !1, line: 17, column: 11)
+!74 = !DILocation(line: 18, column: 15, scope: !73)
+!75 = !DILocation(line: 18, column: 13, scope: !73)
+!76 = !DILocation(line: 20, column: 30, scope: !6)
+!77 = !DILocation(line: 20, column: 4, scope: !6)
+!78 = !DILocation(line: 21, column: 4, scope: !6)
+!79 = !DILocation(line: 22, column: 2, scope: !6)

test/Transforms/SampleProfile/propagate.ll

if.else:                                          ; preds = %entry
   store i64 0, i64* %i, align 8, !dbg !15
   br label %for.cond, !dbg !15
 
 for.cond:                                         ; preds = %for.inc16, %if.else
   %4 = load i64, i64* %i, align 8, !dbg !15
   %5 = load i64, i64* %N.addr, align 8, !dbg !15
   %cmp1 = icmp slt i64 %4, %5, !dbg !15
   br i1 %cmp1, label %for.body, label %for.end18, !dbg !15
-; CHECK: edge for.cond -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge for.cond -> for.end18 probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge for.cond -> for.body probability is 0x745d1746 / 0x80000000 = 90.91% [HOT edge]
+; CHECK: edge for.cond -> for.end18 probability is 0x0ba2e8ba / 0x80000000 = 9.09%
 
 for.body:                                         ; preds = %for.cond
   %6 = load i64, i64* %i, align 8, !dbg !18
   %7 = load i64, i64* %N.addr, align 8, !dbg !18
   %div = sdiv i64 %7, 3, !dbg !18
   %cmp2 = icmp sgt i64 %6, %div, !dbg !18
   br i1 %cmp2, label %if.then3, label %if.end, !dbg !18
 ; CHECK: edge for.body -> if.then3 probability is 0x1999999a / 0x80000000 = 20.00%
if.else7:                                         ; preds = %if.end
   br label %for.cond8, !dbg !28
 
 for.cond8:                                        ; preds = %for.inc, %if.else7
   %13 = load i32, i32* %j, align 4, !dbg !28
   %conv9 = zext i32 %13 to i64, !dbg !28
   %14 = load i64, i64* %i, align 8, !dbg !28
   %cmp10 = icmp slt i64 %conv9, %14, !dbg !28
   br i1 %cmp10, label %for.body11, label %for.end, !dbg !28
-; CHECK: edge for.cond8 -> for.body11 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
-; CHECK: edge for.cond8 -> for.end probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge for.cond8 -> for.body11 probability is 0x5bfc7472 / 0x80000000 = 71.86%
+; CHECK: edge for.cond8 -> for.end probability is 0x24038b8e / 0x80000000 = 28.14%
 
 for.body11:                                       ; preds = %for.cond8
   %15 = load i32, i32* %j, align 4, !dbg !31
   %16 = load i32, i32* %x.addr, align 4, !dbg !31
   %add12 = add i32 %16, %15, !dbg !31
   store i32 %add12, i32* %x.addr, align 4, !dbg !31
   %17 = load i32, i32* %y.addr, align 4, !dbg !33
   %sub13 = sub nsw i32 %17, 3, !dbg !33