"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.
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);
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(); }
/// \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.
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";
}
/// 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.
// 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:
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]).
// avoid the confusion later on.
if (NumSamples == 0)
NumSamples = 1;
- FProfile.addBodySamples(LineOffset, NumSamples);
+ FProfile.addBodySamples(LineOffset, Discriminator, NumSamples);
++LineIt;
}
}
/// \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;
}
/// \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));
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;
}
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));
}
// 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);
}
}
/// \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)++;
// 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;
// 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
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;
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)
DT = DomTree;
PDT = PostDomTree;
LI = Loops;
+ Ctx = &F.getParent()->getContext();
// Compute basic block weights.
Changed |= computeBlockWeights(F);
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)
--- /dev/null
+empty:100:0
+1.-3: 10
--- /dev/null
+empty:100:0
+-1: 10
--- /dev/null
+empty:100:0
+1.3: -10
1: 5279
2: 5279
main:225715:0
-2: 5553
+2.1: 5553
3: 5391
# This indicates that at line 3 of this function, the 'then' branch
-# of the conditional is taken (discriminator '1'). However, we still
-# do not handle this case, so we compute the wrong branch weights here.
+# of the conditional is taken (discriminator '1').
3.1: 5752 _Z3sumii:5860
--- /dev/null
+foo:1000:0
+1: 1
+2: 1
+2.1: 100
+3: 100
+3.1: 5
+4: 100
+5: 1
!16 = metadata !{i32 786468, null, null, metadata !"double", i32 0, i64 64, i64 64, i64 0, i32 0, i32 4} ; [ DW_TAG_base_type ] [double] [line 0, size 64, align 64, offset 0, enc DW_ATE_float]
!17 = metadata !{i32 786688, metadata !4, metadata !"limit", metadata !5, i32 8, metadata !8, i32 0, i32 0} ; [ DW_TAG_auto_variable ] [limit] [line 8]
!18 = metadata !{i32 786688, metadata !19, metadata !"s", metadata !5, i32 10, metadata !16, i32 0, i32 0} ; [ DW_TAG_auto_variable ] [s] [line 10]
-!19 = metadata !{i32 786443, metadata !1, metadata !20, i32 9, i32 0, i32 2} ; [ DW_TAG_lexical_block ] [./branch.cc]
-!20 = metadata !{i32 786443, metadata !1, metadata !4, i32 9, i32 0, i32 1} ; [ DW_TAG_lexical_block ] [./branch.cc]
+!19 = metadata !{i32 786443, metadata !1, metadata !20, i32 9, i32 0, i32 0, i32 2} ; [ DW_TAG_lexical_block ] [./branch.cc]
+!20 = metadata !{i32 786443, metadata !1, metadata !4, i32 9, i32 0, i32 0, i32 1} ; [ DW_TAG_lexical_block ] [./branch.cc]
!21 = metadata !{i32 786688, metadata !22, metadata !"u", metadata !5, i32 11, metadata !8, i32 0, i32 0} ; [ DW_TAG_auto_variable ] [u] [line 11]
-!22 = metadata !{i32 786443, metadata !1, metadata !19, i32 11, i32 0, i32 3} ; [ DW_TAG_lexical_block ] [./branch.cc]
+!22 = metadata !{i32 786443, metadata !1, metadata !19, i32 11, i32 0, i32 0, i32 3} ; [ DW_TAG_lexical_block ] [./branch.cc]
!23 = metadata !{i32 786688, metadata !24, metadata !"x", metadata !5, i32 12, metadata !16, i32 0, i32 0} ; [ DW_TAG_auto_variable ] [x] [line 12]
-!24 = metadata !{i32 786443, metadata !1, metadata !22, i32 11, i32 0, i32 4} ; [ DW_TAG_lexical_block ] [./branch.cc]
+!24 = metadata !{i32 786443, metadata !1, metadata !22, i32 11, i32 0, i32 0, i32 4} ; [ DW_TAG_lexical_block ] [./branch.cc]
!25 = metadata !{i32 2, metadata !"Dwarf Version", i32 4}
!26 = metadata !{metadata !"clang version 3.4 (trunk 192896) (llvm/trunk 192895)"}
!27 = metadata !{i32 4, i32 0, metadata !4, null}
!28 = metadata !{i32 5, i32 0, metadata !29, null}
-!29 = metadata !{i32 786443, metadata !1, metadata !4, i32 5, i32 0, i32 0} ; [ DW_TAG_lexical_block ] [./branch.cc]
+!29 = metadata !{i32 786443, metadata !1, metadata !4, i32 5, i32 0, i32 0, i32 0} ; [ DW_TAG_lexical_block ] [./branch.cc]
!30 = metadata !{i32 8, i32 0, metadata !4, null} ; [ DW_TAG_imported_declaration ]
!31 = metadata !{metadata !32, metadata !32, i64 0}
!32 = metadata !{metadata !"any pointer", metadata !33, i64 0}
br label %while.cond, !dbg !13
while.cond: ; preds = %if.end, %entry
- %0 = load i32* %i, align 4, !dbg !13
- %inc = add nsw i32 %0, 1, !dbg !13
- store i32 %inc, i32* %i, align 4, !dbg !13
- %cmp = icmp slt i32 %0, 400000000, !dbg !13
- br i1 %cmp, label %while.body, label %while.end, !dbg !13
-; CHECK: edge while.cond -> while.body probability is 11143 / 16696 = 66.7405%
-; CHECK: edge while.cond -> while.end probability is 5553 / 16696 = 33.2595%
+ %0 = load i32* %i, align 4, !dbg !14
+ %inc = add nsw i32 %0, 1, !dbg !14
+ store i32 %inc, i32* %i, align 4, !dbg !14
+ %cmp = icmp slt i32 %0, 400000000, !dbg !14
+ br i1 %cmp, label %while.body, label %while.end, !dbg !14
+; CHECK: edge while.cond -> while.body probability is 5391 / 5392 = 99.9815% [HOT edge]
+; CHECK: edge while.cond -> while.end probability is 1 / 5392 = 0.018546%
while.body: ; preds = %while.cond
- %1 = load i32* %i, align 4, !dbg !14
- %cmp1 = icmp ne i32 %1, 100, !dbg !14
- br i1 %cmp1, label %if.then, label %if.else, !dbg !14
-; NOTE: These weights are wrong. We currently do not handle multiple
-; control flow paths in the same line. The edge while.body -> if.then
-; should be much heavier than the other one. Support for DWARF
-; discriminators will fix this.
-; CHECK: edge while.body -> if.then probability is 11143 / 22286 = 50%
-; CHECK: edge while.body -> if.else probability is 11143 / 22286 = 50%
+ %1 = load i32* %i, align 4, !dbg !16
+ %cmp1 = icmp ne i32 %1, 100, !dbg !16
+ br i1 %cmp1, label %if.then, label %if.else, !dbg !16
+; Without discriminator information, the profiler used to think that
+; both branches out of while.body had the same weight. In reality,
+; the edge while.body->if.then is taken most of the time.
+;
+; CHECK: edge while.body -> if.then probability is 5752 / 5753 = 99.9826% [HOT edge]
+; CHECK: edge while.body -> if.else probability is 1 / 5753 = 0.0173822%
+
if.then: ; preds = %while.body
- %2 = load i32* %i, align 4, !dbg !14
- %3 = load i32* %s, align 4, !dbg !14
- %call = call i32 @_Z3sumii(i32 %2, i32 %3), !dbg !14
- store i32 %call, i32* %s, align 4, !dbg !14
- br label %if.end, !dbg !14
+ %2 = load i32* %i, align 4, !dbg !18
+ %3 = load i32* %s, align 4, !dbg !18
+ %call = call i32 @_Z3sumii(i32 %2, i32 %3), !dbg !18
+ store i32 %call, i32* %s, align 4, !dbg !18
+ br label %if.end, !dbg !18
if.else: ; preds = %while.body
- store i32 30, i32* %s, align 4, !dbg !14
+ store i32 30, i32* %s, align 4, !dbg !20
br label %if.end
if.end: ; preds = %if.else, %if.then
- br label %while.cond, !dbg !14
+ br label %while.cond, !dbg !22
while.end: ; preds = %while.cond
- %4 = load i32* %s, align 4, !dbg !16
- %call2 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([11 x i8]* @.str, i32 0, i32 0), i32 %4), !dbg !16
- ret i32 0, !dbg !17
+ %4 = load i32* %s, align 4, !dbg !24
+ %call2 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([11 x i8]* @.str, i32 0, i32 0), i32 %4), !dbg !24
+ ret i32 0, !dbg !25
}
-declare i32 @printf(i8*, ...)
+declare i32 @printf(i8*, ...) #2
!llvm.dbg.cu = !{!0}
!llvm.module.flags = !{!8, !9}
!0 = metadata !{i32 786449, metadata !1, i32 4, metadata !"clang version 3.5 ", i1 false, metadata !"", i32 0, metadata !2, metadata !2, metadata !3, metadata !2, metadata !2, metadata !""} ; [ DW_TAG_compile_unit ] [./calls.cc] [DW_LANG_C_plus_plus]
!1 = metadata !{metadata !"calls.cc", metadata !"."}
-!2 = metadata !{i32 0}
+!2 = metadata !{}
!3 = metadata !{metadata !4, metadata !7}
!4 = metadata !{i32 786478, metadata !1, metadata !5, metadata !"sum", metadata !"sum", metadata !"", i32 3, metadata !6, i1 false, i1 true, i32 0, i32 0, null, i32 256, i1 false, i32 (i32, i32)* @_Z3sumii, null, null, metadata !2, i32 3} ; [ DW_TAG_subprogram ] [line 3] [def] [sum]
!5 = metadata !{i32 786473, metadata !1} ; [ DW_TAG_file_type ] [./calls.cc]
!11 = metadata !{i32 4, i32 0, metadata !4, null}
!12 = metadata !{i32 8, i32 0, metadata !7, null} ; [ DW_TAG_imported_declaration ]
!13 = metadata !{i32 9, i32 0, metadata !7, null}
-!14 = metadata !{i32 10, i32 0, metadata !15, null}
-!15 = metadata !{i32 786443, metadata !1, metadata !7, i32 10, i32 0, i32 0} ; [ DW_TAG_lexical_block ] [./calls.cc]
-!16 = metadata !{i32 11, i32 0, metadata !7, null}
-!17 = metadata !{i32 12, i32 0, metadata !7, null}
+!14 = metadata !{i32 9, i32 0, metadata !15, null}
+!15 = metadata !{i32 786443, metadata !1, metadata !7, i32 9, i32 0, i32 1, i32 1} ; [ DW_TAG_lexical_block ] [./calls.cc]
+!16 = metadata !{i32 10, i32 0, metadata !17, null}
+!17 = metadata !{i32 786443, metadata !1, metadata !7, i32 10, i32 0, i32 0, i32 0} ; [ DW_TAG_lexical_block ] [./calls.cc]
+!18 = metadata !{i32 10, i32 0, metadata !19, null}
+!19 = metadata !{i32 786443, metadata !1, metadata !17, i32 10, i32 0, i32 1, i32 2} ; [ DW_TAG_lexical_block ] [./calls.cc]
+!20 = metadata !{i32 10, i32 0, metadata !21, null}
+!21 = metadata !{i32 786443, metadata !1, metadata !17, i32 10, i32 0, i32 2, i32 3} ; [ DW_TAG_lexical_block ] [./calls.cc]
+!22 = metadata !{i32 10, i32 0, metadata !23, null}
+!23 = metadata !{i32 786443, metadata !1, metadata !17, i32 10, i32 0, i32 3, i32 4} ; [ DW_TAG_lexical_block ] [./calls.cc]
+!24 = metadata !{i32 11, i32 0, metadata !7, null}
+!25 = metadata !{i32 12, i32 0, metadata !7, null}
--- /dev/null
+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/discriminator.prof | opt -analyze -branch-prob | FileCheck %s
+
+; Original code
+;
+; 1 int foo(int i) {
+; 2 int x = 0;
+; 3 while (i < 100) {
+; 4 if (i < 5) x--;
+; 5 i++;
+; 6 }
+; 7 return x;
+; 8 }
+;
+; In this test, if the loop is executed 100 times, the decrement operation
+; at line 4 should only execute 5 times. This is reflected in the profile
+; data for line offset 3. In Inputs/discriminator.prof, we have:
+;
+; 3: 100
+; 3.1: 5
+;
+; This means that the predicate 'i < 5' (line 3) is executed 100 times,
+; but the then branch (line 3.1) is only executed 5 times.
+
+define i32 @foo(i32 %i) #0 {
+; CHECK: Printing analysis 'Branch Probability Analysis' for function 'foo':
+entry:
+ %i.addr = alloca i32, align 4
+ %x = alloca i32, align 4
+ store i32 %i, i32* %i.addr, align 4
+ store i32 0, i32* %x, align 4, !dbg !10
+ br label %while.cond, !dbg !11
+
+while.cond: ; preds = %if.end, %entry
+ %0 = load i32* %i.addr, align 4, !dbg !12
+ %cmp = icmp slt i32 %0, 100, !dbg !12
+ br i1 %cmp, label %while.body, label %while.end, !dbg !12
+; CHECK: edge while.cond -> while.body probability is 100 / 101 = 99.0099% [HOT edge]
+; CHECK: edge while.cond -> while.end probability is 1 / 101 = 0.990099%
+
+while.body: ; preds = %while.cond
+ %1 = load i32* %i.addr, align 4, !dbg !14
+ %cmp1 = icmp slt i32 %1, 50, !dbg !14
+ br i1 %cmp1, label %if.then, label %if.end, !dbg !14
+; CHECK: edge while.body -> if.then probability is 5 / 100 = 5%
+; CHECK: edge while.body -> if.end probability is 95 / 100 = 95% [HOT edge]
+
+if.then: ; preds = %while.body
+ %2 = load i32* %x, align 4, !dbg !17
+ %dec = add nsw i32 %2, -1, !dbg !17
+ store i32 %dec, i32* %x, align 4, !dbg !17
+ br label %if.end, !dbg !17
+
+if.end: ; preds = %if.then, %while.body
+ %3 = load i32* %i.addr, align 4, !dbg !19
+ %inc = add nsw i32 %3, 1, !dbg !19
+ store i32 %inc, i32* %i.addr, align 4, !dbg !19
+ br label %while.cond, !dbg !20
+
+while.end: ; preds = %while.cond
+ %4 = load i32* %x, align 4, !dbg !21
+ ret i32 %4, !dbg !21
+}
+
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!7, !8}
+!llvm.ident = !{!9}
+
+!0 = metadata !{i32 786449, metadata !1, i32 12, metadata !"clang version 3.5 ", i1 false, metadata !"", i32 0, metadata !2, metadata !2, metadata !3, metadata !2, metadata !2, metadata !""} ; [ DW_TAG_compile_unit ] [discriminator.c] [DW_LANG_C99]
+!1 = metadata !{metadata !"discriminator.c", metadata !"."}
+!2 = metadata !{}
+!3 = metadata !{metadata !4}
+!4 = metadata !{i32 786478, metadata !1, metadata !5, metadata !"foo", metadata !"foo", metadata !"", i32 1, metadata !6, i1 false, i1 true, i32 0, i32 0, null, i32 256, i1 false, i32 (i32)* @foo, null, null, metadata !2, i32 1} ; [ DW_TAG_subprogram ] [line 1] [def] [foo]
+!5 = metadata !{i32 786473, metadata !1} ; [ DW_TAG_file_type ] [discriminator.c]
+!6 = metadata !{i32 786453, i32 0, null, metadata !"", i32 0, i64 0, i64 0, i64 0, i32 0, null, metadata !2, i32 0, null, null, null} ; [ DW_TAG_subroutine_type ] [line 0, size 0, align 0, offset 0] [from ]
+!7 = metadata !{i32 2, metadata !"Dwarf Version", i32 4}
+!8 = metadata !{i32 1, metadata !"Debug Info Version", i32 1}
+!9 = metadata !{metadata !"clang version 3.5 "}
+!10 = metadata !{i32 2, i32 0, metadata !4, null}
+!11 = metadata !{i32 3, i32 0, metadata !4, null}
+!12 = metadata !{i32 3, i32 0, metadata !13, null}
+!13 = metadata !{i32 786443, metadata !1, metadata !4, i32 3, i32 0, i32 1, i32 2} ; [ DW_TAG_lexical_block ] [discriminator.c]
+!14 = metadata !{i32 4, i32 0, metadata !15, null}
+!15 = metadata !{i32 786443, metadata !1, metadata !16, i32 4, i32 0, i32 0, i32 1} ; [ DW_TAG_lexical_block ] [discriminator.c]
+!16 = metadata !{i32 786443, metadata !1, metadata !4, i32 3, i32 0, i32 0, i32 0} ; [ DW_TAG_lexical_block ] [discriminator.c]
+!17 = metadata !{i32 4, i32 0, metadata !18, null}
+!18 = metadata !{i32 786443, metadata !1, metadata !15, i32 4, i32 0, i32 1, i32 3} ; [ DW_TAG_lexical_block ] [discriminator.c]
+!19 = metadata !{i32 5, i32 0, metadata !16, null}
+!20 = metadata !{i32 6, i32 0, metadata !16, null}
+!21 = metadata !{i32 7, i32 0, metadata !4, null}
!9 = metadata !{i32 1, metadata !"Debug Info Version", i32 1}
!10 = metadata !{metadata !"clang version 3.5 "}
!11 = metadata !{i32 4, i32 0, metadata !12, null}
-!12 = metadata !{i32 786443, metadata !1, metadata !4, i32 4, i32 0, i32 0} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!12 = metadata !{i32 786443, metadata !1, metadata !4, i32 4, i32 0, i32 0, i32 0} ; [ DW_TAG_lexical_block ] [propagate.cc]
!13 = metadata !{i32 5, i32 0, metadata !14, null}
-!14 = metadata !{i32 786443, metadata !1, metadata !12, i32 4, i32 0, i32 1} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!14 = metadata !{i32 786443, metadata !1, metadata !12, i32 4, i32 0, i32 0, i32 1} ; [ DW_TAG_lexical_block ] [propagate.cc]
!15 = metadata !{i32 7, i32 0, metadata !16, null}
-!16 = metadata !{i32 786443, metadata !1, metadata !17, i32 7, i32 0, i32 3} ; [ DW_TAG_lexical_block ] [propagate.cc]
-!17 = metadata !{i32 786443, metadata !1, metadata !12, i32 6, i32 0, i32 2} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!16 = metadata !{i32 786443, metadata !1, metadata !17, i32 7, i32 0, i32 0, i32 3} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!17 = metadata !{i32 786443, metadata !1, metadata !12, i32 6, i32 0, i32 0, i32 2} ; [ DW_TAG_lexical_block ] [propagate.cc]
!18 = metadata !{i32 8, i32 0, metadata !19, null} ; [ DW_TAG_imported_declaration ]
-!19 = metadata !{i32 786443, metadata !1, metadata !20, i32 8, i32 0, i32 5} ; [ DW_TAG_lexical_block ] [propagate.cc]
-!20 = metadata !{i32 786443, metadata !1, metadata !16, i32 7, i32 0, i32 4} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!19 = metadata !{i32 786443, metadata !1, metadata !20, i32 8, i32 0, i32 0, i32 5} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!20 = metadata !{i32 786443, metadata !1, metadata !16, i32 7, i32 0, i32 0, i32 4} ; [ DW_TAG_lexical_block ] [propagate.cc]
!21 = metadata !{i32 9, i32 0, metadata !19, null}
!22 = metadata !{i32 10, i32 0, metadata !23, null}
-!23 = metadata !{i32 786443, metadata !1, metadata !20, i32 10, i32 0, i32 6} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!23 = metadata !{i32 786443, metadata !1, metadata !20, i32 10, i32 0, i32 0, i32 6} ; [ DW_TAG_lexical_block ] [propagate.cc]
!24 = metadata !{i32 11, i32 0, metadata !25, null}
-!25 = metadata !{i32 786443, metadata !1, metadata !23, i32 10, i32 0, i32 7} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!25 = metadata !{i32 786443, metadata !1, metadata !23, i32 10, i32 0, i32 0, i32 7} ; [ DW_TAG_lexical_block ] [propagate.cc]
!26 = metadata !{i32 12, i32 0, metadata !25, null}
!27 = metadata !{i32 13, i32 0, metadata !25, null}
!28 = metadata !{i32 14, i32 0, metadata !29, null}
-!29 = metadata !{i32 786443, metadata !1, metadata !30, i32 14, i32 0, i32 9} ; [ DW_TAG_lexical_block ] [propagate.cc]
-!30 = metadata !{i32 786443, metadata !1, metadata !23, i32 13, i32 0, i32 8} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!29 = metadata !{i32 786443, metadata !1, metadata !30, i32 14, i32 0, i32 0, i32 9} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!30 = metadata !{i32 786443, metadata !1, metadata !23, i32 13, i32 0, i32 0, i32 8} ; [ DW_TAG_lexical_block ] [propagate.cc]
!31 = metadata !{i32 15, i32 0, metadata !32, null}
-!32 = metadata !{i32 786443, metadata !1, metadata !29, i32 14, i32 0, i32 10} ; [ DW_TAG_lexical_block ] [propagate.cc]
+!32 = metadata !{i32 786443, metadata !1, metadata !29, i32 14, i32 0, i32 0, i32 10} ; [ DW_TAG_lexical_block ] [propagate.cc]
!33 = metadata !{i32 16, i32 0, metadata !32, null}
!34 = metadata !{i32 17, i32 0, metadata !32, null}
!35 = metadata !{i32 19, i32 0, metadata !20, null}
; RUN: not opt < %s -sample-profile -sample-profile-file=missing.prof 2>&1 | FileCheck -check-prefix=MISSING-FILE %s
; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_fn_header.prof 2>&1 | FileCheck -check-prefix=BAD-FN-HEADER %s
; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_sample_line.prof 2>&1 | FileCheck -check-prefix=BAD-SAMPLE-LINE %s
+; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_line_values.prof 2>&1 | FileCheck -check-prefix=BAD-LINE-VALUES %s
+; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_discriminator_value.prof 2>&1 | FileCheck -check-prefix=BAD-DISCRIMINATOR-VALUE %s
+; RUN: not opt < %s -sample-profile -sample-profile-file=%S/Inputs/bad_samples.prof 2>&1 | FileCheck -check-prefix=BAD-SAMPLES %s
define void @empty() {
entry:
; MISSING-FILE: LLVM ERROR: Could not open file missing.prof:
; BAD-FN-HEADER: LLVM ERROR: {{.*}}bad_fn_header.prof:1: Expected 'mangled_name:NUM:NUM', found empty:100:BAD
; BAD-SAMPLE-LINE: LLVM ERROR: {{.*}}bad_sample_line.prof:3: Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found 1: BAD
+; BAD-LINE-VALUES: LLVM ERROR: {{.*}}bad_line_values.prof:2: Expected 'mangled_name:NUM:NUM', found -1: 10
+; BAD-DISCRIMINATOR-VALUE: LLVM ERROR: {{.*}}bad_discriminator_value.prof:2: Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found 1.-3: 10
+; BAD-SAMPLES: LLVM ERROR: {{.*}}bad_samples.prof:2: Expected 'NUM[.NUM]: NUM[ mangled_name:NUM]*', found 1.3: -10