[RFA] Some fixes to ipa-pure-const local analysis

[RFA] Some fixes to ipa-pure-const local analysis

[Jan Hubicka]

Hi,
while looking at ipa-pure-const analyzis rewrite to use SSA dataflow,
I noticed that there are several bits that seems wrong (in conservative way)
to me.  Those are at least wrong relative to old RTL based
implementation.

1) checking of "used" attribute on local variables seems wrong.  In no other
place of compiler we worry about it.  We worry about it only for static vars andfunctions.
Official documentation seems also bit off here:

This attribute, attached to a function, means that code must be emitted
for the function even if it appears that the function is not referenced.
This is useful, for example, when the function is referenced only in
inline assembly.

probably adding "to a function or static variable" is good wording?

2) Checking that initializer of local static variable is_gimple_min_invariant seems
a bit confused, since initializers are not gimplified.  I guess the check was
meant to verify that there is no static constructor emit for it.  I think
TYPE_NEEDS_CONSTRUCTING is proper check here.

3) chec_rhs_var/check_lhs_var is looking if statement can trap.  This is not
sufficient because we should check stmt_count_trap_p instead. Still it seems
wrong.  There is no code in compiler that would make difference in between CONST
and PURE this way.  Only sane reason for this check I can think of is to avoid
DCE from eliminating the call causing program to not trap.  This would be handled
by setting local->looping flag instead, but still since DCE itself is happy to
eliminate stmt_could_trap_p statements, I think this is all unnecesary.

4) look_for_address_of is refusing ADDR_EXPR of VAR_DECL in CONST functions.  I
don't think why VAR_DECL would be worse than PARM_DECL in this respect and
obviously function returning address of static variable is const.  Only reason
here I can think of is the fact that address of local variable might change
depending on call context, but if return value of CONST function contained
address of local variable in her own local stack frame, we would have undefined
behaviour anyway.  If the function was returning address of variable in the
origin function (ie we was looking at nested function), we would have explicit
static chain argument anyway, so the function would be optimized correctly.

I've bootstrapped/regtested x86_64-linux with this patch, OK?

	* ipa-pure-const.c (check_decl): Do not handle used attribute
	on local objects specially; readonly reads are safe.
	(look_for_address_of): Remove.
	(check_rhs_var, check_lhs_var): Remove tree_could_trap check.
