Index: lib/CodeGen/LiveDebugValues.cpp =================================================================== --- lib/CodeGen/LiveDebugValues.cpp +++ lib/CodeGen/LiveDebugValues.cpp @@ -21,6 +21,8 @@ #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/ADT/SparseBitVector.h" +#include "llvm/ADT/UniqueVector.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineInstrBuilder.h" @@ -43,6 +45,16 @@ namespace { +// \brief If @MI is a DBG_VALUE with debug value described by a defined +// register, returns the number of this register. In the other case, returns 0. +static unsigned isDescribedByReg(const MachineInstr &MI) { + assert(MI.isDebugValue() && "expected a DBG_VALUE"); + assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); + // If location of variable is described using a register (directly or + // indirecltly), this register is always a first operand. + return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0; +} + class LiveDebugValues : public MachineFunctionPass { private: @@ -60,31 +72,93 @@ DebugVariable(const DILocalVariable *_var, const DILocation *_inlinedAt) : Var(_var), InlinedAt(_inlinedAt) {} + bool operator<(const DebugVariable &DV) const { + if (Var == DV.Var) + return InlinedAt < DV.InlinedAt; + return Var < DV.Var; + } + bool operator==(const DebugVariable &DV) const { return (Var == DV.Var) && (InlinedAt == DV.InlinedAt); } }; - /// Member variables and functions for Range Extension across basic blocks. + /// A pair of debug variable and value location. struct VarLoc { - DebugVariable Var; - const MachineInstr *MI; // MachineInstr should be a DBG_VALUE instr. + const DebugVariable Var; + const MachineInstr &MI; ///< Only used for cloning a new DBG_VALUE. + + enum { + InvalidKind = 0, + RegisterKind + } Kind; + + /// The value location. Stored separately to avoid repeatedly + /// extracting it from MI. + union { + struct { + uint32_t RegNo; + uint32_t Offset; + } RegisterLoc; + uint64_t Hash; + } Loc; + + VarLoc(const MachineInstr &MI) + : Var(MI.getDebugVariable(), MI.getDebugLoc()->getInlinedAt()), + MI(MI), Kind(InvalidKind) { + assert(MI.isDebugValue() && "not a DBG_VALUE"); + assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); + if (int RegNo = ::isDescribedByReg(MI)) { + Kind = RegisterKind; + Loc.RegisterLoc.RegNo = RegNo; + uint64_t Offset = + MI.isIndirectDebugValue() ? MI.getOperand(1).getImm() : 0; + // We don't support offsets larger than 4GiB here. They are + // slated to be replaced with DIExpressions anyway. + if (Offset >= (1ULL << 32)) + Kind = InvalidKind; + else + Loc.RegisterLoc.Offset = Offset; + } + } - VarLoc(DebugVariable _var, const MachineInstr *_mi) : Var(_var), MI(_mi) {} + /// If this variable is described by a register, return it, + /// otherwise return 0. + unsigned isDescribedByReg() const { + if (Kind == RegisterKind) + return Loc.RegisterLoc.RegNo; + return 0; + } + + void dump() const { MI.dump(); } + + bool operator==(const VarLoc &Other) const { + return Var == Other.Var && Loc.Hash == Other.Loc.Hash; + } - bool operator==(const VarLoc &V) const; + bool operator<(const VarLoc &Other) const { + if (Var == Other.Var) + return Loc.Hash < Other.Loc.Hash; + return Var < Other.Var; + } }; - typedef std::list VarLocList; - typedef SmallDenseMap VarLocInMBB; + typedef UniqueVector VarLocMap; + typedef SparseBitVector<> VarLocList; + typedef SparseBitVector<> VarLocSet; + typedef SmallDenseMap VarLocInMBB; - void transferDebugValue(MachineInstr &MI, VarLocList &OpenRanges); - void transferRegisterDef(MachineInstr &MI, VarLocList &OpenRanges); + void transferDebugValue(const MachineInstr &MI, VarLocList &OpenRanges, + VarLocMap &VarLocIDs); + void transferRegisterDef(MachineInstr &MI, VarLocList &OpenRanges, + const VarLocMap &VarLocIDs); bool transferTerminatorInst(MachineInstr &MI, VarLocList &OpenRanges, - VarLocInMBB &OutLocs); - bool transfer(MachineInstr &MI, VarLocList &OpenRanges, VarLocInMBB &OutLocs); + VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs); + bool transfer(MachineInstr &MI, VarLocList &OpenRanges, VarLocInMBB &OutLocs, + VarLocMap &VarLocIDs); - bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs); + bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs, + const VarLocMap &VarLocIDs); bool ExtendRanges(MachineFunction &MF); @@ -104,8 +178,9 @@ } /// Print to ostream with a message. - void printVarLocInMBB(const VarLocInMBB &V, const char *msg, - raw_ostream &Out) const; + void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V, + const VarLocMap &VarLocIDs, + const char *msg, raw_ostream &Out) const; /// Calculate the liveness information for the given machine function. bool runOnMachineFunction(MachineFunction &MF) override; @@ -132,121 +207,93 @@ MachineFunctionPass::getAnalysisUsage(AU); } -// \brief If @MI is a DBG_VALUE with debug value described by a defined -// register, returns the number of this register. In the other case, returns 0. -static unsigned isDescribedByReg(const MachineInstr &MI) { - assert(MI.isDebugValue()); - assert(MI.getNumOperands() == 4); - // If location of variable is described using a register (directly or - // indirecltly), this register is always a first operand. - return MI.getOperand(0).isReg() ? MI.getOperand(0).getReg() : 0; -} - -// \brief This function takes two DBG_VALUE instructions and returns true -// if their offsets are equal; otherwise returns false. -static bool areOffsetsEqual(const MachineInstr &MI1, const MachineInstr &MI2) { - assert(MI1.isDebugValue()); - assert(MI1.getNumOperands() == 4); - - assert(MI2.isDebugValue()); - assert(MI2.getNumOperands() == 4); - - if (!MI1.isIndirectDebugValue() && !MI2.isIndirectDebugValue()) - return true; - - // Check if both MIs are indirect and they are equal. - if (MI1.isIndirectDebugValue() && MI2.isIndirectDebugValue()) - return MI1.getOperand(1).getImm() == MI2.getOperand(1).getImm(); - - return false; -} - //===----------------------------------------------------------------------===// // Debug Range Extension Implementation //===----------------------------------------------------------------------===// -void LiveDebugValues::printVarLocInMBB(const VarLocInMBB &V, const char *msg, +void LiveDebugValues::printVarLocInMBB(const MachineFunction &MF, + const VarLocInMBB &V, + const VarLocMap &VarLocIDs, + const char *msg, raw_ostream &Out) const { - Out << "Printing " << msg << ":\n"; - for (const auto &L : V) { - Out << "MBB: " << L.first->getName() << ":\n"; - for (const auto &VLL : L.second) { - Out << " Var: " << VLL.Var.Var->getName(); + for (const MachineBasicBlock &BB : MF) { + const auto &L = V.lookup(&BB); + Out << "MBB: " << BB.getName() << ":\n"; + for (unsigned VLL : L) { + const VarLoc &VL = VarLocIDs[VLL]; + Out << " Var: " << VL.Var.Var->getName(); Out << " MI: "; - (*VLL.MI).dump(); + VL.dump(); Out << "\n"; } } Out << "\n"; } -bool LiveDebugValues::VarLoc::operator==(const VarLoc &V) const { - return (Var == V.Var) && (isDescribedByReg(*MI) == isDescribedByReg(*V.MI)) && - (areOffsetsEqual(*MI, *V.MI)); -} - /// End all previous ranges related to @MI and start a new range from @MI /// if it is a DBG_VALUE instr. -void LiveDebugValues::transferDebugValue(MachineInstr &MI, - VarLocList &OpenRanges) { +void LiveDebugValues::transferDebugValue(const MachineInstr &MI, + VarLocList &OpenRanges, + VarLocMap &VarLocIDs) { if (!MI.isDebugValue()) return; - const DILocalVariable *RawVar = MI.getDebugVariable(); - assert(RawVar->isValidLocationForIntrinsic(MI.getDebugLoc()) && + const DILocalVariable *Var = MI.getDebugVariable(); + const DILocation *DebugLoc = MI.getDebugLoc(); + const DILocation *InlinedAt = DebugLoc->getInlinedAt(); + assert(Var->isValidLocationForIntrinsic(DebugLoc) && "Expected inlined-at fields to agree"); - DebugVariable Var(RawVar, MI.getDebugLoc()->getInlinedAt()); // End all previous ranges of Var. - OpenRanges.erase( - std::remove_if(OpenRanges.begin(), OpenRanges.end(), - [&](const VarLoc &V) { return (Var == V.Var); }), - OpenRanges.end()); + SparseBitVector<> KillSet; + for (unsigned ID : OpenRanges) { + auto &ORVar = VarLocIDs[ID].Var; + if (ORVar.Var == Var && ORVar.InlinedAt == InlinedAt) + KillSet.set(ID); + } + OpenRanges.intersectWithComplement(KillSet); - // Add Var to OpenRanges from this DBG_VALUE. + // Add the VarLoc to OpenRanges from this DBG_VALUE. // TODO: Currently handles DBG_VALUE which has only reg as location. - if (isDescribedByReg(MI)) { - VarLoc V(Var, &MI); - OpenRanges.push_back(std::move(V)); - } + if (isDescribedByReg(MI)) + OpenRanges.set(VarLocIDs.insert(MI)); } /// A definition of a register may mark the end of a range. void LiveDebugValues::transferRegisterDef(MachineInstr &MI, - VarLocList &OpenRanges) { + VarLocList &OpenRanges, + const VarLocMap &VarLocIDs) { MachineFunction *MF = MI.getParent()->getParent(); const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); unsigned SP = TLI->getStackPointerRegisterToSaveRestore(); + SparseBitVector<> KillSet; for (const MachineOperand &MO : MI.operands()) { if (MO.isReg() && MO.isDef() && MO.getReg() && TRI->isPhysicalRegister(MO.getReg())) { // Remove ranges of all aliased registers. for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) - OpenRanges.erase(std::remove_if(OpenRanges.begin(), OpenRanges.end(), - [&](const VarLoc &V) { - return (*RAI == - isDescribedByReg(*V.MI)); - }), - OpenRanges.end()); + for (unsigned ID : OpenRanges) + if (VarLocIDs[ID].isDescribedByReg() == *RAI) + KillSet.set(ID); } else if (MO.isRegMask()) { // Remove ranges of all clobbered registers. Register masks don't usually // list SP as preserved. While the debug info may be off for an // instruction or two around callee-cleanup calls, transferring the // DEBUG_VALUE across the call is still a better user experience. - OpenRanges.erase(std::remove_if(OpenRanges.begin(), OpenRanges.end(), - [&](const VarLoc &V) { - unsigned Reg = isDescribedByReg(*V.MI); - return Reg && Reg != SP && - MO.clobbersPhysReg(Reg); - }), - OpenRanges.end()); + for (unsigned ID : OpenRanges) { + unsigned Reg = VarLocIDs[ID].isDescribedByReg(); + if (Reg && Reg != SP && MO.clobbersPhysReg(Reg)) + KillSet.set(ID); + } } } + OpenRanges.intersectWithComplement(KillSet); } /// Terminate all open ranges at the end of the current basic block. bool LiveDebugValues::transferTerminatorInst(MachineInstr &MI, VarLocList &OpenRanges, - VarLocInMBB &OutLocs) { + VarLocInMBB &OutLocs, + const VarLocMap &VarLocIDs) { bool Changed = false; const MachineBasicBlock *CurMBB = MI.getParent(); if (!(MI.isTerminator() || (&MI == &CurMBB->instr_back()))) @@ -255,29 +302,23 @@ if (OpenRanges.empty()) return false; - VarLocList &VLL = OutLocs[CurMBB]; - - for (auto OR : OpenRanges) { - // Copy OpenRanges to OutLocs, if not already present. - assert(OR.MI->isDebugValue()); - DEBUG(dbgs() << "Add to OutLocs: "; OR.MI->dump();); - if (std::find_if(VLL.begin(), VLL.end(), - [&](const VarLoc &V) { return (OR == V); }) == VLL.end()) { - VLL.push_back(std::move(OR)); - Changed = true; - } - } + DEBUG(for (unsigned ID : OpenRanges) { + // Copy OpenRanges to OutLocs, if not already present. + dbgs() << "Add to OutLocs: "; VarLocIDs[ID].dump(); + }); + VarLocSet &VLS = OutLocs[CurMBB]; + Changed = VLS |= OpenRanges; OpenRanges.clear(); return Changed; } /// This routine creates OpenRanges and OutLocs. bool LiveDebugValues::transfer(MachineInstr &MI, VarLocList &OpenRanges, - VarLocInMBB &OutLocs) { + VarLocInMBB &OutLocs, VarLocMap &VarLocIDs) { bool Changed = false; - transferDebugValue(MI, OpenRanges); - transferRegisterDef(MI, OpenRanges); - Changed = transferTerminatorInst(MI, OpenRanges, OutLocs); + transferDebugValue(MI, OpenRanges, VarLocIDs); + transferRegisterDef(MI, OpenRanges, VarLocIDs); + Changed = transferTerminatorInst(MI, OpenRanges, OutLocs, VarLocIDs); return Changed; } @@ -285,14 +326,14 @@ /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same /// source variable in all the predecessors of @MBB reside in the same location. bool LiveDebugValues::join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, - VarLocInMBB &InLocs) { + VarLocInMBB &InLocs, const VarLocMap &VarLocIDs) { DEBUG(dbgs() << "join MBB: " << MBB.getName() << "\n"); bool Changed = false; - VarLocList InLocsT; // Temporary incoming locations. + VarLocSet InLocsT; // Temporary incoming locations. - // For all predecessors of this MBB, find the set of VarLocs that can be - // joined. + // For all predecessors of this MBB, find the set of VarLocs that + // can be joined. for (auto p : MBB.predecessors()) { auto OL = OutLocs.find(p); // Join is null in case of empty OutLocs from any of the pred. @@ -304,44 +345,34 @@ InLocsT = OL->second; continue; } - // Join with this predecessor. - VarLocList &VLL = OL->second; - InLocsT.erase( - std::remove_if(InLocsT.begin(), InLocsT.end(), [&](VarLoc &ILT) { - return (std::find_if(VLL.begin(), VLL.end(), [&](const VarLoc &V) { - return (ILT == V); - }) == VLL.end()); - }), InLocsT.end()); + InLocsT &= OL->second; } if (InLocsT.empty()) return false; - VarLocList &ILL = InLocs[&MBB]; - + VarLocSet &ILS = InLocs[&MBB]; + // Insert DBG_VALUE instructions, if not already inserted. - for (auto ILT : InLocsT) { - if (std::find_if(ILL.begin(), ILL.end(), [&](const VarLoc &I) { - return (ILT == I); - }) == ILL.end()) { - // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a - // new range is started for the var from the mbb's beginning by inserting - // a new DBG_VALUE. transfer() will end this range however appropriate. - const MachineInstr *DMI = ILT.MI; - MachineInstr *MI = - BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(), - DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(), 0, - DMI->getDebugVariable(), DMI->getDebugExpression()); - if (DMI->isIndirectDebugValue()) - MI->getOperand(1).setImm(DMI->getOperand(1).getImm()); - DEBUG(dbgs() << "Inserted: "; MI->dump();); - ++NumInserted; - Changed = true; - - VarLoc V(ILT.Var, MI); - ILL.push_back(std::move(V)); - } + VarLocSet Diff = InLocsT; + Diff.intersectWithComplement(ILS); + for (auto ID : Diff) { + // This VarLoc is not found in InLocs i.e. it is not yet inserted. So, a + // new range is started for the var from the mbb's beginning by inserting + // a new DBG_VALUE. transfer() will end this range however appropriate. + const VarLoc &DiffIt = VarLocIDs[ID]; + const MachineInstr *DMI = &DiffIt.MI; + MachineInstr *MI = + BuildMI(MBB, MBB.instr_begin(), DMI->getDebugLoc(), DMI->getDesc(), + DMI->isIndirectDebugValue(), DMI->getOperand(0).getReg(), 0, + DMI->getDebugVariable(), DMI->getDebugExpression()); + if (DMI->isIndirectDebugValue()) + MI->getOperand(1).setImm(DMI->getOperand(1).getImm()); + DEBUG(dbgs() << "Inserted: "; MI->dump();); + ILS.set(ID); + ++NumInserted; + Changed = true; } return Changed; } @@ -356,6 +387,7 @@ bool OLChanged = false; bool MBBJoined = false; + VarLocMap VarLocIDs; // Map VarLoc<>unique ID for use in bitvectors. VarLocList OpenRanges; // Ranges that are open until end of bb. VarLocInMBB OutLocs; // Ranges that exist beyond bb. VarLocInMBB InLocs; // Ranges that are incoming after joining. @@ -366,11 +398,14 @@ std::greater> Worklist; std::priority_queue, std::greater> Pending; + // Initialize every mbb with OutLocs. for (auto &MBB : MF) for (auto &MI : MBB) - transfer(MI, OpenRanges, OutLocs); - DEBUG(printVarLocInMBB(OutLocs, "OutLocs after initialization", dbgs())); + transfer(MI, OpenRanges, OutLocs, VarLocIDs); + + DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "OutLocs after initialization", + dbgs())); ReversePostOrderTraversal RPOT(&MF); unsigned int RPONumber = 0; @@ -380,7 +415,6 @@ Worklist.push(RPONumber); ++RPONumber; } - // This is a standard "union of predecessor outs" dataflow problem. // To solve it, we perform join() and transfer() using the two worklist method // until the ranges converge. @@ -393,15 +427,18 @@ while (!Worklist.empty()) { MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; Worklist.pop(); - MBBJoined = join(*MBB, OutLocs, InLocs); + MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs); if (MBBJoined) { MBBJoined = false; Changed = true; for (auto &MI : *MBB) - OLChanged |= transfer(MI, OpenRanges, OutLocs); - DEBUG(printVarLocInMBB(OutLocs, "OutLocs after propagating", dbgs())); - DEBUG(printVarLocInMBB(InLocs, "InLocs after propagating", dbgs())); + OLChanged |= transfer(MI, OpenRanges, OutLocs, VarLocIDs); + + DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, + "OutLocs after propagating", dbgs())); + DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, + "InLocs after propagating", dbgs())); if (OLChanged) { OLChanged = false; @@ -419,8 +456,8 @@ assert(Pending.empty() && "Pending should be empty"); } - DEBUG(printVarLocInMBB(OutLocs, "Final OutLocs", dbgs())); - DEBUG(printVarLocInMBB(InLocs, "Final InLocs", dbgs())); + DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs())); + DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs())); return Changed; } Index: test/DebugInfo/COFF/register-variables.ll =================================================================== --- test/DebugInfo/COFF/register-variables.ll +++ test/DebugInfo/COFF/register-variables.ll @@ -38,10 +38,10 @@ ; ASM: testl %esi, %esi ; ASM: je .LBB0_2 ; ASM: # BB#1: # %if.then -; ASM: #DEBUG_VALUE: c <- %EAX -; ASM: #DEBUG_VALUE: inlineinc:a <- %EAX -; ASM: #DEBUG_VALUE: a <- %EAX -; ASM: #DEBUG_VALUE: f:p <- %ESI +; ASM-DAG: #DEBUG_VALUE: c <- %EAX +; ASM-DAG: #DEBUG_VALUE: inlineinc:a <- %EAX +; ASM-DAG: #DEBUG_VALUE: a <- %EAX +; ASM-DAG: #DEBUG_VALUE: f:p <- %ESI ; ASM: incl %eax ; ASM: [[after_inc_eax:\.Ltmp.*]]: ; ASM: #DEBUG_VALUE: inlineinc:b <- %EAX Index: test/DebugInfo/MIR/X86/live-debug-values-3preds.mir =================================================================== --- test/DebugInfo/MIR/X86/live-debug-values-3preds.mir +++ test/DebugInfo/MIR/X86/live-debug-values-3preds.mir @@ -27,10 +27,10 @@ # DBG_VALUE for variables "x", "y" and "z" are extended into BB#9 from its # predecessors BB#0, BB#2 and BB#8. # CHECK: bb.9.for.end: -# CHECK: DBG_VALUE debug-use %edx, debug-use _, !13, !16, debug-location !20 -# CHECK-NEXT: DBG_VALUE debug-use %esi, debug-use _, !12, !16, debug-location !18 -# CHECK-NEXT: DBG_VALUE debug-use %edi, debug-use _, !11, !16, debug-location !17 - +# CHECK-DAG: DBG_VALUE debug-use %edi, debug-use _, !11, !16, debug-location !17 +# CHECK-DAG: DBG_VALUE debug-use %edx, debug-use _, !13, !16, debug-location !20 +# CHECK-DAG: DBG_VALUE debug-use %esi, debug-use _, !12, !16, debug-location !18 +# CHECK: RET --- | ; ModuleID = 'live-debug-values-3preds.ll'