Re: PATCH to implement `restrict' in C

[Mark Mitchell <mark at markmitchell dot com>]

>>>>> "Richard" == Richard Henderson <rth@cygnus.com> writes:

    Richard> On Sat, Oct 10, 1998 at 02:50:06PM -0700, Mark Mitchell
    Richard> wrote:

    >> Unfortunately, your understanding is incorrect. :-)

    Richard> I'm not convinced.

I think the draft clearly supports my point of view.  Do you have
specific concerns?

    >> "A pointer expression E is said to be based on P if
    >> ... modifying P to point to a copy of the array into which it
    >> formerly pointed would change the value of E."

    Richard> Yes.

    >> void h(int n, int* const restrict p, int* const q, int* const
    >> r) { ... }
    >> 
    >> where, as explained in the draft, the const-ness of `q' and `r'
    >> prevents them from becoming based on `p'.  However, if they
    >> were non-const, all bets are off; it would be legal to write:
    >> 
    >> q = p; q[0] = p[0];

    Richard> But if the assignment `q = p' did not exist, then Q could
    Richard> not be said to be based on P and so there is no aliasing
    Richard> possible.

Right.  But, you can't tell this apriori.  The point is that the mere
restrict-ness of a pointer doesn't ensure that it doesn't alias other
pointers.  You are correct that you could in general solve this with
data-flow analysis; however, in principle, the same could be said
about *all* alias analysis.  (Of course, alias analysis is Turing
complete, so sometimes a hint from the user really is essential.)

The point of `restrict', like the rules on types not being able to
alias one-another, or that `const' objects cannot be modified, is
partly to make the compiler's job easier by avoiding the need to do as
much analysis.  In fact, the draft notes at one point that "the const
qualifiers imply, without the need to examine the body of h, that q
and r cannot become based on p".  (There are other reasons for these
keywords as well, of course, like self-documentation.)

    Richard> Solving this correctly is a data flow problem.  I guess
    Richard> you are trying for a subset of the full solution, though
    Richard> its so restricted I'm not sure how useful it would
    Richard> actually be.  If I understand your proposal correctly,
    Richard> given

    Richard> 	void foo(int * restrict a, int * b) { int i; for (i =
    Richard> 0; i < 100; i++) b[i] = a[i] + a[i-1]; }

    Richard> you would incorrectly report true_dependance between B[i]
    Richard> and A[i-1].

Correct.  Note that if, by some data flow analysis, you can show that
b is never assigned to, you can make the alias set for `b' be a subset
of `int', and then get the benefit you would hope for.  I intend to
this for `const' pointers, next, which is a common case in which data
flow analysis is not required.  All optimization solutions represent
only a subset of the "full" solution.  Don't get me wrong; I'm all for
augmenting the optimization done by `restrict' by using data-flow
analysis, but I don't think it's by any means necessary to make it
useful.

Partly, I think that your intuition about the common case may be off.
Common usage of restrict in scientific code is with all pointer
parameters to a function restricted, so that things like array
operations and matrix operations work as with Fortran semantics (i.e.,
parameters don't alias).  My patch enables optization in these common
cases.  With the further optimization that const parameters cannot
alias restrict parameters, even more optimization will be enabled.

That's not to say that more work can't be done here.  Of course it
can.  But, the optimizations enabled by the patch are by no means
inconsequential, or useless.

    Richard> I suppose it is something, though, and gets the parsing
    Richard> in to the front end so that we can solve the problem for
    Richard> real later.

Frankly, I don't much appreciate the tone of this paragraph, or the
one before it.  (In general, I think that the sometime lack of
courtesy on this list is surprising, given the fact that we are all
like-minded inviduals working together towards a common goal.)  I
think with a little more care you could have expressed the point that
there is more to do in the future without demeaning the work done to
date.

The patch does deal with the parsing problem.  It also goes a long way
towards solving the problem "for real", partly by extending alias sets
in a useful way.  (As mentioned in the patch, this extension will also
be useful for additional type-based alias analysis.)  I intend to do
additional work to increase the optimization done by `restrict', and I
am sure that you and others will help.  I think it is better to submit
relatively small chunks one at a time, so that we can all agree on the
basic architectural decisions, than to wait until all possible
features are fleshed out and then submit one massive patch.

-- 
Mark Mitchell 			mark@markmitchell.com
Mark Mitchell Consulting	http://www.markmitchell.com