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(x: 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(Enable: 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(Enable: 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(x: &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 | |