# Data flow analysis questions

## johnl@ima.UUCP (John R. Levine)21 Mar 86 04:07:32 GMT

From comp.compilers

Related articles
Data flow analysis questions johnl@ima.UUCP (1986-03-21)
Re: Data flow analysis questions johnl@ima.UUCP (1986-04-07)
Re: Data flow analysis questions decvax!ucbvax!tektronix!ogcvax!pase (1986-09-23)
| List of all articles for this month |

 From: johnl@ima.UUCP (John R. Levine) Newsgroups: mod.compilers Date: 21 Mar 86 04:07:32 GMT Originally-from: sun!fluke!uw-beaver!entropy!dataio!bright (Walter Bright)

I have been fiddling around with data flow analysis for some time,
and have been presented with the problem of computing GEN and KILL
sets for basic blocks. In C, however, basic blocks can include
expressions with &&, || and ?: in them. The problem reduces to
computing GEN and KILL sets for:

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

Or, given GEN1,KILL1, GEN2,KILL2, GEN3,KILL3 how to we compute GEN and
KILL for the whole thing?

For example, for Available Expression analysis:

GEN = [(GEN1 - KILL2) | GEN2] & [(GEN1 - KILL3) | GEN3]
KILL = KILL1 | KILL2 | KILL3

I believe this is correct, but I can't figure out how to prove it.
Does anyone have a proof for it? I also need developed similar
identities for:

Very Busy Expressions
Reaching Definitions
Live Variables
Copy Propagation

Any theorists out their know the answers? Also, what are the
corresponding identities for:

while (e1)
e2;
--
-----------------------------------------------------------------------------
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