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/MC/MCInstrItineraries.h" 29 using namespace llvm; 30 31 DFAPacketizer::DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2], 32 const unsigned* SET): 33 InstrItins(I), CurrentState(0), DFAStateInputTable(SIT), 34 DFAStateEntryTable(SET) {} 35 36 37 // 38 // ReadTable - Read the DFA transition table and update CachedTable 39 // 40 // Format of the transition tables: 41 // DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 42 // transitions 43 // DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable 44 // for the ith state 45 // 46 void DFAPacketizer::ReadTable(unsigned int state) { 47 unsigned ThisState = DFAStateEntryTable[state]; 48 unsigned NextStateInTable = DFAStateEntryTable[state+1]; 49 // Early exit in case CachedTable has already contains this 50 // state's transitions 51 if (CachedTable.count(UnsignPair(state, 52 DFAStateInputTable[ThisState][0]))) 53 return; 54 55 for (unsigned i = ThisState; i < NextStateInTable; i++) 56 CachedTable[UnsignPair(state, DFAStateInputTable[i][0])] = 57 DFAStateInputTable[i][1]; 58 } 59 60 61 // canReserveResources - Check if the resources occupied by a MCInstrDesc 62 // are available in the current state 63 bool DFAPacketizer::canReserveResources(const llvm::MCInstrDesc* MID) { 64 unsigned InsnClass = MID->getSchedClass(); 65 const llvm::InstrStage* IS = InstrItins->beginStage(InsnClass); 66 unsigned FuncUnits = IS->getUnits(); 67 UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); 68 ReadTable(CurrentState); 69 return (CachedTable.count(StateTrans) != 0); 70 } 71 72 73 // reserveResources - Reserve the resources occupied by a MCInstrDesc and 74 // change the current state to reflect that change 75 void DFAPacketizer::reserveResources(const llvm::MCInstrDesc* MID) { 76 unsigned InsnClass = MID->getSchedClass(); 77 const llvm::InstrStage* IS = InstrItins->beginStage(InsnClass); 78 unsigned FuncUnits = IS->getUnits(); 79 UnsignPair StateTrans = UnsignPair(CurrentState, FuncUnits); 80 ReadTable(CurrentState); 81 assert(CachedTable.count(StateTrans) != 0); 82 CurrentState = CachedTable[StateTrans]; 83 } 84 85 86 // canReserveResources - Check if the resources occupied by a machine 87 // instruction are available in the current state 88 bool DFAPacketizer::canReserveResources(llvm::MachineInstr* MI) { 89 const llvm::MCInstrDesc& MID = MI->getDesc(); 90 return canReserveResources(&MID); 91 } 92 93 // reserveResources - Reserve the resources occupied by a machine 94 // instruction and change the current state to reflect that change 95 void DFAPacketizer::reserveResources(llvm::MachineInstr* MI) { 96 const llvm::MCInstrDesc& MID = MI->getDesc(); 97 reserveResources(&MID); 98 } 99