[PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Richard Guenther]

This is one more preparation for bit-CCP, make the lattice fully
abstract in the propagator and query it via a callback in
substitute_and_fold.  This patch also makes us do less work
substituting and folding by doing a walk over all SSA names first
and replacing their definition with the value from the lattice.

Bootstrapped and tested on x86_64-unknown-linux-gnu.  c52102b
and c52102d now fail, because they rely on undefined signed integer
overflow.

Committed to trunk.

Richard.

2010-08-04  Richard Guenther  <rguenther@suse.de>

	* tree-ssa-propagate.h (struct prop_value_d, prop_value_t): Move ...
	* tree-ssa-ccp.c: ... here.
	* tree-ssa-copy.c: ... and here.
	* tree-ssa-propagate.h (enum value_range_type, struct value_range_d, 
	value_range_t): Move ...
	* tree-vrp.c: ... here.
	* tree-ssa-propagate.h (ssa_prop_get_value_fn): New typedef.
	(substitute_and_fold): Adjust prototype.
	* tree-ssa-propagate.c (replace_uses_in): Adjust.
	(replace_phi_args_in): Likewise.
	(substitute_and_fold): Take callback to query lattice instead
	of pointer to lattice.  Replace SSA name defs with lattice
	values first.
	* tree-ssa-ccp.c (ccp_finalize): Adjust.
	* tree-ssa-copy.c (copy_prop_visit_phi_node): Adjust.
	(get_value): New function.
	(fini_copy_prop): Adjust.
	* tree-vrp.c (vrp_finalize): Adjust.

	* gcc.dg/tree-ssa/vrp35.c: Adjust.
	* gcc.dg/tree-ssa/vrp36.c: Likewise.
	* gcc.dg/tree-ssa/vrp50.c: Likewise.
	* gcc.dg/tree-ssa/vrp52.c: Likewise.

Index: trunk/gcc/tree-ssa-ccp.c
===================================================================
*** trunk.orig/gcc/tree-ssa-ccp.c	2010-08-03 16:12:40.000000000 +0200
--- trunk/gcc/tree-ssa-ccp.c	2010-08-03 16:17:23.000000000 +0200
*************** typedef enum
*** 144,149 ****
--- 144,159 ----
    VARYING
  } ccp_lattice_t;
  
+ struct prop_value_d {
+     /* Lattice value.  */
+     ccp_lattice_t lattice_val;
+ 
+     /* Propagated value.  */
+     tree value;
+ };
+ 
+ typedef struct prop_value_d prop_value_t;
+ 
  /* Array of propagated constant values.  After propagation,
     CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I).  If
     the constant is held in an SSA name representing a memory store
*************** ccp_finalize (void)
*** 645,651 ****
  
    do_dbg_cnt ();
    /* Perform substitutions based on the known constant values.  */
!   something_changed = substitute_and_fold (const_val, ccp_fold_stmt, true);
  
    free (const_val);
    const_val = NULL;
--- 655,662 ----
  
    do_dbg_cnt ();
    /* Perform substitutions based on the known constant values.  */
!   something_changed = substitute_and_fold (get_constant_value,
! 					   ccp_fold_stmt, true);
  
    free (const_val);
    const_val = NULL;
Index: trunk/gcc/tree-ssa-copy.c
===================================================================
*** trunk.orig/gcc/tree-ssa-copy.c	2010-08-03 16:12:40.000000000 +0200
--- trunk/gcc/tree-ssa-copy.c	2010-08-03 16:17:23.000000000 +0200
*************** propagate_tree_value_into_stmt (gimple_s
*** 285,290 ****
--- 285,298 ----
     After propagation, the copy-of value for each variable X_i is
     converted into the final value by walking the copy-of chains and
     updating COPY_OF[i].VALUE to be the last element of the chain.  */
+ 
+ struct prop_value_d {
+     /* Copy-of value.  */
+     tree value;
+ };
+ 
+ typedef struct prop_value_d prop_value_t;
+ 
  static prop_value_t *copy_of;
  
  /* Used in set_copy_of_val to determine if the last link of a copy-of
*************** copy_prop_visit_phi_node (gimple phi)
*** 626,632 ****
  {
    enum ssa_prop_result retval;
    unsigned i;
!   prop_value_t phi_val = { 0, NULL_TREE };
  
    tree lhs = gimple_phi_result (phi);
  
--- 634,640 ----
  {
    enum ssa_prop_result retval;
    unsigned i;
!   prop_value_t phi_val = { NULL_TREE };
  
    tree lhs = gimple_phi_result (phi);
  
*************** init_copy_prop (void)
*** 818,823 ****
--- 826,841 ----
      }
  }
  
+ /* Callback for substitute_and_fold to get at the final copy-of values.  */
+ 
+ static tree
+ get_value (tree name)
+ {
+   tree val = copy_of[SSA_NAME_VERSION (name)].value;
+   if (val && val != name)
+     return val;
+   return NULL_TREE;
+ }
  
  /* Deallocate memory used in copy propagation and do final
     substitution.  */
*************** init_copy_prop (void)
*** 825,836 ****
  static void
  fini_copy_prop (void)
  {
!   size_t i;
!   prop_value_t *tmp;
  
    /* Set the final copy-of value for each variable by traversing the
       copy-of chains.  */
-   tmp = XCNEWVEC (prop_value_t, num_ssa_names);
    for (i = 1; i < num_ssa_names; i++)
      {
        tree var = ssa_name (i);
--- 843,852 ----
  static void
  fini_copy_prop (void)
  {
!   unsigned i;
  
    /* Set the final copy-of value for each variable by traversing the
       copy-of chains.  */
    for (i = 1; i < num_ssa_names; i++)
      {
        tree var = ssa_name (i);
*************** fini_copy_prop (void)
*** 839,845 ****
  	  || copy_of[i].value == var)
  	continue;
  
!       tmp[i].value = get_last_copy_of (var);
  
        /* In theory the points-to solution of all members of the
           copy chain is their intersection.  For now we do not bother
--- 855,861 ----
  	  || copy_of[i].value == var)
  	continue;
  
!       copy_of[i].value = get_last_copy_of (var);
  
        /* In theory the points-to solution of all members of the
           copy chain is their intersection.  For now we do not bother
*************** fini_copy_prop (void)
*** 847,864 ****
  	 information completely by setting the points-to solution
  	 of the representative to the first solution we find if
  	 it doesn't have one already.  */
!       if (tmp[i].value != var
  	  && POINTER_TYPE_P (TREE_TYPE (var))
  	  && SSA_NAME_PTR_INFO (var)
! 	  && !SSA_NAME_PTR_INFO (tmp[i].value))
! 	duplicate_ssa_name_ptr_info (tmp[i].value, SSA_NAME_PTR_INFO (var));
      }
  
!   substitute_and_fold (tmp, NULL, true);
  
    free (cached_last_copy_of);
    free (copy_of);
-   free (tmp);
  }
  
  
--- 863,879 ----
  	 information completely by setting the points-to solution
  	 of the representative to the first solution we find if
  	 it doesn't have one already.  */
!       if (copy_of[i].value != var
  	  && POINTER_TYPE_P (TREE_TYPE (var))
  	  && SSA_NAME_PTR_INFO (var)
! 	  && !SSA_NAME_PTR_INFO (copy_of[i].value))
! 	duplicate_ssa_name_ptr_info (copy_of[i].value, SSA_NAME_PTR_INFO (var));
      }
  
!   substitute_and_fold (get_value, NULL, true);
  
    free (cached_last_copy_of);
    free (copy_of);
  }
  
  
