jsp@cup.portal.com (06/16/88)
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] -- Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | bbn}!ima Please send responses to the originator of the message -- I cannot forward mail accidentally sent back to compilers. Meta-mail to ima!compilers-request