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 }