Silecne array bounds warnings in duplicated code

Silecne array bounds warnings in duplicated code

[Jan Hubicka]

Hi,
this patch address problem I run into with strenghtened cunroll pass.  I made
cunroll to use loop_max_iterations bounds into an account that makes us to
occasionally produce out of bounds loop accesses in loop like:

for (i=0;i<n;i++)
{
  <something>
  if (test)
    break
  a[i]=1;
}
Here the constantly sized array appears in loop with multiple exits and we then
in the last iteration produce out of bound array (since we need to duplicate 
<something> and tree-ssa-vrp warns.

I think this is more generic problem (though appearing rarely): as soon as we
specialize the code, we can no longer warn about out of bounds accesses when we
prove array ref to be constant.  We have no idea if this code path will execute
in practice.

Seems resonable?  I think similar problems can be constructed by inlining, too.
Regtested/bootstrapped x86_64-linux.

Honza

	* tree-cfg.c (gimple_duplicate_bb): Drop NO_WARNING on array refs.
Index: tree-cfg.c
===================================================================
*** tree-cfg.c	(revision 192360)
--- tree-cfg.c	(working copy)
*************** gimple_duplicate_bb (basic_block bb)
*** 5504,5509 ****
--- 5504,5519 ----
        if (lhs && TREE_CODE (lhs) != SSA_NAME)
  	{
  	  tree base = get_base_address (lhs);
+ 	  tree op = lhs;
+
+	  /* Silence the array bounds warning.  After specializing the code we
+	     no longer know if the particular code path can execute at runtime.  */
+ 	  while (handled_component_p (op))
+ 	    {
+ 	      if (TREE_CODE (op) == ARRAY_REF)
+ 		TREE_NO_WARNING (op) = 1;
+ 	      op =  TREE_OPERAND (op, 0);
+   	    }
  	  if (base
  	      && (TREE_CODE (base) == VAR_DECL
  		  || TREE_CODE (base) == RESULT_DECL)
*************** gimple_duplicate_bb (basic_block bb)
*** 5514,5519 ****
--- 5521,5539 ----
  		  || !DECL_HAS_VALUE_EXPR_P (base)))
  	    DECL_NONSHAREABLE (base) = 1;
  	}
+
+	/* Silence the array bounds warning.  After specializing the code we
+	   no longer know if the particular code path can execute at runtime.  */
+       if (gimple_code (stmt) == GIMPLE_ASSIGN)
+ 	{
+ 	  tree op = gimple_assign_rhs1 (stmt);
+ 	  while (handled_component_p (op))
+ 	    {
+ 	      if (TREE_CODE (op) == ARRAY_REF)
+ 		TREE_NO_WARNING (op) = 1;
+ 	      op =  TREE_OPERAND (op, 0);
+   	    }
+ 	}
  
        /* Create new names for all the definitions created by COPY and
  	 add replacement mappings for each new name.  */

Re: Silecne array bounds warnings in duplicated code

[Richard Biener]

On Thu, 11 Oct 2012, Jan Hubicka wrote:

