DFAPacketizer.cpp revision e3fd2a36d93ed65fabe9cd8e1c98edd8d4f7ec62
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/Target/TargetInstrInfo.h" 31#include "llvm/MC/MCInstrItineraries.h" 32using namespace llvm; 33 34DFAPacketizer::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// 49void 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. 66bool 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. 78void 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. 91bool 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. 98void DFAPacketizer::reserveResources(llvm::MachineInstr *MI) { 99 const llvm::MCInstrDesc &MID = MI->getDesc(); 100 reserveResources(&MID); 101} 102 103namespace { 104// DefaultVLIWScheduler - This class extends ScheduleDAGInstrs and overrides 105// Schedule method to build the dependence graph. 106class DefaultVLIWScheduler : public ScheduleDAGInstrs { 107public: 108 DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, 109 MachineDominatorTree &MDT, bool IsPostRA); 110 // Schedule - Actual scheduling work. 111 void schedule(); 112}; 113} // end anonymous namespace 114 115DefaultVLIWScheduler::DefaultVLIWScheduler( 116 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 117 bool IsPostRA) : 118 ScheduleDAGInstrs(MF, MLI, MDT, IsPostRA) { 119} 120 121void DefaultVLIWScheduler::schedule() { 122 // Build the scheduling graph. 123 buildSchedGraph(0); 124} 125 126// VLIWPacketizerList Ctor 127VLIWPacketizerList::VLIWPacketizerList( 128 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 129 bool IsPostRA) : TM(MF.getTarget()), MF(MF) { 130 TII = TM.getInstrInfo(); 131 ResourceTracker = TII->CreateTargetScheduleState(&TM, 0); 132 SchedulerImpl = new DefaultVLIWScheduler(MF, MLI, MDT, IsPostRA); 133} 134 135// VLIWPacketizerList Dtor 136VLIWPacketizerList::~VLIWPacketizerList() { 137 delete SchedulerImpl; 138 delete ResourceTracker; 139} 140 141// ignorePseudoInstruction - ignore pseudo instructions. 142bool VLIWPacketizerList::ignorePseudoInstruction(MachineInstr *MI, 143 MachineBasicBlock *MBB) { 144 if (MI->isDebugValue()) 145 return true; 146 147 if (TII->isSchedulingBoundary(MI, MBB, MF)) 148 return true; 149 150 return false; 151} 152 153// isSoloInstruction - return true if instruction I must end previous 154// packet. 155bool VLIWPacketizerList::isSoloInstruction(MachineInstr *I) { 156 if (I->isInlineAsm()) 157 return true; 158 159 return false; 160} 161 162// addToPacket - Add I to the current packet and reserve resource. 163void VLIWPacketizerList::addToPacket(MachineInstr *MI) { 164 CurrentPacketMIs.push_back(MI); 165 ResourceTracker->reserveResources(MI); 166} 167 168// endPacket - End the current packet, bundle packet instructions and reset 169// DFA state. 170void VLIWPacketizerList::endPacket(MachineBasicBlock *MBB, 171 MachineInstr *I) { 172 if (CurrentPacketMIs.size() > 1) { 173 MachineInstr *MIFirst = CurrentPacketMIs.front(); 174 finalizeBundle(*MBB, MIFirst, I); 175 } 176 CurrentPacketMIs.clear(); 177 ResourceTracker->clearResources(); 178} 179 180// PacketizeMIs - Bundle machine instructions into packets. 181void VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB, 182 MachineBasicBlock::iterator BeginItr, 183 MachineBasicBlock::iterator EndItr) { 184 assert(MBB->end() == EndItr && "Bad EndIndex"); 185 186 SchedulerImpl->enterRegion(MBB, BeginItr, EndItr, MBB->size()); 187 188 // Build the DAG without reordering instructions. 189 SchedulerImpl->schedule(); 190 191 // Remember scheduling units. 192 SUnits = SchedulerImpl->SUnits; 193 194 // The main packetizer loop. 195 for (; BeginItr != EndItr; ++BeginItr) { 196 MachineInstr *MI = BeginItr; 197 198 // Ignore pseudo instructions. 199 if (ignorePseudoInstruction(MI, MBB)) 200 continue; 201 202 // End the current packet if needed. 203 if (isSoloInstruction(MI)) { 204 endPacket(MBB, MI); 205 continue; 206 } 207 208 SUnit *SUI = SchedulerImpl->getSUnit(MI); 209 assert(SUI && "Missing SUnit Info!"); 210 211 // Ask DFA if machine resource is available for MI. 212 bool ResourceAvail = ResourceTracker->canReserveResources(MI); 213 if (ResourceAvail) { 214 // Dependency check for MI with instructions in CurrentPacketMIs. 215 for (std::vector<MachineInstr*>::iterator VI = CurrentPacketMIs.begin(), 216 VE = CurrentPacketMIs.end(); VI != VE; ++VI) { 217 MachineInstr *MJ = *VI; 218 SUnit *SUJ = SchedulerImpl->getSUnit(MJ); 219 assert(SUJ && "Missing SUnit Info!"); 220 221 // Is it legal to packetize SUI and SUJ together. 222 if (!isLegalToPacketizeTogether(SUI, SUJ)) { 223 // Allow packetization if dependency can be pruned. 224 if (!isLegalToPruneDependencies(SUI, SUJ)) { 225 // End the packet if dependency cannot be pruned. 226 endPacket(MBB, MI); 227 break; 228 } // !isLegalToPruneDependencies. 229 } // !isLegalToPacketizeTogether. 230 } // For all instructions in CurrentPacketMIs. 231 } else { 232 // End the packet if resource is not available. 233 endPacket(MBB, MI); 234 } 235 236 // Add MI to the current packet. 237 addToPacket(MI); 238 } // For all instructions in BB. 239 240 // End any packet left behind. 241 endPacket(MBB, EndItr); 242 243 SchedulerImpl->exitRegion(); 244} 245