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 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. clearResources()98 void clearResources() { 99 CurrentState = 0; 100 } 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 getInstrItins()124 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. getResourceTracker()162 DFAPacketizer *getResourceTracker() {return ResourceTracker;} 163 164 // addToPacket - Add MI to the current packet. addToPacket(MachineInstr & MI)165 virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) { 166 CurrentPacketMIs.push_back(&MI); 167 ResourceTracker->reserveResources(MI); 168 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. initPacketizerState()179 virtual void initPacketizerState() {} 180 181 // Check if the given instruction I should be ignored by the packetizer. ignorePseudoInstruction(const MachineInstr & I,const MachineBasicBlock * MBB)182 virtual bool ignorePseudoInstruction(const MachineInstr &I, 183 const MachineBasicBlock *MBB) { 184 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. isSoloInstruction(const MachineInstr & MI)189 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. shouldAddToPacket(const MachineInstr & MI)197 virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; } 198 199 // Check if it is legal to packetize SUI and SUJ together. isLegalToPacketizeTogether(SUnit * SUI,SUnit * SUJ)200 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) { 201 return false; 202 } 203 204 // Check if it is legal to prune dependece between SUI and SUJ. isLegalToPruneDependencies(SUnit * SUI,SUnit * SUJ)205 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) { 206 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 223