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] |

*From*: Jan Hubicka <jh at suse dot cz>*To*: Linus Torvalds <torvalds at transmeta dot com>*Cc*: jh at suse dot cz, gcc at gcc dot gnu dot org*Date*: Fri, 16 Nov 2001 21:04:42 +0100*Subject*: Re: numerical instability and estimate-probability*References*: <Pine.LNX.4.20.0111161103160.9996-100000@moshier.ne.mediaone.net> <200111161722.fAGHMCF15718@penguin.transmeta.com>

> In article <20011116173148.B26573@atrey.karlin.mff.cuni.cz> you write: > > > >Actualy in this case we are speaking about frequencies (for probabilities > >it is just OK to use 0 ... 10000 integers). > > > >The frequencies can get very huge, so only sane workaround wihtout FP > >is IMO only inventing the mantisa/exponent at my own :( > > Ehh.. Why do you need a mantissa at all? > > You're kidding yourself if you think the frequencies are exact, so why > not just do frequencies with logarithmic operations, and always > represent them as powers-of-two - as a simple integer. > > I assume that you never do addition of frequencies anyway (what would > that mean?), so you really only ever multiply frequencies with each > other, no? 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 * frequency_of_header. So I need to sum, compute reciprocals and multiply. Honza

**Follow-Ups**:**Re: numerical instability and estimate-probability***From:*Jan Hubicka

**References**:**Re: numerical instability and estimate-probability***From:*Stephen L Moshier

**Re: numerical instability and estimate-probability***From:*Linus Torvalds

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |