15.4.244  src/lib/compiler/back/low/frequencies/complete-branch-probabilities-g.pkg

## complete-branch-probabilities-g.pkg

# Compiled by:
#     src/lib/compiler/back/low/lib/lowhalf.lib


# Given a machcode_controlflow_graph that may have incomplete branch probability information,
# fill in the information.



###                   "They couldn't hit an elephant at this dist-"
###
###                            -- General John B. Sedgwick, last words, 1864


stipulate
    package odg =  oop_digraph;                                 # oop_digraph           is from   src/lib/graph/oop-digraph.pkg
    package prb =  probability;                                 # probability                   is from   src/lib/compiler/back/low/library/probability.pkg
herein

    # This generic is invoked (only) from:
    #
    #     src/lib/compiler/back/low/frequencies/guess-bblock-execution-frequencies-g.pkg
    #
    generic package   complete_branch_probabilities_g   (
        #             ===============================
        #
        package mcg: Machcode_Controlflow_Graph;                        # Machcode_Controlflow_Graph    is from   src/lib/compiler/back/low/mcg/machcode-controlflow-graph.api

        # Function to record edge probabilities:
        #
        record_probability
            :
            (mcg::Edge_Info,  Float)
            ->
            Void;
    )
    : (weak)
    api {
        package mcg:  Machcode_Controlflow_Graph;               # Machcode_Controlflow_Graph    is from   src/lib/compiler/back/low/mcg/machcode-controlflow-graph.api

        complete_probs:  mcg::Machcode_Controlflow_Graph -> Void;
    }
    {
        # Export to client packages:
        #       
        package mcg =  mcg;                                     # "mcg" == "machcode_controlflow_graph".


        dump_machcode_controlflow_graph_after_probability_completion
            =
            lowhalf_control::make_bool (
              "dump_machcode_controlflow_graph_after_probability_completion",
              "TRUE to dump control flow graph after probability completion"
            );

        my { get=>get_prob, ... }
            =
            lowhalf_notes::branch_probability;

        # Complete edge probabilities:
        #
        fun complete_probs (mcg as odg::DIGRAPH { forall_nodes, out_edges, ... } )
            =
            forall_nodes do_block
            then
                if *dump_machcode_controlflow_graph_after_probability_completion
                    #
                    mcg::dump (
                        *lowhalf_control::debug_stream,
                        "after probability completion",
                        mcg
                    );
                fi
            where
                fun do_block (blk_id, _)
                    =
                    {   fun compute_probs ((_, _, e as mcg::EDGE_INFO { notes, ... } ) ! r, remaining, n, es)
                                =>
                                case (get_prob *notes)
                                    #
                                    NULL  =>    compute_probs (r, remaining, n+1, e ! es);
                                    #
                                    THE p =>    {   record_probability (e, prb::to_float p);
                                                    #
                                                    compute_probs (r, prb::(-) (remaining, p), n, es);
                                                };
                                esac;

                            compute_probs ([], _, 0, _)
                                =>
                                ();

                            compute_probs ([], remaining, n, es)
                                =>
                                {   p = prb::to_float (prb::(/) (remaining, n));
                                    #
                                    list::apply (\\ e = record_probability (e, p))
                                                es;
                                };
                        end;

                        compute_probs (out_edges blk_id, prb::always, 0, []);
                    };
            end;
    };
end;

## COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.