Normalization of control flow graphs

Kristian Bisgaard Lassen <>
16 Apr 2005 11:12:19 -0400

          From comp.compilers

Related articles
Normalization of control flow graphs (Kristian Bisgaard Lassen) (2005-04-16)
| List of all articles for this month |

From: Kristian Bisgaard Lassen <>
Newsgroups: comp.compilers
Date: 16 Apr 2005 11:12:19 -0400
Organization: UNI-C
Keywords: optimize, analysis
Posted-Date: 16 Apr 2005 11:12:19 EDT


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

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

Post a followup to this message

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