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 // Check if the resources occupied by a MCInstrDesc are available in the 56 // current state. 57 bool DFAPacketizer::canReserveResources(const MCInstrDesc *MID) { 58 unsigned Action = ItinActions[MID->getSchedClass()]; 59 if (MID->getSchedClass() == 0 || Action == 0) 60 return false; 61 return A.canAdd(Action); 62 } 63 64 // Reserve the resources occupied by a MCInstrDesc and change the current 65 // state to reflect that change. 66 void DFAPacketizer::reserveResources(const MCInstrDesc *MID) { 67 unsigned Action = ItinActions[MID->getSchedClass()]; 68 if (MID->getSchedClass() == 0 || Action == 0) 69 return; 70 A.add(Action); 71 } 72 73 // Check if the resources occupied by a machine instruction are available 74 // in the current state. 75 bool DFAPacketizer::canReserveResources(MachineInstr &MI) { 76 const MCInstrDesc &MID = MI.getDesc(); 77 return canReserveResources(&MID); 78 } 79 80 // Reserve the resources occupied by a machine instruction and change the 81 // current state to reflect that change. 82 void DFAPacketizer::reserveResources(MachineInstr &MI) { 83 const MCInstrDesc &MID = MI.getDesc(); 84 reserveResources(&MID); 85 } 86 87 unsigned DFAPacketizer::getUsedResources(unsigned InstIdx) { 88 ArrayRef<NfaPath> NfaPaths = A.getNfaPaths(); 89 assert(!NfaPaths.empty() && "Invalid bundle!"); 90 const NfaPath &RS = NfaPaths.front(); 91 92 // RS stores the cumulative resources used up to and including the I'th 93 // instruction. The 0th instruction is the base case. 94 if (InstIdx == 0) 95 return RS[0]; 96 // Return the difference between the cumulative resources used by InstIdx and 97 // its predecessor. 98 return RS[InstIdx] ^ RS[InstIdx - 1]; 99 } 100 101 namespace llvm { 102 103 // This class extends ScheduleDAGInstrs and overrides the schedule method 104 // to build the dependence graph. 105 class DefaultVLIWScheduler : public ScheduleDAGInstrs { 106 private: 107 AAResults *AA; 108 /// Ordered list of DAG postprocessing steps. 109 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations; 110 111 public: 112 DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, 113 AAResults *AA); 114 115 // Actual scheduling work. 116 void schedule() override; 117 118 /// DefaultVLIWScheduler takes ownership of the Mutation object. 119 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) { 120 Mutations.push_back(std::move(Mutation)); 121 } 122 123 protected: 124 void postprocessDAG(); 125 }; 126 127 } // end namespace llvm 128 129 DefaultVLIWScheduler::DefaultVLIWScheduler(MachineFunction &MF, 130 MachineLoopInfo &MLI, 131 AAResults *AA) 132 : ScheduleDAGInstrs(MF, &MLI), AA(AA) { 133 CanHandleTerminators = true; 134 } 135 136 /// Apply each ScheduleDAGMutation step in order. 137 void DefaultVLIWScheduler::postprocessDAG() { 138 for (auto &M : Mutations) 139 M->apply(this); 140 } 141 142 void DefaultVLIWScheduler::schedule() { 143 // Build the scheduling graph. 144 buildSchedGraph(AA); 145 postprocessDAG(); 146 } 147 148 VLIWPacketizerList::VLIWPacketizerList(MachineFunction &mf, 149 MachineLoopInfo &mli, AAResults *aa) 150 : MF(mf), TII(mf.getSubtarget().getInstrInfo()), AA(aa) { 151 ResourceTracker = TII->CreateTargetScheduleState(MF.getSubtarget()); 152 ResourceTracker->setTrackResources(true); 153 VLIWScheduler = new DefaultVLIWScheduler(MF, mli, AA); 154 } 155 156 VLIWPacketizerList::~VLIWPacketizerList() { 157 delete VLIWScheduler; 158 delete ResourceTracker; 159 } 160 161 // End the current packet, bundle packet instructions and reset DFA state. 162 void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB, 163 MachineBasicBlock::iterator MI) { 164 LLVM_DEBUG({ 165 if (!CurrentPacketMIs.empty()) { 166 dbgs() << "Finalizing packet:\n"; 167 unsigned Idx = 0; 168 for (MachineInstr *MI : CurrentPacketMIs) { 169 unsigned R = ResourceTracker->getUsedResources(Idx++); 170 dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI; 171 } 172 } 173 }); 174 if (CurrentPacketMIs.size() > 1) { 175 MachineInstr &MIFirst = *CurrentPacketMIs.front(); 176 finalizeBundle(*MBB, MIFirst.getIterator(), MI.getInstrIterator()); 177 } 178 CurrentPacketMIs.clear(); 179 ResourceTracker->clearResources(); 180 LLVM_DEBUG(dbgs() << "End packet\n"); 181 } 182 183 // Bundle machine instructions into packets. 184 void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB, 185 MachineBasicBlock::iterator BeginItr, 186 MachineBasicBlock::iterator EndItr) { 187 assert(VLIWScheduler && "VLIW Scheduler is not initialized!"); 188 VLIWScheduler->startBlock(MBB); 189 VLIWScheduler->enterRegion(MBB, BeginItr, EndItr, 190 std::distance(BeginItr, EndItr)); 191 VLIWScheduler->schedule(); 192 193 LLVM_DEBUG({ 194 dbgs() << "Scheduling DAG of the packetize region\n"; 195 VLIWScheduler->dump(); 196 }); 197 198 // Generate MI -> SU map. 199 MIToSUnit.clear(); 200 for (SUnit &SU : VLIWScheduler->SUnits) 201 MIToSUnit[SU.getInstr()] = &SU; 202 203 bool LimitPresent = InstrLimit.getPosition(); 204 205 // The main packetizer loop. 206 for (; BeginItr != EndItr; ++BeginItr) { 207 if (LimitPresent) { 208 if (InstrCount >= InstrLimit) { 209 EndItr = BeginItr; 210 break; 211 } 212 InstrCount++; 213 } 214 MachineInstr &MI = *BeginItr; 215 initPacketizerState(); 216 217 // End the current packet if needed. 218 if (isSoloInstruction(MI)) { 219 endPacket(MBB, MI); 220 continue; 221 } 222 223 // Ignore pseudo instructions. 224 if (ignorePseudoInstruction(MI, MBB)) 225 continue; 226 227 SUnit *SUI = MIToSUnit[&MI]; 228 assert(SUI && "Missing SUnit Info!"); 229 230 // Ask DFA if machine resource is available for MI. 231 LLVM_DEBUG(dbgs() << "Checking resources for adding MI to packet " << MI); 232 233 bool ResourceAvail = ResourceTracker->canReserveResources(MI); 234 LLVM_DEBUG({ 235 if (ResourceAvail) 236 dbgs() << " Resources are available for adding MI to packet\n"; 237 else 238 dbgs() << " Resources NOT available\n"; 239 }); 240 if (ResourceAvail && shouldAddToPacket(MI)) { 241 // Dependency check for MI with instructions in CurrentPacketMIs. 242 for (auto MJ : CurrentPacketMIs) { 243 SUnit *SUJ = MIToSUnit[MJ]; 244 assert(SUJ && "Missing SUnit Info!"); 245 246 LLVM_DEBUG(dbgs() << " Checking against MJ " << *MJ); 247 // Is it legal to packetize SUI and SUJ together. 248 if (!isLegalToPacketizeTogether(SUI, SUJ)) { 249 LLVM_DEBUG(dbgs() << " Not legal to add MI, try to prune\n"); 250 // Allow packetization if dependency can be pruned. 251 if (!isLegalToPruneDependencies(SUI, SUJ)) { 252 // End the packet if dependency cannot be pruned. 253 LLVM_DEBUG(dbgs() 254 << " Could not prune dependencies for adding MI\n"); 255 endPacket(MBB, MI); 256 break; 257 } 258 LLVM_DEBUG(dbgs() << " Pruned dependence for adding MI\n"); 259 } 260 } 261 } else { 262 LLVM_DEBUG(if (ResourceAvail) dbgs() 263 << "Resources are available, but instruction should not be " 264 "added to packet\n " 265 << MI); 266 // End the packet if resource is not available, or if the instruction 267 // shoud not be added to the current packet. 268 endPacket(MBB, MI); 269 } 270 271 // Add MI to the current packet. 272 LLVM_DEBUG(dbgs() << "* Adding MI to packet " << MI << '\n'); 273 BeginItr = addToPacket(MI); 274 } // For all instructions in the packetization range. 275 276 // End any packet left behind. 277 endPacket(MBB, EndItr); 278 VLIWScheduler->exitRegion(); 279 VLIWScheduler->finishBlock(); 280 } 281 282 bool VLIWPacketizerList::alias(const MachineMemOperand &Op1, 283 const MachineMemOperand &Op2, 284 bool UseTBAA) const { 285 if (!Op1.getValue() || !Op2.getValue()) 286 return true; 287 288 int64_t MinOffset = std::min(Op1.getOffset(), Op2.getOffset()); 289 int64_t Overlapa = Op1.getSize() + Op1.getOffset() - MinOffset; 290 int64_t Overlapb = Op2.getSize() + Op2.getOffset() - MinOffset; 291 292 AliasResult AAResult = 293 AA->alias(MemoryLocation(Op1.getValue(), Overlapa, 294 UseTBAA ? Op1.getAAInfo() : AAMDNodes()), 295 MemoryLocation(Op2.getValue(), Overlapb, 296 UseTBAA ? Op2.getAAInfo() : AAMDNodes())); 297 298 return AAResult != NoAlias; 299 } 300 301 bool VLIWPacketizerList::alias(const MachineInstr &MI1, 302 const MachineInstr &MI2, 303 bool UseTBAA) const { 304 if (MI1.memoperands_empty() || MI2.memoperands_empty()) 305 return true; 306 307 for (const MachineMemOperand *Op1 : MI1.memoperands()) 308 for (const MachineMemOperand *Op2 : MI2.memoperands()) 309 if (alias(*Op1, *Op2, UseTBAA)) 310 return true; 311 return false; 312 } 313 314 // Add a DAG mutation object to the ordered list. 315 void VLIWPacketizerList::addMutation( 316 std::unique_ptr<ScheduleDAGMutation> Mutation) { 317 VLIWScheduler->addMutation(std::move(Mutation)); 318 } 319