> Hi,
> this patch address problem I run into with strenghtened cunroll pass.  I made
> cunroll to use loop_max_iterations bounds into an account that makes us to
> occasionally produce out of bounds loop accesses in loop like:
> 
> for (i=0;i<n;i++)
> {
>   <something>
>   if (test)
>     break
>   a[i]=1;
> }
> Here the constantly sized array appears in loop with multiple exits and we then
> in the last iteration produce out of bound array (since we need to duplicate 
> <something> and tree-ssa-vrp warns.
> 
> I think this is more generic problem (though appearing rarely): as soon as we
> specialize the code, we can no longer warn about out of bounds accesses when we
> prove array ref to be constant.  We have no idea if this code path will execute
> in practice.
> 
> Seems resonable?  I think similar problems can be constructed by inlining, too.
> Regtested/bootstrapped x86_64-linux.

No, I don't think this is reasonable.  There are other PRs for this
as well, btw.

The array-bounds warning in VRP needs to be conditional if the
path to it isn't always executed, too (thus a may-be warning).

Richard.

> Honza
> 
> 	* tree-cfg.c (gimple_duplicate_bb): Drop NO_WARNING on array refs.
> Index: tree-cfg.c
> ===================================================================
> *** tree-cfg.c	(revision 192360)
> --- tree-cfg.c	(working copy)
> *************** gimple_duplicate_bb (basic_block bb)
> *** 5504,5509 ****
> --- 5504,5519 ----
>         if (lhs && TREE_CODE (lhs) != SSA_NAME)
>   	{
>   	  tree base = get_base_address (lhs);
> + 	  tree op = lhs;
> +
> +	  /* Silence the array bounds warning.  After specializing the code we
> +	     no longer know if the particular code path can execute at runtime.  */
> + 	  while (handled_component_p (op))
> + 	    {
> + 	      if (TREE_CODE (op) == ARRAY_REF)
> + 		TREE_NO_WARNING (op) = 1;
> + 	      op =  TREE_OPERAND (op, 0);
> +   	    }
>   	  if (base
>   	      && (TREE_CODE (base) == VAR_DECL
>   		  || TREE_CODE (base) == RESULT_DECL)
> *************** gimple_duplicate_bb (basic_block bb)
> *** 5514,5519 ****
> --- 5521,5539 ----
>   		  || !DECL_HAS_VALUE_EXPR_P (base)))
>   	    DECL_NONSHAREABLE (base) = 1;
>   	}
> +
> +	/* Silence the array bounds warning.  After specializing the code we
> +	   no longer know if the particular code path can execute at runtime.  */
> +       if (gimple_code (stmt) == GIMPLE_ASSIGN)
> + 	{
> + 	  tree op = gimple_assign_rhs1 (stmt);
> + 	  while (handled_component_p (op))
> + 	    {
> + 	      if (TREE_CODE (op) == ARRAY_REF)
> + 		TREE_NO_WARNING (op) = 1;
> + 	      op =  TREE_OPERAND (op, 0);
> +   	    }
> + 	}
>   
>         /* Create new names for all the definitions created by COPY and
>   	 add replacement mappings for each new name.  */
> 
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend

Re: Silecne array bounds warnings in duplicated code

[Jan Hubicka]

> On Thu, 11 Oct 2012, Jan Hubicka wrote:
> 
> > Hi,
> > this patch address problem I run into with strenghtened cunroll pass.  I made
> > cunroll to use loop_max_iterations bounds into an account that makes us to
> > occasionally produce out of bounds loop accesses in loop like:
> > 
> > for (i=0;i<n;i++)
> > {
> >   <something>
> >   if (test)
> >     break
> >   a[i]=1;
> > }
> > Here the constantly sized array appears in loop with multiple exits and we then
> > in the last iteration produce out of bound array (since we need to duplicate 
> > <something> and tree-ssa-vrp warns.
> > 
> > I think this is more generic problem (though appearing rarely): as soon as we
> > specialize the code, we can no longer warn about out of bounds accesses when we
> > prove array ref to be constant.  We have no idea if this code path will execute
> > in practice.
> > 
> > Seems resonable?  I think similar problems can be constructed by inlining, too.
> > Regtested/bootstrapped x86_64-linux.
> 
> No, I don't think this is reasonable.  There are other PRs for this
> as well, btw.
> 
> The array-bounds warning in VRP needs to be conditional if the
> path to it isn't always executed, too (thus a may-be warning).

Well, this is, of course, in full generality a whole program analysis that we
do not want to solve in the compiler :)

OK, I am also not very happy about this patch, but I need something for the cunroll
change. I wonder what are the options:
 1) leave the warning and say that -O3 bootstrap need -Wno-error.
    We do used unitialized warnings during -O3 bootstrap too, but I do not like
    this variant, since used uninitialized can be silenced by extra initialization,
    while this warning can not. Also these warnings are very confusing and bogus.
 2) make complette unrolling to only silence the warnings in the last copy of the
    loop only when it knows it may contain out of bound accesses
 3) make loop-niter really collect basic blocks that must be unreachable in the
    last iteration and make cunroll to take this into account and insert
    unreachable builtin on beggining of those blocks.

