This is the mail archive of the
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
> 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
> 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 *
> So I need to sum, compute reciprocals and multiply.