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
25#include "llvm/CodeGen/DFAPacketizer.h"
26#include "llvm/ADT/StringExtras.h"
27#include "llvm/Analysis/AliasAnalysis.h"
28#include "llvm/CodeGen/MachineFunction.h"
29#include "llvm/CodeGen/MachineInstr.h"
30#include "llvm/CodeGen/MachineInstrBundle.h"
31#include "llvm/CodeGen/ScheduleDAG.h"
32#include "llvm/CodeGen/TargetInstrInfo.h"
33#include "llvm/CodeGen/TargetSubtargetInfo.h"
34#include "llvm/MC/MCInstrDesc.h"
35#include "llvm/Support/CommandLine.h"
36#include "llvm/Support/Debug.h"
37#include "llvm/Support/raw_ostream.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(Val: 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.
55bool DFAPacketizer::canReserveResources(const MCInstrDesc *MID) {
56 unsigned Action = ItinActions[MID->getSchedClass()];
57 if (MID->getSchedClass() == 0 || Action == 0)
58 return false;
59 return A.canAdd(A: Action);
60}
61
62// Reserve the resources occupied by a MCInstrDesc and change the current
63// state to reflect that change.
64void DFAPacketizer::reserveResources(const MCInstrDesc *MID) {
65 unsigned Action = ItinActions[MID->getSchedClass()];
66 if (MID->getSchedClass() == 0 || Action == 0)
67 return;
68 A.add(A: Action);
69}
70
71// Check if the resources occupied by a machine instruction are available
72// in the current state.
73bool DFAPacketizer::canReserveResources(MachineInstr &MI) {
74 const MCInstrDesc &MID = MI.getDesc();
75 return canReserveResources(MID: &MID);
76}
77
78// Reserve the resources occupied by a machine instruction and change the
79// current state to reflect that change.
80void DFAPacketizer::reserveResources(MachineInstr &MI) {
81 const MCInstrDesc &MID = MI.getDesc();
82 reserveResources(MID: &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
99DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF,
100 MachineLoopInfo &MLI,
101 AAResults *AA)
102 : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
103 CanHandleTerminators = true;
104}
105
106/// Apply each ScheduleDAGMutation step in order.
107void DefaultVLIWScheduler::postProcessDAG() {
108 for (auto &M : Mutations)
109 M->apply(DAG: this);
110}
111
112void DefaultVLIWScheduler::schedule() {
113 // Build the scheduling graph.
114 buildSchedGraph(AA);
115 postProcessDAG();
116}
117
118VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf,
119 MachineLoopInfo &mli, AAResults *aa)
120 : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
121 ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget());
122 ResourceTracker->setTrackResources(true);
123 VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA);
124}
125
126VLIWPacketizerList::~VLIWPacketizerList() {
127 delete VLIWScheduler;
128 delete ResourceTracker;
129}
130
131// End the current packet, bundle packet instructions and reset DFA state.
132void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB,
133 MachineBasicBlock::iterator MI) {
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&: *MBB, FirstMI: MIFirst.getIterator(), LastMI: MI.getInstrIterator());
147 }
148 CurrentPacketMIs.clear();
149 ResourceTracker->clearResources();
150 LLVM_DEBUG(dbgs() << "End packet\n");
151}
152
153// Bundle machine instructions into packets.
154void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB,
155 MachineBasicBlock::iterator BeginItr,
156 MachineBasicBlock::iterator EndItr) {
157 assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
158 VLIWScheduler->startBlock(BB: MBB);
159 VLIWScheduler->enterRegion(bb: MBB, begin: BeginItr, end: EndItr,
160 regioninstrs: std::distance(first: BeginItr, last: EndItr));
161 VLIWScheduler->schedule();
162
163 LLVM_DEBUG({
164 dbgs() << "Scheduling DAG of the packetize region\n";
165 VLIWScheduler->dump();
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;
185 initPacketizerState();
186
187 // End the current packet if needed.
188 if (isSoloInstruction(MI)) {
189 endPacket(MBB, MI);
190 continue;
191 }
192
193 // Ignore pseudo instructions.
194 if (ignorePseudoInstruction(I: MI, MBB))
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.
223 LLVM_DEBUG(dbgs()
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, MI: EndItr);
248 VLIWScheduler->exitRegion();
249 VLIWScheduler->finishBlock();
250}
251
252bool VLIWPacketizerList::alias(const MachineMemOperand &Op1,
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(a: Op1.getOffset(), b: 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(LocA: MemoryLocation(Op1.getValue(), Overlapa,
265 UseTBAA ? Op1.getAAInfo() : AAMDNodes()),
266 LocB: MemoryLocation(Op2.getValue(), Overlapb,
267 UseTBAA ? Op2.getAAInfo() : AAMDNodes()));
268
269 return AAResult != AliasResult::NoAlias;
270}
271
272bool VLIWPacketizerList::alias(const MachineInstr &MI1,
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: *Op1, Op2: *Op2, UseTBAA))
281 return true;
282 return false;
283}
284
285// Add a DAG mutation object to the ordered list.
286void VLIWPacketizerList::addMutation(
287 std::unique_ptr<ScheduleDAGMutation> Mutation) {
288 VLIWScheduler->addMutation(Mutation: std::move(Mutation));
289}
290