Patch ping

Patch ping

[Zdenek Dvorak]

Hello,

http://gcc.gnu.org/ml/gcc-patches/2006-01/msg00676.html
  -- patch to improve the functions to work affine combinations;  this
     patch blocks further ivopts cleanups (in particular, it keeps
     decl_rtl_to_reset alive -- I would really like to get rid of this
     ugly hack).

Zdenek

Re: Patch ping

[Roger Sayle]

On Thu, 16 Feb 2006, Zdenek Dvorak wrote:
> http://gcc.gnu.org/ml/gcc-patches/2006-01/msg00676.html
>   -- patch to improve the functions to work affine combinations;  this
>      patch blocks further ivopts cleanups (in particular, it keeps
>      decl_rtl_to_reset alive -- I would really like to get rid of this
>      ugly hack).


I'm a bit uncomfortable with the code duplication introduced by your
new double_int structure.  Similar double word arithmetic routines
are already duplicated in the tree-ssa optimizers.  The middle-end
handling of TREE_OVERFLOW/TREE_CONSTANT_OVERFLOW and representation
of INTEGER_CST, REAL_CST, CONST_INT and CONST_DOUBLE in trees and
RTL are already "weeping sores" in GCC's infrastructure.  Rather
than add another set of hacks, or get embroiled in the inevitable
clean-up, might I recommend using HOST_WIDE_INT pairs for the time
being?

