Re: patch to fix constant math - 4th patch - the wide-int class.

[Richard Biener <richard.guenther@gmail.com>]

On Tue, Oct 9, 2012 at 5:09 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> This patch implements the wide-int class.    this is a more general version
> of the double-int class and is meant to be the eventual replacement for that
> class.    The use of this class removes all dependencies of the host from
> the target compiler's integer math.
>
> I have made all of the changes i agreed to in the earlier emails. In
> particular, this class internally maintains a bitsize and precision but not
> a mode.     The class now is neutral about modes and tree-types.    the
> functions that take modes or tree-types are just convenience functions that
> translate the parameters into bitsize and precision and where ever there is
> a call that takes a mode, there is a corresponding call that takes a
> tree-type.
>
> All of the little changes that richi suggested have also been made.
>
> The buffer sizes is now twice the size needed by the largest integer mode.
> This gives enough room for tree-vrp to do full multiplies on any type that
> the target supports.
>
> Tested on x86-64.
>
> This patch depends on the first three patches.   I am still waiting on final
> approval on the hwint.h patch.
>
> Ok to commit?

diff --git a/gcc/wide-int.h b/gcc/wide-int.h
new file mode 100644
index 0000000..efd2c01
--- /dev/null
+++ b/gcc/wide-int.h
...
+#ifndef GENERATOR_FILE

The whole file is guarded with that ... why?  That is bound to be fragile once
use of wide-int spreads?  How do generator programs end up including
this file if they don't need it at all?

+#include "tree.h"
+#include "hwint.h"
+#include "options.h"
+#include "tm.h"
+#include "insn-modes.h"
+#include "machmode.h"
+#include "double-int.h"
+#include <gmp.h>
+#include "insn-modes.h"
+

That's a lot of tree and rtl dependencies.  double-int.h avoids these by
placing conversion routines in different headers or by only resorting to
types in coretypes.h.  Please try to reduce the above to a minimum.

+  HOST_WIDE_INT val[2 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_WIDE_INT];

are we sure this rounds properly?  Consider a port with max byte mode
size 4 on a 64bit host.

I still would like to have the ability to provide specializations of wide_int
for "small" sizes, thus ideally wide_int would be a template templated
on the number of HWIs in val.  Interface-wise wide_int<2> should be
identical to double_int, thus we should be able to do

typedef wide_int<2> double_int;

in double-int.h and replace its implementation with a specialization of
wide_int.  Due to a number of divergences (double_int is not a subset
of wide_int) that doesn't seem easily possible (one reason is the
ShiftOp and related enums you use).  Of course wide_int is not a
template either.  For the hypotetical embedded target above we'd
end up using wide_int<1>, a even more trivial specialization.

I realize again this wide-int is not what your wide-int is (because you
add a precision member).  Still factoring out the "common"s of
wide-int and double-int into a wide_int_raw <> template should be
possible.

