[RFC] Changes to the wide-int classes

[Richard Biener]

On Sun, 1 Sep 2013, Richard Sandiford wrote:

> This is an RFC and patch for an alternative way of organising the
> wide-int classes, along the lines I mentioned earlier.  The main points
> are below, each with a "headline" and a bit of extra waffle that can be
> skipped if too long:
> 
> * As Richard requested, the main wide int class is parameterised by the
>   storage:
> 
>     template <typename storage>
>     class GTY(()) generic_wide_int : public storage
> 
> * As Richard also requested, double_int is now implemented in terms of
>   the wide-int routines.
> 
>   This didn't work out quite as elegantly as I'd hoped due to conflicting
>   requirements.  double_int is used in unions and so needs to be a POD,
>   whereas the fancy things we want to allow for wide_int and fixed_wide_int
>   mean that they need to have constructors.  The patch therefore keeps
>   double_int as the basic storage class and defines double_int_ext as
>   the wide-int class.  All the double_int methods therefore need to be
>   kept, but are now simple wrappers around the wi:: routines.
> 
>   double_int_ext and fixed_wide_int <HOST_BITS_PER_DOUBLE_INT> are
>   assignment-compatible.
> 
>   This is just to show that it's possible though.  It probably isn't
>   very efficient...
> 
> * wide-int.h no longer includes tree.h, rtl.h or double-int.h.
> 
>   The rtx and machine_mode routines are now in rtl.h, and the
>   tree-related ones are in tree.h.  double-int.h now depends on
>   wide-int.h, as described above.
> 
> * wide-int.h no longer includes tm.h.
> 
>   This is done by adding a new MAX_BITS_PER_UNIT to machmode.def,
>   so that the definition of MAX_BITSIZE_MODE_ANY_MODE no longer relies on
>   BITS_PER_UNIT.  Although I think we usually assume that BITS_PER_UNIT
>   is a constant, that wouldn't necessarily be true if we ever did support
>   multi-target compilers in future.  MAX_BITS_PER_UNIT is logically
>   the maximum value of BITS_PER_UNIT for any compiled-in target and must
>   be a constant.

It's not necessary to include gmp.h either - that is included from
system.h now.

> * Precision 0 is no longer a special marker for primitive types like ints.
>   It's only used for genuine 0-width integers.
> 
> * The wide-int classes are now relatively light-weight.  All the real
>   work is done by wi:: routines.
> 
>   There are still operator methods for addition, multiplication, etc.,
>   but they just forward to the associated wi:: routine.  I also reluctantly
>   kept and_not and or_not as operator-like methods for now, although I'd
>   like to get rid of them and just keep the genuine operators.  The problem
>   is that I'd have liked the AND routine to be "wi::and", but of course that
>   isn't possible with "and" being a keyword, so I went for "wi::bit_and"
>   instead.  Same for "not" and "wi::bit_not", and "or" and "wi::bit_or".
>   Then it seemed like the others should be bit_* too, and "wi::bit_and_not"
>   just seems a bit unwieldly...
> 
>   Hmm, if we decide to forbid the use of "and" in gcc, perhaps we could
>   #define it to something safe.  But that would probably be too confusing.
>   I'm sure those who like stepping through gcc with gdb are going to hate
>   this patch already, without that to make things worse...
> 
> * fixed_wide_int <N> now only has the number of HWIs required by N.
>   This makes addr_wide_int significantly smaller.
> 
> * fixed_wide_int <N> doesn't have a precision field; the precision
>   is always taken directly from the template argument.
> 
>   This isn't a win sizewise, since the length and precision fitted snugly
>   into a HWI slot, but it means that checks for particular precisions
>   can be resolved at compile time.  E.g. the fast single-HWI paths are
>   now dropped when dealing with fixed_wide_ints.
> 
> * Each integer type is classifed as one of: FLEXIBLE_PRECISION,
>   CONST_PRECISION and VAR_PRECISION.
> 
>   FLEXIBLE_PRECISION is for integers with both a precision and a signedness,
>   like trees and C "int"s.  In the case of C types like "int", the precision
>   depends on the host.
> 
>   CONST_PRECISION is for integers with a constant precision and no signedness,
>   like fixed_wide_int and double_int.  (OK, I realise saying that double_int
>   has no signedness is controversial...)
> 
>   VAR_PRECISION is for integers with a variable precision and no signedness,
>   like wide_int and rtx constants.
> 
> * It is possible to operate directly on two non-wide-int objects.
>   E.g. wi::add (tree_val, 1) is allowed, as is wi::add (rtx_pair_t (...), 1),
>   wi::sub (0, wide_int_val) and wi::lshift (10, 64).
> 
>   The rules are the symmetric extension of:
> 
>     FLEXIBLE_PRECISION op FLEXIBLE_PRECISION => max_wide_int
>     FLEXIBLE_PRECISION op CONST_PRECISION (N) => fixed_wide_int <N>
>     FLEXIBLE_PRECISION op VAR_PRECISION => wide_int
>     CONST_PRECISION (N) op CONST_PRECISION (N) => fixed_wide_int <N>
>     VAR_PRECISION op VAR_PRECISION => wide_int
> 
>   which probably sounds complicated, but I think is pretty natural
>   in practice.  Mixtures between CONST_PRECISION and VAR_PRECISION
>   seem dangerous and so fail to compile.  Mixtures between different
>   CONST_PRECISION widths make no sense and so again fail to compile.
> 
>   There are a couple of extra rules for double_int to get around
>   the PODness thing above.   Although double_int_ext and
>   fixed_wide_int <HOST_BITS_PER_DOUBLE_INT> are assignment-compatible,
>   a plain double_int cannot be initialised from a fixed_wide_int due
>   to the lack of double_int contructors.  See the binary_traits in
>   double-int.h for details.
> 
> * A static assert in the constructor prevents wide_ints from being
>   initialised from types with host-dependent precision (such as "int").
> 
> * A static assert also prevents fixed_wide_ints from being initialised
>   from wide_ints.  I think combinations like that would always be a
>   mistake.
> 
> I've deliberately not tackled any of the other things that have been
> talked about, such as whether excess bits should be defined, whether
> the blocks should be HWIs, etc.  I've also kept things like
> "wi::one (prec)", although this is now exactly equivalent to
> "wi::shwi (1, prec)".  I'm not sure either way on whether the
> one() form is worth keeping.
> 
> The patch is in three parts.  The first is the new wide-int.h,
> which is the one I'm really asking about.  The second has the changes
> to double-int.h and double-int.c.  The third contains all the other
> changes, including those to wide-int.cc.
> 
> The third part in particular might need some clean-up, but like I say
> I'm really asking about the first part for now.  The entire patch did
> pass bootstrap & regression test on x86_64-linux-gnu though.
> (Admittedly with a bit of hackery.  The new versions of build_int_cst*
> trigger an RA bug in which debug insns affect the chosen allocation.
> That isn't caused by a bug in the wide-int patches themselves, since I
> can reproduce it with the same testcase on mainline.  I'll try to look
> into it when I get time, but for now I've added an
> __attribute__((optimize(0))) to the affected routines.)
> 
> The big block comment at the top of wide-int.h probably also needs
> tweaking after these changes.
> 
> Thoughts?

I've looked at the resulting wide-int.h and like it a lot
compared to what is on the branch (less code duplication for one).

I think we should go ahead with this change (keeping the double-int
changes out for now, I didn't yet look at that patch).  We can
iterate on the details on the branch.

Thanks,
Richard.