Fortran vs. C, and noalias: old postings, new data

[Dan Bernstein]

To skip to the big question search for ``throw''.

In article <TMB.90Dec7234544 at bambleweenie57.ai.mit.edu> tmb at bambleweenie57.ai.mit.edu (Thomas M. Breuel) writes:
> A clean way of doing this is by providing a separate looping construct
> with special semantics. For example, you could add a "parallel"
> construct, which carries with it the implicit assumption that there
> are no sequential dependencies among the loop body, or a "vectorloop"
> construct, which carries with it the implicit assumption that all
> sequential dependencies are lexically apparent to the compiler (a kind
> of "noalias" assumption for loop bodies).

I've been trying that in Q but have hit some snags.

My first try was forall. forall is just like for, but first executes the
increment and loop test until it knows what all the values of all index
variables are, then runs the loop in parallel for all the values, or for
a random order of the values. The problem is that a vector machine may
produce pure garbage if you have unexpected aliasing. That result
wouldn't correspond to any executions of the loop in any order.

So I added the obvious restriction: the program must not depend on the
order of execution. But what does this mean? What if a program did
forall(i = 0;i < 100;i++) x[i] = y[i], then used some sort of checksum
to test whether x was valid, then repeated the computation with more
reliable techniques and produced a guaranteed answer? I didn't want to
allow this, but the program would produce correct results no matter
what. How can you disallow the above loop if x and y are aliased?

Then I tried vector. vector loops a specified set of linearly dependent
variables through a linear set of values. This makes some things easier
to define but still doesn't avoid the problem.

My latest attempt is to say that no execution or evaluation of any
statement in the loop can depend on the order of the indices. So in

  forall(i = 0;i < 100;i++) x[i] = y[i]

we can *almost* disallow y[j] being at the same location of x[k]. After
all, i could take on the value of k first, then y[j] would be
overwritten with y[k], and when i took on the value of j, y[k] would be
corrupted. But if y overlaps x exactly, or if y[j] equals y[k], then
this still doesn't change.

So I throw this problem to the net. What restrictions can you put on
forall() so that the optimizer can know x and y are unaliased in this
loop?

  forall(i = 0;i < 100;i++) x[i] = y[i];

I want forall to work just like for, but to work ``the same'' if i runs
through 0..99 in a different order. But there has to be a further rule
to imply that x and y are unaliased. Maybe something like ``no input
inside the loop can be from the same location as an output inside the
loop''? But I worry that this will prohibit something useful.

> Adding a general notion of "noalias" to a language with lots of
> pointers and nested data structures would probably lead to chaos,

I doubt it. If in Q you say

  assert(x notin 100 of y);
  assert(y notin 100 of x);
  for(i = 0;i < 100;i++) x[i] = y[i];

then even my primitive q2c knows that the loop can be vectorized (not
that it can do anything about it). Note that ``assert'' is a pure
assertion mechanism---it isn't defined to do anything in particular if
the expression isn't true. The expression *must* be true.

---Dan