LLVM  10.0.0svn
BPFAbstractMemberAccess.cpp
Go to the documentation of this file.
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"
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"
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 
171 INITIALIZE_PASS(BPFAbstractMemberAccess, DEBUG_TYPE,
172  "abstracting struct/union member accessees", false, false)
173 
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 
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));
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 =
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 
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
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
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 }
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:67
uint64_t getOffsetInBits() const
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1571
INITIALIZE_PASS(BPFAbstractMemberAccess, DEBUG_TYPE, "abstracting struct/union member accessees", false, false) ModulePass *llvm
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:909
This class represents a function call, abstracting a target machine&#39;s calling convention.
static bool SkipDIDerivedTag(unsigned Tag)
Externally visible function.
Definition: GlobalValue.h:48
Metadata node.
Definition: Metadata.h:863
F(f)
An instruction for reading from memory.
Definition: Instructions.h:169
static IntegerType * getInt64Ty(LLVMContext &C)
Definition: Type.cpp:181
Hexagon Common GEP
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:32
StringRef getName() const
DINodeArray getElements() const
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1241
unsigned getTag() const
Array subrange.
uint64_t getSizeInBits() const
static DIType * stripQualifiers(DIType *Ty)
#define DEBUG_TYPE
DIType * getBaseType() const
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
ArchType getArch() const
getArch - Get the parsed architecture type of this triple.
Definition: Triple.h:296
static uint32_t calcArraySize(const DICompositeType *CTy, uint32_t StartDim)
This class represents a no-op cast from one type to another.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:244
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:137
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:883
ModulePass * createBPFAbstractMemberAccess(BPFTargetMachine *TM)
Value * getCalledValue() const
Definition: InstrTypes.h:1280
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
This is an important base class in LLVM.
Definition: Constant.h:41
CountType getCount() const
constexpr char TypeName[]
Key for Kernel::Arg::Metadata::mTypeName.
self_iterator getIterator()
Definition: ilist_node.h:81
Class to represent integer types.
Definition: DerivedTypes.h:40
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:224
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Triple - Helper class for working with autoconf configuration names.
Definition: Triple.h:43
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:338
Base class for types.
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:653
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
iterator_range< user_iterator > users()
Definition: Value.h:420
iterator insert(iterator where, pointer New)
Definition: ilist.h:226
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:180
#define I(x, y, z)
Definition: MD5.cpp:58
iterator_range< debug_compile_units_iterator > debug_compile_units() const
Return an iterator for all DICompileUnits listed in this Module&#39;s llvm.dbg.cu named metadata node and...
Definition: Module.h:781
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:224
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
static const std::string AmaAttr
The attribute attached to globals representing a field access.
Definition: BPFCORE.h:27
const std::string to_string(const T &Value)
Definition: ScopedPrinter.h:61
static GetElementPtrInst * CreateInBounds(Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Create an "inbounds" getelementptr.
Definition: Instructions.h:943
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:74
bool isBitField() const
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:65
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
#define LLVM_DEBUG(X)
Definition: Debug.h:122
Root of the metadata hierarchy.
Definition: Metadata.h:57
static IntegerType * getInt8Ty(LLVMContext &C)
Definition: Type.cpp:178
const BasicBlock * getParent() const
Definition: Instruction.h:66
Basic type, like &#39;int&#39; or &#39;float&#39;.