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