[patch] for PR 27865

Zdenek Dvorak rakdver@atrey.karlin.mff.cuni.cz
Tue Aug 8 09:06:00 GMT 2006


Hello,

there are two problems in this PR.  Firstly, in adjust_range_with_scev,
we use TYPE_{MIN,MAX}_VALUE, but we do not check whether the type in
question is pointer, which leads to ICE.  This patch fixes it by using
{lower,upper}_value_in_type for pointers instead.

Secondly, we are converting [0xfffff..., +, 1] with unsigned int type to
[0xfffff...., +, 1] in pointer type.  This is incorrect and confuses
vrp and other optimizers, since this scev is wrapping, and we assume
that scevs with pointer type do not wrap.  The reason for this is a
missing test in convert_affine_scev (for types with the same precision
and signedness we automatically allow the conversion; however, we must
check that the source scev does not wrap if we require the result to be
non-wrapping).

Fixing the second bug however causes us to fail to determine scalar
evolution in many common cases -- the reason and fix (a bit hacky) for
it is described in detail in the comment before fold_used_pointer in the
patch; basically we use the fact that pointer that is dereferenced or
used in comparison must belong to some object in memory, which makes it
impossible for scev of such variable to wrap in case it is obtained as
cast from type with the same precision.

This fix in turn reveals a problem in ivopts, that may cause us to
use a pointer variable that does not point to any object in comparison
(which gives undefined result according to the c standard).  The last
piece of the patch fixes this.

Bootstrapped & regtested on i686, x86_64 and ppc-linux.

Zdenek

	PR tree-optimization/27865
	* tree-vrp.c (adjust_range_with_scev): Do not use TYPE_{MIN,MAX}_VALUE
	for pointer types.
	* tree-scalar-evolution.c (fold_used_pointer_cast, pointer_offset_p,
	fold_used_pointer, pointer_used_p): New functions.
	(analyze_scalar_evolution_1): Use fold_used_pointer.
	* tree-chrec.c (convert_affine_scev): Convert no-op casts correctly.
	* tree-ssa-loop-ivopts.c (generic_type_for): Return integral type
	for pointers.

Index: tree-vrp.c
===================================================================
*** tree-vrp.c	(revision 115923)
--- tree-vrp.c	(working copy)
*************** static void
*** 2015,2021 ****
  adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
  			tree var)
  {
!   tree init, step, chrec;
    enum ev_direction dir;
  
    /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
--- 2015,2021 ----
  adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
  			tree var)
  {
!   tree init, step, chrec, tmin, tmax, min, max, type;
    enum ev_direction dir;
  
    /* TODO.  Don't adjust anti-ranges.  An anti-range may provide
*************** adjust_range_with_scev (value_range_t *v
*** 2049,2061 ****
  				true))
      return;
  
!   if (!POINTER_TYPE_P (TREE_TYPE (init))
!       && (vr->type == VR_VARYING || vr->type == VR_UNDEFINED))
      {
        /* For VARYING or UNDEFINED ranges, just about anything we get
  	 from scalar evolutions should be better.  */
-       tree min = TYPE_MIN_VALUE (TREE_TYPE (init));
-       tree max = TYPE_MAX_VALUE (TREE_TYPE (init));
  
        if (dir == EV_DIR_DECREASES)
  	max = init;
--- 2049,2071 ----
  				true))
      return;
  
