Index: llvm/trunk/include/llvm/CodeGen/MachineOperand.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/MachineOperand.h +++ llvm/trunk/include/llvm/CodeGen/MachineOperand.h @@ -14,6 +14,7 @@ #ifndef LLVM_CODEGEN_MACHINEOPERAND_H #define LLVM_CODEGEN_MACHINEOPERAND_H +#include "llvm/ADT/DenseMap.h" #include "llvm/IR/Intrinsics.h" #include "llvm/Support/DataTypes.h" #include @@ -65,6 +66,7 @@ MO_CFIIndex, ///< MCCFIInstruction index. MO_IntrinsicID, ///< Intrinsic ID for ISel MO_Predicate, ///< Generic predicate for ISel + MO_Last = MO_Predicate, }; private: @@ -781,6 +783,14 @@ private: void removeRegFromUses(); + /// Artificial kinds for DenseMap usage. + enum : unsigned char { + MO_Empty = MO_Last + 1, + MO_Tombstone, + }; + + friend struct DenseMapInfo; + //===--------------------------------------------------------------------===// // Methods for handling register use/def lists. //===--------------------------------------------------------------------===// @@ -794,6 +804,26 @@ } }; +template <> struct DenseMapInfo { + static MachineOperand getEmptyKey() { + return MachineOperand(static_cast( + MachineOperand::MO_Empty)); + } + static MachineOperand getTombstoneKey() { + return MachineOperand(static_cast( + MachineOperand::MO_Tombstone)); + } + static unsigned getHashValue(const MachineOperand &MO) { + return hash_value(MO); + } + static bool isEqual(const MachineOperand &LHS, const MachineOperand &RHS) { + if (LHS.getType() == MachineOperand::MO_Empty || + LHS.getType() == MachineOperand::MO_Tombstone) + return LHS.getType() == RHS.getType(); + return LHS.isIdenticalTo(RHS); + } +}; + inline raw_ostream &operator<<(raw_ostream &OS, const MachineOperand& MO) { MO.print(OS, nullptr); return OS; Index: llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp =================================================================== --- llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp +++ llvm/trunk/lib/CodeGen/LiveDebugVariables.cpp @@ -126,11 +126,6 @@ /// lexical scope. SmallSet trimmedDefs; - /// coalesceLocation - After LocNo was changed, check if it has become - /// identical to another location, and coalesce them. This may cause LocNo or - /// a later location to be erased, but no earlier location will be erased. - void coalesceLocation(unsigned LocNo); - /// insertDebugValue - Insert a DBG_VALUE into MBB at Idx for LocNo. void insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, unsigned LocNo, LiveIntervals &LIS, const TargetInstrInfo &TII); @@ -421,34 +416,6 @@ } #endif -void UserValue::coalesceLocation(unsigned LocNo) { - unsigned KeepLoc = 0; - for (unsigned e = locations.size(); KeepLoc != e; ++KeepLoc) { - if (KeepLoc == LocNo) - continue; - if (locations[KeepLoc].isIdenticalTo(locations[LocNo])) - break; - } - // No matches. - if (KeepLoc == locations.size()) - return; - - // Keep the smaller location, erase the larger one. - unsigned EraseLoc = LocNo; - if (KeepLoc > EraseLoc) - std::swap(KeepLoc, EraseLoc); - locations.erase(locations.begin() + EraseLoc); - - // Rewrite values. - for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) { - unsigned v = I.value(); - if (v == EraseLoc) - I.setValue(KeepLoc); // Coalesce when possible. - else if (v > EraseLoc) - I.setValueUnchecked(v-1); // Avoid coalescing with untransformed values. - } -} - void UserValue::mapVirtRegs(LDVImpl *LDV) { for (unsigned i = 0, e = locations.size(); i != e; ++i) if (locations[i].isReg() && @@ -973,31 +940,54 @@ static_cast(pImpl)->splitRegister(OldReg, NewRegs); } -void -UserValue::rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI) { - // Iterate over locations in reverse makes it easier to handle coalescing. - for (unsigned i = locations.size(); i ; --i) { - unsigned LocNo = i-1; - MachineOperand &Loc = locations[LocNo]; +void UserValue::rewriteLocations(VirtRegMap &VRM, + const TargetRegisterInfo &TRI) { + // 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 + // position of the previously or newly inserted element. + MapVector NewLocations; + SmallVector LocNoMap(locations.size()); + for (unsigned I = 0, E = locations.size(); I != E; ++I) { + MachineOperand Loc = locations[I]; // Only virtual registers are rewritten. - if (!Loc.isReg() || !Loc.getReg() || - !TargetRegisterInfo::isVirtualRegister(Loc.getReg())) - continue; - unsigned VirtReg = Loc.getReg(); - if (VRM.isAssignedReg(VirtReg) && - TargetRegisterInfo::isPhysicalRegister(VRM.getPhys(VirtReg))) { - // This can create a %noreg operand in rare cases when the sub-register - // index is no longer available. That means the user value is in a - // non-existent sub-register, and %noreg is exactly what we want. - Loc.substPhysReg(VRM.getPhys(VirtReg), TRI); - } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) { - // FIXME: Translate SubIdx to a stackslot offset. - Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg)); - } else { - Loc.setReg(0); - Loc.setSubReg(0); + if (Loc.isReg() && Loc.getReg() && + TargetRegisterInfo::isVirtualRegister(Loc.getReg())) { + unsigned VirtReg = Loc.getReg(); + if (VRM.isAssignedReg(VirtReg) && + TargetRegisterInfo::isPhysicalRegister(VRM.getPhys(VirtReg))) { + // This can create a %noreg operand in rare cases when the sub-register + // index is no longer available. That means the user value is in a + // non-existent sub-register, and %noreg is exactly what we want. + Loc.substPhysReg(VRM.getPhys(VirtReg), TRI); + } else if (VRM.getStackSlot(VirtReg) != VirtRegMap::NO_STACK_SLOT) { + // FIXME: Translate SubIdx to a stackslot offset. + Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg)); + } else { + Loc.setReg(0); + Loc.setSubReg(0); + } } - coalesceLocation(LocNo); + + // Insert this location if it doesn't already exist and record a mapping + // from the old number to the new number. + auto InsertResult = NewLocations.insert({Loc, false}); + LocNoMap[I] = std::distance(NewLocations.begin(), InsertResult.first); + } + + // Rewrite the locations. + locations.clear(); + for (const auto &Pair : NewLocations) + locations.push_back(Pair.first); + + // Update the interval map, but only coalesce left, since intervals to the + // right use the old location numbers. This should merge two contiguous + // DBG_VALUE intervals with different vregs that were allocated to the same + // physical register. + for (LocMap::iterator I = locInts.begin(); I.valid(); ++I) { + unsigned NewLocNo = LocNoMap[I.value()]; + I.setValueUnchecked(NewLocNo); + I.setStart(I.start()); } }