SCEV: preserve debug information attached to PHI nodes.

[aprantl]

Summary

This is a work-in-progress fix for one part of PR35015.

https://bugs.llvm.org/show_bug.cgi?id=35015

[hfinkel]

lib/Analysis/ScalarEvolutionExpander.cpp

1215 ↗

(On Diff #120495)

How do you know that the AddRec being expanded here is equivalent to a canonical induction variable? That's only true if we're expanding '{0,+,1}', right?

Does calling SE.getSCEVValues(Normalized) also find the original PHI node?

[aprantl]

lib/Analysis/ScalarEvolutionExpander.cpp

1215 ↗

(On Diff #120495)

Thanks, that is a good point! I could either constrain it to just handle this special case or attempt to generalize it. Unfortunately I don't know enough about SCEV yet:
Can SCEV also modify the trip count of the loop?
Is there a way I can reconstruct a function (that I then could translate into a DWARF expression) that transforms the value of the new induction variable into the original one for the current iteration?

[hfinkel]

lib/Analysis/ScalarEvolutionExpander.cpp

1215 ↗

(On Diff #120495)

Thanks, that is a good point! I could either constrain it to just handle this special case or attempt > to generalize it. Unfortunately I don't know enough about SCEV yet:

If SE.getSCEVValues(Normalized) will give you the original PHI for a given SCEV, then that should be fully general (at least for cases where there is an existing PHI for a particular).

Can SCEV also modify the trip count of the loop?

SCEV is an analysis, so this is really a question about what transformations might do. A transformation can change the trip count of a loop (generally by reducing it; peeling for example).

Is there a way I can reconstruct a function (that I then could translate into a DWARF expression) that transforms the value of the new induction variable into the original one for the current iteration?

If I have the SCEV of the original induction variable, OrigIVAddRec, and the new induction variable, NewIVAddRec, then you can subtract them:

IVDiff = SE->getMinusSCEV(NewIVAddRec, OrigIVAddRec);

Now, in each iteration, IVDiff is what you need to add to the current induction variable, NewIV, in order to get the value of the existing one, OldIV. So you can construct a DWARF expression that adds IVDiff to NewIV. In some cases, IVDiff will actually just be an SCEVConstant, but it could be a more general expression.

To handle the more-general case, a SCEV -> DWARF utility can be created. One way to do this would be to write an SCEVVisitor that builds up a DWARF expression as it recurses through an SCEV. When you reach an SCEVUnknown, that's just a wrapper around a Value*. And you might be able to short-circuit the evaluation at any SCEV,moreover, if SE.getSCEVValues on that SCEV returns a useful Value*.

I suspect this is most of what you need to do to adjust for what IndVarSimplify does as well (although it also sometimes changes the bitwidth of induction variables, so there's a little more to do there I suspect for those cases).

[aprantl]

lib/Analysis/ScalarEvolutionExpander.cpp

1215 ↗

(On Diff #120495)

Thanks, I have a couple more questions!

Does calling SE.getSCEVValues(Normalized) also find the original PHI node?

SE.getSCEVValues(Normalized) returns a nullptr unfortunately.

Is the problem with L->getCanonicalInductionVariable() that multiple transformations might be applied on top of another and that the IV from the Loop object might be out of date?

I guess I'm also slightly confused at what the SCEV of the original induction variable is. Does the SCEVAddRecExpr *Normalized represent the induction variable or the loop itself?

Normalized->dump() says: {0,+,1}<nuw><nsw><%for.cond>
so this appears to represent the recurrence representing one step in the loop. Is that the "SCEV of the induction variable" or is that different from the SCEVAddRecExpr and how do I get to it?

Does the notation '{0,+,1}' mean start=0, increment_operator=+, increment=1?

That said, the part with the SCEVVisitor ->DWARF translator sounds fairly straightforward and fun to do!

[aprantl]

lib/Analysis/ScalarEvolutionExpander.cpp

1215 ↗

(On Diff #120495)

Based on this snippet from the top of SCEVExpander::getAddRecExprPHILiterally() it looks like PhiSCEV is the SCEV for the original induction variable.

for (auto &I : *L->getHeader()) {
     auto *PN = dyn_cast<PHINode>(&I);
     if (!PN || !SE.isSCEVable(PN->getType()))
       continue;

     const SCEVAddRecExpr *PhiSCEV = dyn_cast<SCEVAddRecExpr>(SE.getSCEV(PN));
     if (!PhiSCEV)
       continue;

[aprantl]

Here is a slightly more general version that includes most of Hal's feedback. I will create a couple of more interesting testcases next to see how to handle cases where the result of subtracting the two recurrences is not a constant.

[hfinkel]

First, should this logic be here or should it be in IndVarSimplify? I ask because there are transformations that can introduce new AddRecs into an existing loop without replacing the induction variable. Only the transformation using the SCEVExpander knows if it is planning to actually replace the induction variable.

A related question: Is it okay to have multiple values in a function define the same dbg.value's variable? If, for example, we were to end up with multiple induction variables in a loop, and all had a relationship to the source-level induction variable, would it be okay if all these PHIs were used by dbg.value intrinsics to define the same source-level variable? Or would that just confuse things?

In your test case, IndVarSimplify is doing induction-variable widening on an already-canonical induction variable. This is an interesting special case because both the old and new induction variables are canonical (i.e., they both start from zero and increment by one on each iteration). One thing that makes it special is that there already is an old canonical induction variable when the new one is added. In general, for IndVarSimplify, we won't have an existing canonical induction variable (we'll just have some other AddRecs - non-canonical induction variables) and we'll be creating the canonical induction variable.

Generally, for IndVarSimplify, you'll have some AddRec corresponding to some existing PHI - the non-canonical induction variable with the debug info - and IndVarSimplify will introduce a canonical induction variable. The AddRec for the existing PHI {a,+,b} is implicitly defined in terms of the canonical induction variable just created: OldPN = a + b*CanPN. So, the dbg.value defining the variable previously defined by OldPN can be defined now by a DWARF expression a + b*CanPN (plus, perhaps any trunctions/extensions).

Also, in your test case here for induction-variable widening, should the DWARF expression after this have some kind of DIExpression with a truncate in it to reverse the effect of the widening?

lib/Analysis/ScalarEvolutionExpander.cpp

1301 ↗

(On Diff #120666)

L->getCanonicalInductionVariable() can fail (i.e., return nullptr), so I imagine this guard could/should be:

if (PhiSCEV && OldPN) {

(the goal of IndVarSimplify is to introduce such a variable, but it might not exist, especially before/during IndVarSimplify running)

[aprantl]

In D39345#909994, @hfinkel wrote:

First, should this logic be here or should it be in IndVarSimplify? I ask because there are transformations that can introduce new AddRecs into an existing loop without replacing the induction variable. Only the transformation using the SCEVExpander knows if it is planning to actually replace the induction variable.

Thanks for pointing this out. I shall take a look at IndVarSimplify to see whether this is a more natural place for this.

A related question: Is it okay to have multiple values in a function define the same dbg.value's variable? If, for example, we were to end up with multiple induction variables in a loop, and all had a relationship to the source-level induction variable, would it be okay if all these PHIs were used by dbg.value intrinsics to define the same source-level variable? Or would that just confuse things?

Multiple dbg.values are totally fine. A dbg.value means that "from here on, the variable's value is SSA-value" and the value is valid until either the register the SSA-value is lowered to is clobbered, the basic block ends, or a new dbg.value describing the same variable is encountered.

In your test case, IndVarSimplify is doing induction-variable widening on an already-canonical induction variable. This is an interesting special case because both the old and new induction variables are canonical (i.e., they both start from zero and increment by one on each iteration). One thing that makes it special is that there already is an old canonical induction variable when the new one is added. In general, for IndVarSimplify, we won't have an existing canonical induction variable (we'll just have some other AddRecs - non-canonical induction variables) and we'll be creating the canonical induction variable.

Interesting. I will try and include the more general case, too. You probably saw on bugzilla that I was out hunting for other interesting testcases recently.

Generally, for IndVarSimplify, you'll have some AddRec corresponding to some existing PHI - the non-canonical induction variable with the debug info - and IndVarSimplify will introduce a canonical induction variable. The AddRec for the existing PHI {a,+,b} is implicitly defined in terms of the canonical induction variable just created: OldPN = a + b*CanPN. So, the dbg.value defining the variable previously defined by OldPN can be defined now by a DWARF expression a + b*CanPN (plus, perhaps any trunctions/extensions).

Thanks for the explanation!

Also, in your test case here for induction-variable widening, should the DWARF expression after this have some kind of DIExpression with a truncate in it to reverse the effect of the widening?

The truncation happens implicitly because the type of the variable and thus its size is also known to the debugger, but if there was a narrowing performed, we would need to insert a sign-extension operation.

[aprantl]

I moved the logic over to indvars now, and that seems to fit naturally into WidenIV::createWideIV() with about the same functionality as above.

But I'm having trouble generating more interesting testcases. For example: The top-level comment in IndVarSimplify claims that the pass would

//   1. The exit condition for the loop is canonicalized to compare the
//      induction value against the exit value.  This turns loops like:
//        'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'

But I can't reproduce this:

char *a;
void f(int j) {
  for (int i = 7; i*i < 1000; i+=1)
      a[i] = i;
}

clang -O3 -c -S -emit-llvm -o - /tmp/loop.c -fno-unroll-loops -mllvm -print-after-all -g 2>&1

*** IR Dump After Induction Variable Simplification ***
for.body:                                         ; preds = %entry, %for.body
  %indvars.iv = phi i64 [ 7, %entry ], [ %indvars.iv.next, %for.body ]

Has the functionality bitrotted, or is the comment out-of-date, or is there now a different transformation that would rewrite a loop like int that comment? Or can I change my testcase somehow?

I then put an assert that IVDiff (the diff between SCEV for the old and new phi in WidenIV::createWideIV()) is not a constant zero and check-llvm-transform still passes. That's not the end of the world, handling the constant-zero case would already be a nice improvement, but I'm wondering if I'm missing the big picture here.

[aprantl]

Meanwhile I uploaded the simplified patch that just handles the common case in indvars.

[hfinkel]

In D39345#912029, @aprantl wrote:

I moved the logic over to indvars now, and that seems to fit naturally into WidenIV::createWideIV() with about the same functionality as above.

But I'm having trouble generating more interesting testcases. For example: The top-level comment in IndVarSimplify claims that the pass would

//   1. The exit condition for the loop is canonicalized to compare the
//      induction value against the exit value.  This turns loops like:
//        'for (i = 7; i*i < 1000; ++i)' into 'for (i = 0; i != 25; ++i)'

But I can't reproduce this:

char *a;
void f(int j) {
  for (int i = 7; i*i < 1000; i+=1)
      a[i] = i;
}

clang -O3 -c -S -emit-llvm -o - /tmp/loop.c -fno-unroll-loops -mllvm -print-after-all -g 2>&1

*** IR Dump After Induction Variable Simplification ***
for.body:                                         ; preds = %entry, %for.body
  %indvars.iv = phi i64 [ 7, %entry ], [ %indvars.iv.next, %for.body ]

Has the functionality bitrotted, or is the comment out-of-date, or is there now a different transformation that would rewrite a loop like int that comment? Or can I change my testcase somehow?

It is out of date. @sanjoy may know more. Thinking about it, I do recall that we might now not do these replacements in cases where SCEV can easily construct the induction-variable recurrence.

I then put an assert that IVDiff (the diff between SCEV for the old and new phi in WidenIV::createWideIV()) is not a constant zero and check-llvm-transform still passes. That's not the end of the world, handling the constant-zero case would already be a nice improvement, but I'm wondering if I'm missing the big picture here.

Hrmm. I'm missing something too. We also don't seem to be collapsing logically-redundant phis, as in:

void foo(int *a, int *b, int n) {
  for (int i = 0, j = 1; i < n; ++i, ++j)
    a[i] = b[j] + 1;
}

this loop still ends up with two phis after optimization. I thought IndVarSimplify took care of this, but evidently it doesn't right now.

For now, given the apparent current state of things, maybe we should just handle the zero-delta case, and then come back to this later as necessary.

[aprantl]

Thanks for confirming! Also, unfortunate :-(
Do you have any feedback on the patch for the zero-delta-case as is that I should be addressing before landing this?

[hfinkel]

In D39345#914083, @aprantl wrote:

Thanks for confirming! Also, unfortunate :-(
Do you have any feedback on the patch for the zero-delta-case as is that I should be addressing before landing this?

I don't think that we need to check the difference at all in this case. It will always be zero because the new SCEV is generated from the old one:

// Widen the induction variable expression.
const SCEV *WideIVExpr = getExtendKind(OrigPhi) == SignExtended
                             ? SE->getSignExtendExpr(AddRec, WideType)
                             : SE->getZeroExtendExpr(AddRec, WideType);

so I think that you can make this debug-value propagation logic simpler?

[aprantl]

Simplify the patch because the SCEV for old and new phi are always the same.

[aprantl]

Remove the lambda; it now looks silly.

[hfinkel]

LGTM

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

 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
while (!NarrowIVUsers.empty()) {
     // Follow all def-use edges from the previous narrow use.
     if (WideUse)
       pushNarrowIVUsers(DU.NarrowUse, WideUse);
 
     // widenIVUse may have removed the def-use edge.
     if (DU.NarrowDef->use_empty())
       DeadInsts.emplace_back(DU.NarrowDef);
   }
+
+  // Attach any debug information to the new PHI. Since OrigPhi and WidePHI
+  // evaluate the same recurrence, we can just copy the debug info over.
+  SmallVector<DbgValueInst *, 1> DbgValues;
+  llvm::findDbgValues(DbgValues, OrigPhi);
+  auto *MDPhi = MetadataAsValue::get(WidePhi->getContext(),
+                                     ValueAsMetadata::get(WidePhi));
+  for (auto &DbgValue : DbgValues)
+    DbgValue->setOperand(0, MDPhi);
   return WidePhi;
 }
 
 /// Calculates control-dependent range for the given def at the given context
 /// by looking at dominating conditions inside of the loop
 void WidenIV::calculatePostIncRange(Instruction *NarrowDef,
                                     Instruction *NarrowUser) {
   using namespace llvm::PatternMatch;

llvm/trunk/test/Transforms/IndVarSimplify/scev-phi-debug-info.ll

+; RUN: opt %s -indvars -S -o - | FileCheck %s
+source_filename = "/Data/llvm/test/Transforms/IndVarSimplify/scev-phi-debug-info.ll"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+%struct.status = type { i32, i8* }
+
+@status = internal unnamed_addr global [32 x %struct.status] zeroinitializer, align 16, !dbg !0
+
+define void @f0() local_unnamed_addr !dbg !20 {
+entry:
+  tail call void @llvm.dbg.value(metadata i32 0, metadata !23, metadata !DIExpression()), !dbg !24
+  br label %for.cond, !dbg !24
+
+for.cond:                                         ; preds = %for.body, %entry
+  ; CHECK: %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
+  ; CHECK: call void @llvm.dbg.value(metadata i64 %indvars.iv, metadata !23, metadata !DIExpression()), !dbg !24
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  tail call void @llvm.dbg.value(metadata i32 %i.0, metadata !23, metadata !DIExpression()), !dbg !24
+  %cmp = icmp slt i32 %i.0, 32, !dbg !24
+  br i1 %cmp, label %for.body, label %for.end, !dbg !24
+
+for.body:                                         ; preds = %for.cond
+  %idxprom = sext i32 %i.0 to i64, !dbg !24
+  %value = getelementptr inbounds [32 x %struct.status], [32 x %struct.status]* @status, i64 0, i64 %idxprom, i32 0, !dbg !24
+  store i32 42, i32* %value, align 16, !dbg !24
+  tail call void @use(i32 %i.0), !dbg !24
+  %inc = add nsw i32 %i.0, 1, !dbg !24
+  tail call void @llvm.dbg.value(metadata i32 %inc, metadata !23, metadata !DIExpression()), !dbg !24
+  br label %for.cond, !dbg !24
+
+for.end:                                          ; preds = %for.cond
+  ret void, !dbg !24
+}
+
+declare void @use(i32)
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #0
+
+attributes #0 = { nounwind readnone speculatable }
+
+!llvm.dbg.cu = !{!2}
+!llvm.module.flags = !{!16, !17, !18}
+!llvm.ident = !{!19}
+
+!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
+!1 = distinct !DIGlobalVariable(name: "status", scope: !2, file: !3, line: 5, type: !6, isLocal: true, isDefinition: true)
+!2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "clang version 6.0.0 (trunk 316001) (llvm/trunk 316171)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5)
+!3 = !DIFile(filename: "x.c", directory: "/home/davide/work/llvm/build-release/bin")
+!4 = !{}
+!5 = !{!0}
+!6 = !DICompositeType(tag: DW_TAG_array_type, baseType: !7, size: 4096, elements: !14)
+!7 = distinct !DICompositeType(tag: DW_TAG_structure_type, name: "status", file: !3, line: 2, size: 128, elements: !8)
+!8 = !{!9, !11}
+!9 = !DIDerivedType(tag: DW_TAG_member, name: "value", scope: !7, file: !3, line: 3, baseType: !10, size: 32)
+!10 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!11 = !DIDerivedType(tag: DW_TAG_member, name: "p", scope: !7, file: !3, line: 4, baseType: !12, size: 64, offset: 64)
+!12 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !13, size: 64)
+!13 = !DIBasicType(name: "unsigned char", size: 8, encoding: DW_ATE_unsigned_char)
+!14 = !{!15}
+!15 = !DISubrange(count: 32)
+!16 = !{i32 2, !"Dwarf Version", i32 4}
+!17 = !{i32 2, !"Debug Info Version", i32 3}
+!18 = !{i32 1, !"wchar_size", i32 4}
+!19 = !{!"clang version 6.0.0 (trunk 316001) (llvm/trunk 316171)"}
+!20 = distinct !DISubprogram(name: "f0", scope: !3, file: !3, line: 6, type: !21, isLocal: false, isDefinition: true, scopeLine: 7, flags: DIFlagPrototyped, isOptimized: true, unit: !2, variables: !22)
+!21 = !DISubroutineType(types: !4)
+!22 = !{!23}
+!23 = !DILocalVariable(name: "i", scope: !20, file: !3, line: 8, type: !10)
+!24 = !DILocation(line: 9, scope: !20)