Lines Matching +full:fetch +full:- +full:depth
1 //===- InstrRefBasedImpl.cpp - Tracking Debug Value MIs -------------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
17 /// map of instruction-to-value is then translated into a register (or spill)
22 /// completed, and we can't alter it just to make debug-info complete. Thus:
29 /// another value), then re-compute an SSA-form representation of the
30 /// MachineFunction, using value propagation to eliminate any un-necessary
37 /// any un-necessary PHIs. This gives us a map of each variable to the value
43 /// After which we can marry-up variable values with a location, and emit
51 /// is proportional to the working-set size of the function, which the compiler
79 //===----------------------------------------------------------------------===//
105 #include "llvm/Config/llvm-config.h"
141 static cl::opt<bool> EmulateOldLDV("emulate-old-livedebugvalues", cl::Hidden,
151 // carefully thinking about -- instead, they probably autogenerated the code.
155 StackWorkingSetLimit("livedebugvalues-max-stack-slots", cl::Hidden,
156 cl::desc("livedebugvalues-stack-ws-limit"),
163 /// specifying block live-in locations and transfers within blocks.
165 /// Operating on a per-block basis, this class takes a (pre-loaded) MLocTracker
166 /// and must be initialized with the set of variable values that are live-in to
168 /// out variable locations for the live-in variable values (if there _is_ a
173 /// This is where debug use-before-defs would be resolved: a variable with an
175 /// value becomes available. Or, we could detect clobbers and re-specify the
181 /// This machine location tracker is assumed to always contain the up-to-date
194 MachineBasicBlock *MBB; /// non-null if we should insert after.
201 /// qualifying meta-information needed to construct a concrete DBG_VALUE-like
224 /// Local cache of what-value-is-in-what-LocIdx. Used to identify differences
232 /// VarLocs[Idx] != MTracker->LocIdxToIDNum[Idx].
243 /// Record of a use-before-def: created when a value that's live-in to the
264 /// collection prevents the use-before-def materializing.
282 unsigned Reg = MTracker->LocIdxToLocID[L];
283 if (Reg >= MTracker->NumRegs)
293 // slots generally live longer than callee-saved registers which generally
294 // live longer than non-callee-saved registers. The minimum value of 0
337 if (MTracker->isSpill(L))
348 /// For a variable \p Var with the live-in value \p Value, attempts to resolve
353 /// \p MBB is the basic block that we are loading the live-in value for.
354 /// \p DbgOpStore is the map containing the DbgOpID->DbgOp mapping needed to
395 ValuesPreferredLoc->first == Num);
397 if (ValuesPreferredLoc->second.isIllegal()) {
399 // use-before-def to be resolved as we step through the block.
414 LocIdx M = ValuesPreferredLoc->second.getLoc();
437 Result.first->second = NewValue;
440 std::make_pair(VarID, &*MTracker->emitLoc(ResolvedDbgOps, Var, DILoc,
444 /// Load object with live-in variable values. \p mlocs contains the live-in
445 /// values in each machine location, while \p vlocs the live-in variable
446 /// values. This method picks variable locations for the live-in variables,
465 // Initialized the preferred-location map with illegal locations, to be
481 for (auto Location : MTracker->locations()) {
492 if (VIt == ValueToLoc.end() || VIt->first != VNum)
495 auto &Previous = VIt->second;
521 /// processed, check whether it defines a variable value in a use-before-def.
535 for (auto &Use : MIt->second) {
554 for (auto Location : MTracker->locations()) {
563 auto &Previous = VIt->second;
574 for (auto &Use : MIt->second) {
585 LocIdx NewLoc = ValueToLoc.find(Op.ID)->second.getLoc();
600 Use.VarID, MTracker->emitLoc(DbgOps, Var, DILoc, Use.Properties)));
612 if (MBB && Pos == MBB->begin())
613 BundleStart = MBB->instr_begin();
615 BundleStart = getBundleStart(Pos->getIterator());
623 if (!Var.getVariable()->isParameter())
629 if (Expr->getNumElements() > 0 && !Expr->isDeref())
636 // Must be in entry block (block number zero), and be a PHI / live-in value.
641 if (MTracker->isSpill(Val.getLoc()))
644 Register SP = TLI->getStackPointerRegisterToSaveRestore();
646 Register Reg = MTracker->LocIdxToLocID[Val.getLoc()];
662 // If this debug value can be converted to be non-variadic, then do so;
684 Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];
694 MI.getDebugLoc()->getInlinedAt());
698 // Ignore non-register locations, we don't transfer those.
704 for (LocIdx Loc : It->second.loc_indices())
708 // Any use-before-defs no longer apply.
718 LocIdx NewLoc = MTracker->getRegMLoc(Reg);
734 MI.getDebugLoc()->getInlinedAt());
736 // Any use-before-defs no longer apply.
742 for (LocIdx Loc : It->second.loc_indices())
760 // Check whether our local copy of values-by-location in #VarLocs is out
763 if (MTracker->readMLoc(NewLoc) != VarLocs[NewLoc.asU64()]) {
767 for (LocIdx Loc : LostVLocIt->second.loc_indices()) {
782 VarLocs[NewLoc.asU64()] = MTracker->readMLoc(NewLoc);
792 It->second.Ops.assign(NewLocs);
793 It->second.Properties = Properties;
825 for (auto Loc : MTracker->locations())
833 for (DebugVariableID VarID : ActiveMLocIt->second) {
834 auto &Prop = ActiveVLocs.find(VarID)->second.Properties;
844 // MLoc is dead, so end their existing MLoc->Var mappings as well.
846 for (DebugVariableID VarID : ActiveMLocIt->second) {
848 // Re-state the variable location: if there's no replacement then NewLoc
851 const DbgValueProperties &Properties = ActiveVLocIt->second.Properties;
853 // Produce the new list of debug ops - an empty list if no new location
854 // was found, or the existing list with the substitution MLoc -> NewLoc
861 DbgOps.insert(DbgOps.begin(), ActiveVLocIt->second.Ops.size(),
863 replace_copy(ActiveVLocIt->second.Ops, DbgOps.begin(), OldOp, NewOp);
868 VarID, &*MTracker->emitLoc(DbgOps, Var, DILoc, Properties)));
873 for (LocIdx Loc : ActiveVLocIt->second.loc_indices()) {
879 ActiveVLocIt->second.Ops = DbgOps;
891 LostMLocIt->second.erase(LocVarIt.second);
897 VarLocs[NewLoc->asU64()] = OldValue;
902 ActiveMLocIt->second.clear();
914 if (VarLocs[Src.asU64()] != MTracker->readMLoc(Src))
918 //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?
933 std::replace(ActiveVLocIt->second.Ops.begin(),
934 ActiveVLocIt->second.Ops.end(), SrcOp, DstOp);
937 MachineInstr *MI = MTracker->emitLoc(ActiveVLocIt->second.Ops, Var, DILoc,
938 ActiveVLocIt->second.Properties);
953 DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0,
954 Var.getVariable()->getScope(),
956 auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE));
968 //===----------------------------------------------------------------------===//
970 //===----------------------------------------------------------------------===//
973 ValueIDNum ValueIDNum::TombstoneValue = {UINT_MAX, UINT_MAX, UINT_MAX - 1};
980 dbgs() << MTrack->LocIdxToName(Loc);
987 dbgs() << MTrack->IDAsString(ID);
994 OpStore->find(*this).dump(MTrack);
1042 // Build some common stack positions -- full registers being spilt to the
1060 // Some subregs have -1, -2 and so forth fed into their fields, to mean
1098 if (MaskPair.first->clobbersPhysReg(ID)) {
1114 // relied upon -- we represent this by giving it a new value.
1118 if (ID < NumRegs && !SPAliases.count(ID) && MO->clobbersPhysReg(ID))
1143 // Initialize to PHI value; corresponds to the location's live-in value
1155 ID -= NumRegs;
1176 dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n";
1209 auto GetRegOp = [](unsigned Reg) -> MachineOperand {
1255 // TODO: support variables that are located in spill slots, with non-zero
1259 // Accept no-subregister slots and subregisters where the offset is zero.
1284 unsigned VariableSizeInBits = Fragment->SizeInBits;
1285 if (VariableSizeInBits != ValueSizeInBits || Expr->isComplex())
1287 } else if (auto Size = Var.getVariable()->getSizeInBits()) {
1293 // https://github.com/llvm/llvm-project/issues/64093
1294 // in particular #issuecomment-2531264124. We use variable locations
1298 // DBG_VALUE as a 128-bit reference. We then issue a DW_OP_deref_size
1307 // smaller or larger value types than the source-variable type, which
1308 // manifests as too-little or too-much memory being read from the stack.
1310 // debug-info.
1322 assert(!Expr->isImplicit());
1324 } else if (UseDerefSize && Expr->isSingleLocationExpression()) {
1333 } else if (Expr->isComplex() || Properties.IsVariadic) {
1352 // Non-empty, non-stack slot, must be a plain register.
1364 unsigned Reg = MTracker->LocIdxToLocID[L];
1374 //===----------------------------------------------------------------------===//
1376 //===----------------------------------------------------------------------===//
1388 const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
1389 assert(PVal->kind() == PseudoSourceValue::FixedStack &&
1391 int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
1394 StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
1395 return MTracker->getOrTrackSpillLoc({Reg, Offset});
1404 // Where in the stack slot is this value defined -- i.e., what size of value
1409 LocationSize SizeInBits = MemOperand->getSizeInBits();
1413 auto IdxIt = MTracker->StackSlotIdxes.find({SizeInBits.getValue(), 0});
1414 if (IdxIt == MTracker->StackSlotIdxes.end())
1419 unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillLoc, IdxIt->second);
1420 return MTracker->getSpillMLoc(SpillID);
1429 assert(MI.getDebugVariable()->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
1430 "Expected inlined-at fields to agree");
1442 (void)MTracker->readReg(MO.getReg());
1456 DebugOps.push_back(DbgOpStore.insert(MTracker->readReg(MO.getReg())));
1464 VTracker->defVar(MI, DbgValueProperties(MI), DebugOps);
1470 TTracker->redefVar(MI);
1481 const MachineFunction &MF = *MI.getParent()->getParent();
1490 LowerBoundIt->Src == SoughtSub.Src) {
1491 std::tie(InstNo, OpNo) = LowerBoundIt->Dest;
1492 SoughtSub.Src = LowerBoundIt->Dest;
1493 if (unsigned Subreg = LowerBoundIt->Subreg)
1498 // Default machine value number is <None> -- if no instruction defines
1507 const MachineInstr &TargetInstr = *InstrIt->second.first;
1508 uint64_t BlockNo = TargetInstr.getParent()->getNumber();
1516 NewID = ValueIDNum(BlockNo, InstrIt->second.second, *L);
1518 // Permit the debug-info to be completely wrong: identifying a nonexistant
1520 // unexpected happened during optimisation. Broken debug-info, however,
1521 // shouldn't crash the compiler -- instead leave the variable value as
1527 unsigned LocID = MTracker->getLocID(MO.getReg());
1528 LocIdx L = MTracker->LocIDToLocIdx[LocID];
1529 NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
1539 } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {
1543 NewID = resolveDbgPHIs(*MI.getParent()->getParent(), *MLiveOuts, *MLiveIns,
1549 // CALL64 @foo, implicit-def $rax
1565 unsigned ThisSize = TRI->getSubRegIdxSize(Subreg);
1566 unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg);
1575 LocIdx L = NewID->getLoc();
1576 if (NewID && !MTracker->isSpill(L)) {
1579 Register Reg = MTracker->LocIdxToLocID[L];
1581 for (const auto *TRCI : TRI->regclasses())
1582 if (TRCI->contains(Reg))
1588 unsigned MainRegSize = TRI->getRegSizeInBits(*TRC);
1592 for (MCPhysReg SR : TRI->subregs(Reg)) {
1593 unsigned Subreg = TRI->getSubRegIndex(Reg, SR);
1594 unsigned SubregSize = TRI->getSubRegIdxSize(Subreg);
1595 unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg);
1606 // Re-state the value as being defined within the subregister
1608 LocIdx NewLoc = MTracker->lookupOrTrackRegister(NewReg);
1609 NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc);
1635 const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1636 assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
1637 "Expected inlined-at fields to agree");
1657 // Default machine value number is <None> -- if no instruction defines
1677 VTracker->defVar(MI, Properties, DbgOpIDs);
1684 // Fetch the concrete DbgOps now, as we will need them later.
1694 // Initialized the preferred-location map with illegal locations, to be
1703 for (auto Location : MTracker->locations()) {
1705 ValueIDNum ID = MTracker->readMLoc(CurL);
1709 auto &Previous = FoundLocs.find(ID)->second;
1713 TTracker->getLocQualityIfBetter(CurL, Previous.getQuality());
1730 LocIdx FoundLoc = FoundLocs.find(DbgOp.ID)->second.getLoc();
1738 TTracker->redefVar(MI, Properties, NewLocs);
1741 // later instructions in this block, this is a block-local use-before-def.
1760 TTracker->addUseBeforeDef(VID, {MI.getDebugExpression(), false, true},
1768 // (XXX -- could morph the DBG_INSTR_REF in the future).
1770 MTracker->emitLoc(NewLocs, V, MI.getDebugLoc().get(), Properties);
1773 TTracker->PendingDbgValues.push_back(std::make_pair(ID, DbgMI));
1774 TTracker->flushDbgValues(MI.getIterator(), nullptr);
1791 auto EmitBadPHI = [this, &MI, InstrNum]() -> bool {
1805 ValueIDNum Num = MTracker->readReg(Reg);
1807 {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)});
1812 MTracker->lookupOrTrackRegister(*RAI);
1819 if (MFI->isDeadObjectIndex(FI))
1824 StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base);
1826 std::optional<SpillLocationNo> SpillNo = MTracker->getOrTrackSpillLoc(SL);
1833 // Any stack location DBG_PHI should have an associate bit-size.
1837 unsigned SpillID = MTracker->getLocID(*SpillNo, {slotBitSize, 0});
1838 LocIdx SpillLoc = MTracker->getSpillMLoc(SpillID);
1839 ValueIDNum Result = MTracker->readMLoc(SpillLoc);
1846 // we're being fed illegal debug-info. Record an empty PHI, so that any
1865 ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg());
1866 // Has a legitimate value -> ignore the implicit def.
1885 auto IgnoreSPAlias = [this, &MI, CallChangesSP](Register R) -> bool {
1888 return MI.isCall() && MTracker->SPAliases.count(R);
1913 MTracker->defReg(DeadReg, CurBB, CurInst);
1916 MTracker->writeRegMask(MO, CurBB, CurInst);
1922 for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
1923 unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillNo, I);
1924 LocIdx L = MTracker->getSpillMLoc(SpillID);
1925 MTracker->setMLoc(L, ValueIDNum(CurBB, CurInst, L));
1939 LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg);
1940 TTracker->clobberMloc(Loc, MI.getIterator(), false);
1946 for (auto L : MTracker->locations()) {
1948 if (MTracker->isSpill(L.Idx))
1951 Register Reg = MTracker->LocIdxToLocID[L.Idx];
1956 if (MO->clobbersPhysReg(Reg))
1957 TTracker->clobberMloc(L.Idx, MI.getIterator(), false);
1965 for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
1966 unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillNo, I);
1967 LocIdx L = MTracker->getSpillMLoc(SpillID);
1968 TTracker->clobberMloc(L, MI.getIterator(), true);
1975 // In all circumstances, re-def all aliases. It's definitely a new value now.
1977 MTracker->defReg(*RAI, CurBB, CurInst);
1979 ValueIDNum SrcValue = MTracker->readReg(SrcRegNum);
1980 MTracker->setReg(DstRegNum, SrcValue);
1986 unsigned DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx);
1991 // have been def'd when the super-reg was, the latter might not be tracked
1995 LocIdx SrcL = MTracker->lookupOrTrackRegister(SrcSubReg);
1996 LocIdx DstL = MTracker->lookupOrTrackRegister(DstSubReg);
1999 ValueIDNum CpyValue = MTracker->readReg(SrcSubReg);
2001 MTracker->setReg(DstSubReg, CpyValue);
2012 // Reject any memory operand that's aliased -- we can't guarantee its value.
2014 const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
2015 if (PVal->isAliased(MFI))
2031 Reg = TII->isStoreToStackSlotPostFE(MI, FI);
2051 // XXX -- it's too difficult to implement VarLocBasedImpl's stack location
2059 int DummyFI = -1;
2060 if (!TII->isStoreToStackSlotPostFE(MI, DummyFI) &&
2061 !TII->isLoadFromStackSlotPostFE(MI, DummyFI))
2072 if (!TII->isStoreToStackSlotPostFE(MI, FIDummy) &&
2073 !TII->isLoadFromStackSlotPostFE(MI, FIDummy))
2080 // Un-set this location and clobber, so that earlier locations don't
2082 for (unsigned SlotIdx = 0; SlotIdx < MTracker->NumSlotIdxes; ++SlotIdx) {
2083 unsigned SpillID = MTracker->getSpillIDWithIdx(*Loc, SlotIdx);
2084 std::optional<LocIdx> MLoc = MTracker->getSpillMLoc(SpillID);
2088 // We need to over-write the stack slot with something (here, a def at
2091 // location and re-installing it in the same place.
2093 MTracker->setMLoc(*MLoc, Def);
2095 TTracker->clobberMloc(*MLoc, MI.getIterator());
2106 auto ReadValue = MTracker->readReg(SrcReg);
2107 LocIdx DstLoc = MTracker->getSpillMLoc(SpillID);
2108 MTracker->setMLoc(DstLoc, ReadValue);
2111 LocIdx SrcLoc = MTracker->getRegMLoc(SrcReg);
2112 TTracker->transferMlocs(SrcLoc, DstLoc, MI.getIterator());
2117 for (MCPhysReg SR : TRI->subregs(Reg)) {
2119 (void)MTracker->lookupOrTrackRegister(SR);
2120 unsigned SubregIdx = TRI->getSubRegIndex(Reg, SR);
2121 unsigned SpillID = MTracker->getLocID(Loc, SubregIdx);
2126 unsigned Size = TRI->getRegSizeInBits(Reg, *MRI);
2127 unsigned SpillID = MTracker->getLocID(Loc, {Size, 0});
2142 MTracker->defReg(*RAI, CurBB, CurInst);
2147 LocIdx SrcIdx = MTracker->getSpillMLoc(SpillID);
2148 auto ReadValue = MTracker->readMLoc(SrcIdx);
2149 MTracker->setReg(DestReg, ReadValue);
2152 for (MCPhysReg SR : TRI->subregs(Reg)) {
2153 unsigned Subreg = TRI->getSubRegIndex(Reg, SR);
2154 unsigned SpillID = MTracker->getLocID(*Loc, Subreg);
2159 unsigned Size = TRI->getRegSizeInBits(Reg, *MRI);
2160 unsigned SpillID = MTracker->getLocID(*Loc, {Size, 0});
2167 auto DestSrc = TII->isCopyLikeInstr(MI);
2171 const MachineOperand *DestRegOp = DestSrc->Destination;
2172 const MachineOperand *SrcRegOp = DestSrc->Source;
2174 Register SrcReg = SrcRegOp->getReg();
2175 Register DestReg = DestRegOp->getReg();
2194 if (EmulateOldLDV && !SrcRegOp->isKill())
2203 LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI);
2204 auto MLocIt = TTracker->ActiveMLocs.find(ClobberedLoc);
2207 if (MLocIt == TTracker->ActiveMLocs.end() || MLocIt->second.empty())
2209 ValueIDNum Value = MTracker->readReg(*RAI);
2222 TTracker->clobberMloc(LocVal.first, LocVal.second, MI.getIterator(), false);
2229 if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill())
2230 TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg),
2231 MTracker->getRegMLoc(DestReg), MI.getIterator());
2235 MTracker->defReg(SrcReg, CurBB, CurInst);
2242 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
2243 /// known-to-overlap fragments are present".
2249 MI.getDebugLoc()->getInlinedAt());
2257 SeenIt->second.insert(ThisFragment);
2270 auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
2271 auto &AllSeenFragments = SeenIt->second;
2287 ASeenFragmentsOverlaps->second.push_back(ThisFragment);
2328 unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs());
2330 BV.resize(TRI->getNumRegs(), true);
2340 // production only, this signifies the live-in value to the block.
2341 MTracker->reset();
2342 MTracker->setMPhis(CurBB);
2370 // any machine location has the live-in phi value from the start of the
2371 // block, it's live-through and doesn't need recording in the transfer
2373 for (auto Location : MTracker->locations()) {
2379 // Insert-or-update.
2383 Result.first->second = P;
2388 for (auto &P : MTracker->Masks) {
2389 BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords);
2394 BitVector UsedRegs(TRI->getNumRegs());
2395 for (auto Location : MTracker->locations()) {
2396 unsigned ID = MTracker->LocIdxToLocID[Location.Idx];
2398 if (ID >= TRI->getNumRegs() || MTracker->SPAliases.count(ID))
2403 // Check that any regmask-clobber of a register that gets tracked, is not
2404 // live-through in the transfer function. It needs to be clobbered at the
2414 unsigned ID = MTracker->getLocID(Bit);
2415 LocIdx Idx = MTracker->LocIDToLocIdx[ID];
2427 ValueIDNum &ValueID = Result.first->second;
2429 // It was left as live-through. Set it to clobbered.
2442 // Handle value-propagation when control flow merges on entry to a block. For
2451 return BBToOrder.find(A)->second < BBToOrder.find(B)->second;
2457 // FIXME: We don't use assert here to prevent instr-ref-unreachable.mir
2468 for (auto Location : MTracker->locations()) {
2471 // Pick out the first predecessors live-out value for this location. It's
2476 // propagate the first live-in value into this block.
2485 // We're now examining a PHI to see whether it's un-necessary. Loop around
2486 // the other live-in values and test whether they're all the same.
2500 // Live-out of a predecessor disagrees with the first predecessor.
2504 // No disagreement? No PHI. Otherwise, leave the PHI in live-ins.
2522 // * Most indexes with non-zero offset will end up being interference units
2526 // We can rely on a single-byte stack index existing already, because we
2528 auto It = MTracker->StackSlotIdxes.find({8, 0});
2529 assert(It != MTracker->StackSlotIdxes.end());
2530 Slots.push_back(It->second);
2532 // Find anything that has a non-zero offset and add that too.
2533 for (auto &Pair : MTracker->StackSlotIdxes) {
2557 for (auto Location : MTracker->locations()) {
2559 if (MTracker->isSpill(L)) {
2560 StackSlots.insert(MTracker->locIDToSpill(MTracker->LocIdxToLocID[L]));
2564 Register R = MTracker->LocIdxToLocID[L];
2567 for (MCRegUnit Unit : TRI->regunits(R.asMCReg())) {
2569 if (!MTracker->isRegisterTracked(*URoot)) {
2588 // Lambda to fetch PHIs for a given location, and write into the PHIBlocks
2596 const auto &TransferFunc = MLocTransfer[MBB->getNumber()];
2601 // The entry block defs the location too: it's the live-in / argument value.
2615 MInLocs[*MBB][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L);
2621 // Install those PHI values into the live-in value array.
2629 unsigned SpillID = MTracker->getSpillIDWithIdx(Slot, Idx);
2630 LocIdx L = MTracker->getSpillMLoc(SpillID);
2636 std::tie(Size, Offset) = MTracker->StackIdxesToPos[Idx];
2637 for (auto &Pair : MTracker->StackSlotIdxes) {
2643 unsigned ThisID = MTracker->getSpillIDWithIdx(Slot, Pair.second);
2644 LocIdx ThisL = MTracker->getSpillMLoc(ThisID);
2652 LocIdx L = MTracker->lookupOrTrackRegister(R);
2655 // Install those PHI values into the live-in value array.
2660 // Super-registers that are "above" the largest register read/written by
2662 if (!MTracker->isRegisterTracked(*RAI))
2665 LocIdx AliasLoc = MTracker->lookupOrTrackRegister(*RAI);
2693 for (auto Location : MTracker->locations())
2697 MTracker->reset();
2700 // any machine-location that isn't live-through a block to be def'd in that
2710 // code. Propagating values allows us to identify such un-necessary PHIs and
2719 CurBB = MBB->getNumber();
2732 // Load the current set of live-ins into MLocTracker.
2733 MTracker->loadFromArray(MInLocs[*MBB], CurBB);
2736 // a live-in value. Evaluate each element, and store to "ToRemap".
2741 ValueIDNum NewID = MTracker->readMLoc(P.second.getLoc());
2751 // transforms the contents of the MLocTracker into the live-outs.
2753 MTracker->setMLoc(P.first, P.second);
2755 // Now copy out-locs from mloc tracker into out-loc vector, checking
2759 for (auto Location : MTracker->locations()) {
2764 MTracker->reset();
2766 // No need to examine successors again if out-locs didn't change.
2770 // All successors should be visited: put any back-edges on the pending
2771 // list for the next pass-through, and any other successors to be
2773 for (auto *s : MBB->successors()) {
2774 // Does branching to this successor represent a back-edge?
2795 // Once all the live-ins don't change on mlocJoin(), we've eliminated all
2829 const DbgValue &FirstValue = *FirstValueIt->second;
2836 const DbgValue &OutVal = *OutValIt->second;
2838 // No-values cannot have locations we can join on.
2860 // We can never join constant ops - the ops must either both be equal
2861 // constant ops or non-const ops.
2874 // already-agreed value.
2898 // Collect a set of locations from predecessor where its live-out value can
2901 unsigned NumLocs = MTracker->getNumLocs();
2906 const DbgValue &OutVal = *OutValIt->second;
2914 // If the live-in value is a def, find the locations where that value is
2920 // Search the live-outs of the predecessor for the specified value.
2928 // a value that's live-through the whole loop. (It has to be a backedge,
2931 // locations feed back into themselves. Therefore, add all self-looping
2932 // machine-value PHI locations.
2961 // Return a PHI-value-number for the found location.
2985 // live-out values.
2997 // All Live-outs will have been initialized.
2998 DbgValue &OutLoc = *VLOCOutLocs.find(p)->second;
3000 // Keep track of where back-edges begin in the Values vector. Relies on
3010 // value, then give up immediately. It's not safe to produce a live-in
3015 // All (non-entry) blocks have at least one non-backedge predecessor.
3020 // If the old live-in value is not a PHI then either a) no PHI is needed
3032 // non-constants.
3034 if (!V.second->Properties.isJoinable(FirstVal.Properties))
3036 if (V.second->Kind == DbgValue::NoVal)
3038 if (!V.second->hasJoinableLocOps(FirstVal))
3048 // If both values are not equal but have equal non-empty IDs then they refer
3051 if (V.second->hasIdenticalValidLocOps(FirstVal))
3055 if (V.second->Kind == DbgValue::VPHI &&
3056 V.second->BlockNo == MBB.getNumber() &&
3064 // No disagreement -> live-through value.
3084 // Get the set of "normal" in-lexical-scope blocks.
3099 // Perform a depth-first-search to enumerate those blocks.
3101 // Depth-first-search state: each node is a block and which successor
3109 for (auto *succ : MBB->successors()) {
3115 DFS.push_back({succ, succ->succ_begin()});
3118 // Search all those blocks, depth first.
3123 if (CurSucc == CurBB->succ_end()) {
3132 DFS.push_back({*CurSucc, (*CurSucc)->succ_begin()});
3169 // that then produces output differences from original-live-debug-values,
3174 // Convert a const set to a non-const set. LexicalScopes
3182 // order-numbers and map back to MBB pointers later, to avoid repeated
3207 // Produce by-MBB indexes of live-in/live-outs, to ease lookup within
3219 // at time, but avoids re-processing variable values because some other
3222 // Re-initialize live-ins and live-outs, to clear the remains of previous
3223 // variables live-ins / live-outs.
3234 auto &TransferFunc = AllTheVLocs[ExpMBB->getNumber()].Vars;
3252 // Insert PHIs into the per-block live-in tables for this variable.
3254 unsigned BlockNo = PHIMBB->getNumber();
3266 // * Eliminates un-necessary VPHIs in vlocJoin,
3268 // stores the result to the blocks live-outs.
3270 // the live-ins change thereafter.
3275 CurBB = MBB->getNumber();
3280 DbgValue *LiveIn = LiveInsIt->second;
3287 SmallVector<const MachineBasicBlock *, 8> Preds(MBB->predecessors());
3289 // If this block's live-in value is a VPHI, try to pick a machine-value
3290 // for it. This makes the machine-value available and propagated
3292 // do this any earlier as it needs to read the block live-outs.
3293 if (LiveIn->Kind == DbgValue::VPHI && LiveIn->BlockNo == (int)CurBB) {
3295 // eliminated and transitions from VPHI-with-location to
3296 // live-through-value. As a result, the selected location of any VPHI
3297 // might change, so we need to re-compute it on each iteration.
3301 bool NewLocPicked = !equal(LiveIn->getDbgOpIDs(), JoinedOps);
3304 LiveIn->setDbgOpIDs(JoinedOps);
3315 auto &VTracker = AllTheVLocs[MBB->getNumber()];
3319 if (TransferIt->second.Kind == DbgValue::Undef) {
3320 DbgValue NewVal(MBB->getNumber(), EmptyProperties, DbgValue::NoVal);
3327 if (*LiveOut != TransferIt->second) {
3328 *LiveOut = TransferIt->second;
3333 // Just copy live-ins to live-outs, for anything not transferred.
3340 // If no live-out value changed, there's no need to explore further.
3344 // We should visit all successors. Ensure we'll visit any non-backedge
3347 for (auto *s : MBB->successors()) {
3348 // Ignore out of scope / not-to-be-explored successors.
3367 // Save live-ins to output vector. Ignore any that are still marked as being
3368 // VPHIs with no location -- those are variables that we know the value of,
3372 if (BlockLiveIn->Kind == DbgValue::NoVal)
3374 if (BlockLiveIn->isUnjoinedPHI())
3376 if (BlockLiveIn->Kind == DbgValue::VPHI)
3377 BlockLiveIn->Kind = DbgValue::Def;
3379 assert(BlockLiveIn->Properties.DIExpr->getFragmentInfo() ==
3382 Output[MBB->getNumber()].push_back(std::make_pair(VarID, *BlockLiveIn));
3384 } // Per-variable loop.
3402 // This is a common case, hence it's worth special-casing it.
3405 VLocTracker &VLocs = AllTheVLocs[AssignMBB->getNumber()];
3407 const DbgValue &Value = ValueIt->second;
3415 // Skip the definition block -- it's assigned the variable value in the middle
3418 if (!DomTree->properlyDominates(AssignMBB, ScopeBlock))
3421 Output[ScopeBlock->getNumber()].push_back({VarID, Value});
3424 // All blocks that aren't dominated have no live-in value, thus no variable
3432 std::string foo = MTracker->LocIdxToName(P.first);
3433 std::string bar = MTracker->IDAsString(P.second);
3434 dbgs() << "Loc " << foo << " --> " << bar << "\n";
3445 auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
3469 BBNumToRPO[MBB->getNumber()] = RPONumber;
3487 assert(It->Src != std::next(It)->Src && "Duplicate variable location "
3494 // Produce an "ejection map" for blocks, i.e., what's the highest-numbered
3507 WorkStack.push_back({TopScope, TopScope->getChildren().size() - 1});
3512 ssize_t ChildNum = ScopePosition.second--;
3514 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
3517 // Push the child and its children-count onto the stack.
3520 std::make_pair(ChildScope, ChildScope->getChildren().size() - 1));
3529 getBlocksForScope(DILocationIt->second, BlocksToExplore,
3530 ScopeToAssignBlocks.find(WS)->second);
3532 unsigned BBNum = MBB->getNumber();
3534 EjectionMap[BBNum] = WS->getDFSOut();
3551 unsigned NumLocs = MTracker->getNumLocs();
3564 // Helper lambda for ejecting a block -- if nothing is going to use the block,
3567 auto EjectBlock = [&](MachineBasicBlock &MBB) -> void {
3571 // Prime the transfer-tracker, and then step through all the block
3573 MTracker->reset();
3574 MTracker->loadFromArray(MInLocs[MBB], BBNum);
3575 TTracker->loadInlocs(MBB, MInLocs[MBB], DbgOpStore, Output[BBNum], NumLocs);
3581 TTracker->checkInstForNewValues(CurInst, MI.getIterator());
3585 // Free machine-location tables for this block.
3588 // We don't need live-in variable values for this block either.
3598 // Proceed to explore in depth first order.
3607 // have a DILocation -- by proxy, this means we never tracked any variable
3610 if (HighestDFSIn <= WS->getDFSIn() && DILocIt != ScopeToDILocation.end()) {
3611 const DILocation *DILoc = DILocIt->second;
3612 auto &VarsWeCareAbout = ScopeToVars.find(WS)->second;
3613 auto &BlocksInScope = ScopeToAssignBlocks.find(WS)->second;
3619 HighestDFSIn = std::max(HighestDFSIn, WS->getDFSIn());
3622 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
3624 // There are children to explore -- push onto stack and continue.
3636 getBlocksForScope(DILocationIt->second, BlocksToExplore,
3637 ScopeToAssignBlocks.find(WS)->second);
3639 if (WS->getDFSOut() == EjectionMap[MBB->getNumber()])
3649 // anything for such out-of-scope blocks, but for the sake of being similar
3659 // Go through all the transfers recorded in the TransferTracker -- this is
3660 // both the live-ins to a block, and any movements of values that happen
3662 for (auto &P : TTracker->Transfers) {
3677 if (P.Pos->isTerminator())
3680 MachineBasicBlock &MBB = *P.Pos->getParent();
3686 return TTracker->Transfers.size() != 0;
3701 this->TPC = TPC;
3703 this->DomTree = DomTree;
3708 TFI->getCalleeSaves(MF, CalleeSavedRegs);
3713 AdjustsStackInCalls = MFI->adjustsStack() &&
3714 STI.getFrameLowering()->stackProbeFunctionModifiesSP();
3716 StackProbeSymbolName = STI.getTargetLowering()->getStackProbeSymbolName(MF);
3727 int MaxNumBlocks = -1;
3741 // Allocate and initialize two array-of-arrays for the live-in and live-out
3744 unsigned NumLocs = MTracker->getNumLocs();
3749 // storing the computed live-ins / live-outs into the array-of-arrays. We use
3750 // both live-ins and live-outs for decision making in the variable value
3754 // Patch up debug phi numbers, turning unknown block-live-in values into
3755 // either live-through machine values, or PHIs.
3757 // Identify unresolved block-live-ins.
3768 // If there is no resolved value for this live-in then it is not directly
3769 // reachable from the entry block -- model it as a PHI on entry to this
3780 CurBB = MBB->getNumber();
3782 VTracker->MBB = MBB;
3783 MTracker->loadFromArray(MInLocs[*MBB], CurBB);
3789 MTracker->reset();
3807 auto *VTracker = &vlocs[MBB->getNumber()];
3809 for (auto &idx : VTracker->Vars) {
3811 const DILocation *ScopeLoc = VTracker->Scopes[VarID];
3815 // No insts in scope -> shouldn't have been recorded.
3819 ScopeToAssignBlocks[Scope].insert(VTracker->MBB);
3838 // a lexical-scope-depth search. It should be functionally identical to
3876 // expects to zero-initialize the type.
3955 /// Map of which blocks generate Undef values -- blocks that are not
3962 /// Table of live-in machine value numbers for blocks / locations.
3984 It->second = new LDVSSABlock(*BB, *this);
3985 return It->second;
3988 /// Find the live-in value number for the given block. Looks up the value at
3991 return MLiveIns[LDVBB->BB][Loc.asU64()].asU64();
4023 // Methods to access block successors -- dereferencing to our wrapper class.
4024 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
4025 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
4037 : PHI(P), Idx(PHI->IncomingValues.size()) {}
4046 BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; }
4048 LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; }
4057 /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
4061 for (MachineBasicBlock *Pred : BB->BB.predecessors())
4062 Preds->push_back(BB->Updater.getSSALDVBlock(Pred));
4065 /// GetPoisonVal - Normally creates an IMPLICIT_DEF instruction with a new
4069 // Create a value number for this block -- it needs to be unique and in the
4072 BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64();
4073 Updater->PoisonMap[&BB->BB] = Num;
4077 /// CreateEmptyPHI - Create a (representation of a) PHI in the given block.
4080 /// solution determined it to be. This includes non-phi values if SSAUpdater
4084 BlockValueNum PHIValNum = Updater->getValue(BB);
4085 LDVSSAPhi *PHI = BB->newPHI(PHIValNum);
4086 Updater->PHIs[PHIValNum] = PHI;
4090 /// AddPHIOperand - Add the specified value as an operand of the PHI for
4093 PHI->IncomingValues.push_back(std::make_pair(Pred, Val));
4096 /// ValueIsPHI - Check if the instruction that defines the specified value
4099 return Updater->PHIs.lookup(Val);
4102 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
4106 if (PHI && PHI->IncomingValues.size() == 0)
4111 /// GetPHIValue - For the specified PHI instruction, return the value
4113 static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; }
4125 return SeenDbgPHIIt->second;
4158 return *LowerIt->ValueRead;
4164 LocIdx Loc = *LowerIt->ReadLoc;
4169 // value, just like SSA. We use the bulk-standard LLVM SSA updater class to
4190 // Actually, we already know what the value is -- the Use is in the same
4192 return ValueIDNum::fromU64(AvailIt->second);
4201 // We have the number for a PHI, or possibly live-through value, to be used
4209 // predecessor values the same, leading to a non-PHI machine value number?
4221 // Sort PHIs to validate into RPO-order.
4227 return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];
4231 ValueIDNum ThisBlockValueNum = MLiveIns[PHI->ParentBlock->BB][Loc.asU64()];
4234 for (auto &PHIIt : PHI->IncomingValues) {
4236 if (Updater.PoisonMap.contains(&PHIIt.first->BB))
4240 const ValueTable &BlockLiveOuts = MLiveOuts[PHIIt.first->BB];
4246 // migrate into loops -- meaning we can only be live-through this
4250 // Does the block have as a live-out, in the location we're examining,
4252 ValueToCheck = VVal->second;
4260 ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum});