Mercurial > hg > truffle

changeset 15202:1f130000d700

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Remove NodeIterable.until methods, NodeIterators and TreeIterators
author Gilles Duboscq <duboscq@ssw.jku.at>
date Thu, 17 Apr 2014 13:21:58 +0200
parents e4b64b69e336
children a40e775ecb83
files graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctFilteredNodeIterable.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctPredicatedProxyNodeIterator.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/FilteredNodeIterable.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/PredicatedProxyNodeIterator.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/ComputeImmediateDominator.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodeIterators.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/TreeIterators.java
diffstat 8 files changed, 6 insertions(+), 417 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctFilteredNodeIterable.java	Thu Apr 17 11:25:27 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctFilteredNodeIterable.java	Thu Apr 17 13:21:58 2014 +0200
@@ -39,6 +39,6 @@
 
     @Override
     public Iterator<T> iterator() {
-        return new DistinctPredicatedProxyNodeIterator<>(until, nodeIterable.iterator(), predicate);
+        return new DistinctPredicatedProxyNodeIterator<>(nodeIterable.iterator(), predicate);
     }
 }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctPredicatedProxyNodeIterator.java	Thu Apr 17 11:25:27 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctPredicatedProxyNodeIterator.java	Thu Apr 17 13:21:58 2014 +0200
@@ -30,8 +30,8 @@
 
     private NodeBitMap visited;
 
