[IndVarSimplify][DebugLoc] When widening the IV increment, correctly set the debug loc.

[andreadb]

Summary

When indvars creates a wide induction variable, the debug location for the loop increment is incorrect (see below):

Example:

extern int foo(int);

int bar(int x, int *a)
  for (int i = 0; i < x; ++i)      // line 4
    a[i] = foo(i);

  return a[0];
}

Before indvars is run, the IV (induction variable) increment is performed in the loop latch at line 4:

%inc = add nsw i32 %i.06, 1, !dbg !13

Where, %i.06 is our IV, and !dbg !13 is a DILocation which refers to line 4, discriminator 2.

After indvars is run, our IV is expanded into:

%indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %for.body.lr.ph]

In particular, %indvars.iv.next is defined by instruction:

%indvars.iv.next = add nuw nsw i64 %indvars.iv, 1, !dbg !9

However, !dbg !9 is the debug loc for line 4, discriminator 1. It should have been line 4, discriminator 2.

This patch fixes the issue by propagating the correct debug location from the original loop increment instruction to the new widened increment.

Please let me know if okay to commit.

Thanks,
Andrea

[andreadb]

Hi David,

On Fri, Oct 21, 2016 at 3:54 PM, David Blaikie <[e-mail]> wrote:

I assume we would see this is a pure debug quality bug if you split the for loop header over multiple lines? (so it wasn't just a discriminator bug)?

You are correct. It is a debug quality issue, and the problem would be more evident if the loop increment is on a different line.

Which instruction/part of the loop header is it taking the line 4/disc 1 from?

It is the SCEVExpander. In particular, it is method SCEVExpander::getAddRecExprPHILiterally().

(sorry for the long explanation. I don't know how to explain it briefly since the logic is quite convoluted...)

What happens is that we delegate to the SCEVExpander the expansion of a IV phi node. We do this by by calling method 'expandCodeFor()' on the SCEVExpander object. When we call it, the normalized SCEV for the reproducible is: {0,+,1}<nuw><nsw><%for.body>.

The SCEVExpander firstly generates code for the expanded 'start' value. In our example, the start value is constant 0, so the expander doesn't have to insert new computation in the loop preheader.
Then SCEVExpander expands the code for the 'step' value. The step value is also a constant, so no extra code is inserted in the loop body. At this point, the algorithm creates a new phi node with no incoming values; the idea is that we populate the new phi node with the "expanded" 'start' value and the widened step instruction.

The logic that populates the phi node is in method 'SCEVExpander::getAddRecExprPHILiterally()' at around lines 1221:1245.
For each loop header predecessor, the algorithm adds a widened incoming value. In the case of the loop latch basic block, the insertion point for the IRBUilder points to the end of the loop latch block (Pred->getTerminator()). That means, the new IV increment will automatically obtain the debug location from Pred->getTerminator().

In our example, Pred->getTerminator() is:

br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge, !dbg !9

Where !dbg !9 is DILocation(line 4, column 3, scope !8).
!8 is a !DILexicalBlockFile with discriminator 1.

That explains why the widen IV increment is associated to line 4, discriminator 1.

I couldn't find a reasonable way to get the debug loc associated to the original loop increment from inside method getAddRecExprPHILiterally(). So, I eventually opted for this simpler patch.

Again, sorry for the long explanation.
I hope this makes sense.

-Andrea

[aprantl]

Seems fine to me.

Out of curiosity: Does the SCE debugger make use of DWARF discriminators? Or is this used for profiling?

[andreadb]

In D25872#578561, @aprantl wrote:

Seems fine to me.

Out of curiosity: Does the SCE debugger make use of DWARF discriminators? Or is this used for profiling?

Thanks Adrian and David!

I have asked to the debugger team. They just told me that tehy currently don't use discriminators. We currently use them only for profiling.

llvm/trunk/lib/Transforms/Scalar/IndVarSimplify.cpp

PHINode *WidenIV::createWideIV(SCEVExpander &Rewriter) {
   // Remembering the WideIV increment generated by SCEVExpander allows
   // widenIVUse to reuse it when widening the narrow IV's increment. We don't
   // employ a general reuse mechanism because the call above is the only call to
   // SCEVExpander. Henceforth, we produce 1-to-1 narrow to wide uses.
   if (BasicBlock *LatchBlock = L->getLoopLatch()) {
     WideInc =
       cast<Instruction>(WidePhi->getIncomingValueForBlock(LatchBlock));
     WideIncExpr = SE->getSCEV(WideInc);
+    // Propagate the debug location associated with the original loop increment
+    // to the new (widened) increment.
+    auto *OrigInc =
+      cast<Instruction>(OrigPhi->getIncomingValueForBlock(LatchBlock));
+    WideInc->setDebugLoc(OrigInc->getDebugLoc());
   }
 
   DEBUG(dbgs() << "Wide IV: " << *WidePhi << "\n");
   ++NumWidened;
 
   // Traverse the def-use chain using a worklist starting at the original IV.
   assert(Widened.empty() && NarrowIVUsers.empty() && "expect initial state" );
 

llvm/trunk/test/DebugInfo/Generic/indvar-discriminator.ll

+; RUN: opt -indvars -S < %s | FileCheck %s
+;
+; When the induction variable is widened by indvars, check that the debug loc
+; associated with the loop increment is correctly propagated.
+;
+; Test case obtained from the following source code:
+;
+; ////
+; extern int foo(int);  // line 1
+;
+; int bar(int X, int *A) {
+;   for (int i = 0; i < X; ++i)  // line 4
+;     A[i] = foo(i);
+;
+;   return A[0];
+; }
+; ///
+;
+; Check that the debug location for the loop increment still refers to
+; line 4, column 26, discriminator 2.
+;
+; CHECK-LABEL: for.body:
+; CHECK: [[PHI:%[0-9a-zA-Z.]+]] = phi i64 [
+; CHECK-LABEL: for.inc:
+; CHECK: add nuw nsw i64 [[PHI]], 1, !dbg ![[INDVARMD:[0-9]+]]
+; CHECK-DAG: ![[INDVARMD]] = !DILocation(line: 4, column: 26, scope: ![[INDVARSCOPEMD:[0-9]+]])
+; CHECK-DAG: ![[INDVARSCOPEMD]] = !DILexicalBlockFile(scope: !{{[0-9]+}}, file: !{{[0-9]+}}, discriminator: 2)
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @bar(i32 %X, i32* %A) !dbg !5 {
+entry:
+  %cmp5 = icmp sgt i32 %X, 0, !dbg !7
+  br i1 %cmp5, label %for.body.lr.ph, label %for.end, !dbg !9
+
+for.body.lr.ph:
+  br label %for.body, !dbg !9
+
+for.body:
+  %i.06 = phi i32 [ 0, %for.body.lr.ph ], [ %inc, %for.inc ]
+  %call = call i32 @foo(i32 %i.06), !dbg !10
+  %idxprom = sext i32 %i.06 to i64, !dbg !11
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom, !dbg !11
+  store i32 %call, i32* %arrayidx, align 4, !dbg !12
+  br label %for.inc, !dbg !11
+
+for.inc:
+  %inc = add nsw i32 %i.06, 1, !dbg !13
+  %cmp = icmp slt i32 %inc, %X, !dbg !7
+  br i1 %cmp, label %for.body, label %for.cond.for.end_crit_edge, !dbg !9, !llvm.loop !15
+
+for.cond.for.end_crit_edge:
+  br label %for.end, !dbg !9
+
+for.end:
+  %0 = load i32, i32* %A, align 4, !dbg !17
+  ret i32 %0, !dbg !18
+}
+
+declare i32 @foo(i32)
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "", isOptimized: false, runtimeVersion: 0, emissionKind: LineTablesOnly, enums: !2)
+!1 = !DIFile(filename: "test.c", directory: "")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = distinct !DISubprogram(name: "bar", scope: !1, file: !1, line: 3, type: !6, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: false, unit: !0, variables: !2)
+!6 = !DISubroutineType(types: !2)
+!7 = !DILocation(line: 4, column: 21, scope: !8)
+!8 = !DILexicalBlockFile(scope: !5, file: !1, discriminator: 1)
+!9 = !DILocation(line: 4, column: 3, scope: !8)
+!10 = !DILocation(line: 5, column: 12, scope: !5)
+!11 = !DILocation(line: 5, column: 5, scope: !5)
+!12 = !DILocation(line: 5, column: 10, scope: !5)
+!13 = !DILocation(line: 4, column: 26, scope: !14)
+!14 = !DILexicalBlockFile(scope: !5, file: !1, discriminator: 2)
+!15 = distinct !{!15, !16}
+!16 = !DILocation(line: 4, column: 3, scope: !5)
+!17 = !DILocation(line: 7, column: 10, scope: !5)
+!18 = !DILocation(line: 7, column: 3, scope: !5)