[esan|cfrag] Instrument GEP instr for struct field access.

[zhaoqin]

Summary

Instrument GEP instruction for counting the number of struct field
address calculation to approximate the number of struct field accesses.

Adds test struct_field_count_basic.ll to test the struct field
instrumentation.

[zhaoqin]

Rebase to ToT and resolve conflicts

[aizatsky]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

331

Will this grow and grow in huge lto programs? Is this a concern?

615

It is not clear to me why this map would contain this source element type at all. Wouldn't this work only for structs defined in the same module?

618

Do you need counters for how many accesses were skipped?

[zhaoqin]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

331

This StructTyMap should be fairly small esp if separate compilation.

If there is any concern, that would be that we have one struct counter array for each struct type and we rely on the linker to merge them based on their name, xref createStructCounterName.
Another concern is the runtime hash map for holding each struct type counter.
I would expect the total number of different struct/class types won't be an insane number.

615

I assume that StructTyMap would have that type (i.e, struct type is in M.getIdentifiedStructTypes()) if the GEP instr knows how to calculate the field offset within the struct.

618

add NumIgnoredGEPs and NumInstrumentedGEPs.

[zhaoqin]

Add NumIgnoredGEPs and NumInstrumentedGEPs.

[aizatsky]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

615

Ack. getIdentifiedStructTypes uses TypeFinder and walks over the tree.

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

static cl::opt<bool> ClInstrumentMemIntrinsics(
     cl::desc("Instrument memintrinsics (memset/memcpy/memmove)"), cl::Hidden);
 
 STATISTIC(NumInstrumentedLoads, "Number of instrumented loads");
 STATISTIC(NumInstrumentedStores, "Number of instrumented stores");
 STATISTIC(NumFastpaths, "Number of instrumented fastpaths");
 STATISTIC(NumAccessesWithIrregularSize,
           "Number of accesses with a size outside our targeted callout sizes");
 STATISTIC(NumIgnoredStructs, "Number of ignored structs");
+STATISTIC(NumIgnoredGEPs, "Number of ignored GEP instructions");
+STATISTIC(NumInstrumentedGEPs, "Number of instrumented GEP instructions");
 
 static const uint64_t EsanCtorAndDtorPriority = 0;
 static const char *const EsanModuleCtorName = "esan.module_ctor";
 static const char *const EsanModuleDtorName = "esan.module_dtor";
 static const char *const EsanInitName = "__esan_init";
 static const char *const EsanExitName = "__esan_exit";
 
 // We must keep these Shadow* constants consistent with the esan runtime.
private:
   void createStructCounterName(
       StructType *StructTy, SmallString<MaxStructCounterNameSize> &NameStr);
   GlobalVariable *createCacheFragInfoGV(Module &M, Constant *UnitName);
   Constant *createEsanInitToolInfoArg(Module &M);
   void createDestructor(Module &M, Constant *ToolInfoArg);
   bool runOnFunction(Function &F, Module &M);
   bool instrumentLoadOrStore(Instruction *I, const DataLayout &DL);
   bool instrumentMemIntrinsic(MemIntrinsic *MI);
+  bool instrumentGetElementPtr(Instruction *I, Module &M);
   bool shouldIgnoreMemoryAccess(Instruction *I);
   int getMemoryAccessFuncIndex(Value *Addr, const DataLayout &DL);
   Value *appToShadow(Value *Shadow, IRBuilder<> &IRB);
   bool instrumentFastpath(Instruction *I, const DataLayout &DL, bool IsStore,
                           Value *Addr, unsigned Alignment);
   // Each tool has its own fastpath routine:
   bool instrumentFastpathCacheFrag(Instruction *I, const DataLayout &DL,
                                    Value *Addr, unsigned Alignment);
private:
   Function *EsanAlignedStore[NumberOfAccessSizes];
   Function *EsanUnalignedLoad[NumberOfAccessSizes];
   Function *EsanUnalignedStore[NumberOfAccessSizes];
   // For irregular sizes of any alignment:
   Function *EsanUnalignedLoadN, *EsanUnalignedStoreN;
   Function *MemmoveFn, *MemcpyFn, *MemsetFn;
   Function *EsanCtorFunction;
   Function *EsanDtorFunction;
