[DebugInfo][X86] Teach Optimize LEAs pass to handle debug values

[andrewng]

Summary

This patch fixes an issue in the Optimize LEAs pass where redundant LEAs were not removed because they were being used by debug values. This issue was discovered when comparing the output of optimized code with and without debug info.

The debug value instructions are now ignored when determining whether LEAs are redundant. The debug values for the redundant LEAs are marked as undefined.

The intention is for a follow up patch which will attempt to preserve the debug values where possible.

[dblaikie]

Looks like this change does two things - fixes the "debug info affects optimization" and also does some work to improve optimized debug info quality? Might be worth separating this into two changes to make sure there's good test coverage/easier to review/etc?

lib/Target/X86/X86OptimizeLEAs.cpp

599

LLVM doesn't have much top level const like this - I'd probably leave it off.

[andrewng]

In D30835#697933, @dblaikie wrote:

Looks like this change does two things - fixes the "debug info affects optimization" and also does some work to improve optimized debug info quality? Might be worth separating this into two changes to make sure there's good test coverage/easier to review/etc?

I'm about to leave work now but I will look on Monday into whether separating this into two makes sense.

lib/Target/X86/X86OptimizeLEAs.cpp

599

No problem, I will remove the const.

[andrewng]

In D30835#697996, @andrewng wrote:

In D30835#697933, @dblaikie wrote:

Looks like this change does two things - fixes the "debug info affects optimization" and also does some work to improve optimized debug info quality? Might be worth separating this into two changes to make sure there's good test coverage/easier to review/etc?

I'm about to leave work now but I will look on Monday into whether separating this into two makes sense.

On further consideration, I think it makes sense to keep the patch as is because otherwise the first patch would be "lossy", i.e. the output would lose debug information. So in fixing the optimisation, ideally the debug information should be correct and preserved. However, if there are concerns with the "patching" of the debug information, then it might make sense to split the patch. What are your thoughts?

[andrewng]

In D30835#699193, @andrewng wrote:

In D30835#697996, @andrewng wrote:

In D30835#697933, @dblaikie wrote:

Looks like this change does two things - fixes the "debug info affects optimization" and also does some work to improve optimized debug info quality? Might be worth separating this into two changes to make sure there's good test coverage/easier to review/etc?

I'm about to leave work now but I will look on Monday into whether separating this into two makes sense.

On further consideration, I think it makes sense to keep the patch as is because otherwise the first patch would be "lossy", i.e. the output would lose debug information. So in fixing the optimisation, ideally the debug information should be correct and preserved. However, if there are concerns with the "patching" of the debug information, then it might make sense to split the patch. What are your thoughts?

I have looked in more detail into the DWARF debug generated by this patch (a side-effect of looking at another debug related codegen issue) and it turns out that the DWARF expression created isn't valid. I have a potential solution in progress, but it looks though generating "correct" DWARF for this particular scenario isn't as straightforward as it first appeared!

So as originally suggested, I will split this patch into one that fixes the codegen but removes the debug values and then see if I can create a reasonable patch to preserve the debug values.

[andrewng]

I have now split this patch and updated this review to contain the first part which fixes the codegen issue but doesn't preserve the debug values. I will work on a separate patch which will attempt to preserve the debug values.

[dblaikie]

lib/Target/X86/X86OptimizeLEAs.cpp

602–603

I think you can use:

for (MachineOperand &MO : MRI->use_nodbg_operands(LastVReg))

here, probably?

[andrewng]

Thanks for the review.

lib/Target/X86/X86OptimizeLEAs.cpp

602–603

Yes, at first I thought so too, but inside the loop there is:

MO.setReg(First.getOperand(0).getReg());

which could affect the use iterator. So the original code which increments the use iterator before any changes is safer.

[andreadb]

I am going to commit this on Andrew's behalf.

