1 //===- DAGISelEmitter.cpp - Generate an instruction selector --------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This tablegen backend emits a DAG instruction selector. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "CodeGenDAGPatterns.h" 14 #include "DAGISelMatcher.h" 15 #include "llvm/Support/Debug.h" 16 #include "llvm/TableGen/Record.h" 17 #include "llvm/TableGen/TableGenBackend.h" 18 using namespace llvm; 19 20 #define DEBUG_TYPE "dag-isel-emitter" 21 22 namespace { 23 /// DAGISelEmitter - The top-level class which coordinates construction 24 /// and emission of the instruction selector. 25 class DAGISelEmitter { 26 CodeGenDAGPatterns CGP; 27 public: 28 explicit DAGISelEmitter(RecordKeeper &R) : CGP(R) {} 29 void run(raw_ostream &OS); 30 }; 31 } // End anonymous namespace 32 33 //===----------------------------------------------------------------------===// 34 // DAGISelEmitter Helper methods 35 // 36 37 /// getResultPatternCost - Compute the number of instructions for this pattern. 38 /// This is a temporary hack. We should really include the instruction 39 /// latencies in this calculation. 40 static unsigned getResultPatternCost(TreePatternNode *P, 41 CodeGenDAGPatterns &CGP) { 42 if (P->isLeaf()) return 0; 43 44 unsigned Cost = 0; 45 Record *Op = P->getOperator(); 46 if (Op->isSubClassOf("Instruction")) { 47 Cost++; 48 CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(Op); 49 if (II.usesCustomInserter) 50 Cost += 10; 51 } 52 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 53 Cost += getResultPatternCost(P->getChild(i), CGP); 54 return Cost; 55 } 56 57 /// getResultPatternCodeSize - Compute the code size of instructions for this 58 /// pattern. 59 static unsigned getResultPatternSize(TreePatternNode *P, 60 CodeGenDAGPatterns &CGP) { 61 if (P->isLeaf()) return 0; 62 63 unsigned Cost = 0; 64 Record *Op = P->getOperator(); 65 if (Op->isSubClassOf("Instruction")) { 66 Cost += Op->getValueAsInt("CodeSize"); 67 } 68 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) 69 Cost += getResultPatternSize(P->getChild(i), CGP); 70 return Cost; 71 } 72 73 namespace { 74 // PatternSortingPredicate - return true if we prefer to match LHS before RHS. 75 // In particular, we want to match maximal patterns first and lowest cost within 76 // a particular complexity first. 77 struct PatternSortingPredicate { 78 PatternSortingPredicate(CodeGenDAGPatterns &cgp) : CGP(cgp) {} 79 CodeGenDAGPatterns &CGP; 80 81 bool operator()(const PatternToMatch *LHS, const PatternToMatch *RHS) { 82 const TreePatternNode *LT = LHS->getSrcPattern(); 83 const TreePatternNode *RT = RHS->getSrcPattern(); 84 85 MVT LHSVT = LT->getNumTypes() != 0 ? LT->getSimpleType(0) : MVT::Other; 86 MVT RHSVT = RT->getNumTypes() != 0 ? RT->getSimpleType(0) : MVT::Other; 87 if (LHSVT.isVector() != RHSVT.isVector()) 88 return RHSVT.isVector(); 89 90 if (LHSVT.isFloatingPoint() != RHSVT.isFloatingPoint()) 91 return RHSVT.isFloatingPoint(); 92 93 // Otherwise, if the patterns might both match, sort based on complexity, 94 // which means that we prefer to match patterns that cover more nodes in the 95 // input over nodes that cover fewer. 96 int LHSSize = LHS->getPatternComplexity(CGP); 97 int RHSSize = RHS->getPatternComplexity(CGP); 98 if (LHSSize > RHSSize) return true; // LHS -> bigger -> less cost 99 if (LHSSize < RHSSize) return false; 100 101 // If the patterns have equal complexity, compare generated instruction cost 102 unsigned LHSCost = getResultPatternCost(LHS->getDstPattern(), CGP); 103 unsigned RHSCost = getResultPatternCost(RHS->getDstPattern(), CGP); 104 if (LHSCost < RHSCost) return true; 105 if (LHSCost > RHSCost) return false; 106 107 unsigned LHSPatSize = getResultPatternSize(LHS->getDstPattern(), CGP); 108 unsigned RHSPatSize = getResultPatternSize(RHS->getDstPattern(), CGP); 109 if (LHSPatSize < RHSPatSize) return true; 110 if (LHSPatSize > RHSPatSize) return false; 111 112 // Sort based on the UID of the pattern, to reflect source order. 113 // Note that this is not guaranteed to be unique, since a single source 114 // pattern may have been resolved into multiple match patterns due to 115 // alternative fragments. To ensure deterministic output, always use 116 // std::stable_sort with this predicate. 117 return LHS->ID < RHS->ID; 118 } 119 }; 120 } // End anonymous namespace 121 122 123 void DAGISelEmitter::run(raw_ostream &OS) { 124 emitSourceFileHeader("DAG Instruction Selector for the " + 125 CGP.getTargetInfo().getName().str() + " target", OS); 126 127 OS << "// *** NOTE: This file is #included into the middle of the target\n" 128 << "// *** instruction selector class. These functions are really " 129 << "methods.\n\n"; 130 131 OS << "// If GET_DAGISEL_DECL is #defined with any value, only function\n" 132 "// declarations will be included when this file is included.\n" 133 "// If GET_DAGISEL_BODY is #defined, its value should be the name of\n" 134 "// the instruction selector class. Function bodies will be emitted\n" 135 "// and each function's name will be qualified with the name of the\n" 136 "// class.\n" 137 "//\n" 138 "// When neither of the GET_DAGISEL* macros is defined, the functions\n" 139 "// are emitted inline.\n\n"; 140 141 LLVM_DEBUG(errs() << "\n\nALL PATTERNS TO MATCH:\n\n"; 142 for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), 143 E = CGP.ptm_end(); 144 I != E; ++I) { 145 errs() << "PATTERN: "; 146 I->getSrcPattern()->dump(); 147 errs() << "\nRESULT: "; 148 I->getDstPattern()->dump(); 149 errs() << "\n"; 150 }); 151 152 // Add all the patterns to a temporary list so we can sort them. 153 std::vector<const PatternToMatch*> Patterns; 154 for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), E = CGP.ptm_end(); 155 I != E; ++I) 156 Patterns.push_back(&*I); 157 158 // We want to process the matches in order of minimal cost. Sort the patterns 159 // so the least cost one is at the start. 160 std::stable_sort(Patterns.begin(), Patterns.end(), 161 PatternSortingPredicate(CGP)); 162 163 164 // Convert each variant of each pattern into a Matcher. 165 std::vector<Matcher*> PatternMatchers; 166 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 167 for (unsigned Variant = 0; ; ++Variant) { 168 if (Matcher *M = ConvertPatternToMatcher(*Patterns[i], Variant, CGP)) 169 PatternMatchers.push_back(M); 170 else 171 break; 172 } 173 } 174 175 std::unique_ptr<Matcher> TheMatcher = 176 std::make_unique<ScopeMatcher>(PatternMatchers); 177 178 OptimizeMatcher(TheMatcher, CGP); 179 //Matcher->dump(); 180 EmitMatcherTable(TheMatcher.get(), CGP, OS); 181 } 182 183 namespace llvm { 184 185 void EmitDAGISel(RecordKeeper &RK, raw_ostream &OS) { 186 DAGISelEmitter(RK).run(OS); 187 } 188 189 } // End llvm namespace 190