1dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta//===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine-----===// 2dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 3dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// The LLVM Compiler Infrastructure 4dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 5dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// This file is distributed under the University of Illinois Open Source 6dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// License. See LICENSE.TXT for details. 7dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 8dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta//===----------------------------------------------------------------------===// 9dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 10dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// This class parses the Schedule.td file and produces an API that can be used 11dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// to reason about whether an instruction can be added to a packet on a VLIW 12dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// architecture. The class internally generates a deterministic finite 13dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// automaton (DFA) that models all possible mappings of machine instructions 14dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// to functional units as instructions are added to a packet. 15dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 16dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta//===----------------------------------------------------------------------===// 17dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 18dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta#include "CodeGenTarget.h" 196f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen#include "llvm/ADT/DenseSet.h" 203adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta#include "llvm/ADT/STLExtras.h" 216f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen#include "llvm/TableGen/Record.h" 226f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen#include "llvm/TableGen/TableGenBackend.h" 23dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta#include <list> 246f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen#include <map> 256f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen#include <string> 26dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptausing namespace llvm; 27dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 28dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 296f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen// class DFAPacketizerEmitter: class that generates and prints out the DFA 306f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen// for resource tracking. 316f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen// 326f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesennamespace { 336f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesenclass DFAPacketizerEmitter { 346f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesenprivate: 356f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen std::string TargetName; 366f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen // 376f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen // allInsnClasses is the set of all possible resources consumed by an 386f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen // InstrStage. 396f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen // 406f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen DenseSet<unsigned> allInsnClasses; 416f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen RecordKeeper &Records; 426f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen 436f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesenpublic: 446f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen DFAPacketizerEmitter(RecordKeeper &R); 456f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen 466f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen // 476f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen // collectAllInsnClasses: Populate allInsnClasses which is a set of units 486f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen // used in each stage. 496f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen // 506f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen void collectAllInsnClasses(const std::string &Name, 516f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen Record *ItinData, 526f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen unsigned &NStages, 536f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen raw_ostream &OS); 546f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen 556f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen void run(raw_ostream &OS); 566f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen}; 576f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen} // End anonymous namespace. 586f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen 596f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen// 60dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 61dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// State represents the usage of machine resources if the packet contains 62dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// a set of instruction classes. 63dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 64f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// Specifically, currentState is a set of bit-masks. 65dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// The nth bit in a bit-mask indicates whether the nth resource is being used 66dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// by this state. The set of bit-masks in a state represent the different 67dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// possible outcomes of transitioning to this state. 68f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// For example: consider a two resource architecture: resource L and resource M 69f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// with three instruction classes: L, M, and L_or_M. 70dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// From the initial state (currentState = 0x00), if we add instruction class 71dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// L_or_M we will transition to a state with currentState = [0x01, 0x10]. This 72dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// represents the possible resource states that can result from adding a L_or_M 73dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// instruction 74dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 75dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// Another way of thinking about this transition is we are mapping a NDFA with 76f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10]. 77dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 783adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// A State instance also contains a collection of transitions from that state: 793adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// a map from inputs to new states. 80dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 81dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptanamespace { 82dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptaclass State { 83dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta public: 84dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta static int currentStateNum; 85dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta int stateNum; 86dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta bool isInitial; 87dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::set<unsigned> stateInfo; 883adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta typedef std::map<unsigned, State *> TransitionMap; 893adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta TransitionMap Transitions; 90dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 91dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta State(); 92464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop State(const State &S); 93dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 943adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta bool operator<(const State &s) const { 953adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta return stateNum < s.stateNum; 963adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta } 973adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta 98dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 99dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // canAddInsnClass - Returns true if an instruction of type InsnClass is a 100f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // valid transition from this state, i.e., can an instruction of type InsnClass 101f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // be added to the packet represented by this state. 102dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 103dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // PossibleStates is the set of valid resource states that ensue from valid 104f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // transitions. 105dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 106e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta bool canAddInsnClass(unsigned InsnClass) const; 107e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta // 108e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta // AddInsnClass - Return all combinations of resource reservation 109e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta // which are possible from this state (PossibleStates). 110e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta // 111e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta void AddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates); 1123adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // 1133adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // addTransition - Add a transition from this state given the input InsnClass 1143adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // 1153adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta void addTransition(unsigned InsnClass, State *To); 1163adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // 1173adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // hasTransition - Returns true if there is a transition from this state 1183adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // given the input InsnClass 1193adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // 1203adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta bool hasTransition(unsigned InsnClass); 121dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta}; 122f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop} // End anonymous namespace. 123dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 124dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 125f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// class DFA: deterministic finite automaton for processor resource tracking. 126dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 127dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptanamespace { 128dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptaclass DFA { 129dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptapublic: 130dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta DFA(); 1313adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta ~DFA(); 132dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 133f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Set of states. Need to keep this sorted to emit the transition table. 1343adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta typedef std::set<State *, less_ptr<State> > StateSet; 1353adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta StateSet states; 136dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 137464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop State *currentState; 138dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 139dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 140f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Modify the DFA. 141dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 142dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta void initialize(); 143464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop void addState(State *); 144dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 145dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 146f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // writeTable: Print out a table representing the DFA. 147dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 148464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName); 149dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta}; 150f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop} // End anonymous namespace. 151dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 152dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 153dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 1543adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// Constructors and destructors for State and DFA 155dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 156dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman DasguptaState::State() : 157dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta stateNum(currentStateNum++), isInitial(false) {} 158dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 159dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 160464f3a332f81364ee09794f9502f0b25671149c6Sebastian PopState::State(const State &S) : 161dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta stateNum(currentStateNum++), isInitial(S.isInitial), 162dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta stateInfo(S.stateInfo) {} 163dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 1643adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman DasguptaDFA::DFA(): currentState(NULL) {} 165dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 1663adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman DasguptaDFA::~DFA() { 1673adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta DeleteContainerPointers(states); 1683adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta} 169dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 1703adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// 1713adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// addTransition - Add a transition from this state given the input InsnClass 1723adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// 1733adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasguptavoid State::addTransition(unsigned InsnClass, State *To) { 1743adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta assert(!Transitions.count(InsnClass) && 1753adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta "Cannot have multiple transitions for the same input"); 1763adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta Transitions[InsnClass] = To; 177dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 178dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 1793adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// 1803adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// hasTransition - Returns true if there is a transition from this state 1813adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// given the input InsnClass 1823adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// 1833adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasguptabool State::hasTransition(unsigned InsnClass) { 1843adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta return Transitions.count(InsnClass) > 0; 185e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta} 186dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 187dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 188e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// AddInsnClass - Return all combinations of resource reservation 189e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// which are possible from this state (PossibleStates). 190dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 191e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasguptavoid State::AddInsnClass(unsigned InsnClass, 192464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop std::set<unsigned> &PossibleStates) { 193dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 194f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Iterate over all resource states in currentState. 195dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 196dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 197dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (std::set<unsigned>::iterator SI = stateInfo.begin(); 198dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta SI != stateInfo.end(); ++SI) { 199dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned thisState = *SI; 200dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 201dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 202f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Iterate over all possible resources used in InsnClass. 203f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}. 204dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 205dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 206dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta DenseSet<unsigned> VisitedResourceStates; 207dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned int j = 0; j < sizeof(InsnClass) * 8; ++j) { 208dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if ((0x1 << j) & InsnClass) { 209dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 210dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // For each possible resource used in InsnClass, generate the 211f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // resource state if that resource was used. 212dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 213dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned ResultingResourceState = thisState | (0x1 << j); 214dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 215dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Check if the resulting resource state can be accommodated in this 216f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // packet. 217f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // We compute ResultingResourceState OR thisState. 218dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // If the result of the OR is different than thisState, it implies 219dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // that there is at least one resource that can be used to schedule 220f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // InsnClass in the current packet. 221dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Insert ResultingResourceState into PossibleStates only if we haven't 222f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // processed ResultingResourceState before. 223dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 224dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if ((ResultingResourceState != thisState) && 225dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta (VisitedResourceStates.count(ResultingResourceState) == 0)) { 226dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta VisitedResourceStates.insert(ResultingResourceState); 227dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta PossibleStates.insert(ResultingResourceState); 228dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 229dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 230dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 231dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 232dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 233e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta} 234e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta 235e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta 236e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// 237e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// canAddInsnClass - Quickly verifies if an instruction of type InsnClass is a 238e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// valid transition from this state i.e., can an instruction of type InsnClass 239e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// be added to the packet represented by this state. 240e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// 241e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasguptabool State::canAddInsnClass(unsigned InsnClass) const { 24287dc7a4c8d21bd638465881f3b6d091f22d9767cAlexey Samsonov for (std::set<unsigned>::const_iterator SI = stateInfo.begin(); 243e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta SI != stateInfo.end(); ++SI) { 244e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta if (~*SI & InsnClass) 245e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta return true; 246e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta } 247e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta return false; 248dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 249dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 250dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 251dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptavoid DFA::initialize() { 2523adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta assert(currentState && "Missing current state"); 253dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta currentState->isInitial = true; 254dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 255dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 256dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 257464f3a332f81364ee09794f9502f0b25671149c6Sebastian Popvoid DFA::addState(State *S) { 258dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta assert(!states.count(S) && "State already exists"); 259dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta states.insert(S); 260dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 261dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 262dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 263dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptaint State::currentStateNum = 0; 264dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 2656f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund OlesenDFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): 266dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta TargetName(CodeGenTarget(R).getName()), 267dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta allInsnClasses(), Records(R) {} 268dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 269dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 270dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 271dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// writeTableAndAPI - Print out a table representing the DFA and the 272f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// associated API to create a DFA packetizer. 273dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 274dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// Format: 275dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 276f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// transitions. 277dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for 278f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// the ith state. 279dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 280dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 281464f3a332f81364ee09794f9502f0b25671149c6Sebastian Popvoid DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { 282079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta static const std::string SentinelEntry = "{-1, -1}"; 2833adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta DFA::StateSet::iterator SI = states.begin(); 284dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // This table provides a map to the beginning of the transitions for State s 285f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // in DFAStateInputTable. 286dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::vector<int> StateEntry(states.size()); 287dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 288dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "namespace llvm {\n\n"; 289dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n"; 290dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 291dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Tracks the total valid transitions encountered so far. It is used 292f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // to construct the StateEntry table. 293dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta int ValidTransitions = 0; 294dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0; i < states.size(); ++i, ++SI) { 2953adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers"); 296dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta StateEntry[i] = ValidTransitions; 2973adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta for (State::TransitionMap::iterator 2983adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta II = (*SI)->Transitions.begin(), IE = (*SI)->Transitions.end(); 2993adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta II != IE; ++II) { 3003adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta OS << "{" << II->first << ", " 3013adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta << II->second->stateNum 302dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta << "}, "; 303dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 3043adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta ValidTransitions += (*SI)->Transitions.size(); 305dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 306f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // If there are no valid transitions from this stage, we need a sentinel 307f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // transition. 308ffbd0715fa0dd5dd2611cd5cea9f7e5516ba9f5fBrendon Cahoon if (ValidTransitions == StateEntry[i]) { 309079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta OS << SentinelEntry << ","; 310ffbd0715fa0dd5dd2611cd5cea9f7e5516ba9f5fBrendon Cahoon ++ValidTransitions; 311ffbd0715fa0dd5dd2611cd5cea9f7e5516ba9f5fBrendon Cahoon } 312dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 313dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "\n"; 314dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 315079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta 316079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta // Print out a sentinel entry at the end of the StateInputTable. This is 317079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta // needed to iterate over StateInputTable in DFAPacketizer::ReadTable() 318079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta OS << SentinelEntry << "\n"; 319079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta 320dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "};\n\n"; 321dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; 322dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 323dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Multiply i by 2 since each entry in DFAStateInputTable is a set of 324f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // two numbers. 325dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0; i < states.size(); ++i) 326dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << StateEntry[i] << ", "; 327dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 328079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta // Print out the index to the sentinel entry in StateInputTable 329079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta OS << ValidTransitions << ", "; 330079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta 331dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "\n};\n"; 332dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "} // namespace\n"; 333dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 334dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 335dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 336f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Emit DFA Packetizer tables if the target is a VLIW machine. 337dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 338dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 339dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; 340dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "namespace llvm {\n"; 341464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop OS << "DFAPacketizer *" << SubTargetClassName << "::" 342dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" 343dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta << " return new DFAPacketizer(IID, " << TargetName 344dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; 345dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "} // End llvm namespace \n"; 346dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 347dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 348dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 349dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 350dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// collectAllInsnClasses - Populate allInsnClasses which is a set of units 351dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// used in each stage. 352dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 3536f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesenvoid DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name, 354dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Record *ItinData, 355dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned &NStages, 356dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta raw_ostream &OS) { 357f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Collect processor itineraries. 358dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::vector<Record*> ProcItinList = 359f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop Records.getAllDerivedDefinitions("ProcessorItineraries"); 360dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 361f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // If just no itinerary then don't bother. 362dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if (ProcItinList.size() < 2) 363dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta return; 364dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::map<std::string, unsigned> NameToBitsMap; 365dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 366dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Parse functional units for all the itineraries. 367dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { 368dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Record *Proc = ProcItinList[i]; 369dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); 370dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 371f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Convert macros to bits for each stage. 372dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0, N = FUs.size(); i < N; ++i) 373dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); 374dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 375dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 376dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta const std::vector<Record*> &StageList = 377dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta ItinData->getValueAsListOfDefs("Stages"); 378dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 379f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // The number of stages. 380dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta NStages = StageList.size(); 381dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 382f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // For each unit. 383dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned UnitBitValue = 0; 384dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 385f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Compute the bitwise or of each unit used in this stage. 386dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0; i < NStages; ++i) { 387dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta const Record *Stage = StageList[i]; 388dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 389f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Get unit list. 390dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta const std::vector<Record*> &UnitList = 391dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Stage->getValueAsListOfDefs("Units"); 392dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 393dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { 394f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Conduct bitwise or. 395dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::string UnitName = UnitList[j]->getName(); 396dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta assert(NameToBitsMap.count(UnitName)); 397dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta UnitBitValue |= NameToBitsMap[UnitName]; 398dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 399dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 400dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if (UnitBitValue != 0) 401dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta allInsnClasses.insert(UnitBitValue); 402dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 403dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 404dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 405dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 406dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 407f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// Run the worklist algorithm to generate the DFA. 408dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 4096f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesenvoid DFAPacketizerEmitter::run(raw_ostream &OS) { 410dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 411f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Collect processor iteraries. 412dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::vector<Record*> ProcItinList = 413dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Records.getAllDerivedDefinitions("ProcessorItineraries"); 414dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 415dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 416f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Collect the instruction classes. 417dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 418dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { 419dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Record *Proc = ProcItinList[i]; 420dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 421f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Get processor itinerary name. 422dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta const std::string &Name = Proc->getName(); 423dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 424f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Skip default. 425dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if (Name == "NoItineraries") 426dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta continue; 427dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 428f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Sanity check for at least one instruction itinerary class. 429dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned NItinClasses = 430dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Records.getAllDerivedDefinitions("InstrItinClass").size(); 431dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if (NItinClasses == 0) 432dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta return; 433dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 434f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Get itinerary data list. 435dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); 436dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 437f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Collect instruction classes for all itinerary data. 438dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { 439dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Record *ItinData = ItinDataList[j]; 440dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned NStages; 441dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta collectAllInsnClasses(Name, ItinData, NStages, OS); 442dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 443dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 444dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 445dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 446dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 447f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Run a worklist algorithm to generate the DFA. 448dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 449dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta DFA D; 450464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop State *Initial = new State; 451dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Initial->isInitial = true; 452dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Initial->stateInfo.insert(0x0); 453dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta D.addState(Initial); 454dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta SmallVector<State*, 32> WorkList; 455dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::map<std::set<unsigned>, State*> Visited; 456dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 457dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta WorkList.push_back(Initial); 458dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 459dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 460f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Worklist algorithm to create a DFA for processor resource tracking. 461dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // C = {set of InsnClasses} 462dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Begin with initial node in worklist. Initial node does not have 463dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // any consumed resources, 464dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // ResourceState = 0x0 465dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Visited = {} 466dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // While worklist != empty 467dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // S = first element of worklist 468dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // For every instruction class C 469dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // if we can accommodate C in S: 470dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // S' = state with resource states = {S Union C} 471dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Add a new transition: S x C -> S' 472dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // If S' is not in Visited: 473dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Add S' to worklist 474dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Add S' to Visited 475dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 476dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta while (!WorkList.empty()) { 477464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop State *current = WorkList.pop_back_val(); 478dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(), 479dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta CE = allInsnClasses.end(); CI != CE; ++CI) { 480dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned InsnClass = *CI; 481dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 482dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::set<unsigned> NewStateResources; 483dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 484dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // If we haven't already created a transition for this input 485f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // and the state can accommodate this InsnClass, create a transition. 486dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 4873adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta if (!current->hasTransition(InsnClass) && 488e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta current->canAddInsnClass(InsnClass)) { 489464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop State *NewState = NULL; 490e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta current->AddInsnClass(InsnClass, NewStateResources); 491e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta assert(NewStateResources.size() && "New states must be generated"); 492dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 493dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 494f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // If we have seen this state before, then do not create a new state. 495dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 496dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 497dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::map<std::set<unsigned>, State*>::iterator VI; 498dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if ((VI = Visited.find(NewStateResources)) != Visited.end()) 499dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta NewState = VI->second; 500dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta else { 501dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta NewState = new State; 502dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta NewState->stateInfo = NewStateResources; 503dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta D.addState(NewState); 504dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Visited[NewStateResources] = NewState; 505dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta WorkList.push_back(NewState); 506dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 5073adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta 5083adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta current->addTransition(InsnClass, NewState); 509dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 510dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 511dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 512dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 513f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Print out the table. 514dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta D.writeTableAndAPI(OS, TargetName); 515dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 5166f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen 5176f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesennamespace llvm { 5186f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen 5196f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesenvoid EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { 5206f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen emitSourceFileHeader("Target DFA Packetizer Tables", OS); 5216f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen DFAPacketizerEmitter(RK).run(OS); 5226f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen} 5236f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen 5246f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen} // End llvm namespace 525