BPF: avoid same condition evaluated in multiple branch instructions

[yonghong-song]

Summary

This patch specifically tries to address an issue reported at

https://lore.kernel.org/bpf/20200812074826.GB754656@krava/

If one icmp condition is used in more than one places, prevent
this condition from inlining into multiple places.

For example,

cond = a < b 
... 
select cond, val1, val2
... 
br cond, block1, block2

In actually lowering, cond will be put into select_cc and br_cc
so we will have proper cond in the jmp inst.
It is reported this caused the issue if cond happens to be

pkt_ptr < pkt_end

due to particular kernel implementation.
The transformation here is to put a barrier after "cond = a < b"
so cond cannot be inlined into select/br. The pseudo generated code
looks like:

if a < b then
  tmp = 1 
then
  tmp = 0 
... 
if (tmp == 1) val1; else val2
... 
if (tmp == 1) goto block1; else goto block2;

The below llc flag is added to turn off this optimization if needed.

llc -march=bpf -bpf-disable-eval-cond-once t.ll

[yonghong-song]

rebase since https://reviews.llvm.org/D87153 changed

[yonghong-song]

• added tests, added llc option to disable optimization if needed.
• removed RFC tag.

llvm/lib/Target/BPF/BPFCheckAndAdjustIR.cpp

 public:
   static char ID;
   BPFCheckAndAdjustIR() : ModulePass(ID) {}
 
 private:
   void checkIR(Module &M);
   bool adjustIR(Module &M);
   bool removePassThroughBuiltin(Module &M);
+  bool serializeCond(Module &M);
 };
 } // End anonymous namespace
 
 char BPFCheckAndAdjustIR::ID = 0;
 INITIALIZE_PASS(BPFCheckAndAdjustIR, DEBUG_TYPE, "BPF Check And Adjust IR",
                 false, false)
 
 ModulePass *llvm::createBPFCheckAndAdjustIR() {
for (auto &BB : F)
         Changed = true;
         Value *Arg = Call->getArgOperand(1);
         Call->replaceAllUsesWith(Arg);
         ToBeDeleted = Call;
       }
   return Changed;
 }
 
+bool BPFCheckAndAdjustIR::serializeCond(Module &M) {
+  // Forcing to lower an icmp condition if it is used
+  // in multiple places.
+  // For:
+  //   icmp1 = ...
+  //   ...
+  //   a = select icmp1, val1, val2
+  //   ...
+  //   ... icmp1 ...
+  // Change to:
+  //   icmp1 = ...
+  //   icmp1 = user_asm_barrier(icmp1)
+  //   ...
+  //   a = select icmp1, val1, val2
+  //   ...
+  //   ... icmp1 ...
+  SmallVector<ICmpInst *, 16> Candidates;
+  for (Function &F : M)
+    for (auto &BB : F)
+      for (auto &I : BB) {
+        auto *Cond = dyn_cast<ICmpInst>(&I);
+        if (!Cond || Cond->use_empty() || Cond->hasOneUse())
+          continue;
+        Candidates.push_back(Cond);
+      }
+
+  if (Candidates.empty())
+    return false;
+
+  bool Changed = false;
+  for (auto *Cond : Candidates) {
+    SmallVector<Instruction *, 16> Uses;
+    for (User *U : Cond->users()) {
+      Instruction *Inst = dyn_cast<Instruction>(U);
+      if (!Inst || (!isa<SelectInst>(Inst) && !isa<BranchInst>(Inst)))
+        continue;
+      Uses.push_back(Inst);
+    }
+    if (Uses.size() < 2)
+      continue;
+
+    Changed = true;
+    Instruction *NextI = Cond->getNextNonDebugInstruction();
+    assert(NextI);
+    FunctionType *AsmTy = FunctionType::get(Cond->getType(), {Cond->getType()}, false);
+    InlineAsm *Asm = InlineAsm::get(AsmTy, StringRef(""), StringRef("=r,0"), true);
+    auto *CI = CallInst::Create(Asm, {Cond}, "", NextI);
+    for (Instruction *Inst : Uses) {
+      Inst->setOperand(0, CI);
+    }
+  }
+
+  return Changed;
+}
+
 bool BPFCheckAndAdjustIR::adjustIR(Module &M) {
-  return removePassThroughBuiltin(M);
+  bool Changed = false;
+
+  Changed = removePassThroughBuiltin(M);
+  Changed = serializeCond(M) || Changed;
+  return Changed;
 }
 
 bool BPFCheckAndAdjustIR::runOnModule(Module &M) {
   checkIR(M);
   return adjustIR(M);
 }