wide-int branch now up for public comment and review

Kenneth Zadeck zadeck@naturalbridge.com
Fri Aug 23 21:01:00 GMT 2013


On 08/23/2013 11:02 AM, Richard Sandiford wrote:
> Hi Kenny,
>
> This is the first time I've looked at the implementation of wide-int.h
> (rather than just looking at the rtl changes, which as you know I like
> in general), so FWIW here are some comments on wide-int.h.  I expect
> a lot of them overlap with Richard B.'s comments.
>
> I also expect many of them are going to be annoying, sorry, but this
> first one definitely will.  The coding conventions say that functions
> should be defined outside the class:
>
>      http://gcc.gnu.org/codingconventions.html
>
> and that opening braces should be on their own line, so most of the file
> needs to be reformatted.  I went through and made that change with the
> patch below, in the process of reading through.  I also removed "SGN
> must be SIGNED or UNSIGNED." because it seemed redundant when those are
> the only two values available.  The patch fixes a few other coding standard
> problems and typos, but I've not made any actual code changes (or at least,
> I didn't mean to).
I had started the file with the functions outside of the class and mike 
had stated putting them in the class, and so i went with putting them in 
the class since many of them were one liners and so having them out of 
line just doubled the size of everything. however, we did not look at 
the coding conventions and that really settles the argument.  Thanks for 
doing this.
> Does it look OK to install?
you can check it in.
> I'm still unsure about these "infinite" precision types, but I understand
> the motivation and I have no objections.  However:
>
>>      * Code that does widening conversions.  The canonical way that
>>        this is performed is to sign or zero extend the input value to
>>        the max width based on the sign of the type of the source and
>>        then to truncate that value to the target type.  This is in
>>        preference to using the sign of the target type to extend the
>>        value directly (which gets the wrong value for the conversion
>>        of large unsigned numbers to larger signed types).


> I don't understand this particular reason.  Using the sign of the source
> type is obviously right, but why does that mean we need "infinite" precision,
> rather than just doubling the precision of the source?
in a sense, "infinite" does not really mean infinite, it really just 
means large enough so that you never loose any information from the 
top.    For widening all that you really need to be "infinite" is one 
more bit larger than the destination type.   We could have had an abi 
where you specified the precision of every operation based on the 
precisions of the inputs.   Instead, for these kinds of operations, we 
decided to sniff the port and determine a fixed width that was large 
enough for everything that was needed for the port. We call that number 
infinite.  This sort of follows the convention that double-int was used 
with were infinite was 128 bits, but with our design/implementation, we 
(hopefully) have no bugs where the size of the datatypes needed never 
runs into implementation limits.

>>    * When a constant that has an integer type is converted to a
>>      wide-int it comes in with precision 0.  For these constants the
>>      top bit does accurately reflect the sign of that constant; this
>>      is an exception to the normal rule that the signedness is not
>>      represented.  When used in a binary operation, the wide-int
>>      implementation properly extends these constants so that they
>>      properly match the other operand of the computation.  This allows
>>      you write:
>>
>>                 tree t = ...
>>                 wide_int x = t + 6;
>>
>>      assuming t is a int_cst.
> This seems dangerous.  Not all code that uses "unsigned HOST_WIDE_INT"
> actually wants it to be an unsigned value.  Some code uses it to avoid
> the undefinedness of signed overflow.  So these overloads could lead
> to us accidentally zero-extending what's conceptually a signed value
> without any obvious indication that that's happening.  Also, hex constants
> are unsigned int, but it doesn't seem safe to assume that 0x80000000 was
> meant to be zero-extended.
>
> I realise the same thing can happen if you mix "unsigned int" with
> HOST_WIDE_INT, but the point is that you shouldn't really do that
> in general, whereas we're defining these overloads precisely so that
> a mixture can be used.
>
> I'd prefer some explicit indication of the sign, at least for anything
> other than plain "int" (so that the compiler will complain about uses
> of "unsigned int" and above).

There is a part of me that finds this scary and a part of me that feels 
that the concern is largely theoretical.    It does make it much easier 
to read and understand the code to be able to write "t + 6" rather than 
"wide_int (t) + wide_int::from_uhwi" (6) but of course you loose some 
control over how 6 is converted.

