[DebugInfo][LCSSA] Rewrite pre-existing debug values outside loop

[dstenb]

Summary

Extend LCSSA so that debug values outside loops are rewritten to
use the PHI nodes that the pass creates.

This fixes PR39019. In that case, we ran LCSSA on a loop that
was later on vectorized, which left us with something like this:

for.cond.cleanup:
  %add.lcssa = phi i32 [ %add, %for.body ], [ %34, %middle.block ]
  call void @llvm.dbg.value(metadata i32 %add,
  ret i32 %add.lcssa

for.body:
  %add =
  [...]
  br i1 %exitcond, label %for.cond.cleanup, label %for.body

which later resulted in the debug.value becoming undef when
removing the scalar loop (and the location would have probably
been wrong for the vectorized case otherwise).

As we now may need to query the AvailableVals cache more than
once for a basic block, FindAvailableVals() in SSAUpdaterImpl is
changed so that it updates the cache for blocks that we do not
create a PHI node for, regardless of the block's number of
predecessors. The debug value in the attached IR reproducer
would not be properly rewritten without this.

Debug values residing in blocks where we have not inserted any
PHI nodes are currently left as-is by this patch. I'm not sure
what should be done with those uses.

[aprantl]

Thanks, this looks reasonable to me.

[mattd]

This LGTM.

lib/Transforms/Utils/LCSSA.cpp

117

Can we move this container and accompanying findDbgValue call closer to where it's used, around line 208, or is it necessary that we get the debug value early before we create the new PHIs?

[dstenb]

Move DbgValues and the findDbgValues() call closer to the use.

[dstenb]

lib/Transforms/Utils/LCSSA.cpp

117

I have moved it now! We should not drop nor add any metadata uses of I between this and the use, so it should be equivalent.

The only reason I put it here was to keep the collection of I's uses near each other, but yes, it is probably better to move DbgValues closer to its use!

[mattd]

lib/Transforms/Utils/LCSSA.cpp

117

Great, thanks!

[dstenb]

Thanks for the reviews! I'm planning on submitting this shortly.

include/llvm/Transforms/Utils/SSAUpdater.h

public:
   /// Indicate that a rewritten value is available in the specified block
   /// with the specified value.
   void AddAvailableValue(BasicBlock *BB, Value *V);
 
   /// Return true if the SSAUpdater already has a value for the specified
   /// block.
   bool HasValueForBlock(BasicBlock *BB) const;
 
+  /// Return the value for the specified block if the SSAUpdater has one,
+  /// otherwise return nullptr.
+  Value *FindValueForBlock(BasicBlock *BB) const;
+
   /// Construct SSA form, materializing a value that is live at the end
   /// of the specified block.
   Value *GetValueAtEndOfBlock(BasicBlock *BB);
 
   /// Construct SSA form, materializing a value that is live in the
   /// middle of the specified block.
   ///
   /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except

include/llvm/Transforms/Utils/SSAUpdaterImpl.h

void FindAvailableVals(BlockListTy *BlockList) {
 
     // Now go back through the worklist in reverse order to fill in the
     // arguments for any new PHIs added in the forward traversal.
     for (typename BlockListTy::reverse_iterator I = BlockList->rbegin(),
            E = BlockList->rend(); I != E; ++I) {
       BBInfo *Info = *I;
 
       if (Info->DefBB != Info) {
-        // Record the available value at join nodes to speed up subsequent
-        // uses of this SSAUpdater for the same value.
-        if (Info->NumPreds > 1)
-          (*AvailableVals)[Info->BB] = Info->DefBB->AvailableVal;
+        // Record the available value to speed up subsequent uses of this
+        // SSAUpdater for the same value.
         continue;
       }
 
       // Check if this block contains a newly added PHI.
       PhiT *PHI = Traits::ValueIsNewPHI(Info->AvailableVal, Updater);
       if (!PHI)
         continue;
 

lib/Transforms/Utils/LCSSA.cpp

 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/PredIteratorCache.h"
 #include "llvm/Pass.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "lcssa"
for (Use &U : I->uses()) {
       if (InstBB != UserBB && !L->contains(UserBB))
         UsesToRewrite.push_back(&U);
     }
 
     // If there are no uses outside the loop, exit with no change.
     if (UsesToRewrite.empty())
       continue;
 
     ++NumLCSSA; // We are applying the transformation
 
     // Invoke instructions are special in that their result value is not
     // available along their unwind edge. The code below tests to see whether
     // DomBB dominates the value, so adjust DomBB to the normal destination
     // block, which is effectively where the value is first usable.
     BasicBlock *DomBB = InstBB;
     if (auto *Inv = dyn_cast<InvokeInst>(I))
       DomBB = Inv->getNormalDest();
for (Use *UseToRewrite : UsesToRewrite) {
         UseToRewrite->set(&UserBB->front());
         continue;
       }
 
       // Otherwise, do full PHI insertion.
       SSAUpdate.RewriteUse(*UseToRewrite);
     }
 
+    SmallVector<DbgValueInst *, 4> DbgValues;
+    llvm::findDbgValues(DbgValues, I);
+
+    // Update pre-existing debug value uses that reside outside the loop.
+    auto &Ctx = I->getContext();
+    for (auto DVI : DbgValues) {
+      BasicBlock *UserBB = DVI->getParent();
+      if (InstBB == UserBB || L->contains(UserBB))
+        continue;
+      // We currently only handle debug values residing in blocks where we have
+      // inserted a PHI instruction.
+      if (Value *V = SSAUpdate.FindValueForBlock(UserBB))
+        DVI->setOperand(0, MetadataAsValue::get(Ctx, ValueAsMetadata::get(V)));
+    }
+
     // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
     // to post-process them to keep LCSSA form.
     for (PHINode *InsertedPN : InsertedPHIs) {
       if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
         if (!L->contains(OtherLoop))
           PostProcessPHIs.push_back(InsertedPN);
     }
 

lib/Transforms/Utils/SSAUpdater.cpp

void SSAUpdater::Initialize(Type *Ty, StringRef Name) {
   ProtoType = Ty;
   ProtoName = Name;
 }
 
 bool SSAUpdater::HasValueForBlock(BasicBlock *BB) const {
   return getAvailableVals(AV).count(BB);
 }
 
+Value *SSAUpdater::FindValueForBlock(BasicBlock *BB) const {
+  AvailableValsTy::iterator AVI = getAvailableVals(AV).find(BB);
+  return (AVI != getAvailableVals(AV).end()) ? AVI->second : nullptr;
+}
+
 void SSAUpdater::AddAvailableValue(BasicBlock *BB, Value *V) {
   assert(ProtoType && "Need to initialize SSAUpdater");
   assert(ProtoType == V->getType() &&
          "All rewritten values must have the same type");
   getAvailableVals(AV)[BB] = V;
 }
 
 static bool IsEquivalentPHI(PHINode *PHI,

test/Transforms/LCSSA/rewrite-existing-dbg-values.ll

+; RUN: opt -S -lcssa < %s | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+; Reproducer for PR39019.
+;
+; Verify that the llvm.dbg.value in the %for.cond.cleanup2 block is rewritten
+; to use the PHI node for %add that is created by LCSSA.
+
+; CHECK-LABEL: for.cond.cleanup2:
+; CHECK-NEXT: [[PN:%[^ ]*]] = phi i32 [ %add.lcssa, %for.cond.cleanup1 ]
+; CHECK-NEXT: call void @llvm.dbg.value(metadata i32 [[PN]], metadata [[VAR:![0-9]+]], metadata !DIExpression())
+; CHECK-NEXT: call void @bar(i32 [[PN]])
+
+; CHECK-LABEL: for.body:
+; CHECK: %add = add nsw i32 0, 2
+; CHECK: call void @llvm.dbg.value(metadata i32 %add, metadata [[VAR]], metadata !DIExpression())
+
+; CHECK: [[VAR]] = !DILocalVariable(name: "sum",
+
+; Function Attrs: nounwind
+define void @foo() #0 !dbg !6 {
+entry:
+  br label %for.cond.preheader, !dbg !12
+
+for.cond.preheader:                               ; preds = %for.cond.cleanup1, %entry
+  br label %for.body, !dbg !12
+
+for.cond.cleanup2:                                ; preds = %for.cond.cleanup1
+  call void @llvm.dbg.value(metadata i32 %add, metadata !9, metadata !DIExpression()), !dbg !12
+  tail call void @bar(i32 %add) #0, !dbg !12
+  ret void, !dbg !12
+
+for.cond.cleanup1:                                ; preds = %for.body
+  br i1 false, label %for.cond.preheader, label %for.cond.cleanup2, !dbg !12
+
+for.body:                                         ; preds = %for.body, %for.cond.preheader
+  %add = add nsw i32 0, 2, !dbg !12
+  call void @llvm.dbg.value(metadata i32 %add, metadata !9, metadata !DIExpression()), !dbg !12
+  br i1 false, label %for.body, label %for.cond.cleanup1, !dbg !12
+}
+
+; Function Attrs: nounwind
+declare void @bar(i32) #0
+
+; Function Attrs: nounwind readnone speculatable
+declare void @llvm.dbg.value(metadata, metadata, metadata) #1
+
+attributes #0 = { nounwind }
+attributes #1 = { nounwind readnone speculatable }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!3, !4}
+!llvm.ident = !{!5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 8.0.0", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, globals: !2, nameTableKind: None)
+!1 = !DIFile(filename: "foo.c", directory: "/")
+!2 = !{}
+!3 = !{i32 2, !"Dwarf Version", i32 4}
+!4 = !{i32 2, !"Debug Info Version", i32 3}
+!5 = !{!"clang version 8.0.0"}
+!6 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 10, type: !7, isLocal: false, isDefinition: true, scopeLine: 10, isOptimized: true, unit: !0, retainedNodes: !8)
+!7 = !DISubroutineType(types: !2)
+!8 = !{!9}
+!9 = !DILocalVariable(name: "sum", scope: !10, file: !1, line: 11, type: !11)
+!10 = !DILexicalBlockFile(scope: !6, file: !1, discriminator: 0)
+!11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+!12 = !DILocation(line: 0, scope: !10)