diff options
Diffstat (limited to 'contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp')
| -rw-r--r-- | contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp | 1787 |
1 files changed, 1306 insertions, 481 deletions
diff --git a/contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp b/contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp index c7d662db5a2f..69726cc9f257 100644 --- a/contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp +++ b/contrib/llvm/utils/TableGen/GlobalISelEmitter.cpp @@ -35,11 +35,11 @@ #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" -#include "llvm/CodeGen/MachineValueType.h" #include "llvm/Support/CodeGenCoverage.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Error.h" #include "llvm/Support/LowLevelTypeImpl.h" +#include "llvm/Support/MachineValueType.h" #include "llvm/Support/ScopedPrinter.h" #include "llvm/TableGen/Error.h" #include "llvm/TableGen/Record.h" @@ -84,6 +84,8 @@ namespace { /// Get the name of the enum value used to number the predicate function. std::string getEnumNameForPredicate(const TreePredicateFn &Predicate) { + if (Predicate.hasGISelPredicateCode()) + return "GIPFP_MI_" + Predicate.getFnName(); return "GIPFP_" + Predicate.getImmTypeIdentifier().str() + "_" + Predicate.getFnName(); } @@ -100,6 +102,7 @@ private: LLT Ty; public: + LLTCodeGen() = default; LLTCodeGen(const LLT &Ty) : Ty(Ty) {} std::string getCxxEnumValue() const { @@ -148,7 +151,7 @@ public: const LLT &get() const { return Ty; } - /// This ordering is used for std::unique() and std::sort(). There's no + /// This ordering is used for std::unique() and llvm::sort(). There's no /// particular logic behind the order but either A < B or B < A must be /// true if A != B. bool operator<(const LLTCodeGen &Other) const { @@ -176,6 +179,9 @@ public: bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; } }; +// Track all types that are used so we can emit the corresponding enum. +std::set<LLTCodeGen> KnownTypes; + 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, ...). @@ -260,6 +266,11 @@ std::string explainOperator(Record *Operator) { ")") .str(); + if (Operator->isSubClassOf("SDNodeXForm")) + return (" (Operator is an unmapped SDNodeXForm, " + Operator->getName() + + ")") + .str(); + return (" (Operator " + Operator->getName() + " not understood)").str(); } @@ -280,12 +291,16 @@ static Error isTrivialOperatorNode(const TreePatternNode *N) { if (Predicate.isImmediatePattern()) continue; - if (Predicate.isNonExtLoad()) + if (Predicate.isNonExtLoad() || Predicate.isAnyExtLoad() || + Predicate.isSignExtLoad() || Predicate.isZeroExtLoad()) continue; if (Predicate.isNonTruncStore()) continue; + if (Predicate.isLoad() && Predicate.getMemoryVT()) + continue; + if (Predicate.isLoad() || Predicate.isStore()) { if (Predicate.isUnindexed()) continue; @@ -306,6 +321,9 @@ static Error isTrivialOperatorNode(const TreePatternNode *N) { Predicate.isAtomicOrderingWeakerThanRelease())) continue; + if (Predicate.hasGISelPredicateCode()) + continue; + HasUnsupportedPredicate = true; Explanation = Separator + "Has a predicate (" + explainPredicates(N) + ")"; Separator = ", "; @@ -315,12 +333,7 @@ static Error isTrivialOperatorNode(const TreePatternNode *N) { break; } - if (N->getTransformFn()) { - Explanation += Separator + "Has a transform function"; - Separator = ", "; - } - - if (!HasUnsupportedPredicate && !N->getTransformFn()) + if (!HasUnsupportedPredicate) return Error::success(); return failedImport(Explanation); @@ -394,19 +407,42 @@ public: /// A bitfield of RecordFlagsBits flags. unsigned Flags; + /// The actual run-time value, if known + int64_t RawValue; + MatchTableRecord(Optional<unsigned> LabelID_, StringRef EmitStr, - unsigned NumElements, unsigned Flags) + unsigned NumElements, unsigned Flags, + int64_t RawValue = std::numeric_limits<int64_t>::min()) : LabelID(LabelID_.hasValue() ? LabelID_.getValue() : ~0u), - EmitStr(EmitStr), NumElements(NumElements), Flags(Flags) { + EmitStr(EmitStr), NumElements(NumElements), Flags(Flags), + RawValue(RawValue) { + assert((!LabelID_.hasValue() || LabelID != ~0u) && "This value is reserved for non-labels"); } + MatchTableRecord(const MatchTableRecord &Other) = default; + MatchTableRecord(MatchTableRecord &&Other) = default; + + /// Useful if a Match Table Record gets optimized out + void turnIntoComment() { + Flags |= MTRF_Comment; + Flags &= ~MTRF_CommaFollows; + NumElements = 0; + } + + /// For Jump Table generation purposes + bool operator<(const MatchTableRecord &Other) const { + return RawValue < Other.RawValue; + } + int64_t getRawValue() const { return RawValue; } void emit(raw_ostream &OS, bool LineBreakNextAfterThis, const MatchTable &Table) const; unsigned size() const { return NumElements; } }; +class Matcher; + /// Holds the contents of a generated MatchTable to enable formatting and the /// necessary index tracking needed to support GIM_Try. class MatchTable { @@ -419,10 +455,11 @@ class MatchTable { /// The currently defined labels. DenseMap<unsigned, unsigned> LabelMap; /// Tracks the sum of MatchTableRecord::NumElements as the table is built. - unsigned CurrentSize; - + unsigned CurrentSize = 0; /// A unique identifier for a MatchTable label. - static unsigned CurrentLabelID; + unsigned CurrentLabelID = 0; + /// Determines if the table should be instrumented for rule coverage tracking. + bool IsWithCoverage; public: static MatchTableRecord LineBreak; @@ -443,11 +480,20 @@ public: return MatchTableRecord(None, NamedValue, 1, MatchTableRecord::MTRF_CommaFollows); } + static MatchTableRecord NamedValue(StringRef NamedValue, int64_t RawValue) { + return MatchTableRecord(None, NamedValue, 1, + MatchTableRecord::MTRF_CommaFollows, RawValue); + } static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue) { return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1, MatchTableRecord::MTRF_CommaFollows); } + static MatchTableRecord NamedValue(StringRef Namespace, StringRef NamedValue, + int64_t RawValue) { + return MatchTableRecord(None, (Namespace + "::" + NamedValue).str(), 1, + MatchTableRecord::MTRF_CommaFollows, RawValue); + } static MatchTableRecord IntValue(int64_t IntValue) { return MatchTableRecord(None, llvm::to_string(IntValue), 1, MatchTableRecord::MTRF_CommaFollows); @@ -465,7 +511,12 @@ public: MatchTableRecord::MTRF_CommaFollows); } - MatchTable(unsigned ID) : ID(ID), CurrentSize(0) {} + static MatchTable buildTable(ArrayRef<Matcher *> Rules, bool WithCoverage); + + MatchTable(bool WithCoverage, unsigned ID = 0) + : ID(ID), IsWithCoverage(WithCoverage) {} + + bool isWithCoverage() const { return IsWithCoverage; } void push_back(const MatchTableRecord &Value) { if (Value.Flags & MatchTableRecord::MTRF_Label) @@ -474,7 +525,7 @@ public: CurrentSize += Value.size(); } - unsigned allocateLabelID() const { return CurrentLabelID++; } + unsigned allocateLabelID() { return CurrentLabelID++; } void defineLabel(unsigned LabelID) { LabelMap.insert(std::make_pair(LabelID, CurrentSize)); @@ -519,8 +570,6 @@ public: } }; -unsigned MatchTable::CurrentLabelID = 0; - MatchTableRecord MatchTable::LineBreak = { None, "" /* Emit String */, 0 /* Elements */, MatchTableRecord::MTRF_LineBreakFollows}; @@ -573,65 +622,172 @@ class RuleMatcher; class Matcher { public: virtual ~Matcher() = default; + virtual void optimize() {} virtual void emit(MatchTable &Table) = 0; - virtual std::unique_ptr<PredicateMatcher> forgetFirstCondition() = 0; + + virtual bool hasFirstCondition() const = 0; + virtual const PredicateMatcher &getFirstCondition() const = 0; + virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0; }; -class GroupMatcher : public Matcher { - SmallVector<std::unique_ptr<PredicateMatcher>, 8> Conditions; - SmallVector<Matcher *, 8> Rules; +MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules, + bool WithCoverage) { + MatchTable Table(WithCoverage); + for (Matcher *Rule : Rules) + Rule->emit(Table); + + return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; +} + +class GroupMatcher final : public Matcher { + /// Conditions that form a common prefix of all the matchers contained. + SmallVector<std::unique_ptr<PredicateMatcher>, 1> Conditions; + + /// All the nested matchers, sharing a common prefix. + std::vector<Matcher *> Matchers; + + /// An owning collection for any auxiliary matchers created while optimizing + /// nested matchers contained. + std::vector<std::unique_ptr<Matcher>> MatcherStorage; public: - void addCondition(std::unique_ptr<PredicateMatcher> &&Predicate) { - Conditions.emplace_back(std::move(Predicate)); + /// Add a matcher to the collection of nested matchers if it meets the + /// requirements, and return true. If it doesn't, do nothing and return false. + /// + /// Expected to preserve its argument, so it could be moved out later on. + bool addMatcher(Matcher &Candidate); + + /// Mark the matcher as fully-built and ensure any invariants expected by both + /// optimize() and emit(...) methods. Generally, both sequences of calls + /// are expected to lead to a sensible result: + /// + /// addMatcher(...)*; finalize(); optimize(); emit(...); and + /// addMatcher(...)*; finalize(); emit(...); + /// + /// or generally + /// + /// addMatcher(...)*; finalize(); { optimize()*; emit(...); }* + /// + /// Multiple calls to optimize() are expected to be handled gracefully, though + /// optimize() is not expected to be idempotent. Multiple calls to finalize() + /// aren't generally supported. emit(...) is expected to be non-mutating and + /// producing the exact same results upon repeated calls. + /// + /// addMatcher() calls after the finalize() call are not supported. + /// + /// finalize() and optimize() are both allowed to mutate the contained + /// matchers, so moving them out after finalize() is not supported. + void finalize(); + void optimize() override; + void emit(MatchTable &Table) override; + + /// Could be used to move out the matchers added previously, unless finalize() + /// has been already called. If any of the matchers are moved out, the group + /// becomes safe to destroy, but not safe to re-use for anything else. + iterator_range<std::vector<Matcher *>::iterator> matchers() { + return make_range(Matchers.begin(), Matchers.end()); } - void addRule(Matcher &Rule) { Rules.push_back(&Rule); } - const std::unique_ptr<PredicateMatcher> &conditions_back() const { - return Conditions.back(); + size_t size() const { return Matchers.size(); } + bool empty() const { return Matchers.empty(); } + + std::unique_ptr<PredicateMatcher> popFirstCondition() override { + assert(!Conditions.empty() && + "Trying to pop a condition from a condition-less group"); + std::unique_ptr<PredicateMatcher> P = std::move(Conditions.front()); + Conditions.erase(Conditions.begin()); + return P; } - bool lastConditionMatches(const PredicateMatcher &Predicate) const; - bool conditions_empty() const { return Conditions.empty(); } - void clear() { - Conditions.clear(); - Rules.clear(); + const PredicateMatcher &getFirstCondition() const override { + assert(!Conditions.empty() && + "Trying to get a condition from a condition-less group"); + return *Conditions.front(); } + bool hasFirstCondition() const override { return !Conditions.empty(); } + +private: + /// See if a candidate matcher could be added to this group solely by + /// analyzing its first condition. + bool candidateConditionMatches(const PredicateMatcher &Predicate) const; +}; + +class SwitchMatcher : public Matcher { + /// All the nested matchers, representing distinct switch-cases. The first + /// conditions (as Matcher::getFirstCondition() reports) of all the nested + /// matchers must share the same type and path to a value they check, in other + /// words, be isIdenticalDownToValue, but have different values they check + /// against. + std::vector<Matcher *> Matchers; + + /// The representative condition, with a type and a path (InsnVarID and OpIdx + /// in most cases) shared by all the matchers contained. + std::unique_ptr<PredicateMatcher> Condition = nullptr; + + /// Temporary set used to check that the case values don't repeat within the + /// same switch. + std::set<MatchTableRecord> Values; + + /// An owning collection for any auxiliary matchers created while optimizing + /// nested matchers contained. + std::vector<std::unique_ptr<Matcher>> MatcherStorage; + +public: + bool addMatcher(Matcher &Candidate); + + void finalize(); void emit(MatchTable &Table) override; - std::unique_ptr<PredicateMatcher> forgetFirstCondition() override { - // We shouldn't need to mess up with groups, since we - // should have merged everything shareable upfront. - // If we start to look into reordering predicates, - // we may want to reconsider this. - assert(0 && "Groups should be formed maximal for now"); - llvm_unreachable("No need for this for now"); + iterator_range<std::vector<Matcher *>::iterator> matchers() { + return make_range(Matchers.begin(), Matchers.end()); } + size_t size() const { return Matchers.size(); } + bool empty() const { return Matchers.empty(); } + + std::unique_ptr<PredicateMatcher> popFirstCondition() override { + // SwitchMatcher doesn't have a common first condition for its cases, as all + // the cases only share a kind of a value (a type and a path to it) they + // match, but deliberately differ in the actual value they match. + llvm_unreachable("Trying to pop a condition from a condition-less group"); + } + const PredicateMatcher &getFirstCondition() const override { + llvm_unreachable("Trying to pop a condition from a condition-less group"); + } + bool hasFirstCondition() const override { return false; } + +private: + /// See if the predicate type has a Switch-implementation for it. + static bool isSupportedPredicateType(const PredicateMatcher &Predicate); + + bool candidateConditionMatches(const PredicateMatcher &Predicate) const; + + /// emit()-helper + static void emitPredicateSpecificOpcodes(const PredicateMatcher &P, + MatchTable &Table); }; /// Generates code to check that a match rule matches. class RuleMatcher : public Matcher { public: - using ActionVec = std::vector<std::unique_ptr<MatchAction>>; - using action_iterator = ActionVec::iterator; + using ActionList = std::list<std::unique_ptr<MatchAction>>; + using action_iterator = ActionList::iterator; protected: /// 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; + using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ; + MatchersTy Matchers; /// A list of actions that need to be taken when all predicates in this rule /// have succeeded. - ActionVec Actions; + ActionList Actions; - using DefinedInsnVariablesMap = - std::map<const InstructionMatcher *, unsigned>; + using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>; - /// A map of instruction matchers to the local variables created by - /// emitCaptureOpcodes(). + /// A map of instruction matchers to the local variables DefinedInsnVariablesMap InsnVariableIDs; - using MutatableInsnSet = SmallPtrSet<const InstructionMatcher *, 4>; + using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>; // The set of instruction matchers that have not yet been claimed for mutation // by a BuildMI. @@ -641,7 +797,7 @@ protected: /// the renderers. StringMap<OperandMatcher *> DefinedOperands; - /// ID for the next instruction variable defined with defineInsnVar() + /// ID for the next instruction variable defined with implicitlyDefineInsnVar() unsigned NextInsnVarID; /// ID for the next output instruction allocated with allocateOutputInsnID() @@ -651,6 +807,7 @@ protected: unsigned NextTempRegID; std::vector<Record *> RequiredFeatures; + std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers; ArrayRef<SMLoc> SrcLoc; @@ -684,16 +841,9 @@ public: action_iterator insertAction(action_iterator InsertPt, 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); - void clearImplicitMap() { - NextInsnVarID = 0; - InsnVariableIDs.clear(); - }; - /// Define an instruction and emit corresponding state-machine opcodes. - unsigned defineInsnVar(MatchTable &Table, const InstructionMatcher &Matcher, - unsigned InsnVarID, unsigned OpIdx); - unsigned getInsnVarID(const InstructionMatcher &InsnMatcher) const; + unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher); + + unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const; DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const { return InsnVariableIDs.begin(); } @@ -715,7 +865,7 @@ public: mutatable_insns() const { return make_range(mutatable_insns_begin(), mutatable_insns_end()); } - void reserveInsnMatcherForMutation(const InstructionMatcher *InsnMatcher) { + void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) { bool R = MutatableInsns.erase(InsnMatcher); assert(R && "Reserving a mutatable insn that isn't available"); (void)R; @@ -743,11 +893,10 @@ public: return I->second; } - const InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const; + InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const; const OperandMatcher &getOperandMatcher(StringRef Name) const; - void emitCaptureOpcodes(MatchTable &Table); - + void optimize() override; void emit(MatchTable &Table) override; /// Compare the priority of this object and B. @@ -759,7 +908,12 @@ public: /// matcher. unsigned countRendererFns() const; - std::unique_ptr<PredicateMatcher> forgetFirstCondition() override; + std::unique_ptr<PredicateMatcher> popFirstCondition() override; + const PredicateMatcher &getFirstCondition() const override; + LLTCodeGen getFirstConditionAsRootType(); + bool hasFirstCondition() const override; + unsigned getNumOperands() const; + StringRef getOpcode() const; // FIXME: Remove this as soon as possible InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); } @@ -767,6 +921,9 @@ public: unsigned allocateOutputInsnID() { return NextOutputInsnID++; } unsigned allocateTempRegID() { return NextTempRegID++; } + iterator_range<MatchersTy::iterator> insnmatchers() { + return make_range(Matchers.begin(), Matchers.end()); + } bool insnmatchers_empty() const { return Matchers.empty(); } void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); } }; @@ -777,58 +934,69 @@ using action_iterator = RuleMatcher::action_iterator; template <class PredicateTy> class PredicateListMatcher { private: - typedef std::vector<std::unique_ptr<PredicateTy>> PredicateVec; - PredicateVec Predicates; - /// Template instantiations should specialize this to return a string to use /// for the comment emitted when there are no predicates. std::string getNoPredicateComment() const; +protected: + using PredicatesTy = std::deque<std::unique_ptr<PredicateTy>>; + PredicatesTy Predicates; + + /// Track if the list of predicates was manipulated by one of the optimization + /// methods. + bool Optimized = false; + public: - /// Construct a new operand predicate and add it to the matcher. + /// Construct a new predicate and add it to the matcher. template <class Kind, class... Args> - Optional<Kind *> addPredicate(Args&&... args) { - Predicates.emplace_back( - llvm::make_unique<Kind>(std::forward<Args>(args)...)); - return static_cast<Kind *>(Predicates.back().get()); - } + Optional<Kind *> addPredicate(Args &&... args); - typename PredicateVec::const_iterator predicates_begin() const { + typename PredicatesTy::iterator predicates_begin() { return Predicates.begin(); } - typename PredicateVec::const_iterator predicates_end() const { + typename PredicatesTy::iterator predicates_end() { return Predicates.end(); } - iterator_range<typename PredicateVec::const_iterator> predicates() const { + iterator_range<typename PredicatesTy::iterator> predicates() { return make_range(predicates_begin(), predicates_end()); } - typename PredicateVec::size_type predicates_size() const { + typename PredicatesTy::size_type predicates_size() const { return Predicates.size(); } bool predicates_empty() const { return Predicates.empty(); } std::unique_ptr<PredicateTy> predicates_pop_front() { std::unique_ptr<PredicateTy> Front = std::move(Predicates.front()); - Predicates.erase(Predicates.begin()); + Predicates.pop_front(); + Optimized = true; return Front; } + void prependPredicate(std::unique_ptr<PredicateTy> &&Predicate) { + Predicates.push_front(std::move(Predicate)); + } + + void eraseNullPredicates() { + const auto NewEnd = + std::stable_partition(Predicates.begin(), Predicates.end(), + std::logical_not<std::unique_ptr<PredicateTy>>()); + if (NewEnd != Predicates.begin()) { + Predicates.erase(Predicates.begin(), NewEnd); + Optimized = true; + } + } + /// Emit MatchTable opcodes that tests whether all the predicates are met. template <class... Args> - void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) const { - if (Predicates.empty()) { + void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) { + if (Predicates.empty() && !Optimized) { Table << MatchTable::Comment(getNoPredicateComment()) << MatchTable::LineBreak; return; } - unsigned OpIdx = (*predicates_begin())->getOpIdx(); - (void)OpIdx; - for (const auto &Predicate : predicates()) { - assert(Predicate->getOpIdx() == OpIdx && - "Checks touch different operands?"); + for (const auto &Predicate : predicates()) Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...); - } } }; @@ -846,8 +1014,12 @@ public: /// are currently not compared between each other. enum PredicateKind { IPM_Opcode, + IPM_NumOperands, IPM_ImmPredicate, IPM_AtomicOrderingMMO, + IPM_MemoryLLTSize, + IPM_MemoryVsLLTSize, + IPM_GenericPredicate, OPM_SameOperand, OPM_ComplexPattern, OPM_IntrinsicID, @@ -869,7 +1041,9 @@ public: PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0) : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {} + unsigned getInsnVarID() const { return InsnVarID; } unsigned getOpIdx() const { return OpIdx; } + virtual ~PredicateMatcher() = default; /// Emit MatchTable opcodes that check the predicate for the given operand. virtual void emitPredicateOpcodes(MatchTable &Table, @@ -878,16 +1052,23 @@ public: PredicateKind getKind() const { return Kind; } virtual bool isIdentical(const PredicateMatcher &B) const { - if (InsnVarID != 0 || OpIdx != (unsigned)~0) { - // We currently don't hoist the record of instruction properly. - // Therefore we can only work on the orig instruction (InsnVarID - // == 0). - DEBUG(dbgs() << "Non-zero instr ID not supported yet\n"); - return false; - } return B.getKind() == getKind() && InsnVarID == B.InsnVarID && OpIdx == B.OpIdx; } + + virtual bool isIdenticalDownToValue(const PredicateMatcher &B) const { + return hasValue() && PredicateMatcher::isIdentical(B); + } + + virtual MatchTableRecord getValue() const { + assert(hasValue() && "Can not get a value of a value-less predicate!"); + llvm_unreachable("Not implemented yet"); + } + virtual bool hasValue() const { return false; } + + /// Report the maximum number of temporary operands needed by the predicate + /// matcher. + virtual unsigned countRendererFns() const { return 0; } }; /// Generates code to check a predicate of an operand. @@ -903,20 +1084,10 @@ public: : PredicateMatcher(Kind, InsnVarID, OpIdx) {} virtual ~OperandPredicateMatcher() {} - /// 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(MatchTable &Table, RuleMatcher &Rule) const {} - /// 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; - - /// Report the maximum number of temporary operands needed by the predicate - /// matcher. - virtual unsigned countRendererFns() const { return 0; } }; template <> @@ -935,12 +1106,17 @@ public: : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx), MatchingName(MatchingName) {} - static bool classof(const OperandPredicateMatcher *P) { + static bool classof(const PredicateMatcher *P) { return P->getKind() == OPM_SameOperand; } void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const override; + + bool isIdentical(const PredicateMatcher &B) const override { + return OperandPredicateMatcher::isIdentical(B) && + MatchingName == cast<SameOperandMatcher>(&B)->MatchingName; + } }; /// Generates code to check that an operand is a particular LLT. @@ -949,7 +1125,15 @@ protected: LLTCodeGen Ty; public: - static std::set<LLTCodeGen> KnownTypes; + static std::map<LLTCodeGen, unsigned> TypeIDValues; + + static void initTypeIDValuesMap() { + TypeIDValues.clear(); + + unsigned ID = 0; + for (const LLTCodeGen LLTy : KnownTypes) + TypeIDValues[LLTy] = ID++; + } LLTOperandMatcher(unsigned InsnVarID, unsigned OpIdx, const LLTCodeGen &Ty) : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) { @@ -963,18 +1147,30 @@ public: return OperandPredicateMatcher::isIdentical(B) && Ty == cast<LLTOperandMatcher>(&B)->Ty; } + MatchTableRecord getValue() const override { + const auto VI = TypeIDValues.find(Ty); + if (VI == TypeIDValues.end()) + return MatchTable::NamedValue(getTy().getCxxEnumValue()); + return MatchTable::NamedValue(getTy().getCxxEnumValue(), VI->second); + } + bool hasValue() const override { + if (TypeIDValues.size() != KnownTypes.size()) + initTypeIDValuesMap(); + return TypeIDValues.count(Ty); + } + + LLTCodeGen getTy() const { return Ty; } void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { Table << MatchTable::Opcode("GIM_CheckType") << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx) << MatchTable::Comment("Type") - << MatchTable::NamedValue(Ty.getCxxEnumValue()) - << MatchTable::LineBreak; + << getValue() << MatchTable::LineBreak; } }; -std::set<LLTCodeGen> LLTOperandMatcher::KnownTypes; +std::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues; /// Generates code to check that an operand is a pointer to any address space. /// @@ -1207,7 +1403,18 @@ public: assert(SymbolicName.empty() && "Operand already has a symbolic name"); SymbolicName = Name; } - unsigned getOperandIndex() const { return OpIdx; } + + /// Construct a new operand predicate and add it to the matcher. + template <class Kind, class... Args> + Optional<Kind *> addPredicate(Args &&... args) { + if (isSameAsAnotherOperand()) + return None; + Predicates.emplace_back(llvm::make_unique<Kind>( + getInsnVarID(), getOpIdx(), std::forward<Args>(args)...)); + return static_cast<Kind *>(Predicates.back().get()); + } + + unsigned getOpIdx() const { return OpIdx; } unsigned getInsnVarID() const; std::string getOperandExpr(unsigned InsnVarID) const { @@ -1220,23 +1427,19 @@ public: Error addTypeCheckPredicate(const TypeSetByHwMode &VTy, bool OperandIsAPointer); - /// Emit MatchTable opcodes to capture instructions into the MIs table. - void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const { - for (const auto &Predicate : predicates()) - Predicate->emitCaptureOpcodes(Table, Rule); - } - /// Emit MatchTable opcodes that test whether the instruction named in /// InsnVarID matches all the predicates and all the operands. - void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const { - std::string Comment; - raw_string_ostream CommentOS(Comment); - CommentOS << "MIs[" << getInsnVarID() << "] "; - if (SymbolicName.empty()) - CommentOS << "Operand " << OpIdx; - else - CommentOS << SymbolicName; - Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak; + void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) { + if (!Optimized) { + std::string Comment; + raw_string_ostream CommentOS(Comment); + CommentOS << "MIs[" << getInsnVarID() << "] "; + if (SymbolicName.empty()) + CommentOS << "Operand " << OpIdx; + else + CommentOS << SymbolicName; + Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak; + } emitPredicateListOpcodes(Table, Rule); } @@ -1244,7 +1447,7 @@ public: /// Compare the priority of this object and B. /// /// Returns true if this object is more important than B. - bool isHigherPriorityThan(const OperandMatcher &B) const { + bool isHigherPriorityThan(OperandMatcher &B) { // Operand matchers involving more predicates have higher priority. if (predicates_size() > B.predicates_size()) return true; @@ -1252,7 +1455,7 @@ public: return false; // This assumes that predicates are added in a consistent order. - for (const auto &Predicate : zip(predicates(), B.predicates())) { + for (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))) @@ -1264,7 +1467,7 @@ public: /// Report the maximum number of temporary operands needed by the operand /// matcher. - unsigned countRendererFns() const { + unsigned countRendererFns() { return std::accumulate( predicates().begin(), predicates().end(), 0, [](unsigned A, @@ -1277,7 +1480,7 @@ public: return AllocatedTemporariesBaseID; } - bool isSameAsAnotherOperand() const { + bool isSameAsAnotherOperand() { for (const auto &Predicate : predicates()) if (isa<SameOperandMatcher>(Predicate)) return true; @@ -1285,21 +1488,6 @@ public: } }; -// Specialize OperandMatcher::addPredicate() to refrain from adding redundant -// predicates. -template <> -template <class Kind, class... Args> -Optional<Kind *> -PredicateListMatcher<OperandPredicateMatcher>::addPredicate(Args &&... args) { - auto *OpMatcher = static_cast<OperandMatcher *>(this); - if (static_cast<OperandMatcher *>(this)->isSameAsAnotherOperand()) - return None; - Predicates.emplace_back(llvm::make_unique<Kind>(OpMatcher->getInsnVarID(), - OpMatcher->getOperandIndex(), - std::forward<Args>(args)...)); - return static_cast<Kind *>(Predicates.back().get()); -} - Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy, bool OperandIsAPointer) { if (!VTy.isMachineValueType()) @@ -1343,15 +1531,11 @@ public: 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; } }; template <> std::string -PredicateListMatcher<InstructionPredicateMatcher>::getNoPredicateComment() const { +PredicateListMatcher<PredicateMatcher>::getNoPredicateComment() const { return "No instruction predicates"; } @@ -1360,7 +1544,17 @@ class InstructionOpcodeMatcher : public InstructionPredicateMatcher { protected: const CodeGenInstruction *I; + static DenseMap<const CodeGenInstruction *, unsigned> OpcodeValues; + public: + static void initOpcodeValuesMap(const CodeGenTarget &Target) { + OpcodeValues.clear(); + + unsigned OpcodeValue = 0; + for (const CodeGenInstruction *I : Target.getInstructionsByEnumValue()) + OpcodeValues[I] = OpcodeValue++; + } + InstructionOpcodeMatcher(unsigned InsnVarID, const CodeGenInstruction *I) : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), I(I) {} @@ -1372,12 +1566,19 @@ public: return InstructionPredicateMatcher::isIdentical(B) && I == cast<InstructionOpcodeMatcher>(&B)->I; } + MatchTableRecord getValue() const override { + const auto VI = OpcodeValues.find(I); + if (VI != OpcodeValues.end()) + return MatchTable::NamedValue(I->Namespace, I->TheDef->getName(), + VI->second); + return MatchTable::NamedValue(I->Namespace, I->TheDef->getName()); + } + bool hasValue() const override { return OpcodeValues.count(I); } void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI") - << MatchTable::IntValue(InsnVarID) - << MatchTable::NamedValue(I->Namespace, I->TheDef->getName()) + << MatchTable::IntValue(InsnVarID) << getValue() << MatchTable::LineBreak; } @@ -1404,6 +1605,42 @@ public: bool isConstantInstruction() const { return I->TheDef->getName() == "G_CONSTANT"; } + + StringRef getOpcode() const { return I->TheDef->getName(); } + unsigned getNumOperands() const { return I->Operands.size(); } + + StringRef getOperandType(unsigned OpIdx) const { + return I->Operands[OpIdx].OperandType; + } +}; + +DenseMap<const CodeGenInstruction *, unsigned> + InstructionOpcodeMatcher::OpcodeValues; + +class InstructionNumOperandsMatcher final : public InstructionPredicateMatcher { + unsigned NumOperands = 0; + +public: + InstructionNumOperandsMatcher(unsigned InsnVarID, unsigned NumOperands) + : InstructionPredicateMatcher(IPM_NumOperands, InsnVarID), + NumOperands(NumOperands) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_NumOperands; + } + + bool isIdentical(const PredicateMatcher &B) const override { + return InstructionPredicateMatcher::isIdentical(B) && + NumOperands == cast<InstructionNumOperandsMatcher>(&B)->NumOperands; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override { + Table << MatchTable::Opcode("GIM_CheckNumOperands") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("Expected") + << MatchTable::IntValue(NumOperands) << MatchTable::LineBreak; + } }; /// Generates code to check that this instruction is a constant whose value @@ -1483,10 +1720,17 @@ public: : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID), Order(Order), Comparator(Comparator) {} - static bool classof(const InstructionPredicateMatcher *P) { + static bool classof(const PredicateMatcher *P) { return P->getKind() == IPM_AtomicOrderingMMO; } + bool isIdentical(const PredicateMatcher &B) const override { + if (!InstructionPredicateMatcher::isIdentical(B)) + return false; + const auto &R = *cast<AtomicOrderingMMOPredicateMatcher>(&B); + return Order == R.Order && Comparator == R.Comparator; + } + void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { StringRef Opcode = "GIM_CheckAtomicOrdering"; @@ -1503,14 +1747,113 @@ public: } }; +/// Generates code to check that the size of an MMO is exactly N bytes. +class MemorySizePredicateMatcher : public InstructionPredicateMatcher { +protected: + unsigned MMOIdx; + uint64_t Size; + +public: + MemorySizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, unsigned Size) + : InstructionPredicateMatcher(IPM_MemoryLLTSize, InsnVarID), + MMOIdx(MMOIdx), Size(Size) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_MemoryLLTSize; + } + bool isIdentical(const PredicateMatcher &B) const override { + return InstructionPredicateMatcher::isIdentical(B) && + MMOIdx == cast<MemorySizePredicateMatcher>(&B)->MMOIdx && + Size == cast<MemorySizePredicateMatcher>(&B)->Size; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override { + Table << MatchTable::Opcode("GIM_CheckMemorySizeEqualTo") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx) + << MatchTable::Comment("Size") << MatchTable::IntValue(Size) + << MatchTable::LineBreak; + } +}; + +/// Generates code to check that the size of an MMO is less-than, equal-to, or +/// greater than a given LLT. +class MemoryVsLLTSizePredicateMatcher : public InstructionPredicateMatcher { +public: + enum RelationKind { + GreaterThan, + EqualTo, + LessThan, + }; + +protected: + unsigned MMOIdx; + RelationKind Relation; + unsigned OpIdx; + +public: + MemoryVsLLTSizePredicateMatcher(unsigned InsnVarID, unsigned MMOIdx, + enum RelationKind Relation, + unsigned OpIdx) + : InstructionPredicateMatcher(IPM_MemoryVsLLTSize, InsnVarID), + MMOIdx(MMOIdx), Relation(Relation), OpIdx(OpIdx) {} + + static bool classof(const PredicateMatcher *P) { + return P->getKind() == IPM_MemoryVsLLTSize; + } + bool isIdentical(const PredicateMatcher &B) const override { + return InstructionPredicateMatcher::isIdentical(B) && + MMOIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->MMOIdx && + Relation == cast<MemoryVsLLTSizePredicateMatcher>(&B)->Relation && + OpIdx == cast<MemoryVsLLTSizePredicateMatcher>(&B)->OpIdx; + } + + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override { + Table << MatchTable::Opcode(Relation == EqualTo + ? "GIM_CheckMemorySizeEqualToLLT" + : Relation == GreaterThan + ? "GIM_CheckMemorySizeGreaterThanLLT" + : "GIM_CheckMemorySizeLessThanLLT") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("MMO") << MatchTable::IntValue(MMOIdx) + << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx) + << MatchTable::LineBreak; + } +}; + +/// Generates code to check an arbitrary C++ instruction predicate. +class GenericInstructionPredicateMatcher : public InstructionPredicateMatcher { +protected: + TreePredicateFn Predicate; + +public: + GenericInstructionPredicateMatcher(unsigned InsnVarID, + TreePredicateFn Predicate) + : InstructionPredicateMatcher(IPM_GenericPredicate, InsnVarID), + Predicate(Predicate) {} + + static bool classof(const InstructionPredicateMatcher *P) { + return P->getKind() == IPM_GenericPredicate; + } + void emitPredicateOpcodes(MatchTable &Table, + RuleMatcher &Rule) const override { + Table << MatchTable::Opcode("GIM_CheckCxxInsnPredicate") + << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) + << MatchTable::Comment("FnId") + << MatchTable::NamedValue(getEnumNameForPredicate(Predicate)) + << MatchTable::LineBreak; + } +}; + /// 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> { +class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> { protected: typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec; @@ -1519,6 +1862,7 @@ protected: /// The operands to match. All rendered operands must be present even if the /// condition is always true. OperandVec Operands; + bool NumOperandsCheck = true; std::string SymbolicName; unsigned InsnVarID; @@ -1531,9 +1875,17 @@ public: InsnVarID = Rule.implicitlyDefineInsnVar(*this); } + /// Construct a new instruction predicate and add it to the matcher. + template <class Kind, class... Args> + Optional<Kind *> addPredicate(Args &&... args) { + Predicates.emplace_back( + llvm::make_unique<Kind>(getInsnVarID(), std::forward<Args>(args)...)); + return static_cast<Kind *>(Predicates.back().get()); + } + RuleMatcher &getRuleMatcher() const { return Rule; } - unsigned getVarID() const { return InsnVarID; } + unsigned getInsnVarID() const { return InsnVarID; } /// Add an operand to the matcher. OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName, @@ -1549,7 +1901,7 @@ public: OperandMatcher &getOperand(unsigned OpIdx) { auto I = std::find_if(Operands.begin(), Operands.end(), [&OpIdx](const std::unique_ptr<OperandMatcher> &X) { - return X->getOperandIndex() == OpIdx; + return X->getOpIdx() == OpIdx; }); if (I != Operands.end()) return **I; @@ -1572,21 +1924,17 @@ public: void pop_front() { Operands.erase(Operands.begin()); } - /// Emit MatchTable opcodes to check the shape of the match and capture - /// instructions into the MIs table. - void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) { - Table << MatchTable::Opcode("GIM_CheckNumOperands") - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) - << MatchTable::Comment("Expected") - << MatchTable::IntValue(getNumOperands()) << MatchTable::LineBreak; - for (const auto &Operand : Operands) - Operand->emitCaptureOpcodes(Table, Rule); - } + void optimize(); /// Emit MatchTable opcodes that test whether the instruction named in /// InsnVarName matches all the predicates and all the operands. - void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const { + void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) { + if (NumOperandsCheck) + InstructionNumOperandsMatcher(InsnVarID, getNumOperands()) + .emitPredicateOpcodes(Table, Rule); + emitPredicateListOpcodes(Table, Rule); + for (const auto &Operand : Operands) Operand->emitPredicateOpcodes(Table, Rule); } @@ -1594,17 +1942,19 @@ public: /// Compare the priority of this object and B. /// /// Returns true if this object is more important than B. - bool isHigherPriorityThan(const InstructionMatcher &B) const { + bool isHigherPriorityThan(InstructionMatcher &B) { // 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))) + for (auto &&P : zip(predicates(), B.predicates())) { + auto L = static_cast<InstructionPredicateMatcher *>(std::get<0>(P).get()); + auto R = static_cast<InstructionPredicateMatcher *>(std::get<1>(P).get()); + if (L->isHigherPriorityThan(*R)) return true; - if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate))) + if (R->isHigherPriorityThan(*L)) return false; } @@ -1620,13 +1970,13 @@ public: /// 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(); - }) + + unsigned countRendererFns() { + return std::accumulate( + predicates().begin(), predicates().end(), 0, + [](unsigned A, + const std::unique_ptr<PredicateMatcher> &Predicate) { + return A + Predicate->countRendererFns(); + }) + std::accumulate( Operands.begin(), Operands.end(), 0, [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) { @@ -1634,24 +1984,36 @@ public: }); } - bool isConstantInstruction() const { - for (const auto &P : predicates()) - if (const InstructionOpcodeMatcher *Opcode = - dyn_cast<InstructionOpcodeMatcher>(P.get())) - return Opcode->isConstantInstruction(); - return false; + InstructionOpcodeMatcher &getOpcodeMatcher() { + for (auto &P : predicates()) + if (auto *OpMatcher = dyn_cast<InstructionOpcodeMatcher>(P.get())) + return *OpMatcher; + llvm_unreachable("Didn't find an opcode matcher"); } + + bool isConstantInstruction() { + return getOpcodeMatcher().isConstantInstruction(); + } + + StringRef getOpcode() { return getOpcodeMatcher().getOpcode(); } }; -template <> -template <class Kind, class... Args> -Optional<Kind *> -PredicateListMatcher<InstructionPredicateMatcher>::addPredicate( - Args &&... args) { - InstructionMatcher *InstMatcher = static_cast<InstructionMatcher *>(this); - Predicates.emplace_back(llvm::make_unique<Kind>(InstMatcher->getVarID(), - std::forward<Args>(args)...)); - return static_cast<Kind *>(Predicates.back().get()); +StringRef RuleMatcher::getOpcode() const { + return Matchers.front()->getOpcode(); +} + +unsigned RuleMatcher::getNumOperands() const { + return Matchers.front()->getNumOperands(); +} + +LLTCodeGen RuleMatcher::getFirstConditionAsRootType() { + InstructionMatcher &InsnMatcher = *Matchers.front(); + if (!InsnMatcher.predicates_empty()) + if (const auto *TM = + dyn_cast<LLTOperandMatcher>(&**InsnMatcher.predicates_begin())) + if (TM->getInsnVarID() == 0 && TM->getOpIdx() == 0) + return TM->getTy(); + return {}; } /// Generates code to check that the operand is a register defined by an @@ -1679,21 +2041,73 @@ public: InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; } - void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - unsigned InsnID = - Rule.defineInsnVar(Table, *InsnMatcher, InsnVarID, getOpIdx()); - (void)InsnID; - assert(InsnMatcher->getVarID() == InsnID && - "Mismatch between build and emit"); - InsnMatcher->emitCaptureOpcodes(Table, Rule); + void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const { + const unsigned NewInsnVarID = InsnMatcher->getInsnVarID(); + Table << MatchTable::Opcode("GIM_RecordInsn") + << MatchTable::Comment("DefineMI") + << MatchTable::IntValue(NewInsnVarID) << MatchTable::Comment("MI") + << MatchTable::IntValue(getInsnVarID()) + << MatchTable::Comment("OpIdx") << MatchTable::IntValue(getOpIdx()) + << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]") + << MatchTable::LineBreak; } void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { + emitCaptureOpcodes(Table, Rule); InsnMatcher->emitPredicateOpcodes(Table, Rule); } + + bool isHigherPriorityThan(const OperandPredicateMatcher &B) const override { + if (OperandPredicateMatcher::isHigherPriorityThan(B)) + return true; + if (B.OperandPredicateMatcher::isHigherPriorityThan(*this)) + return false; + + if (const InstructionOperandMatcher *BP = + dyn_cast<InstructionOperandMatcher>(&B)) + if (InsnMatcher->isHigherPriorityThan(*BP->InsnMatcher)) + return true; + return false; + } }; +void InstructionMatcher::optimize() { + SmallVector<std::unique_ptr<PredicateMatcher>, 8> Stash; + const auto &OpcMatcher = getOpcodeMatcher(); + + Stash.push_back(predicates_pop_front()); + if (Stash.back().get() == &OpcMatcher) { + if (NumOperandsCheck && OpcMatcher.getNumOperands() < getNumOperands()) + Stash.emplace_back( + new InstructionNumOperandsMatcher(InsnVarID, getNumOperands())); + NumOperandsCheck = false; + + for (auto &OM : Operands) + for (auto &OP : OM->predicates()) + if (isa<IntrinsicIDOperandMatcher>(OP)) { + Stash.push_back(std::move(OP)); + OM->eraseNullPredicates(); + break; + } + } + + if (InsnVarID > 0) { + assert(!Operands.empty() && "Nested instruction is expected to def a vreg"); + for (auto &OP : Operands[0]->predicates()) + OP.reset(); + Operands[0]->eraseNullPredicates(); + } + for (auto &OM : Operands) { + for (auto &OP : OM->predicates()) + if (isa<LLTOperandMatcher>(OP)) + Stash.push_back(std::move(OP)); + OM->eraseNullPredicates(); + } + while (!Stash.empty()) + prependPredicate(Stash.pop_back_val()); +} + //===- Actions ------------------------------------------------------------===// class OperandRenderer { public: @@ -1706,7 +2120,8 @@ public: OR_Imm, OR_Register, OR_TempRegister, - OR_ComplexPattern + OR_ComplexPattern, + OR_Custom }; protected: @@ -1749,7 +2164,7 @@ public: Table << MatchTable::Opcode("GIR_Copy") << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID") << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") - << MatchTable::IntValue(Operand.getOperandIndex()) + << MatchTable::IntValue(Operand.getOpIdx()) << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; } }; @@ -1785,7 +2200,7 @@ public: << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID") << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") - << MatchTable::IntValue(Operand.getOperandIndex()) + << MatchTable::IntValue(Operand.getOpIdx()) << MatchTable::NamedValue( (ZeroRegisterDef->getValue("Namespace") ? ZeroRegisterDef->getValueAsString("Namespace") @@ -1816,7 +2231,7 @@ public: const StringRef getSymbolicName() const { return SymbolicName; } void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - const InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); + InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm" : "GIR_CopyConstantAsUImm") @@ -1847,7 +2262,7 @@ public: const StringRef getSymbolicName() const { return SymbolicName; } void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { - const InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); + InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm") << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) @@ -1887,7 +2302,7 @@ public: << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID) << MatchTable::Comment("OldInsnID") << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx") - << MatchTable::IntValue(Operand.getOperandIndex()) + << MatchTable::IntValue(Operand.getOpIdx()) << MatchTable::Comment("SubRegIdx") << MatchTable::IntValue(SubReg->EnumValue) << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; @@ -2018,6 +2433,37 @@ public: } }; +class CustomRenderer : public OperandRenderer { +protected: + unsigned InsnID; + const Record &Renderer; + /// The name of the operand. + const std::string SymbolicName; + +public: + CustomRenderer(unsigned InsnID, const Record &Renderer, + StringRef SymbolicName) + : OperandRenderer(OR_Custom), InsnID(InsnID), Renderer(Renderer), + SymbolicName(SymbolicName) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_Custom; + } + + void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override { + InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName); + unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher); + Table << MatchTable::Opcode("GIR_CustomRenderer") + << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) + << MatchTable::Comment("OldInsnID") + << MatchTable::IntValue(OldInsnVarID) + << MatchTable::Comment("Renderer") + << MatchTable::NamedValue( + "GICR_" + Renderer.getValueAsString("RendererFn").str()) + << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak; + } +}; + /// An action taken when all Matcher predicates succeeded for a parent rule. /// /// Typical actions include: @@ -2051,7 +2497,7 @@ class BuildMIAction : public MatchAction { private: unsigned InsnID; const CodeGenInstruction *I; - const InstructionMatcher *Matched; + InstructionMatcher *Matched; std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers; /// True if the instruction can be built solely by mutating the opcode. @@ -2066,7 +2512,7 @@ private: if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) { const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName()); if (Insn != &OM.getInstructionMatcher() || - OM.getOperandIndex() != Renderer.index()) + OM.getOpIdx() != Renderer.index()) return false; } else return false; @@ -2079,10 +2525,11 @@ public: BuildMIAction(unsigned InsnID, const CodeGenInstruction *I) : InsnID(InsnID), I(I), Matched(nullptr) {} + unsigned getInsnID() const { return InsnID; } const CodeGenInstruction *getCGI() const { return I; } void chooseInsnToMutate(RuleMatcher &Rule) { - for (const auto *MutateCandidate : Rule.mutatable_insns()) { + for (auto *MutateCandidate : Rule.mutatable_insns()) { if (canMutate(Rule, MutateCandidate)) { // Take the first one we're offered that we're able to mutate. Rule.reserveInsnMatcherForMutation(MutateCandidate); @@ -2160,7 +2607,7 @@ public: std::vector<unsigned> MergeInsnIDs; for (const auto &IDMatcherPair : Rule.defined_insn_vars()) MergeInsnIDs.push_back(IDMatcherPair.second); - std::sort(MergeInsnIDs.begin(), MergeInsnIDs.end()); + llvm::sort(MergeInsnIDs.begin(), MergeInsnIDs.end()); for (const auto &MergeInsnID : MergeInsnIDs) Table << MatchTable::IntValue(MergeInsnID); Table << MatchTable::NamedValue("GIU_MergeMemOperands_EndOfList") @@ -2274,27 +2721,13 @@ action_iterator RuleMatcher::insertAction(action_iterator InsertPt, llvm::make_unique<Kind>(std::forward<Args>(args)...)); } -unsigned -RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) { +unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) { unsigned NewInsnVarID = NextInsnVarID++; InsnVariableIDs[&Matcher] = NewInsnVarID; return NewInsnVarID; } -unsigned RuleMatcher::defineInsnVar(MatchTable &Table, - const InstructionMatcher &Matcher, - unsigned InsnID, unsigned OpIdx) { - unsigned NewInsnVarID = implicitlyDefineInsnVar(Matcher); - Table << MatchTable::Opcode("GIM_RecordInsn") - << MatchTable::Comment("DefineMI") << MatchTable::IntValue(NewInsnVarID) - << MatchTable::Comment("MI") << MatchTable::IntValue(InsnID) - << MatchTable::Comment("OpIdx") << MatchTable::IntValue(OpIdx) - << MatchTable::Comment("MIs[" + llvm::to_string(NewInsnVarID) + "]") - << MatchTable::LineBreak; - return NewInsnVarID; -} - -unsigned RuleMatcher::getInsnVarID(const InstructionMatcher &InsnMatcher) const { +unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const { const auto &I = InsnVariableIDs.find(&InsnMatcher); if (I != InsnVariableIDs.end()) return I->second; @@ -2312,7 +2745,7 @@ void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) { OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName()); } -const InstructionMatcher & +InstructionMatcher & RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const { for (const auto &I : InsnVariableIDs) if (I.first->getSymbolicName() == SymbolicName) @@ -2331,25 +2764,10 @@ RuleMatcher::getOperandMatcher(StringRef Name) const { return *I->second; } -/// Emit MatchTable opcodes to check the shape of the match and capture -/// instructions into local variables. -void RuleMatcher::emitCaptureOpcodes(MatchTable &Table) { - assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet"); - unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front()); - (void)InsnVarID; - assert(Matchers.front()->getVarID() == InsnVarID && - "IDs differ between build and emit"); - Matchers.front()->emitCaptureOpcodes(Table, *this); -} - void RuleMatcher::emit(MatchTable &Table) { if (Matchers.empty()) llvm_unreachable("Unexpected empty matcher!"); - // Reset the ID generation so that the emitted IDs match the ones - // we set while building the InstructionMatcher and such. - clearImplicitMap(); - // The representation supports rules that require multiple roots such as: // %ptr(p0) = ... // %elt0(s32) = G_LOAD %ptr @@ -2363,7 +2781,9 @@ void RuleMatcher::emit(MatchTable &Table) { unsigned LabelID = Table.allocateLabelID(); Table << MatchTable::Opcode("GIM_Try", +1) - << MatchTable::Comment("On fail goto") << MatchTable::JumpTarget(LabelID) + << MatchTable::Comment("On fail goto") + << MatchTable::JumpTarget(LabelID) + << MatchTable::Comment(("Rule ID " + Twine(RuleID) + " //").str()) << MatchTable::LineBreak; if (!RequiredFeatures.empty()) { @@ -2372,8 +2792,6 @@ void RuleMatcher::emit(MatchTable &Table) { << MatchTable::LineBreak; } - emitCaptureOpcodes(Table); - Matchers.front()->emitPredicateOpcodes(Table, *this); // We must also check if it's safe to fold the matched instructions. @@ -2388,7 +2806,7 @@ void RuleMatcher::emit(MatchTable &Table) { InsnIDs.push_back(Pair.second); } - std::sort(InsnIDs.begin(), InsnIDs.end()); + llvm::sort(InsnIDs.begin(), InsnIDs.end()); for (const auto &InsnID : InsnIDs) { // Reject the difficult cases until we have a more accurate check. @@ -2433,15 +2851,22 @@ void RuleMatcher::emit(MatchTable &Table) { } } + for (const auto &PM : EpilogueMatchers) + PM->emitPredicateOpcodes(Table, *this); + for (const auto &MA : Actions) MA->emitActionOpcodes(Table, *this); - if (GenerateCoverage) + if (Table.isWithCoverage()) Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID) << MatchTable::LineBreak; + else + Table << MatchTable::Comment(("GIR_Coverage, " + Twine(RuleID) + ",").str()) + << MatchTable::LineBreak; Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak << MatchTable::Label(LabelID); + ++NumPatternEmitted; } bool RuleMatcher::isHigherPriorityThan(const RuleMatcher &B) const { @@ -2505,7 +2930,7 @@ void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const { const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName); unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher()); - assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getVarID()); + assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getInsnVarID()); Table << MatchTable::Opcode("GIM_CheckIsSameOperand") << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID) @@ -2513,7 +2938,7 @@ void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table, << MatchTable::Comment("OtherMI") << MatchTable::IntValue(OtherInsnVarID) << MatchTable::Comment("OtherOpIdx") - << MatchTable::IntValue(OtherOM.getOperandIndex()) + << MatchTable::IntValue(OtherOM.getOpIdx()) << MatchTable::LineBreak; } @@ -2541,25 +2966,43 @@ private: /// GIComplexPatternEquiv. DenseMap<const Record *, const Record *> ComplexPatternEquivs; + /// Keep track of the equivalence between SDNodeXForm's and + /// GICustomOperandRenderer. Map entries are specified by subclassing + /// GISDNodeXFormEquiv. + DenseMap<const Record *, const Record *> SDNodeXFormEquivs; + + /// Keep track of Scores of PatternsToMatch similar to how the DAG does. + /// This adds compatibility for RuleMatchers to use this for ordering rules. + DenseMap<uint64_t, int> RuleMatcherScores; + // Map of predicates to their subtarget features. SubtargetFeatureInfoMap SubtargetFeatures; // Rule coverage information. Optional<CodeGenCoverage> RuleCoverage; + void gatherOpcodeValues(); + void gatherTypeIDValues(); void gatherNodeEquivs(); + // Instruction predicate code that will be emitted in generated functions. + SmallVector<std::string, 2> InstructionPredicateCodes; + unsigned getOrCreateInstructionPredicateFnId(StringRef Code); + Record *findNodeEquiv(Record *N) const; + const CodeGenInstruction *getEquivNode(Record &Equiv, + const TreePatternNode *N) const; Error importRulePredicates(RuleMatcher &M, ArrayRef<Predicate> Predicates); - Expected<InstructionMatcher &> createAndImportSelDAGMatcher( - RuleMatcher &Rule, InstructionMatcher &InsnMatcher, - const TreePatternNode *Src, unsigned &TempOpIdx) const; + Expected<InstructionMatcher &> + createAndImportSelDAGMatcher(RuleMatcher &Rule, + InstructionMatcher &InsnMatcher, + const TreePatternNode *Src, unsigned &TempOpIdx); Error importComplexPatternOperandMatcher(OperandMatcher &OM, Record *R, unsigned &TempOpIdx) const; Error importChildMatcher(RuleMatcher &Rule, InstructionMatcher &InsnMatcher, const TreePatternNode *SrcChild, bool OperandIsAPointer, unsigned OpIdx, - unsigned &TempOpIdx) const; + unsigned &TempOpIdx); Expected<BuildMIAction &> createAndImportInstructionRenderer(RuleMatcher &M, @@ -2585,9 +3028,14 @@ private: importImplicitDefRenderers(BuildMIAction &DstMIBuilder, const std::vector<Record *> &ImplicitDefs) const; - void emitImmPredicates(raw_ostream &OS, StringRef TypeIdentifier, - StringRef Type, - std::function<bool(const Record *R)> Filter); + void emitCxxPredicateFns(raw_ostream &OS, StringRef CodeFieldName, + StringRef TypeIdentifier, StringRef ArgType, + StringRef ArgName, StringRef AdditionalDeclarations, + std::function<bool(const Record *R)> Filter); + void emitImmPredicateFns(raw_ostream &OS, StringRef TypeIdentifier, + StringRef ArgType, + std::function<bool(const Record *R)> Filter); + void emitMIPredicateFns(raw_ostream &OS); /// Analyze pattern \p P, returning a matcher for it if possible. /// Otherwise, return an Error explaining why we don't support it. @@ -2595,19 +3043,15 @@ private: void declareSubtargetFeature(Record *Predicate); - TreePatternNode *fixupPatternNode(TreePatternNode *N); - void fixupPatternTrees(TreePattern *P); + MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize, + bool WithCoverage); +public: /// Takes a sequence of \p Rules and group them based on the predicates - /// they share. \p StorageGroupMatcher is used as a memory container - /// for the the group that are created as part of this process. - /// The optimization process does not change the relative order of - /// the rules. In particular, we don't try to share predicates if - /// that means reordering the rules (e.g., we won't group R1 and R3 - /// in the following example as it would imply reordering R2 and R3 - /// => R1 p1, R2 p2, R3 p1). + /// they share. \p MatcherStorage is used as a memory container + /// for the group that are created as part of this process. /// - /// What this optimization does looks like: + /// What this optimization does looks like if GroupT = GroupMatcher: /// Output without optimization: /// \verbatim /// # R1 @@ -2628,11 +3072,34 @@ private: /// # R2 /// # predicate C /// \endverbatim - std::vector<Matcher *> optimizeRules( - const std::vector<Matcher *> &Rules, - std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher); + template <class GroupT> + static std::vector<Matcher *> optimizeRules( + ArrayRef<Matcher *> Rules, + std::vector<std::unique_ptr<Matcher>> &MatcherStorage); }; +void GlobalISelEmitter::gatherOpcodeValues() { + InstructionOpcodeMatcher::initOpcodeValuesMap(Target); +} + +void GlobalISelEmitter::gatherTypeIDValues() { + LLTOperandMatcher::initTypeIDValuesMap(); +} +unsigned GlobalISelEmitter::getOrCreateInstructionPredicateFnId(StringRef Code) { + // There's not very many predicates that need to be here at the moment so we + // just maintain a simple set-like vector. If it grows then we'll need to do + // something more efficient. + const auto &I = std::find(InstructionPredicateCodes.begin(), + InstructionPredicateCodes.end(), + Code); + if (I == InstructionPredicateCodes.end()) { + unsigned ID = InstructionPredicateCodes.size(); + InstructionPredicateCodes.push_back(Code); + return ID; + } + return std::distance(InstructionPredicateCodes.begin(), I); +} + void GlobalISelEmitter::gatherNodeEquivs() { assert(NodeEquivs.empty()); for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv")) @@ -2645,15 +3112,36 @@ void GlobalISelEmitter::gatherNodeEquivs() { continue; ComplexPatternEquivs[SelDAGEquiv] = Equiv; } + + assert(SDNodeXFormEquivs.empty()); + for (Record *Equiv : RK.getAllDerivedDefinitions("GISDNodeXFormEquiv")) { + Record *SelDAGEquiv = Equiv->getValueAsDef("SelDAGEquivalent"); + if (!SelDAGEquiv) + continue; + SDNodeXFormEquivs[SelDAGEquiv] = Equiv; + } } Record *GlobalISelEmitter::findNodeEquiv(Record *N) const { return NodeEquivs.lookup(N); } +const CodeGenInstruction * +GlobalISelEmitter::getEquivNode(Record &Equiv, const TreePatternNode *N) const { + for (const auto &Predicate : N->getPredicateFns()) { + if (!Equiv.isValueUnset("IfSignExtend") && Predicate.isLoad() && + Predicate.isSignExtLoad()) + return &Target.getInstruction(Equiv.getValueAsDef("IfSignExtend")); + if (!Equiv.isValueUnset("IfZeroExtend") && Predicate.isLoad() && + Predicate.isZeroExtLoad()) + return &Target.getInstruction(Equiv.getValueAsDef("IfZeroExtend")); + } + return &Target.getInstruction(Equiv.getValueAsDef("I")); +} + GlobalISelEmitter::GlobalISelEmitter(RecordKeeper &RK) - : RK(RK), CGP(RK, [&](TreePattern *P) { fixupPatternTrees(P); }), - Target(CGP.getTargetInfo()), CGRegs(RK, Target.getHwModes()) {} + : RK(RK), CGP(RK), Target(CGP.getTargetInfo()), + CGRegs(RK, Target.getHwModes()) {} //===- Emitter ------------------------------------------------------------===// @@ -2672,7 +3160,7 @@ GlobalISelEmitter::importRulePredicates(RuleMatcher &M, Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher( RuleMatcher &Rule, InstructionMatcher &InsnMatcher, - const TreePatternNode *Src, unsigned &TempOpIdx) const { + const TreePatternNode *Src, unsigned &TempOpIdx) { Record *SrcGIEquivOrNull = nullptr; const CodeGenInstruction *SrcGIOrNull = nullptr; @@ -2693,7 +3181,7 @@ Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher( if (!SrcGIEquivOrNull) return failedImport("Pattern operator lacks an equivalent Instruction" + explainOperator(Src->getOperator())); - SrcGIOrNull = &Target.getInstruction(SrcGIEquivOrNull->getValueAsDef("I")); + SrcGIOrNull = getEquivNode(*SrcGIEquivOrNull, Src); // The operators look good: match the opcode InsnMatcher.addPredicate<InstructionOpcodeMatcher>(SrcGIOrNull); @@ -2718,8 +3206,26 @@ Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher( continue; } - // No check required. G_LOAD by itself is a non-extending load. - if (Predicate.isNonExtLoad()) + // G_LOAD is used for both non-extending and any-extending loads. + if (Predicate.isLoad() && Predicate.isNonExtLoad()) { + InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>( + 0, MemoryVsLLTSizePredicateMatcher::EqualTo, 0); + continue; + } + if (Predicate.isLoad() && Predicate.isAnyExtLoad()) { + InsnMatcher.addPredicate<MemoryVsLLTSizePredicateMatcher>( + 0, MemoryVsLLTSizePredicateMatcher::LessThan, 0); + continue; + } + + // No check required. We already did it by swapping the opcode. + if (!SrcGIEquivOrNull->isValueUnset("IfSignExtend") && + Predicate.isSignExtLoad()) + continue; + + // No check required. We already did it by swapping the opcode. + if (!SrcGIEquivOrNull->isValueUnset("IfZeroExtend") && + Predicate.isZeroExtLoad()) continue; // No check required. G_STORE by itself is a non-extending store. @@ -2734,8 +3240,13 @@ Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher( if (!MemTyOrNone) return failedImport("MemVT could not be converted to LLT"); - OperandMatcher &OM = InsnMatcher.getOperand(0); - OM.addPredicate<LLTOperandMatcher>(MemTyOrNone.getValue()); + // MMO's work in bytes so we must take care of unusual types like i1 + // don't round down. + unsigned MemSizeInBits = + llvm::alignTo(MemTyOrNone->get().getSizeInBits(), 8); + + InsnMatcher.addPredicate<MemorySizePredicateMatcher>( + 0, MemSizeInBits / 8); continue; } } @@ -2794,6 +3305,11 @@ Expected<InstructionMatcher &> GlobalISelEmitter::createAndImportSelDAGMatcher( } } + if (Predicate.hasGISelPredicateCode()) { + InsnMatcher.addPredicate<GenericInstructionPredicateMatcher>(Predicate); + continue; + } + return failedImport("Src pattern child has predicate (" + explainPredicates(Src) + ")"); } @@ -2872,7 +3388,7 @@ Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule, const TreePatternNode *SrcChild, bool OperandIsAPointer, unsigned OpIdx, - unsigned &TempOpIdx) const { + unsigned &TempOpIdx) { OperandMatcher &OM = InsnMatcher.addOperand(OpIdx, SrcChild->getName(), TempOpIdx); if (OM.isSameAsAnotherOperand()) @@ -2986,10 +3502,6 @@ Error GlobalISelEmitter::importChildMatcher(RuleMatcher &Rule, Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer( action_iterator InsertPt, RuleMatcher &Rule, BuildMIAction &DstMIBuilder, TreePatternNode *DstChild) { - if (DstChild->getTransformFn() != nullptr) { - return failedImport("Dst pattern child has transform fn " + - DstChild->getTransformFn()->getName()); - } const auto &SubOperand = Rule.getComplexSubOperand(DstChild->getName()); if (SubOperand.hasValue()) { @@ -3000,6 +3512,18 @@ Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer( } if (!DstChild->isLeaf()) { + + if (DstChild->getOperator()->isSubClassOf("SDNodeXForm")) { + auto Child = DstChild->getChild(0); + auto I = SDNodeXFormEquivs.find(DstChild->getOperator()); + if (I != SDNodeXFormEquivs.end()) { + DstMIBuilder.addRenderer<CustomRenderer>(*I->second, Child->getName()); + return InsertPt; + } + return failedImport("SDNodeXForm " + Child->getName() + + " has no custom renderer"); + } + // We accept 'bb' here. It's an operator because BasicBlockSDNode isn't // inline, but in MI it's just another operand. if (DstChild->getOperator()->isSubClassOf("SDNode")) { @@ -3104,10 +3628,6 @@ Expected<action_iterator> GlobalISelEmitter::importExplicitUseRenderer( return InsertPt; } - 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"); } @@ -3135,7 +3655,7 @@ Expected<BuildMIAction &> GlobalISelEmitter::createAndImportInstructionRenderer( Expected<action_iterator> GlobalISelEmitter::createAndImportSubInstructionRenderer( - action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst, + const action_iterator InsertPt, RuleMatcher &M, const TreePatternNode *Dst, unsigned TempRegID) { auto InsertPtOrError = createInstructionRenderer(InsertPt, M, Dst); @@ -3143,7 +3663,6 @@ GlobalISelEmitter::createAndImportSubInstructionRenderer( if (auto Error = InsertPtOrError.takeError()) return std::move(Error); - InsertPt = InsertPtOrError.get(); BuildMIAction &DstMIBuilder = *static_cast<BuildMIAction *>(InsertPtOrError.get()->get()); @@ -3151,10 +3670,13 @@ GlobalISelEmitter::createAndImportSubInstructionRenderer( // Assign the result to TempReg. DstMIBuilder.addRenderer<TempRegRenderer>(TempRegID, true); - InsertPtOrError = importExplicitUseRenderers(InsertPt, M, DstMIBuilder, Dst); + InsertPtOrError = + importExplicitUseRenderers(InsertPtOrError.get(), M, DstMIBuilder, Dst); if (auto Error = InsertPtOrError.takeError()) return std::move(Error); + M.insertAction<ConstrainOperandsToDefinitionAction>(InsertPt, + DstMIBuilder.getInsnID()); return InsertPtOrError.get(); } @@ -3311,7 +3833,9 @@ Error GlobalISelEmitter::importImplicitDefRenderers( Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) { // Keep track of the matchers and actions to emit. + int Score = P.getPatternComplexity(CGP); RuleMatcher M(P.getSrcRecord()->getLoc()); + RuleMatcherScores[M.getRuleID()] = Score; M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) + " => " + llvm::to_string(*P.getDstPattern())); @@ -3526,14 +4050,15 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) { // Emit imm predicate table and an enum to reference them with. // The 'Predicate_' part of the name is redundant but eliminating it is more // trouble than it's worth. -void GlobalISelEmitter::emitImmPredicates( - raw_ostream &OS, StringRef TypeIdentifier, StringRef Type, +void GlobalISelEmitter::emitCxxPredicateFns( + raw_ostream &OS, StringRef CodeFieldName, StringRef TypeIdentifier, + StringRef ArgType, StringRef ArgName, StringRef AdditionalDeclarations, std::function<bool(const Record *R)> Filter) { std::vector<const Record *> MatchedRecords; const auto &Defs = RK.getAllDerivedDefinitions("PatFrag"); std::copy_if(Defs.begin(), Defs.end(), std::back_inserter(MatchedRecords), [&](Record *Record) { - return !Record->getValueAsString("ImmediateCode").empty() && + return !Record->getValueAsString(CodeFieldName).empty() && Filter(Record); }); @@ -3550,16 +4075,20 @@ void GlobalISelEmitter::emitImmPredicates( OS << "};\n"; } - OS << "bool " << Target.getName() << "InstructionSelector::testImmPredicate_" - << TypeIdentifier << "(unsigned PredicateID, " << Type - << " Imm) const {\n"; + OS << "bool " << Target.getName() << "InstructionSelector::test" << ArgName + << "Predicate_" << TypeIdentifier << "(unsigned PredicateID, " << ArgType << " " + << ArgName << ") const {\n" + << AdditionalDeclarations; + if (!AdditionalDeclarations.empty()) + OS << "\n"; if (!MatchedRecords.empty()) OS << " switch (PredicateID) {\n"; for (const auto *Record : MatchedRecords) { OS << " case GIPFP_" << TypeIdentifier << "_Predicate_" << Record->getName() << ": {\n" - << " " << Record->getValueAsString("ImmediateCode") << "\n" - << " llvm_unreachable(\"ImmediateCode should have returned\");\n" + << " " << Record->getValueAsString(CodeFieldName) << "\n" + << " llvm_unreachable(\"" << CodeFieldName + << " should have returned\");\n" << " return false;\n" << " }\n"; } @@ -3570,38 +4099,144 @@ void GlobalISelEmitter::emitImmPredicates( << "}\n"; } +void GlobalISelEmitter::emitImmPredicateFns( + raw_ostream &OS, StringRef TypeIdentifier, StringRef ArgType, + std::function<bool(const Record *R)> Filter) { + return emitCxxPredicateFns(OS, "ImmediateCode", TypeIdentifier, ArgType, + "Imm", "", Filter); +} + +void GlobalISelEmitter::emitMIPredicateFns(raw_ostream &OS) { + return emitCxxPredicateFns( + OS, "GISelPredicateCode", "MI", "const MachineInstr &", "MI", + " const MachineFunction &MF = *MI.getParent()->getParent();\n" + " const MachineRegisterInfo &MRI = MF.getRegInfo();\n" + " (void)MRI;", + [](const Record *R) { return true; }); +} + +template <class GroupT> std::vector<Matcher *> GlobalISelEmitter::optimizeRules( - const std::vector<Matcher *> &Rules, - std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher) { + ArrayRef<Matcher *> Rules, + std::vector<std::unique_ptr<Matcher>> &MatcherStorage) { + std::vector<Matcher *> OptRules; - // Start with a stupid grouping for now. - std::unique_ptr<GroupMatcher> CurrentGroup = make_unique<GroupMatcher>(); - assert(CurrentGroup->conditions_empty()); - unsigned NbGroup = 0; - for (Matcher *Rule : Rules) { - std::unique_ptr<PredicateMatcher> Predicate = Rule->forgetFirstCondition(); - if (!CurrentGroup->conditions_empty() && - !CurrentGroup->lastConditionMatches(*Predicate)) { - // Start a new group. - ++NbGroup; + std::unique_ptr<GroupT> CurrentGroup = make_unique<GroupT>(); + assert(CurrentGroup->empty() && "Newly created group isn't empty!"); + unsigned NumGroups = 0; + + auto ProcessCurrentGroup = [&]() { + if (CurrentGroup->empty()) + // An empty group is good to be reused: + return; + + // If the group isn't large enough to provide any benefit, move all the + // added rules out of it and make sure to re-create the group to properly + // re-initialize it: + if (CurrentGroup->size() < 2) + for (Matcher *M : CurrentGroup->matchers()) + OptRules.push_back(M); + else { + CurrentGroup->finalize(); OptRules.push_back(CurrentGroup.get()); - StorageGroupMatcher.emplace_back(std::move(CurrentGroup)); - CurrentGroup = make_unique<GroupMatcher>(); - assert(CurrentGroup->conditions_empty()); + MatcherStorage.emplace_back(std::move(CurrentGroup)); + ++NumGroups; } - if (CurrentGroup->conditions_empty()) - CurrentGroup->addCondition(std::move(Predicate)); - CurrentGroup->addRule(*Rule); - } - if (!CurrentGroup->conditions_empty()) { - ++NbGroup; - OptRules.push_back(CurrentGroup.get()); - StorageGroupMatcher.emplace_back(std::move(CurrentGroup)); + CurrentGroup = make_unique<GroupT>(); + }; + for (Matcher *Rule : Rules) { + // Greedily add as many matchers as possible to the current group: + if (CurrentGroup->addMatcher(*Rule)) + continue; + + ProcessCurrentGroup(); + assert(CurrentGroup->empty() && "A group wasn't properly re-initialized"); + + // Try to add the pending matcher to a newly created empty group: + if (!CurrentGroup->addMatcher(*Rule)) + // If we couldn't add the matcher to an empty group, that group type + // doesn't support that kind of matchers at all, so just skip it: + OptRules.push_back(Rule); } - DEBUG(dbgs() << "NbGroup: " << NbGroup << "\n"); + ProcessCurrentGroup(); + + LLVM_DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n"); + assert(CurrentGroup->empty() && "The last group wasn't properly processed"); return OptRules; } +MatchTable +GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules, + bool Optimize, bool WithCoverage) { + std::vector<Matcher *> InputRules; + for (Matcher &Rule : Rules) + InputRules.push_back(&Rule); + + if (!Optimize) + return MatchTable::buildTable(InputRules, WithCoverage); + + unsigned CurrentOrdering = 0; + StringMap<unsigned> OpcodeOrder; + for (RuleMatcher &Rule : Rules) { + const StringRef Opcode = Rule.getOpcode(); + assert(!Opcode.empty() && "Didn't expect an undefined opcode"); + if (OpcodeOrder.count(Opcode) == 0) + OpcodeOrder[Opcode] = CurrentOrdering++; + } + + std::stable_sort(InputRules.begin(), InputRules.end(), + [&OpcodeOrder](const Matcher *A, const Matcher *B) { + auto *L = static_cast<const RuleMatcher *>(A); + auto *R = static_cast<const RuleMatcher *>(B); + return std::make_tuple(OpcodeOrder[L->getOpcode()], + L->getNumOperands()) < + std::make_tuple(OpcodeOrder[R->getOpcode()], + R->getNumOperands()); + }); + + for (Matcher *Rule : InputRules) + Rule->optimize(); + + std::vector<std::unique_ptr<Matcher>> MatcherStorage; + std::vector<Matcher *> OptRules = + optimizeRules<GroupMatcher>(InputRules, MatcherStorage); + + for (Matcher *Rule : OptRules) + Rule->optimize(); + + OptRules = optimizeRules<SwitchMatcher>(OptRules, MatcherStorage); + + return MatchTable::buildTable(OptRules, WithCoverage); +} + +void GroupMatcher::optimize() { + // Make sure we only sort by a specific predicate within a range of rules that + // all have that predicate checked against a specific value (not a wildcard): + auto F = Matchers.begin(); + auto T = F; + auto E = Matchers.end(); + while (T != E) { + while (T != E) { + auto *R = static_cast<RuleMatcher *>(*T); + if (!R->getFirstConditionAsRootType().get().isValid()) + break; + ++T; + } + std::stable_sort(F, T, [](Matcher *A, Matcher *B) { + auto *L = static_cast<RuleMatcher *>(A); + auto *R = static_cast<RuleMatcher *>(B); + return L->getFirstConditionAsRootType() < + R->getFirstConditionAsRootType(); + }); + if (T != E) + F = ++T; + } + GlobalISelEmitter::optimizeRules<GroupMatcher>(Matchers, MatcherStorage) + .swap(Matchers); + GlobalISelEmitter::optimizeRules<SwitchMatcher>(Matchers, MatcherStorage) + .swap(Matchers); +} + void GlobalISelEmitter::run(raw_ostream &OS) { if (!UseCoverageFile.empty()) { RuleCoverage = CodeGenCoverage(); @@ -3617,6 +4252,11 @@ void GlobalISelEmitter::run(raw_ostream &OS) { } } + // Track the run-time opcode values + gatherOpcodeValues(); + // Track the run-time LLT ID values + gatherTypeIDValues(); + // Track the GINodeEquiv definitions. gatherNodeEquivs(); @@ -3652,14 +4292,19 @@ void GlobalISelEmitter::run(raw_ostream &OS) { Rules.push_back(std::move(MatcherOrErr.get())); } + // Comparison function to order records by name. + auto orderByName = [](const Record *A, const Record *B) { + return A->getName() < B->getName(); + }; + 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; - }); + llvm::sort(ComplexPredicates.begin(), ComplexPredicates.end(), orderByName); + + std::vector<Record *> CustomRendererFns = + RK.getAllDerivedDefinitions("GICustomOperandRenderer"); + llvm::sort(CustomRendererFns.begin(), CustomRendererFns.end(), orderByName); + unsigned MaxTemporaries = 0; for (const auto &Rule : Rules) MaxTemporaries = std::max(MaxTemporaries, Rule.countRendererFns()); @@ -3677,21 +4322,33 @@ void GlobalISelEmitter::run(raw_ostream &OS) { "ComplexRendererFns(" << Target.getName() << "InstructionSelector::*ComplexMatcherMemFn)(MachineOperand &) const;\n" - << " const MatcherInfoTy<PredicateBitset, ComplexMatcherMemFn> " - "MatcherInfo;\n" - << " static " << Target.getName() + + << " typedef void(" << Target.getName() + << "InstructionSelector::*CustomRendererFn)(MachineInstrBuilder &, const " + "MachineInstr&) " + "const;\n" + << " const ISelInfoTy<PredicateBitset, ComplexMatcherMemFn, " + "CustomRendererFn> " + "ISelInfo;\n"; + OS << " static " << Target.getName() << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n" - << "bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const " + << " static " << Target.getName() + << "InstructionSelector::CustomRendererFn CustomRenderers[];\n" + << " bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const " "override;\n" - << "bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) " + << " bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) " "const override;\n" - << "bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat " + << " bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat " "&Imm) const override;\n" + << " const int64_t *getMatchTable() const override;\n" + << " bool testMIPredicate_MI(unsigned PredicateID, const MachineInstr &MI) " + "const override;\n" << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n"; OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n" << ", State(" << MaxTemporaries << "),\n" - << "MatcherInfo({TypeObjects, FeatureBitsets, ComplexPredicateFns})\n" + << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets" + << ", ComplexPredicateFns, CustomRenderers)\n" << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n"; OS << "#ifdef GET_GLOBALISEL_IMPL\n"; @@ -3723,9 +4380,9 @@ void GlobalISelEmitter::run(raw_ostream &OS) { // 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; - for (const auto &Ty : LLTOperandMatcher::KnownTypes) + for (const auto &Ty : KnownTypes) TypeObjects.push_back(Ty); - std::sort(TypeObjects.begin(), TypeObjects.end()); + llvm::sort(TypeObjects.begin(), TypeObjects.end()); OS << "// LLT Objects.\n" << "enum {\n"; for (const auto &TypeObject : TypeObjects) { @@ -3733,7 +4390,8 @@ void GlobalISelEmitter::run(raw_ostream &OS) { TypeObject.emitCxxEnumValue(OS); OS << ",\n"; } - OS << "};\n" + OS << "};\n"; + OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n" << "const static LLT TypeObjects[] = {\n"; for (const auto &TypeObject : TypeObjects) { OS << " "; @@ -3747,7 +4405,7 @@ void GlobalISelEmitter::run(raw_ostream &OS) { std::vector<std::vector<Record *>> FeatureBitsets; for (auto &Rule : Rules) FeatureBitsets.push_back(Rule.getRequiredFeatures()); - std::sort( + llvm::sort( FeatureBitsets.begin(), FeatureBitsets.end(), [&](const std::vector<Record *> &A, const std::vector<Record *> &B) { if (A.size() < B.size()) @@ -3798,18 +4456,19 @@ void GlobalISelEmitter::run(raw_ostream &OS) { OS << "};\n" << "// See constructor for table contents\n\n"; - emitImmPredicates(OS, "I64", "int64_t", [](const Record *R) { + emitImmPredicateFns(OS, "I64", "int64_t", [](const Record *R) { bool Unset; return !R->getValueAsBitOrUnset("IsAPFloat", Unset) && !R->getValueAsBit("IsAPInt"); }); - emitImmPredicates(OS, "APFloat", "const APFloat &", [](const Record *R) { + emitImmPredicateFns(OS, "APFloat", "const APFloat &", [](const Record *R) { bool Unset; return R->getValueAsBitOrUnset("IsAPFloat", Unset); }); - emitImmPredicates(OS, "APInt", "const APInt &", [](const Record *R) { + emitImmPredicateFns(OS, "APInt", "const APInt &", [](const Record *R) { return R->getValueAsBit("IsAPInt"); }); + emitMIPredicateFns(OS); OS << "\n"; OS << Target.getName() << "InstructionSelector::ComplexMatcherMemFn\n" @@ -3821,22 +4480,30 @@ void GlobalISelEmitter::run(raw_ostream &OS) { << ", // " << Record->getName() << "\n"; OS << "};\n\n"; - OS << "bool " << Target.getName() - << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage " - "&CoverageInfo) 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"; + OS << "// Custom renderers.\n" + << "enum {\n" + << " GICR_Invalid,\n"; + for (const auto &Record : CustomRendererFns) + OS << " GICR_" << Record->getValueAsString("RendererFn") << ", \n"; + OS << "};\n"; + + OS << Target.getName() << "InstructionSelector::CustomRendererFn\n" + << Target.getName() << "InstructionSelector::CustomRenderers[] = {\n" + << " nullptr, // GICP_Invalid\n"; + for (const auto &Record : CustomRendererFns) + OS << " &" << Target.getName() + << "InstructionSelector::" << Record->getValueAsString("RendererFn") + << ", // " << Record->getName() << "\n"; + OS << "};\n\n"; std::stable_sort(Rules.begin(), Rules.end(), [&](const RuleMatcher &A, const RuleMatcher &B) { + int ScoreA = RuleMatcherScores[A.getRuleID()]; + int ScoreB = RuleMatcherScores[B.getRuleID()]; + if (ScoreA > ScoreB) + return true; + if (ScoreB > ScoreA) + return false; if (A.isHigherPriorityThan(B)) { assert(!B.isHigherPriorityThan(A) && "Cannot be more important " "and less important at " @@ -3845,32 +4512,37 @@ void GlobalISelEmitter::run(raw_ostream &OS) { } return false; }); - std::vector<std::unique_ptr<GroupMatcher>> StorageGroupMatcher; - - std::vector<Matcher *> InputRules; - for (Matcher &Rule : Rules) - InputRules.push_back(&Rule); - std::vector<Matcher *> OptRules = - OptimizeMatchTable ? optimizeRules(InputRules, StorageGroupMatcher) - : InputRules; + OS << "bool " << Target.getName() + << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage " + "&CoverageInfo) 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" + << " if (executeMatchTable(*this, OutMIs, State, ISelInfo" + << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures" + << ", CoverageInfo)) {\n" + << " return true;\n" + << " }\n\n" + << " return false;\n" + << "}\n\n"; - MatchTable Table(0); - for (Matcher *Rule : OptRules) { - Rule->emit(Table); - ++NumPatternEmitted; - } - Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; + const MatchTable Table = + buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage); + OS << "const int64_t *" << Target.getName() + << "InstructionSelector::getMatchTable() const {\n"; Table.emitDeclaration(OS); - OS << " if (executeMatchTable(*this, OutMIs, State, MatcherInfo, "; + OS << " return "; Table.emitUse(OS); - OS << ", TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) {\n" - << " return true;\n" - << " }\n\n"; - - OS << " return false;\n" - << "}\n" - << "#endif // ifdef GET_GLOBALISEL_IMPL\n"; + OS << ";\n}\n"; + OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n"; OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n" << "PredicateBitset AvailableModuleFeatures;\n" @@ -3899,137 +4571,290 @@ void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) { Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size())); } -TreePatternNode *GlobalISelEmitter::fixupPatternNode(TreePatternNode *N) { - if (!N->isLeaf()) { - for (unsigned I = 0, E = N->getNumChildren(); I < E; ++I) { - TreePatternNode *OrigChild = N->getChild(I); - TreePatternNode *NewChild = fixupPatternNode(OrigChild); - if (OrigChild != NewChild) - N->setChild(I, NewChild); - } - - if (N->getOperator()->getName() == "ld") { - // If it's a signext-load we need to adapt the pattern slightly. We need - // to split the node into (sext (ld ...)), remove the <<signext>> predicate, - // and then apply the <<signextTY>> predicate by updating the result type - // of the load. - // - // For example: - // (ld:[i32] [iPTR])<<unindexed>><<signext>><<signexti16>> - // must be transformed into: - // (sext:[i32] (ld:[i16] [iPTR])<<unindexed>>) - // - // Likewise for zeroext-load and anyext-load. - - std::vector<TreePredicateFn> Predicates; - bool IsSignExtLoad = false; - bool IsZeroExtLoad = false; - bool IsAnyExtLoad = false; - Record *MemVT = nullptr; - for (const auto &P : N->getPredicateFns()) { - if (P.isLoad() && P.isSignExtLoad()) { - IsSignExtLoad = true; - continue; - } - if (P.isLoad() && P.isZeroExtLoad()) { - IsZeroExtLoad = true; - continue; - } - if (P.isLoad() && P.isAnyExtLoad()) { - IsAnyExtLoad = true; - continue; - } - if (P.isLoad() && P.getMemoryVT()) { - MemVT = P.getMemoryVT(); - continue; - } - Predicates.push_back(P); - } - - if ((IsSignExtLoad || IsZeroExtLoad || IsAnyExtLoad) && MemVT) { - assert((IsSignExtLoad + IsZeroExtLoad + IsAnyExtLoad) == 1 && - "IsSignExtLoad, IsZeroExtLoad, IsAnyExtLoad are mutually exclusive"); - TreePatternNode *Ext = new TreePatternNode( - RK.getDef(IsSignExtLoad ? "sext" - : IsZeroExtLoad ? "zext" : "anyext"), - {N}, 1); - Ext->setType(0, N->getType(0)); - N->clearPredicateFns(); - N->setPredicateFns(Predicates); - N->setType(0, getValueType(MemVT)); - return Ext; - } +void RuleMatcher::optimize() { + for (auto &Item : InsnVariableIDs) { + InstructionMatcher &InsnMatcher = *Item.first; + for (auto &OM : InsnMatcher.operands()) { + // Complex Patterns are usually expensive and they relatively rarely fail + // on their own: more often we end up throwing away all the work done by a + // matching part of a complex pattern because some other part of the + // enclosing pattern didn't match. All of this makes it beneficial to + // delay complex patterns until the very end of the rule matching, + // especially for targets having lots of complex patterns. + for (auto &OP : OM->predicates()) + if (isa<ComplexPatternOperandMatcher>(OP)) + EpilogueMatchers.emplace_back(std::move(OP)); + OM->eraseNullPredicates(); } + InsnMatcher.optimize(); } + llvm::sort( + EpilogueMatchers.begin(), EpilogueMatchers.end(), + [](const std::unique_ptr<PredicateMatcher> &L, + const std::unique_ptr<PredicateMatcher> &R) { + return std::make_tuple(L->getKind(), L->getInsnVarID(), L->getOpIdx()) < + std::make_tuple(R->getKind(), R->getInsnVarID(), R->getOpIdx()); + }); +} - return N; +bool RuleMatcher::hasFirstCondition() const { + if (insnmatchers_empty()) + return false; + InstructionMatcher &Matcher = insnmatchers_front(); + if (!Matcher.predicates_empty()) + return true; + for (auto &OM : Matcher.operands()) + for (auto &OP : OM->predicates()) + if (!isa<InstructionOperandMatcher>(OP)) + return true; + return false; } -void GlobalISelEmitter::fixupPatternTrees(TreePattern *P) { - for (unsigned I = 0, E = P->getNumTrees(); I < E; ++I) { - TreePatternNode *OrigTree = P->getTree(I); - TreePatternNode *NewTree = fixupPatternNode(OrigTree); - if (OrigTree != NewTree) - P->setTree(I, NewTree); - } +const PredicateMatcher &RuleMatcher::getFirstCondition() const { + assert(!insnmatchers_empty() && + "Trying to get a condition from an empty RuleMatcher"); + + InstructionMatcher &Matcher = insnmatchers_front(); + if (!Matcher.predicates_empty()) + return **Matcher.predicates_begin(); + // If there is no more predicate on the instruction itself, look at its + // operands. + for (auto &OM : Matcher.operands()) + for (auto &OP : OM->predicates()) + if (!isa<InstructionOperandMatcher>(OP)) + return *OP; + + llvm_unreachable("Trying to get a condition from an InstructionMatcher with " + "no conditions"); } -std::unique_ptr<PredicateMatcher> RuleMatcher::forgetFirstCondition() { +std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() { assert(!insnmatchers_empty() && - "Trying to forget something that does not exist"); + "Trying to pop a condition from an empty RuleMatcher"); InstructionMatcher &Matcher = insnmatchers_front(); - std::unique_ptr<PredicateMatcher> Condition; if (!Matcher.predicates_empty()) - Condition = Matcher.predicates_pop_front(); - if (!Condition) { - // If there is no more predicate on the instruction itself, look at its - // operands. - assert(!Matcher.operands_empty() && - "Empty instruction should have been discarded"); - OperandMatcher &OpMatcher = **Matcher.operands_begin(); - assert(!OpMatcher.predicates_empty() && "no operand constraint"); - Condition = OpMatcher.predicates_pop_front(); - // If this operand is free of constraints, rip it off. - if (OpMatcher.predicates_empty()) - Matcher.pop_front(); - } - // Rip the instruction off when it is empty. - if (Matcher.operands_empty() && Matcher.predicates_empty()) - insnmatchers_pop_front(); - return Condition; + return Matcher.predicates_pop_front(); + // If there is no more predicate on the instruction itself, look at its + // operands. + for (auto &OM : Matcher.operands()) + for (auto &OP : OM->predicates()) + if (!isa<InstructionOperandMatcher>(OP)) { + std::unique_ptr<PredicateMatcher> Result = std::move(OP); + OM->eraseNullPredicates(); + return Result; + } + + llvm_unreachable("Trying to pop a condition from an InstructionMatcher with " + "no conditions"); } -bool GroupMatcher::lastConditionMatches( +bool GroupMatcher::candidateConditionMatches( const PredicateMatcher &Predicate) const { - const auto &LastCondition = conditions_back(); - return Predicate.isIdentical(*LastCondition); + + if (empty()) { + // Sharing predicates for nested instructions is not supported yet as we + // currently don't hoist the GIM_RecordInsn's properly, therefore we can + // only work on the original root instruction (InsnVarID == 0): + if (Predicate.getInsnVarID() != 0) + return false; + // ... otherwise an empty group can handle any predicate with no specific + // requirements: + return true; + } + + const Matcher &Representative = **Matchers.begin(); + const auto &RepresentativeCondition = Representative.getFirstCondition(); + // ... if not empty, the group can only accomodate matchers with the exact + // same first condition: + return Predicate.isIdentical(RepresentativeCondition); +} + +bool GroupMatcher::addMatcher(Matcher &Candidate) { + if (!Candidate.hasFirstCondition()) + return false; + + const PredicateMatcher &Predicate = Candidate.getFirstCondition(); + if (!candidateConditionMatches(Predicate)) + return false; + + Matchers.push_back(&Candidate); + return true; +} + +void GroupMatcher::finalize() { + assert(Conditions.empty() && "Already finalized?"); + if (empty()) + return; + + Matcher &FirstRule = **Matchers.begin(); + for (;;) { + // All the checks are expected to succeed during the first iteration: + for (const auto &Rule : Matchers) + if (!Rule->hasFirstCondition()) + return; + const auto &FirstCondition = FirstRule.getFirstCondition(); + for (unsigned I = 1, E = Matchers.size(); I < E; ++I) + if (!Matchers[I]->getFirstCondition().isIdentical(FirstCondition)) + return; + + Conditions.push_back(FirstRule.popFirstCondition()); + for (unsigned I = 1, E = Matchers.size(); I < E; ++I) + Matchers[I]->popFirstCondition(); + } } void GroupMatcher::emit(MatchTable &Table) { - unsigned LabelID = Table.allocateLabelID(); - if (!conditions_empty()) { + unsigned LabelID = ~0U; + if (!Conditions.empty()) { + LabelID = Table.allocateLabelID(); Table << MatchTable::Opcode("GIM_Try", +1) << MatchTable::Comment("On fail goto") << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak; - for (auto &Condition : Conditions) - Condition->emitPredicateOpcodes( - Table, *static_cast<RuleMatcher *>(*Rules.begin())); } - // Emit the conditions. - // Then checks apply the rules. - for (const auto &Rule : Rules) - Rule->emit(Table); - // If we don't succeeded for that block, that means we are not going to select - // this instruction. - if (!conditions_empty()) { - Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; - Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak + for (auto &Condition : Conditions) + Condition->emitPredicateOpcodes( + Table, *static_cast<RuleMatcher *>(*Matchers.begin())); + + for (const auto &M : Matchers) + M->emit(Table); + + // Exit the group + if (!Conditions.empty()) + Table << MatchTable::Opcode("GIM_Reject", -1) << MatchTable::LineBreak << MatchTable::Label(LabelID); +} + +bool SwitchMatcher::isSupportedPredicateType(const PredicateMatcher &P) { + return isa<InstructionOpcodeMatcher>(P) || isa<LLTOperandMatcher>(P); +} + +bool SwitchMatcher::candidateConditionMatches( + const PredicateMatcher &Predicate) const { + + if (empty()) { + // Sharing predicates for nested instructions is not supported yet as we + // currently don't hoist the GIM_RecordInsn's properly, therefore we can + // only work on the original root instruction (InsnVarID == 0): + if (Predicate.getInsnVarID() != 0) + return false; + // ... while an attempt to add even a root matcher to an empty SwitchMatcher + // could fail as not all the types of conditions are supported: + if (!isSupportedPredicateType(Predicate)) + return false; + // ... or the condition might not have a proper implementation of + // getValue() / isIdenticalDownToValue() yet: + if (!Predicate.hasValue()) + return false; + // ... otherwise an empty Switch can accomodate the condition with no + // further requirements: + return true; + } + + const Matcher &CaseRepresentative = **Matchers.begin(); + const auto &RepresentativeCondition = CaseRepresentative.getFirstCondition(); + // Switch-cases must share the same kind of condition and path to the value it + // checks: + if (!Predicate.isIdenticalDownToValue(RepresentativeCondition)) + return false; + + const auto Value = Predicate.getValue(); + // ... but be unique with respect to the actual value they check: + return Values.count(Value) == 0; +} + +bool SwitchMatcher::addMatcher(Matcher &Candidate) { + if (!Candidate.hasFirstCondition()) + return false; + + const PredicateMatcher &Predicate = Candidate.getFirstCondition(); + if (!candidateConditionMatches(Predicate)) + return false; + const auto Value = Predicate.getValue(); + Values.insert(Value); + + Matchers.push_back(&Candidate); + return true; +} + +void SwitchMatcher::finalize() { + assert(Condition == nullptr && "Already finalized"); + assert(Values.size() == Matchers.size() && "Broken SwitchMatcher"); + if (empty()) + return; + + std::stable_sort(Matchers.begin(), Matchers.end(), + [](const Matcher *L, const Matcher *R) { + return L->getFirstCondition().getValue() < + R->getFirstCondition().getValue(); + }); + Condition = Matchers[0]->popFirstCondition(); + for (unsigned I = 1, E = Values.size(); I < E; ++I) + Matchers[I]->popFirstCondition(); +} + +void SwitchMatcher::emitPredicateSpecificOpcodes(const PredicateMatcher &P, + MatchTable &Table) { + assert(isSupportedPredicateType(P) && "Predicate type is not supported"); + + if (const auto *Condition = dyn_cast<InstructionOpcodeMatcher>(&P)) { + Table << MatchTable::Opcode("GIM_SwitchOpcode") << MatchTable::Comment("MI") + << MatchTable::IntValue(Condition->getInsnVarID()); + return; + } + if (const auto *Condition = dyn_cast<LLTOperandMatcher>(&P)) { + Table << MatchTable::Opcode("GIM_SwitchType") << MatchTable::Comment("MI") + << MatchTable::IntValue(Condition->getInsnVarID()) + << MatchTable::Comment("Op") + << MatchTable::IntValue(Condition->getOpIdx()); + return; + } + + llvm_unreachable("emitPredicateSpecificOpcodes is broken: can not handle a " + "predicate type that is claimed to be supported"); +} + +void SwitchMatcher::emit(MatchTable &Table) { + assert(Values.size() == Matchers.size() && "Broken SwitchMatcher"); + if (empty()) + return; + assert(Condition != nullptr && + "Broken SwitchMatcher, hasn't been finalized?"); + + std::vector<unsigned> LabelIDs(Values.size()); + std::generate(LabelIDs.begin(), LabelIDs.end(), + [&Table]() { return Table.allocateLabelID(); }); + const unsigned Default = Table.allocateLabelID(); + + const int64_t LowerBound = Values.begin()->getRawValue(); + const int64_t UpperBound = Values.rbegin()->getRawValue() + 1; + + emitPredicateSpecificOpcodes(*Condition, Table); + + Table << MatchTable::Comment("[") << MatchTable::IntValue(LowerBound) + << MatchTable::IntValue(UpperBound) << MatchTable::Comment(")") + << MatchTable::Comment("default:") << MatchTable::JumpTarget(Default); + + int64_t J = LowerBound; + auto VI = Values.begin(); + for (unsigned I = 0, E = Values.size(); I < E; ++I) { + auto V = *VI++; + while (J++ < V.getRawValue()) + Table << MatchTable::IntValue(0); + V.turnIntoComment(); + Table << MatchTable::LineBreak << V << MatchTable::JumpTarget(LabelIDs[I]); + } + Table << MatchTable::LineBreak; + + for (unsigned I = 0, E = Values.size(); I < E; ++I) { + Table << MatchTable::Label(LabelIDs[I]); + Matchers[I]->emit(Table); + Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; } + Table << MatchTable::Label(Default); } -unsigned OperandMatcher::getInsnVarID() const { return Insn.getVarID(); } +unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); } } // end anonymous namespace |