Re: Death by pointers.

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.


It's simple to show this- think of the case where there are two possible
paths, one of which leads to the node with the pointer. The selection of
the path might involve an arbitrary function.


Anyway, there is a solution to this problem, although I'm not sure if it's
worthwhile. You just completely skip alias detection in the compiler.
Assume that there is no alias to your pointer and load it into a register if
doing so will help optimize the code. The trick is to also load an
extension to the register with the address of the origin of the pointer.
Now whenever the CPU does a store, it checks the address of each loaded
pointer. If any registers have the pointer, the register gets an update.
Basically the registers act like a sort of mini-cache.


The extra bits needed for each regsister are probably not much of a problem.
Also a special pointer load instruction wouldn't cost anything. I don't
think that pipelining will interfere with the operations either. The only
really critical part is the speed at which you can do the address
comparisons and the size of the hardware needed to do them. The fact that
there are processors like the R4000 and Alpha, which have TLBs before the
on-chip cache means that this extension might just be possible.


>The thing that makes C a nightmare for optimisation is the
>all-pervading nature of pointers along with the widespread use of void
>pointers which can implicitly cast all over the place. At least if you
>have a constrained pointer model like in Pascal (where pointers are
>only allowed onto the heap) you can contain the alias detection
>problem to the bits of code that are actually manipulating your linked
>list, or whatever. In C, dataflow analysis is essentially impossible,
>which for me is very scary. (Life threatening systems programmed with
>pointers? Just say no.).


Oh? And just which programming system would you trust for life-threatening
systems? The answer is that there are none, and such machines (like
radiation therapy systems), use hardware interlocks (except for the
(I think it's called) Therac-25, which resulted in several deaths, and the
space shuttle guidance computers, which are only trusted because of
extensive testing).


>In the not so distant future, all common computers will use
>superscalar processors of one form or another, and I predict that the
>detailed dataflow analysis required to get the best out of these
>machines will mandate a move towards languages which are easier to
>analyse, that is with restricted use of pointers and possibly a
>complete lack of side effects.


Ah, but how do the benefits of these restrictions balance against the cost
of the inconvenience of the programming systems which result? Try
programming in LabView for a while and then tell me you want no side-
effects or variables.
--
/* jhallen@world.std.com (192.74.137.5) */ /* Joseph H. Allen */
--

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