An Aliasing Validator/Sanitizer

[hfinkel]

Summary

As part of the conversation about the scoped-noalias metadata, our need for a validator / sanitizer for aliasing was heightened. Two use cases were discussed:

1. To validate the user's use of 'restrict' on pointers.
2. To validate LLVM's AA infrastructure.

This implementation is certainly not ready to be committed (although it is functional, and I've found AA bugs with it when self-hosting Clang with it enabled), but I'm posting it to start a conversation on what we want and how it should be implemented.

I originally wrote this in response to bugs appearing when I enabled the use of AA during code generation (and the current implementation is certainly biased toward that use case). There are two modes implemented:

1. A mode where instrumentation is inserted to check NoAlias results on load/store and store/store pairs. Checking "all" such pairs in a function is impractical for large functions, so the current implementation checks only such pairs that occur in between likely scheduling barriers. Also, it inserts the checks late (after almost all optimizations) because my use case was focused on bugs that appeared from using AA during codegen. The checks could certainly be inserted earlier as well. Compiling with -mllvm -codegen-validate-aa enables this.
2. A mode when uses of NoAlias results during instruction scheduling are recorded in a file. When compiling again later, this file can be read and only those specific pairs are instrumented to be checked. This has much lower overhead, but is also less sensitive (because instruction scheduling only uses AA when other methods fail to yield a definitive result and the result might be relevant to scheduling). Compiling with -mllvm -record-aa-sched-mi=SOME_DIRECTORY will cause the AA pairs used during instruction scheduling to be recorded and then compiling with -mllvm -codegen-validate-aa -mllvm -use-recorded-aa=SOME_DIRECTORY will cause the instrumentation to be inserted.

To focus more on user errors, we'd probably want the checks inserted earlier (prior to inlining), the checks to encode source-level locations (instead of or in addition to IR instructions), and to use the sanitizer runtimes to report errors (instead of manually building sprintf/write calls). Also, it currently has no test cases ;)

To get a feel for what this current implementation does:

$ cat /tmp/ta.c
attribute((noinline)) void foo(int * restrict a, int * restrict b) {

*b = *a;

}

int main() {

int a = 5;
foo(&a, &a);

}

$ clang -O3 -o /tmp/ta /tmp/ta.c -mllvm -codegen-validate-aa

$ /tmp/ta
ALIAS: /tmp/ta.c: foo: '%0 = load i32* %a, align 4, !tbaa !1' (in 'entry') and 'store i32 %0, i32* %b, align 4, !tbaa !1' (in 'entry'): [0x7fff55658a24 0x7fff55658a28) <-> [0x7fff55658a24 0x7fff55658a28)
Illegal instruction (core dumped)

Thanks in advance!

[hfinkel]

Ping. (Looking for feedback here... figuring out what and when is useful to check is going to require some discussion)

[atrick]

Hal,

I think both these validation modes will be extremely useful. The first (restrict validation) tests the user annotations. The second (AA validation) tests our AA implementation.

For AA validation we want to be able to recompile a potentially broken program with exactly the same optimization and inlining, at least up to the point where we insert instrumentation.

Your design looks good to me. It can be extended to validate AA across any codegen (or ISEL) pass, as long as memory operands are intact. Validating AA decisions from earlier passes, before the IR is frozen would require a different approach. (If the pass modifies IR while recording decisions we have a problem). To deal with that (in the future) we could use an instruction numbering analysis to identify pairs.

I don't have any conerns at the moment about your design or implementation.

[Eugene.Zelenko]

Looks like patch was not committed.

include/llvm/InitializePasses.h

 void initializeSampleProfileLoaderPass(PassRegistry&);
 void initializeBarrierNoopPass(PassRegistry&);
 void initializeBasicAliasAnalysisPass(PassRegistry&);
 void initializeCallGraphWrapperPassPass(PassRegistry &);
 void initializeBasicTTIPass(PassRegistry&);
 void initializeBlockExtractorPassPass(PassRegistry&);
 void initializeBlockFrequencyInfoPass(PassRegistry&);
 void initializeBoundsCheckingPass(PassRegistry&);
+void initializeValidateAAPass(PassRegistry&);
 void initializeBranchFolderPassPass(PassRegistry&);
 void initializeBranchProbabilityInfoPass(PassRegistry&);
 void initializeBreakCriticalEdgesPass(PassRegistry&);
 void initializeCallGraphPrinterPass(PassRegistry&);
 void initializeCallGraphViewerPass(PassRegistry&);
 void initializeCFGOnlyPrinterPass(PassRegistry&);
 void initializeCFGOnlyViewerPass(PassRegistry&);
 void initializeCFGPrinterPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createSingleLoopExtractorPass();
       (void) llvm::createStripSymbolsPass();
       (void) llvm::createStripNonDebugSymbolsPass();
       (void) llvm::createStripDeadDebugInfoPass();
       (void) llvm::createStripDeadPrototypesPass();
       (void) llvm::createTailCallEliminationPass();
       (void) llvm::createJumpThreadingPass();
       (void) llvm::createUnifyFunctionExitNodesPass();
+      (void) llvm::createValidateAAPass();
       (void) llvm::createInstCountPass();
       (void) llvm::createConstantHoistingPass();
       (void) llvm::createCodeGenPreparePass();
       (void) llvm::createEarlyCSEPass();
       (void) llvm::createGVNPass();
       (void) llvm::createMemCpyOptPass();
       (void) llvm::createLoopDeletionPass();
       (void) llvm::createPostDomTree();

include/llvm/Transforms/Instrumentation.h

return createDataFlowSanitizerPass(ABIListFile, getDFSanArgTLSPtrForJIT,
                                      getDFSanRetValTLSPtrForJIT);
 }
 #endif
 
 // BoundsChecking - This pass instruments the code to perform run-time bounds
 // checking on loads, stores, and other memory intrinsics.
 FunctionPass *createBoundsCheckingPass();
 
