LLVM 19.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
34#include "llvm/MC/MCInstrDesc.h"
36#include "llvm/Support/Debug.h"
38#include <algorithm>
39#include <cassert>
40#include <iterator>
41#include <memory>
42#include <vector>
43
44using namespace llvm;
45
46#define DEBUG_TYPE "packets"
47
48static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden,
49 cl::init(0), cl::desc("If present, stops packetizing after N instructions"));
50
51static unsigned InstrCount = 0;
52
53// Check if the resources occupied by a MCInstrDesc are available in the
54// current state.
56 unsigned Action = ItinActions[MID->getSchedClass()];
57 if (MID->getSchedClass() == 0 || Action == 0)
58 return false;
59 return A.canAdd(Action);
60}
61
62// Reserve the resources occupied by a MCInstrDesc and change the current
63// state to reflect that change.
65 unsigned Action = ItinActions[MID->getSchedClass()];
66 if (MID->getSchedClass() == 0 || Action == 0)
67 return;
68 A.add(Action);
69}
70
71// Check if the resources occupied by a machine instruction are available
72// in the current state.
74 const MCInstrDesc &MID = MI.getDesc();
75 return canReserveResources(&MID);
76}
77
78// Reserve the resources occupied by a machine instruction and change the
79// current state to reflect that change.
81 const MCInstrDesc &MID = MI.getDesc();
82 reserveResources(&MID);
83}
84
85unsigned DFAPacketizer::getUsedResources(unsigned InstIdx) {
86 ArrayRef<NfaPath> NfaPaths = A.getNfaPaths();
87 assert(!NfaPaths.empty() && "Invalid bundle!");
88 const NfaPath &RS = NfaPaths.front();
89
90 // RS stores the cumulative resources used up to and including the I'th
91 // instruction. The 0th instruction is the base case.
92 if (InstIdx == 0)
93 return RS[0];
94 // Return the difference between the cumulative resources used by InstIdx and
95 // its predecessor.
96 return RS[InstIdx] ^ RS[InstIdx - 1];
97}
98
100 MachineLoopInfo &MLI,
101 AAResults *AA)
102 : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
104}
105
106/// Apply each ScheduleDAGMutation step in order.
108 for (auto &M : Mutations)
109 M->apply(this);
110}
111
113 // Build the scheduling graph.
114 buildSchedGraph(AA);
116}
117
120 : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
124}
125
127 delete VLIWScheduler;
128 delete ResourceTracker;
129}
130
131// End the current packet, bundle packet instructions and reset DFA state.
134 LLVM_DEBUG({
135 if (!CurrentPacketMIs.empty()) {
136 dbgs() << "Finalizing packet:\n";
137 unsigned Idx = 0;
138 for (MachineInstr *MI : CurrentPacketMIs) {
139 unsigned R = ResourceTracker->getUsedResources(Idx++);
140 dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;
141 }
142 }
143 });
144 if (CurrentPacketMIs.size() > 1) {
145 MachineInstr &MIFirst = *CurrentPacketMIs.front();
146 finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator());
147 }
148 CurrentPacketMIs.clear();
149 ResourceTracker->clearResources();
150 LLVM_DEBUG(dbgs() << "End packet\n");
151}
152
153// Bundle machine instructions into packets.
157 assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
159 VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,
160 std::distance(BeginItr, EndItr));
162
163 LLVM_DEBUG({
164 dbgs() << "Scheduling DAG of the packetize region\n";
166 });
167
168 // Generate MI -> SU map.
169 MIToSUnit.clear();
170 for (SUnit &SU : VLIWScheduler->SUnits)
171 MIToSUnit[SU.getInstr()] = &SU;
172
173 bool LimitPresent = InstrLimit.getPosition();
174
175 // The main packetizer loop.
176 for (; BeginItr != EndItr; ++BeginItr) {
177 if (LimitPresent) {
178 if (InstrCount >= InstrLimit) {
179 EndItr = BeginItr;
180 break;
181 }
182 InstrCount++;
183 }
184 MachineInstr &MI = *BeginItr;
186
187 // End the current packet if needed.
188 if (isSoloInstruction(MI)) {
189 endPacket(MBB, MI);
190 continue;
191 }
192
193 // Ignore pseudo instructions.
195 continue;
196
197 SUnit *SUI = MIToSUnit[&MI];
198 assert(SUI && "Missing SUnit Info!");
199
200 // Ask DFA if machine resource is available for MI.
201 LLVM_DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);
202
203 bool ResourceAvail = ResourceTracker->canReserveResources(MI);
204 LLVM_DEBUG({
205 if (ResourceAvail)
206 dbgs() << " Resources are available for adding MI to packet\n";
207 else
208 dbgs() << " Resources NOT available\n";
209 });
210 if (ResourceAvail && shouldAddToPacket(MI)) {
211 // Dependency check for MI with instructions in CurrentPacketMIs.
212 for (auto *MJ : CurrentPacketMIs) {
213 SUnit *SUJ = MIToSUnit[MJ];
214 assert(SUJ && "Missing SUnit Info!");
215
216 LLVM_DEBUG(dbgs() << " Checking against MJ " << *MJ);
217 // Is it legal to packetize SUI and SUJ together.
218 if (!isLegalToPacketizeTogether(SUI, SUJ)) {
219 LLVM_DEBUG(dbgs() << " Not legal to add MI, try to prune\n");
220 // Allow packetization if dependency can be pruned.
221 if (!isLegalToPruneDependencies(SUI, SUJ)) {
222 // End the packet if dependency cannot be pruned.
224 << " Could not prune dependencies for adding MI\n");
225 endPacket(MBB, MI);
226 break;
227 }
228 LLVM_DEBUG(dbgs() << " Pruned dependence for adding MI\n");
229 }
230 }
231 } else {
232 LLVM_DEBUG(if (ResourceAvail) dbgs()
233 << "Resources are available, but instruction should not be "
234 "added to packet\n "
235 << MI);
236 // End the packet if resource is not available, or if the instruction
237 // should not be added to the current packet.
238 endPacket(MBB, MI);
239 }
240
241 // Add MI to the current packet.
242 LLVM_DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');
243 BeginItr = addToPacket(MI);
244 } // For all instructions in the packetization range.
245
246 // End any packet left behind.
247 endPacket(MBB, EndItr);
250}
251
253 const MachineMemOperand &Op2,
254 bool UseTBAA) const {
255 if (!Op1.getValue() || !Op2.getValue())
256 return true;
257
258 int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
259 int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset;
260 int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset;
261
262 AliasResult AAResult =
263 AA->alias(MemoryLocation(Op1.getValue(), Overlapa,
264 UseTBAA ? Op1.getAAInfo() : AAMDNodes()),
265 MemoryLocation(Op2.getValue(), Overlapb,
266 UseTBAA ? Op2.getAAInfo() : AAMDNodes()));
267
268 return AAResult != AliasResult::NoAlias;
269}
270
272 const MachineInstr &MI2,
273 bool UseTBAA) const {
274 if (MI1.memoperands_empty() || MI2.memoperands_empty())
275 return true;
276
277 for (const MachineMemOperand *Op1 : MI1.memoperands())
278 for (const MachineMemOperand *Op2 : MI2.memoperands())
279 if (alias(*Op1, *Op2, UseTBAA))
280 return true;
281 return false;
282}
283
284// Add a DAG mutation object to the ordered list.
286 std::unique_ptr<ScheduleDAGMutation> Mutation) {
288}
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:81
@ NoAlias
The two locations do not alias at all.
Definition: AliasAnalysis.h:99
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:168
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
bool canAdd(const ActionT &A)
Return true if the automaton can be transitioned based on input symbol A.
Definition: Automaton.h:244
bool add(const ActionT &A)
Transition the automaton based on input symbol A.
Definition: Automaton.h:233
ArrayRef< NfaPath > getNfaPaths()
Obtain a set of possible paths through the input nondeterministic automaton that could be obtained fr...
Definition: Automaton.h:252
unsigned getUsedResources(unsigned InstIdx)
bool canReserveResources(const MCInstrDesc *MID)
void reserveResources(const MCInstrDesc *MID)
void setTrackResources(bool Track)
Definition: DFAPacketizer.h:97
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
DefaultVLIWScheduler takes ownership of the Mutation object.
Definition: DFAPacketizer.h:65
void postProcessDAG()
Apply each ScheduleDAGMutation step in order.
void schedule() override
Orders nodes according to selected style.
DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, AAResults *AA)
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:600
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:786
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:756
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.
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
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:109
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
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:760