[Bug tree-optimization/85315] missed range optimisation opportunity for derefences where index must be 0 or otherwise constrained

[Bug tree-optimization/85315] missed range optimisation opportunity for derefences where index must be 0 or otherwise constrained

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85315

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #10 from Andrew Macleod <amacleod at redhat dot com> ---
OK, so whats the deal here. I can't really follow what the final request, or
action is.

Is there a conclusion on what needs to be done? if anything?

[Bug tree-optimization/85315] missed range optimisation opportunity for derefences where index must be 0 or otherwise constrained

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85315

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #10)
> OK, so whats the deal here. I can't really follow what the final request, or
> action is.
> 
> Is there a conclusion on what needs to be done? if anything?

See the original description - the request was to derive ranges for
the offset operand in pointer arithmetic based on the size of the
object offsetted.  In the simple example a plain 'int' which is
(in GIMPLE) offsetted by 4 * (a + b) where we should derive that
a + b is zero.

[Bug tree-optimization/85315] missed range optimisation opportunity for derefences where index must be 0 or otherwise constrained

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85315

--- Comment #12 from Andrew Macleod <amacleod at redhat dot com> ---
Maybe I'm a little dense.

if we are presuming that  
  &x + (a + b) 
implies a + b == 0, then we also should assume that

  &x + a  implies a == 0

and if we can make those assumptions, then
&x + 1 is garbage because we can assume 1 == 0.

And if a and b are both unsigned, then I guess we can also assume a == b ==
MAX_UINT / 2 ?


Now, if we decided to actually do this...  I see IL:

<bb 2> :
  x.0_1 = x;
  y = x.0_1;
  a.1_2 = a;
  b.2_3 = b;
  _4 = a.1_2 + b.2_3;
  _5 = (long unsigned int) _4;
  _6 = _5 * 4;
  _7 = &y + _6;

The clear implications is that _6 == 0 in this expression?

If we implemented that in the operator_pointer_plus::op1_range routine, and
then were to back substitute, we'd get
(_6)[0,0] = _5 * 4   -> _5 = [0,0]
(_5)[0,0] = (long unsigned int) _4;  -> _4 == [0,0]
(_4)[0,0] = a.1_2 + b.2_3   which gives us nothing additional...  Other than a
potential relationship to track I suppose  a.1_2 == -B.2_3 for signed, but it
would record that _4 is [0,0] when we calculate an outgoing range.

but regardless, its seems that another straightforward place to do this would
be in statement folding?  Isn't the basic assumption:

_7 = &y + _6;
implies _6 is always 0, which would enable us to fold this to
_7 = &y
then _6 is unused and the other statements would ultimately just go away.

So why not make folding simply throw away the "+ _6" part because it is now
being forced to be 0?  We can't really assume that it is [0,0], but then not
use that information to optimize?

[Bug tree-optimization/85315] missed range optimisation opportunity for derefences where index must be 0 or otherwise constrained

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85315

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #12)
> Maybe I'm a little dense.
> 
> if we are presuming that  
>   &x + (a + b) 
> implies a + b == 0, then we also should assume that

&x + (a + b) for scalar x doesn't imply a + b == 0, it implies a + b <= 1.
Only when it is dereferenced, i.e. (&x)[a + b] is accessed a + b has to be 0.

[Bug tree-optimization/85315] missed range optimisation opportunity for derefences where index must be 0 or otherwise constrained