+// ValidateAA - This pass instruments the code to perform run-time validation
+// of alias-analysis query results.
+FunctionPass *createValidateAAPass();
+
 /// createDebugIRPass - Enable interactive stepping through LLVM IR in LLDB (or
 ///                     GDB) and generate a file with the LLVM IR to be
 ///                     displayed in the debugger.
 ///
 /// Existing debug metadata is preserved (but may be modified) in order to allow
 /// accessing variables in the original source. The line table and file
 /// information is modified to correspond to the lines in the LLVM IR. If
 /// Filename and Directory are empty, a file name is generated based on existing

lib/CodeGen/Passes.cpp

 #include "llvm/IR/Verifier.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/PassManager.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Target/TargetLowering.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
+#include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Scalar.h"
 
 using namespace llvm;
 
 static cl::opt<bool> DisablePostRA("disable-post-ra", cl::Hidden,
     cl::desc("Disable Post Regalloc"));
 static cl::opt<bool> DisableBranchFold("disable-branch-fold", cl::Hidden,
     cl::desc("Disable branch folding"));

 static cl::opt<bool> DisableCopyProp("disable-copyprop", cl::Hidden,
     cl::desc("Disable Copy Propagation pass"));
 static cl::opt<bool> PrintLSR("print-lsr-output", cl::Hidden,
     cl::desc("Print LLVM IR produced by the loop-reduce pass"));
 static cl::opt<bool> PrintISelInput("print-isel-input", cl::Hidden,
     cl::desc("Print LLVM IR input to isel pass"));
 static cl::opt<bool> PrintGCInfo("print-gc", cl::Hidden,
     cl::desc("Dump garbage collector data"));
+static cl::opt<bool> ValidateAA("codegen-validate-aa", cl::Hidden,
+    cl::desc("Instrument code to validate AA queries"));
 static cl::opt<bool> VerifyMachineCode("verify-machineinstrs", cl::Hidden,
     cl::desc("Verify generated machine code"),
     cl::init(getenv("LLVM_VERIFY_MACHINEINSTRS")!=nullptr));
 static cl::opt<std::string>
 PrintMachineInstrs("print-machineinstrs", cl::ValueOptional,
                    cl::desc("Print machine instrs"),
                    cl::value_desc("pass-name"), cl::init("option-unspecified"));
 
+
 // Temporary option to allow experimenting with MachineScheduler as a post-RA
 // scheduler. Targets can "properly" enable this with
 // substitutePass(&PostRASchedulerID, &PostMachineSchedulerID); Ideally it
 // wouldn't be part of the standard pass pipeline, and the target would just add
 // a PostRA scheduling pass wherever it wants.
 static cl::opt<bool> MISchedPostRA("misched-postra", cl::Hidden,
   cl::desc("Run MachineScheduler post regalloc (independent of preRA sched)"));
 
