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