Home | History | Annotate | Download | only in esan 
      1 //===-- cache_frag.cpp ----------------------------------------------------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file is a part of EfficiencySanitizer, a family of performance tuners.
     11 //
     12 // This file contains cache fragmentation-specific code.
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "esan.h"
     16 #include "esan_flags.h"
     17 #include "sanitizer_common/sanitizer_addrhashmap.h"
     18 #include "sanitizer_common/sanitizer_common.h"
     19 #include "sanitizer_common/sanitizer_placement_new.h"
     20 #include <string.h>
     21 
     22 namespace __esan {
     23 
     24 //===-- Struct field access counter runtime -------------------------------===//
     25 
     26 // This should be kept consistent with LLVM's EfficiencySanitizer StructInfo.
     27 struct StructInfo {
     28   const char *StructName;
     29   u32 Size;
     30   u32 NumFields;
     31   u32 *FieldOffset;           // auxiliary struct field info.
     32   u32 *FieldSize;             // auxiliary struct field info.
     33   const char **FieldTypeName; // auxiliary struct field info.
     34   u64 *FieldCounters;
     35   u64 *ArrayCounter;
     36   bool hasAuxFieldInfo() { return FieldOffset != nullptr; }
     37 };
     38 
     39 // This should be kept consistent with LLVM's EfficiencySanitizer CacheFragInfo.
     40 // The tool-specific information per compilation unit (module).
     41 struct CacheFragInfo {
     42   const char *UnitName;
     43   u32 NumStructs;
     44   StructInfo *Structs;
     45 };
     46 
     47 struct StructCounter {
     48   StructInfo *Struct;
     49   u64 Count; // The total access count of the struct.
     50   u64 Ratio; // Difference ratio for the struct layout access.
     51 };
     52 
     53 // We use StructHashMap to keep track of an unique copy of StructCounter.
     54 typedef AddrHashMap<StructCounter, 31051> StructHashMap;
     55 struct Context {
     56   StructHashMap StructMap;
     57   u32 NumStructs;
     58   u64 TotalCount; // The total access count of all structs.
     59 };
     60 static Context *Ctx;
     61 
     62 static void reportStructSummary() {
     63   // FIXME: provide a better struct field access summary report.
     64   Report("%s: total struct field access count = %llu\n", SanitizerToolName,
     65          Ctx->TotalCount);
     66 }
     67 
     68 // FIXME: we are still exploring proper ways to evaluate the difference between
     69 // struct field counts.  Currently, we use a simple formula to calculate the
     70 // difference ratio: V1/V2.
     71 static inline u64 computeDifferenceRatio(u64 Val1, u64 Val2) {
     72   if (Val2 > Val1) {
     73     Swap(Val1, Val2);
     74   }
     75   if (Val2 == 0)
     76     Val2 = 1;
     77   return (Val1 / Val2);
     78 }
     79 
     80 static void reportStructCounter(StructHashMap::Handle &Handle) {
     81   const u32 TypePrintLimit = 512;
     82   const char *type, *start, *end;
     83   StructInfo *Struct = Handle->Struct;
     84   // Union field address calculation is done via bitcast instead of GEP,
     85   // so the count for union is always 0.
     86   // We skip the union report to avoid confusion.
     87   if (strncmp(Struct->StructName, "union.", 6) == 0)
     88     return;
     89   // Remove the '.' after class/struct during print.
     90   if (strncmp(Struct->StructName, "class.", 6) == 0) {
     91     type = "class";
     92     start = &Struct->StructName[6];
     93   } else {
     94     type = "struct";
     95     start = &Struct->StructName[7];
     96   }
     97   // Remove the suffixes with '#' during print.
     98   end = strchr(start, '#');
     99   CHECK(end != nullptr);
    100   Report("  %s %.*s\n", type, end - start, start);
    101   Report("   size = %u, count = %llu, ratio = %llu, array access = %llu\n",
    102          Struct->Size, Handle->Count, Handle->Ratio, *Struct->ArrayCounter);
    103   if (Struct->hasAuxFieldInfo()) {
    104     for (u32 i = 0; i < Struct->NumFields; ++i) {
    105       Report("   #%2u: offset = %u,\t size = %u,"
    106              "\t count = %llu,\t type = %.*s\n",
    107              i, Struct->FieldOffset[i], Struct->FieldSize[i],
    108              Struct->FieldCounters[i], TypePrintLimit, Struct->FieldTypeName[i]);
    109     }
    110   } else {
    111     for (u32 i = 0; i < Struct->NumFields; ++i) {
    112       Report("   #%2u: count = %llu\n", i, Struct->FieldCounters[i]);
    113     }
    114   }
    115 }
    116 
    117 static void computeStructRatio(StructHashMap::Handle &Handle) {
    118   Handle->Ratio = 0;
    119   Handle->Count = Handle->Struct->FieldCounters[0];
    120   for (u32 i = 1; i < Handle->Struct->NumFields; ++i) {
    121     Handle->Count += Handle->Struct->FieldCounters[i];
    122     Handle->Ratio += computeDifferenceRatio(
    123         Handle->Struct->FieldCounters[i - 1], Handle->Struct->FieldCounters[i]);
    124   }
    125   Ctx->TotalCount += Handle->Count;
    126   if (Handle->Ratio >= (u64)getFlags()->report_threshold ||
    127       (Verbosity() >= 1 && Handle->Count > 0))
    128     reportStructCounter(Handle);
    129 }
    130 
    131 static void registerStructInfo(CacheFragInfo *CacheFrag) {
    132   for (u32 i = 0; i < CacheFrag->NumStructs; ++i) {
    133     StructInfo *Struct = &CacheFrag->Structs[i];
    134     StructHashMap::Handle H(&Ctx->StructMap, (uptr)Struct->FieldCounters);
    135     if (H.created()) {
    136       VPrintf(2, " Register %s: %u fields\n", Struct->StructName,
    137               Struct->NumFields);
    138       H->Struct = Struct;
    139       ++Ctx->NumStructs;
    140     } else {
    141       VPrintf(2, " Duplicated %s: %u fields\n", Struct->StructName,
    142               Struct->NumFields);
    143     }
    144   }
    145 }
    146 
    147 static void unregisterStructInfo(CacheFragInfo *CacheFrag) {
    148   // FIXME: if the library is unloaded before finalizeCacheFrag, we should
    149   // collect the result for later report.
    150   for (u32 i = 0; i < CacheFrag->NumStructs; ++i) {
    151     StructInfo *Struct = &CacheFrag->Structs[i];
    152     StructHashMap::Handle H(&Ctx->StructMap, (uptr)Struct->FieldCounters, true);
    153     if (H.exists()) {
    154       VPrintf(2, " Unregister %s: %u fields\n", Struct->StructName,
    155               Struct->NumFields);
    156       // FIXME: we should move this call to finalizeCacheFrag once we can
    157       // iterate over the hash map there.
    158       computeStructRatio(H);
    159       --Ctx->NumStructs;
    160     } else {
    161       VPrintf(2, " Duplicated %s: %u fields\n", Struct->StructName,
    162               Struct->NumFields);
    163     }
    164   }
    165   static bool Reported = false;
    166   if (Ctx->NumStructs == 0 && !Reported) {
    167     Reported = true;
    168     reportStructSummary();
    169   }
    170 }
    171 
    172 //===-- Init/exit functions -----------------------------------------------===//
    173 
    174 void processCacheFragCompilationUnitInit(void *Ptr) {
    175   CacheFragInfo *CacheFrag = (CacheFragInfo *)Ptr;
    176   VPrintf(2, "in esan::%s: %s with %u class(es)/struct(s)\n", __FUNCTION__,
    177           CacheFrag->UnitName, CacheFrag->NumStructs);
    178   registerStructInfo(CacheFrag);
    179 }
    180 
    181 void processCacheFragCompilationUnitExit(void *Ptr) {
    182   CacheFragInfo *CacheFrag = (CacheFragInfo *)Ptr;
    183   VPrintf(2, "in esan::%s: %s with %u class(es)/struct(s)\n", __FUNCTION__,
    184           CacheFrag->UnitName, CacheFrag->NumStructs);
    185   unregisterStructInfo(CacheFrag);
    186 }
    187 
    188 void initializeCacheFrag() {
    189   VPrintf(2, "in esan::%s\n", __FUNCTION__);
    190   // We use placement new to initialize Ctx before C++ static initializaion.
    191   // We make CtxMem 8-byte aligned for atomic operations in AddrHashMap.
    192   static u64 CtxMem[sizeof(Context) / sizeof(u64) + 1];
    193   Ctx = new (CtxMem) Context();
    194   Ctx->NumStructs = 0;
    195 }
    196 
    197 int finalizeCacheFrag() {
    198   VPrintf(2, "in esan::%s\n", __FUNCTION__);
    199   return 0;
    200 }
    201 
    202 void reportCacheFrag() {
    203   VPrintf(2, "in esan::%s\n", __FUNCTION__);
    204   // FIXME: Not yet implemented.  We need to iterate over all of the
    205   // compilation unit data.
    206 }
    207 
    208 } // namespace __esan
    209