1 //=- llvm/CodeGen/DFAPacketizer.cpp - 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 #include "llvm/CodeGen/DFAPacketizer.h" 27 #include "llvm/CodeGen/MachineInstr.h" 28 #include "llvm/CodeGen/MachineInstrBundle.h" 29 #include "llvm/CodeGen/ScheduleDAGInstrs.h" 30 #include "llvm/MC/MCInstrItineraries.h" 31 #include "llvm/Target/TargetInstrInfo.h" 32 33 using namespace llvm; 34 35 // -------------------------------------------------------------------- 36 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp 37 38 namespace { 39 DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) { 40 return (Inp << DFA_MAX_RESOURCES) | FuncUnits; 41 } 42 43 /// Return the DFAInput for an instruction class input vector. 44 /// This function is used in both DFAPacketizer.cpp and in 45 /// DFAPacketizerEmitter.cpp. 46 DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) { 47 DFAInput InsnInput = 0; 48 assert((InsnClass.size() <= DFA_MAX_RESTERMS) && 49 "Exceeded maximum number of DFA terms"); 50 for (auto U : InsnClass) 51 InsnInput = addDFAFuncUnits(InsnInput, U); 52 return InsnInput; 53 } 54 } 55 // -------------------------------------------------------------------- 56 57 DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, 58 const DFAStateInput (*SIT)[2], 59 const unsigned *SET): 60 InstrItins(I), CurrentState(0), DFAStateInputTable(SIT), 61 DFAStateEntryTable(SET) { 62 // Make sure DFA types are large enough for the number of terms & resources. 63 assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAInput)) 64 && "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput"); 65 assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)) 66 && "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput"); 67 } 68 69 70 // Read the DFA transition table and update CachedTable. 71 // 72 // Format of the transition tables: 73 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 74 // transitions 75 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable 76 // for the ith state 77 // 78 void DFAPacketizer::ReadTable(unsigned int state) { 79 unsigned ThisState = DFAStateEntryTable[state]; 80 unsigned NextStateInTable = DFAStateEntryTable[state+1]; 81 // Early exit in case CachedTable has already contains this 82 // state's transitions. 83 if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0]))) 84 return; 85 86 for (unsigned i = ThisState; i < NextStateInTable; i++) 87 CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] = 88 DFAStateInputTable[i][1]; 89 } 90 91 92 // Return the DFAInput for an instruction class. 93 DFAInput DFAPacketizer::getInsnInput(unsigned InsnClass) { 94 // Note: this logic must match that in DFAPacketizerDefs.h for input vectors. 95 DFAInput InsnInput = 0; 96 unsigned i = 0; 97 (void)i; 98 for (const InstrStage *IS = InstrItins->beginStage(InsnClass), 99 *IE = InstrItins->endStage(InsnClass); IS != IE; ++IS) { 100 InsnInput = addDFAFuncUnits(InsnInput, IS->getUnits()); 101 assert((i++ < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs"); 102 } 103 return InsnInput; 104 } 105 106 107 // Return the DFAInput for an instruction class input vector. 108 DFAInput DFAPacketizer::getInsnInput(const std::vector<unsigned> &InsnClass) { 109 return getDFAInsnInput(InsnClass); 110 } 111 112 113 // Check if the resources occupied by a MCInstrDesc are available in the 114 // current state. 115 bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc *MID) { 116 unsigned InsnClass = MID->getSchedClass(); 117 DFAInput InsnInput = getInsnInput(InsnClass); 118 UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); 119 ReadTable(CurrentState); 120 return CachedTable.count(StateTrans) != 0; 121 } 122 123 124 // Reserve the resources occupied by a MCInstrDesc and change the current 125 // state to reflect that change. 126 void DFAPacketizer::reserveResources(const llvm::MCInstrDesc *MID) { 127 unsigned InsnClass = MID->getSchedClass(); 128 DFAInput InsnInput = getInsnInput(InsnClass); 129 UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); 130 ReadTable(CurrentState); 131 assert(CachedTable.count(StateTrans) != 0); 132 CurrentState = CachedTable[StateTrans]; 133 } 134 135 136 // Check if the resources occupied by a machine instruction are available 137 // in the current state. 138 bool DFAPacketizer::canReserveResources(llvm::MachineInstr *MI) { 139 const llvm::MCInstrDesc &MID = MI->getDesc(); 140 return canReserveResources(&MID); 141 } 142 143 144 // Reserve the resources occupied by a machine instruction and change the 145 // current state to reflect that change. 146 void DFAPacketizer::reserveResources(llvm::MachineInstr *MI) { 147 const llvm::MCInstrDesc &MID = MI->getDesc(); 148 reserveResources(&MID); 149 } 150 151 152 namespace llvm { 153 // This class extends ScheduleDAGInstrs and overrides the schedule method 154 // to build the dependence graph. 155 class DefaultVLIWScheduler : public ScheduleDAGInstrs { 156 private: 157 AliasAnalysis *AA; 158 public: 159 DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, 160 AliasAnalysis *AA); 161 // Actual scheduling work. 162 void schedule() override; 163 }; 164 } 165 166 167 DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF, 168 MachineLoopInfo &MLI, 169 AliasAnalysis *AA) 170 : ScheduleDAGInstrs(MF, &MLI), AA(AA) { 171 CanHandleTerminators = true; 172 } 173 174 175 void DefaultVLIWScheduler::schedule() { 176 // Build the scheduling graph. 177 buildSchedGraph(AA); 178 } 179 180 181 VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf, 182 MachineLoopInfo &mli, AliasAnalysis *aa) 183 : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) { 184 ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget()); 185 VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA); 186 } 187 188 189 VLIWPacketizerList::~VLIWPacketizerList() { 190 if (VLIWScheduler) 191 delete VLIWScheduler; 192 if (ResourceTracker) 193 delete ResourceTracker; 194 } 195 196 197 // End the current packet, bundle packet instructions and reset DFA state. 198 void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB, MachineInstr *MI) { 199 if (CurrentPacketMIs.size() > 1) { 200 MachineInstr *MIFirst = CurrentPacketMIs.front(); 201 finalizeBundle(*MBB, MIFirst->getIterator(), MI->getIterator()); 202 } 203 CurrentPacketMIs.clear(); 204 ResourceTracker->clearResources(); 205 } 206 207 208 // Bundle machine instructions into packets. 209 void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB, 210 MachineBasicBlock::iterator BeginItr, 211 MachineBasicBlock::iterator EndItr) { 212 assert(VLIWScheduler && "VLIW Scheduler is not initialized!"); 213 VLIWScheduler->startBlock(MBB); 214 VLIWScheduler->enterRegion(MBB, BeginItr, EndItr, 215 std::distance(BeginItr, EndItr)); 216 VLIWScheduler->schedule(); 217 218 // Generate MI -> SU map. 219 MIToSUnit.clear(); 220 for (SUnit &SU : VLIWScheduler->SUnits) 221 MIToSUnit[SU.getInstr()] = &SU; 222 223 // The main packetizer loop. 224 for (; BeginItr != EndItr; ++BeginItr) { 225 MachineInstr *MI = BeginItr; 226 initPacketizerState(); 227 228 // End the current packet if needed. 229 if (isSoloInstruction(MI)) { 230 endPacket(MBB, MI); 231 continue; 232 } 233 234 // Ignore pseudo instructions. 235 if (ignorePseudoInstruction(MI, MBB)) 236 continue; 237 238 SUnit *SUI = MIToSUnit[MI]; 239 assert(SUI && "Missing SUnit Info!"); 240 241 // Ask DFA if machine resource is available for MI. 242 bool ResourceAvail = ResourceTracker->canReserveResources(MI); 243 if (ResourceAvail && shouldAddToPacket(MI)) { 244 // Dependency check for MI with instructions in CurrentPacketMIs. 245 for (auto MJ : CurrentPacketMIs) { 246 SUnit *SUJ = MIToSUnit[MJ]; 247 assert(SUJ && "Missing SUnit Info!"); 248 249 // Is it legal to packetize SUI and SUJ together. 250 if (!isLegalToPacketizeTogether(SUI, SUJ)) { 251 // Allow packetization if dependency can be pruned. 252 if (!isLegalToPruneDependencies(SUI, SUJ)) { 253 // End the packet if dependency cannot be pruned. 254 endPacket(MBB, MI); 255 break; 256 } 257 } 258 } 259 } else { 260 // End the packet if resource is not available, or if the instruction 261 // shoud not be added to the current packet. 262 endPacket(MBB, MI); 263 } 264 265 // Add MI to the current packet. 266 BeginItr = addToPacket(MI); 267 } // For all instructions in the packetization range. 268 269 // End any packet left behind. 270 endPacket(MBB, EndItr); 271 VLIWScheduler->exitRegion(); 272 VLIWScheduler->finishBlock(); 273 } 274