1 /*
2 * Copyright (c) 2014, 2019, 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.core.common.cfg.AbstractControlFlowGraph.dominates;
28 import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.strictlyDominates;
29 import static org.graalvm.compiler.debug.DebugOptions.LogVerbose;
30
31 import java.util.ArrayList;
32 import java.util.Arrays;
33 import java.util.Iterator;
34 import java.util.List;
35
36 import jdk.internal.vm.compiler.collections.EconomicMap;
37 import jdk.internal.vm.compiler.collections.Equivalence;
38 import org.graalvm.compiler.core.common.cfg.BlockMap;
39 import org.graalvm.compiler.core.gen.NodeLIRBuilder;
40 import org.graalvm.compiler.core.match.MatchPattern.Result;
41 import org.graalvm.compiler.debug.CounterKey;
42 import org.graalvm.compiler.debug.DebugContext;
43 import org.graalvm.compiler.debug.GraalError;
44 import org.graalvm.compiler.graph.Node;
45 import org.graalvm.compiler.graph.NodeMap;
46 import org.graalvm.compiler.nodes.PhiNode;
47 import org.graalvm.compiler.nodes.StructuredGraph;
48 import org.graalvm.compiler.nodes.calc.FloatingNode;
49 import org.graalvm.compiler.nodes.cfg.Block;
50 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
51
52 /**
53 * Container for state captured during a match.
54 */
55 public class MatchContext {
56 private static final CounterKey MatchContextSuccessDifferentBlocks = DebugContext.counter("MatchContextSuccessDifferentBlocks");
57
58 private final Node root;
59
60 private final MatchStatement rule;
61 private final StructuredGraph.ScheduleResult schedule;
62
63 private EconomicMap<String, NamedNode> namedNodes;
64
65 /**
66 * A node consumed by a match. Keeps track of whether side effects can be ignored.
67 */
68 static final class ConsumedNode {
69 final Node node;
70 final boolean ignoresSideEffects;
71
72 ConsumedNode(Node node, boolean ignoresSideEffects) {
73 this.node = node;
74 this.ignoresSideEffects = ignoresSideEffects;
75 }
76 }
77
78 /**
79 * The collection of nodes consumed by this match.
80 */
81 static final class ConsumedNodes implements Iterable<ConsumedNode> {
82 private ArrayList<ConsumedNode> nodes;
83
84 ConsumedNodes() {
85 this.nodes = null;
86 }
87
88 public void add(Node node, boolean ignoresSideEffects) {
89 if (nodes == null) {
90 nodes = new ArrayList<>(2);
91 }
92 nodes.add(new ConsumedNode(node, ignoresSideEffects));
93 }
94
95 public boolean contains(Node node) {
96 for (ConsumedNode c : nodes) {
97 if (c.node == node) {
98 return true;
99 }
100 }
101 return false;
102 }
103
104 public ConsumedNode find(Node node) {
105 for (ConsumedNode c : nodes) {
106 if (c.node == node) {
107 return c;
108 }
109 }
110 return null;
111 }
112
113 @Override
114 public String toString() {
115 Node[] arr = new Node[nodes.size()];
116 int i = 0;
117 for (ConsumedNode c : nodes) {
118 arr[i++] = c.node;
119 }
120 return Arrays.toString(arr);
121 }
122
123 @Override
124 public Iterator<ConsumedNode> iterator() {
125 return nodes.iterator();
126 }
127 }
128
129 private ConsumedNodes consumed = new ConsumedNodes();
130
131 private Block rootBlock;
132 private int rootIndex;
133
134 /**
135 * Block and index in the block at which the match should be emitted. Differs from
136 * rootBlock/rootIndex for (ZeroExtend Read=access) for instance: match should be emitted where
137 * the Read is.
138 */
139 private int emitIndex;
140 private Block emitBlock;
141
142 private final NodeLIRBuilder builder;
143
144 private static class NamedNode {
145 final Class<? extends Node> type;
146 final Node value;
147
148 NamedNode(Class<? extends Node> type, Node value) {
149 this.type = type;
150 this.value = value;
151 }
152 }
153
154 public MatchContext(NodeLIRBuilder builder, MatchStatement rule, int index, Node node, Block rootBlock, StructuredGraph.ScheduleResult schedule) {
155 this.builder = builder;
156 this.rule = rule;
157 this.root = node;
158 assert index == schedule.getBlockToNodesMap().get(rootBlock).indexOf(node);
159 this.schedule = schedule;
160 // The root should be the last index since all the inputs must be scheduled before it.
161 this.rootBlock = rootBlock;
162 rootIndex = index;
163 }
164
165 public Node getRoot() {
166 return root;
167 }
168
169 public Result captureNamedValue(String name, Class<? extends Node> type, Node value) {
170 if (namedNodes == null) {
171 namedNodes = EconomicMap.create(Equivalence.DEFAULT);
172 }
173 NamedNode current = namedNodes.get(name);
174 if (current == null) {
175 current = new NamedNode(type, value);
176 namedNodes.put(name, current);
177 return Result.OK;
178 } else {
179 if (current.value != value || current.type != type) {
180 return Result.namedValueMismatch(value, rule.getPattern());
181 }
182 return Result.OK;
183 }
184 }
185
186 public Result validate() {
187 Result result = findEarlyPosition();
188 if (result != Result.OK) {
189 return result;
190 }
191 findLatePosition();
192 assert emitIndex == rootIndex || consumed.find(root).ignoresSideEffects;
193 return verifyInputs();
194 }
195
196 private Result findEarlyPosition() {
197 int startIndexSideEffect = -1;
198 int endIndexSideEffect = -1;
199 final NodeMap<Block> nodeToBlockMap = schedule.getNodeToBlockMap();
200 final BlockMap<List<Node>> blockToNodesMap = schedule.getBlockToNodesMap();
201
202 // Nodes affected by side effects must be in the same block
203 for (ConsumedNode cn : consumed) {
204 if (!cn.ignoresSideEffects) {
205 Block b = nodeToBlockMap.get(cn.node);
206 if (emitBlock == null) {
207 emitBlock = b;
208 startIndexSideEffect = endIndexSideEffect = blockToNodesMap.get(b).indexOf(cn.node);
209 } else if (emitBlock == b) {
210 int index = blockToNodesMap.get(b).indexOf(cn.node);
211 startIndexSideEffect = Math.min(startIndexSideEffect, index);
212 endIndexSideEffect = Math.max(endIndexSideEffect, index);
213 } else {
214 logFailedMatch("nodes affected by side effects in different blocks %s", cn.node);
215 return Result.notInBlock(cn.node, rule.getPattern());
216 }
217 }
218 }
219 if (emitBlock != null) {
220 // There must be no side effects between nodes that are affected by side effects
221 assert startIndexSideEffect != -1 && endIndexSideEffect != -1;
222 final List<Node> nodes = blockToNodesMap.get(emitBlock);
223 for (int i = startIndexSideEffect; i <= endIndexSideEffect; i++) {
224 Node node = nodes.get(i);
225 if (!sideEffectFree(node) && !consumed.contains(node)) {
226 logFailedMatch("unexpected side effect %s", node);
227 return Result.notSafe(node, rule.getPattern());
228 }
229 }
230 // early position is at the node affected by side effects the closest to the root
231 emitIndex = endIndexSideEffect;
232 } else {
233 // Nodes not affected by side effect: early position is at the root
234 emitBlock = nodeToBlockMap.get(root);
235 emitIndex = rootIndex;
236 }
237 return Result.OK;
238 }
239
240 private static boolean sideEffectFree(Node node) {
241 // The order of evaluation of these nodes controlled by data dependence so they
242 // don't interfere with this match.
243 return node instanceof VirtualObjectNode || node instanceof FloatingNode;
244 }
245
246 private void findLatePosition() {
247 // If emit position is at a node affected by side effects that's followed by side effect
248 // free nodes, the node can be emitted later. This helps when the match has inputs that are
249 // late in the block.
250 int index = rootIndex;
251 if (emitBlock != rootBlock) {
252 index = schedule.getBlockToNodesMap().get(emitBlock).size() - 1;
253 }
254 final List<Node> emitBlockNodes = schedule.getBlockToNodesMap().get(emitBlock);
255 for (int i = emitIndex + 1; i <= index; i++) {
256 Node node = emitBlockNodes.get(i);
257 ConsumedNode cn = consumed.find(node);
258 if (cn == null) {
259 if (!sideEffectFree(node)) {
260 return;
261 }
262 } else {
263 assert cn.ignoresSideEffects;
264 emitIndex = i;
265 }
266 }
267 }
268
269 private Result verifyInputs() {
270 DebugContext debug = root.getDebug();
271 if (emitBlock != rootBlock) {
272 assert consumed.find(root).ignoresSideEffects;
273 Result result = verifyInputsDifferentBlock(root);
274 if (result == Result.OK) {
275 MatchContextSuccessDifferentBlocks.increment(debug);
276 }
277 return result;
278 }
279 // We are going to emit the match at emitIndex. We need to make sure nodes of the match
280 // between emitIndex and rootIndex don't have inputs after position emitIndex that would
281 // make emitIndex an illegal position.
282 final List<Node> nodes = schedule.getBlockToNodesMap().get(rootBlock);
283 for (int i = emitIndex + 1; i <= rootIndex; i++) {
284 Node node = nodes.get(i);
285 ConsumedNode cn = consumed.find(node);
286 if (cn != null) {
287 assert cn.ignoresSideEffects;
288 for (Node in : node.inputs()) {
289 if (!consumed.contains(in)) {
290 for (int j = emitIndex + 1; j < i; j++) {
291 if (nodes.get(j) == in) {
292 logFailedMatch("Earliest position in block is too late %s", in);
293 assert consumed.find(root).ignoresSideEffects;
294 assert verifyInputsDifferentBlock(root) != Result.OK;
295 return Result.tooLate(node, rule.getPattern());
296 }
297 }
298 }
299 }
300 }
301 }
302 assert verifyInputsDifferentBlock(root) == Result.OK;
303 return Result.OK;
304 }
305
306 private Result verifyInputsDifferentBlock(Node node) {
307 // Is there an input that's not part of the match that's after the emit position?
308 for (Node in : node.inputs()) {
309 if (in instanceof PhiNode) {
310 Block b = schedule.getNodeToBlockMap().get(((PhiNode) in).merge());
311 if (dominates(b, emitBlock)) {
312 continue;
313 }
314 } else {
315 Block b = schedule.getNodeToBlockMap().get(in);
316 if (strictlyDominates(b, emitBlock) || (b == emitBlock && schedule.getBlockToNodesMap().get(emitBlock).indexOf(in) <= emitIndex)) {
317 continue;
318 }
319 }
320 ConsumedNode cn = consumed.find(in);
321 if (cn == null) {
322 logFailedMatch("Earliest position in block is too late %s", in);
323 return Result.tooLate(node, rule.getPattern());
324 }
325 assert cn.ignoresSideEffects;
326 Result res = verifyInputsDifferentBlock(in);
327 if (res != Result.OK) {
328 return res;
329 }
330 }
331 return Result.OK;
332 }
333
334 private void logFailedMatch(String s, Node node) {
335 if (LogVerbose.getValue(root.getOptions())) {
336 DebugContext debug = root.getDebug();
337 debug.log(s, node);
338 int startIndex = emitIndex;
339 if (emitBlock != rootBlock) {
340 int endIndex = schedule.getBlockToNodesMap().get(emitBlock).size() - 1;
341 final List<Node> emitBlockNodes = schedule.getBlockToNodesMap().get(emitBlock);
342 debug.log("%s:", emitBlock);
343 for (int j = startIndex; j <= endIndex; j++) {
344 Node theNode = emitBlockNodes.get(j);
345 debug.log("%s(%s) %1s", consumed.contains(theNode) ? "*" : " ", theNode.getUsageCount(), theNode);
346 }
347 startIndex = 0;
348 }
349 debug.log("%s:", rootBlock);
350 final List<Node> nodes = schedule.getBlockToNodesMap().get(rootBlock);
351 for (int j = startIndex; j <= rootIndex; j++) {
352 Node theNode = nodes.get(j);
353 debug.log("%s(%s) %1s", consumed.contains(theNode) ? "*" : " ", theNode.getUsageCount(), theNode);
354 }
355 }
356 }
357
358 /**
359 * Mark the interior nodes with INTERIOR_MATCH and set the Value of the root to be the result.
360 * During final LIR generation it will be evaluated to produce the actual LIR value.
361 *
362 * @param result
363 */
364 public void setResult(ComplexMatchResult result) {
365 ComplexMatchValue value = new ComplexMatchValue(result);
366 Node emitNode = schedule.getBlockToNodesMap().get(emitBlock).get(emitIndex);
367 DebugContext debug = root.getDebug();
368 if (debug.isLogEnabled()) {
369 debug.log("matched %s %s%s", rule.getName(), rule.getPattern(), emitIndex != rootIndex ? " skipping side effects" : "");
370 debug.log("with nodes %s", rule.formatMatch(root));
371 }
372 for (ConsumedNode cn : consumed) {
373 if (cn.node == root || cn.node == emitNode) {
374 continue;
375 }
376 // All the interior nodes should be skipped during the normal doRoot calls in
377 // NodeLIRBuilder so mark them as interior matches. The root of the match will get a
378 // closure which will be evaluated to produce the final LIR.
379 builder.setMatchResult(cn.node, ComplexMatchValue.INTERIOR_MATCH);
380 }
381 builder.setMatchResult(emitNode, value);
382 if (root != emitNode) {
383 // Match is not emitted at the position of root in the block but the uses of root needs
384 // the result of the match so add a ComplexMatchValue that will simply return the result
385 // of the actual match above.
386 builder.setMatchResult(root, new ComplexMatchValue(gen -> gen.operand(emitNode)));
387 }
388 }
389
390 /**
391 * Mark a node as consumed by the match. Consumed nodes will never be evaluated.
392 *
393 * @return Result.OK if the node can be safely consumed.
394 */
395 public Result consume(Node node, boolean ignoresSideEffects, boolean atRoot) {
396 if (atRoot) {
397 consumed.add(node, ignoresSideEffects);
398 return Result.OK;
399 }
400 assert MatchPattern.isSingleValueUser(node) : "should have already been checked";
401
402 if (builder.hasOperand(node)) {
403 return Result.alreadyUsed(node, rule.getPattern());
404 }
405
406 consumed.add(node, ignoresSideEffects);
407 return Result.OK;
408 }
409
410 /**
411 * Return the named node. It's an error if the
412 *
413 * @param name the name of a node in the match rule
414 * @return the matched node
415 * @throws GraalError is the named node doesn't exist.
416 */
417 public Node namedNode(String name) {
418 if (namedNodes != null) {
419 NamedNode value = namedNodes.get(name);
420 if (value != null) {
421 return value.value;
422 }
423 }
424 throw new GraalError("missing node %s", name);
425 }
426
427 @Override
428 public String toString() {
429 return String.format("%s %s (%s/%d, %s/%d) consumed %s", rule, root, rootBlock, rootIndex, emitBlock, emitIndex, consumed);
430 }
431 }