[BPF] Adjust optimizations to generate kernel verifier friendly codes

[yonghong-song]

Summary

The InstCombine phase did the following optimization:

V >= Lo && V <  Hi --> V - Lo u<  Hi - Lo
V <  Lo || V >= Hi --> V - Lo u>= Hi - Lo

This generates code like below:

V.off  = V - Lo
ConstV = Hi - Lo
Cond = V.off u< ConstV
if (Cond) ... 
... V is used ...

The current linux verifier is not able to handle such a sequence
and may reject the prog as it did not used refined value range
for V at the place of "V is used".

Previous attempt, https://reviews.llvm.org/D70372, is to disable
this optimization under BPF target. But it violates the principle
that InstCombiner is target independent.

This patch implemented an IR pass to make the code more friendly
to the verifier. The IR pass will transform the undo the above
InstCombine optimization.

V - Lo u< Hi - Lo --> V >= Lo && V < Hi
V - Lo u>= Hi - Lo --> V < Lo || V >= Hi

In addition, the following two cases are also handled.

V - Lo u<= Hi - Lo --> V >= Lo && V <= Hi
V - Lo u> Hi - Lo --> V <  Lo || V > Hi

As a concrete example, the source code:

#pragma clang loop unroll(disable)
for (i = 0; i < 100; ++i) {
  ret = ext_test(value + off);
  if (ret <= 0 || ret > 7)
    return 0;
  off += ret & 7;
}

The assembly code with -mcpu=v3:

LBB0_1:
        r1 = value ll
        r1 += r6
        call ext_test
        if w0 s< 1 goto LBB0_4
        if w0 s> 7 goto LBB0_4
        r1 = w0
        r1 <<= 32
        r1 >>= 32
        r6 += r1
        w7 += -1
        if w7 != 0 goto LBB0_1

[yonghong-song]

The current kernel did not handle signed compare well for 32bit registers. I will need to make that change first in order to make this llvm change effective.

[ast]

looks fine. could you run it against kernel selftests and check when it triggers? since verifier cannot handle the optimized code there should be almost no cases of reverse transformation.
And if there are then add them as .ll tests?

[yonghong-song]

Indeed tried kernel selftests, revert the previous workaround like

diff --git a/tools/testing/selftests/bpf/progs/test_sysctl_loop1.c b/tools/testing/selftests/bpf/progs/test_sysctl_loop1.c
index d22e438198cf..608a06871572 100644
--- a/tools/testing/selftests/bpf/progs/test_sysctl_loop1.c
+++ b/tools/testing/selftests/bpf/progs/test_sysctl_loop1.c
@@ -44,10 +44,7 @@ int sysctl_tcp_mem(struct bpf_sysctl *ctx)
        unsigned long tcp_mem[TCP_MEM_LOOPS] = {};
        char value[MAX_VALUE_STR_LEN];
        unsigned char i, off = 0;
-       /* a workaround to prevent compiler from generating
-        * codes verifier cannot handle yet.
-        */
-       volatile int ret;
+       int ret;
 
        if (ctx->write)
                return 0;

The optimization kicked in. The adjust-instcombine-1.ll is exactly for the above case. But kernel verifier needs some work to handle 32bit sign comparisons, which I will work on later.

The adjust-instcombine-2.ll is also derived from a real use case inside Facebook.

[yonghong-song]

fix potential overflow issues

[yonghong-song]

Added a machineinstr SSA target phase to add left/aright shift operations if the 32bit subregister is used for sle/slt/sge/sgt operations.

[ast]

llvm/lib/Target/BPF/BPFMIAdjustOpt.cpp

78 ↗

