Lines Matching +full:num +full:- +full:transfer +full:- +full:bits
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
192 struct Transfer {
194 MachineBasicBlock *MBB; /// non-null if we should insert after.
201 /// qualifying meta-information needed to construct a concrete DBG_VALUE-like
222 SmallVector<Transfer, 32> Transfers;
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
265 /// collection prevents the use-before-def materializing.
283 unsigned Reg = MTracker->LocIdxToLocID[L];
284 if (Reg >= MTracker->NumRegs)
294 // slots generally live longer than callee-saved registers which generally
295 // live longer than non-callee-saved registers. The minimum value of 0
338 if (MTracker->isSpill(L))
349 /// For a variable \p Var with the live-in value \p Value, attempts to resolve
354 /// \p MBB is the basic block that we are loading the live-in value for.
355 /// \p DbgOpStore is the map containing the DbgOpID->DbgOp mapping needed to
389 const ValueIDNum &Num = Op.ID;
390 ValueLocPair Probe(Num, LocationAndQuality());
394 // There must be a legitimate entry found for Num.
396 ValuesPreferredLoc->first == Num);
398 if (ValuesPreferredLoc->second.isIllegal()) {
400 // use-before-def to be resolved as we step through the block.
403 if (Num.getBlock() == (unsigned)MBB.getNumber() && !Num.isPHI()) {
405 static_cast<unsigned>(Num.getInst()));
408 recoverAsEntryValue(VarID, Value.Properties, Num);
415 LocIdx M = ValuesPreferredLoc->second.getLoc();
431 // the transfer.
438 Result.first->second = NewValue;
441 std::make_pair(VarID, &*MTracker->emitLoc(ResolvedDbgOps, Var, DILoc,
445 /// Load object with live-in variable values. \p mlocs contains the live-in
446 /// values in each machine location, while \p vlocs the live-in variable
447 /// values. This method picks variable locations for the live-in variables,
466 // Initialized the preferred-location map with illegal locations, to be
482 for (auto Location : MTracker->locations()) {
493 if (VIt == ValueToLoc.end() || VIt->first != VNum)
496 auto &Previous = VIt->second;
522 /// processed, check whether it defines a variable value in a use-before-def.
536 for (auto &Use : MIt->second) {
555 for (auto Location : MTracker->locations()) {
564 auto &Previous = VIt->second;
575 for (auto &Use : MIt->second) {
586 LocIdx NewLoc = ValueToLoc.find(Op.ID)->second.getLoc();
601 Use.VarID, MTracker->emitLoc(DbgOps, Var, DILoc, Use.Properties)));
613 if (MBB && Pos == MBB->begin())
614 BundleStart = MBB->instr_begin();
616 BundleStart = getBundleStart(Pos->getIterator());
624 if (!Var.getVariable()->isParameter())
630 if (Expr->getNumElements() > 0 && !Expr->isDeref())
637 // Must be in entry block (block number zero), and be a PHI / live-in value.
642 if (MTracker->isSpill(Val.getLoc()))
645 Register SP = TLI->getStackPointerRegisterToSaveRestore();
647 Register Reg = MTracker->LocIdxToLocID[Val.getLoc()];
653 const ValueIDNum &Num) {
663 // If this debug value can be converted to be non-variadic, then do so;
679 if (!isEntryValueValue(Num))
685 Register Reg = MTracker->LocIdxToLocID[Num.getLoc()];
695 MI.getDebugLoc()->getInlinedAt());
699 // Ignore non-register locations, we don't transfer those.
705 for (LocIdx Loc : It->second.loc_indices())
709 // Any use-before-defs no longer apply.
719 LocIdx NewLoc = MTracker->getRegMLoc(Reg);
735 MI.getDebugLoc()->getInlinedAt());
737 // Any use-before-defs no longer apply.
743 for (LocIdx Loc : It->second.loc_indices())
761 // Check whether our local copy of values-by-location in #VarLocs is out
764 if (MTracker->readMLoc(NewLoc) != VarLocs[NewLoc.asU64()]) {
768 for (LocIdx Loc : LostVLocIt->second.loc_indices()) {
783 VarLocs[NewLoc.asU64()] = MTracker->readMLoc(NewLoc);
793 It->second.Ops.assign(NewLocs);
794 It->second.Properties = Properties;
826 for (auto Loc : MTracker->locations())
834 for (DebugVariableID VarID : ActiveMLocIt->second) {
835 auto &Prop = ActiveVLocs.find(VarID)->second.Properties;
845 // MLoc is dead, so end their existing MLoc->Var mappings as well.
847 for (DebugVariableID VarID : ActiveMLocIt->second) {
849 // Re-state the variable location: if there's no replacement then NewLoc
852 const DbgValueProperties &Properties = ActiveVLocIt->second.Properties;
854 // Produce the new list of debug ops - an empty list if no new location
855 // was found, or the existing list with the substitution MLoc -> NewLoc
862 DbgOps.insert(DbgOps.begin(), ActiveVLocIt->second.Ops.size(),
864 replace_copy(ActiveVLocIt->second.Ops, DbgOps.begin(), OldOp, NewOp);
869 VarID, &*MTracker->emitLoc(DbgOps, Var, DILoc, Properties)));
874 for (LocIdx Loc : ActiveVLocIt->second.loc_indices()) {
880 ActiveVLocIt->second.Ops = DbgOps;
892 LostMLocIt->second.erase(LocVarIt.second);
898 VarLocs[NewLoc->asU64()] = OldValue;
903 ActiveMLocIt->second.clear();
909 /// Transfer variables based on \p Src to be based on \p Dst. This handles
913 // Does Src still contain the value num we expect? If not, it's been
915 if (VarLocs[Src.asU64()] != MTracker->readMLoc(Src))
919 //^^^ Legitimate scenario on account of un-clobbered slot being assigned to?
934 std::replace(ActiveVLocIt->second.Ops.begin(),
935 ActiveVLocIt->second.Ops.end(), SrcOp, DstOp);
938 MachineInstr *MI = MTracker->emitLoc(ActiveVLocIt->second.Ops, Var, DILoc,
939 ActiveVLocIt->second.Properties);
954 DebugLoc DL = DILocation::get(Var.getVariable()->getContext(), 0, 0,
955 Var.getVariable()->getScope(),
957 auto MIB = BuildMI(MF, DL, TII->get(TargetOpcode::DBG_VALUE));
969 //===----------------------------------------------------------------------===//
971 //===----------------------------------------------------------------------===//
974 ValueIDNum ValueIDNum::TombstoneValue = {UINT_MAX, UINT_MAX, UINT_MAX - 1};
981 dbgs() << MTrack->LocIdxToName(Loc);
988 dbgs() << MTrack->IDAsString(ID);
995 OpStore->find(*this).dump(MTrack);
1043 // Build some common stack positions -- full registers being spilt to the
1061 // Some subregs have -1, -2 and so forth fed into their fields, to mean
1074 // stuff the machine tries to model. If it's more than 512 bits, then it
1099 if (MaskPair.first->clobbersPhysReg(ID)) {
1115 // relied upon -- we represent this by giving it a new value.
1119 if (ID < NumRegs && !SPAliases.count(ID) && MO->clobbersPhysReg(ID))
1144 // Initialize to PHI value; corresponds to the location's live-in value
1145 // during transfer function construction.
1156 ID -= NumRegs;
1167 std::string MLocTracker::IDAsString(const ValueIDNum &Num) const {
1168 std::string DefName = LocIdxToName(Num.getLoc());
1169 return Num.asString(DefName);
1177 dbgs() << LocIdxToName(Location.Idx) << " --> " << DefName << "\n";
1210 auto GetRegOp = [](unsigned Reg) -> MachineOperand {
1256 // TODO: support variables that are located in spill slots, with non-zero
1260 // Accept no-subregister slots and subregisters where the offset is zero.
1285 unsigned VariableSizeInBits = Fragment->SizeInBits;
1286 if (VariableSizeInBits != ValueSizeInBits || Expr->isComplex())
1288 } else if (auto Size = Var.getVariable()->getSizeInBits()) {
1302 assert(!Expr->isImplicit());
1304 } else if (UseDerefSize && Expr->isSingleLocationExpression()) {
1313 } else if (Expr->isComplex() || Properties.IsVariadic) {
1332 // Non-empty, non-stack slot, must be a plain register.
1344 unsigned Reg = MTracker->LocIdxToLocID[L];
1354 //===----------------------------------------------------------------------===//
1356 //===----------------------------------------------------------------------===//
1368 const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
1369 assert(PVal->kind() == PseudoSourceValue::FixedStack &&
1371 int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
1374 StackOffset Offset = TFI->getFrameIndexReference(*MBB->getParent(), FI, Reg);
1375 return MTracker->getOrTrackSpillLoc({Reg, Offset});
1384 // Where in the stack slot is this value defined -- i.e., what size of value
1389 LocationSize SizeInBits = MemOperand->getSizeInBits();
1393 auto IdxIt = MTracker->StackSlotIdxes.find({SizeInBits.getValue(), 0});
1394 if (IdxIt == MTracker->StackSlotIdxes.end())
1399 unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillLoc, IdxIt->second);
1400 return MTracker->getSpillMLoc(SpillID);
1409 assert(MI.getDebugVariable()->isValidLocationForIntrinsic(MI.getDebugLoc()) &&
1410 "Expected inlined-at fields to agree");
1422 (void)MTracker->readReg(MO.getReg());
1436 DebugOps.push_back(DbgOpStore.insert(MTracker->readReg(MO.getReg())));
1444 VTracker->defVar(MI, DbgValueProperties(MI), DebugOps);
1450 TTracker->redefVar(MI);
1461 const MachineFunction &MF = *MI.getParent()->getParent();
1470 LowerBoundIt->Src == SoughtSub.Src) {
1471 std::tie(InstNo, OpNo) = LowerBoundIt->Dest;
1472 SoughtSub.Src = LowerBoundIt->Dest;
1473 if (unsigned Subreg = LowerBoundIt->Subreg)
1478 // Default machine value number is <None> -- if no instruction defines
1487 const MachineInstr &TargetInstr = *InstrIt->second.first;
1488 uint64_t BlockNo = TargetInstr.getParent()->getNumber();
1496 NewID = ValueIDNum(BlockNo, InstrIt->second.second, *L);
1498 // Permit the debug-info to be completely wrong: identifying a nonexistant
1500 // unexpected happened during optimisation. Broken debug-info, however,
1501 // shouldn't crash the compiler -- instead leave the variable value as
1507 unsigned LocID = MTracker->getLocID(MO.getReg());
1508 LocIdx L = MTracker->LocIDToLocIdx[LocID];
1509 NewID = ValueIDNum(BlockNo, InstrIt->second.second, L);
1519 } else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {
1523 NewID = resolveDbgPHIs(*MI.getParent()->getParent(), *MLiveOuts, *MLiveIns,
1529 // CALL64 @foo, implicit-def $rax
1545 unsigned ThisSize = TRI->getSubRegIdxSize(Subreg);
1546 unsigned ThisOffset = TRI->getSubRegIdxOffset(Subreg);
1555 LocIdx L = NewID->getLoc();
1556 if (NewID && !MTracker->isSpill(L)) {
1559 Register Reg = MTracker->LocIdxToLocID[L];
1561 for (const auto *TRCI : TRI->regclasses())
1562 if (TRCI->contains(Reg))
1568 unsigned MainRegSize = TRI->getRegSizeInBits(*TRC);
1572 for (MCPhysReg SR : TRI->subregs(Reg)) {
1573 unsigned Subreg = TRI->getSubRegIndex(Reg, SR);
1574 unsigned SubregSize = TRI->getSubRegIdxSize(Subreg);
1575 unsigned SubregOffset = TRI->getSubRegIdxOffset(Subreg);
1586 // Re-state the value as being defined within the subregister
1588 LocIdx NewLoc = MTracker->lookupOrTrackRegister(NewReg);
1589 NewID = ValueIDNum(NewID->getBlock(), NewID->getInst(), NewLoc);
1608 // transfer function.
1615 const DILocation *InlinedAt = DebugLoc->getInlinedAt();
1616 assert(Var->isValidLocationForIntrinsic(DebugLoc) &&
1617 "Expected inlined-at fields to agree");
1637 // Default machine value number is <None> -- if no instruction defines
1657 VTracker->defVar(MI, Properties, DbgOpIDs);
1674 // Initialized the preferred-location map with illegal locations, to be
1683 for (auto Location : MTracker->locations()) {
1685 ValueIDNum ID = MTracker->readMLoc(CurL);
1689 auto &Previous = FoundLocs.find(ID)->second;
1693 TTracker->getLocQualityIfBetter(CurL, Previous.getQuality());
1710 LocIdx FoundLoc = FoundLocs.find(DbgOp.ID)->second.getLoc();
1717 // Tell transfer tracker that the variable value has changed.
1718 TTracker->redefVar(MI, Properties, NewLocs);
1721 // later instructions in this block, this is a block-local use-before-def.
1740 TTracker->addUseBeforeDef(VID, {MI.getDebugExpression(), false, true},
1748 // (XXX -- could morph the DBG_INSTR_REF in the future).
1750 MTracker->emitLoc(NewLocs, V, MI.getDebugLoc().get(), Properties);
1753 TTracker->PendingDbgValues.push_back(std::make_pair(ID, DbgMI));
1754 TTracker->flushDbgValues(MI.getIterator(), nullptr);
1771 auto EmitBadPHI = [this, &MI, InstrNum]() -> bool {
1785 ValueIDNum Num = MTracker->readReg(Reg);
1787 {InstrNum, MI.getParent(), Num, MTracker->lookupOrTrackRegister(Reg)});
1792 MTracker->lookupOrTrackRegister(*RAI);
1799 if (MFI->isDeadObjectIndex(FI))
1804 StackOffset Offs = TFI->getFrameIndexReference(*MI.getMF(), FI, Base);
1806 std::optional<SpillLocationNo> SpillNo = MTracker->getOrTrackSpillLoc(SL);
1813 // Any stack location DBG_PHI should have an associate bit-size.
1817 unsigned SpillID = MTracker->getLocID(*SpillNo, {slotBitSize, 0});
1818 LocIdx SpillLoc = MTracker->getSpillMLoc(SpillID);
1819 ValueIDNum Result = MTracker->readMLoc(SpillLoc);
1826 // we're being fed illegal debug-info. Record an empty PHI, so that any
1845 ValueIDNum Num = MTracker->readReg(MI.getOperand(0).getReg());
1846 // Has a legitimate value -> ignore the implicit def.
1847 if (Num.getLoc() != 0)
1865 auto IgnoreSPAlias = [this, &MI, CallChangesSP](Register R) -> bool {
1868 return MI.isCall() && MTracker->SPAliases.count(R);
1893 MTracker->defReg(DeadReg, CurBB, CurInst);
1896 MTracker->writeRegMask(MO, CurBB, CurInst);
1902 for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
1903 unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillNo, I);
1904 LocIdx L = MTracker->getSpillMLoc(SpillID);
1905 MTracker->setMLoc(L, ValueIDNum(CurBB, CurInst, L));
1913 // When committing variable values to locations: tell transfer tracker that
1919 LocIdx Loc = MTracker->lookupOrTrackRegister(DeadReg);
1920 TTracker->clobberMloc(Loc, MI.getIterator(), false);
1926 for (auto L : MTracker->locations()) {
1928 if (MTracker->isSpill(L.Idx))
1931 Register Reg = MTracker->LocIdxToLocID[L.Idx];
1936 if (MO->clobbersPhysReg(Reg))
1937 TTracker->clobberMloc(L.Idx, MI.getIterator(), false);
1945 for (unsigned int I = 0; I < MTracker->NumSlotIdxes; ++I) {
1946 unsigned SpillID = MTracker->getSpillIDWithIdx(*SpillNo, I);
1947 LocIdx L = MTracker->getSpillMLoc(SpillID);
1948 TTracker->clobberMloc(L, MI.getIterator(), true);
1955 // In all circumstances, re-def all aliases. It's definitely a new value now.
1957 MTracker->defReg(*RAI, CurBB, CurInst);
1959 ValueIDNum SrcValue = MTracker->readReg(SrcRegNum);
1960 MTracker->setReg(DstRegNum, SrcValue);
1966 unsigned DstSubReg = TRI->getSubReg(DstRegNum, SubRegIdx);
1971 // have been def'd when the super-reg was, the latter might not be tracked
1975 LocIdx SrcL = MTracker->lookupOrTrackRegister(SrcSubReg);
1976 LocIdx DstL = MTracker->lookupOrTrackRegister(DstSubReg);
1979 ValueIDNum CpyValue = MTracker->readReg(SrcSubReg);
1981 MTracker->setReg(DstSubReg, CpyValue);
1992 // Reject any memory operand that's aliased -- we can't guarantee its value.
1994 const PseudoSourceValue *PVal = (*MMOI)->getPseudoValue();
1995 if (PVal->isAliased(MFI))
2011 Reg = TII->isStoreToStackSlotPostFE(MI, FI);
2031 // XXX -- it's too difficult to implement VarLocBasedImpl's stack location
2039 int DummyFI = -1;
2040 if (!TII->isStoreToStackSlotPostFE(MI, DummyFI) &&
2041 !TII->isLoadFromStackSlotPostFE(MI, DummyFI))
2052 if (!TII->isStoreToStackSlotPostFE(MI, FIDummy) &&
2053 !TII->isLoadFromStackSlotPostFE(MI, FIDummy))
2060 // Un-set this location and clobber, so that earlier locations don't
2062 for (unsigned SlotIdx = 0; SlotIdx < MTracker->NumSlotIdxes; ++SlotIdx) {
2063 unsigned SpillID = MTracker->getSpillIDWithIdx(*Loc, SlotIdx);
2064 std::optional<LocIdx> MLoc = MTracker->getSpillMLoc(SpillID);
2068 // We need to over-write the stack slot with something (here, a def at
2071 // location and re-installing it in the same place.
2073 MTracker->setMLoc(*MLoc, Def);
2075 TTracker->clobberMloc(*MLoc, MI.getIterator());
2079 // Try to recognise spill and restore instructions that may transfer a value.
2086 auto ReadValue = MTracker->readReg(SrcReg);
2087 LocIdx DstLoc = MTracker->getSpillMLoc(SpillID);
2088 MTracker->setMLoc(DstLoc, ReadValue);
2091 LocIdx SrcLoc = MTracker->getRegMLoc(SrcReg);
2092 TTracker->transferMlocs(SrcLoc, DstLoc, MI.getIterator());
2096 // Then, transfer subreg bits.
2097 for (MCPhysReg SR : TRI->subregs(Reg)) {
2099 (void)MTracker->lookupOrTrackRegister(SR);
2100 unsigned SubregIdx = TRI->getSubRegIndex(Reg, SR);
2101 unsigned SpillID = MTracker->getLocID(Loc, SubregIdx);
2105 // Directly lookup size of main source reg, and transfer.
2106 unsigned Size = TRI->getRegSizeInBits(Reg, *MRI);
2107 unsigned SpillID = MTracker->getLocID(Loc, {Size, 0});
2122 MTracker->defReg(*RAI, CurBB, CurInst);
2127 LocIdx SrcIdx = MTracker->getSpillMLoc(SpillID);
2128 auto ReadValue = MTracker->readMLoc(SrcIdx);
2129 MTracker->setReg(DestReg, ReadValue);
2132 for (MCPhysReg SR : TRI->subregs(Reg)) {
2133 unsigned Subreg = TRI->getSubRegIndex(Reg, SR);
2134 unsigned SpillID = MTracker->getLocID(*Loc, Subreg);
2138 // Directly look up this registers slot idx by size, and transfer.
2139 unsigned Size = TRI->getRegSizeInBits(Reg, *MRI);
2140 unsigned SpillID = MTracker->getLocID(*Loc, {Size, 0});
2147 auto DestSrc = TII->isCopyLikeInstr(MI);
2151 const MachineOperand *DestRegOp = DestSrc->Destination;
2152 const MachineOperand *SrcRegOp = DestSrc->Source;
2154 Register SrcReg = SrcRegOp->getReg();
2155 Register DestReg = DestRegOp->getReg();
2174 if (EmulateOldLDV && !SrcRegOp->isKill())
2183 LocIdx ClobberedLoc = MTracker->getRegMLoc(*RAI);
2184 auto MLocIt = TTracker->ActiveMLocs.find(ClobberedLoc);
2187 if (MLocIt == TTracker->ActiveMLocs.end() || MLocIt->second.empty())
2189 ValueIDNum Value = MTracker->readReg(*RAI);
2202 TTracker->clobberMloc(LocVal.first, LocVal.second, MI.getIterator(), false);
2206 // Only produce a transfer of DBG_VALUE within a block where old LDV
2209 if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->isKill())
2210 TTracker->transferMlocs(MTracker->getRegMLoc(SrcReg),
2211 MTracker->getRegMLoc(DestReg), MI.getIterator());
2215 MTracker->defReg(SrcReg, CurBB, CurInst);
2222 /// the data-flow stage from "Find any overlapping fragments" to "Check if the
2223 /// known-to-overlap fragments are present".
2229 MI.getDebugLoc()->getInlinedAt());
2252 auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
2253 auto &AllSeenFragments = SeenIt->second;
2269 ASeenFragmentsOverlaps->second.push_back(ThisFragment);
2279 // Try to interpret an MI as a debug or transfer instruction. Only if it's
2301 // to clobber that register in the transfer function. But this information
2310 unsigned BVWords = MachineOperand::getRegMaskSize(TRI->getNumRegs());
2312 BV.resize(TRI->getNumRegs(), true);
2314 // Step through all instructions and inhale the transfer function.
2321 // Set all machine locations to a PHI value. For transfer function
2322 // production only, this signifies the live-in value to the block.
2323 MTracker->reset();
2324 MTracker->setMPhis(CurBB);
2329 // machine transfer function.
2351 // Produce the transfer function, a map of machine location to new value. If
2352 // any machine location has the live-in phi value from the start of the
2353 // block, it's live-through and doesn't need recording in the transfer
2355 for (auto Location : MTracker->locations()) {
2361 // Insert-or-update.
2365 Result.first->second = P;
2370 for (auto &P : MTracker->Masks) {
2371 BlockMasks[CurBB].clearBitsNotInMask(P.first->getRegMask(), BVWords);
2376 BitVector UsedRegs(TRI->getNumRegs());
2377 for (auto Location : MTracker->locations()) {
2378 unsigned ID = MTracker->LocIdxToLocID[Location.Idx];
2380 if (ID >= TRI->getNumRegs() || MTracker->SPAliases.count(ID))
2385 // Check that any regmask-clobber of a register that gets tracked, is not
2386 // live-through in the transfer function. It needs to be clobbered at the
2392 // This produces all the bits that we clobber, but also use. Check that
2393 // they're all clobbered or at least set in the designated transfer
2396 unsigned ID = MTracker->getLocID(Bit);
2397 LocIdx Idx = MTracker->LocIDToLocIdx[ID];
2409 ValueIDNum &ValueID = Result.first->second;
2411 // It was left as live-through. Set it to clobbered.
2424 // Handle value-propagation when control flow merges on entry to a block. For
2435 return BBToOrder.find(A)->second < BBToOrder.find(B)->second;
2441 // FIXME: We don't use assert here to prevent instr-ref-unreachable.mir
2452 for (auto Location : MTracker->locations()) {
2455 // Pick out the first predecessors live-out value for this location. It's
2460 // propagate the first live-in value into this block.
2469 // We're now examining a PHI to see whether it's un-necessary. Loop around
2470 // the other live-in values and test whether they're all the same.
2484 // Live-out of a predecessor disagrees with the first predecessor.
2488 // No disagreement? No PHI. Otherwise, leave the PHI in live-ins.
2506 // * Most indexes with non-zero offset will end up being interference units
2510 // We can rely on a single-byte stack index existing already, because we
2512 auto It = MTracker->StackSlotIdxes.find({8, 0});
2513 assert(It != MTracker->StackSlotIdxes.end());
2514 Slots.push_back(It->second);
2516 // Find anything that has a non-zero offset and add that too.
2517 for (auto &Pair : MTracker->StackSlotIdxes) {
2541 for (auto Location : MTracker->locations()) {
2543 if (MTracker->isSpill(L)) {
2544 StackSlots.insert(MTracker->locIDToSpill(MTracker->LocIdxToLocID[L]));
2548 Register R = MTracker->LocIdxToLocID[L];
2551 for (MCRegUnit Unit : TRI->regunits(R.asMCReg())) {
2553 if (!MTracker->isRegisterTracked(*URoot)) {
2580 const auto &TransferFunc = MLocTransfer[MBB->getNumber()];
2585 // The entry block defs the location too: it's the live-in / argument value.
2599 MInLocs[*MBB][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L);
2605 // Install those PHI values into the live-in value array.
2613 unsigned SpillID = MTracker->getSpillIDWithIdx(Slot, Idx);
2614 LocIdx L = MTracker->getSpillMLoc(SpillID);
2620 std::tie(Size, Offset) = MTracker->StackIdxesToPos[Idx];
2621 for (auto &Pair : MTracker->StackSlotIdxes) {
2627 unsigned ThisID = MTracker->getSpillIDWithIdx(Slot, Pair.second);
2628 LocIdx ThisL = MTracker->getSpillMLoc(ThisID);
2636 LocIdx L = MTracker->lookupOrTrackRegister(R);
2639 // Install those PHI values into the live-in value array.
2644 // Super-registers that are "above" the largest register read/written by
2646 if (!MTracker->isRegisterTracked(*RAI))
2649 LocIdx AliasLoc = MTracker->lookupOrTrackRegister(*RAI);
2677 for (auto Location : MTracker->locations())
2681 MTracker->reset();
2684 // any machine-location that isn't live-through a block to be def'd in that
2694 // code. Propagating values allows us to identify such un-necessary PHIs and
2698 // Vector for storing the evaluated block transfer function.
2703 CurBB = MBB->getNumber();
2711 // Don't examine transfer function if we've visited this loc at least
2716 // Load the current set of live-ins into MLocTracker.
2717 MTracker->loadFromArray(MInLocs[*MBB], CurBB);
2719 // Each element of the transfer function can be a new def, or a read of
2720 // a live-in value. Evaluate each element, and store to "ToRemap".
2725 ValueIDNum NewID = MTracker->readMLoc(P.second.getLoc());
2734 // Commit the transfer function changes into mloc tracker, which
2735 // transforms the contents of the MLocTracker into the live-outs.
2737 MTracker->setMLoc(P.first, P.second);
2739 // Now copy out-locs from mloc tracker into out-loc vector, checking
2741 // the transfer function, and mlocJoin.
2743 for (auto Location : MTracker->locations()) {
2748 MTracker->reset();
2750 // No need to examine successors again if out-locs didn't change.
2754 // All successors should be visited: put any back-edges on the pending
2755 // list for the next pass-through, and any other successors to be
2757 for (auto *s : MBB->successors()) {
2758 // Does branching to this successor represent a back-edge?
2779 // Once all the live-ins don't change on mlocJoin(), we've eliminated all
2790 IDFCalculatorBase<MachineBasicBlock, false> IDF(DomTree->getBase());
2813 const DbgValue &FirstValue = *FirstValueIt->second;
2820 const DbgValue &OutVal = *OutValIt->second;
2822 // No-values cannot have locations we can join on.
2844 // We can never join constant ops - the ops must either both be equal
2845 // constant ops or non-const ops.
2858 // already-agreed value.
2882 // Collect a set of locations from predecessor where its live-out value can
2885 unsigned NumLocs = MTracker->getNumLocs();
2890 const DbgValue &OutVal = *OutValIt->second;
2898 // If the live-in value is a def, find the locations where that value is
2904 // Search the live-outs of the predecessor for the specified value.
2912 // a value that's live-through the whole loop. (It has to be a backedge,
2915 // locations feed back into themselves. Therefore, add all self-looping
2916 // machine-value PHI locations.
2945 // Return a PHI-value-number for the found location.
2969 // live-out values.
2981 // All Live-outs will have been initialized.
2982 DbgValue &OutLoc = *VLOCOutLocs.find(p)->second;
2984 // Keep track of where back-edges begin in the Values vector. Relies on
2994 // value, then give up immediately. It's not safe to produce a live-in
2999 // All (non-entry) blocks have at least one non-backedge predecessor.
3004 // If the old live-in value is not a PHI then either a) no PHI is needed
3016 // non-constants.
3018 if (!V.second->Properties.isJoinable(FirstVal.Properties))
3020 if (V.second->Kind == DbgValue::NoVal)
3022 if (!V.second->hasJoinableLocOps(FirstVal))
3032 // If both values are not equal but have equal non-empty IDs then they refer
3035 if (V.second->hasIdenticalValidLocOps(FirstVal))
3039 if (V.second->Kind == DbgValue::VPHI &&
3040 V.second->BlockNo == MBB.getNumber() &&
3048 // No disagreement -> live-through value.
3068 // Get the set of "normal" in-lexical-scope blocks.
3083 // Perform a depth-first-search to enumerate those blocks.
3085 // Depth-first-search state: each node is a block and which successor
3093 for (auto *succ : MBB->successors()) {
3099 DFS.push_back({succ, succ->succ_begin()});
3107 if (CurSucc == CurBB->succ_end()) {
3116 DFS.push_back({*CurSucc, (*CurSucc)->succ_begin()});
3153 // that then produces output differences from original-live-debug-values,
3158 // Convert a const set to a non-const set. LexicalScopes
3166 // order-numbers and map back to MBB pointers later, to avoid repeated
3191 // Produce by-MBB indexes of live-in/live-outs, to ease lookup within
3203 // at time, but avoids re-processing variable values because some other
3206 // Re-initialize live-ins and live-outs, to clear the remains of previous
3207 // variables live-ins / live-outs.
3218 auto &TransferFunc = AllTheVLocs[ExpMBB->getNumber()].Vars;
3236 // Insert PHIs into the per-block live-in tables for this variable.
3238 unsigned BlockNo = PHIMBB->getNumber();
3250 // * Eliminates un-necessary VPHIs in vlocJoin,
3251 // * Evaluates the blocks transfer function (i.e. variable assignments) and
3252 // stores the result to the blocks live-outs.
3253 // Always evaluate the transfer function on the first iteration, and when
3254 // the live-ins change thereafter.
3259 CurBB = MBB->getNumber();
3264 DbgValue *LiveIn = LiveInsIt->second;
3272 for (const auto *Pred : MBB->predecessors())
3275 // If this block's live-in value is a VPHI, try to pick a machine-value
3276 // for it. This makes the machine-value available and propagated
3278 // do this any earlier as it needs to read the block live-outs.
3279 if (LiveIn->Kind == DbgValue::VPHI && LiveIn->BlockNo == (int)CurBB) {
3281 // eliminated and transitions from VPHI-with-location to
3282 // live-through-value. As a result, the selected location of any VPHI
3283 // might change, so we need to re-compute it on each iteration.
3287 bool NewLocPicked = !equal(LiveIn->getDbgOpIDs(), JoinedOps);
3290 LiveIn->setDbgOpIDs(JoinedOps);
3300 // Do transfer function.
3301 auto &VTracker = AllTheVLocs[MBB->getNumber()];
3304 // Erase on empty transfer (DBG_VALUE $noreg).
3305 if (TransferIt->second.Kind == DbgValue::Undef) {
3306 DbgValue NewVal(MBB->getNumber(), EmptyProperties, DbgValue::NoVal);
3313 if (*LiveOut != TransferIt->second) {
3314 *LiveOut = TransferIt->second;
3319 // Just copy live-ins to live-outs, for anything not transferred.
3326 // If no live-out value changed, there's no need to explore further.
3330 // We should visit all successors. Ensure we'll visit any non-backedge
3333 for (auto *s : MBB->successors()) {
3334 // Ignore out of scope / not-to-be-explored successors.
3353 // Save live-ins to output vector. Ignore any that are still marked as being
3354 // VPHIs with no location -- those are variables that we know the value of,
3358 if (BlockLiveIn->Kind == DbgValue::NoVal)
3360 if (BlockLiveIn->isUnjoinedPHI())
3362 if (BlockLiveIn->Kind == DbgValue::VPHI)
3363 BlockLiveIn->Kind = DbgValue::Def;
3365 assert(BlockLiveIn->Properties.DIExpr->getFragmentInfo() ==
3368 Output[MBB->getNumber()].push_back(std::make_pair(VarID, *BlockLiveIn));
3370 } // Per-variable loop.
3388 // This is a common case, hence it's worth special-casing it.
3390 // Pick out the variables value from the block transfer function.
3391 VLocTracker &VLocs = AllTheVLocs[AssignMBB->getNumber()];
3393 const DbgValue &Value = ValueIt->second;
3401 // Skip the definition block -- it's assigned the variable value in the middle
3404 if (!DomTree->properlyDominates(AssignMBB, ScopeBlock))
3407 Output[ScopeBlock->getNumber()].push_back({VarID, Value});
3410 // All blocks that aren't dominated have no live-in value, thus no variable
3418 std::string foo = MTracker->LocIdxToName(P.first);
3419 std::string bar = MTracker->IDAsString(P.second);
3420 dbgs() << "Loc " << foo << " --> " << bar << "\n";
3431 auto hasNonArtificialLocation = [](const MachineInstr &MI) -> bool {
3455 BBNumToRPO[MBB->getNumber()] = RPONumber;
3473 assert(It->Src != std::next(It)->Src && "Duplicate variable location "
3480 // Produce an "ejection map" for blocks, i.e., what's the highest-numbered
3493 WorkStack.push_back({TopScope, TopScope->getChildren().size() - 1});
3498 ssize_t ChildNum = ScopePosition.second--;
3500 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
3503 // Push the child and its children-count onto the stack.
3506 std::make_pair(ChildScope, ChildScope->getChildren().size() - 1));
3515 getBlocksForScope(DILocationIt->second, BlocksToExplore,
3516 ScopeToAssignBlocks.find(WS)->second);
3518 unsigned BBNum = MBB->getNumber();
3520 EjectionMap[BBNum] = WS->getDFSOut();
3537 unsigned NumLocs = MTracker->getNumLocs();
3550 // Helper lambda for ejecting a block -- if nothing is going to use the block,
3553 auto EjectBlock = [&](MachineBasicBlock &MBB) -> void {
3557 // Prime the transfer-tracker, and then step through all the block
3559 MTracker->reset();
3560 MTracker->loadFromArray(MInLocs[MBB], BBNum);
3561 TTracker->loadInlocs(MBB, MInLocs[MBB], DbgOpStore, Output[BBNum], NumLocs);
3567 TTracker->checkInstForNewValues(CurInst, MI.getIterator());
3571 // Free machine-location tables for this block.
3574 // We don't need live-in variable values for this block either.
3593 // have a DILocation -- by proxy, this means we never tracked any variable
3596 if (HighestDFSIn <= WS->getDFSIn() && DILocIt != ScopeToDILocation.end()) {
3597 const DILocation *DILoc = DILocIt->second;
3598 auto &VarsWeCareAbout = ScopeToVars.find(WS)->second;
3599 auto &BlocksInScope = ScopeToAssignBlocks.find(WS)->second;
3605 HighestDFSIn = std::max(HighestDFSIn, WS->getDFSIn());
3608 const SmallVectorImpl<LexicalScope *> &Children = WS->getChildren();
3610 // There are children to explore -- push onto stack and continue.
3622 getBlocksForScope(DILocationIt->second, BlocksToExplore,
3623 ScopeToAssignBlocks.find(WS)->second);
3625 if (WS->getDFSOut() == EjectionMap[MBB->getNumber()])
3635 // anything for such out-of-scope blocks, but for the sake of being similar
3645 // Go through all the transfers recorded in the TransferTracker -- this is
3646 // both the live-ins to a block, and any movements of values that happen
3648 for (auto &P : TTracker->Transfers) {
3663 if (P.Pos->isTerminator())
3666 MachineBasicBlock &MBB = *P.Pos->getParent();
3672 return TTracker->Transfers.size() != 0;
3687 this->TPC = TPC;
3689 this->DomTree = DomTree;
3694 TFI->getCalleeSaves(MF, CalleeSavedRegs);
3699 AdjustsStackInCalls = MFI->adjustsStack() &&
3700 STI.getFrameLowering()->stackProbeFunctionModifiesSP();
3702 StackProbeSymbolName = STI.getTargetLowering()->getStackProbeSymbolName(MF);
3713 int MaxNumBlocks = -1;
3727 // Allocate and initialize two array-of-arrays for the live-in and live-out
3730 unsigned NumLocs = MTracker->getNumLocs();
3735 // storing the computed live-ins / live-outs into the array-of-arrays. We use
3736 // both live-ins and live-outs for decision making in the variable value
3740 // Patch up debug phi numbers, turning unknown block-live-in values into
3741 // either live-through machine values, or PHIs.
3743 // Identify unresolved block-live-ins.
3747 ValueIDNum &Num = *DBG_PHI.ValueRead;
3748 if (!Num.isPHI())
3751 unsigned BlockNo = Num.getBlock();
3752 LocIdx LocNo = Num.getLoc();
3754 // If there is no resolved value for this live-in then it is not directly
3755 // reachable from the entry block -- model it as a PHI on entry to this
3758 Num = ResolvedValue;
3766 CurBB = MBB->getNumber();
3768 VTracker->MBB = MBB;
3769 MTracker->loadFromArray(MInLocs[*MBB], CurBB);
3775 MTracker->reset();
3793 auto *VTracker = &vlocs[MBB->getNumber()];
3795 for (auto &idx : VTracker->Vars) {
3797 const DILocation *ScopeLoc = VTracker->Scopes[VarID];
3801 // No insts in scope -> shouldn't have been recorded.
3805 ScopeToAssignBlocks[Scope].insert(VTracker->MBB);
3824 // a lexical-scope-depth search. It should be functionally identical to
3862 // expects to zero-initialize the type.
3941 /// Map of which blocks generate Undef values -- blocks that are not
3948 /// Table of live-in machine value numbers for blocks / locations.
3973 return it->second;
3976 /// Find the live-in value number for the given block. Looks up the value at
3979 return MLiveIns[LDVBB->BB][Loc.asU64()].asU64();
4011 // Methods to access block successors -- dereferencing to our wrapper class.
4012 static BlkSucc_iterator BlkSucc_begin(BlkT *BB) { return BB->succ_begin(); }
4013 static BlkSucc_iterator BlkSucc_end(BlkT *BB) { return BB->succ_end(); }
4025 : PHI(P), Idx(PHI->IncomingValues.size()) {}
4034 BlockValueNum getIncomingValue() { return PHI->IncomingValues[Idx].second; }
4036 LDVSSABlock *getIncomingBlock() { return PHI->IncomingValues[Idx].first; }
4045 /// FindPredecessorBlocks - Put the predecessors of BB into the Preds
4049 for (MachineBasicBlock *Pred : BB->BB.predecessors())
4050 Preds->push_back(BB->Updater.getSSALDVBlock(Pred));
4053 /// GetPoisonVal - Normally creates an IMPLICIT_DEF instruction with a new
4057 // Create a value number for this block -- it needs to be unique and in the
4060 BlockValueNum Num = ValueIDNum(BB->BB.getNumber(), 0, Updater->Loc).asU64();
4061 Updater->PoisonMap[&BB->BB] = Num;
4062 return Num;
4065 /// CreateEmptyPHI - Create a (representation of a) PHI in the given block.
4068 /// solution determined it to be. This includes non-phi values if SSAUpdater
4072 BlockValueNum PHIValNum = Updater->getValue(BB);
4073 LDVSSAPhi *PHI = BB->newPHI(PHIValNum);
4074 Updater->PHIs[PHIValNum] = PHI;
4078 /// AddPHIOperand - Add the specified value as an operand of the PHI for
4081 PHI->IncomingValues.push_back(std::make_pair(Pred, Val));
4084 /// ValueIsPHI - Check if the instruction that defines the specified value
4087 return Updater->PHIs.lookup(Val);
4090 /// ValueIsNewPHI - Like ValueIsPHI but also check if the PHI has no source
4094 if (PHI && PHI->IncomingValues.size() == 0)
4099 /// GetPHIValue - For the specified PHI instruction, return the value
4101 static BlockValueNum GetPHIValue(LDVSSAPhi *PHI) { return PHI->PHIValNum; }
4113 return SeenDbgPHIIt->second;
4146 return *LowerIt->ValueRead;
4152 LocIdx Loc = *LowerIt->ReadLoc;
4157 // value, just like SSA. We use the bulk-standard LLVM SSA updater class to
4171 const ValueIDNum &Num = *DBG_PHI.ValueRead;
4172 AvailableValues.insert(std::make_pair(Block, Num.asU64()));
4178 // Actually, we already know what the value is -- the Use is in the same
4180 return ValueIDNum::fromU64(AvailIt->second);
4189 // We have the number for a PHI, or possibly live-through value, to be used
4197 // predecessor values the same, leading to a non-PHI machine value number?
4205 const ValueIDNum &Num = *DBG_PHI.ValueRead;
4206 ValidatedValues.insert(std::make_pair(Block, Num));
4209 // Sort PHIs to validate into RPO-order.
4215 return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];
4219 ValueIDNum ThisBlockValueNum = MLiveIns[PHI->ParentBlock->BB][Loc.asU64()];
4222 for (auto &PHIIt : PHI->IncomingValues) {
4224 if (Updater.PoisonMap.contains(&PHIIt.first->BB))
4228 const ValueTable &BlockLiveOuts = MLiveOuts[PHIIt.first->BB];
4234 // migrate into loops -- meaning we can only be live-through this
4238 // Does the block have as a live-out, in the location we're examining,
4240 ValueToCheck = VVal->second;
4248 ValidatedValues.insert({PHI->ParentBlock, ThisBlockValueNum});