Tolerate negative offset when matching sample profile.

[danielcdh]

Summary

In some cases (as illustrated in the unittest), lineno can be less than the heade_lineno because the function body are included from some other files. In this case, offset will be negative. This patch makes clang still able to match the profile to IR in this situation.

[dnovillo]

lib/Transforms/IPO/SampleProfile.cpp

245–246

Could you factor out this offset computation and add a comment? It's not immediately obvious why the code is doing this saturation and it's used in several places. Also, what's guaranteeing that the saturation will be done on 16 bits?

[danielcdh]

Refactor.

[danielcdh]

lib/Transforms/IPO/SampleProfile.cpp

245–246

Done.

In create_llvm_prof, offset is only encoded in 16 bits.

[dnovillo]

LGTM with the additional check. Thanks.

lib/Transforms/IPO/SampleProfile.cpp

186

I would now assert that this is the case (ie, L - H fits in 16 bits). It's true that most input will come straight out of create_llvm_prof, but not all of it will. In particular, the offsets in the input profiles are specified to be 32-bit unsigned integers.

Alternatively, we could assert this in ProfileData/SampleProfReader.cpp itself. This needs to be done in all 3 readers. Perhaps that's a better place to assert this.

245–246

Sure, but we're sufficiently removed from create_llvm_prof here that it makes sense to remind the user :)

[danielcdh]

Add sanity check.

[danielcdh]

lib/Transforms/IPO/SampleProfile.cpp

186

Added sanity check for LineLocation in text and binary reader. For gcov reader, the reader itself use bit operation to set LineLocation, which ensures that it's always within 16 bits.

[danielcdh]

Update the discriminator assignment algorithm.

• If a scope has already been assigned a discriminator, do not reassign a nested discriminator for it.
• If the file and line both match, even if the column does not match, we should assign a new discriminator for the stmt.

[danielcdh]

supposed to create a new patch... please ignore the previous update sent.

new patch created in http://reviews.llvm.org/D14181

lib/Transforms/IPO/SampleProfile.cpp

protected:
   void findEquivalencesFor(BasicBlock *BB1,
                            SmallVector<BasicBlock *, 8> Descendants,
                            DominatorTreeBase<BasicBlock> *DomTree);
   void propagateWeights(Function &F);
   uint64_t visitEdge(Edge E, unsigned *NumUnknownEdges, Edge *UnknownEdge);
   void buildEdges(Function &F);
   bool propagateThroughEdges(Function &F);
   void computeDominanceAndLoopInfo(Function &F);
+  unsigned getOffset(unsigned L, unsigned H) const;
 
   /// \brief Map basic blocks to their computed weights.
   ///
   /// The weight of a basic block is defined to be the maximum
   /// of all the instruction weights in that block.
   BlockWeightMap BlockWeights;
 
   /// \brief Map edges to their computed weights.
protected:
   /// \brief Name of the profile file to load.
   StringRef Filename;
 
   /// \brief Flag indicating whether the profile input loaded successfully.
   bool ProfileIsValid;
 };
 }
 
+/// \brief Returns the offset of lineno \p L to head_lineno \p H
+///
+/// \param L  Lineno
+/// \param H  Header lineno of the function
+///
+/// \returns offset to the header lineno. 16 bits are used to represent offset.
+/// We assume that a single function will not exceed 65535 LOC.
+unsigned SampleProfileLoader::getOffset(unsigned L, unsigned H) const {
+  return (L - H) & 0xffff;
+}
+
 /// \brief Print the weight of edge \p E on stream \p OS.
 ///
 /// \param OS  Stream to emit the output to.
 /// \param E  Edge to print.
 void SampleProfileLoader::printEdgeWeight(raw_ostream &OS, Edge E) {
   OS << "weight[" << E.first->getName() << "->" << E.second->getName()
      << "]: " << EdgeWeights[E] << "\n";
 }