Index: trunk/gcc/tree-ssa-propagate.c
===================================================================
*** trunk.orig/gcc/tree-ssa-propagate.c	2010-08-03 16:12:40.000000000 +0200
--- trunk/gcc/tree-ssa-propagate.c	2010-08-04 10:22:27.000000000 +0200
*************** static struct prop_stats_d prop_stats;
*** 872,878 ****
     PROP_VALUE. Return true if at least one reference was replaced.  */
  
  static bool
! replace_uses_in (gimple stmt, prop_value_t *prop_value)
  {
    bool replaced = false;
    use_operand_p use;
--- 872,878 ----
     PROP_VALUE. Return true if at least one reference was replaced.  */
  
  static bool
! replace_uses_in (gimple stmt, ssa_prop_get_value_fn get_value)
  {
    bool replaced = false;
    use_operand_p use;
*************** replace_uses_in (gimple stmt, prop_value
*** 881,887 ****
    FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
      {
        tree tuse = USE_FROM_PTR (use);
!       tree val = prop_value[SSA_NAME_VERSION (tuse)].value;
  
        if (val == tuse || val == NULL_TREE)
  	continue;
--- 881,887 ----
    FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
      {
        tree tuse = USE_FROM_PTR (use);
!       tree val = (*get_value) (tuse);
  
        if (val == tuse || val == NULL_TREE)
  	continue;
*************** replace_uses_in (gimple stmt, prop_value
*** 911,917 ****
     values from PROP_VALUE.  */
  
  static void
! replace_phi_args_in (gimple phi, prop_value_t *prop_value)
  {
    size_t i;
    bool replaced = false;
--- 911,917 ----
     values from PROP_VALUE.  */
  
  static void
! replace_phi_args_in (gimple phi, ssa_prop_get_value_fn get_value)
  {
    size_t i;
    bool replaced = false;
*************** replace_phi_args_in (gimple phi, prop_va
*** 928,934 ****
  
        if (TREE_CODE (arg) == SSA_NAME)
  	{
! 	  tree val = prop_value[SSA_NAME_VERSION (arg)].value;
  
  	  if (val && val != arg && may_propagate_copy (arg, val))
  	    {
--- 928,934 ----
  
        if (TREE_CODE (arg) == SSA_NAME)
  	{
! 	  tree val = (*get_value) (arg);
  
  	  if (val && val != arg && may_propagate_copy (arg, val))
  	    {
*************** replace_phi_args_in (gimple phi, prop_va
*** 978,990 ****
     Return TRUE when something changed.  */
  
  bool
! substitute_and_fold (prop_value_t *prop_value, ssa_prop_fold_stmt_fn fold_fn,
  		     bool do_dce)
  {
    basic_block bb;
    bool something_changed = false;
  
!   if (prop_value == NULL && !fold_fn)
      return false;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
--- 978,992 ----
     Return TRUE when something changed.  */
  
  bool
! substitute_and_fold (ssa_prop_get_value_fn get_value_fn,
! 		     ssa_prop_fold_stmt_fn fold_fn,
  		     bool do_dce)
  {
    basic_block bb;
    bool something_changed = false;
+   unsigned i;
  
!   if (!get_value_fn && !fold_fn)
      return false;
  
    if (dump_file && (dump_flags & TDF_DETAILS))
*************** substitute_and_fold (prop_value_t *prop_
*** 992,1006 ****
  
    memset (&prop_stats, 0, sizeof (prop_stats));
  
!   /* Substitute values in every statement of every basic block.  */
    FOR_EACH_BB (bb)
      {
        gimple_stmt_iterator i;
  
        /* Propagate known values into PHI nodes.  */
!       if (prop_value)
  	for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
! 	  replace_phi_args_in (gsi_stmt (i), prop_value);
  
        /* Propagate known values into stmts.  Do a backward walk to expose
  	 more trivially deletable stmts.  */
--- 994,1059 ----
  
    memset (&prop_stats, 0, sizeof (prop_stats));
  
!   /* Substitute lattice values at definition sites.  */
!   if (get_value_fn)
!     for (i = 1; i < num_ssa_names; ++i)
!       {
! 	tree name = ssa_name (i);
! 	tree val;
! 	gimple def_stmt;
! 	gimple_stmt_iterator gsi;
! 
! 	if (!name
! 	    || !is_gimple_reg (name))
! 	  continue;
! 
! 	def_stmt = SSA_NAME_DEF_STMT (name);
! 	if (gimple_nop_p (def_stmt)
! 	    /* Do not substitute ASSERT_EXPR rhs, this will confuse VRP.  */
! 	    || (gimple_assign_single_p (def_stmt)
! 		&& gimple_assign_rhs_code (def_stmt) == ASSERT_EXPR)
! 	    || !(val = (*get_value_fn) (name))
! 	    || !may_propagate_copy (name, val))
! 	  continue;
! 
! 	gsi = gsi_for_stmt (def_stmt);
! 	if (is_gimple_assign (def_stmt))
! 	  {
! 	    gimple_assign_set_rhs_with_ops (&gsi, TREE_CODE (val),
! 					    val, NULL_TREE);
! 	    gcc_assert (gsi_stmt (gsi) == def_stmt);
! 	    if (maybe_clean_eh_stmt (def_stmt))
! 	      gimple_purge_dead_eh_edges (gimple_bb (def_stmt));
! 	    update_stmt (def_stmt);
! 	  }
! 	else if (is_gimple_call (def_stmt))
! 	  {
! 	    if (update_call_from_tree (&gsi, val)
! 		&& maybe_clean_or_replace_eh_stmt (def_stmt, gsi_stmt (gsi)))
! 	      gimple_purge_dead_eh_edges (gimple_bb (gsi_stmt (gsi)));
! 	  }
! 	else if (gimple_code (def_stmt) == GIMPLE_PHI)
! 	  {
! 	    gimple new_stmt = gimple_build_assign (name, val);
! 	    gimple_stmt_iterator gsi2;
! 	    SSA_NAME_DEF_STMT (name) = new_stmt;
! 	    gsi2 = gsi_after_labels (gimple_bb (def_stmt));
! 	    gsi_insert_before (&gsi2, new_stmt, GSI_SAME_STMT);
! 	    remove_phi_node (&gsi, false);
! 	  }
! 
! 	something_changed = true;
!       }
! 
!   /* Propagate into all uses and fold.  */
    FOR_EACH_BB (bb)
      {
        gimple_stmt_iterator i;
  
        /* Propagate known values into PHI nodes.  */
!       if (get_value_fn)
  	for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
! 	  replace_phi_args_in (gsi_stmt (i), get_value_fn);
  
        /* Propagate known values into stmts.  Do a backward walk to expose
  	 more trivially deletable stmts.  */
*************** substitute_and_fold (prop_value_t *prop_
*** 1073,1081 ****
  
  	  /* Only replace real uses if we couldn't fold the
  	     statement using value range information.  */
! 	  if (prop_value
  	      && !did_replace)
! 	    did_replace |= replace_uses_in (stmt, prop_value);
  
  	  /* If we made a replacement, fold the statement.  */
  	  if (did_replace)
--- 1126,1134 ----
  
  	  /* Only replace real uses if we couldn't fold the
  	     statement using value range information.  */
! 	  if (get_value_fn
  	      && !did_replace)
! 	    did_replace |= replace_uses_in (stmt, get_value_fn);
  
  	  /* If we made a replacement, fold the statement.  */
  	  if (did_replace)
Index: trunk/gcc/tree-ssa-propagate.h
===================================================================
*** trunk.orig/gcc/tree-ssa-propagate.h	2010-08-03 16:12:40.000000000 +0200
--- trunk/gcc/tree-ssa-propagate.h	2010-08-03 16:17:23.000000000 +0200
*************** enum ssa_prop_result {
*** 61,116 ****
  };
  
  
- struct prop_value_d {
-     /* Lattice value.  Each propagator is free to define its own
-        lattice and this field is only meaningful while propagating.
-        It will not be used by substitute_and_fold.  */
-     unsigned lattice_val;
- 
-     /* Propagated value.  */
-     tree value;
- };
- 
- typedef struct prop_value_d prop_value_t;
- 
- 
- /* Type of value ranges.  See value_range_d for a description of these
-    types.  */
- enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
- 
- /* Range of values that can be associated with an SSA_NAME after VRP
-    has executed.  */
- struct value_range_d
- {
-   /* Lattice value represented by this range.  */
-   enum value_range_type type;
- 
-   /* Minimum and maximum values represented by this range.  These
-      values should be interpreted as follows:
- 
- 	- If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must
- 	  be NULL.
- 
- 	- If TYPE == VR_RANGE then MIN holds the minimum value and
- 	  MAX holds the maximum value of the range [MIN, MAX].
- 
- 	- If TYPE == ANTI_RANGE the variable is known to NOT
- 	  take any values in the range [MIN, MAX].  */
-   tree min;
-   tree max;
- 
-   /* Set of SSA names whose value ranges are equivalent to this one.
-      This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
-   bitmap equiv;
- };
- 
- typedef struct value_range_d value_range_t;
- 
- 
  /* Call-back functions used by the value propagation engine.  */
  typedef enum ssa_prop_result (*ssa_prop_visit_stmt_fn) (gimple, edge *, tree *);
  typedef enum ssa_prop_result (*ssa_prop_visit_phi_fn) (gimple);
  typedef bool (*ssa_prop_fold_stmt_fn) (gimple_stmt_iterator *gsi);
  
  
  /* In tree-ssa-propagate.c  */
--- 61,71 ----
  };
  
  
  /* Call-back functions used by the value propagation engine.  */
  typedef enum ssa_prop_result (*ssa_prop_visit_stmt_fn) (gimple, edge *, tree *);
  typedef enum ssa_prop_result (*ssa_prop_visit_phi_fn) (gimple);
  typedef bool (*ssa_prop_fold_stmt_fn) (gimple_stmt_iterator *gsi);
+ typedef tree (*ssa_prop_get_value_fn) (tree);
  
  
  /* In tree-ssa-propagate.c  */
*************** bool valid_gimple_rhs_p (tree);
*** 119,124 ****
  void move_ssa_defining_stmt_for_defs (gimple, gimple);
  bool update_call_from_tree (gimple_stmt_iterator *, tree);
  bool stmt_makes_single_store (gimple);
! bool substitute_and_fold (prop_value_t *, ssa_prop_fold_stmt_fn, bool);
  
  #endif /* _TREE_SSA_PROPAGATE_H  */
--- 74,79 ----
  void move_ssa_defining_stmt_for_defs (gimple, gimple);
  bool update_call_from_tree (gimple_stmt_iterator *, tree);
  bool stmt_makes_single_store (gimple);
! bool substitute_and_fold (ssa_prop_get_value_fn, ssa_prop_fold_stmt_fn, bool);
  
  #endif /* _TREE_SSA_PROPAGATE_H  */
Index: trunk/gcc/tree-vrp.c
===================================================================
*** trunk.orig/gcc/tree-vrp.c	2010-08-03 16:12:40.000000000 +0200
--- trunk/gcc/tree-vrp.c	2010-08-03 16:36:26.000000000 +0200
*************** along with GCC; see the file COPYING3.
*** 42,47 ****
--- 42,79 ----
  #include "tree-chrec.h"
  
  
+ /* Type of value ranges.  See value_range_d for a description of these
+    types.  */
+ enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
+ 
+ /* Range of values that can be associated with an SSA_NAME after VRP
+    has executed.  */
+ struct value_range_d
+ {
+   /* Lattice value represented by this range.  */
+   enum value_range_type type;
+ 
+   /* Minimum and maximum values represented by this range.  These
+      values should be interpreted as follows:
+ 
+ 	- If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must
+ 	  be NULL.
+ 
+ 	- If TYPE == VR_RANGE then MIN holds the minimum value and
+ 	  MAX holds the maximum value of the range [MIN, MAX].
+ 
+ 	- If TYPE == ANTI_RANGE the variable is known to NOT
+ 	  take any values in the range [MIN, MAX].  */
+   tree min;
+   tree max;
+ 
+   /* Set of SSA names whose value ranges are equivalent to this one.
+      This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE.  */
+   bitmap equiv;
+ };
+ 
+ typedef struct value_range_d value_range_t;
+ 
  /* Set of SSA names found live during the RPO traversal of the function
     for still active basic-blocks.  */
  static sbitmap *live;
*************** static void
*** 7526,7533 ****
  vrp_finalize (void)
  {
    size_t i;
-   prop_value_t *single_val_range;
-   bool do_value_subst_p;
    unsigned num = num_ssa_names;
  
    if (dump_file)
--- 7558,7563 ----
*************** vrp_finalize (void)
*** 7537,7567 ****
        fprintf (dump_file, "\n");
      }
  
!   /* We may have ended with ranges that have exactly one value.  Those
!      values can be substituted as any other const propagated
!      value using substitute_and_fold.  */
!   single_val_range = XCNEWVEC (prop_value_t, num);
! 
!   do_value_subst_p = false;
!   for (i = 0; i < num; i++)
!     if (vr_value[i]
! 	&& vr_value[i]->type == VR_RANGE
! 	&& vr_value[i]->min == vr_value[i]->max
! 	&& is_gimple_min_invariant (vr_value[i]->min))
!       {
! 	single_val_range[i].value = vr_value[i]->min;
! 	do_value_subst_p = true;
!       }
! 
!   if (!do_value_subst_p)
!     {
!       /* We found no single-valued ranges, don't waste time trying to
! 	 do single value substitution in substitute_and_fold.  */
!       free (single_val_range);
!       single_val_range = NULL;
!     }
! 
!   substitute_and_fold (single_val_range, vrp_fold_stmt, false);
  
    if (warn_array_bounds)
      check_all_array_refs ();
--- 7567,7574 ----
        fprintf (dump_file, "\n");
      }
  
!   substitute_and_fold (op_with_constant_singleton_value_range,
! 		       vrp_fold_stmt, false);
  
    if (warn_array_bounds)
      check_all_array_refs ();
*************** vrp_finalize (void)
*** 7578,7584 ****
  	free (vr_value[i]);
        }
  
-   free (single_val_range);
    free (vr_value);
    free (vr_phi_edge_counts);
  
--- 7585,7590 ----
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c	2009-09-15 15:27:14.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp35.c	2010-08-03 16:28:29.000000000 +0200
*************** int test1(int i, int k)
*** 11,15 ****
    return 1;
  }
  
! /* { dg-final { scan-tree-dump "Folding predicate j_.* == 10 to 0" "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp1" } } */
--- 11,15 ----
    return 1;
  }
  
! /* { dg-final { scan-tree-dump-not "j_.* == 10" "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c	2009-09-15 15:27:14.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp36.c	2010-08-03 16:28:52.000000000 +0200
*************** int foo(int i)
*** 8,12 ****
    return 1;
  }
  
! /* { dg-final { scan-tree-dump "Folding predicate i_.* == 1 to 0" "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp1" } } */
--- 8,12 ----
    return 1;
  }
  
! /* { dg-final { scan-tree-dump-not "i_.* == 1" "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp50.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp50.c	2010-07-09 10:21:18.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp50.c	2010-08-03 16:29:27.000000000 +0200
*************** int baz (int x, int y)
*** 30,36 ****
    return x < 20;
  }
  
! /* { dg-final { scan-tree-dump "Folding predicate i_\[^\n\r\]* to 1" "vrp1" } } */
! /* { dg-final { scan-tree-dump "Folding predicate c_\[^\n\r\]* to 1" "vrp1" } } */
! /* { dg-final { scan-tree-dump "Folding predicate x_\[^\n\r\]* to 1" "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp1" } } */
--- 30,34 ----
    return x < 20;
  }
  
! /* { dg-final { scan-tree-dump-times "return 1;" 3 "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp1" } } */
Index: trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c
===================================================================
*** trunk.orig/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c	2010-07-10 13:25:52.000000000 +0200
--- trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp52.c	2010-08-03 16:29:43.000000000 +0200
*************** foo (unsigned int i, unsigned int j)
*** 12,16 ****
    return i >= 1024 + 2048;
  }
  
! /* { dg-final { scan-tree-dump "Folding predicate i_\[^\n\r\]* to 1" "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp1" } } */
--- 12,16 ----
    return i >= 1024 + 2048;
  }
  
! /* { dg-final { scan-tree-dump-times "return 1;" 1 "vrp1" } } */
  /* { dg-final { cleanup-tree-dump "vrp1" } } */

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Arnaud Charlet]

> Bootstrapped and tested on x86_64-unknown-linux-gnu.  c52102b
> and c52102d now fail, because they rely on undefined signed integer
> overflow.

Ada ACATS tests do not rely on signed integer overflow: Ada has built-in
overflow checks as part of the language, but this capability requires the
-gnato switch.

If these tests are failing, it means the -gnato switch is missing on these
tests.

Can you please fix that by updating gcc/testsuite/ada/acats/overflow.lst ?
Thanks in advance.

Arno

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Richard Guenther]

On Wed, 4 Aug 2010, Arnaud Charlet wrote:

> > Bootstrapped and tested on x86_64-unknown-linux-gnu.  c52102b
> > and c52102d now fail, because they rely on undefined signed integer
> > overflow.
> 
> Ada ACATS tests do not rely on signed integer overflow: Ada has built-in
> overflow checks as part of the language, but this capability requires the
> -gnato switch.
> 
> If these tests are failing, it means the -gnato switch is missing on these
> tests.
> 
> Can you please fix that by updating gcc/testsuite/ada/acats/overflow.lst ?
> Thanks in advance.

Adding -gnato doesn't fix the testcases (checked c52102b).

Richard.

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Arnaud Charlet]

> > > Bootstrapped and tested on x86_64-unknown-linux-gnu.  c52102b
> > > and c52102d now fail, because they rely on undefined signed integer
> > > overflow.
> > 
> > Ada ACATS tests do not rely on signed integer overflow: Ada has built-in
> > overflow checks as part of the language, but this capability requires the
> > -gnato switch.
> > 
> > If these tests are failing, it means the -gnato switch is missing on these
> > tests.
> > 
> > Can you please fix that by updating
> > gcc/testsuite/ada/acats/overflow.lst ?
> > Thanks in advance.
> 
> Adding -gnato doesn't fix the testcases (checked c52102b).

Well, then there's something fishy here that needs to be investigated, can you
expand on why these tests "rely on undefined signed integer overflow" ?

Arno

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Richard Guenther]

On Wed, 4 Aug 2010, Arnaud Charlet wrote:

> > > > Bootstrapped and tested on x86_64-unknown-linux-gnu.  c52102b
> > > > and c52102d now fail, because they rely on undefined signed integer
> > > > overflow.
> > > 
> > > Ada ACATS tests do not rely on signed integer overflow: Ada has built-in
> > > overflow checks as part of the language, but this capability requires the
> > > -gnato switch.
> > > 
> > > If these tests are failing, it means the -gnato switch is missing on these
> > > tests.
> > > 
> > > Can you please fix that by updating
> > > gcc/testsuite/ada/acats/overflow.lst ?
> > > Thanks in advance.
> > 
> > Adding -gnato doesn't fix the testcases (checked c52102b).
> 
> Well, then there's something fishy here that needs to be investigated, can you
> expand on why these tests "rely on undefined signed integer overflow" ?

I looked at the VRP dump and it derives perfectly valid assumptions.
From

  <various bounds checking concludes ident_int_2_12 is [1, 4]
   and ident_int_1_10 is [1, 4]>

<bb 15>:
  D.2465_155 = ident_int_2_12 + 1;
  L27b_156 = D.2465_155 - ident_int_1_10;
  L29b_159 = L27b_156 + 1;

<bb 16>:
  # L29b_363 = PHI <L29b_159(15), 1(14)>
...

  and we arrive with [-3, 9] for prephitmp.53_302 and [-1, 5] for L29b_363

  if (prephitmp.53_302 > L29b_363)
    goto <bb 27>;

<bb 27>:

  thus we can conclude that prephitmp.53_302 is [0, 9] here.
  The following statement then produces a range of [2147483647, overflow].
  So we happily substitute a constant value of 2147483647 for D.2544_253.

  D.2544_253 = prephitmp.53_302 + 2147483647;
  D.2553_254 = (size_type) D.2544_253;
...
  D.2554_257 = D.2553_254 + 1;


Richard.

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Eric Botcazou]

> I looked at the VRP dump and it derives perfectly valid assumptions.
> From
>
>   <various bounds checking concludes ident_int_2_12 is [1, 4]
>    and ident_int_1_10 is [1, 4]>
>
> <bb 15>:
>   D.2465_155 = ident_int_2_12 + 1;
>   L27b_156 = D.2465_155 - ident_int_1_10;
>   L29b_159 = L27b_156 + 1;
>
> <bb 16>:
>   # L29b_363 = PHI <L29b_159(15), 1(14)>
> ...
>
>   and we arrive with [-3, 9] for prephitmp.53_302 and [-1, 5] for L29b_363
>
>   if (prephitmp.53_302 > L29b_363)
>     goto <bb 27>;
>
> <bb 27>:
>
>   thus we can conclude that prephitmp.53_302 is [0, 9] here.
>   The following statement then produces a range of [2147483647, overflow].
>   So we happily substitute a constant value of 2147483647 for D.2544_253.
>
>   D.2544_253 = prephitmp.53_302 + 2147483647;
>   D.2553_254 = (size_type) D.2544_253;
> ...
>   D.2554_257 = D.2553_254 + 1;

I'll look into it.

-- 
Eric Botcazou

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Richard Guenther]

On Wed, 4 Aug 2010, Richard Guenther wrote:

> On Wed, 4 Aug 2010, Arnaud Charlet wrote:
> 
> > > > > Bootstrapped and tested on x86_64-unknown-linux-gnu.  c52102b
> > > > > and c52102d now fail, because they rely on undefined signed integer
> > > > > overflow.
> > > > 
> > > > Ada ACATS tests do not rely on signed integer overflow: Ada has built-in
> > > > overflow checks as part of the language, but this capability requires the
> > > > -gnato switch.
> > > > 
> > > > If these tests are failing, it means the -gnato switch is missing on these
> > > > tests.
> > > > 
> > > > Can you please fix that by updating
> > > > gcc/testsuite/ada/acats/overflow.lst ?
> > > > Thanks in advance.
> > > 
> > > Adding -gnato doesn't fix the testcases (checked c52102b).
> > 
> > Well, then there's something fishy here that needs to be investigated, can you
> > expand on why these tests "rely on undefined signed integer overflow" ?
> 
> I looked at the VRP dump and it derives perfectly valid assumptions.
> From
> 
>   <various bounds checking concludes ident_int_2_12 is [1, 4]
>    and ident_int_1_10 is [1, 4]>
> 
> <bb 15>:
>   D.2465_155 = ident_int_2_12 + 1;
>   L27b_156 = D.2465_155 - ident_int_1_10;
>   L29b_159 = L27b_156 + 1;
> 
> <bb 16>:
>   # L29b_363 = PHI <L29b_159(15), 1(14)>
> ...
> 
>   and we arrive with [-3, 9] for prephitmp.53_302 and [-1, 5] for L29b_363
> 
>   if (prephitmp.53_302 > L29b_363)
>     goto <bb 27>;
> 
> <bb 27>:
> 
>   thus we can conclude that prephitmp.53_302 is [0, 9] here.
>   The following statement then produces a range of [2147483647, overflow].
>   So we happily substitute a constant value of 2147483647 for D.2544_253.
> 
>   D.2544_253 = prephitmp.53_302 + 2147483647;
>   D.2553_254 = (size_type) D.2544_253;
> ...
>   D.2554_257 = D.2553_254 + 1;

Btw, is it really necessary to use INT_MIN as minimum index value for
arrays?

    typedef character c52102b__B_2__T40b[-2147483647:(integer) L29b > 1 ? 
(size_type) (((integer) L29b + -1) + -2147483648) : -2147483648];

    S38b[-2147483647 ...]{lb: -2147483648 sz: 1} = ...

not that it is invalid, but the above situation might be triggered
by this.

Richard.

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Eric Botcazou]

> Btw, is it really necessary to use INT_MIN as minimum index value for
> arrays?
>
>     typedef character c52102b__B_2__T40b[-2147483647:(integer) L29b > 1 ?
> (size_type) (((integer) L29b + -1) + -2147483648) : -2147483648];
>
>     S38b[-2147483647 ...]{lb: -2147483648 sz: 1} = ...
>
> not that it is invalid, but the above situation might be triggered
> by this.

Unfortunately yes, we have unconstrained arrays:

          TYPE ARR IS ARRAY (INTEGER RANGE <>) OF INTEGER;

whose index spans the whole range of "integer" so, when extracting slices of 
them with non-fixed bounds, we need to base them at INT_MIN lest the high 
bound overflows.

-- 
Eric Botcazou

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 935 bytes --]

>   D.2544_253 = prephitmp.53_302 + 2147483647;
>   D.2553_254 = (size_type) D.2544_253;

The signed integer overflow is introduced during the reassoc1 pass.  For the 
attached reduced testcase, we start from:

<bb 43>:
  # L41b_3 = PHI <L41b_213(42), 0(41)>
  L43b_216 = L41b_3 + L39b_195;
  if (L43b_216 <= 0)
    goto <bb 44>;
  else
    goto <bb 45>;

<bb 44>:
Invalid sum of outgoing probabilities 0.0%
  .gnat_rcheck_10 ("c52102b.adb", 44);

<bb 45>:
  D.2615_217 = L43b_216 + -1;
  iftmp.30_218 = D.2615_217 + -2147483648;
  D.2624_225 = (size_type) iftmp.30_218;

and we go to:

<bb 43>:
  # L41b_3 = PHI <L41b_213(42), 0(41)>
  L43b_216 = L41b_3 + L39b_195;
  if (L43b_216 <= 0)
    goto <bb 44>;
  else
    goto <bb 45>;

<bb 44>:
Invalid sum of outgoing probabilities 0.0%
  .gnat_rcheck_10 ("c52102b.adb", 44);

<bb 45>:
  iftmp.30_218 = L43b_216 + 2147483647;
  D.2624_225 = (size_type) iftmp.30_218;



-- 
Eric Botcazou

[-- Attachment #2: c52102b.adb --]
[-- Type: text/x-adasrc, Size: 1934 bytes --]

WITH REPORT; USE REPORT; 

PROCEDURE  C52102B  IS

     IDENT_INT_1 : INTEGER := IDENT_INT (1);
     IDENT_INT_2 : INTEGER := IDENT_INT (2);
     IDENT_INT_3 : INTEGER := IDENT_INT (3);
     IDENT_INT_4 : INTEGER := IDENT_INT (4);
     IDENT_INT_5 : INTEGER := IDENT_INT (5);
     IDENT_INT_6 : INTEGER := IDENT_INT (6);
     IDENT_INT_8 : INTEGER := IDENT_INT (8);
     IDENT_INT_9 : INTEGER := IDENT_INT (9);

BEGIN

     DECLARE
          A   :   ARRAY( 1..IDENT_INT_4 ) OF INTEGER; 

     BEGIN
          A   :=   (  11  ,  12  ,  13  ,  14  );
          A   :=   (  1   , A(IDENT_INT_1) , A(IDENT_INT_2) ,
                                              A(IDENT_INT_1) );
          IF  A /= (  1   ,  11  ,  12  ,  11  )  THEN
               raise Program_Error;
          END IF;

          A   :=   (  11  ,  12  ,  13  ,  14  );
          A   :=   ( A(IDENT_INT_4) , A(IDENT_INT_3) ,
                                       A(IDENT_INT_4) ,  1   );
          IF  A /= (  14  ,  13  ,  14  ,  1   )  THEN
               raise Program_Error;
          END IF;

     END; 


     DECLARE
          TYPE ARR IS ARRAY (INTEGER RANGE <>) OF INTEGER;
          A   :  ARR (1..10);

     BEGIN
          A   :=  ( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 );
          A   :=  0  &  A(IDENT_INT_1..IDENT_INT_2)  &
                        A(IDENT_INT_1..IDENT_INT_2)  &
                         A(IDENT_INT_1..IDENT_INT_5); 
          IF   A  /=  ( 0 , 1 , 2 , 1 , 2 , 1 , 2 , 3 , 4 , 5  )
          THEN
               raise Program_Error;
          END IF;

          A   :=  ( 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 );
          A   :=  A(IDENT_INT_6..IDENT_INT_9)  &
                  A(IDENT_INT_8..IDENT_INT_9)  &
                  A(IDENT_INT_8..IDENT_INT_9)  &  0  &  0; 
          IF   A  /=  ( 6 , 7 , 8 , 9 , 8 , 9 , 8 , 9 , 0 , 0  )
          THEN
               raise Program_Error;
          END IF;

     END; 

END C52102B; 

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Richard Guenther]

On Sun, 8 Aug 2010, Eric Botcazou wrote:

> >   D.2544_253 = prephitmp.53_302 + 2147483647;
> >   D.2553_254 = (size_type) D.2544_253;
> 
> The signed integer overflow is introduced during the reassoc1 pass.  For the 
> attached reduced testcase, we start from:
> 
> <bb 45>:
>   D.2615_217 = L43b_216 + -1;
>   iftmp.30_218 = D.2615_217 + -2147483648;
>   D.2624_225 = (size_type) iftmp.30_218;
> 
> and we go to:
> 
> <bb 45>:
>   iftmp.30_218 = L43b_216 + 2147483647;
>   D.2624_225 = (size_type) iftmp.30_218;

Well, I remember a similar kind of problem fixed in fold - basically
you can't re-associate (a + b) + c to a + (b + c) with signed
arithmetic.  But - we can do so if reassociating constants only
as in the example above.  Because if (L43b_216 - 1) - 2147483648
doesn't overflow then L43b_216 + 2147483647 doesn't either.

So I believe this specific problem pre-exists before re-assoc.

Richard.

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Paolo Bonzini]

On 08/08/2010 04:44 AM, Richard Guenther wrote:
> arithmetic.  But - we can do so if reassociating constants only
> as in the example above.  Because if (L43b_216 - 1) - 2147483648
> doesn't overflow then L43b_216 + 2147483647 doesn't either.

Huh?

a - 1 - 2147483648 is valid if a >= 1.

a + 2147483647 is valid if a < 1.

Paolo

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Paolo Bonzini]

On 08/08/2010 04:44 AM, Richard Guenther wrote:
> arithmetic.  But - we can do so if reassociating constants only
> as in the example above.  Because if (L43b_216 - 1) - 2147483648
> doesn't overflow then L43b_216 + 2147483647 doesn't either.

Huh?

a - 1 - 2147483648 is valid if a >= 1.

a + 2147483647 is valid if a < 1.

Paolo

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Richard Guenther]

On Sun, 8 Aug 2010, Paolo Bonzini wrote:

> On 08/08/2010 04:44 AM, Richard Guenther wrote:
> > arithmetic.  But - we can do so if reassociating constants only
> > as in the example above.  Because if (L43b_216 - 1) - 2147483648
> > doesn't overflow then L43b_216 + 2147483647 doesn't either.
> 
> Huh?
> 
> a - 1 - 2147483648 is valid if a >= 1.
>
> a + 2147483647 is valid if a < 1.

Oh, indeed.  Hm.  I guess we have to be more careful with
constant-folding in reassoc ... (and it's one more reason for
me to pick up no-undefined-overflow again ...).

I guess as I have exposed the issue I have to look into it.

Richard.

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Richard Guenther]

