LLVM 17.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
36#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
46using namespace llvm;
47
48#define DEBUG_TYPE "packets"
49
50static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden,
51 cl::init(0), cl::desc("If present, stops packetizing after N instructions"));
52
53static 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
87unsigned 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
101namespace llvm {
102
103// This class extends ScheduleDAGInstrs and overrides the schedule method
104// to build the dependence graph.
106private:
107 AAResults *AA;
108 /// Ordered list of DAG postprocessing steps.
109 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
110
111public:
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
123protected:
124 void postprocessDAG();
125};
126
127} // end namespace llvm
128
130 MachineLoopInfo &MLI,
131 AAResults *AA)
132 : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
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);
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.
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";
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.
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}
MachineBasicBlock & MBB
static cl::opt< unsigned > InstrLimit("dfa-instr-limit", cl::Hidden, cl::init(0), cl::desc("If present, stops packetizing after N instructions"))
static unsigned InstrCount
#define LLVM_DEBUG(X)
Definition: Debug.h:101
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
PowerPC VSX FMA Mutation
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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"))
This file contains some functions that are useful when dealing with strings.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
The possible results of an alias query.
Definition: AliasAnalysis.h:83
@ NoAlias
The two locations do not alias at all.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
const T & front() const
front - Get the first element.
Definition: ArrayRef.h:166
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:158
bool canAdd(const ActionT &A)
Return true if the automaton can be transitioned based on input symbol A.
Definition: Automaton.h:246
bool add(const ActionT &A)
Transition the automaton based on input symbol A.
Definition: Automaton.h:235
ArrayRef< NfaPath > getNfaPaths()
Obtain a set of possible paths through the input nondeterministic automaton that could be obtained fr...
Definition: Automaton.h:254
unsigned getUsedResources(unsigned InstIdx)
bool canReserveResources(const MCInstrDesc *MID)
void reserveResources(const MCInstrDesc *MID)
void setTrackResources(bool Track)
Definition: DFAPacketizer.h:72
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
DefaultVLIWScheduler takes ownership of the Mutation object.
void schedule() override
Orders nodes according to selected style.
DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, AAResults *AA)
void postprocessDAG()
Apply each ScheduleDAGMutation step in order.
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
unsigned getSchedClass() const
Return the scheduling class for this instruction.
Definition: MCInstrDesc.h:596
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Representation of each machine instruction.
Definition: MachineInstr.h:68
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:743
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:713
A description of a memory reference used in the backend.
uint64_t getSize() const
Return the size in bytes of the memory reference.
AAMDNodes getAAInfo() const
Return the AA tags for the memory reference.
const Value * getValue() const
Return the base address of the memory access.
int64_t getOffset() const
For normal values, this is a byte offset added to the base address.
Representation for a specific memory location.
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
A ScheduleDAG for scheduling lists of MachineInstr.
virtual void finishBlock()
Cleans up after scheduling in the given block.
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
const MachineLoopInfo * MLI
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.
void dump() const override
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:561
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:559
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
MachineFunction & MF
VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI, AAResults *AA)
virtual bool isSoloInstruction(const MachineInstr &MI)
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ)
const TargetInstrInfo * TII
bool alias(const MachineInstr &MI1, const MachineInstr &MI2, bool UseTBAA=true) const
std::vector< MachineInstr * > CurrentPacketMIs
std::map< MachineInstr *, SUnit * > MIToSUnit
DefaultVLIWScheduler * VLIWScheduler
virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ)
DFAPacketizer * ResourceTracker
virtual void initPacketizerState()
virtual void endPacket(MachineBasicBlock *MBB, MachineBasicBlock::iterator MI)
virtual bool ignorePseudoInstruction(const MachineInstr &I, const MachineBasicBlock *MBB)
void PacketizeMIs(MachineBasicBlock *MBB, MachineBasicBlock::iterator BeginItr, MachineBasicBlock::iterator EndItr)
virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI)
virtual bool shouldAddToPacket(const MachineInstr &MI)
self_iterator getIterator()
Definition: ilist_node.h:82
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:651