This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: egcs/gcc patch to speed up compiles of some Fortran code


>  In message <199805231618.MAA27338@melange.gnu.org>you write:
>  > Sat May 23 08:41:29 1998  Craig Burley  <burley@gnu.org>
>  > 
>  > 	* expr.c (safe_from_p): Avoid combinatorial explosion
>  > 	over duplicate SAVE_EXPRs by ensuring we never recurse
>  > 	on one that has already been visited.
>I'd prefer we go ahead and handling resizing the array or using a
>linked list.  Arbitrary limits are bad.  Yes there are lots of them
>in the compiler, but why introduce more when it isn't necessary.

Because it doesn't matter in this case.  There *is* no arbitrary
limit here, in the sense meant by most people (e.g. the GNU coding
guidelines).

The safe_from_p returns a boolean answer to the following question:

  Can you prove that evaluating expression EXP cannot possibly reference
  anything in X?

(Or similar...the "can you prove" is the essential element.)

I base this on the commentary at the beginning of the routine *plus*
the actual code, which seems to clearly avoid some "difficult" kinds
of analysis, erring on the side of saying "no, I cannot prove that"
even when it might be able to.  (Perhaps the commentary should be
adjusted accordingly.)

Without my patch, the question is answered at any expense, including
a huge, unnecessary amount of run time, though in some cases the
answer is "no, I cannot prove that" even though, strictly speaking,
it could.

With my patch, the question is answered at a much lower expense in
the cases we know take an unnecessary amount of run time, by slightly
increasing the problem space for which "no, I cannot prove that" is
returned even though, strictly speaking, it could prove that.

To do this, my patch causes safe_from_p to use a limited amount
of core to track stuff.

If it exceeds that limit, instead of continuing to use a possibly
ever-increasing amount of core and CPU cycles, it simply returns
the following:

  No, I cannot prove that.

In other words, it is my belief that there would be *no* bug if
we replaced all of safe_from_p with:

  return 0;

(Of course, generated code would get slower, which is why we don't
do this.  :)

That's why I say the limited-size array does not constitute an
arbitrary limit -- because there is no user visibility to this
limit.

The only possible way somebody might see this limit is that an
incredibly complicated expression, which, before my patch,
probably would have taken bazillions of cycles to evaluate in
safe_from_p(), is now implemented by, e.g., the compiler creating
an unnecessary temporary variable, and assigning via that temp
instead of directly.  But they'd only see that by analyzing the
generated code; I find it quite unlikely that any of the current
front ends would expose this deficiency in the form of a measurable
drop in the performance of any real code (though, when array-valued
expressions are involved, e.g. Fortran 90, which could happen someday,
that might change).

If anyone knows of any place in gcc where it is required that
safe_from_p returns an absolutely correct answer, then there are
three things we must do:

  1.  Fix my patch to either have no arbitrary limit, or to simply
      abort() if it encounters it.

  2.  Fix the documentation of safe_from_p(), which, IMO, currently
      is consistent with my interpretation above, but which should
      be clarified in any case.

  3.  Fix safe_from_p() itself, which currently does *not* always
      return a correct answer to the either/or form of the question,
      but AFAICT does return a correct answer to the form I posed,
      namely, "can you prove that...".  Note that I don't think this
      is actually possible, though depending on the actual need, it
      might be.  (If the actual need is to have it return 1 if it
      can be *statically* proven that EXP does not reference X, it
      might be possible; it is, IMO, impossible to return 1 *only* if
      EXP references X, 0 otherwise.)

Alternatively, we could fix anyplace in gcc that assumes safe_from_p
will make a perfect determination every time.  I think that's a much
more feasible solution than doing the above.

I doubt any such place exists currently in gcc.

In summary: if the "arbitrary limit" in my patch is ever encountered,
it won't make a bit of difference in terms of whether correct code,
or even high-performing, code gets generated.  If we find out it does,
I'm 99.9% certain the root cause of the problem will *not* be the
arbitrary limit; and that simply removing the limit will not cure
the problem.

        tq vm, (burley)

P.S. I *think* what this means is that, essentially, my original
patch has no agreed-upon problems with it.  The one exception might
be that I should submit a patch to improve the commentary at the
head of safe_from_p.  Here goes, though it isn't in patch form:

/* Subroutine of expand_expr: return nonzero iff it can be proved, using
   whatever knowledge base this routine wishes to use, that there is no
   way that EXP can reference X, which is being modified.  It is always
   correct for this routine to return zero; returning nonzero is correct
   only when EXP cannot reference X.  TOP_P is nonzero if this
   call is going to be used to determine whether we need a temporary
   for EXP, as opposed to a recursive call to this function.  */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]