1 //===- llvm/CodeGen/DFAPacketizer.h - 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 #ifndef LLVM_CODEGEN_DFAPACKETIZER_H
26 #define LLVM_CODEGEN_DFAPACKETIZER_H
27 
28 #include "llvm/CodeGen/MachineBasicBlock.h"
29 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
30 #include "llvm/CodeGen/ScheduleDAGMutation.h"
31 #include "llvm/Support/Automaton.h"
32 #include <cstdint>
33 #include <map>
34 #include <memory>
35 #include <utility>
36 #include <vector>
37 
38 namespace llvm {
39 
40 class ScheduleDAGMutation;
41 class InstrItineraryData;
42 class MachineFunction;
43 class MachineInstr;
44 class MachineLoopInfo;
45 class MCInstrDesc;
46 class SUnit;
47 class TargetInstrInfo;
48 
49 // This class extends ScheduleDAGInstrs and overrides the schedule method
50 // to build the dependence graph.
51 class DefaultVLIWScheduler : public ScheduleDAGInstrs {
52 private:
53   AAResults *AA;
54   /// Ordered list of DAG postprocessing steps.
55   std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
56 
57 public:
58   DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI,
59                        AAResults *AA);
60 
61   // Actual scheduling work.
62   void schedule() override;
63 
64   /// DefaultVLIWScheduler takes ownership of the Mutation object.
65   void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
66     Mutations.push_back(std::move(Mutation));
67   }
68 
69 protected:
70   void postProcessDAG();
71 };
72 
73 class DFAPacketizer {
74 private:
75   const InstrItineraryData *InstrItins;
76   Automaton<uint64_t> A;
77   /// For every itinerary, an "action" to apply to the automaton. This removes
78   /// the redundancy in actions between itinerary classes.
79   ArrayRef<unsigned> ItinActions;
80 
81 public:
82   DFAPacketizer(const InstrItineraryData *InstrItins, Automaton<uint64_t> a,
83                 ArrayRef<unsigned> ItinActions)
84       : InstrItins(InstrItins), A(std::move(a)), ItinActions(ItinActions) {
85     // Start off with resource tracking disabled.
86     A.enableTranscription(false);
87   }
88 
89   // Reset the current state to make all resources available.
90   void clearResources() {
91     A.reset();
92   }
93 
94   // Set whether this packetizer should track not just whether instructions
95   // can be packetized, but also which functional units each instruction ends up
96   // using after packetization.
97   void setTrackResources(bool Track) {
98     A.enableTranscription(Track);
99   }
100 
101   // Check if the resources occupied by a MCInstrDesc are available in
102   // the current state.
103   bool canReserveResources(const MCInstrDesc *MID);
104 
105   // Reserve the resources occupied by a MCInstrDesc and change the current
106   // state to reflect that change.
107   void reserveResources(const MCInstrDesc *MID);
108 
109   // Check if the resources occupied by a machine instruction are available
110   // in the current state.
111   bool canReserveResources(MachineInstr &MI);
112 
113   // Reserve the resources occupied by a machine instruction and change the
114   // current state to reflect that change.
115   void reserveResources(MachineInstr &MI);
116 
117   // Return the resources used by the InstIdx'th instruction added to this
118   // packet. The resources are returned as a bitvector of functional units.
119   //
120   // Note that a bundle may be packed in multiple valid ways. This function
121   // returns one arbitary valid packing.
122   //
123   // Requires setTrackResources(true) to have been called.
124   unsigned getUsedResources(unsigned InstIdx);
125 
126   const InstrItineraryData *getInstrItins() const { return InstrItins; }
127 };
128 
129 // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
130 // packetizer works on machine basic blocks. For each instruction I in BB,
131 // the packetizer consults the DFA to see if machine resources are available
132 // to execute I. If so, the packetizer checks if I depends on any instruction
133 // in the current packet. If no dependency is found, I is added to current
134 // packet and the machine resource is marked as taken. If any dependency is
135 // found, a target API call is made to prune the dependence.
136 class VLIWPacketizerList {
137 protected:
138   MachineFunction &MF;
139   const TargetInstrInfo *TII;
140   AAResults *AA;
141 
142   // The VLIW Scheduler.
143   DefaultVLIWScheduler *VLIWScheduler;
144   // Vector of instructions assigned to the current packet.
145   std::vector<MachineInstr*> CurrentPacketMIs;
146   // DFA resource tracker.
147   DFAPacketizer *ResourceTracker;
148   // Map: MI -> SU.
149   std::map<MachineInstr*, SUnit*> MIToSUnit;
150 
151 public:
152   // The AAResults parameter can be nullptr.
153   VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
154                      AAResults *AA);
155   VLIWPacketizerList &operator=(const VLIWPacketizerList &other) = delete;
156   VLIWPacketizerList(const VLIWPacketizerList &other) = delete;
157   virtual ~VLIWPacketizerList();
158 
159   // Implement this API in the backend to bundle instructions.
160   void PacketizeMIs(MachineBasicBlock *MBB,
161                     MachineBasicBlock::iterator BeginItr,
162                     MachineBasicBlock::iterator EndItr);
163 
164   // Return the ResourceTracker.
165   DFAPacketizer *getResourceTracker() {return ResourceTracker;}
166 
167   // addToPacket - Add MI to the current packet.
168   virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) {
169     CurrentPacketMIs.push_back(&MI);
170     ResourceTracker->reserveResources(MI);
171     return MI;
172   }
173 
174   // End the current packet and reset the state of the packetizer.
175   // Overriding this function allows the target-specific packetizer
176   // to perform custom finalization.
177   virtual void endPacket(MachineBasicBlock *MBB,
178                          MachineBasicBlock::iterator MI);
179 
180   // Perform initialization before packetizing an instruction. This
181   // function is supposed to be overrided by the target dependent packetizer.
182   virtual void initPacketizerState() {}
183 
184   // Check if the given instruction I should be ignored by the packetizer.
185   virtual bool ignorePseudoInstruction(const MachineInstr &I,
186                                        const MachineBasicBlock *MBB) {
187     return false;
188   }
189 
190   // Return true if instruction MI can not be packetized with any other
191   // instruction, which means that MI itself is a packet.
192   virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
193 
194   // Check if the packetizer should try to add the given instruction to
195   // the current packet. One reasons for which it may not be desirable
196   // to include an instruction in the current packet could be that it
197   // would cause a stall.
198   // If this function returns "false", the current packet will be ended,
199   // and the instruction will be added to the next packet.
200   virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
201 
202   // Check if it is legal to packetize SUI and SUJ together.
203   virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
204     return false;
205   }
206 
207   // Check if it is legal to prune dependece between SUI and SUJ.
208   virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
209     return false;
210   }
211 
212   // Add a DAG mutation to be done before the packetization begins.
213   void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
214 
215   bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
216              bool UseTBAA = true) const;
217 
218 private:
219   bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
220              bool UseTBAA = true) const;
221 };
222 
223 } // end namespace llvm
224 
225 #endif // LLVM_CODEGEN_DFAPACKETIZER_H
226