Mercurial > hg > truffle
changeset 8924:fc972f34c1d5
PEA: unify merge and loop logic, implement handling of identity-less virtual objects
| author | Lukas Stadler <lukas.stadler@jku.at> |
|---|---|
| date | Mon, 08 Apr 2013 19:14:32 +0200 |
| parents | a8260ba9c762 |
| children | 1b2635aa6a1d |
| files | graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualObjectNode.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java |
| diffstat | 7 files changed, 462 insertions(+), 483 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualObjectNode.java Mon Apr 08 19:12:19 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/virtual/VirtualObjectNode.java Mon Apr 08 19:14:32 2013 +0200 @@ -55,4 +55,8 @@ public abstract Kind entryKind(int index); public abstract VirtualObjectNode duplicate(); + + public boolean hasIdentity() { + return true; + } }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Mon Apr 08 19:12:19 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Mon Apr 08 19:14:32 2013 +0200 @@ -40,7 +40,7 @@ private final IdentityHashMap<VirtualObjectNode, ObjectState> objectStates = new IdentityHashMap<>(); private final IdentityHashMap<ValueNode, VirtualObjectNode> objectAliases; private final IdentityHashMap<ValueNode, ValueNode> scalarAliases; - private final HashMap<ReadCacheEntry, ValueNode> readCache; + final HashMap<ReadCacheEntry, ValueNode> readCache; static class ReadCacheEntry { @@ -167,8 +167,6 @@ ValueNode[] fieldState = obj.getEntries(); - // some entries are not default constants - do the materialization - virtual.materializeAt(fixed); MaterializeObjectNode materialize = new MaterializeObjectNode(virtual, obj.getLockCount()); ValueNode[] values = new ValueNode[obj.getEntries().length]; materialize.setProbability(fixed.probability()); @@ -249,70 +247,13 @@ return objectStates.values(); } - public Iterable<VirtualObjectNode> getVirtualObjects() { + public Collection<VirtualObjectNode> getVirtualObjects() { return objectAliases.values(); } @Override public String toString() { - return objectStates.toString(); - } - - public void mergeReadCache(List<BlockState> states, MergeNode merge, GraphEffectList effects) { - for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) { - ReadCacheEntry key = entry.getKey(); - ValueNode value = entry.getValue(); - boolean phi = false; - for (int i = 1; i < states.size(); i++) { - ValueNode otherValue = states.get(i).readCache.get(key); - if (otherValue == null) { - value = null; - phi = false; - break; - } - if (!phi && otherValue != value) { - phi = true; - } - } - if (phi) { - PhiNode phiNode = new PhiNode(value.kind(), merge); - effects.addFloatingNode(phiNode); - for (int i = 0; i < states.size(); i++) { - effects.addPhiInput(phiNode, states.get(i).getReadCache(key.object, key.identity)); - } - readCache.put(key, phiNode); - } else if (value != null) { - readCache.put(key, value); - } - } - for (PhiNode phi : merge.phis()) { - if (phi.kind() == Kind.Object) { - for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) { - if (entry.getKey().object == phi.valueAt(0)) { - mergeReadCachePhi(phi, entry.getKey().identity, states, merge, effects); - } - } - - } - } - } - - private void mergeReadCachePhi(PhiNode phi, Object identity, List<BlockState> states, MergeNode merge, GraphEffectList effects) { - ValueNode[] values = new ValueNode[phi.valueCount()]; - for (int i = 0; i < phi.valueCount(); i++) { - ValueNode value = states.get(i).getReadCache(phi.valueAt(i), identity); - if (value == null) { - return; - } - values[i] = value; - } - - PhiNode phiNode = new PhiNode(values[0].kind(), merge); - effects.addFloatingNode(phiNode); - for (int i = 0; i < values.length; i++) { - effects.addPhiInput(phiNode, values[i]); - } - readCache.put(new ReadCacheEntry(identity, phi), phiNode); + return objectStates + " " + readCache; } public static BlockState meetAliases(List<BlockState> states) { @@ -349,4 +290,38 @@ return readCache; } + public boolean equivalentTo(BlockState other) { + if (this == other) { + return true; + } + boolean objectAliasesEqual = compareMaps(objectAliases, other.objectAliases); + boolean objectStatesEqual = compareMaps(objectStates, other.objectStates); + boolean readCacheEqual = compareMapsNoSize(readCache, other.readCache); + boolean scalarAliasesEqual = scalarAliases.equals(other.scalarAliases); + return objectAliasesEqual && objectStatesEqual && readCacheEqual && scalarAliasesEqual; + } + + private static <K, V> boolean compareMaps(Map<K, V> left, Map<K, V> right) { + if (left.size() != right.size()) { + return false; + } + return compareMapsNoSize(left, right); + } + + private static <K, V> boolean compareMapsNoSize(Map<K, V> left, Map<K, V> right) { + if (left == right) { + return true; + } + for (Map.Entry<K, V> entry : right.entrySet()) { + K key = entry.getKey(); + V value = entry.getValue(); + assert value != null; + V otherValue = left.get(key); + if (otherValue != value && !value.equals(otherValue)) { + return false; + } + } + return true; + } + }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java Mon Apr 08 19:12:19 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java Mon Apr 08 19:14:32 2013 +0200 @@ -104,17 +104,17 @@ * * @param node The floating node to be added. */ - public void addFloatingNode(final ValueNode node) { + public void addFloatingNode(final ValueNode node, final String cause) { add(new Effect() { @Override public String name() { - return "addFloatingNode"; + return "addFloatingNode " + cause; } @Override public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert !node.isAlive() && !node.isDeleted(); + assert !node.isAlive() && !node.isDeleted() : node + " " + cause; graph.add(node); } }); @@ -164,7 +164,7 @@ @Override public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { - assert node.isAlive() && value.isAlive(); + assert node.isAlive() && value.isAlive() : node + " " + value; node.addInput(value); } });
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java Mon Apr 08 19:12:19 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/ObjectState.java Mon Apr 08 19:14:32 2013 +0200 @@ -22,6 +22,8 @@ */ package com.oracle.graal.virtual.phases.ea; +import java.util.*; + import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.spi.Virtualizable.EscapeState; @@ -144,4 +146,48 @@ return str.append('}').toString(); } + + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + Arrays.hashCode(entries); + result = prime * result + lockCount; + result = prime * result + ((materializedValue == null) ? 0 : materializedValue.hashCode()); + result = prime * result + ((state == null) ? 0 : state.hashCode()); + result = prime * result + ((virtual == null) ? 0 : virtual.hashCode()); + return result; + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj == null || getClass() != obj.getClass()) { + return false; + } + ObjectState other = (ObjectState) obj; + if (!Arrays.equals(entries, other.entries)) { + return false; + } + if (lockCount != other.lockCount) { + return false; + } + if (materializedValue == null) { + if (other.materializedValue != null) { + return false; + } + } else if (!materializedValue.equals(other.materializedValue)) { + return false; + } + if (state != other.state) { + return false; + } + assert virtual != null && other.virtual != null; + if (!virtual.equals(other.virtual)) { + return false; + } + return true; + } }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Mon Apr 08 19:12:19 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Mon Apr 08 19:14:32 2013 +0200 @@ -39,7 +39,6 @@ import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.schedule.*; import com.oracle.graal.virtual.nodes.*; -import com.oracle.graal.virtual.phases.ea.EffectList.Effect; public class PartialEscapeAnalysisPhase extends Phase { @@ -109,11 +108,7 @@ changed = true; // apply the effects collected during the escape analysis iteration - ArrayList<Node> obsoleteNodes = new ArrayList<>(); - for (Effect effect : closure.getEffects()) { - effect.apply(graph, obsoleteNodes); - } - trace("%s\n", closure.getEffects()); + List<Node> obsoleteNodes = closure.applyEffects(graph); Debug.dump(graph, "after PartialEscapeAnalysis iteration"); assert noObsoleteNodes(graph, obsoleteNodes); @@ -146,7 +141,7 @@ return true; } - static boolean noObsoleteNodes(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { + static boolean noObsoleteNodes(StructuredGraph graph, List<Node> obsoleteNodes) { // helper code that determines the paths that keep obsolete nodes alive: NodeFlood flood = graph.createNodeFlood();
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Mon Apr 08 19:12:19 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeClosure.java Mon Apr 08 19:14:32 2013 +0200 @@ -24,6 +24,7 @@ import static com.oracle.graal.virtual.phases.ea.PartialEscapeAnalysisPhase.*; +import java.io.*; import java.util.*; import com.oracle.graal.api.code.*; @@ -46,6 +47,7 @@ import com.oracle.graal.phases.schedule.*; import com.oracle.graal.virtual.nodes.*; import com.oracle.graal.virtual.phases.ea.BlockState.ReadCacheEntry; +import com.oracle.graal.virtual.phases.ea.EffectList.*; class PartialEscapeClosure extends BlockIteratorClosure<BlockState> { @@ -65,7 +67,8 @@ private final NodeBitMap usages; private final SchedulePhase schedule; - private final GraphEffectList effects = new GraphEffectList(); + private final BlockMap<GraphEffectList> blockEffects; + private final IdentityHashMap<Loop, GraphEffectList> loopMergeEffects = new IdentityHashMap<>(); private final VirtualizerToolImpl tool; @@ -76,19 +79,61 @@ public PartialEscapeClosure(NodeBitMap usages, SchedulePhase schedule, MetaAccessProvider metaAccess, Assumptions assumptions) { this.usages = usages; this.schedule = schedule; - tool = new VirtualizerToolImpl(effects, usages, metaAccess, assumptions); + this.tool = new VirtualizerToolImpl(usages, metaAccess, assumptions); + this.blockEffects = new BlockMap<>(schedule.getCFG()); + for (Block block : schedule.getCFG().getBlocks()) { + blockEffects.put(block, new GraphEffectList()); + } } public boolean hasChanged() { return changed; } - public GraphEffectList getEffects() { - return effects; + private static void trace2(String format, Object... args) { + Debug.log(format, args); } - public int getNewVirtualObjectCount() { - return tool.getNewVirtualObjectCount(); + public List<Node> applyEffects(final StructuredGraph graph) { + final ArrayList<Node> obsoleteNodes = new ArrayList<>(); + BlockIteratorClosure<Object> closure = new BlockIteratorClosure<Object>() { + + private void apply(GraphEffectList effects, Object context) { + if (!effects.isEmpty()) { + trace2(" ==== effects for %s", context); + for (Effect effect : effects) { + effect.apply(graph, obsoleteNodes); + if (effect.isVisible()) { + trace2(" %s", effect); + } + } + } + } + + @Override + protected void processBlock(Block block, Object currentState) { + apply(blockEffects.get(block), block); + } + + @Override + protected Object merge(Block merge, List<Object> states) { + return new Object(); + } + + @Override + protected Object cloneState(Object oldState) { + return oldState; + } + + @Override + protected List<Object> processLoop(Loop loop, Object initialState) { + LoopInfo<Object> info = ReentrantBlockIterator.processLoop(this, loop, initialState); + apply(loopMergeEffects.get(loop), loop); + return info.exitStates; + } + }; + ReentrantBlockIterator.apply(closure, schedule.getCFG().getStartBlock(), new Object(), null); + return obsoleteNodes; } public Map<Invoke, Double> getHints() { @@ -97,6 +142,9 @@ @Override protected void processBlock(Block block, BlockState state) { + GraphEffectList effects = blockEffects.get(block); + tool.setEffects(effects); + trace("\nBlock: %s (", block); List<ScheduledNode> nodeList = schedule.getBlockToNodesMap().get(block); @@ -105,7 +153,7 @@ boolean deleted; if (usages.isMarked(node) || node instanceof VirtualizableAllocation) { trace("[[%s]] ", node); - deleted = processNode((ValueNode) node, lastFixedNode == null ? null : lastFixedNode.next(), state); + deleted = processNode((ValueNode) node, lastFixedNode == null ? null : lastFixedNode.next(), state, effects); } else { trace("%s ", node); deleted = false; @@ -154,7 +202,7 @@ trace(")\n end state: %s\n", state); } - private boolean processNode(final ValueNode node, FixedNode insertBefore, final BlockState state) { + private boolean processNode(final ValueNode node, FixedNode insertBefore, final BlockState state, final GraphEffectList effects) { tool.reset(state, node); if (node instanceof Virtualizable) { ((Virtualizable) node).virtualize(tool); @@ -250,13 +298,13 @@ hints.put(invoke, 5d); } trace("replacing input %s at %s: %s", input, node, obj); - replaceWithMaterialized(input, node, insertBefore, state, obj, METRIC_MATERIALIZATIONS_UNHANDLED); + replaceWithMaterialized(input, node, insertBefore, state, obj, effects, METRIC_MATERIALIZATIONS_UNHANDLED); } } return false; } - private void ensureMaterialized(BlockState state, ObjectState obj, FixedNode materializeBefore, DebugMetric metric) { + private static void ensureMaterialized(BlockState state, ObjectState obj, FixedNode materializeBefore, GraphEffectList effects, DebugMetric metric) { assert obj != null; if (obj.getState() == EscapeState.Virtual) { metric.increment(); @@ -267,178 +315,23 @@ assert !obj.isVirtual(); } - private void replaceWithMaterialized(ValueNode value, Node usage, FixedNode materializeBefore, BlockState state, ObjectState obj, DebugMetric metric) { - ensureMaterialized(state, obj, materializeBefore, metric); + private static void replaceWithMaterialized(ValueNode value, Node usage, FixedNode materializeBefore, BlockState state, ObjectState obj, GraphEffectList effects, DebugMetric metric) { + ensureMaterialized(state, obj, materializeBefore, effects, metric); effects.replaceFirstInput(usage, value, obj.getMaterializedValue()); } @Override - protected BlockState merge(MergeNode merge, List<BlockState> states) { - BlockState newState = BlockState.meetAliases(states); - - // 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 : newState.getVirtualObjects()) { - ObjectState resultState = newState.getObjectStateOptional(object); - if (resultState == null || resultState.isVirtual()) { - int virtual = 0; - ObjectState startObj = states.get(0).getObjectState(object); - int lockCount = startObj.getLockCount(); - boolean locksMatch = true; - ValueNode singleValue = startObj.isVirtual() ? null : startObj.getMaterializedValue(); - for (BlockState state : states) { - ObjectState obj = state.getObjectState(object); - if (obj.isVirtual()) { - virtual++; - singleValue = null; - } else { - if (obj.getMaterializedValue() != singleValue) { - singleValue = null; - } - } - locksMatch &= obj.getLockCount() == lockCount; - } - - assert virtual < states.size() || locksMatch : "mismatching lock counts at " + merge; + protected BlockState merge(Block merge, List<BlockState> states) { + assert blockEffects.get(merge).isEmpty(); + MergeProcessor processor = new MergeProcessor(merge, usages, blockEffects); + processor.merge(states); + blockEffects.get(merge).addAll(processor.mergeEffects); + blockEffects.get(merge).addAll(processor.afterMergeEffects); + return processor.newState; - 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.getObjectState(object); - materialized |= obj.isVirtual(); - ensureMaterialized(state, obj, merge.forwardEndAt(i), METRIC_MATERIALIZATIONS_MERGE); - effects.addPhiInput(materializedValuePhi, obj.getMaterializedValue()); - } - newState.addObject(object, new ObjectState(object, materializedValuePhi, EscapeState.Global, lockCount)); - } else { - newState.addObject(object, new ObjectState(object, singleValue, EscapeState.Global, lockCount)); - } - } else { - assert virtual == states.size(); - ValueNode[] values = startObj.getEntries().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.getObjectState(object).getEntries(); - 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.getObjectState(object).getEntries(); - for (int index = 0; index < values.length; index++) { - if (phis[index] != null) { - ObjectState obj = state.getObjectState(fields[index]); - if (obj != null) { - materialized |= obj.isVirtual(); - ensureMaterialized(state, obj, merge.forwardEndAt(i), METRIC_MATERIALIZATIONS_MERGE); - fields[index] = obj.getMaterializedValue(); - } - 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, EscapeState.Virtual, lockCount)); - } - } - } - - for (PhiNode phi : merge.phis()) { - if (usages.isMarked(phi) && phi.type() == PhiType.Value) { - materialized |= processPhi(newState, merge, phi, states); - } - } - } while (materialized); - - newState.mergeReadCache(states, merge, effects); - - return newState; } - private boolean processPhi(BlockState newState, MergeNode merge, PhiNode phi, List<BlockState> states) { - assert states.size() == phi.valueCount(); - int virtualInputs = 0; - boolean materialized = false; - VirtualObjectNode sameObject = null; - ResolvedJavaType sameType = null; - int sameEntryCount = -1; - for (int i = 0; i < phi.valueCount(); i++) { - ValueNode value = phi.valueAt(i); - ObjectState obj = states.get(i).getObjectState(value); - if (obj != null) { - if (obj.isVirtual()) { - 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, i, obj.getMaterializedValue()); - } - } - } - 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).getObjectState(value); - if (obj != null) { - materialized |= obj.isVirtual(); - replaceWithMaterialized(value, phi, merge.forwardEndAt(i), states.get(i), obj, METRIC_MATERIALIZATIONS_PHI); - } - } - } - return materialized; - } + static PrintStream out = System.out; @Override protected BlockState cloneState(BlockState oldState) { @@ -447,84 +340,45 @@ @Override protected List<BlockState> processLoop(Loop loop, BlockState initialState) { - GraphEffectList successEffects = new GraphEffectList(); - HashSet<PhiDesc> phis = new HashSet<>(); + BlockState loopEntryState = initialState; + BlockState lastMergedState = initialState; + MergeProcessor mergeProcessor = new MergeProcessor(loop.header, usages, blockEffects); for (int iteration = 0; iteration < 10; iteration++) { - BlockState state = initialState.cloneState(); - int checkpoint = effects.checkpoint(); - - for (PhiDesc desc : phis) { - ObjectState obj = state.getObjectState(desc.virtualObject); - if (obj.isVirtual()) { - ValueNode value = obj.getEntry(desc.fieldIndex); - ObjectState valueObj = state.getObjectState(value); - if (valueObj != null) { - assert !valueObj.isVirtual(); - value = valueObj.getMaterializedValue(); - } - - PhiNode phiNode = new PhiNode(value.kind(), loop.loopBegin()); - effects.addFloatingNode(phiNode); - effects.addPhiInput(phiNode, value); - obj.setEntry(desc.fieldIndex, phiNode); - } - } + LoopInfo<BlockState> info = ReentrantBlockIterator.processLoop(this, loop, lastMergedState.cloneState()); - for (PhiNode phi : loop.loopBegin().phis()) { - if (usages.isMarked(phi) && phi.type() == PhiType.Value) { - ObjectState initialObj = initialState.getObjectState(phi.valueAt(0)); - if (initialObj != null) { - if (initialObj.isVirtual()) { - state.addAndMarkAlias(initialObj.virtual, phi, usages); - } else { - successEffects.setPhiInput(phi, 0, initialObj.getMaterializedValue()); - } - } - } - } + List<BlockState> states = new ArrayList<>(); + states.add(initialState); + states.addAll(info.endStates); + mergeProcessor.merge(states); - effects.incLevel(); - LoopInfo<BlockState> info = ReentrantBlockIterator.processLoop(this, loop, state.cloneState()); + Debug.log("================== %s", loop.header); + Debug.log("%s", mergeProcessor.newState); + Debug.log("===== vs."); + Debug.log("%s", lastMergedState); - HashSet<VirtualObjectNode> additionalMaterializations = new HashSet<>(); - HashSet<ReadCacheEntry> additionalKilledReads = new HashSet<>(); - int oldPhiCount = phis.size(); - processLoopEnds(loop, state, info.endStates, successEffects, additionalMaterializations, additionalKilledReads, phis); - if (additionalMaterializations.isEmpty() && additionalKilledReads.isEmpty() && oldPhiCount == phis.size()) { - effects.addAll(successEffects); + if (mergeProcessor.newState.equivalentTo(lastMergedState)) { + blockEffects.get(loop.header).insertAll(mergeProcessor.mergeEffects, 0); + loopMergeEffects.put(loop, mergeProcessor.afterMergeEffects); 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); + processLoopExit((LoopExitNode) loop.exits.get(i).getBeginNode(), loopEntryState, exitState, blockEffects.get(loop.exits.get(i))); } - effects.decLevel(); return info.exitStates; } else { - successEffects.clear(); - effects.backtrack(checkpoint); - effects.decLevel(); - for (VirtualObjectNode virtualObject : additionalMaterializations) { - ObjectState obj = initialState.getObjectState(virtualObject); - if (obj.isVirtual()) { - METRIC_MATERIALIZATIONS_LOOP_REITERATION.increment(); - initialState.materializeBefore(loop.loopBegin().forwardEnd(), virtualObject, EscapeState.Global, effects); - } else { - assert obj.getState() == EscapeState.Global; - } - } - for (ReadCacheEntry entry : additionalKilledReads) { - initialState.getReadCache().remove(entry); + lastMergedState = mergeProcessor.newState; + for (Block block : loop.blocks) { + blockEffects.get(block).clear(); } } } - throw new GraalInternalError("too many iterations at %s", loop); } - private void processLoopExit(LoopExitNode exitNode, BlockState initialState, BlockState exitState) { + private static void processLoopExit(LoopExitNode exitNode, BlockState initialState, BlockState exitState, GraphEffectList effects) { HashMap<VirtualObjectNode, ProxyNode> proxies = new HashMap<>(); for (ProxyNode proxy : exitNode.proxies()) { @@ -543,7 +397,7 @@ if ((value instanceof PhiNode && ((PhiNode) value).merge() == exitNode.loopBegin()) || initialObj == null || !initialObj.isVirtual() || initialObj.getEntry(i) != value) { ProxyNode proxy = new ProxyNode(value, exitNode, PhiType.Value, null); obj.setEntry(i, proxy); - effects.addFloatingNode(proxy); + effects.addFloatingNode(proxy, "virtualProxy"); } } } @@ -552,15 +406,18 @@ ProxyNode proxy = proxies.get(obj.virtual); if (proxy == null) { proxy = new ProxyNode(obj.getMaterializedValue(), exitNode, PhiType.Value, null); - effects.addFloatingNode(proxy); + effects.addFloatingNode(proxy, "proxy"); } else { effects.replaceFirstInput(proxy, proxy.value(), obj.getMaterializedValue()); // nothing to do - will be handled in processNode } obj.updateMaterializedValue(proxy); } else { - assert initialObj.getMaterializedValue() == obj.getMaterializedValue() : "materialized value is not allowed to change within loops: " + initialObj.getMaterializedValue() + - " vs. " + obj.getMaterializedValue() + " at " + exitNode; + // assert initialObj.getMaterializedValue() == obj.getMaterializedValue() : + // "materialized value is not allowed to change within loops: " + +// initialObj.getMaterializedValue() + // + + // " vs. " + obj.getMaterializedValue() + " at " + exitNode; } } } @@ -568,207 +425,312 @@ for (Map.Entry<ReadCacheEntry, ValueNode> entry : exitState.getReadCache().entrySet()) { if (initialState.getReadCache().get(entry.getKey()) != entry.getValue()) { ProxyNode proxy = new ProxyNode(exitState.getReadCache(entry.getKey().object, entry.getKey().identity), exitNode, PhiType.Value, null); - effects.addFloatingNode(proxy); + effects.addFloatingNode(proxy, "readCacheProxy"); entry.setValue(proxy); } } } - private final class PhiDesc { + private static class MergeProcessor { + + private final Block mergeBlock; + private final MergeNode merge; + private final NodeBitMap usages; + private final BlockMap<GraphEffectList> blockEffects; + private final GraphEffectList mergeEffects; + private final GraphEffectList afterMergeEffects; - public final VirtualObjectNode virtualObject; - public final int fieldIndex; + private final HashMap<Object, PhiNode> materializedPhis = new HashMap<>(); + private final IdentityHashMap<VirtualObjectNode, PhiNode[]> valuePhis = new IdentityHashMap<>(); + private final IdentityHashMap<PhiNode, PhiNode[]> valueObjectMergePhis = new IdentityHashMap<>(); + private final IdentityHashMap<PhiNode, VirtualObjectNode> valueObjectVirtuals = new IdentityHashMap<>(); + private BlockState newState; - public PhiDesc(VirtualObjectNode virtualObject, int fieldIndex) { - this.virtualObject = virtualObject; - this.fieldIndex = fieldIndex; + public MergeProcessor(Block mergeBlock, NodeBitMap usages, BlockMap<GraphEffectList> blockEffects) { + this.usages = usages; + this.mergeBlock = mergeBlock; + this.blockEffects = blockEffects; + this.merge = (MergeNode) mergeBlock.getBeginNode(); + this.mergeEffects = new GraphEffectList(); + this.afterMergeEffects = new GraphEffectList(); } - @Override - public int hashCode() { - final int prime = 31; - int result = fieldIndex; - result = prime * result + ((virtualObject == null) ? 0 : virtualObject.hashCode()); + private <T> PhiNode getCachedPhi(T virtual, Kind kind) { + PhiNode result = materializedPhis.get(virtual); + if (result == null) { + result = new PhiNode(kind, merge); + materializedPhis.put(virtual, result); + } + return result; + } + + private PhiNode[] getValuePhis(VirtualObjectNode virtual) { + PhiNode[] result = valuePhis.get(virtual); + if (result == null) { + result = new PhiNode[virtual.entryCount()]; + valuePhis.put(virtual, result); + } + return result; + } + + private PhiNode[] getValueObjectMergePhis(PhiNode phi, int entryCount) { + PhiNode[] result = valueObjectMergePhis.get(phi); + if (result == null) { + result = new PhiNode[entryCount]; + valueObjectMergePhis.put(phi, result); + } + return result; + } + + private VirtualObjectNode getValueObjectVirtual(PhiNode phi, VirtualObjectNode virtual) { + VirtualObjectNode result = valueObjectVirtuals.get(phi); + if (result == null) { + result = virtual.duplicate(); + valueObjectVirtuals.put(phi, result); + } 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 merge(List<BlockState> states) { + newState = BlockState.meetAliases(states); - private void processLoopEnds(Loop loop, BlockState initialState, List<BlockState> loopEndStates, GraphEffectList successEffects, Set<VirtualObjectNode> additionalMaterializations, - HashSet<ReadCacheEntry> additionalKilledReads, HashSet<PhiDesc> phis) { - LoopBeginNode loopBegin = loop.loopBegin(); - int loopEndCount = loop.header.getPredecessorCount() - 1; - - boolean materialized; - do { - materialized = false; - for (ObjectState state : initialState.getStates()) { - for (int loopEndIndex = 0; loopEndIndex < loopEndCount; loopEndIndex++) { - BlockState loopEndState = loopEndStates.get(loopEndIndex); + /* + * 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. + */ - ObjectState endState = loopEndState.getObjectState(state.virtual); - if (state.isVirtual()) { - if (endState.isVirtual()) { - assert state.getEntries().length == endState.getEntries().length; - for (int i = 0; endState.isVirtual() && i < state.getEntries().length; i++) { - ValueNode value = state.getEntry(i); - ValueNode endValue = endState.getEntry(i); - ObjectState valueObj = initialState.getObjectState(value); - ObjectState endValueObj = loopEndState.getObjectState(endValue); + HashSet<VirtualObjectNode> virtualObjects = new HashSet<>(newState.getVirtualObjects()); + boolean materialized; + do { + mergeEffects.clear(); + afterMergeEffects.clear(); + materialized = false; + for (VirtualObjectNode object : virtualObjects) { + ObjectState[] objStates = new ObjectState[states.size()]; + for (int i = 0; i < states.size(); i++) { + objStates[i] = states.get(i).getObjectState(object); + } + int virtual = 0; + ObjectState startObj = objStates[0]; + int lockCount = startObj.getLockCount(); + boolean locksMatch = true; + ValueNode singleValue = startObj.isVirtual() ? null : startObj.getMaterializedValue(); + for (ObjectState obj : objStates) { + if (obj.isVirtual()) { + virtual++; + singleValue = null; + } else { + if (obj.getMaterializedValue() != singleValue) { + singleValue = null; + } + } + locksMatch &= obj.getLockCount() == lockCount; + } - if (valueObj != null) { - if (valueObj.isVirtual()) { - if (endValueObj == null || !endValueObj.isVirtual() || 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.isVirtual()) { - METRIC_MATERIALIZATIONS_LOOP_END.increment(); - FixedNode endNode = loop.header.getPredecessors().get(loopEndIndex + 1).getEndNode(); - loopEndState.materializeBefore(endNode, endValueObj.virtual, EscapeState.Global, successEffects); - materialized = true; - } - } - } + assert virtual < states.size() || locksMatch : "mismatching lock counts at " + merge; + + if (virtual < states.size()) { + if (singleValue == null) { + PhiNode materializedValuePhi = getCachedPhi(object, Kind.Object); + mergeEffects.addFloatingNode(materializedValuePhi, "materializedPhi"); + for (int i = 0; i < states.size(); i++) { + BlockState state = states.get(i); + ObjectState obj = objStates[i]; + materialized |= obj.isVirtual(); + Block predecessor = mergeBlock.getPredecessors().get(i); + ensureMaterialized(state, obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE); + afterMergeEffects.addPhiInput(materializedValuePhi, obj.getMaterializedValue()); + } + newState.addObject(object, new ObjectState(object, materializedValuePhi, EscapeState.Global, lockCount)); + } else { + newState.addObject(object, new ObjectState(object, singleValue, EscapeState.Global, lockCount)); + } + } else { + assert virtual == states.size(); + ValueNode[] values = startObj.getEntries().clone(); + PhiNode[] phis = getValuePhis(object); + for (int index = 0; index < values.length; index++) { + for (int i = 1; i < states.size(); i++) { + ValueNode[] fields = objStates[i].getEntries(); + if (phis[index] == null && values[index] != fields[index]) { + phis[index] = new PhiNode(values[index].kind(), merge); } } + } + outer: for (int index = 0; index < values.length; index++) { + if (phis[index] != null) { + mergeEffects.addFloatingNode(phis[index], "virtualMergePhi"); + for (int i = 0; i < states.size(); i++) { + if (!objStates[i].isVirtual()) { + break outer; + } + ValueNode[] fields = objStates[i].getEntries(); + ObjectState obj = states.get(i).getObjectState(fields[index]); + if (obj != null) { + materialized |= obj.isVirtual(); + Block predecessor = mergeBlock.getPredecessors().get(i); + ensureMaterialized(states.get(i), obj, predecessor.getEndNode(), blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_MERGE); + fields[index] = obj.getMaterializedValue(); + } + afterMergeEffects.addPhiInput(phis[index], fields[index]); + } + values[index] = phis[index]; + } + } + newState.addObject(object, new ObjectState(object, values, EscapeState.Virtual, lockCount)); + } + } + + for (PhiNode phi : merge.phis()) { + if (usages.isMarked(phi) && phi.type() == PhiType.Value) { + materialized |= processPhi(phi, states); + } + } + } while (materialized); + + mergeReadCache(states); + } + + private boolean processPhi(PhiNode phi, List<BlockState> states) { + assert states.size() == phi.valueCount(); + int virtualInputs = 0; + boolean materialized = false; + VirtualObjectNode sameObject = null; + ResolvedJavaType sameType = null; + int sameEntryCount = -1; + boolean hasIdentity = false; + for (int i = 0; i < phi.valueCount(); i++) { + ValueNode value = phi.valueAt(i); + ObjectState obj = states.get(i).getObjectState(value); + if (obj != null) { + if (obj.isVirtual()) { + virtualInputs++; + if (i == 0) { + sameObject = obj.virtual; + sameType = obj.virtual.type(); + sameEntryCount = obj.virtual.entryCount(); } else { - additionalMaterializations.add(state.virtual); + if (sameObject != obj.virtual) { + sameObject = null; + } + if (sameType != obj.virtual.type()) { + sameType = null; + } + if (sameEntryCount != obj.virtual.entryCount()) { + sameEntryCount = -1; + } + hasIdentity |= obj.virtual.hasIdentity(); } + } else { + afterMergeEffects.setPhiInput(phi, i, obj.getMaterializedValue()); } } } - - for (PhiNode phi : loopBegin.phis()) { - if (usages.isMarked(phi) && phi.type() == PhiType.Value) { - ObjectState initialObj = initialState.getObjectState(phi.valueAt(0)); - boolean initialMaterialized = initialObj == null || !initialObj.isVirtual(); + 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) { + if (!hasIdentity) { + VirtualObjectNode virtual = getValueObjectVirtual(phi, states.get(0).getObjectState(phi.valueAt(0)).virtual); - for (int loopEndIndex = 0; loopEndIndex < loopEndCount; loopEndIndex++) { - BlockState loopEndState = loopEndStates.get(loopEndIndex); - LoopEndNode endNode = (LoopEndNode) loop.header.getPredecessors().get(loopEndIndex + 1).getEndNode(); - ObjectState loopEndObj = loopEndState.getObjectState(phi.valueAt(endNode)); - if (loopEndObj == null || !loopEndObj.isVirtual()) { - if (loopEndObj != null) { - successEffects.setPhiInput(phi, loopBegin.phiPredecessorIndex(endNode), loopEndObj.getMaterializedValue()); + PhiNode[] phis = getValueObjectMergePhis(phi, virtual.entryCount()); + for (int i = 0; i < virtual.entryCount(); i++) { + assert virtual.entryKind(i) != Kind.Object; + if (phis[i] == null) { + phis[i] = new PhiNode(virtual.entryKind(i), merge); } - if (!initialMaterialized) { - additionalMaterializations.add(initialObj.virtual); - } - } else { - if (initialMaterialized) { - loopEndState.materializeBefore(endNode, loopEndObj.virtual, EscapeState.Global, successEffects); - materialized = true; - } else { - if (loopEndObj.virtual != initialObj.virtual) { - additionalMaterializations.add(initialObj.virtual); - } + mergeEffects.addFloatingNode(phis[i], "valueObjectPhi"); + for (int i2 = 0; i2 < phi.valueCount(); i2++) { + afterMergeEffects.addPhiInput(phis[i], states.get(i2).getObjectState(phi.valueAt(i2)).getEntry(i)); } } + mergeEffects.addFloatingNode(virtual, "valueObjectNode"); + newState.addObject(virtual, new ObjectState(virtual, Arrays.copyOf(phis, phis.length, ValueNode[].class), EscapeState.Virtual, 0)); + newState.addAndMarkAlias(virtual, virtual, usages); + newState.addAndMarkAlias(virtual, phi, usages); + } else { + materialize = true; + } + } 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).getObjectState(value); + if (obj != null) { + materialized |= obj.isVirtual(); + Block predecessor = mergeBlock.getPredecessors().get(i); + replaceWithMaterialized(value, phi, predecessor.getEndNode(), states.get(i), obj, blockEffects.get(predecessor), METRIC_MATERIALIZATIONS_PHI); } } } - - } while (materialized); - - for (ObjectState state : initialState.getStates()) { - for (BlockState loopEndState : loopEndStates) { - ObjectState endState = loopEndState.getObjectState(state.virtual); - if (state.isVirtual()) { - if (endState.isVirtual()) { - assert state.getEntries().length == endState.getEntries().length; - for (int i = 0; i < state.getEntries().length; i++) { - ValueNode value = state.getEntry(i); - ValueNode endValue = endState.getEntry(i); - ObjectState valueObj = initialState.getObjectState(value); - ObjectState endValueObj = loopEndState.getObjectState(endValue); + return materialized; + } - if (valueObj != null) { - if (valueObj.isVirtual()) { - if (endValueObj == null || !endValueObj.isVirtual() || 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.getMaterializedValue() != valueObj.getMaterializedValue()) || - (endValueObj == null && valueObj.getMaterializedValue() != 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.isVirtual()) { - assert !additionalMaterializations.isEmpty(); - } - successEffects.addPhiInput((PhiNode) value, endValueObj.getMaterializedValue()); - } else { - successEffects.addPhiInput((PhiNode) value, endValue); - } - } else if (value != endValue) { - phis.add(new PhiDesc(state.virtual, i)); - } - } - } - } else { - // endState.materializedValue != null - assert !additionalMaterializations.isEmpty(); + private void mergeReadCache(List<BlockState> states) { + for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) { + ReadCacheEntry key = entry.getKey(); + ValueNode value = entry.getValue(); + boolean phi = false; + for (int i = 1; i < states.size(); i++) { + ValueNode otherValue = states.get(i).readCache.get(key); + if (otherValue == null) { + value = null; + phi = false; + break; + } + if (!phi && otherValue != value) { + phi = true; } - } else { - // state.materializedValue != null - if (endState.isVirtual()) { - /* - * throw new GraalInternalError("un-materialized object state at %s", - * loopEnd); - */ - } else { - if (state.getMaterializedValue() != endState.getMaterializedValue()) { - /* - * throw new - * GraalInternalError("changed materialized value during loop: %s vs %s" - * , state.materializedValue, endState.materializedValue); - */ + } + if (phi) { + PhiNode phiNode = getCachedPhi(entry, value.kind()); + mergeEffects.addFloatingNode(phiNode, "mergeReadCache"); + for (int i = 0; i < states.size(); i++) { + afterMergeEffects.addPhiInput(phiNode, states.get(i).getReadCache(key.object, key.identity)); + } + newState.readCache.put(key, phiNode); + } else if (value != null) { + newState.readCache.put(key, value); + } + } + for (PhiNode phi : merge.phis()) { + if (phi.kind() == Kind.Object) { + for (Map.Entry<ReadCacheEntry, ValueNode> entry : states.get(0).readCache.entrySet()) { + if (entry.getKey().object == phi.valueAt(0)) { + mergeReadCachePhi(phi, entry.getKey().identity, states); } } + } } } - for (Map.Entry<ReadCacheEntry, ValueNode> entry : initialState.getReadCache().entrySet()) { - for (BlockState loopEndState : loopEndStates) { - if (loopEndState.getReadCache().get(entry.getKey()) != entry.getValue()) { - additionalKilledReads.add(entry.getKey()); + private void mergeReadCachePhi(PhiNode phi, Object identity, List<BlockState> states) { + ValueNode[] values = new ValueNode[phi.valueCount()]; + for (int i = 0; i < phi.valueCount(); i++) { + ValueNode value = states.get(i).getReadCache(phi.valueAt(i), identity); + if (value == null) { + return; } + values[i] = value; } + + PhiNode phiNode = getCachedPhi(new ReadCacheEntry(identity, phi), values[0].kind()); + mergeEffects.addFloatingNode(phiNode, "mergeReadCachePhi"); + for (int i = 0; i < values.length; i++) { + afterMergeEffects.addPhiInput(phiNode, values[i]); + } + newState.readCache.put(new ReadCacheEntry(identity, phi), phiNode); } } }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java Mon Apr 08 19:12:19 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/VirtualizerToolImpl.java Mon Apr 08 19:14:32 2013 +0200 @@ -36,13 +36,12 @@ class VirtualizerToolImpl implements VirtualizerTool { - private final GraphEffectList effects; private final NodeBitMap usages; private final MetaAccessProvider metaAccess; private final Assumptions assumptions; + private GraphEffectList effects; - VirtualizerToolImpl(GraphEffectList effects, NodeBitMap usages, MetaAccessProvider metaAccess, Assumptions assumptions) { - this.effects = effects; + VirtualizerToolImpl(NodeBitMap usages, MetaAccessProvider metaAccess, Assumptions assumptions) { this.usages = usages; this.metaAccess = metaAccess; this.assumptions = assumptions; @@ -52,7 +51,6 @@ private boolean customAction; private BlockState state; private ValueNode current; - private int newVirtualObjectCount = 0; @Override public MetaAccessProvider getMetaAccessProvider() { @@ -64,6 +62,10 @@ return assumptions; } + public void setEffects(GraphEffectList effects) { + this.effects = effects; + } + public void reset(BlockState newState, ValueNode newCurrent) { deleted = false; customAction = false; @@ -79,10 +81,6 @@ return customAction; } - public int getNewVirtualObjectCount() { - return newVirtualObjectCount; - } - @Override public State getObjectState(ValueNode value) { return state.getObjectState(value); @@ -155,7 +153,7 @@ if (virtualObject.isAlive()) { state.addAndMarkAlias(virtualObject, virtualObject, usages); } else { - effects.addFloatingNode(virtualObject); + effects.addFloatingNode(virtualObject, "newVirtualObject"); } for (int i = 0; i < entryState.length; i++) { entryState[i] = state.getScalarAlias(entryState[i]); @@ -163,7 +161,6 @@ state.addObject(virtualObject, new ObjectState(virtualObject, entryState, EscapeState.Virtual, lockCount)); state.addAndMarkAlias(virtualObject, virtualObject, usages); PartialEscapeClosure.METRIC_ALLOCATION_REMOVED.increment(); - newVirtualObjectCount++; } @Override