Mercurial > hg > truffle

changeset 15956:edc33e8715d5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
NodeWorkList refactoring
author Lukas Stadler <lukas.stadler@oracle.com>
date Wed, 28 May 2014 17:20:35 +0200
parents 3f48e9a1016c
children cf51d3ade2fb
files graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInsideBefore.java graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInsideFrom.java graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentWhole.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java
diffstat 8 files changed, 144 insertions(+), 187 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Wed May 28 17:20:35 2014 +0200
@@ -752,11 +752,11 @@
     }
 
     public NodeWorkList createNodeWorkList() {
-        return new NodeWorkList(this);
+        return new NodeWorkList.SingletonNodeWorkList(this);
     }
 
-    public NodeWorkList createNodeWorkList(boolean fill, int iterationLimitPerNode) {
-        return new NodeWorkList(this, fill, iterationLimitPerNode);
+    public NodeWorkList createIterativeNodeWorkList(boolean fill, int iterationLimitPerNode) {
+        return new NodeWorkList.IterativeNodeWorkList(this, fill, iterationLimitPerNode);
     }
 
     void register(Node node) {
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java	Wed May 28 17:20:35 2014 +0200
@@ -24,24 +24,11 @@
 
 import java.util.*;
 
-public class NodeWorkList implements Iterable<Node> {
+public abstract class NodeWorkList implements Iterable<Node> {
 
-    private final NodeBitMap visited;
-    private final NodeBitMap inQueue;
-    private final Queue<Node> worklist;
-    private int iterationLimit = Integer.MAX_VALUE;
-    private Node firstNoChange;
-    private Node lastPull;
-    private Node lastChain;
+    protected final Queue<Node> worklist;
 
-    // boolean addAgain
-    public NodeWorkList(Graph graph) {
-        this(graph, false, -1);
-    }
-
-    public NodeWorkList(Graph graph, boolean fill, int iterationLimitPerNode) {
-        visited = graph.createNodeBitMap();
-        inQueue = graph.createNodeBitMap();
+    private NodeWorkList(Graph graph, boolean fill) {
         if (fill) {
             ArrayDeque<Node> deque = new ArrayDeque<>(graph.getNodeCount());
             for (Node node : graph.getNodes()) {
@@ -51,9 +38,6 @@
         } else {
             worklist = new ArrayDeque<>();
         }
-        if (iterationLimitPerNode > 0) {
-            iterationLimit = iterationLimitPerNode * graph.getNodeCount();
-        }
     }
 
     public void addAll(Iterable<? extends Node> nodes) {
@@ -64,103 +48,13 @@
         }
     }
 
-    public void add(Node node) {
-        if (node != null) {
-            if (!visited.isMarkedAndGrow(node)) {
-                addAgain(node);
-            }
-        }
-    }
+    public abstract void add(Node node);
 
-    public void addAgain(Node node) {
-        if (node != null && !inQueue.isMarkedAndGrow(node)) {
-            if (lastPull == node) {
-                if (firstNoChange == null) {
-                    firstNoChange = node;
-                    lastChain = node;
-                } else if (node == firstNoChange) {
-                    throw new InfiniteWorkException("ReAdded " + node);
-                } else {
-                    lastChain = node;
-                }
-            } else {
-                firstNoChange = null;
-            }
-            visited.markAndGrow(node);
-            inQueue.markAndGrow(node);
-            worklist.add(node);
-        }
-    }
-
-    public void clearVisited() {
-        visited.clearAll();
-    }
-
-    public void replaced(Node newNode, Node oldNode) {
-        this.replaced(newNode, oldNode, false);
-    }
-
-    public void replaced(Node newNode, Node oldNode, boolean add) {
-        worklist.remove(oldNode);
-        if (newNode == null) {
-            return;
-        }
-        if (add) {
-            this.add(newNode);
-        }
-        for (Node n : newNode.usages()) {
-            addAgain(n);
-        }
-    }
+    private abstract class QueueConsumingIterator implements Iterator<Node> {
 
-    public boolean isMarked(Node node) {
-        return visited.isMarkedAndGrow(node);
-    }
-
-    public boolean isNew(Node node) {
-        return visited.isNew(node);
-    }
-
-    public boolean isEmpty() {
-        return worklist.isEmpty();
-    }
-
-    public boolean isInQueue(Node node) {
-        return !inQueue.isNew(node) && inQueue.isMarkedAndGrow(node);
-    }
-
-    private class QueueConsumingIterator implements Iterator<Node> {
-
-        private final Queue<Node> queue;
-
-        public QueueConsumingIterator(Queue<Node> queue) {
-            this.queue = queue;
-        }
-
-        @Override
-        public boolean hasNext() {
-            dropDeleted();
-            return iterationLimit > 0 && !queue.isEmpty();
-        }
-
-        @Override
-        public Node next() {
-            if (iterationLimit-- <= 0) {
-                throw new NoSuchElementException();
-            }
-            dropDeleted();
-            Node node = queue.remove();
-            if (lastPull != lastChain) {
-                firstNoChange = null;
-            }
-            lastPull = node;
-            inQueue.clearAndGrow(node);
-            return node;
-        }
-
-        private void dropDeleted() {
-            while (!queue.isEmpty() && queue.peek().isDeleted()) {
-                queue.remove();
+        protected void dropDeleted() {
+            while (!worklist.isEmpty() && worklist.peek().isDeleted()) {
+                worklist.remove();
             }
         }
 
@@ -170,74 +64,142 @@
         }
     }
 
-    @Override
-    public Iterator<Node> iterator() {
-        return new QueueConsumingIterator(worklist);
-    }
-
-    private static class UnmarkedNodeIterator implements Iterator<Node> {
+    public static final class IterativeNodeWorkList extends NodeWorkList {
 
-        private final NodeBitMap visited;
-        private Iterator<Node> nodes;
-        private Node nextNode;
-
-        public UnmarkedNodeIterator(NodeBitMap visited, Iterator<Node> nodes) {
-            this.visited = visited;
-            this.nodes = nodes;
-            forward();
-        }
+        private static final int EXPLICIT_BITMAP_THRESHOLD = 10;
+        protected NodeBitMap inQueue;
 
-        private void forward() {
-            do {
-                if (!nodes.hasNext()) {
-                    nextNode = null;
-                    return;
-                }
-                nextNode = nodes.next();
-            } while (visited.isMarked(nextNode));
-        }
+        private int iterationLimit = Integer.MAX_VALUE;
+        private Node firstNoChange;
+        private Node lastPull;
+        private Node lastChain;
 
-        @Override
-        public boolean hasNext() {
-            return nextNode != null;
-        }
-
-        @Override
-        public Node next() {
-            try {
-                return nextNode;
-            } finally {
-                forward();
+        public IterativeNodeWorkList(Graph graph, boolean fill, int iterationLimitPerNode) {
+            super(graph, fill);
+            if (iterationLimitPerNode > 0) {
+                iterationLimit = iterationLimitPerNode * graph.getNodeCount();
             }
         }
 
         @Override
-        public void remove() {
-            throw new UnsupportedOperationException();
+        public Iterator<Node> iterator() {
+            return new QueueConsumingIterator() {
+                @Override
+                public boolean hasNext() {
+                    dropDeleted();
+                    return iterationLimit > 0 && !worklist.isEmpty();
+                }
+
+                @Override
+                public Node next() {
+                    if (iterationLimit-- <= 0) {
+                        throw new NoSuchElementException();
+                    }
+                    dropDeleted();
+                    Node node = worklist.remove();
+                    assert updateInfiniteWork(node);
+                    if (inQueue != null) {
+                        inQueue.clearAndGrow(node);
+                    }
+                    return node;
+                }
+
+                private boolean updateInfiniteWork(Node node) {
+                    if (lastPull != lastChain) {
+                        firstNoChange = null;
+                    }
+                    lastPull = node;
+                    return true;
+                }
+            };
         }
 
+        @Override
+        public void add(Node node) {
+            if (node != null) {
+                if (inQueue != null) {
+                    if (inQueue.isMarkedAndGrow(node)) {
+                        return;
+                    }
+                } else {
+                    if (worklist.size() > EXPLICIT_BITMAP_THRESHOLD) {
+                        inflateToBitMap(node.graph());
+                    } else {
+                        for (Node queuedNode : worklist) {
+                            if (queuedNode == node) {
+                                return;
+                            }
+                        }
+                    }
+                }
+                assert checkInfiniteWork(node) : "Readded " + node;
+                if (inQueue != null) {
+                    inQueue.markAndGrow(node);
+                }
+                worklist.add(node);
+            }
+        }
+
+        private boolean checkInfiniteWork(Node node) {
+            if (lastPull == node) {
+                if (firstNoChange == null) {
+                    firstNoChange = node;
+                    lastChain = node;
+                } else if (node == firstNoChange) {
+                    return false;
+                } else {
+                    lastChain = node;
+                }
+            } else {
+                firstNoChange = null;
+            }
+            return true;
+        }
+
+        private void inflateToBitMap(Graph graph) {
+            assert inQueue == null;
+            inQueue = graph.createNodeBitMap();
+            for (Node queuedNode : worklist) {
+                if (queuedNode.isAlive()) {
+                    inQueue.mark(queuedNode);
+                }
+            }
+        }
     }
 
-    public Iterable<Node> unmarkedNodes() {
-        return new Iterable<Node>() {
+    public static final class SingletonNodeWorkList extends NodeWorkList {
+        protected final NodeBitMap visited;
 
-            @Override
-            public Iterator<Node> iterator() {
-                return new UnmarkedNodeIterator(visited, visited.graph().getNodes().iterator());
-            }
-        };
-    }
-
-    public static class InfiniteWorkException extends RuntimeException {
-
-        private static final long serialVersionUID = -5319329402219396658L;
-
-        public InfiniteWorkException() {
-            super();
+        public SingletonNodeWorkList(Graph graph) {
+            super(graph, false);
+            visited = graph.createNodeBitMap();
         }
 
-        public InfiniteWorkException(String message) {
-            super(message);
+        @Override
+        public void add(Node node) {
+            if (node != null) {
+                if (!visited.isMarkedAndGrow(node)) {
+                    visited.mark(node);
+                    worklist.add(node);
+                }
+            }
+        }
+
+        @Override
+        public Iterator<Node> iterator() {
+            return new QueueConsumingIterator() {
+                @Override
+                public boolean hasNext() {
+                    dropDeleted();
+                    return !worklist.isEmpty();
+                }
+
+                @Override
+                public Node next() {
+                    dropDeleted();
+                    return worklist.remove();
+                }
+            };
         }
     }
 }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java	Wed May 28 17:20:35 2014 +0200
@@ -66,7 +66,7 @@
     }
 
     public boolean contains(Node n) {
-        return nodes().contains(n);
+        return nodes().isMarkedAndGrow(n);
     }
 
     @SuppressWarnings("unchecked")
@@ -96,7 +96,7 @@
         return original;
     }
 
-    public abstract NodeIterable<Node> nodes();
+    public abstract NodeBitMap nodes();
 
     public StructuredGraph graph() {
         LoopEx l;
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java	Wed May 28 17:20:35 2014 +0200
@@ -102,7 +102,7 @@
     }
 
     @Override
-    public NodeIterable<Node> nodes() {
+    public NodeBitMap nodes() {
         if (nodes == null) {
             LoopFragmentWhole whole = loop().whole();
             whole.nodes(); // init nodes bitmap in whole
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInsideBefore.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInsideBefore.java	Wed May 28 17:20:35 2014 +0200
@@ -23,7 +23,6 @@
 package com.oracle.graal.loop;
 
 import com.oracle.graal.graph.*;
-import com.oracle.graal.graph.iterators.*;
 import com.oracle.graal.nodes.*;
 
 public class LoopFragmentInsideBefore extends LoopFragmentInside {
@@ -51,8 +50,7 @@
     }
 
     @Override
-    public NodeIterable<Node> nodes() {
-        // TODO Auto-generated method stub
+    public NodeBitMap nodes() {
         return null;
     }
 }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInsideFrom.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInsideFrom.java	Wed May 28 17:20:35 2014 +0200
@@ -23,7 +23,6 @@
 package com.oracle.graal.loop;
 
 import com.oracle.graal.graph.*;
-import com.oracle.graal.graph.iterators.*;
 import com.oracle.graal.nodes.*;
 
 public class LoopFragmentInsideFrom extends LoopFragmentInside {
@@ -51,8 +50,7 @@
     }
 
     @Override
-    public NodeIterable<Node> nodes() {
-        // TODO Auto-generated method stub
+    public NodeBitMap nodes() {
         return null;
     }
 }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentWhole.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentWhole.java	Wed May 28 17:20:35 2014 +0200
@@ -25,7 +25,6 @@
 import com.oracle.graal.compiler.common.cfg.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.graph.Graph.DuplicationReplacement;
-import com.oracle.graal.graph.iterators.*;
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.cfg.*;
 
@@ -55,7 +54,7 @@
     }
 
     @Override
-    public NodeIterable<Node> nodes() {
+    public NodeBitMap nodes() {
         if (nodes == null) {
             Loop<Block> lirLoop = loop().lirLoop();
             nodes = LoopFragment.computeNodes(graph(), LoopFragment.toHirBlocks(lirLoop.getBlocks()), LoopFragment.toHirExits(lirLoop.getExits()));
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/CanonicalizerPhase.java	Wed May 28 17:20:35 2014 +0200
@@ -137,9 +137,9 @@
         protected void run(StructuredGraph graph) {
             boolean wholeGraph = newNodesMark == null || newNodesMark.isStart();
             if (initWorkingSet == null) {
-                workList = graph.createNodeWorkList(wholeGraph, MAX_ITERATION_PER_NODE);
+                workList = graph.createIterativeNodeWorkList(wholeGraph, MAX_ITERATION_PER_NODE);
             } else {
-                workList = graph.createNodeWorkList(false, MAX_ITERATION_PER_NODE);
+                workList = graph.createIterativeNodeWorkList(false, MAX_ITERATION_PER_NODE);
                 workList.addAll(initWorkingSet);
             }
             if (!wholeGraph) {
@@ -154,7 +154,7 @@
 
                 @Override
                 public void nodeChanged(Node node) {
-                    workList.addAgain(node);
+                    workList.add(node);
                 }
             };
             graph.trackInputChange(nodeChangedListener);
@@ -336,7 +336,7 @@
                 if (node.inferStamp()) {
                     METRIC_STAMP_CHANGED.increment();
                     for (Node usage : node.usages()) {
-                        workList.addAgain(usage);
+                        workList.add(usage);
                     }
                     return true;
                 }
@@ -373,7 +373,7 @@
 
             @Override
             public void addToWorkList(Node node) {
-                workList.addAgain(node);
+                workList.add(node);
             }
 
             @Override