# HG changeset patch
# User Lukas Stadler <lukas.stadler@jku.at>
# Date 1373547434 -7200
# Node ID 0e671d5268d1559d6960fd57257f01aeeb9e1d2c
# Parent  097a634b57b1c94e4f15c8979411822220f3e0e4
re-introduce early read elimination as part of escape analysis

diff -r 097a634b57b1 -r 0e671d5268d1 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeBlockState.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeBlockState.java	Fri Jul 12 11:19:36 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeBlockState.java	Thu Jul 11 14:57:14 2013 +0200
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2011, 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
diff -r 097a634b57b1 -r 0e671d5268d1 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapePhase.java
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapePhase.java	Fri Jul 12 11:19:36 2013 +0200
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapePhase.java	Thu Jul 11 14:57:14 2013 +0200
@@ -32,6 +32,7 @@
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.nodes.util.*;
 import com.oracle.graal.nodes.virtual.*;
+import com.oracle.graal.options.*;
 import com.oracle.graal.phases.common.*;
 import com.oracle.graal.phases.graph.*;
 import com.oracle.graal.phases.schedule.*;
@@ -39,21 +40,26 @@
 
 public class PartialEscapePhase extends EffectsPhase<PhaseContext> {
 
+    //@formatter:off
+    @Option(help = "")
+    public static final OptionValue<Boolean> OptEarlyReadElimination = new OptionValue<>(true);
+    //@formatter:on
+
+    private final boolean readElimination;
+
     public PartialEscapePhase(boolean iterative, CanonicalizerPhase canonicalizer) {
+        this(iterative, OptEarlyReadElimination.getValue(), canonicalizer);
+    }
+
+    public PartialEscapePhase(boolean iterative, boolean readElimination, CanonicalizerPhase canonicalizer) {
         super(iterative ? EscapeAnalysisIterations.getValue() : 1, canonicalizer);
+        this.readElimination = readElimination;
     }
 
     @Override
     protected void run(StructuredGraph graph, PhaseContext context) {
         if (VirtualUtil.matches(graph, EscapeAnalyzeOnly.getValue())) {
-            boolean analyzableNodes = false;
-            for (Node node : graph.getNodes()) {
-                if (node instanceof VirtualizableAllocation) {
-                    analyzableNodes = true;
-                    break;
-                }
-            }
-            if (analyzableNodes) {
+            if (readElimination || graph.getNodes().filterInterface(VirtualizableAllocation.class).isNotEmpty()) {
                 runAnalysis(graph, context);
             }
         }
@@ -61,7 +67,11 @@
 
     @Override
     protected Closure<?> createEffectsClosure(PhaseContext context, SchedulePhase schedule) {
-        return new PartialEscapeClosure.Final(schedule, context.getRuntime(), context.getAssumptions());
+        if (readElimination) {
+            return new ReadEliminationPEClosure(schedule, context.getRuntime(), context.getAssumptions());
+        } else {
+            return new PartialEscapeClosure.Final(schedule, context.getRuntime(), context.getAssumptions());
+        }
     }
 
     public static Map<Invoke, Double> getHints(StructuredGraph graph) {
diff -r 097a634b57b1 -r 0e671d5268d1 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ReadEliminationPEBlockState.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ReadEliminationPEBlockState.java	Thu Jul 11 14:57:14 2013 +0200
@@ -0,0 +1,145 @@
+/*
+ * Copyright (c) 2011, 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.nodes.*;
+import com.oracle.graal.nodes.virtual.*;
+
+public class ReadEliminationPEBlockState extends PartialEscapeBlockState<ReadEliminationPEBlockState> {
+
+    final HashMap<ReadCacheEntry, ValueNode> readCache;
+
+    static class ReadCacheEntry {
+
+        public final ResolvedJavaField identity;
+        public final ValueNode object;
+
+        public ReadCacheEntry(ResolvedJavaField identity, ValueNode object) {
+            this.identity = identity;
+            this.object = object;
+        }
+
+        @Override
+        public int hashCode() {
+            int result = 31 + ((identity == null) ? 0 : identity.hashCode());
+            return 31 * result + ((object == null) ? 0 : object.hashCode());
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            ReadCacheEntry other = (ReadCacheEntry) obj;
+            return identity == other.identity && object == other.object;
+        }
+
+        @Override
+        public String toString() {
+            return object + ":" + identity;
+        }
+    }
+
+    public ReadEliminationPEBlockState() {
+        readCache = new HashMap<>();
+    }
+
+    public ReadEliminationPEBlockState(ReadEliminationPEBlockState other) {
+        super(other);
+        readCache = new HashMap<>(other.readCache);
+    }
+
+    @Override
+    public String toString() {
+        return super.toString() + " " + readCache;
+    }
+
+    @Override
+    protected void objectMaterialized(VirtualObjectNode virtual, AllocatedObjectNode representation, List<ValueNode> values) {
+        if (virtual instanceof VirtualInstanceNode) {
+            VirtualInstanceNode instance = (VirtualInstanceNode) virtual;
+            for (int i = 0; i < instance.entryCount(); i++) {
+                readCache.put(new ReadCacheEntry(instance.field(i), representation), values.get(i));
+            }
+        }
+    }
+
+    @Override
+    public boolean equivalentTo(ReadEliminationPEBlockState other) {
+        if (!compareMapsNoSize(readCache, other.readCache)) {
+            return false;
+        }
+        return super.equivalentTo(other);
+    }
+
+    public void addReadCache(ValueNode object, ResolvedJavaField identity, ValueNode value) {
+        ValueNode cacheObject;
+        ObjectState obj = getObjectState(object);
+        if (obj != null) {
+            assert !obj.isVirtual();
+            cacheObject = obj.getMaterializedValue();
+        } else {
+            cacheObject = object;
+        }
+        readCache.put(new ReadCacheEntry(identity, cacheObject), value);
+    }
+
+    public ValueNode getReadCache(ValueNode object, ResolvedJavaField identity) {
+        ValueNode cacheObject;
+        ObjectState obj = getObjectState(object);
+        if (obj != null) {
+            assert !obj.isVirtual();
+            cacheObject = obj.getMaterializedValue();
+        } else {
+            cacheObject = object;
+        }
+        ValueNode cacheValue = readCache.get(new ReadCacheEntry(identity, cacheObject));
+        obj = getObjectState(cacheValue);
+        if (obj != null) {
+            assert !obj.isVirtual();
+            cacheValue = obj.getMaterializedValue();
+        } else {
+            // assert !scalarAliases.containsKey(cacheValue);
+            cacheValue = getScalarAlias(cacheValue);
+        }
+        return cacheValue;
+    }
+
+    public void killReadCache() {
+        readCache.clear();
+    }
+
+    public void killReadCache(ResolvedJavaField identity) {
+        Iterator<Map.Entry<ReadCacheEntry, ValueNode>> iter = readCache.entrySet().iterator();
+        while (iter.hasNext()) {
+            Map.Entry<ReadCacheEntry, ValueNode> entry = iter.next();
+            if (entry.getKey().identity == identity) {
+                iter.remove();
+            }
+        }
+    }
+
+    public Map<ReadCacheEntry, ValueNode> getReadCache() {
+        return readCache;
+    }
+}
diff -r 097a634b57b1 -r 0e671d5268d1 graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ReadEliminationPEClosure.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ReadEliminationPEClosure.java	Thu Jul 11 14:57:14 2013 +0200
@@ -0,0 +1,190 @@
+/*
+ * Copyright (c) 2011, 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 static com.oracle.graal.api.meta.LocationIdentity.*;
+
+import java.util.*;
+
+import com.oracle.graal.api.code.*;
+import com.oracle.graal.api.meta.*;
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.PhiNode.PhiType;
+import com.oracle.graal.nodes.cfg.*;
+import com.oracle.graal.nodes.extended.*;
+import com.oracle.graal.nodes.java.*;
+import com.oracle.graal.phases.schedule.*;
+import com.oracle.graal.virtual.phases.ea.ReadEliminationPEBlockState.ReadCacheEntry;
+
+public class ReadEliminationPEClosure extends PartialEscapeClosure<ReadEliminationPEBlockState> {
+
+    public ReadEliminationPEClosure(SchedulePhase schedule, MetaAccessProvider metaAccess, Assumptions assumptions) {
+        super(schedule, metaAccess, assumptions);
+    }
+
+    @Override
+    protected ReadEliminationPEBlockState getInitialState() {
+        return new ReadEliminationPEBlockState();
+    }
+
+    @Override
+    protected boolean processNode(Node node, ReadEliminationPEBlockState state, GraphEffectList effects, FixedWithNextNode lastFixedNode) {
+        boolean deleted = super.processNode(node, state, effects, lastFixedNode);
+        if (!deleted) {
+            if (node instanceof LoadFieldNode) {
+                LoadFieldNode load = (LoadFieldNode) node;
+                ValueNode cachedValue = state.getReadCache(load.object(), load.field());
+                if (cachedValue != null) {
+                    effects.replaceAtUsages(load, cachedValue);
+                    state.addScalarAlias(load, cachedValue);
+                } else {
+                    state.addReadCache(load.object(), load.field(), load);
+                }
+                deleted = true;
+            } else if (node instanceof StoreFieldNode) {
+                StoreFieldNode store = (StoreFieldNode) node;
+                ValueNode cachedValue = state.getReadCache(store.object(), store.field());
+
+                if (state.getScalarAlias(store.value()) == cachedValue) {
+                    effects.deleteFixedNode(store);
+                    deleted = true;
+                }
+                state.killReadCache(store.field());
+                state.addReadCache(store.object(), store.field(), store.value());
+            } else if (node instanceof MemoryCheckpoint.Single) {
+                METRIC_MEMORYCHECKOINT.increment();
+                LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
+                processIdentity(state, identity);
+            } else if (node instanceof MemoryCheckpoint.Multi) {
+                METRIC_MEMORYCHECKOINT.increment();
+                for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
+                    processIdentity(state, identity);
+                }
+            }
+        }
+        return deleted;
+    }
+
+    private static void processIdentity(ReadEliminationPEBlockState state, LocationIdentity identity) {
+        if (identity instanceof ResolvedJavaField) {
+            state.killReadCache((ResolvedJavaField) identity);
+        } else if (identity == ANY_LOCATION) {
+            state.killReadCache();
+        }
+    }
+
+    @Override
+    protected void processLoopExit(LoopExitNode exitNode, ReadEliminationPEBlockState initialState, ReadEliminationPEBlockState exitState, GraphEffectList effects) {
+        super.processLoopExit(exitNode, initialState, exitState, effects);
+
+        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, "readCacheProxy");
+                entry.setValue(proxy);
+            }
+        }
+    }
+
+    @Override
+    protected ReadEliminationPEBlockState cloneState(ReadEliminationPEBlockState other) {
+        return new ReadEliminationPEBlockState(other);
+    }
+
+    @Override
+    protected MergeProcessor createMergeProcessor(Block merge) {
+        return new ReadEliminationMergeProcessor(merge);
+    }
+
+    private class ReadEliminationMergeProcessor extends MergeProcessor {
+
+        public ReadEliminationMergeProcessor(Block mergeBlock) {
+            super(mergeBlock);
+        }
+
+        @Override
+        protected void merge(List<ReadEliminationPEBlockState> states) {
+            super.merge(states);
+
+            mergeReadCache(states);
+        }
+
+        private void mergeReadCache(List<ReadEliminationPEBlockState> states) {
+            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 = getCachedPhi(entry, value.kind());
+                    mergeEffects.addFloatingNode(phiNode, "mergeReadCache");
+                    for (int i = 0; i < states.size(); i++) {
+                        afterMergeEffects.addPhiInput(phiNode, states.get(i).getReadCache(key.object, key.identity));
+                    }
+                    newState.readCache.put(key, phiNode);
+                } else if (value != null) {
+                    newState.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);
+                        }
+                    }
+
+                }
+            }
+        }
+
+        private void mergeReadCachePhi(PhiNode phi, ResolvedJavaField identity, List<ReadEliminationPEBlockState> 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);
+                if (value == null) {
+                    return;
+                }
+                values[i] = value;
+            }
+
+            PhiNode phiNode = getCachedPhi(new ReadCacheEntry(identity, phi), values[0].kind());
+            mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi");
+            for (int i = 0; i < values.length; i++) {
+                afterMergeEffects.addPhiInput(phiNode, values[i]);
+            }
+            newState.readCache.put(new ReadCacheEntry(identity, phi), phiNode);
+        }
+    }
+}