[LoopRotate] Update dbg.value calls

[samparker]

Summary

Propagate debug info through the newly inserted PHI nodes, this was previously attempted in D29578 at the SSA level. As an example of the issue this is fixing:

int main(int a) {

for(int i = 1; i < 10; i++) {
  func2(i, i+a);
}

}

If we currently compile with clang, loop rotation will transform the debug information so that the value 'i' is always set to the constant 1 in the body of the loop.

[aprantl]

lib/Transforms/Scalar/LoopRotation.cpp

182

'.' at the end :-)

183

clang-format, range-based-for?

197

this is doing the lookup twice if successful. Maybe better to use find() instead?

[samparker]

Updated to use range based loops and use find to reduce map lookup overhead.

[samparker]

Ping. @aprantl would you mind reviewing this? Thanks.

[aprantl]

Seems generally plausible. LGTM with all inline comments addressed.

lib/Transforms/Scalar/LoopRotation.cpp

178

Technically LLVM coding guidelines want this to start with a lower case character. (but I see that other functions in the same file also violate this...)

178

Comment what the function is doing?

186

DbgValueMap.insert({DbgII->getVariableLocation(), DbgII)});

191

s/call/instrinsic/

198

1. auto
2. Why do you need a dyn_cast here? I would have either expected a static_cast, or something that actually checks the result.

390

call -> intrinsic

test/Transforms/LoopRotate/phi-dbgvalue.ll

3

Comment what the test is testing.

lib/Transforms/Scalar/LoopRotation.cpp

 } // end anonymous namespace
 
 /// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
 /// old header into the preheader.  If there were uses of the values produced by
 /// these instruction that were outside of the loop, we have to insert PHI nodes
 /// to merge the two values.  Do this now.
 static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
                                             BasicBlock *OrigPreheader,
-                                            ValueToValueMapTy &ValueMap) {
+                                            ValueToValueMapTy &ValueMap,
+                                SmallVectorImpl<PHINode*> *InsertedPHIs) {
   // Remove PHI node entries that are no longer live.
   BasicBlock::iterator I, E = OrigHeader->end();
   for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
     PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));
 
   // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
   // as necessary.
-  SSAUpdater SSA;
+  SSAUpdater SSA(InsertedPHIs);
   for (I = OrigHeader->begin(); I != E; ++I) {
     Value *OrigHeaderVal = &*I;
 
     // If there are no uses of the value (e.g. because it returns void), there
     // is nothing to rewrite.
     if (OrigHeaderVal->use_empty())
       continue;
 
if (auto *VAM = ValueAsMetadata::getIfExists(OrigHeaderVal)) {
             NewVal = UndefValue::get(OrigHeaderVal->getType());
           U = MetadataAsValue::get(C, ValueAsMetadata::get(NewVal));
         }
       }
     }
   }
 }
 
+static void InsertDebugValues(BasicBlock *OrigHeader,
+                              SmallVectorImpl<PHINode*> &InsertedPHIs) {
+  ValueToValueMapTy DbgValueMap;
+
+  // Map existing PHI nodes to their dbg.values
+  for(auto I = OrigHeader->begin(), E = OrigHeader->end(); I != E; ++I) {
+    if (auto DbgII = dyn_cast<DbgInfoIntrinsic>(I)) {
+      if (isa<PHINode>(DbgII->getVariableLocation()))
+        DbgValueMap.insert(std::make_pair(DbgII->getVariableLocation(), DbgII));
+    }
+  }
+
+  // Then iterate through the new PHIs and look to see if they use one of the
+  // previously mapped PHIs. If so, insert a new dbg.value call that will
+  // propagate the info through the new PHI.
+  LLVMContext &C = OrigHeader->getContext();
+  for (auto PHI : InsertedPHIs) {
+    for (auto VI = PHI->value_op_begin(), VE = PHI->value_op_end();
+         VI != VE; ++VI) {
+      if (DbgValueMap.count(*VI)) {
+        DbgInfoIntrinsic *DbgII =
+          dyn_cast<DbgInfoIntrinsic>(DbgValueMap.lookup(*VI));
+        Instruction *NewDbgII = DbgII->clone();
+        auto PhiMAV = MetadataAsValue::get(C, ValueAsMetadata::get(PHI));
+        NewDbgII->setOperand(0, PhiMAV);
+        BasicBlock *Parent = PHI->getParent();
+        NewDbgII->insertBefore(Parent->getFirstNonPHIOrDbgOrLifetime());
+      }
+    }
+  }
+}
+
 /// Rotate loop LP. Return true if the loop is rotated.
 ///
 /// \param SimplifiedLatch is true if the latch was just folded into the final
 /// loop exit. In this case we may want to rotate even though the new latch is
 /// now an exiting branch. This rotation would have happened had the latch not
 /// been simplified. However, if SimplifiedLatch is false, then we avoid
 /// rotating loops in which the latch exits to avoid excessive or endless
 /// rotation. LoopRotate should be repeatable and converge to a canonical
for (BasicBlock::iterator BI = SuccBB->begin();
          PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
       PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);
 
   // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
   // OrigPreHeader's old terminator (the original branch into the loop), and
   // remove the corresponding incoming values from the PHI nodes in OrigHeader.
   LoopEntryBranch->eraseFromParent();
 
+
+  SmallVector<PHINode*, 2> InsertedPHIs;
   // If there were any uses of instructions in the duplicated block outside the
   // loop, update them, inserting PHI nodes as required
