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 import java.util.Map;
  27 import java.util.stream.Collectors;
  28 
  29 import org.graalvm.compiler.nodes.AbstractBeginNode;
  30 import org.graalvm.compiler.nodes.AbstractMergeNode;
  31 import org.graalvm.compiler.nodes.ControlSplitNode;
  32 import org.graalvm.compiler.nodes.FixedNode;
  33 import org.graalvm.compiler.nodes.LoopBeginNode;
  34 import org.graalvm.compiler.nodes.LoopExitNode;
  35 import org.graalvm.compiler.nodes.StructuredGraph;
  36 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph;
  37 import org.graalvm.compiler.phases.Phase;
  38 import org.graalvm.compiler.phases.graph.ReentrantNodeIterator;
  39 
  40 public final class ComputeLoopFrequenciesClosure extends ReentrantNodeIterator.NodeIteratorClosure<Double> {
  41 
  42     private static final ComputeLoopFrequenciesClosure INSTANCE = new ComputeLoopFrequenciesClosure();
  43 
  44     private ComputeLoopFrequenciesClosure() {
  45         // nothing to do
  46     }
  47 
  48     @Override
  49     protected Double processNode(FixedNode node, Double currentState) {
  50         // normal nodes never change the probability of a path
  51         return currentState;
  52     }
  53 
  54     @Override
  55     protected Double merge(AbstractMergeNode merge, List<Double> states) {
  56         // a merge has the sum of all predecessor probabilities
  57         return states.stream().collect(Collectors.summingDouble(d -> d));
  58     }
  59 
  60     @Override
  61     protected Double afterSplit(AbstractBeginNode node, Double oldState) {
  62         // a control split splits up the probability
  63         ControlSplitNode split = (ControlSplitNode) node.predecessor();
  64         return oldState * split.probability(node);
  65     }
  66 
  67     @Override
  68     protected Map<LoopExitNode, Double> processLoop(LoopBeginNode loop, Double initialState) {
  69         Map<LoopExitNode, Double> exitStates = ReentrantNodeIterator.processLoop(this, loop, 1D).exitStates;
  70 
  71         double exitProbability = exitStates.values().stream().mapToDouble(d -> d).sum();
  72         exitProbability = Math.min(1D, exitProbability);
  73         if (exitProbability < ControlFlowGraph.MIN_PROBABILITY) {
  74             exitProbability = ControlFlowGraph.MIN_PROBABILITY;
  75         }
  76         assert exitProbability <= 1D && exitProbability >= 0D;
  77         double loopFrequency = 1D / exitProbability;
  78         loop.setLoopFrequency(loopFrequency);
  79 
  80         double adjustmentFactor = initialState * loopFrequency;
  81         exitStates.replaceAll((exitNode, probability) -> multiplySaturate(probability, adjustmentFactor));
  82 
  83         return exitStates;
  84     }
  85 
  86     /**
  87      * Multiplies a and b and saturates the result to {@link ControlFlowGraph#MAX_PROBABILITY}.
  88      */
  89     public static double multiplySaturate(double a, double b) {
  90         double r = a * b;
  91         if (r > ControlFlowGraph.MAX_PROBABILITY) {
  92             return ControlFlowGraph.MAX_PROBABILITY;
  93         }
  94         return r;
  95     }
  96 
  97     /**
  98      * Computes the frequencies of all loops in the given graph. This is done by performing a
  99      * reverse postorder iteration and computing the probability of all fixed nodes. The combined
 100      * probability of all exits of a loop can be used to compute the loop's expected frequency.
 101      */
 102     public static void compute(StructuredGraph graph) {
 103         if (graph.hasLoops()) {
 104             ReentrantNodeIterator.apply(INSTANCE, graph.start(), 1D);
 105         }
 106     }
 107 
 108     public static class ComputeLoopFrequencyPhase extends Phase {
 109 
 110         @Override
 111         protected void run(StructuredGraph graph) {
 112             compute(graph);
 113         }
 114     }
 115 
 116     public static final ComputeLoopFrequencyPhase PHASE_INSTANCE = new ComputeLoopFrequencyPhase();
 117 
 118 }