[msebor at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85315

--- Comment #14 from Martin Sebor <msebor at gcc dot gnu.org> ---
Andrew, we discussed the same idea for built-in functions at Couldron.  For
instance, in:

  void f (const char *s, int n)
  {
    char a[8];
    memcpy (a, s, n);     // n must be in [0, 8]
    if (n < 0 || n > 8)   // fold to false
      abort ();
  }

[Bug tree-optimization/85315] missed range optimisation opportunity for derefences where index must be 0 or otherwise constrained

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85315

--- Comment #15 from rguenther at suse dot de <rguenther at suse dot de> ---
On November 18, 2020 3:55:44 PM GMT+01:00, amacleod at redhat dot com
<gcc-bugzilla@gcc.gnu.org> wrote:
>https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85315
>
>--- Comment #12 from Andrew Macleod <amacleod at redhat dot com> ---
>Maybe I'm a little dense.
>
>if we are presuming that  
>  &x + (a + b) 
>implies a + b == 0, then we also should assume that
>
>  &x + a  implies a == 0
>
>and if we can make those assumptions, then
>&x + 1 is garbage because we can assume 1 == 0.
>
>And if a and b are both unsigned, then I guess we can also assume a ==
>b ==
>MAX_UINT / 2 ?
>
>
>Now, if we decided to actually do this...  I see IL:
>
><bb 2> :
>  x.0_1 = x;
>  y = x.0_1;
>  a.1_2 = a;
>  b.2_3 = b;
>  _4 = a.1_2 + b.2_3;
>  _5 = (long unsigned int) _4;
>  _6 = _5 * 4;
>  _7 = &y + _6;
>
>The clear implications is that _6 == 0 in this expression?
>
>If we implemented that in the operator_pointer_plus::op1_range routine,
>and
>then were to back substitute, we'd get
>(_6)[0,0] = _5 * 4   -> _5 = [0,0]
>(_5)[0,0] = (long unsigned int) _4;  -> _4 == [0,0]
>(_4)[0,0] = a.1_2 + b.2_3   which gives us nothing additional...  Other
>than a
>potential relationship to track I suppose  a.1_2 == -B.2_3 for signed,
>but it
>would record that _4 is [0,0] when we calculate an outgoing range.
>
>but regardless, its seems that another straightforward place to do this
>would
>be in statement folding?  Isn't the basic assumption:
>
>_7 = &y + _6;
>implies _6 is always 0, which would enable us to fold this to
>_7 = &y
>then _6 is unused and the other statements would ultimately just go
>away.
>
>So why not make folding simply throw away the "+ _6" part because it is
>now
>being forced to be 0?  We can't really assume that it is [0,0], but
>then not
>use that information to optimize?

Well, clearly the zero case is degenerate but it extends to sth like int a[2] ;
and &a + n. I guess you're already handling ARRAY_REF indices.

[Bug tree-optimization/85315] missed range optimisation opportunity for derefences where index must be 0 or otherwise constrained

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85315

--- Comment #16 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Jakub Jelinek from comment #13)
> (In reply to Andrew Macleod from comment #12)
> > Maybe I'm a little dense.
> > 
> > if we are presuming that  
> >   &x + (a + b) 
> > implies a + b == 0, then we also should assume that
> 
> &x + (a + b) for scalar x doesn't imply a + b == 0, it implies a + b <= 1.
> Only when it is dereferenced, i.e. (&x)[a + b] is accessed a + b has to be 0.

OK. certain things about this still confuse me, but thats OK for now. we'll
come back to them.

There seems to be 2 things at play here:
1) lhs = ptr + X
    has certain implications on X, it ptr is &scalar then X = [0, 1] * sizeof
(&scalar)?  
2) if lhs is later de-referenced, then X is known to have been [0,0]?

We're ignoring the nonscalar cases of ptr for now, but Im guessing they are
similar just the values for X are determined differently. 

1) a) could be handled with something like a previously mentioned
range_after_stmt() API for operands which are affected by statements. 
   b)  It can also be impacted by op2_range() during a wind back, but would
likely require some tweaking of gimple_range_calc_op2() to determine that 'ptr'
satisfied the criteria of this scalar condition.   the a) solution would
eliminate the necessity of this.

2) This one is a bit trickier.  We cant use the non-null property since &x +
blah  will already make it non-null... so you are looking for an actual
dereference of itself or an equivalence?   I can probably tweak the non-null
property manager to indicate whether the non-null property also contains a
dereference.. but I guess you would need to know that ALL paths contain a
dereference.

We'd probably get most of what we're looking for if we simply check for a
dereference of LHS in the same block?  and then assert that X is 0.

Is that he basic gist? 
Regardless, I'll come back to this eventually and get someone to clarify all
the intricacies for me, IM just trying to understand the general requirements.