Index: utils/TableGen/GlobalISelEmitter.cpp =================================================================== --- utils/TableGen/GlobalISelEmitter.cpp +++ utils/TableGen/GlobalISelEmitter.cpp @@ -134,6 +134,7 @@ iterator_range predicates() const { return make_range(predicates_begin(), predicates_end()); } + typename PredicateVec::size_type predicates_size() const { return Predicates.size(); } /// Emit a C++ expression that tests whether all the predicates are met. template @@ -161,12 +162,41 @@ /// * Operand is an MBB. class OperandPredicateMatcher { public: + /// This enum defines the priority that is given to the predicate when + /// generating the matcher code. + /// + /// When all more important distinctions between rules are equal, the order of + /// these definitions is the order the matches will be attempted. + /// + /// The only one that's known to matter at the moment is that OPM_Int must + /// have priority over OPM_RegBank. This is because gMIR represents constants + /// as a register def'd by a G_CONSTANT instruction. + enum PredicateKind { + OPM_LLT, + OPM_RegBank, + OPM_MBB, + }; + +protected: + PredicateKind Kind; + +public: + OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {} virtual ~OperandPredicateMatcher() {} + PredicateKind getKind() const { return Kind; } + /// Emit a C++ expression that checks the predicate for the OpIdx operand of /// the instruction given in InsnVarName. virtual void emitCxxPredicateExpr(raw_ostream &OS, const StringRef OperandExpr) 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) { + return Kind < B.Kind; + }; }; /// Generates code to check that an operand is a particular LLT. @@ -175,12 +205,33 @@ std::string Ty; public: - LLTOperandMatcher(std::string Ty) : Ty(Ty) {} + LLTOperandMatcher(std::string Ty) + : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {} + + static bool classof(const OperandPredicateMatcher *P) { + return P->getKind() == OPM_LLT; + } void emitCxxPredicateExpr(raw_ostream &OS, const StringRef OperandExpr) const override { OS << "MRI.getType(" << OperandExpr << ".getReg()) == (" << Ty << ")"; } + + bool isHigherPriorityThan(const OperandPredicateMatcher &B) override { + if (OperandPredicateMatcher::isHigherPriorityThan(B)) + return true; + + // Wider types should have priority over narrower types within the same + // family but the order of the families doesn't matter. So s64 is more + // important than s32 and f64 is more important than f32 but s64 and f64 are + // unordered. + // FIXME: Don't do a lexical comparison of the type name. Check the size + // instead. This only works for the cases we emit so far and is only + // done this way because we can't delve into LLT's yet. + if (Kind == B.getKind()) + return Ty > static_cast(B).Ty; + return false; + }; }; /// Generates code to check that an operand is in a particular register bank. @@ -189,7 +240,12 @@ const CodeGenRegisterClass &RC; public: - RegisterBankOperandMatcher(const CodeGenRegisterClass &RC) : RC(RC) {} + RegisterBankOperandMatcher(const CodeGenRegisterClass &RC) + : OperandPredicateMatcher(OPM_RegBank), RC(RC) {} + + static bool classof(const OperandPredicateMatcher *P) { + return P->getKind() == OPM_RegBank; + } void emitCxxPredicateExpr(raw_ostream &OS, const StringRef OperandExpr) const override { @@ -202,6 +258,12 @@ /// 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 emitCxxPredicateExpr(raw_ostream &OS, const StringRef OperandExpr) const override { OS << OperandExpr << ".isMBB()"; @@ -227,6 +289,23 @@ emitCxxPredicateListExpr(OS, getOperandExpr(InsnVarName)); OS << ")"; } + + /// 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; + + // 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; + } + + return false; + }; }; /// Generates code to check a predicate on an instruction. @@ -235,13 +314,34 @@ /// * The opcode of the instruction is a particular value. /// * The nsw/nuw flag is/isn't set. class InstructionPredicateMatcher { +protected: + /// This enum defines the priority that is given to the predicate when + /// generating the matcher code. + /// + /// When all more important distinctions between rules are equal, the order of + /// these definitions is the order the matches will be attempted. + enum PredicateKind { + IPM_Opcode, + }; + + PredicateKind Kind; + public: virtual ~InstructionPredicateMatcher() {} + PredicateKind getKind() const { return Kind; } + /// Emit a C++ expression that tests whether the instruction named in /// InsnVarName matches the predicate. virtual void emitCxxPredicateExpr(raw_ostream &OS, const StringRef InsnVarName) const = 0; + + /// Compare the priority of this object and B. + /// + /// Returns true if this object is more important than B. + bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const { + return Kind < B.Kind; + }; }; /// Generates code to check the opcode of an instruction. @@ -252,11 +352,32 @@ public: InstructionOpcodeMatcher(const CodeGenInstruction *I) : I(I) {} + static bool classof(const InstructionPredicateMatcher *P) { + return P->getKind() == IPM_Opcode; + } + void emitCxxPredicateExpr(raw_ostream &OS, const StringRef InsnVarName) const override { OS << InsnVarName << ".getOpcode() == " << I->Namespace << "::" << I->TheDef->getName(); } + + /// Compare the priority of this object and B. + /// + /// Returns true if is more important than B. + bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const { + if (InstructionPredicateMatcher::isHigherPriorityThan(B)) + return true; + + // 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(&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 @@ -287,6 +408,27 @@ OS << ")"; } } + + /// 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; + + for (const auto &Predicate : zip(predicates(), B.predicates())) { + if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate))) + return true; + } + + for (const auto &Operand : zip(Operands, B.Operands)) { + if (std::get<0>(Operand).isHigherPriorityThan(std::get<1>(Operand))) + return true; + } + + return false; + }; }; } // end anonymous namespace @@ -387,6 +529,22 @@ OS << " return true;\n"; OS << " }\n\n"; } + + /// Compare the priority of this object and B. + /// + /// Returns true if this object is more important than B. + bool isHigherPriorityThan(const RuleMatcher &B) const { + // Rules involving more match roots have higher priority. + if (Matchers.size() > B.Matchers.size()) + return true; + + for (const auto &Matcher : zip(Matchers, B.Matchers)) { + if (std::get<0>(Matcher)->isHigherPriorityThan(*std::get<1>(Matcher))) + return true; + } + + return false; + }; }; } // end anonymous namespace @@ -561,6 +719,11 @@ } } + std::sort(Rules.begin(), Rules.end(), + [](const RuleMatcher &A, const RuleMatcher &B) { + return A.isHigherPriorityThan(B); + }); + for (const auto &Rule : Rules) { // We're done with this pattern! Emit the processed result. Rule.emit(OS);