13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.core.match;
26
27 import org.graalvm.compiler.debug.CounterKey;
28 import org.graalvm.compiler.debug.DebugContext;
29 import org.graalvm.compiler.graph.Node;
30 import org.graalvm.compiler.graph.Position;
31 import org.graalvm.compiler.nodeinfo.InputType;
32 import org.graalvm.compiler.nodeinfo.Verbosity;
33
34 /**
35 * A simple recursive pattern matcher for a DAG of nodes.
36 */
37
38 public class MatchPattern {
39
40 enum MatchResultCode {
41 OK,
42 WRONG_CLASS,
43 NAMED_VALUE_MISMATCH,
44 TOO_MANY_USERS,
45 NOT_IN_BLOCK,
46 NOT_SAFE,
47 ALREADY_USED,
48 }
49
50 /**
51 * A descriptive result for match failures. This can be helpful for debugging why a match
52 * doesn't work as expected.
53 */
54 static class Result {
55 final MatchResultCode code;
56
57 final Node node;
58
59 final MatchPattern matcher;
60
61 Result(MatchResultCode result, Node node, MatchPattern matcher) {
62 this.code = result;
63 this.node = node;
64 this.matcher = matcher;
65 }
66
67 private static final CounterKey MatchResult_WRONG_CLASS = DebugContext.counter("MatchResult_WRONG_CLASS");
68 private static final CounterKey MatchResult_NAMED_VALUE_MISMATCH = DebugContext.counter("MatchResult_NAMED_VALUE_MISMATCH");
69 private static final CounterKey MatchResult_TOO_MANY_USERS = DebugContext.counter("MatchResult_TOO_MANY_USERS");
70 private static final CounterKey MatchResult_NOT_IN_BLOCK = DebugContext.counter("MatchResult_NOT_IN_BLOCK");
71 private static final CounterKey MatchResult_NOT_SAFE = DebugContext.counter("MatchResult_NOT_SAFE");
72 private static final CounterKey MatchResult_ALREADY_USED = DebugContext.counter("MatchResult_ALREADY_USED");
73
74 static final Result OK = new Result(MatchResultCode.OK, null, null);
75 private static final Result CACHED_WRONG_CLASS = new Result(MatchResultCode.WRONG_CLASS, null, null);
76 private static final Result CACHED_NAMED_VALUE_MISMATCH = new Result(MatchResultCode.NAMED_VALUE_MISMATCH, null, null);
77 private static final Result CACHED_TOO_MANY_USERS = new Result(MatchResultCode.TOO_MANY_USERS, null, null);
78 private static final Result CACHED_NOT_IN_BLOCK = new Result(MatchResultCode.NOT_IN_BLOCK, null, null);
79 private static final Result CACHED_NOT_SAFE = new Result(MatchResultCode.NOT_SAFE, null, null);
80 private static final Result CACHED_ALREADY_USED = new Result(MatchResultCode.ALREADY_USED, null, null);
81
82 static Result wrongClass(Node node, MatchPattern matcher) {
83 MatchResult_WRONG_CLASS.increment(node.getDebug());
84 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.WRONG_CLASS, node, matcher) : CACHED_WRONG_CLASS;
85 }
86
87 static Result namedValueMismatch(Node node, MatchPattern matcher) {
88 MatchResult_NAMED_VALUE_MISMATCH.increment(node.getDebug());
89 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.NAMED_VALUE_MISMATCH, node, matcher) : CACHED_NAMED_VALUE_MISMATCH;
90 }
91
92 static Result tooManyUsers(Node node, MatchPattern matcher) {
93 MatchResult_TOO_MANY_USERS.increment(node.getDebug());
94 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.TOO_MANY_USERS, node, matcher) : CACHED_TOO_MANY_USERS;
95 }
96
97 static Result notInBlock(Node node, MatchPattern matcher) {
98 MatchResult_NOT_IN_BLOCK.increment(node.getDebug());
99 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.NOT_IN_BLOCK, node, matcher) : CACHED_NOT_IN_BLOCK;
100 }
101
102 static Result notSafe(Node node, MatchPattern matcher) {
103 MatchResult_NOT_SAFE.increment(node.getDebug());
104 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.NOT_SAFE, node, matcher) : CACHED_NOT_SAFE;
105 }
106
107 static Result alreadyUsed(Node node, MatchPattern matcher) {
108 MatchResult_ALREADY_USED.increment(node.getDebug());
109 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.ALREADY_USED, node, matcher) : CACHED_ALREADY_USED;
110 }
111
112 @Override
113 public String toString() {
114 if (code == MatchResultCode.OK) {
115 return "OK";
116 }
117 if (node == null) {
118 return code.toString();
119 } else {
120 return code + " " + node.toString(Verbosity.Id) + "|" + node.getClass().getSimpleName() + " " + matcher;
121 }
122 }
123 }
124
125 /**
126 * The expected type of the node. It must match exactly.
127 */
128 private final Class<? extends Node> nodeClass;
129
130 /**
131 * An optional name for this node. A name can occur multiple times in a match and that name must
132 * always refer to the same node of the match will fail.
133 */
134 private final String name;
135
136 /**
137 * Patterns to match the inputs.
138 */
139 private final MatchPattern[] patterns;
140
141 /**
142 * The inputs to match the patterns against.
143 */
144 private final Position[] inputs;
145
146 /**
147 * Can there only be one user of the node. Constant nodes can be matched even if there are other
148 * users.
149 */
150 private final boolean singleUser;
151
152 private static final MatchPattern[] EMPTY_PATTERNS = new MatchPattern[0];
153
154 public MatchPattern(String name, boolean singleUser) {
155 this(null, name, singleUser);
156 }
157
158 public MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser) {
159 this.nodeClass = nodeClass;
160 this.name = name;
161 this.singleUser = singleUser;
162 this.patterns = EMPTY_PATTERNS;
163 this.inputs = null;
164 }
165
166 private MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser, MatchPattern[] patterns, Position[] inputs) {
167 assert inputs == null || inputs.length == patterns.length;
168 this.nodeClass = nodeClass;
169 this.name = name;
170 this.singleUser = singleUser;
171 this.patterns = patterns;
172 this.inputs = inputs;
173 }
174
175 public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, Position[] inputs, boolean singleUser) {
176 this(nodeClass, name, singleUser, new MatchPattern[]{first}, inputs);
177 }
178
179 public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, Position[] inputs, boolean singleUser) {
180 this(nodeClass, name, singleUser, new MatchPattern[]{first, second}, inputs);
181 }
182
183 public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, MatchPattern third, Position[] inputs, boolean singleUser) {
184 this(nodeClass, name, singleUser, new MatchPattern[]{first, second, third}, inputs);
185 }
186
187 Class<? extends Node> nodeClass() {
188 return nodeClass;
189 }
190
191 private Result matchType(Node node) {
192 if (nodeClass != null && node.getClass() != nodeClass) {
193 return Result.wrongClass(node, this);
194 }
195 return Result.OK;
196 }
197
198 /**
199 * Match any named nodes and ensure that the consumed nodes can be safely merged.
200 *
201 * @param node
202 * @param context
203 * @return Result.OK is the pattern can be safely matched.
204 */
205 Result matchUsage(Node node, MatchContext context) {
206 Result result = matchUsage(node, context, true);
207 if (result == Result.OK) {
208 result = context.validate();
209 }
210 return result;
211 }
212
213 private Result matchUsage(Node node, MatchContext context, boolean atRoot) {
214 Result result = matchType(node);
215 if (result != Result.OK) {
216 return result;
217 }
218 if (singleUser && !atRoot) {
219 result = context.consume(node);
220 if (result != Result.OK) {
221 return result;
222 }
223 }
224
225 if (name != null) {
226 result = context.captureNamedValue(name, nodeClass, node);
227 }
228
229 for (int input = 0; input < patterns.length; input++) {
230 result = patterns[input].matchUsage(getInput(input, node), context, false);
231 if (result != Result.OK) {
232 return result;
233 }
234 }
235
236 return result;
237 }
238
239 /**
|
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.core.match;
26
27 import org.graalvm.compiler.debug.CounterKey;
28 import org.graalvm.compiler.debug.DebugContext;
29 import org.graalvm.compiler.graph.Node;
30 import org.graalvm.compiler.graph.Position;
31 import org.graalvm.compiler.nodeinfo.InputType;
32 import org.graalvm.compiler.nodeinfo.Verbosity;
33 import org.graalvm.compiler.nodes.calc.FloatingNode;
34
35 /**
36 * A simple recursive pattern matcher for a DAG of nodes.
37 */
38
39 public class MatchPattern {
40
41 enum MatchResultCode {
42 OK,
43 WRONG_CLASS,
44 NAMED_VALUE_MISMATCH,
45 TOO_MANY_USERS,
46 NOT_IN_BLOCK,
47 NOT_SAFE,
48 ALREADY_USED,
49 TOO_LATE,
50 }
51
52 /**
53 * A descriptive result for match failures. This can be helpful for debugging why a match
54 * doesn't work as expected.
55 */
56 static class Result {
57 final MatchResultCode code;
58
59 final Node node;
60
61 final MatchPattern matcher;
62
63 Result(MatchResultCode result, Node node, MatchPattern matcher) {
64 this.code = result;
65 this.node = node;
66 this.matcher = matcher;
67 }
68
69 private static final CounterKey MatchResult_WRONG_CLASS = DebugContext.counter("MatchResult_WRONG_CLASS");
70 private static final CounterKey MatchResult_NAMED_VALUE_MISMATCH = DebugContext.counter("MatchResult_NAMED_VALUE_MISMATCH");
71 private static final CounterKey MatchResult_TOO_MANY_USERS = DebugContext.counter("MatchResult_TOO_MANY_USERS");
72 private static final CounterKey MatchResult_NOT_IN_BLOCK = DebugContext.counter("MatchResult_NOT_IN_BLOCK");
73 private static final CounterKey MatchResult_NOT_SAFE = DebugContext.counter("MatchResult_NOT_SAFE");
74 private static final CounterKey MatchResult_ALREADY_USED = DebugContext.counter("MatchResult_ALREADY_USED");
75 private static final CounterKey MatchResult_TOO_LATE = DebugContext.counter("MatchResult_TOO_LATE");
76
77 static final Result OK = new Result(MatchResultCode.OK, null, null);
78 private static final Result CACHED_WRONG_CLASS = new Result(MatchResultCode.WRONG_CLASS, null, null);
79 private static final Result CACHED_NAMED_VALUE_MISMATCH = new Result(MatchResultCode.NAMED_VALUE_MISMATCH, null, null);
80 private static final Result CACHED_TOO_MANY_USERS = new Result(MatchResultCode.TOO_MANY_USERS, null, null);
81 private static final Result CACHED_NOT_IN_BLOCK = new Result(MatchResultCode.NOT_IN_BLOCK, null, null);
82 private static final Result CACHED_NOT_SAFE = new Result(MatchResultCode.NOT_SAFE, null, null);
83 private static final Result CACHED_ALREADY_USED = new Result(MatchResultCode.ALREADY_USED, null, null);
84 private static final Result CACHED_TOO_LATE = new Result(MatchResultCode.TOO_LATE, null, null);
85
86 static Result wrongClass(Node node, MatchPattern matcher) {
87 MatchResult_WRONG_CLASS.increment(node.getDebug());
88 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.WRONG_CLASS, node, matcher) : CACHED_WRONG_CLASS;
89 }
90
91 static Result namedValueMismatch(Node node, MatchPattern matcher) {
92 MatchResult_NAMED_VALUE_MISMATCH.increment(node.getDebug());
93 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.NAMED_VALUE_MISMATCH, node, matcher) : CACHED_NAMED_VALUE_MISMATCH;
94 }
95
96 static Result tooManyUsers(Node node, MatchPattern matcher) {
97 MatchResult_TOO_MANY_USERS.increment(node.getDebug());
98 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.TOO_MANY_USERS, node, matcher) : CACHED_TOO_MANY_USERS;
99 }
100
101 static Result notInBlock(Node node, MatchPattern matcher) {
102 MatchResult_NOT_IN_BLOCK.increment(node.getDebug());
103 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.NOT_IN_BLOCK, node, matcher) : CACHED_NOT_IN_BLOCK;
104 }
105
106 static Result notSafe(Node node, MatchPattern matcher) {
107 MatchResult_NOT_SAFE.increment(node.getDebug());
108 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.NOT_SAFE, node, matcher) : CACHED_NOT_SAFE;
109 }
110
111 static Result alreadyUsed(Node node, MatchPattern matcher) {
112 MatchResult_ALREADY_USED.increment(node.getDebug());
113 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.ALREADY_USED, node, matcher) : CACHED_ALREADY_USED;
114 }
115
116 static Result tooLate(Node node, MatchPattern matcher) {
117 MatchResult_TOO_LATE.increment(node.getDebug());
118 return node.getDebug().isLogEnabled() ? new Result(MatchResultCode.TOO_LATE, node, matcher) : CACHED_TOO_LATE;
119 }
120
121 @Override
122 public String toString() {
123 if (code == MatchResultCode.OK) {
124 return "OK";
125 }
126 if (node == null) {
127 return code.toString();
128 } else {
129 return code + " " + node.toString(Verbosity.Id) + "|" + node.getClass().getSimpleName() + " " + matcher;
130 }
131 }
132 }
133
134 /**
135 * The expected type of the node. It must match exactly.
136 */
137 private final Class<? extends Node> nodeClass;
138
139 /**
140 * An optional name for this node. A name can occur multiple times in a match and that name must
141 * always refer to the same node of the match will fail.
142 */
143 private final String name;
144
145 /**
146 * Patterns to match the inputs.
147 */
148 private final MatchPattern[] patterns;
149
150 /**
151 * The inputs to match the patterns against.
152 */
153 private final Position[] inputs;
154
155 /**
156 * Can there only be one user of the node. Constant nodes can be matched even if there are other
157 * users.
158 */
159 private final boolean singleUser;
160
161 /**
162 * Can this node be subsumed into a match even if there are side effecting nodes between this
163 * node and the match.
164 */
165 private final boolean ignoresSideEffects;
166
167 private static final MatchPattern[] EMPTY_PATTERNS = new MatchPattern[0];
168
169 public MatchPattern(String name, boolean singleUser, boolean ignoresSideEffects) {
170 this(null, name, singleUser, ignoresSideEffects);
171 }
172
173 public MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser, boolean ignoresSideEffects) {
174 this.nodeClass = nodeClass;
175 this.name = name;
176 this.singleUser = singleUser;
177 this.ignoresSideEffects = ignoresSideEffects;
178 this.patterns = EMPTY_PATTERNS;
179 this.inputs = null;
180 assert !ignoresSideEffects || FloatingNode.class.isAssignableFrom(nodeClass);
181 }
182
183 private MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser, boolean ignoresSideEffects, MatchPattern[] patterns, Position[] inputs) {
184 assert inputs == null || inputs.length == patterns.length;
185 this.nodeClass = nodeClass;
186 this.name = name;
187 this.singleUser = singleUser;
188 this.ignoresSideEffects = ignoresSideEffects;
189 this.patterns = patterns;
190 this.inputs = inputs;
191 assert !ignoresSideEffects || FloatingNode.class.isAssignableFrom(nodeClass);
192 }
193
194 public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, Position[] inputs, boolean singleUser, boolean ignoresSideEffects) {
195 this(nodeClass, name, singleUser, ignoresSideEffects, new MatchPattern[]{first}, inputs);
196 }
197
198 public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, Position[] inputs, boolean singleUser, boolean ignoresSideEffects) {
199 this(nodeClass, name, singleUser, ignoresSideEffects, new MatchPattern[]{first, second}, inputs);
200 }
201
202 public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, MatchPattern third, Position[] inputs, boolean singleUser, boolean ignoresSideEffects) {
203 this(nodeClass, name, singleUser, ignoresSideEffects, new MatchPattern[]{first, second, third}, inputs);
204 }
205
206 Class<? extends Node> nodeClass() {
207 return nodeClass;
208 }
209
210 private Result matchType(Node node) {
211 if (nodeClass != null && node.getClass() != nodeClass) {
212 return Result.wrongClass(node, this);
213 }
214 return Result.OK;
215 }
216
217 /**
218 * Match any named nodes and ensure that the consumed nodes can be safely merged.
219 *
220 * @param node
221 * @param context
222 * @return Result.OK is the pattern can be safely matched.
223 */
224 Result matchUsage(Node node, MatchContext context) {
225 Result result = matchUsage(node, context, true);
226 if (result == Result.OK) {
227 result = context.validate();
228 }
229 return result;
230 }
231
232 private Result matchUsage(Node node, MatchContext context, boolean atRoot) {
233 Result result = matchType(node);
234 if (result != Result.OK) {
235 return result;
236 }
237 if (singleUser) {
238 result = context.consume(node, ignoresSideEffects, atRoot);
239 if (result != Result.OK) {
240 return result;
241 }
242 }
243
244 if (name != null) {
245 result = context.captureNamedValue(name, nodeClass, node);
246 }
247
248 for (int input = 0; input < patterns.length; input++) {
249 result = patterns[input].matchUsage(getInput(input, node), context, false);
250 if (result != Result.OK) {
251 return result;
252 }
253 }
254
255 return result;
256 }
257
258 /**
|