Entangling your iv-opts clean-ups with the nightmare of GCC's
multi-precision integer handling might result in delaying your
changes until 4.3 or later :-(  For example it isn't clear whether
your new structure is a constructive step in the right direction.

Roger
--

Re: Patch ping

[Zdenek Dvorak]

Hello,

> On Thu, 16 Feb 2006, Zdenek Dvorak wrote:
> > http://gcc.gnu.org/ml/gcc-patches/2006-01/msg00676.html
> >   -- patch to improve the functions to work affine combinations;  this
> >      patch blocks further ivopts cleanups (in particular, it keeps
> >      decl_rtl_to_reset alive -- I would really like to get rid of this
> >      ugly hack).
> 
> 
> I'm a bit uncomfortable with the code duplication introduced by your
> new double_int structure.

what code duplication?  It just introduces a few simple wrapper functions,
so that the manipulation is simpler and the code is cleaner.

> Similar double word arithmetic routines
> are already duplicated in the tree-ssa optimizers.  The middle-end
> handling of TREE_OVERFLOW/TREE_CONSTANT_OVERFLOW and representation
> of INTEGER_CST, REAL_CST, CONST_INT and CONST_DOUBLE in trees and
> RTL are already "weeping sores" in GCC's infrastructure.  Rather
> than add another set of hacks, or get embroiled in the inevitable
> clean-up, might I recommend using HOST_WIDE_INT pairs for the time
> being?

I am really uncomfortable with this suggestion :-( Yep, it is certainly
possible; however, keeping two parts of the same object separate
strikes me as wrong design.

> Entangling your iv-opts clean-ups with the nightmare of GCC's
> multi-precision integer handling might result in delaying your
> changes until 4.3 or later :-(  For example it isn't clear whether
> your new structure is a constructive step in the right direction.

Well, as long as ivopts must handle the case of short and long integers
separately, it is very hard to make any progress in it.

Zdenek

Re: Patch ping

[Paolo Bonzini]

>> Similar double word arithmetic routines
>> are already duplicated in the tree-ssa optimizers.  The middle-end
>> handling of TREE_OVERFLOW/TREE_CONSTANT_OVERFLOW and representation
>> of INTEGER_CST, REAL_CST, CONST_INT and CONST_DOUBLE in trees and
>> RTL are already "weeping sores" in GCC's infrastructure.  Rather
>> than add another set of hacks, or get embroiled in the inevitable
>> clean-up, might I recommend using HOST_WIDE_INT pairs for the time
>> being?

While I agree on the code duplication issues, on the other hand, I like 
the struct double_int much more than HOST_WIDE_INT pairs.

Don't hold your breath, but if Zdenek's patch goes in I might work on 
using his struct double_int in fold-const.c as well.  That's probably 4.3.

Paolo

Re: Patch ping

[Roger Sayle]

On Fri, 17 Feb 2006, Paolo Bonzini wrote:
> While I agree on the code duplication issues, on the other hand, I like
> the struct double_int much more than HOST_WIDE_INT pairs.
>
> Don't hold your breath, but if Zdenek's patch goes in I might work on
> using his struct double_int in fold-const.c as well.  That's probably 4.3.

Ok, I see a plan...

The new double_int bears more than a passing similarity to tree.h's struct
tree_int_cst_lowhi.  It looks like we already have a suitable double_int,
we're just not using it as the basis of our low-level arithmetic routines.

Ok, Zdenek, it looks like the way to proceed is to break out all of
your new wrappers into their own doubleint.h and doubleint.c, and
to change tree.h:tree_int_cst.int_cst to be of type double_int as a
single preparatory patch.  For compatability with the existing usage,
you'll probably want to keep the high word signed.    Clearly these
prototypes don't belong in tree-affine.h, and I'd prefer to leave
hwint.h untouched so it can potentially be used in other projects
(generator programs?) without a hwint.c (i.e. like longlong.h).

Then as time permits, probably mostly in 4.3, we'll move over
fold-const.c, tree.c, tree-ssa and the RTL optimizers to use these new
APIs.  This can also lead into a longer term plan to disambiguate
CONST_DOUBLE in our RTL, by distinguishing CONST_DOUBLE (which should
only need two words), from a hypothetical CONST_REAL (which currently
needs about six).

Presumably folks are happy with taking and returning double_int
structures rather than pointers to them, or pairs of HWIs as is
done with the current APIs?  During the transition the pairs of
HWIs routines will remain.  I suspect that we'll end up with
two sets of low-level interfaces, for with and without over
overflow detection, with overflow being returned as a bool rather
than stored in the double_int representation.  INTEGER_CSTs then
become augmented double_int's with types, overflow, signedness,
etc...

The first patch is simple enough, it's the transition that it
prompts...

Roger
--

Re: Patch ping

[Zdenek Dvorak]

Hello,

> > While I agree on the code duplication issues, on the other hand, I like
> > the struct double_int much more than HOST_WIDE_INT pairs.
> >
> > Don't hold your breath, but if Zdenek's patch goes in I might work on
> > using his struct double_int in fold-const.c as well.  That's probably 4.3.
> 
> Ok, I see a plan...
> 
> The new double_int bears more than a passing similarity to tree.h's struct
> tree_int_cst_lowhi.  It looks like we already have a suitable double_int,
> we're just not using it as the basis of our low-level arithmetic routines.
> 
> Ok, Zdenek, it looks like the way to proceed is to break out all of
> your new wrappers into their own doubleint.h and doubleint.c, and
> to change tree.h:tree_int_cst.int_cst to be of type double_int as a
> single preparatory patch.  For compatability with the existing usage,
> you'll probably want to keep the high word signed.    Clearly these
> prototypes don't belong in tree-affine.h, and I'd prefer to leave
> hwint.h untouched so it can potentially be used in other projects
> (generator programs?) without a hwint.c (i.e. like longlong.h).

here is the proposed patch; bootstrapped & regtested on x86_64.

Zdenek

	* gengtype.c (main): Handle double_int type.
	* tree.h (struct tree_int_cst): Make type of int_cst double_int.
	* doubleint.c: New file.
	* doubleint.h: New file.
	* system.h: Include doubleint.h.
	* Makefile.in (SYSTEM_H): Include doubleint.h.
	(doubleint.o): Add.

Index: gengtype.c
===================================================================
*** gengtype.c	(revision 111309)
--- gengtype.c	(working copy)
*************** main(int ARG_UNUSED (argc), char ** ARG_
*** 3037,3042 ****
--- 3037,3043 ----
  
    do_scalar_typedef ("CUMULATIVE_ARGS", &pos);
    do_scalar_typedef ("REAL_VALUE_TYPE", &pos);
+   do_scalar_typedef ("double_int", &pos);
    do_scalar_typedef ("uint8", &pos);
    do_scalar_typedef ("jword", &pos);
    do_scalar_typedef ("JCF_u2", &pos);
Index: tree.h
===================================================================
*** tree.h	(revision 111309)
--- tree.h	(working copy)
*************** extern void omp_clause_range_check_faile
*** 1239,1251 ****
  struct tree_int_cst GTY(())
  {
    struct tree_common common;
!   /* A sub-struct is necessary here because the function `const_hash'
!      wants to scan both words as a unit and taking the address of the
!      sub-struct yields the properly inclusive bounded pointer.  */
!   struct tree_int_cst_lowhi {
!     unsigned HOST_WIDE_INT low;
!     HOST_WIDE_INT high;
!   } int_cst;
  };
  
  /* In a REAL_CST node.  struct real_value is an opaque entity, with
--- 1239,1245 ----
  struct tree_int_cst GTY(())
  {
    struct tree_common common;
!   double_int int_cst;
  };
  
  /* In a REAL_CST node.  struct real_value is an opaque entity, with
Index: doubleint.c
===================================================================
*** doubleint.c	(revision 0)
--- doubleint.c	(revision 0)
***************
*** 0 ****
--- 1,288 ----
+ /* Operations with long integers.
+    Copyright (C) 2006 Free Software Foundation, Inc.
+    
+ This file is part of GCC.
+    
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+    
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+    
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to the Free
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.  */
+ 
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ 
+ /* Constructs double_int from tree CST.  */
+ 
+ double_int
+ tree_to_double_int (tree cst)
+ {
+   return TREE_INT_CST (cst);
+ }
+ 
+ /* Restricts constant CST to the precision given by MASK.  */
+ 
+ static inline double_int
+ restrict_cst_to_precision (double_int mask, double_int cst)
+ {
+   double_int r;
+   
+   DI_LOW_SET (r, DI_LOW (cst) & DI_LOW (mask));
+   DI_HIGH_SET (r, DI_HIGH (cst) & DI_HIGH (mask));
+ 
+   return r;
+ }
+ 
+ /* Returns true if X (whose precision is given by MASK) fits in
+    HOST_WIDE_INT.  */
+ 
+ bool
+ double_int_fits_in_hwi_p (double_int mask, double_int x)
+ {
+   if (double_int_negative_p (mask, x))
+     return DI_HIGH (x) == DI_HIGH (mask);
+   else
+     return DI_HIGH (x) == 0 && (HOST_WIDE_INT) DI_LOW (x) >= 0;
+ }
+ 
+ /* Returns true if X fits in unsigned HOST_WIDE_INT.  */
+ 
+ bool
+ double_int_fits_in_unsigned_hwi_p (double_int x)
+ {
+   return DI_HIGH (x) == 0;
+ }
+ 
+ /* Returns true if SCALE is negative in precision of MASK.  */
+ 
+ bool
+ double_int_negative_p (double_int mask, double_int scale)
+ {
+   if (DI_HIGH (mask))
+     return (DI_HIGH (scale) & ~(DI_HIGH (mask) >> 1)) != 0;
+   else
+     return (DI_LOW (scale) & ~(DI_LOW (mask) >> 1)) != 0;
+ }
+ 
+ /* Returns value of X, whose precision is given by MASK.  X must satisfy
+    double_int_fits_in_hwi_p.  */
+ 
+ HOST_WIDE_INT
+ double_int_to_hwi (double_int mask, double_int x)
+ {
+   if (DI_HIGH (mask) || !double_int_negative_p (mask, x))
+     return DI_LOW (x);
+   else
+     return DI_LOW (x) | ~DI_LOW (mask);
+ }
+ 
+ /* Returns value of X.  X must satisfy double_int_fits_in_unsigned_hwi_p.  */
+ 
+ unsigned HOST_WIDE_INT
+ double_int_to_unsigned_hwi (double_int x)
+ {
+   return DI_LOW (x);
+ }
+ 
+ /* Returns A * B, truncated so that it fits into precision given by MASK.  */
+ 
+ double_int
+ double_int_mul (double_int mask, double_int a, double_int b)
+ {
+   unsigned HOST_WIDE_INT lo;
+   HOST_WIDE_INT hi;
+   double_int ret;
+ 
+   mul_double (DI_LOW (a), DI_HIGH (a),
+ 	      DI_LOW (b), DI_HIGH (b), &lo, &hi);
+   DI_LOW_SET (ret, lo);
+   DI_HIGH_SET (ret, hi);
+ 
+   return restrict_cst_to_precision (mask, ret);
+ }
+ 
+ /* Returns A + B, truncated so that it fits into precision given by MASK.  */
+ 
+ double_int
+ double_int_add (double_int mask, double_int a, double_int b)
+ {
+   unsigned HOST_WIDE_INT lo;
+   HOST_WIDE_INT hi;
+   double_int ret;
+ 
+   add_double (DI_LOW (a), DI_HIGH (a),
+ 	      DI_LOW (b), DI_HIGH (b), &lo, &hi);
+   DI_LOW_SET (ret, lo);
+   DI_HIGH_SET (ret, hi);
+ 
+   return restrict_cst_to_precision (mask, ret);
+ }
+ 
+ /* Returns -A, truncated so that it fits into precision given by MASK.  */
+ 
+ double_int
+ double_int_negate (double_int mask, double_int a)
+ {
+   unsigned HOST_WIDE_INT lo;
+   HOST_WIDE_INT hi;
+   double_int ret;
+ 
+   neg_double (DI_LOW (a), DI_HIGH (a), &lo, &hi);
+   DI_LOW_SET (ret, lo);
+   DI_HIGH_SET (ret, hi);
+ 
+   return restrict_cst_to_precision (mask, ret);
+ }
+ 
+ /* Returns A / B (computed as unsigned, rounded down).  */
+ 
+ double_int
+ double_int_divide (double_int a, double_int b)
+ {
+   unsigned HOST_WIDE_INT lo, rem_lo;
+   HOST_WIDE_INT hi, rem_hi;
+   double_int ret;
+ 
+   div_and_round_double (FLOOR_DIV_EXPR, true,
+ 			DI_LOW (a), DI_HIGH (a),
+ 			DI_LOW (b), DI_HIGH (b),
+ 			&lo, &hi, &rem_lo, &rem_hi);
+   DI_LOW_SET (ret, lo);
+   DI_HIGH_SET (ret, hi);
+ 
+   return ret;
+ }
+ 
+ /* Constructs tree in type TYPE from with value given by CST (precision of CST
+    is the same as the precision of TYPE -- in particular, it must satisfy
+    double_int_fits_to_type_p).  */
+ 
+ tree
+ double_int_to_tree (tree type, double_int cst)
+ {
+   unsigned HOST_WIDE_INT lo = DI_LOW (cst);
+   HOST_WIDE_INT hi = DI_HIGH (cst);
+   unsigned prec = TYPE_PRECISION (type);
+   bool negative;
+ 
+   if (prec > HOST_BITS_PER_WIDE_INT)
+     {
+       prec -= HOST_BITS_PER_WIDE_INT;
+       negative = (hi >> (prec - 1)) & 1;
+       if (negative)
+ 	hi |= (~(unsigned HOST_WIDE_INT) 0) << (prec - 1) << 1;
+     }
+   else
+     {
+       negative = (DI_LOW (cst) >> (prec - 1)) & 1;
+       if (negative)
+ 	{
+ 	  lo |= (~(unsigned HOST_WIDE_INT) 0) << (prec - 1) << 1;
+ 	  hi = ~(unsigned HOST_WIDE_INT) 0;
+ 	}
+     }
+ 
+   return build_int_cst_wide (type, lo, hi);
+ }
+ 
+ /* Returns true if VAL is smaller or equal to the maximal value
+    representable in TYPE.  */
+ 
+ bool
+ double_int_fits_to_type_p (tree type, double_int val)
+ {
+   unsigned prec = TYPE_PRECISION (type);
+   double_int mask = double_int_mask (TYPE_UNSIGNED (type) ? prec : prec - 1);
+ 
+   return (((DI_LOW (val) & DI_LOW (mask)) == DI_LOW (val))
+ 	  && ((DI_HIGH (val) & DI_HIGH (mask)) == DI_HIGH (val)));
+ }
+ 
+ /* Returns true if A < B, unsigned comparison.  */
+ 
+ bool
+ double_int_smaller_p (double_int a, double_int b)
+ {
+   if (DI_HIGH (a) < DI_HIGH (b))
+     return true;
+   if (DI_HIGH (a) > DI_HIGH (b))
+     return false;
+   return DI_LOW (a) < DI_LOW (b);
+ }
+ 
+ /* Splits last digit of *X in BASE and returns it.  */
+ 
+ static unsigned
+ double_int_split_digit (double_int *x, unsigned base)
+ {
+   unsigned HOST_WIDE_INT resl, reml;
+   HOST_WIDE_INT resh, remh;
+ 
+   div_and_round_double (FLOOR_DIV_EXPR, true, x->low, x->high, base, 0,
+ 			&resl, &resh, &reml, &remh);
+   x->high = resh;
+   x->low = resl;
+ 
+   return reml;
+ }
+ 
+ /* Dumps X (in precision given by MASK) to FILE.  If SIGN is true, X is
+    considered to be signed.  */
+ 
+ void
+ dump_double_int (FILE *file, double_int mask, double_int x, bool sign)
+ {
+   unsigned digits[100], n;
+   int i;
+ 
+   if (double_int_zero_p (x))
+     {
+       fprintf (file, "0");
+       return;
+     }
+ 
+   if (sign && double_int_negative_p (mask, x))
+     {
+       fprintf (file, "-");
+       x = double_int_negate (mask, x);
+     }
+ 
+   for (n = 0; !double_int_zero_p (x); n++)
+     digits[n] = double_int_split_digit (&x, 10);
+   for (i = n - 1; i >= 0; i--)
+     fprintf (file, "%u", digits[i]);
+ }
+ 
+ /* Returns a MASK for precision of PREC bits.  */
+ 
+ double_int 
+ double_int_mask (unsigned prec)
+ {
+   double_int mask;
+ 
+   if (prec > HOST_BITS_PER_WIDE_INT)
+     {
+       prec -= HOST_BITS_PER_WIDE_INT;
+       DI_HIGH_SET (mask, (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1));
+       DI_LOW_SET (mask, ~(unsigned HOST_WIDE_INT) 0);
+     }
+   else
+     {
+       DI_HIGH_SET (mask, 0);
+       DI_LOW_SET (mask, (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1));
+     }
+ 
+   return mask;
+ }
Index: doubleint.h
===================================================================
*** doubleint.h	(revision 0)
--- doubleint.h	(revision 0)
***************
*** 0 ****
--- 1,118 ----
+ /* Operations with long integers.
+    Copyright (C) 2006 Free Software Foundation, Inc.
+    
+ This file is part of GCC.
+    
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+    
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+    
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to the Free
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.  */
+ 
+ #ifndef DOUBLE_INT_H
+ #define DOUBLE_INT_H
+ 
+ /* A large integer.  The precision of the represented number is between
+    1 and 2 * HOST_BITS_PER_WIDE_INT and it must be provided in each
+    operation in form of mask that prescribes the significant bits
+    (such mask is also double_int and can be obtained using
+    double_int_mask).  Signedness is only relevant for some operations
+    (comparisons, division), in these cases the description of
+    the function states whether the numbers are assumed to be signed
+    or unsigned.  */
+ 
+ typedef struct
+ {
+   unsigned HOST_WIDE_INT low;
+   HOST_WIDE_INT high;	/* High is signed for historical reasons (it replaces
+ 			   a similar structure that was used previously).  It
+ 			   makes manipulation with the numbers more cumbersome,
+ 			   so it would be nice to change it.  */
+ } double_int;
+ #define DI_LOW(X) (X).low
+ #define DI_HIGH(X) ((unsigned HOST_WIDE_INT) (X).high)
+ #define DI_LOW_SET(X, L) ((X).low = (unsigned HOST_WIDE_INT) (L))
+ #define DI_HIGH_SET(X, L) ((X).high = (HOST_WIDE_INT) (L))
+ 
+ union tree_node;
+ 
+ union tree_node *double_int_to_tree (union tree_node *, double_int);
+ bool double_int_fits_to_type_p (union tree_node *, double_int);
+ double_int tree_to_double_int (union tree_node *tree);
+ bool double_int_fits_in_hwi_p (double_int, double_int);
+ HOST_WIDE_INT double_int_to_hwi (double_int, double_int);
+ bool double_int_fits_in_unsigned_hwi_p (double_int);
+ unsigned HOST_WIDE_INT double_int_to_unsigned_hwi (double_int);
+ double_int double_int_mul (double_int, double_int, double_int);
+ double_int double_int_add (double_int, double_int, double_int);
+ double_int double_int_negate (double_int, double_int);
+ double_int double_int_divide (double_int, double_int);
+ bool double_int_negative_p (double_int, double_int);
+ bool double_int_smaller_p (double_int, double_int);
+ void dump_double_int (FILE *, double_int, double_int, bool);
+ double_int double_int_mask (unsigned);
+ 
+ /* Constructs double_int from integer CST.  */
+ 
+ static inline double_int
+ hwi_to_double_int (HOST_WIDE_INT cst)
+ {
+   double_int r;
+   
+   DI_LOW_SET (r, cst);
+   DI_HIGH_SET (r, cst < 0 ? ~(unsigned HOST_WIDE_INT) 0 : 0);
+ 
+   return r;
+ }
+ 
+ /* Constructs mask with all bits 1.  */
+ 
+ static inline double_int
+ double_int_all (void)
+ {
+   return hwi_to_double_int (-1);
+ }
+ 
+ /* Returns true if CST is zero.  */
+ 
+ static inline bool
+ double_int_zero_p (double_int cst)
+ {
+   return DI_LOW (cst) == 0 && DI_HIGH (cst) == 0;
+ }
+ 
+ /* Returns true if CST is one.  */
+ 
+ static inline bool
+ double_int_one_p (double_int cst)
+ {
+   return DI_LOW (cst) == 1 && DI_HIGH (cst) == 0;
+ }
+ 
+ /* Returns true if CST is minus one in precision of MASK.  */
+ 
+ static inline bool
+ double_int_minus_one_p (double_int mask, double_int cst)
+ {
+   return (DI_LOW (cst) == DI_LOW (mask)
+ 	  && DI_HIGH (cst) == DI_HIGH (mask));
+ }
+ 
+ /* Returns true if CST1 == CST2.  */
+ 
+ static inline bool
+ double_int_equal_p (double_int cst1, double_int cst2)
+ {
+   return DI_LOW (cst1) == DI_LOW (cst2) && DI_HIGH (cst1) == DI_HIGH (cst2);
+ }
+ 
+ #endif /* DOUBLE_INT_H */
Index: system.h
===================================================================
*** system.h	(revision 111309)
--- system.h	(working copy)
*************** extern void fancy_abort (const char *, i
*** 609,614 ****
--- 609,616 ----
  # define FALSE false
  #endif /* !__cplusplus */
  
+ /* Get definition of double_int.  */
+ #include "doubleint.h"
  
  /* Some compilers do not allow the use of unsigned char in bitfields.  */
  #define BOOL_BITFIELD unsigned int
Index: Makefile.in
===================================================================
*** Makefile.in	(revision 111309)
--- Makefile.in	(working copy)
*************** INSN_ATTR_H = insn-attr.h $(srcdir)/insn
*** 773,779 ****
  C_COMMON_H = c-common.h $(SPLAY_TREE_H) $(CPPLIB_H) $(GGC_H)
  C_PRAGMA_H = c-pragma.h $(CPPLIB_H)
  C_TREE_H = c-tree.h $(C_COMMON_H) toplev.h $(DIAGNOSTIC_H)
! SYSTEM_H = system.h hwint.h $(srcdir)/../include/libiberty.h
  PREDICT_H = predict.h predict.def
  CPPLIB_H = $(srcdir)/../libcpp/include/line-map.h \
  	$(srcdir)/../libcpp/include/cpplib.h
--- 773,779 ----
  C_COMMON_H = c-common.h $(SPLAY_TREE_H) $(CPPLIB_H) $(GGC_H)
  C_PRAGMA_H = c-pragma.h $(CPPLIB_H)
  C_TREE_H = c-tree.h $(C_COMMON_H) toplev.h $(DIAGNOSTIC_H)
! SYSTEM_H = system.h hwint.h doubleint.h $(srcdir)/../include/libiberty.h
  PREDICT_H = predict.h predict.def
  CPPLIB_H = $(srcdir)/../libcpp/include/line-map.h \
  	$(srcdir)/../libcpp/include/cpplib.h
*************** prefix.o: prefix.c $(CONFIG_H) $(SYSTEM_
*** 1779,1784 ****
--- 1779,1786 ----
  convert.o: convert.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
     $(FLAGS_H) convert.h toplev.h langhooks.h real.h
  
+ doubleint.o: doubleint.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H)
+ 
  langhooks.o : langhooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
     $(TREE_H) toplev.h $(TREE_INLINE_H) $(RTL_H) insn-config.h $(INTEGRATE_H) \
     langhooks.h $(LANGHOOKS_DEF_H) $(FLAGS_H) $(GGC_H) $(DIAGNOSTIC_H) intl.h \

Re: Patch ping

[Roger Sayle]

Hi Zdenek,

On Tue, 21 Feb 2006, Zdenek Dvorak wrote:
>
> 	* gengtype.c (main): Handle double_int type.
> 	* tree.h (struct tree_int_cst): Make type of int_cst double_int.
> 	* doubleint.c: New file.
> 	* doubleint.h: New file.
> 	* system.h: Include doubleint.h.
> 	* Makefile.in (SYSTEM_H): Include doubleint.h.
> 	(doubleint.o): Add.

Hmmm, not quite.


> + /* A large integer.  The precision of the represented number is between
> +    1 and 2 * HOST_BITS_PER_WIDE_INT and it must be provided in each
> +    operation in form of mask that prescribes the significant bits
> +    (such mask is also double_int and can be obtained using
> +    double_int_mask).  Signedness is only relevant for some operations
> +    (comparisons, division), in these cases the description of
> +    the function states whether the numbers are assumed to be signed
> +    or unsigned.  */
> +
> + typedef struct
> + {
> +   unsigned HOST_WIDE_INT low;
> +   HOST_WIDE_INT high;	/* High is signed for historical reasons (it replaces
> + 			   a similar structure that was used previously).  It
> + 			   makes manipulation with the numbers more cumbersome,
> + 			   so it would be nice to change it.  */
> + } double_int;
> + #define DI_LOW(X) (X).low
> + #define DI_HIGH(X) ((unsigned HOST_WIDE_INT) (X).high)
> + #define DI_LOW_SET(X, L) ((X).low = (unsigned HOST_WIDE_INT) (L))
> + #define DI_HIGH_SET(X, L) ((X).high = (HOST_WIDE_INT) (L))


I believe that the last sixty years of digital computation have
decisively shown the superiority of two's complement arithmetic
for representing signed integers as binary, and convenient for
interconversion with unsigned values.  You should treat double_int
like you would a TImode.  For example, -1 should be represented by
both the high an low words containing all one bits.


+ /* Returns true if CST is minus one in precision of MASK.  */
+
+ static inline bool
+ double_int_minus_one_p (double_int mask, double_int cst)
+ {
+   return (DI_LOW (cst) == DI_LOW (mask)
+ 	  && DI_HIGH (cst) == DI_HIGH (mask));
+ }

Then you wouldn't need a mask to test for minus one!

+ /* Returns true if SCALE is negative in precision of MASK.  */
+
+ bool
+ double_int_negative_p (double_int mask, double_int scale)
+ {
+   if (DI_HIGH (mask))
+     return (DI_HIGH (scale) & ~(DI_HIGH (mask) >> 1)) != 0;
+   else
+     return (DI_LOW (scale) & ~(DI_LOW (mask) >> 1)) != 0;
+ }

And you wouldn't have to do pass in a mask to determine whether
a value is negative.

You would be able to implement a signed comparison, which is
not so mysteriously missing from from your patch.

But most importantly....

+   mul_double (DI_LOW (a), DI_HIGH (a),
+               DI_LOW (b), DI_HIGH (b), &lo, &hi);
...
+   add_double (DI_LOW (a), DI_HIGH (a),
+ 	      DI_LOW (b), DI_HIGH (b), &lo, &hi);
...
+   neg_double (DI_LOW (a), DI_HIGH (a), &lo, &hi);
...
+   div_and_round_double (FLOOR_DIV_EXPR, true,
+ 			DI_LOW (a), DI_HIGH (a),
+ 			DI_LOW (b), DI_HIGH (b),
+ 			&lo, &hi, &rem_lo, &rem_hi);

You'll now get the correct results out of all of these routines, which
assume the same sign-extended two's complement representation of
integers as used in the rest of the compiler, and the vast majority
of the rest of the planet.


The most bizarre thing is that all of the code that you want/need
to perform 2*HOST_WIDE_INT arithmetic is already in the compiler.



Perhaps I'm thinking about this all wrong.  Anyone whose done a
first-year Computer Science course would be aware of my side of
the argument above, and I'd hope its safe to say you'd be able
to predict these objections.  Maybe you could describe the benefits
of your novel approach?  Why not normalize mask to double_int_all,
which allows values to be represented independently of their
precision?


Roger
--

Re: Patch ping

[Zdenek Dvorak]

Hello,

> I believe that the last sixty years of digital computation have
> decisively shown the superiority of two's complement arithmetic
> for representing signed integers as binary, and convenient for
> interconversion with unsigned values.

yes, this is why I have chosen to use it (well, why I haven't considered
any other in the first place).

> You should treat double_int like you would a TImode.  For example, -1
> should be represented by both the high an low words containing all one
> bits.

This is quite orthogonal issue to whether to use two's complement
arithmetic or something else.  As far as I understand, this is the
main point of your objection, so I will focus on it.  There are several
basic properties I want double_int to satisfy:

1) it is possible to represent numbers with smaller precision than
   2 * HOST_BITS_PER_WIDE_INT
2) it is not neccessary to distinguish between signed and unsigned
   values in functions that perform arithmetics modulo 2^precision
   (+, -, *, negation,...)
3) each number has only one possible representation.

I will for now assume that we agree on that these are desirable; if not,
I will present my arguments on this issue in the followup mail(s).

1) and 3) leave us with basically three choices of how to represent the
numbers; avoiding long explanation, let us demonstrate these on
examples, say we want to represent 8-bit values:

