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