Branch frequency.

I would like any help anyone can give (literature, names, personal experiences,
etc.) with the following: Given a program in some intermediate language and
composed of some number of basic blocks. This can be graphically represented
where each node of the graph corresponds to a basic block and each edge
corresponds to a possible branch. I need a way to find out how many times
each branch (edge) is taken. Note that knowing how many times each basic
block is executed does not necessary provide the information that I want.
I am interested both in methods of statically estimating this, as well as
methods of getting it via running the program.


Certainly somewhere someone has researched this or done a thesis on it
or something. Any of you read any papers or articles? Or done something
like this yourself that you can tell me about?


Thanx,
--James Preston, sun!portal!cup.portal.com!jsp
    (Or if you're feeling adventurous, try pacbell!key!jsp or maybe
      pacbell!ptsfa!key!jsp. I think it's something like that.)
[It occurs to me that it is a fairly common procedure to add counting
instructions, one per basic block, to find out at runtime how often each piece
of a program is run. I believe that John Mashey spend quite a lot of time at
MIPS doing just that. There's no reason why you couldn't do basically the same
thing to count the number of times conditional branches exit in each
direction. Seems like a reasonable idea, and one that's very useful to people
who are trying to figure out branch squashing strategies, but I can't say if
anyone has actually done it and reported on it. -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.