Related articles 

Data flow analysis questions johnl@ima.UUCP (19860321) 
Re: Data flow analysis questions johnl@ima.UUCP (19860407) 
Re: Data flow analysis questions decvax!ucbvax!tektronix!ogcvax!pase (19860923) 
From:  johnl@ima.UUCP (John R. Levine) 
Newsgroups:  mod.compilers 
Date:  21 Mar 86 04:07:32 GMT 
Originallyfrom:  sun!fluke!uwbeaver!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@CCAUNIX or ima!compilers@BBNCCA
Return to the
comp.compilers page.
Search the
comp.compilers archives again.