[esan] EfficiencySanitizer instrumentation pass

[bruening]

Summary

Adds an instrumentation pass for the new EfficiencySanitizer ("esan")
performance tuning family of tools. Multiple tools will be supported
within the same framework. Preliminary support for a cache fragmentation
tool is included here.

The shared instrumentation includes:
+ Turn mem{set,cpy,move} instrinsics into library calls.
+ Slowpath instrumentation of loads and stores via callouts to

the runtime library.

+ Fastpath instrumentation will be per-tool.
+ Which memory accesses to ignore will be per-tool.

[aizatsky]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

21

wrong import order. Please run clang-tidy & clang-format on the file.

48

do you imagine these used for other esan sanitizers as well? Maybe esan-cache-frag-*?

59

this don't follow llvm naming convention.

64

Why do you need this at all, rather than using Options directly?

156

why not __esan_memmove?

167

Ctx

182

this function always returns false.

196

Is it necessary to call it for each function? There could be quite a lot of them.

289

maybe have 3 cases here? Will be more future-proof.

294

llvm_unreachable?

295

return true?

test/Instrumentation/EfficiencySanitizer/cache_frag_basic.ll

52

please add unaligned read & odd size tests.

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

21

Will do. Note that AddressSanitizer.cpp, MemorySanitizer, ThreadSanitizer.cpp, etc. on which this file is based all have this same (incorrect) order.

48

Yes, most of the esan tools instrument all memory references and these options will apply to all of them.

59

Please clarify: the kEsanModuleCtorName, or the esan.module.ctor? Both are matching what the other sanitizers use. Neither matches the official LLVM guide, though lower-case k seems to be used enough it feels like an informal convention, and the runtime interface routines seem to all be C-style to match the extern C interface.

64

There are two methods of invocation: from the clang front-end where -fsanitize=efficiency-foo will become EfficiencySanitizerOptions::ESAN_Foo, or when opt is directly invoked and -esan-foo wlil become ClToolFoo. One needs to be converted to the other. If you have a solution that is simpler, please elaborate on what you mean?

156

That would be more consistent. This current code is modeled after what ThreadSanitizer.cpp and AddressSanitizer.cpp do: they have xsan_* for the others but just "mem*" for the intrinsics. I am happy to add esan_.

167

You're saying current LLVM code prefers "Ctx" as an abbrevation for Context over "Cxt"? OK, sure.

182

Yes, but not in a future CL. We have built some prototypes and some return true for some cases here. We are trying to submit in small pieces for easier reviews. I will add a comment explaining that this will not always be a nop.

196

Hmm, this is modeled after what AddressSanitizer.cpp and ThreadSanitizer.cpp do. They are all function passes, so I believe they do need to re-acquire these functions every time and can't store them in a simple manner. Are you proposing changing them all (esan, asan, tsan, maybe others) to be module passes? How about tackling that in a separate CL?

289

Sure. Again, this was shamelessly modeled after the tsan and asan code.

294

OK.

295

Agreed, this is modifying the function. It seems to be a bug in ThreadSanitizer.cpp as well.

test/Instrumentation/EfficiencySanitizer/cache_frag_basic.ll

52

WIll do.

[silvas]

Is there an RFC for this or something? I'm having a hard time figuring out exactly what it is trying to accomplish or what the ultimate "performance tuning family of tools" is going to be.

I mean, I think it is interesting, but I think llvm-dev would like to see the big picture first.

Is the mem*/str* instrumentation for a shadow-based version of http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40679.pdf ?

[pcc]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

21

No, see http://llvm.org/docs/CodingStandards.html#a-public-header-file-is-a-module third paragraph.

[aizatsky]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

21

Those files do not conform to LLVM coding style right now, but we'd like them to. There's no reason why new code shouldn't.

59

kEsanModuleCtorName

There has been couple complaints about this kind of naming. AFAIK the consensus is that clang-tidy should be happy.

64

I'd rather you convert in the different direction then. From flag to options. Globals are worse than locals :)

156

I'm not sure if there was a reason for that. Maybe history. If nothing prevents it, I suggest you use __esan_ prefix everywhere. Would be much easier to spot/understand the assemby dump.

167

