[DebugInfo] Attempt to preserve more information during tail duplication

[StephenTozer]

Summary

As part of putting together the fix in D106557, I noticed that tail duplication looked to be handling debug info poorly - specifically, debug instructions would be dropped instead of being set undef, potentially extending the lifetimes of prior debug values that should be killed. Furthermore, the deleted debug instructions were not necessarily dead - it looks as though the deletion was added to prevent codegen from being affected by debug instructions, resulting in an overly aggressive dropping of debug info. This patch modifies this step to instead make the best attempt to recover debug info without making any codegen changes.

A function has been added to MachineSSAUpdater, GetExistingValueInMiddleOfBlock, which mimics the current GetValueInMiddleOfBlock function but with the addition that it will never generate any instructions, only fetch a vreg if one already exists. This is used to find valid VRegs for debug values, or else set them undef.

[jmorse]

This sounds really good; I feel bad about a considerable portion of logic being duplicated here though. Annoyingly as "please rewrite" is, could we instead:

• Give GetValueInMiddleOfBlock a default-false "AllowUnavailable" argument,
• Lambda-ise picking GetValueAtEndOfBlockInternal or the Existing flavour,
• Bail out returning $noreg just before creating new values

Or something like that. IMO, future generations will thank us.

llvm/include/llvm/CodeGen/MachineSSAUpdater.h

100

Nit, newline between comments and preceeding method. IMO "Same as the above" is easier to read, explicit being better than implicit.

102

llvm/lib/CodeGen/TailDuplicator.cpp

235–240

Performance opinion: better to store debug uses and re-visit rather than enumerate all the uses again, it'll preserve the same performance characteristics as before this patch.

Also: will not UseMO.setReg invalidate the vreg use list?

[StephenTozer]

llvm/lib/CodeGen/TailDuplicator.cpp

235–240

