[patch] for PR28411

Zdenek Dvorak rakdver@atrey.karlin.mff.cuni.cz
Fri Aug 4 13:30:00 GMT 2006


Hello,

> On Sat, 29 Jul 2006, Zdenek Dvorak wrote:
> >
> > 	PR tree-optimization/28411
> > 	* tree-ssa-loop-niter.c (derive_constant_upper_bound): Pass NULL for
> > 	the remainder argument of double_int_udiv.
> > 	* double-int.c (double_int_div, double_int_udiv, double_int_sdiv):
> > 	Return also remainder after division.
> > 	* double-int.h (double_int_div, double_int_udiv, double_int_sdiv):
> > 	Declaration changed.
> > 	* tree-ssa-loop-ivopts.c (constant_multiple_of): Returns the result
> > 	in double_int.
> > 	(get_computation_aff, get_computation_cost_at): Handle double_int
> > 	return type of constant_multiple_of.
> 
> I'd prefer that you add a new double_int_divmod if you need one, rather
> than change the div, udiv and sdiv APIs.  It makes sense to define/keep
> stable APIs that allow efficient calculation of quotients and remainders
> without the need to calculate both.
> 
> void double_int_sdivmod (double_int a, double_int b, unsigned int code,
> 			 double_int *div, double_int *mod);
> 

here is the updated version; I still do not understand why you consider
it better that way, though.

Zdenek

	PR tree-optimization/28411
	* double-int.c (double_int_div): Use double_int_divmod.
	(double_int_divmod, double_int_sdivmod, double_int_udivmod,
	double_int_mod, double_int_smod, double_int_umod): New functions.
	* double-int.h (double_int_divmod, double_int_sdivmod,
	double_int_udivmod, double_int_mod, double_int_smod, double_int_umod):
	Declare.
	* tree-ssa-loop-ivopts.c (constant_multiple_of): Returns the result
	in double_int.
	(get_computation_aff, get_computation_cost_at): Handle double_int
	return type of constant_multiple_of.

Index: double-int.c
===================================================================
*** double-int.c	(revision 115851)
--- double-int.c	(working copy)
*************** double_int_neg (double_int a)
*** 203,222 ****
  
  /* Returns A / B (computed as unsigned depending on UNS, and rounded as
     specified by CODE).  CODE is enum tree_code in fact, but double_int.h
!    must be included before tree.h.  */
  
  double_int
! double_int_div (double_int a, double_int b, bool uns, unsigned code)
  {
-   unsigned HOST_WIDE_INT rem_lo;
-   HOST_WIDE_INT rem_hi;
    double_int ret;
  
    div_and_round_double (code, uns, a.low, a.high, b.low, b.high,
! 			&ret.low, &ret.high, &rem_lo, &rem_hi);
    return ret;
  }
  
  /* The same as double_int_div with UNS = false.  */
  
  double_int
--- 203,250 ----
  
  /* Returns A / B (computed as unsigned depending on UNS, and rounded as
     specified by CODE).  CODE is enum tree_code in fact, but double_int.h
!    must be included before tree.h.  The remainder after the division is
!    stored to MOD.  */
  
  double_int
! double_int_divmod (double_int a, double_int b, bool uns, unsigned code,
! 		   double_int *mod)
  {
    double_int ret;
  
    div_and_round_double (code, uns, a.low, a.high, b.low, b.high,
! 			&ret.low, &ret.high, &mod->low, &mod->high);
    return ret;
  }
  
+ /* The same as double_int_divmod with UNS = false.  */
+ 
+ double_int
+ double_int_sdivmod (double_int a, double_int b, unsigned code, double_int *mod)
+ {
+   return double_int_divmod (a, b, false, code, mod);
+ }
+ 
+ /* The same as double_int_divmod with UNS = true.  */
+ 
+ double_int
+ double_int_udivmod (double_int a, double_int b, unsigned code, double_int *mod)
+ {
+   return double_int_divmod (a, b, true, code, mod);
+ }
+ 
+ /* Returns A / B (computed as unsigned depending on UNS, and rounded as
+    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
+    must be included before tree.h.  */
+ 
+ double_int
+ double_int_div (double_int a, double_int b, bool uns, unsigned code)
+ {
+   double_int mod;
+ 
+   return double_int_divmod (a, b, uns, code, &mod);
+ }
+ 
  /* The same as double_int_div with UNS = false.  */
  
  double_int
*************** double_int_udiv (double_int a, double_in
*** 233,238 ****
--- 261,295 ----
    return double_int_div (a, b, true, code);
  }
  
