Add @llvm.dbg.value entries for the phi node created by -mem2reg

[keith.walker.arm]

Summary

When phi nodes are created in the -mem2reg phase, the @llvm.dbg.declare
entries are converted to @llvm.dbg.value entries at the place where the
store instructions existed. However no entry is created to describe
the resulting value of the phi node.

The effect of this is especially noticeable in for loops which have a
constant for the intial value; the loop control variable's location
would be described as the intial constant value in the loop body once
the -mem2reg optimization phase was run.

This change adds the creation of the @llvm.dbg.value entries to describe
variables whose location is the result of a phi node created in -mem2reg.

Also when the phi node is finally lowered to a machine instruction it
is important that the lowered "load" instruction is placed before the
associated DEBUG_VALUE entry describing the value loaded.

[dblaikie]

lib/Transforms/Utils/Local.cpp

1062–1074

This might be better written as an llvm::any_of (or at least llvm::find_if), perhaps?

1063–1065

This looks like it might try to dyn_cast the end iterator, which I would imagine isn't valid in general? (is there a reason it's incrementing first then doing work, rather than a more normal for (even range-for) loop?)

test/CodeGen/AArch64/phi-dbg.ll

1–4 ↗

(On Diff #68691)

Seems like this patch could be split in two - this test and the associated improvements to lib/CodeGen - and, separately, the changes mem2reg (& the other test) mentioned in the description.

[keith.walker.arm]

Thanks for the review, I will update the patch taking into account of your comments.

lib/Transforms/Utils/Local.cpp

1062–1074

I'll try doing as you suggest as see if I can re-write it in a more concise form.

1063–1065

The main reason is because I originally copied it from the previous function and then made it work forward rather than back and also become a loop - so it's basic structure is similar to the previous function. I will re-work it.

test/CodeGen/AArch64/phi-dbg.ll

1–4 ↗

(On Diff #68691)

Good idea. I will split it into 2 separate patches.

[keith.walker.arm]

• Moved the changes for ensuring the lowered load instruction in placed before the DEBUG_VALUE entry into a separate change: https://reviews.llvm.org/D23760
• Updated PhiHasDebugValue() to use llvm::any_of

[dblaikie]

I'll leave final sign-off to Adrian, who's worked with the value/variable tracking stuff in more depth more recently than I have.

lib/Transforms/Utils/Local.cpp

1065

Might even just roll the DVI test into the single return expression:

return DVI && DVI->getValue() == APN && ... ;

test/Transforms/Util/mem2reg-dbg.ll

37–38

LLVM registers don't necessarily have names in non-Asserts builds, so it's best to phrase the test so it doesn't use register names (c.0, if.then, entry, etc).

[[PHI:%.*]] = phi i32 [ 12, {{.*}} ], [ 1, {{.*}} ]
call.void @llvm.dbg.value(metadata i32 [[PHI]], ...

(in some cases register names still appear in Asserts builds, but these are mostly just oversight/things we haven't consistently removed)

[aprantl]

lib/Transforms/Utils/Local.cpp

1143

What's the point of this return value? Isn't it always true?

[aprantl]

lib/Transforms/Utils/Local.cpp

1063

Would it be possible to do something like in llvm::FindAllocaDbgDeclare() to avoid scanning all instructions here?

[keith.walker.arm]

lib/Transforms/Utils/Local.cpp

1143

Yes, it does always return true ..... I was just following the coding style in the preceding 2 functions which do a similar job for the load and store operations and which also always returns true. I'll make this a void function and remove the return true values.

[keith.walker.arm]

Updated PhiHasDebugValue() to avoid scanning the whole instructions stream by using a new function llvm::FindAllocaDbgValues(). This new function is similar to the exiting function llvm::FindAllocaDbgDeclare() but has the additional complication that the result of the find can find multiple entries when applied to a phi node.

Updated test to capture matching names.

I decided to leave the function llvm::ConvertDebugDeclareToDebugValue() always returning true so that it has a similar form to the preceding 2 functions which do the same thing.

[aprantl]

Couple of small style nitpicks, but otherwise LGTM.

Thanks!

lib/Transforms/Utils/Local.cpp

1143

Would be a good opportunity to also convert the other function to return void. The return value used to necessary when the function was originally added, but this is no longer the case.

1225

The "FindAllocaDbgValues - " is no longer needed with our current doxygen settings.

1227

This is up to taste, but this could also be written as taking a function/lambda callback instead of creating a temporary array.

[aprantl]

In D23715#544888, @keith.walker.arm wrote:

I decided to leave the function llvm::ConvertDebugDeclareToDebugValue() always returning true so that it has a similar form to the preceding 2 functions which do the same thing.

It would be awesome if you could clean this up in a separate NFC commit (no need to review this separately).

include/llvm/Transforms/Utils/Local.h

 
 class User;
 class BasicBlock;
 class Function;
 class BranchInst;
 class Instruction;
 class CallInst;
 class DbgDeclareInst;
+class DbgValueInst;
 class StoreInst;
 class LoadInst;
 class Value;
 class PHINode;
 class AllocaInst;
 class AssumptionCache;
 class ConstantExpr;
 class DataLayout;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 class DIBuilder;
 class DominatorTree;
 class LazyValueInfo;
 
 template<typename T> class SmallVectorImpl;
 
+typedef SmallVector<DbgValueInst *, 1> DbgValueList;
+
 //===----------------------------------------------------------------------===//
 //  Local constant propagation.
 //
 
 /// If a terminator instruction is predicated on a constant value, convert it
 /// into an unconditional branch to the constant destination.
 /// This is a nontrivial operation because the successors of this basic block
 /// must have their PHI nodes updated.

 bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
                                      StoreInst *SI, DIBuilder &Builder);
 
 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
 /// that has an associated llvm.dbg.decl intrinsic.
 bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
                                      LoadInst *LI, DIBuilder &Builder);
 
+/// Inserts a llvm.dbg.value intrinsic after a phi of an alloca'd value
+/// that has an associated llvm.dbg.decl intrinsic.
+bool ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
+                                     PHINode *LI, DIBuilder &Builder);
+
 /// Lowers llvm.dbg.declare intrinsics into appropriate set of
 /// llvm.dbg.value intrinsics.
 bool LowerDbgDeclare(Function &F);
 
 /// Finds the llvm.dbg.declare intrinsic corresponding to an alloca, if any.
 DbgDeclareInst *FindAllocaDbgDeclare(Value *V);
 
+/// Finds the llvm.dbg.value intrinsics corresponding to an alloca, if any.
+void FindAllocaDbgValues(DbgValueList &DbgValues, Value *V);
+
 /// Replaces llvm.dbg.declare instruction when the address it describes
 /// is replaced with a new value. If Deref is true, an additional DW_OP_deref is
 /// prepended to the expression. If Offset is non-zero, a constant displacement
 /// is added to the expression (after the optional Deref). Offset can be
 /// negative.
 bool replaceDbgDeclare(Value *Address, Value *NewAddress,
                        Instruction *InsertBefore, DIBuilder &Builder,
                        bool Deref, int Offset);

lib/Transforms/Utils/Local.cpp

if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI))
           DVI->getOffset() == 0 &&
           DVI->getVariable() == DIVar &&
           DVI->getExpression() == DIExpr)
         return true;
   }
   return false;
 }
 
