Mercurial > hg > graal-compiler
changeset 8559:af0c1352f969
more work on read elimination
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Tue Mar 26 11:28:52 2013 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Thu Mar 28 15:57:51 2013 +0100 @@ -23,6 +23,7 @@ package com.oracle.graal.compiler.test.ea; import junit.framework.*; +import junit.framework.Assert; import org.junit.Test; @@ -30,7 +31,6 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.test.*; import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; @@ -183,12 +183,7 @@ @Test public void testInstanceOf() { - ReturnNode returnNode = testEscapeAnalysis("testInstanceOfSnippet", null, false); - ValueNode result = returnNode.result(); - Assert.assertTrue(result instanceof ConditionalNode); - ConditionalNode conditional = (ConditionalNode) result; - Assert.assertTrue(conditional.condition() instanceof LogicConstantNode); - Assert.assertEquals(true, ((LogicConstantNode) conditional.condition()).getValue()); + testEscapeAnalysis("testInstanceOfSnippet", Constant.forInt(1), false); } public boolean testInstanceOfSnippet() {
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PEAReadEliminationTest.java Tue Mar 26 11:28:52 2013 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PEAReadEliminationTest.java Thu Mar 28 15:57:51 2013 +0100 @@ -72,6 +72,7 @@ @SuppressWarnings("all") public static int testSimpleSnippet(TestObject a) { a.x = 2; + staticField = a; return a.x; } @@ -84,6 +85,21 @@ } @SuppressWarnings("all") + public static int testSimpleConflictSnippet(TestObject a, TestObject b) { + a.x = 2; + b.x = 3; + staticField = a; + return a.x; + } + + @Test + public void testSimpleConflict() { + ValueNode result = getReturn("testSimpleConflictSnippet").result(); + assertFalse(result.isConstant()); + assertTrue(result instanceof LoadFieldNode); + } + + @SuppressWarnings("all") public static int testParamSnippet(TestObject a, int b) { a.x = b; return a.x; @@ -111,6 +127,39 @@ } @SuppressWarnings("all") + public static int testSimpleLoopSnippet(TestObject obj, int a, int b) { + obj.x = a; + for (int i = 0; i < 10; i++) { + staticField = obj; + } + return obj.x; + } + + @Test + public void testSimpleLoop() { + ValueNode result = getReturn("testSimpleLoopSnippet").result(); + assertTrue(graph.getNodes(LoadFieldNode.class).isEmpty()); + assertEquals(graph.getLocal(1), result); + } + + @SuppressWarnings("all") + public static int testBadLoopSnippet(TestObject obj, int a, int b) { + obj.x = a; + for (int i = 0; i < 10; i++) { + staticField = obj; + obj.x = 0; + } + return obj.x; + } + + @Test + public void testBadLoop() { + ValueNode result = getReturn("testBadLoopSnippet").result(); + assertEquals(1, graph.getNodes(LoadFieldNode.class).count()); + assertTrue(result instanceof LoadFieldNode); + } + + @SuppressWarnings("all") public static int testPhiSnippet(TestObject a, int b) { if (b < 0) { a.x = 1;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Mar 26 11:28:52 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Thu Mar 28 15:57:51 2013 +0100 @@ -125,12 +125,12 @@ new IterativeInliningPhase(runtime, assumptions, cache, plan, optimisticOpts).apply(graph); } else { new InliningPhase(runtime, null, assumptions, cache, plan, optimisticOpts).apply(graph); - } - new DeadCodeEliminationPhase().apply(graph); + new DeadCodeEliminationPhase().apply(graph); - if (GraalOptions.ConditionalElimination && GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase(runtime, assumptions).apply(graph); - new IterativeConditionalEliminationPhase(runtime, assumptions).apply(graph); + if (GraalOptions.ConditionalElimination && GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase(runtime, assumptions).apply(graph); + new IterativeConditionalEliminationPhase(runtime, assumptions).apply(graph); + } } }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/ArrayCopyNode.java Tue Mar 26 11:28:52 2013 +0100 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/ArrayCopyNode.java Thu Mar 28 15:57:51 2013 +0100 @@ -24,7 +24,6 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; import com.oracle.graal.graph.Node.IterableNodeType; import com.oracle.graal.loop.phases.*; import com.oracle.graal.nodes.*;
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/ObjectCloneNode.java Tue Mar 26 11:28:52 2013 +0100 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/replacements/ObjectCloneNode.java Thu Mar 28 15:57:51 2013 +0100 @@ -122,7 +122,7 @@ ValueNode[] state = new ValueNode[fields.length]; final LoadFieldNode[] loads = new LoadFieldNode[fields.length]; for (int i = 0; i < fields.length; i++) { - state[i] = loads[i] = graph().add(new LoadFieldNode(obj, fields[i])); + state[i] = loads[i] = new LoadFieldNode(obj, fields[i]); } final StructuredGraph structuredGraph = (StructuredGraph) graph(); @@ -130,7 +130,7 @@ public void run() { for (LoadFieldNode load : loads) { - structuredGraph.addBeforeFixed(ObjectCloneNode.this, load); + structuredGraph.addBeforeFixed(ObjectCloneNode.this, structuredGraph.add(load)); } } });
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Tue Mar 26 11:28:52 2013 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Thu Mar 28 15:57:51 2013 +0100 @@ -37,11 +37,12 @@ class BlockState { - private final HashMap<VirtualObjectNode, ObjectState> objectStates = new HashMap<>(); - private final HashMap<ValueNode, VirtualObjectNode> objectAliases = new HashMap<>(); - private final HashMap<ValueNode, ValueNode> scalarAliases = new HashMap<>(); + private final IdentityHashMap<VirtualObjectNode, ObjectState> objectStates = new IdentityHashMap<>(); + private final IdentityHashMap<ValueNode, VirtualObjectNode> objectAliases; + private final IdentityHashMap<ValueNode, ValueNode> scalarAliases; + private final HashMap<ReadCacheEntry, ValueNode> readCache; - private static class ReadCacheEntry { + static class ReadCacheEntry { public final Object identity; public final ValueNode object; @@ -63,43 +64,37 @@ return identity == other.identity && object == other.object; } + @Override + public String toString() { + return object + ":" + identity; + } } - private final HashMap<ReadCacheEntry, ValueNode> readCache = new HashMap<>(); - public BlockState() { + objectAliases = new IdentityHashMap<>(); + scalarAliases = new IdentityHashMap<>(); + readCache = new HashMap<>(); } public BlockState(BlockState other) { for (Map.Entry<VirtualObjectNode, ObjectState> entry : other.objectStates.entrySet()) { objectStates.put(entry.getKey(), entry.getValue().cloneState()); } - for (Map.Entry<ValueNode, VirtualObjectNode> entry : other.objectAliases.entrySet()) { - objectAliases.put(entry.getKey(), entry.getValue()); - } - for (Map.Entry<ValueNode, ValueNode> entry : other.scalarAliases.entrySet()) { - scalarAliases.put(entry.getKey(), entry.getValue()); - } + objectAliases = new IdentityHashMap<>(other.objectAliases); + scalarAliases = new IdentityHashMap<>(other.scalarAliases); + readCache = new HashMap<>(other.readCache); } public void addReadCache(ValueNode object, Object identity, ValueNode value) { - ValueNode cacheValue; - ObjectState obj = getObjectState(value); - if (obj != null) { - assert !obj.isVirtual(); - cacheValue = obj.getMaterializedValue(); - } else { - cacheValue = getScalarAlias(value); - } ValueNode cacheObject; - obj = getObjectState(object); + ObjectState obj = getObjectState(object); if (obj != null) { assert !obj.isVirtual(); cacheObject = obj.getMaterializedValue(); } else { cacheObject = object; } - readCache.put(new ReadCacheEntry(identity, cacheObject), cacheValue); + readCache.put(new ReadCacheEntry(identity, cacheObject), value); } public ValueNode getReadCache(ValueNode object, Object identity) { @@ -111,7 +106,15 @@ } else { cacheObject = object; } - return readCache.get(new ReadCacheEntry(identity, cacheObject)); + ValueNode cacheValue = readCache.get(new ReadCacheEntry(identity, cacheObject)); + obj = getObjectState(cacheValue); + if (obj != null) { + assert !obj.isVirtual(); + cacheValue = obj.getMaterializedValue(); + } else { + cacheValue = getScalarAlias(cacheValue); + } + return cacheValue; } public void killReadCache(Object identity) { @@ -275,7 +278,7 @@ PhiNode phiNode = new PhiNode(value.kind(), merge); effects.addFloatingNode(phiNode); for (int i = 0; i < states.size(); i++) { - effects.addPhiInput(phiNode, states.get(i).readCache.get(key)); + effects.addPhiInput(phiNode, states.get(i).getReadCache(key.object, key.identity)); } readCache.put(key, phiNode); } else if (value != null) { @@ -297,7 +300,7 @@ private void mergeReadCachePhi(PhiNode phi, Object identity, List<BlockState> states, MergeNode merge, GraphEffectList effects) { ValueNode[] values = new ValueNode[phi.valueCount()]; for (int i = 0; i < phi.valueCount(); i++) { - ValueNode value = states.get(i).readCache.get(new ReadCacheEntry(identity, phi.valueAt(i))); + ValueNode value = states.get(i).getReadCache(phi.valueAt(i), identity); if (value == null) { return; } @@ -342,4 +345,8 @@ return newState; } + public Map<ReadCacheEntry, ValueNode> getReadCache() { + return readCache; + } + }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/IterativeInliningPhase.java Tue Mar 26 11:28:52 2013 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/IterativeInliningPhase.java Thu Mar 28 15:57:51 2013 +0100 @@ -27,15 +27,10 @@ import com.oracle.graal.api.code.*; import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.common.CanonicalizerPhase.CustomCanonicalizer; -import com.oracle.graal.phases.graph.*; -import com.oracle.graal.phases.schedule.*; -import com.oracle.graal.virtual.phases.ea.EffectList.Effect; public class IterativeInliningPhase extends Phase { @@ -45,7 +40,6 @@ private final Assumptions assumptions; private final GraphCache cache; private final OptimisticOptimizations optimisticOpts; - private CustomCanonicalizer customCanonicalizer; public IterativeInliningPhase(GraalCodeCacheProvider runtime, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts) { this.runtime = runtime; @@ -55,20 +49,12 @@ this.optimisticOpts = optimisticOpts; } - public void setCustomCanonicalizer(CustomCanonicalizer customCanonicalizer) { - this.customCanonicalizer = customCanonicalizer; - } - public static final void trace(String format, Object... obj) { if (GraalOptions.TraceEscapeAnalysis) { Debug.log(format, obj); } } - public static final void error(String format, Object... obj) { - System.out.print(String.format(format, obj)); - } - @Override protected void run(final StructuredGraph graph) { runIterations(graph, true); @@ -82,32 +68,18 @@ @Override public Boolean call() { - SchedulePhase schedule = new SchedulePhase(); - schedule.apply(graph, false); - PartialEscapeClosure closure = new PartialEscapeClosure(graph.createNodeBitMap(), schedule, runtime, assumptions); - ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock(), new BlockState(), null); + boolean progress = false; + PartialEscapeAnalysisPhase ea = new PartialEscapeAnalysisPhase(runtime, assumptions, false); + ea.apply(graph); + progress |= ea.hasChanged(); - if (!closure.getEffects().isEmpty()) { - // apply the effects collected during the escape analysis iteration - ArrayList<Node> obsoleteNodes = new ArrayList<>(); - for (Effect effect : closure.getEffects()) { - effect.apply(graph, obsoleteNodes); - } - trace("%s\n", closure.getEffects()); - - Debug.dump(graph, "after PartialEscapeAnalysis"); - assert PartialEscapeAnalysisPhase.noObsoleteNodes(graph, obsoleteNodes); - - new DeadCodeEliminationPhase().apply(graph); - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase(runtime, assumptions, null, customCanonicalizer).apply(graph); - } - } Map<Invoke, Double> hints = GraalOptions.PEAInliningHints ? PartialEscapeAnalysisPhase.getHints(graph) : null; InliningPhase inlining = new InliningPhase(runtime, hints, assumptions, cache, plan, optimisticOpts); inlining.setMaxMethodsPerInlining(simple ? 1 : Integer.MAX_VALUE); inlining.apply(graph); + progress |= inlining.getInliningCount() > 0; + new DeadCodeEliminationPhase().apply(graph); if (GraalOptions.ConditionalElimination && GraalOptions.OptCanonicalizer) { @@ -115,10 +87,7 @@ new IterativeConditionalEliminationPhase(runtime, assumptions).apply(graph); } - if (closure.getEffects().isEmpty() && inlining.getInliningCount() == 0) { - return false; - } - return true; + return progress; } }); }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Tue Mar 26 11:28:52 2013 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Thu Mar 28 15:57:51 2013 +0100 @@ -48,12 +48,18 @@ private CustomCanonicalizer customCanonicalizer; private final boolean iterative; + private boolean changed; + public PartialEscapeAnalysisPhase(MetaAccessProvider runtime, Assumptions assumptions, boolean iterative) { this.runtime = runtime; this.assumptions = assumptions; this.iterative = iterative; } + public boolean hasChanged() { + return changed; + } + public void setCustomCanonicalizer(CustomCanonicalizer customCanonicalizer) { this.customCanonicalizer = customCanonicalizer; } @@ -64,10 +70,6 @@ } } - public static final void error(String format, Object... obj) { - System.out.print(String.format(format, obj)); - } - @Override protected void run(final StructuredGraph graph) { if (!matches(graph, GraalOptions.EscapeAnalyzeOnly)) { @@ -93,14 +95,16 @@ @Override public Boolean call() { + SchedulePhase schedule = new SchedulePhase(); schedule.apply(graph, false); PartialEscapeClosure closure = new PartialEscapeClosure(graph.createNodeBitMap(), schedule, runtime, assumptions); ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock(), new BlockState(), null); - if (closure.getEffects().isEmpty()) { + if (!closure.hasChanged()) { return false; } + changed = true; // apply the effects collected during the escape analysis iteration ArrayList<Node> obsoleteNodes = new ArrayList<>(); @@ -109,17 +113,16 @@ } trace("%s\n", closure.getEffects()); - Debug.dump(graph, "after PartialEscapeAnalysis"); + Debug.dump(graph, "after PartialEscapeAnalysis iteration"); assert noObsoleteNodes(graph, obsoleteNodes); new DeadCodeEliminationPhase().apply(graph); - if (!iterative) { - return false; - } + if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase(runtime, assumptions, null, customCanonicalizer).apply(graph); } - return true; + + return iterative; } }); } @@ -193,10 +196,10 @@ boolean success = true; for (Node node : obsoleteNodes) { if (flood.isMarked(node)) { - error("offending node path:"); + System.out.print("offending node path:"); Node current = node; while (current != null) { - error(current.toString()); + System.out.println(current.toString()); current = path.get(current); if (current != null && current instanceof FixedNode && !obsoleteNodes.contains(current)) { break;
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Tue Mar 26 11:28:52 2013 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Thu Mar 28 15:57:51 2013 +0100 @@ -45,6 +45,7 @@ import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo; import com.oracle.graal.phases.schedule.*; import com.oracle.graal.virtual.nodes.*; +import com.oracle.graal.virtual.phases.ea.BlockState.ReadCacheEntry; class PartialEscapeClosure extends BlockIteratorClosure<BlockState> { @@ -70,12 +71,18 @@ private final Map<Invoke, Double> hints = new IdentityHashMap<>(); + private boolean changed; + public PartialEscapeClosure(NodeBitMap usages, SchedulePhase schedule, MetaAccessProvider metaAccess, Assumptions assumptions) { this.usages = usages; this.schedule = schedule; tool = new VirtualizerToolImpl(effects, usages, metaAccess, assumptions); } + public boolean hasChanged() { + return changed; + } + public GraphEffectList getEffects() { return effects; } @@ -109,9 +116,12 @@ METRIC_STOREFIELD_RECORDED.increment(); StoreFieldNode store = (StoreFieldNode) node; ValueNode cachedValue = state.getReadCache(store.object(), store.field()); + state.killReadCache(store.field()); + if (cachedValue == store.value()) { effects.addCounterBefore("store elim", 1, false, lastFixedNode.next()); effects.deleteFixedNode(store); + changed = true; } else { state.addReadCache(store.object(), store.field(), store.value()); } @@ -123,6 +133,7 @@ effects.addCounterBefore("load elim", 1, false, lastFixedNode.next()); effects.replaceAtUsages(load, cachedValue); state.addScalarAlias(load, cachedValue); + changed = true; } else { METRIC_LOADFIELD_NOT_ELIMINATED.increment(); state.addReadCache(load.object(), load.field(), load); @@ -149,6 +160,9 @@ ((Virtualizable) node).virtualize(tool); } if (tool.isDeleted()) { + if (tool.isCustomAction() || !(node instanceof VirtualizableAllocation || node instanceof CyclicMaterializeStoreNode)) { + changed = true; + } return true; } if (node instanceof StateSplit) { @@ -475,11 +489,13 @@ List<BlockState> loopEndStates = info.endStates; List<Block> predecessors = loop.header.getPredecessors(); HashSet<VirtualObjectNode> additionalMaterializations = new HashSet<>(); + HashSet<ReadCacheEntry> additionalKilledReads = new HashSet<>(); int oldPhiCount = phis.size(); for (int i = 1; i < predecessors.size(); i++) { - processLoopEnd(loop.loopBegin(), (LoopEndNode) predecessors.get(i).getEndNode(), state, loopEndStates.get(i - 1), successEffects, additionalMaterializations, phis); + processLoopEnd(loop.loopBegin(), (LoopEndNode) predecessors.get(i).getEndNode(), state, loopEndStates.get(i - 1), successEffects, additionalMaterializations, additionalKilledReads, + phis); } - if (additionalMaterializations.isEmpty() && oldPhiCount == phis.size()) { + if (additionalMaterializations.isEmpty() && additionalKilledReads.isEmpty() && oldPhiCount == phis.size()) { effects.addAll(successEffects); assert info.exitStates.size() == loop.exits.size(); @@ -504,6 +520,9 @@ assert obj.getState() == EscapeState.Global; } } + for (ReadCacheEntry entry : additionalKilledReads) { + initialState.getReadCache().remove(entry); + } } } @@ -546,10 +565,18 @@ obj.updateMaterializedValue(proxy); } else { assert initialObj.getMaterializedValue() == obj.getMaterializedValue() : "materialized value is not allowed to change within loops: " + initialObj.getMaterializedValue() + - " vs. " + obj.getMaterializedValue(); + " vs. " + obj.getMaterializedValue() + " at " + exitNode; } } } + + for (Map.Entry<ReadCacheEntry, ValueNode> entry : exitState.getReadCache().entrySet()) { + if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) { + ProxyNode proxy = new ProxyNode(exitState.getReadCache(entry.getKey().object, entry.getKey().identity), exitNode, PhiType.Value, null); + effects.addFloatingNode(proxy); + entry.setValue(proxy); + } + } } private final class PhiDesc { @@ -584,7 +611,7 @@ } private void processLoopEnd(LoopBeginNode loopBegin, LoopEndNode loopEnd, BlockState initialState, BlockState loopEndState, GraphEffectList successEffects, - Set<VirtualObjectNode> additionalMaterializations, HashSet<PhiDesc> phis) { + Set<VirtualObjectNode> additionalMaterializations, HashSet<ReadCacheEntry> additionalKilledReads, HashSet<PhiDesc> phis) { assert loopEnd.loopBegin() == loopBegin; boolean materialized; do { @@ -716,5 +743,11 @@ } } } + + for (Map.Entry<ReadCacheEntry, ValueNode> entry : initialState.getReadCache().entrySet()) { + if (loopEndState.getReadCache().get(entry.getKey()) != entry.getValue()) { + additionalKilledReads.add(entry.getKey()); + } + } } }