601426 - Dodgy and inconsistent tests for intptr range on 64-bit platforms

Status: RESOLVED FIXED

(Tamarin Graveyard :: Virtual Machine, defect)

Description

[William Maddox]

In atom.h, it is claimed that the range of exactly representable integers in an IEEE double is -2^53-1 .. 2^53-1.  This is based on the observation that it is a signed-magnitude representation with 53 bits of magnitude, counting the 52 explicit significand bits and the implicit '1' first significand bit.  We then proceed to define atomIsValidIntptrValue() in terms of whether the *twos complement* representation of the integer fits in 54 bits.  We test a double 'i' like so:  ((i << 10) >> 10)  == i.  This test actually allows -2^53 as a valid intptr, which would be incorrect if the representable range were as claimed.  In fact, this misunderstands the treatment of the implicit leading significand bit. The actual representable range is extended to -2^53 .. 2^53, because the implicit leading 1 can actually play the role of a "54th" significand bit with a suitable exponent, provided the remaining (i.e., explicit) significand bits are all zero. Thus atomIsIntptrValue() test is slightly conservative, but actually is correct, the analysis in the commentary notwithstanding.

      I (decimal)     I (hex)        double(i)

 9007199254740992   20000000000000 4340000000000000    ;  2^53
 9007199254740991   1fffffffffffff 433fffffffffffff    ;  2^53-1
 9007199254740990   1ffffffffffffe 433ffffffffffffe    ;  2^53-2
-9007199254740990 ffe0000000000002 c33ffffffffffffe    ; -2^53-2
-9007199254740991 ffe0000000000001 c33fffffffffffff    ; -2^53-1
-9007199254740992 ffe0000000000000 c340000000000000    ; -2^53

In the intptr+intptr addition fastpath, in both op_add (instr.cpp) and in the interpreter (Interpreter.cpp), a similar test is performed on the result of an addition, again on a twos complement value.  In this case, the operands are pre-shifted to the left by 3 bits before the addition, because of the type tag. 
The sum is thus pre-shifted as well.  We wish to check for overflow of the addition rather than merely the range of a known valid result.  We thus sign extend the result by shifting it 8 places to the left and then 8 places back to the right before performing an overflow test.  Due to the pre-shifting, the 56th bit become the sign, corresponding to the 53rd bit of the actual integer result.  The range of intptr values admitted by this test is -2^52 .. 2^52-1.  Again, this is conservative, but if we were ever to promote a value to a boxed double on the basis of this test, without invoking atomIsValidIntptrValue() or its equivalent first, we would no longer have a canonical representation for all integer values.  I believe the correct resolution is to use a 7 bit shift in the integer fastpaths, corresponding to an effective shift 10 bits (54-bit intptr payload) as in atomIsValidIntptrValue() rather than 11 bits (53-bit payload) as things stand at present.

Comment 1

[William Maddox]

The following code in op_add will result in non-canonical integer values,
i.e., values represented as boxed doubles that could have been represented
as intptrs, and will be if computed on code paths that rely on atomIsValidIntptrValue().

#ifdef AVMPLUS_64BIT
// since 64-bit int atoms expect exactly 53 bits of precision, we want to shift bit 53+3 up into the sign bit and back down
#  define SIGN_EXTEND(v)       ((intptr_t(v) << 8) >> 8)
#else
#  define SIGN_EXTEND(v)       (intptr_t(v))
#endif

    // integer optimization based on the one from Interpreter.cpp, modified
    // to reduce the # of alu instructions
    if (atomIsBothIntptr(lhs,rhs))
    {
        intptr_t const sum = SIGN_EXTEND(lhs + rhs - kIntptrType);
        if ((lhs ^ rhs) < 0 || (lhs ^ sum) >= 0) {
            // no overflow
            return sum;
        }
        // both integers, but overflow happens.  Intentionally add these
        // without casting to int32_t.  If the sum of the shifted values overflow,
        // we know the unshifted values will not overflow with a word-sized add.
        return core->allocDouble(double(atomGetIntptr(lhs) + atomGetIntptr(rhs)));
    }

Compare with this code in atom.h and atom-inlines.h:

    #ifdef AVMPLUS_64BIT
    const intptr_t atomMinIntValue = -((1LL<<53)-1);
    const intptr_t atomMaxIntValue = (1LL<<53)-1;
    const intptr_t atomSignExtendShift = 10;         // 54 significant bits


    REALLY_INLINE bool atomIsValidIntptrValue(const intptr_t i)
    {
        return (((i << atomSignExtendShift) >> atomSignExtendShift) == i);
    }

Comment 2

[William Maddox]

Attachment: Use range of 54-bit twos complement integer consistently as 64-bit intptr range

This is a fairly targetted patch.  I want to clean this up so that some assertions in my latest patch for bug 561249 will be clean and reflect the
intended semantics rather than the mess noted in the present bug.
It is disturbing that identical copies of SIGN_EXTEND appear in both Interpreter.cpp and instr.h.  I considered moving it to atom.h, but the name is really not specific enough to be used in such a global context, and there's a lot of similar duplication in Interpreter.cpp.  I'm hesitant to start pulling on this thread just now, as all this should get cleaned up by moving to opaque atoms.

Comment 3

[Steven Johnson]