Index: ipa-pure-const.c
===================================================================
--- ipa-pure-const.c	(revision 140464)
+++ ipa-pure-const.c	(working copy)
@@ -141,15 +141,6 @@ static inline void 
 check_decl (funct_state local, 
 	    tree t, bool checking_write)
 {
-  /* If the variable has the "used" attribute, treat it as if it had a
-     been touched by the devil.  */
-  if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
-    {
-      local->pure_const_state = IPA_NEITHER;
-      local->looping = false;
-      return;
-    }
-
   /* Do not want to do anything with volatile except mark any
      function that uses one to be not const or pure.  */
   if (TREE_THIS_VOLATILE (t)) 
@@ -163,6 +154,15 @@ check_decl (funct_state local, 
   if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
     return;
 
+  /* If the variable has the "used" attribute, treat it as if it had a
+     been touched by the devil.  */
+  if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
+    {
+      local->pure_const_state = IPA_NEITHER;
+      local->looping = false;
+      return;
+    }
+
   /* Since we have dealt with the locals and params cases above, if we
      are CHECKING_WRITE, this cannot be a pure or constant
      function.  */
@@ -175,14 +175,8 @@ check_decl (funct_state local, 
 
   if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
     {
-      /* If the front end set the variable to be READONLY and
-	 constant, we can allow this variable in pure or const
-	 functions but the scope is too large for our analysis to set
-	 these bits ourselves.  */
-      
-      if (TREE_READONLY (t)
-	  && DECL_INITIAL (t)
-	  && is_gimple_min_invariant (DECL_INITIAL (t)))
+      /* Readonly reads are safe.  */
+      if (TREE_READONLY (t) && !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t)))
 	; /* Read of a constant, do not change the function state.  */
       else 
 	{
@@ -265,26 +259,6 @@ check_tree (funct_state local, tree t, b
     check_operand (local, t, checking_write);
 }
 
-/* Scan tree T to see if there are any addresses taken in within T.  */
-
-static void 
-look_for_address_of (funct_state local, tree t)
-{
-  if (TREE_CODE (t) == ADDR_EXPR)
-    {
-      tree x = get_base_var (t);
-      if (TREE_CODE (x) == VAR_DECL) 
-	{
-	  check_decl (local, x, false);
-	  
-	  /* Taking the address of something appears to be reasonable
-	     in PURE code.  Not allowed in const.  */
-	  if (local->pure_const_state == IPA_CONST)
-	    local->pure_const_state = IPA_PURE;
-	}
-    }
-}
-
 /* Check to see if T is a read or address of operation on a var we are
    interested in analyzing.  LOCAL is passed in to get access to its
    bit vectors.  */
@@ -292,13 +266,6 @@ look_for_address_of (funct_state local, 
 static void
 check_rhs_var (funct_state local, tree t)
 {
-  look_for_address_of (local, t);
-
-  /* Memcmp and strlen can both trap and they are declared pure.  */
-  if (tree_could_trap_p (t)
-      && local->pure_const_state == IPA_CONST)
-    local->pure_const_state = IPA_PURE;
-
   check_tree(local, t, false);
 }
 
@@ -308,12 +275,6 @@ check_rhs_var (funct_state local, tree t
 static void
 check_lhs_var (funct_state local, tree t)
 {
-  /* Memcmp and strlen can both trap and they are declared pure.
-     Which seems to imply that we can apply the same rule here.  */
-  if (tree_could_trap_p (t)
-      && local->pure_const_state == IPA_CONST)
-    local->pure_const_state = IPA_PURE;
-    
   check_tree(local, t, true);
 }
 

Re: [RFA] Some fixes to ipa-pure-const local analysis

[Kenneth Zadeck]

Jan Hubicka wrote:
> Hi,
> while looking at ipa-pure-const analyzis rewrite to use SSA dataflow,
> I noticed that there are several bits that seems wrong (in conservative way)
> to me.  Those are at least wrong relative to old RTL based
> implementation.
>
> 1) checking of "used" attribute on local variables seems wrong.  In no other
> place of compiler we worry about it.  We worry about it only for static vars andfunctions.
> Official documentation seems also bit off here:
>
> This attribute, attached to a function, means that code must be emitted
> for the function even if it appears that the function is not referenced.
> This is useful, for example, when the function is referenced only in
> inline assembly.
>
> probably adding "to a function or static variable" is good wording?
>
> 2) Checking that initializer of local static variable is_gimple_min_invariant seems
> a bit confused, since initializers are not gimplified.  I guess the check was
> meant to verify that there is no static constructor emit for it.  I think
> TYPE_NEEDS_CONSTRUCTING is proper check here.
>
>   
When danny wrote this part, this was the best guess he could make as to
how to check this.  if the way you are advocating is more correct, then
change it.


> 3) chec_rhs_var/check_lhs_var is looking if statement can trap.  This is not
> sufficient because we should check stmt_count_trap_p instead. Still it seems
> wrong.  There is no code in compiler that would make difference in between CONST
> and PURE this way.  Only sane reason for this check I can think of is to avoid
> DCE from eliminating the call causing program to not trap.  This would be handled
> by setting local->looping flag instead, but still since DCE itself is happy to
> eliminate stmt_could_trap_p statements, I think this is all unnecesary.
>
>   
rtl dce will not delete insns that can trap.   if the tree/gimple dce
can, then there may be a problem.  I would assume that the trap testing
is not great since c code generally does not trap.
However given that, if we are looking in the wrong place to determine if
it can trap, then that should be fixed.

> 4) look_for_address_of is refusing ADDR_EXPR of VAR_DECL in CONST functions.  I
> don't think why VAR_DECL would be worse than PARM_DECL in this respect and
> obviously function returning address of static variable is const.  Only reason
> here I can think of is the fact that address of local variable might change
> depending on call context, but if return value of CONST function contained
> address of local variable in her own local stack frame, we would have undefined
> behaviour anyway.  If the function was returning address of variable in the
> origin function (ie we was looking at nested function), we would have explicit
> static chain argument anyway, so the function would be optimized correctly.
>
>   
Const functions cannot look at anything except parameters and
constants.   The
code in look_for_address_of was there to make sure that it did not
fabricate an address that it later read from.  The idea here is that
const functions can be commoned, and pure functions cannot. 


> I've bootstrapped/regtested x86_64-linux with this patch, OK?
>
> 	* ipa-pure-const.c (check_decl): Do not handle used attribute
> 	on local objects specially; readonly reads are safe.
> 	(look_for_address_of): Remove.
> 	(check_rhs_var, check_lhs_var): Remove tree_could_trap check.
> Index: ipa-pure-const.c
> ===================================================================
> --- ipa-pure-const.c	(revision 140464)
> +++ ipa-pure-const.c	(working copy)
> @@ -141,15 +141,6 @@ static inline void 
>  check_decl (funct_state local, 
>  	    tree t, bool checking_write)
>  {
> -  /* If the variable has the "used" attribute, treat it as if it had a
> -     been touched by the devil.  */
> -  if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
> -    {
> -      local->pure_const_state = IPA_NEITHER;
> -      local->looping = false;
> -      return;
> -    }
> -
>    /* Do not want to do anything with volatile except mark any
>       function that uses one to be not const or pure.  */
>    if (TREE_THIS_VOLATILE (t)) 
> @@ -163,6 +154,15 @@ check_decl (funct_state local, 
>    if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
>      return;
>  
> +  /* If the variable has the "used" attribute, treat it as if it had a
> +     been touched by the devil.  */
> +  if (lookup_attribute ("used", DECL_ATTRIBUTES (t)))
> +    {
> +      local->pure_const_state = IPA_NEITHER;
> +      local->looping = false;
> +      return;
> +    }
> +
>    /* Since we have dealt with the locals and params cases above, if we
>       are CHECKING_WRITE, this cannot be a pure or constant
>       function.  */
> @@ -175,14 +175,8 @@ check_decl (funct_state local, 
>  
>    if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
>      {
> -      /* If the front end set the variable to be READONLY and
> -	 constant, we can allow this variable in pure or const
> -	 functions but the scope is too large for our analysis to set
> -	 these bits ourselves.  */
> -      
> -      if (TREE_READONLY (t)
> -	  && DECL_INITIAL (t)
> -	  && is_gimple_min_invariant (DECL_INITIAL (t)))
> +      /* Readonly reads are safe.  */
> +      if (TREE_READONLY (t) && !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t)))
>  	; /* Read of a constant, do not change the function state.  */
>        else 
>  	{
> @@ -265,26 +259,6 @@ check_tree (funct_state local, tree t, b
>      check_operand (local, t, checking_write);
>  }
>  
> -/* Scan tree T to see if there are any addresses taken in within T.  */
> -
> -static void 
> -look_for_address_of (funct_state local, tree t)
> -{
> -  if (TREE_CODE (t) == ADDR_EXPR)
> -    {
> -      tree x = get_base_var (t);
> -      if (TREE_CODE (x) == VAR_DECL) 
> -	{
> -	  check_decl (local, x, false);
> -	  
> -	  /* Taking the address of something appears to be reasonable
> -	     in PURE code.  Not allowed in const.  */
> -	  if (local->pure_const_state == IPA_CONST)
> -	    local->pure_const_state = IPA_PURE;
> -	}
> -    }
> -}
> -
>  /* Check to see if T is a read or address of operation on a var we are
>     interested in analyzing.  LOCAL is passed in to get access to its
>     bit vectors.  */
> @@ -292,13 +266,6 @@ look_for_address_of (funct_state local, 
>  static void
>  check_rhs_var (funct_state local, tree t)
>  {
> -  look_for_address_of (local, t);
> -
> -  /* Memcmp and strlen can both trap and they are declared pure.  */
> -  if (tree_could_trap_p (t)
> -      && local->pure_const_state == IPA_CONST)
> -    local->pure_const_state = IPA_PURE;
> -
>    check_tree(local, t, false);
>  }
>  
> @@ -308,12 +275,6 @@ check_rhs_var (funct_state local, tree t
>  static void
>  check_lhs_var (funct_state local, tree t)
>  {
> -  /* Memcmp and strlen can both trap and they are declared pure.
> -     Which seems to imply that we can apply the same rule here.  */
> -  if (tree_could_trap_p (t)
> -      && local->pure_const_state == IPA_CONST)
> -    local->pure_const_state = IPA_PURE;
> -    
>    check_tree(local, t, true);
>  }
>  
>   

Re: [RFA] Some fixes to ipa-pure-const local analysis

[Jan Hubicka]

> Jan Hubicka wrote:
> > Hi,
> > while looking at ipa-pure-const analyzis rewrite to use SSA dataflow,
> > I noticed that there are several bits that seems wrong (in conservative way)
> > to me.  Those are at least wrong relative to old RTL based
> > implementation.
> >
> > 1) checking of "used" attribute on local variables seems wrong.  In no other
> > place of compiler we worry about it.  We worry about it only for static vars andfunctions.
> > Official documentation seems also bit off here:
> >
> > This attribute, attached to a function, means that code must be emitted
> > for the function even if it appears that the function is not referenced.
> > This is useful, for example, when the function is referenced only in
> > inline assembly.
> >
> > probably adding "to a function or static variable" is good wording?
> >
> > 2) Checking that initializer of local static variable is_gimple_min_invariant seems
> > a bit confused, since initializers are not gimplified.  I guess the check was
> > meant to verify that there is no static constructor emit for it.  I think
> > TYPE_NEEDS_CONSTRUCTING is proper check here.
> >
> >   
> When danny wrote this part, this was the best guess he could make as to
> how to check this.  if the way you are advocating is more correct, then
> change it.

Simple structure constructors are not gimple min invariant (except for
setting everything to zero), so is_giple_min_invariant is definitly
overly conservative.

I am not expert in this area but reading code of C and C++ frontend
seems that all offline constructors are those having
TYPE_NEEDS_CONSTRUCTING set.
> 
> 
> > 3) chec_rhs_var/check_lhs_var is looking if statement can trap.  This is not
> > sufficient because we should check stmt_count_trap_p instead. Still it seems
> > wrong.  There is no code in compiler that would make difference in between CONST
> > and PURE this way.  Only sane reason for this check I can think of is to avoid
> > DCE from eliminating the call causing program to not trap.  This would be handled
> > by setting local->looping flag instead, but still since DCE itself is happy to
> > eliminate stmt_could_trap_p statements, I think this is all unnecesary.
> >
> >   
> rtl dce will not delete insns that can trap.   if the tree/gimple dce
> can, then there may be a problem.  I would assume that the trap testing
> is not great since c code generally does not trap.

gimple_could_trap is correct predicate here.  We assume trapping all
floating point operations with flag_trapping_math that default to 1, so
having the check here effectivly mean that no FP function can be
removable.  Definitly in C compiler is free to remove such operations.
We just can't remove throwing instructions with -fnoncall-exceptions for
Java, but that is handled elsewhere, so I think the check here just can
be skipped.

> However given that, if we are looking in the wrong place to determine if
> it can trap, then that should be fixed.
> 
> > 4) look_for_address_of is refusing ADDR_EXPR of VAR_DECL in CONST functions.  I
> > don't think why VAR_DECL would be worse than PARM_DECL in this respect and
> > obviously function returning address of static variable is const.  Only reason
> > here I can think of is the fact that address of local variable might change
> > depending on call context, but if return value of CONST function contained
> > address of local variable in her own local stack frame, we would have undefined
> > behaviour anyway.  If the function was returning address of variable in the
> > origin function (ie we was looking at nested function), we would have explicit
> > static chain argument anyway, so the function would be optimized correctly.
> >
> >   
> Const functions cannot look at anything except parameters and
> constants.   The
> code in look_for_address_of was there to make sure that it did not
> fabricate an address that it later read from.  The idea here is that
> const functions can be commoned, and pure functions cannot. 

You mean something like:
int *p = &static_var
return *p;
?
Honza

Re: [RFA] Some fixes to ipa-pure-const local analysis

[Kenneth Zadeck]

Jan Hubicka wrote:
>> Jan Hubicka wrote:
>>     
>>> Hi,
>>> while looking at ipa-pure-const analyzis rewrite to use SSA dataflow,
>>> I noticed that there are several bits that seems wrong (in conservative way)
>>> to me.  Those are at least wrong relative to old RTL based
>>> implementation.
>>>
>>> 1) checking of "used" attribute on local variables seems wrong.  In no other
>>> place of compiler we worry about it.  We worry about it only for static vars andfunctions.
>>> Official documentation seems also bit off here:
>>>
>>> This attribute, attached to a function, means that code must be emitted
>>> for the function even if it appears that the function is not referenced.
>>> This is useful, for example, when the function is referenced only in
>>> inline assembly.
>>>
>>> probably adding "to a function or static variable" is good wording?
>>>
>>> 2) Checking that initializer of local static variable is_gimple_min_invariant seems
>>> a bit confused, since initializers are not gimplified.  I guess the check was
>>> meant to verify that there is no static constructor emit for it.  I think
>>> TYPE_NEEDS_CONSTRUCTING is proper check here.
>>>
>>>   
>>>       
>> When danny wrote this part, this was the best guess he could make as to
>> how to check this.  if the way you are advocating is more correct, then
>> change it.
>>     
>
> Simple structure constructors are not gimple min invariant (except for
> setting everything to zero), so is_giple_min_invariant is definitly
> overly conservative.
>
> I am not expert in this area but reading code of C and C++ frontend
> seems that all offline constructors are those having
> TYPE_NEEDS_CONSTRUCTING set.
>   
Then you should consult an expert to figure out how to upgrade this code.

