1 /*
2 * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
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 package org.graalvm.compiler.core.match;
24
25 import org.graalvm.compiler.debug.Debug;
26 import org.graalvm.compiler.debug.DebugCounter;
27 import org.graalvm.compiler.graph.Node;
28 import org.graalvm.compiler.graph.Position;
29 import org.graalvm.compiler.nodeinfo.Verbosity;
30
31 /**
32 * A simple recursive pattern matcher for a DAG of nodes.
33 */
34
35 public class MatchPattern {
36
37 enum MatchResultCode {
38 OK,
39 WRONG_CLASS,
40 NAMED_VALUE_MISMATCH,
41 TOO_MANY_USERS,
42 NOT_IN_BLOCK,
43 NOT_SAFE,
44 ALREADY_USED,
45 }
46
47 /**
48 * A descriptive result for match failures. This can be helpful for debugging why a match
49 * doesn't work as expected.
50 */
51 static class Result {
52 final MatchResultCode code;
53
54 final Node node;
55
56 final MatchPattern matcher;
57
58 Result(MatchResultCode result, Node node, MatchPattern matcher) {
59 this.code = result;
60 this.node = node;
61 this.matcher = matcher;
62 }
63
64 private static final DebugCounter MatchResult_WRONG_CLASS = Debug.counter("MatchResult_WRONG_CLASS");
65 private static final DebugCounter MatchResult_NAMED_VALUE_MISMATCH = Debug.counter("MatchResult_NAMED_VALUE_MISMATCH");
66 private static final DebugCounter MatchResult_TOO_MANY_USERS = Debug.counter("MatchResult_TOO_MANY_USERS");
67 private static final DebugCounter MatchResult_NOT_IN_BLOCK = Debug.counter("MatchResult_NOT_IN_BLOCK");
68 private static final DebugCounter MatchResult_NOT_SAFE = Debug.counter("MatchResult_NOT_SAFE");
69 private static final DebugCounter MatchResult_ALREADY_USED = Debug.counter("MatchResult_ALREADY_USED");
70
71 static final Result OK = new Result(MatchResultCode.OK, null, null);
72 private static final Result CACHED_WRONG_CLASS = new Result(MatchResultCode.WRONG_CLASS, null, null);
73 private static final Result CACHED_NAMED_VALUE_MISMATCH = new Result(MatchResultCode.NAMED_VALUE_MISMATCH, null, null);
74 private static final Result CACHED_TOO_MANY_USERS = new Result(MatchResultCode.TOO_MANY_USERS, null, null);
75 private static final Result CACHED_NOT_IN_BLOCK = new Result(MatchResultCode.NOT_IN_BLOCK, null, null);
76 private static final Result CACHED_NOT_SAFE = new Result(MatchResultCode.NOT_SAFE, null, null);
77 private static final Result CACHED_ALREADY_USED = new Result(MatchResultCode.ALREADY_USED, null, null);
78
79 static Result wrongClass(Node node, MatchPattern matcher) {
80 MatchResult_WRONG_CLASS.increment();
81 return Debug.isLogEnabled() ? new Result(MatchResultCode.WRONG_CLASS, node, matcher) : CACHED_WRONG_CLASS;
82 }
83
84 static Result namedValueMismatch(Node node, MatchPattern matcher) {
85 MatchResult_NAMED_VALUE_MISMATCH.increment();
86 return Debug.isLogEnabled() ? new Result(MatchResultCode.NAMED_VALUE_MISMATCH, node, matcher) : CACHED_NAMED_VALUE_MISMATCH;
87 }
88
89 static Result tooManyUsers(Node node, MatchPattern matcher) {
90 MatchResult_TOO_MANY_USERS.increment();
91 return Debug.isLogEnabled() ? new Result(MatchResultCode.TOO_MANY_USERS, node, matcher) : CACHED_TOO_MANY_USERS;
92 }
93
94 static Result notInBlock(Node node, MatchPattern matcher) {
95 MatchResult_NOT_IN_BLOCK.increment();
96 return Debug.isLogEnabled() ? new Result(MatchResultCode.NOT_IN_BLOCK, node, matcher) : CACHED_NOT_IN_BLOCK;
97 }
98
99 static Result notSafe(Node node, MatchPattern matcher) {
100 MatchResult_NOT_SAFE.increment();
101 return Debug.isLogEnabled() ? new Result(MatchResultCode.NOT_SAFE, node, matcher) : CACHED_NOT_SAFE;
102 }
103
104 static Result alreadyUsed(Node node, MatchPattern matcher) {
105 MatchResult_ALREADY_USED.increment();
106 return Debug.isLogEnabled() ? new Result(MatchResultCode.ALREADY_USED, node, matcher) : CACHED_ALREADY_USED;
107 }
108
109 @Override
110 public String toString() {
111 if (code == MatchResultCode.OK) {
112 return "OK";
113 }
114 if (node == null) {
115 return code.toString();
116 } else {
117 return code + " " + node.toString(Verbosity.Id) + "|" + node.getClass().getSimpleName() + " " + matcher;
118 }
119 }
120 }
121
122 /**
123 * The expected type of the node. It must match exactly.
124 */
125 private final Class<? extends Node> nodeClass;
126
127 /**
128 * An optional name for this node. A name can occur multiple times in a match and that name must
129 * always refer to the same node of the match will fail.
130 */
131 private final String name;
132
133 /**
134 * Patterns to match the inputs.
135 */
136 private final MatchPattern[] patterns;
137
138 /**
139 * The inputs to match the patterns against.
140 */
141 private final Position[] inputs;
142
143 /**
144 * Can there only be one user of the node. Constant nodes can be matched even if there are other
145 * users.
146 */
147 private final boolean singleUser;
148
149 private static final MatchPattern[] EMPTY_PATTERNS = new MatchPattern[0];
150
151 public MatchPattern(String name, boolean singleUser) {
152 this(null, name, singleUser);
153 }
154
155 public MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser) {
156 this.nodeClass = nodeClass;
157 this.name = name;
158 this.singleUser = singleUser;
159 this.patterns = EMPTY_PATTERNS;
160 this.inputs = null;
161 }
162
163 private MatchPattern(Class<? extends Node> nodeClass, String name, boolean singleUser, MatchPattern[] patterns, Position[] inputs) {
164 assert inputs == null || inputs.length == patterns.length;
165 this.nodeClass = nodeClass;
166 this.name = name;
167 this.singleUser = singleUser;
168 this.patterns = patterns;
169 this.inputs = inputs;
170 }
171
172 public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, Position[] inputs, boolean singleUser) {
173 this(nodeClass, name, singleUser, new MatchPattern[]{first}, inputs);
174 }
175
176 public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, Position[] inputs, boolean singleUser) {
177 this(nodeClass, name, singleUser, new MatchPattern[]{first, second}, inputs);
178 }
179
180 public MatchPattern(Class<? extends Node> nodeClass, String name, MatchPattern first, MatchPattern second, MatchPattern third, Position[] inputs, boolean singleUser) {
181 this(nodeClass, name, singleUser, new MatchPattern[]{first, second, third}, inputs);
182 }
183
184 Class<? extends Node> nodeClass() {
185 return nodeClass;
186 }
187
188 private Result matchType(Node node) {
189 if (nodeClass != null && node.getClass() != nodeClass) {
190 return Result.wrongClass(node, this);
191 }
192 return Result.OK;
193 }
194
195 /**
196 * Match any named nodes and ensure that the consumed nodes can be safely merged.
197 *
198 * @param node
199 * @param context
200 * @return Result.OK is the pattern can be safely matched.
201 */
202 Result matchUsage(Node node, MatchContext context) {
203 Result result = matchUsage(node, context, true);
204 if (result == Result.OK) {
205 result = context.validate();
206 }
207 return result;
208 }
209
210 private Result matchUsage(Node node, MatchContext context, boolean atRoot) {
211 Result result = matchType(node);
212 if (result != Result.OK) {
213 return result;
214 }
215 if (singleUser && !atRoot) {
216 result = context.consume(node);
217 if (result != Result.OK) {
218 return result;
219 }
220 }
221
222 if (name != null) {
223 result = context.captureNamedValue(name, nodeClass, node);
224 }
225
226 for (int input = 0; input < patterns.length; input++) {
227 result = patterns[input].matchUsage(getInput(input, node), context, false);
228 if (result != Result.OK) {
229 return result;
230 }
231 }
232
233 return result;
234 }
235
236 /**
237 * Recursively match the shape of the tree without worry about named values. Most matches fail
238 * at this point so it's performed first.
239 *
240 * @param node
241 * @param statement
242 * @return Result.OK if the shape of the pattern matches.
243 */
244 public Result matchShape(Node node, MatchStatement statement) {
245 return matchShape(node, statement, true);
246 }
247
248 private Result matchShape(Node node, MatchStatement statement, boolean atRoot) {
249 Result result = matchType(node);
250 if (result != Result.OK) {
251 return result;
252 }
253
254 if (singleUser && !atRoot) {
255 if (node.getUsageCount() > 1) {
256 return Result.tooManyUsers(node, statement.getPattern());
257 }
258 }
259
260 for (int input = 0; input < patterns.length; input++) {
261 result = patterns[input].matchShape(getInput(input, node), statement, false);
262 if (result != Result.OK) {
263 return result;
264 }
265 }
266
267 return result;
268 }
269
270 /**
271 * For a node starting at root, produce a String showing the inputs that matched against this
272 * rule. It's assumed that a match has already succeeded against this rule, otherwise the
273 * printing may produce exceptions.
274 */
275 public String formatMatch(Node root) {
276 String result = String.format("%s", root);
277 if (patterns.length == 0) {
278 return result;
279 } else {
280 StringBuilder sb = new StringBuilder();
281 sb.append("(");
282 sb.append(result);
283 for (int input = 0; input < patterns.length; input++) {
284 sb.append(" ");
285 sb.append(patterns[input].formatMatch(getInput(input, root)));
286 }
287 sb.append(")");
288 return sb.toString();
289 }
290 }
291
292 private Node getInput(int index, Node node) {
293 return inputs[index].get(node);
294 }
295
296 @Override
297 public String toString() {
298 if (nodeClass == null) {
299 return name;
300 } else {
301 String nodeName = nodeClass.getSimpleName();
302 if (nodeName.endsWith("Node")) {
303 nodeName = nodeName.substring(0, nodeName.length() - 4);
304 }
305 if (patterns.length == 0) {
306 return nodeName + (name != null ? "=" + name : "");
307 } else {
308 StringBuilder sb = new StringBuilder();
309 sb.append("(");
310 sb.append(nodeName);
311 for (int index = 0; index < patterns.length; index++) {
312 sb.append(" ");
313 sb.append(patterns[index].toString());
314 }
315 sb.append(")");
316 return sb.toString();
317 }
318 }
319 }
320 }