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 #define DEBUG_TYPE "packets" 27 28 #include "llvm/CodeGen/DFAPacketizer.h" 29 #include "llvm/CodeGen/MachineInstr.h" 30 #include "llvm/CodeGen/MachineInstrBundle.h" 31 #include "llvm/CodeGen/ScheduleDAGInstrs.h" 32 #include "llvm/MC/MCInstrItineraries.h" 33 #include "llvm/Target/TargetInstrInfo.h" 34 #include "llvm/Support/CommandLine.h" 35 36 using namespace llvm; 37 38 static cl::opt<unsigned> InstrLimit("dfa-instr-limit", cl::Hidden, 39 cl::init(0), cl::desc("If present, stops packetizing after N instructions")); 40 static unsigned InstrCount = 0; 41 42 // -------------------------------------------------------------------- 43 // Definitions shared between DFAPacketizer.cpp and DFAPacketizerEmitter.cpp 44 45 namespace { 46 DFAInput addDFAFuncUnits(DFAInput Inp, unsigned FuncUnits) { 47 return (Inp << DFA_MAX_RESOURCES) | FuncUnits; 48 } 49 50 /// Return the DFAInput for an instruction class input vector. 51 /// This function is used in both DFAPacketizer.cpp and in 52 /// DFAPacketizerEmitter.cpp. 53 DFAInput getDFAInsnInput(const std::vector<unsigned> &InsnClass) { 54 DFAInput InsnInput = 0; 55 assert((InsnClass.size() <= DFA_MAX_RESTERMS) && 56 "Exceeded maximum number of DFA terms"); 57 for (auto U : InsnClass) 58 InsnInput = addDFAFuncUnits(InsnInput, U); 59 return InsnInput; 60 } 61 } 62 // -------------------------------------------------------------------- 63 64 DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, 65 const DFAStateInput (*SIT)[2], 66 const unsigned *SET): 67 InstrItins(I), CurrentState(0), DFAStateInputTable(SIT), 68 DFAStateEntryTable(SET) { 69 // Make sure DFA types are large enough for the number of terms & resources. 70 static_assert((DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= 71 (8 * sizeof(DFAInput)), 72 "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAInput"); 73 static_assert( 74 (DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) <= (8 * sizeof(DFAStateInput)), 75 "(DFA_MAX_RESTERMS * DFA_MAX_RESOURCES) too big for DFAStateInput"); 76 } 77 78 79 // Read the DFA transition table and update CachedTable. 80 // 81 // Format of the transition tables: 82 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 83 // transitions 84 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable 85 // for the ith state 86 // 87 void DFAPacketizer::ReadTable(unsigned int state) { 88 unsigned ThisState = DFAStateEntryTable[state]; 89 unsigned NextStateInTable = DFAStateEntryTable[state+1]; 90 // Early exit in case CachedTable has already contains this 91 // state's transitions. 92 if (CachedTable.count(UnsignPair(state, DFAStateInputTable[ThisState][0]))) 93 return; 94 95 for (unsigned i = ThisState; i < NextStateInTable; i++) 96 CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] = 97 DFAStateInputTable[i][1]; 98 } 99 100 101 // Return the DFAInput for an instruction class. 102 DFAInput DFAPacketizer::getInsnInput(unsigned InsnClass) { 103 // Note: this logic must match that in DFAPacketizerDefs.h for input vectors. 104 DFAInput InsnInput = 0; 105 unsigned i = 0; 106 (void)i; 107 for (const InstrStage *IS = InstrItins->beginStage(InsnClass), 108 *IE = InstrItins->endStage(InsnClass); IS != IE; ++IS) { 109 InsnInput = addDFAFuncUnits(InsnInput, IS->getUnits()); 110 assert((i++ < DFA_MAX_RESTERMS) && "Exceeded maximum number of DFA inputs"); 111 } 112 return InsnInput; 113 } 114 115 116 // Return the DFAInput for an instruction class input vector. 117 DFAInput DFAPacketizer::getInsnInput(const std::vector<unsigned> &InsnClass) { 118 return getDFAInsnInput(InsnClass); 119 } 120 121 122 // Check if the resources occupied by a MCInstrDesc are available in the 123 // current state. 124 bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc *MID) { 125 unsigned InsnClass = MID->getSchedClass(); 126 DFAInput InsnInput = getInsnInput(InsnClass); 127 UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); 128 ReadTable(CurrentState); 129 return CachedTable.count(StateTrans) != 0; 130 } 131 132 133 // Reserve the resources occupied by a MCInstrDesc and change the current 134 // state to reflect that change. 135 void DFAPacketizer::reserveResources(const llvm::MCInstrDesc *MID) { 136 unsigned InsnClass = MID->getSchedClass(); 137 DFAInput InsnInput = getInsnInput(InsnClass); 138 UnsignPair StateTrans = UnsignPair(CurrentState, InsnInput); 139 ReadTable(CurrentState); 140 assert(CachedTable.count(StateTrans) != 0); 141 CurrentState = CachedTable[StateTrans]; 142 } 143 144 145 // Check if the resources occupied by a machine instruction are available 146 // in the current state. 147 bool DFAPacketizer::canReserveResources(llvm::MachineInstr &MI) { 148 const llvm::MCInstrDesc &MID = MI.getDesc(); 149 return canReserveResources(&MID); 150 } 151 152 153 // Reserve the resources occupied by a machine instruction and change the 154 // current state to reflect that change. 155 void DFAPacketizer::reserveResources(llvm::MachineInstr &MI) { 156 const llvm::MCInstrDesc &MID = MI.getDesc(); 157 reserveResources(&MID); 158 } 159 160 161 namespace llvm { 162 // This class extends ScheduleDAGInstrs and overrides the schedule method 163 // to build the dependence graph. 164 class DefaultVLIWScheduler : public ScheduleDAGInstrs { 165 private: 166 AliasAnalysis *AA; 167 /// Ordered list of DAG postprocessing steps. 168 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; 169 public: 170 DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, 171 AliasAnalysis *AA); 172 // Actual scheduling work. 173 void schedule() override; 174 175 /// DefaultVLIWScheduler takes ownership of the Mutation object. 176 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) { 177 Mutations.push_back(std::move(Mutation)); 178 } 179 protected: 180 void postprocessDAG(); 181 }; 182 } 183 184 185 DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF, 186 MachineLoopInfo &MLI, 187 AliasAnalysis *AA) 188 : ScheduleDAGInstrs(MF, &MLI), AA(AA) { 189 CanHandleTerminators = true; 190 } 191 192 193 /// Apply each ScheduleDAGMutation step in order. 194 void DefaultVLIWScheduler::postprocessDAG() { 195 for (auto &M : Mutations) 196 M->apply(this); 197 } 198 199 200 void DefaultVLIWScheduler::schedule() { 201 // Build the scheduling graph. 202 buildSchedGraph(AA); 203 postprocessDAG(); 204 } 205 206 207 VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf, 208 MachineLoopInfo &mli, AliasAnalysis *aa) 209 : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) { 210 ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget()); 211 VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA); 212 } 213 214 215 VLIWPacketizerList::~VLIWPacketizerList() { 216 if (VLIWScheduler) 217 delete VLIWScheduler; 218 if (ResourceTracker) 219 delete ResourceTracker; 220 } 221 222 223 // End the current packet, bundle packet instructions and reset DFA state. 224 void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB, 225 MachineBasicBlock::iterator MI) { 226 DEBUG({ 227 if (!CurrentPacketMIs.empty()) { 228 dbgs() << "Finalizing packet:\n"; 229 for (MachineInstr *MI : CurrentPacketMIs) 230 dbgs() << " * " << *MI; 231 } 232 }); 233 if (CurrentPacketMIs.size() > 1) { 234 MachineInstr &MIFirst = *CurrentPacketMIs.front(); 235 finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator()); 236 } 237 CurrentPacketMIs.clear(); 238 ResourceTracker->clearResources(); 239 DEBUG(dbgs() << "End packet\n"); 240 } 241 242 243 // Bundle machine instructions into packets. 244 void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB, 245 MachineBasicBlock::iterator BeginItr, 246 MachineBasicBlock::iterator EndItr) { 247 assert(VLIWScheduler && "VLIW Scheduler is not initialized!"); 248 VLIWScheduler->startBlock(MBB); 249 VLIWScheduler->enterRegion(MBB, BeginItr, EndItr, 250 std::distance(BeginItr, EndItr)); 251 VLIWScheduler->schedule(); 252 253 DEBUG({ 254 dbgs() << "Scheduling DAG of the packetize region\n"; 255 for (SUnit &SU : VLIWScheduler->SUnits) 256 SU.dumpAll(VLIWScheduler); 257 }); 258 259 // Generate MI -> SU map. 260 MIToSUnit.clear(); 261 for (SUnit &SU : VLIWScheduler->SUnits) 262 MIToSUnit[SU.getInstr()] = &SU; 263 264 bool LimitPresent = InstrLimit.getPosition(); 265 266 // The main packetizer loop. 267 for (; BeginItr != EndItr; ++BeginItr) { 268 if (LimitPresent) { 269 if (InstrCount >= InstrLimit) { 270 EndItr = BeginItr; 271 break; 272 } 273 InstrCount++; 274 } 275 MachineInstr &MI = *BeginItr; 276 initPacketizerState(); 277 278 // End the current packet if needed. 279 if (isSoloInstruction(MI)) { 280 endPacket(MBB, MI); 281 continue; 282 } 283 284 // Ignore pseudo instructions. 285 if (ignorePseudoInstruction(MI, MBB)) 286 continue; 287 288 SUnit *SUI = MIToSUnit[&MI]; 289 assert(SUI && "Missing SUnit Info!"); 290 291 // Ask DFA if machine resource is available for MI. 292 DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI); 293 294 bool ResourceAvail = ResourceTracker->canReserveResources(MI); 295 DEBUG({ 296 if (ResourceAvail) 297 dbgs() << " Resources are available for adding MI to packet\n"; 298 else 299 dbgs() << " Resources NOT available\n"; 300 }); 301 if (ResourceAvail && shouldAddToPacket(MI)) { 302 // Dependency check for MI with instructions in CurrentPacketMIs. 303 for (auto MJ : CurrentPacketMIs) { 304 SUnit *SUJ = MIToSUnit[MJ]; 305 assert(SUJ && "Missing SUnit Info!"); 306 307 DEBUG(dbgs() << " Checking against MJ " << *MJ); 308 // Is it legal to packetize SUI and SUJ together. 309 if (!isLegalToPacketizeTogether(SUI, SUJ)) { 310 DEBUG(dbgs() << " Not legal to add MI, try to prune\n"); 311 // Allow packetization if dependency can be pruned. 312 if (!isLegalToPruneDependencies(SUI, SUJ)) { 313 // End the packet if dependency cannot be pruned. 314 DEBUG(dbgs() << " Could not prune dependencies for adding MI\n"); 315 endPacket(MBB, MI); 316 break; 317 } 318 DEBUG(dbgs() << " Pruned dependence for adding MI\n"); 319 } 320 } 321 } else { 322 DEBUG(if (ResourceAvail) 323 dbgs() << "Resources are available, but instruction should not be " 324 "added to packet\n " << MI); 325 // End the packet if resource is not available, or if the instruction 326 // shoud not be added to the current packet. 327 endPacket(MBB, MI); 328 } 329 330 // Add MI to the current packet. 331 DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n'); 332 BeginItr = addToPacket(MI); 333 } // For all instructions in the packetization range. 334 335 // End any packet left behind. 336 endPacket(MBB, EndItr); 337 VLIWScheduler->exitRegion(); 338 VLIWScheduler->finishBlock(); 339 } 340 341 342 // Add a DAG mutation object to the ordered list. 343 void VLIWPacketizerList::addMutation( 344 std::unique_ptr<ScheduleDAGMutation> Mutation) { 345 VLIWScheduler->addMutation(std::move(Mutation)); 346 } 347