1 /*

     2  * Copyright (c) 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 

    24 

    25 package org.graalvm.compiler.phases.graph;

    26 

    27 import static org.graalvm.compiler.nodes.cfg.ControlFlowGraph.multiplyRelativeFrequencies;

    28 

    29 import java.util.function.ToDoubleFunction;

    30 

    31 import jdk.internal.vm.compiler.collections.EconomicMap;

    32 import jdk.internal.vm.compiler.collections.Equivalence;

    33 import org.graalvm.compiler.debug.CounterKey;

    34 import org.graalvm.compiler.debug.DebugContext;

    35 import org.graalvm.compiler.graph.Node;

    36 import org.graalvm.compiler.graph.NodeInputList;

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

    38 import org.graalvm.compiler.nodes.AbstractEndNode;

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

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

    41 import org.graalvm.compiler.nodes.EndNode;

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

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

    44 import org.graalvm.compiler.nodes.StartNode;

    45 

    46 /**

    47  * Compute relative frequencies for fixed nodes on the fly and cache them at

    48  * {@link AbstractBeginNode}s.

    49  */

    50 public class FixedNodeRelativeFrequencyCache implements ToDoubleFunction<FixedNode> {

    51 

    52     private static final CounterKey computeNodeRelativeFrequencyCounter = DebugContext.counter("ComputeNodeRelativeFrequency");

    53 

    54     private final EconomicMap<FixedNode, Double> cache = EconomicMap.create(Equivalence.IDENTITY);

    55 

    56     /**

    57      * <p>

    58      * Given a {@link FixedNode} this method finds the most immediate {@link AbstractBeginNode}

    59      * preceding it that either:

    60      * <ul>

    61      * <li>has no predecessor (ie, the begin-node is a merge, in particular a loop-begin, or the

    62      * start-node)</li>

    63      * <li>has a control-split predecessor</li>

    64      * </ul>

    65      * </p>

    66      *

    67      * <p>

    68      * The thus found {@link AbstractBeginNode} is equi-probable with the {@link FixedNode} it was

    69      * obtained from. When computed for the first time (afterwards a cache lookup returns it) that

    70      * relative frequency is computed as follows, again depending on the begin-node's predecessor:

    71      * <ul>

    72      * <li>No predecessor. In this case the begin-node is either:</li>

    73      * <ul>

    74      * <li>a merge-node, whose relative frequency adds up those of its forward-ends</li>

    75      * <li>a loop-begin, with frequency as above multiplied by the loop-frequency</li>

    76      * </ul>

    77      * <li>Control-split predecessor: frequency of the branch times that of the control-split</li>

    78      * </ul>

    79      * </p>

    80      *

    81      * <p>

    82      * As an exception to all the above, a frequency of 1 is assumed for a {@link FixedNode} that

    83      * appears to be dead-code (ie, lacks a predecessor).

    84      * </p>

    85      *

    86      */

    87     @Override

    88     public double applyAsDouble(FixedNode node) {

    89         assert node != null;

    90         computeNodeRelativeFrequencyCounter.increment(node.getDebug());

    91 

    92         FixedNode current = findBegin(node);

    93         if (current == null) {

    94             // this should only appear for dead code

    95             return 1D;

    96         }

    97 

    98         assert current instanceof AbstractBeginNode;

    99         Double cachedValue = cache.get(current);

   100         if (cachedValue != null) {

   101             return cachedValue;

   102         }

   103 

   104         double relativeFrequency = 0.0;

   105         if (current.predecessor() == null) {

   106             if (current instanceof AbstractMergeNode) {

   107                 relativeFrequency = handleMerge(current, relativeFrequency);

   108             } else {

   109                 assert current instanceof StartNode;

   110                 relativeFrequency = 1D;

   111             }

   112         } else {

   113             ControlSplitNode split = (ControlSplitNode) current.predecessor();

   114             relativeFrequency = multiplyRelativeFrequencies(split.probability((AbstractBeginNode) current), applyAsDouble(split));

   115         }

   116         assert !Double.isNaN(relativeFrequency) && !Double.isInfinite(relativeFrequency) : current + " " + relativeFrequency;

   117         cache.put(current, relativeFrequency);

   118         return relativeFrequency;

   119     }

   120 

   121     private double handleMerge(FixedNode current, double relativeFrequency) {

   122         double result = relativeFrequency;

   123         AbstractMergeNode currentMerge = (AbstractMergeNode) current;

   124         NodeInputList<EndNode> currentForwardEnds = currentMerge.forwardEnds();

   125         /*

   126          * Use simple iteration instead of streams, since the stream infrastructure adds many frames

   127          * which causes the recursion to overflow the stack earlier than it would otherwise.

   128          */

   129         for (AbstractEndNode endNode : currentForwardEnds) {

   130             result += applyAsDouble(endNode);

   131         }

   132         if (current instanceof LoopBeginNode) {

   133             result = multiplyRelativeFrequencies(result, ((LoopBeginNode) current).loopFrequency());

   134         }

   135         return result;

   136     }

   137 

   138     private static FixedNode findBegin(FixedNode node) {

   139         FixedNode current = node;

   140         while (true) {

   141             assert current != null;

   142             Node predecessor = current.predecessor();

   143             if (current instanceof AbstractBeginNode) {

   144                 if (predecessor == null) {

   145                     break;

   146                 } else if (predecessor.successors().count() != 1) {

   147                     assert predecessor instanceof ControlSplitNode : "a FixedNode with multiple successors needs to be a ControlSplitNode: " + current + " / " + predecessor;

   148                     break;

   149                 }

   150             } else if (predecessor == null) {

   151                 current = null;

   152                 break;

   153             }

   154             current = (FixedNode) predecessor;

   155         }

   156         return current;

   157     }

   158 }