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