1234285Sdim//=- llvm/CodeGen/DFAPacketizer.cpp - DFA Packetizer for VLIW -*- C++ -*-=====// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// This class implements a deterministic finite automaton (DFA) based 10234285Sdim// packetizing mechanism for VLIW architectures. It provides APIs to 11234285Sdim// determine whether there exists a legal mapping of instructions to 12234285Sdim// functional unit assignments in a packet. The DFA is auto-generated from 13234285Sdim// the target's Schedule.td file. 14234285Sdim// 15234285Sdim// A DFA consists of 3 major elements: states, inputs, and transitions. For 16234285Sdim// the packetizing mechanism, the input is the set of instruction classes for 17234285Sdim// a target. The state models all possible combinations of functional unit 18234285Sdim// consumption for a given set of instructions in a packet. A transition 19234285Sdim// models the addition of an instruction to a packet. In the DFA constructed 20234285Sdim// by this class, if an instruction can be added to a packet, then a valid 21234285Sdim// transition exists from the corresponding state. Invalid transitions 22234285Sdim// indicate that the instruction cannot be added to the current packet. 23234285Sdim// 24234285Sdim//===----------------------------------------------------------------------===// 25234285Sdim 26234285Sdim#include "llvm/CodeGen/DFAPacketizer.h" 27234285Sdim#include "llvm/CodeGen/MachineInstr.h" 28234285Sdim#include "llvm/CodeGen/MachineInstrBundle.h" 29249423Sdim#include "llvm/CodeGen/ScheduleDAGInstrs.h" 30249423Sdim#include "llvm/MC/MCInstrItineraries.h" 31234285Sdim#include "llvm/Target/TargetInstrInfo.h" 32234285Sdimusing namespace llvm; 33234285Sdim 34234285SdimDFAPacketizer::DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2], 35234285Sdim const unsigned *SET): 36234285Sdim InstrItins(I), CurrentState(0), DFAStateInputTable(SIT), 37234285Sdim DFAStateEntryTable(SET) {} 38234285Sdim 39234285Sdim 40234285Sdim// 41234285Sdim// ReadTable - Read the DFA transition table and update CachedTable. 42234285Sdim// 43234285Sdim// Format of the transition tables: 44234285Sdim// DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 45234285Sdim// transitions 46234285Sdim// DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable 47234285Sdim// for the ith state 48234285Sdim// 49234285Sdimvoid DFAPacketizer::ReadTable(unsigned int state) { 50234285Sdim unsigned ThisState = DFAStateEntryTable[state]; 51234285Sdim unsigned NextStateInTable = DFAStateEntryTable[state+1]; 52234285Sdim // Early exit in case CachedTable has already contains this 53234285Sdim // state's transitions. 54234285Sdim if (CachedTable.count(UnsignPair(state, 55234285Sdim DFAStateInputTable[ThisState][0]))) 56234285Sdim return; 57234285Sdim 58234285Sdim for (unsigned i = ThisState; i < NextStateInTable; i++) 59234285Sdim CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] = 60234285Sdim DFAStateInputTable[i][1]; 61234285Sdim} 62234285Sdim 63234285Sdim 64234285Sdim// canReserveResources - Check if the resources occupied by a MCInstrDesc 65234285Sdim// are available in the current state. 66234285Sdimbool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc *MID) { 67234285Sdim unsigned InsnClass = MID->getSchedClass(); 68234285Sdim const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass); 69234285Sdim unsigned FuncUnits = IS->getUnits(); 70234285Sdim UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); 71234285Sdim ReadTable(CurrentState); 72234285Sdim return (CachedTable.count(StateTrans) != 0); 73234285Sdim} 74234285Sdim 75234285Sdim 76234285Sdim// reserveResources - Reserve the resources occupied by a MCInstrDesc and 77234285Sdim// change the current state to reflect that change. 78234285Sdimvoid DFAPacketizer::reserveResources(const llvm::MCInstrDesc *MID) { 79234285Sdim unsigned InsnClass = MID->getSchedClass(); 80234285Sdim const llvm::InstrStage *IS = InstrItins->beginStage(InsnClass); 81234285Sdim unsigned FuncUnits = IS->getUnits(); 82234285Sdim UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); 83234285Sdim ReadTable(CurrentState); 84234285Sdim assert(CachedTable.count(StateTrans) != 0); 85234285Sdim CurrentState = CachedTable[StateTrans]; 86234285Sdim} 87234285Sdim 88234285Sdim 89234285Sdim// canReserveResources - Check if the resources occupied by a machine 90234285Sdim// instruction are available in the current state. 91234285Sdimbool DFAPacketizer::canReserveResources(llvm::MachineInstr *MI) { 92234285Sdim const llvm::MCInstrDesc &MID = MI->getDesc(); 93234285Sdim return canReserveResources(&MID); 94234285Sdim} 95234285Sdim 96234285Sdim// reserveResources - Reserve the resources occupied by a machine 97234285Sdim// instruction and change the current state to reflect that change. 98234285Sdimvoid DFAPacketizer::reserveResources(llvm::MachineInstr *MI) { 99234285Sdim const llvm::MCInstrDesc &MID = MI->getDesc(); 100234285Sdim reserveResources(&MID); 101234285Sdim} 102234285Sdim 103239462Sdimnamespace llvm { 104234285Sdim// DefaultVLIWScheduler - This class extends ScheduleDAGInstrs and overrides 105234285Sdim// Schedule method to build the dependence graph. 106234285Sdimclass DefaultVLIWScheduler : public ScheduleDAGInstrs { 107234285Sdimpublic: 108234285Sdim DefaultVLIWScheduler(MachineFunction &MF, MachineLoopInfo &MLI, 109239462Sdim MachineDominatorTree &MDT, bool IsPostRA); 110234285Sdim // Schedule - Actual scheduling work. 111234285Sdim void schedule(); 112234285Sdim}; 113239462Sdim} 114234285Sdim 115234285SdimDefaultVLIWScheduler::DefaultVLIWScheduler( 116234285Sdim MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 117234285Sdim bool IsPostRA) : 118234285Sdim ScheduleDAGInstrs(MF, MLI, MDT, IsPostRA) { 119239462Sdim CanHandleTerminators = true; 120234285Sdim} 121234285Sdim 122234285Sdimvoid DefaultVLIWScheduler::schedule() { 123234285Sdim // Build the scheduling graph. 124234285Sdim buildSchedGraph(0); 125234285Sdim} 126234285Sdim 127234285Sdim// VLIWPacketizerList Ctor 128234285SdimVLIWPacketizerList::VLIWPacketizerList( 129234285Sdim MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 130234285Sdim bool IsPostRA) : TM(MF.getTarget()), MF(MF) { 131234285Sdim TII = TM.getInstrInfo(); 132234285Sdim ResourceTracker = TII->CreateTargetScheduleState(&TM, 0); 133239462Sdim VLIWScheduler = new DefaultVLIWScheduler(MF, MLI, MDT, IsPostRA); 134234285Sdim} 135234285Sdim 136234285Sdim// VLIWPacketizerList Dtor 137234285SdimVLIWPacketizerList::~VLIWPacketizerList() { 138239462Sdim if (VLIWScheduler) 139239462Sdim delete VLIWScheduler; 140234285Sdim 141239462Sdim if (ResourceTracker) 142239462Sdim delete ResourceTracker; 143234285Sdim} 144234285Sdim 145234285Sdim// endPacket - End the current packet, bundle packet instructions and reset 146234285Sdim// DFA state. 147234285Sdimvoid VLIWPacketizerList::endPacket(MachineBasicBlock *MBB, 148239462Sdim MachineInstr *MI) { 149234285Sdim if (CurrentPacketMIs.size() > 1) { 150234285Sdim MachineInstr *MIFirst = CurrentPacketMIs.front(); 151239462Sdim finalizeBundle(*MBB, MIFirst, MI); 152234285Sdim } 153234285Sdim CurrentPacketMIs.clear(); 154234285Sdim ResourceTracker->clearResources(); 155234285Sdim} 156234285Sdim 157234285Sdim// PacketizeMIs - Bundle machine instructions into packets. 158234285Sdimvoid VLIWPacketizerList::PacketizeMIs(MachineBasicBlock *MBB, 159234285Sdim MachineBasicBlock::iterator BeginItr, 160234285Sdim MachineBasicBlock::iterator EndItr) { 161239462Sdim assert(VLIWScheduler && "VLIW Scheduler is not initialized!"); 162239462Sdim VLIWScheduler->startBlock(MBB); 163263508Sdim VLIWScheduler->enterRegion(MBB, BeginItr, EndItr, 164263508Sdim std::distance(BeginItr, EndItr)); 165239462Sdim VLIWScheduler->schedule(); 166234285Sdim 167239462Sdim // Generate MI -> SU map. 168239462Sdim MIToSUnit.clear(); 169239462Sdim for (unsigned i = 0, e = VLIWScheduler->SUnits.size(); i != e; ++i) { 170239462Sdim SUnit *SU = &VLIWScheduler->SUnits[i]; 171239462Sdim MIToSUnit[SU->getInstr()] = SU; 172239462Sdim } 173234285Sdim 174234285Sdim // The main packetizer loop. 175234285Sdim for (; BeginItr != EndItr; ++BeginItr) { 176234285Sdim MachineInstr *MI = BeginItr; 177234285Sdim 178239462Sdim this->initPacketizerState(); 179234285Sdim 180234285Sdim // End the current packet if needed. 181239462Sdim if (this->isSoloInstruction(MI)) { 182234285Sdim endPacket(MBB, MI); 183234285Sdim continue; 184234285Sdim } 185234285Sdim 186239462Sdim // Ignore pseudo instructions. 187239462Sdim if (this->ignorePseudoInstruction(MI, MBB)) 188239462Sdim continue; 189239462Sdim 190239462Sdim SUnit *SUI = MIToSUnit[MI]; 191234285Sdim assert(SUI && "Missing SUnit Info!"); 192234285Sdim 193234285Sdim // Ask DFA if machine resource is available for MI. 194234285Sdim bool ResourceAvail = ResourceTracker->canReserveResources(MI); 195234285Sdim if (ResourceAvail) { 196234285Sdim // Dependency check for MI with instructions in CurrentPacketMIs. 197234285Sdim for (std::vector<MachineInstr*>::iterator VI = CurrentPacketMIs.begin(), 198234285Sdim VE = CurrentPacketMIs.end(); VI != VE; ++VI) { 199234285Sdim MachineInstr *MJ = *VI; 200239462Sdim SUnit *SUJ = MIToSUnit[MJ]; 201234285Sdim assert(SUJ && "Missing SUnit Info!"); 202234285Sdim 203234285Sdim // Is it legal to packetize SUI and SUJ together. 204239462Sdim if (!this->isLegalToPacketizeTogether(SUI, SUJ)) { 205234285Sdim // Allow packetization if dependency can be pruned. 206239462Sdim if (!this->isLegalToPruneDependencies(SUI, SUJ)) { 207234285Sdim // End the packet if dependency cannot be pruned. 208234285Sdim endPacket(MBB, MI); 209234285Sdim break; 210234285Sdim } // !isLegalToPruneDependencies. 211234285Sdim } // !isLegalToPacketizeTogether. 212234285Sdim } // For all instructions in CurrentPacketMIs. 213234285Sdim } else { 214234285Sdim // End the packet if resource is not available. 215234285Sdim endPacket(MBB, MI); 216234285Sdim } 217234285Sdim 218234285Sdim // Add MI to the current packet. 219239462Sdim BeginItr = this->addToPacket(MI); 220234285Sdim } // For all instructions in BB. 221234285Sdim 222234285Sdim // End any packet left behind. 223234285Sdim endPacket(MBB, EndItr); 224239462Sdim VLIWScheduler->exitRegion(); 225239462Sdim VLIWScheduler->finishBlock(); 226234285Sdim} 227