Path flow and Control Flow Problems

I am trying to find out if there are any references on Path analysis of
Control Flow Graphs. Given a source program ( say, in a language like
VHDL ), the first step that I am concerned with is the generation the
Control Flow Graph for the given description ( I had mentioned about this
in my previous posting ).


After the generation of the Control Flow graph, I would have to do an
analysis and enumerate the set of all "fesable" paths that can be taken
from the beggining to the end of the program. (My ultimate goal is
generation of test data through symbolic path execution).


This seems to be non-trivial since I might be faced with the following
situation:
                                                                                                      :
                                                                                                P1 : i = 0
                                                                                                      |
                        : /\ i > 10
                        : ____________/ \__________
                i = 0; | \ / Not P2 |
                while ( i <= 10 ) do | \/ |
                        if i == 10 | P2 | i <= 10 |
                                j = 1; | | |
                                i = i + 1; | / \ |
                        else | i=10 / \ i != 10 |
                                i = i + 1; | ----\ /--- |
                        endif | P3 | \ / | NotP3|
                                                                            | | | |
                end while | j = 1 i = i + 1 |
                        : | i = i + 1 | |
                        : |______|__________| |
                                                                                                                              |
                                                                                                      ____________|
                                                                                                      |
                                                                                                      :
                                                                                                      :




Now in the given type of situation, I would somehow have to know that the
'if' sub-path ( which might be part of my path from the start to the end
of the program ) will only be executed after I execute the 'else' part of
the sub-path 10 times, so that i becomes 10 at the last iteration and then
the 'if' path can get executed. Now, this kind of analysis cannot be done
without prior information of how the value of i gets affected in the
'else' part when I encounter the 'if' part the first time. In other
words, according to the figure, My possible paths from the beggining to
the end will be:


        (1) ...P1 P2 (Not P3) (Not P3)...(Not P3) P3 (Not P2)...


and this will be the only possiblity from the beggining to the end of the
while loop.


My question is : How do I do this kind of path analysis and come up with
all the possible paths that are possible from the begin to the end of my
program description?


I will be very thankful if anyone can offer me any suggestions for the
above 2 questions ( first on the generation of the control flow graph from
a given source program and the second is path analysis of the CFG and come
up with all the possible paths that have to be traversed from the begin to
the end.


Can you please send your replies directly to my e-mail address.


Thanks in advance.


-- Ravi
RAVISHANKAR
Digital Design Environments Lab
Dept. of Elec. and Comp. Engg
University of Cincinnati


E-mail : ravi@thor.ece.uc.edu
Work Phone : (513) 556 - 3025
--

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