Index: debuginfo-tests/dexter-tests/coalesce_dbg_values.cpp =================================================================== --- /dev/null +++ debuginfo-tests/dexter-tests/coalesce_dbg_values.cpp @@ -0,0 +1,14 @@ +// UNSUPPORTED: system-windows +// +// RUN: %dexter --fail-lt 1.0 -w --builder 'clang' \ +// RUN: --debugger 'lldb' --cflags '-O3 -g' -- %s +char a, b; +int main() { + --b; + unsigned var = 36901; + ++var; + if (a) // DexLabel('watch') + b = 0; +} + +// DexExpectWatchValue('var', 36902, on_line='watch') Index: llvm/lib/CodeGen/LiveDebugVariables.cpp =================================================================== --- llvm/lib/CodeGen/LiveDebugVariables.cpp +++ llvm/lib/CodeGen/LiveDebugVariables.cpp @@ -96,31 +96,41 @@ enum : unsigned { UndefLocNo = ~0U }; -/// Describes a location by number along with some flags about the original -/// usage of the location. +/// Describes a location by number, along with the DIExpression which is used to +/// derive a value from this location. Alternatively refered to as a definition +/// (def). Defs are made for fragments (parts) of a source variable. +/// +/// A def range is opened with a def and is terminated at the next def of any +/// overlapping variable fragment. An undef DbgValueLocation means that the +/// value is not available. +/// +/// The combination of an undef location and a nullptr DIExpression explicitly +/// represents an implicit definition range termination, called a 'blocker'. +/// Because of the way we group fragment defs we get the implicit termination +/// rules for free for any defs refering to the exact same fragment. The blocker +/// values are required so that we can represent these implict terminations for +/// all overlapping fragment defs. A blocker behaves like an undef except it will +/// not be emitted as a DBG_VALUE. class DbgValueLocation { public: - DbgValueLocation(unsigned LocNo) - : LocNo(LocNo) { - static_assert(sizeof(*this) == sizeof(unsigned), "bad bitfield packing"); - assert(locNo() == LocNo && "location truncation"); - } + DbgValueLocation() = default; + DbgValueLocation(unsigned LocNo, const DIExpression *Expr) + : LocNo(LocNo), Expression(Expr) {} - DbgValueLocation() : LocNo(0) {} + /// Will return nullptr if this is a dummy value. + const DIExpression *getExpression() const { return Expression; } - unsigned locNo() const { - // Fix up the undef location number, which gets truncated. - return LocNo == INT_MAX ? UndefLocNo : LocNo; - } - bool isUndef() const { return locNo() == UndefLocNo; } + unsigned getLocNo() const { return LocNo; } + + bool isUndef() const { return getLocNo() == UndefLocNo; } DbgValueLocation changeLocNo(unsigned NewLocNo) const { - return DbgValueLocation(NewLocNo); + return DbgValueLocation(NewLocNo, Expression); } friend inline bool operator==(const DbgValueLocation &LHS, const DbgValueLocation &RHS) { - return LHS.LocNo == RHS.LocNo; + return LHS.LocNo == RHS.LocNo && LHS.Expression == RHS.Expression; } friend inline bool operator!=(const DbgValueLocation &LHS, @@ -129,7 +139,8 @@ } private: - unsigned LocNo; + unsigned LocNo = 0; + const DIExpression *Expression = nullptr; }; /// Map of where a user value is live, and its location. @@ -140,34 +151,37 @@ using SpillOffsetMap = DenseMap; namespace { +/// Return a MO which represents a DBG_VALUE undef. +static MachineOperand getUndefMO() { + MachineOperand MO = MachineOperand::CreateReg(0U, false); + MO.setIsDebug(); + return MO; +} class LDVImpl; +class SourceVariable; -/// A user value is a part of a debug info user variable. +/// Tracks definitions of a variable fragment over ranges of instructions. +/// Fragment does not define which variable it refers to because any which +/// refer to the same are stored together in a SourceVariable instance which +/// does define this identity. /// /// A DBG_VALUE instruction notes that (a sub-register of) a virtual register -/// holds part of a user variable. The part is identified by a byte offset. -/// -/// UserValues are grouped into equivalence classes for easier searching. Two -/// user values are related if they refer to the same variable, or if they are -/// held by the same virtual register. The equivalence class is the transitive -/// closure of that relation. -class UserValue { - const DILocalVariable *Variable; ///< The debug info variable we are part of. - const DIExpression *Expression; ///< Any complex address expression. - DebugLoc dl; ///< The debug location for the variable. This is - ///< used by dwarf writer to find lexical scope. - UserValue *leader; ///< Equivalence class leader. - UserValue *next = nullptr; ///< Next value in equivalence class, or null. +/// holds part of a source variable. We emit a DBG_VALUE for each fragment with +/// value definitions for each source variable. +class Fragment { + /// Fragment of source variable covered. + DIExpression::FragmentInfo FragmentInfo; /// Numbered locations referenced by locmap. SmallVector locations; - /// Map of slot indices where this value is live. + /// Map of slot indices where these values are live. LocMap locInts; /// Insert a DBG_VALUE into MBB at Idx for LocNo. - void insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx, + void insertDebugValue(const DIVariable *Variable, const DebugLoc &DebugLoc, + MachineBasicBlock *MBB, SlotIndex StartIdx, SlotIndex StopIdx, DbgValueLocation Loc, bool Spilled, unsigned SpillOffset, LiveIntervals &LIS, const TargetInstrInfo &TII, @@ -178,52 +192,6 @@ bool splitLocation(unsigned OldLocNo, ArrayRef NewRegs, LiveIntervals &LIS); -public: - /// Create a new UserValue. - UserValue(const DILocalVariable *var, const DIExpression *expr, DebugLoc L, - LocMap::Allocator &alloc) - : Variable(var), Expression(expr), dl(std::move(L)), leader(this), - locInts(alloc) {} - - /// Get the leader of this value's equivalence class. - UserValue *getLeader() { - UserValue *l = leader; - while (l != l->leader) - l = l->leader; - return leader = l; - } - - /// Return the next UserValue in the equivalence class. - UserValue *getNext() const { return next; } - - /// Does this UserValue match the parameters? - bool match(const DILocalVariable *Var, const DIExpression *Expr, - const DILocation *IA) const { - // FIXME: The fragment should be part of the equivalence class, but not - // other things in the expression like stack values. - return Var == Variable && Expr == Expression && dl->getInlinedAt() == IA; - } - - /// Merge equivalence classes. - static UserValue *merge(UserValue *L1, UserValue *L2) { - L2 = L2->getLeader(); - if (!L1) - return L2; - L1 = L1->getLeader(); - if (L1 == L2) - return L1; - // Splice L2 before L1's members. - UserValue *End = L2; - while (End->next) { - End->leader = L1; - End = End->next; - } - End->leader = L1; - End->next = L1->next; - L1->next = L2; - return L1; - } - /// Return the location number that matches Loc. /// /// For undef values we always return location number UndefLocNo without @@ -262,7 +230,7 @@ // Bail out if LocNo still is used. for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) { DbgValueLocation Loc = I.value(); - if (Loc.locNo() == LocNo) + if (Loc.getLocNo() == LocNo) return; } // Remove the entry in the locations vector, and adjust all references to @@ -270,17 +238,25 @@ locations.erase(locations.begin() + LocNo); for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) { DbgValueLocation Loc = I.value(); - if (!Loc.isUndef() && Loc.locNo() > LocNo) - I.setValueUnchecked(Loc.changeLocNo(Loc.locNo() - 1)); + if (!Loc.isUndef() && Loc.getLocNo() > LocNo) + I.setValueUnchecked(Loc.changeLocNo(Loc.getLocNo() - 1)); } } +public: + Fragment(const Fragment &) = delete; + + /// Create a new Fragment. + Fragment(DIExpression::FragmentInfo FragInfo, LocMap::Allocator &alloc) + : FragmentInfo(FragInfo), locInts(alloc) {} + /// Ensure that all virtual register locations are mapped. void mapVirtRegs(LDVImpl *LDV); - /// Add a definition point to this value. - void addDef(SlotIndex Idx, const MachineOperand &LocMO) { - DbgValueLocation Loc(getLocationNo(LocMO)); + /// Add a value definition point for this fragment. + void addDef(SlotIndex Idx, const MachineOperand &LocMO, + const DIExpression *Expr) { + DbgValueLocation Loc(getLocationNo(LocMO), Expr); // Add a singular (Idx,Idx) -> Loc mapping. LocMap::iterator I = locInts.find(Idx); if (!I.valid() || I.start() != Idx) @@ -290,6 +266,9 @@ I.setValue(Loc); } + /// Add a fake definition point which prevents adjacent locations coalescing. + void addBlocker(SlotIndex Idx) { addDef(Idx, getUndefMO(), nullptr); } + /// Extend the current definition as far as possible down. /// /// Stop when meeting an existing def or when leaving the live @@ -313,20 +292,22 @@ /// any of the copies are available at the kill points, and add defs if /// possible. /// + /// \param SrcVar Block value intervals for overlapping fragments. /// \param LI Scan for copies of the value in LI->reg. /// \param LocNo Location number of LI->reg. /// \param Kills Points where the range of LocNo could be extended. /// \param [in,out] NewDefs Append (Idx, LocNo) of inserted defs here. void addDefsFromCopies( - LiveInterval *LI, unsigned LocNo, + SourceVariable &SrcVar, LiveInterval *LI, DbgValueLocation Loc, const SmallVectorImpl &Kills, SmallVectorImpl> &NewDefs, MachineRegisterInfo &MRI, LiveIntervals &LIS); /// Compute the live intervals of all locations after collecting all their /// def points. - void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, - LiveIntervals &LIS, LexicalScopes &LS); + void computeIntervals(SourceVariable &SrcVar, MachineRegisterInfo &MRI, + const TargetRegisterInfo &TRI, LiveIntervals &LIS, + LexicalScopes &LS); /// Replace OldReg ranges with NewRegs ranges where NewRegs is /// live. Returns true if any changes were made. @@ -342,13 +323,82 @@ SpillOffsetMap &SpillOffsets); /// Recreate DBG_VALUE instruction from data structures. - void emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS, + void emitDebugValues(const DIVariable *Variable, const DebugLoc &DebugLoc, + VirtRegMap *VRM, LiveIntervals &LIS, const TargetInstrInfo &TII, const TargetRegisterInfo &TRI, const SpillOffsetMap &SpillOffsets); - /// Return DebugLoc of this UserValue. - DebugLoc getDebugLoc() { return dl;} + /// Returns true if FragInfo covers exactly the same bits as this fragment. + bool match(DIExpression::FragmentInfo FragInfo) { + return FragmentInfo == FragInfo; + } + + /// Returns true if FragInfo covers any of the same bits as this fragment. + bool overlap(DIExpression::FragmentInfo FragInfo) { + return DIExpression::fragmentsOverlap(FragmentInfo, FragInfo); + } + + void print(raw_ostream &, const TargetRegisterInfo *); + void print(raw_ostream &, const DIVariable *, const DebugLoc &, + const TargetRegisterInfo *); +}; + +/// Identifies a unique instance of a source variable and acts as a container for +/// all fragment definitions for that source variable. +/// +/// The identity is derived from the source variable itself and the inlining +/// scope. This guarantees that two inlined versions of the same variable +/// are identified uniquely. +/// +/// This class allows us to, for any def, quickly search for overlapping fragments +/// with defs and explictly terminate their ranges. +class SourceVariable { + using FragmentInfo = DIExpression::FragmentInfo; + + /// A DefaultFragment covers the whole variable. + static const FragmentInfo DefaultFragment; + + /// The debug info variable we are describing. + const DILocalVariable *Variable; + + /// The debug location for the variable. + DebugLoc DL; + + /// The fragments for this variable which have definition points. + SmallVector, 4> Fragments; + + /// Allocator required for Fragment ctor. + LocMap::Allocator &Allocator; + + /// Get FragmentInfo from Expr or return DefaultFragment if there isn't one. + static FragmentInfo getFragmentInfo(const DIExpression *Expr); + +public: + using iterator = SmallVectorImpl>::iterator; + + SourceVariable() = delete; + SourceVariable(const DILocalVariable *Var, DebugLoc L, + LocMap::Allocator &MapAllocator) + : Variable(Var), DL(std::move(L)), Allocator(MapAllocator) {} + + /// Add a value definition point for the fragment described by Expr and add a + /// blocker to overlapping fragments. + void addDef(SlotIndex Idx, const MachineOperand &LocMO, + const DIExpression *Expr); + + /// Add a blocker to overlapping fragments (excluding an exact match). + void addBlockerForOverlaps(SlotIndex Idx, const DIExpression *Expr); + + const DIVariable *getVariable() const { return Variable; } + + DebugLoc getDebugLoc() const { return DL; } + + /// Iterate over the fragments for this variable which have definition points. + iterator begin() { return Fragments.begin(); } + + /// Iterate over the fragments for this variable which have definition points. + iterator end() { return Fragments.end(); } void print(raw_ostream &, const TargetRegisterInfo *); }; @@ -398,26 +448,28 @@ /// Whether the machine function is modified during the pass. bool ModifiedMF = false; - /// All allocated UserValue instances. - SmallVector, 8> userValues; + /// All allocated SourceVariable instances. + SmallVector, 8> sourceVariables; /// All allocated UserLabel instances. SmallVector, 2> userLabels; - /// Map virtual register to eq class leader. - using VRMap = DenseMap; - VRMap virtRegToEqClass; + /// Map virtual register to Fragments with values which use it. + using VRMap = std::unordered_map>; + VRMap VirtRegToFragments; - /// Map user variable to eq class leader. - using UVMap = DenseMap; - UVMap userVarMap; + /// SourceVariables are mapped to an ID for fast searching when adding + /// initial fragment value definitions. + using SourceVariableId = std::pair; + using SVMap = DenseMap; + SVMap SourceVariableMap; - /// Find or create a UserValue. - UserValue *getUserValue(const DILocalVariable *Var, const DIExpression *Expr, - const DebugLoc &DL); + /// Find or create a SourceVariable. + SourceVariable *getSourceVariable(const DILocalVariable *Var, + const DebugLoc &DL); - /// Find the EC leader for VirtReg or null. - UserValue *lookupVirtReg(unsigned VirtReg); + /// Return the fragments with values using VirtReg, or nullptr if non exist. + SmallVectorImpl *lookupVirtReg(unsigned VirtReg); /// Add DBG_VALUE instruction to our maps. /// @@ -435,8 +487,8 @@ /// \returns True if the DBG_LABEL instruction should be deleted. bool handleDebugLabel(MachineInstr &MI, SlotIndex Idx); - /// Collect and erase all DBG_VALUE instructions, adding a UserValue def - /// for each instruction. + /// Collect and erase all DBG_VALUE instructions, adding a variable fragment + /// value def for each instruction. /// /// \param mf MachineFunction to be scanned. /// @@ -455,10 +507,10 @@ /// Release all memory. void clear() { MF = nullptr; - userValues.clear(); + sourceVariables.clear(); userLabels.clear(); - virtRegToEqClass.clear(); - userVarMap.clear(); + VirtRegToFragments.clear(); + SourceVariableMap.clear(); // Make sure we call emitDebugValues if the machine function was modified. assert((!ModifiedMF || EmitDone) && "Dbg values are not emitted in LDV"); @@ -466,8 +518,8 @@ ModifiedMF = false; } - /// Map virtual register to an equivalence class. - void mapVirtReg(unsigned VirtReg, UserValue *EC); + /// Map virtual register to a Fragment. + void mapVirtReg(unsigned VirtReg, Fragment *F); /// Replace all references to OldReg with NewRegs. void splitRegister(unsigned OldReg, ArrayRef NewRegs); @@ -527,18 +579,27 @@ } } -void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { +void Fragment::print(raw_ostream &OS, const DIVariable *V, const DebugLoc &DL, + const TargetRegisterInfo *TRI) { OS << "!\""; - printExtendedName(OS, Variable, dl); + printExtendedName(OS, V, DL); + OS << "\""; + print(OS, TRI); +} - OS << "\"\t"; +void Fragment::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { + OS << "\t"; for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) { + if (!I.value().getExpression()) { + OS << "block"; + continue; + } OS << " [" << I.start() << ';' << I.stop() << "):"; if (I.value().isUndef()) OS << "undef"; - else { - OS << I.value().locNo(); - } + else + OS << I.value().getLocNo(); + OS << *I.value().getExpression(); } for (unsigned i = 0, e = locations.size(); i != e; ++i) { OS << " Loc" << i << '='; @@ -547,6 +608,11 @@ OS << '\n'; } +void SourceVariable::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { + for (auto &F : Fragments) + F->print(OS, Variable, DL, TRI); +} + void UserLabel::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { OS << "!\""; printExtendedName(OS, Label, dl); @@ -558,48 +624,86 @@ void LDVImpl::print(raw_ostream &OS) { OS << "********** DEBUG VARIABLES **********\n"; - for (auto &userValue : userValues) - userValue->print(OS, TRI); + for (auto &SrcVar : sourceVariables) + SrcVar->print(OS, TRI); OS << "********** DEBUG LABELS **********\n"; for (auto &userLabel : userLabels) userLabel->print(OS, TRI); } #endif -void UserValue::mapVirtRegs(LDVImpl *LDV) { +void Fragment::mapVirtRegs(LDVImpl *LDV) { for (unsigned i = 0, e = locations.size(); i != e; ++i) if (locations[i].isReg() && Register::isVirtualRegister(locations[i].getReg())) LDV->mapVirtReg(locations[i].getReg(), this); } -UserValue *LDVImpl::getUserValue(const DILocalVariable *Var, - const DIExpression *Expr, const DebugLoc &DL) { - UserValue *&Leader = userVarMap[Var]; - if (Leader) { - UserValue *UV = Leader->getLeader(); - Leader = UV; - for (; UV; UV = UV->getNext()) - if (UV->match(Var, Expr, DL->getInlinedAt())) - return UV; +const DIExpression::FragmentInfo SourceVariable::DefaultFragment = { + std::numeric_limits::max(), std::numeric_limits::min()}; + +SourceVariable::FragmentInfo +SourceVariable::getFragmentInfo(const DIExpression *Expr) { + return Expr->getFragmentInfo().getValueOr(DefaultFragment); +} + +void SourceVariable::addDef(SlotIndex Idx, const MachineOperand &LocMO, + const DIExpression *Expr) { + FragmentInfo FragInfo = SourceVariable::getFragmentInfo(Expr); + // Search for exact matching Fragment. + Fragment *ExactMatch = nullptr; + for (auto &Fragment : Fragments) { + if (Fragment->match(FragInfo)) + ExactMatch = Fragment.get(); + // Add blocker def for any overlaps. + else if (Fragment->overlap(FragInfo)) + Fragment->addBlocker(Idx); } - userValues.push_back( - std::make_unique(Var, Expr, DL, allocator)); - UserValue *UV = userValues.back().get(); - Leader = UserValue::merge(Leader, UV); - return UV; + // Create a new Fragment if there wans't one for this Fragment. + if (!ExactMatch) { + Fragments.push_back(std::make_unique(FragInfo, Allocator)); + ExactMatch = Fragments.back().get(); + } + + // Add def for the fragment range. + ExactMatch->addDef(Idx, LocMO, Expr); +} + +void SourceVariable::addBlockerForOverlaps(SlotIndex Idx, + const DIExpression *Expr) { + FragmentInfo FragInfo = SourceVariable::getFragmentInfo(Expr); + for (auto &Fragment : Fragments) { + if (!Fragment->overlap(FragInfo)) + continue; + if (Fragment->match(FragInfo)) + continue; + Fragment->addBlocker(Idx); + } } -void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) { +SourceVariable *LDVImpl::getSourceVariable(const DILocalVariable *Var, + const DebugLoc &DL) { + auto Ident = std::make_pair(Var, DL->getInlinedAt()); + SourceVariable *&SVEntry = SourceVariableMap[Ident]; + + if (SVEntry) + return SVEntry; + + sourceVariables.push_back( + std::make_unique(Var, DL, allocator)); + return SVEntry = sourceVariables.back().get(); +} + +void LDVImpl::mapVirtReg(unsigned VirtReg, Fragment *F) { assert(Register::isVirtualRegister(VirtReg) && "Only map VirtRegs"); - UserValue *&Leader = virtRegToEqClass[VirtReg]; - Leader = UserValue::merge(Leader, EC); + VirtRegToFragments[VirtReg].push_back(F); } -UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) { - if (UserValue *UV = virtRegToEqClass.lookup(VirtReg)) - return UV->getLeader(); +SmallVectorImpl *LDVImpl::lookupVirtReg(unsigned VirtReg) { + VRMap::iterator Itr = VirtRegToFragments.find(VirtReg); + if (Itr != VirtRegToFragments.end()) + return &Itr->second; return nullptr; } @@ -645,20 +749,17 @@ } } - // Get or create the UserValue for (variable,offset) here. + // Get or create the Fragment for (variable,offset) here. assert(!MI.getOperand(1).isImm() && "DBG_VALUE with indirect flag before " "LiveDebugVariables"); const DILocalVariable *Var = MI.getDebugVariable(); const DIExpression *Expr = MI.getDebugExpression(); - UserValue *UV = - getUserValue(Var, Expr, MI.getDebugLoc()); + SourceVariable *SrcVar = getSourceVariable(Var, MI.getDebugLoc()); if (!Discard) - UV->addDef(Idx, MI.getOperand(0)); - else { - MachineOperand MO = MachineOperand::CreateReg(0U, false); - MO.setIsDebug(); - UV->addDef(Idx, MO); - } + SrcVar->addDef(Idx, MI.getOperand(0), Expr); + else + SrcVar->addDef(Idx, getUndefMO(), Expr); + return true; } @@ -720,9 +821,9 @@ return Changed; } -void UserValue::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR, - const VNInfo *VNI, SmallVectorImpl *Kills, - LiveIntervals &LIS) { +void Fragment::extendDef(SlotIndex Idx, DbgValueLocation Loc, LiveRange *LR, + const VNInfo *VNI, SmallVectorImpl *Kills, + LiveIntervals &LIS) { SlotIndex Start = Idx; MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start); SlotIndex Stop = LIS.getMBBEndIdx(MBB); @@ -764,8 +865,8 @@ I.insert(Start, Stop, Loc); } -void UserValue::addDefsFromCopies( - LiveInterval *LI, unsigned LocNo, +void Fragment::addDefsFromCopies( + SourceVariable &SrcVar, LiveInterval *LI, DbgValueLocation Loc, const SmallVectorImpl &Kills, SmallVectorImpl> &NewDefs, MachineRegisterInfo &MRI, LiveIntervals &LIS) { @@ -795,7 +896,7 @@ // it, or we are looking at a wrong value of LI. SlotIndex Idx = LIS.getInstructionIndex(*MI); LocMap::iterator I = locInts.find(Idx.getRegSlot(true)); - if (!I.valid() || I.value().locNo() != LocNo) + if (!I.valid() || I.value().getLocNo() != Loc.getLocNo()) continue; if (!LIS.hasInterval(DstReg)) @@ -829,17 +930,19 @@ MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def); assert(CopyMI && CopyMI->isCopy() && "Bad copy value"); unsigned LocNo = getLocationNo(CopyMI->getOperand(0)); - DbgValueLocation NewLoc(LocNo); + DbgValueLocation NewLoc = Loc.changeLocNo(LocNo); I.insert(Idx, Idx.getNextSlot(), NewLoc); NewDefs.push_back(std::make_pair(Idx, NewLoc)); + SrcVar.addBlockerForOverlaps(Idx, Loc.getExpression()); break; } } } -void UserValue::computeIntervals(MachineRegisterInfo &MRI, - const TargetRegisterInfo &TRI, - LiveIntervals &LIS, LexicalScopes &LS) { +void Fragment::computeIntervals(SourceVariable &SrcVar, + MachineRegisterInfo &MRI, + const TargetRegisterInfo &TRI, + LiveIntervals &LIS, LexicalScopes &LS) { SmallVector, 16> Defs; // Collect all defs to be extended (Skipping undefs). @@ -851,7 +954,7 @@ for (unsigned i = 0; i != Defs.size(); ++i) { SlotIndex Idx = Defs[i].first; DbgValueLocation Loc = Defs[i].second; - const MachineOperand &LocMO = locations[Loc.locNo()]; + const MachineOperand &LocMO = locations[Loc.getLocNo()]; if (!LocMO.isReg()) { extendDef(Idx, Loc, nullptr, nullptr, nullptr, LIS); @@ -877,7 +980,7 @@ // sub-register in that regclass). For now, simply skip handling copies if // a sub-register is involved. if (LI && !LocMO.getSubReg()) - addDefsFromCopies(LI, Loc.locNo(), Kills, Defs, MRI, LIS); + addDefsFromCopies(SrcVar, LI, Loc, Kills, Defs, MRI, LIS); continue; } @@ -895,7 +998,7 @@ // causing extra unnecessary DBG_VALUEs to be emitted. To prevent // this, trim the intervals to the lexical scope. - LexicalScope *Scope = LS.findLexicalScope(dl); + LexicalScope *Scope = LS.findLexicalScope(SrcVar.getDebugLoc()); if (!Scope) return; @@ -954,9 +1057,11 @@ LexicalScopes LS; LS.initialize(*MF); - for (unsigned i = 0, e = userValues.size(); i != e; ++i) { - userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, LS); - userValues[i]->mapVirtRegs(this); + for (auto &SrcVar : sourceVariables) { + for (const auto &Fragment : *SrcVar) { + Fragment->computeIntervals(*SrcVar, MF->getRegInfo(), *TRI, *LIS, LS); + Fragment->mapVirtRegs(this); + } } } @@ -1013,9 +1118,8 @@ // Live Range Splitting //===----------------------------------------------------------------------===// -bool -UserValue::splitLocation(unsigned OldLocNo, ArrayRef NewRegs, - LiveIntervals& LIS) { +bool Fragment::splitLocation(unsigned OldLocNo, ArrayRef NewRegs, + LiveIntervals &LIS) { LLVM_DEBUG({ dbgs() << "Splitting Loc" << OldLocNo << '\t'; print(dbgs(), nullptr); @@ -1044,7 +1148,8 @@ break; // Now LII->end > LocMapI.start(). Do we have an overlap? - if (LocMapI.value().locNo() == OldLocNo && LII->start < LocMapI.stop()) { + if (LocMapI.value().getLocNo() == OldLocNo && + LII->start < LocMapI.stop()) { // Overlapping correct location. Allocate NewLocNo now. if (NewLocNo == UndefLocNo) { MachineOperand MO = MachineOperand::CreateReg(LI->reg, false); @@ -1109,9 +1214,8 @@ return DidChange; } -bool -UserValue::splitRegister(unsigned OldReg, ArrayRef NewRegs, - LiveIntervals &LIS) { +bool Fragment::splitRegister(unsigned OldReg, ArrayRef NewRegs, + LiveIntervals &LIS) { bool DidChange = false; // Split locations referring to OldReg. Iterate backwards so splitLocation can // safely erase unused locations. @@ -1127,16 +1231,18 @@ void LDVImpl::splitRegister(unsigned OldReg, ArrayRef NewRegs) { bool DidChange = false; - for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext()) - DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS); + if (auto *Fragments = lookupVirtReg(OldReg)) + for (auto *Fragment : *Fragments) + DidChange |= Fragment->splitRegister(OldReg, NewRegs, *LIS); if (!DidChange) return; // Map all of the new virtual registers. - UserValue *UV = lookupVirtReg(OldReg); - for (unsigned i = 0; i != NewRegs.size(); ++i) - mapVirtReg(NewRegs[i], UV); + if (auto *Fragments = lookupVirtReg(OldReg)) + for (auto *Fragment : *Fragments) + for (unsigned i = 0; i != NewRegs.size(); ++i) + mapVirtReg(NewRegs[i], Fragment); } void LiveDebugVariables:: @@ -1145,10 +1251,10 @@ static_cast(pImpl)->splitRegister(OldReg, NewRegs); } -void UserValue::rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF, - const TargetInstrInfo &TII, - const TargetRegisterInfo &TRI, - SpillOffsetMap &SpillOffsets) { +void Fragment::rewriteLocations(VirtRegMap &VRM, const MachineFunction &MF, + const TargetInstrInfo &TII, + const TargetRegisterInfo &TRI, + SpillOffsetMap &SpillOffsets) { // Build a set of new locations with new numbers so we can coalesce our // IntervalMap if two vreg intervals collapse to the same physical location. // Use MapVector instead of SetVector because MapVector::insert returns the @@ -1223,7 +1329,7 @@ // so skip over them. See getLocationNo(). if (Loc.isUndef()) continue; - unsigned NewLocNo = LocNoMap[Loc.locNo()]; + unsigned NewLocNo = LocNoMap[Loc.getLocNo()]; I.setValueUnchecked(Loc.changeLocNo(NewLocNo)); I.setStart(I.start()); } @@ -1277,43 +1383,45 @@ return MBB->end(); } -void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex StartIdx, - SlotIndex StopIdx, DbgValueLocation Loc, - bool Spilled, unsigned SpillOffset, - LiveIntervals &LIS, const TargetInstrInfo &TII, - const TargetRegisterInfo &TRI) { +void Fragment::insertDebugValue(const DIVariable *Variable, const DebugLoc &DL, + MachineBasicBlock *MBB, SlotIndex StartIdx, + SlotIndex StopIdx, DbgValueLocation Loc, + bool Spilled, unsigned SpillOffset, + LiveIntervals &LIS, const TargetInstrInfo &TII, + const TargetRegisterInfo &TRI) { SlotIndex MBBEndIdx = LIS.getMBBEndIdx(&*MBB); // Only search within the current MBB. StopIdx = (MBBEndIdx < StopIdx) ? MBBEndIdx : StopIdx; MachineBasicBlock::iterator I = findInsertLocation(MBB, StartIdx, LIS); // Undef values don't exist in locations so create new "noreg" register MOs // for them. See getLocationNo(). - MachineOperand MO = !Loc.isUndef() ? - locations[Loc.locNo()] : - MachineOperand::CreateReg(/* Reg */ 0, /* isDef */ false, /* isImp */ false, - /* isKill */ false, /* isDead */ false, - /* isUndef */ false, /* isEarlyClobber */ false, - /* SubReg */ 0, /* isDebug */ true); + MachineOperand MO = + !Loc.isUndef() ? locations[Loc.getLocNo()] + : MachineOperand::CreateReg( + /* Reg */ 0, /* isDef */ false, /* isImp */ false, + /* isKill */ false, /* isDead */ false, + /* isUndef */ false, /* isEarlyClobber */ false, + /* SubReg */ 0, /* isDebug */ true); ++NumInsertedDebugValues; - assert(cast(Variable) - ->isValidLocationForIntrinsic(getDebugLoc()) && + assert(cast(Variable)->isValidLocationForIntrinsic(DL) && "Expected inlined-at fields to agree"); + const DIExpression *Expr = Loc.getExpression(); + assert(Expr && "nullptr represents dummy value."); // If the location was spilled, the new DBG_VALUE will be indirect. If the // original DBG_VALUE was indirect, we need to add DW_OP_deref to indicate // that the original virtual register was a pointer. Also, add the stack slot // offset for the spilled register to the expression. - const DIExpression *Expr = Expression; if (Spilled) Expr = DIExpression::prepend(Expr, DIExpression::ApplyOffset, SpillOffset); assert((!Spilled || MO.isFI()) && "a spilled location must be a frame index"); do { - BuildMI(*MBB, I, getDebugLoc(), TII.get(TargetOpcode::DBG_VALUE), - Spilled, MO, Variable, Expr); + BuildMI(*MBB, I, DL, TII.get(TargetOpcode::DBG_VALUE), Spilled, MO, + Variable, Expr); // Continue and insert DBG_VALUES after every redefinition of register // associated with the debug value within the range @@ -1330,28 +1438,36 @@ .addMetadata(Label); } -void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS, - const TargetInstrInfo &TII, - const TargetRegisterInfo &TRI, - const SpillOffsetMap &SpillOffsets) { +void Fragment::emitDebugValues(const DIVariable *Variable, const DebugLoc &DL, + VirtRegMap *VRM, LiveIntervals &LIS, + const TargetInstrInfo &TII, + const TargetRegisterInfo &TRI, + const SpillOffsetMap &SpillOffsets) { MachineFunction::iterator MFEnd = VRM->getMachineFunction().end(); for (LocMap::const_iterator I = locInts.begin(); I.valid();) { SlotIndex Start = I.start(); SlotIndex Stop = I.stop(); DbgValueLocation Loc = I.value(); + + ++I; + // Skip dummy values. + if (!Loc.getExpression()) + continue; + auto SpillIt = - !Loc.isUndef() ? SpillOffsets.find(Loc.locNo()) : SpillOffsets.end(); + !Loc.isUndef() ? SpillOffsets.find(Loc.getLocNo()) : SpillOffsets.end(); bool Spilled = SpillIt != SpillOffsets.end(); unsigned SpillOffset = Spilled ? SpillIt->second : 0; - LLVM_DEBUG(dbgs() << "\t[" << Start << ';' << Stop << "):" << Loc.locNo()); + LLVM_DEBUG(dbgs() << "\t[" << Start << ';' << Stop + << "):" << Loc.getLocNo()); MachineFunction::iterator MBB = LIS.getMBBFromIndex(Start)->getIterator(); SlotIndex MBBEnd = LIS.getMBBEndIdx(&*MBB); LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd); - insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, SpillOffset, LIS, TII, - TRI); + insertDebugValue(Variable, DL, &*MBB, Start, Stop, Loc, Spilled, + SpillOffset, LIS, TII, TRI); // This interval may span multiple basic blocks. // Insert a DBG_VALUE into each one. while (Stop > MBBEnd) { @@ -1361,14 +1477,12 @@ break; MBBEnd = LIS.getMBBEndIdx(&*MBB); LLVM_DEBUG(dbgs() << ' ' << printMBBReference(*MBB) << '-' << MBBEnd); - insertDebugValue(&*MBB, Start, Stop, Loc, Spilled, SpillOffset, LIS, TII, - TRI); + insertDebugValue(Variable, DL, &*MBB, Start, Stop, Loc, Spilled, + SpillOffset, LIS, TII, TRI); } LLVM_DEBUG(dbgs() << '\n'); if (MBB == MFEnd) break; - - ++I; } } @@ -1388,10 +1502,14 @@ return; const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); SpillOffsetMap SpillOffsets; - for (auto &userValue : userValues) { - LLVM_DEBUG(userValue->print(dbgs(), TRI)); - userValue->rewriteLocations(*VRM, *MF, *TII, *TRI, SpillOffsets); - userValue->emitDebugValues(VRM, *LIS, *TII, *TRI, SpillOffsets); + for (auto &SrcVar : sourceVariables) { + for (const auto &Fragment : *SrcVar) { + LLVM_DEBUG(Fragment->print(dbgs(), SrcVar->getVariable(), + SrcVar->getDebugLoc(), TRI)); + Fragment->rewriteLocations(*VRM, *MF, *TII, *TRI, SpillOffsets); + Fragment->emitDebugValues(SrcVar->getVariable(), SrcVar->getDebugLoc(), + VRM, *LIS, *TII, *TRI, SpillOffsets); + } } LLVM_DEBUG(dbgs() << "********** EMITTING LIVE DEBUG LABELS **********\n"); for (auto &userLabel : userLabels) { Index: llvm/test/DebugInfo/ARM/PR26163.ll =================================================================== --- llvm/test/DebugInfo/ARM/PR26163.ll +++ llvm/test/DebugInfo/ARM/PR26163.ll @@ -10,8 +10,7 @@ ; ; CHECK: DW_TAG_inlined_subroutine ; CHECK: DW_TAG_variable -; CHECK: DW_AT_location ({{.*}} -; CHECK-NEXT: [0x00000004, 0x00000014): DW_OP_lit0, DW_OP_stack_value, DW_OP_piece 0x4) +; DW_AT_location (DW_OP_lit0, DW_OP_stack_value, DW_OP_piece 0x4) ; Created form the following test case (PR26163) with ; clang -cc1 -triple armv4t--freebsd11.0-gnueabi -emit-obj -debug-info-kind=standalone -O2 -x c test.c Index: llvm/test/DebugInfo/MIR/X86/live-debug-vars-unused-arg-debugonly.mir =================================================================== --- llvm/test/DebugInfo/MIR/X86/live-debug-vars-unused-arg-debugonly.mir +++ llvm/test/DebugInfo/MIR/X86/live-debug-vars-unused-arg-debugonly.mir @@ -153,11 +153,11 @@ # not cover the whole BB. # # CHECKDBG-LABEL: ********** EMITTING LIVE DEBUG VARIABLES ********** -# CHECKDBG-NEXT: !"argc,5" [0B;0e):0 Loc0=$edi +# CHECKDBG-NEXT: !"argc,5" [0B;0e):0{{.*}}Loc0=$edi # CHECKDBG-NEXT: [0B;0e):0 %bb.0-160B -# CHECKDBG-NEXT: !"argv,5" [0B;0e):0 Loc0=$rsi +# CHECKDBG-NEXT: !"argv,5" [0B;0e):0{{.*}}Loc0=$rsi # CHECKDBG-NEXT: [0B;0e):0 %bb.0-160B -# CHECKDBG-NEXT: !"a0,7" [16r;64r):0 Loc0=%2 +# CHECKDBG-NEXT: !"a0,7" [16r;64r):0{{.*}}Loc0=%2 # CHECKDBG-NEXT: [16r;64r):0 %bb.0-160B -# CHECKDBG-NEXT: !"a1,8" [32r;80r):0 Loc0=%3 +# CHECKDBG-NEXT: !"a1,8" [32r;80r):0{{.*}}Loc0=%3 # CHECKDBG-NEXT: [32r;80r):0 %bb.0-160B Index: llvm/test/DebugInfo/X86/dbg-addr-dse.ll =================================================================== --- llvm/test/DebugInfo/X86/dbg-addr-dse.ll +++ llvm/test/DebugInfo/X86/dbg-addr-dse.ll @@ -3,10 +3,6 @@ ; RUN: FileCheck %s < %t.s --check-prefix=ASM ; RUN: llvm-dwarfdump %t.o | FileCheck %s --check-prefix=DWARF -; XFAIL: * -; See PR41992, the third and final dbg.value disappears after -; LiveDebugVariables. - ; In this example, the variable lives mostly in memory, but at the point of the ; assignment to global, it lives nowhere, and is described as the constant ; value 1. Index: llvm/test/DebugInfo/X86/live-debug-vars-dse.mir =================================================================== --- llvm/test/DebugInfo/X86/live-debug-vars-dse.mir +++ llvm/test/DebugInfo/X86/live-debug-vars-dse.mir @@ -1,9 +1,5 @@ # RUN: llc -start-after=machine-scheduler %s -o - | FileCheck %s -# XFAIL: * -# See PR41992, the third and final dbg.value disappears after -# LiveDebugVariables. - # C source: # void escape(int *); # extern int global; Index: llvm/test/DebugInfo/pr41992.ll =================================================================== --- /dev/null +++ llvm/test/DebugInfo/pr41992.ll @@ -0,0 +1,105 @@ +; Test that identical DBG_VALUES are correctly coalesced (or not). +; NOTE: The IR in this file has been modified by hand and is based off the IR +; in the top comment here https://bugs.llvm.org/show_bug.cgi?id=41992 + +; RUN: llc %s -stop-after=virtregrewriter -o - | FileCheck %s --implicit-check-not=DBG_VALUE + +; Test that two identical DBG_VALUEs are not coalesced when another used to +; describe the same source variable fragment but with a different DIExpression +; is found between them. +; +; CHECK: name: f1 +; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR:[0-9]+]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16) +; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_LLVM_fragment, 0, 16) +; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16) + + +; Test that two identical DBG_VALUEs are not coalesced when another used to +; describe overlapping fragments of the same variable but with a different DIExpression +; is found between them. +; +; CHECK: name: f2 +; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR:[0-9]+]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16) +; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_LLVM_fragment, 8, 16) +; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16) + + +; Test that two identical DBG_VALUEs are coalesced when another used to +; describe another fragment of the same source variable s found between them. +; +; CHECK: name: f3 +; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR:[0-9]+]], !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16) +; CHECK: DBG_VALUE %stack.0.x.addr, $noreg, ![[DBG_VAR]], !DIExpression(DW_OP_LLVM_fragment, 16, 16) + + +declare void @llvm.dbg.addr(metadata, metadata, metadata) +declare void @llvm.dbg.value(metadata, metadata, metadata) +declare void @escape(i32*) + +@global = external global i32, align 4 + +define void @f1(i32 %x) !dbg !8 { +entry: + %x.addr = alloca i32, align 4 + store i32 %x, i32* %x.addr, align 4 + call void @llvm.dbg.value(metadata i32* %x.addr, metadata !13, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !18 + call void @escape(i32* %x.addr), !dbg !18 + call void @llvm.dbg.value(metadata i32* %x.addr, metadata !13, metadata !DIExpression(DW_OP_LLVM_fragment, 0, 16)), !dbg !18 + store i32 1, i32* @global, align 4, !dbg !18 + call void @llvm.dbg.value(metadata i32* %x.addr, metadata !13, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !18 + store i32 2, i32* %x.addr, align 4, !dbg !18 + call void @escape(i32* %x.addr), !dbg !18 + ret void, !dbg !18 +} + +define void @f2(i32 %x) !dbg !22 { +entry: + %x.addr = alloca i32, align 4 + store i32 %x, i32* %x.addr, align 4 + call void @llvm.dbg.value(metadata i32* %x.addr, metadata !24, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !23 + call void @escape(i32* %x.addr) + call void @llvm.dbg.value(metadata i32* %x.addr, metadata !24, metadata !DIExpression(DW_OP_LLVM_fragment, 8, 16)), !dbg !23 + store i32 1, i32* @global, align 4 + call void @llvm.dbg.value(metadata i32* %x.addr, metadata !24, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !23 + store i32 2, i32* %x.addr, align 4 + call void @escape(i32* %x.addr) + ret void +} + +define void @f3(i32 %x) !dbg !19 { +entry: + %x.addr = alloca i32, align 4 + store i32 %x, i32* %x.addr, align 4 + call void @llvm.dbg.value(metadata i32* %x.addr, metadata !21, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !20 + call void @escape(i32* %x.addr) + call void @llvm.dbg.value(metadata i32* %x.addr, metadata !21, metadata !DIExpression(DW_OP_LLVM_fragment, 16, 16)), !dbg !20 + store i32 1, i32* @global, align 4 + call void @llvm.dbg.value(metadata i32* %x.addr, metadata !21, metadata !DIExpression(DW_OP_deref, DW_OP_LLVM_fragment, 0, 16)), !dbg !20 + store i32 2, i32* %x.addr, align 4 + call void @escape(i32* %x.addr) + ret void +} + +!llvm.dbg.cu = !{!0} +!llvm.module.flags = !{!3, !4} +!llvm.ident = !{!7} + +!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 10.0.0 ", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2) +!1 = !DIFile(filename: "dse.c", directory: "") +!2 = !{} +!3 = !{i32 2, !"Dwarf Version", i32 4} +!4 = !{i32 2, !"Debug Info Version", i32 3} +!7 = !{!"clang version 10.0.0 "} +!8 = distinct !DISubprogram(name: "f1", scope: !1, file: !1, line: 3, type: !9, isLocal: false, isDefinition: true, scopeLine: 3, flags: DIFlagPrototyped, isOptimized: true, unit: !0, retainedNodes: !12) +!9 = !DISubroutineType(types: !10) +!10 = !{null, !11} +!11 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) +!12 = !{!13} +!13 = !DILocalVariable(name: "x", arg: 1, scope: !8, file: !1, line: 3, type: !11) +!18 = !DILocation(line: 3, column: 12, scope: !8) +!19 = distinct !DISubprogram(name: "f2", scope: !1, file: !1, line: 20, type: !9, isLocal: false, isDefinition: true, scopeLine: 20, flags: DIFlagPrototyped, isOptimized: true, unit: !0, retainedNodes: !12) +!20 = !DILocation(line: 23, column: 12, scope: !19) +!21 = !DILocalVariable(name: "x", arg: 1, scope: !19, file: !1, line: 21, type: !11) +!22 = distinct !DISubprogram(name: "f3", scope: !1, file: !1, line: 20, type: !9, isLocal: false, isDefinition: true, scopeLine: 30, flags: DIFlagPrototyped, isOptimized: true, unit: !0, retainedNodes: !12) +!23 = !DILocation(line: 23, column: 12, scope: !22) +!24 = !DILocalVariable(name: "x", arg: 1, scope: !22, file: !1, line: 31, type: !11)