Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site ima.UUCP
Path: utzoo!decvax!cca!ima!johnl
From: johnl@ima.UUCP (John R. Levine)
Newsgroups: mod.compilers
Subject: Data flow analysis questions
Message-ID: <170@ima.UUCP>
Date: Thu, 20-Mar-86 23:07:32 EST
Article-I.D.: ima.170
Posted: Thu Mar 20 23:07:32 1986
Date-Received: Sat, 22-Mar-86 07:45:09 EST
Lines: 49
Approved: <compilers@ima.UUCP>
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