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 }