Propagate debug info for Phi node in SSAUpdater

[samparker]

Summary

Phi nodes are created in the SSAUpdater, however debug info is not updated causing incorrect values after transformations like loop rotation. This patch inserts a new call to dbg.value for each variable operand of the phi that has debug metadata attached.

[aprantl]

test/Transforms/Util/phi-dbgvalue.ll

41

The "string" attributes can probably be stripped.

[keith.walker.arm]

This change looks good to me, but I think it would be good if someone more experienced than me in the usage of debug metadata could give the final OK to this change.

[samparker]

Removed the string attributes from the test case. Also moved the Update function into SSAUpdater instead of a static function of SSAUpdaterTraits because I wanted to call the function from within SSAUpdater as well.

[samparker]

Ping. Is there anyone who could take a look at this please?

[samparker]

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.

[samparker]

Hi @dberlin
I see you're involved in debug, IR and SSA, so would you mind taking a look at this?

Thanks,
Sam

[• dberlin]

lib/Transforms/Utils/SSAUpdater.cpp

218

This looks really badly n^2 per call.
Is there really no faster way?

[samparker]

lib/Transforms/Utils/SSAUpdater.cpp

218

I know it is going to be slow, but it was the only way I found... I have basically no experience in this area though and was hoping to get some suggestions.

[• dberlin]

Staring at this, so far i don't believe this is the correct way to fix this.

If you look at your before test case, there is a debug value for the phi.
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

After, the dbg.value is destroyed as the phi is recreated in for.body:
for.body:
%i.01 = phi i32 [ 1, %entry ], [ %inc, %for.body ]

I agree that seems bad.

However, you are adding debug info based on operands of the phi, etc.
I don't see why the answer isn't "stash away debug value in loop rotate", "reattach to new phi name"?

Doing this in ssa updater seems .. strange, and the way you are doing it seems even stranger.
At worst, if you ere doing it in ssa updater, it should be something like "if the old phi result (*not* operand) had a use in debug info, the new one should".
But even then, this is something i would expect callers to deal with as they rewrite uses.

[samparker]

Hi Daniel,

Thanks for your comments. I had hoped that performing this in the SSA updater would prevent this bug from appearing in other passes that update/replace the Phi nodes. Do you think there's a way to achieve this in a manner that isn't local to loop rotate? And by stashing and replacing, will getMetadata and setMetadata be okay for this purpose? Would I still not have to update the debug value to reflect the value of the new phi node?

Thanks again,
sam

[• dberlin]

In D29578#681419, @samparker wrote:

Hi Daniel,

Thanks for your comments. I had hoped that performing this in the SSA updater would prevent this bug from appearing in other passes that update/replace the Phi nodes.

I agree with your general idea and thought that it would be nice to solve once and for all.
However, if you wanted to do that, you'd have to do two things:
A. Demonstrate it was a general problem that needs solving (Ie there were other places with the same issue). This is just because we don't want to make a general thing to solve problems that may not actually be general.
B. Demonstrate you could do so quickly and efficiently in a general way. Especially in SSAUpdater, which gets used a *lot*.
If you want to do both, great.
So far, i think B is your bigger issue. Your approach so far is N^2, and it seems hard to make it not N^2 with the API SSAUpdater provides. I've got an SSAUpdater rewrite outstanding, but i didn't change the API.

If you demonstrate it's a larger problem, i'm happy to help think about what kind of API might allow us to solve this issue in better time bounds.
But such a thing may not be theoretically possible. In which case, i'd argue we should just bite the bullet and fix passes that have this issue, and do so in a way that is faster (and then add testcases to make sure nobody breaks it)

Do you think there's a way to achieve this in a manner that isn't local to loop rotate?

I'd need more data. IE at least some other examples where passes are breaking this

And by stashing and replacing, will getMetadata and setMetadata be okay for this purpose?

Sure

Would I still not have to update the debug value to reflect the value of the new phi node?

You would, but again, in the case of loop rotate, you know you have a 1:1 mapping between old and new.

Thanks again,
sam

[samparker]

Ok, well I will try to fix this in loop rotate for the moment. @keith.walker.arm , do we have any other debug issues that maybe related to this?

[keith.walker.arm]

I currently don't know of any other optimisation phases where the debug information for the results of a phi node is incorrect; but I would not be surprised to find that once the loop rotate issue is fixed and the information is able to correctly propagate in this phase that other optimisation phases which copy phi nodes are also found to have a problem.

[samparker]

I've created a new patch to make the changes to LoopRotate: https://reviews.llvm.org/D30190

include/llvm/CodeGen/MachineSSAUpdater.h

 
   /// RewriteUse - Rewrite a use of the symbolic value.  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(MachineOperand &U);
 
