diff options
Diffstat (limited to 'utils/TableGen')
| -rw-r--r-- | utils/TableGen/AsmMatcherEmitter.cpp | 85 | ||||
| -rw-r--r-- | utils/TableGen/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | utils/TableGen/CodeGenRegisters.cpp | 146 | ||||
| -rw-r--r-- | utils/TableGen/CodeGenRegisters.h | 7 | ||||
| -rw-r--r-- | utils/TableGen/CodeGenTarget.cpp | 1 | ||||
| -rw-r--r-- | utils/TableGen/DFAPacketizerEmitter.cpp | 512 | ||||
| -rw-r--r-- | utils/TableGen/DFAPacketizerEmitter.h | 54 | ||||
| -rw-r--r-- | utils/TableGen/EDEmitter.cpp | 12 | ||||
| -rw-r--r-- | utils/TableGen/LLVMBuild.txt | 1 | ||||
| -rw-r--r-- | utils/TableGen/SubtargetEmitter.cpp | 4 | ||||
| -rw-r--r-- | utils/TableGen/TableGen.cpp | 7 |
11 files changed, 745 insertions, 85 deletions
diff --git a/utils/TableGen/AsmMatcherEmitter.cpp b/utils/TableGen/AsmMatcherEmitter.cpp index 01754c3..5ef0db9 100644 --- a/utils/TableGen/AsmMatcherEmitter.cpp +++ b/utils/TableGen/AsmMatcherEmitter.cpp @@ -252,11 +252,6 @@ public: switch (Kind) { case Invalid: assert(0 && "Invalid kind!"); - case Token: - // Tokens are comparable by value. - // - // FIXME: Compare by enum value. - return ValueName < RHS.ValueName; default: // This class precedes the RHS if it is a proper subset of the RHS. @@ -737,7 +732,9 @@ void MatchableInfo::TokenizeAsmString(const AsmMatcherInfo &Info) { // The first token of the instruction is the mnemonic, which must be a // simple string, not a $foo variable or a singleton register. - assert(!AsmOperands.empty() && "Instruction has no tokens?"); + if (AsmOperands.empty()) + throw TGError(TheDef->getLoc(), + "Instruction '" + TheDef->getName() + "' has no tokens"); Mnemonic = AsmOperands[0].Token; if (Mnemonic[0] == '$' || getSingletonRegisterForAsmOperand(0, Info)) throw TGError(TheDef->getLoc(), @@ -1302,6 +1299,17 @@ void AsmMatcherInfo::BuildInfo() { II->BuildAliasResultOperands(); } + // Process token alias definitions and set up the associated superclass + // information. + std::vector<Record*> AllTokenAliases = + Records.getAllDerivedDefinitions("TokenAlias"); + for (unsigned i = 0, e = AllTokenAliases.size(); i != e; ++i) { + Record *Rec = AllTokenAliases[i]; + ClassInfo *FromClass = getTokenClass(Rec->getValueAsString("FromToken")); + ClassInfo *ToClass = getTokenClass(Rec->getValueAsString("ToToken")); + FromClass->SuperClasses.push_back(ToClass); + } + // Reorder classes so that classes precede super classes. std::sort(Classes.begin(), Classes.end(), less_ptr<ClassInfo>()); } @@ -1663,7 +1671,7 @@ static void EmitMatchClassEnumeration(CodeGenTarget &Target, /// EmitValidateOperandClass - Emit the function to validate an operand class. static void EmitValidateOperandClass(AsmMatcherInfo &Info, raw_ostream &OS) { - OS << "static bool ValidateOperandClass(MCParsedAsmOperand *GOp, " + OS << "static bool validateOperandClass(MCParsedAsmOperand *GOp, " << "MatchClassKind Kind) {\n"; OS << " " << Info.Target.getName() << "Operand &Operand = *(" << Info.Target.getName() << "Operand*)GOp;\n"; @@ -1674,7 +1682,8 @@ static void EmitValidateOperandClass(AsmMatcherInfo &Info, // Check for Token operands first. OS << " if (Operand.isToken())\n"; - OS << " return MatchTokenString(Operand.getToken()) == Kind;\n\n"; + OS << " return isSubclass(matchTokenString(Operand.getToken()), Kind);" + << "\n\n"; // Check for register operands, including sub-classes. OS << " if (Operand.isReg()) {\n"; @@ -1688,7 +1697,7 @@ static void EmitValidateOperandClass(AsmMatcherInfo &Info, << it->first->getName() << ": OpKind = " << it->second->Name << "; break;\n"; OS << " }\n"; - OS << " return IsSubclass(OpKind, Kind);\n"; + OS << " return isSubclass(OpKind, Kind);\n"; OS << " }\n\n"; // Check the user classes. We don't care what order since we're only @@ -1715,8 +1724,8 @@ static void EmitValidateOperandClass(AsmMatcherInfo &Info, static void EmitIsSubclass(CodeGenTarget &Target, std::vector<ClassInfo*> &Infos, raw_ostream &OS) { - OS << "/// IsSubclass - Compute whether \\arg A is a subclass of \\arg B.\n"; - OS << "static bool IsSubclass(MatchClassKind A, MatchClassKind B) {\n"; + OS << "/// isSubclass - Compute whether \\arg A is a subclass of \\arg B.\n"; + OS << "static bool isSubclass(MatchClassKind A, MatchClassKind B) {\n"; OS << " if (A == B)\n"; OS << " return true;\n\n"; @@ -1727,32 +1736,30 @@ static void EmitIsSubclass(CodeGenTarget &Target, ie = Infos.end(); it != ie; ++it) { ClassInfo &A = **it; - if (A.Kind != ClassInfo::Token) { - std::vector<StringRef> SuperClasses; - for (std::vector<ClassInfo*>::iterator it = Infos.begin(), - ie = Infos.end(); it != ie; ++it) { - ClassInfo &B = **it; - - if (&A != &B && A.isSubsetOf(B)) - SuperClasses.push_back(B.Name); - } + std::vector<StringRef> SuperClasses; + for (std::vector<ClassInfo*>::iterator it = Infos.begin(), + ie = Infos.end(); it != ie; ++it) { + ClassInfo &B = **it; - if (SuperClasses.empty()) - continue; + if (&A != &B && A.isSubsetOf(B)) + SuperClasses.push_back(B.Name); + } - OS << "\n case " << A.Name << ":\n"; + if (SuperClasses.empty()) + continue; - if (SuperClasses.size() == 1) { - OS << " return B == " << SuperClasses.back() << ";\n"; - continue; - } + OS << "\n case " << A.Name << ":\n"; - OS << " switch (B) {\n"; - OS << " default: return false;\n"; - for (unsigned i = 0, e = SuperClasses.size(); i != e; ++i) - OS << " case " << SuperClasses[i] << ": return true;\n"; - OS << " }\n"; + if (SuperClasses.size() == 1) { + OS << " return B == " << SuperClasses.back() << ";\n"; + continue; } + + OS << " switch (B) {\n"; + OS << " default: return false;\n"; + for (unsigned i = 0, e = SuperClasses.size(); i != e; ++i) + OS << " case " << SuperClasses[i] << ": return true;\n"; + OS << " }\n"; } OS << " }\n"; OS << "}\n\n"; @@ -1774,7 +1781,7 @@ static void EmitMatchTokenString(CodeGenTarget &Target, "return " + CI.Name + ";")); } - OS << "static MatchClassKind MatchTokenString(StringRef Name) {\n"; + OS << "static MatchClassKind matchTokenString(StringRef Name) {\n"; StringMatcher("Name", Matches, OS).Emit(); @@ -1912,7 +1919,7 @@ static bool EmitMnemonicAliases(raw_ostream &OS, const AsmMatcherInfo &Info) { Info.getRecords().getAllDerivedDefinitions("MnemonicAlias"); if (Aliases.empty()) return false; - OS << "static void ApplyMnemonicAliases(StringRef &Mnemonic, " + OS << "static void applyMnemonicAliases(StringRef &Mnemonic, " "unsigned Features) {\n"; // Keep track of all the aliases from a mnemonic. Use an std::map so that the @@ -2061,7 +2068,7 @@ static void EmitCustomOperandParsing(raw_ostream &OS, CodeGenTarget &Target, // the found operand class. OS << Target.getName() << ClassName << "::OperandMatchResultTy " << Target.getName() << ClassName << "::\n" - << "TryCustomParseOperand(SmallVectorImpl<MCParsedAsmOperand*>" + << "tryCustomParseOperand(SmallVectorImpl<MCParsedAsmOperand*>" << " &Operands,\n unsigned MCK) {\n\n" << " switch(MCK) {\n"; @@ -2127,7 +2134,7 @@ static void EmitCustomOperandParsing(raw_ostream &OS, CodeGenTarget &Target, // Emit call to the custom parser method OS << " // call custom parse method to handle the operand\n"; OS << " OperandMatchResultTy Result = "; - OS << "TryCustomParseOperand(Operands, it->Class);\n"; + OS << "tryCustomParseOperand(Operands, it->Class);\n"; OS << " if (Result != MatchOperand_NoMatch)\n"; OS << " return Result;\n"; OS << " }\n\n"; @@ -2214,7 +2221,7 @@ void AsmMatcherEmitter::run(raw_ostream &OS) { OS << " SmallVectorImpl<MCParsedAsmOperand*> &Operands,\n"; OS << " StringRef Mnemonic);\n"; - OS << " OperandMatchResultTy TryCustomParseOperand(\n"; + OS << " OperandMatchResultTy tryCustomParseOperand(\n"; OS << " SmallVectorImpl<MCParsedAsmOperand*> &Operands,\n"; OS << " unsigned MCK);\n\n"; } @@ -2361,7 +2368,7 @@ void AsmMatcherEmitter::run(raw_ostream &OS) { if (HasMnemonicAliases) { OS << " // Process all MnemonicAliases to remap the mnemonic.\n"; - OS << " ApplyMnemonicAliases(Mnemonic, AvailableFeatures);\n\n"; + OS << " applyMnemonicAliases(Mnemonic, AvailableFeatures);\n\n"; } // Emit code to compute the class list for this operand vector. @@ -2403,7 +2410,7 @@ void AsmMatcherEmitter::run(raw_ostream &OS) { OS << " OperandsValid = (it->Classes[i] == " <<"InvalidMatchClass);\n"; OS << " break;\n"; OS << " }\n"; - OS << " if (ValidateOperandClass(Operands[i+1], " + OS << " if (validateOperandClass(Operands[i+1], " "(MatchClassKind)it->Classes[i]))\n"; OS << " continue;\n"; OS << " // If this operand is broken for all of the instances of this\n"; diff --git a/utils/TableGen/CMakeLists.txt b/utils/TableGen/CMakeLists.txt index 9e87515..ac33f99 100644 --- a/utils/TableGen/CMakeLists.txt +++ b/utils/TableGen/CMakeLists.txt @@ -17,6 +17,7 @@ add_tablegen(llvm-tblgen LLVM DAGISelMatcherGen.cpp DAGISelMatcherOpt.cpp DAGISelMatcher.cpp + DFAPacketizerEmitter.cpp DisassemblerEmitter.cpp EDEmitter.cpp FastISelEmitter.cpp diff --git a/utils/TableGen/CodeGenRegisters.cpp b/utils/TableGen/CodeGenRegisters.cpp index 8de4615..3aadf50 100644 --- a/utils/TableGen/CodeGenRegisters.cpp +++ b/utils/TableGen/CodeGenRegisters.cpp @@ -582,6 +582,23 @@ void CodeGenRegBank::addToMaps(CodeGenRegisterClass *RC) { Key2RC.insert(std::make_pair(K, RC)); } +// Create a synthetic sub-class if it is missing. +CodeGenRegisterClass* +CodeGenRegBank::getOrCreateSubClass(const CodeGenRegisterClass *RC, + const CodeGenRegister::Set *Members, + StringRef Name) { + // Synthetic sub-class has the same size and alignment as RC. + CodeGenRegisterClass::Key K(Members, RC->SpillSize, RC->SpillAlignment); + RCKeyMap::const_iterator FoundI = Key2RC.find(K); + if (FoundI != Key2RC.end()) + return FoundI->second; + + // Sub-class doesn't exist, create a new one. + CodeGenRegisterClass *NewRC = new CodeGenRegisterClass(Name, K); + addToMaps(NewRC); + return NewRC; +} + CodeGenRegisterClass *CodeGenRegBank::getRegClass(Record *Def) { if (CodeGenRegisterClass *RC = Def2RC[Def]) return RC; @@ -739,61 +756,102 @@ void CodeGenRegBank::computeDerivedInfo() { computeComposites(); } +// +// Synthesize missing register class intersections. +// +// Make sure that sub-classes of RC exists such that getCommonSubClass(RC, X) +// returns a maximal register class for all X. +// +void CodeGenRegBank::inferCommonSubClass(CodeGenRegisterClass *RC) { + for (unsigned rci = 0, rce = RegClasses.size(); rci != rce; ++rci) { + CodeGenRegisterClass *RC1 = RC; + CodeGenRegisterClass *RC2 = RegClasses[rci]; + if (RC1 == RC2) + continue; + + // Compute the set intersection of RC1 and RC2. + const CodeGenRegister::Set &Memb1 = RC1->getMembers(); + const CodeGenRegister::Set &Memb2 = RC2->getMembers(); + CodeGenRegister::Set Intersection; + std::set_intersection(Memb1.begin(), Memb1.end(), + Memb2.begin(), Memb2.end(), + std::inserter(Intersection, Intersection.begin()), + CodeGenRegister::Less()); + + // Skip disjoint class pairs. + if (Intersection.empty()) + continue; + + // If RC1 and RC2 have different spill sizes or alignments, use the + // larger size for sub-classing. If they are equal, prefer RC1. + if (RC2->SpillSize > RC1->SpillSize || + (RC2->SpillSize == RC1->SpillSize && + RC2->SpillAlignment > RC1->SpillAlignment)) + std::swap(RC1, RC2); + + getOrCreateSubClass(RC1, &Intersection, + RC1->getName() + "_and_" + RC2->getName()); + } +} + +// +// Synthesize missing sub-classes for getSubClassWithSubReg(). +// +// Make sure that the set of registers in RC with a given SubIdx sub-register +// form a register class. Update RC->SubClassWithSubReg. +// +void CodeGenRegBank::inferSubClassWithSubReg(CodeGenRegisterClass *RC) { + // Map SubRegIndex to set of registers in RC supporting that SubRegIndex. + typedef std::map<Record*, CodeGenRegister::Set, LessRecord> SubReg2SetMap; + + // Compute the set of registers supporting each SubRegIndex. + SubReg2SetMap SRSets; + for (CodeGenRegister::Set::const_iterator RI = RC->getMembers().begin(), + RE = RC->getMembers().end(); RI != RE; ++RI) { + const CodeGenRegister::SubRegMap &SRM = (*RI)->getSubRegs(); + for (CodeGenRegister::SubRegMap::const_iterator I = SRM.begin(), + E = SRM.end(); I != E; ++I) + SRSets[I->first].insert(*RI); + } + + // Find matching classes for all SRSets entries. Iterate in SubRegIndex + // numerical order to visit synthetic indices last. + for (unsigned sri = 0, sre = SubRegIndices.size(); sri != sre; ++sri) { + Record *SubIdx = SubRegIndices[sri]; + SubReg2SetMap::const_iterator I = SRSets.find(SubIdx); + // Unsupported SubRegIndex. Skip it. + if (I == SRSets.end()) + continue; + // In most cases, all RC registers support the SubRegIndex. + if (I->second.size() == RC->getMembers().size()) { + RC->setSubClassWithSubReg(SubIdx, RC); + continue; + } + // This is a real subset. See if we have a matching class. + CodeGenRegisterClass *SubRC = + getOrCreateSubClass(RC, &I->second, + RC->getName() + "_with_" + I->first->getName()); + RC->setSubClassWithSubReg(SubIdx, SubRC); + } +} + +// // Infer missing register classes. // -// For every register class RC, make sure that the set of registers in RC with -// a given SubIxx sub-register form a register class. void CodeGenRegBank::computeInferredRegisterClasses() { // When this function is called, the register classes have not been sorted // and assigned EnumValues yet. That means getSubClasses(), // getSuperClasses(), and hasSubClass() functions are defunct. - // Map SubRegIndex to register set. - typedef std::map<Record*, CodeGenRegister::Set, LessRecord> SubReg2SetMap; - // Visit all register classes, including the ones being added by the loop. for (unsigned rci = 0; rci != RegClasses.size(); ++rci) { - CodeGenRegisterClass &RC = *RegClasses[rci]; - - // Compute the set of registers supporting each SubRegIndex. - SubReg2SetMap SRSets; - for (CodeGenRegister::Set::const_iterator RI = RC.getMembers().begin(), - RE = RC.getMembers().end(); RI != RE; ++RI) { - const CodeGenRegister::SubRegMap &SRM = (*RI)->getSubRegs(); - for (CodeGenRegister::SubRegMap::const_iterator I = SRM.begin(), - E = SRM.end(); I != E; ++I) - SRSets[I->first].insert(*RI); - } + CodeGenRegisterClass *RC = RegClasses[rci]; - // Find matching classes for all SRSets entries. Iterate in SubRegIndex - // numerical order to visit synthetic indices last. - for (unsigned sri = 0, sre = SubRegIndices.size(); sri != sre; ++sri) { - Record *SubIdx = SubRegIndices[sri]; - SubReg2SetMap::const_iterator I = SRSets.find(SubIdx); - // Unsupported SubRegIndex. Skip it. - if (I == SRSets.end()) - continue; - // In most cases, all RC registers support the SubRegIndex. - if (I->second.size() == RC.getMembers().size()) { - RC.setSubClassWithSubReg(SubIdx, &RC); - continue; - } + // Synthesize answers for getSubClassWithSubReg(). + inferSubClassWithSubReg(RC); - // This is a real subset. See if we have a matching class. - CodeGenRegisterClass::Key K(&I->second, RC.SpillSize, RC.SpillAlignment); - RCKeyMap::const_iterator FoundI = Key2RC.find(K); - if (FoundI != Key2RC.end()) { - RC.setSubClassWithSubReg(SubIdx, FoundI->second); - continue; - } - - // Class doesn't exist. - CodeGenRegisterClass *NewRC = - new CodeGenRegisterClass(RC.getName() + "_with_" + - I->first->getName(), K); - addToMaps(NewRC); - RC.setSubClassWithSubReg(SubIdx, NewRC); - } + // Synthesize answers for getCommonSubClass(). + inferCommonSubClass(RC); } } diff --git a/utils/TableGen/CodeGenRegisters.h b/utils/TableGen/CodeGenRegisters.h index 4fc34b0..c74cfd6 100644 --- a/utils/TableGen/CodeGenRegisters.h +++ b/utils/TableGen/CodeGenRegisters.h @@ -237,8 +237,15 @@ namespace llvm { // Add RC to *2RC maps. void addToMaps(CodeGenRegisterClass*); + // Create a synthetic sub-class if it is missing. + CodeGenRegisterClass *getOrCreateSubClass(const CodeGenRegisterClass *RC, + const CodeGenRegister::Set *Membs, + StringRef Name); + // Infer missing register classes. void computeInferredRegisterClasses(); + void inferCommonSubClass(CodeGenRegisterClass *RC); + void inferSubClassWithSubReg(CodeGenRegisterClass *RC); // Composite SubRegIndex instances. // Map (SubRegIndex, SubRegIndex) -> SubRegIndex. diff --git a/utils/TableGen/CodeGenTarget.cpp b/utils/TableGen/CodeGenTarget.cpp index 6e1872e..c8d2b00 100644 --- a/utils/TableGen/CodeGenTarget.cpp +++ b/utils/TableGen/CodeGenTarget.cpp @@ -267,6 +267,7 @@ void CodeGenTarget::ComputeInstrsByEnum() const { "DBG_VALUE", "REG_SEQUENCE", "COPY", + "BUNDLE", 0 }; const DenseMap<const Record*, CodeGenInstruction*> &Insts = getInstructions(); diff --git a/utils/TableGen/DFAPacketizerEmitter.cpp b/utils/TableGen/DFAPacketizerEmitter.cpp new file mode 100644 index 0000000..2862d0c --- /dev/null +++ b/utils/TableGen/DFAPacketizerEmitter.cpp @@ -0,0 +1,512 @@ +//===- DFAPacketizerEmitter.cpp - Packetization DFA for a VLIW machine-----===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This class parses the Schedule.td file and produces an API that can be used +// to reason about whether an instruction can be added to a packet on a VLIW +// architecture. The class internally generates a deterministic finite +// automaton (DFA) that models all possible mappings of machine instructions +// to functional units as instructions are added to a packet. +// +//===----------------------------------------------------------------------===// + +#include "llvm/MC/MCInstrDesc.h" +#include "llvm/MC/MCInstrItineraries.h" +#include "llvm/TableGen/Record.h" +#include "CodeGenTarget.h" +#include "DFAPacketizerEmitter.h" +#include <list> + +using namespace llvm; + +// +// +// State represents the usage of machine resources if the packet contains +// a set of instruction classes. +// +// Specifically, currentState is a set of bit-masks. +// The nth bit in a bit-mask indicates whether the nth resource is being used +// by this state. The set of bit-masks in a state represent the different +// possible outcomes of transitioning to this state. +// For example: consider a two resource architecture: resource L and resource M +// with three instruction classes: L, M, and L_or_M. +// From the initial state (currentState = 0x00), if we add instruction class +// L_or_M we will transition to a state with currentState = [0x01, 0x10]. This +// represents the possible resource states that can result from adding a L_or_M +// instruction +// +// Another way of thinking about this transition is we are mapping a NDFA with +// two states [0x01] and [0x10] into a DFA with a single state [0x01, 0x10]. +// +// +namespace { +class State { + public: + static int currentStateNum; + int stateNum; + bool isInitial; + std::set<unsigned> stateInfo; + + State(); + State(const State &S); + + // + // canAddInsnClass - Returns true if an instruction of type InsnClass is a + // valid transition from this state, i.e., can an instruction of type InsnClass + // be added to the packet represented by this state. + // + // PossibleStates is the set of valid resource states that ensue from valid + // transitions. + // + bool canAddInsnClass(unsigned InsnClass, std::set<unsigned> &PossibleStates); +}; +} // End anonymous namespace. + + +namespace { +struct Transition { + public: + static int currentTransitionNum; + int transitionNum; + State *from; + unsigned input; + State *to; + + Transition(State *from_, unsigned input_, State *to_); +}; +} // End anonymous namespace. + + +// +// Comparators to keep set of states sorted. +// +namespace { +struct ltState { + bool operator()(const State *s1, const State *s2) const; +}; +} // End anonymous namespace. + + +// +// class DFA: deterministic finite automaton for processor resource tracking. +// +namespace { +class DFA { +public: + DFA(); + + // Set of states. Need to keep this sorted to emit the transition table. + std::set<State*, ltState> states; + + // Map from a state to the list of transitions with that state as source. + std::map<State*, SmallVector<Transition*, 16>, ltState> stateTransitions; + State *currentState; + + // Highest valued Input seen. + unsigned LargestInput; + + // + // Modify the DFA. + // + void initialize(); + void addState(State *); + void addTransition(Transition *); + + // + // getTransition - Return the state when a transition is made from + // State From with Input I. If a transition is not found, return NULL. + // + State *getTransition(State *, unsigned); + + // + // isValidTransition: Predicate that checks if there is a valid transition + // from state From on input InsnClass. + // + bool isValidTransition(State *From, unsigned InsnClass); + + // + // writeTable: Print out a table representing the DFA. + // + void writeTableAndAPI(raw_ostream &OS, const std::string &ClassName); +}; +} // End anonymous namespace. + + +// +// Constructors for State, Transition, and DFA +// +State::State() : + stateNum(currentStateNum++), isInitial(false) {} + + +State::State(const State &S) : + stateNum(currentStateNum++), isInitial(S.isInitial), + stateInfo(S.stateInfo) {} + + +Transition::Transition(State *from_, unsigned input_, State *to_) : + transitionNum(currentTransitionNum++), from(from_), input(input_), + to(to_) {} + + +DFA::DFA() : + LargestInput(0) {} + + +bool ltState::operator()(const State *s1, const State *s2) const { + return (s1->stateNum < s2->stateNum); +} + + +// +// canAddInsnClass - Returns true if an instruction of type InsnClass is a +// valid transition from this state i.e., can an instruction of type InsnClass +// be added to the packet represented by this state. +// +// PossibleStates is the set of valid resource states that ensue from valid +// transitions. +// +bool State::canAddInsnClass(unsigned InsnClass, + std::set<unsigned> &PossibleStates) { + // + // Iterate over all resource states in currentState. + // + bool AddedState = false; + + for (std::set<unsigned>::iterator SI = stateInfo.begin(); + SI != stateInfo.end(); ++SI) { + unsigned thisState = *SI; + + // + // Iterate over all possible resources used in InsnClass. + // For ex: for InsnClass = 0x11, all resources = {0x01, 0x10}. + // + + DenseSet<unsigned> VisitedResourceStates; + for (unsigned int j = 0; j < sizeof(InsnClass) * 8; ++j) { + if ((0x1 << j) & InsnClass) { + // + // For each possible resource used in InsnClass, generate the + // resource state if that resource was used. + // + unsigned ResultingResourceState = thisState | (0x1 << j); + // + // Check if the resulting resource state can be accommodated in this + // packet. + // We compute ResultingResourceState OR thisState. + // If the result of the OR is different than thisState, it implies + // that there is at least one resource that can be used to schedule + // InsnClass in the current packet. + // Insert ResultingResourceState into PossibleStates only if we haven't + // processed ResultingResourceState before. + // + if ((ResultingResourceState != thisState) && + (VisitedResourceStates.count(ResultingResourceState) == 0)) { + VisitedResourceStates.insert(ResultingResourceState); + PossibleStates.insert(ResultingResourceState); + AddedState = true; + } + } + } + } + + return AddedState; +} + + +void DFA::initialize() { + currentState->isInitial = true; +} + + +void DFA::addState(State *S) { + assert(!states.count(S) && "State already exists"); + states.insert(S); +} + + +void DFA::addTransition(Transition *T) { + // Update LargestInput. + if (T->input > LargestInput) + LargestInput = T->input; + + // Add the new transition. + stateTransitions[T->from].push_back(T); +} + + +// +// getTransition - Return the state when a transition is made from +// State From with Input I. If a transition is not found, return NULL. +// +State *DFA::getTransition(State *From, unsigned I) { + // Do we have a transition from state From? + if (!stateTransitions.count(From)) + return NULL; + + // Do we have a transition from state From with Input I? + for (SmallVector<Transition*, 16>::iterator VI = + stateTransitions[From].begin(); + VI != stateTransitions[From].end(); ++VI) + if ((*VI)->input == I) + return (*VI)->to; + + return NULL; +} + + +bool DFA::isValidTransition(State *From, unsigned InsnClass) { + return (getTransition(From, InsnClass) != NULL); +} + + +int State::currentStateNum = 0; +int Transition::currentTransitionNum = 0; + +DFAGen::DFAGen(RecordKeeper &R): + TargetName(CodeGenTarget(R).getName()), + allInsnClasses(), Records(R) {} + + +// +// writeTableAndAPI - Print out a table representing the DFA and the +// associated API to create a DFA packetizer. +// +// Format: +// DFAStateInputTable[][2] = pairs of <Input, Transition> for all valid +// transitions. +// DFAStateEntryTable[i] = Index of the first entry in DFAStateInputTable for +// the ith state. +// +// +void DFA::writeTableAndAPI(raw_ostream &OS, const std::string &TargetName) { + std::set<State*, ltState>::iterator SI = states.begin(); + // This table provides a map to the beginning of the transitions for State s + // in DFAStateInputTable. + std::vector<int> StateEntry(states.size()); + + OS << "namespace llvm {\n\n"; + OS << "const int " << TargetName << "DFAStateInputTable[][2] = {\n"; + + // Tracks the total valid transitions encountered so far. It is used + // to construct the StateEntry table. + int ValidTransitions = 0; + for (unsigned i = 0; i < states.size(); ++i, ++SI) { + StateEntry[i] = ValidTransitions; + for (unsigned j = 0; j <= LargestInput; ++j) { + assert (((*SI)->stateNum == (int) i) && "Mismatch in state numbers"); + if (!isValidTransition(*SI, j)) + continue; + + OS << "{" << j << ", " + << getTransition(*SI, j)->stateNum + << "}, "; + ++ValidTransitions; + } + + // If there are no valid transitions from this stage, we need a sentinel + // transition. + if (ValidTransitions == StateEntry[i]) + OS << "{-1, -1},"; + + OS << "\n"; + } + OS << "};\n\n"; + OS << "const unsigned int " << TargetName << "DFAStateEntryTable[] = {\n"; + + // Multiply i by 2 since each entry in DFAStateInputTable is a set of + // two numbers. + for (unsigned i = 0; i < states.size(); ++i) + OS << StateEntry[i] << ", "; + + OS << "\n};\n"; + OS << "} // namespace\n"; + + + // + // Emit DFA Packetizer tables if the target is a VLIW machine. + // + std::string SubTargetClassName = TargetName + "GenSubtargetInfo"; + OS << "\n" << "#include \"llvm/CodeGen/DFAPacketizer.h\"\n"; + OS << "namespace llvm {\n"; + OS << "DFAPacketizer *" << SubTargetClassName << "::" + << "createDFAPacketizer(const InstrItineraryData *IID) const {\n" + << " return new DFAPacketizer(IID, " << TargetName + << "DFAStateInputTable, " << TargetName << "DFAStateEntryTable);\n}\n\n"; + OS << "} // End llvm namespace \n"; +} + + +// +// collectAllInsnClasses - Populate allInsnClasses which is a set of units +// used in each stage. +// +void DFAGen::collectAllInsnClasses(const std::string &Name, + Record *ItinData, + unsigned &NStages, + raw_ostream &OS) { + // Collect processor itineraries. + std::vector<Record*> ProcItinList = + Records.getAllDerivedDefinitions("ProcessorItineraries"); + + // If just no itinerary then don't bother. + if (ProcItinList.size() < 2) + return; + std::map<std::string, unsigned> NameToBitsMap; + + // Parse functional units for all the itineraries. + for (unsigned i = 0, N = ProcItinList.size(); i < N; ++i) { + Record *Proc = ProcItinList[i]; + std::vector<Record*> FUs = Proc->getValueAsListOfDefs("FU"); + + // Convert macros to bits for each stage. + for (unsigned i = 0, N = FUs.size(); i < N; ++i) + NameToBitsMap[FUs[i]->getName()] = (unsigned) (1U << i); + } + + const std::vector<Record*> &StageList = + ItinData->getValueAsListOfDefs("Stages"); + + // The number of stages. + NStages = StageList.size(); + + // For each unit. + unsigned UnitBitValue = 0; + + // Compute the bitwise or of each unit used in this stage. + for (unsigned i = 0; i < NStages; ++i) { + const Record *Stage = StageList[i]; + + // Get unit list. + const std::vector<Record*> &UnitList = + Stage->getValueAsListOfDefs("Units"); + + for (unsigned j = 0, M = UnitList.size(); j < M; ++j) { + // Conduct bitwise or. + std::string UnitName = UnitList[j]->getName(); + assert(NameToBitsMap.count(UnitName)); + UnitBitValue |= NameToBitsMap[UnitName]; + } + + if (UnitBitValue != 0) + allInsnClasses.insert(UnitBitValue); + } +} + + +// +// Run the worklist algorithm to generate the DFA. +// +void DFAGen::run(raw_ostream &OS) { + EmitSourceFileHeader("Target DFA Packetizer Tables", OS); + + // Collect processor iteraries. + std::vector<Record*> ProcItinList = + Records.getAllDerivedDefinitions("ProcessorItineraries"); + + // + // Collect the instruction classes. + // + for (unsigned i = 0, N = ProcItinList.size(); i < N; i++) { + Record *Proc = ProcItinList[i]; + + // Get processor itinerary name. + const std::string &Name = Proc->getName(); + + // Skip default. + if (Name == "NoItineraries") + continue; + + // Sanity check for at least one instruction itinerary class. + unsigned NItinClasses = + Records.getAllDerivedDefinitions("InstrItinClass").size(); + if (NItinClasses == 0) + return; + + // Get itinerary data list. + std::vector<Record*> ItinDataList = Proc->getValueAsListOfDefs("IID"); + + // Collect instruction classes for all itinerary data. + for (unsigned j = 0, M = ItinDataList.size(); j < M; j++) { + Record *ItinData = ItinDataList[j]; + unsigned NStages; + collectAllInsnClasses(Name, ItinData, NStages, OS); + } + } + + + // + // Run a worklist algorithm to generate the DFA. + // + DFA D; + State *Initial = new State; + Initial->isInitial = true; + Initial->stateInfo.insert(0x0); + D.addState(Initial); + SmallVector<State*, 32> WorkList; + std::map<std::set<unsigned>, State*> Visited; + + WorkList.push_back(Initial); + + // + // Worklist algorithm to create a DFA for processor resource tracking. + // C = {set of InsnClasses} + // Begin with initial node in worklist. Initial node does not have + // any consumed resources, + // ResourceState = 0x0 + // Visited = {} + // While worklist != empty + // S = first element of worklist + // For every instruction class C + // if we can accommodate C in S: + // S' = state with resource states = {S Union C} + // Add a new transition: S x C -> S' + // If S' is not in Visited: + // Add S' to worklist + // Add S' to Visited + // + while (!WorkList.empty()) { + State *current = WorkList.pop_back_val(); + for (DenseSet<unsigned>::iterator CI = allInsnClasses.begin(), + CE = allInsnClasses.end(); CI != CE; ++CI) { + unsigned InsnClass = *CI; + + std::set<unsigned> NewStateResources; + // + // If we haven't already created a transition for this input + // and the state can accommodate this InsnClass, create a transition. + // + if (!D.getTransition(current, InsnClass) && + current->canAddInsnClass(InsnClass, NewStateResources)) { + State *NewState = NULL; + + // + // If we have seen this state before, then do not create a new state. + // + // + std::map<std::set<unsigned>, State*>::iterator VI; + if ((VI = Visited.find(NewStateResources)) != Visited.end()) + NewState = VI->second; + else { + NewState = new State; + NewState->stateInfo = NewStateResources; + D.addState(NewState); + Visited[NewStateResources] = NewState; + WorkList.push_back(NewState); + } + + Transition *NewTransition = new Transition(current, InsnClass, + NewState); + D.addTransition(NewTransition); + } + } + } + + // Print out the table. + D.writeTableAndAPI(OS, TargetName); +} diff --git a/utils/TableGen/DFAPacketizerEmitter.h b/utils/TableGen/DFAPacketizerEmitter.h new file mode 100644 index 0000000..8f47dde --- /dev/null +++ b/utils/TableGen/DFAPacketizerEmitter.h @@ -0,0 +1,54 @@ +//===- DFAPacketizerEmitter.h - Packetization DFA for a VLIW machine-------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This class parses the Schedule.td file and produces an API that can be used +// to reason about whether an instruction can be added to a packet on a VLIW +// architecture. The class internally generates a deterministic finite +// automaton (DFA) that models all possible mappings of machine instructions +// to functional units as instructions are added to a packet. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/TableGen/TableGenBackend.h" +#include <map> +#include <string> + +namespace llvm { +// +// class DFAGen: class that generates and prints out the DFA for resource +// tracking. +// +class DFAGen : public TableGenBackend { +private: + std::string TargetName; + // + // allInsnClasses is the set of all possible resources consumed by an + // InstrStage. + // + DenseSet<unsigned> allInsnClasses; + RecordKeeper &Records; + +public: + DFAGen(RecordKeeper &R); + + // + // collectAllInsnClasses: Populate allInsnClasses which is a set of units + // used in each stage. + // + void collectAllInsnClasses(const std::string &Name, + Record *ItinData, + unsigned &NStages, + raw_ostream &OS); + + void run(raw_ostream &OS); +}; +} diff --git a/utils/TableGen/EDEmitter.cpp b/utils/TableGen/EDEmitter.cpp index 1953dad..6c3cae2 100644 --- a/utils/TableGen/EDEmitter.cpp +++ b/utils/TableGen/EDEmitter.cpp @@ -576,6 +576,8 @@ static int ARMFlagFromOpName(LiteralConstantEmitter *type, REG("VecListThreeD"); REG("VecListFourD"); REG("VecListTwoQ"); + REG("VecListOneDAllLanes"); + REG("VecListTwoDAllLanes"); IMM("i32imm"); IMM("i32imm_hilo16"); @@ -608,6 +610,14 @@ static int ARMFlagFromOpName(LiteralConstantEmitter *type, IMM("nImmSplatI64"); IMM("nImmVMOVI32"); IMM("nImmVMOVF32"); + IMM("imm8"); + IMM("imm16"); + IMM("imm32"); + IMM("imm1_7"); + IMM("imm1_15"); + IMM("imm1_31"); + IMM("imm0_1"); + IMM("imm0_3"); IMM("imm0_7"); IMM("imm0_15"); IMM("imm0_255"); @@ -746,7 +756,7 @@ static void ARMPopulateOperands( errs() << "Operand type: " << rec.getName() << '\n'; errs() << "Operand name: " << operandInfo.Name << '\n'; errs() << "Instruction name: " << inst.TheDef->getName() << '\n'; - llvm_unreachable("Unhandled type"); + throw("Unhandled type in EDEmitter"); } } } diff --git a/utils/TableGen/LLVMBuild.txt b/utils/TableGen/LLVMBuild.txt index b2a8ac6..b0081eb 100644 --- a/utils/TableGen/LLVMBuild.txt +++ b/utils/TableGen/LLVMBuild.txt @@ -20,4 +20,3 @@ type = BuildTool name = tblgen parent = BuildTools required_libraries = Support TableGen - diff --git a/utils/TableGen/SubtargetEmitter.cpp b/utils/TableGen/SubtargetEmitter.cpp index 3a6ff4e..34cd9a9 100644 --- a/utils/TableGen/SubtargetEmitter.cpp +++ b/utils/TableGen/SubtargetEmitter.cpp @@ -711,9 +711,13 @@ void SubtargetEmitter::run(raw_ostream &OS) { std::string ClassName = Target + "GenSubtargetInfo"; OS << "namespace llvm {\n"; + OS << "class DFAPacketizer;\n"; OS << "struct " << ClassName << " : public TargetSubtargetInfo {\n" << " explicit " << ClassName << "(StringRef TT, StringRef CPU, " << "StringRef FS);\n" + << "public:\n" + << " DFAPacketizer *createDFAPacketizer(const InstrItineraryData *IID)" + << " const;\n" << "};\n"; OS << "} // End llvm namespace \n"; diff --git a/utils/TableGen/TableGen.cpp b/utils/TableGen/TableGen.cpp index 12ebc57..3899a41 100644 --- a/utils/TableGen/TableGen.cpp +++ b/utils/TableGen/TableGen.cpp @@ -16,6 +16,7 @@ #include "CallingConvEmitter.h" #include "CodeEmitterGen.h" #include "DAGISelEmitter.h" +#include "DFAPacketizerEmitter.h" #include "DisassemblerEmitter.h" #include "EDEmitter.h" #include "FastISelEmitter.h" @@ -47,6 +48,7 @@ enum ActionType { GenPseudoLowering, GenCallingConv, GenDAGISel, + GenDFAPacketizer, GenFastISel, GenSubtarget, GenIntrinsic, @@ -79,6 +81,8 @@ namespace { "Generate assembly instruction matcher"), clEnumValN(GenDAGISel, "gen-dag-isel", "Generate a DAG instruction selector"), + clEnumValN(GenDFAPacketizer, "gen-dfa-packetizer", + "Generate DFA Packetizer for VLIW targets"), clEnumValN(GenFastISel, "gen-fast-isel", "Generate a \"fast\" instruction selector"), clEnumValN(GenSubtarget, "gen-subtarget", @@ -134,6 +138,9 @@ public: case GenDAGISel: DAGISelEmitter(Records).run(OS); break; + case GenDFAPacketizer: + DFAGen(Records).run(OS); + break; case GenFastISel: FastISelEmitter(Records).run(OS); break; |