-- (a):
   unsigned 127 = signed 127 = {0, 127}
   unsigned 255 = signed -1 = {0, 255}
-- (b)
   unsigned 127 = signed 127 = {0, 127}
   unsigned 255 = signed -1 = {-1, -1}
-- (c)
   unsigned 127 = signed 127 = {0, 127}
   unsigned 255 = {0,255}
   signed -1 = {-1, -1}

My choice is (a).  Your choice seems to be either (b) or (c), you are
not quite clear about it.  By property 2, it would be nice for signed
and unsigned numbers with the same precision to have the same
representation (use the same range of numbers); this leaves only (a) and
(b) as possibilities.

Regardless of the choice, because of 3) you need to have some normalization of the
results of the operation -- e.g., in representation (b), 127 + 127 = 254 = {-1, -2},
but add_double would return {0,254}.  In representation (a), -1 + -1 = -2 = {0,254},
but add_double would return {0, 510}.

For (a), this normalization is X & MASK.  For (b), it is
if (X & (1<< (prec - 1)) == 0) ? X & MASK : X | ~MASK.
Between (a) and (b), I have chosen (a) as the normalization is simpler.

> + /* Returns true if CST is minus one in precision of MASK.  */
> +
> + static inline bool
> + double_int_minus_one_p (double_int mask, double_int cst)
> + {
> +   return (DI_LOW (cst) == DI_LOW (mask)
> + 	  && DI_HIGH (cst) == DI_HIGH (mask));
> + }
> 
> Then you wouldn't need a mask to test for minus one!
>
> + /* Returns true if SCALE is negative in precision of MASK.  */
> +
> + bool
> + double_int_negative_p (double_int mask, double_int scale)
> + {
> +   if (DI_HIGH (mask))
> +     return (DI_HIGH (scale) & ~(DI_HIGH (mask) >> 1)) != 0;
> +   else
> +     return (DI_LOW (scale) & ~(DI_LOW (mask) >> 1)) != 0;
> + }
> 
> And you wouldn't have to do pass in a mask to determine whether
> a value is negative.

