Re: C constant expressions proposals

[Joe Buck <Joe dot Buck at synopsys dot COM>]

On Wed, Aug 18, 2004 at 12:31:51PM -0400, Robert Dewar wrote:
> I am confused. Full detection of undefined variables requires full
> flow analysis and solution of data flow equations.

Agreed; you need lots of optimization to do a decent job of detection
of undefined variables.

Even data flow equations don't really suffice to do an accurate job,
as that approach misses correlations between branches.  Avoiding certain
common kinds of false positives would require something like gated single
assignment.

typedef ... T;
bool expensive_test();
void do_something();
T* give_me_a_pointer();
void use(T*);

void foo() {
    bool flag = false;
    T* p;
    if (expensive_test()) {
	p = give_me_a_pointer();
	flag = true;
    }
    do_something();
    if (flag) {
	use(p);
    }
}

Flow analysis and solution of data flow equations will say that the call
to use() might use an uninitialized p.  The programmer could initialize p
to NULL but that is a wasted store.  Here's a gated SSA form:

void foo() {
    flag$1 = false;
    p$1 = <uninitialized>;
    $cond = expensive_test();
    if ($cond) {
	p$2 = give_me_a_pointer();
	flag$2 = true;
    }
    flag$3 = gated_phi($cond, true, false);
    p$3 = gated_phi($cond, p$2, p$1);
    do_something();
    if (flag$3) {
	use(p$3);
    }
}

gated_phi is a phi with a condition specifying which value is to be used;
it is therefore equivalent to the C ?: operator (though don't go turning
it into a jump; that kills the whole reason for using it).

But gated_phi($cond, true, false) is just $cond.  We then can turn the
last if into

    if ($cond) {
	use(gated_phi($cond, p$2, <uninitialized>));
    }

but since $cond is true in the true branch of the if, just

	use(p$2);

and we've proven that p cannot be used uninitialized.

Alternatively, this approach can determine that p$1 is dead if the user
had written

	T* p = 0;

to silence the existing uninitialized variable warning.