1 /* 2 * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 package org.graalvm.compiler.loop.phases; 24 25 import static org.graalvm.compiler.core.common.GraalOptions.MaximumDesiredSize; 26 27 import java.util.ArrayList; 28 import java.util.Iterator; 29 import java.util.List; 30 31 import org.graalvm.compiler.graph.Graph.Mark; 32 import org.graalvm.compiler.core.common.RetryableBailoutException; 33 import org.graalvm.compiler.graph.Position; 34 import org.graalvm.compiler.loop.LoopEx; 35 import org.graalvm.compiler.loop.LoopFragmentWhole; 36 import org.graalvm.compiler.nodeinfo.InputType; 37 import org.graalvm.compiler.nodes.AbstractBeginNode; 38 import org.graalvm.compiler.nodes.BeginNode; 39 import org.graalvm.compiler.nodes.ControlSplitNode; 40 import org.graalvm.compiler.nodes.IfNode; 41 import org.graalvm.compiler.nodes.LoopBeginNode; 42 import org.graalvm.compiler.nodes.StructuredGraph; 43 import org.graalvm.compiler.nodes.ValueNode; 44 import org.graalvm.compiler.nodes.extended.SwitchNode; 45 import org.graalvm.compiler.phases.common.CanonicalizerPhase; 46 import org.graalvm.compiler.phases.tiers.PhaseContext; 47 48 public abstract class LoopTransformations { 49 50 private LoopTransformations() { 51 // does not need to be instantiated 52 } 53 54 public static void peel(LoopEx loop) { 55 loop.inside().duplicate().insertBefore(loop); 56 loop.loopBegin().setLoopFrequency(Math.max(0.0, loop.loopBegin().loopFrequency() - 1)); 57 } 58 59 public static void fullUnroll(LoopEx loop, PhaseContext context, CanonicalizerPhase canonicalizer) { 60 // assert loop.isCounted(); //TODO (gd) strenghten : counted with known trip count 61 LoopBeginNode loopBegin = loop.loopBegin(); 62 StructuredGraph graph = loopBegin.graph(); 63 int initialNodeCount = graph.getNodeCount(); 64 while (!loopBegin.isDeleted()) { 65 Mark mark = graph.getMark(); 66 peel(loop); 67 canonicalizer.applyIncremental(graph, context, mark); 68 loop.invalidateFragments(); 69 if (graph.getNodeCount() > initialNodeCount + MaximumDesiredSize.getValue(graph.getOptions()) * 2) { 70 throw new RetryableBailoutException("FullUnroll : Graph seems to grow out of proportion"); 71 } 72 } 73 } 74 75 public static void unswitch(LoopEx loop, List<ControlSplitNode> controlSplitNodeSet) { 76 ControlSplitNode firstNode = controlSplitNodeSet.iterator().next(); 77 LoopFragmentWhole originalLoop = loop.whole(); 78 StructuredGraph graph = firstNode.graph(); 79 80 loop.loopBegin().incrementUnswitches(); 81 82 // create new control split out of loop 83 ControlSplitNode newControlSplit = (ControlSplitNode) firstNode.copyWithInputs(); 84 originalLoop.entryPoint().replaceAtPredecessor(newControlSplit); 85 86 /* 87 * The code below assumes that all of the control split nodes have the same successor 88 * structure, which should have been enforced by findUnswitchable. 89 */ 90 Iterator<Position> successors = firstNode.successorPositions().iterator(); 91 assert successors.hasNext(); 92 // original loop is used as first successor 93 Position firstPosition = successors.next(); 94 AbstractBeginNode originalLoopBegin = BeginNode.begin(originalLoop.entryPoint()); 95 firstPosition.set(newControlSplit, originalLoopBegin); 96 97 while (successors.hasNext()) { 98 Position position = successors.next(); 99 // create a new loop duplicate and connect it. 100 LoopFragmentWhole duplicateLoop = originalLoop.duplicate(); 101 AbstractBeginNode newBegin = BeginNode.begin(duplicateLoop.entryPoint()); 102 position.set(newControlSplit, newBegin); 103 104 // For each cloned ControlSplitNode, simplify the proper path 105 for (ControlSplitNode controlSplitNode : controlSplitNodeSet) { 106 ControlSplitNode duplicatedControlSplit = duplicateLoop.getDuplicatedNode(controlSplitNode); 107 if (duplicatedControlSplit.isAlive()) { 108 AbstractBeginNode survivingSuccessor = (AbstractBeginNode) position.get(duplicatedControlSplit); 109 survivingSuccessor.replaceAtUsages(InputType.Guard, newBegin); 110 graph.removeSplitPropagate(duplicatedControlSplit, survivingSuccessor); 111 } 112 } 113 } 114 // original loop is simplified last to avoid deleting controlSplitNode too early 115 for (ControlSplitNode controlSplitNode : controlSplitNodeSet) { 116 if (controlSplitNode.isAlive()) { 117 AbstractBeginNode survivingSuccessor = (AbstractBeginNode) firstPosition.get(controlSplitNode); 118 survivingSuccessor.replaceAtUsages(InputType.Guard, originalLoopBegin); 119 graph.removeSplitPropagate(controlSplitNode, survivingSuccessor); 120 } 121 } 122 123 // TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms) 124 } 125 126 public static List<ControlSplitNode> findUnswitchable(LoopEx loop) { 127 List<ControlSplitNode> controls = null; 128 ValueNode invariantValue = null; 129 for (IfNode ifNode : loop.whole().nodes().filter(IfNode.class)) { 130 if (loop.isOutsideLoop(ifNode.condition())) { 131 if (controls == null) { 132 invariantValue = ifNode.condition(); 133 controls = new ArrayList<>(); 134 controls.add(ifNode); 135 } else if (ifNode.condition() == invariantValue) { 136 controls.add(ifNode); 137 } 138 } 139 } 140 if (controls == null) { 141 SwitchNode firstSwitch = null; 142 for (SwitchNode switchNode : loop.whole().nodes().filter(SwitchNode.class)) { 143 if (switchNode.successors().count() > 1 && loop.isOutsideLoop(switchNode.value())) { 144 if (controls == null) { 145 firstSwitch = switchNode; 146 invariantValue = switchNode.value(); 147 controls = new ArrayList<>(); 148 controls.add(switchNode); 149 } else if (switchNode.value() == invariantValue && firstSwitch.structureEquals(switchNode)) { 150 // Only collect switches which test the same values in the same order 151 controls.add(switchNode); 152 } 153 } 154 } 155 } 156 return controls; 157 } 158 }