Re: loops in irreducible graph? (Cliff Click)
Thu, 13 Jan 1994 14:53:50 GMT

          From comp.compilers

Related articles
loops in irreducible graph? (1994-01-12)
Re: loops in irreducible graph? (1994-01-13)
Re: loops in irreducible graph? (1994-01-14)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Cliff Click)
Keywords: optimize, analysis
Organization: Center for Research on Parallel Computations
References: 94-01-042
Date: Thu, 13 Jan 1994 14:53:50 GMT (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:

    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.

-- -- Massively Scalar Compiler Group, Rice University

Post a followup to this message

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