[2/5,P1,tree-optimization/71437] Record more equivalences in some cases

On 03/15/2017 09:17 PM, Jeff Law wrote:
>
> Patch #3 will remove handle_dominating_asserts from the core of the jump
> threading code and push it into VRP's callbacks where it should always
> have been.
>
> As a side effect it causes some code which was previously only used for
> threading from VRP to be used unconditionally.  It's actually a good
> thing as that code will find more jump threads.  But in one case  the
> resulting code is tougher for tree-ssa-uninit.c to handle and we get a
> false positive uninit warning.
>
> As it turns out for that case we're better off improving DOM slightly
> which allows DOM to simplify the test even further.  This patch
> implements the DOM improvement so that we don't see a regression when
> patch #3 is installed.
>
> The particular case we're looking to improve looks like
>
> t = a | b;
> if (t == 0)
> ...
>
> In the TRUE arm we know that a must be zero and b must be zero.
> Discovering those equivalences allows DOM to do a better job for the
> uninit testcase from the testsuite.
>
> There's clearly more that could be done with this code, but I didn't
> want to take it any further than was needed to address the regression
> that would be caused by patch #3.
>
> Bootstrapped and regression tested on x86_64-linux-gnu.  Installing on
> the trunk.  I'll be testing this in combination with patch #1 tomorrow
> on ppc64le to get additional coverage.
>
> Jeff
Whoops.  This time with the patch.

Jeff
PR tree-optimization/71437
	* tree-ssa-dom.c (derive_equivalences_from_bit_ior): New function.
	(record_temporary_equivalences): Use it.

On Wed, Mar 15, 2017 at 09:18:27PM -0600, Jeff Law wrote:
> On 03/15/2017 09:17 PM, Jeff Law wrote:
> > 
> > Patch #3 will remove handle_dominating_asserts from the core of the jump
> > threading code and push it into VRP's callbacks where it should always
> > have been.
> > 
> > As a side effect it causes some code which was previously only used for
> > threading from VRP to be used unconditionally.  It's actually a good
> > thing as that code will find more jump threads.  But in one case  the
> > resulting code is tougher for tree-ssa-uninit.c to handle and we get a
> > false positive uninit warning.
> > 
> > As it turns out for that case we're better off improving DOM slightly
> > which allows DOM to simplify the test even further.  This patch
> > implements the DOM improvement so that we don't see a regression when
> > patch #3 is installed.
> > 
> > The particular case we're looking to improve looks like
> > 
> > t = a | b;
> > if (t == 0)
> > ...
> > 
> > In the TRUE arm we know that a must be zero and b must be zero.
> > Discovering those equivalences allows DOM to do a better job for the
> > uninit testcase from the testsuite.
> > 
> > There's clearly more that could be done with this code, but I didn't
> > want to take it any further than was needed to address the regression
> > that would be caused by patch #3.
> > 
> > Bootstrapped and regression tested on x86_64-linux-gnu.  Installing on
> > the trunk.  I'll be testing this in combination with patch #1 tomorrow
> > on ppc64le to get additional coverage.
> > 
> > Jeff
> Whoops.  This time with the patch.
> 
> Jeff

