Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!uxc.cso.uiuc.edu!tank!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.c
Subject: Re: 2 lint questions
Message-ID: <18845@mimsy.UUCP>
Date: 1 Aug 89 01:47:19 GMT
References: <5967@ingr.com> <18796@mimsy.UUCP> <PAUL.89Jul31124616@marvin.moncam.co.uk>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 51

In some article someone asked:
>>Is there any way to get lint to detect a closed loop of code which can
>>never be called?

>In article <18796@mimsy.UUCP> I suggested that
>Lint would need to do call graph analysis to find these; I have never
>seen one that does.

In article <PAUL.89Jul31124616@marvin.moncam.co.uk> paul@moncam.co.uk
(Paul Hudson) replies:
>Don't hold your breath - determining whether code is reachable is
>equivalent to the halting problem. Lint takes long enough already -
>infinite time seems a little over-the-top.

This is true.  The problem of discovering that some code is not
reachable is, however, simpler.  That is, there exist code sequences
that are easy to prove unreachable.  Although there are some sequences
that are unsolvable---for instance,

	if (other_program_halts())
		fn();
	else
		exit(0);

---there are plenty of sequences that *are* solvable, such as

	int main() { return 0; }
	void a() { b(); }
	void b() { a(); }

and it would certainly be `in the spirit of lint' to find such.

Note that this problem is essentially the same as discovering that

	f()
	{
		goto skip;
	loop:
		notused();
		goto loop;
	skip:
		used();

	}

contains unreachable code, except that the scope over which one
must analyse is greater.  Of course, lint does not catch this last
example either.
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris