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; 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // stateNum is the only member used for equality/ordering, all other members 86dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // can be mutated even in const State objects. 87dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const int stateNum; 88dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines mutable bool isInitial; 89dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines mutable std::set<unsigned> stateInfo; 90dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typedef std::map<unsigned, const State *> TransitionMap; 91dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines mutable TransitionMap Transitions; 92dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 93dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta State(); 94dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 953adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta bool operator<(const State &s) const { 963adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta return stateNum < s.stateNum; 973adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta } 983adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta 99dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 100dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // canAddInsnClass - Returns true if an instruction of type InsnClass is a 101f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // valid transition from this state, i.e., can an instruction of type InsnClass 102f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // be added to the packet represented by this state. 103dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 104dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // PossibleStates is the set of valid resource states that ensue from valid 105f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // transitions. 106dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 107e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta bool canAddInsnClass(unsigned InsnClass) const; 108e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta // 109e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta // AddInsnClass - Return all combinations of resource reservation 110e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta // which are possible from this state (PossibleStates). 111e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta // 112dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void AddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates) const; 1133adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // 1143adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // addTransition - Add a transition from this state given the input InsnClass 1153adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // 116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines void addTransition(unsigned InsnClass, const State *To) const; 1173adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // 1183adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // hasTransition - Returns true if there is a transition from this state 1193adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // given the input InsnClass 1203adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta // 121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool hasTransition(unsigned InsnClass) const; 122dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta}; 123f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop} // End anonymous namespace. 124dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 125dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 126f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// class DFA: deterministic finite automaton for processor resource tracking. 127dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 128dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptanamespace { 129dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptaclass DFA { 130dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptapublic: 131dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta DFA(); 132dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 133f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Set of states. Need to keep this sorted to emit the transition table. 134dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines typedef std::set<State> StateSet; 1353adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta StateSet states; 136dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 137464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop State *currentState; 138dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 139dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 140f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Modify the DFA. 141dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 142dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const State &newState(); 143dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 144dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 145f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // writeTable: Print out a table representing the DFA. 146dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 147464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName); 148dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta}; 149f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop} // End anonymous namespace. 150dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 151dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 152dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 1533adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// Constructors and destructors for State and DFA 154dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 155dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman DasguptaState::State() : 156dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta stateNum(currentStateNum++), isInitial(false) {} 157dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 158dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesDFA::DFA(): currentState(nullptr) {} 159dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 1603adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// 1613adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// addTransition - Add a transition from this state given the input InsnClass 1623adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// 163dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid State::addTransition(unsigned InsnClass, const State *To) const { 1643adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta assert(!Transitions.count(InsnClass) && 1653adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta "Cannot have multiple transitions for the same input"); 1663adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta Transitions[InsnClass] = To; 167dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 168dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 1693adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// 1703adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// hasTransition - Returns true if there is a transition from this state 1713adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// given the input InsnClass 1723adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta// 173dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool State::hasTransition(unsigned InsnClass) const { 1743adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta return Transitions.count(InsnClass) > 0; 175e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta} 176dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 177dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 178e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// AddInsnClass - Return all combinations of resource reservation 179e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// which are possible from this state (PossibleStates). 180dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 181e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasguptavoid State::AddInsnClass(unsigned InsnClass, 182dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::set<unsigned> &PossibleStates) const { 183dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 184f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Iterate over all resource states in currentState. 185dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 186dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 187dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (std::set<unsigned>::iterator SI = stateInfo.begin(); 188dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta SI != stateInfo.end(); ++SI) { 189dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned thisState = *SI; 190dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 191dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 192f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Iterate over all possible resources used in InsnClass. 193f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}. 194dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 195dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 196dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta DenseSet<unsigned> VisitedResourceStates; 197dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned int j = 0; j < sizeof(InsnClass) * 8; ++j) { 198dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if ((0x1 << j) & InsnClass) { 199dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 200dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // For each possible resource used in InsnClass, generate the 201f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // resource state if that resource was used. 202dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 203dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned ResultingResourceState = thisState | (0x1 << j); 204dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 205dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Check if the resulting resource state can be accommodated in this 206f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // packet. 207f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // We compute ResultingResourceState OR thisState. 208dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // If the result of the OR is different than thisState, it implies 209dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // that there is at least one resource that can be used to schedule 210f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // InsnClass in the current packet. 211dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Insert ResultingResourceState into PossibleStates only if we haven't 212f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // processed ResultingResourceState before. 213dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 214dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if ((ResultingResourceState != thisState) && 215dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta (VisitedResourceStates.count(ResultingResourceState) == 0)) { 216dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta VisitedResourceStates.insert(ResultingResourceState); 217dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta PossibleStates.insert(ResultingResourceState); 218dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 219dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 220dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 221dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 222dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 223e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta} 224e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta 225e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta 226e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// 227e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// canAddInsnClass - Quickly verifies if an instruction of type InsnClass is a 228e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// valid transition from this state i.e., can an instruction of type InsnClass 229e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// be added to the packet represented by this state. 230e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta// 231e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasguptabool State::canAddInsnClass(unsigned InsnClass) const { 23287dc7a4c8d21bd638465881f3b6d091f22d9767cAlexey Samsonov for (std::set<unsigned>::const_iterator SI = stateInfo.begin(); 233e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta SI != stateInfo.end(); ++SI) { 234e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta if (~*SI & InsnClass) 235e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta return true; 236e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta } 237e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta return false; 238dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 239dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 240dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 241dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesconst State &DFA::newState() { 242dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto IterPair = states.insert(State()); 243dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(IterPair.second && "State already exists"); 244dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return *IterPair.first; 245dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 246dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 247dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 248dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasguptaint State::currentStateNum = 0; 249dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 2506f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund OlesenDFAPacketizerEmitter::DFAPacketizerEmitter(RecordKeeper &R): 251dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta TargetName(CodeGenTarget(R).getName()), 252dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta allInsnClasses(), Records(R) {} 253dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 254dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 255dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 256dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// writeTableAndAPI - Print out a table representing the DFA and the 257f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// associated API to create a DFA packetizer. 258dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 259dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// Format: 260dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid 261f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// transitions. 262dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for 263f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// the ith state. 264dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 265dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 266464f3a332f81364ee09794f9502f0b25671149c6Sebastian Popvoid DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { 267079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta static const std::string SentinelEntry = "{-1, -1}"; 2683adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta DFA::StateSet::iterator SI = states.begin(); 269dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // This table provides a map to the beginning of the transitions for State s 270f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // in DFAStateInputTable. 271dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::vector<int> StateEntry(states.size()); 272dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 273dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "namespace llvm {\n\n"; 274dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n"; 275dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 276dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Tracks the total valid transitions encountered so far. It is used 277f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // to construct the StateEntry table. 278dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta int ValidTransitions = 0; 279dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0; i < states.size(); ++i, ++SI) { 280dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert ((SI->stateNum == (int) i) && "Mismatch in state numbers"); 281dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta StateEntry[i] = ValidTransitions; 2823adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta for (State::TransitionMap::iterator 283dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines II = SI->Transitions.begin(), IE = SI->Transitions.end(); 2843adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta II != IE; ++II) { 2853adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta OS << "{" << II->first << ", " 2863adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta << II->second->stateNum 287dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta << "}, "; 288dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 289dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ValidTransitions += SI->Transitions.size(); 290dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 291f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // If there are no valid transitions from this stage, we need a sentinel 292f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // transition. 293ffbd0715fa0dd5dd2611cd5cea9f7e5516ba9f5fBrendon Cahoon if (ValidTransitions == StateEntry[i]) { 294079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta OS << SentinelEntry << ","; 295ffbd0715fa0dd5dd2611cd5cea9f7e5516ba9f5fBrendon Cahoon ++ValidTransitions; 296ffbd0715fa0dd5dd2611cd5cea9f7e5516ba9f5fBrendon Cahoon } 297dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 298dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "\n"; 299dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 300079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta 301079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta // Print out a sentinel entry at the end of the StateInputTable. This is 302079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta // needed to iterate over StateInputTable in DFAPacketizer::ReadTable() 303079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta OS << SentinelEntry << "\n"; 304079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta 305dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "};\n\n"; 306dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; 307dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 308dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Multiply i by 2 since each entry in DFAStateInputTable is a set of 309f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // two numbers. 310dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0; i < states.size(); ++i) 311dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << StateEntry[i] << ", "; 312dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 313079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta // Print out the index to the sentinel entry in StateInputTable 314079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta OS << ValidTransitions << ", "; 315079e0819bc4a0dde6ce427757130db85216167deAnshuman Dasgupta 316dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "\n};\n"; 317dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "} // namespace\n"; 318dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 319dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 320dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 321f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Emit DFA Packetizer tables if the target is a VLIW machine. 322dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 323dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; 324dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; 325dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "namespace llvm {\n"; 326464f3a332f81364ee09794f9502f0b25671149c6Sebastian Pop OS << "DFAPacketizer *" << SubTargetClassName << "::" 327dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" 328dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta << " return new DFAPacketizer(IID, " << TargetName 329dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; 330dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta OS << "} // End llvm namespace \n"; 331dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 332dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 333dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 334dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 335dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// collectAllInsnClasses - Populate allInsnClasses which is a set of units 336dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// used in each stage. 337dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 3386f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesenvoid DFAPacketizerEmitter::collectAllInsnClasses(const std::string &Name, 339dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Record *ItinData, 340dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned &NStages, 341dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta raw_ostream &OS) { 342f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Collect processor itineraries. 343dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::vector<Record*> ProcItinList = 344f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop Records.getAllDerivedDefinitions("ProcessorItineraries"); 345dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 346f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // If just no itinerary then don't bother. 347dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if (ProcItinList.size() < 2) 348dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta return; 349dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::map<std::string, unsigned> NameToBitsMap; 350dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 351dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Parse functional units for all the itineraries. 352dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { 353dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Record *Proc = ProcItinList[i]; 354dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); 355dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 356f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Convert macros to bits for each stage. 357dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0, N = FUs.size(); i < N; ++i) 358dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); 359dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 360dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 361dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta const std::vector<Record*> &StageList = 362dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta ItinData->getValueAsListOfDefs("Stages"); 363dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 364f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // The number of stages. 365dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta NStages = StageList.size(); 366dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 367f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // For each unit. 368dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned UnitBitValue = 0; 369dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 370f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Compute the bitwise or of each unit used in this stage. 371dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0; i < NStages; ++i) { 372dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta const Record *Stage = StageList[i]; 373dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 374f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Get unit list. 375dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta const std::vector<Record*> &UnitList = 376dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Stage->getValueAsListOfDefs("Units"); 377dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 378dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { 379f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Conduct bitwise or. 380dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::string UnitName = UnitList[j]->getName(); 381dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta assert(NameToBitsMap.count(UnitName)); 382dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta UnitBitValue |= NameToBitsMap[UnitName]; 383dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 384dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 385dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if (UnitBitValue != 0) 386dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta allInsnClasses.insert(UnitBitValue); 387dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 388dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 389dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 390dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 391dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 392f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop// Run the worklist algorithm to generate the DFA. 393dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta// 3946f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesenvoid DFAPacketizerEmitter::run(raw_ostream &OS) { 395dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 396f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Collect processor iteraries. 397dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::vector<Record*> ProcItinList = 398dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Records.getAllDerivedDefinitions("ProcessorItineraries"); 399dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 400dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 401f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Collect the instruction classes. 402dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 403dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { 404dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Record *Proc = ProcItinList[i]; 405dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 406f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Get processor itinerary name. 407dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta const std::string &Name = Proc->getName(); 408dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 409f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Skip default. 410dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if (Name == "NoItineraries") 411dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta continue; 412dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 413f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Sanity check for at least one instruction itinerary class. 414dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned NItinClasses = 415dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Records.getAllDerivedDefinitions("InstrItinClass").size(); 416dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta if (NItinClasses == 0) 417dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta return; 418dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 419f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Get itinerary data list. 420dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); 421dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 422f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Collect instruction classes for all itinerary data. 423dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { 424dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Record *ItinData = ItinDataList[j]; 425dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned NStages; 426dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta collectAllInsnClasses(Name, ItinData, NStages, OS); 427dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 428dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 429dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 430dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 431dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 432f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Run a worklist algorithm to generate the DFA. 433dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 434dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta DFA D; 435dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const State *Initial = &D.newState(); 436dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Initial->isInitial = true; 437dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Initial->stateInfo.insert(0x0); 438dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SmallVector<const State*, 32> WorkList; 439dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines std::map<std::set<unsigned>, const State*> Visited; 440dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 441dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta WorkList.push_back(Initial); 442dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 443dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 444f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Worklist algorithm to create a DFA for processor resource tracking. 445dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // C = {set of InsnClasses} 446dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Begin with initial node in worklist. Initial node does not have 447dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // any consumed resources, 448dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // ResourceState = 0x0 449dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Visited = {} 450dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // While worklist != empty 451dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // S = first element of worklist 452dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // For every instruction class C 453dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // if we can accommodate C in S: 454dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // S' = state with resource states = {S Union C} 455dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Add a new transition: S x C -> S' 456dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // If S' is not in Visited: 457dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Add S' to worklist 458dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // Add S' to Visited 459dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 460dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta while (!WorkList.empty()) { 461dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const State *current = WorkList.pop_back_val(); 462dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(), 463dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta CE = allInsnClasses.end(); CI != CE; ++CI) { 464dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta unsigned InsnClass = *CI; 465dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 466dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta std::set<unsigned> NewStateResources; 467dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 468dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // If we haven't already created a transition for this input 469f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // and the state can accommodate this InsnClass, create a transition. 470dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 4713adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta if (!current->hasTransition(InsnClass) && 472e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta current->canAddInsnClass(InsnClass)) { 473dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const State *NewState; 474e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta current->AddInsnClass(InsnClass, NewStateResources); 475e2529dc91e06e84ae3e7730c37a42ff9486b25bfAnshuman Dasgupta assert(NewStateResources.size() && "New states must be generated"); 476dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 477dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 478f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // If we have seen this state before, then do not create a new state. 479dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 480dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta // 481dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto VI = Visited.find(NewStateResources); 482dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (VI != Visited.end()) 483dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta NewState = VI->second; 484dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta else { 485dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NewState = &D.newState(); 486dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta NewState->stateInfo = NewStateResources; 487dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta Visited[NewStateResources] = NewState; 488dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta WorkList.push_back(NewState); 489dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 4903adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta 4913adf3b0ac0927ee95d59e3c98599254072fb26f5Anshuman Dasgupta current->addTransition(InsnClass, NewState); 492dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 493dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 494dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta } 495dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta 496f6f77e90a18142e196cbc2a6ee87cdf7461b17dfSebastian Pop // Print out the table. 497dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta D.writeTableAndAPI(OS, TargetName); 498dc81e5da271ed394e2029c83458773c4ae2fc5f4Anshuman Dasgupta} 4996f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen 5006f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesennamespace llvm { 5016f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen 5026f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesenvoid EmitDFAPacketizer(RecordKeeper &RK, raw_ostream &OS) { 5036f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen emitSourceFileHeader("Target DFA Packetizer Tables", OS); 5046f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen DFAPacketizerEmitter(RK).run(OS); 5056f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen} 5066f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen 5076f36fa981a59461466e12e5056ba209d289b81b1Jakob Stoklund Olesen} // End llvm namespace 508