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
43using namespace llvm;
44
45#define DEBUG_TYPE "packets"
46
47static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden,
48 cl::init(Val: 0), cl::desc("If present, stops packetizing after N instructions"));
49
50static unsigned InstrCount = 0;
51
52// Check if the resources occupied by a MCInstrDesc are available in the
53// current state.
54bool DFAPacketizer::canReserveResources(const MCInstrDesc *MID) {
55 unsigned Action = ItinActions[MID->getSchedClass()];
56 if (MID->getSchedClass() == 0 || Action == 0)
57 return false;
58 return A.canAdd(A: Action);
59}
60
61// Reserve the resources occupied by a MCInstrDesc and change the current
62// state to reflect that change.
63void DFAPacketizer::reserveResources(const MCInstrDesc *MID) {
64 unsigned Action = ItinActions[MID->getSchedClass()];
65 if (MID->getSchedClass() == 0 || Action == 0)
66 return;
67 A.add(A: Action);
68}
69
70// Check if the resources occupied by a machine instruction are available
71// in the current state.
72bool DFAPacketizer::canReserveResources(MachineInstr &MI) {
73 const MCInstrDesc &MID = MI.getDesc();
74 return canReserveResources(MID: &MID);
75}
76
77// Reserve the resources occupied by a machine instruction and change the
78// current state to reflect that change.
79void DFAPacketizer::reserveResources(MachineInstr &MI) {
80 const MCInstrDesc &MID = MI.getDesc();
81 reserveResources(MID: &MID);
82}
83
84unsigned DFAPacketizer::getUsedResources(unsigned InstIdx) {
85 ArrayRef<NfaPath> NfaPaths = A.getNfaPaths();
86 assert(!NfaPaths.empty() && "Invalid bundle!");
87 const NfaPath &RS = NfaPaths.front();
88
89 // RS stores the cumulative resources used up to and including the I'th
90 // instruction. The 0th instruction is the base case.
91 if (InstIdx == 0)
92 return RS[0];
93 // Return the difference between the cumulative resources used by InstIdx and
94 // its predecessor.
95 return RS[InstIdx] ^ RS[InstIdx - 1];
96}
97
98DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF,
99 MachineLoopInfo &MLI,
100 AAResults *AA)
101 : ScheduleDAGInstrs(MF, &MLI), AA(AA) {
102 CanHandleTerminators = true;
103}
104
105/// Apply each ScheduleDAGMutation step in order.
106void DefaultVLIWScheduler::postProcessDAG() {
107 for (auto &M : Mutations)
108 M->apply(DAG: this);
109}
110
111void DefaultVLIWScheduler::schedule() {
112 // Build the scheduling graph.
113 buildSchedGraph(AA);
114 postProcessDAG();
115}
116
117VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf,
118 MachineLoopInfo &mli, AAResults *aa)
119 : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) {
120 ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget());
121 ResourceTracker->setTrackResources(true);
122 VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA);
123}
124
125VLIWPacketizerList::~VLIWPacketizerList() {
126 delete VLIWScheduler;
127 delete ResourceTracker;
128}
129
130// End the current packet, bundle packet instructions and reset DFA state.
131void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB,
132 MachineBasicBlock::iterator MI) {
133 LLVM_DEBUG({
134 if (!CurrentPacketMIs.empty()) {
135 dbgs() << "Finalizing packet:\n";
136 unsigned Idx = 0;
137 for (MachineInstr *MI : CurrentPacketMIs) {
138 unsigned R = ResourceTracker->getUsedResources(Idx++);
139 dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;
140 }
141 }
142 });
143 if (CurrentPacketMIs.size() > 1) {
144 MachineInstr &MIFirst = *CurrentPacketMIs.front();
145 finalizeBundle(MBB&: *MBB, FirstMI: MIFirst.getIterator(), LastMI: MI.getInstrIterator());
146 }
147 CurrentPacketMIs.clear();
148 ResourceTracker->clearResources();
149 LLVM_DEBUG(dbgs() << "End packet\n");
150}
151
152// Bundle machine instructions into packets.
153void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB,
154 MachineBasicBlock::iterator BeginItr,
155 MachineBasicBlock::iterator EndItr) {
156 assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
157 VLIWScheduler->startBlock(BB: MBB);
158 VLIWScheduler->enterRegion(bb: MBB, begin: BeginItr, end: EndItr,
159 regioninstrs: std::distance(first: BeginItr, last: EndItr));
160 VLIWScheduler->schedule();
161
162 LLVM_DEBUG({
163 dbgs() << "Scheduling DAG of the packetize region\n";
164 VLIWScheduler->dump();
165 });
166
167 // Generate MI -> SU map.
168 MIToSUnit.clear();
169 for (SUnit &SU : VLIWScheduler->SUnits)
170 MIToSUnit[SU.getInstr()] = &SU;
171
172 bool LimitPresent = InstrLimit.getPosition();
173
174 // The main packetizer loop.
175 for (; BeginItr != EndItr; ++BeginItr) {
176 if (LimitPresent) {
177 if (InstrCount >= InstrLimit) {
178 EndItr = BeginItr;
179 break;
180 }
181 InstrCount++;
182 }
183 MachineInstr &MI = *BeginItr;
184 initPacketizerState();
185
186 // End the current packet if needed.
187 if (isSoloInstruction(MI)) {
188 endPacket(MBB, MI);
189 continue;
190 }
191
192 // Ignore pseudo instructions.
193 if (ignorePseudoInstruction(I: MI, MBB))
194 continue;
195
196 SUnit *SUI = MIToSUnit[&MI];
197 assert(SUI && "Missing SUnit Info!");
198
199 // Ask DFA if machine resource is available for MI.
200 LLVM_DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI);
201
202 bool ResourceAvail = ResourceTracker->canReserveResources(MI);
203 LLVM_DEBUG({
204 if (ResourceAvail)
205 dbgs() << " Resources are available for adding MI to packet\n";
206 else
207 dbgs() << " Resources NOT available\n";
208 });
209 if (ResourceAvail && shouldAddToPacket(MI)) {
210 // Dependency check for MI with instructions in CurrentPacketMIs.
211 for (auto *MJ : CurrentPacketMIs) {
212 SUnit *SUJ = MIToSUnit[MJ];
213 assert(SUJ && "Missing SUnit Info!");
214
215 LLVM_DEBUG(dbgs() << " Checking against MJ " << *MJ);
216 // Is it legal to packetize SUI and SUJ together.
217 if (!isLegalToPacketizeTogether(SUI, SUJ)) {
218 LLVM_DEBUG(dbgs() << " Not legal to add MI, try to prune\n");
219 // Allow packetization if dependency can be pruned.
220 if (!isLegalToPruneDependencies(SUI, SUJ)) {
221 // End the packet if dependency cannot be pruned.
222 LLVM_DEBUG(dbgs()
223 << " Could not prune dependencies for adding MI\n");
224 endPacket(MBB, MI);
225 break;
226 }
227 LLVM_DEBUG(dbgs() << " Pruned dependence for adding MI\n");
228 }
229 }
230 } else {
231 LLVM_DEBUG(if (ResourceAvail) dbgs()
232 << "Resources are available, but instruction should not be "
233 "added to packet\n "
234 << MI);
235 // End the packet if resource is not available, or if the instruction
236 // should not be added to the current packet.
237 endPacket(MBB, MI);
238 }
239
240 // Add MI to the current packet.
241 LLVM_DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n');
242 BeginItr = addToPacket(MI);
243 } // For all instructions in the packetization range.
244
245 // End any packet left behind.
246 endPacket(MBB, MI: EndItr);
247 VLIWScheduler->exitRegion();
248 VLIWScheduler->finishBlock();
249}
250
251bool VLIWPacketizerList::alias(const MachineMemOperand &Op1,
252 const MachineMemOperand &Op2,
253 bool UseTBAA) const {
254 if (!Op1.getValue() || !Op2.getValue() || !Op1.getSize().hasValue() ||
255 !Op2.getSize().hasValue())
256 return true;
257
258 int64_t MinOffset = std::min(a: Op1.getOffset(), b: Op2.getOffset());
259 int64_t Overlapa = Op1.getSize().getValue() + Op1.getOffset() - MinOffset;
260 int64_t Overlapb = Op2.getSize().getValue() + Op2.getOffset() - MinOffset;
261
262 AliasResult AAResult =
263 AA->alias(LocA: MemoryLocation(Op1.getValue(), Overlapa,
264 UseTBAA ? Op1.getAAInfo() : AAMDNodes()),
265 LocB: MemoryLocation(Op2.getValue(), Overlapb,
266 UseTBAA ? Op2.getAAInfo() : AAMDNodes()));
267
268 return AAResult != AliasResult::NoAlias;
269}
270
271bool VLIWPacketizerList::alias(const MachineInstr &MI1,
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: *Op1, Op2: *Op2, UseTBAA))
280 return true;
281 return false;
282}
283
284// Add a DAG mutation object to the ordered list.
285void VLIWPacketizerList::addMutation(
286 std::unique_ptr<ScheduleDAGMutation> Mutation) {
287 VLIWScheduler->addMutation(Mutation: std::move(Mutation));
288}
289