1 //===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This tablegen backend emits code for use by the GlobalISel instruction
12 /// selector. See include/llvm/CodeGen/TargetGlobalISel.td.
14 /// This file analyzes the patterns recognized by the SelectionDAGISel tablegen
15 /// backend, filters out the ones that are unsupported, maps
16 /// SelectionDAG-specific constructs to their GlobalISel counterpart
17 /// (when applicable: MVT to LLT; SDNode to generic Instruction).
19 /// Not all patterns are supported: pass the tablegen invocation
20 /// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped,
23 /// The generated file defines a single method:
24 /// bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const;
25 /// intended to be used in InstructionSelector::select as the first-step
26 /// selector for the patterns that don't require complex C++.
28 /// FIXME: We'll probably want to eventually define a base
29 /// "TargetGenInstructionSelector" class.
31 //===----------------------------------------------------------------------===//
33 #include "CodeGenDAGPatterns.h"
34 #include "llvm/ADT/Optional.h"
35 #include "llvm/ADT/Statistic.h"
36 #include "llvm/CodeGen/MachineValueType.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/TableGen/Error.h"
39 #include "llvm/TableGen/Record.h"
40 #include "llvm/TableGen/TableGenBackend.h"
44 #define DEBUG_TYPE "gisel-emitter"
46 STATISTIC(NumPatternTotal, "Total number of patterns");
47 STATISTIC(NumPatternSkipped, "Number of patterns skipped");
48 STATISTIC(NumPatternEmitted, "Number of patterns emitted");
50 static cl::opt<bool> WarnOnSkippedPatterns(
51 "warn-on-skipped-patterns",
52 cl::desc("Explain why a pattern was skipped for inclusion "
53 "in the GlobalISel selector"),
58 class GlobalISelEmitter {
60 explicit GlobalISelEmitter(RecordKeeper &RK);
61 void run(raw_ostream &OS);
64 const RecordKeeper &RK;
65 const CodeGenDAGPatterns CGP;
66 const CodeGenTarget &Target;
68 /// Keep track of the equivalence between SDNodes and Instruction.
69 /// This is defined using 'GINodeEquiv' in the target description.
70 DenseMap<Record *, const CodeGenInstruction *> NodeEquivs;
72 void gatherNodeEquivs();
73 const CodeGenInstruction *findNodeEquiv(Record *N);
79 /// Analyze pattern \p P, possibly emitting matching code for it to \p OS.
80 /// Otherwise, return a reason why this pattern was skipped for emission.
81 Optional<SkipReason> runOnPattern(const PatternToMatch &P,
85 } // end anonymous namespace
87 //===- Helper functions ---------------------------------------------------===//
89 /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for
90 /// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...).
91 static Optional<std::string> MVTToLLT(MVT::SimpleValueType SVT) {
93 raw_string_ostream OS(TyStr);
95 if (VT.isVector() && VT.getVectorNumElements() != 1) {
96 OS << "LLT::vector(" << VT.getVectorNumElements() << ", "
97 << VT.getScalarSizeInBits() << ")";
98 } else if (VT.isInteger() || VT.isFloatingPoint()) {
99 OS << "LLT::scalar(" << VT.getSizeInBits() << ")";
107 static bool isTrivialOperatorNode(const TreePatternNode *N) {
108 return !N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn();
111 //===- Matchers -----------------------------------------------------------===//
114 virtual ~Matcher() {}
115 virtual void emit(raw_ostream &OS) const = 0;
118 raw_ostream &operator<<(raw_ostream &S, const Matcher &M) {
124 virtual ~MatchAction() {}
125 virtual void emit(raw_ostream &OS) const = 0;
128 raw_ostream &operator<<(raw_ostream &S, const MatchAction &A) {
133 struct MatchOpcode : public Matcher {
134 MatchOpcode(const CodeGenInstruction *I) : I(I) {}
135 const CodeGenInstruction *I;
137 virtual void emit(raw_ostream &OS) const {
138 OS << "I.getOpcode() == " << I->Namespace << "::" << I->TheDef->getName();
142 struct MatchRegOpType : public Matcher {
143 MatchRegOpType(unsigned OpIdx, std::string Ty)
144 : OpIdx(OpIdx), Ty(Ty) {}
148 virtual void emit(raw_ostream &OS) const {
149 OS << "MRI.getType(I.getOperand(" << OpIdx << ").getReg()) == (" << Ty
154 struct MatchRegOpBank : public Matcher {
155 MatchRegOpBank(unsigned OpIdx, const CodeGenRegisterClass &RC)
156 : OpIdx(OpIdx), RC(RC) {}
158 const CodeGenRegisterClass &RC;
160 virtual void emit(raw_ostream &OS) const {
161 OS << "(&RBI.getRegBankFromRegClass(" << RC.getQualifiedName()
162 << "RegClass) == RBI.getRegBank(I.getOperand(" << OpIdx
163 << ").getReg(), MRI, TRI))";
167 struct MatchMBBOp : public Matcher {
168 MatchMBBOp(unsigned OpIdx) : OpIdx(OpIdx) {}
171 virtual void emit(raw_ostream &OS) const {
172 OS << "I.getOperand(" << OpIdx << ").isMBB()";
176 struct MutateOpcode : public MatchAction {
177 MutateOpcode(const CodeGenInstruction *I) : I(I) {}
178 const CodeGenInstruction *I;
180 virtual void emit(raw_ostream &OS) const {
181 OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName()
186 class MatcherEmitter {
187 const PatternToMatch &P;
190 std::vector<std::unique_ptr<Matcher>> Matchers;
191 std::vector<std::unique_ptr<MatchAction>> Actions;
193 MatcherEmitter(const PatternToMatch &P) : P(P) {}
195 void emit(raw_ostream &OS) {
196 if (Matchers.empty())
197 llvm_unreachable("Unexpected empty matcher!");
199 OS << " // Src: " << *P.getSrcPattern() << "\n"
200 << " // Dst: " << *P.getDstPattern() << "\n";
202 OS << " if ((" << *Matchers.front() << ")";
203 for (auto &MA : makeArrayRef(Matchers).drop_front())
204 OS << " &&\n (" << *MA << ")";
207 for (auto &MA : Actions)
208 OS << " " << *MA << "\n";
210 OS << " constrainSelectedInstRegOperands(I, TII, TRI, RBI);\n";
211 OS << " return true;\n";
216 //===- GlobalISelEmitter class --------------------------------------------===//
218 void GlobalISelEmitter::gatherNodeEquivs() {
219 assert(NodeEquivs.empty());
220 for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv"))
221 NodeEquivs[Equiv->getValueAsDef("Node")] =
222 &Target.getInstruction(Equiv->getValueAsDef("I"));
225 const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) {
226 return NodeEquivs.lookup(N);
229 GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK)
230 : RK(RK), CGP(RK), Target(CGP.getTargetInfo()) {}
232 //===- Emitter ------------------------------------------------------------===//
234 Optional<GlobalISelEmitter::SkipReason>
235 GlobalISelEmitter::runOnPattern(const PatternToMatch &P, raw_ostream &OS) {
237 // Keep track of the matchers and actions to emit.
240 // First, analyze the whole pattern.
241 // If the entire pattern has a predicate (e.g., target features), ignore it.
242 if (!P.getPredicates()->getValues().empty())
243 return SkipReason{"Pattern has a predicate"};
245 // Physreg imp-defs require additional logic. Ignore the pattern.
246 if (!P.getDstRegs().empty())
247 return SkipReason{"Pattern defines a physical register"};
249 // Next, analyze the pattern operators.
250 TreePatternNode *Src = P.getSrcPattern();
251 TreePatternNode *Dst = P.getDstPattern();
253 // If the root of either pattern isn't a simple operator, ignore it.
254 if (!isTrivialOperatorNode(Dst))
255 return SkipReason{"Dst pattern root isn't a trivial operator"};
256 if (!isTrivialOperatorNode(Src))
257 return SkipReason{"Src pattern root isn't a trivial operator"};
259 Record *DstOp = Dst->getOperator();
260 if (!DstOp->isSubClassOf("Instruction"))
261 return SkipReason{"Pattern operator isn't an instruction"};
263 auto &DstI = Target.getInstruction(DstOp);
265 auto SrcGIOrNull = findNodeEquiv(Src->getOperator());
267 return SkipReason{"Pattern operator lacks an equivalent Instruction"};
268 auto &SrcGI = *SrcGIOrNull;
270 // The operators look good: match the opcode and mutate it to the new one.
271 M.Matchers.emplace_back(new MatchOpcode(&SrcGI));
272 M.Actions.emplace_back(new MutateOpcode(&DstI));
274 // Next, analyze the children, only accepting patterns that don't require
275 // any change to operands.
276 if (Src->getNumChildren() != Dst->getNumChildren())
277 return SkipReason{"Src/dst patterns have a different # of children"};
281 // Start with the defined operands (i.e., the results of the root operator).
282 if (DstI.Operands.NumDefs != Src->getExtTypes().size())
283 return SkipReason{"Src pattern results and dst MI defs are different"};
285 for (const EEVT::TypeSet &Ty : Src->getExtTypes()) {
286 Record *DstIOpRec = DstI.Operands[OpIdx].Rec;
287 if (!DstIOpRec->isSubClassOf("RegisterClass"))
288 return SkipReason{"Dst MI def isn't a register class"};
290 auto OpTyOrNone = MVTToLLT(Ty.getConcrete());
292 return SkipReason{"Dst operand has an unsupported type"};
294 M.Matchers.emplace_back(new MatchRegOpType(OpIdx, *OpTyOrNone));
295 M.Matchers.emplace_back(
296 new MatchRegOpBank(OpIdx, Target.getRegisterClass(DstIOpRec)));
300 // Finally match the used operands (i.e., the children of the root operator).
301 for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) {
302 auto *SrcChild = Src->getChild(i);
303 auto *DstChild = Dst->getChild(i);
305 // Patterns can reorder operands. Ignore those for now.
306 if (SrcChild->getName() != DstChild->getName())
307 return SkipReason{"Src/dst pattern children not in same order"};
309 // The only non-leaf child we accept is 'bb': it's an operator because
310 // BasicBlockSDNode isn't inline, but in MI it's just another operand.
311 if (!SrcChild->isLeaf()) {
312 if (DstChild->isLeaf() ||
313 SrcChild->getOperator() != DstChild->getOperator())
314 return SkipReason{"Src/dst pattern child operator mismatch"};
316 if (SrcChild->getOperator()->isSubClassOf("SDNode")) {
317 auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator());
318 if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") {
319 M.Matchers.emplace_back(new MatchMBBOp(OpIdx++));
323 return SkipReason{"Src pattern child isn't a leaf node"};
326 if (SrcChild->getLeafValue() != DstChild->getLeafValue())
327 return SkipReason{"Src/dst pattern child leaf mismatch"};
329 // Otherwise, we're looking for a bog-standard RegisterClass operand.
330 if (SrcChild->hasAnyPredicate())
331 return SkipReason{"Src pattern child has predicate"};
332 auto *ChildRec = cast<DefInit>(SrcChild->getLeafValue())->getDef();
333 if (!ChildRec->isSubClassOf("RegisterClass"))
334 return SkipReason{"Src pattern child isn't a RegisterClass"};
336 ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes();
337 if (ChildTypes.size() != 1)
338 return SkipReason{"Src pattern child has multiple results"};
340 auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete());
342 return SkipReason{"Src operand has an unsupported type"};
344 M.Matchers.emplace_back(new MatchRegOpType(OpIdx, *OpTyOrNone));
345 M.Matchers.emplace_back(
346 new MatchRegOpBank(OpIdx, Target.getRegisterClass(ChildRec)));
350 // We're done with this pattern! Emit the processed result.
356 void GlobalISelEmitter::run(raw_ostream &OS) {
357 // Track the GINodeEquiv definitions.
360 emitSourceFileHeader(("Global Instruction Selector for the " +
361 Target.getName() + " target").str(), OS);
362 OS << "bool " << Target.getName()
363 << "InstructionSelector::selectImpl"
364 "(MachineInstr &I) const {\n const MachineRegisterInfo &MRI = "
365 "I.getParent()->getParent()->getRegInfo();\n";
367 // Look through the SelectionDAG patterns we found, possibly emitting some.
368 for (const PatternToMatch &Pat : CGP.ptms()) {
370 if (auto SkipReason = runOnPattern(Pat, OS)) {
371 if (WarnOnSkippedPatterns) {
372 PrintWarning(Pat.getSrcRecord()->getLoc(),
373 "Skipped pattern: " + SkipReason->Reason);
379 OS << " return false;\n}\n";
382 //===----------------------------------------------------------------------===//
385 void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) {
386 GlobalISelEmitter(RK).run(OS);
388 } // End llvm namespace