DataFlowSanitizer.cpp revision ef8136dda15f6b57b8633cdcc0e2b78a944e2b5d 
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/Analysis/ValueTracking.h"
52#include "llvm/IR/InlineAsm.h"
53#include "llvm/IR/IRBuilder.h"
54#include "llvm/IR/LLVMContext.h"
55#include "llvm/IR/MDBuilder.h"
56#include "llvm/IR/Type.h"
57#include "llvm/IR/Value.h"
58#include "llvm/InstVisitor.h"
59#include "llvm/Pass.h"
60#include "llvm/Support/CommandLine.h"
61#include "llvm/Transforms/Utils/BasicBlockUtils.h"
62#include "llvm/Transforms/Utils/Local.h"
63#include "llvm/Transforms/Utils/SpecialCaseList.h"
64#include <iterator>
65
66using namespace llvm;
67
68// The -dfsan-preserve-alignment flag controls whether this pass assumes that
69// alignment requirements provided by the input IR are correct.  For example,
70// if the input IR contains a load with alignment 8, this flag will cause
71// the shadow load to have alignment 16.  This flag is disabled by default as
72// we have unfortunately encountered too much code (including Clang itself;
73// see PR14291) which performs misaligned access.
74static cl::opt<bool> ClPreserveAlignment(
75    "dfsan-preserve-alignment",
76    cl::desc("respect alignment requirements provided by input IR"), cl::Hidden,
77    cl::init(false));
78
79// The ABI list file controls how shadow parameters are passed.  The pass treats
80// every function labelled "uninstrumented" in the ABI list file as conforming
81// to the "native" (i.e. unsanitized) ABI.  Unless the ABI list contains
82// additional annotations for those functions, a call to one of those functions
83// will produce a warning message, as the labelling behaviour of the function is
84// unknown.  The other supported annotations are "functional" and "discard",
85// which are described below under DataFlowSanitizer::WrapperKind.
86static cl::opt<std::string> ClABIListFile(
87    "dfsan-abilist",
88    cl::desc("File listing native ABI functions and how the pass treats them"),
89    cl::Hidden);
90
91// Controls whether the pass uses IA_Args or IA_TLS as the ABI for instrumented
92// functions (see DataFlowSanitizer::InstrumentedABI below).
93static cl::opt<bool> ClArgsABI(
94    "dfsan-args-abi",
95    cl::desc("Use the argument ABI rather than the TLS ABI"),
96    cl::Hidden);
97
98namespace {
99
100class DataFlowSanitizer : public ModulePass {
101  friend struct DFSanFunction;
102  friend class DFSanVisitor;
103
104  enum {
105    ShadowWidth = 16
106  };
107
108  /// Which ABI should be used for instrumented functions?
109  enum InstrumentedABI {
110    /// Argument and return value labels are passed through additional
111    /// arguments and by modifying the return type.
112    IA_Args,
113
114    /// Argument and return value labels are passed through TLS variables
115    /// __dfsan_arg_tls and __dfsan_retval_tls.
116    IA_TLS
117  };
118
119  /// How should calls to uninstrumented functions be handled?
120  enum WrapperKind {
121    /// This function is present in an uninstrumented form but we don't know
122    /// how it should be handled.  Print a warning and call the function anyway.
123    /// Don't label the return value.
124    WK_Warning,
125
126    /// This function does not write to (user-accessible) memory, and its return
127    /// value is unlabelled.
128    WK_Discard,
129
130    /// This function does not write to (user-accessible) memory, and the label
131    /// of its return value is the union of the label of its arguments.
132    WK_Functional,
133
134    /// Instead of calling the function, a custom wrapper __dfsw_F is called,
135    /// where F is the name of the function.  This function may wrap the
136    /// original function or provide its own implementation.  This is similar to
137    /// the IA_Args ABI, except that IA_Args uses a struct return type to
138    /// pass the return value shadow in a register, while WK_Custom uses an
139    /// extra pointer argument to return the shadow.  This allows the wrapped
140    /// form of the function type to be expressed in C.
141    WK_Custom
142  };
143
144  DataLayout *DL;
145  Module *Mod;
146  LLVMContext *Ctx;
147  IntegerType *ShadowTy;
148  PointerType *ShadowPtrTy;
149  IntegerType *IntptrTy;
150  ConstantInt *ZeroShadow;
151  ConstantInt *ShadowPtrMask;
152  ConstantInt *ShadowPtrMul;
153  Constant *ArgTLS;
154  Constant *RetvalTLS;
155  void *(*GetArgTLSPtr)();
156  void *(*GetRetvalTLSPtr)();
157  Constant *GetArgTLS;
158  Constant *GetRetvalTLS;
159  FunctionType *DFSanUnionFnTy;
160  FunctionType *DFSanUnionLoadFnTy;
161  FunctionType *DFSanUnimplementedFnTy;
162  FunctionType *DFSanSetLabelFnTy;
163  Constant *DFSanUnionFn;
164  Constant *DFSanUnionLoadFn;
165  Constant *DFSanUnimplementedFn;
166  Constant *DFSanSetLabelFn;
167  MDNode *ColdCallWeights;
168  OwningPtr<SpecialCaseList> ABIList;
169  DenseMap<Value *, Function *> UnwrappedFnMap;
170  AttributeSet ReadOnlyNoneAttrs;
171
172  Value *getShadowAddress(Value *Addr, Instruction *Pos);
173  Value *combineShadows(Value *V1, Value *V2, Instruction *Pos);
174  bool isInstrumented(Function *F);
175  FunctionType *getArgsFunctionType(FunctionType *T);
176  FunctionType *getCustomFunctionType(FunctionType *T);
177  InstrumentedABI getInstrumentedABI();
178  WrapperKind getWrapperKind(Function *F);
179
180 public:
181  DataFlowSanitizer(StringRef ABIListFile = StringRef(),
182                    void *(*getArgTLS)() = 0, void *(*getRetValTLS)() = 0);
183  static char ID;
184  bool doInitialization(Module &M);
185  bool runOnModule(Module &M);
186};
187
188struct DFSanFunction {
189  DataFlowSanitizer &DFS;
190  Function *F;
191  DataFlowSanitizer::InstrumentedABI IA;
192  bool IsNativeABI;
193  Value *ArgTLSPtr;
194  Value *RetvalTLSPtr;
195  AllocaInst *LabelReturnAlloca;
196  DenseMap<Value *, Value *> ValShadowMap;
197  DenseMap<AllocaInst *, AllocaInst *> AllocaShadowMap;
198  std::vector<std::pair<PHINode *, PHINode *> > PHIFixups;
199  DenseSet<Instruction *> SkipInsts;
200
201  DFSanFunction(DataFlowSanitizer &DFS, Function *F, bool IsNativeABI)
202      : DFS(DFS), F(F), IA(DFS.getInstrumentedABI()),
203        IsNativeABI(IsNativeABI), ArgTLSPtr(0), RetvalTLSPtr(0),
204        LabelReturnAlloca(0) {}
205  Value *getArgTLSPtr();
206  Value *getArgTLS(unsigned Index, Instruction *Pos);
207  Value *getRetvalTLS();
208  Value *getShadow(Value *V);
209  void setShadow(Instruction *I, Value *Shadow);
210  Value *combineOperandShadows(Instruction *Inst);
211  Value *loadShadow(Value *ShadowAddr, uint64_t Size, uint64_t Align,
212                    Instruction *Pos);
213  void storeShadow(Value *Addr, uint64_t Size, uint64_t Align, Value *Shadow,
214                   Instruction *Pos);
215};
216
217class DFSanVisitor : public InstVisitor<DFSanVisitor> {
218 public:
219  DFSanFunction &DFSF;
220  DFSanVisitor(DFSanFunction &DFSF) : DFSF(DFSF) {}
221
222  void visitOperandShadowInst(Instruction &I);
223
224  void visitBinaryOperator(BinaryOperator &BO);
225  void visitCastInst(CastInst &CI);
226  void visitCmpInst(CmpInst &CI);
227  void visitGetElementPtrInst(GetElementPtrInst &GEPI);
228  void visitLoadInst(LoadInst &LI);
229  void visitStoreInst(StoreInst &SI);
230  void visitReturnInst(ReturnInst &RI);
231  void visitCallSite(CallSite CS);
232  void visitPHINode(PHINode &PN);
233  void visitExtractElementInst(ExtractElementInst &I);
234  void visitInsertElementInst(InsertElementInst &I);
235  void visitShuffleVectorInst(ShuffleVectorInst &I);
236  void visitExtractValueInst(ExtractValueInst &I);
237  void visitInsertValueInst(InsertValueInst &I);
238  void visitAllocaInst(AllocaInst &I);
239  void visitSelectInst(SelectInst &I);
240  void visitMemSetInst(MemSetInst &I);
241  void visitMemTransferInst(MemTransferInst &I);
242};
243
244}
245
246char DataFlowSanitizer::ID;
247INITIALIZE_PASS(DataFlowSanitizer, "dfsan",
248                "DataFlowSanitizer: dynamic data flow analysis.", false, false)
249
250ModulePass *llvm::createDataFlowSanitizerPass(StringRef ABIListFile,
251                                              void *(*getArgTLS)(),
252                                              void *(*getRetValTLS)()) {
253  return new DataFlowSanitizer(ABIListFile, getArgTLS, getRetValTLS);
254}
255
256DataFlowSanitizer::DataFlowSanitizer(StringRef ABIListFile,
257                                     void *(*getArgTLS)(),
258                                     void *(*getRetValTLS)())
259    : ModulePass(ID), GetArgTLSPtr(getArgTLS), GetRetvalTLSPtr(getRetValTLS),
260      ABIList(SpecialCaseList::createOrDie(ABIListFile.empty() ? ClABIListFile
261                                                               : ABIListFile)) {
262}
263
264FunctionType *DataFlowSanitizer::getArgsFunctionType(FunctionType *T) {
265  llvm::SmallVector<Type *, 4> ArgTypes;
266  std::copy(T->param_begin(), T->param_end(), std::back_inserter(ArgTypes));
267  for (unsigned i = 0, e = T->getNumParams(); i != e; ++i)
268    ArgTypes.push_back(ShadowTy);
269  if (T->isVarArg())
270    ArgTypes.push_back(ShadowPtrTy);
271  Type *RetType = T->getReturnType();
272  if (!RetType->isVoidTy())
273    RetType = StructType::get(RetType, ShadowTy, (Type *)0);
274  return FunctionType::get(RetType, ArgTypes, T->isVarArg());
275}
276
277FunctionType *DataFlowSanitizer::getCustomFunctionType(FunctionType *T) {
278  assert(!T->isVarArg());
279  llvm::SmallVector<Type *, 4> ArgTypes;
280  std::copy(T->param_begin(), T->param_end(), std::back_inserter(ArgTypes));
281  for (unsigned i = 0, e = T->getNumParams(); i != e; ++i)
282    ArgTypes.push_back(ShadowTy);
283  Type *RetType = T->getReturnType();
284  if (!RetType->isVoidTy())
285    ArgTypes.push_back(ShadowPtrTy);
286  return FunctionType::get(T->getReturnType(), ArgTypes, false);
287}
288
289bool DataFlowSanitizer::doInitialization(Module &M) {
290  DL = getAnalysisIfAvailable<DataLayout>();
291  if (!DL)
292    return false;
293
294  Mod = &M;
295  Ctx = &M.getContext();
296  ShadowTy = IntegerType::get(*Ctx, ShadowWidth);
297  ShadowPtrTy = PointerType::getUnqual(ShadowTy);
298  IntptrTy = DL->getIntPtrType(*Ctx);
299  ZeroShadow = ConstantInt::getSigned(ShadowTy, 0);
300  ShadowPtrMask = ConstantInt::getSigned(IntptrTy, ~0x700000000000LL);
301  ShadowPtrMul = ConstantInt::getSigned(IntptrTy, ShadowWidth / 8);
302
303  Type *DFSanUnionArgs[2] = { ShadowTy, ShadowTy };
304  DFSanUnionFnTy =
305      FunctionType::get(ShadowTy, DFSanUnionArgs, /*isVarArg=*/ false);
306  Type *DFSanUnionLoadArgs[2] = { ShadowPtrTy, IntptrTy };
307  DFSanUnionLoadFnTy =
308      FunctionType::get(ShadowTy, DFSanUnionLoadArgs, /*isVarArg=*/ false);
309  DFSanUnimplementedFnTy = FunctionType::get(
310      Type::getVoidTy(*Ctx), Type::getInt8PtrTy(*Ctx), /*isVarArg=*/false);
311  Type *DFSanSetLabelArgs[3] = { ShadowTy, Type::getInt8PtrTy(*Ctx), IntptrTy };
312  DFSanSetLabelFnTy = FunctionType::get(Type::getVoidTy(*Ctx),
313                                        DFSanSetLabelArgs, /*isVarArg=*/false);
314
315  if (GetArgTLSPtr) {
316    Type *ArgTLSTy = ArrayType::get(ShadowTy, 64);
317    ArgTLS = 0;
318    GetArgTLS = ConstantExpr::getIntToPtr(
319        ConstantInt::get(IntptrTy, uintptr_t(GetArgTLSPtr)),
320        PointerType::getUnqual(
321            FunctionType::get(PointerType::getUnqual(ArgTLSTy), (Type *)0)));
322  }
323  if (GetRetvalTLSPtr) {
324    RetvalTLS = 0;
325    GetRetvalTLS = ConstantExpr::getIntToPtr(
326        ConstantInt::get(IntptrTy, uintptr_t(GetRetvalTLSPtr)),
327        PointerType::getUnqual(
328            FunctionType::get(PointerType::getUnqual(ShadowTy), (Type *)0)));
329  }
330
331  ColdCallWeights = MDBuilder(*Ctx).createBranchWeights(1, 1000);
332  return true;
333}
334
335bool DataFlowSanitizer::isInstrumented(Function *F) {
336  return !ABIList->isIn(*F, "uninstrumented");
337}
338
339DataFlowSanitizer::InstrumentedABI DataFlowSanitizer::getInstrumentedABI() {
340  return ClArgsABI ? IA_Args : IA_TLS;
341}
342
343DataFlowSanitizer::WrapperKind DataFlowSanitizer::getWrapperKind(Function *F) {
344  if (ABIList->isIn(*F, "functional"))
345    return WK_Functional;
346  if (ABIList->isIn(*F, "discard"))
347    return WK_Discard;
348  if (ABIList->isIn(*F, "custom"))
349    return WK_Custom;
350
351  return WK_Warning;
352}
353
354bool DataFlowSanitizer::runOnModule(Module &M) {
355  if (!DL)
356    return false;
357
358  if (ABIList->isIn(M, "skip"))
359    return false;
360
361  if (!GetArgTLSPtr) {
362    Type *ArgTLSTy = ArrayType::get(ShadowTy, 64);
363    ArgTLS = Mod->getOrInsertGlobal("__dfsan_arg_tls", ArgTLSTy);
364    if (GlobalVariable *G = dyn_cast<GlobalVariable>(ArgTLS))
365      G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel);
366  }
367  if (!GetRetvalTLSPtr) {
368    RetvalTLS = Mod->getOrInsertGlobal("__dfsan_retval_tls", ShadowTy);
369    if (GlobalVariable *G = dyn_cast<GlobalVariable>(RetvalTLS))
370      G->setThreadLocalMode(GlobalVariable::InitialExecTLSModel);
371  }
372
373  DFSanUnionFn = Mod->getOrInsertFunction("__dfsan_union", DFSanUnionFnTy);
374  if (Function *F = dyn_cast<Function>(DFSanUnionFn)) {
375    F->addAttribute(AttributeSet::FunctionIndex, Attribute::ReadNone);
376    F->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
377    F->addAttribute(1, Attribute::ZExt);
378    F->addAttribute(2, Attribute::ZExt);
379  }
380  DFSanUnionLoadFn =
381      Mod->getOrInsertFunction("__dfsan_union_load", DFSanUnionLoadFnTy);
382  if (Function *F = dyn_cast<Function>(DFSanUnionLoadFn)) {
383    F->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
384  }
385  DFSanUnimplementedFn =
386      Mod->getOrInsertFunction("__dfsan_unimplemented", DFSanUnimplementedFnTy);
387  DFSanSetLabelFn =
388      Mod->getOrInsertFunction("__dfsan_set_label", DFSanSetLabelFnTy);
389  if (Function *F = dyn_cast<Function>(DFSanSetLabelFn)) {
390    F->addAttribute(1, Attribute::ZExt);
391  }
392
393  std::vector<Function *> FnsToInstrument;
394  llvm::SmallPtrSet<Function *, 2> FnsWithNativeABI;
395  for (Module::iterator i = M.begin(), e = M.end(); i != e; ++i) {
396    if (!i->isIntrinsic() &&
397        i != DFSanUnionFn &&
398        i != DFSanUnionLoadFn &&
399        i != DFSanUnimplementedFn &&
400        i != DFSanSetLabelFn)
401      FnsToInstrument.push_back(&*i);
402  }
403
404  AttrBuilder B;
405  B.addAttribute(Attribute::ReadOnly).addAttribute(Attribute::ReadNone);
406  ReadOnlyNoneAttrs = AttributeSet::get(*Ctx, AttributeSet::FunctionIndex, B);
407
408  // First, change the ABI of every function in the module.  ABI-listed
409  // functions keep their original ABI and get a wrapper function.
410  for (std::vector<Function *>::iterator i = FnsToInstrument.begin(),
411                                         e = FnsToInstrument.end();
412       i != e; ++i) {
413    Function &F = **i;
414    FunctionType *FT = F.getFunctionType();
415
416    if (FT->getNumParams() == 0 && !FT->isVarArg() &&
417        FT->getReturnType()->isVoidTy())
418      continue;
419
420    if (isInstrumented(&F)) {
421      if (getInstrumentedABI() == IA_Args) {
422        FunctionType *NewFT = getArgsFunctionType(FT);
423        Function *NewF = Function::Create(NewFT, F.getLinkage(), "", &M);
424        NewF->copyAttributesFrom(&F);
425        NewF->removeAttributes(
426            AttributeSet::ReturnIndex,
427            AttributeFuncs::typeIncompatible(NewFT->getReturnType(),
428                                             AttributeSet::ReturnIndex));
429        for (Function::arg_iterator FArg = F.arg_begin(),
430                                    NewFArg = NewF->arg_begin(),
431                                    FArgEnd = F.arg_end();
432             FArg != FArgEnd; ++FArg, ++NewFArg) {
433          FArg->replaceAllUsesWith(NewFArg);
434        }
435        NewF->getBasicBlockList().splice(NewF->begin(), F.getBasicBlockList());
436
437        for (Function::use_iterator ui = F.use_begin(), ue = F.use_end();
438             ui != ue;) {
439          BlockAddress *BA = dyn_cast<BlockAddress>(ui.getUse().getUser());
440          ++ui;
441          if (BA) {
442            BA->replaceAllUsesWith(
443                BlockAddress::get(NewF, BA->getBasicBlock()));
444            delete BA;
445          }
446        }
447        F.replaceAllUsesWith(
448            ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT)));
449        NewF->takeName(&F);
450        F.eraseFromParent();
451        *i = NewF;
452      }
453               // Hopefully, nobody will try to indirectly call a vararg
454               // function... yet.
455    } else if (FT->isVarArg()) {
456      UnwrappedFnMap[&F] = &F;
457      *i = 0;
458    } else {
459      // Build a wrapper function for F.  The wrapper simply calls F, and is
460      // added to FnsToInstrument so that any instrumentation according to its
461      // WrapperKind is done in the second pass below.
462      FunctionType *NewFT = getInstrumentedABI() == IA_Args
463                                ? getArgsFunctionType(FT)
464                                : FT;
465      Function *NewF =
466          Function::Create(NewFT, GlobalValue::LinkOnceODRLinkage,
467                           std::string("dfsw$") + F.getName(), &M);
468      NewF->copyAttributesFrom(&F);
469      NewF->removeAttributes(
470              AttributeSet::ReturnIndex,
471              AttributeFuncs::typeIncompatible(NewFT->getReturnType(),
472                                               AttributeSet::ReturnIndex));
473      if (getInstrumentedABI() == IA_TLS)
474        NewF->removeAttributes(AttributeSet::FunctionIndex,
475                               ReadOnlyNoneAttrs);
476
477      BasicBlock *BB = BasicBlock::Create(*Ctx, "entry", NewF);
478      std::vector<Value *> Args;
479      unsigned n = FT->getNumParams();
480      for (Function::arg_iterator ai = NewF->arg_begin(); n != 0; ++ai, --n)
481        Args.push_back(&*ai);
482      CallInst *CI = CallInst::Create(&F, Args, "", BB);
483      if (FT->getReturnType()->isVoidTy())
484        ReturnInst::Create(*Ctx, BB);
485      else
486        ReturnInst::Create(*Ctx, CI, BB);
487
488      Value *WrappedFnCst =
489          ConstantExpr::getBitCast(NewF, PointerType::getUnqual(FT));
490      F.replaceAllUsesWith(WrappedFnCst);
491      UnwrappedFnMap[WrappedFnCst] = &F;
492      *i = NewF;
493
494      if (!F.isDeclaration()) {
495        // This function is probably defining an interposition of an
496        // uninstrumented function and hence needs to keep the original ABI.
497        // But any functions it may call need to use the instrumented ABI, so
498        // we instrument it in a mode which preserves the original ABI.
499        FnsWithNativeABI.insert(&F);
500
501        // This code needs to rebuild the iterators, as they may be invalidated
502        // by the push_back, taking care that the new range does not include
503        // any functions added by this code.
504        size_t N = i - FnsToInstrument.begin(),
505               Count = e - FnsToInstrument.begin();
506        FnsToInstrument.push_back(&F);
507        i = FnsToInstrument.begin() + N;
508        e = FnsToInstrument.begin() + Count;
509      }
510    }
511  }
512
513  for (std::vector<Function *>::iterator i = FnsToInstrument.begin(),
514                                         e = FnsToInstrument.end();
515       i != e; ++i) {
516    if (!*i || (*i)->isDeclaration())
517      continue;
518
519    removeUnreachableBlocks(**i);
520
521    DFSanFunction DFSF(*this, *i, FnsWithNativeABI.count(*i));
522
523    // DFSanVisitor may create new basic blocks, which confuses df_iterator.
524    // Build a copy of the list before iterating over it.
525    llvm::SmallVector<BasicBlock *, 4> BBList;
526    std::copy(df_begin(&(*i)->getEntryBlock()), df_end(&(*i)->getEntryBlock()),
527              std::back_inserter(BBList));
528
529    for (llvm::SmallVector<BasicBlock *, 4>::iterator i = BBList.begin(),
530                                                      e = BBList.end();
531         i != e; ++i) {
532      Instruction *Inst = &(*i)->front();
533      while (1) {
534        // DFSanVisitor may split the current basic block, changing the current
535        // instruction's next pointer and moving the next instruction to the
536        // tail block from which we should continue.
537        Instruction *Next = Inst->getNextNode();
538        // DFSanVisitor may delete Inst, so keep track of whether it was a
539        // terminator.
540        bool IsTerminator = isa<TerminatorInst>(Inst);
541        if (!DFSF.SkipInsts.count(Inst))
542          DFSanVisitor(DFSF).visit(Inst);
543        if (IsTerminator)
544          break;
545        Inst = Next;
546      }
547    }
548
549    // We will not necessarily be able to compute the shadow for every phi node
550    // until we have visited every block.  Therefore, the code that handles phi
551    // nodes adds them to the PHIFixups list so that they can be properly
552    // handled here.
553    for (std::vector<std::pair<PHINode *, PHINode *> >::iterator
554             i = DFSF.PHIFixups.begin(),
555             e = DFSF.PHIFixups.end();
556         i != e; ++i) {
557      for (unsigned val = 0, n = i->first->getNumIncomingValues(); val != n;
558           ++val) {
559        i->second->setIncomingValue(
560            val, DFSF.getShadow(i->first->getIncomingValue(val)));
561      }
562    }
563  }
564
565  return false;
566}
567
568Value *DFSanFunction::getArgTLSPtr() {
569  if (ArgTLSPtr)
570    return ArgTLSPtr;
571  if (DFS.ArgTLS)
572    return ArgTLSPtr = DFS.ArgTLS;
573
574  IRBuilder<> IRB(F->getEntryBlock().begin());
575  return ArgTLSPtr = IRB.CreateCall(DFS.GetArgTLS);
576}
577
578Value *DFSanFunction::getRetvalTLS() {
579  if (RetvalTLSPtr)
580    return RetvalTLSPtr;
581  if (DFS.RetvalTLS)
582    return RetvalTLSPtr = DFS.RetvalTLS;
583
584  IRBuilder<> IRB(F->getEntryBlock().begin());
585  return RetvalTLSPtr = IRB.CreateCall(DFS.GetRetvalTLS);
586}
587
588Value *DFSanFunction::getArgTLS(unsigned Idx, Instruction *Pos) {
589  IRBuilder<> IRB(Pos);
590  return IRB.CreateConstGEP2_64(getArgTLSPtr(), 0, Idx);
591}
592
593Value *DFSanFunction::getShadow(Value *V) {
594  if (!isa<Argument>(V) && !isa<Instruction>(V))
595    return DFS.ZeroShadow;
596  Value *&Shadow = ValShadowMap[V];
597  if (!Shadow) {
598    if (Argument *A = dyn_cast<Argument>(V)) {
599      if (IsNativeABI)
600        return DFS.ZeroShadow;
601      switch (IA) {
602      case DataFlowSanitizer::IA_TLS: {
603        Value *ArgTLSPtr = getArgTLSPtr();
604        Instruction *ArgTLSPos =
605            DFS.ArgTLS ? &*F->getEntryBlock().begin()
606                       : cast<Instruction>(ArgTLSPtr)->getNextNode();
607        IRBuilder<> IRB(ArgTLSPos);
608        Shadow = IRB.CreateLoad(getArgTLS(A->getArgNo(), ArgTLSPos));
609        break;
610      }
611      case DataFlowSanitizer::IA_Args: {
612        unsigned ArgIdx = A->getArgNo() + F->getArgumentList().size() / 2;
613        Function::arg_iterator i = F->arg_begin();
614        while (ArgIdx--)
615          ++i;
616        Shadow = i;
617        assert(Shadow->getType() == DFS.ShadowTy);
618        break;
619      }
620      }
621    } else {
622      Shadow = DFS.ZeroShadow;
623    }
624  }
625  return Shadow;
626}
627
628void DFSanFunction::setShadow(Instruction *I, Value *Shadow) {
629  assert(!ValShadowMap.count(I));
630  assert(Shadow->getType() == DFS.ShadowTy);
631  ValShadowMap[I] = Shadow;
632}
633
634Value *DataFlowSanitizer::getShadowAddress(Value *Addr, Instruction *Pos) {
635  assert(Addr != RetvalTLS && "Reinstrumenting?");
636  IRBuilder<> IRB(Pos);
637  return IRB.CreateIntToPtr(
638      IRB.CreateMul(
639          IRB.CreateAnd(IRB.CreatePtrToInt(Addr, IntptrTy), ShadowPtrMask),
640          ShadowPtrMul),
641      ShadowPtrTy);
642}
643
644// Generates IR to compute the union of the two given shadows, inserting it
645// before Pos.  Returns the computed union Value.
646Value *DataFlowSanitizer::combineShadows(Value *V1, Value *V2,
647                                         Instruction *Pos) {
648  if (V1 == ZeroShadow)
649    return V2;
650  if (V2 == ZeroShadow)
651    return V1;
652  if (V1 == V2)
653    return V1;
654  IRBuilder<> IRB(Pos);
655  BasicBlock *Head = Pos->getParent();
656  Value *Ne = IRB.CreateICmpNE(V1, V2);
657  Instruction *NeInst = dyn_cast<Instruction>(Ne);
658  if (NeInst) {
659    BranchInst *BI = cast<BranchInst>(SplitBlockAndInsertIfThen(
660        NeInst, /*Unreachable=*/ false, ColdCallWeights));
661    IRBuilder<> ThenIRB(BI);
662    CallInst *Call = ThenIRB.CreateCall2(DFSanUnionFn, V1, V2);
663    Call->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
664    Call->addAttribute(1, Attribute::ZExt);
665    Call->addAttribute(2, Attribute::ZExt);
666
667    BasicBlock *Tail = BI->getSuccessor(0);
668    PHINode *Phi = PHINode::Create(ShadowTy, 2, "", Tail->begin());
669    Phi->addIncoming(Call, Call->getParent());
670    Phi->addIncoming(ZeroShadow, Head);
671    Pos = Phi;
672    return Phi;
673  } else {
674    assert(0 && "todo");
675    return 0;
676  }
677}
678
679// A convenience function which folds the shadows of each of the operands
680// of the provided instruction Inst, inserting the IR before Inst.  Returns
681// the computed union Value.
682Value *DFSanFunction::combineOperandShadows(Instruction *Inst) {
683  if (Inst->getNumOperands() == 0)
684    return DFS.ZeroShadow;
685
686  Value *Shadow = getShadow(Inst->getOperand(0));
687  for (unsigned i = 1, n = Inst->getNumOperands(); i != n; ++i) {
688    Shadow = DFS.combineShadows(Shadow, getShadow(Inst->getOperand(i)), Inst);
689  }
690  return Shadow;
691}
692
693void DFSanVisitor::visitOperandShadowInst(Instruction &I) {
694  Value *CombinedShadow = DFSF.combineOperandShadows(&I);
695  DFSF.setShadow(&I, CombinedShadow);
696}
697
698// Generates IR to load shadow corresponding to bytes [Addr, Addr+Size), where
699// Addr has alignment Align, and take the union of each of those shadows.
700Value *DFSanFunction::loadShadow(Value *Addr, uint64_t Size, uint64_t Align,
701                                 Instruction *Pos) {
702  if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) {
703    llvm::DenseMap<AllocaInst *, AllocaInst *>::iterator i =
704        AllocaShadowMap.find(AI);
705    if (i != AllocaShadowMap.end()) {
706      IRBuilder<> IRB(Pos);
707      return IRB.CreateLoad(i->second);
708    }
709  }
710
711  uint64_t ShadowAlign = Align * DFS.ShadowWidth / 8;
712  SmallVector<Value *, 2> Objs;
713  GetUnderlyingObjects(Addr, Objs, DFS.DL);
714  bool AllConstants = true;
715  for (SmallVector<Value *, 2>::iterator i = Objs.begin(), e = Objs.end();
716       i != e; ++i) {
717    if (isa<Function>(*i) || isa<BlockAddress>(*i))
718      continue;
719    if (isa<GlobalVariable>(*i) && cast<GlobalVariable>(*i)->isConstant())
720      continue;
721
722    AllConstants = false;
723    break;
724  }
725  if (AllConstants)
726    return DFS.ZeroShadow;
727
728  Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos);
729  switch (Size) {
730  case 0:
731    return DFS.ZeroShadow;
732  case 1: {
733    LoadInst *LI = new LoadInst(ShadowAddr, "", Pos);
734    LI->setAlignment(ShadowAlign);
735    return LI;
736  }
737  case 2: {
738    IRBuilder<> IRB(Pos);
739    Value *ShadowAddr1 =
740        IRB.CreateGEP(ShadowAddr, ConstantInt::get(DFS.IntptrTy, 1));
741    return DFS.combineShadows(IRB.CreateAlignedLoad(ShadowAddr, ShadowAlign),
742                              IRB.CreateAlignedLoad(ShadowAddr1, ShadowAlign),
743                              Pos);
744  }
745  }
746  if (Size % (64 / DFS.ShadowWidth) == 0) {
747    // Fast path for the common case where each byte has identical shadow: load
748    // shadow 64 bits at a time, fall out to a __dfsan_union_load call if any
749    // shadow is non-equal.
750    BasicBlock *FallbackBB = BasicBlock::Create(*DFS.Ctx, "", F);
751    IRBuilder<> FallbackIRB(FallbackBB);
752    CallInst *FallbackCall = FallbackIRB.CreateCall2(
753        DFS.DFSanUnionLoadFn, ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size));
754    FallbackCall->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
755
756    // Compare each of the shadows stored in the loaded 64 bits to each other,
757    // by computing (WideShadow rotl ShadowWidth) == WideShadow.
758    IRBuilder<> IRB(Pos);
759    Value *WideAddr =
760        IRB.CreateBitCast(ShadowAddr, Type::getInt64PtrTy(*DFS.Ctx));
761    Value *WideShadow = IRB.CreateAlignedLoad(WideAddr, ShadowAlign);
762    Value *TruncShadow = IRB.CreateTrunc(WideShadow, DFS.ShadowTy);
763    Value *ShlShadow = IRB.CreateShl(WideShadow, DFS.ShadowWidth);
764    Value *ShrShadow = IRB.CreateLShr(WideShadow, 64 - DFS.ShadowWidth);
765    Value *RotShadow = IRB.CreateOr(ShlShadow, ShrShadow);
766    Value *ShadowsEq = IRB.CreateICmpEQ(WideShadow, RotShadow);
767
768    BasicBlock *Head = Pos->getParent();
769    BasicBlock *Tail = Head->splitBasicBlock(Pos);
770    // In the following code LastBr will refer to the previous basic block's
771    // conditional branch instruction, whose true successor is fixed up to point
772    // to the next block during the loop below or to the tail after the final
773    // iteration.
774    BranchInst *LastBr = BranchInst::Create(FallbackBB, FallbackBB, ShadowsEq);
775    ReplaceInstWithInst(Head->getTerminator(), LastBr);
776
777    for (uint64_t Ofs = 64 / DFS.ShadowWidth; Ofs != Size;
778         Ofs += 64 / DFS.ShadowWidth) {
779      BasicBlock *NextBB = BasicBlock::Create(*DFS.Ctx, "", F);
780      IRBuilder<> NextIRB(NextBB);
781      WideAddr = NextIRB.CreateGEP(WideAddr, ConstantInt::get(DFS.IntptrTy, 1));
782      Value *NextWideShadow = NextIRB.CreateAlignedLoad(WideAddr, ShadowAlign);
783      ShadowsEq = NextIRB.CreateICmpEQ(WideShadow, NextWideShadow);
784      LastBr->setSuccessor(0, NextBB);
785      LastBr = NextIRB.CreateCondBr(ShadowsEq, FallbackBB, FallbackBB);
786    }
787
788    LastBr->setSuccessor(0, Tail);
789    FallbackIRB.CreateBr(Tail);
790    PHINode *Shadow = PHINode::Create(DFS.ShadowTy, 2, "", &Tail->front());
791    Shadow->addIncoming(FallbackCall, FallbackBB);
792    Shadow->addIncoming(TruncShadow, LastBr->getParent());
793    return Shadow;
794  }
795
796  IRBuilder<> IRB(Pos);
797  CallInst *FallbackCall = IRB.CreateCall2(
798      DFS.DFSanUnionLoadFn, ShadowAddr, ConstantInt::get(DFS.IntptrTy, Size));
799  FallbackCall->addAttribute(AttributeSet::ReturnIndex, Attribute::ZExt);
800  return FallbackCall;
801}
802
803void DFSanVisitor::visitLoadInst(LoadInst &LI) {
804  uint64_t Size = DFSF.DFS.DL->getTypeStoreSize(LI.getType());
805  uint64_t Align;
806  if (ClPreserveAlignment) {
807    Align = LI.getAlignment();
808    if (Align == 0)
809      Align = DFSF.DFS.DL->getABITypeAlignment(LI.getType());
810  } else {
811    Align = 1;
812  }
813  IRBuilder<> IRB(&LI);
814  Value *LoadedShadow =
815      DFSF.loadShadow(LI.getPointerOperand(), Size, Align, &LI);
816  Value *PtrShadow = DFSF.getShadow(LI.getPointerOperand());
817  DFSF.setShadow(&LI, DFSF.DFS.combineShadows(LoadedShadow, PtrShadow, &LI));
818}
819
820void DFSanFunction::storeShadow(Value *Addr, uint64_t Size, uint64_t Align,
821                                Value *Shadow, Instruction *Pos) {
822  if (AllocaInst *AI = dyn_cast<AllocaInst>(Addr)) {
823    llvm::DenseMap<AllocaInst *, AllocaInst *>::iterator i =
824        AllocaShadowMap.find(AI);
825    if (i != AllocaShadowMap.end()) {
826      IRBuilder<> IRB(Pos);
827      IRB.CreateStore(Shadow, i->second);
828      return;
829    }
830  }
831
832  uint64_t ShadowAlign = Align * DFS.ShadowWidth / 8;
833  IRBuilder<> IRB(Pos);
834  Value *ShadowAddr = DFS.getShadowAddress(Addr, Pos);
835  if (Shadow == DFS.ZeroShadow) {
836    IntegerType *ShadowTy = IntegerType::get(*DFS.Ctx, Size * DFS.ShadowWidth);
837    Value *ExtZeroShadow = ConstantInt::get(ShadowTy, 0);
838    Value *ExtShadowAddr =
839        IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowTy));
840    IRB.CreateAlignedStore(ExtZeroShadow, ExtShadowAddr, ShadowAlign);
841    return;
842  }
843
844  const unsigned ShadowVecSize = 128 / DFS.ShadowWidth;
845  uint64_t Offset = 0;
846  if (Size >= ShadowVecSize) {
847    VectorType *ShadowVecTy = VectorType::get(DFS.ShadowTy, ShadowVecSize);
848    Value *ShadowVec = UndefValue::get(ShadowVecTy);
849    for (unsigned i = 0; i != ShadowVecSize; ++i) {
850      ShadowVec = IRB.CreateInsertElement(
851          ShadowVec, Shadow, ConstantInt::get(Type::getInt32Ty(*DFS.Ctx), i));
852    }
853    Value *ShadowVecAddr =
854        IRB.CreateBitCast(ShadowAddr, PointerType::getUnqual(ShadowVecTy));
855    do {
856      Value *CurShadowVecAddr = IRB.CreateConstGEP1_32(ShadowVecAddr, Offset);
857      IRB.CreateAlignedStore(ShadowVec, CurShadowVecAddr, ShadowAlign);
858      Size -= ShadowVecSize;
859      ++Offset;
860    } while (Size >= ShadowVecSize);
861    Offset *= ShadowVecSize;
862  }
863  while (Size > 0) {
864    Value *CurShadowAddr = IRB.CreateConstGEP1_32(ShadowAddr, Offset);
865    IRB.CreateAlignedStore(Shadow, CurShadowAddr, ShadowAlign);
866    --Size;
867    ++Offset;
868  }
869}
870
871void DFSanVisitor::visitStoreInst(StoreInst &SI) {
872  uint64_t Size =
873      DFSF.DFS.DL->getTypeStoreSize(SI.getValueOperand()->getType());
874  uint64_t Align;
875  if (ClPreserveAlignment) {
876    Align = SI.getAlignment();
877    if (Align == 0)
878      Align = DFSF.DFS.DL->getABITypeAlignment(SI.getValueOperand()->getType());
879  } else {
880    Align = 1;
881  }
882  DFSF.storeShadow(SI.getPointerOperand(), Size, Align,
883                   DFSF.getShadow(SI.getValueOperand()), &SI);
884}
885
886void DFSanVisitor::visitBinaryOperator(BinaryOperator &BO) {
887  visitOperandShadowInst(BO);
888}
889
890void DFSanVisitor::visitCastInst(CastInst &CI) { visitOperandShadowInst(CI); }
891
892void DFSanVisitor::visitCmpInst(CmpInst &CI) { visitOperandShadowInst(CI); }
893
894void DFSanVisitor::visitGetElementPtrInst(GetElementPtrInst &GEPI) {
895  visitOperandShadowInst(GEPI);
896}
897
898void DFSanVisitor::visitExtractElementInst(ExtractElementInst &I) {
899  visitOperandShadowInst(I);
900}
901
902void DFSanVisitor::visitInsertElementInst(InsertElementInst &I) {
903  visitOperandShadowInst(I);
904}
905
906void DFSanVisitor::visitShuffleVectorInst(ShuffleVectorInst &I) {
907  visitOperandShadowInst(I);
908}
909
910void DFSanVisitor::visitExtractValueInst(ExtractValueInst &I) {
911  visitOperandShadowInst(I);
912}
913
914void DFSanVisitor::visitInsertValueInst(InsertValueInst &I) {
915  visitOperandShadowInst(I);
916}
917
918void DFSanVisitor::visitAllocaInst(AllocaInst &I) {
919  bool AllLoadsStores = true;
920  for (Instruction::use_iterator i = I.use_begin(), e = I.use_end(); i != e;
921       ++i) {
922    if (isa<LoadInst>(*i))
923      continue;
924
925    if (StoreInst *SI = dyn_cast<StoreInst>(*i)) {
926      if (SI->getPointerOperand() == &I)
927        continue;
928    }
929
930    AllLoadsStores = false;
931    break;
932  }
933  if (AllLoadsStores) {
934    IRBuilder<> IRB(&I);
935    DFSF.AllocaShadowMap[&I] = IRB.CreateAlloca(DFSF.DFS.ShadowTy);
936  }
937  DFSF.setShadow(&I, DFSF.DFS.ZeroShadow);
938}
939
940void DFSanVisitor::visitSelectInst(SelectInst &I) {
941  Value *CondShadow = DFSF.getShadow(I.getCondition());
942  Value *TrueShadow = DFSF.getShadow(I.getTrueValue());
943  Value *FalseShadow = DFSF.getShadow(I.getFalseValue());
944
945  if (isa<VectorType>(I.getCondition()->getType())) {
946    DFSF.setShadow(
947        &I, DFSF.DFS.combineShadows(
948                CondShadow,
949                DFSF.DFS.combineShadows(TrueShadow, FalseShadow, &I), &I));
950  } else {
951    Value *ShadowSel;
952    if (TrueShadow == FalseShadow) {
953      ShadowSel = TrueShadow;
954    } else {
955      ShadowSel =
956          SelectInst::Create(I.getCondition(), TrueShadow, FalseShadow, "", &I);
957    }
958    DFSF.setShadow(&I, DFSF.DFS.combineShadows(CondShadow, ShadowSel, &I));
959  }
960}
961
962void DFSanVisitor::visitMemSetInst(MemSetInst &I) {
963  IRBuilder<> IRB(&I);
964  Value *ValShadow = DFSF.getShadow(I.getValue());
965  IRB.CreateCall3(
966      DFSF.DFS.DFSanSetLabelFn, ValShadow,
967      IRB.CreateBitCast(I.getDest(), Type::getInt8PtrTy(*DFSF.DFS.Ctx)),
968      IRB.CreateZExtOrTrunc(I.getLength(), DFSF.DFS.IntptrTy));
969}
970
971void DFSanVisitor::visitMemTransferInst(MemTransferInst &I) {
972  IRBuilder<> IRB(&I);
973  Value *DestShadow = DFSF.DFS.getShadowAddress(I.getDest(), &I);
974  Value *SrcShadow = DFSF.DFS.getShadowAddress(I.getSource(), &I);
975  Value *LenShadow = IRB.CreateMul(
976      I.getLength(),
977      ConstantInt::get(I.getLength()->getType(), DFSF.DFS.ShadowWidth / 8));
978  Value *AlignShadow;
979  if (ClPreserveAlignment) {
980    AlignShadow = IRB.CreateMul(I.getAlignmentCst(),
981                                ConstantInt::get(I.getAlignmentCst()->getType(),
982                                                 DFSF.DFS.ShadowWidth / 8));
983  } else {
984    AlignShadow = ConstantInt::get(I.getAlignmentCst()->getType(),
985                                   DFSF.DFS.ShadowWidth / 8);
986  }
987  Type *Int8Ptr = Type::getInt8PtrTy(*DFSF.DFS.Ctx);
988  DestShadow = IRB.CreateBitCast(DestShadow, Int8Ptr);
989  SrcShadow = IRB.CreateBitCast(SrcShadow, Int8Ptr);
990  IRB.CreateCall5(I.getCalledValue(), DestShadow, SrcShadow, LenShadow,
991                  AlignShadow, I.getVolatileCst());
992}
993
994void DFSanVisitor::visitReturnInst(ReturnInst &RI) {
995  if (!DFSF.IsNativeABI && RI.getReturnValue()) {
996    switch (DFSF.IA) {
997    case DataFlowSanitizer::IA_TLS: {
998      Value *S = DFSF.getShadow(RI.getReturnValue());
999      IRBuilder<> IRB(&RI);
1000      IRB.CreateStore(S, DFSF.getRetvalTLS());
1001      break;
1002    }
1003    case DataFlowSanitizer::IA_Args: {
1004      IRBuilder<> IRB(&RI);
1005      Type *RT = DFSF.F->getFunctionType()->getReturnType();
1006      Value *InsVal =
1007          IRB.CreateInsertValue(UndefValue::get(RT), RI.getReturnValue(), 0);
1008      Value *InsShadow =
1009          IRB.CreateInsertValue(InsVal, DFSF.getShadow(RI.getReturnValue()), 1);
1010      RI.setOperand(0, InsShadow);
1011      break;
1012    }
1013    }
1014  }
1015}
1016
1017void DFSanVisitor::visitCallSite(CallSite CS) {
1018  Function *F = CS.getCalledFunction();
1019  if ((F && F->isIntrinsic()) || isa<InlineAsm>(CS.getCalledValue())) {
1020    visitOperandShadowInst(*CS.getInstruction());
1021    return;
1022  }
1023
1024  IRBuilder<> IRB(CS.getInstruction());
1025
1026  DenseMap<Value *, Function *>::iterator i =
1027      DFSF.DFS.UnwrappedFnMap.find(CS.getCalledValue());
1028  if (i != DFSF.DFS.UnwrappedFnMap.end()) {
1029    Function *F = i->second;
1030    switch (DFSF.DFS.getWrapperKind(F)) {
1031    case DataFlowSanitizer::WK_Warning: {
1032      CS.setCalledFunction(F);
1033      IRB.CreateCall(DFSF.DFS.DFSanUnimplementedFn,
1034                     IRB.CreateGlobalStringPtr(F->getName()));
1035      DFSF.setShadow(CS.getInstruction(), DFSF.DFS.ZeroShadow);
1036      return;
1037    }
1038    case DataFlowSanitizer::WK_Discard: {
1039      CS.setCalledFunction(F);
1040      DFSF.setShadow(CS.getInstruction(), DFSF.DFS.ZeroShadow);
1041      return;
1042    }
1043    case DataFlowSanitizer::WK_Functional: {
1044      CS.setCalledFunction(F);
1045      visitOperandShadowInst(*CS.getInstruction());
1046      return;
1047    }
1048    case DataFlowSanitizer::WK_Custom: {
1049      // Don't try to handle invokes of custom functions, it's too complicated.
1050      // Instead, invoke the dfsw$ wrapper, which will in turn call the __dfsw_
1051      // wrapper.
1052      if (CallInst *CI = dyn_cast<CallInst>(CS.getInstruction())) {
1053        FunctionType *FT = F->getFunctionType();
1054        FunctionType *CustomFT = DFSF.DFS.getCustomFunctionType(FT);
1055        std::string CustomFName = "__dfsw_";
1056        CustomFName += F->getName();
1057        Constant *CustomF =
1058            DFSF.DFS.Mod->getOrInsertFunction(CustomFName, CustomFT);
1059        if (Function *CustomFn = dyn_cast<Function>(CustomF)) {
1060          CustomFn->copyAttributesFrom(F);
1061
1062          // Custom functions returning non-void will write to the return label.
1063          if (!FT->getReturnType()->isVoidTy()) {
1064            CustomFn->removeAttributes(AttributeSet::FunctionIndex,
1065                                       DFSF.DFS.ReadOnlyNoneAttrs);
1066          }
1067        }
1068
1069        std::vector<Value *> Args;
1070
1071        CallSite::arg_iterator i = CS.arg_begin();
1072        for (unsigned n = FT->getNumParams(); n != 0; ++i, --n)
1073          Args.push_back(*i);
1074
1075        i = CS.arg_begin();
1076        for (unsigned n = FT->getNumParams(); n != 0; ++i, --n)
1077          Args.push_back(DFSF.getShadow(*i));
1078
1079        if (!FT->getReturnType()->isVoidTy()) {
1080          if (!DFSF.LabelReturnAlloca) {
1081            DFSF.LabelReturnAlloca =
1082                new AllocaInst(DFSF.DFS.ShadowTy, "labelreturn",
1083                               DFSF.F->getEntryBlock().begin());
1084          }
1085          Args.push_back(DFSF.LabelReturnAlloca);
1086        }
1087
1088        CallInst *CustomCI = IRB.CreateCall(CustomF, Args);
1089        CustomCI->setCallingConv(CI->getCallingConv());
1090        CustomCI->setAttributes(CI->getAttributes());
1091
1092        if (!FT->getReturnType()->isVoidTy()) {
1093          LoadInst *LabelLoad = IRB.CreateLoad(DFSF.LabelReturnAlloca);
1094          DFSF.setShadow(CustomCI, LabelLoad);
1095        }
1096
1097        CI->replaceAllUsesWith(CustomCI);
1098        CI->eraseFromParent();
1099        return;
1100      }
1101      break;
1102    }
1103    }
1104  }
1105
1106  FunctionType *FT = cast<FunctionType>(
1107      CS.getCalledValue()->getType()->getPointerElementType());
1108  if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) {
1109    for (unsigned i = 0, n = FT->getNumParams(); i != n; ++i) {
1110      IRB.CreateStore(DFSF.getShadow(CS.getArgument(i)),
1111                      DFSF.getArgTLS(i, CS.getInstruction()));
1112    }
1113  }
1114
1115  Instruction *Next = 0;
1116  if (!CS.getType()->isVoidTy()) {
1117    if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) {
1118      if (II->getNormalDest()->getSinglePredecessor()) {
1119        Next = II->getNormalDest()->begin();
1120      } else {
1121        BasicBlock *NewBB =
1122            SplitEdge(II->getParent(), II->getNormalDest(), &DFSF.DFS);
1123        Next = NewBB->begin();
1124      }
1125    } else {
1126      Next = CS->getNextNode();
1127    }
1128
1129    if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_TLS) {
1130      IRBuilder<> NextIRB(Next);
1131      LoadInst *LI = NextIRB.CreateLoad(DFSF.getRetvalTLS());
1132      DFSF.SkipInsts.insert(LI);
1133      DFSF.setShadow(CS.getInstruction(), LI);
1134    }
1135  }
1136
1137  // Do all instrumentation for IA_Args down here to defer tampering with the
1138  // CFG in a way that SplitEdge may be able to detect.
1139  if (DFSF.DFS.getInstrumentedABI() == DataFlowSanitizer::IA_Args) {
1140    FunctionType *NewFT = DFSF.DFS.getArgsFunctionType(FT);
1141    Value *Func =
1142        IRB.CreateBitCast(CS.getCalledValue(), PointerType::getUnqual(NewFT));
1143    std::vector<Value *> Args;
1144
1145    CallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end();
1146    for (unsigned n = FT->getNumParams(); n != 0; ++i, --n)
1147      Args.push_back(*i);
1148
1149    i = CS.arg_begin();
1150    for (unsigned n = FT->getNumParams(); n != 0; ++i, --n)
1151      Args.push_back(DFSF.getShadow(*i));
1152
1153    if (FT->isVarArg()) {
1154      unsigned VarArgSize = CS.arg_size() - FT->getNumParams();
1155      ArrayType *VarArgArrayTy = ArrayType::get(DFSF.DFS.ShadowTy, VarArgSize);
1156      AllocaInst *VarArgShadow =
1157          new AllocaInst(VarArgArrayTy, "", DFSF.F->getEntryBlock().begin());
1158      Args.push_back(IRB.CreateConstGEP2_32(VarArgShadow, 0, 0));
1159      for (unsigned n = 0; i != e; ++i, ++n) {
1160        IRB.CreateStore(DFSF.getShadow(*i),
1161                        IRB.CreateConstGEP2_32(VarArgShadow, 0, n));
1162        Args.push_back(*i);
1163      }
1164    }
1165
1166    CallSite NewCS;
1167    if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) {
1168      NewCS = IRB.CreateInvoke(Func, II->getNormalDest(), II->getUnwindDest(),
1169                               Args);
1170    } else {
1171      NewCS = IRB.CreateCall(Func, Args);
1172    }
1173    NewCS.setCallingConv(CS.getCallingConv());
1174    NewCS.setAttributes(CS.getAttributes().removeAttributes(
1175        *DFSF.DFS.Ctx, AttributeSet::ReturnIndex,
1176        AttributeFuncs::typeIncompatible(NewCS.getInstruction()->getType(),
1177                                         AttributeSet::ReturnIndex)));
1178
1179    if (Next) {
1180      ExtractValueInst *ExVal =
1181          ExtractValueInst::Create(NewCS.getInstruction(), 0, "", Next);
1182      DFSF.SkipInsts.insert(ExVal);
1183      ExtractValueInst *ExShadow =
1184          ExtractValueInst::Create(NewCS.getInstruction(), 1, "", Next);
1185      DFSF.SkipInsts.insert(ExShadow);
1186      DFSF.setShadow(ExVal, ExShadow);
1187
1188      CS.getInstruction()->replaceAllUsesWith(ExVal);
1189    }
1190
1191    CS.getInstruction()->eraseFromParent();
1192  }
1193}
1194
1195void DFSanVisitor::visitPHINode(PHINode &PN) {
1196  PHINode *ShadowPN =
1197      PHINode::Create(DFSF.DFS.ShadowTy, PN.getNumIncomingValues(), "", &PN);
1198
1199  // Give the shadow phi node valid predecessors to fool SplitEdge into working.
1200  Value *UndefShadow = UndefValue::get(DFSF.DFS.ShadowTy);
1201  for (PHINode::block_iterator i = PN.block_begin(), e = PN.block_end(); i != e;
1202       ++i) {
1203    ShadowPN->addIncoming(UndefShadow, *i);
1204  }
1205
1206  DFSF.PHIFixups.push_back(std::make_pair(&PN, ShadowPN));
1207  DFSF.setShadow(&PN, ShadowPN);
1208}
1209