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 <map> 32 33 namespace llvm { 34 35 class MCInstrDesc; 36 class MachineInstr; 37 class MachineLoopInfo; 38 class MachineDominatorTree; 39 class InstrItineraryData; 40 class DefaultVLIWScheduler; 41 class SUnit; 42 43 // -------------------------------------------------------------------- 44 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp 45 46 // DFA_MAX_RESTERMS * DFA_MAX_RESOURCES must fit within sizeof DFAInput. 47 // This is verified in DFAPacketizer.cpp:DFAPacketizer::DFAPacketizer. 48 // 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 53 // 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 62 // 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. 65 66 typedef uint64_t DFAInput; 67 typedef int64_t DFAStateInput; 68 #define DFA_TBLTYPE "int64_t" // For generating DFAStateInputTable. 69 // -------------------------------------------------------------------- 70 71 class DFAPacketizer { 72 private: 73 typedef std::pair<unsigned, DFAInput> UnsignPair; 74 75 const InstrItineraryData *InstrItins; 76 int CurrentState; 77 const DFAStateInput (*DFAStateInputTable)[2]; 78 const unsigned *DFAStateEntryTable; 79 80 // CachedTable is a map from <FromState, Input> to ToState. 81 DenseMap<UnsignPair, unsigned> CachedTable; 82 83 // ReadTable - Read the DFA transition table and update CachedTable. 84 void ReadTable(unsigned state); 85 86 public: 87 DFAPacketizer(const InstrItineraryData *I, const DFAStateInput (*SIT)[2], 88 const unsigned *SET); 89 90 // Reset the current state to make all resources available. 91 void clearResources() { 92 CurrentState = 0; 93 } 94 95 // getInsnInput - Return the DFAInput for an instruction class. 96 DFAInput getInsnInput(unsigned InsnClass); 97 98 // getInsnInput - Return the DFAInput for an instruction class input vector. 99 static DFAInput getInsnInput(const std::vector<unsigned> &InsnClass); 100 101 // canReserveResources - Check if the resources occupied by a MCInstrDesc 102 // are available in the current state. 103 bool canReserveResources(const llvm::MCInstrDesc *MID); 104 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); 108 109 // canReserveResources - Check if the resources occupied by a machine 110 // instruction are available in the current state. 111 bool canReserveResources(llvm::MachineInstr *MI); 112 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); 116 117 const InstrItineraryData *getInstrItins() const { return InstrItins; } 118 }; 119 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 { 128 protected: 129 MachineFunction &MF; 130 const TargetInstrInfo *TII; 131 AliasAnalysis *AA; 132 133 // The VLIW Scheduler. 134 DefaultVLIWScheduler *VLIWScheduler; 135 136 // Vector of instructions assigned to the current packet. 137 std::vector<MachineInstr*> CurrentPacketMIs; 138 // DFA resource tracker. 139 DFAPacketizer *ResourceTracker; 140 141 // Generate MI -> SU map. 142 std::map<MachineInstr*, SUnit*> MIToSUnit; 143 144 public: 145 // The AliasAnalysis parameter can be nullptr. 146 VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI, 147 AliasAnalysis *AA); 148 149 virtual ~VLIWPacketizerList(); 150 151 // PacketizeMIs - Implement this API in the backend to bundle instructions. 152 void PacketizeMIs(MachineBasicBlock *MBB, 153 MachineBasicBlock::iterator BeginItr, 154 MachineBasicBlock::iterator EndItr); 155 156 // getResourceTracker - return ResourceTracker 157 DFAPacketizer *getResourceTracker() {return ResourceTracker;} 158 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); 164 return MII; 165 } 166 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); 171 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; } 176 177 // ignorePseudoInstruction - Ignore bundling of pseudo instructions. 178 virtual bool ignorePseudoInstruction(const MachineInstr *I, 179 const MachineBasicBlock *MBB) { 180 return false; 181 } 182 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) { 186 return true; 187 } 188 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) { 196 return true; 197 } 198 199 // isLegalToPacketizeTogether - Is it legal to packetize SUI and SUJ 200 // together. 201 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) { 202 return false; 203 } 204 205 // isLegalToPruneDependencies - Is it legal to prune dependece between SUI 206 // and SUJ. 207 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) { 208 return false; 209 } 210 211 }; 212 } 213 214 #endif 215
