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