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