changeset 9809:a8a5d5832def

first step towards extensibility of the escape analysis phase
author Lukas Stadler <lukas.stadler@jku.at>
date Fri, 17 May 2013 16:47:13 +0200
parents 12fdb8fe0a35
children b49fdcee6cb0
files graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualUtil.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java
diffstat 8 files changed, 216 insertions(+), 141 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java	Fri May 17 15:41:39 2013 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java	Fri May 17 16:47:13 2013 +0200
@@ -37,6 +37,8 @@
 
     public abstract static class BlockIteratorClosure<StateT> {
 
+        protected abstract StateT getInitialState();
+
         protected abstract StateT processBlock(Block block, StateT currentState);
 
         protected abstract StateT merge(Block merge, List<StateT> states);
@@ -70,7 +72,11 @@
         return info;
     }
 
-    public static <StateT> IdentityHashMap<FixedNode, StateT> apply(BlockIteratorClosure<StateT> closure, Block start, StateT initialState, Set<Block> boundary) {
+    public static <StateT> void apply(BlockIteratorClosure<StateT> closure, Block start) {
+        apply(closure, start, closure.getInitialState(), null);
+    }
+
+    private static <StateT> IdentityHashMap<FixedNode, StateT> apply(BlockIteratorClosure<StateT> closure, Block start, StateT initialState, Set<Block> boundary) {
         Deque<Block> blockQueue = new ArrayDeque<>();
         /*
          * States are stored on EndNodes before merges, and on BeginNodes after ControlSplitNodes.
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Fri May 17 15:41:39 2013 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/schedule/SchedulePhase.java	Fri May 17 16:47:13 2013 +0200
@@ -84,6 +84,11 @@
     private class MemoryScheduleClosure extends BlockIteratorClosure<HashSet<FloatingReadNode>> {
 
         @Override
+        protected HashSet<FloatingReadNode> getInitialState() {
+            return new HashSet<>();
+        }
+
+        @Override
         protected HashSet<FloatingReadNode> processBlock(Block block, HashSet<FloatingReadNode> currentState) {
             for (Node node : getBlockToNodesMap().get(block)) {
                 if (node instanceof FloatingReadNode) {
@@ -184,7 +189,7 @@
             sortNodesWithinBlocks(graph, SchedulingStrategy.EARLIEST);
 
             MemoryScheduleClosure closure = new MemoryScheduleClosure();
-            ReentrantBlockIterator.apply(closure, getCFG().getStartBlock(), new HashSet<FloatingReadNode>(), null);
+            ReentrantBlockIterator.apply(closure, getCFG().getStartBlock());
 
             cfg.clearNodeToBlock();
             blockToNodesMap = new BlockMap<>(cfg);
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java	Fri May 17 15:41:39 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java	Fri May 17 16:47:13 2013 +0200
@@ -22,8 +22,6 @@
  */
 package com.oracle.graal.virtual.phases.ea;
 
-import static com.oracle.graal.virtual.phases.ea.PartialEscapeAnalysisPhase.*;
-
 import java.util.*;
 
 import com.oracle.graal.api.meta.*;
@@ -159,7 +157,7 @@
 
     private void materializeWithCommit(FixedNode fixed, VirtualObjectNode virtual, List<AllocatedObjectNode> objects, List<int[]> locks, List<ValueNode> values, List<ValueNode> otherAllocations,
                     EscapeState state) {
-        trace("materializing %s", virtual);
+        VirtualUtil.trace("materializing %s", virtual);
         ObjectState obj = getObjectState(virtual);
 
         ValueNode[] entries = obj.getEntries();
@@ -241,29 +239,34 @@
         return objectStates + " " + readCache;
     }
 
-    public static BlockState meetAliases(List<BlockState> states) {
+    public BlockState meetAliases(List<? extends BlockState> states) {
         BlockState newState = new BlockState();
 
-        newState.objectAliases.putAll(states.get(0).objectAliases);
+        BlockState firstState = states.get(0);
+        newState.objectAliases.putAll(firstState.objectAliases);
         for (int i = 1; i < states.size(); i++) {
             BlockState state = states.get(i);
-            for (Map.Entry<ValueNode, VirtualObjectNode> entry : states.get(0).objectAliases.entrySet()) {
+            Iterator<Map.Entry<ValueNode, VirtualObjectNode>> iter = newState.objectAliases.entrySet().iterator();
+            while (iter.hasNext()) {
+                Map.Entry<ValueNode, VirtualObjectNode> entry = iter.next();
                 if (state.objectAliases.containsKey(entry.getKey())) {
                     assert state.objectAliases.get(entry.getKey()) == entry.getValue();
                 } else {
-                    newState.objectAliases.remove(entry.getKey());
+                    iter.remove();
                 }
             }
         }
 
-        newState.scalarAliases.putAll(states.get(0).scalarAliases);
+        newState.scalarAliases.putAll(firstState.scalarAliases);
         for (int i = 1; i < states.size(); i++) {
             BlockState state = states.get(i);
-            for (Map.Entry<ValueNode, ValueNode> entry : states.get(0).scalarAliases.entrySet()) {
+            Iterator<Map.Entry<ValueNode, ValueNode>> iter = newState.scalarAliases.entrySet().iterator();
+            while (iter.hasNext()) {
+                Map.Entry<ValueNode, ValueNode> entry = iter.next();
                 if (state.scalarAliases.containsKey(entry.getKey())) {
                     assert state.scalarAliases.get(entry.getKey()) == entry.getValue();
                 } else {
-                    newState.scalarAliases.remove(entry.getKey());
+                    iter.remove();
                 }
             }
         }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java	Fri May 17 15:41:39 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java	Fri May 17 16:47:13 2013 +0200
@@ -215,7 +215,7 @@
                 FixedNode next = node.next();
                 node.setNext(null);
                 node.replaceAtPredecessor(next);
-                obsoleteNodes.add(node);
+                assert obsoleteNodes.add(node);
             }
         });
     }
@@ -250,7 +250,7 @@
                     FixedNode next = ((FixedWithNextNode) node).next();
                     ((FixedWithNextNode) node).setNext(null);
                     node.replaceAtPredecessor(next);
-                    obsoleteNodes.add(node);
+                    assert obsoleteNodes.add(node);
                 }
             }
         });
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java	Fri May 17 15:41:39 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java	Fri May 17 16:47:13 2013 +0200
@@ -25,7 +25,6 @@
 import java.util.*;
 import java.util.concurrent.*;
 
