# HG changeset patch # User Christian Humer # Date 1412868318 -7200 # Node ID 5787218bad9174c518226cd80b2c6aee07f7371a # Parent 9e1ec84d28992c6dda32d028c9f8c3ce68892748 Truffle: implemented recursive node iterator and node streams for the graal runtime. diff -r 9e1ec84d2899 -r 5787218bad91 graal/com.oracle.graal.truffle.test/sl/TestInliningMaxCallerSize.sl --- a/graal/com.oracle.graal.truffle.test/sl/TestInliningMaxCallerSize.sl Thu Oct 09 11:32:21 2014 -0700 +++ b/graal/com.oracle.graal.truffle.test/sl/TestInliningMaxCallerSize.sl Thu Oct 09 17:25:18 2014 +0200 @@ -23,7 +23,7 @@ waitForOptimization(callUntilOptimized(test1)); assertTrue(isInlined(test1, test1, inlinableFunction), "inlinableFunction is not inlined"); - waitForOptimization(callUntilOptimized(test2)); - assertFalse(isInlined(test2, test2, notInlinableFunction), "notInlinableFunction is inlined"); + waitForOptimization(callUntilOptimized(test2)); + assertFalse(isInlined(test2, test2, notInlinableFunction), "notInlinableFunction is inlined"); setOption("TruffleInliningMaxCallerSize", originalMaxCallerSize); } diff -r 9e1ec84d2899 -r 5787218bad91 graal/com.oracle.graal.truffle.test/sl/TestInliningRecursive2.sl --- a/graal/com.oracle.graal.truffle.test/sl/TestInliningRecursive2.sl Thu Oct 09 11:32:21 2014 -0700 +++ b/graal/com.oracle.graal.truffle.test/sl/TestInliningRecursive2.sl Thu Oct 09 17:25:18 2014 +0200 @@ -29,9 +29,9 @@ function main() { waitForOptimization(callUntilOptimized(test)); assertTrue(isInlined(test, test, fib), "not inlined: test -> fib"); - if (getOption("TruffleContextSensitiveInlining")) { - assertTrue(isInlined(test, fib, call), "not inlined: fib -> call"); - assertFalse(isInlined(test, call, fib), "inlined: call -> fib"); - assertTrue(isInlined(test, call, void), "inlined: call -> void"); - } + + assertTrue(isInlined(test, fib, call), "not inlined: fib -> call"); + assertFalse(isInlined(test, call, fib), "inlined: call -> fib"); + assertTrue(isInlined(test, call, void), "inlined: call -> void"); + } diff -r 9e1ec84d2899 -r 5787218bad91 graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/builtins/SLIsInlinedBuiltin.java --- a/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/builtins/SLIsInlinedBuiltin.java Thu Oct 09 11:32:21 2014 -0700 +++ b/graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/builtins/SLIsInlinedBuiltin.java Thu Oct 09 17:25:18 2014 +0200 @@ -25,6 +25,7 @@ import java.util.*; import com.oracle.graal.truffle.*; +import com.oracle.graal.truffle.TruffleInlining.CallTreeNodeVisitor; import com.oracle.truffle.api.CompilerDirectives.SlowPath; import com.oracle.truffle.api.dsl.*; import com.oracle.truffle.api.nodes.*; @@ -45,7 +46,7 @@ for (OptimizedCallTarget target : findDuplicateCallTargets((OptimizedCallTarget) rootFunction.getCallTarget())) { if (target.isValid()) { - searchInlined(trace, target, new ArrayList<>(), parentFunction, inlinedFunction); + searchInlined(trace, target, parentFunction, inlinedFunction); } } @@ -61,32 +62,25 @@ } } - private void searchInlined(InliningTrace trace, OptimizedCallTarget rootTarget, List stack, SLFunction parent, SLFunction inlinedFunction) { - OptimizedCallTarget root; - if (stack.isEmpty()) { - root = rootTarget; - } else { - root = stack.get(stack.size() - 1).getCurrentCallTarget(); - } + private static void searchInlined(InliningTrace trace, OptimizedCallTarget rootTarget, SLFunction parent, SLFunction inlinedFunction) { + rootTarget.accept(new CallTreeNodeVisitor() { - for (OptimizedDirectCallNode callNode : root.getCallNodes()) { - stack.add(callNode); - - boolean inlined = rootTarget.isInlined(stack); - if (callNode.getRootNode().getCallTarget() == parent.getCallTarget() && callNode.getCallTarget() == inlinedFunction.getCallTarget()) { - if (inlined) { - trace.allFalse = false; - } else { - trace.allTrue = false; + public boolean visit(List decisionStack, Node node) { + if (node instanceof OptimizedDirectCallNode) { + OptimizedDirectCallNode callNode = (OptimizedDirectCallNode) node; + if (callNode.getRootNode().getCallTarget() == parent.getCallTarget() && callNode.getCallTarget() == inlinedFunction.getCallTarget()) { + TruffleInliningDecision decision = (TruffleInliningDecision) decisionStack.get(decisionStack.size() - 1); + if (decision.isInline()) { + trace.allFalse = false; + } else { + trace.allTrue = false; + } + } } + return true; } - if (inlined) { - searchInlined(trace, rootTarget, stack, parent, inlinedFunction); - } - - stack.remove(stack.size() - 1); - } + }, true); } private static final class InliningTrace { diff -r 9e1ec84d2899 -r 5787218bad91 graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java --- a/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java Thu Oct 09 11:32:21 2014 -0700 +++ b/graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java Thu Oct 09 17:25:18 2014 +0200 @@ -472,6 +472,26 @@ invalidate(oldNode, newNode, reason); } + public void accept(NodeVisitor visitor, boolean includeInlinedNodes) { + TruffleInlining inliner = getInlining(); + if (includeInlinedNodes && inliner != null) { + inlining.accept(this, visitor); + } else { + getRootNode().accept(visitor); + } + } + + public Stream nodeStream(boolean includeInlinedNodes) { + Iterator iterator; + TruffleInlining inliner = getInlining(); + if (includeInlinedNodes && inliner != null) { + iterator = inliner.makeNodeIterator(this); + } else { + iterator = NodeUtil.makeRecursiveIterator(this.getRootNode()); + } + return StreamSupport.stream(Spliterators.spliteratorUnknownSize(iterator, 0), false); + } + public Map getDebugProperties() { Map properties = new LinkedHashMap<>(); addASTSizeProperty(this, properties); diff -r 9e1ec84d2899 -r 5787218bad91 graal/com.oracle.truffle.api.test/src/com/oracle/truffle/api/test/nodes/NodeUtilTest.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.truffle.api.test/src/com/oracle/truffle/api/test/nodes/NodeUtilTest.java Thu Oct 09 17:25:18 2014 +0200 @@ -0,0 +1,93 @@ +/* + * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.truffle.api.test.nodes; + +import java.util.*; + +import org.junit.*; +import static org.junit.Assert.*; +import static org.hamcrest.CoreMatchers.*; + +import com.oracle.truffle.api.frame.*; +import com.oracle.truffle.api.nodes.*; + +public class NodeUtilTest { + + @Test + public void testRecursiveIterator1() { + TestRootNode root = new TestRootNode(); + root.child0 = new TestNode(); + root.adoptChildren(); + + int count = iterate(NodeUtil.makeRecursiveIterator(root)); + + assertThat(count, is(2)); + assertThat(root.visited, is(0)); + assertThat(root.child0.visited, is(1)); + } + + private static int iterate(Iterator iterator) { + int iterationCount = 0; + while (iterator.hasNext()) { + Node node = iterator.next(); + if (node == null) { + continue; + } + if (node instanceof TestNode) { + ((TestNode) node).visited = iterationCount; + } else if (node instanceof TestRootNode) { + ((TestRootNode) node).visited = iterationCount; + } else { + throw new AssertionError(); + } + iterationCount++; + } + return iterationCount; + } + + private static class TestNode extends Node { + + @Child TestNode child0; + @Child TestNode child1; + + private int visited; + + public TestNode() { + } + + } + + private static class TestRootNode extends RootNode { + + @Child TestNode child0; + + private int visited; + + @Override + public Object execute(VirtualFrame frame) { + return null; + } + + } + +} diff -r 9e1ec84d2899 -r 5787218bad91 graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeCost.java --- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeCost.java Thu Oct 09 11:32:21 2014 -0700 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeCost.java Thu Oct 09 17:25:18 2014 +0200 @@ -66,4 +66,8 @@ */ MEGAMORPHIC; + public boolean isTrivial() { + return this == NONE || this == UNINITIALIZED; + } + } diff -r 9e1ec84d2899 -r 5787218bad91 graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeUtil.java --- a/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeUtil.java Thu Oct 09 11:32:21 2014 -0700 +++ b/graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeUtil.java Thu Oct 09 17:25:18 2014 +0200 @@ -344,6 +344,74 @@ return NodeClass.get(node.getClass()).makeIterator(node); } + public static Iterator makeRecursiveIterator(Node node) { + return new RecursiveNodeIterator(node); + } + + private final static class RecursiveNodeIterator implements Iterator { + private final List> iteratorStack = new ArrayList<>(); + + public RecursiveNodeIterator(final Node node) { + iteratorStack.add(new Iterator() { + + private boolean visited; + + public void remove() { + throw new UnsupportedOperationException(); + } + + public Node next() { + if (visited) { + throw new NoSuchElementException(); + } + visited = true; + return node; + } + + public boolean hasNext() { + return !visited; + } + }); + } + + public boolean hasNext() { + return peekIterator() != null; + } + + public Node next() { + Iterator iterator = peekIterator(); + if (iterator == null) { + throw new NoSuchElementException(); + } + + Node node = iterator.next(); + if (node != null) { + Iterator childIterator = makeIterator(node); + if (childIterator.hasNext()) { + iteratorStack.add(childIterator); + } + } + return node; + } + + private Iterator peekIterator() { + int tos = iteratorStack.size() - 1; + while (tos >= 0) { + Iterator iterable = iteratorStack.get(tos); + if (iterable.hasNext()) { + return iterable; + } else { + iteratorStack.remove(tos--); + } + } + return null; + } + + public void remove() { + throw new UnsupportedOperationException(); + } + } + private static long[] toLongArray(List list) { long[] array = new long[list.size()]; for (int i = 0; i < list.size(); i++) { @@ -606,17 +674,25 @@ } public static int countNodes(Node root) { - return countNodes(root, null, false); + Iterator nodeIterator = makeRecursiveIterator(root); + int count = 0; + while (nodeIterator.hasNext()) { + nodeIterator.next(); + count++; + } + return count; } public static int countNodes(Node root, NodeCountFilter filter) { - return countNodes(root, filter, false); - } - - public static int countNodes(Node root, NodeCountFilter filter, boolean visitInlinedCallNodes) { - NodeCountVisitor nodeCount = new NodeCountVisitor(filter, visitInlinedCallNodes); - root.accept(nodeCount); - return nodeCount.nodeCount; + Iterator nodeIterator = makeRecursiveIterator(root); + int count = 0; + while (nodeIterator.hasNext()) { + Node node = nodeIterator.next(); + if (node != null && filter.isCounted(node)) { + count++; + } + } + return count; } public interface NodeCountFilter { @@ -625,38 +701,6 @@ } - private static final class NodeCountVisitor implements NodeVisitor { - - private final boolean visitInlinedCallNodes; - int nodeCount; - private final NodeCountFilter filter; - - private NodeCountVisitor(NodeCountFilter filter, boolean visitInlinedCallNodes) { - this.filter = filter; - this.visitInlinedCallNodes = visitInlinedCallNodes; - } - - @Override - public boolean visit(Node node) { - if (filter == null || filter.isCounted(node)) { - nodeCount++; - } - - if (visitInlinedCallNodes && node instanceof DirectCallNode) { - DirectCallNode call = (DirectCallNode) node; - if (call.isInlined()) { - Node target = ((RootCallTarget) call.getCurrentCallTarget()).getRootNode(); - if (target != null) { - target.accept(this); - } - } - } - - return true; - } - - } - public static String printCompactTreeToString(Node node) { StringWriter out = new StringWriter(); printCompactTree(new PrintWriter(out), null, node, 1);