[RFC] Emit assume operands as unevaluated expressions

[Lancern]

A Motivating Example

Let's consider the following over-simplified code as a motivating example:

int foo(const std::vector<int> &v) {
  __builtin_assume(!v.empty());
  return v.at(0);
}

int bar(const std::vector<int> &v) {
  bool empty = v.empty();
  __builtin_assume(!empty);
  return v.at(0);
}

The current clang trunk emits the following code for the two functions above under -O1 :

_Z3fooRKSt6vectorIiSaIiEE:
        mov     rax, qword ptr [rdi]
        mov     rdx, qword ptr [rdi + 8]
        sub     rdx, rax
        je      .LBB0_2
        mov     eax, dword ptr [rax]
        ret
.LBB0_2:
        push    rax
        sar     rdx, 2
        lea     rdi, [rip + .L.str]
        xor     esi, esi
        xor     eax, eax
        call    _ZSt24__throw_out_of_range_fmtPKcz@PLT

_Z3barRKSt6vectorIiSaIiEE:
        mov     rax, qword ptr [rdi]
        mov     eax, dword ptr [rax]
        ret

A bit surprisingly clang (and LLVM) failed to optimize away the boundary check in function foo . The reason could be seen from the warning message clang emits:

<source>:4:20: warning: assumption is ignored because it contains (potential) side-effects [-Wassume]
    4 |   __builtin_assume(!v.empty());
      |                    ^~~~~~~~~~

The __builtin_assume intrinsic function (and equivalently the C++23 [[assume(expr)]] attribute) is special because it explicitly prevents its operand from being evaluated. Thus, if clang determines the assume operand may carry any side effects, it just gives up and won't emit any optimization hints from the assume statement. In function bar , the assume operand is a simple and stupid id-expression which clang knows for sure would be free of side effects, so clang happily generates a load to the local variable and emits a call to @llvm.assume . However, in function foo , the assume operand is a suspicious function call expression which calls a function not explicitly marked as pure. Clang has to be conservative and assumes that the callee might have arbitrary side effects. Thus clang could not safely generate a call to the function, and it has to ignore the assume statement.

It could be tough, if not impossible, to resolve this problem in the original clang CodeGen, since you need to implement some kind of "inlining" to teach CodeGen that the call to vector::empty is free of side effects. I believe this is a case where ClangIR could help.

Potential Solution

I'm writing down some rough ideas about the potential solution for the problem, in the hope that it could become more mature and doable with feedbacks and discussions. This may not be a good solution at all, I'm very open to other approaches as well.

The solution is to emit the assume statement into a new assume operation (let's name it cir.assume_expr here) that contains an "unevaluated" region:

cir.assume_expr {
    %0 = cir.call @std_vector_empty(%v) : (!cir.ptr<!vector>) -> !cir.bool
    cir.yield %0 : !cir.bool
}

The cir.assume_expr operation has a region and no operands. The region is "unevaluated": code within the region will not evaluate with respect to the as-if rule. The region effectively contains code for evaluating the assume operand. The terminating operation of the region must be a cir.yield operation that yields a boolean value.

When lowering, we handle the new operation in the following way:

• If the region is pure (all operations in the region is pure), inline the region before the operation and replace the operation with an assume hint.
• Otherwise, we just discard the operation.

It's pretty straightforward and mimics the original clang behavior.

The interesting part about the new operation is that it allows us to perform "inlining" in the region's code, and this allows us to reason about the purity of the assume operand across functions. AFAIK, @keryell recently is playing around (#1164) on the MLIR inliner with CIR. The inliner could inline the call to vector::empty in the region, which could transform the code above into something similar to:

cir.assume_expr {
    %begin_ptr = cir.get_member %v[0]
    %end_ptr = cir.get_member %v[1]
    %begin = cir.load %begin_ptr
    %end = cir.load %end_ptr
    %size = cir.binop(sub, %end, %begin)
    %zero = cir.const 0
    %0 = cir.cmp(eq, %size, %zero)
    cir.yield %0 : !cir.bool
}

After inlining, the region becomes pure, which enables the lowering of the assume operation.

[keryell]

I think you could solve in a simpler way this problem by involving the current "idiom recognition" and play with abstract interpretation to figure out the semantics of the code instead of looking at implementation details of !v.empty().
It would be just leveraging the current work already done in CIR static analysis to do high-level code optimization, not only bug detection as today.

[Lancern]

I think you could solve in a simpler way this problem by involving the current "idiom recognition" and play with abstract interpretation to figure out the semantics of the code instead of looking at implementation details of !v.empty().

This would be a good way to quickly tackle this problem, but the downside is that this only works for "well-known" (i.e. standard library) function calls that we have to exhaustively enumerate. If the user code calls into non-standard functions and libraries, idiom recognition would not work. Is my understanding correct?

[bcardosolopes]

current "idiom recognition" and play with abstract interpretation to figure out the semantics of the code instead of looking at implementation details of !v.empty().

+1

If the user code calls into non-standard functions and libraries, idiom recognition would not work. Is my understanding correct?

Yep, though in theory we could teach ClangIR about non-standard functions and libraries, as a quick example, we want to this for Folly and I believe others would want to do things like this for their own libraries.

Many folks in the community want something like this and we often discuss about it - yet unclear the best mechanism to do this will be: annotations in the library itself? "inline CIR asm"? JSON file with extra info? Harcoded in the compiler via tablegen? There are multiple routes.