The vreg use list is (as far as I'm aware) a linked list, so calling setReg after iterating to the next use will not cause any issues.

[jmorse]

llvm/lib/CodeGen/TailDuplicator.cpp

235–240

Ah, I missed the pre-increment x_x

[StephenTozer]

Reduce code duplication, avoid unnecessary use-list iteration.

[StephenTozer]

Fix incorrect parameter, false -> true

[StephenTozer]

Ping.

[jmorse]

LGTM; however, will the use of isDebugValue cause this to affect variadic variable locations? It's probably fine to only address one form in this patch, and consider DBG_VALUE_LIST some other time.

llvm/lib/CodeGen/TailDuplicator.cpp

226

llvm/include/llvm/CodeGen/MachineSSAUpdater.h

public:
   /// value for the specified block.
   bool HasValueForBlock(MachineBasicBlock *BB) const;
 
   /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
   /// live at the end of the specified block.
   Register GetValueAtEndOfBlock(MachineBasicBlock *BB);
 
   /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
-  /// is live in the middle of the specified block.
+  /// is live in the middle of the specified block. If ExistingValueOnly is
+  /// true then this will only return an existing value or $noreg; otherwise new
+  /// instructions may be inserted to materialize a value.
   ///
   /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
   /// important case: if there is a definition of the rewritten value after the
   /// 'use' in BB.  Consider code like this:
   ///
   ///      X1 = ...
   ///   SomeBB:
   ///      use(X)
   ///      X2 = ...
   ///      br Cond, SomeBB, OutBB
   ///
   /// In this case, there are two values (X1 and X2) added to the AvailableVals
   /// set by the client of the rewriter, and those values are both live out of
   /// their respective blocks.  However, the use of X happens in the *middle* of
   /// a block.  Because of this, we need to insert a new PHI node in SomeBB to
   /// merge the appropriate values, and this value isn't live out of the block.
-  Register GetValueInMiddleOfBlock(MachineBasicBlock *BB);
+  Register GetValueInMiddleOfBlock(MachineBasicBlock *BB,
+                                   bool ExistingValueOnly = false);
 
   /// 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);
 
 private:
-  Register GetValueAtEndOfBlockInternal(MachineBasicBlock *BB);
+  // If ExistingValueOnly is true, will not create any new instructions. Used
+  // for debug values, which cannot modify Codegen.
+  Register GetValueAtEndOfBlockInternal(MachineBasicBlock *BB,
+                                        bool ExistingValueOnly = false);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_CODEGEN_MACHINESSAUPDATER_H

llvm/lib/CodeGen/MachineSSAUpdater.cpp

MachineInstrBuilder InsertNewDef(unsigned Opcode,
                            const TargetRegisterClass *RC,
                            MachineRegisterInfo *MRI,
                            const TargetInstrInfo *TII) {
   Register NewVR = MRI->createVirtualRegister(RC);
   return BuildMI(*BB, I, DebugLoc(), TII->get(Opcode), NewVR);
 }
 
 /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
-/// is live in the middle of the specified block.
+/// is live in the middle of the specified block. If ExistingValueOnly is
+/// true then this will only return an existing value or $noreg; otherwise new
+/// instructions may be inserted to materialize a value.
 ///
 /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
 /// important case: if there is a definition of the rewritten value after the
 /// 'use' in BB.  Consider code like this:
 ///
 ///      X1 = ...
 ///   SomeBB:
 ///      use(X)
 ///      X2 = ...
 ///      br Cond, SomeBB, OutBB
 ///
 /// In this case, there are two values (X1 and X2) added to the AvailableVals
 /// set by the client of the rewriter, and those values are both live out of
 /// their respective blocks.  However, the use of X happens in the *middle* of
 /// a block.  Because of this, we need to insert a new PHI node in SomeBB to
 /// merge the appropriate values, and this value isn't live out of the block.
-Register MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB) {
+Register MachineSSAUpdater::GetValueInMiddleOfBlock(MachineBasicBlock *BB,
+                                                    bool ExistingValueOnly) {
   // If there is no definition of the renamed variable in this block, just use
   // GetValueAtEndOfBlock to do our work.
   if (!HasValueForBlock(BB))
-    return GetValueAtEndOfBlockInternal(BB);
+    return GetValueAtEndOfBlockInternal(BB, ExistingValueOnly);
 
   // If there are no predecessors, just return undef.
   if (BB->pred_empty()) {
+    // If we cannot insert new instructions, just return $noreg.
+    if (ExistingValueOnly)
+      return Register();
     // Insert an implicit_def to represent an undef value.
     MachineInstr *NewDef = InsertNewDef(TargetOpcode::IMPLICIT_DEF,
                                         BB, BB->getFirstTerminator(),
                                         VRC, MRI, TII);
     return NewDef->getOperand(0).getReg();
   }
 
   // Otherwise, we have the hard case.  Get the live-in values for each
   // predecessor.
   SmallVector<std::pair<MachineBasicBlock*, Register>, 8> PredValues;
   Register SingularValue;
 
   bool isFirstPred = true;
   for (MachineBasicBlock *PredBB : BB->predecessors()) {
-    Register PredVal = GetValueAtEndOfBlockInternal(PredBB);
+    Register PredVal = GetValueAtEndOfBlockInternal(PredBB, ExistingValueOnly);
     PredValues.push_back(std::make_pair(PredBB, PredVal));
 
     // Compute SingularValue.
     if (isFirstPred) {
       SingularValue = PredVal;
       isFirstPred = false;
     } else if (PredVal != SingularValue)
       SingularValue = Register();
   }
 
   // Otherwise, if all the merged values are the same, just use it.
   if (SingularValue)
     return SingularValue;
 
   // If an identical PHI is already in BB, just reuse it.
   Register DupPHI = LookForIdenticalPHI(BB, PredValues);
   if (DupPHI)
     return DupPHI;
 
+  // If we cannot create new instructions, return $noreg now.
+  if (ExistingValueOnly)
+    return Register();
+
   // Otherwise, we do need a PHI: insert one now.
   MachineBasicBlock::iterator Loc = BB->empty() ? BB->end() : BB->begin();
   MachineInstrBuilder InsertedPHI = InsertNewDef(TargetOpcode::PHI, BB,
                                                  Loc, VRC, MRI, TII);
 
   // Fill in all the predecessors of the PHI.
   for (unsigned i = 0, e = PredValues.size(); i != e; ++i)
     InsertedPHI.addReg(PredValues[i].second).addMBB(PredValues[i].first);

 };
 
 } // end namespace llvm
 
 /// GetValueAtEndOfBlockInternal - Check to see if AvailableVals has an entry
 /// for the specified BB and if so, return it.  If not, construct SSA form by
 /// first calculating the required placement of PHIs and then inserting new
 /// PHIs where needed.
