BPF: move AbstractMemberAccess and PreserveDIType passes to EP_EarlyAsPossible

[yonghong-song]

Summary

Move abstractMemberAccess and PreserveDIType passes as early as
possible, right after clang code generation.

Currently, compiler may transform the above code

p1 = llvm.bpf.builtin.preserve.struct.access(base, 0, 0);
p2 = llvm.bpf.builtin.preserve.struct.access(p1, 1, 2);
a = llvm.bpf.builtin.preserve_field_info(p2, EXIST);
if (a) {
  p1 = llvm.bpf.builtin.preserve.struct.access(base, 0, 0);
  p2 = llvm.bpf.builtin.preserve.struct.access(p1, 1, 2);
  bpf_probe_read(buf, buf_size, p2);
}

to

p1 = llvm.bpf.builtin.preserve.struct.access(base, 0, 0);
p2 = llvm.bpf.builtin.preserve.struct.access(p1, 1, 2);
a = llvm.bpf.builtin.preserve_field_info(p2, EXIST);
if (a) {
  bpf_probe_read(buf, buf_size, p2);
}

and eventually assembly code looks like

reloc_exist = 1;
reloc_member_offset = 10; //calculate member offset from base
p2 = base + reloc_member_offset;
if (reloc_exist) {
  bpf_probe_read(bpf, buf_size, p2);
}

if during libbpf relocation resolution, reloc_exist is actually
resolved to 0 (not exist), reloc_member_offset relocation cannot
be resolved and will be patched with illegal instruction.
This will cause verifier failure.

This patch attempts to address this issue by do chaining
analysis and replace chains with special globals right
after clang code gen. This will remove the cse possibility
described in the above. The IR typically looks like

%6 = load @llvm.sk_buff:0:50$0:0:0:2:0
%7 = bitcast %struct.sk_buff* %2 to i8*
%8 = getelementptr i8, i8* %7, %6

for a particular address computation relocation.

But this transformation has another consequence, code sinking
may happen like below:

PHI = <possibly different @preserve_*_access_globals>
%7 = bitcast %struct.sk_buff* %2 to i8*
%8 = getelementptr i8, i8* %7, %6

For such cases, we will not able to generate relocations since
multiple relocations are merged into one.

This patch introduced a passthrough builtin
to prevent such optimization. Looks like inline assembly has more
impact for optimizaiton, e.g., inlining. Using passthrough has
less impact on optimizations.

A new IR pass is introduced at the beginning of target-dependent
IR optimization, which does:

• report fatal error if any reloc global in PHI nodes
• remove all bpf passthrough builtin functions

Changes for existing CORE tests:

• for clang tests, add "-Xclang -disable-llvm-passes" flags to avoid builtin->reloc_global transformation so the test is still able to check correctness for clang generated IR.
• for llvm CodeGen/BPF tests, add "opt -O2 <ir_file> | llvm-dis" command before "llc" command since "opt" is needed to call newly-placed builtin->reloc_global transformation. Add target triple in the IR file since "opt" requires it.
• Since target triple is added in IR file, if a test may produce different results for different endianness, two tests will be created, one for bpfeb and another for bpfel, e.g., some tests for relocation of lshift/rshift of bitfields.
• field-reloc-bitfield-1.ll has different relocations compared to old codes. This is because for the structure in the test, new code returns struct layout alignment 4 while old code is 8. Align 8 is more precise and permits double load. With align 4, the new mechanism uses 4-byte load, so generating different relocations.
• test intrinsic-transforms.ll is removed. This is used to test cse on intrinsics so we do not lose metadata. Now metadata is attached to global and not instruction, it won't get lost with cse.

[yonghong-song]

• introduced __builtin_bpf_passthrough() and use it for user barrier instead of inline asm. I found inline asm has some impact on inlining when running selftests (specifically checked for map_ptr_kern.c).
• introduced an IR pass at the beginning of target dependent optimizations to (1). ensure reloc globals not in PHI node, (2). remove __builtin_bpf_passthrough(). (3). coalescing reloc globals if possible.

This patch can now pass all selftests.

[ast]

llvm/lib/Target/BPF/BPFAbstractMemberAccess.cpp

105

Instead of adding this attribute when bpf_passthrough is inserted by the compiler would it be possible to have this attribute attached to the builtin unconditionally? Meaning that the user could use such builtin in their C code and it would contain NoMerge as well ?

[yonghong-song]

llvm/lib/Target/BPF/BPFAbstractMemberAccess.cpp

105

All the __builtin_preserve_* builtins will be gone at this phase (the first phase after clang codegen) after they are replaced by globals. So here we are dealing with cases where they may not have calls in the basic block which contains relocation globals.

[yonghong-song]

add seq_num arg to passthrough builtin.

[ast]

llvm/lib/Target/BPF/BPFAbstractMemberAccess.cpp

1072

why did you remove the whole comment? Only 'NoMerge' part of it is no longer relevant, right?
But the rest is still very helpful to understand the intent or I'm missing something?

[yonghong-song]

llvm/lib/Target/BPF/BPFAbstractMemberAccess.cpp

1072

Okay, NoMerge part is irrelevant now. The sequence number of will prevent any kind of merging/CSE, not just tail merging. I will restore the comments.

[yonghong-song]

• • remove RFC tag. The patch is complete and all tests are adjusted and passed.
  • remove the adjustIR phase which tries to coalescing two reloc-globals. My previous implementation did not compare the *last* type in the first reloc-global and the *first* type in the second reloc-global. This will require to traverse the access string (0:1:1:...). This seems too much work for this little optimization. I will delay it into the future as an enhancement.
• adjusted existing clang/llvm CORE tests so they can pass.

llvm/include/llvm/IR/IntrinsicsBPF.td

