Re: loops in irreducible graph?

sreedhar@sally.cs.mcgill.ca (V.C. SREEDHAR) writes:
      There are many ways to identify loops/nested loops (sometimes also called
      as natural loops) for reducible flowgraph. Can someone point to me how to
      identify loops in irreducible graph? or rather loops/nested-loops that
      are not reducible (in the usual sense of definition[1]). The notion of
      loops is little tricky for multiple entry loops.


Use a variation of Tarjan's:


    @Article{Tarj:Testing,
    Author={R. E. Tarjan}, Title={Testing Flow Graph Reducibility},
    Journal={Journal of Computer and System Sciences}, Volume={9},
    Pages={355-365}, Year=1974, location=95}


Basically, each loop can have several headers instead of just one.


My code takes in a CFG and builds loop trees out of loop nests. It
handles loops that share the same header (one block heads multiple loops)
as well as irreducible loops (one loop has multiple blocks heading it).


If there is enough desire I can post my C++ code for doing this thing.
Otherwise, I will just hand out email. Be warned: this code comes from
inside a compiler, and interacts with the compiler in crufty ways. It is
not a clean "algorithms book" implementation.


Cliff
--
cliffc@cs.rice.edu -- Massively Scalar Compiler Group, Rice University
--

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