>>     
>>> 3) chec_rhs_var/check_lhs_var is looking if statement can trap.  This is not
>>> sufficient because we should check stmt_count_trap_p instead. Still it seems
>>> wrong.  There is no code in compiler that would make difference in between CONST
>>> and PURE this way.  Only sane reason for this check I can think of is to avoid
>>> DCE from eliminating the call causing program to not trap.  This would be handled
>>> by setting local->looping flag instead, but still since DCE itself is happy to
>>> eliminate stmt_could_trap_p statements, I think this is all unnecesary.
>>>
>>>   
>>>       
>> rtl dce will not delete insns that can trap.   if the tree/gimple dce
>> can, then there may be a problem.  I would assume that the trap testing
>> is not great since c code generally does not trap.
>>     
>
> gimple_could_trap is correct predicate here.  We assume trapping all
> floating point operations with flag_trapping_math that default to 1, so
> having the check here effectivly mean that no FP function can be
> removable.  Definitly in C compiler is free to remove such operations.
> We just can't remove throwing instructions with -fnoncall-exceptions for
> Java, but that is handled elsewhere, so I think the check here just can
> be skipped.
>
>   
Some check needs to be there.    I am not saying that we got the right
set of checks but if we are throwing things, we can only mark the
function pure, we cannot mark it const.


