diff options
Diffstat (limited to 'llvm/utils/TableGen/GlobalISelEmitter.cpp')
| -rw-r--r-- | llvm/utils/TableGen/GlobalISelEmitter.cpp | 865 |
1 files changed, 560 insertions, 305 deletions
diff --git a/llvm/utils/TableGen/GlobalISelEmitter.cpp b/llvm/utils/TableGen/GlobalISelEmitter.cpp index 1237f8c4e16..c852fb36e17 100644 --- a/llvm/utils/TableGen/GlobalISelEmitter.cpp +++ b/llvm/utils/TableGen/GlobalISelEmitter.cpp @@ -100,6 +100,7 @@ private: LLT Ty; public: + LLTCodeGen() = default; LLTCodeGen(const LLT &Ty) : Ty(Ty) {} std::string getCxxEnumValue() const { @@ -401,13 +402,34 @@ 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; @@ -453,11 +475,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); @@ -586,8 +617,12 @@ 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; }; MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules, @@ -599,34 +634,75 @@ MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules, return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; } -class GroupMatcher : public Matcher { - SmallVector<std::unique_ptr<PredicateMatcher>, 8> Conditions; - SmallVector<Matcher *, 8> Rules; +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(); } - void emit(MatchTable &Table) override; + bool hasFirstCondition() const override { return !Conditions.empty(); } - 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"); - } +private: + /// See if a candidate matcher could be added to this group solely by + /// analyzing its first condition. + bool candidateConditionMatches(const PredicateMatcher &Predicate) const; }; /// Generates code to check that a match rule matches. @@ -640,20 +716,19 @@ protected: /// 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. 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. @@ -663,7 +738,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() @@ -673,6 +748,7 @@ protected: unsigned NextTempRegID; std::vector<Record *> RequiredFeatures; + std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers; ArrayRef<SMLoc> SrcLoc; @@ -706,16 +782,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(); } @@ -737,7 +806,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; @@ -765,11 +834,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. @@ -781,7 +849,11 @@ 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; // FIXME: Remove this as soon as possible InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); } @@ -789,6 +861,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()); } }; @@ -799,58 +874,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)...); - } } }; @@ -868,6 +954,7 @@ public: /// are currently not compared between each other. enum PredicateKind { IPM_Opcode, + IPM_NumOperands, IPM_ImmPredicate, IPM_AtomicOrderingMMO, IPM_MemoryLLTSize, @@ -893,7 +980,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, @@ -902,16 +991,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). - LLVM_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. @@ -927,20 +1023,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 <> @@ -959,12 +1045,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. @@ -973,6 +1064,16 @@ protected: LLTCodeGen Ty; public: + 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) { KnownTypes.insert(Ty); @@ -985,17 +1086,31 @@ 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::map<LLTCodeGen, unsigned> LLTOperandMatcher::TypeIDValues; + /// Generates code to check that an operand is a pointer to any address space. /// /// In SelectionDAG, the types did not describe pointers or address spaces. As a @@ -1227,7 +1342,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 { @@ -1240,23 +1366,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); } @@ -1264,7 +1386,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; @@ -1272,7 +1394,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))) @@ -1284,7 +1406,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, @@ -1297,7 +1419,7 @@ public: return AllocatedTemporariesBaseID; } - bool isSameAsAnotherOperand() const { + bool isSameAsAnotherOperand() { for (const auto &Predicate : predicates()) if (isa<SameOperandMatcher>(Predicate)) return true; @@ -1305,21 +1427,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()) @@ -1363,15 +1470,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"; } @@ -1380,7 +1483,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) {} @@ -1392,12 +1505,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; } @@ -1424,8 +1544,17 @@ public: bool isConstantInstruction() const { return I->TheDef->getName() == "G_CONSTANT"; } + + unsigned getNumOperands() const { return I->Operands.size(); } + + StringRef getOperandType(unsigned OpIdx) const { + return I->Operands[OpIdx].OperandType; + } }; +DenseMap<const CodeGenInstruction *, unsigned> + InstructionOpcodeMatcher::OpcodeValues; + /// Generates code to check that this instruction is a constant whose value /// meets an immediate predicate. /// @@ -1503,10 +1632,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"; @@ -1605,8 +1741,7 @@ public: /// 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; @@ -1627,9 +1762,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, @@ -1645,7 +1788,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; @@ -1668,21 +1811,18 @@ 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) { + 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) { 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); - } - /// 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 { emitPredicateListOpcodes(Table, Rule); + for (const auto &Operand : Operands) Operand->emitPredicateOpcodes(Table, Rule); } @@ -1690,17 +1830,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; } @@ -1716,13 +1858,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) { @@ -1730,24 +1872,30 @@ 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(); } }; -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()); +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 @@ -1775,17 +1923,20 @@ 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); } @@ -1859,7 +2010,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; } }; @@ -1895,7 +2046,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") @@ -1926,7 +2077,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") @@ -1957,7 +2108,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) @@ -1997,7 +2148,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; @@ -2146,8 +2297,7 @@ public: } 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_CustomRenderer") << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID) @@ -2193,7 +2343,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. @@ -2208,7 +2358,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; @@ -2225,7 +2375,7 @@ public: 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); @@ -2417,27 +2567,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; @@ -2455,7 +2591,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) @@ -2474,25 +2610,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 @@ -2506,7 +2627,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()) { @@ -2515,8 +2638,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. @@ -2576,12 +2697,18 @@ void RuleMatcher::emit(MatchTable &Table) { } } + for (const auto &PM : EpilogueMatchers) + PM->emitPredicateOpcodes(Table, *this); + for (const auto &MA : Actions) MA->emitActionOpcodes(Table, *this); 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); @@ -2649,7 +2776,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) @@ -2657,7 +2784,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; } @@ -2700,6 +2827,8 @@ private: // Rule coverage information. Optional<CodeGenCoverage> RuleCoverage; + void gatherOpcodeValues(); + void gatherTypeIDValues(); void gatherNodeEquivs(); Record *findNodeEquiv(Record *N) const; const CodeGenInstruction *getEquivNode(Record &Equiv, @@ -2750,16 +2879,15 @@ private: void declareSubtargetFeature(Record *Predicate); + 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 + /// they share. \p MatcherStorage is used as a memory container /// for 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). /// - /// What this optimization does looks like: + /// What this optimization does looks like if GroupT = GroupMatcher: /// Output without optimization: /// \verbatim /// # R1 @@ -2780,14 +2908,20 @@ private: /// # R2 /// # predicate C /// \endverbatim - std::vector<Matcher *> optimizeRules( + template <class GroupT> + static std::vector<Matcher *> optimizeRules( ArrayRef<Matcher *> Rules, - std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher); - - MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize, - bool WithCoverage); + std::vector<std::unique_ptr<Matcher>> &MatcherStorage); }; +void GlobalISelEmitter::gatherOpcodeValues() { + InstructionOpcodeMatcher::initOpcodeValuesMap(Target); +} + +void GlobalISelEmitter::gatherTypeIDValues() { + LLTOperandMatcher::initTypeIDValuesMap(); +} + void GlobalISelEmitter::gatherNodeEquivs() { assert(NodeEquivs.empty()); for (Record *Equiv : RK.getAllDerivedDefinitions("GINodeEquiv")) @@ -3522,7 +3656,6 @@ Expected<RuleMatcher> GlobalISelEmitter::runOnPattern(const PatternToMatch &P) { M.addAction<DebugCommentAction>(llvm::to_string(*P.getSrcPattern()) + " => " + llvm::to_string(*P.getDstPattern())); - M.addAction<DebugCommentAction>("Rule ID " + llvm::to_string(M.getRuleID())); if (auto Error = importRulePredicates(M, P.getPredicates())) return std::move(Error); @@ -3778,35 +3911,53 @@ void GlobalISelEmitter::emitImmPredicates( << "}\n"; } +template <class GroupT> std::vector<Matcher *> GlobalISelEmitter::optimizeRules( ArrayRef<Matcher *> Rules, - std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher) { + 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); } - LLVM_DEBUG(dbgs() << "NbGroup: " << NbGroup << "\n"); + ProcessCurrentGroup(); + + DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n"); + assert(CurrentGroup->empty() && "The last group wasn't properly processed"); return OptRules; } @@ -3820,9 +3971,15 @@ GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules, if (!Optimize) return MatchTable::buildTable(InputRules, WithCoverage); - std::vector<std::unique_ptr<GroupMatcher>> StorageGroupMatcher; + for (Matcher *Rule : InputRules) + Rule->optimize(); + + std::vector<std::unique_ptr<Matcher>> MatcherStorage; std::vector<Matcher *> OptRules = - optimizeRules(InputRules, StorageGroupMatcher); + optimizeRules<GroupMatcher>(InputRules, MatcherStorage); + + for (Matcher *Rule : OptRules) + Rule->optimize(); return MatchTable::buildTable(OptRules, WithCoverage); } @@ -3842,6 +3999,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(); @@ -3930,8 +4092,8 @@ void GlobalISelEmitter::run(raw_ostream &OS) { OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n" << ", State(" << MaxTemporaries << "),\n" - << "ISelInfo({TypeObjects, FeatureBitsets, ComplexPredicateFns, " - "CustomRenderers})\n" + << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets" + << ", ComplexPredicateFns, CustomRenderers)\n" << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n"; OS << "#ifdef GET_GLOBALISEL_IMPL\n"; @@ -3973,7 +4135,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 << " "; @@ -4152,62 +4315,154 @@ void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) { Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size())); } -std::unique_ptr<PredicateMatcher> RuleMatcher::forgetFirstCondition() { +void RuleMatcher::optimize() { + for (auto &Item : InsnVariableIDs) { + InstructionMatcher &InsnMatcher = *Item.first; + for (auto &OM : InsnMatcher.operands()) { + // Register Banks checks rarely fail, but often crash as targets usually + // provide only partially defined RegisterBankInfo::getRegBankFromRegClass + // method. Often the problem is hidden as non-optimized MatchTable checks + // banks rather late, most notably after checking target / function / + // module features and a few opcodes. That makes these checks a) + // beneficial to delay until the very end (we don't want to perform a lot + // of checks that all pass and then fail at the very end) b) not safe to + // have as early checks. + for (auto &OP : OM->predicates()) + if (isa<RegisterBankOperandMatcher>(OP) || + 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()); + }); +} + +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; +} + +const PredicateMatcher &RuleMatcher::getFirstCondition() const { assert(!insnmatchers_empty() && - "Trying to forget something that does not exist"); + "Trying to get 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_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"); } -bool GroupMatcher::lastConditionMatches( +std::unique_ptr<PredicateMatcher> RuleMatcher::popFirstCondition() { + assert(!insnmatchers_empty() && + "Trying to pop a condition from an empty RuleMatcher"); + + InstructionMatcher &Matcher = insnmatchers_front(); + if (!Matcher.predicates_empty()) + 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)) { + auto Result = std::move(OP); + OM->eraseNullPredicates(); + return Result; + } + + llvm_unreachable("Trying to pop a condition from an InstructionMatcher with " + "no conditions"); +} + +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(); + + 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); - } } -unsigned OperandMatcher::getInsnVarID() const { return Insn.getVarID(); } +unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); } } // end anonymous namespace |
