BPF: Enable frontend constant folding for VLA size

[yonghong-song]

Summary

Paul Chaignon reported a bpf verifier failure ([1]) due to using
non-ABI register R11. For the test case, llvm11 is okay while
llvm12 and later generates verifier unfriendly code.

The failure is related to variable length array size.
The following mimics the variable length array definition
in the test case:

#define AA 40
struct t { char a[20]; };
void foo(void *); 
int test() {
   const int a = 8;
   char tmp[AA + sizeof(struct t) + a]; 
   foo(tmp);
   ... 
}

Paul helped bisect that the following llvm commit is
responsible:

552c6c232872 ("PR44406: Follow behavior of array bound constant
              folding in more recent versions of GCC.")

Basically, before the above commit, clang frontend did constant
folding for array size "AA + sizeof(struct t) + a" to be 68,
so used alloca for stack allocation. After the above commit,
clang frontend didn't do constant folding for array size
any more, which results in a VLA and "llvm.stacksave"/"llvm.stackrestore"
is generated.

BPF architecture API does not support stack pointer (sp) register.
The LLVM internally used R11 to indicate sp register but it should
not be in the final code. Otherwise, kernel verifier will reject it.

This patch attempts to permit array size constant folding
in clang frontend for BPF target. This allows better code and
better developer experience. Otherwise users will need to manually
recalculate the array size whenever some macro or constant value
changes.

[1] https://lore.kernel.org/bpf/20210809151202.GB1012999@Mem/

[yonghong-song]

• fix clant-format warnings.

[pchaigno]

I tested this patch by running it through Cilium's CI which compiles, loads, and validates the behavior of hundreds of slightly different BPF programs. The tests cover several different kernels and all three BPF instruction set extensions (mcpu={v1,v2,v3}). It did not generate invalid bytecode with the register R11 anymore and the tests did not uncover any other regressions with this patch.

[yonghong-song]

ping. @rsmith could you help take a look at the patch? Thanks!

[yonghong-song]

@rsmith ping again. Could you help take a look at this patch? Thanks!

[yonghong-song]

@rsmith ping again, did you get a time to take a look?

[efriedma]

I'd prefer not to mess with the AST if we don't need to; more differences between targets make it harder to understand any issues that come up. BPF-flavored C already has enough weird differences without adding unnecessary changes.

If all you need is to avoid unnecessary llvm.stacksave calls, can you try messing with CodeGenFunction::EmitAutoVarAlloca?

[yonghong-song]

@efriedma Thanks for suggestion! Let me look at CodeGenFunction::EmitAutoVarAlloca() call instead.

[yonghong-song]

I checked EmitAutoVarAlloca(). It emits the llvm.stacksave() due to

// If the type is variably-modified, emit all the VLA sizes for it.
if (Ty->isVariablyModifiedType())
  EmitVariablyModifiedType(Ty);

Here, in order not to generate llvm.stacksave(), we need to evaluate the array size expression for Ty.
But it is probably not a good idea to re-evaluate Ty during code generation phase. If we really want to evaluate, we should evaluate earlier during semantic analysis phase like this patch.

Another solution is to implement pruning llvm.stacksave/stackrestore in backend. Currently InstCombine phase tries to remove some adjacent stacksave() and stackrestore() instrinsics. We could try to enhance InstCombine to handle more complicated cases, or considering this may be just a BPF use case (which doesn't support dynamic memory allocation), we can implement a bpf backend IR phase to remove it.

[pchaigno]

@efriedma @rsmith Did you get a chance to take a look? This regression is still affecting LLVM, including the recently released v13.0.0.

[efriedma]

I don't think my opinion has changed here. I'm against the solution proposed in this patch. The other solutions discussed in the review seem fine. (The simplest is just to make the bpf backend ignore stacksave/stackrestore calls.)

[yonghong-song]

@pchaigno as @efriedma suggested, we can add some transformation in BPF target IR passes to ignore @llvm.stacksave() and @llvm.stackrestore(). I should have a patch ready soon.

[yonghong-song]

@pchaigno @efriedma I added an IR pass in BPF backend to remove these stacksave/stackrestore intrinsics. https://reviews.llvm.org/D111897
@pchaigno Could you test with https://reviews.llvm.org/D111897 instead?

clang/lib/Sema/SemaType.cpp

 
 /// Check whether the specified array bound can be evaluated using the relevant
 /// language rules. If so, returns the possibly-converted expression and sets
 /// SizeVal to the size. If not, but the expression might be a VLA bound,
 /// returns ExprResult(). Otherwise, produces a diagnostic and returns
 /// ExprError().
 static ExprResult checkArraySize(Sema &S, Expr *&ArraySize,
                                  llvm::APSInt &SizeVal, unsigned VLADiag,
-                                 bool VLAIsError) {
+                                 bool VLAIsError, Sema::AllowFoldKind CanFold) {
   if (S.getLangOpts().CPlusPlus14 &&
       (VLAIsError ||
        !ArraySize->getType()->isIntegralOrUnscopedEnumerationType())) {
     // C++14 [dcl.array]p1:
     //   The constant-expression shall be a converted constant expression of
     //   type std::size_t.
     //
     // Don't apply this rule if we might be forming a VLA: in that case, we
public:
     }
 
     Sema::SemaDiagnosticBuilder diagnoseFold(Sema &S,
                                              SourceLocation Loc) override {
       return S.Diag(Loc, diag::ext_vla_folded_to_constant);
     }
   } Diagnoser(VLADiag, VLAIsError);
 
-  ExprResult R =
-      S.VerifyIntegerConstantExpression(ArraySize, &SizeVal, Diagnoser);
+  ExprResult R = S.VerifyIntegerConstantExpression(ArraySize, &SizeVal,
+                                                   Diagnoser, CanFold);
   if (Diagnoser.IsVLA)
     return ExprResult();
   return R;
 }
 
 /// Build an array type.
 ///
 /// \param T The type of each element in the array.
if (!getLangOpts().CPlusPlus11 &&
     Diag(ArraySize->getBeginLoc(), diag::err_array_size_non_int)
         << ArraySize->getType() << ArraySize->getSourceRange();
     return QualType();
   }
 
   // VLAs always produce at least a -Wvla diagnostic, sometimes an error.
   unsigned VLADiag;
   bool VLAIsError;
+  AllowFoldKind CanFold = Sema::NoFold;
   if (getLangOpts().OpenCL) {
     // OpenCL v1.2 s6.9.d: variable length arrays are not supported.
     VLADiag = diag::err_opencl_vla;
     VLAIsError = true;
+  } else if (Context.getTargetInfo().getTriple().isBPF()) {
+    // BPF target does not support variable length array, but
+    // we don't force an error here. We will try to do constant
+    // folding for array size as much as possible. LLVM backend
+    // will do some checking and warn users if variable length
+    // array still remains.
+    VLADiag = diag::warn_vla_used;
+    VLAIsError = false;
+    CanFold = Sema::AllowFold;
   } else if (getLangOpts().C99) {
     VLADiag = diag::warn_vla_used;
     VLAIsError = false;
   } else if (isSFINAEContext()) {
     VLADiag = diag::err_vla_in_sfinae;
     VLAIsError = true;
   } else {
     VLADiag = diag::ext_vla;
if (ASM == ArrayType::Star) {
 
       T = Context.getVariableArrayType(T, nullptr, ASM, Quals, Brackets);
     } else {
       T = Context.getIncompleteArrayType(T, ASM, Quals);
     }
   } else if (ArraySize->isTypeDependent() || ArraySize->isValueDependent()) {
     T = Context.getDependentSizedArrayType(T, ArraySize, ASM, Quals, Brackets);
   } else {
-    ExprResult R =
-        checkArraySize(*this, ArraySize, ConstVal, VLADiag, VLAIsError);
+    ExprResult R = checkArraySize(*this, ArraySize, ConstVal, VLADiag,
+                                  VLAIsError, CanFold);
     if (R.isInvalid())
       return QualType();
 
     if (!R.isUsable()) {
       // C99: an array with a non-ICE size is a VLA. We accept any expression
       // that we can fold to a non-zero positive value as a non-VLA as an
       // extension.
       T = Context.getVariableArrayType(T, ArraySize, ASM, Quals, Brackets);

clang/test/CodeGen/bpf-vla.c

+// REQUIRES: bpf-registered-target
+// RUN: %clang -target bpf -emit-llvm -S -g %s -o - | FileCheck %s
+
+#define AA 40
+struct t {
+  char a[20];
+};
+void foo(void *);
+int test() {
+   const int a = 8;
+   char tmp[AA + sizeof(struct t) + a];
+
+// CHECK: define dso_local i32 @test(
+// CHECK: %tmp = alloca [68 x i8], align 1
+// CHECK-NOT: llvm.stacksave
+
+   foo(tmp);
+   return 0;
+}
+
+int test2(int b) {
+   const int a = 8;
+   char tmp[a + b];
+
+// CHECK: define dso_local i32 @test2(
+// CHECK: llvm.stacksave
+   foo(tmp);
+   return 0;
+}

llvm/include/llvm/ADT/Triple.h

bool isAArch64(int PointerWidth) const {
     if (!isAArch64())
       return false;
     return getArch() == Triple::aarch64_32 ||
                    getEnvironment() == Triple::GNUILP32
                ? PointerWidth == 32
                : PointerWidth == 64;
   }
 
+  /// Tests whether the target is BPF (little and big endian).
+  bool isBPF() const {
+    return getArch() == Triple::bpfel || getArch() == Triple::bpfeb;
+  }
+
   /// Tests whether the target is MIPS 32-bit (little and big endian).
   bool isMIPS32() const {
     return getArch() == Triple::mips || getArch() == Triple::mipsel;
   }
 
   /// Tests whether the target is MIPS 64-bit (little and big endian).
   bool isMIPS64() const {
     return getArch() == Triple::mips64 || getArch() == Triple::mips64el;