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 // Bitfield member access needs special attention. User cannot take the
  54 // address of a bitfield acceess. To facilitate kernel verifier
  55 // for easy bitfield code optimization, a new clang intrinsic is introduced:
  56 //   uint32_t __builtin_preserve_field_info(member_access, info_kind)
  57 // In IR, a chain with two (or more) intrinsic calls will be generated:
  58 //   ...
  59 //   addr = preserve_struct_access_index(base, 1, 1) !struct s
  60 //   uint32_t result = bpf_preserve_field_info(addr, info_kind)
  61 //
  62 // Suppose the info_kind is FIELD_SIGNEDNESS,
  63 // The above two IR intrinsics will be replaced with
  64 // a relocatable insn:
  65 //   signness = /* signness of member_access */
  66 // and signness can be changed by bpf loader based on the
  67 // types on the host.
  68 //
  69 // User can also test whether a field exists or not with
  70 //   uint32_t result = bpf_preserve_field_info(member_access, FIELD_EXISTENCE)
  71 // The field will be always available (result = 1) during initial
  72 // compilation, but bpf loader can patch with the correct value
  73 // on the target host where the member_access may or may not be available
  74 //
  75 //===----------------------------------------------------------------------===//
  76
  77 #include "BPF.h"
  78 #include "BPFCORE.h"
  79 #include "BPFTargetMachine.h"
  80 #include "llvm/IR/DebugInfoMetadata.h"
  81 #include "llvm/IR/GlobalVariable.h"
  82 #include "llvm/IR/Instruction.h"
  83 #include "llvm/IR/Instructions.h"
  84 #include "llvm/IR/Module.h"
  85 #include "llvm/IR/Type.h"
  86 #include "llvm/IR/User.h"
  87 #include "llvm/IR/Value.h"
  88 #include "llvm/Pass.h"
  89 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  90 #include <stack>
  91
  92 #define DEBUG_TYPE "bpf-abstract-member-access"
  93
  94 namespace llvm {
  95 const std::string BPFCoreSharedInfo::AmaAttr = "btf_ama";
  96 } // namespace llvm
  97
  98 using namespace llvm;
  99
 100 namespace {
 101
 102 class BPFAbstractMemberAccess final : public ModulePass {
 103   StringRef getPassName() const override {
 104     return "BPF Abstract Member Access";
 105   }
 106
 107   bool runOnModule(Module &M) override;
 108
 109 public:
 110   static char ID;
 111   TargetMachine *TM;
 112   // Add optional BPFTargetMachine parameter so that BPF backend can add the phase
 113   // with target machine to find out the endianness. The default constructor (without
 114   // parameters) is used by the pass manager for managing purposes.
 115   BPFAbstractMemberAccess(BPFTargetMachine *TM = nullptr) : ModulePass(ID), TM(TM) {}
 116
 117   struct CallInfo {
 118     uint32_t Kind;
 119     uint32_t AccessIndex;
 120     MDNode *Metadata;
 121     Value *Base;
 122   };
 123   typedef std::stack<std::pair<CallInst *, CallInfo>> CallInfoStack;
 124
 125 private:
 126   enum : uint32_t {
 127     BPFPreserveArrayAI = 1,
 128     BPFPreserveUnionAI = 2,
 129     BPFPreserveStructAI = 3,
 130     BPFPreserveFieldInfoAI = 4,
 131   };
 132
 133   std::map<std::string, GlobalVariable *> GEPGlobals;
 134   // A map to link preserve_*_access_index instrinsic calls.
 135   std::map<CallInst *, std::pair<CallInst *, CallInfo>> AIChain;
 136   // A map to hold all the base preserve_*_access_index instrinsic calls.
 137   // The base call is not an input of any other preserve_*
 138   // intrinsics.
 139   std::map<CallInst *, CallInfo> BaseAICalls;
 140
 141   bool doTransformation(Module &M);
 142
 143   void traceAICall(CallInst *Call, CallInfo &ParentInfo);
 144   void traceBitCast(BitCastInst *BitCast, CallInst *Parent,
 145                     CallInfo &ParentInfo);
 146   void traceGEP(GetElementPtrInst *GEP, CallInst *Parent,
 147                 CallInfo &ParentInfo);
 148   void collectAICallChains(Module &M, Function &F);
 149
 150   bool IsPreserveDIAccessIndexCall(const CallInst *Call, CallInfo &Cinfo);
 151   bool IsValidAIChain(const MDNode *ParentMeta, uint32_t ParentAI,
 152                       const MDNode *ChildMeta);
 153   bool removePreserveAccessIndexIntrinsic(Module &M);
 154   void replaceWithGEP(std::vector<CallInst *> &CallList,
 155                       uint32_t NumOfZerosIndex, uint32_t DIIndex);
 156   bool HasPreserveFieldInfoCall(CallInfoStack &CallStack);
 157   void GetStorageBitRange(DICompositeType *CTy, DIDerivedType *MemberTy,
 158                           uint32_t AccessIndex, uint32_t &StartBitOffset,
 159                           uint32_t &EndBitOffset);
 160   uint32_t GetFieldInfo(uint32_t InfoKind, DICompositeType *CTy,
 161                         uint32_t AccessIndex, uint32_t PatchImm);
 162
 163   Value *computeBaseAndAccessKey(CallInst *Call, CallInfo &CInfo,
 164                                  std::string &AccessKey, MDNode *&BaseMeta);
 165   uint64_t getConstant(const Value *IndexValue);
 166   bool transformGEPChain(Module &M, CallInst *Call, CallInfo &CInfo);
 167 };
 168 } // End anonymous namespace
 169
 170 char BPFAbstractMemberAccess::ID = 0;
 171 INITIALIZE_PASS(BPFAbstractMemberAccess, DEBUG_TYPE,
 172                 "abstracting struct/union member accessees", false, false)
 173
 174 ModulePass *llvm::createBPFAbstractMemberAccess(BPFTargetMachine *TM) {
 175   return new BPFAbstractMemberAccess(TM);
 176 }
 177
 178 bool BPFAbstractMemberAccess::runOnModule(Module &M) {
 179   LLVM_DEBUG(dbgs() << "********** Abstract Member Accesses **********\n");
 180
 181   // Bail out if no debug info.
 182   if (M.debug_compile_units().empty())
 183     return false;
 184
 185   return doTransformation(M);
 186 }
 187
 188 static bool SkipDIDerivedTag(unsigned Tag) {
 189   if (Tag != dwarf::DW_TAG_typedef && Tag != dwarf::DW_TAG_const_type &&
 190       Tag != dwarf::DW_TAG_volatile_type &&
 191       Tag != dwarf::DW_TAG_restrict_type &&
 192       Tag != dwarf::DW_TAG_member)
 193      return false;
 194   return true;
 195 }
 196
 197 static DIType * stripQualifiers(DIType *Ty) {
 198   while (auto *DTy = dyn_cast<DIDerivedType>(Ty)) {
 199     if (!SkipDIDerivedTag(DTy->getTag()))
 200       break;
 201     Ty = DTy->getBaseType();
 202   }
 203   return Ty;
 204 }
 205
 206 static const DIType * stripQualifiers(const DIType *Ty) {
 207   while (auto *DTy = dyn_cast<DIDerivedType>(Ty)) {
 208     if (!SkipDIDerivedTag(DTy->getTag()))
 209       break;
 210     Ty = DTy->getBaseType();
 211   }
 212   return Ty;
 213 }
 214
 215 static uint32_t calcArraySize(const DICompositeType *CTy, uint32_t StartDim) {
 216   DINodeArray Elements = CTy->getElements();
 217   uint32_t DimSize = 1;
 218   for (uint32_t I = StartDim; I < Elements.size(); ++I) {
 219     if (auto *Element = dyn_cast_or_null<DINode>(Elements[I]))
 220       if (Element->getTag() == dwarf::DW_TAG_subrange_type) {
 221         const DISubrange *SR = cast<DISubrange>(Element);
 222         auto *CI = SR->getCount().dyn_cast<ConstantInt *>();
 223         DimSize *= CI->getSExtValue();
 224       }
 225   }
 226
 227   return DimSize;
 228 }
 229
 230 /// Check whether a call is a preserve_*_access_index intrinsic call or not.
 231 bool BPFAbstractMemberAccess::IsPreserveDIAccessIndexCall(const CallInst *Call,
 232                                                           CallInfo &CInfo) {
 233   if (!Call)
 234     return false;
 235
 236   const auto *GV = dyn_cast<GlobalValue>(Call->getCalledValue());
 237   if (!GV)
 238     return false;
 239   if (GV->getName().startswith("llvm.preserve.array.access.index")) {
 240     CInfo.Kind = BPFPreserveArrayAI;
 241     CInfo.Metadata = Call->getMetadata(LLVMContext::MD_preserve_access_index);
 242     if (!CInfo.Metadata)
 243       report_fatal_error("Missing metadata for llvm.preserve.array.access.index intrinsic");
 244     CInfo.AccessIndex = getConstant(Call->getArgOperand(2));
 245     CInfo.Base = Call->getArgOperand(0);
 246     return true;
 247   }
 248   if (GV->getName().startswith("llvm.preserve.union.access.index")) {
 249     CInfo.Kind = BPFPreserveUnionAI;
 250     CInfo.Metadata = Call->getMetadata(LLVMContext::MD_preserve_access_index);
 251     if (!CInfo.Metadata)
 252       report_fatal_error("Missing metadata for llvm.preserve.union.access.index intrinsic");
 253     CInfo.AccessIndex = getConstant(Call->getArgOperand(1));
 254     CInfo.Base = Call->getArgOperand(0);
 255     return true;
 256   }
 257   if (GV->getName().startswith("llvm.preserve.struct.access.index")) {
 258     CInfo.Kind = BPFPreserveStructAI;
 259     CInfo.Metadata = Call->getMetadata(LLVMContext::MD_preserve_access_index);
 260     if (!CInfo.Metadata)
 261       report_fatal_error("Missing metadata for llvm.preserve.struct.access.index intrinsic");
 262     CInfo.AccessIndex = getConstant(Call->getArgOperand(2));
 263     CInfo.Base = Call->getArgOperand(0);
 264     return true;
 265   }
 266   if (GV->getName().startswith("llvm.bpf.preserve.field.info")) {
 267     CInfo.Kind = BPFPreserveFieldInfoAI;
 268     CInfo.Metadata = nullptr;
 269     // Check validity of info_kind as clang did not check this.
 270     uint64_t InfoKind = getConstant(Call->getArgOperand(1));
 271     if (InfoKind >= BPFCoreSharedInfo::MAX_FIELD_RELOC_KIND)
 272       report_fatal_error("Incorrect info_kind for llvm.bpf.preserve.field.info intrinsic");
 273     CInfo.AccessIndex = InfoKind;
 274     return true;
 275   }
 276
 277   return false;
 278 }
 279
 280 void BPFAbstractMemberAccess::replaceWithGEP(std::vector<CallInst *> &CallList,
 281                                              uint32_t DimensionIndex,
 282                                              uint32_t GEPIndex) {
 283   for (auto Call : CallList) {
 284     uint32_t Dimension = 1;
 285     if (DimensionIndex > 0)
 286       Dimension = getConstant(Call->getArgOperand(DimensionIndex));
 287
 288     Constant *Zero =
 289         ConstantInt::get(Type::getInt32Ty(Call->getParent()->getContext()), 0);
 290     SmallVector<Value *, 4> IdxList;
 291     for (unsigned I = 0; I < Dimension; ++I)
 292       IdxList.push_back(Zero);
 293     IdxList.push_back(Call->getArgOperand(GEPIndex));
 294
 295     auto *GEP = GetElementPtrInst::CreateInBounds(Call->getArgOperand(0),
 296                                                   IdxList, "", Call);
 297     Call->replaceAllUsesWith(GEP);
 298     Call->eraseFromParent();
 299   }
 300 }
 301
 302 bool BPFAbstractMemberAccess::removePreserveAccessIndexIntrinsic(Module &M) {
 303   std::vector<CallInst *> PreserveArrayIndexCalls;
 304   std::vector<CallInst *> PreserveUnionIndexCalls;
 305   std::vector<CallInst *> PreserveStructIndexCalls;
 306   bool Found = false;
 307
 308   for (Function &F : M)
 309     for (auto &BB : F)
 310       for (auto &I : BB) {
 311         auto *Call = dyn_cast<CallInst>(&I);
 312         CallInfo CInfo;
 313         if (!IsPreserveDIAccessIndexCall(Call, CInfo))
 314           continue;
 315
 316         Found = true;
 317         if (CInfo.Kind == BPFPreserveArrayAI)
 318           PreserveArrayIndexCalls.push_back(Call);
 319         else if (CInfo.Kind == BPFPreserveUnionAI)
 320           PreserveUnionIndexCalls.push_back(Call);
 321         else
 322           PreserveStructIndexCalls.push_back(Call);
 323       }
 324
 325   // do the following transformation:
 326   // . addr = preserve_array_access_index(base, dimension, index)
 327   //   is transformed to
 328   //     addr = GEP(base, dimenion's zero's, index)
 329   // . addr = preserve_union_access_index(base, di_index)
 330   //   is transformed to
 331   //     addr = base, i.e., all usages of "addr" are replaced by "base".
 332   // . addr = preserve_struct_access_index(base, gep_index, di_index)
 333   //   is transformed to
 334   //     addr = GEP(base, 0, gep_index)
 335   replaceWithGEP(PreserveArrayIndexCalls, 1, 2);
 336   replaceWithGEP(PreserveStructIndexCalls, 0, 1);
 337   for (auto Call : PreserveUnionIndexCalls) {
 338     Call->replaceAllUsesWith(Call->getArgOperand(0));
 339     Call->eraseFromParent();
 340   }
 341
 342   return Found;
 343 }
 344
 345 /// Check whether the access index chain is valid. We check
 346 /// here because there may be type casts between two
 347 /// access indexes. We want to ensure memory access still valid.
 348 bool BPFAbstractMemberAccess::IsValidAIChain(const MDNode *ParentType,
 349                                              uint32_t ParentAI,
 350                                              const MDNode *ChildType) {
 351   if (!ChildType)
 352     return true; // preserve_field_info, no type comparison needed.
 353
 354   const DIType *PType = stripQualifiers(cast<DIType>(ParentType));
 355   const DIType *CType = stripQualifiers(cast<DIType>(ChildType));
 356
 357   // Child is a derived/pointer type, which is due to type casting.
 358   // Pointer type cannot be in the middle of chain.
 359   if (isa<DIDerivedType>(CType))
 360     return false;
 361
 362   // Parent is a pointer type.
 363   if (const auto *PtrTy = dyn_cast<DIDerivedType>(PType)) {
 364     if (PtrTy->getTag() != dwarf::DW_TAG_pointer_type)
 365       return false;
 366     return stripQualifiers(PtrTy->getBaseType()) == CType;
 367   }
 368
 369   // Otherwise, struct/union/array types
 370   const auto *PTy = dyn_cast<DICompositeType>(PType);
 371   const auto *CTy = dyn_cast<DICompositeType>(CType);
 372   assert(PTy && CTy && "ParentType or ChildType is null or not composite");
 373
 374   uint32_t PTyTag = PTy->getTag();
 375   assert(PTyTag == dwarf::DW_TAG_array_type ||
 376          PTyTag == dwarf::DW_TAG_structure_type ||
 377          PTyTag == dwarf::DW_TAG_union_type);
 378
 379   uint32_t CTyTag = CTy->getTag();
 380   assert(CTyTag == dwarf::DW_TAG_array_type ||
 381          CTyTag == dwarf::DW_TAG_structure_type ||
 382          CTyTag == dwarf::DW_TAG_union_type);
 383
 384   // Multi dimensional arrays, base element should be the same
 385   if (PTyTag == dwarf::DW_TAG_array_type && PTyTag == CTyTag)
 386     return PTy->getBaseType() == CTy->getBaseType();
 387
 388   DIType *Ty;
 389   if (PTyTag == dwarf::DW_TAG_array_type)
 390     Ty = PTy->getBaseType();
 391   else
 392     Ty = dyn_cast<DIType>(PTy->getElements()[ParentAI]);
 393
 394   return dyn_cast<DICompositeType>(stripQualifiers(Ty)) == CTy;
 395 }
 396
 397 void BPFAbstractMemberAccess::traceAICall(CallInst *Call,
 398                                           CallInfo &ParentInfo) {
 399   for (User *U : Call->users()) {
 400     Instruction *Inst = dyn_cast<Instruction>(U);
 401     if (!Inst)
 402       continue;
 403
 404     if (auto *BI = dyn_cast<BitCastInst>(Inst)) {
 405       traceBitCast(BI, Call, ParentInfo);
 406     } else if (auto *CI = dyn_cast<CallInst>(Inst)) {
 407       CallInfo ChildInfo;
 408
 409       if (IsPreserveDIAccessIndexCall(CI, ChildInfo) &&
 410           IsValidAIChain(ParentInfo.Metadata, ParentInfo.AccessIndex,
 411                          ChildInfo.Metadata)) {
 412         AIChain[CI] = std::make_pair(Call, ParentInfo);
 413         traceAICall(CI, ChildInfo);
 414       } else {
 415         BaseAICalls[Call] = ParentInfo;
 416       }
 417     } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
 418       if (GI->hasAllZeroIndices())
 419         traceGEP(GI, Call, ParentInfo);
 420       else
 421         BaseAICalls[Call] = ParentInfo;
 422     } else {
 423       BaseAICalls[Call] = ParentInfo;
 424     }
 425   }
 426 }
 427
 428 void BPFAbstractMemberAccess::traceBitCast(BitCastInst *BitCast,
 429                                            CallInst *Parent,
 430                                            CallInfo &ParentInfo) {
 431   for (User *U : BitCast->users()) {
 432     Instruction *Inst = dyn_cast<Instruction>(U);
 433     if (!Inst)
 434       continue;
 435
 436     if (auto *BI = dyn_cast<BitCastInst>(Inst)) {
 437       traceBitCast(BI, Parent, ParentInfo);
 438     } else if (auto *CI = dyn_cast<CallInst>(Inst)) {
 439       CallInfo ChildInfo;
 440       if (IsPreserveDIAccessIndexCall(CI, ChildInfo) &&
 441           IsValidAIChain(ParentInfo.Metadata, ParentInfo.AccessIndex,
 442                          ChildInfo.Metadata)) {
 443         AIChain[CI] = std::make_pair(Parent, ParentInfo);
 444         traceAICall(CI, ChildInfo);
 445       } else {
 446         BaseAICalls[Parent] = ParentInfo;
 447       }
 448     } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
 449       if (GI->hasAllZeroIndices())
 450         traceGEP(GI, Parent, ParentInfo);
 451       else
 452         BaseAICalls[Parent] = ParentInfo;
 453     } else {
 454       BaseAICalls[Parent] = ParentInfo;
 455     }
 456   }
 457 }
 458
 459 void BPFAbstractMemberAccess::traceGEP(GetElementPtrInst *GEP, CallInst *Parent,
 460                                        CallInfo &ParentInfo) {
 461   for (User *U : GEP->users()) {
 462     Instruction *Inst = dyn_cast<Instruction>(U);
 463     if (!Inst)
 464       continue;
 465
 466     if (auto *BI = dyn_cast<BitCastInst>(Inst)) {
 467       traceBitCast(BI, Parent, ParentInfo);
 468     } else if (auto *CI = dyn_cast<CallInst>(Inst)) {
 469       CallInfo ChildInfo;
 470       if (IsPreserveDIAccessIndexCall(CI, ChildInfo) &&
 471           IsValidAIChain(ParentInfo.Metadata, ParentInfo.AccessIndex,
 472                          ChildInfo.Metadata)) {
 473         AIChain[CI] = std::make_pair(Parent, ParentInfo);
 474         traceAICall(CI, ChildInfo);
 475       } else {
 476         BaseAICalls[Parent] = ParentInfo;
 477       }
 478     } else if (auto *GI = dyn_cast<GetElementPtrInst>(Inst)) {
 479       if (GI->hasAllZeroIndices())
 480         traceGEP(GI, Parent, ParentInfo);
 481       else
 482         BaseAICalls[Parent] = ParentInfo;
 483     } else {
 484       BaseAICalls[Parent] = ParentInfo;
 485     }
 486   }
 487 }
 488
 489 void BPFAbstractMemberAccess::collectAICallChains(Module &M, Function &F) {
 490   AIChain.clear();
 491   BaseAICalls.clear();
 492
 493   for (auto &BB : F)
 494     for (auto &I : BB) {
 495       CallInfo CInfo;
 496       auto *Call = dyn_cast<CallInst>(&I);
 497       if (!IsPreserveDIAccessIndexCall(Call, CInfo) ||
 498           AIChain.find(Call) != AIChain.end())
 499         continue;
 500
 501       traceAICall(Call, CInfo);
 502     }
 503 }
 504
 505 uint64_t BPFAbstractMemberAccess::getConstant(const Value *IndexValue) {
 506   const ConstantInt *CV = dyn_cast<ConstantInt>(IndexValue);
 507   assert(CV);
 508   return CV->getValue().getZExtValue();
 509 }
 510
 511 /// Get the start and the end of storage offset for \p MemberTy.
 512 /// The storage bits are corresponding to the LLVM internal types,
 513 /// and the storage bits for the member determines what load width
 514 /// to use in order to extract the bitfield value.
 515 void BPFAbstractMemberAccess::GetStorageBitRange(DICompositeType *CTy,
 516                                                  DIDerivedType *MemberTy,
 517                                                  uint32_t AccessIndex,
 518                                                  uint32_t &StartBitOffset,
 519                                                  uint32_t &EndBitOffset) {
 520   auto SOff = dyn_cast<ConstantInt>(MemberTy->getStorageOffsetInBits());
 521   assert(SOff);
 522   StartBitOffset = SOff->getZExtValue();
 523
 524   EndBitOffset = CTy->getSizeInBits();
 525   uint32_t Index = AccessIndex + 1;
 526   for (; Index < CTy->getElements().size(); ++Index) {
 527     auto Member = cast<DIDerivedType>(CTy->getElements()[Index]);
 528     if (!Member->getStorageOffsetInBits()) {
 529       EndBitOffset = Member->getOffsetInBits();
 530       break;
 531     }
 532     SOff = dyn_cast<ConstantInt>(Member->getStorageOffsetInBits());
 533     assert(SOff);
 534     unsigned BitOffset = SOff->getZExtValue();
 535     if (BitOffset != StartBitOffset) {
 536       EndBitOffset = BitOffset;
 537       break;
 538     }
 539   }
 540 }
 541
 542 uint32_t BPFAbstractMemberAccess::GetFieldInfo(uint32_t InfoKind,
 543                                                DICompositeType *CTy,
 544                                                uint32_t AccessIndex,
 545                                                uint32_t PatchImm) {
 546   if (InfoKind == BPFCoreSharedInfo::FIELD_EXISTENCE)
 547       return 1;
 548
 549   uint32_t Tag = CTy->getTag();
 550   if (InfoKind == BPFCoreSharedInfo::FIELD_BYTE_OFFSET) {
 551     if (Tag == dwarf::DW_TAG_array_type) {
 552       auto *EltTy = stripQualifiers(CTy->getBaseType());
 553       PatchImm += AccessIndex * calcArraySize(CTy, 1) *
 554                   (EltTy->getSizeInBits() >> 3);
 555     } else if (Tag == dwarf::DW_TAG_structure_type) {
 556       auto *MemberTy = cast<DIDerivedType>(CTy->getElements()[AccessIndex]);
 557       if (!MemberTy->isBitField()) {
 558         PatchImm += MemberTy->getOffsetInBits() >> 3;
 559       } else {
 560         auto SOffset = dyn_cast<ConstantInt>(MemberTy->getStorageOffsetInBits());
 561         assert(SOffset);
 562         PatchImm += SOffset->getZExtValue() >> 3;
 563       }
 564     }
 565     return PatchImm;
 566   }
 567
 568   if (InfoKind == BPFCoreSharedInfo::FIELD_BYTE_SIZE) {
 569     if (Tag == dwarf::DW_TAG_array_type) {
 570       auto *EltTy = stripQualifiers(CTy->getBaseType());
 571       return calcArraySize(CTy, 1) * (EltTy->getSizeInBits() >> 3);
 572     } else {
 573       auto *MemberTy = cast<DIDerivedType>(CTy->getElements()[AccessIndex]);
 574       uint32_t SizeInBits = MemberTy->getSizeInBits();
 575       if (!MemberTy->isBitField())
 576         return SizeInBits >> 3;
 577
 578       unsigned SBitOffset, NextSBitOffset;
 579       GetStorageBitRange(CTy, MemberTy, AccessIndex, SBitOffset, NextSBitOffset);
 580       SizeInBits = NextSBitOffset - SBitOffset;
 581       if (SizeInBits & (SizeInBits - 1))
 582         report_fatal_error("Unsupported field expression for llvm.bpf.preserve.field.info");
 583       return SizeInBits >> 3;
 584     }
 585   }
 586
 587   if (InfoKind == BPFCoreSharedInfo::FIELD_SIGNEDNESS) {
 588     const DIType *BaseTy;
 589     if (Tag == dwarf::DW_TAG_array_type) {
 590       // Signedness only checked when final array elements are accessed.
 591       if (CTy->getElements().size() != 1)
 592         report_fatal_error("Invalid array expression for llvm.bpf.preserve.field.info");
 593       BaseTy = stripQualifiers(CTy->getBaseType());
 594     } else {
 595       auto *MemberTy = cast<DIDerivedType>(CTy->getElements()[AccessIndex]);
 596       BaseTy = stripQualifiers(MemberTy->getBaseType());
 597     }
 598
 599     // Only basic types and enum types have signedness.
 600     const auto *BTy = dyn_cast<DIBasicType>(BaseTy);
 601     while (!BTy) {
 602       const auto *CompTy = dyn_cast<DICompositeType>(BaseTy);
 603       // Report an error if the field expression does not have signedness.
 604       if (!CompTy || CompTy->getTag() != dwarf::DW_TAG_enumeration_type)
 605         report_fatal_error("Invalid field expression for llvm.bpf.preserve.field.info");
 606       BaseTy = stripQualifiers(CompTy->getBaseType());
 607       BTy = dyn_cast<DIBasicType>(BaseTy);
 608     }
 609     uint32_t Encoding = BTy->getEncoding();
 610     return (Encoding == dwarf::DW_ATE_signed || Encoding == dwarf::DW_ATE_signed_char);
 611   }
 612
 613   if (InfoKind == BPFCoreSharedInfo::FIELD_LSHIFT_U64) {
 614     // The value is loaded into a value with FIELD_BYTE_SIZE size,
 615     // and then zero or sign extended to U64.
 616     // FIELD_LSHIFT_U64 and FIELD_RSHIFT_U64 are operations
 617     // to extract the original value.
 618     const Triple &Triple = TM->getTargetTriple();
 619     DIDerivedType *MemberTy = nullptr;
 620     bool IsBitField = false;
 621     uint32_t SizeInBits;
 622
 623     if (Tag == dwarf::DW_TAG_array_type) {
 624       auto *EltTy = stripQualifiers(CTy->getBaseType());
 625       SizeInBits = calcArraySize(CTy, 1) * EltTy->getSizeInBits();
 626     } else {
 627       MemberTy = cast<DIDerivedType>(CTy->getElements()[AccessIndex]);
 628       SizeInBits = MemberTy->getSizeInBits();
 629       IsBitField = MemberTy->isBitField();
 630     }
 631
 632     if (!IsBitField) {
 633       if (SizeInBits > 64)
 634         report_fatal_error("too big field size for llvm.bpf.preserve.field.info");
 635       return 64 - SizeInBits;
 636     }
 637
 638     unsigned SBitOffset, NextSBitOffset;
 639     GetStorageBitRange(CTy, MemberTy, AccessIndex, SBitOffset, NextSBitOffset);
 640     if (NextSBitOffset - SBitOffset > 64)
 641       report_fatal_error("too big field size for llvm.bpf.preserve.field.info");
 642
 643     unsigned OffsetInBits = MemberTy->getOffsetInBits();
 644     if (Triple.getArch() == Triple::bpfel)
 645       return SBitOffset + 64 - OffsetInBits - SizeInBits;
 646     else
 647       return OffsetInBits + 64 - NextSBitOffset;
 648   }
 649
 650   if (InfoKind == BPFCoreSharedInfo::FIELD_RSHIFT_U64) {
 651     DIDerivedType *MemberTy = nullptr;
 652     bool IsBitField = false;
 653     uint32_t SizeInBits;
 654     if (Tag == dwarf::DW_TAG_array_type) {
 655       auto *EltTy = stripQualifiers(CTy->getBaseType());
 656       SizeInBits = calcArraySize(CTy, 1) * EltTy->getSizeInBits();
 657     } else {
 658       MemberTy = cast<DIDerivedType>(CTy->getElements()[AccessIndex]);
 659       SizeInBits = MemberTy->getSizeInBits();
 660       IsBitField = MemberTy->isBitField();
 661     }
 662
 663     if (!IsBitField) {
 664       if (SizeInBits > 64)
 665         report_fatal_error("too big field size for llvm.bpf.preserve.field.info");
 666       return 64 - SizeInBits;
 667     }
 668
 669     unsigned SBitOffset, NextSBitOffset;
 670     GetStorageBitRange(CTy, MemberTy, AccessIndex, SBitOffset, NextSBitOffset);
 671     if (NextSBitOffset - SBitOffset > 64)
 672       report_fatal_error("too big field size for llvm.bpf.preserve.field.info");
 673
 674     return 64 - SizeInBits;
 675   }
 676
 677   llvm_unreachable("Unknown llvm.bpf.preserve.field.info info kind");
 678 }
 679
 680 bool BPFAbstractMemberAccess::HasPreserveFieldInfoCall(CallInfoStack &CallStack) {
 681   // This is called in error return path, no need to maintain CallStack.
 682   while (CallStack.size()) {
 683     auto StackElem = CallStack.top();
 684     if (StackElem.second.Kind == BPFPreserveFieldInfoAI)
 685       return true;
 686     CallStack.pop();
 687   }
 688   return false;
 689 }
 690
 691 /// Compute the base of the whole preserve_* intrinsics chains, i.e., the base
 692 /// pointer of the first preserve_*_access_index call, and construct the access
 693 /// string, which will be the name of a global variable.
 694 Value *BPFAbstractMemberAccess::computeBaseAndAccessKey(CallInst *Call,
 695                                                         CallInfo &CInfo,
 696                                                         std::string &AccessKey,
 697                                                         MDNode *&TypeMeta) {
 698   Value *Base = nullptr;
 699   std::string TypeName;
 700   CallInfoStack CallStack;
 701
 702   // Put the access chain into a stack with the top as the head of the chain.
 703   while (Call) {
 704     CallStack.push(std::make_pair(Call, CInfo));
 705     CInfo = AIChain[Call].second;
 706     Call = AIChain[Call].first;
 707   }
 708
 709   // The access offset from the base of the head of chain is also
 710   // calculated here as all debuginfo types are available.
 711
 712   // Get type name and calculate the first index.
 713   // We only want to get type name from structure or union.
 714   // If user wants a relocation like
 715   //    int *p; ... __builtin_preserve_access_index(&p[4]) ...
 716   // or
 717   //    int a[10][20]; ... __builtin_preserve_access_index(&a[2][3]) ...
 718   // we will skip them.
 719   uint32_t FirstIndex = 0;
 720   uint32_t PatchImm = 0; // AccessOffset or the requested field info
 721   uint32_t InfoKind = BPFCoreSharedInfo::FIELD_BYTE_OFFSET;
 722   while (CallStack.size()) {
 723     auto StackElem = CallStack.top();
 724     Call = StackElem.first;
 725     CInfo = StackElem.second;
 726
 727     if (!Base)
 728       Base = CInfo.Base;
 729
 730     DIType *Ty = stripQualifiers(cast<DIType>(CInfo.Metadata));
 731     if (CInfo.Kind == BPFPreserveUnionAI ||
 732         CInfo.Kind == BPFPreserveStructAI) {
 733       // struct or union type
 734       TypeName = Ty->getName();
 735       TypeMeta = Ty;
 736       PatchImm += FirstIndex * (Ty->getSizeInBits() >> 3);
 737       break;
 738     }
 739
 740     assert(CInfo.Kind == BPFPreserveArrayAI);
 741
 742     // Array entries will always be consumed for accumulative initial index.
 743     CallStack.pop();
 744
 745     // BPFPreserveArrayAI
 746     uint64_t AccessIndex = CInfo.AccessIndex;
 747
 748     DIType *BaseTy = nullptr;
 749     bool CheckElemType = false;
 750     if (const auto *CTy = dyn_cast<DICompositeType>(Ty)) {
 751       // array type
 752       assert(CTy->getTag() == dwarf::DW_TAG_array_type);
 753
 754
 755       FirstIndex += AccessIndex * calcArraySize(CTy, 1);
 756       BaseTy = stripQualifiers(CTy->getBaseType());
 757       CheckElemType = CTy->getElements().size() == 1;
 758     } else {
 759       // pointer type
 760       auto *DTy = cast<DIDerivedType>(Ty);
 761       assert(DTy->getTag() == dwarf::DW_TAG_pointer_type);
 762
 763       BaseTy = stripQualifiers(DTy->getBaseType());
 764       CTy = dyn_cast<DICompositeType>(BaseTy);
 765       if (!CTy) {
 766         CheckElemType = true;
 767       } else if (CTy->getTag() != dwarf::DW_TAG_array_type) {
 768         FirstIndex += AccessIndex;
 769         CheckElemType = true;
 770       } else {
 771         FirstIndex += AccessIndex * calcArraySize(CTy, 0);
 772       }
 773     }
 774
 775     if (CheckElemType) {
 776       auto *CTy = dyn_cast<DICompositeType>(BaseTy);
 777       if (!CTy) {
 778         if (HasPreserveFieldInfoCall(CallStack))
 779           report_fatal_error("Invalid field access for llvm.preserve.field.info intrinsic");
 780         return nullptr;
 781       }
 782
 783       unsigned CTag = CTy->getTag();
 784       if (CTag == dwarf::DW_TAG_structure_type || CTag == dwarf::DW_TAG_union_type) {
 785         TypeName = CTy->getName();
 786       } else {
 787         if (HasPreserveFieldInfoCall(CallStack))
 788           report_fatal_error("Invalid field access for llvm.preserve.field.info intrinsic");
 789         return nullptr;
 790       }
 791       TypeMeta = CTy;
 792       PatchImm += FirstIndex * (CTy->getSizeInBits() >> 3);
 793       break;
 794     }
 795   }
 796   assert(TypeName.size());
 797   AccessKey += std::to_string(FirstIndex);
 798
 799   // Traverse the rest of access chain to complete offset calculation
 800   // and access key construction.
 801   while (CallStack.size()) {
 802     auto StackElem = CallStack.top();
 803     CInfo = StackElem.second;
 804     CallStack.pop();
 805
 806     if (CInfo.Kind == BPFPreserveFieldInfoAI)
 807       break;
 808
 809     // If the next Call (the top of the stack) is a BPFPreserveFieldInfoAI,
 810     // the action will be extracting field info.
 811     if (CallStack.size()) {
 812       auto StackElem2 = CallStack.top();
 813       CallInfo CInfo2 = StackElem2.second;
 814       if (CInfo2.Kind == BPFPreserveFieldInfoAI) {
 815         InfoKind = CInfo2.AccessIndex;
 816         assert(CallStack.size() == 1);
 817       }
 818     }
 819
 820     // Access Index
 821     uint64_t AccessIndex = CInfo.AccessIndex;
 822     AccessKey += ":" + std::to_string(AccessIndex);
 823
 824     MDNode *MDN = CInfo.Metadata;
 825     // At this stage, it cannot be pointer type.
 826     auto *CTy = cast<DICompositeType>(stripQualifiers(cast<DIType>(MDN)));
 827     PatchImm = GetFieldInfo(InfoKind, CTy, AccessIndex, PatchImm);
 828   }
 829
 830   // Access key is the type name + reloc type + patched imm + access string,
 831   // uniquely identifying one relocation.
 832   AccessKey = TypeName + ":" + std::to_string(InfoKind) + ":" +
 833               std::to_string(PatchImm) + "$" + AccessKey;
 834
 835   return Base;
 836 }
 837
 838 /// Call/Kind is the base preserve_*_access_index() call. Attempts to do
 839 /// transformation to a chain of relocable GEPs.
 840 bool BPFAbstractMemberAccess::transformGEPChain(Module &M, CallInst *Call,
 841                                                 CallInfo &CInfo) {
 842   std::string AccessKey;
 843   MDNode *TypeMeta;
 844   Value *Base =
 845       computeBaseAndAccessKey(Call, CInfo, AccessKey, TypeMeta);
 846   if (!Base)
 847     return false;
 848
 849   BasicBlock *BB = Call->getParent();
 850   GlobalVariable *GV;
 851
 852   if (GEPGlobals.find(AccessKey) == GEPGlobals.end()) {
 853     IntegerType *VarType;
 854     if (CInfo.Kind == BPFPreserveFieldInfoAI)
 855       VarType = Type::getInt32Ty(BB->getContext()); // 32bit return value
 856     else
 857       VarType = Type::getInt64Ty(BB->getContext()); // 64bit ptr arith
 858
 859     GV = new GlobalVariable(M, VarType, false, GlobalVariable::ExternalLinkage,
 860                             NULL, AccessKey);
 861     GV->addAttribute(BPFCoreSharedInfo::AmaAttr);
 862     GV->setMetadata(LLVMContext::MD_preserve_access_index, TypeMeta);
 863     GEPGlobals[AccessKey] = GV;
 864   } else {
 865     GV = GEPGlobals[AccessKey];
 866   }
 867
 868   if (CInfo.Kind == BPFPreserveFieldInfoAI) {
 869     // Load the global variable which represents the returned field info.
 870     auto *LDInst = new LoadInst(Type::getInt32Ty(BB->getContext()), GV);
 871     BB->getInstList().insert(Call->getIterator(), LDInst);
 872     Call->replaceAllUsesWith(LDInst);
 873     Call->eraseFromParent();
 874     return true;
 875   }
 876
 877   // For any original GEP Call and Base %2 like
 878   //   %4 = bitcast %struct.net_device** %dev1 to i64*
 879   // it is transformed to:
 880   //   %6 = load sk_buff:50:$0:0:0:2:0
 881   //   %7 = bitcast %struct.sk_buff* %2 to i8*
 882   //   %8 = getelementptr i8, i8* %7, %6
 883   //   %9 = bitcast i8* %8 to i64*
 884   //   using %9 instead of %4
 885   // The original Call inst is removed.
 886
 887   // Load the global variable.
 888   auto *LDInst = new LoadInst(Type::getInt64Ty(BB->getContext()), GV);
 889   BB->getInstList().insert(Call->getIterator(), LDInst);
 890
 891   // Generate a BitCast
 892   auto *BCInst = new BitCastInst(Base, Type::getInt8PtrTy(BB->getContext()));
 893   BB->getInstList().insert(Call->getIterator(), BCInst);
 894
 895   // Generate a GetElementPtr
 896   auto *GEP = GetElementPtrInst::Create(Type::getInt8Ty(BB->getContext()),
 897                                         BCInst, LDInst);
 898   BB->getInstList().insert(Call->getIterator(), GEP);
 899
 900   // Generate a BitCast
 901   auto *BCInst2 = new BitCastInst(GEP, Call->getType());
 902   BB->getInstList().insert(Call->getIterator(), BCInst2);
 903
 904   Call->replaceAllUsesWith(BCInst2);
 905   Call->eraseFromParent();
 906
 907   return true;
 908 }
 909
 910 bool BPFAbstractMemberAccess::doTransformation(Module &M) {
 911   bool Transformed = false;
 912
 913   for (Function &F : M) {
 914     // Collect PreserveDIAccessIndex Intrinsic call chains.
 915     // The call chains will be used to generate the access
 916     // patterns similar to GEP.
 917     collectAICallChains(M, F);
 918
 919     for (auto &C : BaseAICalls)
 920       Transformed = transformGEPChain(M, C.first, C.second) || Transformed;
 921   }
 922
 923   return removePreserveAccessIndexIntrinsic(M) || Transformed;
 924 }