yes, this is about the only real advantage of the representation (b).

> You would be able to implement a signed comparison, which is
> not so mysteriously missing from from your patch.

You would still need to distinguish between signed and unsigned versions
of the comparison, at the very least for numbers whose precision is
exactly 2 * HOST_BITS_PER_WIDE_INT.

The reason I do not implement signed comparison is that I do not need it
anywhere, not because it would be somehow fundamentally harder than the
unsigned case.

> But most importantly....
> 
> +   mul_double (DI_LOW (a), DI_HIGH (a),
> +               DI_LOW (b), DI_HIGH (b), &lo, &hi);
> ...
> +   add_double (DI_LOW (a), DI_HIGH (a),
> + 	      DI_LOW (b), DI_HIGH (b), &lo, &hi);
> ...
> +   neg_double (DI_LOW (a), DI_HIGH (a), &lo, &hi);
> ...
> +   div_and_round_double (FLOOR_DIV_EXPR, true,
> + 			DI_LOW (a), DI_HIGH (a),
> + 			DI_LOW (b), DI_HIGH (b),
> + 			&lo, &hi, &rem_lo, &rem_hi);
> 
> You'll now get the correct results out of all of these routines, which
> assume the same sign-extended two's complement representation of
> integers as used in the rest of the compiler, and the vast majority
> of the rest of the planet.

Regardless of whether the representation you choose is (a), (b), or (c),
you need to do some normalization of the result.  This is simplest for
(a) -- just mask out bits outside of the precision, more complicated for
(b) -- you need to do sign extension, and even more quite complex for (c)
(you need to distinguish between the signed and unsigned cases).

Zdenek

Re: Patch ping

[Richard Henderson]

On Tue, Feb 21, 2006 at 04:43:17PM +0100, Zdenek Dvorak wrote:
> yes, this is about the only real advantage of the representation (b).

The fact that rtl uses (b) for its const_int lends support for using
that representation elsewhere.  It's surely less confusing to have 
one rule instead of two.


r~

Re: Patch ping

[Zdenek Dvorak]

Hello,

> On Tue, Feb 21, 2006 at 04:43:17PM +0100, Zdenek Dvorak wrote:
> > yes, this is about the only real advantage of the representation (b).
> 
> The fact that rtl uses (b) for its const_int lends support for using
> that representation elsewhere.  It's surely less confusing to have 
> one rule instead of two.

rtl (function immed_double_const) usses the following rules:
the function takes two HOST_WIDE_INTs i0 and i1 (where i1 corresponds to higher
bits).  Let w be precision of the mode of the constructed constant, and
s the sign bit of the represented number (i.e. the one at position
1 << (w - 1)).

If w <= HOST_BITS_PER_WIDE_INT, the functions returns just CONST_INT, not
CONST_DOUBLE.  In this case, rule (b) -- filling bits above w with s --
is used.

Suppose now w > HOST_BITS_PER_WIDE_INT.  If i1 == 0 and i0 >=0, or
i1 == -1 and i1 < 0, we return CONST_INT for i0, anyway.

Otherwise, the components i0 and i1 are put into the constant unchanged.

In particular, this means that the rtl semantics allows multiple
representations for the same number, in case
HOST_BITS_PER_WIDE_INT < w < 2 * HOST_BITS_PER_WIDE_INT.

I do not really have very strong preferences whether to use semantics
(a) or (b), as long as we do not use the semantics we use for rtl :-)
I slightly prefer (a), as

1) normalization is slightly simpler
2) it is the more senseful one if the components of double_int are
   manipulated as unsigned numbers (which I prefer as it makes it
   less likely to run into problems with undefined semantics of
   overflow for signed types).

Zdenek

Re: Patch ping

[Richard Henderson]

On Wed, Feb 22, 2006 at 12:04:37AM +0100, Zdenek Dvorak wrote:
> If w <= HOST_BITS_PER_WIDE_INT, the functions returns just CONST_INT, not
> CONST_DOUBLE.  In this case, rule (b) -- filling bits above w with s --
> is used.

Yep.

> Suppose now w > HOST_BITS_PER_WIDE_INT.  If i1 == 0 and i0 >=0, or
> i1 == -1 and i1 < 0, we return CONST_INT for i0, anyway.

Sure.  It saves memory.

> Otherwise, the components i0 and i1 are put into the constant unchanged.

Note that there exists no rtl mode for which w > HBPWI and w < 2*HBPWI.
That is, if w > HBPWI, then w == 2*HBPWI.  So the point you're trying to
make here doesn't actually apply, so rule (b) continues to hold.


r~

Re: Patch ping

[Zdenek Dvorak]

Hello,

> On Wed, Feb 22, 2006 at 12:04:37AM +0100, Zdenek Dvorak wrote:
> > If w <= HOST_BITS_PER_WIDE_INT, the functions returns just CONST_INT, not
> > CONST_DOUBLE.  In this case, rule (b) -- filling bits above w with s --
> > is used.
> 
> Yep.
> 
> > Suppose now w > HOST_BITS_PER_WIDE_INT.  If i1 == 0 and i0 >=0, or
> > i1 == -1 and i1 < 0, we return CONST_INT for i0, anyway.
> 
> Sure.  It saves memory.
> 
> > Otherwise, the components i0 and i1 are put into the constant unchanged.
> 
> Note that there exists no rtl mode for which w > HBPWI and w < 2*HBPWI.
> That is, if w > HBPWI, then w == 2*HBPWI.  So the point you're trying to
> make here doesn't actually apply, so rule (b) continues to hold.

ehm... immed_double_const would really need clean up, and pruning of
completely missleading comments... I will send patch once it passes
testing.

Anyway, here is the patch for double_ints with rule (b).

Zdenek

	* gengtype.c (main): Handle double_int type.
	* tree.h (struct tree_int_cst): Make type of int_cst double_int.
	* doubleint.c: New file.
	* doubleint.h: New file.
	* system.h: Include doubleint.h.
	* Makefile.in (SYSTEM_H): Include doubleint.
	(doubleint.o): Add.

