vendor/llvm/llvm-release_34-r197841

12 files changed, 362 insertions, 161 deletions

diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h
index 8f1a6e2b75c31..65cafe2ec2812 100644
--- a/include/llvm/Transforms/Utils/BasicBlockUtils.h
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -70,28 +70,6 @@ void ReplaceInstWithInst(BasicBlock::InstListType &BIL,
 //
 void ReplaceInstWithInst(Instruction *From, Instruction *To);
 
-/// FindFunctionBackedges - Analyze the specified function to find all of the
-/// loop backedges in the function and return them.  This is a relatively cheap
-/// (compared to computing dominators and loop info) analysis.
-///
-/// The output is added to Result, as pairs of <from,to> edge info.
-void FindFunctionBackedges(const Function &F,
-      SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result);
-
-
-/// GetSuccessorNumber - Search for the specified successor of basic block BB
-/// and return its position in the terminator instruction's list of
-/// successors.  It is an error to call this with a block that is not a
-/// successor.
-unsigned GetSuccessorNumber(BasicBlock *BB, BasicBlock *Succ);
-
-/// isCriticalEdge - Return true if the specified edge is a critical edge.
-/// Critical edges are edges from a block with multiple successors to a block
-/// with multiple predecessors.
-///
-bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
-                    bool AllowIdenticalEdges = false);
-
 /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
 /// split the critical edge.  This will update DominatorTree and
 /// DominatorFrontier information if it is available, thus calling this pass
@@ -227,6 +205,15 @@ ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
 TerminatorInst *SplitBlockAndInsertIfThen(Instruction *Cmp,
     bool Unreachable, MDNode *BranchWeights = 0);
 
+///
+/// GetIfCondition - Check whether BB is the merge point of a if-region.
+/// If so, return the boolean condition that determines which entry into
+/// BB will be taken.  Also, return by references the block that will be
+/// entered from if the condition is true, and the block that will be
+/// entered if the condition is false.
+
+Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
+		      BasicBlock *&IfFalse);
 } // End llvm namespace
 
 #endif
diff --git a/include/llvm/Transforms/Utils/BlackList.h b/include/llvm/Transforms/Utils/BlackList.h
deleted file mode 100644
index 316b364845caf..0000000000000
--- a/include/llvm/Transforms/Utils/BlackList.h
+++ /dev/null
@@ -1,59 +0,0 @@
-//===-- BlackList.h - blacklist for sanitizers ------------------*- C++ -*-===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//===----------------------------------------------------------------------===//
-//
-// This is a utility class for instrumentation passes (like AddressSanitizer
-// or ThreadSanitizer) to avoid instrumenting some functions or global
-// variables based on a user-supplied blacklist.
-//
-// The blacklist disables instrumentation of various functions and global
-// variables.  Each line contains a prefix, followed by a wild card expression.
-// Empty lines and lines starting with "#" are ignored.
-// ---
-// # Blacklisted items:
-// fun:*_ZN4base6subtle*
-// global:*global_with_bad_access_or_initialization*
-// global-init:*global_with_initialization_issues*
-// global-init-type:*Namespace::ClassName*
-// src:file_with_tricky_code.cc
-// global-init-src:ignore-global-initializers-issues.cc
-// ---
-// Note that the wild card is in fact an llvm::Regex, but * is automatically
-// replaced with .*
-// This is similar to the "ignore" feature of ThreadSanitizer.
-// http://code.google.com/p/data-race-test/wiki/ThreadSanitizerIgnores
-//
-//===----------------------------------------------------------------------===//
-//
-
-#include "llvm/ADT/StringMap.h"
-
-namespace llvm {
-class Function;
-class GlobalVariable;
-class Module;
-class Regex;
-class StringRef;
-
-class BlackList {
- public:
-  BlackList(const StringRef Path);
-  // Returns whether either this function or it's source file are blacklisted.
-  bool isIn(const Function &F) const;
-  // Returns whether either this global or it's source file are blacklisted.
-  bool isIn(const GlobalVariable &G) const;
-  // Returns whether this module is blacklisted by filename.
-  bool isIn(const Module &M) const;
-  // Returns whether a global should be excluded from initialization checking.
-  bool isInInit(const GlobalVariable &G) const;
- private:
-  StringMap<Regex*> Entries;
-
-  bool inSection(const StringRef Section, const StringRef Query) const;
-};
-
-}  // namespace llvm
diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h
index 14212f622ba59..3ec132937c0d9 100644
--- a/include/llvm/Transforms/Utils/Cloning.h
+++ b/include/llvm/Transforms/Utils/Cloning.h
@@ -131,7 +131,8 @@ void CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
                        SmallVectorImpl<ReturnInst*> &Returns,
                        const char *NameSuffix = "", 
                        ClonedCodeInfo *CodeInfo = 0,
