Re: [PATCH] Avoid introducing undefined behavior in sccp (PR tree-optimization/59387)

[Richard Biener <rguenther at suse dot de>]

On Fri, 10 Jan 2014, Jakub Jelinek wrote:

> Hi!
> 
> If folded_casts is true, sccp can introduce undefined behavior even when
> there was none in the original loop, e.g. all actual additions performed in
> unsigned type and then cast back to signed.
> 
> The following patch fixes that by turning the arithmetic stmts added by sccp
> use unsigned operations if folded_casts and def's type has undefined
> overflow behavior.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
> 
> 2014-01-10  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/59387
> 	* tree-scalar-evolution.c: Include gimple-fold.h and gimplify-me.h.
> 	(scev_const_prop): If folded_casts and type has undefined overflow,
> 	use force_gimple_operand instead of force_gimple_operand_gsi and
> 	for each added stmt if it is assign with
> 	arith_code_with_undefined_signed_overflow, call
> 	rewrite_to_defined_overflow.
> 	* tree-ssa-loop-im.c: Don't include gimplify-me.h, include
> 	gimple-fold.h instead.
> 	(arith_code_with_undefined_signed_overflow,
> 	rewrite_to_defined_overflow): Moved to ...
> 	* gimple-fold.c (arith_code_with_undefined_signed_overflow,
> 	rewrite_to_defined_overflow): ... here.  No longer static.
> 	Include gimplify-me.h.
> 	* gimple-fold.h (arith_code_with_undefined_signed_overflow,
> 	rewrite_to_defined_overflow): New prototypes.
> 
> 	* gcc.c-torture/execute/pr59387.c: New test.
> 
> --- gcc/tree-scalar-evolution.c.jj	2014-01-08 17:44:57.596582925 +0100
> +++ gcc/tree-scalar-evolution.c	2014-01-10 15:46:55.355915072 +0100
> @@ -286,6 +286,8 @@ along with GCC; see the file COPYING3.
>  #include "dumpfile.h"
>  #include "params.h"
>  #include "tree-ssa-propagate.h"
> +#include "gimple-fold.h"
> +#include "gimplify-me.h"
>  
>  static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
>  static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
> @@ -3409,7 +3411,7 @@ scev_const_prop (void)
>      {
>        edge exit;
>        tree def, rslt, niter;
> -      gimple_stmt_iterator bsi;
> +      gimple_stmt_iterator gsi;
>  
>        /* If we do not know exact number of iterations of the loop, we cannot
>  	 replace the final value.  */
> @@ -3424,7 +3426,7 @@ scev_const_prop (void)
>        /* Ensure that it is possible to insert new statements somewhere.  */
>        if (!single_pred_p (exit->dest))
>  	split_loop_exit_edge (exit);
> -      bsi = gsi_after_labels (exit->dest);
> +      gsi = gsi_after_labels (exit->dest);
>  
>        ex_loop = superloop_at_depth (loop,
>  				    loop_depth (exit->dest->loop_father) + 1);
> @@ -3447,7 +3449,9 @@ scev_const_prop (void)
>  	      continue;
>  	    }
>  
> -	  def = analyze_scalar_evolution_in_loop (ex_loop, loop, def, NULL);
> +	  bool folded_casts;
> +	  def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
> +						  &folded_casts);
>  	  def = compute_overall_effect_of_inner_loop (ex_loop, def);
>  	  if (!tree_does_not_contain_chrecs (def)
>  	      || chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
> @@ -3485,10 +3489,38 @@ scev_const_prop (void)
>  	  def = unshare_expr (def);
>  	  remove_phi_node (&psi, false);
>  
> -	  def = force_gimple_operand_gsi (&bsi, def, false, NULL_TREE,
> -      					  true, GSI_SAME_STMT);
> +	  if (TREE_CODE (def) == INTEGER_CST && TREE_OVERFLOW (def))

TREE_OVERFLOW_P (), but it seems to me that the SCEV machinery
should do this at a good place (like where it finally records
the result into its cache before returning it, at set_and_end:
of analyze_scalar_evolution_1).

> +	    def = drop_tree_overflow (def);
> +
> +	  /* If def's type has undefined overflow and there were folded
> +	     casts, rewrite all stmts added for def into arithmetics
> +	     with defined overflow behavior.  */
> +	  if (folded_casts && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
> +	    {
> +	      gimple_seq stmts;
> +	      gimple_stmt_iterator gsi2;
> +	      def = force_gimple_operand (def, &stmts, true, NULL_TREE);
> +	      gsi2 = gsi_start (stmts);
> +	      while (!gsi_end_p (gsi2))
> +		{
> +		  gimple stmt = gsi_stmt (gsi2);
> +		  gsi_next (&gsi2);
> +		  if (is_gimple_assign (stmt)
> +		      && arith_code_with_undefined_signed_overflow
> +					(gimple_assign_rhs_code (stmt)))
> +		    gsi_insert_seq_before (&gsi,
> +					   rewrite_to_defined_overflow (stmt),
> +					   GSI_SAME_STMT);

Hmm, stmt is still in the 'stmts' sequence here, I think you should
gsi_remove it before inserting it elsewhere.

> +		  else
> +		    gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);

Also applies here, of course.

Otherwise ok.

Thanks,
Richard.

> +		}
> +	    }
> +	  else
> +	    def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
> +					    true, GSI_SAME_STMT);
> +
>  	  ass = gimple_build_assign (rslt, def);
> -	  gsi_insert_before (&bsi, ass, GSI_SAME_STMT);
> +	  gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
>  	  if (dump_file)
>  	    {
>  	      print_gimple_stmt (dump_file, ass, 0, 0);
> --- gcc/tree-ssa-loop-im.c.jj	2014-01-03 11:40:29.000000000 +0100
> +++ gcc/tree-ssa-loop-im.c	2014-01-10 15:34:32.512734315 +0100
> @@ -35,7 +35,6 @@ along with GCC; see the file COPYING3.
>  #include "gimple.h"
>  #include "gimplify.h"
>  #include "gimple-iterator.h"
> -#include "gimplify-me.h"
>  #include "gimple-ssa.h"
>  #include "tree-cfg.h"
>  #include "tree-phinodes.h"
> @@ -53,6 +52,7 @@ along with GCC; see the file COPYING3.
>  #include "tree-affine.h"
>  #include "tree-ssa-propagate.h"
>  #include "trans-mem.h"
> +#include "gimple-fold.h"
>  
>  /* TODO:  Support for predicated code motion.  I.e.
>  
> @@ -1135,67 +1135,6 @@ public:
>    unsigned int todo_;
>  };
>  
> -/* Return true if CODE is an operation that when operating on signed
> -   integer types involves undefined behavior on overflow and the
> -   operation can be expressed with unsigned arithmetic.  */
> -
> -static bool
> -arith_code_with_undefined_signed_overflow (tree_code code)
> -{
> -  switch (code)
> -    {
> -    case PLUS_EXPR:
> -    case MINUS_EXPR:
> -    case MULT_EXPR:
> -    case NEGATE_EXPR:
> -    case POINTER_PLUS_EXPR:
> -      return true;
> -    default:
> -      return false;
> -    }
> -}
> -
> -/* Rewrite STMT, an assignment with a signed integer or pointer arithmetic
> -   operation that can be transformed to unsigned arithmetic by converting
> -   its operand, carrying out the operation in the corresponding unsigned
> -   type and converting the result back to the original type.
> -
> -   Returns a sequence of statements that replace STMT and also contain
> -   a modified form of STMT itself.  */
> -
> -static gimple_seq
> -rewrite_to_defined_overflow (gimple stmt)
> -{
> -  if (dump_file && (dump_flags & TDF_DETAILS))
> -    {
> -      fprintf (dump_file, "rewriting stmt with undefined signed "
> -	       "overflow ");
> -      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
> -    }
> -
> -  tree lhs = gimple_assign_lhs (stmt);
> -  tree type = unsigned_type_for (TREE_TYPE (lhs));
> -  gimple_seq stmts = NULL;
> -  for (unsigned i = 1; i < gimple_num_ops (stmt); ++i)
> -    {
> -      gimple_seq stmts2 = NULL;
> -      gimple_set_op (stmt, i,
> -		     force_gimple_operand (fold_convert (type,
> -							 gimple_op (stmt, i)),
> -					   &stmts2, true, NULL_TREE));
> -      gimple_seq_add_seq (&stmts, stmts2);
> -    }
> -  gimple_assign_set_lhs (stmt, make_ssa_name (type, stmt));
> -  if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
> -    gimple_assign_set_rhs_code (stmt, PLUS_EXPR);
> -  gimple_seq_add_stmt (&stmts, stmt);
> -  gimple cvt = gimple_build_assign_with_ops
> -      (NOP_EXPR, lhs, gimple_assign_lhs (stmt), NULL_TREE);
> -  gimple_seq_add_stmt (&stmts, cvt);
> -
> -  return stmts;
> -}
> -
>  /* Hoist the statements in basic block BB out of the loops prescribed by
>     data stored in LIM_DATA structures associated with each statement.  Callback
>     for walk_dominator_tree.  */
> --- gcc/gimple-fold.c.jj	2014-01-09 21:08:41.000000000 +0100
> +++ gcc/gimple-fold.c	2014-01-10 15:34:02.274882625 +0100
> @@ -51,6 +51,7 @@ along with GCC; see the file COPYING3.
>  #include "gimple-pretty-print.h"
>  #include "tree-ssa-address.h"
>  #include "langhooks.h"
> +#include "gimplify-me.h"
>  
>  /* Return true when DECL can be referenced from current unit.
>     FROM_DECL (if non-null) specify constructor of variable DECL was taken from.
> @@ -3548,3 +3549,64 @@ gimple_fold_indirect_ref (tree t)
>  
>    return NULL_TREE;
>  }
> +
> +/* Return true if CODE is an operation that when operating on signed
> +   integer types involves undefined behavior on overflow and the
> +   operation can be expressed with unsigned arithmetic.  */
> +
> +bool
> +arith_code_with_undefined_signed_overflow (tree_code code)
> +{
> +  switch (code)
> +    {
> +    case PLUS_EXPR:
> +    case MINUS_EXPR:
> +    case MULT_EXPR:
> +    case NEGATE_EXPR:
> +    case POINTER_PLUS_EXPR:
> +      return true;
> +    default:
> +      return false;
> +    }
> +}
> +
> +/* Rewrite STMT, an assignment with a signed integer or pointer arithmetic
> +   operation that can be transformed to unsigned arithmetic by converting
> +   its operand, carrying out the operation in the corresponding unsigned
> +   type and converting the result back to the original type.
> +
> +   Returns a sequence of statements that replace STMT and also contain
> +   a modified form of STMT itself.  */
> +
> +gimple_seq
> +rewrite_to_defined_overflow (gimple stmt)
> +{
> +  if (dump_file && (dump_flags & TDF_DETAILS))
> +    {
> +      fprintf (dump_file, "rewriting stmt with undefined signed "
> +	       "overflow ");
> +      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
> +    }
> +
> +  tree lhs = gimple_assign_lhs (stmt);
> +  tree type = unsigned_type_for (TREE_TYPE (lhs));
> +  gimple_seq stmts = NULL;
> +  for (unsigned i = 1; i < gimple_num_ops (stmt); ++i)
> +    {
> +      gimple_seq stmts2 = NULL;
> +      gimple_set_op (stmt, i,
> +		     force_gimple_operand (fold_convert (type,
> +							 gimple_op (stmt, i)),
> +					   &stmts2, true, NULL_TREE));
> +      gimple_seq_add_seq (&stmts, stmts2);
> +    }
> +  gimple_assign_set_lhs (stmt, make_ssa_name (type, stmt));
> +  if (gimple_assign_rhs_code (stmt) == POINTER_PLUS_EXPR)
> +    gimple_assign_set_rhs_code (stmt, PLUS_EXPR);
> +  gimple_seq_add_stmt (&stmts, stmt);
> +  gimple cvt = gimple_build_assign_with_ops
> +      (NOP_EXPR, lhs, gimple_assign_lhs (stmt), NULL_TREE);
> +  gimple_seq_add_stmt (&stmts, cvt);
> +
> +  return stmts;
> +}
> --- gcc/gimple-fold.h.jj	2014-01-03 11:40:57.000000000 +0100
> +++ gcc/gimple-fold.h	2014-01-10 15:25:32.705493146 +0100
> @@ -40,5 +40,7 @@ extern tree fold_const_aggregate_ref (tr
>  extern tree gimple_get_virt_method_for_binfo (HOST_WIDE_INT, tree);
>  extern bool gimple_val_nonnegative_real_p (tree);
>  extern tree gimple_fold_indirect_ref (tree);
> +extern bool arith_code_with_undefined_signed_overflow (tree_code);
> +extern gimple_seq rewrite_to_defined_overflow (gimple);
>  
>  #endif  /* GCC_GIMPLE_FOLD_H */
> --- gcc/testsuite/gcc.c-torture/execute/pr59387.c.jj	2014-01-10 14:36:03.476754070 +0100
> +++ gcc/testsuite/gcc.c-torture/execute/pr59387.c	2014-01-10 14:36:03.476754070 +0100
> @@ -0,0 +1,19 @@
> +/* PR tree-optimization/59387 */
> +
> +int a, *d, **e = &d, f;
> +char c;
> +struct S { int f1; } b;
> +
> +int
> +main ()
> +{
> +  for (a = -19; a; a++)
> +    {
> +      for (b.f1 = 0; b.f1 < 24; b.f1++)
> +	c--;
> +      *e = &f;
> +      if (!d)
> +	return 0;
> +    }
> +  return 0;
> +}
> 
> 	Jakub
> 
> 

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