105 #include "llvm/Config/llvm-config.h"
122 #include <functional>
131 using namespace llvm;
136 #define DEBUG_TYPE "livedebugvalues"
141 cl::desc(
"Act like old LiveDebugValues did"),
155 cl::desc(
"livedebugvalues-stack-ws-limit"),
249 CalleeSavedRegs(CalleeSavedRegs) {
252 ShouldEmitDebugEntryValues =
TM.Options.ShouldEmitDebugEntryValues();
269 UseBeforeDefs.
clear();
270 UseBeforeDefVariables.
clear();
272 auto isCalleeSaved = [&](
LocIdx L) {
277 if (CalleeSavedRegs.
test(*RAI))
287 for (
auto &VLoc : VLocs)
291 ActiveMLocs.
reserve(VLocs.size());
292 ActiveVLocs.
reserve(VLocs.size());
297 for (
auto Location : MTracker->
locations()) {
298 LocIdx Idx = Location.Idx;
300 VarLocs.push_back(VNum);
303 auto VIt = ValueToLoc.
find(VNum);
304 if (VIt == ValueToLoc.
end())
307 LocIdx CurLoc = VIt->second;
313 (!isCalleeSaved(CurLoc) && isCalleeSaved(Idx.
asU64()))) {
320 for (
const auto &Var : VLocs) {
322 PendingDbgValues.push_back(
323 emitMOLoc(*Var.second.MO, Var.first, Var.second.Properties));
329 auto ValuesPreferredLoc = ValueToLoc.
find(Num);
330 if (ValuesPreferredLoc->second.isIllegal()) {
334 addUseBeforeDef(Var.first, Var.second.Properties, Num);
336 recoverAsEntryValue(Var.first, Var.second.Properties, Num);
340 LocIdx M = ValuesPreferredLoc->second;
342 auto Result = ActiveVLocs.
insert(std::make_pair(Var.first, NewValue));
344 Result.first->second = NewValue;
345 ActiveMLocs[
M].
insert(Var.first);
346 PendingDbgValues.push_back(
347 MTracker->
emitLoc(
M, Var.first, Var.second.Properties));
357 UseBeforeDefs[
ID.getInst()].push_back(UBD);
358 UseBeforeDefVariables.
insert(Var);
366 auto MIt = UseBeforeDefs.
find(Inst);
367 if (MIt == UseBeforeDefs.
end())
370 for (
auto &
Use : MIt->second) {
382 if (!UseBeforeDefVariables.
count(
Use.Var))
385 PendingDbgValues.push_back(MTracker->
emitLoc(L,
Use.Var,
Use.Properties));
387 flushDbgValues(pos,
nullptr);
392 if (PendingDbgValues.size() == 0)
402 Transfers.push_back({BundleStart,
MBB, PendingDbgValues});
403 PendingDbgValues.
clear();
440 if (!ShouldEmitDebugEntryValues)
444 if (!isEntryValueVariable(Var, Prop.
DIExpr))
448 if (!isEntryValueValue(Num))
457 PendingDbgValues.push_back(emitMOLoc(MO, Var, {
NewExpr, Prop.
Indirect}));
464 MI.getDebugLoc()->getInlinedAt());
471 auto It = ActiveVLocs.
find(Var);
472 if (It != ActiveVLocs.
end()) {
473 ActiveMLocs[It->second.Loc].
erase(Var);
474 ActiveVLocs.
erase(It);
477 UseBeforeDefVariables.
erase(Var);
483 redefVar(
MI, Properties, NewLoc);
492 MI.getDebugLoc()->getInlinedAt());
494 UseBeforeDefVariables.
erase(Var);
497 auto It = ActiveVLocs.
find(Var);
498 if (It != ActiveVLocs.
end())
499 ActiveMLocs[It->second.Loc].
erase(Var);
504 LocIdx NewLoc = *OptNewLoc;
510 for (
auto &
P : ActiveMLocs[NewLoc]) {
513 ActiveMLocs[NewLoc.asU64()].
clear();
514 VarLocs[NewLoc.asU64()] = MTracker->
readMLoc(NewLoc);
517 ActiveMLocs[NewLoc].
insert(Var);
518 if (It == ActiveVLocs.
end()) {
522 It->second.Loc = NewLoc;
523 It->second.Properties = Properties;
532 bool MakeUndef =
true) {
533 auto ActiveMLocIt = ActiveMLocs.
find(MLoc);
534 if (ActiveMLocIt == ActiveMLocs.
end())
545 if (Loc.Value == OldValue)
550 if (!NewLoc && !MakeUndef) {
552 for (
auto &Var : ActiveMLocIt->second) {
553 auto &Prop = ActiveVLocs.
find(Var)->second.Properties;
554 recoverAsEntryValue(Var, Prop, OldValue);
556 flushDbgValues(Pos,
nullptr);
562 for (
auto &Var : ActiveMLocIt->second) {
563 auto ActiveVLocIt = ActiveVLocs.
find(Var);
568 PendingDbgValues.push_back(MTracker->
emitLoc(NewLoc, Var, Properties));
573 ActiveVLocs.
erase(ActiveVLocIt);
575 ActiveVLocIt->second.Loc = *NewLoc;
581 if (!NewMLocs.
empty())
582 for (
auto &Var : NewMLocs)
583 ActiveMLocs[*NewLoc].
insert(Var);
588 VarLocs[NewLoc->
asU64()] = OldValue;
590 flushDbgValues(Pos,
nullptr);
593 ActiveMLocIt = ActiveMLocs.
find(MLoc);
594 ActiveMLocIt->second.clear();
603 if (VarLocs[Src.asU64()] != MTracker->
readMLoc(Src))
610 auto MovingVars = ActiveMLocs[Src];
611 ActiveMLocs[Dst] = MovingVars;
612 VarLocs[Dst.asU64()] = VarLocs[Src.asU64()];
615 for (
auto &Var : MovingVars) {
616 auto ActiveVLocIt = ActiveVLocs.
find(Var);
617 assert(ActiveVLocIt != ActiveVLocs.
end());
618 ActiveVLocIt->second.Loc = Dst;
621 MTracker->
emitLoc(Dst, Var, ActiveVLocIt->second.Properties);
622 PendingDbgValues.push_back(
MI);
624 ActiveMLocs[Src].
clear();
625 flushDbgValues(Pos,
nullptr);
639 auto MIB =
BuildMI(MF,
DL,
TII->get(TargetOpcode::DBG_VALUE));
646 MIB.addMetadata(Properties.
DIExpr);
681 LocIdxToIDNum(
ValueIDNum::EmptyValue), LocIdxToLocID(0) {
719 if (Size > 60000 || Offs > 60000)
755 if (MaskPair.first->clobbersPhysReg(
ID)) {
757 ValNum = {
CurBB, MaskPair.second, NewIdx};
778 Masks.push_back(std::make_pair(MO, InstID));
784 if (SpillID.
id() == 0) {
793 for (
unsigned StackIdx = 0; StackIdx <
NumSlotIdxes; ++StackIdx) {
814 return Twine(
"slot ")
831 std::string MLocName =
LocIdxToName(Location.Value.getLoc());
832 std::string DefName = Location.Value.asString(MLocName);
840 dbgs() <<
"Idx " << Location.Idx.asU64() <<
" " <<
foo <<
"\n";
862 unsigned short Offset = StackIdx.second;
890 bool UseDerefSize =
false;
892 unsigned DerefSizeInBytes = ValueSizeInBits / 8;
894 unsigned VariableSizeInBits = Fragment->SizeInBits;
895 if (VariableSizeInBits != ValueSizeInBits || Expr->
isComplex())
898 if (*Size != ValueSizeInBits) {
911 Expr, DIExpression::ApplyOffset | DIExpression::DerefAfter,
914 }
else if (UseDerefSize) {
920 Expr = DIExpression::prependOpcodes(Expr, Ops,
true);
921 unsigned Flags = DIExpression::StackValue | DIExpression::ApplyOffset;
929 Expr, DIExpression::ApplyOffset | DIExpression::DerefAfter,
957 MIB.addMetadata(Expr);
967 if (CalleeSavedRegs.
test(*RAI))
982 InstrRefBasedLDV::extractSpillBaseRegAndOffset(
const MachineInstr &
MI) {
984 "Spill instruction does not have exactly one memory operand?");
985 auto MMOI =
MI.memoperands_begin();
987 assert(PVal->
kind() == PseudoSourceValue::FixedStack &&
988 "Inconsistent memory operand in spill instruction");
989 int FI = cast<FixedStackPseudoSourceValue>(PVal)->getFrameIndex();
1006 auto *MemOperand = *
MI.memoperands_begin();
1007 unsigned SizeInBits = MemOperand->getSizeInBits();
1022 bool InstrRefBasedLDV::transferDebugValue(
const MachineInstr &
MI) {
1023 if (!
MI.isDebugValue())
1031 "Expected inlined-at fields to agree");
1039 if (
Scope ==
nullptr)
1045 if (
MI.isDebugValueList()) {
1047 VTracker->
defVar(
MI, Properties, None);
1070 VTracker->
defVar(
MI, Properties, None);
1071 }
else if (
MI.getOperand(0).isImm() ||
MI.getOperand(0).isFPImm() ||
1072 MI.getOperand(0).isCImm()) {
1087 if (!
MI.isDebugRef())
1092 if (!VTracker && !TTracker)
1095 unsigned InstNo =
MI.getOperand(0).getImm();
1096 unsigned OpNo =
MI.getOperand(1).getImm();
1103 "Expected inlined-at fields to agree");
1108 if (
Scope ==
nullptr)
1125 LowerBoundIt->Src == SoughtSub.Src) {
1126 std::tie(InstNo, OpNo) = LowerBoundIt->Dest;
1127 SoughtSub.Src = LowerBoundIt->Dest;
1128 if (
unsigned Subreg = LowerBoundIt->Subreg)
1129 SeenSubregs.push_back(Subreg);
1139 auto InstrIt = DebugInstrNumToInstr.find(InstNo);
1141 DebugPHINumToValue.end(), InstNo);
1142 if (InstrIt != DebugInstrNumToInstr.end()) {
1143 const MachineInstr &TargetInstr = *InstrIt->second.first;
1148 if (OpNo == MachineFunction::DebugOperandMemNumber &&
1152 NewID =
ValueIDNum(BlockNo, InstrIt->second.second, *L);
1153 }
else if (OpNo != MachineFunction::DebugOperandMemNumber) {
1165 NewID =
ValueIDNum(BlockNo, InstrIt->second.second, L);
1171 {
dbgs() <<
"Seen instruction reference to illegal operand\n"; });
1175 }
else if (PHIIt != DebugPHINumToValue.end() && PHIIt->InstrNum == InstNo) {
1178 NewID = resolveDbgPHIs(*
MI.getParent()->getParent(), MLiveOuts, MLiveIns,
1191 if (NewID && !SeenSubregs.empty()) {
1199 for (
unsigned Subreg :
reverse(SeenSubregs)) {
1211 if (NewID && !MTracker->
isSpill(L)) {
1217 if (TRCI->contains(
Reg))
1219 assert(TRC &&
"Couldn't find target register class?");
1224 if (Size != MainRegSize || Offset) {
1231 if (SubregSize == Size && SubregOffset == Offset) {
1259 VTracker->
defVar(
MI, Properties, NewID);
1269 for (
auto Location : MTracker->
locations()) {
1272 if (NewID &&
ID == NewID) {
1282 else if (!MTracker->
isSpill(*FoundLoc) &&
1291 TTracker->
redefVar(
MI, Properties, FoundLoc);
1295 if (!FoundLoc && NewID && NewID->
getBlock() == CurBB &&
1310 if (!
MI.isDebugPHI())
1314 if (VTracker || TTracker)
1320 unsigned InstrNum =
MI.getOperand(1).getImm();
1322 auto EmitBadPHI = [
this, &
MI, InstrNum](void) ->
bool {
1327 DebugPHINumToValue.push_back({InstrNum,
MI.getParent(),
None,
None});
1336 auto PHIRec = DebugPHIRecord(
1338 DebugPHINumToValue.push_back(PHIRec);
1343 }
else if (MO.
isFI()) {
1350 return EmitBadPHI();
1361 return EmitBadPHI();
1364 assert(
MI.getNumOperands() == 3 &&
"Stack DBG_PHI with no size?");
1365 unsigned slotBitSize =
MI.getOperand(2).getImm();
1367 unsigned SpillID = MTracker->
getLocID(*SpillNo, {slotBitSize, 0});
1372 auto DbgPHI = DebugPHIRecord({InstrNum,
MI.getParent(), Result,
SpillLoc});
1373 DebugPHINumToValue.push_back(DbgPHI);
1380 {
dbgs() <<
"Seen DBG_PHI with unrecognised operand format\n"; });
1381 return EmitBadPHI();
1390 if (
MI.isImplicitDef()) {
1400 }
else if (
MI.isMetaInstruction())
1408 bool CallChangesSP =
false;
1409 if (AdjustsStackInCalls &&
MI.isCall() &&
MI.getOperand(0).isSymbol() &&
1410 !strcmp(
MI.getOperand(0).getSymbolName(), StackProbeSymbolName.
data()))
1411 CallChangesSP =
true;
1415 auto IgnoreSPAlias = [
this, &
MI, CallChangesSP](
Register R) ->
bool {
1418 return MI.isCall() && MTracker->
SPAliases.count(R);
1430 Register::isPhysicalRegister(MO.
getReg()) &&
1431 !IgnoreSPAlias(MO.
getReg())) {
1438 RegMaskPtrs.push_back(&MO);
1444 MTracker->
defReg(DeadReg, CurBB, CurInst);
1446 for (
auto *MO : RegMaskPtrs)
1468 for (
uint32_t DeadReg : DeadRegs) {
1475 if (!RegMaskPtrs.empty()) {
1482 if (IgnoreSPAlias(
Reg))
1485 for (
auto *MO : RegMaskPtrs)
1503 void InstrRefBasedLDV::performCopy(
Register SrcRegNum,
Register DstRegNum) {
1506 MTracker->
defReg(*RAI, CurBB, CurInst);
1509 MTracker->
setReg(DstRegNum, SrcValue);
1513 unsigned SrcSubReg = SRI.getSubReg();
1514 unsigned SubRegIdx = SRI.getSubRegIndex();
1515 unsigned DstSubReg = TRI->
getSubReg(DstRegNum, SubRegIdx);
1530 MTracker->
setReg(DstSubReg, CpyValue);
1538 if (!
MI.hasOneMemOperand())
1542 auto MMOI =
MI.memoperands_begin();
1547 if (!
MI.getSpillSize(TII) && !
MI.getFoldedSpillSize(TII))
1551 return extractSpillBaseRegAndOffset(
MI);
1556 if (!isSpillInstruction(
MI, MF))
1567 if (!
MI.hasOneMemOperand())
1572 if (
MI.getRestoreSize(TII)) {
1573 Reg =
MI.getOperand(0).getReg();
1574 return extractSpillBaseRegAndOffset(
MI);
1579 bool InstrRefBasedLDV::transferSpillOrRestoreInst(
MachineInstr &
MI) {
1611 for (
unsigned SlotIdx = 0; SlotIdx < MTracker->
NumSlotIdxes; ++SlotIdx) {
1629 if (isLocationSpill(
MI, MF,
Reg)) {
1634 auto DoTransfer = [&](
Register SrcReg,
unsigned SpillID) {
1635 auto ReadValue = MTracker->
readReg(SrcReg);
1637 MTracker->
setMLoc(DstLoc, ReadValue);
1650 unsigned SpillID = MTracker->
getLocID(Loc, SubregIdx);
1651 DoTransfer(*SRI, SpillID);
1657 DoTransfer(
Reg, SpillID);
1671 MTracker->
defReg(*RAI, CurBB, CurInst);
1675 auto DoTransfer = [&](
Register DestReg,
unsigned SpillID) {
1677 auto ReadValue = MTracker->
readMLoc(SrcIdx);
1678 MTracker->
setReg(DestReg, ReadValue);
1683 unsigned SpillID = MTracker->
getLocID(*Loc, Subreg);
1684 DoTransfer(*SRI, SpillID);
1689 unsigned SpillID = MTracker->
getLocID(*Loc, {
Size, 0});
1690 DoTransfer(
Reg, SpillID);
1703 auto isCalleeSavedReg = [&](
unsigned Reg) {
1705 if (CalleeSavedRegs.
test(*RAI))
1714 if (SrcReg == DestReg)
1734 InstrRefBasedLDV::performCopy(SrcReg, DestReg);
1739 if (TTracker && isCalleeSavedReg(DestReg) && SrcRegOp->
isKill())
1745 MTracker->
defReg(SrcReg, CurBB, CurInst);
1752 TTracker->
clobberMloc(ClobberedLoc,
MI.getIterator(),
false);
1766 assert(
MI.isDebugValue() ||
MI.isDebugRef());
1768 MI.getDebugLoc()->getInlinedAt());
1769 FragmentInfo ThisFragment = MIVar.getFragmentOrDefault();
1774 auto SeenIt = SeenFragments.
find(MIVar.getVariable());
1775 if (SeenIt == SeenFragments.
end()) {
1777 OneFragment.
insert(ThisFragment);
1778 SeenFragments.
insert({MIVar.getVariable(), OneFragment});
1780 OverlapFragments.
insert({{MIVar.getVariable(), ThisFragment}, {}});
1787 OverlapFragments.
insert({{MIVar.getVariable(), ThisFragment}, {}});
1788 if (!IsInOLapMap.second)
1791 auto &ThisFragmentsOverlaps = IsInOLapMap.first->second;
1792 auto &AllSeenFragments = SeenIt->second;
1797 for (
auto &ASeenFragment : AllSeenFragments) {
1799 if (DIExpression::fragmentsOverlap(ThisFragment, ASeenFragment)) {
1801 ThisFragmentsOverlaps.push_back(ASeenFragment);
1804 auto ASeenFragmentsOverlaps =
1805 OverlapFragments.
find({MIVar.getVariable(), ASeenFragment});
1806 assert(ASeenFragmentsOverlaps != OverlapFragments.
end() &&
1807 "Previously seen var fragment has no vector of overlaps");
1808 ASeenFragmentsOverlaps->second.push_back(ThisFragment);
1812 AllSeenFragments.insert(ThisFragment);
1820 if (transferDebugValue(
MI))
1822 if (transferDebugInstrRef(
MI, MLiveOuts, MLiveIns))
1824 if (transferDebugPHI(
MI))
1826 if (transferRegisterCopy(
MI))
1828 if (transferSpillOrRestoreInst(
MI))
1830 transferRegisterDef(
MI);
1833 void InstrRefBasedLDV::produceMLocTransferFunction(
1835 unsigned MaxNumBlocks) {
1845 BlockMasks.
resize(MaxNumBlocks);
1848 unsigned BVWords = MachineOperand::getRegMaskSize(TRI->
getNumRegs());
1849 for (
auto &BV : BlockMasks)
1853 for (
auto &
MBB : MF) {
1865 for (
auto &
MI :
MBB) {
1868 process(
MI,
nullptr,
nullptr);
1871 if (
MI.isDebugValue() ||
MI.isDebugRef())
1872 accumulateFragmentMap(
MI);
1876 if (
uint64_t InstrNo =
MI.peekDebugInstrNum()) {
1877 auto InstrAndPos = std::make_pair(&
MI, CurInst);
1879 DebugInstrNumToInstr.insert(std::make_pair(InstrNo, InstrAndPos));
1882 assert(InsertResult.second);
1893 for (
auto Location : MTracker->
locations()) {
1896 if (
P.isPHI() &&
P.getLoc() == Idx.
asU64())
1900 auto &TransferMap = MLocTransfer[CurBB];
1901 auto Result = TransferMap.insert(std::make_pair(Idx.
asU64(),
P));
1908 for (
auto &
P : MTracker->
Masks) {
1909 BlockMasks[CurBB].clearBitsNotInMask(
P.first->getRegMask(), BVWords);
1915 for (
auto Location : MTracker->
locations()) {
1926 for (
unsigned int I = 0;
I < MaxNumBlocks; ++
I) {
1936 auto &TransferMap = MLocTransfer[
I];
1945 TransferMap.insert(std::make_pair(Idx.
asU64(), NotGeneratedNum));
1950 ValueID = NotGeneratedNum;
1956 bool InstrRefBasedLDV::mlocJoin(
1960 bool Changed =
false;
1969 BlockOrders.push_back(Pred);
1973 return BBToOrder.find(A)->second < BBToOrder.find(
B)->second;
1978 if (BlockOrders.size() == 0)
1983 for (
auto Location : MTracker->
locations()) {
1988 ValueIDNum FirstVal = OutLocs[BlockOrders[0]->getNumber()][Idx.
asU64()];
1993 if (InLocs[Idx.
asU64()] != FirstVal) {
1994 InLocs[Idx.
asU64()] = FirstVal;
2002 bool Disagree =
false;
2003 for (
unsigned int I = 1;
I < BlockOrders.size(); ++
I) {
2009 if (FirstVal == PredLiveOut)
2022 InLocs[Idx.
asU64()] = FirstVal;
2031 void InstrRefBasedLDV::findStackIndexInterference(
2046 Slots.push_back(It->second);
2051 if (!Pair.first.second)
2053 Slots.push_back(Pair.second);
2057 void InstrRefBasedLDV::placeMLocPHIs(
2061 findStackIndexInterference(StackUnits);
2073 for (
auto Location : MTracker->
locations()) {
2082 bool AnyIllegal =
false;
2091 FoundRegUnits.
insert(*URoot);
2097 NormalLocsToPHI.
insert(L);
2101 RegUnitsToPHIUp.
insert(FoundRegUnits.
begin(), FoundRegUnits.
end());
2107 auto CollectPHIsForLoc = [&](
LocIdx L) {
2110 for (
unsigned int I = 0;
I < OrderToBB.size(); ++
I) {
2112 const auto &TransferFunc = MLocTransfer[
MBB->
getNumber()];
2113 if (TransferFunc.find(L) != TransferFunc.end())
2120 if (!DefBlocks.
empty())
2126 BlockPHIPlacement(AllBlocks, DefBlocks, PHIBlocks);
2129 auto InstallPHIsAtLoc = [&PHIBlocks, &MInLocs](
LocIdx L) {
2135 for (
LocIdx L : NormalLocsToPHI) {
2136 CollectPHIsForLoc(L);
2138 InstallPHIsAtLoc(L);
2144 for (
unsigned Idx : StackUnits) {
2147 CollectPHIsForLoc(L);
2148 InstallPHIsAtLoc(L);
2154 unsigned ThisSize, ThisOffset;
2155 std::tie(ThisSize, ThisOffset) = Pair.first;
2156 if (ThisSize + ThisOffset <= Offset || Size + Offset <= ThisOffset)
2161 InstallPHIsAtLoc(ThisL);
2167 for (
Register R : RegUnitsToPHIUp) {
2169 CollectPHIsForLoc(L);
2172 InstallPHIsAtLoc(L);
2182 InstallPHIsAtLoc(AliasLoc);
2187 void InstrRefBasedLDV::buildMLocValueMap(
2190 std::priority_queue<unsigned int, std::vector<unsigned int>,
2191 std::greater<unsigned int>>
2202 for (
unsigned int I = 0;
I < BBToOrder.size(); ++
I) {
2204 OnWorklist.
insert(OrderToBB[
I]);
2205 AllBlocks.
insert(OrderToBB[
I]);
2209 for (
auto Location : MTracker->
locations())
2217 placeMLocPHIs(MF, AllBlocks, MInLocs, MLocTransfer);
2228 while (!Worklist.empty() || !Pending.empty()) {
2232 while (!Worklist.empty()) {
2239 InLocsChanged = mlocJoin(*
MBB, Visited, MOutLocs, MInLocs[CurBB]);
2240 InLocsChanged |= Visited.
insert(
MBB).second;
2253 for (
auto &
P : MLocTransfer[CurBB]) {
2254 if (
P.second.getBlock() == CurBB &&
P.second.isPHI()) {
2257 ToRemap.push_back(std::make_pair(
P.first, NewID));
2260 assert(
P.second.getBlock() == CurBB);
2261 ToRemap.push_back(std::make_pair(
P.first,
P.second));
2267 for (
auto &
P : ToRemap)
2273 bool OLChanged =
false;
2274 for (
auto Location : MTracker->
locations()) {
2290 if (BBToOrder[
s] > BBToOrder[
MBB]) {
2292 if (OnWorklist.
insert(
s).second)
2293 Worklist.push(BBToOrder[
s]);
2296 if (OnPending.
insert(
s).second)
2297 Pending.push(BBToOrder[
s]);
2302 Worklist.swap(Pending);
2307 assert(Pending.empty() &&
"Pending should be empty");
2314 void InstrRefBasedLDV::BlockPHIPlacement(
2323 IDF.setLiveInBlocks(AllBlocks);
2324 IDF.setDefiningBlocks(DefBlocks);
2325 IDF.calculate(PHIBlocks);
2339 if (BlockOrders.empty())
2342 for (
auto p : BlockOrders) {
2343 unsigned ThisBBNum =
p->getNumber();
2344 auto OutValIt = LiveOuts.find(
p);
2345 if (OutValIt == LiveOuts.end())
2348 const DbgValue &OutVal = *OutValIt->second;
2357 Locs.
resize(Locs.size() + 1);
2366 for (
unsigned int I = 0;
I < NumLocs; ++
I) {
2367 if (MOutLocs[ThisBBNum][
I] == ValToLookFor)
2368 Locs.back().push_back(
LocIdx(
I));
2383 for (
unsigned int I = 0;
I < NumLocs; ++
I) {
2385 if (MOutLocs[ThisBBNum][
I] == MPHI)
2386 Locs.back().push_back(
LocIdx(
I));
2392 assert(Locs.size() == BlockOrders.size());
2397 for (
auto *Prop : Properties)
2398 if (*Prop != *Properties0)
2404 for (
unsigned int I = 1;
I < Locs.size(); ++
I) {
2405 auto &LocVec = Locs[
I];
2407 std::set_intersection(CandidateLocs.begin(), CandidateLocs.end(),
2408 LocVec.begin(), LocVec.end(), std::inserter(NewCandidates, NewCandidates.begin()));
2409 CandidateLocs = NewCandidates;
2411 if (CandidateLocs.empty())
2417 LocIdx L = *CandidateLocs.begin();
2424 bool InstrRefBasedLDV::vlocJoin(
2429 bool Changed =
false;
2435 return BBToOrder[
A] < BBToOrder[
B];
2440 unsigned CurBlockRPONum = BBToOrder[&
MBB];
2446 int BackEdgesStart = 0;
2447 for (
auto p : BlockOrders) {
2456 DbgValue &OutLoc = *VLOCOutLocs.find(
p)->second;
2460 unsigned ThisBBRPONum = BBToOrder[
p];
2461 if (ThisBBRPONum < CurBlockRPONum)
2464 Values.push_back(std::make_pair(
p, &OutLoc));
2470 if (Bail || Values.size() == 0)
2476 const DbgValue &FirstVal = *Values[0].second;
2482 Changed = LiveIn != FirstVal;
2491 for (
auto &V : Values) {
2492 if (V.second->Properties != FirstVal.
Properties)
2501 bool Disagree =
false;
2502 for (
auto &V : Values) {
2503 if (*V.second == FirstVal)
2510 std::distance(Values.begin(), &V) >= BackEdgesStart)
2518 Changed = LiveIn != FirstVal;
2525 Changed = LiveIn != VPHI;
2532 void InstrRefBasedLDV::getBlocksForScope(
2542 BlocksToExplore.
insert(AssignBlocks.
begin(), AssignBlocks.
end());
2552 for (
auto *
MBB : BlocksToExplore) {
2562 if (BlocksToExplore.count(succ))
2564 if (!ArtificialBlocks.count(succ))
2567 DFS.push_back({succ, succ->succ_begin()});
2571 while (!DFS.empty()) {
2575 if (CurSucc == CurBB->
succ_end()) {
2582 if (!ToAdd.
count(*CurSucc) && ArtificialBlocks.count(*CurSucc)) {
2584 DFS.push_back({*CurSucc, (*CurSucc)->succ_begin()});
2592 BlocksToExplore.insert(ToAdd.
begin(), ToAdd.
end());
2595 void InstrRefBasedLDV::buildVLocValueMap(
2604 std::priority_queue<unsigned int, std::vector<unsigned int>,
2605 std::greater<unsigned int>>
2617 return BBToOrder[
A] < BBToOrder[
B];
2620 getBlocksForScope(DILoc, BlocksToExplore, AssignBlocks);
2626 if (BlocksToExplore.
size() == 1)
2633 for (
const auto *
MBB : BlocksToExplore)
2637 for (
auto *
MBB : BlocksToExplore)
2641 unsigned NumBlocks = BlockOrders.size();
2651 for (
unsigned int I = 0;
I < NumBlocks; ++
I) {
2653 LiveIns.push_back(EmptyDbgValue);
2654 LiveOuts.push_back(EmptyDbgValue);
2660 LiveOutIdx.reserve(NumBlocks);
2661 LiveInIdx.reserve(NumBlocks);
2662 for (
unsigned I = 0;
I < NumBlocks; ++
I) {
2663 LiveOutIdx[BlockOrders[
I]] = &LiveOuts[
I];
2664 LiveInIdx[BlockOrders[
I]] = &LiveIns[
I];
2671 for (
auto &Var : VarsWeCareAbout) {
2674 for (
unsigned int I = 0;
I < NumBlocks; ++
I) {
2676 LiveIns[
I] = EmptyDbgValue;
2677 LiveOuts[
I] = EmptyDbgValue;
2684 auto &TransferFunc = AllTheVLocs[ExpMBB->getNumber()].Vars;
2685 if (TransferFunc.find(Var) != TransferFunc.end())
2693 if (DefBlocks.
size() == 1) {
2694 placePHIsForSingleVarDefinition(MutBlocksToExplore, *DefBlocks.
begin(),
2695 AllTheVLocs, Var, Output);
2700 BlockPHIPlacement(MutBlocksToExplore, DefBlocks, PHIBlocks);
2704 unsigned BlockNo = PHIMBB->getNumber();
2705 DbgValue *LiveIn = LiveInIdx[PHIMBB];
2709 for (
auto *
MBB : BlockOrders) {
2710 Worklist.push(BBToOrder[
MBB]);
2721 bool FirstTrip =
true;
2722 while (!Worklist.empty() || !Pending.empty()) {
2723 while (!Worklist.empty()) {
2724 auto *
MBB = OrderToBB[Worklist.top()];
2728 auto LiveInsIt = LiveInIdx.find(
MBB);
2729 assert(LiveInsIt != LiveInIdx.end());
2730 DbgValue *LiveIn = LiveInsIt->second;
2734 bool InLocsChanged =
2735 vlocJoin(*
MBB, LiveOutIdx, BlocksToExplore, *LiveIn);
2739 Preds.push_back(Pred);
2751 pickVPHILoc(*
MBB, Var, LiveOutIdx, MOutLocs, Preds);
2754 InLocsChanged |= LiveIn->
ID != *ValueNum;
2755 LiveIn->
ID = *ValueNum;
2759 if (!InLocsChanged && !FirstTrip)
2763 bool OLChanged =
false;
2767 auto TransferIt = VTracker.
Vars.find(Var);
2768 if (TransferIt != VTracker.
Vars.end()) {
2772 if (*LiveOut != NewVal) {
2778 if (*LiveOut != TransferIt->second) {
2779 *LiveOut = TransferIt->second;
2785 if (*LiveOut != *LiveIn) {
2800 if (LiveInIdx.find(
s) == LiveInIdx.end())
2803 if (BBToOrder[
s] > BBToOrder[
MBB]) {
2804 if (OnWorklist.
insert(
s).second)
2805 Worklist.push(BBToOrder[
s]);
2806 }
else if (OnPending.
insert(
s).second && (FirstTrip || OLChanged)) {
2807 Pending.push(BBToOrder[
s]);
2811 Worklist.swap(Pending);
2821 for (
auto *
MBB : BlockOrders) {
2831 Var.
getFragment() &&
"Fragment info missing during value prop");
2836 BlockOrders.clear();
2837 BlocksToExplore.clear();
2840 void InstrRefBasedLDV::placePHIsForSingleVarDefinition(
2856 auto ValueIt = VLocs.
Vars.find(Var);
2867 for (
auto *ScopeBlock : InScopeBlocks) {
2871 Output[ScopeBlock->getNumber()].push_back({Var,
Value});
2878 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2881 for (
auto &
P : mloc_transfer) {
2884 dbgs() <<
"Loc " <<
foo <<
" --> " <<
bar <<
"\n";
2895 auto hasNonArtificialLocation = [](
const MachineInstr &
MI) ->
bool {
2897 return DL.getLine() != 0;
2901 for (
auto &
MBB : MF)
2903 ArtificialBlocks.insert(&
MBB);
2907 unsigned int RPONumber = 0;
2909 OrderToBB[RPONumber] =
MBB;
2910 BBToOrder[
MBB] = RPONumber;
2918 #ifdef EXPENSIVE_CHECKS
2921 if (MF.DebugValueSubstitutions.size() > 2) {
2922 for (
auto It = MF.DebugValueSubstitutions.begin();
2923 It != std::prev(MF.DebugValueSubstitutions.end()); ++It) {
2924 assert(It->Src != std::next(It)->Src &&
"Duplicate variable location "
2925 "substitution seen");
2934 void InstrRefBasedLDV::makeDepthFirstEjectionMap(
2936 const ScopeToDILocT &ScopeToDILocation,
2937 ScopeToAssignBlocksT &ScopeToAssignBlocks) {
2944 WorkStack.push_back({TopScope, TopScope->getChildren().
size() - 1});
2946 while (!WorkStack.empty()) {
2947 auto &ScopePosition = WorkStack.back();
2949 ssize_t ChildNum = ScopePosition.second--;
2952 if (ChildNum >= 0) {
2955 auto &ChildScope = Children[ChildNum];
2956 WorkStack.push_back(
2957 std::make_pair(ChildScope, ChildScope->getChildren().size() - 1));
2959 WorkStack.pop_back();
2964 auto DILocationIt = ScopeToDILocation.find(WS);
2965 if (DILocationIt != ScopeToDILocation.end()) {
2966 getBlocksForScope(DILocationIt->second, BlocksToExplore,
2967 ScopeToAssignBlocks.find(WS)->second);
2968 for (
auto *
MBB : BlocksToExplore) {
2970 if (EjectionMap[BBNum] == 0)
2974 BlocksToExplore.clear();
2980 bool InstrRefBasedLDV::depthFirstVLocAndEmit(
2981 unsigned MaxNumBlocks,
const ScopeToDILocT &ScopeToDILocation,
2982 const ScopeToVarsT &ScopeToVars, ScopeToAssignBlocksT &ScopeToAssignBlocks,
2987 TTracker =
new TransferTracker(TII, MTracker, MF, *TRI, CalleeSavedRegs, TPC);
2997 EjectionMap.
resize(MaxNumBlocks, 0);
2998 makeDepthFirstEjectionMap(EjectionMap, ScopeToDILocation,
2999 ScopeToAssignBlocks);
3006 AllTheVLocs[BBNum].
clear();
3012 TTracker->
loadInlocs(
MBB, MInLocs[BBNum], Output[BBNum], NumLocs);
3016 for (
auto &
MI :
MBB) {
3017 process(
MI, MOutLocs.get(), MInLocs.get());
3023 MInLocs[BBNum].reset();
3024 MOutLocs[BBNum].reset();
3027 AllTheVLocs[BBNum].
clear();
3033 unsigned HighestDFSIn = 0;
3036 while (!WorkStack.empty()) {
3037 auto &ScopePosition = WorkStack.back();
3039 ssize_t ChildNum = ScopePosition.second++;
3046 auto DILocIt = ScopeToDILocation.find(WS);
3047 if (HighestDFSIn <= WS->getDFSIn() && DILocIt != ScopeToDILocation.end()) {
3049 auto &VarsWeCareAbout = ScopeToVars.find(WS)->second;
3050 auto &BlocksInScope = ScopeToAssignBlocks.find(WS)->second;
3052 buildVLocValueMap(DILoc, VarsWeCareAbout, BlocksInScope, Output, MOutLocs,
3053 MInLocs, AllTheVLocs);
3060 if (ChildNum < (ssize_t)Children.size()) {
3062 auto &ChildScope = Children[ChildNum];
3063 WorkStack.push_back(std::make_pair(ChildScope, 0));
3065 WorkStack.pop_back();
3069 auto DILocationIt = ScopeToDILocation.find(WS);
3070 if (DILocationIt == ScopeToDILocation.end())
3073 getBlocksForScope(DILocationIt->second, BlocksToExplore,
3074 ScopeToAssignBlocks.find(WS)->second);
3075 for (
auto *
MBB : BlocksToExplore)
3079 BlocksToExplore.clear();
3088 for (
auto *
MBB : ArtificialBlocks)
3092 return emitTransfers(AllVarsNumbering);
3095 bool InstrRefBasedLDV::emitTransfers(
3108 MI->getDebugLoc()->getInlinedAt());
3112 [](
const auto &A,
const auto &
B) {
return A.first <
B.first; });
3117 for (
const auto &Pair : Insts)
3122 if (
P.Pos->isTerminator())
3126 for (
const auto &Pair : Insts)
3140 unsigned InputDbgValLimit) {
3148 this->DomTree = DomTree;
3159 STI.getFrameLowering()->stackProbeFunctionModifiesSP();
3160 if (AdjustsStackInCalls)
3161 StackProbeSymbolName = STI.getTargetLowering()->getStackProbeSymbolName(MF);
3172 int MaxNumBlocks = -1;
3173 for (
auto &
MBB : MF)
3175 assert(MaxNumBlocks >= 0);
3180 MLocTransfer.
resize(MaxNumBlocks);
3182 SavedLiveIns.resize(MaxNumBlocks);
3184 produceMLocTransferFunction(MF, MLocTransfer, MaxNumBlocks);
3189 FuncValueTable MOutLocs = std::make_unique<ValueTable[]>(MaxNumBlocks);
3190 FuncValueTable MInLocs = std::make_unique<ValueTable[]>(MaxNumBlocks);
3192 for (
int i = 0;
i < MaxNumBlocks; ++
i) {
3194 MOutLocs[
i] = std::make_unique<ValueIDNum[]>(NumLocs);
3195 MInLocs[
i] = std::make_unique<ValueIDNum[]>(NumLocs);
3202 buildMLocValueMap(MF, MInLocs, MOutLocs, MLocTransfer);
3206 for (
auto &DBG_PHI : DebugPHINumToValue) {
3208 if (!DBG_PHI.ValueRead)
3217 Num = MInLocs[BlockNo][LocNo.
asU64()];
3224 for (
auto &OrderPair : OrderToBB) {
3227 VTracker = &vlocs[CurBB];
3231 for (
auto &
MI :
MBB) {
3232 process(
MI, MOutLocs.get(), MInLocs.get());
3254 unsigned VarAssignCount = 0;
3255 for (
unsigned int I = 0;
I < OrderToBB.size(); ++
I) {
3256 auto *
MBB = OrderToBB[
I];
3259 for (
auto &idx : VTracker->
Vars) {
3260 const auto &Var = idx.first;
3262 assert(ScopeLoc !=
nullptr);
3268 AllVarsNumbering.
insert(std::make_pair(Var, AllVarsNumbering.
size()));
3269 ScopeToVars[
Scope].insert(Var);
3270 ScopeToAssignBlocks[
Scope].insert(VTracker->
MBB);
3271 ScopeToDILocation[
Scope] = ScopeLoc;
3276 bool Changed =
false;
3282 VarAssignCount > InputDbgValLimit) {
3283 LLVM_DEBUG(
dbgs() <<
"Disabling InstrRefBasedLDV: " << MF.getName()
3284 <<
" has " << MaxNumBlocks <<
" basic blocks and "
3286 <<
" variable assignments, exceeding limits.\n");
3291 Changed = depthFirstVLocAndEmit(
3292 MaxNumBlocks, ScopeToDILocation, ScopeToVars, ScopeToAssignBlocks,
3293 SavedLiveIns, MOutLocs, MInLocs, vlocs, MF, AllVarsNumbering, *TPC);
3302 ArtificialBlocks.clear();
3306 DebugInstrNumToInstr.clear();
3307 DebugPHINumToValue.clear();
3308 OverlapFragments.
clear();
3309 SeenFragments.
clear();
3310 SeenDbgPHIs.clear();
3321 class LDVSSAUpdater;
3334 LDVSSABlock *ParentBlock;
3335 BlockValueNum PHIValNum;
3336 LDVSSAPhi(BlockValueNum PHIValNum, LDVSSABlock *ParentBlock)
3337 : ParentBlock(ParentBlock), PHIValNum(PHIValNum) {}
3339 LDVSSABlock *
getParent() {
return ParentBlock; }
3344 class LDVSSABlockIterator {
3347 LDVSSAUpdater &Updater;
3350 LDVSSAUpdater &Updater)
3351 : PredIt(PredIt), Updater(Updater) {}
3353 bool operator!=(
const LDVSSABlockIterator &OtherIt)
const {
3354 return OtherIt.PredIt != PredIt;
3357 LDVSSABlockIterator &operator++() {
3371 LDVSSAUpdater &Updater;
3377 :
BB(
BB), Updater(Updater) {}
3380 return LDVSSABlockIterator(
BB.succ_begin(), Updater);
3384 return LDVSSABlockIterator(
BB.succ_end(), Updater);
3388 LDVSSAPhi *newPHI(BlockValueNum
Value) {
3389 PHIList.emplace_back(
Value,
this);
3390 return &PHIList.back();
3394 PHIListT &phis() {
return PHIList; }
3400 class LDVSSAUpdater {
3415 : Loc(L), MLiveIns(MLiveIns) {}
3418 for (
auto &Block : BlockMap)
3419 delete Block.second;
3426 ~LDVSSAUpdater() { reset(); }
3431 auto it = BlockMap.find(
BB);
3432 if (
it == BlockMap.end()) {
3433 BlockMap[
BB] =
new LDVSSABlock(*
BB, *
this);
3434 it = BlockMap.find(
BB);
3441 BlockValueNum getValue(LDVSSABlock *LDVBB) {
3442 return MLiveIns[LDVBB->BB.getNumber()][Loc.
asU64()].asU64();
3447 return Updater.getSSALDVBlock(*PredIt);
3453 out <<
"SSALDVPHI " << PHI.PHIValNum;
3479 class PHI_iterator {
3488 : PHI(
P), Idx(PHI->IncomingValues.
size()) {}
3505 return PHI_iterator(PHI,
true);
3513 Preds->push_back(
BB->Updater.getSSALDVBlock(Pred));
3524 Updater->UndefMap[&
BB->BB] = Num;
3534 LDVSSAUpdater *Updater) {
3535 BlockValueNum PHIValNum = Updater->getValue(
BB);
3536 LDVSSAPhi *PHI =
BB->newPHI(PHIValNum);
3537 Updater->PHIs[PHIValNum] = PHI;
3543 static void AddPHIOperand(LDVSSAPhi *PHI, BlockValueNum Val, LDVSSABlock *Pred) {
3544 PHI->IncomingValues.push_back(std::make_pair(Pred, Val));
3549 static LDVSSAPhi *
ValueIsPHI(BlockValueNum Val, LDVSSAUpdater *Updater) {
3550 auto PHIIt = Updater->PHIs.find(Val);
3551 if (PHIIt == Updater->PHIs.end())
3553 return PHIIt->second;
3559 LDVSSAPhi *PHI = ValueIsPHI(Val, Updater);
3560 if (PHI && PHI->IncomingValues.size() == 0)
3567 static BlockValueNum
GetPHIValue(LDVSSAPhi *PHI) {
return PHI->PHIValNum; }
3575 assert(MLiveOuts && MLiveIns &&
3576 "Tried to resolve DBG_PHI before location "
3577 "tables allocated?");
3581 auto SeenDbgPHIIt = SeenDbgPHIs.find(&Here);
3582 if (SeenDbgPHIIt != SeenDbgPHIs.end())
3583 return SeenDbgPHIIt->second;
3586 resolveDbgPHIsImpl(MF, MLiveOuts, MLiveIns, Here, InstrNum);
3587 SeenDbgPHIs.insert({&Here,
Result});
3596 auto RangePair = std::equal_range(DebugPHINumToValue.begin(),
3597 DebugPHINumToValue.end(), InstrNum);
3598 auto LowerIt = RangePair.first;
3599 auto UpperIt = RangePair.second;
3602 if (LowerIt == UpperIt)
3609 auto DBGPHIRange =
make_range(LowerIt, UpperIt);
3610 for (
const DebugPHIRecord &DBG_PHI : DBGPHIRange)
3611 if (!DBG_PHI.ValueRead)
3615 if (std::distance(LowerIt, UpperIt) == 1)
3616 return *LowerIt->ValueRead;
3622 LocIdx Loc = *LowerIt->ReadLoc;
3631 LDVSSAUpdater Updater(Loc, MLiveIns);
3639 for (
const auto &DBG_PHI : DBGPHIRange) {
3640 LDVSSABlock *
Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
3642 AvailableValues.
insert(std::make_pair(Block, Num.
asU64()));
3645 LDVSSABlock *HereBlock = Updater.getSSALDVBlock(Here.
getParent());
3646 const auto &AvailIt = AvailableValues.
find(HereBlock);
3647 if (AvailIt != AvailableValues.
end()) {
3656 BlockValueNum ResultInt = Impl.GetValue(Updater.getSSALDVBlock(Here.
getParent()));
3673 for (
const auto &DBG_PHI : DBGPHIRange) {
3674 LDVSSABlock *
Block = Updater.getSSALDVBlock(DBG_PHI.MBB);
3676 ValidatedValues.
insert(std::make_pair(Block, Num));
3681 for (
auto &PHI : CreatedPHIs)
3682 SortedPHIs.push_back(PHI);
3685 SortedPHIs.begin(), SortedPHIs.end(), [&](LDVSSAPhi *A, LDVSSAPhi *
B) {
3686 return BBToOrder[&A->getParent()->BB] < BBToOrder[&B->getParent()->BB];
3689 for (
auto &PHI : SortedPHIs) {
3691 MLiveIns[PHI->ParentBlock->BB.getNumber()][Loc.
asU64()];
3694 for (
auto &PHIIt : PHI->IncomingValues) {
3696 if (Updater.UndefMap.find(&PHIIt.first->BB) != Updater.UndefMap.end())
3700 const ValueTable &BlockLiveOuts = MLiveOuts[PHIIt.first->BB.getNumber()];
3702 auto VVal = ValidatedValues.
find(PHIIt.first);
3703 if (VVal == ValidatedValues.
end()) {
3708 ValueToCheck = ThisBlockValueNum;
3712 ValueToCheck = VVal->second;
3715 if (BlockLiveOuts[Loc.
asU64()] != ValueToCheck)
3720 ValidatedValues.
insert({PHI->ParentBlock, ThisBlockValueNum});