# HG changeset patch # User Thomas Wuerthinger # Date 1309355120 -7200 # Node ID b6282786e163ec4f8af9c7c6aa13848f31b7f6c6 # Parent 222f60eb09a78800837493516e67f4b6ac720114 Added canonicalization of boolean nodes and if conditions diff -r 222f60eb09a7 -r b6282786e163 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 Tue Jun 28 16:59:56 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Wed Jun 29 15:45:20 2011 +0200 @@ -101,6 +101,7 @@ public static boolean TraceAssembler = ____; public static boolean TraceInlining = ____; public static boolean TraceDeadCodeElimination = ____; + public static boolean TraceCanonicalizer = ____; public static boolean TraceMemoryMaps = ____; public static boolean TraceReadElimination = ____; public static boolean TraceGVN = ____; diff -r 222f60eb09a7 -r b6282786e163 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/CompilerGraph.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/CompilerGraph.java Tue Jun 28 16:59:56 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/CompilerGraph.java Wed Jun 29 15:45:20 2011 +0200 @@ -25,6 +25,7 @@ import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.ir.*; import com.oracle.max.graal.graph.*; +import com.sun.cri.ri.*; public class CompilerGraph extends Graph { @@ -56,6 +57,9 @@ return unwindSingleton; } + public RiRuntime runtime() { + return compilation.runtime; + } public GraalCompilation getCompilation() { return compilation; diff -r 222f60eb09a7 -r b6282786e163 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Compare.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Compare.java Tue Jun 28 16:59:56 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Compare.java Wed Jun 29 15:45:20 2011 +0200 @@ -22,7 +22,10 @@ */ package com.oracle.max.graal.compiler.ir; +import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.graph.*; +import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*; import com.oracle.max.graal.compiler.util.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -138,6 +141,15 @@ return "Comp " + condition.operator; } + @SuppressWarnings("unchecked") + @Override + public T lookup(Class clazz) { + if (clazz == CanonicalizerOp.class) { + return (T) CANONICALIZER; + } + return super.lookup(clazz); + } + @Override public Node copy(Graph into) { Compare x = new Compare(null, condition, null, into); @@ -149,4 +161,27 @@ public BooleanNode negate() { return new Compare(x(), condition.negate(), y(), graph()); } + + private static CanonicalizerOp CANONICALIZER = new CanonicalizerOp() { + @Override + public Node canonical(Node node) { + Compare compare = (Compare) node; + if (compare.x().isConstant() && compare.y().isConstant()) { + CiConstant constX = compare.x().asConstant(); + CiConstant constY = compare.y().asConstant(); + Boolean result = compare.condition().foldCondition(constX, constY, ((CompilerGraph) node.graph()).runtime()); + if (result != null) { + if (GraalOptions.TraceCanonicalizer) { + TTY.println("folded condition " + constX + " " + compare.condition() + " " + constY); + } + return Constant.forBoolean(result, compare.graph()); + } else { + if (GraalOptions.TraceCanonicalizer) { + TTY.println("if not removed %s %s %s (%s %s)", constX, compare.condition(), constY, constX.kind, constY.kind); + } + } + } + return compare; + } + }; } diff -r 222f60eb09a7 -r b6282786e163 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Constant.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Constant.java Tue Jun 28 16:59:56 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Constant.java Wed Jun 29 15:45:20 2011 +0200 @@ -33,7 +33,7 @@ * The {@code Constant} instruction represents a constant such as an integer value, * long, float, object reference, address, etc. */ -public final class Constant extends FloatingNode { +public final class Constant extends BooleanNode { private static final int INPUT_COUNT = 0; private static final int SUCCESSOR_COUNT = 0; @@ -55,6 +55,14 @@ v.visitConstant(this); } + @Override + public BooleanNode negate() { + if (kind != CiKind.Boolean) { + throw new IllegalStateException(); + } + return Constant.forBoolean(!value.asBoolean(), graph()); + } + /** * Creates an instruction for a double constant. * @param d the double value for which to create the instruction @@ -193,7 +201,6 @@ @Override public Node copy(Graph into) { - Constant x = new Constant(value, into); - return x; + return new Constant(value, into); } } diff -r 222f60eb09a7 -r b6282786e163 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FixedGuard.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FixedGuard.java Tue Jun 28 16:59:56 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FixedGuard.java Wed Jun 29 15:45:20 2011 +0200 @@ -22,7 +22,10 @@ */ package com.oracle.max.graal.compiler.ir; +import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.ir.Deoptimize.DeoptAction; +import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.CanonicalizerOp; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -62,4 +65,35 @@ public Node copy(Graph into) { return new FixedGuard(into); } + + @SuppressWarnings("unchecked") + @Override + public T lookup(Class clazz) { + if (clazz == CanonicalizerOp.class) { + return (T) CANONICALIZER; + } + return super.lookup(clazz); + } + + private static CanonicalizerOp CANONICALIZER = new CanonicalizerOp() { + @Override + public Node canonical(Node node) { + FixedGuard fixedGuard = (FixedGuard) node; + if (fixedGuard.node() instanceof Constant) { + Constant c = (Constant) fixedGuard.node(); + if (c.asConstant().asBoolean()) { + if (GraalOptions.TraceCanonicalizer) { + TTY.println("Removing redundant fixed guard " + fixedGuard); + } + return fixedGuard.next(); + } else { + if (GraalOptions.TraceCanonicalizer) { + TTY.println("Replacing fixed guard " + fixedGuard + " with deoptimization node"); + } + return new Deoptimize(DeoptAction.InvalidateRecompile, fixedGuard.graph()); + } + } + return fixedGuard; + } + }; } diff -r 222f60eb09a7 -r b6282786e163 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/GuardNode.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/GuardNode.java Tue Jun 28 16:59:56 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/GuardNode.java Wed Jun 29 15:45:20 2011 +0200 @@ -22,7 +22,10 @@ */ package com.oracle.max.graal.compiler.ir; +import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.ir.Deoptimize.*; +import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -64,11 +67,37 @@ @Override public void print(LogStream out) { - out.print("clip node ").print(node()); + out.print("guard node ").print(node()); } @Override public Node copy(Graph into) { return new GuardNode(into); } + + @SuppressWarnings("unchecked") + @Override + public T lookup(Class clazz) { + if (clazz == CanonicalizerOp.class) { + return (T) CANONICALIZER; + } + return super.lookup(clazz); + } + + private static CanonicalizerOp CANONICALIZER = new CanonicalizerOp() { + @Override + public Node canonical(Node node) { + GuardNode guard = (GuardNode) node; + if (guard.node() instanceof Constant) { + Constant c = (Constant) guard.node(); + if (c.asConstant().asBoolean()) { + if (GraalOptions.TraceCanonicalizer) { + TTY.println("Removing redundant floating guard " + guard); + } + return Node.Null; + } + } + return guard; + } + }; } diff -r 222f60eb09a7 -r b6282786e163 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/If.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/If.java Tue Jun 28 16:59:56 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/If.java Wed Jun 29 15:45:20 2011 +0200 @@ -22,7 +22,9 @@ */ package com.oracle.max.graal.compiler.ir; +import com.oracle.max.graal.compiler.*; import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.CanonicalizerOp; import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; @@ -112,4 +114,35 @@ public Node copy(Graph into) { return new If(null, into); } + + @SuppressWarnings("unchecked") + @Override + public T lookup(Class clazz) { + if (clazz == CanonicalizerOp.class) { + return (T) CANONICALIZER; + } + return super.lookup(clazz); + } + + private static CanonicalizerOp CANONICALIZER = new CanonicalizerOp() { + @Override + public Node canonical(Node node) { + If ifNode = (If) node; + if (ifNode.compare() instanceof Constant) { + Constant c = (Constant) ifNode.compare(); + if (c.asConstant().asBoolean()) { + if (GraalOptions.TraceCanonicalizer) { + TTY.println("Replacing if " + ifNode + " with true branch"); + } + return ifNode.trueSuccessor(); + } else { + if (GraalOptions.TraceCanonicalizer) { + TTY.println("Replacing if " + ifNode + " with false branch"); + } + return ifNode.falseSuccessor(); + } + } + return ifNode; + } + }; } diff -r 222f60eb09a7 -r b6282786e163 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Tue Jun 28 16:59:56 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Wed Jun 29 15:45:20 2011 +0200 @@ -43,7 +43,6 @@ } } } - assert false : "LoopBegin should always have a LoopEnd"; return null; } @@ -64,8 +63,7 @@ @Override public Node copy(Graph into) { - LoopBegin x = new LoopBegin(into); - return x; + return new LoopBegin(into); } @Override diff -r 222f60eb09a7 -r b6282786e163 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Tue Jun 28 16:59:56 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java Wed Jun 29 15:45:20 2011 +0200 @@ -35,54 +35,29 @@ private NodeFlood flood; private Graph graph; - private ArrayList brokenLoops; @Override protected void run(Graph graph) { this.graph = graph; this.flood = graph.createNodeFlood(); - this.brokenLoops = new ArrayList(); - - // remove chained Merges - for (Merge merge : graph.getNodes(Merge.class)) { - if (merge.endCount() == 1 && merge.usages().size() == 0 && !(merge instanceof LoopBegin)) { - FixedNode next = merge.next(); - EndNode endNode = merge.endAt(0); - merge.delete(); - endNode.replaceAndDelete(next); - } - } - // remove if nodes with constant-value comparison -// for (If ifNode : graph.getNodes(If.class)) { -// Compare compare = ifNode.compare(); -// if (compare.x().isConstant() && compare.y().isConstant()) { -// CiConstant constX = compare.x().asConstant(); -// CiConstant constY = compare.y().asConstant(); -// Boolean result = compare.condition().foldCondition(constX, constY, GraalCompilation.compilation().runtime); -// if (result != null) { -// Node actualSuccessor = result ? ifNode.trueSuccessor() : ifNode.falseSuccessor(); -// ifNode.replace(actualSuccessor); -// } else { -// TTY.println("if not removed %s %s %s (%s %s)", constX, compare.condition(), constY, constX.kind, constY.kind); -// } -// } -// } flood.add(graph.start()); - iterateSuccessors(); disconnectCFGNodes(); iterateInputs(); disconnectNodes(); deleteNodes(); - deleteBrokenLoops(); + // remove chained Merges + for (Merge merge : graph.getNodes(Merge.class)) { + if (merge.endCount() == 1 && !(merge instanceof LoopBegin)) { + replacePhis(merge); + merge.endAt(0).replaceAndDelete(merge.next()); + merge.delete(); + } + } new PhiSimplifier(graph); - - if (GraalOptions.TraceDeadCodeElimination) { - TTY.println("dead code elimination finished"); - } } private void iterateSuccessors() { @@ -108,20 +83,28 @@ // We are a dead end node leading to a live merge. merge.removeEnd(end); } + } else if (node instanceof LoopEnd) { + LoopBegin loop = ((LoopEnd) node).loopBegin(); + if (flood.isMarked(loop)) { + if (GraalOptions.TraceDeadCodeElimination) { + TTY.println("Building loop begin node back: " + loop); + } + ((LoopEnd) node).setLoopBegin(null); + EndNode endNode = loop.endAt(0); + assert endNode.predecessors().size() == 1 : endNode.predecessors().size(); + replacePhis(loop); + endNode.replaceAndDelete(loop.next()); + loop.delete(); + } } } } } - private void deleteBrokenLoops() { - for (LoopBegin loop : brokenLoops) { - assert loop.predecessors().size() == 1; - for (Node usage : new ArrayList(loop.usages())) { - assert usage instanceof Phi; - usage.replaceAndDelete(((Phi) usage).valueAt(0)); - } - - loop.replaceAndDelete(loop.next()); + private void replacePhis(Merge merge) { + for (Node usage : new ArrayList(merge.usages())) { + assert usage instanceof Phi; + usage.replaceAndDelete(((Phi) usage).valueAt(0)); } } diff -r 222f60eb09a7 -r b6282786e163 graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java --- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jun 28 16:59:56 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Wed Jun 29 15:45:20 2011 +0200 @@ -1148,7 +1148,7 @@ lastInstr = null; return fixed; } - } else { + } else if (prev != cur) { prev.replaceAtPredecessors(fixed); lastInstr = null; return fixed;