Re: reducible loops

lee@dumas.rutgers.edu (Yong-fong Lee)
26 Feb 92 16:21:30 GMT

          From comp.compilers
Related articles
reducible loops preston@cs.rice.edu (1992-02-24)
Re: reducible loops rockwell@socrates.umd.edu (Raul Deluth Miller-Rockwell) (1992-02-25)
Re: reducible loops preston@dawn.cs.rice.edu (1992-02-26)
Re: reducible loops lee@dumas.rutgers.edu (1992-02-26)
Re: reducible loops glew@pdx007.intel.com (1992-02-26)
Re: reducible loops preston@dawn.cs.rice.edu (1992-02-27)
Re: reducible loops joel@decwrl.dec.com (1992-02-28)
Re: reducible loops idacrd!desj@uunet.UU.NET (1992-03-09)
Re: reducible loops preston@dawn.cs.rice.edu (1992-03-10)
| List of all articles for this month |
Newsgroups: comp.compilers
From: lee@dumas.rutgers.edu (Yong-fong Lee)
Keywords: optimize, bibliography
Organization: Rutgers Univ., New Brunswick, N.J.
References: <9202220021.AA28153@ucbvax.Berkeley.EDU> 92-02-112
Date: 26 Feb 92 16:21:30 GMT



A flow graph is irreducible if it contains the following subgraph


a
/ \
/ \
| |
V V
---->
b c
<----I


where a, b and c are distinct, and edges among them represent
node-disjoint paths. Intuitively, an irreducible flow graph contains a
cycle with multiple entry nodes. In our example, nodes b and c are entry
nodes in a cycle.


Ryder and Paull's "Elimination algorithms for data flow analysis" (ACM
Computing Surveys, vol. 18, no. 3, Sept. 1986) is a good tutorial for four
elimination methods:


1. Allen-Cocke interval analysis,
2. Hecht-Ullman T1-T2 analysis,
3. Tarjan interval analysis, and
4. Graham-Wegman analysis.


Each of these methods provides some graph transformation(s) to reduce a
reducible flow graph into a single node.


Yong-fong
----------------------


@Article{allen:cacm76,
Author = "Frances E. Allen and John Cocke",
Title = "A Program Data Flow Analysis Procedure",
Journal = cacm,
Volume = 19,
Number = 3,
Year = 1976,
Pages = "137--147" }


@Article{graham:jacm76,
    author = "Susan Graham and Mark Wegman",
    title = "A fast and usually linear algorithm for global flow analysis",
    journal = jacm,
    year = "1976",
    volume = "23",
    number = "1",
    pages = "172-202",
    month = jan,
}


@Article{hecht:siamjc77,
    author = "Matthew S. Hecht and Jeffrey D. Ullman",
    title = "A Simple Algorithm for Global Data Flow Analysis Problems",
    journal = "SIAM Journal of Computing",
    year = "1977",
    volume = "4",
    number = "4",
    pages = "519-532",
    month = dec,
}


@article{ryder:cs86,
    author = "Ryder, Barbara G. and Paull, Marvin C.",
    title = "Elimination Algorithms for Data Flow Analysis",
    journal = "ACM Computing Surveys",
    volume = 18,
    number = 3,
    month = sep,
    year = 1986,
    pages = "277--316"}


@Article{tarjan:jcsc74,
    author = "Robert E. Tarjan",
    title = "Testing Flow Graph Reducibility",
    journal = "Journal of Computer and System Sciences",
    year = "1974",
    volume = "9",
    pages = "355-365",
}
--

Post a followup to this message

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