johnl@ima.UUCP (John R. Levine) (03/21/86)
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
johnl@ima.UUCP (Compilers mailing list) (09/29/86)
In article <ima.181> Rob Warnock writes: > My two workhorse references on data-flow (and control-flow) analysis > are: > > 1. William Wulf, et. al., "The Design of an Optimizing Compiler", > (American-Elseivier 1975). > > 2. Hecht, "Flow Analysis of Computer Programs" (North-Holland 1977). I've been hunting high and low for copies of these two books, and yes, they really are out of print. Does anyone have a spare copy or know of one that they might be willing to part with for a reasonable price? (I'm especially after the first reference.) I could sure use some help finding them. Doug Pase -- ...ucbvax!tektronix!ogcvax!pase or pase@Oregon-Grad -- Send compilers mail to ima!compilers or, in a pinch to Levine@YALE.EDU Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | bbncca}!ima Please send responses to the originator of the message -- I cannot forward mail accidentally sent back to compilers. Meta-mail to ima!compilers-request