I actually thought this is a typo :) Seems to be 20x usages for Ctx than Cxt :)

182

Yep. A simple TBD will do.

196

No, I don't propose that. I guess if this becomes a problem, you'd be able to change it to ModulePass. Let's ignore this for a while.

[silvas]

In D19167#403143, @silvas wrote:

Is there an RFC for this or something? I'm having a hard time figuring out exactly what it is trying to accomplish or what the ultimate "performance tuning family of tools" is going to be.

I mean, I think it is interesting, but I think llvm-dev would like to see the big picture first.

Is the mem*/str* instrumentation for a shadow-based version of http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40679.pdf ?

I probed a bit on IRC and there didn't seem to be any general awareness of this EfficiencySanitizer. Would you mind starting an RFC on llvm-dev?

[bruening]

In D19167#403143, @silvas wrote:

Is there an RFC for this or something? I'm having a hard time figuring out exactly what it is trying to accomplish or what the ultimate "performance tuning family of tools" is going to be.

I will send an RFC to llvm-dev.

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

156

These are calling the libc functions, which are then intercepted, rather than calling custom routines in the runtime: thus they must remain the exported libc names.

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

21

So the current code is correct. Note that clang-format does not think so.

[bruening]

Addresses reviewer comments + clang-tidy and clang-format

[aizatsky]

include/llvm/Transforms/Instrumentation.h

128

Update comment.

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

318

for simplicity/consistency let's make TypeSize in bytes?

[bruening]

Address reviewer comments: typo and size in bytes.

[aizatsky]

The code LGTM.

[filcab]

Thanks a lot for working on this. I'm interested in it. :-)

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

52

Would "loads and stores" be better than a general "memory accesses"?

95

shouldIgnoreMemoryAccess?

139

Why not load/store, like the llvm instructions, instead of read and write?

147

Why the different SmallString size?

168

Any reason for the extra parens?

307

The three cases above can be written more succintly (and made easier to follow/spot (lack of) differences).
Check out AddressSanitizer::instrumentMemIntrinsic.

323

Do we want to warn once (per run of whatever tool), though?

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

307

Reviewer ping-pong :) Please see the original version of this code in the first patchset, which matched what asan had, and the reviewer comment above asking to change it to the current form.

[filcab]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

307

I have a very strong preference over the simpler (to read and (even more important: ) to spot differences) code.
Mike: Do you have a strong preference over this idiom?
MemTransferIntrin has been there, with only these two subclasses, since 2009.
I think it's better to have the simpler version, and eventually change it if we need.

btw, Derek: You can reduce the noise by using isa<Mem...>, and getting the arguments from a MemIntrinsic, like ASan does.

[aizatsky]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

307

No I do not have any strong preference.

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

52

OK. The flag was modeled after tsan's flag which has this name.

139

This was modeled after tsan, which calls them read and write. It looks like asan uses load and store. I am fine changing it.

147

That's what tsan has, presumably being paranoid about the extra length of "unaligned".

168

This is what AddressSanitizer.cpp and MemorySanitizer.cpp have. Will remove from here.

307

btw, Derek: You can reduce the noise by using isa<Mem...>, and getting the arguments from a MemIntrinsic, like ASan does.

This code was originally modeled after tsan. Yes, asan is more succinct than the tsan code, once it does the cast.

323

OK. I don't see any DO_ONCE macro or std::call_once in the code base so I suppose a direct static bool is the method.

How do I test for this warning in the .ll file? Also, it seems to pollute the lit output a bit.

[bruening]

Rename read to load; add warning; other misc requested changes.

[filcab]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

324

Polluting output too much is annoying. Thinking about it, I guess we might hit this on most runs, not just rarely, which makes it less useful.
How about doing something like ASan does in instrumentUnusualSizeOrAlignment?

[filcab]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

324

Or just add an __esan_{un,}aligned_load_n function which we call with addr and size, and then we can figure out the fastpath later (which depends on the tool anyway).

[bruening]

Add callouts for unusually-sized loads and stores.

[filcab]

My bigger nits are name related, so I'll give you the LGTM now.

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

60

We probably want to change "Bad" to something else. Non-power-of-two-below-or-equal-to-16 doesn't roll off the tongue, though.
How about "irregular", or something like that? Or even "unusual". My problem here is that it's not explanatory.

