brintos / llvm-project-archived public Read only

1//===- InstrRefBasedImpl.cpp - Tracking Debug Value MIs -------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8/// \file InstrRefBasedImpl.cpp9///10/// This is a separate implementation of LiveDebugValues, see11/// LiveDebugValues.cpp and VarLocBasedImpl.cpp for more information.12///13/// This pass propagates variable locations between basic blocks, resolving14/// control flow conflicts between them. The problem is SSA construction, where15/// each debug instruction assigns the *value* that a variable has, and every16/// instruction where the variable is in scope uses that variable. The resulting17/// map of instruction-to-value is then translated into a register (or spill)18/// location for each variable over each instruction.19///20/// The primary difference from normal SSA construction is that we cannot21/// _create_ PHI values that contain variable values. CodeGen has already22/// completed, and we can't alter it just to make debug-info complete. Thus:23/// we can identify function positions where we would like a PHI value for a24/// variable, but must search the MachineFunction to see whether such a PHI is25/// available. If no such PHI exists, the variable location must be dropped.26///27/// To achieve this, we perform two kinds of analysis. First, we identify28/// every value defined by every instruction (ignoring those that only move29/// another value), then re-compute an SSA-form representation of the30/// MachineFunction, using value propagation to eliminate any un-necessary31/// PHI values. This gives us a map of every value computed in the function,32/// and its location within the register file / stack.33///34/// Secondly, for each variable we perform the same analysis, where each debug35/// instruction is considered a def, and every instruction where the variable36/// is in lexical scope as a use. Value propagation is used again to eliminate37/// any un-necessary PHIs. This gives us a map of each variable to the value38/// it should have in a block.39///40/// Once both are complete, we have two maps for each block:41///  * Variables to the values they should have,42///  * Values to the register / spill slot they are located in.43/// After which we can marry-up variable values with a location, and emit44/// DBG_VALUE instructions specifying those locations. Variable locations may45/// be dropped in this process due to the desired variable value not being46/// resident in any machine location, or because there is no PHI value in any47/// location that accurately represents the desired value.  The building of48/// location lists for each block is left to DbgEntityHistoryCalculator.49///50/// This pass is kept efficient because the size of the first SSA problem51/// is proportional to the working-set size of the function, which the compiler52/// tries to keep small. (It's also proportional to the number of blocks).53/// Additionally, we repeatedly perform the second SSA problem analysis with54/// only the variables and blocks in a single lexical scope, exploiting their55/// locality.56///57/// ### Terminology58///59/// A machine location is a register or spill slot, a value is something that's60/// defined by an instruction or PHI node, while a variable value is the value61/// assigned to a variable. A variable location is a machine location, that must62/// contain the appropriate variable value. A value that is a PHI node is63/// occasionally called an mphi.64///65/// The first SSA problem is the "machine value location" problem,66/// because we're determining which machine locations contain which values.67/// The "locations" are constant: what's unknown is what value they contain.68///69/// The second SSA problem (the one for variables) is the "variable value70/// problem", because it's determining what values a variable has, rather than71/// what location those values are placed in.72///73/// TODO:74///   Overlapping fragments75///   Entry values76///   Add back DEBUG statements for debugging this77///   Collect statistics78///79//===----------------------------------------------------------------------===//80 81#include "llvm/ADT/DenseMap.h"82#include "llvm/ADT/PostOrderIterator.h"83#include "llvm/ADT/STLExtras.h"84#include "llvm/ADT/SmallPtrSet.h"85#include "llvm/ADT/SmallSet.h"86#include "llvm/ADT/SmallVector.h"87#include "llvm/BinaryFormat/Dwarf.h"88#include "llvm/CodeGen/LexicalScopes.h"89#include "llvm/CodeGen/MachineBasicBlock.h"90#include "llvm/CodeGen/MachineDominators.h"91#include "llvm/CodeGen/MachineFrameInfo.h"92#include "llvm/CodeGen/MachineFunction.h"93#include "llvm/CodeGen/MachineInstr.h"94#include "llvm/CodeGen/MachineInstrBuilder.h"95#include "llvm/CodeGen/MachineInstrBundle.h"96#include "llvm/CodeGen/MachineMemOperand.h"97#include "llvm/CodeGen/MachineOperand.h"98#include "llvm/CodeGen/PseudoSourceValue.h"99#include "llvm/CodeGen/TargetFrameLowering.h"100#include "llvm/CodeGen/TargetInstrInfo.h"101#include "llvm/CodeGen/TargetLowering.h"102#include "llvm/CodeGen/TargetRegisterInfo.h"103#include "llvm/CodeGen/TargetSubtargetInfo.h"104#include "llvm/Config/llvm-config.h"105#include "llvm/IR/DebugInfoMetadata.h"106#include "llvm/IR/DebugLoc.h"107#include "llvm/IR/Function.h"108#include "llvm/MC/MCRegisterInfo.h"109#include "llvm/Support/Casting.h"110#include "llvm/Support/Compiler.h"111#include "llvm/Support/Debug.h"112#include "llvm/Support/GenericIteratedDominanceFrontier.h"113#include "llvm/Support/TypeSize.h"114#include "llvm/Support/raw_ostream.h"115#include "llvm/Target/TargetMachine.h"116#include "llvm/Transforms/Utils/SSAUpdaterImpl.h"117#include <algorithm>118#include <cassert>119#include <climits>120#include <cstdint>121#include <functional>122#include <queue>123#include <tuple>124#include <utility>125#include <vector>126 127#include "InstrRefBasedImpl.h"128#include "LiveDebugValues.h"129#include <optional>130 131using namespace llvm;132using namespace LiveDebugValues;133 134// SSAUpdaterImple sets DEBUG_TYPE, change it.135#undef DEBUG_TYPE136#define DEBUG_TYPE "livedebugvalues"137 138// Act more like the VarLoc implementation, by propagating some locations too139// far and ignoring some transfers.140static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,141                                   cl::desc("Act like old LiveDebugValues did"),142                                   cl::init(false));143 144// Limit for the maximum number of stack slots we should track, past which we145// will ignore any spills. InstrRefBasedLDV gathers detailed information on all146// stack slots which leads to high memory consumption, and in some scenarios147// (such as asan with very many locals) the working set of the function can be148// very large, causing many spills. In these scenarios, it is very unlikely that149// the developer has hundreds of variables live at the same time that they're150// carefully thinking about -- instead, they probably autogenerated the code.151// When this happens, gracefully stop tracking excess spill slots, rather than152// consuming all the developer's memory.153static cl::opt<unsigned>154    StackWorkingSetLimit("livedebugvalues-max-stack-slots", cl::Hidden,155                         cl::desc("livedebugvalues-stack-ws-limit"),156                         cl::init(250));157 158DbgOpID DbgOpID::UndefID = DbgOpID(0xffffffff);159 160/// Tracker for converting machine value locations and variable values into161/// variable locations (the output of LiveDebugValues), recorded as DBG_VALUEs162/// specifying block live-in locations and transfers within blocks.163///164/// Operating on a per-block basis, this class takes a (pre-loaded) MLocTracker165/// and must be initialized with the set of variable values that are live-in to166/// the block. The caller then repeatedly calls process(). TransferTracker picks167/// out variable locations for the live-in variable values (if there _is_ a168/// location) and creates the corresponding DBG_VALUEs. Then, as the block is169/// stepped through, transfers of values between machine locations are170/// identified and if profitable, a DBG_VALUE created.171///172/// This is where debug use-before-defs would be resolved: a variable with an173/// unavailable value could materialize in the middle of a block, when the174/// value becomes available. Or, we could detect clobbers and re-specify the175/// variable in a backup location. (XXX these are unimplemented).176class TransferTracker {177public:178  const TargetInstrInfo *TII;179  const TargetLowering *TLI;180  /// This machine location tracker is assumed to always contain the up-to-date181  /// value mapping for all machine locations. TransferTracker only reads182  /// information from it. (XXX make it const?)183  MLocTracker *MTracker;184  MachineFunction &MF;185  const DebugVariableMap &DVMap;186  bool ShouldEmitDebugEntryValues;187 188  /// Record of all changes in variable locations at a block position. Awkwardly189  /// we allow inserting either before or after the point: MBB != nullptr190  /// indicates it's before, otherwise after.191  struct Transfer {192    MachineBasicBlock::instr_iterator Pos; /// Position to insert DBG_VALUes193    MachineBasicBlock *MBB; /// non-null if we should insert after.194    /// Vector of DBG_VALUEs to insert. Store with their DebugVariableID so that195    /// they can be sorted into a stable order for emission at a later time.196    SmallVector<std::pair<DebugVariableID, MachineInstr *>, 4> Insts;197  };198 199  /// Stores the resolved operands (machine locations and constants) and200  /// qualifying meta-information needed to construct a concrete DBG_VALUE-like201  /// instruction.202  struct ResolvedDbgValue {203    SmallVector<ResolvedDbgOp> Ops;204    DbgValueProperties Properties;205 206    ResolvedDbgValue(SmallVectorImpl<ResolvedDbgOp> &Ops,207                     DbgValueProperties Properties)208        : Ops(Ops.begin(), Ops.end()), Properties(Properties) {}209 210    /// Returns all the LocIdx values used in this struct, in the order in which211    /// they appear as operands in the debug value; may contain duplicates.212    auto loc_indices() const {213      return map_range(214          make_filter_range(215              Ops, [](const ResolvedDbgOp &Op) { return !Op.IsConst; }),216          [](const ResolvedDbgOp &Op) { return Op.Loc; });217    }218  };219 220  /// Collection of transfers (DBG_VALUEs) to be inserted.221  SmallVector<Transfer, 32> Transfers;222 223  /// Local cache of what-value-is-in-what-LocIdx. Used to identify differences224  /// between TransferTrackers view of variable locations and MLocTrackers. For225  /// example, MLocTracker observes all clobbers, but TransferTracker lazily226  /// does not.227  SmallVector<ValueIDNum, 32> VarLocs;228 229  /// Map from LocIdxes to which DebugVariables are based that location.230  /// Mantained while stepping through the block. Not accurate if231  /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx].232  DenseMap<LocIdx, SmallSet<DebugVariableID, 4>> ActiveMLocs;233 234  /// Map from DebugVariable to it's current location and qualifying meta235  /// information. To be used in conjunction with ActiveMLocs to construct236  /// enough information for the DBG_VALUEs for a particular LocIdx.237  DenseMap<DebugVariableID, ResolvedDbgValue> ActiveVLocs;238 239  /// Temporary cache of DBG_VALUEs to be entered into the Transfers collection.240  SmallVector<std::pair<DebugVariableID, MachineInstr *>, 4> PendingDbgValues;241 242  /// Record of a use-before-def: created when a value that's live-in to the243  /// current block isn't available in any machine location, but it will be244  /// defined in this block.245  struct UseBeforeDef {246    /// Value of this variable, def'd in block.247    SmallVector<DbgOp> Values;248    /// Identity of this variable.249    DebugVariableID VarID;250    /// Additional variable properties.251    DbgValueProperties Properties;252    UseBeforeDef(ArrayRef<DbgOp> Values, DebugVariableID VarID,253                 const DbgValueProperties &Properties)254        : Values(Values), VarID(VarID), Properties(Properties) {}255  };256 257  /// Map from instruction index (within the block) to the set of UseBeforeDefs258  /// that become defined at that instruction.259  DenseMap<unsigned, SmallVector<UseBeforeDef, 1>> UseBeforeDefs;260 261  /// The set of variables that are in UseBeforeDefs and can become a location262  /// once the relevant value is defined. An element being erased from this263  /// collection prevents the use-before-def materializing.264  DenseSet<DebugVariableID> UseBeforeDefVariables;265 266  const TargetRegisterInfo &TRI;267  const BitVector &CalleeSavedRegs;268 269  TransferTracker(const TargetInstrInfo *TII, MLocTracker *MTracker,270                  MachineFunction &MF, const DebugVariableMap &DVMap,271                  const TargetRegisterInfo &TRI,272                  const BitVector &CalleeSavedRegs,273                  bool ShouldEmitDebugEntryValues)274      : TII(TII), MTracker(MTracker), MF(MF), DVMap(DVMap), TRI(TRI),275        CalleeSavedRegs(CalleeSavedRegs) {276    TLI = MF.getSubtarget().getTargetLowering();277    this->ShouldEmitDebugEntryValues = ShouldEmitDebugEntryValues;278  }279 280  bool isCalleeSaved(LocIdx L) const {281    unsigned Reg = MTracker->LocIdxToLocID[L];282    if (Reg >= MTracker->NumRegs)283      return false;284    for (MCRegAliasIterator RAI(Reg, &TRI, true); RAI.isValid(); ++RAI)285      if (CalleeSavedRegs.test((*RAI).id()))286        return true;287    return false;288  };289 290  // An estimate of the expected lifespan of values at a machine location, with291  // a greater value corresponding to a longer expected lifespan, i.e. spill292  // slots generally live longer than callee-saved registers which generally293  // live longer than non-callee-saved registers. The minimum value of 0294  // corresponds to an illegal location that cannot have a "lifespan" at all.295  enum class LocationQuality : unsigned char {296    Illegal = 0,297    Register,298    CalleeSavedRegister,299    SpillSlot,300    Best = SpillSlot301  };302 303  class LocationAndQuality {304    unsigned Location : 24;305    unsigned Quality : 8;306 307  public:308    LocationAndQuality() : Location(0), Quality(0) {}309    LocationAndQuality(LocIdx L, LocationQuality Q)310        : Location(L.asU64()), Quality(static_cast<unsigned>(Q)) {}311    LocIdx getLoc() const {312      if (!Quality)313        return LocIdx::MakeIllegalLoc();314      return LocIdx(Location);315    }316    LocationQuality getQuality() const { return LocationQuality(Quality); }317    bool isIllegal() const { return !Quality; }318    bool isBest() const { return getQuality() == LocationQuality::Best; }319  };320 321  using ValueLocPair = std::pair<ValueIDNum, LocationAndQuality>;322 323  static inline bool ValueToLocSort(const ValueLocPair &A,324                                    const ValueLocPair &B) {325    return A.first < B.first;326  };327 328  // Returns the LocationQuality for the location L iff the quality of L is329  // is strictly greater than the provided minimum quality.330  std::optional<LocationQuality>331  getLocQualityIfBetter(LocIdx L, LocationQuality Min) const {332    if (L.isIllegal())333      return std::nullopt;334    if (Min >= LocationQuality::SpillSlot)335      return std::nullopt;336    if (MTracker->isSpill(L))337      return LocationQuality::SpillSlot;338    if (Min >= LocationQuality::CalleeSavedRegister)339      return std::nullopt;340    if (isCalleeSaved(L))341      return LocationQuality::CalleeSavedRegister;342    if (Min >= LocationQuality::Register)343      return std::nullopt;344    return LocationQuality::Register;345  }346 347  /// For a variable \p Var with the live-in value \p Value, attempts to resolve348  /// the DbgValue to a concrete DBG_VALUE, emitting that value and loading the349  /// tracking information to track Var throughout the block.350  /// \p ValueToLoc is a map containing the best known location for every351  ///    ValueIDNum that Value may use.352  /// \p MBB is the basic block that we are loading the live-in value for.353  /// \p DbgOpStore is the map containing the DbgOpID->DbgOp mapping needed to354  ///    determine the values used by Value.355  void loadVarInloc(MachineBasicBlock &MBB, DbgOpIDMap &DbgOpStore,356                    const SmallVectorImpl<ValueLocPair> &ValueToLoc,357                    DebugVariableID VarID, DbgValue Value) {358    SmallVector<DbgOp> DbgOps;359    SmallVector<ResolvedDbgOp> ResolvedDbgOps;360    bool IsValueValid = true;361    unsigned LastUseBeforeDef = 0;362    bool DbgLocAvailableAndIsEntryVal = false;363 364    // If every value used by the incoming DbgValue is available at block365    // entry, ResolvedDbgOps will contain the machine locations/constants for366    // those values and will be used to emit a debug location.367    // If one or more values are not yet available, but will all be defined in368    // this block, then LastUseBeforeDef will track the instruction index in369    // this BB at which the last of those values is defined, DbgOps will370    // contain the values that we will emit when we reach that instruction.371    // If one or more values are undef or not available throughout this block,372    // and we can't recover as an entry value, we set IsValueValid=false and373    // skip this variable.374    for (DbgOpID ID : Value.getDbgOpIDs()) {375      DbgOp Op = DbgOpStore.find(ID);376      DbgOps.push_back(Op);377      if (ID.isUndef()) {378        IsValueValid = false;379        break;380      }381      if (ID.isConst()) {382        ResolvedDbgOps.push_back(Op.MO);383        continue;384      }385 386      // Search for the desired ValueIDNum, to examine the best location found387      // for it. Use an empty ValueLocPair to search for an entry in ValueToLoc.388      const ValueIDNum &Num = Op.ID;389      ValueLocPair Probe(Num, LocationAndQuality());390      auto ValuesPreferredLoc =391          llvm::lower_bound(ValueToLoc, Probe, ValueToLocSort);392 393      // There must be a legitimate entry found for Num.394      assert(ValuesPreferredLoc != ValueToLoc.end() &&395             ValuesPreferredLoc->first == Num);396 397      if (ValuesPreferredLoc->second.isIllegal()) {398        // If it's a def that occurs in this block, register it as a399        // use-before-def to be resolved as we step through the block.400        // Continue processing values so that we add any other UseBeforeDef401        // entries needed for later.402        if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI()) {403          LastUseBeforeDef = std::max(LastUseBeforeDef,404                                      static_cast<unsigned>(Num.getInst()));405          continue;406        }407        recoverAsEntryValue(VarID, Value.Properties, Num);408        IsValueValid = false;409        break;410      }411 412      // Defer modifying ActiveVLocs until after we've confirmed we have a413      // live range.414      LocIdx M = ValuesPreferredLoc->second.getLoc();415      ResolvedDbgOps.push_back(M);416      if (Value.Properties.DIExpr->isEntryValue())417        DbgLocAvailableAndIsEntryVal = true;418    }419 420    // If we cannot produce a valid value for the LiveIn value within this421    // block, skip this variable.422    if (!IsValueValid)423      return;424 425    // Add UseBeforeDef entry for the last value to be defined in this block.426    if (LastUseBeforeDef) {427      addUseBeforeDef(VarID, Value.Properties, DbgOps, LastUseBeforeDef);428      return;429    }430 431    auto &[Var, DILoc] = DVMap.lookupDVID(VarID);432    PendingDbgValues.push_back(433        std::make_pair(VarID, &*MTracker->emitLoc(ResolvedDbgOps, Var, DILoc,434                                                  Value.Properties)));435 436    // If the location is available at block entry and is an entry value, skip437    // tracking and recording thr transfer.438    if (DbgLocAvailableAndIsEntryVal)439      return;440 441    // The LiveIn value is available at block entry, begin tracking and record442    // the transfer.443    for (const ResolvedDbgOp &Op : ResolvedDbgOps)444      if (!Op.IsConst)445        ActiveMLocs[Op.Loc].insert(VarID);446    auto NewValue = ResolvedDbgValue{ResolvedDbgOps, Value.Properties};447    auto Result = ActiveVLocs.insert(std::make_pair(VarID, NewValue));448    if (!Result.second)449      Result.first->second = NewValue;450  }451 452  /// Load object with live-in variable values. \p mlocs contains the live-in453  /// values in each machine location, while \p vlocs the live-in variable454  /// values. This method picks variable locations for the live-in variables,455  /// creates DBG_VALUEs and puts them in #Transfers, then prepares the other456  /// object fields to track variable locations as we step through the block.457  /// FIXME: could just examine mloctracker instead of passing in \p mlocs?458  void459  loadInlocs(MachineBasicBlock &MBB, ValueTable &MLocs, DbgOpIDMap &DbgOpStore,460             const SmallVectorImpl<std::pair<DebugVariableID, DbgValue>> &VLocs,461             unsigned NumLocs) {462    ActiveMLocs.clear();463    ActiveVLocs.clear();464    VarLocs.clear();465    VarLocs.reserve(NumLocs);466    UseBeforeDefs.clear();467    UseBeforeDefVariables.clear();468 469    // Mapping of the preferred locations for each value. Collected into this470    // vector then sorted for easy searching.471    SmallVector<ValueLocPair, 16> ValueToLoc;472 473    // Initialized the preferred-location map with illegal locations, to be474    // filled in later.475    for (const auto &VLoc : VLocs)476      if (VLoc.second.Kind == DbgValue::Def)477        for (DbgOpID OpID : VLoc.second.getDbgOpIDs())478          if (!OpID.ID.IsConst)479            ValueToLoc.push_back(480                {DbgOpStore.find(OpID).ID, LocationAndQuality()});481 482    llvm::sort(ValueToLoc, ValueToLocSort);483    ActiveMLocs.reserve(VLocs.size());484    ActiveVLocs.reserve(VLocs.size());485 486    // Produce a map of value numbers to the current machine locs they live487    // in. When emulating VarLocBasedImpl, there should only be one488    // location; when not, we get to pick.489    for (auto Location : MTracker->locations()) {490      LocIdx Idx = Location.Idx;491      ValueIDNum &VNum = MLocs[Idx.asU64()];492      if (VNum == ValueIDNum::EmptyValue)493        continue;494      VarLocs.push_back(VNum);495 496      // Is there a variable that wants a location for this value? If not, skip.497      ValueLocPair Probe(VNum, LocationAndQuality());498      auto VIt = llvm::lower_bound(ValueToLoc, Probe, ValueToLocSort);499      if (VIt == ValueToLoc.end() || VIt->first != VNum)500        continue;501 502      auto &Previous = VIt->second;503      // If this is the first location with that value, pick it. Otherwise,504      // consider whether it's a "longer term" location.505      std::optional<LocationQuality> ReplacementQuality =506          getLocQualityIfBetter(Idx, Previous.getQuality());507      if (ReplacementQuality)508        Previous = LocationAndQuality(Idx, *ReplacementQuality);509    }510 511    // Now map variables to their picked LocIdxes.512    for (const auto &Var : VLocs) {513      loadVarInloc(MBB, DbgOpStore, ValueToLoc, Var.first, Var.second);514    }515    flushDbgValues(MBB.begin(), &MBB);516  }517 518  /// Record that \p Var has value \p ID, a value that becomes available519  /// later in the function.520  void addUseBeforeDef(DebugVariableID VarID,521                       const DbgValueProperties &Properties,522                       const SmallVectorImpl<DbgOp> &DbgOps, unsigned Inst) {523    UseBeforeDefs[Inst].emplace_back(DbgOps, VarID, Properties);524    UseBeforeDefVariables.insert(VarID);525  }526 527  /// After the instruction at index \p Inst and position \p pos has been528  /// processed, check whether it defines a variable value in a use-before-def.529  /// If so, and the variable value hasn't changed since the start of the530  /// block, create a DBG_VALUE.531  void checkInstForNewValues(unsigned Inst, MachineBasicBlock::iterator pos) {532    auto MIt = UseBeforeDefs.find(Inst);533    if (MIt == UseBeforeDefs.end())534      return;535 536    // Map of values to the locations that store them for every value used by537    // the variables that may have become available.538    SmallDenseMap<ValueIDNum, LocationAndQuality> ValueToLoc;539 540    // Populate ValueToLoc with illegal default mappings for every value used by541    // any UseBeforeDef variables for this instruction.542    for (auto &Use : MIt->second) {543      if (!UseBeforeDefVariables.count(Use.VarID))544        continue;545 546      for (DbgOp &Op : Use.Values) {547        assert(!Op.isUndef() && "UseBeforeDef erroneously created for a "548                                "DbgValue with undef values.");549        if (Op.IsConst)550          continue;551 552        ValueToLoc.insert({Op.ID, LocationAndQuality()});553      }554    }555 556    // Exit early if we have no DbgValues to produce.557    if (ValueToLoc.empty())558      return;559 560    // Determine the best location for each desired value.561    for (auto Location : MTracker->locations()) {562      LocIdx Idx = Location.Idx;563      ValueIDNum &LocValueID = Location.Value;564 565      // Is there a variable that wants a location for this value? If not, skip.566      auto VIt = ValueToLoc.find(LocValueID);567      if (VIt == ValueToLoc.end())568        continue;569 570      auto &Previous = VIt->second;571      // If this is the first location with that value, pick it. Otherwise,572      // consider whether it's a "longer term" location.573      std::optional<LocationQuality> ReplacementQuality =574          getLocQualityIfBetter(Idx, Previous.getQuality());575      if (ReplacementQuality)576        Previous = LocationAndQuality(Idx, *ReplacementQuality);577    }578 579    // Using the map of values to locations, produce a final set of values for580    // this variable.581    for (auto &Use : MIt->second) {582      if (!UseBeforeDefVariables.count(Use.VarID))583        continue;584 585      SmallVector<ResolvedDbgOp> DbgOps;586 587      for (DbgOp &Op : Use.Values) {588        if (Op.IsConst) {589          DbgOps.push_back(Op.MO);590          continue;591        }592        LocIdx NewLoc = ValueToLoc.find(Op.ID)->second.getLoc();593        if (NewLoc.isIllegal())594          break;595        DbgOps.push_back(NewLoc);596      }597 598      // If at least one value used by this debug value is no longer available,599      // i.e. one of the values was killed before we finished defining all of600      // the values used by this variable, discard.601      if (DbgOps.size() != Use.Values.size())602        continue;603 604      // Otherwise, we're good to go.605      auto &[Var, DILoc] = DVMap.lookupDVID(Use.VarID);606      PendingDbgValues.push_back(std::make_pair(607          Use.VarID, MTracker->emitLoc(DbgOps, Var, DILoc, Use.Properties)));608    }609    flushDbgValues(pos, nullptr);610  }611 612  /// Helper to move created DBG_VALUEs into Transfers collection.613  void flushDbgValues(MachineBasicBlock::iterator Pos, MachineBasicBlock *MBB) {614    if (PendingDbgValues.size() == 0)615      return;616 617    // Pick out the instruction start position.618    MachineBasicBlock::instr_iterator BundleStart;619    if (MBB && Pos == MBB->begin())620      BundleStart = MBB->instr_begin();621    else622      BundleStart = getBundleStart(Pos->getIterator());623 624    Transfers.push_back({BundleStart, MBB, PendingDbgValues});625    PendingDbgValues.clear();626  }627 628  bool isEntryValueVariable(const DebugVariable &Var,629                            const DIExpression *Expr) const {630    if (!Var.getVariable()->isParameter())631      return false;632 633    if (Var.getInlinedAt())634      return false;635 636    if (Expr->getNumElements() > 0 && !Expr->isDeref())637      return false;638 639    return true;640  }641 642  bool isEntryValueValue(const ValueIDNum &Val) const {643    // Must be in entry block (block number zero), and be a PHI / live-in value.644    if (Val.getBlock() || !Val.isPHI())645      return false;646 647    // Entry values must enter in a register.648    if (MTracker->isSpill(Val.getLoc()))649      return false;650 651    Register SP = TLI->getStackPointerRegisterToSaveRestore();652    Register FP = TRI.getFrameRegister(MF);653    Register Reg = MTracker->LocIdxToLocID[Val.getLoc()];654    return Reg != SP && Reg != FP;655  }656 657  bool recoverAsEntryValue(DebugVariableID VarID,658                           const DbgValueProperties &Prop,659                           const ValueIDNum &Num) {660    // Is this variable location a candidate to be an entry value. First,661    // should we be trying this at all?662    if (!ShouldEmitDebugEntryValues)663      return false;664 665    const DIExpression *DIExpr = Prop.DIExpr;666 667    // We don't currently emit entry values for DBG_VALUE_LISTs.668    if (Prop.IsVariadic) {669      // If this debug value can be converted to be non-variadic, then do so;670      // otherwise give up.671      auto NonVariadicExpression =672          DIExpression::convertToNonVariadicExpression(DIExpr);673      if (!NonVariadicExpression)674        return false;675      DIExpr = *NonVariadicExpression;676    }677 678    auto &[Var, DILoc] = DVMap.lookupDVID(VarID);679 680    // If the expression is a DW_OP_entry_value, emit the variable location681    // as-is.682    if (DIExpr->isEntryValue()) {683      Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];684      MachineOperand MO = MachineOperand::CreateReg(Reg, false);685      PendingDbgValues.push_back(std::make_pair(686          VarID, &*emitMOLoc(MO, Var, {DIExpr, Prop.Indirect, false})));687      return true;688    }689 690    // Is the variable appropriate for entry values (i.e., is a parameter).691    if (!isEntryValueVariable(Var, DIExpr))692      return false;693 694    // Is the value assigned to this variable still the entry value?695    if (!isEntryValueValue(Num))696      return false;697 698    // Emit a variable location using an entry value expression.699    DIExpression *NewExpr =700        DIExpression::prepend(DIExpr, DIExpression::EntryValue);701    Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];702    MachineOperand MO = MachineOperand::CreateReg(Reg, false);703    PendingDbgValues.push_back(std::make_pair(704        VarID, &*emitMOLoc(MO, Var, {NewExpr, Prop.Indirect, false})));705    return true;706  }707 708  /// Change a variable value after encountering a DBG_VALUE inside a block.709  void redefVar(const MachineInstr &MI) {710    DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),711                      MI.getDebugLoc()->getInlinedAt());712    DbgValueProperties Properties(MI);713    DebugVariableID VarID = DVMap.getDVID(Var);714 715    // Ignore non-register locations, we don't transfer those.716    if (MI.isUndefDebugValue() || MI.getDebugExpression()->isEntryValue() ||717        all_of(MI.debug_operands(),718               [](const MachineOperand &MO) { return !MO.isReg(); })) {719      auto It = ActiveVLocs.find(VarID);720      if (It != ActiveVLocs.end()) {721        for (LocIdx Loc : It->second.loc_indices())722          ActiveMLocs[Loc].erase(VarID);723        ActiveVLocs.erase(It);724      }725      // Any use-before-defs no longer apply.726      UseBeforeDefVariables.erase(VarID);727      return;728    }729 730    SmallVector<ResolvedDbgOp> NewLocs;731    for (const MachineOperand &MO : MI.debug_operands()) {732      if (MO.isReg()) {733        // Any undef regs have already been filtered out above.734        Register Reg = MO.getReg();735        LocIdx NewLoc = MTracker->getRegMLoc(Reg);736        NewLocs.push_back(NewLoc);737      } else {738        NewLocs.push_back(MO);739      }740    }741 742    redefVar(MI, Properties, NewLocs);743  }744 745  /// Handle a change in variable location within a block. Terminate the746  /// variables current location, and record the value it now refers to, so747  /// that we can detect location transfers later on.748  void redefVar(const MachineInstr &MI, const DbgValueProperties &Properties,749                SmallVectorImpl<ResolvedDbgOp> &NewLocs) {750    DebugVariable Var(MI.getDebugVariable(), MI.getDebugExpression(),751                      MI.getDebugLoc()->getInlinedAt());752    DebugVariableID VarID = DVMap.getDVID(Var);753    // Any use-before-defs no longer apply.754    UseBeforeDefVariables.erase(VarID);755 756    // Erase any previous location.757    auto It = ActiveVLocs.find(VarID);758    if (It != ActiveVLocs.end()) {759      for (LocIdx Loc : It->second.loc_indices())760        ActiveMLocs[Loc].erase(VarID);761    }762 763    // If there _is_ no new location, all we had to do was erase.764    if (NewLocs.empty()) {765      if (It != ActiveVLocs.end())766        ActiveVLocs.erase(It);767      return;768    }769 770    SmallVector<std::pair<LocIdx, DebugVariableID>> LostMLocs;771    for (ResolvedDbgOp &Op : NewLocs) {772      if (Op.IsConst)773        continue;774 775      LocIdx NewLoc = Op.Loc;776 777      // Check whether our local copy of values-by-location in #VarLocs is out778      // of date. Wipe old tracking data for the location if it's been clobbered779      // in the meantime.780      if (MTracker->readMLoc(NewLoc) != VarLocs[NewLoc.asU64()]) {781        for (const auto &P : ActiveMLocs[NewLoc]) {782          auto LostVLocIt = ActiveVLocs.find(P);783          if (LostVLocIt != ActiveVLocs.end()) {784            for (LocIdx Loc : LostVLocIt->second.loc_indices()) {785              // Every active variable mapping for NewLoc will be cleared, no786              // need to track individual variables.787              if (Loc == NewLoc)788                continue;789              LostMLocs.emplace_back(Loc, P);790            }791          }792          ActiveVLocs.erase(P);793        }794        for (const auto &LostMLoc : LostMLocs)795          ActiveMLocs[LostMLoc.first].erase(LostMLoc.second);796        LostMLocs.clear();797        It = ActiveVLocs.find(VarID);798        ActiveMLocs[NewLoc.asU64()].clear();799        VarLocs[NewLoc.asU64()] = MTracker->readMLoc(NewLoc);800      }801 802      ActiveMLocs[NewLoc].insert(VarID);803    }804 805    if (It == ActiveVLocs.end()) {806      ActiveVLocs.insert(807          std::make_pair(VarID, ResolvedDbgValue(NewLocs, Properties)));808    } else {809      It->second.Ops.assign(NewLocs);810      It->second.Properties = Properties;811    }812  }813 814  /// Account for a location \p mloc being clobbered. Examine the variable815  /// locations that will be terminated: and try to recover them by using816  /// another location. Optionally, given \p MakeUndef, emit a DBG_VALUE to817  /// explicitly terminate a location if it can't be recovered.818  void clobberMloc(LocIdx MLoc, MachineBasicBlock::iterator Pos,819                   bool MakeUndef = true) {820    auto ActiveMLocIt = ActiveMLocs.find(MLoc);821    if (ActiveMLocIt == ActiveMLocs.end())822      return;823 824    // What was the old variable value?825    ValueIDNum OldValue = VarLocs[MLoc.asU64()];826    clobberMloc(MLoc, OldValue, Pos, MakeUndef);827  }828  /// Overload that takes an explicit value \p OldValue for when the value in829  /// \p MLoc has changed and the TransferTracker's locations have not been830  /// updated yet.831  void clobberMloc(LocIdx MLoc, ValueIDNum OldValue,832                   MachineBasicBlock::iterator Pos, bool MakeUndef = true) {833    auto ActiveMLocIt = ActiveMLocs.find(MLoc);834    if (ActiveMLocIt == ActiveMLocs.end())835      return;836 837    VarLocs[MLoc.asU64()] = ValueIDNum::EmptyValue;838 839    // Examine the remaining variable locations: if we can find the same value840    // again, we can recover the location.841    std::optional<LocIdx> NewLoc;842    for (auto Loc : MTracker->locations())843      if (Loc.Value == OldValue)844        NewLoc = Loc.Idx;845 846    // If there is no location, and we weren't asked to make the variable847    // explicitly undef, then stop here.848    if (!NewLoc && !MakeUndef) {849      // Try and recover a few more locations with entry values.850      for (DebugVariableID VarID : ActiveMLocIt->second) {851        auto &Prop = ActiveVLocs.find(VarID)->second.Properties;852        recoverAsEntryValue(VarID, Prop, OldValue);853      }854      flushDbgValues(Pos, nullptr);855      return;856    }857 858    // Examine all the variables based on this location.859    DenseSet<DebugVariableID> NewMLocs;860    // If no new location has been found, every variable that depends on this861    // MLoc is dead, so end their existing MLoc->Var mappings as well.862    SmallVector<std::pair<LocIdx, DebugVariableID>> LostMLocs;863    for (DebugVariableID VarID : ActiveMLocIt->second) {864      auto ActiveVLocIt = ActiveVLocs.find(VarID);865      // Re-state the variable location: if there's no replacement then NewLoc866      // is std::nullopt and a $noreg DBG_VALUE will be created. Otherwise, a867      // DBG_VALUE identifying the alternative location will be emitted.868      const DbgValueProperties &Properties = ActiveVLocIt->second.Properties;869 870      // Produce the new list of debug ops - an empty list if no new location871      // was found, or the existing list with the substitution MLoc -> NewLoc872      // otherwise.873      SmallVector<ResolvedDbgOp> DbgOps;874      if (NewLoc) {875        ResolvedDbgOp OldOp(MLoc);876        ResolvedDbgOp NewOp(*NewLoc);877        // Insert illegal ops to overwrite afterwards.878        DbgOps.insert(DbgOps.begin(), ActiveVLocIt->second.Ops.size(),879                      ResolvedDbgOp(LocIdx::MakeIllegalLoc()));880        replace_copy(ActiveVLocIt->second.Ops, DbgOps.begin(), OldOp, NewOp);881      }882 883      auto &[Var, DILoc] = DVMap.lookupDVID(VarID);884      PendingDbgValues.push_back(std::make_pair(885          VarID, &*MTracker->emitLoc(DbgOps, Var, DILoc, Properties)));886 887      // Update machine locations <=> variable locations maps. Defer updating888      // ActiveMLocs to avoid invalidating the ActiveMLocIt iterator.889      if (!NewLoc) {890        for (LocIdx Loc : ActiveVLocIt->second.loc_indices()) {891          if (Loc != MLoc)892            LostMLocs.emplace_back(Loc, VarID);893        }894        ActiveVLocs.erase(ActiveVLocIt);895      } else {896        ActiveVLocIt->second.Ops = DbgOps;897        NewMLocs.insert(VarID);898      }899    }900 901    // Remove variables from ActiveMLocs if they no longer use any other MLocs902    // due to being killed by this clobber.903    for (auto &LocVarIt : LostMLocs) {904      auto LostMLocIt = ActiveMLocs.find(LocVarIt.first);905      assert(LostMLocIt != ActiveMLocs.end() &&906             "Variable was using this MLoc, but ActiveMLocs[MLoc] has no "907             "entries?");908      LostMLocIt->second.erase(LocVarIt.second);909    }910 911    // We lazily track what locations have which values; if we've found a new912    // location for the clobbered value, remember it.913    if (NewLoc)914      VarLocs[NewLoc->asU64()] = OldValue;915 916    flushDbgValues(Pos, nullptr);917 918    // Commit ActiveMLoc changes.919    ActiveMLocIt->second.clear();920    if (!NewMLocs.empty())921      ActiveMLocs[*NewLoc].insert_range(NewMLocs);922  }923 924  /// Transfer variables based on \p Src to be based on \p Dst. This handles925  /// both register copies as well as spills and restores. Creates DBG_VALUEs926  /// describing the movement.927  void transferMlocs(LocIdx Src, LocIdx Dst, MachineBasicBlock::iterator Pos) {928    // Does Src still contain the value num we expect? If not, it's been929    // clobbered in the meantime, and our variable locations are stale.930    if (VarLocs[Src.asU64()] != MTracker->readMLoc(Src))931      return;932 933    // assert(ActiveMLocs[Dst].size() == 0);934    //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?935 936    // Move set of active variables from one location to another.937    auto MovingVars = ActiveMLocs[Src];938    ActiveMLocs[Dst].insert_range(MovingVars);939    VarLocs[Dst.asU64()] = VarLocs[Src.asU64()];940 941    // For each variable based on Src; create a location at Dst.942    ResolvedDbgOp SrcOp(Src);943    ResolvedDbgOp DstOp(Dst);944    for (DebugVariableID VarID : MovingVars) {945      auto ActiveVLocIt = ActiveVLocs.find(VarID);946      assert(ActiveVLocIt != ActiveVLocs.end());947 948      // Update all instances of Src in the variable's tracked values to Dst.949      llvm::replace(ActiveVLocIt->second.Ops, SrcOp, DstOp);950 951      auto &[Var, DILoc] = DVMap.lookupDVID(VarID);952      MachineInstr *MI = MTracker->emitLoc(ActiveVLocIt->second.Ops, Var, DILoc,953                                           ActiveVLocIt->second.Properties);954      PendingDbgValues.push_back(std::make_pair(VarID, MI));955    }956    ActiveMLocs[Src].clear();957    flushDbgValues(Pos, nullptr);958 959    // XXX XXX XXX "pretend to be old LDV" means dropping all tracking data960    // about the old location.961    if (EmulateOldLDV)962      VarLocs[Src.asU64()] = ValueIDNum::EmptyValue;963  }964 965  MachineInstrBuilder emitMOLoc(const MachineOperand &MO,966                                const DebugVariable &Var,967                                const DbgValueProperties &Properties) {968    DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0,969                                  Var.getVariable()->getScope(),970                                  const_cast<DILocation *>(Var.getInlinedAt()));971    auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE));972    MIB.add(MO);973    if (Properties.Indirect)974      MIB.addImm(0);975    else976      MIB.addReg(0);977    MIB.addMetadata(Var.getVariable());978    MIB.addMetadata(Properties.DIExpr);979    return MIB;980  }981};982 983//===----------------------------------------------------------------------===//984//            Implementation985//===----------------------------------------------------------------------===//986 987ValueIDNum ValueIDNum::EmptyValue = {UINT_MAX, UINT_MAX, UINT_MAX};988ValueIDNum ValueIDNum::TombstoneValue = {UINT_MAX, UINT_MAX, UINT_MAX - 1};989 990#ifndef NDEBUG991void ResolvedDbgOp::dump(const MLocTracker *MTrack) const {992  if (IsConst) {993    dbgs() << MO;994  } else {995    dbgs() << MTrack->LocIdxToName(Loc);996  }997}998void DbgOp::dump(const MLocTracker *MTrack) const {999  if (IsConst) {1000    dbgs() << MO;1001  } else if (!isUndef()) {1002    dbgs() << MTrack->IDAsString(ID);1003  }1004}1005void DbgOpID::dump(const MLocTracker *MTrack, const DbgOpIDMap *OpStore) const {1006  if (!OpStore) {1007    dbgs() << "ID(" << asU32() << ")";1008  } else {1009    OpStore->find(*this).dump(MTrack);1010  }1011}1012void DbgValue::dump(const MLocTracker *MTrack,1013                    const DbgOpIDMap *OpStore) const {1014  if (Kind == NoVal) {1015    dbgs() << "NoVal(" << BlockNo << ")";1016  } else if (Kind == VPHI || Kind == Def) {1017    if (Kind == VPHI)1018      dbgs() << "VPHI(" << BlockNo << ",";1019    else1020      dbgs() << "Def(";1021    for (unsigned Idx = 0; Idx < getDbgOpIDs().size(); ++Idx) {1022      getDbgOpID(Idx).dump(MTrack, OpStore);1023      if (Idx != 0)1024        dbgs() << ",";1025    }1026    dbgs() << ")";1027  }1028  if (Properties.Indirect)1029    dbgs() << " indir";1030  if (Properties.DIExpr)1031    dbgs() << " " << *Properties.DIExpr;1032}1033#endif1034 1035MLocTracker::MLocTracker(MachineFunction &MF, const TargetInstrInfo &TII,1036                         const TargetRegisterInfo &TRI,1037                         const TargetLowering &TLI)1038    : MF(MF), TII(TII), TRI(TRI), TLI(TLI),1039      LocIdxToIDNum(ValueIDNum::EmptyValue), LocIdxToLocID(0) {1040  NumRegs = TRI.getNumRegs();1041  reset();1042  LocIDToLocIdx.resize(NumRegs, LocIdx::MakeIllegalLoc());1043  assert(NumRegs < (1u << NUM_LOC_BITS)); // Detect bit packing failure1044 1045  // Always track SP. This avoids the implicit clobbering caused by regmasks1046  // from affectings its values. (LiveDebugValues disbelieves calls and1047  // regmasks that claim to clobber SP).1048  Register SP = TLI.getStackPointerRegisterToSaveRestore();1049  if (SP) {1050    unsigned ID = getLocID(SP);1051    (void)lookupOrTrackRegister(ID);1052 1053    for (MCRegAliasIterator RAI(SP, &TRI, true); RAI.isValid(); ++RAI)1054      SPAliases.insert(*RAI);1055  }1056 1057  // Build some common stack positions -- full registers being spilt to the1058  // stack.1059  StackSlotIdxes.insert({{8, 0}, 0});1060  StackSlotIdxes.insert({{16, 0}, 1});1061  StackSlotIdxes.insert({{32, 0}, 2});1062  StackSlotIdxes.insert({{64, 0}, 3});1063  StackSlotIdxes.insert({{128, 0}, 4});1064  StackSlotIdxes.insert({{256, 0}, 5});1065  StackSlotIdxes.insert({{512, 0}, 6});1066 1067  // Traverse all the subregister idxes, and ensure there's an index for them.1068  // Duplicates are no problem: we're interested in their position in the1069  // stack slot, we don't want to type the slot.1070  for (unsigned int I = 1; I < TRI.getNumSubRegIndices(); ++I) {1071    unsigned Size = TRI.getSubRegIdxSize(I);1072    unsigned Offs = TRI.getSubRegIdxOffset(I);1073    unsigned Idx = StackSlotIdxes.size();1074 1075    // Some subregs have -1, -2 and so forth fed into their fields, to mean1076    // special backend things. Ignore those.1077    if (Size > 60000 || Offs > 60000)1078      continue;1079 1080    StackSlotIdxes.insert({{Size, Offs}, Idx});1081  }1082 1083  // There may also be strange register class sizes (think x86 fp80s).1084  for (const TargetRegisterClass *RC : TRI.regclasses()) {1085    unsigned Size = TRI.getRegSizeInBits(*RC);1086 1087    // We might see special reserved values as sizes, and classes for other1088    // stuff the machine tries to model. If it's more than 512 bits, then it1089    // is very unlikely to be a register than can be spilt.1090    if (Size > 512)1091      continue;1092 1093    unsigned Idx = StackSlotIdxes.size();1094    StackSlotIdxes.insert({{Size, 0}, Idx});1095  }1096 1097  for (auto &Idx : StackSlotIdxes)1098    StackIdxesToPos[Idx.second] = Idx.first;1099 1100  NumSlotIdxes = StackSlotIdxes.size();1101}1102 1103LocIdx MLocTracker::trackRegister(unsigned ID) {1104  assert(ID != 0);1105  LocIdx NewIdx = LocIdx(LocIdxToIDNum.size());1106  LocIdxToIDNum.grow(NewIdx);1107  LocIdxToLocID.grow(NewIdx);1108 1109  // Default: it's an mphi.1110  ValueIDNum ValNum = {CurBB, 0, NewIdx};1111  // Was this reg ever touched by a regmask?1112  for (const auto &MaskPair : reverse(Masks)) {1113    if (MaskPair.first->clobbersPhysReg(ID)) {1114      // There was an earlier def we skipped.1115      ValNum = {CurBB, MaskPair.second, NewIdx};1116      break;1117    }1118  }1119 1120  LocIdxToIDNum[NewIdx] = ValNum;1121  LocIdxToLocID[NewIdx] = ID;1122  return NewIdx;1123}1124 1125void MLocTracker::writeRegMask(const MachineOperand *MO, unsigned CurBB,1126                               unsigned InstID) {1127  // Def any register we track have that isn't preserved. The regmask1128  // terminates the liveness of a register, meaning its value can't be1129  // relied upon -- we represent this by giving it a new value.1130  for (auto Location : locations()) {1131    unsigned ID = LocIdxToLocID[Location.Idx];1132    // Don't clobber SP, even if the mask says it's clobbered.1133    if (ID < NumRegs && !SPAliases.count(ID) && MO->clobbersPhysReg(ID))1134      defReg(ID, CurBB, InstID);1135  }1136  Masks.push_back(std::make_pair(MO, InstID));1137}1138 1139std::optional<SpillLocationNo> MLocTracker::getOrTrackSpillLoc(SpillLoc L) {1140  SpillLocationNo SpillID(SpillLocs.idFor(L));1141 1142  if (SpillID.id() == 0) {1143    // If there is no location, and we have reached the limit of how many stack1144    // slots to track, then don't track this one.1145    if (SpillLocs.size() >= StackWorkingSetLimit)1146      return std::nullopt;1147 1148    // Spill location is untracked: create record for this one, and all1149    // subregister slots too.1150    SpillID = SpillLocationNo(SpillLocs.insert(L));1151    for (unsigned StackIdx = 0; StackIdx < NumSlotIdxes; ++StackIdx) {1152      unsigned L = getSpillIDWithIdx(SpillID, StackIdx);1153      LocIdx Idx = LocIdx(LocIdxToIDNum.size()); // New idx1154      LocIdxToIDNum.grow(Idx);1155      LocIdxToLocID.grow(Idx);1156      LocIDToLocIdx.push_back(Idx);1157      LocIdxToLocID[Idx] = L;1158      // Initialize to PHI value; corresponds to the location's live-in value1159      // during transfer function construction.1160      LocIdxToIDNum[Idx] = ValueIDNum(CurBB, 0, Idx);1161    }1162  }1163  return SpillID;1164}1165 1166std::string MLocTracker::LocIdxToName(LocIdx Idx) const {1167  unsigned ID = LocIdxToLocID[Idx];1168  if (ID >= NumRegs) {1169    StackSlotPos Pos = locIDToSpillIdx(ID);1170    ID -= NumRegs;1171    unsigned Slot = ID / NumSlotIdxes;1172    return Twine("slot ")1173        .concat(Twine(Slot).concat(Twine(" sz ").concat(Twine(Pos.first)1174        .concat(Twine(" offs ").concat(Twine(Pos.second))))))1175        .str();1176  } else {1177    return TRI.getRegAsmName(ID).str();1178  }1179}1180 1181std::string MLocTracker::IDAsString(const ValueIDNum &Num) const {1182  std::string DefName = LocIdxToName(Num.getLoc());1183  return Num.asString(DefName);1184}1185 1186#ifndef NDEBUG1187LLVM_DUMP_METHOD void MLocTracker::dump() {1188  for (auto Location : locations()) {1189    std::string MLocName = LocIdxToName(Location.Value.getLoc());1190    std::string DefName = Location.Value.asString(MLocName);1191    dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n";1192  }1193}1194 1195LLVM_DUMP_METHOD void MLocTracker::dump_mloc_map() {1196  for (auto Location : locations()) {1197    std::string foo = LocIdxToName(Location.Idx);1198    dbgs() << "Idx " << Location.Idx.asU64() << " " << foo << "\n";1199  }1200}1201#endif1202 1203MachineInstrBuilder1204MLocTracker::emitLoc(const SmallVectorImpl<ResolvedDbgOp> &DbgOps,1205                     const DebugVariable &Var, const DILocation *DILoc,1206                     const DbgValueProperties &Properties) {1207  DebugLoc DL = DebugLoc(DILoc);1208 1209  const MCInstrDesc &Desc = Properties.IsVariadic1210                                ? TII.get(TargetOpcode::DBG_VALUE_LIST)1211                                : TII.get(TargetOpcode::DBG_VALUE);1212 1213#ifdef EXPENSIVE_CHECKS1214  assert(all_of(DbgOps,1215                [](const ResolvedDbgOp &Op) {1216                  return Op.IsConst || !Op.Loc.isIllegal();1217                }) &&1218         "Did not expect illegal ops in DbgOps.");1219  assert((DbgOps.size() == 0 ||1220          DbgOps.size() == Properties.getLocationOpCount()) &&1221         "Expected to have either one DbgOp per MI LocationOp, or none.");1222#endif1223 1224  auto GetRegOp = [](unsigned Reg) -> MachineOperand {1225    return MachineOperand::CreateReg(1226        /* Reg */ Reg, /* isDef */ false, /* isImp */ false,1227        /* isKill */ false, /* isDead */ false,1228        /* isUndef */ false, /* isEarlyClobber */ false,1229        /* SubReg */ 0, /* isDebug */ true);1230  };1231 1232  SmallVector<MachineOperand> MOs;1233 1234  auto EmitUndef = [&]() {1235    MOs.clear();1236    MOs.assign(Properties.getLocationOpCount(), GetRegOp(0));1237    return BuildMI(MF, DL, Desc, false, MOs, Var.getVariable(),1238                   Properties.DIExpr);1239  };1240 1241  // Don't bother passing any real operands to BuildMI if any of them would be1242  // $noreg.1243  if (DbgOps.empty())1244    return EmitUndef();1245 1246  bool Indirect = Properties.Indirect;1247 1248  const DIExpression *Expr = Properties.DIExpr;1249 1250  assert(DbgOps.size() == Properties.getLocationOpCount());1251 1252  // If all locations are valid, accumulate them into our list of1253  // MachineOperands. For any spilled locations, either update the indirectness1254  // register or apply the appropriate transformations in the DIExpression.1255  for (size_t Idx = 0; Idx < Properties.getLocationOpCount(); ++Idx) {1256    const ResolvedDbgOp &Op = DbgOps[Idx];1257 1258    if (Op.IsConst) {1259      MOs.push_back(Op.MO);1260      continue;1261    }1262 1263    LocIdx MLoc = Op.Loc;1264    unsigned LocID = LocIdxToLocID[MLoc];1265    if (LocID >= NumRegs) {1266      SpillLocationNo SpillID = locIDToSpill(LocID);1267      StackSlotPos StackIdx = locIDToSpillIdx(LocID);1268      unsigned short Offset = StackIdx.second;1269 1270      // TODO: support variables that are located in spill slots, with non-zero1271      // offsets from the start of the spill slot. It would require some more1272      // complex DIExpression calculations. This doesn't seem to be produced by1273      // LLVM right now, so don't try and support it.1274      // Accept no-subregister slots and subregisters where the offset is zero.1275      // The consumer should already have type information to work out how large1276      // the variable is.1277      if (Offset == 0) {1278        const SpillLoc &Spill = SpillLocs[SpillID.id()];1279        unsigned Base = Spill.SpillBase;1280 1281        // There are several ways we can dereference things, and several inputs1282        // to consider:1283        // * NRVO variables will appear with IsIndirect set, but should have1284        //   nothing else in their DIExpressions,1285        // * Variables with DW_OP_stack_value in their expr already need an1286        //   explicit dereference of the stack location,1287        // * Values that don't match the variable size need DW_OP_deref_size,1288        // * Everything else can just become a simple location expression.1289 1290        // We need to use deref_size whenever there's a mismatch between the1291        // size of value and the size of variable portion being read.1292        // Additionally, we should use it whenever dealing with stack_value1293        // fragments, to avoid the consumer having to determine the deref size1294        // from DW_OP_piece.1295        bool UseDerefSize = false;1296        unsigned ValueSizeInBits = getLocSizeInBits(MLoc);1297        unsigned DerefSizeInBytes = ValueSizeInBits / 8;1298        if (auto Fragment = Var.getFragment()) {1299          unsigned VariableSizeInBits = Fragment->SizeInBits;1300          if (VariableSizeInBits != ValueSizeInBits || Expr->isComplex())1301            UseDerefSize = true;1302        } else if (auto Size = Var.getVariable()->getSizeInBits()) {1303          if (*Size != ValueSizeInBits) {1304            UseDerefSize = true;1305          }1306        }1307 1308        // https://github.com/llvm/llvm-project/issues/640931309        // in particular #issuecomment-2531264124. We use variable locations1310        // such as DBG_VALUE $xmm0 as shorthand to refer to "the low lane of1311        // $xmm0", and this is reflected in how DWARF is interpreted too.1312        // However InstrRefBasedLDV tries to be smart and interprets such a1313        // DBG_VALUE as a 128-bit reference. We then issue a DW_OP_deref_size1314        // of 128 bits to the stack, which isn't permitted by DWARF (it's1315        // larger than a pointer).1316        //1317        // Solve this for now by not using DW_OP_deref_size if it would be1318        // illegal. Instead we'll use DW_OP_deref, and the consumer will load1319        // the variable type from the stack, which should be correct.1320        //1321        // There's still a risk of imprecision when LLVM decides to use1322        // smaller or larger value types than the source-variable type, which1323        // manifests as too-little or too-much memory being read from the stack.1324        // However we can't solve that without putting more type information in1325        // debug-info.1326        if (ValueSizeInBits > MF.getTarget().getPointerSizeInBits(0))1327          UseDerefSize = false;1328 1329        SmallVector<uint64_t, 5> OffsetOps;1330        TRI.getOffsetOpcodes(Spill.SpillOffset, OffsetOps);1331        bool StackValue = false;1332 1333        if (Properties.Indirect) {1334          // This is something like an NRVO variable, where the pointer has been1335          // spilt to the stack. It should end up being a memory location, with1336          // the pointer to the variable loaded off the stack with a deref:1337          assert(!Expr->isImplicit());1338          OffsetOps.push_back(dwarf::DW_OP_deref);1339        } else if (UseDerefSize && Expr->isSingleLocationExpression()) {1340          // TODO: Figure out how to handle deref size issues for variadic1341          // values.1342          // We're loading a value off the stack that's not the same size as the1343          // variable. Add / subtract stack offset, explicitly deref with a1344          // size, and add DW_OP_stack_value if not already present.1345          OffsetOps.push_back(dwarf::DW_OP_deref_size);1346          OffsetOps.push_back(DerefSizeInBytes);1347          StackValue = true;1348        } else if (Expr->isComplex() || Properties.IsVariadic) {1349          // A variable with no size ambiguity, but with extra elements in it's1350          // expression. Manually dereference the stack location.1351          OffsetOps.push_back(dwarf::DW_OP_deref);1352        } else {1353          // A plain value that has been spilt to the stack, with no further1354          // context. Request a location expression, marking the DBG_VALUE as1355          // IsIndirect.1356          Indirect = true;1357        }1358 1359        Expr = DIExpression::appendOpsToArg(Expr, OffsetOps, Idx, StackValue);1360        MOs.push_back(GetRegOp(Base));1361      } else {1362        // This is a stack location with a weird subregister offset: emit an1363        // undef DBG_VALUE instead.1364        return EmitUndef();1365      }1366    } else {1367      // Non-empty, non-stack slot, must be a plain register.1368      MOs.push_back(GetRegOp(LocID));1369    }1370  }1371 1372  return BuildMI(MF, DL, Desc, Indirect, MOs, Var.getVariable(), Expr);1373}1374 1375/// Default construct and initialize the pass.1376InstrRefBasedLDV::InstrRefBasedLDV() = default;1377 1378bool InstrRefBasedLDV::isCalleeSaved(LocIdx L) const {1379  unsigned Reg = MTracker->LocIdxToLocID[L];1380  return isCalleeSavedReg(Reg);1381}1382bool InstrRefBasedLDV::isCalleeSavedReg(Register R) const {1383  for (MCRegAliasIterator RAI(R, TRI, true); RAI.isValid(); ++RAI)1384    if (CalleeSavedRegs.test((*RAI).id()))1385      return true;1386  return false;1387}1388 1389//===----------------------------------------------------------------------===//1390//            Debug Range Extension Implementation1391//===----------------------------------------------------------------------===//1392 1393#ifndef NDEBUG1394// Something to restore in the future.1395// void InstrRefBasedLDV::printVarLocInMBB(..)1396#endif1397 1398std::optional<SpillLocationNo>1399InstrRefBasedLDV::extractSpillBaseRegAndOffset(const MachineInstr &MI) {1400  assert(MI.hasOneMemOperand() &&1401         "Spill instruction does not have exactly one memory operand?");1402  auto MMOI = MI.memoperands_begin();1403  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();1404  assert(PVal->kind() == PseudoSourceValue::FixedStack &&1405         "Inconsistent memory operand in spill instruction");1406  int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();1407  const MachineBasicBlock *MBB = MI.getParent();1408  Register Reg;1409  StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);1410  return MTracker->getOrTrackSpillLoc({Reg, Offset});1411}1412 1413std::optional<LocIdx>1414InstrRefBasedLDV::findLocationForMemOperand(const MachineInstr &MI) {1415  std::optional<SpillLocationNo> SpillLoc = extractSpillBaseRegAndOffset(MI);1416  if (!SpillLoc)1417    return std::nullopt;1418 1419  // Where in the stack slot is this value defined -- i.e., what size of value1420  // is this? An important question, because it could be loaded into a register1421  // from the stack at some point. Happily the memory operand will tell us1422  // the size written to the stack.1423  auto *MemOperand = *MI.memoperands_begin();1424  LocationSize SizeInBits = MemOperand->getSizeInBits();1425  assert(SizeInBits.hasValue() && "Expected to find a valid size!");1426 1427  // Find that position in the stack indexes we're tracking.1428  auto IdxIt = MTracker->StackSlotIdxes.find({SizeInBits.getValue(), 0});1429  if (IdxIt == MTracker->StackSlotIdxes.end())1430    // That index is not tracked. This is suprising, and unlikely to ever1431    // occur, but the safe action is to indicate the variable is optimised out.1432    return std::nullopt;1433 1434  unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillLoc, IdxIt->second);1435  return MTracker->getSpillMLoc(SpillID);1436}1437 1438/// End all previous ranges related to @MI and start a new range from @MI1439/// if it is a DBG_VALUE instr.1440bool InstrRefBasedLDV::transferDebugValue(const MachineInstr &MI) {1441  if (!MI.isDebugValue())1442    return false;1443 1444  assert(MI.getDebugVariable()->isValidLocationForIntrinsic(MI.getDebugLoc()) &&1445         "Expected inlined-at fields to agree");1446 1447  // If there are no instructions in this lexical scope, do no location tracking1448  // at all, this variable shouldn't get a legitimate location range.1449  auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());1450  if (Scope == nullptr)1451    return true; // handled it; by doing nothing1452 1453  // MLocTracker needs to know that this register is read, even if it's only1454  // read by a debug inst.1455  for (const MachineOperand &MO : MI.debug_operands())1456    if (MO.isReg() && MO.getReg() != 0)1457      (void)MTracker->readReg(MO.getReg());1458 1459  // If we're preparing for the second analysis (variables), the machine value1460  // locations are already solved, and we report this DBG_VALUE and the value1461  // it refers to to VLocTracker.1462  if (VTracker) {1463    SmallVector<DbgOpID> DebugOps;1464    // Feed defVar the new variable location, or if this is a DBG_VALUE $noreg,1465    // feed defVar None.1466    if (!MI.isUndefDebugValue()) {1467      for (const MachineOperand &MO : MI.debug_operands()) {1468        // There should be no undef registers here, as we've screened for undef1469        // debug values.1470        if (MO.isReg()) {1471          DebugOps.push_back(DbgOpStore.insert(MTracker->readReg(MO.getReg())));1472        } else if (MO.isImm() || MO.isFPImm() || MO.isCImm()) {1473          DebugOps.push_back(DbgOpStore.insert(MO));1474        } else {1475          llvm_unreachable("Unexpected debug operand type.");1476        }1477      }1478    }1479    VTracker->defVar(MI, DbgValueProperties(MI), DebugOps);1480  }1481 1482  // If performing final tracking of transfers, report this variable definition1483  // to the TransferTracker too.1484  if (TTracker)1485    TTracker->redefVar(MI);1486  return true;1487}1488 1489std::optional<ValueIDNum> InstrRefBasedLDV::getValueForInstrRef(1490    unsigned InstNo, unsigned OpNo, MachineInstr &MI,1491    const FuncValueTable *MLiveOuts, const FuncValueTable *MLiveIns) {1492  // Various optimizations may have happened to the value during codegen,1493  // recorded in the value substitution table. Apply any substitutions to1494  // the instruction / operand number in this DBG_INSTR_REF, and collect1495  // any subregister extractions performed during optimization.1496  const MachineFunction &MF = *MI.getParent()->getParent();1497 1498  // Create dummy substitution with Src set, for lookup.1499  auto SoughtSub =1500      MachineFunction::DebugSubstitution({InstNo, OpNo}, {0, 0}, 0);1501 1502  SmallVector<unsigned, 4> SeenSubregs;1503  auto LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);1504  while (LowerBoundIt != MF.DebugValueSubstitutions.end() &&1505         LowerBoundIt->Src == SoughtSub.Src) {1506    std::tie(InstNo, OpNo) = LowerBoundIt->Dest;1507    SoughtSub.Src = LowerBoundIt->Dest;1508    if (unsigned Subreg = LowerBoundIt->Subreg)1509      SeenSubregs.push_back(Subreg);1510    LowerBoundIt = llvm::lower_bound(MF.DebugValueSubstitutions, SoughtSub);1511  }1512 1513  // Default machine value number is <None> -- if no instruction defines1514  // the corresponding value, it must have been optimized out.1515  std::optional<ValueIDNum> NewID;1516 1517  // Try to lookup the instruction number, and find the machine value number1518  // that it defines. It could be an instruction, or a PHI.1519  auto InstrIt = DebugInstrNumToInstr.find(InstNo);1520  auto PHIIt = llvm::lower_bound(DebugPHINumToValue, InstNo);1521  if (InstrIt != DebugInstrNumToInstr.end()) {1522    const MachineInstr &TargetInstr = *InstrIt->second.first;1523    uint64_t BlockNo = TargetInstr.getParent()->getNumber();1524 1525    // Pick out the designated operand. It might be a memory reference, if1526    // a register def was folded into a stack store.1527    if (OpNo == MachineFunction::DebugOperandMemNumber &&1528        TargetInstr.hasOneMemOperand()) {1529      std::optional<LocIdx> L = findLocationForMemOperand(TargetInstr);1530      if (L)1531        NewID = ValueIDNum(BlockNo, InstrIt->second.second, *L);1532    } else if (OpNo != MachineFunction::DebugOperandMemNumber) {1533      // Permit the debug-info to be completely wrong: identifying a nonexistant1534      // operand, or one that is not a register definition, means something1535      // unexpected happened during optimisation. Broken debug-info, however,1536      // shouldn't crash the compiler -- instead leave the variable value as1537      // None, which will make it appear "optimised out".1538      if (OpNo < TargetInstr.getNumOperands()) {1539        const MachineOperand &MO = TargetInstr.getOperand(OpNo);1540 1541        if (MO.isReg() && MO.isDef() && MO.getReg()) {1542          unsigned LocID = MTracker->getLocID(MO.getReg());1543          LocIdx L = MTracker->LocIDToLocIdx[LocID];1544          NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);1545        }1546      }1547 1548      if (!NewID) {1549        LLVM_DEBUG(1550            { dbgs() << "Seen instruction reference to illegal operand\n"; });1551      }1552    }1553    // else: NewID is left as None.1554  } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {1555    // It's actually a PHI value. Which value it is might not be obvious, use1556    // the resolver helper to find out.1557    assert(MLiveOuts && MLiveIns);1558    NewID = resolveDbgPHIs(*MI.getParent()->getParent(), *MLiveOuts, *MLiveIns,1559                           MI, InstNo);1560  }1561 1562  // Apply any subregister extractions, in reverse. We might have seen code1563  // like this:1564  //    CALL64 @foo, implicit-def $rax1565  //    %0:gr64 = COPY $rax1566  //    %1:gr32 = COPY %0.sub_32bit1567  //    %2:gr16 = COPY %1.sub_16bit1568  //    %3:gr8  = COPY %2.sub_8bit1569  // In which case each copy would have been recorded as a substitution with1570  // a subregister qualifier. Apply those qualifiers now.1571  if (NewID && !SeenSubregs.empty()) {1572    unsigned Offset = 0;1573    unsigned Size = 0;1574 1575    // Look at each subregister that we passed through, and progressively1576    // narrow in, accumulating any offsets that occur. Substitutions should1577    // only ever be the same or narrower width than what they read from;1578    // iterate in reverse order so that we go from wide to small.1579    for (unsigned Subreg : reverse(SeenSubregs)) {1580      unsigned ThisSize = TRI->getSubRegIdxSize(Subreg);1581      unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg);1582      Offset += ThisOffset;1583      Size = (Size == 0) ? ThisSize : std::min(Size, ThisSize);1584    }1585 1586    // If that worked, look for an appropriate subregister with the register1587    // where the define happens. Don't look at values that were defined during1588    // a stack write: we can't currently express register locations within1589    // spills.1590    LocIdx L = NewID->getLoc();1591    if (NewID && !MTracker->isSpill(L)) {1592      // Find the register class for the register where this def happened.1593      // FIXME: no index for this?1594      Register Reg = MTracker->LocIdxToLocID[L];1595      const TargetRegisterClass *TRC = nullptr;1596      for (const auto *TRCI : TRI->regclasses())1597        if (TRCI->contains(Reg))1598          TRC = TRCI;1599      assert(TRC && "Couldn't find target register class?");1600 1601      // If the register we have isn't the right size or in the right place,1602      // Try to find a subregister inside it.1603      unsigned MainRegSize = TRI->getRegSizeInBits(*TRC);1604      if (Size != MainRegSize || Offset) {1605        // Enumerate all subregisters, searching.1606        Register NewReg = Register();1607        for (MCRegister SR : TRI->subregs(Reg)) {1608          unsigned Subreg = TRI->getSubRegIndex(Reg, SR);1609          unsigned SubregSize = TRI->getSubRegIdxSize(Subreg);1610          unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg);1611          if (SubregSize == Size && SubregOffset == Offset) {1612            NewReg = SR;1613            break;1614          }1615        }1616 1617        // If we didn't find anything: there's no way to express our value.1618        if (!NewReg) {1619          NewID = std::nullopt;1620        } else {1621          // Re-state the value as being defined within the subregister1622          // that we found.1623          LocIdx NewLoc =1624              MTracker->lookupOrTrackRegister(MTracker->getLocID(NewReg));1625          NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc);1626        }1627      }1628    } else {1629      // If we can't handle subregisters, unset the new value.1630      NewID = std::nullopt;1631    }1632  }1633 1634  return NewID;1635}1636 1637bool InstrRefBasedLDV::transferDebugInstrRef(MachineInstr &MI,1638                                             const FuncValueTable *MLiveOuts,1639                                             const FuncValueTable *MLiveIns) {1640  if (!MI.isDebugRef())1641    return false;1642 1643  // Only handle this instruction when we are building the variable value1644  // transfer function.1645  if (!VTracker && !TTracker)1646    return false;1647 1648  const DILocalVariable *Var = MI.getDebugVariable();1649  const DIExpression *Expr = MI.getDebugExpression();1650  const DILocation *DebugLoc = MI.getDebugLoc();1651  const DILocation *InlinedAt = DebugLoc->getInlinedAt();1652  assert(Var->isValidLocationForIntrinsic(DebugLoc) &&1653         "Expected inlined-at fields to agree");1654 1655  DebugVariable V(Var, Expr, InlinedAt);1656 1657  auto *Scope = LS.findLexicalScope(MI.getDebugLoc().get());1658  if (Scope == nullptr)1659    return true; // Handled by doing nothing. This variable is never in scope.1660 1661  SmallVector<DbgOpID> DbgOpIDs;1662  for (const MachineOperand &MO : MI.debug_operands()) {1663    if (!MO.isDbgInstrRef()) {1664      assert(!MO.isReg() && "DBG_INSTR_REF should not contain registers");1665      DbgOpID ConstOpID = DbgOpStore.insert(DbgOp(MO));1666      DbgOpIDs.push_back(ConstOpID);1667      continue;1668    }1669 1670    unsigned InstNo = MO.getInstrRefInstrIndex();1671    unsigned OpNo = MO.getInstrRefOpIndex();1672 1673    // Default machine value number is <None> -- if no instruction defines1674    // the corresponding value, it must have been optimized out.1675    std::optional<ValueIDNum> NewID =1676        getValueForInstrRef(InstNo, OpNo, MI, MLiveOuts, MLiveIns);1677    // We have a value number or std::nullopt. If the latter, then kill the1678    // entire debug value.1679    if (NewID) {1680      DbgOpIDs.push_back(DbgOpStore.insert(*NewID));1681    } else {1682      DbgOpIDs.clear();1683      break;1684    }1685  }1686 1687  // We have a DbgOpID for every value or for none. Tell the variable value1688  // tracker about it. The rest of this LiveDebugValues implementation acts1689  // exactly the same for DBG_INSTR_REFs as DBG_VALUEs (just, the former can1690  // refer to values that aren't immediately available).1691  DbgValueProperties Properties(Expr, false, true);1692  if (VTracker)1693    VTracker->defVar(MI, Properties, DbgOpIDs);1694 1695  // If we're on the final pass through the function, decompose this INSTR_REF1696  // into a plain DBG_VALUE.1697  if (!TTracker)1698    return true;1699 1700  // Fetch the concrete DbgOps now, as we will need them later.1701  SmallVector<DbgOp> DbgOps;1702  for (DbgOpID OpID : DbgOpIDs) {1703    DbgOps.push_back(DbgOpStore.find(OpID));1704  }1705 1706  // Pick a location for the machine value number, if such a location exists.1707  // (This information could be stored in TransferTracker to make it faster).1708  SmallDenseMap<ValueIDNum, TransferTracker::LocationAndQuality> FoundLocs;1709  SmallVector<ValueIDNum> ValuesToFind;1710  // Initialized the preferred-location map with illegal locations, to be1711  // filled in later.1712  for (const DbgOp &Op : DbgOps) {1713    if (!Op.IsConst)1714      if (FoundLocs.try_emplace(Op.ID).second)1715        ValuesToFind.push_back(Op.ID);1716  }1717 1718  for (auto Location : MTracker->locations()) {1719    LocIdx CurL = Location.Idx;1720    ValueIDNum ID = MTracker->readMLoc(CurL);1721    auto ValueToFindIt = find(ValuesToFind, ID);1722    if (ValueToFindIt == ValuesToFind.end())1723      continue;1724    auto &Previous = FoundLocs.find(ID)->second;1725    // If this is the first location with that value, pick it. Otherwise,1726    // consider whether it's a "longer term" location.1727    std::optional<TransferTracker::LocationQuality> ReplacementQuality =1728        TTracker->getLocQualityIfBetter(CurL, Previous.getQuality());1729    if (ReplacementQuality) {1730      Previous = TransferTracker::LocationAndQuality(CurL, *ReplacementQuality);1731      if (Previous.isBest()) {1732        ValuesToFind.erase(ValueToFindIt);1733        if (ValuesToFind.empty())1734          break;1735      }1736    }1737  }1738 1739  SmallVector<ResolvedDbgOp> NewLocs;1740  for (const DbgOp &DbgOp : DbgOps) {1741    if (DbgOp.IsConst) {1742      NewLocs.push_back(DbgOp.MO);1743      continue;1744    }1745    LocIdx FoundLoc = FoundLocs.find(DbgOp.ID)->second.getLoc();1746    if (FoundLoc.isIllegal()) {1747      NewLocs.clear();1748      break;1749    }1750    NewLocs.push_back(FoundLoc);1751  }1752  // Tell transfer tracker that the variable value has changed.1753  TTracker->redefVar(MI, Properties, NewLocs);1754 1755  // If there were values with no location, but all such values are defined in1756  // later instructions in this block, this is a block-local use-before-def.1757  if (!DbgOps.empty() && NewLocs.empty()) {1758    bool IsValidUseBeforeDef = true;1759    uint64_t LastUseBeforeDef = 0;1760    for (auto ValueLoc : FoundLocs) {1761      ValueIDNum NewID = ValueLoc.first;1762      LocIdx FoundLoc = ValueLoc.second.getLoc();1763      if (!FoundLoc.isIllegal())1764        continue;1765      // If we have an value with no location that is not defined in this block,1766      // then it has no location in this block, leaving this value undefined.1767      if (NewID.getBlock() != CurBB || NewID.getInst() <= CurInst) {1768        IsValidUseBeforeDef = false;1769        break;1770      }1771      LastUseBeforeDef = std::max(LastUseBeforeDef, NewID.getInst());1772    }1773    if (IsValidUseBeforeDef) {1774      DebugVariableID VID = DVMap.insertDVID(V, MI.getDebugLoc().get());1775      TTracker->addUseBeforeDef(VID, {MI.getDebugExpression(), false, true},1776                                DbgOps, LastUseBeforeDef);1777    }1778  }1779 1780  // Produce a DBG_VALUE representing what this DBG_INSTR_REF meant.1781  // This DBG_VALUE is potentially a $noreg / undefined location, if1782  // FoundLoc is illegal.1783  // (XXX -- could morph the DBG_INSTR_REF in the future).1784  MachineInstr *DbgMI =1785      MTracker->emitLoc(NewLocs, V, MI.getDebugLoc().get(), Properties);1786  DebugVariableID ID = DVMap.getDVID(V);1787 1788  TTracker->PendingDbgValues.push_back(std::make_pair(ID, DbgMI));1789  TTracker->flushDbgValues(MI.getIterator(), nullptr);1790  return true;1791}1792 1793bool InstrRefBasedLDV::transferDebugPHI(MachineInstr &MI) {1794  if (!MI.isDebugPHI())1795    return false;1796 1797  // Analyse these only when solving the machine value location problem.1798  if (VTracker || TTracker)1799    return true;1800 1801  // First operand is the value location, either a stack slot or register.1802  // Second is the debug instruction number of the original PHI.1803  const MachineOperand &MO = MI.getOperand(0);1804  unsigned InstrNum = MI.getOperand(1).getImm();1805 1806  auto EmitBadPHI = [this, &MI, InstrNum]() -> bool {1807    // Helper lambda to do any accounting when we fail to find a location for1808    // a DBG_PHI. This can happen if DBG_PHIs are malformed, or refer to a1809    // dead stack slot, for example.1810    // Record a DebugPHIRecord with an empty value + location.1811    DebugPHINumToValue.push_back(1812        {InstrNum, MI.getParent(), std::nullopt, std::nullopt});1813    return true;1814  };1815 1816  if (MO.isReg() && MO.getReg()) {1817    // The value is whatever's currently in the register. Read and record it,1818    // to be analysed later.1819    Register Reg = MO.getReg();1820    ValueIDNum Num = MTracker->readReg(Reg);1821    auto PHIRec = DebugPHIRecord(1822        {InstrNum, MI.getParent(), Num,1823         MTracker->lookupOrTrackRegister(MTracker->getLocID(Reg))});1824    DebugPHINumToValue.push_back(PHIRec);1825 1826    // Ensure this register is tracked.1827    for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)1828      MTracker->lookupOrTrackRegister(MTracker->getLocID(*RAI));1829  } else if (MO.isFI()) {1830    // The value is whatever's in this stack slot.1831    unsigned FI = MO.getIndex();1832 1833    // If the stack slot is dead, then this was optimized away.1834    // FIXME: stack slot colouring should account for slots that get merged.1835    if (MFI->isDeadObjectIndex(FI))1836      return EmitBadPHI();1837 1838    // Identify this spill slot, ensure it's tracked.1839    Register Base;1840    StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base);1841    SpillLoc SL = {Base, Offs};1842    std::optional<SpillLocationNo> SpillNo = MTracker->getOrTrackSpillLoc(SL);1843 1844    // We might be able to find a value, but have chosen not to, to avoid1845    // tracking too much stack information.1846    if (!SpillNo)1847      return EmitBadPHI();1848 1849    // Any stack location DBG_PHI should have an associate bit-size.1850    assert(MI.getNumOperands() == 3 && "Stack DBG_PHI with no size?");1851    unsigned slotBitSize = MI.getOperand(2).getImm();1852 1853    unsigned SpillID = MTracker->getLocID(*SpillNo, {slotBitSize, 0});1854    LocIdx SpillLoc = MTracker->getSpillMLoc(SpillID);1855    ValueIDNum Result = MTracker->readMLoc(SpillLoc);1856 1857    // Record this DBG_PHI for later analysis.1858    auto DbgPHI = DebugPHIRecord({InstrNum, MI.getParent(), Result, SpillLoc});1859    DebugPHINumToValue.push_back(DbgPHI);1860  } else {1861    // Else: if the operand is neither a legal register or a stack slot, then1862    // we're being fed illegal debug-info. Record an empty PHI, so that any1863    // debug users trying to read this number will be put off trying to1864    // interpret the value.1865    LLVM_DEBUG(1866        { dbgs() << "Seen DBG_PHI with unrecognised operand format\n"; });1867    return EmitBadPHI();1868  }1869 1870  return true;1871}1872 1873void InstrRefBasedLDV::transferRegisterDef(MachineInstr &MI) {1874  // Meta Instructions do not affect the debug liveness of any register they1875  // define.1876  if (MI.isImplicitDef()) {1877    // Except when there's an implicit def, and the location it's defining has1878    // no value number. The whole point of an implicit def is to announce that1879    // the register is live, without be specific about it's value. So define1880    // a value if there isn't one already.1881    ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg());1882    // Has a legitimate value -> ignore the implicit def.1883    if (Num.getLoc() != 0)1884      return;1885    // Otherwise, def it here.1886  } else if (MI.isMetaInstruction())1887    return;1888 1889  // We always ignore SP defines on call instructions, they don't actually1890  // change the value of the stack pointer... except for win32's _chkstk. This1891  // is rare: filter quickly for the common case (no stack adjustments, not a1892  // call, etc). If it is a call that modifies SP, recognise the SP register1893  // defs.1894  bool CallChangesSP = false;1895  if (AdjustsStackInCalls && MI.isCall() && MI.getOperand(0).isSymbol() &&1896      !strcmp(MI.getOperand(0).getSymbolName(), StackProbeSymbolName.data()))1897    CallChangesSP = true;1898 1899  // Test whether we should ignore a def of this register due to it being part1900  // of the stack pointer.1901  auto IgnoreSPAlias = [this, &MI, CallChangesSP](Register R) -> bool {1902    if (CallChangesSP)1903      return false;1904    return MI.isCall() && MTracker->SPAliases.count(R);1905  };1906 1907  // Find the regs killed by MI, and find regmasks of preserved regs.1908  // Max out the number of statically allocated elements in `DeadRegs`, as this1909  // prevents fallback to std::set::count() operations.1910  SmallSet<uint32_t, 32> DeadRegs;1911  SmallVector<const uint32_t *, 4> RegMasks;1912  SmallVector<const MachineOperand *, 4> RegMaskPtrs;1913  for (const MachineOperand &MO : MI.operands()) {1914    // Determine whether the operand is a register def.1915    if (MO.isReg() && MO.isDef() && MO.getReg() && MO.getReg().isPhysical() &&1916        !IgnoreSPAlias(MO.getReg())) {1917      // Remove ranges of all aliased registers.1918      for (MCRegAliasIterator RAI(MO.getReg(), TRI, true); RAI.isValid(); ++RAI)1919        // FIXME: Can we break out of this loop early if no insertion occurs?1920        DeadRegs.insert((*RAI).id());1921    } else if (MO.isRegMask()) {1922      RegMasks.push_back(MO.getRegMask());1923      RegMaskPtrs.push_back(&MO);1924    }1925  }1926 1927  // Tell MLocTracker about all definitions, of regmasks and otherwise.1928  for (uint32_t DeadReg : DeadRegs)1929    MTracker->defReg(DeadReg, CurBB, CurInst);1930 1931  for (const auto *MO : RegMaskPtrs)1932    MTracker->writeRegMask(MO, CurBB, CurInst);1933 1934  // If this instruction writes to a spill slot, def that slot.1935  if (hasFoldedStackStore(MI)) {1936    if (std::optional<SpillLocationNo> SpillNo =1937            extractSpillBaseRegAndOffset(MI)) {1938      for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {1939        unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillNo, I);1940        LocIdx L = MTracker->getSpillMLoc(SpillID);1941        MTracker->setMLoc(L, ValueIDNum(CurBB, CurInst, L));1942      }1943    }1944  }1945 1946  if (!TTracker)1947    return;1948 1949  // When committing variable values to locations: tell transfer tracker that1950  // we've clobbered things. It may be able to recover the variable from a1951  // different location.1952 1953  // Inform TTracker about any direct clobbers.1954  for (MCRegister DeadReg : DeadRegs) {1955    LocIdx Loc = MTracker->lookupOrTrackRegister(MTracker->getLocID(DeadReg));1956    TTracker->clobberMloc(Loc, MI.getIterator(), false);1957  }1958 1959  // Look for any clobbers performed by a register mask. Only test locations1960  // that are actually being tracked.1961  if (!RegMaskPtrs.empty()) {1962    for (auto L : MTracker->locations()) {1963      // Stack locations can't be clobbered by regmasks.1964      if (MTracker->isSpill(L.Idx))1965        continue;1966 1967      Register Reg = MTracker->LocIdxToLocID[L.Idx];1968      if (IgnoreSPAlias(Reg))1969        continue;1970 1971      for (const auto *MO : RegMaskPtrs)1972        if (MO->clobbersPhysReg(Reg))1973          TTracker->clobberMloc(L.Idx, MI.getIterator(), false);1974    }1975  }1976 1977  // Tell TTracker about any folded stack store.1978  if (hasFoldedStackStore(MI)) {1979    if (std::optional<SpillLocationNo> SpillNo =1980            extractSpillBaseRegAndOffset(MI)) {1981      for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {1982        unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillNo, I);1983        LocIdx L = MTracker->getSpillMLoc(SpillID);1984        TTracker->clobberMloc(L, MI.getIterator(), true);1985      }1986    }1987  }1988}1989 1990void InstrRefBasedLDV::performCopy(Register SrcRegNum, Register DstRegNum) {1991  // In all circumstances, re-def all aliases. It's definitely a new value now.1992  for (MCRegAliasIterator RAI(DstRegNum, TRI, true); RAI.isValid(); ++RAI)1993    MTracker->defReg(*RAI, CurBB, CurInst);1994 1995  ValueIDNum SrcValue = MTracker->readReg(SrcRegNum);1996  MTracker->setReg(DstRegNum, SrcValue);1997 1998  // Copy subregisters from one location to another.1999  for (MCSubRegIndexIterator SRI(SrcRegNum, TRI); SRI.isValid(); ++SRI) {2000    MCRegister SrcSubReg = SRI.getSubReg();2001    unsigned SubRegIdx = SRI.getSubRegIndex();2002    MCRegister DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx);2003    if (!DstSubReg)2004      continue;2005 2006    // Do copy. There are two matching subregisters, the source value should2007    // have been def'd when the super-reg was, the latter might not be tracked2008    // yet.2009    // This will force SrcSubReg to be tracked, if it isn't yet. Will read2010    // mphi values if it wasn't tracked.2011    LocIdx SrcL =2012        MTracker->lookupOrTrackRegister(MTracker->getLocID(SrcSubReg));2013    LocIdx DstL =2014        MTracker->lookupOrTrackRegister(MTracker->getLocID(DstSubReg));2015    (void)SrcL;2016    (void)DstL;2017    ValueIDNum CpyValue = MTracker->readReg(SrcSubReg);2018 2019    MTracker->setReg(DstSubReg, CpyValue);2020  }2021}2022 2023std::optional<SpillLocationNo>2024InstrRefBasedLDV::isSpillInstruction(const MachineInstr &MI,2025                                     MachineFunction *MF) {2026  // TODO: Handle multiple stores folded into one.2027  if (!MI.hasOneMemOperand())2028    return std::nullopt;2029 2030  // Reject any memory operand that's aliased -- we can't guarantee its value.2031  auto MMOI = MI.memoperands_begin();2032  const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();2033  if (PVal->isAliased(MFI))2034    return std::nullopt;2035 2036  if (!MI.getSpillSize(TII) && !MI.getFoldedSpillSize(TII))2037    return std::nullopt; // This is not a spill instruction, since no valid size2038                         // was returned from either function.2039 2040  return extractSpillBaseRegAndOffset(MI);2041}2042 2043bool InstrRefBasedLDV::isLocationSpill(const MachineInstr &MI,2044                                       MachineFunction *MF, unsigned &Reg) {2045  if (!isSpillInstruction(MI, MF))2046    return false;2047 2048  int FI;2049  Reg = TII->isStoreToStackSlotPostFE(MI, FI);2050  return Reg != 0;2051}2052 2053std::optional<SpillLocationNo>2054InstrRefBasedLDV::isRestoreInstruction(const MachineInstr &MI,2055                                       MachineFunction *MF, unsigned &Reg) {2056  if (!MI.hasOneMemOperand())2057    return std::nullopt;2058 2059  // FIXME: Handle folded restore instructions with more than one memory2060  // operand.2061  if (MI.getRestoreSize(TII)) {2062    Reg = MI.getOperand(0).getReg();2063    return extractSpillBaseRegAndOffset(MI);2064  }2065  return std::nullopt;2066}2067 2068bool InstrRefBasedLDV::transferSpillOrRestoreInst(MachineInstr &MI) {2069  // XXX -- it's too difficult to implement VarLocBasedImpl's  stack location2070  // limitations under the new model. Therefore, when comparing them, compare2071  // versions that don't attempt spills or restores at all.2072  if (EmulateOldLDV)2073    return false;2074 2075  // Strictly limit ourselves to plain loads and stores, not all instructions2076  // that can access the stack.2077  int DummyFI = -1;2078  if (!TII->isStoreToStackSlotPostFE(MI, DummyFI) &&2079      !TII->isLoadFromStackSlotPostFE(MI, DummyFI))2080    return false;2081 2082  MachineFunction *MF = MI.getMF();2083  unsigned Reg;2084 2085  LLVM_DEBUG(dbgs() << "Examining instruction: "; MI.dump(););2086 2087  // Strictly limit ourselves to plain loads and stores, not all instructions2088  // that can access the stack.2089  int FIDummy;2090  if (!TII->isStoreToStackSlotPostFE(MI, FIDummy) &&2091      !TII->isLoadFromStackSlotPostFE(MI, FIDummy))2092    return false;2093 2094  // First, if there are any DBG_VALUEs pointing at a spill slot that is2095  // written to, terminate that variable location. The value in memory2096  // will have changed. DbgEntityHistoryCalculator doesn't try to detect this.2097  if (std::optional<SpillLocationNo> Loc = isSpillInstruction(MI, MF)) {2098    // Un-set this location and clobber, so that earlier locations don't2099    // continue past this store.2100    for (unsigned SlotIdx = 0; SlotIdx < MTracker->NumSlotIdxes; ++SlotIdx) {2101      unsigned SpillID = MTracker->getSpillIDWithIdx(*Loc, SlotIdx);2102      std::optional<LocIdx> MLoc = MTracker->getSpillMLoc(SpillID);2103      if (!MLoc)2104        continue;2105 2106      // We need to over-write the stack slot with something (here, a def at2107      // this instruction) to ensure no values are preserved in this stack slot2108      // after the spill. It also prevents TTracker from trying to recover the2109      // location and re-installing it in the same place.2110      ValueIDNum Def(CurBB, CurInst, *MLoc);2111      MTracker->setMLoc(*MLoc, Def);2112      if (TTracker)2113        TTracker->clobberMloc(*MLoc, MI.getIterator());2114    }2115  }2116 2117  // Try to recognise spill and restore instructions that may transfer a value.2118  if (isLocationSpill(MI, MF, Reg)) {2119    // isLocationSpill returning true should guarantee we can extract a2120    // location.2121    SpillLocationNo Loc = *extractSpillBaseRegAndOffset(MI);2122 2123    auto DoTransfer = [&](Register SrcReg, unsigned SpillID) {2124      auto ReadValue = MTracker->readReg(SrcReg);2125      LocIdx DstLoc = MTracker->getSpillMLoc(SpillID);2126      MTracker->setMLoc(DstLoc, ReadValue);2127 2128      if (TTracker) {2129        LocIdx SrcLoc = MTracker->getRegMLoc(SrcReg);2130        TTracker->transferMlocs(SrcLoc, DstLoc, MI.getIterator());2131      }2132    };2133 2134    // Then, transfer subreg bits.2135    for (MCPhysReg SR : TRI->subregs(Reg)) {2136      // Ensure this reg is tracked,2137      (void)MTracker->lookupOrTrackRegister(MTracker->getLocID(SR));2138      unsigned SubregIdx = TRI->getSubRegIndex(Reg, SR);2139      unsigned SpillID = MTracker->getLocID(Loc, SubregIdx);2140      DoTransfer(SR, SpillID);2141    }2142 2143    // Directly lookup size of main source reg, and transfer.2144    unsigned Size = TRI->getRegSizeInBits(Reg, *MRI);2145    unsigned SpillID = MTracker->getLocID(Loc, {Size, 0});2146    DoTransfer(Reg, SpillID);2147  } else {2148    std::optional<SpillLocationNo> Loc = isRestoreInstruction(MI, MF, Reg);2149    if (!Loc)2150      return false;2151 2152    // Assumption: we're reading from the base of the stack slot, not some2153    // offset into it. It seems very unlikely LLVM would ever generate2154    // restores where this wasn't true. This then becomes a question of what2155    // subregisters in the destination register line up with positions in the2156    // stack slot.2157 2158    // Def all registers that alias the destination.2159    for (MCRegAliasIterator RAI(Reg, TRI, true); RAI.isValid(); ++RAI)2160      MTracker->defReg(*RAI, CurBB, CurInst);2161 2162    // Now find subregisters within the destination register, and load values2163    // from stack slot positions.2164    auto DoTransfer = [&](Register DestReg, unsigned SpillID) {2165      LocIdx SrcIdx = MTracker->getSpillMLoc(SpillID);2166      auto ReadValue = MTracker->readMLoc(SrcIdx);2167      MTracker->setReg(DestReg, ReadValue);2168    };2169 2170    for (MCPhysReg SR : TRI->subregs(Reg)) {2171      unsigned Subreg = TRI->getSubRegIndex(Reg, SR);2172      unsigned SpillID = MTracker->getLocID(*Loc, Subreg);2173      DoTransfer(SR, SpillID);2174    }2175 2176    // Directly look up this registers slot idx by size, and transfer.2177    unsigned Size = TRI->getRegSizeInBits(Reg, *MRI);2178    unsigned SpillID = MTracker->getLocID(*Loc, {Size, 0});2179    DoTransfer(Reg, SpillID);2180  }2181  return true;2182}2183 2184bool InstrRefBasedLDV::transferRegisterCopy(MachineInstr &MI) {2185  auto DestSrc = TII->isCopyLikeInstr(MI);2186  if (!DestSrc)2187    return false;2188 2189  const MachineOperand *DestRegOp = DestSrc->Destination;2190  const MachineOperand *SrcRegOp = DestSrc->Source;2191 2192  Register SrcReg = SrcRegOp->getReg();2193  Register DestReg = DestRegOp->getReg();2194 2195  // Ignore identity copies. Yep, these make it as far as LiveDebugValues.2196  if (SrcReg == DestReg)2197    return true;2198 2199  // For emulating VarLocBasedImpl:2200  // We want to recognize instructions where destination register is callee2201  // saved register. If register that could be clobbered by the call is2202  // included, there would be a great chance that it is going to be clobbered2203  // soon. It is more likely that previous register, which is callee saved, is2204  // going to stay unclobbered longer, even if it is killed.2205  //2206  // For InstrRefBasedImpl, we can track multiple locations per value, so2207  // ignore this condition.2208  if (EmulateOldLDV && !isCalleeSavedReg(DestReg))2209    return false;2210 2211  // InstrRefBasedImpl only followed killing copies.2212  if (EmulateOldLDV && !SrcRegOp->isKill())2213    return false;2214 2215  // Before we update MTracker, remember which values were present in each of2216  // the locations about to be overwritten, so that we can recover any2217  // potentially clobbered variables.2218  DenseMap<LocIdx, ValueIDNum> ClobberedLocs;2219  if (TTracker) {2220    for (MCRegAliasIterator RAI(DestReg, TRI, true); RAI.isValid(); ++RAI) {2221      LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI);2222      auto MLocIt = TTracker->ActiveMLocs.find(ClobberedLoc);2223      // If ActiveMLocs isn't tracking this location or there are no variables2224      // using it, don't bother remembering.2225      if (MLocIt == TTracker->ActiveMLocs.end() || MLocIt->second.empty())2226        continue;2227      ValueIDNum Value = MTracker->readReg(*RAI);2228      ClobberedLocs[ClobberedLoc] = Value;2229    }2230  }2231 2232  // Copy MTracker info, including subregs if available.2233  InstrRefBasedLDV::performCopy(SrcReg, DestReg);2234 2235  // The copy might have clobbered variables based on the destination register.2236  // Tell TTracker about it, passing the old ValueIDNum to search for2237  // alternative locations (or else terminating those variables).2238  if (TTracker) {2239    for (auto LocVal : ClobberedLocs) {2240      TTracker->clobberMloc(LocVal.first, LocVal.second, MI.getIterator(), false);2241    }2242  }2243 2244  // Only produce a transfer of DBG_VALUE within a block where old LDV2245  // would have. We might make use of the additional value tracking in some2246  // other way, later.2247  if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill())2248    TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg),2249                            MTracker->getRegMLoc(DestReg), MI.getIterator());2250 2251  // VarLocBasedImpl would quit tracking the old location after copying.2252  if (EmulateOldLDV && SrcReg != DestReg)2253    MTracker->defReg(SrcReg, CurBB, CurInst);2254 2255  return true;2256}2257 2258/// Accumulate a mapping between each DILocalVariable fragment and other2259/// fragments of that DILocalVariable which overlap. This reduces work during2260/// the data-flow stage from "Find any overlapping fragments" to "Check if the2261/// known-to-overlap fragments are present".2262/// \param MI A previously unprocessed debug instruction to analyze for2263///           fragment usage.2264void InstrRefBasedLDV::accumulateFragmentMap(MachineInstr &MI) {2265  assert(MI.isDebugValueLike());2266  DebugVariable MIVar(MI.getDebugVariable(), MI.getDebugExpression(),2267                      MI.getDebugLoc()->getInlinedAt());2268  FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();2269 2270  // If this is the first sighting of this variable, then we are guaranteed2271  // there are currently no overlapping fragments either. Initialize the set2272  // of seen fragments, record no overlaps for the current one, and return.2273  auto [SeenIt, Inserted] = SeenFragments.try_emplace(MIVar.getVariable());2274  if (Inserted) {2275    SeenIt->second.insert(ThisFragment);2276 2277    OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});2278    return;2279  }2280 2281  // If this particular Variable/Fragment pair already exists in the overlap2282  // map, it has already been accounted for.2283  auto IsInOLapMap =2284      OverlapFragments.insert({{MIVar.getVariable(), ThisFragment}, {}});2285  if (!IsInOLapMap.second)2286    return;2287 2288  auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;2289  auto &AllSeenFragments = SeenIt->second;2290 2291  // Otherwise, examine all other seen fragments for this variable, with "this"2292  // fragment being a previously unseen fragment. Record any pair of2293  // overlapping fragments.2294  for (const auto &ASeenFragment : AllSeenFragments) {2295    // Does this previously seen fragment overlap?2296    if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {2297      // Yes: Mark the current fragment as being overlapped.2298      ThisFragmentsOverlaps.push_back(ASeenFragment);2299      // Mark the previously seen fragment as being overlapped by the current2300      // one.2301      auto ASeenFragmentsOverlaps =2302          OverlapFragments.find({MIVar.getVariable(), ASeenFragment});2303      assert(ASeenFragmentsOverlaps != OverlapFragments.end() &&2304             "Previously seen var fragment has no vector of overlaps");2305      ASeenFragmentsOverlaps->second.push_back(ThisFragment);2306    }2307  }2308 2309  AllSeenFragments.insert(ThisFragment);2310}2311 2312void InstrRefBasedLDV::process(MachineInstr &MI,2313                               const FuncValueTable *MLiveOuts,2314                               const FuncValueTable *MLiveIns) {2315  // Try to interpret an MI as a debug or transfer instruction. Only if it's2316  // none of these should we interpret it's register defs as new value2317  // definitions.2318  if (transferDebugValue(MI))2319    return;2320  if (transferDebugInstrRef(MI, MLiveOuts, MLiveIns))2321    return;2322  if (transferDebugPHI(MI))2323    return;2324  if (transferRegisterCopy(MI))2325    return;2326  if (transferSpillOrRestoreInst(MI))2327    return;2328  transferRegisterDef(MI);2329}2330 2331void InstrRefBasedLDV::produceMLocTransferFunction(2332    MachineFunction &MF, SmallVectorImpl<MLocTransferMap> &MLocTransfer,2333    unsigned MaxNumBlocks) {2334  // Because we try to optimize around register mask operands by ignoring regs2335  // that aren't currently tracked, we set up something ugly for later: RegMask2336  // operands that are seen earlier than the first use of a register, still need2337  // to clobber that register in the transfer function. But this information2338  // isn't actively recorded. Instead, we track each RegMask used in each block,2339  // and accumulated the clobbered but untracked registers in each block into2340  // the following bitvector. Later, if new values are tracked, we can add2341  // appropriate clobbers.2342  SmallVector<BitVector, 32> BlockMasks;2343  BlockMasks.resize(MaxNumBlocks);2344 2345  // Reserve one bit per register for the masks described above.2346  unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs());2347  for (auto &BV : BlockMasks)2348    BV.resize(TRI->getNumRegs(), true);2349 2350  // Step through all instructions and inhale the transfer function.2351  for (auto &MBB : MF) {2352    // Object fields that are read by trackers to know where we are in the2353    // function.2354    CurBB = MBB.getNumber();2355    CurInst = 1;2356 2357    // Set all machine locations to a PHI value. For transfer function2358    // production only, this signifies the live-in value to the block.2359    MTracker->reset();2360    MTracker->setMPhis(CurBB);2361 2362    // Step through each instruction in this block.2363    for (auto &MI : MBB) {2364      // Pass in an empty unique_ptr for the value tables when accumulating the2365      // machine transfer function.2366      process(MI, nullptr, nullptr);2367 2368      // Also accumulate fragment map.2369      if (MI.isDebugValueLike())2370        accumulateFragmentMap(MI);2371 2372      // Create a map from the instruction number (if present) to the2373      // MachineInstr and its position.2374      if (uint64_t InstrNo = MI.peekDebugInstrNum()) {2375        auto InstrAndPos = std::make_pair(&MI, CurInst);2376        auto InsertResult =2377            DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos));2378 2379        // There should never be duplicate instruction numbers.2380        assert(InsertResult.second);2381        (void)InsertResult;2382      }2383 2384      ++CurInst;2385    }2386 2387    // Produce the transfer function, a map of machine location to new value. If2388    // any machine location has the live-in phi value from the start of the2389    // block, it's live-through and doesn't need recording in the transfer2390    // function.2391    for (auto Location : MTracker->locations()) {2392      LocIdx Idx = Location.Idx;2393      ValueIDNum &P = Location.Value;2394      if (P.isPHI() && P.getLoc() == Idx.asU64())2395        continue;2396 2397      // Insert-or-update.2398      auto &TransferMap = MLocTransfer[CurBB];2399      auto Result = TransferMap.insert(std::make_pair(Idx.asU64(), P));2400      if (!Result.second)2401        Result.first->second = P;2402    }2403 2404    // Accumulate any bitmask operands into the clobbered reg mask for this2405    // block.2406    for (auto &P : MTracker->Masks) {2407      BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords);2408    }2409  }2410 2411  // Compute a bitvector of all the registers that are tracked in this block.2412  BitVector UsedRegs(TRI->getNumRegs());2413  for (auto Location : MTracker->locations()) {2414    unsigned ID = MTracker->LocIdxToLocID[Location.Idx];2415    // Ignore stack slots, and aliases of the stack pointer.2416    if (ID >= TRI->getNumRegs() || MTracker->SPAliases.count(ID))2417      continue;2418    UsedRegs.set(ID);2419  }2420 2421  // Check that any regmask-clobber of a register that gets tracked, is not2422  // live-through in the transfer function. It needs to be clobbered at the2423  // very least.2424  for (unsigned int I = 0; I < MaxNumBlocks; ++I) {2425    BitVector &BV = BlockMasks[I];2426    BV.flip();2427    BV &= UsedRegs;2428    // This produces all the bits that we clobber, but also use. Check that2429    // they're all clobbered or at least set in the designated transfer2430    // elem.2431    for (unsigned Bit : BV.set_bits()) {2432      unsigned ID = MTracker->getLocID(Bit);2433      LocIdx Idx = MTracker->LocIDToLocIdx[ID];2434      auto &TransferMap = MLocTransfer[I];2435 2436      // Install a value representing the fact that this location is effectively2437      // written to in this block. As there's no reserved value, instead use2438      // a value number that is never generated. Pick the value number for the2439      // first instruction in the block, def'ing this location, which we know2440      // this block never used anyway.2441      ValueIDNum NotGeneratedNum = ValueIDNum(I, 1, Idx);2442      auto Result =2443        TransferMap.insert(std::make_pair(Idx.asU64(), NotGeneratedNum));2444      if (!Result.second) {2445        ValueIDNum &ValueID = Result.first->second;2446        if (ValueID.getBlock() == I && ValueID.isPHI())2447          // It was left as live-through. Set it to clobbered.2448          ValueID = NotGeneratedNum;2449      }2450    }2451  }2452}2453 2454bool InstrRefBasedLDV::mlocJoin(2455    MachineBasicBlock &MBB, SmallPtrSet<const MachineBasicBlock *, 16> &Visited,2456    FuncValueTable &OutLocs, ValueTable &InLocs) {2457  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");2458  bool Changed = false;2459 2460  // Handle value-propagation when control flow merges on entry to a block. For2461  // any location without a PHI already placed, the location has the same value2462  // as its predecessors. If a PHI is placed, test to see whether it's now a2463  // redundant PHI that we can eliminate.2464 2465  SmallVector<const MachineBasicBlock *, 8> BlockOrders(MBB.predecessors());2466 2467  // Visit predecessors in RPOT order.2468  auto Cmp = [&](const MachineBasicBlock *A, const MachineBasicBlock *B) {2469    return BBToOrder.find(A)->second < BBToOrder.find(B)->second;2470  };2471  llvm::sort(BlockOrders, Cmp);2472 2473  // Skip entry block.2474  if (BlockOrders.size() == 0) {2475    // FIXME: We don't use assert here to prevent instr-ref-unreachable.mir2476    // failing.2477    LLVM_DEBUG(if (!MBB.isEntryBlock()) dbgs()2478               << "Found not reachable block " << MBB.getFullName()2479               << " from entry which may lead out of "2480                  "bound access to VarLocs\n");2481    return false;2482  }2483 2484  // Step through all machine locations, look at each predecessor and test2485  // whether we can eliminate redundant PHIs.2486  for (auto Location : MTracker->locations()) {2487    LocIdx Idx = Location.Idx;2488 2489    // Pick out the first predecessors live-out value for this location. It's2490    // guaranteed to not be a backedge, as we order by RPO.2491    ValueIDNum FirstVal = OutLocs[*BlockOrders[0]][Idx.asU64()];2492 2493    // If we've already eliminated a PHI here, do no further checking, just2494    // propagate the first live-in value into this block.2495    if (InLocs[Idx.asU64()] != ValueIDNum(MBB.getNumber(), 0, Idx)) {2496      if (InLocs[Idx.asU64()] != FirstVal) {2497        InLocs[Idx.asU64()] = FirstVal;2498        Changed |= true;2499      }2500      continue;2501    }2502 2503    // We're now examining a PHI to see whether it's un-necessary. Loop around2504    // the other live-in values and test whether they're all the same.2505    bool Disagree = false;2506    for (unsigned int I = 1; I < BlockOrders.size(); ++I) {2507      const MachineBasicBlock *PredMBB = BlockOrders[I];2508      const ValueIDNum &PredLiveOut = OutLocs[*PredMBB][Idx.asU64()];2509 2510      // Incoming values agree, continue trying to eliminate this PHI.2511      if (FirstVal == PredLiveOut)2512        continue;2513 2514      // We can also accept a PHI value that feeds back into itself.2515      if (PredLiveOut == ValueIDNum(MBB.getNumber(), 0, Idx))2516        continue;2517 2518      // Live-out of a predecessor disagrees with the first predecessor.2519      Disagree = true;2520    }2521 2522    // No disagreement? No PHI. Otherwise, leave the PHI in live-ins.2523    if (!Disagree) {2524      InLocs[Idx.asU64()] = FirstVal;2525      Changed |= true;2526    }2527  }2528 2529  // TODO: Reimplement NumInserted and NumRemoved.2530  return Changed;2531}2532 2533void InstrRefBasedLDV::findStackIndexInterference(2534    SmallVectorImpl<unsigned> &Slots) {2535  // We could spend a bit of time finding the exact, minimal, set of stack2536  // indexes that interfere with each other, much like reg units. Or, we can2537  // rely on the fact that:2538  //  * The smallest / lowest index will interfere with everything at zero2539  //    offset, which will be the largest set of registers,2540  //  * Most indexes with non-zero offset will end up being interference units2541  //    anyway.2542  // So just pick those out and return them.2543 2544  // We can rely on a single-byte stack index existing already, because we2545  // initialize them in MLocTracker.2546  auto It = MTracker->StackSlotIdxes.find({8, 0});2547  assert(It != MTracker->StackSlotIdxes.end());2548  Slots.push_back(It->second);2549 2550  // Find anything that has a non-zero offset and add that too.2551  for (auto &Pair : MTracker->StackSlotIdxes) {2552    // Is offset zero? If so, ignore.2553    if (!Pair.first.second)2554      continue;2555    Slots.push_back(Pair.second);2556  }2557}2558 2559void InstrRefBasedLDV::placeMLocPHIs(2560    MachineFunction &MF, SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,2561    FuncValueTable &MInLocs, SmallVectorImpl<MLocTransferMap> &MLocTransfer) {2562  SmallVector<unsigned, 4> StackUnits;2563  findStackIndexInterference(StackUnits);2564 2565  // To avoid repeatedly running the PHI placement algorithm, leverage the2566  // fact that a def of register MUST also def its register units. Find the2567  // units for registers, place PHIs for them, and then replicate them for2568  // aliasing registers. Some inputs that are never def'd (DBG_PHIs of2569  // arguments) don't lead to register units being tracked, just place PHIs for2570  // those registers directly. Stack slots have their own form of "unit",2571  // store them to one side.2572  SmallSet<Register, 32> RegUnitsToPHIUp;2573  SmallSet<LocIdx, 32> NormalLocsToPHI;2574  SmallSet<SpillLocationNo, 32> StackSlots;2575  for (auto Location : MTracker->locations()) {2576    LocIdx L = Location.Idx;2577    if (MTracker->isSpill(L)) {2578      StackSlots.insert(MTracker->locIDToSpill(MTracker->LocIdxToLocID[L]));2579      continue;2580    }2581 2582    Register R = MTracker->LocIdxToLocID[L];2583    SmallSet<Register, 8> FoundRegUnits;2584    bool AnyIllegal = false;2585    for (MCRegUnit Unit : TRI->regunits(R.asMCReg())) {2586      for (MCRegUnitRootIterator URoot(Unit, TRI); URoot.isValid(); ++URoot) {2587        if (!MTracker->isRegisterTracked(*URoot)) {2588          // Not all roots were loaded into the tracking map: this register2589          // isn't actually def'd anywhere, we only read from it. Generate PHIs2590          // for this reg, but don't iterate units.2591          AnyIllegal = true;2592        } else {2593          FoundRegUnits.insert(*URoot);2594        }2595      }2596    }2597 2598    if (AnyIllegal) {2599      NormalLocsToPHI.insert(L);2600      continue;2601    }2602 2603    RegUnitsToPHIUp.insert_range(FoundRegUnits);2604  }2605 2606  // Lambda to fetch PHIs for a given location, and write into the PHIBlocks2607  // collection.2608  SmallVector<MachineBasicBlock *, 32> PHIBlocks;2609  auto CollectPHIsForLoc = [&](LocIdx L) {2610    // Collect the set of defs.2611    SmallPtrSet<MachineBasicBlock *, 32> DefBlocks;2612    for (MachineBasicBlock *MBB : OrderToBB) {2613      const auto &TransferFunc = MLocTransfer[MBB->getNumber()];2614      if (TransferFunc.contains(L))2615        DefBlocks.insert(MBB);2616    }2617 2618    // The entry block defs the location too: it's the live-in / argument value.2619    // Only insert if there are other defs though; everything is trivially live2620    // through otherwise.2621    if (!DefBlocks.empty())2622      DefBlocks.insert(&*MF.begin());2623 2624    // Ask the SSA construction algorithm where we should put PHIs. Clear2625    // anything that might have been hanging around from earlier.2626    PHIBlocks.clear();2627    BlockPHIPlacement(AllBlocks, DefBlocks, PHIBlocks);2628  };2629 2630  auto InstallPHIsAtLoc = [&PHIBlocks, &MInLocs](LocIdx L) {2631    for (const MachineBasicBlock *MBB : PHIBlocks)2632      MInLocs[*MBB][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L);2633  };2634 2635  // For locations with no reg units, just place PHIs.2636  for (LocIdx L : NormalLocsToPHI) {2637    CollectPHIsForLoc(L);2638    // Install those PHI values into the live-in value array.2639    InstallPHIsAtLoc(L);2640  }2641 2642  // For stack slots, calculate PHIs for the equivalent of the units, then2643  // install for each index.2644  for (SpillLocationNo Slot : StackSlots) {2645    for (unsigned Idx : StackUnits) {2646      unsigned SpillID = MTracker->getSpillIDWithIdx(Slot, Idx);2647      LocIdx L = MTracker->getSpillMLoc(SpillID);2648      CollectPHIsForLoc(L);2649      InstallPHIsAtLoc(L);2650 2651      // Find anything that aliases this stack index, install PHIs for it too.2652      unsigned Size, Offset;2653      std::tie(Size, Offset) = MTracker->StackIdxesToPos[Idx];2654      for (auto &Pair : MTracker->StackSlotIdxes) {2655        unsigned ThisSize, ThisOffset;2656        std::tie(ThisSize, ThisOffset) = Pair.first;2657        if (ThisSize + ThisOffset <= Offset || Size + Offset <= ThisOffset)2658          continue;2659 2660        unsigned ThisID = MTracker->getSpillIDWithIdx(Slot, Pair.second);2661        LocIdx ThisL = MTracker->getSpillMLoc(ThisID);2662        InstallPHIsAtLoc(ThisL);2663      }2664    }2665  }2666 2667  // For reg units, place PHIs, and then place them for any aliasing registers.2668  for (Register R : RegUnitsToPHIUp) {2669    LocIdx L = MTracker->lookupOrTrackRegister(MTracker->getLocID(R));2670    CollectPHIsForLoc(L);2671 2672    // Install those PHI values into the live-in value array.2673    InstallPHIsAtLoc(L);2674 2675    // Now find aliases and install PHIs for those.2676    for (MCRegAliasIterator RAI(R, TRI, true); RAI.isValid(); ++RAI) {2677      // Super-registers that are "above" the largest register read/written by2678      // the function will alias, but will not be tracked.2679      if (!MTracker->isRegisterTracked(*RAI))2680        continue;2681 2682      LocIdx AliasLoc =2683          MTracker->lookupOrTrackRegister(MTracker->getLocID(*RAI));2684      InstallPHIsAtLoc(AliasLoc);2685    }2686  }2687}2688 2689void InstrRefBasedLDV::buildMLocValueMap(2690    MachineFunction &MF, FuncValueTable &MInLocs, FuncValueTable &MOutLocs,2691    SmallVectorImpl<MLocTransferMap> &MLocTransfer) {2692  std::priority_queue<unsigned int, std::vector<unsigned int>,2693                      std::greater<unsigned int>>2694      Worklist, Pending;2695 2696  // We track what is on the current and pending worklist to avoid inserting2697  // the same thing twice. We could avoid this with a custom priority queue,2698  // but this is probably not worth it.2699  SmallPtrSet<MachineBasicBlock *, 16> OnPending, OnWorklist;2700 2701  // Initialize worklist with every block to be visited. Also produce list of2702  // all blocks.2703  SmallPtrSet<MachineBasicBlock *, 32> AllBlocks;2704  for (unsigned int I = 0; I < BBToOrder.size(); ++I) {2705    Worklist.push(I);2706    OnWorklist.insert(OrderToBB[I]);2707    AllBlocks.insert(OrderToBB[I]);2708  }2709 2710  // Initialize entry block to PHIs. These represent arguments.2711  for (auto Location : MTracker->locations())2712    MInLocs.tableForEntryMBB()[Location.Idx.asU64()] =2713        ValueIDNum(0, 0, Location.Idx);2714 2715  MTracker->reset();2716 2717  // Start by placing PHIs, using the usual SSA constructor algorithm. Consider2718  // any machine-location that isn't live-through a block to be def'd in that2719  // block.2720  placeMLocPHIs(MF, AllBlocks, MInLocs, MLocTransfer);2721 2722  // Propagate values to eliminate redundant PHIs. At the same time, this2723  // produces the table of Block x Location => Value for the entry to each2724  // block.2725  // The kind of PHIs we can eliminate are, for example, where one path in a2726  // conditional spills and restores a register, and the register still has2727  // the same value once control flow joins, unbeknowns to the PHI placement2728  // code. Propagating values allows us to identify such un-necessary PHIs and2729  // remove them.2730  SmallPtrSet<const MachineBasicBlock *, 16> Visited;2731  while (!Worklist.empty() || !Pending.empty()) {2732    // Vector for storing the evaluated block transfer function.2733    SmallVector<std::pair<LocIdx, ValueIDNum>, 32> ToRemap;2734 2735    while (!Worklist.empty()) {2736      MachineBasicBlock *MBB = OrderToBB[Worklist.top()];2737      CurBB = MBB->getNumber();2738      Worklist.pop();2739 2740      // Join the values in all predecessor blocks.2741      bool InLocsChanged;2742      InLocsChanged = mlocJoin(*MBB, Visited, MOutLocs, MInLocs[*MBB]);2743      InLocsChanged |= Visited.insert(MBB).second;2744 2745      // Don't examine transfer function if we've visited this loc at least2746      // once, and inlocs haven't changed.2747      if (!InLocsChanged)2748        continue;2749 2750      // Load the current set of live-ins into MLocTracker.2751      MTracker->loadFromArray(MInLocs[*MBB], CurBB);2752 2753      // Each element of the transfer function can be a new def, or a read of2754      // a live-in value. Evaluate each element, and store to "ToRemap".2755      ToRemap.clear();2756      for (auto &P : MLocTransfer[CurBB]) {2757        if (P.second.getBlock() == CurBB && P.second.isPHI()) {2758          // This is a movement of whatever was live in. Read it.2759          ValueIDNum NewID = MTracker->readMLoc(P.second.getLoc());2760          ToRemap.push_back(std::make_pair(P.first, NewID));2761        } else {2762          // It's a def. Just set it.2763          assert(P.second.getBlock() == CurBB);2764          ToRemap.push_back(std::make_pair(P.first, P.second));2765        }2766      }2767 2768      // Commit the transfer function changes into mloc tracker, which2769      // transforms the contents of the MLocTracker into the live-outs.2770      for (auto &P : ToRemap)2771        MTracker->setMLoc(P.first, P.second);2772 2773      // Now copy out-locs from mloc tracker into out-loc vector, checking2774      // whether changes have occurred. These changes can have come from both2775      // the transfer function, and mlocJoin.2776      bool OLChanged = false;2777      for (auto Location : MTracker->locations()) {2778        OLChanged |= MOutLocs[*MBB][Location.Idx.asU64()] != Location.Value;2779        MOutLocs[*MBB][Location.Idx.asU64()] = Location.Value;2780      }2781 2782      MTracker->reset();2783 2784      // No need to examine successors again if out-locs didn't change.2785      if (!OLChanged)2786        continue;2787 2788      // All successors should be visited: put any back-edges on the pending2789      // list for the next pass-through, and any other successors to be2790      // visited this pass, if they're not going to be already.2791      for (auto *s : MBB->successors()) {2792        // Does branching to this successor represent a back-edge?2793        unsigned Order = BBToOrder[s];2794        if (Order > BBToOrder[MBB]) {2795          // No: visit it during this dataflow iteration.2796          if (OnWorklist.insert(s).second)2797            Worklist.push(Order);2798        } else {2799          // Yes: visit it on the next iteration.2800          if (OnPending.insert(s).second)2801            Pending.push(Order);2802        }2803      }2804    }2805 2806    Worklist.swap(Pending);2807    std::swap(OnPending, OnWorklist);2808    OnPending.clear();2809    // At this point, pending must be empty, since it was just the empty2810    // worklist2811    assert(Pending.empty() && "Pending should be empty");2812  }2813 2814  // Once all the live-ins don't change on mlocJoin(), we've eliminated all2815  // redundant PHIs.2816}2817 2818void InstrRefBasedLDV::BlockPHIPlacement(2819    const SmallPtrSetImpl<MachineBasicBlock *> &AllBlocks,2820    const SmallPtrSetImpl<MachineBasicBlock *> &DefBlocks,2821    SmallVectorImpl<MachineBasicBlock *> &PHIBlocks) {2822  // Apply IDF calculator to the designated set of location defs, storing2823  // required PHIs into PHIBlocks. Uses the dominator tree stored in the2824  // InstrRefBasedLDV object.2825  IDFCalculatorBase<MachineBasicBlock, false> IDF(*DomTree);2826 2827  IDF.setLiveInBlocks(AllBlocks);2828  IDF.setDefiningBlocks(DefBlocks);2829  IDF.calculate(PHIBlocks);2830}2831 2832bool InstrRefBasedLDV::pickVPHILoc(2833    SmallVectorImpl<DbgOpID> &OutValues, const MachineBasicBlock &MBB,2834    const LiveIdxT &LiveOuts, FuncValueTable &MOutLocs,2835    const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) {2836 2837  // No predecessors means no PHIs.2838  if (BlockOrders.empty())2839    return false;2840 2841  // All the location operands that do not already agree need to be joined,2842  // track the indices of each such location operand here.2843  SmallDenseSet<unsigned> LocOpsToJoin;2844 2845  auto FirstValueIt = LiveOuts.find(BlockOrders[0]);2846  if (FirstValueIt == LiveOuts.end())2847    return false;2848  const DbgValue &FirstValue = *FirstValueIt->second;2849 2850  for (const auto p : BlockOrders) {2851    auto OutValIt = LiveOuts.find(p);2852    if (OutValIt == LiveOuts.end())2853      // If we have a predecessor not in scope, we'll never find a PHI position.2854      return false;2855    const DbgValue &OutVal = *OutValIt->second;2856 2857    // No-values cannot have locations we can join on.2858    if (OutVal.Kind == DbgValue::NoVal)2859      return false;2860 2861    // For unjoined VPHIs where we don't know the location, we definitely2862    // can't find a join loc unless the VPHI is a backedge.2863    if (OutVal.isUnjoinedPHI() && OutVal.BlockNo != MBB.getNumber())2864      return false;2865 2866    if (!FirstValue.Properties.isJoinable(OutVal.Properties))2867      return false;2868 2869    for (unsigned Idx = 0; Idx < FirstValue.getLocationOpCount(); ++Idx) {2870      // An unjoined PHI has no defined locations, and so a shared location must2871      // be found for every operand.2872      if (OutVal.isUnjoinedPHI()) {2873        LocOpsToJoin.insert(Idx);2874        continue;2875      }2876      DbgOpID FirstValOp = FirstValue.getDbgOpID(Idx);2877      DbgOpID OutValOp = OutVal.getDbgOpID(Idx);2878      if (FirstValOp != OutValOp) {2879        // We can never join constant ops - the ops must either both be equal2880        // constant ops or non-const ops.2881        if (FirstValOp.isConst() || OutValOp.isConst())2882          return false;2883        else2884          LocOpsToJoin.insert(Idx);2885      }2886    }2887  }2888 2889  SmallVector<DbgOpID> NewDbgOps;2890 2891  for (unsigned Idx = 0; Idx < FirstValue.getLocationOpCount(); ++Idx) {2892    // If this op doesn't need to be joined because the values agree, use that2893    // already-agreed value.2894    if (!LocOpsToJoin.contains(Idx)) {2895      NewDbgOps.push_back(FirstValue.getDbgOpID(Idx));2896      continue;2897    }2898 2899    std::optional<ValueIDNum> JoinedOpLoc =2900        pickOperandPHILoc(Idx, MBB, LiveOuts, MOutLocs, BlockOrders);2901 2902    if (!JoinedOpLoc)2903      return false;2904 2905    NewDbgOps.push_back(DbgOpStore.insert(*JoinedOpLoc));2906  }2907 2908  OutValues.append(NewDbgOps);2909  return true;2910}2911 2912std::optional<ValueIDNum> InstrRefBasedLDV::pickOperandPHILoc(2913    unsigned DbgOpIdx, const MachineBasicBlock &MBB, const LiveIdxT &LiveOuts,2914    FuncValueTable &MOutLocs,2915    const SmallVectorImpl<const MachineBasicBlock *> &BlockOrders) {2916 2917  // Collect a set of locations from predecessor where its live-out value can2918  // be found.2919  SmallVector<SmallVector<LocIdx, 4>, 8> Locs;2920  unsigned NumLocs = MTracker->getNumLocs();2921 2922  for (const auto p : BlockOrders) {2923    auto OutValIt = LiveOuts.find(p);2924    assert(OutValIt != LiveOuts.end());2925    const DbgValue &OutVal = *OutValIt->second;2926    DbgOpID OutValOpID = OutVal.getDbgOpID(DbgOpIdx);2927    DbgOp OutValOp = DbgOpStore.find(OutValOpID);2928    assert(!OutValOp.IsConst);2929 2930    // Create new empty vector of locations.2931    Locs.resize(Locs.size() + 1);2932 2933    // If the live-in value is a def, find the locations where that value is2934    // present. Do the same for VPHIs where we know the VPHI value.2935    if (OutVal.Kind == DbgValue::Def ||2936        (OutVal.Kind == DbgValue::VPHI && OutVal.BlockNo != MBB.getNumber() &&2937         !OutValOp.isUndef())) {2938      ValueIDNum ValToLookFor = OutValOp.ID;2939      // Search the live-outs of the predecessor for the specified value.2940      for (unsigned int I = 0; I < NumLocs; ++I) {2941        if (MOutLocs[*p][I] == ValToLookFor)2942          Locs.back().push_back(LocIdx(I));2943      }2944    } else {2945      assert(OutVal.Kind == DbgValue::VPHI);2946      // Otherwise: this is a VPHI on a backedge feeding back into itself, i.e.2947      // a value that's live-through the whole loop. (It has to be a backedge,2948      // because a block can't dominate itself). We can accept as a PHI location2949      // any location where the other predecessors agree, _and_ the machine2950      // locations feed back into themselves. Therefore, add all self-looping2951      // machine-value PHI locations.2952      for (unsigned int I = 0; I < NumLocs; ++I) {2953        ValueIDNum MPHI(MBB.getNumber(), 0, LocIdx(I));2954        if (MOutLocs[*p][I] == MPHI)2955          Locs.back().push_back(LocIdx(I));2956      }2957    }2958  }2959  // We should have found locations for all predecessors, or returned.2960  assert(Locs.size() == BlockOrders.size());2961 2962  // Starting with the first set of locations, take the intersection with2963  // subsequent sets.2964  SmallVector<LocIdx, 4> CandidateLocs = Locs[0];2965  for (unsigned int I = 1; I < Locs.size(); ++I) {2966    auto &LocVec = Locs[I];2967    SmallVector<LocIdx, 4> NewCandidates;2968    std::set_intersection(CandidateLocs.begin(), CandidateLocs.end(),2969                          LocVec.begin(), LocVec.end(), std::inserter(NewCandidates, NewCandidates.begin()));2970    CandidateLocs = std::move(NewCandidates);2971  }2972  if (CandidateLocs.empty())2973    return std::nullopt;2974 2975  // We now have a set of LocIdxes that contain the right output value in2976  // each of the predecessors. Pick the lowest; if there's a register loc,2977  // that'll be it.2978  LocIdx L = *CandidateLocs.begin();2979 2980  // Return a PHI-value-number for the found location.2981  ValueIDNum PHIVal = {(unsigned)MBB.getNumber(), 0, L};2982  return PHIVal;2983}2984 2985bool InstrRefBasedLDV::vlocJoin(2986    MachineBasicBlock &MBB, LiveIdxT &VLOCOutLocs,2987    SmallPtrSet<const MachineBasicBlock *, 8> &BlocksToExplore,2988    DbgValue &LiveIn) {2989  LLVM_DEBUG(dbgs() << "join MBB: " << MBB.getNumber() << "\n");2990  bool Changed = false;2991 2992  // Order predecessors by RPOT order, for exploring them in that order.2993  SmallVector<MachineBasicBlock *, 8> BlockOrders(MBB.predecessors());2994 2995  auto Cmp = [&](MachineBasicBlock *A, MachineBasicBlock *B) {2996    return BBToOrder[A] < BBToOrder[B];2997  };2998 2999  llvm::sort(BlockOrders, Cmp);3000 3001  unsigned CurBlockRPONum = BBToOrder[&MBB];3002 3003  // Collect all the incoming DbgValues for this variable, from predecessor3004  // live-out values.3005  SmallVector<InValueT, 8> Values;3006  bool Bail = false;3007  int BackEdgesStart = 0;3008  for (auto *p : BlockOrders) {3009    // If the predecessor isn't in scope / to be explored, we'll never be3010    // able to join any locations.3011    if (!BlocksToExplore.contains(p)) {3012      Bail = true;3013      break;3014    }3015 3016    // All Live-outs will have been initialized.3017    DbgValue &OutLoc = *VLOCOutLocs.find(p)->second;3018 3019    // Keep track of where back-edges begin in the Values vector. Relies on3020    // BlockOrders being sorted by RPO.3021    unsigned ThisBBRPONum = BBToOrder[p];3022    if (ThisBBRPONum < CurBlockRPONum)3023      ++BackEdgesStart;3024 3025    Values.push_back(std::make_pair(p, &OutLoc));3026  }3027 3028  // If there were no values, or one of the predecessors couldn't have a3029  // value, then give up immediately. It's not safe to produce a live-in3030  // value. Leave as whatever it was before.3031  if (Bail || Values.size() == 0)3032    return false;3033 3034  // All (non-entry) blocks have at least one non-backedge predecessor.3035  // Pick the variable value from the first of these, to compare against3036  // all others.3037  const DbgValue &FirstVal = *Values[0].second;3038 3039  // If the old live-in value is not a PHI then either a) no PHI is needed3040  // here, or b) we eliminated the PHI that was here. If so, we can just3041  // propagate in the first parent's incoming value.3042  if (LiveIn.Kind != DbgValue::VPHI || LiveIn.BlockNo != MBB.getNumber()) {3043    Changed = LiveIn != FirstVal;3044    if (Changed)3045      LiveIn = FirstVal;3046    return Changed;3047  }3048 3049  // Scan for variable values that can never be resolved: if they have3050  // different DIExpressions, different indirectness, or are mixed constants /3051  // non-constants.3052  for (const auto &V : Values) {3053    if (!V.second->Properties.isJoinable(FirstVal.Properties))3054      return false;3055    if (V.second->Kind == DbgValue::NoVal)3056      return false;3057    if (!V.second->hasJoinableLocOps(FirstVal))3058      return false;3059  }3060 3061  // Try to eliminate this PHI. Do the incoming values all agree?3062  bool Disagree = false;3063  for (auto &V : Values) {3064    if (*V.second == FirstVal)3065      continue; // No disagreement.3066 3067    // If both values are not equal but have equal non-empty IDs then they refer3068    // to the same value from different sources (e.g. one is VPHI and the other3069    // is Def), which does not cause disagreement.3070    if (V.second->hasIdenticalValidLocOps(FirstVal))3071      continue;3072 3073    // Eliminate if a backedge feeds a VPHI back into itself.3074    if (V.second->Kind == DbgValue::VPHI &&3075        V.second->BlockNo == MBB.getNumber() &&3076        // Is this a backedge?3077        std::distance(Values.begin(), &V) >= BackEdgesStart)3078      continue;3079 3080    Disagree = true;3081  }3082 3083  // No disagreement -> live-through value.3084  if (!Disagree) {3085    Changed = LiveIn != FirstVal;3086    if (Changed)3087      LiveIn = FirstVal;3088    return Changed;3089  } else {3090    // Otherwise use a VPHI.3091    DbgValue VPHI(MBB.getNumber(), FirstVal.Properties, DbgValue::VPHI);3092    Changed = LiveIn != VPHI;3093    if (Changed)3094      LiveIn = VPHI;3095    return Changed;3096  }3097}3098 3099void InstrRefBasedLDV::getBlocksForScope(3100    const DILocation *DILoc,3101    SmallPtrSetImpl<const MachineBasicBlock *> &BlocksToExplore,3102    const SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks) {3103  // Get the set of "normal" in-lexical-scope blocks.3104  LS.getMachineBasicBlocks(DILoc, BlocksToExplore);3105 3106  // VarLoc LiveDebugValues tracks variable locations that are defined in3107  // blocks not in scope. This is something we could legitimately ignore, but3108  // lets allow it for now for the sake of coverage.3109  BlocksToExplore.insert_range(AssignBlocks);3110 3111  // Storage for artificial blocks we intend to add to BlocksToExplore.3112  DenseSet<const MachineBasicBlock *> ToAdd;3113 3114  // To avoid needlessly dropping large volumes of variable locations, propagate3115  // variables through aritifical blocks, i.e. those that don't have any3116  // instructions in scope at all. To accurately replicate VarLoc3117  // LiveDebugValues, this means exploring all artificial successors too.3118  // Perform a depth-first-search to enumerate those blocks.3119  for (const auto *MBB : BlocksToExplore) {3120    // Depth-first-search state: each node is a block and which successor3121    // we're currently exploring.3122    SmallVector<std::pair<const MachineBasicBlock *,3123                          MachineBasicBlock::const_succ_iterator>,3124                8>3125        DFS;3126 3127    // Find any artificial successors not already tracked.3128    for (auto *succ : MBB->successors()) {3129      if (BlocksToExplore.count(succ))3130        continue;3131      if (!ArtificialBlocks.count(succ))3132        continue;3133      ToAdd.insert(succ);3134      DFS.push_back({succ, succ->succ_begin()});3135    }3136 3137    // Search all those blocks, depth first.3138    while (!DFS.empty()) {3139      const MachineBasicBlock *CurBB = DFS.back().first;3140      MachineBasicBlock::const_succ_iterator &CurSucc = DFS.back().second;3141      // Walk back if we've explored this blocks successors to the end.3142      if (CurSucc == CurBB->succ_end()) {3143        DFS.pop_back();3144        continue;3145      }3146 3147      // If the current successor is artificial and unexplored, descend into3148      // it.3149      if (!ToAdd.count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) {3150        ToAdd.insert(*CurSucc);3151        DFS.push_back({*CurSucc, (*CurSucc)->succ_begin()});3152        continue;3153      }3154 3155      ++CurSucc;3156    }3157  };3158 3159  BlocksToExplore.insert_range(ToAdd);3160}3161 3162void InstrRefBasedLDV::buildVLocValueMap(3163    const DILocation *DILoc,3164    const SmallSet<DebugVariableID, 4> &VarsWeCareAbout,3165    SmallPtrSetImpl<MachineBasicBlock *> &AssignBlocks, LiveInsT &Output,3166    FuncValueTable &MOutLocs, FuncValueTable &MInLocs,3167    SmallVectorImpl<VLocTracker> &AllTheVLocs) {3168  // This method is much like buildMLocValueMap: but focuses on a single3169  // LexicalScope at a time. Pick out a set of blocks and variables that are3170  // to have their value assignments solved, then run our dataflow algorithm3171  // until a fixedpoint is reached.3172  std::priority_queue<unsigned int, std::vector<unsigned int>,3173                      std::greater<unsigned int>>3174      Worklist, Pending;3175  SmallPtrSet<MachineBasicBlock *, 16> OnWorklist, OnPending;3176 3177  // The set of blocks we'll be examining.3178  SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;3179 3180  // The order in which to examine them (RPO).3181  SmallVector<MachineBasicBlock *, 16> BlockOrders;3182  SmallVector<unsigned, 32> BlockOrderNums;3183 3184  getBlocksForScope(DILoc, BlocksToExplore, AssignBlocks);3185 3186  // Single block scope: not interesting! No propagation at all. Note that3187  // this could probably go above ArtificialBlocks without damage, but3188  // that then produces output differences from original-live-debug-values,3189  // which propagates from a single block into many artificial ones.3190  if (BlocksToExplore.size() == 1)3191    return;3192 3193  // Convert a const set to a non-const set. LexicalScopes3194  // getMachineBasicBlocks returns const MBB pointers, IDF wants mutable ones.3195  // (Neither of them mutate anything).3196  SmallPtrSet<MachineBasicBlock *, 8> MutBlocksToExplore;3197  for (const auto *MBB : BlocksToExplore)3198    MutBlocksToExplore.insert(const_cast<MachineBasicBlock *>(MBB));3199 3200  // Picks out relevants blocks RPO order and sort them. Sort their3201  // order-numbers and map back to MBB pointers later, to avoid repeated3202  // DenseMap queries during comparisons.3203  for (const auto *MBB : BlocksToExplore)3204    BlockOrderNums.push_back(BBToOrder[MBB]);3205 3206  llvm::sort(BlockOrderNums);3207  for (unsigned int I : BlockOrderNums)3208    BlockOrders.push_back(OrderToBB[I]);3209  BlockOrderNums.clear();3210  unsigned NumBlocks = BlockOrders.size();3211 3212  // Allocate some vectors for storing the live ins and live outs. Large.3213  SmallVector<DbgValue, 32> LiveIns, LiveOuts;3214  LiveIns.reserve(NumBlocks);3215  LiveOuts.reserve(NumBlocks);3216 3217  // Initialize all values to start as NoVals. This signifies "it's live3218  // through, but we don't know what it is".3219  DbgValueProperties EmptyProperties(EmptyExpr, false, false);3220  for (unsigned int I = 0; I < NumBlocks; ++I) {3221    DbgValue EmptyDbgValue(I, EmptyProperties, DbgValue::NoVal);3222    LiveIns.push_back(EmptyDbgValue);3223    LiveOuts.push_back(EmptyDbgValue);3224  }3225 3226  // Produce by-MBB indexes of live-in/live-outs, to ease lookup within3227  // vlocJoin.3228  LiveIdxT LiveOutIdx, LiveInIdx;3229  LiveOutIdx.reserve(NumBlocks);3230  LiveInIdx.reserve(NumBlocks);3231  for (unsigned I = 0; I < NumBlocks; ++I) {3232    LiveOutIdx[BlockOrders[I]] = &LiveOuts[I];3233    LiveInIdx[BlockOrders[I]] = &LiveIns[I];3234  }3235 3236  // Loop over each variable and place PHIs for it, then propagate values3237  // between blocks. This keeps the locality of working on one lexical scope at3238  // at time, but avoids re-processing variable values because some other3239  // variable has been assigned.3240  for (DebugVariableID VarID : VarsWeCareAbout) {3241    // Re-initialize live-ins and live-outs, to clear the remains of previous3242    // variables live-ins / live-outs.3243    for (unsigned int I = 0; I < NumBlocks; ++I) {3244      DbgValue EmptyDbgValue(I, EmptyProperties, DbgValue::NoVal);3245      LiveIns[I] = EmptyDbgValue;3246      LiveOuts[I] = EmptyDbgValue;3247    }3248 3249    // Place PHIs for variable values, using the LLVM IDF calculator.3250    // Collect the set of blocks where variables are def'd.3251    SmallPtrSet<MachineBasicBlock *, 32> DefBlocks;3252    for (const MachineBasicBlock *ExpMBB : BlocksToExplore) {3253      auto &TransferFunc = AllTheVLocs[ExpMBB->getNumber()].Vars;3254      if (TransferFunc.contains(VarID))3255        DefBlocks.insert(const_cast<MachineBasicBlock *>(ExpMBB));3256    }3257 3258    SmallVector<MachineBasicBlock *, 32> PHIBlocks;3259 3260    // Request the set of PHIs we should insert for this variable. If there's3261    // only one value definition, things are very simple.3262    if (DefBlocks.size() == 1) {3263      placePHIsForSingleVarDefinition(MutBlocksToExplore, *DefBlocks.begin(),3264                                      AllTheVLocs, VarID, Output);3265      continue;3266    }3267 3268    // Otherwise: we need to place PHIs through SSA and propagate values.3269    BlockPHIPlacement(MutBlocksToExplore, DefBlocks, PHIBlocks);3270 3271    // Insert PHIs into the per-block live-in tables for this variable.3272    for (MachineBasicBlock *PHIMBB : PHIBlocks) {3273      unsigned BlockNo = PHIMBB->getNumber();3274      DbgValue *LiveIn = LiveInIdx[PHIMBB];3275      *LiveIn = DbgValue(BlockNo, EmptyProperties, DbgValue::VPHI);3276    }3277 3278    for (auto *MBB : BlockOrders) {3279      Worklist.push(BBToOrder[MBB]);3280      OnWorklist.insert(MBB);3281    }3282 3283    // Iterate over all the blocks we selected, propagating the variables value.3284    // This loop does two things:3285    //  * Eliminates un-necessary VPHIs in vlocJoin,3286    //  * Evaluates the blocks transfer function (i.e. variable assignments) and3287    //    stores the result to the blocks live-outs.3288    // Always evaluate the transfer function on the first iteration, and when3289    // the live-ins change thereafter.3290    bool FirstTrip = true;3291    while (!Worklist.empty() || !Pending.empty()) {3292      while (!Worklist.empty()) {3293        auto *MBB = OrderToBB[Worklist.top()];3294        CurBB = MBB->getNumber();3295        Worklist.pop();3296 3297        auto LiveInsIt = LiveInIdx.find(MBB);3298        assert(LiveInsIt != LiveInIdx.end());3299        DbgValue *LiveIn = LiveInsIt->second;3300 3301        // Join values from predecessors. Updates LiveInIdx, and writes output3302        // into JoinedInLocs.3303        bool InLocsChanged =3304            vlocJoin(*MBB, LiveOutIdx, BlocksToExplore, *LiveIn);3305 3306        SmallVector<const MachineBasicBlock *, 8> Preds(MBB->predecessors());3307 3308        // If this block's live-in value is a VPHI, try to pick a machine-value3309        // for it. This makes the machine-value available and propagated3310        // through all blocks by the time value propagation finishes. We can't3311        // do this any earlier as it needs to read the block live-outs.3312        if (LiveIn->Kind == DbgValue::VPHI && LiveIn->BlockNo == (int)CurBB) {3313          // There's a small possibility that on a preceeding path, a VPHI is3314          // eliminated and transitions from VPHI-with-location to3315          // live-through-value. As a result, the selected location of any VPHI3316          // might change, so we need to re-compute it on each iteration.3317          SmallVector<DbgOpID> JoinedOps;3318 3319          if (pickVPHILoc(JoinedOps, *MBB, LiveOutIdx, MOutLocs, Preds)) {3320            bool NewLocPicked = !equal(LiveIn->getDbgOpIDs(), JoinedOps);3321            InLocsChanged |= NewLocPicked;3322            if (NewLocPicked)3323              LiveIn->setDbgOpIDs(JoinedOps);3324          }3325        }3326 3327        if (!InLocsChanged && !FirstTrip)3328          continue;3329 3330        DbgValue *LiveOut = LiveOutIdx[MBB];3331        bool OLChanged = false;3332 3333        // Do transfer function.3334        auto &VTracker = AllTheVLocs[MBB->getNumber()];3335        auto TransferIt = VTracker.Vars.find(VarID);3336        if (TransferIt != VTracker.Vars.end()) {3337          // Erase on empty transfer (DBG_VALUE $noreg).3338          if (TransferIt->second.Kind == DbgValue::Undef) {3339            DbgValue NewVal(MBB->getNumber(), EmptyProperties, DbgValue::NoVal);3340            if (*LiveOut != NewVal) {3341              *LiveOut = NewVal;3342              OLChanged = true;3343            }3344          } else {3345            // Insert new variable value; or overwrite.3346            if (*LiveOut != TransferIt->second) {3347              *LiveOut = TransferIt->second;3348              OLChanged = true;3349            }3350          }3351        } else {3352          // Just copy live-ins to live-outs, for anything not transferred.3353          if (*LiveOut != *LiveIn) {3354            *LiveOut = *LiveIn;3355            OLChanged = true;3356          }3357        }3358 3359        // If no live-out value changed, there's no need to explore further.3360        if (!OLChanged)3361          continue;3362 3363        // We should visit all successors. Ensure we'll visit any non-backedge3364        // successors during this dataflow iteration; book backedge successors3365        // to be visited next time around.3366        for (auto *s : MBB->successors()) {3367          // Ignore out of scope / not-to-be-explored successors.3368          if (!LiveInIdx.contains(s))3369            continue;3370 3371          unsigned Order = BBToOrder[s];3372          if (Order > BBToOrder[MBB]) {3373            if (OnWorklist.insert(s).second)3374              Worklist.push(Order);3375          } else if (OnPending.insert(s).second && (FirstTrip || OLChanged)) {3376            Pending.push(Order);3377          }3378        }3379      }3380      Worklist.swap(Pending);3381      std::swap(OnWorklist, OnPending);3382      OnPending.clear();3383      assert(Pending.empty());3384      FirstTrip = false;3385    }3386 3387    // Save live-ins to output vector. Ignore any that are still marked as being3388    // VPHIs with no location -- those are variables that we know the value of,3389    // but are not actually available in the register file.3390    for (auto *MBB : BlockOrders) {3391      DbgValue *BlockLiveIn = LiveInIdx[MBB];3392      if (BlockLiveIn->Kind == DbgValue::NoVal)3393        continue;3394      if (BlockLiveIn->isUnjoinedPHI())3395        continue;3396      if (BlockLiveIn->Kind == DbgValue::VPHI)3397        BlockLiveIn->Kind = DbgValue::Def;3398      [[maybe_unused]] auto &[Var, DILoc] = DVMap.lookupDVID(VarID);3399      assert(BlockLiveIn->Properties.DIExpr->getFragmentInfo() ==3400                 Var.getFragment() &&3401             "Fragment info missing during value prop");3402      Output[MBB->getNumber()].push_back(std::make_pair(VarID, *BlockLiveIn));3403    }3404  } // Per-variable loop.3405 3406  BlockOrders.clear();3407  BlocksToExplore.clear();3408}3409 3410void InstrRefBasedLDV::placePHIsForSingleVarDefinition(3411    const SmallPtrSetImpl<MachineBasicBlock *> &InScopeBlocks,3412    MachineBasicBlock *AssignMBB, SmallVectorImpl<VLocTracker> &AllTheVLocs,3413    DebugVariableID VarID, LiveInsT &Output) {3414  // If there is a single definition of the variable, then working out it's3415  // value everywhere is very simple: it's every block dominated by the3416  // definition. At the dominance frontier, the usual algorithm would:3417  //  * Place PHIs,3418  //  * Propagate values into them,3419  //  * Find there's no incoming variable value from the other incoming branches3420  //    of the dominance frontier,3421  //  * Specify there's no variable value in blocks past the frontier.3422  // This is a common case, hence it's worth special-casing it.3423 3424  // Pick out the variables value from the block transfer function.3425  VLocTracker &VLocs = AllTheVLocs[AssignMBB->getNumber()];3426  auto ValueIt = VLocs.Vars.find(VarID);3427  const DbgValue &Value = ValueIt->second;3428 3429  // If it's an explicit assignment of "undef", that means there is no location3430  // anyway, anywhere.3431  if (Value.Kind == DbgValue::Undef)3432    return;3433 3434  // Assign the variable value to entry to each dominated block that's in scope.3435  // Skip the definition block -- it's assigned the variable value in the middle3436  // of the block somewhere.3437  for (auto *ScopeBlock : InScopeBlocks) {3438    if (!DomTree->properlyDominates(AssignMBB, ScopeBlock))3439      continue;3440 3441    Output[ScopeBlock->getNumber()].push_back({VarID, Value});3442  }3443 3444  // All blocks that aren't dominated have no live-in value, thus no variable3445  // value will be given to them.3446}3447 3448#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)3449void InstrRefBasedLDV::dump_mloc_transfer(3450    const MLocTransferMap &mloc_transfer) const {3451  for (const auto &P : mloc_transfer) {3452    std::string foo = MTracker->LocIdxToName(P.first);3453    std::string bar = MTracker->IDAsString(P.second);3454    dbgs() << "Loc " << foo << " --> " << bar << "\n";3455  }3456}3457#endif3458 3459void InstrRefBasedLDV::initialSetup(MachineFunction &MF) {3460  // Build some useful data structures.3461 3462  LLVMContext &Context = MF.getFunction().getContext();3463  EmptyExpr = DIExpression::get(Context, {});3464 3465  auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {3466    if (const DebugLoc &DL = MI.getDebugLoc())3467      return DL.getLine() != 0;3468    return false;3469  };3470 3471  // Collect a set of all the artificial blocks. Collect the size too, ilist3472  // size calls are O(n).3473  unsigned int Size = 0;3474  for (auto &MBB : MF) {3475    ++Size;3476    if (none_of(MBB.instrs(), hasNonArtificialLocation))3477      ArtificialBlocks.insert(&MBB);3478  }3479 3480  // Compute mappings of block <=> RPO order.3481  ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);3482  unsigned int RPONumber = 0;3483  OrderToBB.reserve(Size);3484  BBToOrder.reserve(Size);3485  BBNumToRPO.reserve(Size);3486  auto processMBB = [&](MachineBasicBlock *MBB) {3487    OrderToBB.push_back(MBB);3488    BBToOrder[MBB] = RPONumber;3489    BBNumToRPO[MBB->getNumber()] = RPONumber;3490    ++RPONumber;3491  };3492  for (MachineBasicBlock *MBB : RPOT)3493    processMBB(MBB);3494  for (MachineBasicBlock &MBB : MF)3495    if (!BBToOrder.contains(&MBB))3496      processMBB(&MBB);3497 3498  // Order value substitutions by their "source" operand pair, for quick lookup.3499  llvm::sort(MF.DebugValueSubstitutions);3500 3501#ifdef EXPENSIVE_CHECKS3502  // As an expensive check, test whether there are any duplicate substitution3503  // sources in the collection.3504  if (MF.DebugValueSubstitutions.size() > 2) {3505    for (auto It = MF.DebugValueSubstitutions.begin();3506         It != std::prev(MF.DebugValueSubstitutions.end()); ++It) {3507      assert(It->Src != std::next(It)->Src && "Duplicate variable location "3508                                              "substitution seen");3509    }3510  }3511#endif3512}3513 3514// Produce an "ejection map" for blocks, i.e., what's the highest-numbered3515// lexical scope it's used in. When exploring in DFS order and we pass that3516// scope, the block can be processed and any tracking information freed.3517void InstrRefBasedLDV::makeDepthFirstEjectionMap(3518    SmallVectorImpl<unsigned> &EjectionMap,3519    const ScopeToDILocT &ScopeToDILocation,3520    ScopeToAssignBlocksT &ScopeToAssignBlocks) {3521  SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;3522  SmallVector<std::pair<LexicalScope *, ssize_t>, 4> WorkStack;3523  auto *TopScope = LS.getCurrentFunctionScope();3524 3525  // Unlike lexical scope explorers, we explore in reverse order, to find the3526  // "last" lexical scope used for each block early.3527  WorkStack.push_back({TopScope, TopScope->getChildren().size() - 1});3528 3529  while (!WorkStack.empty()) {3530    auto &ScopePosition = WorkStack.back();3531    LexicalScope *WS = ScopePosition.first;3532    ssize_t ChildNum = ScopePosition.second--;3533 3534    const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();3535    if (ChildNum >= 0) {3536      // If ChildNum is positive, there are remaining children to explore.3537      // Push the child and its children-count onto the stack.3538      auto &ChildScope = Children[ChildNum];3539      WorkStack.push_back(3540          std::make_pair(ChildScope, ChildScope->getChildren().size() - 1));3541    } else {3542      WorkStack.pop_back();3543 3544      // We've explored all children and any later blocks: examine all blocks3545      // in our scope. If they haven't yet had an ejection number set, then3546      // this scope will be the last to use that block.3547      auto DILocationIt = ScopeToDILocation.find(WS);3548      if (DILocationIt != ScopeToDILocation.end()) {3549        getBlocksForScope(DILocationIt->second, BlocksToExplore,3550                          ScopeToAssignBlocks.find(WS)->second);3551        for (const auto *MBB : BlocksToExplore) {3552          unsigned BBNum = MBB->getNumber();3553          if (EjectionMap[BBNum] == 0)3554            EjectionMap[BBNum] = WS->getDFSOut();3555        }3556 3557        BlocksToExplore.clear();3558      }3559    }3560  }3561}3562 3563bool InstrRefBasedLDV::depthFirstVLocAndEmit(3564    unsigned MaxNumBlocks, const ScopeToDILocT &ScopeToDILocation,3565    const ScopeToVarsT &ScopeToVars, ScopeToAssignBlocksT &ScopeToAssignBlocks,3566    LiveInsT &Output, FuncValueTable &MOutLocs, FuncValueTable &MInLocs,3567    SmallVectorImpl<VLocTracker> &AllTheVLocs, MachineFunction &MF,3568    bool ShouldEmitDebugEntryValues) {3569  TTracker = new TransferTracker(TII, MTracker, MF, DVMap, *TRI,3570                                 CalleeSavedRegs, ShouldEmitDebugEntryValues);3571  unsigned NumLocs = MTracker->getNumLocs();3572  VTracker = nullptr;3573 3574  // No scopes? No variable locations.3575  if (!LS.getCurrentFunctionScope())3576    return false;3577 3578  // Build map from block number to the last scope that uses the block.3579  SmallVector<unsigned, 16> EjectionMap;3580  EjectionMap.resize(MaxNumBlocks, 0);3581  makeDepthFirstEjectionMap(EjectionMap, ScopeToDILocation,3582                            ScopeToAssignBlocks);3583 3584  // Helper lambda for ejecting a block -- if nothing is going to use the block,3585  // we can translate the variable location information into DBG_VALUEs and then3586  // free all of InstrRefBasedLDV's data structures.3587  auto EjectBlock = [&](MachineBasicBlock &MBB) -> void {3588    unsigned BBNum = MBB.getNumber();3589    AllTheVLocs[BBNum].clear();3590 3591    // Prime the transfer-tracker, and then step through all the block3592    // instructions, installing transfers.3593    MTracker->reset();3594    MTracker->loadFromArray(MInLocs[MBB], BBNum);3595    TTracker->loadInlocs(MBB, MInLocs[MBB], DbgOpStore, Output[BBNum], NumLocs);3596 3597    CurBB = BBNum;3598    CurInst = 1;3599    for (auto &MI : MBB) {3600      process(MI, &MOutLocs, &MInLocs);3601      TTracker->checkInstForNewValues(CurInst, MI.getIterator());3602      ++CurInst;3603    }3604 3605    // Free machine-location tables for this block.3606    MInLocs.ejectTableForBlock(MBB);3607    MOutLocs.ejectTableForBlock(MBB);3608    // We don't need live-in variable values for this block either.3609    Output[BBNum].clear();3610    AllTheVLocs[BBNum].clear();3611  };3612 3613  SmallPtrSet<const MachineBasicBlock *, 8> BlocksToExplore;3614  SmallVector<std::pair<LexicalScope *, ssize_t>, 4> WorkStack;3615  WorkStack.push_back({LS.getCurrentFunctionScope(), 0});3616  unsigned HighestDFSIn = 0;3617 3618  // Proceed to explore in depth first order.3619  while (!WorkStack.empty()) {3620    auto &ScopePosition = WorkStack.back();3621    LexicalScope *WS = ScopePosition.first;3622    ssize_t ChildNum = ScopePosition.second++;3623 3624    // We obesrve scopes with children twice here, once descending in, once3625    // ascending out of the scope nest. Use HighestDFSIn as a ratchet to ensure3626    // we don't process a scope twice. Additionally, ignore scopes that don't3627    // have a DILocation -- by proxy, this means we never tracked any variable3628    // assignments in that scope.3629    auto DILocIt = ScopeToDILocation.find(WS);3630    if (HighestDFSIn <= WS->getDFSIn() && DILocIt != ScopeToDILocation.end()) {3631      const DILocation *DILoc = DILocIt->second;3632      auto &VarsWeCareAbout = ScopeToVars.find(WS)->second;3633      auto &BlocksInScope = ScopeToAssignBlocks.find(WS)->second;3634 3635      buildVLocValueMap(DILoc, VarsWeCareAbout, BlocksInScope, Output, MOutLocs,3636                        MInLocs, AllTheVLocs);3637    }3638 3639    HighestDFSIn = std::max(HighestDFSIn, WS->getDFSIn());3640 3641    // Descend into any scope nests.3642    const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();3643    if (ChildNum < (ssize_t)Children.size()) {3644      // There are children to explore -- push onto stack and continue.3645      auto &ChildScope = Children[ChildNum];3646      WorkStack.push_back(std::make_pair(ChildScope, 0));3647    } else {3648      WorkStack.pop_back();3649 3650      // We've explored a leaf, or have explored all the children of a scope.3651      // Try to eject any blocks where this is the last scope it's relevant to.3652      auto DILocationIt = ScopeToDILocation.find(WS);3653      if (DILocationIt == ScopeToDILocation.end())3654        continue;3655 3656      getBlocksForScope(DILocationIt->second, BlocksToExplore,3657                        ScopeToAssignBlocks.find(WS)->second);3658      for (const auto *MBB : BlocksToExplore)3659        if (WS->getDFSOut() == EjectionMap[MBB->getNumber()])3660          EjectBlock(const_cast<MachineBasicBlock &>(*MBB));3661 3662      BlocksToExplore.clear();3663    }3664  }3665 3666  // Some artificial blocks may not have been ejected, meaning they're not3667  // connected to an actual legitimate scope. This can technically happen3668  // with things like the entry block. In theory, we shouldn't need to do3669  // anything for such out-of-scope blocks, but for the sake of being similar3670  // to VarLocBasedLDV, eject these too.3671  for (auto *MBB : ArtificialBlocks)3672    if (MInLocs.hasTableFor(*MBB))3673      EjectBlock(*MBB);3674 3675  return emitTransfers();3676}3677 3678bool InstrRefBasedLDV::emitTransfers() {3679  // Go through all the transfers recorded in the TransferTracker -- this is3680  // both the live-ins to a block, and any movements of values that happen3681  // in the middle.3682  for (auto &P : TTracker->Transfers) {3683    // We have to insert DBG_VALUEs in a consistent order, otherwise they3684    // appear in DWARF in different orders. Use the order that they appear3685    // when walking through each block / each instruction, stored in3686    // DVMap.3687    llvm::sort(P.Insts, llvm::less_first());3688 3689    // Insert either before or after the designated point...3690    if (P.MBB) {3691      MachineBasicBlock &MBB = *P.MBB;3692      for (const auto &Pair : P.Insts)3693        MBB.insert(P.Pos, Pair.second);3694    } else {3695      // Terminators, like tail calls, can clobber things. Don't try and place3696      // transfers after them.3697      if (P.Pos->isTerminator())3698        continue;3699 3700      MachineBasicBlock &MBB = *P.Pos->getParent();3701      for (const auto &Pair : P.Insts)3702        MBB.insertAfterBundle(P.Pos, Pair.second);3703    }3704  }3705 3706  return TTracker->Transfers.size() != 0;3707}3708 3709/// Calculate the liveness information for the given machine function and3710/// extend ranges across basic blocks.3711bool InstrRefBasedLDV::ExtendRanges(MachineFunction &MF,3712                                    MachineDominatorTree *DomTree,3713                                    bool ShouldEmitDebugEntryValues,3714                                    unsigned InputBBLimit,3715                                    unsigned InputDbgValLimit) {3716  // No subprogram means this function contains no debuginfo.3717  if (!MF.getFunction().getSubprogram())3718    return false;3719 3720  LLVM_DEBUG(dbgs() << "\nDebug Range Extension\n");3721 3722  this->DomTree = DomTree;3723  TRI = MF.getSubtarget().getRegisterInfo();3724  MRI = &MF.getRegInfo();3725  TII = MF.getSubtarget().getInstrInfo();3726  TFI = MF.getSubtarget().getFrameLowering();3727  TFI->getCalleeSaves(MF, CalleeSavedRegs);3728  MFI = &MF.getFrameInfo();3729  LS.scanFunction(MF);3730 3731  const auto &STI = MF.getSubtarget();3732  AdjustsStackInCalls = MFI->adjustsStack() &&3733                        STI.getFrameLowering()->stackProbeFunctionModifiesSP();3734  if (AdjustsStackInCalls)3735    StackProbeSymbolName = STI.getTargetLowering()->getStackProbeSymbolName(MF);3736 3737  MTracker =3738      new MLocTracker(MF, *TII, *TRI, *MF.getSubtarget().getTargetLowering());3739  VTracker = nullptr;3740  TTracker = nullptr;3741 3742  SmallVector<MLocTransferMap, 32> MLocTransfer;3743  SmallVector<VLocTracker, 8> vlocs;3744  LiveInsT SavedLiveIns;3745 3746  int MaxNumBlocks = -1;3747  for (auto &MBB : MF)3748    MaxNumBlocks = std::max(MBB.getNumber(), MaxNumBlocks);3749  assert(MaxNumBlocks >= 0);3750  ++MaxNumBlocks;3751 3752  initialSetup(MF);3753 3754  MLocTransfer.resize(MaxNumBlocks);3755  vlocs.resize(MaxNumBlocks, VLocTracker(DVMap, OverlapFragments, EmptyExpr));3756  SavedLiveIns.resize(MaxNumBlocks);3757 3758  produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks);3759 3760  // Allocate and initialize two array-of-arrays for the live-in and live-out3761  // machine values. The outer dimension is the block number; while the inner3762  // dimension is a LocIdx from MLocTracker.3763  unsigned NumLocs = MTracker->getNumLocs();3764  FuncValueTable MOutLocs(MaxNumBlocks, NumLocs);3765  FuncValueTable MInLocs(MaxNumBlocks, NumLocs);3766 3767  // Solve the machine value dataflow problem using the MLocTransfer function,3768  // storing the computed live-ins / live-outs into the array-of-arrays. We use3769  // both live-ins and live-outs for decision making in the variable value3770  // dataflow problem.3771  buildMLocValueMap(MF, MInLocs, MOutLocs, MLocTransfer);3772 3773  // Patch up debug phi numbers, turning unknown block-live-in values into3774  // either live-through machine values, or PHIs.3775  for (auto &DBG_PHI : DebugPHINumToValue) {3776    // Identify unresolved block-live-ins.3777    if (!DBG_PHI.ValueRead)3778      continue;3779 3780    ValueIDNum &Num = *DBG_PHI.ValueRead;3781    if (!Num.isPHI())3782      continue;3783 3784    unsigned BlockNo = Num.getBlock();3785    LocIdx LocNo = Num.getLoc();3786    ValueIDNum ResolvedValue = MInLocs[BlockNo][LocNo.asU64()];3787    // If there is no resolved value for this live-in then it is not directly3788    // reachable from the entry block -- model it as a PHI on entry to this3789    // block, which means we leave the ValueIDNum unchanged.3790    if (ResolvedValue != ValueIDNum::EmptyValue)3791      Num = ResolvedValue;3792  }3793  // Later, we'll be looking up ranges of instruction numbers.3794  llvm::sort(DebugPHINumToValue);3795 3796  // Walk back through each block / instruction, collecting DBG_VALUE3797  // instructions and recording what machine value their operands refer to.3798  for (MachineBasicBlock *MBB : OrderToBB) {3799    CurBB = MBB->getNumber();3800    VTracker = &vlocs[CurBB];3801    VTracker->MBB = MBB;3802    MTracker->loadFromArray(MInLocs[*MBB], CurBB);3803    CurInst = 1;3804    for (auto &MI : *MBB) {3805      process(MI, &MOutLocs, &MInLocs);3806      ++CurInst;3807    }3808    MTracker->reset();3809  }3810 3811  // Map from one LexicalScope to all the variables in that scope.3812  ScopeToVarsT ScopeToVars;3813 3814  // Map from One lexical scope to all blocks where assignments happen for3815  // that scope.3816  ScopeToAssignBlocksT ScopeToAssignBlocks;3817 3818  // Store map of DILocations that describes scopes.3819  ScopeToDILocT ScopeToDILocation;3820 3821  // To mirror old LiveDebugValues, enumerate variables in RPOT order. Otherwise3822  // the order is unimportant, it just has to be stable.3823  unsigned VarAssignCount = 0;3824  for (MachineBasicBlock *MBB : OrderToBB) {3825    auto *VTracker = &vlocs[MBB->getNumber()];3826    // Collect each variable with a DBG_VALUE in this block.3827    for (auto &idx : VTracker->Vars) {3828      DebugVariableID VarID = idx.first;3829      const DILocation *ScopeLoc = VTracker->Scopes[VarID];3830      assert(ScopeLoc != nullptr);3831      auto *Scope = LS.findLexicalScope(ScopeLoc);3832 3833      // No insts in scope -> shouldn't have been recorded.3834      assert(Scope != nullptr);3835 3836      ScopeToVars[Scope].insert(VarID);3837      ScopeToAssignBlocks[Scope].insert(VTracker->MBB);3838      ScopeToDILocation[Scope] = ScopeLoc;3839      ++VarAssignCount;3840    }3841  }3842 3843  bool Changed = false;3844 3845  // If we have an extremely large number of variable assignments and blocks,3846  // bail out at this point. We've burnt some time doing analysis already,3847  // however we should cut our losses.3848  if ((unsigned)MaxNumBlocks > InputBBLimit &&3849      VarAssignCount > InputDbgValLimit) {3850    LLVM_DEBUG(dbgs() << "Disabling InstrRefBasedLDV: " << MF.getName()3851                      << " has " << MaxNumBlocks << " basic blocks and "3852                      << VarAssignCount3853                      << " variable assignments, exceeding limits.\n");3854  } else {3855    // Optionally, solve the variable value problem and emit to blocks by using3856    // a lexical-scope-depth search. It should be functionally identical to3857    // the "else" block of this condition.3858    Changed = depthFirstVLocAndEmit(3859        MaxNumBlocks, ScopeToDILocation, ScopeToVars, ScopeToAssignBlocks,3860        SavedLiveIns, MOutLocs, MInLocs, vlocs, MF, ShouldEmitDebugEntryValues);3861  }3862 3863  delete MTracker;3864  delete TTracker;3865  MTracker = nullptr;3866  VTracker = nullptr;3867  TTracker = nullptr;3868 3869  ArtificialBlocks.clear();3870  OrderToBB.clear();3871  BBToOrder.clear();3872  BBNumToRPO.clear();3873  DebugInstrNumToInstr.clear();3874  DebugPHINumToValue.clear();3875  OverlapFragments.clear();3876  SeenFragments.clear();3877  SeenDbgPHIs.clear();3878  DbgOpStore.clear();3879  DVMap.clear();3880 3881  return Changed;3882}3883 3884LDVImpl *llvm::makeInstrRefBasedLiveDebugValues() {3885  return new InstrRefBasedLDV();3886}3887 3888namespace {3889class LDVSSABlock;3890class LDVSSAUpdater;3891 3892// Pick a type to identify incoming block values as we construct SSA. We3893// can't use anything more robust than an integer unfortunately, as SSAUpdater3894// expects to zero-initialize the type.3895typedef uint64_t BlockValueNum;3896 3897/// Represents an SSA PHI node for the SSA updater class. Contains the block3898/// this PHI is in, the value number it would have, and the expected incoming3899/// values from parent blocks.3900class LDVSSAPhi {3901public:3902  SmallVector<std::pair<LDVSSABlock *, BlockValueNum>, 4> IncomingValues;3903  LDVSSABlock *ParentBlock;3904  BlockValueNum PHIValNum;3905  LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock)3906      : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {}3907 3908  LDVSSABlock *getParent() { return ParentBlock; }3909};3910 3911/// Thin wrapper around a block predecessor iterator. Only difference from a3912/// normal block iterator is that it dereferences to an LDVSSABlock.3913class LDVSSABlockIterator {3914public:3915  MachineBasicBlock::pred_iterator PredIt;3916  LDVSSAUpdater &Updater;3917 3918  LDVSSABlockIterator(MachineBasicBlock::pred_iterator PredIt,3919                      LDVSSAUpdater &Updater)3920      : PredIt(PredIt), Updater(Updater) {}3921 3922  bool operator!=(const LDVSSABlockIterator &OtherIt) const {3923    return OtherIt.PredIt != PredIt;3924  }3925 3926  LDVSSABlockIterator &operator++() {3927    ++PredIt;3928    return *this;3929  }3930 3931  LDVSSABlock *operator*();3932};3933 3934/// Thin wrapper around a block for SSA Updater interface. Necessary because3935/// we need to track the PHI value(s) that we may have observed as necessary3936/// in this block.3937class LDVSSABlock {3938public:3939  MachineBasicBlock &BB;3940  LDVSSAUpdater &Updater;3941  using PHIListT = SmallVector<LDVSSAPhi, 1>;3942  /// List of PHIs in this block. There should only ever be one.3943  PHIListT PHIList;3944 3945  LDVSSABlock(MachineBasicBlock &BB, LDVSSAUpdater &Updater)3946      : BB(BB), Updater(Updater) {}3947 3948  LDVSSABlockIterator succ_begin() {3949    return LDVSSABlockIterator(BB.succ_begin(), Updater);3950  }3951 3952  LDVSSABlockIterator succ_end() {3953    return LDVSSABlockIterator(BB.succ_end(), Updater);3954  }3955 3956  /// SSAUpdater has requested a PHI: create that within this block record.3957  LDVSSAPhi *newPHI(BlockValueNum Value) {3958    PHIList.emplace_back(Value, this);3959    return &PHIList.back();3960  }3961 3962  /// SSAUpdater wishes to know what PHIs already exist in this block.3963  PHIListT &phis() { return PHIList; }3964};3965 3966/// Utility class for the SSAUpdater interface: tracks blocks, PHIs and values3967/// while SSAUpdater is exploring the CFG. It's passed as a handle / baton to3968// SSAUpdaterTraits<LDVSSAUpdater>.3969class LDVSSAUpdater {3970public:3971  /// Map of value numbers to PHI records.3972  DenseMap<BlockValueNum, LDVSSAPhi *> PHIs;3973  /// Map of which blocks generate Undef values -- blocks that are not3974  /// dominated by any Def.3975  DenseMap<MachineBasicBlock *, BlockValueNum> PoisonMap;3976  /// Map of machine blocks to our own records of them.3977  DenseMap<MachineBasicBlock *, LDVSSABlock *> BlockMap;3978  /// Machine location where any PHI must occur.3979  LocIdx Loc;3980  /// Table of live-in machine value numbers for blocks / locations.3981  const FuncValueTable &MLiveIns;3982 3983  LDVSSAUpdater(LocIdx L, const FuncValueTable &MLiveIns)3984      : Loc(L), MLiveIns(MLiveIns) {}3985 3986  void reset() {3987    for (auto &Block : BlockMap)3988      delete Block.second;3989 3990    PHIs.clear();3991    PoisonMap.clear();3992    BlockMap.clear();3993  }3994 3995  ~LDVSSAUpdater() { reset(); }3996 3997  /// For a given MBB, create a wrapper block for it. Stores it in the3998  /// LDVSSAUpdater block map.3999  LDVSSABlock *getSSALDVBlock(MachineBasicBlock *BB) {4000    auto [It, Inserted] = BlockMap.try_emplace(BB);4001    if (Inserted)4002      It->second = new LDVSSABlock(*BB, *this);4003    return It->second;4004  }4005 4006  /// Find the live-in value number for the given block. Looks up the value at4007  /// the PHI location on entry.4008  BlockValueNum getValue(LDVSSABlock *LDVBB) {4009    return MLiveIns[LDVBB->BB][Loc.asU64()].asU64();4010  }4011};4012 4013LDVSSABlock *LDVSSABlockIterator::operator*() {4014  return Updater.getSSALDVBlock(*PredIt);4015}4016 4017#ifndef NDEBUG4018 4019raw_ostream &operator<<(raw_ostream &out, const LDVSSAPhi &PHI) {4020  out << "SSALDVPHI " << PHI.PHIValNum;4021  return out;4022}4023 4024#endif4025 4026} // namespace4027 4028namespace llvm {4029 4030/// Template specialization to give SSAUpdater access to CFG and value4031/// information. SSAUpdater calls methods in these traits, passing in the4032/// LDVSSAUpdater object, to learn about blocks and the values they define.4033/// It also provides methods to create PHI nodes and track them.4034template <> class SSAUpdaterTraits<LDVSSAUpdater> {4035public:4036  using BlkT = LDVSSABlock;4037  using ValT = BlockValueNum;4038  using PhiT = LDVSSAPhi;4039  using BlkSucc_iterator = LDVSSABlockIterator;4040 4041  // Methods to access block successors -- dereferencing to our wrapper class.4042  static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }4043  static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }4044 4045  /// Iterator for PHI operands.4046  class PHI_iterator {4047  private:4048    LDVSSAPhi *PHI;4049    unsigned Idx;4050 4051  public:4052    explicit PHI_iterator(LDVSSAPhi *P) // begin iterator4053        : PHI(P), Idx(0) {}4054    PHI_iterator(LDVSSAPhi *P, bool) // end iterator4055        : PHI(P), Idx(PHI->IncomingValues.size()) {}4056 4057    PHI_iterator &operator++() {4058      Idx++;4059      return *this;4060    }4061    bool operator==(const PHI_iterator &X) const { return Idx == X.Idx; }4062    bool operator!=(const PHI_iterator &X) const { return !operator==(X); }4063 4064    BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; }4065 4066    LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; }4067  };4068 4069  static inline PHI_iterator PHI_begin(PhiT *PHI) { return PHI_iterator(PHI); }4070 4071  static inline PHI_iterator PHI_end(PhiT *PHI) {4072    return PHI_iterator(PHI, true);4073  }4074 4075  /// FindPredecessorBlocks - Put the predecessors of BB into the Preds4076  /// vector.4077  static void FindPredecessorBlocks(LDVSSABlock *BB,4078                                    SmallVectorImpl<LDVSSABlock *> *Preds) {4079    for (MachineBasicBlock *Pred : BB->BB.predecessors())4080      Preds->push_back(BB->Updater.getSSALDVBlock(Pred));4081  }4082 4083  /// GetPoisonVal - Normally creates an IMPLICIT_DEF instruction with a new4084  /// register. For LiveDebugValues, represents a block identified as not having4085  /// any DBG_PHI predecessors.4086  static BlockValueNum GetPoisonVal(LDVSSABlock *BB, LDVSSAUpdater *Updater) {4087    // Create a value number for this block -- it needs to be unique and in the4088    // "poison" collection, so that we know it's not real. Use a number4089    // representing a PHI into this block.4090    BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64();4091    Updater->PoisonMap[&BB->BB] = Num;4092    return Num;4093  }4094 4095  /// CreateEmptyPHI - Create a (representation of a) PHI in the given block.4096  /// SSAUpdater will populate it with information about incoming values. The4097  /// value number of this PHI is whatever the  machine value number problem4098  /// solution determined it to be. This includes non-phi values if SSAUpdater4099  /// tries to create a PHI where the incoming values are identical.4100  static BlockValueNum CreateEmptyPHI(LDVSSABlock *BB, unsigned NumPreds,4101                                   LDVSSAUpdater *Updater) {4102    BlockValueNum PHIValNum = Updater->getValue(BB);4103    LDVSSAPhi *PHI = BB->newPHI(PHIValNum);4104    Updater->PHIs[PHIValNum] = PHI;4105    return PHIValNum;4106  }4107 4108  /// AddPHIOperand - Add the specified value as an operand of the PHI for4109  /// the specified predecessor block.4110  static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) {4111    PHI->IncomingValues.push_back(std::make_pair(Pred, Val));4112  }4113 4114  /// ValueIsPHI - Check if the instruction that defines the specified value4115  /// is a PHI instruction.4116  static LDVSSAPhi *ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {4117    return Updater->PHIs.lookup(Val);4118  }4119 4120  /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source4121  /// operands, i.e., it was just added.4122  static LDVSSAPhi *ValueIsNewPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {4123    LDVSSAPhi *PHI = ValueIsPHI(Val, Updater);4124    if (PHI && PHI->IncomingValues.size() == 0)4125      return PHI;4126    return nullptr;4127  }4128 4129  /// GetPHIValue - For the specified PHI instruction, return the value4130  /// that it defines.4131  static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; }4132};4133 4134} // end namespace llvm4135 4136std::optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIs(4137    MachineFunction &MF, const FuncValueTable &MLiveOuts,4138    const FuncValueTable &MLiveIns, MachineInstr &Here, uint64_t InstrNum) {4139  // This function will be called twice per DBG_INSTR_REF, and might end up4140  // computing lots of SSA information: memoize it.4141  auto SeenDbgPHIIt = SeenDbgPHIs.find(std::make_pair(&Here, InstrNum));4142  if (SeenDbgPHIIt != SeenDbgPHIs.end())4143    return SeenDbgPHIIt->second;4144 4145  std::optional<ValueIDNum> Result =4146      resolveDbgPHIsImpl(MF, MLiveOuts, MLiveIns, Here, InstrNum);4147  SeenDbgPHIs.insert({std::make_pair(&Here, InstrNum), Result});4148  return Result;4149}4150 4151std::optional<ValueIDNum> InstrRefBasedLDV::resolveDbgPHIsImpl(4152    MachineFunction &MF, const FuncValueTable &MLiveOuts,4153    const FuncValueTable &MLiveIns, MachineInstr &Here, uint64_t InstrNum) {4154  // Pick out records of DBG_PHI instructions that have been observed. If there4155  // are none, then we cannot compute a value number.4156  auto RangePair = std::equal_range(DebugPHINumToValue.begin(),4157                                    DebugPHINumToValue.end(), InstrNum);4158  auto LowerIt = RangePair.first;4159  auto UpperIt = RangePair.second;4160 4161  // No DBG_PHI means there can be no location.4162  if (LowerIt == UpperIt)4163    return std::nullopt;4164 4165  // If any DBG_PHIs referred to a location we didn't understand, don't try to4166  // compute a value. There might be scenarios where we could recover a value4167  // for some range of DBG_INSTR_REFs, but at this point we can have high4168  // confidence that we've seen a bug.4169  auto DBGPHIRange = make_range(LowerIt, UpperIt);4170  for (const DebugPHIRecord &DBG_PHI : DBGPHIRange)4171    if (!DBG_PHI.ValueRead)4172      return std::nullopt;4173 4174  // If there's only one DBG_PHI, then that is our value number.4175  if (std::distance(LowerIt, UpperIt) == 1)4176    return *LowerIt->ValueRead;4177 4178  // Pick out the location (physreg, slot) where any PHIs must occur. It's4179  // technically possible for us to merge values in different registers in each4180  // block, but highly unlikely that LLVM will generate such code after register4181  // allocation.4182  LocIdx Loc = *LowerIt->ReadLoc;4183 4184  // We have several DBG_PHIs, and a use position (the Here inst). All each4185  // DBG_PHI does is identify a value at a program position. We can treat each4186  // DBG_PHI like it's a Def of a value, and the use position is a Use of a4187  // value, just like SSA. We use the bulk-standard LLVM SSA updater class to4188  // determine which Def is used at the Use, and any PHIs that happen along4189  // the way.4190  // Adapted LLVM SSA Updater:4191  LDVSSAUpdater Updater(Loc, MLiveIns);4192  // Map of which Def or PHI is the current value in each block.4193  DenseMap<LDVSSABlock *, BlockValueNum> AvailableValues;4194  // Set of PHIs that we have created along the way.4195  SmallVector<LDVSSAPhi *, 8> CreatedPHIs;4196 4197  // Each existing DBG_PHI is a Def'd value under this model. Record these Defs4198  // for the SSAUpdater.4199  for (const auto &DBG_PHI : DBGPHIRange) {4200    LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);4201    const ValueIDNum &Num = *DBG_PHI.ValueRead;4202    AvailableValues.insert(std::make_pair(Block, Num.asU64()));4203  }4204 4205  LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.getParent());4206  const auto &AvailIt = AvailableValues.find(HereBlock);4207  if (AvailIt != AvailableValues.end()) {4208    // Actually, we already know what the value is -- the Use is in the same4209    // block as the Def.4210    return ValueIDNum::fromU64(AvailIt->second);4211  }4212 4213  // Otherwise, we must use the SSA Updater. It will identify the value number4214  // that we are to use, and the PHIs that must happen along the way.4215  SSAUpdaterImpl<LDVSSAUpdater> Impl(&Updater, &AvailableValues, &CreatedPHIs);4216  BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.getParent()));4217  ValueIDNum Result = ValueIDNum::fromU64(ResultInt);4218 4219  // We have the number for a PHI, or possibly live-through value, to be used4220  // at this Use. There are a number of things we have to check about it though:4221  //  * Does any PHI use an 'Undef' (like an IMPLICIT_DEF) value? If so, this4222  //    Use was not completely dominated by DBG_PHIs and we should abort.4223  //  * Are the Defs or PHIs clobbered in a block? SSAUpdater isn't aware that4224  //    we've left SSA form. Validate that the inputs to each PHI are the4225  //    expected values.4226  //  * Is a PHI we've created actually a merging of values, or are all the4227  //    predecessor values the same, leading to a non-PHI machine value number?4228  //    (SSAUpdater doesn't know that either). Remap validated PHIs into the4229  //    the ValidatedValues collection below to sort this out.4230  DenseMap<LDVSSABlock *, ValueIDNum> ValidatedValues;4231 4232  // Define all the input DBG_PHI values in ValidatedValues.4233  for (const auto &DBG_PHI : DBGPHIRange) {4234    LDVSSABlock *Block = Updater.getSSALDVBlock(DBG_PHI.MBB);4235    const ValueIDNum &Num = *DBG_PHI.ValueRead;4236    ValidatedValues.insert(std::make_pair(Block, Num));4237  }4238 4239  // Sort PHIs to validate into RPO-order.4240  SmallVector<LDVSSAPhi *, 8> SortedPHIs(CreatedPHIs);4241 4242  llvm::sort(SortedPHIs, [&](LDVSSAPhi *A, LDVSSAPhi *B) {4243    return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];4244  });4245 4246  for (auto &PHI : SortedPHIs) {4247    ValueIDNum ThisBlockValueNum = MLiveIns[PHI->ParentBlock->BB][Loc.asU64()];4248 4249    // Are all these things actually defined?4250    for (auto &PHIIt : PHI->IncomingValues) {4251      // Any undef input means DBG_PHIs didn't dominate the use point.4252      if (Updater.PoisonMap.contains(&PHIIt.first->BB))4253        return std::nullopt;4254 4255      ValueIDNum ValueToCheck;4256      const ValueTable &BlockLiveOuts = MLiveOuts[PHIIt.first->BB];4257 4258      auto VVal = ValidatedValues.find(PHIIt.first);4259      if (VVal == ValidatedValues.end()) {4260        // We cross a loop, and this is a backedge. LLVMs tail duplication4261        // happens so late that DBG_PHI instructions should not be able to4262        // migrate into loops -- meaning we can only be live-through this4263        // loop.4264        ValueToCheck = ThisBlockValueNum;4265      } else {4266        // Does the block have as a live-out, in the location we're examining,4267        // the value that we expect? If not, it's been moved or clobbered.4268        ValueToCheck = VVal->second;4269      }4270 4271      if (BlockLiveOuts[Loc.asU64()] != ValueToCheck)4272        return std::nullopt;4273    }4274 4275    // Record this value as validated.4276    ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum});4277  }4278 4279  // All the PHIs are valid: we can return what the SSAUpdater said our value4280  // number was.4281  return Result;4282}4283