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.