Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!usenet.ins.cwru.edu!agate!dog.ee.lbl.gov!elf.ee.lbl.gov!torek
From: torek@elf.ee.lbl.gov (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: Can analysis detect undefined expressions?
Message-ID: <14394@dog.ee.lbl.gov>
Date: 18 Jun 91 07:09:53 GMT
References: <14206.285B7688@stjhmc.fidonet.org>
Reply-To: torek@elf.ee.lbl.gov (Chris Torek)
Organization: Lawrence Berkeley Laboratory, Berkeley
Lines: 50
Supersedes: <14392@dog.ee.lbl.gov>
X-Local-Date: Tue, 18 Jun 91 00:09:53 PDT

(I realized shortly after posting article <14392@dog.ee.lbl.gov> that its
example was incorrect.  Those of you whose news systems do not understand
the "Supersedes" header may see it anyway.  Sorry about that.)

>>From: ckp@grebyn.com (Checkpoint Technologies)
>>I'd like to know if there has been any attempt to diagnose such undefined
>>expressions.  It seems like an exceedingly difficult thing to do ...

In article <14206.285B7688@stjhmc.fidonet.org>
Dave.Harris@f14.n15.z1.fidonet.org (Dave Harris) writes:
>On the whole, I would say it is NOT possible to contend with every case.

Indeed, it is fairly easy to show that no compiler can diagnose all
misuses correctly.  On the other hand, diagnosing obvious misuses is
easy, and most `lint's, for instance, will note that:

	i = i++ + i++;

is undefined.  The interesting part comes in trying to catch the less
obvious misuses without catching non-obvious non-misuses.  For instance,

	if (use_j)
		p = &j;
	else
		p = &a[j];
	*p += foo;
	if (something)
		*p *= 2;
	if (anotherthing)
		*p /= 3;
	use(*p);
	if (use_j)
		done_j();
	else
		j += (*p)++;

may be correct (if use() modifies use_j, it may be incorrect as well),
but deciding for certain whether it is or is not is a hard problem.  I
believe that a global-analysis system would be able to decide `correct'
or `incorrect' (rather than `don't know') in most real code, and that
it could do so in a sufficiently small amount of time to make it worth
running on `high stakes' code such as that found in embedded medical
systems.  That is, I think that a decent analysis program could point
out a minimum number of questionable cases after running on a powerful
system for only a few months or even weeks.  As we learn more, and the
system becomes more effective, I think such analysis will become
commonplace, but this seems to be a number of years away.
-- 
In-Real-Life: Chris Torek, Lawrence Berkeley Lab CSE/EE (+1 415 486 5427)
Berkeley, CA		Domain:	torek@ee.lbl.gov