Mercurial > hg > truffle

changeset 17043:46cefd15ba3f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
NodeRefIterator advances lazily instead of eagerly, allowing the next element to be cached in the advance operation
author Doug Simon <doug.simon@oracle.com>
date Thu, 04 Sep 2014 12:54:06 +0200
parents 9fe9d32e00b5
children d5289a18cf5d
files graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/NodeRefIteratorTest.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeAllRefsIterator.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterable.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterator.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefWithModCountIterator.java graal/com.oracle.graal.nodeinfo.processor/src/com/oracle/graal/nodeinfo/processor/GraphNodeGenerator.java
diffstat 6 files changed, 259 insertions(+), 44 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/NodeRefIteratorTest.java	Thu Sep 04 12:54:06 2014 +0200
@@ -0,0 +1,219 @@
+/*
+ * Copyright (c) 2012, 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.graal.compiler.test;
+
+import org.junit.*;
+
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodeinfo.*;
+import com.oracle.graal.nodes.*;
+
+public class NodeRefIteratorTest extends GraalCompilerTest {
+
+    @NodeInfo
+    static class TestNode extends Node {
+        @Successor Node s1;
+        @Successor Node s2;
+        @Successor NodeSuccessorList<Node> stail;
+
+        @Input NodeInputList<ValueNode> itail;
+        @Input ValueNode i1;
+        @Input ValueNode i2;
+
+        public static TestNode create() {
+            return USE_GENERATED_NODES ? new NodeRefIteratorTest_TestNodeGen() : new TestNode();
+        }
+    }
+
+    @Test
+    public void testInputs() {
+        TestNode n = TestNode.create();
+
+        ConstantNode i1 = ConstantNode.forInt(1);
+        ConstantNode i2 = ConstantNode.forDouble(1.0d);
+        ConstantNode i3 = ConstantNode.forInt(4);
+        ConstantNode i4 = ConstantNode.forInt(14);
+        n.itail = new NodeInputList<>(n, new ValueNode[]{i3, i4});
+        n.i1 = i1;
+        n.i2 = i2;
+
+        NodeClassIterable inputs = n.inputs();
+
+        NodePosIterator iterator = inputs.iterator();
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i1);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i2);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i3);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i4);
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = inputs.iterator();
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "input 0/-1");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "input 1/-1");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "input 2/0");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "input 2/1");
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = inputs.iterator();
+        n.i1 = i4;
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i4);
+        n.i2 = i1;
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i1);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i3);
+        n.itail.initialize(1, i4);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i4);
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = inputs.iterator();
+        n.i1 = null;
+        n.i2 = i2;
+        n.itail.initialize(0, null);
+        n.itail.initialize(1, i4);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i2);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i4);
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = inputs.withNullIterator();
+        n.i1 = null;
+        n.i2 = null;
+        n.itail.initialize(0, i3);
+        n.itail.initialize(1, null);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), i3);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+    }
+
+    @Test
+    public void testSuccessors() {
+        TestNode n = TestNode.create();
+        EndNode s1 = EndNode.create();
+        EndNode s2 = EndNode.create();
+        EndNode s3 = EndNode.create();
+        EndNode s4 = EndNode.create();
+        n.s1 = s1;
+        n.s2 = s2;
+        n.stail = new NodeSuccessorList<>(n, new Node[]{s3, s4});
+
+        NodeClassIterable successors = n.successors();
+        NodePosIterator iterator = successors.iterator();
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s1);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s2);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s3);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s4);
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = successors.iterator();
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "successor 0/-1");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "successor 1/-1");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "successor 2/0");
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.nextPosition().toString(), "successor 2/1");
+        Assert.assertFalse(iterator.hasNext());
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = successors.iterator();
+        n.s1 = s4;
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s4);
+        n.s2 = s1;
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s1);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s3);
+        n.stail.initialize(1, s4);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s4);
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = successors.iterator();
+        n.s1 = null;
+        n.s2 = s2;
+        n.stail.initialize(0, null);
+        n.stail.initialize(1, s4);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s2);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s4);
+        Assert.assertFalse(iterator.hasNext());
+
+        iterator = successors.withNullIterator();
+        n.s1 = null;
+        n.s2 = null;
+        n.stail.initialize(0, s3);
+        n.stail.initialize(1, null);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertEquals(iterator.next(), s3);
+        Assert.assertTrue(iterator.hasNext());
+        Assert.assertNull(iterator.next());
+        Assert.assertFalse(iterator.hasNext());
+    }
+}
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeAllRefsIterator.java	Thu Sep 04 12:51:43 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeAllRefsIterator.java	Thu Sep 04 12:54:06 2014 +0200
@@ -33,14 +33,16 @@
 
     public NodeAllRefsIterator(Node node, int nodeFields, int nodeListFields, boolean isInputs) {
         super(node, nodeFields, nodeListFields, isInputs);
-        forward();
     }
 
     @Override
     protected void forward() {
+        assert needsForward;
+        needsForward = false;
         if (index < nodeFields) {
             index++;
             if (index < nodeFields) {
+                nextElement = getNode(index);
                 return;
             }
         } else {
@@ -52,6 +54,7 @@
                 list = getNodeList(index - nodeFields);
             }
             if (subIndex < list.size()) {
+                nextElement = list.get(subIndex);
                 return;
             }
             subIndex = 0;
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterable.java	Thu Sep 04 12:51:43 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterable.java	Thu Sep 04 12:54:06 2014 +0200
@@ -56,9 +56,7 @@
         if (MODIFICATION_COUNTS_ENABLED) {
             return new NodeRefWithModCountIterator(node, nodeFields, nodeListFields, isInputs);
         } else {
-            NodeRefIterator iter = new NodeRefIterator(node, nodeFields, nodeListFields, isInputs);
-            iter.forward();
-            return iter;
+            return new NodeRefIterator(node, nodeFields, nodeListFields, isInputs);
         }
     }
 
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterator.java	Thu Sep 04 12:51:43 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefIterator.java	Thu Sep 04 12:54:06 2014 +0200
@@ -67,6 +67,8 @@
      */
     protected int subIndex;
 