On Sun, 8 Aug 2010, Richard Guenther wrote:

> On Sun, 8 Aug 2010, Paolo Bonzini wrote:
> 
> > On 08/08/2010 04:44 AM, Richard Guenther wrote:
> > > arithmetic.  But - we can do so if reassociating constants only
> > > as in the example above.  Because if (L43b_216 - 1) - 2147483648
> > > doesn't overflow then L43b_216 + 2147483647 doesn't either.
> > 
> > Huh?
> > 
> > a - 1 - 2147483648 is valid if a >= 1.
> >
> > a + 2147483647 is valid if a < 1.
> 
> Oh, indeed.  Hm.  I guess we have to be more careful with
> constant-folding in reassoc ... (and it's one more reason for
> me to pick up no-undefined-overflow again ...).
> 
> I guess as I have exposed the issue I have to look into it.

C testcase which already fold messes up (well, exposes bogus
IL to VRP):

extern void abort (void);
int i = 1;
int main()
{
  if ((i - 1) - (-__INT_MAX__ - 1) != (-__INT_MAX__ - 1))
    abort ();
  return 0;
}

Testcase which forwprop breaks (via fold) with -fstrict-overflow:

extern void abort (void);
int i = 1;
int main()
{
  int j = i - 1;
  j = j - (-__INT_MAX__ - 1);
  if (j != (-__INT_MAX__ - 1))
    abort ();
  return 0;
}

