# HG changeset patch # User Thomas Wuerthinger # Date 1309174193 -7200 # Node ID 3ada297d75ed8bcb72c3edac8affad5c0b55ba28 # Parent 45ba159b4bd1d6d36dc4ec7d0e6e06c060f6bdb5 Towards new memory dependence graph. diff -r 45ba159b4bd1 -r 3ada297d75ed graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/AbstractMemoryCheckpointNode.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/AbstractMemoryCheckpointNode.java Fri Jun 24 15:39:54 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/AbstractMemoryCheckpointNode.java Mon Jun 27 13:29:53 2011 +0200 @@ -41,6 +41,13 @@ super(result, inputCount + INPUT_COUNT, successorCount + SUCCESSOR_COUNT, graph); } + @Override + public Map getDebugProperties() { + Map debugProperties = super.getDebugProperties(); + debugProperties.put("memoryCheckpoint", "true"); + return debugProperties; + } + public List mergedNodes() { return inputs().variablePart(); } diff -r 45ba159b4bd1 -r 3ada297d75ed graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/AccessNode.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/AccessNode.java Fri Jun 24 15:39:54 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/AccessNode.java Mon Jun 27 13:29:53 2011 +0200 @@ -27,7 +27,7 @@ import com.sun.cri.ci.*; -public abstract class AccessNode extends StateSplit { +public abstract class AccessNode extends AbstractMemoryCheckpointNode { private static final int INPUT_COUNT = 3; private static final int INPUT_NODE = 0; private static final int INPUT_LOCATION = 1; diff -r 45ba159b4bd1 -r 3ada297d75ed graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MemoryCheckpointNode.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MemoryCheckpointNode.java Fri Jun 24 15:39:54 2011 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,55 +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.max.graal.compiler.ir; - -import com.oracle.max.graal.compiler.gen.*; -import com.oracle.max.graal.graph.*; -import com.sun.cri.ci.*; - - -public final class MemoryCheckpointNode extends AbstractMemoryCheckpointNode { - - private static final int SUCCESSOR_COUNT = 0; - private static final int INPUT_COUNT = 0; - - public MemoryCheckpointNode(Graph graph) { - this(CiKind.Illegal, 0, 0, graph); - } - - public MemoryCheckpointNode(CiKind result, int inputCount, int successorCount, Graph graph) { - super(result, inputCount + INPUT_COUNT, successorCount + SUCCESSOR_COUNT, graph); - } - - @Override - public T lookup(Class clazz) { - if (clazz == LIRGenerator.LIRGeneratorOp.class) { - return null; - } - return super.lookup(clazz); - } - - @Override - public Node copy(Graph into) { - return new MemoryCheckpointNode(into); - } -} diff -r 45ba159b4bd1 -r 3ada297d75ed graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/WriteMemoryCheckpointNode.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/WriteMemoryCheckpointNode.java Mon Jun 27 13:29:53 2011 +0200 @@ -0,0 +1,55 @@ +/* + * 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.max.graal.compiler.ir; + +import com.oracle.max.graal.compiler.gen.*; +import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; + + +public final class WriteMemoryCheckpointNode extends AbstractMemoryCheckpointNode { + + private static final int SUCCESSOR_COUNT = 0; + private static final int INPUT_COUNT = 0; + + public WriteMemoryCheckpointNode(Graph graph) { + this(CiKind.Illegal, 0, 0, graph); + } + + public WriteMemoryCheckpointNode(CiKind result, int inputCount, int successorCount, Graph graph) { + super(result, inputCount + INPUT_COUNT, successorCount + SUCCESSOR_COUNT, graph); + } + + @Override + public T lookup(Class clazz) { + if (clazz == LIRGenerator.LIRGeneratorOp.class) { + return null; + } + return super.lookup(clazz); + } + + @Override + public Node copy(Graph into) { + return new WriteMemoryCheckpointNode(into); + } +} diff -r 45ba159b4bd1 -r 3ada297d75ed graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/MemoryPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/MemoryPhase.java Fri Jun 24 15:39:54 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/MemoryPhase.java Mon Jun 27 13:29:53 2011 +0200 @@ -30,6 +30,7 @@ import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.schedule.*; import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; public class MemoryPhase extends Phase { @@ -40,9 +41,18 @@ private HashMap> locationToReads; private Node lastReadWriteMerge; private Node lastWriteMerge; + private int mergeOperations; public MemoryMap(Block b, MemoryMap memoryMap) { this(b); + for (Entry e : memoryMap.locationToWrite.entrySet()) { + locationToWrite.put(e.getKey(), e.getValue()); + } + for (Entry> e : memoryMap.locationToReads.entrySet()) { + locationToReads.put(e.getKey(), new ArrayList(e.getValue())); + } + lastReadWriteMerge = memoryMap.lastReadWriteMerge; + lastWriteMerge = memoryMap.lastWriteMerge; } public MemoryMap(Block b) { @@ -52,15 +62,70 @@ if (GraalOptions.TraceMemoryMaps) { TTY.println("Creating new memory map for block B" + b.blockID()); } - assert b.firstNode() == b.firstNode().graph().start(); - lastReadWriteMerge = b.firstNode(); - lastWriteMerge = b.firstNode(); + StartNode startNode = b.firstNode().graph().start(); + if (b.firstNode() == startNode) { + WriteMemoryCheckpointNode checkpoint = new WriteMemoryCheckpointNode(startNode.graph()); + checkpoint.setNext((FixedNode) startNode.start()); + startNode.setStart(checkpoint); + lastReadWriteMerge = checkpoint; + lastWriteMerge = checkpoint; + } } public void mergeWith(MemoryMap memoryMap) { if (GraalOptions.TraceMemoryMaps) { TTY.println("Merging with memory map of block B" + memoryMap.block.blockID()); } + + lastReadWriteMerge = mergeNodes(lastReadWriteMerge, memoryMap.lastReadWriteMerge); + lastWriteMerge = mergeNodes(lastWriteMerge, memoryMap.lastWriteMerge); + + List toRemove = new ArrayList(); + for (Entry e : locationToWrite.entrySet()) { + if (memoryMap.locationToWrite.containsKey(e.getKey())) { + if (GraalOptions.TraceMemoryMaps) { + TTY.println("Merging entries for location " + e.getKey()); + } + locationToWrite.put(e.getKey(), mergeNodes(e.getValue(), memoryMap.locationToWrite.get(e.getKey()))); + } else { + toRemove.add(e.getKey()); + } + } + + for (Object o : toRemove) { + locationToWrite.remove(o); + } + + for (Entry> e : memoryMap.locationToReads.entrySet()) { + for (Node n : e.getValue()) { + addRead(n, e.getKey()); + } + } + + mergeOperations++; + } + + private Node mergeNodes(Node original, Node newValue) { + if (original == newValue) { + // Nothing to merge. + if (GraalOptions.TraceMemoryMaps) { + TTY.println("Nothing to merge both nodes are " + original.id()); + } + return original; + } + Merge m = (Merge) block.firstNode(); + if (original instanceof Phi && ((Phi) original).merge() == m) { + ((Phi) original).addInput(newValue); + return original; + } else { + Phi phi = new Phi(CiKind.Illegal, m, m.graph()); + phi.makeDead(); // Phi does not produce a value, it is only a memory phi. + for (int i = 0; i < mergeOperations + 1; ++i) { + phi.addInput(original); + } + phi.addInput(newValue); + return phi; + } } public void createWriteMemoryMerge(AbstractMemoryCheckpointNode memMerge) { @@ -107,7 +172,7 @@ boolean connectionAdded = false; if (locationToReads.containsKey(location)) { for (Node prevRead : locationToReads.get(location)) { - node.inputs().add(prevRead); + node.inputs().variablePart().add(prevRead); connectionAdded = true; } } @@ -143,7 +208,7 @@ node.inputs().variablePart().add(lastReadWriteMerge); } - addRead(node, location); + //addRead(node, location); } private void addRead(Node node, Object location) { @@ -184,23 +249,20 @@ } else { map = new MemoryMap(b, memoryMaps[b.getPredecessors().get(0).blockID()]); for (int i = 1; i < b.getPredecessors().size(); ++i) { - map.mergeWith(memoryMaps[b.getPredecessors().get(0).blockID()]); + map.mergeWith(memoryMaps[b.getPredecessors().get(i).blockID()]); } } - // Lower the instructions of this block. + // Create the floating memory checkpoint instructions. for (final Node n : b.getInstructions()) { - // This memory merge node is not lowered => create a memory merge nevertheless. - if (n instanceof AbstractMemoryCheckpointNode) { - map.createReadWriteMemoryCheckpoint((AbstractMemoryCheckpointNode) n); - } else if (n instanceof ReadNode) { + if (n instanceof ReadNode) { ReadNode readNode = (ReadNode) n; readNode.replaceAtPredecessors(readNode.next()); readNode.setNext(null); map.registerRead(readNode); } else if (n instanceof WriteNode) { WriteNode writeNode = (WriteNode) n; - MemoryCheckpointNode checkpoint = new MemoryCheckpointNode(writeNode.graph()); + WriteMemoryCheckpointNode checkpoint = new WriteMemoryCheckpointNode(writeNode.graph()); checkpoint.setStateAfter(writeNode.stateAfter()); writeNode.setStateAfter(null); checkpoint.setNext(writeNode.next()); @@ -208,6 +270,8 @@ writeNode.replaceAtPredecessors(checkpoint); map.registerWrite(writeNode); map.createWriteMemoryMerge(checkpoint); + } else if (n instanceof AbstractMemoryCheckpointNode) { + map.createReadWriteMemoryCheckpoint((AbstractMemoryCheckpointNode) n); } } diff -r 45ba159b4bd1 -r 3ada297d75ed graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Fri Jun 24 15:39:54 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Mon Jun 27 13:29:53 2011 +0200 @@ -74,10 +74,9 @@ if (b.lastNode() == null) { b.setFirstNode(n); b.setLastNode(n); + b.getInstructions().add(n); } else { - if (b.firstNode() != b.lastNode()) { - b.getInstructions().add(0, b.firstNode()); - } + b.getInstructions().add(0, n); b.setFirstNode(n); } @@ -321,15 +320,15 @@ List sortedInstructions = new ArrayList(instructions.size() + 2); assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b; - assert !instructions.contains(b.firstNode()); - assert !instructions.contains(b.lastNode()); +// assert !instructions.contains(b.firstNode()); +// assert !instructions.contains(b.lastNode()); assert !map.isMarked(b.lastNode()) && nodeToBlock.get(b.lastNode()) == b; - addToSorting(b, b.firstNode(), sortedInstructions, map); + //addToSorting(b, b.firstNode(), sortedInstructions, map); for (Node i : instructions) { addToSorting(b, i, sortedInstructions, map); } - addToSorting(b, b.lastNode(), sortedInstructions, map); + //addToSorting(b, b.lastNode(), sortedInstructions, map); // Make sure that last node gets really last (i.e. when a frame state successor hangs off it). Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1); @@ -351,6 +350,11 @@ } } b.setInstructions(sortedInstructions); +// TTY.println(); +// TTY.println("B" + b.blockID()); +// for (Node n : sortedInstructions) { +// TTY.println("n=" + n); +// } } private void addToSorting(Block b, Node i, List sortedInstructions, NodeBitMap map) { @@ -358,9 +362,19 @@ return; } + if (i instanceof WriteNode) { + // Make sure every ReadNode that is connected to the same memory state is executed before every write node. + WriteNode wn = (WriteNode) i; + // TODO: Iterate over variablePart. + wn.inputs().variablePart(); + } + FrameState state = null; + WriteNode writeNode = null; for (Node input : i.inputs()) { - if (input instanceof FrameState) { + if (input instanceof WriteNode && !map.isMarked(input) && nodeToBlock.get(input) == b) { + writeNode = (WriteNode) input; + } else if (input instanceof FrameState) { state = (FrameState) input; } else { addToSorting(b, input, sortedInstructions, map); @@ -373,20 +387,12 @@ map.mark(i); - for (Node succ : i.successors()) { - if (succ instanceof FrameState) { - addToSorting(b, succ, sortedInstructions, map); - } - } - - if (state != null) { - addToSorting(b, state, sortedInstructions, map); - } + addToSorting(b, state, sortedInstructions, map); + assert writeNode == null || !map.isMarked(writeNode); + addToSorting(b, writeNode, sortedInstructions, map); // Now predecessors and inputs are scheduled => we can add this node. - if (!(i instanceof FrameState)) { - sortedInstructions.add(i); - } + sortedInstructions.add(i); } private void computeDominators() { diff -r 45ba159b4bd1 -r 3ada297d75ed graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotRuntime.java --- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotRuntime.java Fri Jun 24 15:39:54 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotRuntime.java Mon Jun 27 13:29:53 2011 +0200 @@ -266,10 +266,6 @@ memoryWrite.setGuard((GuardNode) tool.createGuard(new IsNonNull(field.object(), graph))); memoryWrite.setStateAfter(field.stateAfter()); memoryWrite.setNext(field.next()); - - //MemoryMergeNode memoryMergeNode = new MemoryMergeNode(graph); - //memoryMergeNode.setStateAfter(field.stateAfter()); - //tool.createMemoryMerge(memoryMergeNode); if (field.field().kind() == CiKind.Object && !field.value().isNullConstant()) { FieldWriteBarrier writeBarrier = new FieldWriteBarrier(field.object(), graph); memoryWrite.setNext(writeBarrier); diff -r 45ba159b4bd1 -r 3ada297d75ed src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/GraalEdgeColorFilter.java --- a/src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/GraalEdgeColorFilter.java Fri Jun 24 15:39:54 2011 +0200 +++ b/src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/GraalEdgeColorFilter.java Mon Jun 27 13:29:53 2011 +0200 @@ -28,6 +28,7 @@ import com.sun.hotspot.igv.graph.Connection; import com.sun.hotspot.igv.graph.Diagram; import com.sun.hotspot.igv.graph.Figure; +import com.sun.hotspot.igv.graph.InputSlot; import com.sun.hotspot.igv.graph.OutputSlot; import java.awt.Color; import java.util.List; @@ -39,8 +40,9 @@ */ public class GraalEdgeColorFilter extends AbstractFilter { - private Color successorColor = Color.ORANGE; + private Color successorColor = Color.BLUE; private Color usageColor = Color.RED; + private Color memoryColor = Color.GREEN; public GraalEdgeColorFilter() { } @@ -53,7 +55,6 @@ List
figures = d.getFigures(); for (Figure f : figures) { Properties p = f.getProperties(); - int succCount = Integer.parseInt(p.get("successorCount")); for (OutputSlot os : f.getOutputSlots()) { Color color; @@ -69,6 +70,22 @@ } } } + for (Figure f : figures) { + Properties p = f.getProperties(); + int predCount = Integer.parseInt(p.get("predecessorCount")); + int inputCount = Integer.parseInt(p.get("inputCount")); + int variableInputCount = Integer.parseInt(p.get("variableInputCount")); + if (p.get("memoryCheckpoint") != null) { + for (InputSlot is : f.getInputSlots()) { + if (is.getPosition() > predCount + inputCount - variableInputCount) { + is.setColor(memoryColor); + for (Connection c : is.getConnections()) { + c.setColor(memoryColor); + } + } + } + } + } } public Color getUsageColor() { @@ -78,7 +95,15 @@ public void setUsageColor(Color usageColor) { this.usageColor = usageColor; } + + public void setMemoryColor(Color memoryColor) { + this.memoryColor = memoryColor; + } + public Color getMemoryColor() { + return memoryColor; + } + public Color getSuccessorColor() { return successorColor; }