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.DebugOptions.LogVerbose;
26
27 import java.util.ArrayList;
28 import java.util.Arrays;
29 import java.util.List;
30
31 import org.graalvm.compiler.core.gen.NodeLIRBuilder;
32 import org.graalvm.compiler.core.match.MatchPattern.Result;
33 import org.graalvm.compiler.debug.DebugContext;
34 import org.graalvm.compiler.debug.GraalError;
35 import org.graalvm.compiler.graph.Node;
36 import org.graalvm.compiler.nodes.calc.FloatingNode;
37 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
38 import org.graalvm.util.EconomicMap;
39 import org.graalvm.util.Equivalence;
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 EconomicMap<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 = EconomicMap.create(Equivalence.DEFAULT);
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(root.getOptions())) {
113 DebugContext debug = root.getDebug();
114 debug.log("unexpected node %s", node);
115 for (int j = startIndex; j <= endIndex; j++) {
116 Node theNode = nodes.get(j);
117 debug.log("%s(%s) %1s", (consumed != null && consumed.contains(theNode) || theNode == root) ? "*" : " ", theNode.getUsageCount(), theNode);
118 }
119 }
120 return Result.notSafe(node, rule.getPattern());
121 }
122 }
123 return Result.OK;
124 }
125
126 /**
127 * Mark the interior nodes with INTERIOR_MATCH and set the Value of the root to be the result.
128 * During final LIR generation it will be evaluated to produce the actual LIR value.
129 *
130 * @param result
131 */
132 public void setResult(ComplexMatchResult result) {
133 ComplexMatchValue value = new ComplexMatchValue(result);
134 DebugContext debug = root.getDebug();
135 if (debug.isLogEnabled()) {
136 debug.log("matched %s %s", rule.getName(), rule.getPattern());
137 debug.log("with nodes %s", rule.formatMatch(root));
138 }
139 if (consumed != null) {
140 for (Node node : consumed) {
141 // All the interior nodes should be skipped during the normal doRoot calls in
142 // NodeLIRBuilder so mark them as interior matches. The root of the match will get a
143 // closure which will be evaluated to produce the final LIR.
144 builder.setMatchResult(node, ComplexMatchValue.INTERIOR_MATCH);
145 }
146 }
147 builder.setMatchResult(root, value);
148 }
149
150 /**
151 * Mark a node as consumed by the match. Consumed nodes will never be evaluated.
152 *
153 * @return Result.OK if the node can be safely consumed.
154 */
155 public Result consume(Node node) {
156 assert MatchPattern.isSingleValueUser(node) : "should have already been checked";
157
158 // Check NOT_IN_BLOCK first since that usually implies ALREADY_USED
159 int index = nodes.indexOf(node);
160 if (index == -1) {
161 return Result.notInBlock(node, rule.getPattern());
162 }
163
164 if (builder.hasOperand(node)) {
165 return Result.alreadyUsed(node, rule.getPattern());
166 }
167
168 startIndex = Math.min(startIndex, index);
169 if (consumed == null) {
170 consumed = new ArrayList<>(2);
171 }
172 consumed.add(node);
173 return Result.OK;
174 }
175
176 /**
177 * Return the named node. It's an error if the
178 *
179 * @param name the name of a node in the match rule
180 * @return the matched node
181 * @throws GraalError is the named node doesn't exist.
182 */
183 public Node namedNode(String name) {
184 if (namedNodes != null) {
185 NamedNode value = namedNodes.get(name);
186 if (value != null) {
187 return value.value;
188 }
189 }
190 throw new GraalError("missing node %s", name);
191 }
192
193 @Override
194 public String toString() {
195 return String.format("%s %s (%d, %d) consumed %s", rule, root, startIndex, endIndex, consumed != null ? Arrays.toString(consumed.toArray()) : "");
196 }
197 }