-                       ValueMapTypeRemapper *TypeMapper = 0);
+                       ValueMapTypeRemapper *TypeMapper = 0,
+                       ValueMaterializer *Materializer = 0);
 
 /// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
 /// except that it does some simple constant prop and DCE on the fly.  The
diff --git a/include/llvm/Transforms/Utils/GlobalStatus.h b/include/llvm/Transforms/Utils/GlobalStatus.h
new file mode 100644
index 0000000000000..c36609508808d
--- /dev/null
+++ b/include/llvm/Transforms/Utils/GlobalStatus.h
@@ -0,0 +1,82 @@
+//===- GlobalStatus.h - Compute status info for globals ---------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_GLOBALSTATUS_H
+#define LLVM_TRANSFORMS_UTILS_GLOBALSTATUS_H
+
+#include "llvm/IR/Instructions.h"
+
+namespace llvm {
+class Value;
+class Function;
+
+/// It is safe to destroy a constant iff it is only used by constants itself.
+/// Note that constants cannot be cyclic, so this test is pretty easy to
+/// implement recursively.
+///
+bool isSafeToDestroyConstant(const Constant *C);
+
+/// As we analyze each global, keep track of some information about it.  If we
+/// find out that the address of the global is taken, none of this info will be
+/// accurate.
+struct GlobalStatus {
+  /// True if the global's address is used in a comparison.
+  bool IsCompared;
+
+  /// True if the global is ever loaded.  If the global isn't ever loaded it
+  /// can be deleted.
+  bool IsLoaded;
+
+  /// Keep track of what stores to the global look like.
+  enum StoredType {
+    /// There is no store to this global.  It can thus be marked constant.
+    NotStored,
+
+    /// This global is stored to, but the only thing stored is the constant it
+    /// was initialized with. This is only tracked for scalar globals.
+    InitializerStored,
+
+    /// This global is stored to, but only its initializer and one other value
+    /// is ever stored to it.  If this global isStoredOnce, we track the value
+    /// stored to it in StoredOnceValue below.  This is only tracked for scalar
+    /// globals.
+    StoredOnce,
+
+    /// This global is stored to by multiple values or something else that we
+    /// cannot track.
+    Stored
+  } StoredType;
+
+  /// If only one value (besides the initializer constant) is ever stored to
+  /// this global, keep track of what value it is.
+  Value *StoredOnceValue;
+
+  /// These start out null/false.  When the first accessing function is noticed,
+  /// it is recorded. When a second different accessing function is noticed,
+  /// HasMultipleAccessingFunctions is set to true.
+  const Function *AccessingFunction;
+  bool HasMultipleAccessingFunctions;
+
+  /// Set to true if this global has a user that is not an instruction (e.g. a
+  /// constant expr or GV initializer).
+  bool HasNonInstructionUser;
+
+  /// Set to the strongest atomic ordering requirement.
+  AtomicOrdering Ordering;
+
+  /// Look at all uses of the global and fill in the GlobalStatus structure.  If
+  /// the global has its address taken, return true to indicate we can't do
+  /// anything with it.
+  static bool analyzeGlobal(const Value *V, GlobalStatus &GS);
+
+  GlobalStatus();
+};
+}
+
+#endif
diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h
index 267825079e114..5586c155bb11b 100644
--- a/include/llvm/Transforms/Utils/Local.h
+++ b/include/llvm/Transforms/Utils/Local.h
@@ -39,9 +39,10 @@ class DataLayout;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 class DIBuilder;
+class AliasAnalysis;
 
 template<typename T> class SmallVectorImpl;
-  
+
 //===----------------------------------------------------------------------===//
 //  Local constant propagation.
 //
