# HG changeset patch # User Gilles Duboscq # Date 1397733718 -7200 # Node ID 1f130000d7003d2072f5287096b90cf183360ca8 # Parent e4b64b69e336225ad14ab6d1eb3b1968899d62c5 Remove NodeIterable.until methods, NodeIterators and TreeIterators diff -r e4b64b69e336 -r 1f130000d700 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctFilteredNodeIterable.java --- 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 iterator() { - return new DistinctPredicatedProxyNodeIterator<>(until, nodeIterable.iterator(), predicate); + return new DistinctPredicatedProxyNodeIterator<>(nodeIterable.iterator(), predicate); } } diff -r e4b64b69e336 -r 1f130000d700 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctPredicatedProxyNodeIterator.java --- 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 iterator, NodePredicate predicate) { - super(until, iterator, predicate); + public DistinctPredicatedProxyNodeIterator(Iterator iterator, NodePredicate predicate) { + super(iterator, predicate); } @Override diff -r e4b64b69e336 -r 1f130000d700 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/FilteredNodeIterable.java --- 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 nodeIterable; protected NodePredicate predicate = NodePredicates.alwaysTrue(); - protected NodePredicate until = NodePredicates.isNull(); public FilteredNodeIterable(NodeIterable nodeIterable) { this.nodeIterable = nodeIterable; @@ -47,18 +46,6 @@ } @Override - public NodeIterable until(final T u) { - until = until.or(NodePredicates.equals(u)); - return this; - } - - @Override - public NodeIterable until(final Class clazz) { - until = until.or(NodePredicates.isA(clazz)); - return this; - } - - @Override public FilteredNodeIterable nonNull() { this.predicate = this.predicate.and(NodePredicates.isNotNull()); return this; @@ -68,13 +55,12 @@ public DistinctFilteredNodeIterable distinct() { DistinctFilteredNodeIterable distinct = new DistinctFilteredNodeIterable<>(nodeIterable); distinct.predicate = predicate; - distinct.until = until; return distinct; } @Override public Iterator iterator() { - return new PredicatedProxyNodeIterator<>(until, nodeIterable.iterator(), predicate); + return new PredicatedProxyNodeIterator<>(nodeIterable.iterator(), predicate); } @SuppressWarnings("unchecked") diff -r e4b64b69e336 -r 1f130000d700 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/NodeIterable.java --- 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 extends Iterable { - default NodeIterable until(final T u) { - return new FilteredNodeIterable<>(this).until(u); - } - - default NodeIterable until(final Class clazz) { - return new FilteredNodeIterable<>(this).until(clazz); - } - @SuppressWarnings("unchecked") default NodeIterable filter(Class clazz) { return (NodeIterable) new FilteredNodeIterable<>(this).and(NodePredicates.isA(clazz)); diff -r e4b64b69e336 -r 1f130000d700 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/PredicatedProxyNodeIterator.java --- 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 iterator; private final NodePredicate predicate; - private final NodePredicate until; - public PredicatedProxyNodeIterator(NodePredicate until, Iterator iterator, NodePredicate predicate) { - this.until = until; + public PredicatedProxyNodeIterator(Iterator 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; } } diff -r e4b64b69e336 -r 1f130000d700 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/ComputeImmediateDominator.java --- 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 toExplore; - private final Queue speculativeExplore; - private final NodeMap 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 children; - private final Collection 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 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(); - } - } -} diff -r e4b64b69e336 -r 1f130000d700 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodeIterators.java --- 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 dominators(final FixedNode n) { - return new NodeIterable() { - - @Override - public Iterator iterator() { - return new NodeIterator() { - - 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; - } - } - }; - } - }; - } -} diff -r e4b64b69e336 -r 1f130000d700 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/TreeIterators.java --- 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 implements Iterator { - - private Deque stack = new LinkedList<>(); - - public PrefixTreeIterator(T root) { - stack.push(root); - } - - public PrefixTreeIterator(Iterable roots) { - for (T root : roots) { - stack.addLast(root); - } - } - - @Override - public boolean hasNext() { - return !stack.isEmpty(); - } - - @Override - public T next() { - T top = stack.pop(); - LinkedList 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 children(T node); - } -}