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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]