X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2FTableGen%2FDAGISelMatcherEmitter.cpp;h=26f53dca63618c65783b208d11d5739403334150;hb=47f0e3f434e2e43f951c3a826c40906cb15b7285;hp=c6addd8b0db4ee713f8ff64e245493ff7b1a30d9;hpb=ff7fb60f2a7e2f3efd54df6480aadcb4adf5cab7;p=oota-llvm.git diff --git a/utils/TableGen/DAGISelMatcherEmitter.cpp b/utils/TableGen/DAGISelMatcherEmitter.cpp index c6addd8b0db..26f53dca636 100644 --- a/utils/TableGen/DAGISelMatcherEmitter.cpp +++ b/utils/TableGen/DAGISelMatcherEmitter.cpp @@ -7,98 +7,87 @@ // //===----------------------------------------------------------------------===// // -// This file contains code to generate C++ code a matcher. +// This file contains code to generate C++ code for a matcher. // //===----------------------------------------------------------------------===// #include "DAGISelMatcher.h" #include "CodeGenDAGPatterns.h" -#include "Record.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/SmallString.h" #include "llvm/ADT/StringMap.h" +#include "llvm/ADT/TinyPtrVector.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Support/FormattedStream.h" +#include "llvm/TableGen/Record.h" using namespace llvm; enum { CommentIndent = 30 }; -/// ClassifyInt - Classify an integer by size, return '1','2','4','8' if this -/// fits in 1, 2, 4, or 8 sign extended bytes. -static char ClassifyInt(int64_t Val) { - if (Val == int8_t(Val)) return '1'; - if (Val == int16_t(Val)) return '2'; - if (Val == int32_t(Val)) return '4'; - return '8'; -} - -/// EmitInt - Emit the specified integer, returning the number of bytes emitted. -static unsigned EmitInt(int64_t Val, formatted_raw_ostream &OS) { - unsigned BytesEmitted = 1; - OS << (int)(unsigned char)Val << ", "; - if (Val == int8_t(Val)) { - OS << '\n'; - return BytesEmitted; - } - - OS << (int)(unsigned char)(Val >> 8) << ", "; - ++BytesEmitted; - - if (Val != int16_t(Val)) { - OS << (int)(unsigned char)(Val >> 16) << ", " - << (int)(unsigned char)(Val >> 24) << ", "; - BytesEmitted += 2; - - if (Val != int32_t(Val)) { - OS << (int)(unsigned char)(Val >> 32) << ", " - << (int)(unsigned char)(Val >> 40) << ", " - << (int)(unsigned char)(Val >> 48) << ", " - << (int)(unsigned char)(Val >> 56) << ", "; - BytesEmitted += 4; - } - } - - OS.PadToColumn(CommentIndent) << "// " << Val << " aka 0x"; - OS.write_hex(Val) << '\n'; - return BytesEmitted; -} +// To reduce generated source code size. +static cl::opt +OmitComments("omit-comments", cl::desc("Do not generate comments"), + cl::init(false)); namespace { class MatcherTableEmitter { - StringMap NodePredicateMap, PatternPredicateMap; - std::vector NodePredicates, PatternPredicates; + const CodeGenDAGPatterns &CGP; + + DenseMap NodePredicateMap; + std::vector NodePredicates; + + // We de-duplicate the predicates by code string, and use this map to track + // all the patterns with "identical" predicates. + StringMap> NodePredicatesByCodeToRun; + + StringMap PatternPredicateMap; + std::vector PatternPredicates; DenseMap ComplexPatternMap; std::vector ComplexPatterns; DenseMap NodeXFormMap; - std::vector NodeXForms; + std::vector NodeXForms; - // Per opcode frequence count. - std::vector Histogram; public: - MatcherTableEmitter() {} + MatcherTableEmitter(const CodeGenDAGPatterns &cgp) + : CGP(cgp) {} unsigned EmitMatcherList(const Matcher *N, unsigned Indent, unsigned StartIdx, formatted_raw_ostream &OS); - + void EmitPredicateFunctions(formatted_raw_ostream &OS); - - void EmitHistogram(formatted_raw_ostream &OS); + + void EmitHistogram(const Matcher *N, formatted_raw_ostream &OS); private: unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, formatted_raw_ostream &OS); - - unsigned getNodePredicate(StringRef PredName) { - unsigned &Entry = NodePredicateMap[PredName]; + + unsigned getNodePredicate(TreePredicateFn Pred) { + TreePattern *TP = Pred.getOrigPatFragRecord(); + unsigned &Entry = NodePredicateMap[TP]; if (Entry == 0) { - NodePredicates.push_back(PredName.str()); - Entry = NodePredicates.size(); + TinyPtrVector &SameCodePreds = + NodePredicatesByCodeToRun[Pred.getCodeToRunOnSDNode()]; + if (SameCodePreds.empty()) { + // We've never seen a predicate with the same code: allocate an entry. + NodePredicates.push_back(Pred); + Entry = NodePredicates.size(); + } else { + // We did see an identical predicate: re-use it. + Entry = NodePredicateMap[SameCodePreds.front()]; + assert(Entry != 0); + } + // In both cases, we've never seen this particular predicate before, so + // mark it in the list of predicates sharing the same code. + SameCodePreds.push_back(TP); } return Entry-1; } + unsigned getPatternPredicate(StringRef PredName) { unsigned &Entry = PatternPredicateMap[PredName]; if (Entry == 0) { @@ -107,7 +96,6 @@ private: } return Entry-1; } - unsigned getComplexPat(const ComplexPattern &P) { unsigned &Entry = ComplexPatternMap[&P]; if (Entry == 0) { @@ -116,7 +104,7 @@ private: } return Entry-1; } - + unsigned getNodeXFormID(Record *Rec) { unsigned &Entry = NodeXFormMap[Rec]; if (Entry == 0) { @@ -125,13 +113,13 @@ private: } return Entry-1; } - + }; } // end anonymous namespace. static unsigned GetVBRSize(unsigned Val) { if (Val <= 127) return 1; - + unsigned NumBytes = 0; while (Val >= 128) { Val >>= 7; @@ -142,45 +130,51 @@ static unsigned GetVBRSize(unsigned Val) { /// EmitVBRValue - Emit the specified value as a VBR, returning the number of /// bytes emitted. -static unsigned EmitVBRValue(unsigned Val, raw_ostream &OS) { +static uint64_t EmitVBRValue(uint64_t Val, raw_ostream &OS) { if (Val <= 127) { OS << Val << ", "; return 1; } - - unsigned InVal = Val; + + uint64_t InVal = Val; unsigned NumBytes = 0; while (Val >= 128) { OS << (Val&127) << "|128,"; Val >>= 7; ++NumBytes; } - OS << Val << "/*" << InVal << "*/, "; + OS << Val; + if (!OmitComments) + OS << "/*" << InVal << "*/"; + OS << ", "; return NumBytes+1; } -/// EmitMatcherOpcodes - Emit bytes for the specified matcher and return +/// EmitMatcher - Emit bytes for the specified matcher and return /// the number of bytes emitted. unsigned MatcherTableEmitter:: EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, formatted_raw_ostream &OS) { OS.PadToColumn(Indent*2); - + switch (N->getKind()) { case Matcher::Scope: { const ScopeMatcher *SM = cast(N); - assert(SM->getNext() == 0 && "Shouldn't have next after scope"); - + assert(SM->getNext() == nullptr && "Shouldn't have next after scope"); + unsigned StartIdx = CurrentIdx; - + // Emit all of the children. for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) { if (i == 0) { OS << "OPC_Scope, "; ++CurrentIdx; - } else { - OS << "/*" << CurrentIdx << "*/"; - OS.PadToColumn(Indent*2) << "/*Scope*/ "; + } else { + if (!OmitComments) { + OS << "/*" << CurrentIdx << "*/"; + OS.PadToColumn(Indent*2) << "/*Scope*/ "; + } else + OS.PadToColumn(Indent*2); } // We need to encode the child and the offset of the failure code before @@ -193,182 +187,325 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, unsigned VBRSize = 0; do { VBRSize = GetVBRSize(ChildSize); - + TmpBuf.clear(); raw_svector_ostream OS(TmpBuf); formatted_raw_ostream FOS(OS); - ChildSize = EmitMatcherList(cast(N)->getChild(i), - Indent+1, CurrentIdx+VBRSize, FOS); + ChildSize = EmitMatcherList(SM->getChild(i), Indent+1, + CurrentIdx+VBRSize, FOS); } while (GetVBRSize(ChildSize) != VBRSize); - + assert(ChildSize != 0 && "Should not have a zero-sized child!"); - + CurrentIdx += EmitVBRValue(ChildSize, OS); - OS << "/*->" << CurrentIdx+ChildSize << "*/"; - - if (i == 0) - OS.PadToColumn(CommentIndent) << "// " << SM->getNumChildren() - << " children in Scope"; - - OS << '\n' << TmpBuf.str(); + if (!OmitComments) { + OS << "/*->" << CurrentIdx+ChildSize << "*/"; + + if (i == 0) + OS.PadToColumn(CommentIndent) << "// " << SM->getNumChildren() + << " children in Scope"; + } + + OS << '\n' << TmpBuf; CurrentIdx += ChildSize; } - + // Emit a zero as a sentinel indicating end of 'Scope'. - OS << "/*" << CurrentIdx << "*/"; - OS.PadToColumn(Indent*2) << "0, /*End of Scope*/\n"; + if (!OmitComments) + OS << "/*" << CurrentIdx << "*/"; + OS.PadToColumn(Indent*2) << "0, "; + if (!OmitComments) + OS << "/*End of Scope*/"; + OS << '\n'; return CurrentIdx - StartIdx + 1; } - + case Matcher::RecordNode: OS << "OPC_RecordNode,"; - OS.PadToColumn(CommentIndent) << "// " - << cast(N)->getWhatFor() << '\n'; + if (!OmitComments) + OS.PadToColumn(CommentIndent) << "// #" + << cast(N)->getResultNo() << " = " + << cast(N)->getWhatFor(); + OS << '\n'; return 1; case Matcher::RecordChild: OS << "OPC_RecordChild" << cast(N)->getChildNo() << ','; - OS.PadToColumn(CommentIndent) << "// " - << cast(N)->getWhatFor() << '\n'; + if (!OmitComments) + OS.PadToColumn(CommentIndent) << "// #" + << cast(N)->getResultNo() << " = " + << cast(N)->getWhatFor(); + OS << '\n'; return 1; - + case Matcher::RecordMemRef: OS << "OPC_RecordMemRef,\n"; return 1; - - case Matcher::CaptureFlagInput: - OS << "OPC_CaptureFlagInput,\n"; + + case Matcher::CaptureGlueInput: + OS << "OPC_CaptureGlueInput,\n"; return 1; - + case Matcher::MoveChild: OS << "OPC_MoveChild, " << cast(N)->getChildNo() << ",\n"; return 2; - + case Matcher::MoveParent: OS << "OPC_MoveParent,\n"; return 1; - + case Matcher::CheckSame: OS << "OPC_CheckSame, " << cast(N)->getMatchNumber() << ",\n"; return 2; + case Matcher::CheckChildSame: + OS << "OPC_CheckChild" + << cast(N)->getChildNo() << "Same, " + << cast(N)->getMatchNumber() << ",\n"; + return 2; + case Matcher::CheckPatternPredicate: { - StringRef Pred = cast(N)->getPredicate(); + StringRef Pred =cast(N)->getPredicate(); OS << "OPC_CheckPatternPredicate, " << getPatternPredicate(Pred) << ','; - OS.PadToColumn(CommentIndent) << "// " << Pred << '\n'; + if (!OmitComments) + OS.PadToColumn(CommentIndent) << "// " << Pred; + OS << '\n'; return 2; } case Matcher::CheckPredicate: { - StringRef Pred = cast(N)->getPredicateName(); + TreePredicateFn Pred = cast(N)->getPredicate(); OS << "OPC_CheckPredicate, " << getNodePredicate(Pred) << ','; - OS.PadToColumn(CommentIndent) << "// " << Pred << '\n'; + if (!OmitComments) + OS.PadToColumn(CommentIndent) << "// " << Pred.getFnName(); + OS << '\n'; return 2; } case Matcher::CheckOpcode: - OS << "OPC_CheckOpcode, " - << cast(N)->getOpcode().getEnumName() << ",\n"; - return 2; - - case Matcher::CheckMultiOpcode: { - const CheckMultiOpcodeMatcher *CMO = cast(N); - OS << "OPC_CheckMultiOpcode, " << CMO->getNumOpcodes() << ", "; - for (unsigned i = 0, e = CMO->getNumOpcodes(); i != e; ++i) - OS << CMO->getOpcode(i).getEnumName() << ", "; + OS << "OPC_CheckOpcode, TARGET_VAL(" + << cast(N)->getOpcode().getEnumName() << "),\n"; + return 3; + + case Matcher::SwitchOpcode: + case Matcher::SwitchType: { + unsigned StartIdx = CurrentIdx; + + unsigned NumCases; + if (const SwitchOpcodeMatcher *SOM = dyn_cast(N)) { + OS << "OPC_SwitchOpcode "; + NumCases = SOM->getNumCases(); + } else { + OS << "OPC_SwitchType "; + NumCases = cast(N)->getNumCases(); + } + + if (!OmitComments) + OS << "/*" << NumCases << " cases */"; + OS << ", "; + ++CurrentIdx; + + // For each case we emit the size, then the opcode, then the matcher. + for (unsigned i = 0, e = NumCases; i != e; ++i) { + const Matcher *Child; + unsigned IdxSize; + if (const SwitchOpcodeMatcher *SOM = dyn_cast(N)) { + Child = SOM->getCaseMatcher(i); + IdxSize = 2; // size of opcode in table is 2 bytes. + } else { + Child = cast(N)->getCaseMatcher(i); + IdxSize = 1; // size of type in table is 1 byte. + } + + // We need to encode the opcode and the offset of the case code before + // emitting the case code. Handle this by buffering the output into a + // string while we get the size. Unfortunately, the offset of the + // children depends on the VBR size of the child, so for large children we + // have to iterate a bit. + SmallString<128> TmpBuf; + unsigned ChildSize = 0; + unsigned VBRSize = 0; + do { + VBRSize = GetVBRSize(ChildSize); + + TmpBuf.clear(); + raw_svector_ostream OS(TmpBuf); + formatted_raw_ostream FOS(OS); + ChildSize = EmitMatcherList(Child, Indent+1, CurrentIdx+VBRSize+IdxSize, + FOS); + } while (GetVBRSize(ChildSize) != VBRSize); + + assert(ChildSize != 0 && "Should not have a zero-sized child!"); + + if (i != 0) { + if (!OmitComments) + OS << "/*" << CurrentIdx << "*/"; + OS.PadToColumn(Indent*2); + if (!OmitComments) + OS << (isa(N) ? + "/*SwitchOpcode*/ " : "/*SwitchType*/ "); + } + + // Emit the VBR. + CurrentIdx += EmitVBRValue(ChildSize, OS); + + if (const SwitchOpcodeMatcher *SOM = dyn_cast(N)) + OS << "TARGET_VAL(" << SOM->getCaseOpcode(i).getEnumName() << "),"; + else + OS << getEnumName(cast(N)->getCaseType(i)) << ','; + + CurrentIdx += IdxSize; + + if (!OmitComments) + OS << "// ->" << CurrentIdx+ChildSize; + OS << '\n'; + OS << TmpBuf; + CurrentIdx += ChildSize; + } + + // Emit the final zero to terminate the switch. + if (!OmitComments) + OS << "/*" << CurrentIdx << "*/"; + OS.PadToColumn(Indent*2) << "0, "; + if (!OmitComments) + OS << (isa(N) ? + "// EndSwitchOpcode" : "// EndSwitchType"); + OS << '\n'; - return 2 + CMO->getNumOpcodes(); + ++CurrentIdx; + return CurrentIdx-StartIdx; } - - case Matcher::CheckType: + + case Matcher::CheckType: + assert(cast(N)->getResNo() == 0 && + "FIXME: Add support for CheckType of resno != 0"); OS << "OPC_CheckType, " << getEnumName(cast(N)->getType()) << ",\n"; return 2; + case Matcher::CheckChildType: OS << "OPC_CheckChild" << cast(N)->getChildNo() << "Type, " << getEnumName(cast(N)->getType()) << ",\n"; return 2; - + case Matcher::CheckInteger: { - int64_t Val = cast(N)->getValue(); - OS << "OPC_CheckInteger" << ClassifyInt(Val) << ", "; - return EmitInt(Val, OS)+1; - } + OS << "OPC_CheckInteger, "; + unsigned Bytes=1+EmitVBRValue(cast(N)->getValue(), OS); + OS << '\n'; + return Bytes; + } + case Matcher::CheckChildInteger: { + OS << "OPC_CheckChild" << cast(N)->getChildNo() + << "Integer, "; + unsigned Bytes=1+EmitVBRValue(cast(N)->getValue(), + OS); + OS << '\n'; + return Bytes; + } case Matcher::CheckCondCode: OS << "OPC_CheckCondCode, ISD::" << cast(N)->getCondCodeName() << ",\n"; return 2; - + case Matcher::CheckValueType: OS << "OPC_CheckValueType, MVT::" << cast(N)->getTypeName() << ",\n"; return 2; case Matcher::CheckComplexPat: { - const ComplexPattern &Pattern = - cast(N)->getPattern(); - OS << "OPC_CheckComplexPat, " << getComplexPat(Pattern) << ','; - OS.PadToColumn(CommentIndent) << "// " << Pattern.getSelectFunc(); - OS << ": " << Pattern.getNumOperands() << " operands"; - if (Pattern.hasProperty(SDNPHasChain)) - OS << " + chain result and input"; + const CheckComplexPatMatcher *CCPM = cast(N); + const ComplexPattern &Pattern = CCPM->getPattern(); + OS << "OPC_CheckComplexPat, /*CP*/" << getComplexPat(Pattern) << ", /*#*/" + << CCPM->getMatchNumber() << ','; + + if (!OmitComments) { + OS.PadToColumn(CommentIndent) << "// " << Pattern.getSelectFunc(); + OS << ":$" << CCPM->getName(); + for (unsigned i = 0, e = Pattern.getNumOperands(); i != e; ++i) + OS << " #" << CCPM->getFirstResult()+i; + + if (Pattern.hasProperty(SDNPHasChain)) + OS << " + chain result"; + } OS << '\n'; - return 2; + return 3; } - + case Matcher::CheckAndImm: { - int64_t Val = cast(N)->getValue(); - OS << "OPC_CheckAndImm" << ClassifyInt(Val) << ", "; - return EmitInt(Val, OS)+1; + OS << "OPC_CheckAndImm, "; + unsigned Bytes=1+EmitVBRValue(cast(N)->getValue(), OS); + OS << '\n'; + return Bytes; } case Matcher::CheckOrImm: { - int64_t Val = cast(N)->getValue(); - OS << "OPC_CheckOrImm" << ClassifyInt(Val) << ", "; - return EmitInt(Val, OS)+1; + OS << "OPC_CheckOrImm, "; + unsigned Bytes = 1+EmitVBRValue(cast(N)->getValue(), OS); + OS << '\n'; + return Bytes; } + case Matcher::CheckFoldableChainNode: OS << "OPC_CheckFoldableChainNode,\n"; return 1; - case Matcher::CheckChainCompatible: - OS << "OPC_CheckChainCompatible, " - << cast(N)->getPreviousOp() << ",\n"; - return 2; - + case Matcher::EmitInteger: { int64_t Val = cast(N)->getValue(); - OS << "OPC_EmitInteger" << ClassifyInt(Val) << ", " + OS << "OPC_EmitInteger, " << getEnumName(cast(N)->getVT()) << ", "; - return EmitInt(Val, OS)+2; + unsigned Bytes = 2+EmitVBRValue(Val, OS); + OS << '\n'; + return Bytes; } case Matcher::EmitStringInteger: { const std::string &Val = cast(N)->getValue(); // These should always fit into one byte. - OS << "OPC_EmitInteger1, " + OS << "OPC_EmitInteger, " << getEnumName(cast(N)->getVT()) << ", " << Val << ",\n"; return 3; } - - case Matcher::EmitRegister: - OS << "OPC_EmitRegister, " - << getEnumName(cast(N)->getVT()) << ", "; - if (Record *R = cast(N)->getReg()) - OS << getQualifiedName(R) << ",\n"; - else - OS << "0 /*zero_reg*/,\n"; - return 3; - + + case Matcher::EmitRegister: { + const EmitRegisterMatcher *Matcher = cast(N); + const CodeGenRegister *Reg = Matcher->getReg(); + // If the enum value of the register is larger than one byte can handle, + // use EmitRegister2. + if (Reg && Reg->EnumValue > 255) { + OS << "OPC_EmitRegister2, " << getEnumName(Matcher->getVT()) << ", "; + OS << "TARGET_VAL(" << getQualifiedName(Reg->TheDef) << "),\n"; + return 4; + } else { + OS << "OPC_EmitRegister, " << getEnumName(Matcher->getVT()) << ", "; + if (Reg) { + OS << getQualifiedName(Reg->TheDef) << ",\n"; + } else { + OS << "0 "; + if (!OmitComments) + OS << "/*zero_reg*/"; + OS << ",\n"; + } + return 3; + } + } + case Matcher::EmitConvertToTarget: OS << "OPC_EmitConvertToTarget, " << cast(N)->getSlot() << ",\n"; return 2; - + case Matcher::EmitMergeInputChains: { const EmitMergeInputChainsMatcher *MN = cast(N); + + // Handle the specialized forms OPC_EmitMergeInputChains1_0 and 1_1. + if (MN->getNumNodes() == 1 && MN->getNode(0) < 2) { + OS << "OPC_EmitMergeInputChains1_" << MN->getNode(0) << ",\n"; + return 1; + } + OS << "OPC_EmitMergeInputChains, " << MN->getNumNodes() << ", "; for (unsigned i = 0, e = MN->getNumNodes(); i != e; ++i) OS << MN->getNode(i) << ", "; @@ -385,60 +522,68 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, const EmitNodeXFormMatcher *XF = cast(N); OS << "OPC_EmitNodeXForm, " << getNodeXFormID(XF->getNodeXForm()) << ", " << XF->getSlot() << ','; - OS.PadToColumn(CommentIndent) << "// "<getNodeXForm()->getName()<<'\n'; + if (!OmitComments) + OS.PadToColumn(CommentIndent) << "// "<getNodeXForm()->getName(); + OS <<'\n'; return 3; } - + case Matcher::EmitNode: case Matcher::MorphNodeTo: { const EmitNodeMatcherCommon *EN = cast(N); OS << (isa(EN) ? "OPC_EmitNode" : "OPC_MorphNodeTo"); - OS << ", TARGET_OPCODE(" << EN->getOpcodeName() << "), 0"; - + OS << ", TARGET_VAL(" << EN->getOpcodeName() << "), 0"; + if (EN->hasChain()) OS << "|OPFL_Chain"; - if (EN->hasInFlag()) OS << "|OPFL_FlagInput"; - if (EN->hasOutFlag()) OS << "|OPFL_FlagOutput"; + if (EN->hasInFlag()) OS << "|OPFL_GlueInput"; + if (EN->hasOutFlag()) OS << "|OPFL_GlueOutput"; if (EN->hasMemRefs()) OS << "|OPFL_MemRefs"; if (EN->getNumFixedArityOperands() != -1) OS << "|OPFL_Variadic" << EN->getNumFixedArityOperands(); OS << ",\n"; - - OS.PadToColumn(Indent*2+4) << EN->getNumVTs() << "/*#VTs*/, "; + + OS.PadToColumn(Indent*2+4) << EN->getNumVTs(); + if (!OmitComments) + OS << "/*#VTs*/"; + OS << ", "; for (unsigned i = 0, e = EN->getNumVTs(); i != e; ++i) OS << getEnumName(EN->getVT(i)) << ", "; - OS << EN->getNumOperands() << "/*#Ops*/, "; + OS << EN->getNumOperands(); + if (!OmitComments) + OS << "/*#Ops*/"; + OS << ", "; unsigned NumOperandBytes = 0; - for (unsigned i = 0, e = EN->getNumOperands(); i != e; ++i) { - // We emit the operand numbers in VBR encoded format, in case the number - // is too large to represent with a byte. + for (unsigned i = 0, e = EN->getNumOperands(); i != e; ++i) NumOperandBytes += EmitVBRValue(EN->getOperand(i), OS); - } - - // Print the result #'s for EmitNode. - if (const EmitNodeMatcher *E = dyn_cast(EN)) { - if (unsigned NumResults = EN->getNumNonChainFlagVTs()) { - OS.PadToColumn(CommentIndent) << "// Results = "; - unsigned First = E->getFirstResultSlot(); - for (unsigned i = 0; i != NumResults; ++i) - OS << "#" << First+i << " "; + + if (!OmitComments) { + // Print the result #'s for EmitNode. + if (const EmitNodeMatcher *E = dyn_cast(EN)) { + if (unsigned NumResults = EN->getNumVTs()) { + OS.PadToColumn(CommentIndent) << "// Results ="; + unsigned First = E->getFirstResultSlot(); + for (unsigned i = 0; i != NumResults; ++i) + OS << " #" << First+i; + } } - } - OS << '\n'; - - if (const MorphNodeToMatcher *SNT = dyn_cast(N)) { - OS.PadToColumn(Indent*2) << "// Src: " - << *SNT->getPattern().getSrcPattern() << '\n'; - OS.PadToColumn(Indent*2) << "// Dst: " - << *SNT->getPattern().getDstPattern() << '\n'; - - } - + OS << '\n'; + + if (const MorphNodeToMatcher *SNT = dyn_cast(N)) { + OS.PadToColumn(Indent*2) << "// Src: " + << *SNT->getPattern().getSrcPattern() << " - Complexity = " + << SNT->getPattern().getPatternComplexity(CGP) << '\n'; + OS.PadToColumn(Indent*2) << "// Dst: " + << *SNT->getPattern().getDstPattern() << '\n'; + } + } else + OS << '\n'; + return 6+EN->getNumVTs()+NumOperandBytes; } - case Matcher::MarkFlagResults: { - const MarkFlagResultsMatcher *CFR = cast(N); - OS << "OPC_MarkFlagResults, " << CFR->getNumNodes() << ", "; + case Matcher::MarkGlueResults: { + const MarkGlueResultsMatcher *CFR = cast(N); + OS << "OPC_MarkGlueResults, " << CFR->getNumNodes() << ", "; unsigned NumOperandBytes = 0; for (unsigned i = 0, e = CFR->getNumNodes(); i != e; ++i) NumOperandBytes += EmitVBRValue(CFR->getNode(i), OS); @@ -452,15 +597,18 @@ EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) NumResultBytes += EmitVBRValue(CM->getResult(i), OS); OS << '\n'; - OS.PadToColumn(Indent*2) << "// Src: " - << *CM->getPattern().getSrcPattern() << '\n'; - OS.PadToColumn(Indent*2) << "// Dst: " - << *CM->getPattern().getDstPattern() << '\n'; + if (!OmitComments) { + OS.PadToColumn(Indent*2) << "// Src: " + << *CM->getPattern().getSrcPattern() << " - Complexity = " + << CM->getPattern().getPatternComplexity(CGP) << '\n'; + OS.PadToColumn(Indent*2) << "// Dst: " + << *CM->getPattern().getDstPattern(); + } + OS << '\n'; return 2 + NumResultBytes; } } - assert(0 && "Unreachable"); - return 0; + llvm_unreachable("Unreachable"); } /// EmitMatcherList - Emit the bytes for the specified matcher subtree. @@ -469,15 +617,12 @@ EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx, formatted_raw_ostream &OS) { unsigned Size = 0; while (N) { - if (unsigned(N->getKind()) >= Histogram.size()) - Histogram.resize(N->getKind()+1); - Histogram[N->getKind()]++; - - OS << "/*" << CurrentIdx << "*/"; + if (!OmitComments) + OS << "/*" << CurrentIdx << "*/"; unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS); Size += MatcherSize; CurrentIdx += MatcherSize; - + // If there are other nodes in this list, iterate to them, otherwise we're // done. N = N->getNext(); @@ -486,91 +631,166 @@ EmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx, } void MatcherTableEmitter::EmitPredicateFunctions(formatted_raw_ostream &OS) { - // FIXME: Don't build off the DAGISelEmitter's predicates, emit them directly - // here into the case stmts. - // Emit pattern predicates. - OS << "bool CheckPatternPredicate(unsigned PredNo) const {\n"; - OS << " switch (PredNo) {\n"; - OS << " default: assert(0 && \"Invalid predicate in table?\");\n"; - for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i) - OS << " case " << i << ": return " << PatternPredicates[i] << ";\n"; - OS << " }\n"; - OS << "}\n\n"; + if (!PatternPredicates.empty()) { + OS << "bool CheckPatternPredicate(unsigned PredNo) const override {\n"; + OS << " switch (PredNo) {\n"; + OS << " default: llvm_unreachable(\"Invalid predicate in table?\");\n"; + for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i) + OS << " case " << i << ": return " << PatternPredicates[i] << ";\n"; + OS << " }\n"; + OS << "}\n\n"; + } // Emit Node predicates. - OS << "bool CheckNodePredicate(SDNode *N, unsigned PredNo) const {\n"; - OS << " switch (PredNo) {\n"; - OS << " default: assert(0 && \"Invalid predicate in table?\");\n"; - for (unsigned i = 0, e = NodePredicates.size(); i != e; ++i) - OS << " case " << i << ": return " << NodePredicates[i] << "(N);\n"; - OS << " }\n"; - OS << "}\n\n"; - + if (!NodePredicates.empty()) { + OS << "bool CheckNodePredicate(SDNode *Node,\n"; + OS << " unsigned PredNo) const override {\n"; + OS << " switch (PredNo) {\n"; + OS << " default: llvm_unreachable(\"Invalid predicate in table?\");\n"; + for (unsigned i = 0, e = NodePredicates.size(); i != e; ++i) { + // Emit the predicate code corresponding to this pattern. + TreePredicateFn PredFn = NodePredicates[i]; + + assert(!PredFn.isAlwaysTrue() && "No code in this predicate"); + OS << " case " << i << ": { \n"; + for (auto *SimilarPred : + NodePredicatesByCodeToRun[PredFn.getCodeToRunOnSDNode()]) + OS << " // " << TreePredicateFn(SimilarPred).getFnName() <<'\n'; + + OS << PredFn.getCodeToRunOnSDNode() << "\n }\n"; + } + OS << " }\n"; + OS << "}\n\n"; + } + // Emit CompletePattern matchers. // FIXME: This should be const. - OS << "bool CheckComplexPattern(SDNode *Root, SDValue N,\n"; - OS << " unsigned PatternNo, SmallVectorImpl &Result) {\n"; - OS << " switch (PatternNo) {\n"; - OS << " default: assert(0 && \"Invalid pattern # in table?\");\n"; - for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) { - const ComplexPattern &P = *ComplexPatterns[i]; - unsigned NumOps = P.getNumOperands(); - - if (P.hasProperty(SDNPHasChain)) - ++NumOps; // Get the chained node too. - - OS << " case " << i << ":\n"; - OS << " Result.resize(Result.size()+" << NumOps << ");\n"; - OS << " return " << P.getSelectFunc(); - - // FIXME: Temporary hack until old isel dies. - if (P.hasProperty(SDNPHasChain)) - OS << "XXX"; - - OS << "(Root, N"; - for (unsigned i = 0; i != NumOps; ++i) - OS << ", Result[Result.size()-" << (NumOps-i) << ']'; - OS << ");\n"; - } - OS << " }\n"; - OS << "}\n\n"; - + if (!ComplexPatterns.empty()) { + OS << "bool CheckComplexPattern(SDNode *Root, SDNode *Parent,\n"; + OS << " SDValue N, unsigned PatternNo,\n"; + OS << " SmallVectorImpl > &Result) override {\n"; + OS << " unsigned NextRes = Result.size();\n"; + OS << " switch (PatternNo) {\n"; + OS << " default: llvm_unreachable(\"Invalid pattern # in table?\");\n"; + for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) { + const ComplexPattern &P = *ComplexPatterns[i]; + unsigned NumOps = P.getNumOperands(); + + if (P.hasProperty(SDNPHasChain)) + ++NumOps; // Get the chained node too. + + OS << " case " << i << ":\n"; + OS << " Result.resize(NextRes+" << NumOps << ");\n"; + OS << " return " << P.getSelectFunc(); + + OS << "("; + // If the complex pattern wants the root of the match, pass it in as the + // first argument. + if (P.hasProperty(SDNPWantRoot)) + OS << "Root, "; + + // If the complex pattern wants the parent of the operand being matched, + // pass it in as the next argument. + if (P.hasProperty(SDNPWantParent)) + OS << "Parent, "; + + OS << "N"; + for (unsigned i = 0; i != NumOps; ++i) + OS << ", Result[NextRes+" << i << "].first"; + OS << ");\n"; + } + OS << " }\n"; + OS << "}\n\n"; + } + + // Emit SDNodeXForm handlers. // FIXME: This should be const. - OS << "SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) {\n"; - OS << " switch (XFormNo) {\n"; - OS << " default: assert(0 && \"Invalid xform # in table?\");\n"; - - // FIXME: The node xform could take SDValue's instead of SDNode*'s. - for (unsigned i = 0, e = NodeXForms.size(); i != e; ++i) - OS << " case " << i << ": return Transform_" << NodeXForms[i]->getName() - << "(V.getNode());\n"; - OS << " }\n"; - OS << "}\n\n"; + if (!NodeXForms.empty()) { + OS << "SDValue RunSDNodeXForm(SDValue V, unsigned XFormNo) override {\n"; + OS << " switch (XFormNo) {\n"; + OS << " default: llvm_unreachable(\"Invalid xform # in table?\");\n"; + + // FIXME: The node xform could take SDValue's instead of SDNode*'s. + for (unsigned i = 0, e = NodeXForms.size(); i != e; ++i) { + const CodeGenDAGPatterns::NodeXForm &Entry = + CGP.getSDNodeTransform(NodeXForms[i]); + + Record *SDNode = Entry.first; + const std::string &Code = Entry.second; + + OS << " case " << i << ": { "; + if (!OmitComments) + OS << "// " << NodeXForms[i]->getName(); + OS << '\n'; + + std::string ClassName = CGP.getSDNodeInfo(SDNode).getSDClassName(); + if (ClassName == "SDNode") + OS << " SDNode *N = V.getNode();\n"; + else + OS << " " << ClassName << " *N = cast<" << ClassName + << ">(V.getNode());\n"; + OS << Code << "\n }\n"; + } + OS << " }\n"; + OS << "}\n\n"; + } +} + +static void BuildHistogram(const Matcher *M, std::vector &OpcodeFreq){ + for (; M != nullptr; M = M->getNext()) { + // Count this node. + if (unsigned(M->getKind()) >= OpcodeFreq.size()) + OpcodeFreq.resize(M->getKind()+1); + OpcodeFreq[M->getKind()]++; + + // Handle recursive nodes. + if (const ScopeMatcher *SM = dyn_cast(M)) { + for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) + BuildHistogram(SM->getChild(i), OpcodeFreq); + } else if (const SwitchOpcodeMatcher *SOM = + dyn_cast(M)) { + for (unsigned i = 0, e = SOM->getNumCases(); i != e; ++i) + BuildHistogram(SOM->getCaseMatcher(i), OpcodeFreq); + } else if (const SwitchTypeMatcher *STM = dyn_cast(M)) { + for (unsigned i = 0, e = STM->getNumCases(); i != e; ++i) + BuildHistogram(STM->getCaseMatcher(i), OpcodeFreq); + } + } } -void MatcherTableEmitter::EmitHistogram(formatted_raw_ostream &OS) { +void MatcherTableEmitter::EmitHistogram(const Matcher *M, + formatted_raw_ostream &OS) { + if (OmitComments) + return; + + std::vector OpcodeFreq; + BuildHistogram(M, OpcodeFreq); + OS << " // Opcode Histogram:\n"; - for (unsigned i = 0, e = Histogram.size(); i != e; ++i) { + for (unsigned i = 0, e = OpcodeFreq.size(); i != e; ++i) { OS << " // #"; switch ((Matcher::KindTy)i) { - case Matcher::Scope: OS << "OPC_Scope"; break; - case Matcher::RecordNode: OS << "OPC_RecordNode"; break; + case Matcher::Scope: OS << "OPC_Scope"; break; + case Matcher::RecordNode: OS << "OPC_RecordNode"; break; case Matcher::RecordChild: OS << "OPC_RecordChild"; break; case Matcher::RecordMemRef: OS << "OPC_RecordMemRef"; break; - case Matcher::CaptureFlagInput: OS << "OPC_CaptureFlagInput"; break; + case Matcher::CaptureGlueInput: OS << "OPC_CaptureGlueInput"; break; case Matcher::MoveChild: OS << "OPC_MoveChild"; break; case Matcher::MoveParent: OS << "OPC_MoveParent"; break; case Matcher::CheckSame: OS << "OPC_CheckSame"; break; + case Matcher::CheckChildSame: OS << "OPC_CheckChildSame"; break; case Matcher::CheckPatternPredicate: OS << "OPC_CheckPatternPredicate"; break; case Matcher::CheckPredicate: OS << "OPC_CheckPredicate"; break; case Matcher::CheckOpcode: OS << "OPC_CheckOpcode"; break; - case Matcher::CheckMultiOpcode: OS << "OPC_CheckMultiOpcode"; break; + case Matcher::SwitchOpcode: OS << "OPC_SwitchOpcode"; break; case Matcher::CheckType: OS << "OPC_CheckType"; break; + case Matcher::SwitchType: OS << "OPC_SwitchType"; break; case Matcher::CheckChildType: OS << "OPC_CheckChildType"; break; case Matcher::CheckInteger: OS << "OPC_CheckInteger"; break; + case Matcher::CheckChildInteger: OS << "OPC_CheckChildInteger"; break; case Matcher::CheckCondCode: OS << "OPC_CheckCondCode"; break; case Matcher::CheckValueType: OS << "OPC_CheckValueType"; break; case Matcher::CheckComplexPat: OS << "OPC_CheckComplexPat"; break; @@ -578,7 +798,6 @@ void MatcherTableEmitter::EmitHistogram(formatted_raw_ostream &OS) { case Matcher::CheckOrImm: OS << "OPC_CheckOrImm"; break; case Matcher::CheckFoldableChainNode: OS << "OPC_CheckFoldableChainNode"; break; - case Matcher::CheckChainCompatible: OS << "OPC_CheckChainCompatible"; break; case Matcher::EmitInteger: OS << "OPC_EmitInteger"; break; case Matcher::EmitStringInteger: OS << "OPC_EmitStringInteger"; break; case Matcher::EmitRegister: OS << "OPC_EmitRegister"; break; @@ -588,36 +807,39 @@ void MatcherTableEmitter::EmitHistogram(formatted_raw_ostream &OS) { case Matcher::EmitNode: OS << "OPC_EmitNode"; break; case Matcher::MorphNodeTo: OS << "OPC_MorphNodeTo"; break; case Matcher::EmitNodeXForm: OS << "OPC_EmitNodeXForm"; break; - case Matcher::MarkFlagResults: OS << "OPC_MarkFlagResults"; break; - case Matcher::CompleteMatch: OS << "OPC_CompleteMatch"; break; + case Matcher::MarkGlueResults: OS << "OPC_MarkGlueResults"; break; + case Matcher::CompleteMatch: OS << "OPC_CompleteMatch"; break; } - - OS.PadToColumn(40) << " = " << Histogram[i] << '\n'; + + OS.PadToColumn(40) << " = " << OpcodeFreq[i] << '\n'; } OS << '\n'; } -void llvm::EmitMatcherTable(const Matcher *TheMatcher, raw_ostream &O) { +void llvm::EmitMatcherTable(const Matcher *TheMatcher, + const CodeGenDAGPatterns &CGP, + raw_ostream &O) { formatted_raw_ostream OS(O); - + OS << "// The main instruction selector code.\n"; OS << "SDNode *SelectCode(SDNode *N) {\n"; - MatcherTableEmitter MatcherEmitter; + MatcherTableEmitter MatcherEmitter(CGP); - OS << " // Opcodes are emitted as 2 bytes, TARGET_OPCODE handles this.\n"; - OS << " #define TARGET_OPCODE(X) X & 255, unsigned(X) >> 8\n"; + OS << " // Some target values are emitted as 2 bytes, TARGET_VAL handles\n"; + OS << " // this.\n"; + OS << " #define TARGET_VAL(X) X & 255, unsigned(X) >> 8\n"; OS << " static const unsigned char MatcherTable[] = {\n"; - unsigned TotalSize = MatcherEmitter.EmitMatcherList(TheMatcher, 5, 0, OS); + unsigned TotalSize = MatcherEmitter.EmitMatcherList(TheMatcher, 6, 0, OS); OS << " 0\n }; // Total Array size is " << (TotalSize+1) << " bytes\n\n"; - - MatcherEmitter.EmitHistogram(OS); - - OS << " #undef TARGET_OPCODE\n"; + + MatcherEmitter.EmitHistogram(TheMatcher, OS); + + OS << " #undef TARGET_VAL\n"; OS << " return SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n}\n"; - OS << "\n"; - + OS << '\n'; + // Next up, emit the function for node and pattern predicates: MatcherEmitter.EmitPredicateFunctions(OS); }