[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 ↗

(On Diff #53917)

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

48 ↗

(On Diff #53917)

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

59 ↗

(On Diff #53917)

this don't follow llvm naming convention.

64 ↗

(On Diff #53917)

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

156 ↗

(On Diff #53917)

why not __esan_memmove?

167 ↗

(On Diff #53917)

Ctx

182 ↗

(On Diff #53917)

this function always returns false.

196 ↗

(On Diff #53917)

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

289 ↗

(On Diff #53917)

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

294 ↗

(On Diff #53917)

llvm_unreachable?

295 ↗

(On Diff #53917)

return true?

test/Instrumentation/EfficiencySanitizer/cache_frag_basic.ll

52 ↗

(On Diff #53917)

please add unaligned read & odd size tests.

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

21 ↗

(On Diff #53917)

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

48 ↗

(On Diff #53917)

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

59 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

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

182 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

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

294 ↗

(On Diff #53917)

OK.

295 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

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

[aizatsky]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

21 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

kEsanModuleCtorName

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

64 ↗

(On Diff #53917)

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

156 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

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

182 ↗

(On Diff #53917)

Yep. A simple TBD will do.

196 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

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 ↗

(On Diff #53917)

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 ↗

(On Diff #54154)

Update comment.

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

317 ↗

(On Diff #54154)

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 ↗

(On Diff #54286)

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

94 ↗

(On Diff #54286)

shouldIgnoreMemoryAccess?

138 ↗

(On Diff #54286)

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

146 ↗

(On Diff #54286)

Why the different SmallString size?

167 ↗

(On Diff #54286)

Any reason for the extra parens?

306 ↗

(On Diff #54286)

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

322 ↗

(On Diff #54286)

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

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

306 ↗

(On Diff #54286)

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 ↗

(On Diff #54286)

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 ↗

(On Diff #54286)

No I do not have any strong preference.

[bruening]

lib/Transforms/Instrumentation/EfficiencySanitizer.cpp

51 ↗

(On Diff #54286)

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

138 ↗

(On Diff #54286)

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 ↗

(On Diff #54286)

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

167 ↗

(On Diff #54286)

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

306 ↗

(On Diff #54286)

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 ↗

(On Diff #54286)

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

323 ↗

(On Diff #54429)

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

323 ↗

(On Diff #54429)

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

59 ↗

(On Diff #54548)

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.

112 ↗

(On Diff #54548)

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

157 ↗

(On Diff #54548)

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.

llvm/trunk/include/llvm/InitializePasses.h

 void initializePGOInstrumentationUsePass(PassRegistry&);
 void initializeInstrProfilingLegacyPassPass(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&);

llvm/trunk/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,

llvm/trunk/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)

llvm/trunk/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> ClInstrumentLoadsAndStores(
+    "esan-instrument-loads-and-stores", cl::init(true),
+    cl::desc("Instrument loads and stores"), cl::Hidden);
+static cl::opt<bool> ClInstrumentMemIntrinsics(
+    "esan-instrument-memintrinsics", cl::init(true),
+    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");
+
+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(MemIntrinsic *MI);
+  bool shouldIgnoreMemoryAccess(Instruction *I);
+  int getMemoryAccessFuncIndex(Value *Addr, const DataLayout &DL);
+  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);
+
+  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 *EsanAlignedLoad[NumberOfAccessSizes];
+  Function *EsanAlignedStore[NumberOfAccessSizes];
+  Function *EsanUnalignedLoad[NumberOfAccessSizes];
+  Function *EsanUnalignedStore[NumberOfAccessSizes];
+  // For irregular sizes of any alignment:
+  Function *EsanUnalignedLoadN, *EsanUnalignedStoreN;
+  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)
+    // load + store instrumentation: these callouts are for the slowpath.
+    SmallString<32> AlignedLoadName("__esan_aligned_load" + ByteSizeStr);
+    EsanAlignedLoad[Idx] =
+        checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+            AlignedLoadName, IRB.getVoidTy(), IRB.getInt8PtrTy(), nullptr));
+    SmallString<32> AlignedStoreName("__esan_aligned_store" + ByteSizeStr);
+    EsanAlignedStore[Idx] =
+        checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+            AlignedStoreName, IRB.getVoidTy(), IRB.getInt8PtrTy(), nullptr));
+    SmallString<32> UnalignedLoadName("__esan_unaligned_load" + ByteSizeStr);
+    EsanUnalignedLoad[Idx] =
+        checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+            UnalignedLoadName, IRB.getVoidTy(), IRB.getInt8PtrTy(), nullptr));
+    SmallString<32> UnalignedStoreName("__esan_unaligned_store" + ByteSizeStr);
+    EsanUnalignedStore[Idx] =
+        checkSanitizerInterfaceFunction(M.getOrInsertFunction(
+            UnalignedStoreName, IRB.getVoidTy(), IRB.getInt8PtrTy(), nullptr));
+  }
+  EsanUnalignedLoadN = checkSanitizerInterfaceFunction(
+      M.getOrInsertFunction("__esan_unaligned_loadN", IRB.getVoidTy(),
+                            IRB.getInt8PtrTy(), IntptrTy, nullptr));
+  EsanUnalignedStoreN = checkSanitizerInterfaceFunction(
+      M.getOrInsertFunction("__esan_unaligned_storeN", IRB.getVoidTy(),
+                            IRB.getInt8PtrTy(), IntptrTy, 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::shouldIgnoreMemoryAccess(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)) &&
+          !shouldIgnoreMemoryAccess(&Inst))
+        LoadsAndStores.push_back(&Inst);
+      else if (isa<MemIntrinsic>(Inst))
+        MemIntrinCalls.push_back(&Inst);
+    }
+  }
+
+  if (ClInstrumentLoadsAndStores) {
+    for (auto Inst : LoadsAndStores) {
+      Res |= instrumentLoadOrStore(Inst, DL);
+    }
+  }
+
+  if (ClInstrumentMemIntrinsics) {
+    for (auto Inst : MemIntrinCalls) {
+      Res |= instrumentMemIntrinsic(cast<MemIntrinsic>(Inst));
+    }
+  }
+
+  return Res;
+}
+
+bool EfficiencySanitizer::instrumentLoadOrStore(Instruction *I,
+                                                const DataLayout &DL) {
+  IRBuilder<> IRB(I);
+  bool IsStore;
+  Value *Addr;
+  unsigned Alignment;
+  if (LoadInst *Load = dyn_cast<LoadInst>(I)) {
+    IsStore = false;
+    Alignment = Load->getAlignment();
+    Addr = Load->getPointerOperand();
+  } else if (StoreInst *Store = dyn_cast<StoreInst>(I)) {
+    IsStore = true;
+    Alignment = Store->getAlignment();
+    Addr = Store->getPointerOperand();
+  } else if (AtomicRMWInst *RMW = dyn_cast<AtomicRMWInst>(I)) {
+    IsStore = true;
+    Alignment = 0;
+    Addr = RMW->getPointerOperand();
+  } else if (AtomicCmpXchgInst *Xchg = dyn_cast<AtomicCmpXchgInst>(I)) {
+    IsStore = true;
+    Alignment = 0;
+    Addr = Xchg->getPointerOperand();
+  } else
+    llvm_unreachable("Unsupported mem access type");
+
+  Type *OrigTy = cast<PointerType>(Addr->getType())->getElementType();
+  const uint32_t TypeSizeBytes = DL.getTypeStoreSizeInBits(OrigTy) / 8;
+  Value *OnAccessFunc = nullptr;
+  if (IsStore)
+    NumInstrumentedStores++;
+  else
+    NumInstrumentedLoads++;
+  int Idx = getMemoryAccessFuncIndex(Addr, DL);
+  if (Idx < 0) {
+    OnAccessFunc = IsStore ? EsanUnalignedStoreN : EsanUnalignedLoadN;
+    IRB.CreateCall(OnAccessFunc,
+                   {IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()),
+                    ConstantInt::get(IntptrTy, TypeSizeBytes)});
+  } else {
+    if (instrumentFastpath(I, DL, IsStore, Addr, Alignment)) {
+      NumFastpaths++;
+      return true;
+    }
+    if (Alignment == 0 || Alignment >= 8 || (Alignment % TypeSizeBytes) == 0)
+      OnAccessFunc = IsStore ? EsanAlignedStore[Idx] : EsanAlignedLoad[Idx];
+    else
+      OnAccessFunc = IsStore ? EsanUnalignedStore[Idx] : EsanUnalignedLoad[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(MemIntrinsic *MI) {
+  IRBuilder<> IRB(MI);
+  bool Res = false;
+  if (isa<MemSetInst>(MI)) {
+    IRB.CreateCall(
+        MemsetFn,
+        {IRB.CreatePointerCast(MI->getArgOperand(0), IRB.getInt8PtrTy()),
+         IRB.CreateIntCast(MI->getArgOperand(1), IRB.getInt32Ty(), false),
+         IRB.CreateIntCast(MI->getArgOperand(2), IntptrTy, false)});
+    MI->eraseFromParent();
+    Res = true;
+  } else if (isa<MemTransferInst>(MI)) {
+    IRB.CreateCall(
+        isa<MemCpyInst>(MI) ? MemcpyFn : MemmoveFn,
+        {IRB.CreatePointerCast(MI->getArgOperand(0), IRB.getInt8PtrTy()),
+         IRB.CreatePointerCast(MI->getArgOperand(1), IRB.getInt8PtrTy()),
+         IRB.CreateIntCast(MI->getArgOperand(2), IntptrTy, false)});
+    MI->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) {
+    // Irregular sizes do not have per-size call targets.
+    NumAccessesWithIrregularSize++;
+    return -1;
+  }
+  size_t Idx = countTrailingZeros(TypeSizeBytes);
+  assert(Idx < NumberOfAccessSizes);
+  return Idx;
+}
+
+bool EfficiencySanitizer::instrumentFastpath(Instruction *I,
+                                             const DataLayout &DL, bool IsStore,
+                                             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;
+}

llvm/trunk/lib/Transforms/Instrumentation/Instrumentation.cpp

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

llvm/trunk/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_load1(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_load2(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_load4(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_load8(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_load16(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_store1(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_store2(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_store4(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_store8(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_store16(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_load2(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_load4(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_load8(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_load16(i8* %0)
+; CHECK-NEXT:   %tmp1 = load i128, i128* %a, align 1
+; CHECK-NEXT:   ret i128 %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_store2(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_store4(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_store8(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_store16(i8* %0)
+; CHECK-NEXT:   store i128 1, i128* %a, align 1
+; CHECK-NEXT:   ret void
+}
+
+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
+; Unusual loads and stores:
+
+define x86_fp80 @loadUnalignedFP(x86_fp80* %a) {
+entry:
+  %tmp1 = load x86_fp80, x86_fp80* %a, align 1
+  ret x86_fp80 %tmp1
+; CHECK:        %0 = bitcast x86_fp80* %a to i8*
+; CHECK-NEXT:   call void @__esan_unaligned_loadN(i8* %0, i64 10)
+; CHECK-NEXT:   %tmp1 = load x86_fp80, x86_fp80* %a, align 1
+; CHECK-NEXT:   ret x86_fp80 %tmp1
+}
+
+define void @storeUnalignedFP(x86_fp80* %a) {
+entry:
+  store x86_fp80 0xK00000000000000000000, x86_fp80* %a, align 1
+  ret void
+; CHECK:        %0 = bitcast x86_fp80* %a to i8*
+; CHECK-NEXT:   call void @__esan_unaligned_storeN(i8* %0, i64 10)
+; CHECK-NEXT:   store x86_fp80 0xK00000000000000000000, x86_fp80* %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)