| 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 "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(Name: "Instruction" )) { |
| 53 | Cost++; |
| 54 | const CodeGenInstruction &II = CGP.getTargetInfo().getInstruction(InstRec: Op); |
| 55 | if (II.usesCustomInserter) |
| 56 | Cost += 10; |
| 57 | } |
| 58 | for (const TreePatternNode &Child : P.children()) |
| 59 | Cost += getResultPatternCost(P: 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(Name: "Instruction" )) { |
| 73 | Cost += Op->getValueAsInt(FieldName: "CodeSize" ); |
| 74 | } |
| 75 | for (const TreePatternNode &Child : P.children()) |
| 76 | Cost += getResultPatternSize(P: Child, CGP); |
| 77 | return Cost; |
| 78 | } |
| 79 | |
| 80 | namespace { |
| 81 | // The properties of a pattern used to sort it, computed once per pattern. |
| 82 | struct PatternSortKey { |
| 83 | const PatternToMatch *Pattern; |
| 84 | bool IsVector = false; |
| 85 | bool IsFP = false; |
| 86 | int Complexity; |
| 87 | unsigned Cost; |
| 88 | unsigned Size; |
| 89 | |
| 90 | PatternSortKey(const PatternToMatch *P, const CodeGenDAGPatterns &CGP) |
| 91 | : Pattern(P), Complexity(P->getPatternComplexity(CGP)), |
| 92 | Cost(getResultPatternCost(P: P->getDstPattern(), CGP)), |
| 93 | Size(getResultPatternSize(P: P->getDstPattern(), CGP)) { |
| 94 | const TreePatternNode &T = P->getSrcPattern(); |
| 95 | if (T.getNumTypes() != 0) { |
| 96 | for (auto [_, VT] : T.getType(ResNo: 0)) { |
| 97 | IsVector |= VT.isVector(); |
| 98 | IsFP |= VT.isFloatingPoint(); |
| 99 | } |
| 100 | } |
| 101 | } |
| 102 | }; |
| 103 | |
| 104 | // PatternSortingPredicate - return true if we prefer to match LHS before RHS. |
| 105 | // In particular, we want to match maximal patterns first and lowest cost within |
| 106 | // a particular complexity first. |
| 107 | struct PatternSortingPredicate { |
| 108 | bool operator()(const PatternSortKey &LHS, const PatternSortKey &RHS) { |
| 109 | if (LHS.IsVector != RHS.IsVector) |
| 110 | return RHS.IsVector; |
| 111 | |
| 112 | if (LHS.IsFP != RHS.IsFP) |
| 113 | return RHS.IsFP; |
| 114 | |
| 115 | // Otherwise, if the patterns might both match, sort based on complexity, |
| 116 | // which means that we prefer to match patterns that cover more nodes in the |
| 117 | // input over nodes that cover fewer. |
| 118 | if (LHS.Complexity > RHS.Complexity) |
| 119 | return true; // LHS -> bigger -> less cost |
| 120 | if (LHS.Complexity < RHS.Complexity) |
| 121 | return false; |
| 122 | |
| 123 | // If the patterns have equal complexity, compare generated instruction cost |
| 124 | if (LHS.Cost < RHS.Cost) |
| 125 | return true; |
| 126 | if (LHS.Cost > RHS.Cost) |
| 127 | return false; |
| 128 | |
| 129 | if (LHS.Size < RHS.Size) |
| 130 | return true; |
| 131 | if (LHS.Size > RHS.Size) |
| 132 | return false; |
| 133 | |
| 134 | // Sort based on the UID of the pattern, to reflect source order. |
| 135 | // Note that this is not guaranteed to be unique, since a single source |
| 136 | // pattern may have been resolved into multiple match patterns due to |
| 137 | // alternative fragments. To ensure deterministic output, always use |
| 138 | // std::stable_sort with this predicate. |
| 139 | return LHS.Pattern->getID() < RHS.Pattern->getID(); |
| 140 | } |
| 141 | }; |
| 142 | } // End anonymous namespace |
| 143 | |
| 144 | void DAGISelEmitter::run(raw_ostream &OS) { |
| 145 | TGTimer &Timer = Records.getTimer(); |
| 146 | Timer.startTimer(Name: "Parse patterns" ); |
| 147 | emitSourceFileHeader(Desc: "DAG Instruction Selector for the " + |
| 148 | CGP.getTargetInfo().getName().str() + " target" , |
| 149 | OS); |
| 150 | |
| 151 | OS << "// *** NOTE: This file is #included into the middle of the target\n" |
| 152 | << "// *** instruction selector class. These functions are really " |
| 153 | << "methods.\n\n" ; |
| 154 | |
| 155 | OS << "// If GET_DAGISEL_DECL is #defined with any value, only function\n" |
| 156 | "// declarations will be included when this file is included.\n" |
| 157 | "// If GET_DAGISEL_BODY is #defined, its value should be the name of\n" |
| 158 | "// the instruction selector class. Function bodies will be emitted\n" |
| 159 | "// and each function's name will be qualified with the name of the\n" |
| 160 | "// class.\n" |
| 161 | "//\n" |
| 162 | "// When neither of the GET_DAGISEL* macros is defined, the functions\n" |
| 163 | "// are emitted inline.\n\n" ; |
| 164 | |
| 165 | LLVM_DEBUG(dbgs() << "\n\nALL PATTERNS TO MATCH:\n\n" ; |
| 166 | for (CodeGenDAGPatterns::ptm_iterator I = CGP.ptm_begin(), |
| 167 | E = CGP.ptm_end(); |
| 168 | I != E; ++I) { |
| 169 | dbgs() << "PATTERN: " ; |
| 170 | I->getSrcPattern().dump(); |
| 171 | dbgs() << "\nRESULT: " ; |
| 172 | I->getDstPattern().dump(); |
| 173 | dbgs() << "\n" ; |
| 174 | }); |
| 175 | |
| 176 | // Add all the patterns to a temporary list so we can sort them. |
| 177 | Timer.startTimer(Name: "Sort patterns" ); |
| 178 | std::vector<PatternSortKey> SortKeys; |
| 179 | for (const PatternToMatch &PTM : CGP.ptms()) |
| 180 | SortKeys.emplace_back(args: &PTM, args: CGP); |
| 181 | |
| 182 | // We want to process the matches in order of minimal cost. Sort the patterns |
| 183 | // so the least cost one is at the start. |
| 184 | llvm::stable_sort(Range&: SortKeys, C: PatternSortingPredicate()); |
| 185 | std::vector<const PatternToMatch *> Patterns; |
| 186 | Patterns.reserve(n: SortKeys.size()); |
| 187 | for (const PatternSortKey &Key : SortKeys) |
| 188 | Patterns.push_back(x: Key.Pattern); |
| 189 | |
| 190 | // Convert each variant of each pattern into a Matcher. |
| 191 | Timer.startTimer(Name: "Convert to matchers" ); |
| 192 | SmallVector<MatcherList, 0> PatternMatchers; |
| 193 | for (const PatternToMatch *PTM : Patterns) { |
| 194 | for (unsigned Variant = 0;; ++Variant) { |
| 195 | MatcherList ML = ConvertPatternToMatcherList(Pattern: *PTM, Variant, CGP); |
| 196 | if (ML.empty()) |
| 197 | break; |
| 198 | PatternMatchers.push_back(Elt: std::move(ML)); |
| 199 | } |
| 200 | } |
| 201 | |
| 202 | MatcherList Matchers; |
| 203 | Matchers.push_front(M: new ScopeMatcher(std::move(PatternMatchers))); |
| 204 | |
| 205 | Timer.startTimer(Name: "Optimize matchers" ); |
| 206 | OptimizeMatcher(ML&: Matchers, CGP); |
| 207 | |
| 208 | // Matchers->dump(); |
| 209 | |
| 210 | Timer.startTimer(Name: "Emit matcher table" ); |
| 211 | EmitMatcherTable(ML&: Matchers, CGP, OS); |
| 212 | } |
| 213 | |
| 214 | static TableGen::Emitter::OptClass<DAGISelEmitter> |
| 215 | X("gen-dag-isel" , "Generate a DAG instruction selector" ); |
| 216 | |