Mercurial > hg > truffle

changeset 8556:c69b29285ff8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
better read elimination
author Lukas Stadler <lukas.stadler@jku.at>
date Mon, 25 Mar 2013 11:21:33 +0100
parents 85d5fd3724ef
children ca3a5c5d3947
files graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PEAReadEliminationTest.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
diffstat 5 files changed, 326 insertions(+), 37 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PEAReadEliminationTest.java	Mon Mar 25 11:21:33 2013 +0100
@@ -0,0 +1,161 @@
+/*
+ * 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.compiler.test.ea;
+
+import static org.junit.Assert.*;
+
+import java.util.concurrent.*;
+
+import org.junit.*;
+
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.compiler.test.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.java.*;
+import com.oracle.graal.phases.*;
+import com.oracle.graal.phases.common.*;
+import com.oracle.graal.virtual.phases.ea.*;
+
+public class PEAReadEliminationTest extends GraalCompilerTest {
+
+    private StructuredGraph graph;
+
+    public static Object staticField;
+
+    public static class TestObject implements Callable<Integer> {
+
+        public int x;
+        public int y;
+
+        public TestObject(int x, int y) {
+            this.x = x;
+            this.y = y;
+        }
+
+        @Override
+        public Integer call() throws Exception {
+            return x;
+        }
+    }
+
+    public static class TestObject2 {
+
+        public Object x;
+        public Object y;
+
+        public TestObject2(Object x, Object y) {
+            this.x = x;
+            this.y = y;
+        }
+    }
+
+    @SuppressWarnings("all")
+    public static int testSimpleSnippet(TestObject a) {
+        a.x = 2;
+        return a.x;
+    }
+
+    @Test
+    public void testSimple() {
+        ValueNode result = getReturn("testSimpleSnippet").result();
+        assertTrue(graph.getNodes(LoadFieldNode.class).isEmpty());
+        assertTrue(result.isConstant());
+        assertEquals(2, result.asConstant().asInt());
+    }
+
+    @SuppressWarnings("all")
+    public static int testParamSnippet(TestObject a, int b) {
+        a.x = b;
+        return a.x;
+    }
+
+    @Test
+    public void testParam() {
+        ValueNode result = getReturn("testParamSnippet").result();
+        assertTrue(graph.getNodes(LoadFieldNode.class).isEmpty());
+        assertEquals(graph.getLocal(1), result);
+    }
+
+    @SuppressWarnings("all")
+    public static int testMaterializedSnippet(int a) {
+        TestObject obj = new TestObject(a, 0);
+        staticField = obj;
+        return obj.x;
+    }
+
+    @Test
+    public void testMaterialized() {
+        ValueNode result = getReturn("testMaterializedSnippet").result();
+        assertTrue(graph.getNodes(LoadFieldNode.class).isEmpty());
+        assertEquals(graph.getLocal(0), result);
+    }
+
+    @SuppressWarnings("all")
+    public static int testPhiSnippet(TestObject a, int b) {
+        if (b < 0) {
+            a.x = 1;
+        } else {
+            a.x = 2;
+        }
+        return a.x;
+    }
+
+    @Test
+    public void testPhi() {
+        ValueNode result = getReturn("testPhiSnippet").result();
+        assertTrue(graph.getNodes(LoadFieldNode.class).isEmpty());
+        assertTrue(result instanceof PhiNode);
+        PhiNode phi = (PhiNode) result;
+        assertTrue(phi.valueAt(0).isConstant());
+        assertTrue(phi.valueAt(1).isConstant());
+        assertEquals(1, phi.valueAt(0).asConstant().asInt());
+        assertEquals(2, phi.valueAt(1).asConstant().asInt());
+    }
+
+    @SuppressWarnings("all")
+    public static void testSimpleStoreSnippet(TestObject a, int b) {
+        a.x = b;
+        a.x = b;
+    }
+
+    @Test
+    public void testSimpleStore() {
+        processMethod("testSimpleStoreSnippet");
+        assertEquals(1, graph.getNodes().filter(StoreFieldNode.class).count());
+    }
+
+    final ReturnNode getReturn(String snippet) {
+        processMethod(snippet);
+        assertEquals(1, graph.getNodes(ReturnNode.class).count());
+        return graph.getNodes(ReturnNode.class).first();
+    }
+
+    private void processMethod(final String snippet) {
+        graph = parse(snippet);
+        new ComputeProbabilityPhase().apply(graph);
+        Assumptions assumptions = new Assumptions(false);
+        new InliningPhase(runtime(), null, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
+        GraalOptions.PEAReadCache = true;
+        new PartialEscapeAnalysisPhase(runtime(), assumptions, false).apply(graph);
+    }
+}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java	Mon Mar 25 11:18:19 2013 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java	Mon Mar 25 11:21:33 2013 +0100
@@ -83,11 +83,35 @@
     }
 
     public void addReadCache(ValueNode object, Object identity, ValueNode value) {
-        readCache.put(new ReadCacheEntry(identity, object), 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);
+        if (obj != null) {
+            assert !obj.isVirtual();
+            cacheObject = obj.getMaterializedValue();
+        } else {
+            cacheObject = object;
+        }
+        readCache.put(new ReadCacheEntry(identity, cacheObject), cacheValue);
     }
 
     public ValueNode getReadCache(ValueNode object, Object identity) {
-        return readCache.get(new ReadCacheEntry(identity, object));
+        ValueNode cacheObject;
+        ObjectState obj = getObjectState(object);
+        if (obj != null) {
+            assert !obj.isVirtual();
+            cacheObject = obj.getMaterializedValue();
+        } else {
+            cacheObject = object;
+        }
+        return readCache.get(new ReadCacheEntry(identity, cacheObject));
     }
 
     public void killReadCache(Object identity) {
@@ -175,6 +199,13 @@
         }
         deferred.remove(virtual);
 
+        if (virtual instanceof VirtualInstanceNode) {
+            VirtualInstanceNode instance = (VirtualInstanceNode) virtual;
+            for (int i = 0; i < fieldState.length; i++) {
+                readCache.put(new ReadCacheEntry(instance.field(i), materialize), fieldState[i]);
+            }
+        }
+
         materializeEffects.addMaterialization(materialize, fixed, values);
     }
 
@@ -224,7 +255,64 @@
         return objectStates.toString();
     }
 
-    public static BlockState meetAliasesAndCache(List<BlockState> states) {
+    public void mergeReadCache(List<BlockState> states, MergeNode merge, GraphEffectList effects) {
+        for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
+            ReadCacheEntry key = entry.getKey();
+            ValueNode value = entry.getValue();
+            boolean phi = false;
+            for (int i = 1; i < states.size(); i++) {
+                ValueNode otherValue = states.get(i).readCache.get(key);
+                if (otherValue == null) {
+                    value = null;
+                    phi = false;
+                    break;
+                }
+                if (!phi && otherValue != value) {
+                    phi = true;
+                }
+            }
+            if (phi) {
+                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));
+                }
+                readCache.put(key, phiNode);
+            } else if (value != null) {
+                readCache.put(key, value);
+            }
+        }
+        for (PhiNode phi : merge.phis()) {
+            if (phi.kind() == Kind.Object) {
+                for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
+                    if (entry.getKey().object == phi.valueAt(0)) {
+                        mergeReadCachePhi(phi, entry.getKey().identity, states, merge, effects);
+                    }
+                }
+
+            }
+        }
+    }
+
+    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)));
+            if (value == null) {
+                return;
+            }
+            values[i] = value;
+        }
+
+        PhiNode phiNode = new PhiNode(values[0].kind(), merge);
+        effects.addFloatingNode(phiNode);
+        for (int i = 0; i < values.length; i++) {
+            effects.addPhiInput(phiNode, values[i]);
+        }
+        readCache.put(new ReadCacheEntry(identity, phi), phiNode);
+    }
+
+    public static BlockState meetAliases(List<BlockState> states) {
         BlockState newState = new BlockState();
 
         newState.objectAliases.putAll(states.get(0).objectAliases);
@@ -251,21 +339,7 @@
             }
         }
 
-        for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) {
-            ReadCacheEntry key = entry.getKey();
-            ValueNode value = entry.getValue();
-            for (int i = 1; i < states.size(); i++) {
-                ValueNode otherValue = states.get(i).readCache.get(key);
-                if (otherValue == null || otherValue != value) {
-                    value = null;
-                    break;
-                }
-            }
-            if (value != null) {
-                newState.readCache.put(key, value);
-            }
-        }
-
         return newState;
     }
+
 }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java	Mon Mar 25 11:18:19 2013 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java	Mon Mar 25 11:21:33 2013 +0100
@@ -26,12 +26,55 @@
 
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.debug.*;
 import com.oracle.graal.nodes.virtual.*;
 import com.oracle.graal.phases.common.*;
 import com.oracle.graal.virtual.nodes.*;
 
 public class GraphEffectList extends EffectList {
 
+    public void addCounterBefore(final String name, final int increment, final boolean addContext, final FixedNode position) {
+        if (!DynamicCounterNode.enabled) {
+            return;
+        }
+        add(new Effect() {
+
+            @Override
+            public String name() {
+                return "addCounterBefore";
+            }
+
+            @Override
+            public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
+                assert position.isAlive();
+                DynamicCounterNode node = graph.add(new DynamicCounterNode(name, increment, addContext));
+                graph.addBeforeFixed(position, node);
+                node.setProbability(position.probability());
+            }
+        });
+    }
+
+    public void addSurvivingCounterBefore(final String name, final int increment, final boolean addContext, final ValueNode checkedValue, final FixedNode position) {
+        if (!DynamicCounterNode.enabled) {
+            return;
+        }
+        add(new Effect() {
+
+            @Override
+            public String name() {
+                return "addSurvivingCounterBefore";
+            }
+
+            @Override
+            public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) {
+                assert position.isAlive();
+                DynamicCounterNode node = graph.add(new SurvivingCounterNode(name, increment, addContext, checkedValue));
+                graph.addBeforeFixed(position, node);
+                node.setProbability(position.probability());
+            }
+        });
+    }
+
     /**
      * Adds the given fixed node to the graph's control flow, before position (so that the original
      * predecessor of position will then be node's predecessor).
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java	Mon Mar 25 11:18:19 2013 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java	Mon Mar 25 11:21:33 2013 +0100
@@ -30,6 +30,7 @@
 import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.debug.*;
 import com.oracle.graal.nodes.java.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.phases.*;
@@ -73,15 +74,17 @@
             return;
         }
 
-        boolean analyzableNodes = false;
-        for (Node node : graph.getNodes()) {
-            if (node instanceof VirtualizableAllocation) {
-                analyzableNodes = true;
-                break;
+        if (!GraalOptions.PEAReadCache) {
+            boolean analyzableNodes = false;
+            for (Node node : graph.getNodes()) {
+                if (node instanceof VirtualizableAllocation) {
+                    analyzableNodes = true;
+                    break;
+                }
             }
-        }
-        if (!analyzableNodes) {
-            return;
+            if (!analyzableNodes) {
+                return;
+            }
         }
 
         Boolean continueIteration = true;
@@ -120,6 +123,12 @@
                 }
             });
         }
+
+        for (Node node : graph.getNodes()) {
+            if (node instanceof LoadFieldNode) {
+                DynamicCounterNode.addCounterBefore("load non-elim", 1, false, (FixedNode) node);
+            }
+        }
     }
 
     private static boolean matches(StructuredGraph graph, String filter) {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Mon Mar 25 11:18:19 2013 +0100
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java	Mon Mar 25 11:21:33 2013 +0100
@@ -37,7 +37,7 @@
 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.*;
+import com.oracle.graal.nodes.spi.Virtualizable.EscapeState;
 import com.oracle.graal.nodes.virtual.*;
 import com.oracle.graal.phases.*;
 import com.oracle.graal.phases.graph.*;
@@ -108,19 +108,19 @@
                     if (node instanceof StoreFieldNode) {
                         METRIC_STOREFIELD_RECORDED.increment();
                         StoreFieldNode store = (StoreFieldNode) node;
-                        ValueNode value = store.value();
-                        ObjectState obj = state.getObjectState(value);
-                        if (obj != null) {
-                            assert !obj.isVirtual();
-                            value = obj.getMaterializedValue();
+                        ValueNode cachedValue = state.getReadCache(store.object(), store.field());
+                        if (cachedValue == store.value()) {
+                            effects.addCounterBefore("store elim", 1, false, lastFixedNode.next());
+                            effects.deleteFixedNode(store);
+                        } else {
+                            state.addReadCache(store.object(), store.field(), store.value());
                         }
-                        value = state.getScalarAlias(value);
-                        state.addReadCache(store.object(), store.field(), value);
                     } else if (node instanceof LoadFieldNode) {
                         LoadFieldNode load = (LoadFieldNode) node;
                         ValueNode cachedValue = state.getReadCache(load.object(), load.field());
                         if (cachedValue != null) {
                             METRIC_LOADFIELD_ELIMINATED.increment();
+                            effects.addCounterBefore("load elim", 1, false, lastFixedNode.next());
                             effects.replaceAtUsages(load, cachedValue);
                             state.addScalarAlias(load, cachedValue);
                         } else {
@@ -260,7 +260,7 @@
 
     @Override
     protected BlockState merge(MergeNode merge, List<BlockState> states) {
-        BlockState newState = BlockState.meetAliasesAndCache(states);
+        BlockState newState = BlockState.meetAliases(states);
 
         // Iterative processing:
         // Merging the materialized/virtual state of virtual objects can lead to new
@@ -352,13 +352,15 @@
                 }
             }
 
-            for (PhiNode phi : merge.phis().snapshot()) {
+            for (PhiNode phi : merge.phis()) {
                 if (usages.isMarked(phi) && phi.type() == PhiType.Value) {
                     materialized |= processPhi(newState, merge, phi, states);
                 }
             }
         } while (materialized);
 
+        newState.mergeReadCache(states, merge, effects);
+
         return newState;
     }
 
@@ -625,7 +627,7 @@
                     }
                 }
             }
-            for (PhiNode phi : loopBegin.phis().snapshot()) {
+            for (PhiNode phi : loopBegin.phis()) {
                 if (usages.isMarked(phi) && phi.type() == PhiType.Value) {
                     ObjectState initialObj = initialState.getObjectState(phi.valueAt(0));
                     boolean initialMaterialized = initialObj == null || !initialObj.isVirtual();