>>    Note that the bits above the precision are not defined and the
>>    algorithms used here are careful not to depend on their value.  In
>>    particular, values that come in from rtx constants may have random
>>    bits.
> I have a feeling I'm rehashing a past debate, sorry, but rtx constants can't
> have random bits.  The upper bits must be a sign extension of the value.
> There's exactly one valid rtx for each (value, mode) pair.  If you saw
> something different then that sounds like a bug.  The rules should already
> be fairly well enforced though, since something like (const_int 128) --
> or (const_int 256) -- will not match a QImode operand.
>
> This is probably the part of the representation that I disagree most with.
> There seem to be two main ways we could hande the extension to whole HWIs:
>
> (1) leave the stored upper bits undefined and extend them on read
> (2) keep the stored upper bits in extended form
It is not a matter of opening old wounds.   I had run some tests on 
x86-64 and was never able to assume that the bits above the precision 
had always been canonized.   I will admit that i did not try to run down 
the bugs because i thought that since the rtx constructors did not have 
a mode associated with them now was one required to in the constructors, 
that this was not an easily solvable problem.   So i have no idea if i 
hit the one and only bug or was about to start drinking from a fire 
hose.   But the back ends are full of GEN_INT (a) where a came from god 
knows where and you almost never see it properly canonized.   I think 
that until GEN_INT takes a mandatory non VOIDmode mode parameter, and 
that constructor canonizes it, you are doomed chasing this bug 
forever.    My/our experience on the dataflow branch was that unless you 
go clean things up AND put in a bunch of traps to keep people honest, 
you are never going to be able to make this assumption.

Having said that, we actually do neither of (1) or (2) inside of 
wide-int.  For rtl to wide-int, we leave the upper bits undefined and 
never allow you to look at them because the constructor has a mode and 
that mode allows you to draw a line in the sand.   There is no 
constructor for the "infinite" wide ints from rtl so you have no way to 
look.

Doing this allows us to do something that richi really wanted: avoiding 
copying.   We do not get to do as much richi would like and when he 
comes back from leave, he may have other places where can apply it, but 
right now if you say w = t + 6 as above, it "borrows" the rep from t to 
do the add, it does not really build a wide-int. We also do this if t is 
an rtx const.   But if we had to canonize the number, then we could not 
borrow the rep.
> The patch goes for (1) but (2) seems better to me, for a few reasons:
>
> * As above, constants coming from rtl are already in the right form,
>    so if you create a wide_int from an rtx and only query it, no explicit
>    extension is needed.
>
> * Things like logical operations and right shifts naturally preserve
>    the sign-extended form, so only a subset of write operations need
>    to take special measures.
right now the internals of wide-int do not keep the bits above the 
precision clean.   as you point out this could be fixed by changing 
lshift, add, sub, mul, div (and anything else i have forgotten about) 
and removing the code that cleans this up on exit.   I actually do not 
really care which way we go here but if we do go on keeping the bits 
clean above the precision inside wide-int, we are going to have to clean 
the bits in the constructors from rtl, or fix some/a lot of bugs.

But if you want to go with the stay clean plan you have to start clean, 
so at the rtl level this means copying. and it is the not copying trick 
that pushed me in the direction we went.

At the tree level, this is not an issue.   There are no constructors for 
tree-csts that do not have a type and before we copy the rep from the 
wide-int to the tree, we clean the top bits.   (BTW - If i had to guess 
what the bug is with the missing messages on the mips port, it would be 
because the front ends HAD a bad habit of creating constants that did 
not fit into a type and then later checking to see if there were any 
interesting bits above the precision in the int-cst.  This now does not 
work because we clean out those top bits on construction but it would 
not surprise me if we missed the fixed point constant path.)   So at the 
tree level, we could easily go either way here, but there is a cost at 
the rtl level with doing (2).


> * You have a public interface that exposes the underlying HWIs
>    (which is fine with me FWIW), so it seems better to expose a fully-defined
>    HWI rather than only a partially-defined HWI.
>
> E.g. zero_p is:
>
>    HOST_WIDE_INT x;
>
>    if (precision && precision < HOST_BITS_PER_WIDE_INT)
>      x = sext_hwi (val[0], precision);
>    else if (len == 0)
>      {
>        gcc_assert (precision == 0);
>        return true;
>      }
the above test for len==0 has been removed because it is rot.

