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/CodeGen/MachineBasicBlock.h" 29 #include "llvm/Support/Automaton.h" 30 #include <cstdint> 31 #include <map> 32 #include <memory> 33 #include <utility> 34 #include <vector> 35 36 namespace llvm { 37 38 class DefaultVLIWScheduler; 39 class ScheduleDAGMutation; 40 class InstrItineraryData; 41 class MachineFunction; 42 class MachineInstr; 43 class MachineLoopInfo; 44 class MCInstrDesc; 45 class SUnit; 46 class TargetInstrInfo; 47 48 class DFAPacketizer { 49 private: 50 const InstrItineraryData *InstrItins; 51 Automaton<uint64_t> A; 52 /// For every itinerary, an "action" to apply to the automaton. This removes 53 /// the redundancy in actions between itinerary classes. 54 ArrayRef<unsigned> ItinActions; 55 56 public: 57 DFAPacketizer(const InstrItineraryData *InstrItins, Automaton<uint64_t> a, 58 ArrayRef<unsigned> ItinActions) 59 : InstrItins(InstrItins), A(std::move(a)), ItinActions(ItinActions) { 60 // Start off with resource tracking disabled. 61 A.enableTranscription(false); 62 } 63 64 // Reset the current state to make all resources available. 65 void clearResources() { 66 A.reset(); 67 } 68 69 // Set whether this packetizer should track not just whether instructions 70 // can be packetized, but also which functional units each instruction ends up 71 // using after packetization. 72 void setTrackResources(bool Track) { 73 A.enableTranscription(Track); 74 } 75 76 // Check if the resources occupied by a MCInstrDesc are available in 77 // the current state. 78 bool canReserveResources(const MCInstrDesc *MID); 79 80 // Reserve the resources occupied by a MCInstrDesc and change the current 81 // state to reflect that change. 82 void reserveResources(const MCInstrDesc *MID); 83 84 // Check if the resources occupied by a machine instruction are available 85 // in the current state. 86 bool canReserveResources(MachineInstr &MI); 87 88 // Reserve the resources occupied by a machine instruction and change the 89 // current state to reflect that change. 90 void reserveResources(MachineInstr &MI); 91 92 // Return the resources used by the InstIdx'th instruction added to this 93 // packet. The resources are returned as a bitvector of functional units. 94 // 95 // Note that a bundle may be packed in multiple valid ways. This function 96 // returns one arbitary valid packing. 97 // 98 // Requires setTrackResources(true) to have been called. 99 unsigned getUsedResources(unsigned InstIdx); 100 101 const InstrItineraryData *getInstrItins() const { return InstrItins; } 102 }; 103 104 // VLIWPacketizerList implements a simple VLIW packetizer using DFA. The 105 // packetizer works on machine basic blocks. For each instruction I in BB, 106 // the packetizer consults the DFA to see if machine resources are available 107 // to execute I. If so, the packetizer checks if I depends on any instruction 108 // in the current packet. If no dependency is found, I is added to current 109 // packet and the machine resource is marked as taken. If any dependency is 110 // found, a target API call is made to prune the dependence. 111 class VLIWPacketizerList { 112 protected: 113 MachineFunction &MF; 114 const TargetInstrInfo *TII; 115 AAResults *AA; 116 117 // The VLIW Scheduler. 118 DefaultVLIWScheduler *VLIWScheduler; 119 // Vector of instructions assigned to the current packet. 120 std::vector<MachineInstr*> CurrentPacketMIs; 121 // DFA resource tracker. 122 DFAPacketizer *ResourceTracker; 123 // Map: MI -> SU. 124 std::map<MachineInstr*, SUnit*> MIToSUnit; 125 126 public: 127 // The AAResults parameter can be nullptr. 128 VLIWPacketizerList(MachineFunction &MF, MachineLoopInfo &MLI, 129 AAResults *AA); 130 131 virtual ~VLIWPacketizerList(); 132 133 // Implement this API in the backend to bundle instructions. 134 void PacketizeMIs(MachineBasicBlock *MBB, 135 MachineBasicBlock::iterator BeginItr, 136 MachineBasicBlock::iterator EndItr); 137 138 // Return the ResourceTracker. 139 DFAPacketizer *getResourceTracker() {return ResourceTracker;} 140 141 // addToPacket - Add MI to the current packet. 142 virtual MachineBasicBlock::iterator addToPacket(MachineInstr &MI) { 143 CurrentPacketMIs.push_back(&MI); 144 ResourceTracker->reserveResources(MI); 145 return MI; 146 } 147 148 // End the current packet and reset the state of the packetizer. 149 // Overriding this function allows the target-specific packetizer 150 // to perform custom finalization. 151 virtual void endPacket(MachineBasicBlock *MBB, 152 MachineBasicBlock::iterator MI); 153 154 // Perform initialization before packetizing an instruction. This 155 // function is supposed to be overrided by the target dependent packetizer. 156 virtual void initPacketizerState() {} 157 158 // Check if the given instruction I should be ignored by the packetizer. 159 virtual bool ignorePseudoInstruction(const MachineInstr &I, 160 const MachineBasicBlock *MBB) { 161 return false; 162 } 163 164 // Return true if instruction MI can not be packetized with any other 165 // instruction, which means that MI itself is a packet. 166 virtual bool isSoloInstruction(const MachineInstr &MI) { return true; } 167 168 // Check if the packetizer should try to add the given instruction to 169 // the current packet. One reasons for which it may not be desirable 170 // to include an instruction in the current packet could be that it 171 // would cause a stall. 172 // If this function returns "false", the current packet will be ended, 173 // and the instruction will be added to the next packet. 174 virtual bool shouldAddToPacket(const MachineInstr &MI) { return true; } 175 176 // Check if it is legal to packetize SUI and SUJ together. 177 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) { 178 return false; 179 } 180 181 // Check if it is legal to prune dependece between SUI and SUJ. 182 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) { 183 return false; 184 } 185 186 // Add a DAG mutation to be done before the packetization begins. 187 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation); 188 189 bool alias(const MachineInstr &MI1, const MachineInstr &MI2, 190 bool UseTBAA = true) const; 191 192 private: 193 bool alias(const MachineMemOperand &Op1, const MachineMemOperand &Op2, 194 bool UseTBAA = true) const; 195 }; 196 197 } // end namespace llvm 198 199 #endif // LLVM_CODEGEN_DFAPACKETIZER_H 200