LLVM  10.0.0svn
DFAPacketizer.cpp
Go to the documentation of this file.
1 //=- llvm/CodeGen/DFAPacketizer.cpp - DFA Packetizer for VLIW -*- C++ -*-=====//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 // This class implements a deterministic finite automaton (DFA) based
9 // packetizing mechanism for VLIW architectures. It provides APIs to
10 // determine whether there exists a legal mapping of instructions to
11 // functional unit assignments in a packet. The DFA is auto-generated from
12 // the target's Schedule.td file.
13 //
14 // A DFA consists of 3 major elements: states, inputs, and transitions. For
15 // the packetizing mechanism, the input is the set of instruction classes for
16 // a target. The state models all possible combinations of functional unit
17 // consumption for a given set of instructions in a packet. A transition
18 // models the addition of an instruction to a packet. In the DFA constructed
19 // by this class, if an instruction can be added to a packet, then a valid
20 // transition exists from the corresponding state. Invalid transitions
21 // indicate that the instruction cannot be added to the current packet.
22 //
23 //===----------------------------------------------------------------------===//
24 
26 #include "llvm/ADT/StringExtras.h"
35 #include "llvm/MC/MCInstrDesc.h"
38 #include "llvm/Support/Debug.h"
40 #include <algorithm>
41 #include <cassert>
42 #include <iterator>
43 #include <memory>
44 #include <vector>
45 
46 using namespace llvm;
47 
48 #define DEBUG_TYPE "packets"
49 
50 static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden,
51  cl::init(0), cl::desc("If present, stops packetizing after N instructions"));
52 
53 static unsigned InstrCount = 0;
54 
55 // --------------------------------------------------------------------
56 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
57 
58 static DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) {
59  return (Inp << DFA_MAX_RESOURCES) | FuncUnits;
60 }
61 
62 /// Return the DFAInput for an instruction class input vector.
63 /// This function is used in both DFAPacketizer.cpp and in
64 /// DFAPacketizerEmitter.cpp.
65 static DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) {
66  DFAInput InsnInput = 0;
67  assert((InsnClass.size() <= DFA_MAX_RESTERMS) &&
68  "Exceeded maximum number of DFA terms");
69  for (auto U : InsnClass)
70  InsnInput = addDFAFuncUnits(InsnInput, U);
71  return InsnInput;
72 }
73 
74 // --------------------------------------------------------------------
75 
76 // Make sure DFA types are large enough for the number of terms & resources.
77 static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <=
78  (8 * sizeof(DFAInput)),
79  "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput");
80 static_assert(
81  (DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)),
82  "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput");
83 
84 // Return the DFAInput for an instruction class.
86  // Note: this logic must match that in DFAPacketizerDefs.h for input vectors.
87  DFAInput InsnInput = 0;
88  unsigned i = 0;
89  (void)i;
90  for (const InstrStage *IS = InstrItins->beginStage(InsnClass),
91  *IE = InstrItins->endStage(InsnClass); IS != IE; ++IS) {
92  InsnInput = addDFAFuncUnits(InsnInput, IS->getUnits());
93  assert((i++ < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs");
94  }
95  return InsnInput;
96 }
97 
98 // Return the DFAInput for an instruction class input vector.
99 DFAInput DFAPacketizer::getInsnInput(const std::vector<unsigned> &InsnClass) {
100  return getDFAInsnInput(InsnClass);
101 }
102 
103 // Check if the resources occupied by a MCInstrDesc are available in the
104 // current state.
106  unsigned InsnClass = MID->getSchedClass();
107  DFAInput InsnInput = getInsnInput(InsnClass);
108  return A.canAdd(InsnInput);
109 }
110 
111 // Reserve the resources occupied by a MCInstrDesc and change the current
112 // state to reflect that change.
114  unsigned InsnClass = MID->getSchedClass();
115  DFAInput InsnInput = getInsnInput(InsnClass);
116  A.add(InsnInput);
117 }
118 
119 // Check if the resources occupied by a machine instruction are available
120 // in the current state.
122  const MCInstrDesc &MID = MI.getDesc();
123  return canReserveResources(&MID);
124 }
125 
126 // Reserve the resources occupied by a machine instruction and change the
127 // current state to reflect that change.
129  const MCInstrDesc &MID = MI.getDesc();
130  reserveResources(&MID);
131 }
132 
133 unsigned DFAPacketizer::getUsedResources(unsigned InstIdx) {
134  ArrayRef<NfaPath> NfaPaths = A.getNfaPaths();
135  assert(!NfaPaths.empty() && "Invalid bundle!");
136  const NfaPath &RS = NfaPaths.front();
137 
138  // RS stores the cumulative resources used up to and including the I'th
139  // instruction. The 0th instruction is the base case.
140  if (InstIdx == 0)
141  return RS[0];
142  // Return the difference between the cumulative resources used by InstIdx and
143  // its predecessor.
144  return RS[InstIdx] ^ RS[InstIdx - 1];
145 }
146 
147 namespace llvm {
148 
149 // This class extends ScheduleDAGInstrs and overrides the schedule method
150 // to build the dependence graph.
152 private:
153  AAResults *AA;
154  /// Ordered list of DAG postprocessing steps.
155  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
156 
157 public:
159  AAResults *AA);
160 
161  // Actual scheduling work.
162  void schedule() override;
163 
164  /// DefaultVLIWScheduler takes ownership of the Mutation object.
165  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
166  Mutations.push_back(std::move(Mutation));
167  }
168 
169 protected:
170  void postprocessDAG();
171 };
172 
173 } // end namespace llvm
174 
176  MachineLoopInfo &MLI,
177  AAResults *AA)
178  : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
179  CanHandleTerminators = true;
180 }
181 
182 /// Apply each ScheduleDAGMutation step in order.
184  for (auto &M : Mutations)
185  M->apply(this);
186 }
187 
189  // Build the scheduling graph.
190  buildSchedGraph(AA);
191  postprocessDAG();
192 }
193 
196  : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
200 }
201 
203  delete VLIWScheduler;
204  delete ResourceTracker;
205 }
206 
207 // End the current packet, bundle packet instructions and reset DFA state.
210  LLVM_DEBUG({
211  if (!CurrentPacketMIs.empty()) {
212  dbgs() << "Finalizing packet:\n";
213  unsigned Idx = 0;
214  for (MachineInstr *MI : CurrentPacketMIs) {
215  unsigned R = ResourceTracker->getUsedResources(Idx++);
216  dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;
217  }
218  }
219  });
220  if (CurrentPacketMIs.size() > 1) {
221  MachineInstr &MIFirst = *CurrentPacketMIs.front();
222  finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());
223  }
224  CurrentPacketMIs.clear();
226  LLVM_DEBUG(dbgs() << "End packet\n");
227 }
228 
229 // Bundle machine instructions into packets.
233  assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
235  VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,
236  std::distance(BeginItr, EndItr));
238 
239  LLVM_DEBUG({
240  dbgs() << "Scheduling DAG of the packetize region\n";
241  VLIWScheduler->dump();
242  });
243 
244  // Generate MI -> SU map.
245  MIToSUnit.clear();
246  for (SUnit &SU : VLIWScheduler->SUnits)
247  MIToSUnit[SU.getInstr()] = &SU;
248 
249  bool LimitPresent = InstrLimit.getPosition();
250 
251  // The main packetizer loop.
252  for (; BeginItr != EndItr; ++BeginItr) {
253  if (LimitPresent) {
254  if (InstrCount >= InstrLimit) {
255  EndItr = BeginItr;
256  break;
257  }
258  InstrCount++;
259  }
260  MachineInstr &MI = *BeginItr;
262 
263  // End the current packet if needed.
264  if (isSoloInstruction(MI)) {
265  endPacket(MBB, MI);
266  continue;
267  }
268 
269  // Ignore pseudo instructions.
270  if (ignorePseudoInstruction(MI, MBB))
271  continue;
272 
273  SUnit *SUI = MIToSUnit[&MI];
274  assert(SUI && "Missing SUnit Info!");
275 
276  // Ask DFA if machine resource is available for MI.
277  LLVM_DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);
278 
279  bool ResourceAvail = ResourceTracker->canReserveResources(MI);
280  LLVM_DEBUG({
281  if (ResourceAvail)
282  dbgs() << " Resources are available for adding MI to packet\n";
283  else
284  dbgs() << " Resources NOT available\n";
285  });
286  if (ResourceAvail && shouldAddToPacket(MI)) {
287  // Dependency check for MI with instructions in CurrentPacketMIs.
288  for (auto MJ : CurrentPacketMIs) {
289  SUnit *SUJ = MIToSUnit[MJ];
290  assert(SUJ && "Missing SUnit Info!");
291 
292  LLVM_DEBUG(dbgs() << " Checking against MJ " << *MJ);
293  // Is it legal to packetize SUI and SUJ together.
294  if (!isLegalToPacketizeTogether(SUI, SUJ)) {
295  LLVM_DEBUG(dbgs() << " Not legal to add MI, try to prune\n");
296  // Allow packetization if dependency can be pruned.
297  if (!isLegalToPruneDependencies(SUI, SUJ)) {
298  // End the packet if dependency cannot be pruned.
299  LLVM_DEBUG(dbgs()
300  << " Could not prune dependencies for adding MI\n");
301  endPacket(MBB, MI);
302  break;
303  }
304  LLVM_DEBUG(dbgs() << " Pruned dependence for adding MI\n");
305  }
306  }
307  } else {
308  LLVM_DEBUG(if (ResourceAvail) dbgs()
309  << "Resources are available, but instruction should not be "
310  "added to packet\n "
311  << MI);
312  // End the packet if resource is not available, or if the instruction
313  // shoud not be added to the current packet.
314  endPacket(MBB, MI);
315  }
316 
317  // Add MI to the current packet.
318  LLVM_DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');
319  BeginItr = addToPacket(MI);
320  } // For all instructions in the packetization range.
321 
322  // End any packet left behind.
323  endPacket(MBB, EndItr);
326 }
327 
329  const MachineMemOperand &Op2,
330  bool UseTBAA) const {
331  if (!Op1.getValue() || !Op2.getValue())
332  return true;
333 
334  int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
335  int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset;
336  int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset;
337 
338  AliasResult AAResult =
339  AA->alias(MemoryLocation(Op1.getValue(), Overlapa,
340  UseTBAA ? Op1.getAAInfo() : AAMDNodes()),
341  MemoryLocation(Op2.getValue(), Overlapb,
342  UseTBAA ? Op2.getAAInfo() : AAMDNodes()));
343 
344  return AAResult != NoAlias;
345 }
346 
348  const MachineInstr &MI2,
349  bool UseTBAA) const {
350  if (MI1.memoperands_empty() || MI2.memoperands_empty())
351  return true;
352 
353  for (const MachineMemOperand *Op1 : MI1.memoperands())
354  for (const MachineMemOperand *Op2 : MI2.memoperands())
355  if (alias(*Op1, *Op2, UseTBAA))
356  return true;
357  return false;
358 }
359 
360 // Add a DAG mutation object to the ordered list.
362  std::unique_ptr<ScheduleDAGMutation> Mutation) {
363  VLIWScheduler->addMutation(std::move(Mutation));
364 }
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:151
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)
void dump() const override
This class represents lattice values for constants.
Definition: AllocatorList.h:23
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:179
void setTrackResources(bool Track)
Definition: DFAPacketizer.h:98
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
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)
VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI, AAResults *AA)
virtual bool ignorePseudoInstruction(const MachineInstr &I, const MachineBasicBlock *MBB)
static unsigned InstrCount
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:560
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.
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
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
MachineFunction & MF
PowerPC VSX FMA Mutation
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:407
DFAPacketizer * ResourceTracker
virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI)
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
DefaultVLIWScheduler takes ownership of the Mutation object.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
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.
bool add(const ActionT &A)
Transition the automaton based on input symbol A.
Definition: Automaton.h:225
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
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:601
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:533
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, AAResults *AA)
#define DFA_MAX_RESOURCES
Definition: DFAPacketizer.h:70
virtual bool shouldAddToPacket(const MachineInstr &MI)
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:81
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:643
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
ArrayRef< NfaPath > getNfaPaths()
Obtain a set of possible paths through the input nondeterministic automaton that could be obtained fr...
Definition: Automaton.h:244
static DFAInput getDFAInsnInput(const std::vector< unsigned > &InsnClass)
Return the DFAInput for an instruction class input vector.
virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ)
bool canAdd(const ActionT &A)
Return true if the automaton can be transitioned based on input symbol A.
Definition: Automaton.h:236
A ScheduleDAG for scheduling lists of MachineInstr.
Representation of each machine instruction.
Definition: MachineInstr.h:63
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.
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:558
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 memory access done by this instr...
Definition: MachineInstr.h:563
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
int64_t getOffset() const
For normal values, this is a byte offset added to the base address.
IRTranslator LLVM IR MI
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:562
#define LLVM_DEBUG(X)
Definition: Debug.h:122
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...
unsigned getUsedResources(unsigned InstIdx)
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:242
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:143
std::string utohexstr(uint64_t X, bool LowerCase=false)
Definition: StringExtras.h:124
void reserveResources(const MCInstrDesc *MID)