1 /*

     2  * Copyright (c) 2011, 2014, 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.java;

    24 

    25 import java.util.List;

    26 

    27 import org.graalvm.compiler.nodes.AbstractBeginNode;

    28 import org.graalvm.compiler.nodes.AbstractMergeNode;

    29 import org.graalvm.compiler.nodes.ControlSplitNode;

    30 import org.graalvm.compiler.nodes.FixedNode;

    31 import org.graalvm.compiler.nodes.LoopBeginNode;

    32 import org.graalvm.compiler.nodes.LoopExitNode;

    33 import org.graalvm.compiler.nodes.StructuredGraph;

    34 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;

    35 import org.graalvm.compiler.phases.Phase;

    36 import org.graalvm.compiler.phases.graph.ReentrantNodeIterator;

    37 import org.graalvm.util.EconomicMap;

    38 

    39 import static org.graalvm.compiler.nodes.cfg.ControlFlowGraph.multiplyProbabilities;

    40 

    41 public final class ComputeLoopFrequenciesClosure extends ReentrantNodeIterator.NodeIteratorClosure<Double> {

    42 

    43     private static final ComputeLoopFrequenciesClosure INSTANCE = new ComputeLoopFrequenciesClosure();

    44 

    45     private ComputeLoopFrequenciesClosure() {

    46         // nothing to do

    47     }

    48 

    49     @Override

    50     protected Double processNode(FixedNode node, Double currentState) {

    51         // normal nodes never change the probability of a path

    52         return currentState;

    53     }

    54 

    55     @Override

    56     protected Double merge(AbstractMergeNode merge, List<Double> states) {

    57         // a merge has the sum of all predecessor probabilities

    58         double result = 0.0;

    59         for (double d : states) {

    60             result += d;

    61         }

    62         return result;

    63     }

    64 

    65     @Override

    66     protected Double afterSplit(AbstractBeginNode node, Double oldState) {

    67         // a control split splits up the probability

    68         ControlSplitNode split = (ControlSplitNode) node.predecessor();

    69         return oldState * split.probability(node);

    70     }

    71 

    72     @Override

    73     protected EconomicMap<LoopExitNode, Double> processLoop(LoopBeginNode loop, Double initialState) {

    74         EconomicMap<LoopExitNode, Double> exitStates = ReentrantNodeIterator.processLoop(this, loop, 1D).exitStates;

    75 

    76         double exitProbability = 0.0;

    77         for (double d : exitStates.getValues()) {

    78             exitProbability += d;

    79         }

    80         exitProbability = Math.min(1.0, exitProbability);

    81         exitProbability = Math.max(ControlFlowGraph.MIN_PROBABILITY, exitProbability);

    82         double loopFrequency = 1.0 / exitProbability;

    83         loop.setLoopFrequency(loopFrequency);

    84 

    85         double adjustmentFactor = initialState * loopFrequency;

    86         exitStates.replaceAll((exitNode, probability) -> multiplyProbabilities(probability, adjustmentFactor));

    87 

    88         return exitStates;

    89     }

    90 

    91     /**

    92      * Computes the frequencies of all loops in the given graph. This is done by performing a

    93      * reverse postorder iteration and computing the probability of all fixed nodes. The combined

    94      * probability of all exits of a loop can be used to compute the loop's expected frequency.

    95      */

    96     public static void compute(StructuredGraph graph) {

    97         if (graph.hasLoops()) {

    98             ReentrantNodeIterator.apply(INSTANCE, graph.start(), 1D);

    99         }

   100     }

   101 

   102     public static class ComputeLoopFrequencyPhase extends Phase {

   103 

   104         @Override

   105         protected void run(StructuredGraph graph) {

   106             compute(graph);

   107         }

   108     }

   109 

   110     public static final ComputeLoopFrequencyPhase PHASE_INSTANCE = new ComputeLoopFrequencyPhase();

   111 

   112 }