1 /* 2 * Copyright (c) 2014, 2015, 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 static org.graalvm.compiler.debug.GraalDebugConfig.Options.LogVerbose; 26 27 import java.util.ArrayList; 28 import java.util.Arrays; 29 import java.util.HashMap; 30 import java.util.List; 31 import java.util.Map; 32 33 import org.graalvm.compiler.core.gen.NodeLIRBuilder; 34 import org.graalvm.compiler.core.match.MatchPattern.Result; 35 import org.graalvm.compiler.debug.Debug; 36 import org.graalvm.compiler.debug.GraalError; 37 import org.graalvm.compiler.graph.Node; 38 import org.graalvm.compiler.nodes.calc.FloatingNode; 39 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode; 40 41 /** 42 * Container for state captured during a match. 43 */ 44 public class MatchContext { 45 46 private final Node root; 47 48 private final List<Node> nodes; 49 50 private final MatchStatement rule; 51 52 private Map<String, NamedNode> namedNodes; 53 54 private ArrayList<Node> consumed; 55 56 private int startIndex; 57 58 private int endIndex; 59 60 private final NodeLIRBuilder builder; 61 62 private static class NamedNode { 63 final Class<? extends Node> type; 64 final Node value; 65 66 NamedNode(Class<? extends Node> type, Node value) { 67 this.type = type; 68 this.value = value; 69 } 70 } 71 72 public MatchContext(NodeLIRBuilder builder, MatchStatement rule, int index, Node node, List<Node> nodes) { 73 this.builder = builder; 74 this.rule = rule; 75 this.root = node; 76 this.nodes = nodes; 77 assert index == nodes.indexOf(node); 78 // The root should be the last index since all the inputs must be scheduled before it. 79 startIndex = endIndex = index; 80 } 81 82 public Node getRoot() { 83 return root; 84 } 85 86 public Result captureNamedValue(String name, Class<? extends Node> type, Node value) { 87 if (namedNodes == null) { 88 namedNodes = new HashMap<>(2); 89 } 90 NamedNode current = namedNodes.get(name); 91 if (current == null) { 92 current = new NamedNode(type, value); 93 namedNodes.put(name, current); 94 return Result.OK; 95 } else { 96 if (current.value != value || current.type != type) { 97 return Result.namedValueMismatch(value, rule.getPattern()); 98 } 99 return Result.OK; 100 } 101 } 102 103 public Result validate() { 104 // Ensure that there's no unsafe work in between these operations. 105 for (int i = startIndex; i <= endIndex; i++) { 106 Node node = nodes.get(i); 107 if (node instanceof VirtualObjectNode || node instanceof FloatingNode) { 108 // The order of evaluation of these nodes controlled by data dependence so they 109 // don't interfere with this match. 110 continue; 111 } else if ((consumed == null || !consumed.contains(node)) && node != root) { 112 if (LogVerbose.getValue()) { 113 Debug.log("unexpected node %s", node); 114 for (int j = startIndex; j <= endIndex; j++) { 115 Node theNode = nodes.get(j); 116 Debug.log("%s(%s) %1s", (consumed != null && consumed.contains(theNode) || theNode == root) ? "*" : " ", theNode.getUsageCount(), theNode); 117 } 118 } 119 return Result.notSafe(node, rule.getPattern()); 120 } 121 } 122 return Result.OK; 123 } 124 125 /** 126 * Mark the interior nodes with INTERIOR_MATCH and set the Value of the root to be the result. 127 * During final LIR generation it will be evaluated to produce the actual LIR value. 128 * 129 * @param result 130 */ 131 public void setResult(ComplexMatchResult result) { 132 ComplexMatchValue value = new ComplexMatchValue(result); 133 if (Debug.isLogEnabled()) { 134 Debug.log("matched %s %s", rule.getName(), rule.getPattern()); 135 Debug.log("with nodes %s", rule.formatMatch(root)); 136 } 137 if (consumed != null) { 138 for (Node node : consumed) { 139 // All the interior nodes should be skipped during the normal doRoot calls in 140 // NodeLIRBuilder so mark them as interior matches. The root of the match will get a 141 // closure which will be evaluated to produce the final LIR. 142 builder.setMatchResult(node, ComplexMatchValue.INTERIOR_MATCH); 143 } 144 } 145 builder.setMatchResult(root, value); 146 } 147 148 /** 149 * Mark a node as consumed by the match. Consumed nodes will never be evaluated. 150 * 151 * @return Result.OK if the node can be safely consumed. 152 */ 153 public Result consume(Node node) { 154 assert node.getUsageCount() <= 1 : "should have already been checked"; 155 156 // Check NOT_IN_BLOCK first since that usually implies ALREADY_USED 157 int index = nodes.indexOf(node); 158 if (index == -1) { 159 return Result.notInBlock(node, rule.getPattern()); 160 } 161 162 if (builder.hasOperand(node)) { 163 return Result.alreadyUsed(node, rule.getPattern()); 164 } 165 166 startIndex = Math.min(startIndex, index); 167 if (consumed == null) { 168 consumed = new ArrayList<>(2); 169 } 170 consumed.add(node); 171 return Result.OK; 172 } 173 174 /** 175 * Return the named node. It's an error if the 176 * 177 * @param name the name of a node in the match rule 178 * @return the matched node 179 * @throws GraalError is the named node doesn't exist. 180 */ 181 public Node namedNode(String name) { 182 if (namedNodes != null) { 183 NamedNode value = namedNodes.get(name); 184 if (value != null) { 185 return value.value; 186 } 187 } 188 throw new GraalError("missing node %s", name); 189 } 190 191 @Override 192 public String toString() { 193 return String.format("%s %s (%d, %d) consumed %s", rule, root, startIndex, endIndex, consumed != null ? Arrays.toString(consumed.toArray()) : ""); 194 } 195 }