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 }