+    protected Node nextElement;
+    protected boolean needsForward;
     protected NodeList<? extends Node> list;
 
     /**
@@ -85,7 +87,8 @@
         this.allNodeRefFields = nodeListFields + nodeFields;
         this.nodeFields = nodeFields;
         this.isInputs = isInputs;
-        index = Node.NOT_ITERABLE;
+        this.needsForward = true;
+        index = -1;
         subIndex = 0;
     }
 
@@ -111,10 +114,12 @@
     }
 
     protected void forward() {
+        needsForward = false;
         if (index < nodeFields) {
             index++;
             while (index < nodeFields) {
-                if (getNode(index) != null) {
+                nextElement = getNode(index);
+                if (nextElement != null) {
                     return;
                 }
                 index++;
@@ -128,7 +133,8 @@
             }
             assert list == getNodeList(index - nodeFields);
             while (subIndex < list.size()) {
-                if (list.get(subIndex) != null) {
+                nextElement = list.get(subIndex);
+                if (nextElement != null) {
                     return;
                 }
                 subIndex++;
@@ -140,39 +146,39 @@
     }
 
     private Node nextElement() {
-        if (index < nodeFields) {
-            return getNode(index);
-        } else if (index < allNodeRefFields) {
-            assert getNodeList(index - nodeFields) == list;
-            return list.get(subIndex);
+        if (needsForward) {
+            forward();
+        }
+        needsForward = true;
+        if (index < allNodeRefFields) {
+            return nextElement;
         }
         throw new NoSuchElementException();
     }
 
     @Override
     public boolean hasNext() {
-        return index >= 0 && index < allNodeRefFields;
+        if (needsForward) {
+            forward();
+        }
+        return index < allNodeRefFields;
     }
 
     @Override
     public Node next() {
-        try {
-            return nextElement();
-        } finally {
-            forward();
-        }
+        return nextElement();
     }
 
     public Position nextPosition() {
-        try {
-            if (index < nodeFields) {
-                return new Position(isInputs, index, Node.NOT_ITERABLE);
-            } else {
-                return new Position(isInputs, index, subIndex);
-            }
-        } finally {
+        if (needsForward) {
             forward();
         }
+        needsForward = true;
+        if (index < nodeFields) {
+            return new Position(isInputs, index, Node.NOT_ITERABLE);
+        } else {
+            return new Position(isInputs, index, subIndex);
+        }
     }
 
     @Override
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefWithModCountIterator.java	Thu Sep 04 12:51:43 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeRefWithModCountIterator.java	Thu Sep 04 12:54:06 2014 +0200
@@ -40,7 +40,6 @@
         super(node, nodeFields, nodeListFields, isInputs);
         assert MODIFICATION_COUNTS_ENABLED;
         this.modCount = node.modCount();
-        forward();
     }
 
     @Override
--- a/graal/com.oracle.graal.nodeinfo.processor/src/com/oracle/graal/nodeinfo/processor/GraphNodeGenerator.java	Thu Sep 04 12:51:43 2014 +0200
+++ b/graal/com.oracle.graal.nodeinfo.processor/src/com/oracle/graal/nodeinfo/processor/GraphNodeGenerator.java	Thu Sep 04 12:54:06 2014 +0200
@@ -524,7 +524,6 @@
 
         // Constructor
         CodeExecutableElement ctor = new CodeExecutableElement(Collections.emptySet(), null, name);
-        addParameter(ctor, getType(boolean.class), "callForward");
         CodeTreeBuilder b = ctor.createBuilder();
         b.startStatement().startSuperCall();
         b.string(genClassName, ".this");
@@ -532,9 +531,6 @@
         b.string(String.valueOf(nodeListFields.size()));
         b.string(String.valueOf(nodeRefsType == NodeRefsType.Inputs));
         b.end().end();
-        b.startIf().string("callForward").end().startBlock();
-        b.startStatement().string("forward()").end();
-        b.end();
         cls.add(ctor);
 
         // Methods overriding those in NodeRefIterator
@@ -681,23 +677,20 @@
         CodeTypeElement cls = new CodeTypeElement(modifiers(PRIVATE, FINAL), ElementKind.CLASS, packageElement, name);
         cls.setSuperClass(inputsIteratorType);
 
-        // Constructor
-        CodeExecutableElement ctor = new CodeExecutableElement(Collections.emptySet(), null, name);
-        CodeTreeBuilder b = ctor.createBuilder();
-        b.startStatement().startSuperCall();
-        b.string("true");
-        b.end().end();
-        cls.add(ctor);
-
         // forward() method
         CodeExecutableElement method = new CodeExecutableElement(modifiers(PROTECTED), getType(void.class), "forward");
-        b = method.createBuilder();
+        CodeTreeBuilder b = method.createBuilder();
         int nodeFieldsSize = nodeFields.size();
         int nodeListFieldsSize = nodeListFields.size();
         String cond = "index < " + nodeFieldsSize;
+        if (GENERATE_ASSERTIONS) {
+            b.startAssert().string("needsForward").end();
+        }
+        b.startStatement().string("needsForward = false").end();
         b.startIf().string(cond).end().startBlock();
         b.startStatement().string("index++").end();
         b.startIf().string(cond).end().startBlock();
+        b.startStatement().string("nextElement = getNode(index)").end();
         b.startStatement().string("return").end();
         b.end();
         b.end();
@@ -710,6 +703,7 @@
         b.startStatement().string("list = getNodeList(index - " + nodeFieldsSize + ")").end();
         b.end();
         b.startIf().string("subIndex < list.size()").end().startBlock();
+        b.startStatement().string("nextElement = list.get(subIndex)").end();
         b.startStatement().string("return").end();
         b.end();
         b.startStatement().string("subIndex = 0").end();
@@ -733,12 +727,8 @@
         // Constructor
         CodeExecutableElement ctor = new CodeExecutableElement(Collections.emptySet(), null, name);
         CodeTreeBuilder b = ctor.createBuilder();
-        b.startStatement().startSuperCall();
-        b.string("false");
-        b.end().end();
         b.startAssert().staticReference(getType("com.oracle.graal.graph.Graph"), "MODIFICATION_COUNTS_ENABLED").end();
         b.startStatement().string("this.modCount = modCount()").end();
-        b.startStatement().string("forward()").end();
         cls.add(ctor);
 
         // hasNext, next and nextPosition methods
@@ -773,7 +763,7 @@
         b.startStatement().string("return new " + nodeRefsType + "WithModCountIterator()").end();
         b.end();
         b.startElseBlock();
-        b.startStatement().string("return new " + nodeRefsType + "Iterator(true)").end();
+        b.startStatement().string("return new " + nodeRefsType + "Iterator()").end();
         b.end();
         cls.add(method);