+ /* Returns A % B (computed as unsigned depending on UNS, and rounded as
+    specified by CODE).  CODE is enum tree_code in fact, but double_int.h
+    must be included before tree.h.  */
+ 
+ double_int
+ double_int_mod (double_int a, double_int b, bool uns, unsigned code)
+ {
+   double_int mod;
+ 
+   double_int_divmod (a, b, uns, code, &mod);
+   return mod;
+ }
+ 
+ /* The same as double_int_mod with UNS = false.  */
+ 
+ double_int
+ double_int_smod (double_int a, double_int b, unsigned code)
+ {
+   return double_int_mod (a, b, false, code);
+ }
+ 
+ /* The same as double_int_mod with UNS = true.  */
+ 
+ double_int
+ double_int_umod (double_int a, double_int b, unsigned code)
+ {
+   return double_int_mod (a, b, true, code);
+ }
+ 
  /* Constructs tree in type TYPE from with value given by CST.  */
  
  tree
Index: double-int.h
===================================================================
*** double-int.h	(revision 115851)
--- double-int.h	(working copy)
*************** unsigned HOST_WIDE_INT double_int_to_uhw
*** 116,121 ****
--- 116,127 ----
  double_int double_int_div (double_int, double_int, bool, unsigned);
  double_int double_int_sdiv (double_int, double_int, unsigned);
  double_int double_int_udiv (double_int, double_int, unsigned);
+ double_int double_int_mod (double_int, double_int, bool, unsigned);
+ double_int double_int_smod (double_int, double_int, unsigned);
+ double_int double_int_umod (double_int, double_int, unsigned);
+ double_int double_int_divmod (double_int, double_int, bool, unsigned, double_int *);
+ double_int double_int_sdivmod (double_int, double_int, unsigned, double_int *);
+ double_int double_int_udivmod (double_int, double_int, unsigned, double_int *);
  bool double_int_negative_p (double_int);
  int double_int_cmp (double_int, double_int, bool);
  int double_int_scmp (double_int, double_int);
Index: tree-ssa-loop-ivopts.c
===================================================================
*** tree-ssa-loop-ivopts.c	(revision 115851)
--- tree-ssa-loop-ivopts.c	(working copy)
*************** tree_int_cst_sign_bit (tree t)
*** 2554,2574 ****
    return (w >> bitno) & 1;
  }
  
! /* If we can prove that TOP = cst * BOT for some constant cst in TYPE,
!    return cst.  Otherwise return NULL_TREE.  */
  
! static tree
! constant_multiple_of (tree type, tree top, tree bot)
  {
!   tree res, mby, p0, p1;
    enum tree_code code;
!   bool negate;
  
    STRIP_NOPS (top);
    STRIP_NOPS (bot);
  
    if (operand_equal_p (top, bot, 0))
!     return build_int_cst (type, 1);
  
    code = TREE_CODE (top);
    switch (code)
--- 2554,2580 ----
    return (w >> bitno) & 1;
  }
  
! /* If we can prove that TOP = cst * BOT for some constant cst,
!    store cst to MUL and return true.  Otherwise return false.
!    The returned value is always sign-extended, regardless of the
!    signedness of TOP and BOT.  */
  
! static bool
! constant_multiple_of (tree top, tree bot, double_int *mul)
  {
!   tree mby;
    enum tree_code code;
!   double_int res, p0, p1;
!   unsigned precision = TYPE_PRECISION (TREE_TYPE (top));
  
    STRIP_NOPS (top);
    STRIP_NOPS (bot);
  
    if (operand_equal_p (top, bot, 0))
!     {
!       *mul = double_int_one;
!       return true;
!     }
  
    code = TREE_CODE (top);
    switch (code)
*************** constant_multiple_of (tree type, tree to
*** 2576,2635 ****
      case MULT_EXPR:
        mby = TREE_OPERAND (top, 1);
        if (TREE_CODE (mby) != INTEGER_CST)
! 	return NULL_TREE;
  
!       res = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
!       if (!res)
! 	return NULL_TREE;
  
!       return fold_binary_to_constant (MULT_EXPR, type, res,
! 				      fold_convert (type, mby));
  
      case PLUS_EXPR:
      case MINUS_EXPR:
!       p0 = constant_multiple_of (type, TREE_OPERAND (top, 0), bot);
!       if (!p0)
! 	return NULL_TREE;
!       p1 = constant_multiple_of (type, TREE_OPERAND (top, 1), bot);
!       if (!p1)
! 	return NULL_TREE;
  
!       return fold_binary_to_constant (code, type, p0, p1);
  
      case INTEGER_CST:
        if (TREE_CODE (bot) != INTEGER_CST)
! 	return NULL_TREE;
! 
!       bot = fold_convert (type, bot);
!       top = fold_convert (type, top);
! 
!       /* If BOT seems to be negative, try dividing by -BOT instead, and negate
! 	 the result afterwards.  */
!       if (tree_int_cst_sign_bit (bot))
! 	{
! 	  negate = true;
! 	  bot = fold_unary_to_constant (NEGATE_EXPR, type, bot);
! 	}
!       else
! 	negate = false;
! 
!       /* Ditto for TOP.  */
!       if (tree_int_cst_sign_bit (top))
! 	{
! 	  negate = !negate;
! 	  top = fold_unary_to_constant (NEGATE_EXPR, type, top);
! 	}
! 
!       if (!zero_p (fold_binary_to_constant (TRUNC_MOD_EXPR, type, top, bot)))
! 	return NULL_TREE;
  
!       res = fold_binary_to_constant (EXACT_DIV_EXPR, type, top, bot);
!       if (negate)
! 	res = fold_unary_to_constant (NEGATE_EXPR, type, res);
!       return res;
  
      default:
!       return NULL_TREE;
      }
  }
  
