lib/Transforms/Instrumentation/DataFlowSanitizer.cpp

   1 //===-- DataFlowSanitizer.cpp - dynamic data flow analysis ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 /// \file
  10 /// This file is a part of DataFlowSanitizer, a generalised dynamic data flow
  11 /// analysis.
  12 ///
  13 /// Unlike other Sanitizer tools, this tool is not designed to detect a specific
  14 /// class of bugs on its own.  Instead, it provides a generic dynamic data flow
  15 /// analysis framework to be used by clients to help detect application-specific
  16 /// issues within their own code.
  17 ///
  18 /// The analysis is based on automatic propagation of data flow labels (also
  19 /// known as taint labels) through a program as it performs computation.  Each
  20 /// byte of application memory is backed by two bytes of shadow memory which
  21 /// hold the label.  On Linux/x86_64, memory is laid out as follows:
  22 ///
  23 /// +--------------------+ 0x800000000000 (top of memory)
  24 /// | application memory |
  25 /// +--------------------+ 0x700000008000 (kAppAddr)
  26 /// |                    |
  27 /// |       unused       |
  28 /// |                    |
  29 /// +--------------------+ 0x200200000000 (kUnusedAddr)
  30 /// |    union table     |
  31 /// +--------------------+ 0x200000000000 (kUnionTableAddr)
  32 /// |   shadow memory    |
  33 /// +--------------------+ 0x000000010000 (kShadowAddr)
  34 /// | reserved by kernel |
  35 /// +--------------------+ 0x000000000000
  36 ///
  37 /// To derive a shadow memory address from an application memory address,
  38 /// bits 44-46 are cleared to bring the address into the range
  39 /// [0x000000008000,0x100000000000).  Then the address is shifted left by 1 to
  40 /// account for the double byte representation of shadow labels and move the
  41 /// address into the shadow memory range.  See the function
  42 /// DataFlowSanitizer::getShadowAddress below.
  43 ///
  44 /// For more information, please refer to the design document:
  45 /// http://clang.llvm.org/docs/DataFlowSanitizerDesign.html
  46
  47 #include "llvm/Transforms/Instrumentation.h"
  48 #include "llvm/ADT/DenseMap.h"
  49 #include "llvm/ADT/DenseSet.h"
  50 #include "llvm/ADT/DepthFirstIterator.h"
  51 #include "llvm/ADT/StringExtras.h"
  52 #include "llvm/Analysis/ValueTracking.h"
  53 #include "llvm/IR/Dominators.h"
  54 #include "llvm/IR/DebugInfo.h"
  55 #include "llvm/IR/IRBuilder.h"
  56 #include "llvm/IR/InlineAsm.h"
  57 #include "llvm/IR/InstVisitor.h"
  58 #include "llvm/IR/LLVMContext.h"
  59 #include "llvm/IR/MDBuilder.h"
  60 #include "llvm/IR/Type.h"
  61 #include "llvm/IR/Value.h"
  62 #include "llvm/Pass.h"
  63 #include "llvm/Support/CommandLine.h"
  64 #include "llvm/Support/SpecialCaseList.h"
  65 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  66 #include "llvm/Transforms/Utils/Local.h"
  67 #include <algorithm>
  68 #include <iterator>
  69 #include <set>
  70 #include <utility>
  71
  72 using namespace llvm;
  73
  74 // The -dfsan-preserve-alignment flag controls whether this pass assumes that
  75 // alignment requirements provided by the input IR are correct.  For example,
  76 // if the input IR contains a load with alignment 8, this flag will cause
  77 // the shadow load to have alignment 16.  This flag is disabled by default as
  78 // we have unfortunately encountered too much code (including Clang itself;
  79 // see PR14291) which performs misaligned access.
  80 static cl::opt<bool> ClPreserveAlignment(
  81     "dfsan-preserve-alignment",
  82     cl::desc("respect alignment requirements provided by input IR"), cl::Hidden,
  83     cl::init(false));
  84
  85 // The ABI list file controls how shadow parameters are passed.  The pass treats
  86 // every function labelled "uninstrumented" in the ABI list file as conforming
  87 // to the "native" (i.e. unsanitized) ABI.  Unless the ABI list contains
  88 // additional annotations for those functions, a call to one of those functions
  89 // will produce a warning message, as the labelling behaviour of the function is
  90 // unknown.  The other supported annotations are "functional" and "discard",
  91 // which are described below under DataFlowSanitizer::WrapperKind.
  92 static cl::opt<std::string> ClABIListFile(
  93     "dfsan-abilist",
  94     cl::desc("File listing native ABI functions and how the pass treats them"),
  95     cl::Hidden);
  96
  97 // Controls whether the pass uses IA_Args or IA_TLS as the ABI for instrumented
  98 // functions (see DataFlowSanitizer::InstrumentedABI below).
  99 static cl::opt<bool> ClArgsABI(
 100     "dfsan-args-abi",
 101     cl::desc("Use the argument ABI rather than the TLS ABI"),
 102     cl::Hidden);
 103
 104 // Controls whether the pass includes or ignores the labels of pointers in load
 105 // instructions.
 106 static cl::opt<bool> ClCombinePointerLabelsOnLoad(
 107     "dfsan-combine-pointer-labels-on-load",
 108     cl::desc("Combine the label of the pointer with the label of the data when "
 109              "loading from memory."),
 110     cl::Hidden, cl::init(true));
 111
 112 // Controls whether the pass includes or ignores the labels of pointers in
 113 // stores instructions.
 114 static cl::opt<bool> ClCombinePointerLabelsOnStore(
 115     "dfsan-combine-pointer-labels-on-store",
 116     cl::desc("Combine the label of the pointer with the label of the data when "
 117              "storing in memory."),
 118     cl::Hidden, cl::init(false));
 119
 120 static cl::opt<bool> ClDebugNonzeroLabels(
 121     "dfsan-debug-nonzero-labels",
 122     cl::desc("Insert calls to __dfsan_nonzero_label on observing a parameter, "
 123              "load or return with a nonzero label"),
 124     cl::Hidden);
 125
 126 namespace {
 127
 128 StringRef GetGlobalTypeString(const GlobalValue &G) {
 129   // Types of GlobalVariables are always pointer types.
 130   Type *GType = G.getType()->getElementType();
 131   // For now we support blacklisting struct types only.
 132   if (StructType *SGType = dyn_cast<StructType>(GType)) {
 133     if (!SGType->isLiteral())
 134       return SGType->getName();
 135   }
 136   return "<unknown type>";
 137 }
 138
 139 class DFSanABIList {
 140   std::unique_ptr<SpecialCaseList> SCL;
 141
 142  public:
 143   DFSanABIList(std::unique_ptr<SpecialCaseList> SCL) : SCL(std::move(SCL)) {}
 144
 145   /// Returns whether either this function or its source file are listed in the
 146   /// given category.
 147   bool isIn(const Function &F, StringRef Category) const {
 148     return isIn(*F.getParent(), Category) ||
 149            SCL->inSection("fun", F.getName(), Category);
 150   }
 151
 152   /// Returns whether this global alias is listed in the given category.
 153   ///
 154   /// If GA aliases a function, the alias's name is matched as a function name
 155   /// would be.  Similarly, aliases of globals are matched like globals.
 156   bool isIn(const GlobalAlias &GA, StringRef Category) const {
 157     if (isIn(*GA.getParent(), Category))
 158       return true;
 159
 160     if (isa<FunctionType>(GA.getType()->getElementType()))
 161       return SCL->inSection("fun", GA.getName(), Category);
 162
 163     return SCL->inSection("global", GA.getName(), Category) ||
 164            SCL->inSection("type", GetGlobalTypeString(GA), Category);
 165   }
 166
 167   /// Returns whether this module is listed in the given category.
 168   bool isIn(const Module &M, StringRef Category) const {
 169     return SCL->inSection("src", M.getModuleIdentifier(), Category);
 170   }
 171 };
 172
 173 class DataFlowSanitizer : public ModulePass {
 174   friend struct DFSanFunction;
 175   friend class DFSanVisitor;
 176
 177   enum {
 178     ShadowWidth = 16
 179   };
 180
 181   /// Which ABI should be used for instrumented functions?
 182   enum InstrumentedABI {
 183     /// Argument and return value labels are passed through additional
 184     /// arguments and by modifying the return type.
 185     IA_Args,
 186
 187     /// Argument and return value labels are passed through TLS variables
 188     /// __dfsan_arg_tls and __dfsan_retval_tls.
 189     IA_TLS
 190   };
 191
 192   /// How should calls to uninstrumented functions be handled?
 193   enum WrapperKind {
 194     /// This function is present in an uninstrumented form but we don't know
 195     /// how it should be handled.  Print a warning and call the function anyway.
 196     /// Don't label the return value.
 197     WK_Warning,
 198
 199     /// This function does not write to (user-accessible) memory, and its return
 200     /// value is unlabelled.
 201     WK_Discard,
 202
 203     /// This function does not write to (user-accessible) memory, and the label
 204     /// of its return value is the union of the label of its arguments.
 205     WK_Functional,
 206
 207     /// Instead of calling the function, a custom wrapper __dfsw_F is called,
 208     /// where F is the name of the function.  This function may wrap the
 209     /// original function or provide its own implementation.  This is similar to
 210     /// the IA_Args ABI, except that IA_Args uses a struct return type to
 211     /// pass the return value shadow in a register, while WK_Custom uses an
 212     /// extra pointer argument to return the shadow.  This allows the wrapped
 213     /// form of the function type to be expressed in C.
 214     WK_Custom
 215   };
 216
 217   const DataLayout *DL;
 218   Module *Mod;
 219   LLVMContext *Ctx;
 220   IntegerType *ShadowTy;
 221   PointerType *ShadowPtrTy;
 222   IntegerType *IntptrTy;
 223   ConstantInt *ZeroShadow;
 224   ConstantInt *ShadowPtrMask;
 225   ConstantInt *ShadowPtrMul;
 226   Constant *ArgTLS;
 227   Constant *RetvalTLS;
 228   void *(*GetArgTLSPtr)();
 229   void *(*GetRetvalTLSPtr)();
 230   Constant *GetArgTLS;
 231   Constant *GetRetvalTLS;
 232   FunctionType *DFSanUnionFnTy;
 233   FunctionType *DFSanUnionLoadFnTy;
 234   FunctionType *DFSanUnimplementedFnTy;
 235   FunctionType *DFSanSetLabelFnTy;
 236   FunctionType *DFSanNonzeroLabelFnTy;
 237   FunctionType *DFSanVarargWrapperFnTy;
 238   Constant *DFSanUnionFn;
 239   Constant *DFSanCheckedUnionFn;
 240   Constant *DFSanUnionLoadFn;
 241   Constant *DFSanUnimplementedFn;
 242   Constant *DFSanSetLabelFn;
 243   Constant *DFSanNonzeroLabelFn;
 244   Constant *DFSanVarargWrapperFn;
 245   MDNode *ColdCallWeights;
 246   DFSanABIList ABIList;
 247   DenseMap<Value *, Function *> UnwrappedFnMap;
 248   AttributeSet ReadOnlyNoneAttrs;
 249   DenseMap<const Function *, DISubprogram> FunctionDIs;
 250
 251   Value *getShadowAddress(Value *Addr, Instruction *Pos);
 252   bool isInstrumented(const Function *F);
 253   bool isInstrumented(const GlobalAlias *GA);
 254   FunctionType *getArgsFunctionType(FunctionType *T);
 255   FunctionType *getTrampolineFunctionType(FunctionType *T);
 256   FunctionType *getCustomFunctionType(FunctionType *T);
 257   InstrumentedABI getInstrumentedABI();
 258   WrapperKind getWrapperKind(Function *F);
 259   void addGlobalNamePrefix(GlobalValue *GV);
 260   Function *buildWrapperFunction(Function *F, StringRef NewFName,
 261                                  GlobalValue::LinkageTypes NewFLink,
 262                                  FunctionType *NewFT);
 263   Constant *getOrBuildTrampolineFunction(FunctionType *FT, StringRef FName);
 264
 265  public:
 266   DataFlowSanitizer(StringRef ABIListFile = StringRef(),
 267                     void *(*getArgTLS)() = nullptr,
 268                     void *(*getRetValTLS)() = nullptr);
 269   static char ID;
 270   bool doInitialization(Module &M) override;
 271   bool runOnModule(Module &M) override;
 272 };
 273
 274 struct DFSanFunction {
 275   DataFlowSanitizer &DFS;
 276   Function *F;
 277   DominatorTree DT;
 278   DataFlowSanitizer::InstrumentedABI IA;
 279   bool IsNativeABI;
 280   Value *ArgTLSPtr;
 281   Value *RetvalTLSPtr;
 282   AllocaInst *LabelReturnAlloca;
 283   DenseMap<Value *, Value *> ValShadowMap;
 284   DenseMap<AllocaInst *, AllocaInst *> AllocaShadowMap;
 285   std::vector<std::pair<PHINode *, PHINode *> > PHIFixups;
 286   DenseSet<Instruction *> SkipInsts;
 287   std::vector<Value *> NonZeroChecks;
 288   bool AvoidNewBlocks;
 289
 290   struct CachedCombinedShadow {
 291     BasicBlock *Block;
 292     Value *Shadow;
 293   };
 294   DenseMap<std::pair<Value *, Value *>, CachedCombinedShadow>
 295       CachedCombinedShadows;
 296   DenseMap<Value *, std::set<Value *>> ShadowElements;
 297
 298   DFSanFunction(DataFlowSanitizer &DFS, Function *F, bool IsNativeABI)
 299       : DFS(DFS), F(F), IA(DFS.getInstrumentedABI()),
 300         IsNativeABI(IsNativeABI), ArgTLSPtr(nullptr), RetvalTLSPtr(nullptr),
 301         LabelReturnAlloca(nullptr) {
 302     DT.recalculate(*F);
 303     // FIXME: Need to track down the register allocator issue which causes poor
 304     // performance in pathological cases with large numbers of basic blocks.
 305     AvoidNewBlocks = F->size() > 1000;
 306   }
 307   Value *getArgTLSPtr();
 308   Value *getArgTLS(unsigned Index, Instruction *Pos);
 309   Value *getRetvalTLS();
 310   Value *getShadow(Value *V);
 311   void setShadow(Instruction *I, Value *Shadow);
 312   Value *combineShadows(Value *V1, Value *V2, Instruction *Pos);
 313   Value *combineOperandShadows(Instruction *Inst);
 314   Value *loadShadow(Value *ShadowAddr, uint64_t Size, uint64_t Align,
 315                     Instruction *Pos);
 316   void storeShadow(Value *Addr, uint64_t Size, uint64_t Align, Value *Shadow,
 317                    Instruction *Pos);
 318 };
 319
 320 class DFSanVisitor : public InstVisitor<DFSanVisitor> {
 321  public:
 322   DFSanFunction &DFSF;
 323   DFSanVisitor(DFSanFunction &DFSF) : DFSF(DFSF) {}
 324
 325   void visitOperandShadowInst(Instruction &I);
 326
 327   void visitBinaryOperator(BinaryOperator &BO);
 328   void visitCastInst(CastInst &CI);
 329   void visitCmpInst(CmpInst &CI);
 330   void visitGetElementPtrInst(GetElementPtrInst &GEPI);
 331   void visitLoadInst(LoadInst &LI);
 332   void visitStoreInst(StoreInst &SI);
 333   void visitReturnInst(ReturnInst &RI);
 334   void visitCallSite(CallSite CS);
 335   void visitPHINode(PHINode &PN);
 336   void visitExtractElementInst(ExtractElementInst &I);
 337   void visitInsertElementInst(InsertElementInst &I);
 338   void visitShuffleVectorInst(ShuffleVectorInst &I);
 339   void visitExtractValueInst(ExtractValueInst &I);
 340   void visitInsertValueInst(InsertValueInst &I);
 341   void visitAllocaInst(AllocaInst &I);
 342   void visitSelectInst(SelectInst &I);
 343   void visitMemSetInst(MemSetInst &I);
 344   void visitMemTransferInst(MemTransferInst &I);
 345 };
 346
 347 }
 348
 349 char DataFlowSanitizer::ID;
 350 INITIALIZE_PASS(DataFlowSanitizer, "dfsan",
 351                 "DataFlowSanitizer: dynamic data flow analysis.", false, false)
 352
 353 ModulePass *llvm::createDataFlowSanitizerPass(StringRef ABIListFile,
 354                                               void *(*getArgTLS)(),
 355                                               void *(*getRetValTLS)()) {
 356   return new DataFlowSanitizer(ABIListFile, getArgTLS, getRetValTLS);
 357 }
 358
 359 DataFlowSanitizer::DataFlowSanitizer(StringRef ABIListFile,
 360                                      void *(*getArgTLS)(),
 361                                      void *(*getRetValTLS)())
 362     : ModulePass(ID), GetArgTLSPtr(getArgTLS), GetRetvalTLSPtr(getRetValTLS),
 363       ABIList(SpecialCaseList::createOrDie(ABIListFile.empty() ? ClABIListFile
 364                                                                : ABIListFile)) {
 365 }
 366
 367 FunctionType *DataFlowSanitizer::getArgsFunctionType(FunctionType *T) {
 368   llvm::SmallVector<Type *, 4> ArgTypes;
 369   std::copy(T->param_begin(), T->param_end(), std::back_inserter(ArgTypes));
 370   for (unsigned i = 0, e = T->getNumParams(); i != e; ++i)
 371     ArgTypes.push_back(ShadowTy);
 372   if (T->isVarArg())
 373     ArgTypes.push_back(ShadowPtrTy);
 374   Type *RetType = T->getReturnType();
 375   if (!RetType->isVoidTy())
 376     RetType = StructType::get(RetType, ShadowTy, (Type *)nullptr);
 377   return FunctionType::get(RetType, ArgTypes, T->isVarArg());
 378 }
 379
 380 FunctionType *DataFlowSanitizer::getTrampolineFunctionType(FunctionType *T) {
 381   assert(!T->isVarArg());
 382   llvm::SmallVector<Type *, 4> ArgTypes;
 383   ArgTypes.push_back(T->getPointerTo());
 384   std::copy(T->param_begin(), T->param_end(), std::back_inserter(ArgTypes));
 385   for (unsigned i = 0, e = T->getNumParams(); i != e; ++i)
 386     ArgTypes.push_back(ShadowTy);
 387   Type *RetType = T->getReturnType();
 388   if (!RetType->isVoidTy())
 389     ArgTypes.push_back(ShadowPtrTy);
 390   return FunctionType::get(T->getReturnType(), ArgTypes, false);
 391 }
 392
 393 FunctionType *DataFlowSanitizer::getCustomFunctionType(FunctionType *T) {
 394   llvm::SmallVector<Type *, 4> ArgTypes;
 395   for (FunctionType::param_iterator i = T->param_begin(), e = T->param_end();
 396        i != e; ++i) {
 397     FunctionType *FT;
 398     if (isa<PointerType>(*i) && (FT = dyn_cast<FunctionType>(cast<PointerType>(
 399                                      *i)->getElementType()))) {
 400       ArgTypes.push_back(getTrampolineFunctionType(FT)->getPointerTo());
 401       ArgTypes.push_back(Type::getInt8PtrTy(*Ctx));
 402     } else {
 403       ArgTypes.push_back(*i);
 404     }
 405   }
 406   for (unsigned i = 0, e = T->getNumParams(); i != e; ++i)
 407     ArgTypes.push_back(ShadowTy);
 408   if (T->isVarArg())
 409     ArgTypes.push_back(ShadowPtrTy);
 410   Type *RetType = T->getReturnType();
 411   if (!RetType->isVoidTy())
 412     ArgTypes.push_back(ShadowPtrTy);
 413   return FunctionType::get(T->getReturnType(), ArgTypes, T->isVarArg());
 414 }
 415
 416 bool DataFlowSanitizer::doInitialization(Module &M) {
 417   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
 418   if (!DLP)
 419     report_fatal_error("data layout missing");
 420   DL = &DLP->getDataLayout();
 421
 422   Mod = &M;
 423   Ctx = &M.getContext();
 424   ShadowTy = IntegerType::get(*Ctx, ShadowWidth);
 425   ShadowPtrTy = PointerType::getUnqual(ShadowTy);
 426   IntptrTy = DL->getIntPtrType(*Ctx);
 427   ZeroShadow = ConstantInt::getSigned(ShadowTy, 0);
 428   ShadowPtrMask = ConstantInt::getSigned(IntptrTy, ~0x700000000000LL);
 429   ShadowPtrMul = ConstantInt::getSigned(IntptrTy, ShadowWidth / 8);
 430
 431   Type *DFSanUnionArgs[2] = { ShadowTy, ShadowTy };
 432   DFSanUnionFnTy =
 433       FunctionType::get(ShadowTy, DFSanUnionArgs, /*isVarArg=*/ false);
 434   Type *DFSanUnionLoadArgs[2] = { ShadowPtrTy, IntptrTy };
 435   DFSanUnionLoadFnTy =
 436       FunctionType::get(ShadowTy, DFSanUnionLoadArgs, /*isVarArg=*/ false);
 437   DFSanUnimplementedFnTy = FunctionType::get(
 438       Type::getVoidTy(*Ctx), Type::getInt8PtrTy(*Ctx), /*isVarArg=*/false);
 439   Type *DFSanSetLabelArgs[3] = { ShadowTy, Type::getInt8PtrTy(*Ctx), IntptrTy };
 440   DFSanSetLabelFnTy = FunctionType::get(Type::getVoidTy(*Ctx),
 441                                         DFSanSetLabelArgs, /*isVarArg=*/false);
 442   DFSanNonzeroLabelFnTy = FunctionType::get(
 443       Type::getVoidTy(*Ctx), None, /*isVarArg=*/false);
 444   DFSanVarargWrapperFnTy = FunctionType::get(
 445       Type::getVoidTy(*Ctx), Type::getInt8PtrTy(*Ctx), /*isVarArg=*/false);
 446
 447   if (GetArgTLSPtr) {
 448     Type *ArgTLSTy = ArrayType::get(ShadowTy, 64);
 449     ArgTLS = nullptr;
 450     GetArgTLS = ConstantExpr::getIntToPtr(
 451         ConstantInt::get(IntptrTy, uintptr_t(GetArgTLSPtr)),
 452         PointerType::getUnqual(
 453             FunctionType::get(PointerType::getUnqual(ArgTLSTy),
 454                               (Type *)nullptr)));
 455   }
 456   if (GetRetvalTLSPtr) {
 457     RetvalTLS = nullptr;
 458     GetRetvalTLS = ConstantExpr::getIntToPtr(
 459         ConstantInt::get(IntptrTy, uintptr_t(GetRetvalTLSPtr)),
 460         PointerType::getUnqual(
 461             FunctionType::get(PointerType::getUnqual(ShadowTy),
 462                               (Type *)nullptr)));
 463   }
 464
 465   ColdCallWeights = MDBuilder(*Ctx).createBranchWeights(1, 1000);
 466   return true;
 467 }
 468
 469 bool DataFlowSanitizer::isInstrumented(const Function *F) {
 470   return !ABIList.isIn(*F, "uninstrumented");
 471 }
 472
 473 bool DataFlowSanitizer::isInstrumented(const GlobalAlias *GA) {
 474   return !ABIList.isIn(*GA, "uninstrumented");
 475 }
 476
 477 DataFlowSanitizer::InstrumentedABI DataFlowSanitizer::getInstrumentedABI() {
 478   return ClArgsABI ? IA_Args : IA_TLS;
 479 }
 480
 481 DataFlowSanitizer::WrapperKind DataFlowSanitizer::getWrapperKind(Function *F) {
 482   if (ABIList.isIn(*F, "functional"))
 483     return WK_Functional;
 484   if (ABIList.isIn(*F, "discard"))
 485     return WK_Discard;
 486   if (ABIList.isIn(*F, "custom"))
 487     return WK_Custom;
 488
 489   return WK_Warning;
 490 }
 491
 492 void DataFlowSanitizer::addGlobalNamePrefix(GlobalValue *GV) {
 493   std::string GVName = GV->getName(), Prefix = "dfs$";
 494   GV->setName(Prefix + GVName);
 495
 496   // Try to change the name of the function in module inline asm.  We only do
 497   // this for specific asm directives, currently only ".symver", to try to avoid
 498   // corrupting asm which happens to contain the symbol name as a substring.
 499   // Note that the substitution for .symver assumes that the versioned symbol
 500   // also has an instrumented name.
 501   std::string Asm = GV->getParent()->getModuleInlineAsm();
 502   std::string SearchStr = ".symver " + GVName + ",";
 503   size_t Pos = Asm.find(SearchStr);
 504   if (Pos != std::string::npos) {
 505     Asm.replace(Pos, SearchStr.size(),
 506                 ".symver " + Prefix + GVName + "," + Prefix);
 507     GV->getParent()->setModuleInlineAsm(Asm);
 508   }
 509 }
 510
 511 Function *
 512 DataFlowSanitizer::buildWrapperFunction(Function *F, StringRef NewFName,
 513                                         GlobalValue::LinkageTypes NewFLink,
 514                                         FunctionType *NewFT) {
 515   FunctionType *FT = F->getFunctionType();
 516   Function *NewF = Function::Create(NewFT, NewFLink, NewFName,
 517                                     F->getParent());
 518   NewF->copyAttributesFrom(F);
 519   NewF->removeAttributes(
 520       AttributeSet::ReturnIndex,
 521       AttributeFuncs::typeIncompatible(NewFT->getReturnType(),
 522                                        AttributeSet::ReturnIndex));
 523
 524   BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", NewF);
 525   if (F->isVarArg()) {
 526     NewF->removeAttributes(
 527         AttributeSet::FunctionIndex,
 528         AttributeSet().addAttribute(*Ctx, AttributeSet::FunctionIndex,
 529                                     "split-stack"));
 530     CallInst::Create(DFSanVarargWrapperFn,
 531                      IRBuilder<>(BB).CreateGlobalStringPtr(F->getName()), "",
 532                      BB);
 533     new UnreachableInst(*Ctx, BB);
 534   } else {
 535     std::vector<Value *> Args;
 536     unsigned n = FT->getNumParams();
 537     for (Function::arg_iterator ai = NewF->arg_begin(); n != 0; ++ai, --n)
 538       Args.push_back(&*ai);
 539     CallInst *CI = CallInst::Create(F, Args, "", BB);
 540     if (FT->getReturnType()->isVoidTy())
 541       ReturnInst::Create(*Ctx, BB);
 542     else
 543       ReturnInst::Create(*Ctx, CI, BB);
 544   }
 545
 546   return NewF;
 547 }
 548
 549 Constant *DataFlowSanitizer::getOrBuildTrampolineFunction(FunctionType *FT,
 550                                                           StringRef FName) {
 551   FunctionType *FTT = getTrampolineFunctionType(FT);
 552   Constant *C = Mod->getOrInsertFunction(FName, FTT);
 553   Function *F = dyn_cast<Function>(C);
 554   if (F && F->isDeclaration()) {
 555     F->setLinkage(GlobalValue::LinkOnceODRLinkage);
 556     BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", F);
 557     std::vector<Value *> Args;
 558     Function::arg_iterator AI = F->arg_begin(); ++AI;
 559     for (unsigned N = FT->getNumParams(); N != 0; ++AI, --N)
 560       Args.push_back(&*AI);
 561     CallInst *CI =
 562         CallInst::Create(&F->getArgumentList().front(), Args, "", BB);
 563     ReturnInst *RI;
 564     if (FT->getReturnType()->isVoidTy())
 565       RI = ReturnInst::Create(*Ctx, BB);
 566     else
 567       RI = ReturnInst::Create(*Ctx, CI, BB);
 568
 569     DFSanFunction DFSF(*this, F, /*IsNativeABI=*/true);
 570     Function::arg_iterator ValAI = F->arg_begin(), ShadowAI = AI; ++ValAI;
 571     for (unsigned N = FT->getNumParams(); N != 0; ++ValAI, ++ShadowAI, --N)
 572       DFSF.ValShadowMap[ValAI] = ShadowAI;
 573     DFSanVisitor(DFSF).visitCallInst(*CI);
 574     if (!FT->getReturnType()->isVoidTy())
 575       new StoreInst(DFSF.getShadow(RI->getReturnValue()),
 576                     &F->getArgumentList().back(), RI);
 577   }
 578
 579   return C;
 580 }
 581
 582 bool DataFlowSanitizer::runOnModule(Module &M) {
 583   if (!DL)
 584     return false;
 585
 586   if (ABIList.isIn(M, "skip"))
 587     return false;
 588
 589   FunctionDIs = makeSubprogramMap(M);
 590
 591   if (!GetArgTLSPtr) {
 592     Type *ArgTLSTy = ArrayType::get(ShadowTy, 64);
 593     ArgTLS = Mod->getOrInsertGlobal("__dfsan_arg_tls", ArgTLSTy);
 594     if (GlobalVariable *G = dyn_cast<GlobalVariable>(ArgTLS))
 595       G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel);
 596   }
 597   if (!GetRetvalTLSPtr) {
 598     RetvalTLS = Mod->getOrInsertGlobal("__dfsan_retval_tls", ShadowTy);
 599     if (GlobalVariable *G = dyn_cast<GlobalVariable>(RetvalTLS))
 600       G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel);
 601   }
 602
 603   DFSanUnionFn = Mod->getOrInsertFunction("__dfsan_union", DFSanUnionFnTy);
 604   if (Function *F = dyn_cast<Function>(DFSanUnionFn)) {
 605     F->addAttribute(AttributeSet::FunctionIndex, Attribute::NoUnwind);
 606     F->addAttribute(AttributeSet::FunctionIndex, Attribute::ReadNone);
 607     F->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
 608     F->addAttribute(1, Attribute::ZExt);
 609     F->addAttribute(2, Attribute::ZExt);
 610   }
 611   DFSanCheckedUnionFn = Mod->getOrInsertFunction("dfsan_union", DFSanUnionFnTy);
 612   if (Function *F = dyn_cast<Function>(DFSanCheckedUnionFn)) {
 613     F->addAttribute(AttributeSet::FunctionIndex, Attribute::NoUnwind);
 614     F->addAttribute(AttributeSet::FunctionIndex, Attribute::ReadNone);
 615     F->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
 616     F->addAttribute(1, Attribute::ZExt);
 617     F->addAttribute(2, Attribute::ZExt);
 618   }
 619   DFSanUnionLoadFn =
 620       Mod->getOrInsertFunction("__dfsan_union_load", DFSanUnionLoadFnTy);
 621   if (Function *F = dyn_cast<Function>(DFSanUnionLoadFn)) {
 622     F->addAttribute(AttributeSet::FunctionIndex, Attribute::NoUnwind);
 623     F->addAttribute(AttributeSet::FunctionIndex, Attribute::ReadOnly);
 624     F->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
 625   }
 626   DFSanUnimplementedFn =
 627       Mod->getOrInsertFunction("__dfsan_unimplemented", DFSanUnimplementedFnTy);
 628   DFSanSetLabelFn =
 629       Mod->getOrInsertFunction("__dfsan_set_label", DFSanSetLabelFnTy);
 630   if (Function *F = dyn_cast<Function>(DFSanSetLabelFn)) {
 631     F->addAttribute(1, Attribute::ZExt);
 632   }
 633   DFSanNonzeroLabelFn =
 634       Mod->getOrInsertFunction("__dfsan_nonzero_label", DFSanNonzeroLabelFnTy);
 635   DFSanVarargWrapperFn = Mod->getOrInsertFunction("__dfsan_vararg_wrapper",
 636                                                   DFSanVarargWrapperFnTy);
 637
 638   std::vector<Function *> FnsToInstrument;
 639   llvm::SmallPtrSet<Function *, 2> FnsWithNativeABI;
 640   for (Module::iterator i = M.begin(), e = M.end(); i != e; ++i) {
 641     if (!i->isIntrinsic() &&
 642         i != DFSanUnionFn &&
 643         i != DFSanCheckedUnionFn &&
 644         i != DFSanUnionLoadFn &&
 645         i != DFSanUnimplementedFn &&
 646         i != DFSanSetLabelFn &&
 647         i != DFSanNonzeroLabelFn &&
 648         i != DFSanVarargWrapperFn)
 649       FnsToInstrument.push_back(&*i);
 650   }
 651
 652   // Give function aliases prefixes when necessary, and build wrappers where the
 653   // instrumentedness is inconsistent.
 654   for (Module::alias_iterator i = M.alias_begin(), e = M.alias_end(); i != e;) {
 655     GlobalAlias *GA = &*i;
 656     ++i;
 657     // Don't stop on weak.  We assume people aren't playing games with the
 658     // instrumentedness of overridden weak aliases.
 659     if (auto F = dyn_cast<Function>(GA->getBaseObject())) {
 660       bool GAInst = isInstrumented(GA), FInst = isInstrumented(F);
 661       if (GAInst && FInst) {
 662         addGlobalNamePrefix(GA);
 663       } else if (GAInst != FInst) {
 664         // Non-instrumented alias of an instrumented function, or vice versa.
 665         // Replace the alias with a native-ABI wrapper of the aliasee.  The pass
 666         // below will take care of instrumenting it.
 667         Function *NewF =
 668             buildWrapperFunction(F, "", GA->getLinkage(), F->getFunctionType());
 669         GA->replaceAllUsesWith(ConstantExpr::getBitCast(NewF, GA->getType()));
 670         NewF->takeName(GA);
 671         GA->eraseFromParent();
 672         FnsToInstrument.push_back(NewF);
 673       }
 674     }
 675   }
 676
 677   AttrBuilder B;
 678   B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
 679   ReadOnlyNoneAttrs = AttributeSet::get(*Ctx, AttributeSet::FunctionIndex, B);
 680
 681   // First, change the ABI of every function in the module.  ABI-listed
 682   // functions keep their original ABI and get a wrapper function.
 683   for (std::vector<Function *>::iterator i = FnsToInstrument.begin(),
 684                                          e = FnsToInstrument.end();
 685        i != e; ++i) {
 686     Function &F = **i;
 687     FunctionType *FT = F.getFunctionType();
 688
 689     bool IsZeroArgsVoidRet = (FT->getNumParams() == 0 && !FT->isVarArg() &&
 690                               FT->getReturnType()->isVoidTy());
 691
 692     if (isInstrumented(&F)) {
 693       // Instrumented functions get a 'dfs$' prefix.  This allows us to more
 694       // easily identify cases of mismatching ABIs.
 695       if (getInstrumentedABI() == IA_Args && !IsZeroArgsVoidRet) {
 696         FunctionType *NewFT = getArgsFunctionType(FT);
 697         Function *NewF = Function::Create(NewFT, F.getLinkage(), "", &M);
 698         NewF->copyAttributesFrom(&F);
 699         NewF->removeAttributes(
 700             AttributeSet::ReturnIndex,
 701             AttributeFuncs::typeIncompatible(NewFT->getReturnType(),
 702                                              AttributeSet::ReturnIndex));
 703         for (Function::arg_iterator FArg = F.arg_begin(),
 704                                     NewFArg = NewF->arg_begin(),
 705                                     FArgEnd = F.arg_end();
 706              FArg != FArgEnd; ++FArg, ++NewFArg) {
 707           FArg->replaceAllUsesWith(NewFArg);
 708         }
 709         NewF->getBasicBlockList().splice(NewF->begin(), F.getBasicBlockList());
 710
 711         for (Function::user_iterator UI = F.user_begin(), UE = F.user_end();
 712              UI != UE;) {
 713           BlockAddress *BA = dyn_cast<BlockAddress>(*UI);
 714           ++UI;
 715           if (BA) {
 716             BA->replaceAllUsesWith(
 717                 BlockAddress::get(NewF, BA->getBasicBlock()));
 718             delete BA;
 719           }
 720         }
 721         F.replaceAllUsesWith(
 722             ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT)));
 723         NewF->takeName(&F);
 724         F.eraseFromParent();
 725         *i = NewF;
 726         addGlobalNamePrefix(NewF);
 727       } else {
 728         addGlobalNamePrefix(&F);
 729       }
 730     } else if (!IsZeroArgsVoidRet || getWrapperKind(&F) == WK_Custom) {
 731       // Build a wrapper function for F.  The wrapper simply calls F, and is
 732       // added to FnsToInstrument so that any instrumentation according to its
 733       // WrapperKind is done in the second pass below.
 734       FunctionType *NewFT = getInstrumentedABI() == IA_Args
 735                                 ? getArgsFunctionType(FT)
 736                                 : FT;
 737       Function *NewF = buildWrapperFunction(
 738           &F, std::string("dfsw$") + std::string(F.getName()),
 739           GlobalValue::LinkOnceODRLinkage, NewFT);
 740       if (getInstrumentedABI() == IA_TLS)
 741         NewF->removeAttributes(AttributeSet::FunctionIndex, ReadOnlyNoneAttrs);
 742
 743       Value *WrappedFnCst =
 744           ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT));
 745       F.replaceAllUsesWith(WrappedFnCst);
 746
 747       // Patch the pointer to LLVM function in debug info descriptor.
 748       auto DI = FunctionDIs.find(&F);
 749       if (DI != FunctionDIs.end())
 750         DI->second.replaceFunction(&F);
 751
 752       UnwrappedFnMap[WrappedFnCst] = &F;
 753       *i = NewF;
 754
 755       if (!F.isDeclaration()) {
 756         // This function is probably defining an interposition of an
 757         // uninstrumented function and hence needs to keep the original ABI.
 758         // But any functions it may call need to use the instrumented ABI, so
 759         // we instrument it in a mode which preserves the original ABI.
 760         FnsWithNativeABI.insert(&F);
 761
 762         // This code needs to rebuild the iterators, as they may be invalidated
 763         // by the push_back, taking care that the new range does not include
 764         // any functions added by this code.
 765         size_t N = i - FnsToInstrument.begin(),
 766                Count = e - FnsToInstrument.begin();
 767         FnsToInstrument.push_back(&F);
 768         i = FnsToInstrument.begin() + N;
 769         e = FnsToInstrument.begin() + Count;
 770       }
 771                // Hopefully, nobody will try to indirectly call a vararg
 772                // function... yet.
 773     } else if (FT->isVarArg()) {
 774       UnwrappedFnMap[&F] = &F;
 775       *i = nullptr;
 776     }
 777   }
 778
 779   for (std::vector<Function *>::iterator i = FnsToInstrument.begin(),
 780                                          e = FnsToInstrument.end();
 781        i != e; ++i) {
 782     if (!*i || (*i)->isDeclaration())
 783       continue;
 784
 785     removeUnreachableBlocks(**i);
 786
 787     DFSanFunction DFSF(*this, *i, FnsWithNativeABI.count(*i));
 788
 789     // DFSanVisitor may create new basic blocks, which confuses df_iterator.
 790     // Build a copy of the list before iterating over it.
 791     llvm::SmallVector<BasicBlock *, 4> BBList(
 792         depth_first(&(*i)->getEntryBlock()));
 793
 794     for (llvm::SmallVector<BasicBlock *, 4>::iterator i = BBList.begin(),
 795                                                       e = BBList.end();
 796          i != e; ++i) {
 797       Instruction *Inst = &(*i)->front();
 798       while (1) {
 799         // DFSanVisitor may split the current basic block, changing the current
 800         // instruction's next pointer and moving the next instruction to the
 801         // tail block from which we should continue.
 802         Instruction *Next = Inst->getNextNode();
 803         // DFSanVisitor may delete Inst, so keep track of whether it was a
 804         // terminator.
 805         bool IsTerminator = isa<TerminatorInst>(Inst);
 806         if (!DFSF.SkipInsts.count(Inst))
 807           DFSanVisitor(DFSF).visit(Inst);
 808         if (IsTerminator)
 809           break;
 810         Inst = Next;
 811       }
 812     }
 813
 814     // We will not necessarily be able to compute the shadow for every phi node
 815     // until we have visited every block.  Therefore, the code that handles phi
 816     // nodes adds them to the PHIFixups list so that they can be properly
 817     // handled here.
 818     for (std::vector<std::pair<PHINode *, PHINode *> >::iterator
 819              i = DFSF.PHIFixups.begin(),
 820              e = DFSF.PHIFixups.end();
 821          i != e; ++i) {
 822       for (unsigned val = 0, n = i->first->getNumIncomingValues(); val != n;
 823            ++val) {
 824         i->second->setIncomingValue(
 825             val, DFSF.getShadow(i->first->getIncomingValue(val)));
 826       }
 827     }
 828
 829     // -dfsan-debug-nonzero-labels will split the CFG in all kinds of crazy
 830     // places (i.e. instructions in basic blocks we haven't even begun visiting
 831     // yet).  To make our life easier, do this work in a pass after the main
 832     // instrumentation.
 833     if (ClDebugNonzeroLabels) {
 834       for (Value *V : DFSF.NonZeroChecks) {
 835         Instruction *Pos;
 836         if (Instruction *I = dyn_cast<Instruction>(V))
 837           Pos = I->getNextNode();
 838         else
 839           Pos = DFSF.F->getEntryBlock().begin();
 840         while (isa<PHINode>(Pos) || isa<AllocaInst>(Pos))
 841           Pos = Pos->getNextNode();
 842         IRBuilder<> IRB(Pos);
 843         Value *Ne = IRB.CreateICmpNE(V, DFSF.DFS.ZeroShadow);
 844         BranchInst *BI = cast<BranchInst>(SplitBlockAndInsertIfThen(
 845             Ne, Pos, /*Unreachable=*/false, ColdCallWeights));
 846         IRBuilder<> ThenIRB(BI);
 847         ThenIRB.CreateCall(DFSF.DFS.DFSanNonzeroLabelFn);
 848       }
 849     }
 850   }
 851
 852   return false;
 853 }
 854
 855 Value *DFSanFunction::getArgTLSPtr() {
 856   if (ArgTLSPtr)
 857     return ArgTLSPtr;
 858   if (DFS.ArgTLS)
 859     return ArgTLSPtr = DFS.ArgTLS;
 860
 861   IRBuilder<> IRB(F->getEntryBlock().begin());
 862   return ArgTLSPtr = IRB.CreateCall(DFS.GetArgTLS);
 863 }
 864
 865 Value *DFSanFunction::getRetvalTLS() {
 866   if (RetvalTLSPtr)
 867     return RetvalTLSPtr;
 868   if (DFS.RetvalTLS)
 869     return RetvalTLSPtr = DFS.RetvalTLS;
 870
 871   IRBuilder<> IRB(F->getEntryBlock().begin());
 872   return RetvalTLSPtr = IRB.CreateCall(DFS.GetRetvalTLS);
 873 }
 874
 875 Value *DFSanFunction::getArgTLS(unsigned Idx, Instruction *Pos) {
 876   IRBuilder<> IRB(Pos);
 877   return IRB.CreateConstGEP2_64(getArgTLSPtr(), 0, Idx);
 878 }
 879
 880 Value *DFSanFunction::getShadow(Value *V) {
 881   if (!isa<Argument>(V) && !isa<Instruction>(V))
 882     return DFS.ZeroShadow;
 883   Value *&Shadow = ValShadowMap[V];
 884   if (!Shadow) {
 885     if (Argument *A = dyn_cast<Argument>(V)) {
 886       if (IsNativeABI)
 887         return DFS.ZeroShadow;
 888       switch (IA) {
 889       case DataFlowSanitizer::IA_TLS: {
 890         Value *ArgTLSPtr = getArgTLSPtr();
 891         Instruction *ArgTLSPos =
 892             DFS.ArgTLS ? &*F->getEntryBlock().begin()
 893                        : cast<Instruction>(ArgTLSPtr)->getNextNode();
 894         IRBuilder<> IRB(ArgTLSPos);
 895         Shadow = IRB.CreateLoad(getArgTLS(A->getArgNo(), ArgTLSPos));
 896         break;
 897       }
 898       case DataFlowSanitizer::IA_Args: {
 899         unsigned ArgIdx = A->getArgNo() + F->getArgumentList().size() / 2;
 900         Function::arg_iterator i = F->arg_begin();
 901         while (ArgIdx--)
 902           ++i;
 903         Shadow = i;
 904         assert(Shadow->getType() == DFS.ShadowTy);
 905         break;
 906       }
 907       }
 908       NonZeroChecks.push_back(Shadow);
 909     } else {
 910       Shadow = DFS.ZeroShadow;
 911     }
 912   }
 913   return Shadow;
 914 }
 915
 916 void DFSanFunction::setShadow(Instruction *I, Value *Shadow) {
 917   assert(!ValShadowMap.count(I));
 918   assert(Shadow->getType() == DFS.ShadowTy);
 919   ValShadowMap[I] = Shadow;
 920 }
 921
 922 Value *DataFlowSanitizer::getShadowAddress(Value *Addr, Instruction *Pos) {
 923   assert(Addr != RetvalTLS && "Reinstrumenting?");
 924   IRBuilder<> IRB(Pos);
 925   return IRB.CreateIntToPtr(
 926       IRB.CreateMul(
 927           IRB.CreateAnd(IRB.CreatePtrToInt(Addr, IntptrTy), ShadowPtrMask),
 928           ShadowPtrMul),
 929       ShadowPtrTy);
 930 }
 931
 932 // Generates IR to compute the union of the two given shadows, inserting it
 933 // before Pos.  Returns the computed union Value.
 934 Value *DFSanFunction::combineShadows(Value *V1, Value *V2, Instruction *Pos) {
 935   if (V1 == DFS.ZeroShadow)
 936     return V2;
 937   if (V2 == DFS.ZeroShadow)
 938     return V1;
 939   if (V1 == V2)
 940     return V1;
 941
 942   auto V1Elems = ShadowElements.find(V1);
 943   auto V2Elems = ShadowElements.find(V2);
 944   if (V1Elems != ShadowElements.end() && V2Elems != ShadowElements.end()) {
 945     if (std::includes(V1Elems->second.begin(), V1Elems->second.end(),
 946                       V2Elems->second.begin(), V2Elems->second.end())) {
 947       return V1;
 948     } else if (std::includes(V2Elems->second.begin(), V2Elems->second.end(),
 949                              V1Elems->second.begin(), V1Elems->second.end())) {
 950       return V2;
 951     }
 952   } else if (V1Elems != ShadowElements.end()) {
 953     if (V1Elems->second.count(V2))
 954       return V1;
 955   } else if (V2Elems != ShadowElements.end()) {
 956     if (V2Elems->second.count(V1))
 957       return V2;
 958   }
 959
 960   auto Key = std::make_pair(V1, V2);
 961   if (V1 > V2)
 962     std::swap(Key.first, Key.second);
 963   CachedCombinedShadow &CCS = CachedCombinedShadows[Key];
 964   if (CCS.Block && DT.dominates(CCS.Block, Pos->getParent()))
 965     return CCS.Shadow;
 966
 967   IRBuilder<> IRB(Pos);
 968   if (AvoidNewBlocks) {
 969     CallInst *Call = IRB.CreateCall2(DFS.DFSanCheckedUnionFn, V1, V2);
 970     Call->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
 971     Call->addAttribute(1, Attribute::ZExt);
 972     Call->addAttribute(2, Attribute::ZExt);
 973
 974     CCS.Block = Pos->getParent();
 975     CCS.Shadow = Call;
 976   } else {
 977     BasicBlock *Head = Pos->getParent();
 978     Value *Ne = IRB.CreateICmpNE(V1, V2);
 979     BranchInst *BI = cast<BranchInst>(SplitBlockAndInsertIfThen(
 980         Ne, Pos, /*Unreachable=*/false, DFS.ColdCallWeights, &DT));
 981     IRBuilder<> ThenIRB(BI);
 982     CallInst *Call = ThenIRB.CreateCall2(DFS.DFSanUnionFn, V1, V2);
 983     Call->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
 984     Call->addAttribute(1, Attribute::ZExt);
 985     Call->addAttribute(2, Attribute::ZExt);
 986
 987     BasicBlock *Tail = BI->getSuccessor(0);
 988     PHINode *Phi = PHINode::Create(DFS.ShadowTy, 2, "", Tail->begin());
 989     Phi->addIncoming(Call, Call->getParent());
 990     Phi->addIncoming(V1, Head);
 991
 992     CCS.Block = Tail;
 993     CCS.Shadow = Phi;
 994   }
 995
 996   std::set<Value *> UnionElems;
 997   if (V1Elems != ShadowElements.end()) {
 998     UnionElems = V1Elems->second;
 999   } else {
1000     UnionElems.insert(V1);
1001   }
1002   if (V2Elems != ShadowElements.end()) {
1003     UnionElems.insert(V2Elems->second.begin(), V2Elems->second.end());
1004   } else {
1005     UnionElems.insert(V2);
1006   }
1007   ShadowElements[CCS.Shadow] = std::move(UnionElems);
1008
1009   return CCS.Shadow;
1010 }
1011
1012 // A convenience function which folds the shadows of each of the operands
1013 // of the provided instruction Inst, inserting the IR before Inst.  Returns
1014 // the computed union Value.
1015 Value *DFSanFunction::combineOperandShadows(Instruction *Inst) {
1016   if (Inst->getNumOperands() == 0)
1017     return DFS.ZeroShadow;
1018
1019   Value *Shadow = getShadow(Inst->getOperand(0));
1020   for (unsigned i = 1, n = Inst->getNumOperands(); i != n; ++i) {
1021     Shadow = combineShadows(Shadow, getShadow(Inst->getOperand(i)), Inst);
1022   }
1023   return Shadow;
1024 }
1025
1026 void DFSanVisitor::visitOperandShadowInst(Instruction &I) {
1027   Value *CombinedShadow = DFSF.combineOperandShadows(&I);
1028   DFSF.setShadow(&I, CombinedShadow);
1029 }
1030
1031 // Generates IR to load shadow corresponding to bytes [Addr, Addr+Size), where
1032 // Addr has alignment Align, and take the union of each of those shadows.
1033 Value *DFSanFunction::loadShadow(Value *Addr, uint64_t Size, uint64_t Align,
1034                                  Instruction *Pos) {
1035   if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) {
1036     llvm::DenseMap<AllocaInst *, AllocaInst *>::iterator i =
1037         AllocaShadowMap.find(AI);
1038     if (i != AllocaShadowMap.end()) {
1039       IRBuilder<> IRB(Pos);
1040       return IRB.CreateLoad(i->second);
1041     }
1042   }
1043
1044   uint64_t ShadowAlign = Align * DFS.ShadowWidth / 8;
1045   SmallVector<Value *, 2> Objs;
1046   GetUnderlyingObjects(Addr, Objs, DFS.DL);
1047   bool AllConstants = true;
1048   for (SmallVector<Value *, 2>::iterator i = Objs.begin(), e = Objs.end();
1049        i != e; ++i) {
1050     if (isa<Function>(*i) || isa<BlockAddress>(*i))
1051       continue;
1052     if (isa<GlobalVariable>(*i) && cast<GlobalVariable>(*i)->isConstant())
1053       continue;
1054
1055     AllConstants = false;
1056     break;
1057   }
1058   if (AllConstants)
1059     return DFS.ZeroShadow;
1060
1061   Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos);
1062   switch (Size) {
1063   case 0:
1064     return DFS.ZeroShadow;
1065   case 1: {
1066     LoadInst *LI = new LoadInst(ShadowAddr, "", Pos);
1067     LI->setAlignment(ShadowAlign);
1068     return LI;
1069   }
1070   case 2: {
1071     IRBuilder<> IRB(Pos);
1072     Value *ShadowAddr1 =
1073         IRB.CreateGEP(ShadowAddr, ConstantInt::get(DFS.IntptrTy, 1));
1074     return combineShadows(IRB.CreateAlignedLoad(ShadowAddr, ShadowAlign),
1075                           IRB.CreateAlignedLoad(ShadowAddr1, ShadowAlign), Pos);
1076   }
1077   }
1078   if (!AvoidNewBlocks && Size % (64 / DFS.ShadowWidth) == 0) {
1079     // Fast path for the common case where each byte has identical shadow: load
1080     // shadow 64 bits at a time, fall out to a __dfsan_union_load call if any
1081     // shadow is non-equal.
1082     BasicBlock *FallbackBB = BasicBlock::Create(*DFS.Ctx, "", F);
1083     IRBuilder<> FallbackIRB(FallbackBB);
1084     CallInst *FallbackCall = FallbackIRB.CreateCall2(
1085         DFS.DFSanUnionLoadFn, ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size));
1086     FallbackCall->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
1087
1088     // Compare each of the shadows stored in the loaded 64 bits to each other,
1089     // by computing (WideShadow rotl ShadowWidth) == WideShadow.
1090     IRBuilder<> IRB(Pos);
1091     Value *WideAddr =
1092         IRB.CreateBitCast(ShadowAddr, Type::getInt64PtrTy(*DFS.Ctx));
1093     Value *WideShadow = IRB.CreateAlignedLoad(WideAddr, ShadowAlign);
1094     Value *TruncShadow = IRB.CreateTrunc(WideShadow, DFS.ShadowTy);
1095     Value *ShlShadow = IRB.CreateShl(WideShadow, DFS.ShadowWidth);
1096     Value *ShrShadow = IRB.CreateLShr(WideShadow, 64 - DFS.ShadowWidth);
1097     Value *RotShadow = IRB.CreateOr(ShlShadow, ShrShadow);
1098     Value *ShadowsEq = IRB.CreateICmpEQ(WideShadow, RotShadow);
1099
1100     BasicBlock *Head = Pos->getParent();
1101     BasicBlock *Tail = Head->splitBasicBlock(Pos);
1102
1103     if (DomTreeNode *OldNode = DT.getNode(Head)) {
1104       std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
1105
1106       DomTreeNode *NewNode = DT.addNewBlock(Tail, Head);
1107       for (auto Child : Children)
1108         DT.changeImmediateDominator(Child, NewNode);
1109     }
1110
1111     // In the following code LastBr will refer to the previous basic block's
1112     // conditional branch instruction, whose true successor is fixed up to point
1113     // to the next block during the loop below or to the tail after the final
1114     // iteration.
1115     BranchInst *LastBr = BranchInst::Create(FallbackBB, FallbackBB, ShadowsEq);
1116     ReplaceInstWithInst(Head->getTerminator(), LastBr);
1117     DT.addNewBlock(FallbackBB, Head);
1118
1119     for (uint64_t Ofs = 64 / DFS.ShadowWidth; Ofs != Size;
1120          Ofs += 64 / DFS.ShadowWidth) {
1121       BasicBlock *NextBB = BasicBlock::Create(*DFS.Ctx, "", F);
1122       DT.addNewBlock(NextBB, LastBr->getParent());
1123       IRBuilder<> NextIRB(NextBB);
1124       WideAddr = NextIRB.CreateGEP(WideAddr, ConstantInt::get(DFS.IntptrTy, 1));
1125       Value *NextWideShadow = NextIRB.CreateAlignedLoad(WideAddr, ShadowAlign);
1126       ShadowsEq = NextIRB.CreateICmpEQ(WideShadow, NextWideShadow);
1127       LastBr->setSuccessor(0, NextBB);
1128       LastBr = NextIRB.CreateCondBr(ShadowsEq, FallbackBB, FallbackBB);
1129     }
1130
1131     LastBr->setSuccessor(0, Tail);
1132     FallbackIRB.CreateBr(Tail);
1133     PHINode *Shadow = PHINode::Create(DFS.ShadowTy, 2, "", &Tail->front());
1134     Shadow->addIncoming(FallbackCall, FallbackBB);
1135     Shadow->addIncoming(TruncShadow, LastBr->getParent());
1136     return Shadow;
1137   }
1138
1139   IRBuilder<> IRB(Pos);
1140   CallInst *FallbackCall = IRB.CreateCall2(
1141       DFS.DFSanUnionLoadFn, ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size));
1142   FallbackCall->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
1143   return FallbackCall;
1144 }
1145
1146 void DFSanVisitor::visitLoadInst(LoadInst &LI) {
1147   uint64_t Size = DFSF.DFS.DL->getTypeStoreSize(LI.getType());
1148   if (Size == 0) {
1149     DFSF.setShadow(&LI, DFSF.DFS.ZeroShadow);
1150     return;
1151   }
1152
1153   uint64_t Align;
1154   if (ClPreserveAlignment) {
1155     Align = LI.getAlignment();
1156     if (Align == 0)
1157       Align = DFSF.DFS.DL->getABITypeAlignment(LI.getType());
1158   } else {
1159     Align = 1;
1160   }
1161   IRBuilder<> IRB(&LI);
1162   Value *Shadow = DFSF.loadShadow(LI.getPointerOperand(), Size, Align, &LI);
1163   if (ClCombinePointerLabelsOnLoad) {
1164     Value *PtrShadow = DFSF.getShadow(LI.getPointerOperand());
1165     Shadow = DFSF.combineShadows(Shadow, PtrShadow, &LI);
1166   }
1167   if (Shadow != DFSF.DFS.ZeroShadow)
1168     DFSF.NonZeroChecks.push_back(Shadow);
1169
1170   DFSF.setShadow(&LI, Shadow);
1171 }
1172
1173 void DFSanFunction::storeShadow(Value *Addr, uint64_t Size, uint64_t Align,
1174                                 Value *Shadow, Instruction *Pos) {
1175   if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) {
1176     llvm::DenseMap<AllocaInst *, AllocaInst *>::iterator i =
1177         AllocaShadowMap.find(AI);
1178     if (i != AllocaShadowMap.end()) {
1179       IRBuilder<> IRB(Pos);
1180       IRB.CreateStore(Shadow, i->second);
1181       return;
1182     }
1183   }
1184
1185   uint64_t ShadowAlign = Align * DFS.ShadowWidth / 8;
1186   IRBuilder<> IRB(Pos);
1187   Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos);
1188   if (Shadow == DFS.ZeroShadow) {
1189     IntegerType *ShadowTy = IntegerType::get(*DFS.Ctx, Size * DFS.ShadowWidth);
1190     Value *ExtZeroShadow = ConstantInt::get(ShadowTy, 0);
1191     Value *ExtShadowAddr =
1192         IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowTy));
1193     IRB.CreateAlignedStore(ExtZeroShadow, ExtShadowAddr, ShadowAlign);
1194     return;
1195   }
1196
1197   const unsigned ShadowVecSize = 128 / DFS.ShadowWidth;
1198   uint64_t Offset = 0;
1199   if (Size >= ShadowVecSize) {
1200     VectorType *ShadowVecTy = VectorType::get(DFS.ShadowTy, ShadowVecSize);
1201     Value *ShadowVec = UndefValue::get(ShadowVecTy);
1202     for (unsigned i = 0; i != ShadowVecSize; ++i) {
1203       ShadowVec = IRB.CreateInsertElement(
1204           ShadowVec, Shadow, ConstantInt::get(Type::getInt32Ty(*DFS.Ctx), i));
1205     }
1206     Value *ShadowVecAddr =
1207         IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowVecTy));
1208     do {
1209       Value *CurShadowVecAddr = IRB.CreateConstGEP1_32(ShadowVecAddr, Offset);
1210       IRB.CreateAlignedStore(ShadowVec, CurShadowVecAddr, ShadowAlign);
1211       Size -= ShadowVecSize;
1212       ++Offset;
1213     } while (Size >= ShadowVecSize);
1214     Offset *= ShadowVecSize;
1215   }
1216   while (Size > 0) {
1217     Value *CurShadowAddr = IRB.CreateConstGEP1_32(ShadowAddr, Offset);
1218     IRB.CreateAlignedStore(Shadow, CurShadowAddr, ShadowAlign);
1219     --Size;
1220     ++Offset;
1221   }
1222 }
1223
1224 void DFSanVisitor::visitStoreInst(StoreInst &SI) {
1225   uint64_t Size =
1226       DFSF.DFS.DL->getTypeStoreSize(SI.getValueOperand()->getType());
1227   if (Size == 0)
1228     return;
1229
1230   uint64_t Align;
1231   if (ClPreserveAlignment) {
1232     Align = SI.getAlignment();
1233     if (Align == 0)
1234       Align = DFSF.DFS.DL->getABITypeAlignment(SI.getValueOperand()->getType());
1235   } else {
1236     Align = 1;
1237   }
1238
1239   Value* Shadow = DFSF.getShadow(SI.getValueOperand());
1240   if (ClCombinePointerLabelsOnStore) {
1241     Value *PtrShadow = DFSF.getShadow(SI.getPointerOperand());
1242     Shadow = DFSF.combineShadows(Shadow, PtrShadow, &SI);
1243   }
1244   DFSF.storeShadow(SI.getPointerOperand(), Size, Align, Shadow, &SI);
1245 }
1246
1247 void DFSanVisitor::visitBinaryOperator(BinaryOperator &BO) {
1248   visitOperandShadowInst(BO);
1249 }
1250
1251 void DFSanVisitor::visitCastInst(CastInst &CI) { visitOperandShadowInst(CI); }
1252
1253 void DFSanVisitor::visitCmpInst(CmpInst &CI) { visitOperandShadowInst(CI); }
1254
1255 void DFSanVisitor::visitGetElementPtrInst(GetElementPtrInst &GEPI) {
1256   visitOperandShadowInst(GEPI);
1257 }
1258
1259 void DFSanVisitor::visitExtractElementInst(ExtractElementInst &I) {
1260   visitOperandShadowInst(I);
1261 }
1262
1263 void DFSanVisitor::visitInsertElementInst(InsertElementInst &I) {
1264   visitOperandShadowInst(I);
1265 }
1266
1267 void DFSanVisitor::visitShuffleVectorInst(ShuffleVectorInst &I) {
1268   visitOperandShadowInst(I);
1269 }
1270
1271 void DFSanVisitor::visitExtractValueInst(ExtractValueInst &I) {
1272   visitOperandShadowInst(I);
1273 }
1274
1275 void DFSanVisitor::visitInsertValueInst(InsertValueInst &I) {
1276   visitOperandShadowInst(I);
1277 }
1278
1279 void DFSanVisitor::visitAllocaInst(AllocaInst &I) {
1280   bool AllLoadsStores = true;
1281   for (User *U : I.users()) {
1282     if (isa<LoadInst>(U))
1283       continue;
1284
1285     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1286       if (SI->getPointerOperand() == &I)
1287         continue;
1288     }
1289
1290     AllLoadsStores = false;
1291     break;
1292   }
1293   if (AllLoadsStores) {
1294     IRBuilder<> IRB(&I);
1295     DFSF.AllocaShadowMap[&I] = IRB.CreateAlloca(DFSF.DFS.ShadowTy);
1296   }
1297   DFSF.setShadow(&I, DFSF.DFS.ZeroShadow);
1298 }
1299
1300 void DFSanVisitor::visitSelectInst(SelectInst &I) {
1301   Value *CondShadow = DFSF.getShadow(I.getCondition());
1302   Value *TrueShadow = DFSF.getShadow(I.getTrueValue());
1303   Value *FalseShadow = DFSF.getShadow(I.getFalseValue());
1304
1305   if (isa<VectorType>(I.getCondition()->getType())) {
1306     DFSF.setShadow(
1307         &I,
1308         DFSF.combineShadows(
1309             CondShadow, DFSF.combineShadows(TrueShadow, FalseShadow, &I), &I));
1310   } else {
1311     Value *ShadowSel;
1312     if (TrueShadow == FalseShadow) {
1313       ShadowSel = TrueShadow;
1314     } else {
1315       ShadowSel =
1316           SelectInst::Create(I.getCondition(), TrueShadow, FalseShadow, "", &I);
1317     }
1318     DFSF.setShadow(&I, DFSF.combineShadows(CondShadow, ShadowSel, &I));
1319   }
1320 }
1321
1322 void DFSanVisitor::visitMemSetInst(MemSetInst &I) {
1323   IRBuilder<> IRB(&I);
1324   Value *ValShadow = DFSF.getShadow(I.getValue());
1325   IRB.CreateCall3(
1326       DFSF.DFS.DFSanSetLabelFn, ValShadow,
1327       IRB.CreateBitCast(I.getDest(), Type::getInt8PtrTy(*DFSF.DFS.Ctx)),
1328       IRB.CreateZExtOrTrunc(I.getLength(), DFSF.DFS.IntptrTy));
1329 }
1330
1331 void DFSanVisitor::visitMemTransferInst(MemTransferInst &I) {
1332   IRBuilder<> IRB(&I);
1333   Value *DestShadow = DFSF.DFS.getShadowAddress(I.getDest(), &I);
1334   Value *SrcShadow = DFSF.DFS.getShadowAddress(I.getSource(), &I);
1335   Value *LenShadow = IRB.CreateMul(
1336       I.getLength(),
1337       ConstantInt::get(I.getLength()->getType(), DFSF.DFS.ShadowWidth / 8));
1338   Value *AlignShadow;
1339   if (ClPreserveAlignment) {
1340     AlignShadow = IRB.CreateMul(I.getAlignmentCst(),
1341                                 ConstantInt::get(I.getAlignmentCst()->getType(),
1342                                                  DFSF.DFS.ShadowWidth / 8));
1343   } else {
1344     AlignShadow = ConstantInt::get(I.getAlignmentCst()->getType(),
1345                                    DFSF.DFS.ShadowWidth / 8);
1346   }
1347   Type *Int8Ptr = Type::getInt8PtrTy(*DFSF.DFS.Ctx);
1348   DestShadow = IRB.CreateBitCast(DestShadow, Int8Ptr);
1349   SrcShadow = IRB.CreateBitCast(SrcShadow, Int8Ptr);
1350   IRB.CreateCall5(I.getCalledValue(), DestShadow, SrcShadow, LenShadow,
1351                   AlignShadow, I.getVolatileCst());
1352 }
1353
1354 void DFSanVisitor::visitReturnInst(ReturnInst &RI) {
1355   if (!DFSF.IsNativeABI && RI.getReturnValue()) {
1356     switch (DFSF.IA) {
1357     case DataFlowSanitizer::IA_TLS: {
1358       Value *S = DFSF.getShadow(RI.getReturnValue());
1359       IRBuilder<> IRB(&RI);
1360       IRB.CreateStore(S, DFSF.getRetvalTLS());
1361       break;
1362     }
1363     case DataFlowSanitizer::IA_Args: {
1364       IRBuilder<> IRB(&RI);
1365       Type *RT = DFSF.F->getFunctionType()->getReturnType();
1366       Value *InsVal =
1367           IRB.CreateInsertValue(UndefValue::get(RT), RI.getReturnValue(), 0);
1368       Value *InsShadow =
1369           IRB.CreateInsertValue(InsVal, DFSF.getShadow(RI.getReturnValue()), 1);
1370       RI.setOperand(0, InsShadow);
1371       break;
1372     }
1373     }
1374   }
1375 }
1376
1377 void DFSanVisitor::visitCallSite(CallSite CS) {
1378   Function *F = CS.getCalledFunction();
1379   if ((F && F->isIntrinsic()) || isa<InlineAsm>(CS.getCalledValue())) {
1380     visitOperandShadowInst(*CS.getInstruction());
1381     return;
1382   }
1383
1384   // Calls to this function are synthesized in wrappers, and we shouldn't
1385   // instrument them.
1386   if (F == DFSF.DFS.DFSanVarargWrapperFn)
1387     return;
1388
1389   assert(!(cast<FunctionType>(
1390       CS.getCalledValue()->getType()->getPointerElementType())->isVarArg() &&
1391            dyn_cast<InvokeInst>(CS.getInstruction())));
1392
1393   IRBuilder<> IRB(CS.getInstruction());
1394
1395   DenseMap<Value *, Function *>::iterator i =
1396       DFSF.DFS.UnwrappedFnMap.find(CS.getCalledValue());
1397   if (i != DFSF.DFS.UnwrappedFnMap.end()) {
1398     Function *F = i->second;
1399     switch (DFSF.DFS.getWrapperKind(F)) {
1400     case DataFlowSanitizer::WK_Warning: {
1401       CS.setCalledFunction(F);
1402       IRB.CreateCall(DFSF.DFS.DFSanUnimplementedFn,
1403                      IRB.CreateGlobalStringPtr(F->getName()));
1404       DFSF.setShadow(CS.getInstruction(), DFSF.DFS.ZeroShadow);
1405       return;
1406     }
1407     case DataFlowSanitizer::WK_Discard: {
1408       CS.setCalledFunction(F);
1409       DFSF.setShadow(CS.getInstruction(), DFSF.DFS.ZeroShadow);
1410       return;
1411     }
1412     case DataFlowSanitizer::WK_Functional: {
1413       CS.setCalledFunction(F);
1414       visitOperandShadowInst(*CS.getInstruction());
1415       return;
1416     }
1417     case DataFlowSanitizer::WK_Custom: {
1418       // Don't try to handle invokes of custom functions, it's too complicated.
1419       // Instead, invoke the dfsw$ wrapper, which will in turn call the __dfsw_
1420       // wrapper.
1421       if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) {
1422         FunctionType *FT = F->getFunctionType();
1423         FunctionType *CustomFT = DFSF.DFS.getCustomFunctionType(FT);
1424         std::string CustomFName = "__dfsw_";
1425         CustomFName += F->getName();
1426         Constant *CustomF =
1427             DFSF.DFS.Mod->getOrInsertFunction(CustomFName, CustomFT);
1428         if (Function *CustomFn = dyn_cast<Function>(CustomF)) {
1429           CustomFn->copyAttributesFrom(F);
1430
1431           // Custom functions returning non-void will write to the return label.
1432           if (!FT->getReturnType()->isVoidTy()) {
1433             CustomFn->removeAttributes(AttributeSet::FunctionIndex,
1434                                        DFSF.DFS.ReadOnlyNoneAttrs);
1435           }
1436         }
1437
1438         std::vector<Value *> Args;
1439
1440         CallSite::arg_iterator i = CS.arg_begin();
1441         for (unsigned n = FT->getNumParams(); n != 0; ++i, --n) {
1442           Type *T = (*i)->getType();
1443           FunctionType *ParamFT;
1444           if (isa<PointerType>(T) &&
1445               (ParamFT = dyn_cast<FunctionType>(
1446                    cast<PointerType>(T)->getElementType()))) {
1447             std::string TName = "dfst";
1448             TName += utostr(FT->getNumParams() - n);
1449             TName += "$";
1450             TName += F->getName();
1451             Constant *T = DFSF.DFS.getOrBuildTrampolineFunction(ParamFT, TName);
1452             Args.push_back(T);
1453             Args.push_back(
1454                 IRB.CreateBitCast(*i, Type::getInt8PtrTy(*DFSF.DFS.Ctx)));
1455           } else {
1456             Args.push_back(*i);
1457           }
1458         }
1459
1460         i = CS.arg_begin();
1461         for (unsigned n = FT->getNumParams(); n != 0; ++i, --n)
1462           Args.push_back(DFSF.getShadow(*i));
1463
1464         if (FT->isVarArg()) {
1465           auto LabelVAAlloca =
1466               new AllocaInst(ArrayType::get(DFSF.DFS.ShadowTy,
1467                                             CS.arg_size() - FT->getNumParams()),
1468                              "labelva", DFSF.F->getEntryBlock().begin());
1469
1470           for (unsigned n = 0; i != CS.arg_end(); ++i, ++n) {
1471             auto LabelVAPtr = IRB.CreateStructGEP(LabelVAAlloca, n);
1472             IRB.CreateStore(DFSF.getShadow(*i), LabelVAPtr);
1473           }
1474
1475           Args.push_back(IRB.CreateStructGEP(LabelVAAlloca, 0));
1476         }
1477
1478         if (!FT->getReturnType()->isVoidTy()) {
1479           if (!DFSF.LabelReturnAlloca) {
1480             DFSF.LabelReturnAlloca =
1481                 new AllocaInst(DFSF.DFS.ShadowTy, "labelreturn",
1482                                DFSF.F->getEntryBlock().begin());
1483           }
1484           Args.push_back(DFSF.LabelReturnAlloca);
1485         }
1486
1487         for (i = CS.arg_begin() + FT->getNumParams(); i != CS.arg_end(); ++i)
1488           Args.push_back(*i);
1489
1490         CallInst *CustomCI = IRB.CreateCall(CustomF, Args);
1491         CustomCI->setCallingConv(CI->getCallingConv());
1492         CustomCI->setAttributes(CI->getAttributes());
1493
1494         if (!FT->getReturnType()->isVoidTy()) {
1495           LoadInst *LabelLoad = IRB.CreateLoad(DFSF.LabelReturnAlloca);
1496           DFSF.setShadow(CustomCI, LabelLoad);
1497         }
1498
1499         CI->replaceAllUsesWith(CustomCI);
1500         CI->eraseFromParent();
1501         return;
1502       }
1503       break;
1504     }
1505     }
1506   }
1507
1508   FunctionType *FT = cast<FunctionType>(
1509       CS.getCalledValue()->getType()->getPointerElementType());
1510   if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) {
1511     for (unsigned i = 0, n = FT->getNumParams(); i != n; ++i) {
1512       IRB.CreateStore(DFSF.getShadow(CS.getArgument(i)),
1513                       DFSF.getArgTLS(i, CS.getInstruction()));
1514     }
1515   }
1516
1517   Instruction *Next = nullptr;
1518   if (!CS.getType()->isVoidTy()) {
1519     if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) {
1520       if (II->getNormalDest()->getSinglePredecessor()) {
1521         Next = II->getNormalDest()->begin();
1522       } else {
1523         BasicBlock *NewBB =
1524             SplitEdge(II->getParent(), II->getNormalDest(), &DFSF.DFS);
1525         Next = NewBB->begin();
1526       }
1527     } else {
1528       Next = CS->getNextNode();
1529     }
1530
1531     if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) {
1532       IRBuilder<> NextIRB(Next);
1533       LoadInst *LI = NextIRB.CreateLoad(DFSF.getRetvalTLS());
1534       DFSF.SkipInsts.insert(LI);
1535       DFSF.setShadow(CS.getInstruction(), LI);
1536       DFSF.NonZeroChecks.push_back(LI);
1537     }
1538   }
1539
1540   // Do all instrumentation for IA_Args down here to defer tampering with the
1541   // CFG in a way that SplitEdge may be able to detect.
1542   if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_Args) {
1543     FunctionType *NewFT = DFSF.DFS.getArgsFunctionType(FT);
1544     Value *Func =
1545         IRB.CreateBitCast(CS.getCalledValue(), PointerType::getUnqual(NewFT));
1546     std::vector<Value *> Args;
1547
1548     CallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end();
1549     for (unsigned n = FT->getNumParams(); n != 0; ++i, --n)
1550       Args.push_back(*i);
1551
1552     i = CS.arg_begin();
1553     for (unsigned n = FT->getNumParams(); n != 0; ++i, --n)
1554       Args.push_back(DFSF.getShadow(*i));
1555
1556     if (FT->isVarArg()) {
1557       unsigned VarArgSize = CS.arg_size() - FT->getNumParams();
1558       ArrayType *VarArgArrayTy = ArrayType::get(DFSF.DFS.ShadowTy, VarArgSize);
1559       AllocaInst *VarArgShadow =
1560           new AllocaInst(VarArgArrayTy, "", DFSF.F->getEntryBlock().begin());
1561       Args.push_back(IRB.CreateConstGEP2_32(VarArgShadow, 0, 0));
1562       for (unsigned n = 0; i != e; ++i, ++n) {
1563         IRB.CreateStore(DFSF.getShadow(*i),
1564                         IRB.CreateConstGEP2_32(VarArgShadow, 0, n));
1565         Args.push_back(*i);
1566       }
1567     }
1568
1569     CallSite NewCS;
1570     if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) {
1571       NewCS = IRB.CreateInvoke(Func, II->getNormalDest(), II->getUnwindDest(),
1572                                Args);
1573     } else {
1574       NewCS = IRB.CreateCall(Func, Args);
1575     }
1576     NewCS.setCallingConv(CS.getCallingConv());
1577     NewCS.setAttributes(CS.getAttributes().removeAttributes(
1578         *DFSF.DFS.Ctx, AttributeSet::ReturnIndex,
1579         AttributeFuncs::typeIncompatible(NewCS.getInstruction()->getType(),
1580                                          AttributeSet::ReturnIndex)));
1581
1582     if (Next) {
1583       ExtractValueInst *ExVal =
1584           ExtractValueInst::Create(NewCS.getInstruction(), 0, "", Next);
1585       DFSF.SkipInsts.insert(ExVal);
1586       ExtractValueInst *ExShadow =
1587           ExtractValueInst::Create(NewCS.getInstruction(), 1, "", Next);
1588       DFSF.SkipInsts.insert(ExShadow);
1589       DFSF.setShadow(ExVal, ExShadow);
1590       DFSF.NonZeroChecks.push_back(ExShadow);
1591
1592       CS.getInstruction()->replaceAllUsesWith(ExVal);
1593     }
1594
1595     CS.getInstruction()->eraseFromParent();
1596   }
1597 }
1598
1599 void DFSanVisitor::visitPHINode(PHINode &PN) {
1600   PHINode *ShadowPN =
1601       PHINode::Create(DFSF.DFS.ShadowTy, PN.getNumIncomingValues(), "", &PN);
1602
1603   // Give the shadow phi node valid predecessors to fool SplitEdge into working.
1604   Value *UndefShadow = UndefValue::get(DFSF.DFS.ShadowTy);
1605   for (PHINode::block_iterator i = PN.block_begin(), e = PN.block_end(); i != e;
1606        ++i) {
1607     ShadowPN->addIncoming(UndefShadow, *i);
1608   }
1609
1610   DFSF.PHIFixups.push_back(std::make_pair(&PN, ShadowPN));
1611   DFSF.setShadow(&PN, ShadowPN);
1612 }