-  RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap);
+  RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap,
+                                  &InsertedPHIs);
+
+  // Attach dbg.value calls to the new phis if that phi uses a value that
+  // previously had debug metadata attached. This keeps the debug info
+  // up-to-date in the loop body.
+  if (!InsertedPHIs.empty())
+    InsertDebugValues(OrigHeader, InsertedPHIs);
 
   // NewHeader is now the header of the loop.
   L->moveToHeader(NewHeader);
   assert(L->getHeader() == NewHeader && "Latch block is our new header");
 
   // At this point, we've finished our major CFG changes.  As part of cloning
   // the loop into the preheader we've simplified instructions and the
   // duplicated conditional branch may now be branching on a constant.  If it is

test/Transforms/LoopRotate/phi-dbgvalue.ll

+; RUN: opt -S -loop-rotate < %s | FileCheck %s
+
+;CHECK-LABEL: func
+;CHECK-LABEL: entry
+;CHECK-NEXT: tail call void @llvm.dbg.value(metadata i32 %a
+;CHECK-NEXT: tail call void @llvm.dbg.value(metadata i32 1, i64 0, metadata !13, metadata !11), !dbg !15
+;CHECK-LABEL: for.body:
+;CHECK-NEXT: [[I:%.*]] = phi i32 [ 1, %entry ], [ %inc, %for.body ]
+;CHECK-NEXT: tail call void @llvm.dbg.value(metadata i32 [[I]], i64 0, metadata !13, metadata !11), !dbg !15
+
+; Function Attrs: noinline nounwind
+define void @func(i32 %a) local_unnamed_addr #0 !dbg !6 {
+entry:
+  tail call void @llvm.dbg.value(metadata i32 %a, i64 0, metadata !10, metadata !11), !dbg !12
+  tail call void @llvm.dbg.value(metadata i32 1, i64 0, metadata !13, metadata !11), !dbg !15
+  br label %for.cond, !dbg !16
+
+for.cond:                                         ; preds = %for.body, %entry
+  %i.0 = phi i32 [ 1, %entry ], [ %inc, %for.body ]
+  tail call void @llvm.dbg.value(metadata i32 %i.0, i64 0, metadata !13, metadata !11), !dbg !15
+  %cmp = icmp slt i32 %i.0, 10, !dbg !17
+  br i1 %cmp, label %for.body, label %for.end, !dbg !20
+
+for.body:                                         ; preds = %for.cond
+  %add = add nsw i32 %i.0, %a, !dbg !22
+  %call = tail call i32 @func2(i32 %i.0, i32 %add) #3, !dbg !24
+  %inc = add nsw i32 %i.0, 1, !dbg !25
+  tail call void @llvm.dbg.value(metadata i32 %inc, i64 0, metadata !13, metadata !11), !dbg !15
+  br label %for.cond, !dbg !27, !llvm.loop !28
+
+for.end:                                          ; preds = %for.cond
+  ret void, !dbg !31
+}
+
+declare i32 @func2(i32, i32) local_unnamed_addr
+
+; Function Attrs: nounwind readnone
+declare void @llvm.dbg.value(metadata, i64, metadata, metadata) #2
+
+attributes #0 = { noinline nounwind }
+attributes #2 = { nounwind readnone }
+attributes #3 = { nounwind }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+!llvm.ident = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 5.0.0 (http://llvm.org/git/clang.git 0f3ed908c1f13f83da4b240f7595eb8d05e0a754) (http://llvm.org/git/llvm.git 8e270f5a6b8ceb0f3ac3ef1ffb83c5e29b44ae68)", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
+!1 = !DIFile(filename: "debug-phi.c", directory: "/work/projects/src/tests/debug")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{!"clang version 5.0.0 (http://llvm.org/git/clang.git 0f3ed908c1f13f83da4b240f7595eb8d05e0a754) (http://llvm.org/git/llvm.git 8e270f5a6b8ceb0f3ac3ef1ffb83c5e29b44ae68)"}
+!6 = distinct !DISubprogram(name: "func", scope: !1, file: !1, line: 2, type: !7, isLocal: false, isDefinition: true, scopeLine: 2, flags: DIFlagPrototyped, isOptimized: false, unit: !0, variables: !2)
+!7 = !DISubroutineType(types: !8)
+!8 = !{null, !9}
+!9 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!10 = !DILocalVariable(name: "a", arg: 1, scope: !6, file: !1, line: 2, type: !9)
+!11 = !DIExpression()
+!12 = !DILocation(line: 2, column: 15, scope: !6)
+!13 = !DILocalVariable(name: "i", scope: !14, file: !1, line: 3, type: !9)
+!14 = distinct !DILexicalBlock(scope: !6, file: !1, line: 3, column: 3)
+!15 = !DILocation(line: 3, column: 11, scope: !14)
+!16 = !DILocation(line: 3, column: 7, scope: !14)
+!17 = !DILocation(line: 3, column: 20, scope: !18)
+!18 = !DILexicalBlockFile(scope: !19, file: !1, discriminator: 1)
+!19 = distinct !DILexicalBlock(scope: !14, file: !1, line: 3, column: 3)
+!20 = !DILocation(line: 3, column: 3, scope: !21)
+!21 = !DILexicalBlockFile(scope: !14, file: !1, discriminator: 1)
+!22 = !DILocation(line: 4, column: 15, scope: !23)
+!23 = distinct !DILexicalBlock(scope: !19, file: !1, line: 3, column: 31)
+!24 = !DILocation(line: 4, column: 5, scope: !23)
+!25 = !DILocation(line: 3, column: 27, scope: !26)
+!26 = !DILexicalBlockFile(scope: !19, file: !1, discriminator: 2)
+!27 = !DILocation(line: 3, column: 3, scope: !26)
+!28 = distinct !{!28, !29, !30}
+!29 = !DILocation(line: 3, column: 3, scope: !14)
+!30 = !DILocation(line: 5, column: 3, scope: !14)
+!31 = !DILocation(line: 6, column: 1, scope: !6)