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