Index: llvm/trunk/include/llvm/Target/Target.td =================================================================== --- llvm/trunk/include/llvm/Target/Target.td +++ llvm/trunk/include/llvm/Target/Target.td @@ -1340,3 +1340,8 @@ // Pull in the common support for DAG isel generation. // include "llvm/Target/TargetSelectionDAG.td" + +//===----------------------------------------------------------------------===// +// Pull in the common support for Global ISel generation. +// +include "llvm/Target/TargetGlobalISel.td" Index: llvm/trunk/include/llvm/Target/TargetGlobalISel.td =================================================================== --- llvm/trunk/include/llvm/Target/TargetGlobalISel.td +++ llvm/trunk/include/llvm/Target/TargetGlobalISel.td @@ -0,0 +1,29 @@ +//===- TargetGlobalISel.td - Common code for GlobalISel ----*- tablegen -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the target-independent interfaces used to support +// SelectionDAG instruction selection patterns (specified in +// TargetSelectionDAG.td) when generating GlobalISel instruction selectors. +// +// This is intended as a compatibility layer, to enable reuse of target +// descriptions written for SelectionDAG without requiring explicit GlobalISel +// support. It will eventually supersede SelectionDAG patterns. +// +//===----------------------------------------------------------------------===// + +// Declare that a generic Instruction is 'equivalent' to an SDNode, that is, +// SelectionDAG patterns involving the SDNode can be transformed to match the +// Instruction instead. +class GINodeEquiv { + Instruction I = i; + SDNode Node = node; +} + +def : GINodeEquiv; +def : GINodeEquiv; Index: llvm/trunk/lib/Target/AArch64/AArch64InstructionSelector.h =================================================================== --- llvm/trunk/lib/Target/AArch64/AArch64InstructionSelector.h +++ llvm/trunk/lib/Target/AArch64/AArch64InstructionSelector.h @@ -32,6 +32,10 @@ virtual bool select(MachineInstr &I) const override; private: + /// tblgen-erated 'select' implementation, used as the initial selector for + /// the patterns that don't require complex C++. + bool selectImpl(MachineInstr &I) const; + const AArch64TargetMachine &TM; const AArch64Subtarget &STI; const AArch64InstrInfo &TII; Index: llvm/trunk/lib/Target/AArch64/AArch64InstructionSelector.cpp =================================================================== --- llvm/trunk/lib/Target/AArch64/AArch64InstructionSelector.cpp +++ llvm/trunk/lib/Target/AArch64/AArch64InstructionSelector.cpp @@ -36,6 +36,8 @@ #error "You shouldn't build this" #endif +#include "AArch64GenGlobalISel.inc" + AArch64InstructionSelector::AArch64InstructionSelector( const AArch64TargetMachine &TM, const AArch64Subtarget &STI, const AArch64RegisterBankInfo &RBI) @@ -139,6 +141,7 @@ case TargetOpcode::G_AND: return AArch64::ANDWrr; case TargetOpcode::G_ADD: + assert(OpSize != 32 && "s32 G_ADD should have been selected"); return AArch64::ADDWrr; case TargetOpcode::G_SUB: return AArch64::SUBWrr; @@ -163,7 +166,6 @@ return AArch64::EORXrr; case TargetOpcode::G_AND: return AArch64::ANDXrr; - case TargetOpcode::G_ADD: case TargetOpcode::G_GEP: return AArch64::ADDXrr; case TargetOpcode::G_SUB: @@ -527,15 +529,13 @@ return false; } + if (selectImpl(I)) + return true; + LLT Ty = I.getOperand(0).isReg() ? MRI.getType(I.getOperand(0).getReg()) : LLT{}; switch (Opcode) { - case TargetOpcode::G_BR: { - I.setDesc(TII.get(AArch64::B)); - return true; - } - case TargetOpcode::G_BRCOND: { if (Ty.getSizeInBits() > 32) { // We shouldn't need this on AArch64, but it would be implemented as an Index: llvm/trunk/lib/Target/AArch64/CMakeLists.txt =================================================================== --- llvm/trunk/lib/Target/AArch64/CMakeLists.txt +++ llvm/trunk/lib/Target/AArch64/CMakeLists.txt @@ -13,6 +13,9 @@ tablegen(LLVM AArch64GenSubtargetInfo.inc -gen-subtarget) tablegen(LLVM AArch64GenDisassemblerTables.inc -gen-disassembler) tablegen(LLVM AArch64GenSystemOperands.inc -gen-searchable-tables) +if(LLVM_BUILD_GLOBAL_ISEL) + tablegen(LLVM AArch64GenGlobalISel.inc -gen-global-isel) +endif() add_public_tablegen_target(AArch64CommonTableGen) Index: llvm/trunk/utils/TableGen/CMakeLists.txt =================================================================== --- llvm/trunk/utils/TableGen/CMakeLists.txt +++ llvm/trunk/utils/TableGen/CMakeLists.txt @@ -22,6 +22,7 @@ DisassemblerEmitter.cpp FastISelEmitter.cpp FixedLenDecoderEmitter.cpp + GlobalISelEmitter.cpp InstrInfoEmitter.cpp IntrinsicEmitter.cpp OptParserEmitter.cpp Index: llvm/trunk/utils/TableGen/CodeGenDAGPatterns.h =================================================================== --- llvm/trunk/utils/TableGen/CodeGenDAGPatterns.h +++ llvm/trunk/utils/TableGen/CodeGenDAGPatterns.h @@ -809,11 +809,13 @@ LessRecordByID>::const_iterator pf_iterator; pf_iterator pf_begin() const { return PatternFragments.begin(); } pf_iterator pf_end() const { return PatternFragments.end(); } + iterator_range ptfs() const { return PatternFragments; } // Patterns to match information. typedef std::vector::const_iterator ptm_iterator; ptm_iterator ptm_begin() const { return PatternsToMatch.begin(); } ptm_iterator ptm_end() const { return PatternsToMatch.end(); } + iterator_range ptms() const { return PatternsToMatch; } /// Parse the Pattern for an instruction, and insert the result in DAGInsts. typedef std::map DAGInstMap; Index: llvm/trunk/utils/TableGen/GlobalISelEmitter.cpp =================================================================== --- llvm/trunk/utils/TableGen/GlobalISelEmitter.cpp +++ llvm/trunk/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 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 +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 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 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 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 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> Matchers; + std::vector> 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::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(SrcChild->getLeafValue())->getDef(); + if (!ChildRec->isSubClassOf("RegisterClass")) + return SkipReason{"Src pattern child isn't a RegisterClass"}; + + ArrayRef 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 Index: llvm/trunk/utils/TableGen/TableGen.cpp =================================================================== --- llvm/trunk/utils/TableGen/TableGen.cpp +++ llvm/trunk/utils/TableGen/TableGen.cpp @@ -45,6 +45,7 @@ GenCTags, GenAttributes, GenSearchableTables, + GenGlobalISel, }; namespace { @@ -91,7 +92,9 @@ clEnumValN(GenAttributes, "gen-attrs", "Generate attributes"), clEnumValN(GenSearchableTables, "gen-searchable-tables", - "Generate generic binary-searchable table"))); + "Generate generic binary-searchable table"), + clEnumValN(GenGlobalISel, "gen-global-isel", + "Generate GlobalISel selector"))); cl::opt Class("class", cl::desc("Print Enum list for this class"), @@ -177,6 +180,9 @@ case GenSearchableTables: EmitSearchableTables(Records, OS); break; + case GenGlobalISel: + EmitGlobalISel(Records, OS); + break; } return false; Index: llvm/trunk/utils/TableGen/TableGenBackends.h =================================================================== --- llvm/trunk/utils/TableGen/TableGenBackends.h +++ llvm/trunk/utils/TableGen/TableGenBackends.h @@ -80,6 +80,7 @@ void EmitCTags(RecordKeeper &RK, raw_ostream &OS); void EmitAttributes(RecordKeeper &RK, raw_ostream &OS); void EmitSearchableTables(RecordKeeper &RK, raw_ostream &OS); +void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS); } // End llvm namespace