X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLiveDebugVariables.cpp;h=f89879dd33b14e8026897785ff621c1f5c633d35;hb=6035518e3bd06cef0515af5a319fbe2cea7df6d4;hp=2b6a54eab5ad654e47aed9e9f0919289493d176b;hpb=1dea232624c246341a5a98e0d481ba89f854012c;p=oota-llvm.git diff --git a/lib/CodeGen/LiveDebugVariables.cpp b/lib/CodeGen/LiveDebugVariables.cpp index 2b6a54eab5a..f89879dd33b 100644 --- a/lib/CodeGen/LiveDebugVariables.cpp +++ b/lib/CodeGen/LiveDebugVariables.cpp @@ -19,26 +19,39 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "livedebug" #include "LiveDebugVariables.h" -#include "VirtRegMap.h" -#include "llvm/Constants.h" -#include "llvm/Metadata.h" -#include "llvm/Value.h" #include "llvm/ADT/IntervalMap.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/LexicalScopes.h" #include "llvm/CodeGen/LiveIntervalAnalysis.h" #include "llvm/CodeGen/MachineDominators.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstrBuilder.h" +#include "llvm/CodeGen/MachineRegisterInfo.h" #include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/VirtRegMap.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/DebugInfo.h" +#include "llvm/IR/Metadata.h" +#include "llvm/IR/Value.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetRegisterInfo.h" +#include "llvm/Target/TargetSubtargetInfo.h" + +#include using namespace llvm; +#define DEBUG_TYPE "livedebug" + +static cl::opt +EnableLDV("live-debug-variables", cl::init(true), + cl::desc("Enable the live debug variables pass"), cl::Hidden); + +STATISTIC(NumInsertedDebugValues, "Number of DBG_VALUEs inserted"); char LiveDebugVariables::ID = 0; INITIALIZE_PASS_BEGIN(LiveDebugVariables, "livedebugvars", @@ -55,111 +68,35 @@ void LiveDebugVariables::getAnalysisUsage(AnalysisUsage &AU) const { MachineFunctionPass::getAnalysisUsage(AU); } -LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID), pImpl(0) { +LiveDebugVariables::LiveDebugVariables() : MachineFunctionPass(ID), pImpl(nullptr) { initializeLiveDebugVariablesPass(*PassRegistry::getPassRegistry()); } -/// Location - All the different places a user value can reside. -/// Note that this includes immediate values that technically aren't locations. -namespace { -struct Location { - /// kind - What kind of location is this? - enum Kind { - locUndef = 0, - locImm = 0x80000000, - locFPImm - }; - /// Kind - One of the following: - /// 1. locUndef - /// 2. Register number (physical or virtual), data.SubIdx is the subreg index. - /// 3. ~Frame index, data.Offset is the offset. - /// 4. locImm, data.ImmVal is the constant integer value. - /// 5. locFPImm, data.CFP points to the floating point constant. - unsigned Kind; - - /// Data - Extra data about location. - union { - unsigned SubIdx; ///< For virtual registers. - int64_t Offset; ///< For frame indices. - int64_t ImmVal; ///< For locImm. - const ConstantFP *CFP; ///< For locFPImm. - } Data; - - Location(const MachineOperand &MO) { - switch(MO.getType()) { - case MachineOperand::MO_Register: - Kind = MO.getReg(); - Data.SubIdx = MO.getSubReg(); - return; - case MachineOperand::MO_Immediate: - Kind = locImm; - Data.ImmVal = MO.getImm(); - return; - case MachineOperand::MO_FPImmediate: - Kind = locFPImm; - Data.CFP = MO.getFPImm(); - return; - case MachineOperand::MO_FrameIndex: - Kind = ~MO.getIndex(); - // FIXME: MO_FrameIndex should support an offset. - Data.Offset = 0; - return; - default: - Kind = locUndef; - return; - } - } +/// LocMap - Map of where a user value is live, and its location. +typedef IntervalMap LocMap; - /// addOperand - Add this location as a machine operand to MI. - MachineInstrBuilder addOperand(MachineInstrBuilder MI) const { - switch (Kind) { - case locImm: - return MI.addImm(Data.ImmVal); - case locFPImm: - return MI.addFPImm(Data.CFP); - default: - if (isFrameIndex()) - return MI.addFrameIndex(getFrameIndex()); - else - return MI.addReg(Kind); // reg and undef. - } - } +namespace { +/// UserValueScopes - Keeps track of lexical scopes associated with a +/// user value's source location. +class UserValueScopes { + DebugLoc DL; + LexicalScopes &LS; + SmallPtrSet LBlocks; - bool operator==(const Location &RHS) const { - if (Kind != RHS.Kind) - return false; - switch (Kind) { - case locUndef: +public: + UserValueScopes(DebugLoc D, LexicalScopes &L) : DL(D), LS(L) {} + + /// dominates - Return true if current scope dominates at least one machine + /// instruction in a given machine basic block. + bool dominates(MachineBasicBlock *MBB) { + if (LBlocks.empty()) + LS.getMachineBasicBlocks(DL, LBlocks); + if (LBlocks.count(MBB) != 0 || LS.dominates(DL, MBB)) return true; - case locImm: - return Data.ImmVal == RHS.Data.ImmVal; - case locFPImm: - return Data.CFP == RHS.Data.CFP; - default: - if (isReg()) - return Data.SubIdx == RHS.Data.SubIdx; - else - return Data.Offset == RHS.Data.Offset; - } + return false; } - - /// isUndef - is this the singleton undef? - bool isUndef() const { return Kind == locUndef; } - - /// isReg - is this a register location? - bool isReg() const { return Kind && Kind < locImm; } - - /// isFrameIndex - is this a frame index location? - bool isFrameIndex() const { return Kind > locFPImm; } - - int getFrameIndex() const { return ~Kind; } - - void print(raw_ostream&, const TargetRegisterInfo*); }; -} - -/// LocMap - Map of where a user value is live, and its location. -typedef IntervalMap LocMap; +} // end anonymous namespace /// UserValue - A user value is a part of a debug info user variable. /// @@ -171,15 +108,18 @@ typedef IntervalMap LocMap; /// held by the same virtual register. The equivalence class is the transitive /// closure of that relation. namespace { +class LDVImpl; class UserValue { const MDNode *variable; ///< The debug info variable we are part of. unsigned offset; ///< Byte offset into variable. - + bool IsIndirect; ///< true if this is a register-indirect+offset value. + 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; ///< Next value in equivalence class, or null. /// Numbered locations referenced by locmap. - SmallVector locations; + SmallVector locations; /// Map of slot indices where this value is live. LocMap locInts; @@ -193,14 +133,17 @@ class UserValue { void insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, unsigned LocNo, LiveIntervals &LIS, const TargetInstrInfo &TII); - /// insertDebugKill - Insert an undef DBG_VALUE into MBB at Idx. - void insertDebugKill(MachineBasicBlock *MBB, SlotIndex Idx, - LiveIntervals &LIS, const TargetInstrInfo &TII); + /// splitLocation - Replace OldLocNo ranges with NewRegs ranges where NewRegs + /// is live. Returns true if any changes were made. + bool splitLocation(unsigned OldLocNo, ArrayRef NewRegs, + LiveIntervals &LIS); public: /// UserValue - Create a new UserValue. - UserValue(const MDNode *var, unsigned o, LocMap::Allocator &alloc) - : variable(var), offset(o), leader(this), next(0), locInts(alloc) + UserValue(const MDNode *var, unsigned o, bool i, DebugLoc L, + LocMap::Allocator &alloc) + : variable(var), offset(o), IsIndirect(i), dl(L), leader(this), + next(nullptr), locInts(alloc) {} /// getLeader - Get the leader of this value's equivalence class. @@ -214,9 +157,9 @@ public: /// getNext - Return the next UserValue in the equivalence class. UserValue *getNext() const { return next; } - /// match - Does this UserValue match the aprameters? - bool match(const MDNode *Var, unsigned Offset) const { - return Var == variable && Offset == offset; + /// match - Does this UserValue match the parameters? + bool match(const MDNode *Var, unsigned Offset, bool indirect) const { + return Var == variable && Offset == offset && indirect == IsIndirect; } /// merge - Merge equivalence classes. @@ -238,54 +181,101 @@ public: } /// getLocationNo - Return the location number that matches Loc. - unsigned getLocationNo(Location Loc) { - if (Loc.isUndef()) - return ~0u; - unsigned n = std::find(locations.begin(), locations.end(), Loc) - - locations.begin(); - if (n == locations.size()) - locations.push_back(Loc); - return n; + unsigned getLocationNo(const MachineOperand &LocMO) { + if (LocMO.isReg()) { + if (LocMO.getReg() == 0) + return ~0u; + // For register locations we dont care about use/def and other flags. + for (unsigned i = 0, e = locations.size(); i != e; ++i) + if (locations[i].isReg() && + locations[i].getReg() == LocMO.getReg() && + locations[i].getSubReg() == LocMO.getSubReg()) + return i; + } else + for (unsigned i = 0, e = locations.size(); i != e; ++i) + if (LocMO.isIdenticalTo(locations[i])) + return i; + locations.push_back(LocMO); + // We are storing a MachineOperand outside a MachineInstr. + locations.back().clearParent(); + // Don't store def operands. + if (locations.back().isReg()) + locations.back().setIsUse(); + return locations.size() - 1; } + /// mapVirtRegs - Ensure that all virtual register locations are mapped. + void mapVirtRegs(LDVImpl *LDV); + /// addDef - Add a definition point to this value. void addDef(SlotIndex Idx, const MachineOperand &LocMO) { // Add a singular (Idx,Idx) -> Loc mapping. LocMap::iterator I = locInts.find(Idx); if (!I.valid() || I.start() != Idx) I.insert(Idx, Idx.getNextSlot(), getLocationNo(LocMO)); + else + // A later DBG_VALUE at the same SlotIndex overrides the old location. + I.setValue(getLocationNo(LocMO)); } /// extendDef - Extend the current definition as far as possible down the /// dominator tree. Stop when meeting an existing def or when leaving the live /// range of VNI. + /// End points where VNI is no longer live are added to Kills. /// @param Idx Starting point for the definition. /// @param LocNo Location number to propagate. - /// @param LI Restrict liveness to where LI has the value VNI. May be null. - /// @param VNI When LI is not null, this is the value to restrict to. + /// @param LR Restrict liveness to where LR has the value VNI. May be null. + /// @param VNI When LR is not null, this is the value to restrict to. + /// @param Kills Append end points of VNI's live range to Kills. /// @param LIS Live intervals analysis. /// @param MDT Dominator tree. void extendDef(SlotIndex Idx, unsigned LocNo, - LiveInterval *LI, const VNInfo *VNI, - LiveIntervals &LIS, MachineDominatorTree &MDT); + LiveRange *LR, const VNInfo *VNI, + SmallVectorImpl *Kills, + LiveIntervals &LIS, MachineDominatorTree &MDT, + UserValueScopes &UVS); + + /// addDefsFromCopies - The value in LI/LocNo may be copies to other + /// registers. Determine if any of the copies are available at the kill + /// points, and add defs if possible. + /// @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 NewDefs Append (Idx, LocNo) of inserted defs here. + void addDefsFromCopies(LiveInterval *LI, unsigned LocNo, + const SmallVectorImpl &Kills, + SmallVectorImpl > &NewDefs, + MachineRegisterInfo &MRI, + LiveIntervals &LIS); /// computeIntervals - Compute the live intervals of all locations after /// collecting all their def points. - void computeIntervals(LiveIntervals &LIS, MachineDominatorTree &MDT); + void computeIntervals(MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI, + LiveIntervals &LIS, MachineDominatorTree &MDT, + UserValueScopes &UVS); - /// renameRegister - Update locations to rewrite OldReg as NewReg:SubIdx. - void renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx, - const TargetRegisterInfo *TRI); + /// splitRegister - Replace OldReg ranges with NewRegs ranges where NewRegs is + /// live. Returns true if any changes were made. + bool splitRegister(unsigned OldLocNo, ArrayRef NewRegs, + LiveIntervals &LIS); /// rewriteLocations - Rewrite virtual register locations according to the /// provided virtual register map. void rewriteLocations(VirtRegMap &VRM, const TargetRegisterInfo &TRI); - /// emitDebugVariables - Recreate DBG_VALUE instruction from data structures. + /// emitDebugValues - Recreate DBG_VALUE instruction from data structures. void emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS, const TargetInstrInfo &TRI); - void print(raw_ostream&, const TargetRegisterInfo*); + /// findDebugLoc - Return DebugLoc used for this DBG_VALUE instruction. A + /// variable may have more than one corresponding DBG_VALUE instructions. + /// Only first one needs DebugLoc to identify variable's lexical scope + /// in source file. + DebugLoc findDebugLoc(); + + /// getDebugLoc - Return DebugLoc of this UserValue. + DebugLoc getDebugLoc() { return dl;} + void print(raw_ostream&, const TargetMachine*); }; } // namespace @@ -296,11 +286,17 @@ class LDVImpl { LocMap::Allocator allocator; MachineFunction *MF; LiveIntervals *LIS; + LexicalScopes LS; MachineDominatorTree *MDT; const TargetRegisterInfo *TRI; + /// Whether emitDebugValues is called. + bool EmitDone; + /// Whether the machine function is modified during the pass. + bool ModifiedMF; + /// userValues - All allocated UserValue instances. - SmallVector userValues; + SmallVector, 8> userValues; /// Map virtual register to eq class leader. typedef DenseMap VRMap; @@ -311,14 +307,12 @@ class LDVImpl { UVMap userVarMap; /// getUserValue - Find or create a UserValue. - UserValue *getUserValue(const MDNode *Var, unsigned Offset); + UserValue *getUserValue(const MDNode *Var, unsigned Offset, + bool IsIndirect, DebugLoc DL); /// lookupVirtReg - Find the EC leader for VirtReg or null. UserValue *lookupVirtReg(unsigned VirtReg); - /// mapVirtReg - Map virtual register to an equivalence class. - void mapVirtReg(unsigned VirtReg, UserValue *EC); - /// handleDebugValue - Add DBG_VALUE instruction to our maps. /// @param MI DBG_VALUE instruction /// @param Idx Last valid SLotIndex before instruction. @@ -336,58 +330,41 @@ class LDVImpl { void computeIntervals(); public: - LDVImpl(LiveDebugVariables *ps) : pass(*ps) {} + LDVImpl(LiveDebugVariables *ps) + : pass(*ps), MF(nullptr), EmitDone(false), ModifiedMF(false) {} bool runOnMachineFunction(MachineFunction &mf); - /// clear - Relase all memory. + /// clear - Release all memory. void clear() { - DeleteContainerPointers(userValues); + MF = nullptr; userValues.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"); + EmitDone = false; + ModifiedMF = false; } - /// renameRegister - Replace all references to OldReg wiht NewReg:SubIdx. - void renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx); + /// mapVirtReg - Map virtual register to an equivalence class. + void mapVirtReg(unsigned VirtReg, UserValue *EC); + + /// splitRegister - Replace all references to OldReg with NewRegs. + void splitRegister(unsigned OldReg, ArrayRef NewRegs); - /// emitDebugVariables - Recreate DBG_VALUE instruction from data structures. + /// emitDebugValues - Recreate DBG_VALUE instruction from data structures. void emitDebugValues(VirtRegMap *VRM); void print(raw_ostream&); }; } // namespace -void Location::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { - switch (Kind) { - case locUndef: - OS << "undef"; - return; - case locImm: - OS << "int:" << Data.ImmVal; - return; - case locFPImm: - OS << "fp:" << Data.CFP->getValueAPF().convertToDouble(); - return; - default: - if (isReg()) { - if (TargetRegisterInfo::isVirtualRegister(Kind)) { - OS << "%reg" << Kind; - if (Data.SubIdx) - OS << ':' << TRI->getSubRegIndexName(Data.SubIdx); - } else - OS << '%' << TRI->getName(Kind); - } else { - OS << "fi#" << ~Kind; - if (Data.Offset) - OS << '+' << Data.Offset; - } - return; - } -} - -void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { - if (const MDString *MDS = dyn_cast(variable->getOperand(2))) - OS << "!\"" << MDS->getString() << "\"\t"; +void UserValue::print(raw_ostream &OS, const TargetMachine *TM) { + DIVariable DV(variable); + OS << "!\""; + DV.printExtendedName(OS); + OS << "\"\t"; if (offset) OS << '+' << offset; for (LocMap::const_iterator I = locInts.begin(); I.valid(); ++I) { @@ -399,7 +376,7 @@ void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { } for (unsigned i = 0, e = locations.size(); i != e; ++i) { OS << " Loc" << i << '='; - locations[i].print(OS, TRI); + locations[i].print(OS, TM); } OS << '\n'; } @@ -407,21 +384,25 @@ void UserValue::print(raw_ostream &OS, const TargetRegisterInfo *TRI) { void LDVImpl::print(raw_ostream &OS) { OS << "********** DEBUG VARIABLES **********\n"; for (unsigned i = 0, e = userValues.size(); i != e; ++i) - userValues[i]->print(OS, TRI); + userValues[i]->print(OS, &MF->getTarget()); } void UserValue::coalesceLocation(unsigned LocNo) { - unsigned KeepLoc = std::find(locations.begin(), locations.begin() + LocNo, - locations[LocNo]) - locations.begin(); - unsigned EraseLoc = LocNo; - if (KeepLoc == LocNo) { - EraseLoc = std::find(locations.begin() + LocNo + 1, locations.end(), - locations[LocNo]) - locations.begin(); - // No matches. - if (EraseLoc == locations.size()) - return; + unsigned KeepLoc = 0; + for (unsigned e = locations.size(); KeepLoc != e; ++KeepLoc) { + if (KeepLoc == LocNo) + continue; + if (locations[KeepLoc].isIdenticalTo(locations[LocNo])) + break; } - assert(KeepLoc < EraseLoc); + // 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. @@ -434,18 +415,27 @@ void UserValue::coalesceLocation(unsigned LocNo) { } } -UserValue *LDVImpl::getUserValue(const MDNode *Var, unsigned Offset) { +void UserValue::mapVirtRegs(LDVImpl *LDV) { + for (unsigned i = 0, e = locations.size(); i != e; ++i) + if (locations[i].isReg() && + TargetRegisterInfo::isVirtualRegister(locations[i].getReg())) + LDV->mapVirtReg(locations[i].getReg(), this); +} + +UserValue *LDVImpl::getUserValue(const MDNode *Var, unsigned Offset, + bool IsIndirect, DebugLoc DL) { UserValue *&Leader = userVarMap[Var]; if (Leader) { UserValue *UV = Leader->getLeader(); Leader = UV; for (; UV; UV = UV->getNext()) - if (UV->match(Var, Offset)) + if (UV->match(Var, Offset, IsIndirect)) return UV; } - UserValue *UV = new UserValue(Var, Offset, allocator); - userValues.push_back(UV); + userValues.push_back( + make_unique(Var, Offset, IsIndirect, DL, allocator)); + UserValue *UV = userValues.back().get(); Leader = UserValue::merge(Leader, UV); return UV; } @@ -459,29 +449,24 @@ void LDVImpl::mapVirtReg(unsigned VirtReg, UserValue *EC) { UserValue *LDVImpl::lookupVirtReg(unsigned VirtReg) { if (UserValue *UV = virtRegToEqClass.lookup(VirtReg)) return UV->getLeader(); - return 0; + return nullptr; } bool LDVImpl::handleDebugValue(MachineInstr *MI, SlotIndex Idx) { // DBG_VALUE loc, offset, variable if (MI->getNumOperands() != 3 || - !MI->getOperand(1).isImm() || !MI->getOperand(2).isMetadata()) { + !(MI->getOperand(1).isReg() || MI->getOperand(1).isImm()) || + !MI->getOperand(2).isMetadata()) { DEBUG(dbgs() << "Can't handle " << *MI); return false; } // Get or create the UserValue for (variable,offset). - unsigned Offset = MI->getOperand(1).getImm(); + bool IsIndirect = MI->isIndirectDebugValue(); + unsigned Offset = IsIndirect ? MI->getOperand(1).getImm() : 0; const MDNode *Var = MI->getOperand(2).getMetadata(); - UserValue *UV = getUserValue(Var, Offset); - - // If the location is a virtual register, make sure it is mapped. - if (MI->getOperand(0).isReg()) { - unsigned Reg = MI->getOperand(0).getReg(); - if (Reg && TargetRegisterInfo::isVirtualRegister(Reg)) - mapVirtReg(Reg, UV); - } - + //here. + UserValue *UV = getUserValue(Var, Offset, IsIndirect, MI->getDebugLoc()); UV->addDef(Idx, MI->getOperand(0)); return true; } @@ -500,7 +485,7 @@ bool LDVImpl::collectDebugValues(MachineFunction &mf) { // DBG_VALUE has no slot index, use the previous instruction instead. SlotIndex Idx = MBBI == MBB->begin() ? LIS->getMBBStartIdx(MBB) : - LIS->getInstructionIndex(llvm::prior(MBBI)).getDefIndex(); + LIS->getInstructionIndex(std::prev(MBBI)).getRegSlot(); // Handle consecutive DBG_VALUE instructions with the same slot index. do { if (handleDebugValue(MBBI, Idx)) { @@ -515,25 +500,29 @@ bool LDVImpl::collectDebugValues(MachineFunction &mf) { } void UserValue::extendDef(SlotIndex Idx, unsigned LocNo, - LiveInterval *LI, const VNInfo *VNI, - LiveIntervals &LIS, MachineDominatorTree &MDT) { + LiveRange *LR, const VNInfo *VNI, + SmallVectorImpl *Kills, + LiveIntervals &LIS, MachineDominatorTree &MDT, + UserValueScopes &UVS) { SmallVector Todo; Todo.push_back(Idx); - do { SlotIndex Start = Todo.pop_back_val(); MachineBasicBlock *MBB = LIS.getMBBFromIndex(Start); SlotIndex Stop = LIS.getMBBEndIdx(MBB); - LocMap::iterator I = locInts.find(Idx); + LocMap::iterator I = locInts.find(Start); // Limit to VNI's live range. bool ToEnd = true; - if (LI && VNI) { - LiveRange *Range = LI->getLiveRangeContaining(Start); - if (!Range || Range->valno != VNI) + if (LR && VNI) { + LiveInterval::Segment *Segment = LR->getSegmentContaining(Start); + if (!Segment || Segment->valno != VNI) { + if (Kills) + Kills->push_back(Start); continue; - if (Range->end < Stop) - Stop = Range->end, ToEnd = false; + } + if (Segment->end < Stop) + Stop = Segment->end, ToEnd = false; } // There could already be a short def at Start. @@ -549,6 +538,9 @@ void UserValue::extendDef(SlotIndex Idx, unsigned LocNo, // Limited by the next def. if (I.valid() && I.start() < Stop) Stop = I.start(), ToEnd = false; + // Limited by VNI's live range. + else if (!ToEnd && Kills) + Kills->push_back(Stop); if (Start >= Stop) continue; @@ -560,13 +552,91 @@ void UserValue::extendDef(SlotIndex Idx, unsigned LocNo, continue; const std::vector &Children = MDT.getNode(MBB)->getChildren(); - for (unsigned i = 0, e = Children.size(); i != e; ++i) - Todo.push_back(LIS.getMBBStartIdx(Children[i]->getBlock())); + for (unsigned i = 0, e = Children.size(); i != e; ++i) { + MachineBasicBlock *MBB = Children[i]->getBlock(); + if (UVS.dominates(MBB)) + Todo.push_back(LIS.getMBBStartIdx(MBB)); + } } while (!Todo.empty()); } void -UserValue::computeIntervals(LiveIntervals &LIS, MachineDominatorTree &MDT) { +UserValue::addDefsFromCopies(LiveInterval *LI, unsigned LocNo, + const SmallVectorImpl &Kills, + SmallVectorImpl > &NewDefs, + MachineRegisterInfo &MRI, LiveIntervals &LIS) { + if (Kills.empty()) + return; + // Don't track copies from physregs, there are too many uses. + if (!TargetRegisterInfo::isVirtualRegister(LI->reg)) + return; + + // Collect all the (vreg, valno) pairs that are copies of LI. + SmallVector, 8> CopyValues; + for (MachineOperand &MO : MRI.use_nodbg_operands(LI->reg)) { + MachineInstr *MI = MO.getParent(); + // Copies of the full value. + if (MO.getSubReg() || !MI->isCopy()) + continue; + unsigned DstReg = MI->getOperand(0).getReg(); + + // Don't follow copies to physregs. These are usually setting up call + // arguments, and the argument registers are always call clobbered. We are + // better off in the source register which could be a callee-saved register, + // or it could be spilled. + if (!TargetRegisterInfo::isVirtualRegister(DstReg)) + continue; + + // Is LocNo extended to reach this copy? If not, another def may be blocking + // 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) + continue; + + if (!LIS.hasInterval(DstReg)) + continue; + LiveInterval *DstLI = &LIS.getInterval(DstReg); + const VNInfo *DstVNI = DstLI->getVNInfoAt(Idx.getRegSlot()); + assert(DstVNI && DstVNI->def == Idx.getRegSlot() && "Bad copy value"); + CopyValues.push_back(std::make_pair(DstLI, DstVNI)); + } + + if (CopyValues.empty()) + return; + + DEBUG(dbgs() << "Got " << CopyValues.size() << " copies of " << *LI << '\n'); + + // Try to add defs of the copied values for each kill point. + for (unsigned i = 0, e = Kills.size(); i != e; ++i) { + SlotIndex Idx = Kills[i]; + for (unsigned j = 0, e = CopyValues.size(); j != e; ++j) { + LiveInterval *DstLI = CopyValues[j].first; + const VNInfo *DstVNI = CopyValues[j].second; + if (DstLI->getVNInfoAt(Idx) != DstVNI) + continue; + // Check that there isn't already a def at Idx + LocMap::iterator I = locInts.find(Idx); + if (I.valid() && I.start() <= Idx) + continue; + DEBUG(dbgs() << "Kill at " << Idx << " covered by valno #" + << DstVNI->id << " in " << *DstLI << '\n'); + MachineInstr *CopyMI = LIS.getInstructionFromIndex(DstVNI->def); + assert(CopyMI && CopyMI->isCopy() && "Bad copy value"); + unsigned LocNo = getLocationNo(CopyMI->getOperand(0)); + I.insert(Idx, Idx.getNextSlot(), LocNo); + NewDefs.push_back(std::make_pair(Idx, LocNo)); + break; + } + } +} + +void +UserValue::computeIntervals(MachineRegisterInfo &MRI, + const TargetRegisterInfo &TRI, + LiveIntervals &LIS, + MachineDominatorTree &MDT, + UserValueScopes &UVS) { SmallVector, 16> Defs; // Collect all defs to be extended (Skipping undefs). @@ -574,18 +644,38 @@ UserValue::computeIntervals(LiveIntervals &LIS, MachineDominatorTree &MDT) { if (I.value() != ~0u) Defs.push_back(std::make_pair(I.start(), I.value())); - for (unsigned i = 0, e = Defs.size(); i != e; ++i) { + // Extend all defs, and possibly add new ones along the way. + for (unsigned i = 0; i != Defs.size(); ++i) { SlotIndex Idx = Defs[i].first; unsigned LocNo = Defs[i].second; - const Location &Loc = locations[LocNo]; + const MachineOperand &Loc = locations[LocNo]; + + if (!Loc.isReg()) { + extendDef(Idx, LocNo, nullptr, nullptr, nullptr, LIS, MDT, UVS); + continue; + } // Register locations are constrained to where the register value is live. - if (Loc.isReg() && LIS.hasInterval(Loc.Kind)) { - LiveInterval *LI = &LIS.getInterval(Loc.Kind); - const VNInfo *VNI = LI->getVNInfoAt(Idx); - extendDef(Idx, LocNo, LI, VNI, LIS, MDT); - } else - extendDef(Idx, LocNo, 0, 0, LIS, MDT); + if (TargetRegisterInfo::isVirtualRegister(Loc.getReg())) { + LiveInterval *LI = nullptr; + const VNInfo *VNI = nullptr; + if (LIS.hasInterval(Loc.getReg())) { + LI = &LIS.getInterval(Loc.getReg()); + VNI = LI->getVNInfoAt(Idx); + } + SmallVector Kills; + extendDef(Idx, LocNo, LI, VNI, &Kills, LIS, MDT, UVS); + if (LI) + addDefsFromCopies(LI, LocNo, Kills, Defs, MRI, LIS); + continue; + } + + // For physregs, use the live range of the first regunit as a guide. + unsigned Unit = *MCRegUnitIterator(Loc.getReg(), &TRI); + LiveRange *LR = &LIS.getRegUnit(Unit); + const VNInfo *VNI = LR->getVNInfoAt(Idx); + // Don't track copies from physregs, it is too expensive. + extendDef(Idx, LocNo, LR, VNI, nullptr, LIS, MDT, UVS); } // Finally, erase all the undefs. @@ -597,27 +687,49 @@ UserValue::computeIntervals(LiveIntervals &LIS, MachineDominatorTree &MDT) { } void LDVImpl::computeIntervals() { - for (unsigned i = 0, e = userValues.size(); i != e; ++i) - userValues[i]->computeIntervals(*LIS, *MDT); + for (unsigned i = 0, e = userValues.size(); i != e; ++i) { + UserValueScopes UVS(userValues[i]->getDebugLoc(), LS); + userValues[i]->computeIntervals(MF->getRegInfo(), *TRI, *LIS, *MDT, UVS); + userValues[i]->mapVirtRegs(this); + } } bool LDVImpl::runOnMachineFunction(MachineFunction &mf) { + clear(); MF = &mf; LIS = &pass.getAnalysis(); MDT = &pass.getAnalysis(); - TRI = mf.getTarget().getRegisterInfo(); - clear(); + TRI = mf.getSubtarget().getRegisterInfo(); + LS.initialize(mf); DEBUG(dbgs() << "********** COMPUTING LIVE DEBUG VARIABLES: " - << ((Value*)mf.getFunction())->getName() - << " **********\n"); + << mf.getName() << " **********\n"); bool Changed = collectDebugValues(mf); computeIntervals(); DEBUG(print(dbgs())); + ModifiedMF = Changed; return Changed; } +static void removeDebugValues(MachineFunction &mf) { + for (MachineBasicBlock &MBB : mf) { + for (auto MBBI = MBB.begin(), MBBE = MBB.end(); MBBI != MBBE; ) { + if (!MBBI->isDebugValue()) { + ++MBBI; + continue; + } + MBBI = MBB.erase(MBBI); + } + } +} + bool LiveDebugVariables::runOnMachineFunction(MachineFunction &mf) { + if (!EnableLDV) + return false; + if (!FunctionDIs.count(mf.getFunction())) { + removeDebugValues(mf); + return false; + } if (!pImpl) pImpl = new LDVImpl(this); return static_cast(pImpl)->runOnMachineFunction(mf); @@ -633,41 +745,143 @@ LiveDebugVariables::~LiveDebugVariables() { delete static_cast(pImpl); } -void UserValue:: -renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx, - const TargetRegisterInfo *TRI) { - for (unsigned i = locations.size(); i; --i) { - unsigned LocNo = i - 1; - Location &Loc = locations[LocNo]; - if (Loc.Kind != OldReg) +//===----------------------------------------------------------------------===// +// Live Range Splitting +//===----------------------------------------------------------------------===// + +bool +UserValue::splitLocation(unsigned OldLocNo, ArrayRef NewRegs, + LiveIntervals& LIS) { + DEBUG({ + dbgs() << "Splitting Loc" << OldLocNo << '\t'; + print(dbgs(), nullptr); + }); + bool DidChange = false; + LocMap::iterator LocMapI; + LocMapI.setMap(locInts); + for (unsigned i = 0; i != NewRegs.size(); ++i) { + LiveInterval *LI = &LIS.getInterval(NewRegs[i]); + if (LI->empty()) continue; - Loc.Kind = NewReg; - if (SubIdx && Loc.Data.SubIdx) - Loc.Data.SubIdx = TRI->composeSubRegIndices(SubIdx, Loc.Data.SubIdx); - coalesceLocation(LocNo); + + // Don't allocate the new LocNo until it is needed. + unsigned NewLocNo = ~0u; + + // Iterate over the overlaps between locInts and LI. + LocMapI.find(LI->beginIndex()); + if (!LocMapI.valid()) + continue; + LiveInterval::iterator LII = LI->advanceTo(LI->begin(), LocMapI.start()); + LiveInterval::iterator LIE = LI->end(); + while (LocMapI.valid() && LII != LIE) { + // At this point, we know that LocMapI.stop() > LII->start. + LII = LI->advanceTo(LII, LocMapI.start()); + if (LII == LIE) + break; + + // Now LII->end > LocMapI.start(). Do we have an overlap? + if (LocMapI.value() == OldLocNo && LII->start < LocMapI.stop()) { + // Overlapping correct location. Allocate NewLocNo now. + if (NewLocNo == ~0u) { + MachineOperand MO = MachineOperand::CreateReg(LI->reg, false); + MO.setSubReg(locations[OldLocNo].getSubReg()); + NewLocNo = getLocationNo(MO); + DidChange = true; + } + + SlotIndex LStart = LocMapI.start(); + SlotIndex LStop = LocMapI.stop(); + + // Trim LocMapI down to the LII overlap. + if (LStart < LII->start) + LocMapI.setStartUnchecked(LII->start); + if (LStop > LII->end) + LocMapI.setStopUnchecked(LII->end); + + // Change the value in the overlap. This may trigger coalescing. + LocMapI.setValue(NewLocNo); + + // Re-insert any removed OldLocNo ranges. + if (LStart < LocMapI.start()) { + LocMapI.insert(LStart, LocMapI.start(), OldLocNo); + ++LocMapI; + assert(LocMapI.valid() && "Unexpected coalescing"); + } + if (LStop > LocMapI.stop()) { + ++LocMapI; + LocMapI.insert(LII->end, LStop, OldLocNo); + --LocMapI; + } + } + + // Advance to the next overlap. + if (LII->end < LocMapI.stop()) { + if (++LII == LIE) + break; + LocMapI.advanceTo(LII->start); + } else { + ++LocMapI; + if (!LocMapI.valid()) + break; + LII = LI->advanceTo(LII, LocMapI.start()); + } + } } + + // Finally, remove any remaining OldLocNo intervals and OldLocNo itself. + locations.erase(locations.begin() + OldLocNo); + LocMapI.goToBegin(); + while (LocMapI.valid()) { + unsigned v = LocMapI.value(); + if (v == OldLocNo) { + DEBUG(dbgs() << "Erasing [" << LocMapI.start() << ';' + << LocMapI.stop() << ")\n"); + LocMapI.erase(); + } else { + if (v > OldLocNo) + LocMapI.setValueUnchecked(v-1); + ++LocMapI; + } + } + + DEBUG({dbgs() << "Split result: \t"; print(dbgs(), nullptr);}); + return DidChange; } -void LDVImpl:: -renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx) { - UserValue *UV = lookupVirtReg(OldReg); - if (!UV) - return; +bool +UserValue::splitRegister(unsigned OldReg, ArrayRef NewRegs, + LiveIntervals &LIS) { + bool DidChange = false; + // Split locations referring to OldReg. Iterate backwards so splitLocation can + // safely erase unused locations. + for (unsigned i = locations.size(); i ; --i) { + unsigned LocNo = i-1; + const MachineOperand *Loc = &locations[LocNo]; + if (!Loc->isReg() || Loc->getReg() != OldReg) + continue; + DidChange |= splitLocation(LocNo, NewRegs, LIS); + } + return DidChange; +} - if (TargetRegisterInfo::isVirtualRegister(NewReg)) - mapVirtReg(NewReg, UV); - virtRegToEqClass.erase(OldReg); +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); - do { - UV->renameRegister(OldReg, NewReg, SubIdx, TRI); - UV = UV->getNext(); - } while (UV); + 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); } void LiveDebugVariables:: -renameRegister(unsigned OldReg, unsigned NewReg, unsigned SubIdx) { +splitRegister(unsigned OldReg, ArrayRef NewRegs, LiveIntervals &LIS) { if (pImpl) - static_cast(pImpl)->renameRegister(OldReg, NewReg, SubIdx); + static_cast(pImpl)->splitRegister(OldReg, NewRegs); } void @@ -675,33 +889,33 @@ 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; - Location &Loc = locations[LocNo]; + MachineOperand &Loc = locations[LocNo]; // Only virtual registers are rewritten. - if (!Loc.isReg() || !TargetRegisterInfo::isVirtualRegister(Loc.Kind)) + if (!Loc.isReg() || !Loc.getReg() || + !TargetRegisterInfo::isVirtualRegister(Loc.getReg())) continue; - unsigned VirtReg = Loc.Kind; - if (VRM.isAssignedReg(VirtReg)) { - unsigned PhysReg = VRM.getPhys(VirtReg); - if (Loc.Data.SubIdx) - PhysReg = TRI.getSubReg(PhysReg, Loc.Data.SubIdx); - Loc.Kind = PhysReg; - Loc.Data.SubIdx = 0; + 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) { - Loc.Kind = ~VRM.getStackSlot(VirtReg); // FIXME: Translate SubIdx to a stackslot offset. - Loc.Data.Offset = 0; + Loc = MachineOperand::CreateFI(VRM.getStackSlot(VirtReg)); } else { - Loc.Kind = Location::locUndef; + Loc.setReg(0); + Loc.setSubReg(0); } coalesceLocation(LocNo); } - DEBUG(print(dbgs(), &TRI)); } -/// findInsertLocation - Find an iterator and DebugLoc for inserting a DBG_VALUE +/// findInsertLocation - Find an iterator for inserting a DBG_VALUE /// instruction. static MachineBasicBlock::iterator -findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx, DebugLoc &DL, +findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx, LiveIntervals &LIS) { SlotIndex Start = LIS.getMBBStartIdx(MBB); Idx = Idx.getBaseIndex(); @@ -712,46 +926,35 @@ findInsertLocation(MachineBasicBlock *MBB, SlotIndex Idx, DebugLoc &DL, // We've reached the beginning of MBB. if (Idx == Start) { MachineBasicBlock::iterator I = MBB->SkipPHIsAndLabels(MBB->begin()); - if (I != MBB->end()) - DL = I->getDebugLoc(); return I; } Idx = Idx.getPrevIndex(); } - // We found an instruction. The insert point is after the instr. - DL = MI->getDebugLoc(); - return llvm::next(MachineBasicBlock::iterator(MI)); + + // Don't insert anything after the first terminator, though. + return MI->isTerminator() ? MBB->getFirstTerminator() : + std::next(MachineBasicBlock::iterator(MI)); } +DebugLoc UserValue::findDebugLoc() { + DebugLoc D = dl; + dl = DebugLoc(); + return D; +} void UserValue::insertDebugValue(MachineBasicBlock *MBB, SlotIndex Idx, unsigned LocNo, LiveIntervals &LIS, const TargetInstrInfo &TII) { - DebugLoc DL; - MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, DL, LIS); - Location &Loc = locations[LocNo]; - - // Frame index locations may require a target callback. - if (Loc.isFrameIndex()) { - MachineInstr *MI = TII.emitFrameIndexDebugValue(*MBB->getParent(), - Loc.getFrameIndex(), - offset, variable, DL); - if (MI) { - MBB->insert(I, MI); - return; - } - } - // This is not a frame index, or the target is happy with a standard FI. - Loc.addOperand(BuildMI(*MBB, I, DL, TII.get(TargetOpcode::DBG_VALUE))) - .addImm(offset).addMetadata(variable); -} - -void UserValue::insertDebugKill(MachineBasicBlock *MBB, SlotIndex Idx, - LiveIntervals &LIS, const TargetInstrInfo &TII) { - DebugLoc DL; - MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, DL, LIS); - BuildMI(*MBB, I, DL, TII.get(TargetOpcode::DBG_VALUE)).addReg(0) - .addImm(offset).addMetadata(variable); + MachineBasicBlock::iterator I = findInsertLocation(MBB, Idx, LIS); + MachineOperand &Loc = locations[LocNo]; + ++NumInsertedDebugValues; + + if (Loc.isReg()) + BuildMI(*MBB, I, findDebugLoc(), TII.get(TargetOpcode::DBG_VALUE), + IsIndirect, Loc.getReg(), offset, variable); + else + BuildMI(*MBB, I, findDebugLoc(), TII.get(TargetOpcode::DBG_VALUE)) + .addOperand(Loc).addImm(offset).addMetadata(variable); } void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS, @@ -768,7 +971,6 @@ void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS, DEBUG(dbgs() << " BB#" << MBB->getNumber() << '-' << MBBEnd); insertDebugValue(MBB, Start, LocNo, LIS, TII); - // This interval may span multiple basic blocks. // Insert a DBG_VALUE into each one. while(Stop > MBBEnd) { @@ -785,22 +987,20 @@ void UserValue::emitDebugValues(VirtRegMap *VRM, LiveIntervals &LIS, break; ++I; - if (Stop == MBBEnd) - continue; - // The current interval ends before MBB. - // Insert a kill if there is a gap. - if (!I.valid() || I.start() > Stop) - insertDebugKill(MBB, Stop, LIS, TII); } } void LDVImpl::emitDebugValues(VirtRegMap *VRM) { DEBUG(dbgs() << "********** EMITTING LIVE DEBUG VARIABLES **********\n"); - const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); + if (!MF) + return; + const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo(); for (unsigned i = 0, e = userValues.size(); i != e; ++i) { + DEBUG(userValues[i]->print(dbgs(), &MF->getTarget())); userValues[i]->rewriteLocations(*VRM, *TRI); userValues[i]->emitDebugValues(VRM, *LIS, *TII); } + EmitDone = true; } void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) { @@ -808,6 +1008,10 @@ void LiveDebugVariables::emitDebugValues(VirtRegMap *VRM) { static_cast(pImpl)->emitDebugValues(VRM); } +bool LiveDebugVariables::doInitialization(Module &M) { + FunctionDIs = makeSubprogramMap(M); + return Pass::doInitialization(M); +} #ifndef NDEBUG void LiveDebugVariables::dump() { @@ -815,4 +1019,3 @@ void LiveDebugVariables::dump() { static_cast(pImpl)->print(dbgs()); } #endif -