(In reply to comment #2)
>  I'm hesitant to start pulling
> on this thread just now, as all this should get cleaned up by moving to opaque
> atoms.

Opaque Atoms have been on the table for years now, and still aren't done, so don't wait for that to happen. I vote for unifying the macros.

Comment 4

[Steven Johnson]

Comment on attachment 481058 [details] [diff] [review]
Use range of 54-bit twos complement integer consistently as 64-bit intptr range

Conceptually, sounds fine. Clearly what we really need now is some acceptance tests (or, more likely, selftests) to actually exercise the values around this limit...

Comment 5

[William Maddox]

Please tell me it isn't so...

Looking in AvmCore.cpp at AvmCore::doubleToAtom() and AvmCore::doubleToAtom_sse2(), it appears that we produce a kIntptrType atom only when the double has an integral value AND that value fits in 32 bits!  The crucial logic in atomIsValidIntptrValueAndEqualTo() is careful to specify an intptr_t for the candidate integer argument, and use atomSignExtendShift to determine if the value will fit in the allotted space.  The conversion from the double to a candidate integer, however, produces a 32-bit result even on a 64-bit platform. For example, on the Mac:

#if defined(AVMPLUS_IA32) || defined(AVMPLUS_AMD64)
    //...
    Atom AvmCore::doubleToAtom_sse2(double n)
    {
        // handle integer values w/out allocation
        // this logic rounds in the wrong direction for E3, but
        // we never use a rounded value, only cleanly converted values.
#if defined(WIN32) || defined(__ICC)
    //...
#elif defined(_MAC)

        // MacTel always has SSE2 available
        int32_t const intval = _mm_cvttsd_si32(_mm_set_sd(n));
        if (atomIsValidIntptrValueAndEqualTo(intval, n))
            return atomFromIntptrValue(intval);

        return allocDouble(n);
	
	//...

In the event that the double is too large to truncate to an integer, 'intval' will be 0x80000000, or -2^31, a perfectly good kIntptrType value on a 64-bit platform.  Fortunately, atomIsValidIntptrValueAndEqualTo() will compare it against the original double and catch this.  The problem is that integer values representable in more than 32 bits, but in 54 or less, should be represented by a kIntptrType atom, not a kDoubleType atom.

Comment 6

[Edwin Smith]

(In reply to comment #5)
> Please tell me it isn't so...

The SSE2 optimization predated the support for 53-bit integers in kIntptrType.  This might seem like a lost opportunity, but the working assumption is that the benefit of the single instruction CVTTSD2SI fast path outweighs the lost opportunity to handle 33-53 bit ints using kIntptrType.

Still, if you can think of a way to improve the code, go for it.  One important sub-case might be double-to-uint32 on 64-bit cpus.

Why support 53 bits at all? We debated this quite a bit. The conclusion (which really ought to be in the Atom comments) was that on 64bit cpus, its important enough to handle full int32 and uint32 value ranges, which requires at least 33 bits of signed precision.  Given that, (shrug), its arbitrary where to set the cutoff point, between 33 and 53 bits.

Comment 7

[Steven Johnson]

(In reply to comment #6)
> The SSE2 optimization predated the support for 53-bit integers in kIntptrType. 

Yep. (Though I'm shamed to admit I didn't even notice this when I revved the kIntptrType stuff for 64-bit.)

Pretty much agree with Edwin though: efficiency is highly desirable here. But if x86-64 has a similar double-to-int64 conversion opcode it's certainly worth using it... I'm not aware of one though, have to poke into the Intel manuals to see.

Comment 8

[Steven Johnson]

Werner comments in #tamarin:

"CVTTSD2SI with REX byte supports a full quad word integer - 3 billion works fine into a 64-bit RAX"

So a 64-bit specialization should be possible here

Comment 9

[Rick Reitmaier]

Comment on attachment 481058 [details] [diff] [review]
Use range of 54-bit twos complement integer consistently as 64-bit intptr range

r+ who can complain if you're adding helpful comments and agree with Steven above, don't wait for the conversion to happen, let clean up the code now if we find anything.

Comment 10

[William Maddox]

It turns out that the issue reported here not only results in non-canonical integer-valued atoms on 64-bit platforms, but also results in incorrect wrapping of some additions at the 53-bit boundary, due to the incorrect shift value in the SIGN_EXTEND macro, which does not agree with the atomSignExtendShift value.  This problem was observed while investigating bug 700620.

Comment 11

[William Maddox]

Attachment: V2:Use range of 54-bit twos complement integer consistently as 64-bit intptr range

Includes previous (V1) patch, as well as a fix to the inlined addition code, effectively inlined the old broken definition of SIGN_EXTEND.

Modifies the test cases for specialized addition to canonicalize the values of numeric atoms so that kIntptrType boundary cases are effective as intended.

Adds primitives to System class in avmshell to support the tests.
(Same as https://bugzilla.mozilla.org/attachment.cgi?id=600226)

Comment 12

[Edwin Smith]

Comment on attachment 600305 [details] [diff] [review]
V2:Use range of 54-bit twos complement integer consistently as 64-bit intptr range

just to be clear in case it wasn't before:  There has never been an intention in the AVM to guarantee canonical Atom values - any Number can be a kDoubleType atom or a kIntptrType atom so long as it doesn't wrongly change the value.  In other words its never a corectness bug for 5 to be stored as a kDoubleType atom.

All computations on Number atoms must produce the right value regardless of input representation.  Computations *can* rely on inputs being valid -- for example on 64bit it should be safe to assume (and assert) that a kIntptrType atom is in the valid 53 bit range.

Thus, it would be okay with me if we used shift sizes that restricted kIntptrType values to (say) 50 bits, just to stay well clear of the edge cases.  But if we get the boundary conditions exactly right (as it now seems to be), all the better.

Excellent comment rewrite in atom.h.

Add a comment on is64bit() explaining that its for testing purposes only - apart from memory/stack/timing this should be the only way to detect the system word size.

Comment 13

[Tamarin Bot]

changeset: 7214:1fb053b49a9f
user:      William Maddox <[e-mail]>
summary:   Bug 601426: Use range of 54-bit twos complement integer consistently as 64-bit intptr range (r=edwsmith)

http://hg.mozilla.org/tamarin-redux/rev/1fb053b49a9f