Patch for dbg variable instrinsics to point towards cloned values in JumpThreading

[BenJMudd]

Summary

This is a patch to fix debug value intrinsics outside of cloned blocks in the jumpthreading pass to point towards any derived values. If it cannot it sets them to undef

[nlopes]

llvm/lib/Transforms/Utils/SSAUpdater.cpp

221

Please use PoisonValue as placeholder whenever possible. We are trying to get rid of undef in LLVM.
Thank you!

[BenJMudd]

llvm/lib/Transforms/Utils/SSAUpdater.cpp

221

This patch doesnt introduce any newly created undef Values, just moving where they're created, so I believe it should stay undef for now, until this and the relevant tests are migrated

[probinson]

Please use clang-format-patch to correct some style issues.

[probinson]

llvm/include/llvm/Transforms/Utils/SSAUpdater.h

121

[BenJMudd]

Used clang-format-diff to fix formatting issues brought up by Paul Robinson

[BenJMudd]

it's -> its

[probinson]

Please generate diffs with full context (e.g., -U999999 in the diff/show command). It's really helpful to be able to look above and below the modified lines to understand the context of the patch.

[BenJMudd]

Added context to diff file

[probinson]

One minor comment. I don't feel comfortable enough with metadata to actually approve this, however.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

2058

[BenJMudd]

Added comment from Paul Robinson

[StephenTozer]

Changes LGTM!

[BenJMudd]

Moved definition of NewVal in SSAUpdater.cpp line 217 -> 219

[Michael137]

FYI, it looks like this broke https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/50434/testReport/junit/lldb-api/tools_lldb-vscode_optimized/TestVSCode_optimized_py/ where we're presumably relying on a variable to have gotten optimised out but which is now not the case anymore. So not an issue with this patch necessarily, just notifying.

Snippet from test:

