UBSan output is incorrect for non power-of-2 sized _BitInt types

[bjope]

Consider this test case:

unsigned foo(unsigned _BitInt(44) x) {
    _BitInt(9) c = -2;
    return x >> c;
}

int main() {
  return foo(5) ? 1 : 0;    
}

As shown by https://godbolt.org/z/M614qnhco , the result when compiling and running this program (with ubsan) is weird:

/app/example.c:3:14: runtime error: shift exponent 510 is too large for 64-bit type 'unsigned _BitInt(44)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:3:14 

The expected error here would be "shift exponent -2 is negative". But it is not only the detection of isNegative for the exponent that is wrong, it also reports an incorrect bitwidth (64-bit type) for the shifted value.

Afaict the problem is that the TypeDescriptor encoding (compiler-rt/lib/ubsan/ubsan_value.h) encodes the _BitInt types like ordinary integer types:

    /// An integer type. Lowest bit is 1 for a signed value, 0 for an unsigned
    /// value. Remaining bits are log_2(bit width). The value representation is
    /// the integer itself if it fits into a ValueHandle, and a pointer to the
    /// integer otherwise.
    TK_Integer = 0x0000,

But using log_2(bit width) does not work that well when having non-power-of-two bit widths.

One idea could be to introduce a new TK_BitInt kind, that encodes the bit wifth in some other way? Although I have no idea how big impact that has on the rest of the code.

This problem was found when running tests with the fix from #88004

[llvmbot]

@llvm/issue-subscribers-bug

Author: Björn Pettersson (bjope)

Consider this test case: ``` unsigned foo(unsigned _BitInt(44) x) { _BitInt(9) c = -2; return x >> c; }

int main() {
return foo(5) ? 1 : 0;
}

As shown by https://godbolt.org/z/M614qnhco , the result when compiling and running this program (with ubsan) is weird:

/app/example.c:3:14: runtime error: shift exponent 510 is too large for 64-bit type 'unsigned _BitInt(44)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:3:14

The expected error here would be "shift exponent -2 is negative". But it is not only the detection of isNegative for the exponent that is wrong, it also reports an incorrect bitwidth (64-bit type) for the shifted value.

Afaict the problem is that the TypeDescriptor encoding (compiler-rt/lib/ubsan/ubsan_value.h) encodes the _BitInt types like ordinary integer types:

/// An integer type. Lowest bit is 1 for a signed value, 0 for an unsigned
/// value. Remaining bits are log_2(bit width). The value representation is
/// the integer itself if it fits into a ValueHandle, and a pointer to the
/// integer otherwise.
TK_Integer = 0x0000,

But using log_2(bit width) does not work that well when having non-power-of-two bit widths.

One idea could be to introduce a new TK_BitInt kind, that encodes the bit wifth in some other way? Although I have no idea how big impact that has on the rest of the code.

This problem was found when running tests with the fix from https://github.com/llvm/llvm-project/pull/88004
</details>

[bjope]

Probably a bit related to #64100

[shafik]

CC @AaronBallman

[vabridgers]

Is the approach outlined by @zygoloid in #64100 acceptable to address this issue?

[AaronBallman]

Is the approach outlined by @zygoloid in #64100 acceptable to address this issue?

Yes, I believe it is.

[bjope]

I still think it looks weird when it says that the 44-bit bitint is a 64-bit type and an 130-bit bitint is a 128-bit type etc.

See the example here, https://godbolt.org/z/E6j7E6GWb , resulting in:

/app/example.c:3:14: runtime error: shift exponent 456 is too large for 64-bit type '_BitInt(44)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:3:14 
/app/example.c:7:14: runtime error: shift exponent 4294967240 is too large for 64-bit type 'unsigned _BitInt(44)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:7:14 
/app/example.c:11:14: runtime error: shift exponent 600 is too large for 128-bit type '_BitInt(130)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:11:14 

So I think the fix in #93612 only solved parts of the problem described.

[earnol]

The values displayed are correct, but the bitness itself might need to be corrected. However i might say the current message is better in a sense as it gives information about storage size for the _BitInt, but it needs to be properly formulated.
As for the message what do you think about changing the message to:
shift exponent 456 is too large for 44-bit type '_BitInt(44)' stored as 64-bit. ?

As for bit int with N above 130 it has other issues.

[bjope]

I don't think "stored as" is of much interest in these error messages. The size of the bitint type should be more interesting (and you can derive the type store size from knowing the size in bits of the _BitInt, but not the other way around).

One thing that looks a bit weird right now is this example: https://godbolt.org/z/czsjszzxa

When shifting a _BitInt(64) 67 steps to the left we get:

/app/example.c:6:14: runtime error: shift exponent 67 is too large for 64-bit type '_BitInt(64)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:6:14 

But when shifting a _BitInt(65) 67 steps to the left we get this more confusing message:

/app/example.c:10:14: runtime error: left shift of 15 by 67 places cannot be represented in type '_BitInt(65)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:10:14 

I think the above is due to comparing the shift count with the weird rounded size from the TypeInfo rather using the width of the _BitInt. That wouldn't happen if using the size in bits of the bitint instead of using the log2 size.

[earnol]

Then what type message do you propose?
I understand why it works out this way but still not fully clear on wanted position.
The third case the store type is int128 (16 bytes are used to store x in foo3) and this it is totally valid to have an exponent of 67 (because 67 < 128).
Adding to your example, please notice the message changes for calls:
foo2(15, 63)
and
foo2(15, 64)
In first case we have cannot be represented message because if the first argument would not 15 but zero there would be no ubsan error.
In second case we have is too large message because the second argument invalid regardless to the first argument.

At least in my eyes, it is important to distinguish those 2 cases.
But it is a my POV. POV of the person who knows how does it works. Maybe user perspective is different and i missing it.

The more confusing case is this: https://godbolt.org/z/q8xfxPa67.
We are getting cannot be represented message because internal type is uint64_t. This the shift was fine, but the end result did not fit into allocated space of 44 bits.
This might be a bug in the handler logic that should be and can be addressed.

[bjope]

Then what type message do you propose? I understand why it works out this way but still not fully clear on wanted position. The third case the store type is int128 (16 bytes are used to store x in foo3) and this it is totally valid to have an exponent of 67 (because 67 < 128).

It is UB to shift a _BitInt(65) more than 65 bits. That is why we report the ubsan shift out-of-bounds. The store type has nothing to do with it.

I expect errors like these:

/app/example.c:2:14: runtime error: shift exponent 67 is too large for 63-bit type '_BitInt(63)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:2:14 
/app/example.c:6:14: runtime error: shift exponent 67 is too large for 64-bit type '_BitInt(64)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:6:14 
/app/example.c:10:14: runtime error: shift exponent 67 is too large for 65-bit type '_BitInt(65)'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /app/example.c:10:14