Mercurial > hg > graal-compiler
changeset 3110:883c2f14e7d0
Fixed various peeling bugs (can use nodes which are not Placeholders as loop exits)
author | Gilles Duboscq <gilles.duboscq@oracle.com> |
---|---|
date | Fri, 01 Jul 2011 18:37:54 +0200 |
parents | 3664989976e2 |
children | c3573103764e |
files | graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalMetrics.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java src/share/tools/IdealGraphVisualizer/Coordinator/src/com/sun/hotspot/igv/coordinator/StandardGroupOrganizer.java |
diffstat | 5 files changed, 90 insertions(+), 77 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalMetrics.java Fri Jul 01 12:57:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalMetrics.java Fri Jul 01 18:37:54 2011 +0200 @@ -62,6 +62,7 @@ public static int FrameStatesCreated; public static int FrameStateValuesCreated; public static int NodesCanonicalized; + public static int LoopsPeeled; public static void print() { for (Entry<String, GraalMetrics> m : map.entrySet()) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Fri Jul 01 12:57:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Fri Jul 01 18:37:54 2011 +0200 @@ -151,4 +151,5 @@ public static boolean OptCanonicalizer = true; public static boolean OptLoops = true; + public static boolean LoopPeeling = ____; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Fri Jul 01 12:57:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Fri Jul 01 18:37:54 2011 +0200 @@ -24,6 +24,7 @@ import java.util.*; +import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.compiler.util.LoopUtil.Loop; @@ -38,14 +39,24 @@ protected void run(Graph graph) { List<Loop> loops = LoopUtil.computeLoops(graph); -// for (Loop loop : loops) { -// System.out.println("Peel loop : " + loop.loopBegin()); -// LoopUtil.peelLoop(loop); -// } -// loops = LoopUtil.computeLoops(graph); // TODO (gd) avoid recomputing loops - - for (Loop loop : loops) { - doLoopCounters(loop); + // TODO (gd) currently counter detection is disabled when loop peeling is active + if (GraalOptions.LoopPeeling) { +peeling: + for (Loop loop : loops) { + // System.out.println("Peel loop : " + loop.loopBegin()); + for (Node exit : loop.exits()) { + if (!(exit instanceof StateSplit) || ((StateSplit) exit).stateAfter() == null) { + // TODO (gd) can not do loop peeling if an exit has no state. see LoopUtil.findNearestMergableExitPoint + continue peeling; + } + } + LoopUtil.peelLoop(loop); + } + } else { +// loops = LoopUtil.computeLoops(graph); // TODO (gd) avoid recomputing loops + for (Loop loop : loops) { + doLoopCounters(loop); + } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Fri Jul 01 12:57:10 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Fri Jul 01 18:37:54 2011 +0200 @@ -76,17 +76,19 @@ private static class PeelingResult { public final FixedNode begin; public final FixedNode end; - public final NodeMap<Placeholder> exits; + public final NodeMap<StateSplit> exits; + public final NodeBitMap unaffectedExits; 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) { + public PeelingResult(FixedNode begin, FixedNode end, NodeMap<StateSplit> exits, NodeMap<Placeholder> phis, NodeMap<Node> phiInits, NodeMap<Node> dataOut, NodeBitMap unaffectedExits) { this.begin = begin; this.end = end; this.exits = exits; this.phis = phis; this.phiInits = phiInits; this.dataOut = dataOut; + this.unaffectedExits = unaffectedExits; } } @@ -230,7 +232,7 @@ return loopNodes; } - public static void ifDoWhileTransform(Loop loop, If split) { + public static void inverseLoop(Loop loop, If split) { assert loop.nodes().isMarked(split); FixedNode noExit = split.trueSuccessor(); FixedNode exit = split.falseSuccessor(); @@ -284,6 +286,7 @@ parent.exits = computeLoopExits(parent.loopBegin, parent.nodes); parent = parent.parent; } + GraalMetrics.LoopsPeeled++; } private static void rewirePeeling(PeelingResult peeling, Loop loop, FixedNode from) { @@ -329,79 +332,64 @@ } NodeMap<NodeMap<Value>> newExitValues = graph.createNodeMap(); List<Node> exitPoints = new LinkedList<Node>(); - for (Node exit : loop.exits()) { + for (Node exit : peeling.unaffectedExits) { exitPoints.add(exit); } - for (Entry<Node, Placeholder> entry : peeling.exits.entries()) { - Placeholder original = (Placeholder) entry.getKey(); - Placeholder newExit = entry.getValue(); - FixedNode next = original.next(); + for (Entry<Node, StateSplit> entry : peeling.exits.entries()) { + StateSplit original = (StateSplit) entry.getKey(); + StateSplit newExit = entry.getValue(); 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); + merge.setStateAfter(newState.duplicate(newState.bci)); + merge.setNext(original.next()); original.setNext(oEnd); - newExit.setStateAfter(null); - newExit.replaceAndDelete(nEnd); - - exitPoints.add(nEnd); + newExit.setNext(nEnd); + exitPoints.add(original); + exitPoints.add(newExit); } - for (Entry<Node, Placeholder> entry : peeling.exits.entries()) { - Placeholder original = (Placeholder) entry.getKey(); + for (Entry<Node, StateSplit> entry : peeling.exits.entries()) { + StateSplit original = (StateSplit) 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(original, (Value) originalValue); - phiMap.set(nEnd, (Value) newValue); + FrameState originalState = original.stateAfter(); + while (newState != null) { + assert originalState != null; + NodeArray oInputs = originalState.inputs(); + NodeArray nInputs = newState.inputs(); + int oSize = oInputs.size(); + for (int i = 1; i < oSize; i++) { // TODO (gd) start from 1 to avoid outer framestate, hacky.. + Node newValue = nInputs.get(i); + Node originalValue = oInputs.get(i); + if (newValue != originalValue) { + Node newExit = nEnd.singlePredecessor(); + NodeMap<Value> phiMap = newExitValues.get(originalValue); + if (phiMap == null) { + phiMap = graph.createNodeMap(); + newExitValues.set(originalValue, phiMap); + } + phiMap.set(original, (Value) originalValue); + phiMap.set(newExit, (Value) newValue); - phiMap = newExitValues.get(newValue); - if (phiMap == null) { - phiMap = graph.createNodeMap(); - newExitValues.set(newValue, phiMap); + phiMap = newExitValues.get(newValue); + if (phiMap == null) { + phiMap = graph.createNodeMap(); + newExitValues.set(newValue, phiMap); + } + phiMap.set(original, (Value) originalValue); + phiMap.set(nEnd, (Value) newValue); } - phiMap.set(original, (Value) originalValue); - phiMap.set(nEnd, (Value) newValue); } + newState = newState.outerFrameState(); + originalState = originalState.outerFrameState(); } - /*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); - } - }*/ + assert originalState == null; } for (Entry<Node, NodeMap<Value>> entry : newExitValues.entries()) { Value original = (Value) entry.getKey(); @@ -567,15 +555,16 @@ clearWithState(loopBegin, marked); Map<Node, Node> replacements = new HashMap<Node, Node>(); NodeMap<Placeholder> phis = graph.createNodeMap(); - NodeMap<Placeholder> exits = graph.createNodeMap(); - + NodeMap<StateSplit> exits = graph.createNodeMap(); + NodeBitMap unaffectedExits = graph.createNodeBitMap(); + NodeBitMap clonedExits = graph.createNodeBitMap(); for (Node exit : loop.exits()) { if (marked.isMarked(exit.singlePredecessor())) { - Placeholder pExit = (Placeholder) exit; - marked.mark(pExit.stateAfter()); - Placeholder p = new Placeholder(graph); - replacements.put(exit, p); - exits.set(exit, p); + StateSplit pExit = findNearestMergableExitPoint(exit, marked); + markWithState(pExit, marked); + clonedExits.mark(pExit); + } else { + unaffectedExits.mark(exit); } } @@ -587,7 +576,7 @@ marked.clear(n); } for (Node input : n.dataInputs()) { - if (!marked.isMarked(input) && (!(input instanceof Phi) || ((Phi) input).merge() != loopBegin)) { + if (!marked.isMarked(input) && (!(input instanceof Phi) || ((Phi) input).merge() != loopBegin) && replacements.get(input) == null) { replacements.put(input, input); } } @@ -602,6 +591,10 @@ Map<Node, Node> duplicates = graph.addDuplicate(marked, replacements); + for (Node n : clonedExits) { + exits.set(n, (StateSplit) duplicates.get(n)); + } + NodeMap<Node> dataOut = graph.createNodeMap(); for (Node n : marked) { for (Node usage : n.dataUsages()) { @@ -628,7 +621,12 @@ 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); + return new PeelingResult(newBegin, newFrom, exits, phis, phiInits, dataOut, unaffectedExits); + } + + private static StateSplit findNearestMergableExitPoint(Node exit, NodeBitMap marked) { + // TODO (gd) find appropriate point : will be useful if a loop exit goes "up" as a result of making a branch dead in the loop body + return (StateSplit) exit; } private static NodeBitMap inOrBefore(Loop loop) { @@ -686,8 +684,9 @@ map.mark(n); if (n instanceof StateSplit) { FrameState stateAfter = ((StateSplit) n).stateAfter(); - if (stateAfter != null) { + while (stateAfter != null) { map.mark(stateAfter); + stateAfter = stateAfter.outerFrameState(); } } } @@ -696,8 +695,9 @@ map.clear(n); if (n instanceof StateSplit) { FrameState stateAfter = ((StateSplit) n).stateAfter(); - if (stateAfter != null) { + while (stateAfter != null) { map.clear(stateAfter); + stateAfter = stateAfter.outerFrameState(); } } }
--- a/src/share/tools/IdealGraphVisualizer/Coordinator/src/com/sun/hotspot/igv/coordinator/StandardGroupOrganizer.java Fri Jul 01 12:57:10 2011 +0200 +++ b/src/share/tools/IdealGraphVisualizer/Coordinator/src/com/sun/hotspot/igv/coordinator/StandardGroupOrganizer.java Fri Jul 01 18:37:54 2011 +0200 @@ -51,7 +51,7 @@ List<Group> children = new ArrayList<Group>(); children.add(g); if(g.getGraphs().size() == 1) { - g.getGraphs().get(0).setName(g.getName() + " / " + g.getGraphs().get(0).getName()); + //g.getGraphs().get(0).setName(g.getName() + " / " + g.getGraphs().get(0).getName()); result.add(new Pair<String, List<Group>>("", children)); } else { Pair<String, List<Group>> p = new Pair<String, List<Group>>();