1 /*
2 * Copyright (c) 2014, 2018, 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
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 /**
240 * Recursively match the shape of the tree without worry about named values. Most matches fail
241 * at this point so it's performed first.
242 *
243 * @param node
244 * @param statement
245 * @return Result.OK if the shape of the pattern matches.
246 */
247 public Result matchShape(Node node, MatchStatement statement) {
248 return matchShape(node, statement, true);
249 }
250
251 private Result matchShape(Node node, MatchStatement statement, boolean atRoot) {
252 Result result = matchType(node);
253 if (result != Result.OK) {
254 return result;
255 }
256
257 if (singleUser && !atRoot) {
258 if (!isSingleValueUser(node)) {
259 return Result.tooManyUsers(node, statement.getPattern());
260 }
261 }
262
263 for (int input = 0; input < patterns.length; input++) {
264 result = patterns[input].matchShape(getInput(input, node), statement, false);
265 if (result != Result.OK) {
266 return result;
267 }
268 }
269
270 return result;
271 }
272
273 public static boolean isSingleValueUser(Node node) {
274 int valueUsage = node.getUsageCount();
275 if (valueUsage == 1) {
276 return true;
277 }
278 if (node.isAllowedUsageType(InputType.Guard)) {
279 // See if the other usages are non-Value usages.
280 valueUsage = 0;
281 for (Node usage : node.usages()) {
282 for (Position input : usage.inputPositions()) {
283 if (input.getInputType() == InputType.Value && input.get(usage) == node) {
284 valueUsage++;
285 if (valueUsage > 1) {
286 // Too many value users
287 return false;
288 }
289 }
290 }
291 }
292 assert valueUsage == 1;
293 return true;
294 }
295 return false;
296 }
297
298 /**
299 * For a node starting at root, produce a String showing the inputs that matched against this
300 * rule. It's assumed that a match has already succeeded against this rule, otherwise the
301 * printing may produce exceptions.
302 */
303 public String formatMatch(Node root) {
304 String result = String.format("%s", root);
305 if (patterns.length == 0) {
306 return result;
307 } else {
308 StringBuilder sb = new StringBuilder();
309 sb.append("(");
310 sb.append(result);
311 for (int input = 0; input < patterns.length; input++) {
312 sb.append(" ");
313 sb.append(patterns[input].formatMatch(getInput(input, root)));
314 }
315 sb.append(")");
316 return sb.toString();
317 }
318 }
319
320 private Node getInput(int index, Node node) {
321 return inputs[index].get(node);
322 }
323
324 @Override
325 public String toString() {
326 if (nodeClass == null) {
327 return name;
328 } else {
329 String nodeName = nodeClass.getSimpleName();
330 if (nodeName.endsWith("Node")) {
331 nodeName = nodeName.substring(0, nodeName.length() - 4);
332 }
333 if (patterns.length == 0) {
334 return nodeName + (name != null ? "=" + name : "");
335 } else {
336 StringBuilder sb = new StringBuilder();
337 sb.append("(");
338 sb.append(nodeName);
339 for (int index = 0; index < patterns.length; index++) {
340 sb.append(" ");
341 sb.append(patterns[index].toString());
342 }
343 sb.append(")");
344 return sb.toString();
345 }
346 }
347 }
348 }