LLVM  6.0.0svn
DFAPacketizer.cpp
Go to the documentation of this file.
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 
34 #include "llvm/MC/MCInstrDesc.h"
37 #include "llvm/Support/Debug.h"
39 #include <algorithm>
40 #include <cassert>
41 #include <iterator>
42 #include <memory>
43 #include <vector>
44 
45 using namespace llvm;
46 
47 #define DEBUG_TYPE "packets"
48 
49 static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden,
50  cl::init(0), cl::desc("If present, stops packetizing after N instructions"));
51 
52 static unsigned InstrCount = 0;
53 
54 // --------------------------------------------------------------------
55 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
56 
57 static DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
58  return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
59 }
60 
61 /// Return the DFAInput for an instruction class input vector.
62 /// This function is used in both DFAPacketizer.cpp and in
63 /// DFAPacketizerEmitter.cpp.
64 static DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
65  DFAInput InsnInput = 0;
66  assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
67  "Exceeded maximum number of DFA terms");
68  for (auto U : InsnClass)
69  InsnInput = addDFAFuncUnits(InsnInput, U);
70  return InsnInput;
71 }
72 
73 // --------------------------------------------------------------------
74 
76  const DFAStateInput (*SIT)[2],
77  const unsigned *SET):
78  InstrItins(I), DFAStateInputTable(SIT), DFAStateEntryTable(SET) {
79  // Make sure DFA types are large enough for the number of terms & resources.
80  static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <=
81  (8 * sizeof(DFAInput)),
82  "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput");
83  static_assert(
84  (DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)),
85  "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput");
86 }
87 
88 // Read the DFA transition table and update CachedTable.
89 //
90 // Format of the transition tables:
91 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid
92 // transitions
93 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable
94 // for the ith state
95 //
96 void DFAPacketizer::ReadTable(unsigned int state) {
97  unsigned ThisState = DFAStateEntryTable[state];
98  unsigned NextStateInTable = DFAStateEntryTable[state+1];
99  // Early exit in case CachedTable has already contains this
100  // state's transitions.
101  if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0])))
102  return;
103 
104  for (unsigned i = ThisState; i < NextStateInTable; i++)
105  CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] =
106  DFAStateInputTable[i][1];
107 }
108 
109 // Return the DFAInput for an instruction class.
111  // Note: this logic must match that in DFAPacketizerDefs.h for input vectors.
112  DFAInput InsnInput = 0;
113  unsigned i = 0;
114  (void)i;
115  for (const InstrStage *IS = InstrItins->beginStage(InsnClass),
116  *IE = InstrItins->endStage(InsnClass); IS != IE; ++IS) {
117  InsnInput = addDFAFuncUnits(InsnInput, IS->getUnits());
118  assert((i++ < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs");
119  }
120  return InsnInput;
121 }
122 
123 // Return the DFAInput for an instruction class input vector.
124 DFAInput DFAPacketizer::getInsnInput(const std::vector<unsigned> &InsnClass) {
125  return getDFAInsnInput(InsnClass);
126 }
127 
128 // Check if the resources occupied by a MCInstrDesc are available in the
129 // current state.
131  unsigned InsnClass = MID->getSchedClass();
132  DFAInput InsnInput = getInsnInput(InsnClass);
133  UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
134  ReadTable(CurrentState);
135  return CachedTable.count(StateTrans) != 0;
136 }
137 
138 // Reserve the resources occupied by a MCInstrDesc and change the current
139 // state to reflect that change.
141  unsigned InsnClass = MID->getSchedClass();
142  DFAInput InsnInput = getInsnInput(InsnClass);
143  UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput);
144  ReadTable(CurrentState);
145  assert(CachedTable.count(StateTrans) != 0);
146  CurrentState = CachedTable[StateTrans];
147 }
148 
149 // Check if the resources occupied by a machine instruction are available
150 // in the current state.
152  const MCInstrDesc &MID = MI.getDesc();
153  return canReserveResources(&MID);
154 }
155 
156 // Reserve the resources occupied by a machine instruction and change the
157 // current state to reflect that change.
159  const MCInstrDesc &MID = MI.getDesc();
160  reserveResources(&MID);
161 }
162 
163 namespace llvm {
164 
165 // This class extends ScheduleDAGInstrs and overrides the schedule method
166 // to build the dependence graph.
168 private:
169  AliasAnalysis *AA;
170  /// Ordered list of DAG postprocessing steps.
171  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
172 
173 public:
175  AliasAnalysis *AA);
176 
177  // Actual scheduling work.
178  void schedule() override;
179 
180  /// DefaultVLIWScheduler takes ownership of the Mutation object.
181  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
182  Mutations.push_back(std::move(Mutation));
183  }
184 
185 protected:
186  void postprocessDAG();
187 };
188 
189 } // end namespace llvm
190 
192  MachineLoopInfo &MLI,
193  AliasAnalysis *AA)
194  : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
195  CanHandleTerminators = true;
196 }
197 
198 /// Apply each ScheduleDAGMutation step in order.
200  for (auto &M : Mutations)
201  M->apply(this);
202 }
203 
205  // Build the scheduling graph.
206  buildSchedGraph(AA);
207  postprocessDAG();
208 }
209 
212  : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
215 }
216 
218  delete VLIWScheduler;
219  delete ResourceTracker;
220 }
221 
222 // End the current packet, bundle packet instructions and reset DFA state.
225  DEBUG({
226  if (!CurrentPacketMIs.empty()) {
227  dbgs() << "Finalizing packet:\n";
228  for (MachineInstr *MI : CurrentPacketMIs)
229  dbgs() << " * " << *MI;
230  }
231  });
232  if (CurrentPacketMIs.size() > 1) {
233  MachineInstr &MIFirst = *CurrentPacketMIs.front();
234  finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());
235  }
236  CurrentPacketMIs.clear();
238  DEBUG(dbgs() << "End packet\n");
239 }
240 
241 // Bundle machine instructions into packets.
245  assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
247  VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,
248  std::distance(BeginItr, EndItr));
250 
251  DEBUG({
252  dbgs() << "Scheduling DAG of the packetize region\n";
253  for (SUnit &SU : VLIWScheduler->SUnits)
255  });
256 
257  // Generate MI -> SU map.
258  MIToSUnit.clear();
259  for (SUnit &SU : VLIWScheduler->SUnits)
260  MIToSUnit[SU.getInstr()] = &SU;
261 
262  bool LimitPresent = InstrLimit.getPosition();
263 
264  // The main packetizer loop.
265  for (; BeginItr != EndItr; ++BeginItr) {
266  if (LimitPresent) {
267  if (InstrCount >= InstrLimit) {
268  EndItr = BeginItr;
269  break;
270  }
271  InstrCount++;
272  }
273  MachineInstr &MI = *BeginItr;
275 
276  // End the current packet if needed.
277  if (isSoloInstruction(MI)) {
278  endPacket(MBB, MI);
279  continue;
280  }
281 
282  // Ignore pseudo instructions.
283  if (ignorePseudoInstruction(MI, MBB))
284  continue;
285 
286  SUnit *SUI = MIToSUnit[&MI];
287  assert(SUI && "Missing SUnit Info!");
288 
289  // Ask DFA if machine resource is available for MI.
290  DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);
291 
292  bool ResourceAvail = ResourceTracker->canReserveResources(MI);
293  DEBUG({
294  if (ResourceAvail)
295  dbgs() << " Resources are available for adding MI to packet\n";
296  else
297  dbgs() << " Resources NOT available\n";
298  });
299  if (ResourceAvail && shouldAddToPacket(MI)) {
300  // Dependency check for MI with instructions in CurrentPacketMIs.
301  for (auto MJ : CurrentPacketMIs) {
302  SUnit *SUJ = MIToSUnit[MJ];
303  assert(SUJ && "Missing SUnit Info!");
304 
305  DEBUG(dbgs() << " Checking against MJ " << *MJ);
306  // Is it legal to packetize SUI and SUJ together.
307  if (!isLegalToPacketizeTogether(SUI, SUJ)) {
308  DEBUG(dbgs() << " Not legal to add MI, try to prune\n");
309  // Allow packetization if dependency can be pruned.
310  if (!isLegalToPruneDependencies(SUI, SUJ)) {
311  // End the packet if dependency cannot be pruned.
312  DEBUG(dbgs() << " Could not prune dependencies for adding MI\n");
313  endPacket(MBB, MI);
314  break;
315  }
316  DEBUG(dbgs() << " Pruned dependence for adding MI\n");
317  }
318  }
319  } else {
320  DEBUG(if (ResourceAvail)
321  dbgs() << "Resources are available, but instruction should not be "
322  "added to packet\n " << MI);
323  // End the packet if resource is not available, or if the instruction
324  // shoud not be added to the current packet.
325  endPacket(MBB, MI);
326  }
327 
328  // Add MI to the current packet.
329  DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');
330  BeginItr = addToPacket(MI);
331  } // For all instructions in the packetization range.
332 
333  // End any packet left behind.
334  endPacket(MBB, EndItr);
337 }
338 
340  const MachineMemOperand &Op2,
341  bool UseTBAA) const {
342  if (!Op1.getValue() || !Op2.getValue())
343  return true;
344 
345  int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
346  int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset;
347  int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset;
348 
349  AliasResult AAResult =
350  AA->alias(MemoryLocation(Op1.getValue(), Overlapa,
351  UseTBAA ? Op1.getAAInfo() : AAMDNodes()),
352  MemoryLocation(Op2.getValue(), Overlapb,
353  UseTBAA ? Op2.getAAInfo() : AAMDNodes()));
354 
355  return AAResult != NoAlias;
356 }
357 
359  const MachineInstr &MI2,
360  bool UseTBAA) const {
361  if (MI1.memoperands_empty() || MI2.memoperands_empty())
362  return true;
363 
364  for (const MachineMemOperand *Op1 : MI1.memoperands())
365  for (const MachineMemOperand *Op2 : MI2.memoperands())
366  if (alias(*Op1, *Op2, UseTBAA))
367  return true;
368  return false;
369 }
370 
371 // Add a DAG mutation object to the ordered list.
373  std::unique_ptr<ScheduleDAGMutation> Mutation) {
374  VLIWScheduler->addMutation(std::move(Mutation));
375 }
std::vector< MachineInstr * > CurrentPacketMIs
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
virtual void finishBlock()
Cleans up after scheduling in the given block.
virtual void initPacketizerState()
static DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits)
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
const InstrStage * beginStage(unsigned ItinClassIndx) const
Return the first stage of the itinerary.
DFAInput getInsnInput(unsigned InsnClass)
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
uint64_t getSize() const
Return the size in bytes of the memory reference.
virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ)
The two locations do not alias at all.
Definition: AliasAnalysis.h:85
virtual bool ignorePseudoInstruction(const MachineInstr &I, const MachineBasicBlock *MBB)
static unsigned InstrCount
iterator_range< mmo_iterator > memoperands()
Definition: MachineInstr.h:396
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
int64_t DFAStateInput
Definition: DFAPacketizer.h:73
void schedule() override
Orders nodes according to selected style.
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:570
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
AAMDNodes getAAInfo() const
Return the AA tags for the memory reference.
void buildSchedGraph(AliasAnalysis *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
std::map< MachineInstr *, SUnit * > MIToSUnit
A description of a memory reference used in the backend.
bool alias(const MachineInstr &MI1, const MachineInstr &MI2, bool UseTBAA=true) const
void postprocessDAG()
Apply each ScheduleDAGMutation step in order.
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
virtual void endPacket(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI)
uint64_t DFAInput
Definition: DFAPacketizer.h:72
MachineFunction & MF
PowerPC VSX FMA Mutation
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:287
DFAPacketizer * ResourceTracker
virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI)
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
DefaultVLIWScheduler takes ownership of the Mutation object.
Itinerary data supplied by a subtarget to be used by a target.
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the DAG and common scheduler state for a new scheduling region.
DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA)
const Value * getValue() const
Return the base address of the memory access.
unsigned getSchedClass() const
Return the scheduling class for this instruction.
Definition: MCInstrDesc.h:565
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:378
#define SET(n)
Definition: MD5.cpp:68
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
#define DFA_MAX_RESOURCES
Definition: DFAPacketizer.h:70
virtual bool shouldAddToPacket(const MachineInstr &MI)
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:79
virtual bool isSoloInstruction(const MachineInstr &MI)
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
self_iterator getIterator()
Definition: ilist_node.h:82
Representation for a specific memory location.
const TargetInstrInfo * TII
bool canReserveResources(const MCInstrDesc *MID)
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:642
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static DFAInput getDFAInsnInput(const std::vector< unsigned > &InsnClass)
Return the DFAInput for an instruction class input vector.
virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ)
A ScheduleDAG for scheduling lists of MachineInstr.
Representation of each machine instruction.
Definition: MachineInstr.h:59
static cl::opt< bool > UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"))
These values represent a non-pipelined step in the execution of an instruction.
const InstrStage * endStage(unsigned ItinClassIndx) const
Return the last+1 stage of the itinerary.
#define I(x, y, z)
Definition: MD5.cpp:58
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:568
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
Definition: DenseMap.h:141
static cl::opt< unsigned > InstrLimit("dfa-instr-limit", cl::Hidden, cl::init(0), cl::desc("If present, stops packetizing after N instructions"))
#define DFA_MAX_RESTERMS
Definition: DFAPacketizer.h:69
bool memoperands_empty() const
Return true if we don&#39;t have any memory operands which described the the memory access done by this i...
Definition: MachineInstr.h:394
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
int64_t getOffset() const
For normal values, this is a byte offset added to the base address.
VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI, AliasAnalysis *AA)
#define DEBUG(X)
Definition: Debug.h:118
IRTranslator LLVM IR MI
void dumpAll(const ScheduleDAG *G) const
DFAPacketizer(const InstrItineraryData *I, const DFAStateInput(*SIT)[2], const unsigned *SET)
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:572
void finalizeBundle(MachineBasicBlock &MBB, MachineBasicBlock::instr_iterator FirstMI, MachineBasicBlock::instr_iterator LastMI)
finalizeBundle - Finalize a machine instruction bundle which includes a sequence of instructions star...
void PacketizeMIs(MachineBasicBlock *MBB, MachineBasicBlock::iterator BeginItr, MachineBasicBlock::iterator EndItr)
DefaultVLIWScheduler * VLIWScheduler
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:247
void reserveResources(const MCInstrDesc *MID)