//===- 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, and target indices) 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, the set of /// machine-locations that currently describe it (a single location for /// DBG_VALUE or multiple for DBG_VALUE_LIST), and the DBG_VALUE inst that /// specifies the location. Each VarLoc is indexed in the (function-scope) \p /// VarLocMap, giving each VarLoc a set of unique indexes, each of which /// corresponds to one of the VarLoc's machine-locations and can be used to /// lookup the VarLoc in the VarLocMap. Rather than operate directly on machine /// locations, the dataflow analysis in this pass identifies locations by their /// indices in the VarLocMap, meaning all the variable locations in a block can /// be described by a sparse vector of VarLocMap indices. /// /// 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 debug value instructions /// 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/BinaryFormat/Dwarf.h" #include "llvm/CodeGen/LexicalScopes.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineFunction.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/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/DebugInfoMetadata.h" #include "llvm/IR/DebugLoc.h" #include "llvm/IR/Function.h" #include "llvm/MC/MCRegisterInfo.h" #include "llvm/Support/Casting.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 <map> #include <optional> #include <queue> #include <tuple> #include <utility> #include <vector> usingnamespacellvm; #define DEBUG_TYPE … STATISTIC(NumInserted, "Number of DBG_VALUE instructions inserted"); /// 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) { … } namespace { // Max out the number of statically allocated elements in DefinedRegsSet, as // this prevents fallback to std::set::count() operations. DefinedRegsSet; // The IDs in this set correspond to MachineLocs in VarLocs, as well as VarLocs // that represent Entry Values; every VarLoc in the set will also appear // exactly once at Location=0. // As a result, each VarLoc may appear more than once in this "set", but each // range corresponding to a Reg, SpillLoc, or EntryValue type will still be a // "true" set (i.e. each VarLoc may appear only once), and the range Location=0 // is the set of all VarLocs. VarLocSet; /// 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 { … }; // Simple Set for storing all the VarLoc Indices at a Location bucket. VarLocsInRange; // Vector of all `LocIndex`s for a given VarLoc; the same Location should not // appear in any two of these, as each VarLoc appears at most once in any // Location bucket. LocIndices; class VarLocBasedLDV : public LDVImpl { … }; } // end anonymous namespace //===----------------------------------------------------------------------===// // Implementation //===----------------------------------------------------------------------===// VarLocBasedLDV::VarLocBasedLDV() = default; VarLocBasedLDV::~VarLocBasedLDV() = default; /// 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) { … } void VarLocBasedLDV::OpenRangesSet::erase(const VarLocsInRange &KillSet, const VarLocMap &VarLocIDs, LocIndex::u32_location_t Location) { … } void VarLocBasedLDV::OpenRangesSet::insertFromLocSet(const VarLocSet &ToLoad, const VarLocMap &Map) { … } void VarLocBasedLDV::OpenRangesSet::insert(LocIndices VarLocIDs, const VarLoc &VL) { … } /// Return the Loc ID of an entry value backup location, if it exists for the /// variable. std::optional<LocIndices> VarLocBasedLDV::OpenRangesSet::getEntryValueBackup(DebugVariable Var) { … } void VarLocBasedLDV::collectIDsForRegs(VarLocsInRange &Collected, const DefinedRegsSet &Regs, const VarLocSet &CollectFrom, const VarLocMap &VarLocIDs) { … } void VarLocBasedLDV::getUsedRegs(const VarLocSet &CollectFrom, SmallVectorImpl<Register> &UsedRegs) const { … } //===----------------------------------------------------------------------===// // 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; SmallVector<VarLoc, 32> VarLocs; collectAllVarLocs(VarLocs, L, VarLocIDs); Out << "MBB: " << BB.getNumber() << ":\n"; for (const VarLoc &VL : VarLocs) { Out << " Var: " << VL.Var.getVariable()->getName(); Out << " MI: "; VL.dump(TRI, TII, Out); } } Out << "\n"; } #endif VarLocBasedLDV::VarLoc::SpillLoc VarLocBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) { … } /// Do cleanup of \p EntryValTransfers created by \p TRInst, by removing the /// Transfer, which uses the to-be-deleted \p EntryVL. void VarLocBasedLDV::cleanupEntryValueTransfers( const MachineInstr *TRInst, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, const VarLoc &EntryVL, InstToEntryLocMap &EntryValTransfers) { … } /// 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 and do the cleanup of /// emitted Entry Value Transfers, otherwise return false. void VarLocBasedLDV::removeEntryValue(const MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, const VarLoc &EntryVL, InstToEntryLocMap &EntryValTransfers, RegDefToInstMap &RegSetInstrs) { … } /// 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, InstToEntryLocMap &EntryValTransfers, RegDefToInstMap &RegSetInstrs) { … } // This should be removed later, doesn't fit the new design. void VarLocBasedLDV::collectAllVarLocs(SmallVectorImpl<VarLoc> &Collected, const VarLocSet &CollectFrom, const VarLocMap &VarLocIDs) { … } /// Turn the entry value backup locations into primary locations. void VarLocBasedLDV::emitEntryValues(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, InstToEntryLocMap &EntryValTransfers, VarLocsInRange &KillSet) { … } /// 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, const VarLoc::MachineLoc &OldLoc, Register NewReg) { … } /// A definition of a register may mark the end of a range. void VarLocBasedLDV::transferRegisterDef(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, InstToEntryLocMap &EntryValTransfers, RegDefToInstMap &RegSetInstrs) { … } void VarLocBasedLDV::transferWasmDef(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs) { … } bool VarLocBasedLDV::isSpillInstruction(const MachineInstr &MI, MachineFunction *MF) { … } bool VarLocBasedLDV::isLocationSpill(const MachineInstr &MI, MachineFunction *MF, Register &Reg) { … } std::optional<VarLocBasedLDV::VarLoc::SpillLoc> VarLocBasedLDV::isRestoreInstruction(const MachineInstr &MI, MachineFunction *MF, Register &Reg) { … } /// 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) { … } /// 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) { … } /// Terminate all open ranges at the end of the current basic block. bool VarLocBasedLDV::transferTerminator(MachineBasicBlock *CurMBB, OpenRangesSet &OpenRanges, VarLocInMBB &OutLocs, const VarLocMap &VarLocIDs) { … } /// 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) { … } /// This routine creates OpenRanges. void VarLocBasedLDV::process(MachineInstr &MI, OpenRangesSet &OpenRanges, VarLocMap &VarLocIDs, TransferMap &Transfers, InstToEntryLocMap &EntryValTransfers, RegDefToInstMap &RegSetInstrs) { … } /// 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) { … } void VarLocBasedLDV::flushPendingLocs(VarLocInMBB &PendingInLocs, VarLocMap &VarLocIDs) { … } bool VarLocBasedLDV::isEntryValueCandidate( const MachineInstr &MI, const DefinedRegsSet &DefinedRegs) const { … } /// Collect all register defines (including aliases) for the given instruction. static void collectRegDefs(const MachineInstr &MI, DefinedRegsSet &Regs, const TargetRegisterInfo *TRI) { … } /// 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) { … } /// Calculate the liveness information for the given machine function and /// extend ranges across basic blocks. bool VarLocBasedLDV::ExtendRanges(MachineFunction &MF, MachineDominatorTree *DomTree, TargetPassConfig *TPC, unsigned InputBBLimit, unsigned InputDbgValLimit) { … } LDVImpl * llvm::makeVarLocBasedLiveDebugValues() { … }