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() || !Op1.getSize().hasValue() ||
256 !Op2.getSize().hasValue())
257 return true;
258
259 int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset());
260 int64_t Overlapa = Op1.getSize().getValue() + Op1.getOffset() - MinOffset;
261 int64_t Overlapb = Op2.getSize().getValue() + Op2.getOffset() - MinOffset;
262
263 AliasResult AAResult =
264 AA->alias(MemoryLocation(Op1.getValue(), Overlapa,
265 UseTBAA ? Op1.getAAInfo() : AAMDNodes()),
266 MemoryLocation(Op2.getValue(), Overlapb,
267 UseTBAA ? Op2.getAAInfo() : AAMDNodes()));
268
269 return AAResult != AliasResult::NoAlias;
270}
271
273 const MachineInstr &MI2,
274 bool UseTBAA) const {
275 if (MI1.memoperands_empty() || MI2.memoperands_empty())
276 return true;
277
278 for (const MachineMemOperand *Op1 : MI1.memoperands())
279 for (const MachineMemOperand *Op2 : MI2.memoperands())
280 if (alias(*Op1, *Op2, UseTBAA))
281 return true;
282 return false;
283}
284
285// Add a DAG mutation object to the ordered list.
287 std::unique_ptr<ScheduleDAGMutation> Mutation) {
289}
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)
bool hasValue() const
TypeSize getValue() const
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:69
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:809
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:779
A description of a memory reference used in the backend.
LocationSize 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:390
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:579
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