From 98409ec54e30b851b56b61429259ca2499f65808 Mon Sep 17 00:00:00 2001 From: Simon Pilgrim Date: Mon, 9 Sep 2019 12:33:22 +0000 Subject: [PATCH] Revert rL371198 from llvm/trunk: [DFAPacketizer] Track resources for packetized instructions This patch allows the DFAPacketizer to be queried after a packet is formed to work out which resources were allocated to the packetized instructions. This is particularly important for targets that do their own bundle packing - it's not sufficient to know simply that instructions can share a packet; which slots are used is also required for encoding. This extends the emitter to emit a side-table containing resource usage diffs for each state transition. The packetizer maintains a set of all possible resource states in its current state. After packetization is complete, all remaining resource states are possible packetization strategies. The sidetable is only ~500K for Hexagon, but the extra tracking is disabled by default (most uses of the packetizer like MachinePipeliner don't care and don't need the extra maintained state). Differential Revision: https://reviews.llvm.org/D66936 ........ Reverted as this is causing "compiler out of heap space" errors on MSVC 2017/19 NDEBUG builds git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@371393 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/DFAPacketizer.h | 44 +----- lib/CodeGen/DFAPacketizer.cpp | 65 ++------- lib/Target/Hexagon/HexagonVLIWPacketizer.cpp | 11 -- test/CodeGen/Hexagon/packetizer-resources.ll | 29 ---- utils/TableGen/DFAPacketizerEmitter.cpp | 140 +++++++------------ 5 files changed, 60 insertions(+), 229 deletions(-) delete mode 100644 test/CodeGen/Hexagon/packetizer-resources.ll diff --git a/include/llvm/CodeGen/DFAPacketizer.h b/include/llvm/CodeGen/DFAPacketizer.h index f053e357df8..cf58ee0cabe 100644 --- a/include/llvm/CodeGen/DFAPacketizer.h +++ b/include/llvm/CodeGen/DFAPacketizer.h @@ -82,53 +82,20 @@ private: int CurrentState = 0; const DFAStateInput (*DFAStateInputTable)[2]; const unsigned *DFAStateEntryTable; - const std::pair *DFAResourceTransitionTable; - const unsigned *DFAResourceTransitionEntryTable; // CachedTable is a map from to ToState. DenseMap CachedTable; - // CachedResourceTransitions is a map from to a list of - // resource transitions. - DenseMap>> - CachedResourceTransitions; // Read the DFA transition table and update CachedTable. void ReadTable(unsigned state); - bool TrackResources = false; - // State for the current packet. Every entry is a possible packing of the - // bundle, indexed by cumulative resource state. Each entry is a list of the - // cumulative resource states after packing each instruction. For example if - // we pack I0: [0x4] and I1: [0x2] we will end up with: - // ResourceStates[0x6] = [0x4, 0x6] - DenseMap> ResourceStates; - public: DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2], - const unsigned *SET, - const std::pair *RTT = nullptr, - const unsigned *RTET = nullptr); + const unsigned *SET); // Reset the current state to make all resources available. void clearResources() { CurrentState = 0; - ResourceStates.clear(); - ResourceStates[0] = {}; - } - - // Set whether this packetizer should track not just whether instructions - // can be packetized, but also which functional units each instruction ends up - // using after packetization. - void setTrackResources(bool Track) { - if (Track != TrackResources) { - TrackResources = Track; - if (Track) { - CachedTable.clear(); - assert(DFAResourceTransitionEntryTable); - assert(DFAResourceTransitionTable); - } - } - assert(CurrentState == 0 && "Can only change TrackResources on an empty packetizer!"); } // Return the DFAInput for an instruction class. @@ -153,15 +120,6 @@ public: // current state to reflect that change. void reserveResources(MachineInstr &MI); - // Return the resources used by the InstIdx'th instruction added to this - // packet. The resources are returned as a bitvector of functional units. - // - // Note that a bundle may be packed in multiple valid ways. This function - // returns one arbitary valid packing. - // - // Requires setTrackResources(true) to have been called. - unsigned getUsedResources(unsigned InstIdx); - const InstrItineraryData *getInstrItins() const { return InstrItins; } }; diff --git a/lib/CodeGen/DFAPacketizer.cpp b/lib/CodeGen/DFAPacketizer.cpp index edf5186124e..b99be5d7a87 100644 --- a/lib/CodeGen/DFAPacketizer.cpp +++ b/lib/CodeGen/DFAPacketizer.cpp @@ -23,7 +23,6 @@ //===----------------------------------------------------------------------===// #include "llvm/CodeGen/DFAPacketizer.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/CodeGen/MachineFunction.h" #include "llvm/CodeGen/MachineInstr.h" #include "llvm/CodeGen/MachineInstrBundle.h" @@ -73,11 +72,9 @@ static DFAInput getDFAInsnInput(const std::vector &InsnClass) { // -------------------------------------------------------------------- DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, - const DFAStateInput (*SIT)[2], const unsigned *SET, - const std::pair *RTT, - const unsigned *RTET) - : InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET), - DFAResourceTransitionTable(RTT), DFAResourceTransitionEntryTable(RTET) { + const DFAStateInput (*SIT)[2], + const unsigned *SET): + InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET) { // Make sure DFA types are large enough for the number of terms & resources. static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAInput)), @@ -85,7 +82,6 @@ DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, static_assert( (DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)), "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput"); - clearResources(); } // Read the DFA transition table and update CachedTable. @@ -97,26 +93,16 @@ DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, // for the ith state // void DFAPacketizer::ReadTable(unsigned int state) { - unsigned ThisStateIdx = DFAStateEntryTable[state]; - unsigned NextStateIdxInTable = DFAStateEntryTable[state + 1]; + unsigned ThisState = DFAStateEntryTable[state]; + unsigned NextStateInTable = DFAStateEntryTable[state+1]; // Early exit in case CachedTable has already contains this // state's transitions. - if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisStateIdx][0]))) + if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0]))) return; - for (unsigned TransitionIdx = ThisStateIdx; - TransitionIdx < NextStateIdxInTable; TransitionIdx++) { - auto TransitionPair = - UnsignPair(state, DFAStateInputTable[TransitionIdx][0]); - CachedTable[TransitionPair] = DFAStateInputTable[TransitionIdx][1]; - - if (TrackResources) { - unsigned I = DFAResourceTransitionEntryTable[TransitionIdx]; - unsigned E = DFAResourceTransitionEntryTable[TransitionIdx + 1]; - CachedResourceTransitions[TransitionPair] = makeArrayRef( - &DFAResourceTransitionTable[I], &DFAResourceTransitionTable[E]); - } - } + for (unsigned i = ThisState; i < NextStateInTable; i++) + CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] = + DFAStateInputTable[i][1]; } // Return the DFAInput for an instruction class. @@ -155,16 +141,6 @@ void DFAPacketizer::reserveResources(const MCInstrDesc *MID) { DFAInput InsnInput = getInsnInput(InsnClass); UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); ReadTable(CurrentState); - - if (TrackResources) { - DenseMap> NewResourceStates; - for (const auto &KV : CachedResourceTransitions[StateTrans]) { - assert(ResourceStates.count(KV.first)); - NewResourceStates[KV.second] = ResourceStates[KV.first]; - NewResourceStates[KV.second].push_back(KV.second); - } - ResourceStates = NewResourceStates; - } assert(CachedTable.count(StateTrans) != 0); CurrentState = CachedTable[StateTrans]; } @@ -183,21 +159,6 @@ void DFAPacketizer::reserveResources(MachineInstr &MI) { reserveResources(&MID); } -unsigned DFAPacketizer::getUsedResources(unsigned InstIdx) { - assert(TrackResources && "getUsedResources requires resource tracking!"); - // Assert that there is at least one example of a valid bundle format. - assert(!ResourceStates.empty() && "Invalid bundle!"); - SmallVectorImpl &RS = ResourceStates.begin()->second; - - // RS stores the cumulative resources used up to and including the I'th - // instruction. The 0th instruction is the base case. - if (InstIdx == 0) - return RS[0]; - // Return the difference between the cumulative resources used by InstIdx and - // its predecessor. - return RS[InstIdx] ^ RS[InstIdx - 1]; -} - namespace llvm { // This class extends ScheduleDAGInstrs and overrides the schedule method @@ -249,7 +210,6 @@ VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf, MachineLoopInfo &mli, AliasAnalysis *aa) : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) { ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget()); - ResourceTracker->setTrackResources(true); VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA); } @@ -264,11 +224,8 @@ void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB, LLVM_DEBUG({ if (!CurrentPacketMIs.empty()) { dbgs() << "Finalizing packet:\n"; - unsigned Idx = 0; - for (MachineInstr *MI : CurrentPacketMIs) { - unsigned R = ResourceTracker->getUsedResources(Idx++); - dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI; - } + for (MachineInstr *MI : CurrentPacketMIs) + dbgs() << " * " << *MI; } }); if (CurrentPacketMIs.size() > 1) { diff --git a/lib/Target/Hexagon/HexagonVLIWPacketizer.cpp b/lib/Target/Hexagon/HexagonVLIWPacketizer.cpp index 7024dafd479..c89c0b3369f 100644 --- a/lib/Target/Hexagon/HexagonVLIWPacketizer.cpp +++ b/lib/Target/Hexagon/HexagonVLIWPacketizer.cpp @@ -24,7 +24,6 @@ #include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/StringExtras.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/CodeGen/MachineBasicBlock.h" #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" @@ -1764,16 +1763,6 @@ HexagonPacketizerList::addToPacket(MachineInstr &MI) { void HexagonPacketizerList::endPacket(MachineBasicBlock *MBB, MachineBasicBlock::iterator EndMI) { // Replace VLIWPacketizerList::endPacket(MBB, EndMI). - LLVM_DEBUG({ - if (!CurrentPacketMIs.empty()) { - dbgs() << "Finalizing packet:\n"; - unsigned Idx = 0; - for (MachineInstr *MI : CurrentPacketMIs) { - unsigned R = ResourceTracker->getUsedResources(Idx++); - dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI; - } - } - }); bool memShufDisabled = getmemShufDisabled(); if (memShufDisabled && !foundLSInPacket()) { diff --git a/test/CodeGen/Hexagon/packetizer-resources.ll b/test/CodeGen/Hexagon/packetizer-resources.ll deleted file mode 100644 index 9bd0cb1f5fa..00000000000 --- a/test/CodeGen/Hexagon/packetizer-resources.ll +++ /dev/null @@ -1,29 +0,0 @@ -; RUN: llc -O2 -march=hexagon < %s -debug-only=packets 2>&1 | FileCheck %s -; REQUIRES: asserts - -; CHECK: Finalizing packet: -; CHECK-NEXT: * [res:0x8] renamable $r1 = S2_vsplatrb renamable $r0 -; CHECK-NEXT: * [res:0x4] renamable $d1 = S2_vsplatrh killed renamable $r0 - -target triple = "hexagon" - -; Function Attrs: nounwind readnone -define i64 @f0(i64 %a0) #0 { -b0: - %v0 = trunc i64 %a0 to i32 - %v1 = and i32 %v0, 65535 - %v2 = tail call i64 @llvm.hexagon.S2.vsplatrh(i32 %v1) - %v3 = and i32 %v0, 255 - %v4 = tail call i32 @llvm.hexagon.S2.vsplatrb(i32 %v3) - %v5 = sext i32 %v4 to i64 - %v6 = add nsw i64 %v5, %v2 - ret i64 %v6 -} - -; Function Attrs: nounwind readnone -declare i64 @llvm.hexagon.S2.vsplatrh(i32) #0 - -; Function Attrs: nounwind readnone -declare i32 @llvm.hexagon.S2.vsplatrb(i32) #0 - -attributes #0 = { nounwind readnone } diff --git a/utils/TableGen/DFAPacketizerEmitter.cpp b/utils/TableGen/DFAPacketizerEmitter.cpp index 8952151cdf7..19a6580c1d4 100644 --- a/utils/TableGen/DFAPacketizerEmitter.cpp +++ b/utils/TableGen/DFAPacketizerEmitter.cpp @@ -192,14 +192,7 @@ class State { const int stateNum; mutable bool isInitial; mutable std::set stateInfo; - - struct TransitionInfo { - // Maps from a resource bitmask in this state to the equivalent resource - // bitmap in the transitioned-to state. This is a 1-to-N mapping. - std::vector> ResourceTransitions; - const State *S; - }; - using TransitionMap = std::map, TransitionInfo>; + typedef std::map, const State *> TransitionMap; mutable TransitionMap Transitions; State(); @@ -228,14 +221,9 @@ class State { // PossibleStates is the set of valid resource states that ensue from valid // transitions. // - // TransitionInfo maps from a resource bitmask B in this state to a resource - // bitmask B' in PossibleStates. This is a one-to-many (or none) mapping. - // - void AddInsnClass( - std::vector &InsnClass, - std::map &ComboBitToBitsMap, - std::set &PossibleStates, - std::vector> &TransitionInfo) const; + void AddInsnClass(std::vector &InsnClass, + std::map &ComboBitToBitsMap, + std::set &PossibleStates) const; // // AddInsnClassStages - Return all combinations of resource reservation @@ -243,17 +231,16 @@ class State { // which are possible from this state (PossibleStates). // void AddInsnClassStages(std::vector &InsnClass, - std::map &ComboBitToBitsMap, - unsigned chkstage, unsigned numstages, - unsigned prevState, unsigned origState, - DenseSet &VisitedResourceStates) const; + std::map &ComboBitToBitsMap, + unsigned chkstage, unsigned numstages, + unsigned prevState, unsigned origState, + DenseSet &VisitedResourceStates, + std::set &PossibleStates) const; // - // addTransition - Add a transition from this state given the input InsnClass. + // addTransition - Add a transition from this state given the input InsnClass // - void addTransition( - std::vector InsnClass, const State *To, - const std::vector> &TransitionInfo) const; + void addTransition(std::vector InsnClass, const State *To) const; // // hasTransition - Returns true if there is a transition from this state @@ -342,12 +329,11 @@ State::State() : // // addTransition - Add a transition from this state given the input InsnClass // -void State::addTransition( - std::vector InsnClass, const State *To, - const std::vector> &TransitionInfo) const { +void State::addTransition(std::vector InsnClass, const State *To) + const { assert(!Transitions.count(InsnClass) && "Cannot have multiple transitions for the same input"); - Transitions[InsnClass] = {TransitionInfo, To}; + Transitions[InsnClass] = To; } // @@ -365,11 +351,9 @@ bool State::hasTransition(std::vector InsnClass) const { // PossibleStates is the set of valid resource states that ensue from valid // transitions. // -void State::AddInsnClass( - std::vector &InsnClass, - std::map &ComboBitToBitsMap, - std::set &PossibleStates, - std::vector> &TransitionInfo) const { +void State::AddInsnClass(std::vector &InsnClass, + std::map &ComboBitToBitsMap, + std::set &PossibleStates) const { // // Iterate over all resource states in currentState. // @@ -378,26 +362,25 @@ void State::AddInsnClass( for (std::set::iterator SI = stateInfo.begin(); SI != stateInfo.end(); ++SI) { - unsigned ThisState = *SI; + unsigned thisState = *SI; DenseSet VisitedResourceStates; - LLVM_DEBUG(dbgs() << " thisState: 0x" << Twine::utohexstr(ThisState) + LLVM_DEBUG(dbgs() << " thisState: 0x" << Twine::utohexstr(thisState) << "\n"); - AddInsnClassStages(InsnClass, ComboBitToBitsMap, numstages - 1, numstages, - ThisState, ThisState, VisitedResourceStates); - for (unsigned NewState : VisitedResourceStates) { - PossibleStates.insert(NewState); - TransitionInfo.emplace_back(ThisState, NewState); - } + AddInsnClassStages(InsnClass, ComboBitToBitsMap, + numstages - 1, numstages, + thisState, thisState, + VisitedResourceStates, PossibleStates); } } -void State::AddInsnClassStages( - std::vector &InsnClass, - std::map &ComboBitToBitsMap, unsigned chkstage, - unsigned numstages, unsigned prevState, unsigned origState, - DenseSet &VisitedResourceStates) const { +void State::AddInsnClassStages(std::vector &InsnClass, + std::map &ComboBitToBitsMap, + unsigned chkstage, unsigned numstages, + unsigned prevState, unsigned origState, + DenseSet &VisitedResourceStates, + std::set &PossibleStates) const { assert((chkstage < numstages) && "AddInsnClassStages: stage out of range"); unsigned thisStage = InsnClass[chkstage]; @@ -455,6 +438,7 @@ void State::AddInsnClassStages( if (ResultingResourceState != prevState) { if (VisitedResourceStates.count(ResultingResourceState) == 0) { VisitedResourceStates.insert(ResultingResourceState); + PossibleStates.insert(ResultingResourceState); LLVM_DEBUG(dbgs() << "\tResultingResourceState: 0x" << Twine::utohexstr(ResultingResourceState) << "\n"); @@ -472,9 +456,10 @@ void State::AddInsnClassStages( // if (ResultingResourceState != prevState) { LLVM_DEBUG(dbgs() << "\n"); - AddInsnClassStages(InsnClass, ComboBitToBitsMap, chkstage - 1, - numstages, ResultingResourceState, origState, - VisitedResourceStates); + AddInsnClassStages(InsnClass, ComboBitToBitsMap, + chkstage - 1, numstages, + ResultingResourceState, origState, + VisitedResourceStates, PossibleStates); } else { LLVM_DEBUG(dbgs() << "\tSkipped Add - no resources available\n"); } @@ -593,10 +578,17 @@ void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName, II = SI->Transitions.begin(), IE = SI->Transitions.end(); II != IE; ++II) { OS << "{0x" << Twine::utohexstr(getDFAInsnInput(II->first)) << ", " - << II->second.S->stateNum << "},\t"; + << II->second->stateNum << "},\t"; } ValidTransitions += SI->Transitions.size(); + // If there are no valid transitions from this stage, we need a sentinel + // transition. + if (ValidTransitions == StateEntry[i]) { + OS << SentinelEntry << ",\t"; + ++ValidTransitions; + } + OS << " // state " << i << ": " << StateEntry[i]; if (StateEntry[i] != (ValidTransitions-1)) { // More than one transition. OS << "-" << (ValidTransitions-1); @@ -618,6 +610,8 @@ void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName, OS << "// " << numStates << " states\n"; OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; + // Multiply i by 2 since each entry in DFAStateInputTable is a set of + // two numbers. unsigned lastState = 0; for (unsigned i = 0; i < numStates; ++i) { if (i && ((i % 10) == 0)) { @@ -626,44 +620,11 @@ void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName, } OS << StateEntry[i] << ", "; } + // Print out the index to the sentinel entry in StateInputTable OS << ValidTransitions << ", "; OS << " // states " << (lastState+1) << ":" << numStates << "\n"; OS << "};\n"; - - // Generate the resource transition table. - OS << "const std::pair " << TargetName - << "DFAResourceTransitionTable[] = { \n"; - int N = 0; - StateEntry.clear(); - for (const State &S : states) { - for (auto &KV : S.Transitions) { - StateEntry.push_back(N); - for (std::pair &T : KV.second.ResourceTransitions) { - OS << "{0x" << utohexstr(T.first) << ", 0x" << utohexstr(T.second) - << "}, "; - ++N; - } - } - OS << "\n "; - } - // Add a sentinel entry to terminate the search. - StateEntry.push_back(N); - OS << "\n {~0U,~0U}\n};\n\n"; - - OS << "// " << TargetName << "DFAResourceTransitionEntryTable[i] = " - << "Index of the first entry in DFAResourceTransitionTable for\n"; - OS << "// the ith transition.\n"; - OS << "const unsigned int " << TargetName - << "DFAResourceTransitionEntryTable[] = { \n"; - - N = 0; - for (int S : StateEntry) { - OS << S << ","; - if (N++ % 10 == 0) - OS << "\n "; - } - OS << "\n ~0U\n};\n"; } // @@ -985,9 +946,7 @@ void DFAPacketizerEmitter::emitForItineraries( if (!current->hasTransition(InsnClass) && current->canMaybeAddInsnClass(InsnClass, ComboBitToBitsMap)) { const State *NewState = nullptr; - std::vector> TransitionInfo; - current->AddInsnClass(InsnClass, ComboBitToBitsMap, NewStateResources, - TransitionInfo); + current->AddInsnClass(InsnClass, ComboBitToBitsMap, NewStateResources); if (NewStateResources.empty()) { LLVM_DEBUG(dbgs() << " Skipped - no new states generated\n"); continue; @@ -1023,7 +982,7 @@ void DFAPacketizerEmitter::emitForItineraries( }); } - current->addTransition(InsnClass, NewState, TransitionInfo); + current->addTransition(InsnClass, NewState); } } } @@ -1041,10 +1000,7 @@ void DFAPacketizerEmitter::emitForItineraries( << "DFAPacketizer(const InstrItineraryData *IID) const {\n" << " return new DFAPacketizer(IID, " << TargetName << DFAName << "DFAStateInputTable, " << TargetName << DFAName - << "DFAStateEntryTable, " << TargetName << DFAName - << "DFAResourceTransitionTable, " << TargetName << DFAName - << "DFAResourceTransitionEntryTable" - << ");\n}\n\n"; + << "DFAStateEntryTable);\n}\n\n"; } namespace llvm { -- 2.40.0