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