| //===- VarLocBasedImpl.cpp - Tracking Debug Value MIs with VarLoc class----===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| /// |
| /// \file VarLocBasedImpl.cpp |
| /// |
| /// LiveDebugValues is an optimistic "available expressions" dataflow |
| /// algorithm. The set of expressions is the set of machine locations |
| /// (registers, spill slots, constants) that a variable fragment might be |
| /// located, qualified by a DIExpression and indirect-ness flag, while each |
| /// variable is identified by a DebugVariable object. The availability of an |
| /// expression begins when a DBG_VALUE instruction specifies the location of a |
| /// DebugVariable, and continues until that location is clobbered or |
| /// re-specified by a different DBG_VALUE for the same DebugVariable. |
| /// |
| /// The output of LiveDebugValues is additional DBG_VALUE instructions, |
| /// placed to extend variable locations as far they're available. This file |
| /// and the VarLocBasedLDV class is an implementation that explicitly tracks |
| /// locations, using the VarLoc class. |
| /// |
| /// The canonical "available expressions" problem doesn't have expression |
| /// clobbering, instead when a variable is re-assigned, any expressions using |
| /// that variable get invalidated. LiveDebugValues can map onto "available |
| /// expressions" by having every register represented by a variable, which is |
| /// used in an expression that becomes available at a DBG_VALUE instruction. |
| /// When the register is clobbered, its variable is effectively reassigned, and |
| /// expressions computed from it become unavailable. A similar construct is |
| /// needed when a DebugVariable has its location re-specified, to invalidate |
| /// all other locations for that DebugVariable. |
| /// |
| /// Using the dataflow analysis to compute the available expressions, we create |
| /// a DBG_VALUE at the beginning of each block where the expression is |
| /// live-in. This propagates variable locations into every basic block where |
| /// the location can be determined, rather than only having DBG_VALUEs in blocks |
| /// where locations are specified due to an assignment or some optimization. |
| /// Movements of values between registers and spill slots are annotated with |
| /// DBG_VALUEs too to track variable values bewteen locations. All this allows |
| /// DbgEntityHistoryCalculator to focus on only the locations within individual |
| /// blocks, facilitating testing and improving modularity. |
| /// |
| /// We follow an optimisic dataflow approach, with this lattice: |
| /// |
| /// \verbatim |
| /// ┬ "Unknown" |
| /// | |
| /// v |
| /// True |
| /// | |
| /// v |
| /// ⊥ False |
| /// \endverbatim With "True" signifying that the expression is available (and |
| /// thus a DebugVariable's location is the corresponding register), while |
| /// "False" signifies that the expression is unavailable. "Unknown"s never |
| /// survive to the end of the analysis (see below). |
| /// |
| /// Formally, all DebugVariable locations that are live-out of a block are |
| /// initialized to \top. A blocks live-in values take the meet of the lattice |
| /// value for every predecessors live-outs, except for the entry block, where |
| /// all live-ins are \bot. The usual dataflow propagation occurs: the transfer |
| /// function for a block assigns an expression for a DebugVariable to be "True" |
| /// if a DBG_VALUE in the block specifies it; "False" if the location is |
| /// clobbered; or the live-in value if it is unaffected by the block. We |
| /// visit each block in reverse post order until a fixedpoint is reached. The |
| /// solution produced is maximal. |
| /// |
| /// Intuitively, we start by assuming that every expression / variable location |
| /// is at least "True", and then propagate "False" from the entry block and any |
| /// clobbers until there are no more changes to make. This gives us an accurate |
| /// solution because all incorrect locations will have a "False" propagated into |
| /// them. It also gives us a solution that copes well with loops by assuming |
| /// that variable locations are live-through every loop, and then removing those |
| /// that are not through dataflow. |
| /// |
| /// Within LiveDebugValues: each variable location is represented by a |
| /// VarLoc object that identifies the source variable, its current |
| /// machine-location, and the DBG_VALUE inst that specifies the location. Each |
| /// VarLoc is indexed in the (function-scope) \p VarLocMap, giving each VarLoc a |
| /// unique index. Rather than operate directly on machine locations, the |
| /// dataflow analysis in this pass identifies locations by their index in the |
| /// VarLocMap, meaning all the variable locations in a block can be described |
| /// by a sparse vector of VarLocMap indicies. |
| /// |
| /// All the storage for the dataflow analysis is local to the ExtendRanges |
| /// method and passed down to helper methods. "OutLocs" and "InLocs" record the |
| /// in and out lattice values for each block. "OpenRanges" maintains a list of |
| /// variable locations and, with the "process" method, evaluates the transfer |
| /// function of each block. "flushPendingLocs" installs DBG_VALUEs for each |
| /// live-in location at the start of blocks, while "Transfers" records |
| /// transfers of values between machine-locations. |
| /// |
| /// We avoid explicitly representing the "Unknown" (\top) lattice value in the |
| /// implementation. Instead, unvisited blocks implicitly have all lattice |
| /// values set as "Unknown". After being visited, there will be path back to |
| /// the entry block where the lattice value is "False", and as the transfer |
| /// function cannot make new "Unknown" locations, there are no scenarios where |
| /// a block can have an "Unknown" location after being visited. Similarly, we |
| /// don't enumerate all possible variable locations before exploring the |
| /// function: when a new location is discovered, all blocks previously explored |
| /// were implicitly "False" but unrecorded, and become explicitly "False" when |
| /// a new VarLoc is created with its bit not set in predecessor InLocs or |
| /// OutLocs. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #include "LiveDebugValues.h" |
| |
| #include "llvm/ADT/CoalescingBitVector.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/PostOrderIterator.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/ADT/UniqueVector.h" |
| #include "llvm/CodeGen/LexicalScopes.h" |
| #include "llvm/CodeGen/MachineBasicBlock.h" |
| #include "llvm/CodeGen/MachineFrameInfo.h" |
| #include "llvm/CodeGen/MachineFunction.h" |
| #include "llvm/CodeGen/MachineFunctionPass.h" |
| #include "llvm/CodeGen/MachineInstr.h" |
| #include "llvm/CodeGen/MachineInstrBuilder.h" |
| #include "llvm/CodeGen/MachineMemOperand.h" |
| #include "llvm/CodeGen/MachineOperand.h" |
| #include "llvm/CodeGen/PseudoSourceValue.h" |
| #include "llvm/CodeGen/RegisterScavenging.h" |
| #include "llvm/CodeGen/TargetFrameLowering.h" |
| #include "llvm/CodeGen/TargetInstrInfo.h" |
| #include "llvm/CodeGen/TargetLowering.h" |
| #include "llvm/CodeGen/TargetPassConfig.h" |
| #include "llvm/CodeGen/TargetRegisterInfo.h" |
| #include "llvm/CodeGen/TargetSubtargetInfo.h" |
| #include "llvm/Config/llvm-config.h" |
| #include "llvm/IR/DIBuilder.h" |
| #include "llvm/IR/DebugInfoMetadata.h" |
| #include "llvm/IR/DebugLoc.h" |
| #include "llvm/IR/Function.h" |
| #include "llvm/IR/Module.h" |
| #include "llvm/InitializePasses.h" |
| #include "llvm/MC/MCRegisterInfo.h" |
| #include "llvm/Pass.h" |
| #include "llvm/Support/Casting.h" |
| #include "llvm/Support/Compiler.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/TypeSize.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include "llvm/Target/TargetMachine.h" |
| #include <algorithm> |
| #include <cassert> |
| #include <cstdint> |
| #include <functional> |
| #include <queue> |
| #include <tuple> |
| #include <utility> |
| #include <vector> |
| |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "livedebugvalues" |
| |
| STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted"); |
| |
| // Options to prevent pathological compile-time behavior. If InputBBLimit and |
| // InputDbgValueLimit are both exceeded, range extension is disabled. |
| static cl::opt<unsigned> InputBBLimit( |
| "livedebugvalues-input-bb-limit", |
| cl::desc("Maximum input basic blocks before DBG_VALUE limit applies"), |
| cl::init(10000), cl::Hidden); |
| static cl::opt<unsigned> InputDbgValueLimit( |
| "livedebugvalues-input-dbg-value-limit", |
| cl::desc( |
| "Maximum input DBG_VALUE insts supported by debug range extension"), |
| cl::init(50000), cl::Hidden); |
| |
| // If @MI is a DBG_VALUE with debug value described by a defined |
| // register, returns the number of this register. In the other case, returns 0. |
| static Register isDbgValueDescribedByReg(const MachineInstr &MI) { |
| assert(MI.isDebugValue() && "expected a DBG_VALUE"); |
| assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); |
| // If location of variable is described using a register (directly |
| // or indirectly), this register is always a first operand. |
| return MI.getDebugOperand(0).isReg() ? MI.getDebugOperand(0).getReg() |
| : Register(); |
| } |
| |
| /// If \p Op is a stack or frame register return true, otherwise return false. |
| /// This is used to avoid basing the debug entry values on the registers, since |
| /// we do not support it at the moment. |
| static bool isRegOtherThanSPAndFP(const MachineOperand &Op, |
| const MachineInstr &MI, |
| const TargetRegisterInfo *TRI) { |
| if (!Op.isReg()) |
| return false; |
| |
| const MachineFunction *MF = MI.getParent()->getParent(); |
| const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); |
| Register SP = TLI->getStackPointerRegisterToSaveRestore(); |
| Register FP = TRI->getFrameRegister(*MF); |
| Register Reg = Op.getReg(); |
| |
| return Reg && Reg != SP && Reg != FP; |
| } |
| |
| namespace { |
| |
| // Max out the number of statically allocated elements in DefinedRegsSet, as |
| // this prevents fallback to std::set::count() operations. |
| using DefinedRegsSet = SmallSet<Register, 32>; |
| |
| using VarLocSet = CoalescingBitVector<uint64_t>; |
| |
| /// A type-checked pair of {Register Location (or 0), Index}, used to index |
| /// into a \ref VarLocMap. This can be efficiently converted to a 64-bit int |
| /// for insertion into a \ref VarLocSet, and efficiently converted back. The |
| /// type-checker helps ensure that the conversions aren't lossy. |
| /// |
| /// Why encode a location /into/ the VarLocMap index? This makes it possible |
| /// to find the open VarLocs killed by a register def very quickly. This is a |
| /// performance-critical operation for LiveDebugValues. |
| struct LocIndex { |
| using u32_location_t = uint32_t; |
| using u32_index_t = uint32_t; |
| |
| u32_location_t Location; // Physical registers live in the range [1;2^30) (see |
| // \ref MCRegister), so we have plenty of range left |
| // here to encode non-register locations. |
| u32_index_t Index; |
| |
| /// The first location greater than 0 that is not reserved for VarLocs of |
| /// kind RegisterKind. |
| static constexpr u32_location_t kFirstInvalidRegLocation = 1 << 30; |
| |
| /// A special location reserved for VarLocs of kind SpillLocKind. |
| static constexpr u32_location_t kSpillLocation = kFirstInvalidRegLocation; |
| |
| /// A special location reserved for VarLocs of kind EntryValueBackupKind and |
| /// EntryValueCopyBackupKind. |
| static constexpr u32_location_t kEntryValueBackupLocation = |
| kFirstInvalidRegLocation + 1; |
| |
| LocIndex(u32_location_t Location, u32_index_t Index) |
| : Location(Location), Index(Index) {} |
| |
| uint64_t getAsRawInteger() const { |
| return (static_cast<uint64_t>(Location) << 32) | Index; |
| } |
| |
| template<typename IntT> static LocIndex fromRawInteger(IntT ID) { |
| static_assert(std::is_unsigned<IntT>::value && |
| sizeof(ID) == sizeof(uint64_t), |
| "Cannot convert raw integer to LocIndex"); |
| return {static_cast<u32_location_t>(ID >> 32), |
| static_cast<u32_index_t>(ID)}; |
| } |
| |
| /// Get the start of the interval reserved for VarLocs of kind RegisterKind |
| /// which reside in \p Reg. The end is at rawIndexForReg(Reg+1)-1. |
| static uint64_t rawIndexForReg(uint32_t Reg) { |
| return LocIndex(Reg, 0).getAsRawInteger(); |
| } |
| |
| /// Return a range covering all set indices in the interval reserved for |
| /// \p Location in \p Set. |
| static auto indexRangeForLocation(const VarLocSet &Set, |
| u32_location_t Location) { |
| uint64_t Start = LocIndex(Location, 0).getAsRawInteger(); |
| uint64_t End = LocIndex(Location + 1, 0).getAsRawInteger(); |
| return Set.half_open_range(Start, End); |
| } |
| }; |
| |
| class VarLocBasedLDV : public LDVImpl { |
| private: |
| const TargetRegisterInfo *TRI; |
| const TargetInstrInfo *TII; |
| const TargetFrameLowering *TFI; |
| TargetPassConfig *TPC; |
| BitVector CalleeSavedRegs; |
| LexicalScopes LS; |
| VarLocSet::Allocator Alloc; |
| |
| enum struct TransferKind { TransferCopy, TransferSpill, TransferRestore }; |
| |
| using FragmentInfo = DIExpression::FragmentInfo; |
| using OptFragmentInfo = Optional<DIExpression::FragmentInfo>; |
| |
| /// A pair of debug variable and value location. |
| struct VarLoc { |
| // The location at which a spilled variable resides. It consists of a |
| // register and an offset. |
| struct SpillLoc { |
| unsigned SpillBase; |
| StackOffset SpillOffset; |
| bool operator==(const SpillLoc &Other) const { |
| return SpillBase == Other.SpillBase && SpillOffset == Other.SpillOffset; |
| } |
| bool operator!=(const SpillLoc &Other) const { |
| return !(*this == Other); |
| } |
| }; |
| |
| /// Identity of the variable at this location. |
| const DebugVariable Var; |
| |
| /// The expression applied to this location. |
| const DIExpression *Expr; |
| |
| /// DBG_VALUE to clone var/expr information from if this location |
| /// is moved. |
| const MachineInstr &MI; |
| |
| enum VarLocKind { |
| InvalidKind = 0, |
| RegisterKind, |
| SpillLocKind, |
| ImmediateKind, |
| EntryValueKind, |
| EntryValueBackupKind, |
| EntryValueCopyBackupKind |
| } Kind = InvalidKind; |
| |
| /// The value location. Stored separately to avoid repeatedly |
| /// extracting it from MI. |
| union LocUnion { |
| uint64_t RegNo; |
| SpillLoc SpillLocation; |
| uint64_t Hash; |
| int64_t Immediate; |
| const ConstantFP *FPImm; |
| const ConstantInt *CImm; |
| LocUnion() : Hash(0) {} |
| } Loc; |
| |
| VarLoc(const MachineInstr &MI, LexicalScopes &LS) |
| : Var(MI.getDebugVariable(), MI.getDebugExpression(), |
| MI.getDebugLoc()->getInlinedAt()), |
| Expr(MI.getDebugExpression()), MI(MI) { |
| assert(MI.isDebugValue() && "not a DBG_VALUE"); |
| assert(MI.getNumOperands() == 4 && "malformed DBG_VALUE"); |
| if (int RegNo = isDbgValueDescribedByReg(MI)) { |
| Kind = RegisterKind; |
| Loc.RegNo = RegNo; |
| } else if (MI.getDebugOperand(0).isImm()) { |
| Kind = ImmediateKind; |
| Loc.Immediate = MI.getDebugOperand(0).getImm(); |
| } else if (MI.getDebugOperand(0).isFPImm()) { |
| Kind = ImmediateKind; |
| Loc.FPImm = MI.getDebugOperand(0).getFPImm(); |
| } else if (MI.getDebugOperand(0).isCImm()) { |
| Kind = ImmediateKind; |
| Loc.CImm = MI.getDebugOperand(0).getCImm(); |
| } |
| |
| // We create the debug entry values from the factory functions rather than |
| // from this ctor. |
| assert(Kind != EntryValueKind && !isEntryBackupLoc()); |
| } |
| |
| /// Take the variable and machine-location in DBG_VALUE MI, and build an |
| /// entry location using the given expression. |
| static VarLoc CreateEntryLoc(const MachineInstr &MI, LexicalScopes &LS, |
| const DIExpression *EntryExpr, Register Reg) { |
| VarLoc VL(MI, LS); |
| assert(VL.Kind == RegisterKind); |
| VL.Kind = EntryValueKind; |
| VL.Expr = EntryExpr; |
| VL.Loc.RegNo = Reg; |
| return VL; |
| } |
| |
| /// Take the variable and machine-location from the DBG_VALUE (from the |
| /// function entry), and build an entry value backup location. The backup |
| /// location will turn into the normal location if the backup is valid at |
| /// the time of the primary location clobbering. |
| static VarLoc CreateEntryBackupLoc(const MachineInstr &MI, |
| LexicalScopes &LS, |
| const DIExpression *EntryExpr) { |
| VarLoc VL(MI, LS); |
| assert(VL.Kind == RegisterKind); |
| VL.Kind = EntryValueBackupKind; |
| VL.Expr = EntryExpr; |
| return VL; |
| } |
| |
| /// Take the variable and machine-location from the DBG_VALUE (from the |
| /// function entry), and build a copy of an entry value backup location by |
| /// setting the register location to NewReg. |
| static VarLoc CreateEntryCopyBackupLoc(const MachineInstr &MI, |
| LexicalScopes &LS, |
| const DIExpression *EntryExpr, |
| Register NewReg) { |
| VarLoc VL(MI, LS); |
| assert(VL.Kind == RegisterKind); |
| VL.Kind = EntryValueCopyBackupKind; |
| VL.Expr = EntryExpr; |
| VL.Loc.RegNo = NewReg; |
| return VL; |
| } |
| |
| /// Copy the register location in DBG_VALUE MI, updating the register to |
| /// be NewReg. |
| static VarLoc CreateCopyLoc(const MachineInstr &MI, LexicalScopes &LS, |
| Register NewReg) { |
| VarLoc VL(MI, LS); |
| assert(VL.Kind == RegisterKind); |
| VL.Loc.RegNo = NewReg; |
| return VL; |
| } |
| |
| /// Take the variable described by DBG_VALUE MI, and create a VarLoc |
| /// locating it in the specified spill location. |
| static VarLoc CreateSpillLoc(const MachineInstr &MI, unsigned SpillBase, |
| StackOffset SpillOffset, LexicalScopes &LS) { |
| VarLoc VL(MI, LS); |
| assert(VL.Kind == RegisterKind); |
| VL.Kind = SpillLocKind; |
| VL.Loc.SpillLocation = {SpillBase, SpillOffset}; |
| return VL; |
| } |
| |
| /// Create a DBG_VALUE representing this VarLoc in the given function. |
| /// Copies variable-specific information such as DILocalVariable and |
| /// inlining information from the original DBG_VALUE instruction, which may |
| /// have been several transfers ago. |
| MachineInstr *BuildDbgValue(MachineFunction &MF) const { |
| const DebugLoc &DbgLoc = MI.getDebugLoc(); |
| bool Indirect = MI.isIndirectDebugValue(); |
| const auto &IID = MI.getDesc(); |
| const DILocalVariable *Var = MI.getDebugVariable(); |
| const DIExpression *DIExpr = MI.getDebugExpression(); |
| NumInserted++; |
| |
| switch (Kind) { |
| case EntryValueKind: |
| // An entry value is a register location -- but with an updated |
| // expression. The register location of such DBG_VALUE is always the one |
| // from the entry DBG_VALUE, it does not matter if the entry value was |
| // copied in to another register due to some optimizations. |
| return BuildMI(MF, DbgLoc, IID, Indirect, |
| MI.getDebugOperand(0).getReg(), Var, Expr); |
| case RegisterKind: |
| // Register locations are like the source DBG_VALUE, but with the |
| // register number from this VarLoc. |
| return BuildMI(MF, DbgLoc, IID, Indirect, Loc.RegNo, Var, DIExpr); |
| case SpillLocKind: { |
| // Spills are indirect DBG_VALUEs, with a base register and offset. |
| // Use the original DBG_VALUEs expression to build the spilt location |
| // on top of. FIXME: spill locations created before this pass runs |
| // are not recognized, and not handled here. |
| auto *TRI = MF.getSubtarget().getRegisterInfo(); |
| auto *SpillExpr = TRI->prependOffsetExpression( |
| DIExpr, DIExpression::ApplyOffset, Loc.SpillLocation.SpillOffset); |
| unsigned Base = Loc.SpillLocation.SpillBase; |
| return BuildMI(MF, DbgLoc, IID, true, Base, Var, SpillExpr); |
| } |
| case ImmediateKind: { |
| MachineOperand MO = MI.getDebugOperand(0); |
| return BuildMI(MF, DbgLoc, IID, Indirect, MO, Var, DIExpr); |
| } |
| case EntryValueBackupKind: |
| case EntryValueCopyBackupKind: |
| case InvalidKind: |
| llvm_unreachable( |
| "Tried to produce DBG_VALUE for invalid or backup VarLoc"); |
| } |
| llvm_unreachable("Unrecognized VarLocBasedLDV.VarLoc.Kind enum"); |
| } |
| |
| /// Is the Loc field a constant or constant object? |
| bool isConstant() const { return Kind == ImmediateKind; } |
| |
| /// Check if the Loc field is an entry backup location. |
| bool isEntryBackupLoc() const { |
| return Kind == EntryValueBackupKind || Kind == EntryValueCopyBackupKind; |
| } |
| |
| /// If this variable is described by a register holding the entry value, |
| /// return it, otherwise return 0. |
| unsigned getEntryValueBackupReg() const { |
| if (Kind == EntryValueBackupKind) |
| return Loc.RegNo; |
| return 0; |
| } |
| |
| /// If this variable is described by a register holding the copy of the |
| /// entry value, return it, otherwise return 0. |
| unsigned getEntryValueCopyBackupReg() const { |
| if (Kind == EntryValueCopyBackupKind) |
| return Loc.RegNo; |
| return 0; |
| } |
| |
| /// If this variable is described by a register, return it, |
| /// otherwise return 0. |
| unsigned isDescribedByReg() const { |
| if (Kind == RegisterKind) |
| return Loc.RegNo; |
| return 0; |
| } |
| |
| /// Determine whether the lexical scope of this value's debug location |
| /// dominates MBB. |
| bool dominates(LexicalScopes &LS, MachineBasicBlock &MBB) const { |
| return LS.dominates(MI.getDebugLoc().get(), &MBB); |
| } |
| |
| #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
| // TRI can be null. |
| void dump(const TargetRegisterInfo *TRI, raw_ostream &Out = dbgs()) const { |
| Out << "VarLoc("; |
| switch (Kind) { |
| case RegisterKind: |
| case EntryValueKind: |
| case EntryValueBackupKind: |
| case EntryValueCopyBackupKind: |
| Out << printReg(Loc.RegNo, TRI); |
| break; |
| case SpillLocKind: |
| Out << printReg(Loc.SpillLocation.SpillBase, TRI); |
| Out << "[" << Loc.SpillLocation.SpillOffset.getFixed() << " + " |
| << Loc.SpillLocation.SpillOffset.getScalable() << "x vscale" |
| << "]"; |
| break; |
| case ImmediateKind: |
| Out << Loc.Immediate; |
| break; |
| case InvalidKind: |
| llvm_unreachable("Invalid VarLoc in dump method"); |
| } |
| |
| Out << ", \"" << Var.getVariable()->getName() << "\", " << *Expr << ", "; |
| if (Var.getInlinedAt()) |
| Out << "!" << Var.getInlinedAt()->getMetadataID() << ")\n"; |
| else |
| Out << "(null))"; |
| |
| if (isEntryBackupLoc()) |
| Out << " (backup loc)\n"; |
| else |
| Out << "\n"; |
| } |
| #endif |
| |
| bool operator==(const VarLoc &Other) const { |
| if (Kind != Other.Kind || !(Var == Other.Var) || Expr != Other.Expr) |
| return false; |
| |
| switch (Kind) { |
| case SpillLocKind: |
| return Loc.SpillLocation == Other.Loc.SpillLocation; |
| case RegisterKind: |
| case ImmediateKind: |
| case EntryValueKind: |
| case EntryValueBackupKind: |
| case EntryValueCopyBackupKind: |
| return Loc.Hash == Other.Loc.Hash; |
| default: |
| llvm_unreachable("Invalid kind"); |
| } |
| } |
| |
| /// This operator guarantees that VarLocs are sorted by Variable first. |
| bool operator<(const VarLoc &Other) const { |
| switch (Kind) { |
| case SpillLocKind: |
| return std::make_tuple(Var, Kind, Loc.SpillLocation.SpillBase, |
| Loc.SpillLocation.SpillOffset.getFixed(), |
| Loc.SpillLocation.SpillOffset.getScalable(), |
| Expr) < |
| std::make_tuple( |
| Other.Var, Other.Kind, Other.Loc.SpillLocation.SpillBase, |
| Other.Loc.SpillLocation.SpillOffset.getFixed(), |
| Other.Loc.SpillLocation.SpillOffset.getScalable(), |
| Other.Expr); |
| case RegisterKind: |
| case ImmediateKind: |
| case EntryValueKind: |
| case EntryValueBackupKind: |
| case EntryValueCopyBackupKind: |
| return std::tie(Var, Kind, Loc.Hash, Expr) < |
| std::tie(Other.Var, Other.Kind, Other.Loc.Hash, Other.Expr); |
| default: |
| llvm_unreachable("Invalid kind"); |
| } |
| } |
| }; |
| |
| /// VarLocMap is used for two things: |
| /// 1) Assigning a unique LocIndex to a VarLoc. This LocIndex can be used to |
| /// virtually insert a VarLoc into a VarLocSet. |
| /// 2) Given a LocIndex, look up the unique associated VarLoc. |
| class VarLocMap { |
| /// Map a VarLoc to an index within the vector reserved for its location |
| /// within Loc2Vars. |
| std::map<VarLoc, LocIndex::u32_index_t> Var2Index; |
| |
| /// Map a location to a vector which holds VarLocs which live in that |
| /// location. |
| SmallDenseMap<LocIndex::u32_location_t, std::vector<VarLoc>> Loc2Vars; |
| |
| /// Determine the 32-bit location reserved for \p VL, based on its kind. |
| static LocIndex::u32_location_t getLocationForVar(const VarLoc &VL) { |
| switch (VL.Kind) { |
| case VarLoc::RegisterKind: |
| assert((VL.Loc.RegNo < LocIndex::kFirstInvalidRegLocation) && |
| "Physreg out of range?"); |
| return VL.Loc.RegNo; |
| case VarLoc::SpillLocKind: |
| return LocIndex::kSpillLocation; |
| case VarLoc::EntryValueBackupKind: |
| case VarLoc::EntryValueCopyBackupKind: |
| return LocIndex::kEntryValueBackupLocation; |
| default: |
| return 0; |
| } |
| } |
| |
| public: |
| /// Retrieve a unique LocIndex for \p VL. |
| LocIndex insert(const VarLoc &VL) { |
| LocIndex::u32_location_t Location = getLocationForVar(VL); |
| LocIndex::u32_index_t &Index = Var2Index[VL]; |
| if (!Index) { |
| auto &Vars = Loc2Vars[Location]; |
| Vars.push_back(VL); |
| Index = Vars.size(); |
| } |
| return {Location, Index - 1}; |
| } |
| |
| /// Retrieve the unique VarLoc associated with \p ID. |
| const VarLoc &operator[](LocIndex ID) const { |
| auto LocIt = Loc2Vars.find(ID.Location); |
| assert(LocIt != Loc2Vars.end() && "Location not tracked"); |
| return LocIt->second[ID.Index]; |
| } |
| }; |
| |
| using VarLocInMBB = |
| SmallDenseMap<const MachineBasicBlock *, std::unique_ptr<VarLocSet>>; |
| struct TransferDebugPair { |
| MachineInstr *TransferInst; ///< Instruction where this transfer occurs. |
| LocIndex LocationID; ///< Location number for the transfer dest. |
| }; |
| using TransferMap = SmallVector<TransferDebugPair, 4>; |
| |
| // Types for recording sets of variable fragments that overlap. For a given |
| // local variable, we record all other fragments of that variable that could |
| // overlap it, to reduce search time. |
| using FragmentOfVar = |
| std::pair<const DILocalVariable *, DIExpression::FragmentInfo>; |
| using OverlapMap = |
| DenseMap<FragmentOfVar, SmallVector<DIExpression::FragmentInfo, 1>>; |
| |
| // Helper while building OverlapMap, a map of all fragments seen for a given |
| // DILocalVariable. |
| using VarToFragments = |
| DenseMap<const DILocalVariable *, SmallSet<FragmentInfo, 4>>; |
| |
| /// This holds the working set of currently open ranges. For fast |
| /// access, this is done both as a set of VarLocIDs, and a map of |
| /// DebugVariable to recent VarLocID. Note that a DBG_VALUE ends all |
| /// previous open ranges for the same variable. In addition, we keep |
| /// two different maps (Vars/EntryValuesBackupVars), so erase/insert |
| /// methods act differently depending on whether a VarLoc is primary |
| /// location or backup one. In the case the VarLoc is backup location |
| /// we will erase/insert from the EntryValuesBackupVars map, otherwise |
| /// we perform the operation on the Vars. |
| class OpenRangesSet { |
| VarLocSet VarLocs; |
| // Map the DebugVariable to recent primary location ID. |
| SmallDenseMap<DebugVariable, LocIndex, 8> Vars; |
| // Map the DebugVariable to recent backup location ID. |
| SmallDenseMap<DebugVariable, LocIndex, 8> EntryValuesBackupVars; |
| OverlapMap &OverlappingFragments; |
| |
| public: |
| OpenRangesSet(VarLocSet::Allocator &Alloc, OverlapMap &_OLapMap) |
| : VarLocs(Alloc), OverlappingFragments(_OLapMap) {} |
| |
| const VarLocSet &getVarLocs() const { return VarLocs; } |
| |
| /// Terminate all open ranges for VL.Var by removing it from the set. |
| void erase(const VarLoc &VL); |
| |
| /// Terminate all open ranges listed in \c KillSet by removing |
| /// them from the set. |
| void erase(const VarLocSet &KillSet, const VarLocMap &VarLocIDs); |
| |
| /// Insert a new range into the set. |
| void insert(LocIndex VarLocID, const VarLoc &VL); |
| |
| /// Insert a set of ranges. |
| void insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map) { |
| for (uint64_t ID : ToLoad) { |
| LocIndex Idx = LocIndex::fromRawInteger(ID); |
| const VarLoc &VarL = Map[Idx]; |
| insert(Idx, VarL); |
| } |
| } |
| |
| llvm::Optional<LocIndex> getEntryValueBackup(DebugVariable Var); |
| |
| /// Empty the set. |
| void clear() { |
| VarLocs.clear(); |
| Vars.clear(); |
| EntryValuesBackupVars.clear(); |
| } |
| |
| /// Return whether the set is empty or not. |
| bool empty() const { |
| assert(Vars.empty() == EntryValuesBackupVars.empty() && |
| Vars.empty() == VarLocs.empty() && |
| "open ranges are inconsistent"); |
| return VarLocs.empty(); |
| } |
| |
| /// Get an empty range of VarLoc IDs. |
| auto getEmptyVarLocRange() const { |
| return iterator_range<VarLocSet::const_iterator>(getVarLocs().end(), |
| getVarLocs().end()); |
| } |
| |
| /// Get all set IDs for VarLocs of kind RegisterKind in \p Reg. |
| auto getRegisterVarLocs(Register Reg) const { |
| return LocIndex::indexRangeForLocation(getVarLocs(), Reg); |
| } |
| |
| /// Get all set IDs for VarLocs of kind SpillLocKind. |
| auto getSpillVarLocs() const { |
| return LocIndex::indexRangeForLocation(getVarLocs(), |
| LocIndex::kSpillLocation); |
| } |
| |
| /// Get all set IDs for VarLocs of kind EntryValueBackupKind or |
| /// EntryValueCopyBackupKind. |
| auto getEntryValueBackupVarLocs() const { |
| return LocIndex::indexRangeForLocation( |
| getVarLocs(), LocIndex::kEntryValueBackupLocation); |
| } |
| }; |
| |
| /// Collect all VarLoc IDs from \p CollectFrom for VarLocs of kind |
| /// RegisterKind which are located in any reg in \p Regs. Insert collected IDs |
| /// into \p Collected. |
| void collectIDsForRegs(VarLocSet &Collected, const DefinedRegsSet &Regs, |
| const VarLocSet &CollectFrom) const; |
| |
| /// Get the registers which are used by VarLocs of kind RegisterKind tracked |
| /// by \p CollectFrom. |
| void getUsedRegs(const VarLocSet &CollectFrom, |
| SmallVectorImpl<uint32_t> &UsedRegs) const; |
| |
| VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, VarLocInMBB &Locs) { |
| std::unique_ptr<VarLocSet> &VLS = Locs[MBB]; |
| if (!VLS) |
| VLS = std::make_unique<VarLocSet>(Alloc); |
| return *VLS.get(); |
| } |
| |
| const VarLocSet &getVarLocsInMBB(const MachineBasicBlock *MBB, |
| const VarLocInMBB &Locs) const { |
| auto It = Locs.find(MBB); |
| assert(It != Locs.end() && "MBB not in map"); |
| return *It->second.get(); |
| } |
| |
| /// Tests whether this instruction is a spill to a stack location. |
| bool isSpillInstruction(const MachineInstr &MI, MachineFunction *MF); |
| |
| /// Decide if @MI is a spill instruction and return true if it is. We use 2 |
| /// criteria to make this decision: |
| /// - Is this instruction a store to a spill slot? |
| /// - Is there a register operand that is both used and killed? |
| /// TODO: Store optimization can fold spills into other stores (including |
| /// other spills). We do not handle this yet (more than one memory operand). |
| bool isLocationSpill(const MachineInstr &MI, MachineFunction *MF, |
| Register &Reg); |
| |
| /// Returns true if the given machine instruction is a debug value which we |
| /// can emit entry values for. |
| /// |
| /// Currently, we generate debug entry values only for parameters that are |
| /// unmodified throughout the function and located in a register. |
| bool isEntryValueCandidate(const MachineInstr &MI, |
| const DefinedRegsSet &Regs) const; |
| |
| /// If a given instruction is identified as a spill, return the spill location |
| /// and set \p Reg to the spilled register. |
| Optional<VarLoc::SpillLoc> isRestoreInstruction(const MachineInstr &MI, |
| MachineFunction *MF, |
| Register &Reg); |
| /// Given a spill instruction, extract the register and offset used to |
| /// address the spill location in a target independent way. |
| VarLoc::SpillLoc extractSpillBaseRegAndOffset(const MachineInstr &MI); |
| void insertTransferDebugPair(MachineInstr &MI, OpenRangesSet &OpenRanges, |
| TransferMap &Transfers, VarLocMap &VarLocIDs, |
| LocIndex OldVarID, TransferKind Kind, |
| Register NewReg = Register()); |
| |
| void transferDebugValue(const MachineInstr &MI, OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs); |
| void transferSpillOrRestoreInst(MachineInstr &MI, OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, TransferMap &Transfers); |
| bool removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, const VarLoc &EntryVL); |
| void emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, TransferMap &Transfers, |
| VarLocSet &KillSet); |
| void recordEntryValue(const MachineInstr &MI, |
| const DefinedRegsSet &DefinedRegs, |
| OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs); |
| void transferRegisterCopy(MachineInstr &MI, OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, TransferMap &Transfers); |
| void transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, TransferMap &Transfers); |
| bool transferTerminator(MachineBasicBlock *MBB, OpenRangesSet &OpenRanges, |
| VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs); |
| |
| void process(MachineInstr &MI, OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, TransferMap &Transfers); |
| |
| void accumulateFragmentMap(MachineInstr &MI, VarToFragments &SeenFragments, |
| OverlapMap &OLapMap); |
| |
| bool join(MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs, |
| const VarLocMap &VarLocIDs, |
| SmallPtrSet<const MachineBasicBlock *, 16> &Visited, |
| SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks); |
| |
| /// Create DBG_VALUE insts for inlocs that have been propagated but |
| /// had their instruction creation deferred. |
| void flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs); |
| |
| bool ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) override; |
| |
| public: |
| /// Default construct and initialize the pass. |
| VarLocBasedLDV(); |
| |
| ~VarLocBasedLDV(); |
| |
| /// Print to ostream with a message. |
| void printVarLocInMBB(const MachineFunction &MF, const VarLocInMBB &V, |
| const VarLocMap &VarLocIDs, const char *msg, |
| raw_ostream &Out) const; |
| }; |
| |
| } // end anonymous namespace |
| |
| //===----------------------------------------------------------------------===// |
| // Implementation |
| //===----------------------------------------------------------------------===// |
| |
| VarLocBasedLDV::VarLocBasedLDV() { } |
| |
| VarLocBasedLDV::~VarLocBasedLDV() { } |
| |
| /// Erase a variable from the set of open ranges, and additionally erase any |
| /// fragments that may overlap it. If the VarLoc is a backup location, erase |
| /// the variable from the EntryValuesBackupVars set, indicating we should stop |
| /// tracking its backup entry location. Otherwise, if the VarLoc is primary |
| /// location, erase the variable from the Vars set. |
| void VarLocBasedLDV::OpenRangesSet::erase(const VarLoc &VL) { |
| // Erasure helper. |
| auto DoErase = [VL, this](DebugVariable VarToErase) { |
| auto *EraseFrom = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; |
| auto It = EraseFrom->find(VarToErase); |
| if (It != EraseFrom->end()) { |
| LocIndex ID = It->second; |
| VarLocs.reset(ID.getAsRawInteger()); |
| EraseFrom->erase(It); |
| } |
| }; |
| |
| DebugVariable Var = VL.Var; |
| |
| // Erase the variable/fragment that ends here. |
| DoErase(Var); |
| |
| // Extract the fragment. Interpret an empty fragment as one that covers all |
| // possible bits. |
| FragmentInfo ThisFragment = Var.getFragmentOrDefault(); |
| |
| // There may be fragments that overlap the designated fragment. Look them up |
| // in the pre-computed overlap map, and erase them too. |
| auto MapIt = OverlappingFragments.find({Var.getVariable(), ThisFragment}); |
| if (MapIt != OverlappingFragments.end()) { |
| for (auto Fragment : MapIt->second) { |
| VarLocBasedLDV::OptFragmentInfo FragmentHolder; |
| if (!DebugVariable::isDefaultFragment(Fragment)) |
| FragmentHolder = VarLocBasedLDV::OptFragmentInfo(Fragment); |
| DoErase({Var.getVariable(), FragmentHolder, Var.getInlinedAt()}); |
| } |
| } |
| } |
| |
| void VarLocBasedLDV::OpenRangesSet::erase(const VarLocSet &KillSet, |
| const VarLocMap &VarLocIDs) { |
| VarLocs.intersectWithComplement(KillSet); |
| for (uint64_t ID : KillSet) { |
| const VarLoc *VL = &VarLocIDs[LocIndex::fromRawInteger(ID)]; |
| auto *EraseFrom = VL->isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; |
| EraseFrom->erase(VL->Var); |
| } |
| } |
| |
| void VarLocBasedLDV::OpenRangesSet::insert(LocIndex VarLocID, |
| const VarLoc &VL) { |
| auto *InsertInto = VL.isEntryBackupLoc() ? &EntryValuesBackupVars : &Vars; |
| VarLocs.set(VarLocID.getAsRawInteger()); |
| InsertInto->insert({VL.Var, VarLocID}); |
| } |
| |
| /// Return the Loc ID of an entry value backup location, if it exists for the |
| /// variable. |
| llvm::Optional<LocIndex> |
| VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(DebugVariable Var) { |
| auto It = EntryValuesBackupVars.find(Var); |
| if (It != EntryValuesBackupVars.end()) |
| return It->second; |
| |
| return llvm::None; |
| } |
| |
| void VarLocBasedLDV::collectIDsForRegs(VarLocSet &Collected, |
| const DefinedRegsSet &Regs, |
| const VarLocSet &CollectFrom) const { |
| assert(!Regs.empty() && "Nothing to collect"); |
| SmallVector<uint32_t, 32> SortedRegs; |
| append_range(SortedRegs, Regs); |
| array_pod_sort(SortedRegs.begin(), SortedRegs.end()); |
| auto It = CollectFrom.find(LocIndex::rawIndexForReg(SortedRegs.front())); |
| auto End = CollectFrom.end(); |
| for (uint32_t Reg : SortedRegs) { |
| // The half-open interval [FirstIndexForReg, FirstInvalidIndex) contains all |
| // possible VarLoc IDs for VarLocs of kind RegisterKind which live in Reg. |
| uint64_t FirstIndexForReg = LocIndex::rawIndexForReg(Reg); |
| uint64_t FirstInvalidIndex = LocIndex::rawIndexForReg(Reg + 1); |
| It.advanceToLowerBound(FirstIndexForReg); |
| |
| // Iterate through that half-open interval and collect all the set IDs. |
| for (; It != End && *It < FirstInvalidIndex; ++It) |
| Collected.set(*It); |
| |
| if (It == End) |
| return; |
| } |
| } |
| |
| void VarLocBasedLDV::getUsedRegs(const VarLocSet &CollectFrom, |
| SmallVectorImpl<uint32_t> &UsedRegs) const { |
| // All register-based VarLocs are assigned indices greater than or equal to |
| // FirstRegIndex. |
| uint64_t FirstRegIndex = LocIndex::rawIndexForReg(1); |
| uint64_t FirstInvalidIndex = |
| LocIndex::rawIndexForReg(LocIndex::kFirstInvalidRegLocation); |
| for (auto It = CollectFrom.find(FirstRegIndex), |
| End = CollectFrom.find(FirstInvalidIndex); |
| It != End;) { |
| // We found a VarLoc ID for a VarLoc that lives in a register. Figure out |
| // which register and add it to UsedRegs. |
| uint32_t FoundReg = LocIndex::fromRawInteger(*It).Location; |
| assert((UsedRegs.empty() || FoundReg != UsedRegs.back()) && |
| "Duplicate used reg"); |
| UsedRegs.push_back(FoundReg); |
| |
| // Skip to the next /set/ register. Note that this finds a lower bound, so |
| // even if there aren't any VarLocs living in `FoundReg+1`, we're still |
| // guaranteed to move on to the next register (or to end()). |
| uint64_t NextRegIndex = LocIndex::rawIndexForReg(FoundReg + 1); |
| It.advanceToLowerBound(NextRegIndex); |
| } |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Debug Range Extension Implementation |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef NDEBUG |
| void VarLocBasedLDV::printVarLocInMBB(const MachineFunction &MF, |
| const VarLocInMBB &V, |
| const VarLocMap &VarLocIDs, |
| const char *msg, |
| raw_ostream &Out) const { |
| Out << '\n' << msg << '\n'; |
| for (const MachineBasicBlock &BB : MF) { |
| if (!V.count(&BB)) |
| continue; |
| const VarLocSet &L = getVarLocsInMBB(&BB, V); |
| if (L.empty()) |
| continue; |
| Out << "MBB: " << BB.getNumber() << ":\n"; |
| for (uint64_t VLL : L) { |
| const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(VLL)]; |
| Out << " Var: " << VL.Var.getVariable()->getName(); |
| Out << " MI: "; |
| VL.dump(TRI, Out); |
| } |
| } |
| Out << "\n"; |
| } |
| #endif |
| |
| VarLocBasedLDV::VarLoc::SpillLoc |
| VarLocBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) { |
| assert(MI.hasOneMemOperand() && |
| "Spill instruction does not have exactly one memory operand?"); |
| auto MMOI = MI.memoperands_begin(); |
| const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue(); |
| assert(PVal->kind() == PseudoSourceValue::FixedStack && |
| "Inconsistent memory operand in spill instruction"); |
| int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex(); |
| const MachineBasicBlock *MBB = MI.getParent(); |
| Register Reg; |
| StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg); |
| return {Reg, Offset}; |
| } |
| |
| /// Try to salvage the debug entry value if we encounter a new debug value |
| /// describing the same parameter, otherwise stop tracking the value. Return |
| /// true if we should stop tracking the entry value, otherwise return false. |
| bool VarLocBasedLDV::removeEntryValue(const MachineInstr &MI, |
| OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, |
| const VarLoc &EntryVL) { |
| // Skip the DBG_VALUE which is the debug entry value itself. |
| if (MI.isIdenticalTo(EntryVL.MI)) |
| return false; |
| |
| // If the parameter's location is not register location, we can not track |
| // the entry value any more. In addition, if the debug expression from the |
| // DBG_VALUE is not empty, we can assume the parameter's value has changed |
| // indicating that we should stop tracking its entry value as well. |
| if (!MI.getDebugOperand(0).isReg() || |
| MI.getDebugExpression()->getNumElements() != 0) |
| return true; |
| |
| // If the DBG_VALUE comes from a copy instruction that copies the entry value, |
| // it means the parameter's value has not changed and we should be able to use |
| // its entry value. |
| bool TrySalvageEntryValue = false; |
| Register Reg = MI.getDebugOperand(0).getReg(); |
| auto I = std::next(MI.getReverseIterator()); |
| const MachineOperand *SrcRegOp, *DestRegOp; |
| if (I != MI.getParent()->rend()) { |
| // TODO: Try to keep tracking of an entry value if we encounter a propagated |
| // DBG_VALUE describing the copy of the entry value. (Propagated entry value |
| // does not indicate the parameter modification.) |
| auto DestSrc = TII->isCopyInstr(*I); |
| if (!DestSrc) |
| return true; |
| |
| SrcRegOp = DestSrc->Source; |
| DestRegOp = DestSrc->Destination; |
| if (Reg != DestRegOp->getReg()) |
| return true; |
| TrySalvageEntryValue = true; |
| } |
| |
| if (TrySalvageEntryValue) { |
| for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) { |
| const VarLoc &VL = VarLocIDs[LocIndex::fromRawInteger(ID)]; |
| if (VL.getEntryValueCopyBackupReg() == Reg && |
| VL.MI.getDebugOperand(0).getReg() == SrcRegOp->getReg()) |
| return false; |
| } |
| } |
| |
| return true; |
| } |
| |
| /// End all previous ranges related to @MI and start a new range from @MI |
| /// if it is a DBG_VALUE instr. |
| void VarLocBasedLDV::transferDebugValue(const MachineInstr &MI, |
| OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs) { |
| if (!MI.isDebugValue()) |
| return; |
| const DILocalVariable *Var = MI.getDebugVariable(); |
| const DIExpression *Expr = MI.getDebugExpression(); |
| const DILocation *DebugLoc = MI.getDebugLoc(); |
| const DILocation *InlinedAt = DebugLoc->getInlinedAt(); |
| assert(Var->isValidLocationForIntrinsic(DebugLoc) && |
| "Expected inlined-at fields to agree"); |
| |
| DebugVariable V(Var, Expr, InlinedAt); |
| |
| // Check if this DBG_VALUE indicates a parameter's value changing. |
| // If that is the case, we should stop tracking its entry value. |
| auto EntryValBackupID = OpenRanges.getEntryValueBackup(V); |
| if (Var->isParameter() && EntryValBackupID) { |
| const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID]; |
| if (removeEntryValue(MI, OpenRanges, VarLocIDs, EntryVL)) { |
| LLVM_DEBUG(dbgs() << "Deleting a DBG entry value because of: "; |
| MI.print(dbgs(), /*IsStandalone*/ false, |
| /*SkipOpers*/ false, /*SkipDebugLoc*/ false, |
| /*AddNewLine*/ true, TII)); |
| OpenRanges.erase(EntryVL); |
| } |
| } |
| |
| if (isDbgValueDescribedByReg(MI) || MI.getDebugOperand(0).isImm() || |
| MI.getDebugOperand(0).isFPImm() || MI.getDebugOperand(0).isCImm()) { |
| // Use normal VarLoc constructor for registers and immediates. |
| VarLoc VL(MI, LS); |
| // End all previous ranges of VL.Var. |
| OpenRanges.erase(VL); |
| |
| LocIndex ID = VarLocIDs.insert(VL); |
| // Add the VarLoc to OpenRanges from this DBG_VALUE. |
| OpenRanges.insert(ID, VL); |
| } else if (MI.hasOneMemOperand()) { |
| llvm_unreachable("DBG_VALUE with mem operand encountered after regalloc?"); |
| } else { |
| // This must be an undefined location. If it has an open range, erase it. |
| assert(MI.getDebugOperand(0).isReg() && |
| MI.getDebugOperand(0).getReg() == 0 && |
| "Unexpected non-undef DBG_VALUE encountered"); |
| VarLoc VL(MI, LS); |
| OpenRanges.erase(VL); |
| } |
| } |
| |
| /// Turn the entry value backup locations into primary locations. |
| void VarLocBasedLDV::emitEntryValues(MachineInstr &MI, |
| OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, |
| TransferMap &Transfers, |
| VarLocSet &KillSet) { |
| // Do not insert entry value locations after a terminator. |
| if (MI.isTerminator()) |
| return; |
| |
| for (uint64_t ID : KillSet) { |
| LocIndex Idx = LocIndex::fromRawInteger(ID); |
| const VarLoc &VL = VarLocIDs[Idx]; |
| if (!VL.Var.getVariable()->isParameter()) |
| continue; |
| |
| auto DebugVar = VL.Var; |
| Optional<LocIndex> EntryValBackupID = |
| OpenRanges.getEntryValueBackup(DebugVar); |
| |
| // If the parameter has the entry value backup, it means we should |
| // be able to use its entry value. |
| if (!EntryValBackupID) |
| continue; |
| |
| const VarLoc &EntryVL = VarLocIDs[*EntryValBackupID]; |
| VarLoc EntryLoc = |
| VarLoc::CreateEntryLoc(EntryVL.MI, LS, EntryVL.Expr, EntryVL.Loc.RegNo); |
| LocIndex EntryValueID = VarLocIDs.insert(EntryLoc); |
| Transfers.push_back({&MI, EntryValueID}); |
| OpenRanges.insert(EntryValueID, EntryLoc); |
| } |
| } |
| |
| /// Create new TransferDebugPair and insert it in \p Transfers. The VarLoc |
| /// with \p OldVarID should be deleted form \p OpenRanges and replaced with |
| /// new VarLoc. If \p NewReg is different than default zero value then the |
| /// new location will be register location created by the copy like instruction, |
| /// otherwise it is variable's location on the stack. |
| void VarLocBasedLDV::insertTransferDebugPair( |
| MachineInstr &MI, OpenRangesSet &OpenRanges, TransferMap &Transfers, |
| VarLocMap &VarLocIDs, LocIndex OldVarID, TransferKind Kind, |
| Register NewReg) { |
| const MachineInstr *DebugInstr = &VarLocIDs[OldVarID].MI; |
| |
| auto ProcessVarLoc = [&MI, &OpenRanges, &Transfers, &VarLocIDs](VarLoc &VL) { |
| LocIndex LocId = VarLocIDs.insert(VL); |
| |
| // Close this variable's previous location range. |
| OpenRanges.erase(VL); |
| |
| // Record the new location as an open range, and a postponed transfer |
| // inserting a DBG_VALUE for this location. |
| OpenRanges.insert(LocId, VL); |
| assert(!MI.isTerminator() && "Cannot insert DBG_VALUE after terminator"); |
| TransferDebugPair MIP = {&MI, LocId}; |
| Transfers.push_back(MIP); |
| }; |
| |
| // End all previous ranges of VL.Var. |
| OpenRanges.erase(VarLocIDs[OldVarID]); |
| switch (Kind) { |
| case TransferKind::TransferCopy: { |
| assert(NewReg && |
| "No register supplied when handling a copy of a debug value"); |
| // Create a DBG_VALUE instruction to describe the Var in its new |
| // register location. |
| VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg); |
| ProcessVarLoc(VL); |
| LLVM_DEBUG({ |
| dbgs() << "Creating VarLoc for register copy:"; |
| VL.dump(TRI); |
| }); |
| return; |
| } |
| case TransferKind::TransferSpill: { |
| // Create a DBG_VALUE instruction to describe the Var in its spilled |
| // location. |
| VarLoc::SpillLoc SpillLocation = extractSpillBaseRegAndOffset(MI); |
| VarLoc VL = VarLoc::CreateSpillLoc(*DebugInstr, SpillLocation.SpillBase, |
| SpillLocation.SpillOffset, LS); |
| ProcessVarLoc(VL); |
| LLVM_DEBUG({ |
| dbgs() << "Creating VarLoc for spill:"; |
| VL.dump(TRI); |
| }); |
| return; |
| } |
| case TransferKind::TransferRestore: { |
| assert(NewReg && |
| "No register supplied when handling a restore of a debug value"); |
| // DebugInstr refers to the pre-spill location, therefore we can reuse |
| // its expression. |
| VarLoc VL = VarLoc::CreateCopyLoc(*DebugInstr, LS, NewReg); |
| ProcessVarLoc(VL); |
| LLVM_DEBUG({ |
| dbgs() << "Creating VarLoc for restore:"; |
| VL.dump(TRI); |
| }); |
| return; |
| } |
| } |
| llvm_unreachable("Invalid transfer kind"); |
| } |
| |
| /// A definition of a register may mark the end of a range. |
| void VarLocBasedLDV::transferRegisterDef( |
| MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, |
| TransferMap &Transfers) { |
| |
| // Meta Instructions do not affect the debug liveness of any register they |
| // define. |
| if (MI.isMetaInstruction()) |
| return; |
| |
| MachineFunction *MF = MI.getMF(); |
| const TargetLowering *TLI = MF->getSubtarget().getTargetLowering(); |
| Register SP = TLI->getStackPointerRegisterToSaveRestore(); |
| |
| // Find the regs killed by MI, and find regmasks of preserved regs. |
| DefinedRegsSet DeadRegs; |
| SmallVector<const uint32_t *, 4> RegMasks; |
| for (const MachineOperand &MO : MI.operands()) { |
| // Determine whether the operand is a register def. |
| if (MO.isReg() && MO.isDef() && MO.getReg() && |
| Register::isPhysicalRegister(MO.getReg()) && |
| !(MI.isCall() && MO.getReg() == SP)) { |
| // Remove ranges of all aliased registers. |
| for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI) |
| // FIXME: Can we break out of this loop early if no insertion occurs? |
| DeadRegs.insert(*RAI); |
| } else if (MO.isRegMask()) { |
| RegMasks.push_back(MO.getRegMask()); |
| } |
| } |
| |
| // Erase VarLocs which reside in one of the dead registers. For performance |
| // reasons, it's critical to not iterate over the full set of open VarLocs. |
| // Iterate over the set of dying/used regs instead. |
| if (!RegMasks.empty()) { |
| SmallVector<uint32_t, 32> UsedRegs; |
| getUsedRegs(OpenRanges.getVarLocs(), UsedRegs); |
| for (uint32_t Reg : UsedRegs) { |
| // Remove ranges of all clobbered registers. Register masks don't usually |
| // list SP as preserved. Assume that call instructions never clobber SP, |
| // because some backends (e.g., AArch64) never list SP in the regmask. |
| // While the debug info may be off for an instruction or two around |
| // callee-cleanup calls, transferring the DEBUG_VALUE across the call is |
| // still a better user experience. |
| if (Reg == SP) |
| continue; |
| bool AnyRegMaskKillsReg = |
| any_of(RegMasks, [Reg](const uint32_t *RegMask) { |
| return MachineOperand::clobbersPhysReg(RegMask, Reg); |
| }); |
| if (AnyRegMaskKillsReg) |
| DeadRegs.insert(Reg); |
| } |
| } |
| |
| if (DeadRegs.empty()) |
| return; |
| |
| VarLocSet KillSet(Alloc); |
| collectIDsForRegs(KillSet, DeadRegs, OpenRanges.getVarLocs()); |
| OpenRanges.erase(KillSet, VarLocIDs); |
| |
| if (TPC) { |
| auto &TM = TPC->getTM<TargetMachine>(); |
| if (TM.Options.ShouldEmitDebugEntryValues()) |
| emitEntryValues(MI, OpenRanges, VarLocIDs, Transfers, KillSet); |
| } |
| } |
| |
| bool VarLocBasedLDV::isSpillInstruction(const MachineInstr &MI, |
| MachineFunction *MF) { |
| // TODO: Handle multiple stores folded into one. |
| if (!MI.hasOneMemOperand()) |
| return false; |
| |
| if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII)) |
| return false; // This is not a spill instruction, since no valid size was |
| // returned from either function. |
| |
| return true; |
| } |
| |
| bool VarLocBasedLDV::isLocationSpill(const MachineInstr &MI, |
| MachineFunction *MF, Register &Reg) { |
| if (!isSpillInstruction(MI, MF)) |
| return false; |
| |
| auto isKilledReg = [&](const MachineOperand MO, Register &Reg) { |
| if (!MO.isReg() || !MO.isUse()) { |
| Reg = 0; |
| return false; |
| } |
| Reg = MO.getReg(); |
| return MO.isKill(); |
| }; |
| |
| for (const MachineOperand &MO : MI.operands()) { |
| // In a spill instruction generated by the InlineSpiller the spilled |
| // register has its kill flag set. |
| if (isKilledReg(MO, Reg)) |
| return true; |
| if (Reg != 0) { |
| // Check whether next instruction kills the spilled register. |
| // FIXME: Current solution does not cover search for killed register in |
| // bundles and instructions further down the chain. |
| auto NextI = std::next(MI.getIterator()); |
| // Skip next instruction that points to basic block end iterator. |
| if (MI.getParent()->end() == NextI) |
| continue; |
| Register RegNext; |
| for (const MachineOperand &MONext : NextI->operands()) { |
| // Return true if we came across the register from the |
| // previous spill instruction that is killed in NextI. |
| if (isKilledReg(MONext, RegNext) && RegNext == Reg) |
| return true; |
| } |
| } |
| } |
| // Return false if we didn't find spilled register. |
| return false; |
| } |
| |
| Optional<VarLocBasedLDV::VarLoc::SpillLoc> |
| VarLocBasedLDV::isRestoreInstruction(const MachineInstr &MI, |
| MachineFunction *MF, Register &Reg) { |
| if (!MI.hasOneMemOperand()) |
| return None; |
| |
| // FIXME: Handle folded restore instructions with more than one memory |
| // operand. |
| if (MI.getRestoreSize(TII)) { |
| Reg = MI.getOperand(0).getReg(); |
| return extractSpillBaseRegAndOffset(MI); |
| } |
| return None; |
| } |
| |
| /// A spilled register may indicate that we have to end the current range of |
| /// a variable and create a new one for the spill location. |
| /// A restored register may indicate the reverse situation. |
| /// We don't want to insert any instructions in process(), so we just create |
| /// the DBG_VALUE without inserting it and keep track of it in \p Transfers. |
| /// It will be inserted into the BB when we're done iterating over the |
| /// instructions. |
| void VarLocBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI, |
| OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, |
| TransferMap &Transfers) { |
| MachineFunction *MF = MI.getMF(); |
| TransferKind TKind; |
| Register Reg; |
| Optional<VarLoc::SpillLoc> Loc; |
| |
| LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump();); |
| |
| // First, if there are any DBG_VALUEs pointing at a spill slot that is |
| // written to, then close the variable location. The value in memory |
| // will have changed. |
| VarLocSet KillSet(Alloc); |
| if (isSpillInstruction(MI, MF)) { |
| Loc = extractSpillBaseRegAndOffset(MI); |
| for (uint64_t ID : OpenRanges.getSpillVarLocs()) { |
| LocIndex Idx = LocIndex::fromRawInteger(ID); |
| const VarLoc &VL = VarLocIDs[Idx]; |
| assert(VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?"); |
| if (VL.Loc.SpillLocation == *Loc) { |
| // This location is overwritten by the current instruction -- terminate |
| // the open range, and insert an explicit DBG_VALUE $noreg. |
| // |
| // Doing this at a later stage would require re-interpreting all |
| // DBG_VALUes and DIExpressions to identify whether they point at |
| // memory, and then analysing all memory writes to see if they |
| // overwrite that memory, which is expensive. |
| // |
| // At this stage, we already know which DBG_VALUEs are for spills and |
| // where they are located; it's best to fix handle overwrites now. |
| KillSet.set(ID); |
| VarLoc UndefVL = VarLoc::CreateCopyLoc(VL.MI, LS, 0); |
| LocIndex UndefLocID = VarLocIDs.insert(UndefVL); |
| Transfers.push_back({&MI, UndefLocID}); |
| } |
| } |
| OpenRanges.erase(KillSet, VarLocIDs); |
| } |
| |
| // Try to recognise spill and restore instructions that may create a new |
| // variable location. |
| if (isLocationSpill(MI, MF, Reg)) { |
| TKind = TransferKind::TransferSpill; |
| LLVM_DEBUG(dbgs() << "Recognized as spill: "; MI.dump();); |
| LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI) |
| << "\n"); |
| } else { |
| if (!(Loc = isRestoreInstruction(MI, MF, Reg))) |
| return; |
| TKind = TransferKind::TransferRestore; |
| LLVM_DEBUG(dbgs() << "Recognized as restore: "; MI.dump();); |
| LLVM_DEBUG(dbgs() << "Register: " << Reg << " " << printReg(Reg, TRI) |
| << "\n"); |
| } |
| // Check if the register or spill location is the location of a debug value. |
| auto TransferCandidates = OpenRanges.getEmptyVarLocRange(); |
| if (TKind == TransferKind::TransferSpill) |
| TransferCandidates = OpenRanges.getRegisterVarLocs(Reg); |
| else if (TKind == TransferKind::TransferRestore) |
| TransferCandidates = OpenRanges.getSpillVarLocs(); |
| for (uint64_t ID : TransferCandidates) { |
| LocIndex Idx = LocIndex::fromRawInteger(ID); |
| const VarLoc &VL = VarLocIDs[Idx]; |
| if (TKind == TransferKind::TransferSpill) { |
| assert(VL.isDescribedByReg() == Reg && "Broken VarLocSet?"); |
| LLVM_DEBUG(dbgs() << "Spilling Register " << printReg(Reg, TRI) << '(' |
| << VL.Var.getVariable()->getName() << ")\n"); |
| } else { |
| assert(TKind == TransferKind::TransferRestore && |
| VL.Kind == VarLoc::SpillLocKind && "Broken VarLocSet?"); |
| if (VL.Loc.SpillLocation != *Loc) |
| // The spill location is not the location of a debug value. |
| continue; |
| LLVM_DEBUG(dbgs() << "Restoring Register " << printReg(Reg, TRI) << '(' |
| << VL.Var.getVariable()->getName() << ")\n"); |
| } |
| insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, TKind, |
| Reg); |
| // FIXME: A comment should explain why it's correct to return early here, |
| // if that is in fact correct. |
| return; |
| } |
| } |
| |
| /// If \p MI is a register copy instruction, that copies a previously tracked |
| /// value from one register to another register that is callee saved, we |
| /// create new DBG_VALUE instruction described with copy destination register. |
| void VarLocBasedLDV::transferRegisterCopy(MachineInstr &MI, |
| OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, |
| TransferMap &Transfers) { |
| auto DestSrc = TII->isCopyInstr(MI); |
| if (!DestSrc) |
| return; |
| |
| const MachineOperand *DestRegOp = DestSrc->Destination; |
| const MachineOperand *SrcRegOp = DestSrc->Source; |
| |
| if (!DestRegOp->isDef()) |
| return; |
| |
| auto isCalleeSavedReg = [&](Register Reg) { |
| for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI) |
| if (CalleeSavedRegs.test(*RAI)) |
| return true; |
| return false; |
| }; |
| |
| Register SrcReg = SrcRegOp->getReg(); |
| Register DestReg = DestRegOp->getReg(); |
| |
| // We want to recognize instructions where destination register is callee |
| // saved register. If register that could be clobbered by the call is |
| // included, there would be a great chance that it is going to be clobbered |
| // soon. It is more likely that previous register location, which is callee |
| // saved, is going to stay unclobbered longer, even if it is killed. |
| if (!isCalleeSavedReg(DestReg)) |
| return; |
| |
| // Remember an entry value movement. If we encounter a new debug value of |
| // a parameter describing only a moving of the value around, rather then |
| // modifying it, we are still able to use the entry value if needed. |
| if (isRegOtherThanSPAndFP(*DestRegOp, MI, TRI)) { |
| for (uint64_t ID : OpenRanges.getEntryValueBackupVarLocs()) { |
| LocIndex Idx = LocIndex::fromRawInteger(ID); |
| const VarLoc &VL = VarLocIDs[Idx]; |
| if (VL.getEntryValueBackupReg() == SrcReg) { |
| LLVM_DEBUG(dbgs() << "Copy of the entry value: "; MI.dump();); |
| VarLoc EntryValLocCopyBackup = |
| VarLoc::CreateEntryCopyBackupLoc(VL.MI, LS, VL.Expr, DestReg); |
| |
| // Stop tracking the original entry value. |
| OpenRanges.erase(VL); |
| |
| // Start tracking the entry value copy. |
| LocIndex EntryValCopyLocID = VarLocIDs.insert(EntryValLocCopyBackup); |
| OpenRanges.insert(EntryValCopyLocID, EntryValLocCopyBackup); |
| break; |
| } |
| } |
| } |
| |
| if (!SrcRegOp->isKill()) |
| return; |
| |
| for (uint64_t ID : OpenRanges.getRegisterVarLocs(SrcReg)) { |
| LocIndex Idx = LocIndex::fromRawInteger(ID); |
| assert(VarLocIDs[Idx].isDescribedByReg() == SrcReg && "Broken VarLocSet?"); |
| insertTransferDebugPair(MI, OpenRanges, Transfers, VarLocIDs, Idx, |
| TransferKind::TransferCopy, DestReg); |
| // FIXME: A comment should explain why it's correct to return early here, |
| // if that is in fact correct. |
| return; |
| } |
| } |
| |
| /// Terminate all open ranges at the end of the current basic block. |
| bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB, |
| OpenRangesSet &OpenRanges, |
| VarLocInMBB &OutLocs, |
| const VarLocMap &VarLocIDs) { |
| bool Changed = false; |
| |
| LLVM_DEBUG(for (uint64_t ID |
| : OpenRanges.getVarLocs()) { |
| // Copy OpenRanges to OutLocs, if not already present. |
| dbgs() << "Add to OutLocs in MBB #" << CurMBB->getNumber() << ": "; |
| VarLocIDs[LocIndex::fromRawInteger(ID)].dump(TRI); |
| }); |
| VarLocSet &VLS = getVarLocsInMBB(CurMBB, OutLocs); |
| Changed = VLS != OpenRanges.getVarLocs(); |
| // New OutLocs set may be different due to spill, restore or register |
| // copy instruction processing. |
| if (Changed) |
| VLS = OpenRanges.getVarLocs(); |
| OpenRanges.clear(); |
| return Changed; |
| } |
| |
| /// Accumulate a mapping between each DILocalVariable fragment and other |
| /// fragments of that DILocalVariable which overlap. This reduces work during |
| /// the data-flow stage from "Find any overlapping fragments" to "Check if the |
| /// known-to-overlap fragments are present". |
| /// \param MI A previously unprocessed DEBUG_VALUE instruction to analyze for |
| /// fragment usage. |
| /// \param SeenFragments Map from DILocalVariable to all fragments of that |
| /// Variable which are known to exist. |
| /// \param OverlappingFragments The overlap map being constructed, from one |
| /// Var/Fragment pair to a vector of fragments known to overlap. |
| void VarLocBasedLDV::accumulateFragmentMap(MachineInstr &MI, |
| VarToFragments &SeenFragments, |
| OverlapMap &OverlappingFragments) { |
| DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(), |
| MI.getDebugLoc()->getInlinedAt()); |
| FragmentInfo ThisFragment = MIVar.getFragmentOrDefault(); |
| |
| // If this is the first sighting of this variable, then we are guaranteed |
| // there are currently no overlapping fragments either. Initialize the set |
| // of seen fragments, record no overlaps for the current one, and return. |
| auto SeenIt = SeenFragments.find(MIVar.getVariable()); |
| if (SeenIt == SeenFragments.end()) { |
| SmallSet<FragmentInfo, 4> OneFragment; |
| OneFragment.insert(ThisFragment); |
| SeenFragments.insert({MIVar.getVariable(), OneFragment}); |
| |
| OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); |
| return; |
| } |
| |
| // If this particular Variable/Fragment pair already exists in the overlap |
| // map, it has already been accounted for. |
| auto IsInOLapMap = |
| OverlappingFragments.insert({{MIVar.getVariable(), ThisFragment}, {}}); |
| if (!IsInOLapMap.second) |
| return; |
| |
| auto &ThisFragmentsOverlaps = IsInOLapMap.first->second; |
| auto &AllSeenFragments = SeenIt->second; |
| |
| // Otherwise, examine all other seen fragments for this variable, with "this" |
| // fragment being a previously unseen fragment. Record any pair of |
| // overlapping fragments. |
| for (auto &ASeenFragment : AllSeenFragments) { |
| // Does this previously seen fragment overlap? |
| if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) { |
| // Yes: Mark the current fragment as being overlapped. |
| ThisFragmentsOverlaps.push_back(ASeenFragment); |
| // Mark the previously seen fragment as being overlapped by the current |
| // one. |
| auto ASeenFragmentsOverlaps = |
| OverlappingFragments.find({MIVar.getVariable(), ASeenFragment}); |
| assert(ASeenFragmentsOverlaps != OverlappingFragments.end() && |
| "Previously seen var fragment has no vector of overlaps"); |
| ASeenFragmentsOverlaps->second.push_back(ThisFragment); |
| } |
| } |
| |
| AllSeenFragments.insert(ThisFragment); |
| } |
| |
| /// This routine creates OpenRanges. |
| void VarLocBasedLDV::process(MachineInstr &MI, OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs, TransferMap &Transfers) { |
| transferDebugValue(MI, OpenRanges, VarLocIDs); |
| transferRegisterDef(MI, OpenRanges, VarLocIDs, Transfers); |
| transferRegisterCopy(MI, OpenRanges, VarLocIDs, Transfers); |
| transferSpillOrRestoreInst(MI, OpenRanges, VarLocIDs, Transfers); |
| } |
| |
| /// This routine joins the analysis results of all incoming edges in @MBB by |
| /// inserting a new DBG_VALUE instruction at the start of the @MBB - if the same |
| /// source variable in all the predecessors of @MBB reside in the same location. |
| bool VarLocBasedLDV::join( |
| MachineBasicBlock &MBB, VarLocInMBB &OutLocs, VarLocInMBB &InLocs, |
| const VarLocMap &VarLocIDs, |
| SmallPtrSet<const MachineBasicBlock *, 16> &Visited, |
| SmallPtrSetImpl<const MachineBasicBlock *> &ArtificialBlocks) { |
| LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n"); |
| |
| VarLocSet InLocsT(Alloc); // Temporary incoming locations. |
| |
| // For all predecessors of this MBB, find the set of VarLocs that |
| // can be joined. |
| int NumVisited = 0; |
| for (auto p : MBB.predecessors()) { |
| // Ignore backedges if we have not visited the predecessor yet. As the |
| // predecessor hasn't yet had locations propagated into it, most locations |
| // will not yet be valid, so treat them as all being uninitialized and |
| // potentially valid. If a location guessed to be correct here is |
| // invalidated later, we will remove it when we revisit this block. |
| if (!Visited.count(p)) { |
| LLVM_DEBUG(dbgs() << " ignoring unvisited pred MBB: " << p->getNumber() |
| << "\n"); |
| continue; |
| } |
| auto OL = OutLocs.find(p); |
| // Join is null in case of empty OutLocs from any of the pred. |
| if (OL == OutLocs.end()) |
| return false; |
| |
| // Just copy over the Out locs to incoming locs for the first visited |
| // predecessor, and for all other predecessors join the Out locs. |
| VarLocSet &OutLocVLS = *OL->second.get(); |
| if (!NumVisited) |
| InLocsT = OutLocVLS; |
| else |
| InLocsT &= OutLocVLS; |
| |
| LLVM_DEBUG({ |
| if (!InLocsT.empty()) { |
| for (uint64_t ID : InLocsT) |
| dbgs() << " gathered candidate incoming var: " |
| << VarLocIDs[LocIndex::fromRawInteger(ID)] |
| .Var.getVariable() |
| ->getName() |
| << "\n"; |
| } |
| }); |
| |
| NumVisited++; |
| } |
| |
| // Filter out DBG_VALUES that are out of scope. |
| VarLocSet KillSet(Alloc); |
| bool IsArtificial = ArtificialBlocks.count(&MBB); |
| if (!IsArtificial) { |
| for (uint64_t ID : InLocsT) { |
| LocIndex Idx = LocIndex::fromRawInteger(ID); |
| if (!VarLocIDs[Idx].dominates(LS, MBB)) { |
| KillSet.set(ID); |
| LLVM_DEBUG({ |
| auto Name = VarLocIDs[Idx].Var.getVariable()->getName(); |
| dbgs() << " killing " << Name << ", it doesn't dominate MBB\n"; |
| }); |
| } |
| } |
| } |
| InLocsT.intersectWithComplement(KillSet); |
| |
| // As we are processing blocks in reverse post-order we |
| // should have processed at least one predecessor, unless it |
| // is the entry block which has no predecessor. |
| assert((NumVisited || MBB.pred_empty()) && |
| "Should have processed at least one predecessor"); |
| |
| VarLocSet &ILS = getVarLocsInMBB(&MBB, InLocs); |
| bool Changed = false; |
| if (ILS != InLocsT) { |
| ILS = InLocsT; |
| Changed = true; |
| } |
| |
| return Changed; |
| } |
| |
| void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs, |
| VarLocMap &VarLocIDs) { |
| // PendingInLocs records all locations propagated into blocks, which have |
| // not had DBG_VALUE insts created. Go through and create those insts now. |
| for (auto &Iter : PendingInLocs) { |
| // Map is keyed on a constant pointer, unwrap it so we can insert insts. |
| auto &MBB = const_cast<MachineBasicBlock &>(*Iter.first); |
| VarLocSet &Pending = *Iter.second.get(); |
| |
| for (uint64_t ID : Pending) { |
| // The ID location is live-in to MBB -- work out what kind of machine |
| // location it is and create a DBG_VALUE. |
| const VarLoc &DiffIt = VarLocIDs[LocIndex::fromRawInteger(ID)]; |
| if (DiffIt.isEntryBackupLoc()) |
| continue; |
| MachineInstr *MI = DiffIt.BuildDbgValue(*MBB.getParent()); |
| MBB.insert(MBB.instr_begin(), MI); |
| |
| (void)MI; |
| LLVM_DEBUG(dbgs() << "Inserted: "; MI->dump();); |
| } |
| } |
| } |
| |
| bool VarLocBasedLDV::isEntryValueCandidate( |
| const MachineInstr &MI, const DefinedRegsSet &DefinedRegs) const { |
| assert(MI.isDebugValue() && "This must be DBG_VALUE."); |
| |
| // TODO: Add support for local variables that are expressed in terms of |
| // parameters entry values. |
| // TODO: Add support for modified arguments that can be expressed |
| // by using its entry value. |
| auto *DIVar = MI.getDebugVariable(); |
| if (!DIVar->isParameter()) |
| return false; |
| |
| // Do not consider parameters that belong to an inlined function. |
| if (MI.getDebugLoc()->getInlinedAt()) |
| return false; |
| |
| // Only consider parameters that are described using registers. Parameters |
| // that are passed on the stack are not yet supported, so ignore debug |
| // values that are described by the frame or stack pointer. |
| if (!isRegOtherThanSPAndFP(MI.getDebugOperand(0), MI, TRI)) |
| return false; |
| |
| // If a parameter's value has been propagated from the caller, then the |
| // parameter's DBG_VALUE may be described using a register defined by some |
| // instruction in the entry block, in which case we shouldn't create an |
| // entry value. |
| if (DefinedRegs.count(MI.getDebugOperand(0).getReg())) |
| return false; |
| |
| // TODO: Add support for parameters that have a pre-existing debug expressions |
| // (e.g. fragments). |
| if (MI.getDebugExpression()->getNumElements() > 0) |
| return false; |
| |
| return true; |
| } |
| |
| /// Collect all register defines (including aliases) for the given instruction. |
| static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs, |
| const TargetRegisterInfo *TRI) { |
| for (const MachineOperand &MO : MI.operands()) |
| if (MO.isReg() && MO.isDef() && MO.getReg()) |
| for (MCRegAliasIterator AI(MO.getReg(), TRI, true); AI.isValid(); ++AI) |
| Regs.insert(*AI); |
| } |
| |
| /// This routine records the entry values of function parameters. The values |
| /// could be used as backup values. If we loose the track of some unmodified |
| /// parameters, the backup values will be used as a primary locations. |
| void VarLocBasedLDV::recordEntryValue(const MachineInstr &MI, |
| const DefinedRegsSet &DefinedRegs, |
| OpenRangesSet &OpenRanges, |
| VarLocMap &VarLocIDs) { |
| if (TPC) { |
| auto &TM = TPC->getTM<TargetMachine>(); |
| if (!TM.Options.ShouldEmitDebugEntryValues()) |
| return; |
| } |
| |
| DebugVariable V(MI.getDebugVariable(), MI.getDebugExpression(), |
| MI.getDebugLoc()->getInlinedAt()); |
| |
| if (!isEntryValueCandidate(MI, DefinedRegs) || |
| OpenRanges.getEntryValueBackup(V)) |
| return; |
| |
| LLVM_DEBUG(dbgs() << "Creating the backup entry location: "; MI.dump();); |
| |
| // Create the entry value and use it as a backup location until it is |
| // valid. It is valid until a parameter is not changed. |
| DIExpression *NewExpr = |
| DIExpression::prepend(MI.getDebugExpression(), DIExpression::EntryValue); |
| VarLoc EntryValLocAsBackup = VarLoc::CreateEntryBackupLoc(MI, LS, NewExpr); |
| LocIndex EntryValLocID = VarLocIDs.insert(EntryValLocAsBackup); |
| OpenRanges.insert(EntryValLocID, EntryValLocAsBackup); |
| } |
| |
| /// Calculate the liveness information for the given machine function and |
| /// extend ranges across basic blocks. |
| bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, TargetPassConfig *TPC) { |
| LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n"); |
| |
| if (!MF.getFunction().getSubprogram()) |
| // VarLocBaseLDV will already have removed all DBG_VALUEs. |
| return false; |
| |
| // Skip functions from NoDebug compilation units. |
| if (MF.getFunction().getSubprogram()->getUnit()->getEmissionKind() == |
| DICompileUnit::NoDebug) |
| return false; |
| |
| TRI = MF.getSubtarget().getRegisterInfo(); |
| TII = MF.getSubtarget().getInstrInfo(); |
| TFI = MF.getSubtarget().getFrameLowering(); |
| TFI->getCalleeSaves(MF, CalleeSavedRegs); |
| this->TPC = TPC; |
| LS.initialize(MF); |
| |
| bool Changed = false; |
| bool OLChanged = false; |
| bool MBBJoined = false; |
| |
| VarLocMap VarLocIDs; // Map VarLoc<>unique ID for use in bitvectors. |
| OverlapMap OverlapFragments; // Map of overlapping variable fragments. |
| OpenRangesSet OpenRanges(Alloc, OverlapFragments); |
| // Ranges that are open until end of bb. |
| VarLocInMBB OutLocs; // Ranges that exist beyond bb. |
| VarLocInMBB InLocs; // Ranges that are incoming after joining. |
| TransferMap Transfers; // DBG_VALUEs associated with transfers (such as |
| // spills, copies and restores). |
| |
| VarToFragments SeenFragments; |
| |
| // Blocks which are artificial, i.e. blocks which exclusively contain |
| // instructions without locations, or with line 0 locations. |
| SmallPtrSet<const MachineBasicBlock *, 16> ArtificialBlocks; |
| |
| DenseMap<unsigned int, MachineBasicBlock *> OrderToBB; |
| DenseMap<MachineBasicBlock *, unsigned int> BBToOrder; |
| std::priority_queue<unsigned int, std::vector<unsigned int>, |
| std::greater<unsigned int>> |
| Worklist; |
| std::priority_queue<unsigned int, std::vector<unsigned int>, |
| std::greater<unsigned int>> |
| Pending; |
| |
| // Set of register defines that are seen when traversing the entry block |
| // looking for debug entry value candidates. |
| DefinedRegsSet DefinedRegs; |
| |
| // Only in the case of entry MBB collect DBG_VALUEs representing |
| // function parameters in order to generate debug entry values for them. |
| MachineBasicBlock &First_MBB = *(MF.begin()); |
| for (auto &MI : First_MBB) { |
| collectRegDefs(MI, DefinedRegs, TRI); |
| if (MI.isDebugValue()) |
| recordEntryValue(MI, DefinedRegs, OpenRanges, VarLocIDs); |
| } |
| |
| // Initialize per-block structures and scan for fragment overlaps. |
| for (auto &MBB : MF) |
| for (auto &MI : MBB) |
| if (MI.isDebugValue()) |
| accumulateFragmentMap(MI, SeenFragments, OverlapFragments); |
| |
| auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool { |
| if (const DebugLoc &DL = MI.getDebugLoc()) |
| return DL.getLine() != 0; |
| return false; |
| }; |
| for (auto &MBB : MF) |
| if (none_of(MBB.instrs(), hasNonArtificialLocation)) |
| ArtificialBlocks.insert(&MBB); |
| |
| LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, |
| "OutLocs after initialization", dbgs())); |
| |
| ReversePostOrderTraversal<MachineFunction *> RPOT(&MF); |
| unsigned int RPONumber = 0; |
| for (MachineBasicBlock *MBB : RPOT) { |
| OrderToBB[RPONumber] = MBB; |
| BBToOrder[MBB] = RPONumber; |
| Worklist.push(RPONumber); |
| ++RPONumber; |
| } |
| |
| if (RPONumber > InputBBLimit) { |
| unsigned NumInputDbgValues = 0; |
| for (auto &MBB : MF) |
| for (auto &MI : MBB) |
| if (MI.isDebugValue()) |
| ++NumInputDbgValues; |
| if (NumInputDbgValues > InputDbgValueLimit) { |
| LLVM_DEBUG(dbgs() << "Disabling VarLocBasedLDV: " << MF.getName() |
| << " has " << RPONumber << " basic blocks and " |
| << NumInputDbgValues |
| << " input DBG_VALUEs, exceeding limits.\n"); |
| return false; |
| } |
| } |
| |
| // This is a standard "union of predecessor outs" dataflow problem. |
| // To solve it, we perform join() and process() using the two worklist method |
| // until the ranges converge. |
| // Ranges have converged when both worklists are empty. |
| SmallPtrSet<const MachineBasicBlock *, 16> Visited; |
| while (!Worklist.empty() || !Pending.empty()) { |
| // We track what is on the pending worklist to avoid inserting the same |
| // thing twice. We could avoid this with a custom priority queue, but this |
| // is probably not worth it. |
| SmallPtrSet<MachineBasicBlock *, 16> OnPending; |
| LLVM_DEBUG(dbgs() << "Processing Worklist\n"); |
| while (!Worklist.empty()) { |
| MachineBasicBlock *MBB = OrderToBB[Worklist.top()]; |
| Worklist.pop(); |
| MBBJoined = join(*MBB, OutLocs, InLocs, VarLocIDs, Visited, |
| ArtificialBlocks); |
| MBBJoined |= Visited.insert(MBB).second; |
| if (MBBJoined) { |
| MBBJoined = false; |
| Changed = true; |
| // Now that we have started to extend ranges across BBs we need to |
| // examine spill, copy and restore instructions to see whether they |
| // operate with registers that correspond to user variables. |
| // First load any pending inlocs. |
| OpenRanges.insertFromLocSet(getVarLocsInMBB(MBB, InLocs), VarLocIDs); |
| for (auto &MI : *MBB) |
| process(MI, OpenRanges, VarLocIDs, Transfers); |
| OLChanged |= transferTerminator(MBB, OpenRanges, OutLocs, VarLocIDs); |
| |
| LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, |
| "OutLocs after propagating", dbgs())); |
| LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, |
| "InLocs after propagating", dbgs())); |
| |
| if (OLChanged) { |
| OLChanged = false; |
| for (auto s : MBB->successors()) |
| if (OnPending.insert(s).second) { |
| Pending.push(BBToOrder[s]); |
| } |
| } |
| } |
| } |
| Worklist.swap(Pending); |
| // At this point, pending must be empty, since it was just the empty |
| // worklist |
| assert(Pending.empty() && "Pending should be empty"); |
| } |
| |
| // Add any DBG_VALUE instructions created by location transfers. |
| for (auto &TR : Transfers) { |
| assert(!TR.TransferInst->isTerminator() && |
| "Cannot insert DBG_VALUE after terminator"); |
| MachineBasicBlock *MBB = TR.TransferInst->getParent(); |
| const VarLoc &VL = VarLocIDs[TR.LocationID]; |
| MachineInstr *MI = VL.BuildDbgValue(MF); |
| MBB->insertAfterBundle(TR.TransferInst->getIterator(), MI); |
| } |
| Transfers.clear(); |
| |
| // Deferred inlocs will not have had any DBG_VALUE insts created; do |
| // that now. |
| flushPendingLocs(InLocs, VarLocIDs); |
| |
| LLVM_DEBUG(printVarLocInMBB(MF, OutLocs, VarLocIDs, "Final OutLocs", dbgs())); |
| LLVM_DEBUG(printVarLocInMBB(MF, InLocs, VarLocIDs, "Final InLocs", dbgs())); |
| return Changed; |
| } |
| |
| LDVImpl * |
| llvm::makeVarLocBasedLiveDebugValues() |
| { |
| return new VarLocBasedLDV(); |
| } |