void TargetPassConfig::addIRPasses() {
   addPass(createGCLoweringPass());
 
   // Make sure that no unreachable blocks are instruction selected.
   addPass(createUnreachableBlockEliminationPass());
 
   // Prepare expensive constants for SelectionDAG.
   if (getOptLevel() != CodeGenOpt::None && !DisableConstantHoisting)
     addPass(createConstantHoistingPass());
+
+  if (ValidateAA)
+    addPass(createValidateAAPass());
 }
 
 /// Turn exception handling constructs into something the code generators can
 /// handle.
 void TargetPassConfig::addPassesToHandleExceptions() {
   switch (TM->getMCAsmInfo()->getExceptionHandlingType()) {
   case ExceptionHandling::SjLj:
     // SjLj piggy-backs on dwarf for this bit. The cleanups done apply to both

lib/CodeGen/ScheduleDAGInstrs.cpp

 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/PseudoSourceValue.h"
 #include "llvm/CodeGen/RegisterPressure.h"
 #include "llvm/CodeGen/ScheduleDFS.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/MC/MCInstrItineraries.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Format.h"
+#include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include <queue>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "misched"
 
 static cl::opt<bool> EnableAASchedMI("enable-aa-sched-mi", cl::Hidden,
     cl::ZeroOrMore, cl::init(false),
     cl::desc("Enable use of AA during MI GAD construction"));
 
 static cl::opt<bool> UseTBAA("use-tbaa-in-sched-mi", cl::Hidden,
     cl::init(true), cl::desc("Enable use of TBAA during MI GAD construction"));
 
+static cl::opt<std::string> RecordAA("record-aa-sched-mi", cl::Hidden,
+    cl::desc("A directory into which AA queries should be recorded"));
+static raw_fd_ostream *AARecorderOuts = 0;
+
 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineFunction &mf,
                                      const MachineLoopInfo &mli,
                                      const MachineDominatorTree &mdt,
                                      bool IsPostRAFlag,
                                      bool RemoveKillFlags,
                                      LiveIntervals *lis)
   : ScheduleDAG(mf), MLI(mli), MDT(mdt), MFI(mf.getFrameInfo()), LIS(lis),
     IsPostRA(IsPostRAFlag), RemoveKillFlags(RemoveKillFlags),
static bool MIsNeedChainEdge(AliasAnalysis *AA, const MachineFrameInfo *MFI,
   int64_t Overlapb = MMOb->getSize() + MMOb->getOffset() - MinOffset;
 
   AliasAnalysis::AliasResult AAResult = AA->alias(
       AliasAnalysis::Location(MMOa->getValue(), Overlapa,
                               UseTBAA ? MMOa->getTBAAInfo() : nullptr),
       AliasAnalysis::Location(MMOb->getValue(), Overlapb,
                               UseTBAA ? MMOb->getTBAAInfo() : nullptr));
 
+  if (AAResult == AliasAnalysis::NoAlias && !RecordAA.empty()) {
+    const Instruction *I1 = dyn_cast<Instruction>(MMOa->getValue()),
+                      *I2 = dyn_cast<Instruction>(MMOb->getValue());
+    if (I1 && I2) {
+      if (!AARecorderOuts) {
+        std::string MID = I1->getParent()->getParent()->
+                            getParent()->getModuleIdentifier();
+        std::replace(MID.begin(), MID.end(), '/', '_');
+
+        SmallString<1024> Filename;
+        llvm::sys::path::append(Filename, RecordAA, MID);
+        std::string ErrorInfo;
+        AARecorderOuts = new raw_fd_ostream(Filename.c_str(), ErrorInfo,
+                                            sys::fs::F_None);
+      }
+
+      (*AARecorderOuts) << I1->getParent()->getParent()->getName() << "\n";
+      I1->print(*AARecorderOuts);
+      (*AARecorderOuts) << "\n    " << Overlapa << "\n";
+      I2->print(*AARecorderOuts);
+      (*AARecorderOuts) << "\n    " << Overlapb << "\n\n";
+    }
+  }
+
   return (AAResult != AliasAnalysis::NoAlias);
 }
 
 /// This recursive function iterates over chain deps of SUb looking for
 /// "latest" node that needs a chain edge to SUa.
 static unsigned
 iterateChainSucc(AliasAnalysis *AA, const MachineFrameInfo *MFI,
                  SUnit *SUa, SUnit *SUb, SUnit *ExitSU, unsigned *Depth,
void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA,
   }
   if (DbgMI)
     FirstDbgValue = DbgMI;
 
   Defs.clear();
   Uses.clear();
   VRegDefs.clear();
   PendingLoads.clear();
+
+  if (AARecorderOuts)
+    AARecorderOuts->flush();
 }
 
 /// \brief Initialize register live-range state for updating kills.
 void ScheduleDAGInstrs::startBlockForKills(MachineBasicBlock *BB) {
   // Start with no live registers.
   LiveRegs.reset();
 
   // Examine the live-in regs of all successors.

lib/Transforms/Scalar/CMakeLists.txt

add_llvm_library(LLVMScalarOpts
   Scalar.cpp
   ScalarReplAggregates.cpp
   Scalarizer.cpp
   SeparateConstOffsetFromGEP.cpp
   SimplifyCFGPass.cpp
   Sink.cpp
   StructurizeCFG.cpp
   TailRecursionElimination.cpp
+  ValidateAA.cpp
   )
 
 add_dependencies(LLVMScalarOpts intrinsics_gen)

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeSROA_DTPass(Registry);
   initializeSROA_SSAUpPass(Registry);
   initializeCFGSimplifyPassPass(Registry);
   initializeStructurizeCFGPass(Registry);
   initializeSinkingPass(Registry);
   initializeTailCallElimPass(Registry);
   initializeSeparateConstOffsetFromGEPPass(Registry);
   initializeLoadCombinePass(Registry);
+  initializeValidateAAPass(Registry);
 }
 
 void LLVMInitializeScalarOpts(LLVMPassRegistryRef R) {
   initializeScalarOpts(*unwrap(R));
 }
 
 void LLVMAddAggressiveDCEPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createAggressiveDCEPass());

