1203954Srdivacky//===- DAGISelMatcherEmitter.cpp - Matcher Emitter ------------------------===// 2203954Srdivacky// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6203954Srdivacky// 7203954Srdivacky//===----------------------------------------------------------------------===// 8203954Srdivacky// 9212904Sdim// This file contains code to generate C++ code for a matcher. 10203954Srdivacky// 11203954Srdivacky//===----------------------------------------------------------------------===// 12203954Srdivacky 13321369Sdim#include "CodeGenDAGPatterns.h" 14203954Srdivacky#include "DAGISelMatcher.h" 15204642Srdivacky#include "llvm/ADT/DenseMap.h" 16321369Sdim#include "llvm/ADT/StringMap.h" 17321369Sdim#include "llvm/ADT/MapVector.h" 18203954Srdivacky#include "llvm/ADT/SmallString.h" 19203954Srdivacky#include "llvm/ADT/StringMap.h" 20296417Sdim#include "llvm/ADT/TinyPtrVector.h" 21204642Srdivacky#include "llvm/Support/CommandLine.h" 22327952Sdim#include "llvm/Support/Format.h" 23321369Sdim#include "llvm/Support/SourceMgr.h" 24321369Sdim#include "llvm/TableGen/Error.h" 25249423Sdim#include "llvm/TableGen/Record.h" 26203954Srdivackyusing namespace llvm; 27203954Srdivacky 28203954Srdivackyenum { 29327952Sdim IndexWidth = 6, 30327952Sdim FullIndexWidth = IndexWidth + 4, 31327952Sdim HistOpcWidth = 40, 32203954Srdivacky}; 33203954Srdivacky 34321369Sdimcl::OptionCategory DAGISelCat("Options for -gen-dag-isel"); 35321369Sdim 36204642Srdivacky// To reduce generated source code size. 37321369Sdimstatic cl::opt<bool> OmitComments("omit-comments", 38321369Sdim cl::desc("Do not generate comments"), 39321369Sdim cl::init(false), cl::cat(DAGISelCat)); 40203954Srdivacky 41321369Sdimstatic cl::opt<bool> InstrumentCoverage( 42321369Sdim "instrument-coverage", 43321369Sdim cl::desc("Generates tables to help identify patterns matched"), 44321369Sdim cl::init(false), cl::cat(DAGISelCat)); 45321369Sdim 46203954Srdivackynamespace { 47203954Srdivackyclass MatcherTableEmitter { 48206083Srdivacky const CodeGenDAGPatterns &CGP; 49327952Sdim 50221345Sdim DenseMap<TreePattern *, unsigned> NodePredicateMap; 51221345Sdim std::vector<TreePredicateFn> NodePredicates; 52344779Sdim std::vector<TreePredicateFn> NodePredicatesWithOperands; 53296417Sdim 54296417Sdim // We de-duplicate the predicates by code string, and use this map to track 55296417Sdim // all the patterns with "identical" predicates. 56296417Sdim StringMap<TinyPtrVector<TreePattern *>> NodePredicatesByCodeToRun; 57327952Sdim 58221345Sdim StringMap<unsigned> PatternPredicateMap; 59221345Sdim std::vector<std::string> PatternPredicates; 60204642Srdivacky 61204642Srdivacky DenseMap<const ComplexPattern*, unsigned> ComplexPatternMap; 62204642Srdivacky std::vector<const ComplexPattern*> ComplexPatterns; 63204642Srdivacky 64204642Srdivacky 65204642Srdivacky DenseMap<Record*, unsigned> NodeXFormMap; 66204642Srdivacky std::vector<Record*> NodeXForms; 67204642Srdivacky 68321369Sdim std::vector<std::string> VecIncludeStrings; 69321369Sdim MapVector<std::string, unsigned, StringMap<unsigned> > VecPatterns; 70321369Sdim 71321369Sdim unsigned getPatternIdxFromTable(std::string &&P, std::string &&include_loc) { 72321369Sdim const auto It = VecPatterns.find(P); 73321369Sdim if (It == VecPatterns.end()) { 74321369Sdim VecPatterns.insert(make_pair(std::move(P), VecPatterns.size())); 75321369Sdim VecIncludeStrings.push_back(std::move(include_loc)); 76321369Sdim return VecIncludeStrings.size() - 1; 77321369Sdim } 78321369Sdim return It->second; 79321369Sdim } 80321369Sdim 81203954Srdivackypublic: 82221345Sdim MatcherTableEmitter(const CodeGenDAGPatterns &cgp) 83221345Sdim : CGP(cgp) {} 84203954Srdivacky 85204642Srdivacky unsigned EmitMatcherList(const Matcher *N, unsigned Indent, 86327952Sdim unsigned StartIdx, raw_ostream &OS); 87221345Sdim 88327952Sdim void EmitPredicateFunctions(raw_ostream &OS); 89221345Sdim 90327952Sdim void EmitHistogram(const Matcher *N, raw_ostream &OS); 91321369Sdim 92321369Sdim void EmitPatternMatchTable(raw_ostream &OS); 93321369Sdim 94203954Srdivackyprivate: 95344779Sdim void EmitNodePredicatesFunction(const std::vector<TreePredicateFn> &Preds, 96344779Sdim StringRef Decl, raw_ostream &OS); 97344779Sdim 98204642Srdivacky unsigned EmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, 99327952Sdim raw_ostream &OS); 100221345Sdim 101221345Sdim unsigned getNodePredicate(TreePredicateFn Pred) { 102296417Sdim TreePattern *TP = Pred.getOrigPatFragRecord(); 103296417Sdim unsigned &Entry = NodePredicateMap[TP]; 104203954Srdivacky if (Entry == 0) { 105296417Sdim TinyPtrVector<TreePattern *> &SameCodePreds = 106296417Sdim NodePredicatesByCodeToRun[Pred.getCodeToRunOnSDNode()]; 107296417Sdim if (SameCodePreds.empty()) { 108296417Sdim // We've never seen a predicate with the same code: allocate an entry. 109344779Sdim if (Pred.usesOperands()) { 110344779Sdim NodePredicatesWithOperands.push_back(Pred); 111344779Sdim Entry = NodePredicatesWithOperands.size(); 112344779Sdim } else { 113344779Sdim NodePredicates.push_back(Pred); 114344779Sdim Entry = NodePredicates.size(); 115344779Sdim } 116296417Sdim } else { 117296417Sdim // We did see an identical predicate: re-use it. 118296417Sdim Entry = NodePredicateMap[SameCodePreds.front()]; 119296417Sdim assert(Entry != 0); 120344779Sdim assert(TreePredicateFn(SameCodePreds.front()).usesOperands() == 121344779Sdim Pred.usesOperands() && 122344779Sdim "PatFrags with some code must have same usesOperands setting"); 123296417Sdim } 124296417Sdim // In both cases, we've never seen this particular predicate before, so 125296417Sdim // mark it in the list of predicates sharing the same code. 126296417Sdim SameCodePreds.push_back(TP); 127203954Srdivacky } 128203954Srdivacky return Entry-1; 129203954Srdivacky } 130327952Sdim 131203954Srdivacky unsigned getPatternPredicate(StringRef PredName) { 132203954Srdivacky unsigned &Entry = PatternPredicateMap[PredName]; 133203954Srdivacky if (Entry == 0) { 134203954Srdivacky PatternPredicates.push_back(PredName.str()); 135203954Srdivacky Entry = PatternPredicates.size(); 136203954Srdivacky } 137203954Srdivacky return Entry-1; 138203954Srdivacky } 139204642Srdivacky unsigned getComplexPat(const ComplexPattern &P) { 140204642Srdivacky unsigned &Entry = ComplexPatternMap[&P]; 141204642Srdivacky if (Entry == 0) { 142204642Srdivacky ComplexPatterns.push_back(&P); 143204642Srdivacky Entry = ComplexPatterns.size(); 144204642Srdivacky } 145204642Srdivacky return Entry-1; 146204642Srdivacky } 147221345Sdim 148204642Srdivacky unsigned getNodeXFormID(Record *Rec) { 149204642Srdivacky unsigned &Entry = NodeXFormMap[Rec]; 150204642Srdivacky if (Entry == 0) { 151204642Srdivacky NodeXForms.push_back(Rec); 152204642Srdivacky Entry = NodeXForms.size(); 153204642Srdivacky } 154204642Srdivacky return Entry-1; 155204642Srdivacky } 156221345Sdim 157203954Srdivacky}; 158203954Srdivacky} // end anonymous namespace. 159203954Srdivacky 160321369Sdimstatic std::string GetPatFromTreePatternNode(const TreePatternNode *N) { 161321369Sdim std::string str; 162321369Sdim raw_string_ostream Stream(str); 163321369Sdim Stream << *N; 164321369Sdim Stream.str(); 165321369Sdim return str; 166321369Sdim} 167321369Sdim 168204642Srdivackystatic unsigned GetVBRSize(unsigned Val) { 169204642Srdivacky if (Val <= 127) return 1; 170221345Sdim 171204642Srdivacky unsigned NumBytes = 0; 172204642Srdivacky while (Val >= 128) { 173204642Srdivacky Val >>= 7; 174204642Srdivacky ++NumBytes; 175204642Srdivacky } 176204642Srdivacky return NumBytes+1; 177204642Srdivacky} 178204642Srdivacky 179204642Srdivacky/// EmitVBRValue - Emit the specified value as a VBR, returning the number of 180204642Srdivacky/// bytes emitted. 181204642Srdivackystatic uint64_t EmitVBRValue(uint64_t Val, raw_ostream &OS) { 182204642Srdivacky if (Val <= 127) { 183204642Srdivacky OS << Val << ", "; 184204642Srdivacky return 1; 185204642Srdivacky } 186221345Sdim 187204642Srdivacky uint64_t InVal = Val; 188204642Srdivacky unsigned NumBytes = 0; 189204642Srdivacky while (Val >= 128) { 190204642Srdivacky OS << (Val&127) << "|128,"; 191204642Srdivacky Val >>= 7; 192204642Srdivacky ++NumBytes; 193204642Srdivacky } 194204642Srdivacky OS << Val; 195204642Srdivacky if (!OmitComments) 196204642Srdivacky OS << "/*" << InVal << "*/"; 197204642Srdivacky OS << ", "; 198204642Srdivacky return NumBytes+1; 199204642Srdivacky} 200204642Srdivacky 201321369Sdim// This is expensive and slow. 202321369Sdimstatic std::string getIncludePath(const Record *R) { 203321369Sdim std::string str; 204321369Sdim raw_string_ostream Stream(str); 205321369Sdim auto Locs = R->getLoc(); 206321369Sdim SMLoc L; 207321369Sdim if (Locs.size() > 1) { 208321369Sdim // Get where the pattern prototype was instantiated 209321369Sdim L = Locs[1]; 210321369Sdim } else if (Locs.size() == 1) { 211321369Sdim L = Locs[0]; 212321369Sdim } 213321369Sdim unsigned CurBuf = SrcMgr.FindBufferContainingLoc(L); 214321369Sdim assert(CurBuf && "Invalid or unspecified location!"); 215321369Sdim 216321369Sdim Stream << SrcMgr.getBufferInfo(CurBuf).Buffer->getBufferIdentifier() << ":" 217321369Sdim << SrcMgr.FindLineNumber(L, CurBuf); 218321369Sdim Stream.str(); 219321369Sdim return str; 220321369Sdim} 221321369Sdim 222327952Sdimstatic void BeginEmitFunction(raw_ostream &OS, StringRef RetType, 223327952Sdim StringRef Decl, bool AddOverride) { 224327952Sdim OS << "#ifdef GET_DAGISEL_DECL\n"; 225327952Sdim OS << RetType << ' ' << Decl; 226327952Sdim if (AddOverride) 227327952Sdim OS << " override"; 228327952Sdim OS << ";\n" 229327952Sdim "#endif\n" 230327952Sdim "#if defined(GET_DAGISEL_BODY) || DAGISEL_INLINE\n"; 231327952Sdim OS << RetType << " DAGISEL_CLASS_COLONCOLON " << Decl << "\n"; 232327952Sdim if (AddOverride) { 233327952Sdim OS << "#if DAGISEL_INLINE\n" 234327952Sdim " override\n" 235327952Sdim "#endif\n"; 236327952Sdim } 237327952Sdim} 238327952Sdim 239327952Sdimstatic void EndEmitFunction(raw_ostream &OS) { 240327952Sdim OS << "#endif // GET_DAGISEL_BODY\n\n"; 241327952Sdim} 242327952Sdim 243321369Sdimvoid MatcherTableEmitter::EmitPatternMatchTable(raw_ostream &OS) { 244321369Sdim 245321369Sdim assert(isUInt<16>(VecPatterns.size()) && 246321369Sdim "Using only 16 bits to encode offset into Pattern Table"); 247321369Sdim assert(VecPatterns.size() == VecIncludeStrings.size() && 248321369Sdim "The sizes of Pattern and include vectors should be the same"); 249327952Sdim 250327952Sdim BeginEmitFunction(OS, "StringRef", "getPatternForIndex(unsigned Index)", 251327952Sdim true/*AddOverride*/); 252327952Sdim OS << "{\n"; 253321369Sdim OS << "static const char * PATTERN_MATCH_TABLE[] = {\n"; 254321369Sdim 255321369Sdim for (const auto &It : VecPatterns) { 256321369Sdim OS << "\"" << It.first << "\",\n"; 257321369Sdim } 258321369Sdim 259321369Sdim OS << "\n};"; 260321369Sdim OS << "\nreturn StringRef(PATTERN_MATCH_TABLE[Index]);"; 261353358Sdim OS << "\n}\n"; 262327952Sdim EndEmitFunction(OS); 263321369Sdim 264327952Sdim BeginEmitFunction(OS, "StringRef", "getIncludePathForIndex(unsigned Index)", 265327952Sdim true/*AddOverride*/); 266327952Sdim OS << "{\n"; 267321369Sdim OS << "static const char * INCLUDE_PATH_TABLE[] = {\n"; 268321369Sdim 269321369Sdim for (const auto &It : VecIncludeStrings) { 270321369Sdim OS << "\"" << It << "\",\n"; 271321369Sdim } 272321369Sdim 273321369Sdim OS << "\n};"; 274321369Sdim OS << "\nreturn StringRef(INCLUDE_PATH_TABLE[Index]);"; 275353358Sdim OS << "\n}\n"; 276327952Sdim EndEmitFunction(OS); 277321369Sdim} 278321369Sdim 279249423Sdim/// EmitMatcher - Emit bytes for the specified matcher and return 280203954Srdivacky/// the number of bytes emitted. 281203954Srdivackyunsigned MatcherTableEmitter:: 282204642SrdivackyEmitMatcher(const Matcher *N, unsigned Indent, unsigned CurrentIdx, 283327952Sdim raw_ostream &OS) { 284327952Sdim OS.indent(Indent*2); 285221345Sdim 286203954Srdivacky switch (N->getKind()) { 287204642Srdivacky case Matcher::Scope: { 288204642Srdivacky const ScopeMatcher *SM = cast<ScopeMatcher>(N); 289276479Sdim assert(SM->getNext() == nullptr && "Shouldn't have next after scope"); 290221345Sdim 291204642Srdivacky unsigned StartIdx = CurrentIdx; 292221345Sdim 293204642Srdivacky // Emit all of the children. 294204642Srdivacky for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) { 295204642Srdivacky if (i == 0) { 296204642Srdivacky OS << "OPC_Scope, "; 297204642Srdivacky ++CurrentIdx; 298204642Srdivacky } else { 299204642Srdivacky if (!OmitComments) { 300327952Sdim OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/"; 301327952Sdim OS.indent(Indent*2) << "/*Scope*/ "; 302204642Srdivacky } else 303327952Sdim OS.indent(Indent*2); 304204642Srdivacky } 305204642Srdivacky 306204642Srdivacky // We need to encode the child and the offset of the failure code before 307204642Srdivacky // emitting either of them. Handle this by buffering the output into a 308204642Srdivacky // string while we get the size. Unfortunately, the offset of the 309204642Srdivacky // children depends on the VBR size of the child, so for large children we 310204642Srdivacky // have to iterate a bit. 311204642Srdivacky SmallString<128> TmpBuf; 312204642Srdivacky unsigned ChildSize = 0; 313204642Srdivacky unsigned VBRSize = 0; 314204642Srdivacky do { 315204642Srdivacky VBRSize = GetVBRSize(ChildSize); 316221345Sdim 317204642Srdivacky TmpBuf.clear(); 318204642Srdivacky raw_svector_ostream OS(TmpBuf); 319204642Srdivacky ChildSize = EmitMatcherList(SM->getChild(i), Indent+1, 320327952Sdim CurrentIdx+VBRSize, OS); 321204642Srdivacky } while (GetVBRSize(ChildSize) != VBRSize); 322221345Sdim 323204642Srdivacky assert(ChildSize != 0 && "Should not have a zero-sized child!"); 324221345Sdim 325204642Srdivacky CurrentIdx += EmitVBRValue(ChildSize, OS); 326204642Srdivacky if (!OmitComments) { 327204642Srdivacky OS << "/*->" << CurrentIdx+ChildSize << "*/"; 328221345Sdim 329204642Srdivacky if (i == 0) 330327952Sdim OS << " // " << SM->getNumChildren() << " children in Scope"; 331204642Srdivacky } 332221345Sdim 333288943Sdim OS << '\n' << TmpBuf; 334204642Srdivacky CurrentIdx += ChildSize; 335204642Srdivacky } 336221345Sdim 337204642Srdivacky // Emit a zero as a sentinel indicating end of 'Scope'. 338204642Srdivacky if (!OmitComments) 339327952Sdim OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/"; 340327952Sdim OS.indent(Indent*2) << "0, "; 341204642Srdivacky if (!OmitComments) 342204642Srdivacky OS << "/*End of Scope*/"; 343204642Srdivacky OS << '\n'; 344204642Srdivacky return CurrentIdx - StartIdx + 1; 345204642Srdivacky } 346221345Sdim 347204642Srdivacky case Matcher::RecordNode: 348204642Srdivacky OS << "OPC_RecordNode,"; 349204642Srdivacky if (!OmitComments) 350327952Sdim OS << " // #" 351327952Sdim << cast<RecordMatcher>(N)->getResultNo() << " = " 352327952Sdim << cast<RecordMatcher>(N)->getWhatFor(); 353204642Srdivacky OS << '\n'; 354203954Srdivacky return 1; 355204642Srdivacky 356204642Srdivacky case Matcher::RecordChild: 357204642Srdivacky OS << "OPC_RecordChild" << cast<RecordChildMatcher>(N)->getChildNo() 358204642Srdivacky << ','; 359204642Srdivacky if (!OmitComments) 360327952Sdim OS << " // #" 361327952Sdim << cast<RecordChildMatcher>(N)->getResultNo() << " = " 362327952Sdim << cast<RecordChildMatcher>(N)->getWhatFor(); 363204642Srdivacky OS << '\n'; 364203954Srdivacky return 1; 365221345Sdim 366204642Srdivacky case Matcher::RecordMemRef: 367204642Srdivacky OS << "OPC_RecordMemRef,\n"; 368204642Srdivacky return 1; 369221345Sdim 370218893Sdim case Matcher::CaptureGlueInput: 371218893Sdim OS << "OPC_CaptureGlueInput,\n"; 372204642Srdivacky return 1; 373221345Sdim 374309124Sdim case Matcher::MoveChild: { 375309124Sdim const auto *MCM = cast<MoveChildMatcher>(N); 376221345Sdim 377309124Sdim OS << "OPC_MoveChild"; 378309124Sdim // Handle the specialized forms. 379309124Sdim if (MCM->getChildNo() >= 8) 380309124Sdim OS << ", "; 381309124Sdim OS << MCM->getChildNo() << ",\n"; 382309124Sdim return (MCM->getChildNo() >= 8) ? 2 : 1; 383309124Sdim } 384309124Sdim 385204642Srdivacky case Matcher::MoveParent: 386203954Srdivacky OS << "OPC_MoveParent,\n"; 387203954Srdivacky return 1; 388221345Sdim 389204642Srdivacky case Matcher::CheckSame: 390203954Srdivacky OS << "OPC_CheckSame, " 391204642Srdivacky << cast<CheckSameMatcher>(N)->getMatchNumber() << ",\n"; 392203954Srdivacky return 2; 393203954Srdivacky 394261991Sdim case Matcher::CheckChildSame: 395261991Sdim OS << "OPC_CheckChild" 396261991Sdim << cast<CheckChildSameMatcher>(N)->getChildNo() << "Same, " 397261991Sdim << cast<CheckChildSameMatcher>(N)->getMatchNumber() << ",\n"; 398261991Sdim return 2; 399261991Sdim 400204642Srdivacky case Matcher::CheckPatternPredicate: { 401221345Sdim StringRef Pred =cast<CheckPatternPredicateMatcher>(N)->getPredicate(); 402203954Srdivacky OS << "OPC_CheckPatternPredicate, " << getPatternPredicate(Pred) << ','; 403204642Srdivacky if (!OmitComments) 404327952Sdim OS << " // " << Pred; 405204642Srdivacky OS << '\n'; 406203954Srdivacky return 2; 407203954Srdivacky } 408204642Srdivacky case Matcher::CheckPredicate: { 409221345Sdim TreePredicateFn Pred = cast<CheckPredicateMatcher>(N)->getPredicate(); 410344779Sdim unsigned OperandBytes = 0; 411344779Sdim 412344779Sdim if (Pred.usesOperands()) { 413344779Sdim unsigned NumOps = cast<CheckPredicateMatcher>(N)->getNumOperands(); 414344779Sdim OS << "OPC_CheckPredicateWithOperands, " << NumOps << "/*#Ops*/, "; 415344779Sdim for (unsigned i = 0; i < NumOps; ++i) 416344779Sdim OS << cast<CheckPredicateMatcher>(N)->getOperandNo(i) << ", "; 417344779Sdim OperandBytes = 1 + NumOps; 418344779Sdim } else { 419344779Sdim OS << "OPC_CheckPredicate, "; 420344779Sdim } 421344779Sdim 422344779Sdim OS << getNodePredicate(Pred) << ','; 423204642Srdivacky if (!OmitComments) 424327952Sdim OS << " // " << Pred.getFnName(); 425204642Srdivacky OS << '\n'; 426344779Sdim return 2 + OperandBytes; 427203954Srdivacky } 428203954Srdivacky 429204642Srdivacky case Matcher::CheckOpcode: 430221345Sdim OS << "OPC_CheckOpcode, TARGET_VAL(" 431206083Srdivacky << cast<CheckOpcodeMatcher>(N)->getOpcode().getEnumName() << "),\n"; 432206083Srdivacky return 3; 433221345Sdim 434204642Srdivacky case Matcher::SwitchOpcode: 435204642Srdivacky case Matcher::SwitchType: { 436204642Srdivacky unsigned StartIdx = CurrentIdx; 437221345Sdim 438204642Srdivacky unsigned NumCases; 439204642Srdivacky if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) { 440204642Srdivacky OS << "OPC_SwitchOpcode "; 441204642Srdivacky NumCases = SOM->getNumCases(); 442204642Srdivacky } else { 443204642Srdivacky OS << "OPC_SwitchType "; 444204642Srdivacky NumCases = cast<SwitchTypeMatcher>(N)->getNumCases(); 445204642Srdivacky } 446204642Srdivacky 447204642Srdivacky if (!OmitComments) 448204642Srdivacky OS << "/*" << NumCases << " cases */"; 449204642Srdivacky OS << ", "; 450204642Srdivacky ++CurrentIdx; 451221345Sdim 452204642Srdivacky // For each case we emit the size, then the opcode, then the matcher. 453204642Srdivacky for (unsigned i = 0, e = NumCases; i != e; ++i) { 454204642Srdivacky const Matcher *Child; 455206083Srdivacky unsigned IdxSize; 456206083Srdivacky if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) { 457204642Srdivacky Child = SOM->getCaseMatcher(i); 458206083Srdivacky IdxSize = 2; // size of opcode in table is 2 bytes. 459206083Srdivacky } else { 460204642Srdivacky Child = cast<SwitchTypeMatcher>(N)->getCaseMatcher(i); 461206083Srdivacky IdxSize = 1; // size of type in table is 1 byte. 462206083Srdivacky } 463221345Sdim 464204642Srdivacky // We need to encode the opcode and the offset of the case code before 465204642Srdivacky // emitting the case code. Handle this by buffering the output into a 466204642Srdivacky // string while we get the size. Unfortunately, the offset of the 467204642Srdivacky // children depends on the VBR size of the child, so for large children we 468204642Srdivacky // have to iterate a bit. 469204642Srdivacky SmallString<128> TmpBuf; 470204642Srdivacky unsigned ChildSize = 0; 471204642Srdivacky unsigned VBRSize = 0; 472204642Srdivacky do { 473204642Srdivacky VBRSize = GetVBRSize(ChildSize); 474221345Sdim 475204642Srdivacky TmpBuf.clear(); 476204642Srdivacky raw_svector_ostream OS(TmpBuf); 477206083Srdivacky ChildSize = EmitMatcherList(Child, Indent+1, CurrentIdx+VBRSize+IdxSize, 478327952Sdim OS); 479204642Srdivacky } while (GetVBRSize(ChildSize) != VBRSize); 480221345Sdim 481204642Srdivacky assert(ChildSize != 0 && "Should not have a zero-sized child!"); 482221345Sdim 483204642Srdivacky if (i != 0) { 484261991Sdim if (!OmitComments) 485327952Sdim OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/"; 486327952Sdim OS.indent(Indent*2); 487204642Srdivacky if (!OmitComments) 488261991Sdim OS << (isa<SwitchOpcodeMatcher>(N) ? 489261991Sdim "/*SwitchOpcode*/ " : "/*SwitchType*/ "); 490204642Srdivacky } 491221345Sdim 492204642Srdivacky // Emit the VBR. 493204642Srdivacky CurrentIdx += EmitVBRValue(ChildSize, OS); 494221345Sdim 495204642Srdivacky if (const SwitchOpcodeMatcher *SOM = dyn_cast<SwitchOpcodeMatcher>(N)) 496221345Sdim OS << "TARGET_VAL(" << SOM->getCaseOpcode(i).getEnumName() << "),"; 497204642Srdivacky else 498206083Srdivacky OS << getEnumName(cast<SwitchTypeMatcher>(N)->getCaseType(i)) << ','; 499206083Srdivacky 500206083Srdivacky CurrentIdx += IdxSize; 501206083Srdivacky 502204642Srdivacky if (!OmitComments) 503206083Srdivacky OS << "// ->" << CurrentIdx+ChildSize; 504204642Srdivacky OS << '\n'; 505288943Sdim OS << TmpBuf; 506204642Srdivacky CurrentIdx += ChildSize; 507204642Srdivacky } 508204642Srdivacky 509204642Srdivacky // Emit the final zero to terminate the switch. 510261991Sdim if (!OmitComments) 511327952Sdim OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/"; 512327952Sdim OS.indent(Indent*2) << "0,"; 513204642Srdivacky if (!OmitComments) 514204642Srdivacky OS << (isa<SwitchOpcodeMatcher>(N) ? 515327952Sdim " // EndSwitchOpcode" : " // EndSwitchType"); 516204642Srdivacky 517204642Srdivacky OS << '\n'; 518204642Srdivacky ++CurrentIdx; 519204642Srdivacky return CurrentIdx-StartIdx; 520204642Srdivacky } 521204642Srdivacky 522204642Srdivacky case Matcher::CheckType: 523327952Sdim if (cast<CheckTypeMatcher>(N)->getResNo() == 0) { 524327952Sdim OS << "OPC_CheckType, " 525327952Sdim << getEnumName(cast<CheckTypeMatcher>(N)->getType()) << ",\n"; 526327952Sdim return 2; 527327952Sdim } 528327952Sdim OS << "OPC_CheckTypeRes, " << cast<CheckTypeMatcher>(N)->getResNo() 529327952Sdim << ", " << getEnumName(cast<CheckTypeMatcher>(N)->getType()) << ",\n"; 530327952Sdim return 3; 531221345Sdim 532204642Srdivacky case Matcher::CheckChildType: 533204642Srdivacky OS << "OPC_CheckChild" 534204642Srdivacky << cast<CheckChildTypeMatcher>(N)->getChildNo() << "Type, " 535204642Srdivacky << getEnumName(cast<CheckChildTypeMatcher>(N)->getType()) << ",\n"; 536204642Srdivacky return 2; 537221345Sdim 538204642Srdivacky case Matcher::CheckInteger: { 539204642Srdivacky OS << "OPC_CheckInteger, "; 540204642Srdivacky unsigned Bytes=1+EmitVBRValue(cast<CheckIntegerMatcher>(N)->getValue(), OS); 541204642Srdivacky OS << '\n'; 542204642Srdivacky return Bytes; 543204642Srdivacky } 544276479Sdim case Matcher::CheckChildInteger: { 545276479Sdim OS << "OPC_CheckChild" << cast<CheckChildIntegerMatcher>(N)->getChildNo() 546276479Sdim << "Integer, "; 547276479Sdim unsigned Bytes=1+EmitVBRValue(cast<CheckChildIntegerMatcher>(N)->getValue(), 548276479Sdim OS); 549276479Sdim OS << '\n'; 550276479Sdim return Bytes; 551276479Sdim } 552204642Srdivacky case Matcher::CheckCondCode: 553203954Srdivacky OS << "OPC_CheckCondCode, ISD::" 554204642Srdivacky << cast<CheckCondCodeMatcher>(N)->getCondCodeName() << ",\n"; 555203954Srdivacky return 2; 556221345Sdim 557353358Sdim case Matcher::CheckChild2CondCode: 558353358Sdim OS << "OPC_CheckChild2CondCode, ISD::" 559353358Sdim << cast<CheckChild2CondCodeMatcher>(N)->getCondCodeName() << ",\n"; 560353358Sdim return 2; 561353358Sdim 562204642Srdivacky case Matcher::CheckValueType: 563203954Srdivacky OS << "OPC_CheckValueType, MVT::" 564204642Srdivacky << cast<CheckValueTypeMatcher>(N)->getTypeName() << ",\n"; 565203954Srdivacky return 2; 566203954Srdivacky 567204642Srdivacky case Matcher::CheckComplexPat: { 568204792Srdivacky const CheckComplexPatMatcher *CCPM = cast<CheckComplexPatMatcher>(N); 569204792Srdivacky const ComplexPattern &Pattern = CCPM->getPattern(); 570204792Srdivacky OS << "OPC_CheckComplexPat, /*CP*/" << getComplexPat(Pattern) << ", /*#*/" 571204792Srdivacky << CCPM->getMatchNumber() << ','; 572221345Sdim 573204642Srdivacky if (!OmitComments) { 574327952Sdim OS << " // " << Pattern.getSelectFunc(); 575204792Srdivacky OS << ":$" << CCPM->getName(); 576204792Srdivacky for (unsigned i = 0, e = Pattern.getNumOperands(); i != e; ++i) 577204792Srdivacky OS << " #" << CCPM->getFirstResult()+i; 578221345Sdim 579204642Srdivacky if (Pattern.hasProperty(SDNPHasChain)) 580204792Srdivacky OS << " + chain result"; 581204642Srdivacky } 582204642Srdivacky OS << '\n'; 583204792Srdivacky return 3; 584204642Srdivacky } 585221345Sdim 586204642Srdivacky case Matcher::CheckAndImm: { 587204642Srdivacky OS << "OPC_CheckAndImm, "; 588204642Srdivacky unsigned Bytes=1+EmitVBRValue(cast<CheckAndImmMatcher>(N)->getValue(), OS); 589204642Srdivacky OS << '\n'; 590204642Srdivacky return Bytes; 591203954Srdivacky } 592203954Srdivacky 593204642Srdivacky case Matcher::CheckOrImm: { 594204642Srdivacky OS << "OPC_CheckOrImm, "; 595204642Srdivacky unsigned Bytes = 1+EmitVBRValue(cast<CheckOrImmMatcher>(N)->getValue(), OS); 596204642Srdivacky OS << '\n'; 597204642Srdivacky return Bytes; 598203954Srdivacky } 599221345Sdim 600204642Srdivacky case Matcher::CheckFoldableChainNode: 601204642Srdivacky OS << "OPC_CheckFoldableChainNode,\n"; 602203954Srdivacky return 1; 603221345Sdim 604353358Sdim case Matcher::CheckImmAllOnesV: 605353358Sdim OS << "OPC_CheckImmAllOnesV,\n"; 606353358Sdim return 1; 607353358Sdim 608353358Sdim case Matcher::CheckImmAllZerosV: 609353358Sdim OS << "OPC_CheckImmAllZerosV,\n"; 610353358Sdim return 1; 611353358Sdim 612204642Srdivacky case Matcher::EmitInteger: { 613204642Srdivacky int64_t Val = cast<EmitIntegerMatcher>(N)->getValue(); 614204642Srdivacky OS << "OPC_EmitInteger, " 615204642Srdivacky << getEnumName(cast<EmitIntegerMatcher>(N)->getVT()) << ", "; 616204642Srdivacky unsigned Bytes = 2+EmitVBRValue(Val, OS); 617204642Srdivacky OS << '\n'; 618204642Srdivacky return Bytes; 619203954Srdivacky } 620204642Srdivacky case Matcher::EmitStringInteger: { 621204642Srdivacky const std::string &Val = cast<EmitStringIntegerMatcher>(N)->getValue(); 622204642Srdivacky // These should always fit into one byte. 623204642Srdivacky OS << "OPC_EmitInteger, " 624204642Srdivacky << getEnumName(cast<EmitStringIntegerMatcher>(N)->getVT()) << ", " 625204642Srdivacky << Val << ",\n"; 626204642Srdivacky return 3; 627204642Srdivacky } 628221345Sdim 629221345Sdim case Matcher::EmitRegister: { 630221345Sdim const EmitRegisterMatcher *Matcher = cast<EmitRegisterMatcher>(N); 631221345Sdim const CodeGenRegister *Reg = Matcher->getReg(); 632221345Sdim // If the enum value of the register is larger than one byte can handle, 633221345Sdim // use EmitRegister2. 634221345Sdim if (Reg && Reg->EnumValue > 255) { 635221345Sdim OS << "OPC_EmitRegister2, " << getEnumName(Matcher->getVT()) << ", "; 636221345Sdim OS << "TARGET_VAL(" << getQualifiedName(Reg->TheDef) << "),\n"; 637221345Sdim return 4; 638221345Sdim } else { 639221345Sdim OS << "OPC_EmitRegister, " << getEnumName(Matcher->getVT()) << ", "; 640221345Sdim if (Reg) { 641221345Sdim OS << getQualifiedName(Reg->TheDef) << ",\n"; 642221345Sdim } else { 643221345Sdim OS << "0 "; 644221345Sdim if (!OmitComments) 645221345Sdim OS << "/*zero_reg*/"; 646221345Sdim OS << ",\n"; 647221345Sdim } 648221345Sdim return 3; 649204642Srdivacky } 650221345Sdim } 651221345Sdim 652204642Srdivacky case Matcher::EmitConvertToTarget: 653204642Srdivacky OS << "OPC_EmitConvertToTarget, " 654204642Srdivacky << cast<EmitConvertToTargetMatcher>(N)->getSlot() << ",\n"; 655204642Srdivacky return 2; 656221345Sdim 657204642Srdivacky case Matcher::EmitMergeInputChains: { 658204642Srdivacky const EmitMergeInputChainsMatcher *MN = 659204642Srdivacky cast<EmitMergeInputChainsMatcher>(N); 660221345Sdim 661309124Sdim // Handle the specialized forms OPC_EmitMergeInputChains1_0, 1_1, and 1_2. 662309124Sdim if (MN->getNumNodes() == 1 && MN->getNode(0) < 3) { 663206083Srdivacky OS << "OPC_EmitMergeInputChains1_" << MN->getNode(0) << ",\n"; 664206083Srdivacky return 1; 665206083Srdivacky } 666221345Sdim 667204642Srdivacky OS << "OPC_EmitMergeInputChains, " << MN->getNumNodes() << ", "; 668204642Srdivacky for (unsigned i = 0, e = MN->getNumNodes(); i != e; ++i) 669204642Srdivacky OS << MN->getNode(i) << ", "; 670204642Srdivacky OS << '\n'; 671204642Srdivacky return 2+MN->getNumNodes(); 672204642Srdivacky } 673360784Sdim case Matcher::EmitCopyToReg: { 674360784Sdim const auto *C2RMatcher = cast<EmitCopyToRegMatcher>(N); 675360784Sdim int Bytes = 3; 676360784Sdim const CodeGenRegister *Reg = C2RMatcher->getDestPhysReg(); 677360784Sdim if (Reg->EnumValue > 255) { 678360784Sdim assert(isUInt<16>(Reg->EnumValue) && "not handled"); 679360784Sdim OS << "OPC_EmitCopyToReg2, " << C2RMatcher->getSrcSlot() << ", " 680360784Sdim << "TARGET_VAL(" << getQualifiedName(Reg->TheDef) << "),\n"; 681360784Sdim ++Bytes; 682360784Sdim } else { 683360784Sdim OS << "OPC_EmitCopyToReg, " << C2RMatcher->getSrcSlot() << ", " 684360784Sdim << getQualifiedName(Reg->TheDef) << ",\n"; 685360784Sdim } 686360784Sdim 687360784Sdim return Bytes; 688360784Sdim } 689204642Srdivacky case Matcher::EmitNodeXForm: { 690204642Srdivacky const EmitNodeXFormMatcher *XF = cast<EmitNodeXFormMatcher>(N); 691204642Srdivacky OS << "OPC_EmitNodeXForm, " << getNodeXFormID(XF->getNodeXForm()) << ", " 692204642Srdivacky << XF->getSlot() << ','; 693204642Srdivacky if (!OmitComments) 694327952Sdim OS << " // "<<XF->getNodeXForm()->getName(); 695204642Srdivacky OS <<'\n'; 696204642Srdivacky return 3; 697204642Srdivacky } 698221345Sdim 699204642Srdivacky case Matcher::EmitNode: 700204642Srdivacky case Matcher::MorphNodeTo: { 701321369Sdim auto NumCoveredBytes = 0; 702321369Sdim if (InstrumentCoverage) { 703321369Sdim if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) { 704321369Sdim NumCoveredBytes = 3; 705321369Sdim OS << "OPC_Coverage, "; 706321369Sdim std::string src = 707321369Sdim GetPatFromTreePatternNode(SNT->getPattern().getSrcPattern()); 708321369Sdim std::string dst = 709321369Sdim GetPatFromTreePatternNode(SNT->getPattern().getDstPattern()); 710321369Sdim Record *PatRecord = SNT->getPattern().getSrcRecord(); 711321369Sdim std::string include_src = getIncludePath(PatRecord); 712321369Sdim unsigned Offset = 713321369Sdim getPatternIdxFromTable(src + " -> " + dst, std::move(include_src)); 714321369Sdim OS << "TARGET_VAL(" << Offset << "),\n"; 715327952Sdim OS.indent(FullIndexWidth + Indent * 2); 716321369Sdim } 717321369Sdim } 718204642Srdivacky const EmitNodeMatcherCommon *EN = cast<EmitNodeMatcherCommon>(N); 719204642Srdivacky OS << (isa<EmitNodeMatcher>(EN) ? "OPC_EmitNode" : "OPC_MorphNodeTo"); 720309124Sdim bool CompressVTs = EN->getNumVTs() < 3; 721309124Sdim if (CompressVTs) 722309124Sdim OS << EN->getNumVTs(); 723309124Sdim 724221345Sdim OS << ", TARGET_VAL(" << EN->getOpcodeName() << "), 0"; 725221345Sdim 726204642Srdivacky if (EN->hasChain()) OS << "|OPFL_Chain"; 727218893Sdim if (EN->hasInFlag()) OS << "|OPFL_GlueInput"; 728218893Sdim if (EN->hasOutFlag()) OS << "|OPFL_GlueOutput"; 729204642Srdivacky if (EN->hasMemRefs()) OS << "|OPFL_MemRefs"; 730204642Srdivacky if (EN->getNumFixedArityOperands() != -1) 731204642Srdivacky OS << "|OPFL_Variadic" << EN->getNumFixedArityOperands(); 732204642Srdivacky OS << ",\n"; 733221345Sdim 734327952Sdim OS.indent(FullIndexWidth + Indent*2+4); 735309124Sdim if (!CompressVTs) { 736309124Sdim OS << EN->getNumVTs(); 737309124Sdim if (!OmitComments) 738309124Sdim OS << "/*#VTs*/"; 739309124Sdim OS << ", "; 740309124Sdim } 741204642Srdivacky for (unsigned i = 0, e = EN->getNumVTs(); i != e; ++i) 742204642Srdivacky OS << getEnumName(EN->getVT(i)) << ", "; 743204642Srdivacky 744204642Srdivacky OS << EN->getNumOperands(); 745204642Srdivacky if (!OmitComments) 746204642Srdivacky OS << "/*#Ops*/"; 747204642Srdivacky OS << ", "; 748204642Srdivacky unsigned NumOperandBytes = 0; 749204642Srdivacky for (unsigned i = 0, e = EN->getNumOperands(); i != e; ++i) 750204642Srdivacky NumOperandBytes += EmitVBRValue(EN->getOperand(i), OS); 751221345Sdim 752204642Srdivacky if (!OmitComments) { 753204642Srdivacky // Print the result #'s for EmitNode. 754204642Srdivacky if (const EmitNodeMatcher *E = dyn_cast<EmitNodeMatcher>(EN)) { 755204642Srdivacky if (unsigned NumResults = EN->getNumVTs()) { 756327952Sdim OS << " // Results ="; 757204642Srdivacky unsigned First = E->getFirstResultSlot(); 758204642Srdivacky for (unsigned i = 0; i != NumResults; ++i) 759239462Sdim OS << " #" << First+i; 760204642Srdivacky } 761204642Srdivacky } 762204642Srdivacky OS << '\n'; 763204642Srdivacky 764204642Srdivacky if (const MorphNodeToMatcher *SNT = dyn_cast<MorphNodeToMatcher>(N)) { 765327952Sdim OS.indent(FullIndexWidth + Indent*2) << "// Src: " 766221345Sdim << *SNT->getPattern().getSrcPattern() << " - Complexity = " 767206083Srdivacky << SNT->getPattern().getPatternComplexity(CGP) << '\n'; 768327952Sdim OS.indent(FullIndexWidth + Indent*2) << "// Dst: " 769204642Srdivacky << *SNT->getPattern().getDstPattern() << '\n'; 770204642Srdivacky } 771204642Srdivacky } else 772204642Srdivacky OS << '\n'; 773221345Sdim 774321369Sdim return 5 + !CompressVTs + EN->getNumVTs() + NumOperandBytes + 775321369Sdim NumCoveredBytes; 776204642Srdivacky } 777204642Srdivacky case Matcher::CompleteMatch: { 778204642Srdivacky const CompleteMatchMatcher *CM = cast<CompleteMatchMatcher>(N); 779321369Sdim auto NumCoveredBytes = 0; 780321369Sdim if (InstrumentCoverage) { 781321369Sdim NumCoveredBytes = 3; 782321369Sdim OS << "OPC_Coverage, "; 783321369Sdim std::string src = 784321369Sdim GetPatFromTreePatternNode(CM->getPattern().getSrcPattern()); 785321369Sdim std::string dst = 786321369Sdim GetPatFromTreePatternNode(CM->getPattern().getDstPattern()); 787321369Sdim Record *PatRecord = CM->getPattern().getSrcRecord(); 788321369Sdim std::string include_src = getIncludePath(PatRecord); 789321369Sdim unsigned Offset = 790321369Sdim getPatternIdxFromTable(src + " -> " + dst, std::move(include_src)); 791321369Sdim OS << "TARGET_VAL(" << Offset << "),\n"; 792327952Sdim OS.indent(FullIndexWidth + Indent * 2); 793321369Sdim } 794204642Srdivacky OS << "OPC_CompleteMatch, " << CM->getNumResults() << ", "; 795204642Srdivacky unsigned NumResultBytes = 0; 796204642Srdivacky for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) 797204642Srdivacky NumResultBytes += EmitVBRValue(CM->getResult(i), OS); 798204642Srdivacky OS << '\n'; 799204642Srdivacky if (!OmitComments) { 800327952Sdim OS.indent(FullIndexWidth + Indent*2) << " // Src: " 801221345Sdim << *CM->getPattern().getSrcPattern() << " - Complexity = " 802206083Srdivacky << CM->getPattern().getPatternComplexity(CGP) << '\n'; 803327952Sdim OS.indent(FullIndexWidth + Indent*2) << " // Dst: " 804204642Srdivacky << *CM->getPattern().getDstPattern(); 805204642Srdivacky } 806204642Srdivacky OS << '\n'; 807321369Sdim return 2 + NumResultBytes + NumCoveredBytes; 808204642Srdivacky } 809204642Srdivacky } 810234353Sdim llvm_unreachable("Unreachable"); 811203954Srdivacky} 812203954Srdivacky 813204642Srdivacky/// EmitMatcherList - Emit the bytes for the specified matcher subtree. 814203954Srdivackyunsigned MatcherTableEmitter:: 815204642SrdivackyEmitMatcherList(const Matcher *N, unsigned Indent, unsigned CurrentIdx, 816327952Sdim raw_ostream &OS) { 817203954Srdivacky unsigned Size = 0; 818204642Srdivacky while (N) { 819204642Srdivacky if (!OmitComments) 820327952Sdim OS << "/*" << format_decimal(CurrentIdx, IndexWidth) << "*/"; 821204642Srdivacky unsigned MatcherSize = EmitMatcher(N, Indent, CurrentIdx, OS); 822204642Srdivacky Size += MatcherSize; 823204642Srdivacky CurrentIdx += MatcherSize; 824221345Sdim 825204642Srdivacky // If there are other nodes in this list, iterate to them, otherwise we're 826204642Srdivacky // done. 827204642Srdivacky N = N->getNext(); 828204642Srdivacky } 829204642Srdivacky return Size; 830204642Srdivacky} 831204642Srdivacky 832344779Sdimvoid MatcherTableEmitter::EmitNodePredicatesFunction( 833344779Sdim const std::vector<TreePredicateFn> &Preds, StringRef Decl, 834344779Sdim raw_ostream &OS) { 835344779Sdim if (Preds.empty()) 836344779Sdim return; 837344779Sdim 838344779Sdim BeginEmitFunction(OS, "bool", Decl, true/*AddOverride*/); 839344779Sdim OS << "{\n"; 840344779Sdim OS << " switch (PredNo) {\n"; 841344779Sdim OS << " default: llvm_unreachable(\"Invalid predicate in table?\");\n"; 842344779Sdim for (unsigned i = 0, e = Preds.size(); i != e; ++i) { 843344779Sdim // Emit the predicate code corresponding to this pattern. 844344779Sdim TreePredicateFn PredFn = Preds[i]; 845344779Sdim 846344779Sdim assert(!PredFn.isAlwaysTrue() && "No code in this predicate"); 847344779Sdim OS << " case " << i << ": { \n"; 848344779Sdim for (auto *SimilarPred : 849344779Sdim NodePredicatesByCodeToRun[PredFn.getCodeToRunOnSDNode()]) 850344779Sdim OS << " // " << TreePredicateFn(SimilarPred).getFnName() <<'\n'; 851344779Sdim 852344779Sdim OS << PredFn.getCodeToRunOnSDNode() << "\n }\n"; 853344779Sdim } 854344779Sdim OS << " }\n"; 855344779Sdim OS << "}\n"; 856344779Sdim EndEmitFunction(OS); 857344779Sdim} 858344779Sdim 859327952Sdimvoid MatcherTableEmitter::EmitPredicateFunctions(raw_ostream &OS) { 860204642Srdivacky // Emit pattern predicates. 861204642Srdivacky if (!PatternPredicates.empty()) { 862327952Sdim BeginEmitFunction(OS, "bool", 863327952Sdim "CheckPatternPredicate(unsigned PredNo) const", true/*AddOverride*/); 864327952Sdim OS << "{\n"; 865204642Srdivacky OS << " switch (PredNo) {\n"; 866234353Sdim OS << " default: llvm_unreachable(\"Invalid predicate in table?\");\n"; 867204642Srdivacky for (unsigned i = 0, e = PatternPredicates.size(); i != e; ++i) 868204642Srdivacky OS << " case " << i << ": return " << PatternPredicates[i] << ";\n"; 869204642Srdivacky OS << " }\n"; 870327952Sdim OS << "}\n"; 871327952Sdim EndEmitFunction(OS); 872204642Srdivacky } 873221345Sdim 874204642Srdivacky // Emit Node predicates. 875344779Sdim EmitNodePredicatesFunction( 876344779Sdim NodePredicates, "CheckNodePredicate(SDNode *Node, unsigned PredNo) const", 877344779Sdim OS); 878344779Sdim EmitNodePredicatesFunction( 879344779Sdim NodePredicatesWithOperands, 880344779Sdim "CheckNodePredicateWithOperands(SDNode *Node, unsigned PredNo, " 881344779Sdim "const SmallVectorImpl<SDValue> &Operands) const", 882344779Sdim OS); 883327952Sdim 884204642Srdivacky // Emit CompletePattern matchers. 885204642Srdivacky // FIXME: This should be const. 886204642Srdivacky if (!ComplexPatterns.empty()) { 887327952Sdim BeginEmitFunction(OS, "bool", 888327952Sdim "CheckComplexPattern(SDNode *Root, SDNode *Parent,\n" 889327952Sdim " SDValue N, unsigned PatternNo,\n" 890327952Sdim " SmallVectorImpl<std::pair<SDValue, SDNode*>> &Result)", 891327952Sdim true/*AddOverride*/); 892327952Sdim OS << "{\n"; 893210299Sed OS << " unsigned NextRes = Result.size();\n"; 894204642Srdivacky OS << " switch (PatternNo) {\n"; 895234353Sdim OS << " default: llvm_unreachable(\"Invalid pattern # in table?\");\n"; 896204642Srdivacky for (unsigned i = 0, e = ComplexPatterns.size(); i != e; ++i) { 897204642Srdivacky const ComplexPattern &P = *ComplexPatterns[i]; 898204642Srdivacky unsigned NumOps = P.getNumOperands(); 899204642Srdivacky 900204642Srdivacky if (P.hasProperty(SDNPHasChain)) 901204642Srdivacky ++NumOps; // Get the chained node too. 902221345Sdim 903204642Srdivacky OS << " case " << i << ":\n"; 904321369Sdim if (InstrumentCoverage) 905321369Sdim OS << " {\n"; 906210299Sed OS << " Result.resize(NextRes+" << NumOps << ");\n"; 907321369Sdim if (InstrumentCoverage) 908321369Sdim OS << " bool Succeeded = " << P.getSelectFunc(); 909321369Sdim else 910321369Sdim OS << " return " << P.getSelectFunc(); 911204642Srdivacky 912218893Sdim OS << "("; 913218893Sdim // If the complex pattern wants the root of the match, pass it in as the 914218893Sdim // first argument. 915218893Sdim if (P.hasProperty(SDNPWantRoot)) 916218893Sdim OS << "Root, "; 917221345Sdim 918218893Sdim // If the complex pattern wants the parent of the operand being matched, 919218893Sdim // pass it in as the next argument. 920218893Sdim if (P.hasProperty(SDNPWantParent)) 921218893Sdim OS << "Parent, "; 922221345Sdim 923218893Sdim OS << "N"; 924204642Srdivacky for (unsigned i = 0; i != NumOps; ++i) 925218893Sdim OS << ", Result[NextRes+" << i << "].first"; 926204642Srdivacky OS << ");\n"; 927321369Sdim if (InstrumentCoverage) { 928321369Sdim OS << " if (Succeeded)\n"; 929321369Sdim OS << " dbgs() << \"\\nCOMPLEX_PATTERN: " << P.getSelectFunc() 930321369Sdim << "\\n\" ;\n"; 931321369Sdim OS << " return Succeeded;\n"; 932321369Sdim OS << " }\n"; 933321369Sdim } 934204642Srdivacky } 935204642Srdivacky OS << " }\n"; 936327952Sdim OS << "}\n"; 937327952Sdim EndEmitFunction(OS); 938204642Srdivacky } 939221345Sdim 940221345Sdim 941204642Srdivacky // Emit SDNodeXForm handlers. 942204642Srdivacky // FIXME: This should be const. 943204642Srdivacky if (!NodeXForms.empty()) { 944327952Sdim BeginEmitFunction(OS, "SDValue", 945327952Sdim "RunSDNodeXForm(SDValue V, unsigned XFormNo)", true/*AddOverride*/); 946327952Sdim OS << "{\n"; 947204642Srdivacky OS << " switch (XFormNo) {\n"; 948234353Sdim OS << " default: llvm_unreachable(\"Invalid xform # in table?\");\n"; 949221345Sdim 950204642Srdivacky // FIXME: The node xform could take SDValue's instead of SDNode*'s. 951204642Srdivacky for (unsigned i = 0, e = NodeXForms.size(); i != e; ++i) { 952204642Srdivacky const CodeGenDAGPatterns::NodeXForm &Entry = 953204642Srdivacky CGP.getSDNodeTransform(NodeXForms[i]); 954221345Sdim 955204642Srdivacky Record *SDNode = Entry.first; 956204642Srdivacky const std::string &Code = Entry.second; 957221345Sdim 958204642Srdivacky OS << " case " << i << ": { "; 959204642Srdivacky if (!OmitComments) 960204642Srdivacky OS << "// " << NodeXForms[i]->getName(); 961204642Srdivacky OS << '\n'; 962221345Sdim 963204642Srdivacky std::string ClassName = CGP.getSDNodeInfo(SDNode).getSDClassName(); 964204642Srdivacky if (ClassName == "SDNode") 965204642Srdivacky OS << " SDNode *N = V.getNode();\n"; 966204642Srdivacky else 967204642Srdivacky OS << " " << ClassName << " *N = cast<" << ClassName 968204642Srdivacky << ">(V.getNode());\n"; 969204642Srdivacky OS << Code << "\n }\n"; 970203954Srdivacky } 971204642Srdivacky OS << " }\n"; 972327952Sdim OS << "}\n"; 973327952Sdim EndEmitFunction(OS); 974203954Srdivacky } 975203954Srdivacky} 976203954Srdivacky 977204792Srdivackystatic void BuildHistogram(const Matcher *M, std::vector<unsigned> &OpcodeFreq){ 978276479Sdim for (; M != nullptr; M = M->getNext()) { 979204792Srdivacky // Count this node. 980204792Srdivacky if (unsigned(M->getKind()) >= OpcodeFreq.size()) 981204792Srdivacky OpcodeFreq.resize(M->getKind()+1); 982204792Srdivacky OpcodeFreq[M->getKind()]++; 983221345Sdim 984204792Srdivacky // Handle recursive nodes. 985204792Srdivacky if (const ScopeMatcher *SM = dyn_cast<ScopeMatcher>(M)) { 986204792Srdivacky for (unsigned i = 0, e = SM->getNumChildren(); i != e; ++i) 987204792Srdivacky BuildHistogram(SM->getChild(i), OpcodeFreq); 988221345Sdim } else if (const SwitchOpcodeMatcher *SOM = 989204792Srdivacky dyn_cast<SwitchOpcodeMatcher>(M)) { 990204792Srdivacky for (unsigned i = 0, e = SOM->getNumCases(); i != e; ++i) 991204792Srdivacky BuildHistogram(SOM->getCaseMatcher(i), OpcodeFreq); 992204792Srdivacky } else if (const SwitchTypeMatcher *STM = dyn_cast<SwitchTypeMatcher>(M)) { 993204792Srdivacky for (unsigned i = 0, e = STM->getNumCases(); i != e; ++i) 994204792Srdivacky BuildHistogram(STM->getCaseMatcher(i), OpcodeFreq); 995204792Srdivacky } 996204792Srdivacky } 997204792Srdivacky} 998204792Srdivacky 999327952Sdimstatic StringRef getOpcodeString(Matcher::KindTy Kind) { 1000327952Sdim switch (Kind) { 1001327952Sdim case Matcher::Scope: return "OPC_Scope"; break; 1002327952Sdim case Matcher::RecordNode: return "OPC_RecordNode"; break; 1003327952Sdim case Matcher::RecordChild: return "OPC_RecordChild"; break; 1004327952Sdim case Matcher::RecordMemRef: return "OPC_RecordMemRef"; break; 1005327952Sdim case Matcher::CaptureGlueInput: return "OPC_CaptureGlueInput"; break; 1006327952Sdim case Matcher::MoveChild: return "OPC_MoveChild"; break; 1007327952Sdim case Matcher::MoveParent: return "OPC_MoveParent"; break; 1008327952Sdim case Matcher::CheckSame: return "OPC_CheckSame"; break; 1009327952Sdim case Matcher::CheckChildSame: return "OPC_CheckChildSame"; break; 1010327952Sdim case Matcher::CheckPatternPredicate: 1011327952Sdim return "OPC_CheckPatternPredicate"; break; 1012327952Sdim case Matcher::CheckPredicate: return "OPC_CheckPredicate"; break; 1013327952Sdim case Matcher::CheckOpcode: return "OPC_CheckOpcode"; break; 1014327952Sdim case Matcher::SwitchOpcode: return "OPC_SwitchOpcode"; break; 1015327952Sdim case Matcher::CheckType: return "OPC_CheckType"; break; 1016327952Sdim case Matcher::SwitchType: return "OPC_SwitchType"; break; 1017327952Sdim case Matcher::CheckChildType: return "OPC_CheckChildType"; break; 1018327952Sdim case Matcher::CheckInteger: return "OPC_CheckInteger"; break; 1019327952Sdim case Matcher::CheckChildInteger: return "OPC_CheckChildInteger"; break; 1020327952Sdim case Matcher::CheckCondCode: return "OPC_CheckCondCode"; break; 1021353358Sdim case Matcher::CheckChild2CondCode: return "OPC_CheckChild2CondCode"; break; 1022327952Sdim case Matcher::CheckValueType: return "OPC_CheckValueType"; break; 1023327952Sdim case Matcher::CheckComplexPat: return "OPC_CheckComplexPat"; break; 1024327952Sdim case Matcher::CheckAndImm: return "OPC_CheckAndImm"; break; 1025327952Sdim case Matcher::CheckOrImm: return "OPC_CheckOrImm"; break; 1026327952Sdim case Matcher::CheckFoldableChainNode: 1027327952Sdim return "OPC_CheckFoldableChainNode"; break; 1028353358Sdim case Matcher::CheckImmAllOnesV: return "OPC_CheckImmAllOnesV"; break; 1029353358Sdim case Matcher::CheckImmAllZerosV: return "OPC_CheckImmAllZerosV"; break; 1030327952Sdim case Matcher::EmitInteger: return "OPC_EmitInteger"; break; 1031327952Sdim case Matcher::EmitStringInteger: return "OPC_EmitStringInteger"; break; 1032327952Sdim case Matcher::EmitRegister: return "OPC_EmitRegister"; break; 1033327952Sdim case Matcher::EmitConvertToTarget: return "OPC_EmitConvertToTarget"; break; 1034327952Sdim case Matcher::EmitMergeInputChains: return "OPC_EmitMergeInputChains"; break; 1035327952Sdim case Matcher::EmitCopyToReg: return "OPC_EmitCopyToReg"; break; 1036327952Sdim case Matcher::EmitNode: return "OPC_EmitNode"; break; 1037327952Sdim case Matcher::MorphNodeTo: return "OPC_MorphNodeTo"; break; 1038327952Sdim case Matcher::EmitNodeXForm: return "OPC_EmitNodeXForm"; break; 1039327952Sdim case Matcher::CompleteMatch: return "OPC_CompleteMatch"; break; 1040327952Sdim } 1041327952Sdim 1042327952Sdim llvm_unreachable("Unhandled opcode?"); 1043327952Sdim} 1044327952Sdim 1045204792Srdivackyvoid MatcherTableEmitter::EmitHistogram(const Matcher *M, 1046327952Sdim raw_ostream &OS) { 1047204642Srdivacky if (OmitComments) 1048204642Srdivacky return; 1049221345Sdim 1050204792Srdivacky std::vector<unsigned> OpcodeFreq; 1051204792Srdivacky BuildHistogram(M, OpcodeFreq); 1052221345Sdim 1053204642Srdivacky OS << " // Opcode Histogram:\n"; 1054204792Srdivacky for (unsigned i = 0, e = OpcodeFreq.size(); i != e; ++i) { 1055327952Sdim OS << " // #" 1056327952Sdim << left_justify(getOpcodeString((Matcher::KindTy)i), HistOpcWidth) 1057327952Sdim << " = " << OpcodeFreq[i] << '\n'; 1058204642Srdivacky } 1059204642Srdivacky OS << '\n'; 1060203954Srdivacky} 1061203954Srdivacky 1062203954Srdivacky 1063204642Srdivackyvoid llvm::EmitMatcherTable(const Matcher *TheMatcher, 1064221345Sdim const CodeGenDAGPatterns &CGP, 1065327952Sdim raw_ostream &OS) { 1066327952Sdim OS << "#if defined(GET_DAGISEL_DECL) && defined(GET_DAGISEL_BODY)\n"; 1067327952Sdim OS << "#error GET_DAGISEL_DECL and GET_DAGISEL_BODY cannot be both defined, "; 1068327952Sdim OS << "undef both for inline definitions\n"; 1069327952Sdim OS << "#endif\n\n"; 1070221345Sdim 1071327952Sdim // Emit a check for omitted class name. 1072327952Sdim OS << "#ifdef GET_DAGISEL_BODY\n"; 1073327952Sdim OS << "#define LOCAL_DAGISEL_STRINGIZE(X) LOCAL_DAGISEL_STRINGIZE_(X)\n"; 1074327952Sdim OS << "#define LOCAL_DAGISEL_STRINGIZE_(X) #X\n"; 1075327952Sdim OS << "static_assert(sizeof(LOCAL_DAGISEL_STRINGIZE(GET_DAGISEL_BODY)) > 1," 1076327952Sdim "\n"; 1077327952Sdim OS << " \"GET_DAGISEL_BODY is empty: it should be defined with the class " 1078327952Sdim "name\");\n"; 1079327952Sdim OS << "#undef LOCAL_DAGISEL_STRINGIZE_\n"; 1080327952Sdim OS << "#undef LOCAL_DAGISEL_STRINGIZE\n"; 1081327952Sdim OS << "#endif\n\n"; 1082203954Srdivacky 1083327952Sdim OS << "#if !defined(GET_DAGISEL_DECL) && !defined(GET_DAGISEL_BODY)\n"; 1084327952Sdim OS << "#define DAGISEL_INLINE 1\n"; 1085327952Sdim OS << "#else\n"; 1086327952Sdim OS << "#define DAGISEL_INLINE 0\n"; 1087327952Sdim OS << "#endif\n\n"; 1088327952Sdim 1089327952Sdim OS << "#if !DAGISEL_INLINE\n"; 1090327952Sdim OS << "#define DAGISEL_CLASS_COLONCOLON GET_DAGISEL_BODY ::\n"; 1091327952Sdim OS << "#else\n"; 1092327952Sdim OS << "#define DAGISEL_CLASS_COLONCOLON\n"; 1093327952Sdim OS << "#endif\n\n"; 1094327952Sdim 1095327952Sdim BeginEmitFunction(OS, "void", "SelectCode(SDNode *N)", false/*AddOverride*/); 1096206083Srdivacky MatcherTableEmitter MatcherEmitter(CGP); 1097203954Srdivacky 1098327952Sdim OS << "{\n"; 1099221345Sdim OS << " // Some target values are emitted as 2 bytes, TARGET_VAL handles\n"; 1100221345Sdim OS << " // this.\n"; 1101221345Sdim OS << " #define TARGET_VAL(X) X & 255, unsigned(X) >> 8\n"; 1102203954Srdivacky OS << " static const unsigned char MatcherTable[] = {\n"; 1103327952Sdim unsigned TotalSize = MatcherEmitter.EmitMatcherList(TheMatcher, 1, 0, OS); 1104203954Srdivacky OS << " 0\n }; // Total Array size is " << (TotalSize+1) << " bytes\n\n"; 1105221345Sdim 1106204792Srdivacky MatcherEmitter.EmitHistogram(TheMatcher, OS); 1107221345Sdim 1108221345Sdim OS << " #undef TARGET_VAL\n"; 1109309124Sdim OS << " SelectCodeCommon(N, MatcherTable,sizeof(MatcherTable));\n"; 1110309124Sdim OS << "}\n"; 1111327952Sdim EndEmitFunction(OS); 1112221345Sdim 1113203954Srdivacky // Next up, emit the function for node and pattern predicates: 1114206083Srdivacky MatcherEmitter.EmitPredicateFunctions(OS); 1115321369Sdim 1116321369Sdim if (InstrumentCoverage) 1117321369Sdim MatcherEmitter.EmitPatternMatchTable(OS); 1118327952Sdim 1119327952Sdim // Clean up the preprocessor macros. 1120327952Sdim OS << "\n"; 1121327952Sdim OS << "#ifdef DAGISEL_INLINE\n"; 1122327952Sdim OS << "#undef DAGISEL_INLINE\n"; 1123327952Sdim OS << "#endif\n"; 1124327952Sdim OS << "#ifdef DAGISEL_CLASS_COLONCOLON\n"; 1125327952Sdim OS << "#undef DAGISEL_CLASS_COLONCOLON\n"; 1126327952Sdim OS << "#endif\n"; 1127327952Sdim OS << "#ifdef GET_DAGISEL_DECL\n"; 1128327952Sdim OS << "#undef GET_DAGISEL_DECL\n"; 1129327952Sdim OS << "#endif\n"; 1130327952Sdim OS << "#ifdef GET_DAGISEL_BODY\n"; 1131327952Sdim OS << "#undef GET_DAGISEL_BODY\n"; 1132327952Sdim OS << "#endif\n"; 1133203954Srdivacky} 1134