# HG changeset patch # User Doug Simon # Date 1349710318 -7200 # Node ID d9e47ad2a456d96a8b75aa412afa815dc3f6bd58 # Parent 2e96dc4eb8e226583d4193297879f9bd470dbeda moved classes from com.oracle.graal.util into com.oracle.graal.nodes.util diff -r 2e96dc4eb8e2 -r d9e47ad2a456 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/ComputeImmediateDominator.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/ComputeImmediateDominator.java Mon Oct 08 17:31:58 2012 +0200 @@ -0,0 +1,261 @@ +/* + * 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.*; +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 new GraalInternalError(t).addContext("Could not find a dominator").addContext(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.blockSuccessorCount()) { // 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 (EndNode 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 2e96dc4eb8e2 -r d9e47ad2a456 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodeIterators.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodeIterators.java Mon Oct 08 17:31:58 2012 +0200 @@ -0,0 +1,53 @@ +/* + * 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 AbstractNodeIterable() { + @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 2e96dc4eb8e2 -r d9e47ad2a456 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/TreeIterators.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/TreeIterators.java Mon Oct 08 17:31:58 2012 +0200 @@ -0,0 +1,67 @@ +/* + * 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); + } +} diff -r 2e96dc4eb8e2 -r d9e47ad2a456 graal/com.oracle.graal.nodes/src/com/oracle/graal/util/ComputeImmediateDominator.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/util/ComputeImmediateDominator.java Mon Oct 08 17:30:11 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,261 +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.util; - -import java.util.*; - -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 new GraalInternalError(t).addContext("Could not find a dominator").addContext(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.blockSuccessorCount()) { // 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 (EndNode 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 2e96dc4eb8e2 -r d9e47ad2a456 graal/com.oracle.graal.nodes/src/com/oracle/graal/util/NodeIterators.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/util/NodeIterators.java Mon Oct 08 17:30:11 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,53 +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.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 AbstractNodeIterable() { - @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 2e96dc4eb8e2 -r d9e47ad2a456 graal/com.oracle.graal.nodes/src/com/oracle/graal/util/TreeIterators.java --- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/util/TreeIterators.java Mon Oct 08 17:30:11 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,67 +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.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); - } -} diff -r 2e96dc4eb8e2 -r d9e47ad2a456 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoopSafepointInsertionPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoopSafepointInsertionPhase.java Mon Oct 08 17:30:11 2012 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoopSafepointInsertionPhase.java Mon Oct 08 17:31:58 2012 +0200 @@ -24,8 +24,8 @@ import com.oracle.graal.graph.iterators.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; -import com.oracle.graal.util.*; /** * Adds safepoints to loops.