Update Debug Intrinsics in RewriteUsesOfClonedInstructions in LoopRotation

[tjablin]

Summary

Loop rotation clones instruction from the old header into the preheader. If there were uses of values produced by these instructions that were outside the loop, we have to insert PHI nodes to merge the two values. If the values are used by DbgIntrinsics they will be used as a MetadataAsValue of a ValueAsMetadata of the original values, and iterating all of the uses of the original value will not update the DbgIntrinsics. The new code checks if the values are used by DbgIntrinsics and if so, updates them using essentially the same logic as the original code.

The attached testcase demonstrates the issue. Without the fix, the DbgIntrinic outside the loop uses values computed inside the loop, even though these values do not dominate the DbgIntrinsic.

[dblaikie]

Does this cause changes in non-debug IR in the presence of debug info
intrinsics? (you mention that "If there were uses of values produced by
these instructions that were outside the loop, we have to insert PHI nodes
to merge the two values." - that sounds like it could be a problem, as
enabling debug info is not intended to change optimization/code generation)

[tjablin]

Update to address David's comments. This version of the patch will never insert additional PHINodes for DbgInfoIntrinsics. Instead, DbgInfoIntrinsics are updated when the needed Value is already live in the DbgInfoIntrinsic's BasicBlock. If the Value is dead, it is replaced with Undef.

[aprantl]

lib/Transforms/Scalar/LoopRotation.cpp

141

Missing a '.'

143

could use auto here, the type is obvious from context.

147

Could this be written as a range-based for?

148

Isn't this dangerous; could there be other metadata uses (TBAA, etc)? Should we use a dyn_cast here?

[tjablin]

Address Adrian's concerns:

• Add period to end of comment.
• Use auto where possible.
• Range-based for is not possible, since updating the use will also invalidate the underlying iterator.
• Switch to dyn_cast, although I'm pretty sure that only DbgIntrinsics use MetadataAsValue currently.

[aprantl]

Small nitpick, otherwise this looks good now unless David has remaining concerns.

thanks!

lib/Transforms/Scalar/LoopRotation.cpp

149

if !() continue; ?

[dblaikie]

nah, I'll leave it to you

[tjablin]

Switch to if !() continue; construct instead of nested if per Adrian's comment.

[cycheng]

Committed r269034
On behalf of Tom.

lib/Transforms/Scalar/LoopRotation.cpp

for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
         if (UserBB == OrigPreheader) {
           U = OrigPreHeaderVal;
           continue;
         }
       }
 
       // Anything else can be handled by SSAUpdater.
       SSA.RewriteUse(U);