@@ -79,7 +80,7 @@ bool RecursivelyDeleteTriviallyDeadInstructions(Value *V,
 /// too, recursively.  Return true if a change was made.
 bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=0);
 
-  
+
 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to
 /// simplify any instructions in it and recursively delete dead instructions.
 ///
@@ -87,7 +88,7 @@ bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=0);
 /// instructions in other blocks as well in this block.
 bool SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD = 0,
                                  const TargetLibraryInfo *TLI = 0);
-    
+
 //===----------------------------------------------------------------------===//
 //  Control Flow Graph Restructuring.
 //
@@ -105,15 +106,15 @@ bool SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD = 0,
 /// recursively fold the 'and' to 0.
 void RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
                                   DataLayout *TD = 0);
-    
-  
+
+
 /// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its
 /// predecessor is known to have one successor (BB!).  Eliminate the edge
 /// between them, moving the instructions in the predecessor into BB.  This
 /// deletes the predecessor block.
 ///
 void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, Pass *P = 0);
-    
+
 
 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
 /// unconditional branch, and contains no instructions other than PHI nodes,
@@ -138,6 +139,12 @@ bool EliminateDuplicatePHINodes(BasicBlock *BB);
 bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
                  const DataLayout *TD = 0);
 
+/// FlatternCFG - This function is used to flatten a CFG.  For
+/// example, it uses parallel-and and parallel-or mode to collapse
+//  if-conditions and merge if-regions with identical statements.
+///
+bool FlattenCFG(BasicBlock *BB, AliasAnalysis *AA = 0);
+
 /// FoldBranchToCommonDest - If this basic block is ONLY a setcc and a branch,
 /// and if a predecessor branches to us and one of our successors, fold the
 /// setcc into the predecessor and use logical operations to pick the right
@@ -156,7 +163,7 @@ AllocaInst *DemoteRegToStack(Instruction &X,
 
 /// DemotePHIToStack - This function takes a virtual register computed by a phi
 /// node and replaces it with a slot in the stack frame, allocated via alloca.
-/// The phi node is deleted and it returns the pointer to the alloca inserted. 
+/// The phi node is deleted and it returns the pointer to the alloca inserted.
 AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = 0);
 
 /// getOrEnforceKnownAlignment - If the specified pointer has an alignment that
