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 
44 using namespace llvm;
45 
46 #define DEBUG_TYPE "packets"
47 
48 static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden,
49   cl::init(0), cl::desc("If present, stops packetizing after N instructions"));
50 
51 static unsigned InstrCount = 0;
52 
53 // Check if the resources occupied by a MCInstrDesc are available in the
54 // current state.
55 bool 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(Action);
60 }
61 
62 // Reserve the resources occupied by a MCInstrDesc and change the current
63 // state to reflect that change.
64 void DFAPacketizer::reserveResources(const MCInstrDesc *MID) {
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.
73 bool DFAPacketizer::canReserveResources(MachineInstr &MI) {
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.
80 void DFAPacketizer::reserveResources(MachineInstr &MI) {
81   const MCInstrDesc &MID = MI.getDesc();
82   reserveResources(&MID);
83 }
84 
85 unsigned 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 
99 DefaultVLIWScheduler::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.
107 void DefaultVLIWScheduler::postProcessDAG() {
108   for (auto &M : Mutations)
109     M->apply(this);
110 }
111 
112 void DefaultVLIWScheduler::schedule() {
113   // Build the scheduling graph.
114   buildSchedGraph(AA);
115   postProcessDAG();
116 }
117 
118 VLIWPacketizerList::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 
126 VLIWPacketizerList::~VLIWPacketizerList() {
127   delete VLIWScheduler;
128   delete ResourceTracker;
129 }
130 
131 // End the current packet, bundle packet instructions and reset DFA state.
132 void 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, 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.
154 void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB,
155                                       MachineBasicBlock::iterator BeginItr,
156                                       MachineBasicBlock::iterator EndItr) {
157   assert(VLIWScheduler && "VLIW Scheduler is not initialized!");
158   VLIWScheduler->startBlock(MBB);
159   VLIWScheduler->enterRegion(MBB, BeginItr, EndItr,
160                              std::distance(BeginItr, 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(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, EndItr);
248   VLIWScheduler->exitRegion();
249   VLIWScheduler->finishBlock();
250 }
251 
252 bool VLIWPacketizerList::alias(const MachineMemOperand &Op1,
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 
271 bool 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, *Op2, UseTBAA))
280         return true;
281   return false;
282 }
283 
284 // Add a DAG mutation object to the ordered list.
285 void VLIWPacketizerList::addMutation(
286       std::unique_ptr<ScheduleDAGMutation> Mutation) {
287   VLIWScheduler->addMutation(std::move(Mutation));
288 }
289