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"
21using namespace llvm;
22
23#define DEBUG_TYPE "dag-isel-emitter"
24
25namespace {
26/// DAGISelEmitter - The top-level class which coordinates construction
27/// and emission of the instruction selector.
28class DAGISelEmitter {
29 const RecordKeeper &Records; // Just so we can get at the timing functions.
30 const CodeGenDAGPatterns CGP;
31
32public:
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.
45static 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.
65static 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
80namespace {
81// The properties of a pattern used to sort it, computed once per pattern.
82struct 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.
107struct 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
144void 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
214static TableGen::Emitter::OptClass<DAGISelEmitter>
215 X("gen-dag-isel", "Generate a DAG instruction selector");
216