-Register MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB){
+Register
+MachineSSAUpdater::GetValueAtEndOfBlockInternal(MachineBasicBlock *BB,
+                                                bool ExistingValueOnly) {
   AvailableValsTy &AvailableVals = getAvailableVals(AV);
-  if (Register V = AvailableVals[BB])
-    return V;
+  Register ExistingVal = AvailableVals.lookup(BB);
+  if (ExistingVal || ExistingValueOnly)
+    return ExistingVal;
 
   SSAUpdaterImpl<MachineSSAUpdater> Impl(this, &AvailableVals, InsertedPHIs);
   return Impl.GetValue(BB);
 }

llvm/lib/CodeGen/TailDuplicator.cpp

for (unsigned i = 0, e = SSAUpdateVRs.size(); i != e; ++i) {
       DenseMap<Register, AvailableValsTy>::iterator LI =
           SSAUpdateVals.find(VReg);
       for (unsigned j = 0, ee = LI->second.size(); j != ee; ++j) {
         MachineBasicBlock *SrcBB = LI->second[j].first;
         Register SrcReg = LI->second[j].second;
         SSAUpdate.AddAvailableValue(SrcBB, SrcReg);
       }
 
+      SmallVector<MachineOperand *> DebugUses;
       // Rewrite uses that are outside of the original def's block.
       MachineRegisterInfo::use_iterator UI = MRI->use_begin(VReg);
-      // Only remove instructions after loop, as DBG_VALUE_LISTs with multiple
-      // uses of VReg may invalidate the use iterator when erased.
-      SmallPtrSet<MachineInstr *, 4> InstrsToRemove;
       while (UI != MRI->use_end()) {
         MachineOperand &UseMO = *UI;
         MachineInstr *UseMI = UseMO.getParent();
         ++UI;
+        // Rewrite debug uses last so that they can take advantage of any
+        // register mappings introduced by other users in its BB, since we
+        // cannot create new register definitions specifically for the debug
+        // instruction (as debug instructions should not affect CodeGen).
         if (UseMI->isDebugValue()) {
-          // SSAUpdate can replace the use with an undef. That creates
-          // a debug instruction that is a kill.
-          // FIXME: Should it SSAUpdate job to delete debug instructions
-          // instead of replacing the use with undef?
-          InstrsToRemove.insert(UseMI);
+          DebugUses.push_back(&UseMO);
           continue;
         }
         if (UseMI->getParent() == DefBB && !UseMI->isPHI())
           continue;
         SSAUpdate.RewriteUse(UseMO);
       }
-      for (auto *MI : InstrsToRemove)
-        MI->eraseFromParent();
+      for (auto *UseMO : DebugUses) {
+        MachineInstr *UseMI = UseMO->getParent();
+        UseMO->setReg(
+            SSAUpdate.GetValueInMiddleOfBlock(UseMI->getParent(), true));
+      }
     }
 
     SSAUpdateVRs.clear();
     SSAUpdateVals.clear();
   }
 
   // Eliminate some of the copies inserted by tail duplication to maintain
   // SSA form.
   for (unsigned i = 0, e = Copies.size(); i != e; ++i) {

llvm/test/CodeGen/X86/tail-dup-debugvalue.mir

 # RUN: llc -run-pass=early-tailduplication -mtriple=x86_64-unknown-linux-gnu %s -o - | FileCheck %s
 
 # Tail Duplication may update SSA values and invalidate any DBG_VALUEs that
-# use those values; those DBG_VALUEs should be deleted. This behaviour is tested
+# use those values; those DBG_VALUEs should be set undef. This is tested
 # for DBG_VALUE users, and DBG_VALUE_LISTs that use the value multiple times.
 
-# CHECK-NOT: DBG_VALUE
+# CHECK: ![[VAR_J:[0-9]+]] = !DILocalVariable(name: "j"
+# CHECK: ![[VAR_K:[0-9]+]] = !DILocalVariable(name: "k"
+# CHECK-LABEL: bb.1.L:
+# CHECK: %[[REGISTER:[0-9]+]]:gr32 = PHI
+# CHECK-LABEL: bb.2.if.end4:
+# CHECK: DBG_VALUE_LIST ![[VAR_J]],
+# CHECK-SAME: %[[REGISTER]], 1, %[[REGISTER]]
+# CHECK: DBG_VALUE %[[REGISTER]], $noreg, ![[VAR_K]]
+
 --- |
   target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
   target triple = "x86_64-unknown-linux-gnu"
   
   define dso_local void @main() local_unnamed_addr #0 !dbg !15 {
   entry:
     br label %L.outer