Mercurial > hg > truffle
changeset 3201:38792f959479
Merge
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/EdgeMoveOptimizer.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/alloc/EdgeMoveOptimizer.java Fri Jul 08 15:00:16 2011 +0200 @@ -221,11 +221,11 @@ // the instructions are inserted at the end of the block before these two branches int insertIdx = instructions.size() - 2; - if (GraalOptions.DetailedAsserts) { + if (GraalOptions.DetailedAsserts && false) { // not true anymore with guards for (int i = insertIdx - 1; i >= 0; i--) { LIRInstruction op = instructions.get(i); if ((op.code == LIROpcode.Branch || op.code == LIROpcode.CondFloatBranch) && ((LIRBranch) op).block() != null) { - throw new Error("block with two successors can have only two branch instructions"); + throw new Error("block with two successors can have only two branch instructions : error in " + block); } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Fri Jul 08 15:00:16 2011 +0200 @@ -229,14 +229,14 @@ if (block != null) { stream.printf(" <p name='block'>%d</p>%n", block.blockID()); if (!(node instanceof Phi || node instanceof FrameState || node instanceof Local || node instanceof LoopCounter) && !block.getInstructions().contains(node)) { - stream.printf(" <p name='notInOwnBlock'>true</p>%n"); + stream.println(" <p name='notInOwnBlock'>true</p>"); } } else { - stream.printf(" <p name='block'>noBlock</p>%n"); + stream.println(" <p name='block'>noBlock</p>"); noBlockNodes.add(node); } if (loopExits.isMarked(node)) { - stream.printf(" <p name='loopExit'>true</p>%n"); + stream.println(" <p name='loopExit'>true</p>"); } StringBuilder sb = new StringBuilder(); if (loops != null) { @@ -264,7 +264,7 @@ Set<String> nodeBits = bits.get(node); if (nodeBits != null) { for (String bit : nodeBits) { - stream.printf(" <p name='"); + stream.print(" <p name='"); stream.print(bit); stream.println("'>true</p>"); } @@ -310,14 +310,14 @@ private void printBlock(Graph graph, Block block, NodeMap<Block> nodeToBlock) { stream.printf(" <block name='%d'>%n", block.blockID()); - stream.printf(" <successors>%n"); + stream.println(" <successors>"); for (Block sux : block.getSuccessors()) { if (sux != null) { stream.printf(" <successor name='%d'/>%n", sux.blockID()); } } - stream.printf(" </successors>%n"); - stream.printf(" <nodes>%n"); + stream.println(" </successors>"); + stream.println(" <nodes>"); Set<Node> nodes = new HashSet<Node>(block.getInstructions()); @@ -360,7 +360,7 @@ } } } - stream.printf(" </nodes>%n"); + stream.println(" </nodes>"); stream.printf(" </block>%n", block.blockID()); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java Fri Jul 08 15:00:16 2011 +0200 @@ -101,7 +101,7 @@ try { socket = new Socket(host, port); if (socket.getInputStream().read() == 'y') { - stream = socket.getOutputStream(); + stream = new BufferedOutputStream(socket.getOutputStream(), 0x4000); } else { // server currently does not accept any input socket.close();
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Fri Jul 08 15:00:16 2011 +0200 @@ -1731,7 +1731,7 @@ } } // the value must be a constant or have a valid operand - assert operand.isLegal() : "this root has not been visited yet; instruction=" + instruction; + assert operand.isLegal() : "this root has not been visited yet; instruction=" + instruction + " currentBlock=" + currentBlock; return operand; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Fri Jul 08 15:00:16 2011 +0200 @@ -109,6 +109,10 @@ if (GraalOptions.OptLoops) { new LoopPhase().apply(graph); + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase().apply(graph); + new DeadCodeEliminationPhase().apply(graph); + } } if (GraalOptions.EscapeAnalysis) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java Fri Jul 08 15:00:16 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()); + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Fri Jul 08 15:00:16 2011 +0200 @@ -27,6 +27,7 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.compiler.ir.Phi.PhiType; +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.*; @@ -44,7 +45,16 @@ if (GraalOptions.LoopPeeling) { peeling: for (Loop loop : loops) { - // System.out.println("Peel loop : " + loop.loopBegin()); + GraalCompilation compilation = GraalCompilation.compilation(); + if (compilation.compiler.isObserved()) { + Map<String, Object> debug = new HashMap<String, Object>(); + 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) { // TODO (gd) can not do loop peeling if an exit has no state. see LoopUtil.findNearestMergableExitPoint
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/IdentifyBlocksPhase.java Fri Jul 08 15:00:16 2011 +0200 @@ -323,6 +323,8 @@ block = getCommonDominator(block, mergeBlock.getPredecessors().get(i)); } } + } else if (usage instanceof FrameState && ((FrameState) usage).outerFrameState() == n) { + block = getCommonDominator(block, assignLatestPossibleBlockToNode(usage)); } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) { Merge merge = ((FrameState) usage).block(); for (Node pred : merge.cfgPredecessors()) { @@ -517,7 +519,7 @@ int cnt = 0; while (!workList.isEmpty()) { - if (cnt++ > blocks.size() * 10) { + if (cnt++ > blocks.size() * 15) { throw new RuntimeException("(ls) endless loop in computeDominators?"); } Block b = workList.remove();
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java Fri Jul 08 15:00:16 2011 +0200 @@ -27,6 +27,7 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.ir.Phi.PhiType; import com.oracle.max.graal.compiler.observer.*; import com.oracle.max.graal.compiler.value.*; import com.oracle.max.graal.graph.*; @@ -82,36 +83,6 @@ colors.set(merge, color); } } - - - /*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 { - System.out.println("Can not color " + merge); - work.addAgain(merge); - } - }*/ } private static <T> Collection<Merge> colorCFGDownToMerge(Node from, T color, NodeMap<T> colors) { @@ -129,7 +100,7 @@ break; } colors.set(current, color); - if (current instanceof FixedNodeWithNext) { + if (current instanceof FixedNodeWithNext && !(current instanceof Invoke && ((Invoke) current).exceptionEdge() != null)) { current = ((FixedNodeWithNext) current).next(); } else if (current instanceof EndNode) { current = ((EndNode) current).merge(); @@ -138,6 +109,10 @@ for (Node sux : current.cfgSuccessors()) { work.add(sux); } + } else if (current instanceof Invoke && ((Invoke) current).exceptionEdge() != null) { + Invoke invoke = (Invoke) current; + work.add(invoke.next()); + work.add(invoke.exceptionEdge()); } current = null; } @@ -152,6 +127,8 @@ void fixNode(Node node, T color); Value fixPhiInput(Value input, T color); boolean explore(Node n); + List<T> parentColors(T color); + Merge merge(T color); } // TODO (gd) rework that code around Phi handling : too complicated @@ -214,11 +191,14 @@ } else { T color = internalColoring.get(usage); if (color == null) { - //System.out.println("Split : color from " + usage + " is null"); - delay = true; - break; + //System.out.println("Split : color from " + usage + " is null : " + (lambda.explore(usage) ? "Should be colored" : "Should be white")); + if (lambda.explore(usage)) { + delay = true; + break; + } + } else { + colors.add(color); } - colors.add(color); } } if (delay) { @@ -235,19 +215,44 @@ 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); + Map<T, Node> newNodes = new HashMap<T, Node>(); + Queue<T> colorQueue = new LinkedList<T>(colors); + while (!colorQueue.isEmpty()) { + T color = colorQueue.poll(); + List<T> parentColors = lambda.parentColors(color); + Node newNode; + if (parentColors.size() > 1 && !(node instanceof FrameState) && colors.containsAll(parentColors)) { + boolean ready = true; + for (T parentColor : parentColors) { + if (newNodes.get(parentColor) == null) { + ready = false; + break; + } + } + if (!ready) { + colorQueue.offer(color); + continue; + } + Phi phi = new Phi(((Value) node).kind, lambda.merge(color), PhiType.Value, node.graph()); + for (T parentColor : parentColors) { + Node input = newNodes.get(parentColor); + phi.addInput(input); + } + newNode = phi; + } else { + 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 (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); + newNodes.put(color, newNode); LinkedList<Node> dataUsages = new LinkedList<Node>(); for (Node usage : node.dataUsages()) { dataUsages.add(usage); @@ -273,12 +278,15 @@ } } } + lambda.fixNode(node, null /*white*/); } if (node instanceof StateSplit) { FrameState stateAfter = ((StateSplit) node).stateAfter(); if (stateAfter != null && lambda.explore(stateAfter) && !work.isNew(stateAfter)) { //System.out.println("Split : Add framestate to work"); - work.add(stateAfter); + if (!(node instanceof Merge && coloring.get(((Merge) node).next()) == null)) { // not dangling colored merge + work.add(stateAfter); + } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Fri Jul 08 15:00:16 2011 +0200 @@ -40,12 +40,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; } @@ -53,7 +56,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; } @@ -72,6 +84,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 { @@ -82,7 +119,8 @@ public final NodeMap<Placeholder> phis; public final NodeMap<Node> phiInits; public final NodeMap<Node> dataOut; - public PeelingResult(FixedNode begin, FixedNode end, NodeMap<StateSplit> exits, NodeMap<Placeholder> phis, NodeMap<Node> phiInits, NodeMap<Node> dataOut, NodeBitMap unaffectedExits) { + public final NodeBitMap exitFrameStates; + public PeelingResult(FixedNode begin, FixedNode end, NodeMap<StateSplit> exits, NodeMap<Placeholder> phis, NodeMap<Node> phiInits, NodeMap<Node> dataOut, NodeBitMap unaffectedExits, NodeBitMap exitFrameStates) { this.begin = begin; this.end = end; this.exits = exits; @@ -90,20 +128,22 @@ this.phiInits = phiInits; this.dataOut = dataOut; this.unaffectedExits = unaffectedExits; + this.exitFrameStates = exitFrameStates; } } 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); - 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); } } @@ -112,25 +152,17 @@ 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(); - NodeFlood workCFG = graph.createNodeFlood(); - workCFG.add(loopBegin.loopEnd()); - for (Node n : workCFG) { - if (n == loopBegin) { - continue; - } + 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); } } } - for (Node pred : n.cfgPredecessors()) { - workCFG.add(pred); - } } return exits; } @@ -170,7 +202,8 @@ } NodeBitMap inOrBefore = loopBegin.graph().createNodeBitMap(); for (Node n : workData2) { - markWithState(n, inOrBefore); + //markWithState(n, inOrBefore); + inOrBefore.mark(n); if (n instanceof Phi) { // filter out data graph cycles Phi phi = (Phi) n; if (phi.type() == PhiType.Value) { @@ -193,11 +226,19 @@ } 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) { + FrameState stateAfter = ((StateSplit) n).stateAfter(); + if (stateAfter != null) { + workData2.add(stateAfter); } } } - if (!recurse) { + /*if (!recurse) { recurse = true; GraalCompilation compilation = GraalCompilation.compilation(); if (compilation.compiler.isObserved()) { @@ -208,7 +249,7 @@ compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Compute loop nodes loop#" + loopBegin.id(), loopBegin.graph(), true, false, debug)); } recurse = false; - } + }*/ inOrAfter.setIntersect(inOrBefore); loopNodes.setUnion(inOrAfter); return loopNodes; @@ -234,16 +275,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); @@ -277,14 +318,15 @@ System.out.println(" - " + entry.getKey() + " -> " + entry.getValue()); }*/ rewirePeeling(peeling, loop, loopEnd); - if (compilation.compiler.isObserved()) { + /*if (compilation.compiler.isObserved()) { compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After rewirePeeling", loopEnd.graph(), true, false)); - } + }*/ // 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 +337,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(); @@ -318,7 +360,14 @@ for (Entry<Node, Placeholder> entry : peeling.phis.entries()) { Phi phi = (Phi) entry.getKey(); Placeholder p = entry.getValue(); - p.replaceAndDelete(phi.valueAt(phiInitIndex)); + Value init = phi.valueAt(phiInitIndex); + p.replaceAndDelete(init); + for (Entry<Node, Node> dataEntry : peeling.dataOut.entries()) { + if (dataEntry.getValue() == p) { + dataEntry.setValue(init); + //System.out.println("Patch dataOut : " + dataEntry.getKey() + " -> " + dataEntry.getValue()); + } + } } for (Entry<Node, Node> entry : peeling.phiInits.entries()) { Phi phi = (Phi) entry.getKey(); @@ -342,10 +391,10 @@ EndNode oEnd = new EndNode(graph); EndNode nEnd = new EndNode(graph); Merge merge = new Merge(graph); - FrameState newState = newExit.stateAfter(); + FrameState originalState = original.stateAfter(); merge.addEnd(nEnd); merge.addEnd(oEnd); - merge.setStateAfter(newState.duplicate(newState.bci)); + merge.setStateAfter(originalState.duplicate(originalState.bci, true)); merge.setNext(original.next()); original.setNext(oEnd); newExit.setNext(nEnd); @@ -358,40 +407,20 @@ EndNode oEnd = (EndNode) original.next(); Merge merge = oEnd.merge(); EndNode nEnd = merge.endAt(1 - merge.phiPredecessorIndex(oEnd)); - FrameState newState = merge.stateAfter(); - 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); + Node newExit = nEnd.singlePredecessor(); + for (Entry<Node, Node> dataEntry : peeling.dataOut.entries()) { + Node originalValue = dataEntry.getKey(); + Node newValue = dataEntry.getValue(); + 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.set(original, (Value) originalValue); - phiMap.set(nEnd, (Value) newValue); - } - } - newState = newState.outerFrameState(); - originalState = originalState.outerFrameState(); - } - assert originalState == null; - } for (Entry<Node, NodeMap<Value>> entry : newExitValues.entries()) { Value original = (Value) entry.getKey(); NodeMap<Value> pointToValue = entry.getValue(); @@ -403,10 +432,10 @@ } } - replaceValuesAtLoopExits(newExitValues, loop, exitPoints); + replaceValuesAtLoopExits(newExitValues, loop, exitPoints, peeling.exitFrameStates); } - private static void replaceValuesAtLoopExits(final NodeMap<NodeMap<Value>> newExitValues, Loop loop, List<Node> exitPoints) { + private static void replaceValuesAtLoopExits(final NodeMap<NodeMap<Value>> newExitValues, Loop loop, List<Node> exitPoints, final NodeBitMap exitFrameStates) { Graph graph = loop.loopBegin().graph(); final NodeMap<Node> colors = graph.createNodeMap(); @@ -455,25 +484,31 @@ } }); - final NodeBitMap inOrBefore = inOrBefore(loop); + + loop.invalidateCached(); + final NodeBitMap inOrBefore = loop.inOrBefore(); GraalCompilation compilation = GraalCompilation.compilation(); if (compilation.compiler.isObserved()) { Map<String, Object> debug = new HashMap<String, Object>(); 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)); } GraphUtil.splitFromColoring(colors, new ColorSplitingLambda<Node>(){ @Override public void fixSplit(Node oldNode, Node newNode, Node color) { + assert color != null; this.fixNode(newNode, color); } private Value getValueAt(Node point, NodeMap<Value> valueMap, CiKind kind) { Value value = valueMap.get(point); if (value != null) { - //System.out.println("getValueAt(" + point + ", valueMap, kind) = " + value); + //System.out.println("getValueAt(" + point + ", valueMap, kind) = (cached) " + value); return value; } Merge merge = (Merge) point; @@ -495,31 +530,65 @@ for (EndNode end : merge.cfgPredecessors()) { phi.addInput(getValueAt(colors.get(end), valueMap, kind)); } - //System.out.println("getValueAt(" + point + ", valueMap, kind) = " + phi); + //System.out.println("getValueAt(" + point + ", valueMap, kind) = (new-phi) " + phi); return phi; } else { assert v != null; valueMap.set(point, v); - //System.out.println("getValueAt(" + point + ", valueMap, kind) = " + v); + //System.out.println("getValueAt(" + point + ", valueMap, kind) = (unique) " + v); return v; } } @Override public boolean explore(Node n) { - return !inOrBefore.isNew(n) && !inOrBefore.isMarked(n) && !(n instanceof Local) && !(n instanceof Constant); //TODO (gd) hum + /*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 && !afterColoringFramestate(n)); //TODO (gd) hum + } + public boolean afterColoringFramestate(Node n) { + if (!(n instanceof FrameState)) { + return false; + } + final FrameState frameState = (FrameState) n; + Merge block = frameState.block(); + if (block != null) { + return colors.get(block.next()) == null; + } + StateSplit stateSplit = frameState.stateSplit(); + if (stateSplit != null) { + return colors.get(stateSplit) == null; + } + for (FrameState inner : frameState.innerFrameStates()) { + if (!afterColoringFramestate(inner)) { + return false; + } + } + return true; } @Override public void fixNode(Node node, Node color) { //System.out.println("fixNode(" + node + ", " + color + ")"); - for (int i = 0; i < node.inputs().size(); i++) { - Node input = node.inputs().get(i); - if (input == null || newExitValues.isNew(input)) { - continue; + if (color == null) { + // 'white' it out : make non-explorable + if (!exitFrameStates.isNew(node)) { + exitFrameStates.clear(node); } - NodeMap<Value> valueMap = newExitValues.get(input); - if (valueMap != null) { - Value replacement = getValueAt(color, valueMap, ((Value) input).kind); - node.inputs().set(i, replacement); + inOrBefore.mark(node); + } else { + 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); + node.inputs().set(i, replacement); + } } } } @@ -533,11 +602,28 @@ return getValueAt(color, valueMap, input.kind); } return input; - }}); + } + @Override + public List<Node> parentColors(Node color) { + if (!(color instanceof Merge)) { + return Collections.emptyList(); + } + Merge merge = (Merge) color; + List<Node> parentColors = new ArrayList<Node>(merge.phiPredecessorCount()); + for (Node pred : merge.phiPredecessors()) { + parentColors.add(colors.get(pred)); + } + return parentColors; + } + @Override + public Merge merge(Node color) { + return (Merge) color; + } + }); - if (compilation.compiler.isObserved()) { + /*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) { @@ -545,11 +631,11 @@ Graph graph = loopBegin.graph(); NodeBitMap marked = computeLoopNodesFrom(loopBegin, from); GraalCompilation compilation = GraalCompilation.compilation(); - if (compilation.compiler.isObserved()) { + /*if (compilation.compiler.isObserved()) { Map<String, Object> debug = new HashMap<String, Object>(); debug.put("marked", marked); compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After computeLoopNodesFrom", loopBegin.graph(), true, false, debug)); - } + }*/ if (from == loopBegin.loopEnd()) { clearWithState(from, marked); } @@ -559,16 +645,35 @@ NodeMap<StateSplit> exits = graph.createNodeMap(); NodeBitMap unaffectedExits = graph.createNodeBitMap(); NodeBitMap clonedExits = graph.createNodeBitMap(); + NodeBitMap exitFrameStates = graph.createNodeBitMap(); for (Node exit : loop.exits()) { if (marked.isMarked(exit.singlePredecessor())) { StateSplit pExit = findNearestMergableExitPoint(exit, marked); markWithState(pExit, marked); clonedExits.mark(pExit); + FrameState stateAfter = pExit.stateAfter(); + while (stateAfter != null) { + exitFrameStates.mark(stateAfter); + stateAfter = stateAfter.outerFrameState(); + } } else { unaffectedExits.mark(exit); } } + NodeBitMap dataOut = graph.createNodeBitMap(); + for (Node n : marked) { + if (!(n instanceof FrameState)) { + for (Node usage : n.dataUsages()) { + if ((!marked.isMarked(usage) && !((usage instanceof Phi) && ((Phi) usage).merge() != loopBegin)) + || (marked.isMarked(usage) && exitFrameStates.isMarked(usage))) { + dataOut.mark(n); + break; + } + } + } + } + for (Node n : marked) { if (n instanceof Phi && ((Phi) n).merge() == loopBegin) { Placeholder p = new Placeholder(graph); @@ -592,37 +697,45 @@ Map<Node, Node> duplicates = graph.addDuplicate(marked, replacements); + /*System.out.println("Dup mapping :"); + for (Entry<Node, Node> entry : duplicates.entrySet()) { + System.out.println(" - " + entry.getKey().id() + " -> " + entry.getValue().id()); + }*/ + + NodeMap<Node> dataOutMapping = graph.createNodeMap(); + for (Node n : dataOut) { + Node newOut = duplicates.get(n); + if (newOut == null) { + newOut = replacements.get(n); + } + assert newOut != null; + dataOutMapping.set(n, newOut); + } + 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()) { - 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(); + if (from == loopBegin.loopEnd()) { + 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)); + } else { + phiInits.set(phi, backValue); } } } - 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, unaffectedExits); + return new PeelingResult(newBegin, newFrom, exits, phis, phiInits, dataOutMapping, unaffectedExits, exitFrameStates); } private static StateSplit findNearestMergableExitPoint(Node exit, NodeBitMap marked) { @@ -630,11 +743,43 @@ 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; + 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); @@ -662,7 +807,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) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java Fri Jul 08 13:41:27 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java Fri Jul 08 15:00:16 2011 +0200 @@ -150,10 +150,18 @@ * Gets a copy of this frame state. */ public FrameState duplicate(int bci) { + return duplicate(bci, false); + } + + public FrameState duplicate(int bci, boolean duplicateOuter) { FrameState other = new FrameState(method, bci, localsSize, stackSize, locksSize, rethrowException, graph()); other.inputs().setAll(inputs()); other.variableInputs().addAll(variableInputs()); - other.setOuterFrameState(outerFrameState()); + FrameState outerFrameState = outerFrameState(); + if (duplicateOuter && outerFrameState != null) { + outerFrameState = outerFrameState.duplicate(outerFrameState.bci, duplicateOuter); + } + other.setOuterFrameState(outerFrameState); return other; } @@ -455,6 +463,42 @@ return null; } + public Iterable<FrameState> innerFrameStates() { + final Iterator<Node> iterator = usages().iterator(); + return new Iterable<FrameState>() { + @Override + public Iterator<FrameState> iterator() { + return new Iterator<FrameState>() { + private Node next; + @Override + public void remove() { + throw new UnsupportedOperationException(); + } + @Override + public FrameState next() { + forward(); + if (!hasNext()) { + throw new NoSuchElementException(); + } + FrameState res = (FrameState) next; + next = null; + return res; + } + @Override + public boolean hasNext() { + forward(); + return next != null; + } + private void forward() { + while (!(next instanceof FrameState) && iterator.hasNext()) { + next = iterator.next(); + } + } + }; + } + }; + } + /** * The interface implemented by a client of {@link FrameState#forEachPhi(Merge, PhiProcedure)} and * {@link FrameState#forEachLivePhi(Merge, PhiProcedure)}. @@ -641,12 +685,21 @@ } @Override - public Node copy(Graph into) { - return new FrameState(method, bci, localsSize, stackSize, locksSize, rethrowException, into); + public void delete() { + FrameState outerFrameState = outerFrameState(); + super.delete(); + if (outerFrameState != null && outerFrameState.usages().isEmpty()) { + outerFrameState.delete(); + } } @Override public void setRethrowException(boolean b) { rethrowException = b; } + + @Override + public Node copy(Graph into) { + return new FrameState(method, bci, localsSize, stackSize, locksSize, rethrowException, into); + } }
--- a/runfilter.sh Fri Jul 08 13:41:27 2011 +0200 +++ b/runfilter.sh Fri Jul 08 15:00:16 2011 +0200 @@ -18,4 +18,4 @@ FILTER=$1 shift 1 TESTDIR=${MAXINE}/com.oracle.max.vm/test -${JDK7}/bin/java -client -d64 -graal -ea -esa -Xcomp -XX:+PrintCompilation -XX:CompileOnly=jtt -Xbootclasspath/p:"${MAXINE}/com.oracle.max.vm/bin" -Xbootclasspath/p:"${MAXINE}/com.oracle.max.base/bin" $@ test.com.sun.max.vm.compiler.JavaTester -filter=${FILTER} -verbose=1 -gen-run-scheme=false -run-scheme-package=all $@ ${TESTDIR}/jtt/bytecode ${TESTDIR}/jtt/except ${TESTDIR}/jtt/hotpath ${TESTDIR}/jtt/jdk ${TESTDIR}/jtt/lang ${TESTDIR}/jtt/loop ${TESTDIR}/jtt/micro ${TESTDIR}/jtt/optimize ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/threads +${JDK7}/bin/java -client -d64 -graal -ea -esa -Xcomp -XX:+PrintCompilation -XX:CompileOnly=jtt -Xbootclasspath/p:"${MAXINE}/com.oracle.max.vm/bin" -Xbootclasspath/p:"${MAXINE}/com.oracle.max.base/bin" $@ test.com.sun.max.vm.compiler.JavaTester -filter=${FILTER} -verbose=1 -gen-run-scheme=false -run-scheme-package=all $@ ${TESTDIR}/jtt/bytecode ${TESTDIR}/jtt/except ${TESTDIR}/jtt/hotpath ${TESTDIR}/jtt/jdk ${TESTDIR}/jtt/lang ${TESTDIR}/jtt/loop ${TESTDIR}/jtt/micro ${TESTDIR}/jtt/optimize ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/threads ${TESTDIR}/jtt/reflect ${TESTDIR}/jtt/hotspot