# HG changeset patch # User Gilles Duboscq # Date 1310125118 -7200 # Node ID 494f0ff09b14047698ae31225bfc2ed209663a11 # Parent adfd999fff7d33ab2c221d80865d4a91963fb947 More precise inOrBefore, make both inOrBefore and inOrAfter accessible on Loop, compute inOrAfter, inOrBefore and full loop nodes only if needed diff -r adfd999fff7d -r 494f0ff09b14 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java Thu Jul 07 18:21:30 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java Fri Jul 08 13:38:38 2011 +0200 @@ -74,4 +74,9 @@ public Iterable< ? extends Node> dataUsages() { return Collections.emptyList(); } + + @Override + public Iterable< ? extends Node> cfgSuccessors() { + return Arrays.asList(this.merge()); + } } diff -r adfd999fff7d -r 494f0ff09b14 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 Thu Jul 07 18:21:30 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Fri Jul 08 13:38:38 2011 +0200 @@ -26,6 +26,7 @@ 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.util.*; import com.oracle.max.graal.compiler.util.LoopUtil.Loop; import com.oracle.max.graal.compiler.value.*; @@ -43,6 +44,15 @@ if (GraalOptions.LoopPeeling) { peeling: for (Loop loop : loops) { + GraalCompilation compilation = GraalCompilation.compilation(); + if (compilation.compiler.isObserved()) { + Map debug = new HashMap(); + debug.put("loopExits", loop.exits()); + debug.put("inOrBefore", loop.inOrBefore()); + debug.put("inOrAfter", loop.inOrAfter()); + debug.put("nodes", loop.nodes()); + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Loop #" + loop.loopBegin().id(), graph, true, false, debug)); + } //System.out.println("Peel loop : " + loop.loopBegin()); for (Node exit : loop.exits()) { if (!(exit instanceof StateSplit) || ((StateSplit) exit).stateAfter() == null) { diff -r adfd999fff7d -r 494f0ff09b14 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 Thu Jul 07 18:21:30 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Fri Jul 08 13:38:38 2011 +0200 @@ -39,12 +39,15 @@ public static class Loop { private final LoopBegin loopBegin; - private NodeBitMap nodes; + private NodeBitMap cfgNodes; private Loop parent; private NodeBitMap exits; + private NodeBitMap inOrBefore; + private NodeBitMap inOrAfter; + private NodeBitMap nodes; public Loop(LoopBegin loopBegin, NodeBitMap nodes, NodeBitMap exits) { this.loopBegin = loopBegin; - this.nodes = nodes; + this.cfgNodes = nodes; this.exits = exits; } @@ -52,7 +55,16 @@ return loopBegin; } + public NodeBitMap cfgNodes() { + return cfgNodes; + } + public NodeBitMap nodes() { + if (nodes == null) { + nodes = loopBegin().graph().createNodeBitMap(); + nodes.setUnion(inOrAfter()); + nodes.setIntersect(inOrBefore()); + } return nodes; } @@ -71,6 +83,31 @@ public boolean isChild(Loop loop) { return loop.parent != null && (loop.parent == this || loop.parent.isChild(this)); } + + public NodeBitMap inOrAfter() { + if (inOrAfter == null) { + inOrAfter = LoopUtil.inOrAfter(this); + } + return inOrAfter; + } + + public NodeBitMap inOrBefore() { + if (inOrBefore == null) { + inOrBefore = LoopUtil.inOrBefore(this, inOrAfter()); + } + return inOrBefore; + } + + public void invalidateCached() { + inOrAfter = null; + inOrBefore = null; + nodes = null; + } + + @Override + public String toString() { + return "Loop #" + loopBegin().id(); + } } private static class PeelingResult { @@ -97,14 +134,15 @@ public static List computeLoops(Graph graph) { List loops = new LinkedList(); for (LoopBegin loopBegin : graph.getNodes(LoopBegin.class)) { - NodeBitMap nodes = computeLoopNodes(loopBegin); - NodeBitMap exits = computeLoopExits(loopBegin, nodes); - loops.add(new Loop(loopBegin, nodes, exits)); + NodeBitMap cfgNodes = markUpCFG(loopBegin, loopBegin.loopEnd()); // computeLoopNodes(loopBegin); + cfgNodes.mark(loopBegin); + NodeBitMap exits = computeLoopExits(loopBegin, cfgNodes); + loops.add(new Loop(loopBegin, cfgNodes, exits)); } for (Loop loop : loops) { for (Loop other : loops) { - if (other != loop && other.nodes().isMarked(loop.loopBegin())) { - if (loop.parent() == null || loop.parent().nodes().isMarked(other.loopBegin())) { + if (other != loop && other.cfgNodes().isMarked(loop.loopBegin())) { + if (loop.parent() == null || loop.parent().cfgNodes().isMarked(other.loopBegin())) { loop.setParent(other); } } @@ -113,13 +151,13 @@ return loops; } - public static NodeBitMap computeLoopExits(LoopBegin loopBegin, NodeBitMap nodes) { + public static NodeBitMap computeLoopExits(LoopBegin loopBegin, NodeBitMap cfgNodes) { Graph graph = loopBegin.graph(); NodeBitMap exits = graph.createNodeBitMap(); - for (Node n : markUpCFG(loopBegin, loopBegin.loopEnd())) { + for (Node n : cfgNodes) { if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) { for (Node sux : n.cfgSuccessors()) { - if (!nodes.isMarked(sux) && sux instanceof FixedNode) { + if (!cfgNodes.isMarked(sux) && sux instanceof FixedNode) { exits.mark(sux); } } @@ -187,7 +225,9 @@ } if (n instanceof Merge) { //add phis & counters for (Node usage : n.dataUsages()) { - workData2.add(usage); + if (!(usage instanceof LoopEnd)) { + workData2.add(usage); + } } } if (n instanceof StateSplit) { @@ -234,16 +274,16 @@ } public static void inverseLoop(Loop loop, If split) { - assert loop.nodes().isMarked(split); + assert loop.cfgNodes().isMarked(split); FixedNode noExit = split.trueSuccessor(); FixedNode exit = split.falseSuccessor(); - if (loop.nodes().isMarked(exit) && !loop.nodes().isMarked(noExit)) { + if (loop.cfgNodes().isMarked(exit) && !loop.cfgNodes().isMarked(noExit)) { FixedNode tmp = noExit; noExit = exit; exit = tmp; } - assert !loop.nodes().isMarked(exit); - assert loop.nodes().isMarked(noExit); + assert !loop.cfgNodes().isMarked(exit); + assert loop.cfgNodes().isMarked(noExit); PeelingResult peeling = preparePeeling(loop, split); rewirePeeling(peeling, loop, split); @@ -283,8 +323,9 @@ // update parents Loop parent = loop.parent(); while (parent != null) { - parent.nodes = computeLoopNodes(parent.loopBegin); - parent.exits = computeLoopExits(parent.loopBegin, parent.nodes); + parent.cfgNodes = computeLoopNodes(parent.loopBegin); + parent.invalidateCached(); + parent.exits = computeLoopExits(parent.loopBegin, parent.cfgNodes); parent = parent.parent; } GraalMetrics.LoopsPeeled++; @@ -295,7 +336,7 @@ Graph graph = loopBegin.graph(); Node loopPred = loopBegin.singlePredecessor(); loopPred.successors().replace(loopBegin.forwardEdge(), peeling.begin); - NodeBitMap loopNodes = loop.nodes(); + NodeBitMap loopNodes = loop.cfgNodes(); Node originalLast = from; if (originalLast == loopBegin.loopEnd()) { originalLast = loopBegin.loopEnd().singlePredecessor(); @@ -442,13 +483,17 @@ } }); - final NodeBitMap inOrBefore = inOrBefore(loop); + + loop.invalidateCached(); + final NodeBitMap inOrBefore = loop.inOrBefore(); GraalCompilation compilation = GraalCompilation.compilation(); if (compilation.compiler.isObserved()) { Map debug = new HashMap(); debug.put("loopExits", colors); debug.put("inOrBefore", inOrBefore); + debug.put("inOrAfter", loop.inOrAfter()); + debug.put("nodes", loop.nodes()); debug.put("exitFrameStates", exitFrameStates); compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After coloring", graph, true, false, debug)); } @@ -495,6 +540,11 @@ } @Override public boolean explore(Node n) { + /*System.out.println("Explore " + n + "?"); + System.out.println(" - exitFS : " + (!exitFrameStates.isNew(n) && exitFrameStates.isMarked(n))); + System.out.println(" - !inOrBefore : " + (!inOrBefore.isNew(n) && !inOrBefore.isMarked(n))); + System.out.println(" - inputs > 0 : " + (n.inputs().size() > 0)); + System.out.println(" - !danglingMergeFrameState : " + (!danglingMergeFrameState(n)));*/ return (!exitFrameStates.isNew(n) && exitFrameStates.isMarked(n)) || (!inOrBefore.isNew(n) && !inOrBefore.isMarked(n) && n.inputs().size() > 0 && !danglingMergeFrameState(n)); //TODO (gd) hum } @@ -510,7 +560,9 @@ //System.out.println("fixNode(" + node + ", " + color + ")"); if (color == null) { // 'white' it out : make non-explorable - exitFrameStates.clear(node); + if (!exitFrameStates.isNew(node)) { + exitFrameStates.clear(node); + } inOrBefore.mark(node); } else { for (int i = 0; i < node.inputs().size(); i++) { @@ -677,11 +729,45 @@ return (StateSplit) exit; } - private static NodeBitMap inOrBefore(Loop loop) { + private static NodeBitMap inOrAfter(Loop loop) { + Graph graph = loop.loopBegin().graph(); + NodeBitMap inOrAfter = graph.createNodeBitMap(); + NodeFlood work = graph.createNodeFlood(); + NodeBitMap loopNodes = loop.cfgNodes(); + work.addAll(loopNodes); + for (Node n : work) { + //inOrAfter.mark(n); + markWithState(n, inOrAfter); + for (Node sux : n.successors()) { + if (sux != null) { + work.add(sux); + } + } + for (Node usage : n.usages()) { + if (usage instanceof Phi) { // filter out data graph cycles + Phi phi = (Phi) usage; + if (!phi.isDead()) { + Merge merge = phi.merge(); + if (merge instanceof LoopBegin) { + LoopBegin phiLoop = (LoopBegin) merge; + int backIndex = phiLoop.phiPredecessorIndex(phiLoop.loopEnd()); + if (phi.valueAt(backIndex) == n) { + continue; + } + } + } + } + work.add(usage); + } + } + return inOrAfter; + } + + private static NodeBitMap inOrBefore(Loop loop, NodeBitMap inOrAfter) { Graph graph = loop.loopBegin().graph(); NodeBitMap inOrBefore = graph.createNodeBitMap(); NodeFlood work = graph.createNodeFlood(); - NodeBitMap loopNodes = loop.nodes(); + NodeBitMap loopNodes = loop.cfgNodes(); work.addAll(loopNodes); for (Node n : work) { inOrBefore.mark(n); @@ -709,7 +795,19 @@ work.add(in); } } - if (n instanceof LoopBegin) { + for (Node sux : n.cfgSuccessors()) { // go down into branches that are not 'inOfAfter' + if (sux != null && !inOrAfter.isMarked(sux)) { + work.add(sux); + } + } + if (n instanceof Merge) { //add phis & counters + for (Node usage : n.dataUsages()) { + if (!(usage instanceof LoopEnd)) { + work.add(usage); + } + } + } + if (n instanceof LoopBegin && n != loop.loopBegin()) { Loop p = loop.parent; boolean isParent = false; while (p != null) {