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