# HG changeset patch # User Gilles Duboscq # Date 1309538274 -7200 # Node ID 883c2f14e7d0869578ae6c598af555afc919ea75 # Parent 3664989976e2aee48278b4928a43893e3df714a9 Fixed various peeling bugs (can use nodes which are not Placeholders as loop exits) diff -r 3664989976e2 -r 883c2f14e7d0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalMetrics.java --- 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 m : map.entrySet()) { diff -r 3664989976e2 -r 883c2f14e7d0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java --- 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 = ____; } diff -r 3664989976e2 -r 883c2f14e7d0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java --- 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 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); + } } } diff -r 3664989976e2 -r 883c2f14e7d0 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java --- 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 exits; + public final NodeMap exits; + public final NodeBitMap unaffectedExits; public final NodeMap phis; public final NodeMap phiInits; public final NodeMap dataOut; - public PeelingResult(FixedNode begin, FixedNode end, NodeMap exits, NodeMap phis, NodeMap phiInits, NodeMap dataOut) { + public PeelingResult(FixedNode begin, FixedNode end, NodeMap exits, NodeMap phis, NodeMap phiInits, NodeMap 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> newExitValues = graph.createNodeMap(); List exitPoints = new LinkedList(); - for (Node exit : loop.exits()) { + for (Node exit : peeling.unaffectedExits) { exitPoints.add(exit); } - for (Entry entry : peeling.exits.entries()) { - Placeholder original = (Placeholder) entry.getKey(); - Placeholder newExit = entry.getValue(); - FixedNode next = original.next(); + for (Entry 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 entry : peeling.exits.entries()) { - Placeholder original = (Placeholder) entry.getKey(); + for (Entry 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 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 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 phiMap = newExitValues.get(originalValue); - if (phiMap == null) { - phiMap = graph.createNodeMap(); - newExitValues.set(originalValue, phiMap); - } - phiMap.set(merge, newPhi); - } - }*/ + assert originalState == null; } for (Entry> entry : newExitValues.entries()) { Value original = (Value) entry.getKey(); @@ -567,15 +555,16 @@ clearWithState(loopBegin, marked); Map replacements = new HashMap(); NodeMap phis = graph.createNodeMap(); - NodeMap exits = graph.createNodeMap(); - + NodeMap 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 duplicates = graph.addDuplicate(marked, replacements); + for (Node n : clonedExits) { + exits.set(n, (StateSplit) duplicates.get(n)); + } + NodeMap 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(); } } } diff -r 3664989976e2 -r 883c2f14e7d0 src/share/tools/IdealGraphVisualizer/Coordinator/src/com/sun/hotspot/igv/coordinator/StandardGroupOrganizer.java --- 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 children = new ArrayList(); 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>("", children)); } else { Pair> p = new Pair>();