!   type = TREE_TYPE (var);
!   if (POINTER_TYPE_P (type) || !TYPE_MIN_VALUE (type))
!     tmin = lower_bound_in_type (type, type);
!   else
!     tmin = TYPE_MIN_VALUE (type);
!   if (POINTER_TYPE_P (type) || !TYPE_MAX_VALUE (type))
!     tmax = upper_bound_in_type (type, type);
!   else
!     tmax = TYPE_MAX_VALUE (type);
! 
!   if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
      {
+       min = tmin;
+       max = tmax;
+ 
        /* For VARYING or UNDEFINED ranges, just about anything we get
  	 from scalar evolutions should be better.  */
  
        if (dir == EV_DIR_DECREASES)
  	max = init;
*************** adjust_range_with_scev (value_range_t *v
*** 2064,2070 ****
  
        /* If we would create an invalid range, then just assume we
  	 know absolutely nothing.  This may be over-conservative,
! 	 but it's clearly safe.  */
        if (compare_values (min, max) == 1)
  	return;
  
--- 2074,2081 ----
  
        /* If we would create an invalid range, then just assume we
  	 know absolutely nothing.  This may be over-conservative,
! 	 but it's clearly safe, and should happen only in unreachable
!          parts of code, or for invalid programs.  */
        if (compare_values (min, max) == 1)
  	return;
  
*************** adjust_range_with_scev (value_range_t *v
*** 2072,2079 ****
      }
    else if (vr->type == VR_RANGE)
      {
!       tree min = vr->min;
!       tree max = vr->max;
  
        if (dir == EV_DIR_DECREASES)
  	{
--- 2083,2090 ----
      }
    else if (vr->type == VR_RANGE)
      {
!       min = vr->min;
!       max = vr->max;
  
        if (dir == EV_DIR_DECREASES)
  	{
*************** adjust_range_with_scev (value_range_t *v
*** 2084,2093 ****
  	      max = init;
  
  	      /* If we just created an invalid range with the minimum
! 		 greater than the maximum, take the minimum all the
! 		 way to -INF.  */
  	      if (compare_values (min, max) == 1)
! 		min = TYPE_MIN_VALUE (TREE_TYPE (min));
  	    }
  	}
        else
--- 2095,2105 ----
  	      max = init;
  
  	      /* If we just created an invalid range with the minimum
! 		 greater than the maximum, we fail conservatively.
! 		 This should happen only in unreachable
! 		 parts of code, or for invalid programs.  */
  	      if (compare_values (min, max) == 1)
! 		return;
  	    }
  	}
        else
*************** adjust_range_with_scev (value_range_t *v
*** 2097,2107 ****
  	    {
  	      min = init;
  
! 	      /* If we just created an invalid range with the minimum
! 		 greater than the maximum, take the maximum all the
! 		 way to +INF.  */
  	      if (compare_values (min, max) == 1)
! 		max = TYPE_MAX_VALUE (TREE_TYPE (max));
  	    }
  	}
  
--- 2109,2117 ----
  	    {
  	      min = init;
  
! 	      /* Again, avoid creating invalid range by failing.  */
  	      if (compare_values (min, max) == 1)
! 		return;
  	    }
  	}
  
Index: tree-scalar-evolution.c
===================================================================
*** tree-scalar-evolution.c	(revision 115923)
--- tree-scalar-evolution.c	(working copy)
*************** compute_scalar_evolution_in_loop (struct
*** 1718,1723 ****
--- 1718,1896 ----
    return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
  }
  
+ /* Folds EXPR, if it is a cast to pointer, assuming that the created
+    polynomial_chrec does not wrap.  */
+ 
+ static tree
+ fold_used_pointer_cast (tree expr)
+ {
+   tree op;
+   tree type, inner_type;
+ 
+   if (TREE_CODE (expr) != NOP_EXPR && TREE_CODE (expr) != CONVERT_EXPR)
+     return expr;
+ 
+   op = TREE_OPERAND (expr, 0);
+   if (TREE_CODE (op) != POLYNOMIAL_CHREC)
+     return expr;
+ 
+   type = TREE_TYPE (expr);
+   inner_type = TREE_TYPE (op);
+ 
+   if (!INTEGRAL_TYPE_P (inner_type)
+       || TYPE_PRECISION (inner_type) != TYPE_PRECISION (type))
+     return expr;
+ 
+   return build_polynomial_chrec (CHREC_VARIABLE (op),
+ 		chrec_convert (type, CHREC_LEFT (op), NULL_TREE),
+ 		chrec_convert (type, CHREC_RIGHT (op), NULL_TREE));
+ }
+ 
+ /* Returns true if EXPR is an expression corresponding to offset of pointer
+    in p + offset.  */
+ 
+ static bool
+ pointer_offset_p (tree expr)
+ {
+   if (TREE_CODE (expr) == INTEGER_CST)
+     return true;
+ 
+   if ((TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
+       && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))))
+     return true;
+ 
+   return false;
+ }
+ 
+ /* EXPR is a scalar evolution of a pointer that is dereferenced or used in
+    comparison.  This means that it must point to a part of some object in
+    memory, which enables us to argue about overflows and possibly simplify
+    the EXPR.  Returns the simplified value.
+ 
+    Currently, for
+ 
+    int i, n;
+    int *p;
+ 
+    for (i = -n; i < n; i++)
+      *(p + i) = ...;
+ 
+    We generate the following code (assuming that size of int and size_t is
+    4 bytes):
+ 
+    for (i = -n; i < n; i++)
+      {
+        size_t tmp1, tmp2;
+        int *tmp3, *tmp4;
+ 
+        tmp1 = (size_t) i;	(1)
+        tmp2 = 4 * tmp1;		(2)
+        tmp3 = (int *) tmp2;	(3)
+        tmp4 = p + tmp3;		(4)
+ 
+        *tmp4 = ...;
+      }
+ 
+    We in general assume that pointer arithmetics does not overflow (since its
+    behavior is undefined in that case).  One of the problems is that our
+    translation does not capture this property very well -- (int *) is
+    considered unsigned, hence the computation in (4) does overflow if i is
+    negative.
+ 
+    This impreciseness creates complications in scev analysis.  The scalar
+    evolution of i is [-n, +, 1].  Since int and size_t have the same precision
+    (in this example), and size_t is unsigned (so we do not care about
+    overflows), we succeed to derive that scev of tmp1 is [(size_t) -n, +, 1]
+    and scev of tmp2 is [4 * (size_t) -n, +, 4].  With tmp3, we run into
+    problem -- [(int *) (4 * (size_t) -n), +, 4] wraps, and since we on several
+    places assume that this is not the case for scevs with pointer type, we
+    cannot use this scev for tmp3; hence, its scev is
+    (int *) [(4 * (size_t) -n), +, 4], and scev of tmp4 is
+    p + (int *) [(4 * (size_t) -n), +, 4].  Most of the optimizers are unable to
+    work with scevs of this shape.
+ 
+    However, since tmp4 is dereferenced, all its values must belong to a single
+    object, and taking into account that the precision of int * and size_t is
+    the same, it is impossible for its scev to wrap.  Hence, we can derive that
+    its evolution is [p + (int *) (4 * (size_t) -n), +, 4], which the optimizers
+    can work with.
+ 
+    ??? Maybe we should use different representation for pointer arithmetics,
+    however that is a long-term project with a lot of potential for creating
+    bugs.  */
+ 
+ static tree
+ fold_used_pointer (tree expr)
+ {
+   tree op0, op1, new0, new1;
+   enum tree_code code = TREE_CODE (expr);
+ 
+   if (code == PLUS_EXPR
+       || code == MINUS_EXPR)
+     {
+       op0 = TREE_OPERAND (expr, 0);
+       op1 = TREE_OPERAND (expr, 1);
+ 
+       if (pointer_offset_p (op1))
+ 	{
+ 	  new0 = fold_used_pointer (op0);
+ 	  new1 = fold_used_pointer_cast (op1);
+ 	}
+       else if (code == PLUS_EXPR && pointer_offset_p (op0))
+ 	{
+ 	  new0 = fold_used_pointer_cast (op0);
+ 	  new1 = fold_used_pointer (op1);
+ 	}
+       else
+ 	return expr;
+ 
+       if (new0 == op0 && new1 == op1)
+ 	return expr;
+ 
+       if (code == PLUS_EXPR)
+ 	expr = chrec_fold_plus (TREE_TYPE (expr), new0, new1);
+       else
+ 	expr = chrec_fold_minus (TREE_TYPE (expr), new0, new1);
+ 
+       return expr;
+     }
+   else
+     return fold_used_pointer_cast (expr);
+ }
+ 
+ /* Returns true if PTR is dereferenced, or used in comparison.  */
+ 
+ static bool
+ pointer_used_p (tree ptr)
+ {
+   use_operand_p use_p;
+   imm_use_iterator imm_iter;
+   tree stmt, rhs;
+ 
+   if (get_ptr_info (ptr)->is_dereferenced)
+     return true;
+ 
+   FOR_EACH_IMM_USE_FAST (use_p, imm_iter, ptr)
+     {
+       stmt = USE_STMT (use_p);
+       if (TREE_CODE (stmt) == COND_EXPR)
+ 	return true;
+ 
+       if (TREE_CODE (stmt) != MODIFY_EXPR)
+ 	continue;
+ 
+       rhs = TREE_OPERAND (stmt, 1);
+       if (!COMPARISON_CLASS_P (rhs))
+ 	continue;
+ 
+       if (TREE_OPERAND (stmt, 0) == ptr
+ 	  || TREE_OPERAND (stmt, 1) == ptr)
+ 	return true;
+     }
+ 
+   return false;
+ }
+ 
  /* Helper recursive function.  */
  
  static tree
