| //===- 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 "SubtargetFeatureInfo.h" |
| #include "llvm/ADT/Optional.h" |
| #include "llvm/ADT/SmallSet.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/CodeGen/MachineValueType.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Error.h" |
| #include "llvm/Support/LowLevelTypeImpl.h" |
| #include "llvm/Support/ScopedPrinter.h" |
| #include "llvm/TableGen/Error.h" |
| #include "llvm/TableGen/Record.h" |
| #include "llvm/TableGen/TableGenBackend.h" |
| #include <string> |
| #include <numeric> |
| using namespace llvm; |
| |
| #define DEBUG_TYPE "gisel-emitter" |
| |
| STATISTIC(NumPatternTotal, "Total number of patterns"); |
| STATISTIC(NumPatternImported, "Number of patterns imported from SelectionDAG"); |
| STATISTIC(NumPatternImportsSkipped, "Number of SelectionDAG imports skipped"); |
| STATISTIC(NumPatternEmitted, "Number of patterns emitted"); |
| /// A unique identifier for a MatchTable. |
| static unsigned CurrentMatchTableID = 0; |
| |
| cl::OptionCategory GlobalISelEmitterCat("Options for -gen-global-isel"); |
| |
| 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), cl::cat(GlobalISelEmitterCat)); |
| |
| namespace { |
| //===- Helper functions ---------------------------------------------------===// |
| |
| /// This class stands in for LLT wherever we want to tablegen-erate an |
| /// equivalent at compiler run-time. |
| class LLTCodeGen { |
| private: |
| LLT Ty; |
| |
| public: |
| LLTCodeGen(const LLT &Ty) : Ty(Ty) {} |
| |
| void emitCxxEnumValue(raw_ostream &OS) const { |
| if (Ty.isScalar()) { |
| OS << "GILLT_s" << Ty.getSizeInBits(); |
| return; |
| } |
| if (Ty.isVector()) { |
| OS << "GILLT_v" << Ty.getNumElements() << "s" << Ty.getScalarSizeInBits(); |
| return; |
| } |
| llvm_unreachable("Unhandled LLT"); |
| } |
| |
| void emitCxxConstructorCall(raw_ostream &OS) const { |
| if (Ty.isScalar()) { |
| OS << "LLT::scalar(" << Ty.getSizeInBits() << ")"; |
| return; |
| } |
| if (Ty.isVector()) { |
| OS << "LLT::vector(" << Ty.getNumElements() << ", " |
| << Ty.getScalarSizeInBits() << ")"; |
| return; |
| } |
| llvm_unreachable("Unhandled LLT"); |
| } |
| |
| const LLT &get() const { return Ty; } |
| |
| /// This ordering is used for std::unique() and std::sort(). There's no |
| /// particular logic behind the order. |
| bool operator<(const LLTCodeGen &Other) const { |
| if (!Ty.isValid()) |
| return Other.Ty.isValid(); |
| if (Ty.isScalar()) { |
| if (!Other.Ty.isValid()) |
| return false; |
| if (Other.Ty.isScalar()) |
| return Ty.getSizeInBits() < Other.Ty.getSizeInBits(); |
| return false; |
| } |
| if (Ty.isVector()) { |
| if (!Other.Ty.isValid() || Other.Ty.isScalar()) |
| return false; |
| if (Other.Ty.isVector()) { |
| if (Ty.getNumElements() < Other.Ty.getNumElements()) |
| return true; |
| if (Ty.getNumElements() > Other.Ty.getNumElements()) |
| return false; |
| return Ty.getSizeInBits() < Other.Ty.getSizeInBits(); |
| } |
| return false; |
| } |
| llvm_unreachable("Unhandled LLT"); |
| } |
| }; |
| |
| class InstructionMatcher; |
| /// 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<LLTCodeGen> MVTToLLT(MVT::SimpleValueType SVT) { |
| MVT VT(SVT); |
| if (VT.isVector() && VT.getVectorNumElements() != 1) |
| return LLTCodeGen( |
| LLT::vector(VT.getVectorNumElements(), VT.getScalarSizeInBits())); |
| if (VT.isInteger() || VT.isFloatingPoint()) |
| return LLTCodeGen(LLT::scalar(VT.getSizeInBits())); |
| return None; |
| } |
| |
| static std::string explainPredicates(const TreePatternNode *N) { |
| std::string Explanation = ""; |
| StringRef Separator = ""; |
| for (const auto &P : N->getPredicateFns()) { |
| Explanation += |
| (Separator + P.getOrigPatFragRecord()->getRecord()->getName()).str(); |
| if (P.isAlwaysTrue()) |
| Explanation += " always-true"; |
| if (P.isImmediatePattern()) |
| Explanation += " immediate"; |
| } |
| return Explanation; |
| } |
| |
| std::string explainOperator(Record *Operator) { |
| if (Operator->isSubClassOf("SDNode")) |
| return (" (" + Operator->getValueAsString("Opcode") + ")").str(); |
| |
| if (Operator->isSubClassOf("Intrinsic")) |
| return (" (Operator is an Intrinsic, " + Operator->getName() + ")").str(); |
| |
| return " (Operator not understood)"; |
| } |
| |
| /// Helper function to let the emitter report skip reason error messages. |
| static Error failedImport(const Twine &Reason) { |
| return make_error<StringError>(Reason, inconvertibleErrorCode()); |
| } |
| |
| static Error isTrivialOperatorNode(const TreePatternNode *N) { |
| std::string Explanation = ""; |
| std::string Separator = ""; |
| if (N->isLeaf()) { |
| if (isa<IntInit>(N->getLeafValue())) |
| return Error::success(); |
| |
| Explanation = "Is a leaf"; |
| Separator = ", "; |
| } |
| |
| if (N->hasAnyPredicate()) { |
| Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")"; |
| Separator = ", "; |
| } |
| |
| if (N->getTransformFn()) { |
| Explanation += Separator + "Has a transform function"; |
| Separator = ", "; |
| } |
| |
| if (!N->isLeaf() && !N->hasAnyPredicate() && !N->getTransformFn()) |
| return Error::success(); |
| |
| return failedImport(Explanation); |
| } |
| |
| static Record *getInitValueAsRegClass(Init *V) { |
| if (DefInit *VDefInit = dyn_cast<DefInit>(V)) { |
| if (VDefInit->getDef()->isSubClassOf("RegisterOperand")) |
| return VDefInit->getDef()->getValueAsDef("RegClass"); |
| if (VDefInit->getDef()->isSubClassOf("RegisterClass")) |
| return VDefInit->getDef(); |
| } |
| return nullptr; |
| } |
| |
| std::string |
| getNameForFeatureBitset(const std::vector<Record *> &FeatureBitset) { |
| std::string Name = "GIFBS"; |
| for (const auto &Feature : FeatureBitset) |
| Name += ("_" + Feature->getName()).str(); |
| return Name; |
| } |
| //===- Matchers -----------------------------------------------------------===// |
| |
| class OperandMatcher; |
| class MatchAction; |
| |
| /// Generates code to check that a match rule matches. |
| class RuleMatcher { |
| /// A list of matchers that all need to succeed for the current rule to match. |
| /// FIXME: This currently supports a single match position but could be |
| /// extended to support multiple positions to support div/rem fusion or |
| /// load-multiple instructions. |
| std::vector<std::unique_ptr<InstructionMatcher>> Matchers; |
| |
| /// A list of actions that need to be taken when all predicates in this rule |
| /// have succeeded. |
| std::vector<std::unique_ptr<MatchAction>> Actions; |
| |
| /// A map of instruction matchers to the local variables created by |
| /// emitCaptureOpcodes(). |
| std::map<const InstructionMatcher *, unsigned> InsnVariableIDs; |
| |
| /// ID for the next instruction variable defined with defineInsnVar() |
| unsigned NextInsnVarID; |
| |
| std::vector<Record *> RequiredFeatures; |
| |
| public: |
| RuleMatcher() |
| : Matchers(), Actions(), InsnVariableIDs(), NextInsnVarID(0) {} |
| RuleMatcher(RuleMatcher &&Other) = default; |
| RuleMatcher &operator=(RuleMatcher &&Other) = default; |
| |
| InstructionMatcher &addInstructionMatcher(); |
| void addRequiredFeature(Record *Feature); |
| const std::vector<Record *> &getRequiredFeatures() const; |
| |
| template <class Kind, class... Args> Kind &addAction(Args &&... args); |
| |
| /// Define an instruction without emitting any code to do so. |
| /// This is used for the root of the match. |
| unsigned implicitlyDefineInsnVar(const InstructionMatcher &Matcher); |
| /// Define an instruction and emit corresponding state-machine opcodes. |
| unsigned defineInsnVar(raw_ostream &OS, const InstructionMatcher &Matcher, |
| unsigned InsnVarID, unsigned OpIdx); |
| unsigned getInsnVarID(const InstructionMatcher &InsnMatcher) const; |
| |
| void emitCaptureOpcodes(raw_ostream &OS); |
| |
| void emit(raw_ostream &OS); |
| |
| /// Compare the priority of this object and B. |
| /// |
| /// Returns true if this object is more important than B. |
| bool isHigherPriorityThan(const RuleMatcher &B) const; |
| |
| /// Report the maximum number of temporary operands needed by the rule |
| /// matcher. |
| unsigned countRendererFns() const; |
| |
| // FIXME: Remove this as soon as possible |
| InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); } |
| }; |
| |
| template <class PredicateTy> class PredicateListMatcher { |
| private: |
| typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec; |
| PredicateVec Predicates; |
| |
| public: |
| /// Construct a new operand predicate and add it to the matcher. |
| template <class Kind, class... Args> |
| Kind &addPredicate(Args&&... args) { |
| Predicates.emplace_back( |
| llvm::make_unique<Kind>(std::forward<Args>(args)...)); |
| return *static_cast<Kind *>(Predicates.back().get()); |
| } |
| |
| typename PredicateVec::const_iterator predicates_begin() const { |
| return Predicates.begin(); |
| } |
| typename PredicateVec::const_iterator predicates_end() const { |
| return Predicates.end(); |
| } |
| iterator_range<typename PredicateVec::const_iterator> predicates() const { |
| return make_range(predicates_begin(), predicates_end()); |
| } |
| typename PredicateVec::size_type predicates_size() const { |
| return Predicates.size(); |
| } |
| |
| /// Emit MatchTable opcodes that tests whether all the predicates are met. |
| template <class... Args> |
| void emitPredicateListOpcodes(raw_ostream &OS, Args &&... args) const { |
| if (Predicates.empty()) { |
| OS << "// No predicates\n"; |
| return; |
| } |
| |
| for (const auto &Predicate : predicates()) |
| Predicate->emitPredicateOpcodes(OS, std::forward<Args>(args)...); |
| } |
| }; |
| |
| /// Generates code to check a predicate of an operand. |
| /// |
| /// Typical predicates include: |
| /// * Operand is a particular register. |
| /// * Operand is assigned a particular register bank. |
| /// * Operand is an MBB. |
| class OperandPredicateMatcher { |
| public: |
| /// This enum is used for RTTI and also defines the priority that is given to |
| /// the predicate when generating the matcher code. Kinds with higher priority |
| /// must be tested first. |
| /// |
| /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter |
| /// but OPM_Int must have priority over OPM_RegBank since constant integers |
| /// are represented by a virtual register defined by a G_CONSTANT instruction. |
| enum PredicateKind { |
| OPM_ComplexPattern, |
| OPM_Instruction, |
| OPM_IntrinsicID, |
| OPM_Int, |
| OPM_LiteralInt, |
| OPM_LLT, |
| OPM_RegBank, |
| OPM_MBB, |
| }; |
| |
| protected: |
| PredicateKind Kind; |
| |
| public: |
| OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {} |
| virtual ~OperandPredicateMatcher() {} |
| |
| PredicateKind getKind() const { return Kind; } |
| |
| /// Return the OperandMatcher for the specified operand or nullptr if there |
| /// isn't one by that name in this operand predicate matcher. |
| /// |
| /// InstructionOperandMatcher is the only subclass that can return non-null |
| /// for this. |
| virtual Optional<const OperandMatcher *> |
| getOptionalOperand(StringRef SymbolicName) const { |
| assert(!SymbolicName.empty() && "Cannot lookup unnamed operand"); |
| return None; |
| } |
| |
| /// Emit MatchTable opcodes to capture instructions into the MIs table. |
| /// |
| /// Only InstructionOperandMatcher needs to do anything for this method the |
| /// rest just walk the tree. |
| virtual void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID, unsigned OpIdx) const {} |
| |
| /// Emit MatchTable opcodes that check the predicate for the given operand. |
| virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID, |
| unsigned OpIdx) const = 0; |
| |
| /// Compare the priority of this object and B. |
| /// |
| /// Returns true if this object is more important than B. |
| virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const { |
| return Kind < B.Kind; |
| }; |
| |
| /// Report the maximum number of temporary operands needed by the predicate |
| /// matcher. |
| virtual unsigned countRendererFns() const { return 0; } |
| }; |
| |
| /// Generates code to check that an operand is a particular LLT. |
| class LLTOperandMatcher : public OperandPredicateMatcher { |
| protected: |
| LLTCodeGen Ty; |
| |
| public: |
| LLTOperandMatcher(const LLTCodeGen &Ty) |
| : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {} |
| |
| static bool classof(const OperandPredicateMatcher *P) { |
| return P->getKind() == OPM_LLT; |
| } |
| |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID, unsigned OpIdx) const override { |
| OS << " GIM_CheckType, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx |
| << ", /*Type*/"; |
| Ty.emitCxxEnumValue(OS); |
| OS << ", \n"; |
| } |
| }; |
| |
| /// Generates code to check that an operand is a particular target constant. |
| class ComplexPatternOperandMatcher : public OperandPredicateMatcher { |
| protected: |
| const OperandMatcher &Operand; |
| const Record &TheDef; |
| |
| unsigned getAllocatedTemporariesBaseID() const; |
| |
| public: |
| ComplexPatternOperandMatcher(const OperandMatcher &Operand, |
| const Record &TheDef) |
| : OperandPredicateMatcher(OPM_ComplexPattern), Operand(Operand), |
| TheDef(TheDef) {} |
| |
| static bool classof(const OperandPredicateMatcher *P) { |
| return P->getKind() == OPM_ComplexPattern; |
| } |
| |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID, unsigned OpIdx) const override { |
| unsigned ID = getAllocatedTemporariesBaseID(); |
| OS << " GIM_CheckComplexPattern, /*MI*/" << InsnVarID << ", /*Op*/" |
| << OpIdx << ", /*Renderer*/" << ID << ", GICP_" |
| << TheDef.getName() << ",\n"; |
| } |
| |
| unsigned countRendererFns() const override { |
| return 1; |
| } |
| }; |
| |
| /// Generates code to check that an operand is in a particular register bank. |
| class RegisterBankOperandMatcher : public OperandPredicateMatcher { |
| protected: |
| const CodeGenRegisterClass &RC; |
| |
| public: |
| RegisterBankOperandMatcher(const CodeGenRegisterClass &RC) |
| : OperandPredicateMatcher(OPM_RegBank), RC(RC) {} |
| |
| static bool classof(const OperandPredicateMatcher *P) { |
| return P->getKind() == OPM_RegBank; |
| } |
| |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID, unsigned OpIdx) const override { |
| OS << " GIM_CheckRegBankForClass, /*MI*/" << InsnVarID << ", /*Op*/" |
| << OpIdx << ", /*RC*/" << RC.getQualifiedName() << "RegClassID,\n"; |
| } |
| }; |
| |
| /// Generates code to check that an operand is a basic block. |
| class MBBOperandMatcher : public OperandPredicateMatcher { |
| public: |
| MBBOperandMatcher() : OperandPredicateMatcher(OPM_MBB) {} |
| |
| static bool classof(const OperandPredicateMatcher *P) { |
| return P->getKind() == OPM_MBB; |
| } |
| |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID, unsigned OpIdx) const override { |
| OS << " GIM_CheckIsMBB, /*MI*/" << InsnVarID << ", /*Op*/" << OpIdx << ",\n"; |
| } |
| }; |
| |
| /// Generates code to check that an operand is a G_CONSTANT with a particular |
| /// int. |
| class ConstantIntOperandMatcher : public OperandPredicateMatcher { |
| protected: |
| int64_t Value; |
| |
| public: |
| ConstantIntOperandMatcher(int64_t Value) |
| : OperandPredicateMatcher(OPM_Int), Value(Value) {} |
| |
| static bool classof(const OperandPredicateMatcher *P) { |
| return P->getKind() == OPM_Int; |
| } |
| |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID, unsigned OpIdx) const override { |
| OS << " GIM_CheckConstantInt, /*MI*/" << InsnVarID << ", /*Op*/" |
| << OpIdx << ", " << Value << ",\n"; |
| } |
| }; |
| |
| /// Generates code to check that an operand is a raw int (where MO.isImm() or |
| /// MO.isCImm() is true). |
| class LiteralIntOperandMatcher : public OperandPredicateMatcher { |
| protected: |
| int64_t Value; |
| |
| public: |
| LiteralIntOperandMatcher(int64_t Value) |
| : OperandPredicateMatcher(OPM_LiteralInt), Value(Value) {} |
| |
| static bool classof(const OperandPredicateMatcher *P) { |
| return P->getKind() == OPM_LiteralInt; |
| } |
| |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID, unsigned OpIdx) const override { |
| OS << " GIM_CheckLiteralInt, /*MI*/" << InsnVarID << ", /*Op*/" |
| << OpIdx << ", " << Value << ",\n"; |
| } |
| }; |
| |
| /// Generates code to check that an operand is an intrinsic ID. |
| class IntrinsicIDOperandMatcher : public OperandPredicateMatcher { |
| protected: |
| const CodeGenIntrinsic *II; |
| |
| public: |
| IntrinsicIDOperandMatcher(const CodeGenIntrinsic *II) |
| : OperandPredicateMatcher(OPM_IntrinsicID), II(II) {} |
| |
| static bool classof(const OperandPredicateMatcher *P) { |
| return P->getKind() == OPM_IntrinsicID; |
| } |
| |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID, unsigned OpIdx) const override { |
| OS << " GIM_CheckIntrinsicID, /*MI*/" << InsnVarID << ", /*Op*/" |
| << OpIdx << ", Intrinsic::" << II->EnumName << ",\n"; |
| } |
| }; |
| |
| /// Generates code to check that a set of predicates match for a particular |
| /// operand. |
| class OperandMatcher : public PredicateListMatcher<OperandPredicateMatcher> { |
| protected: |
| InstructionMatcher &Insn; |
| unsigned OpIdx; |
| std::string SymbolicName; |
| |
| /// The index of the first temporary variable allocated to this operand. The |
| /// number of allocated temporaries can be found with |
| /// countRendererFns(). |
| unsigned AllocatedTemporariesBaseID; |
| |
| public: |
| OperandMatcher(InstructionMatcher &Insn, unsigned OpIdx, |
| const std::string &SymbolicName, |
| unsigned AllocatedTemporariesBaseID) |
| : Insn(Insn), OpIdx(OpIdx), SymbolicName(SymbolicName), |
| AllocatedTemporariesBaseID(AllocatedTemporariesBaseID) {} |
| |
| bool hasSymbolicName() const { return !SymbolicName.empty(); } |
| const StringRef getSymbolicName() const { return SymbolicName; } |
| void setSymbolicName(StringRef Name) { |
| assert(SymbolicName.empty() && "Operand already has a symbolic name"); |
| SymbolicName = Name; |
| } |
| unsigned getOperandIndex() const { return OpIdx; } |
| |
| std::string getOperandExpr(unsigned InsnVarID) const { |
| return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" + |
| llvm::to_string(OpIdx) + ")"; |
| } |
| |
| Optional<const OperandMatcher *> |
| getOptionalOperand(StringRef DesiredSymbolicName) const { |
| assert(!DesiredSymbolicName.empty() && "Cannot lookup unnamed operand"); |
| if (DesiredSymbolicName == SymbolicName) |
| return this; |
| for (const auto &OP : predicates()) { |
| const auto &MaybeOperand = OP->getOptionalOperand(DesiredSymbolicName); |
| if (MaybeOperand.hasValue()) |
| return MaybeOperand.getValue(); |
| } |
| return None; |
| } |
| |
| InstructionMatcher &getInstructionMatcher() const { return Insn; } |
| |
| /// Emit MatchTable opcodes to capture instructions into the MIs table. |
| void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID) const { |
| for (const auto &Predicate : predicates()) |
| Predicate->emitCaptureOpcodes(OS, Rule, InsnVarID, OpIdx); |
| } |
| |
| /// Emit MatchTable opcodes that test whether the instruction named in |
| /// InsnVarID matches all the predicates and all the operands. |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID) const { |
| OS << " // MIs[" << InsnVarID << "] "; |
| if (SymbolicName.empty()) |
| OS << "Operand " << OpIdx; |
| else |
| OS << SymbolicName; |
| OS << "\n"; |
| emitPredicateListOpcodes(OS, Rule, InsnVarID, OpIdx); |
| } |
| |
| /// Compare the priority of this object and B. |
| /// |
| /// Returns true if this object is more important than B. |
| bool isHigherPriorityThan(const OperandMatcher &B) const { |
| // Operand matchers involving more predicates have higher priority. |
| if (predicates_size() > B.predicates_size()) |
| return true; |
| if (predicates_size() < B.predicates_size()) |
| return false; |
| |
| // This assumes that predicates are added in a consistent order. |
| for (const auto &Predicate : zip(predicates(), B.predicates())) { |
| if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate))) |
| return true; |
| if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate))) |
| return false; |
| } |
| |
| return false; |
| }; |
| |
| /// Report the maximum number of temporary operands needed by the operand |
| /// matcher. |
| unsigned countRendererFns() const { |
| return std::accumulate( |
| predicates().begin(), predicates().end(), 0, |
| [](unsigned A, |
| const std::unique_ptr<OperandPredicateMatcher> &Predicate) { |
| return A + Predicate->countRendererFns(); |
| }); |
| } |
| |
| unsigned getAllocatedTemporariesBaseID() const { |
| return AllocatedTemporariesBaseID; |
| } |
| }; |
| |
| unsigned ComplexPatternOperandMatcher::getAllocatedTemporariesBaseID() const { |
| return Operand.getAllocatedTemporariesBaseID(); |
| } |
| |
| /// Generates code to check a predicate on an instruction. |
| /// |
| /// Typical predicates include: |
| /// * The opcode of the instruction is a particular value. |
| /// * The nsw/nuw flag is/isn't set. |
| class InstructionPredicateMatcher { |
| protected: |
| /// This enum is used for RTTI and also defines the priority that is given to |
| /// the predicate when generating the matcher code. Kinds with higher priority |
| /// must be tested first. |
| enum PredicateKind { |
| IPM_Opcode, |
| }; |
| |
| PredicateKind Kind; |
| |
| public: |
| InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {} |
| virtual ~InstructionPredicateMatcher() {} |
| |
| PredicateKind getKind() const { return Kind; } |
| |
| /// Emit MatchTable opcodes that test whether the instruction named in |
| /// InsnVarID matches the predicate. |
| virtual void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID) const = 0; |
| |
| /// Compare the priority of this object and B. |
| /// |
| /// Returns true if this object is more important than B. |
| virtual bool |
| isHigherPriorityThan(const InstructionPredicateMatcher &B) const { |
| return Kind < B.Kind; |
| }; |
| |
| /// Report the maximum number of temporary operands needed by the predicate |
| /// matcher. |
| virtual unsigned countRendererFns() const { return 0; } |
| }; |
| |
| /// Generates code to check the opcode of an instruction. |
| class InstructionOpcodeMatcher : public InstructionPredicateMatcher { |
| protected: |
| const CodeGenInstruction *I; |
| |
| public: |
| InstructionOpcodeMatcher(const CodeGenInstruction *I) |
| : InstructionPredicateMatcher(IPM_Opcode), I(I) {} |
| |
| static bool classof(const InstructionPredicateMatcher *P) { |
| return P->getKind() == IPM_Opcode; |
| } |
| |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID) const override { |
| OS << " GIM_CheckOpcode, /*MI*/" << InsnVarID << ", " << I->Namespace |
| << "::" << I->TheDef->getName() << ",\n"; |
| } |
| |
| /// Compare the priority of this object and B. |
| /// |
| /// Returns true if this object is more important than B. |
| bool |
| isHigherPriorityThan(const InstructionPredicateMatcher &B) const override { |
| if (InstructionPredicateMatcher::isHigherPriorityThan(B)) |
| return true; |
| if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this)) |
| return false; |
| |
| // Prioritize opcodes for cosmetic reasons in the generated source. Although |
| // this is cosmetic at the moment, we may want to drive a similar ordering |
| // using instruction frequency information to improve compile time. |
| if (const InstructionOpcodeMatcher *BO = |
| dyn_cast<InstructionOpcodeMatcher>(&B)) |
| return I->TheDef->getName() < BO->I->TheDef->getName(); |
| |
| return false; |
| }; |
| }; |
| |
| /// Generates code to check that a set of predicates and operands match for a |
| /// particular instruction. |
| /// |
| /// Typical predicates include: |
| /// * Has a specific opcode. |
| /// * Has an nsw/nuw flag or doesn't. |
| class InstructionMatcher |
| : public PredicateListMatcher<InstructionPredicateMatcher> { |
| protected: |
| typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec; |
| |
| /// The operands to match. All rendered operands must be present even if the |
| /// condition is always true. |
| OperandVec Operands; |
| |
| public: |
| /// Add an operand to the matcher. |
| OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName, |
| unsigned AllocatedTemporariesBaseID) { |
| Operands.emplace_back(new OperandMatcher(*this, OpIdx, SymbolicName, |
| AllocatedTemporariesBaseID)); |
| return *Operands.back(); |
| } |
| |
| OperandMatcher &getOperand(unsigned OpIdx) { |
| auto I = std::find_if(Operands.begin(), Operands.end(), |
| [&OpIdx](const std::unique_ptr<OperandMatcher> &X) { |
| return X->getOperandIndex() == OpIdx; |
| }); |
| if (I != Operands.end()) |
| return **I; |
| llvm_unreachable("Failed to lookup operand"); |
| } |
| |
| Optional<const OperandMatcher *> |
| getOptionalOperand(StringRef SymbolicName) const { |
| assert(!SymbolicName.empty() && "Cannot lookup unnamed operand"); |
| for (const auto &Operand : Operands) { |
| const auto &OM = Operand->getOptionalOperand(SymbolicName); |
| if (OM.hasValue()) |
| return OM.getValue(); |
| } |
| return None; |
| } |
| |
| const OperandMatcher &getOperand(StringRef SymbolicName) const { |
| Optional<const OperandMatcher *>OM = getOptionalOperand(SymbolicName); |
| if (OM.hasValue()) |
| return *OM.getValue(); |
| llvm_unreachable("Failed to lookup operand"); |
| } |
| |
| unsigned getNumOperands() const { return Operands.size(); } |
| OperandVec::iterator operands_begin() { return Operands.begin(); } |
| OperandVec::iterator operands_end() { return Operands.end(); } |
| iterator_range<OperandVec::iterator> operands() { |
| return make_range(operands_begin(), operands_end()); |
| } |
| OperandVec::const_iterator operands_begin() const { return Operands.begin(); } |
| OperandVec::const_iterator operands_end() const { return Operands.end(); } |
| iterator_range<OperandVec::const_iterator> operands() const { |
| return make_range(operands_begin(), operands_end()); |
| } |
| |
| /// Emit MatchTable opcodes to check the shape of the match and capture |
| /// instructions into the MIs table. |
| void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnID) { |
| OS << " GIM_CheckNumOperands, /*MI*/" << InsnID << ", /*Expected*/" |
| << getNumOperands() << ",\n"; |
| for (const auto &Operand : Operands) |
| Operand->emitCaptureOpcodes(OS, Rule, InsnID); |
| } |
| |
| /// Emit MatchTable opcodes that test whether the instruction named in |
| /// InsnVarName matches all the predicates and all the operands. |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID) const { |
| emitPredicateListOpcodes(OS, Rule, InsnVarID); |
| for (const auto &Operand : Operands) |
| Operand->emitPredicateOpcodes(OS, Rule, InsnVarID); |
| } |
| |
| /// Compare the priority of this object and B. |
| /// |
| /// Returns true if this object is more important than B. |
| bool isHigherPriorityThan(const InstructionMatcher &B) const { |
| // Instruction matchers involving more operands have higher priority. |
| if (Operands.size() > B.Operands.size()) |
| return true; |
| if (Operands.size() < B.Operands.size()) |
| return false; |
| |
| for (const auto &Predicate : zip(predicates(), B.predicates())) { |
| if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate))) |
| return true; |
| if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate))) |
| return false; |
| } |
| |
| for (const auto &Operand : zip(Operands, B.Operands)) { |
| if (std::get<0>(Operand)->isHigherPriorityThan(*std::get<1>(Operand))) |
| return true; |
| if (std::get<1>(Operand)->isHigherPriorityThan(*std::get<0>(Operand))) |
| return false; |
| } |
| |
| return false; |
| }; |
| |
| /// Report the maximum number of temporary operands needed by the instruction |
| /// matcher. |
| unsigned countRendererFns() const { |
| return std::accumulate(predicates().begin(), predicates().end(), 0, |
| [](unsigned A, |
| const std::unique_ptr<InstructionPredicateMatcher> |
| &Predicate) { |
| return A + Predicate->countRendererFns(); |
| }) + |
| std::accumulate( |
| Operands.begin(), Operands.end(), 0, |
| [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) { |
| return A + Operand->countRendererFns(); |
| }); |
| } |
| }; |
| |
| /// Generates code to check that the operand is a register defined by an |
| /// instruction that matches the given instruction matcher. |
| /// |
| /// For example, the pattern: |
| /// (set $dst, (G_MUL (G_ADD $src1, $src2), $src3)) |
| /// would use an InstructionOperandMatcher for operand 1 of the G_MUL to match |
| /// the: |
| /// (G_ADD $src1, $src2) |
| /// subpattern. |
| class InstructionOperandMatcher : public OperandPredicateMatcher { |
| protected: |
| std::unique_ptr<InstructionMatcher> InsnMatcher; |
| |
| public: |
| InstructionOperandMatcher() |
| : OperandPredicateMatcher(OPM_Instruction), |
| InsnMatcher(new InstructionMatcher()) {} |
| |
| static bool classof(const OperandPredicateMatcher *P) { |
| return P->getKind() == OPM_Instruction; |
| } |
| |
| InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; } |
| |
| Optional<const OperandMatcher *> |
| getOptionalOperand(StringRef SymbolicName) const override { |
| assert(!SymbolicName.empty() && "Cannot lookup unnamed operand"); |
| return InsnMatcher->getOptionalOperand(SymbolicName); |
| } |
| |
| void emitCaptureOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnID, unsigned OpIdx) const override { |
| unsigned InsnVarID = Rule.defineInsnVar(OS, *InsnMatcher, InsnID, OpIdx); |
| InsnMatcher->emitCaptureOpcodes(OS, Rule, InsnVarID); |
| } |
| |
| void emitPredicateOpcodes(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned InsnVarID_, |
| unsigned OpIdx_) const override { |
| unsigned InsnVarID = Rule.getInsnVarID(*InsnMatcher); |
| InsnMatcher->emitPredicateOpcodes(OS, Rule, InsnVarID); |
| } |
| }; |
| |
| //===- Actions ------------------------------------------------------------===// |
| class OperandRenderer { |
| public: |
| enum RendererKind { |
| OR_Copy, |
| OR_CopySubReg, |
| OR_Imm, |
| OR_Register, |
| OR_ComplexPattern |
| }; |
| |
| protected: |
| RendererKind Kind; |
| |
| public: |
| OperandRenderer(RendererKind Kind) : Kind(Kind) {} |
| virtual ~OperandRenderer() {} |
| |
| RendererKind getKind() const { return Kind; } |
| |
| virtual void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const = 0; |
| }; |
| |
| /// A CopyRenderer emits code to copy a single operand from an existing |
| /// instruction to the one being built. |
| class CopyRenderer : public OperandRenderer { |
| protected: |
| unsigned NewInsnID; |
| /// The matcher for the instruction that this operand is copied from. |
| /// This provides the facility for looking up an a operand by it's name so |
| /// that it can be used as a source for the instruction being built. |
| const InstructionMatcher &Matched; |
| /// The name of the operand. |
| const StringRef SymbolicName; |
| |
| public: |
| CopyRenderer(unsigned NewInsnID, const InstructionMatcher &Matched, |
| StringRef SymbolicName) |
| : OperandRenderer(OR_Copy), NewInsnID(NewInsnID), Matched(Matched), |
| SymbolicName(SymbolicName) {} |
| |
| static bool classof(const OperandRenderer *R) { |
| return R->getKind() == OR_Copy; |
| } |
| |
| const StringRef getSymbolicName() const { return SymbolicName; } |
| |
| void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override { |
| const OperandMatcher &Operand = Matched.getOperand(SymbolicName); |
| unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); |
| OS << " GIR_Copy, /*NewInsnID*/" << NewInsnID << ", /*OldInsnID*/" |
| << OldInsnVarID << ", /*OpIdx*/" << Operand.getOperandIndex() << ", // " |
| << SymbolicName << "\n"; |
| } |
| }; |
| |
| /// A CopySubRegRenderer emits code to copy a single register operand from an |
| /// existing instruction to the one being built and indicate that only a |
| /// subregister should be copied. |
| class CopySubRegRenderer : public OperandRenderer { |
| protected: |
| unsigned NewInsnID; |
| /// The matcher for the instruction that this operand is copied from. |
| /// This provides the facility for looking up an a operand by it's name so |
| /// that it can be used as a source for the instruction being built. |
| const InstructionMatcher &Matched; |
| /// The name of the operand. |
| const StringRef SymbolicName; |
| /// The subregister to extract. |
| const CodeGenSubRegIndex *SubReg; |
| |
| public: |
| CopySubRegRenderer(unsigned NewInsnID, const InstructionMatcher &Matched, |
| StringRef SymbolicName, const CodeGenSubRegIndex *SubReg) |
| : OperandRenderer(OR_CopySubReg), NewInsnID(NewInsnID), Matched(Matched), |
| SymbolicName(SymbolicName), SubReg(SubReg) {} |
| |
| static bool classof(const OperandRenderer *R) { |
| return R->getKind() == OR_CopySubReg; |
| } |
| |
| const StringRef getSymbolicName() const { return SymbolicName; } |
| |
| void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override { |
| const OperandMatcher &Operand = Matched.getOperand(SymbolicName); |
| unsigned OldInsnVarID = Rule.getInsnVarID(Operand.getInstructionMatcher()); |
| OS << " GIR_CopySubReg, /*NewInsnID*/" << NewInsnID |
| << ", /*OldInsnID*/" << OldInsnVarID << ", /*OpIdx*/" |
| << Operand.getOperandIndex() << ", /*SubRegIdx*/" << SubReg->EnumValue |
| << ", // " << SymbolicName << "\n"; |
| } |
| }; |
| |
| /// Adds a specific physical register to the instruction being built. |
| /// This is typically useful for WZR/XZR on AArch64. |
| class AddRegisterRenderer : public OperandRenderer { |
| protected: |
| unsigned InsnID; |
| const Record *RegisterDef; |
| |
| public: |
| AddRegisterRenderer(unsigned InsnID, const Record *RegisterDef) |
| : OperandRenderer(OR_Register), InsnID(InsnID), RegisterDef(RegisterDef) { |
| } |
| |
| static bool classof(const OperandRenderer *R) { |
| return R->getKind() == OR_Register; |
| } |
| |
| void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override { |
| OS << " GIR_AddRegister, /*InsnID*/" << InsnID << ", " |
| << (RegisterDef->getValue("Namespace") |
| ? RegisterDef->getValueAsString("Namespace") |
| : "") |
| << "::" << RegisterDef->getName() << ",\n"; |
| } |
| }; |
| |
| /// Adds a specific immediate to the instruction being built. |
| class ImmRenderer : public OperandRenderer { |
| protected: |
| unsigned InsnID; |
| int64_t Imm; |
| |
| public: |
| ImmRenderer(unsigned InsnID, int64_t Imm) |
| : OperandRenderer(OR_Imm), InsnID(InsnID), Imm(Imm) {} |
| |
| static bool classof(const OperandRenderer *R) { |
| return R->getKind() == OR_Imm; |
| } |
| |
| void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override { |
| OS << " GIR_AddImm, /*InsnID*/" << InsnID << ", /*Imm*/" << Imm |
| << ",\n"; |
| } |
| }; |
| |
| /// Adds operands by calling a renderer function supplied by the ComplexPattern |
| /// matcher function. |
| class RenderComplexPatternOperand : public OperandRenderer { |
| private: |
| unsigned InsnID; |
| const Record &TheDef; |
| /// The name of the operand. |
| const StringRef SymbolicName; |
| /// The renderer number. This must be unique within a rule since it's used to |
| /// identify a temporary variable to hold the renderer function. |
| unsigned RendererID; |
| |
| unsigned getNumOperands() const { |
| return TheDef.getValueAsDag("Operands")->getNumArgs(); |
| } |
| |
| public: |
| RenderComplexPatternOperand(unsigned InsnID, const Record &TheDef, |
| StringRef SymbolicName, unsigned RendererID) |
| : OperandRenderer(OR_ComplexPattern), InsnID(InsnID), TheDef(TheDef), |
| SymbolicName(SymbolicName), RendererID(RendererID) {} |
| |
| static bool classof(const OperandRenderer *R) { |
| return R->getKind() == OR_ComplexPattern; |
| } |
| |
| void emitRenderOpcodes(raw_ostream &OS, RuleMatcher &Rule) const override { |
| OS << " GIR_ComplexRenderer, /*InsnID*/" << InsnID << ", /*RendererID*/" |
| << RendererID << ",\n"; |
| } |
| }; |
| |
| /// An action taken when all Matcher predicates succeeded for a parent rule. |
| /// |
| /// Typical actions include: |
| /// * Changing the opcode of an instruction. |
| /// * Adding an operand to an instruction. |
| class MatchAction { |
| public: |
| virtual ~MatchAction() {} |
| |
| /// Emit the C++ statements to implement the action. |
| /// |
| /// \param RecycleInsnID If given, it's an instruction to recycle. The |
| /// requirements on the instruction vary from action to |
| /// action. |
| virtual void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned RecycleInsnID) const = 0; |
| }; |
| |
| /// Generates a comment describing the matched rule being acted upon. |
| class DebugCommentAction : public MatchAction { |
| private: |
| const PatternToMatch &P; |
| |
| public: |
| DebugCommentAction(const PatternToMatch &P) : P(P) {} |
| |
| void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned RecycleInsnID) const override { |
| OS << " // " << *P.getSrcPattern() << " => " << *P.getDstPattern() |
| << "\n"; |
| } |
| }; |
| |
| /// Generates code to build an instruction or mutate an existing instruction |
| /// into the desired instruction when this is possible. |
| class BuildMIAction : public MatchAction { |
| private: |
| unsigned InsnID; |
| const CodeGenInstruction *I; |
| const InstructionMatcher &Matched; |
| std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers; |
| |
| /// True if the instruction can be built solely by mutating the opcode. |
| bool canMutate() const { |
| if (OperandRenderers.size() != Matched.getNumOperands()) |
| return false; |
| |
| for (const auto &Renderer : enumerate(OperandRenderers)) { |
| if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) { |
| const OperandMatcher &OM = Matched.getOperand(Copy->getSymbolicName()); |
| if (&Matched != &OM.getInstructionMatcher() || |
| OM.getOperandIndex() != Renderer.index()) |
| return false; |
| } else |
| return false; |
| } |
| |
| return true; |
| } |
| |
| public: |
| BuildMIAction(unsigned InsnID, const CodeGenInstruction *I, |
| const InstructionMatcher &Matched) |
| : InsnID(InsnID), I(I), Matched(Matched) {} |
| |
| template <class Kind, class... Args> |
| Kind &addRenderer(Args&&... args) { |
| OperandRenderers.emplace_back( |
| llvm::make_unique<Kind>(std::forward<Args>(args)...)); |
| return *static_cast<Kind *>(OperandRenderers.back().get()); |
| } |
| |
| void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned RecycleInsnID) const override { |
| if (canMutate()) { |
| OS << " GIR_MutateOpcode, /*InsnID*/" << InsnID |
| << ", /*RecycleInsnID*/ " << RecycleInsnID << ", /*Opcode*/" |
| << I->Namespace << "::" << I->TheDef->getName() << ",\n"; |
| |
| if (!I->ImplicitDefs.empty() || !I->ImplicitUses.empty()) { |
| for (auto Def : I->ImplicitDefs) { |
| auto Namespace = Def->getValue("Namespace") |
| ? Def->getValueAsString("Namespace") |
| : ""; |
| OS << " GIR_AddImplicitDef, " << InsnID << ", " << Namespace |
| << "::" << Def->getName() << ",\n"; |
| } |
| for (auto Use : I->ImplicitUses) { |
| auto Namespace = Use->getValue("Namespace") |
| ? Use->getValueAsString("Namespace") |
| : ""; |
| OS << " GIR_AddImplicitUse, " << InsnID << ", " << Namespace |
| << "::" << Use->getName() << ",\n"; |
| } |
| } |
| return; |
| } |
| |
| // TODO: Simple permutation looks like it could be almost as common as |
| // mutation due to commutative operations. |
| |
| OS << " GIR_BuildMI, /*InsnID*/" << InsnID << ", /*Opcode*/" |
| << I->Namespace << "::" << I->TheDef->getName() << ",\n"; |
| for (const auto &Renderer : OperandRenderers) |
| Renderer->emitRenderOpcodes(OS, Rule); |
| |
| OS << " GIR_MergeMemOperands, /*InsnID*/" << InsnID << ",\n" |
| << " GIR_EraseFromParent, /*InsnID*/" << RecycleInsnID << ",\n"; |
| } |
| }; |
| |
| /// Generates code to constrain the operands of an output instruction to the |
| /// register classes specified by the definition of that instruction. |
| class ConstrainOperandsToDefinitionAction : public MatchAction { |
| unsigned InsnID; |
| |
| public: |
| ConstrainOperandsToDefinitionAction(unsigned InsnID) : InsnID(InsnID) {} |
| |
| void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned RecycleInsnID) const override { |
| OS << " GIR_ConstrainSelectedInstOperands, /*InsnID*/" << InsnID << ",\n"; |
| } |
| }; |
| |
| /// Generates code to constrain the specified operand of an output instruction |
| /// to the specified register class. |
| class ConstrainOperandToRegClassAction : public MatchAction { |
| unsigned InsnID; |
| unsigned OpIdx; |
| const CodeGenRegisterClass &RC; |
| |
| public: |
| ConstrainOperandToRegClassAction(unsigned InsnID, unsigned OpIdx, |
| const CodeGenRegisterClass &RC) |
| : InsnID(InsnID), OpIdx(OpIdx), RC(RC) {} |
| |
| void emitCxxActionStmts(raw_ostream &OS, RuleMatcher &Rule, |
| unsigned RecycleInsnID) const override { |
| OS << " GIR_ConstrainOperandRC, /*InsnID*/" << InsnID << ", /*Op*/" |
| << OpIdx << ", /*RC " << RC.getName() << "*/ " << RC.EnumValue << ",\n"; |
| } |
| }; |
| |
| InstructionMatcher &RuleMatcher::addInstructionMatcher() { |
| Matchers.emplace_back(new InstructionMatcher()); |
| return *Matchers.back(); |
| } |
| |
| void RuleMatcher::addRequiredFeature(Record *Feature) { |
| RequiredFeatures.push_back(Feature); |
| } |
| |
| const std::vector<Record *> &RuleMatcher::getRequiredFeatures() const { |
| return RequiredFeatures; |
| } |
| |
| template <class Kind, class... Args> |
| Kind &RuleMatcher::addAction(Args &&... args) { |
| Actions.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...)); |
| return *static_cast<Kind *>(Actions.back().get()); |
| } |
| |
| unsigned |
| RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) { |
| unsigned NewInsnVarID = NextInsnVarID++; |
| InsnVariableIDs[&Matcher] = NewInsnVarID; |
| return NewInsnVarID; |
| } |
| |
| unsigned RuleMatcher::defineInsnVar(raw_ostream &OS, |
| const InstructionMatcher &Matcher, |
| unsigned InsnID, unsigned OpIdx) { |
| unsigned NewInsnVarID = implicitlyDefineInsnVar(Matcher); |
| OS << " GIM_RecordInsn, /*DefineMI*/" << NewInsnVarID << ", /*MI*/" |
| << InsnID << ", /*OpIdx*/" << OpIdx << ", // MIs[" << NewInsnVarID |
| << "]\n"; |
| return NewInsnVarID; |
| } |
| |
| unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const { |
| const auto &I = InsnVariableIDs.find(&InsnMatcher); |
| if (I != InsnVariableIDs.end()) |
| return I->second; |
| llvm_unreachable("Matched Insn was not captured in a local variable"); |
| } |
| |
| /// Emit MatchTable opcodes to check the shape of the match and capture |
| /// instructions into local variables. |
| void RuleMatcher::emitCaptureOpcodes(raw_ostream &OS) { |
| assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet"); |
| unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front()); |
| Matchers.front()->emitCaptureOpcodes(OS, *this, InsnVarID); |
| } |
| |
| void RuleMatcher::emit(raw_ostream &OS) { |
| if (Matchers.empty()) |
| llvm_unreachable("Unexpected empty matcher!"); |
| |
| // The representation supports rules that require multiple roots such as: |
| // %ptr(p0) = ... |
| // %elt0(s32) = G_LOAD %ptr |
| // %1(p0) = G_ADD %ptr, 4 |
| // %elt1(s32) = G_LOAD p0 %1 |
| // which could be usefully folded into: |
| // %ptr(p0) = ... |
| // %elt0(s32), %elt1(s32) = TGT_LOAD_PAIR %ptr |
| // on some targets but we don't need to make use of that yet. |
| assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet"); |
| |
| OS << " const static int64_t MatchTable" << CurrentMatchTableID << "[] = {\n"; |
| if (!RequiredFeatures.empty()) { |
| OS << " GIM_CheckFeatures, " << getNameForFeatureBitset(RequiredFeatures) |
| << ",\n"; |
| } |
| |
| emitCaptureOpcodes(OS); |
| |
| Matchers.front()->emitPredicateOpcodes(OS, *this, |
| getInsnVarID(*Matchers.front())); |
| |
| // We must also check if it's safe to fold the matched instructions. |
| if (InsnVariableIDs.size() >= 2) { |
| // Invert the map to create stable ordering (by var names) |
| SmallVector<unsigned, 2> InsnIDs; |
| for (const auto &Pair : InsnVariableIDs) { |
| // Skip the root node since it isn't moving anywhere. Everything else is |
| // sinking to meet it. |
| if (Pair.first == Matchers.front().get()) |
| continue; |
| |
| InsnIDs.push_back(Pair.second); |
| } |
| std::sort(InsnIDs.begin(), InsnIDs.end()); |
| |
| for (const auto &InsnID : InsnIDs) { |
| // Reject the difficult cases until we have a more accurate check. |
| OS << " GIM_CheckIsSafeToFold, /*InsnID*/" << InsnID << ",\n"; |
| |
| // FIXME: Emit checks to determine it's _actually_ safe to fold and/or |
| // account for unsafe cases. |
| // |
| // Example: |
| // MI1--> %0 = ... |
| // %1 = ... %0 |
| // MI0--> %2 = ... %0 |
| // It's not safe to erase MI1. We currently handle this by not |
| // erasing %0 (even when it's dead). |
| // |
| // Example: |
| // MI1--> %0 = load volatile @a |
| // %1 = load volatile @a |
| // MI0--> %2 = ... %0 |
| // It's not safe to sink %0's def past %1. We currently handle |
| // this by rejecting all loads. |
| // |
| // Example: |
| // MI1--> %0 = load @a |
| // %1 = store @a |
| // MI0--> %2 = ... %0 |
| // It's not safe to sink %0's def past %1. We currently handle |
| // this by rejecting all loads. |
| // |
| // Example: |
| // G_CONDBR %cond, @BB1 |
| // BB0: |
| // MI1--> %0 = load @a |
| // G_BR @BB1 |
| // BB1: |
| // MI0--> %2 = ... %0 |
| // It's not always safe to sink %0 across control flow. In this |
| // case it may introduce a memory fault. We currentl handle this |
| // by rejecting all loads. |
| } |
| } |
| |
| for (const auto &MA : Actions) |
| MA->emitCxxActionStmts(OS, *this, 0); |
| OS << " GIR_Done,\n" |
| << " };\n" |
| << " State.MIs.resize(1);\n" |
| << " DEBUG(dbgs() << \"Processing MatchTable" << CurrentMatchTableID |
| << "\\n\");\n" |
| << " if (executeMatchTable(*this, OutMIs, State, MatcherInfo, MatchTable" |
| << CurrentMatchTableID << ", TII, MRI, TRI, RBI, AvailableFeatures)) {\n" |
| << " return true;\n" |
| << " }\n\n"; |
| } |
| |
| bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const { |
| // Rules involving more match roots have higher priority. |
| if (Matchers.size() > B.Matchers.size()) |
| return true; |
| if (Matchers.size() < B.Matchers.size()) |
| return false; |
| |
| for (const auto &Matcher : zip(Matchers, B.Matchers)) { |
| if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher))) |
| return true; |
| if (std::get<1>(Matcher)->isHigherPriorityThan(*std::get<0>(Matcher))) |
| return false; |
| } |
| |
| return false; |
| } |
| |
| unsigned RuleMatcher::countRendererFns() const { |
| return std::accumulate( |
| Matchers.begin(), Matchers.end(), 0, |
| [](unsigned A, const std::unique_ptr<InstructionMatcher> &Matcher) { |
| return A + Matcher->countRendererFns(); |
| }); |
| } |
| |
| //===- GlobalISelEmitter class --------------------------------------------===// |
| |
| class GlobalISelEmitter { |
| public: |
| explicit GlobalISelEmitter(RecordKeeper &RK); |
| void run(raw_ostream &OS); |
| |
| private: |
| const RecordKeeper &RK; |
| const CodeGenDAGPatterns CGP; |
| const CodeGenTarget &Target; |
| CodeGenRegBank CGRegs; |
| |
| /// Keep track of the equivalence between SDNodes and Instruction. |
| /// This is defined using 'GINodeEquiv' in the target description. |
| DenseMap<Record *, const CodeGenInstruction *> NodeEquivs; |
| |
| /// Keep track of the equivalence between ComplexPattern's and |
| /// GIComplexOperandMatcher. Map entries are specified by subclassing |
| /// GIComplexPatternEquiv. |
| DenseMap<const Record *, const Record *> ComplexPatternEquivs; |
| |
| // Map of predicates to their subtarget features. |
| SubtargetFeatureInfoMap SubtargetFeatures; |
| |
| void gatherNodeEquivs(); |
| const CodeGenInstruction *findNodeEquiv(Record *N) const; |
| |
| Error importRulePredicates(RuleMatcher &M, ArrayRef<Init *> Predicates); |
| Expected<InstructionMatcher &> |
| createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher, |
| const TreePatternNode *Src, |
| unsigned &TempOpIdx) const; |
| Error importChildMatcher(InstructionMatcher &InsnMatcher, |
| const TreePatternNode *SrcChild, unsigned OpIdx, |
| unsigned &TempOpIdx) const; |
| Expected<BuildMIAction &> |
| createAndImportInstructionRenderer(RuleMatcher &M, const TreePatternNode *Dst, |
| const InstructionMatcher &InsnMatcher); |
| Error importExplicitUseRenderer(BuildMIAction &DstMIBuilder, |
| TreePatternNode *DstChild, |
| const InstructionMatcher &InsnMatcher) const; |
| Error importDefaultOperandRenderers(BuildMIAction &DstMIBuilder, |
| DagInit *DefaultOps) const; |
| Error |
| importImplicitDefRenderers(BuildMIAction &DstMIBuilder, |
| const std::vector<Record *> &ImplicitDefs) const; |
| |
| /// Analyze pattern \p P, returning a matcher for it if possible. |
| /// Otherwise, return an Error explaining why we don't support it. |
| Expected<RuleMatcher> runOnPattern(const PatternToMatch &P); |
| |
| void declareSubtargetFeature(Record *Predicate); |
| }; |
| |
| void GlobalISelEmitter::gatherNodeEquivs() { |
| assert(NodeEquivs.empty()); |
| for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv")) |
| NodeEquivs[Equiv->getValueAsDef("Node")] = |
| &Target.getInstruction(Equiv->getValueAsDef("I")); |
| |
| assert(ComplexPatternEquivs.empty()); |
| for (Record *Equiv : RK.getAllDerivedDefinitions("GIComplexPatternEquiv")) { |
| Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent"); |
| if (!SelDAGEquiv) |
| continue; |
| ComplexPatternEquivs[SelDAGEquiv] = Equiv; |
| } |
| } |
| |
| const CodeGenInstruction *GlobalISelEmitter::findNodeEquiv(Record *N) const { |
| return NodeEquivs.lookup(N); |
| } |
| |
| GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK) |
| : RK(RK), CGP(RK), Target(CGP.getTargetInfo()), CGRegs(RK) {} |
| |
| //===- Emitter ------------------------------------------------------------===// |
| |
| Error |
| GlobalISelEmitter::importRulePredicates(RuleMatcher &M, |
| ArrayRef<Init *> Predicates) { |
| for (const Init *Predicate : Predicates) { |
| const DefInit *PredicateDef = static_cast<const DefInit *>(Predicate); |
| declareSubtargetFeature(PredicateDef->getDef()); |
| M.addRequiredFeature(PredicateDef->getDef()); |
| } |
| |
| return Error::success(); |
| } |
| |
| Expected<InstructionMatcher &> |
| GlobalISelEmitter::createAndImportSelDAGMatcher(InstructionMatcher &InsnMatcher, |
| const TreePatternNode *Src, |
| unsigned &TempOpIdx) const { |
| const CodeGenInstruction *SrcGIOrNull = nullptr; |
| |
| // Start with the defined operands (i.e., the results of the root operator). |
| if (Src->getExtTypes().size() > 1) |
| return failedImport("Src pattern has multiple results"); |
| |
| if (Src->isLeaf()) { |
| Init *SrcInit = Src->getLeafValue(); |
| if (isa<IntInit>(SrcInit)) { |
| InsnMatcher.addPredicate<InstructionOpcodeMatcher>( |
| &Target.getInstruction(RK.getDef("G_CONSTANT"))); |
| } else |
| return failedImport( |
| "Unable to deduce gMIR opcode to handle Src (which is a leaf)"); |
| } else { |
| SrcGIOrNull = findNodeEquiv(Src->getOperator()); |
| if (!SrcGIOrNull) |
| return failedImport("Pattern operator lacks an equivalent Instruction" + |
| explainOperator(Src->getOperator())); |
| auto &SrcGI = *SrcGIOrNull; |
| |
| // The operators look good: match the opcode |
| InsnMatcher.addPredicate<InstructionOpcodeMatcher>(&SrcGI); |
| } |
| |
| unsigned OpIdx = 0; |
| for (const EEVT::TypeSet &Ty : Src->getExtTypes()) { |
| auto OpTyOrNone = MVTToLLT(Ty.getConcrete()); |
| |
| if (!OpTyOrNone) |
| return failedImport( |
| "Result of Src pattern operator has an unsupported type"); |
| |
| // Results don't have a name unless they are the root node. The caller will |
| // set the name if appropriate. |
| OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx); |
| OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone); |
| } |
| |
| if (Src->isLeaf()) { |
| Init *SrcInit = Src->getLeafValue(); |
| if (IntInit *SrcIntInit = dyn_cast<IntInit>(SrcInit)) { |
| OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, "", TempOpIdx); |
| OM.addPredicate<LiteralIntOperandMatcher>(SrcIntInit->getValue()); |
| } else |
| return failedImport( |
| "Unable to deduce gMIR opcode to handle Src (which is a leaf)"); |
| } else { |
| assert(SrcGIOrNull && |
| "Expected to have already found an equivalent Instruction"); |
| // Match the used operands (i.e. the children of the operator). |
| for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) { |
| TreePatternNode *SrcChild = Src->getChild(i); |
| |
| // For G_INTRINSIC, the operand immediately following the defs is an |
| // intrinsic ID. |
| if (SrcGIOrNull->TheDef->getName() == "G_INTRINSIC" && i == 0) { |
| if (const CodeGenIntrinsic *II = Src->getIntrinsicInfo(CGP)) { |
| OperandMatcher &OM = |
| InsnMatcher.addOperand(OpIdx++, SrcChild->getName(), TempOpIdx); |
| OM.addPredicate<IntrinsicIDOperandMatcher>(II); |
| continue; |
| } |
| |
| return failedImport("Expected IntInit containing instrinsic ID)"); |
| } |
| |
| if (auto Error = |
| importChildMatcher(InsnMatcher, SrcChild, OpIdx++, TempOpIdx)) |
| return std::move(Error); |
| } |
| } |
| |
| return InsnMatcher; |
| } |
| |
| Error GlobalISelEmitter::importChildMatcher(InstructionMatcher &InsnMatcher, |
| const TreePatternNode *SrcChild, |
| unsigned OpIdx, |
| unsigned &TempOpIdx) const { |
| OperandMatcher &OM = |
| InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx); |
| |
| if (SrcChild->hasAnyPredicate()) |
| return failedImport("Src pattern child has predicate (" + |
| explainPredicates(SrcChild) + ")"); |
| |
| ArrayRef<EEVT::TypeSet> ChildTypes = SrcChild->getExtTypes(); |
| if (ChildTypes.size() != 1) |
| return failedImport("Src pattern child has multiple results"); |
| |
| // Check MBB's before the type check since they are not a known type. |
| if (!SrcChild->isLeaf()) { |
| if (SrcChild->getOperator()->isSubClassOf("SDNode")) { |
| auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator()); |
| if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") { |
| OM.addPredicate<MBBOperandMatcher>(); |
| return Error::success(); |
| } |
| } |
| } |
| |
| auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete()); |
| if (!OpTyOrNone) |
| return failedImport("Src operand has an unsupported type (" + to_string(*SrcChild) + ")"); |
| OM.addPredicate<LLTOperandMatcher>(*OpTyOrNone); |
| |
| // Check for nested instructions. |
| if (!SrcChild->isLeaf()) { |
| // Map the node to a gMIR instruction. |
| InstructionOperandMatcher &InsnOperand = |
| OM.addPredicate<InstructionOperandMatcher>(); |
| auto InsnMatcherOrError = createAndImportSelDAGMatcher( |
| InsnOperand.getInsnMatcher(), SrcChild, TempOpIdx); |
| if (auto Error = InsnMatcherOrError.takeError()) |
| return Error; |
| |
| return Error::success(); |
| } |
| |
| // Check for constant immediates. |
| if (auto *ChildInt = dyn_cast<IntInit>(SrcChild->getLeafValue())) { |
| OM.addPredicate<ConstantIntOperandMatcher>(ChildInt->getValue()); |
| return Error::success(); |
| } |
| |
| // Check for def's like register classes or ComplexPattern's. |
| if (auto *ChildDefInit = dyn_cast<DefInit>(SrcChild->getLeafValue())) { |
| auto *ChildRec = ChildDefInit->getDef(); |
| |
| // Check for register classes. |
| if (ChildRec->isSubClassOf("RegisterClass") || |
| ChildRec->isSubClassOf("RegisterOperand")) { |
| OM.addPredicate<RegisterBankOperandMatcher>( |
| Target.getRegisterClass(getInitValueAsRegClass(ChildDefInit))); |
| return Error::success(); |
| } |
| |
| // Check for ComplexPattern's. |
| if (ChildRec->isSubClassOf("ComplexPattern")) { |
| const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec); |
| if (ComplexPattern == ComplexPatternEquivs.end()) |
| return failedImport("SelectionDAG ComplexPattern (" + |
| ChildRec->getName() + ") not mapped to GlobalISel"); |
| |
| OM.addPredicate<ComplexPatternOperandMatcher>(OM, |
| *ComplexPattern->second); |
| TempOpIdx++; |
| return Error::success(); |
| } |
| |
| if (ChildRec->isSubClassOf("ImmLeaf")) { |
| return failedImport( |
| "Src pattern child def is an unsupported tablegen class (ImmLeaf)"); |
| } |
| |
| return failedImport( |
| "Src pattern child def is an unsupported tablegen class"); |
| } |
| |
| return failedImport("Src pattern child is an unsupported kind"); |
| } |
| |
| Error GlobalISelEmitter::importExplicitUseRenderer( |
| BuildMIAction &DstMIBuilder, TreePatternNode *DstChild, |
| const InstructionMatcher &InsnMatcher) const { |
| // 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 (!DstChild->isLeaf()) { |
| if (DstChild->getOperator()->isSubClassOf("SDNode")) { |
| auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator()); |
| if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") { |
| DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher, |
| DstChild->getName()); |
| return Error::success(); |
| } |
| } |
| return failedImport("Dst pattern child isn't a leaf node or an MBB"); |
| } |
| |
| // Otherwise, we're looking for a bog-standard RegisterClass operand. |
| if (DstChild->hasAnyPredicate()) |
| return failedImport("Dst pattern child has predicate (" + |
| explainPredicates(DstChild) + ")"); |
| |
| if (auto *ChildDefInit = dyn_cast<DefInit>(DstChild->getLeafValue())) { |
| auto *ChildRec = ChildDefInit->getDef(); |
| |
| ArrayRef<EEVT::TypeSet> ChildTypes = DstChild->getExtTypes(); |
| if (ChildTypes.size() != 1) |
| return failedImport("Dst pattern child has multiple results"); |
| |
| auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete()); |
| if (!OpTyOrNone) |
| return failedImport("Dst operand has an unsupported type"); |
| |
| if (ChildRec->isSubClassOf("Register")) { |
| DstMIBuilder.addRenderer<AddRegisterRenderer>(0, ChildRec); |
| return Error::success(); |
| } |
| |
| if (ChildRec->isSubClassOf("RegisterClass") || |
| ChildRec->isSubClassOf("RegisterOperand")) { |
| DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher, |
| DstChild->getName()); |
| return Error::success(); |
| } |
| |
| if (ChildRec->isSubClassOf("ComplexPattern")) { |
| const auto &ComplexPattern = ComplexPatternEquivs.find(ChildRec); |
| if (ComplexPattern == ComplexPatternEquivs.end()) |
| return failedImport( |
| "SelectionDAG ComplexPattern not mapped to GlobalISel"); |
| |
| const OperandMatcher &OM = InsnMatcher.getOperand(DstChild->getName()); |
| DstMIBuilder.addRenderer<RenderComplexPatternOperand>( |
| 0, *ComplexPattern->second, DstChild->getName(), |
| OM.getAllocatedTemporariesBaseID()); |
| return Error::success(); |
| } |
| |
| if (ChildRec->isSubClassOf("SDNodeXForm")) |
| return failedImport("Dst pattern child def is an unsupported tablegen " |
| "class (SDNodeXForm)"); |
| |
| return failedImport( |
| "Dst pattern child def is an unsupported tablegen class"); |
| } |
| |
| return failedImport("Dst pattern child is an unsupported kind"); |
| } |
| |
| Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer( |
| RuleMatcher &M, const TreePatternNode *Dst, |
| const InstructionMatcher &InsnMatcher) { |
| Record *DstOp = Dst->getOperator(); |
| if (!DstOp->isSubClassOf("Instruction")) { |
| if (DstOp->isSubClassOf("ValueType")) |
| return failedImport( |
| "Pattern operator isn't an instruction (it's a ValueType)"); |
| return failedImport("Pattern operator isn't an instruction"); |
| } |
| CodeGenInstruction *DstI = &Target.getInstruction(DstOp); |
| |
| unsigned DstINumUses = DstI->Operands.size() - DstI->Operands.NumDefs; |
| unsigned ExpectedDstINumUses = Dst->getNumChildren(); |
| bool IsExtractSubReg = false; |
| |
| // COPY_TO_REGCLASS is just a copy with a ConstrainOperandToRegClassAction |
| // attached. Similarly for EXTRACT_SUBREG except that's a subregister copy. |
| if (DstI->TheDef->getName() == "COPY_TO_REGCLASS") { |
| DstI = &Target.getInstruction(RK.getDef("COPY")); |
| DstINumUses--; // Ignore the class constraint. |
| ExpectedDstINumUses--; |
| } else if (DstI->TheDef->getName() == "EXTRACT_SUBREG") { |
| DstI = &Target.getInstruction(RK.getDef("COPY")); |
| IsExtractSubReg = true; |
| } |
| |
| auto &DstMIBuilder = M.addAction<BuildMIAction>(0, DstI, InsnMatcher); |
| |
| // Render the explicit defs. |
| for (unsigned I = 0; I < DstI->Operands.NumDefs; ++I) { |
| const CGIOperandList::OperandInfo &DstIOperand = DstI->Operands[I]; |
| DstMIBuilder.addRenderer<CopyRenderer>(0, InsnMatcher, DstIOperand.Name); |
| } |
| |
| // EXTRACT_SUBREG needs to use a subregister COPY. |
| if (IsExtractSubReg) { |
| if (!Dst->getChild(0)->isLeaf()) |
| return failedImport("EXTRACT_SUBREG child #1 is not a leaf"); |
| |
| if (DefInit *SubRegInit = |
| dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue())) { |
| CodeGenRegisterClass *RC = CGRegs.getRegClass( |
| getInitValueAsRegClass(Dst->getChild(0)->getLeafValue())); |
| CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef()); |
| |
| const auto &SrcRCDstRCPair = |
| RC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx); |
| if (SrcRCDstRCPair.hasValue()) { |
| assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass"); |
| if (SrcRCDstRCPair->first != RC) |
| return failedImport("EXTRACT_SUBREG requires an additional COPY"); |
| } |
| |
| DstMIBuilder.addRenderer<CopySubRegRenderer>( |
| 0, InsnMatcher, Dst->getChild(0)->getName(), SubIdx); |
| return DstMIBuilder; |
| } |
| |
| return failedImport("EXTRACT_SUBREG child #1 is not a subreg index"); |
| } |
| |
| // Render the explicit uses. |
| unsigned Child = 0; |
| unsigned NumDefaultOps = 0; |
| for (unsigned I = 0; I != DstINumUses; ++I) { |
| const CGIOperandList::OperandInfo &DstIOperand = |
| DstI->Operands[DstI->Operands.NumDefs + I]; |
| |
| // If the operand has default values, introduce them now. |
| // FIXME: Until we have a decent test case that dictates we should do |
| // otherwise, we're going to assume that operands with default values cannot |
| // be specified in the patterns. Therefore, adding them will not cause us to |
| // end up with too many rendered operands. |
| if (DstIOperand.Rec->isSubClassOf("OperandWithDefaultOps")) { |
| DagInit *DefaultOps = DstIOperand.Rec->getValueAsDag("DefaultOps"); |
| if (auto Error = importDefaultOperandRenderers(DstMIBuilder, DefaultOps)) |
| return std::move(Error); |
| ++NumDefaultOps; |
| continue; |
| } |
| |
| if (auto Error = importExplicitUseRenderer( |
| DstMIBuilder, Dst->getChild(Child), InsnMatcher)) |
| return std::move(Error); |
| ++Child; |
| } |
| |
| if (NumDefaultOps + ExpectedDstINumUses != DstINumUses) |
| return failedImport("Expected " + llvm::to_string(DstINumUses) + |
| " used operands but found " + |
| llvm::to_string(ExpectedDstINumUses) + |
| " explicit ones and " + llvm::to_string(NumDefaultOps) + |
| " default ones"); |
| |
| return DstMIBuilder; |
| } |
| |
| Error GlobalISelEmitter::importDefaultOperandRenderers( |
| BuildMIAction &DstMIBuilder, DagInit *DefaultOps) const { |
| for (const auto *DefaultOp : DefaultOps->getArgs()) { |
| // Look through ValueType operators. |
| if (const DagInit *DefaultDagOp = dyn_cast<DagInit>(DefaultOp)) { |
| if (const DefInit *DefaultDagOperator = |
| dyn_cast<DefInit>(DefaultDagOp->getOperator())) { |
| if (DefaultDagOperator->getDef()->isSubClassOf("ValueType")) |
| DefaultOp = DefaultDagOp->getArg(0); |
| } |
| } |
| |
| if (const DefInit *DefaultDefOp = dyn_cast<DefInit>(DefaultOp)) { |
| DstMIBuilder.addRenderer<AddRegisterRenderer>(0, DefaultDefOp->getDef()); |
| continue; |
| } |
| |
| if (const IntInit *DefaultIntOp = dyn_cast<IntInit>(DefaultOp)) { |
| DstMIBuilder.addRenderer<ImmRenderer>(0, DefaultIntOp->getValue()); |
| continue; |
| } |
| |
| return failedImport("Could not add default op"); |
| } |
| |
| return Error::success(); |
| } |
| |
| Error GlobalISelEmitter::importImplicitDefRenderers( |
| BuildMIAction &DstMIBuilder, |
| const std::vector<Record *> &ImplicitDefs) const { |
| if (!ImplicitDefs.empty()) |
| return failedImport("Pattern defines a physical register"); |
| return Error::success(); |
| } |
| |
| Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) { |
| // Keep track of the matchers and actions to emit. |
| RuleMatcher M; |
| M.addAction<DebugCommentAction>(P); |
| |
| if (auto Error = importRulePredicates(M, P.getPredicates()->getValues())) |
| return std::move(Error); |
| |
| // 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 (auto Err = isTrivialOperatorNode(Dst)) |
| return failedImport("Dst pattern root isn't a trivial operator (" + |
| toString(std::move(Err)) + ")"); |
| if (auto Err = isTrivialOperatorNode(Src)) |
| return failedImport("Src pattern root isn't a trivial operator (" + |
| toString(std::move(Err)) + ")"); |
| |
| if (Dst->isLeaf()) |
| return failedImport("Dst pattern root isn't a known leaf"); |
| |
| // Start with the defined operands (i.e., the results of the root operator). |
| Record *DstOp = Dst->getOperator(); |
| if (!DstOp->isSubClassOf("Instruction")) |
| return failedImport("Pattern operator isn't an instruction"); |
| |
| auto &DstI = Target.getInstruction(DstOp); |
| if (DstI.Operands.NumDefs != Src->getExtTypes().size()) |
| return failedImport("Src pattern results and dst MI defs are different (" + |
| to_string(Src->getExtTypes().size()) + " def(s) vs " + |
| to_string(DstI.Operands.NumDefs) + " def(s))"); |
| |
| InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(); |
| unsigned TempOpIdx = 0; |
| auto InsnMatcherOrError = |
| createAndImportSelDAGMatcher(InsnMatcherTemp, Src, TempOpIdx); |
| if (auto Error = InsnMatcherOrError.takeError()) |
| return std::move(Error); |
| InstructionMatcher &InsnMatcher = InsnMatcherOrError.get(); |
| |
| // The root of the match also has constraints on the register bank so that it |
| // matches the result instruction. |
| unsigned OpIdx = 0; |
| for (const EEVT::TypeSet &Ty : Src->getExtTypes()) { |
| (void)Ty; |
| |
| const auto &DstIOperand = DstI.Operands[OpIdx]; |
| Record *DstIOpRec = DstIOperand.Rec; |
| if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") { |
| DstIOpRec = getInitValueAsRegClass(Dst->getChild(1)->getLeafValue()); |
| |
| if (DstIOpRec == nullptr) |
| return failedImport( |
| "COPY_TO_REGCLASS operand #1 isn't a register class"); |
| } else if (DstI.TheDef->getName() == "EXTRACT_SUBREG") { |
| if (!Dst->getChild(0)->isLeaf()) |
| return failedImport("EXTRACT_SUBREG operand #0 isn't a leaf"); |
| |
| // We can assume that a subregister is in the same bank as it's super |
| // register. |
| DstIOpRec = getInitValueAsRegClass(Dst->getChild(0)->getLeafValue()); |
| |
| if (DstIOpRec == nullptr) |
| return failedImport( |
| "EXTRACT_SUBREG operand #0 isn't a register class"); |
| } else if (DstIOpRec->isSubClassOf("RegisterOperand")) |
| DstIOpRec = DstIOpRec->getValueAsDef("RegClass"); |
| else if (!DstIOpRec->isSubClassOf("RegisterClass")) |
| return failedImport("Dst MI def isn't a register class" + |
| to_string(*Dst)); |
| |
| OperandMatcher &OM = InsnMatcher.getOperand(OpIdx); |
| OM.setSymbolicName(DstIOperand.Name); |
| OM.addPredicate<RegisterBankOperandMatcher>( |
| Target.getRegisterClass(DstIOpRec)); |
| ++OpIdx; |
| } |
| |
| auto DstMIBuilderOrError = |
| createAndImportInstructionRenderer(M, Dst, InsnMatcher); |
| if (auto Error = DstMIBuilderOrError.takeError()) |
| return std::move(Error); |
| BuildMIAction &DstMIBuilder = DstMIBuilderOrError.get(); |
| |
| // Render the implicit defs. |
| // These are only added to the root of the result. |
| if (auto Error = importImplicitDefRenderers(DstMIBuilder, P.getDstRegs())) |
| return std::move(Error); |
| |
| // Constrain the registers to classes. This is normally derived from the |
| // emitted instruction but a few instructions require special handling. |
| if (DstI.TheDef->getName() == "COPY_TO_REGCLASS") { |
| // COPY_TO_REGCLASS does not provide operand constraints itself but the |
| // result is constrained to the class given by the second child. |
| Record *DstIOpRec = |
| getInitValueAsRegClass(Dst->getChild(1)->getLeafValue()); |
| |
| if (DstIOpRec == nullptr) |
| return failedImport("COPY_TO_REGCLASS operand #1 isn't a register class"); |
| |
| M.addAction<ConstrainOperandToRegClassAction>( |
| 0, 0, Target.getRegisterClass(DstIOpRec)); |
| |
| // We're done with this pattern! It's eligible for GISel emission; return |
| // it. |
| ++NumPatternImported; |
| return std::move(M); |
| } |
| |
| if (DstI.TheDef->getName() == "EXTRACT_SUBREG") { |
| // EXTRACT_SUBREG selects into a subregister COPY but unlike most |
| // instructions, the result register class is controlled by the |
| // subregisters of the operand. As a result, we must constrain the result |
| // class rather than check that it's already the right one. |
| if (!Dst->getChild(0)->isLeaf()) |
| return failedImport("EXTRACT_SUBREG child #1 is not a leaf"); |
| |
| DefInit *SubRegInit = dyn_cast<DefInit>(Dst->getChild(1)->getLeafValue()); |
| if (!SubRegInit) |
| return failedImport("EXTRACT_SUBREG child #1 is not a subreg index"); |
| |
| // Constrain the result to the same register bank as the operand. |
| Record *DstIOpRec = |
| getInitValueAsRegClass(Dst->getChild(0)->getLeafValue()); |
| |
| if (DstIOpRec == nullptr) |
| return failedImport("EXTRACT_SUBREG operand #1 isn't a register class"); |
| |
| CodeGenSubRegIndex *SubIdx = CGRegs.getSubRegIdx(SubRegInit->getDef()); |
| CodeGenRegisterClass *SrcRC = CGRegs.getRegClass(DstIOpRec); |
| |
| // It would be nice to leave this constraint implicit but we're required |
| // to pick a register class so constrain the result to a register class |
| // that can hold the correct MVT. |
| // |
| // FIXME: This may introduce an extra copy if the chosen class doesn't |
| // actually contain the subregisters. |
| assert(Src->getExtTypes().size() == 1 && |
| "Expected Src of EXTRACT_SUBREG to have one result type"); |
| |
| const auto &SrcRCDstRCPair = |
| SrcRC->getMatchingSubClassWithSubRegs(CGRegs, SubIdx); |
| assert(SrcRCDstRCPair->second && "Couldn't find a matching subclass"); |
| M.addAction<ConstrainOperandToRegClassAction>(0, 0, *SrcRCDstRCPair->second); |
| M.addAction<ConstrainOperandToRegClassAction>(0, 1, *SrcRCDstRCPair->first); |
| |
| // We're done with this pattern! It's eligible for GISel emission; return |
| // it. |
| ++NumPatternImported; |
| return std::move(M); |
| } |
| |
| M.addAction<ConstrainOperandsToDefinitionAction>(0); |
| |
| // We're done with this pattern! It's eligible for GISel emission; return it. |
| ++NumPatternImported; |
| return std::move(M); |
| } |
| |
| void GlobalISelEmitter::run(raw_ostream &OS) { |
| // Track the GINodeEquiv definitions. |
| gatherNodeEquivs(); |
| |
| emitSourceFileHeader(("Global Instruction Selector for the " + |
| Target.getName() + " target").str(), OS); |
| std::vector<RuleMatcher> Rules; |
| // Look through the SelectionDAG patterns we found, possibly emitting some. |
| for (const PatternToMatch &Pat : CGP.ptms()) { |
| ++NumPatternTotal; |
| auto MatcherOrErr = runOnPattern(Pat); |
| |
| // The pattern analysis can fail, indicating an unsupported pattern. |
| // Report that if we've been asked to do so. |
| if (auto Err = MatcherOrErr.takeError()) { |
| if (WarnOnSkippedPatterns) { |
| PrintWarning(Pat.getSrcRecord()->getLoc(), |
| "Skipped pattern: " + toString(std::move(Err))); |
| } else { |
| consumeError(std::move(Err)); |
| } |
| ++NumPatternImportsSkipped; |
| continue; |
| } |
| |
| Rules.push_back(std::move(MatcherOrErr.get())); |
| } |
| |
| std::stable_sort(Rules.begin(), Rules.end(), |
| [&](const RuleMatcher &A, const RuleMatcher &B) { |
| if (A.isHigherPriorityThan(B)) { |
| assert(!B.isHigherPriorityThan(A) && "Cannot be more important " |
| "and less important at " |
| "the same time"); |
| return true; |
| } |
| return false; |
| }); |
| |
| std::vector<Record *> ComplexPredicates = |
| RK.getAllDerivedDefinitions("GIComplexOperandMatcher"); |
| std::sort(ComplexPredicates.begin(), ComplexPredicates.end(), |
| [](const Record *A, const Record *B) { |
| if (A->getName() < B->getName()) |
| return true; |
| return false; |
| }); |
| unsigned MaxTemporaries = 0; |
| for (const auto &Rule : Rules) |
| MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns()); |
| |
| OS << "#ifdef GET_GLOBALISEL_PREDICATE_BITSET\n" |
| << "const unsigned MAX_SUBTARGET_PREDICATES = " << SubtargetFeatures.size() |
| << ";\n" |
| << "using PredicateBitset = " |
| "llvm::PredicateBitsetImpl<MAX_SUBTARGET_PREDICATES>;\n" |
| << "#endif // ifdef GET_GLOBALISEL_PREDICATE_BITSET\n\n"; |
| |
| OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n" |
| << " mutable MatcherState State;\n" |
| << " typedef " |
| "ComplexRendererFn(" |
| << Target.getName() |
| << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n" |
| << "const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> " |
| "MatcherInfo;\n" |
| << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n"; |
| |
| OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n" |
| << ", State(" << MaxTemporaries << "),\n" |
| << "MatcherInfo({TypeObjects, FeatureBitsets, {\n" |
| << " nullptr, // GICP_Invalid\n"; |
| for (const auto &Record : ComplexPredicates) |
| OS << " &" << Target.getName() |
| << "InstructionSelector::" << Record->getValueAsString("MatcherFn") |
| << ", // " << Record->getName() << "\n"; |
| OS << "}})\n" |
| << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n"; |
| |
| OS << "#ifdef GET_GLOBALISEL_IMPL\n"; |
| SubtargetFeatureInfo::emitSubtargetFeatureBitEnumeration(SubtargetFeatures, |
| OS); |
| |
| // Separate subtarget features by how often they must be recomputed. |
| SubtargetFeatureInfoMap ModuleFeatures; |
| std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(), |
| std::inserter(ModuleFeatures, ModuleFeatures.end()), |
| [](const SubtargetFeatureInfoMap::value_type &X) { |
| return !X.second.mustRecomputePerFunction(); |
| }); |
| SubtargetFeatureInfoMap FunctionFeatures; |
| std::copy_if(SubtargetFeatures.begin(), SubtargetFeatures.end(), |
| std::inserter(FunctionFeatures, FunctionFeatures.end()), |
| [](const SubtargetFeatureInfoMap::value_type &X) { |
| return X.second.mustRecomputePerFunction(); |
| }); |
| |
| SubtargetFeatureInfo::emitComputeAvailableFeatures( |
| Target.getName(), "InstructionSelector", "computeAvailableModuleFeatures", |
| ModuleFeatures, OS); |
| SubtargetFeatureInfo::emitComputeAvailableFeatures( |
| Target.getName(), "InstructionSelector", |
| "computeAvailableFunctionFeatures", FunctionFeatures, OS, |
| "const MachineFunction *MF"); |
| |
| // Emit a table containing the LLT objects needed by the matcher and an enum |
| // for the matcher to reference them with. |
| std::vector<LLTCodeGen> TypeObjects = { |
| LLT::scalar(8), LLT::scalar(16), LLT::scalar(32), |
| LLT::scalar(64), LLT::scalar(80), LLT::vector(8, 1), |
| LLT::vector(16, 1), LLT::vector(32, 1), LLT::vector(64, 1), |
| LLT::vector(8, 8), LLT::vector(16, 8), LLT::vector(32, 8), |
| LLT::vector(64, 8), LLT::vector(4, 16), LLT::vector(8, 16), |
| LLT::vector(16, 16), LLT::vector(32, 16), LLT::vector(2, 32), |
| LLT::vector(4, 32), LLT::vector(8, 32), LLT::vector(16, 32), |
| LLT::vector(2, 64), LLT::vector(4, 64), LLT::vector(8, 64), |
| }; |
| std::sort(TypeObjects.begin(), TypeObjects.end()); |
| OS << "enum {\n"; |
| for (const auto &TypeObject : TypeObjects) { |
| OS << " "; |
| TypeObject.emitCxxEnumValue(OS); |
| OS << ",\n"; |
| } |
| OS << "};\n" |
| << "const static LLT TypeObjects[] = {\n"; |
| for (const auto &TypeObject : TypeObjects) { |
| OS << " "; |
| TypeObject.emitCxxConstructorCall(OS); |
| OS << ",\n"; |
| } |
| OS << "};\n\n"; |
| |
| // Emit a table containing the PredicateBitsets objects needed by the matcher |
| // and an enum for the matcher to reference them with. |
| std::vector<std::vector<Record *>> FeatureBitsets; |
| for (auto &Rule : Rules) |
| FeatureBitsets.push_back(Rule.getRequiredFeatures()); |
| std::sort( |
| FeatureBitsets.begin(), FeatureBitsets.end(), |
| [&](const std::vector<Record *> &A, const std::vector<Record *> &B) { |
| if (A.size() < B.size()) |
| return true; |
| if (A.size() > B.size()) |
| return false; |
| for (const auto &Pair : zip(A, B)) { |
| if (std::get<0>(Pair)->getName() < std::get<1>(Pair)->getName()) |
| return true; |
| if (std::get<0>(Pair)->getName() > std::get<1>(Pair)->getName()) |
| return false; |
| } |
| return false; |
| }); |
| FeatureBitsets.erase( |
| std::unique(FeatureBitsets.begin(), FeatureBitsets.end()), |
| FeatureBitsets.end()); |
| OS << "enum {\n" |
| << " GIFBS_Invalid,\n"; |
| for (const auto &FeatureBitset : FeatureBitsets) { |
| if (FeatureBitset.empty()) |
| continue; |
| OS << " " << getNameForFeatureBitset(FeatureBitset) << ",\n"; |
| } |
| OS << "};\n" |
| << "const static PredicateBitset FeatureBitsets[] {\n" |
| << " {}, // GIFBS_Invalid\n"; |
| for (const auto &FeatureBitset : FeatureBitsets) { |
| if (FeatureBitset.empty()) |
| continue; |
| OS << " {"; |
| for (const auto &Feature : FeatureBitset) { |
| const auto &I = SubtargetFeatures.find(Feature); |
| assert(I != SubtargetFeatures.end() && "Didn't import predicate?"); |
| OS << I->second.getEnumBitName() << ", "; |
| } |
| OS << "},\n"; |
| } |
| OS << "};\n\n"; |
| |
| // Emit complex predicate table and an enum to reference them with. |
| OS << "enum {\n" |
| << " GICP_Invalid,\n"; |
| for (const auto &Record : ComplexPredicates) |
| OS << " GICP_" << Record->getName() << ",\n"; |
| OS << "};\n" |
| << "// See constructor for table contents\n\n"; |
| |
| OS << "bool " << Target.getName() |
| << "InstructionSelector::selectImpl(MachineInstr &I) const {\n" |
| << " MachineFunction &MF = *I.getParent()->getParent();\n" |
| << " MachineRegisterInfo &MRI = MF.getRegInfo();\n" |
| << " // FIXME: This should be computed on a per-function basis rather " |
| "than per-insn.\n" |
| << " AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, " |
| "&MF);\n" |
| << " const PredicateBitset AvailableFeatures = getAvailableFeatures();\n" |
| << " NewMIVector OutMIs;\n" |
| << " State.MIs.clear();\n" |
| << " State.MIs.push_back(&I);\n\n"; |
| |
| for (auto &Rule : Rules) { |
| Rule.emit(OS); |
| ++CurrentMatchTableID; |
| ++NumPatternEmitted; |
| assert(CurrentMatchTableID == NumPatternEmitted && |
| "Statistic deviates from number of emitted tables"); |
| } |
| |
| OS << " return false;\n" |
| << "}\n" |
| << "#endif // ifdef GET_GLOBALISEL_IMPL\n"; |
| |
| OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n" |
| << "PredicateBitset AvailableModuleFeatures;\n" |
| << "mutable PredicateBitset AvailableFunctionFeatures;\n" |
| << "PredicateBitset getAvailableFeatures() const {\n" |
| << " return AvailableModuleFeatures | AvailableFunctionFeatures;\n" |
| << "}\n" |
| << "PredicateBitset\n" |
| << "computeAvailableModuleFeatures(const " << Target.getName() |
| << "Subtarget *Subtarget) const;\n" |
| << "PredicateBitset\n" |
| << "computeAvailableFunctionFeatures(const " << Target.getName() |
| << "Subtarget *Subtarget,\n" |
| << " const MachineFunction *MF) const;\n" |
| << "#endif // ifdef GET_GLOBALISEL_PREDICATES_DECL\n"; |
| |
| OS << "#ifdef GET_GLOBALISEL_PREDICATES_INIT\n" |
| << "AvailableModuleFeatures(computeAvailableModuleFeatures(&STI)),\n" |
| << "AvailableFunctionFeatures()\n" |
| << "#endif // ifdef GET_GLOBALISEL_PREDICATES_INIT\n"; |
| } |
| |
| void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) { |
| if (SubtargetFeatures.count(Predicate) == 0) |
| SubtargetFeatures.emplace( |
| Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size())); |
| } |
| |
| } // end anonymous namespace |
| |
| //===----------------------------------------------------------------------===// |
| |
| namespace llvm { |
| void EmitGlobalISel(RecordKeeper &RK, raw_ostream &OS) { |
| GlobalISelEmitter(RK).run(OS); |
| } |
| } // End llvm namespace |