GEN/KILL sets

johnl@ima.UUCP (John R. Levine)
23 Mar 86 01:31:59 GMT

          From comp.compilers
Related articles
GEN/KILL sets johnl@ima.UUCP (1986-03-23)
| List of all articles for this month |
Relay-Version: version B 2.10.2 9/12/84; site mit-prep.ARPA
Posting-Version: version B 2.10.2 9/18/84; site ima.UUCP
From: johnl@ima.UUCP (John R. Levine)
Newsgroups: mod.compilers
Date: 23 Mar 86 01:31:59 GMT
Article-I.D.: ima.171
Posted: Sat Mar 22 20:31:59 1986
Date-Received: 24 Mar 86 11:46:54 GMT

Given the following flow graph:


|
+---+
| 1 |
+---+
| Flow is from top to bottom.
+---------+----------+ Diagram for construct:
| |
            +---+ +---+ if (e1)
            | 2 | | 3 | e2;
            +---+ +---+ else
                | | e3;
+---------+----------+
|


The question is, given GEN and KILL for each node, what is GEN and
KILL for the whole graph? Aho, Sethi, and Ullman, in "Compilers:
Principles, Techniques, and Tools", p. 608, define GEN as the
information generated within a statement, and KILL as the information
killed by statement. They give set equations on page 612 that can be
composed to get the desired answer.


The information generated by the complete graph is the information
generated by node 1, and not killed by both nodes 2 and 3, plus the
information generated by either node 2 or 3, so


GEN = (GEN1 - (KILL2 & KILL3)) | (GEN2 | GEN3)


The information killed by the complete graph is the information killed
by node 1 and not generated by either node 2 or 3, together with the
information killed by both nodes 2 and 3.


KILL = (KILL1 - (GEN2 | GEN3)) | (KILL1 & KILL2)


Their interpretations of GEN and KILL are more precisely: the
information potentially generated along any path within a node, and the
information definitely killed along any path within a node,
respectively.


The situation gets more confused when loops, breaks, continues, and
gotos intrude.


In more complicated circumstances, such as Modula-2, with its
multi-level loop exits, it makes more sense to think of flow
attributes as being path attributes rather than node attributes.


-- Richard Schooler
Intermetrics, Inc.
{ihnp4,ima}!inmet!schooler
--
-----------------------------------------------------------------------------
Send submissions to: ima!compilers


ima is reachable as { ucbvax!cbosgd | ihnp4 | cca | bbncca | think |
uiucdcs | allegra | inmet | yale | harvard }!ima!...
Arpa mail may make it to ima!compilers@CCA-UNIX or ima!compilers@BBNCCA


Post a followup to this message

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