>    else
>      x = val[0];
>
>    return len == 1 && x == 0;
>
> but I think it really ought to be just:
>
>    return len == 1 && val[0] == 0;
If we did your 2, it would be this way.
>>    When the precision is 0, all the bits in the LEN elements of
>>    VEC are significant with no undefined bits.  Precisionless
>>    constants are limited to being one or two HOST_WIDE_INTs.  When two
>>    are used the upper value is 0, and the high order bit of the first
>>    value is set.  (Note that this may need to be generalized if it is
>>    ever necessary to support 32bit HWIs again).
> I didn't understand this.  When are two HOST_WIDE_INTs needed for
> "precision 0"?
if a large unsigned constant comes in with the top bit set, the 
canonized value takes 2 hwis, the top hwi being 0.
>> #define addr_max_bitsize (64)
>> #define addr_max_precision \
> These should either be lower-case C++ constants or upper-case macros.
this will be fixed.
>>   /* VAL is set to a size that is capable of computing a full
>>      multiplication on the largest mode that is represented on the
>>      target.  Currently there is a part of tree-vrp that requires 2x +
>>      2 bits of precision where x is the precision of the variables
>>      being optimized.  */
>>   HOST_WIDE_INT val[WIDE_INT_MAX_ELTS];
> This comment seems redundant with the one above WIDE_INT_MAX_ELTS
> and likely to get out of date.
this will be fixed
>>      So real hardware only looks at a small part of the shift amount.
>>      On IBM machines, this tends to be 1 more than what is necessary
>>      to encode the shift amount.  The rest of the world looks at only
>>      the minimum number of bits.  This means that only 3 gate delays
>>      are necessary to set up the shifter.
> I agree that it makes sense for wide_int to provide a form of shift
> in which the shift amount is truncated.  However, I strongly believe
> wide-int.h should not test SHIFT_COUNT_TRUNCATED directly.  It should
> be up to the callers to decide when truncation is needed (and to what width).
richi does not like this either so i will get rid of it.
>
> We really need to get rid of the #include "tm.h" in wide-int.h.
> MAX_BITSIZE_MODE_ANY_INT should be the only partially-target-dependent
> thing in there.  If that comes from tm.h then perhaps we should put it
> into a new header file instead.
I will talk to mike about fixing this.
>> /* Return THIS as a signed HOST_WIDE_INT.  If THIS does not fit in
>>     PREC, the information is lost. */
>> HOST_WIDE_INT
>> to_shwi (unsigned int prec = 0) const
> Just dropping the excess bits seems dangerous.  I think we should assert
> instead, at least when prec is 0.
there are times when this is useful.   there is a lot of code that just 
wants to look at the bottom bits to do some alignment stuff. I guess 
that code could just grab the bottom elt of the array, but has not 
generally been how these this has been done.
>> /* Return true if THIS is negative based on the interpretation of SGN.
>>     For UNSIGNED, this is always false.  This is correct even if
>>     precision is 0.  */
>> inline bool
>> wide_int::neg_p (signop sgn) const
> It seems odd that you have to pass SIGNED here.  I assume you were doing
> it so that the caller is forced to confirm signedness in the cases where
> a tree type is involved, but:
>
> * neg_p kind of implies signedness anyway
> * you don't require this for minus_one_p, so the interface isn't consistent
> * at the rtl level signedness isn't a property of the "type" (mode),
>    so it seems strange to add an extra hoop there
it was done this way so that you can pass in TYPE_SIGN (t) in as the 
second parameter.   We could default the parameter to SIGNED and that 
would solve both cases.   I will look into minus_one_p.


>> /* Return true if THIS fits in an unsigned HOST_WIDE_INT with no
>>     loss of precision.  */
>> inline bool
>> wide_int_ro::fits_uhwi_p () const
>> {
>>    return len == 1 || (len == 2 && val[1] == 0);
>> }
> This doesn't look right, since len == 1 could mean that you have a
> gazillion-bit all-ones number.  Also, the val[1] == 0 check seems
> to assume the upper bits are defined when the precision isn't a multiple
> of the HWI size (although as above I that's a good thing and should be
> enforced).
you are correct.
> sign_mask has:

>>    gcc_unreachable ();
>> #if 0
>>    return val[len - 1] >> (HOST_BITS_PER_WIDE_INT - 1);
>> #endif
> Maybe remove this?
>
> The inline div routines do:
i will work on this this weekend.   tree vrp has not been our friend and 
sometimes does not like to compile this function.