*************** analyze_scalar_evolution_1 (struct loop 
*** 1766,1771 ****
--- 1939,1949 ----
      {
      case MODIFY_EXPR:
        res = interpret_rhs_modify_expr (loop, def, TREE_OPERAND (def, 1), type);
+ 
+       if (POINTER_TYPE_P (type)
+ 	  && !automatically_generated_chrec_p (res)
+ 	  && pointer_used_p (var))
+ 	res = fold_used_pointer (res);
        break;
  
      case PHI_NODE:
Index: tree-chrec.c
===================================================================
*** tree-chrec.c	(revision 115923)
--- tree-chrec.c	(working copy)
*************** convert_affine_scev (struct loop *loop, 
*** 1162,1168 ****
  	 -- must_check_src_overflow is true, and the range of TYPE is superset
  	    of the range of CT -- i.e., in all cases except if CT signed and
  	    TYPE unsigned.
!          -- both CT and TYPE have the same precision and signedness.  */
        if (must_check_src_overflow)
  	{
  	  if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
--- 1162,1171 ----
  	 -- must_check_src_overflow is true, and the range of TYPE is superset
  	    of the range of CT -- i.e., in all cases except if CT signed and
  	    TYPE unsigned.
!          -- both CT and TYPE have the same precision and signedness, and we
! 	    verify instead that the source does not overflow (this may be
! 	    easier than verifying it for the result, as we may use the
! 	    information about the semantics of overflow in CT).  */
        if (must_check_src_overflow)
  	{
  	  if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
*************** convert_affine_scev (struct loop *loop, 
*** 1172,1178 ****
  	}
        else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
  	       && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
! 	must_check_rslt_overflow = false;
        else
  	must_check_rslt_overflow = true;
      }
--- 1175,1184 ----
  	}
        else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
  	       && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
! 	{
! 	  must_check_rslt_overflow = false;
! 	  must_check_src_overflow = true;
! 	}
        else
  	must_check_rslt_overflow = true;
      }
Index: tree-ssa-loop-ivopts.c
===================================================================
*** tree-ssa-loop-ivopts.c	(revision 115923)
--- tree-ssa-loop-ivopts.c	(working copy)
*************** strip_offset (tree expr, unsigned HOST_W
*** 1925,1938 ****
  }
  
  /* Returns variant of TYPE that can be used as base for different uses.
!    For integer types, we return unsigned variant of the type, which
!    avoids problems with overflows.  For pointer types, we return void *.  */
  
  static tree
  generic_type_for (tree type)
  {
    if (POINTER_TYPE_P (type))
!     return ptr_type_node;
  
    if (TYPE_UNSIGNED (type))
      return type;
--- 1925,1938 ----
  }
  
  /* Returns variant of TYPE that can be used as base for different uses.
!    We return unsigned type with the same precision, which avoids problems
!    with overflows.  */
  
  static tree
  generic_type_for (tree type)
  {
    if (POINTER_TYPE_P (type))
!     return unsigned_type_for (type);
  
    if (TYPE_UNSIGNED (type))
      return type;



More information about the Gcc-patches mailing list