recording the program flow

Discussion in 'C Programming' started by jacob navia, Jul 28, 2004.

  1. jacob navia

    jacob navia Guest

    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
     
    jacob navia, Jul 28, 2004
    #1
    1. Advertising

  2. jacob navia

    Ben Pfaff Guest

    "jacob navia" <> 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[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
    \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
    );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p\
    );}return 0;}
     
    Ben Pfaff, Jul 28, 2004
    #2
    1. Advertising

  3. jacob navia

    Eric Sosman Guest

    [OT] Re: recording the program flow

    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.

    --
     
    Eric Sosman, Jul 28, 2004
    #3
  4. jacob navia

    jacob navia Guest

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

    Thanks a lot for this reference
     
    jacob navia, Jul 28, 2004
    #4
  5. jacob navia

    jacob navia Guest

    Re: [OT] Re: recording the program flow

    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
     
    jacob navia, Jul 28, 2004
    #5
  6. Re: [OT] Re: recording the program flow

    "jacob navia" <> 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_Keith) <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.
     
    Keith Thompson, Jul 28, 2004
    #6
  7. jacob navia

    jacob navia Guest

    Re: [OT] Re: recording the program flow

    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.
     
    jacob navia, Jul 29, 2004
    #7
  8. jacob navia

    Rob Thorpe Guest

    Re: [OT] Re: recording the program flow

    "jacob navia" <> wrote in message news:<ce9cp7$39c$>...
    > 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.
     
    Rob Thorpe, Jul 29, 2004
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. KathyB
    Replies:
    0
    Views:
    307
    KathyB
    Jul 20, 2003
  2. Dovelet
    Replies:
    6
    Views:
    365
    Mabden
    Nov 14, 2005
  3. utab
    Replies:
    18
    Views:
    1,714
    Diego Martins
    Apr 27, 2006
  4. Jack Dowson
    Replies:
    0
    Views:
    481
    Jack Dowson
    May 7, 2007
  5. Skybuck Flying
    Replies:
    1
    Views:
    68
    Dan Stromberg
    Apr 3, 2014
Loading...

Share This Page