+  // Remember the counter variable for each struct type to avoid
+  // recomputing the variable name later during instrumentation.
+  std::map<Type *, GlobalVariable *> StructTyMap;
 };
 } // namespace
 
 char EfficiencySanitizer::ID = 0;
 INITIALIZE_PASS(EfficiencySanitizer, "esan",
                 "EfficiencySanitizer: finds performance issues.", false, false)
 
 const char *EfficiencySanitizer::getPassName() const {
for (auto &StructTy : Vec) {
     // compilation units will be merged into one.
     auto *CounterArrayTy = ArrayType::get(Int64Ty, StructTy->getNumElements());
     GlobalVariable *Counters =
       new GlobalVariable(M, CounterArrayTy, false,
                          GlobalVariable::WeakAnyLinkage,
                          ConstantAggregateZero::get(CounterArrayTy),
                          CounterNameStr);
 
+    // Remember the counter variable for each struct type.
+    StructTyMap.insert(std::pair<Type *, GlobalVariable *>(StructTy, Counters));
+
     // FieldTypeNames.
     // We pass the field type name array to the runtime for better reporting.
     auto *TypeNameArrayTy = ArrayType::get(Int8PtrTy, StructTy->getNumElements());
     GlobalVariable *TypeName =
       new GlobalVariable(M, TypeNameArrayTy, true,
                          GlobalVariable::InternalLinkage, nullptr);
     SmallVector<Constant *, 16> TypeNameVec;
     for (unsigned i = 0; i < StructTy->getNumElements(); ++i) {

 
 bool EfficiencySanitizer::runOnFunction(Function &F, Module &M) {
   // This is required to prevent instrumenting the call to __esan_init from
   // within the module constructor.
   if (&F == EsanCtorFunction)
     return false;
   SmallVector<Instruction *, 8> LoadsAndStores;
   SmallVector<Instruction *, 8> MemIntrinCalls;
+  SmallVector<Instruction *, 8> GetElementPtrs;
   bool Res = false;
   const DataLayout &DL = M.getDataLayout();
 
   for (auto &BB : F) {
     for (auto &Inst : BB) {
       if ((isa<LoadInst>(Inst) || isa<StoreInst>(Inst) ||
            isa<AtomicRMWInst>(Inst) || isa<AtomicCmpXchgInst>(Inst)) &&
           !shouldIgnoreMemoryAccess(&Inst))
         LoadsAndStores.push_back(&Inst);
       else if (isa<MemIntrinsic>(Inst))
         MemIntrinCalls.push_back(&Inst);
+      else if (isa<GetElementPtrInst>(Inst))
+        GetElementPtrs.push_back(&Inst);
     }
   }
 
   if (ClInstrumentLoadsAndStores) {
     for (auto Inst : LoadsAndStores) {
       Res |= instrumentLoadOrStore(Inst, DL);
     }
   }
 
   if (ClInstrumentMemIntrinsics) {
     for (auto Inst : MemIntrinCalls) {
       Res |= instrumentMemIntrinsic(cast<MemIntrinsic>(Inst));
     }
   }
 
+  if (Options.ToolType == EfficiencySanitizerOptions::ESAN_CacheFrag) {
+    for (auto Inst : GetElementPtrs) {
+      Res |= instrumentGetElementPtr(Inst, M);
+    }
+  }
+
   return Res;
 }
 
 bool EfficiencySanitizer::instrumentLoadOrStore(Instruction *I,
                                                 const DataLayout &DL) {
   IRBuilder<> IRB(I);
   bool IsStore;
   Value *Addr;
IRB.CreateCall(
          IRB.CreateIntCast(MI->getArgOperand(2), IntptrTy, false)});
     MI->eraseFromParent();
     Res = true;
   } else
     llvm_unreachable("Unsupported mem intrinsic type");
   return Res;
 }
 
+bool EfficiencySanitizer::instrumentGetElementPtr(Instruction *I, Module &M) {
+  GetElementPtrInst *GepInst = dyn_cast<GetElementPtrInst>(I);
+  if (GepInst == nullptr || !isa<StructType>(GepInst->getSourceElementType()) ||
+      StructTyMap.count(GepInst->getSourceElementType()) == 0 ||
+      !GepInst->hasAllConstantIndices() ||
+      // Only handle simple struct field GEP.
+      GepInst->getNumIndices() != 2) {
+    ++NumIgnoredGEPs;
+    return false;
+  }
+  StructType *StructTy = dyn_cast<StructType>(GepInst->getSourceElementType());
+  if (shouldIgnoreStructType(StructTy)) {
+    ++NumIgnoredGEPs;
+    return false;
+  }
+  ++NumInstrumentedGEPs;
+  // Use the last index as the index within the struct.
+  ConstantInt *Idx = dyn_cast<ConstantInt>(GepInst->getOperand(2));
+  if (Idx == nullptr || Idx->getZExtValue() > StructTy->getNumElements())
+    return false;
+
+  GlobalVariable *CounterArray = StructTyMap[StructTy];
+  if (CounterArray == nullptr)
+    return false;
+  IRBuilder<> IRB(I);
+  Constant *Indices[2];
+  // Xref http://llvm.org/docs/LangRef.html#i-getelementptr and
+  // http://llvm.org/docs/GetElementPtr.html.
+  // The first index of the GEP instruction steps through the first operand,
+  // i.e., the array itself.
+  Indices[0] = ConstantInt::get(IRB.getInt32Ty(), 0);
+  // The second index is the index within the array.
+  Indices[1] = ConstantInt::get(IRB.getInt32Ty(), Idx->getZExtValue());
+  Constant *Counter =
+      ConstantExpr::getGetElementPtr(ArrayType::get(IRB.getInt64Ty(),
+                                                    StructTy->getNumElements()),
+                                     CounterArray, Indices);
+  Value *Load = IRB.CreateLoad(Counter);
+  IRB.CreateStore(IRB.CreateAdd(Load, ConstantInt::get(IRB.getInt64Ty(), 1)),
+                  Counter);
+  return true;
+}
+
 int EfficiencySanitizer::getMemoryAccessFuncIndex(Value *Addr,
                                                   const DataLayout &DL) {
   Type *OrigPtrTy = Addr->getType();
   Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType();
   assert(OrigTy->isSized());
   // The size is always a multiple of 8.
   uint32_t TypeSizeBytes = DL.getTypeStoreSizeInBits(OrigTy) / 8;
   if (TypeSizeBytes != 1 && TypeSizeBytes != 2 && TypeSizeBytes != 4 &&

test/Instrumentation/EfficiencySanitizer/struct_field_count_basic.ll

+; Test basic EfficiencySanitizer struct field count instrumentation.
+;
+; RUN: opt < %s -esan -esan-cache-frag -esan-instrument-loads-and-stores=false -esan-instrument-memintrinsics=false -S | FileCheck %s
+
+%struct.A = type { i32, i32 }
+%union.U = type { double }
+%struct.C = type { %struct.anon, %union.anon, [10 x i8] }
+%struct.anon = type { i32, i32 }
+%union.anon = type { double }
+
+define i32 @main() {
+entry:
+  %a = alloca %struct.A, align 4
+  %u = alloca %union.U, align 8
+  %c = alloca [2 x %struct.C], align 16
+  %k = alloca %struct.A*, align 8
+  %x = getelementptr inbounds %struct.A, %struct.A* %a, i32 0, i32 0
+  %y = getelementptr inbounds %struct.A, %struct.A* %a, i32 0, i32 1
+  %f = bitcast %union.U* %u to float*
+  %d = bitcast %union.U* %u to double*
+  %arrayidx = getelementptr inbounds [2 x %struct.C], [2 x %struct.C]* %c, i64 0, i64 0
+  %cs = getelementptr inbounds %struct.C, %struct.C* %arrayidx, i32 0, i32 0
+  %x1 = getelementptr inbounds %struct.anon, %struct.anon* %cs, i32 0, i32 0
+  %arrayidx2 = getelementptr inbounds [2 x %struct.C], [2 x %struct.C]* %c, i64 0, i64 1
+  %cs3 = getelementptr inbounds %struct.C, %struct.C* %arrayidx2, i32 0, i32 0
+  %y4 = getelementptr inbounds %struct.anon, %struct.anon* %cs3, i32 0, i32 1
+  %arrayidx5 = getelementptr inbounds [2 x %struct.C], [2 x %struct.C]* %c, i64 0, i64 0
+  %cu = getelementptr inbounds %struct.C, %struct.C* %arrayidx5, i32 0, i32 1
+  %f6 = bitcast %union.anon* %cu to float*
+  %arrayidx7 = getelementptr inbounds [2 x %struct.C], [2 x %struct.C]* %c, i64 0, i64 1
+  %cu8 = getelementptr inbounds %struct.C, %struct.C* %arrayidx7, i32 0, i32 1
+  %d9 = bitcast %union.anon* %cu8 to double*
+  %arrayidx10 = getelementptr inbounds [2 x %struct.C], [2 x %struct.C]* %c, i64 0, i64 0
+  %c11 = getelementptr inbounds %struct.C, %struct.C* %arrayidx10, i32 0, i32 2
+  %arrayidx12 = getelementptr inbounds [10 x i8], [10 x i8]* %c11, i64 0, i64 2
+  %k1 = load %struct.A*, %struct.A** %k, align 8
+  %arrayidx13 = getelementptr inbounds %struct.A, %struct.A* %k1, i64 0
+  ret i32 0
+}
+
+; CHECK: @llvm.global_ctors = {{.*}}@esan.module_ctor
+
+; CHECK:        %a = alloca %struct.A, align 4
+; CHECK-NEXT:   %u = alloca %union.U, align 8
+; CHECK-NEXT:   %c = alloca [2 x %struct.C], align 16
+; CHECK-NEXT:   %k = alloca %struct.A*, align 8
+; CHECK-NEXT:   %0 = load i64, i64* getelementptr inbounds ([2 x i64], [2 x i64]* @"struct.A#2#11#11", i32 0, i32 0)
+; CHECK-NEXT:   %1 = add i64 %0, 1
+; CHECK-NEXT:   store i64 %1, i64* getelementptr inbounds ([2 x i64], [2 x i64]* @"struct.A#2#11#11", i32 0, i32 0)
+; CHECK-NEXT:   %x = getelementptr inbounds %struct.A, %struct.A* %a, i32 0, i32 0
+; CHECK-NEXT:   %2 = load i64, i64* getelementptr inbounds ([2 x i64], [2 x i64]* @"struct.A#2#11#11", i32 0, i32 1)
+; CHECK-NEXT:   %3 = add i64 %2, 1
+; CHECK-NEXT:   store i64 %3, i64* getelementptr inbounds ([2 x i64], [2 x i64]* @"struct.A#2#11#11", i32 0, i32 1)
+; CHECK-NEXT:   %y = getelementptr inbounds %struct.A, %struct.A* %a, i32 0, i32 1
+; CHECK-NEXT:   %f = bitcast %union.U* %u to float*
+; CHECK-NEXT:   %d = bitcast %union.U* %u to double*
+; CHECK-NEXT:   %arrayidx = getelementptr inbounds [2 x %struct.C], [2 x %struct.C]* %c, i64 0, i64 0
+; CHECK-NEXT:   %4 = load i64, i64* getelementptr inbounds ([3 x i64], [3 x i64]* @"struct.C#3#14#13#13", i32 0, i32 0)
+; CHECK-NEXT:   %5 = add i64 %4, 1
+; CHECK-NEXT:   store i64 %5, i64* getelementptr inbounds ([3 x i64], [3 x i64]* @"struct.C#3#14#13#13", i32 0, i32 0)
+; CHECK-NEXT:   %cs = getelementptr inbounds %struct.C, %struct.C* %arrayidx, i32 0, i32 0
+; CHECK-NEXT:   %6 = load i64, i64* getelementptr inbounds ([2 x i64], [2 x i64]* @"struct.anon#2#11#11", i32 0, i32 0)
+; CHECK-NEXT:   %7 = add i64 %6, 1
+; CHECK-NEXT:   store i64 %7, i64* getelementptr inbounds ([2 x i64], [2 x i64]* @"struct.anon#2#11#11", i32 0, i32 0)
+; CHECK-NEXT:   %x1 = getelementptr inbounds %struct.anon, %struct.anon* %cs, i32 0, i32 0
+; CHECK-NEXT:   %arrayidx2 = getelementptr inbounds [2 x %struct.C], [2 x %struct.C]* %c, i64 0, i64 1
+; CHECK-NEXT:   %8 = load i64, i64* getelementptr inbounds ([3 x i64], [3 x i64]* @"struct.C#3#14#13#13", i32 0, i32 0)
+; CHECK-NEXT:   %9 = add i64 %8, 1
+; CHECK-NEXT:   store i64 %9, i64* getelementptr inbounds ([3 x i64], [3 x i64]* @"struct.C#3#14#13#13", i32 0, i32 0)
+; CHECK-NEXT:   %cs3 = getelementptr inbounds %struct.C, %struct.C* %arrayidx2, i32 0, i32 0
+; CHECK-NEXT:   %10 = load i64, i64* getelementptr inbounds ([2 x i64], [2 x i64]* @"struct.anon#2#11#11", i32 0, i32 1)
+; CHECK-NEXT:   %11 = add i64 %10, 1
+; CHECK-NEXT:   store i64 %11, i64* getelementptr inbounds ([2 x i64], [2 x i64]* @"struct.anon#2#11#11", i32 0, i32 1)
+; CHECK-NEXT:   %y4 = getelementptr inbounds %struct.anon, %struct.anon* %cs3, i32 0, i32 1
+; CHECK-NEXT:   %arrayidx5 = getelementptr inbounds [2 x %struct.C], [2 x %struct.C]* %c, i64 0, i64 0
+; CHECK-NEXT:   %12 = load i64, i64* getelementptr inbounds ([3 x i64], [3 x i64]* @"struct.C#3#14#13#13", i32 0, i32 1)
+; CHECK-NEXT:   %13 = add i64 %12, 1
+; CHECK-NEXT:   store i64 %13, i64* getelementptr inbounds ([3 x i64], [3 x i64]* @"struct.C#3#14#13#13", i32 0, i32 1)
+; CHECK-NEXT:   %cu = getelementptr inbounds %struct.C, %struct.C* %arrayidx5, i32 0, i32 1
+; CHECK-NEXT:   %f6 = bitcast %union.anon* %cu to float*
+; CHECK-NEXT:   %arrayidx7 = getelementptr inbounds [2 x %struct.C], [2 x %struct.C]* %c, i64 0, i64 1
+; CHECK-NEXT:   %14 = load i64, i64* getelementptr inbounds ([3 x i64], [3 x i64]* @"struct.C#3#14#13#13", i32 0, i32 1)
+; CHECK-NEXT:   %15 = add i64 %14, 1
+; CHECK-NEXT:   store i64 %15, i64* getelementptr inbounds ([3 x i64], [3 x i64]* @"struct.C#3#14#13#13", i32 0, i32 1)
+; CHECK-NEXT:   %cu8 = getelementptr inbounds %struct.C, %struct.C* %arrayidx7, i32 0, i32 1
+; CHECK-NEXT:   %d9 = bitcast %union.anon* %cu8 to double*
+; CHECK-NEXT:   %arrayidx10 = getelementptr inbounds [2 x %struct.C], [2 x %struct.C]* %c, i64 0, i64 0
+; CHECK-NEXT:   %16 = load i64, i64* getelementptr inbounds ([3 x i64], [3 x i64]* @"struct.C#3#14#13#13", i32 0, i32 2)
+; CHECK-NEXT:   %17 = add i64 %16, 1
+; CHECK-NEXT:   store i64 %17, i64* getelementptr inbounds ([3 x i64], [3 x i64]* @"struct.C#3#14#13#13", i32 0, i32 2)
+; CHECK-NEXT:   %c11 = getelementptr inbounds %struct.C, %struct.C* %arrayidx10, i32 0, i32 2
+; CHECK-NEXT:   %arrayidx12 = getelementptr inbounds [10 x i8], [10 x i8]* %c11, i64 0, i64 2
+; CHECK-NEXT:   %k1 = load %struct.A*, %struct.A** %k, align 8
+; CHECK-NEXT:   %arrayidx13 = getelementptr inbounds %struct.A, %struct.A* %k1, i64 0
+; CHECK-NEXT:   ret i32 0