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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains definitions for nodes of a tree structure for representing
10// 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 specific
29/// 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// MatcherNode
47//===----------------------------------------------------------------------===//
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 tree
55 /// using the patterns within the given module and return the root matcher
56 /// node. `valueToPosition` is a map that is populated with the original
57 /// 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 node
69 /// 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 be
78 /// 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// BoolNode
105//===----------------------------------------------------------------------===//
106
107/// A BoolNode denotes a question with a boolean-like result. These nodes branch
108/// to a single node on a successful result, otherwise defaulting to the failure
109/// 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 to
116 /// 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// ExitNode
137//===----------------------------------------------------------------------===//
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 to
144 /// support type casting.
145 static bool classof(const MatcherNode *node) {
146 return node->getMatcherTypeID() == TypeID::get<ExitNode>();
147 }
148};
149
150//===----------------------------------------------------------------------===//
151// SuccessNode
152//===----------------------------------------------------------------------===//
153
154/// A SuccessNode denotes that a given high level pattern has successfully been
155/// matched. This does not terminate the matcher, as there may be multiple
156/// 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 to
162 /// 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 this
175 /// node.
176 pdl::PatternOp pattern;
177
178 /// The chosen root of the pattern.
179 Value root;
180};
181
182//===----------------------------------------------------------------------===//
183// SwitchNode
184//===----------------------------------------------------------------------===//
185
186/// A SwitchNode denotes a question with multiple potential results. These nodes
187/// 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 to
192 /// 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 contained
198 /// within a mapping between the various case answers to destination matcher
199 /// 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(x: children.begin(), n: i);
207 }
208
209private:
210 /// Switch predicate "answers" select the child. Answers that are not found
211 /// default to the failure node.
212 ChildMapT children;
213};
214
215} // namespace pdl_to_pdl_interp
216} // namespace mlir
217
218#endif // MLIR_CONVERSION_PDLTOPDLINTERP_PREDICATETREE_H_
219

source code of mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.h