recording the program flow

[jacob navia]

Suppose that you want to know where your program has
passed, i.e. the exact flow of the program.

A brute force solution is to make an array of n lines, n being
the number of lines in the function. At each line then, you increment
a variable like this:

// NRLINES is the number of lines in the program module
int lines[NRLINES];
int fn(int a)
{
int s;
a = a + 1; lines[__LINE__]++;
s = a -= 1; lines[__LINE__]++;
etc
}

At the end of the run, you write into a file all those arrays. For each
source file you get one.

Obviously this is very inefficient. In the concrete example
above it would suffice a single counter since if you get
into that function at all, all the counters must have the
same value, there are no iterations constructs, gotos etc.

Refining this we could say that it suffices a single counter
for each basic block, i.e. between a label and a control
flow instruction (jump).

Function calls are a problem because they could indirectly call
longjmp and jump to a function higher in the stack.

I would like to research this a bit. Does anyone here know of
references to this problem in the literature?

Thanks in advance

jacob

[Ben Pfaff]

"jacob navia" <ja***@jacob.re mcomp.fr> writes:

Suppose that you want to know where your program has
passed, i.e. the exact flow of the program.
[...]
I would like to research this a bit. Does anyone here know of
references to this problem in the literature?

For me, because I work with whole-system simulators and virtual
machine monitors extensively, the "obvious" solution seems to be
to use the simulator to record the program's flow. For example,
on x86 Linux you could adapt valgrind to keep track of which
basic blocks are executed.
--
int main(void){char p[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Eric Sosman]

jacob navia wrote:

Suppose that you want to know where your program has
passed, i.e. the exact flow of the program. [...]

The illustrative code you provided didn't record what
I'd understand as the "flow" of the program: that would
include not only how many times you'd reached a particular
spot in the program, but also how you happened to arrive
there and where you went next. From the code, I think
what you're looking for is "coverage analysis," a phrase
that gets plenty of hits on Google.

--
Er*********@sun .com

[jacob navia]

Didn't know about valgrind. Looks like a monster software...

Thanks a lot for this reference

[jacob navia]

The application I have in mind is when you hit a breakpoint in
my debugger, to be able to show the user the trace of the
last x lines executed, i.e to help the user understand how the
program got there.

jacob

[Keith Thompson]

"jacob navia" <ja***@jacob.re mcomp.fr> writes:

The application I have in mind is when you hit a breakpoint in
my debugger, to be able to show the user the trace of the
last x lines executed, i.e to help the user understand how the
program got there.

Then the solution you mentioned in your original post:

lines[__LINE__]++;

won't do it; it just counts the number of times each line is executed.

What you want is something like:

trace[index++] = __LINE__;

Avoiding overflow and other such details are left as an exercise.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[jacob navia]

A circular buffer will suffer from loops, that can swamp
the buffer if taken several hundred times, not an uncommon
thing in computer programs.

Of course is simple and easy to implement. But there
must be scientists that have researched this before, (at
least I think), and that have better solutions that either
mine or yours.

I mean tracing a program is not a new thing...

In Google I found only links about manual tracing,
some exercises for a university class...

In citeseer I found
Optimally Profiling and Tracing Programs
http://citeseer.ist.psu.edu/ball92optimally.html
but it is from 1992. I thought there could be more recent
work.

In any case I will start trying to understand that one.
It isn't easy reading... sigh.

[Rob Thorpe]

"jacob navia" <ja***@jacob.re mcomp.fr> wrote in message news:<ce******* ***@news-reader5.wanadoo .fr>...

A circular buffer will suffer from loops, that can swamp
the buffer if taken several hundred times, not an uncommon
thing in computer programs.

Of course is simple and easy to implement. But there
must be scientists that have researched this before, (at
least I think), and that have better solutions that either
mine or yours.

I mean tracing a program is not a new thing...

In Google I found only links about manual tracing,
some exercises for a university class...

In citeseer I found
Optimally Profiling and Tracing Programs
http://citeseer.ist.psu.edu/ball92optimally.html
but it is from 1992. I thought there could be more recent
work.

In any case I will start trying to understand that one.
It isn't easy reading... sigh.

It's something some Lisp systems can do. Maybe you could have a look
at the code of one.