[DFAPacketizer] Reapply: Track resources for packetized instructions

Reapply with fix to reduce resources required by the compiler - use
unsigned[2] instead of std::pair. This causes clang and gcc to compile
the generated file multiple times faster, and hopefully will reduce
the resource requirements on Visual Studio also. This fix is a little
ugly but it's clearly the same issue the previous author of
DFAPacketizer faced (the previous tables use unsigned[2] rather uglily
too).

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

llvm-svn: 371399

1 files changed, 54 insertions, 11 deletions

diff --git a/llvm/lib/CodeGen/DFAPacketizer.cpp b/llvm/lib/CodeGen/DFAPacketizer.cpp
index b99be5d7a87..500ae68d007 100644
--- a/llvm/lib/CodeGen/DFAPacketizer.cpp
+++ b/llvm/lib/CodeGen/DFAPacketizer.cpp
@@ -23,6 +23,7 @@
 //===----------------------------------------------------------------------===//
 
 #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"
@@ -72,9 +73,11 @@ static DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
 // --------------------------------------------------------------------
 
 DFAPacketizer::DFAPacketizer(const InstrItineraryData *I,
-                             const DFAStateInput (*SIT)[2],
-                             const unsigned *SET):
-  InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET) {
+                             const DFAStateInput (*SIT)[2], const unsigned *SET,
+                             const unsigned (*RTT)[2],
+                             const unsigned *RTET)
+    : InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET),
+      DFAResourceTransitionTable(RTT), DFAResourceTransitionEntryTable(RTET) {
   // Make sure DFA types are large enough for the number of terms & resources.
   static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <=
                     (8 * sizeof(DFAInput)),
@@ -82,6 +85,7 @@ 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.
@@ -93,16 +97,26 @@ DFAPacketizer::DFAPacketizer(const InstrItineraryData *I,
 //                         for the ith state
 //
 void DFAPacketizer::ReadTable(unsigned int state) {
-  unsigned ThisState = DFAStateEntryTable[state];
-  unsigned NextStateInTable = DFAStateEntryTable[state+1];
+  unsigned ThisStateIdx = DFAStateEntryTable[state];
+  unsigned NextStateIdxInTable = DFAStateEntryTable[state + 1];
   // Early exit in case CachedTable has already contains this
   // state's transitions.
-  if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0])))
+  if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisStateIdx][0])))
     return;
 
-  for (unsigned i = ThisState; i < NextStateInTable; i++)
-    CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] =
-      DFAStateInputTable[i][1];
+  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]);
+    }
+  }
 }
 
 // Return the DFAInput for an instruction class.
@@ -141,6 +155,16 @@ void DFAPacketizer::reserveResources(const MCInstrDesc *MID) {
   DFAInput InsnInput = getInsnInput(InsnClass);
   UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
   ReadTable(CurrentState);
+
+  if (TrackResources) {
+    DenseMap<unsigned, SmallVector<unsigned, 8>> NewResourceStates;
+    for (const auto &KV : CachedResourceTransitions[StateTrans]) {
+      assert(ResourceStates.count(KV[0]));
+      NewResourceStates[KV[1]] = ResourceStates[KV[0]];
+      NewResourceStates[KV[1]].push_back(KV[1]);
+    }
+    ResourceStates = NewResourceStates;
+  }
   assert(CachedTable.count(StateTrans) != 0);
   CurrentState = CachedTable[StateTrans];
 }
@@ -159,6 +183,21 @@ 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<unsigned> &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
@@ -210,6 +249,7 @@ 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);
 }
 
@@ -224,8 +264,11 @@ void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB,
   LLVM_DEBUG({
     if (!CurrentPacketMIs.empty()) {
       dbgs() << "Finalizing packet:\n";
-      for (MachineInstr *MI : CurrentPacketMIs)
-        dbgs() << " * " << *MI;
+      unsigned Idx = 0;
+      for (MachineInstr *MI : CurrentPacketMIs) {
+        unsigned R = ResourceTracker->getUsedResources(Idx++);
+        dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;
+      }
     }
   });
   if (CurrentPacketMIs.size() > 1) {