Mercurial > hg > graal-compiler
changeset 3081:0a5776813ff0
Loop peeling work
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Tue Jun 28 10:10:47 2011 +0200 @@ -24,6 +24,7 @@ import java.io.*; import java.util.*; +import java.util.AbstractMap.SimpleImmutableEntry; import java.util.Map.Entry; import com.oracle.max.graal.compiler.ir.*; @@ -109,10 +110,14 @@ flush(); } + public void print(Graph graph, String title, boolean shortNames) { + print(graph, title, shortNames, Collections.<String, Object>emptyMap()); + } + /** * Prints an entire {@link Graph} with the specified title, optionally using short names for nodes. */ - public void print(Graph graph, String title, boolean shortNames) { + public void print(Graph graph, String title, boolean shortNames, Map<String, Object> debugObjects) { stream.printf(" <graph name='%s'>%n", escape(title)); noBlockNodes.clear(); IdentifyBlocksPhase schedule = null; @@ -121,12 +126,12 @@ schedule.apply(graph); } catch (Throwable t) { // nothing to do here... - t.printStackTrace(); + //t.printStackTrace(); } List<Loop> loops = LoopUtil.computeLoops(graph); stream.println(" <nodes>"); - List<Edge> edges = printNodes(graph, shortNames, schedule == null ? null : schedule.getNodeToBlock(), loops); + List<Edge> edges = printNodes(graph, shortNames, schedule == null ? null : schedule.getNodeToBlock(), loops, debugObjects); stream.println(" </nodes>"); stream.println(" <edges>"); @@ -148,11 +153,50 @@ flush(); } - private List<Edge> printNodes(Graph graph, boolean shortNames, NodeMap<Block> nodeToBlock, List<Loop> loops) { + private List<Edge> printNodes(Graph graph, boolean shortNames, NodeMap<Block> nodeToBlock, List<Loop> loops, Map<String, Object> debugObjects) { ArrayList<Edge> edges = new ArrayList<Edge>(); NodeBitMap loopExits = graph.createNodeBitMap(); for (Loop loop : loops) { - loopExits.markAll(loop.exist()); + loopExits.setUnion(loop.exits()); + } + + Map<Node, Set<Entry<String, Integer>>> colors = new HashMap<Node, Set<Entry<String, Integer>>>(); + Map<Node, Set<String>> bits = new HashMap<Node, Set<String>>(); + if (debugObjects != null) { + for (Entry<String, Object> entry : debugObjects.entrySet()) { + String name = entry.getKey(); + Object obj = entry.getValue(); + if (obj instanceof NodeMap) { + Map<Object, Integer> colorNumbers = new HashMap<Object, Integer>(); + int nextColor = 0; + NodeMap<?> map = (NodeMap<?>) obj; + for (Entry<Node, ?> mapEntry : map.entries()) { + Node node = mapEntry.getKey(); + Object color = mapEntry.getValue(); + Integer colorNumber = colorNumbers.get(color); + if (colorNumber == null) { + colorNumber = nextColor++; + colorNumbers.put(color, colorNumber); + } + Set<Entry<String, Integer>> nodeColors = colors.get(node); + if (nodeColors == null) { + nodeColors = new HashSet<Entry<String, Integer>>(); + colors.put(node, nodeColors); + } + nodeColors.add(new SimpleImmutableEntry<String, Integer>(name + "Color", colorNumber)); + } + } else if (obj instanceof NodeBitMap) { + NodeBitMap bitmap = (NodeBitMap) obj; + for (Node node : bitmap) { + Set<String> nodeBits = bits.get(node); + if (nodeBits == null) { + nodeBits = new HashSet<String>(); + bits.put(node, nodeBits); + } + nodeBits.add(name); + } + } + } } for (Node node : graph.getNodes()) { @@ -199,6 +243,22 @@ if (sb.length() > 0) { stream.printf(" <p name='loops'>%s</p>%n", sb); } + + Set<Entry<String, Integer>> nodeColors = colors.get(node); + if (nodeColors != null) { + for (Entry<String, Integer> color : nodeColors) { + String name = color.getKey(); + Integer value = color.getValue(); + stream.printf(" <p name='%s'>%d</p>%n", name, value); + } + } + Set<String> nodeBits = bits.get(node); + if (nodeBits != null) { + for (String bit : nodeBits) { + stream.printf(" <p name='%s'>true</p>%n", bit); + } + } + for (Entry<Object, Object> entry : props.entrySet()) { String key = entry.getKey().toString(); String value = entry.getValue() == null ? "null" : entry.getValue().toString(); @@ -240,8 +300,9 @@ // if (sux.firstNode() instanceof LoopBegin && block.lastNode() instanceof LoopEnd) { //TODO gd // // Skip back edges. // } else { + if (sux != null) { stream.printf(" <successor name='%d'/>%n", sux.blockID()); -// } + } } stream.printf(" </successors>%n"); stream.printf(" <nodes>%n");
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java Tue Jun 28 10:10:47 2011 +0200 @@ -142,7 +142,7 @@ public void compilationEvent(CompilationEvent event) { if (printer != null && event.getGraph() != null && event.isHIRValid()) { Graph graph = event.getGraph(); - printer.print(graph, event.getLabel(), true); + printer.print(graph, event.getLabel(), true, event.getDebugObjects()); } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Tue Jun 28 10:10:47 2011 +0200 @@ -1464,6 +1464,9 @@ } private void moveToPhi(Merge merge, Node pred) { + if (GraalOptions.TraceLIRGeneratorLevel >= 1) { + TTY.println("MOVE TO PHI from " + pred + " to " + merge); + } int nextSuccIndex = merge.phiPredecessorIndex(pred); PhiResolver resolver = new PhiResolver(this); for (Phi phi : merge.phis()) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java Tue Jun 28 10:10:47 2011 +0200 @@ -22,6 +22,8 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.compiler.debug.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -67,4 +69,9 @@ assertTrue(predecessors().size() <= 1, "at most one predecessor"); return true; } + + @Override + public Iterable< ? extends Node> dataUsages() { + return Collections.emptyList(); + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Tue Jun 28 10:10:47 2011 +0200 @@ -83,6 +83,16 @@ throw Util.shouldNotReachHere("unknown pred : " + pred + "(sp=" + forwardEdge() + ", le=" + this.loopEnd() + ")"); } + @Override + public Node phiPredecessorAt(int index) { + if (index == 0) { + return forwardEdge(); + } else if (index == 1) { + return loopEnd(); + } + throw Util.shouldNotReachHere(); + } + public Collection<LoopCounter> counters() { return Util.filter(this.usages(), LoopCounter.class); } @@ -109,6 +119,12 @@ } @Override + public Node singlePredecessor() { + assert endCount() == 1; + return endAt(0).singlePredecessor(); + } + + @Override public Iterable< ? extends Node> dataUsages() { final Iterator< ? extends Node> dataUsages = super.dataUsages().iterator(); return new Iterable<Node>() {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java Tue Jun 28 10:10:47 2011 +0200 @@ -337,6 +337,10 @@ return endIndex(end); } + public Node phiPredecessorAt(int index) { + return endAt(index); + } + public Collection<Phi> phis() { return Util.filter(this.usages(), Phi.class); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Phi.java Tue Jun 28 10:10:47 2011 +0200 @@ -22,7 +22,10 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.ir.StateSplit.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -59,6 +62,7 @@ } public void setMerge(Merge n) { + assert n != null; inputs().set(super.inputCount() + INPUT_MERGE, n); } @@ -156,4 +160,16 @@ x.isDead = isDead; return x; } + + @Override + public Iterable<? extends Node> dataInputs() { + final Iterator< ? extends Node> input = super.dataInputs().iterator(); + return new Iterable<Node>() { + @Override + public Iterator<Node> iterator() { + // TODO Auto-generated method stub + return new FilteringIterator(input, Merge.class); + } + }; + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Value.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Value.java Tue Jun 28 10:10:47 2011 +0200 @@ -179,7 +179,7 @@ return properties; } - @Override + /*@Override public Iterable<? extends Node> dataUsages() { final Iterator<? extends Node> dataUsages = super.dataUsages().iterator(); return new Iterable<Node>() { @@ -188,5 +188,5 @@ return new StateSplit.FilteringIterator(dataUsages, FrameState.class); } }; - } + }*/ }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/observer/CompilationEvent.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/observer/CompilationEvent.java Tue Jun 28 10:10:47 2011 +0200 @@ -56,6 +56,7 @@ private Interval[] intervals; private int intervalsSize; private Interval[] intervalsCopy = null; + Map<String, Object> debugObjects; public CompilationEvent(GraalCompilation compilation) { this(compilation, null); @@ -74,6 +75,14 @@ this.lirValid = lirValid; } + public CompilationEvent(GraalCompilation compilation, String label, Graph graph, boolean hirValid, boolean lirValid, Map<String, Object> debugObjects) { + this(compilation, label); + this.graph = graph; + this.hirValid = hirValid; + this.lirValid = lirValid; + this.debugObjects = debugObjects; + } + public CompilationEvent(GraalCompilation compilation, String label, Graph graph, boolean hirValid, boolean lirValid, CiTargetMethod targetMethod) { this(compilation, label, graph, hirValid, lirValid); this.targetMethod = targetMethod; @@ -139,4 +148,9 @@ public int getCodeSize() { return codeSize; } + + + public Map<String, Object> getDebugObjects() { + return debugObjects; + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jun 28 10:10:47 2011 +0200 @@ -201,7 +201,7 @@ List<Loop> loops = LoopUtil.computeLoops(graph); NodeBitMap loopExits = graph.createNodeBitMap(); for (Loop loop : loops) { - loopExits.markAll(loop.exist()); + loopExits.setUnion(loop.exits()); } // remove Placeholders
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Tue Jun 28 10:10:47 2011 +0200 @@ -26,6 +26,7 @@ import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.util.*; +import com.oracle.max.graal.compiler.util.LoopUtil.Loop; import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -35,14 +36,21 @@ @Override protected void run(Graph graph) { - for (LoopBegin n : graph.getNodes(LoopBegin.class)) { - doLoop(n); + List<Loop> loops = LoopUtil.computeLoops(graph); + /* + for (Loop loop : loops) { + LoopUtil.peelLoop(loop); + } +// loops = LoopUtil.computeLoops(graph); // TODO (gd) avoid recomputing loops + */ + for (Loop loop : loops) { + doLoopCounters(loop); } } - private void doLoop(LoopBegin loopBegin) { - NodeBitMap loopNodes = LoopUtil.computeLoopNodes(loopBegin); - List<LoopCounter> counters = findLoopCounters(loopBegin, loopNodes); + private void doLoopCounters(Loop loop) { + LoopBegin loopBegin = loop.loopBegin(); + List<LoopCounter> counters = findLoopCounters(loopBegin, loop.nodes()); mergeLoopCounters(counters, loopBegin); } @@ -102,6 +110,9 @@ if (phi.valueCount() == 2) { Value backEdge = phi.valueAt(1); Value init = phi.valueAt(0); + if (loopNodes.isNew(init) || loopNodes.isNew(backEdge)) { + continue; + } if (loopNodes.isMarked(init)) { // try to reverse init/backEdge order Value tmp = backEdge; @@ -127,7 +138,7 @@ useCounterAfterAdd = true; } } - if (stride != null && !loopNodes.isMarked(stride)) { + if (stride != null && !loopNodes.isNew(stride) && !loopNodes.isMarked(stride)) { Graph graph = loopBegin.graph(); LoopCounter counter = new LoopCounter(init.kind, init, stride, loopBegin, graph); counters.add(counter);
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java Tue Jun 28 10:10:47 2011 +0200 @@ -0,0 +1,225 @@ +/* + * 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.util; + +import java.util.*; +import java.util.Map.Entry; + +import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.value.*; +import com.oracle.max.graal.graph.*; + +public class GraphUtil { + + public static interface ColoringLambda<T> { + T color(Iterable<T> incomming, Merge merge); + } + + /** + * colors down, applying the lambda at merge points, starting at the pre-colored points. + */ + public static <T> void colorCFGDown(NodeMap<T> colors, ColoringLambda<T> lambda) { + List<Node> startingPoints = new LinkedList<Node>(); + for (Entry<Node, T> entry : colors.entries()) { + startingPoints.add(entry.getKey()); + } + NodeWorkList work = colors.graph().createNodeWorkList(); + for (Node startingPoint : startingPoints) { + if (startingPoint instanceof Merge) { + work.addAll(colorCFGDownToMerge(((Merge) startingPoint).next(), colors.get(startingPoint), colors)); + } else { + work.addAll(colorCFGDownToMerge(startingPoint, colors.get(startingPoint), colors)); + } + } + for (Node n : work) { + //System.out.println("Color : work on " + n); + Merge merge = (Merge) n; + ArrayList<T> incomming = new ArrayList<T>(2); + for (EndNode end : merge.cfgPredecessors()) { + incomming.add(colors.get(end)); + } + T color = lambda.color(incomming, merge); + if (color != null) { + colors.set(merge, color); + work.addAll(colorCFGDownToMerge(merge.next(), color, colors)); + } else { + work.addAgain(merge); + } + } + } + + private static <T> Collection<Merge> colorCFGDownToMerge(Node from, T color, NodeMap<T> colors) { + //System.out.println("colorCFGDownToMerge(" + from + ", " + color + ", colors)"); + NodeFlood work = from.graph().createNodeFlood(); + Collection<Merge> merges = new LinkedList<Merge>(); + work.add(from); + for (Node node : work) { + //System.out.println("colorToMerge : work on " + node); + Node current = node; + while (current != null) { + //System.out.println("colorToMerge : current " + current); + if (current instanceof Merge) { + merges.add((Merge) current); + break; + } + colors.set(current, color); + if (current instanceof FixedNodeWithNext) { + current = ((FixedNodeWithNext) current).next(); + } else if (current instanceof EndNode) { + current = ((EndNode) current).merge(); + } else { + if (current instanceof ControlSplit) { + for (Node sux : current.cfgSuccessors()) { + work.add(sux); + } + } + current = null; + } + } + } + //System.out.println("return " + merges); + return merges; + } + + public static interface ColorSplitingLambda<T> { + void fixSplit(Node oldNode, Node newNode, T color); + void fixNode(Node node, T color); + boolean explore(Node n); + } + + // TODO (gd) handle FrameSate inputs/usages properly + public static <T> void splitFromColoring(NodeMap<T> coloring, ColorSplitingLambda<T> lambda) { + Map<Node, T> internalColoring = new HashMap<Node, T>(); + Queue<Node> work = new LinkedList<Node>(); + for (Entry<Node, T> entry : coloring.entries()) { + T color = entry.getValue(); + Node node = entry.getKey(); + work.offer(node); + internalColoring.put(node, color); + } + Set<T> colors = new HashSet<T>(); + while (!work.isEmpty()) { + Node node = work.poll(); + //System.out.println("Split : work on " + node); + boolean delay = false; + colors.clear(); + T originalColoringColor = coloring.get(node); + if (originalColoringColor == null && internalColoring.get(node) != null) { + //System.out.println("Split : ori == null && intern != null -> continue"); + continue; + } + if (originalColoringColor == null) { + for (Node usage : node.dataUsages()) { + if (usage instanceof Phi) { + Phi phi = (Phi) usage; + Merge merge = phi.merge(); + //System.out.println("Split merge : " + merge + ".endCount = " + merge.endCount() + " phi " + phi + ".valueCount : " + phi.valueCount()); + for (int i = 0; i < phi.valueCount(); i++) { + Value v = phi.valueAt(i); + if (v == node) { + T color = internalColoring.get(merge.phiPredecessorAt(i)); + if (color == null) { + //System.out.println("Split : color from " + usage + " is null"); + delay = true; + break; + } + colors.add(color); + } + } + } else { + T color = internalColoring.get(usage); + if (color == null) { + //System.out.println("Split : color from " + usage + " is null"); + delay = true; + break; + } + colors.add(color); + } + } + if (delay) { + //System.out.println("Split : delay"); + work.offer(node); + continue; + } + } else { + colors.add(originalColoringColor); + } + if (colors.size() == 1) { + //System.out.println("Split : 1 color, coloring, fixing"); + T color = colors.iterator().next(); + internalColoring.put(node, color); + lambda.fixNode(node, color); + } else { + //System.out.println("Split : " + colors.size() + " colors, coloring, spliting, fixing"); + for (T color : colors) { + Node newNode = node.copy(); + for (int i = 0; i < node.inputs().size(); i++) { + Node input = node.inputs().get(i); + newNode.inputs().setOrExpand(i, input); + } + for (int i = 0; i < node.successors().size(); i++) { + Node input = node.successors().get(i); + newNode.successors().setOrExpand(i, input); + } + internalColoring.put(newNode, color); + lambda.fixSplit(node, newNode, color); + for (Node usage : node.dataUsages()) { + if (usage instanceof Phi) { + Phi phi = (Phi) usage; + Merge merge = phi.merge(); + for (int i = 0; i < phi.valueCount(); i++) { + Value v = phi.valueAt(i); + if (v == node) { + T uColor = internalColoring.get(merge.endAt(i)); + if (uColor == color) { + phi.setValueAt(i, (Value) newNode); + } + } + } + } else { + T uColor = internalColoring.get(usage); + if (uColor == color) { + usage.inputs().replace(node, newNode); + } + } + } + } + } + + if (node instanceof StateSplit) { + FrameState stateAfter = ((StateSplit) node).stateAfter(); + if (stateAfter != null && lambda.explore(stateAfter)) { + //System.out.println("Split : Add framestate to work"); + work.offer(stateAfter); + } + } + + for (Node input : node.dataInputs()) { + if (lambda.explore(input) && coloring.get(input) == null) { + //System.out.println("Split : Add input " + input + " to work"); + work.offer(input); + } + } + } + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Tue Jun 28 10:10:47 2011 +0200 @@ -23,10 +23,17 @@ package com.oracle.max.graal.compiler.util; import java.util.*; +import java.util.Map.Entry; +import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.observer.*; import com.oracle.max.graal.compiler.schedule.*; +import com.oracle.max.graal.compiler.util.GraphUtil.ColorSplitingLambda; +import com.oracle.max.graal.compiler.util.GraphUtil.ColoringLambda; +import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; +import com.sun.cri.ci.*; public class LoopUtil { @@ -34,11 +41,11 @@ private final LoopBegin loopBegin; private final NodeBitMap nodes; private Loop parent; - private final List<FixedNode> exits; - public Loop(LoopBegin loopBegin, NodeBitMap nodes) { + private final NodeBitMap exits; + public Loop(LoopBegin loopBegin, NodeBitMap nodes, NodeBitMap exits) { this.loopBegin = loopBegin; this.nodes = nodes; - this.exits = new LinkedList<FixedNode>(); + this.exits = exits; } public LoopBegin loopBegin() { @@ -53,7 +60,7 @@ return parent; } - public List<FixedNode> exist() { + public NodeBitMap exits() { return exits; } @@ -62,11 +69,29 @@ } } + private static class PeelingResult { + public final FixedNode begin; + public final FixedNode end; + public final NodeMap<Placeholder> exits; + public final NodeMap<Placeholder> phis; + public final NodeMap<Node> phiInits; + public final NodeMap<Node> dataOut; + public PeelingResult(FixedNode begin, FixedNode end, NodeMap<Placeholder> exits, NodeMap<Placeholder> phis, NodeMap<Node> phiInits, NodeMap<Node> dataOut) { + this.begin = begin; + this.end = end; + this.exits = exits; + this.phis = phis; + this.phiInits = phiInits; + this.dataOut = dataOut; + } + } + public static List<Loop> computeLoops(Graph graph) { List<Loop> loops = new LinkedList<LoopUtil.Loop>(); for (LoopBegin loopBegin : graph.getNodes(LoopBegin.class)) { NodeBitMap nodes = computeLoopNodes(loopBegin); - Loop loop = new Loop(loopBegin, nodes); + NodeBitMap exits = graph.createNodeBitMap(); + Loop loop = new Loop(loopBegin, nodes, exits); NodeFlood workCFG = graph.createNodeFlood(); workCFG.add(loopBegin.loopEnd()); for (Node n : workCFG) { @@ -76,7 +101,7 @@ if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) { for (Node sux : n.cfgSuccessors()) { if (!nodes.isMarked(sux) && sux instanceof FixedNode) { - loop.exits.add((FixedNode) sux); + exits.mark(sux); } } } @@ -99,25 +124,17 @@ } public static NodeBitMap computeLoopNodes(LoopBegin loopBegin) { - LoopEnd loopEnd = loopBegin.loopEnd(); - NodeBitMap loopNodes = loopBegin.graph().createNodeBitMap(); - NodeFlood workCFG = loopBegin.graph().createNodeFlood(); + return computeLoopNodesFrom(loopBegin, loopBegin.loopEnd()); + } + + public static NodeBitMap computeLoopNodesFrom(LoopBegin loopBegin, FixedNode from) { NodeFlood workData1 = loopBegin.graph().createNodeFlood(); NodeFlood workData2 = loopBegin.graph().createNodeFlood(); - workCFG.add(loopEnd); - for (Node n : workCFG) { + NodeBitMap loopNodes = markUpCFG(loopBegin, from); + loopNodes.mark(loopBegin); + for (Node n : loopNodes) { workData1.add(n); workData2.add(n); - loopNodes.mark(n); - if (n == loopBegin) { - continue; - } - if (n instanceof LoopBegin) { - workCFG.add(((LoopBegin) n).loopEnd()); - } - for (Node pred : n.cfgPredecessors()) { - workCFG.add(pred); - } } NodeBitMap inOrAfter = loopBegin.graph().createNodeBitMap(); for (Node n : workData1) { @@ -138,8 +155,404 @@ } } } - inOrBefore.setIntersect(inOrAfter); - loopNodes.setUnion(inOrBefore); + inOrAfter.setIntersect(inOrBefore); + loopNodes.setUnion(inOrAfter); + return loopNodes; + } + + private static NodeBitMap markUpCFG(LoopBegin loopBegin, FixedNode from) { + NodeFlood workCFG = loopBegin.graph().createNodeFlood(); + workCFG.add(from); + NodeBitMap loopNodes = loopBegin.graph().createNodeBitMap(); + for (Node n : workCFG) { + if (n == loopBegin) { + continue; + } + loopNodes.mark(n); + if (n instanceof LoopBegin) { + workCFG.add(((LoopBegin) n).loopEnd()); + } + for (Node pred : n.cfgPredecessors()) { + workCFG.add(pred); + } + } return loopNodes; } + + public static void ifDoWhileTransform(Loop loop, If split) { + assert loop.nodes().isMarked(split); + FixedNode noExit = split.trueSuccessor(); + FixedNode exit = split.falseSuccessor(); + if (loop.nodes().isMarked(exit) && !loop.nodes().isMarked(noExit)) { + FixedNode tmp = noExit; + noExit = exit; + exit = tmp; + } + assert !loop.nodes().isMarked(exit); + assert loop.nodes().isMarked(noExit); + + PeelingResult peeling = preparePeeling(loop, split); + rewirePeeling(peeling, loop, split); + // TODO (gd) move peeled part to the end, rewire dataOut + } + + public static void peelLoop(Loop loop) { + LoopEnd loopEnd = loop.loopBegin().loopEnd(); + PeelingResult peeling = preparePeeling(loop, loopEnd); + GraalCompilation compilation = GraalCompilation.compilation(); + if (compilation.compiler.isObserved()) { + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After peeling preparation", loopEnd.graph(), true, false)); + } + /*System.out.println("Peeling : "); + System.out.println(" begin = " + peeling.begin); + System.out.println(" end = " + peeling.end); + System.out.println(" Phis :"); + for (Entry<Node, Placeholder> entry : peeling.phis.entries()) { + System.out.println(" - " + entry.getKey() + " -> " + entry.getValue()); + } + System.out.println(" Exits :"); + for (Entry<Node, Placeholder> entry : peeling.exits.entries()) { + System.out.println(" - " + entry.getKey() + " -> " + entry.getValue()); + } + System.out.println(" PhiInits :"); + for (Entry<Node, Node> entry : peeling.phiInits.entries()) { + System.out.println(" - " + entry.getKey() + " -> " + entry.getValue()); + } + System.out.println(" DataOut :"); + for (Entry<Node, Node> entry : peeling.dataOut.entries()) { + System.out.println(" - " + entry.getKey() + " -> " + entry.getValue()); + }*/ + rewirePeeling(peeling, loop, loopEnd); + if (compilation.compiler.isObserved()) { + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After rewirePeeling", loopEnd.graph(), true, false)); + } + } + + private static void rewirePeeling(PeelingResult peeling, Loop loop, FixedNode from) { + LoopBegin loopBegin = loop.loopBegin(); + Graph graph = loopBegin.graph(); + Node loopPred = loopBegin.singlePredecessor(); + if (loopPred instanceof FixedNodeWithNext) { + ((FixedNodeWithNext) loopPred).setNext(peeling.begin); + } else if (loopPred instanceof StartNode) { + ((StartNode) loopPred).setStart(peeling.begin); + } else { + Util.shouldNotReachHere(); + } + NodeBitMap loopNodes = loop.nodes(); + Node originalLast = from; + if (originalLast == loopBegin.loopEnd()) { + originalLast = loopBegin.loopEnd().singlePredecessor(); + } + int size = originalLast.successors().size(); + boolean found = false; + for (int i = 0; i < size; i++) { + Node sux = originalLast.successors().get(i); + if (sux == null) { + continue; + } + if (loopNodes.isMarked(sux)) { + assert !found; + peeling.end.successors().set(i, loopBegin.forwardEdge()); + found = true; + } + } + assert found; + int phiInitIndex = loopBegin.phiPredecessorIndex(loopBegin.forwardEdge()); + for (Entry<Node, Placeholder> entry : peeling.phis.entries()) { + Phi phi = (Phi) entry.getKey(); + Placeholder p = entry.getValue(); + p.replaceAndDelete(phi.valueAt(phiInitIndex)); + } + for (Entry<Node, Node> entry : peeling.phiInits.entries()) { + Phi phi = (Phi) entry.getKey(); + Node newInit = entry.getValue(); + phi.setValueAt(phiInitIndex, (Value) newInit); + } + + if (from == loopBegin.loopEnd()) { + for (LoopCounter counter : loopBegin.counters()) { + counter.setInit(new IntegerAdd(counter.kind, counter.init(), counter.stride(), graph)); + } + } + NodeMap<NodeMap<Value>> newExitValues = graph.createNodeMap(); + List<Node> exitPoints = new LinkedList<Node>(); + for (Node exit : loop.exits()) { + exitPoints.add(exit); + } + for (Entry<Node, Placeholder> entry : peeling.exits.entries()) { + Placeholder original = (Placeholder) entry.getKey(); + Placeholder newExit = entry.getValue(); + FixedNode next = original.next(); + EndNode oEnd = new EndNode(graph); + EndNode nEnd = new EndNode(graph); + Merge merge = new Merge(graph); + merge.setNext(next); + FrameState newState = newExit.stateAfter(); + merge.addEnd(nEnd); + merge.setStateAfter(newState); + //newState.merge(merge, original.stateAfter()); + merge.addEnd(oEnd); + original.setNext(oEnd); + newExit.setStateAfter(null); + newExit.replaceAndDelete(nEnd); + + exitPoints.remove(original); + exitPoints.add(oEnd); + exitPoints.add(nEnd); + } + + for (Entry<Node, Placeholder> entry : peeling.exits.entries()) { + Placeholder original = (Placeholder) entry.getKey(); + EndNode oEnd = (EndNode) original.next(); + Merge merge = oEnd.merge(); + EndNode nEnd = merge.endAt(1 - merge.phiPredecessorIndex(oEnd)); + FrameState newState = merge.stateAfter(); + NodeArray oInputs = original.stateAfter().inputs(); + NodeArray nInputs = newState.inputs(); + int oSize = oInputs.size(); + for (int i = 0; i < oSize; i++) { + Node newValue = nInputs.get(i); + Node originalValue = oInputs.get(i); + if (newValue != originalValue) { + NodeMap<Value> phiMap = newExitValues.get(originalValue); + if (phiMap == null) { + phiMap = graph.createNodeMap(); + newExitValues.set(originalValue, phiMap); + } + phiMap.set(oEnd, (Value) originalValue); + phiMap.set(nEnd, (Value) newValue); + + phiMap = newExitValues.get(newValue); + if (phiMap == null) { + phiMap = graph.createNodeMap(); + newExitValues.set(newValue, phiMap); + } + phiMap.set(oEnd, (Value) originalValue); + phiMap.set(nEnd, (Value) newValue); + } + } + /*Placeholder original = (Placeholder) entry.getKey(); + Merge merge = ((EndNode) original.next()).merge(); + FrameState newState = merge.stateAfter(); + NodeArray oInputs = original.stateAfter().inputs(); + NodeArray nInputs = newState.inputs(); + int oSize = oInputs.size(); + for (int i = 0; i < oSize; i++) { + Node newValue = nInputs.get(i); + Node originalValue = oInputs.get(i); + if (newValue != originalValue && newValue instanceof Phi) { + Phi newPhi = (Phi) newValue; + assert newPhi.valueAt(1) == originalValue; + NodeMap<Value> phiMap = newExitValues.get(originalValue); + if (phiMap == null) { + phiMap = graph.createNodeMap(); + newExitValues.set(originalValue, phiMap); + } + phiMap.set(merge, newPhi); + } + }*/ + } + for (Entry<Node, NodeMap<Value>> entry : newExitValues.entries()) { + Value original = (Value) entry.getKey(); + NodeMap<Value> pointToValue = entry.getValue(); + for (Node exit : exitPoints) { + Node valueAtExit = pointToValue.get(exit); + if (valueAtExit == null) { + pointToValue.set(exit, original); + } + } + } + + replaceValuesAtLoopExits(newExitValues, loop, exitPoints); + } + + private static void replaceValuesAtLoopExits(final NodeMap<NodeMap<Value>> newExitValues, Loop loop, List<Node> exitPoints) { + Graph graph = loop.loopBegin().graph(); + final NodeMap<Node> colors = graph.createNodeMap(); + + // prepare inital colors + for (Node exitPoint : exitPoints) { + colors.set(exitPoint, exitPoint); + } + + /*System.out.println("newExitValues"); + for (Entry<Node, NodeMap<Value>> entry : newExitValues.entries()) { + System.out.println(" - " + entry.getKey() + " :"); + for (Entry<Node, Value> entry2 : entry.getValue().entries()) { + System.out.println(" + " + entry2.getKey() + " -> " + entry2.getValue()); + } + }*/ + + // color + GraphUtil.colorCFGDown(colors, new ColoringLambda<Node>() { + @Override + public Node color(Iterable<Node> incomming, Merge merge) { + Node color = null; + for (Node c : incomming) { + if (c == null) { + return null; + } + if (color == null) { + color = c; + } else if (color != c) { + return merge; + } + } + return color; + } + }); + + final NodeBitMap inOrBefore = inOrBefore(loop); + + GraalCompilation compilation = GraalCompilation.compilation(); + if (compilation.compiler.isObserved()) { + Map<String, Object> debug = new HashMap<String, Object>(); + debug.put("loopExits", colors); + debug.put("inOrBefore", inOrBefore); + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After coloring", graph, true, false, debug)); + } + + // TODO (gd) handle Phi inputs properly : use the color from the corresponding EndNode + GraphUtil.splitFromColoring(colors, new ColorSplitingLambda<Node>(){ + @Override + public void fixSplit(Node oldNode, Node newNode, Node color) { + this.fixNode(newNode, color); + } + private Value getValueAt(Node point, NodeMap<Value> valueMap, CiKind kind) { + Value value = valueMap.get(point); + if (value != null) { + return value; + } + Merge merge = (Merge) point; + Phi phi = new Phi(kind, merge, merge.graph()); + valueMap.set(point, phi); + for (EndNode end : merge.cfgPredecessors()) { + phi.addInput(getValueAt(colors.get(end), valueMap, kind)); + } + return phi; + } + @Override + public boolean explore(Node n) { + return !inOrBefore.isNew(n) && !inOrBefore.isMarked(n) && !(n instanceof Local); //TODO (gd) hum + } + @Override + public void fixNode(Node node, Node color) { + for (int i = 0; i < node.inputs().size(); i++) { + Node input = node.inputs().get(i); + if (input == null || newExitValues.isNew(input)) { + continue; + } + NodeMap<Value> valueMap = newExitValues.get(input); + if (valueMap != null) { + Value replacement = getValueAt(color, valueMap, ((Value) input).kind); + //if (!(replacement instanceof Phi && replacement == node)) { // handle the Phi that were created when merging loop exits + node.inputs().set(i, replacement); + //} + } + } + }}); + + if (compilation.compiler.isObserved()) { + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After split from colors", graph, true, false)); + } + } + + private static PeelingResult preparePeeling(Loop loop, FixedNode from) { + LoopBegin loopBegin = loop.loopBegin(); + Graph graph = loopBegin.graph(); + NodeBitMap marked = computeLoopNodesFrom(loopBegin, from); + if (from == loopBegin.loopEnd()) { + marked.clear(from); + } + marked.clear(loopBegin); + Map<Node, Node> replacements = new HashMap<Node, Node>(); + NodeMap<Placeholder> phis = graph.createNodeMap(); + NodeMap<Placeholder> exits = graph.createNodeMap(); + + + for (Node exit : loop.exits()) { + if (marked.isMarked(exit.singlePredecessor())) { + marked.mark(((Placeholder) exit).stateAfter()); + Placeholder p = new Placeholder(graph); + replacements.put(exit, p); + exits.set(exit, p); + } + } + + for (Node n : marked) { + if (n instanceof StateSplit) { + FrameState stateAfter = ((StateSplit) n).stateAfter(); + if (stateAfter != null) { + marked.mark(stateAfter); + } + } + if (n instanceof Phi && ((Phi) n).merge() == loopBegin) { + Placeholder p = new Placeholder(graph); + replacements.put(n, p); + phis.set(n, p); + marked.clear(n); + } + for (Node input : n.dataInputs()) { + if (!marked.isMarked(input) && (!(input instanceof Phi) || ((Phi) input).merge() != loopBegin)) { + replacements.put(input, input); + } + } + } + + Map<Node, Node> duplicates = graph.addDuplicate(marked, replacements); + + GraalCompilation compilation = GraalCompilation.compilation(); + if (compilation.compiler.isObserved()) { + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After addDuplicate", graph, true, false)); + } + + NodeMap<Node> dataOut = graph.createNodeMap(); + for (Node n : marked) { + for (Node usage : n.dataUsages()) { + System.out.println("n = " + n + "; u= " + usage); + if (!marked.isMarked(usage) + && !loop.nodes().isNew(usage) && loop.nodes().isMarked(usage) + && !((usage instanceof Phi) || ((Phi) usage).merge() != loopBegin)) { + dataOut.set(n, duplicates.get(n)); + break; + } + } + } + NodeMap<Node> phiInits = graph.createNodeMap(); + int backIndex = loopBegin.phiPredecessorIndex(loopBegin.loopEnd()); + int fowardIndex = loopBegin.phiPredecessorIndex(loopBegin.forwardEdge()); + for (Phi phi : loopBegin.phis()) { + Value backValue = phi.valueAt(backIndex); + if (marked.isMarked(backValue)) { + phiInits.set(phi, duplicates.get(backValue)); + } else if (backValue instanceof Phi && ((Phi) backValue).merge() == loopBegin) { + Phi backPhi = (Phi) backValue; + phiInits.set(phi, backPhi.valueAt(fowardIndex)); + } + } + + FixedNode newBegin = (FixedNode) duplicates.get(loopBegin.next()); + FixedNode newFrom = (FixedNode) duplicates.get(from == loopBegin.loopEnd() ? from.singlePredecessor() : from); + return new PeelingResult(newBegin, newFrom, exits, phis, phiInits, dataOut); + } + + private static NodeBitMap inOrBefore(Loop loop) { + Graph graph = loop.loopBegin().graph(); + NodeBitMap inOrBefore = graph.createNodeBitMap(); + NodeFlood work = graph.createNodeFlood(); + work.addAll(loop.nodes()); + for (Node n : work) { + inOrBefore.mark(n); + for (Node pred : n.predecessors()) { + work.add(pred); + } + for (Node in : n.inputs()) { + if (in != null) { + work.add(in); + } + } + } + return inOrBefore; + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java Fri Jun 24 15:01:20 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java Tue Jun 28 10:10:47 2011 +0200 @@ -420,6 +420,15 @@ return null; } + public StateSplit stateSplit() { + for (Node n : usages()) { + if (n instanceof StateSplit) { + return (StateSplit) n; + } + } + return null; + } + /** * The interface implemented by a client of {@link FrameState#forEachPhi(Merge, PhiProcedure)} and * {@link FrameState#forEachLivePhi(Merge, PhiProcedure)}. @@ -467,7 +476,7 @@ @Override public String toString() { - StringBuilder sb = new StringBuilder(); + /*StringBuilder sb = new StringBuilder(); String nl = String.format("%n"); sb.append("[bci: ").append(bci).append("]").append(nl); for (int i = 0; i < localsSize(); ++i) { @@ -482,7 +491,8 @@ Value value = lockAt(i); sb.append(String.format(" lock[%d] = %-8s : %s%n", i, value == null ? "bogus" : value.kind.javaName, value)); } - return sb.toString(); + return sb.toString();*/ + return super.toString(); } @Override
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/GraalColoringFilter.java Tue Jun 28 10:10:47 2011 +0200 @@ -0,0 +1,79 @@ +/* + * 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.sun.hotspot.igv.graal.filters; + +import com.sun.hotspot.igv.data.Properties; +import com.sun.hotspot.igv.filter.AbstractFilter; +import com.sun.hotspot.igv.graph.Diagram; +import com.sun.hotspot.igv.graph.Figure; +import java.awt.Color; +import java.util.List; + +public class GraalColoringFilter extends AbstractFilter { + + private String colorName; + + public GraalColoringFilter(String colorName) { + this.colorName = colorName; + } + + public String getName() { + return "Graal Coloring Filter (" + colorName + ")"; + } + + public void apply(Diagram d) { + List<Figure> figures = d.getFigures(); + int colors = 0; + for (Figure f : figures) { + Properties p = f.getProperties(); + final String prop = p.get(colorName + "Color"); + if (prop == null) { + continue; + } + try { + int color = Integer.parseInt(prop); + if (color > colors) { + colors = color; + } + } catch (NumberFormatException nfe) { + // nothing to do + } + } + colors++; + for (Figure f : figures) { + Properties p = f.getProperties(); + final String prop = p.get(colorName + "Color"); + if (prop == null) { + continue; + } + try { + int color = Integer.parseInt(prop); + Color c = Color.getHSBColor((float) color / colors, 1.0f, 0.7f); + f.setColor(c); + } catch (NumberFormatException nfe) { + // nothing to do + } + } + } +}
--- a/src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/color.filter Fri Jun 24 15:01:20 2011 +0200 +++ b/src/share/tools/IdealGraphVisualizer/Graal/src/com/sun/hotspot/igv/graal/filters/color.filter Tue Jun 28 10:10:47 2011 +0200 @@ -1,9 +1,11 @@ colorize("name", ".*", white); -colorize("name", "StartNode|EndNode|LoopBegin|LoopEnd|Return", red); +colorize("name", "StartNode|EndNode|LoopBegin|LoopEnd|Return", orange); colorize("name", "Phi:.*", magenta); colorize("name", "FrameState@.*", new java.awt.Color(0.5, 0.8, 1.0)); colorize("name", "If", pink); colorize("name", "const.*", new java.awt.Color(0.7, 0.7, 0.7)); colorize("name", "Local", new java.awt.Color(0.85, 0.85, 0.85)); colorize("name", "\\+|-|\\*|/", cyan); -colorize("name", "Comp .*", yellow); \ No newline at end of file +colorize("name", "Comp .*", yellow); + +colorize("notInOwnBlock", "true", red); \ No newline at end of file