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