> 	PR tree-optimization/71437
> 	* tree-ssa-dom.c (derive_equivalences_from_bit_ior): New function.
> 	(record_temporary_equivalences): Use it.
> 
> diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
> index ad71269..0ebe892 100644
> --- a/gcc/tree-ssa-dom.c
> +++ b/gcc/tree-ssa-dom.c
> @@ -691,6 +691,33 @@ back_propagate_equivalences (tree lhs, edge e,
>      BITMAP_FREE (domby);
>  }
>  
> +/* Record NAME has the value zero and if NAME was set from a BIT_IOR_EXPR
> +   recurse into both operands recording their values as zero too.  */
> +
> +static void
> +derive_equivalencs_from_bit_ior (tree name, const_and_copies *const_and_copies)
> +{
> +  if (TREE_CODE (name) == SSA_NAME)
> +    {
> +      tree value = fold_convert (TREE_TYPE (name), integer_zero_node);
> +
> +      /* This records the equivalence for the toplevel object.  */
> +      record_equality (name, value, const_and_copies);
> +
> +      /* And we can recurse into each operand to potentially find more
> +	 equivalences.  */
> +      gimple *def_stmt = SSA_NAME_DEF_STMT (name);
> +      if (is_gimple_assign (def_stmt)
> +	  && gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR)
> +	{
> +	  derive_equivalencs_from_bit_ior (gimple_assign_rhs1 (def_stmt),
> +					   const_and_copies);
> +	  derive_equivalencs_from_bit_ior (gimple_assign_rhs2 (def_stmt),
> +					   const_and_copies);
> +	}
> +    }
> +}
> +
>  /* Record into CONST_AND_COPIES and AVAIL_EXPRS_STACK any equivalences implied
>     by traversing edge E (which are cached in E->aux).
>  
> @@ -711,7 +738,28 @@ record_temporary_equivalences (edge e,
>        /* If we have 0 = COND or 1 = COND equivalences, record them
>  	 into our expression hash tables.  */
>        for (i = 0; edge_info->cond_equivalences.iterate (i, &eq); ++i)
> -	avail_exprs_stack->record_cond (eq);
> +	{
> +	  avail_exprs_stack->record_cond (eq);
> +
> +	  /* If the condition is testing that X == 0 is true or X != 0 is false
> +	     and X is set from a BIT_IOR_EXPR, then we can record equivalences
> +	     for the operands of the BIT_IOR_EXPR (and recurse on those).  */
> +	  tree op0 = eq->cond.ops.binary.opnd0;
> +	  tree op1 = eq->cond.ops.binary.opnd1;
> +	  if (TREE_CODE (op0) == SSA_NAME && integer_zerop (op1))
> +	    {
> +	      enum tree_code code = eq->cond.ops.binary.op;
> +	      if ((code == EQ_EXPR && eq->value == boolean_true_node)
> +		  || (code == NE_EXPR && eq->value == boolean_false_node))
> +		derive_equivalencs_from_bit_ior (op0, const_and_copies);
> +
> +	      /* TODO: We could handle BIT_AND_EXPR in a similar fashion
> +		 recording that the operands have a nonzero value.  */
> +
> +	      /* TODO: We can handle more cases here, particularly when OP0 is
> +		 known to have a boolean range.  */

I don't think its necessarily useful to put a list here of all possible
improvements, but we could also handle things like if ((a | b) </> 0)
since those imply !=.

Trev

On 03/16/2017 06:54 AM, Trevor Saunders wrote:
>> +	  if (TREE_CODE (op0) == SSA_NAME && integer_zerop (op1))
>> +	    {
>> +	      enum tree_code code = eq->cond.ops.binary.op;
>> +	      if ((code == EQ_EXPR && eq->value == boolean_true_node)
>> +		  || (code == NE_EXPR && eq->value == boolean_false_node))
>> +		derive_equivalencs_from_bit_ior (op0, const_and_copies);
>> +
>> +	      /* TODO: We could handle BIT_AND_EXPR in a similar fashion
>> +		 recording that the operands have a nonzero value.  */
>> +
>> +	      /* TODO: We can handle more cases here, particularly when OP0 is
>> +		 known to have a boolean range.  */
>
> I don't think its necessarily useful to put a list here of all possible
> improvements, but we could also handle things like if ((a | b) </> 0)
> since those imply !=.
The equivalences you derive here must hold for both objects.  So without 
additional range information you can't really determine anything about 
(a | b) > 0.

If a and b are booleans or unsigned, then ideally we'd canonicalize the 
test into an [in]equality test.  At which point the existing code would 
fire recording  a = 0 and b = 0 on the false edge.  You still can't 
record anything on the true edge.  I don't think we're good at the 
canonicalization these days.

For (a & b) != 0, unconstrained we could record a != 0 and b != 0 on the 
true edge, but nothing can be recorded on the false edge.

If we know a and b have boolean ranges we can refine that to a = 1 and b 
= 1 on the true edge, but again, nothing can be recorded on the false edge.



Jeff

On Thu, Mar 16, 2017 at 09:03:43AM -0600, Jeff Law wrote:
> On 03/16/2017 06:54 AM, Trevor Saunders wrote:
> > > +	  if (TREE_CODE (op0) == SSA_NAME && integer_zerop (op1))
> > > +	    {
> > > +	      enum tree_code code = eq->cond.ops.binary.op;
> > > +	      if ((code == EQ_EXPR && eq->value == boolean_true_node)
> > > +		  || (code == NE_EXPR && eq->value == boolean_false_node))
> > > +		derive_equivalencs_from_bit_ior (op0, const_and_copies);
> > > +
> > > +	      /* TODO: We could handle BIT_AND_EXPR in a similar fashion
> > > +		 recording that the operands have a nonzero value.  */
> > > +
> > > +	      /* TODO: We can handle more cases here, particularly when OP0 is
> > > +		 known to have a boolean range.  */
> > 
> > I don't think its necessarily useful to put a list here of all possible
> > improvements, but we could also handle things like if ((a | b) </> 0)
> > since those imply !=.
> The equivalences you derive here must hold for both objects.  So without
> additional range information you can't really determine anything about (a |
> b) > 0.

ga! I clearly didn't think this all the way through, sorry.

Trev

On Thu, 16 Mar 2017, Jeff Law wrote:

> On 03/16/2017 06:54 AM, Trevor Saunders wrote:
>>> +	  if (TREE_CODE (op0) == SSA_NAME && integer_zerop (op1))
>>> +	    {
>>> +	      enum tree_code code = eq->cond.ops.binary.op;
>>> +	      if ((code == EQ_EXPR && eq->value == boolean_true_node)
>>> +		  || (code == NE_EXPR && eq->value == boolean_false_node))
>>> +		derive_equivalencs_from_bit_ior (op0, const_and_copies);
>>> +
>>> +	      /* TODO: We could handle BIT_AND_EXPR in a similar fashion
>>> +		 recording that the operands have a nonzero value.  */
>>> +
>>> +	      /* TODO: We can handle more cases here, particularly when OP0 
>>> is
>>> +		 known to have a boolean range.  */
>> 
>> I don't think its necessarily useful to put a list here of all possible
>> improvements, but we could also handle things like if ((a | b) </> 0)
>> since those imply !=.
> The equivalences you derive here must hold for both objects.  So without 
> additional range information you can't really determine anything about (a | 
> b) > 0.

I didn't follow the discussion so I am probably completely off, but 
(a|b)>=0 is equivalent to (a>=0)&(b>=0) since it just tests for the sign 
bit (surprisingly we seem to generate different code for the 2 versions).