>> However given that, if we are looking in the wrong place to determine if
>> it can trap, then that should be fixed.
>>
>>     
>>> 4) look_for_address_of is refusing ADDR_EXPR of VAR_DECL in CONST functions.  I
>>> don't think why VAR_DECL would be worse than PARM_DECL in this respect and
>>> obviously function returning address of static variable is const.  Only reason
>>> here I can think of is the fact that address of local variable might change
>>> depending on call context, but if return value of CONST function contained
>>> address of local variable in her own local stack frame, we would have undefined
>>> behaviour anyway.  If the function was returning address of variable in the
>>> origin function (ie we was looking at nested function), we would have explicit
>>> static chain argument anyway, so the function would be optimized correctly.
>>>
>>>   
>>>       
>> Const functions cannot look at anything except parameters and
>> constants.   The
>> code in look_for_address_of was there to make sure that it did not
>> fabricate an address that it later read from.  The idea here is that
>> const functions can be commoned, and pure functions cannot. 
>>     
>
> You mean something like:
> int *p = &static_var
> return *p;
>   
yes, something like this.

> ?
> Honza
>   

Re: [RFA] Some fixes to ipa-pure-const local analysis

[Jan Hubicka]

> > Simple structure constructors are not gimple min invariant (except for
> > setting everything to zero), so is_giple_min_invariant is definitly
> > overly conservative.
> >
> > I am not expert in this area but reading code of C and C++ frontend
> > seems that all offline constructors are those having
> > TYPE_NEEDS_CONSTRUCTING set.
> >   
> Then you should consult an expert to figure out how to upgrade this code.