113

I'd prefer a better explained name, like EsanStoreN (probably with a comment saying we assume it's unaligned, for now?)

158

Same thing, I'd prefer a __esan_unaligned_store_n name (or __esan_unaligned_store_range, if you're following tsan's names, instead of asan's), like the other sanitizers.

include/llvm/InitializePasses.h

 void initializePGOInstrumentationUsePass(PassRegistry&);
 void initializeInstrProfilingPass(PassRegistry&);
 void initializeAddressSanitizerPass(PassRegistry&);
 void initializeAddressSanitizerModulePass(PassRegistry&);
 void initializeMemorySanitizerPass(PassRegistry&);
 void initializeThreadSanitizerPass(PassRegistry&);
 void initializeSanitizerCoverageModulePass(PassRegistry&);
 void initializeDataFlowSanitizerPass(PassRegistry&);
+void initializeEfficiencySanitizerPass(PassRegistry&);
 void initializeScalarizerPass(PassRegistry&);
 void initializeEarlyCSELegacyPassPass(PassRegistry &);
 void initializeEliminateAvailableExternallyPass(PassRegistry&);
 void initializeExpandISelPseudosPass(PassRegistry&);
 void initializeForceFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializeGCMachineCodeAnalysisPass(PassRegistry&);
 void initializeGCModuleInfoPass(PassRegistry&);
 void initializeGVNLegacyPassPass(PassRegistry&);

include/llvm/Transforms/Instrumentation.h

 // Insert ThreadSanitizer (race detection) instrumentation
 FunctionPass *createThreadSanitizerPass();
 
 // Insert DataFlowSanitizer (dynamic data flow analysis) instrumentation
 ModulePass *createDataFlowSanitizerPass(
     const std::vector<std::string> &ABIListFiles = std::vector<std::string>(),
     void *(*getArgTLS)() = nullptr, void *(*getRetValTLS)() = nullptr);
 