lib/Target/X86/X86OptimizeLEAs.cpp

 #include "X86Subtarget.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/LiveVariables.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "x86-optimize-LEAs"

 // 3) All uses of the Last LEA def register are replaceable, thus the
 //    register is used only as address base.
 bool OptimizeLEAPass::isReplaceable(const MachineInstr &First,
                                     const MachineInstr &Last,
                                     int64_t &AddrDispShift) const {
   assert(isLEA(First) && isLEA(Last) &&
          "The function works only with LEA instructions");
 
-  // Get new address displacement.
-  AddrDispShift = getAddrDispShift(Last, 1, First, 1);
-
   // Make sure that LEA def registers belong to the same class. There may be
   // instructions (like MOV8mr_NOREX) which allow a limited set of registers to
   // be used as their operands, so we must be sure that replacing one LEA
   // with another won't lead to putting a wrong register in the instruction.
   if (MRI->getRegClass(First.getOperand(0).getReg()) !=
       MRI->getRegClass(Last.getOperand(0).getReg()))
     return false;
 
+  // Get new address displacement.
+  AddrDispShift = getAddrDispShift(Last, 1, First, 1);
+
   // Loop over all uses of the Last LEA to check that its def register is
   // used only as address base for memory accesses. If so, it can be
   // replaced, otherwise - no.
-  for (auto &MO : MRI->use_operands(Last.getOperand(0).getReg())) {
+  for (auto &MO : MRI->use_nodbg_operands(Last.getOperand(0).getReg())) {
     MachineInstr &MI = *MO.getParent();
 
     // Get the number of the first memory operand.
     const MCInstrDesc &Desc = MI.getDesc();
     int MemOpNo = X86II::getMemoryOperandNo(Desc.TSFlags);
 
     // If the use instruction has no memory operand - the LEA is not
     // replaceable.
for (auto I = MBB->begin(), E = MBB->end(); I != E;) {
     DEBUG(dbgs() << "OptimizeLEAs: Replaced by: "; MI.dump(););
 
     Changed = true;
   }
 
   return Changed;
 }
 
+// Replace debug value MI with a new debug value instruction using register VReg
+// and a new DIExpression based on the old DIExpression with the prepended
+// address displacement.
+static MachineInstr *replaceDebugValue(MachineInstr &MI, unsigned VReg,
+                                       int64_t AddrDispShift,
+                                       const X86InstrInfo *TII) {
+  // Get existing DIExpression elements and prepend address displacement.
+  const DIExpression *Expr = MI.getDebugExpression();
+  ArrayRef<uint64_t> OrigElements = Expr->getElements();
+  SmallVector<uint64_t, 8> Elements(OrigElements.size() + 2);
+  if (AddrDispShift < 0) {
+    Elements[0] = dwarf::DW_OP_minus;
+    Elements[1] = -AddrDispShift;
+  } else {
+    Elements[0] = dwarf::DW_OP_plus;
+    Elements[1] = AddrDispShift;
+  }
+  std::copy(OrigElements.begin(), OrigElements.end(), Elements.begin() + 2);
+
+  // Create new DIEXpression with address displacement.
+  Expr = DIExpression::get(Expr->getContext(), Elements);
+
+  // Replace DBG_VALUE instruction with modified version.
+  MachineBasicBlock *MBB = MI.getParent();
+  DebugLoc DL = MI.getDebugLoc();
+  bool IsIndirect = MI.isIndirectDebugValue();
+  uint64_t Offset = IsIndirect ? MI.getOperand(1).getImm() : 0;
+  const MDNode *Var = MI.getDebugVariable();
+  return BuildMI(*MBB, MBB->erase(&MI), DL, TII->get(TargetOpcode::DBG_VALUE),
+                 IsIndirect, VReg, Offset, Var, Expr);
+}
+
 // Try to find similar LEAs in the list and replace one with another.
 bool OptimizeLEAPass::removeRedundantLEAs(MemOpMap &LEAs) {
   bool Changed = false;
 
   // Loop over all entries in the table.
   for (auto &E : LEAs) {
     auto &List = E.second;
 
while (I1 != List.end()) {
         if (!isReplaceable(First, Last, AddrDispShift)) {
           ++I2;
           continue;
         }
 
         // Loop over all uses of the Last LEA and update their operands. Note
         // that the correctness of this has already been checked in the
         // isReplaceable function.
+        const unsigned FirstVReg = First.getOperand(0).getReg();
         for (auto UI = MRI->use_begin(Last.getOperand(0).getReg()),
                   UE = MRI->use_end();
              UI != UE;) {
           MachineOperand &MO = *UI++;
           MachineInstr &MI = *MO.getParent();
 
+          if (MI.isDebugValue()) {
+            // Replace DBG_VALUE instruction with modified version using the
+            // register from the replacing LEA and the address displacement
+            // between the LEA instructions.
+            replaceDebugValue(MI, FirstVReg, AddrDispShift, TII);
+            continue;
+          }
+
           // Get the number of the first memory operand.
           const MCInstrDesc &Desc = MI.getDesc();
           int MemOpNo =
               X86II::getMemoryOperandNo(Desc.TSFlags) +
               X86II::getOperandBias(Desc);
 
           // Update address base.
-          MO.setReg(First.getOperand(0).getReg());
+          MO.setReg(FirstVReg);
 
           // Update address disp.
           MachineOperand &Op = MI.getOperand(MemOpNo + X86::AddrDisp);
           if (Op.isImm())
             Op.setImm(Op.getImm() + AddrDispShift);
           else if (!Op.isJTI())
             Op.setOffset(Op.getOffset() + AddrDispShift);
         }
 
         // Since we can possibly extend register lifetime, clear kill flags.
-        MRI->clearKillFlags(First.getOperand(0).getReg());
+        MRI->clearKillFlags(FirstVReg);
 
         ++NumRedundantLEAs;
         DEBUG(dbgs() << "OptimizeLEAs: Remove redundant LEA: "; Last.dump(););
 
         // By this moment, all of the Last LEA's uses must be replaced. So we
         // can freely remove it.
-        assert(MRI->use_empty(Last.getOperand(0).getReg()) &&
+        assert(MRI->use_nodbg_empty(Last.getOperand(0).getReg()) &&
                "The LEA's def register must have no uses");
         Last.eraseFromParent();
 
         // Erase removed LEA from the list.
         I2 = List.erase(I2);
 
         Changed = true;
       }

test/CodeGen/X86/lea-opt-with-debug.mir

+# RUN: llc -mtriple=x86_64-unknown-unknown -start-after peephole-opt -stop-before detect-dead-lanes -o - %s | FileCheck %s
+
+# Test that the optimize LEA pass can remove a redundant LEA even when it is
+# also used by a DBG_VALUE. Check that the uses of the replaced LEA are updated
+# correctly.
+
+--- |
+  target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+
+  %struct.A = type { i32, i32, i32 }
+
+  @c = common local_unnamed_addr global %struct.A* null, align 8
+  @a = common local_unnamed_addr global i32 0, align 4
+  @d = common local_unnamed_addr global i32 0, align 4
+  @b = common local_unnamed_addr global i32 0, align 4
+
+  define i32 @fn1() local_unnamed_addr !dbg !9 {
+    %1 = load %struct.A*, %struct.A** @c, align 8, !dbg !14
+    %2 = load i32, i32* @a, align 4, !dbg !14
+    %3 = sext i32 %2 to i64, !dbg !14
+    %4 = getelementptr inbounds %struct.A, %struct.A* %1, i64 %3, !dbg !14
+    %5 = ptrtoint %struct.A* %4 to i64, !dbg !14
+    %6 = trunc i64 %5 to i32, !dbg !14
+    store i32 %6, i32* @d, align 4, !dbg !14
+    %7 = getelementptr inbounds %struct.A, %struct.A* %1, i64 %3, i32 2, !dbg !15
+    tail call void @llvm.dbg.value(metadata i32* %7, i64 0, metadata !12, metadata !16), !dbg !17
+    br label %8, !dbg !18
+
+  ; <label>:8:                                      ; preds = %8, %0
+    %9 = load i32, i32* %7, align 4, !dbg !19
+    store i32 %9, i32* @d, align 4, !dbg !19
+    br label %8, !dbg !20
+  }
+
+  ; Function Attrs: nounwind readnone
+  declare void @llvm.dbg.value(metadata, i64, metadata, metadata) #0
+
+  attributes #0 = { nounwind readnone }
+
+  !llvm.dbg.cu = !{!0}
+  !llvm.module.flags = !{!5, !6, !7}
+  !misc = !{!8}
+
+  !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, retainedTypes: !3, globals: !2)
+  !1 = !DIFile(filename: "test.c", directory: "")
+  !2 = !{}
+  !3 = !{!4}
+  !4 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed)
+  !5 = !{i32 2, !"Dwarf Version", i32 4}
+  !6 = !{i32 2, !"Debug Info Version", i32 3}
+  !7 = !{i32 1, !"PIC Level", i32 2}
+  !8 = !DIExpression(DW_OP_plus, 8)
+  !9 = distinct !DISubprogram(name: "fn1", scope: !1, file: !1, line: 7, type: !10, isLocal: false, isDefinition: true, scopeLine: 7, isOptimized: true, unit: !0, variables: !11)
+  !10 = !DISubroutineType(types: !3)
+  !11 = !{!12}
+  !12 = !DILocalVariable(name: "e", scope: !9, file: !1, line: 8, type: !13)
+  !13 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: !4, size: 64)
+  !14 = !DILocation(line: 9, scope: !9)
+  !15 = !DILocation(line: 10, scope: !9)
+  !16 = !DIExpression()
+  !17 = !DILocation(line: 8, scope: !9)
+  !18 = !DILocation(line: 11, scope: !9)
+  !19 = !DILocation(line: 13, scope: !9)
+  !20 = !DILocation(line: 14, scope: !9)
+
+...
+---
+name:            fn1
+alignment:       4
+exposesReturnsTwice: false
+legalized:       false
+regBankSelected: false
+selected:        false
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gr64 }
+  - { id: 1, class: gr64 }
+  - { id: 2, class: gr64_nosp }
+  - { id: 3, class: gr64_nosp }
+  - { id: 4, class: gr64 }
+  - { id: 5, class: gr32 }
+  - { id: 6, class: gr32 }
+frameInfo:
+  isFrameAddressTaken: false
+  isReturnAddressTaken: false
+  hasStackMap:     false
+  hasPatchPoint:   false
+  stackSize:       0
+  offsetAdjustment: 0
+  maxAlignment:    0
+  adjustsStack:    false
+  hasCalls:        false
+  maxCallFrameSize: 0
+  hasOpaqueSPAdjustment: false
+  hasVAStart:      false
+  hasMustTailInVarArgFunc: false
+body:             |
+  bb.0 (%ir-block.0):
+    successors: %bb.1(0x80000000)
+
+    ; CHECK: %3 = LEA64r %2, 2, %2, 0, _, debug-location !14
+    ; CHECK-NEXT: %4 = LEA64r %1, 4, %3, 0, _, debug-location !14
+    ; CHECK-NOT: %0 = LEA64r %1, 4, %3, 8, _, debug-location !15
+    ; CHECK: DBG_VALUE debug-use %4, debug-use _, !12, !8, debug-location !17
+
+    %1 = MOV64rm %rip, 1, _, @c, _, debug-location !14 :: (dereferenceable load 8 from @c)
+    %2 = MOVSX64rm32 %rip, 1, _, @a, _, debug-location !14 :: (dereferenceable load 4 from @a)
+    %3 = LEA64r %2, 2, %2, 0, _, debug-location !14
+    %4 = LEA64r %1, 4, %3, 0, _, debug-location !14
+    %5 = COPY %4.sub_32bit, debug-location !14
+    MOV32mr %rip, 1, _, @d, _, killed %5, debug-location !14 :: (store 4 into @d)
+    %0 = LEA64r %1, 4, %3, 8, _, debug-location !15
+    DBG_VALUE debug-use %0, debug-use _, !12, !16, debug-location !17
+
+    ; CHECK-LABEL: bb.1 (%ir-block.8):
+    ; CHECK: %6 = MOV32rm %4, 1, _, 8, _, debug-location !19 :: (load 4 from %ir.7)
+
+  bb.1 (%ir-block.8):
+    successors: %bb.1(0x80000000)
+
+    %6 = MOV32rm %0, 1, _, 0, _, debug-location !19 :: (load 4 from %ir.7)
+    MOV32mr %rip, 1, _, @d, _, killed %6, debug-location !19 :: (store 4 into @d)
+    JMP_1 %bb.1, debug-location !20
+
+...