This is why I sent this patch for review and hope some expert to appear
and tell me :)
> 
> >>     
> >>> 3) chec_rhs_var/check_lhs_var is looking if statement can trap.  This is not
> >>> sufficient because we should check stmt_count_trap_p instead. Still it seems
> >>> wrong.  There is no code in compiler that would make difference in between CONST
> >>> and PURE this way.  Only sane reason for this check I can think of is to avoid
> >>> DCE from eliminating the call causing program to not trap.  This would be handled
> >>> by setting local->looping flag instead, but still since DCE itself is happy to
> >>> eliminate stmt_could_trap_p statements, I think this is all unnecesary.
> >>>
> >>>   
> >>>       
> >> rtl dce will not delete insns that can trap.   if the tree/gimple dce
> >> can, then there may be a problem.  I would assume that the trap testing
> >> is not great since c code generally does not trap.
> >>     
> >
> > gimple_could_trap is correct predicate here.  We assume trapping all
> > floating point operations with flag_trapping_math that default to 1, so
> > having the check here effectivly mean that no FP function can be
> > removable.  Definitly in C compiler is free to remove such operations.
> > We just can't remove throwing instructions with -fnoncall-exceptions for
> > Java, but that is handled elsewhere, so I think the check here just can
> > be skipped.
> >
> >   
> Some check needs to be there.    I am not saying that we got the right
> set of checks but if we are throwing things, we can only mark the
> function pure, we cannot mark it const.