+class wide_int {
+  /* Internal representation.  */
+
+  /* VAL is set to a size that is capable of computing a full
+     multiplication on the largest mode that is represented on the
+     target.  The full multiplication is use by tree-vrp.  If
+     operations are added that require larger buffers, then VAL needs
+     to be changed.  */
+  HOST_WIDE_INT val[2 * MAX_BITSIZE_MODE_ANY_INT / HOST_BITS_PER_WIDE_INT];
+  unsigned short len;
+  unsigned int bitsize;
+  unsigned int precision;

The len, bitsize and precision members need documentation.  At least
one sounds redundant.

+ public:
+  enum ShiftOp {
+    NONE,
NONE is never a descriptive name ... I suppose this is for arithmetic vs.
logical shifts?
+    /* There are two uses for the wide-int shifting functions.  The
+       first use is as an emulation of the target hardware.  The
+       second use is as service routines for other optimizations.  The
+       first case needs to be identified by passing TRUNC as the value
+       of ShiftOp so that shift amount is properly handled according to the
+       SHIFT_COUNT_TRUNCATED flag.  For the second case, the shift
+       amount is always truncated by the bytesize of the mode of
+       THIS.  */
+    TRUNC

ah, no, it's for SHIFT_COUNT_TRUNCATED.  "mode of THIS"?  Now
it's precision I suppose.  That said, handling SHIFT_COUNT_TRUNCATED
in wide-int sounds over-engineered, the caller should be responsible
of applying SHIFT_COUNT_TRUNCATED when needed.

+  enum SignOp {
+    /* Many of the math functions produce different results depending
+       on if they are SIGNED or UNSIGNED.  In general, there are two
+       different functions, whose names are prefixed with an 'S" and
+       or an 'U'.  However, for some math functions there is also a
+       routine that does not have the prefix and takes an SignOp
+       parameter of SIGNED or UNSIGNED.  */
+    SIGNED,
+    UNSIGNED
+  };

double-int and _all_ of the rest of the middle-end uses a 'int uns' parameter
for this.  _Please_ follow that.  Otherwise if you communicate between
those interfaces you have to to uns ? UNSIGNED : SIGNED and
signop == UNSIGNED ? 1 : 0 all over the place.

+  static wide_int from_shwi (HOST_WIDE_INT op0, unsigned int bitsize,
+                            unsigned int precision);
+  static wide_int from_shwi (HOST_WIDE_INT op0, unsigned int bitsize,
+                            unsigned int precision, bool *overflow);

I suppose , bool *overflow = NULL would do as well?  What's the
distinction between bitsize and precision (I suppose, see the above
question)?  I suppose precision <= bitsize and bits above precision
are sign/zero extended (and the rest of the val[] array contains undefined
content?)?  But we also have 'len', which then matches bitsize (well
it may be larger).  So IMHO either bitsize or len is redundant.  At least
the tree level nowhere considers partial integer modes special this way
(only the precision is ever taken into account, but we always sign-/zero-extend
to the whole double-int - thus 'len' in wide-int terms).

+  inline static wide_int from_hwi (HOST_WIDE_INT op0, const_tree type);
+  inline static wide_int from_hwi (HOST_WIDE_INT op0, const_tree type,
+                                  bool *overflow);

Are you needing this overload or are you adding it for "completeness"?
Because this interface is wrong(TM), and whoever calls it has at least
cleanup opportunities ... from_tree or from_rtx makes sense.

Also in which cases do you need "overflow"?  a HWI always fits in
a wide-int!  All trees and rtxen do, too.  You seem to merge two
operations here, conversion to wide-int and truncation / extension.
That doesn't look like a clean interface to me.

+  static wide_int from_double_int (enum machine_mode, double_int);

the choice of passing a mode seems arbitrary (the natural interface
would be nothing - precision is 2 * HWI).  Passing it as first parameter
is even more strange to me ;)

+  static wide_int from_tree (const_tree);
+  static wide_int from_rtx (const_rtx, enum machine_mode);

+  HOST_WIDE_INT to_shwi (unsigned int prec) const;

See above - merges two basic operations.  You should write

 w.sext (prec).to_shwi ()

instead (I _suppose_ it should sign-extend, should it? ;)).  Btw, why
don't we need to always specify bitsize together with precision in all
the places?  (not that I am arguing for it, I'm arguing for the
removal of bitsize)

+  static wide_int max_value (unsigned int bitsize, unsigned int prec,
SignOp sgn);

now that I am seeing this - is there any restriction on how the precision
of a partial integer mode may differ from its bitsize?  Can we have
POImode with 1 bit precision?  I suppose the solution for all this is
that when converting a wide-int to a RTX with a mode then we need to
zero-/sign-extend to the modes bitsize (and wide-int only cares about
precision).  Eventually a set_len can adjust the amount of BITS_PER_UNITs
we fill with meaningful values if needed.  Otherwise len == precision
/ BITS_PER_UNIT (rounded to HWI for obvious practical reasons).

+  inline static wide_int minus_one (unsigned int bitsize, unsigned int prec);
+  inline static wide_int minus_one (const_tree type);
+  inline static wide_int minus_one (enum machine_mode mode);
+  inline static wide_int zero (unsigned int bitsize, unsigned int prec);
+  inline static wide_int zero (const_tree type);
+  inline static wide_int zero (enum machine_mode mode);
+  inline static wide_int one (unsigned int bitsize, unsigned int prec);
+  inline static wide_int one (const_tree type);
+  inline static wide_int one (enum machine_mode mode);
+  inline static wide_int two (unsigned int bitsize, unsigned int prec);
+  inline static wide_int two (const_tree type);
+  inline static wide_int two (enum machine_mode mode);
+  inline static wide_int ten (unsigned int bitsize, unsigned int prec);
+  inline static wide_int ten (const_tree type);
+  inline static wide_int ten (enum machine_mode mode);

