Mercurial > hg > truffle
changeset 6524:a206e077ffc8
rename packages in graal.virtual to match project name
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Sun Oct 07 14:08:36 2012 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Sun Oct 07 14:11:55 2012 +0200 @@ -29,11 +29,11 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.*; import com.oracle.graal.compiler.phases.*; -import com.oracle.graal.compiler.phases.ea.*; import com.oracle.graal.compiler.test.*; import com.oracle.graal.debug.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; +import com.oracle.graal.virtual.phases.ea.*; /** * In these test cases the probability of all invokes is set to a high value, such that an InliningPhase should inline them all.
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Sun Oct 07 14:08:36 2012 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Sun Oct 07 14:11:55 2012 +0200 @@ -30,13 +30,13 @@ import com.oracle.graal.compiler.*; import com.oracle.graal.compiler.phases.*; -import com.oracle.graal.compiler.phases.ea.*; import com.oracle.graal.compiler.test.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.virtual.*; +import com.oracle.graal.virtual.nodes.*; +import com.oracle.graal.virtual.phases.ea.*; /** * In these test cases the probability of all invokes is set to a high value, such that an InliningPhase should inline
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Sun Oct 07 14:08:36 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Sun Oct 07 14:11:55 2012 +0200 @@ -33,8 +33,6 @@ import com.oracle.graal.compiler.gen.*; import com.oracle.graal.compiler.phases.*; import com.oracle.graal.compiler.phases.PhasePlan.PhasePosition; -import com.oracle.graal.compiler.phases.ea.*; -import com.oracle.graal.compiler.phases.ea.experimental.*; import com.oracle.graal.compiler.schedule.*; import com.oracle.graal.compiler.target.*; import com.oracle.graal.debug.*; @@ -44,6 +42,8 @@ import com.oracle.graal.loop.phases.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.virtual.phases.ea.*; +import com.oracle.graal.virtual.phases.ea.experimental.*; public class GraalCompiler {
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java Sun Oct 07 14:08:36 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/DebugInfoBuilder.java Sun Oct 07 14:11:55 2012 +0200 @@ -32,6 +32,7 @@ import com.oracle.graal.lir.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.virtual.*; +import com.oracle.graal.virtual.nodes.*; public class DebugInfoBuilder { private final NodeMap<Value> nodeOperands;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Sun Oct 07 14:08:36 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Sun Oct 07 14:11:55 2012 +0200 @@ -48,6 +48,7 @@ import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.virtual.*; +import com.oracle.graal.virtual.nodes.*; import com.oracle.max.asm.*; /**
--- a/graal/com.oracle.graal.snippets.test/src/com/oracle/graal/snippets/MonitorTest.java Sun Oct 07 14:08:36 2012 +0200 +++ b/graal/com.oracle.graal.snippets.test/src/com/oracle/graal/snippets/MonitorTest.java Sun Oct 07 14:11:55 2012 +0200 @@ -24,8 +24,8 @@ import org.junit.*; -import com.oracle.graal.compiler.phases.ea.*; import com.oracle.graal.compiler.test.*; +import com.oracle.graal.virtual.phases.ea.*; public class MonitorTest extends GraalCompilerTest {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/compiler/phases/ea/MergeableBlockState.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,29 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.phases.ea; - - -public interface MergeableBlockState<T> { - - T clone(); -}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/compiler/phases/ea/PartialEscapeAnalysisPhase.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1147 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.phases.ea; - -import java.util.*; - -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.api.meta.JavaType.*; -import com.oracle.graal.compiler.*; -import com.oracle.graal.compiler.phases.*; -import com.oracle.graal.compiler.schedule.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.PhiNode.PhiType; -import com.oracle.graal.nodes.VirtualState.NodeClosure; -import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.extended.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.nodes.virtual.*; - -class EscapeAnalysisIteration { - - // Metrics - private static final DebugMetric metricAllocationRemoved = Debug.metric("AllocationRemoved"); - private static final DebugMetric metricAllocationFieldsRemoved = Debug.metric("AllocationFieldsRemoved"); - private static final DebugMetric metricStoreRemoved = Debug.metric("StoreRemoved"); - private static final DebugMetric metricLoadRemoved = Debug.metric("LoadRemoved"); - private static final DebugMetric metricLockRemoved = Debug.metric("LockRemoved"); - private static final DebugMetric metricOtherRemoved = Debug.metric("OtherRemoved"); - private static final DebugMetric metricMaterializations = Debug.metric("Materializations"); - private static final DebugMetric metricMaterializationFields = Debug.metric("MaterializationFields"); - private static final DebugMetric metricLoopBailouts = Debug.metric("LoopBailouts"); - private static final DebugMetric metricMonitorBailouts = Debug.metric("MonitorBailouts"); - - - private static final ValueNode DUMMY_NODE = new ValueNode(null) { - }; - - 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)); - } - - private final StructuredGraph graph; - private final MetaAccessProvider runtime; - private final SchedulePhase schedule; - private final NodeBitMap usages; - boolean changed = false; - - private final boolean changeGraph; - - private final HashSet<VirtualObjectNode> reusedVirtualObjects = new HashSet<>(); - private final HashSet<ValueNode> allocations; - private final ArrayList<ValueNode> obsoleteNodes = new ArrayList<>(); - private int virtualIds = 0; - - public EscapeAnalysisIteration(StructuredGraph graph, SchedulePhase schedule, MetaAccessProvider runtime, HashSet<ValueNode> allocations, boolean changeGraph) { - this.graph = graph; - this.schedule = schedule; - this.runtime = runtime; - this.allocations = allocations; - this.changeGraph = changeGraph; - this.usages = graph.createNodeBitMap(); - } - - public void run() { - new PartialEscapeIterator(graph, schedule.getCFG().getStartBlock()).apply(); - - if (changeGraph) { - Debug.dump(graph, "after PartialEscapeAnalysis"); - - for (ValueNode node : obsoleteNodes) { - if (node.isAlive() && node instanceof FixedWithNextNode) { - FixedWithNextNode x = (FixedWithNextNode) node; - FixedNode next = x.next(); - x.setNext(null); - ((FixedWithNextNode) node.predecessor()).setNext(next); - } - } - new DeadCodeEliminationPhase().apply(graph); - - if (changed) { - Debug.log("escape analysis on %s\n", graph.method()); - } - } - } - - private static class ObjectState { - - public final VirtualObjectNode virtual; - public ValueNode[] fieldState; - public ValueNode materializedValue; - public int lockCount; - public boolean initialized; - - public ObjectState(VirtualObjectNode virtual, ValueNode[] fieldState, int lockCount) { - this.virtual = virtual; - this.fieldState = fieldState; - this.lockCount = lockCount; - this.initialized = false; - } - - public ObjectState(VirtualObjectNode virtual, ValueNode materializedValue, int lockCount) { - this.virtual = virtual; - this.materializedValue = materializedValue; - this.lockCount = lockCount; - this.initialized = true; - } - - private ObjectState(ObjectState other) { - virtual = other.virtual; - fieldState = other.fieldState == null ? null : other.fieldState.clone(); - materializedValue = other.materializedValue; - lockCount = other.lockCount; - initialized = other.initialized; - } - - @Override - public ObjectState clone() { - return new ObjectState(this); - } - - @Override - public String toString() { - StringBuilder str = new StringBuilder().append('{'); - if (lockCount > 0) { - str.append('l').append(lockCount).append(' '); - } - if (fieldState != null) { - for (int i = 0; i < fieldState.length; i++) { - str.append(virtual.fieldName(i)).append('=').append(fieldState[i]).append(' '); - } - } - if (materializedValue != null) { - str.append("mat=").append(materializedValue); - } - - return str.append('}').toString(); - } - } - - private class BlockState implements MergeableBlockState<BlockState> { - - private final HashMap<VirtualObjectNode, ObjectState> objectStates = new HashMap<>(); - private final HashMap<ValueNode, VirtualObjectNode> objectAliases = new HashMap<>(); - - public BlockState() { - } - - public BlockState(BlockState other) { - for (Map.Entry<VirtualObjectNode, ObjectState> entry : other.objectStates.entrySet()) { - objectStates.put(entry.getKey(), entry.getValue().clone()); - } - for (Map.Entry<ValueNode, VirtualObjectNode> entry : other.objectAliases.entrySet()) { - objectAliases.put(entry.getKey(), entry.getValue()); - } - } - - public ObjectState objectState(VirtualObjectNode object) { - assert objectStates.containsKey(object); - return objectStates.get(object); - } - - public ObjectState objectState(ValueNode value) { - VirtualObjectNode object = objectAliases.get(value); - return object == null ? null : objectState(object); - } - - @Override - public BlockState clone() { - return new BlockState(this); - } - - public void materializeBefore(FixedNode fixed, VirtualObjectNode virtual) { - if (changeGraph) { - HashSet<VirtualObjectNode> deferred = new HashSet<>(); - ArrayList<FixedWithNextNode> deferredStores = new ArrayList<>(); - materializeChangedBefore(fixed, virtual, deferred, deferredStores); - for (FixedWithNextNode write : deferredStores) { - write.setProbability(fixed.probability()); - graph.addBeforeFixed(fixed, write); - } - } else { - materializeUnchangedBefore(virtual); - } - } - - private void materializeUnchangedBefore(VirtualObjectNode virtual) { - trace("materializing %s", virtual); - ObjectState obj = objectState(virtual); - if (obj.lockCount > 0) { - if (changeGraph) { - error("object materialized with lock: %s\n", virtual); - } - metricMonitorBailouts.increment(); - throw new BailoutException("object materialized with lock"); - } - - ValueNode[] fieldState = obj.fieldState; - obj.fieldState = null; - obj.materializedValue = DUMMY_NODE; - for (int i = 0; i < fieldState.length; i++) { - ObjectState valueObj = objectState(fieldState[i]); - if (valueObj != null) { - if (valueObj.materializedValue == null) { - materializeUnchangedBefore(valueObj.virtual); - } - } - } - obj.initialized = true; - } - - private void materializeChangedBefore(FixedNode fixed, VirtualObjectNode virtual, HashSet<VirtualObjectNode> deferred, ArrayList<FixedWithNextNode> deferredStores) { - trace("materializing %s at %s", virtual, fixed); - ObjectState obj = objectState(virtual); - if (obj.lockCount > 0) { - error("object materialized with lock: %s\n", virtual); - metricMonitorBailouts.increment(); - throw new BailoutException("object materialized with lock"); - } - - MaterializeObjectNode materialize = graph.add(new MaterializeObjectNode(virtual, false)); - materialize.setProbability(fixed.probability()); - ValueNode[] fieldState = obj.fieldState; - metricMaterializations.increment(); - metricMaterializationFields.add(fieldState.length); - obj.fieldState = null; - obj.materializedValue = materialize; - deferred.add(virtual); - for (int i = 0; i < fieldState.length; i++) { - ObjectState valueObj = objectState(fieldState[i]); - if (valueObj != null) { - if (valueObj.materializedValue == null) { - materializeChangedBefore(fixed, valueObj.virtual, deferred, deferredStores); - } - if (deferred.contains(valueObj.virtual)) { - Kind fieldKind; - if (virtual instanceof VirtualArrayNode) { - deferredStores.add(graph.add(new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, i))); - fieldKind = ((VirtualArrayNode) virtual).componentType().kind(); - } else { - VirtualInstanceNode instanceObject = (VirtualInstanceNode) virtual; - deferredStores.add(graph.add(new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, instanceObject.field(i)))); - fieldKind = instanceObject.field(i).type().kind(); - } - materialize.values().set(i, ConstantNode.defaultForKind(fieldKind, graph)); - } else { - assert valueObj.initialized : "should be initialized: " + virtual + " at " + fixed; - materialize.values().set(i, valueObj.materializedValue); - } - } else { - materialize.values().set(i, fieldState[i]); - } - } - deferred.remove(virtual); - - obj.initialized = true; - graph.addBeforeFixed(fixed, materialize); - } - - private void addAndMarkAlias(VirtualObjectNode virtual, ValueNode node, boolean remove) { - objectAliases.put(node, virtual); - for (Node usage : node.usages()) { - markVirtualUsages(usage); - } - if (remove) { - obsoleteNodes.add(node); - } - } - - private void markVirtualUsages(Node node) { - if (!usages.isNew(node)) { - usages.mark(node); - } - if (node instanceof VirtualState) { - for (Node usage : node.usages()) { - markVirtualUsages(usage); - } - } - } - - public void addObject(VirtualObjectNode virtual, ObjectState state) { - objectStates.put(virtual, state); - } - - public Iterable<ObjectState> states() { - return objectStates.values(); - } - - @Override - public String toString() { - return objectStates.toString(); - } - } - - private class PartialEscapeIterator extends PostOrderBlockIterator<BlockState> { - - public PartialEscapeIterator(StructuredGraph graph, Block start) { - super(graph, start, new BlockState()); - } - - @Override - protected void processBlock(Block block, BlockState state) { - trace("\nBlock: %s (", block); - List<ScheduledNode> nodeList = schedule.getBlockToNodesMap().get(block); - - FixedWithNextNode lastFixedNode = null; - for (Node node : nodeList) { - EscapeOp op = null; - if (node instanceof EscapeAnalyzable) { - op = ((EscapeAnalyzable) node).getEscapeOp(); - } - if (op != null) { - // only escape analyze allocations that were escape analyzed during the first iteration - if (changeGraph && !allocations.contains(node)) { - op = null; - } - } - - if (op != null) { - trace("{{%s}} ", node); - VirtualObjectNode virtualObject = op.virtualObject(virtualIds); - if (virtualObject.isAlive()) { - reusedVirtualObjects.add(virtualObject); - state.addAndMarkAlias(virtualObject, virtualObject, false); - } else { - if (changeGraph) { - virtualObject = graph.add(virtualObject); - } - } - ValueNode[] fieldState = changeGraph ? op.fieldState() : new ValueNode[virtualObject.entryCount()]; - if (changeGraph) { - metricAllocationRemoved.increment(); - metricAllocationFieldsRemoved.add(fieldState.length); - } else { - allocations.add((ValueNode) node); - } - state.addObject(virtualObject, new ObjectState(virtualObject, fieldState, 0)); - state.addAndMarkAlias(virtualObject, (ValueNode) node, true); - virtualIds++; - } else { - if (changeGraph && node instanceof LoopExitNode) { - for (ObjectState obj : state.states()) { - if (obj.fieldState != null) { - for (int i = 0; i < obj.fieldState.length; i++) { - ValueNode value = obj.fieldState[i]; - ObjectState valueObj = state.objectState(value); - if (valueObj == null) { - obj.fieldState[i] = graph.unique(new ValueProxyNode(value, (LoopExitNode) node, PhiType.Value)); - } - } - } else { - obj.materializedValue = graph.unique(new ValueProxyNode(obj.materializedValue, (LoopExitNode) node, PhiType.Value)); - } - } - } - - if (usages.isMarked(node)) { - trace("[[%s]] ", node); - processNode((ValueNode) node, lastFixedNode == null ? null : lastFixedNode.next(), state); - } else { - trace("%s ", node); - } - } - - if (node instanceof FixedWithNextNode && node.isAlive()) { - lastFixedNode = (FixedWithNextNode) node; - } - } - trace(")\n end state: %s\n", state); - } - - private void processNode(final ValueNode node, FixedNode insertBefore, final BlockState state) { - boolean usageFound = false; - if (node instanceof PiNode || node instanceof ValueProxyNode) { - ValueNode value = node instanceof PiNode ? ((PiNode) node).object() : ((ValueProxyNode) node).value(); - ObjectState obj = state.objectState(value); - assert obj != null : node; - if (obj.materializedValue == null) { - state.addAndMarkAlias(obj.virtual, node, true); - } else { - if (changeGraph) { - node.replaceFirstInput(value, obj.materializedValue); - } - } - usageFound = true; - } else if (node instanceof CheckCastNode) { - CheckCastNode x = (CheckCastNode) node; - ObjectState obj = state.objectState(x.object()); - assert obj != null : x; - if (obj.materializedValue == null) { - if (x.targetClass() != null && obj.virtual.type().isSubtypeOf(x.targetClass())) { - metricOtherRemoved.increment(); - state.addAndMarkAlias(obj.virtual, x, true); - // throw new UnsupportedOperationException("probably incorrect - losing dependency"); - } else { - replaceWithMaterialized(x.object(), x, state, obj); - } - } else { - if (changeGraph) { - node.replaceFirstInput(x.object(), obj.materializedValue); - } - } - usageFound = true; - } else if (node instanceof IsNullNode) { - IsNullNode x = (IsNullNode) node; - ObjectState obj = state.objectState(x.object()); - assert obj != null : x; - if (changeGraph) { - graph.replaceFloating(x, graph.unique(ConstantNode.forBoolean(false, graph))); - metricOtherRemoved.increment(); - } - usageFound = true; - } else if (node instanceof AccessMonitorNode) { - AccessMonitorNode x = (AccessMonitorNode) node; - ObjectState obj = state.objectState(x.object()); - if (obj != null) { - Debug.log("monitor operation %s on %s\n", x, obj.virtual); - if (node instanceof MonitorEnterNode) { - obj.lockCount++; - } else { - assert node instanceof MonitorExitNode; - obj.lockCount--; - } - if (changeGraph) { - changed = true; - if (obj.materializedValue == null) { - metricLockRemoved.increment(); - node.replaceFirstInput(x.object(), obj.virtual); - x.eliminate(); - } else { - node.replaceFirstInput(x.object(), obj.materializedValue); - } - } - usageFound = true; - } - } else if (node instanceof CyclicMaterializeStoreNode) { - CyclicMaterializeStoreNode x = (CyclicMaterializeStoreNode) node; - ObjectState obj = state.objectState(x.object()); - assert obj != null : x; - if (obj.virtual instanceof VirtualArrayNode) { - obj.fieldState[x.targetIndex()] = x.value(); - } else { - VirtualInstanceNode instance = (VirtualInstanceNode) obj.virtual; - int index = instance.fieldIndex(x.targetField()); - obj.fieldState[index] = x.value(); - } - if (changeGraph) { - graph.removeFixed(x); - } - usageFound = true; - } else if (node instanceof LoadFieldNode) { - LoadFieldNode x = (LoadFieldNode) node; - ObjectState obj = state.objectState(x.object()); - assert obj != null : x; - VirtualInstanceNode virtual = (VirtualInstanceNode) obj.virtual; - int fieldIndex = virtual.fieldIndex(x.field()); - if (fieldIndex == -1) { - // the field does not exist in the virtual object - ensureMaterialized(state, obj, x); - } - if (obj.materializedValue == null) { - ValueNode result = obj.fieldState[fieldIndex]; - ObjectState resultObj = state.objectState(result); - if (resultObj != null) { - state.addAndMarkAlias(resultObj.virtual, x, true); - } else { - if (changeGraph) { - x.replaceAtUsages(result); - graph.removeFixed(x); - } - } - if (changeGraph) { - metricLoadRemoved.increment(); - } - changed = true; - } else { - if (changeGraph) { - x.replaceFirstInput(x.object(), obj.materializedValue); - } - } - usageFound = true; - } else if (node instanceof StoreFieldNode) { - StoreFieldNode x = (StoreFieldNode) node; - ValueNode object = x.object(); - ValueNode value = x.value(); - ObjectState obj = state.objectState(object); - if (obj != null) { - VirtualInstanceNode virtual = (VirtualInstanceNode) obj.virtual; - int fieldIndex = virtual.fieldIndex(x.field()); - if (fieldIndex == -1) { - // the field does not exist in the virtual object - ensureMaterialized(state, obj, x); - } - if (obj.materializedValue == null) { - obj.fieldState[fieldIndex] = value; - if (changeGraph) { - graph.removeFixed(x); - metricStoreRemoved.increment(); - } - changed = true; - } else { - if (changeGraph) { - x.replaceFirstInput(object, obj.materializedValue); - } - ObjectState valueObj = state.objectState(value); - if (valueObj != null) { - replaceWithMaterialized(value, x, state, valueObj); - } - } - usageFound = true; - } else { - ObjectState valueObj = state.objectState(value); - if (valueObj != null) { - replaceWithMaterialized(value, x, state, valueObj); - usageFound = true; - } - } - } else if (node instanceof LoadIndexedNode) { - LoadIndexedNode x = (LoadIndexedNode) node; - ValueNode array = x.array(); - ObjectState arrayObj = state.objectState(array); - if (arrayObj != null) { - if (arrayObj.materializedValue == null) { - int index = x.index().isConstant() ? x.index().asConstant().asInt() : -1; - if (index < 0 || index >= arrayObj.fieldState.length) { - // out of bounds or not constant - replaceWithMaterialized(array, x, state, arrayObj); - } else { - ValueNode result = arrayObj.fieldState[index]; - ObjectState resultObj = state.objectState(result); - if (resultObj != null) { - state.addAndMarkAlias(resultObj.virtual, x, true); - } else { - if (changeGraph) { - x.replaceAtUsages(result); - graph.removeFixed(x); - } - } - if (changeGraph) { - metricLoadRemoved.increment(); - } - changed = true; - } - } else { - if (changeGraph) { - x.replaceFirstInput(array, arrayObj.materializedValue); - } - } - usageFound = true; - } - } else if (node instanceof StoreIndexedNode) { - StoreIndexedNode x = (StoreIndexedNode) node; - ValueNode array = x.array(); - ValueNode value = x.value(); - ObjectState arrayObj = state.objectState(array); - ObjectState valueObj = state.objectState(value); - - if (arrayObj != null) { - if (arrayObj.materializedValue == null) { - int index = x.index().isConstant() ? x.index().asConstant().asInt() : -1; - if (index < 0 || index >= arrayObj.fieldState.length) { - // out of bounds or not constant - replaceWithMaterialized(array, x, state, arrayObj); - if (valueObj != null) { - replaceWithMaterialized(value, x, state, valueObj); - } - } else { - arrayObj.fieldState[index] = value; - if (changeGraph) { - graph.removeFixed(x); - metricStoreRemoved.increment(); - } - changed = true; - } - } else { - if (changeGraph) { - x.replaceFirstInput(array, arrayObj.materializedValue); - } - if (valueObj != null) { - replaceWithMaterialized(value, x, state, valueObj); - } - } - usageFound = true; - } else { - if (valueObj != null) { - replaceWithMaterialized(value, x, state, valueObj); - usageFound = true; - } - } - } else if (node instanceof RegisterFinalizerNode) { - RegisterFinalizerNode x = (RegisterFinalizerNode) node; - ObjectState obj = state.objectState(x.object()); - replaceWithMaterialized(x.object(), x, state, obj); - usageFound = true; - } else if (node instanceof ArrayLengthNode) { - ArrayLengthNode x = (ArrayLengthNode) node; - ObjectState obj = state.objectState(x.array()); - assert obj != null : x; - if (changeGraph) { - graph.replaceFixedWithFloating(x, ConstantNode.forInt(((VirtualArrayNode) obj.virtual).entryCount(), graph)); - metricOtherRemoved.increment(); - } - changed = true; - usageFound = true; - } else if (node instanceof LoadHubNode) { - LoadHubNode x = (LoadHubNode) node; - ObjectState obj = state.objectState(x.object()); - assert obj != null : x; - if (changeGraph) { - ConstantNode hub = ConstantNode.forConstant(obj.virtual.type().getEncoding(Representation.ObjectHub), runtime, graph); - graph.replaceFixedWithFloating(x, hub); - metricOtherRemoved.increment(); - } - changed = true; - usageFound = true; - } else if (node instanceof ReturnNode) { - ReturnNode x = (ReturnNode) node; - ObjectState obj = state.objectState(x.result()); - replaceWithMaterialized(x.result(), x, state, obj); - usageFound = true; - } else if (node instanceof MethodCallTargetNode) { - for (ValueNode argument : ((MethodCallTargetNode) node).arguments()) { - ObjectState obj = state.objectState(argument); - if (obj != null) { - replaceWithMaterialized(argument, node, insertBefore, state, obj); - usageFound = true; - } - } - } else if (node instanceof ObjectEqualsNode) { - ObjectEqualsNode x = (ObjectEqualsNode) node; - ObjectState xObj = state.objectState(x.x()); - ObjectState yObj = state.objectState(x.y()); - boolean xVirtual = xObj != null && xObj.materializedValue == null; - boolean yVirtual = yObj != null && yObj.materializedValue == null; - - if (changeGraph) { - if (xVirtual ^ yVirtual) { - // one of them is virtual: they can never be the same objects - graph.replaceFloating(x, ConstantNode.forBoolean(false, graph)); - usageFound = true; - metricOtherRemoved.increment(); - changed = true; - } else if (xVirtual && yVirtual) { - // both are virtual: check if they refer to the same object - graph.replaceFloating(x, ConstantNode.forBoolean(xObj == yObj, graph)); - usageFound = true; - metricOtherRemoved.increment(); - changed = true; - } else { - assert xObj != null || yObj != null; - if (xObj != null) { - assert xObj.materializedValue != null; - node.replaceFirstInput(x.x(), xObj.materializedValue); - } - if (yObj != null) { - assert yObj.materializedValue != null; - node.replaceFirstInput(x.y(), yObj.materializedValue); - } - } - } - usageFound = true; - } else if (node instanceof MergeNode) { - usageFound = true; - } else if (node instanceof UnsafeLoadNode || node instanceof UnsafeStoreNode || node instanceof CompareAndSwapNode || node instanceof SafeReadNode) { - for (ValueNode input : node.inputs().filter(ValueNode.class)) { - ObjectState obj = state.objectState(input); - if (obj != null) { - replaceWithMaterialized(input, node, insertBefore, state, obj); - usageFound = true; - } - } - } - if (node.isAlive() && node instanceof StateSplit) { - StateSplit split = (StateSplit) node; - FrameState stateAfter = split.stateAfter(); - if (stateAfter != null) { - if (changeGraph) { - if (stateAfter.usages().size() > 1) { - stateAfter = (FrameState) stateAfter.copyWithInputs(); - split.setStateAfter(stateAfter); - } - final HashSet<ObjectState> virtual = new HashSet<>(); - stateAfter.applyToNonVirtual(new NodeClosure<ValueNode>() { - - @Override - public void apply(Node usage, ValueNode value) { - ObjectState valueObj = state.objectState(value); - if (valueObj != null) { - virtual.add(valueObj); - usage.replaceFirstInput(value, valueObj.virtual); - } else if (value instanceof VirtualObjectNode) { - ObjectState virtualObj = null; - for (ObjectState obj : state.states()) { - if (value == obj.virtual) { - virtualObj = obj; - break; - } - } - if (virtualObj != null) { - virtual.add(virtualObj); - } - } - } - }); - for (ObjectState obj : state.states()) { - if (obj.materializedValue == null && obj.lockCount > 0) { - virtual.add(obj); - } - } - - ArrayDeque<ObjectState> queue = new ArrayDeque<>(virtual); - while (!queue.isEmpty()) { - ObjectState obj = queue.removeLast(); - if (obj.materializedValue == null) { - for (ValueNode field : obj.fieldState) { - ObjectState fieldObj = state.objectState(field); - if (fieldObj != null) { - if (fieldObj.materializedValue == null && !virtual.contains(fieldObj)) { - virtual.add(fieldObj); - queue.addLast(fieldObj); - } - } - } - } - } - for (ObjectState obj : virtual) { - EscapeObjectState v; - if (obj.materializedValue == null) { - ValueNode[] fieldState = obj.fieldState.clone(); - for (int i = 0; i < fieldState.length; i++) { - ObjectState valueObj = state.objectState(fieldState[i]); - if (valueObj != null) { - if (valueObj.materializedValue == null) { - fieldState[i] = valueObj.virtual; - } else { - fieldState[i] = valueObj.materializedValue; - } - } - } - v = graph.add(new VirtualObjectState(obj.virtual, fieldState)); - } else { - v = graph.add(new MaterializedObjectState(obj.virtual, obj.materializedValue)); - } - for (int i = 0; i < stateAfter.virtualObjectMappingCount(); i++) { - if (stateAfter.virtualObjectMappingAt(i).object() == v.object()) { - if (reusedVirtualObjects.contains(v.object())) { - stateAfter.virtualObjectMappings().remove(i); - } else { - throw new GraalInternalError("unexpected duplicate virtual state at: %s for %s", node, v.object()); - } - } - } - stateAfter.addVirtualObjectMapping(v); - } - } - usageFound = true; - } - } - if (!usageFound) { - for (ValueNode input : node.inputs().filter(ValueNode.class)) { - ObjectState obj = state.objectState(input); - if (obj != null) { - replaceWithMaterialized(input, node, insertBefore, state, obj); - usageFound = true; - } - } - Debug.log("unexpected usage of %s: %s\n", node, node.inputs().snapshot()); - } - } - - private void ensureMaterialized(BlockState state, ObjectState obj, FixedNode materializeBefore) { - assert obj != null; - if (obj.materializedValue == null) { - state.materializeBefore(materializeBefore, obj.virtual); - } - assert obj.materializedValue != null; - } - - private void replaceWithMaterialized(ValueNode value, FixedNode usage, BlockState state, ObjectState obj) { - ensureMaterialized(state, obj, usage); - if (changeGraph) { - usage.replaceFirstInput(value, obj.materializedValue); - } - } - - private void replaceWithMaterialized(ValueNode value, Node usage, FixedNode materializeBefore, BlockState state, ObjectState obj) { - ensureMaterialized(state, obj, materializeBefore); - if (changeGraph) { - usage.replaceFirstInput(value, obj.materializedValue); - } - } - - @Override - protected BlockState merge(MergeNode merge, List<BlockState> states) { - BlockState newState = new BlockState(); - - newState.objectAliases.putAll(states.get(0).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()) { - if (state.objectAliases.containsKey(entry.getKey())) { - assert state.objectAliases.get(entry.getKey()) == entry.getValue(); - } else { - newState.objectAliases.remove(entry.getKey()); - } - } - } - - // Iterative processing: - // Merging the materialized/virtual state of virtual objects can lead to new materializations, which can - // lead to new materializations because of phis, and so on. - - boolean materialized; - do { - materialized = false; - // use a hash set to make the values distinct... - for (VirtualObjectNode object : new HashSet<>(newState.objectAliases.values())) { - ObjectState resultState = newState.objectStates.get(object); - if (resultState == null || resultState.materializedValue == null) { - int virtual = 0; - int lockCount = states.get(0).objectState(object).lockCount; - for (BlockState state : states) { - ObjectState obj = state.objectState(object); - if (obj.materializedValue == null) { - virtual++; - } - assert obj.lockCount == lockCount : "mismatching lock counts"; - } - - if (virtual < states.size()) { - ValueNode materializedValuePhi = changeGraph ? graph.add(new PhiNode(Kind.Object, merge)) : DUMMY_NODE; - for (int i = 0; i < states.size(); i++) { - BlockState state = states.get(i); - ObjectState obj = state.objectState(object); - materialized |= obj.materializedValue == null; - ensureMaterialized(state, obj, merge.forwardEndAt(i)); - if (changeGraph) { - ((PhiNode) materializedValuePhi).addInput(obj.materializedValue); - } - } - newState.addObject(object, new ObjectState(object, materializedValuePhi, lockCount)); - } else { - assert virtual == states.size(); - ValueNode[] values = states.get(0).objectState(object).fieldState.clone(); - PhiNode[] phis = new PhiNode[values.length]; - boolean[] phiCreated = new boolean[values.length]; - int mismatch = 0; - for (int i = 1; i < states.size(); i++) { - BlockState state = states.get(i); - ValueNode[] fields = state.objectState(object).fieldState; - for (int index = 0; index < values.length; index++) { - if (!phiCreated[index] && values[index] != fields[index]) { - mismatch++; - if (changeGraph) { - phis[index] = graph.add(new PhiNode(values[index].kind(), merge)); - } - phiCreated[index] = true; - } - } - } - if (mismatch > 0) { - for (int i = 0; i < states.size(); i++) { - BlockState state = states.get(i); - ValueNode[] fields = state.objectState(object).fieldState; - for (int index = 0; index < values.length; index++) { - if (phiCreated[index]) { - ObjectState obj = state.objectState(fields[index]); - if (obj != null) { - materialized |= obj.materializedValue == null; - ensureMaterialized(state, obj, merge.forwardEndAt(i)); - fields[index] = obj.materializedValue; - } - if (changeGraph) { - phis[index].addInput(fields[index]); - } - } - } - } - for (int index = 0; index < values.length; index++) { - if (phiCreated[index]) { - values[index] = phis[index]; - } - } - } - newState.addObject(object, new ObjectState(object, values, lockCount)); - } - } - } - - for (PhiNode phi : merge.phis().snapshot()) { - if (usages.isMarked(phi) && phi.type() == PhiType.Value) { - materialized |= processPhi(newState, merge, phi, states); - } - } - } while (materialized); - - return newState; - } - - private boolean processPhi(BlockState newState, MergeNode merge, PhiNode phi, List<BlockState> states) { - assert states.size() == phi.valueCount(); - int virtualInputs = 0; - boolean materialized = false; - VirtualObjectNode sameObject = null; - ResolvedJavaType sameType = null; - int sameEntryCount = -1; - for (int i = 0; i < phi.valueCount(); i++) { - ValueNode value = phi.valueAt(i); - ObjectState obj = states.get(i).objectState(value); - if (obj != null) { - if (obj.materializedValue == null) { - virtualInputs++; - if (i == 0) { - sameObject = obj.virtual; - sameType = obj.virtual.type(); - sameEntryCount = obj.virtual.entryCount(); - } else { - if (sameObject != obj.virtual) { - sameObject = null; - } - if (sameType != obj.virtual.type()) { - sameType = null; - } - if (sameEntryCount != obj.virtual.entryCount()) { - sameEntryCount = -1; - } - } - } else { - if (changeGraph) { - phi.setValueAt(i, obj.materializedValue); - } - } - } - } - boolean materialize = false; - if (virtualInputs == 0) { - // nothing to do... - } else if (virtualInputs == phi.valueCount()) { - if (sameObject != null) { - newState.addAndMarkAlias(sameObject, phi, true); - } else if (sameType != null && sameEntryCount != -1) { - materialize = true; - // throw new GraalInternalError("merge required for %s", sameType); - } else { - materialize = true; - } - } else { - materialize = true; - } - - if (materialize) { - for (int i = 0; i < phi.valueCount(); i++) { - ValueNode value = phi.valueAt(i); - ObjectState obj = states.get(i).objectState(value); - if (obj != null) { - materialized |= obj.materializedValue == null; - replaceWithMaterialized(value, phi, merge.forwardEndAt(i), states.get(i), obj); - } - } - } - return materialized; - } - - @Override - protected BlockState loopBegin(LoopBeginNode loopBegin, BlockState beforeLoopState) { - BlockState state = beforeLoopState; - for (ObjectState obj : state.states()) { - if (obj.fieldState != null) { - for (int i = 0; obj.fieldState != null && i < obj.fieldState.length; i++) { - ValueNode value = obj.fieldState[i]; - ObjectState valueObj = state.objectState(value); - if (valueObj != null) { - ensureMaterialized(state, valueObj, loopBegin.forwardEnd()); - value = valueObj.materializedValue; - } - } - } - } - for (ObjectState obj : state.states()) { - if (obj.fieldState != null) { - for (int i = 0; i < obj.fieldState.length; i++) { - ValueNode value = obj.fieldState[i]; - ObjectState valueObj = state.objectState(value); - if (valueObj != null) { - value = valueObj.materializedValue; - } - if (changeGraph) { - assert value != null; - PhiNode valuePhi = graph.add(new PhiNode(value.kind(), loopBegin)); - valuePhi.addInput(value); - obj.fieldState[i] = valuePhi; - } - } - } - } - for (PhiNode phi : loopBegin.phis()) { - ObjectState obj = state.objectState(phi.valueAt(0)); - if (obj != null) { - ensureMaterialized(state, obj, loopBegin.forwardEnd()); - if (changeGraph) { - phi.setValueAt(0, obj.materializedValue); - } - } - } - return state.clone(); - } - - @Override - protected BlockState loopEnds(LoopBeginNode loopBegin, BlockState loopBeginState, List<BlockState> loopEndStates) { - BlockState state = loopBeginState.clone(); - List<LoopEndNode> loopEnds = loopBegin.orderedLoopEnds(); - for (ObjectState obj : state.states()) { - if (obj.fieldState != null) { - Iterator<LoopEndNode> iter = loopEnds.iterator(); - for (BlockState loopEndState : loopEndStates) { - LoopEndNode loopEnd = iter.next(); - ObjectState endObj = loopEndState.objectState(obj.virtual); - if (endObj.fieldState == null) { - if (changeGraph) { - error("object materialized within loop: %s\n", obj.virtual); - } - metricLoopBailouts.increment(); - throw new BailoutException("object materialized within loop"); - } - for (int i = 0; endObj.fieldState != null && i < endObj.fieldState.length; i++) { - ValueNode value = endObj.fieldState[i]; - ObjectState valueObj = loopEndState.objectState(value); - if (valueObj != null) { - ensureMaterialized(loopEndState, valueObj, loopEnd); - value = valueObj.materializedValue; - } - if (changeGraph) { - ((PhiNode) obj.fieldState[i]).addInput(value); - } - } - } - } - } - for (PhiNode phi : loopBegin.phis()) { - if (phi.valueCount() == 1) { - if (changeGraph) { - phi.replaceAtUsages(phi.valueAt(0)); - } - } else { - assert phi.valueCount() == loopEndStates.size() + 1; - for (int i = 0; i < loopEndStates.size(); i++) { - BlockState loopEndState = loopEndStates.get(i); - ObjectState obj = loopEndState.objectState(phi.valueAt(i + 1)); - if (obj != null) { - ensureMaterialized(loopEndState, obj, loopEnds.get(i)); - if (changeGraph) { - phi.setValueAt(i + 1, obj.materializedValue); - } - } - } - } - } - return state; - } - - @Override - protected BlockState afterSplit(FixedNode node, BlockState oldState) { - return oldState.clone(); - } - } -} - -public class PartialEscapeAnalysisPhase extends Phase { - - private final TargetDescription target; - private final GraalCodeCacheProvider runtime; - private final Assumptions assumptions; - - public PartialEscapeAnalysisPhase(TargetDescription target, GraalCodeCacheProvider runtime, Assumptions assumptions) { - this.runtime = runtime; - this.target = target; - this.assumptions = assumptions; - } - - @Override - protected void run(StructuredGraph graph) { - iteration(graph, 0); - } - - - private void iteration(final StructuredGraph graph, final int num) { - HashSet<ValueNode> allocations = new HashSet<>(); - SchedulePhase schedule = new SchedulePhase(); - schedule.apply(graph, false); - EscapeAnalysisIteration iteration = null; - try { - iteration = new EscapeAnalysisIteration(graph, schedule, runtime, allocations, false); - iteration.run(); - } catch (BailoutException e) { - // do nothing if the if the escape analysis bails out during the analysis iteration... - return; - } - if (iteration.changed) { - try { - new EscapeAnalysisIteration(graph, schedule, runtime, allocations, true).run(); - new CanonicalizerPhase(target, runtime, assumptions).apply(graph); - } catch (BailoutException e) { - throw new GraalInternalError(e); - } - // next round... - if (num < 2) { - Debug.scope("next", new Runnable() { - @Override - public void run() { - iteration(graph, num + 1); - } - }); - } - } - } -} -
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/compiler/phases/ea/PostOrderBlockIterator.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,183 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.phases.ea; - -import java.util.*; - -import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; -import com.oracle.graal.nodes.*; - -public abstract class PostOrderBlockIterator<T extends MergeableBlockState<T>> { - - private final NodeBitMap visitedEnds; - private final Deque<Block> blockQueue; - private final IdentityHashMap<FixedNode, T> blockEndStates; - private final IdentityHashMap<LoopBeginNode, T> loopBeginStates; - private final Block start; - - private T state; - - public PostOrderBlockIterator(StructuredGraph graph, Block start, T initialState) { - visitedEnds = graph.createNodeBitMap(); - blockQueue = new ArrayDeque<>(); - blockEndStates = new IdentityHashMap<>(); - loopBeginStates = new IdentityHashMap<>(); - this.start = start; - this.state = initialState; - } - - public void apply() { - Block current = start; - - do { - processBlock(current, state); - - if (current.getSuccessors().isEmpty()) { - // nothing to do... - } else if (current.getSuccessors().size() == 1) { - Block successor = current.getSuccessors().get(0); - if (successor.isLoopHeader()) { - if (current.getEndNode() instanceof LoopEndNode) { - finishLoopEnds((LoopEndNode) current.getEndNode()); - } else { - LoopBeginNode loopBegin = (LoopBeginNode) successor.getBeginNode(); - state = loopBegin(loopBegin, state); - loopBeginStates.put(loopBegin, state); - state = state.clone(); - current = successor; - continue; - } - } else { - if (successor.getBeginNode() instanceof LoopExitNode) { - assert successor.getPredecessors().size() == 1; - current = successor; - continue; - } else { - if (current.getEndNode() instanceof EndNode) { - assert successor.getPredecessors().size() > 1 : "invalid block schedule at " + successor.getBeginNode(); - queueMerge((EndNode) current.getEndNode(), successor); - } else { - assert successor.getPredecessors().size() == 1 : "invalid block schedule at " + successor.getBeginNode(); - current = successor; - continue; - } - } - } - } else { - assert current.getSuccessors().size() > 1; - queueSuccessors(current); - } - current = nextQueuedBlock(); - } while (current != null); - } - - protected abstract void processBlock(Block block, T currentState); - - protected abstract T merge(MergeNode merge, List<T> states); - - protected abstract T loopBegin(LoopBeginNode loopBegin, T beforeLoopState); - - protected abstract T loopEnds(LoopBeginNode loopBegin, T loopBeginState, List<T> loopEndStates); - - protected abstract T afterSplit(FixedNode node, T oldState); - - - private void queueSuccessors(Block current) { - blockEndStates.put(current.getEndNode(), state); - for (Block block : current.getSuccessors()) { - blockQueue.addFirst(block); - } - } - - private Block nextQueuedBlock() { - int maxIterations = blockQueue.size(); - while (maxIterations-- > 0) { - Block block = blockQueue.removeFirst(); - if (block.getPredecessors().size() > 1) { - MergeNode merge = (MergeNode) block.getBeginNode(); - ArrayList<T> states = new ArrayList<>(merge.forwardEndCount()); - for (int i = 0; i < merge.forwardEndCount(); i++) { - T other = blockEndStates.get(merge.forwardEndAt(i)); - assert other != null; - states.add(other); - } - state = merge(merge, states); - if (state != null) { - return block; - } else { - blockQueue.addLast(block); - } - } else { - assert block.getPredecessors().size() == 1; - assert block.getBeginNode().predecessor() != null; - state = afterSplit(block.getBeginNode(), blockEndStates.get(block.getBeginNode().predecessor())); - return block; - } - } - return null; - } - - private void queueMerge(EndNode end, Block mergeBlock) { - assert !visitedEnds.isMarked(end); - assert !blockEndStates.containsKey(end); - blockEndStates.put(end, state); - visitedEnds.mark(end); - MergeNode merge = end.merge(); - boolean endsVisited = true; - for (int i = 0; i < merge.forwardEndCount(); i++) { - if (!visitedEnds.isMarked(merge.forwardEndAt(i))) { - endsVisited = false; - break; - } - } - if (endsVisited) { - blockQueue.addFirst(mergeBlock); - } - } - - private void finishLoopEnds(LoopEndNode end) { - assert !visitedEnds.isMarked(end); - assert !blockEndStates.containsKey(end); - blockEndStates.put(end, state); - visitedEnds.mark(end); - LoopBeginNode begin = end.loopBegin(); - boolean endsVisited = true; - for (LoopEndNode le : begin.loopEnds()) { - if (!visitedEnds.isMarked(le)) { - endsVisited = false; - break; - } - } - if (endsVisited) { - ArrayList<T> states = new ArrayList<>(begin.loopEnds().count()); - for (LoopEndNode le : begin.orderedLoopEnds()) { - states.add(blockEndStates.get(le)); - } - T loopBeginState = loopBeginStates.get(begin); - if (loopBeginState != null) { - loopEnds(begin, loopBeginState, states); - } - } - } -}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/compiler/phases/ea/experimental/BlockIteratorClosure.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,46 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.phases.ea.experimental; - -import java.util.*; - -import com.oracle.graal.compiler.phases.ea.*; -import com.oracle.graal.lir.cfg.*; -import com.oracle.graal.nodes.*; - -public abstract class BlockIteratorClosure<T extends MergeableBlockState<T>> { - - public static class LoopInfo<T extends MergeableBlockState<T>> { - - public final List<T> endStates = new ArrayList<>(); - public final List<T> exitStates = new ArrayList<>(); - } - - protected abstract void processBlock(Block block, T currentState); - - protected abstract T merge(MergeNode merge, List<T> states); - - protected abstract T afterSplit(FixedNode node, T oldState); - - protected abstract List<T> processLoop(Loop loop, T initialState); -}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/compiler/phases/ea/experimental/EffectList.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,181 +0,0 @@ -/* - * Copyright (c) 2012, 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.phases.ea.experimental; - -import java.lang.reflect.*; -import java.util.*; - -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; - -public class EffectList implements Iterable<EffectList.Effect> { - - public abstract static class Effect { - - public boolean isVisible() { - return true; - } - - @Override - public String toString() { - StringBuilder str = new StringBuilder(); - for (Field field : getClass().getDeclaredFields()) { - String name = field.getName(); - if (name.contains("$")) { - name = name.substring(name.indexOf('$') + 1); - } - if (!Modifier.isStatic(field.getModifiers()) && !name.equals("0")) { - try { - field.setAccessible(true); - str.append(str.length() > 0 ? ", " : "").append(name).append("=").append(format(field.get(this))); - } catch (Exception e) { - e.printStackTrace(); - } - } - } - return name() + " [" + str + "]"; - } - - private static String format(Object object) { - if (object != null && Object[].class.isAssignableFrom(object.getClass())) { - return Arrays.toString((Object[]) object); - } - return "" + object; - } - - public abstract String name(); - - public abstract void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes); - } - - private Effect[] effects = new Effect[16]; - private int[] level = new int[16]; - private int size; - private int currentLevel; - - public void add(Effect effect) { - if (effects.length == size) { - effects = Arrays.copyOf(effects, effects.length * 2); - level = Arrays.copyOf(level, effects.length); - } - level[size] = currentLevel; - effects[size++] = effect; - } - - public void addAll(Collection< ? extends Effect> list) { - int length = effects.length; - if (size + list.size() > length) { - while (size + list.size() > length) { - length *= 2; - } - effects = Arrays.copyOf(effects, length); - level = Arrays.copyOf(level, effects.length); - } - for (Effect effect : list) { - level[size] = currentLevel; - effects[size++] = effect; - } - } - - public void addAll(EffectList list) { - int length = effects.length; - if (size + list.size > length) { - while (size + list.size > length) { - length *= 2; - } - effects = Arrays.copyOf(effects, length); - level = Arrays.copyOf(level, effects.length); - } - for (Effect effect : list) { - level[size] = currentLevel; - effects[size++] = effect; - } - } - - public int checkpoint() { - return size; - } - - public int size() { - return size; - } - - public void backtrack(int checkpoint) { - assert checkpoint <= size; - size = checkpoint; - } - - @Override - public Iterator<Effect> iterator() { - return new Iterator<Effect>() { - - int index; - final int listSize = EffectList.this.size; - - @Override - public boolean hasNext() { - return index < listSize; - } - - @Override - public Effect next() { - return effects[index++]; - } - - @Override - public void remove() { - throw new UnsupportedOperationException(); - } - }; - } - - public void incLevel() { - currentLevel++; - } - - public void decLevel() { - currentLevel--; - } - - public Effect get(int index) { - if (index >= size) { - throw new IndexOutOfBoundsException(); - } - return effects[index]; - } - - public int levelAt(int index) { - if (index >= size) { - throw new IndexOutOfBoundsException(); - } - return level[index]; - } - - public void clear() { - size = 0; - } - - public boolean isEmpty() { - return size == 0; - } -}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/compiler/phases/ea/experimental/GraphEffectList.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,222 +0,0 @@ -/* - * Copyright (c) 2012, 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.phases.ea.experimental; - -import java.util.*; - -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.virtual.*; - -public class GraphEffectList extends EffectList { - - public void addFixedNodeBefore(final FixedWithNextNode node, final FixedNode position) { - add(new Effect() { - - @Override - public String name() { - return "addFixedNodeBefore"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert !node.isAlive() && !node.isDeleted() && position.isAlive(); - graph.addBeforeFixed(position, graph.add(node)); - node.setProbability(position.probability()); - } - }); - } - - public void addFloatingNode(final FloatingNode node) { - add(new Effect() { - - @Override - public String name() { - return "addFloatingNode"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert !node.isAlive() && !node.isDeleted(); - graph.add(node); - } - }); - } - - public void addMaterialization(final MaterializeObjectNode node, final FixedNode position, final ValueNode[] values) { - add(new Effect() { - - @Override - public String name() { - return "addMaterialization"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert !node.isAlive() && !node.isDeleted() && position.isAlive(); - graph.addBeforeFixed(position, graph.add(node)); - node.setProbability(position.probability()); - for (int i = 0; i < values.length; i++) { - node.values().set(i, values[i]); - } - } - }); - } - - public void addPhiInput(final PhiNode node, final ValueNode value) { - add(new Effect() { - - @Override - public String name() { - return "addPhiInput"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert node.isAlive() && value.isAlive(); - node.addInput(value); - } - }); - } - - public void addVirtualMapping(final FrameState node, final EscapeObjectState state, final HashSet<VirtualObjectNode> reusedVirtualObjects) { - add(new Effect() { - - @Override - public String name() { - return "addVirtualMapping"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert node.isAlive() && !state.isAlive() && !state.isDeleted(); - FrameState stateAfter = node; - for (int i = 0; i < stateAfter.virtualObjectMappingCount(); i++) { - if (stateAfter.virtualObjectMappingAt(i).object() == state.object()) { - if (reusedVirtualObjects.contains(state.object())) { - stateAfter.virtualObjectMappings().remove(i); - } else { - throw new GraalInternalError("unexpected duplicate virtual state at: %s for %s", stateAfter, state.object()); - } - } - } - stateAfter.addVirtualObjectMapping(graph.add(state)); - } - - @Override - public boolean isVisible() { - return false; - } - }); - } - - public void deleteFixedNode(final FixedWithNextNode node) { - add(new Effect() { - - @Override - public String name() { - return "deleteFixedNode"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert node.isAlive(); - FixedNode next = node.next(); - node.setNext(null); - node.replaceAtPredecessor(next); - obsoleteNodes.add(node); - } - }); - } - - public void eliminateMonitor(final AccessMonitorNode node) { - add(new Effect() { - - @Override - public String name() { - return "eliminateMonitor"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert node.isAlive() && node.object().isAlive() && (node.object() instanceof VirtualObjectNode); - node.eliminate(); - } - }); - } - - public void replaceAtUsages(final ValueNode node, final ValueNode replacement) { - add(new Effect() { - - @Override - public String name() { - return "replaceAtUsages"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert node.isAlive() && replacement.isAlive(); - node.replaceAtUsages(replacement); - } - }); - } - - public void replaceFirstInput(final Node node, final ValueNode oldInput, final ValueNode newInput) { - add(new Effect() { - - @Override - public String name() { - return "replaceFirstInput"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert node.isAlive() && oldInput.isAlive() && newInput.isAlive(); - node.replaceFirstInput(oldInput, newInput); - } - - @Override - public boolean isVisible() { - return !(node instanceof FrameState); - } - }); - } - - public void setPhiInput(final PhiNode node, final ValueNode value, final int index) { - add(new Effect() { - - @Override - public String name() { - return "setPhiInput"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert node.isAlive() && value.isAlive() && index >= 0; - node.setValueAt(index, value); - } - }); - } -}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/compiler/phases/ea/experimental/ReentrantBlockIterator.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,165 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.phases.ea.experimental; - -import java.util.*; - -import com.oracle.graal.compiler.phases.ea.*; -import com.oracle.graal.compiler.phases.ea.experimental.BlockIteratorClosure.LoopInfo; -import com.oracle.graal.lir.cfg.*; -import com.oracle.graal.nodes.*; - -public final class ReentrantBlockIterator { - - private ReentrantBlockIterator() { - // no instances allowed - } - - public static <T extends MergeableBlockState<T>> LoopInfo<T> processLoop(BlockIteratorClosure<T> closure, Loop loop, T initialState) { - IdentityHashMap<FixedNode, T> blockEndStates = apply(closure, loop.header, initialState, new HashSet<>(loop.blocks)); - - LoopInfo<T> info = new LoopInfo<>(); - List<Block> predecessors = loop.header.getPredecessors(); - for (int i = 1; i < predecessors.size(); i++) { - info.endStates.add(blockEndStates.get(predecessors.get(i).getEndNode())); - } - for (Block loopExit : loop.exits) { - assert loopExit.getPredecessors().size() == 1; - T exitState = blockEndStates.get(loopExit.getPredecessors().get(0).getEndNode()); - assert exitState != null; - info.exitStates.add(exitState); - } - return info; - } - - public static <T extends MergeableBlockState<T>> IdentityHashMap<FixedNode, T> apply(BlockIteratorClosure<T> closure, Block start, T initialState, Set<Block> boundary) { - Deque<Block> blockQueue = new ArrayDeque<>(); - IdentityHashMap<FixedNode, T> blockEndStates = new IdentityHashMap<>(); - - T state = initialState; - Block current = start; - - do { - if (boundary == null || boundary.contains(current)) { - closure.processBlock(current, state); - - if (current.getSuccessors().isEmpty()) { - // nothing to do... - } else if (current.getSuccessors().size() == 1) { - Block successor = current.getSuccessors().get(0); - if (successor.isLoopHeader()) { - if (current.isLoopEnd()) { - // nothing to do... loop ends only lead to loop begins we've already visited - blockEndStates.put(current.getEndNode(), state); - } else { - // recurse into the loop - Loop loop = successor.getLoop(); - LoopBeginNode loopBegin = loop.loopBegin(); - assert successor.getBeginNode() == loopBegin; - - List<T> exitStates = closure.processLoop(loop, state); - - int i = 0; - assert loop.exits.size() == exitStates.size(); - for (Block exit : loop.exits) { - blockEndStates.put(exit.getPredecessors().get(0).getEndNode(), exitStates.get(i++)); - blockQueue.addFirst(exit); - } - } - } else { - if (successor.getBeginNode() instanceof LoopExitNode) { - assert successor.getPredecessors().size() == 1; - blockEndStates.put(current.getEndNode(), state); - current = successor; - continue; - } else { - if (current.getEndNode() instanceof EndNode) { - assert successor.getPredecessors().size() > 1 : "invalid block schedule at " + successor.getBeginNode(); - EndNode end = (EndNode) current.getEndNode(); - - // add the end node and see if the merge is ready for processing - assert !blockEndStates.containsKey(end); - blockEndStates.put(end, state); - MergeNode merge = end.merge(); - boolean endsVisited = true; - for (int i = 0; i < merge.forwardEndCount(); i++) { - if (!blockEndStates.containsKey(merge.forwardEndAt(i))) { - endsVisited = false; - break; - } - } - if (endsVisited) { - blockQueue.addFirst(successor); - } - } else { - assert successor.getPredecessors().size() == 1 : "invalid block schedule at " + successor.getBeginNode(); - current = successor; - continue; - } - } - } - } else { - assert current.getSuccessors().size() > 1; - blockEndStates.put(current.getEndNode(), state); - for (Block block : current.getSuccessors()) { - blockQueue.addFirst(block); - } - } - } - - // get next queued block - if (blockQueue.isEmpty()) { - current = null; - } else { - int maxIterations = blockQueue.size(); - while (maxIterations-- > 0) { - current = blockQueue.removeFirst(); - if (current.getPredecessors().size() > 1) { - MergeNode merge = (MergeNode) current.getBeginNode(); - ArrayList<T> states = new ArrayList<>(merge.forwardEndCount()); - for (int i = 0; i < merge.forwardEndCount(); i++) { - T other = blockEndStates.get(merge.forwardEndAt(i)); - assert other != null; - states.add(other); - } - state = closure.merge(merge, states); - if (state != null) { - break; - } else { - blockQueue.addLast(current); - current = null; - } - } else { - assert current.getPredecessors().size() == 1; - assert current.getBeginNode().predecessor() != null; - if (boundary == null || boundary.contains(current)) { - state = closure.afterSplit(current.getBeginNode(), blockEndStates.get(current.getBeginNode().predecessor())); - break; - } - } - } - } - } while (current != null); - return blockEndStates; - } -}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/compiler/phases/ea/experimental/SplitPartialEscapeAnalysisPhase.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1252 +0,0 @@ -/* - * Copyright (c) 2011, 2012, 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.phases.ea.experimental; - -import java.util.*; - -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.meta.JavaType.Representation; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.compiler.*; -import com.oracle.graal.compiler.phases.*; -import com.oracle.graal.compiler.phases.ea.*; -import com.oracle.graal.compiler.phases.ea.experimental.EffectList.Effect; -import com.oracle.graal.compiler.schedule.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.PhiNode.PhiType; -import com.oracle.graal.nodes.VirtualState.NodeClosure; -import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.extended.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.nodes.virtual.*; - -class EscapeAnalysisIteration { - - 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)); - } - - private final StructuredGraph graph; - private final MetaAccessProvider runtime; - private final SchedulePhase schedule; - private final NodeBitMap usages; - - private final HashSet<VirtualObjectNode> reusedVirtualObjects = new HashSet<>(); - private int virtualIds = 0; - - public EscapeAnalysisIteration(StructuredGraph graph, SchedulePhase schedule, MetaAccessProvider runtime) { - this.graph = graph; - this.schedule = schedule; - this.runtime = runtime; - this.usages = graph.createNodeBitMap(); - } - - public void run() { - PartialEscapeClosure closure = new PartialEscapeClosure(); - ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock(), new BlockState(), null); - ArrayList<Node> obsoleteNodes = new ArrayList<>(); - for (int i = 0; i < closure.effects.size(); i++) { - Effect effect = closure.effects.get(i); - effect.apply(graph, obsoleteNodes); - if (GraalOptions.TraceEscapeAnalysis) { - if (effect.isVisible()) { - int level = closure.effects.levelAt(i); - StringBuilder str = new StringBuilder(); - for (int i2 = 0; i2 < level; i2++) { - str.append(" "); - } - trace(str.append(effect).toString()); - } - } - } - Debug.dump(graph, "after PartialEscapeAnalysis"); - - // 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 EndNode) { - // EndNode end = (EndNode) 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); - // } - // } - // - // 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); - // } - // } - // } - // - // for (Node node : obsoleteNodes) { - // if (flood.isMarked(node)) { - // System.out.println("offending node path:"); - // Node current = node; - // while (current != null) { - // System.out.println(current); - // current = path.get(current); - // if (current != null && current instanceof FixedNode && !obsoleteNodes.contains(current)) { - // break; - // } - // } - // } - // } - - new DeadCodeEliminationPhase().apply(graph); - - } - - private static class ObjectState { - - public final VirtualObjectNode virtual; - public ValueNode[] fieldState; - public ValueNode materializedValue; - public int lockCount; - - public ObjectState(VirtualObjectNode virtual, ValueNode[] fieldState, int lockCount) { - this.virtual = virtual; - this.fieldState = fieldState; - this.lockCount = lockCount; - } - - public ObjectState(VirtualObjectNode virtual, ValueNode materializedValue, int lockCount) { - this.virtual = virtual; - this.materializedValue = materializedValue; - this.lockCount = lockCount; - } - - private ObjectState(ObjectState other) { - virtual = other.virtual; - fieldState = other.fieldState == null ? null : other.fieldState.clone(); - materializedValue = other.materializedValue; - lockCount = other.lockCount; - } - - @Override - public ObjectState clone() { - return new ObjectState(this); - } - - @Override - public String toString() { - StringBuilder str = new StringBuilder().append('{'); - if (lockCount > 0) { - str.append('l').append(lockCount).append(' '); - } - if (fieldState != null) { - for (int i = 0; i < fieldState.length; i++) { - str.append(virtual.fieldName(i)).append('=').append(fieldState[i]).append(' '); - } - } - if (materializedValue != null) { - str.append("mat=").append(materializedValue); - } - - return str.append('}').toString(); - } - } - - private class BlockState implements MergeableBlockState<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<>(); - - public BlockState() { - } - - public BlockState(BlockState other) { - for (Map.Entry<VirtualObjectNode, ObjectState> entry : other.objectStates.entrySet()) { - objectStates.put(entry.getKey(), entry.getValue().clone()); - } - 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()); - } - } - - public ObjectState objectState(VirtualObjectNode object) { - assert objectStates.containsKey(object); - return objectStates.get(object); - } - - public ObjectState objectStateOptional(VirtualObjectNode object) { - return objectStates.get(object); - } - - public ObjectState objectState(ValueNode value) { - VirtualObjectNode object = objectAliases.get(value); - return object == null ? null : objectState(object); - } - - @Override - public BlockState clone() { - return new BlockState(this); - } - - public void materializeBefore(FixedNode fixed, VirtualObjectNode virtual, GraphEffectList materializeEffects) { - HashSet<VirtualObjectNode> deferred = new HashSet<>(); - GraphEffectList deferredStores = new GraphEffectList(); - materializeChangedBefore(fixed, virtual, deferred, deferredStores, materializeEffects); - materializeEffects.addAll(deferredStores); - } - - private void materializeChangedBefore(FixedNode fixed, VirtualObjectNode virtual, HashSet<VirtualObjectNode> deferred, GraphEffectList deferredStores, GraphEffectList materializeEffects) { - trace("materializing %s at %s", virtual, fixed); - ObjectState obj = objectState(virtual); - if (obj.lockCount > 0 && obj.virtual.type().isArrayClass()) { -// error("array materialized with lock: %s\n", virtual); - throw new BailoutException("array materialized with lock"); - } - - MaterializeObjectNode materialize = new MaterializeObjectNode(virtual, obj.lockCount > 0); - ValueNode[] values = new ValueNode[obj.fieldState.length]; - materialize.setProbability(fixed.probability()); - ValueNode[] fieldState = obj.fieldState; - obj.fieldState = null; - obj.materializedValue = materialize; - deferred.add(virtual); - for (int i = 0; i < fieldState.length; i++) { - ObjectState valueObj = objectState(fieldState[i]); - if (valueObj != null) { - if (valueObj.materializedValue == null) { - materializeChangedBefore(fixed, valueObj.virtual, deferred, deferredStores, materializeEffects); - } - if (deferred.contains(valueObj.virtual)) { - Kind fieldKind; - CyclicMaterializeStoreNode store; - if (virtual instanceof VirtualArrayNode) { - store = new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, i); - fieldKind = ((VirtualArrayNode) virtual).componentType().kind(); - } else { - VirtualInstanceNode instanceObject = (VirtualInstanceNode) virtual; - store = new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, instanceObject.field(i)); - fieldKind = instanceObject.field(i).type().kind(); - } - deferredStores.addFixedNodeBefore(store, fixed); - values[i] = ConstantNode.defaultForKind(fieldKind, graph); - } else { - values[i] = valueObj.materializedValue; - } - } else { - values[i] = fieldState[i]; - } - } - deferred.remove(virtual); - - materializeEffects.addMaterialization(materialize, fixed, values); - } - - private void addAndMarkAlias(VirtualObjectNode virtual, ValueNode node) { - objectAliases.put(node, virtual); - for (Node usage : node.usages()) { - markVirtualUsages(usage); - } - } - - private void markVirtualUsages(Node node) { - if (!usages.isNew(node)) { - usages.mark(node); - } - if (node instanceof VirtualState) { - for (Node usage : node.usages()) { - markVirtualUsages(usage); - } - } - } - - public void addObject(VirtualObjectNode virtual, ObjectState state) { - objectStates.put(virtual, state); - } - - public void addScalarAlias(ValueNode alias, ValueNode value) { - scalarAliases.put(alias, value); - } - - public ValueNode scalarAlias(ValueNode alias) { - ValueNode result = scalarAliases.get(alias); - return result == null ? alias : result; - } - - public Iterable<ObjectState> states() { - return objectStates.values(); - } - - @Override - public String toString() { - return objectStates.toString(); - } - } - - private class PartialEscapeClosure extends BlockIteratorClosure<BlockState> { - - private final GraphEffectList effects = new GraphEffectList(); - - @Override - protected void processBlock(Block block, BlockState state) { - trace("\nBlock: %s (", block); - List<ScheduledNode> nodeList = schedule.getBlockToNodesMap().get(block); - - FixedWithNextNode lastFixedNode = null; - for (Node node : nodeList) { - EscapeOp op = null; - if (node instanceof EscapeAnalyzable) { - op = ((EscapeAnalyzable) node).getEscapeOp(); - } - // if (node instanceof NewInstanceNode) { - // if (!((NewInstanceNode) node).instanceClass().name().contains("Key")) { - // op = null; - // } - // } else { - // op = null; - // } - - if (op != null) { - trace("{{%s}} ", node); - VirtualObjectNode virtualObject = op.virtualObject(virtualIds); - if (virtualObject.isAlive()) { - reusedVirtualObjects.add(virtualObject); - state.addAndMarkAlias(virtualObject, virtualObject); - } else { - effects.addFloatingNode(virtualObject); - } - state.addObject(virtualObject, new ObjectState(virtualObject, op.fieldState(), 0)); - state.addAndMarkAlias(virtualObject, (ValueNode) node); - effects.deleteFixedNode((FixedWithNextNode) node); - virtualIds++; - } else { - if (usages.isMarked(node)) { - trace("[[%s]] ", node); - processNode((ValueNode) node, lastFixedNode == null ? null : lastFixedNode.next(), state); - } else { - trace("%s ", node); - } - } - - if (node instanceof FixedWithNextNode && node.isAlive()) { - lastFixedNode = (FixedWithNextNode) node; - } - } - trace(")\n end state: %s\n", state); - } - - private void processNode(final ValueNode node, FixedNode insertBefore, final BlockState state) { - boolean usageFound = false; - if (node instanceof PiNode || node instanceof ValueProxyNode) { - ValueNode value = node instanceof PiNode ? ((PiNode) node).object() : ((ValueProxyNode) node).value(); - ObjectState obj = state.objectState(value); - if (obj != null) { - if (obj.materializedValue == null) { - state.addAndMarkAlias(obj.virtual, node); - } else { - effects.replaceFirstInput(node, value, obj.materializedValue); - } - usageFound = true; - } - } else if (node instanceof CheckCastNode) { - CheckCastNode x = (CheckCastNode) node; - ObjectState obj = state.objectState(x.object()); - if (obj != null) { - if (obj.materializedValue == null) { - if (x.targetClass() != null && obj.virtual.type().isSubtypeOf(x.targetClass())) { - state.addAndMarkAlias(obj.virtual, x); - effects.deleteFixedNode(x); - } else { - replaceWithMaterialized(x.object(), x, state, obj); - } - } else { - effects.replaceFirstInput(x, x.object(), obj.materializedValue); - } - usageFound = true; - } - } else if (node instanceof IsNullNode) { - IsNullNode x = (IsNullNode) node; - if (state.objectState(x.object()) != null) { - replaceAtUsages(state, x, graph.unique(ConstantNode.forBoolean(false, graph))); - usageFound = true; - } - } else if (node instanceof AccessMonitorNode) { - AccessMonitorNode x = (AccessMonitorNode) node; - ObjectState obj = state.objectState(x.object()); - if (obj != null) { - Debug.log("monitor operation %s on %s\n", x, obj.virtual); - if (node instanceof MonitorEnterNode) { - obj.lockCount++; - } else { - assert node instanceof MonitorExitNode; - obj.lockCount--; - } - if (obj.materializedValue == null) { - effects.replaceFirstInput(node, x.object(), obj.virtual); - effects.eliminateMonitor(x); - } else { - effects.replaceFirstInput(node, x.object(), obj.materializedValue); - } - usageFound = true; - } - } else if (node instanceof CyclicMaterializeStoreNode) { - CyclicMaterializeStoreNode x = (CyclicMaterializeStoreNode) node; - ObjectState obj = state.objectState(x.object()); - if (obj != null) { - if (obj.virtual instanceof VirtualArrayNode) { - obj.fieldState[x.targetIndex()] = x.value(); - } else { - VirtualInstanceNode instance = (VirtualInstanceNode) obj.virtual; - int index = instance.fieldIndex(x.targetField()); - obj.fieldState[index] = x.value(); - } - effects.deleteFixedNode(x); - usageFound = true; - } - } else if (node instanceof LoadFieldNode) { - LoadFieldNode x = (LoadFieldNode) node; - ObjectState obj = state.objectState(x.object()); - if (obj != null) { - VirtualInstanceNode virtual = (VirtualInstanceNode) obj.virtual; - int fieldIndex = virtual.fieldIndex(x.field()); - if (fieldIndex == -1) { - // the field does not exist in the virtual object - ensureMaterialized(state, obj, x); - } - if (obj.materializedValue == null) { - ValueNode result = obj.fieldState[fieldIndex]; - ObjectState resultObj = state.objectState(result); - if (resultObj != null) { - state.addAndMarkAlias(resultObj.virtual, x); - } else { - replaceAtUsages(state, x, result); - } - effects.deleteFixedNode(x); - } else { - effects.replaceFirstInput(x, x.object(), obj.materializedValue); - } - usageFound = true; - } - } else if (node instanceof StoreFieldNode) { - StoreFieldNode x = (StoreFieldNode) node; - ValueNode object = x.object(); - ValueNode value = x.value(); - ObjectState obj = state.objectState(object); - if (obj != null) { - VirtualInstanceNode virtual = (VirtualInstanceNode) obj.virtual; - int fieldIndex = virtual.fieldIndex(x.field()); - if (fieldIndex == -1) { - // the field does not exist in the virtual object - ensureMaterialized(state, obj, x); - } - if (obj.materializedValue == null) { - obj.fieldState[fieldIndex] = state.scalarAlias(value); - effects.deleteFixedNode(x); - } else { - effects.replaceFirstInput(x, object, obj.materializedValue); - ObjectState valueObj = state.objectState(value); - if (valueObj != null) { - replaceWithMaterialized(value, x, state, valueObj); - } - } - usageFound = true; - } else { - ObjectState valueObj = state.objectState(value); - if (valueObj != null) { - replaceWithMaterialized(value, x, state, valueObj); - usageFound = true; - } - } - } else if (node instanceof LoadIndexedNode) { - LoadIndexedNode x = (LoadIndexedNode) node; - ValueNode array = x.array(); - ObjectState arrayObj = state.objectState(array); - if (arrayObj != null) { - if (arrayObj.materializedValue == null) { - ValueNode indexValue = state.scalarAlias(x.index()); - int index = indexValue.isConstant() ? indexValue.asConstant().asInt() : -1; - if (index < 0 || index >= arrayObj.fieldState.length) { - // out of bounds or not constant - replaceWithMaterialized(array, x, state, arrayObj); - } else { - ValueNode result = arrayObj.fieldState[index]; - ObjectState resultObj = state.objectState(result); - if (resultObj != null) { - state.addAndMarkAlias(resultObj.virtual, x); - } else { - replaceAtUsages(state, x, result); - } - effects.deleteFixedNode(x); - } - } else { - effects.replaceFirstInput(x, array, arrayObj.materializedValue); - } - usageFound = true; - } - } else if (node instanceof StoreIndexedNode) { - StoreIndexedNode x = (StoreIndexedNode) node; - ValueNode array = x.array(); - ValueNode value = x.value(); - ObjectState arrayObj = state.objectState(array); - ObjectState valueObj = state.objectState(value); - - if (arrayObj != null) { - if (arrayObj.materializedValue == null) { - ValueNode indexValue = state.scalarAlias(x.index()); - int index = indexValue.isConstant() ? indexValue.asConstant().asInt() : -1; - if (index < 0 || index >= arrayObj.fieldState.length) { - // out of bounds or not constant - replaceWithMaterialized(array, x, state, arrayObj); - if (valueObj != null) { - replaceWithMaterialized(value, x, state, valueObj); - } - } else { - arrayObj.fieldState[index] = state.scalarAlias(value); - effects.deleteFixedNode(x); - } - } else { - effects.replaceFirstInput(x, array, arrayObj.materializedValue); - if (valueObj != null) { - replaceWithMaterialized(value, x, state, valueObj); - } - } - usageFound = true; - } else { - if (valueObj != null) { - replaceWithMaterialized(value, x, state, valueObj); - usageFound = true; - } - } - } else if (node instanceof RegisterFinalizerNode) { - RegisterFinalizerNode x = (RegisterFinalizerNode) node; - ObjectState obj = state.objectState(x.object()); - if (obj != null) { - replaceWithMaterialized(x.object(), x, state, obj); - usageFound = true; - } - } else if (node instanceof ArrayLengthNode) { - ArrayLengthNode x = (ArrayLengthNode) node; - ObjectState obj = state.objectState(x.array()); - if (obj != null) { - replaceAtUsages(state, x, ConstantNode.forInt(((VirtualArrayNode) obj.virtual).entryCount(), graph)); - effects.deleteFixedNode(x); - usageFound = true; - } - } else if (node instanceof LoadHubNode) { - LoadHubNode x = (LoadHubNode) node; - ObjectState obj = state.objectState(x.object()); - if (obj != null) { - replaceAtUsages(state, x, ConstantNode.forConstant(obj.virtual.type().getEncoding(Representation.ObjectHub), runtime, graph)); - effects.deleteFixedNode(x); - usageFound = true; - } - } else if (node instanceof ReturnNode) { - ReturnNode x = (ReturnNode) node; - ObjectState obj = state.objectState(x.result()); - if (obj != null) { - replaceWithMaterialized(x.result(), x, state, obj); - usageFound = true; - } - } else if (node instanceof MethodCallTargetNode) { - for (ValueNode argument : ((MethodCallTargetNode) node).arguments()) { - ObjectState obj = state.objectState(argument); - if (obj != null) { - replaceWithMaterialized(argument, node, insertBefore, state, obj); - usageFound = true; - } - } - } else if (node instanceof ObjectEqualsNode) { - ObjectEqualsNode x = (ObjectEqualsNode) node; - ObjectState xObj = state.objectState(x.x()); - ObjectState yObj = state.objectState(x.y()); - boolean xVirtual = xObj != null && xObj.materializedValue == null; - boolean yVirtual = yObj != null && yObj.materializedValue == null; - - if (xVirtual ^ yVirtual) { - // one of them is virtual: they can never be the same objects - replaceAtUsages(state, x, ConstantNode.forBoolean(false, graph)); - usageFound = true; - } else if (xVirtual && yVirtual) { - // both are virtual: check if they refer to the same object - replaceAtUsages(state, x, ConstantNode.forBoolean(xObj == yObj, graph)); - usageFound = true; - } else { - if (xObj != null || yObj != null) { - if (xObj != null) { - assert xObj.materializedValue != null; - effects.replaceFirstInput(x, x.x(), xObj.materializedValue); - } - if (yObj != null) { - assert yObj.materializedValue != null; - effects.replaceFirstInput(x, x.y(), yObj.materializedValue); - } - usageFound = true; - } - } - } else if (node instanceof MergeNode) { - usageFound = true; - } else if (node instanceof UnsafeLoadNode || node instanceof UnsafeStoreNode || node instanceof CompareAndSwapNode || node instanceof SafeReadNode) { - for (ValueNode input : node.inputs().filter(ValueNode.class)) { - ObjectState obj = state.objectState(input); - if (obj != null) { - replaceWithMaterialized(input, node, insertBefore, state, obj); - usageFound = true; - } - } - } - if (node.isAlive() && node instanceof StateSplit) { - StateSplit split = (StateSplit) node; - FrameState stateAfter = split.stateAfter(); - if (stateAfter != null) { - if (stateAfter.usages().size() > 1) { - stateAfter = (FrameState) stateAfter.copyWithInputs(); - split.setStateAfter(stateAfter); - } - final HashSet<ObjectState> virtual = new HashSet<>(); - stateAfter.applyToNonVirtual(new NodeClosure<ValueNode>() { - - @Override - public void apply(Node usage, ValueNode value) { - ObjectState valueObj = state.objectState(value); - if (valueObj != null) { - virtual.add(valueObj); - effects.replaceFirstInput(usage, value, valueObj.virtual); - } else if (value instanceof VirtualObjectNode) { - ObjectState virtualObj = null; - for (ObjectState obj : state.states()) { - if (value == obj.virtual) { - virtualObj = obj; - break; - } - } - if (virtualObj != null) { - virtual.add(virtualObj); - } - } - } - }); - for (ObjectState obj : state.states()) { - if (obj.materializedValue == null && obj.lockCount > 0) { - virtual.add(obj); - } - } - - ArrayDeque<ObjectState> queue = new ArrayDeque<>(virtual); - while (!queue.isEmpty()) { - ObjectState obj = queue.removeLast(); - if (obj.materializedValue == null) { - for (ValueNode field : obj.fieldState) { - ObjectState fieldObj = state.objectState(field); - if (fieldObj != null) { - if (fieldObj.materializedValue == null && !virtual.contains(fieldObj)) { - virtual.add(fieldObj); - queue.addLast(fieldObj); - } - } - } - } - } - for (ObjectState obj : virtual) { - EscapeObjectState v; - if (obj.materializedValue == null) { - ValueNode[] fieldState = obj.fieldState.clone(); - for (int i = 0; i < fieldState.length; i++) { - ObjectState valueObj = state.objectState(fieldState[i]); - if (valueObj != null) { - if (valueObj.materializedValue == null) { - fieldState[i] = valueObj.virtual; - } else { - fieldState[i] = valueObj.materializedValue; - } - } - } - v = new VirtualObjectState(obj.virtual, fieldState); - } else { - v = new MaterializedObjectState(obj.virtual, obj.materializedValue); - } - effects.addVirtualMapping(stateAfter, v, reusedVirtualObjects); - } - } - usageFound = true; - } - if (!usageFound) { - for (ValueNode input : node.inputs().filter(ValueNode.class)) { - ObjectState obj = state.objectState(input); - if (obj != null) { - replaceWithMaterialized(input, node, insertBefore, state, obj); - usageFound = true; - } - } - Debug.log("unexpected usage of %s: %s\n", node, node.inputs().snapshot()); - } - } - - private void replaceAtUsages(final BlockState state, ValueNode x, ValueNode value) { - effects.replaceAtUsages(x, value); - state.addScalarAlias(x, value); - } - - private void ensureMaterialized(BlockState state, ObjectState obj, FixedNode materializeBefore) { - assert obj != null; - if (obj.materializedValue == null) { - state.materializeBefore(materializeBefore, obj.virtual, effects); - } - assert obj.materializedValue != null; - } - - private void replaceWithMaterialized(ValueNode value, FixedNode usage, BlockState state, ObjectState obj) { - ensureMaterialized(state, obj, usage); - effects.replaceFirstInput(usage, value, obj.materializedValue); - } - - private void replaceWithMaterialized(ValueNode value, Node usage, FixedNode materializeBefore, BlockState state, ObjectState obj) { - ensureMaterialized(state, obj, materializeBefore); - effects.replaceFirstInput(usage, value, obj.materializedValue); - } - - @Override - protected BlockState merge(MergeNode merge, List<BlockState> states) { - BlockState newState = new BlockState(); - - newState.objectAliases.putAll(states.get(0).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()) { - if (state.objectAliases.containsKey(entry.getKey())) { - assert state.objectAliases.get(entry.getKey()) == entry.getValue(); - } else { - newState.objectAliases.remove(entry.getKey()); - } - } - } - - newState.scalarAliases.putAll(states.get(0).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()) { - if (state.scalarAliases.containsKey(entry.getKey())) { - assert state.scalarAliases.get(entry.getKey()) == entry.getValue(); - } else { - newState.scalarAliases.remove(entry.getKey()); - } - } - } - - // Iterative processing: - // Merging the materialized/virtual state of virtual objects can lead to new materializations, which can - // lead to new materializations because of phis, and so on. - - boolean materialized; - do { - materialized = false; - // use a hash set to make the values distinct... - for (VirtualObjectNode object : new HashSet<>(newState.objectAliases.values())) { - ObjectState resultState = newState.objectStates.get(object); - if (resultState == null || resultState.materializedValue == null) { - int virtual = 0; - int lockCount = states.get(0).objectState(object).lockCount; - ValueNode singleValue = states.get(0).objectState(object).materializedValue; - for (BlockState state : states) { - ObjectState obj = state.objectState(object); - if (obj.materializedValue == null) { - virtual++; - singleValue = null; - } else { - if (obj.materializedValue != singleValue) { - singleValue = null; - } - } - assert obj.lockCount == lockCount : "mismatching lock counts"; - } - - if (virtual < states.size()) { - if (singleValue == null) { - PhiNode materializedValuePhi = new PhiNode(Kind.Object, merge); - effects.addFloatingNode(materializedValuePhi); - for (int i = 0; i < states.size(); i++) { - BlockState state = states.get(i); - ObjectState obj = state.objectState(object); - materialized |= obj.materializedValue == null; - ensureMaterialized(state, obj, merge.forwardEndAt(i)); - effects.addPhiInput(materializedValuePhi, obj.materializedValue); - } - newState.addObject(object, new ObjectState(object, materializedValuePhi, lockCount)); - } else { - newState.addObject(object, new ObjectState(object, singleValue, lockCount)); - } - } else { - assert virtual == states.size(); - ValueNode[] values = states.get(0).objectState(object).fieldState.clone(); - PhiNode[] phis = new PhiNode[values.length]; - int mismatch = 0; - for (int i = 1; i < states.size(); i++) { - BlockState state = states.get(i); - ValueNode[] fields = state.objectState(object).fieldState; - for (int index = 0; index < values.length; index++) { - if (phis[index] == null && values[index] != fields[index]) { - mismatch++; - phis[index] = new PhiNode(values[index].kind(), merge); - effects.addFloatingNode(phis[index]); - } - } - } - if (mismatch > 0) { - for (int i = 0; i < states.size(); i++) { - BlockState state = states.get(i); - ValueNode[] fields = state.objectState(object).fieldState; - for (int index = 0; index < values.length; index++) { - if (phis[index] != null) { - ObjectState obj = state.objectState(fields[index]); - if (obj != null) { - materialized |= obj.materializedValue == null; - ensureMaterialized(state, obj, merge.forwardEndAt(i)); - fields[index] = obj.materializedValue; - } - effects.addPhiInput(phis[index], fields[index]); - } - } - } - for (int index = 0; index < values.length; index++) { - if (phis[index] != null) { - values[index] = phis[index]; - } - } - } - newState.addObject(object, new ObjectState(object, values, lockCount)); - } - } - } - - for (PhiNode phi : merge.phis().snapshot()) { - if (usages.isMarked(phi) && phi.type() == PhiType.Value) { - materialized |= processPhi(newState, merge, phi, states); - } - } - } while (materialized); - - return newState; - } - - private boolean processPhi(BlockState newState, MergeNode merge, PhiNode phi, List<BlockState> states) { - assert states.size() == phi.valueCount(); - int virtualInputs = 0; - boolean materialized = false; - VirtualObjectNode sameObject = null; - ResolvedJavaType sameType = null; - int sameEntryCount = -1; - for (int i = 0; i < phi.valueCount(); i++) { - ValueNode value = phi.valueAt(i); - ObjectState obj = states.get(i).objectState(value); - if (obj != null) { - if (obj.materializedValue == null) { - virtualInputs++; - if (i == 0) { - sameObject = obj.virtual; - sameType = obj.virtual.type(); - sameEntryCount = obj.virtual.entryCount(); - } else { - if (sameObject != obj.virtual) { - sameObject = null; - } - if (sameType != obj.virtual.type()) { - sameType = null; - } - if (sameEntryCount != obj.virtual.entryCount()) { - sameEntryCount = -1; - } - } - } else { - effects.setPhiInput(phi, obj.materializedValue, i); - } - } - } - boolean materialize = false; - if (virtualInputs == 0) { - // nothing to do... - } else if (virtualInputs == phi.valueCount()) { - if (sameObject != null) { - newState.addAndMarkAlias(sameObject, phi); - } else if (sameType != null && sameEntryCount != -1) { - materialize = true; - // throw new GraalInternalError("merge required for %s", sameType); - } else { - materialize = true; - } - } else { - materialize = true; - } - - if (materialize) { - for (int i = 0; i < phi.valueCount(); i++) { - ValueNode value = phi.valueAt(i); - ObjectState obj = states.get(i).objectState(value); - if (obj != null) { - materialized |= obj.materializedValue == null; - replaceWithMaterialized(value, phi, merge.forwardEndAt(i), states.get(i), obj); - } - } - } - return materialized; - } - - @Override - protected BlockState afterSplit(FixedNode node, BlockState oldState) { - return oldState.clone(); - } - - @Override - protected List<BlockState> processLoop(Loop loop, BlockState initialState) { - GraphEffectList successEffects = new GraphEffectList(); - HashSet<PhiDesc> phis = new HashSet<>(); - for (int iteration = 0; iteration < 10; iteration++) { - BlockState state = initialState.clone(); - int checkpoint = effects.checkpoint(); - - for (PhiDesc desc : phis) { - ObjectState obj = state.objectState(desc.virtualObject); - if (obj.materializedValue == null) { - ValueNode value = obj.fieldState[desc.fieldIndex]; - ObjectState valueObj = state.objectState(value); - if (valueObj != null) { - assert valueObj.materializedValue != null; - value = valueObj.materializedValue; - } - - PhiNode phiNode = new PhiNode(value.kind(), loop.loopBegin()); - effects.addFloatingNode(phiNode); - effects.addPhiInput(phiNode, value); - obj.fieldState[desc.fieldIndex] = phiNode; - } - } - - for (PhiNode phi : loop.loopBegin().phis()) { - if (usages.isMarked(phi) && phi.type() == PhiType.Value) { - ObjectState initialObj = initialState.objectState(phi.valueAt(0)); - if (initialObj != null) { - if (initialObj.materializedValue == null) { - state.addAndMarkAlias(initialObj.virtual, phi); - } else { - successEffects.setPhiInput(phi, initialObj.materializedValue, 0); - } - } - } - } - - effects.incLevel(); - LoopInfo<BlockState> info = ReentrantBlockIterator.processLoop(this, loop, state.clone()); - - List<BlockState> loopEndStates = info.endStates; - List<Block> predecessors = loop.header.getPredecessors(); - HashSet<VirtualObjectNode> additionalMaterializations = 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); - } - if (additionalMaterializations.isEmpty() && oldPhiCount == phis.size()) { - effects.addAll(successEffects); - - assert info.exitStates.size() == loop.exits.size(); - for (int i = 0; i < loop.exits.size(); i++) { - BlockState exitState = info.exitStates.get(i); - assert exitState != null : "no loop exit state at " + loop.exits.get(i) + " / " + loop.header; - processLoopExit((LoopExitNode) loop.exits.get(i).getBeginNode(), state, exitState); - } - - effects.decLevel(); - return info.exitStates; - } else { - successEffects.clear(); - effects.backtrack(checkpoint); - effects.decLevel(); - for (VirtualObjectNode virtualObject : additionalMaterializations) { - ObjectState obj = initialState.objectState(virtualObject); - if (obj.materializedValue == null) { - initialState.materializeBefore(loop.loopBegin().forwardEnd(), virtualObject, effects); - } - } - } - } - - throw new GraalInternalError("too many iterations at %s", loop); - } - - private void processLoopExit(LoopExitNode exitNode, BlockState initialState, BlockState exitState) { - HashMap<VirtualObjectNode, ValueProxyNode> proxies = new HashMap<>(); - - for (ValueProxyNode proxy : exitNode.proxies()) { - ObjectState obj = exitState.objectState(proxy.value()); - if (obj != null) { - proxies.put(obj.virtual, proxy); - } - } - for (ObjectState obj : exitState.states()) { - ObjectState initialObj = initialState.objectStateOptional(obj.virtual); - if (obj.materializedValue == null) { - for (int i = 0; i < obj.fieldState.length; i++) { - ValueNode value = obj.fieldState[i]; - ObjectState valueObj = exitState.objectState(value); - if (valueObj == null) { - if ((value instanceof PhiNode && ((PhiNode) value).merge() == exitNode.loopBegin()) || initialObj == null || initialObj.materializedValue != null || - initialObj.fieldState[i] != value) { - ValueProxyNode proxy = new ValueProxyNode(value, exitNode, PhiType.Value); - obj.fieldState[i] = proxy; - effects.addFloatingNode(proxy); - } - } - } - } else { - if (initialObj == null || initialObj.materializedValue == null) { - ValueProxyNode proxy = proxies.get(obj.virtual); - if (proxy == null) { - proxy = new ValueProxyNode(obj.materializedValue, exitNode, PhiType.Value); - effects.addFloatingNode(proxy); - } else { - effects.replaceFirstInput(proxy, proxy.value(), obj.materializedValue); - // nothing to do - will be handled in processNode - } - obj.materializedValue = proxy; - } else { - assert initialObj.materializedValue == obj.materializedValue : "materialized value is not allowed to change within loops: " + initialObj.materializedValue + " vs. " + - obj.materializedValue; - } - } - } - } - - private final class PhiDesc { - - public final VirtualObjectNode virtualObject; - public final int fieldIndex; - - public PhiDesc(VirtualObjectNode virtualObject, int fieldIndex) { - this.virtualObject = virtualObject; - this.fieldIndex = fieldIndex; - } - - @Override - public int hashCode() { - final int prime = 31; - int result = fieldIndex; - result = prime * result + ((virtualObject == null) ? 0 : virtualObject.hashCode()); - return result; - } - - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } - if (obj == null || getClass() != obj.getClass()) { - return false; - } - PhiDesc other = (PhiDesc) obj; - return virtualObject == other.virtualObject && fieldIndex == other.fieldIndex; - } - } - - private void processLoopEnd(LoopBeginNode loopBegin, LoopEndNode loopEnd, BlockState initialState, BlockState loopEndState, GraphEffectList successEffects, - Set<VirtualObjectNode> additionalMaterializations, HashSet<PhiDesc> phis) { - assert loopEnd.loopBegin() == loopBegin; - boolean materialized; - do { - materialized = false; - for (ObjectState state : initialState.states()) { - ObjectState endState = loopEndState.objectState(state.virtual); - if (state.materializedValue == null) { - if (endState.materializedValue == null) { - assert state.fieldState.length == endState.fieldState.length; - for (int i = 0; endState.fieldState != null && i < state.fieldState.length; i++) { - ValueNode value = state.fieldState[i]; - ValueNode endValue = endState.fieldState[i]; - ObjectState valueObj = initialState.objectState(value); - ObjectState endValueObj = loopEndState.objectState(endValue); - - if (valueObj != null) { - if (valueObj.materializedValue == null) { - if (endValueObj == null || endValueObj.materializedValue != null || valueObj.virtual != endValueObj.virtual) { - additionalMaterializations.add(valueObj.virtual); - } else { - // endValue is also virtual and refers to the same virtual object, so we're - // good. - } - } - } else { - if (value instanceof PhiNode && ((PhiNode) value).merge() == loopBegin) { - if (endValueObj != null) { - if (endValueObj.materializedValue == null) { - loopEndState.materializeBefore(loopEnd, endValueObj.virtual, successEffects); - materialized = true; - } - } - } - } - } - } else { - additionalMaterializations.add(state.virtual); - } - } - } - for (PhiNode phi : loopBegin.phis().snapshot()) { - if (usages.isMarked(phi) && phi.type() == PhiType.Value) { - ObjectState initialObj = initialState.objectState(phi.valueAt(0)); - boolean initialMaterialized = initialObj == null || initialObj.materializedValue != null; - - ObjectState loopEndObj = loopEndState.objectState(phi.valueAt(loopEnd)); - if (loopEndObj == null || loopEndObj.materializedValue != null) { - if (loopEndObj != null) { - successEffects.setPhiInput(phi, loopEndObj.materializedValue, loopBegin.phiPredecessorIndex(loopEnd)); - } - if (!initialMaterialized) { - additionalMaterializations.add(initialObj.virtual); - } - } else { - if (initialMaterialized) { - loopEndState.materializeBefore(loopEnd, loopEndObj.virtual, successEffects); - materialized = true; - } else { - if (loopEndObj.virtual != initialObj.virtual) { - additionalMaterializations.add(initialObj.virtual); - } - } - } - } - } - } while (materialized); - - for (ObjectState state : initialState.states()) { - ObjectState endState = loopEndState.objectState(state.virtual); - if (state.materializedValue == null) { - if (endState.materializedValue == null) { - assert state.fieldState.length == endState.fieldState.length; - for (int i = 0; i < state.fieldState.length; i++) { - ValueNode value = state.fieldState[i]; - ValueNode endValue = endState.fieldState[i]; - ObjectState valueObj = initialState.objectState(value); - ObjectState endValueObj = loopEndState.objectState(endValue); - - if (valueObj != null) { - if (valueObj.materializedValue == null) { - if (endValueObj == null || endValueObj.materializedValue != null || valueObj.virtual != endValueObj.virtual) { - assert !additionalMaterializations.isEmpty(); - } else { - // endValue is also virtual and refers to the same virtual object, so we're - // good. - } - } else { - if ((endValueObj != null && endValueObj.materializedValue != valueObj.materializedValue) || (endValueObj == null && valueObj.materializedValue != endValue)) { - phis.add(new PhiDesc(state.virtual, i)); - } else { - // either endValue has the same materialized value as value or endValue is the - // same as the materialized value, so we're good. - } - } - } else { - if (value instanceof PhiNode && ((PhiNode) value).merge() == loopBegin) { - if (endValueObj != null) { - if (endValueObj.materializedValue == null) { - assert !additionalMaterializations.isEmpty(); - } - successEffects.addPhiInput((PhiNode) value, endValueObj.materializedValue); - } else { - successEffects.addPhiInput((PhiNode) value, endValue); - } - } else if (value != endValue) { - phis.add(new PhiDesc(state.virtual, i)); - } - } - } - } else { - // endState.materializedValue != null - assert !additionalMaterializations.isEmpty(); - } - } else { - // state.materializedValue != null - if (endState.materializedValue == null) { - // throw new GraalInternalError("un-materialized object state at %s", loopEnd); - } else { - if (state.materializedValue != endState.materializedValue) { - // throw new GraalInternalError("changed materialized value during loop: %s vs %s", - // state.materializedValue, endState.materializedValue); - } - } - } - } - } - } -} - -public class SplitPartialEscapeAnalysisPhase extends Phase { - - private final GraalCodeCacheProvider runtime; - - public SplitPartialEscapeAnalysisPhase(GraalCodeCacheProvider runtime) { - this.runtime = runtime; - } - - @Override - protected void run(StructuredGraph graph) { - SchedulePhase schedule = new SchedulePhase(); - schedule.apply(graph, false); - new EscapeAnalysisIteration(graph, schedule, runtime).run(); - } -}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/nodes/virtual/CyclicMaterializeStoreNode.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,85 +0,0 @@ -/* - * Copyright (c) 2009, 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.virtual; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.nodes.type.*; - -/** - * The {@code StoreFieldNode} represents a write to a static or instance field. - */ -@NodeInfo(nameTemplate = "MaterializeStore#{p#target/s}") -public final class CyclicMaterializeStoreNode extends FixedWithNextNode implements Lowerable { - - @Input private ValueNode object; - @Input private ValueNode value; - private final Object target; - - public ValueNode object() { - return object; - } - - public ValueNode value() { - return value; - } - - public ResolvedJavaField targetField() { - return (ResolvedJavaField) target; - } - - public int targetIndex() { - return (int) target; - } - - public CyclicMaterializeStoreNode(ValueNode object, ValueNode value, ResolvedJavaField field) { - super(StampFactory.forVoid()); - this.object = object; - this.value = value; - this.target = field; - } - - public CyclicMaterializeStoreNode(ValueNode object, ValueNode value, int index) { - super(StampFactory.forVoid()); - this.object = object; - this.value = value; - this.target = index; - } - - @Override - public void lower(LoweringTool tool) { - StructuredGraph graph = (StructuredGraph) graph(); - ResolvedJavaType type = object.objectStamp().type(); - FixedWithNextNode store; - if (target instanceof Integer) { - store = graph.add(new StoreIndexedNode(object, ConstantNode.forInt((int) target, graph), type.componentType().kind(), value, -1)); - } else { - assert target instanceof ResolvedJavaField; - store = graph.add(new StoreFieldNode(object, (ResolvedJavaField) target, value, -1)); - } - graph.replaceFixedWithFixed(this, store); - } -}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/nodes/virtual/MaterializeObjectNode.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,117 +0,0 @@ -/* - * Copyright (c) 2009, 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.virtual; - -import com.oracle.graal.api.meta.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.java.*; -import com.oracle.graal.nodes.spi.*; -import com.oracle.graal.nodes.type.*; - -@NodeInfo(nameTemplate = "Materialize {i#virtualObject}") -public final class MaterializeObjectNode extends FixedWithNextNode implements EscapeAnalyzable, Lowerable, Node.IterableNodeType, Canonicalizable { - - @Input private final NodeInputList<ValueNode> values; - @Input private final VirtualObjectNode virtualObject; - private final boolean locked; - - public MaterializeObjectNode(VirtualObjectNode virtualObject, boolean locked) { - super(StampFactory.exactNonNull(virtualObject.type())); - this.virtualObject = virtualObject; - this.locked = locked; - this.values = new NodeInputList<>(this, virtualObject.entryCount()); - } - - public NodeInputList<ValueNode> values() { - return values; - } - - @Override - public void lower(LoweringTool tool) { - StructuredGraph graph = (StructuredGraph) graph(); - if (virtualObject instanceof VirtualInstanceNode) { - VirtualInstanceNode virtual = (VirtualInstanceNode) virtualObject; - - NewInstanceNode newInstance = graph.add(new NewInstanceNode(virtual.type(), false, locked)); - this.replaceAtUsages(newInstance); - graph.addAfterFixed(this, newInstance); - - FixedWithNextNode position = newInstance; - for (int i = 0; i < virtual.entryCount(); i++) { - StoreFieldNode store = graph.add(new StoreFieldNode(newInstance, virtual.field(i), values.get(i), -1)); - graph.addAfterFixed(position, store); - position = store; - } - - graph.removeFixed(this); - } else { - assert virtualObject instanceof VirtualArrayNode; - VirtualArrayNode virtual = (VirtualArrayNode) virtualObject; - - ResolvedJavaType element = virtual.componentType(); - NewArrayNode newArray; - if (element.kind() == Kind.Object) { - newArray = graph.add(new NewObjectArrayNode(element, ConstantNode.forInt(virtual.entryCount(), graph), false, locked)); - } else { - newArray = graph.add(new NewPrimitiveArrayNode(element, ConstantNode.forInt(virtual.entryCount(), graph), false, locked)); - } - this.replaceAtUsages(newArray); - graph.addAfterFixed(this, newArray); - - FixedWithNextNode position = newArray; - for (int i = 0; i < virtual.entryCount(); i++) { - StoreIndexedNode store = graph.add(new StoreIndexedNode(newArray, ConstantNode.forInt(i, graph), element.kind(), values.get(i), -1)); - graph.addAfterFixed(position, store); - position = store; - } - - graph.removeFixed(this); - } - } - - @Override - public ValueNode canonical(CanonicalizerTool tool) { - if (usages().isEmpty()) { - return null; - } else { - return this; - } - } - - @Override - public EscapeOp getEscapeOp() { - return new EscapeOp() { - - @Override - public ValueNode[] fieldState() { - return values.toArray(new ValueNode[values.size()]); - } - - @Override - public VirtualObjectNode virtualObject(int virtualId) { - return virtualObject; - } - }; - } -}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/nodes/virtual/MaterializedObjectState.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,59 +0,0 @@ -/* - * Copyright (c) 2009, 2012, 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.virtual; - -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.spi.*; - -/** - * This class encapsulated the materialized state of an escape analyzed object. - */ -public final class MaterializedObjectState extends EscapeObjectState implements Node.IterableNodeType, LIRLowerable { - - @Input private ValueNode materializedValue; - - public ValueNode materializedValue() { - return materializedValue; - } - - public MaterializedObjectState(VirtualObjectNode object, ValueNode materializedValue) { - super(object); - this.materializedValue = materializedValue; - } - - @Override - public void generate(LIRGeneratorTool generator) { - // Nothing to do, virtual object states are processed as part of the handling of StateSplit nodes. - } - - @Override - public MaterializedObjectState duplicateWithVirtualState() { - return graph().add(new MaterializedObjectState(object(), materializedValue)); - } - - @Override - public void applyToNonVirtual(NodeClosure< ? super ValueNode> closure) { - closure.apply(this, materializedValue); - } -}
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/nodes/virtual/VirtualObjectState.java Sun Oct 07 14:08:36 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,70 +0,0 @@ -/* - * Copyright (c) 2009, 2012, 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.virtual; - -import java.util.*; - -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.spi.*; - -/** - * This class encapsulated the virtual state of an escape analyzed object. - */ -public final class VirtualObjectState extends EscapeObjectState implements Node.IterableNodeType, LIRLowerable { - - @Input private final NodeInputList<ValueNode> fieldValues; - - public NodeInputList<ValueNode> fieldValues() { - return fieldValues; - } - - public VirtualObjectState(VirtualObjectNode object, ValueNode[] fieldValues) { - super(object); - assert object.entryCount() == fieldValues.length; - this.fieldValues = new NodeInputList<>(this, fieldValues); - } - - private VirtualObjectState(VirtualObjectNode object, List<ValueNode> fieldValues) { - super(object); - assert object.entryCount() == fieldValues.size(); - this.fieldValues = new NodeInputList<>(this, fieldValues); - } - - @Override - public void generate(LIRGeneratorTool generator) { - // Nothing to do, virtual object states are processed as part of the handling of StateSplit nodes. - } - - @Override - public VirtualObjectState duplicateWithVirtualState() { - return graph().add(new VirtualObjectState(object(), fieldValues)); - } - - @Override - public void applyToNonVirtual(NodeClosure< ? super ValueNode> closure) { - for (ValueNode value : fieldValues) { - closure.apply(this, value); - } - } -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/nodes/CyclicMaterializeStoreNode.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,85 @@ +/* + * Copyright (c) 2009, 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.virtual.nodes; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.java.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; + +/** + * The {@code StoreFieldNode} represents a write to a static or instance field. + */ +@NodeInfo(nameTemplate = "MaterializeStore#{p#target/s}") +public final class CyclicMaterializeStoreNode extends FixedWithNextNode implements Lowerable { + + @Input private ValueNode object; + @Input private ValueNode value; + private final Object target; + + public ValueNode object() { + return object; + } + + public ValueNode value() { + return value; + } + + public ResolvedJavaField targetField() { + return (ResolvedJavaField) target; + } + + public int targetIndex() { + return (int) target; + } + + public CyclicMaterializeStoreNode(ValueNode object, ValueNode value, ResolvedJavaField field) { + super(StampFactory.forVoid()); + this.object = object; + this.value = value; + this.target = field; + } + + public CyclicMaterializeStoreNode(ValueNode object, ValueNode value, int index) { + super(StampFactory.forVoid()); + this.object = object; + this.value = value; + this.target = index; + } + + @Override + public void lower(LoweringTool tool) { + StructuredGraph graph = (StructuredGraph) graph(); + ResolvedJavaType type = object.objectStamp().type(); + FixedWithNextNode store; + if (target instanceof Integer) { + store = graph.add(new StoreIndexedNode(object, ConstantNode.forInt((int) target, graph), type.componentType().kind(), value, -1)); + } else { + assert target instanceof ResolvedJavaField; + store = graph.add(new StoreFieldNode(object, (ResolvedJavaField) target, value, -1)); + } + graph.replaceFixedWithFixed(this, store); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/nodes/MaterializeObjectNode.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,118 @@ +/* + * Copyright (c) 2009, 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.virtual.nodes; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.java.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; +import com.oracle.graal.nodes.virtual.*; + +@NodeInfo(nameTemplate = "Materialize {i#virtualObject}") +public final class MaterializeObjectNode extends FixedWithNextNode implements EscapeAnalyzable, Lowerable, Node.IterableNodeType, Canonicalizable { + + @Input private final NodeInputList<ValueNode> values; + @Input private final VirtualObjectNode virtualObject; + private final boolean locked; + + public MaterializeObjectNode(VirtualObjectNode virtualObject, boolean locked) { + super(StampFactory.exactNonNull(virtualObject.type())); + this.virtualObject = virtualObject; + this.locked = locked; + this.values = new NodeInputList<>(this, virtualObject.entryCount()); + } + + public NodeInputList<ValueNode> values() { + return values; + } + + @Override + public void lower(LoweringTool tool) { + StructuredGraph graph = (StructuredGraph) graph(); + if (virtualObject instanceof VirtualInstanceNode) { + VirtualInstanceNode virtual = (VirtualInstanceNode) virtualObject; + + NewInstanceNode newInstance = graph.add(new NewInstanceNode(virtual.type(), false, locked)); + this.replaceAtUsages(newInstance); + graph.addAfterFixed(this, newInstance); + + FixedWithNextNode position = newInstance; + for (int i = 0; i < virtual.entryCount(); i++) { + StoreFieldNode store = graph.add(new StoreFieldNode(newInstance, virtual.field(i), values.get(i), -1)); + graph.addAfterFixed(position, store); + position = store; + } + + graph.removeFixed(this); + } else { + assert virtualObject instanceof VirtualArrayNode; + VirtualArrayNode virtual = (VirtualArrayNode) virtualObject; + + ResolvedJavaType element = virtual.componentType(); + NewArrayNode newArray; + if (element.kind() == Kind.Object) { + newArray = graph.add(new NewObjectArrayNode(element, ConstantNode.forInt(virtual.entryCount(), graph), false, locked)); + } else { + newArray = graph.add(new NewPrimitiveArrayNode(element, ConstantNode.forInt(virtual.entryCount(), graph), false, locked)); + } + this.replaceAtUsages(newArray); + graph.addAfterFixed(this, newArray); + + FixedWithNextNode position = newArray; + for (int i = 0; i < virtual.entryCount(); i++) { + StoreIndexedNode store = graph.add(new StoreIndexedNode(newArray, ConstantNode.forInt(i, graph), element.kind(), values.get(i), -1)); + graph.addAfterFixed(position, store); + position = store; + } + + graph.removeFixed(this); + } + } + + @Override + public ValueNode canonical(CanonicalizerTool tool) { + if (usages().isEmpty()) { + return null; + } else { + return this; + } + } + + @Override + public EscapeOp getEscapeOp() { + return new EscapeOp() { + + @Override + public ValueNode[] fieldState() { + return values.toArray(new ValueNode[values.size()]); + } + + @Override + public VirtualObjectNode virtualObject(int virtualId) { + return virtualObject; + } + }; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/nodes/MaterializedObjectState.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,60 @@ +/* + * Copyright (c) 2009, 2012, 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.nodes; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.virtual.*; + +/** + * This class encapsulated the materialized state of an escape analyzed object. + */ +public final class MaterializedObjectState extends EscapeObjectState implements Node.IterableNodeType, LIRLowerable { + + @Input private ValueNode materializedValue; + + public ValueNode materializedValue() { + return materializedValue; + } + + public MaterializedObjectState(VirtualObjectNode object, ValueNode materializedValue) { + super(object); + this.materializedValue = materializedValue; + } + + @Override + public void generate(LIRGeneratorTool generator) { + // Nothing to do, virtual object states are processed as part of the handling of StateSplit nodes. + } + + @Override + public MaterializedObjectState duplicateWithVirtualState() { + return graph().add(new MaterializedObjectState(object(), materializedValue)); + } + + @Override + public void applyToNonVirtual(NodeClosure< ? super ValueNode> closure) { + closure.apply(this, materializedValue); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/nodes/VirtualObjectState.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,71 @@ +/* + * Copyright (c) 2009, 2012, 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.nodes; + +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.virtual.*; + +/** + * This class encapsulated the virtual state of an escape analyzed object. + */ +public final class VirtualObjectState extends EscapeObjectState implements Node.IterableNodeType, LIRLowerable { + + @Input private final NodeInputList<ValueNode> fieldValues; + + public NodeInputList<ValueNode> fieldValues() { + return fieldValues; + } + + public VirtualObjectState(VirtualObjectNode object, ValueNode[] fieldValues) { + super(object); + assert object.entryCount() == fieldValues.length; + this.fieldValues = new NodeInputList<>(this, fieldValues); + } + + private VirtualObjectState(VirtualObjectNode object, List<ValueNode> fieldValues) { + super(object); + assert object.entryCount() == fieldValues.size(); + this.fieldValues = new NodeInputList<>(this, fieldValues); + } + + @Override + public void generate(LIRGeneratorTool generator) { + // Nothing to do, virtual object states are processed as part of the handling of StateSplit nodes. + } + + @Override + public VirtualObjectState duplicateWithVirtualState() { + return graph().add(new VirtualObjectState(object(), fieldValues)); + } + + @Override + public void applyToNonVirtual(NodeClosure< ? super ValueNode> closure) { + for (ValueNode value : fieldValues) { + closure.apply(this, value); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/MergeableBlockState.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,29 @@ +/* + * Copyright (c) 2011, 2012, 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; + + +public interface MergeableBlockState<T> { + + T clone(); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,1148 @@ +/* + * Copyright (c) 2011, 2012, 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.code.*; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.api.meta.JavaType.*; +import com.oracle.graal.compiler.*; +import com.oracle.graal.compiler.phases.*; +import com.oracle.graal.compiler.schedule.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.PhiNode.PhiType; +import com.oracle.graal.nodes.VirtualState.NodeClosure; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.extended.*; +import com.oracle.graal.nodes.java.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.virtual.*; +import com.oracle.graal.virtual.nodes.*; + +class EscapeAnalysisIteration { + + // Metrics + private static final DebugMetric metricAllocationRemoved = Debug.metric("AllocationRemoved"); + private static final DebugMetric metricAllocationFieldsRemoved = Debug.metric("AllocationFieldsRemoved"); + private static final DebugMetric metricStoreRemoved = Debug.metric("StoreRemoved"); + private static final DebugMetric metricLoadRemoved = Debug.metric("LoadRemoved"); + private static final DebugMetric metricLockRemoved = Debug.metric("LockRemoved"); + private static final DebugMetric metricOtherRemoved = Debug.metric("OtherRemoved"); + private static final DebugMetric metricMaterializations = Debug.metric("Materializations"); + private static final DebugMetric metricMaterializationFields = Debug.metric("MaterializationFields"); + private static final DebugMetric metricLoopBailouts = Debug.metric("LoopBailouts"); + private static final DebugMetric metricMonitorBailouts = Debug.metric("MonitorBailouts"); + + + private static final ValueNode DUMMY_NODE = new ValueNode(null) { + }; + + 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)); + } + + private final StructuredGraph graph; + private final MetaAccessProvider runtime; + private final SchedulePhase schedule; + private final NodeBitMap usages; + boolean changed = false; + + private final boolean changeGraph; + + private final HashSet<VirtualObjectNode> reusedVirtualObjects = new HashSet<>(); + private final HashSet<ValueNode> allocations; + private final ArrayList<ValueNode> obsoleteNodes = new ArrayList<>(); + private int virtualIds = 0; + + public EscapeAnalysisIteration(StructuredGraph graph, SchedulePhase schedule, MetaAccessProvider runtime, HashSet<ValueNode> allocations, boolean changeGraph) { + this.graph = graph; + this.schedule = schedule; + this.runtime = runtime; + this.allocations = allocations; + this.changeGraph = changeGraph; + this.usages = graph.createNodeBitMap(); + } + + public void run() { + new PartialEscapeIterator(graph, schedule.getCFG().getStartBlock()).apply(); + + if (changeGraph) { + Debug.dump(graph, "after PartialEscapeAnalysis"); + + for (ValueNode node : obsoleteNodes) { + if (node.isAlive() && node instanceof FixedWithNextNode) { + FixedWithNextNode x = (FixedWithNextNode) node; + FixedNode next = x.next(); + x.setNext(null); + ((FixedWithNextNode) node.predecessor()).setNext(next); + } + } + new DeadCodeEliminationPhase().apply(graph); + + if (changed) { + Debug.log("escape analysis on %s\n", graph.method()); + } + } + } + + private static class ObjectState { + + public final VirtualObjectNode virtual; + public ValueNode[] fieldState; + public ValueNode materializedValue; + public int lockCount; + public boolean initialized; + + public ObjectState(VirtualObjectNode virtual, ValueNode[] fieldState, int lockCount) { + this.virtual = virtual; + this.fieldState = fieldState; + this.lockCount = lockCount; + this.initialized = false; + } + + public ObjectState(VirtualObjectNode virtual, ValueNode materializedValue, int lockCount) { + this.virtual = virtual; + this.materializedValue = materializedValue; + this.lockCount = lockCount; + this.initialized = true; + } + + private ObjectState(ObjectState other) { + virtual = other.virtual; + fieldState = other.fieldState == null ? null : other.fieldState.clone(); + materializedValue = other.materializedValue; + lockCount = other.lockCount; + initialized = other.initialized; + } + + @Override + public ObjectState clone() { + return new ObjectState(this); + } + + @Override + public String toString() { + StringBuilder str = new StringBuilder().append('{'); + if (lockCount > 0) { + str.append('l').append(lockCount).append(' '); + } + if (fieldState != null) { + for (int i = 0; i < fieldState.length; i++) { + str.append(virtual.fieldName(i)).append('=').append(fieldState[i]).append(' '); + } + } + if (materializedValue != null) { + str.append("mat=").append(materializedValue); + } + + return str.append('}').toString(); + } + } + + private class BlockState implements MergeableBlockState<BlockState> { + + private final HashMap<VirtualObjectNode, ObjectState> objectStates = new HashMap<>(); + private final HashMap<ValueNode, VirtualObjectNode> objectAliases = new HashMap<>(); + + public BlockState() { + } + + public BlockState(BlockState other) { + for (Map.Entry<VirtualObjectNode, ObjectState> entry : other.objectStates.entrySet()) { + objectStates.put(entry.getKey(), entry.getValue().clone()); + } + for (Map.Entry<ValueNode, VirtualObjectNode> entry : other.objectAliases.entrySet()) { + objectAliases.put(entry.getKey(), entry.getValue()); + } + } + + public ObjectState objectState(VirtualObjectNode object) { + assert objectStates.containsKey(object); + return objectStates.get(object); + } + + public ObjectState objectState(ValueNode value) { + VirtualObjectNode object = objectAliases.get(value); + return object == null ? null : objectState(object); + } + + @Override + public BlockState clone() { + return new BlockState(this); + } + + public void materializeBefore(FixedNode fixed, VirtualObjectNode virtual) { + if (changeGraph) { + HashSet<VirtualObjectNode> deferred = new HashSet<>(); + ArrayList<FixedWithNextNode> deferredStores = new ArrayList<>(); + materializeChangedBefore(fixed, virtual, deferred, deferredStores); + for (FixedWithNextNode write : deferredStores) { + write.setProbability(fixed.probability()); + graph.addBeforeFixed(fixed, write); + } + } else { + materializeUnchangedBefore(virtual); + } + } + + private void materializeUnchangedBefore(VirtualObjectNode virtual) { + trace("materializing %s", virtual); + ObjectState obj = objectState(virtual); + if (obj.lockCount > 0) { + if (changeGraph) { + error("object materialized with lock: %s\n", virtual); + } + metricMonitorBailouts.increment(); + throw new BailoutException("object materialized with lock"); + } + + ValueNode[] fieldState = obj.fieldState; + obj.fieldState = null; + obj.materializedValue = DUMMY_NODE; + for (int i = 0; i < fieldState.length; i++) { + ObjectState valueObj = objectState(fieldState[i]); + if (valueObj != null) { + if (valueObj.materializedValue == null) { + materializeUnchangedBefore(valueObj.virtual); + } + } + } + obj.initialized = true; + } + + private void materializeChangedBefore(FixedNode fixed, VirtualObjectNode virtual, HashSet<VirtualObjectNode> deferred, ArrayList<FixedWithNextNode> deferredStores) { + trace("materializing %s at %s", virtual, fixed); + ObjectState obj = objectState(virtual); + if (obj.lockCount > 0) { + error("object materialized with lock: %s\n", virtual); + metricMonitorBailouts.increment(); + throw new BailoutException("object materialized with lock"); + } + + MaterializeObjectNode materialize = graph.add(new MaterializeObjectNode(virtual, false)); + materialize.setProbability(fixed.probability()); + ValueNode[] fieldState = obj.fieldState; + metricMaterializations.increment(); + metricMaterializationFields.add(fieldState.length); + obj.fieldState = null; + obj.materializedValue = materialize; + deferred.add(virtual); + for (int i = 0; i < fieldState.length; i++) { + ObjectState valueObj = objectState(fieldState[i]); + if (valueObj != null) { + if (valueObj.materializedValue == null) { + materializeChangedBefore(fixed, valueObj.virtual, deferred, deferredStores); + } + if (deferred.contains(valueObj.virtual)) { + Kind fieldKind; + if (virtual instanceof VirtualArrayNode) { + deferredStores.add(graph.add(new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, i))); + fieldKind = ((VirtualArrayNode) virtual).componentType().kind(); + } else { + VirtualInstanceNode instanceObject = (VirtualInstanceNode) virtual; + deferredStores.add(graph.add(new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, instanceObject.field(i)))); + fieldKind = instanceObject.field(i).type().kind(); + } + materialize.values().set(i, ConstantNode.defaultForKind(fieldKind, graph)); + } else { + assert valueObj.initialized : "should be initialized: " + virtual + " at " + fixed; + materialize.values().set(i, valueObj.materializedValue); + } + } else { + materialize.values().set(i, fieldState[i]); + } + } + deferred.remove(virtual); + + obj.initialized = true; + graph.addBeforeFixed(fixed, materialize); + } + + private void addAndMarkAlias(VirtualObjectNode virtual, ValueNode node, boolean remove) { + objectAliases.put(node, virtual); + for (Node usage : node.usages()) { + markVirtualUsages(usage); + } + if (remove) { + obsoleteNodes.add(node); + } + } + + private void markVirtualUsages(Node node) { + if (!usages.isNew(node)) { + usages.mark(node); + } + if (node instanceof VirtualState) { + for (Node usage : node.usages()) { + markVirtualUsages(usage); + } + } + } + + public void addObject(VirtualObjectNode virtual, ObjectState state) { + objectStates.put(virtual, state); + } + + public Iterable<ObjectState> states() { + return objectStates.values(); + } + + @Override + public String toString() { + return objectStates.toString(); + } + } + + private class PartialEscapeIterator extends PostOrderBlockIterator<BlockState> { + + public PartialEscapeIterator(StructuredGraph graph, Block start) { + super(graph, start, new BlockState()); + } + + @Override + protected void processBlock(Block block, BlockState state) { + trace("\nBlock: %s (", block); + List<ScheduledNode> nodeList = schedule.getBlockToNodesMap().get(block); + + FixedWithNextNode lastFixedNode = null; + for (Node node : nodeList) { + EscapeOp op = null; + if (node instanceof EscapeAnalyzable) { + op = ((EscapeAnalyzable) node).getEscapeOp(); + } + if (op != null) { + // only escape analyze allocations that were escape analyzed during the first iteration + if (changeGraph && !allocations.contains(node)) { + op = null; + } + } + + if (op != null) { + trace("{{%s}} ", node); + VirtualObjectNode virtualObject = op.virtualObject(virtualIds); + if (virtualObject.isAlive()) { + reusedVirtualObjects.add(virtualObject); + state.addAndMarkAlias(virtualObject, virtualObject, false); + } else { + if (changeGraph) { + virtualObject = graph.add(virtualObject); + } + } + ValueNode[] fieldState = changeGraph ? op.fieldState() : new ValueNode[virtualObject.entryCount()]; + if (changeGraph) { + metricAllocationRemoved.increment(); + metricAllocationFieldsRemoved.add(fieldState.length); + } else { + allocations.add((ValueNode) node); + } + state.addObject(virtualObject, new ObjectState(virtualObject, fieldState, 0)); + state.addAndMarkAlias(virtualObject, (ValueNode) node, true); + virtualIds++; + } else { + if (changeGraph && node instanceof LoopExitNode) { + for (ObjectState obj : state.states()) { + if (obj.fieldState != null) { + for (int i = 0; i < obj.fieldState.length; i++) { + ValueNode value = obj.fieldState[i]; + ObjectState valueObj = state.objectState(value); + if (valueObj == null) { + obj.fieldState[i] = graph.unique(new ValueProxyNode(value, (LoopExitNode) node, PhiType.Value)); + } + } + } else { + obj.materializedValue = graph.unique(new ValueProxyNode(obj.materializedValue, (LoopExitNode) node, PhiType.Value)); + } + } + } + + if (usages.isMarked(node)) { + trace("[[%s]] ", node); + processNode((ValueNode) node, lastFixedNode == null ? null : lastFixedNode.next(), state); + } else { + trace("%s ", node); + } + } + + if (node instanceof FixedWithNextNode && node.isAlive()) { + lastFixedNode = (FixedWithNextNode) node; + } + } + trace(")\n end state: %s\n", state); + } + + private void processNode(final ValueNode node, FixedNode insertBefore, final BlockState state) { + boolean usageFound = false; + if (node instanceof PiNode || node instanceof ValueProxyNode) { + ValueNode value = node instanceof PiNode ? ((PiNode) node).object() : ((ValueProxyNode) node).value(); + ObjectState obj = state.objectState(value); + assert obj != null : node; + if (obj.materializedValue == null) { + state.addAndMarkAlias(obj.virtual, node, true); + } else { + if (changeGraph) { + node.replaceFirstInput(value, obj.materializedValue); + } + } + usageFound = true; + } else if (node instanceof CheckCastNode) { + CheckCastNode x = (CheckCastNode) node; + ObjectState obj = state.objectState(x.object()); + assert obj != null : x; + if (obj.materializedValue == null) { + if (x.targetClass() != null && obj.virtual.type().isSubtypeOf(x.targetClass())) { + metricOtherRemoved.increment(); + state.addAndMarkAlias(obj.virtual, x, true); + // throw new UnsupportedOperationException("probably incorrect - losing dependency"); + } else { + replaceWithMaterialized(x.object(), x, state, obj); + } + } else { + if (changeGraph) { + node.replaceFirstInput(x.object(), obj.materializedValue); + } + } + usageFound = true; + } else if (node instanceof IsNullNode) { + IsNullNode x = (IsNullNode) node; + ObjectState obj = state.objectState(x.object()); + assert obj != null : x; + if (changeGraph) { + graph.replaceFloating(x, graph.unique(ConstantNode.forBoolean(false, graph))); + metricOtherRemoved.increment(); + } + usageFound = true; + } else if (node instanceof AccessMonitorNode) { + AccessMonitorNode x = (AccessMonitorNode) node; + ObjectState obj = state.objectState(x.object()); + if (obj != null) { + Debug.log("monitor operation %s on %s\n", x, obj.virtual); + if (node instanceof MonitorEnterNode) { + obj.lockCount++; + } else { + assert node instanceof MonitorExitNode; + obj.lockCount--; + } + if (changeGraph) { + changed = true; + if (obj.materializedValue == null) { + metricLockRemoved.increment(); + node.replaceFirstInput(x.object(), obj.virtual); + x.eliminate(); + } else { + node.replaceFirstInput(x.object(), obj.materializedValue); + } + } + usageFound = true; + } + } else if (node instanceof CyclicMaterializeStoreNode) { + CyclicMaterializeStoreNode x = (CyclicMaterializeStoreNode) node; + ObjectState obj = state.objectState(x.object()); + assert obj != null : x; + if (obj.virtual instanceof VirtualArrayNode) { + obj.fieldState[x.targetIndex()] = x.value(); + } else { + VirtualInstanceNode instance = (VirtualInstanceNode) obj.virtual; + int index = instance.fieldIndex(x.targetField()); + obj.fieldState[index] = x.value(); + } + if (changeGraph) { + graph.removeFixed(x); + } + usageFound = true; + } else if (node instanceof LoadFieldNode) { + LoadFieldNode x = (LoadFieldNode) node; + ObjectState obj = state.objectState(x.object()); + assert obj != null : x; + VirtualInstanceNode virtual = (VirtualInstanceNode) obj.virtual; + int fieldIndex = virtual.fieldIndex(x.field()); + if (fieldIndex == -1) { + // the field does not exist in the virtual object + ensureMaterialized(state, obj, x); + } + if (obj.materializedValue == null) { + ValueNode result = obj.fieldState[fieldIndex]; + ObjectState resultObj = state.objectState(result); + if (resultObj != null) { + state.addAndMarkAlias(resultObj.virtual, x, true); + } else { + if (changeGraph) { + x.replaceAtUsages(result); + graph.removeFixed(x); + } + } + if (changeGraph) { + metricLoadRemoved.increment(); + } + changed = true; + } else { + if (changeGraph) { + x.replaceFirstInput(x.object(), obj.materializedValue); + } + } + usageFound = true; + } else if (node instanceof StoreFieldNode) { + StoreFieldNode x = (StoreFieldNode) node; + ValueNode object = x.object(); + ValueNode value = x.value(); + ObjectState obj = state.objectState(object); + if (obj != null) { + VirtualInstanceNode virtual = (VirtualInstanceNode) obj.virtual; + int fieldIndex = virtual.fieldIndex(x.field()); + if (fieldIndex == -1) { + // the field does not exist in the virtual object + ensureMaterialized(state, obj, x); + } + if (obj.materializedValue == null) { + obj.fieldState[fieldIndex] = value; + if (changeGraph) { + graph.removeFixed(x); + metricStoreRemoved.increment(); + } + changed = true; + } else { + if (changeGraph) { + x.replaceFirstInput(object, obj.materializedValue); + } + ObjectState valueObj = state.objectState(value); + if (valueObj != null) { + replaceWithMaterialized(value, x, state, valueObj); + } + } + usageFound = true; + } else { + ObjectState valueObj = state.objectState(value); + if (valueObj != null) { + replaceWithMaterialized(value, x, state, valueObj); + usageFound = true; + } + } + } else if (node instanceof LoadIndexedNode) { + LoadIndexedNode x = (LoadIndexedNode) node; + ValueNode array = x.array(); + ObjectState arrayObj = state.objectState(array); + if (arrayObj != null) { + if (arrayObj.materializedValue == null) { + int index = x.index().isConstant() ? x.index().asConstant().asInt() : -1; + if (index < 0 || index >= arrayObj.fieldState.length) { + // out of bounds or not constant + replaceWithMaterialized(array, x, state, arrayObj); + } else { + ValueNode result = arrayObj.fieldState[index]; + ObjectState resultObj = state.objectState(result); + if (resultObj != null) { + state.addAndMarkAlias(resultObj.virtual, x, true); + } else { + if (changeGraph) { + x.replaceAtUsages(result); + graph.removeFixed(x); + } + } + if (changeGraph) { + metricLoadRemoved.increment(); + } + changed = true; + } + } else { + if (changeGraph) { + x.replaceFirstInput(array, arrayObj.materializedValue); + } + } + usageFound = true; + } + } else if (node instanceof StoreIndexedNode) { + StoreIndexedNode x = (StoreIndexedNode) node; + ValueNode array = x.array(); + ValueNode value = x.value(); + ObjectState arrayObj = state.objectState(array); + ObjectState valueObj = state.objectState(value); + + if (arrayObj != null) { + if (arrayObj.materializedValue == null) { + int index = x.index().isConstant() ? x.index().asConstant().asInt() : -1; + if (index < 0 || index >= arrayObj.fieldState.length) { + // out of bounds or not constant + replaceWithMaterialized(array, x, state, arrayObj); + if (valueObj != null) { + replaceWithMaterialized(value, x, state, valueObj); + } + } else { + arrayObj.fieldState[index] = value; + if (changeGraph) { + graph.removeFixed(x); + metricStoreRemoved.increment(); + } + changed = true; + } + } else { + if (changeGraph) { + x.replaceFirstInput(array, arrayObj.materializedValue); + } + if (valueObj != null) { + replaceWithMaterialized(value, x, state, valueObj); + } + } + usageFound = true; + } else { + if (valueObj != null) { + replaceWithMaterialized(value, x, state, valueObj); + usageFound = true; + } + } + } else if (node instanceof RegisterFinalizerNode) { + RegisterFinalizerNode x = (RegisterFinalizerNode) node; + ObjectState obj = state.objectState(x.object()); + replaceWithMaterialized(x.object(), x, state, obj); + usageFound = true; + } else if (node instanceof ArrayLengthNode) { + ArrayLengthNode x = (ArrayLengthNode) node; + ObjectState obj = state.objectState(x.array()); + assert obj != null : x; + if (changeGraph) { + graph.replaceFixedWithFloating(x, ConstantNode.forInt(((VirtualArrayNode) obj.virtual).entryCount(), graph)); + metricOtherRemoved.increment(); + } + changed = true; + usageFound = true; + } else if (node instanceof LoadHubNode) { + LoadHubNode x = (LoadHubNode) node; + ObjectState obj = state.objectState(x.object()); + assert obj != null : x; + if (changeGraph) { + ConstantNode hub = ConstantNode.forConstant(obj.virtual.type().getEncoding(Representation.ObjectHub), runtime, graph); + graph.replaceFixedWithFloating(x, hub); + metricOtherRemoved.increment(); + } + changed = true; + usageFound = true; + } else if (node instanceof ReturnNode) { + ReturnNode x = (ReturnNode) node; + ObjectState obj = state.objectState(x.result()); + replaceWithMaterialized(x.result(), x, state, obj); + usageFound = true; + } else if (node instanceof MethodCallTargetNode) { + for (ValueNode argument : ((MethodCallTargetNode) node).arguments()) { + ObjectState obj = state.objectState(argument); + if (obj != null) { + replaceWithMaterialized(argument, node, insertBefore, state, obj); + usageFound = true; + } + } + } else if (node instanceof ObjectEqualsNode) { + ObjectEqualsNode x = (ObjectEqualsNode) node; + ObjectState xObj = state.objectState(x.x()); + ObjectState yObj = state.objectState(x.y()); + boolean xVirtual = xObj != null && xObj.materializedValue == null; + boolean yVirtual = yObj != null && yObj.materializedValue == null; + + if (changeGraph) { + if (xVirtual ^ yVirtual) { + // one of them is virtual: they can never be the same objects + graph.replaceFloating(x, ConstantNode.forBoolean(false, graph)); + usageFound = true; + metricOtherRemoved.increment(); + changed = true; + } else if (xVirtual && yVirtual) { + // both are virtual: check if they refer to the same object + graph.replaceFloating(x, ConstantNode.forBoolean(xObj == yObj, graph)); + usageFound = true; + metricOtherRemoved.increment(); + changed = true; + } else { + assert xObj != null || yObj != null; + if (xObj != null) { + assert xObj.materializedValue != null; + node.replaceFirstInput(x.x(), xObj.materializedValue); + } + if (yObj != null) { + assert yObj.materializedValue != null; + node.replaceFirstInput(x.y(), yObj.materializedValue); + } + } + } + usageFound = true; + } else if (node instanceof MergeNode) { + usageFound = true; + } else if (node instanceof UnsafeLoadNode || node instanceof UnsafeStoreNode || node instanceof CompareAndSwapNode || node instanceof SafeReadNode) { + for (ValueNode input : node.inputs().filter(ValueNode.class)) { + ObjectState obj = state.objectState(input); + if (obj != null) { + replaceWithMaterialized(input, node, insertBefore, state, obj); + usageFound = true; + } + } + } + if (node.isAlive() && node instanceof StateSplit) { + StateSplit split = (StateSplit) node; + FrameState stateAfter = split.stateAfter(); + if (stateAfter != null) { + if (changeGraph) { + if (stateAfter.usages().size() > 1) { + stateAfter = (FrameState) stateAfter.copyWithInputs(); + split.setStateAfter(stateAfter); + } + final HashSet<ObjectState> virtual = new HashSet<>(); + stateAfter.applyToNonVirtual(new NodeClosure<ValueNode>() { + + @Override + public void apply(Node usage, ValueNode value) { + ObjectState valueObj = state.objectState(value); + if (valueObj != null) { + virtual.add(valueObj); + usage.replaceFirstInput(value, valueObj.virtual); + } else if (value instanceof VirtualObjectNode) { + ObjectState virtualObj = null; + for (ObjectState obj : state.states()) { + if (value == obj.virtual) { + virtualObj = obj; + break; + } + } + if (virtualObj != null) { + virtual.add(virtualObj); + } + } + } + }); + for (ObjectState obj : state.states()) { + if (obj.materializedValue == null && obj.lockCount > 0) { + virtual.add(obj); + } + } + + ArrayDeque<ObjectState> queue = new ArrayDeque<>(virtual); + while (!queue.isEmpty()) { + ObjectState obj = queue.removeLast(); + if (obj.materializedValue == null) { + for (ValueNode field : obj.fieldState) { + ObjectState fieldObj = state.objectState(field); + if (fieldObj != null) { + if (fieldObj.materializedValue == null && !virtual.contains(fieldObj)) { + virtual.add(fieldObj); + queue.addLast(fieldObj); + } + } + } + } + } + for (ObjectState obj : virtual) { + EscapeObjectState v; + if (obj.materializedValue == null) { + ValueNode[] fieldState = obj.fieldState.clone(); + for (int i = 0; i < fieldState.length; i++) { + ObjectState valueObj = state.objectState(fieldState[i]); + if (valueObj != null) { + if (valueObj.materializedValue == null) { + fieldState[i] = valueObj.virtual; + } else { + fieldState[i] = valueObj.materializedValue; + } + } + } + v = graph.add(new VirtualObjectState(obj.virtual, fieldState)); + } else { + v = graph.add(new MaterializedObjectState(obj.virtual, obj.materializedValue)); + } + for (int i = 0; i < stateAfter.virtualObjectMappingCount(); i++) { + if (stateAfter.virtualObjectMappingAt(i).object() == v.object()) { + if (reusedVirtualObjects.contains(v.object())) { + stateAfter.virtualObjectMappings().remove(i); + } else { + throw new GraalInternalError("unexpected duplicate virtual state at: %s for %s", node, v.object()); + } + } + } + stateAfter.addVirtualObjectMapping(v); + } + } + usageFound = true; + } + } + if (!usageFound) { + for (ValueNode input : node.inputs().filter(ValueNode.class)) { + ObjectState obj = state.objectState(input); + if (obj != null) { + replaceWithMaterialized(input, node, insertBefore, state, obj); + usageFound = true; + } + } + Debug.log("unexpected usage of %s: %s\n", node, node.inputs().snapshot()); + } + } + + private void ensureMaterialized(BlockState state, ObjectState obj, FixedNode materializeBefore) { + assert obj != null; + if (obj.materializedValue == null) { + state.materializeBefore(materializeBefore, obj.virtual); + } + assert obj.materializedValue != null; + } + + private void replaceWithMaterialized(ValueNode value, FixedNode usage, BlockState state, ObjectState obj) { + ensureMaterialized(state, obj, usage); + if (changeGraph) { + usage.replaceFirstInput(value, obj.materializedValue); + } + } + + private void replaceWithMaterialized(ValueNode value, Node usage, FixedNode materializeBefore, BlockState state, ObjectState obj) { + ensureMaterialized(state, obj, materializeBefore); + if (changeGraph) { + usage.replaceFirstInput(value, obj.materializedValue); + } + } + + @Override + protected BlockState merge(MergeNode merge, List<BlockState> states) { + BlockState newState = new BlockState(); + + newState.objectAliases.putAll(states.get(0).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()) { + if (state.objectAliases.containsKey(entry.getKey())) { + assert state.objectAliases.get(entry.getKey()) == entry.getValue(); + } else { + newState.objectAliases.remove(entry.getKey()); + } + } + } + + // Iterative processing: + // Merging the materialized/virtual state of virtual objects can lead to new materializations, which can + // lead to new materializations because of phis, and so on. + + boolean materialized; + do { + materialized = false; + // use a hash set to make the values distinct... + for (VirtualObjectNode object : new HashSet<>(newState.objectAliases.values())) { + ObjectState resultState = newState.objectStates.get(object); + if (resultState == null || resultState.materializedValue == null) { + int virtual = 0; + int lockCount = states.get(0).objectState(object).lockCount; + for (BlockState state : states) { + ObjectState obj = state.objectState(object); + if (obj.materializedValue == null) { + virtual++; + } + assert obj.lockCount == lockCount : "mismatching lock counts"; + } + + if (virtual < states.size()) { + ValueNode materializedValuePhi = changeGraph ? graph.add(new PhiNode(Kind.Object, merge)) : DUMMY_NODE; + for (int i = 0; i < states.size(); i++) { + BlockState state = states.get(i); + ObjectState obj = state.objectState(object); + materialized |= obj.materializedValue == null; + ensureMaterialized(state, obj, merge.forwardEndAt(i)); + if (changeGraph) { + ((PhiNode) materializedValuePhi).addInput(obj.materializedValue); + } + } + newState.addObject(object, new ObjectState(object, materializedValuePhi, lockCount)); + } else { + assert virtual == states.size(); + ValueNode[] values = states.get(0).objectState(object).fieldState.clone(); + PhiNode[] phis = new PhiNode[values.length]; + boolean[] phiCreated = new boolean[values.length]; + int mismatch = 0; + for (int i = 1; i < states.size(); i++) { + BlockState state = states.get(i); + ValueNode[] fields = state.objectState(object).fieldState; + for (int index = 0; index < values.length; index++) { + if (!phiCreated[index] && values[index] != fields[index]) { + mismatch++; + if (changeGraph) { + phis[index] = graph.add(new PhiNode(values[index].kind(), merge)); + } + phiCreated[index] = true; + } + } + } + if (mismatch > 0) { + for (int i = 0; i < states.size(); i++) { + BlockState state = states.get(i); + ValueNode[] fields = state.objectState(object).fieldState; + for (int index = 0; index < values.length; index++) { + if (phiCreated[index]) { + ObjectState obj = state.objectState(fields[index]); + if (obj != null) { + materialized |= obj.materializedValue == null; + ensureMaterialized(state, obj, merge.forwardEndAt(i)); + fields[index] = obj.materializedValue; + } + if (changeGraph) { + phis[index].addInput(fields[index]); + } + } + } + } + for (int index = 0; index < values.length; index++) { + if (phiCreated[index]) { + values[index] = phis[index]; + } + } + } + newState.addObject(object, new ObjectState(object, values, lockCount)); + } + } + } + + for (PhiNode phi : merge.phis().snapshot()) { + if (usages.isMarked(phi) && phi.type() == PhiType.Value) { + materialized |= processPhi(newState, merge, phi, states); + } + } + } while (materialized); + + return newState; + } + + private boolean processPhi(BlockState newState, MergeNode merge, PhiNode phi, List<BlockState> states) { + assert states.size() == phi.valueCount(); + int virtualInputs = 0; + boolean materialized = false; + VirtualObjectNode sameObject = null; + ResolvedJavaType sameType = null; + int sameEntryCount = -1; + for (int i = 0; i < phi.valueCount(); i++) { + ValueNode value = phi.valueAt(i); + ObjectState obj = states.get(i).objectState(value); + if (obj != null) { + if (obj.materializedValue == null) { + virtualInputs++; + if (i == 0) { + sameObject = obj.virtual; + sameType = obj.virtual.type(); + sameEntryCount = obj.virtual.entryCount(); + } else { + if (sameObject != obj.virtual) { + sameObject = null; + } + if (sameType != obj.virtual.type()) { + sameType = null; + } + if (sameEntryCount != obj.virtual.entryCount()) { + sameEntryCount = -1; + } + } + } else { + if (changeGraph) { + phi.setValueAt(i, obj.materializedValue); + } + } + } + } + boolean materialize = false; + if (virtualInputs == 0) { + // nothing to do... + } else if (virtualInputs == phi.valueCount()) { + if (sameObject != null) { + newState.addAndMarkAlias(sameObject, phi, true); + } else if (sameType != null && sameEntryCount != -1) { + materialize = true; + // throw new GraalInternalError("merge required for %s", sameType); + } else { + materialize = true; + } + } else { + materialize = true; + } + + if (materialize) { + for (int i = 0; i < phi.valueCount(); i++) { + ValueNode value = phi.valueAt(i); + ObjectState obj = states.get(i).objectState(value); + if (obj != null) { + materialized |= obj.materializedValue == null; + replaceWithMaterialized(value, phi, merge.forwardEndAt(i), states.get(i), obj); + } + } + } + return materialized; + } + + @Override + protected BlockState loopBegin(LoopBeginNode loopBegin, BlockState beforeLoopState) { + BlockState state = beforeLoopState; + for (ObjectState obj : state.states()) { + if (obj.fieldState != null) { + for (int i = 0; obj.fieldState != null && i < obj.fieldState.length; i++) { + ValueNode value = obj.fieldState[i]; + ObjectState valueObj = state.objectState(value); + if (valueObj != null) { + ensureMaterialized(state, valueObj, loopBegin.forwardEnd()); + value = valueObj.materializedValue; + } + } + } + } + for (ObjectState obj : state.states()) { + if (obj.fieldState != null) { + for (int i = 0; i < obj.fieldState.length; i++) { + ValueNode value = obj.fieldState[i]; + ObjectState valueObj = state.objectState(value); + if (valueObj != null) { + value = valueObj.materializedValue; + } + if (changeGraph) { + assert value != null; + PhiNode valuePhi = graph.add(new PhiNode(value.kind(), loopBegin)); + valuePhi.addInput(value); + obj.fieldState[i] = valuePhi; + } + } + } + } + for (PhiNode phi : loopBegin.phis()) { + ObjectState obj = state.objectState(phi.valueAt(0)); + if (obj != null) { + ensureMaterialized(state, obj, loopBegin.forwardEnd()); + if (changeGraph) { + phi.setValueAt(0, obj.materializedValue); + } + } + } + return state.clone(); + } + + @Override + protected BlockState loopEnds(LoopBeginNode loopBegin, BlockState loopBeginState, List<BlockState> loopEndStates) { + BlockState state = loopBeginState.clone(); + List<LoopEndNode> loopEnds = loopBegin.orderedLoopEnds(); + for (ObjectState obj : state.states()) { + if (obj.fieldState != null) { + Iterator<LoopEndNode> iter = loopEnds.iterator(); + for (BlockState loopEndState : loopEndStates) { + LoopEndNode loopEnd = iter.next(); + ObjectState endObj = loopEndState.objectState(obj.virtual); + if (endObj.fieldState == null) { + if (changeGraph) { + error("object materialized within loop: %s\n", obj.virtual); + } + metricLoopBailouts.increment(); + throw new BailoutException("object materialized within loop"); + } + for (int i = 0; endObj.fieldState != null && i < endObj.fieldState.length; i++) { + ValueNode value = endObj.fieldState[i]; + ObjectState valueObj = loopEndState.objectState(value); + if (valueObj != null) { + ensureMaterialized(loopEndState, valueObj, loopEnd); + value = valueObj.materializedValue; + } + if (changeGraph) { + ((PhiNode) obj.fieldState[i]).addInput(value); + } + } + } + } + } + for (PhiNode phi : loopBegin.phis()) { + if (phi.valueCount() == 1) { + if (changeGraph) { + phi.replaceAtUsages(phi.valueAt(0)); + } + } else { + assert phi.valueCount() == loopEndStates.size() + 1; + for (int i = 0; i < loopEndStates.size(); i++) { + BlockState loopEndState = loopEndStates.get(i); + ObjectState obj = loopEndState.objectState(phi.valueAt(i + 1)); + if (obj != null) { + ensureMaterialized(loopEndState, obj, loopEnds.get(i)); + if (changeGraph) { + phi.setValueAt(i + 1, obj.materializedValue); + } + } + } + } + } + return state; + } + + @Override + protected BlockState afterSplit(FixedNode node, BlockState oldState) { + return oldState.clone(); + } + } +} + +public class PartialEscapeAnalysisPhase extends Phase { + + private final TargetDescription target; + private final GraalCodeCacheProvider runtime; + private final Assumptions assumptions; + + public PartialEscapeAnalysisPhase(TargetDescription target, GraalCodeCacheProvider runtime, Assumptions assumptions) { + this.runtime = runtime; + this.target = target; + this.assumptions = assumptions; + } + + @Override + protected void run(StructuredGraph graph) { + iteration(graph, 0); + } + + + private void iteration(final StructuredGraph graph, final int num) { + HashSet<ValueNode> allocations = new HashSet<>(); + SchedulePhase schedule = new SchedulePhase(); + schedule.apply(graph, false); + EscapeAnalysisIteration iteration = null; + try { + iteration = new EscapeAnalysisIteration(graph, schedule, runtime, allocations, false); + iteration.run(); + } catch (BailoutException e) { + // do nothing if the if the escape analysis bails out during the analysis iteration... + return; + } + if (iteration.changed) { + try { + new EscapeAnalysisIteration(graph, schedule, runtime, allocations, true).run(); + new CanonicalizerPhase(target, runtime, assumptions).apply(graph); + } catch (BailoutException e) { + throw new GraalInternalError(e); + } + // next round... + if (num < 2) { + Debug.scope("next", new Runnable() { + @Override + public void run() { + iteration(graph, num + 1); + } + }); + } + } + } +} +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PostOrderBlockIterator.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,183 @@ +/* + * Copyright (c) 2011, 2012, 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.graph.*; +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; + +public abstract class PostOrderBlockIterator<T extends MergeableBlockState<T>> { + + private final NodeBitMap visitedEnds; + private final Deque<Block> blockQueue; + private final IdentityHashMap<FixedNode, T> blockEndStates; + private final IdentityHashMap<LoopBeginNode, T> loopBeginStates; + private final Block start; + + private T state; + + public PostOrderBlockIterator(StructuredGraph graph, Block start, T initialState) { + visitedEnds = graph.createNodeBitMap(); + blockQueue = new ArrayDeque<>(); + blockEndStates = new IdentityHashMap<>(); + loopBeginStates = new IdentityHashMap<>(); + this.start = start; + this.state = initialState; + } + + public void apply() { + Block current = start; + + do { + processBlock(current, state); + + if (current.getSuccessors().isEmpty()) { + // nothing to do... + } else if (current.getSuccessors().size() == 1) { + Block successor = current.getSuccessors().get(0); + if (successor.isLoopHeader()) { + if (current.getEndNode() instanceof LoopEndNode) { + finishLoopEnds((LoopEndNode) current.getEndNode()); + } else { + LoopBeginNode loopBegin = (LoopBeginNode) successor.getBeginNode(); + state = loopBegin(loopBegin, state); + loopBeginStates.put(loopBegin, state); + state = state.clone(); + current = successor; + continue; + } + } else { + if (successor.getBeginNode() instanceof LoopExitNode) { + assert successor.getPredecessors().size() == 1; + current = successor; + continue; + } else { + if (current.getEndNode() instanceof EndNode) { + assert successor.getPredecessors().size() > 1 : "invalid block schedule at " + successor.getBeginNode(); + queueMerge((EndNode) current.getEndNode(), successor); + } else { + assert successor.getPredecessors().size() == 1 : "invalid block schedule at " + successor.getBeginNode(); + current = successor; + continue; + } + } + } + } else { + assert current.getSuccessors().size() > 1; + queueSuccessors(current); + } + current = nextQueuedBlock(); + } while (current != null); + } + + protected abstract void processBlock(Block block, T currentState); + + protected abstract T merge(MergeNode merge, List<T> states); + + protected abstract T loopBegin(LoopBeginNode loopBegin, T beforeLoopState); + + protected abstract T loopEnds(LoopBeginNode loopBegin, T loopBeginState, List<T> loopEndStates); + + protected abstract T afterSplit(FixedNode node, T oldState); + + + private void queueSuccessors(Block current) { + blockEndStates.put(current.getEndNode(), state); + for (Block block : current.getSuccessors()) { + blockQueue.addFirst(block); + } + } + + private Block nextQueuedBlock() { + int maxIterations = blockQueue.size(); + while (maxIterations-- > 0) { + Block block = blockQueue.removeFirst(); + if (block.getPredecessors().size() > 1) { + MergeNode merge = (MergeNode) block.getBeginNode(); + ArrayList<T> states = new ArrayList<>(merge.forwardEndCount()); + for (int i = 0; i < merge.forwardEndCount(); i++) { + T other = blockEndStates.get(merge.forwardEndAt(i)); + assert other != null; + states.add(other); + } + state = merge(merge, states); + if (state != null) { + return block; + } else { + blockQueue.addLast(block); + } + } else { + assert block.getPredecessors().size() == 1; + assert block.getBeginNode().predecessor() != null; + state = afterSplit(block.getBeginNode(), blockEndStates.get(block.getBeginNode().predecessor())); + return block; + } + } + return null; + } + + private void queueMerge(EndNode end, Block mergeBlock) { + assert !visitedEnds.isMarked(end); + assert !blockEndStates.containsKey(end); + blockEndStates.put(end, state); + visitedEnds.mark(end); + MergeNode merge = end.merge(); + boolean endsVisited = true; + for (int i = 0; i < merge.forwardEndCount(); i++) { + if (!visitedEnds.isMarked(merge.forwardEndAt(i))) { + endsVisited = false; + break; + } + } + if (endsVisited) { + blockQueue.addFirst(mergeBlock); + } + } + + private void finishLoopEnds(LoopEndNode end) { + assert !visitedEnds.isMarked(end); + assert !blockEndStates.containsKey(end); + blockEndStates.put(end, state); + visitedEnds.mark(end); + LoopBeginNode begin = end.loopBegin(); + boolean endsVisited = true; + for (LoopEndNode le : begin.loopEnds()) { + if (!visitedEnds.isMarked(le)) { + endsVisited = false; + break; + } + } + if (endsVisited) { + ArrayList<T> states = new ArrayList<>(begin.loopEnds().count()); + for (LoopEndNode le : begin.orderedLoopEnds()) { + states.add(blockEndStates.get(le)); + } + T loopBeginState = loopBeginStates.get(begin); + if (loopBeginState != null) { + loopEnds(begin, loopBeginState, states); + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/BlockIteratorClosure.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,46 @@ +/* + * Copyright (c) 2011, 2012, 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.experimental; + +import java.util.*; + +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.virtual.phases.ea.*; + +public abstract class BlockIteratorClosure<T extends MergeableBlockState<T>> { + + public static class LoopInfo<T extends MergeableBlockState<T>> { + + public final List<T> endStates = new ArrayList<>(); + public final List<T> exitStates = new ArrayList<>(); + } + + protected abstract void processBlock(Block block, T currentState); + + protected abstract T merge(MergeNode merge, List<T> states); + + protected abstract T afterSplit(FixedNode node, T oldState); + + protected abstract List<T> processLoop(Loop loop, T initialState); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/EffectList.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,181 @@ +/* + * Copyright (c) 2012, 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.experimental; + +import java.lang.reflect.*; +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; + +public class EffectList implements Iterable<EffectList.Effect> { + + public abstract static class Effect { + + public boolean isVisible() { + return true; + } + + @Override + public String toString() { + StringBuilder str = new StringBuilder(); + for (Field field : getClass().getDeclaredFields()) { + String name = field.getName(); + if (name.contains("$")) { + name = name.substring(name.indexOf('$') + 1); + } + if (!Modifier.isStatic(field.getModifiers()) && !name.equals("0")) { + try { + field.setAccessible(true); + str.append(str.length() > 0 ? ", " : "").append(name).append("=").append(format(field.get(this))); + } catch (Exception e) { + e.printStackTrace(); + } + } + } + return name() + " [" + str + "]"; + } + + private static String format(Object object) { + if (object != null && Object[].class.isAssignableFrom(object.getClass())) { + return Arrays.toString((Object[]) object); + } + return "" + object; + } + + public abstract String name(); + + public abstract void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes); + } + + private Effect[] effects = new Effect[16]; + private int[] level = new int[16]; + private int size; + private int currentLevel; + + public void add(Effect effect) { + if (effects.length == size) { + effects = Arrays.copyOf(effects, effects.length * 2); + level = Arrays.copyOf(level, effects.length); + } + level[size] = currentLevel; + effects[size++] = effect; + } + + public void addAll(Collection< ? extends Effect> list) { + int length = effects.length; + if (size + list.size() > length) { + while (size + list.size() > length) { + length *= 2; + } + effects = Arrays.copyOf(effects, length); + level = Arrays.copyOf(level, effects.length); + } + for (Effect effect : list) { + level[size] = currentLevel; + effects[size++] = effect; + } + } + + public void addAll(EffectList list) { + int length = effects.length; + if (size + list.size > length) { + while (size + list.size > length) { + length *= 2; + } + effects = Arrays.copyOf(effects, length); + level = Arrays.copyOf(level, effects.length); + } + for (Effect effect : list) { + level[size] = currentLevel; + effects[size++] = effect; + } + } + + public int checkpoint() { + return size; + } + + public int size() { + return size; + } + + public void backtrack(int checkpoint) { + assert checkpoint <= size; + size = checkpoint; + } + + @Override + public Iterator<Effect> iterator() { + return new Iterator<Effect>() { + + int index; + final int listSize = EffectList.this.size; + + @Override + public boolean hasNext() { + return index < listSize; + } + + @Override + public Effect next() { + return effects[index++]; + } + + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + }; + } + + public void incLevel() { + currentLevel++; + } + + public void decLevel() { + currentLevel--; + } + + public Effect get(int index) { + if (index >= size) { + throw new IndexOutOfBoundsException(); + } + return effects[index]; + } + + public int levelAt(int index) { + if (index >= size) { + throw new IndexOutOfBoundsException(); + } + return level[index]; + } + + public void clear() { + size = 0; + } + + public boolean isEmpty() { + return size == 0; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/GraphEffectList.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,223 @@ +/* + * Copyright (c) 2012, 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.experimental; + +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.java.*; +import com.oracle.graal.nodes.virtual.*; +import com.oracle.graal.virtual.nodes.*; + +public class GraphEffectList extends EffectList { + + public void addFixedNodeBefore(final FixedWithNextNode node, final FixedNode position) { + add(new Effect() { + + @Override + public String name() { + return "addFixedNodeBefore"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + assert !node.isAlive() && !node.isDeleted() && position.isAlive(); + graph.addBeforeFixed(position, graph.add(node)); + node.setProbability(position.probability()); + } + }); + } + + public void addFloatingNode(final FloatingNode node) { + add(new Effect() { + + @Override + public String name() { + return "addFloatingNode"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + assert !node.isAlive() && !node.isDeleted(); + graph.add(node); + } + }); + } + + public void addMaterialization(final MaterializeObjectNode node, final FixedNode position, final ValueNode[] values) { + add(new Effect() { + + @Override + public String name() { + return "addMaterialization"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + assert !node.isAlive() && !node.isDeleted() && position.isAlive(); + graph.addBeforeFixed(position, graph.add(node)); + node.setProbability(position.probability()); + for (int i = 0; i < values.length; i++) { + node.values().set(i, values[i]); + } + } + }); + } + + public void addPhiInput(final PhiNode node, final ValueNode value) { + add(new Effect() { + + @Override + public String name() { + return "addPhiInput"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + assert node.isAlive() && value.isAlive(); + node.addInput(value); + } + }); + } + + public void addVirtualMapping(final FrameState node, final EscapeObjectState state, final HashSet<VirtualObjectNode> reusedVirtualObjects) { + add(new Effect() { + + @Override + public String name() { + return "addVirtualMapping"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + assert node.isAlive() && !state.isAlive() && !state.isDeleted(); + FrameState stateAfter = node; + for (int i = 0; i < stateAfter.virtualObjectMappingCount(); i++) { + if (stateAfter.virtualObjectMappingAt(i).object() == state.object()) { + if (reusedVirtualObjects.contains(state.object())) { + stateAfter.virtualObjectMappings().remove(i); + } else { + throw new GraalInternalError("unexpected duplicate virtual state at: %s for %s", stateAfter, state.object()); + } + } + } + stateAfter.addVirtualObjectMapping(graph.add(state)); + } + + @Override + public boolean isVisible() { + return false; + } + }); + } + + public void deleteFixedNode(final FixedWithNextNode node) { + add(new Effect() { + + @Override + public String name() { + return "deleteFixedNode"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + assert node.isAlive(); + FixedNode next = node.next(); + node.setNext(null); + node.replaceAtPredecessor(next); + obsoleteNodes.add(node); + } + }); + } + + public void eliminateMonitor(final AccessMonitorNode node) { + add(new Effect() { + + @Override + public String name() { + return "eliminateMonitor"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + assert node.isAlive() && node.object().isAlive() && (node.object() instanceof VirtualObjectNode); + node.eliminate(); + } + }); + } + + public void replaceAtUsages(final ValueNode node, final ValueNode replacement) { + add(new Effect() { + + @Override + public String name() { + return "replaceAtUsages"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + assert node.isAlive() && replacement.isAlive(); + node.replaceAtUsages(replacement); + } + }); + } + + public void replaceFirstInput(final Node node, final ValueNode oldInput, final ValueNode newInput) { + add(new Effect() { + + @Override + public String name() { + return "replaceFirstInput"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + assert node.isAlive() && oldInput.isAlive() && newInput.isAlive(); + node.replaceFirstInput(oldInput, newInput); + } + + @Override + public boolean isVisible() { + return !(node instanceof FrameState); + } + }); + } + + public void setPhiInput(final PhiNode node, final ValueNode value, final int index) { + add(new Effect() { + + @Override + public String name() { + return "setPhiInput"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + assert node.isAlive() && value.isAlive() && index >= 0; + node.setValueAt(index, value); + } + }); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/ReentrantBlockIterator.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,165 @@ +/* + * Copyright (c) 2011, 2012, 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.experimental; + +import java.util.*; + +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.virtual.phases.ea.*; +import com.oracle.graal.virtual.phases.ea.experimental.BlockIteratorClosure.*; + +public final class ReentrantBlockIterator { + + private ReentrantBlockIterator() { + // no instances allowed + } + + public static <T extends MergeableBlockState<T>> LoopInfo<T> processLoop(BlockIteratorClosure<T> closure, Loop loop, T initialState) { + IdentityHashMap<FixedNode, T> blockEndStates = apply(closure, loop.header, initialState, new HashSet<>(loop.blocks)); + + LoopInfo<T> info = new LoopInfo<>(); + List<Block> predecessors = loop.header.getPredecessors(); + for (int i = 1; i < predecessors.size(); i++) { + info.endStates.add(blockEndStates.get(predecessors.get(i).getEndNode())); + } + for (Block loopExit : loop.exits) { + assert loopExit.getPredecessors().size() == 1; + T exitState = blockEndStates.get(loopExit.getPredecessors().get(0).getEndNode()); + assert exitState != null; + info.exitStates.add(exitState); + } + return info; + } + + public static <T extends MergeableBlockState<T>> IdentityHashMap<FixedNode, T> apply(BlockIteratorClosure<T> closure, Block start, T initialState, Set<Block> boundary) { + Deque<Block> blockQueue = new ArrayDeque<>(); + IdentityHashMap<FixedNode, T> blockEndStates = new IdentityHashMap<>(); + + T state = initialState; + Block current = start; + + do { + if (boundary == null || boundary.contains(current)) { + closure.processBlock(current, state); + + if (current.getSuccessors().isEmpty()) { + // nothing to do... + } else if (current.getSuccessors().size() == 1) { + Block successor = current.getSuccessors().get(0); + if (successor.isLoopHeader()) { + if (current.isLoopEnd()) { + // nothing to do... loop ends only lead to loop begins we've already visited + blockEndStates.put(current.getEndNode(), state); + } else { + // recurse into the loop + Loop loop = successor.getLoop(); + LoopBeginNode loopBegin = loop.loopBegin(); + assert successor.getBeginNode() == loopBegin; + + List<T> exitStates = closure.processLoop(loop, state); + + int i = 0; + assert loop.exits.size() == exitStates.size(); + for (Block exit : loop.exits) { + blockEndStates.put(exit.getPredecessors().get(0).getEndNode(), exitStates.get(i++)); + blockQueue.addFirst(exit); + } + } + } else { + if (successor.getBeginNode() instanceof LoopExitNode) { + assert successor.getPredecessors().size() == 1; + blockEndStates.put(current.getEndNode(), state); + current = successor; + continue; + } else { + if (current.getEndNode() instanceof EndNode) { + assert successor.getPredecessors().size() > 1 : "invalid block schedule at " + successor.getBeginNode(); + EndNode end = (EndNode) current.getEndNode(); + + // add the end node and see if the merge is ready for processing + assert !blockEndStates.containsKey(end); + blockEndStates.put(end, state); + MergeNode merge = end.merge(); + boolean endsVisited = true; + for (int i = 0; i < merge.forwardEndCount(); i++) { + if (!blockEndStates.containsKey(merge.forwardEndAt(i))) { + endsVisited = false; + break; + } + } + if (endsVisited) { + blockQueue.addFirst(successor); + } + } else { + assert successor.getPredecessors().size() == 1 : "invalid block schedule at " + successor.getBeginNode(); + current = successor; + continue; + } + } + } + } else { + assert current.getSuccessors().size() > 1; + blockEndStates.put(current.getEndNode(), state); + for (Block block : current.getSuccessors()) { + blockQueue.addFirst(block); + } + } + } + + // get next queued block + if (blockQueue.isEmpty()) { + current = null; + } else { + int maxIterations = blockQueue.size(); + while (maxIterations-- > 0) { + current = blockQueue.removeFirst(); + if (current.getPredecessors().size() > 1) { + MergeNode merge = (MergeNode) current.getBeginNode(); + ArrayList<T> states = new ArrayList<>(merge.forwardEndCount()); + for (int i = 0; i < merge.forwardEndCount(); i++) { + T other = blockEndStates.get(merge.forwardEndAt(i)); + assert other != null; + states.add(other); + } + state = closure.merge(merge, states); + if (state != null) { + break; + } else { + blockQueue.addLast(current); + current = null; + } + } else { + assert current.getPredecessors().size() == 1; + assert current.getBeginNode().predecessor() != null; + if (boundary == null || boundary.contains(current)) { + state = closure.afterSplit(current.getBeginNode(), blockEndStates.get(current.getBeginNode().predecessor())); + break; + } + } + } + } + } while (current != null); + return blockEndStates; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/SplitPartialEscapeAnalysisPhase.java Sun Oct 07 14:11:55 2012 +0200 @@ -0,0 +1,1253 @@ +/* + * Copyright (c) 2011, 2012, 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.experimental; + +import java.util.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.JavaType.Representation; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.*; +import com.oracle.graal.compiler.phases.*; +import com.oracle.graal.compiler.schedule.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.PhiNode.PhiType; +import com.oracle.graal.nodes.VirtualState.NodeClosure; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.extended.*; +import com.oracle.graal.nodes.java.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.virtual.*; +import com.oracle.graal.virtual.nodes.*; +import com.oracle.graal.virtual.phases.ea.*; +import com.oracle.graal.virtual.phases.ea.experimental.EffectList.*; + +class EscapeAnalysisIteration { + + 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)); + } + + private final StructuredGraph graph; + private final MetaAccessProvider runtime; + private final SchedulePhase schedule; + private final NodeBitMap usages; + + private final HashSet<VirtualObjectNode> reusedVirtualObjects = new HashSet<>(); + private int virtualIds = 0; + + public EscapeAnalysisIteration(StructuredGraph graph, SchedulePhase schedule, MetaAccessProvider runtime) { + this.graph = graph; + this.schedule = schedule; + this.runtime = runtime; + this.usages = graph.createNodeBitMap(); + } + + public void run() { + PartialEscapeClosure closure = new PartialEscapeClosure(); + ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock(), new BlockState(), null); + ArrayList<Node> obsoleteNodes = new ArrayList<>(); + for (int i = 0; i < closure.effects.size(); i++) { + Effect effect = closure.effects.get(i); + effect.apply(graph, obsoleteNodes); + if (GraalOptions.TraceEscapeAnalysis) { + if (effect.isVisible()) { + int level = closure.effects.levelAt(i); + StringBuilder str = new StringBuilder(); + for (int i2 = 0; i2 < level; i2++) { + str.append(" "); + } + trace(str.append(effect).toString()); + } + } + } + Debug.dump(graph, "after PartialEscapeAnalysis"); + + // 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 EndNode) { + // EndNode end = (EndNode) 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); + // } + // } + // + // 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); + // } + // } + // } + // + // for (Node node : obsoleteNodes) { + // if (flood.isMarked(node)) { + // System.out.println("offending node path:"); + // Node current = node; + // while (current != null) { + // System.out.println(current); + // current = path.get(current); + // if (current != null && current instanceof FixedNode && !obsoleteNodes.contains(current)) { + // break; + // } + // } + // } + // } + + new DeadCodeEliminationPhase().apply(graph); + + } + + private static class ObjectState { + + public final VirtualObjectNode virtual; + public ValueNode[] fieldState; + public ValueNode materializedValue; + public int lockCount; + + public ObjectState(VirtualObjectNode virtual, ValueNode[] fieldState, int lockCount) { + this.virtual = virtual; + this.fieldState = fieldState; + this.lockCount = lockCount; + } + + public ObjectState(VirtualObjectNode virtual, ValueNode materializedValue, int lockCount) { + this.virtual = virtual; + this.materializedValue = materializedValue; + this.lockCount = lockCount; + } + + private ObjectState(ObjectState other) { + virtual = other.virtual; + fieldState = other.fieldState == null ? null : other.fieldState.clone(); + materializedValue = other.materializedValue; + lockCount = other.lockCount; + } + + @Override + public ObjectState clone() { + return new ObjectState(this); + } + + @Override + public String toString() { + StringBuilder str = new StringBuilder().append('{'); + if (lockCount > 0) { + str.append('l').append(lockCount).append(' '); + } + if (fieldState != null) { + for (int i = 0; i < fieldState.length; i++) { + str.append(virtual.fieldName(i)).append('=').append(fieldState[i]).append(' '); + } + } + if (materializedValue != null) { + str.append("mat=").append(materializedValue); + } + + return str.append('}').toString(); + } + } + + private class BlockState implements MergeableBlockState<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<>(); + + public BlockState() { + } + + public BlockState(BlockState other) { + for (Map.Entry<VirtualObjectNode, ObjectState> entry : other.objectStates.entrySet()) { + objectStates.put(entry.getKey(), entry.getValue().clone()); + } + 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()); + } + } + + public ObjectState objectState(VirtualObjectNode object) { + assert objectStates.containsKey(object); + return objectStates.get(object); + } + + public ObjectState objectStateOptional(VirtualObjectNode object) { + return objectStates.get(object); + } + + public ObjectState objectState(ValueNode value) { + VirtualObjectNode object = objectAliases.get(value); + return object == null ? null : objectState(object); + } + + @Override + public BlockState clone() { + return new BlockState(this); + } + + public void materializeBefore(FixedNode fixed, VirtualObjectNode virtual, GraphEffectList materializeEffects) { + HashSet<VirtualObjectNode> deferred = new HashSet<>(); + GraphEffectList deferredStores = new GraphEffectList(); + materializeChangedBefore(fixed, virtual, deferred, deferredStores, materializeEffects); + materializeEffects.addAll(deferredStores); + } + + private void materializeChangedBefore(FixedNode fixed, VirtualObjectNode virtual, HashSet<VirtualObjectNode> deferred, GraphEffectList deferredStores, GraphEffectList materializeEffects) { + trace("materializing %s at %s", virtual, fixed); + ObjectState obj = objectState(virtual); + if (obj.lockCount > 0 && obj.virtual.type().isArrayClass()) { +// error("array materialized with lock: %s\n", virtual); + throw new BailoutException("array materialized with lock"); + } + + MaterializeObjectNode materialize = new MaterializeObjectNode(virtual, obj.lockCount > 0); + ValueNode[] values = new ValueNode[obj.fieldState.length]; + materialize.setProbability(fixed.probability()); + ValueNode[] fieldState = obj.fieldState; + obj.fieldState = null; + obj.materializedValue = materialize; + deferred.add(virtual); + for (int i = 0; i < fieldState.length; i++) { + ObjectState valueObj = objectState(fieldState[i]); + if (valueObj != null) { + if (valueObj.materializedValue == null) { + materializeChangedBefore(fixed, valueObj.virtual, deferred, deferredStores, materializeEffects); + } + if (deferred.contains(valueObj.virtual)) { + Kind fieldKind; + CyclicMaterializeStoreNode store; + if (virtual instanceof VirtualArrayNode) { + store = new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, i); + fieldKind = ((VirtualArrayNode) virtual).componentType().kind(); + } else { + VirtualInstanceNode instanceObject = (VirtualInstanceNode) virtual; + store = new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, instanceObject.field(i)); + fieldKind = instanceObject.field(i).type().kind(); + } + deferredStores.addFixedNodeBefore(store, fixed); + values[i] = ConstantNode.defaultForKind(fieldKind, graph); + } else { + values[i] = valueObj.materializedValue; + } + } else { + values[i] = fieldState[i]; + } + } + deferred.remove(virtual); + + materializeEffects.addMaterialization(materialize, fixed, values); + } + + private void addAndMarkAlias(VirtualObjectNode virtual, ValueNode node) { + objectAliases.put(node, virtual); + for (Node usage : node.usages()) { + markVirtualUsages(usage); + } + } + + private void markVirtualUsages(Node node) { + if (!usages.isNew(node)) { + usages.mark(node); + } + if (node instanceof VirtualState) { + for (Node usage : node.usages()) { + markVirtualUsages(usage); + } + } + } + + public void addObject(VirtualObjectNode virtual, ObjectState state) { + objectStates.put(virtual, state); + } + + public void addScalarAlias(ValueNode alias, ValueNode value) { + scalarAliases.put(alias, value); + } + + public ValueNode scalarAlias(ValueNode alias) { + ValueNode result = scalarAliases.get(alias); + return result == null ? alias : result; + } + + public Iterable<ObjectState> states() { + return objectStates.values(); + } + + @Override + public String toString() { + return objectStates.toString(); + } + } + + private class PartialEscapeClosure extends BlockIteratorClosure<BlockState> { + + private final GraphEffectList effects = new GraphEffectList(); + + @Override + protected void processBlock(Block block, BlockState state) { + trace("\nBlock: %s (", block); + List<ScheduledNode> nodeList = schedule.getBlockToNodesMap().get(block); + + FixedWithNextNode lastFixedNode = null; + for (Node node : nodeList) { + EscapeOp op = null; + if (node instanceof EscapeAnalyzable) { + op = ((EscapeAnalyzable) node).getEscapeOp(); + } + // if (node instanceof NewInstanceNode) { + // if (!((NewInstanceNode) node).instanceClass().name().contains("Key")) { + // op = null; + // } + // } else { + // op = null; + // } + + if (op != null) { + trace("{{%s}} ", node); + VirtualObjectNode virtualObject = op.virtualObject(virtualIds); + if (virtualObject.isAlive()) { + reusedVirtualObjects.add(virtualObject); + state.addAndMarkAlias(virtualObject, virtualObject); + } else { + effects.addFloatingNode(virtualObject); + } + state.addObject(virtualObject, new ObjectState(virtualObject, op.fieldState(), 0)); + state.addAndMarkAlias(virtualObject, (ValueNode) node); + effects.deleteFixedNode((FixedWithNextNode) node); + virtualIds++; + } else { + if (usages.isMarked(node)) { + trace("[[%s]] ", node); + processNode((ValueNode) node, lastFixedNode == null ? null : lastFixedNode.next(), state); + } else { + trace("%s ", node); + } + } + + if (node instanceof FixedWithNextNode && node.isAlive()) { + lastFixedNode = (FixedWithNextNode) node; + } + } + trace(")\n end state: %s\n", state); + } + + private void processNode(final ValueNode node, FixedNode insertBefore, final BlockState state) { + boolean usageFound = false; + if (node instanceof PiNode || node instanceof ValueProxyNode) { + ValueNode value = node instanceof PiNode ? ((PiNode) node).object() : ((ValueProxyNode) node).value(); + ObjectState obj = state.objectState(value); + if (obj != null) { + if (obj.materializedValue == null) { + state.addAndMarkAlias(obj.virtual, node); + } else { + effects.replaceFirstInput(node, value, obj.materializedValue); + } + usageFound = true; + } + } else if (node instanceof CheckCastNode) { + CheckCastNode x = (CheckCastNode) node; + ObjectState obj = state.objectState(x.object()); + if (obj != null) { + if (obj.materializedValue == null) { + if (x.targetClass() != null && obj.virtual.type().isSubtypeOf(x.targetClass())) { + state.addAndMarkAlias(obj.virtual, x); + effects.deleteFixedNode(x); + } else { + replaceWithMaterialized(x.object(), x, state, obj); + } + } else { + effects.replaceFirstInput(x, x.object(), obj.materializedValue); + } + usageFound = true; + } + } else if (node instanceof IsNullNode) { + IsNullNode x = (IsNullNode) node; + if (state.objectState(x.object()) != null) { + replaceAtUsages(state, x, graph.unique(ConstantNode.forBoolean(false, graph))); + usageFound = true; + } + } else if (node instanceof AccessMonitorNode) { + AccessMonitorNode x = (AccessMonitorNode) node; + ObjectState obj = state.objectState(x.object()); + if (obj != null) { + Debug.log("monitor operation %s on %s\n", x, obj.virtual); + if (node instanceof MonitorEnterNode) { + obj.lockCount++; + } else { + assert node instanceof MonitorExitNode; + obj.lockCount--; + } + if (obj.materializedValue == null) { + effects.replaceFirstInput(node, x.object(), obj.virtual); + effects.eliminateMonitor(x); + } else { + effects.replaceFirstInput(node, x.object(), obj.materializedValue); + } + usageFound = true; + } + } else if (node instanceof CyclicMaterializeStoreNode) { + CyclicMaterializeStoreNode x = (CyclicMaterializeStoreNode) node; + ObjectState obj = state.objectState(x.object()); + if (obj != null) { + if (obj.virtual instanceof VirtualArrayNode) { + obj.fieldState[x.targetIndex()] = x.value(); + } else { + VirtualInstanceNode instance = (VirtualInstanceNode) obj.virtual; + int index = instance.fieldIndex(x.targetField()); + obj.fieldState[index] = x.value(); + } + effects.deleteFixedNode(x); + usageFound = true; + } + } else if (node instanceof LoadFieldNode) { + LoadFieldNode x = (LoadFieldNode) node; + ObjectState obj = state.objectState(x.object()); + if (obj != null) { + VirtualInstanceNode virtual = (VirtualInstanceNode) obj.virtual; + int fieldIndex = virtual.fieldIndex(x.field()); + if (fieldIndex == -1) { + // the field does not exist in the virtual object + ensureMaterialized(state, obj, x); + } + if (obj.materializedValue == null) { + ValueNode result = obj.fieldState[fieldIndex]; + ObjectState resultObj = state.objectState(result); + if (resultObj != null) { + state.addAndMarkAlias(resultObj.virtual, x); + } else { + replaceAtUsages(state, x, result); + } + effects.deleteFixedNode(x); + } else { + effects.replaceFirstInput(x, x.object(), obj.materializedValue); + } + usageFound = true; + } + } else if (node instanceof StoreFieldNode) { + StoreFieldNode x = (StoreFieldNode) node; + ValueNode object = x.object(); + ValueNode value = x.value(); + ObjectState obj = state.objectState(object); + if (obj != null) { + VirtualInstanceNode virtual = (VirtualInstanceNode) obj.virtual; + int fieldIndex = virtual.fieldIndex(x.field()); + if (fieldIndex == -1) { + // the field does not exist in the virtual object + ensureMaterialized(state, obj, x); + } + if (obj.materializedValue == null) { + obj.fieldState[fieldIndex] = state.scalarAlias(value); + effects.deleteFixedNode(x); + } else { + effects.replaceFirstInput(x, object, obj.materializedValue); + ObjectState valueObj = state.objectState(value); + if (valueObj != null) { + replaceWithMaterialized(value, x, state, valueObj); + } + } + usageFound = true; + } else { + ObjectState valueObj = state.objectState(value); + if (valueObj != null) { + replaceWithMaterialized(value, x, state, valueObj); + usageFound = true; + } + } + } else if (node instanceof LoadIndexedNode) { + LoadIndexedNode x = (LoadIndexedNode) node; + ValueNode array = x.array(); + ObjectState arrayObj = state.objectState(array); + if (arrayObj != null) { + if (arrayObj.materializedValue == null) { + ValueNode indexValue = state.scalarAlias(x.index()); + int index = indexValue.isConstant() ? indexValue.asConstant().asInt() : -1; + if (index < 0 || index >= arrayObj.fieldState.length) { + // out of bounds or not constant + replaceWithMaterialized(array, x, state, arrayObj); + } else { + ValueNode result = arrayObj.fieldState[index]; + ObjectState resultObj = state.objectState(result); + if (resultObj != null) { + state.addAndMarkAlias(resultObj.virtual, x); + } else { + replaceAtUsages(state, x, result); + } + effects.deleteFixedNode(x); + } + } else { + effects.replaceFirstInput(x, array, arrayObj.materializedValue); + } + usageFound = true; + } + } else if (node instanceof StoreIndexedNode) { + StoreIndexedNode x = (StoreIndexedNode) node; + ValueNode array = x.array(); + ValueNode value = x.value(); + ObjectState arrayObj = state.objectState(array); + ObjectState valueObj = state.objectState(value); + + if (arrayObj != null) { + if (arrayObj.materializedValue == null) { + ValueNode indexValue = state.scalarAlias(x.index()); + int index = indexValue.isConstant() ? indexValue.asConstant().asInt() : -1; + if (index < 0 || index >= arrayObj.fieldState.length) { + // out of bounds or not constant + replaceWithMaterialized(array, x, state, arrayObj); + if (valueObj != null) { + replaceWithMaterialized(value, x, state, valueObj); + } + } else { + arrayObj.fieldState[index] = state.scalarAlias(value); + effects.deleteFixedNode(x); + } + } else { + effects.replaceFirstInput(x, array, arrayObj.materializedValue); + if (valueObj != null) { + replaceWithMaterialized(value, x, state, valueObj); + } + } + usageFound = true; + } else { + if (valueObj != null) { + replaceWithMaterialized(value, x, state, valueObj); + usageFound = true; + } + } + } else if (node instanceof RegisterFinalizerNode) { + RegisterFinalizerNode x = (RegisterFinalizerNode) node; + ObjectState obj = state.objectState(x.object()); + if (obj != null) { + replaceWithMaterialized(x.object(), x, state, obj); + usageFound = true; + } + } else if (node instanceof ArrayLengthNode) { + ArrayLengthNode x = (ArrayLengthNode) node; + ObjectState obj = state.objectState(x.array()); + if (obj != null) { + replaceAtUsages(state, x, ConstantNode.forInt(((VirtualArrayNode) obj.virtual).entryCount(), graph)); + effects.deleteFixedNode(x); + usageFound = true; + } + } else if (node instanceof LoadHubNode) { + LoadHubNode x = (LoadHubNode) node; + ObjectState obj = state.objectState(x.object()); + if (obj != null) { + replaceAtUsages(state, x, ConstantNode.forConstant(obj.virtual.type().getEncoding(Representation.ObjectHub), runtime, graph)); + effects.deleteFixedNode(x); + usageFound = true; + } + } else if (node instanceof ReturnNode) { + ReturnNode x = (ReturnNode) node; + ObjectState obj = state.objectState(x.result()); + if (obj != null) { + replaceWithMaterialized(x.result(), x, state, obj); + usageFound = true; + } + } else if (node instanceof MethodCallTargetNode) { + for (ValueNode argument : ((MethodCallTargetNode) node).arguments()) { + ObjectState obj = state.objectState(argument); + if (obj != null) { + replaceWithMaterialized(argument, node, insertBefore, state, obj); + usageFound = true; + } + } + } else if (node instanceof ObjectEqualsNode) { + ObjectEqualsNode x = (ObjectEqualsNode) node; + ObjectState xObj = state.objectState(x.x()); + ObjectState yObj = state.objectState(x.y()); + boolean xVirtual = xObj != null && xObj.materializedValue == null; + boolean yVirtual = yObj != null && yObj.materializedValue == null; + + if (xVirtual ^ yVirtual) { + // one of them is virtual: they can never be the same objects + replaceAtUsages(state, x, ConstantNode.forBoolean(false, graph)); + usageFound = true; + } else if (xVirtual && yVirtual) { + // both are virtual: check if they refer to the same object + replaceAtUsages(state, x, ConstantNode.forBoolean(xObj == yObj, graph)); + usageFound = true; + } else { + if (xObj != null || yObj != null) { + if (xObj != null) { + assert xObj.materializedValue != null; + effects.replaceFirstInput(x, x.x(), xObj.materializedValue); + } + if (yObj != null) { + assert yObj.materializedValue != null; + effects.replaceFirstInput(x, x.y(), yObj.materializedValue); + } + usageFound = true; + } + } + } else if (node instanceof MergeNode) { + usageFound = true; + } else if (node instanceof UnsafeLoadNode || node instanceof UnsafeStoreNode || node instanceof CompareAndSwapNode || node instanceof SafeReadNode) { + for (ValueNode input : node.inputs().filter(ValueNode.class)) { + ObjectState obj = state.objectState(input); + if (obj != null) { + replaceWithMaterialized(input, node, insertBefore, state, obj); + usageFound = true; + } + } + } + if (node.isAlive() && node instanceof StateSplit) { + StateSplit split = (StateSplit) node; + FrameState stateAfter = split.stateAfter(); + if (stateAfter != null) { + if (stateAfter.usages().size() > 1) { + stateAfter = (FrameState) stateAfter.copyWithInputs(); + split.setStateAfter(stateAfter); + } + final HashSet<ObjectState> virtual = new HashSet<>(); + stateAfter.applyToNonVirtual(new NodeClosure<ValueNode>() { + + @Override + public void apply(Node usage, ValueNode value) { + ObjectState valueObj = state.objectState(value); + if (valueObj != null) { + virtual.add(valueObj); + effects.replaceFirstInput(usage, value, valueObj.virtual); + } else if (value instanceof VirtualObjectNode) { + ObjectState virtualObj = null; + for (ObjectState obj : state.states()) { + if (value == obj.virtual) { + virtualObj = obj; + break; + } + } + if (virtualObj != null) { + virtual.add(virtualObj); + } + } + } + }); + for (ObjectState obj : state.states()) { + if (obj.materializedValue == null && obj.lockCount > 0) { + virtual.add(obj); + } + } + + ArrayDeque<ObjectState> queue = new ArrayDeque<>(virtual); + while (!queue.isEmpty()) { + ObjectState obj = queue.removeLast(); + if (obj.materializedValue == null) { + for (ValueNode field : obj.fieldState) { + ObjectState fieldObj = state.objectState(field); + if (fieldObj != null) { + if (fieldObj.materializedValue == null && !virtual.contains(fieldObj)) { + virtual.add(fieldObj); + queue.addLast(fieldObj); + } + } + } + } + } + for (ObjectState obj : virtual) { + EscapeObjectState v; + if (obj.materializedValue == null) { + ValueNode[] fieldState = obj.fieldState.clone(); + for (int i = 0; i < fieldState.length; i++) { + ObjectState valueObj = state.objectState(fieldState[i]); + if (valueObj != null) { + if (valueObj.materializedValue == null) { + fieldState[i] = valueObj.virtual; + } else { + fieldState[i] = valueObj.materializedValue; + } + } + } + v = new VirtualObjectState(obj.virtual, fieldState); + } else { + v = new MaterializedObjectState(obj.virtual, obj.materializedValue); + } + effects.addVirtualMapping(stateAfter, v, reusedVirtualObjects); + } + } + usageFound = true; + } + if (!usageFound) { + for (ValueNode input : node.inputs().filter(ValueNode.class)) { + ObjectState obj = state.objectState(input); + if (obj != null) { + replaceWithMaterialized(input, node, insertBefore, state, obj); + usageFound = true; + } + } + Debug.log("unexpected usage of %s: %s\n", node, node.inputs().snapshot()); + } + } + + private void replaceAtUsages(final BlockState state, ValueNode x, ValueNode value) { + effects.replaceAtUsages(x, value); + state.addScalarAlias(x, value); + } + + private void ensureMaterialized(BlockState state, ObjectState obj, FixedNode materializeBefore) { + assert obj != null; + if (obj.materializedValue == null) { + state.materializeBefore(materializeBefore, obj.virtual, effects); + } + assert obj.materializedValue != null; + } + + private void replaceWithMaterialized(ValueNode value, FixedNode usage, BlockState state, ObjectState obj) { + ensureMaterialized(state, obj, usage); + effects.replaceFirstInput(usage, value, obj.materializedValue); + } + + private void replaceWithMaterialized(ValueNode value, Node usage, FixedNode materializeBefore, BlockState state, ObjectState obj) { + ensureMaterialized(state, obj, materializeBefore); + effects.replaceFirstInput(usage, value, obj.materializedValue); + } + + @Override + protected BlockState merge(MergeNode merge, List<BlockState> states) { + BlockState newState = new BlockState(); + + newState.objectAliases.putAll(states.get(0).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()) { + if (state.objectAliases.containsKey(entry.getKey())) { + assert state.objectAliases.get(entry.getKey()) == entry.getValue(); + } else { + newState.objectAliases.remove(entry.getKey()); + } + } + } + + newState.scalarAliases.putAll(states.get(0).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()) { + if (state.scalarAliases.containsKey(entry.getKey())) { + assert state.scalarAliases.get(entry.getKey()) == entry.getValue(); + } else { + newState.scalarAliases.remove(entry.getKey()); + } + } + } + + // Iterative processing: + // Merging the materialized/virtual state of virtual objects can lead to new materializations, which can + // lead to new materializations because of phis, and so on. + + boolean materialized; + do { + materialized = false; + // use a hash set to make the values distinct... + for (VirtualObjectNode object : new HashSet<>(newState.objectAliases.values())) { + ObjectState resultState = newState.objectStates.get(object); + if (resultState == null || resultState.materializedValue == null) { + int virtual = 0; + int lockCount = states.get(0).objectState(object).lockCount; + ValueNode singleValue = states.get(0).objectState(object).materializedValue; + for (BlockState state : states) { + ObjectState obj = state.objectState(object); + if (obj.materializedValue == null) { + virtual++; + singleValue = null; + } else { + if (obj.materializedValue != singleValue) { + singleValue = null; + } + } + assert obj.lockCount == lockCount : "mismatching lock counts"; + } + + if (virtual < states.size()) { + if (singleValue == null) { + PhiNode materializedValuePhi = new PhiNode(Kind.Object, merge); + effects.addFloatingNode(materializedValuePhi); + for (int i = 0; i < states.size(); i++) { + BlockState state = states.get(i); + ObjectState obj = state.objectState(object); + materialized |= obj.materializedValue == null; + ensureMaterialized(state, obj, merge.forwardEndAt(i)); + effects.addPhiInput(materializedValuePhi, obj.materializedValue); + } + newState.addObject(object, new ObjectState(object, materializedValuePhi, lockCount)); + } else { + newState.addObject(object, new ObjectState(object, singleValue, lockCount)); + } + } else { + assert virtual == states.size(); + ValueNode[] values = states.get(0).objectState(object).fieldState.clone(); + PhiNode[] phis = new PhiNode[values.length]; + int mismatch = 0; + for (int i = 1; i < states.size(); i++) { + BlockState state = states.get(i); + ValueNode[] fields = state.objectState(object).fieldState; + for (int index = 0; index < values.length; index++) { + if (phis[index] == null && values[index] != fields[index]) { + mismatch++; + phis[index] = new PhiNode(values[index].kind(), merge); + effects.addFloatingNode(phis[index]); + } + } + } + if (mismatch > 0) { + for (int i = 0; i < states.size(); i++) { + BlockState state = states.get(i); + ValueNode[] fields = state.objectState(object).fieldState; + for (int index = 0; index < values.length; index++) { + if (phis[index] != null) { + ObjectState obj = state.objectState(fields[index]); + if (obj != null) { + materialized |= obj.materializedValue == null; + ensureMaterialized(state, obj, merge.forwardEndAt(i)); + fields[index] = obj.materializedValue; + } + effects.addPhiInput(phis[index], fields[index]); + } + } + } + for (int index = 0; index < values.length; index++) { + if (phis[index] != null) { + values[index] = phis[index]; + } + } + } + newState.addObject(object, new ObjectState(object, values, lockCount)); + } + } + } + + for (PhiNode phi : merge.phis().snapshot()) { + if (usages.isMarked(phi) && phi.type() == PhiType.Value) { + materialized |= processPhi(newState, merge, phi, states); + } + } + } while (materialized); + + return newState; + } + + private boolean processPhi(BlockState newState, MergeNode merge, PhiNode phi, List<BlockState> states) { + assert states.size() == phi.valueCount(); + int virtualInputs = 0; + boolean materialized = false; + VirtualObjectNode sameObject = null; + ResolvedJavaType sameType = null; + int sameEntryCount = -1; + for (int i = 0; i < phi.valueCount(); i++) { + ValueNode value = phi.valueAt(i); + ObjectState obj = states.get(i).objectState(value); + if (obj != null) { + if (obj.materializedValue == null) { + virtualInputs++; + if (i == 0) { + sameObject = obj.virtual; + sameType = obj.virtual.type(); + sameEntryCount = obj.virtual.entryCount(); + } else { + if (sameObject != obj.virtual) { + sameObject = null; + } + if (sameType != obj.virtual.type()) { + sameType = null; + } + if (sameEntryCount != obj.virtual.entryCount()) { + sameEntryCount = -1; + } + } + } else { + effects.setPhiInput(phi, obj.materializedValue, i); + } + } + } + boolean materialize = false; + if (virtualInputs == 0) { + // nothing to do... + } else if (virtualInputs == phi.valueCount()) { + if (sameObject != null) { + newState.addAndMarkAlias(sameObject, phi); + } else if (sameType != null && sameEntryCount != -1) { + materialize = true; + // throw new GraalInternalError("merge required for %s", sameType); + } else { + materialize = true; + } + } else { + materialize = true; + } + + if (materialize) { + for (int i = 0; i < phi.valueCount(); i++) { + ValueNode value = phi.valueAt(i); + ObjectState obj = states.get(i).objectState(value); + if (obj != null) { + materialized |= obj.materializedValue == null; + replaceWithMaterialized(value, phi, merge.forwardEndAt(i), states.get(i), obj); + } + } + } + return materialized; + } + + @Override + protected BlockState afterSplit(FixedNode node, BlockState oldState) { + return oldState.clone(); + } + + @Override + protected List<BlockState> processLoop(Loop loop, BlockState initialState) { + GraphEffectList successEffects = new GraphEffectList(); + HashSet<PhiDesc> phis = new HashSet<>(); + for (int iteration = 0; iteration < 10; iteration++) { + BlockState state = initialState.clone(); + int checkpoint = effects.checkpoint(); + + for (PhiDesc desc : phis) { + ObjectState obj = state.objectState(desc.virtualObject); + if (obj.materializedValue == null) { + ValueNode value = obj.fieldState[desc.fieldIndex]; + ObjectState valueObj = state.objectState(value); + if (valueObj != null) { + assert valueObj.materializedValue != null; + value = valueObj.materializedValue; + } + + PhiNode phiNode = new PhiNode(value.kind(), loop.loopBegin()); + effects.addFloatingNode(phiNode); + effects.addPhiInput(phiNode, value); + obj.fieldState[desc.fieldIndex] = phiNode; + } + } + + for (PhiNode phi : loop.loopBegin().phis()) { + if (usages.isMarked(phi) && phi.type() == PhiType.Value) { + ObjectState initialObj = initialState.objectState(phi.valueAt(0)); + if (initialObj != null) { + if (initialObj.materializedValue == null) { + state.addAndMarkAlias(initialObj.virtual, phi); + } else { + successEffects.setPhiInput(phi, initialObj.materializedValue, 0); + } + } + } + } + + effects.incLevel(); + LoopInfo<BlockState> info = ReentrantBlockIterator.processLoop(this, loop, state.clone()); + + List<BlockState> loopEndStates = info.endStates; + List<Block> predecessors = loop.header.getPredecessors(); + HashSet<VirtualObjectNode> additionalMaterializations = 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); + } + if (additionalMaterializations.isEmpty() && oldPhiCount == phis.size()) { + effects.addAll(successEffects); + + assert info.exitStates.size() == loop.exits.size(); + for (int i = 0; i < loop.exits.size(); i++) { + BlockState exitState = info.exitStates.get(i); + assert exitState != null : "no loop exit state at " + loop.exits.get(i) + " / " + loop.header; + processLoopExit((LoopExitNode) loop.exits.get(i).getBeginNode(), state, exitState); + } + + effects.decLevel(); + return info.exitStates; + } else { + successEffects.clear(); + effects.backtrack(checkpoint); + effects.decLevel(); + for (VirtualObjectNode virtualObject : additionalMaterializations) { + ObjectState obj = initialState.objectState(virtualObject); + if (obj.materializedValue == null) { + initialState.materializeBefore(loop.loopBegin().forwardEnd(), virtualObject, effects); + } + } + } + } + + throw new GraalInternalError("too many iterations at %s", loop); + } + + private void processLoopExit(LoopExitNode exitNode, BlockState initialState, BlockState exitState) { + HashMap<VirtualObjectNode, ValueProxyNode> proxies = new HashMap<>(); + + for (ValueProxyNode proxy : exitNode.proxies()) { + ObjectState obj = exitState.objectState(proxy.value()); + if (obj != null) { + proxies.put(obj.virtual, proxy); + } + } + for (ObjectState obj : exitState.states()) { + ObjectState initialObj = initialState.objectStateOptional(obj.virtual); + if (obj.materializedValue == null) { + for (int i = 0; i < obj.fieldState.length; i++) { + ValueNode value = obj.fieldState[i]; + ObjectState valueObj = exitState.objectState(value); + if (valueObj == null) { + if ((value instanceof PhiNode && ((PhiNode) value).merge() == exitNode.loopBegin()) || initialObj == null || initialObj.materializedValue != null || + initialObj.fieldState[i] != value) { + ValueProxyNode proxy = new ValueProxyNode(value, exitNode, PhiType.Value); + obj.fieldState[i] = proxy; + effects.addFloatingNode(proxy); + } + } + } + } else { + if (initialObj == null || initialObj.materializedValue == null) { + ValueProxyNode proxy = proxies.get(obj.virtual); + if (proxy == null) { + proxy = new ValueProxyNode(obj.materializedValue, exitNode, PhiType.Value); + effects.addFloatingNode(proxy); + } else { + effects.replaceFirstInput(proxy, proxy.value(), obj.materializedValue); + // nothing to do - will be handled in processNode + } + obj.materializedValue = proxy; + } else { + assert initialObj.materializedValue == obj.materializedValue : "materialized value is not allowed to change within loops: " + initialObj.materializedValue + " vs. " + + obj.materializedValue; + } + } + } + } + + private final class PhiDesc { + + public final VirtualObjectNode virtualObject; + public final int fieldIndex; + + public PhiDesc(VirtualObjectNode virtualObject, int fieldIndex) { + this.virtualObject = virtualObject; + this.fieldIndex = fieldIndex; + } + + @Override + public int hashCode() { + final int prime = 31; + int result = fieldIndex; + result = prime * result + ((virtualObject == null) ? 0 : virtualObject.hashCode()); + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj == null || getClass() != obj.getClass()) { + return false; + } + PhiDesc other = (PhiDesc) obj; + return virtualObject == other.virtualObject && fieldIndex == other.fieldIndex; + } + } + + private void processLoopEnd(LoopBeginNode loopBegin, LoopEndNode loopEnd, BlockState initialState, BlockState loopEndState, GraphEffectList successEffects, + Set<VirtualObjectNode> additionalMaterializations, HashSet<PhiDesc> phis) { + assert loopEnd.loopBegin() == loopBegin; + boolean materialized; + do { + materialized = false; + for (ObjectState state : initialState.states()) { + ObjectState endState = loopEndState.objectState(state.virtual); + if (state.materializedValue == null) { + if (endState.materializedValue == null) { + assert state.fieldState.length == endState.fieldState.length; + for (int i = 0; endState.fieldState != null && i < state.fieldState.length; i++) { + ValueNode value = state.fieldState[i]; + ValueNode endValue = endState.fieldState[i]; + ObjectState valueObj = initialState.objectState(value); + ObjectState endValueObj = loopEndState.objectState(endValue); + + if (valueObj != null) { + if (valueObj.materializedValue == null) { + if (endValueObj == null || endValueObj.materializedValue != null || valueObj.virtual != endValueObj.virtual) { + additionalMaterializations.add(valueObj.virtual); + } else { + // endValue is also virtual and refers to the same virtual object, so we're + // good. + } + } + } else { + if (value instanceof PhiNode && ((PhiNode) value).merge() == loopBegin) { + if (endValueObj != null) { + if (endValueObj.materializedValue == null) { + loopEndState.materializeBefore(loopEnd, endValueObj.virtual, successEffects); + materialized = true; + } + } + } + } + } + } else { + additionalMaterializations.add(state.virtual); + } + } + } + for (PhiNode phi : loopBegin.phis().snapshot()) { + if (usages.isMarked(phi) && phi.type() == PhiType.Value) { + ObjectState initialObj = initialState.objectState(phi.valueAt(0)); + boolean initialMaterialized = initialObj == null || initialObj.materializedValue != null; + + ObjectState loopEndObj = loopEndState.objectState(phi.valueAt(loopEnd)); + if (loopEndObj == null || loopEndObj.materializedValue != null) { + if (loopEndObj != null) { + successEffects.setPhiInput(phi, loopEndObj.materializedValue, loopBegin.phiPredecessorIndex(loopEnd)); + } + if (!initialMaterialized) { + additionalMaterializations.add(initialObj.virtual); + } + } else { + if (initialMaterialized) { + loopEndState.materializeBefore(loopEnd, loopEndObj.virtual, successEffects); + materialized = true; + } else { + if (loopEndObj.virtual != initialObj.virtual) { + additionalMaterializations.add(initialObj.virtual); + } + } + } + } + } + } while (materialized); + + for (ObjectState state : initialState.states()) { + ObjectState endState = loopEndState.objectState(state.virtual); + if (state.materializedValue == null) { + if (endState.materializedValue == null) { + assert state.fieldState.length == endState.fieldState.length; + for (int i = 0; i < state.fieldState.length; i++) { + ValueNode value = state.fieldState[i]; + ValueNode endValue = endState.fieldState[i]; + ObjectState valueObj = initialState.objectState(value); + ObjectState endValueObj = loopEndState.objectState(endValue); + + if (valueObj != null) { + if (valueObj.materializedValue == null) { + if (endValueObj == null || endValueObj.materializedValue != null || valueObj.virtual != endValueObj.virtual) { + assert !additionalMaterializations.isEmpty(); + } else { + // endValue is also virtual and refers to the same virtual object, so we're + // good. + } + } else { + if ((endValueObj != null && endValueObj.materializedValue != valueObj.materializedValue) || (endValueObj == null && valueObj.materializedValue != endValue)) { + phis.add(new PhiDesc(state.virtual, i)); + } else { + // either endValue has the same materialized value as value or endValue is the + // same as the materialized value, so we're good. + } + } + } else { + if (value instanceof PhiNode && ((PhiNode) value).merge() == loopBegin) { + if (endValueObj != null) { + if (endValueObj.materializedValue == null) { + assert !additionalMaterializations.isEmpty(); + } + successEffects.addPhiInput((PhiNode) value, endValueObj.materializedValue); + } else { + successEffects.addPhiInput((PhiNode) value, endValue); + } + } else if (value != endValue) { + phis.add(new PhiDesc(state.virtual, i)); + } + } + } + } else { + // endState.materializedValue != null + assert !additionalMaterializations.isEmpty(); + } + } else { + // state.materializedValue != null + if (endState.materializedValue == null) { + // throw new GraalInternalError("un-materialized object state at %s", loopEnd); + } else { + if (state.materializedValue != endState.materializedValue) { + // throw new GraalInternalError("changed materialized value during loop: %s vs %s", + // state.materializedValue, endState.materializedValue); + } + } + } + } + } + } +} + +public class SplitPartialEscapeAnalysisPhase extends Phase { + + private final GraalCodeCacheProvider runtime; + + public SplitPartialEscapeAnalysisPhase(GraalCodeCacheProvider runtime) { + this.runtime = runtime; + } + + @Override + protected void run(StructuredGraph graph) { + SchedulePhase schedule = new SchedulePhase(); + schedule.apply(graph, false); + new EscapeAnalysisIteration(graph, schedule, runtime).run(); + } +}