Mercurial > hg > truffle

changeset 17399:5787218bad91

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Truffle: implemented recursive node iterator and node streams for the graal runtime.
author Christian Humer <christian.humer@gmail.com>
date Thu, 09 Oct 2014 17:25:18 +0200
parents 9e1ec84d2899
children e3dd05527c2f
files graal/com.oracle.graal.truffle.test/sl/TestInliningMaxCallerSize.sl graal/com.oracle.graal.truffle.test/sl/TestInliningRecursive2.sl graal/com.oracle.graal.truffle.test/src/com/oracle/graal/truffle/test/builtins/SLIsInlinedBuiltin.java graal/com.oracle.graal.truffle/src/com/oracle/graal/truffle/OptimizedCallTarget.java graal/com.oracle.truffle.api.test/src/com/oracle/truffle/api/test/nodes/NodeUtilTest.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeCost.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/nodes/NodeUtil.java
diffstat 7 files changed, 225 insertions(+), 70 deletions(-) [+]
line wrap: on
line diff
--- 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);
 }  
--- 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");
+    
 }  
--- 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<OptimizedDirectCallNode> 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<TruffleInlining> 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 {
--- 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<Node> nodeStream(boolean includeInlinedNodes) {
+        Iterator<Node> 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<String, Object> getDebugProperties() {
         Map<String, Object> properties = new LinkedHashMap<>();
         addASTSizeProperty(this, properties);
--- /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<Node> 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;
+        }
+
+    }
+
+}
--- 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;
+    }
+
 }
--- 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<Node> makeRecursiveIterator(Node node) {
+        return new RecursiveNodeIterator(node);
+    }
+
+    private final static class RecursiveNodeIterator implements Iterator<Node> {
+        private final List<Iterator<Node>> iteratorStack = new ArrayList<>();
+
+        public RecursiveNodeIterator(final Node node) {
+            iteratorStack.add(new Iterator<Node>() {
+
+                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<Node> iterator = peekIterator();
+            if (iterator == null) {
+                throw new NoSuchElementException();
+            }
+
+            Node node = iterator.next();
+            if (node != null) {
+                Iterator<Node> childIterator = makeIterator(node);
+                if (childIterator.hasNext()) {
+                    iteratorStack.add(childIterator);
+                }
+            }
+            return node;
+        }
+
+        private Iterator<Node> peekIterator() {
+            int tos = iteratorStack.size() - 1;
+            while (tos >= 0) {
+                Iterator<Node> 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<Long> 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<Node> 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<Node> 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);