wheeee .... ;)

What's wrong with from_uhwi (10, ...)?  double-int has the above for
compatibility reasons only.  And why should I care about type/mode/size
for something as simple as '1'?

+  inline unsigned short get_len () const;
+  inline unsigned int get_bitsize () const;
+  inline unsigned int get_precision () const;
+  inline unsigned int get_full_len () const;

not sure which air you are pulling full_len from ;)

+  wide_int force_to_size (unsigned int bitsize,
+                         unsigned int precision) const;

or rather 'trunc'?  Seems to be truncation and set_len combined?

I wonder if for the various ways to specify precision/len there is a nice C++
way of moving this detail out of wide-int.  I can think only of one:

struct WIntSpec {
  WIntSpec (unsigned int len, unsigned int precision);
  WIntSpec (const_tree);
  WIntSpec (enum machine_mode);
  unsigned int len;
  unsigned int precision;
};

and then (sorry to pick one of the less useful functions):

  inline static wide_int zero (WIntSpec)

which you should be able to call like

  wide_int::zero (SImode)
  wide_int::zero (integer_type_node)

and (ugly)

  wide_int::zero (WIntSpec (32, 32))

with C++0x wide_int::zero ({32, 32}) should be possible?  Or we keep
the precision overload.  At least providing the WIntSpec abstraction
allows custom ways of specifying required bits to not pollute wide-int
itself too much.  Lawrence?

+  /* Printing functions.  */
+
+  void print_dec (char *buf, SignOp sgn) const;
+  void print_dec (FILE *file, SignOp sgn) const;
+  void print_decs (char *buf) const;
+  void print_decs (FILE *file) const;
+  void print_decu (char *buf) const;
+  void print_decu (FILE *file) const;
+  void print_hex (char *buf) const;
+  void print_hex (FILE *file) const;

consider moving them to standalone functions, out of wide-int.h

+  inline bool minus_one_p () const;
+  inline bool zero_p () const;
+  inline bool one_p () const;
+  inline bool neg_p () const;

what's wrong with w == -1, w == 0, w == 1, etc.?

+  bool only_sign_bit_p (unsigned int prec) const;
+  bool only_sign_bit_p () const;

what's that?  Some of the less obvious functions should be documented
in the header I think.  Smells of combining two things again here.
Either wide-int has an intrinsic precision or it has not ... (like double-int).

+  bool fits_u_p (unsigned int prec) const;
+  bool fits_s_p (unsigned int prec) const;

See above.

+  /* Extension  */
+
+  inline wide_int ext (unsigned int offset, SignOp sgn) const;
+  wide_int sext (unsigned int offset) const;
+  wide_int sext (enum machine_mode mode) const;
+  wide_int zext (unsigned int offset) const;
+  wide_int zext (enum machine_mode mode) const;

'offset'?  I suppose that's 'precision'.  Does that alter the
precision of *this?
I think it should (and thus there should be no set_precision function).
If it doesn't alter precision the functions don't make much sense to me.

+  wide_int set_bit (unsigned int bitpos) const;

this kind of interface is strange.  You call it like w.set_bit (1) but it
doesn't actually set bit 1 in w but it constructs a new wide_int and
returns that.  So I suppose it should be

  wide_int with_bit_set (unsigned int bitpos) const;

or similar.  Or simply have a mutating set_bit.  Or leave it out entierly,
we cannot have many uses of this kind of weird interface.

similar comments for the rest.

.... rest skipped ...

+                                   / HOST_BITS_PER_WIDE_INT + 32));
+  char *dump (char* buf) const;
+ private:
+
+  /* Private utility routines.  */
+  wide_int decompress (unsigned int target, unsigned int bitsize,
+                      unsigned int precision) const;
+  static wide_int add_overflow (const wide_int *op0, const wide_int *op1,
+                               wide_int::SignOp sgn, bool *overflow);
+  static wide_int sub_overflow (const wide_int *op0, const wide_int *op1,
+                               wide_int::SignOp sgn, bool *overflow);
+};


IMHO way too many functions for a well tested initial implementation.
There are a lot of things that seem operation compositions.  Is your
concern efficiency here?  That would be bad as that means wide_ints
are too heavy weight.

Can you use gcov to see which functions have (how much) coverage?

Thanks,
Richard.



> kenny
>
>