[LoopDeletion] Update debug values after loop deletion.

[davide]

Summary

When loops are deleted, we don't keep track of variables modified inside the loops, so the DI will contain the wrong value for these.

e.g.

int b() {

int i;
for (i = 0; i < 2; i++)
  ;
patatino();
return a;

-> 6 patatino();

7   	  return a;
8   	}
9   	int main() { b(); }

(lldb) frame var i
(int) i = 0

We mark instead these values as unavailable inserting a @llvm.dbg.value(undef to make sure we don't end up printing an incorrect value in the debugger. We could consider doing something fancier, for, e.g. constants, in the future.

PR39868.
rdar://problem/46418795

[davide]

patch with context.

[aprantl]

This looks like the right & safe thing to do.

llvm/lib/Transforms/Utils/LoopUtils.cpp

372 ↗

(On Diff #176719)

I'd add:
// Since debug values in the loop have been deleted, inserting an undef dbg.value truncates the range of any dbg.value before the loop where the loop used to be. This is particularly important for constant values.

llvm/test/Transforms/LoopDeletion/diundef.ll

24 ↗

(On Diff #176719)

we probably can strip all the TBAA info

38 ↗

(On Diff #176719)

we can probably remove most of these attributes

64 ↗

(On Diff #176719)

we can probably simplify the metadata by removing the column info

[davide]

llvm/lib/Transforms/Utils/LoopUtils.cpp

376 ↗

(On Diff #176719)

Here I wasn't sure whether substituting with void undef was correct (or if it mattered at all).

388–392 ↗

(On Diff #176719)

Aside, I saw we only remove the loop if we have LoopInfo available. Shouldn't we do that unconditionally?

llvm/test/Transforms/LoopDeletion/diundef.ll

64 ↗

(On Diff #176719)

I'll do the other twos, but this makes me a little nervous. It also doesn't really simplify that much, so I don't think it's really worth diverging.

[davide]

Updated to address Adrian's comments.

[aprantl]

llvm/test/Transforms/LoopDeletion/diundef.ll

21 ↗

(On Diff #176724)

Can you add a second CHECK(-NEXT) to make sure that this dbg.value is actually in the location we think it is (i.e., after the branch)?

[aprantl]

llvm/test/Transforms/LoopDeletion/diundef.ll

20 ↗

(On Diff #176724)

And add:
// Test that after deleting the loop, the initializer value doesn't suddenly extend beyond the loop.

[jmorse]

Looks good; one observation is that if we have N dbg.value's of a variable in the loop, we'll end up with N dbg.value(undef)'s of that variable in the exit block. Ideally we'd only emit one per variable.

[edited for clarity]

[davide]

I'll switch this to be a DenseMap.

[aprantl]

llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp

574

I suppose this could be just a set instead of a map now?

llvm/trunk/lib/Transforms/Utils/LoopUtils.cpp

 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/IR/DIBuilder.h"
 #include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
   if (DT) {
     // Update the dominator tree by informing it about the new edge from the
     // preheader to the exit.
     DTU.insertEdge(Preheader, ExitBlock);
     // Inform the dominator tree about the removed edge.
     DTU.deleteEdge(Preheader, L->getHeader());
   }
 
+  // Use a map to unique and a vector to guarantee deterministic ordering.
+  llvm::SmallDenseMap<std::pair<DIVariable *, DIExpression *>,
+                      DbgVariableIntrinsic *, 4>
+      DeadDebugMap;
+  llvm::SmallVector<DbgVariableIntrinsic *, 4> DeadDebugInst;
+
   // Given LCSSA form is satisfied, we should not have users of instructions
   // within the dead loop outside of the loop. However, LCSSA doesn't take
   // unreachable uses into account. We handle them here.
   // We could do it after drop all references (in this case all users in the
   // loop will be already eliminated and we have less work to do but according
   // to API doc of User::dropAllReferences only valid operation after dropping
   // references, is deletion. So let's substitute all usages of
   // instruction from the loop with undef value of corresponding type first.
   for (auto *Block : L->blocks())
     for (Instruction &I : *Block) {
       auto *Undef = UndefValue::get(I.getType());
       for (Value::use_iterator UI = I.use_begin(), E = I.use_end(); UI != E;) {
         Use &U = *UI;
         ++UI;
         if (auto *Usr = dyn_cast<Instruction>(U.getUser()))
           if (L->contains(Usr->getParent()))
             continue;
         // If we have a DT then we can check that uses outside a loop only in
         // unreachable block.
         if (DT)
           assert(!DT->isReachableFromEntry(U) &&
                  "Unexpected user in reachable block");
         U.set(Undef);
       }
+      auto *DVI = dyn_cast<DbgVariableIntrinsic>(&I);
+      if (!DVI)
+        continue;
+      auto Key = DeadDebugMap.find({DVI->getVariable(), DVI->getExpression()});
+      if (Key != DeadDebugMap.end())
+        continue;
+      DeadDebugMap[{DVI->getVariable(), DVI->getExpression()}] = DVI;
+      DeadDebugInst.push_back(DVI);
     }
 
+  // After the loop has been deleted all the values defined and modified
+  // inside the loop are going to be unavailable.
+  // Since debug values in the loop have been deleted, inserting an undef
+  // dbg.value truncates the range of any dbg.value before the loop where the
+  // loop used to be. This is particularly important for constant values.
+  DIBuilder DIB(*ExitBlock->getModule());
+  for (auto *DVI : DeadDebugInst)
+    DIB.insertDbgValueIntrinsic(
+        UndefValue::get(DVI->getType()), DVI->getVariable(),
+        DVI->getExpression(), DVI->getDebugLoc(), ExitBlock->getFirstNonPHI());
+
   // Remove the block from the reference counting scheme, so that we can
   // delete it freely later.
   for (auto *Block : L->blocks())
     Block->dropAllReferences();
 
   if (LI) {
     // Erase the instructions and the blocks without having to worry
     // about ordering because we already dropped the references.

llvm/trunk/test/Transforms/LoopDeletion/diundef.ll

+; RUN: opt %s -loop-deletion -S | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-apple-macosx10.14.0"
+
+@a = common local_unnamed_addr global i32 0, align 4, !dbg !0
+
+define i32 @b() local_unnamed_addr !dbg !12 {
+entry:
+  call void @llvm.dbg.value(metadata i32 0, metadata !16, metadata !DIExpression()), !dbg !17
+  br label %for.cond, !dbg !18
+
+for.cond:                                         ; preds = %for.cond, %entry
+  %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.cond ], !dbg !20
+  call void @llvm.dbg.value(metadata i32 %i.0, metadata !16, metadata !DIExpression()), !dbg !17
+  %inc = add nuw nsw i32 %i.0, 1, !dbg !21
+  call void @llvm.dbg.value(metadata i32 %inc, metadata !16, metadata !DIExpression()), !dbg !17
+  %exitcond = icmp ne i32 %inc, 3, !dbg !23
+  br i1 %exitcond, label %for.cond, label %for.end, !dbg !24, !llvm.loop !25
+
+; CHECK: call void @llvm.dbg.value(metadata void undef, metadata !16, metadata !DIExpression()), !dbg !17
+; CHECK-NEXT: %call = tail call i32 {{.*}} @patatino()
+for.end:                                          ; preds = %for.cond
+  %call = tail call i32 (...) @patatino() #3, !dbg !27
+  %0 = load i32, i32* @a, align 4, !dbg !28
+  ret i32 %0, !dbg !33
+}
+
+declare i32 @patatino(...) local_unnamed_addr
+
+define i32 @main() local_unnamed_addr !dbg !34 {
+entry:
+  %call = call i32 @b(), !dbg !35
+  ret i32 0, !dbg !36
+}
+
+declare void @llvm.dbg.value(metadata, metadata, metadata)
+
+!llvm.dbg.cu = !{!2}
+!llvm.module.flags = !{!7, !8, !9, !10}
+!llvm.ident = !{!11}
+
+!0 = !DIGlobalVariableExpression(var: !1, expr: !DIExpression())
+!1 = distinct !DIGlobalVariable(name: "a", scope: !2, file: !3, line: 1, type: !6, isLocal: false, isDefinition: true)
+!2 = distinct !DICompileUnit(language: DW_LANG_C99, file: !3, producer: "clang version 8.0.0 ", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !4, globals: !5, nameTableKind: GNU)
+!3 = !DIFile(filename: "a.c", directory: "/Users/davide/work/llvm-project-20170507/build-debug/bin")
+!4 = !{}
+!5 = !{!0}
+!6 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!7 = !{i32 2, !"Dwarf Version", i32 4}
+!8 = !{i32 2, !"Debug Info Version", i32 3}
+!9 = !{i32 1, !"wchar_size", i32 4}
+!10 = !{i32 7, !"PIC Level", i32 2}
+!11 = !{!"clang version 8.0.0 "}
+!12 = distinct !DISubprogram(name: "b", scope: !3, file: !3, line: 2, type: !13, scopeLine: 2, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !2, retainedNodes: !15)
+!13 = !DISubroutineType(types: !14)
+!14 = !{!6}
+!15 = !{!16}
+!16 = !DILocalVariable(name: "i", scope: !12, file: !3, line: 3, type: !6)
+!17 = !DILocation(line: 3, column: 7, scope: !12)
+!18 = !DILocation(line: 4, column: 8, scope: !19)
+!19 = distinct !DILexicalBlock(scope: !12, file: !3, line: 4, column: 3)
+!20 = !DILocation(line: 0, scope: !19)
+!21 = !DILocation(line: 4, column: 23, scope: !22)
+!22 = distinct !DILexicalBlock(scope: !19, file: !3, line: 4, column: 3)
+!23 = !DILocation(line: 4, column: 17, scope: !22)
+!24 = !DILocation(line: 4, column: 3, scope: !19)
+!25 = distinct !{!25, !24, !26}
+!26 = !DILocation(line: 5, column: 5, scope: !19)
+!27 = !DILocation(line: 6, column: 3, scope: !12)
+!28 = !DILocation(line: 7, column: 10, scope: !12)
+!33 = !DILocation(line: 7, column: 3, scope: !12)
+!34 = distinct !DISubprogram(name: "main", scope: !3, file: !3, line: 9, type: !13, scopeLine: 9, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !2, retainedNodes: !4)
+!35 = !DILocation(line: 9, column: 14, scope: !34)
+!36 = !DILocation(line: 9, column: 19, scope: !34)