Mercurial > hg > graal-compiler
changeset 22992:dd3f7ad81b73
Split com.oracle.graal.loop in 2 parts, Make LoopPolicies extensible
Moved the phases out of com.oracle.graal.loop into com.oracle.graal.loop.phases.
Made LoopPolicies an interface with a default implementation.
Pass a LoopPolicies instance to the different loop phases constructors.
Add abstract classes for loop phases to hold onto the loop polcies.
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/BoxingEliminationTest.java Fri Nov 13 12:26:12 2015 -0800 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/BoxingEliminationTest.java Fri Nov 13 14:12:43 2015 +0100 @@ -26,6 +26,7 @@ import org.junit.Ignore; import org.junit.Test; +import com.oracle.graal.loop.DefaultLoopPolicies; import com.oracle.graal.loop.phases.LoopPeelingPhase; import com.oracle.graal.nodes.ReturnNode; import com.oracle.graal.nodes.StructuredGraph; @@ -326,7 +327,7 @@ canonicalizer.apply(graph, context); new InliningPhase(new CanonicalizerPhase()).apply(graph, context); if (loopPeeling) { - new LoopPeelingPhase().apply(graph); + new LoopPeelingPhase(new DefaultLoopPolicies()).apply(graph, context); } new DeadCodeEliminationPhase().apply(graph); canonicalizer.apply(graph, context);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LoopUnswitchTest.java Fri Nov 13 12:26:12 2015 -0800 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/LoopUnswitchTest.java Fri Nov 13 14:12:43 2015 +0100 @@ -28,6 +28,7 @@ import com.oracle.graal.debug.Debug.Scope; import com.oracle.graal.debug.DebugDumpScope; import com.oracle.graal.graph.Node; +import com.oracle.graal.loop.DefaultLoopPolicies; import com.oracle.graal.loop.phases.LoopUnswitchingPhase; import com.oracle.graal.nodes.StateSplit; import com.oracle.graal.nodes.StructuredGraph; @@ -128,7 +129,7 @@ final StructuredGraph graph = parseEager(snippet, AllowAssumptions.NO); final StructuredGraph referenceGraph = parseEager(referenceSnippet, AllowAssumptions.NO); - new LoopUnswitchingPhase().apply(graph); + new LoopUnswitchingPhase(new DefaultLoopPolicies()).apply(graph); // Framestates create comparison problems for (Node stateSplit : graph.getNodes().filterInterface(StateSplit.class)) {
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Fri Nov 13 12:26:12 2015 -0800 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Fri Nov 13 14:12:43 2015 +0100 @@ -28,6 +28,7 @@ import org.junit.Test; import com.oracle.graal.graph.Node; +import com.oracle.graal.loop.DefaultLoopPolicies; import com.oracle.graal.loop.phases.LoopFullUnrollPhase; import com.oracle.graal.loop.phases.LoopPeelingPhase; import com.oracle.graal.nodes.extended.ValueAnchorNode; @@ -312,7 +313,7 @@ @Test public void testFullyUnrolledLoop() { prepareGraph("testFullyUnrolledLoopSnippet", false); - new LoopFullUnrollPhase(new CanonicalizerPhase()).apply(graph, context); + new LoopFullUnrollPhase(new CanonicalizerPhase(), new DefaultLoopPolicies()).apply(graph, context); new PartialEscapePhase(false, new CanonicalizerPhase()).apply(graph, context); Assert.assertEquals(1, returnNodes.size()); Assert.assertTrue(returnNodes.get(0).result() instanceof AllocatedObjectNode); @@ -343,7 +344,7 @@ @Test public void testPeeledLoop() { prepareGraph("testPeeledLoopSnippet", false); - new LoopPeelingPhase().apply(graph); + new LoopPeelingPhase(new DefaultLoopPolicies()).apply(graph); new SchedulePhase().apply(graph); }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/HighTier.java Fri Nov 13 12:26:12 2015 -0800 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/phases/HighTier.java Fri Nov 13 14:12:43 2015 +0100 @@ -37,6 +37,8 @@ import jdk.vm.ci.options.OptionType; import jdk.vm.ci.options.OptionValue; +import com.oracle.graal.loop.DefaultLoopPolicies; +import com.oracle.graal.loop.LoopPolicies; import com.oracle.graal.loop.phases.LoopFullUnrollPhase; import com.oracle.graal.loop.phases.LoopPeelingPhase; import com.oracle.graal.loop.phases.LoopUnswitchingPhase; @@ -87,16 +89,17 @@ appendPhase(new ConvertDeoptimizeToGuardPhase()); } + LoopPolicies loopPolicies = createLoopPolicies(); if (FullUnroll.getValue()) { - appendPhase(new LoopFullUnrollPhase(canonicalizer)); + appendPhase(new LoopFullUnrollPhase(canonicalizer, loopPolicies)); } if (OptLoopTransform.getValue()) { if (LoopPeeling.getValue()) { - appendPhase(new LoopPeelingPhase()); + appendPhase(new LoopPeelingPhase(loopPolicies)); } if (LoopUnswitch.getValue()) { - appendPhase(new LoopUnswitchingPhase()); + appendPhase(new LoopUnswitchingPhase(loopPolicies)); } } @@ -114,4 +117,8 @@ appendPhase(new HighTierReconcileInstrumentationPhase()); } } + + public LoopPolicies createLoopPolicies() { + return new DefaultLoopPolicies(); + } }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/phases/OnStackReplacementPhase.java Fri Nov 13 12:26:12 2015 -0800 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/phases/OnStackReplacementPhase.java Fri Nov 13 14:12:43 2015 +0100 @@ -31,8 +31,8 @@ import com.oracle.graal.graph.Node; import com.oracle.graal.graph.iterators.NodeIterable; import com.oracle.graal.loop.LoopEx; -import com.oracle.graal.loop.LoopTransformations; import com.oracle.graal.loop.LoopsData; +import com.oracle.graal.loop.phases.LoopTransformations; import com.oracle.graal.nodeinfo.InputType; import com.oracle.graal.nodeinfo.Verbosity; import com.oracle.graal.nodes.AbstractBeginNode;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop.phases/src/com/oracle/graal/loop/phases/ContextlessLoopPhase.java Fri Nov 13 14:12:43 2015 +0100 @@ -0,0 +1,49 @@ +/* + * Copyright (c) 2015, 2015, 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.loop.phases; + +import com.oracle.graal.loop.LoopPolicies; +import com.oracle.graal.nodes.StructuredGraph; +import com.oracle.graal.phases.tiers.PhaseContext; + +public abstract class ContextlessLoopPhase<P extends LoopPolicies> extends LoopPhase<P> { + + public ContextlessLoopPhase(P policies) { + super(policies); + } + + public final void apply(final StructuredGraph graph) { + apply(graph, true); + } + + public final void apply(final StructuredGraph graph, final boolean dumpGraph) { + apply(graph, null, dumpGraph); + } + + protected abstract void run(StructuredGraph graph); + + @Override + protected final void run(StructuredGraph graph, PhaseContext context) { + run(graph); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop.phases/src/com/oracle/graal/loop/phases/LoopFullUnrollPhase.java Fri Nov 13 14:12:43 2015 +0100 @@ -0,0 +1,66 @@ +/* + * 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.loop.phases; + +import com.oracle.graal.debug.Debug; +import com.oracle.graal.debug.DebugMetric; +import com.oracle.graal.loop.LoopEx; +import com.oracle.graal.loop.LoopPolicies; +import com.oracle.graal.loop.LoopsData; +import com.oracle.graal.nodes.StructuredGraph; +import com.oracle.graal.phases.common.CanonicalizerPhase; +import com.oracle.graal.phases.tiers.PhaseContext; + +public class LoopFullUnrollPhase extends LoopPhase<LoopPolicies> { + + private static final DebugMetric FULLY_UNROLLED_LOOPS = Debug.metric("FullUnrolls"); + private final CanonicalizerPhase canonicalizer; + + public LoopFullUnrollPhase(CanonicalizerPhase canonicalizer, LoopPolicies policies) { + super(policies); + this.canonicalizer = canonicalizer; + } + + @Override + protected void run(StructuredGraph graph, PhaseContext context) { + if (graph.hasLoops()) { + boolean peeled; + do { + peeled = false; + final LoopsData dataCounted = new LoopsData(graph); + dataCounted.detectedCountedLoops(); + for (LoopEx loop : dataCounted.countedLoops()) { + if (getPolicies().shouldFullUnroll(loop)) { + Debug.log("FullUnroll %s", loop); + LoopTransformations.fullUnroll(loop, context, canonicalizer); + FULLY_UNROLLED_LOOPS.increment(); + Debug.dump(graph, "FullUnroll %s", loop); + peeled = true; + break; + } + } + dataCounted.deleteUnusedNodes(); + } while (peeled); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop.phases/src/com/oracle/graal/loop/phases/LoopPeelingPhase.java Fri Nov 13 14:12:43 2015 +0100 @@ -0,0 +1,51 @@ +/* + * Copyright (c) 2012, 2015, 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.loop.phases; + +import com.oracle.graal.debug.Debug; +import com.oracle.graal.loop.LoopEx; +import com.oracle.graal.loop.LoopPolicies; +import com.oracle.graal.loop.LoopsData; +import com.oracle.graal.nodes.StructuredGraph; + +public class LoopPeelingPhase extends ContextlessLoopPhase<LoopPolicies> { + + public LoopPeelingPhase(LoopPolicies policies) { + super(policies); + } + + @Override + protected void run(StructuredGraph graph) { + if (graph.hasLoops()) { + LoopsData data = new LoopsData(graph); + for (LoopEx loop : data.outerFirst()) { + if (getPolicies().shouldPeel(loop, data.getCFG())) { + Debug.log("Peeling %s", loop); + LoopTransformations.peel(loop); + Debug.dump(graph, "Peeling %s", loop); + } + } + data.deleteUnusedNodes(); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop.phases/src/com/oracle/graal/loop/phases/LoopPhase.java Fri Nov 13 14:12:43 2015 +0100 @@ -0,0 +1,39 @@ +/* + * 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.loop.phases; + +import com.oracle.graal.loop.LoopPolicies; +import com.oracle.graal.phases.BasePhase; +import com.oracle.graal.phases.tiers.PhaseContext; + +public abstract class LoopPhase<P extends LoopPolicies> extends BasePhase<PhaseContext> { + private P policies; + + public LoopPhase(P policies) { + this.policies = policies; + } + + protected P getPolicies() { + return policies; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop.phases/src/com/oracle/graal/loop/phases/LoopSafepointEliminationPhase.java Fri Nov 13 14:12:43 2015 +0100 @@ -0,0 +1,73 @@ +/* + * Copyright (c) 2011, 2013, 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.loop.phases; + +import com.oracle.graal.loop.LoopEx; +import com.oracle.graal.loop.LoopsData; +import com.oracle.graal.nodes.FixedNode; +import com.oracle.graal.nodes.Invoke; +import com.oracle.graal.nodes.LoopEndNode; +import com.oracle.graal.nodes.StructuredGraph; +import com.oracle.graal.nodes.cfg.Block; +import com.oracle.graal.nodes.extended.ForeignCallNode; +import com.oracle.graal.phases.BasePhase; +import com.oracle.graal.phases.tiers.MidTierContext; + +public class LoopSafepointEliminationPhase extends BasePhase<MidTierContext> { + + @Override + protected void run(StructuredGraph graph, MidTierContext context) { + LoopsData loops = new LoopsData(graph); + if (context.getOptimisticOptimizations().useLoopLimitChecks() && graph.getGuardsStage().allowsFloatingGuards()) { + loops.detectedCountedLoops(); + for (LoopEx loop : loops.countedLoops()) { + if (loop.loop().getChildren().isEmpty() && loop.counted().getStamp().getBits() <= 32) { + boolean hasSafepoint = false; + for (LoopEndNode loopEnd : loop.loopBegin().loopEnds()) { + hasSafepoint |= loopEnd.canSafepoint(); + } + if (hasSafepoint) { + loop.counted().createOverFlowGuard(); + loop.loopBegin().disableSafepoint(); + } + } + } + } + for (LoopEx loop : loops.countedLoops()) { + for (LoopEndNode loopEnd : loop.loopBegin().loopEnds()) { + Block b = loops.getCFG().blockFor(loopEnd); + blocks: while (b != loop.loop().getHeader()) { + assert b != null; + for (FixedNode node : b.getNodes()) { + if (node instanceof Invoke || node instanceof ForeignCallNode) { + loopEnd.disableSafepoint(); + break blocks; + } + } + b = b.getDominator(); + } + } + } + loops.deleteUnusedNodes(); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop.phases/src/com/oracle/graal/loop/phases/LoopTransformations.java Fri Nov 13 14:12:43 2015 +0100 @@ -0,0 +1,159 @@ +/* + * 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.loop.phases; + +import static com.oracle.graal.compiler.common.GraalOptions.MaximumDesiredSize; + +import java.util.ArrayList; +import java.util.List; + +import com.oracle.graal.graph.Graph.Mark; +import com.oracle.graal.graph.NodePosIterator; +import com.oracle.graal.graph.Position; +import com.oracle.graal.loop.LoopEx; +import com.oracle.graal.loop.LoopFragmentWhole; +import com.oracle.graal.nodeinfo.InputType; +import com.oracle.graal.nodes.AbstractBeginNode; +import com.oracle.graal.nodes.BeginNode; +import com.oracle.graal.nodes.ControlSplitNode; +import com.oracle.graal.nodes.IfNode; +import com.oracle.graal.nodes.LoopBeginNode; +import com.oracle.graal.nodes.StructuredGraph; +import com.oracle.graal.nodes.ValueNode; +import com.oracle.graal.nodes.extended.SwitchNode; +import com.oracle.graal.phases.common.CanonicalizerPhase; +import com.oracle.graal.phases.tiers.PhaseContext; + +import jdk.vm.ci.code.BailoutException; + +public abstract class LoopTransformations { + + private LoopTransformations() { + // does not need to be instantiated + } + + public static void peel(LoopEx loop) { + loop.inside().duplicate().insertBefore(loop); + loop.loopBegin().setLoopFrequency(Math.max(0.0, loop.loopBegin().loopFrequency() - 1)); + } + + public static void fullUnroll(LoopEx loop, PhaseContext context, CanonicalizerPhase canonicalizer) { + // assert loop.isCounted(); //TODO (gd) strenghten : counted with known trip count + LoopBeginNode loopBegin = loop.loopBegin(); + StructuredGraph graph = loopBegin.graph(); + while (!loopBegin.isDeleted()) { + Mark mark = graph.getMark(); + peel(loop); + canonicalizer.applyIncremental(graph, context, mark); + loopBegin.removeDeadPhis(); + loop.invalidateFragments(); + if (graph.getNodeCount() > MaximumDesiredSize.getValue() * 3) { + throw new BailoutException("FullUnroll : Graph seems to grow out of proportion"); + } + } + } + + public static void unswitch(LoopEx loop, List<ControlSplitNode> controlSplitNodeSet) { + ControlSplitNode firstNode = controlSplitNodeSet.iterator().next(); + LoopFragmentWhole originalLoop = loop.whole(); + StructuredGraph graph = firstNode.graph(); + + loop.loopBegin().incrementUnswitches(); + + // create new control split out of loop + ControlSplitNode newControlSplit = (ControlSplitNode) firstNode.copyWithInputs(); + originalLoop.entryPoint().replaceAtPredecessor(newControlSplit); + + /* + * The code below assumes that all of the control split nodes have the same successor + * structure, which should have been enforced by findUnswitchable. + */ + NodePosIterator successors = firstNode.successors().iterator(); + assert successors.hasNext(); + // original loop is used as first successor + Position firstPosition = successors.nextPosition(); + AbstractBeginNode originalLoopBegin = BeginNode.begin(originalLoop.entryPoint()); + firstPosition.set(newControlSplit, originalLoopBegin); + + while (successors.hasNext()) { + Position position = successors.nextPosition(); + // create a new loop duplicate and connect it. + LoopFragmentWhole duplicateLoop = originalLoop.duplicate(); + AbstractBeginNode newBegin = BeginNode.begin(duplicateLoop.entryPoint()); + position.set(newControlSplit, newBegin); + + // For each cloned ControlSplitNode, simplify the proper path + for (ControlSplitNode controlSplitNode : controlSplitNodeSet) { + ControlSplitNode duplicatedControlSplit = duplicateLoop.getDuplicatedNode(controlSplitNode); + if (duplicatedControlSplit.isAlive()) { + AbstractBeginNode survivingSuccessor = (AbstractBeginNode) position.get(duplicatedControlSplit); + survivingSuccessor.replaceAtUsages(InputType.Guard, newBegin); + graph.removeSplitPropagate(duplicatedControlSplit, survivingSuccessor); + } + } + } + // original loop is simplified last to avoid deleting controlSplitNode too early + for (ControlSplitNode controlSplitNode : controlSplitNodeSet) { + if (controlSplitNode.isAlive()) { + AbstractBeginNode survivingSuccessor = (AbstractBeginNode) firstPosition.get(controlSplitNode); + survivingSuccessor.replaceAtUsages(InputType.Guard, originalLoopBegin); + graph.removeSplitPropagate(controlSplitNode, survivingSuccessor); + } + } + + // TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms) + } + + public static List<ControlSplitNode> findUnswitchable(LoopEx loop) { + List<ControlSplitNode> controls = null; + ValueNode invariantValue = null; + for (IfNode ifNode : loop.whole().nodes().filter(IfNode.class)) { + if (loop.isOutsideLoop(ifNode.condition())) { + if (controls == null) { + invariantValue = ifNode.condition(); + controls = new ArrayList<>(); + controls.add(ifNode); + } else if (ifNode.condition() == invariantValue) { + controls.add(ifNode); + } + } + } + if (controls == null) { + SwitchNode firstSwitch = null; + for (SwitchNode switchNode : loop.whole().nodes().filter(SwitchNode.class)) { + if (switchNode.successors().count() > 1 && loop.isOutsideLoop(switchNode.value())) { + if (controls == null) { + firstSwitch = switchNode; + invariantValue = switchNode.value(); + controls = new ArrayList<>(); + controls.add(switchNode); + } else if (switchNode.value() == invariantValue && firstSwitch.structureEquals(switchNode)) { + // Only collect switches which test the same values in the same order + controls.add(switchNode); + } + } + } + } + return controls; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop.phases/src/com/oracle/graal/loop/phases/LoopUnswitchingPhase.java Fri Nov 13 14:12:43 2015 +0100 @@ -0,0 +1,92 @@ +/* + * 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.loop.phases; + +import java.util.List; + +import com.oracle.graal.debug.Debug; +import com.oracle.graal.debug.DebugMetric; +import com.oracle.graal.graph.NodePosIterator; +import com.oracle.graal.loop.LoopEx; +import com.oracle.graal.loop.LoopPolicies; +import com.oracle.graal.loop.LoopsData; +import com.oracle.graal.nodes.AbstractBeginNode; +import com.oracle.graal.nodes.ControlSplitNode; +import com.oracle.graal.nodes.StructuredGraph; + +public class LoopUnswitchingPhase extends ContextlessLoopPhase<LoopPolicies> { + private static final DebugMetric UNSWITCHED = Debug.metric("Unswitched"); + private static final DebugMetric UNSWITCH_CANDIDATES = Debug.metric("UnswitchCandidates"); + private static final DebugMetric UNSWITCH_EARLY_REJECTS = Debug.metric("UnswitchEarlyRejects"); + + public LoopUnswitchingPhase(LoopPolicies policies) { + super(policies); + } + + @Override + protected void run(StructuredGraph graph) { + if (graph.hasLoops()) { + boolean unswitched; + do { + unswitched = false; + final LoopsData dataUnswitch = new LoopsData(graph); + for (LoopEx loop : dataUnswitch.outerFirst()) { + if (getPolicies().shouldTryUnswitch(loop)) { + List<ControlSplitNode> controlSplits = LoopTransformations.findUnswitchable(loop); + if (controlSplits != null) { + UNSWITCH_CANDIDATES.increment(); + if (getPolicies().shouldUnswitch(loop, controlSplits)) { + if (Debug.isLogEnabled()) { + logUnswitch(loop, controlSplits); + } + LoopTransformations.unswitch(loop, controlSplits); + UNSWITCHED.increment(); + unswitched = true; + break; + } + } + } else { + UNSWITCH_EARLY_REJECTS.increment(); + } + } + } while (unswitched); + } + } + + private static void logUnswitch(LoopEx loop, List<ControlSplitNode> controlSplits) { + StringBuilder sb = new StringBuilder("Unswitching "); + sb.append(loop).append(" at "); + for (ControlSplitNode controlSplit : controlSplits) { + sb.append(controlSplit).append(" ["); + NodePosIterator it = controlSplit.successors().iterator(); + while (it.hasNext()) { + sb.append(controlSplit.probability((AbstractBeginNode) it.next())); + if (it.hasNext()) { + sb.append(", "); + } + } + sb.append("]"); + } + Debug.log("%s", sb); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop.phases/src/com/oracle/graal/loop/phases/ReassociateInvariantPhase.java Fri Nov 13 14:12:43 2015 +0100 @@ -0,0 +1,49 @@ +/* + * Copyright (c) 2015, 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.loop.phases; + +import com.oracle.graal.debug.Debug; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.loop.LoopEx; +import com.oracle.graal.loop.LoopsData; +import com.oracle.graal.nodes.StructuredGraph; +import com.oracle.graal.phases.Phase; + +public class ReassociateInvariantPhase extends Phase { + + @SuppressWarnings("try") + @Override + protected void run(StructuredGraph graph) { + if (graph.hasLoops()) { + final LoopsData dataReassociate = new LoopsData(graph); + try (Scope s = Debug.scope("ReassociateInvariants")) { + for (LoopEx loop : dataReassociate.loops()) { + loop.reassociateInvariants(); + } + } catch (Throwable e) { + throw Debug.handle(e); + } + dataReassociate.deleteUnusedNodes(); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/DefaultLoopPolicies.java Fri Nov 13 14:12:43 2015 +0100 @@ -0,0 +1,157 @@ +/* + * Copyright (c) 2012, 2015, 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.loop; + +import static com.oracle.graal.compiler.common.GraalOptions.LoopMaxUnswitch; +import static com.oracle.graal.compiler.common.GraalOptions.MaximumDesiredSize; +import static com.oracle.graal.compiler.common.GraalOptions.MinimumPeelProbability; + +import java.util.List; + +import jdk.vm.ci.options.Option; +import jdk.vm.ci.options.OptionType; +import jdk.vm.ci.options.OptionValue; + +import com.oracle.graal.debug.Debug; +import com.oracle.graal.debug.DebugMetric; +import com.oracle.graal.graph.Node; +import com.oracle.graal.nodes.AbstractBeginNode; +import com.oracle.graal.nodes.ControlSplitNode; +import com.oracle.graal.nodes.LoopBeginNode; +import com.oracle.graal.nodes.MergeNode; +import com.oracle.graal.nodes.VirtualState; +import com.oracle.graal.nodes.VirtualState.VirtualClosure; +import com.oracle.graal.nodes.cfg.Block; +import com.oracle.graal.nodes.cfg.ControlFlowGraph; +import com.oracle.graal.nodes.debug.ControlFlowAnchorNode; + +public class DefaultLoopPolicies implements LoopPolicies { + @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> LoopUnswitchMaxIncrease = new OptionValue<>(500); + @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> LoopUnswitchTrivial = new OptionValue<>(10); + @Option(help = "", type = OptionType.Expert) public static final OptionValue<Double> LoopUnswitchFrequencyBoost = new OptionValue<>(10.0); + + @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> FullUnrollMaxNodes = new OptionValue<>(300); + @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> FullUnrollMaxIterations = new OptionValue<>(600); + @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> ExactFullUnrollMaxNodes = new OptionValue<>(1200); + + // TODO (gd) change when inversion is available + @Override + public boolean shouldPeel(LoopEx loop, ControlFlowGraph cfg) { + if (loop.detectCounted()) { + return false; + } + LoopBeginNode loopBegin = loop.loopBegin(); + double entryProbability = cfg.blockFor(loopBegin.forwardEnd()).probability(); + if (entryProbability > MinimumPeelProbability.getValue() && loop.size() + loopBegin.graph().getNodeCount() < MaximumDesiredSize.getValue()) { + // check whether we're allowed to peel this loop + for (Node node : loop.inside().nodes()) { + if (node instanceof ControlFlowAnchorNode) { + return false; + } + } + return true; + } else { + return false; + } + } + + @Override + public boolean shouldFullUnroll(LoopEx loop) { + if (!loop.isCounted() || !loop.counted().isConstantMaxTripCount()) { + return false; + } + CountedLoopInfo counted = loop.counted(); + long maxTrips = counted.constantMaxTripCount(); + int maxNodes = (counted.isExactTripCount() && counted.isConstantExactTripCount()) ? ExactFullUnrollMaxNodes.getValue() : FullUnrollMaxNodes.getValue(); + maxNodes = Math.min(maxNodes, MaximumDesiredSize.getValue() - loop.loopBegin().graph().getNodeCount()); + int size = Math.max(1, loop.size() - 1 - loop.loopBegin().phis().count()); + if (maxTrips <= FullUnrollMaxIterations.getValue() && size * maxTrips <= maxNodes) { + // check whether we're allowed to unroll this loop + for (Node node : loop.inside().nodes()) { + if (node instanceof ControlFlowAnchorNode) { + return false; + } + } + return true; + } else { + return false; + } + } + + @Override + public boolean shouldTryUnswitch(LoopEx loop) { + LoopBeginNode loopBegin = loop.loopBegin(); + double loopFrequency = loopBegin.loopFrequency(); + if (loopFrequency <= 1.0) { + return false; + } + return loopBegin.unswitches() <= LoopMaxUnswitch.getValue(); + } + + private static final class CountingClosure implements VirtualClosure { + int count; + + public void apply(VirtualState node) { + count++; + } + } + + private static class IsolatedInitialization { + static final DebugMetric UNSWITCH_SPLIT_WITH_PHIS = Debug.metric("UnswitchSplitWithPhis"); + } + + @Override + public boolean shouldUnswitch(LoopEx loop, List<ControlSplitNode> controlSplits) { + int inBranchTotal = 0; + int phis = 0; + for (ControlSplitNode controlSplit : controlSplits) { + for (Node successor : controlSplit.successors()) { + AbstractBeginNode branch = (AbstractBeginNode) successor; + // this may count twice because of fall-through in switches + inBranchTotal += loop.nodesInLoopBranch(branch).count(); + } + Block postDomBlock = loop.loopsData().getCFG().blockFor(controlSplit).getPostdominator(); + if (postDomBlock != null) { + IsolatedInitialization.UNSWITCH_SPLIT_WITH_PHIS.increment(); + phis += ((MergeNode) postDomBlock.getBeginNode()).phis().count(); + } + } + + CountingClosure stateNodesCount = new CountingClosure(); + double loopFrequency = loop.loopBegin().loopFrequency(); + int maxDiff = LoopUnswitchTrivial.getValue() + (int) (LoopUnswitchFrequencyBoost.getValue() * (loopFrequency - 1.0 + phis)); + + maxDiff = Math.min(maxDiff, LoopUnswitchMaxIncrease.getValue()); + int remainingGraphSpace = MaximumDesiredSize.getValue() - loop.loopBegin().graph().getNodeCount(); + maxDiff = Math.min(maxDiff, remainingGraphSpace); + + loop.loopBegin().stateAfter().applyToVirtual(stateNodesCount); + int loopTotal = loop.size() - loop.loopBegin().phis().count() - stateNodesCount.count - 1; + int actualDiff = loopTotal - inBranchTotal; + + Debug.log("shouldUnswitch(%s, %s) : delta=%d (%.2f%% inside of branches), max=%d, f=%.2f, phis=%d -> %b", loop, controlSplits, actualDiff, (double) (inBranchTotal) / loopTotal * 100, maxDiff, + loopFrequency, phis, actualDiff <= maxDiff); + return actualDiff <= maxDiff; + } + +}
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Fri Nov 13 12:26:12 2015 -0800 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Fri Nov 13 14:12:43 2015 +0100 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2015, 2015, 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 @@ -22,136 +22,17 @@ */ package com.oracle.graal.loop; -import static com.oracle.graal.compiler.common.GraalOptions.LoopMaxUnswitch; -import static com.oracle.graal.compiler.common.GraalOptions.MaximumDesiredSize; -import static com.oracle.graal.compiler.common.GraalOptions.MinimumPeelProbability; - import java.util.List; -import jdk.vm.ci.options.Option; -import jdk.vm.ci.options.OptionType; -import jdk.vm.ci.options.OptionValue; - -import com.oracle.graal.debug.Debug; -import com.oracle.graal.debug.DebugMetric; -import com.oracle.graal.graph.Node; -import com.oracle.graal.nodes.AbstractBeginNode; import com.oracle.graal.nodes.ControlSplitNode; -import com.oracle.graal.nodes.LoopBeginNode; -import com.oracle.graal.nodes.MergeNode; -import com.oracle.graal.nodes.VirtualState; -import com.oracle.graal.nodes.VirtualState.VirtualClosure; -import com.oracle.graal.nodes.cfg.Block; import com.oracle.graal.nodes.cfg.ControlFlowGraph; -import com.oracle.graal.nodes.debug.ControlFlowAnchorNode; - -public abstract class LoopPolicies { - @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> LoopUnswitchMaxIncrease = new OptionValue<>(500); - @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> LoopUnswitchTrivial = new OptionValue<>(10); - @Option(help = "", type = OptionType.Expert) public static final OptionValue<Double> LoopUnswitchFrequencyBoost = new OptionValue<>(10.0); - @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> FullUnrollMaxNodes = new OptionValue<>(300); - @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> FullUnrollMaxIterations = new OptionValue<>(600); - @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> ExactFullUnrollMaxNodes = new OptionValue<>(1200); - - private LoopPolicies() { - // does not need to be instantiated - } - - // TODO (gd) change when inversion is available - public static boolean shouldPeel(LoopEx loop, ControlFlowGraph cfg) { - if (loop.detectCounted()) { - return false; - } - LoopBeginNode loopBegin = loop.loopBegin(); - double entryProbability = cfg.blockFor(loopBegin.forwardEnd()).probability(); - if (entryProbability > MinimumPeelProbability.getValue() && loop.size() + loopBegin.graph().getNodeCount() < MaximumDesiredSize.getValue()) { - // check whether we're allowed to peel this loop - for (Node node : loop.inside().nodes()) { - if (node instanceof ControlFlowAnchorNode) { - return false; - } - } - return true; - } else { - return false; - } - } +public interface LoopPolicies { + boolean shouldPeel(LoopEx loop, ControlFlowGraph cfg); - public static boolean shouldFullUnroll(LoopEx loop) { - if (!loop.isCounted() || !loop.counted().isConstantMaxTripCount()) { - return false; - } - CountedLoopInfo counted = loop.counted(); - long maxTrips = counted.constantMaxTripCount(); - int maxNodes = (counted.isExactTripCount() && counted.isConstantExactTripCount()) ? ExactFullUnrollMaxNodes.getValue() : FullUnrollMaxNodes.getValue(); - maxNodes = Math.min(maxNodes, MaximumDesiredSize.getValue() - loop.loopBegin().graph().getNodeCount()); - int size = Math.max(1, loop.size() - 1 - loop.loopBegin().phis().count()); - if (size * maxTrips <= maxNodes) { - // check whether we're allowed to unroll this loop - for (Node node : loop.inside().nodes()) { - if (node instanceof ControlFlowAnchorNode) { - return false; - } - } - return true; - } else { - return false; - } - } - - public static boolean shouldTryUnswitch(LoopEx loop) { - LoopBeginNode loopBegin = loop.loopBegin(); - double loopFrequency = loopBegin.loopFrequency(); - if (loopFrequency <= 1.0) { - return false; - } - return loopBegin.unswitches() <= LoopMaxUnswitch.getValue(); - } - - private static final class CountingClosure implements VirtualClosure { - int count; - - public void apply(VirtualState node) { - count++; - } - } + boolean shouldFullUnroll(LoopEx loop); - private static class IsolatedInitialization { - static final DebugMetric UNSWITCH_SPLIT_WITH_PHIS = Debug.metric("UnswitchSplitWithPhis"); - } + boolean shouldTryUnswitch(LoopEx loop); - public static boolean shouldUnswitch(LoopEx loop, List<ControlSplitNode> controlSplits) { - int inBranchTotal = 0; - int phis = 0; - for (ControlSplitNode controlSplit : controlSplits) { - for (Node successor : controlSplit.successors()) { - AbstractBeginNode branch = (AbstractBeginNode) successor; - // this may count twice because of fall-through in switches - inBranchTotal += loop.nodesInLoopBranch(branch).count(); - } - Block postDomBlock = loop.loopsData().getCFG().blockFor(controlSplit).getPostdominator(); - if (postDomBlock != null) { - IsolatedInitialization.UNSWITCH_SPLIT_WITH_PHIS.increment(); - phis += ((MergeNode) postDomBlock.getBeginNode()).phis().count(); - } - } - - CountingClosure stateNodesCount = new CountingClosure(); - double loopFrequency = loop.loopBegin().loopFrequency(); - int maxDiff = LoopUnswitchTrivial.getValue() + (int) (LoopUnswitchFrequencyBoost.getValue() * (loopFrequency - 1.0 + phis)); - - maxDiff = Math.min(maxDiff, LoopUnswitchMaxIncrease.getValue()); - int remainingGraphSpace = MaximumDesiredSize.getValue() - loop.loopBegin().graph().getNodeCount(); - maxDiff = Math.min(maxDiff, remainingGraphSpace); - - loop.loopBegin().stateAfter().applyToVirtual(stateNodesCount); - int loopTotal = loop.size() - loop.loopBegin().phis().count() - stateNodesCount.count - 1; - int actualDiff = loopTotal - inBranchTotal; - - Debug.log("shouldUnswitch(%s, %s) : delta=%d (%.2f%% inside of branches), max=%d, f=%.2f, phis=%d -> %b", loop, controlSplits, actualDiff, (double) (inBranchTotal) / loopTotal * 100, maxDiff, - loopFrequency, phis, actualDiff <= maxDiff); - return actualDiff <= maxDiff; - } - + boolean shouldUnswitch(LoopEx loop, List<ControlSplitNode> controlSplits); }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopTransformations.java Fri Nov 13 12:26:12 2015 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,158 +0,0 @@ -/* - * 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.loop; - -import static com.oracle.graal.compiler.common.GraalOptions.MaximumDesiredSize; - -import java.util.ArrayList; -import java.util.List; - -import jdk.vm.ci.code.BailoutException; - -import com.oracle.graal.graph.Graph.Mark; -import com.oracle.graal.graph.NodePosIterator; -import com.oracle.graal.graph.Position; -import com.oracle.graal.nodeinfo.InputType; -import com.oracle.graal.nodes.AbstractBeginNode; -import com.oracle.graal.nodes.BeginNode; -import com.oracle.graal.nodes.ControlSplitNode; -import com.oracle.graal.nodes.IfNode; -import com.oracle.graal.nodes.LoopBeginNode; -import com.oracle.graal.nodes.StructuredGraph; -import com.oracle.graal.nodes.ValueNode; -import com.oracle.graal.nodes.extended.SwitchNode; -import com.oracle.graal.phases.common.CanonicalizerPhase; -import com.oracle.graal.phases.tiers.PhaseContext; - -public abstract class LoopTransformations { - - private LoopTransformations() { - // does not need to be instantiated - } - - public static void peel(LoopEx loop) { - loop.inside().duplicate().insertBefore(loop); - loop.loopBegin().setLoopFrequency(Math.max(0.0, loop.loopBegin().loopFrequency() - 1)); - } - - public static void fullUnroll(LoopEx loop, PhaseContext context, CanonicalizerPhase canonicalizer) { - // assert loop.isCounted(); //TODO (gd) strenghten : counted with known trip count - int iterations = 0; - LoopBeginNode loopBegin = loop.loopBegin(); - StructuredGraph graph = loopBegin.graph(); - while (!loopBegin.isDeleted()) { - Mark mark = graph.getMark(); - peel(loop); - canonicalizer.applyIncremental(graph, context, mark); - loopBegin.removeDeadPhis(); - loop.invalidateFragments(); - if (iterations++ > LoopPolicies.FullUnrollMaxIterations.getValue() || graph.getNodeCount() > MaximumDesiredSize.getValue() * 3) { - throw new BailoutException("FullUnroll : Graph seems to grow out of proportion"); - } - } - } - - public static void unswitch(LoopEx loop, List<ControlSplitNode> controlSplitNodeSet) { - ControlSplitNode firstNode = controlSplitNodeSet.iterator().next(); - LoopFragmentWhole originalLoop = loop.whole(); - StructuredGraph graph = firstNode.graph(); - - loop.loopBegin().incrementUnswitches(); - - // create new control split out of loop - ControlSplitNode newControlSplit = (ControlSplitNode) firstNode.copyWithInputs(); - originalLoop.entryPoint().replaceAtPredecessor(newControlSplit); - - /* - * The code below assumes that all of the control split nodes have the same successor - * structure, which should have been enforced by findUnswitchable. - */ - NodePosIterator successors = firstNode.successors().iterator(); - assert successors.hasNext(); - // original loop is used as first successor - Position firstPosition = successors.nextPosition(); - AbstractBeginNode originalLoopBegin = BeginNode.begin(originalLoop.entryPoint()); - firstPosition.set(newControlSplit, originalLoopBegin); - - while (successors.hasNext()) { - Position position = successors.nextPosition(); - // create a new loop duplicate and connect it. - LoopFragmentWhole duplicateLoop = originalLoop.duplicate(); - AbstractBeginNode newBegin = BeginNode.begin(duplicateLoop.entryPoint()); - position.set(newControlSplit, newBegin); - - // For each cloned ControlSplitNode, simplify the proper path - for (ControlSplitNode controlSplitNode : controlSplitNodeSet) { - ControlSplitNode duplicatedControlSplit = duplicateLoop.getDuplicatedNode(controlSplitNode); - if (duplicatedControlSplit.isAlive()) { - AbstractBeginNode survivingSuccessor = (AbstractBeginNode) position.get(duplicatedControlSplit); - survivingSuccessor.replaceAtUsages(InputType.Guard, newBegin); - graph.removeSplitPropagate(duplicatedControlSplit, survivingSuccessor); - } - } - } - // original loop is simplified last to avoid deleting controlSplitNode too early - for (ControlSplitNode controlSplitNode : controlSplitNodeSet) { - if (controlSplitNode.isAlive()) { - AbstractBeginNode survivingSuccessor = (AbstractBeginNode) firstPosition.get(controlSplitNode); - survivingSuccessor.replaceAtUsages(InputType.Guard, originalLoopBegin); - graph.removeSplitPropagate(controlSplitNode, survivingSuccessor); - } - } - - // TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms) - } - - public static List<ControlSplitNode> findUnswitchable(LoopEx loop) { - List<ControlSplitNode> controls = null; - ValueNode invariantValue = null; - for (IfNode ifNode : loop.whole().nodes().filter(IfNode.class)) { - if (loop.isOutsideLoop(ifNode.condition())) { - if (controls == null) { - invariantValue = ifNode.condition(); - controls = new ArrayList<>(); - controls.add(ifNode); - } else if (ifNode.condition() == invariantValue) { - controls.add(ifNode); - } - } - } - if (controls == null) { - SwitchNode firstSwitch = null; - for (SwitchNode switchNode : loop.whole().nodes().filter(SwitchNode.class)) { - if (switchNode.successors().count() > 1 && loop.isOutsideLoop(switchNode.value())) { - if (controls == null) { - firstSwitch = switchNode; - invariantValue = switchNode.value(); - controls = new ArrayList<>(); - controls.add(switchNode); - } else if (switchNode.value() == invariantValue && firstSwitch.structureEquals(switchNode)) { - // Only collect switches which test the same values in the same order - controls.add(switchNode); - } - } - } - } - return controls; - } -}
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopFullUnrollPhase.java Fri Nov 13 12:26:12 2015 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,67 +0,0 @@ -/* - * 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.loop.phases; - -import com.oracle.graal.debug.Debug; -import com.oracle.graal.debug.DebugMetric; -import com.oracle.graal.loop.LoopEx; -import com.oracle.graal.loop.LoopPolicies; -import com.oracle.graal.loop.LoopTransformations; -import com.oracle.graal.loop.LoopsData; -import com.oracle.graal.nodes.StructuredGraph; -import com.oracle.graal.phases.BasePhase; -import com.oracle.graal.phases.common.CanonicalizerPhase; -import com.oracle.graal.phases.tiers.PhaseContext; - -public class LoopFullUnrollPhase extends BasePhase<PhaseContext> { - - private static final DebugMetric FULLY_UNROLLED_LOOPS = Debug.metric("FullUnrolls"); - private final CanonicalizerPhase canonicalizer; - - public LoopFullUnrollPhase(CanonicalizerPhase canonicalizer) { - this.canonicalizer = canonicalizer; - } - - @Override - protected void run(StructuredGraph graph, PhaseContext context) { - if (graph.hasLoops()) { - boolean peeled; - do { - peeled = false; - final LoopsData dataCounted = new LoopsData(graph); - dataCounted.detectedCountedLoops(); - for (LoopEx loop : dataCounted.countedLoops()) { - if (LoopPolicies.shouldFullUnroll(loop)) { - Debug.log("FullUnroll %s", loop); - LoopTransformations.fullUnroll(loop, context, canonicalizer); - FULLY_UNROLLED_LOOPS.increment(); - Debug.dump(graph, "FullUnroll %s", loop); - peeled = true; - break; - } - } - dataCounted.deleteUnusedNodes(); - } while (peeled); - } - } -}
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopPeelingPhase.java Fri Nov 13 12:26:12 2015 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,49 +0,0 @@ -/* - * Copyright (c) 2012, 2015, 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.loop.phases; - -import com.oracle.graal.debug.Debug; -import com.oracle.graal.loop.LoopEx; -import com.oracle.graal.loop.LoopPolicies; -import com.oracle.graal.loop.LoopTransformations; -import com.oracle.graal.loop.LoopsData; -import com.oracle.graal.nodes.StructuredGraph; -import com.oracle.graal.phases.Phase; - -public class LoopPeelingPhase extends Phase { - - @Override - protected void run(StructuredGraph graph) { - if (graph.hasLoops()) { - LoopsData data = new LoopsData(graph); - for (LoopEx loop : data.outerFirst()) { - if (LoopPolicies.shouldPeel(loop, data.getCFG())) { - Debug.log("Peeling %s", loop); - LoopTransformations.peel(loop); - Debug.dump(graph, "Peeling %s", loop); - } - } - data.deleteUnusedNodes(); - } - } -}
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopSafepointEliminationPhase.java Fri Nov 13 12:26:12 2015 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,73 +0,0 @@ -/* - * Copyright (c) 2011, 2013, 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.loop.phases; - -import com.oracle.graal.loop.LoopEx; -import com.oracle.graal.loop.LoopsData; -import com.oracle.graal.nodes.FixedNode; -import com.oracle.graal.nodes.Invoke; -import com.oracle.graal.nodes.LoopEndNode; -import com.oracle.graal.nodes.StructuredGraph; -import com.oracle.graal.nodes.cfg.Block; -import com.oracle.graal.nodes.extended.ForeignCallNode; -import com.oracle.graal.phases.BasePhase; -import com.oracle.graal.phases.tiers.MidTierContext; - -public class LoopSafepointEliminationPhase extends BasePhase<MidTierContext> { - - @Override - protected void run(StructuredGraph graph, MidTierContext context) { - LoopsData loops = new LoopsData(graph); - if (context.getOptimisticOptimizations().useLoopLimitChecks() && graph.getGuardsStage().allowsFloatingGuards()) { - loops.detectedCountedLoops(); - for (LoopEx loop : loops.countedLoops()) { - if (loop.loop().getChildren().isEmpty() && loop.counted().getStamp().getBits() <= 32) { - boolean hasSafepoint = false; - for (LoopEndNode loopEnd : loop.loopBegin().loopEnds()) { - hasSafepoint |= loopEnd.canSafepoint(); - } - if (hasSafepoint) { - loop.counted().createOverFlowGuard(); - loop.loopBegin().disableSafepoint(); - } - } - } - } - for (LoopEx loop : loops.countedLoops()) { - for (LoopEndNode loopEnd : loop.loopBegin().loopEnds()) { - Block b = loops.getCFG().blockFor(loopEnd); - blocks: while (b != loop.loop().getHeader()) { - assert b != null; - for (FixedNode node : b.getNodes()) { - if (node instanceof Invoke || node instanceof ForeignCallNode) { - loopEnd.disableSafepoint(); - break blocks; - } - } - b = b.getDominator(); - } - } - } - loops.deleteUnusedNodes(); - } -}
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopUnswitchingPhase.java Fri Nov 13 12:26:12 2015 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,91 +0,0 @@ -/* - * 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.loop.phases; - -import java.util.List; - -import com.oracle.graal.debug.Debug; -import com.oracle.graal.debug.DebugMetric; -import com.oracle.graal.graph.NodePosIterator; -import com.oracle.graal.loop.LoopEx; -import com.oracle.graal.loop.LoopPolicies; -import com.oracle.graal.loop.LoopTransformations; -import com.oracle.graal.loop.LoopsData; -import com.oracle.graal.nodes.AbstractBeginNode; -import com.oracle.graal.nodes.ControlSplitNode; -import com.oracle.graal.nodes.StructuredGraph; -import com.oracle.graal.phases.Phase; - -public class LoopUnswitchingPhase extends Phase { - - private static final DebugMetric UNSWITCHED = Debug.metric("Unswitched"); - private static final DebugMetric UNSWITCH_CANDIDATES = Debug.metric("UnswitchCandidates"); - private static final DebugMetric UNSWITCH_EARLY_REJECTS = Debug.metric("UnswitchEarlyRejects"); - - @Override - protected void run(StructuredGraph graph) { - if (graph.hasLoops()) { - boolean unswitched; - do { - unswitched = false; - final LoopsData dataUnswitch = new LoopsData(graph); - for (LoopEx loop : dataUnswitch.outerFirst()) { - if (LoopPolicies.shouldTryUnswitch(loop)) { - List<ControlSplitNode> controlSplits = LoopTransformations.findUnswitchable(loop); - if (controlSplits != null) { - UNSWITCH_CANDIDATES.increment(); - if (LoopPolicies.shouldUnswitch(loop, controlSplits)) { - if (Debug.isLogEnabled()) { - logUnswitch(loop, controlSplits); - } - LoopTransformations.unswitch(loop, controlSplits); - UNSWITCHED.increment(); - unswitched = true; - break; - } - } - } else { - UNSWITCH_EARLY_REJECTS.increment(); - } - } - } while (unswitched); - } - } - - private static void logUnswitch(LoopEx loop, List<ControlSplitNode> controlSplits) { - StringBuilder sb = new StringBuilder("Unswitching "); - sb.append(loop).append(" at "); - for (ControlSplitNode controlSplit : controlSplits) { - sb.append(controlSplit).append(" ["); - NodePosIterator it = controlSplit.successors().iterator(); - while (it.hasNext()) { - sb.append(controlSplit.probability((AbstractBeginNode) it.next())); - if (it.hasNext()) { - sb.append(", "); - } - } - sb.append("]"); - } - Debug.log("%s", sb); - } -}
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/ReassociateInvariantPhase.java Fri Nov 13 12:26:12 2015 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,49 +0,0 @@ -/* - * Copyright (c) 2015, 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.loop.phases; - -import com.oracle.graal.debug.Debug; -import com.oracle.graal.debug.Debug.Scope; -import com.oracle.graal.loop.LoopEx; -import com.oracle.graal.loop.LoopsData; -import com.oracle.graal.nodes.StructuredGraph; -import com.oracle.graal.phases.Phase; - -public class ReassociateInvariantPhase extends Phase { - - @SuppressWarnings("try") - @Override - protected void run(StructuredGraph graph) { - if (graph.hasLoops()) { - final LoopsData dataReassociate = new LoopsData(graph); - try (Scope s = Debug.scope("ReassociateInvariants")) { - for (LoopEx loop : dataReassociate.loops()) { - loop.reassociateInvariants(); - } - } catch (Throwable e) { - throw Debug.handle(e); - } - dataReassociate.deleteUnusedNodes(); - } - } -}
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java Fri Nov 13 12:26:12 2015 -0800 +++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/SnippetTemplate.java Fri Nov 13 14:12:43 2015 +0100 @@ -73,8 +73,8 @@ import com.oracle.graal.graph.NodePosIterator; import com.oracle.graal.graph.Position; import com.oracle.graal.loop.LoopEx; -import com.oracle.graal.loop.LoopTransformations; import com.oracle.graal.loop.LoopsData; +import com.oracle.graal.loop.phases.LoopTransformations; import com.oracle.graal.nodeinfo.InputType; import com.oracle.graal.nodeinfo.NodeInfo; import com.oracle.graal.nodes.AbstractBeginNode;
--- a/mx.graal/suite.py Fri Nov 13 12:26:12 2015 -0800 +++ b/mx.graal/suite.py Fri Nov 13 14:12:43 2015 +0100 @@ -493,7 +493,7 @@ "dependencies" : [ "com.oracle.graal.api.directives", "com.oracle.graal.java", - "com.oracle.graal.loop", + "com.oracle.graal.loop.phases", "com.oracle.graal.word", ], "checkstyle" : "com.oracle.graal.graph", @@ -664,7 +664,20 @@ "com.oracle.graal.loop" : { "subDir" : "graal", "sourceDirs" : ["src"], - "dependencies" : ["com.oracle.graal.phases.common"], + "dependencies" : ["com.oracle.graal.nodes"], + "annotationProcessors" : deps(["jvmci:JVMCI_OPTIONS_PROCESSOR"]), + "checkstyle" : "com.oracle.graal.graph", + "javaCompliance" : "1.8", + "workingSets" : "Graal", + }, + + "com.oracle.graal.loop.phases" : { + "subDir" : "graal", + "sourceDirs" : ["src"], + "dependencies" : [ + "com.oracle.graal.loop", + "com.oracle.graal.phases.common", + ], "annotationProcessors" : deps(["jvmci:JVMCI_OPTIONS_PROCESSOR"]), "checkstyle" : "com.oracle.graal.graph", "javaCompliance" : "1.8", @@ -676,7 +689,7 @@ "sourceDirs" : ["src"], "dependencies" : [ "com.oracle.graal.virtual", - "com.oracle.graal.loop", + "com.oracle.graal.loop.phases", ], "checkstyle" : "com.oracle.graal.graph", "javaCompliance" : "1.8",