001/*
002 * Copyright (c) 2012, 2015, 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 com.oracle.graal.debug.*;
030import jdk.internal.jvmci.options.*;
031
032import com.oracle.graal.graph.*;
033import com.oracle.graal.nodes.*;
034import com.oracle.graal.nodes.VirtualState.VirtualClosure;
035import com.oracle.graal.nodes.cfg.*;
036import com.oracle.graal.nodes.debug.*;
037
038public abstract class LoopPolicies {
039    @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> LoopUnswitchMaxIncrease = new OptionValue<>(500);
040    @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> LoopUnswitchTrivial = new OptionValue<>(10);
041    @Option(help = "", type = OptionType.Expert) public static final OptionValue<Double> LoopUnswitchFrequencyBoost = new OptionValue<>(10.0);
042
043    @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> FullUnrollMaxNodes = new OptionValue<>(300);
044    @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> FullUnrollMaxIterations = new OptionValue<>(600);
045    @Option(help = "", type = OptionType.Expert) public static final OptionValue<Integer> ExactFullUnrollMaxNodes = new OptionValue<>(1200);
046
047    private LoopPolicies() {
048        // does not need to be instantiated
049    }
050
051    // TODO (gd) change when inversion is available
052    public static boolean shouldPeel(LoopEx loop, ControlFlowGraph cfg) {
053        if (loop.detectCounted()) {
054            return false;
055        }
056        LoopBeginNode loopBegin = loop.loopBegin();
057        double entryProbability = cfg.blockFor(loopBegin.forwardEnd()).probability();
058        if (entryProbability > MinimumPeelProbability.getValue() && loop.size() + loopBegin.graph().getNodeCount() < MaximumDesiredSize.getValue()) {
059            // check whether we're allowed to peel this loop
060            for (Node node : loop.inside().nodes()) {
061                if (node instanceof ControlFlowAnchorNode) {
062                    return false;
063                }
064            }
065            return true;
066        } else {
067            return false;
068        }
069    }
070
071    public static boolean shouldFullUnroll(LoopEx loop) {
072        if (!loop.isCounted() || !loop.counted().isConstantMaxTripCount()) {
073            return false;
074        }
075        CountedLoopInfo counted = loop.counted();
076        long maxTrips = counted.constantMaxTripCount();
077        int maxNodes = (counted.isExactTripCount() && counted.isConstantExactTripCount()) ? ExactFullUnrollMaxNodes.getValue() : FullUnrollMaxNodes.getValue();
078        maxNodes = Math.min(maxNodes, MaximumDesiredSize.getValue() - loop.loopBegin().graph().getNodeCount());
079        int size = Math.max(1, loop.size() - 1 - loop.loopBegin().phis().count());
080        if (size * maxTrips <= maxNodes) {
081            // check whether we're allowed to unroll this loop
082            for (Node node : loop.inside().nodes()) {
083                if (node instanceof ControlFlowAnchorNode) {
084                    return false;
085                }
086            }
087            return true;
088        } else {
089            return false;
090        }
091    }
092
093    public static boolean shouldTryUnswitch(LoopEx loop) {
094        LoopBeginNode loopBegin = loop.loopBegin();
095        double loopFrequency = loopBegin.loopFrequency();
096        if (loopFrequency <= 1.0) {
097            return false;
098        }
099        return loopBegin.unswitches() <= LoopMaxUnswitch.getValue();
100    }
101
102    private static final class CountingClosure implements VirtualClosure {
103        int count;
104
105        public void apply(VirtualState node) {
106            count++;
107        }
108    }
109
110    private static class IsolatedInitialization {
111        static final DebugMetric UNSWITCH_SPLIT_WITH_PHIS = Debug.metric("UnswitchSplitWithPhis");
112    }
113
114    public static boolean shouldUnswitch(LoopEx loop, List<ControlSplitNode> controlSplits) {
115        int inBranchTotal = 0;
116        int phis = 0;
117        for (ControlSplitNode controlSplit : controlSplits) {
118            for (Node successor : controlSplit.successors()) {
119                AbstractBeginNode branch = (AbstractBeginNode) successor;
120                // this may count twice because of fall-through in switches
121                inBranchTotal += loop.nodesInLoopBranch(branch).count();
122            }
123            Block postDomBlock = loop.loopsData().getCFG().blockFor(controlSplit).getPostdominator();
124            if (postDomBlock != null) {
125                IsolatedInitialization.UNSWITCH_SPLIT_WITH_PHIS.increment();
126                phis += ((MergeNode) postDomBlock.getBeginNode()).phis().count();
127            }
128        }
129
130        CountingClosure stateNodesCount = new CountingClosure();
131        double loopFrequency = loop.loopBegin().loopFrequency();
132        int maxDiff = LoopUnswitchTrivial.getValue() + (int) (LoopUnswitchFrequencyBoost.getValue() * (loopFrequency - 1.0 + phis));
133
134        maxDiff = Math.min(maxDiff, LoopUnswitchMaxIncrease.getValue());
135        int remainingGraphSpace = MaximumDesiredSize.getValue() - loop.loopBegin().graph().getNodeCount();
136        maxDiff = Math.min(maxDiff, remainingGraphSpace);
137
138        loop.loopBegin().stateAfter().applyToVirtual(stateNodesCount);
139        int loopTotal = loop.size() - loop.loopBegin().phis().count() - stateNodesCount.count - 1;
140        int actualDiff = loopTotal - inBranchTotal;
141
142        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,
143                        loopFrequency, phis, actualDiff <= maxDiff);
144        return actualDiff <= maxDiff;
145    }
146
147}