# HG changeset patch # User Doug Simon # Date 1351637999 -3600 # Node ID 7e371de0de7de790e85ec621a77f260e50caf08a # Parent 2d5407ae1ac439b4286d2cb14f4c4ed4d64d641e# Parent c162fcf45ce79588e9f18efb7b65aaf09460d3a0 Merge. diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/CodeCacheProvider.java --- a/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/CodeCacheProvider.java Tue Oct 30 23:58:53 2012 +0100 +++ b/graal/com.oracle.graal.api.code/src/com/oracle/graal/api/code/CodeCacheProvider.java Tue Oct 30 23:59:59 2012 +0100 @@ -70,12 +70,6 @@ int getCustomStackAreaSize(); /** - * Determines if a call instruction in compiled code can assume all allocatable - * registers are killed by the call. - */ - boolean callKillsRegisters(); - - /** * Minimum size of the stack area reserved for outgoing parameters. This area is reserved in all cases, even when * the compiled method has no regular call instructions. * diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Tue Oct 30 23:58:53 2012 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Tue Oct 30 23:59:59 2012 +0100 @@ -171,7 +171,7 @@ new InliningPhase(null, runtime(), null, null, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph); new DeadCodeEliminationPhase().apply(graph); Debug.dump(graph, "Graph"); - new PartialEscapeAnalysisPhase(null, runtime(), null).apply(graph); + new PartialEscapeAnalysisPhase(null).apply(graph); new CullFrameStatesPhase().apply(graph); new CanonicalizerPhase(null, runtime(), null).apply(graph); Debug.dump(graph, "Graph"); diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java --- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Tue Oct 30 23:58:53 2012 +0100 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Tue Oct 30 23:59:59 2012 +0100 @@ -157,7 +157,7 @@ new DeadCodeEliminationPhase().apply(graph); new CanonicalizerPhase(null, runtime(), null).apply(graph); // TypeSystemTest.outputGraph(graph, "before EscapeAnalysis " + snippet); - new PartialEscapeAnalysisPhase(null, runtime(), null).apply(graph); + new PartialEscapeAnalysisPhase(null).apply(graph); // TypeSystemTest.outputGraph(graph, "after EscapeAnalysis " + snippet); new CullFrameStatesPhase().apply(graph); new DeadCodeEliminationPhase().apply(graph); diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Oct 30 23:58:53 2012 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Oct 30 23:59:59 2012 +0100 @@ -40,11 +40,10 @@ import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; -import com.oracle.graal.phases.PhasePlan.*; +import com.oracle.graal.phases.PhasePlan.PhasePosition; import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.schedule.*; import com.oracle.graal.virtual.phases.ea.*; -import com.oracle.graal.virtual.phases.ea.experimental.*; public class GraalCompiler { @@ -157,7 +156,7 @@ } if (GraalOptions.PartialEscapeAnalysis && !plan.isPhaseDisabled(PartialEscapeAnalysisPhase.class)) { - new SplitPartialEscapeAnalysisPhase(runtime).apply(graph); + new PartialEscapeAnalysisPhase(runtime).apply(graph); } if (GraalOptions.OptLoopTransform) { new LoopTransformHighPhase().apply(graph); diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java Tue Oct 30 23:58:53 2012 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/LinearScanWalker.java Tue Oct 30 23:59:59 2012 +0100 @@ -29,7 +29,7 @@ import java.util.*; import com.oracle.graal.api.code.*; -import com.oracle.graal.api.code.Register.*; +import com.oracle.graal.api.code.Register.RegisterFlag; import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.alloc.Interval.RegisterBinding; import com.oracle.graal.compiler.alloc.Interval.RegisterPriority; @@ -37,7 +37,7 @@ import com.oracle.graal.compiler.alloc.Interval.State; import com.oracle.graal.debug.*; import com.oracle.graal.lir.*; -import com.oracle.graal.lir.StandardOp.*; +import com.oracle.graal.lir.StandardOp.MoveOp; import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.util.*; @@ -73,7 +73,13 @@ LinearScanWalker(LinearScan allocator, Interval unhandledFixedFirst, Interval unhandledAnyFirst) { super(allocator, unhandledFixedFirst, unhandledAnyFirst); - this.callKillsRegisters = allocator.frameMap.runtime.callKillsRegisters(); + + // If all allocatable registers are caller saved, then no registers are live across a call site. + // The register allocator can save time not trying to find a register at a call site. + HashSet registers = new HashSet<>(Arrays.asList(allocator.frameMap.registerConfig.getAllocatableRegisters())); + registers.removeAll(Arrays.asList(allocator.frameMap.registerConfig.getCallerSaveRegisters())); + callKillsRegisters = registers.size() == 0; + moveResolver = new MoveResolver(allocator); spillIntervals = Util.uncheckedCast(new List[allocator.registers.length]); for (int i = 0; i < allocator.registers.length; i++) { diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.hotspot.amd64/src/com/oracle/graal/hotspot/amd64/AMD64HotSpotRuntime.java --- a/graal/com.oracle.graal.hotspot.amd64/src/com/oracle/graal/hotspot/amd64/AMD64HotSpotRuntime.java Tue Oct 30 23:58:53 2012 +0100 +++ b/graal/com.oracle.graal.hotspot.amd64/src/com/oracle/graal/hotspot/amd64/AMD64HotSpotRuntime.java Tue Oct 30 23:59:59 2012 +0100 @@ -123,11 +123,6 @@ } @Override - public boolean callKillsRegisters() { - return true; - } - - @Override public Register threadRegister() { return r15; } diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ReentrantBlockIterator.java Tue Oct 30 23:59:59 2012 +0100 @@ -0,0 +1,185 @@ +/* + * 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.phases.graph; + +import java.util.*; + +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; + +public final class ReentrantBlockIterator { + + public abstract static class MergeableBlockState { + + public abstract T cloneState(); + } + + public static class LoopInfo> { + + public final List endStates = new ArrayList<>(); + public final List exitStates = new ArrayList<>(); + } + + public abstract static class BlockIteratorClosure> { + + protected abstract void processBlock(Block block, T currentState); + + protected abstract T merge(MergeNode merge, List states); + + protected abstract T afterSplit(FixedNode node, T oldState); + + protected abstract List processLoop(Loop loop, T initialState); + } + + private ReentrantBlockIterator() { + // no instances allowed + } + + public static > LoopInfo processLoop(BlockIteratorClosure closure, Loop loop, T initialState) { + IdentityHashMap blockEndStates = apply(closure, loop.header, initialState, new HashSet<>(loop.blocks)); + + LoopInfo info = new LoopInfo<>(); + List 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 > IdentityHashMap apply(BlockIteratorClosure closure, Block start, T initialState, Set boundary) { + Deque blockQueue = new ArrayDeque<>(); + IdentityHashMap 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 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 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; + } +} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Tue Oct 30 23:59:59 2012 +0100 @@ -0,0 +1,168 @@ +/* + * 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 static com.oracle.graal.virtual.phases.ea.PartialEscapeAnalysisPhase.*; + +import java.util.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.virtual.*; +import com.oracle.graal.phases.graph.ReentrantBlockIterator.MergeableBlockState; +import com.oracle.graal.virtual.nodes.*; + +class BlockState extends MergeableBlockState { + + final HashMap objectStates = new HashMap<>(); + final HashMap objectAliases = new HashMap<>(); + final HashMap scalarAliases = new HashMap<>(); + + public BlockState() { + } + + public BlockState(BlockState other) { + for (Map.Entry entry : other.objectStates.entrySet()) { + objectStates.put(entry.getKey(), entry.getValue().clone()); + } + for (Map.Entry entry : other.objectAliases.entrySet()) { + objectAliases.put(entry.getKey(), entry.getValue()); + } + for (Map.Entry 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 cloneState() { + return new BlockState(this); + } + + public void materializeBefore(FixedNode fixed, VirtualObjectNode virtual, GraphEffectList materializeEffects) { + HashSet deferred = new HashSet<>(); + GraphEffectList deferredStores = new GraphEffectList(); + materializeChangedBefore(fixed, virtual, deferred, deferredStores, materializeEffects); + materializeEffects.addAll(deferredStores); + } + + private void materializeChangedBefore(FixedNode fixed, VirtualObjectNode virtual, HashSet deferred, GraphEffectList deferredStores, GraphEffectList materializeEffects) { + trace("materializing %s at %s", virtual, fixed); + ObjectState obj = objectState(virtual); + if (obj.lockCount > 0 && obj.virtual.type().isArrayClass()) { + 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().getKind(); + } else { + VirtualInstanceNode instanceObject = (VirtualInstanceNode) virtual; + store = new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, instanceObject.field(i)); + fieldKind = instanceObject.field(i).getType().getKind(); + } + deferredStores.addFixedNodeBefore(store, fixed); + values[i] = ConstantNode.defaultForKind(fieldKind, fixed.graph()); + } else { + values[i] = valueObj.materializedValue; + } + } else { + values[i] = fieldState[i]; + } + } + deferred.remove(virtual); + + materializeEffects.addMaterialization(materialize, fixed, values); + } + + void addAndMarkAlias(VirtualObjectNode virtual, ValueNode node, NodeBitMap usages) { + objectAliases.put(node, virtual); + for (Node usage : node.usages()) { + markVirtualUsages(usage, usages); + } + } + + private void markVirtualUsages(Node node, NodeBitMap usages) { + if (!usages.isNew(node)) { + usages.mark(node); + } + if (node instanceof VirtualState) { + for (Node usage : node.usages()) { + markVirtualUsages(usage, usages); + } + } + } + + 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 states() { + return objectStates.values(); + } + + @Override + public String toString() { + return objectStates.toString(); + } +} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/EffectList.java Tue Oct 30 23:59:59 2012 +0100 @@ -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; + +import java.lang.reflect.*; +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; + +public class EffectList implements Iterable { + + 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 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 iterator() { + return new Iterator() { + + 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; + } +} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java Tue Oct 30 23:59:59 2012 +0100 @@ -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; + +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 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 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 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 obsoleteNodes) { + assert node.isAlive() && value.isAlive(); + node.addInput(value); + } + }); + } + + public void addVirtualMapping(final FrameState node, final EscapeObjectState state, final HashSet reusedVirtualObjects) { + add(new Effect() { + + @Override + public String name() { + return "addVirtualMapping"; + } + + @Override + public void apply(StructuredGraph graph, ArrayList 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 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 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 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 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 obsoleteNodes) { + assert node.isAlive() && value.isAlive() && index >= 0; + node.setValueAt(index, value); + } + }); + } +} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/MergeableBlockState.java --- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/MergeableBlockState.java Tue Oct 30 23:58:53 2012 +0100 +++ /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.virtual.phases.ea; - - -public interface MergeableBlockState { - - T clone(); -} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java Tue Oct 30 23:59:59 2012 +0100 @@ -0,0 +1,76 @@ +/* + * 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 com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.virtual.*; + +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(); + } +} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java --- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Tue Oct 30 23:58:53 2012 +0100 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Tue Oct 30 23:59:59 2012 +0100 @@ -24,42 +24,17 @@ import java.util.*; -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.api.meta.ResolvedJavaType.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; 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.cfg.*; -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.phases.*; import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.schedule.*; -import com.oracle.graal.virtual.nodes.*; - -class EscapeAnalysisIteration { +import com.oracle.graal.virtual.phases.ea.EffectList.Effect; - // 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 class PartialEscapeAnalysisPhase extends Phase { public static final void trace(String format, Object... obj) { if (GraalOptions.TraceEscapeAnalysis) { @@ -71,1078 +46,107 @@ 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 GraalCodeCacheProvider runtime; - private final HashSet reusedVirtualObjects = new HashSet<>(); - private final HashSet allocations; - private final ArrayList obsoleteNodes = new ArrayList<>(); - private int virtualIds = 0; - - public EscapeAnalysisIteration(StructuredGraph graph, SchedulePhase schedule, MetaAccessProvider runtime, HashSet allocations, boolean changeGraph) { - this.graph = graph; - this.schedule = schedule; + public PartialEscapeAnalysisPhase(GraalCodeCacheProvider runtime) { 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 + protected void run(StructuredGraph graph) { + SchedulePhase schedule = new SchedulePhase(); + schedule.apply(graph, false); + PartialEscapeClosure closure = new PartialEscapeClosure(graph.createNodeBitMap(), schedule, runtime); + ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock(), new BlockState(), null); - @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(' '); + // apply the effects collected during the escape analysis iteration + ArrayList 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()); } } - if (materializedValue != null) { - str.append("mat=").append(materializedValue); - } - - return str.append('}').toString(); - } - } - - private class BlockState implements MergeableBlockState { - - private final HashMap objectStates = new HashMap<>(); - private final HashMap objectAliases = new HashMap<>(); - - public BlockState() { - } - - public BlockState(BlockState other) { - for (Map.Entry entry : other.objectStates.entrySet()) { - objectStates.put(entry.getKey(), entry.getValue().clone()); - } - for (Map.Entry entry : other.objectAliases.entrySet()) { - objectAliases.put(entry.getKey(), entry.getValue()); - } } + Debug.dump(graph, "after PartialEscapeAnalysis"); + assert noObsoleteNodes(graph, obsoleteNodes); - public ObjectState objectState(VirtualObjectNode object) { - assert objectStates.containsKey(object); - return objectStates.get(object); - } + new DeadCodeEliminationPhase().apply(graph); + } - public ObjectState objectState(ValueNode value) { - VirtualObjectNode object = objectAliases.get(value); - return object == null ? null : objectState(object); - } + private static boolean noObsoleteNodes(StructuredGraph graph, ArrayList obsoleteNodes) { + // helper code that determines the paths that keep obsolete nodes alive: - @Override - public BlockState clone() { - return new BlockState(this); - } - - public void materializeBefore(FixedNode fixed, VirtualObjectNode virtual) { - if (changeGraph) { - HashSet deferred = new HashSet<>(); - ArrayList deferredStores = new ArrayList<>(); - materializeChangedBefore(fixed, virtual, deferred, deferredStores); - for (FixedWithNextNode write : deferredStores) { - write.setProbability(fixed.probability()); - graph.addBeforeFixed(fixed, write); + NodeFlood flood = graph.createNodeFlood(); + IdentityHashMap 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 { - 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); + for (Node successor : current.successors()) { + flood.add(successor); + if (!path.containsKey(successor)) { + path.put(successor, current); } } } - obj.initialized = true; - } - - private void materializeChangedBefore(FixedNode fixed, VirtualObjectNode virtual, HashSet deferred, ArrayList 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().getKind(); - } else { - VirtualInstanceNode instanceObject = (VirtualInstanceNode) virtual; - deferredStores.add(graph.add(new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, instanceObject.field(i)))); - fieldKind = instanceObject.field(i).getType().getKind(); - } - 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 states() { - return objectStates.values(); - } - - @Override - public String toString() { - return objectStates.toString(); - } - } - - private class PartialEscapeIterator extends PostOrderBlockIterator { - - public PartialEscapeIterator(StructuredGraph graph, Block start) { - super(graph, start, new BlockState()); - } - - @Override - protected void processBlock(Block block, BlockState state) { - trace("\nBlock: %s (", block); - List 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; - } + for (Node node : obsoleteNodes) { + if (node instanceof FixedNode) { + assert !flood.isMarked(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 (obj.virtual.type().isSubtypeOf(x.type())) { - 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; + 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); } } } - 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 virtual = new HashSet<>(); - stateAfter.applyToNonVirtual(new NodeClosure() { - - @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 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; + } + for (Node current : flood) { + for (Node input : current.inputs()) { + flood.add(input); + if (!path.containsKey(input)) { + path.put(input, current); } } - 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 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 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 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 success = true; + 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; } } - } - 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; - } - } - } + success = false; } - 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 loopEndStates) { - BlockState state = loopBeginState.clone(); - List loopEnds = loopBegin.orderedLoopEnds(); - for (ObjectState obj : state.states()) { - if (obj.fieldState != null) { - Iterator 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(); - } + return success; } } - -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 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); - } - }); - } - } - } -} - diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Tue Oct 30 23:59:59 2012 +0100 @@ -0,0 +1,942 @@ +/* + * 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 static com.oracle.graal.virtual.phases.ea.PartialEscapeAnalysisPhase.*; + +import java.util.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.api.meta.ResolvedJavaType.Representation; +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +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.cfg.*; +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.phases.graph.*; +import com.oracle.graal.phases.graph.ReentrantBlockIterator.BlockIteratorClosure; +import com.oracle.graal.phases.graph.ReentrantBlockIterator.LoopInfo; +import com.oracle.graal.phases.schedule.*; +import com.oracle.graal.virtual.nodes.*; + +class PartialEscapeClosure extends BlockIteratorClosure { + + final GraphEffectList effects = new GraphEffectList(); + private final HashSet reusedVirtualObjects = new HashSet<>(); + private int virtualIds = 0; + + private final NodeBitMap usages; + private final SchedulePhase schedule; + private final MetaAccessProvider runtime; + + public PartialEscapeClosure(NodeBitMap usages, SchedulePhase schedule, MetaAccessProvider runtime) { + this.usages = usages; + this.schedule = schedule; + this.runtime = runtime; + } + + @Override + protected void processBlock(Block block, BlockState state) { + trace("\nBlock: %s (", block); + List 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) { + trace("{{%s}} ", node); + VirtualObjectNode virtualObject = op.virtualObject(virtualIds); + if (virtualObject.isAlive()) { + reusedVirtualObjects.add(virtualObject); + state.addAndMarkAlias(virtualObject, virtualObject, usages); + } else { + effects.addFloatingNode(virtualObject); + } + state.addObject(virtualObject, new ObjectState(virtualObject, op.fieldState(), 0)); + state.addAndMarkAlias(virtualObject, (ValueNode) node, usages); + 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, usages); + } 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 (obj.virtual.type().isSubtypeOf(x.type())) { + state.addAndMarkAlias(obj.virtual, x, usages); + 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, ConstantNode.forBoolean(false, node.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, usages); + } 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, usages); + } 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(), node.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, node.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, node.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, node.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 virtual = new HashSet<>(); + stateAfter.applyToNonVirtual(new NodeClosure() { + + @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 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 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 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 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 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, usages); + } 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.cloneState(); + } + + @Override + protected List processLoop(Loop loop, BlockState initialState) { + GraphEffectList successEffects = new GraphEffectList(); + HashSet phis = new HashSet<>(); + for (int iteration = 0; iteration < 10; iteration++) { + BlockState state = initialState.cloneState(); + 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, usages); + } else { + successEffects.setPhiInput(phi, initialObj.materializedValue, 0); + } + } + } + } + + effects.incLevel(); + LoopInfo info = ReentrantBlockIterator.processLoop(this, loop, state.cloneState()); + + List loopEndStates = info.endStates; + List predecessors = loop.header.getPredecessors(); + HashSet 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 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 additionalMaterializations, HashSet 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); + } + } + } + } + } +} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PostOrderBlockIterator.java --- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PostOrderBlockIterator.java Tue Oct 30 23:58:53 2012 +0100 +++ /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.virtual.phases.ea; - -import java.util.*; - -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.cfg.*; - -public abstract class PostOrderBlockIterator> { - - private final NodeBitMap visitedEnds; - private final Deque blockQueue; - private final IdentityHashMap blockEndStates; - private final IdentityHashMap 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 states); - - protected abstract T loopBegin(LoopBeginNode loopBegin, T beforeLoopState); - - protected abstract T loopEnds(LoopBeginNode loopBegin, T loopBeginState, List 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 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 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); - } - } - } -} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/BlockIteratorClosure.java --- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/BlockIteratorClosure.java Tue Oct 30 23:58:53 2012 +0100 +++ /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.virtual.phases.ea.experimental; - -import java.util.*; - -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.cfg.*; -import com.oracle.graal.virtual.phases.ea.*; - -public abstract class BlockIteratorClosure> { - - public static class LoopInfo> { - - public final List endStates = new ArrayList<>(); - public final List exitStates = new ArrayList<>(); - } - - protected abstract void processBlock(Block block, T currentState); - - protected abstract T merge(MergeNode merge, List states); - - protected abstract T afterSplit(FixedNode node, T oldState); - - protected abstract List processLoop(Loop loop, T initialState); -} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/EffectList.java --- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/EffectList.java Tue Oct 30 23:58:53 2012 +0100 +++ /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.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 { - - 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 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 iterator() { - return new Iterator() { - - 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; - } -} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/GraphEffectList.java --- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/GraphEffectList.java Tue Oct 30 23:58:53 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,223 +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.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 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 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 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 obsoleteNodes) { - assert node.isAlive() && value.isAlive(); - node.addInput(value); - } - }); - } - - public void addVirtualMapping(final FrameState node, final EscapeObjectState state, final HashSet reusedVirtualObjects) { - add(new Effect() { - - @Override - public String name() { - return "addVirtualMapping"; - } - - @Override - public void apply(StructuredGraph graph, ArrayList 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 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 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 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 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 obsoleteNodes) { - assert node.isAlive() && value.isAlive() && index >= 0; - node.setValueAt(index, value); - } - }); - } -} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/ReentrantBlockIterator.java --- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/ReentrantBlockIterator.java Tue Oct 30 23:58:53 2012 +0100 +++ /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.virtual.phases.ea.experimental; - -import java.util.*; - -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.cfg.*; -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 > LoopInfo processLoop(BlockIteratorClosure closure, Loop loop, T initialState) { - IdentityHashMap blockEndStates = apply(closure, loop.header, initialState, new HashSet<>(loop.blocks)); - - LoopInfo info = new LoopInfo<>(); - List 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 > IdentityHashMap apply(BlockIteratorClosure closure, Block start, T initialState, Set boundary) { - Deque blockQueue = new ArrayDeque<>(); - IdentityHashMap 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 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 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; - } -} diff -r 2d5407ae1ac4 -r 7e371de0de7d graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/SplitPartialEscapeAnalysisPhase.java --- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/experimental/SplitPartialEscapeAnalysisPhase.java Tue Oct 30 23:58:53 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1253 +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.virtual.phases.ea.experimental; - -import java.util.*; - -import com.oracle.graal.api.code.*; -import com.oracle.graal.api.meta.ResolvedJavaType.Representation; -import com.oracle.graal.api.meta.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.PhiNode.PhiType; -import com.oracle.graal.nodes.VirtualState.NodeClosure; -import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.cfg.*; -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.phases.*; -import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.schedule.*; -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 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 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 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 { - - private final HashMap objectStates = new HashMap<>(); - private final HashMap objectAliases = new HashMap<>(); - private final HashMap scalarAliases = new HashMap<>(); - - public BlockState() { - } - - public BlockState(BlockState other) { - for (Map.Entry entry : other.objectStates.entrySet()) { - objectStates.put(entry.getKey(), entry.getValue().clone()); - } - for (Map.Entry entry : other.objectAliases.entrySet()) { - objectAliases.put(entry.getKey(), entry.getValue()); - } - for (Map.Entry 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 deferred = new HashSet<>(); - GraphEffectList deferredStores = new GraphEffectList(); - materializeChangedBefore(fixed, virtual, deferred, deferredStores, materializeEffects); - materializeEffects.addAll(deferredStores); - } - - private void materializeChangedBefore(FixedNode fixed, VirtualObjectNode virtual, HashSet 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().getKind(); - } else { - VirtualInstanceNode instanceObject = (VirtualInstanceNode) virtual; - store = new CyclicMaterializeStoreNode(materialize, valueObj.materializedValue, instanceObject.field(i)); - fieldKind = instanceObject.field(i).getType().getKind(); - } - 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 states() { - return objectStates.values(); - } - - @Override - public String toString() { - return objectStates.toString(); - } - } - - private class PartialEscapeClosure extends BlockIteratorClosure { - - private final GraphEffectList effects = new GraphEffectList(); - - @Override - protected void processBlock(Block block, BlockState state) { - trace("\nBlock: %s (", block); - List 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 (obj.virtual.type().isSubtypeOf(x.type())) { - 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 virtual = new HashSet<>(); - stateAfter.applyToNonVirtual(new NodeClosure() { - - @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 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 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 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 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 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 processLoop(Loop loop, BlockState initialState) { - GraphEffectList successEffects = new GraphEffectList(); - HashSet 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 info = ReentrantBlockIterator.processLoop(this, loop, state.clone()); - - List loopEndStates = info.endStates; - List predecessors = loop.header.getPredecessors(); - HashSet 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 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 additionalMaterializations, HashSet 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(); - } -}