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
38namespace llvm {
39
40class ScheduleDAGMutation;
41class InstrItineraryData;
42class MachineFunction;
43class MachineInstr;
44class MachineLoopInfo;
45class MCInstrDesc;
46class SUnit;
47class TargetInstrInfo;
48
49// This class extends ScheduleDAGInstrs and overrides the schedule method
50// to build the dependence graph.
51class DefaultVLIWScheduler : public ScheduleDAGInstrs {
52private:
53 AAResults *AA;
54 /// Ordered list of DAG postprocessing steps.
55 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
56
57public:
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
69protected:
70 void postProcessDAG();
71};
72
73class DFAPacketizer {
74private:
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
81public:
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.
136class VLIWPacketizerList {
137protected:
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
151public:
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
218private:
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