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