16 Apr 2005 11:12:19 -0400

Related articles |
---|

Normalization of control flow graphs krell@daimi.au.dk (Kristian Bisgaard Lassen) (2005-04-16) |

From: | Kristian Bisgaard Lassen <krell@daimi.au.dk> |

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 |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.