def int_bpf_btf_type_id : GCCBuiltin<"__builtin_bpf_btf_type_id">,
               Intrinsic<[llvm_i32_ty], [llvm_i32_ty, llvm_i64_ty],
               [IntrNoMem]>;
   def int_bpf_preserve_type_info : GCCBuiltin<"__builtin_bpf_preserve_type_info">,
               Intrinsic<[llvm_i32_ty], [llvm_i32_ty, llvm_i64_ty],
               [IntrNoMem]>;
   def int_bpf_preserve_enum_value : GCCBuiltin<"__builtin_bpf_preserve_enum_value">,
               Intrinsic<[llvm_i64_ty], [llvm_i32_ty, llvm_ptr_ty, llvm_i64_ty],
               [IntrNoMem]>;
+  def int_bpf_passthrough : GCCBuiltin<"__builtin_bpf_passthrough">,
+              Intrinsic<[llvm_any_ty], [llvm_any_ty], [IntrNoMem]>;
 }

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 *createBPFAbstractMemberAccess(BPFTargetMachine *TM);
-ModulePass *createBPFPreserveDIType();
+ModulePass *createBPFCheckAndAdjustIR();
 
+FunctionPass *createBPFAbstractMemberAccess(BPFTargetMachine *TM);
+FunctionPass *createBPFPreserveDIType();
 FunctionPass *createBPFISelDag(BPFTargetMachine &TM);
 FunctionPass *createBPFMISimplifyPatchablePass();
 FunctionPass *createBPFMIPeepholePass();
 FunctionPass *createBPFMIPeepholeTruncElimPass();
 FunctionPass *createBPFMIPreEmitPeepholePass();
 FunctionPass *createBPFMIPreEmitCheckingPass();
 
+void initializeBPFCheckAndAdjustIRPass(PassRegistry&);
+
 void initializeBPFAbstractMemberAccessPass(PassRegistry&);
 void initializeBPFPreserveDITypePass(PassRegistry&);
 void initializeBPFMISimplifyPatchablePass(PassRegistry&);
 void initializeBPFMIPeepholePass(PassRegistry&);
 void initializeBPFMIPeepholeTruncElimPass(PassRegistry&);
 void initializeBPFMIPreEmitPeepholePass(PassRegistry&);
 void initializeBPFMIPreEmitCheckingPass(PassRegistry&);
 }
 
 #endif

llvm/lib/Target/BPF/BPFAbstractMemberAccess.cpp

 
 #include "BPF.h"
 #include "BPFCORE.h"
 #include "BPFTargetMachine.h"
 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicsBPF.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"
 #include <stack>
 
 #define DEBUG_TYPE "bpf-abstract-member-access"
 
 namespace llvm {
 constexpr StringRef BPFCoreSharedInfo::AmaAttr;
+
+Instruction *BPFCoreSharedInfo::insertPassThrough(Module *M, BasicBlock *BB,
+                                                  Instruction *Input,
+                                                  Instruction *Before) {
+  Function *Fn = Intrinsic::getDeclaration(M, Intrinsic::bpf_passthrough,
+                                           {Input->getType(), Input->getType()});
+  auto *NewInst = CallInst::Create(Fn, {Input});
+  // Prevent sink common which may create a PHI node for reloc globals.
+  NewInst->addAttribute(AttributeList::FunctionIndex, Attribute::NoMerge);
+  BB->getInstList().insert(Before->getIterator(), NewInst);
+  return NewInst;
+}
 } // namespace llvm
 
 using namespace llvm;
 
 namespace {
 
-class BPFAbstractMemberAccess final : public ModulePass {
-  StringRef getPassName() const override {
-    return "BPF Abstract Member Access";
-  }
-
-  bool runOnModule(Module &M) override;
+class BPFAbstractMemberAccess final : public FunctionPass {
+  bool runOnFunction(Function &F) override;
 
 public:
   static char ID;
   TargetMachine *TM;
   // Add optional BPFTargetMachine parameter so that BPF backend can add the phase
   // with target machine to find out the endianness. The default constructor (without
   // parameters) is used by the pass manager for managing purposes.
-  BPFAbstractMemberAccess(BPFTargetMachine *TM = nullptr) : ModulePass(ID), TM(TM) {}
+  BPFAbstractMemberAccess(BPFTargetMachine *TM = nullptr)
+      : FunctionPass(ID), TM(TM) {}
 
   struct CallInfo {
     uint32_t Kind;
     uint32_t AccessIndex;
     Align RecordAlignment;
     MDNode *Metadata;
     Value *Base;
   };
   typedef std::stack<std::pair<CallInst *, CallInfo>> CallInfoStack;
 
 private:
   enum : uint32_t {
     BPFPreserveArrayAI = 1,
     BPFPreserveUnionAI = 2,
     BPFPreserveStructAI = 3,
     BPFPreserveFieldInfoAI = 4,
   };
 
   const DataLayout *DL = nullptr;
+  Module *M = nullptr;
 
   std::map<std::string, GlobalVariable *> GEPGlobals;
   // A map to link preserve_*_access_index instrinsic calls.
   std::map<CallInst *, std::pair<CallInst *, CallInfo>> AIChain;
   // A map to hold all the base preserve_*_access_index instrinsic calls.
   // The base call is not an input of any other preserve_*
   // intrinsics.
   std::map<CallInst *, CallInfo> BaseAICalls;
 
-  bool doTransformation(Module &M);
+  bool doTransformation(Function &F);
 
   void traceAICall(CallInst *Call, CallInfo &ParentInfo);
   void traceBitCast(BitCastInst *BitCast, CallInst *Parent,
                     CallInfo &ParentInfo);
   void traceGEP(GetElementPtrInst *GEP, CallInst *Parent,
                 CallInfo &ParentInfo);
-  void collectAICallChains(Module &M, Function &F);
+  void collectAICallChains(Function &F);
 
   bool IsPreserveDIAccessIndexCall(const CallInst *Call, CallInfo &Cinfo);
   bool IsValidAIChain(const MDNode *ParentMeta, uint32_t ParentAI,
                       const MDNode *ChildMeta);
-  bool removePreserveAccessIndexIntrinsic(Module &M);
+  bool removePreserveAccessIndexIntrinsic(Function &F);
   void replaceWithGEP(std::vector<CallInst *> &CallList,
                       uint32_t NumOfZerosIndex, uint32_t DIIndex);
   bool HasPreserveFieldInfoCall(CallInfoStack &CallStack);
   void GetStorageBitRange(DIDerivedType *MemberTy, Align RecordAlignment,
                           uint32_t &StartBitOffset, uint32_t &EndBitOffset);
   uint32_t GetFieldInfo(uint32_t InfoKind, DICompositeType *CTy,
                         uint32_t AccessIndex, uint32_t PatchImm,
                         Align RecordAlignment);
 
   Value *computeBaseAndAccessKey(CallInst *Call, CallInfo &CInfo,
                                  std::string &AccessKey, MDNode *&BaseMeta);
   MDNode *computeAccessKey(CallInst *Call, CallInfo &CInfo,
                            std::string &AccessKey, bool &IsInt32Ret);
   uint64_t getConstant(const Value *IndexValue);
-  bool transformGEPChain(Module &M, CallInst *Call, CallInfo &CInfo);
+  bool transformGEPChain(CallInst *Call, CallInfo &CInfo);
 };
 } // End anonymous namespace
 
 char BPFAbstractMemberAccess::ID = 0;
 INITIALIZE_PASS(BPFAbstractMemberAccess, DEBUG_TYPE,
-                "abstracting struct/union member accessees", false, false)
+                "BPF Abstract Member Access", false, false)
 