+// Options for EfficiencySanitizer sub-tools.
+struct EfficiencySanitizerOptions {
+  EfficiencySanitizerOptions() : ToolType(ESAN_None) {}
+  enum Type {
+    ESAN_None = 0,
+    ESAN_CacheFrag,
+  } ToolType;
+};
+
+// Insert SanitizerCoverage instrumentation.
+FunctionPass *createEfficiencySanitizerPass(
+    const EfficiencySanitizerOptions &Options = EfficiencySanitizerOptions());
+
 // Options for sanitizer coverage instrumentation.
 struct SanitizerCoverageOptions {
   SanitizerCoverageOptions()
       : CoverageType(SCK_None), IndirectCalls(false), TraceBB(false),
         TraceCmp(false), Use8bitCounters(false), TracePC(false) {}
 
   enum Type {
     SCK_None = 0,

lib/Transforms/Instrumentation/CMakeLists.txt

 add_llvm_library(LLVMInstrumentation
   AddressSanitizer.cpp
   BoundsChecking.cpp
   DataFlowSanitizer.cpp
   GCOVProfiling.cpp
   MemorySanitizer.cpp
   Instrumentation.cpp
   InstrProfiling.cpp
   PGOInstrumentation.cpp
   SanitizerCoverage.cpp
   ThreadSanitizer.cpp
+  EfficiencySanitizer.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   )
 
 add_dependencies(LLVMInstrumentation intrinsics_gen)

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

+//===-- EfficiencySanitizer.cpp - performance tuner -----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of EfficiencySanitizer, a family of performance tuners
+// that detects multiple performance issues via separate sub-tools.
+//
+// The instrumentation phase is straightforward:
+//   - Take action on every memory access: either inlined instrumentation,
+//     or Inserted calls to our run-time library.
+//   - Optimizations may apply to avoid instrumenting some of the accesses.
+//   - Turn mem{set,cpy,move} instrinsics into library calls.
+// The rest is handled by the run-time library.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Instrumentation.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/Type.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "esan"
+
+// The tool type must be just one of these ClTool* options, as the tools
+// cannot be combined due to shadow memory constraints.
+static cl::opt<bool>  ClToolCacheFrag(
+    "esan-cache-frag", cl::init(false),
+    cl::desc("Detect cache fragmentation"), cl::Hidden);
+// Each new tool will get its own opt flag here.
+
+static cl::opt<bool>  ClInstrumentMemoryAccesses(
+    "esan-instrument-memory-accesses", cl::init(true),
+    cl::desc("Instrument memory accesses"), cl::Hidden);
+static cl::opt<bool>  ClInstrumentMemIntrinsics(
+    "esan-instrument-memintrinsics", cl::init(true),
+    cl::desc("Instrument memintrinsics (memset/memcpy/memmove)"), cl::Hidden);
+
+STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
+STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
+STATISTIC(NumFastpaths, "Number of instrumented fastpaths");
+STATISTIC(NumAccessesWithBadSize, "Number of accesses with a bad size");
+
+static const char *const kEsanModuleCtorName = "esan.module_ctor";
+static const char *const kEsanInitName = "__esan_init";
+
+namespace {
+
+static void OverrideOptionsFromCL(const EfficiencySanitizerOptions &Options) {
+  if (Options.ToolType == EfficiencySanitizerOptions::ESAN_CacheFrag)
+    ClToolCacheFrag = true;
+
+  // Direct opt invocation with no params will have the default ESAN_None.
+  if (!ClToolCacheFrag)
+    ClToolCacheFrag = true; // Default tool
+
+  // Exactly one tool must be enabled.
+  assert(ClToolCacheFrag);
+}
+
+/// EfficiencySanitizer: instrument each module to find performance issues.
+class EfficiencySanitizer : public FunctionPass {
+ public:
+  EfficiencySanitizer(
+      const EfficiencySanitizerOptions &Opts = EfficiencySanitizerOptions())
+      : FunctionPass(ID), Options(Opts) {
+    OverrideOptionsFromCL(Opts);
+  }
+  const char *getPassName() const override;
+  bool runOnFunction(Function &F) override;
+  bool doInitialization(Module &M) override;
+  static char ID;
+
+ private:
+  void initializeCallbacks(Module &M);
+  bool instrumentLoadOrStore(Instruction *I, const DataLayout &DL);
+  bool instrumentMemIntrinsic(Instruction *I);
+  bool ignoreMemoryAccess(Instruction *I);
+  int getMemoryAccessFuncIndex(Value *Addr, const DataLayout &DL);
+  bool instrumentFastpath(Instruction *I, const DataLayout &DL, bool IsWrite,
+                          Value *Addr, unsigned Alignment);
+  // Each tool has its own fastpath routine:
+  bool instrumentFastpathCacheFrag(Instruction *I, const DataLayout &DL,
+                                   Value *Addr, unsigned Alignment);
+
+  EfficiencySanitizerOptions Options;
+  LLVMContext *Cxt;
+  Type *IntptrTy;
+  // Our slowpath involves callouts to the runtime library.
+  // Access sizes are powers of two: 1, 2, 4, 8, 16.
+  static const size_t kNumberOfAccessSizes = 5;
+  Function *EsanAlignedRead[kNumberOfAccessSizes];
+  Function *EsanAlignedWrite[kNumberOfAccessSizes];
+  Function *EsanUnalignedRead[kNumberOfAccessSizes];
+  Function *EsanUnalignedWrite[kNumberOfAccessSizes];
+  Function *MemmoveFn, *MemcpyFn, *MemsetFn;
+  Function *EsanCtorFunction;
+};
+}  // namespace
+
+char EfficiencySanitizer::ID = 0;
+INITIALIZE_PASS(EfficiencySanitizer, "esan",
+    "EfficiencySanitizer: finds performance issues.",
+    false, false)
+
+const char *EfficiencySanitizer::getPassName() const {
+  return "EfficiencySanitizer";
+}
+
+FunctionPass *llvm::createEfficiencySanitizerPass(
+    const EfficiencySanitizerOptions &Options) {
+  return new EfficiencySanitizer(Options);
+}
+
+void EfficiencySanitizer::initializeCallbacks(Module &M) {
+  IRBuilder<> IRB(M.getContext());
+  // Initialize the callbacks.
+  for (size_t i = 0; i < kNumberOfAccessSizes; ++i) {
+    const unsigned ByteSize = 1U << i;
+    std::string ByteSizeStr = utostr(ByteSize);
+    // We'll inline the most common (i.e., aligned and frequent sizes)
+    // read + write instrumentation: these callouts are for the slowpath.
+    SmallString<32> AlignedReadName("__esan_aligned_read" + ByteSizeStr);
+    EsanAlignedRead[i] = checkSanitizerInterfaceFunction
+      (M.getOrInsertFunction(AlignedReadName, IRB.getVoidTy(),
+                             IRB.getInt8PtrTy(), nullptr));
+    SmallString<32> AlignedWriteName("__esan_aligned_write" + ByteSizeStr);
+    EsanAlignedWrite[i] = checkSanitizerInterfaceFunction
+      (M.getOrInsertFunction(AlignedWriteName, IRB.getVoidTy(),
+                             IRB.getInt8PtrTy(), nullptr));
+    SmallString<64> UnalignedReadName("__esan_unaligned_read" + ByteSizeStr);
+    EsanUnalignedRead[i] = checkSanitizerInterfaceFunction
+      (M.getOrInsertFunction(UnalignedReadName, IRB.getVoidTy(), IRB.
+                             getInt8PtrTy(), nullptr));
+    SmallString<64> UnalignedWriteName("__esan_unaligned_write" + ByteSizeStr);
+    EsanUnalignedWrite[i] = checkSanitizerInterfaceFunction
+      (M.getOrInsertFunction(UnalignedWriteName, IRB.getVoidTy(), IRB.
+                             getInt8PtrTy(), nullptr));
+  }
+  MemmoveFn = checkSanitizerInterfaceFunction(
+      M.getOrInsertFunction("memmove", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
+                            IRB.getInt8PtrTy(), IntptrTy, nullptr));
+  MemcpyFn = checkSanitizerInterfaceFunction(
+      M.getOrInsertFunction("memcpy", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
+                            IRB.getInt8PtrTy(), IntptrTy, nullptr));
+  MemsetFn = checkSanitizerInterfaceFunction(
+      M.getOrInsertFunction("memset", IRB.getInt8PtrTy(), IRB.getInt8PtrTy(),
+                            IRB.getInt32Ty(), IntptrTy, nullptr));
+}
+
+bool EfficiencySanitizer::doInitialization(Module &M) {
+  Cxt = &(M.getContext());
+  const DataLayout &DL = M.getDataLayout();
+  IRBuilder<> IRB(M.getContext());
+  IntegerType *OrdTy = IRB.getInt32Ty();
+  IntptrTy = DL.getIntPtrType(M.getContext());
+  std::tie(EsanCtorFunction, std::ignore) = createSanitizerCtorAndInitFunctions(
+      M, kEsanModuleCtorName, kEsanInitName, /*InitArgTypes=*/{OrdTy},
+      /*InitArgs=*/{ConstantInt::get(OrdTy,
+                                     static_cast<int>(Options.ToolType))});
+
+  appendToGlobalCtors(M, EsanCtorFunction, 0);
+
+  return true;
+}
+
+bool EfficiencySanitizer::ignoreMemoryAccess(Instruction *I) {
+  if (ClToolCacheFrag) {
+    // We'd like to know about cache fragmentation in vtable accesses and
+    // constant data references, so we do not currently ignore anything.
+    return false;
+  }
+  return false;
+}
+
+bool EfficiencySanitizer::runOnFunction(Function &F) {
+  // This is required to prevent instrumenting the call to __esan_init from
+  // within the module constructor.
+  if (&F == EsanCtorFunction)
+    return false;
+  initializeCallbacks(*F.getParent());
+  SmallVector<Instruction*, 8> LoadsAndStores;
+  SmallVector<Instruction*, 8> MemIntrinCalls;
+  bool Res = false;
+  const DataLayout &DL = F.getParent()->getDataLayout();
+
+  for (auto &BB : F) {
+    for (auto &Inst : BB) {
+      if ((isa<LoadInst>(Inst) || isa<StoreInst>(Inst) ||
+           isa<AtomicRMWInst>(Inst) || isa<AtomicCmpXchgInst>(Inst)) &&
+          !ignoreMemoryAccess(&Inst))
+        LoadsAndStores.push_back(&Inst);
+      else if (isa<MemIntrinsic>(Inst))
+        MemIntrinCalls.push_back(&Inst);
+    }
+  }
+
+  if (ClInstrumentMemoryAccesses) {
+    for (auto Inst : LoadsAndStores) {
+      Res |= instrumentLoadOrStore(Inst, DL);
+    }
+  }
+
+  if (ClInstrumentMemIntrinsics) {
+    for (auto Inst : MemIntrinCalls) {
+      Res |= instrumentMemIntrinsic(Inst);
+    }
+  }
+
+  return Res;
+}
+
+bool EfficiencySanitizer::instrumentLoadOrStore(Instruction *I,
+                                                const DataLayout &DL) {
+  IRBuilder<> IRB(I);
+  bool IsWrite;
+  Value *Addr;
+  unsigned Alignment;
+  if (LoadInst *Load = dyn_cast<LoadInst>(I)) {
+    IsWrite = false;
+    Alignment = Load->getAlignment();
+    Addr = Load->getPointerOperand();
+  } else if (StoreInst *Store = dyn_cast<StoreInst>(I)) {
+    IsWrite = true;
+    Alignment = Store->getAlignment();
+    Addr = Store->getPointerOperand();
+  } else if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
+    IsWrite = true;
+    Alignment = 0;
+    Addr = RMW->getPointerOperand();
+  } else if (AtomicCmpXchgInst *Xchg = dyn_cast<AtomicCmpXchgInst>(I)) {
+    IsWrite = true;
+    Alignment = 0;
+    Addr = Xchg->getPointerOperand();
+  } else
+    llvm_unreachable("Unsupported mem access type");
+
+  int Idx = getMemoryAccessFuncIndex(Addr, DL);
+  if (Idx < 0)
+    return false;
+  Type *OrigTy = cast<PointerType>(Addr->getType())->getElementType();
+  const uint32_t TypeSize = DL.getTypeStoreSizeInBits(OrigTy);
+  Value *OnAccessFunc = nullptr;
+  if (IsWrite)
+    NumInstrumentedWrites++;
+  else
+    NumInstrumentedReads++;
+  if (instrumentFastpath(I, DL, IsWrite, Addr, Alignment)) {
+    NumFastpaths++;
+    return true;
+  }
+  if (Alignment == 0 || Alignment >= 8 || (Alignment % (TypeSize / 8)) == 0)
+    OnAccessFunc = IsWrite ? EsanAlignedWrite[Idx] : EsanAlignedRead[Idx];
+  else
+    OnAccessFunc = IsWrite ? EsanUnalignedWrite[Idx] : EsanUnalignedRead[Idx];
+  IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()));
+  return true;
+}
+
+// It's simplest to replace the memset/memmove/memcpy intrinsics with
+// calls that the runtime library intercepts.
+// Our pass is late enough that calls should not turn back into intrinsics.
+bool EfficiencySanitizer::instrumentMemIntrinsic(Instruction *I) {
+  IRBuilder<> IRB(I);
+  if (MemSetInst *M = dyn_cast<MemSetInst>(I)) {
+    IRB.CreateCall(
+        MemsetFn,
+        {IRB.CreatePointerCast(M->getArgOperand(0), IRB.getInt8PtrTy()),
+         IRB.CreateIntCast(M->getArgOperand(1), IRB.getInt32Ty(), false),
+         IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false)});
+    I->eraseFromParent();
+  } else if (MemTransferInst *M = dyn_cast<MemTransferInst>(I)) {
+    IRB.CreateCall(
+        isa<MemCpyInst>(M) ? MemcpyFn : MemmoveFn,
+        {IRB.CreatePointerCast(M->getArgOperand(0), IRB.getInt8PtrTy()),
+         IRB.CreatePointerCast(M->getArgOperand(1), IRB.getInt8PtrTy()),
+         IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false)});
+    I->eraseFromParent();
+  }
+  return false;
+}
+
+int EfficiencySanitizer::getMemoryAccessFuncIndex(Value *Addr,
+                                                  const DataLayout &DL) {
+  Type *OrigPtrTy = Addr->getType();
+  Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType();
+  assert(OrigTy->isSized());
+  uint32_t TypeSize = DL.getTypeStoreSizeInBits(OrigTy);
+  if (TypeSize != 8  && TypeSize != 16 &&
+      TypeSize != 32 && TypeSize != 64 && TypeSize != 128) {
+    NumAccessesWithBadSize++;
+    // Ignore all unusual sizes.
+    return -1;
+  }
+  size_t Idx = countTrailingZeros(TypeSize / 8);
+  assert(Idx < kNumberOfAccessSizes);
+  return Idx;
+}
+
+bool EfficiencySanitizer::instrumentFastpath(Instruction *I,
+                                             const DataLayout &DL,
+                                             bool IsWrite,
+                                             Value *Addr,
+                                             unsigned Alignment) {
+  if (ClToolCacheFrag) {
+    return instrumentFastpathCacheFrag(I, DL, Addr, Alignment);
+  }
+  return false;
+}
+
+bool EfficiencySanitizer::instrumentFastpathCacheFrag(
+    Instruction *I, const DataLayout &DL, Value *Addr, unsigned Alignment) {
+  // TODO(bruening): implement a fastpath for aligned accesses
+  return false;
+}

