[RFC v2] [Clang] Introduce OverflowBehaviorTypes (for wrapping and non-wrapping arithmetic)

Clang Frontend
1

Support the Linux kernel’s need for defining overflow resolution behavior for types at the source level by introducing OverflowBehaviorTypes to Clang’s type system.

Key discussion areas for this RFC include C++ support, narrowing semantics and other design or implementation topics.

This RFC is a follow-up to [RFC] [Clang] Canonical wrapping and non-wrapping types. There is valuable background and discussion on that RFC. To summarize, it seems folks are on board with the general idea of canonical wrapping types.

Implementation

v2 uses an attribute to create an OverflowBehaviorType within the AST. This is not as prone to getting “lost” or stripped away like my PR add wraps and no_wraps attributes. This is because v2 doesn’t use AttributedTypes.

v1 used type specifiers to instantiate built-in integral types like _Wrap int or _NoWrap int. v2 instead parses overflow_behavior attributes to create OverflowBehaviorTypes within the AST. Promotions and codegen take special care to consider OverflowBehaviorTypes. Since OBTs are canonical types in the AST we have a very nice time persisting the types through promotions. During codegen, llvm already has intrinsics across a variety of bitwidths which we emit based on the OBTs present; Clang doesn’t do any of the overflow calculations itself (except for -Winteger-overflow ICE checks for which OBTs have a backdoor).

To best grasp the behaviors mentioned above, take a look at the Clang sema and codegen tests:

I have a linux tree which is a fork of Kees’ for-next tree which has the necessary kbuild changes to support the INTEGER_WRAP config option as well as OverflowBehaviorTypes and sanitizer special case lists.

With this kernel tree and this llvm tree I built an x86 kernel with the INTEGER_WRAP sanitizers on and marked size_t with a no_wrap overflow behavior type. The current configuration means I am only getting splats around arithmetic containing size_t types. I’ve had a syzkaller instance running against this image for a couple weeks with promising results. We are getting solid signal for overflow bugs in the kernel which is not something we’ve ever really had since we couldn’t turn on the integer sanitizers without tons of noise. Now, with a SSCL ignorelist and a size_t overflow_behavior annotation, we are getting type-level granularity.

Here’s my Linux tree with the necessary kbuild changes: GitHub - JustinStitt/linux at dev/v6.15-rc4/int-wrap-types-poc

Here’s my LLVM tree implementing OverflowBehaviorTypes: GitHub - JustinStitt/llvm-project at overflow-behavior-types (wip)

Narrowing semantics

OverflowBehaviorTypes will perform implicit narrowing casts on other operands in order to 1) get both types to the same bitwidth and 2) have the final result type be the same bitwidth and share the overflow behavior of the OBT.

Here is the most obvious example to show this behavior:

void foo(char __no_wrap A) {
  unsigned long B;
  (A + B);
}

