• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //=- llvm/CodeGen/DFAPacketizer.cpp - DFA Packetizer for VLIW -*- C++ -*-=====//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 // This class implements a deterministic finite automaton (DFA) based
10 // packetizing mechanism for VLIW architectures. It provides APIs to
11 // determine whether there exists a legal mapping of instructions to
12 // functional unit assignments in a packet. The DFA is auto-generated from
13 // the target's Schedule.td file.
14 //
15 // A DFA consists of 3 major elements: states, inputs, and transitions. For
16 // the packetizing mechanism, the input is the set of instruction classes for
17 // a target. The state models all possible combinations of functional unit
18 // consumption for a given set of instructions in a packet. A transition
19 // models the addition of an instruction to a packet. In the DFA constructed
20 // by this class, if an instruction can be added to a packet, then a valid
21 // transition exists from the corresponding state. Invalid transitions
22 // indicate that the instruction cannot be added to the current packet.
23 //
24 //===----------------------------------------------------------------------===//
25 
26 #define DEBUG_TYPE "packets"
27 
28 #include "llvm/CodeGen/DFAPacketizer.h"
29 #include "llvm/CodeGen/MachineInstr.h"
30 #include "llvm/CodeGen/MachineInstrBundle.h"
31 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
32 #include "llvm/MC/MCInstrItineraries.h"
33 #include "llvm/Target/TargetInstrInfo.h"
34 
35 using namespace llvm;
36 
37 // --------------------------------------------------------------------
38 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
39 
40 namespace {
addDFAFuncUnits(DFAInput Inp,unsigned FuncUnits)41   DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
42     return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
43   }
44 
45   /// Return the DFAInput for an instruction class input vector.
46   /// This function is used in both DFAPacketizer.cpp and in
47   /// DFAPacketizerEmitter.cpp.
getDFAInsnInput(const std::vector<unsigned> & InsnClass)48   DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
49     DFAInput InsnInput = 0;
50     assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
51            "Exceeded maximum number of DFA terms");
52     for (auto U : InsnClass)
53       InsnInput = addDFAFuncUnits(InsnInput, U);
54     return InsnInput;
55   }
56 }
57 // --------------------------------------------------------------------
58 
DFAPacketizer(const InstrItineraryData * I,const DFAStateInput (* SIT)[2],const unsigned * SET)59 DFAPacketizer::DFAPacketizer(const InstrItineraryData *I,
60                              const DFAStateInput (*SIT)[2],
61                              const unsigned *SET):
62   InstrItins(I), CurrentState(0), DFAStateInputTable(SIT),
63   DFAStateEntryTable(SET) {
64   // Make sure DFA types are large enough for the number of terms & resources.
65   static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <=
66                     (8 * sizeof(DFAInput)),
67                 "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput");
68   static_assert(
69       (DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)),
70       "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput");
71 }
72 
73 
74 // Read the DFA transition table and update CachedTable.
75 //
76 // Format of the transition tables:
77 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
78 //                           transitions
79 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable
80 //                         for the ith state
81 //
ReadTable(unsigned int state)82 void DFAPacketizer::ReadTable(unsigned int state) {
83   unsigned ThisState = DFAStateEntryTable[state];
84   unsigned NextStateInTable = DFAStateEntryTable[state+1];
85   // Early exit in case CachedTable has already contains this
86   // state's transitions.
87   if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0])))
88     return;
89 
90   for (unsigned i = ThisState; i < NextStateInTable; i++)
91     CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] =
92       DFAStateInputTable[i][1];
93 }
94 
95 
96 // Return the DFAInput for an instruction class.
getInsnInput(unsigned InsnClass)97 DFAInput DFAPacketizer::getInsnInput(unsigned InsnClass) {
98   // Note: this logic must match that in DFAPacketizerDefs.h for input vectors.
99   DFAInput InsnInput = 0;
100   unsigned i = 0;
101   (void)i;
102   for (const InstrStage *IS = InstrItins->beginStage(InsnClass),
103        *IE = InstrItins->endStage(InsnClass); IS != IE; ++IS) {
104     InsnInput = addDFAFuncUnits(InsnInput, IS->getUnits());
105     assert((i++ < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs");
106   }
107   return InsnInput;
108 }
109 
110 
111 // Return the DFAInput for an instruction class input vector.
getInsnInput(const std::vector<unsigned> & InsnClass)112 DFAInput DFAPacketizer::getInsnInput(const std::vector<unsigned> &InsnClass) {
113   return getDFAInsnInput(InsnClass);
114 }
115 
116 
117 // Check if the resources occupied by a MCInstrDesc are available in the
118 // current state.
canReserveResources(const llvm::MCInstrDesc * MID)119 bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc *MID) {
120   unsigned InsnClass = MID->getSchedClass();
121   DFAInput InsnInput = getInsnInput(InsnClass);
122   UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
123   ReadTable(CurrentState);
124   return CachedTable.count(StateTrans) != 0;
125 }
126 
127 
128 // Reserve the resources occupied by a MCInstrDesc and change the current
129 // state to reflect that change.
reserveResources(const llvm::MCInstrDesc * MID)130 void DFAPacketizer::reserveResources(const llvm::MCInstrDesc *MID) {
131   unsigned InsnClass = MID->getSchedClass();
132   DFAInput InsnInput = getInsnInput(InsnClass);
133   UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
134   ReadTable(CurrentState);
135   assert(CachedTable.count(StateTrans) != 0);
136   CurrentState = CachedTable[StateTrans];
137 }
138 
139 
140 // Check if the resources occupied by a machine instruction are available
141 // in the current state.
canReserveResources(llvm::MachineInstr & MI)142 bool DFAPacketizer::canReserveResources(llvm::MachineInstr &MI) {
143   const llvm::MCInstrDesc &MID = MI.getDesc();
144   return canReserveResources(&MID);
145 }
146 
147 
148 // Reserve the resources occupied by a machine instruction and change the
149 // current state to reflect that change.
reserveResources(llvm::MachineInstr & MI)150 void DFAPacketizer::reserveResources(llvm::MachineInstr &MI) {
151   const llvm::MCInstrDesc &MID = MI.getDesc();
152   reserveResources(&MID);
153 }
154 
155 
156 namespace llvm {
157 // This class extends ScheduleDAGInstrs and overrides the schedule method
158 // to build the dependence graph.
159 class DefaultVLIWScheduler : public ScheduleDAGInstrs {
160 private:
161   AliasAnalysis *AA;
162   /// Ordered list of DAG postprocessing steps.
163   std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
164 public:
165   DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI,
166                        AliasAnalysis *AA);
167   // Actual scheduling work.
168   void schedule() override;
169 
170   /// DefaultVLIWScheduler takes ownership of the Mutation object.
addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation)171   void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
172     Mutations.push_back(std::move(Mutation));
173   }
174 protected:
175   void postprocessDAG();
176 };
177 }
178 
179 
DefaultVLIWScheduler(MachineFunction & MF,MachineLoopInfo & MLI,AliasAnalysis * AA)180 DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF,
181                                            MachineLoopInfo &MLI,
182                                            AliasAnalysis *AA)
183     : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
184   CanHandleTerminators = true;
185 }
186 
187 
188 /// Apply each ScheduleDAGMutation step in order.
postprocessDAG()189 void DefaultVLIWScheduler::postprocessDAG() {
190   for (auto &M : Mutations)
191     M->apply(this);
192 }
193 
194 
schedule()195 void DefaultVLIWScheduler::schedule() {
196   // Build the scheduling graph.
197   buildSchedGraph(AA);
198   postprocessDAG();
199 }
200 
201 
VLIWPacketizerList(MachineFunction & mf,MachineLoopInfo & mli,AliasAnalysis * aa)202 VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf,
203                                        MachineLoopInfo &mli, AliasAnalysis *aa)
204     : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
205   ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget());
206   VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA);
207 }
208 
209 
~VLIWPacketizerList()210 VLIWPacketizerList::~VLIWPacketizerList() {
211   if (VLIWScheduler)
212     delete VLIWScheduler;
213   if (ResourceTracker)
214     delete ResourceTracker;
215 }
216 
217 
218 // End the current packet, bundle packet instructions and reset DFA state.
endPacket(MachineBasicBlock * MBB,MachineBasicBlock::iterator MI)219 void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB,
220                                    MachineBasicBlock::iterator MI) {
221   if (CurrentPacketMIs.size() > 1) {
222     MachineInstr &MIFirst = *CurrentPacketMIs.front();
223     finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());
224   }
225   CurrentPacketMIs.clear();
226   ResourceTracker->clearResources();
227   DEBUG(dbgs() << "End packet\n");
228 }
229 
230 
231 // Bundle machine instructions into packets.
PacketizeMIs(MachineBasicBlock * MBB,MachineBasicBlock::iterator BeginItr,MachineBasicBlock::iterator EndItr)232 void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB,
233                                       MachineBasicBlock::iterator BeginItr,
234                                       MachineBasicBlock::iterator EndItr) {
235   assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
236   VLIWScheduler->startBlock(MBB);
237   VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,
238                              std::distance(BeginItr, EndItr));
239   VLIWScheduler->schedule();
240 
241   DEBUG({
242     dbgs() << "Scheduling DAG of the packetize region\n";
243     for (SUnit &SU : VLIWScheduler->SUnits)
244       SU.dumpAll(VLIWScheduler);
245   });
246 
247   // Generate MI -> SU map.
248   MIToSUnit.clear();
249   for (SUnit &SU : VLIWScheduler->SUnits)
250     MIToSUnit[SU.getInstr()] = &SU;
251 
252   // The main packetizer loop.
253   for (; BeginItr != EndItr; ++BeginItr) {
254     MachineInstr &MI = *BeginItr;
255     initPacketizerState();
256 
257     // End the current packet if needed.
258     if (isSoloInstruction(MI)) {
259       endPacket(MBB, MI);
260       continue;
261     }
262 
263     // Ignore pseudo instructions.
264     if (ignorePseudoInstruction(MI, MBB))
265       continue;
266 
267     SUnit *SUI = MIToSUnit[&MI];
268     assert(SUI && "Missing SUnit Info!");
269 
270     // Ask DFA if machine resource is available for MI.
271     DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);
272 
273     bool ResourceAvail = ResourceTracker->canReserveResources(MI);
274     DEBUG({
275       if (ResourceAvail)
276         dbgs() << "  Resources are available for adding MI to packet\n";
277       else
278         dbgs() << "  Resources NOT available\n";
279     });
280     if (ResourceAvail && shouldAddToPacket(MI)) {
281       // Dependency check for MI with instructions in CurrentPacketMIs.
282       for (auto MJ : CurrentPacketMIs) {
283         SUnit *SUJ = MIToSUnit[MJ];
284         assert(SUJ && "Missing SUnit Info!");
285 
286         DEBUG(dbgs() << "  Checking against MJ " << *MJ);
287         // Is it legal to packetize SUI and SUJ together.
288         if (!isLegalToPacketizeTogether(SUI, SUJ)) {
289           DEBUG(dbgs() << "  Not legal to add MI, try to prune\n");
290           // Allow packetization if dependency can be pruned.
291           if (!isLegalToPruneDependencies(SUI, SUJ)) {
292             // End the packet if dependency cannot be pruned.
293             DEBUG(dbgs() << "  Could not prune dependencies for adding MI\n");
294             endPacket(MBB, MI);
295             break;
296           }
297           DEBUG(dbgs() << "  Pruned dependence for adding MI\n");
298         }
299       }
300     } else {
301       DEBUG(if (ResourceAvail)
302         dbgs() << "Resources are available, but instruction should not be "
303                   "added to packet\n  " << MI);
304       // End the packet if resource is not available, or if the instruction
305       // shoud not be added to the current packet.
306       endPacket(MBB, MI);
307     }
308 
309     // Add MI to the current packet.
310     DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');
311     BeginItr = addToPacket(MI);
312   } // For all instructions in the packetization range.
313 
314   // End any packet left behind.
315   endPacket(MBB, EndItr);
316   VLIWScheduler->exitRegion();
317   VLIWScheduler->finishBlock();
318 }
319 
320 
321 // Add a DAG mutation object to the ordered list.
addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation)322 void VLIWPacketizerList::addMutation(
323       std::unique_ptr<ScheduleDAGMutation> Mutation) {
324   VLIWScheduler->addMutation(std::move(Mutation));
325 }
326