SampleProfileLoader::getInstWeight(const Instruction &Inst) const {
 
   const FunctionSamples *FS = findFunctionSamples(Inst);
   if (!FS)
     return std::error_code();
 
   const DILocation *DIL = DLoc;
   unsigned Lineno = DLoc.getLine();
   unsigned HeaderLineno = DIL->getScope()->getSubprogram()->getLine();
-  if (Lineno < HeaderLineno)
-    return std::error_code();
 
-  ErrorOr<uint64_t> R =
-      FS->findSamplesAt(Lineno - HeaderLineno, DIL->getDiscriminator());
+  ErrorOr<uint64_t> R = FS->findSamplesAt(getOffset(Lineno, HeaderLineno),
+                                          DIL->getDiscriminator());
   if (R)
     DEBUG(dbgs() << "    " << Lineno << "." << DIL->getDiscriminator() << ":"
                  << Inst << " (line offset: " << Lineno - HeaderLineno << "."
                  << DIL->getDiscriminator() << " - weight: " << R.get()
                  << ")\n");
   return R;
 }
 

 /// \returns The FunctionSamples pointer to the inlined instance.
 const FunctionSamples *
 SampleProfileLoader::findCalleeFunctionSamples(const CallInst &Inst) const {
   const DILocation *DIL = Inst.getDebugLoc();
   if (!DIL) {
     return nullptr;
   }
   DISubprogram *SP = DIL->getScope()->getSubprogram();
-  if (!SP || DIL->getLine() < SP->getLine())
+  if (!SP)
     return nullptr;
 
   Function *CalleeFunc = Inst.getCalledFunction();
   if (!CalleeFunc) {
     return nullptr;
   }
 
   StringRef CalleeName = CalleeFunc->getName();
   const FunctionSamples *FS = findFunctionSamples(Inst);
   if (FS == nullptr)
     return nullptr;
 
-  return FS->findFunctionSamplesAt(CallsiteLocation(
-      DIL->getLine() - SP->getLine(), DIL->getDiscriminator(), CalleeName));
+  return FS->findFunctionSamplesAt(
+      CallsiteLocation(getOffset(DIL->getLine(), SP->getLine()),
+                       DIL->getDiscriminator(), CalleeName));
 }
 
 /// \brief Get the FunctionSamples for an instruction.
 ///
 /// The FunctionSamples of an instruction \p Inst is the inlined instance
 /// in which that instruction is coming from. We traverse the inline stack
 /// of that instruction, and match it with the tree nodes in the profile.
 ///
 /// \param Inst Instruction to query.
 ///
 /// \returns the FunctionSamples pointer to the inlined instance.
 const FunctionSamples *
 SampleProfileLoader::findFunctionSamples(const Instruction &Inst) const {
   SmallVector<CallsiteLocation, 10> S;
   const DILocation *DIL = Inst.getDebugLoc();
   if (!DIL) {
     return Samples;
   }
   StringRef CalleeName;
   for (const DILocation *DIL = Inst.getDebugLoc(); DIL;
        DIL = DIL->getInlinedAt()) {
     DISubprogram *SP = DIL->getScope()->getSubprogram();
-    if (!SP || DIL->getLine() < SP->getLine())
+    if (!SP)
       return nullptr;
     if (!CalleeName.empty()) {
-      S.push_back(CallsiteLocation(DIL->getLine() - SP->getLine(),
+      S.push_back(CallsiteLocation(getOffset(DIL->getLine(), SP->getLine()),
                                    DIL->getDiscriminator(), CalleeName));
     }
     CalleeName = SP->getLinkageName();
   }
   if (S.size() == 0)
     return Samples;
   const FunctionSamples *FS = Samples;
   for (int i = S.size() - 1; i >= 0 && FS != nullptr; i--) {

test/Transforms/SampleProfile/Inputs/offset.prof

+_Z3fooi:300:1
+ 65532: 1000
+ 65533: 10
+ 65535: 990

test/Transforms/SampleProfile/offset.ll

+; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/offset.prof | opt -analyze -branch-prob | FileCheck %s
+
+; Original C++ code for this test case:
+;
+; a.cc:
+; #1
+; #2
+; #3
+; #4
+; #5 int foo(int a) {
+; #6 #include "a.b"
+; #7}
+;
+; a.b:
+; #1 if (a > 0) {
+; #2   return 10;
+; #3 } else {
+; #4   return 20;
+; #5 }
+
+; Function Attrs: nounwind uwtable
+define i32 @_Z3fooi(i32 %a) #0 {
+entry:
+  %retval = alloca i32, align 4
+  %a.addr = alloca i32, align 4
+  store i32 %a, i32* %a.addr, align 4
+  call void @llvm.dbg.declare(metadata i32* %a.addr, metadata !11, metadata !12), !dbg !13
+  %0 = load i32, i32* %a.addr, align 4, !dbg !14
+  %cmp = icmp sgt i32 %0, 0, !dbg !18
+  br i1 %cmp, label %if.then, label %if.else, !dbg !19
+; CHECK: edge entry -> if.then probability is 0x0147ae14 / 0x80000000 = 1.00%
+; CHECK: edge entry -> if.else probability is 0x7eb851ec / 0x80000000 = 99.00% [HOT edge]
+
+if.then:                                          ; preds = %entry
+  store i32 10, i32* %retval, align 4, !dbg !20
+  br label %return, !dbg !20
+
+if.else:                                          ; preds = %entry
+  store i32 20, i32* %retval, align 4, !dbg !22
+  br label %return, !dbg !22
+
+return:                                           ; preds = %if.else, %if.then
+  %1 = load i32, i32* %retval, align 4, !dbg !24
+  ret i32 %1, !dbg !24
+}
+
+; Function Attrs: nounwind readnone
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+attributes #0 = { nounwind 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"="+fxsr,+mmx,+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind readnone }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!8, !9}
+!llvm.ident = !{!10}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "clang version 3.8.0 (trunk 250750)", isOptimized: false, runtimeVersion: 0, emissionKind: 1, enums: !2, subprograms: !3)
+!1 = !DIFile(filename: "a.cc", directory: "/tmp")
+!2 = !{}
+!3 = !{!4}
+!4 = distinct !DISubprogram(name: "foo", linkageName: "_Z3fooi", scope: !1, file: !1, line: 5, type: !5, isLocal: false, isDefinition: true, scopeLine: 5, flags: DIFlagPrototyped, isOptimized: false, function: i32 (i32)* @_Z3fooi, variables: !2)
+!5 = !DISubroutineType(types: !6)
+!6 = !{!7, !7}
+!7 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!8 = !{i32 2, !"Dwarf Version", i32 4}
+!9 = !{i32 2, !"Debug Info Version", i32 3}
+!10 = !{!"clang version 3.8.0 (trunk 250750)"}
+!11 = !DILocalVariable(name: "a", arg: 1, scope: !4, file: !1, line: 5, type: !7)
+!12 = !DIExpression()
+!13 = !DILocation(line: 5, column: 13, scope: !4)
+!14 = !DILocation(line: 1, column: 5, scope: !15)
+!15 = distinct !DILexicalBlock(scope: !17, file: !16, line: 1, column: 5)
+!16 = !DIFile(filename: "./a.b", directory: "/tmp")
+!17 = !DILexicalBlockFile(scope: !4, file: !16, discriminator: 0)
+!18 = !DILocation(line: 1, column: 7, scope: !15)
+!19 = !DILocation(line: 1, column: 5, scope: !17)
+!20 = !DILocation(line: 2, column: 3, scope: !21)
+!21 = distinct !DILexicalBlock(scope: !15, file: !16, line: 1, column: 12)
+!22 = !DILocation(line: 4, column: 3, scope: !23)
+!23 = distinct !DILexicalBlock(scope: !15, file: !16, line: 3, column: 8)
+!24 = !DILocation(line: 7, column: 1, scope: !25)
+!25 = !DILexicalBlockFile(scope: !4, file: !1, discriminator: 0)