Mercurial > hg > truffle
changeset 3082:d5218b246554
Fix multiple bugs in loop peeling
| author | Gilles Duboscq <gilles.duboscq@oracle.com> |
|---|---|
| date | Tue, 28 Jun 2011 16:13:32 +0200 |
| parents | 0a5776813ff0 |
| children | 25b5ec0568e6 |
| files | graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.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/GraphUtil.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java |
| diffstat | 7 files changed, 200 insertions(+), 107 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Tue Jun 28 10:10:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinter.java Tue Jun 28 16:13:32 2011 +0200 @@ -297,9 +297,6 @@ stream.printf(" <block name='%d'>%n", block.blockID()); stream.printf(" <successors>%n"); for (Block sux : block.getSuccessors()) { -// 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()); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Tue Jun 28 10:10:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/gen/LIRGenerator.java Tue Jun 28 16:13:32 2011 +0200 @@ -1053,7 +1053,7 @@ lastState = fs; } else if (block.blockPredecessors().size() == 1) { FrameState fs = block.blockPredecessors().get(0).lastState(); - assert fs != null; //TODO gd maybe this assert should be removed + assert fs != null; if (GraalOptions.TraceLIRGeneratorLevel >= 2) { TTY.println("STATE CHANGE (singlePred)"); if (GraalOptions.TraceLIRGeneratorLevel >= 3) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Tue Jun 28 10:10:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Tue Jun 28 16:13:32 2011 +0200 @@ -28,10 +28,9 @@ import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.graph.*; -public class LoopBegin extends Merge{ +public class LoopBegin extends Merge { public LoopBegin(Graph graph) { super(graph); - this.addEnd(new EndNode(graph)); } public LoopEnd loopEnd() {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jun 28 10:10:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jun 28 16:13:32 2011 +0200 @@ -1167,6 +1167,7 @@ if (block.firstInstruction == null) { if (block.isLoopHeader) { LoopBegin loopBegin = new LoopBegin(graph); + loopBegin.addEnd(new EndNode(graph)); LoopEnd loopEnd = new LoopEnd(graph); loopEnd.setLoopBegin(loopBegin); Placeholder pBegin = new Placeholder(graph);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Tue Jun 28 10:10:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java Tue Jun 28 16:13:32 2011 +0200 @@ -37,12 +37,12 @@ @Override protected void run(Graph graph) { List<Loop> loops = LoopUtil.computeLoops(graph); - /* - for (Loop loop : loops) { - LoopUtil.peelLoop(loop); - } + +// for (Loop loop : loops) { +// LoopUtil.peelLoop(loop); +// } // 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/GraphUtil.java Tue Jun 28 10:10:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java Tue Jun 28 16:13:32 2011 +0200 @@ -25,7 +25,9 @@ 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.value.*; import com.oracle.max.graal.graph.*; @@ -104,40 +106,65 @@ public static interface ColorSplitingLambda<T> { void fixSplit(Node oldNode, Node newNode, T color); void fixNode(Node node, T color); + Value fixPhiInput(Value input, T color); boolean explore(Node n); } - // TODO (gd) handle FrameSate inputs/usages properly + // TODO (gd) rework that code around Phi handling : too complicated 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>(); + NodeWorkList work = coloring.graph().createNodeWorkList(); for (Entry<Node, T> entry : coloring.entries()) { T color = entry.getValue(); Node node = entry.getKey(); - work.offer(node); + work.add(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)); + try { + for (Node node : work) { + //System.out.println("Split : work on " + node); + if (node instanceof Phi) { + Phi phi = (Phi) node; + Merge merge = phi.merge(); + for (int i = 0; i < phi.valueCount(); i++) { + Value v = phi.valueAt(i); + if (v != null) { + T color = internalColoring.get(merge.phiPredecessorAt(i)); + Value replace = lambda.fixPhiInput(v, color); + if (replace != v) { + phi.setValueAt(i, replace); + } + } + } + } else { + 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; @@ -146,79 +173,99 @@ colors.add(color); } } + if (delay) { + //System.out.println("Split : delay"); + work.addAgain(node); + continue; + } } else { - T color = internalColoring.get(usage); - if (color == null) { - //System.out.println("Split : color from " + usage + " is null"); - delay = true; - break; - } - colors.add(color); + colors.add(originalColoringColor); } - } - 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 (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); + LinkedList<Node> dataUsages = new LinkedList<Node>(); + for (Node usage : node.dataUsages()) { + dataUsages.add(usage); + } + for (Node usage : 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) { - phi.setValueAt(i, (Value) newNode); + usage.inputs().replace(node, 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) && !work.isNew(stateAfter)) { + //System.out.println("Split : Add framestate to work"); + work.add(stateAfter); + } + } - 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); + if (node instanceof Merge) { + for (Node usage : node.usages()) { + if (!work.isNew(usage)) { + work.add(usage); + } + } + } + + if (node instanceof LoopEnd) { + work.add(((LoopEnd) node).loopBegin()); + } + + for (Node input : node.dataInputs()) { + if (lambda.explore(input) && coloring.get(input) == null && !work.isNew(input)) { + //System.out.println("Split : Add input " + input + " to work from " + node); + work.add(input); + } } } - - 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); + } catch (RuntimeException re) { + re.printStackTrace(); + GraalCompilation compilation = GraalCompilation.compilation(); + if (compilation.compiler.isObserved()) { + NodeMap<T> debugColoring = coloring.graph().createNodeMap(); + for (Entry<Node, T> entry : internalColoring.entrySet()) { + debugColoring.set(entry.getKey(), entry.getValue()); } + Map<String, Object> debug = new HashMap<String, Object>(); + debug.put("split", debugColoring); + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "RuntimeException in split", coloring.graph(), true, false, debug)); } } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Tue Jun 28 10:10:47 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java Tue Jun 28 16:13:32 2011 +0200 @@ -126,7 +126,7 @@ public static NodeBitMap computeLoopNodes(LoopBegin loopBegin) { return computeLoopNodesFrom(loopBegin, loopBegin.loopEnd()); } - + private static boolean recurse = false; public static NodeBitMap computeLoopNodesFrom(LoopBegin loopBegin, FixedNode from) { NodeFlood workData1 = loopBegin.graph().createNodeFlood(); NodeFlood workData2 = loopBegin.graph().createNodeFlood(); @@ -140,6 +140,17 @@ for (Node n : workData1) { inOrAfter.mark(n); for (Node usage : n.dataUsages()) { + 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; + } + } + } workData1.add(usage); } } @@ -155,6 +166,18 @@ } } } + /*if (!recurse) { + recurse = true; + GraalCompilation compilation = GraalCompilation.compilation(); + if (compilation.compiler.isObserved()) { + Map<String, Object> debug = new HashMap<String, Object>(); + debug.put("loopNodes", loopNodes); + debug.put("inOrAfter", inOrAfter); + debug.put("inOrBefore", inOrBefore); + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Compute loop nodes", loopBegin.graph(), true, false, debug)); + } + recurse = false; + }*/ inOrAfter.setIntersect(inOrBefore); loopNodes.setUnion(inOrAfter); return loopNodes; @@ -297,8 +320,6 @@ newExit.setStateAfter(null); newExit.replaceAndDelete(nEnd); - exitPoints.remove(original); - exitPoints.add(oEnd); exitPoints.add(nEnd); } @@ -413,7 +434,6 @@ 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) { @@ -425,12 +445,30 @@ return value; } Merge merge = (Merge) point; - Phi phi = new Phi(kind, merge, merge.graph()); - valueMap.set(point, phi); + ArrayList<Value> values = new ArrayList<Value>(merge.phiPredecessorCount()); + Value v = null; + boolean createPhi = false; for (EndNode end : merge.cfgPredecessors()) { - phi.addInput(getValueAt(colors.get(end), valueMap, kind)); + Value valueAt = getValueAt(colors.get(end), valueMap, kind); + if (v == null) { + v = valueAt; + } else if (v != valueAt) { + createPhi = true; + } + values.add(valueAt); } - return phi; + if (createPhi) { + 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; + } else { + assert v != null; + valueMap.set(point, v); + return v; + } } @Override public boolean explore(Node n) { @@ -451,6 +489,17 @@ //} } } + } + @Override + public Value fixPhiInput(Value input, Node color) { + if (newExitValues.isNew(input)) { + return input; + } + NodeMap<Value> valueMap = newExitValues.get(input); + if (valueMap != null) { + return getValueAt(color, valueMap, input.kind); + } + return input; }}); if (compilation.compiler.isObserved()) { @@ -470,7 +519,6 @@ 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()); @@ -500,17 +548,18 @@ } } - 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)); + Map<String, Object> debug = new HashMap<String, Object>(); + debug.put("marked", marked); + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Before addDuplicate", loopBegin.graph(), true, false, debug)); } + Map<Node, Node> duplicates = graph.addDuplicate(marked, replacements); + 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)) {