diff --git a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h --- a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h +++ b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.h @@ -889,6 +889,10 @@ ValueIDNum **MOutLocs, SmallVectorImpl &MLocTransfer); + /// Examine the stack indexes (i.e. offsets within the stack) to find the + /// basic units of interference -- like reg units, but for the stack. + void findStackIndexInterference(SmallVectorImpl &Slots); + /// Install PHI values into the live-in array for each block, according to /// the IDF of each register. void placeMLocPHIs(MachineFunction &MF, diff --git a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp --- a/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp +++ b/llvm/lib/CodeGen/LiveDebugValues/InstrRefBasedImpl.cpp @@ -1884,22 +1884,52 @@ return Changed; } -void InstrRefBasedLDV::placeMLocPHIs(MachineFunction &MF, - SmallPtrSetImpl &AllBlocks, - ValueIDNum **MInLocs, - SmallVectorImpl &MLocTransfer) { +void InstrRefBasedLDV::findStackIndexInterference( + SmallVectorImpl &Slots) { + // We could spend a bit of time finding the exact, minimal, set of stack + // indexes that interfere with each other, much like reg units. Or, we can + // rely on the fact that: + // * The smallest / lowest index will interfere with everything at zero + // offset, which will be the largest set of registers, + // * Most indexes with non-zero offset will end up being interference units + // anyway. + // So just pick those out and return them. + + // We can rely on a single-byte stack index existing already, because we + // initialize them in MLocTracker. + auto It = MTracker->StackSlotIdxes.find({8, 0}); + assert(It != MTracker->StackSlotIdxes.end()); + Slots.push_back(It->second); + + // Find anything that has a non-zero offset and add that too. + for (auto &Pair : MTracker->StackSlotIdxes) { + // Is offset zero? If so, ignore. + if (!Pair.first.second) + continue; + Slots.push_back(Pair.second); + } +} + +void InstrRefBasedLDV::placeMLocPHIs( + MachineFunction &MF, SmallPtrSetImpl &AllBlocks, + ValueIDNum **MInLocs, SmallVectorImpl &MLocTransfer) { + SmallVector StackUnits; + findStackIndexInterference(StackUnits); + // To avoid repeatedly running the PHI placement algorithm, leverage the // fact that a def of register MUST also def its register units. Find the - // units for registers, place PHIs for them, and then replicate them for + // units for registers, place PHIs for them, and then replicate them for // aliasing registers. Some inputs that are never def'd (DBG_PHIs of // arguments) don't lead to register units being tracked, just place PHIs for - // those registers directly. Do the same for stack slots. + // those registers directly. Stack slots have their own form of "unit", + // store them to one side. SmallSet RegUnitsToPHIUp; - SmallSet LocsToPHI; + SmallSet NormalLocsToPHI; + SmallSet StackSlots; for (auto Location : MTracker->locations()) { LocIdx L = Location.Idx; if (MTracker->isSpill(L)) { - LocsToPHI.insert(L); + StackSlots.insert(MTracker->locIDToSpill(MTracker->LocIdxToLocID[L])); continue; } @@ -1920,7 +1950,7 @@ } if (AnyIllegal) { - LocsToPHI.insert(L); + NormalLocsToPHI.insert(L); continue; } @@ -1952,12 +1982,41 @@ BlockPHIPlacement(AllBlocks, DefBlocks, PHIBlocks); }; - // For spill slots, and locations with no reg units, just place PHIs. - for (LocIdx L : LocsToPHI) { - CollectPHIsForLoc(L); - // Install those PHI values into the live-in value array. + auto InstallPHIsAtLoc = [&PHIBlocks, &MInLocs](LocIdx L) { for (const MachineBasicBlock *MBB : PHIBlocks) MInLocs[MBB->getNumber()][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L); + }; + + // For locations with no reg units, just place PHIs. + for (LocIdx L : NormalLocsToPHI) { + CollectPHIsForLoc(L); + // Install those PHI values into the live-in value array. + InstallPHIsAtLoc(L); + } + + // For stack slots, calculate PHIs for the equivalent of the units, then + // install for each index. + for (SpillLocationNo Slot : StackSlots) { + for (unsigned Idx : StackUnits) { + unsigned SpillID = MTracker->getSpillIDWithIdx(Slot, Idx); + LocIdx L = MTracker->getSpillMLoc(SpillID); + CollectPHIsForLoc(L); + InstallPHIsAtLoc(L); + + // Find anything that aliases this stack index, install PHIs for it too. + unsigned Size, Offset; + std::tie(Size, Offset) = MTracker->StackIdxesToPos[Idx]; + for (auto &Pair : MTracker->StackSlotIdxes) { + unsigned ThisSize, ThisOffset; + std::tie(ThisSize, ThisOffset) = Pair.first; + if (ThisSize + ThisOffset <= Offset || Size + Offset <= ThisOffset) + continue; + + unsigned ThisID = MTracker->getSpillIDWithIdx(Slot, Pair.second); + LocIdx ThisL = MTracker->getSpillMLoc(ThisID); + InstallPHIsAtLoc(ThisL); + } + } } // For reg units, place PHIs, and then place them for any aliasing registers. @@ -1966,8 +2025,7 @@ CollectPHIsForLoc(L); // Install those PHI values into the live-in value array. - for (const MachineBasicBlock *MBB : PHIBlocks) - MInLocs[MBB->getNumber()][L.asU64()] = ValueIDNum(MBB->getNumber(), 0, L); + InstallPHIsAtLoc(L); // Now find aliases and install PHIs for those. for (MCRegAliasIterator RAI(R, TRI, true); RAI.isValid(); ++RAI) { @@ -1977,9 +2035,7 @@ continue; LocIdx AliasLoc = MTracker->lookupOrTrackRegister(*RAI); - for (const MachineBasicBlock *MBB : PHIBlocks) - MInLocs[MBB->getNumber()][AliasLoc.asU64()] = - ValueIDNum(MBB->getNumber(), 0, AliasLoc); + InstallPHIsAtLoc(AliasLoc); } } } diff --git a/llvm/unittests/CodeGen/InstrRefLDVTest.cpp b/llvm/unittests/CodeGen/InstrRefLDVTest.cpp --- a/llvm/unittests/CodeGen/InstrRefLDVTest.cpp +++ b/llvm/unittests/CodeGen/InstrRefLDVTest.cpp @@ -178,6 +178,13 @@ LDV->buildMLocValueMap(*MF, MInLocs, MOutLocs, MLocTransfer); } + void placeMLocPHIs(MachineFunction &MF, + SmallPtrSetImpl &AllBlocks, + ValueIDNum **MInLocs, + SmallVectorImpl &MLocTransfer) { + LDV->placeMLocPHIs(MF, AllBlocks, MInLocs, MLocTransfer); + } + Optional pickVPHILoc(const MachineBasicBlock &MBB, const DebugVariable &Var, const InstrRefBasedLDV::LiveIdxT &LiveOuts, ValueIDNum **MOutLocs, @@ -1073,6 +1080,92 @@ TransferFunc[2].clear(); } +TEST_F(InstrRefLDVTest, MLocDiamondSpills) { + // Test that defs in stack locations that require PHIs, cause PHIs to be + // installed in aliasing locations. i.e., if there's a PHI in the lower + // 8 bits of the stack, there should be PHIs for 16/32/64 bit locations + // on the stack too. + // Technically this isn't needed for accuracy: we should calculate PHIs + // independently for each location. However, because there's an optimisation + // that only places PHIs for the lower "interfering" parts of stack slots, + // test for this behaviour. + setupDiamondBlocks(); + + ASSERT_TRUE(MTracker->getNumLocs() == 1); + LocIdx RspLoc(0); + + // Create a stack location and ensure it's tracked. + SpillLoc SL = {getRegByName("RSP"), StackOffset::getFixed(-8)}; + SpillLocationNo SpillNo = MTracker->getOrTrackSpillLoc(SL); + ASSERT_EQ(MTracker->getNumLocs(), 10u); // Tracks all possible stack locs. + // Locations are: RSP, stack slots from 2^3 bits wide up to 2^9 for zmm regs, + // then slots for sub_8bit_hi and sub_16bit_hi ({8, 8} and {16, 16}). + + // Pick out the locations on the stack that various x86 regs would be written + // to. HAX is the upper 16 bits of EAX. + unsigned ALID = MTracker->getLocID(SpillNo, {8, 0}); + unsigned AHID = MTracker->getLocID(SpillNo, {8, 8}); + unsigned AXID = MTracker->getLocID(SpillNo, {16, 0}); + unsigned EAXID = MTracker->getLocID(SpillNo, {32, 0}); + unsigned HAXID = MTracker->getLocID(SpillNo, {16, 16}); + unsigned RAXID = MTracker->getLocID(SpillNo, {64, 0}); + LocIdx ALStackLoc = MTracker->getSpillMLoc(ALID); + LocIdx AHStackLoc = MTracker->getSpillMLoc(AHID); + LocIdx AXStackLoc = MTracker->getSpillMLoc(AXID); + LocIdx EAXStackLoc = MTracker->getSpillMLoc(EAXID); + LocIdx HAXStackLoc = MTracker->getSpillMLoc(HAXID); + LocIdx RAXStackLoc = MTracker->getSpillMLoc(RAXID); + // There are other locations, for things like xmm0, which we're going to + // ignore here. + + ValueIDNum InLocs[4][10]; + ValueIDNum *InLocsPtr[4] = {InLocs[0], InLocs[1], InLocs[2], InLocs[3]}; + + // Transfer function: start with nothing. + SmallVector TransferFunc; + TransferFunc.resize(4); + + // Name some values. + unsigned EntryBlk = 0, Blk1 = 1, RetBlk = 3; + + ValueIDNum LiveInRsp(EntryBlk, 0, RspLoc); + ValueIDNum ALLiveIn(EntryBlk, 0, ALStackLoc); + ValueIDNum AHLiveIn(EntryBlk, 0, AHStackLoc); + ValueIDNum HAXLiveIn(EntryBlk, 0, HAXStackLoc); + ValueIDNum ALPHI(RetBlk, 0, ALStackLoc); + ValueIDNum AXPHI(RetBlk, 0, AXStackLoc); + ValueIDNum EAXPHI(RetBlk, 0, EAXStackLoc); + ValueIDNum HAXPHI(RetBlk, 0, HAXStackLoc); + ValueIDNum RAXPHI(RetBlk, 0, RAXStackLoc); + + ValueIDNum ALDefInBlk1(Blk1, 1, ALStackLoc); + ValueIDNum HAXDefInBlk1(Blk1, 1, HAXStackLoc); + + SmallPtrSet AllBlocks{MBB0, MBB1, MBB2, MBB3}; + + // If we put defs into one side of the diamond, for AL and HAX, then we should + // find all aliasing positions have PHIs placed. This isn't technically what + // the transfer function says to do: but we're testing that the optimisation + // to reduce IDF calculation does the right thing. + // AH should not be def'd: it don't alias AL or HAX. + // + // NB: we don't call buildMLocValueMap, because it will try to eliminate the + // upper-slot PHIs, and succeed because of our slightly cooked transfer + // function. + TransferFunc[1].insert({ALStackLoc, ALDefInBlk1}); + TransferFunc[1].insert({HAXStackLoc, HAXDefInBlk1}); + initValueArray(InLocsPtr, 4, 10); + placeMLocPHIs(*MF, AllBlocks, InLocsPtr, TransferFunc); + EXPECT_EQ(InLocs[3][ALStackLoc.asU64()], ALPHI); + EXPECT_EQ(InLocs[3][AXStackLoc.asU64()], AXPHI); + EXPECT_EQ(InLocs[3][EAXStackLoc.asU64()], EAXPHI); + EXPECT_EQ(InLocs[3][HAXStackLoc.asU64()], HAXPHI); + EXPECT_EQ(InLocs[3][RAXStackLoc.asU64()], RAXPHI); + // AH should be left untouched, + EXPECT_EQ(InLocs[3][AHStackLoc.asU64()], ValueIDNum::EmptyValue); + +} + TEST_F(InstrRefLDVTest, MLocSimpleLoop) { // entry // |