Mercurial > hg > truffle
changeset 5675:776366f3a41a
A bit of work on counted loops
Introduce FullUnroll phase before EscapeAnalysis
split Loop transforms into 2 phase : things that run before lowering, and things that run after lowering
Introduce Reassociate invariants after lowering
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Thu Jun 21 16:31:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Thu Jun 21 16:35:23 2012 +0200 @@ -134,7 +134,6 @@ if (GraalOptions.Inline && !plan.isPhaseDisabled(InliningPhase.class)) { new InliningPhase(target, runtime, null, assumptions, cache, plan, optimisticOpts).apply(graph); - new DeadCodeEliminationPhase().apply(graph); new PhiStampPhase().apply(graph); if (GraalOptions.PropagateTypes) { @@ -153,19 +152,17 @@ plan.runPhases(PhasePosition.HIGH_LEVEL, graph); + if (GraalOptions.FullUnroll) { + new LoopFullUnrollPhase().apply(graph); + } + if (GraalOptions.EscapeAnalysis && !plan.isPhaseDisabled(EscapeAnalysisPhase.class)) { new EscapeAnalysisPhase(target, runtime, assumptions, cache, plan, optimisticOpts).apply(graph); new PhiStampPhase().apply(graph); - if (GraalOptions.OptCanonicalizer) { - new CanonicalizerPhase(target, runtime, assumptions).apply(graph); - } } - if (GraalOptions.OptLoops) { - if (GraalOptions.OptLoopTransform) { - new LoopTransformPhase().apply(graph); - } + if (GraalOptions.OptLoopTransform) { + new LoopTransformHighPhase().apply(graph); } - new RemoveValueProxyPhase().apply(graph); if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase(target, runtime, assumptions).apply(graph); } @@ -191,15 +188,26 @@ new CheckCastEliminationPhase().apply(graph); } + if (GraalOptions.OptLoopTransform) { + new LoopTransformLowPhase().apply(graph); + } + new RemoveValueProxyPhase().apply(graph); if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase(target, runtime, assumptions).apply(graph); } - new DeadCodeEliminationPhase().apply(graph); + if (GraalOptions.CheckCastElimination) { + new CheckCastEliminationPhase().apply(graph); + } + plan.runPhases(PhasePosition.MID_LEVEL, graph); plan.runPhases(PhasePosition.LOW_LEVEL, graph); + new DeadCodeEliminationPhase().apply(graph); + if (GraalOptions.OptCanonicalizer) { + new CanonicalizerPhase(target, runtime, assumptions).apply(graph); + } // Add safepoints to loops if (GraalOptions.GenLoopSafepoints) { new LoopSafepointInsertionPhase().apply(graph);
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java Thu Jun 21 16:31:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java Thu Jun 21 16:35:23 2012 +0200 @@ -200,7 +200,6 @@ public static boolean OptReadElimination = true; public static boolean OptGVN = true; public static boolean OptCanonicalizer = true; - public static boolean OptLoops = true; public static boolean ScheduleOutOfLoops = true; public static boolean OptReorderLoops = true; public static boolean OptEliminateGuards = true; @@ -209,6 +208,11 @@ public static boolean OptLoopTransform = true; public static boolean OptSafepointElimination = true; + // Loops + public static boolean ReassociateInvariants = true; + public static boolean FullUnroll = true; + public static int FullUnrollMaxNodes = 250; // TODO (gd) tune + /** * Insert a counter in the method prologue to track the most frequently called methods that were compiled by Graal. */
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/CountedLoopInfo.java Thu Jun 21 16:31:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/CountedLoopInfo.java Thu Jun 21 16:35:23 2012 +0200 @@ -22,6 +22,7 @@ */ package com.oracle.graal.compiler.loop; +import com.oracle.graal.compiler.loop.InductionVariable.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; @@ -29,14 +30,17 @@ private final LoopEx loop; private InductionVariable iv; private ValueNode end; + private boolean oneOff; - CountedLoopInfo(LoopEx loop, InductionVariable iv, ValueNode end) { + CountedLoopInfo(LoopEx loop, InductionVariable iv, ValueNode end, boolean oneOff) { this.loop = loop; this.iv = iv; this.end = end; + this.oneOff = oneOff; } public ValueNode maxTripCountNode() { + //TODO (gd) stuarte and respect oneOff return IntegerArithmeticNode.div(IntegerArithmeticNode.sub(end, iv.initNode()), iv.strideNode()); } @@ -45,7 +49,9 @@ } public long constantMaxTripCount() { - return (((ConstantNode) end).asConstant().asLong() - iv.constantInit()) / iv.constantStride(); + long off = oneOff ? iv.direction() == Direction.Up ? 1 : -1 : 0; + long max = (((ConstantNode) end).asConstant().asLong() + off - iv.constantInit()) / iv.constantStride(); + return Math.max(0, max); } public boolean isExactTripCount() { @@ -66,4 +72,9 @@ assert isExactTripCount(); return constantMaxTripCount(); } + + @Override + public String toString() { + return "iv=" + iv + " until " + end + (oneOff ? iv.direction() == Direction.Up ? "+1" : "-1" : ""); + } }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java Thu Jun 21 16:31:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopEx.java Thu Jun 21 16:35:23 2012 +0200 @@ -22,9 +22,14 @@ */ package com.oracle.graal.compiler.loop; +import com.oracle.graal.api.code.*; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; +import com.oracle.graal.graph.iterators.*; import com.oracle.graal.lir.cfg.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; public class LoopEx { private final Loop lirLoop; @@ -105,6 +110,32 @@ @Override public String toString() { - return isCounted() ? "Counted" : "" + "Loop (depth=" + lirLoop().depth + ") " + loopBegin(); + return (isCounted() ? "CountedLoop [" + counted() + "] " : "Loop ") + "(depth=" + lirLoop().depth + ") " + loopBegin(); + } + + private class InvariantPredicate extends NodePredicate { + @Override + public boolean apply(Node n) { + return isOutsideLoop(n); + } + } + + public void reassociateInvariants() { + InvariantPredicate invariant = new InvariantPredicate(); + StructuredGraph graph = (StructuredGraph) loopBegin().graph(); + for (BinaryNode binary : whole().nodes().filter(BinaryNode.class)) { + if (!BinaryNode.canTryReassociate(binary)) { + continue; + } + BinaryNode result = BinaryNode.reassociate(binary, invariant); + if (result != binary) { + Debug.log(CodeUtil.format("%H::%n", Debug.contextLookup(ResolvedJavaMethod.class)) + " : Reassociated %s into %s", binary, result); + graph.replaceFloating(binary, result); + } + } + } + + public void setCounted(CountedLoopInfo countedLoopInfo) { + counted = countedLoopInfo; } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopPolicies.java Thu Jun 21 16:35:23 2012 +0200 @@ -0,0 +1,49 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.loop; + +import com.oracle.graal.compiler.*; +import com.oracle.graal.nodes.*; + + +public abstract class LoopPolicies { + private LoopPolicies() { + // does not need to be instantiated + } + + // TODO (gd) change when inversion is available + public static boolean shouldPeel(LoopEx loop) { + LoopBeginNode loopBegin = loop.loopBegin(); + double entryProbability = loopBegin.forwardEnd().probability(); + return entryProbability > GraalOptions.MinimumPeelProbability && loop.size() + loopBegin.graph().getNodeCount() < GraalOptions.MaximumDesiredSize; + } + + public static boolean shouldFullUnroll(LoopEx loop) { + if (!loop.isCounted() || !loop.counted().isConstantMaxTripCount()) { + return false; + } + long exactTrips = loop.counted().constantMaxTripCount(); + int maxNodes = Math.min(GraalOptions.FullUnrollMaxNodes, GraalOptions.MaximumDesiredSize - loop.loopBegin().graph().getNodeCount()); + return loop.size() * exactTrips <= maxNodes; + } +}
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java Thu Jun 21 16:31:10 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/loop/LoopsData.java Thu Jun 21 16:35:23 2012 +0200 @@ -23,6 +23,7 @@ package com.oracle.graal.compiler.loop; import java.util.*; +import java.util.concurrent.*; import com.oracle.graal.compiler.loop.InductionVariable.*; import com.oracle.graal.debug.*; @@ -35,8 +36,14 @@ private Map<Loop, LoopEx> lirLoopToEx = new IdentityHashMap<>(); private Map<LoopBeginNode, LoopEx> loopBeginToEx = new IdentityHashMap<>(); - public LoopsData(StructuredGraph graph) { - ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, false); + public LoopsData(final StructuredGraph graph) { + + ControlFlowGraph cfg = Debug.scope("ControlFlowGraph", new Callable<ControlFlowGraph>() { + @Override + public ControlFlowGraph call() throws Exception { + return ControlFlowGraph.compute(graph, true, true, true, false); + } + }); for (Loop lirLoop : cfg.getLoops()) { LoopEx ex = new LoopEx(lirLoop, this); lirLoopToEx.put(lirLoop, ex); @@ -139,8 +146,7 @@ break; default: throw GraalInternalError.shouldNotReachHere(); } - // TODO (gd) - Debug.log("absorb %b %s", oneOff, limit); + loop.setCounted(new CountedLoopInfo(loop, iv, limit, oneOff)); } } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopFullUnrollPhase.java Thu Jun 21 16:35:23 2012 +0200 @@ -0,0 +1,51 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.phases; + +import com.oracle.graal.compiler.loop.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.nodes.*; + + +public class LoopFullUnrollPhase extends Phase { + + @Override + protected void run(StructuredGraph graph) { + if (graph.hasLoops()) { + while (true) { + final LoopsData dataCounted = new LoopsData(graph); + dataCounted.detectedCountedLoops(); + for (final LoopEx loop : dataCounted.countedLoops()) { + if (LoopPolicies.shouldFullUnroll(loop)) { + Debug.log("FullUnroll %s", loop); + LoopTransformations.fullUnroll(loop); + Debug.dump(graph, "After fullUnroll %s", loop); + continue; + } + } + break; + } + } + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformHighPhase.java Thu Jun 21 16:35:23 2012 +0200 @@ -0,0 +1,44 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.phases; + +import com.oracle.graal.compiler.loop.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.nodes.*; + +public class LoopTransformHighPhase extends Phase { + + @Override + protected void run(StructuredGraph graph) { + if (graph.hasLoops()) { + LoopsData data = new LoopsData(graph); + for (LoopEx loop : data.outterFirst()) { + if (LoopPolicies.shouldPeel(loop)) { + Debug.log("Peeling %s", loop); + LoopTransformations.peel(loop); + Debug.dump(graph, "After peeling %s", loop); + } + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/LoopTransformLowPhase.java Thu Jun 21 16:35:23 2012 +0200 @@ -0,0 +1,48 @@ +/* + * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.phases; + +import com.oracle.graal.compiler.*; +import com.oracle.graal.compiler.loop.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.nodes.*; + +public class LoopTransformLowPhase extends Phase { + + @Override + protected void run(StructuredGraph graph) { + if (graph.hasLoops()) { + if (GraalOptions.ReassociateInvariants) { + final LoopsData dataReassociate = new LoopsData(graph); + Debug.scope("ReassociateInvariants", new Runnable() { + @Override + public void run() { + for (LoopEx loop : dataReassociate.loops()) { + loop.reassociateInvariants(); + } + } + }); + } + } + } +}