Bah.

Richard.

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Richard Guenther]

On Sun, 8 Aug 2010, Richard Guenther wrote:

> On Sun, 8 Aug 2010, Richard Guenther wrote:
> 
> > On Sun, 8 Aug 2010, Paolo Bonzini wrote:
> > 
> > > On 08/08/2010 04:44 AM, Richard Guenther wrote:
> > > > arithmetic.  But - we can do so if reassociating constants only
> > > > as in the example above.  Because if (L43b_216 - 1) - 2147483648
> > > > doesn't overflow then L43b_216 + 2147483647 doesn't either.
> > > 
> > > Huh?
> > > 
> > > a - 1 - 2147483648 is valid if a >= 1.
> > >
> > > a + 2147483647 is valid if a < 1.
> > 
> > Oh, indeed.  Hm.  I guess we have to be more careful with
> > constant-folding in reassoc ... (and it's one more reason for
> > me to pick up no-undefined-overflow again ...).
> > 
> > I guess as I have exposed the issue I have to look into it.
> 
> C testcase which already fold messes up (well, exposes bogus
> IL to VRP):
> 
> extern void abort (void);
> int i = 1;
> int main()
> {
>   if ((i - 1) - (-__INT_MAX__ - 1) != (-__INT_MAX__ - 1))
>     abort ();
>   return 0;
> }
> 
> Testcase which forwprop breaks (via fold) with -fstrict-overflow:
> 
> extern void abort (void);
> int i = 1;
> int main()
> {
>   int j = i - 1;
>   j = j - (-__INT_MAX__ - 1);
>   if (j != (-__INT_MAX__ - 1))
>     abort ();
>   return 0;
> }

The above needs to read j = j + (-__INT_MAX__ - 1); of course.  None
of the testcases fail though, we cover up ourselves in other passes.

I filed PR45232 and attached a prototype patch.

Richard.

Re: [PATCH] Keep lattice abstract in the SSA propagator, substitue lattice values at defs

[Eric Botcazou]

> I filed PR45232 and attached a prototype patch.

Thanks.

-- 
Eric Botcazou