Index: lib/CodeGen/MachineSink.cpp =================================================================== --- lib/CodeGen/MachineSink.cpp +++ lib/CodeGen/MachineSink.cpp @@ -16,6 +16,7 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/SetVector.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/SparseBitVector.h" @@ -108,6 +109,11 @@ // Remember debug uses of vregs seen, so we know what to sink out of blocks. DenseMap> SeenDbgUsers; + // Iterator identifying the last "significant" DBG_VALUE in the block (i.e. + // non-undef DBG_VALUE). Used to determine whether sinking DBG_VALUEs will + // change the order that assignments appear. + MachineBasicBlock::iterator LastDbgInst; + public: static char ID; // Pass identification @@ -360,6 +366,7 @@ if (!DT->isReachableFromEntry(&MBB)) return false; bool MadeChange = false; + LastDbgInst = MBB.end(); // Cache all successors, sorted by frequency info and loop depth. AllSuccsCache AllSuccessors; @@ -759,13 +766,122 @@ MBP.LHS.getReg() == BaseOp->getReg(); } +/// Separate DBG_VALUE instructions into those that would cause reordering of +/// assignments when sunk, and those that would not. Uses (and updates) the last +/// non-undef DBG_VALUE in the block to determine whether sinking DBG_VALUEs +/// sink past it (thus reordering). +static void +filterReorderingDbgValues(MachineBasicBlock::iterator &LastDbgInst, + MachineBasicBlock &MBB, + SmallVectorImpl &ToSink, + SmallVectorImpl &ReorderingDbgVals) { + SmallPtrSet SinkingSet(ToSink.begin(), ToSink.end()); + SmallVector NoReordering; + + // Walk the LastDbgInst iterator backwards: members of SinkingSet can be + // ignored, but if any another DBG_VALUE is seen then the members of + // SinkingSet will re-order when sunk past it. + // Keep track of which DBG_VALUEs are definitely safe-to-sink in NoReordering + // so that we can cope with partial cases where some DBG_VALUEs are safe to + // sink, and some are not. + for (; LastDbgInst != MBB.begin() && NoReordering.size() != ToSink.size(); + --LastDbgInst) { + if (LastDbgInst == MBB.end() || !LastDbgInst->isDebugValue()) + continue; + + // Ignore undef DBG_VALUEs. They do not present program state, and so can't + // mislead the developer. + const MachineOperand &LastOp = LastDbgInst->getOperand(0); + if (LastOp.isReg() && LastOp.getReg() == 0) + continue; + + if (SinkingSet.count(&*LastDbgInst)) { + // The last DBG_VALUE in the block is to be sunk: there are no others + // that it can sink past. Mark it as safe. + NoReordering.push_back(&*LastDbgInst); + SinkingSet.erase(&*LastDbgInst); + continue; + } else { + // We've found a meaningful DBG_VALUE that the contents of SinkingSet will + // be sunk past, causing assignment reordering. Report those as DBG_VALUEs + // that will re-order assignments. + for (auto *DbgVal : SinkingSet) + ReorderingDbgVals.push_back(DbgVal); + + // Sinking DBG_VALUEs that we've previously determined to not re-order can + // safely be sunk with no further consideration. + ToSink = NoReordering; + return; + } + } + + // The loop terminates when we hit the start of the block (no re-ordering) + // or all the DBG_VALUEs were determined to be safe for re-ordering. No need + // to separate which DBG_VALUEs to sink. + + // If we determined that no re-ordering occurs, step past the last seen + // DBG_VALUE. + if (NoReordering.size() == ToSink.size() && LastDbgInst != MBB.begin()) + --LastDbgInst; + + return; +} + +static void copyPropDbgValues(MachineInstr &MI, + SmallVectorImpl &DbgVals) +{ + SmallVector NoCopyProp; + const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo(); + const TargetInstrInfo &TII = *MI.getMF()->getSubtarget().getInstrInfo(); + + const MachineOperand *SrcMO = nullptr, *DstMO = nullptr; + if (!TII.isCopyInstr(MI, SrcMO, DstMO)) + return; + + // Check validity of forwarding this copy. + bool PostRA = MRI.getNumVirtRegs() == 0; + + for (auto *DbgMI : DbgVals) { + MachineOperand DbgMO = DbgMI->getOperand(0); + + bool DoCopy = false; + + // Pre-regalloc, only forward if all operands are virtual and their + // subregisters agree (or there are no subregs at all). More analysis + // might recover some forwardable copies. + if (TargetRegisterInfo::isVirtualRegister(DbgMO.getReg()) && + TargetRegisterInfo::isVirtualRegister(SrcMO->getReg()) && + DbgMO.getSubReg() == SrcMO->getSubReg() == DstMO->getSubReg() && + !PostRA) + DoCopy = true; + // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register + // of this copy. Only forward the copy if the DBG_VALUE operand exactly + // matches the copy destination. + else if (!TargetRegisterInfo::isVirtualRegister(DbgMO.getReg()) && + !TargetRegisterInfo::isVirtualRegister(SrcMO->getReg()) && + DbgMO.getReg() == DstMO->getReg() && PostRA) + DoCopy = true; + + if (DoCopy) { + DbgMI->getOperand(0).setReg(SrcMO->getReg()); + DbgMI->getOperand(0).setSubReg(SrcMO->getSubReg()); + } else { + NoCopyProp.push_back(DbgMI); + } + } + + // We might have successfully copy-prop'd several DBG_VALUEs, if there are + // any remaining then leave them to the caller to sink. + DbgVals.clear(); + DbgVals = NoCopyProp; + return; +} + /// Sink an instruction and its associated debug instructions. static void performSink(MachineInstr &MI, MachineBasicBlock &SuccToSinkTo, MachineBasicBlock::iterator InsertPos, - SmallVectorImpl &DbgValuesToSink) { - const MachineRegisterInfo &MRI = MI.getMF()->getRegInfo(); - const TargetInstrInfo &TII = *MI.getMF()->getSubtarget().getInstrInfo(); - + SmallVectorImpl &DbgValuesToSink, + MachineBasicBlock::iterator &LastDbgInst) { // If we cannot find a location to use (merge with), then we erase the debug // location to prevent debug-info driven tools from potentially reporting // wrong location information. @@ -775,58 +891,49 @@ else MI.setDebugLoc(DebugLoc()); + // Separate DBG_VALUEs that can sink without re-ordering variable values + // from those that cannot. + SmallVector ReorderingDbgVals; + filterReorderingDbgValues(LastDbgInst, *MI.getParent(), DbgValuesToSink, + ReorderingDbgVals); + // Move the instruction. MachineBasicBlock *ParentBlock = MI.getParent(); SuccToSinkTo.splice(InsertPos, ParentBlock, MI, ++MachineBasicBlock::iterator(MI)); + SmallPtrSet + OtherSuccs(ParentBlock->succ_begin(), ParentBlock->succ_end()); + OtherSuccs.erase(&SuccToSinkTo); + + // Sink DBG_VALUEs that won't re-order assignments. Enter undef DBG_VALUEs in + // all other successor blocks: we can't know the variables location in other + // successors unless a new DBG_VALUE specifies it. + for (auto DBI = DbgValuesToSink.begin(), DBE = DbgValuesToSink.end(); + DBI != DBE;) { + for (auto *MBB : OtherSuccs) { + auto MIt = MBB->getFirstNonPHI(); + MachineInstr *NewDbgMI = (*DBI)->getMF()->CloneMachineInstr(*DBI); + MBB->insert(MIt, NewDbgMI); + NewDbgMI->getOperand(0).setReg(0); + } + + SmallVectorImpl::iterator ToSink = DBI++; + SuccToSinkTo.insert(InsertPos, (*ToSink)->removeFromParent()); + } + // Sink a copy of debug users to the insert position. Mark the original // DBG_VALUE location as 'undef', indicating that any earlier variable // location should be terminated as we've optimised away the value at this // point. - // If the sunk instruction is a copy, try to forward the copy instead of - // leaving an 'undef' DBG_VALUE in the original location. Don't do this if - // there's any subregister weirdness involved. - for (SmallVectorImpl::iterator DBI = DbgValuesToSink.begin(), - DBE = DbgValuesToSink.end(); + for (SmallVectorImpl::iterator + DBI = ReorderingDbgVals.begin(), + DBE = ReorderingDbgVals.end(); DBI != DBE; ++DBI) { MachineInstr *DbgMI = *DBI; MachineInstr *NewDbgMI = DbgMI->getMF()->CloneMachineInstr(*DBI); SuccToSinkTo.insert(InsertPos, NewDbgMI); - - // Copy DBG_VALUE operand and set the original to undef. We then check to - // see whether this is something that can be const-propagated. - MachineOperand DbgMO = DbgMI->getOperand(0); DbgMI->getOperand(0).setReg(0); - - const MachineOperand *SrcMO = nullptr, *DstMO = nullptr; - if (TII.isCopyInstr(MI, SrcMO, DstMO)) { - bool DoCopy = false; - - // Check validity of forwarding this copy. - bool PostRA = MRI.getNumVirtRegs() == 0; - - // Pre-regalloc, only forward if all operands are virtual and their - // subregisters agree (or there are no subregs at all). More analysis - // might recover some forwardable copies. - if (TargetRegisterInfo::isVirtualRegister(DbgMO.getReg()) && - TargetRegisterInfo::isVirtualRegister(SrcMO->getReg()) && - DbgMO.getSubReg() == SrcMO->getSubReg() == DstMO->getSubReg() && - !PostRA) - DoCopy = true; - // Post-regalloc, we may be sinking a DBG_VALUE of a sub or super-register - // of this copy. Only forward the copy if the DBG_VALUE operand exactly - // matches the copy destination. - else if (!TargetRegisterInfo::isVirtualRegister(DbgMO.getReg()) && - !TargetRegisterInfo::isVirtualRegister(SrcMO->getReg()) && - DbgMO.getReg() == DstMO->getReg() && PostRA) - DoCopy = true; - - if (DoCopy) { - DbgMI->getOperand(0).setReg(SrcMO->getReg()); - DbgMI->getOperand(0).setSubReg(SrcMO->getSubReg()); - } - } } } @@ -959,10 +1066,12 @@ // After sinking, some debug users may not be dominated any more. If possible, // copy-propagate their operands. As it's expensive, don't do this if there's // no debuginfo in the program. - if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy()) + if (MI.getMF()->getFunction().getSubprogram() && MI.isCopy()) { + copyPropDbgValues(MI, DbgUsersToSink); SalvageUnsunkDebugUsersOfCopy(MI, SuccToSinkTo); + } - performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink); + performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink, LastDbgInst); // Conservatively, clear any kill flags, since it's possible that they are no // longer correct. @@ -1237,6 +1346,7 @@ ModifiedRegUnits.clear(); UsedRegUnits.clear(); SeenDbgInstrs.clear(); + MachineBasicBlock::iterator LastDbgInst = CurBB.end(); for (auto I = CurBB.rbegin(), E = CurBB.rend(); I != E;) { MachineInstr *MI = &*I; @@ -1318,11 +1428,16 @@ DbgValsToSinkSet.end()); llvm::sort(DbgValsToSink); + // Copy propagating these dbg values -- even though we only sink copies -- + // isn't guaranteed to succeed, as the copy may be for a register that + // aliases the DBG_VALUE operand, which isn't propagated. + copyPropDbgValues(*MI, DbgValsToSink); + // Clear the kill flag if SrcReg is killed between MI and the end of the // block. clearKillFlags(MI, CurBB, UsedOpsInCopy, UsedRegUnits, TRI); MachineBasicBlock::iterator InsertPos = SuccBB->getFirstNonPHI(); - performSink(*MI, *SuccBB, InsertPos, DbgValsToSink); + performSink(*MI, *SuccBB, InsertPos, DbgValsToSink, LastDbgInst); updateLiveIn(MI, SuccBB, UsedOpsInCopy, DefedRegsInCopy); Changed = true; Index: test/CodeGen/X86/postra-ignore-dbg-instrs.mir =================================================================== --- test/CodeGen/X86/postra-ignore-dbg-instrs.mir +++ test/CodeGen/X86/postra-ignore-dbg-instrs.mir @@ -62,7 +62,6 @@ # CHECK-NOT: $eax = COPY $edi # CHECK: bb.1: # CHECK: renamable $eax = COPY $edi -# CHECK-NEXT: DBG_VALUE $eax, # CHECK: bb.2: name: x1 alignment: 4 Index: test/CodeGen/X86/pr38952.mir =================================================================== --- test/CodeGen/X86/pr38952.mir +++ test/CodeGen/X86/pr38952.mir @@ -75,7 +75,7 @@ DBG_VALUE $edi, $noreg, !21, !DIExpression() renamable $ebx = COPY $edi renamable $eax = MOV32r0 implicit-def dead $eflags - DBG_VALUE $ebx, $noreg, !21, !DIExpression() + DBG_VALUE $bx, $noreg, !21, !DIExpression() CMP32ri $edi, 255, implicit-def $eflags JG_1 %bb.2, implicit killed $eflags JMP_1 %bb.1 @@ -86,7 +86,7 @@ liveins: $ebx ; CHECK: $ebx = COPY $edi - ; CHECK-NEXT: DBG_VALUE $ebx + ; CHECK-NEXT: DBG_VALUE $bx renamable $rdx = MOVSX64rr32 renamable $ebx renamable $rdx = nsw SHL64ri killed renamable $rdx, 2, implicit-def dead $eflags ADJCALLSTACKDOWN64 0, 0, 0, implicit-def dead $rsp, implicit-def dead $eflags, implicit-def dead $ssp, implicit $rsp, implicit $ssp Index: test/DebugInfo/MIR/X86/machinesink.mir =================================================================== --- test/DebugInfo/MIR/X86/machinesink.mir +++ test/DebugInfo/MIR/X86/machinesink.mir @@ -1,9 +1,8 @@ # RUN: llc -run-pass=machine-sink -o - %s | FileCheck %s # Check various things when we sink machine instructions: # a) DBG_VALUEs should sink with defs -# b) Undefs should be left behind -# c) DBG_VALUEs not immediately following the defining inst should sink too -# d) If we generate debug-use-before-defs through sinking, and can copy +# b) DBG_VALUEs not immediately following the defining inst should sink too +# c) If we generate debug-use-before-defs through sinking, and can copy # propagate to a different value, we should do that. --- | target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" @@ -72,12 +71,10 @@ successors: %bb.1.nou(0x80000000), %bb.2.exit liveins: $rdi, $esi - ; This block should have the vreg copy sunk from it, the DBG_VALUE with it, - ; and an undef DBG_VALUE left over. + ; This block should have the vreg copy sunk from it, the DBG_VALUE with it. ; CHECK-LABEL: bb.0.entry: ; CHECK: [[ARG0VREG:%[0-9]+]]:gr64 = COPY $rdi ; CHECK-NEXT: CMP32ri $esi, 0 - ; CHECK-NEXT: DBG_VALUE $noreg, $noreg, [[VARNUM]] ; CHECK-NEXT: JE_1 ; CHECK-NEXT: JMP_1 @@ -108,6 +105,6 @@ ; CHECK-NEXT: $rax = MOV64rr [[ARG0VREG]] ; CHECK-NEXT: RET 0 DBG_VALUE %5, _, !16, !17, debug-location !18 - $rax = MOV64rr %2, _, 0, _ + $rax = MOV64rr %2 RET 0 ... Index: test/DebugInfo/MIR/X86/postra-subreg-sink.mir =================================================================== --- test/DebugInfo/MIR/X86/postra-subreg-sink.mir +++ test/DebugInfo/MIR/X86/postra-subreg-sink.mir @@ -60,7 +60,7 @@ ; In the following code, the: ; DBG_VALUE of $edi should not sink: it's an argument - ; DBG_VALUE of $ebx should sink: it's a standard copy + ; DBG_VALUE of $ebx should copy-prop: it's a standard copy ; DBG_VALUE of $bx should sink: a write of its superregister sinks ; DBG_VALUE of $ecx should sink: a write of one of its subregisters sinks @@ -70,14 +70,11 @@ ; CHECK: liveins: $edi ; CHECK: DBG_VALUE $edi, $noreg, ![[BARVAR]] ; CHECK-NEXT: DBG_VALUE $edi, $noreg, ![[ARGVAR]] - ; CHECK-NEXT: DBG_VALUE $noreg, $noreg, ![[BAZVAR]] ; CHECK-NEXT: renamable $cl = MOV8ri 1 - ; CHECK-NEXT: DBG_VALUE $noreg, $noreg, ![[FOOVAR]] ; CHECK-NEXT: JMP_1 %bb.1 ; CHECK: bb.1.return: ; CHECK: liveins: $cl, $edi ; CHECK: renamable $ebx = COPY $edi - ; CHECK-NEXT: DBG_VALUE $ebx, $noreg, ![[ARGVAR]] ; CHECK-NEXT: DBG_VALUE $bx, $noreg, ![[BAZVAR]] ; CHECK-NEXT: renamable $ch = COPY renamable $cl ; CHECK-NEXT: DBG_VALUE $ecx, $noreg, ![[FOOVAR]] Index: test/DebugInfo/MIR/X86/sink-leaves-undef.mir =================================================================== --- test/DebugInfo/MIR/X86/sink-leaves-undef.mir +++ test/DebugInfo/MIR/X86/sink-leaves-undef.mir @@ -1,7 +1,8 @@ # RUN: llc %s -o - -run-pass=machine-sink -mtriple=x86_64-- | FileCheck %s # This is a copy of test/CodeGen/X86/MachineSink-DbgValue.ll, where we -# additionally test that when the MOV32rm defining %0 is sunk, it leaves -# an 'undef' DBG_VALUE behind to terminate earlier location ranges. +# test that when the MOV32rm defining %0 is sunk past a later DBG_VALUE, it +# leaves an 'undef' DBG_VALUE behind to terminate earlier location ranges, to +# avoid re-ordering of assignments. --- | target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-apple-macosx10.7.0" @@ -88,9 +89,12 @@ %3:gr32 = COPY $edi DBG_VALUE %3, $noreg, !9, !DIExpression(), debug-location !14 %0:gr32 = MOV32rm %4, 1, $noreg, 0, $noreg, debug-location !15 :: (load 4 from %ir.c, align 1) + ; The debug inst to sink: DBG_VALUE %0, $noreg, !12, !DIExpression(), debug-location !15 %5:gr32 = MOV32r0 implicit-def dead $eflags %6:gr32 = SUB32ri8 %3, 42, implicit-def $eflags, debug-location !17 + ; Earlier debug inst will re-order assignments with this debug inst. + DBG_VALUE %3, $noreg, !9, !DIExpression(), debug-location !14 JNE_1 %bb.2, implicit $eflags, debug-location !17 JMP_1 %bb.1, debug-location !17