-    public DistinctPredicatedProxyNodeIterator(NodePredicate until, Iterator<T> iterator, NodePredicate predicate) {
-        super(until, iterator, predicate);
+    public DistinctPredicatedProxyNodeIterator(Iterator<T> iterator, NodePredicate predicate) {
+        super(iterator, predicate);
     }
 
     @Override
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/FilteredNodeIterable.java	Thu Apr 17 11:25:27 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/FilteredNodeIterable.java	Thu Apr 17 13:21:58 2014 +0200
@@ -30,7 +30,6 @@
 
     protected final NodeIterable<T> nodeIterable;
     protected NodePredicate predicate = NodePredicates.alwaysTrue();
-    protected NodePredicate until = NodePredicates.isNull();
 
     public FilteredNodeIterable(NodeIterable<T> nodeIterable) {
         this.nodeIterable = nodeIterable;
@@ -47,18 +46,6 @@
     }
 
     @Override
-    public NodeIterable<T> until(final T u) {
-        until = until.or(NodePredicates.equals(u));
-        return this;
-    }
-
-    @Override
-    public NodeIterable<T> until(final Class<? extends T> clazz) {
-        until = until.or(NodePredicates.isA(clazz));
-        return this;
-    }
-
-    @Override
     public FilteredNodeIterable<T> nonNull() {
         this.predicate = this.predicate.and(NodePredicates.isNotNull());
         return this;
@@ -68,13 +55,12 @@
     public DistinctFilteredNodeIterable<T> distinct() {
         DistinctFilteredNodeIterable<T> distinct = new DistinctFilteredNodeIterable<>(nodeIterable);
         distinct.predicate = predicate;
-        distinct.until = until;
         return distinct;
     }
 
     @Override
     public Iterator<T> iterator() {
-        return new PredicatedProxyNodeIterator<>(until, nodeIterable.iterator(), predicate);
+        return new PredicatedProxyNodeIterator<>(nodeIterable.iterator(), predicate);
     }
 
     @SuppressWarnings("unchecked")
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java	Thu Apr 17 11:25:27 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java	Thu Apr 17 13:21:58 2014 +0200
@@ -28,14 +28,6 @@
 
 public interface NodeIterable<T extends Node> extends Iterable<T> {
 
-    default NodeIterable<T> until(final T u) {
-        return new FilteredNodeIterable<>(this).until(u);
-    }
-
-    default NodeIterable<T> until(final Class<? extends T> clazz) {
-        return new FilteredNodeIterable<>(this).until(clazz);
-    }
-
     @SuppressWarnings("unchecked")
     default <F extends T> NodeIterable<F> filter(Class<F> clazz) {
         return (NodeIterable<F>) new FilteredNodeIterable<>(this).and(NodePredicates.isA(clazz));
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/PredicatedProxyNodeIterator.java	Thu Apr 17 11:25:27 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/PredicatedProxyNodeIterator.java	Thu Apr 17 13:21:58 2014 +0200
@@ -30,10 +30,8 @@
 
     private final Iterator<T> iterator;
     private final NodePredicate predicate;
-    private final NodePredicate until;
 
-    public PredicatedProxyNodeIterator(NodePredicate until, Iterator<T> iterator, NodePredicate predicate) {
-        this.until = until;
+    public PredicatedProxyNodeIterator(Iterator<T> iterator, NodePredicate predicate) {
         this.iterator = iterator;
         this.predicate = predicate;
     }
@@ -43,7 +41,7 @@
         while ((current == null || !current.isAlive() || !predicate.apply(current)) && iterator.hasNext()) {
             current = iterator.next();
         }
-        if (current != null && (!current.isAlive() || !predicate.apply(current) || until.apply(current))) {
+        if (current != null && (!current.isAlive() || !predicate.apply(current))) {
             current = null;
         }
     }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/ComputeImmediateDominator.java	Thu Apr 17 11:25:27 2014 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,263 +0,0 @@
-/*
- * Copyright (c) 2011, 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.nodes.util;
-
-import java.util.*;
-
-import com.oracle.graal.compiler.common.*;
-import com.oracle.graal.graph.*;
-import com.oracle.graal.nodes.*;
-
-public final class ComputeImmediateDominator {
-
-    private final MergeNode dominated;
-    private final Queue<FixedNode> toExplore;
-    private final Queue<FixedNode> speculativeExplore;
-    private final NodeMap<DominatorInfo> infoMap;
-    private final DominatorInfo fullInfo;
-    private FixedNode dominator;
-    private int nextBit = 1;
-
-    public ComputeImmediateDominator(MergeNode dominated) {
-        this.dominated = dominated;
-        this.toExplore = new LinkedList<>();
-        this.speculativeExplore = new LinkedList<>();
-        this.infoMap = dominated.graph().createNodeMap();
-        fullInfo = new DominatorInfo(dominated, true);
-
-        this.processMerge(dominated, fullInfo);
-        if (toExplore.size() == 1) {
-            dominator = toExplore.remove();
-        }
-    }
-
-    public FixedNode compute() {
-        try {
-            while (dominator == null && (!toExplore.isEmpty() || !speculativeExplore.isEmpty())) {
-                while (!toExplore.isEmpty()) {
-                    exploreUp(toExplore.remove());
-                    if (dominator != null) {
-                        return dominator;
-                    }
-                }
-                exploreUp(speculativeExplore.remove());
-            }
-            return dominator;
-        } catch (Throwable t) {
-            throw GraalGraphInternalError.transformAndAddContext(new GraalInternalError(t).addContext("Could not find a dominator"), dominated);
-        }
-    }
-
-    private void exploreUp(FixedNode from) {
-        FixedNode p = from;
-        DominatorInfo info = infoMap.get(from);
-        if (info.isExplored()) {
-            return;
-        }
-        // TTY.println("exploreUp(" + from + ") with " + info);
-        info.setExplored();
-        while (p != null) {
-            if (p instanceof MergeNode) {
-                processMerge((MergeNode) p, info);
-                p = null;
-            } else if (p instanceof ControlSplitNode) {
-                processControlSplit((ControlSplitNode) p, info);
-                p = null;
-            } else {
-                p = (FixedNode) p.predecessor();
-            }
-        }
-    }
-
-    private void processControlSplit(ControlSplitNode cs, DominatorInfo info) {
-        // TTY.println("processControlSplit(" + cs + ", " + info + ")");
-        DominatorInfo csInfo = infoMap.get(cs);
-        if (csInfo == null) {
-            csInfo = new DominatorInfo(cs, false);
-            infoMap.set(cs, csInfo);
-        }
-        csInfo.add(info);
-        FixedNode next = (FixedNode) cs.predecessor();
-        if (checkControlSplitInfo(csInfo)) {
-            return;
-        }
-        if (csInfo.isExplored()) {
-            // TTY.println("  Already explored, propagate update");
-            propagateUpdate(csInfo);
-        } else {
-            if (csInfo.parentCount() == cs.successors().count()) { // all paths leading to this CS
-                                                                   // have been explored
-                // TTY.println("  All parents explored, Enqueue");
-                toExplore.add(next);
-                speculativeExplore.remove(next);
-            } else {
-                // TTY.println("  Not all parents explored : Enqueue speculative");
-                speculativeExplore.add(next);
-            }
-        }
-        infoMap.set(next, csInfo);
-    }
-
-    private boolean propagateUpdate(DominatorInfo di) {
-        // TTY.println("   propagateUpdate(" + di + ")");
-        for (DominatorInfo child : di.children()) {
-            // TTY.println("      add to child " + child);
-            if (child.add(di, false)) {
-                if (child.equals(fullInfo)) {
-                    // TTY.println("   Found DOM!");
-                    dominator = child.node();
-                    return true;
-                }
-                if (propagateUpdate(child)) {
-                    return true;
-                }
-            }
-        }
-        return false;
-    }
-
-    private boolean checkControlSplitInfo(DominatorInfo di) {
-        // TTY.println("   checkControlSplitInfo(" + di + ")");
-        if (di.equals(fullInfo)) {
-            dominator = di.node();
-            // TTY.println("   Found DOM!");
-            return true;
-        }
-        return false;
-    }
-
-    private void processMerge(MergeNode merge, DominatorInfo info) {
-        // TTY.println("processMerge(" + merge + ", " + info + ")");
-        for (AbstractEndNode end : merge.cfgPredecessors()) {
-            toExplore.add(end);
-            infoMap.set(end, info.createChild(end));
-            // TTY.println("  Enqueue end : " + end + " with " + infoMap.get(end));
-        }
-    }
-
-    private class DominatorInfo {
-
-        private final FixedNode node;
-        private final BitSet bits;
-        private final BitSet ownBits;
-        private final Collection<DominatorInfo> children;
-        private final Collection<DominatorInfo> parents;
-        private boolean explored;
-
-        public DominatorInfo(FixedNode node, boolean full) {
-            this.node = node;
-            this.bits = new BitSet();
-            this.ownBits = new BitSet();
-            this.children = new ArrayList<>(2);
-            this.parents = new ArrayList<>(2);
-            if (full) {
-                addOwnBits(0);
-            }
-        }
-
-        public boolean isExplored() {
-            return explored;
-        }
-
-        public void setExplored() {
-            explored = true;
-        }
-
-        public DominatorInfo createChild(FixedNode childNode) {
-            DominatorInfo di = new DominatorInfo(childNode, false);
-            di.bits.or(bits);
-            di.ownBits.or(ownBits);
-            if (!children.isEmpty() || di.ownBits.isEmpty()) {
-                int newBit = nextBit++;
-                di.bits.xor(ownBits);
-                di.bits.set(newBit);
-                di.ownBits.clear();
-                di.ownBits.set(newBit);
-                addOwnBits(newBit);
-            }
-            children.add(di);
-            di.parents.add(this);
-            return di;
-        }
-
-        private void addOwnBits(int newBit) {
-            if (!bits.get(newBit)) {
-                ownBits.set(newBit);
-                bits.set(newBit);
-                for (DominatorInfo parent : parents) {
-                    parent.addOwnBits(newBit);
-                }
-            }
-        }
-
-        public boolean add(DominatorInfo i) {
-            return add(i, true);
-        }
-
-        public boolean add(DominatorInfo i, boolean addParent) {
-            boolean ret = true;
-            if (addParent) {
-                parents.add(i);
-                i.children.add(this);
-                bits.or(i.bits);
-            } else {
-                BitSet newBits = (BitSet) i.bits.clone();
-                newBits.andNot(bits);
-                newBits.andNot(i.ownBits);
-                ret = !newBits.isEmpty();
-                bits.or(newBits);
-            }
-            return ret;
-        }
-
-        public int parentCount() {
-            return parents.size();
-        }
-
-        public FixedNode node() {
-            return node;
-        }
-
-        public Collection<DominatorInfo> children() {
-            return children;
-        }
-
-        @Override
-        public boolean equals(Object obj) {
-            if (!(obj instanceof DominatorInfo)) {
-                return false;
-            }
-            return ((DominatorInfo) obj).bits.equals(bits);
-        }
-
-        @Override
-        public String toString() {
-            return bits + " (o" + ownBits + ") " + node;
-        }
-
-        @Override
-        public int hashCode() {
-            return bits.hashCode();
-        }
-    }
-}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodeIterators.java	Thu Apr 17 11:25:27 2014 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,56 +0,0 @@
-/*
- * Copyright (c) 2011, 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.nodes.util;
-
-import java.util.*;
-
-import com.oracle.graal.graph.iterators.*;
-import com.oracle.graal.nodes.*;
-
-public class NodeIterators {
-
-    public static NodeIterable<FixedNode> dominators(final FixedNode n) {
-        return new NodeIterable<FixedNode>() {
-
-            @Override
-            public Iterator<FixedNode> iterator() {
-                return new NodeIterator<FixedNode>() {
-
-                    FixedNode p = n;
-
-                    @Override
-                    protected void forward() {
-                        if (current == null) {
-                            if (p instanceof MergeNode) {
-                                current = new ComputeImmediateDominator((MergeNode) p).compute();
-                            } else {
-                                current = (FixedNode) p.predecessor();
-                            }
-                            p = current;
-                        }
-                    }
-                };
-            }
-        };
-    }
-}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/TreeIterators.java	Thu Apr 17 11:25:27 2014 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,68 +0,0 @@
-/*
- * Copyright (c) 2011, 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.nodes.util;
-
-import java.util.*;
-
-public class TreeIterators {
-
-    public abstract static class PrefixTreeIterator<T> implements Iterator<T> {
-
-        private Deque<T> stack = new LinkedList<>();
-
-        public PrefixTreeIterator(T root) {
-            stack.push(root);
-        }
-
-        public PrefixTreeIterator(Iterable<T> roots) {
-            for (T root : roots) {
-                stack.addLast(root);
-            }
-        }
-
-        @Override
-        public boolean hasNext() {
-            return !stack.isEmpty();
-        }
-
-        @Override
-        public T next() {
-            T top = stack.pop();
-            LinkedList<T> list = new LinkedList<>();
-            for (T child : children(top)) {
-                list.addFirst(child);
-            }
-            for (T child : list) {
-                stack.push(child);
-            }
-            return top;
-        }
-
-        @Override
-        public void remove() {
-            throw new UnsupportedOperationException();
-        }
-
-        protected abstract Iterable<T> children(T node);
-    }
-}