lib/Transforms/Scalar/ValidateAA.cpp

+//===- ValidateAA.cpp - Instrumentation for run-time AA validation --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a pass that instruments the code to perform run-time
+// alias analysis validation on loads, stores, and other memory intrinsics.
+//
+//===----------------------------------------------------------------------===//
+
+#define DEBUG_TYPE "validate-aa"
+#include "llvm/Transforms/Instrumentation.h"
+#include "llvm/Transforms/Utils/BuildLibCalls.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/Analysis/TargetFolder.h"
+#include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Intrinsics.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/LineIterator.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Target/TargetLibraryInfo.h"
+using namespace llvm;
+
+static cl::opt<bool> SingleTrapBB("validate-aa-single-trap",
+                                  cl::desc("Use one trap block per function"));
+
+STATISTIC(ChecksAdded, "AA Validation checks added");
+STATISTIC(ChecksSkipped, "AA Validation checks skipped");
+
+static cl::opt<std::string> RecordedAA("use-recorded-aa", cl::Hidden,
+    cl::desc("A directory into which AA queries were recorded"));
+
+namespace {
+  struct ValidateAA : public FunctionPass {
+    static char ID;
+
+    ValidateAA() : FunctionPass(ID) {
+      initializeValidateAAPass(*PassRegistry::getPassRegistry());
+    }
+
+    virtual bool runOnFunction(Function &F);
+
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+      AU.addRequired<DataLayoutPass>();
+      AU.addRequired<TargetLibraryInfo>();
+      AU.addRequired<AliasAnalysis>();
+      AU.addRequired<DominatorTreeWrapperPass>();
+    }
+
+  private:
+    const DataLayout *TD;
+    const TargetLibraryInfo *TLI;
+    AliasAnalysis *AA;
+    DominatorTree *DT;
+    IRBuilder<> *Builder;
+    BasicBlock *TrapBB;
+
+    BasicBlock *getTrapBB(Instruction *Inst, std::string *Err = 0,
+                          Value *FirstStart = 0, Value *FirstEnd = 0,
+                          Value *SecondStart = 0, Value *SecondEnd = 0);
+    void emitBranchToTrap(Value *Cmp = 0, std::string *Err = 0,
+                          Value *FirstStart = 0, Value *FirstEnd = 0,
+                          Value *SecondStart = 0, Value *SecondEnd = 0);
+    bool instrument(Instruction *First, Instruction *Second,
+                    std::string *Err = 0,
+                    uint64_t FirstSize = 0, uint64_t SecondSize = 0);
+
+    bool runLoadStores(Function &F);
+    bool runRecorded(Function &F);
+ };
+}
+
+char ValidateAA::ID = 0;
+INITIALIZE_PASS_BEGIN(ValidateAA, "validate-aa", "Run-time AA validation",
+                false, false)
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
+INITIALIZE_PASS_END(ValidateAA, "validate-aa", "Run-time AA validation",
+                false, false)
+
+
+/// getTrapBB - create a basic block that traps. All overflowing conditions
+/// branch to this block. There's only one trap block per function.
+BasicBlock *ValidateAA::getTrapBB(Instruction *Inst, std::string *Err,
+                                  Value *FirstStart, Value *FirstEnd,
+                                  Value *SecondStart, Value *SecondEnd) {
+  if (TrapBB && SingleTrapBB)
+    return TrapBB;
+
+  Function *Fn = Inst->getParent()->getParent();
+  IRBuilder<>::InsertPointGuard Guard(*Builder);
+  TrapBB = BasicBlock::Create(Fn->getContext(), "trap", Fn);
+  Builder->SetInsertPoint(TrapBB);
+
+  Value *F;
+  if (Err && !SingleTrapBB && TLI->has(LibFunc::write) &&
+      TLI->has(LibFunc::sprintf) && TLI->has(LibFunc::strlen)) {
+    Module *M = Fn->getParent();
+
+    Value *ErrStr = Builder->CreateGlobalString(*Err);
+    ErrStr = CastToCStr(ErrStr, *Builder);
+
+    AttributeSet AS[3];
+    AS[0] = AttributeSet::get(M->getContext(), 1, Attribute::NoCapture);
+    Attribute::AttrKind AVs[2] = { Attribute::ReadOnly, Attribute::NoCapture };
+    AS[1] = AttributeSet::get(M->getContext(), 2,
+                            ArrayRef<Attribute::AttrKind>(AVs, 2));
+    AS[2] = AttributeSet::get(M->getContext(), AttributeSet::FunctionIndex,
+                              Attribute::NoUnwind);
+
+    const size_t ExtraSize = 64; /* 4 * 16 */;
+    Value *FullErrStr =
+      Builder->CreateAlloca(Builder->getInt8Ty(),
+                            Builder->getInt32(Err->size() + ExtraSize));
+   
+
+    Type *Types[2] = { Builder->getInt8PtrTy(), Builder->getInt8PtrTy() };
+    FunctionType *SPrintfTy = FunctionType::get(Builder->getInt32Ty(),
+                                                Types, true);
+    StringRef SPrintfName = TLI->getName(LibFunc::sprintf);
+    F = M->getOrInsertFunction(SPrintfName, SPrintfTy,
+                               AttributeSet::get(M->getContext(), AS));
+
+    Value *Params[6] = { FullErrStr, ErrStr,
+                         FirstStart, FirstEnd,
+                         SecondStart, SecondEnd };
+    CallInst *CI = Builder->CreateCall(F, Params);
+
+    if (const Function *WFn = dyn_cast<Function>(F->stripPointerCasts()))
+      CI->setCallingConv(WFn->getCallingConv());
+
+    AttributeSet AS2[2];
+    AS2[0] = AttributeSet::get(M->getContext(), 2, Attribute::NoCapture);
+    AS2[1] = AttributeSet::get(M->getContext(), AttributeSet::FunctionIndex,
+                              Attribute::NoUnwind);
+    
+    StringRef WriteName = TLI->getName(LibFunc::write);
+    F = M->getOrInsertFunction(WriteName,
+                               AttributeSet::get(M->getContext(), AS2),
+                               TD->getIntPtrType(M->getContext()),
+                               Builder->getInt32Ty(),
+                               Builder->getInt8PtrTy(),
+                               TD->getIntPtrType(M->getContext()), NULL);
+
+    Value *ErrSize = EmitStrLen(FullErrStr, *Builder, TD, TLI);
+    ErrSize =
+      Builder->CreateNUWAdd(ErrSize, ConstantInt::get(ErrSize->getType(), 1));
+
+    CI = Builder->CreateCall3(F, Builder->getInt32(2),
+                              FullErrStr, ErrSize);
+
+    if (const Function *WFn = dyn_cast<Function>(F->stripPointerCasts()))
+      CI->setCallingConv(WFn->getCallingConv());
+  }
+
+  F = Intrinsic::getDeclaration(Fn->getParent(), Intrinsic::trap);
+  CallInst *TrapCall = Builder->CreateCall(F);
+  TrapCall->setDoesNotReturn();
+  TrapCall->setDoesNotThrow();
+  TrapCall->setDebugLoc(Inst->getDebugLoc());
+  Builder->CreateUnreachable();
+
+  return TrapBB;
+}
+
+
+/// emitBranchToTrap - emit a branch instruction to a trap block.
+/// If Cmp is non-null, perform a jump only if its value evaluates to true.
+void ValidateAA::emitBranchToTrap(Value *Cmp, std::string *Err,
+                                  Value *FirstStart, Value *FirstEnd,
+                                  Value *SecondStart, Value *SecondEnd) {
+  // check if the comparison is always false
+  ConstantInt *C = dyn_cast_or_null<ConstantInt>(Cmp);
+  if (C) {
+    ++ChecksSkipped;
+    if (!C->getZExtValue())
+      return;
+    else
+      Cmp = 0; // unconditional branch
+  }
+  ++ChecksAdded;
+
+  Instruction *Inst = Builder->GetInsertPoint();
+  BasicBlock *OldBB = Inst->getParent();
+  BasicBlock *Cont = OldBB->splitBasicBlock(Inst);
+  OldBB->getTerminator()->eraseFromParent();
+
+  if (Cmp)
+    BranchInst::Create(getTrapBB(Inst, Err, FirstStart, FirstEnd,
+                                            SecondStart, SecondEnd),
+                       Cont, Cmp, OldBB);
+  else
+    BranchInst::Create(getTrapBB(Inst, Err, FirstStart, FirstEnd,
+                                            SecondStart, SecondEnd), OldBB);
+}
+
+
+/// instrument - adds run-time AA validation checks to memory accessing instructions.
+/// Of the two arguments, the first one dominates the second.
+bool ValidateAA::instrument(Instruction *First, Instruction *Second,
+                            std::string *Err,
+                            uint64_t FirstSize, uint64_t SecondSize) {
+  Value *FirstPtr, *SecondPtr;
+  if (isa<LoadInst>(First) || isa<StoreInst>(First))
+    FirstPtr =
+      isa<LoadInst>(First) ? cast<LoadInst>(First)->getPointerOperand() :
+                             cast<StoreInst>(First)->getPointerOperand();
+  else
+    FirstPtr = First;
+
+  if (isa<LoadInst>(Second) || isa<StoreInst>(Second))
+    SecondPtr =
+      isa<LoadInst>(Second) ? cast<LoadInst>(Second)->getPointerOperand() :
+                              cast<StoreInst>(Second)->getPointerOperand();
+  else
+    SecondPtr = Second;
+
+  if (!FirstSize)
+    FirstSize =
+      TD->getTypeStoreSize(FirstPtr->getType()->getPointerElementType());
+  if (!SecondSize)
+    SecondSize =
+      TD->getTypeStoreSize(SecondPtr->getType()->getPointerElementType());
+
+  if (isa<LoadInst>(Second) || isa<StoreInst>(Second)) {
+    Builder->SetInsertPoint(Second);
+  } else {
+    BasicBlock::iterator IP = std::next(BasicBlock::iterator(Second));
+    if (IP == Second->getParent()->end())
+      Builder->SetInsertPoint(Second->getParent());
+    else
+      Builder->SetInsertPoint(IP);
+  }
+
+  Value *FirstStart =
+    Builder->CreatePtrToInt(FirstPtr, Builder->getInt64Ty());
+  Value *SecondStart =
+    Builder->CreatePtrToInt(SecondPtr, Builder->getInt64Ty());
+
+  Value *FirstEnd =
+    Builder->CreateNUWAdd(FirstStart, Builder->getInt64(FirstSize));
+  Value *SecondEnd =
+    Builder->CreateNUWAdd(SecondStart, Builder->getInt64(SecondSize));
+
+  Value *Overlap = Builder->CreateAnd(
+    Builder->CreateICmpUGT(FirstEnd, SecondStart),
+    Builder->CreateICmpULT(FirstStart, SecondEnd)
+  );
+
+  emitBranchToTrap(Overlap, Err, FirstStart, FirstEnd, SecondStart, SecondEnd);
+
+  return true;
+}
+
+namespace {
+  // Note that we form the error string here so that it refers to the original
+  // (non-instrumented) BB names.
+  struct InstructionPair {
+    InstructionPair() : First(0), Second(0) {}
+    InstructionPair(Instruction *F, Instruction *S)
+      : First(F), Second(S) {
+      std::string FirstStr, SecondStr;
+      raw_string_ostream FirstOS(FirstStr), SecondOS(SecondStr);
+      First->print(FirstOS);
+      Second->print(SecondOS);
+
+      // The printed instructions often start with spaces (which we don't want).
+      while (FirstStr[0] == ' ')
+        FirstStr.erase(FirstStr.begin());
+      while (SecondStr[0] == ' ')
+        SecondStr.erase(SecondStr.begin());
+
+      // We need to escape all existing '%' characters for use with printf.
+      for (size_t p = 0; (p = FirstStr.find("%", p)) != std::string::npos;
+           p += 2)
+        FirstStr.replace(p, 1, "%%");
+      for (size_t p = 0; (p = SecondStr.find("%", p)) != std::string::npos;
+           p += 2)
+        SecondStr.replace(p, 1, "%%");
+
+      Err = ("ALIAS: " +
+        First->getParent()->getParent()->getParent()->
+          getModuleIdentifier() + ": " +
+        First->getParent()->getParent()->getName() + ": '" +
+        FirstStr + "' (in '" + First->getParent()->getName() +
+        "') and '" +
+        SecondStr + "' (in '" + Second->getParent()->getName() +
+        "'): [%p %p) <-> [%p %p)\n").str();
+    }
+
+    Instruction *First, *Second;
+    std::string Err;
+  };
+
+  struct SizedInstructionPair : InstructionPair {
+    SizedInstructionPair() : FirstSize(0), SecondSize(0) {}
+    SizedInstructionPair(Instruction *F, Instruction *S,
+                         uint64_t FSize, uint64_t SSize)
+      : InstructionPair(F, S), FirstSize(FSize), SecondSize(SSize) {}
+    uint64_t FirstSize, SecondSize;
+  };
+}
+
+bool ValidateAA::runLoadStores(Function &F) {
+  bool MadeChange = false;
+
+  // We cannot validate all load/store and store/store NoAlias results, that
+  // would take too long (even restricted to one basic block in non-trivial
+  // cases). So instead, we work backward until we reach some likely relevant
+  // scheduling barrier.
+
+  std::vector<InstructionPair> Pairs;
+
+  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
+    Instruction *MemI = &*I;
+    if (!isa<LoadInst>(MemI) && !isa<StoreInst>(MemI))
+      continue;
+
+    AliasAnalysis::Location MemILoc = isa<LoadInst>(MemI) ?
+      AA->getLocation(cast<LoadInst>(MemI)) :
+      AA->getLocation(cast<StoreInst>(MemI));
+
+    Instruction *Last;
+    if (BasicBlock::iterator(MemI) != MemI->getParent()->begin())
+      Last = std::prev(BasicBlock::iterator(MemI));
+    else if (BasicBlock *PredBB = MemI->getParent()->getUniquePredecessor())
+      Last = PredBB->getTerminator();
+    else
+      continue;
+
+    // Walk backward, through the parent block and any unique predecessors (as
+    // they might be merged at the MI level).
+    bool Done = false;
+    while (!Done) {
+      for (BasicBlock::reverse_iterator
+           J(std::next(BasicBlock::iterator(Last))),
+           JE = Last->getParent()->rend(); J != JE && !Done; ++J) {
+        if (CallSite CS = cast<Value>(&*J)) {
+          AliasAnalysis::ModRefResult MRR = AA->getModRefInfo(CS, MemILoc);
+          if ((isa<LoadInst>(MemI) && (MRR & AliasAnalysis::Mod)) ||
+              (isa<StoreInst>(MemI) && MRR)) {
+            Done = true;
+            break;
+          }
+        }
+
+        if (!isa<LoadInst>(*J) && !isa<StoreInst>(*J))
+          continue;
+        if (isa<LoadInst>(MemI) && isa<LoadInst>(*J))
+          continue;
+
+        if (AA->alias(MemILoc,
+                     isa<LoadInst>(&*J) ?
+                     AA->getLocation(cast<LoadInst>(&*J)) :
+                     AA->getLocation(cast<StoreInst>(&*J))) ==
+            AliasAnalysis::NoAlias) {
+          Pairs.push_back(InstructionPair(&*J, MemI)); 
+        } else {
+          Done = true;
+          break;
+        }
+      }
+
+      if (!Done) {
+        if (BasicBlock *PredBB = Last->getParent()->getUniquePredecessor())
+          Last = PredBB->getTerminator();
+        else
+          Done = true;
+      }
+    }
+  }
+
+  if (Pairs.empty())
+    return MadeChange;
+
+  MadeChange = true;
+
+  for (unsigned i = 0, ie = Pairs.size(); i != ie; ++i)
+    instrument(Pairs[i].First, Pairs[i].Second, &Pairs[i].Err);    
+
+  return MadeChange;
+}
+
+bool ValidateAA::runRecorded(Function &F) {
+  bool MadeChange = false;
+
+  std::string MID = F.getParent()->getModuleIdentifier();
+  std::replace(MID.begin(), MID.end(), '/', '_');
+
+  SmallString<1024> Filename;
+  llvm::sys::path::append(Filename, RecordedAA, MID);
+
+  ErrorOr<std::unique_ptr<MemoryBuffer>> File =
+    MemoryBuffer::getFile(Filename.str());
+  if (File.getError())
+    return MadeChange;
+ 
+  StringMap<Instruction *> Pointers;
+  for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
+    if (I->getType()->isPointerTy()) {
+      std::string PtrStr;
+      raw_string_ostream PtrOS(PtrStr);
+      I->print(PtrOS);
+      Pointers[PtrStr] = &*I;
+    }
+
+  std::vector<SizedInstructionPair> Pairs;
+
+  for (line_iterator LI(*File.get()); !LI.is_at_end(); ++LI) {
+    std::string FuncName = *LI;
+    if ((++LI).is_at_end())
+      break;
+
+    std::string FirstStr = *LI;
+    if ((++LI).is_at_end())
+      break;
+    std::string FirstSizeStr = *LI;
+    if ((++LI).is_at_end())
+      break;
+
+    std::string SecondStr = *LI;
+    if ((++LI).is_at_end())
+      break;
+    std::string SecondSizeStr = *LI;
+    if ((++LI).is_at_end())
+      break;
+
+    if (FuncName != F.getName())
+      continue;
+
+    StringMap<Instruction *>::iterator II = Pointers.find(FirstStr);
+    if (II == Pointers.end())
+      continue;
+    Instruction *First = II->getValue();
+
+    II = Pointers.find(SecondStr);
+    if (II == Pointers.end())
+      continue;
+    Instruction *Second = II->getValue();
+
+    long FirstSize = std::atol(FirstSizeStr.c_str());
+    long SecondSize = std::atol(SecondSizeStr.c_str());
+
+    if (DT->dominates(First, Second)) {
+      Pairs.push_back(SizedInstructionPair(First, Second,
+                                           FirstSize, SecondSize));
+    } else if (DT->dominates(Second, First)) {
+      Pairs.push_back(SizedInstructionPair(Second, First,
+                                           SecondSize, FirstSize));
+    }
+  }
+
+  if (Pairs.empty())
+    return MadeChange;
+
+  MadeChange = true;
+
+  for (unsigned i = 0, ie = Pairs.size(); i != ie; ++i)
+    instrument(Pairs[i].First, Pairs[i].Second, &Pairs[i].Err,
+               Pairs[i].FirstSize, Pairs[i].SecondSize);
+
+  return MadeChange;
+}
+
+bool ValidateAA::runOnFunction(Function &F) {
+  TD = &getAnalysis<DataLayoutPass>().getDataLayout();
+  TLI = &getAnalysis<TargetLibraryInfo>();
+  AA = &getAnalysis<AliasAnalysis>();
+  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+
+  TrapBB = 0;
+  IRBuilder<> TheBuilder(F.getContext());
+  Builder = &TheBuilder;
+
+  if (RecordedAA.empty())
+    return runLoadStores(F);
+
+  return runRecorded(F);
+}
+
+FunctionPass *llvm::createValidateAAPass() {
+  return new ValidateAA();
+}