--- 2582,2621 ----
      case MULT_EXPR:
        mby = TREE_OPERAND (top, 1);
        if (TREE_CODE (mby) != INTEGER_CST)
! 	return false;
  
!       if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &res))
! 	return false;
  
!       *mul = double_int_sext (double_int_mul (res, tree_to_double_int (mby)),
! 			      precision);
!       return true;
  
      case PLUS_EXPR:
      case MINUS_EXPR:
!       if (!constant_multiple_of (TREE_OPERAND (top, 0), bot, &p0)
! 	  || !constant_multiple_of (TREE_OPERAND (top, 1), bot, &p1))
! 	return false;
  
!       if (code == MINUS_EXPR)
! 	p1 = double_int_neg (p1);
!       *mul = double_int_sext (double_int_add (p0, p1), precision);
!       return true;
  
      case INTEGER_CST:
        if (TREE_CODE (bot) != INTEGER_CST)
! 	return false;
  
!       p0 = double_int_sext (tree_to_double_int (bot), precision);
!       p1 = double_int_sext (tree_to_double_int (top), precision);
!       if (double_int_zero_p (p1))
! 	return false;
!       *mul = double_int_sext (double_int_sdivmod (p0, p1, FLOOR_DIV_EXPR, &res),
! 			      precision);
!       return double_int_zero_p (res);
  
      default:
!       return false;
      }
  }
  
*************** get_computation_aff (struct loop *loop,
*** 2964,2969 ****
--- 2950,2956 ----
    HOST_WIDE_INT ratioi;
    struct affine_tree_combination cbase_aff, expr_aff;
    tree cstep_orig = cstep, ustep_orig = ustep;
+   double_int rat;
  
    if (TYPE_PRECISION (utype) > TYPE_PRECISION (ctype))
      {
*************** get_computation_aff (struct loop *loop,
*** 3018,3038 ****
      }
    else
      {
!       ratio = constant_multiple_of (uutype, ustep_orig, cstep_orig);
!       if (!ratio)
  	return false;
  
        /* Ratioi is only used to detect special cases when the multiplicative
! 	 factor is 1 or -1, so if we cannot convert ratio to HOST_WIDE_INT,
! 	 we may set it to 0.  We prefer cst_and_fits_in_hwi/int_cst_value
! 	 to integer_onep/integer_all_onesp, since the former ignores
! 	 TREE_OVERFLOW.  */
!       if (cst_and_fits_in_hwi (ratio))
! 	ratioi = int_cst_value (ratio);
!       else if (integer_onep (ratio))
! 	ratioi = 1;
!       else if (integer_all_onesp (ratio))
! 	ratioi = -1;
        else
  	ratioi = 0;
      }
--- 3005,3019 ----
      }
    else
      {
!       if (!constant_multiple_of (ustep_orig, cstep_orig, &rat))
  	return false;
+       ratio = double_int_to_tree (uutype, rat);
  
        /* Ratioi is only used to detect special cases when the multiplicative
! 	 factor is 1 or -1, so if rat does not fit to HOST_WIDE_INT, we may
! 	 set it to 0.  */
!       if (double_int_fits_in_shwi_p (rat))
! 	ratioi = double_int_to_shwi (rat);
        else
  	ratioi = 0;
      }
*************** get_computation_cost_at (struct ivopts_d
*** 3753,3771 ****
      }
    else
      {
!       tree rat;
        
!       rat = constant_multiple_of (utype, ustep, cstep);
!     
!       if (!rat)
  	return INFTY;
! 
!       if (cst_and_fits_in_hwi (rat))
! 	ratio = int_cst_value (rat);
!       else if (integer_onep (rat))
! 	ratio = 1;
!       else if (integer_all_onesp (rat))
! 	ratio = -1;
        else
  	return INFTY;
      }
--- 3734,3746 ----
      }
    else
      {
!       double_int rat;
        
!       if (!constant_multiple_of (ustep, cstep, &rat))
  	return INFTY;
!     
!       if (double_int_fits_in_shwi_p (rat))
! 	ratio = double_int_to_shwi (rat);
        else
  	return INFTY;
      }



More information about the Gcc-patches mailing list