001/*
002 * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.loop;
024
025import static com.oracle.graal.compiler.common.GraalOptions.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.code.*;
030
031import com.oracle.graal.graph.Graph.Mark;
032import com.oracle.graal.graph.*;
033import com.oracle.graal.nodeinfo.*;
034import com.oracle.graal.nodes.*;
035import com.oracle.graal.nodes.extended.*;
036import com.oracle.graal.phases.common.*;
037import com.oracle.graal.phases.tiers.*;
038
039public abstract class LoopTransformations {
040
041    private LoopTransformations() {
042        // does not need to be instantiated
043    }
044
045    public static void peel(LoopEx loop) {
046        loop.inside().duplicate().insertBefore(loop);
047        loop.loopBegin().setLoopFrequency(Math.max(0.0, loop.loopBegin().loopFrequency() - 1));
048    }
049
050    public static void fullUnroll(LoopEx loop, PhaseContext context, CanonicalizerPhase canonicalizer) {
051        // assert loop.isCounted(); //TODO (gd) strenghten : counted with known trip count
052        int iterations = 0;
053        LoopBeginNode loopBegin = loop.loopBegin();
054        StructuredGraph graph = loopBegin.graph();
055        while (!loopBegin.isDeleted()) {
056            Mark mark = graph.getMark();
057            peel(loop);
058            canonicalizer.applyIncremental(graph, context, mark);
059            loopBegin.removeDeadPhis();
060            loop.invalidateFragments();
061            if (iterations++ > LoopPolicies.FullUnrollMaxIterations.getValue() || graph.getNodeCount() > MaximumDesiredSize.getValue() * 3) {
062                throw new BailoutException("FullUnroll : Graph seems to grow out of proportion");
063            }
064        }
065    }
066
067    public static void unswitch(LoopEx loop, List<ControlSplitNode> controlSplitNodeSet) {
068        ControlSplitNode firstNode = controlSplitNodeSet.iterator().next();
069        LoopFragmentWhole originalLoop = loop.whole();
070        StructuredGraph graph = firstNode.graph();
071
072        loop.loopBegin().incrementUnswitches();
073
074        // create new control split out of loop
075        ControlSplitNode newControlSplit = (ControlSplitNode) firstNode.copyWithInputs();
076        originalLoop.entryPoint().replaceAtPredecessor(newControlSplit);
077
078        /*
079         * The code below assumes that all of the control split nodes have the same successor
080         * structure, which should have been enforced by findUnswitchable.
081         */
082        NodePosIterator successors = firstNode.successors().iterator();
083        assert successors.hasNext();
084        // original loop is used as first successor
085        Position firstPosition = successors.nextPosition();
086        AbstractBeginNode originalLoopBegin = BeginNode.begin(originalLoop.entryPoint());
087        firstPosition.set(newControlSplit, originalLoopBegin);
088
089        while (successors.hasNext()) {
090            Position position = successors.nextPosition();
091            // create a new loop duplicate and connect it.
092            LoopFragmentWhole duplicateLoop = originalLoop.duplicate();
093            AbstractBeginNode newBegin = BeginNode.begin(duplicateLoop.entryPoint());
094            position.set(newControlSplit, newBegin);
095
096            // For each cloned ControlSplitNode, simplify the proper path
097            for (ControlSplitNode controlSplitNode : controlSplitNodeSet) {
098                ControlSplitNode duplicatedControlSplit = duplicateLoop.getDuplicatedNode(controlSplitNode);
099                if (duplicatedControlSplit.isAlive()) {
100                    AbstractBeginNode survivingSuccessor = (AbstractBeginNode) position.get(duplicatedControlSplit);
101                    survivingSuccessor.replaceAtUsages(InputType.Guard, newBegin);
102                    graph.removeSplitPropagate(duplicatedControlSplit, survivingSuccessor);
103                }
104            }
105        }
106        // original loop is simplified last to avoid deleting controlSplitNode too early
107        for (ControlSplitNode controlSplitNode : controlSplitNodeSet) {
108            if (controlSplitNode.isAlive()) {
109                AbstractBeginNode survivingSuccessor = (AbstractBeginNode) firstPosition.get(controlSplitNode);
110                survivingSuccessor.replaceAtUsages(InputType.Guard, originalLoopBegin);
111                graph.removeSplitPropagate(controlSplitNode, survivingSuccessor);
112            }
113        }
114
115        // TODO (gd) probabilities need some amount of fixup.. (probably also in other transforms)
116    }
117
118    public static List<ControlSplitNode> findUnswitchable(LoopEx loop) {
119        List<ControlSplitNode> controls = null;
120        ValueNode invariantValue = null;
121        for (IfNode ifNode : loop.whole().nodes().filter(IfNode.class)) {
122            if (loop.isOutsideLoop(ifNode.condition())) {
123                if (controls == null) {
124                    invariantValue = ifNode.condition();
125                    controls = new ArrayList<>();
126                    controls.add(ifNode);
127                } else if (ifNode.condition() == invariantValue) {
128                    controls.add(ifNode);
129                }
130            }
131        }
132        if (controls == null) {
133            SwitchNode firstSwitch = null;
134            for (SwitchNode switchNode : loop.whole().nodes().filter(SwitchNode.class)) {
135                if (switchNode.successors().count() > 1 && loop.isOutsideLoop(switchNode.value())) {
136                    if (controls == null) {
137                        firstSwitch = switchNode;
138                        invariantValue = switchNode.value();
139                        controls = new ArrayList<>();
140                        controls.add(switchNode);
141                    } else if (switchNode.value() == invariantValue && firstSwitch.structureEquals(switchNode)) {
142                        // Only collect switches which test the same values in the same order
143                        controls.add(switchNode);
144                    }
145                }
146            }
147        }
148        return controls;
149    }
150}