Normalization of control flow graphs

Hi,


I am trying to implement a normalization of a control flow graph as the
one Zahira Ammarguellat proposed in the article "A Control-Flow
Normalization Algorithm and its Complexity".


The trick she uses to normalize the CFG with is by, among other things,
to create a DFST of the CFG and remove the back and cross edges to
create a DAG. However, I can not see why the topological order of the
DAG is unique, because you can develop the DFST in so many ways, i.e.
cross edges could be forward edges in some of the DFST's. For instance:
Let say we have a flow


S -> A | B
B -> A | T
A -> A | T
T


Then one DAG as described above would be


S -> A -> T
      -> B


with topological order (S, A, B, T) or (S, B, A, T) depending on what
order the children are processed in.


and another could be


S -> B -> T
                -> A


here the topological order would be (S, B, T, A) or (S, B, A, T).


It seems like in my implementation that it really matters which way the
nodes are topological ordered.


My question is: What am I doing wrong? What have I misunderstood? (If
this is the wrong forum for these questions could you please refer me to
a more appropriate one.)


Best regards,
      Kristian Bisgaard Lassen

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