ubsan vs. _BitInt

[jakubjelinek]

Consider

_BitInt(15) foo (_BitInt(15) x, _BitInt(15) y) { return x + y; }
_BitInt(115) bar (_BitInt(115) x, _BitInt(115) y) { return x + y; }
_BitInt(385) baz (_BitInt(385) x, _BitInt(385) y) { return x + y; }
int
main ()
{
  volatile _BitInt(15) a = foo (16383wb, 1wb);
  volatile _BitInt(115) b = bar (20769187434139310514121985316880383wb, 1wb);
  volatile _BitInt(385) c = baz (39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990306815wb, 1wb);
}

with -fsanitize=undefined.
At least on godbolt with clang trunk I'm getting
/app/example.c:1:59: runtime error: signed integer overflow: 16383 + 1 cannot be represented in type '_BitInt(15)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:1:59 in
/app/example.c:2:62: runtime error: signed integer overflow: 0x0003ffffffffffffffffffffffffffff + 1 cannot be represented in type '_BitInt(115)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:2:62 in
UndefinedBehaviorSanitizer: CHECK failed: ubsan_value.cpp:86 "((0 && "unexpected bit width")) != (0)" (0x0, 0x0) (tid=1)
The ubsan_value.{h,cpp} representation I guess is fine for very small _BitInt, the ones which fit into ValueHandle, the compiler
can/will sign/zero extend the values to ValueHandle bits. For slightly larger _BitInt (33 to 64 on 32-bit arches, 65 to 128 on 64-bit arches), I guess the compiler could sign/zero extend it in memory, but anything larger will simply not be handled by the library.
I wonder if we shouldn't add Tk_BitInt = 0x0002 and have TypeInfo in that case be the _BitInt precision rather than ceil log2 of it,
though that field is just 16-bit and I think LLVM currently supports even larger _BitInt.

I guess for now I'll add GCC -fsanitize=undefined support just for what can be encoded in the current scheme, but it would be really nice to have libubsan support even for larger _BitInts.

@AaronBallman

[llvmbot]

@llvm/issue-subscribers-bug

[llvmbot]

@llvm/issue-subscribers-c2x

[AaronBallman]

Heh, this is in that special place somewhere between feature request and bug report, but I think this falls more on the "bug" side of things given that _BitInt is standardized and Clang supports very large bit widths for the type. Confirming the report from that perspective.

[jakubjelinek]

If you want to split it, it can be both.
The bug part would be that LLVM emits for _BitInt larger than 128-bits (or 64-bits for 32-bit arches) TypeKind TK_Integer
which can cause crashes in libubsan or bogus values printed; in GCC I'm going to emit for the type being for those TK_Unknown instead, that results in

runtime error: unsigned integer overflow: <unknown> + <unknown> cannot be represented in type '_BitInt(385)'

rather than

runtime error: signed integer overflow: 0x.................................................................................................................. + 1 cannot be represented in type '_BitInt(385)'