Index: gengtype.c
===================================================================
*** gengtype.c	(revision 111309)
--- gengtype.c	(working copy)
*************** main(int ARG_UNUSED (argc), char ** ARG_
*** 3037,3042 ****
--- 3037,3043 ----
  
    do_scalar_typedef ("CUMULATIVE_ARGS", &pos);
    do_scalar_typedef ("REAL_VALUE_TYPE", &pos);
+   do_scalar_typedef ("double_int", &pos);
    do_scalar_typedef ("uint8", &pos);
    do_scalar_typedef ("jword", &pos);
    do_scalar_typedef ("JCF_u2", &pos);
Index: tree.h
===================================================================
*** tree.h	(revision 111309)
--- tree.h	(working copy)
*************** extern void omp_clause_range_check_faile
*** 1239,1251 ****
  struct tree_int_cst GTY(())
  {
    struct tree_common common;
!   /* A sub-struct is necessary here because the function `const_hash'
!      wants to scan both words as a unit and taking the address of the
!      sub-struct yields the properly inclusive bounded pointer.  */
!   struct tree_int_cst_lowhi {
!     unsigned HOST_WIDE_INT low;
!     HOST_WIDE_INT high;
!   } int_cst;
  };
  
  /* In a REAL_CST node.  struct real_value is an opaque entity, with
--- 1239,1245 ----
  struct tree_int_cst GTY(())
  {
    struct tree_common common;
!   double_int int_cst;
  };
  
  /* In a REAL_CST node.  struct real_value is an opaque entity, with
Index: doubleint.c
===================================================================
*** doubleint.c	(revision 0)
--- doubleint.c	(revision 0)
***************
*** 0 ****
--- 1,298 ----
+ /* Operations with long integers.
+    Copyright (C) 2006 Free Software Foundation, Inc.
+    
+ This file is part of GCC.
+    
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+    
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+    
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to the Free
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.  */
+ 
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ 
+ /* Restricts constant CST to the precision given by MASK.  */
+ 
+ static inline double_int
+ restrict_cst_to_precision (double_int mask, double_int cst)
+ {
+   double_int r;
+   bool negative;
+   unsigned HOST_WIDE_INT sbit, snum;
+  
+   /* Copy the sign bit to the bits outside of mask.  */
+   if (DI_HIGH (mask))
+     {
+       sbit = (DI_HIGH (mask) >> 1) + 1;
+       snum = DI_HIGH (cst);
+     }
+   else
+     {
+       sbit = (DI_LOW (mask) >> 1) + 1;
+       snum = DI_LOW (cst);
+     }
+   negative = (snum & sbit) != 0;
+ 
+   if (negative)
+     {
+       DI_LOW_SET (r, DI_LOW (cst) | ~DI_LOW (mask));
+       DI_HIGH_SET (r, DI_HIGH (cst) | ~DI_HIGH (mask));
+     }
+   else
+     {
+       DI_LOW_SET (r, DI_LOW (cst) & DI_LOW (mask));
+       DI_HIGH_SET (r, DI_HIGH (cst) & DI_HIGH (mask));
+     }
+ 
+   return r;
+ }
+ 
+ /* Zeros bits of CST outside of MASK.  */
+ 
+ static inline double_int
+ zero_excess_bits (double_int mask, double_int cst)
+ {
+   double_int r;
+  
+   DI_LOW_SET (r, DI_LOW (cst) & DI_LOW (mask));
+   DI_HIGH_SET (r, DI_HIGH (cst) & DI_HIGH (mask));
+ 
+   return r;
+ }
+ 
+ /* Constructs double_int from tree CST.  */
+ 
+ double_int
+ tree_to_double_int (tree cst)
+ {
+   tree type = TREE_TYPE (cst);
+   double_int mask = double_int_mask (TYPE_PRECISION (type));
+   return restrict_cst_to_precision (mask, TREE_INT_CST (cst));
+ }
+ 
+ /* Returns true if X fits in HOST_WIDE_INT.  */
+ 
+ bool
+ double_int_fits_in_hwi_p (double_int x)
+ {
+   return ((DI_HIGH (x) == 0 && (HOST_WIDE_INT) DI_LOW (x) >= 0)
+ 	  || (DI_HIGH (x) == ALL_ONES && (HOST_WIDE_INT) DI_LOW (x) < 0));
+ }
+ 
+ /* Returns true if X fits in unsigned HOST_WIDE_INT.  */
+ 
+ bool
+ double_int_fits_in_unsigned_hwi_p (double_int x)
+ {
+   return DI_HIGH (x) == 0;
+ }
+ 
+ /* Returns true if SCALE is negative.  */
+ 
+ bool
+ double_int_negative_p (double_int scale)
+ {
+   return (HOST_WIDE_INT) DI_HIGH (scale) < 0;
+ }
+ 
+ /* Returns value of X as a signed number.  X must satisfy
+    double_int_fits_in_hwi_p.  */
+ 
+ HOST_WIDE_INT
+ double_int_to_hwi (double_int x)
+ {
+   return DI_LOW (x);
+ }
+ 
+ /* Returns value of X as an unsigned number.  X must satisfy
+    double_int_fits_in_unsigned_hwi_p.  */
+ 
+ unsigned HOST_WIDE_INT
+ double_int_to_unsigned_hwi (double_int x)
+ {
+   return DI_LOW (x);
+ }
+ 
+ /* Returns A * B, in precision given by MASK.  */
+ 
+ double_int
+ double_int_mul (double_int mask, double_int a, double_int b)
+ {
+   unsigned HOST_WIDE_INT lo;
+   HOST_WIDE_INT hi;
+   double_int ret;
+ 
+   mul_double (DI_LOW (a), DI_HIGH (a),
+ 	      DI_LOW (b), DI_HIGH (b), &lo, &hi);
+   DI_LOW_SET (ret, lo);
+   DI_HIGH_SET (ret, hi);
+ 
+   return restrict_cst_to_precision (mask, ret);
+ }
+ 
+ /* Returns A + B, in precision given by MASK.  */
+ 
+ double_int
+ double_int_add (double_int mask, double_int a, double_int b)
+ {
+   unsigned HOST_WIDE_INT lo;
+   HOST_WIDE_INT hi;
+   double_int ret;
+ 
+   add_double (DI_LOW (a), DI_HIGH (a),
+ 	      DI_LOW (b), DI_HIGH (b), &lo, &hi);
+   DI_LOW_SET (ret, lo);
+   DI_HIGH_SET (ret, hi);
+ 
+   return restrict_cst_to_precision (mask, ret);
+ }
+ 
+ /* Returns -A, in precision given by MASK.  */
+ 
+ double_int
+ double_int_negate (double_int mask, double_int a)
+ {
+   unsigned HOST_WIDE_INT lo;
+   HOST_WIDE_INT hi;
+   double_int ret;
+ 
+   neg_double (DI_LOW (a), DI_HIGH (a), &lo, &hi);
+   DI_LOW_SET (ret, lo);
+   DI_HIGH_SET (ret, hi);
+ 
+   return restrict_cst_to_precision (mask, ret);
+ }
+ 
+ /* Returns A / B (computed as unsigned in precision given by MASK, rounded
+    down).  */
+ 
+ double_int
+ double_int_divide (double_int mask, double_int a, double_int b)
+ {
+   unsigned HOST_WIDE_INT lo, rem_lo;
+   HOST_WIDE_INT hi, rem_hi;
+   double_int ret;
+ 
+   a = zero_excess_bits (mask, a);
+   b = zero_excess_bits (mask, b);
+   div_and_round_double (FLOOR_DIV_EXPR, true,
+ 			DI_LOW (a), DI_HIGH (a),
+ 			DI_LOW (b), DI_HIGH (b),
+ 			&lo, &hi, &rem_lo, &rem_hi);
+   DI_LOW_SET (ret, lo);
+   DI_HIGH_SET (ret, hi);
+ 
+   return restrict_cst_to_precision (mask, ret);
+ }
+ 
+ /* Constructs tree in type TYPE from with value given by CST (precision of CST
+    is the same as the precision of TYPE).  */
+ 
+ tree
+ double_int_to_tree (tree type, double_int cst)
+ {
+   unsigned HOST_WIDE_INT lo = DI_LOW (cst);
+   HOST_WIDE_INT hi = DI_HIGH (cst);
+ 
+   if (TYPE_UNSIGNED (type))
+     cst = zero_excess_bits (double_int_mask (TYPE_PRECISION (type)), cst);
+   return build_int_cst_wide (type, lo, hi);
+ }
+ 
+ /* Returns true if A < B, unsigned comparison, in precision given by MASK.  */
+ 
+ bool
+ double_int_smaller_p (double_int mask, double_int a, double_int b)
+ {
+   a = zero_excess_bits (mask, a);
+   b = zero_excess_bits (mask, b);
+   if (DI_HIGH (a) < DI_HIGH (b))
+     return true;
+   if (DI_HIGH (a) > DI_HIGH (b))
+     return false;
+   return DI_LOW (a) < DI_LOW (b);
+ }
+ 
+ /* Splits last digit of *X (taken as unsigned in precision
+    of 2 * HOST_BITS_PER_WIDE_INT bits) in BASE and returns it.  */
+ 
+ static unsigned
+ double_int_split_digit (double_int *x, unsigned base)
+ {
+   unsigned HOST_WIDE_INT resl, reml;
+   HOST_WIDE_INT resh, remh;
+ 
+   div_and_round_double (FLOOR_DIV_EXPR, true, x->low, x->high, base, 0,
+ 			&resl, &resh, &reml, &remh);
+   x->high = resh;
+   x->low = resl;
+ 
+   return reml;
+ }
+ 
+ /* Dumps X (in precision given by MASK) to FILE.  If SIGN is true, X is
+    considered to be signed.  */
+ 
+ void
+ dump_double_int (FILE *file, double_int mask, double_int x, bool sign)
+ {
+   unsigned digits[100], n;
+   int i;
+ 
+   if (double_int_zero_p (x))
+     {
+       fprintf (file, "0");
+       return;
+     }
+ 
+   if (double_int_negative_p (x))
+     {
+       if (sign)
+ 	{
+ 	  fprintf (file, "-");
+ 	  x = double_int_negate (mask, x);
+ 	}
+       else
+ 	x = zero_excess_bits (mask, x);
+     }
+ 
+   for (n = 0; !double_int_zero_p (x); n++)
+     digits[n] = double_int_split_digit (&x, 10);
+   for (i = n - 1; i >= 0; i--)
+     fprintf (file, "%u", digits[i]);
+ }
+ 
+ /* Returns a MASK for precision of PREC bits.  */
+ 
+ double_int 
+ double_int_mask (unsigned prec)
+ {
+   double_int mask;
+ 
+   if (prec > HOST_BITS_PER_WIDE_INT)
+     {
+       prec -= HOST_BITS_PER_WIDE_INT;
+       DI_HIGH_SET (mask, (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1));
+       DI_LOW_SET (mask, ~(unsigned HOST_WIDE_INT) 0);
+     }
+   else
+     {
+       DI_HIGH_SET (mask, 0);
+       DI_LOW_SET (mask, (((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1));
+     }
+ 
+   return mask;
+ }
Index: doubleint.h
===================================================================
*** doubleint.h	(revision 0)
--- doubleint.h	(revision 0)
***************
*** 0 ****
--- 1,126 ----
+ /* Operations with long integers.
+    Copyright (C) 2006 Free Software Foundation, Inc.
+    
+ This file is part of GCC.
+    
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+    
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+    
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to the Free
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.  */
+ 
+ #ifndef DOUBLE_INT_H
+ #define DOUBLE_INT_H
+ 
+ /* A large integer.  The precision of the represented number is between
+    1 and 2 * HOST_BITS_PER_WIDE_INT and it must be provided in each
+    operation in form of mask that prescribes the significant bits
+    (such mask is also double_int and can be obtained using
+    double_int_mask).  Signedness is only relevant for some operations
+    (comparisons, division), in these cases the description of
+    the function states whether the numbers are assumed to be signed
+    or unsigned.  The bits outside of the precision of the number are
+    set to be equal to the sign bit, for compatibility with rtl
+    representation (and tree representation of numbers in signed types;
+    in unsigned ones, such bits are zeroed).  */
+ 
+ typedef struct
+ {
+   unsigned HOST_WIDE_INT low;
+   HOST_WIDE_INT high;	/* High is signed for historical reasons (it replaces
+ 			   a similar structure that was used previously).  It
+ 			   makes manipulation with the numbers more cumbersome,
+ 			   so it would be nice to change it.  */
+ } double_int;
+ #define DI_LOW(X) (X).low
+ #define DI_HIGH(X) ((unsigned HOST_WIDE_INT) (X).high)
+ #define DI_LOW_SET(X, L) ((X).low = (unsigned HOST_WIDE_INT) (L))
+ #define DI_HIGH_SET(X, L) ((X).high = (HOST_WIDE_INT) (L))
+ #define ALL_ONES (~((unsigned HOST_WIDE_INT) 0))
+ 
+ union tree_node;
+ 
+ union tree_node *double_int_to_tree (union tree_node *, double_int);
+ double_int tree_to_double_int (union tree_node *tree);
+ bool double_int_fits_in_hwi_p (double_int);
+ HOST_WIDE_INT double_int_to_hwi (double_int);
+ bool double_int_fits_in_unsigned_hwi_p (double_int);
+ unsigned HOST_WIDE_INT double_int_to_unsigned_hwi (double_int);
+ double_int double_int_mul (double_int, double_int, double_int);
+ double_int double_int_add (double_int, double_int, double_int);
+ double_int double_int_negate (double_int, double_int);
+ double_int double_int_divide (double_int, double_int, double_int);
+ bool double_int_negative_p (double_int);
+ bool double_int_smaller_p (double_int, double_int, double_int);
+ void dump_double_int (FILE *, double_int, double_int, bool);
+ double_int double_int_mask (unsigned);
+ 
+ /* Constructs double_int from integer CST.  Note that this number may need to
+    be masked for a given precison in order to be valid.  */
+ 
+ static inline double_int
+ hwi_to_double_int (HOST_WIDE_INT cst)
+ {
+   double_int r;
+   
+   DI_LOW_SET (r, cst);
+   DI_HIGH_SET (r, cst < 0 ? ALL_ONES : 0);
+ 
+   return r;
+ }
+ 
+ /* Constructs mask with all bits 1.  */
+ 
+ static inline double_int
+ double_int_all (void)
+ {
+   double_int r;
+ 
+   DI_LOW_SET (r, ALL_ONES);
+   DI_HIGH_SET (r, ALL_ONES);
+ 
+   return r;
+ }
+ 
+ /* Returns true if CST is zero.  */
+ 
+ static inline bool
+ double_int_zero_p (double_int cst)
+ {
+   return DI_LOW (cst) == 0 && DI_HIGH (cst) == 0;
+ }
+ 
+ /* Returns true if CST is one.  */
+ 
+ static inline bool
+ double_int_one_p (double_int cst)
+ {
+   return DI_LOW (cst) == 1 && DI_HIGH (cst) == 0;
+ }
+ 
+ /* Returns true if CST is minus one.  */
+ 
+ static inline bool
+ double_int_minus_one_p (double_int cst)
+ {
+   return (DI_LOW (cst) == ALL_ONES && DI_HIGH (cst) == ALL_ONES);
+ }
+ 
+ /* Returns true if CST1 == CST2.  */
+ 
+ static inline bool
+ double_int_equal_p (double_int cst1, double_int cst2)
+ {
+   return DI_LOW (cst1) == DI_LOW (cst2) && DI_HIGH (cst1) == DI_HIGH (cst2);
+ }
+ 
+ #endif /* DOUBLE_INT_H */
Index: system.h
===================================================================
*** system.h	(revision 111309)
--- system.h	(working copy)
*************** extern void fancy_abort (const char *, i
*** 609,614 ****
--- 609,616 ----
  # define FALSE false
  #endif /* !__cplusplus */
  
+ /* Get definition of double_int.  */
+ #include "doubleint.h"
  
  /* Some compilers do not allow the use of unsigned char in bitfields.  */
  #define BOOL_BITFIELD unsigned int
Index: Makefile.in
===================================================================
*** Makefile.in	(revision 111309)
--- Makefile.in	(working copy)
*************** INSN_ATTR_H = insn-attr.h $(srcdir)/insn
*** 773,779 ****
  C_COMMON_H = c-common.h $(SPLAY_TREE_H) $(CPPLIB_H) $(GGC_H)
  C_PRAGMA_H = c-pragma.h $(CPPLIB_H)
  C_TREE_H = c-tree.h $(C_COMMON_H) toplev.h $(DIAGNOSTIC_H)
! SYSTEM_H = system.h hwint.h $(srcdir)/../include/libiberty.h
  PREDICT_H = predict.h predict.def
  CPPLIB_H = $(srcdir)/../libcpp/include/line-map.h \
  	$(srcdir)/../libcpp/include/cpplib.h
--- 773,779 ----
  C_COMMON_H = c-common.h $(SPLAY_TREE_H) $(CPPLIB_H) $(GGC_H)
  C_PRAGMA_H = c-pragma.h $(CPPLIB_H)
  C_TREE_H = c-tree.h $(C_COMMON_H) toplev.h $(DIAGNOSTIC_H)
! SYSTEM_H = system.h hwint.h doubleint.h $(srcdir)/../include/libiberty.h
  PREDICT_H = predict.h predict.def
  CPPLIB_H = $(srcdir)/../libcpp/include/line-map.h \
  	$(srcdir)/../libcpp/include/cpplib.h
*************** prefix.o: prefix.c $(CONFIG_H) $(SYSTEM_
*** 1779,1784 ****
--- 1779,1786 ----
  convert.o: convert.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
     $(FLAGS_H) convert.h toplev.h langhooks.h real.h
  
+ doubleint.o: doubleint.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H)
+ 
  langhooks.o : langhooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
     $(TREE_H) toplev.h $(TREE_INLINE_H) $(RTL_H) insn-config.h $(INTEGRATE_H) \
     langhooks.h $(LANGHOOKS_DEF_H) $(FLAGS_H) $(GGC_H) $(DIAGNOSTIC_H) intl.h \

[patch] double_int

[Zdenek Dvorak]

Hello,

this patch implements double_int type (for representing long integers),
that should in the long run enable us to handle long integer arithmetics
in both tree and rtl optimizers in cleaner and more consistent way.
See http://gcc.gnu.org/ml/gcc-patches/2006-02/msg01431.html and
followups for the original proposal and some discussions.

I have agreed with Roger on the following implementation of double_int.
The most important change wrto the original design is that the functions
only compute with numbers with 2*HOST_BITS_PER_WIDE_INT bits (i.e., the
functions no longer take the arguments that specify the precision of the
operands) -- the users that need to compute with numbers of smaller
precision must call double_int_ext operation that will normalize the
number (fill in the bits over the precision either with zero or the sign
bit, depending on the signedness).

Comments (not neccessarily regarding just this change)?

Bootstrapped & regtested on i686.

Zdenek

	* gengtype.c (main): Handle double_int type.
	* tree.h (struct tree_int_cst): Make type of int_cst double_int.
	* double-int.c: New file.
	* double-int.h: New file.
	* system.h: Include doubleint.h.
	* Makefile.in (SYSTEM_H): Include double-int.h.
	(double-int.o): Add.

Index: gengtype.c
===================================================================
*** gengtype.c	(revision 111507)
--- gengtype.c	(working copy)
*************** main(int ARG_UNUSED (argc), char ** ARG_
*** 3037,3042 ****
--- 3037,3043 ----
  
    do_scalar_typedef ("CUMULATIVE_ARGS", &pos);
    do_scalar_typedef ("REAL_VALUE_TYPE", &pos);
+   do_scalar_typedef ("double_int", &pos);
    do_scalar_typedef ("uint8", &pos);
    do_scalar_typedef ("jword", &pos);
    do_scalar_typedef ("JCF_u2", &pos);
Index: tree.h
===================================================================
*** tree.h	(revision 111507)
--- tree.h	(working copy)
*************** extern void omp_clause_range_check_faile
*** 1239,1251 ****
  struct tree_int_cst GTY(())
  {
    struct tree_common common;
!   /* A sub-struct is necessary here because the function `const_hash'
!      wants to scan both words as a unit and taking the address of the
!      sub-struct yields the properly inclusive bounded pointer.  */
!   struct tree_int_cst_lowhi {
!     unsigned HOST_WIDE_INT low;
!     HOST_WIDE_INT high;
!   } int_cst;
  };
  
  /* In a REAL_CST node.  struct real_value is an opaque entity, with
--- 1239,1245 ----
  struct tree_int_cst GTY(())
  {
    struct tree_common common;
!   double_int int_cst;
  };
  
  /* In a REAL_CST node.  struct real_value is an opaque entity, with
Index: double-int.c
===================================================================
*** double-int.c	(revision 0)
--- double-int.c	(revision 0)
***************
*** 0 ****
--- 1,344 ----
+ /* Operations with long integers.
+    Copyright (C) 2006 Free Software Foundation, Inc.
+    
+ This file is part of GCC.
+    
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+    
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+    
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to the Free
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.  */
+ 
+ #include "config.h"
+ #include "system.h"
+ #include "coretypes.h"
+ #include "tm.h"
+ #include "tree.h"
+ 
+ /* Returns mask for PREC bits.  */
+ 
+ static inline double_int
+ double_int_mask (unsigned prec)
+ {
+   unsigned HOST_WIDE_INT m;
+   double_int mask;
+ 
+   if (prec > HOST_BITS_PER_WIDE_INT)
+     {
+       prec -= HOST_BITS_PER_WIDE_INT;
+       m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
+       mask.high = (HOST_WIDE_INT) m;
+       mask.low = ALL_ONES;
+     }
+   else
+     {
+       mask.high = 0;
+       mask.low = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1;
+     }
+ 
+   return mask;
+ }
+ 
+ /* Clears the bits of CST over the precision PREC.  If UNS is false, the bits
+    outside of the precision are set to the sign bit (i.e., the PREC-th one),
+    otherwise they are set to zero.
+  
+    This corresponds to returning the value represented by PREC lowermost bits
+    of CST, with the given signedness.  */
+ 
+ double_int
+ double_int_ext (double_int cst, unsigned prec, bool uns)
+ {
+   if (uns)
+     return double_int_zext (cst, prec);
+   else
+     return double_int_sext (cst, prec);
+ }
+ 
+ /* The same as double_int_ext with UNS = true.  */
+ 
+ double_int
+ double_int_zext (double_int cst, unsigned prec)
+ {
+   double_int mask = double_int_mask (prec);
+   double_int r;
+ 
+   r.low = cst.low & ~mask.low;
+   r.high = cst.high & ~mask.high;
+ 
+   return r;
+ }
+ 
+ /* The same as double_int_ext with UNS = false.  */
+ 
+ double_int
+ double_int_sext (double_int cst, unsigned prec)
+ {
+   double_int mask = double_int_mask (prec);
+   double_int r;
+   unsigned HOST_WIDE_INT snum;
+ 
+   if (prec <= HOST_BITS_PER_WIDE_INT)
+     snum = cst.low;
+   else
+     {
+       prec -= HOST_BITS_PER_WIDE_INT;
+       snum = (unsigned HOST_WIDE_INT) cst.high;
+     }
+   if (((snum >> (prec - 1)) & 1) == 1)
+     {
+       r.low = cst.low | mask.low;
+       r.high = cst.high | mask.high;
+     }
+   else
+     {
+       r.low = cst.low & ~mask.low;
+       r.high = cst.high & ~mask.high;
+     } 
+ 
+   return r;
+ }
+ 
+ /* Constructs long integer from tree CST.  The extra bits over the precision of
+    the number are filled with sign bit if CST is signed, and with zeros if it
+    is unsigned.  */
+ 
+ double_int
+ tree_to_double_int (tree cst)
+ {
+   /* We do not need to call double_int_restrict here to ensure the semantics as
+      described, as this is the default one for trees.  */
+   return TREE_INT_CST (cst);
+ }
+ 
+ /* Returns true if CST fits in unsigned HOST_WIDE_INT.  */
+ 
+ bool
+ double_int_fits_in_uhwi_p (double_int cst)
+ {
+   return cst.high == 0;
+ }
+ 
+ /* Returns true if CST fits in signed HOST_WIDE_INT.  */
+ 
+ bool
+ double_int_fits_in_shwi_p (double_int cst)
+ {
+   if (cst.high == 0)
+     return (HOST_WIDE_INT) cst.low >= 0;
+   else if (cst.high == -1)
+     return (HOST_WIDE_INT) cst.low < 0;
+   else
+     return false;
+ }
+ 
+ /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in
+    unsigned HOST_WIDE_INT if UNS is true.  */
+ 
+ bool
+ double_int_fits_in_hwi_p (double_int cst, bool uns)
+ {
+   if (uns)
+     return double_int_fits_in_uhwi_p (cst);
+   else
+     return double_int_fits_in_shwi_p (cst);
+ }
+ 
+ /* Returns value of CST as a signed number.  CST must satisfy
+    double_int_fits_in_shwi_p.  */
+ 
+ HOST_WIDE_INT
+ double_int_to_shwi (double_int cst)
+ {
+   return (HOST_WIDE_INT) cst.low;
+ }
+ 
+ /* Returns value of CST as an unsigned number.  CST must satisfy
+    double_int_fits_in_uhwi_p.  */
+ 
+ unsigned HOST_WIDE_INT
+ double_int_to_uhwi (double_int cst)
+ {
+   return cst.low;
+ }
+ 
+ /* Returns A * B.  */
+ 
+ double_int
+ double_int_mul (double_int a, double_int b)
+ {
+   double_int ret;
+   mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
+   return ret;
+ }
+ 
+ /* Returns A + B.  */
+ 
+ double_int
+ double_int_add (double_int a, double_int b)
+ {
+   double_int ret;
+   add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high);
+   return ret;
+ }
+ 
+ /* Returns -A.  */
+ 
+ double_int
+ double_int_neg (double_int a)
+ {
+   double_int ret;
+   neg_double (a.low, a.high, &ret.low, &ret.high);
+   return ret;
+ }
+ 
+ /* 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
+ double_int_sdiv (double_int a, double_int b, unsigned code)
+ {
+   return double_int_div (a, b, false, code);
+ }
+ 
+ /* The same as double_int_div with UNS = true.  */
+ 
+ double_int
+ double_int_udiv (double_int a, double_int b, unsigned code)
+ {
+   return double_int_div (a, b, true, code);
+ }
+ 
+ /* Constructs tree in type TYPE from with value given by CST.  */
+ 
+ tree
+ double_int_to_tree (tree type, double_int cst)
+ {
+   cst = double_int_ext (cst, TYPE_PRECISION (type), TYPE_UNSIGNED (type));
+ 
+   return build_int_cst_wide (type, cst.low, cst.high);
+ }
+ 
+ /* Returns true if CST is negative.  Of course, CST is considered to
+    be signed.  */
+ 
+ bool
+ double_int_negative_p (double_int cst)
+ {
+   return cst.high < 0;
+ }
+ 
+ /* Returns -1 if A < B, 0 if A == B and 1 if A > B.  Signedness of the
+    comparison is given by UNS.  */
+ 
+ int
+ double_int_cmp (double_int a, double_int b, bool uns)
+ {
+   if (uns)
+     return double_int_ucmp (a, b);
+   else
+     return double_int_scmp (a, b);
+ }
+ 
+ /* Compares two unsigned values A and B.  Returns -1 if A < B, 0 if A == B,
+    and 1 if A > B.  */
+ 
+ int
+ double_int_ucmp (double_int a, double_int b)
+ {
+   if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high)
+     return -1;
+   if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high)
+     return 1;
+   if (a.low < b.low)
+     return -1;
+   if (a.low > b.low)
+     return 1;
+ 
+   return 0;
+ }
+ 
+ /* Compares two signed values A and B.  Returns -1 if A < B, 0 if A == B,
+    and 1 if A > B.  */
+ 
+ int
+ double_int_scmp (double_int a, double_int b)
+ {
+   if (a.high < b.high)
+     return -1;
+   if (a.high > b.high)
+     return 1;
+   if ((HOST_WIDE_INT) a.low < (HOST_WIDE_INT) b.low)
+     return -1;
+   if ((HOST_WIDE_INT) a.low > (HOST_WIDE_INT) b.low)
+     return 1;
+ 
+   return 0;
+ }
+ 
+ /* Splits last digit of *CST (taken as unsigned) in BASE and returns it.  */
+ 
+ static unsigned
+ double_int_split_digit (double_int *cst, unsigned base)
+ {
+   unsigned HOST_WIDE_INT resl, reml;
+   HOST_WIDE_INT resh, remh;
+ 
+   div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0,
+ 			&resl, &resh, &reml, &remh);
+   cst->high = resh;
+   cst->low = resl;
+ 
+   return reml;
+ }
+ 
+ /* Dumps CST to FILE.  If UNS is true, CST is considered to be unsigned,
+    otherwise it is signed.  */
+ 
+ void
+ dump_double_int (FILE *file, double_int cst, bool uns)
+ {
+   unsigned digits[100], n;
+   int i;
+ 
+   if (double_int_zero_p (cst))
+     {
+       fprintf (file, "0");
+       return;
+     }
+ 
+   if (!uns && double_int_negative_p (cst))
+     {
+       fprintf (file, "-");
+       cst = double_int_neg (cst);
+     }
+ 
+   for (n = 0; !double_int_zero_p (cst); n++)
+     digits[n] = double_int_split_digit (&cst, 10);
+   for (i = n - 1; i >= 0; i--)
+     fprintf (file, "%u", digits[i]);
+ }
Index: double-int.h
===================================================================
*** double-int.h	(revision 0)
--- double-int.h	(revision 0)
***************
*** 0 ****
--- 1,169 ----
+ /* Operations with long integers.
+    Copyright (C) 2006 Free Software Foundation, Inc.
+    
+ This file is part of GCC.
+    
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by the
+ Free Software Foundation; either version 2, or (at your option) any
+ later version.
+    
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ for more details.
+    
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING.  If not, write to the Free
+ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.  */
+ 
+ #ifndef DOUBLE_INT_H
+ #define DOUBLE_INT_H
+ 
+ /* A large integer is currently represented as a pair of HOST_WIDE_INTs.
+    It therefore represents a number with precision of
+    2 * HOST_BITS_PER_WIDE_INT bits (it is however possible that the
+    internal representation will change, if numbers with greater precision
+    are needed, so the users should not rely on it).  The representation does
+    not contain any information about signedness of the represented value, so
+    it can be used to represent both signed and unsigned numbers.  For
+    operations where the results depend on signedness (division, comparisons),
+    it must be specified separately.  For each such operation, there are three
+    versions of the function -- double_int_op, that takes an extra UNS argument
+    giving the signedness of the values, and double_int_sop and double_int_uop
+    that stand for its specializations for signed and unsigned values.
+ 
+    You may also represent with numbers in smaller precision using double_int.
+    You however need to use double_int_ext (that fills in the bits of the
+    number over the prescribed precision with zeros or with the sign bit) before
+    operations that do not perform arithmetics modulo 2^precision (comparisons,
+    division), and possibly before storing the results, if you want to keep
+    them in some canonical form).  In general, the signedness of double_int_ext
+    should match the signedness of the operation.
+ 
+    ??? The components of double_int differ in signedness mostly for
+    historical reasons (they replace an older structure used to represent
+    numbers with precision wigher than HOST_WIDE_INT).  It might be less
+    confusing to have them both signed or both unsigned.  */
+ 
+ typedef struct
+ {
+   unsigned HOST_WIDE_INT low;
+   HOST_WIDE_INT high;
+ } double_int;
+ 
+ union tree_node;
+ 
+ /* Constructors and conversions.  */
+ 
+ union tree_node *double_int_to_tree (union tree_node *, double_int);
+ double_int tree_to_double_int (union tree_node *tree);
+ 
+ /* Constructs double_int from integer CST.  The bits over the precision of
+    HOST_WIDE_INT are filled with the sign bit.  */
+ 
+ static inline double_int
+ shwi_to_double_int (HOST_WIDE_INT cst)
+ {
+   double_int r;
+   
+   r.low = (unsigned HOST_WIDE_INT) cst;
+   r.high = cst < 0 ? -1 : 0;
+ 
+   return r;
+ }
+ 
+ /* Some useful constants.  */
+ 
+ #define double_int_minus_one (shwi_to_double_int (-1))
+ #define double_int_zero (shwi_to_double_int (0))
+ #define double_int_one (shwi_to_double_int (1))
+ #define double_int_two (shwi_to_double_int (2))
+ #define double_int_ten (shwi_to_double_int (10))
+ 
+ /* Constructs double_int from unsigned integer CST.  The bits over the
+    precision of HOST_WIDE_INT are filled with zeros.  */
+ 
+ static inline double_int
+ uhwi_to_double_int (unsigned HOST_WIDE_INT cst)
+ {
+   double_int r;
+   
+   r.low = cst;
+   r.high = 0;
+ 
+   return r;
+ }
+ 
+ /* The following operations perform arithmetics modulo 2^precision,
+    so you do not need to call double_int_ext between them, even if
+    you are representing numbers with precision less than
+    2 * HOST_BITS_PER_WIDE_INT bits.  */
+ 
+ double_int double_int_mul (double_int, double_int);
+ double_int double_int_add (double_int, double_int);
+ double_int double_int_neg (double_int);
+ 
+ /* You must ensure that double_int_ext is called on the operands
+    of the following operations, if the precision of the numbers
+    is less than 2 * HOST_BITS_PER_WIDE_INT bits.  */
+ bool double_int_fits_in_hwi_p (double_int, bool);
+ bool double_int_fits_in_shwi_p (double_int);
+ bool double_int_fits_in_uhwi_p (double_int);
+ HOST_WIDE_INT double_int_to_shwi (double_int);
+ unsigned HOST_WIDE_INT double_int_to_uhwi (double_int);
+ 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);
+ bool double_int_negative_p (double_int);
+ int double_int_cmp (double_int, double_int, bool);
+ int double_int_scmp (double_int, double_int);
+ int double_int_ucmp (double_int, double_int);
+ void dump_double_int (FILE *, double_int, bool);
+ 
+ /* Zero and sign extension of numbers in smaller precisions.  */
+ 
+ double_int double_int_ext (double_int, unsigned, bool);
+ double_int double_int_sext (double_int, unsigned);
+ double_int double_int_zext (double_int, unsigned);
+ 
+ #define ALL_ONES (~((unsigned HOST_WIDE_INT) 0))
+ 
+ /* The operands of the following comparison functions must be processed
+    with double_int_ext, if their precision is less than
+    2 * HOST_BITS_PER_WIDE_INT bits.  */
+ 
+ /* Returns true if CST is zero.  */
+ 
+ static inline bool
+ double_int_zero_p (double_int cst)
+ {
+   return cst.low == 0 && cst.high == 0;
+ }
+ 
+ /* Returns true if CST is one.  */
+ 
+ static inline bool
+ double_int_one_p (double_int cst)
+ {
+   return cst.low == 1 && cst.high == 0;
+ }
+ 
+ /* Returns true if CST is minus one.  */
+ 
+ static inline bool
+ double_int_minus_one_p (double_int cst)
+ {
+   return (cst.low == ALL_ONES && cst.high == -1);
+ }
+ 
+ /* Returns true if CST1 == CST2.  */
+ 
+ static inline bool
+ double_int_equal_p (double_int cst1, double_int cst2)
+ {
+   return cst1.low == cst2.low && cst1.high == cst2.high;
+ }
+ 
+ #endif /* DOUBLE_INT_H */
Index: system.h
===================================================================
*** system.h	(revision 111507)
--- system.h	(working copy)
*************** extern void fancy_abort (const char *, i
*** 609,614 ****
--- 609,616 ----
  # define FALSE false
  #endif /* !__cplusplus */
  
+ /* Get definition of double_int.  */
+ #include "double-int.h"
  
  /* Some compilers do not allow the use of unsigned char in bitfields.  */
  #define BOOL_BITFIELD unsigned int
Index: Makefile.in
===================================================================
*** Makefile.in	(revision 111507)
--- Makefile.in	(working copy)
*************** INSN_ATTR_H = insn-attr.h $(srcdir)/insn
*** 773,779 ****
  C_COMMON_H = c-common.h $(SPLAY_TREE_H) $(CPPLIB_H) $(GGC_H)
  C_PRAGMA_H = c-pragma.h $(CPPLIB_H)
  C_TREE_H = c-tree.h $(C_COMMON_H) toplev.h $(DIAGNOSTIC_H)
! SYSTEM_H = system.h hwint.h $(srcdir)/../include/libiberty.h
  PREDICT_H = predict.h predict.def
  CPPLIB_H = $(srcdir)/../libcpp/include/line-map.h \
  	$(srcdir)/../libcpp/include/cpplib.h
--- 773,779 ----
  C_COMMON_H = c-common.h $(SPLAY_TREE_H) $(CPPLIB_H) $(GGC_H)
  C_PRAGMA_H = c-pragma.h $(CPPLIB_H)
  C_TREE_H = c-tree.h $(C_COMMON_H) toplev.h $(DIAGNOSTIC_H)
! SYSTEM_H = system.h hwint.h double-int.h $(srcdir)/../include/libiberty.h
  PREDICT_H = predict.h predict.def
  CPPLIB_H = $(srcdir)/../libcpp/include/line-map.h \
  	$(srcdir)/../libcpp/include/cpplib.h
*************** C_OBJS = c-lang.o stub-objc.o $(C_AND_OB
*** 952,958 ****
  
  # Language-independent object files.
  OBJS-common = \
!  tree-chrec.o tree-scalar-evolution.o tree-data-ref.o			   \
   tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o  \
   gimplify.o tree-pretty-print.o tree-into-ssa.o				   \
   tree-outof-ssa.o tree-ssa-ccp.o tree-vn.o tree-ssa-uncprop.o		   \
--- 952,958 ----
  
  # Language-independent object files.
  OBJS-common = \
!  double-int.o tree-chrec.o tree-scalar-evolution.o tree-data-ref.o	   \
   tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o  \
   gimplify.o tree-pretty-print.o tree-into-ssa.o				   \
   tree-outof-ssa.o tree-ssa-ccp.o tree-vn.o tree-ssa-uncprop.o		   \
*************** prefix.o: prefix.c $(CONFIG_H) $(SYSTEM_
*** 1779,1784 ****
--- 1779,1786 ----
  convert.o: convert.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H) \
     $(FLAGS_H) convert.h toplev.h langhooks.h real.h
  
+ double-int.o: double-int.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(TREE_H)
+ 
  langhooks.o : langhooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
     $(TREE_H) toplev.h $(TREE_INLINE_H) $(RTL_H) insn-config.h $(INTEGRATE_H) \
     langhooks.h $(LANGHOOKS_DEF_H) $(FLAGS_H) $(GGC_H) $(DIAGNOSTIC_H) intl.h \

Re: [patch] double_int

[Richard Henderson]

On Tue, Feb 28, 2006 at 12:38:07PM +0100, Zdenek Dvorak wrote:
> Comments (not neccessarily regarding just this change)?

I'm ok with this approach.


r~

Re: [patch] double_int

[Roger Sayle]

On Tue, 28 Feb 2006, Zdenek Dvorak wrote:
> 	* gengtype.c (main): Handle double_int type.
> 	* tree.h (struct tree_int_cst): Make type of int_cst double_int.
> 	* double-int.c: New file.
> 	* double-int.h: New file.
> 	* system.h: Include doubleint.h.
> 	* Makefile.in (SYSTEM_H): Include double-int.h.
> 	(double-int.o): Add.

Many thanks to RTH for confirming that he's happy with this API.
This is OK for mainline.

Roger
--