[PATCH] Fix PR34099, wrong-code with CCP

[PATCH] Fix PR34099, wrong-code with CCP

[Richard Guenther]

Currently CCP takes results of operations with at least one undefined
operand as undefined, which does not honor certain corner cases such
as UNDEFINED & x where if x is zero, the result of the operation is
not undefined.  The original testcase in question is about complex
lowering building a complex value by parts as

  tmp = IMAGPART_EXPR <z>
  z = COMPLEX_EXPR <real, tmp>
  tmp = REALPART_EXPR <z>
  z = COMPLEX_EXPR <tmp, imag>

which is not quite optimal, but legal.  CCP now saw the first tmp to
be UNDEFINED and propagated this state right through the final value
of z.  Oops.

Fixed by building a white list of operators where the current approach
works and otherwise falling back to VARYING.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to mainline.

Richard.

2007-11-15  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/34099
	* tree-ssa-ccp.c (likely_value): Use a whitelist for operators
	that produce UNDEFINED result if at least one of its operands
	is UNDEFINED.  By default the result is only UNDEFINED if all
	operands are UNDEFINED.

	* g++.dg/torture/pr3499.C: New testcase.
	* gcc.c-torture/execute/pr34099.c: Likewise.

Index: testsuite/g++.dg/torture/pr34099.C
===================================================================
*** testsuite/g++.dg/torture/pr34099.C	(revision 0)
--- testsuite/g++.dg/torture/pr34099.C	(revision 0)
***************
*** 0 ****
--- 1,25 ----
+ /* { dg-do run } */
+ 
+ #include <complex>
+ 
+ typedef std::complex<double> NumType;
+ 
+ void
+ multiply(NumType a, NumType b, unsigned ac, NumType &ab)
+ {
+   NumType s;
+   for (unsigned j=0; j<ac; j++)
+     s = a * b;
+   ab = s;
+ }
+ extern "C" void abort (void);
+ int main()
+ {
+   NumType a(1,2), b(3,-2), c;
+   multiply(a, b, 1, c);
+   if (c.real() != 7
+       || c.imag() != 4)
+     abort ();
+   return 0;
+ }
+ 
Index: tree-ssa-ccp.c
===================================================================
*** tree-ssa-ccp.c	(revision 130196)
--- tree-ssa-ccp.c	(working copy)
*************** set_lattice_value (tree var, prop_value_
*** 507,513 ****
  
     If STMT has no operands, then return CONSTANT.
  
!    Else if any operands of STMT are undefined, then return UNDEFINED.
  
     Else if any operands of STMT are constants, then return CONSTANT.
  
--- 507,514 ----
  
     If STMT has no operands, then return CONSTANT.
  
!    Else if undefinedness of operands of STMT cause its value to be
!    undefined, then return UNDEFINED.
  
     Else if any operands of STMT are constants, then return CONSTANT.
  
*************** set_lattice_value (tree var, prop_value_
*** 516,522 ****
  static ccp_lattice_t
  likely_value (tree stmt)
  {
!   bool has_constant_operand;
    stmt_ann_t ann;
    tree use;
    ssa_op_iter iter;
--- 517,523 ----
  static ccp_lattice_t
  likely_value (tree stmt)
  {
!   bool has_constant_operand, has_undefined_operand, all_undefined_operands;
    stmt_ann_t ann;
    tree use;
    ssa_op_iter iter;
*************** likely_value (tree stmt)
*** 552,568 ****
      return CONSTANT;
  
    has_constant_operand = false;
    FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
      {
        prop_value_t *val = get_value (use);
  
        if (val->lattice_val == UNDEFINED)
! 	return UNDEFINED;
  
        if (val->lattice_val == CONSTANT)
  	has_constant_operand = true;
      }
  
    if (has_constant_operand
        /* We do not consider virtual operands here -- load from read-only
  	 memory may have only VARYING virtual operands, but still be
--- 553,624 ----
      return CONSTANT;
  
    has_constant_operand = false;
+   has_undefined_operand = false;
+   all_undefined_operands = true;
    FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE | SSA_OP_VUSE)
      {
        prop_value_t *val = get_value (use);
  
        if (val->lattice_val == UNDEFINED)
! 	has_undefined_operand = true;
!       else
! 	all_undefined_operands = false;
  
        if (val->lattice_val == CONSTANT)
  	has_constant_operand = true;
      }
  
+   /* If the operation combines operands like COMPLEX_EXPR make sure to
+      not mark the result UNDEFINED if only one part of the result is
+      undefined.  */
+   if (has_undefined_operand
+       && all_undefined_operands)
+     return UNDEFINED;
+   else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+ 	   && has_undefined_operand)
+     {
+       switch (TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)))
+ 	{
+ 	/* Unary operators are handled with all_undefined_operands.  */
+ 	case PLUS_EXPR:
+ 	case MINUS_EXPR:
+ 	case MULT_EXPR:
+ 	case POINTER_PLUS_EXPR:
+ 	case TRUNC_DIV_EXPR:
+ 	case CEIL_DIV_EXPR:
+ 	case FLOOR_DIV_EXPR:
+ 	case ROUND_DIV_EXPR:
+ 	case TRUNC_MOD_EXPR:
+ 	case CEIL_MOD_EXPR:
+ 	case FLOOR_MOD_EXPR:
+ 	case ROUND_MOD_EXPR:
+ 	case RDIV_EXPR:
+ 	case EXACT_DIV_EXPR:
+ 	case LSHIFT_EXPR:
+ 	case RSHIFT_EXPR:
+ 	case LROTATE_EXPR:
+ 	case RROTATE_EXPR:
+ 	case EQ_EXPR:
+ 	case NE_EXPR:
+ 	case LT_EXPR:
+ 	case GT_EXPR:
+ 	  /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
+ 	     Not bitwise operators, one VARYING operand may specify the
+ 	     result completely.  Not logical operators for the same reason.
+ 	     Not LE/GE comparisons or unordered comparisons.  Not
+ 	     COMPLEX_EXPR as one VARYING operand makes the result partly
+ 	     not UNDEFINED.  */
+ 	  return UNDEFINED;
+ 
+ 	default:
+ 	  ;
+ 	}
+     }
+   /* If there was an UNDEFINED operand but the result may be not UNDEFINED
+      fall back to VARYING even if there were CONSTANT operands.  */
+   if (has_undefined_operand)
+     return VARYING;
+ 
    if (has_constant_operand
        /* We do not consider virtual operands here -- load from read-only
  	 memory may have only VARYING virtual operands, but still be

Index: testsuite/gcc.c-torture/execute/pr34099.c
===================================================================
*** testsuite/gcc.c-torture/execute/pr34099.c	(revision 0)
--- testsuite/gcc.c-torture/execute/pr34099.c	(revision 0)
***************
*** 0 ****
--- 1,16 ----
+ int foo (int b, int c)
+ {
+   int x;
+   if (b)
+     return x & c;
+   else
+     return 1;
+ }
+ extern void abort (void);
+ int main()
+ {
+   if (foo(1, 0) != 0)
+     abort ();
+   return 0;
+ }
+ 

Re: [PATCH] Fix PR34099, wrong-code with CCP

[Joseph S. Myers]

On Fri, 16 Nov 2007, Richard Guenther wrote:

> + 	case MULT_EXPR:
> + 	case TRUNC_DIV_EXPR:
> + 	case CEIL_DIV_EXPR:
> + 	case FLOOR_DIV_EXPR:
> + 	case ROUND_DIV_EXPR:
> + 	case TRUNC_MOD_EXPR:
> + 	case CEIL_MOD_EXPR:
> + 	case FLOOR_MOD_EXPR:
> + 	case ROUND_MOD_EXPR:
> + 	case EQ_EXPR:
> + 	case NE_EXPR:
> + 	case LT_EXPR:
> + 	case GT_EXPR:
> + 	  /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
> + 	     Not bitwise operators, one VARYING operand may specify the
> + 	     result completely.  Not logical operators for the same reason.
> + 	     Not LE/GE comparisons or unordered comparisons.  Not
> + 	     COMPLEX_EXPR as one VARYING operand makes the result partly
> + 	     not UNDEFINED.  */

x * 0 and x % 1 are always 0 (for integer x).  Comparisons may be always 0 
or always 1 for one operand outside the range of the unsigned char from 
which the original operand was promoted; likewise the results of 
divisions, or shifts.

(Exactly what is or is not undefined behavior in the presence of 
uninitialized values is the subject of DR#338 
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_338.htm>.  DR#260 was 
an earlier DR concerning related issues.)

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [PATCH] Fix PR34099, wrong-code with CCP

[Richard Guenther]

On Fri, 16 Nov 2007, Joseph S. Myers wrote:

> On Fri, 16 Nov 2007, Richard Guenther wrote:
> 
> > + 	case MULT_EXPR:
> > + 	case TRUNC_DIV_EXPR:
> > + 	case CEIL_DIV_EXPR:
> > + 	case FLOOR_DIV_EXPR:
> > + 	case ROUND_DIV_EXPR:
> > + 	case TRUNC_MOD_EXPR:
> > + 	case CEIL_MOD_EXPR:
> > + 	case FLOOR_MOD_EXPR:
> > + 	case ROUND_MOD_EXPR:
> > + 	case EQ_EXPR:
> > + 	case NE_EXPR:
> > + 	case LT_EXPR:
> > + 	case GT_EXPR:
> > + 	  /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
> > + 	     Not bitwise operators, one VARYING operand may specify the
> > + 	     result completely.  Not logical operators for the same reason.
> > + 	     Not LE/GE comparisons or unordered comparisons.  Not
> > + 	     COMPLEX_EXPR as one VARYING operand makes the result partly
> > + 	     not UNDEFINED.  */
> 
> x * 0 and x % 1 are always 0 (for integer x).  Comparisons may be always 0 
> or always 1 for one operand outside the range of the unsigned char from 
> which the original operand was promoted; likewise the results of 
> divisions, or shifts.

Right.  That'll shrink down the list to nearly zero operands.  Unless
we start to tell apart which of the operands is undefined.  I'll do a
followup patch.

> (Exactly what is or is not undefined behavior in the presence of 
> uninitialized values is the subject of DR#338 
> <http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_338.htm>.  DR#260 was 
> an earlier DR concerning related issues.)

Interesting read ;)

Thanks,
Richard.

Re: [PATCH] Fix PR34099, wrong-code with CCP

[Richard Guenther]

On Fri, 16 Nov 2007, Richard Guenther wrote:

> On Fri, 16 Nov 2007, Joseph S. Myers wrote:
> 
> > On Fri, 16 Nov 2007, Richard Guenther wrote:
> > 
> > > + 	case MULT_EXPR:
> > > + 	case TRUNC_DIV_EXPR:
> > > + 	case CEIL_DIV_EXPR:
> > > + 	case FLOOR_DIV_EXPR:
> > > + 	case ROUND_DIV_EXPR:
> > > + 	case TRUNC_MOD_EXPR:
> > > + 	case CEIL_MOD_EXPR:
> > > + 	case FLOOR_MOD_EXPR:
> > > + 	case ROUND_MOD_EXPR:
> > > + 	case EQ_EXPR:
> > > + 	case NE_EXPR:
> > > + 	case LT_EXPR:
> > > + 	case GT_EXPR:
> > > + 	  /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
> > > + 	     Not bitwise operators, one VARYING operand may specify the
> > > + 	     result completely.  Not logical operators for the same reason.
> > > + 	     Not LE/GE comparisons or unordered comparisons.  Not
> > > + 	     COMPLEX_EXPR as one VARYING operand makes the result partly
> > > + 	     not UNDEFINED.  */
> > 
> > x * 0 and x % 1 are always 0 (for integer x).  Comparisons may be always 0 
> > or always 1 for one operand outside the range of the unsigned char from 
> > which the original operand was promoted; likewise the results of 
> > divisions, or shifts.
> 
> Right.  That'll shrink down the list to nearly zero operands.  Unless
> we start to tell apart which of the operands is undefined.  I'll do a
> followup patch.

Like this one.  Bootstrap / regtest in progress.

Richard.

2007-11-18  Richard Guenther  <rguenther@suse.de>

	PR tree-optimization/34
	* tree-ssa-ccp.c (likely_value): Exclude all but PLUS_EXPR,
	MINUS_EXPR and POINTER_PLUS_EXPR from handling as UNDEFINED
	if only one operand is undefined.

	* gcc.c-torture/execute/pr34099-2.c: New testcase.

Index: tree-ssa-ccp.c
===================================================================
*** tree-ssa-ccp.c	(revision 130268)
--- tree-ssa-ccp.c	(working copy)
*************** likely_value (tree stmt)
*** 582,613 ****
  	/* Unary operators are handled with all_undefined_operands.  */
  	case PLUS_EXPR:
  	case MINUS_EXPR:
- 	case MULT_EXPR:
  	case POINTER_PLUS_EXPR:
- 	case TRUNC_DIV_EXPR:
- 	case CEIL_DIV_EXPR:
- 	case FLOOR_DIV_EXPR:
- 	case ROUND_DIV_EXPR:
- 	case TRUNC_MOD_EXPR:
- 	case CEIL_MOD_EXPR:
- 	case FLOOR_MOD_EXPR:
- 	case ROUND_MOD_EXPR:
- 	case RDIV_EXPR:
- 	case EXACT_DIV_EXPR:
- 	case LSHIFT_EXPR:
- 	case RSHIFT_EXPR:
- 	case LROTATE_EXPR:
- 	case RROTATE_EXPR:
- 	case EQ_EXPR:
- 	case NE_EXPR:
- 	case LT_EXPR:
- 	case GT_EXPR:
  	  /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
  	     Not bitwise operators, one VARYING operand may specify the
  	     result completely.  Not logical operators for the same reason.
! 	     Not LE/GE comparisons or unordered comparisons.  Not
! 	     COMPLEX_EXPR as one VARYING operand makes the result partly
! 	     not UNDEFINED.  */
  	  return UNDEFINED;
  
  	default:
--- 582,594 ----
  	/* Unary operators are handled with all_undefined_operands.  */
  	case PLUS_EXPR:
  	case MINUS_EXPR:
  	case POINTER_PLUS_EXPR:
  	  /* Not MIN_EXPR, MAX_EXPR.  One VARYING operand may be selected.
  	     Not bitwise operators, one VARYING operand may specify the
  	     result completely.  Not logical operators for the same reason.
! 	     Not COMPLEX_EXPR as one VARYING operand makes the result partly
! 	     not UNDEFINED.  Not *DIV_EXPR, comparisons and shifts because
! 	     the undefined operand may be promoted.  */
  	  return UNDEFINED;
  
  	default:
Index: testsuite/gcc.c-torture/execute/pr34099-2.c
===================================================================
*** testsuite/gcc.c-torture/execute/pr34099-2.c	(revision 0)
--- testsuite/gcc.c-torture/execute/pr34099-2.c	(revision 0)
***************
*** 0 ****
--- 1,47 ----
+ int test1 (int b, int c)
+ {
+   char x;
+   if (b)
+     return x / c;
+   else
+     return 1;
+ }
+ int test2 (int b, int c)
+ {
+   int x;
+   if (b)
+     return x * c;
+   else
+     return 1;
+ }
+ int test3 (int b, int c)
+ {
+   int x;
+   if (b)
+     return x % c;
+   else
+     return 1;
+ }
+ int test4 (int b, int c)
+ {
+   char x;
+   if (b)
+     return x == c;
+   else
+     return 1;
+ }
+ 
+ extern void abort (void);
+ int main()
+ {
+   if (test1(1, 1000) != 0)
+     abort ();
+   if (test2(1, 0) != 0)
+     abort ();
+   if (test3(1, 1) != 0)
+     abort ();
+   if (test4(1, 1000) != 0)
+     abort ();
+   return 0;
+ }
+