Xref: utzoo comp.lang.c:34596 comp.lang.fortran:4342 Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!hsdndev!cmcl2!kramden.acf.nyu.edu!brnstnd From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein) Newsgroups: comp.lang.c,comp.lang.fortran Subject: Re: Fortran vs. C, and noalias: old postings, new data Message-ID: <2026:Dec1000:49:0990@kramden.acf.nyu.edu> Date: 10 Dec 90 00:49:09 GMT References: <221@validgh.com> Organization: IR Lines: 70 To skip to the big question search for ``throw''. In article tmb@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