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