This is the mail archive of the
`gcc@gcc.gnu.org`
mailing list for the GCC project.

# Re: numerical instability and estimate-probability

>
oops, I should always read emails before sending.
> I was also thinkingg about logaritmic sollution. But actually I do add
> frequencies (to compute frequency of basic block, you need to sub frequencies
&sum
> of all it's predecesor, thats the rule).
> Unfortunately predecesors can be numberous and making error in such case
> is relativly important.
>
> Imagine switch statement followed by code. If the switch do have 200
> possibilities I sum together 200 values and I need to get 1, not 0 in case the
> switch is executed.
>
> I will try to re-think this, but when I was oriignally thinking about this
> solution (1 year ago roughly), it didn't fit...
>
> For those who are curious, the algorithm basically estimates probabilities
> for branches. Based on that it attempt to compute how often given basic block
> compute. In the acyclic tree you can simply propagate frequencies - once
^^^^^^ execute
> all predecesors are known, you simply sum them.
>
> In the cyclic code the algorithm ignore everything except natural loop
> (loop with single entry point and single backward edge). Then it goes
> over loop nest and always compute "cyclic probability" that is probability
> that loopback edge is reached when the loop is entered.
>
> The expected amount of iteration is then 1/cyclic_probability *
> frequency_of_header.
>
> So I need to sum, compute reciprocals and multiply.
>
> Honza