+/// See if there is a dbg.value intrinsic for DIVar for the PHI node.
+static bool PhiHasDebugValue(DILocalVariable *DIVar, 
+                             DIExpression *DIExpr,
+                             PHINode *APN) {
+  // Since we can't guarantee that the original dbg.declare instrinsic
+  // is removed by LowerDbgDeclare(), we need to make sure that we are
+  // not inserting the same dbg.value intrinsic over and over.
+  DbgValueList DbgValues;
+  FindAllocaDbgValues(DbgValues, APN);
+  for (auto DVI : DbgValues) {
+    assert (DVI->getValue() == APN);
+    assert (DVI->getOffset() == 0);
+    if ((DVI->getVariable() == DIVar) && (DVI->getExpression() == DIExpr))
+      return true;
+  }
+  return false;
+}
+
 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
 /// that has an associated llvm.dbg.decl intrinsic.
 bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
                                            StoreInst *SI, DIBuilder &Builder) {
   auto *DIVar = DDI->getVariable();
   auto *DIExpr = DDI->getExpression();
   assert(DIVar && "Missing variable");
 
   // If an argument is zero extended then use argument directly. The ZExt
bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
   // preferable to keep tracking both the loaded value and the original
   // address in case the alloca can not be elided.
   Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
       LI, 0, DIVar, DIExpr, DDI->getDebugLoc(), (Instruction *)nullptr);
   DbgValue->insertAfter(LI);
   return true;
 }
 
+/// Inserts a llvm.dbg.value intrinsic after a phi 
+/// that has an associated llvm.dbg.decl intrinsic.
+bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
+                                           PHINode *APN, DIBuilder &Builder) {
+  auto *DIVar = DDI->getVariable();
+  auto *DIExpr = DDI->getExpression();
+  assert(DIVar && "Missing variable");
+
+  if (PhiHasDebugValue(DIVar, DIExpr, APN))
+    return true;
+
+  Instruction *DbgValue = Builder.insertDbgValueIntrinsic(
+      APN, 0, DIVar, DIExpr, DDI->getDebugLoc(), (Instruction *)nullptr);
+  DbgValue->insertBefore(&*APN->getParent()->getFirstInsertionPt());
+  return true;
+}
+
 /// Determine whether this alloca is either a VLA or an array.
 static bool isArray(AllocaInst *AI) {
   return AI->isArrayAllocation() ||
     AI->getType()->getElementType()->isArrayTy();
 }
 
 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
 /// of llvm.dbg.value intrinsics.
if (auto *L = LocalAsMetadata::getIfExists(V))
     if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
       for (User *U : MDV->users())
         if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U))
           return DDI;
 
   return nullptr;
 }
 