+  // TODO This is unimplemented.
+  /// UpdatePHIDebugInfo - Insert dbg.value calls to newly created PHI nodes
+  /// so that debug info can be kept up-to-date. Unimplemented.
+  void UpdatePHIDebugInfo(MachineInstr *PHI) { }
+
 private:
   unsigned GetValueAtEndOfBlockInternal(MachineBasicBlock *BB);
 
   void operator=(const MachineSSAUpdater&) = delete;
   MachineSSAUpdater(const MachineSSAUpdater&) = delete;
 };
 
 } // End llvm namespace
 
 #endif

include/llvm/Transforms/Utils/SSAUpdater.h

 
   /// \brief 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);
 
+  /// UpdatePHIDebugInfo - Insert dbg.value calls to newly created PHI nodes
+  /// so that debug info can be kept up-to-date.
+  void UpdatePHIDebugInfo(PHINode *PHI);
+
 private:
   Value *GetValueAtEndOfBlockInternal(BasicBlock *BB);
 };
 
 /// \brief 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

include/llvm/Transforms/Utils/SSAUpdaterImpl.h

         BBInfo *PredInfo = Info->Preds[p];
         BlkT *Pred = PredInfo->BB;
         // Skip to the nearest preceding definition.
         if (PredInfo->DefBB != PredInfo)
           PredInfo = PredInfo->DefBB;
         Traits::AddPHIOperand(PHI, PredInfo->AvailableVal, Pred);
       }
 
+      Updater->UpdatePHIDebugInfo(PHI);
       DEBUG(dbgs() << "  Inserted PHI: " << *PHI << "\n");
 
       // If the client wants to know about all new instructions, tell it.
       if (InsertedPHIs) InsertedPHIs->push_back(PHI);
     }
   }
 
   /// FindExistingPHI - Look through the PHI nodes in a block to see if any of

lib/Transforms/Utils/SSAUpdater.cpp

 #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/DebugLoc.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Utils/SSAUpdater.h"
if (Value *V =
     return V;
   }
 
   // Set the DebugLoc of the inserted PHI, if available.
   DebugLoc DL;
   if (const Instruction *I = BB->getFirstNonPHI())
       DL = I->getDebugLoc();
   InsertedPHI->setDebugLoc(DL);
+  UpdatePHIDebugInfo(InsertedPHI);
 
   // If the client wants to know about all new instructions, tell it.
   if (InsertedPHIs) InsertedPHIs->push_back(InsertedPHI);
 
   DEBUG(dbgs() << "  Inserted PHI: " << *InsertedPHI << "\n");
   return InsertedPHI;
 }
 
void SSAUpdater::RewriteUseAfterInsertions(Use &U) {
   if (PHINode *UserPN = dyn_cast<PHINode>(User))
     V = GetValueAtEndOfBlock(UserPN->getIncomingBlock(U));
   else
     V = GetValueAtEndOfBlock(User->getParent());
   
   U.set(V);
 }
 
+void SSAUpdater::UpdatePHIDebugInfo(PHINode *PHI) {
+  LLVMContext &C = PHI->getParent()->getContext();
+
+  for (unsigned i = 0; i < PHI->getNumOperands(); ++i) {
+    Value *Val = PHI->getOperand(i);
+
+    if (isa<Constant>(Val))
+      continue;
+
+    // If the value is a non constant and it has debug info attached, create
+    // another debug value for this PHI so that the debug value is kept
+    // up-to-date.
+    if (auto *VAM = ValueAsMetadata::getIfExists(Val)) {
+      if (auto *MAV = MetadataAsValue::getIfExists(C, VAM)) {
+        for (auto UI = MAV->use_begin(), E = MAV->use_end(); UI != E;) {
+          // Grab the use before incrementing the iterator. Otherwise,
+          // altering the Use will invalidate the iterator.
+          Use &U = *UI++;
+          auto *UserInst = dyn_cast<DbgInfoIntrinsic>(U.getUser());
+          if (!UserInst)
+            continue;
+          Instruction *Clone = UserInst->clone();
+          auto PhiMAV = MetadataAsValue::get(C, ValueAsMetadata::get(PHI));
+          Clone->setOperand(0, PhiMAV);
+          BasicBlock *BB = PHI->getParent();
+          Clone->insertBefore(BB->getFirstNonPHIOrDbgOrLifetime());
+        }
+      }
+    }
+  }
+}
+
 namespace llvm {
 
 template<>
 class SSAUpdaterTraits<SSAUpdater> {
 public:
   typedef BasicBlock BlkT;
   typedef Value *ValT;
   typedef PHINode PhiT;

test/Transforms/Util/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)