(the <unknown> is IMHO acceptable for now, making it print as unsigned integer overflow rather than signed is less so),
and then the enhancement request to encode _BitInt (at least the one which can't be encoded in 64-bit/128-bit ints).
Now, because TypeInfo is just 16-bit, with TK_BitInt if it is lowest bit 1 for signed 0 for unsigned and the remaining the N from _BitInt(N), it could only represent up to _BitInt(32767). Perhaps value 32767 * 2 + signed could be reserved for TypeName must be '_BitInt(123456)' or 'unsigned _BitInt(123456)' format and ubsan should parse the name in that case to determine precision. In any case, TK_BitInt then would have values a pointer to array of limbs in the arch specific limb size and endianity.

[jakubjelinek]

Or another possibility would be to encode the architecture details of _BitInt representation in TypeInfo as well, like include exact_log2 of limb bitsize and little vs. big endian and grab the precision always from the type name.

[AaronBallman]

CC @zygoloid as UBSan code owner

[zygoloid]

How do we want to format larger _BitInts?

In particular, I wonder how useful it is to include the numerical value in the diagnostic when the integer is very large. The maximum value for a _BitInt(65536) is 19729 decimal digits long and 16384 hexdecimal digits long, so I think at least by the time we're dealing with integers of that size we don't want to print the full value. Perhaps we could (eg) pass the runtime only the high and low bits of the number if they don't fit within a primitive type? That'd be enough to print things like:

/app/example.c:2:62: runtime error: signed integer overflow: 0x3fffffff...ffffffff + 0x00000000...00000001 cannot be represented in type '_BitInt(9999)'

... which might be more useful than printing out several pages of the full value.

Perhaps we could handle _BitInt as follows:

• If the _BitInt is no wider than the widest primitive type, then widen it to a power of two size and use a TK_Integer representation.
• Otherwise, use a new TK_BigInteger representation where TypeInfo just indicates whether it's signed or unsigned and (in order to support correct elided formatting in hexadecimal) the bit width mod 4, and the value representation contains the high and low bits, stored in the high and low halves of the ValueHandle -- that is, high and low 16 bits for 32-bit architectures and high and low 32 bits for 64-bit architectures.

Or another possibility would be to encode the architecture details of _BitInt representation in TypeInfo as well, like include exact_log2 of limb bitsize and little vs. big endian and grab the precision always from the type name.

For Clang at least, the type name we include in the type descriptor isn't necessarily _BitInt(...), and might be a typedef name with an "aka". I think it might be a bit fragile to have the runtime try to parse the width out of that.

[jakubjelinek]

I think the compiler should pass the full value, after all, it likely has it already somewhere in memory if it is large and passing something different would mean larger code. Whatever the library does with it is its decision and could be adjusted by user requests e.g. through env vars etc.
Widening to some wider power of two primitive type works fine for +-* overflow, but doesn't e.g. for shift sanitization.
Say _BitInt(15) left shift sanitization by 15 gives weird message if the library thinks it is a 16-bit type, etc.
Of course, there could be a special rule that _BitInt which fits into ValueHandle bits is passed in those bits converted to ValueHandle type.
The division sanitization is something where it wants to check the whole value, whether it is the type's signed minimum, or -1, or 0, etc.

BTW, even the __int128 printing when it uses hexadecimal number is weird. I think it would be better for signed types if a value is negative to print -0x........... rather than 0x...........; especially for _BitInt it is confusing when it shows also bits outside of the range from promoting it into wider power of two type (if any).

[jakubjelinek]

BTW, regarding the parsing of TypeName string, another possibility how to encode full precision is put it after the NUL termination of TypeName string if TypeKind would be the new TK_BitInt or TK_BitInteger, however it is called, either aligned or not. Or, put the precision into TypeInfo if it fits there and only resort to putting it after TypeName if it doesn't.
Testcase could be e.g.:

__attribute__((noipa)) int
foo15 (_BitInt(15) *p, _BitInt(15) *q, int n)
{
  q[0] = p[0] + p[1];
  q[1] = p[2] - p[3];
  q[2] = p[4] * p[5];
  q[3] = p[6] / p[7];
  q[4] = p[8] << n;
  q[5] = p[9] >> n;
  return n;
}

void
test15 ()
{
  static _BitInt(15) p[] = {
    16382wb, 1wb,
    -16383wb, 1wb,
    127wb, 129wb,
    -16383wb - 1, 1wb,
    0wb, 1wb,
    16383wb, 1wb,
    -16383wb - 1, 1wb,
    127wb, 130wb,
    -16383wb - 1, -1wb,
    0wb, 1wb
  };
  _BitInt(15) q[6];
  int n = foo15 (p, q, 14);
  q[4] = p[8] << (n + 2);
  q[5] = p[9] >> (n + 2);
  foo15 (p + 10, q, 15);
}

#if __BITINT_MAXWIDTH__ >= 125
__attribute__((noipa)) int
foo125 (_BitInt(125) *p, _BitInt(125) *q, int n)
{
  q[0] = p[0] + p[1];
  q[1] = p[2] - p[3];
  q[2] = p[4] * p[5];
  q[3] = p[6] / p[7];
  q[4] = p[8] << n;
  q[5] = p[9] >> n;
  return n;
}

void
test125 ()
{
  static _BitInt(125) p[] = {
    21267647932558653966460912964485513214wb, 1wb,
    -21267647932558653966460912964485513215wb, 1wb,
    4611686018427387903wb, 4611686018427387905wb,
    -21267647932558653966460912964485513215wb - 1, 1wb,
    0wb, 1wb,
    21267647932558653966460912964485513215wb, 1wb,
    -21267647932558653966460912964485513215wb - 1, 1wb,
    4611686018427387903wb, 4611686018427387906wb,
    -21267647932558653966460912964485513215wb - 1, -1wb,
    0wb, 1wb
  };
  _BitInt(125) q[6];
  int n = foo125 (p, q, 123);
  q[4] = p[8] << (n + 5);
  q[5] = p[9] >> (n + 5);
  foo125 (p + 10, q, 125);
}
#endif

#if __BITINT_MAXWIDTH__ >= 575
__attribute__((noipa)) int
foo575 (_BitInt(575) *p, _BitInt(575) *q, int n)
{
  q[0] = p[0] + p[1];
  q[1] = p[2] - p[3];
  q[2] = p[4] * p[5];
  q[3] = p[6] / p[7];
  q[4] = p[8] << n;
  q[5] = p[9] >> n;
  return n;
}

void
test575 ()
{
  static _BitInt(575) p[] = {
    61832600368276133515125630254911797508782837275302959978515764023224306276632966792579100265310761247399417856504034834837841258576687802491886538775473291979151693037174782wb, 1wb,
    -61832600368276133515125630254911797508782837275302959978515764023224306276632966792579100265310761247399417856504034834837841258576687802491886538775473291979151693037174783wb, 1wb,
    248661618204893321077691124073410420050228075398673858720231988446579748506266687766527wb, 248661618204893321077691124073410420050228075398673858720231988446579748506266687766529wb,
    -61832600368276133515125630254911797508782837275302959978515764023224306276632966792579100265310761247399417856504034834837841258576687802491886538775473291979151693037174783wb - 1, 1wb,
    0wb, 1wb,
    61832600368276133515125630254911797508782837275302959978515764023224306276632966792579100265310761247399417856504034834837841258576687802491886538775473291979151693037174783wb, 1wb,
    -61832600368276133515125630254911797508782837275302959978515764023224306276632966792579100265310761247399417856504034834837841258576687802491886538775473291979151693037174783wb - 1, 1wb,
    248661618204893321077691124073410420050228075398673858720231988446579748506266687766527wb, 248661618204893321077691124073410420050228075398673858720231988446579748506266687766530wb,
    -61832600368276133515125630254911797508782837275302959978515764023224306276632966792579100265310761247399417856504034834837841258576687802491886538775473291979151693037174783wb - 1, -1wb,
    0wb, 1wb
  };
  _BitInt(575) q[6];
  foo575 (p, q, 574);
  foo575 (p + 10, q, 575);
}
#endif

int
main ()
{
  test15 ();
#if __BITINT_MAXWIDTH__ >= 125
  test125 ();
#endif
#if __BITINT_MAXWIDTH__ >= 575
  test575 ();
#endif
}