Xref: utzoo comp.lang.c:34704 comp.lang.fortran:4383
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!uwm.edu!psuvax1!hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.c,comp.lang.fortran
Subject: Re: alternatives to "noalias"?
Message-ID: <1682:Dec1108:57:4190@kramden.acf.nyu.edu>
Date: 11 Dec 90 08:57:41 GMT
References: <14065@june.cs.washington.edu> <12873:Dec1021:09:2890@kramden.acf.nyu.edu> <12337@life.ai.mit.edu>
Organization: IR
Lines: 28

In article <12337@life.ai.mit.edu> tmb@ai.mit.edu writes:
> In article <12873:Dec1021:09:2890@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
    [ how to define forall? ]
> There are several useful abstractions:
  [ some possibilities ]

But you aren't addressing the real problem. See below.

> |> If the programmer writes
> |>   forall(i = 0;i < 100;i++) x[i] = y[i];
> |> then the compiler had better be able to conclude that x and y don't
> |> overlap. 
> No, they may overlap.

No! There are vector and parallel machines where the compiler must
generate vastly different code when x and y overlap and when they don't.
Parallel code when x = y is simply *wrong*. It will generate garbage
results. Even if x and y are all filled with the same values, the above
loop may produce new values if the arrays overlap and it is run in
parallel! So any definition along the lines of ``the results must not
depend on the order of execution'' is *not enough*. Two parallel writes
may produce different results from any serial execution of the writes.

*This* is the optimization problem we have to solve. An assertion of
non-aliasing solves the problem, but forall would be a lot more
convenient. How do we define it?

---Dan