@@ -179,28 +186,34 @@ static inline unsigned getKnownAlignment(Value *V, const DataLayout *TD = 0) {
 template<typename IRBuilderTy>
 Value *EmitGEPOffset(IRBuilderTy *Builder, const DataLayout &TD, User *GEP,
                      bool NoAssumptions = false) {
-  gep_type_iterator GTI = gep_type_begin(GEP);
-  Type *IntPtrTy = TD.getIntPtrType(GEP->getContext());
+  GEPOperator *GEPOp = cast<GEPOperator>(GEP);
+  Type *IntPtrTy = TD.getIntPtrType(GEP->getType());
   Value *Result = Constant::getNullValue(IntPtrTy);
 
   // If the GEP is inbounds, we know that none of the addressing operations will
   // overflow in an unsigned sense.
-  bool isInBounds = cast<GEPOperator>(GEP)->isInBounds() && !NoAssumptions;
+  bool isInBounds = GEPOp->isInBounds() && !NoAssumptions;
 
   // Build a mask for high order bits.
-  unsigned IntPtrWidth = TD.getPointerSizeInBits();
-  uint64_t PtrSizeMask = ~0ULL >> (64-IntPtrWidth);
+  unsigned IntPtrWidth = IntPtrTy->getScalarType()->getIntegerBitWidth();
+  uint64_t PtrSizeMask = ~0ULL >> (64 - IntPtrWidth);
 
+  gep_type_iterator GTI = gep_type_begin(GEP);
   for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end(); i != e;
        ++i, ++GTI) {
     Value *Op = *i;
     uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()) & PtrSizeMask;
-    if (ConstantInt *OpC = dyn_cast<ConstantInt>(Op)) {
-      if (OpC->isZero()) continue;
+    if (Constant *OpC = dyn_cast<Constant>(Op)) {
+      if (OpC->isZeroValue())
+        continue;
 
       // Handle a struct index, which adds its field offset to the pointer.
       if (StructType *STy = dyn_cast<StructType>(*GTI)) {
-        Size = TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue());
+        if (OpC->getType()->isVectorTy())
+          OpC = OpC->getSplatValue();
+
+        uint64_t OpValue = cast<ConstantInt>(OpC)->getZExtValue();
+        Size = TD.getStructLayout(STy)->getElementOffset(OpValue);
 
         if (Size)
           Result = Builder->CreateAdd(Result, ConstantInt::get(IntPtrTy, Size),
diff --git a/include/llvm/Transforms/Utils/LoopUtils.h b/include/llvm/Transforms/Utils/LoopUtils.h
new file mode 100644
index 0000000000000..4745eba079aee
--- /dev/null
+++ b/include/llvm/Transforms/Utils/LoopUtils.h
@@ -0,0 +1,26 @@
+//===- llvm/Transforms/Utils/LoopUtils.h - Loop utilities -*- C++ -*-=========//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines some loop transformation utilities.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
+#define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
+
+namespace llvm {
+
+class Loop;
+class Pass;
+
+BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P);
+
+}
+
+#endif
diff --git a/include/llvm/Transforms/Utils/ModuleUtils.h b/include/llvm/Transforms/Utils/ModuleUtils.h
index bb7fc06bf5307..98a19ed426ace 100644
--- a/include/llvm/Transforms/Utils/ModuleUtils.h
+++ b/include/llvm/Transforms/Utils/ModuleUtils.h
@@ -18,6 +18,9 @@ namespace llvm {
 
 class Module;
 class Function;
+class GlobalValue;
+class GlobalVariable;
+template <class PtrType, unsigned SmallSize> class SmallPtrSet;
 
 /// Append F to the list of global ctors of module M with the given Priority.
 /// This wraps the function in the appropriate structure and stores it along
@@ -28,6 +31,11 @@ void appendToGlobalCtors(Module &M, Function *F, int Priority);
 /// Same as appendToGlobalCtors(), but for global dtors.
 void appendToGlobalDtors(Module &M, Function *F, int Priority);
 
+/// \brief Given "llvm.used" or "llvm.compiler.used" as a global name, collect
+/// the initializer elements of that global in Set and return the global itself.
+GlobalVariable *collectUsedGlobalVariables(Module &M,
+                                           SmallPtrSet<GlobalValue *, 8> &Set,
+                                           bool CompilerUsed);
 } // End llvm namespace
 
 #endif //  LLVM_TRANSFORMS_UTILS_MODULEUTILS_H
diff --git a/include/llvm/Transforms/Utils/PromoteMemToReg.h b/include/llvm/Transforms/Utils/PromoteMemToReg.h
index 52a6157d95ad0..22f46e5fc963c 100644
--- a/include/llvm/Transforms/Utils/PromoteMemToReg.h
+++ b/include/llvm/Transforms/Utils/PromoteMemToReg.h
@@ -15,7 +15,7 @@
 #ifndef LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H
 #define LLVM_TRANSFORMS_UTILS_PROMOTEMEMTOREG_H
 
-#include <vector>
+#include "llvm/ADT/ArrayRef.h"
 
 namespace llvm {
 
@@ -23,21 +23,25 @@ class AllocaInst;
 class DominatorTree;
 class AliasSetTracker;
 
-/// isAllocaPromotable - Return true if this alloca is legal for promotion.
-/// This is true if there are only loads and stores to the alloca...
+/// \brief Return true if this alloca is legal for promotion.
 ///
+/// This is true if there are only loads, stores, and lifetime markers
+/// (transitively) using this alloca. This also enforces that there is only
+/// ever one layer of bitcasts or GEPs between the alloca and the lifetime
+/// markers.
 bool isAllocaPromotable(const AllocaInst *AI);
 
-/// PromoteMemToReg - Promote the specified list of alloca instructions into
-/// scalar registers, inserting PHI nodes as appropriate.  This function makes
-/// use of DominanceFrontier information.  This function does not modify the CFG
-/// of the function at all.  All allocas must be from the same function.
+/// \brief Promote the specified list of alloca instructions into scalar
+/// registers, inserting PHI nodes as appropriate.
+///
+/// This function makes use of DominanceFrontier information.  This function
+/// does not modify the CFG of the function at all.  All allocas must be from
+/// the same function.
 ///
 /// If AST is specified, the specified tracker is updated to reflect changes
 /// made to the IR.
-///
-void PromoteMemToReg(const std::vector<AllocaInst*> &Allocas,
-                     DominatorTree &DT, AliasSetTracker *AST = 0);
+void PromoteMemToReg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
+                     AliasSetTracker *AST = 0);
 
 } // End llvm namespace
 
diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h
index cd048936e0bf3..0c0e5de584fdc 100644
--- a/include/llvm/Transforms/Utils/SSAUpdater.h
+++ b/include/llvm/Transforms/Utils/SSAUpdater.h
@@ -28,82 +28,90 @@ namespace llvm {
   class Use;
   class Value;
 
-/// SSAUpdater - This class updates SSA form for a set of values defined in
-/// multiple blocks.  This is used when code duplication or another unstructured
+/// \brief Helper class for SSA formation on a set of values defined in
+/// multiple blocks.
+///
+/// This is used when code duplication or another unstructured
 /// transformation wants to rewrite a set of uses of one value with uses of a
 /// set of values.
 class SSAUpdater {
   friend class SSAUpdaterTraits<SSAUpdater>;
 
 private:
-  /// AvailableVals - This keeps track of which value to use on a per-block
-  /// basis.  When we insert PHI nodes, we keep track of them here.
+  /// This keeps track of which value to use on a per-block basis. When we
+  /// insert PHI nodes, we keep track of them here.
   //typedef DenseMap<BasicBlock*, Value*> AvailableValsTy;
   void *AV;
 
   /// ProtoType holds the type of the values being rewritten.
   Type *ProtoType;
 
-  // PHI nodes are given a name based on ProtoName.
+  /// PHI nodes are given a name based on ProtoName.
   std::string ProtoName;
 
-  /// InsertedPHIs - If this is non-null, the SSAUpdater adds all PHI nodes that
-  /// it creates to the vector.
+  /// If this is non-null, the SSAUpdater adds all PHI nodes that it creates to
+  /// the vector.
   SmallVectorImpl<PHINode*> *InsertedPHIs;
 
 public:
-  /// SSAUpdater constructor.  If InsertedPHIs is specified, it will be filled
+  /// If InsertedPHIs is specified, it will be filled
   /// in with all PHI Nodes created by rewriting.
   explicit SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = 0);
   ~SSAUpdater();
 
-  /// Initialize - Reset this object to get ready for a new set of SSA
-  /// updates with type 'Ty'.  PHI nodes get a name based on 'Name'.
+  /// \brief Reset this object to get ready for a new set of SSA updates with
+  /// type 'Ty'.
+  ///
+  /// PHI nodes get a name based on 'Name'.
   void Initialize(Type *Ty, StringRef Name);
 
-  /// AddAvailableValue - Indicate that a rewritten value is available at the
-  /// end of the specified block with the specified value.
+  /// \brief Indicate that a rewritten value is available in the specified block
+  /// with the specified value.
   void AddAvailableValue(BasicBlock *BB, Value *V);
 
-  /// HasValueForBlock - Return true if the SSAUpdater already has a value for
-  /// the specified block.
+  /// \brief Return true if the SSAUpdater already has a value for the specified
+  /// block.
   bool HasValueForBlock(BasicBlock *BB) const;
 
-  /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
-  /// live at the end of the specified block.
+  /// \brief Construct SSA form, materializing a value that is live at the end
+  /// of the specified block.
   Value *GetValueAtEndOfBlock(BasicBlock *BB);
 
-  /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
-  /// is live in the middle of the specified block.
+  /// \brief Construct SSA form, materializing a value that is live in the
+  /// middle of the specified block.
   ///
-  /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
-  /// important case: if there is a definition of the rewritten value after the
-  /// 'use' in BB.  Consider code like this:
+  /// \c GetValueInMiddleOfBlock is the same as \c GetValueAtEndOfBlock except
+  /// in one important case: if there is a definition of the rewritten value
+  /// after the 'use' in BB.  Consider code like this:
   ///
+  /// \code
   ///      X1 = ...
   ///   SomeBB:
   ///      use(X)
   ///      X2 = ...
   ///      br Cond, SomeBB, OutBB
+  /// \endcode
   ///
   /// In this case, there are two values (X1 and X2) added to the AvailableVals
   /// set by the client of the rewriter, and those values are both live out of
   /// their respective blocks.  However, the use of X happens in the *middle* of
   /// a block.  Because of this, we need to insert a new PHI node in SomeBB to
   /// merge the appropriate values, and this value isn't live out of the block.
-  ///
   Value *GetValueInMiddleOfBlock(BasicBlock *BB);
 
-  /// RewriteUse - Rewrite a use of the symbolic value.  This handles PHI nodes,
-  /// which use their value in the corresponding predecessor.  Note that this
-  /// will not work if the use is supposed to be rewritten to a value defined in
-  /// the same block as the use, but above it.  Any 'AddAvailableValue's added
-  /// for the use's block will be considered to be below it.
+  /// \brief Rewrite a use of the symbolic value.
+  ///
+  /// This handles PHI nodes, which use their value in the corresponding
+  /// predecessor. Note that this will not work if the use is supposed to be
+  /// rewritten to a value defined in the same block as the use, but above it.
+  /// Any 'AddAvailableValue's added for the use's block will be considered to
+  /// be below it.
   void RewriteUse(Use &U);
 
-  /// RewriteUseAfterInsertions - Rewrite a use, just like RewriteUse.  However,
-  /// this version of the method can rewrite uses in the same block as a
-  /// definition, because it assumes that all uses of a value are below any
+  /// \brief Rewrite a use like \c RewriteUse but handling in-block definitions.
+  ///
+  /// This version of the method can rewrite uses in the same block as
+  /// a definition, because it assumes that all uses of a value are below any
   /// inserted values.
   void RewriteUseAfterInsertions(Use &U);
 
@@ -113,15 +121,15 @@ private:
   void operator=(const SSAUpdater&) LLVM_DELETED_FUNCTION;
   SSAUpdater(const SSAUpdater&) LLVM_DELETED_FUNCTION;
 };
-  
-/// LoadAndStorePromoter - This little helper class provides a convenient way to
-/// promote a collection of loads and stores into SSA Form using the SSAUpdater.
+
+/// \brief Helper class for promoting a collection of loads and stores into SSA
+/// Form using the SSAUpdater.
+///
 /// This handles complexities that SSAUpdater doesn't, such as multiple loads
 /// and stores in one block.
 ///
 /// Clients of this class are expected to subclass this and implement the
 /// virtual methods.
-///
 class LoadAndStorePromoter {
 protected:
   SSAUpdater &SSA;
@@ -130,34 +138,36 @@ public:
                        SSAUpdater &S, StringRef Name = StringRef());
   virtual ~LoadAndStorePromoter() {}
   
-  /// run - This does the promotion.  Insts is a list of loads and stores to
-  /// promote, and Name is the basename for the PHIs to insert.  After this is
-  /// complete, the loads and stores are removed from the code.
+  /// \brief This does the promotion.
+  ///
+  /// Insts is a list of loads and stores to promote, and Name is the basename
+  /// for the PHIs to insert. After this is complete, the loads and stores are
+  /// removed from the code.
   void run(const SmallVectorImpl<Instruction*> &Insts) const;
   
   
-  /// Return true if the specified instruction is in the Inst list (which was
-  /// passed into the run method).  Clients should implement this with a more
-  /// efficient version if possible.
+  /// \brief Return true if the specified instruction is in the Inst list.
+  ///
+  /// The Insts list is the one passed into the constructor. Clients should
+  /// implement this with a more efficient version if possible.
   virtual bool isInstInList(Instruction *I,
                             const SmallVectorImpl<Instruction*> &Insts) const;
   
-  /// doExtraRewritesBeforeFinalDeletion - This hook is invoked after all the
-  /// stores are found and inserted as available values, but 
+  /// \brief This hook is invoked after all the stores are found and inserted as
+  /// available values.
   virtual void doExtraRewritesBeforeFinalDeletion() const {
   }
   
-  /// replaceLoadWithValue - Clients can choose to implement this to get
-  /// notified right before a load is RAUW'd another value.
+  /// \brief Clients can choose to implement this to get notified right before
+  /// a load is RAUW'd another value.
   virtual void replaceLoadWithValue(LoadInst *LI, Value *V) const {
   }
 
-  /// This is called before each instruction is deleted.
+  /// \brief Called before each instruction is deleted.
   virtual void instructionDeleted(Instruction *I) const {
   }
 
-  /// updateDebugInfo - This is called to update debug info associated with the
-  /// instruction.
+  /// \brief Called to update debug info associated with the instruction.
   virtual void updateDebugInfo(Instruction *I) const {
   }
 };
diff --git a/include/llvm/Transforms/Utils/SpecialCaseList.h b/include/llvm/Transforms/Utils/SpecialCaseList.h
new file mode 100644
index 0000000000000..34c28fc1cafef
--- /dev/null
+++ b/include/llvm/Transforms/Utils/SpecialCaseList.h
@@ -0,0 +1,110 @@
+//===-- SpecialCaseList.h - special case list for sanitizers ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//===----------------------------------------------------------------------===//
+//
+// This is a utility class for instrumentation passes (like AddressSanitizer
+// or ThreadSanitizer) to avoid instrumenting some functions or global
+// variables based on a user-supplied list.
+//
+// The list can also specify categories for specific globals, which can be used
+// to instruct an instrumentation pass to treat certain functions or global
+// variables in a specific way, such as by omitting certain aspects of
+// instrumentation while keeping others, or informing the instrumentation pass
+// that a specific uninstrumentable function has certain semantics, thus
+// allowing the pass to instrument callers according to those semantics.
+//
+// For example, AddressSanitizer uses the "init" category for globals whose
+// initializers should not be instrumented, but which in all other respects
+// should be instrumented.
+//
+// Each line contains a prefix, followed by a colon and a wild card expression,
+// followed optionally by an equals sign and an instrumentation-specific
+// category.  Empty lines and lines starting with "#" are ignored.
+// ---
+// # Blacklisted items:
+// fun:*_ZN4base6subtle*
+// global:*global_with_bad_access_or_initialization*
+// global:*global_with_initialization_issues*=init
+// type:*Namespace::ClassName*=init
+// src:file_with_tricky_code.cc
+// src:ignore-global-initializers-issues.cc=init
+//
+// # Functions with pure functional semantics:
+// fun:cos=functional
+// fun:sin=functional
+// ---
+// Note that the wild card is in fact an llvm::Regex, but * is automatically
+// replaced with .*
+// This is similar to the "ignore" feature of ThreadSanitizer.
+// http://code.google.com/p/data-race-test/wiki/ThreadSanitizerIgnores
+//
+//===----------------------------------------------------------------------===//
+//
+
+#include "llvm/ADT/StringMap.h"
+
+namespace llvm {
+class Function;
+class GlobalAlias;
+class GlobalVariable;
+class MemoryBuffer;
+class Module;
+class Regex;
+class StringRef;
+
+class SpecialCaseList {
+ public:
+  /// Parses the special case list from a file. If Path is empty, returns
+  /// an empty special case list. On failure, returns 0 and writes an error
+  /// message to string.
+  static SpecialCaseList *create(const StringRef Path, std::string &Error);
+  /// Parses the special case list from a memory buffer. On failure, returns
+  /// 0 and writes an error message to string.
+  static SpecialCaseList *create(const MemoryBuffer *MB, std::string &Error);
+  /// Parses the special case list from a file. On failure, reports a fatal
+  /// error.
+  static SpecialCaseList *createOrDie(const StringRef Path);
+
+  ~SpecialCaseList();
+
+  /// Returns whether either this function or its source file are listed in the
+  /// given category, which may be omitted to search the empty category.
+  bool isIn(const Function &F, const StringRef Category = StringRef()) const;
+
+  /// Returns whether this global, its type or its source file are listed in the
+  /// given category, which may be omitted to search the empty category.
+  bool isIn(const GlobalVariable &G,
+            const StringRef Category = StringRef()) const;
+
+  /// Returns whether this global alias is listed in the given category, which
+  /// may be omitted to search the empty category.
+  ///
+  /// If GA aliases a function, the alias's name is matched as a function name
+  /// would be.  Similarly, aliases of globals are matched like globals.
+  bool isIn(const GlobalAlias &GA,
+            const StringRef Category = StringRef()) const;
+
+  /// Returns whether this module is listed in the given category, which may be
+  /// omitted to search the empty category.
+  bool isIn(const Module &M, const StringRef Category = StringRef()) const;
+
+ private:
+  SpecialCaseList(SpecialCaseList const &) LLVM_DELETED_FUNCTION;
+  SpecialCaseList &operator=(SpecialCaseList const &) LLVM_DELETED_FUNCTION;
+
+  struct Entry;
+  StringMap<StringMap<Entry> > Entries;
+
+  SpecialCaseList();
+  /// Parses just-constructed SpecialCaseList entries from a memory buffer.
+  bool parse(const MemoryBuffer *MB, std::string &Error);
+
+  bool inSectionCategory(const StringRef Section, const StringRef Query,
+                         const StringRef Category) const;
+};
+
+}  // namespace llvm
diff --git a/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h b/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h
index 54506cfff4c30..933c85c51609f 100644
--- a/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h
+++ b/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h
@@ -34,7 +34,7 @@ public:
   // We can preserve non-critical-edgeness when we unify function exit nodes
   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 
-  // getReturn|Unwind|UnreachableBlock - Return the new single (or nonexistant)
+  // getReturn|Unwind|UnreachableBlock - Return the new single (or nonexistent)
   // return, unwind, or unreachable  basic blocks in the CFG.
   //
   BasicBlock *getReturnBlock() const { return ReturnBlock; }
diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h
index 5390c5e8ed47e..d56ac07690fd5 100644
--- a/include/llvm/Transforms/Utils/ValueMapper.h
+++ b/include/llvm/Transforms/Utils/ValueMapper.h
@@ -33,6 +33,19 @@ namespace llvm {
     /// remap types while mapping values.
     virtual Type *remapType(Type *SrcTy) = 0;
   };
+
+  /// ValueMaterializer - This is a class that can be implemented by clients
+  /// to materialize Values on demand.
+  class ValueMaterializer {
+    virtual void anchor(); // Out of line method.
+  public:
+    virtual ~ValueMaterializer() {}
+
+    /// materializeValueFor - The client should implement this method if they
+    /// want to generate a mapped Value on demand. For example, if linking
+    /// lazily.
+    virtual Value *materializeValueFor(Value *V) = 0;
+  };
   
   /// RemapFlags - These are flags that the value mapping APIs allow.
   enum RemapFlags {
@@ -55,23 +68,29 @@ namespace llvm {
   
   Value *MapValue(const Value *V, ValueToValueMapTy &VM,
                   RemapFlags Flags = RF_None,
-                  ValueMapTypeRemapper *TypeMapper = 0);
+                  ValueMapTypeRemapper *TypeMapper = 0,
+                  ValueMaterializer *Materializer = 0);
 
   void RemapInstruction(Instruction *I, ValueToValueMapTy &VM,
                         RemapFlags Flags = RF_None,
-                        ValueMapTypeRemapper *TypeMapper = 0);
+                        ValueMapTypeRemapper *TypeMapper = 0,
+                        ValueMaterializer *Materializer = 0);
   
   /// MapValue - provide versions that preserve type safety for MDNode and
   /// Constants.
   inline MDNode *MapValue(const MDNode *V, ValueToValueMapTy &VM,
                           RemapFlags Flags = RF_None,
-                          ValueMapTypeRemapper *TypeMapper = 0) {
-    return cast<MDNode>(MapValue((const Value*)V, VM, Flags, TypeMapper));
+                          ValueMapTypeRemapper *TypeMapper = 0,
+                          ValueMaterializer *Materializer = 0) {
+    return cast<MDNode>(MapValue((const Value*)V, VM, Flags, TypeMapper,
+                                 Materializer));
   }
   inline Constant *MapValue(const Constant *V, ValueToValueMapTy &VM,
                             RemapFlags Flags = RF_None,
-                            ValueMapTypeRemapper *TypeMapper = 0) {
-    return cast<Constant>(MapValue((const Value*)V, VM, Flags, TypeMapper));
+                            ValueMapTypeRemapper *TypeMapper = 0,
+                            ValueMaterializer *Materializer = 0) {
+    return cast<Constant>(MapValue((const Value*)V, VM, Flags, TypeMapper,
+                                   Materializer));
   }