# HG changeset patch # User Gilles Duboscq # Date 1342548420 -7200 # Node ID 421e767d8038f5a78dbc1f3213a9c695f915dedd # Parent 610f9e377c70d2e74a63cb78a7c31accf72b8bbb Make FloatingRead phase respect loop closed form and use PostOrderNodeIterator Do low loop transformations and proxies removal before CheckCastElimination diff -r 610f9e377c70 -r 421e767d8038 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 Mon Jul 16 11:07:07 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Jul 17 20:07:00 2012 +0200 @@ -181,18 +181,24 @@ new CullFrameStatesPhase().apply(graph); } - new FloatingReadPhase().apply(graph); - if (GraalOptions.OptGVN) { - new GlobalValueNumberingPhase().apply(graph); - } - if (GraalOptions.OptReadElimination) { - new ReadEliminationPhase().apply(graph); + if (GraalOptions.FloatingReads) { + int mark = graph.getMark(); + new FloatingReadPhase().apply(graph); + new CanonicalizerPhase(target, runtime, assumptions, mark, null).apply(graph); + if (GraalOptions.OptReadElimination) { + new ReadEliminationPhase().apply(graph); + } } if (GraalOptions.PropagateTypes) { new PropagateTypeCachePhase(target, runtime, assumptions).apply(graph); } + if (GraalOptions.OptLoopTransform) { + new LoopTransformLowPhase().apply(graph); + } + new RemoveValueProxyPhase().apply(graph); + if (GraalOptions.CheckCastElimination) { new CheckCastEliminationPhase().apply(graph); } @@ -200,19 +206,10 @@ new CanonicalizerPhase(target, runtime, assumptions).apply(graph); } - if (GraalOptions.OptLoopTransform) { - new LoopTransformLowPhase().apply(graph); - } - new RemoveValueProxyPhase().apply(graph); - plan.runPhases(PhasePosition.MID_LEVEL, graph); plan.runPhases(PhasePosition.LOW_LEVEL, graph); - new DeadCodeEliminationPhase().apply(graph); - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase(target, runtime, assumptions).apply(graph); - } // Add safepoints to loops if (GraalOptions.GenLoopSafepoints) { new LoopSafepointInsertionPhase().apply(graph); diff -r 610f9e377c70 -r 421e767d8038 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/FloatingRead2Phase.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/FloatingRead2Phase.java Mon Jul 16 11:07:07 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,266 +0,0 @@ -/* - * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ -package com.oracle.graal.compiler.phases; - -import java.util.*; - -import com.oracle.graal.compiler.graph.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.PhiNode.PhiType; -import com.oracle.graal.nodes.extended.*; - -public class FloatingRead2Phase extends Phase { - - private IdentityHashMap> loopEndStatesMap; - - private static class LoopState { - public LoopBeginNode loopBegin; - public MemoryMap state; - public IdentityHashMap loopPhiLocations = new IdentityHashMap<>(); - public ValueNode loopEntryAnyLocation; - public LoopState(LoopBeginNode loopBegin, MemoryMap state, ValueNode loopEntryAnyLocation) { - this.loopBegin = loopBegin; - this.state = state; - this.loopEntryAnyLocation = loopEntryAnyLocation; - } - } - - private class MemoryMap implements MergeableState { - private IdentityHashMap lastMemorySnapshot; - private LinkedList loops; - - public MemoryMap(MemoryMap memoryMap) { - lastMemorySnapshot = new IdentityHashMap<>(memoryMap.lastMemorySnapshot); - loops = new LinkedList<>(memoryMap.loops); - } - - public MemoryMap() { - lastMemorySnapshot = new IdentityHashMap<>(); - loops = new LinkedList<>(); - } - - @Override - public boolean merge(MergeNode merge, List withStates) { - if (withStates.size() == 0) { - return true; - } - Debug.log("Merge with %s", lastMemorySnapshot); - IdentityHashMap visitedKeys = new IdentityHashMap<>(); - for (MemoryMap other : withStates) { - Debug.log(" other: %s", other.lastMemorySnapshot); - for (Map.Entry entry : lastMemorySnapshot.entrySet()) { - Object key = entry.getKey(); - visitedKeys.put(key, key); - ValueNode localNode = entry.getValue(); - ValueNode otherNode = other.lastMemorySnapshot.get(key); - if (otherNode == null) { - otherNode = other.lastMemorySnapshot.get(LocationNode.ANY_LOCATION); - } - assert localNode != null; - if (localNode != otherNode && !merge.isPhiAtMerge(localNode)) { - PhiNode phi = merge.graph().add(new PhiNode(PhiType.Memory, merge)); - phi.addInput(localNode); - lastMemorySnapshot.put(key, phi); - } - } - } - for (Map.Entry entry : lastMemorySnapshot.entrySet()) { - ValueNode localNode = entry.getValue(); - PhiNode phi = null; - if (merge.isPhiAtMerge(localNode)) { - phi = (PhiNode) localNode; - } else if (!visitedKeys.containsKey(entry.getKey())) { - phi = merge.graph().add(new PhiNode(PhiType.Memory, merge)); - phi.addInput(localNode); - lastMemorySnapshot.put(entry.getKey(), phi); - } - if (phi != null) { - Debug.log("Phi @ %s for %s", merge, entry.getKey()); - for (MemoryMap other : withStates) { - ValueNode otherNode = other.lastMemorySnapshot.get(entry.getKey()); - if (otherNode == null) { - otherNode = other.lastMemorySnapshot.get(LocationNode.ANY_LOCATION); - } - assert otherNode != null; - phi.addInput(otherNode); - } - } - } - return true; - } - - @Override - public void loopBegin(LoopBeginNode loopBegin) { - LoopState loopState = new LoopState(loopBegin, this, lastMemorySnapshot.get(LocationNode.ANY_LOCATION)); - for (Map.Entry entry : lastMemorySnapshot.entrySet()) { - PhiNode phi = loopBegin.graph().add(new PhiNode(PhiType.Memory, loopBegin)); - phi.addInput(entry.getValue()); - entry.setValue(phi); - loopState.loopPhiLocations.put(phi, entry.getKey()); - } - loops.push(loopState); - } - - @Override - public void loopEnds(LoopBeginNode loopBegin, List loopEndStates) { - loopEndStatesMap.put(loopBegin, loopEndStates); - tryFinishLoopPhis(this, loopBegin); - } - - @Override - public void afterSplit(FixedNode node) { - // nothing - } - - @Override - public MemoryMap clone() { - return new MemoryMap(this); - } - } - - @Override - protected void run(StructuredGraph graph) { - loopEndStatesMap = new IdentityHashMap<>(); - new PostOrderNodeIterator(graph.start(), new MemoryMap()) { - @Override - protected void node(FixedNode node) { - processNode(node, state); - } - }.apply(); - } - - private void processNode(FixedNode node, MemoryMap state) { - if (node instanceof ReadNode) { - processRead((ReadNode) node, state); - } else if (node instanceof WriteNode) { - processWrite((WriteNode) node, state); - } else if (node instanceof MemoryCheckpoint) { - processCheckpoint((MemoryCheckpoint) node, state); - } else if (node instanceof LoopExitNode) { - processLoopExit((LoopExitNode) node, state); - } - } - - private static void processCheckpoint(MemoryCheckpoint checkpoint, MemoryMap state) { - for (Map.Entry entry : state.lastMemorySnapshot.entrySet()) { - entry.setValue((ValueNode) checkpoint); - } - state.lastMemorySnapshot.put(LocationNode.ANY_LOCATION, (ValueNode) checkpoint); - } - - private static void processWrite(WriteNode writeNode, MemoryMap state) { - if (writeNode.location().locationIdentity() == LocationNode.ANY_LOCATION) { - state.lastMemorySnapshot.clear(); - } - state.lastMemorySnapshot.put(writeNode.location().locationIdentity(), writeNode); - } - - private void processRead(ReadNode readNode, MemoryMap state) { - StructuredGraph graph = (StructuredGraph) readNode.graph(); - assert readNode.getNullCheck() == false; - Object locationIdentity = readNode.location().locationIdentity(); - ValueNode lastLocationAccess = getLastLocationAccessForRead(state, locationIdentity); - FloatingReadNode floatingRead = graph.unique(new FloatingReadNode(readNode.object(), readNode.location(), lastLocationAccess, readNode.stamp(), readNode.dependencies())); - floatingRead.setNullCheck(readNode.getNullCheck()); - ValueAnchorNode anchor = null; - for (GuardNode guard : readNode.dependencies().filter(GuardNode.class)) { - if (anchor == null) { - anchor = graph.add(new ValueAnchorNode()); - } - anchor.addAnchoredNode(guard); - } - if (anchor != null) { - graph.addAfterFixed(readNode, anchor); - } - graph.replaceFixedWithFloating(readNode, floatingRead); - } - - private ValueNode getLastLocationAccessForRead(MemoryMap state, Object locationIdentity) { - ValueNode lastLocationAccess; - if (locationIdentity == LocationNode.FINAL_LOCATION) { - lastLocationAccess = null; - } else { - lastLocationAccess = state.lastMemorySnapshot.get(locationIdentity); - if (lastLocationAccess == null) { - LoopState lastLoop = state.loops.peek(); - if (lastLoop == null) { - lastLocationAccess = state.lastMemorySnapshot.get(LocationNode.ANY_LOCATION); - Debug.log("getLastLocationAccessForRead(%s, %s) -> unknown, not in a loop : %s", state, locationIdentity, lastLocationAccess); - } else { - ValueNode phiInit; - if (state.loops.size() > 1) { - Debug.log("getLastLocationAccessForRead(%s, %s) -> unknown, in a non-outtermost loop, getting state in 2nd loop", state, locationIdentity); - phiInit = getLastLocationAccessForRead(state.loops.get(1).state, locationIdentity); - } else { - phiInit = lastLoop.loopEntryAnyLocation; - Debug.log("getLastLocationAccessForRead(%s, %s) -> unknown, in a outtermost loop : Phi(%s,...)", state, locationIdentity, phiInit); - } - PhiNode phi = lastLoop.loopBegin.graph().add(new PhiNode(PhiType.Memory, lastLoop.loopBegin)); - phi.addInput(phiInit); - lastLoop.state.lastMemorySnapshot.put(locationIdentity, phi); - lastLoop.loopPhiLocations.put(phi, locationIdentity); - tryFinishLoopPhis(lastLoop.state, lastLoop.loopBegin); - lastLocationAccess = phi; - } - state.lastMemorySnapshot.put(locationIdentity, lastLocationAccess); - } else { - Debug.log("getLastLocationAccessForRead(%s, %s) -> directly : %s", state, locationIdentity, lastLocationAccess); - } - } - return lastLocationAccess; - } - - private static void processLoopExit(LoopExitNode exit, MemoryMap state) { - for (Map.Entry entry : state.lastMemorySnapshot.entrySet()) { - entry.setValue(exit.graph().unique(new ValueProxyNode(entry.getValue(), exit, PhiType.Memory))); - } - LoopState poped = state.loops.pop(); - assert poped.loopBegin == exit.loopBegin(); - } - - private void tryFinishLoopPhis(MemoryMap loopMemory, LoopBeginNode loopBegin) { - List loopEndStates = loopEndStatesMap.get(loopBegin); - if (loopEndStates == null) { - return; - } - LoopState loopState = loopMemory.loops.get(0); - int i = 0; - while (loopState.loopBegin != loopBegin) { - loopState = loopMemory.loops.get(++i); - } - for (PhiNode phi : loopBegin.phis()) { - if (phi.type() == PhiType.Memory && phi.valueCount() == 1) { - Object location = loopState.loopPhiLocations.get(phi); - assert location != null : "unknown location for " + phi; - for (MemoryMap endState : loopEndStates) { - ValueNode otherNode = endState.lastMemorySnapshot.get(location); - if (otherNode == null) { - otherNode = endState.lastMemorySnapshot.get(LocationNode.ANY_LOCATION); - } - phi.addInput(otherNode); - } - } - } - } -} diff -r 610f9e377c70 -r 421e767d8038 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/FloatingReadPhase.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/FloatingReadPhase.java Mon Jul 16 11:07:07 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/FloatingReadPhase.java Tue Jul 17 20:07:00 2012 +0200 @@ -24,308 +24,269 @@ import java.util.*; -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.lir.cfg.*; +import com.oracle.graal.compiler.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.PhiNode.PhiType; import com.oracle.graal.nodes.extended.*; public class FloatingReadPhase extends Phase { - private static class MemoryMap { - private Block block; - private IdentityHashMap map; - private IdentityHashMap loopEntryMap; - private int mergeOperationCount; + private IdentityHashMap> loopEndStatesMap; - public MemoryMap(Block block) { - this.block = block; - map = new IdentityHashMap<>(); + private static class LoopState { + public LoopBeginNode loopBegin; + public MemoryMap state; + public IdentityHashMap loopPhiLocations = new IdentityHashMap<>(); + public ValueNode loopEntryAnyLocation; + public LoopState(LoopBeginNode loopBegin, MemoryMap state, ValueNode loopEntryAnyLocation) { + this.loopBegin = loopBegin; + this.state = state; + this.loopEntryAnyLocation = loopEntryAnyLocation; } - public MemoryMap(Block block, MemoryMap other) { - this(block); - map.putAll(other.map); + @Override + public String toString() { + return "State@" + loopBegin; + } + } + + private class MemoryMap implements MergeableState { + private IdentityHashMap lastMemorySnapshot; + private LinkedList loops; + + public MemoryMap(MemoryMap memoryMap) { + lastMemorySnapshot = new IdentityHashMap<>(memoryMap.lastMemorySnapshot); + loops = new LinkedList<>(memoryMap.loops); } - public void mergeLoopEntryWith(MemoryMap otherMemoryMap, LoopBeginNode begin, EndNode pred) { - for (Object keyInOther : otherMemoryMap.map.keySet()) { - assert loopEntryMap.containsKey(keyInOther) || map.get(keyInOther) == otherMemoryMap.map.get(keyInOther) : keyInOther + ", " + map.get(keyInOther) + " vs " + otherMemoryMap.map.get(keyInOther) + " " + begin; + public MemoryMap() { + lastMemorySnapshot = new IdentityHashMap<>(); + loops = new LinkedList<>(); + } + + @Override + public String toString() { + return "Map=" + lastMemorySnapshot.toString() + " Loops=" + loops.toString(); + } + + @Override + public boolean merge(MergeNode merge, List withStates) { + if (withStates.size() == 0) { + return true; } - for (Map.Entry entry : loopEntryMap.entrySet()) { - PhiNode phiNode = (PhiNode) entry.getValue(); - Object key = entry.getKey(); - Node other; - if (otherMemoryMap.map.containsKey(key)) { - other = otherMemoryMap.map.get(key); - } else { - other = otherMemoryMap.map.get(LocationNode.ANY_LOCATION); - } - - // this explicitly honors the phi input index, since the iteration order will not always adhere to the end index ordering. - // TODO(ls) check for instances of this problem in other places. - int index = begin.phiPredecessorIndex(pred); - phiNode.initializeValueAt(index, (ValueNode) other); - } - } - - public void mergeWith(MemoryMap otherMemoryMap, Block b) { - Debug.log("Merging block %s into block %s.", otherMemoryMap.block, block); - IdentityHashMap otherMap = otherMemoryMap.map; - - for (Map.Entry entry : map.entrySet()) { - if (otherMap.containsKey(entry.getKey())) { - mergeNodes(entry.getKey(), entry.getValue(), otherMap.get(entry.getKey()), b); - } else { - mergeNodes(entry.getKey(), entry.getValue(), otherMap.get(LocationNode.ANY_LOCATION), b); + int minLoops = loops.size(); + for (MemoryMap other : withStates) { + int otherLoops = other.loops.size(); + if (otherLoops < minLoops) { + minLoops = otherLoops; } } - - Node anyLocationNode = map.get(LocationNode.ANY_LOCATION); - for (Map.Entry entry : otherMap.entrySet()) { - if (!map.containsKey(entry.getKey())) { - Node current = anyLocationNode; - if (anyLocationNode instanceof PhiNode) { - PhiNode phiNode = (PhiNode) anyLocationNode; - if (phiNode.merge() == block.getBeginNode()) { - PhiNode phiCopy = (PhiNode) phiNode.copyWithInputs(); - phiCopy.removeInput(phiCopy.valueCount() - 1); - current = phiCopy; - map.put(entry.getKey(), current); - } - } - mergeNodes(entry.getKey(), current, entry.getValue(), b); + while (loops.size() > minLoops) { + loops.pop(); + } + for (MemoryMap other : withStates) { + while (other.loops.size() > minLoops) { + other.loops.pop(); } } - mergeOperationCount++; - } - - private void mergeNodes(Object location, Node original, Node newValue, Block mergeBlock) { - if (original == newValue) { - Debug.log("Nothing to merge both nodes are %s.", original); - return; + IdentityHashMap keys = new IdentityHashMap<>(); + for (Object key : lastMemorySnapshot.keySet()) { + keys.put(key, key); } - MergeNode m = (MergeNode) mergeBlock.getBeginNode(); - if (m.isPhiAtMerge(original)) { - PhiNode phi = (PhiNode) original; - phi.addInput((ValueNode) newValue); - Debug.log("Add new input to %s: %s.", original, newValue); - assert phi.valueCount() <= phi.merge().forwardEndCount() : phi.merge(); - } else { - PhiNode phi = m.graph().unique(new PhiNode(PhiType.Memory, m)); - // TODO(ls) how does this work? add documentation ... - for (int i = 0; i < mergeOperationCount + 1; ++i) { - phi.addInput((ValueNode) original); + for (MemoryMap other : withStates) { + assert other.loops.size() == loops.size(); + assert other.loops.size() < 1 || other.loops.peek().loopBegin == loops.peek().loopBegin; + for (Object key : other.lastMemorySnapshot.keySet()) { + keys.put(key, key); + } + } + + for (Object key : keys.keySet()) { + ValueNode merged = lastMemorySnapshot.get(key); + if (merged == null) { + merged = lastMemorySnapshot.get(LocationNode.ANY_LOCATION); } - phi.addInput((ValueNode) newValue); - Debug.log("Creating new %s merge=%s newValue=%s location=%s.", phi, phi.merge(), newValue, location); - assert phi.valueCount() <= phi.merge().forwardEndCount() + ((phi.merge() instanceof LoopBeginNode) ? 1 : 0) : phi.merge() + "/" + phi.valueCount() + "/" + phi.merge().forwardEndCount() + "/" + mergeOperationCount; - assert m.usages().contains(phi); - assert phi.merge().usages().contains(phi); - for (Node input : phi.inputs()) { - assert input.usages().contains(phi); + Iterator it = withStates.iterator(); + int i = 1; + boolean isPhi = false; + while (it.hasNext()) { + MemoryMap other = it.next(); + ValueNode otherValue = other.lastMemorySnapshot.get(key); + if (otherValue == null) { + otherValue = other.lastMemorySnapshot.get(LocationNode.ANY_LOCATION); + } + if (isPhi) { + ((PhiNode) merged).addInput(otherValue); + } else if (merged != otherValue) { + PhiNode phi = merge.graph().add(new PhiNode(PhiType.Memory, merge)); + for (int j = 0; j < i; j++) { + phi.addInput(merged); + } + phi.addInput(otherValue); + merged = phi; + isPhi = true; + lastMemorySnapshot.put(key, phi); + } + i++; } - map.put(location, phi); } - } - - public void processCheckpoint(MemoryCheckpoint checkpoint) { - map.clear(); - map.put(LocationNode.ANY_LOCATION, (Node) checkpoint); - } - - public void processWrite(WriteNode writeNode) { - if (writeNode.location().locationIdentity() == LocationNode.ANY_LOCATION) { - map.clear(); - } - map.put(writeNode.location().locationIdentity(), writeNode); + return true; } - public void processRead(ReadNode readNode) { - StructuredGraph graph = (StructuredGraph) readNode.graph(); - assert readNode.getNullCheck() == false; - - Debug.log("Register read to node %s.", readNode); - FloatingReadNode floatingRead; - if (readNode.location().locationIdentity() == LocationNode.FINAL_LOCATION) { - floatingRead = graph.unique(new FloatingReadNode(readNode.object(), readNode.location(), null, readNode.stamp(), readNode.dependencies())); - } else { - floatingRead = graph.unique(new FloatingReadNode(readNode.object(), readNode.location(), getLocationForRead(readNode), readNode.stamp(), readNode.dependencies())); + @Override + public void loopBegin(LoopBeginNode loopBegin) { + LoopState loopState = new LoopState(loopBegin, this, lastMemorySnapshot.get(LocationNode.ANY_LOCATION)); + for (Map.Entry entry : lastMemorySnapshot.entrySet()) { + PhiNode phi = loopBegin.graph().add(new PhiNode(PhiType.Memory, loopBegin)); + phi.addInput(entry.getValue()); + entry.setValue(phi); + loopState.loopPhiLocations.put(phi, entry.getKey()); } - floatingRead.setNullCheck(readNode.getNullCheck()); - ValueAnchorNode anchor = null; - for (GuardNode guard : readNode.dependencies().filter(GuardNode.class)) { - if (anchor == null) { - anchor = graph.add(new ValueAnchorNode()); - } - anchor.addAnchoredNode(guard); - } - if (anchor != null) { - graph.addAfterFixed(readNode, anchor); - } - graph.replaceFixedWithFloating(readNode, floatingRead); - } - - private Node getLocationForRead(ReadNode readNode) { - Object locationIdentity = readNode.location().locationIdentity(); - Node result = map.get(locationIdentity); - if (result == null) { - result = map.get(LocationNode.ANY_LOCATION); - } - return result; + loops.push(loopState); } - public void createLoopEntryMemoryMap(Set modifiedLocations, Loop loop) { - - loopEntryMap = new IdentityHashMap<>(); - - for (Object modifiedLocation : modifiedLocations) { - Node other; - if (map.containsKey(modifiedLocation)) { - other = map.get(modifiedLocation); - } else { - other = map.get(LocationNode.ANY_LOCATION); - } - createLoopEntryPhi(modifiedLocation, other, loop); - } - - if (modifiedLocations.contains(LocationNode.ANY_LOCATION)) { - for (Map.Entry entry : map.entrySet()) { - if (!modifiedLocations.contains(entry.getKey())) { - createLoopEntryPhi(entry.getKey(), entry.getValue(), loop); - } - } - } + @Override + public void loopEnds(LoopBeginNode loopBegin, List loopEndStates) { + loopEndStatesMap.put(loopBegin, loopEndStates); + tryFinishLoopPhis(this, loopBegin); } - private void createLoopEntryPhi(Object modifiedLocation, Node other, Loop loop) { - PhiNode phi = other.graph().unique(new PhiNode(PhiType.Memory, (MergeNode) loop.header.getBeginNode())); - phi.addInput((ValueNode) other); - map.put(modifiedLocation, phi); - loopEntryMap.put(modifiedLocation, phi); + @Override + public void afterSplit(FixedNode node) { + // nothing } - - public IdentityHashMap getLoopEntryMap() { - return loopEntryMap; + @Override + public MemoryMap clone() { + return new MemoryMap(this); } } @Override protected void run(StructuredGraph graph) { - - // Add start node write checkpoint. - addStartCheckpoint(graph); - - // Identify blocks. - ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); - Block[] blocks = cfg.getBlocks(); - - HashMap> modifiedValues = new HashMap<>(); - // Initialize modified values to empty hash set. - for (Loop loop : cfg.getLoops()) { - modifiedValues.put(loop, new HashSet<>()); - } - - // Get modified values in loops. - for (Node n : graph.getNodes()) { - Block block = cfg.blockFor(n); - if (block != null && block.getLoop() != null) { - if (n instanceof WriteNode) { - WriteNode writeNode = (WriteNode) n; - traceWrite(block.getLoop(), writeNode.location().locationIdentity(), modifiedValues); - } else if (n instanceof MemoryCheckpoint) { - traceMemoryCheckpoint(block.getLoop(), modifiedValues); - } + loopEndStatesMap = new IdentityHashMap<>(); + new PostOrderNodeIterator(graph.start(), new MemoryMap()) { + @Override + protected void node(FixedNode node) { + processNode(node, state); } - } - - // Propagate values to parent loops. - for (Loop loop : cfg.getLoops()) { - if (loop.depth == 1) { - propagateFromChildren(loop, modifiedValues); - } - } - - Debug.log("Modified values: %s.", modifiedValues); - - - // Process blocks (predecessors first). - MemoryMap[] memoryMaps = new MemoryMap[blocks.length]; - for (final Block b : blocks) { - processBlock(b, memoryMaps, cfg.getNodeToBlock(), modifiedValues); - } + }.apply(); } - private static void addStartCheckpoint(StructuredGraph graph) { - BeginNode entryPoint = graph.start(); - FixedNode next = entryPoint.next(); - if (!(next instanceof MemoryCheckpoint)) { - graph.addAfterFixed(entryPoint, graph.add(new WriteMemoryCheckpointNode())); + private void processNode(FixedNode node, MemoryMap state) { + if (node instanceof ReadNode) { + processRead((ReadNode) node, state); + } else if (node instanceof WriteNode) { + processWrite((WriteNode) node, state); + } else if (node instanceof MemoryCheckpoint) { + processCheckpoint((MemoryCheckpoint) node, state); + } else if (node instanceof LoopExitNode) { + processLoopExit((LoopExitNode) node, state); } } - private static void processBlock(Block b, MemoryMap[] memoryMaps, NodeMap nodeToBlock, HashMap> modifiedValues) { - // Create initial memory map for the block. - MemoryMap map = null; - if (b.getPredecessors().size() == 0) { - map = new MemoryMap(b); + private static void processCheckpoint(MemoryCheckpoint checkpoint, MemoryMap state) { + processAnyLocationWrite((ValueNode) checkpoint, state); + } + + private static void processWrite(WriteNode writeNode, MemoryMap state) { + if (writeNode.location().locationIdentity() == LocationNode.ANY_LOCATION) { + processAnyLocationWrite(writeNode, state); + } + state.lastMemorySnapshot.put(writeNode.location().locationIdentity(), writeNode); + } + + private static void processAnyLocationWrite(ValueNode modifiying, MemoryMap state) { + for (Map.Entry entry : state.lastMemorySnapshot.entrySet()) { + entry.setValue(modifiying); + } + state.lastMemorySnapshot.put(LocationNode.ANY_LOCATION, modifiying); + state.loops.clear(); + } + + private void processRead(ReadNode readNode, MemoryMap state) { + StructuredGraph graph = (StructuredGraph) readNode.graph(); + assert readNode.getNullCheck() == false; + Object locationIdentity = readNode.location().locationIdentity(); + ValueNode lastLocationAccess = getLastLocationAccessForRead(state, locationIdentity); + FloatingReadNode floatingRead = graph.unique(new FloatingReadNode(readNode.object(), readNode.location(), lastLocationAccess, readNode.stamp(), readNode.dependencies())); + floatingRead.setNullCheck(readNode.getNullCheck()); + ValueAnchorNode anchor = null; + for (GuardNode guard : readNode.dependencies().filter(GuardNode.class)) { + if (anchor == null) { + anchor = graph.add(new ValueAnchorNode()); + } + anchor.addAnchoredNode(guard); + } + if (anchor != null) { + graph.addAfterFixed(readNode, anchor); + } + graph.replaceFixedWithFloating(readNode, floatingRead); + } + + private ValueNode getLastLocationAccessForRead(MemoryMap state, Object locationIdentity) { + ValueNode lastLocationAccess; + if (locationIdentity == LocationNode.FINAL_LOCATION) { + lastLocationAccess = null; } else { - map = new MemoryMap(b, memoryMaps[b.getPredecessors().get(0).getId()]); - if (b.isLoopHeader()) { - Loop loop = b.getLoop(); - map.createLoopEntryMemoryMap(modifiedValues.get(loop), loop); + lastLocationAccess = state.lastMemorySnapshot.get(locationIdentity); + if (lastLocationAccess == null) { + LoopState lastLoop = state.loops.peek(); + if (lastLoop == null) { + lastLocationAccess = state.lastMemorySnapshot.get(LocationNode.ANY_LOCATION); + } else { + ValueNode phiInit; + if (state.loops.size() > 1) { + phiInit = getLastLocationAccessForRead(state.loops.get(1).state, locationIdentity); + } else { + phiInit = lastLoop.loopEntryAnyLocation; + } + PhiNode phi = lastLoop.loopBegin.graph().add(new PhiNode(PhiType.Memory, lastLoop.loopBegin)); + phi.addInput(phiInit); + lastLoop.state.lastMemorySnapshot.put(locationIdentity, phi); + lastLoop.loopPhiLocations.put(phi, locationIdentity); + tryFinishLoopPhis(lastLoop.state, lastLoop.loopBegin); + lastLocationAccess = phi; + } + state.lastMemorySnapshot.put(locationIdentity, lastLocationAccess); } - for (int i = 1; i < b.getPredecessors().size(); ++i) { - Block block = b.getPredecessors().get(i); - if (!block.isLoopEnd()) { - map.mergeWith(memoryMaps[block.getId()], b); + } + return lastLocationAccess; + } + + private static void processLoopExit(LoopExitNode exit, MemoryMap state) { + for (Map.Entry entry : state.lastMemorySnapshot.entrySet()) { + entry.setValue(exit.graph().unique(new ValueProxyNode(entry.getValue(), exit, PhiType.Memory))); + } + if (!state.loops.isEmpty()) { + state.loops.pop(); + } + } + + private void tryFinishLoopPhis(MemoryMap loopMemory, LoopBeginNode loopBegin) { + List loopEndStates = loopEndStatesMap.get(loopBegin); + if (loopEndStates == null) { + return; + } + LoopState loopState = loopMemory.loops.get(0); + int i = 0; + while (loopState.loopBegin != loopBegin) { + loopState = loopMemory.loops.get(++i); + } + for (PhiNode phi : loopBegin.phis()) { + if (phi.type() == PhiType.Memory && phi.valueCount() == 1) { + Object location = loopState.loopPhiLocations.get(phi); + assert location != null : "unknown location for " + phi; + for (MemoryMap endState : loopEndStates) { + ValueNode otherNode = endState.lastMemorySnapshot.get(location); + if (otherNode == null) { + otherNode = endState.lastMemorySnapshot.get(LocationNode.ANY_LOCATION); + } + phi.addInput(otherNode); } } } - memoryMaps[b.getId()] = map; - - // Process instructions of this block. - for (Node n : b.getNodes()) { - if (n instanceof ReadNode) { - ReadNode readNode = (ReadNode) n; - map.processRead(readNode); - } else if (n instanceof WriteNode) { - WriteNode writeNode = (WriteNode) n; - map.processWrite(writeNode); - } else if (n instanceof MemoryCheckpoint) { - MemoryCheckpoint checkpoint = (MemoryCheckpoint) n; - map.processCheckpoint(checkpoint); - } - } - - - if (b.getEndNode() instanceof LoopEndNode) { - LoopEndNode end = (LoopEndNode) b.getEndNode(); - LoopBeginNode begin = end.loopBegin(); - Block beginBlock = nodeToBlock.get(begin); - MemoryMap memoryMap = memoryMaps[beginBlock.getId()]; - assert memoryMap != null; - assert memoryMap.getLoopEntryMap() != null; - memoryMap.mergeLoopEntryWith(map, begin, (EndNode) b.getEndNode()); - } - } - - private static void traceMemoryCheckpoint(Loop loop, HashMap> modifiedValues) { - modifiedValues.get(loop).add(LocationNode.ANY_LOCATION); - } - - private void propagateFromChildren(Loop loop, HashMap> modifiedValues) { - for (Loop child : loop.children) { - propagateFromChildren(child, modifiedValues); - modifiedValues.get(loop).addAll(modifiedValues.get(child)); - } - } - - private static void traceWrite(Loop loop, Object locationIdentity, HashMap> modifiedValues) { - modifiedValues.get(loop).add(locationIdentity); } }