+
+      // Replace MetadataAsValue(ValueAsMetadata(OrigHeaderVal)) uses in debug
+      // intrinsics
+      LLVMContext &C = OrigHeader->getContext();
+      if (ValueAsMetadata *VAM = ValueAsMetadata::getIfExists(OrigHeaderVal)) {
+        if (MetadataAsValue *MAV = MetadataAsValue::getIfExists(C, VAM)) {
+          for (auto UI = MAV->use_begin(), E = MAV->use_end(); UI != E; ) {
+            // Grab the use before incrementing the iterator.
+            Use &U = *UI++;
+            DbgInfoIntrinsic *UserInst = cast<DbgInfoIntrinsic>(U.getUser());
+            BasicBlock *UserBB = UserInst->getParent();
+
+            // The original users in the OrigHeader are already using the
+            // original definitions.
+            if (UserBB == OrigHeader)
+              continue;
+            
+            // Users in the OrigPreHeader need to use the value to which the
+            // original definitions are mapped and anything else can be handled
+            // by the SSAUpdater
+            Value *NewVal = UserBB == OrigPreheader ?
+              OrigPreHeaderVal :
+              SSA.GetValueInMiddleOfBlock(UserBB);
+            U = MetadataAsValue::get(C, ValueAsMetadata::get(NewVal));
+          }
+        }
+      }
     }
   }
 }
 
 /// 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
 /// form. This property is satisfied because simplifying the loop latch can only
 /// happen once across multiple invocations of the LoopRotate pass.
 static bool rotateLoop(Loop *L, unsigned MaxHeaderSize, LoopInfo *LI,
                        const TargetTransformInfo *TTI, AssumptionCache *AC,
                        DominatorTree *DT, ScalarEvolution *SE,
                        bool SimplifiedLatch) {
   // If the loop has only one block then there is not much to rotate.
   if (L->getBlocks().size() == 1)

test/Transforms/LoopRotate/dbgvalue.ll

 ; RUN: opt -S -loop-rotate < %s | FileCheck %s
 
 declare void @llvm.dbg.declare(metadata, metadata, metadata) nounwind readnone
 declare void @llvm.dbg.value(metadata, i64, metadata, metadata) nounwind readnone
 
 define i32 @tak(i32 %x, i32 %y, i32 %z) nounwind ssp !dbg !0 {
 ; CHECK-LABEL: define i32 @tak(
 ; CHECK: entry
 ; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 %x
+; CHECK: tail call void @llvm.dbg.value(metadata i32 %call
 
 entry:
   br label %tailrecurse
 
 tailrecurse:                                      ; preds = %if.then, %entry
   %x.tr = phi i32 [ %x, %entry ], [ %call, %if.then ]
   %y.tr = phi i32 [ %y, %entry ], [ %call9, %if.then ]
   %z.tr = phi i32 [ %z, %entry ], [ %call14, %if.then ]

 
 if.end:                                           ; preds = %tailrecurse
   br label %return, !dbg !16
 
 return:                                           ; preds = %if.end
   ret i32 %z.tr, !dbg !17
 }
 
+define i32 @tak2(i32 %x, i32 %y, i32 %z) nounwind ssp !dbg !0 {
+; CHECK-LABEL: define i32 @tak2(
+; CHECK: entry
+; CHECK: tail call void @llvm.dbg.value(metadata i32 %x.tr
+; CHECK: tail call void @llvm.dbg.value(metadata i32 %x.tr
+
+entry:
+  br label %tailrecurse
+
+tailrecurse:                                      ; preds = %if.then, %entry
+  %x.tr = phi i32 [ %x, %entry ], [ %call, %if.then ]
+  %y.tr = phi i32 [ %y, %entry ], [ %call9, %if.then ]
+  %z.tr = phi i32 [ %z, %entry ], [ %call14, %if.then ]
+  %cmp = icmp slt i32 %y.tr, %x.tr, !dbg !12
+  br i1 %cmp, label %if.then, label %if.end, !dbg !12
+
+if.then:                                          ; preds = %tailrecurse
+  tail call void @llvm.dbg.value(metadata i32 %x.tr, i64 0, metadata !6, metadata !DIExpression()), !dbg !7
+  tail call void @llvm.dbg.value(metadata i32 %y.tr, i64 0, metadata !8, metadata !DIExpression()), !dbg !9
+  tail call void @llvm.dbg.value(metadata i32 %z.tr, i64 0, metadata !10, metadata !DIExpression()), !dbg !11
+  %sub = sub nsw i32 %x.tr, 1, !dbg !14
+  %call = tail call i32 @tak(i32 %sub, i32 %y.tr, i32 %z.tr), !dbg !14
+  %sub6 = sub nsw i32 %y.tr, 1, !dbg !14
+  %call9 = tail call i32 @tak(i32 %sub6, i32 %z.tr, i32 %x.tr), !dbg !14
+  %sub11 = sub nsw i32 %z.tr, 1, !dbg !14
+  %call14 = tail call i32 @tak(i32 %sub11, i32 %x.tr, i32 %y.tr), !dbg !14
+  br label %tailrecurse
+
+if.end:                                           ; preds = %tailrecurse
+  tail call void @llvm.dbg.value(metadata i32 %x.tr, i64 0, metadata !6, metadata !DIExpression()), !dbg !7
+  tail call void @llvm.dbg.value(metadata i32 %y.tr, i64 0, metadata !8, metadata !DIExpression()), !dbg !9
+  tail call void @llvm.dbg.value(metadata i32 %z.tr, i64 0, metadata !10, metadata !DIExpression()), !dbg !11
+  br label %return, !dbg !16
+
+return:                                           ; preds = %if.end
+  ret i32 %z.tr, !dbg !17
+}
+
 @channelColumns = external global i64
 @horzPlane = external global i8*, align 8
 
 define void @FindFreeHorzSeg(i64 %startCol, i64 %row, i64* %rowStart) {
 ; Ensure that the loop increment basic block is rotated into the tail of the
 ; body, even though it contains a debug intrinsic call.
 ; CHECK-LABEL: define void @FindFreeHorzSeg(
 ; CHECK: %dec = add