>>    if (overflow)
>>      *overflow = false;
> but then just pass overflow to divmod_internal.  Seems better to initialise
> *overflow there instead.
>
> div_floor has:
>
>>      return divmod_internal (true, val, len, p1, s, cl, p2, sgn,
>> 			    &remainder, false, overflow);
>>
>>      if (quotient.neg_p (sgn) && !remainder.zero_p ())
>>        return quotient - 1;
>>      return quotient;
>>    }
> where the last bit is unreachable.
not to mention that the compiler never complained.
>
>> /* Divide DIVISOR into THIS producing the remainder.  The result is
>>     the same size as the operands.  The sign is specified in SGN.
>>     The output is floor truncated.  OVERFLOW is set to true if the
>>     result overflows, false otherwise.  */
>> template <typename T>
>> inline wide_int_ro
>> wide_int_ro::mod_floor (const T &c, signop sgn, bool *overflow = 0) const
> It's really the quotient that's floor-truncated, not the output
> (the remainder).  I was a bit confused at first why you'd need to
> truncate an integer remainder.  Same for the other functions.
The comments needs work, not the code.   You do have to adjust the 
remainder in some cases, but it is not truncation.
>> #ifdef DEBUG_WIDE_INT
>>    debug_vwa ("wide_int_ro:: %d = (%s == %s)\n", result, *this, s, cl, p2);
>> #endif
> I think these are going to bitrot quickly if we #if 0 then out.
> I think we should either use:
>
>    if (DEBUG_WIDE_INT)
>      debug_vwa ("wide_int_ro:: %d = (%s == %s)\n", result, *this, s, cl, p2);
>
> or drop them.
my plan is to leave these in while the branch is still being developed 
and then get rid of them before it is merged.    My guess is that i am 
going to need them still when i try the 32bit hwi test.

> The implementations of the general to_shwi1 and to_shwi2 functions look
> identical.  I think the comment should explain why two functions are needed.
I will check this
>> /* Negate THIS.  */
>> inline wide_int_ro
>> wide_int_ro::operator - () const
>> {
>>    wide_int_ro r;
>>    r = wide_int_ro (0) - *this;
>>    return r;
>> }
>>
>> /* Negate THIS.  */
>> inline wide_int_ro
>> wide_int_ro::neg () const
>> {
>>    wide_int_ro z = wide_int_ro::from_shwi (0, precision);
>>
>>    gcc_checking_assert (precision);
>>    return z - *this;
>> }
> Why do we need both of these, and why are they implemented slightly
> differently?
neg should go away.
>> template <int bitsize>
>> inline bool
>> fixed_wide_int <bitsize>::multiple_of_p (const wide_int_ro &factor,
>> 					 signop sgn,
>> 					 fixed_wide_int *multiple) const
>> {
>>    return wide_int_ro::multiple_of_p (factor, sgn,
>> 				     reinterpret_cast <wide_int *> (multiple));
>> }
> The patch has several instances of this kind of reinterpret_cast.
> It looks like an aliasing violation.
>
> The main thing that's changed since the early patches is that we now
> have a mixture of wide-int types.  This seems to have led to a lot of
> boiler-plate forwarding functions (or at least it felt like that while
> moving them all out the class).  And that in turn seems to be because
> you're trying to keep everything as member functions.  E.g. a lot of the
> forwarders are from a member function to a static function.
>
> Wouldn't it be better to have the actual classes be light-weight,
> with little more than accessors, and do the actual work with non-member
> template functions?  There seems to be 3 grades of wide-int:
>
>    (1) read-only, constant precision  (from int, etc.)
>    (2) read-write, constant precision  (fixed_wide_int)
>    (3) read-write, variable precision  (wide_int proper)
>
> but we should be able to hide that behind templates, with compiler errors
> if you try to write to (1), etc.
>
> To take one example, the reason we can't simply use things like
> std::min on wide ints is because signedness needs to be specified
> explicitly, but there's a good reason why the standard defined
> std::min (x, y) rather than x.min (y).  It seems like we ought
> to have smin and umin functions alongside std::min, rather than
> make them member functions.  We could put them in a separate namespace
> if necessary.
>
> I might have a go at trying this last part next week, unless Richard is
> already in the process of rewriting things :-)
mike will answer this.
> Thanks,
> Richard
>
>



More information about the Gcc-patches mailing list