Static analysis of code for "flop counting"?

We have run into the problem of wanting to count the number of
operations (mostly floating point) actually performed by a code as it
executes, but not having compiler/run time support to do it
dynamically. In this case, we aren't looking for the hot spots to
optimize the code, but rather for things like total counts of various
kinds of operations.


It seems to be that the alternative ways of getting operation counts
from a code are to:


1) Have a physical hardware monitor which does it for you.
2) Periodically sample the code - with all of the problems related
      to sampling
3) Have the compiler generate reference counts at the basic block or
      statement level and use a postprocessor to get results
4) Read the code and derive equations based on various flow analyses
      which would give estimates of operation counts.
5) Some other mechanism I didn't think of.


We don't have access to 1 and 3, and various difficulties make 2 too
inaccurate to use. I am looking for help with 4 or 5. Any pointers
or references to papers or actual systems would be appreciated.


I am aware that static analysis won't work in the general case,
because of situations like:


        READ (5,100) N, (X(I),I=1,N)
        Y = 0.0
        DO 10 I = 1, N
        Y = Y + X(I)
        IF (Y .GT. 10.0) GO TO 15
  10 CONTINUE
  15 CONTINUE
        END


But if the IF statement was missing, this fragment might produce the
analysis:


READ AN INTEGER VALUE 1
INTEGER LVALUE N
INTEGER RVALUE N
READ AN FLOATING POINT VALUE N
FLOATING POINT STORE 2 * N + 1
FLOATING POINT RVALUE 2 * N
FLOATING POINT LVALUE N + 1
FLOATING POINT ADD N


(etc)


Anyway, I've just started looking into the problem, so any help at all
would be appreciated.


Marty
fouts@ames-nas.arpa
[This sounds a lot like the kind of things that people do when they try to
prove programs correct -- loop invariants and such. Another approach that
I have seen is to run the source program through a preprocessor which adds
tracing code into the source, then compile the resulting program with the
regular compiler. I'll try to find references on that, and as always invite
comment from the readership. -John]
--

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