int main(int argc, char const *argv[]) {               
  int optimized = argc > 1 ? std::stoi(argv[1]) : 0;   
                                                       
  printf("argc: %d, optimized: %d\n", argc, optimized);

compiled with -glldb -O3

[aprantl]

In D140404#4096775, @Michael137 wrote:

FYI, it looks like this broke https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/50434/testReport/junit/lldb-api/tools_lldb-vscode_optimized/TestVSCode_optimized_py/ where we're presumably relying on a variable to have gotten optimised out but which is now not the case anymore. So not an issue with this patch necessarily, just notifying.

Snippet from test:

int main(int argc, char const *argv[]) {               
  int optimized = argc > 1 ? std::stoi(argv[1]) : 0;   
                                                       
  printf("argc: %d, optimized: %d\n", argc, optimized);

compiled with -glldb -O3

In D140404#4096775, @Michael137 wrote:

FYI, it looks like this broke https://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/50434/testReport/junit/lldb-api/tools_lldb-vscode_optimized/TestVSCode_optimized_py/ where we're presumably relying on a variable to have gotten optimised out but which is now not the case anymore. So not an issue with this patch necessarily, just notifying.

Snippet from test:

int main(int argc, char const *argv[]) {               
  int optimized = argc > 1 ? std::stoi(argv[1]) : 0;   
                                                       
  printf("argc: %d, optimized: %d\n", argc, optimized);

compiled with -glldb -O3

If it's relying on debug info to get lost would using a nodebug attribute work, or does it need a variable, but without a location? In that case, we could rewrite the test to compile to LLVM IR at -O0, use sed to remote the location from the dbg.declare() and then compile the patch IR with clang. That would be cross-architecture and slightly more reliable (if still ugly) than relying on -O3 doing something specific.

[uabelho]

Hi,

It looks like this patch makes jump-threading yield different results with/without debug info.
With

opt -passes=jump-threading bbi-78731_red.ll -S -o -

We get e.g

for.cond:                                         ; preds = %lor.end51, %entry
  %cond4130 = phi i32 [ undef, %entry ], [ %cond4131, %lor.end51 ]
  %e.0 = phi i32 [ 0, %entry ], [ %cond3111226, %lor.end51 ]

and if we comment out the call to llvm.dbg.value we instead get

for.cond:                                         ; preds = %lor.end51, %entry
  %e.0 = phi i32 [ 0, %entry ], [ %cond3111226, %lor.end51 ]

bbi-78731_red.ll3 KBDownload

[jmorse]

/me squints -- I think the idea here was that if SSAUpdater has a value at the end of the block we can use that and it won't cause new codegen; but then we're using GetValueInMiddleOfBlock, which will generate code in certain circumstances.

@StephenTozer @BenJMudd Presumably we can just use GetValueAtEndOfBlock as this isn't a general SSA update query, we have a guarantee that only blocks outside of the the (threaded) value definitions will be updated, where there's no need to consider definitions in the middle of the block.

[uabelho]

In D140404#4109678, @jmorse wrote:

/me squints -- I think the idea here was that if SSAUpdater has a value at the end of the block we can use that and it won't cause new codegen; but then we're using GetValueInMiddleOfBlock, which will generate code in certain circumstances.

@StephenTozer @BenJMudd Presumably we can just use GetValueAtEndOfBlock as this isn't a general SSA update query, we have a guarantee that only blocks outside of the the (threaded) value definitions will be updated, where there's no need to consider definitions in the middle of the block.

I just did a quick test to do

 void SSAUpdater::UpdateDebugValue(Instruction *I, DbgValueInst *DbgValue) {
   BasicBlock *UserBB = DbgValue->getParent();
   if (HasValueForBlock(UserBB)) {
-    Value *NewVal = GetValueInMiddleOfBlock(UserBB);
+    Value *NewVal = GetValueAtEndOfBlock(UserBB);
     DbgValue->replaceVariableLocationOp(I, NewVal);
   }
   else
     DbgValue->setKillLocation();
 }

and then the difference I saw with/without debug info disappears.
I don't know anything about this, just wanted to let you know your suggestion indeed seems to work.

[StephenTozer]

In D140404#4109678, @jmorse wrote:

/me squints -- I think the idea here was that if SSAUpdater has a value at the end of the block we can use that and it won't cause new codegen; but then we're using GetValueInMiddleOfBlock, which will generate code in certain circumstances.

Ah, my bad - I've bumped into this before and saw the potential for CodeGen changes, but misread/misremembered the logic and thought that the HasValueForBlock check was guarding against CodeGen. I think GetValueAtEndOfBlock can also generate SSA, the function for this is FindValueForBlock.

[BenJMudd]

Ah ok, I had no idea that GetValueInMiddleOfBlock was causing code gen. @StephenTozer using FindValueForBlock seems to be the best solution then, thanks.

[StephenTozer]

Actually looking back over it I'd add further - FindValueForBlock isn't necessarily right because we're looking for values in the middle of the block, and that function will give us the value at the end only (which may be incorrect depending on the position of the debug value). I encountered this problem in MachineSSAUpdater, and the approach I took there was to add a ExistingValueOnly parameter to GetValue(InMiddle|AtEnd)OfBlock that performs all the same logic but returns empty if it would need to generate any code to provide a value. Happy to repeat that fix here!

[jmorse]

Cool, sounds like this is just a case of mistaken-function-identity, thanks for catching this @uabelho. I'll drop in a follow-up patch shortly to use GetValueAtEndOfBlock

llvm/include/llvm/Transforms/Utils/SSAUpdater.h

 class Instruction;
 class LoadInst;
 class PHINode;
 template <typename T> class SmallVectorImpl;
 template <typename T> class SSAUpdaterTraits;
 class Type;
 class Use;
 class Value;
+class DbgValueInst;
 
 /// Helper class for SSA formation on a set of values defined in
 /// multiple blocks.
 ///
 /// This is used when code duplication or another unstructured
 /// transformation wants to rewrite a set of uses of one value with uses of a
 /// set of values.
 class SSAUpdater {
public:
   ///
   /// This handles PHI nodes, which use their value in the corresponding
   /// predecessor. Note that this will not work if the use is supposed to be
   /// rewritten to a value defined in the same block as the use, but above it.
   /// Any 'AddAvailableValue's added for the use's block will be considered to
   /// be below it.
   void RewriteUse(Use &U);
 
+  /// Rewrite debug value intrinsics to conform to a new SSA form.
+  ///
+  /// This will scout out all the debug value instrinsics associated with
+  /// the instruction. Anything outside of its block will have its
+  /// value set to the new SSA value if available, and undef if not.
+  void UpdateDebugValues(Instruction *I);
+  void UpdateDebugValues(Instruction *I,
+                         SmallVectorImpl<DbgValueInst *> &DbgValues);
+
   /// Rewrite a use like \c RewriteUse but handling in-block definitions.
   ///
   /// This version of the method can rewrite uses in the same block as
   /// a definition, because it assumes that all uses of a value are below any
   /// inserted values.
   void RewriteUseAfterInsertions(Use &U);
 
 private:
   Value *GetValueAtEndOfBlockInternal(BasicBlock *BB);
+  void UpdateDebugValue(Instruction *I, DbgValueInst *DbgValue);
 };
 
 /// Helper class for promoting a collection of loads and stores into SSA
 /// Form using the SSAUpdater.
 ///
 /// This handles complexities that SSAUpdater doesn't, such as multiple loads
 /// and stores in one block.
 ///

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/LLVMContext.h"
void JumpThreadingPass::updateSSA(
     BasicBlock *BB, BasicBlock *NewBB,
     DenseMap<Instruction *, Value *> &ValueMapping) {
   // If there were values defined in BB that are used outside the block, then we
   // now have to update all uses of the value to use either the original value,
   // the cloned value, or some PHI derived value.  This can require arbitrary
   // PHI insertion, of which we are prepared to do, clean these up now.
   SSAUpdater SSAUpdate;
   SmallVector<Use *, 16> UsesToRename;
+  SmallVector<DbgValueInst *, 4> DbgValues;
 
   for (Instruction &I : *BB) {
     // Scan all uses of this instruction to see if it is used outside of its
     // block, and if so, record them in UsesToRename.
     for (Use &U : I.uses()) {
       Instruction *User = cast<Instruction>(U.getUser());
       if (PHINode *UserPN = dyn_cast<PHINode>(User)) {
         if (UserPN->getIncomingBlock(U) == BB)
           continue;
       } else if (User->getParent() == BB)
         continue;
 
       UsesToRename.push_back(&U);
     }
 
+    // Find debug values outside of the block
+    findDbgValues(DbgValues, &I);
+    DbgValues.erase(remove_if(DbgValues,
+                              [&](const DbgValueInst *DbgVal) {
+                                return DbgVal->getParent() == BB;
+                              }),
+                    DbgValues.end());
+
     // If there are no uses outside the block, we're done with this instruction.
-    if (UsesToRename.empty())
+    if (UsesToRename.empty() && DbgValues.empty())
       continue;
     LLVM_DEBUG(dbgs() << "JT: Renaming non-local uses of: " << I << "\n");
 
     // We found a use of I outside of BB.  Rename all uses of I that are outside
     // its block to be uses of the appropriate PHI node etc.  See ValuesInBlocks
     // with the two values we know.
     SSAUpdate.Initialize(I.getType(), I.getName());
     SSAUpdate.AddAvailableValue(BB, &I);
     SSAUpdate.AddAvailableValue(NewBB, ValueMapping[&I]);
 
     while (!UsesToRename.empty())
       SSAUpdate.RewriteUse(*UsesToRename.pop_back_val());
+    if (!DbgValues.empty()) {
+      SSAUpdate.UpdateDebugValues(&I, DbgValues);
+      DbgValues.clear();
+    }
+
     LLVM_DEBUG(dbgs() << "\n");
   }
 }
 
 /// Clone instructions in range [BI, BE) to NewBB.  For PHI nodes, we only clone
 /// arguments that come from PredBB.  Return the map from the variables in the
 /// source basic block to the variables in the newly created basic block.
 DenseMap<Instruction *, Value *>

llvm/lib/Transforms/Utils/SSAUpdater.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
void SSAUpdater::RewriteUse(Use &U) {
   if (PHINode *UserPN = dyn_cast<PHINode>(User))
     V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
   else
     V = GetValueInMiddleOfBlock(User->getParent());
 
   U.set(V);
 }
 
+void SSAUpdater::UpdateDebugValues(Instruction *I) {
+  SmallVector<DbgValueInst *, 4> DbgValues;
+  llvm::findDbgValues(DbgValues, I);
+  for (auto &DbgValue : DbgValues) {
+    if (DbgValue->getParent() == I->getParent())
+      continue;
+    UpdateDebugValue(I, DbgValue);
+  }
+}
+
+void SSAUpdater::UpdateDebugValues(Instruction *I,
+                                   SmallVectorImpl<DbgValueInst *> &DbgValues) {
+  for (auto &DbgValue : DbgValues) {
+    UpdateDebugValue(I, DbgValue);
+  }
+}
+
+void SSAUpdater::UpdateDebugValue(Instruction *I, DbgValueInst *DbgValue) {
+  BasicBlock *UserBB = DbgValue->getParent();
+  if (HasValueForBlock(UserBB)) {
+    Value *NewVal = GetValueInMiddleOfBlock(UserBB);
+    DbgValue->replaceVariableLocationOp(I, NewVal);
+  }
+  else
+    DbgValue->setUndef();
+}
+
 void SSAUpdater::RewriteUseAfterInsertions(Use &U) {
   Instruction *User = cast<Instruction>(U.getUser());
 
   Value *V;
   if (PHINode *UserPN = dyn_cast<PHINode>(User))
     V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
   else
     V = GetValueAtEndOfBlock(User->getParent());

llvm/test/Transforms/JumpThreading/thread-debug-info.ll

 bb.f4:                                            ; preds = %bb.file
   call void @f4(), !dbg !27
   br label %exit, !dbg !28
 
 exit:                                             ; preds = %bb.f4, %bb.f3, %bb.f2
   ret void, !dbg !29
 }
 
+; This is testing for debug value instrinsics outside of the threaded block pointing to a value
+; inside to correctly take any new definitions.
+define void @test2(i32 %cond1, i32 %cond2) !dbg !5 {
+; CHECK: bb.f3
+; CHECK: call void @llvm.dbg.value(metadata ptr @a, metadata !{{[0-9]+}}, metadata !DIExpression()), !dbg !{{[0-9]+}}
+; CHECK: bb.f4
+; CHECK-NEXT: [[PTR3:%.*]] = phi ptr [ null, %bb.cond2 ]
+; CHECK-NEXT: call void @llvm.dbg.value(metadata ptr [[PTR3]], metadata !{{[0-9]+}}, metadata !DIExpression()), !dbg !{{[0-9]+}}
+entry:
+  %tobool = icmp eq i32 %cond1, 0, !dbg !15
+  br i1 %tobool, label %bb.cond2, label %bb.f1, !dbg !16
+
+bb.f1:                                            ; preds = %entry
+  call void @f1(), !dbg !17
+  br label %bb.cond2, !dbg !18
+
+bb.cond2:                                         ; preds = %bb.f1, %entry
+  %ptr = phi ptr [ null, %bb.f1 ], [ @a, %entry ], !dbg !19
+  %tobool1 = icmp eq i32 %cond2, 0, !dbg !20
+  br i1 %tobool1, label %bb.file, label %bb.f2, !dbg !21
+
+bb.f2:                                            ; preds = %bb.cond2
+  call void @f2(), !dbg !22
+  br label %exit, !dbg !23
+
+bb.file:                                          ; preds = %bb.cond2
+  %cmp = icmp eq ptr %ptr, null, !dbg !24
+  call void @llvm.dbg.value(metadata ptr %ptr, metadata !14, metadata !DIExpression()), !dbg !21
+  br i1 %cmp, label %bb.f4, label %bb.f3, !dbg !25
+
+bb.f3:                                            ; preds = %bb.file
+  call void @f3(), !dbg !26
+  br label %exit, !dbg !27
+
+bb.f4:                                            ; preds = %bb.file
+  call void @f4(), !dbg !28
+  br label %exit, !dbg !29
+
+exit:                                             ; preds = %bb.f4, %bb.f3, %bb.f2
+  ret void, !dbg !29
+}
+
 declare void @f1()
 
 declare void @f2()
 
 declare void @f3()
 
 declare void @f4()
 

 !22 = !DILocation(line: 8, column: 1, scope: !5)
 !23 = !DILocation(line: 9, column: 1, scope: !5)
 !24 = !DILocation(line: 10, column: 1, scope: !5)
 !25 = !DILocation(line: 11, column: 1, scope: !5)
 !26 = !DILocation(line: 12, column: 1, scope: !5)
 !27 = !DILocation(line: 13, column: 1, scope: !5)
 !28 = !DILocation(line: 14, column: 1, scope: !5)
 !29 = !DILocation(line: 15, column: 1, scope: !5)
 No newline at end of file