lib/Target/BPF/BPFAbstractMemberAccess.cpp

   1 //===------ BPFAbstractMemberAccess.cpp - Abstracting Member Accesses -----===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This pass abstracted struct/union member accesses in order to support
  10 // compile-once run-everywhere (CO-RE). The CO-RE intends to compile the program
  11 // which can run on different kernels. In particular, if bpf program tries to
  12 // access a particular kernel data structure member, the details of the
  13 // intermediate member access will be remembered so bpf loader can do
  14 // necessary adjustment right before program loading.
  15 //
  16 // For example,
  17 //
  18 //   struct s {
  19 //     int a;
  20 //     int b;
  21 //   };
  22 //   struct t {
  23 //     struct s c;
  24 //     int d;
  25 //   };
  26 //   struct t e;
  27 //
  28 // For the member access e.c.b, the compiler will generate code
  29 //   &e + 4
  30 //
  31 // The compile-once run-everywhere instead generates the following code
  32 //   r = 4
  33 //   &e + r
  34 // The "4" in "r = 4" can be changed based on a particular kernel version.
  35 // For example, on a particular kernel version, if struct s is changed to
  36 //
  37 //   struct s {
  38 //     int new_field;
  39 //     int a;
  40 //     int b;
  41 //   }
  42 //
  43 // By repeating the member access on the host, the bpf loader can
  44 // adjust "r = 4" as "r = 8".
  45 //
  46 // This feature relies on the following three intrinsic calls:
  47 //   addr = preserve_array_access_index(base, dimension, index)
  48 //   addr = preserve_union_access_index(base, di_index)
  49 //          !llvm.preserve.access.index <union_ditype>
  50 //   addr = preserve_struct_access_index(base, gep_index, di_index)
  51 //          !llvm.preserve.access.index <struct_ditype>
  52 //
  53 //===----------------------------------------------------------------------===//
  54
  55 #include "BPF.h"
  56 #include "BPFCORE.h"
  57 #include "BPFTargetMachine.h"
  58 #include "llvm/IR/DebugInfoMetadata.h"
  59 #include "llvm/IR/GlobalVariable.h"
  60 #include "llvm/IR/Instruction.h"
  61 #include "llvm/IR/Instructions.h"
  62 #include "llvm/IR/Module.h"
  63 #include "llvm/IR/Type.h"
  64 #include "llvm/IR/User.h"
  65 #include "llvm/IR/Value.h"
  66 #include "llvm/Pass.h"
  67 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  68 #include <stack>
  69
  70 #define DEBUG_TYPE "bpf-abstract-member-access"
  71
  72 namespace llvm {
  73 const std::string BPFCoreSharedInfo::AmaAttr = "btf_ama";
  74 const std::string BPFCoreSharedInfo::PatchableExtSecName =
  75     ".BPF.patchable_externs";
  76 } // namespace llvm
  77
  78 using namespace llvm;
  79
  80 namespace {
  81
  82 class BPFAbstractMemberAccess final : public ModulePass {
  83   StringRef getPassName() const override {
  84     return "BPF Abstract Member Access";
  85   }
  86
  87   bool runOnModule(Module &M) override;
  88
  89 public:
  90   static char ID;
  91   BPFAbstractMemberAccess() : ModulePass(ID) {}
  92
  93 private:
  94   enum : uint32_t {
  95     BPFPreserveArrayAI = 1,
  96     BPFPreserveUnionAI = 2,
  97     BPFPreserveStructAI = 3,
  98   };
  99
 100   std::map<std::string, GlobalVariable *> GEPGlobals;
 101   // A map to link preserve_*_access_index instrinsic calls.
 102   std::map<CallInst *, std::pair<CallInst *, uint32_t>> AIChain;
 103   // A map to hold all the base preserve_*_access_index instrinsic calls.
 104   // The base call is not an input of any other preserve_*_access_index
 105   // intrinsics.
 106   std::map<CallInst *, uint32_t> BaseAICalls;
 107
 108   bool doTransformation(Module &M);
 109
 110   void traceAICall(CallInst *Call, uint32_t Kind, const MDNode *ParentMeta,
 111                    uint32_t ParentAI);
 112   void traceBitCast(BitCastInst *BitCast, CallInst *Parent, uint32_t Kind,
 113                     const MDNode *ParentMeta, uint32_t ParentAI);
 114   void traceGEP(GetElementPtrInst *GEP, CallInst *Parent, uint32_t Kind,
 115                 const MDNode *ParentMeta, uint32_t ParentAI);
 116   void collectAICallChains(Module &M, Function &F);
 117
 118   bool IsPreserveDIAccessIndexCall(const CallInst *Call, uint32_t &Kind,
 119                                    const MDNode *&TypeMeta, uint32_t &AccessIndex);
 120   bool IsValidAIChain(const MDNode *ParentMeta, uint32_t ParentAI,
 121                       const MDNode *ChildMeta);
 122   bool removePreserveAccessIndexIntrinsic(Module &M);
 123   void replaceWithGEP(std::vector<CallInst *> &CallList,
 124                       uint32_t NumOfZerosIndex, uint32_t DIIndex);
 125
 126   Value *computeBaseAndAccessKey(CallInst *Call, std::string &AccessKey,
 127                                  uint32_t Kind, MDNode *&BaseMeta);
 128   bool getAccessIndex(const Value *IndexValue, uint64_t &AccessIndex);
 129   bool transformGEPChain(Module &M, CallInst *Call, uint32_t Kind);
 130 };
 131 } // End anonymous namespace
 132
 133 char BPFAbstractMemberAccess::ID = 0;
 134 INITIALIZE_PASS(BPFAbstractMemberAccess, DEBUG_TYPE,
 135                 "abstracting struct/union member accessees", false, false)
 136
 137 ModulePass *llvm::createBPFAbstractMemberAccess() {
 138   return new BPFAbstractMemberAccess();
 139 }
 140
 141 bool BPFAbstractMemberAccess::runOnModule(Module &M) {
 142   LLVM_DEBUG(dbgs() << "********** Abstract Member Accesses **********\n");
 143
 144   // Bail out if no debug info.
 145   if (empty(M.debug_compile_units()))
 146     return false;
 147
 148   return doTransformation(M);
 149 }
 150
 151 static bool SkipDIDerivedTag(unsigned Tag) {
 152   if (Tag != dwarf::DW_TAG_typedef && Tag != dwarf::DW_TAG_const_type &&
 153       Tag != dwarf::DW_TAG_volatile_type &&
 154       Tag != dwarf::DW_TAG_restrict_type &&
 155       Tag != dwarf::DW_TAG_member)
 156      return false;
 157   return true;
 158 }
 159
 160 static DIType * stripQualifiers(DIType *Ty) {
 161   while (auto *DTy = dyn_cast<DIDerivedType>(Ty)) {
 162     if (!SkipDIDerivedTag(DTy->getTag()))
 163       break;
 164     Ty = DTy->getBaseType();
 165   }
 166   return Ty;
 167 }
 168
 169 static const DIType * stripQualifiers(const DIType *Ty) {
 170   while (auto *DTy = dyn_cast<DIDerivedType>(Ty)) {
 171     if (!SkipDIDerivedTag(DTy->getTag()))
 172       break;
 173     Ty = DTy->getBaseType();
 174   }
 175   return Ty;
 176 }
 177
 178 static uint32_t calcArraySize(const DICompositeType *CTy, uint32_t StartDim) {
 179   DINodeArray Elements = CTy->getElements();
 180   uint32_t DimSize = 1;
 181   for (uint32_t I = StartDim; I < Elements.size(); ++I) {
 182     if (auto *Element = dyn_cast_or_null<DINode>(Elements[I]))
 183       if (Element->getTag() == dwarf::DW_TAG_subrange_type) {
 184         const DISubrange *SR = cast<DISubrange>(Element);
 185         auto *CI = SR->getCount().dyn_cast<ConstantInt *>();
 186         DimSize *= CI->getSExtValue();
 187       }
 188   }
 189
 190   return DimSize;
 191 }
 192
 193 /// Check whether a call is a preserve_*_access_index intrinsic call or not.
 194 bool BPFAbstractMemberAccess::IsPreserveDIAccessIndexCall(const CallInst *Call,
 195                                                           uint32_t &Kind,
 196                                                           const MDNode *&TypeMeta,
 197                                                           uint32_t &AccessIndex) {
 198   if (!Call)
 199     return false;
 200
 201   const auto *GV = dyn_cast<GlobalValue>(Call->getCalledValue());
 202   if (!GV)
 203     return false;
 204   if (GV->getName().startswith("llvm.preserve.array.access.index")) {
 205     Kind = BPFPreserveArrayAI;
 206     TypeMeta = Call->getMetadata(LLVMContext::MD_preserve_access_index);
 207     if (!TypeMeta)
 208       report_fatal_error("Missing metadata for llvm.preserve.array.access.index intrinsic");
 209     AccessIndex = cast<ConstantInt>(Call->getArgOperand(2))
 210                       ->getZExtValue();
 211     return true;
 212   }
 213   if (GV->getName().startswith("llvm.preserve.union.access.index")) {
 214     Kind = BPFPreserveUnionAI;
 215     TypeMeta = Call->getMetadata(LLVMContext::MD_preserve_access_index);
 216     if (!TypeMeta)
 217       report_fatal_error("Missing metadata for llvm.preserve.union.access.index intrinsic");
 218     AccessIndex = cast<ConstantInt>(Call->getArgOperand(1))
 219                       ->getZExtValue();
 220     return true;
 221   }
 222   if (GV->getName().startswith("llvm.preserve.struct.access.index")) {
 223     Kind = BPFPreserveStructAI;
 224     TypeMeta = Call->getMetadata(LLVMContext::MD_preserve_access_index);
 225     if (!TypeMeta)
 226       report_fatal_error("Missing metadata for llvm.preserve.struct.access.index intrinsic");
 227     AccessIndex = cast<ConstantInt>(Call->getArgOperand(2))
 228                       ->getZExtValue();
 229     return true;
 230   }
 231
 232   return false;
 233 }
 234
 235 void BPFAbstractMemberAccess::replaceWithGEP(std::vector<CallInst *> &CallList,
 236                                              uint32_t DimensionIndex,
 237                                              uint32_t GEPIndex) {
 238   for (auto Call : CallList) {
 239     uint32_t Dimension = 1;
 240     if (DimensionIndex > 0)
 241       Dimension = cast<ConstantInt>(Call->getArgOperand(DimensionIndex))
 242                       ->getZExtValue();
 243
 244     Constant *Zero =
 245         ConstantInt::get(Type::getInt32Ty(Call->getParent()->getContext()), 0);
 246     SmallVector<Value *, 4> IdxList;
 247     for (unsigned I = 0; I < Dimension; ++I)
 248       IdxList.push_back(Zero);
 249     IdxList.push_back(Call->getArgOperand(GEPIndex));
 250
 251     auto *GEP = GetElementPtrInst::CreateInBounds(Call->getArgOperand(0),
 252                                                   IdxList, "", Call);
 253     Call->replaceAllUsesWith(GEP);
 254     Call->eraseFromParent();
 255   }
 256 }
 257
 258 bool BPFAbstractMemberAccess::removePreserveAccessIndexIntrinsic(Module &M) {
 259   std::vector<CallInst *> PreserveArrayIndexCalls;
 260   std::vector<CallInst *> PreserveUnionIndexCalls;
 261   std::vector<CallInst *> PreserveStructIndexCalls;
 262   bool Found = false;
 263
 264   for (Function &F : M)
 265     for (auto &BB : F)
 266       for (auto &I : BB) {
 267         auto *Call = dyn_cast<CallInst>(&I);
 268         uint32_t Kind;
 269         const MDNode *TypeMeta;
 270         uint32_t AccessIndex;
 271         if (!IsPreserveDIAccessIndexCall(Call, Kind, TypeMeta, AccessIndex))
 272           continue;
 273
 274         Found = true;
 275         if (Kind == BPFPreserveArrayAI)
 276           PreserveArrayIndexCalls.push_back(Call);
 277         else if (Kind == BPFPreserveUnionAI)
 278           PreserveUnionIndexCalls.push_back(Call);
 279         else
 280           PreserveStructIndexCalls.push_back(Call);
 281       }
 282
 283   // do the following transformation:
 284   // . addr = preserve_array_access_index(base, dimension, index)
 285   //   is transformed to
 286   //     addr = GEP(base, dimenion's zero's, index)
 287   // . addr = preserve_union_access_index(base, di_index)
 288   //   is transformed to
 289   //     addr = base, i.e., all usages of "addr" are replaced by "base".
 290   // . addr = preserve_struct_access_index(base, gep_index, di_index)
 291   //   is transformed to
 292   //     addr = GEP(base, 0, gep_index)
 293   replaceWithGEP(PreserveArrayIndexCalls, 1, 2);
 294   replaceWithGEP(PreserveStructIndexCalls, 0, 1);
 295   for (auto Call : PreserveUnionIndexCalls) {
 296     Call->replaceAllUsesWith(Call->getArgOperand(0));
 297     Call->eraseFromParent();
 298   }
 299
 300   return Found;
 301 }
 302
 303 /// Check whether the access index chain is valid. We check
 304 /// here because there may be type casts between two
 305 /// access indexes. We want to ensure memory access still valid.
 306 bool BPFAbstractMemberAccess::IsValidAIChain(const MDNode *ParentType,
 307                                              uint32_t ParentAI,
 308                                              const MDNode *ChildType) {
 309   const DIType *PType = stripQualifiers(cast<DIType>(ParentType));
 310   const DIType *CType = stripQualifiers(cast<DIType>(ChildType));
 311
 312   // Child is a derived/pointer type, which is due to type casting.
 313   // Pointer type cannot be in the middle of chain.
 314   if (isa<DIDerivedType>(CType))
 315     return false;
 316
 317   // Parent is a pointer type.
 318   if (const auto *PtrTy = dyn_cast<DIDerivedType>(PType)) {
 319     if (PtrTy->getTag() != dwarf::DW_TAG_pointer_type)
 320       return false;
 321     return stripQualifiers(PtrTy->getBaseType()) == CType;
 322   }
 323
 324   // Otherwise, struct/union/array types
 325   const auto *PTy = dyn_cast<DICompositeType>(PType);
 326   const auto *CTy = dyn_cast<DICompositeType>(CType);
 327   assert(PTy && CTy && "ParentType or ChildType is null or not composite");
 328
 329   uint32_t PTyTag = PTy->getTag();
 330   assert(PTyTag == dwarf::DW_TAG_array_type ||
 331          PTyTag == dwarf::DW_TAG_structure_type ||
 332          PTyTag == dwarf::DW_TAG_union_type);
 333
 334   uint32_t CTyTag = CTy->getTag();
 335   assert(CTyTag == dwarf::DW_TAG_array_type ||
 336          CTyTag == dwarf::DW_TAG_structure_type ||
 337          CTyTag == dwarf::DW_TAG_union_type);
 338
 339   // Multi dimensional arrays, base element should be the same
 340   if (PTyTag == dwarf::DW_TAG_array_type && PTyTag == CTyTag)
 341     return PTy->getBaseType() == CTy->getBaseType();
 342
 343   DIType *Ty;
 344   if (PTyTag == dwarf::DW_TAG_array_type)
 345     Ty = PTy->getBaseType();
 346   else
 347     Ty = dyn_cast<DIType>(PTy->getElements()[ParentAI]);
 348
 349   return dyn_cast<DICompositeType>(stripQualifiers(Ty)) == CTy;
 350 }
 351
 352 void BPFAbstractMemberAccess::traceAICall(CallInst *Call, uint32_t Kind,
 353                                           const MDNode *ParentMeta,
 354                                           uint32_t ParentAI) {
 355   for (User *U : Call->users()) {
 356     Instruction *Inst = dyn_cast<Instruction>(U);
 357     if (!Inst)
 358       continue;
 359
 360     if (auto *BI = dyn_cast<BitCastInst>(Inst)) {
 361       traceBitCast(BI, Call, Kind, ParentMeta, ParentAI);
 362     } else if (auto *CI = dyn_cast<CallInst>(Inst)) {
 363       uint32_t CIKind;
 364       const MDNode *ChildMeta;
 365       uint32_t ChildAI;
 366       if (IsPreserveDIAccessIndexCall(CI, CIKind, ChildMeta, ChildAI) &&
 367           IsValidAIChain(ParentMeta, ParentAI, ChildMeta)) {
 368         AIChain[CI] = std::make_pair(Call, Kind);
 369         traceAICall(CI, CIKind, ChildMeta, ChildAI);
 370       } else {
 371         BaseAICalls[Call] = Kind;
 372       }
 373     } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
 374       if (GI->hasAllZeroIndices())
 375         traceGEP(GI, Call, Kind, ParentMeta, ParentAI);
 376       else
 377         BaseAICalls[Call] = Kind;
 378     } else {
 379       BaseAICalls[Call] = Kind;
 380     }
 381   }
 382 }
 383
 384 void BPFAbstractMemberAccess::traceBitCast(BitCastInst *BitCast,
 385                                            CallInst *Parent, uint32_t Kind,
 386                                            const MDNode *ParentMeta,
 387                                            uint32_t ParentAI) {
 388   for (User *U : BitCast->users()) {
 389     Instruction *Inst = dyn_cast<Instruction>(U);
 390     if (!Inst)
 391       continue;
 392
 393     if (auto *BI = dyn_cast<BitCastInst>(Inst)) {
 394       traceBitCast(BI, Parent, Kind, ParentMeta, ParentAI);
 395     } else if (auto *CI = dyn_cast<CallInst>(Inst)) {
 396       uint32_t CIKind;
 397       const MDNode *ChildMeta;
 398       uint32_t ChildAI;
 399       if (IsPreserveDIAccessIndexCall(CI, CIKind, ChildMeta, ChildAI) &&
 400           IsValidAIChain(ParentMeta, ParentAI, ChildMeta)) {
 401         AIChain[CI] = std::make_pair(Parent, Kind);
 402         traceAICall(CI, CIKind, ChildMeta, ChildAI);
 403       } else {
 404         BaseAICalls[Parent] = Kind;
 405       }
 406     } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
 407       if (GI->hasAllZeroIndices())
 408         traceGEP(GI, Parent, Kind, ParentMeta, ParentAI);
 409       else
 410         BaseAICalls[Parent] = Kind;
 411     } else {
 412       BaseAICalls[Parent] = Kind;
 413     }
 414   }
 415 }
 416
 417 void BPFAbstractMemberAccess::traceGEP(GetElementPtrInst *GEP, CallInst *Parent,
 418                                        uint32_t Kind, const MDNode *ParentMeta,
 419                                        uint32_t ParentAI) {
 420   for (User *U : GEP->users()) {
 421     Instruction *Inst = dyn_cast<Instruction>(U);
 422     if (!Inst)
 423       continue;
 424
 425     if (auto *BI = dyn_cast<BitCastInst>(Inst)) {
 426       traceBitCast(BI, Parent, Kind, ParentMeta, ParentAI);
 427     } else if (auto *CI = dyn_cast<CallInst>(Inst)) {
 428       uint32_t CIKind;
 429       const MDNode *ChildMeta;
 430       uint32_t ChildAI;
 431       if (IsPreserveDIAccessIndexCall(CI, CIKind, ChildMeta, ChildAI) &&
 432           IsValidAIChain(ParentMeta, ParentAI, ChildMeta)) {
 433         AIChain[CI] = std::make_pair(Parent, Kind);
 434         traceAICall(CI, CIKind, ChildMeta, ChildAI);
 435       } else {
 436         BaseAICalls[Parent] = Kind;
 437       }
 438     } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
 439       if (GI->hasAllZeroIndices())
 440         traceGEP(GI, Parent, Kind, ParentMeta, ParentAI);
 441       else
 442         BaseAICalls[Parent] = Kind;
 443     } else {
 444       BaseAICalls[Parent] = Kind;
 445     }
 446   }
 447 }
 448
 449 void BPFAbstractMemberAccess::collectAICallChains(Module &M, Function &F) {
 450   AIChain.clear();
 451   BaseAICalls.clear();
 452
 453   for (auto &BB : F)
 454     for (auto &I : BB) {
 455       uint32_t Kind;
 456       const MDNode *TypeMeta;
 457       uint32_t AccessIndex;
 458       auto *Call = dyn_cast<CallInst>(&I);
 459       if (!IsPreserveDIAccessIndexCall(Call, Kind, TypeMeta, AccessIndex) ||
 460           AIChain.find(Call) != AIChain.end())
 461         continue;
 462
 463       traceAICall(Call, Kind, TypeMeta, AccessIndex);
 464     }
 465 }
 466
 467 /// Get access index from the preserve_*_access_index intrinsic calls.
 468 bool BPFAbstractMemberAccess::getAccessIndex(const Value *IndexValue,
 469                                              uint64_t &AccessIndex) {
 470   const ConstantInt *CV = dyn_cast<ConstantInt>(IndexValue);
 471   if (!CV)
 472     return false;
 473
 474   AccessIndex = CV->getValue().getZExtValue();
 475   return true;
 476 }
 477
 478 /// Compute the base of the whole preserve_*_access_index chains, i.e., the base
 479 /// pointer of the first preserve_*_access_index call, and construct the access
 480 /// string, which will be the name of a global variable.
 481 Value *BPFAbstractMemberAccess::computeBaseAndAccessKey(CallInst *Call,
 482                                                         std::string &AccessKey,
 483                                                         uint32_t Kind,
 484                                                         MDNode *&TypeMeta) {
 485   Value *Base = nullptr;
 486   std::string TypeName;
 487   std::stack<std::pair<CallInst *, uint32_t>> CallStack;
 488
 489   // Put the access chain into a stack with the top as the head of the chain.
 490   while (Call) {
 491     CallStack.push(std::make_pair(Call, Kind));
 492     Kind = AIChain[Call].second;
 493     Call = AIChain[Call].first;
 494   }
 495
 496   // The access offset from the base of the head of chain is also
 497   // calculated here as all debuginfo types are available.
 498
 499   // Get type name and calculate the first index.
 500   // We only want to get type name from structure or union.
 501   // If user wants a relocation like
 502   //    int *p; ... __builtin_preserve_access_index(&p[4]) ...
 503   // or
 504   //    int a[10][20]; ... __builtin_preserve_access_index(&a[2][3]) ...
 505   // we will skip them.
 506   uint32_t FirstIndex = 0;
 507   uint32_t AccessOffset = 0;
 508   while (CallStack.size()) {
 509     auto StackElem = CallStack.top();
 510     Call = StackElem.first;
 511     Kind = StackElem.second;
 512
 513     if (!Base)
 514       Base = Call->getArgOperand(0);
 515
 516     MDNode *MDN = Call->getMetadata(LLVMContext::MD_preserve_access_index);
 517     DIType *Ty = stripQualifiers(cast<DIType>(MDN));
 518     if (Kind == BPFPreserveUnionAI || Kind == BPFPreserveStructAI) {
 519       // struct or union type
 520       TypeName = Ty->getName();
 521       TypeMeta = Ty;
 522       AccessOffset += FirstIndex * Ty->getSizeInBits() >> 3;
 523       break;
 524     }
 525
 526     // Array entries will always be consumed for accumulative initial index.
 527     CallStack.pop();
 528
 529     // BPFPreserveArrayAI
 530     uint64_t AccessIndex;
 531     if (!getAccessIndex(Call->getArgOperand(2), AccessIndex))
 532       return nullptr;
 533
 534     DIType *BaseTy = nullptr;
 535     bool CheckElemType = false;
 536     if (const auto *CTy = dyn_cast<DICompositeType>(Ty)) {
 537       // array type
 538       assert(CTy->getTag() == dwarf::DW_TAG_array_type);
 539
 540
 541       FirstIndex += AccessIndex * calcArraySize(CTy, 1);
 542       BaseTy = stripQualifiers(CTy->getBaseType());
 543       CheckElemType = CTy->getElements().size() == 1;
 544     } else {
 545       // pointer type
 546       auto *DTy = cast<DIDerivedType>(Ty);
 547       assert(DTy->getTag() == dwarf::DW_TAG_pointer_type);
 548
 549       BaseTy = stripQualifiers(DTy->getBaseType());
 550       CTy = dyn_cast<DICompositeType>(BaseTy);
 551       if (!CTy) {
 552         CheckElemType = true;
 553       } else if (CTy->getTag() != dwarf::DW_TAG_array_type) {
 554         FirstIndex += AccessIndex;
 555         CheckElemType = true;
 556       } else {
 557         FirstIndex += AccessIndex * calcArraySize(CTy, 0);
 558       }
 559     }
 560
 561     if (CheckElemType) {
 562       auto *CTy = dyn_cast<DICompositeType>(BaseTy);
 563       if (!CTy)
 564         return nullptr;
 565
 566       unsigned CTag = CTy->getTag();
 567       if (CTag != dwarf::DW_TAG_structure_type && CTag != dwarf::DW_TAG_union_type)
 568         return nullptr;
 569       else
 570         TypeName = CTy->getName();
 571       TypeMeta = CTy;
 572       AccessOffset += FirstIndex * CTy->getSizeInBits() >> 3;
 573       break;
 574     }
 575   }
 576   assert(TypeName.size());
 577   AccessKey += std::to_string(FirstIndex);
 578
 579   // Traverse the rest of access chain to complete offset calculation
 580   // and access key construction.
 581   while (CallStack.size()) {
 582     auto StackElem = CallStack.top();
 583     Call = StackElem.first;
 584     Kind = StackElem.second;
 585     CallStack.pop();
 586
 587     // Access Index
 588     uint64_t AccessIndex;
 589     uint32_t ArgIndex = (Kind == BPFPreserveUnionAI) ? 1 : 2;
 590     if (!getAccessIndex(Call->getArgOperand(ArgIndex), AccessIndex))
 591       return nullptr;
 592     AccessKey += ":" + std::to_string(AccessIndex);
 593
 594     MDNode *MDN = Call->getMetadata(LLVMContext::MD_preserve_access_index);
 595     // At this stage, it cannot be pointer type.
 596     auto *CTy = cast<DICompositeType>(stripQualifiers(cast<DIType>(MDN)));
 597     uint32_t Tag = CTy->getTag();
 598     if (Tag == dwarf::DW_TAG_structure_type) {
 599       auto *MemberTy = cast<DIDerivedType>(CTy->getElements()[AccessIndex]);
 600       AccessOffset += MemberTy->getOffsetInBits() >> 3;
 601     } else if (Tag == dwarf::DW_TAG_array_type) {
 602       auto *EltTy = stripQualifiers(CTy->getBaseType());
 603       AccessOffset += AccessIndex * calcArraySize(CTy, 1) *
 604                       EltTy->getSizeInBits() >> 3;
 605     }
 606   }
 607
 608   // Access key is the type name + access string, uniquely identifying
 609   // one kernel memory access.
 610   AccessKey = TypeName + ":" + std::to_string(AccessOffset) + "$" + AccessKey;
 611
 612   return Base;
 613 }
 614
 615 /// Call/Kind is the base preserve_*_access_index() call. Attempts to do
 616 /// transformation to a chain of relocable GEPs.
 617 bool BPFAbstractMemberAccess::transformGEPChain(Module &M, CallInst *Call,
 618                                                 uint32_t Kind) {
 619   std::string AccessKey;
 620   MDNode *TypeMeta;
 621   Value *Base =
 622       computeBaseAndAccessKey(Call, AccessKey, Kind, TypeMeta);
 623   if (!Base)
 624     return false;
 625
 626   // Do the transformation
 627   // For any original GEP Call and Base %2 like
 628   //   %4 = bitcast %struct.net_device** %dev1 to i64*
 629   // it is transformed to:
 630   //   %6 = load sk_buff:50:$0:0:0:2:0
 631   //   %7 = bitcast %struct.sk_buff* %2 to i8*
 632   //   %8 = getelementptr i8, i8* %7, %6
 633   //   %9 = bitcast i8* %8 to i64*
 634   //   using %9 instead of %4
 635   // The original Call inst is removed.
 636   BasicBlock *BB = Call->getParent();
 637   GlobalVariable *GV;
 638
 639   if (GEPGlobals.find(AccessKey) == GEPGlobals.end()) {
 640     GV = new GlobalVariable(M, Type::getInt64Ty(BB->getContext()), false,
 641                             GlobalVariable::ExternalLinkage, NULL, AccessKey);
 642     GV->addAttribute(BPFCoreSharedInfo::AmaAttr);
 643     GV->setMetadata(LLVMContext::MD_preserve_access_index, TypeMeta);
 644     GEPGlobals[AccessKey] = GV;
 645   } else {
 646     GV = GEPGlobals[AccessKey];
 647   }
 648
 649   // Load the global variable.
 650   auto *LDInst = new LoadInst(Type::getInt64Ty(BB->getContext()), GV);
 651   BB->getInstList().insert(Call->getIterator(), LDInst);
 652
 653   // Generate a BitCast
 654   auto *BCInst = new BitCastInst(Base, Type::getInt8PtrTy(BB->getContext()));
 655   BB->getInstList().insert(Call->getIterator(), BCInst);
 656
 657   // Generate a GetElementPtr
 658   auto *GEP = GetElementPtrInst::Create(Type::getInt8Ty(BB->getContext()),
 659                                         BCInst, LDInst);
 660   BB->getInstList().insert(Call->getIterator(), GEP);
 661
 662   // Generate a BitCast
 663   auto *BCInst2 = new BitCastInst(GEP, Call->getType());
 664   BB->getInstList().insert(Call->getIterator(), BCInst2);
 665
 666   Call->replaceAllUsesWith(BCInst2);
 667   Call->eraseFromParent();
 668
 669   return true;
 670 }
 671
 672 bool BPFAbstractMemberAccess::doTransformation(Module &M) {
 673   bool Transformed = false;
 674
 675   for (Function &F : M) {
 676     // Collect PreserveDIAccessIndex Intrinsic call chains.
 677     // The call chains will be used to generate the access
 678     // patterns similar to GEP.
 679     collectAICallChains(M, F);
 680
 681     for (auto &C : BaseAICalls)
 682       Transformed = transformGEPChain(M, C.first, C.second) || Transformed;
 683   }
 684
 685   return removePreserveAccessIndexIntrinsic(M) || Transformed;
 686 }