219 lines · c
1//===- PredicateTree.h - Predicate tree node definitions --------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file contains definitions for nodes of a tree structure for representing10// the general control flow within a pattern match.11//12//===----------------------------------------------------------------------===//13 14#ifndef MLIR_LIB_CONVERSION_PDLTOPDLINTERP_PREDICATETREE_H_15#define MLIR_LIB_CONVERSION_PDLTOPDLINTERP_PREDICATETREE_H_16 17#include "Predicate.h"18#include "mlir/Dialect/PDL/IR/PDLOps.h"19#include "llvm/ADT/MapVector.h"20 21namespace mlir {22class ModuleOp;23 24namespace pdl_to_pdl_interp {25 26class MatcherNode;27 28/// A PositionalPredicate is a predicate that is associated with a specific29/// positional value.30struct PositionalPredicate {31 PositionalPredicate(Position *pos,32 const PredicateBuilder::Predicate &predicate)33 : position(pos), question(predicate.first), answer(predicate.second) {}34 35 /// The position the predicate is applied to.36 Position *position;37 38 /// The question that the predicate applies.39 Qualifier *question;40 41 /// The expected answer of the predicate.42 Qualifier *answer;43};44 45//===----------------------------------------------------------------------===//46// MatcherNode47//===----------------------------------------------------------------------===//48 49/// This class represents the base of a predicate matcher node.50class MatcherNode {51public:52 virtual ~MatcherNode() = default;53 54 /// Given a module containing PDL pattern operations, generate a matcher tree55 /// using the patterns within the given module and return the root matcher56 /// node. `valueToPosition` is a map that is populated with the original57 /// pdl values and their corresponding positions in the matcher tree.58 static std::unique_ptr<MatcherNode>59 generateMatcherTree(ModuleOp module, PredicateBuilder &builder,60 DenseMap<Value, Position *> &valueToPosition);61 62 /// Returns the position on which the question predicate should be checked.63 Position *getPosition() const { return position; }64 65 /// Returns the predicate checked on this node.66 Qualifier *getQuestion() const { return question; }67 68 /// Returns the node that should be visited if this, or a subsequent node69 /// fails.70 std::unique_ptr<MatcherNode> &getFailureNode() { return failureNode; }71 72 /// Sets the node that should be visited if this, or a subsequent node fails.73 void setFailureNode(std::unique_ptr<MatcherNode> node) {74 failureNode = std::move(node);75 }76 77 /// Returns the unique type ID of this matcher instance. This should not be78 /// used directly, and is provided to support type casting.79 TypeID getMatcherTypeID() const { return matcherTypeID; }80 81protected:82 MatcherNode(TypeID matcherTypeID, Position *position = nullptr,83 Qualifier *question = nullptr,84 std::unique_ptr<MatcherNode> failureNode = nullptr);85 86private:87 /// The position on which the predicate should be checked.88 Position *position;89 90 /// The predicate that is checked on the given position.91 Qualifier *question;92 93 /// The node to visit if this node fails.94 std::unique_ptr<MatcherNode> failureNode;95 96 /// An owning store for the failure node if it is owned by this node.97 std::unique_ptr<MatcherNode> failureNodeStorage;98 99 /// A unique identifier for the derived matcher node, used for type casting.100 TypeID matcherTypeID;101};102 103//===----------------------------------------------------------------------===//104// BoolNode105//===----------------------------------------------------------------------===//106 107/// A BoolNode denotes a question with a boolean-like result. These nodes branch108/// to a single node on a successful result, otherwise defaulting to the failure109/// node.110struct BoolNode : public MatcherNode {111 BoolNode(Position *position, Qualifier *question, Qualifier *answer,112 std::unique_ptr<MatcherNode> successNode,113 std::unique_ptr<MatcherNode> failureNode = nullptr);114 115 /// Returns if the given matcher node is an instance of this class, used to116 /// support type casting.117 static bool classof(const MatcherNode *node) {118 return node->getMatcherTypeID() == TypeID::get<BoolNode>();119 }120 121 /// Returns the expected answer of this boolean node.122 Qualifier *getAnswer() const { return answer; }123 124 /// Returns the node that should be visited on success.125 std::unique_ptr<MatcherNode> &getSuccessNode() { return successNode; }126 127private:128 /// The expected answer of this boolean node.129 Qualifier *answer;130 131 /// The next node if this node succeeds. Otherwise, go to the failure node.132 std::unique_ptr<MatcherNode> successNode;133};134 135//===----------------------------------------------------------------------===//136// ExitNode137//===----------------------------------------------------------------------===//138 139/// An ExitNode is a special sentinel node that denotes the end of matcher.140struct ExitNode : public MatcherNode {141 ExitNode() : MatcherNode(TypeID::get<ExitNode>()) {}142 143 /// Returns if the given matcher node is an instance of this class, used to144 /// support type casting.145 static bool classof(const MatcherNode *node) {146 return node->getMatcherTypeID() == TypeID::get<ExitNode>();147 }148};149 150//===----------------------------------------------------------------------===//151// SuccessNode152//===----------------------------------------------------------------------===//153 154/// A SuccessNode denotes that a given high level pattern has successfully been155/// matched. This does not terminate the matcher, as there may be multiple156/// successful matches.157struct SuccessNode : public MatcherNode {158 explicit SuccessNode(pdl::PatternOp pattern, Value root,159 std::unique_ptr<MatcherNode> failureNode);160 161 /// Returns if the given matcher node is an instance of this class, used to162 /// support type casting.163 static bool classof(const MatcherNode *node) {164 return node->getMatcherTypeID() == TypeID::get<SuccessNode>();165 }166 167 /// Return the high level pattern operation that is matched with this node.168 pdl::PatternOp getPattern() const { return pattern; }169 170 /// Return the chosen root of the pattern.171 Value getRoot() const { return root; }172 173private:174 /// The high level pattern operation that was successfully matched with this175 /// node.176 pdl::PatternOp pattern;177 178 /// The chosen root of the pattern.179 Value root;180};181 182//===----------------------------------------------------------------------===//183// SwitchNode184//===----------------------------------------------------------------------===//185 186/// A SwitchNode denotes a question with multiple potential results. These nodes187/// branch to a specific node based on the result of the question.188struct SwitchNode : public MatcherNode {189 SwitchNode(Position *position, Qualifier *question);190 191 /// Returns if the given matcher node is an instance of this class, used to192 /// support type casting.193 static bool classof(const MatcherNode *node) {194 return node->getMatcherTypeID() == TypeID::get<SwitchNode>();195 }196 197 /// Returns the children of this switch node. The children are contained198 /// within a mapping between the various case answers to destination matcher199 /// nodes.200 using ChildMapT = llvm::MapVector<Qualifier *, std::unique_ptr<MatcherNode>>;201 ChildMapT &getChildren() { return children; }202 203 /// Returns the child at the given index.204 std::pair<Qualifier *, std::unique_ptr<MatcherNode>> &getChild(unsigned i) {205 assert(i < children.size() && "invalid child index");206 return *std::next(children.begin(), i);207 }208 209private:210 /// Switch predicate "answers" select the child. Answers that are not found211 /// default to the failure node.212 ChildMapT children;213};214 215} // namespace pdl_to_pdl_interp216} // namespace mlir217 218#endif // MLIR_CONVERSION_PDLTOPDLINTERP_PREDICATETREE_H_219