Re: Death by pointers.

whitten@netcom.com (David Whitten)
Tue, 5 Sep 1995 15:48:38 GMT

          From comp.compilers
Related articles
Order of argument evaluation in C++, etc. hbaker@netcom.com (1995-07-08)
Re: Order of argument evaluation in C++, etc. jan@neuroinformatik.ruhr-uni-bochum.de (1995-08-25)
Death by pointers. (Was: order of argument evaluation in C++, etc.) johnston@imec.be (1995-08-30)
Re: Death by pointers. jhallen@world.std.com (1995-09-05)
Re: Death by pointers. whitten@netcom.com (1995-09-05)
Re: Death by pointers. chase@centerline.com (1995-09-06)
Re: Death by pointers. hbaker@netcom.com (1995-09-11)
Re: Death by pointers. graham.matthews@pell.anu.edu.au (1995-09-12)
Re: Death by pointers. chase@centerline.com (1995-09-12)
Re: Death by pointers. preston@tera.com (1995-09-13)
Re: Death by pointers. ECE@dwaf-hri.pwv.gov.za (John Carter) (1995-09-23)
[1 later articles]
| List of all articles for this month |
Newsgroups: comp.compilers
From: whitten@netcom.com (David Whitten)
Keywords: optimize, analysis
Organization: NETCOM On-line Communication Services (408 261-4700 guest)
References: 95-07-068 95-08-195 95-09-030
Date: Tue, 5 Sep 1995 15:48:38 GMT

Adrian Johnstone (johnston@imec.be) wrote:
: On the sub-issue of alias detection as a problem in argument evaluation:


: : Unless I'm very much mistaken, alias identification is an insoluble
: : problem, and flagging order dependencies in expressions runs straight into
: : that wall.


: : Well, I guess it's insoluble in general (no my area of expertise), but it is
: : certainly possible and useful. It's clear that this is really what we're
: : talking about.


: In the C language, alias detection in the presecence of recursive data
: structures (i.e. linked lists and up) is an NP-complete problem, which
: certainly meets my definition of insoluble ;-). I'm not at home right
: now so I can't find the reference but it's derived in someone's PhD
: theis. Actually it's not at all surprising if you think about it. I
: would rather suppose that this result is true in any pointer-using
: language, including Pascal et al.


So the NP-Complete problem only occurs with languages that define
recursive data structures? What about a language where the only
aliasing that can occur is when parameter passing exists? (and
no variables may store explicit addresses?)


In this language, assume you can pass components of bundle/record/struct's
as parameters, and that you can pass store the NAME of a variable as the
value of a variable (and lookup a variable's value using its name later).


I'm sure the storage of Names and lookup of a name is very similar to
pointers, but doesn't have the same implications as real address pointers
in terms of garbage collection, but the only aliasing happening through
parameter passing seems to limit the alias detection problem to me.


I'm posting because I expect someone who actually has read these
results might be able to elaborate whether this limits the alias detection
problem sufficiently to make it solvable.


David (Whitten@netcom.com) (214) 437-5255
[Seems to me it'd be easy enough to construct alias problems which reduce to
the halting problem. -John]


--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.