Data flow analysis questions

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

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