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 #include "llvm/CodeGen/DFAPacketizer.h" 27 #include "llvm/CodeGen/MachineInstr.h" 28 #include "llvm/CodeGen/MachineInstrBundle.h" 29 #include "llvm/CodeGen/ScheduleDAGInstrs.h" 30 #include "llvm/MC/MCInstrItineraries.h" 31 #include "llvm/Target/TargetInstrInfo.h" 32 using namespace llvm; 33 34 DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2], 35 const unsigned *SET): 36 InstrItins(I), CurrentState(0), DFAStateInputTable(SIT), 37 DFAStateEntryTable(SET) {} 38 39 40 // 41 // ReadTable - Read the DFA transition table and update CachedTable. 42 // 43 // Format of the transition tables: 44 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 45 // transitions 46 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable 47 // for the ith state 48 // 49 void DFAPacketizer::ReadTable(unsigned int state) { 50 unsigned ThisState = DFAStateEntryTable[state]; 51 unsigned NextStateInTable = DFAStateEntryTable[state+1]; 52 // Early exit in case CachedTable has already contains this 53 // state's transitions. 54 if (CachedTable.count(UnsignPair(state, 55 DFAStateInputTable[ThisState][0]))) 56 return; 57 58 for (unsigned i = ThisState; i < NextStateInTable; i++) 59 CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] = 60 DFAStateInputTable[i][1]; 61 } 62 63 64 // canReserveResources - Check if the resources occupied by a MCInstrDesc 65 // are available in the current state. 66 bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc *MID) { 67 unsigned InsnClass = MID->getSchedClass(); 68 const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass); 69 unsigned FuncUnits = IS->getUnits(); 70 UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); 71 ReadTable(CurrentState); 72 return (CachedTable.count(StateTrans) != 0); 73 } 74 75 76 // reserveResources - Reserve the resources occupied by a MCInstrDesc and 77 // change the current state to reflect that change. 78 void DFAPacketizer::reserveResources(const llvm::MCInstrDesc *MID) { 79 unsigned InsnClass = MID->getSchedClass(); 80 const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass); 81 unsigned FuncUnits = IS->getUnits(); 82 UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); 83 ReadTable(CurrentState); 84 assert(CachedTable.count(StateTrans) != 0); 85 CurrentState = CachedTable[StateTrans]; 86 } 87 88 89 // canReserveResources - Check if the resources occupied by a machine 90 // instruction are available in the current state. 91 bool DFAPacketizer::canReserveResources(llvm::MachineInstr *MI) { 92 const llvm::MCInstrDesc &MID = MI->getDesc(); 93 return canReserveResources(&MID); 94 } 95 96 // reserveResources - Reserve the resources occupied by a machine 97 // instruction and change the current state to reflect that change. 98 void DFAPacketizer::reserveResources(llvm::MachineInstr *MI) { 99 const llvm::MCInstrDesc &MID = MI->getDesc(); 100 reserveResources(&MID); 101 } 102 103 namespace llvm { 104 // DefaultVLIWScheduler - This class extends ScheduleDAGInstrs and overrides 105 // Schedule method to build the dependence graph. 106 class DefaultVLIWScheduler : public ScheduleDAGInstrs { 107 public: 108 DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, 109 MachineDominatorTree &MDT, bool IsPostRA); 110 // Schedule - Actual scheduling work. 111 void schedule() override; 112 }; 113 } 114 115 DefaultVLIWScheduler::DefaultVLIWScheduler( 116 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 117 bool IsPostRA) : 118 ScheduleDAGInstrs(MF, MLI, MDT, IsPostRA) { 119 CanHandleTerminators = true; 120 } 121 122 void DefaultVLIWScheduler::schedule() { 123 // Build the scheduling graph. 124 buildSchedGraph(nullptr); 125 } 126 127 // VLIWPacketizerList Ctor 128 VLIWPacketizerList::VLIWPacketizerList( 129 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 130 bool IsPostRA) : TM(MF.getTarget()), MF(MF) { 131 TII = TM.getInstrInfo(); 132 ResourceTracker = TII->CreateTargetScheduleState(&TM, nullptr); 133 VLIWScheduler = new DefaultVLIWScheduler(MF, MLI, MDT, IsPostRA); 134 } 135 136 // VLIWPacketizerList Dtor 137 VLIWPacketizerList::~VLIWPacketizerList() { 138 if (VLIWScheduler) 139 delete VLIWScheduler; 140 141 if (ResourceTracker) 142 delete ResourceTracker; 143 } 144 145 // endPacket - End the current packet, bundle packet instructions and reset 146 // DFA state. 147 void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB, 148 MachineInstr *MI) { 149 if (CurrentPacketMIs.size() > 1) { 150 MachineInstr *MIFirst = CurrentPacketMIs.front(); 151 finalizeBundle(*MBB, MIFirst, MI); 152 } 153 CurrentPacketMIs.clear(); 154 ResourceTracker->clearResources(); 155 } 156 157 // PacketizeMIs - Bundle machine instructions into packets. 158 void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB, 159 MachineBasicBlock::iterator BeginItr, 160 MachineBasicBlock::iterator EndItr) { 161 assert(VLIWScheduler && "VLIW Scheduler is not initialized!"); 162 VLIWScheduler->startBlock(MBB); 163 VLIWScheduler->enterRegion(MBB, BeginItr, EndItr, 164 std::distance(BeginItr, EndItr)); 165 VLIWScheduler->schedule(); 166 167 // Generate MI -> SU map. 168 MIToSUnit.clear(); 169 for (unsigned i = 0, e = VLIWScheduler->SUnits.size(); i != e; ++i) { 170 SUnit *SU = &VLIWScheduler->SUnits[i]; 171 MIToSUnit[SU->getInstr()] = SU; 172 } 173 174 // The main packetizer loop. 175 for (; BeginItr != EndItr; ++BeginItr) { 176 MachineInstr *MI = BeginItr; 177 178 this->initPacketizerState(); 179 180 // End the current packet if needed. 181 if (this->isSoloInstruction(MI)) { 182 endPacket(MBB, MI); 183 continue; 184 } 185 186 // Ignore pseudo instructions. 187 if (this->ignorePseudoInstruction(MI, MBB)) 188 continue; 189 190 SUnit *SUI = MIToSUnit[MI]; 191 assert(SUI && "Missing SUnit Info!"); 192 193 // Ask DFA if machine resource is available for MI. 194 bool ResourceAvail = ResourceTracker->canReserveResources(MI); 195 if (ResourceAvail) { 196 // Dependency check for MI with instructions in CurrentPacketMIs. 197 for (std::vector<MachineInstr*>::iterator VI = CurrentPacketMIs.begin(), 198 VE = CurrentPacketMIs.end(); VI != VE; ++VI) { 199 MachineInstr *MJ = *VI; 200 SUnit *SUJ = MIToSUnit[MJ]; 201 assert(SUJ && "Missing SUnit Info!"); 202 203 // Is it legal to packetize SUI and SUJ together. 204 if (!this->isLegalToPacketizeTogether(SUI, SUJ)) { 205 // Allow packetization if dependency can be pruned. 206 if (!this->isLegalToPruneDependencies(SUI, SUJ)) { 207 // End the packet if dependency cannot be pruned. 208 endPacket(MBB, MI); 209 break; 210 } // !isLegalToPruneDependencies. 211 } // !isLegalToPacketizeTogether. 212 } // For all instructions in CurrentPacketMIs. 213 } else { 214 // End the packet if resource is not available. 215 endPacket(MBB, MI); 216 } 217 218 // Add MI to the current packet. 219 BeginItr = this->addToPacket(MI); 220 } // For all instructions in BB. 221 222 // End any packet left behind. 223 endPacket(MBB, EndItr); 224 VLIWScheduler->exitRegion(); 225 VLIWScheduler->finishBlock(); 226 } 227