-import com.oracle.graal.api.meta.*;
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
@@ -42,6 +41,13 @@
 
 public class PartialEscapeAnalysisPhase extends BasePhase<HighTierContext> {
 
+    public abstract static class Closure<T> extends ReentrantBlockIterator.BlockIteratorClosure<T> {
+
+        public abstract boolean hasChanged();
+
+        public abstract void applyEffects();
+    }
+
     private final CustomCanonicalizer customCanonicalizer;
     private final boolean iterative;
     private final boolean readElimination;
@@ -56,26 +62,20 @@
         this.readElimination = readElimination;
     }
 
-    public static final void trace(String format, Object... obj) {
-        if (GraalOptions.TraceEscapeAnalysis) {
-            Debug.log(format, obj);
-        }
-    }
-
     @Override
     protected void run(StructuredGraph graph, HighTierContext context) {
         runAnalysis(graph, context);
     }
 
     public boolean runAnalysis(final StructuredGraph graph, final HighTierContext context) {
-        if (!matches(graph, GraalOptions.EscapeAnalyzeOnly)) {
+        if (!VirtualUtil.matches(graph, GraalOptions.EscapeAnalyzeOnly)) {
             return false;
         }
 
         if (!readElimination) {
             boolean analyzableNodes = false;
             for (Node node : graph.getNodes()) {
-                if (node instanceof VirtualizableRoot) {
+                if (node instanceof VirtualizableAllocation) {
                     analyzableNodes = true;
                     break;
                 }
@@ -95,18 +95,17 @@
 
                     SchedulePhase schedule = new SchedulePhase();
                     schedule.apply(graph, false);
-                    PartialEscapeClosure closure = new PartialEscapeClosure(graph.createNodeBitMap(), schedule, context.getRuntime(), context.getAssumptions());
-                    ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock(), new BlockState(), null);
+                    Closure<?> closure = createAnalysisClosure(context, schedule);
+                    ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock());
 
                     if (!closure.hasChanged()) {
                         return false;
                     }
 
                     // apply the effects collected during the escape analysis iteration
-                    List<Node> obsoleteNodes = closure.applyEffects(graph);
+                    closure.applyEffects();
 
                     Debug.dump(graph, "after PartialEscapeAnalysis iteration");
-                    assert noObsoleteNodes(graph, obsoleteNodes);
 
                     new DeadCodeEliminationPhase().apply(graph);
 
@@ -124,85 +123,8 @@
         return changed;
     }
 
-    private static boolean matches(StructuredGraph graph, String filter) {
-        if (filter != null) {
-            if (filter.startsWith("~")) {
-                ResolvedJavaMethod method = graph.method();
-                return method == null || !MetaUtil.format("%H.%n", method).contains(filter.substring(1));
-            } else {
-                ResolvedJavaMethod method = graph.method();
-                return method != null && MetaUtil.format("%H.%n", method).contains(filter);
-            }
-        }
-        return true;
-    }
-
-    static boolean noObsoleteNodes(StructuredGraph graph, List<Node> obsoleteNodes) {
-        // helper code that determines the paths that keep obsolete nodes alive:
-
-        NodeFlood flood = graph.createNodeFlood();
-        IdentityHashMap<Node, Node> path = new IdentityHashMap<>();
-        flood.add(graph.start());
-        for (Node current : flood) {
-            if (current instanceof AbstractEndNode) {
-                AbstractEndNode end = (AbstractEndNode) current;
-                flood.add(end.merge());
-                if (!path.containsKey(end.merge())) {
-                    path.put(end.merge(), end);
-                }
-            } else {
-                for (Node successor : current.successors()) {
-                    flood.add(successor);
-                    if (!path.containsKey(successor)) {
-                        path.put(successor, current);
-                    }
-                }
-            }
-        }
-
-        for (Node node : obsoleteNodes) {
-            if (node instanceof FixedNode) {
-                assert !flood.isMarked(node) : node;
-            }
-        }
-
-        for (Node node : graph.getNodes()) {
-            if (node instanceof LocalNode) {
-                flood.add(node);
-            }
-            if (flood.isMarked(node)) {
-                for (Node input : node.inputs()) {
-                    flood.add(input);
-                    if (!path.containsKey(input)) {
-                        path.put(input, node);
-                    }
-                }
-            }
-        }
-        for (Node current : flood) {
-            for (Node input : current.inputs()) {
-                flood.add(input);
-                if (!path.containsKey(input)) {
-                    path.put(input, current);
-                }
-            }
-        }
-        boolean success = true;
-        for (Node node : obsoleteNodes) {
-            if (flood.isMarked(node)) {
-                TTY.print("offending node path:");
-                Node current = node;
-                while (current != null) {
-                    TTY.println(current.toString());
-                    current = path.get(current);
-                    if (current != null && current instanceof FixedNode && !obsoleteNodes.contains(current)) {
-                        break;
-                    }
-                }
-                success = false;
-            }
-        }
-        return success;
+    protected Closure<?> createAnalysisClosure(final HighTierContext context, SchedulePhase schedule) {
+        return new PartialEscapeClosure<>(schedule, context.getRuntime(), context.getAssumptions());
     }
 
     public static Map<Invoke, Double> getHints(StructuredGraph graph) {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Fri May 17 15:41:39 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Fri May 17 16:47:13 2013 +0200
@@ -22,8 +22,6 @@
  */
 package com.oracle.graal.virtual.phases.ea;
 
-import static com.oracle.graal.virtual.phases.ea.PartialEscapeAnalysisPhase.*;
-
 import java.util.*;
 
 import com.oracle.graal.api.code.*;
@@ -34,8 +32,8 @@
 import com.oracle.graal.nodes.PhiNode.PhiType;
 import com.oracle.graal.nodes.VirtualState.NodeClosure;
 import com.oracle.graal.nodes.cfg.*;
+import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.nodes.extended.LocationNode.LocationIdentity;
-import com.oracle.graal.nodes.extended.*;
 import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.spi.Virtualizable.EscapeState;
@@ -49,7 +47,7 @@
 import com.oracle.graal.virtual.phases.ea.BlockState.ReadCacheEntry;
 import com.oracle.graal.virtual.phases.ea.EffectList.Effect;
 
-class PartialEscapeClosure extends BlockIteratorClosure<BlockState> {
+class PartialEscapeClosure<BlockT extends BlockState> extends PartialEscapeAnalysisPhase.Closure<BlockT> {
 
     public static final DebugMetric METRIC_MATERIALIZATIONS = Debug.metric("Materializations");
     public static final DebugMetric METRIC_MATERIALIZATIONS_PHI = Debug.metric("MaterializationsPhi");
@@ -73,8 +71,8 @@
 
     private boolean changed;
 
-    public PartialEscapeClosure(NodeBitMap usages, SchedulePhase schedule, MetaAccessProvider metaAccess, Assumptions assumptions) {
-        this.usages = usages;
+    public PartialEscapeClosure(SchedulePhase schedule, MetaAccessProvider metaAccess, Assumptions assumptions) {
+        this.usages = schedule.getCFG().graph.createNodeBitMap();
         this.schedule = schedule;
         this.tool = new VirtualizerToolImpl(usages, metaAccess, assumptions);
         this.blockEffects = new BlockMap<>(schedule.getCFG());
@@ -83,14 +81,28 @@
         }
     }
 
+    @SuppressWarnings("unchecked")
+    @Override
+    protected BlockT getInitialState() {
+        return (BlockT) new BlockState();
+    }
+
+    @Override
     public boolean hasChanged() {
         return changed;
     }
 
-    public List<Node> applyEffects(final StructuredGraph graph) {
-        final ArrayList<Node> obsoleteNodes = new ArrayList<>();
+    @Override
+    public void applyEffects() {
+        final StructuredGraph graph = schedule.getCFG().graph;
+        final ArrayList<Node> obsoleteNodes = new ArrayList<>(0);
         BlockIteratorClosure<Void> closure = new BlockIteratorClosure<Void>() {
 
+            @Override
+            protected Void getInitialState() {
+                return null;
+            }
+
             private void apply(GraphEffectList effects, Object context) {
                 if (!effects.isEmpty()) {
                     Debug.log(" ==== effects for %s", context);
@@ -126,8 +138,8 @@
                 return info.exitStates;
             }
         };
-        ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock(), null, null);
-        return obsoleteNodes;
+        ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock());
+        assert VirtualUtil.assertNonReachable(graph, obsoleteNodes);
     }
 
     public Map<Invoke, Double> getHints() {
@@ -135,11 +147,11 @@
     }
 
     @Override
-    protected BlockState processBlock(Block block, BlockState state) {
+    protected BlockT processBlock(Block block, BlockT state) {
         GraphEffectList effects = blockEffects.get(block);
         tool.setEffects(effects);
 
-        trace("\nBlock: %s (", block);
+        VirtualUtil.trace("\nBlock: %s (", block);
         List<ScheduledNode> nodeList = schedule.getBlockToNodesMap().get(block);
 
         FixedWithNextNode lastFixedNode = null;
@@ -147,11 +159,11 @@
             boolean deleted;
             boolean isMarked = usages.isMarked(node);
             if (isMarked || node instanceof VirtualizableRoot) {
-                trace("[[%s]] ", node);
+                VirtualUtil.trace("[[%s]] ", node);
                 FixedNode nextFixedNode = lastFixedNode == null ? null : lastFixedNode.next();
                 deleted = processNode((ValueNode) node, nextFixedNode, state, effects, isMarked);
             } else {
-                trace("%s ", node);
+                VirtualUtil.trace("%s ", node);
                 deleted = false;
             }
             if (GraalOptions.OptEarlyReadElimination) {
@@ -171,11 +183,11 @@
                 lastFixedNode = (FixedWithNextNode) node;
             }
         }
-        trace(")\n    end state: %s\n", state);
+        VirtualUtil.trace(")\n    end state: %s\n", state);
         return state;
     }
 
-    private boolean processNode(final ValueNode node, FixedNode insertBefore, final BlockState state, final GraphEffectList effects, boolean isMarked) {
+    private boolean processNode(final ValueNode node, FixedNode insertBefore, final BlockT state, final GraphEffectList effects, boolean isMarked) {
         tool.reset(state, node, insertBefore);
         if (node instanceof Virtualizable) {
             ((Virtualizable) node).virtualize(tool);
@@ -268,7 +280,7 @@
                         Invoke invoke = ((MethodCallTargetNode) node).invoke();
                         hints.put(invoke, 5d);
                     }
-                    trace("replacing input %s at %s: %s", input, node, obj);
+                    VirtualUtil.trace("replacing input %s at %s: %s", input, node, obj);
                     replaceWithMaterialized(input, node, insertBefore, state, obj, effects, METRIC_MATERIALIZATIONS_UNHANDLED);
                 }
             }
@@ -293,9 +305,9 @@
     }
 
     @Override
-    protected BlockState merge(Block merge, List<BlockState> states) {
+    protected BlockT merge(Block merge, List<BlockT> states) {
         assert blockEffects.get(merge).isEmpty();
-        MergeProcessor processor = new MergeProcessor(merge, usages, blockEffects);
+        MergeProcessor<BlockT> processor = new MergeProcessor<>(merge, usages, blockEffects);
         processor.merge(states);
         blockEffects.get(merge).addAll(processor.mergeEffects);
         blockEffects.get(merge).addAll(processor.afterMergeEffects);
@@ -303,20 +315,22 @@
 
     }
 
+    @SuppressWarnings("unchecked")
     @Override
-    protected BlockState cloneState(BlockState oldState) {
-        return oldState.cloneState();
+    protected BlockT cloneState(BlockState oldState) {
+        return (BlockT) oldState.cloneState();
     }
 
     @Override
-    protected List<BlockState> processLoop(Loop loop, BlockState initialState) {
+    protected List<BlockT> processLoop(Loop loop, BlockT initialState) {
         BlockState loopEntryState = initialState;
         BlockState lastMergedState = initialState;
-        MergeProcessor mergeProcessor = new MergeProcessor(loop.header, usages, blockEffects);
+        MergeProcessor<BlockT> mergeProcessor = new MergeProcessor<>(loop.header, usages, blockEffects);
         for (int iteration = 0; iteration < 10; iteration++) {
-            LoopInfo<BlockState> info = ReentrantBlockIterator.processLoop(this, loop, lastMergedState.cloneState());
+            @SuppressWarnings("unchecked")
+            LoopInfo<BlockT> info = ReentrantBlockIterator.processLoop(this, loop, (BlockT) lastMergedState.cloneState());
 
-            List<BlockState> states = new ArrayList<>();
+            List<BlockT> states = new ArrayList<>();
             states.add(initialState);
             states.addAll(info.endStates);
             mergeProcessor.merge(states);
@@ -399,7 +413,7 @@
         }
     }
 
-    private static class MergeProcessor {
+    private static class MergeProcessor<BlockT extends BlockState> {
 
         private final Block mergeBlock;
         private final MergeNode merge;
@@ -412,7 +426,7 @@
         private final IdentityHashMap<VirtualObjectNode, PhiNode[]> valuePhis = new IdentityHashMap<>();
         private final IdentityHashMap<PhiNode, PhiNode[]> valueObjectMergePhis = new IdentityHashMap<>();
         private final IdentityHashMap<PhiNode, VirtualObjectNode> valueObjectVirtuals = new IdentityHashMap<>();
-        private BlockState newState;
+        private BlockT newState;
 
         public MergeProcessor(Block mergeBlock, NodeBitMap usages, BlockMap<GraphEffectList> blockEffects) {
             this.usages = usages;
@@ -459,8 +473,9 @@
             return result;
         }
 
-        private void merge(List<BlockState> states) {
-            newState = BlockState.meetAliases(states);
+        @SuppressWarnings("unchecked")
+        private void merge(List<BlockT> states) {
+            newState = (BlockT) states.get(0).meetAliases(states);
 
             /*
              * Iterative processing: Merging the materialized/virtual state of virtual objects can
@@ -559,7 +574,7 @@
             mergeReadCache(states);
         }
 
-        private boolean processPhi(PhiNode phi, List<BlockState> states) {
+        private boolean processPhi(PhiNode phi, List<BlockT> states) {
             assert states.size() == phi.valueCount();
             int virtualInputs = 0;
             boolean materialized = false;
@@ -643,7 +658,7 @@
             return materialized;
         }
 
-        private void mergeReadCache(List<BlockState> states) {
+        private void mergeReadCache(List<BlockT> states) {
             for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
                 ReadCacheEntry key = entry.getKey();
                 ValueNode value = entry.getValue();
@@ -682,7 +697,7 @@
             }
         }
 
-        private void mergeReadCachePhi(PhiNode phi, ResolvedJavaField identity, List<BlockState> states) {
+        private void mergeReadCachePhi(PhiNode phi, ResolvedJavaField identity, List<BlockT> states) {
             ValueNode[] values = new ValueNode[phi.valueCount()];
             for (int i = 0; i < phi.valueCount(); i++) {
                 ValueNode value = states.get(i).getReadCache(phi.valueAt(i), identity);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualUtil.java	Fri May 17 16:47:13 2013 +0200
@@ -0,0 +1,126 @@
+/*
+ * Copyright (c) 2013, 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.virtual.phases.ea;
+
+import java.util.*;
+
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.debug.*;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.phases.*;
+
+public final class VirtualUtil {
+
+    private VirtualUtil() {
+        GraalInternalError.shouldNotReachHere();
+    }
+
+    public static boolean assertNonReachable(StructuredGraph graph, List<Node> obsoleteNodes) {
+        // helper code that determines the paths that keep obsolete nodes alive:
+
+        NodeFlood flood = graph.createNodeFlood();
+        IdentityHashMap<Node, Node> path = new IdentityHashMap<>();
+        flood.add(graph.start());
+        for (Node current : flood) {
+            if (current instanceof AbstractEndNode) {
+                AbstractEndNode end = (AbstractEndNode) current;
+                flood.add(end.merge());
+                if (!path.containsKey(end.merge())) {
+                    path.put(end.merge(), end);
+                }
+            } else {
+                for (Node successor : current.successors()) {
+                    flood.add(successor);
+                    if (!path.containsKey(successor)) {
+                        path.put(successor, current);
+                    }
+                }
+            }
+        }
+
+        for (Node node : obsoleteNodes) {
+            if (node instanceof FixedNode) {
+                assert !flood.isMarked(node) : node;
+            }
+        }
+
+        for (Node node : graph.getNodes()) {
+            if (node instanceof LocalNode) {
+                flood.add(node);
+            }
+            if (flood.isMarked(node)) {
+                for (Node input : node.inputs()) {
+                    flood.add(input);
+                    if (!path.containsKey(input)) {
+                        path.put(input, node);
+                    }
+                }
+            }
+        }
+        for (Node current : flood) {
+            for (Node input : current.inputs()) {
+                flood.add(input);
+                if (!path.containsKey(input)) {
+                    path.put(input, current);
+                }
+            }
+        }
+        boolean success = true;
+        for (Node node : obsoleteNodes) {
+            if (flood.isMarked(node)) {
+                TTY.print("offending node path:");
+                Node current = node;
+                while (current != null) {
+                    TTY.println(current.toString());
+                    current = path.get(current);
+                    if (current != null && current instanceof FixedNode && !obsoleteNodes.contains(current)) {
+                        break;
+                    }
+                }
+                success = false;
+            }
+        }
+        return success;
+    }
+
+    public static void trace(String format, Object... obj) {
+        if (GraalOptions.TraceEscapeAnalysis) {
+            Debug.log(format, obj);
+        }
+    }
+
+    static boolean matches(StructuredGraph graph, String filter) {
+        if (filter != null) {
+            if (filter.startsWith("~")) {
+                ResolvedJavaMethod method = graph.method();
+                return method == null || !MetaUtil.format("%H.%n", method).contains(filter.substring(1));
+            } else {
+                ResolvedJavaMethod method = graph.method();
+                return method != null && MetaUtil.format("%H.%n", method).contains(filter);
+            }
+        }
+        return true;
+    }
+
+}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java	Fri May 17 15:41:39 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java	Fri May 17 16:47:13 2013 +0200
@@ -22,8 +22,6 @@
  */
 package com.oracle.graal.virtual.phases.ea;
 
-import static com.oracle.graal.virtual.phases.ea.PartialEscapeAnalysisPhase.*;
-
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.graph.*;
@@ -149,7 +147,7 @@
 
     @Override
     public void createVirtualObject(VirtualObjectNode virtualObject, ValueNode[] entryState, int[] locks) {
-        trace("{{%s}} ", current);
+        VirtualUtil.trace("{{%s}} ", current);
         if (virtualObject.isAlive()) {
             state.addAndMarkAlias(virtualObject, virtualObject, usages);
         } else {