Drawing CFGs

Manel Fernandez <mfernand@ac.upc.es>
28 Jun 2001 23:45:38 -0400

          From comp.compilers

Related articles
Drawing CFGs mfernand@ac.upc.es (Manel Fernandez) (2001-06-28)
Re: Drawing CFGs timothyc@huginn.CS.Berkeley.EDU (2001-07-27)
| List of all articles for this month |

From: Manel Fernandez <mfernand@ac.upc.es>
Newsgroups: comp.compilers
Date: 28 Jun 2001 23:45:38 -0400
Organization: Computer Architecture Department
Keywords: tools, question
Posted-Date: 28 Jun 2001 23:45:38 EDT

-- Hi all,

I'm writing a tool for drawing CFGs. To do this, a little routine
assigns a 'level' to every basic block (BB), in order to draw the CFG in
a top-down way.

My approach is the following: starting from the entry point (level 0), I
go through every BB in the CFG. Being X a particular BB, and succ(X,i)
the i-th succesor of X:

        for every i in successors(X)
            if ( level(succ(X,i)) <= level(X) ) then
                  level(succ(X,i)) := level(X) + 1;

The algorithm is applied iterativelly, until a solution is found. In
this loop, all the "back edges" (that is, [succ(X,i) dominates X]) are

The algorithm works very well with CFGs that only contains 'natural
loops'. However, it never ends with CFGs containing non-natural loops.
This was something expected, since the 'back edge' definition using
domination information is restrictive.

How could I deal with non-natural loops?



    o o o Manel Fernandez Gomez
    o o o Department of Computer Architecture Phone: +34 93 401 7187
    o o o Universitat Politecnica de Catalunya Fax : +34 93 401 7055
                  C/ Jordi Girona, 1-3
                  Campus Nord, Modul D6-116 mailto:mfernand@ac.upc.es
    U P C 08034 BARCELONA (SPAIN) http://www.ac.upc.es/homes/mfernand

Post a followup to this message

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