1//=- llvm/CodeGen/DFAPacketizer.h - 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#ifndef LLVM_CODEGEN_DFAPACKETIZER_H 27#define LLVM_CODEGEN_DFAPACKETIZER_H 28 29#include "llvm/ADT/DenseMap.h" 30#include "llvm/CodeGen/MachineBasicBlock.h" 31#include <map> 32 33namespace llvm { 34 35class MCInstrDesc; 36class MachineInstr; 37class MachineLoopInfo; 38class MachineDominatorTree; 39class InstrItineraryData; 40class DefaultVLIWScheduler; 41class SUnit; 42 43class DFAPacketizer { 44private: 45 typedef std::pair<unsigned, unsigned> UnsignPair; 46 const InstrItineraryData *InstrItins; 47 int CurrentState; 48 const int (*DFAStateInputTable)[2]; 49 const unsigned *DFAStateEntryTable; 50 51 // CachedTable is a map from <FromState, Input> to ToState. 52 DenseMap<UnsignPair, unsigned> CachedTable; 53 54 // ReadTable - Read the DFA transition table and update CachedTable. 55 void ReadTable(unsigned int state); 56 57public: 58 DFAPacketizer(const InstrItineraryData *I, const int (*SIT)[2], 59 const unsigned *SET); 60 61 // Reset the current state to make all resources available. 62 void clearResources() { 63 CurrentState = 0; 64 } 65 66 // canReserveResources - Check if the resources occupied by a MCInstrDesc 67 // are available in the current state. 68 bool canReserveResources(const llvm::MCInstrDesc *MID); 69 70 // reserveResources - Reserve the resources occupied by a MCInstrDesc and 71 // change the current state to reflect that change. 72 void reserveResources(const llvm::MCInstrDesc *MID); 73 74 // canReserveResources - Check if the resources occupied by a machine 75 // instruction are available in the current state. 76 bool canReserveResources(llvm::MachineInstr *MI); 77 78 // reserveResources - Reserve the resources occupied by a machine 79 // instruction and change the current state to reflect that change. 80 void reserveResources(llvm::MachineInstr *MI); 81 82 const InstrItineraryData *getInstrItins() const { return InstrItins; } 83}; 84 85// VLIWPacketizerList - Implements a simple VLIW packetizer using DFA. The 86// packetizer works on machine basic blocks. For each instruction I in BB, the 87// packetizer consults the DFA to see if machine resources are available to 88// execute I. If so, the packetizer checks if I depends on any instruction J in 89// the current packet. If no dependency is found, I is added to current packet 90// and machine resource is marked as taken. If any dependency is found, a target 91// API call is made to prune the dependence. 92class VLIWPacketizerList { 93protected: 94 const TargetMachine &TM; 95 const MachineFunction &MF; 96 const TargetInstrInfo *TII; 97 98 // The VLIW Scheduler. 99 DefaultVLIWScheduler *VLIWScheduler; 100 101 // Vector of instructions assigned to the current packet. 102 std::vector<MachineInstr*> CurrentPacketMIs; 103 // DFA resource tracker. 104 DFAPacketizer *ResourceTracker; 105 106 // Generate MI -> SU map. 107 std::map<MachineInstr*, SUnit*> MIToSUnit; 108 109public: 110 VLIWPacketizerList( 111 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 112 bool IsPostRA); 113 114 virtual ~VLIWPacketizerList(); 115 116 // PacketizeMIs - Implement this API in the backend to bundle instructions. 117 void PacketizeMIs(MachineBasicBlock *MBB, 118 MachineBasicBlock::iterator BeginItr, 119 MachineBasicBlock::iterator EndItr); 120 121 // getResourceTracker - return ResourceTracker 122 DFAPacketizer *getResourceTracker() {return ResourceTracker;} 123 124 // addToPacket - Add MI to the current packet. 125 virtual MachineBasicBlock::iterator addToPacket(MachineInstr *MI) { 126 MachineBasicBlock::iterator MII = MI; 127 CurrentPacketMIs.push_back(MI); 128 ResourceTracker->reserveResources(MI); 129 return MII; 130 } 131 132 // endPacket - End the current packet. 133 void endPacket(MachineBasicBlock *MBB, MachineInstr *MI); 134 135 // initPacketizerState - perform initialization before packetizing 136 // an instruction. This function is supposed to be overrided by 137 // the target dependent packetizer. 138 virtual void initPacketizerState() { return; } 139 140 // ignorePseudoInstruction - Ignore bundling of pseudo instructions. 141 virtual bool ignorePseudoInstruction(MachineInstr *I, 142 MachineBasicBlock *MBB) { 143 return false; 144 } 145 146 // isSoloInstruction - return true if instruction MI can not be packetized 147 // with any other instruction, which means that MI itself is a packet. 148 virtual bool isSoloInstruction(MachineInstr *MI) { 149 return true; 150 } 151 152 // isLegalToPacketizeTogether - Is it legal to packetize SUI and SUJ 153 // together. 154 virtual bool isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) { 155 return false; 156 } 157 158 // isLegalToPruneDependencies - Is it legal to prune dependece between SUI 159 // and SUJ. 160 virtual bool isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) { 161 return false; 162 } 163 164}; 165} 166 167#endif 168