001/*
002 * Copyright (c) 2011, 2014, 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.java;
024
025import static com.oracle.graal.nodes.cfg.ControlFlowGraph.*;
026
027import java.util.*;
028import java.util.stream.*;
029
030import com.oracle.graal.nodes.*;
031import com.oracle.graal.phases.graph.*;
032
033public final class ComputeLoopFrequenciesClosure extends ReentrantNodeIterator.NodeIteratorClosure<Double> {
034
035    private static final ComputeLoopFrequenciesClosure INSTANCE = new ComputeLoopFrequenciesClosure();
036
037    private ComputeLoopFrequenciesClosure() {
038        // nothing to do
039    }
040
041    @Override
042    protected Double processNode(FixedNode node, Double currentState) {
043        // normal nodes never change the probability of a path
044        return currentState;
045    }
046
047    @Override
048    protected Double merge(AbstractMergeNode merge, List<Double> states) {
049        // a merge has the sum of all predecessor probabilities
050        return states.stream().collect(Collectors.summingDouble(d -> d));
051    }
052
053    @Override
054    protected Double afterSplit(AbstractBeginNode node, Double oldState) {
055        // a control split splits up the probability
056        ControlSplitNode split = (ControlSplitNode) node.predecessor();
057        return oldState * split.probability(node);
058    }
059
060    @Override
061    protected Map<LoopExitNode, Double> processLoop(LoopBeginNode loop, Double initialState) {
062        Map<LoopExitNode, Double> exitStates = ReentrantNodeIterator.processLoop(this, loop, 1D).exitStates;
063
064        double exitProbability = exitStates.values().stream().mapToDouble(d -> d).sum();
065        exitProbability = Math.min(1D, exitProbability);
066        if (exitProbability < MIN_PROBABILITY) {
067            exitProbability = MIN_PROBABILITY;
068        }
069        assert exitProbability <= 1D && exitProbability >= 0D;
070        double loopFrequency = 1D / exitProbability;
071        loop.setLoopFrequency(loopFrequency);
072
073        double adjustmentFactor = initialState * loopFrequency;
074        exitStates.replaceAll((exitNode, probability) -> multiplySaturate(probability, adjustmentFactor));
075
076        return exitStates;
077    }
078
079    /**
080     * Multiplies a and b and saturates the result to 1/{@link #MIN_PROBABILITY}.
081     *
082     * @return a times b saturated to 1/{@link #MIN_PROBABILITY}
083     */
084    public static double multiplySaturate(double a, double b) {
085        double r = a * b;
086        if (r > 1 / MIN_PROBABILITY) {
087            return 1 / MIN_PROBABILITY;
088        }
089        return r;
090    }
091
092    /**
093     * Computes the frequencies of all loops in the given graph. This is done by performing a
094     * reverse postorder iteration and computing the probability of all fixed nodes. The combined
095     * probability of all exits of a loop can be used to compute the loop's expected frequency.
096     */
097    public static void compute(StructuredGraph graph) {
098        if (graph.hasLoops()) {
099            ReentrantNodeIterator.apply(INSTANCE, graph.start(), 1D);
100        }
101    }
102
103}