hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.loop.phases/src/org/graalvm/compiler/loop/phases/LoopTransformations.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.loop.phases/src/org/graalvm/compiler/loop/phases/LoopTransformations.java Thu Feb 16 15:46:09 2017 -0800
@@ -0,0 +1,158 @@
+/*
+ * 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 org.graalvm.compiler.loop.phases;
+
+import static org.graalvm.compiler.core.common.GraalOptions.MaximumDesiredSize;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import org.graalvm.compiler.graph.Graph.Mark;
+import org.graalvm.compiler.common.RetryableBailoutException;
+import org.graalvm.compiler.graph.Position;
+import org.graalvm.compiler.loop.LoopEx;
+import org.graalvm.compiler.loop.LoopFragmentWhole;
+import org.graalvm.compiler.nodeinfo.InputType;
+import org.graalvm.compiler.nodes.AbstractBeginNode;
+import org.graalvm.compiler.nodes.BeginNode;
+import org.graalvm.compiler.nodes.ControlSplitNode;
+import org.graalvm.compiler.nodes.IfNode;
+import org.graalvm.compiler.nodes.LoopBeginNode;
+import org.graalvm.compiler.nodes.StructuredGraph;
+import org.graalvm.compiler.nodes.ValueNode;
+import org.graalvm.compiler.nodes.extended.SwitchNode;
+import org.graalvm.compiler.phases.common.CanonicalizerPhase;
+import org.graalvm.compiler.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
+ LoopBeginNode loopBegin = loop.loopBegin();
+ StructuredGraph graph = loopBegin.graph();
+ int initialNodeCount = graph.getNodeCount();
+ while (!loopBegin.isDeleted()) {
+ Mark mark = graph.getMark();
+ peel(loop);
+ canonicalizer.applyIncremental(graph, context, mark);
+ loop.invalidateFragments();
+ if (graph.getNodeCount() > initialNodeCount + MaximumDesiredSize.getValue() * 2) {
+ throw new RetryableBailoutException("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.
+ */
+ Iterator<Position> successors = firstNode.successorPositions().iterator();
+ assert successors.hasNext();
+ // original loop is used as first successor
+ Position firstPosition = successors.next();
+ AbstractBeginNode originalLoopBegin = BeginNode.begin(originalLoop.entryPoint());
+ firstPosition.set(newControlSplit, originalLoopBegin);
+
+ while (successors.hasNext()) {
+ Position position = successors.next();
+ // 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;
+ }
+}