1234285Sdim//=- llvm/CodeGen/DFAPacketizer.h - 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#ifndef LLVM_CODEGEN_DFAPACKETIZER_H 27234285Sdim#define LLVM_CODEGEN_DFAPACKETIZER_H 28234285Sdim 29249423Sdim#include "llvm/ADT/DenseMap.h" 30234285Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 31239462Sdim#include <map> 32234285Sdim 33234285Sdimnamespace llvm { 34234285Sdim 35234285Sdimclass MCInstrDesc; 36234285Sdimclass MachineInstr; 37234285Sdimclass MachineLoopInfo; 38234285Sdimclass MachineDominatorTree; 39234285Sdimclass InstrItineraryData; 40239462Sdimclass DefaultVLIWScheduler; 41234285Sdimclass SUnit; 42234285Sdim 43234285Sdimclass DFAPacketizer { 44234285Sdimprivate: 45234285Sdim typedef std::pair<unsigned, unsigned> UnsignPair; 46234285Sdim const InstrItineraryData *InstrItins; 47234285Sdim int CurrentState; 48234285Sdim const int (*DFAStateInputTable)[2]; 49234285Sdim const unsigned *DFAStateEntryTable; 50234285Sdim 51234285Sdim // CachedTable is a map from <FromState, Input> to ToState. 52234285Sdim DenseMap<UnsignPair, unsigned> CachedTable; 53234285Sdim 54234285Sdim // ReadTable - Read the DFA transition table and update CachedTable. 55234285Sdim void ReadTable(unsigned int state); 56234285Sdim 57234285Sdimpublic: 58234285Sdim DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2], 59234285Sdim const unsigned *SET); 60234285Sdim 61234285Sdim // Reset the current state to make all resources available. 62234285Sdim void clearResources() { 63234285Sdim CurrentState = 0; 64234285Sdim } 65234285Sdim 66234285Sdim // canReserveResources - Check if the resources occupied by a MCInstrDesc 67234285Sdim // are available in the current state. 68234285Sdim bool canReserveResources(const llvm::MCInstrDesc *MID); 69234285Sdim 70234285Sdim // reserveResources - Reserve the resources occupied by a MCInstrDesc and 71234285Sdim // change the current state to reflect that change. 72234285Sdim void reserveResources(const llvm::MCInstrDesc *MID); 73234285Sdim 74234285Sdim // canReserveResources - Check if the resources occupied by a machine 75234285Sdim // instruction are available in the current state. 76234285Sdim bool canReserveResources(llvm::MachineInstr *MI); 77234285Sdim 78234285Sdim // reserveResources - Reserve the resources occupied by a machine 79234285Sdim // instruction and change the current state to reflect that change. 80234285Sdim void reserveResources(llvm::MachineInstr *MI); 81239462Sdim 82239462Sdim const InstrItineraryData *getInstrItins() const { return InstrItins; } 83234285Sdim}; 84234285Sdim 85234285Sdim// VLIWPacketizerList - Implements a simple VLIW packetizer using DFA. The 86234285Sdim// packetizer works on machine basic blocks. For each instruction I in BB, the 87234285Sdim// packetizer consults the DFA to see if machine resources are available to 88234285Sdim// execute I. If so, the packetizer checks if I depends on any instruction J in 89234285Sdim// the current packet. If no dependency is found, I is added to current packet 90234285Sdim// and machine resource is marked as taken. If any dependency is found, a target 91234285Sdim// API call is made to prune the dependence. 92234285Sdimclass VLIWPacketizerList { 93239462Sdimprotected: 94234285Sdim const TargetMachine &TM; 95234285Sdim const MachineFunction &MF; 96234285Sdim const TargetInstrInfo *TII; 97234285Sdim 98239462Sdim // The VLIW Scheduler. 99239462Sdim DefaultVLIWScheduler *VLIWScheduler; 100234285Sdim 101234285Sdim // Vector of instructions assigned to the current packet. 102234285Sdim std::vector<MachineInstr*> CurrentPacketMIs; 103234285Sdim // DFA resource tracker. 104234285Sdim DFAPacketizer *ResourceTracker; 105234285Sdim 106239462Sdim // Generate MI -> SU map. 107239462Sdim std::map<MachineInstr*, SUnit*> MIToSUnit; 108239462Sdim 109234285Sdimpublic: 110234285Sdim VLIWPacketizerList( 111234285Sdim MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 112234285Sdim bool IsPostRA); 113234285Sdim 114234285Sdim virtual ~VLIWPacketizerList(); 115234285Sdim 116234285Sdim // PacketizeMIs - Implement this API in the backend to bundle instructions. 117234285Sdim void PacketizeMIs(MachineBasicBlock *MBB, 118234285Sdim MachineBasicBlock::iterator BeginItr, 119234285Sdim MachineBasicBlock::iterator EndItr); 120234285Sdim 121234285Sdim // getResourceTracker - return ResourceTracker 122234285Sdim DFAPacketizer *getResourceTracker() {return ResourceTracker;} 123234285Sdim 124234285Sdim // addToPacket - Add MI to the current packet. 125239462Sdim virtual MachineBasicBlock::iterator addToPacket(MachineInstr *MI) { 126239462Sdim MachineBasicBlock::iterator MII = MI; 127239462Sdim CurrentPacketMIs.push_back(MI); 128239462Sdim ResourceTracker->reserveResources(MI); 129239462Sdim return MII; 130239462Sdim } 131234285Sdim 132234285Sdim // endPacket - End the current packet. 133239462Sdim void endPacket(MachineBasicBlock *MBB, MachineInstr *MI); 134234285Sdim 135239462Sdim // initPacketizerState - perform initialization before packetizing 136239462Sdim // an instruction. This function is supposed to be overrided by 137239462Sdim // the target dependent packetizer. 138249423Sdim virtual void initPacketizerState() { return; } 139239462Sdim 140234285Sdim // ignorePseudoInstruction - Ignore bundling of pseudo instructions. 141239462Sdim virtual bool ignorePseudoInstruction(MachineInstr *I, 142239462Sdim MachineBasicBlock *MBB) { 143239462Sdim return false; 144239462Sdim } 145234285Sdim 146239462Sdim // isSoloInstruction - return true if instruction MI can not be packetized 147239462Sdim // with any other instruction, which means that MI itself is a packet. 148239462Sdim virtual bool isSoloInstruction(MachineInstr *MI) { 149239462Sdim return true; 150239462Sdim } 151234285Sdim 152234285Sdim // isLegalToPacketizeTogether - Is it legal to packetize SUI and SUJ 153234285Sdim // together. 154234285Sdim virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) { 155234285Sdim return false; 156234285Sdim } 157234285Sdim 158234285Sdim // isLegalToPruneDependencies - Is it legal to prune dependece between SUI 159234285Sdim // and SUJ. 160234285Sdim virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) { 161234285Sdim return false; 162234285Sdim } 163239462Sdim 164234285Sdim}; 165234285Sdim} 166234285Sdim 167234285Sdim#endif 168