lib/Target/BPF/BPFAdjustOpt.cpp - llvm-project/llvm - Git at Google

 //===---------------- 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.
 //
 //===----------------------------------------------------------------------===//

 #include "BPF.h"
 #include "BPFCORE.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicsBPF.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.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;
 using namespace llvm::PatternMatch;

 static cl::opt<bool>
     DisableBPFserializeICMP("bpf-disable-serialize-icmp", cl::Hidden,
                             cl::desc("BPF: Disable Serializing ICMP insns."),
                             cl::init(false));

 static cl::opt<bool> DisableBPFavoidSpeculation(
     "bpf-disable-avoid-speculation", cl::Hidden,
     cl::desc("BPF: Disable Avoiding Speculative Code Motion."),
     cl::init(false));

 namespace {
 class BPFAdjustOptImpl {
   struct PassThroughInfo {
     Instruction *Input;
     Instruction *UsedInst;
     uint32_t OpIdx;
     PassThroughInfo(Instruction *I, Instruction *U, uint32_t Idx)
         : Input(I), UsedInst(U), OpIdx(Idx) {}
   };

 public:
   BPFAdjustOptImpl(Module *M) : M(M) {}

   bool run();

 private:
   Module *M;
   SmallVector<PassThroughInfo, 16> PassThroughs;

   bool adjustICmpToBuiltin();
   void adjustBasicBlock(BasicBlock &BB);
   bool serializeICMPCrossBB(BasicBlock &BB);
   void adjustInst(Instruction &I);
   bool serializeICMPInBB(Instruction &I);
   bool avoidSpeculation(Instruction &I);
   bool insertPassThrough();
 };

 } // End anonymous namespace

 bool BPFAdjustOptImpl::run() {
   bool Changed = adjustICmpToBuiltin();

   for (Function &F : *M)
     for (auto &BB : F) {
       adjustBasicBlock(BB);
       for (auto &I : BB)
         adjustInst(I);
     }
   return insertPassThrough() || Changed;
 }

 // Commit acabad9ff6bf ("[InstCombine] try to canonicalize icmp with
 // trunc op into mask and cmp") added a transformation to
 // convert "(conv)a < power_2_const" to "a & <const>" in certain
 // cases and bpf kernel verifier has to handle the resulted code
 // conservatively and this may reject otherwise legitimate program.
 // Here, we change related icmp code to a builtin which will
 // be restored to original icmp code later to prevent that
 // InstCombine transformatin.
 bool BPFAdjustOptImpl::adjustICmpToBuiltin() {
   bool Changed = false;
   ICmpInst *ToBeDeleted = nullptr;
   for (Function &F : *M)
     for (auto &BB : F)
       for (auto &I : BB) {
         if (ToBeDeleted) {
           ToBeDeleted->eraseFromParent();
           ToBeDeleted = nullptr;
         }

         auto *Icmp = dyn_cast<ICmpInst>(&I);
         if (!Icmp)
           continue;

         Value *Op0 = Icmp->getOperand(0);
         if (!isa<TruncInst>(Op0))
           continue;

         auto ConstOp1 = dyn_cast<ConstantInt>(Icmp->getOperand(1));
         if (!ConstOp1)
           continue;

         auto ConstOp1Val = ConstOp1->getValue().getZExtValue();
         auto Op = Icmp->getPredicate();
         if (Op == ICmpInst::ICMP_ULT || Op == ICmpInst::ICMP_UGE) {
           if ((ConstOp1Val - 1) & ConstOp1Val)
             continue;
         } else if (Op == ICmpInst::ICMP_ULE || Op == ICmpInst::ICMP_UGT) {
           if (ConstOp1Val & (ConstOp1Val + 1))
             continue;
         } else {
           continue;
         }

         Constant *Opcode =
             ConstantInt::get(Type::getInt32Ty(BB.getContext()), Op);
         Function *Fn = Intrinsic::getOrInsertDeclaration(
             M, Intrinsic::bpf_compare, {Op0->getType(), ConstOp1->getType()});
         auto *NewInst = CallInst::Create(Fn, {Opcode, Op0, ConstOp1});
         NewInst->insertBefore(I.getIterator());
         Icmp->replaceAllUsesWith(NewInst);
         Changed = true;
         ToBeDeleted = Icmp;
       }

   return Changed;
 }

 bool BPFAdjustOptImpl::insertPassThrough() {
   for (auto &Info : PassThroughs) {
     auto *CI = BPFCoreSharedInfo::insertPassThrough(
         M, Info.UsedInst->getParent(), Info.Input, Info.UsedInst);
     Info.UsedInst->setOperand(Info.OpIdx, CI);
   }

   return !PassThroughs.empty();
 }

 // To avoid combining conditionals in the same basic block by
 // instrcombine optimization.
 bool BPFAdjustOptImpl::serializeICMPInBB(Instruction &I) {
   // For:
   //   comp1 = icmp <opcode> ...;
   //   comp2 = icmp <opcode> ...;
   //   ... or comp1 comp2 ...
   // changed to:
   //   comp1 = icmp <opcode> ...;
   //   comp2 = icmp <opcode> ...;
   //   new_comp1 = __builtin_bpf_passthrough(seq_num, comp1)
   //   ... or new_comp1 comp2 ...
   Value *Op0, *Op1;
   // Use LogicalOr (accept `or i1` as well as `select i1 Op0, true, Op1`)
   if (!match(&I, m_LogicalOr(m_Value(Op0), m_Value(Op1))))
     return false;
   auto *Icmp1 = dyn_cast<ICmpInst>(Op0);
   if (!Icmp1)
     return false;
   auto *Icmp2 = dyn_cast<ICmpInst>(Op1);
   if (!Icmp2)
     return false;

   Value *Icmp1Op0 = Icmp1->getOperand(0);
   Value *Icmp2Op0 = Icmp2->getOperand(0);
   if (Icmp1Op0 != Icmp2Op0)
     return false;

   // Now we got two icmp instructions which feed into
   // an "or" instruction.
   PassThroughInfo Info(Icmp1, &I, 0);
   PassThroughs.push_back(Info);
   return true;
 }

 // To avoid combining conditionals in the same basic block by
 // instrcombine optimization.
 bool BPFAdjustOptImpl::serializeICMPCrossBB(BasicBlock &BB) {
   // For:
   //   B1:
   //     comp1 = icmp <opcode> ...;
   //     if (comp1) goto B2 else B3;
   //   B2:
   //     comp2 = icmp <opcode> ...;
   //     if (comp2) goto B4 else B5;
   //   B4:
   //     ...
   // changed to:
   //   B1:
   //     comp1 = icmp <opcode> ...;
   //     comp1 = __builtin_bpf_passthrough(seq_num, comp1);
   //     if (comp1) goto B2 else B3;
   //   B2:
   //     comp2 = icmp <opcode> ...;
   //     if (comp2) goto B4 else B5;
   //   B4:
   //     ...

   // Check basic predecessors, if two of them (say B1, B2) are using
   // icmp instructions to generate conditions and one is the predesessor
   // of another (e.g., B1 is the predecessor of B2). Add a passthrough
   // barrier after icmp inst of block B1.
   BasicBlock *B2 = BB.getSinglePredecessor();
   if (!B2)
     return false;

   BasicBlock *B1 = B2->getSinglePredecessor();
   if (!B1)
     return false;

   Instruction *TI = B2->getTerminator();
   auto *BI = dyn_cast<BranchInst>(TI);
   if (!BI || !BI->isConditional())
     return false;
   auto *Cond = dyn_cast<ICmpInst>(BI->getCondition());
   if (!Cond || &*B2->getFirstNonPHIIt() != Cond)
     return false;
   Value *B2Op0 = Cond->getOperand(0);
   auto Cond2Op = Cond->getPredicate();

   TI = B1->getTerminator();
   BI = dyn_cast<BranchInst>(TI);
   if (!BI || !BI->isConditional())
     return false;
   Cond = dyn_cast<ICmpInst>(BI->getCondition());
   if (!Cond)
     return false;
   Value *B1Op0 = Cond->getOperand(0);
   auto Cond1Op = Cond->getPredicate();

   if (B1Op0 != B2Op0)
     return false;

   if (Cond1Op == ICmpInst::ICMP_SGT || Cond1Op == ICmpInst::ICMP_SGE) {
     if (Cond2Op != ICmpInst::ICMP_SLT && Cond2Op != ICmpInst::ICMP_SLE)
       return false;
   } else if (Cond1Op == ICmpInst::ICMP_SLT || Cond1Op == ICmpInst::ICMP_SLE) {
     if (Cond2Op != ICmpInst::ICMP_SGT && Cond2Op != ICmpInst::ICMP_SGE)
       return false;
   } else if (Cond1Op == ICmpInst::ICMP_ULT || Cond1Op == ICmpInst::ICMP_ULE) {
     if (Cond2Op != ICmpInst::ICMP_UGT && Cond2Op != ICmpInst::ICMP_UGE)
       return false;
   } else if (Cond1Op == ICmpInst::ICMP_UGT || Cond1Op == ICmpInst::ICMP_UGE) {
     if (Cond2Op != ICmpInst::ICMP_ULT && Cond2Op != ICmpInst::ICMP_ULE)
       return false;
   } else {
     return false;
   }

   PassThroughInfo Info(Cond, BI, 0);
   PassThroughs.push_back(Info);

   return true;
 }

 // To avoid speculative hoisting certain computations out of
 // a basic block.
 bool BPFAdjustOptImpl::avoidSpeculation(Instruction &I) {
   if (auto *LdInst = dyn_cast<LoadInst>(&I)) {
     if (auto *GV = dyn_cast<GlobalVariable>(LdInst->getOperand(0))) {
       if (GV->hasAttribute(BPFCoreSharedInfo::AmaAttr) ||
           GV->hasAttribute(BPFCoreSharedInfo::TypeIdAttr))
         return false;
     }
   }

   if (!isa<LoadInst>(&I) && !isa<CallInst>(&I))
     return false;

   // For:
   //   B1:
   //     var = ...
   //     ...
   //     /* icmp may not be in the same block as var = ... */
   //     comp1 = icmp <opcode> var, <const>;
   //     if (comp1) goto B2 else B3;
   //   B2:
   //     ... var ...
   // change to:
   //   B1:
   //     var = ...
   //     ...
   //     /* icmp may not be in the same block as var = ... */
   //     comp1 = icmp <opcode> var, <const>;
   //     if (comp1) goto B2 else B3;
   //   B2:
   //     var = __builtin_bpf_passthrough(seq_num, var);
   //     ... var ...
   bool isCandidate = false;
   SmallVector<PassThroughInfo, 4> Candidates;
   for (User *U : I.users()) {
     Instruction *Inst = dyn_cast<Instruction>(U);
     if (!Inst)
       continue;

     // May cover a little bit more than the
     // above pattern.
     if (auto *Icmp1 = dyn_cast<ICmpInst>(Inst)) {
       Value *Icmp1Op1 = Icmp1->getOperand(1);
       if (!isa<Constant>(Icmp1Op1))
         return false;
       isCandidate = true;
       continue;
     }

     // Ignore the use in the same basic block as the definition.
     if (Inst->getParent() == I.getParent())
       continue;

     // use in a different basic block, If there is a call or
     // load/store insn before this instruction in this basic
     // block. Most likely it cannot be hoisted out. Skip it.
     for (auto &I2 : *Inst->getParent()) {
       if (isa<CallInst>(&I2))
         return false;
       if (isa<LoadInst>(&I2) || isa<StoreInst>(&I2))
         return false;
       if (&I2 == Inst)
         break;
     }

     // It should be used in a GEP or a simple arithmetic like
     // ZEXT/SEXT which is used for GEP.
     if (Inst->getOpcode() == Instruction::ZExt ||
         Inst->getOpcode() == Instruction::SExt) {
       PassThroughInfo Info(&I, Inst, 0);
       Candidates.push_back(Info);
     } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
       // traverse GEP inst to find Use operand index
       unsigned i, e;
       for (i = 1, e = GI->getNumOperands(); i != e; ++i) {
         Value *V = GI->getOperand(i);
         if (V == &I)
           break;
       }
       if (i == e)
         continue;

       PassThroughInfo Info(&I, GI, i);
       Candidates.push_back(Info);
     }
   }

   if (!isCandidate || Candidates.empty())
     return false;

   llvm::append_range(PassThroughs, Candidates);
   return true;
 }

 void BPFAdjustOptImpl::adjustBasicBlock(BasicBlock &BB) {
   if (!DisableBPFserializeICMP && serializeICMPCrossBB(BB))
     return;
 }

 void BPFAdjustOptImpl::adjustInst(Instruction &I) {
   if (!DisableBPFserializeICMP && serializeICMPInBB(I))
     return;
   if (!DisableBPFavoidSpeculation && avoidSpeculation(I))
     return;
 }

 PreservedAnalyses BPFAdjustOptPass::run(Module &M, ModuleAnalysisManager &AM) {
   return BPFAdjustOptImpl(&M).run() ? PreservedAnalyses::none()
                                     : PreservedAnalyses::all();
 }
	//===---------------- 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.
	//
	//===----------------------------------------------------------------------===//

	#include "BPF.h"
	#include "BPFCORE.h"
	#include "llvm/IR/Instruction.h"
	#include "llvm/IR/Instructions.h"
	#include "llvm/IR/IntrinsicsBPF.h"
	#include "llvm/IR/Module.h"
	#include "llvm/IR/PatternMatch.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;
	using namespace llvm::PatternMatch;

	static cl::opt<bool>
	DisableBPFserializeICMP("bpf-disable-serialize-icmp", cl::Hidden,
	cl::desc("BPF: Disable Serializing ICMP insns."),
	cl::init(false));

	static cl::opt<bool> DisableBPFavoidSpeculation(
	"bpf-disable-avoid-speculation", cl::Hidden,
	cl::desc("BPF: Disable Avoiding Speculative Code Motion."),
	cl::init(false));

	namespace {
	class BPFAdjustOptImpl {
	struct PassThroughInfo {
	Instruction *Input;
	Instruction *UsedInst;
	uint32_t OpIdx;
	PassThroughInfo(Instruction I, Instruction U, uint32_t Idx)
	: Input(I), UsedInst(U), OpIdx(Idx) {}
	};

	public:
	BPFAdjustOptImpl(Module *M) : M(M) {}

	bool run();

	private:
	Module *M;
	SmallVector<PassThroughInfo, 16> PassThroughs;

	bool adjustICmpToBuiltin();
	void adjustBasicBlock(BasicBlock &BB);
	bool serializeICMPCrossBB(BasicBlock &BB);
	void adjustInst(Instruction &I);
	bool serializeICMPInBB(Instruction &I);
	bool avoidSpeculation(Instruction &I);
	bool insertPassThrough();
	};

	} // End anonymous namespace

	bool BPFAdjustOptImpl::run() {
	bool Changed = adjustICmpToBuiltin();

	for (Function &F : *M)
	for (auto &BB : F) {
	adjustBasicBlock(BB);
	for (auto &I : BB)
	adjustInst(I);
	}
	return insertPassThrough() \|\| Changed;
	}

	// Commit acabad9ff6bf ("[InstCombine] try to canonicalize icmp with
	// trunc op into mask and cmp") added a transformation to
	// convert "(conv)a < power_2_const" to "a & <const>" in certain
	// cases and bpf kernel verifier has to handle the resulted code
	// conservatively and this may reject otherwise legitimate program.
	// Here, we change related icmp code to a builtin which will
	// be restored to original icmp code later to prevent that
	// InstCombine transformatin.
	bool BPFAdjustOptImpl::adjustICmpToBuiltin() {
	bool Changed = false;
	ICmpInst *ToBeDeleted = nullptr;
	for (Function &F : *M)
	for (auto &BB : F)
	for (auto &I : BB) {
	if (ToBeDeleted) {
	ToBeDeleted->eraseFromParent();
	ToBeDeleted = nullptr;
	}

	auto *Icmp = dyn_cast<ICmpInst>(&I);
	if (!Icmp)
	continue;

	Value *Op0 = Icmp->getOperand(0);
	if (!isa<TruncInst>(Op0))
	continue;

	auto ConstOp1 = dyn_cast<ConstantInt>(Icmp->getOperand(1));
	if (!ConstOp1)
	continue;

	auto ConstOp1Val = ConstOp1->getValue().getZExtValue();
	auto Op = Icmp->getPredicate();
	if (Op == ICmpInst::ICMP_ULT \|\| Op == ICmpInst::ICMP_UGE) {
	if ((ConstOp1Val - 1) & ConstOp1Val)
	continue;
	} else if (Op == ICmpInst::ICMP_ULE \|\| Op == ICmpInst::ICMP_UGT) {
	if (ConstOp1Val & (ConstOp1Val + 1))
	continue;
	} else {
	continue;
	}

	Constant *Opcode =
	ConstantInt::get(Type::getInt32Ty(BB.getContext()), Op);
	Function *Fn = Intrinsic::getOrInsertDeclaration(
	M, Intrinsic::bpf_compare, {Op0->getType(), ConstOp1->getType()});
	auto *NewInst = CallInst::Create(Fn, {Opcode, Op0, ConstOp1});
	NewInst->insertBefore(I.getIterator());
	Icmp->replaceAllUsesWith(NewInst);
	Changed = true;
	ToBeDeleted = Icmp;
	}

	return Changed;
	}

	bool BPFAdjustOptImpl::insertPassThrough() {
	for (auto &Info : PassThroughs) {
	auto *CI = BPFCoreSharedInfo::insertPassThrough(
	M, Info.UsedInst->getParent(), Info.Input, Info.UsedInst);
	Info.UsedInst->setOperand(Info.OpIdx, CI);
	}

	return !PassThroughs.empty();
	}

	// To avoid combining conditionals in the same basic block by
	// instrcombine optimization.
	bool BPFAdjustOptImpl::serializeICMPInBB(Instruction &I) {
	// For:
	// comp1 = icmp <opcode> ...;
	// comp2 = icmp <opcode> ...;
	// ... or comp1 comp2 ...
	// changed to:
	// comp1 = icmp <opcode> ...;
	// comp2 = icmp <opcode> ...;
	// new_comp1 = __builtin_bpf_passthrough(seq_num, comp1)
	// ... or new_comp1 comp2 ...
	Value Op0, Op1;
	// Use LogicalOr (accept `or i1` as well as `select i1 Op0, true, Op1`)
	if (!match(&I, m_LogicalOr(m_Value(Op0), m_Value(Op1))))
	return false;
	auto *Icmp1 = dyn_cast<ICmpInst>(Op0);
	if (!Icmp1)
	return false;
	auto *Icmp2 = dyn_cast<ICmpInst>(Op1);
	if (!Icmp2)
	return false;

	Value *Icmp1Op0 = Icmp1->getOperand(0);
	Value *Icmp2Op0 = Icmp2->getOperand(0);
	if (Icmp1Op0 != Icmp2Op0)
	return false;

	// Now we got two icmp instructions which feed into
	// an "or" instruction.
	PassThroughInfo Info(Icmp1, &I, 0);
	PassThroughs.push_back(Info);
	return true;
	}

	// To avoid combining conditionals in the same basic block by
	// instrcombine optimization.
	bool BPFAdjustOptImpl::serializeICMPCrossBB(BasicBlock &BB) {
	// For:
	// B1:
	// comp1 = icmp <opcode> ...;
	// if (comp1) goto B2 else B3;
	// B2:
	// comp2 = icmp <opcode> ...;
	// if (comp2) goto B4 else B5;
	// B4:
	// ...
	// changed to:
	// B1:
	// comp1 = icmp <opcode> ...;
	// comp1 = __builtin_bpf_passthrough(seq_num, comp1);
	// if (comp1) goto B2 else B3;
	// B2:
	// comp2 = icmp <opcode> ...;
	// if (comp2) goto B4 else B5;
	// B4:
	// ...

	// Check basic predecessors, if two of them (say B1, B2) are using
	// icmp instructions to generate conditions and one is the predesessor
	// of another (e.g., B1 is the predecessor of B2). Add a passthrough
	// barrier after icmp inst of block B1.
	BasicBlock *B2 = BB.getSinglePredecessor();
	if (!B2)
	return false;

	BasicBlock *B1 = B2->getSinglePredecessor();
	if (!B1)
	return false;

	Instruction *TI = B2->getTerminator();
	auto *BI = dyn_cast<BranchInst>(TI);
	if (!BI \|\| !BI->isConditional())
	return false;
	auto *Cond = dyn_cast<ICmpInst>(BI->getCondition());
	if (!Cond \|\| &*B2->getFirstNonPHIIt() != Cond)
	return false;
	Value *B2Op0 = Cond->getOperand(0);
	auto Cond2Op = Cond->getPredicate();

	TI = B1->getTerminator();
	BI = dyn_cast<BranchInst>(TI);
	if (!BI \|\| !BI->isConditional())
	return false;
	Cond = dyn_cast<ICmpInst>(BI->getCondition());
	if (!Cond)
	return false;
	Value *B1Op0 = Cond->getOperand(0);
	auto Cond1Op = Cond->getPredicate();

	if (B1Op0 != B2Op0)
	return false;

	if (Cond1Op == ICmpInst::ICMP_SGT \|\| Cond1Op == ICmpInst::ICMP_SGE) {
	if (Cond2Op != ICmpInst::ICMP_SLT && Cond2Op != ICmpInst::ICMP_SLE)
	return false;
	} else if (Cond1Op == ICmpInst::ICMP_SLT \|\| Cond1Op == ICmpInst::ICMP_SLE) {
	if (Cond2Op != ICmpInst::ICMP_SGT && Cond2Op != ICmpInst::ICMP_SGE)
	return false;
	} else if (Cond1Op == ICmpInst::ICMP_ULT \|\| Cond1Op == ICmpInst::ICMP_ULE) {
	if (Cond2Op != ICmpInst::ICMP_UGT && Cond2Op != ICmpInst::ICMP_UGE)
	return false;
	} else if (Cond1Op == ICmpInst::ICMP_UGT \|\| Cond1Op == ICmpInst::ICMP_UGE) {
	if (Cond2Op != ICmpInst::ICMP_ULT && Cond2Op != ICmpInst::ICMP_ULE)
	return false;
	} else {
	return false;
	}

	PassThroughInfo Info(Cond, BI, 0);
	PassThroughs.push_back(Info);

	return true;
	}

	// To avoid speculative hoisting certain computations out of
	// a basic block.
	bool BPFAdjustOptImpl::avoidSpeculation(Instruction &I) {
	if (auto *LdInst = dyn_cast<LoadInst>(&I)) {
	if (auto *GV = dyn_cast<GlobalVariable>(LdInst->getOperand(0))) {
	if (GV->hasAttribute(BPFCoreSharedInfo::AmaAttr) \|\|
	GV->hasAttribute(BPFCoreSharedInfo::TypeIdAttr))
	return false;
	}
	}

	if (!isa<LoadInst>(&I) && !isa<CallInst>(&I))
	return false;

	// For:
	// B1:
	// var = ...
	// ...
	// /* icmp may not be in the same block as var = ... */
	// comp1 = icmp <opcode> var, <const>;
	// if (comp1) goto B2 else B3;
	// B2:
	// ... var ...
	// change to:
	// B1:
	// var = ...
	// ...
	// /* icmp may not be in the same block as var = ... */
	// comp1 = icmp <opcode> var, <const>;
	// if (comp1) goto B2 else B3;
	// B2:
	// var = __builtin_bpf_passthrough(seq_num, var);
	// ... var ...
	bool isCandidate = false;
	SmallVector<PassThroughInfo, 4> Candidates;
	for (User *U : I.users()) {
	Instruction *Inst = dyn_cast<Instruction>(U);
	if (!Inst)
	continue;

	// May cover a little bit more than the
	// above pattern.
	if (auto *Icmp1 = dyn_cast<ICmpInst>(Inst)) {
	Value *Icmp1Op1 = Icmp1->getOperand(1);
	if (!isa<Constant>(Icmp1Op1))
	return false;
	isCandidate = true;
	continue;
	}

	// Ignore the use in the same basic block as the definition.
	if (Inst->getParent() == I.getParent())
	continue;

	// use in a different basic block, If there is a call or
	// load/store insn before this instruction in this basic
	// block. Most likely it cannot be hoisted out. Skip it.
	for (auto &I2 : *Inst->getParent()) {
	if (isa<CallInst>(&I2))
	return false;
	if (isa<LoadInst>(&I2) \|\| isa<StoreInst>(&I2))
	return false;
	if (&I2 == Inst)
	break;
	}

	// It should be used in a GEP or a simple arithmetic like
	// ZEXT/SEXT which is used for GEP.
	if (Inst->getOpcode() == Instruction::ZExt \|\|
	Inst->getOpcode() == Instruction::SExt) {
	PassThroughInfo Info(&I, Inst, 0);
	Candidates.push_back(Info);
	} else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
	// traverse GEP inst to find Use operand index
	unsigned i, e;
	for (i = 1, e = GI->getNumOperands(); i != e; ++i) {
	Value *V = GI->getOperand(i);
	if (V == &I)
	break;
	}
	if (i == e)
	continue;

	PassThroughInfo Info(&I, GI, i);
	Candidates.push_back(Info);
	}
	}

	if (!isCandidate \|\| Candidates.empty())
	return false;

	llvm::append_range(PassThroughs, Candidates);
	return true;
	}

	void BPFAdjustOptImpl::adjustBasicBlock(BasicBlock &BB) {
	if (!DisableBPFserializeICMP && serializeICMPCrossBB(BB))
	return;
	}

	void BPFAdjustOptImpl::adjustInst(Instruction &I) {
	if (!DisableBPFserializeICMP && serializeICMPInBB(I))
	return;
	if (!DisableBPFavoidSpeculation && avoidSpeculation(I))
	return;
	}

	PreservedAnalyses BPFAdjustOptPass::run(Module &M, ModuleAnalysisManager &AM) {
	return BPFAdjustOptImpl(&M).run() ? PreservedAnalyses::none()
	: PreservedAnalyses::all();
	}