# Re: loops in irreducible graph?

## cliffc@rice.edu (Cliff Click)Thu, 13 Jan 1994 14:53:50 GMT

From comp.compilers

Related articles
loops in irreducible graph? sreedhar@sally.cs.mcgill.ca (1994-01-12)
Re: loops in irreducible graph? cliffc@rice.edu (1994-01-13)
Re: loops in irreducible graph? stoltz@cse.ogi.edu (1994-01-14)
| List of all articles for this month |

 Newsgroups: comp.compilers From: cliffc@rice.edu (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

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}

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
--

Post a followup to this message