// relevant AST snippet
`-BinaryOperator 0x55d82d556558 <col:4, col:8> '__no_wrap char':'char' '+'
  |-ImplicitCastExpr 0x55d82d556510 <col:4> '__no_wrap char':'char' <LValueToRValue>
  | `-DeclRefExpr 0x55d82d5564d0 <col:4> '__no_wrap char':'char' lvalue ParmVar 0x55d82d556278 'A' '__no_wrap char':'char'
  `-ImplicitCastExpr 0x55d82d556540 <col:8> '__no_wrap char':'char' <IntegralCast>
    `-ImplicitCastExpr 0x55d82d556528 <col:8> 'unsigned long' <LValueToRValue>
      `-DeclRefExpr 0x55d82d5564f0 <col:8> 'unsigned long' lvalue Var 0x55d82d556450 'B' 'unsigned long'

There are two main reasons for this narrowing cast:

  1. So we don’t forget relevant bitwidths for the OBTs

  2. Better integer-overflow signal since the splat reports on the arithmetic and not on the implicit cast which may cause truncation.

To help explain (1) and (2), consider this arithmetic expression:

__nowrap char a;
int b; long c;
(a + b + c + 7);

Following normal C implicit promotion rules a+b has the result type of ‘int’ which means any further arithmetic we wish to check for overflow is now checking at the incorrect bit boundary. And in this particular example, again following normal C promotion rules, the final arithmetic expression has a result type of ‘long’ so we would not even get reliable truncation reporting from the sanitizers.

To solve this we could carry bitwidth information within the OverflowBehaviorType itself and proceed with the usual promotion semantics. We could then just emit the overflow intrinsic that matches the “stored” bitwidth from and OBT field. To reduce initial complexity to myself and to reviewers, I’ve opted to just add narrowing casts with their own simple (yet maybe-not-so obvious) semantics.

Current problems

We ran into a case in the kernel that spawns -Wformat warnings. It looks something like this:

unsigned long long a;
size_t b;

printf("%llx", a + b);

The format specifier expects an ‘unsigned long long’ but due to an implicit narrowing cast the type is actually ‘unsigned long’. Note that ‘long’ and ‘long long’ have different bitwidths on 32bit vs 64bit. Currently I am just doing my builds with -Wno-format but I see two realistic solutions for stuff like this (but I’m happy to hear about any new ideas):

  1. change all the occurrences in the kernel to use new specifiers (gets weird with the aforementioned 32bit vs 64bit differences)

  2. add some compiler workaround which adds a final implicit cast back up to the expected type.

We should be careful with (2) as adding too many compiler backdoors risks overcomplications. The aforementioned narrowing semantics is already “pushing it”.

TODO

  • add a flag to enable OverflowBehaviorTypes -foverflow-behavior-types
  • expand on C++ compatibility
  • _BitInt types?
  • other overflow behaviors (e.g., saturation)

CCs (because you participated in v1)

@kees @mizvekov @Meinersbur @AaronBallman @jyknight @melver @efriedma-quic @ldionne @rnk @reinterpretcast @philnik @vitalybuka

:white_check_mark: Consensus to move forward with this RFC was called in this message.

2

It looks like the “current problems” are a direct consequence of the “narrowing semantics”. Which then begs the question, would a version that follows normal C promotion rules be superior to users?

To solve this we could carry bitwidth information within the OverflowBehaviorType itself and proceed with the usual promotion semantics. We could then just emit the overflow intrinsic that matches the “stored” bitwidth from and OBT field. To reduce initial complexity [..]

Despite the conceptually simpler version, the semantic change might be a lot more complex to reconcile for users. Also, you say that you want to check “further arithmetic for overflow”, but perhaps the user intended for the implicit promotion to happen? Wouldn’t that result in false positives?

3

If a user marks a type’s overflow behavior as wrapping then they may be surprised when it doesn’t wrap on the type’s actual boundaries; traditional C promotions risk messing with this assumption. OBTs lose a lot of their usefulness if some special care (narrowing, or other approach) isn’t taken to maintain bit boundaries.

Example assuming traditional C promotion rules:

unsigned char __attribute__((overflow_behavior(wrap))) A;
(A + 1); // `A` is promoted to int, we no longer get
         // overflow signal on the `unsigned char` boundary!

I am fine taking any approach to ease the complexity for users but I think we should also recognize that these types are opt-in and are used to hyper-specify type behaviors – users should expect semantic changes (think _BitInt and fixed point types which also have some non-traditional semantics). I am happy to hear more thoughts on this.

It should be noted that promotion rules between two OBT types is more or less the same as traditional C promotions. The narrowing semantics I’ve outlined are intended for arithmetic consisting of an OBT type and a non-OBT type.

4

More specifically, they follow max bit-width promotion rules, not the anachronistic C promotion which starts at “int”. An OBT u8 plus OBT u16 will promote to u16, not u32. And this is good! :slight_smile:

When mixing types in a calculation (i.e. non-OBT with OBT), I think it’s totally fine to follow the OBT promotion rules. If not, we get some conditions that don’t make sense: OBT u16 + u64 should not become OBT u64.

5

@melver Did we address your concerns?

And others, are there any lingering design concerns? I’m eager to get a PR up on GitHub as I suspect there will be lots of code changes requested over there.

6

More or less. If the semantic pitfall here is documented properly, and if based on empirical results (Linux kernel), this is the right thing to do, then it makes sense. But from an initial reading, it sounded like the narrowing decision was made to work around avoiding technical complexity in the compiler of an alternative (traditional semantics, but still warn somehow).

7

The current implementation of the narrowing semantics doesn’t compromise on functionality, regardless of its simplicity on the compiler side. Of the two implementations that I thought could deliver on the design goals, I opted for the easier one to implement for the compiler but could pivot if reviewers felt strongly about it. If we are in agreement about WHY narrowing semantics are needed for OBTs then the implementation thereof can be handled in code review.

To recap, the big reasons why we need narrowing semantics or a system like it is

  1. to preserve overflow bit boundary information across arithmetic expressions
  2. to give accurate and timely overflow signal
8

Can you go into more detail about what the usual arithmetic conversions are expected to do when trying to pick a common type? Am I correct in understanding that this is basically the opposite to arithmetic conversions for non-__no_wrap types in that __no_wrap types convert to the smallest common type and “regular” types convert to the largest common type? Does the same happen for __wrap types? Also, what happens when the types are the same except for sign (e.g., __no_wrap unsigned short and __no_wrap short)?

9

Trying to cover all bases:

  1. regular, everyday, non-OBT conversions unchanged

  2. OBT conversions between same kind (wrap+wrap, NoWrap+NoWrap) results in larger of two sizes chosen. (i.e. w_u8 + w_u16 = w_16, if same width, unsigned favored over signed)

  3. OBT conversions between differing kinds (wrap+nowrap) results in the nowrap type (regardless of sign or width). Really, intentionally adding no_wrap + wrap should be a compiler warning!

  4. arithmetic between an OBT and a normal integral type results in the type of the OBT being chosen (regardless of sign)

10

Thank you!

So this does not allow for integer promotion? e.g., w_u8 + w_u16 → w_32 + w_32 = w_32

And regardless of width?

I’m bringing these kinds of questions up because I’m worried about subtle behavioral changes as people add _Wrap and _NoWrap to their code. Some folks have an intuition about promotions automatically widening calculations that could be misguided with this feature.

If the mental model is "arithmetic involving a value whose type is _NoWrap means that arithmetic operation will not wrap, then I think this all makes sense. But if the mental model is “modifying this value whose type is _NoWrap will not wrap”, then it seems kind of surprising. e.g.,

_NoWrap signed char sc = 64;
int x = sc + 256;

Is that code intended to wrap/be diagnosed? Or is that only intended for code like:

_NoWrap signed char sc = 64;
sc += 256;
11

This is correct, traditional integer promotions do not apply in this instance. This approach allows us to wrap or warn about overflow on the right bit width.

Yes regardless of width. e.g., w_u8 + u64 = w_u8. Do note that there is an implicit cast from u64 down to w_u8 which could still result in -fsanitize=implicit-unsigned-integer-truncation warnings.

Thanks for thinking deeply about this, your questions and concerns are all valid and really help with the design + documentation of this feature.

Right, but some of the gosh darn arithmetic conversions are sort of why we’re in this predicament in the first place. Arithmetic in C is magic and overflow behavior can be just as confusing. If we make good design decisions and write good documentation, there’s an opportunity to shape the future of safe arithmetic in C with Clang.

The current design matches the former.

Using your example:

This code should be diagnosed; the sc + 256 is arithmetic involving a value whose type is _NoWrap. This is especially crucial behavior for some allocation patterns:

struct foo *allocate_me_some_foos(unsigned char __attribute__((overflow_behavior(no_wrap))) num) {
  return (struct foo*)malloc(num * sizeof(struct foo));
}

Even though num is never re-assigned we are quite interested in whether or not it is involved in overflowing arithmetic.

12

Thank you for the explanation! I think what keeps tripping me up is that the annotation looks exactly like a qualifier but isn’t really about access to the value, it’s about operations involving the value (and perhaps even operations that don’t involve the value). Back to my example:

_NoWrap signed char sc = 64;
int x = sc + 256;

_NoWrap doesn’t mean sc cannot wrap, it means the addition happens in a different width than the usual language rules would use and that operation is not allowed to wrap. And the more complicated the expression, the easier it is to miss that both of those things are happening. e.g.,

_NoWrap signed char sc = 64;
auto x = ((sc + 8) * (12 - foo)) / y;

If sc is the only thing marked _NoWrap, reasoning about the resulting type of x will be challenging and debugging this code may be harder due to the question of which operations are not allowed to wrap. Does this mean 12 - foo could be what eventually gets caught wrapping because _NoWrap propagated from sc due to the qualifier being kind of viral? If so, what about a case where the _NoWrap variable does not contribute to the wrap happening? e.g.,

_NoWrap signed char sc = 0;
int x = 127 + (false ? sc : 1);

If I follow along properly, this would drop the 127 down to _NoWrap signed char which then wraps because of the +1 but sc isn’t actually contributing its value to anything.

13

I’m following what you’re saying and I agree it is problematic on the basis of how confusing it may be. However, limiting the scope to just accesses and stores renders OBTs more or less useless. We run into the same problems that currently exist: less-than-int types literally cannot overflow, we can only diagnose truncation when storing the value; we lose all overflow signal.

I want to find a way forward that maintains good and accurate overflow signal while addressing your concerns about confusing promotion semantics. I fear that attempting to make the compiler smarter when handling arithmetic expressions containing OBTs may just further confuse developers. These types are opt-in and purpose-built, some burden is on the developer to properly utilize the types and understand their semantics. For example, how _Sat _Fract and _BitInt have their own semantic quirks (although I understand they look more like types so it is more permissible).

_BitInt(39) sc;
int foo;
short y;
auto x = ((sc + 8) * (12 - foo)) / y;

You would have to do similar amounts of investigative work to determine the type of x for OBTs and for _BitInt. _BitInt can get a tad bit more confusing when using non-traditional bit widths too! (note that _BitInts don’t narrow exactly like OBTs do so this example is more so for demonstration).

My intention isn’t to bash _BitInt, I just want to demonstrate that purpose-built types can sometimes necessarily carry some semantic baggage to properly serve their purpose. Let’s not use this as an excuse to ship horribly convoluted features, though. We still need good design and documentation.

Correct. This is one of those cases where we could make the compiler smarter and have it pick a better type if it sees the OBT is not used at all but we risk further semantic confusions.

I’ll also note that I’ve attempted to closely match Rust’s Wrapping in std::num - Rust feature set in the sense that all types participating in an arithmetic expression containing a wrapping type must be the same bitwidth (or implement traits for off-width maths). We don’t have traits and other magics in C so narrowing semantics serves the same purpose of getting everything to the same bitwidth.

14

I apologize, I forgot a key point that I brought up (ugh): this looks like a qualifier, but it’s a type specifier. It’s like _Complex float, not like const int. And so it doesn’t have to be about the stores and loads, it makes sense for it to be about the expressions. And reasoning about operations on mixed distinct types is always harder than on operations with the same type, so there’s nothing new here.

Yup, agreed!

So thinking about it again as a type specifier, there are some questions about C++. You’re not allowed to do this:

template <typename Ty>
void func(_Complex Ty i) {}

(Compiler Explorer), which means you cannot do this either:

template <typename Ty>
void func(_NoWrap Ty i) {}

Is that acceptable behavior for you?

But you can overload or specialize based on it, like this:

void func(_NoWrap int i);
void func(int i); // Overload, not invalid redeclaration

template <typename Ty>
struct S {};

template <>
struct S<_NoWrap int> {};

template <>
struct S<int> {};

but this does raise the question: is _Wrap unsigned int the same type as unsigned int? Or is this like char where char, signed char, and unsigned char are distinct types even though char has a default of being either signed or unsigned?

Also, am I correct in understanding that a pointer to a wrap/nowrap type cannot alias with a pointer to a non-wrap/non-nowrap type because the types are distinct? So you cannot do int i = 12; _NoWrap int *j = &i; kind of things?

15

Yes and this is how the current implementation operates. Check out the c++ sema tests. I’ve updated them to include more patterns like that ones you’ve written.

For the purposes of overloading or template specialization, OBTs will choose any that exactly match their type specs. If there isn’t an exact match then it will look for matches on the type without wrapping behavior specified:

void foo(char a) {} // <--- picked
void foo(int a) {}

void bar(__no_wrap char a) {
  foo(a);
}

If there isn’t a match on the exact OBT type or the stripped OBT type then it should default to normal/typical discovery. While writing this up I found a case that my implementation handles potentially poorly:

void foo(__no_wrap int a) {}
void foo(int a) {}
void bar(int b) { foo(b); } // error: call to 'foo' is ambiguous

… there’s an exact match for int but __no_wrap int is offering itself up as a viable option which it probably shouldn’t be, thus creating ambiguity during discovery. As a gut feeling, users probably shouldn’t be overloading based on overflow behavior types alone so maybe this bug is a feature. Let me know what you think and I could get this changed or leave it as is.

This is my idea as well. My current implementation disallows this but only for C++, for some reason. In C, this initialization isn’t an error but it should be and I am trying to fix it now that I am aware of it :slight_smile:

Admittedly, I am not an expert on C++ templating and overloading semantics. Aaron, these cases you’re pointing out are really helpful and valuable. I want to know your thoughts on how I am currently handling the cases you’ve pointed out and maybe other cases you can think of. I am also happy to address any design concerns anyone has.

Note: I’ll be AFK from June 18 to June 30, following my return I want to get a PR up so we can expose and fix implementation flaws.

1 Like
16

I think this situation should lead to an ambiguous overload set, then it behaves more consistently like a type specifier: Compiler Explorer

I’m not certain I agree; if the overload set is formed, there’s an exact match in that set. So either we shouldn’t be forming an overload set or we should be taking the exact match. I think we should take the exact match.

17

When overloading is not in question, do you think we should allow implicit conversions between __no_wrap int and int:

void foo(int a);

int main() {
  __no_wrap int a;
  foo(a);
}

I don’t think this should be an error in C, at worst it’s a warning. However, for C++ what do you think? Check this modified version of your Godbolt example.

I agree, I’ll implement this behavior.

18

That’s a good question! The reason the implicit conversion isn’t allow for _Complex float to float is because of information loss; a complex number isn’t the same as just its real component. But the same information loss isn’t present for __no_wrap, it’s just the operations that are different. But if you allow implicit conversions, then does that mean integer promotions as well? e.g., anywhere an int can be used, we’d drop the __no_wrap. That seems like a bad idea. :smiley:

Because it’s easier to relax an error than it is to introduce one later, maybe we should require explicit conversions initially and see how well that works in practice. The uses in the wild may help inform us whether that was a good decision or whether we should relax it. So int → __other int would allow implicit conversions so you get the correct common type in binary expressions, but __other int → int would require an explicit cast. WDYT?

CC @efriedma-quic for another opinion on this.

19

In the kernel we want size_t to be no_wrap and there exists some cases where a size_t is passed to a function that has a unsigned long, or u64 or other 64-bit unsigned type. So, we’d have to go and fix those up (probably for the best).

Anyways, I’m on board with a warning (then error with -Werror) when overflow behavior is stripped away – maybe -Wimplicitly-discarded-overflow-behavior.

The question now is: should we warn for all cases, or only certain combinations of sign and behaviors?

20

I think that’s a reasonable diagnostic group name.

I think that depends on the use cases you have in mind. To me, it doesn’t make sense to diagnose a wrap size_t when it converts to a size_t because that type allows wrapping anyway. But I could see folks wanting the behavior to be explicitly specified, and so maybe we want a more pedantic form of the diagnostic in addition to one that diagnoses the dangerous behavioral changes.