1 //===- llvm/CodeGen/DFAPacketizer.h - DFA Packetizer for VLIW ---*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
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.
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.
24 //===----------------------------------------------------------------------===//
26 #ifndef LLVM_CODEGEN_DFAPACKETIZER_H
27 #define LLVM_CODEGEN_DFAPACKETIZER_H
29 #include "llvm/ADT/DenseMap.h"
30 #include "llvm/CodeGen/MachineBasicBlock.h"
31 #include "llvm/CodeGen/ScheduleDAGMutation.h"
40 class DefaultVLIWScheduler;
41 class InstrItineraryData;
42 class MachineFunction;
44 class MachineLoopInfo;
47 class TargetInstrInfo;
49 // --------------------------------------------------------------------
50 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
52 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
53 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
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
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
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.
72 using DFAInput = uint64_t;
73 using DFAStateInput = int64_t;
75 #define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable.
76 // --------------------------------------------------------------------
80 using UnsignPair = std::pair<unsigned, DFAInput>;
82 const InstrItineraryData *InstrItins;
84 const DFAStateInput (*DFAStateInputTable)[2];
85 const unsigned *DFAStateEntryTable;
87 // CachedTable is a map from <FromState, Input> to ToState.
88 DenseMap<UnsignPair, unsigned> CachedTable;
90 // Read the DFA transition table and update CachedTable.
91 void ReadTable(unsigned state);
94 DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
97 // Reset the current state to make all resources available.
98 void clearResources() {
102 // Return the DFAInput for an instruction class.
103 DFAInput getInsnInput(unsigned InsnClass);
105 // Return the DFAInput for an instruction class input vector.
106 static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass);
108 // Check if the resources occupied by a MCInstrDesc are available in
109 // the current state.
110 bool canReserveResources(const MCInstrDesc *MID);
112 // Reserve the resources occupied by a MCInstrDesc and change the current
113 // state to reflect that change.
114 void reserveResources(const MCInstrDesc *MID);
116 // Check if the resources occupied by a machine instruction are available
117 // in the current state.
118 bool canReserveResources(MachineInstr &MI);
120 // Reserve the resources occupied by a machine instruction and change the
121 // current state to reflect that change.
122 void reserveResources(MachineInstr &MI);
124 const InstrItineraryData *getInstrItins() const { return InstrItins; }
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 {
137 const TargetInstrInfo *TII;
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;
147 std::map<MachineInstr*, SUnit*> MIToSUnit;
150 // The AliasAnalysis parameter can be nullptr.
151 VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
154 virtual ~VLIWPacketizerList();
156 // Implement this API in the backend to bundle instructions.
157 void PacketizeMIs(MachineBasicBlock *MBB,
158 MachineBasicBlock::iterator BeginItr,
159 MachineBasicBlock::iterator EndItr);
161 // Return the ResourceTracker.
162 DFAPacketizer *getResourceTracker() {return ResourceTracker;}
164 // addToPacket - Add MI to the current packet.
165 virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) {
166 CurrentPacketMIs.push_back(&MI);
167 ResourceTracker->reserveResources(MI);
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);
177 // Perform initialization before packetizing an instruction. This
178 // function is supposed to be overrided by the target dependent packetizer.
179 virtual void initPacketizerState() {}
181 // Check if the given instruction I should be ignored by the packetizer.
182 virtual bool ignorePseudoInstruction(const MachineInstr &I,
183 const MachineBasicBlock *MBB) {
187 // Return true if instruction MI can not be packetized with any other
188 // instruction, which means that MI itself is a packet.
189 virtual bool isSoloInstruction(const MachineInstr &MI) { return true; }
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 virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; }
199 // Check if it is legal to packetize SUI and SUJ together.
200 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
204 // Check if it is legal to prune dependece between SUI and SUJ.
205 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
209 // Add a DAG mutation to be done before the packetization begins.
210 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation);
212 bool alias(const MachineInstr &MI1, const MachineInstr &MI2,
213 bool UseTBAA = true) const;
216 bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2,
217 bool UseTBAA = true) const;
220 } // end namespace llvm
222 #endif // LLVM_CODEGEN_DFAPACKETIZER_H