[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

22

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

49

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

60

this don't follow llvm naming convention.

65

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

157

why not __esan_memmove?

168

Ctx

183

this function always returns false.

197

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

290

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

295

llvm_unreachable?

296

return true?

test/Instrumentation/EfficiencySanitizer/cache_frag_basic.ll

53

please add unaligned read & odd size tests.

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

22

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

49

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

60

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.

65

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?

157

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_.

168

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

183

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.

197

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?

290

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

295

OK.

296

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

test/Instrumentation/EfficiencySanitizer/cache_frag_basic.ll

53

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

22

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

[aizatsky]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

22

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.

60

kEsanModuleCtorName

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

65

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

157

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.

168

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

183

Yep. A simple TBD will do.

197

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

157

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

22

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

51

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

94

shouldIgnoreMemoryAccess?

138

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

146

Why the different SmallString size?

167

Any reason for the extra parens?

306

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

322

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

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

306

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

306

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

306

No I do not have any strong preference.

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

51

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

138

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

146

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

167

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

306

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.

322

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 EfficiencySanitizer 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 data cache fragmentation"), cl::Hidden);
+// Each new tool will get its own opt flag here.
+// These are converted to EfficiencySanitizerOptions for use
+// in the code.
+
+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 EsanModuleCtorName = "esan.module_ctor";
+static const char *const EsanInitName = "__esan_init";
+
+namespace {
+
+static EfficiencySanitizerOptions
+OverrideOptionsFromCL(EfficiencySanitizerOptions Options) {
+  if (ClToolCacheFrag)
+    Options.ToolType = EfficiencySanitizerOptions::ESAN_CacheFrag;
+
+  // Direct opt invocation with no params will have the default ESAN_None.
+  // We run the default tool in that case.
+  if (Options.ToolType == EfficiencySanitizerOptions::ESAN_None)
+    Options.ToolType = EfficiencySanitizerOptions::ESAN_CacheFrag;
+
+  return Options;
+}
+
+/// EfficiencySanitizer: instrument each module to find performance issues.
+class EfficiencySanitizer : public FunctionPass {
+public:
+  EfficiencySanitizer(
+      const EfficiencySanitizerOptions &Opts = EfficiencySanitizerOptions())
+      : FunctionPass(ID), Options(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 *Ctx;
+  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 NumberOfAccessSizes = 5;
+  Function *EsanAlignedRead[NumberOfAccessSizes];
+  Function *EsanAlignedWrite[NumberOfAccessSizes];
+  Function *EsanUnalignedRead[NumberOfAccessSizes];
+  Function *EsanUnalignedWrite[NumberOfAccessSizes];
+  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 Idx = 0; Idx < NumberOfAccessSizes; ++Idx) {
+    const unsigned ByteSize = 1U << Idx;
+    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[Idx] =
+        checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+            AlignedReadName, IRB.getVoidTy(), IRB.getInt8PtrTy(), nullptr));
+    SmallString<32> AlignedWriteName("__esan_aligned_write" + ByteSizeStr);
+    EsanAlignedWrite[Idx] =
+        checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+            AlignedWriteName, IRB.getVoidTy(), IRB.getInt8PtrTy(), nullptr));
+    SmallString<64> UnalignedReadName("__esan_unaligned_read" + ByteSizeStr);
+    EsanUnalignedRead[Idx] =
+        checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+            UnalignedReadName, IRB.getVoidTy(), IRB.getInt8PtrTy(), nullptr));
+    SmallString<64> UnalignedWriteName("__esan_unaligned_write" + ByteSizeStr);
+    EsanUnalignedWrite[Idx] =
+        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) {
+  Ctx = &(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, EsanModuleCtorName, EsanInitName, /*InitArgTypes=*/{OrdTy},
+      /*InitArgs=*/{
+          ConstantInt::get(OrdTy, static_cast<int>(Options.ToolType))});
+
+  appendToGlobalCtors(M, EsanCtorFunction, 0);
+
+  return true;
+}
+
+bool EfficiencySanitizer::ignoreMemoryAccess(Instruction *I) {
+  if (Options.ToolType == EfficiencySanitizerOptions::ESAN_CacheFrag) {
+    // We'd like to know about cache fragmentation in vtable accesses and
+    // constant data references, so we do not currently ignore anything.
+    return false;
+  }
+  // TODO(bruening): future tools will be returning true for some cases.
+  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;
+  // As a function pass, we must re-initialize every time.
+  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 TypeSizeBytes = DL.getTypeStoreSizeInBits(OrigTy) / 8;
+  Value *OnAccessFunc = nullptr;
+  if (IsWrite)
+    NumInstrumentedWrites++;
+  else
+    NumInstrumentedReads++;
+  if (instrumentFastpath(I, DL, IsWrite, Addr, Alignment)) {
+    NumFastpaths++;
+    return true;
+  }
+  if (Alignment == 0 || Alignment >= 8 || (Alignment % TypeSizeBytes) == 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);
+  bool Res = false;
+  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();
+    Res = true;
+  } else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I)) {
+    IRB.CreateCall(
+        MemcpyFn,
+        {IRB.CreatePointerCast(M->getArgOperand(0), IRB.getInt8PtrTy()),
+         IRB.CreatePointerCast(M->getArgOperand(1), IRB.getInt8PtrTy()),
+         IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false)});
+    I->eraseFromParent();
+    Res = true;
+  } else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I)) {
+    IRB.CreateCall(
+        MemmoveFn,
+        {IRB.CreatePointerCast(M->getArgOperand(0), IRB.getInt8PtrTy()),
+         IRB.CreatePointerCast(M->getArgOperand(1), IRB.getInt8PtrTy()),
+         IRB.CreateIntCast(M->getArgOperand(2), IntptrTy, false)});
+    I->eraseFromParent();
+    Res = true;
+  } else
+    llvm_unreachable("Unsupported mem intrinsic type");
+  return Res;
+}
+
+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 &&
+      TypeSizeBytes != 8 && TypeSizeBytes != 16) {
+    NumAccessesWithBadSize++;
+    // Ignore all unusual sizes.
+    return -1;
+  }
+  size_t Idx = countTrailingZeros(TypeSizeBytes);
+  assert(Idx < NumberOfAccessSizes);
+  return Idx;
+}
+
+bool EfficiencySanitizer::instrumentFastpath(Instruction *I,
+                                             const DataLayout &DL, bool IsWrite,
+                                             Value *Addr, unsigned Alignment) {
+  if (Options.ToolType == EfficiencySanitizerOptions::ESAN_CacheFrag) {
+    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
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+; Aligned loads:
+
+define i8 @loadAligned1(i8* %a) {
+entry:
+  %tmp1 = load i8, i8* %a, align 1
+  ret i8 %tmp1
+; CHECK: @llvm.global_ctors = {{.*}}@esan.module_ctor
+; CHECK:        call void @__esan_aligned_read1(i8* %a)
+; CHECK-NEXT:   %tmp1 = load i8, i8* %a, align 1
+; CHECK-NEXT:   ret i8 %tmp1
+}
+
+define i16 @loadAligned2(i16* %a) {
+entry:
+  %tmp1 = load i16, i16* %a, align 2
+  ret i16 %tmp1
+; CHECK:        %0 = bitcast i16* %a to i8*
+; CHECK-NEXT:   call void @__esan_aligned_read2(i8* %0)
+; CHECK-NEXT:   %tmp1 = load i16, i16* %a, align 2
+; CHECK-NEXT:   ret i16 %tmp1
+}
+
+define i32 @loadAligned4(i32* %a) {
+entry:
+  %tmp1 = load i32, i32* %a, align 4
+  ret i32 %tmp1
+; 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
+}
+
+define i64 @loadAligned8(i64* %a) {
+entry:
+  %tmp1 = load i64, i64* %a, align 8
+  ret i64 %tmp1
+; CHECK:        %0 = bitcast i64* %a to i8*
+; CHECK-NEXT:   call void @__esan_aligned_read8(i8* %0)
+; CHECK-NEXT:   %tmp1 = load i64, i64* %a, align 8
+; CHECK-NEXT:   ret i64 %tmp1
+}
+
+define i128 @loadAligned16(i128* %a) {
+entry:
+  %tmp1 = load i128, i128* %a, align 16
+  ret i128 %tmp1
+; CHECK:        %0 = bitcast i128* %a to i8*
+; CHECK-NEXT:   call void @__esan_aligned_read16(i8* %0)
+; CHECK-NEXT:   %tmp1 = load i128, i128* %a, align 16
+; CHECK-NEXT:   ret i128 %tmp1
+}
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+; Aligned stores:
+
+define void @storeAligned1(i8* %a) {
+entry:
+  store i8 1, i8* %a, align 1
+  ret void
+; CHECK:        call void @__esan_aligned_write1(i8* %a)
+; CHECK-NEXT:   store i8 1, i8* %a, align 1
+; CHECK-NEXT:   ret void
+}
+
+define void @storeAligned2(i16* %a) {
+entry:
+  store i16 1, i16* %a, align 2
+  ret void
+; CHECK:        %0 = bitcast i16* %a to i8*
+; CHECK-NEXT:   call void @__esan_aligned_write2(i8* %0)
+; CHECK-NEXT:   store i16 1, i16* %a, align 2
+; CHECK-NEXT:   ret void
+}
+
+define void @storeAligned4(i32* %a) {
+entry:
+  store i32 1, i32* %a, align 4
+  ret void
+; CHECK:        %0 = bitcast i32* %a to i8*
+; CHECK-NEXT:   call void @__esan_aligned_write4(i8* %0)
+; CHECK-NEXT:   store i32 1, i32* %a, align 4
+; CHECK-NEXT:   ret void
+}
+
+define void @storeAligned8(i64* %a) {
+entry:
+  store i64 1, i64* %a, align 8
+  ret void
+; CHECK:        %0 = bitcast i64* %a to i8*
+; CHECK-NEXT:   call void @__esan_aligned_write8(i8* %0)
+; CHECK-NEXT:   store i64 1, i64* %a, align 8
+; CHECK-NEXT:   ret void
+}
+
+define void @storeAligned16(i128* %a) {
+entry:
+  store i128 1, i128* %a, align 16
+  ret void
+; CHECK:        %0 = bitcast i128* %a to i8*
+; CHECK-NEXT:   call void @__esan_aligned_write16(i8* %0)
+; CHECK-NEXT:   store i128 1, i128* %a, align 16
+; CHECK-NEXT:   ret void
+}
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+; Unaligned loads:
+
+define i16 @loadUnaligned2(i16* %a) {
+entry:
+  %tmp1 = load i16, i16* %a, align 1
+  ret i16 %tmp1
+; CHECK:        %0 = bitcast i16* %a to i8*
+; CHECK-NEXT:   call void @__esan_unaligned_read2(i8* %0)
+; CHECK-NEXT:   %tmp1 = load i16, i16* %a, align 1
+; CHECK-NEXT:   ret i16 %tmp1
+}
+
+define i32 @loadUnaligned4(i32* %a) {
+entry:
+  %tmp1 = load i32, i32* %a, align 1
+  ret i32 %tmp1
+; CHECK:        %0 = bitcast i32* %a to i8*
+; CHECK-NEXT:   call void @__esan_unaligned_read4(i8* %0)
+; CHECK-NEXT:   %tmp1 = load i32, i32* %a, align 1
+; CHECK-NEXT:   ret i32 %tmp1
+}
+
+define i64 @loadUnaligned8(i64* %a) {
+entry:
+  %tmp1 = load i64, i64* %a, align 1
+  ret i64 %tmp1
+; CHECK:        %0 = bitcast i64* %a to i8*
+; CHECK-NEXT:   call void @__esan_unaligned_read8(i8* %0)
+; CHECK-NEXT:   %tmp1 = load i64, i64* %a, align 1
+; CHECK-NEXT:   ret i64 %tmp1
+}
+
+define i128 @loadUnaligned16(i128* %a) {
+entry:
+  %tmp1 = load i128, i128* %a, align 1
+  ret i128 %tmp1
+; CHECK:        %0 = bitcast i128* %a to i8*
+; CHECK-NEXT:   call void @__esan_unaligned_read16(i8* %0)
+; CHECK-NEXT:   %tmp1 = load i128, i128* %a, align 1
+; CHECK-NEXT:   ret i128 %tmp1
+}
+
+define x86_fp80 @loadUnalignedFP(x86_fp80* %a) {
+entry:
+  %tmp1 = load x86_fp80, x86_fp80* %a, align 1
+  ret x86_fp80 %tmp1
+; CHECK:         %tmp1 = load x86_fp80, x86_fp80* %a, align 1
+; CHECK-NEXT:   ret x86_fp80 %tmp1
+}
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+; Unaligned stores:
+
+define void @storeUnaligned2(i16* %a) {
+entry:
+  store i16 1, i16* %a, align 1
+  ret void
+; CHECK:        %0 = bitcast i16* %a to i8*
+; CHECK-NEXT:   call void @__esan_unaligned_write2(i8* %0)
+; CHECK-NEXT:   store i16 1, i16* %a, align 1
+; CHECK-NEXT:   ret void
+}
+
+define void @storeUnaligned4(i32* %a) {
+entry:
+  store i32 1, i32* %a, align 1
+  ret void
+; CHECK:        %0 = bitcast i32* %a to i8*
+; CHECK-NEXT:   call void @__esan_unaligned_write4(i8* %0)
+; CHECK-NEXT:   store i32 1, i32* %a, align 1
+; CHECK-NEXT:   ret void
+}
+
+define void @storeUnaligned8(i64* %a) {
+entry:
+  store i64 1, i64* %a, align 1
+  ret void
+; CHECK:        %0 = bitcast i64* %a to i8*
+; CHECK-NEXT:   call void @__esan_unaligned_write8(i8* %0)
+; CHECK-NEXT:   store i64 1, i64* %a, align 1
+; CHECK-NEXT:   ret void
+}
+
+define void @storeUnaligned16(i128* %a) {
+entry:
+  store i128 1, i128* %a, align 1
+  ret void
+; CHECK:        %0 = bitcast i128* %a to i8*
+; CHECK-NEXT:   call void @__esan_unaligned_write16(i8* %0)
+; CHECK-NEXT:   store i128 1, i128* %a, align 1
+; CHECK-NEXT:   ret void
+}
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+; 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
+}
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+; Top-level:
+
+; CHECK: define internal void @esan.module_ctor()
+; CHECK: call void @__esan_init(i32 1)