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