LLVM  14.0.0git
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 // Check if the resources occupied by a MCInstrDesc are available in the
56 // current state.
58  unsigned Action = ItinActions[MID->getSchedClass()];
59  if (MID->getSchedClass() == 0 || Action == 0)
60  return false;
61  return A.canAdd(Action);
62 }
63 
64 // Reserve the resources occupied by a MCInstrDesc and change the current
65 // state to reflect that change.
67  unsigned Action = ItinActions[MID->getSchedClass()];
68  if (MID->getSchedClass() == 0 || Action == 0)
69  return;
70  A.add(Action);
71 }
72 
73 // Check if the resources occupied by a machine instruction are available
74 // in the current state.
76  const MCInstrDesc &MID = MI.getDesc();
77  return canReserveResources(&MID);
78 }
79 
80 // Reserve the resources occupied by a machine instruction and change the
81 // current state to reflect that change.
83  const MCInstrDesc &MID = MI.getDesc();
84  reserveResources(&MID);
85 }
86 
87 unsigned DFAPacketizer::getUsedResources(unsigned InstIdx) {
88  ArrayRef<NfaPath> NfaPaths = A.getNfaPaths();
89  assert(!NfaPaths.empty() && "Invalid bundle!");
90  const NfaPath &RS = NfaPaths.front();
91 
92  // RS stores the cumulative resources used up to and including the I'th
93  // instruction. The 0th instruction is the base case.
94  if (InstIdx == 0)
95  return RS[0];
96  // Return the difference between the cumulative resources used by InstIdx and
97  // its predecessor.
98  return RS[InstIdx] ^ RS[InstIdx - 1];
99 }
100 
101 namespace llvm {
102 
103 // This class extends ScheduleDAGInstrs and overrides the schedule method
104 // to build the dependence graph.
106 private:
107  AAResults *AA;
108  /// Ordered list of DAG postprocessing steps.
109  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
110 
111 public:
113  AAResults *AA);
114 
115  // Actual scheduling work.
116  void schedule() override;
117 
118  /// DefaultVLIWScheduler takes ownership of the Mutation object.
119  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
120  Mutations.push_back(std::move(Mutation));
121  }
122 
123 protected:
124  void postprocessDAG();
125 };
126 
127 } // end namespace llvm
128 
130  MachineLoopInfo &MLI,
131  AAResults *AA)
132  : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
133  CanHandleTerminators = true;
134 }
135 
136 /// Apply each ScheduleDAGMutation step in order.
138  for (auto &M : Mutations)
139  M->apply(this);
140 }
141 
143  // Build the scheduling graph.
144  buildSchedGraph(AA);
145  postprocessDAG();
146 }
147 
150  : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
154 }
155 
157  delete VLIWScheduler;
158  delete ResourceTracker;
159 }
160 
161 // End the current packet, bundle packet instructions and reset DFA state.
164  LLVM_DEBUG({
165  if (!CurrentPacketMIs.empty()) {
166  dbgs() << "Finalizing packet:\n";
167  unsigned Idx = 0;
168  for (MachineInstr *MI : CurrentPacketMIs) {
169  unsigned R = ResourceTracker->getUsedResources(Idx++);
170  dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;
171  }
172  }
173  });
174  if (CurrentPacketMIs.size() > 1) {
175  MachineInstr &MIFirst = *CurrentPacketMIs.front();
176  finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());
177  }
178  CurrentPacketMIs.clear();
179  ResourceTracker->clearResources();
180  LLVM_DEBUG(dbgs() << "End packet\n");
181 }
182 
183 // Bundle machine instructions into packets.
184 void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB,
187  assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
189  VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,
190  std::distance(BeginItr, EndItr));
192 
193  LLVM_DEBUG({
194  dbgs() << "Scheduling DAG of the packetize region\n";
195  VLIWScheduler->dump();
196  });
197 
198  // Generate MI -> SU map.
199  MIToSUnit.clear();
200  for (SUnit &SU : VLIWScheduler->SUnits)
201  MIToSUnit[SU.getInstr()] = &SU;
202 
203  bool LimitPresent = InstrLimit.getPosition();
204 
205  // The main packetizer loop.
206  for (; BeginItr != EndItr; ++BeginItr) {
207  if (LimitPresent) {
208  if (InstrCount >= InstrLimit) {
209  EndItr = BeginItr;
210  break;
211  }
212  InstrCount++;
213  }
214  MachineInstr &MI = *BeginItr;
216 
217  // End the current packet if needed.
218  if (isSoloInstruction(MI)) {
219  endPacket(MBB, MI);
220  continue;
221  }
222 
223  // Ignore pseudo instructions.
225  continue;
226 
227  SUnit *SUI = MIToSUnit[&MI];
228  assert(SUI && "Missing SUnit Info!");
229 
230  // Ask DFA if machine resource is available for MI.
231  LLVM_DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);
232 
233  bool ResourceAvail = ResourceTracker->canReserveResources(MI);
234  LLVM_DEBUG({
235  if (ResourceAvail)
236  dbgs() << " Resources are available for adding MI to packet\n";
237  else
238  dbgs() << " Resources NOT available\n";
239  });
240  if (ResourceAvail && shouldAddToPacket(MI)) {
241  // Dependency check for MI with instructions in CurrentPacketMIs.
242  for (auto MJ : CurrentPacketMIs) {
243  SUnit *SUJ = MIToSUnit[MJ];
244  assert(SUJ && "Missing SUnit Info!");
245 
246  LLVM_DEBUG(dbgs() << " Checking against MJ " << *MJ);
247  // Is it legal to packetize SUI and SUJ together.
248  if (!isLegalToPacketizeTogether(SUI, SUJ)) {
249  LLVM_DEBUG(dbgs() << " Not legal to add MI, try to prune\n");
250  // Allow packetization if dependency can be pruned.
251  if (!isLegalToPruneDependencies(SUI, SUJ)) {
252  // End the packet if dependency cannot be pruned.
253  LLVM_DEBUG(dbgs()
254  << " Could not prune dependencies for adding MI\n");
255  endPacket(MBB, MI);
256  break;
257  }
258  LLVM_DEBUG(dbgs() << " Pruned dependence for adding MI\n");
259  }
260  }
261  } else {
262  LLVM_DEBUG(if (ResourceAvail) dbgs()
263  << "Resources are available, but instruction should not be "
264  "added to packet\n "
265  << MI);
266  // End the packet if resource is not available, or if the instruction
267  // shoud not be added to the current packet.
268  endPacket(MBB, MI);
269  }
270 
271  // Add MI to the current packet.
272  LLVM_DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');
273  BeginItr = addToPacket(MI);
274  } // For all instructions in the packetization range.
275 
276  // End any packet left behind.
277  endPacket(MBB, EndItr);
280 }
281 
283  const MachineMemOperand &Op2,
284  bool UseTBAA) const {
285  if (!Op1.getValue() || !Op2.getValue())
286  return true;
287 
288  int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
289  int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset;
290  int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset;
291 
292  AliasResult AAResult =
293  AA->alias(MemoryLocation(Op1.getValue(), Overlapa,
294  UseTBAA ? Op1.getAAInfo() : AAMDNodes()),
295  MemoryLocation(Op2.getValue(), Overlapb,
296  UseTBAA ? Op2.getAAInfo() : AAMDNodes()));
297 
298  return AAResult != AliasResult::NoAlias;
299 }
300 
302  const MachineInstr &MI2,
303  bool UseTBAA) const {
304  if (MI1.memoperands_empty() || MI2.memoperands_empty())
305  return true;
306 
307  for (const MachineMemOperand *Op1 : MI1.memoperands())
308  for (const MachineMemOperand *Op2 : MI2.memoperands())
309  if (alias(*Op1, *Op2, UseTBAA))
310  return true;
311  return false;
312 }
313 
314 // Add a DAG mutation object to the ordered list.
316  std::unique_ptr<ScheduleDAGMutation> Mutation) {
318 }
llvm::VLIWPacketizerList::VLIWScheduler
DefaultVLIWScheduler * VLIWScheduler
Definition: DFAPacketizer.h:119
ScheduleDAG.h
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
MachineInstr.h
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
MCInstrDesc.h
llvm::VLIWPacketizerList::addMutation
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
Definition: DFAPacketizer.cpp:315
llvm::VLIWPacketizerList::alias
bool alias(const MachineInstr &MI1, const MachineInstr &MI2, bool UseTBAA=true) const
Definition: DFAPacketizer.cpp:301
aa
aa
Definition: AliasAnalysis.cpp:846
llvm::ScheduleDAGInstrs::buildSchedGraph
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
Definition: ScheduleDAGInstrs.cpp:730
llvm::VLIWPacketizerList::ignorePseudoInstruction
virtual bool ignorePseudoInstruction(const MachineInstr &I, const MachineBasicBlock *MBB)
Definition: DFAPacketizer.h:160
ScheduleDAGInstrs.h
llvm::VLIWPacketizerList::shouldAddToPacket
virtual bool shouldAddToPacket(const MachineInstr &MI)
Definition: DFAPacketizer.h:175
llvm::DFAPacketizer::canReserveResources
bool canReserveResources(const MCInstrDesc *MID)
Definition: DFAPacketizer.cpp:57
llvm::SmallVector< uint64_t, 4 >
llvm::MCInstrDesc::getSchedClass
unsigned getSchedClass() const
Return the scheduling class for this instruction.
Definition: MCInstrDesc.h:612
llvm::MachineMemOperand::getOffset
int64_t getOffset() const
For normal values, this is a byte offset added to the base address.
Definition: MachineMemOperand.h:227
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
InstrCount
static unsigned InstrCount
Definition: DFAPacketizer.cpp:53
llvm::AAMDNodes
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:651
TargetInstrInfo.h
llvm::MachineMemOperand
A description of a memory reference used in the backend.
Definition: MachineMemOperand.h:128
llvm::TargetInstrInfo::CreateTargetScheduleState
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
Definition: TargetInstrInfo.h:1775
llvm::ScheduleDAGInstrs::startBlock
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
Definition: ScheduleDAGInstrs.cpp:178
llvm::AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:81
InstrLimit
static cl::opt< unsigned > InstrLimit("dfa-instr-limit", cl::Hidden, cl::init(0), cl::desc("If present, stops packetizing after N instructions"))
llvm::VLIWPacketizerList::endPacket
virtual void endPacket(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI)
Definition: DFAPacketizer.cpp:162
llvm::VLIWPacketizerList::isLegalToPruneDependencies
virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ)
Definition: DFAPacketizer.h:183
llvm::VLIWPacketizerList::VLIWPacketizerList
VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI, AAResults *AA)
Definition: DFAPacketizer.cpp:148
llvm::VLIWPacketizerList::ResourceTracker
DFAPacketizer * ResourceTracker
Definition: DFAPacketizer.h:123
llvm::MachineMemOperand::getAAInfo
AAMDNodes getAAInfo() const
Return the AA tags for the memory reference.
Definition: MachineMemOperand.h:258
llvm::Automaton::getNfaPaths
ArrayRef< NfaPath > getNfaPaths()
Obtain a set of possible paths through the input nondeterministic automaton that could be obtained fr...
Definition: Automaton.h:254
llvm::ArrayRef::empty
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
AliasAnalysis.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
llvm::finalizeBundle
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...
Definition: MachineInstrBundle.cpp:123
MCInstrItineraries.h
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::DFAPacketizer::getUsedResources
unsigned getUsedResources(unsigned InstIdx)
Definition: DFAPacketizer.cpp:87
llvm::MachineMemOperand::getValue
const Value * getValue() const
Return the base address of the memory access.
Definition: MachineMemOperand.h:211
llvm::ScheduleDAGInstrs::CanHandleTerminators
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
Definition: ScheduleDAGInstrs.h:136
llvm::ScheduleDAGInstrs::exitRegion
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
Definition: ScheduleDAGInstrs.cpp:197
DFAPacketizer.h
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:129
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:195
MachineInstrBundle.h
llvm::VLIWPacketizerList::MF
MachineFunction & MF
Definition: DFAPacketizer.h:114
llvm::VLIWPacketizerList::addToPacket
virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI)
Definition: DFAPacketizer.h:143
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:626
llvm::cl::opt
Definition: CommandLine.h:1434
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::VLIWPacketizerList::isSoloInstruction
virtual bool isSoloInstruction(const MachineInstr &MI)
Definition: DFAPacketizer.h:167
llvm::DFAPacketizer::setTrackResources
void setTrackResources(bool Track)
Definition: DFAPacketizer.h:73
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::VLIWPacketizerList::AA
AAResults * AA
Definition: DFAPacketizer.h:116
llvm::SUnit::getInstr
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
StringExtras.h
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::VLIWPacketizerList::~VLIWPacketizerList
virtual ~VLIWPacketizerList()
Definition: DFAPacketizer.cpp:156
UseTBAA
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"))
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
llvm::ScheduleDAG::MF
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:560
llvm::AliasResult::NoAlias
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
llvm::DefaultVLIWScheduler::postprocessDAG
void postprocessDAG()
Apply each ScheduleDAGMutation step in order.
Definition: DFAPacketizer.cpp:137
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
TargetSubtargetInfo.h
llvm::Automaton::canAdd
bool canAdd(const ActionT &A)
Return true if the automaton can be transitioned based on input symbol A.
Definition: Automaton.h:246
Mutation
PowerPC VSX FMA Mutation
Definition: PPCVSXFMAMutate.cpp:391
llvm::ScheduleDAGInstrs::dump
void dump() const override
Definition: ScheduleDAGInstrs.cpp:1172
llvm::DefaultVLIWScheduler::schedule
void schedule() override
Orders nodes according to selected style.
Definition: DFAPacketizer.cpp:142
llvm::ArrayRef::front
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:168
llvm::ScheduleDAGInstrs::enterRegion
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.
Definition: ScheduleDAGInstrs.cpp:187
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::ScheduleDAGInstrs::MLI
const MachineLoopInfo * MLI
Definition: ScheduleDAGInstrs.h:121
llvm::ScheduleDAG::SUnits
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:562
llvm::MachineMemOperand::getSize
uint64_t getSize() const
Return the size in bytes of the memory reference.
Definition: MachineMemOperand.h:236
llvm::AAResults::alias
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
Definition: AliasAnalysis.cpp:120
llvm::MachineInstr::memoperands_empty
bool memoperands_empty() const
Return true if we don't have any memory operands which described the memory access done by this instr...
Definition: MachineInstr.h:720
llvm::VLIWPacketizerList::MIToSUnit
std::map< MachineInstr *, SUnit * > MIToSUnit
Definition: DFAPacketizer.h:125
llvm::VLIWPacketizerList::initPacketizerState
virtual void initPacketizerState()
Definition: DFAPacketizer.h:157
llvm::ScheduleDAGInstrs::finishBlock
virtual void finishBlock()
Cleans up after scheduling in the given block.
Definition: ScheduleDAGInstrs.cpp:182
llvm::DefaultVLIWScheduler
Definition: DFAPacketizer.cpp:105
llvm::DefaultVLIWScheduler::addMutation
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
DefaultVLIWScheduler takes ownership of the Mutation object.
Definition: DFAPacketizer.cpp:119
llvm::MachineInstr::memoperands
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:690
llvm::DefaultVLIWScheduler::DefaultVLIWScheduler
DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, AAResults *AA)
Definition: DFAPacketizer.cpp:129
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
llvm::cl::desc
Definition: CommandLine.h:414
llvm::VLIWPacketizerList::TII
const TargetInstrInfo * TII
Definition: DFAPacketizer.h:115
llvm::ScheduleDAGInstrs
A ScheduleDAG for scheduling lists of MachineInstr.
Definition: ScheduleDAGInstrs.h:119
raw_ostream.h
MachineFunction.h
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::VLIWPacketizerList::isLegalToPacketizeTogether
virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ)
Definition: DFAPacketizer.h:178
llvm::DFAPacketizer::reserveResources
void reserveResources(const MCInstrDesc *MID)
Definition: DFAPacketizer.cpp:66
Debug.h
llvm::Automaton::add
bool add(const ActionT &A)
Transition the automaton based on input symbol A.
Definition: Automaton.h:235
llvm::MemoryLocation
Representation for a specific memory location.
Definition: MemoryLocation.h:209
llvm::VLIWPacketizerList::CurrentPacketMIs
std::vector< MachineInstr * > CurrentPacketMIs
Definition: DFAPacketizer.h:121