(On Diff #238927)

I'm not sure that is correct. Reading lower 32-bit doesn't clear upper bits. I think pattern matching would need to consider the origin of w0. It's not a guarantee that it came as return from a function.
I think teaching verifier to understand this is a better option.

[yonghong-song]

llvm/lib/Target/BPF/BPFMIAdjustOpt.cpp

78 ↗

(On Diff #238927)

good point. the use case is from the function return and then use w0 after that. I want to try verifier because it is tricky to get it 100% right as so many things tangled together. But maybe in verifier we do want 32bit register tracking. The work may help other potential 32bit related issues.

[tstellar]

I may not quite understand what the verifier is looking for here, but rather than trying to undo the optimization in 2 different places, would it be possible to implement this by having the InstructionSelector emit some kind of Pseudo Instruction for inputs to the comparison? For example, what would normally be selected to:

if w0 s< 1 goto LBB0_4

You could instead emit:

w0 = verify_range w0
if w0 s< 1 goto LBB0_4

verify_range would be a pseudo instruction that gets expanded to a real instruction either by ExpandPostRAPseudo or during MC lowering.

This seems like it would be more simple to implement and also more robust.

[yonghong-song]

@tstellar Thanks for your comments. The MachineInstr SSA based optimization is really a ugly hack. Currently verifier is not able to verify the program correctly, i.e., rejects the program for certain patterns related subregister uses. The commit message provides more information. @ast suggested to look at whether we can improve kernel verifier and I will take a look there. If kernel can be enhanced, I will drop the second MachineInstr SSA pass.

[yonghong-song]

revert back to previous version where no hacking with machine IR optimization to add extra "<<" and "s>>". Will try to enhance verifier to do the work.

[yonghong-song]

previous version has runtime failure with latest code base. Fixed the issue and reload the working code.

[anakryiko]

V >= Lo && V < Hi --> V - Lo u< Hi - Lo
V < Lo || V >= Hi --> V - Lo u>= Hi - Lo

Isn't the following possible as well?

V >= Lo && V <= Hi --> V - Lo u<= Hi - Lo
V < Lo || V > Hi --> V - Lo u> Hi - Lo

Should the code handle them as well?

[yonghong-song]

In D72787#2083897, @anakryiko wrote:

V >= Lo && V < Hi --> V - Lo u< Hi - Lo
V < Lo || V >= Hi --> V - Lo u>= Hi - Lo

Isn't the following possible as well?

V >= Lo && V <= Hi --> V - Lo u<= Hi - Lo
V < Lo || V > Hi --> V - Lo u> Hi - Lo

Should the code handle them as well?

This is actually handled. If you have code like

if (v > 0) { if (v <= 16) ...}

The compiler will first transform it to

if (v >= 1) { if (v <= 17) ... }

and then do the above transformation.
With the pre-transformation, you limit the downword cases.

[yonghong-song]

removed MachineInstr AdjustOpt transformation since latest linux 32bit handling has been improved. No need to llvm to generate additional shifts. Also handled two more cases in IR AdjustOpt for

V - Lo u<= Hi - Lo --> V >= Lo && V <= Hi
V - Lo u> Hi - Lo --> V <  Lo || V > Hi

[yonghong-song]

Instead of undoing instcombine optimization, we will implement a BPF IR pass which is called before instcombine to modifying IR to prevent the optimization. So abandon this revision now.

llvm/lib/Target/BPF/BPF.h

 #define LLVM_LIB_TARGET_BPF_BPF_H
 
 #include "MCTargetDesc/BPFMCTargetDesc.h"
 #include "llvm/Target/TargetMachine.h"
 
 namespace llvm {
 class BPFTargetMachine;
 
+ModulePass *createBPFAdjustOpt();
 ModulePass *createBPFAbstractMemberAccess(BPFTargetMachine *TM);
 
 FunctionPass *createBPFISelDag(BPFTargetMachine &TM);
 FunctionPass *createBPFMISimplifyPatchablePass();
 FunctionPass *createBPFMIPeepholePass();
 FunctionPass *createBPFMIPeepholeTruncElimPass();
 FunctionPass *createBPFMIPreEmitPeepholePass();
 FunctionPass *createBPFMIPreEmitCheckingPass();
 
+void initializeBPFAdjustOptPass(PassRegistry&);
 void initializeBPFAbstractMemberAccessPass(PassRegistry&);
 void initializeBPFMISimplifyPatchablePass(PassRegistry&);
 void initializeBPFMIPeepholePass(PassRegistry&);
 void initializeBPFMIPeepholeTruncElimPass(PassRegistry&);
 void initializeBPFMIPreEmitPeepholePass(PassRegistry&);
 void initializeBPFMIPreEmitCheckingPass(PassRegistry&);
 }
 
 #endif

llvm/lib/Target/BPF/BPFAdjustOpt.cpp

+//===---------------- BPFAdjustOpt.cpp - Adjust Optimization --------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Adjust optimization to make the code more kernel verifier friendly.
+// For example, the following optimization is undone:
+//   - InstCombineAndOrXor
+//
+//===----------------------------------------------------------------------===//
+
+#include "BPF.h"
+#include "BPFTargetMachine.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+
+#define DEBUG_TYPE "bpf-adjust-opt"
+
+using namespace llvm;
+
+namespace {
+
+class BPFAdjustOpt final : public ModulePass {
+  StringRef getPassName() const override {
+    return "BPF Adjust Optimization";
+  }
+
+  bool runOnModule(Module &M) override;
+
+public:
+  static char ID;
+  BPFAdjustOpt() : ModulePass(ID) {}
+
+private:
+  bool adjustOpt(Module &M);
+  bool adjustInstCombine(Module &M, Function &F);
+};
+} // End anonymous namespace
+
+char BPFAdjustOpt::ID = 0;
+INITIALIZE_PASS(BPFAdjustOpt, DEBUG_TYPE, "adjust optimization", false, false)
+
+ModulePass *llvm::createBPFAdjustOpt() {
+  return new BPFAdjustOpt();
+}
+
+bool BPFAdjustOpt::runOnModule(Module &M) {
+  LLVM_DEBUG(dbgs() << "********** Adjust Optimization **********\n");
+
+  return adjustOpt(M);
+}
+
+bool BPFAdjustOpt::adjustInstCombine(Module &M, Function &F) {
+  bool Changed = false;
+
+  for (auto &BB : F)
+    for (auto &I : BB) {
+      if (I.getNumUses() <= 1)
+        continue;
+
+      // The instruction has more than one use.
+      // Check whether one use is in a path refined by the
+      // InstCombine, and undo the optimization.
+      //   V - Lo u<= Hi - Lo --> V >= Lo && V <= Hi
+      //   V - Lo u>  Hi - Lo --> V <  Lo || V >  Hi
+      for (User *U : I.users()) {
+        // First instruction (ArithInst): tmp = V - Lo or tmp = V + -Lo
+        auto *ArithInst = dyn_cast<Instruction>(U);
+        if (!ArithInst || !ArithInst->hasOneUse())
+          continue;
+
+        if (ArithInst->getOpcode() != Instruction::Sub &&
+            ArithInst->getOpcode() != Instruction::Add)
+          continue;
+
+        const auto *CV = dyn_cast<ConstantInt>(ArithInst->getOperand(1));
+        if (!CV)
+          continue;
+
+        int64_t ValLo = CV->getValue().getSExtValue();
+        if (ArithInst->getOpcode() == Instruction::Add)
+          ValLo = -ValLo;
+
+        // Second instruction (CmpInst): tmp u<= (Hi - Lo) or tmp u> (Hi - Lo)
+        auto *CmpInst = dyn_cast<ICmpInst>(*ArithInst->user_begin());
+        if (!CmpInst)
+          continue;
+
+        if (CmpInst->getPredicate() != ICmpInst::ICMP_UGT &&
+            CmpInst->getPredicate() != ICmpInst::ICMP_ULE)
+          continue;
+
+        CV = dyn_cast<ConstantInt>(CmpInst->getOperand(1));
+        if (!CV)
+          continue;
+
+        int64_t ValHi = ValLo + CV->getValue().getSExtValue();
+        if (ValHi <= ValLo || ValHi < INT_MIN || ValHi > INT_MAX)
+          continue;
+
+        Value *NewValLo = ConstantInt::get(CV->getType(), ValLo);
+        Value *NewValHi = ConstantInt::get(CV->getType(), ValHi);
+
+        // Add new instructions right before ArithInst
+        IRBuilder<> Builder(ArithInst);
+        if (CmpInst->getPredicate() == ICmpInst::ICMP_UGT) {
+          //   %call: I
+          //   %cmp1 = icmp slt i32 %call, Lo
+          //   %cmp2 = icmp sgt i32 %call, Hi
+          //   %or.cond = or i1 %cmp1, %cmp2
+          //   replace all users of CmpInst with %or.cond
+          Value *Cmp1 = Builder.CreateICmpSLT(&I, NewValLo);
+          Value *Cmp2 = Builder.CreateICmpSGT(&I, NewValHi);
+          Value *OrCond = Builder.CreateOr(Cmp1, Cmp2);
+          CmpInst->replaceAllUsesWith(OrCond);
+        } else {
+          //   %call: I
+          //   %cmp1 = icmp sge i32 %call, Lo
+          //   %cmp2 = icmp sle i32 %call, Hi
+          //   %and.cond = and i1 %cmp1, %cmp2
+          //   replace all users of CmpInst with %and.cond
+          Value *Cmp1 = Builder.CreateICmpSGE(&I, NewValLo);
+          Value *Cmp2 = Builder.CreateICmpSLE(&I, NewValHi);
+          Value *AndCond = Builder.CreateAnd(Cmp1, Cmp2);
+          CmpInst->replaceAllUsesWith(AndCond);
+        }
+
+        CmpInst->eraseFromParent();
+        ArithInst->eraseFromParent();
+
+        Changed = true;
+      }
+    }
+
+  return Changed;
+}
+
+bool BPFAdjustOpt::adjustOpt(Module &M) {
+  bool Changed = false;
+
+  for (Function &F : M) {
+    Changed = adjustInstCombine(M, F) || Changed;
+  }
+
+  return Changed;
+}

llvm/lib/Target/BPF/BPFTargetMachine.cpp

 
 extern "C" LLVM_EXTERNAL_VISIBILITY void LLVMInitializeBPFTarget() {
   // Register the target.
   RegisterTargetMachine<BPFTargetMachine> X(getTheBPFleTarget());
   RegisterTargetMachine<BPFTargetMachine> Y(getTheBPFbeTarget());
   RegisterTargetMachine<BPFTargetMachine> Z(getTheBPFTarget());
 
   PassRegistry &PR = *PassRegistry::getPassRegistry();
+  initializeBPFAdjustOptPass(PR);
   initializeBPFAbstractMemberAccessPass(PR);
   initializeBPFMIPeepholePass(PR);
   initializeBPFMIPeepholeTruncElimPass(PR);
 }
 
 // DataLayout: little or big endian
 static std::string computeDataLayout(const Triple &TT) {
   if (TT.getArch() == Triple::bpfeb)

 }
 
 TargetPassConfig *BPFTargetMachine::createPassConfig(PassManagerBase &PM) {
   return new BPFPassConfig(*this, PM);
 }
 
 void BPFPassConfig::addIRPasses() {
 
+  addPass(createBPFAdjustOpt());
   addPass(createBPFAbstractMemberAccess(&getBPFTargetMachine()));
 
   TargetPassConfig::addIRPasses();
 }
 
 // Install an instruction selector pass using
 // the ISelDag to gen BPF code.
 bool BPFPassConfig::addInstSelector() {

llvm/lib/Target/BPF/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS BPF.td)
 
 tablegen(LLVM BPFGenAsmMatcher.inc -gen-asm-matcher)
 tablegen(LLVM BPFGenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM BPFGenCallingConv.inc -gen-callingconv)
 tablegen(LLVM BPFGenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM BPFGenDisassemblerTables.inc -gen-disassembler)
 tablegen(LLVM BPFGenInstrInfo.inc -gen-instr-info)
 tablegen(LLVM BPFGenMCCodeEmitter.inc -gen-emitter)
 tablegen(LLVM BPFGenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM BPFGenSubtargetInfo.inc -gen-subtarget)
 
 add_public_tablegen_target(BPFCommonTableGen)
 
 add_llvm_target(BPFCodeGen
   BPFAbstractMemberAccess.cpp
+  BPFAdjustOpt.cpp
   BPFAsmPrinter.cpp
   BPFFrameLowering.cpp
   BPFInstrInfo.cpp
   BPFISelDAGToDAG.cpp
   BPFISelLowering.cpp
   BPFMCInstLower.cpp
   BPFRegisterInfo.cpp
   BPFSelectionDAGInfo.cpp

llvm/test/CodeGen/BPF/adjust-instcombine-1.ll

+; RUN: llc < %s -march=bpfel | FileCheck --check-prefix=CHECK %s
+; RUN: llc < %s -march=bpfel -mcpu=v3 | FileCheck --check-prefix=CHECK-V3 %s
+;
+; Source Code:
+;   char value[7];
+;   extern int ext_test(void *);
+;   int test() {
+;     int i, ret, off = 0;
+;
+;     #pragma clang loop unroll(disable)
+;     for (i = 0; i < 50; ++i) {
+;       ret = ext_test(value + off);
+;       if (ret <= 0 || ret > 7)
+;         return 0;
+;       off += ret & 7;
+;     }
+;     return 0;
+;   }
+; Compilation flag:
+;   clang -target bpf -O2 -S -emit-llvm test.c
+
+@value = common dso_local global [7 x i8] zeroinitializer, align 1
+; Function Attrs: nounwind
+define dso_local i32 @test() local_unnamed_addr #0 {
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %if.end, %entry
+  %off.013 = phi i32 [ 0, %entry ], [ %add, %if.end ]
+  %i.012 = phi i32 [ 0, %entry ], [ %inc, %if.end ]
+  %idx.ext = zext i32 %off.013 to i64
+  %add.ptr = getelementptr inbounds [7 x i8], [7 x i8]* @value, i64 0, i64 %idx.ext
+  %call = tail call i32 @ext_test(i8* nonnull %add.ptr) #2
+  %call.off = add i32 %call, -1
+  %0 = icmp ugt i32 %call.off, 6
+  br i1 %0, label %cleanup, label %if.end
+; CHECK:    r[[VAL1:[0-9]+]] = 1
+; CHECK:    if r[[VAL1]] s> r[[BASER:[0-9]+]]
+; CHECK:    if r[[BASER]] s> 7
+; CHECK-V3: if w[[BASEW:[0-9]+]] s< 1
+; CHECK-V3: if w[[BASEW]] s> 7
+
+if.end:                                           ; preds = %for.body
+  %add = add nuw nsw i32 %call, %off.013
+  %inc = add nuw nsw i32 %i.012, 1
+  %exitcond = icmp eq i32 %inc, 50
+  br i1 %exitcond, label %cleanup, label %for.body, !llvm.loop !2
+
+cleanup:                                          ; preds = %if.end, %for.body
+  ret i32 0
+}
+declare dso_local i32 @ext_test(i8*) local_unnamed_addr #1
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nounwind }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 11.0.0 (https://github.com/llvm/llvm-project.git ca2e7bed9f7835eec20acfdbabed0617126561aa)"}
+!2 = distinct !{!2, !3}
+!3 = !{!"llvm.loop.unroll.disable"}

llvm/test/CodeGen/BPF/adjust-instcombine-2.ll

+; RUN: llc < %s -march=bpfel | FileCheck --check-prefix=CHECK %s
+; RUN: llc < %s -march=bpfel -mcpu=v3 | FileCheck --check-prefix=CHECK-V3 %s
+;
+; Source Code:
+;   int ext_test(int);
+;   int test(int *len) {
+;     char options[10] = {};
+;     int options_len = *len;
+;     if (options_len < 4 || options_len > 10) return 0;
+;     return ext_test(options_len);
+;   }
+; Compilation flag:
+;   clang -target bpf -O2 -S -emit-llvm test.c
+
+; Function Attrs: nounwind
+define dso_local i32 @test(i32* nocapture readonly %len) local_unnamed_addr #0 {
+entry:
+  %0 = load i32, i32* %len, align 4, !tbaa !2
+  %.off = add i32 %0, -4
+  %1 = icmp ugt i32 %.off, 6
+  br i1 %1, label %cleanup, label %if.end
+
+; CHECK:    r[[VAL4:[0-9]+]] = 4
+; CHECK:    if r[[VAL4]] s> r[[BASER:[0-9]+]]
+; CHECK:    if r[[BASER]] s> 10
+; CHECK-V3: if w[[BASEW:[0-9]+]] s< 4
+; CHECK-V3: if w[[BASEW]] s> 10
+
+if.end:                                           ; preds = %entry
+  %call = tail call i32 @ext_test(i32 %0) #2
+  br label %cleanup
+
+cleanup:                                          ; preds = %entry, %if.end
+  %retval.0 = phi i32 [ %call, %if.end ], [ 0, %entry ]
+  ret i32 %retval.0
+}
+declare dso_local i32 @ext_test(i32) local_unnamed_addr #1
+
+attributes #0 = { nounwind "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { nounwind }
+
+!llvm.module.flags = !{!0}
+!llvm.ident = !{!1}
+
+!0 = !{i32 1, !"wchar_size", i32 4}
+!1 = !{!"clang version 11.0.0 (https://github.com/llvm/llvm-project.git ca2e7bed9f7835eec20acfdbabed0617126561aa)"}
+!2 = !{!3, !3, i64 0}
+!3 = !{!"int", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}