Line data Source code
1 : //===- llvm/CodeGen/DFAPacketizer.h - DFA Packetizer for VLIW ---*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : // This class implements a deterministic finite automaton (DFA) based
10 : // packetizing mechanism for VLIW architectures. It provides APIs to
11 : // determine whether there exists a legal mapping of instructions to
12 : // functional unit assignments in a packet. The DFA is auto-generated from
13 : // the target's Schedule.td file.
14 : //
15 : // A DFA consists of 3 major elements: states, inputs, and transitions. For
16 : // the packetizing mechanism, the input is the set of instruction classes for
17 : // a target. The state models all possible combinations of functional unit
18 : // consumption for a given set of instructions in a packet. A transition
19 : // models the addition of an instruction to a packet. In the DFA constructed
20 : // by this class, if an instruction can be added to a packet, then a valid
21 : // transition exists from the corresponding state. Invalid transitions
22 : // indicate that the instruction cannot be added to the current packet.
23 : //
24 : //===----------------------------------------------------------------------===//
25 :
26 : #ifndef LLVM_CODEGEN_DFAPACKETIZER_H
27 : #define LLVM_CODEGEN_DFAPACKETIZER_H
28 :
29 : #include "llvm/ADT/DenseMap.h"
30 : #include "llvm/CodeGen/MachineBasicBlock.h"
31 : #include "llvm/CodeGen/ScheduleDAGMutation.h"
32 : #include <cstdint>
33 : #include <map>
34 : #include <memory>
35 : #include <utility>
36 : #include <vector>
37 :
38 : namespace llvm {
39 :
40 : class DefaultVLIWScheduler;
41 : class InstrItineraryData;
42 : class MachineFunction;
43 : class MachineInstr;
44 : class MachineLoopInfo;
45 : class MCInstrDesc;
46 : class SUnit;
47 : class TargetInstrInfo;
48 :
49 : // --------------------------------------------------------------------
50 : // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
51 :
52 : // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
53 : // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
54 : //
55 : // e.g. terms x resource bit combinations that fit in uint32_t:
56 : // 4 terms x 8 bits = 32 bits
57 : // 3 terms x 10 bits = 30 bits
58 : // 2 terms x 16 bits = 32 bits
59 : //
60 : // e.g. terms x resource bit combinations that fit in uint64_t:
61 : // 8 terms x 8 bits = 64 bits
62 : // 7 terms x 9 bits = 63 bits
63 : // 6 terms x 10 bits = 60 bits
64 : // 5 terms x 12 bits = 60 bits
65 : // 4 terms x 16 bits = 64 bits <--- current
66 : // 3 terms x 21 bits = 63 bits
67 : // 2 terms x 32 bits = 64 bits
68 : //
69 : #define DFA_MAX_RESTERMS 4 // The max # of AND'ed resource terms.
70 : #define DFA_MAX_RESOURCES 16 // The max # of resource bits in one term.
71 :
72 : using DFAInput = uint64_t;
73 : using DFAStateInput = int64_t;
74 :
75 : #define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable.
76 : // --------------------------------------------------------------------
77 :
78 20988 : class DFAPacketizer {
79 : private:
80 : using UnsignPair = std::pair<unsigned, DFAInput>;
81 :
82 : const InstrItineraryData *InstrItins;
83 : int CurrentState = 0;
84 : const DFAStateInput (*DFAStateInputTable)[2];
85 : const unsigned *DFAStateEntryTable;
86 :
87 : // CachedTable is a map from <FromState, Input> to ToState.
88 : DenseMap<UnsignPair, unsigned> CachedTable;
89 :
90 : // Read the DFA transition table and update CachedTable.
91 : void ReadTable(unsigned state);
92 :
93 : public:
94 : DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
95 : const unsigned *SET);
96 :
97 : // Reset the current state to make all resources available.
98 0 : void clearResources() {
99 104344 : CurrentState = 0;
100 0 : }
101 :
102 : // Return the DFAInput for an instruction class.
103 : DFAInput getInsnInput(unsigned InsnClass);
104 :
105 : // Return the DFAInput for an instruction class input vector.
106 : static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass);
107 :
108 : // Check if the resources occupied by a MCInstrDesc are available in
109 : // the current state.
110 : bool canReserveResources(const MCInstrDesc *MID);
111 :
112 : // Reserve the resources occupied by a MCInstrDesc and change the current
113 : // state to reflect that change.
114 : void reserveResources(const MCInstrDesc *MID);
115 :
116 : // Check if the resources occupied by a machine instruction are available
117 : // in the current state.
118 : bool canReserveResources(MachineInstr &MI);
119 :
120 : // Reserve the resources occupied by a machine instruction and change the
121 : // current state to reflect that change.
122 : void reserveResources(MachineInstr &MI);
123 :
124 0 : const InstrItineraryData *getInstrItins() const { return InstrItins; }
125 : };
126 :
127 : // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The
128 : // packetizer works on machine basic blocks. For each instruction I in BB,
129 : // the packetizer consults the DFA to see if machine resources are available
130 : // to execute I. If so, the packetizer checks if I depends on any instruction
131 : // in the current packet. If no dependency is found, I is added to current
132 : // packet and the machine resource is marked as taken. If any dependency is
133 : // found, a target API call is made to prune the dependence.
134 : class VLIWPacketizerList {
135 : protected:
136 : MachineFunction &MF;
137 : const TargetInstrInfo *TII;
138 : AliasAnalysis *AA;
139 :
140 : // The VLIW Scheduler.
141 : DefaultVLIWScheduler *VLIWScheduler;
142 : // Vector of instructions assigned to the current packet.
143 : std::vector<MachineInstr*> CurrentPacketMIs;
144 : // DFA resource tracker.
145 : DFAPacketizer *ResourceTracker;
146 : // Map: MI -> SU.
147 : std::map<MachineInstr*, SUnit*> MIToSUnit;
148 :
149 : public:
150 : // The AliasAnalysis parameter can be nullptr.
151 : VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
152 : AliasAnalysis *AA);
153 :
154 : virtual ~VLIWPacketizerList();
155 :
156 : // Implement this API in the backend to bundle instructions.
157 : void PacketizeMIs(MachineBasicBlock *MBB,
158 : MachineBasicBlock::iterator BeginItr,
159 : MachineBasicBlock::iterator EndItr);
160 :
161 : // Return the ResourceTracker.
162 0 : DFAPacketizer *getResourceTracker() {return ResourceTracker;}
163 :
164 : // addToPacket - Add MI to the current packet.
165 46385 : virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) {
166 46385 : CurrentPacketMIs.push_back(&MI);
167 46385 : ResourceTracker->reserveResources(MI);
168 46385 : return MI;
169 : }
170 :
171 : // End the current packet and reset the state of the packetizer.
172 : // Overriding this function allows the target-specific packetizer
173 : // to perform custom finalization.
174 : virtual void endPacket(MachineBasicBlock *MBB,
175 : MachineBasicBlock::iterator MI);
176 :
177 : // Perform initialization before packetizing an instruction. This
178 : // function is supposed to be overrided by the target dependent packetizer.
179 0 : virtual void initPacketizerState() {}
180 :
181 : // Check if the given instruction I should be ignored by the packetizer.
182 0 : virtual bool ignorePseudoInstruction(const MachineInstr &I,
183 : const MachineBasicBlock *MBB) {
184 0 : return false;
185 : }
186 :
187 : // Return true if instruction MI can not be packetized with any other
188 : // instruction, which means that MI itself is a packet.
189 0 : virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
190 :
191 : // Check if the packetizer should try to add the given instruction to
192 : // the current packet. One reasons for which it may not be desirable
193 : // to include an instruction in the current packet could be that it
194 : // would cause a stall.
195 : // If this function returns "false", the current packet will be ended,
196 : // and the instruction will be added to the next packet.
197 46210 : virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
198 :
199 : // Check if it is legal to packetize SUI and SUJ together.
200 0 : virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
201 0 : return false;
202 : }
203 :
204 : // Check if it is legal to prune dependece between SUI and SUJ.
205 0 : virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
206 0 : return false;
207 : }
208 :
209 : // Add a DAG mutation to be done before the packetization begins.
210 : void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
211 :
212 : bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
213 : bool UseTBAA = true) const;
214 :
215 : private:
216 : bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
217 : bool UseTBAA = true) const;
218 : };
219 :
220 : } // end namespace llvm
221 :
222 : #endif // LLVM_CODEGEN_DFAPACKETIZER_H
|