-ModulePass *llvm::createBPFAbstractMemberAccess(BPFTargetMachine *TM) {
+FunctionPass *llvm::createBPFAbstractMemberAccess(BPFTargetMachine *TM) {
   return new BPFAbstractMemberAccess(TM);
 }
 
-bool BPFAbstractMemberAccess::runOnModule(Module &M) {
+bool BPFAbstractMemberAccess::runOnFunction(Function &F) {
   LLVM_DEBUG(dbgs() << "********** Abstract Member Accesses **********\n");
 
+  M = F.getParent();
+  if (!M)
+    return false;
+
   // Bail out if no debug info.
-  if (M.debug_compile_units().empty())
+  if (M->debug_compile_units().empty())
     return false;
 
-  DL = &M.getDataLayout();
-  return doTransformation(M);
+  DL = &M->getDataLayout();
+  return doTransformation(F);
 }
 
 static bool SkipDIDerivedTag(unsigned Tag, bool skipTypedef) {
   if (Tag != dwarf::DW_TAG_typedef && Tag != dwarf::DW_TAG_const_type &&
       Tag != dwarf::DW_TAG_volatile_type &&
       Tag != dwarf::DW_TAG_restrict_type &&
       Tag != dwarf::DW_TAG_member)
     return false;
for (auto Call : CallList) {
 
     auto *GEP = GetElementPtrInst::CreateInBounds(Call->getArgOperand(0),
                                                   IdxList, "", Call);
     Call->replaceAllUsesWith(GEP);
     Call->eraseFromParent();
   }
 }
 
-bool BPFAbstractMemberAccess::removePreserveAccessIndexIntrinsic(Module &M) {
+bool BPFAbstractMemberAccess::removePreserveAccessIndexIntrinsic(Function &F) {
   std::vector<CallInst *> PreserveArrayIndexCalls;
   std::vector<CallInst *> PreserveUnionIndexCalls;
   std::vector<CallInst *> PreserveStructIndexCalls;
   bool Found = false;
 
-  for (Function &F : M)
-    for (auto &BB : F)
-      for (auto &I : BB) {
-        auto *Call = dyn_cast<CallInst>(&I);
-        CallInfo CInfo;
-        if (!IsPreserveDIAccessIndexCall(Call, CInfo))
-          continue;
 
-        Found = true;
-        if (CInfo.Kind == BPFPreserveArrayAI)
-          PreserveArrayIndexCalls.push_back(Call);
-        else if (CInfo.Kind == BPFPreserveUnionAI)
-          PreserveUnionIndexCalls.push_back(Call);
-        else
-          PreserveStructIndexCalls.push_back(Call);
-      }
 
   // do the following transformation:
   // . addr = preserve_array_access_index(base, dimension, index)
   //   is transformed to
   //     addr = GEP(base, dimenion's zero's, index)
   // . addr = preserve_union_access_index(base, di_index)
   //   is transformed to
   //     addr = base, i.e., all usages of "addr" are replaced by "base".
if (auto *BI = dyn_cast<BitCastInst>(Inst)) {
       else
         BaseAICalls[Parent] = ParentInfo;
     } else {
       BaseAICalls[Parent] = ParentInfo;
     }
   }
 }
 
-void BPFAbstractMemberAccess::collectAICallChains(Module &M, Function &F) {
+void BPFAbstractMemberAccess::collectAICallChains(Function &F) {
   AIChain.clear();
   BaseAICalls.clear();
 
   for (auto &BB : F)
     for (auto &I : BB) {
       CallInfo CInfo;
       auto *Call = dyn_cast<CallInst>(&I);
       if (!IsPreserveDIAccessIndexCall(Call, CInfo) ||
AccessKey = "llvm." + Ty->getName().str() + ":" +
               std::to_string(CInfo.AccessIndex) + std::string(":") +
               std::to_string(PatchImm) + std::string("$") + AccessStr;
 
   return Ty;
 }
 
 /// Call/Kind is the base preserve_*_access_index() call. Attempts to do
 /// transformation to a chain of relocable GEPs.
-bool BPFAbstractMemberAccess::transformGEPChain(Module &M, CallInst *Call,
+bool BPFAbstractMemberAccess::transformGEPChain(CallInst *Call,
                                                 CallInfo &CInfo) {
   std::string AccessKey;
   MDNode *TypeMeta;
   Value *Base = nullptr;
   bool IsInt32Ret;
 
   IsInt32Ret = CInfo.Kind == BPFPreserveFieldInfoAI;
   if (CInfo.Kind == BPFPreserveFieldInfoAI && CInfo.Metadata) {
bool BPFAbstractMemberAccess::transformGEPChain(CallInst *Call,
 
   if (GEPGlobals.find(AccessKey) == GEPGlobals.end()) {
     IntegerType *VarType;
     if (IsInt32Ret)
       VarType = Type::getInt32Ty(BB->getContext()); // 32bit return value
     else
       VarType = Type::getInt64Ty(BB->getContext()); // 64bit ptr or enum value
 
-    GV = new GlobalVariable(M, VarType, false, GlobalVariable::ExternalLinkage,
+    GV = new GlobalVariable(*M, VarType, false, GlobalVariable::ExternalLinkage,
                             NULL, AccessKey);
     GV->addAttribute(BPFCoreSharedInfo::AmaAttr);
     GV->setMetadata(LLVMContext::MD_preserve_access_index, TypeMeta);
     GEPGlobals[AccessKey] = GV;
   } else {
     GV = GEPGlobals[AccessKey];
   }
 
   if (CInfo.Kind == BPFPreserveFieldInfoAI) {
     // Load the global variable which represents the returned field info.
     LoadInst *LDInst;
     if (IsInt32Ret)
       LDInst = new LoadInst(Type::getInt32Ty(BB->getContext()), GV, "", Call);
     else
       LDInst = new LoadInst(Type::getInt64Ty(BB->getContext()), GV, "", Call);
-    Call->replaceAllUsesWith(LDInst);
+
+    Instruction *PassThroughInst =
+        BPFCoreSharedInfo::insertPassThrough(M, BB, LDInst, Call);
+    Call->replaceAllUsesWith(PassThroughInst);
     Call->eraseFromParent();
     return true;
   }
 
   // For any original GEP Call and Base %2 like
   //   %4 = bitcast %struct.net_device** %dev1 to i64*
   // it is transformed to:
-  //   %6 = load sk_buff:50:$0:0:0:2:0
+  //   %6 = load llvm.sk_buff:50:$0:0:0:2:0
   //   %7 = bitcast %struct.sk_buff* %2 to i8*
   //   %8 = getelementptr i8, i8* %7, %6
   //   %9 = bitcast i8* %8 to i64*
   //   using %9 instead of %4
   // The original Call inst is removed.
 
   // Load the global variable.
   auto *LDInst = new LoadInst(Type::getInt64Ty(BB->getContext()), GV, "", Call);
 
   // Generate a BitCast
   auto *BCInst = new BitCastInst(Base, Type::getInt8PtrTy(BB->getContext()));
   BB->getInstList().insert(Call->getIterator(), BCInst);
 
   // Generate a GetElementPtr
   auto *GEP = GetElementPtrInst::Create(Type::getInt8Ty(BB->getContext()),
                                         BCInst, LDInst);
   BB->getInstList().insert(Call->getIterator(), GEP);
 
   // Generate a BitCast
   auto *BCInst2 = new BitCastInst(GEP, Call->getType());
   BB->getInstList().insert(Call->getIterator(), BCInst2);
 
-  Call->replaceAllUsesWith(BCInst2);
+  // For the following code,
+  //    Block0:
+  //      ...
+  //      if (...) goto Block1 else ...
+  //    Block1:
+  //      %6 = load llvm.sk_buff:50:$0:0:0:2:0
+  //      %7 = bitcast %struct.sk_buff* %2 to i8*
+  //      %8 = getelementptr i8, i8* %7, %6
+  //      ...
+  //      goto CommonExit
+  //    Block2:
+  //      ...
+  //      if (...) goto Block3 else ...
+  //    Block3:
+  //      %6 = load llvm.bpf_map:40:$0:0:0:2:0
+  //      %7 = bitcast %struct.sk_buff* %2 to i8*
+  //      %8 = getelementptr i8, i8* %7, %6
+  //      ...
+  //      goto CommonExit
+  //    CommonExit
+  // SimplifyCFG may generate:
+  //    Block0:
+  //      ...
+  //      if (...) goto Block_Common else ...
+  //     Block2:
+  //       ...
+  //      if (...) goto Block_Common else ...
+  //    Block_Common:
+  //      PHI = [llvm.sk_buff:50:$0:0:0:2:0, llvm.bpf_map:40:$0:0:0:2:0]
+  //      %6 = load PHI
+  //      %7 = bitcast %struct.sk_buff* %2 to i8*
+  //      %8 = getelementptr i8, i8* %7, %6
+  //      ...
+  //      goto CommonExit
+  //  For the above code, we cannot perform proper relocation since
+  //  "load PHI" has two possible relocations.
+  //
+  // Current SimplifyCFG has a couple of ways to prevent the above
+  // transformation:
+  //   - insert an inline asm in the basic block
+  //   - insert a call and mark it with NoMerge function attribute.
+  // We use __builtin_bpf_passthrough() call marked with NoMerge approach.
+  // Compared to inline assembly approach, this has less impact on inlining
+  // and other optimizations. The __builtin_bpf_passthrough() will be removed
+  // in the beginning of Target IR passes.
+  //
+  // This approach is also used in other places when global var
+  // representing a relocation is used.
+  Instruction *PassThroughInst =
+      BPFCoreSharedInfo::insertPassThrough(M, BB, BCInst2, Call);
+  Call->replaceAllUsesWith(PassThroughInst);
   Call->eraseFromParent();
 
   return true;
 }
 
-bool BPFAbstractMemberAccess::doTransformation(Module &M) {
+bool BPFAbstractMemberAccess::doTransformation(Function &F) {
   bool Transformed = false;
 
-  for (Function &F : M) {
-    // Collect PreserveDIAccessIndex Intrinsic call chains.
-    // The call chains will be used to generate the access
-    // patterns similar to GEP.
-    collectAICallChains(M, F);
+  collectAICallChains(F);
 
-    for (auto &C : BaseAICalls)
-      Transformed = transformGEPChain(M, C.first, C.second) || Transformed;
-  }
+    Transformed = transformGEPChain(C.first, C.second) || Transformed;
 
-  return removePreserveAccessIndexIntrinsic(M) || Transformed;
+  return removePreserveAccessIndexIntrinsic(F) || Transformed;
 }

llvm/lib/Target/BPF/BPFCORE.h

 //===- BPFCORE.h - Common info for Compile-Once Run-EveryWhere  -*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_TARGET_BPF_BPFCORE_H
 #define LLVM_LIB_TARGET_BPF_BPFCORE_H
 
 #include "llvm/ADT/StringRef.h"
 
 namespace llvm {
 
+class BasicBlock;
+class CallInst;
+class Instruction;
+class Module;
+
 class BPFCoreSharedInfo {
 public:
   enum PatchableRelocKind : uint32_t {
     FIELD_BYTE_OFFSET = 0,
     FIELD_BYTE_SIZE,
     FIELD_EXISTENCE,
     FIELD_SIGNEDNESS,
     FIELD_LSHIFT_U64,
enum PreserveEnumValue : uint32_t {
 
     MAX_PRESERVE_ENUM_VALUE_FLAG,
   };
 
   /// The attribute attached to globals representing a field access
   static constexpr StringRef AmaAttr = "btf_ama";
   /// The attribute attached to globals representing a type id
   static constexpr StringRef TypeIdAttr = "btf_type_id";
+
+  /// Insert a bpf passthrough builtin function.
+  static Instruction *insertPassThrough(Module *M, BasicBlock *BB,
+                                        Instruction *Input,
+                                        Instruction *Before);
 };
 
 } // namespace llvm
 
 #endif

llvm/lib/Target/BPF/BPFCheckAndAdjustIR.cpp

+//===------------ BPFCheckAndAdjustIR.cpp - Check and Adjust IR -----------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Check IR and adjust IR for verifier friendly codes.
+// The following are done for IR checking:
+//   - no relocation globals in PHI node.
+// The following are done for IR adjustment:
+//   - remove __builtin_bpf_passthrough builtins. Target independent IR
+//     optimizations are done and those builtins can be removed.
+//   - coalesce possible relocations. The builtin->relocation_global
+//     transformation is done before inlining. Inlining may expose
+//     additional opportunities.
+//
+//===----------------------------------------------------------------------===//
+
+#include "BPF.h"
+#include "BPFCORE.h"
+#include "BPFTargetMachine.h"
+#include "llvm/IR/DebugInfoMetadata.h"
+#include "llvm/IR/GlobalVariable.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-check-and-opt-ir"
+
+using namespace llvm;
+
+namespace {
+
+class BPFCheckAndAdjustIR final : public ModulePass {
+  struct RelocOptInfo {
+    GetElementPtrInst *GEP1;
+    GetElementPtrInst *GEP2;
+    std::string RelocStr;
+    MDNode *TypeMeta;
+    RelocOptInfo(GetElementPtrInst *I1, GetElementPtrInst *I2, std::string Str, MDNode *Meta)
+        : GEP1(I1), GEP2(I2), RelocStr(Str), TypeMeta(Meta) {}
+  };
+
+  bool runOnModule(Module &F) override;
+
+public:
+  static char ID;
+  BPFCheckAndAdjustIR() : ModulePass(ID) {}
+
+private:
+  std::map<std::string, GlobalVariable *> GEPGlobals;
+  SmallVector<RelocOptInfo, 16> RelocOptCands;
+
+  void checkIR(Module &M);
+  bool adjustIR(Module &M);
+  bool removePassThroughBuiltin(Module &M);
+  bool optimizeReloc(Module &M);
+  void findOptRelocCand(Instruction &I);
+  void checkBitCast(BitCastInst *BI, GetElementPtrInst *GEP1, GlobalVariable *GV1);
+  void checkGEP(GetElementPtrInst *GEP2, GetElementPtrInst *GEP1, GlobalVariable *GV1);
+};
+} // End anonymous namespace
+
+char BPFCheckAndAdjustIR::ID = 0;
+INITIALIZE_PASS(BPFCheckAndAdjustIR, DEBUG_TYPE, "BPF Check And Adjust IR",
+                false, false)
+
+ModulePass *llvm::createBPFCheckAndAdjustIR() {
+  return new BPFCheckAndAdjustIR();
+}
+
+bool BPFCheckAndAdjustIR::runOnModule(Module &M) {
+  checkIR(M);
+  return adjustIR(M);
+}
+
+void BPFCheckAndAdjustIR::checkIR(Module &M) {
+  // Ensure relocation global won't appear in PHI node
+  // This may happen if the compiler generated the following code:
+  //   B1:
+  //      g1 = @llvm.skb_buff:0:1...
+  //      ...
+  //      goto B_COMMON
+  //   B2:
+  //      g2 = @llvm.skb_buff:0:2...
+  //      ...
+  //      goto B_COMMON
+  //   B_COMMON:
+  //      g = PHI(g1, g2)
+  //      x = load g
+  //      ...
+  // If anything likes the above "g = PHI(g1, g2)", issue a fatal error.
+  for (Function &F : M)
+    for (auto &BB : F)
+      for (auto &I : BB) {
+        PHINode *PN = dyn_cast<PHINode>(&I);
+        if (!PN || PN->use_empty())
+          continue;
+        for (int i = 0, e = PN->getNumIncomingValues(); i < e; ++i) {
+          auto *GV = dyn_cast<GlobalVariable>(PN->getIncomingValue(i));
+          if (!GV)
+            continue;
+          if (GV->hasAttribute(BPFCoreSharedInfo::AmaAttr) ||
+              GV->hasAttribute(BPFCoreSharedInfo::TypeIdAttr))
+            report_fatal_error("relocation global in PHI node");
+        }
+      }
+}
+
+bool BPFCheckAndAdjustIR::removePassThroughBuiltin(Module &M) {
+  // Remove __builtin_bpf_passthrough()'s which are used to prevent
+  // certain IR optimizations. Now major IR optimizations are done,
+  // remove them.
+  bool Changed = false;
+  CallInst *ToBeDeleted = nullptr;
+  for (Function &F : M)
+    for (auto &BB : F)
+      for (auto &I : BB) {
+        if (ToBeDeleted) {
+          ToBeDeleted->eraseFromParent();
+          ToBeDeleted = nullptr;
+        }
+
+        auto *Call = dyn_cast<CallInst>(&I);
+        if (!Call)
+          continue;
+        auto *GV = dyn_cast<GlobalValue>(Call->getCalledOperand());
+        if (!GV)
+          continue;
+        if (!GV->getName().startswith("llvm.bpf.passthrough"))
+          continue;
+        Changed = true;
+        Value *Arg = Call->getArgOperand(0);
+        Call->replaceAllUsesWith(Arg);
+        ToBeDeleted = Call;
+      }
+  return Changed;
+}
+
+// Adjust/Optimize the following pattern
+//    %0 = load i64, i64* @"llvm.bpf_htab:0:0$0:0", align 8
+//    %1 = getelementptr i8, i8* bitcast (%struct.anon.2* @m_hash to i8*),
+//         i64 %0
+//    %2 = bitcast i8* %1 to %struct.bpf_map*
+//    %3 = load i64, i64* @"llvm.bpf_map:0:0$0:0", align 8
+//    %4 = bitcast %struct.bpf_map* %2 to i8*
+//    %5 = getelementptr i8, i8* %4, i64 %3
+// In the above sequence, we have address computation like
+//    @m_hash + @"llvm.bpf_htab:0:0$0:0" + @"llvm.bpf_map:0:0$0:0"
+// The above two relocations can be merged to
+//    @"llvm.bpf_htab:0:0$0:0:0"
+// and new address computation looks like
+//    @m_hash + @"llvm.bpf_htab:0:0$0:0:0"
+bool BPFCheckAndAdjustIR::optimizeReloc(Module &M) {
+  // Find candidates.
+  for (Function &F : M)
+    for (auto &BB : F) {
+      BasicBlock::iterator I = BB.begin(), E = BB.end();
+      for (; I != E; ++I)
+        findOptRelocCand(*I);
+    }
+
+  if (RelocOptCands.empty())
+    return false;
+
+  // Do transformations one candidate at a time.
+  for (auto &Cand : RelocOptCands) {
+    GetElementPtrInst *GEP1 = Cand.GEP1;
+    GetElementPtrInst *GEP2 = Cand.GEP2;
+    std::string RelocStr = Cand.RelocStr;
+    IntegerType *OffsetType = Type::getInt64Ty(M.getContext());
+    GlobalVariable *GV;
+
+    if (GEPGlobals.find(RelocStr) == GEPGlobals.end()) {
+      MDNode *TypeMeta = Cand.TypeMeta;
+      GV = new GlobalVariable(M, OffsetType, false,
+                              GlobalVariable::ExternalLinkage, NULL, RelocStr);
+      GV->addAttribute(BPFCoreSharedInfo::AmaAttr);
+      GV->setMetadata(LLVMContext::MD_preserve_access_index, TypeMeta);
+      GEPGlobals[RelocStr] = GV;
+    } else {
+      GV = GEPGlobals[RelocStr];
+    }
+
+    auto *LDInst = new LoadInst(OffsetType, GV, "", GEP2);
+    auto *NewGEP = GetElementPtrInst::Create(Type::getInt8Ty(M.getContext()),
+                                             GEP1->getOperand(0), LDInst);
+    GEP2->getParent()->getInstList().insert(GEP2->getIterator(), NewGEP);
+    GEP2->replaceAllUsesWith(NewGEP);
+  }
+  return true;
+}
+
+void BPFCheckAndAdjustIR::checkBitCast(BitCastInst *BI, GetElementPtrInst *GEP1,
+                                       GlobalVariable *GV1) {
+  for (User *U : BI->users()) {
+    if (auto *BI2 = dyn_cast<BitCastInst>(U))
+      checkBitCast(BI2, GEP1, GV1);
+    else if (auto *GEP2 = dyn_cast<GetElementPtrInst>(U))
+      checkGEP(GEP2, GEP1, GV1);
+  }
+}
+
+void BPFCheckAndAdjustIR::checkGEP(GetElementPtrInst *GEP2, GetElementPtrInst *GEP1,
+                                   GlobalVariable *GV1) {
+  // Find the second reloc global.
+  if (GEP2->getNumOperands() != 2)
+    return;
+
+  // GEP2 cannot be the first GEP of another candidate.
+  // We do not optimize chain of three relocation globals, which should be rare.
+  for (auto &Cand : RelocOptCands) {
+    if (GEP2 == Cand.GEP1)
+      return;
+  }
+
+  auto *LdInst2 = dyn_cast<LoadInst>(GEP2->getOperand(1));
+  if (!LdInst2)
+    return;
+
+  auto *GV2 = dyn_cast<GlobalVariable>(LdInst2->getOperand(0));
+  if (!GV2 || !GV2->hasAttribute(BPFCoreSharedInfo::AmaAttr))
+    return;
+
+  // Calculate the combined relocation access string and patch immediate.
+  StringRef GV1Name = GV1->getName();
+  size_t GV1_FirstColon = GV1Name.find_first_of(':');
+  size_t GV1_SecondColon = GV1Name.find_first_of(':', GV1_FirstColon + 1);
+  size_t GV1_FirstDollar = GV1Name.find_first_of('$');
+  StringRef IndexPattern1 = GV1Name.substr(GV1_FirstDollar + 1);
+  StringRef RelocKindStr1 =
+      GV1Name.substr(GV1_FirstColon + 1, GV1_SecondColon - GV1_FirstColon);
+  StringRef PatchImmStr1 =
+      GV1Name.substr(GV1_SecondColon + 1, GV1_FirstDollar - GV1_SecondColon);
+
+  StringRef GV2Name = GV2->getName();
+  size_t GV2_FirstColon = GV2Name.find_first_of(':');
+  size_t GV2_SecondColon = GV2Name.find_first_of(':', GV2_FirstColon + 1);
+  size_t GV2_FirstDollar = GV2Name.find_first_of('$');
+  StringRef IndexPattern2 = GV2Name.substr(GV2_FirstDollar + 1);
+  StringRef RelocKindStr2 =
+      GV2Name.substr(GV2_FirstColon + 1, GV2_SecondColon - GV2_FirstColon);
+  StringRef PatchImmStr2 =
+      GV2Name.substr(GV2_SecondColon + 1, GV2_FirstDollar - GV2_SecondColon);
+
+  // RelocKind should be the same and the second access string should have
+  // "0" as the first index.
+  if (RelocKindStr1 != RelocKindStr2 || IndexPattern2[0] != '0')
+    return;
+
+  uint32_t NewPatchImm = std::stoll(std::string(PatchImmStr1)) +
+                         std::stoll(std::string(PatchImmStr2));
+  std::string NewIndexPattern =
+      std::string(IndexPattern1) + std::string(IndexPattern2.substr(1));
+
+  std::string NewTypeStr = std::string(GV1Name.substr(0, GV1_SecondColon)) +
+                           ":" + std::to_string(NewPatchImm) + "$" +
+                           NewIndexPattern;
+
+  // A candidate to merge two relocations into one
+  MDNode *MDN = GV1->getMetadata(LLVMContext::MD_preserve_access_index);
+  RelocOptInfo Candidate(GEP1, GEP2, NewTypeStr, MDN);
+  RelocOptCands.push_back(Candidate);
+}
+
+void BPFCheckAndAdjustIR::findOptRelocCand(Instruction &I) {
+  // Find the first reloc global.
+  auto *LdInst = dyn_cast<LoadInst>(&I);
+  if (!LdInst)
+    return;
+
+  auto *GV1 = dyn_cast<GlobalVariable>(LdInst->getOperand(0));
+  if (!GV1 || !GV1->hasAttribute(BPFCoreSharedInfo::AmaAttr))
+    return;
+
+  // Remember the RelocStr=>GlobalVariable matching so we do not
+  // create a global with identical name.
+  if (GEPGlobals.find(std::string(GV1->getName())) == GEPGlobals.end())
+    GEPGlobals[std::string(GV1->getName())] = GV1;
+
+  for (User *U : LdInst->users()) {
+    GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(U);
+    if (!GEP1 || GEP1->getNumOperands() != 2)
+      continue;
+
+    // GEP1: op0: Base, op1: reloc_global
+    for (User *U2 : GEP1->users()) {
+      if (auto *BI = dyn_cast<BitCastInst>(U2))
+        checkBitCast(BI, GEP1, GV1);
+      else if (auto *GEP2 = dyn_cast<GetElementPtrInst>(U2))
+        checkGEP(GEP2, GEP1, GV1);
+    }
+  }
+}
+
+bool BPFCheckAndAdjustIR::adjustIR(Module &M) {
+  bool Changed = false;
+
+  Changed = removePassThroughBuiltin(M);
+  Changed = optimizeReloc(M) || Changed;
+
+  return false;
+}

llvm/lib/Target/BPF/BPFPreserveDIType.cpp

 namespace llvm {
 constexpr StringRef BPFCoreSharedInfo::TypeIdAttr;
 } // namespace llvm
 
 using namespace llvm;
 
 namespace {
 
-class BPFPreserveDIType final : public ModulePass {
-  StringRef getPassName() const override {
-    return "BPF Preserve DebugInfo Type";
-  }
-
-  bool runOnModule(Module &M) override;
+class BPFPreserveDIType final : public FunctionPass {
+  bool runOnFunction(Function &F) override;
 
 public:
   static char ID;
-  BPFPreserveDIType() : ModulePass(ID) {}
+  BPFPreserveDIType() : FunctionPass(ID) {}
 
 private:
-  bool doTransformation(Module &M);
+  Module *M = nullptr;
+
+  bool doTransformation(Function &F);
 };
 } // End anonymous namespace
 
 char BPFPreserveDIType::ID = 0;
-INITIALIZE_PASS(BPFPreserveDIType, DEBUG_TYPE, "preserve debuginfo type", false,
-                false)
+INITIALIZE_PASS(BPFPreserveDIType, DEBUG_TYPE, "BPF Preserve Debuginfo Type",
+                false, false)
 
-ModulePass *llvm::createBPFPreserveDIType() { return new BPFPreserveDIType(); }
+FunctionPass *llvm::createBPFPreserveDIType() { return new BPFPreserveDIType(); }
 
-bool BPFPreserveDIType::runOnModule(Module &M) {
+bool BPFPreserveDIType::runOnFunction(Function &F) {
   LLVM_DEBUG(dbgs() << "********** preserve debuginfo type **********\n");
 
+  M = F.getParent();
+  if (!M)
+    return false;
+
   // Bail out if no debug info.
-  if (M.debug_compile_units().empty())
+  if (M->debug_compile_units().empty())
     return false;
 
-  return doTransformation(M);
+  return doTransformation(F);
 }
 
-bool BPFPreserveDIType::doTransformation(Module &M) {
+bool BPFPreserveDIType::doTransformation(Function &F) {
   std::vector<CallInst *> PreserveDITypeCalls;
 
-  for (auto &F : M) {
-    for (auto &BB : F) {
-      for (auto &I : BB) {
-        auto *Call = dyn_cast<CallInst>(&I);
-        if (!Call)
-          continue;
 
-        const auto *GV = dyn_cast<GlobalValue>(Call->getCalledOperand());
-        if (!GV)
-          continue;
 
-        if (GV->getName().startswith("llvm.bpf.btf.type.id")) {
-          if (!Call->getMetadata(LLVMContext::MD_preserve_access_index))
-            report_fatal_error(
-                "Missing metadata for llvm.bpf.btf.type.id intrinsic");
-          PreserveDITypeCalls.push_back(Call);
-        }
-      }
-    }
-  }
 
   if (PreserveDITypeCalls.empty())
     return false;
 
   std::string BaseName = "llvm.btf_type_id.";
   int Count = 0;
   for (auto Call : PreserveDITypeCalls) {
     const ConstantInt *Flag = dyn_cast<ConstantInt>(Call->getArgOperand(1));
if (FlagValue == BPFCoreSharedInfo::BTF_TYPE_ID_LOCAL_RELOC) {
       if (Ty->getName().empty())
         report_fatal_error("Empty type name for BTF_TYPE_ID_REMOTE reloc");
     }
 
     BasicBlock *BB = Call->getParent();
     IntegerType *VarType = Type::getInt32Ty(BB->getContext());
     std::string GVName = BaseName + std::to_string(Count) + "$" +
         std::to_string(Reloc);
     GlobalVariable *GV =
-        new GlobalVariable(M, VarType, false, GlobalVariable::ExternalLinkage,
+        new GlobalVariable(*M, VarType, false, GlobalVariable::ExternalLinkage,
                            NULL, GVName);
     GV->addAttribute(BPFCoreSharedInfo::TypeIdAttr);
     GV->setMetadata(LLVMContext::MD_preserve_access_index, MD);
 
     // Load the global variable which represents the type info.
     auto *LDInst = new LoadInst(Type::getInt32Ty(BB->getContext()), GV, "",
                                 Call);
-    Call->replaceAllUsesWith(LDInst);
+    Instruction *PassThroughInst =
+        BPFCoreSharedInfo::insertPassThrough(M, BB, LDInst, Call);
+    Call->replaceAllUsesWith(PassThroughInst);
     Call->eraseFromParent();
     Count++;
   }
 
   return true;
 }

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();
   initializeBPFAbstractMemberAccessPass(PR);
   initializeBPFPreserveDITypePass(PR);
+  initializeBPFCheckAndAdjustIRPass(PR);
   initializeBPFMIPeepholePass(PR);
   initializeBPFMIPeepholeTruncElimPass(PR);
 }
 
 // DataLayout: little or big endian
 static std::string computeDataLayout(const Triple &TT) {
   if (TT.getArch() == Triple::bpfeb)
     return "E-m:e-p:64:64-i64:64-i128:128-n32:64-S128";

 };
 }
 
 TargetPassConfig *BPFTargetMachine::createPassConfig(PassManagerBase &PM) {
   return new BPFPassConfig(*this, PM);
 }
 
 void BPFTargetMachine::adjustPassManager(PassManagerBuilder &Builder) {
-  Builder.addExtension(
+      PassManagerBuilder::EP_EarlyAsPossible,
+      [&](const PassManagerBuilder &, legacy::PassManagerBase &PM) {
+        PM.add(createBPFAbstractMemberAccess(this));
+        PM.add(createBPFPreserveDIType());
+      });
+
+  Builder.addExtension(
       PassManagerBuilder::EP_Peephole,
       [&](const PassManagerBuilder &, legacy::PassManagerBase &PM) {
         PM.add(createCFGSimplificationPass(
             SimplifyCFGOptions().hoistCommonInsts(true)));
       });
 }
 
 void BPFPassConfig::addIRPasses() {
-  addPass(createBPFAbstractMemberAccess(&getBPFTargetMachine()));
-  addPass(createBPFPreserveDIType());
-
+  addPass(createBPFCheckAndAdjustIR());
   TargetPassConfig::addIRPasses();
 }
 
 // Install an instruction selector pass using
 // the ISelDag to gen BPF code.
 bool BPFPassConfig::addInstSelector() {
   addPass(createBPFISelDag(getBPFTargetMachine()));
 

llvm/lib/Target/BPF/CMakeLists.txt

 tablegen(LLVM BPFGenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM BPFGenSubtargetInfo.inc -gen-subtarget)
 
 add_public_tablegen_target(BPFCommonTableGen)
 
 add_llvm_target(BPFCodeGen
   BPFAbstractMemberAccess.cpp
   BPFAsmPrinter.cpp
+  BPFCheckAndAdjustIR.cpp
   BPFFrameLowering.cpp
   BPFInstrInfo.cpp
   BPFISelDAGToDAG.cpp
   BPFISelLowering.cpp
   BPFMCInstLower.cpp
   BPFPreserveDIType.cpp
   BPFRegisterInfo.cpp
   BPFSelectionDAGInfo.cpp