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