summaryrefslogtreecommitdiff
path: root/llvm/lib/CodeGen/LiveDebugVariables.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/CodeGen/LiveDebugVariables.cpp')
-rw-r--r--llvm/lib/CodeGen/LiveDebugVariables.cpp226
1 files changed, 111 insertions, 115 deletions
diff --git a/llvm/lib/CodeGen/LiveDebugVariables.cpp b/llvm/lib/CodeGen/LiveDebugVariables.cpp
index 2dd462fc72b3a..2cc547a6b741f 100644
--- a/llvm/lib/CodeGen/LiveDebugVariables.cpp
+++ b/llvm/lib/CodeGen/LiveDebugVariables.cpp
@@ -49,6 +49,7 @@
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/Metadata.h"
+#include "llvm/InitializePasses.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/Casting.h"
@@ -142,51 +143,22 @@ namespace {
class LDVImpl;
-/// A UserValue is uniquely identified by the source variable it refers to
-/// (Variable), the expression describing how to get the value (Expression) and
-/// the specific usage (InlinedAt). InlinedAt differentiates both between
-/// inline and non-inline functions, and multiple inlined instances in the same
-/// scope. FIXME: The only part of the Expression which matters for UserValue
-/// identification is the fragment part.
-class UserValueIdentity {
-private:
- /// The debug info variable we are part of.
- const DILocalVariable *Variable;
- /// Any complex address expression.
- const DIExpression *Expression;
- /// Function usage identification.
- const DILocation *InlinedAt;
-
-public:
- UserValueIdentity(const DILocalVariable *Var, const DIExpression *Expr,
- const DILocation *IA)
- : Variable(Var), Expression(Expr), InlinedAt(IA) {}
-
- bool match(const DILocalVariable *Var, const DIExpression *Expr,
- const DILocation *IA) const {
- // FIXME: The fragment should be part of the identity, but not
- // other things in the expression like stack values.
- return Var == Variable && Expr == Expression && IA == InlinedAt;
- }
-
- bool match(const UserValueIdentity &Other) const {
- return match(Other.Variable, Other.Expression, Other.InlinedAt);
- }
-
- unsigned hash_value() const {
- return hash_combine(Variable, Expression, InlinedAt);
- }
-};
-
/// A user value is a part of a debug info user variable.
///
/// 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.
/// Numbered locations referenced by locmap.
SmallVector<MachineOperand, 4> locations;
@@ -207,15 +179,49 @@ class UserValue {
LiveIntervals &LIS);
public:
- UserValue(const UserValue &) = delete;
-
/// Create a new UserValue.
UserValue(const DILocalVariable *var, const DIExpression *expr, DebugLoc L,
LocMap::Allocator &alloc)
- : Variable(var), Expression(expr), dl(std::move(L)), locInts(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;
+ }
- UserValueIdentity getId() {
- return UserValueIdentity(Variable, Expression, dl->getInlinedAt());
+ /// 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.
@@ -250,6 +256,25 @@ public:
return locations.size() - 1;
}
+ /// Remove (recycle) a location number. If \p LocNo still is used by the
+ /// locInts nothing is done.
+ void removeLocationIfUnused(unsigned LocNo) {
+ // 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)
+ return;
+ }
+ // Remove the entry in the locations vector, and adjust all references to
+ // location numbers above the removed entry.
+ 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));
+ }
+ }
+
/// Ensure that all virtual register locations are mapped.
void mapVirtRegs(LDVImpl *LDV);
@@ -327,29 +352,7 @@ public:
void print(raw_ostream &, const TargetRegisterInfo *);
};
-} // namespace
-namespace llvm {
-template <> struct DenseMapInfo<UserValueIdentity> {
- static UserValueIdentity getEmptyKey() {
- auto Key = DenseMapInfo<DILocalVariable *>::getEmptyKey();
- return UserValueIdentity(Key, nullptr, nullptr);
- }
- static UserValueIdentity getTombstoneKey() {
- auto Key = DenseMapInfo<DILocalVariable *>::getTombstoneKey();
- return UserValueIdentity(Key, nullptr, nullptr);
- }
- static unsigned getHashValue(const UserValueIdentity &Val) {
- return Val.hash_value();
- }
- static bool isEqual(const UserValueIdentity &LHS,
- const UserValueIdentity &RHS) {
- return LHS.match(RHS);
- }
-};
-} // namespace llvm
-
-namespace {
/// A user label is a part of a debug info user label.
class UserLabel {
const DILabel *Label; ///< The debug info label we are part of.
@@ -401,20 +404,20 @@ class LDVImpl {
/// All allocated UserLabel instances.
SmallVector<std::unique_ptr<UserLabel>, 2> userLabels;
- /// Map virtual register to UserValues which use it.
- using VRMap = DenseMap<unsigned, SmallVector<UserValue *, 4>>;
- VRMap VirtRegToUserVals;
+ /// Map virtual register to eq class leader.
+ using VRMap = DenseMap<unsigned, UserValue *>;
+ VRMap virtRegToEqClass;
- /// Map unique UserValue identity to UserValue.
- using UVMap = DenseMap<UserValueIdentity, UserValue *>;
- UVMap UserVarMap;
+ /// Map user variable to eq class leader.
+ using UVMap = DenseMap<const DILocalVariable *, UserValue *>;
+ UVMap userVarMap;
/// Find or create a UserValue.
UserValue *getUserValue(const DILocalVariable *Var, const DIExpression *Expr,
const DebugLoc &DL);
- /// Find the UserValues for VirtReg or null.
- SmallVectorImpl<UserValue *> *lookupVirtReg(unsigned VirtReg);
+ /// Find the EC leader for VirtReg or null.
+ UserValue *lookupVirtReg(unsigned VirtReg);
/// Add DBG_VALUE instruction to our maps.
///
@@ -454,8 +457,8 @@ public:
MF = nullptr;
userValues.clear();
userLabels.clear();
- VirtRegToUserVals.clear();
- UserVarMap.clear();
+ virtRegToEqClass.clear();
+ userVarMap.clear();
// Make sure we call emitDebugValues if the machine function was modified.
assert((!ModifiedMF || EmitDone) &&
"Dbg values are not emitted in LDV");
@@ -463,8 +466,8 @@ public:
ModifiedMF = false;
}
- /// Map virtual register to a UserValue.
- void mapVirtReg(unsigned VirtReg, UserValue *UV);
+ /// Map virtual register to an equivalence class.
+ void mapVirtReg(unsigned VirtReg, UserValue *EC);
/// Replace all references to OldReg with NewRegs.
void splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs);
@@ -503,7 +506,7 @@ static void printExtendedName(raw_ostream &OS, const DINode *Node,
const DILocation *DL) {
const LLVMContext &Ctx = Node->getContext();
StringRef Res;
- unsigned Line;
+ unsigned Line = 0;
if (const auto *V = dyn_cast<const DILocalVariable>(Node)) {
Res = V->getName();
Line = V->getLine();
@@ -572,27 +575,31 @@ void UserValue::mapVirtRegs(LDVImpl *LDV) {
UserValue *LDVImpl::getUserValue(const DILocalVariable *Var,
const DIExpression *Expr, const DebugLoc &DL) {
- auto Ident = UserValueIdentity(Var, Expr, DL->getInlinedAt());
- UserValue *&UVEntry = UserVarMap[Ident];
-
- if (UVEntry)
- return UVEntry;
+ 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;
+ }
- userValues.push_back(std::make_unique<UserValue>(Var, Expr, DL, allocator));
- return UVEntry = userValues.back().get();
+ userValues.push_back(
+ std::make_unique<UserValue>(Var, Expr, DL, allocator));
+ UserValue *UV = userValues.back().get();
+ Leader = UserValue::merge(Leader, UV);
+ return UV;
}
-void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *UV) {
+void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) {
assert(Register::isVirtualRegister(VirtReg) && "Only map VirtRegs");
- assert(UserVarMap.find(UV->getId()) != UserVarMap.end() &&
- "UserValue should exist in UserVarMap");
- VirtRegToUserVals[VirtReg].push_back(UV);
+ UserValue *&Leader = virtRegToEqClass[VirtReg];
+ Leader = UserValue::merge(Leader, EC);
}
-SmallVectorImpl<UserValue *> *LDVImpl::lookupVirtReg(unsigned VirtReg) {
- VRMap::iterator Itr = VirtRegToUserVals.find(VirtReg);
- if (Itr != VirtRegToUserVals.end())
- return &Itr->getSecond();
+UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) {
+ if (UserValue *UV = virtRegToEqClass.lookup(VirtReg))
+ return UV->getLeader();
return nullptr;
}
@@ -1086,23 +1093,14 @@ UserValue::splitLocation(unsigned OldLocNo, ArrayRef<unsigned> NewRegs,
}
}
- // Finally, remove any remaining OldLocNo intervals and OldLocNo itself.
- locations.erase(locations.begin() + OldLocNo);
- LocMapI.goToBegin();
- while (LocMapI.valid()) {
- DbgValueLocation v = LocMapI.value();
- if (v.locNo() == OldLocNo) {
- LLVM_DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';'
- << LocMapI.stop() << ")\n");
- LocMapI.erase();
- } else {
- // Undef values always have location number UndefLocNo, so don't change
- // locNo in that case. See getLocationNo().
- if (!v.isUndef() && v.locNo() > OldLocNo)
- LocMapI.setValueUnchecked(v.changeLocNo(v.locNo() - 1));
- ++LocMapI;
- }
- }
+ // Finally, remove OldLocNo unless it is still used by some interval in the
+ // locInts map. One case when OldLocNo still is in use is when the register
+ // has been spilled. In such situations the spilled register is kept as a
+ // location until rewriteLocations is called (VirtRegMap is mapping the old
+ // register to the spill slot). So for a while we can have locations that map
+ // to virtual registers that have been removed from both the MachineFunction
+ // and from LiveIntervals.
+ removeLocationIfUnused(OldLocNo);
LLVM_DEBUG({
dbgs() << "Split result: \t";
@@ -1129,18 +1127,16 @@ UserValue::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs,
void LDVImpl::splitRegister(unsigned OldReg, ArrayRef<unsigned> NewRegs) {
bool DidChange = false;
- if (auto *UserVals = lookupVirtReg(OldReg))
- for (auto *UV : *UserVals)
- DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
+ for (UserValue *UV = lookupVirtReg(OldReg); UV; UV = UV->getNext())
+ DidChange |= UV->splitRegister(OldReg, NewRegs, *LIS);
if (!DidChange)
return;
// Map all of the new virtual registers.
- if (auto *UserVals = lookupVirtReg(OldReg))
- for (auto *UV : *UserVals)
- for (unsigned i = 0; i != NewRegs.size(); ++i)
- mapVirtReg(NewRegs[i], UV);
+ UserValue *UV = lookupVirtReg(OldReg);
+ for (unsigned i = 0; i != NewRegs.size(); ++i)
+ mapVirtReg(NewRegs[i], UV);
}
void LiveDebugVariables::
generated by cgit v1.2.3 (git 2.25.1) at 2025-11-04 14:42:33 +0000