# 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