lib/Transforms/Instrumentation/Instrumentation.cpp

void llvm::initializeInstrumentation(PassRegistry &Registry) {
   initializeGCOVProfilerPass(Registry);
   initializePGOInstrumentationGenPass(Registry);
   initializePGOInstrumentationUsePass(Registry);
   initializeInstrProfilingPass(Registry);
   initializeMemorySanitizerPass(Registry);
   initializeThreadSanitizerPass(Registry);
   initializeSanitizerCoverageModulePass(Registry);
   initializeDataFlowSanitizerPass(Registry);
+  initializeEfficiencySanitizerPass(Registry);
 }
 
 /// LLVMInitializeInstrumentation - C binding for
 /// initializeInstrumentation.
 void LLVMInitializeInstrumentation(LLVMPassRegistryRef R) {
   initializeInstrumentation(*unwrap(R));
 }

test/Instrumentation/EfficiencySanitizer/cache_frag_basic.ll

+; Test basic EfficiencySanitizer cache frag instrumentation.
+;
+; RUN: opt < %s -esan -esan-cache-frag -S | FileCheck %s
+
+define i32 @loadWord(i32* %a) {
+entry:
+  %tmp1 = load i32, i32* %a, align 4
+  ret i32 %tmp1
+}
+
+; CHECK: @llvm.global_ctors = {{.*}}@esan.module_ctor
+
+; CHECK:        %0 = bitcast i32* %a to i8*
+; CHECK-NEXT:   call void @__esan_aligned_read4(i8* %0)
+; CHECK-NEXT:   %tmp1 = load i32, i32* %a, align 4
+; CHECK-NEXT:   ret i32 %tmp1
+
+; Ensure that esan converts memcpy intrinsics to calls:
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1)
+declare void @llvm.memmove.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1)
+declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1)
+
+define void @memCpyTest(i8* nocapture %x, i8* nocapture %y) {
+entry:
+    tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* %x, i8* %y, i64 16, i32 4, i1 false)
+    ret void
+; CHECK: define void @memCpyTest
+; CHECK: call i8* @memcpy
+; CHECK: ret void
+}
+
+define void @memMoveTest(i8* nocapture %x, i8* nocapture %y) {
+entry:
+    tail call void @llvm.memmove.p0i8.p0i8.i64(i8* %x, i8* %y, i64 16, i32 4, i1 false)
+    ret void
+; CHECK: define void @memMoveTest
+; CHECK: call i8* @memmove
+; CHECK: ret void
+}
+
+define void @memSetTest(i8* nocapture %x) {
+entry:
+    tail call void @llvm.memset.p0i8.i64(i8* %x, i8 77, i64 16, i32 4, i1 false)
+    ret void
+; CHECK: define void @memSetTest
+; CHECK: call i8* @memset
+; CHECK: ret void
+}
+
+; CHECK: define internal void @esan.module_ctor()
+; CHECK: call void @__esan_init(i32 0)