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 "llvm/Support/Automaton.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 const InstrItineraryData *InstrItins; 81 Automaton<DFAInput> A; 82 83 public: 84 DFAPacketizer(const InstrItineraryData *InstrItins, Automaton<uint64_t> a) : 85 InstrItins(InstrItins), A(std::move(a)) { 86 // Start off with resource tracking disabled. 87 A.enableTranscription(false); 88 } 89 90 // Reset the current state to make all resources available. 91 void clearResources() { 92 A.reset(); 93 } 94 95 // Set whether this packetizer should track not just whether instructions 96 // can be packetized, but also which functional units each instruction ends up 97 // using after packetization. 98 void setTrackResources(bool Track) { 99 A.enableTranscription(Track); 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 124 // Return the resources used by the InstIdx'th instruction added to this 125 // packet. The resources are returned as a bitvector of functional units. 126 // 127 // Note that a bundle may be packed in multiple valid ways. This function 128 // returns one arbitary valid packing. 129 // 130 // Requires setTrackResources(true) to have been called. 131 unsigned getUsedResources(unsigned InstIdx); 132 133 const InstrItineraryData *getInstrItins() const { return InstrItins; } 134 }; 135 136 // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The 137 // packetizer works on machine basic blocks. For each instruction I in BB, 138 // the packetizer consults the DFA to see if machine resources are available 139 // to execute I. If so, the packetizer checks if I depends on any instruction 140 // in the current packet. If no dependency is found, I is added to current 141 // packet and the machine resource is marked as taken. If any dependency is 142 // found, a target API call is made to prune the dependence. 143 class VLIWPacketizerList { 144 protected: 145 MachineFunction &MF; 146 const TargetInstrInfo *TII; 147 AliasAnalysis *AA; 148 149 // The VLIW Scheduler. 150 DefaultVLIWScheduler *VLIWScheduler; 151 // Vector of instructions assigned to the current packet. 152 std::vector<MachineInstr*> CurrentPacketMIs; 153 // DFA resource tracker. 154 DFAPacketizer *ResourceTracker; 155 // Map: MI -> SU. 156 std::map<MachineInstr*, SUnit*> MIToSUnit; 157 158 public: 159 // The AliasAnalysis parameter can be nullptr. 160 VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI, 161 AliasAnalysis *AA); 162 163 virtual ~VLIWPacketizerList(); 164 165 // Implement this API in the backend to bundle instructions. 166 void PacketizeMIs(MachineBasicBlock *MBB, 167 MachineBasicBlock::iterator BeginItr, 168 MachineBasicBlock::iterator EndItr); 169 170 // Return the ResourceTracker. 171 DFAPacketizer *getResourceTracker() {return ResourceTracker;} 172 173 // addToPacket - Add MI to the current packet. 174 virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) { 175 CurrentPacketMIs.push_back(&MI); 176 ResourceTracker->reserveResources(MI); 177 return MI; 178 } 179 180 // End the current packet and reset the state of the packetizer. 181 // Overriding this function allows the target-specific packetizer 182 // to perform custom finalization. 183 virtual void endPacket(MachineBasicBlock *MBB, 184 MachineBasicBlock::iterator MI); 185 186 // Perform initialization before packetizing an instruction. This 187 // function is supposed to be overrided by the target dependent packetizer. 188 virtual void initPacketizerState() {} 189 190 // Check if the given instruction I should be ignored by the packetizer. 191 virtual bool ignorePseudoInstruction(const MachineInstr &I, 192 const MachineBasicBlock *MBB) { 193 return false; 194 } 195 196 // Return true if instruction MI can not be packetized with any other 197 // instruction, which means that MI itself is a packet. 198 virtual bool isSoloInstruction(const MachineInstr &MI) { return true; } 199 200 // Check if the packetizer should try to add the given instruction to 201 // the current packet. One reasons for which it may not be desirable 202 // to include an instruction in the current packet could be that it 203 // would cause a stall. 204 // If this function returns "false", the current packet will be ended, 205 // and the instruction will be added to the next packet. 206 virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; } 207 208 // Check if it is legal to packetize SUI and SUJ together. 209 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) { 210 return false; 211 } 212 213 // Check if it is legal to prune dependece between SUI and SUJ. 214 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) { 215 return false; 216 } 217 218 // Add a DAG mutation to be done before the packetization begins. 219 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation); 220 221 bool alias(const MachineInstr &MI1, const MachineInstr &MI2, 222 bool UseTBAA = true) const; 223 224 private: 225 bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2, 226 bool UseTBAA = true) const; 227 }; 228 229 } // end namespace llvm 230 231 #endif // LLVM_CODEGEN_DFAPACKETIZER_H 232