< prev index next >
src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.core/src/org/graalvm/compiler/core/match/MatchContext.java
Print this page
*** 22,65 ****
*/
package org.graalvm.compiler.core.match;
import static org.graalvm.compiler.debug.DebugOptions.LogVerbose;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import jdk.internal.vm.compiler.collections.EconomicMap;
import jdk.internal.vm.compiler.collections.Equivalence;
import org.graalvm.compiler.core.gen.NodeLIRBuilder;
import org.graalvm.compiler.core.match.MatchPattern.Result;
import org.graalvm.compiler.debug.DebugContext;
import org.graalvm.compiler.debug.GraalError;
import org.graalvm.compiler.graph.Node;
import org.graalvm.compiler.nodes.calc.FloatingNode;
import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
/**
* Container for state captured during a match.
*/
public class MatchContext {
private final Node root;
- private final List<Node> nodes;
-
private final MatchStatement rule;
private EconomicMap<String, NamedNode> namedNodes;
! private ArrayList<Node> consumed;
! private int startIndex;
! private int endIndex;
private final NodeLIRBuilder builder;
private static class NamedNode {
final Class<? extends Node> type;
--- 22,145 ----
*/
package org.graalvm.compiler.core.match;
+ import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.dominates;
+ import static org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph.strictlyDominates;
import static org.graalvm.compiler.debug.DebugOptions.LogVerbose;
import java.util.ArrayList;
import java.util.Arrays;
+ import java.util.Iterator;
import java.util.List;
import jdk.internal.vm.compiler.collections.EconomicMap;
import jdk.internal.vm.compiler.collections.Equivalence;
+ import org.graalvm.compiler.core.common.cfg.BlockMap;
import org.graalvm.compiler.core.gen.NodeLIRBuilder;
import org.graalvm.compiler.core.match.MatchPattern.Result;
+ import org.graalvm.compiler.debug.CounterKey;
import org.graalvm.compiler.debug.DebugContext;
import org.graalvm.compiler.debug.GraalError;
import org.graalvm.compiler.graph.Node;
+ import org.graalvm.compiler.graph.NodeMap;
+ import org.graalvm.compiler.nodes.PhiNode;
+ import org.graalvm.compiler.nodes.StructuredGraph;
import org.graalvm.compiler.nodes.calc.FloatingNode;
+ import org.graalvm.compiler.nodes.cfg.Block;
import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
/**
* Container for state captured during a match.
*/
public class MatchContext {
+ private static final CounterKey MatchContextSuccessDifferentBlocks = DebugContext.counter("MatchContextSuccessDifferentBlocks");
private final Node root;
private final MatchStatement rule;
+ private final StructuredGraph.ScheduleResult schedule;
private EconomicMap<String, NamedNode> namedNodes;
! /**
! * A node consumed by a match. Keeps track of whether side effects can be ignored.
! */
! static final class ConsumedNode {
! final Node node;
! final boolean ignoresSideEffects;
!
! ConsumedNode(Node node, boolean ignoresSideEffects) {
! this.node = node;
! this.ignoresSideEffects = ignoresSideEffects;
! }
! }
!
! /**
! * The collection of nodes consumed by this match.
! */
! static final class ConsumedNodes implements Iterable<ConsumedNode> {
! private ArrayList<ConsumedNode> nodes;
!
! ConsumedNodes() {
! this.nodes = null;
! }
!
! public void add(Node node, boolean ignoresSideEffects) {
! if (nodes == null) {
! nodes = new ArrayList<>(2);
! }
! nodes.add(new ConsumedNode(node, ignoresSideEffects));
! }
! public boolean contains(Node node) {
! for (ConsumedNode c : nodes) {
! if (c.node == node) {
! return true;
! }
! }
! return false;
! }
! public ConsumedNode find(Node node) {
! for (ConsumedNode c : nodes) {
! if (c.node == node) {
! return c;
! }
! }
! return null;
! }
!
! @Override
! public String toString() {
! Node[] arr = new Node[nodes.size()];
! int i = 0;
! for (ConsumedNode c : nodes) {
! arr[i++] = c.node;
! }
! return Arrays.toString(arr);
! }
!
! @Override
! public Iterator<ConsumedNode> iterator() {
! return nodes.iterator();
! }
! }
!
! private ConsumedNodes consumed = new ConsumedNodes();
!
! private Block rootBlock;
! private int rootIndex;
!
! /**
! * Block and index in the block at which the match should be emitted. Differs from
! * rootBlock/rootIndex for (ZeroExtend Read=access) for instance: match should be emitted where
! * the Read is.
! */
! private int emitIndex;
! private Block emitBlock;
private final NodeLIRBuilder builder;
private static class NamedNode {
final Class<? extends Node> type;
*** 69,86 ****
this.type = type;
this.value = value;
}
}
! public MatchContext(NodeLIRBuilder builder, MatchStatement rule, int index, Node node, List<Node> nodes) {
this.builder = builder;
this.rule = rule;
this.root = node;
! this.nodes = nodes;
! assert index == nodes.indexOf(node);
// The root should be the last index since all the inputs must be scheduled before it.
! startIndex = endIndex = index;
}
public Node getRoot() {
return root;
}
--- 149,167 ----
this.type = type;
this.value = value;
}
}
! public MatchContext(NodeLIRBuilder builder, MatchStatement rule, int index, Node node, Block rootBlock, StructuredGraph.ScheduleResult schedule) {
this.builder = builder;
this.rule = rule;
this.root = node;
! assert index == schedule.getBlockToNodesMap().get(rootBlock).indexOf(node);
! this.schedule = schedule;
// The root should be the last index since all the inputs must be scheduled before it.
! this.rootBlock = rootBlock;
! rootIndex = index;
}
public Node getRoot() {
return root;
}
*** 101,179 ****
return Result.OK;
}
}
public Result validate() {
! // Ensure that there's no unsafe work in between these operations.
! for (int i = startIndex; i <= endIndex; i++) {
Node node = nodes.get(i);
! if (node instanceof VirtualObjectNode || node instanceof FloatingNode) {
! // The order of evaluation of these nodes controlled by data dependence so they
! // don't interfere with this match.
! continue;
! } else if ((consumed == null || !consumed.contains(node)) && node != root) {
! if (LogVerbose.getValue(root.getOptions())) {
! DebugContext debug = root.getDebug();
! debug.log("unexpected node %s", node);
! for (int j = startIndex; j <= endIndex; j++) {
! Node theNode = nodes.get(j);
! debug.log("%s(%s) %1s", (consumed != null && consumed.contains(theNode) || theNode == root) ? "*" : " ", theNode.getUsageCount(), theNode);
}
}
! return Result.notSafe(node, rule.getPattern());
}
}
return Result.OK;
}
/**
* Mark the interior nodes with INTERIOR_MATCH and set the Value of the root to be the result.
* During final LIR generation it will be evaluated to produce the actual LIR value.
*
* @param result
*/
public void setResult(ComplexMatchResult result) {
ComplexMatchValue value = new ComplexMatchValue(result);
DebugContext debug = root.getDebug();
if (debug.isLogEnabled()) {
! debug.log("matched %s %s", rule.getName(), rule.getPattern());
debug.log("with nodes %s", rule.formatMatch(root));
}
! if (consumed != null) {
! for (Node node : consumed) {
! // All the interior nodes should be skipped during the normal doRoot calls in
! // NodeLIRBuilder so mark them as interior matches. The root of the match will get a
! // closure which will be evaluated to produce the final LIR.
! builder.setMatchResult(node, ComplexMatchValue.INTERIOR_MATCH);
}
}
- builder.setMatchResult(root, value);
}
/**
* Mark a node as consumed by the match. Consumed nodes will never be evaluated.
*
* @return Result.OK if the node can be safely consumed.
*/
! public Result consume(Node node) {
! assert MatchPattern.isSingleValueUser(node) : "should have already been checked";
!
! // Check NOT_IN_BLOCK first since that usually implies ALREADY_USED
! int index = nodes.indexOf(node);
! if (index == -1) {
! return Result.notInBlock(node, rule.getPattern());
}
if (builder.hasOperand(node)) {
return Result.alreadyUsed(node, rule.getPattern());
}
! startIndex = Math.min(startIndex, index);
! if (consumed == null) {
! consumed = new ArrayList<>(2);
! }
! consumed.add(node);
return Result.OK;
}
/**
* Return the named node. It's an error if the
--- 182,411 ----
return Result.OK;
}
}
public Result validate() {
! Result result = findEarlyPosition();
! if (result != Result.OK) {
! return result;
! }
! findLatePosition();
! assert emitIndex == rootIndex || consumed.find(root).ignoresSideEffects;
! return verifyInputs();
! }
!
! private Result findEarlyPosition() {
! int startIndexSideEffect = -1;
! int endIndexSideEffect = -1;
! final NodeMap<Block> nodeToBlockMap = schedule.getNodeToBlockMap();
! final BlockMap<List<Node>> blockToNodesMap = schedule.getBlockToNodesMap();
!
! // Nodes affected by side effects must be in the same block
! for (ConsumedNode cn : consumed) {
! if (!cn.ignoresSideEffects) {
! Block b = nodeToBlockMap.get(cn.node);
! if (emitBlock == null) {
! emitBlock = b;
! startIndexSideEffect = endIndexSideEffect = blockToNodesMap.get(b).indexOf(cn.node);
! } else if (emitBlock == b) {
! int index = blockToNodesMap.get(b).indexOf(cn.node);
! startIndexSideEffect = Math.min(startIndexSideEffect, index);
! endIndexSideEffect = Math.max(endIndexSideEffect, index);
! } else {
! logFailedMatch("nodes affected by side effects in different blocks %s", cn.node);
! return Result.notInBlock(cn.node, rule.getPattern());
! }
! }
! }
! if (emitBlock != null) {
! // There must be no side effects between nodes that are affected by side effects
! assert startIndexSideEffect != -1 && endIndexSideEffect != -1;
! final List<Node> nodes = blockToNodesMap.get(emitBlock);
! for (int i = startIndexSideEffect; i <= endIndexSideEffect; i++) {
! Node node = nodes.get(i);
! if (!sideEffectFree(node) && !consumed.contains(node)) {
! logFailedMatch("unexpected side effect %s", node);
! return Result.notSafe(node, rule.getPattern());
! }
! }
! // early position is at the node affected by side effects the closest to the root
! emitIndex = endIndexSideEffect;
! } else {
! // Nodes not affected by side effect: early position is at the root
! emitBlock = nodeToBlockMap.get(root);
! emitIndex = rootIndex;
! }
! return Result.OK;
! }
!
! private static boolean sideEffectFree(Node node) {
! // The order of evaluation of these nodes controlled by data dependence so they
! // don't interfere with this match.
! return node instanceof VirtualObjectNode || node instanceof FloatingNode;
! }
!
! private void findLatePosition() {
! // If emit position is at a node affected by side effects that's followed by side effect
! // free nodes, the node can be emitted later. This helps when the match has inputs that are
! // late in the block.
! int index = rootIndex;
! if (emitBlock != rootBlock) {
! index = schedule.getBlockToNodesMap().get(emitBlock).size() - 1;
! }
! final List<Node> emitBlockNodes = schedule.getBlockToNodesMap().get(emitBlock);
! for (int i = emitIndex + 1; i <= index; i++) {
! Node node = emitBlockNodes.get(i);
! ConsumedNode cn = consumed.find(node);
! if (cn == null) {
! if (!sideEffectFree(node)) {
! return;
! }
! } else {
! assert cn.ignoresSideEffects;
! emitIndex = i;
! }
! }
! }
!
! private Result verifyInputs() {
! DebugContext debug = root.getDebug();
! if (emitBlock != rootBlock) {
! assert consumed.find(root).ignoresSideEffects;
! Result result = verifyInputsDifferentBlock(root);
! if (result == Result.OK) {
! MatchContextSuccessDifferentBlocks.increment(debug);
! }
! return result;
! }
! // We are going to emit the match at emitIndex. We need to make sure nodes of the match
! // between emitIndex and rootIndex don't have inputs after position emitIndex that would
! // make emitIndex an illegal position.
! final List<Node> nodes = schedule.getBlockToNodesMap().get(rootBlock);
! for (int i = emitIndex + 1; i <= rootIndex; i++) {
Node node = nodes.get(i);
! ConsumedNode cn = consumed.find(node);
! if (cn != null) {
! assert cn.ignoresSideEffects;
! for (Node in : node.inputs()) {
! if (!consumed.contains(in)) {
! for (int j = emitIndex + 1; j < i; j++) {
! if (nodes.get(j) == in) {
! logFailedMatch("Earliest position in block is too late %s", in);
! assert consumed.find(root).ignoresSideEffects;
! assert verifyInputsDifferentBlock(root) != Result.OK;
! return Result.tooLate(node, rule.getPattern());
! }
! }
}
}
! }
! }
! assert verifyInputsDifferentBlock(root) == Result.OK;
! return Result.OK;
! }
!
! private Result verifyInputsDifferentBlock(Node node) {
! // Is there an input that's not part of the match that's after the emit position?
! for (Node in : node.inputs()) {
! if (in instanceof PhiNode) {
! Block b = schedule.getNodeToBlockMap().get(((PhiNode) in).merge());
! if (dominates(b, emitBlock)) {
! continue;
! }
! } else {
! Block b = schedule.getNodeToBlockMap().get(in);
! if (strictlyDominates(b, emitBlock) || (b == emitBlock && schedule.getBlockToNodesMap().get(emitBlock).indexOf(in) <= emitIndex)) {
! continue;
! }
! }
! ConsumedNode cn = consumed.find(in);
! if (cn == null) {
! logFailedMatch("Earliest position in block is too late %s", in);
! return Result.tooLate(node, rule.getPattern());
! }
! assert cn.ignoresSideEffects;
! Result res = verifyInputsDifferentBlock(in);
! if (res != Result.OK) {
! return res;
}
}
return Result.OK;
}
+ private void logFailedMatch(String s, Node node) {
+ if (LogVerbose.getValue(root.getOptions())) {
+ DebugContext debug = root.getDebug();
+ debug.log(s, node);
+ int startIndex = emitIndex;
+ if (emitBlock != rootBlock) {
+ int endIndex = schedule.getBlockToNodesMap().get(emitBlock).size() - 1;
+ final List<Node> emitBlockNodes = schedule.getBlockToNodesMap().get(emitBlock);
+ debug.log("%s:", emitBlock);
+ for (int j = startIndex; j <= endIndex; j++) {
+ Node theNode = emitBlockNodes.get(j);
+ debug.log("%s(%s) %1s", consumed.contains(theNode) ? "*" : " ", theNode.getUsageCount(), theNode);
+ }
+ startIndex = 0;
+ }
+ debug.log("%s:", rootBlock);
+ final List<Node> nodes = schedule.getBlockToNodesMap().get(rootBlock);
+ for (int j = startIndex; j <= rootIndex; j++) {
+ Node theNode = nodes.get(j);
+ debug.log("%s(%s) %1s", consumed.contains(theNode) ? "*" : " ", theNode.getUsageCount(), theNode);
+ }
+ }
+ }
+
/**
* Mark the interior nodes with INTERIOR_MATCH and set the Value of the root to be the result.
* During final LIR generation it will be evaluated to produce the actual LIR value.
*
* @param result
*/
public void setResult(ComplexMatchResult result) {
ComplexMatchValue value = new ComplexMatchValue(result);
+ Node emitNode = schedule.getBlockToNodesMap().get(emitBlock).get(emitIndex);
DebugContext debug = root.getDebug();
if (debug.isLogEnabled()) {
! debug.log("matched %s %s%s", rule.getName(), rule.getPattern(), emitIndex != rootIndex ? " skipping side effects" : "");
debug.log("with nodes %s", rule.formatMatch(root));
}
! for (ConsumedNode cn : consumed) {
! if (cn.node == root || cn.node == emitNode) {
! continue;
}
+ // All the interior nodes should be skipped during the normal doRoot calls in
+ // NodeLIRBuilder so mark them as interior matches. The root of the match will get a
+ // closure which will be evaluated to produce the final LIR.
+ builder.setMatchResult(cn.node, ComplexMatchValue.INTERIOR_MATCH);
+ }
+ builder.setMatchResult(emitNode, value);
+ if (root != emitNode) {
+ // Match is not emitted at the position of root in the block but the uses of root needs
+ // the result of the match so add a ComplexMatchValue that will simply return the result
+ // of the actual match above.
+ builder.setMatchResult(root, new ComplexMatchValue(gen -> gen.operand(emitNode)));
}
}
/**
* Mark a node as consumed by the match. Consumed nodes will never be evaluated.
*
* @return Result.OK if the node can be safely consumed.
*/
! public Result consume(Node node, boolean ignoresSideEffects, boolean atRoot) {
! if (atRoot) {
! consumed.add(node, ignoresSideEffects);
! return Result.OK;
}
+ assert MatchPattern.isSingleValueUser(node) : "should have already been checked";
if (builder.hasOperand(node)) {
return Result.alreadyUsed(node, rule.getPattern());
}
! consumed.add(node, ignoresSideEffects);
return Result.OK;
}
/**
* Return the named node. It's an error if the
*** 192,199 ****
throw new GraalError("missing node %s", name);
}
@Override
public String toString() {
! return String.format("%s %s (%d, %d) consumed %s", rule, root, startIndex, endIndex, consumed != null ? Arrays.toString(consumed.toArray()) : "");
}
}
--- 424,431 ----
throw new GraalError("missing node %s", name);
}
@Override
public String toString() {
! return String.format("%s %s (%s/%d, %s/%d) consumed %s", rule, root, rootBlock, rootIndex, emitBlock, emitIndex, consumed);
}
}
< prev index next >