diff options
Diffstat (limited to 'contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp')
| -rw-r--r-- | contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp | 388 |
1 files changed, 388 insertions, 0 deletions
diff --git a/contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp b/contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp new file mode 100644 index 0000000..2bc6181 --- /dev/null +++ b/contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp @@ -0,0 +1,388 @@ +//===- GlobalISelEmitter.cpp - Generate an instruction selector -----------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// \file +/// This tablegen backend emits code for use by the GlobalISel instruction +/// selector. See include/llvm/CodeGen/TargetGlobalISel.td. +/// +/// This file analyzes the patterns recognized by the SelectionDAGISel tablegen +/// backend, filters out the ones that are unsupported, maps +/// SelectionDAG-specific constructs to their GlobalISel counterpart +/// (when applicable: MVT to LLT; SDNode to generic Instruction). +/// +/// Not all patterns are supported: pass the tablegen invocation +/// "-warn-on-skipped-patterns" to emit a warning when a pattern is skipped, +/// as well as why. +/// +/// The generated file defines a single method: +/// bool <Target>InstructionSelector::selectImpl(MachineInstr &I) const; +/// intended to be used in InstructionSelector::select as the first-step +/// selector for the patterns that don't require complex C++. +/// +/// FIXME: We'll probably want to eventually define a base +/// "TargetGenInstructionSelector" class. +/// +//===----------------------------------------------------------------------===// + +#include "CodeGenDAGPatterns.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/MachineValueType.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/TableGen/Error.h" +#include "llvm/TableGen/Record.h" +#include "llvm/TableGen/TableGenBackend.h" +#include <string> +using namespace llvm; + +#define DEBUG_TYPE "gisel-emitter" + +STATISTIC(NumPatternTotal, "Total number of patterns"); +STATISTIC(NumPatternSkipped, "Number of patterns skipped"); +STATISTIC(NumPatternEmitted, "Number of patterns emitted"); + +static cl::opt<bool> WarnOnSkippedPatterns( + "warn-on-skipped-patterns", + cl::desc("Explain why a pattern was skipped for inclusion " + "in the GlobalISel selector"), + cl::init(false)); + +namespace { + +class GlobalISelEmitter { +public: + explicit GlobalISelEmitter(RecordKeeper &RK); + void run(raw_ostream &OS); + +private: + const RecordKeeper &RK; + const CodeGenDAGPatterns CGP; + const CodeGenTarget &Target; + + /// Keep track of the equivalence between SDNodes and Instruction. + /// This is defined using 'GINodeEquiv' in the target description. + DenseMap<Record *, const CodeGenInstruction *> NodeEquivs; + + void gatherNodeEquivs(); + const CodeGenInstruction *findNodeEquiv(Record *N); + + struct SkipReason { + std::string Reason; + }; + + /// Analyze pattern \p P, possibly emitting matching code for it to \p OS. + /// Otherwise, return a reason why this pattern was skipped for emission. + Optional<SkipReason> runOnPattern(const PatternToMatch &P, + raw_ostream &OS); +}; + +} // end anonymous namespace + +//===- Helper functions ---------------------------------------------------===// + +/// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for +/// MVTs that don't map cleanly to an LLT (e.g., iPTR, *any, ...). +static Optional<std::string> MVTToLLT(MVT::SimpleValueType SVT) { + std::string TyStr; + raw_string_ostream OS(TyStr); + MVT VT(SVT); + if (VT.isVector() && VT.getVectorNumElements() != 1) { + OS << "LLT::vector(" << VT.getVectorNumElements() << ", " + << VT.getScalarSizeInBits() << ")"; + } else if (VT.isInteger() || VT.isFloatingPoint()) { + OS << "LLT::scalar(" << VT.getSizeInBits() << ")"; + } else { + return None; + } + OS.flush(); + return TyStr; +} + +static bool isTrivialOperatorNode(const TreePatternNode *N) { + return !N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn(); +} + +//===- Matchers -----------------------------------------------------------===// + +struct Matcher { + virtual ~Matcher() {} + virtual void emit(raw_ostream &OS) const = 0; +}; + +raw_ostream &operator<<(raw_ostream &S, const Matcher &M) { + M.emit(S); + return S; +} + +struct MatchAction { + virtual ~MatchAction() {} + virtual void emit(raw_ostream &OS) const = 0; +}; + +raw_ostream &operator<<(raw_ostream &S, const MatchAction &A) { + A.emit(S); + return S; +} + +struct MatchOpcode : public Matcher { + MatchOpcode(const CodeGenInstruction *I) : I(I) {} + const CodeGenInstruction *I; + + virtual void emit(raw_ostream &OS) const { + OS << "I.getOpcode() == " << I->Namespace << "::" << I->TheDef->getName(); + } +}; + +struct MatchRegOpType : public Matcher { + MatchRegOpType(unsigned OpIdx, std::string Ty) + : OpIdx(OpIdx), Ty(Ty) {} + unsigned OpIdx; + std::string Ty; + + virtual void emit(raw_ostream &OS) const { + OS << "MRI.getType(I.getOperand(" << OpIdx << ").getReg()) == (" << Ty + << ")"; + } +}; + +struct MatchRegOpBank : public Matcher { + MatchRegOpBank(unsigned OpIdx, const CodeGenRegisterClass &RC) + : OpIdx(OpIdx), RC(RC) {} + unsigned OpIdx; + const CodeGenRegisterClass &RC; + + virtual void emit(raw_ostream &OS) const { + OS << "(&RBI.getRegBankFromRegClass(" << RC.getQualifiedName() + << "RegClass) == RBI.getRegBank(I.getOperand(" << OpIdx + << ").getReg(), MRI, TRI))"; + } +}; + +struct MatchMBBOp : public Matcher { + MatchMBBOp(unsigned OpIdx) : OpIdx(OpIdx) {} + unsigned OpIdx; + + virtual void emit(raw_ostream &OS) const { + OS << "I.getOperand(" << OpIdx << ").isMBB()"; + } +}; + +struct MutateOpcode : public MatchAction { + MutateOpcode(const CodeGenInstruction *I) : I(I) {} + const CodeGenInstruction *I; + + virtual void emit(raw_ostream &OS) const { + OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName() + << "));"; + } +}; + +class MatcherEmitter { + const PatternToMatch &P; + +public: + std::vector<std::unique_ptr<Matcher>> Matchers; + std::vector<std::unique_ptr<MatchAction>> Actions; + + MatcherEmitter(const PatternToMatch &P) : P(P) {} + + void emit(raw_ostream &OS) { + if (Matchers.empty()) + llvm_unreachable("Unexpected empty matcher!"); + + OS << " // Src: " << *P.getSrcPattern() << "\n" + << " // Dst: " << *P.getDstPattern() << "\n"; + + OS << " if ((" << *Matchers.front() << ")"; + for (auto &MA : makeArrayRef(Matchers).drop_front()) + OS << " &&\n (" << *MA << ")"; + OS << ") {\n"; + + for (auto &MA : Actions) + OS << " " << *MA << "\n"; + + OS << " constrainSelectedInstRegOperands(I, TII, TRI, RBI);\n"; + OS << " return true;\n"; + OS << " }\n"; + } +}; + +//===- GlobalISelEmitter class --------------------------------------------===// + +void GlobalISelEmitter::gatherNodeEquivs() { + assert(NodeEquivs.empty()); + for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv")) + NodeEquivs[Equiv->getValueAsDef("Node")] = + &Target.getInstruction(Equiv->getValueAsDef("I")); +} + +const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) { + return NodeEquivs.lookup(N); +} + +GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK) + : RK(RK), CGP(RK), Target(CGP.getTargetInfo()) {} + +//===- Emitter ------------------------------------------------------------===// + +Optional<GlobalISelEmitter::SkipReason> +GlobalISelEmitter::runOnPattern(const PatternToMatch &P, raw_ostream &OS) { + + // Keep track of the matchers and actions to emit. + MatcherEmitter M(P); + + // First, analyze the whole pattern. + // If the entire pattern has a predicate (e.g., target features), ignore it. + if (!P.getPredicates()->getValues().empty()) + return SkipReason{"Pattern has a predicate"}; + + // Physreg imp-defs require additional logic. Ignore the pattern. + if (!P.getDstRegs().empty()) + return SkipReason{"Pattern defines a physical register"}; + + // Next, analyze the pattern operators. + TreePatternNode *Src = P.getSrcPattern(); + TreePatternNode *Dst = P.getDstPattern(); + + // If the root of either pattern isn't a simple operator, ignore it. + if (!isTrivialOperatorNode(Dst)) + return SkipReason{"Dst pattern root isn't a trivial operator"}; + if (!isTrivialOperatorNode(Src)) + return SkipReason{"Src pattern root isn't a trivial operator"}; + + Record *DstOp = Dst->getOperator(); + if (!DstOp->isSubClassOf("Instruction")) + return SkipReason{"Pattern operator isn't an instruction"}; + + auto &DstI = Target.getInstruction(DstOp); + + auto SrcGIOrNull = findNodeEquiv(Src->getOperator()); + if (!SrcGIOrNull) + return SkipReason{"Pattern operator lacks an equivalent Instruction"}; + auto &SrcGI = *SrcGIOrNull; + + // The operators look good: match the opcode and mutate it to the new one. + M.Matchers.emplace_back(new MatchOpcode(&SrcGI)); + M.Actions.emplace_back(new MutateOpcode(&DstI)); + + // Next, analyze the children, only accepting patterns that don't require + // any change to operands. + if (Src->getNumChildren() != Dst->getNumChildren()) + return SkipReason{"Src/dst patterns have a different # of children"}; + + unsigned OpIdx = 0; + + // Start with the defined operands (i.e., the results of the root operator). + if (DstI.Operands.NumDefs != Src->getExtTypes().size()) + return SkipReason{"Src pattern results and dst MI defs are different"}; + + for (const EEVT::TypeSet &Ty : Src->getExtTypes()) { + Record *DstIOpRec = DstI.Operands[OpIdx].Rec; + if (!DstIOpRec->isSubClassOf("RegisterClass")) + return SkipReason{"Dst MI def isn't a register class"}; + + auto OpTyOrNone = MVTToLLT(Ty.getConcrete()); + if (!OpTyOrNone) + return SkipReason{"Dst operand has an unsupported type"}; + + M.Matchers.emplace_back(new MatchRegOpType(OpIdx, *OpTyOrNone)); + M.Matchers.emplace_back( + new MatchRegOpBank(OpIdx, Target.getRegisterClass(DstIOpRec))); + ++OpIdx; + } + + // Finally match the used operands (i.e., the children of the root operator). + for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) { + auto *SrcChild = Src->getChild(i); + auto *DstChild = Dst->getChild(i); + + // Patterns can reorder operands. Ignore those for now. + if (SrcChild->getName() != DstChild->getName()) + return SkipReason{"Src/dst pattern children not in same order"}; + + // The only non-leaf child we accept is 'bb': it's an operator because + // BasicBlockSDNode isn't inline, but in MI it's just another operand. + if (!SrcChild->isLeaf()) { + if (DstChild->isLeaf() || + SrcChild->getOperator() != DstChild->getOperator()) + return SkipReason{"Src/dst pattern child operator mismatch"}; + + if (SrcChild->getOperator()->isSubClassOf("SDNode")) { + auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator()); + if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") { + M.Matchers.emplace_back(new MatchMBBOp(OpIdx++)); + continue; + } + } + return SkipReason{"Src pattern child isn't a leaf node"}; + } + + if (SrcChild->getLeafValue() != DstChild->getLeafValue()) + return SkipReason{"Src/dst pattern child leaf mismatch"}; + + // Otherwise, we're looking for a bog-standard RegisterClass operand. + if (SrcChild->hasAnyPredicate()) + return SkipReason{"Src pattern child has predicate"}; + auto *ChildRec = cast<DefInit>(SrcChild->getLeafValue())->getDef(); + if (!ChildRec->isSubClassOf("RegisterClass")) + return SkipReason{"Src pattern child isn't a RegisterClass"}; + + ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes(); + if (ChildTypes.size() != 1) + return SkipReason{"Src pattern child has multiple results"}; + + auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete()); + if (!OpTyOrNone) + return SkipReason{"Src operand has an unsupported type"}; + + M.Matchers.emplace_back(new MatchRegOpType(OpIdx, *OpTyOrNone)); + M.Matchers.emplace_back( + new MatchRegOpBank(OpIdx, Target.getRegisterClass(ChildRec))); + ++OpIdx; + } + + // We're done with this pattern! Emit the processed result. + M.emit(OS); + ++NumPatternEmitted; + return None; +} + +void GlobalISelEmitter::run(raw_ostream &OS) { + // Track the GINodeEquiv definitions. + gatherNodeEquivs(); + + emitSourceFileHeader(("Global Instruction Selector for the " + + Target.getName() + " target").str(), OS); + OS << "bool " << Target.getName() + << "InstructionSelector::selectImpl" + "(MachineInstr &I) const {\n const MachineRegisterInfo &MRI = " + "I.getParent()->getParent()->getRegInfo();\n"; + + // Look through the SelectionDAG patterns we found, possibly emitting some. + for (const PatternToMatch &Pat : CGP.ptms()) { + ++NumPatternTotal; + if (auto SkipReason = runOnPattern(Pat, OS)) { + if (WarnOnSkippedPatterns) { + PrintWarning(Pat.getSrcRecord()->getLoc(), + "Skipped pattern: " + SkipReason->Reason); + } + ++NumPatternSkipped; + } + } + + OS << " return false;\n}\n"; +} + +//===----------------------------------------------------------------------===// + +namespace llvm { +void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) { + GlobalISelEmitter(RK).run(OS); +} +} // End llvm namespace |
