potential simple loop optimization assistance strategy?

potential simple loop optimization assistance strategy?

[Paul Schlie]

As in general it seems that as the compiler knows what it needs to know to
enable ideal loop optimization, why not simply have it assert: if it knew x,
then it could do y?  For example, if given something like:

  for (i = x; i < y; i++){ ... }

Where it may not be known statically if x < y, or what (y - x) % N may be;
therefore possibly difficult to ideally optimize.  Where then instead of
assuming something that may not be factual by default, it could generate a
warning indicating that the loop may be further optimized if it knew that
x < y, and/or (y - x) % N == 0.  Where then the programmer could then choose
to warrant it by preconditioning the loop:

  assert((x < y) && ((y - x) % 4)); // which could throw an exception.

  for ((i = x; i < y; i++){ ... }

Where although it would require run-time code, it's overhead should be
insignificant if the benefit of the optimization were truly significant;
thereby enabling the programmer to help the compiler help himself, without
the introducing potentially arbitrary behaviors, by explicitly trapping them
instead.

Where if the programmer didn't add an assertion, or explicitly enable a
potentially unsafe optimization, then the compiler should not presume
anything other than what it truly factually knows, which may include
optimizations based on whether the target traps or wraps overflow, etc.

(it may even be reasonable for the compiler to optionally insert run-time
assertions automatically to enable the deterministic trapping of conditions
which may be inconsistent with the optimizations assumptions?)

Re: potential simple loop optimization assistance strategy?

[Gabriel Dos Reis]

Paul Schlie <schlie@comcast.net> writes:

| As in general it seems that as the compiler knows what it needs to know to
| enable ideal loop optimization, why not simply have it assert: if it knew x,
| then it could do y?  For example, if given something like:
| 
|   for (i = x; i < y; i++){ ... }
| 
| Where it may not be known statically if x < y, or what (y - x) % N may be;
| therefore possibly difficult to ideally optimize.  Where then instead of
| assuming something that may not be factual by default, it could generate a
| warning indicating that the loop may be further optimized if it knew that
| x < y, and/or (y - x) % N == 0.  Where then the programmer could then choose
| to warrant it by preconditioning the loop:
| 
|   assert((x < y) && ((y - x) % 4)); // which could throw an exception.
| 
|   for ((i = x; i < y; i++){ ... }
| 
| Where although it would require run-time code, it's overhead should be
| insignificant if the benefit of the optimization were truly significant;

I would not predicate the transformation on that assumption
(negligible cost of assertion).  That could happen in an inner tight
loop. 

What we need is a balance that does not require too much of work from
the compiler -- because otherwise, it won't happen.

-- Gaby

Re: potential simple loop optimization assistance strategy?

[Paul Schlie]

> From: Gabriel Dos Reis <gdr@integrable-solutions.net>
> | Paul Schlie <schlie@comcast.net> writes:
> | As in general it seems that as the compiler knows what it needs to know to
> | enable ideal loop optimization, why not simply have it assert: if it knew x,
> | then it could do y?  For example, if given something like:
> | 
> |   for (i = x; i < y; i++){ ... }
> | 
> | Where it may not be known statically if x < y, or what (y - x) % N may be;
> | therefore possibly difficult to ideally optimize.  Where then instead of
> | assuming something that may not be factual by default, it could generate a
> | warning indicating that the loop may be further optimized if it knew that
> | x < y, and/or (y - x) % N == 0.  Where then the programmer could then choose
> | to warrant it by preconditioning the loop:
> | 
> |   assert((x < y) && ((y - x) % 4)); // which could throw an exception.
> | 
> |   for ((i = x; i < y; i++){ ... }
> | 
> | Where although it would require run-time code, it's overhead should be
> | insignificant if the benefit of the optimization were truly significant;
> 
> I would not predicate the transformation on that assumption
> (negligible cost of assertion).  That could happen in an inner tight
> loop. 
> 
> What we need is a balance that does not require too much of work from
> the compiler -- because otherwise, it won't happen.

Understood, but can't help but wonder how many nested loops realalisticly
have nested data dependancies; but none the less, I guess all it takes is
one important one to justify worrying about it. And agree it would be nice
if static assertions could be made in some reasonable way embedded in the
code.

Re: potential simple loop optimization assistance strategy?

[Devang Patel]

On Jul 1, 2005, at 8:51 AM, Paul Schlie wrote:

> As in general it seems that as the compiler knows what it needs to  
> know to
> enable ideal loop optimization, why not simply have it assert: if  
> it knew x,
> then it could do y?  For example, if given something like:
>
>   for (i = x; i < y; i++){ ... }
>
> Where it may not be known statically if x < y, or what (y - x) % N  
> may be;
> therefore possibly difficult to ideally optimize.  Where then  
> instead of
> assuming something that may not be factual by default, it could  
> generate a
> warning indicating that the loop may be further optimized if it  
> knew that
> x < y, and/or (y - x) % N == 0.  Where then the programmer could  
> then choose
> to warrant it by preconditioning the loop:
>
>   assert((x < y) && ((y - x) % 4)); // which could throw an exception.
>
>   for ((i = x; i < y; i++){ ... }
>
> Where although it would require run-time code, it's overhead should be
> insignificant if the benefit of the optimization were truly  
> significant;
> thereby enabling the programmer to help the compiler help himself,  
> without
> the introducing potentially arbitrary behaviors, by explicitly  
> trapping them
> instead.
>
> Where if the programmer didn't add an assertion, or explicitly  
> enable a
> potentially unsafe optimization, then the compiler should not presume
> anything other than what it truly factually knows, which may include
> optimizations based on whether the target traps or wraps overflow,  
> etc.
>
> (it may even be reasonable for the compiler to optionally insert  
> run-time
> assertions automatically to enable the deterministic trapping of  
> conditions
> which may be inconsistent with the optimizations assumptions?)
>

Various compilers support #pragma to inform compiler about approx.  
number
of loop iterations.


-
Devang

Re: potential simple loop optimization assistance strategy?

[Giovanni Bajo]

Paul Schlie <schlie@comcast.net> wrote:

> Where then the programmer could then choose
> to warrant it by preconditioning the loop:
>
>   assert((x < y) && ((y - x) % 4)); // which could throw an exception.
>
>   for ((i = x; i < y; i++){ ... }

There has been some opposition in the past about allowing conditions in
asserts to be used as hints to the optimizers. In fact, I would like to know
if there is a current statement of purpose about this. That is, would there
be strong oppositions to patches doing this?
-- 
Giovanni Bajo

Re: potential simple loop optimization assistance strategy?

[Diego Novillo]

On Fri, Jul 01, 2005 at 08:16:19PM +0200, Giovanni Bajo wrote:
> Paul Schlie <schlie@comcast.net> wrote:
> 
> > Where then the programmer could then choose
> > to warrant it by preconditioning the loop:
> >
> >   assert((x < y) && ((y - x) % 4)); // which could throw an exception.
> >
> >   for ((i = x; i < y; i++){ ... }
> 
> There has been some opposition in the past about allowing conditions in
> asserts to be used as hints to the optimizers. In fact, I would like to know
> if there is a current statement of purpose about this. That is, would there
> be strong oppositions to patches doing this?
>
VRP naturally takes advantage of assert (though not in some
occassions involving unsigned types).  Try:

#include <assert.h>

foo (int i)
{
  assert (i != 0);
  if (i == 0)
    return 3;

  return 2;
}


Diego.

Re: potential simple loop optimization assistance strategy?

[Giovanni Bajo]

Diego Novillo <dnovillo@redhat.com> wrote:

>> There has been some opposition in the past about allowing conditions in
>> asserts to be used as hints to the optimizers. In fact, I would like to
>> know if there is a current statement of purpose about this. That is,
would
>> there be strong oppositions to patches doing this?
>>
> VRP naturally takes advantage of assert (though not in some
> occassions involving unsigned types).  Try:
>
> #include <assert.h>
>
> foo (int i)
> {
>   assert (i != 0);
>   if (i == 0)
>     return 3;
>
>   return 2;
> }

Agreed, but my point is whether we can do that when NDEBUG is defined.
-- 
Giovanni Bajo

Re: potential simple loop optimization assistance strategy?

[Paul Schlie]

> From: Giovanni Bajo <rasky@develer.com>
>> Diego Novillo <dnovillo@redhat.com> wrote:
>>> There has been some opposition in the past about allowing conditions in
>>> asserts to be used as hints to the optimizers. In fact, I would like to
>>> know if there is a current statement of purpose about this. That is,
> would
>>> there be strong oppositions to patches doing this?
>>> 
>> VRP naturally takes advantage of assert (though not in some
>> occassions involving unsigned types).  Try:
>> 
>> #include <assert.h>
>> 
>> foo (int i)
>> {
>>   assert (i != 0);
>>   if (i == 0)
>>     return 3;
>> 
>>   return 2;
>> }
> 
> Agreed, but my point is whether we can do that when NDEBUG is defined.

Might be nice to have both flavors, or take a parameter which indicates
if it's meant to be a static assertion, or throw a named runtime exception;
where the static assertion inhibit code generation simply inhibits code
generation somehow? as their requirement is not mutually exclusive.

Re: potential simple loop optimization assistance strategy?

[Giovanni Bajo]

Tom Tromey <tromey@redhat.com> wrote:

> Giovanni> Agreed, but my point is whether we can do that when NDEBUG
> Giovanni> is defined.
>
> I thought when NDEBUG is defined, assert expands to something like
> '(void) 0' -- the original expression is no longer around.


Yes, but the condition is still morally true in the code. NDEBUG is meant to
speed up the generated code, and it's actually a pity that instead it
*disables* some optimizations because we don't see the condition anymore. My
suggestion is that assert with NDEBUG might expand to something like:

if (condition)
   unreachable();

where unreachable is a function call marked with a special attribute saying
that execution can never get there. This way the run-time check is removed from
the code, but the range information can still be propagated and used.

Notice that such an attribute would be needed in the first place for
gcc_unreachable() in our own sources. Right now we expand it to gcc_assert(0),
but we could do much better with a special attribute.

Giovanni Bajo

Re: potential simple loop optimization assistance strategy?

[Michael Veksler]

Giovanni Bajo wrote on 02/07/2005 12:18:00:
>
> Yes, but the condition is still morally true in the code. NDEBUG is meant
to
> speed up the generated code, and it's actually a pity that instead it
> *disables* some optimizations because we don't see the condition anymore.
My
> suggestion is that assert with NDEBUG might expand to something like:
>
> if (condition)
>    unreachable();
>
> where unreachable is a function call marked with a special attribute
saying
> that execution can never get there. This way the run-time check is
> removed from
> the code, but the range information can still be propagated and used.
>
> Notice that such an attribute would be needed in the first place for
> gcc_unreachable() in our own sources. Right now we expand it to
gcc_assert(0),
> but we could do much better with a special attribute.

I always thought that when NDEBUG is set, then assert(x) should
have no side effects. So if "condition" contains any side effect,
or potential side effect (e.g. through function call), then the
compiler should not generate the code for "condition".

  Michael

Re: potential simple loop optimization assistance strategy?

[Giovanni Bajo]

Michael Veksler <VEKSLER@il.ibm.com> wrote:

> have no side effects. So if "condition" contains any side effect,
> or potential side effect (e.g. through function call), then the
> compiler should not generate the code for "condition".


Right. Thus we can find a way to avoid generating e.g. function calls or
similar things, and get information from the most basic conditions.

Giovanni Bajo