throwing is not trapping.  In C++ you throw via throw() call that will
make funtion unpure.  In Java you can throw via NULL pointer reference
and similar construct and Java does not allow these to be optimized out.
Flag_non_call_exception && gimple_can_throw is correct predicate here. 

Can you give me example where const/pure makes difference here?
I can only think of problem of removing the throw, but both const and
pure functions can be removed.
> >
> > You mean something like:
> > int *p = &static_var
> > return *p;
> >   
> yes, something like this.

Hmm, this is handled at INDIRECT_REF checking.  How much it is different from

int
t(int *a)
{
  return *a;
}

that is also just pure but not const?

this is why I think we are speaking only of code:

int *
t(int a)
{
  return &a
}

that is undefined anyway.

Honza
> 
> > ?
> > Honza
> >   

Re: [RFA] Some fixes to ipa-pure-const local analysis

[Jan Hubicka]

> 
> 	* ipa-pure-const.c (check_decl): Do not handle used attribute
> 	on local objects specially; readonly reads are safe.
> 	(look_for_address_of): Remove.
> 	(check_rhs_var, check_lhs_var): Remove tree_could_trap check.
Hi,
after some discussion both here and offline, I am still convinced that
the changes are safe, so I've comitted to the pretty-ipa branch.
I will cleanup the local analysis and add nothrow/noreturn tracking too.

Honza