Obviously 3) is most complette.  I am however not sure how to add it to niter
API.  I do not think we want to record the lists of basic block into loop bound
structure since they wil be hard to update.  But then we need to someone
extern max_niter API to optionally return it when needed.

You are more familiar with that code than me, any preferences?
Honza
> 
> Richard.

Re: Silecne array bounds warnings in duplicated code

[Richard Biener]

On Fri, 12 Oct 2012, Jan Hubicka wrote:

> > On Thu, 11 Oct 2012, Jan Hubicka wrote:
> > 
> > > Hi,
> > > this patch address problem I run into with strenghtened cunroll pass.  I made
> > > cunroll to use loop_max_iterations bounds into an account that makes us to
> > > occasionally produce out of bounds loop accesses in loop like:
> > > 
> > > for (i=0;i<n;i++)
> > > {
> > >   <something>
> > >   if (test)
> > >     break
> > >   a[i]=1;
> > > }
> > > Here the constantly sized array appears in loop with multiple exits and we then
> > > in the last iteration produce out of bound array (since we need to duplicate 
> > > <something> and tree-ssa-vrp warns.
> > > 
> > > I think this is more generic problem (though appearing rarely): as soon as we
> > > specialize the code, we can no longer warn about out of bounds accesses when we
> > > prove array ref to be constant.  We have no idea if this code path will execute
> > > in practice.
> > > 
> > > Seems resonable?  I think similar problems can be constructed by inlining, too.
> > > Regtested/bootstrapped x86_64-linux.
> > 
> > No, I don't think this is reasonable.  There are other PRs for this
> > as well, btw.
> > 
> > The array-bounds warning in VRP needs to be conditional if the
> > path to it isn't always executed, too (thus a may-be warning).
> 
> Well, this is, of course, in full generality a whole program analysis that we
> do not want to solve in the compiler :)
> 
> OK, I am also not very happy about this patch, but I need something for the cunroll
> change. I wonder what are the options:
>  1) leave the warning and say that -O3 bootstrap need -Wno-error.
>     We do used unitialized warnings during -O3 bootstrap too, but I do not like
>     this variant, since used uninitialized can be silenced by extra initialization,
>     while this warning can not. Also these warnings are very confusing and bogus.
>  2) make complette unrolling to only silence the warnings in the last copy of the
>     loop only when it knows it may contain out of bound accesses
>  3) make loop-niter really collect basic blocks that must be unreachable in the
>     last iteration and make cunroll to take this into account and insert
>     unreachable builtin on beggining of those blocks.
> 
> Obviously 3) is most complette.  I am however not sure how to add it to niter
> API.  I do not think we want to record the lists of basic block into loop bound
> structure since they wil be hard to update.  But then we need to someone
> extern max_niter API to optionally return it when needed.
> 
> You are more familiar with that code than me, any preferences?

My preference is to do what was requested in some bugreport,
split the array-bounds warning into a may and a must case
(obviously giving away the possibility a function is not executed).
For always executed stmts issue the 'must' case, for not always
executed stmts issue the 'may' case.  Disable the may case
for -O3 bootstrap.

The other preference is to attach to-be issued warnings to stmts
and issue them only if the stmt didn't turn out to be dead.

In general there is a conflict between warning late to expose
knowledge from optimization and not emit too many false positives.

That said, I don't worry about -O3 bootstrap warnings - simply
disable those warnings that turn out to be too noisy and have
false positives.  I thought we had -Wno-error=array-bounds
for example.

Richard.

Re: Silecne array bounds warnings in duplicated code

[Jan Hubicka]