+/// FindAllocaDbgValues - Finds the llvm.dbg.value intrinsics describing the
+/// alloca 'V', if any.
+void llvm::FindAllocaDbgValues(DbgValueList &DbgValues, Value *V) {
+  if (auto *L = LocalAsMetadata::getIfExists(V))
+    if (auto *MDV = MetadataAsValue::getIfExists(V->getContext(), L))
+      for (User *U : MDV->users())
+        if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(U))
+          DbgValues.push_back(DVI);
+}
+
 static void DIExprAddDeref(SmallVectorImpl<uint64_t> &Expr) {
   Expr.push_back(dwarf::DW_OP_deref);
 }
 
 static void DIExprAddOffset(SmallVectorImpl<uint64_t> &Expr, int Offset) {
   if (Offset > 0) {
     Expr.push_back(dwarf::DW_OP_plus);
     Expr.push_back(Offset);

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

if (PhiToAllocaMap.count(APN)) {
         unsigned AllocaNo = PhiToAllocaMap[APN];
 
         // Add N incoming values to the PHI node.
         for (unsigned i = 0; i != NumEdges; ++i)
           APN->addIncoming(IncomingVals[AllocaNo], Pred);
 
         // The currently active variable for this block is now the PHI.
         IncomingVals[AllocaNo] = APN;
+        if (DbgDeclareInst *DDI = AllocaDbgDeclares[AllocaNo])
+          ConvertDebugDeclareToDebugValue(DDI, APN, DIB);
 
         // Get the next phi node.
         ++PNI;
         APN = dyn_cast<PHINode>(PNI);
         if (!APN)
           break;
 
         // Verify that it is missing entries.  If not, it is not being inserted

test/Transforms/Util/mem2reg-dbg.ll

+; RUN: opt -mem2reg -S < %s | FileCheck %s
+
+; Test that a @llvm.dbg.value node is created to describe the value returned by a phi node when
+; lowering a @llvm.dbg.declare node
+
+; Created from the C code, compiled with -O0 -g:
+;
+; int func(int a)
+; {
+;         int c = 1;
+;         if (a < 0 ) {
+;                 c = 12;
+;         }
+;         return c;
+; }
+
+; Function Attrs: nounwind
+define i32 @func(i32 %a) #0 !dbg !8 {
+entry:
+  %a.addr = alloca i32, align 4
+  %c = alloca i32, align 4
+  store i32 %a, i32* %a.addr, align 4
+  call void @llvm.dbg.declare(metadata i32* %a.addr, metadata !12, metadata !13), !dbg !14
+  call void @llvm.dbg.declare(metadata i32* %c, metadata !15, metadata !13), !dbg !16
+  store i32 1, i32* %c, align 4, !dbg !16
+  %0 = load i32, i32* %a.addr, align 4, !dbg !17
+  %cmp = icmp slt i32 %0, 0, !dbg !19
+  br i1 %cmp, label %if.then, label %if.end, !dbg !20
+
+if.then:                                          ; preds = %entry
+  store i32 12, i32* %c, align 4, !dbg !21
+  br label %if.end, !dbg !23
+
+if.end:                                           ; preds = %if.then, %entry
+  %1 = load i32, i32* %c, align 4, !dbg !24
+; CHECK: [[PHI:%.*]] = phi i32 [ 12, {{.*}} ], [ 1, {{.*}} ]
+; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 [[PHI]], i64 0, metadata !15, metadata !13), !dbg !16
+  ret i32 %1, !dbg !25
+}
+
+; Function Attrs: nounwind readnone
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+attributes #1 = { nounwind readnone }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4, !5, !6}
+!llvm.ident = !{!7}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "a.c", directory: "/tmp")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{i32 1, !"wchar_size", i32 4}
+!6 = !{i32 1, !"min_enum_size", i32 4}
+!7 = !{!"clang"}
+!8 = distinct !DISubprogram(name: "func", scope: !1, file: !1, line: 1, type: !9, isLocal: false, isDefinition: true, scopeLine: 2, flags: DIFlagPrototyped, isOptimized: false, unit: !0, variables: !2)
+!9 = !DISubroutineType(types: !10)
+!10 = !{!11, !11}
+!11 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!12 = !DILocalVariable(name: "a", arg: 1, scope: !8, file: !1, line: 1, type: !11)
+!13 = !DIExpression()
+!14 = !DILocation(line: 1, column: 14, scope: !8)
+!15 = !DILocalVariable(name: "c", scope: !8, file: !1, line: 3, type: !11)
+!16 = !DILocation(line: 3, column: 6, scope: !8)
+!17 = !DILocation(line: 4, column: 6, scope: !18)
+!18 = distinct !DILexicalBlock(scope: !8, file: !1, line: 4, column: 6)
+!19 = !DILocation(line: 4, column: 8, scope: !18)
+!20 = !DILocation(line: 4, column: 6, scope: !8)
+!21 = !DILocation(line: 5, column: 5, scope: !22)
+!22 = distinct !DILexicalBlock(scope: !18, file: !1, line: 4, column: 14)
+!23 = !DILocation(line: 6, column: 2, scope: !22)
+!24 = !DILocation(line: 7, column: 9, scope: !8)
+!25 = !DILocation(line: 7, column: 2, scope: !8)
+