Mercurial > hg > truffle
changeset 4328:60c48d99c28b
Loop :
consistant naming (local->direct),
print loop exits when printing loop structure,
fix for loop exits : one loop exit may also exit outter loops
Added cardinalty for NodeBitMaps
Added exits detection tests to NestedLoopTest
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/Loop.java Wed Jan 25 18:01:00 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/Loop.java Thu Jan 26 12:17:11 2012 +0100 @@ -75,12 +75,12 @@ return parent == l || (parent != null && parent.isChildOf(l)); } - public boolean localContainsFixed(FixedNode n) { + public boolean containsDirectFixed(FixedNode n) { return directCFGNodes.isMarked(n); } public boolean containsFixed(FixedNode n) { - if (localContainsFixed(n)) { + if (containsDirectFixed(n)) { return true; } for (Loop child : children()) { @@ -104,7 +104,7 @@ } @SuppressWarnings("unchecked") - public Iterable<FixedNode> fixedNodes() { + public Iterable<FixedNode> directFixedNodes() { return (Iterable) directCFGNodes; } @@ -113,7 +113,7 @@ loop.parent = this; } - NodeBitMap directCFGNode() { + NodeBitMap directCFGNodes() { return directCFGNodes; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/LoopInfo.java Wed Jan 25 18:01:00 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/LoopInfo.java Thu Jan 26 12:17:11 2012 +0100 @@ -65,17 +65,26 @@ } } - private void print(Loop loop) { - TTY.println("%s", loop.loopBegin()); - TTY.println("-- subnodes"); - for (Node node : loop.fixedNodes()) { - TTY.println(" " + node); + private void print(final Loop loop) { + TTY.out().printf("%s\n", loop.loopBegin()); + TTY.out().println("-- exits"); + TTY.out().adjustIndentation(+2); + for (Node n : loop.exits()) { + TTY.out().printf("%s from %s\n", n, n.predecessor()); } - TTY.println("-- subloops"); + TTY.out().adjustIndentation(-2); + TTY.out().println("-- directNodes"); + TTY.out().adjustIndentation(+2); + for (final Node node : loop.directFixedNodes()) { + TTY.out().printf("%s\n", node); + } + TTY.out().adjustIndentation(-2); + TTY.out().println("-- subloops"); + TTY.out().adjustIndentation(+2); for (Loop sub : loop.children()) { print(sub); } - TTY.println("-- sub"); - TTY.println(); + TTY.out().adjustIndentation(-2); + TTY.out().println("-- sub"); } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/LoopUtil.java Wed Jan 25 18:01:00 2012 +0100 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/loop/LoopUtil.java Thu Jan 26 12:17:11 2012 +0100 @@ -53,11 +53,13 @@ //Find exits for (Loop loop : info.loops()) { - for (FixedNode n : loop.fixedNodes()) { + for (FixedNode n : loop.directFixedNodes()) { if (n instanceof ControlSplitNode) { for (BeginNode sux : ((ControlSplitNode) n).blockSuccessors()) { - if (!loop.containsFixed(sux)) { - loop.exits().mark(sux); + Loop l = loop; + while (l != null && !l.containsFixed(sux)) { + l.exits().mark(sux); + l = l.parent(); } } } @@ -103,10 +105,10 @@ mark((LoopBeginNode) n, nodeToLoop); } else { if (oldMark != null) { - oldMark.directCFGNode().clear(n); + oldMark.directCFGNodes().clear(n); } nodeToLoop.set(n, loop); - loop.directCFGNode().mark(n); + loop.directCFGNodes().mark(n); } } }
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java Wed Jan 25 18:01:00 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java Thu Jan 26 12:17:11 2012 +0100 @@ -160,4 +160,8 @@ public Iterator<Node> iterator() { return new MarkedNodeIterator(NodeBitMap.this, graph().getNodes().iterator()); } + + public int cardinality() { + return bitMap.cardinality(); + } }
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeUsagesList.java Wed Jan 25 18:01:00 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeUsagesList.java Thu Jan 26 12:17:11 2012 +0100 @@ -48,10 +48,16 @@ return size; } + @Override public boolean isEmpty() { return size == 0; } + @Override + public boolean isNotEmpty() { + return size > 0; + } + protected void incModCount() { modCount++; }
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/iterators/FilteredNodeIterable.java Wed Jan 25 18:01:00 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/iterators/FilteredNodeIterable.java Thu Jan 26 12:17:11 2012 +0100 @@ -43,6 +43,14 @@ this.predicate = predicate.or(new TypePredicate(clazz)); return (FilteredNodeIterable<Node>) this; } + public FilteredNodeIterable<T> and(NodePredicate nodePredicate) { + this.predicate = this.predicate.and(nodePredicate); + return this; + } + public FilteredNodeIterable<T> or(NodePredicate nodePredicate) { + this.predicate = this.predicate.or(nodePredicate); + return this; + } @Override public Iterator<T> iterator() { final Iterator<T> iterator = nodeIterable.iterator();
--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/iterators/NodeIterable.java Wed Jan 25 18:01:00 2012 +0100 +++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/iterators/NodeIterable.java Thu Jan 26 12:17:11 2012 +0100 @@ -39,6 +39,9 @@ public <F extends T> FilteredNodeIterable<F> filter(Class<F> clazz) { return new FilteredNodeIterable<>(this).and(clazz); } + public FilteredNodeIterable<T> filter(NodePredicate predicate) { + return new FilteredNodeIterable<>(this).and(predicate); + } public List<T> snapshot() { ArrayList<T> list = new ArrayList<>(); for (T n : this) { @@ -53,4 +56,19 @@ } return null; } + public int count() { + int count = 0; + Iterator<T> iterator = iterator(); + while (iterator.hasNext()) { + iterator.next(); + count++; + } + return count; + } + public boolean isEmpty() { + return count() == 0; + } + public boolean isNotEmpty() { + return iterator().hasNext(); + } }
--- a/graal/com.oracle.max.graal.tests/src/com/oracle/max/graal/compiler/tests/NestedLoopTest.java Wed Jan 25 18:01:00 2012 +0100 +++ b/graal/com.oracle.max.graal.tests/src/com/oracle/max/graal/compiler/tests/NestedLoopTest.java Thu Jan 26 12:17:11 2012 +0100 @@ -27,98 +27,93 @@ import com.oracle.max.graal.compiler.loop.*; import com.oracle.max.graal.nodes.*; -/** - * In the following tests, the usages of local variable "a" are replaced with the integer constant 0. - * Then canonicalization is applied and it is verified that the resulting graph is equal to the - * graph of the method that just has a "return 1" statement in it. - */ public class NestedLoopTest extends GraphTest { @Test public void test1() { - test("test1Snippet"); + test("test1Snippet", 5, 5, 4); } @Test public void test2() { - test("test2Snippet"); + test("test2Snippet", 2, 5, 4); } @Test public void test3() { - test("test3Snippet"); + test("test3Snippet", 1, 5, 4); } @Test public void test4() { - test("test4Snippet"); + test("test4Snippet", 1, 6, 4); } @SuppressWarnings("all") public static void test1Snippet(int a) { - while (a()) { - m1: while (b()) { - while (c()) { - if (d()) { - break m1; + while (a()) { // a() exits root, while() exits root + m1: while (b()) { // b() exits nested & root, while() exits nested + while (c()) { // c() exits innermost & nested & root, while() exits innermost + if (d()) { // d() exits innermost & nested & root + break m1; // break exits innermost & nested } } } } - } + }// total : root = 5 exits, nested = 5, innermost = 4 @SuppressWarnings("all") public static void test2Snippet(int a) { - while (a()) { + while (a()) { // a() exits root, while() exits root try { - m1: while (b()) { - while (c()) { - if (d()) { - break m1; + m1: while (b()) { // b() exits nested, while() exits nested + while (c()) { // c() exits innermost & nested, while() exits innermost + if (d()) { // d() exits innermost & nested + break m1; // break exits innermost & nested } } } } catch (Throwable t) { } } - } + }// total : root = 2 exits, nested = 5, innermost = 4 @SuppressWarnings("all") public static void test3Snippet(int a) { - while (a == 0) { + while (a == 0) { // while() exits root try { - m1: while (b()) { - while (c()) { - if (d()) { - a(); - break m1; + m1: while (b()) { // b() exits nested, while() exits nested + while (c()) { // c() exits innermost & nested, while() exits innermost + if (d()) { // d() exits innermost & nested + a(); // a() exits nothing (already outside innermost & nested) + break m1; // break exits innermost & nested } } } } catch (Throwable t) { } } - } + }// total : root = 1 exit, nested = 5, innermost = 4 public static void test4Snippet(int a) { - while (a != 0) { + while (a != 0) { // while() exits root try { - m1: while (a != 0) { - b(); - while (c()) { - if (d()) { - break m1; + m1: while (a != 0) { // while() exits nested + b(); // b() exits nested + while (c()) { // c() exits innermost & nested, while() exits innermost + if (d()) { // d() exits innermost & nested + break m1; // break exits innermost & nested } } if (a != 2) { - a(); - throw new Exception(); + a(); // a() exits nothing (already outside innermost & nested) + throw new Exception(); // throw exits nested } } } catch (Throwable t) { } } - } + } // total : root = 1 exit, nested = 6, innermost = 4 private static boolean a() { return false; @@ -145,7 +140,7 @@ return null; } - private void test(String snippet) { + private void test(String snippet, int rootExits, int nestedExits, int innerExits) { StructuredGraph graph = parse(snippet); print(graph); LoopInfo loopInfo = LoopUtil.computeLoopInfo(graph); @@ -157,10 +152,15 @@ Invoke b = getInvoke("b", graph); Invoke c = getInvoke("c", graph); Invoke d = getInvoke("d", graph); - Assert.assertTrue(rootLoop.localContainsFixed((FixedNode) a)); - Assert.assertTrue(nestedLoop.localContainsFixed((FixedNode) b)); - Assert.assertTrue(innerMostLoop.localContainsFixed((FixedNode) c)); - Assert.assertTrue(innerMostLoop.localContainsFixed((FixedNode) d)); + Assert.assertTrue(rootLoop.containsDirectFixed((FixedNode) a)); + Assert.assertTrue(nestedLoop.containsDirectFixed((FixedNode) b)); + Assert.assertTrue(innerMostLoop.containsDirectFixed((FixedNode) c)); + Assert.assertTrue(innerMostLoop.containsDirectFixed((FixedNode) d)); + Assert.assertTrue(rootLoop.containsFixed((FixedNode) d)); + Assert.assertTrue(nestedLoop.containsFixed((FixedNode) d)); + Assert.assertEquals(rootExits, rootLoop.exits().cardinality()); + Assert.assertEquals(nestedExits, nestedLoop.exits().cardinality()); + Assert.assertEquals(innerExits, innerMostLoop.exits().cardinality()); print(graph); } }