> On Fri, 12 Oct 2012, Jan Hubicka wrote:
> 
> > > On Thu, 11 Oct 2012, Jan Hubicka wrote:
> > > 
> > > > Hi,
> > > > this patch address problem I run into with strenghtened cunroll pass.  I made
> > > > cunroll to use loop_max_iterations bounds into an account that makes us to
> > > > occasionally produce out of bounds loop accesses in loop like:
> > > > 
> > > > for (i=0;i<n;i++)
> > > > {
> > > >   <something>
> > > >   if (test)
> > > >     break
> > > >   a[i]=1;
> > > > }
> > > > Here the constantly sized array appears in loop with multiple exits and we then
> > > > in the last iteration produce out of bound array (since we need to duplicate 
> > > > <something> and tree-ssa-vrp warns.
> > > > 
> > > > I think this is more generic problem (though appearing rarely): as soon as we
> > > > specialize the code, we can no longer warn about out of bounds accesses when we
> > > > prove array ref to be constant.  We have no idea if this code path will execute
> > > > in practice.
> > > > 
> > > > Seems resonable?  I think similar problems can be constructed by inlining, too.
> > > > Regtested/bootstrapped x86_64-linux.
> > > 
> > > No, I don't think this is reasonable.  There are other PRs for this
> > > as well, btw.
> > > 
> > > The array-bounds warning in VRP needs to be conditional if the
> > > path to it isn't always executed, too (thus a may-be warning).
> > 
> > Well, this is, of course, in full generality a whole program analysis that we
> > do not want to solve in the compiler :)
> > 
> > OK, I am also not very happy about this patch, but I need something for the cunroll
> > change. I wonder what are the options:
> >  1) leave the warning and say that -O3 bootstrap need -Wno-error.
> >     We do used unitialized warnings during -O3 bootstrap too, but I do not like
> >     this variant, since used uninitialized can be silenced by extra initialization,
> >     while this warning can not. Also these warnings are very confusing and bogus.
> >  2) make complette unrolling to only silence the warnings in the last copy of the
> >     loop only when it knows it may contain out of bound accesses
> >  3) make loop-niter really collect basic blocks that must be unreachable in the
> >     last iteration and make cunroll to take this into account and insert
> >     unreachable builtin on beggining of those blocks.
> > 
> > Obviously 3) is most complette.  I am however not sure how to add it to niter
> > API.  I do not think we want to record the lists of basic block into loop bound
> > structure since they wil be hard to update.  But then we need to someone
> > extern max_niter API to optionally return it when needed.
> > 
> > You are more familiar with that code than me, any preferences?
> 
> My preference is to do what was requested in some bugreport,
> split the array-bounds warning into a may and a must case
> (obviously giving away the possibility a function is not executed).
> For always executed stmts issue the 'must' case, for not always
> executed stmts issue the 'may' case.  Disable the may case
> for -O3 bootstrap.
Hmm, I may look into that, but I will stil lmake us to output obviously
bogus may warnings ...
> 
> The other preference is to attach to-be issued warnings to stmts
> and issue them only if the stmt didn't turn out to be dead.

... in this case stmt may not turn out to be dead.  Loop infrasturcture is the
only who conclude that code is unreachable just because it will do out of bound
access. Ths is why I am considering 3) as only way to really kill those
statements instead of producing dead code in final output of the compiler.

We may in fact make VRP to wire in __builtin_unreachable in the cases it now
warns for as these won't be executed in valid program.  It will for sure
introduce some debugging challenges for the code that no longer segfaults but
does someting completely crazy ;))
> 
> In general there is a conflict between warning late to expose
> knowledge from optimization and not emit too many false positives.

Indeed, these kind of analysis are fishy when scheduled in normal
optimization queue. Static analyzers don't do thinks like code specialization
that triggers the false positives.

Honza
> 
> That said, I don't worry about -O3 bootstrap warnings - simply
> disable those warnings that turn out to be too noisy and have
> false positives.  I thought we had -Wno-error=array-bounds
> for example.
> 
> Richard.