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"
37 class MachineLoopInfo;
38 class MachineDominatorTree;
39 class InstrItineraryData;
40 class DefaultVLIWScheduler;
43 // --------------------------------------------------------------------
44 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp
46 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput.
47 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer.
49 // e.g. terms x resource bit combinations that fit in uint32_t:
50 // 4 terms x 8 bits = 32 bits
51 // 3 terms x 10 bits = 30 bits
52 // 2 terms x 16 bits = 32 bits
54 // e.g. terms x resource bit combinations that fit in uint64_t:
55 // 8 terms x 8 bits = 64 bits
56 // 7 terms x 9 bits = 63 bits
57 // 6 terms x 10 bits = 60 bits
58 // 5 terms x 12 bits = 60 bits
59 // 4 terms x 16 bits = 64 bits <--- current
60 // 3 terms x 21 bits = 63 bits
61 // 2 terms x 32 bits = 64 bits
63 #define DFA_MAX_RESTERMS 4 // The max # of AND'ed resource terms.
64 #define DFA_MAX_RESOURCES 16 // The max # of resource bits in one term.
66 typedef uint64_t DFAInput;
67 typedef int64_t DFAStateInput;
68 #define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable.
69 // --------------------------------------------------------------------
73 typedef std::pair<unsigned, DFAInput> UnsignPair;
75 const InstrItineraryData *InstrItins;
77 const DFAStateInput (*DFAStateInputTable)[2];
78 const unsigned *DFAStateEntryTable;
80 // CachedTable is a map from <FromState, Input> to ToState.
81 DenseMap<UnsignPair, unsigned> CachedTable;
83 // ReadTable - Read the DFA transition table and update CachedTable.
84 void ReadTable(unsigned state);
87 DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2],
90 // Reset the current state to make all resources available.
91 void clearResources() {
95 // getInsnInput - Return the DFAInput for an instruction class.
96 DFAInput getInsnInput(unsigned InsnClass);
98 // getInsnInput - Return the DFAInput for an instruction class input vector.
99 static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass);
101 // canReserveResources - Check if the resources occupied by a MCInstrDesc
102 // are available in the current state.
103 bool canReserveResources(const llvm::MCInstrDesc *MID);
105 // reserveResources - Reserve the resources occupied by a MCInstrDesc and
106 // change the current state to reflect that change.
107 void reserveResources(const llvm::MCInstrDesc *MID);
109 // canReserveResources - Check if the resources occupied by a machine
110 // instruction are available in the current state.
111 bool canReserveResources(llvm::MachineInstr *MI);
113 // reserveResources - Reserve the resources occupied by a machine
114 // instruction and change the current state to reflect that change.
115 void reserveResources(llvm::MachineInstr *MI);
117 const InstrItineraryData *getInstrItins() const { return InstrItins; }
120 // VLIWPacketizerList - Implements a simple VLIW packetizer using DFA. The
121 // packetizer works on machine basic blocks. For each instruction I in BB, the
122 // packetizer consults the DFA to see if machine resources are available to
123 // execute I. If so, the packetizer checks if I depends on any instruction J in
124 // the current packet. If no dependency is found, I is added to current packet
125 // and machine resource is marked as taken. If any dependency is found, a target
126 // API call is made to prune the dependence.
127 class VLIWPacketizerList {
130 const TargetInstrInfo *TII;
133 // The VLIW Scheduler.
134 DefaultVLIWScheduler *VLIWScheduler;
136 // Vector of instructions assigned to the current packet.
137 std::vector<MachineInstr*> CurrentPacketMIs;
138 // DFA resource tracker.
139 DFAPacketizer *ResourceTracker;
141 // Generate MI -> SU map.
142 std::map<MachineInstr*, SUnit*> MIToSUnit;
145 // The AliasAnalysis parameter can be nullptr.
146 VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI,
149 virtual ~VLIWPacketizerList();
151 // PacketizeMIs - Implement this API in the backend to bundle instructions.
152 void PacketizeMIs(MachineBasicBlock *MBB,
153 MachineBasicBlock::iterator BeginItr,
154 MachineBasicBlock::iterator EndItr);
156 // getResourceTracker - return ResourceTracker
157 DFAPacketizer *getResourceTracker() {return ResourceTracker;}
159 // addToPacket - Add MI to the current packet.
160 virtual MachineBasicBlock::iterator addToPacket(MachineInstr *MI) {
161 MachineBasicBlock::iterator MII = MI;
162 CurrentPacketMIs.push_back(MI);
163 ResourceTracker->reserveResources(MI);
167 // End the current packet and reset the state of the packetizer.
168 // Overriding this function allows the target-specific packetizer
169 // to perform custom finalization.
170 virtual void endPacket(MachineBasicBlock *MBB, MachineInstr *MI);
172 // initPacketizerState - perform initialization before packetizing
173 // an instruction. This function is supposed to be overrided by
174 // the target dependent packetizer.
175 virtual void initPacketizerState() { return; }
177 // ignorePseudoInstruction - Ignore bundling of pseudo instructions.
178 virtual bool ignorePseudoInstruction(const MachineInstr *I,
179 const MachineBasicBlock *MBB) {
183 // isSoloInstruction - return true if instruction MI can not be packetized
184 // with any other instruction, which means that MI itself is a packet.
185 virtual bool isSoloInstruction(const MachineInstr *MI) {
189 // Check if the packetizer should try to add the given instruction to
190 // the current packet. One reasons for which it may not be desirable
191 // to include an instruction in the current packet could be that it
192 // would cause a stall.
193 // If this function returns "false", the current packet will be ended,
194 // and the instruction will be added to the next packet.
195 virtual bool shouldAddToPacket(const MachineInstr *MI) {
199 // isLegalToPacketizeTogether - Is it legal to packetize SUI and SUJ
201 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
205 // isLegalToPruneDependencies - Is it legal to prune dependece between SUI
207 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {