johnl@ima.UUCP (John R. Levine) (03/23/86)
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