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 #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. clearResources()97 void clearResources() { 98 CurrentState = 0; 99 } 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 getInstrItins()123 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. getResourceTracker()161 DFAPacketizer *getResourceTracker() {return ResourceTracker;} 162 163 // addToPacket - Add MI to the current packet. addToPacket(MachineInstr & MI)164 virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) { 165 CurrentPacketMIs.push_back(&MI); 166 ResourceTracker->reserveResources(MI); 167 return MI; 168 } 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. initPacketizerState()178 virtual void initPacketizerState() {} 179 180 // Check if the given instruction I should be ignored by the packetizer. ignorePseudoInstruction(const MachineInstr & I,const MachineBasicBlock * MBB)181 virtual bool ignorePseudoInstruction(const MachineInstr &I, 182 const MachineBasicBlock *MBB) { 183 return false; 184 } 185 186 // Return true if instruction MI can not be packetized with any other 187 // instruction, which means that MI itself is a packet. isSoloInstruction(const MachineInstr & MI)188 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. shouldAddToPacket(const MachineInstr & MI)196 virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; } 197 198 // Check if it is legal to packetize SUI and SUJ together. isLegalToPacketizeTogether(SUnit * SUI,SUnit * SUJ)199 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) { 200 return false; 201 } 202 203 // Check if it is legal to prune dependece between SUI and SUJ. isLegalToPruneDependencies(SUnit * SUI,SUnit * SUJ)204 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) { 205 return false; 206 } 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 222