Shafik Yaghmour

Compiler Engineer at Intel. This is a personal blog. The opinions stated here are my own, not those of my company.

Exploring Clangs Enum implementation and How we Catch Undefined Behavior

15 Nov 2022 » C++

Intro

In Part 1: Enums In C++, Choice is Oft Beguiled I talked about how enums work in C++ and the various choices we have. If you are not familiar with how enums work reading part 1 will help you to understand part 2.

In this part we will dive into some of the clang internals for tracking the range of values of an enum and how it is used by UBSan and the optimizer. Finally we will look at constant expressions and a recent set of patches I landed to diagnose undefined behavior.

Keeping Track of Positive and Negative Bits

In clang for an enum without a fixed underlying type we need to track the range of values it can represent. In the AST we represent an enum using an EnumDecl which is a DeclContext and within the DeclContext we have NumPositiveBits and NumNegativeBits. These fields are part of the class EnumDeclBitfields which is part of anonymous union used as a Sum Type to represent the various bits used by the various derived classes of DeclContext:

 class EnumDeclBitfields {

    ...

    /// Width in bits required to store all the non-negative
    /// enumerators of this enum.
    uint64_t NumPositiveBits : 8;

    /// Width in bits required to store all the negative
    /// enumerators of this enum.
    uint64_t NumNegativeBits : 8;

    ...

When we are processing the body of the enum in Sema::ActOnEnumBody(...) we use the following code to calculate the positive and negative bits:

  unsigned NumNegativeBits = 0;
  unsigned NumPositiveBits = 0;

  for (unsigned i = 0, e = Elements.size(); i != e; ++i) {
    EnumConstantDecl *ECD =
      cast_or_null<EnumConstantDecl>(Elements[i]);
    if (!ECD) continue;  // Already issued a diagnostic.

    const llvm::APSInt &InitVal = ECD->getInitVal();

    // Keep track of the size of positive and negative values.
    if (InitVal.isUnsigned() || InitVal.isNonNegative()) {
      // If the enumerator is zero that should still be counted as a positive
      // bit since we need a bit to store the value zero.
      unsigned ActiveBits = InitVal.getActiveBits();
      NumPositiveBits = std::max({NumPositiveBits, ActiveBits, 1u});
    } else {
      NumNegativeBits = std::max(NumNegativeBits,
                                 (unsigned)InitVal.getMinSignedBits());
    }
  }

  // If we have have an empty set of enumerators we still need one bit.
  // From [dcl.enum]p8
  // If the enumerator-list is empty, the values of the enumeration are as if
  // the enumeration had a single enumerator with value 0
  if (!NumPositiveBits && !NumNegativeBits)
    NumPositiveBits = 1;

For each enumerator we will calculate the highest bit required to represent the enumerator. If it is positive value we will update NumPositiveBits and if it is negative value we will update NumNegativeBits. At the end if we have no enumerators it will treat it as-if we had a single enumerator of value 0 and set NumPositiveBits to 1.

UBSan

Since we know the number of positive and negative bits required to represent all the enumerators we can calculate the range of underlying values for an enum without a fixed underlying type. EnumDecl provides a member function getValueRange(...) which calculate the maximum and minimum values inclusive:

void EnumDecl::getValueRange(llvm::APInt &Max, llvm::APInt &Min) const {
  unsigned Bitwidth = getASTContext().getIntWidth(getIntegerType());
  unsigned NumNegativeBits = getNumNegativeBits();
  unsigned NumPositiveBits = getNumPositiveBits();

  if (NumNegativeBits) {
    unsigned NumBits = std::max(NumNegativeBits, NumPositiveBits + 1);
    Max = llvm::APInt(Bitwidth, 1) << (NumBits - 1);
    Min = -Max;
  } else {
    Max = llvm::APInt(Bitwidth, 1) << NumPositiveBits;
    Min = llvm::APInt::getZero(Bitwidth);
  }
}

This is important to be able to calculate this range because if we use static_cast to convert an integral or enumeration type to an enumeration type that does not have a fixed underlying type then the resulting value must be within the range of values of the enumeration, otherwise it invokes undefined behavior, see [expr.static.cast]p10 which says:

If the enumeration type does not have a fixed underlying type, the value is unchanged, if the original value is within the range of the enumeration values ([dcl.enum]), and otherwise, the behavior is undefined

For example:

enum E1 {e1=0};             // Range of values [0,1]

void f() {
  E1 x = static_cast<E1>(2); // undefined behavior, 2 is outside the range of values
}

We can catch this using UBSan which will detect the undefined behavior when loading the value of the enumeration (see it live):

enum E1 {e1=0};             // Range of values [0,1]

int main() {
  E1 x = static_cast<E1>(2); // undefined behavior, 2 is outside the range of values
  return x; // UBSan will catch that we are loading a value outside the range
}

UBSan uses getValueRange(...) through getRangeForType(...) to generate icmp bound checks, for example (see it live):

enum E1 {e1=-1,e2=1};             // Range of values [-2,1]

int main() {
  E1 e = static_cast<E1>(8);
  return e; // When -fsanitize=enum is enabled the load of value
            // will cause range check to be generated
}

Results in the following IR to be generated to enable checking the enum value is valid:

%1 = icmp sle i32 %0, 1, !dbg !23, !nosanitize !20  ; Check max bound
%2 = icmp sge i32 %0, -2, !dbg !23, !nosanitize !20 ; Check min bound
%3 = and i1 %1, %2, !dbg !23, !nosanitize !20       ; Combine checks into a single boolean value
                                                    ; Next if checks fails branch to invalid value handler
br i1 %3, label %cont, label %handler.load_invalid_value, !dbg !23, !prof !24, !nosanitize !20

LLVM Range Info

The enum range information is can also be used by the optimizer. If we look at the LLVM language reference for range meta data it says:

range metadata may be attached only to load, call and invoke of integer types. It expresses the possible ranges the loaded value or the value returned by the called function at this call site is in. If the loaded or returned value is not in the specified range, the behavior is undefined.

If we take the previous example and use -fstrict-enums combined with optimization level -O1 or greater during code generation range meta data will be attached to the load of the enum values. We need to also use -Xclang -disable-llvm-passes in order to preserve the IR we want to see for this case (see it live):

; Range meta data from !28 applies to this load
%0 = load i32, ptr %e, align 4, !dbg !27, !tbaa !23, !range !28
;; emitted code
; Range meta data tells us the range of values [2,2) or [2,1]
!28 = !{i32 -2, i32 2}

Constant Expression

Operations that invoke undefined behavior in a constant expression context are ill-formed. So just as UBSan will catch assigning a value to enum without a fixed underlying type outside of it’s range we should also expect this to be caught in a constant expression context. While UBSan requires a load of the value before we can catch this specific undefined behavior in a constant expression context we will catch this once the value is assigned (see it live):

enum E1 {e1=0};             // Range of values [0,1]

void f() {
  constexpr E1 x = static_cast<E1>(2); // Ill-formed, invoking undefined behavior is not allowed in
                                       // a constant expression
}

Unfortunately clang was not conforming in this case. I recently worked on a fix for this. The change ended up being too disruptive, so we allowed for a transition period where it could be turned into a warning while fixes were put in place.

We can see from several examples such as this case with a bit-field type or this case Boost MPL where it caught real bugs that had gone unnoticed.

Thank you to those who provided feedback on or reviewed this write-up: Tom Honermann and Rosa Yaghmour.

Of course in the end, all errors are the author’s.