Vendor import of llvm trunk r154661:vendor/llvm/llvm-trunk-r154661

http://llvm.org/svn/llvm-project/llvm/trunk@r154661

30 files changed, 698 insertions, 410 deletions

diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h
index d71ba208a129..b823f71a2217 100644
--- a/include/llvm/Analysis/AliasAnalysis.h
+++ b/include/llvm/Analysis/AliasAnalysis.h
@@ -327,7 +327,7 @@ public:
   }
 
   /// doesAccessArgPointees - Return true if functions with the specified
-  /// behavior are known to potentially read or write  from objects pointed
+  /// behavior are known to potentially read or write from objects pointed
   /// to be their pointer-typed arguments (with arbitrary offsets).
   ///
   static bool doesAccessArgPointees(ModRefBehavior MRB) {
@@ -568,6 +568,11 @@ bool isNoAliasCall(const Value *V);
 ///
 bool isIdentifiedObject(const Value *V);
 
+/// isKnownNonNull - Return true if this pointer couldn't possibly be null by
+/// its definition.  This returns true for allocas, non-extern-weak globals and
+/// byval arguments.
+bool isKnownNonNull(const Value *V);
+
 } // End llvm namespace
 
 #endif
diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h
index c4ebe4015bf8..95626d624a13 100644
--- a/include/llvm/Analysis/AliasSetTracker.h
+++ b/include/llvm/Analysis/AliasSetTracker.h
@@ -264,6 +264,7 @@ private:
   }
   void setVolatile() { Volatile = true; }
 
+public:
   /// aliasesPointer - Return true if the specified pointer "may" (or must)
   /// alias one of the members in the set.
   ///
diff --git a/include/llvm/Analysis/BlockFrequencyImpl.h b/include/llvm/Analysis/BlockFrequencyImpl.h
index 0fb2bd7db50e..6f2ccfb19901 100644
--- a/include/llvm/Analysis/BlockFrequencyImpl.h
+++ b/include/llvm/Analysis/BlockFrequencyImpl.h
@@ -24,7 +24,6 @@
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <vector>
-#include <sstream>
 #include <string>
 
 namespace llvm {
@@ -41,7 +40,7 @@ class MachineBlockFrequencyInfo;
 template<class BlockT, class FunctionT, class BlockProbInfoT>
 class BlockFrequencyImpl {
 
-  DenseMap<BlockT *, BlockFrequency> Freqs;
+  DenseMap<const BlockT *, BlockFrequency> Freqs;
 
   BlockProbInfoT *BPI;
 
@@ -52,15 +51,16 @@ class BlockFrequencyImpl {
   const uint32_t EntryFreq;
 
   std::string getBlockName(BasicBlock *BB) const {
-    return BB->getNameStr();
+    return BB->getName().str();
   }
 
   std::string getBlockName(MachineBasicBlock *MBB) const {
-    std::stringstream ss;
+    std::string str;
+    raw_string_ostream ss(str);
     ss << "BB#" << MBB->getNumber();
 
     if (const BasicBlock *BB = MBB->getBasicBlock())
-      ss << " derived from LLVM BB " << BB->getNameStr();
+      ss << " derived from LLVM BB " << BB->getName();
 
     return ss.str();
   }
@@ -308,8 +308,9 @@ class BlockFrequencyImpl {
 
 public:
   /// getBlockFreq - Return block frequency. Return 0 if we don't have it.
-  BlockFrequency getBlockFreq(BlockT *BB) const {
-    typename DenseMap<BlockT *, BlockFrequency>::const_iterator I = Freqs.find(BB);
+  BlockFrequency getBlockFreq(const BlockT *BB) const {
+    typename DenseMap<const BlockT *, BlockFrequency>::const_iterator
+      I = Freqs.find(BB);
     if (I != Freqs.end())
       return I->second;
     return 0;
diff --git a/include/llvm/Analysis/BlockFrequencyInfo.h b/include/llvm/Analysis/BlockFrequencyInfo.h
index 9e698a9f4bb1..fcab90677a48 100644
--- a/include/llvm/Analysis/BlockFrequencyInfo.h
+++ b/include/llvm/Analysis/BlockFrequencyInfo.h
@@ -47,7 +47,7 @@ public:
   /// that we should not rely on the value itself, but only on the comparison to
   /// the other block frequencies. We do this to avoid using of floating points.
   ///
-  BlockFrequency getBlockFreq(BasicBlock *BB) const;
+  BlockFrequency getBlockFreq(const BasicBlock *BB) const;
 };
 
 }
diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h
index a2c12ab9e824..2ced7967ed5b 100644
--- a/include/llvm/Analysis/BranchProbabilityInfo.h
+++ b/include/llvm/Analysis/BranchProbabilityInfo.h
@@ -17,29 +17,23 @@
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/BranchProbability.h"
 
 namespace llvm {
-
+class LoopInfo;
 class raw_ostream;
 
+/// \brief Analysis pass providing branch probability information.
+///
+/// This is a function analysis pass which provides information on the relative
+/// probabilities of each "edge" in the function's CFG where such an edge is
+/// defined by a pair of basic blocks. The probability for a given block and
+/// a successor block are always relative to the probabilities of the other
+/// successor blocks. Another way of looking at it is that the probabilities
+/// for a given block B and each of its successors should sum to exactly
+/// one (100%).
 class BranchProbabilityInfo : public FunctionPass {
-
-  // Default weight value. Used when we don't have information about the edge.
-  // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of
-  // the successors have a weight yet. But it doesn't make sense when providing
-  // weight to an edge that may have siblings with non-zero weights. This can
-  // be handled various ways, but it's probably fine for an edge with unknown
-  // weight to just "inherit" the non-zero weight of an adjacent successor.
-  static const uint32_t DEFAULT_WEIGHT = 16;
-
-  typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
-
-  DenseMap<Edge, uint32_t> Weights;
-
-  // Get sum of the block successors' weights.
-  uint32_t getSumForBlock(const BasicBlock *BB) const;
-
 public:
   static char ID;
 
@@ -48,34 +42,86 @@ public:
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const;
-
   bool runOnFunction(Function &F);
+  void print(raw_ostream &OS, const Module *M = 0) const;
+
+  /// \brief Get an edge's probability, relative to other out-edges of the Src.
+  ///
+  /// This routine provides access to the fractional probability between zero
+  /// (0%) and one (100%) of this edge executing, relative to other edges
+  /// leaving the 'Src' block. The returned probability is never zero, and can
+  /// only be one if the source block has only one successor.
+  BranchProbability getEdgeProbability(const BasicBlock *Src,
+                                       const BasicBlock *Dst) const;
+
+  /// \brief Test if an edge is hot relative to other out-edges of the Src.
+  ///
+  /// Check whether this edge out of the source block is 'hot'. We define hot
+  /// as having a relative probability >= 80%.
+  bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const;
 
-  // Returned value is between 1 and UINT32_MAX. Look at
-  // BranchProbabilityInfo.cpp for details.
+  /// \brief Retrieve the hot successor of a block if one exists.
+  ///
+  /// Given a basic block, look through its successors and if one exists for
+  /// which \see isEdgeHot would return true, return that successor block.
+  BasicBlock *getHotSucc(BasicBlock *BB) const;
+
+  /// \brief Print an edge's probability.
+  ///
+  /// Retrieves an edge's probability similarly to \see getEdgeProbability, but
+  /// then prints that probability to the provided stream. That stream is then
+  /// returned.
+  raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src,
+                                    const BasicBlock *Dst) const;
+
+  /// \brief Get the raw edge weight calculated for the block pair.
+  ///
+  /// This returns the raw edge weight. It is guaranteed to fall between 1 and
+  /// UINT32_MAX. Note that the raw edge weight is not meaningful in isolation.
+  /// This interface should be very carefully, and primarily by routines that
+  /// are updating the analysis by later calling setEdgeWeight.
   uint32_t getEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst) const;
 
-  // Look at BranchProbabilityInfo.cpp for details. Use it with caution!
+  /// \brief Set the raw edge weight for the block pair.
+  ///
+  /// This allows a pass to explicitly set the edge weight for a block. It can
+  /// be used when updating the CFG to update and preserve the branch
+  /// probability information. Read the implementation of how these edge
+  /// weights are calculated carefully before using!
   void setEdgeWeight(const BasicBlock *Src, const BasicBlock *Dst,
                      uint32_t Weight);
 
-  // A 'Hot' edge is an edge which probability is >= 80%.
-  bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const;
+private:
+  typedef std::pair<const BasicBlock *, const BasicBlock *> Edge;
 
-  // Return a hot successor for the block BB or null if there isn't one.
-  BasicBlock *getHotSucc(BasicBlock *BB) const;
+  // Default weight value. Used when we don't have information about the edge.
+  // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of
+  // the successors have a weight yet. But it doesn't make sense when providing
+  // weight to an edge that may have siblings with non-zero weights. This can
+  // be handled various ways, but it's probably fine for an edge with unknown
+  // weight to just "inherit" the non-zero weight of an adjacent successor.
+  static const uint32_t DEFAULT_WEIGHT = 16;
 
-  // Return a probability as a fraction between 0 (0% probability) and
-  // 1 (100% probability), however the value is never equal to 0, and can be 1
-  // only iff SRC block has only one successor.
-  BranchProbability getEdgeProbability(const BasicBlock *Src,
-                                       const BasicBlock *Dst) const;
+  DenseMap<Edge, uint32_t> Weights;
+
+  /// \brief Handle to the LoopInfo analysis.
+  LoopInfo *LI;
+
+  /// \brief Track the last function we run over for printing.
+  Function *LastF;
+
+  /// \brief Track the set of blocks directly succeeded by a returning block.
+  SmallPtrSet<BasicBlock *, 16> PostDominatedByUnreachable;
+
+  /// \brief Get sum of the block successors' weights.
+  uint32_t getSumForBlock(const BasicBlock *BB) const;
 
-  // Print value between 0 (0% probability) and 1 (100% probability),
-  // however the value is never equal to 0, and can be 1 only iff SRC block
-  // has only one successor.
-  raw_ostream &printEdgeProbability(raw_ostream &OS, BasicBlock *Src,
-                                    BasicBlock *Dst) const;
+  bool calcUnreachableHeuristics(BasicBlock *BB);
+  bool calcMetadataWeights(BasicBlock *BB);
+  bool calcPointerHeuristics(BasicBlock *BB);
+  bool calcLoopBranchHeuristics(BasicBlock *BB);
+  bool calcZeroHeuristics(BasicBlock *BB);
+  bool calcFloatingPointHeuristics(BasicBlock *BB);
 };
 
 }
diff --git a/include/llvm/Analysis/CFGPrinter.h b/include/llvm/Analysis/CFGPrinter.h
index 61614e34dacc..4704a929acf6 100644
--- a/include/llvm/Analysis/CFGPrinter.h
+++ b/include/llvm/Analysis/CFGPrinter.h
@@ -29,13 +29,13 @@ struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits {
   DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
 
   static std::string getGraphName(const Function *F) {
-    return "CFG for '" + F->getNameStr() + "' function";
+    return "CFG for '" + F->getName().str() + "' function";
   }
 
   static std::string getSimpleNodeLabel(const BasicBlock *Node,
-                                  const Function *Graph) {
+                                        const Function *) {
     if (!Node->getName().empty())
-      return Node->getNameStr(); 
+      return Node->getName().str();
 
     std::string Str;
     raw_string_ostream OS(Str);
@@ -45,7 +45,7 @@ struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits {
   }
 
   static std::string getCompleteNodeLabel(const BasicBlock *Node, 
-                                          const Function *Graph) {
+                                          const Function *) {
     std::string Str;
     raw_string_ostream OS(Str);
 
@@ -95,7 +95,9 @@ struct DOTGraphTraits<const Function*> : public DefaultDOTGraphTraits {
       
       std::string Str;
       raw_string_ostream OS(Str);
-      OS << SI->getCaseValue(SuccNo)->getValue();
+      SwitchInst::ConstCaseIt Case =
+          SwitchInst::ConstCaseIt::fromSuccessorIndex(SI, SuccNo); 
+      OS << Case.getCaseValue()->getValue();
       return OS.str();
     }    
     return "";
diff --git a/include/llvm/Analysis/CaptureTracking.h b/include/llvm/Analysis/CaptureTracking.h
index b3390f47d2f3..9b5e8425ad29 100644
--- a/include/llvm/Analysis/CaptureTracking.h
+++ b/include/llvm/Analysis/CaptureTracking.h
@@ -14,9 +14,12 @@
 #ifndef LLVM_ANALYSIS_CAPTURETRACKING_H
 #define LLVM_ANALYSIS_CAPTURETRACKING_H
 
-namespace llvm {
-  class Value;
+#include "llvm/Constants.h"
+#include "llvm/Instructions.h"
+#include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Support/CallSite.h"
 
+namespace llvm {
   /// PointerMayBeCaptured - Return true if this pointer value may be captured
   /// by the enclosing function (which is required to exist).  This routine can
   /// be expensive, so consider caching the results.  The boolean ReturnCaptures
@@ -28,6 +31,33 @@ namespace llvm {
                             bool ReturnCaptures,
                             bool StoreCaptures);
 
+  /// This callback is used in conjunction with PointerMayBeCaptured. In
+  /// addition to the interface here, you'll need to provide your own getters
+  /// to see whether anything was captured.
+  struct CaptureTracker {
+    virtual ~CaptureTracker();
+
+    /// tooManyUses - The depth of traversal has breached a limit. There may be
+    /// capturing instructions that will not be passed into captured().
+    virtual void tooManyUses() = 0;
+
+    /// shouldExplore - This is the use of a value derived from the pointer.
+    /// To prune the search (ie., assume that none of its users could possibly
+    /// capture) return false. To search it, return true.
+    ///
+    /// U->getUser() is always an Instruction.
+    virtual bool shouldExplore(Use *U) = 0;
+
+    /// captured - Information about the pointer was captured by the user of
+    /// use U. Return true to stop the traversal or false to continue looking
+    /// for more capturing instructions.
+    virtual bool captured(Use *U) = 0;
+  };
+
+  /// PointerMayBeCaptured - Visit the value and the values derived from it and
+  /// find values which appear to be capturing the pointer value. This feeds
+  /// results into and is controlled by the CaptureTracker object.
+  void PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker);
 } // end namespace llvm
 
 #endif
diff --git a/include/llvm/Analysis/CodeMetrics.h b/include/llvm/Analysis/CodeMetrics.h
index d96dd82b3591..711607834921 100644
--- a/include/llvm/Analysis/CodeMetrics.h
+++ b/include/llvm/Analysis/CodeMetrics.h
@@ -1,4 +1,4 @@
-//===- CodeMetrics.h - Measures the weight of a function---------*- C++ -*-===//
+//===- CodeMetrics.h - Code cost measurements -------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -18,80 +18,75 @@
 #include "llvm/ADT/DenseMap.h"
 
 namespace llvm {
-
+  class BasicBlock;
+  class Function;
+  class Instruction;
   class TargetData;
+  class Value;
 
-  // CodeMetrics - Calculate size and a few similar metrics for a set of
-  // basic blocks.
-  struct CodeMetrics {
-    /// NeverInline - True if this callee should never be inlined into a
-    /// caller.
-    // bool NeverInline;
+  /// \brief Check whether an instruction is likely to be "free" when lowered.
+  bool isInstructionFree(const Instruction *I, const TargetData *TD = 0);
+
+  /// \brief Check whether a call will lower to something small.
+  ///
+  /// This tests checks whether calls to this function will lower to something
+  /// significantly cheaper than a traditional call, often a single
+  /// instruction.
+  bool callIsSmall(const Function *F);
 
-    // True if this function contains a call to setjmp or _setjmp
-    bool callsSetJmp;
+  /// \brief Utility to calculate the size and a few similar metrics for a set
+  /// of basic blocks.
+  struct CodeMetrics {
+    /// \brief True if this function contains a call to setjmp or other functions
+    /// with attribute "returns twice" without having the attribute itself.
+    bool exposesReturnsTwice;
 
-    // True if this function calls itself
+    /// \brief True if this function calls itself.
     bool isRecursive;
 
-    // True if this function contains one or more indirect branches
+    /// \brief True if this function contains one or more indirect branches.
     bool containsIndirectBr;
 
-    /// usesDynamicAlloca - True if this function calls alloca (in the C sense).
+    /// \brief True if this function calls alloca (in the C sense).
     bool usesDynamicAlloca;
 
-    /// NumInsts, NumBlocks - Keep track of how large each function is, which
-    /// is used to estimate the code size cost of inlining it.
-    unsigned NumInsts, NumBlocks;
+    /// \brief Number of instructions in the analyzed blocks.
+    unsigned NumInsts;
+
+    /// \brief Number of analyzed blocks.
+    unsigned NumBlocks;
 
-    /// NumBBInsts - Keeps track of basic block code size estimates.
+    /// \brief Keeps track of basic block code size estimates.
     DenseMap<const BasicBlock *, unsigned> NumBBInsts;
 
-    /// NumCalls - Keep track of the number of calls to 'big' functions.
+    /// \brief Keep track of the number of calls to 'big' functions.
     unsigned NumCalls;
 
-    /// NumInlineCandidates - Keep track of the number of calls to internal
-    /// functions with only a single caller.  These are likely targets for
-    /// future inlining, likely exposed by interleaved devirtualization.
+    /// \brief The number of calls to internal functions with a single caller.
+    ///
+    /// These are likely targets for future inlining, likely exposed by
+    /// interleaved devirtualization.
     unsigned NumInlineCandidates;
 
-    /// NumVectorInsts - Keep track of how many instructions produce vector
-    /// values.  The inliner is being more aggressive with inlining vector
-    /// kernels.
+    /// \brief How many instructions produce vector values.
+    ///
+    /// The inliner is more aggressive with inlining vector kernels.
     unsigned NumVectorInsts;
 
-    /// NumRets - Keep track of how many Ret instructions the block contains.
+    /// \brief How many 'ret' instructions the blocks contain.
     unsigned NumRets;
 
-    CodeMetrics() : callsSetJmp(false), isRecursive(false),
+    CodeMetrics() : exposesReturnsTwice(false), isRecursive(false),
                     containsIndirectBr(false), usesDynamicAlloca(false),
                     NumInsts(0), NumBlocks(0), NumCalls(0),
                     NumInlineCandidates(0), NumVectorInsts(0),
                     NumRets(0) {}
 
-    /// analyzeBasicBlock - Add information about the specified basic block
-    /// to the current structure.
+    /// \brief Add information about a block to the current state.
     void analyzeBasicBlock(const BasicBlock *BB, const TargetData *TD = 0);
 
-    /// analyzeFunction - Add information about the specified function
-    /// to the current structure.
+    /// \brief Add information about a function to the current state.
     void analyzeFunction(Function *F, const TargetData *TD = 0);
-
-    /// CountCodeReductionForConstant - Figure out an approximation for how
-    /// many instructions will be constant folded if the specified value is
-    /// constant.
-    unsigned CountCodeReductionForConstant(Value *V);
-
-    /// CountBonusForConstant - Figure out an approximation for how much
-    /// per-call performance boost we can expect if the specified value is
-    /// constant.
-    unsigned CountBonusForConstant(Value *V);
-
-    /// CountCodeReductionForAlloca - Figure out an approximation of how much
-    /// smaller the function will be if it is inlined into a context where an
-    /// argument becomes an alloca.
-    ///
-    unsigned CountCodeReductionForAlloca(Value *V);
   };
 }
 
diff --git a/include/llvm/Analysis/ConstantFolding.h b/include/llvm/Analysis/ConstantFolding.h
index 05018fa1617a..2fdef5f0836e 100644
--- a/include/llvm/Analysis/ConstantFolding.h
+++ b/include/llvm/Analysis/ConstantFolding.h
@@ -25,6 +25,7 @@ namespace llvm {
   class ConstantExpr;
   class Instruction;
   class TargetData;
+  class TargetLibraryInfo;
   class Function;
   class Type;
   template<typename T>
@@ -35,13 +36,15 @@ namespace llvm {
 /// Note that this fails if not all of the operands are constant.  Otherwise,
 /// this function can only fail when attempting to fold instructions like loads
 /// and stores, which have no constant expression form.
-Constant *ConstantFoldInstruction(Instruction *I, const TargetData *TD = 0);
+Constant *ConstantFoldInstruction(Instruction *I, const TargetData *TD = 0,
+                                  const TargetLibraryInfo *TLI = 0);
 
 /// ConstantFoldConstantExpression - Attempt to fold the constant expression
 /// using the specified TargetData.  If successful, the constant result is
 /// result is returned, if not, null is returned.
 Constant *ConstantFoldConstantExpression(const ConstantExpr *CE,
-                                         const TargetData *TD = 0);
+                                         const TargetData *TD = 0,
+                                         const TargetLibraryInfo *TLI = 0);
 
 /// ConstantFoldInstOperands - Attempt to constant fold an instruction with the
 /// specified operands.  If successful, the constant result is returned, if not,
@@ -51,7 +54,8 @@ Constant *ConstantFoldConstantExpression(const ConstantExpr *CE,
 ///
 Constant *ConstantFoldInstOperands(unsigned Opcode, Type *DestTy,
                                    ArrayRef<Constant *> Ops,
-                                   const TargetData *TD = 0);
+                                   const TargetData *TD = 0,
+                                   const TargetLibraryInfo *TLI = 0);
 
 /// ConstantFoldCompareInstOperands - Attempt to constant fold a compare
 /// instruction (icmp/fcmp) with the specified operands.  If it fails, it
@@ -59,7 +63,8 @@ Constant *ConstantFoldInstOperands(unsigned Opcode, Type *DestTy,
 ///
 Constant *ConstantFoldCompareInstOperands(unsigned Predicate,
                                           Constant *LHS, Constant *RHS,
-                                          const TargetData *TD = 0);
+                                          const TargetData *TD = 0,
+                                          const TargetLibraryInfo *TLI = 0);
 
 /// ConstantFoldInsertValueInstruction - Attempt to constant fold an insertvalue
 /// instruction with the specified operands and indices.  The constant result is
@@ -76,15 +81,22 @@ Constant *ConstantFoldLoadFromConstPtr(Constant *C, const TargetData *TD = 0);
 /// getelementptr constantexpr, return the constant value being addressed by the
 /// constant expression, or null if something is funny and we can't decide.
 Constant *ConstantFoldLoadThroughGEPConstantExpr(Constant *C, ConstantExpr *CE);
-  
+
+/// ConstantFoldLoadThroughGEPIndices - Given a constant and getelementptr
+/// indices (with an *implied* zero pointer index that is not in the list),
+/// return the constant value being addressed by a virtual load, or null if
+/// something is funny and we can't decide.
+Constant *ConstantFoldLoadThroughGEPIndices(Constant *C,
+                                            ArrayRef<Constant*> Indices);
+
 /// canConstantFoldCallTo - Return true if its even possible to fold a call to
 /// the specified function.
 bool canConstantFoldCallTo(const Function *F);
 
 /// ConstantFoldCall - Attempt to constant fold a call to the specified function
 /// with the specified arguments, returning null if unsuccessful.
-Constant *
-ConstantFoldCall(Function *F, ArrayRef<Constant *> Operands);
+Constant *ConstantFoldCall(Function *F, ArrayRef<Constant *> Operands,
+                           const TargetLibraryInfo *TLI = 0);
 }
 
 #endif
diff --git a/include/llvm/Analysis/DIBuilder.h b/include/llvm/Analysis/DIBuilder.h
index ee24226c748f..2d109cdbf08f 100644
--- a/include/llvm/Analysis/DIBuilder.h
+++ b/include/llvm/Analysis/DIBuilder.h
@@ -42,6 +42,7 @@ namespace llvm {
   class DISubprogram;
   class DITemplateTypeParameter;
   class DITemplateValueParameter;
+  class DIObjCProperty;
 
   class DIBuilder {
     private:
@@ -190,6 +191,39 @@ namespace llvm {
                           StringRef PropertySetterName = StringRef(),
                           unsigned PropertyAttributes = 0);
 
+    /// createObjCIVar - Create debugging information entry for Objective-C
+    /// instance variable.
+    /// @param Name         Member name.
+    /// @param File         File where this member is defined.
+    /// @param LineNo       Line number.
+    /// @param SizeInBits   Member size.
+    /// @param AlignInBits  Member alignment.
+    /// @param OffsetInBits Member offset.
+    /// @param Flags        Flags to encode member attribute, e.g. private
+    /// @param Ty           Parent type.
+    /// @param Property     Property associated with this ivar.
+    DIType createObjCIVar(StringRef Name, DIFile File,
+                          unsigned LineNo, uint64_t SizeInBits, 
+                          uint64_t AlignInBits, uint64_t OffsetInBits, 
+                          unsigned Flags, DIType Ty,
+                          MDNode *PropertyNode);
+
+    /// createObjCProperty - Create debugging information entry for Objective-C
+    /// property.
+    /// @param Name         Property name.
+    /// @param File         File where this property is defined.
+    /// @param LineNumber   Line number.
+    /// @param GetterName   Name of the Objective C property getter selector.
+    /// @param SetterName   Name of the Objective C property setter selector.
+    /// @param PropertyAttributes Objective C property attributes.
+    /// @param Ty           Type.
+    DIObjCProperty createObjCProperty(StringRef Name,
+				      DIFile File, unsigned LineNumber,
+				      StringRef GetterName,
+				      StringRef SetterName,
+				      unsigned PropertyAttributes,
+				      DIType Ty);
+      
     /// createClassType - Create debugging information entry for a class.
     /// @param Scope        Scope in which this class is defined.
     /// @param Name         class name.
@@ -313,6 +347,10 @@ namespace llvm {
     DIType createTemporaryType();
     DIType createTemporaryType(DIFile F);
 
+    /// createForwardDecl - Create a temporary forward-declared type.
+    DIType createForwardDecl(unsigned Tag, StringRef Name, DIFile F,
+                             unsigned Line, unsigned RuntimeLang = 0);
+
     /// retainType - Retain DIType in a module even if it is not referenced 
     /// through debug info anchors.
     void retainType(DIType T);
@@ -407,6 +445,7 @@ namespace llvm {
     /// @param Ty            Function type.
     /// @param isLocalToUnit True if this function is not externally visible..
     /// @param isDefinition  True if this is a function definition.
+    /// @param ScopeLine     Set to the beginning of the scope this starts
     /// @param Flags         e.g. is this function prototyped or not.
     ///                      This flags are used to emit dwarf attributes.
     /// @param isOptimized   True if optimization is ON.
@@ -417,6 +456,7 @@ namespace llvm {
                                 DIFile File, unsigned LineNo,
                                 DIType Ty, bool isLocalToUnit,
                                 bool isDefinition,
+                                unsigned ScopeLine,
                                 unsigned Flags = 0,
                                 bool isOptimized = false,
                                 Function *Fn = 0,
@@ -470,7 +510,7 @@ namespace llvm {
     /// @param Scope       Lexical block.
     /// @param File        Source file.
     DILexicalBlockFile createLexicalBlockFile(DIDescriptor Scope,
-					      DIFile File);
+                                              DIFile File);
     
     /// createLexicalBlock - This creates a descriptor for a lexical block
     /// with the specified parent context.
diff --git a/include/llvm/Analysis/DOTGraphTraitsPass.h b/include/llvm/Analysis/DOTGraphTraitsPass.h
index 30741c4970ab..b701b8fca5d4 100644
--- a/include/llvm/Analysis/DOTGraphTraitsPass.h
+++ b/include/llvm/Analysis/DOTGraphTraitsPass.h
@@ -31,7 +31,7 @@ struct DOTGraphTraitsViewer : public FunctionPass {
     std::string Title, GraphName;
     Graph = &getAnalysis<Analysis>();
     GraphName = DOTGraphTraits<Analysis*>::getGraphName(Graph);
-    Title = GraphName + " for '" + F.getNameStr() + "' function";
+    Title = GraphName + " for '" + F.getName().str() + "' function";
     ViewGraph(Graph, Name, Simple, Title);
 
     return false;
@@ -55,7 +55,7 @@ struct DOTGraphTraitsPrinter : public FunctionPass {
 
   virtual bool runOnFunction(Function &F) {
     Analysis *Graph;
-    std::string Filename = Name + "." + F.getNameStr() + ".dot";
+    std::string Filename = Name + "." + F.getName().str() + ".dot";
     errs() << "Writing '" << Filename << "'...";
 
     std::string ErrorInfo;
@@ -64,7 +64,7 @@ struct DOTGraphTraitsPrinter : public FunctionPass {
 
     std::string Title, GraphName;
     GraphName = DOTGraphTraits<Analysis*>::getGraphName(Graph);
-    Title = GraphName + " for '" + F.getNameStr() + "' function";
+    Title = GraphName + " for '" + F.getName().str() + "' function";
 
     if (ErrorInfo.empty())
       WriteGraph(File, Graph, Simple, Title);
diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h
index 9a53c4dadba0..894c5428b988 100644
--- a/include/llvm/Analysis/DebugInfo.h
+++ b/include/llvm/Analysis/DebugInfo.h
@@ -43,6 +43,7 @@ namespace llvm {
   class DILexicalBlockFile;
   class DIVariable;
   class DIType;
+  class DIObjCProperty;
 
   /// DIDescriptor - A thin wraper around MDNode to access encoded debug info.
   /// This should not be stored in a container, because underly MDNode may
@@ -128,6 +129,7 @@ namespace llvm {
     bool isUnspecifiedParameter() const;
     bool isTemplateTypeParameter() const;
     bool isTemplateValueParameter() const;
+    bool isObjCProperty() const;
   };
 
   /// DISubrange - This is used to represent ranges, for array bounds.
@@ -135,8 +137,8 @@ namespace llvm {
   public:
     explicit DISubrange(const MDNode *N = 0) : DIDescriptor(N) {}
 
-    int64_t getLo() const { return (int64_t)getUInt64Field(1); }
-    int64_t getHi() const { return (int64_t)getUInt64Field(2); }
+    uint64_t getLo() const { return getUInt64Field(1); }
+    uint64_t getHi() const { return getUInt64Field(2); }
   };
 
   /// DIArray - This descriptor holds an array of descriptors.
@@ -153,6 +155,7 @@ namespace llvm {
 
   /// DIScope - A base class for various scopes.
   class DIScope : public DIDescriptor {
+    virtual void anchor();
   public:
     explicit DIScope(const MDNode *N = 0) : DIDescriptor (N) {}
     virtual ~DIScope() {}
@@ -163,6 +166,7 @@ namespace llvm {
 
   /// DICompileUnit - A wrapper for a compile unit.
   class DICompileUnit : public DIScope {
+    virtual void anchor();
   public:
     explicit DICompileUnit(const MDNode *N = 0) : DIScope(N) {}
 
@@ -202,6 +206,7 @@ namespace llvm {
 
   /// DIFile - This is a wrapper for a file.
   class DIFile : public DIScope {
+    virtual void anchor();
   public:
     explicit DIFile(const MDNode *N = 0) : DIScope(N) {
       if (DbgNode && !isFile())
@@ -230,7 +235,7 @@ namespace llvm {
   /// FIXME: Types should be factored much better so that CV qualifiers and
   /// others do not require a huge and empty descriptor full of zeros.
   class DIType : public DIScope {
-  public:
+    virtual void anchor();
   protected:
     // This ctor is used when the Tag has already been validated by a derived
     // ctor.
@@ -240,7 +245,6 @@ namespace llvm {
 
     /// Verify - Verify that a type descriptor is well formed.
     bool Verify() const;
-  public:
     explicit DIType(const MDNode *N);
     explicit DIType() {}
     virtual ~DIType() {}
@@ -320,6 +324,7 @@ namespace llvm {
 
   /// DIBasicType - A basic type, like 'int' or 'float'.
   class DIBasicType : public DIType {
+    virtual void anchor();
   public:
     explicit DIBasicType(const MDNode *N = 0) : DIType(N) {}
 
@@ -338,6 +343,7 @@ namespace llvm {
   /// DIDerivedType - A simple derived type, like a const qualified type,
   /// a typedef, a pointer or reference, etc.
   class DIDerivedType : public DIType {
+    virtual void anchor();
   protected:
     explicit DIDerivedType(const MDNode *N, bool, bool)
       : DIType(N, true, true) {}
@@ -351,29 +357,45 @@ namespace llvm {
     /// return base type size.
     uint64_t getOriginalTypeSize() const;
 
-    StringRef getObjCPropertyName() const { return getStringField(10); }
+    /// getObjCProperty - Return property node, if this ivar is 
+    /// associated with one.
+    MDNode *getObjCProperty() const;
+
+    StringRef getObjCPropertyName() const { 
+      if (getVersion() > LLVMDebugVersion11)
+        return StringRef();
+      return getStringField(10); 
+    }
     StringRef getObjCPropertyGetterName() const {
+      assert (getVersion() <= LLVMDebugVersion11  && "Invalid Request");
       return getStringField(11);
     }
     StringRef getObjCPropertySetterName() const {
+      assert (getVersion() <= LLVMDebugVersion11  && "Invalid Request");
       return getStringField(12);
     }
     bool isReadOnlyObjCProperty() {
+      assert (getVersion() <= LLVMDebugVersion11  && "Invalid Request");
       return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_readonly) != 0;
     }
     bool isReadWriteObjCProperty() {
+      assert (getVersion() <= LLVMDebugVersion11  && "Invalid Request");
       return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_readwrite) != 0;
     }
     bool isAssignObjCProperty() {
+      assert (getVersion() <= LLVMDebugVersion11  && "Invalid Request");
       return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_assign) != 0;
     }
     bool isRetainObjCProperty() {
+      assert (getVersion() <= LLVMDebugVersion11  && "Invalid Request");
       return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_retain) != 0;
     }
     bool isCopyObjCProperty() {
+      assert (getVersion() <= LLVMDebugVersion11  && "Invalid Request");
       return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_copy) != 0;
     }
     bool isNonAtomicObjCProperty() {
+      assert (getVersion() <= LLVMDebugVersion11  && "Invalid Request");
       return (getUnsignedField(13) & dwarf::DW_APPLE_PROPERTY_nonatomic) != 0;
     }
 
@@ -391,6 +413,7 @@ namespace llvm {
   /// other types, like a function or struct.
   /// FIXME: Why is this a DIDerivedType??
   class DICompositeType : public DIDerivedType {
+    virtual void anchor();
   public:
     explicit DICompositeType(const MDNode *N = 0)
       : DIDerivedType(N, true, true) {
@@ -454,6 +477,7 @@ namespace llvm {
 
   /// DISubprogram - This is a wrapper for a subprogram (e.g. a function).
   class DISubprogram : public DIScope {
+    virtual void anchor();
   public:
     explicit DISubprogram(const MDNode *N = 0) : DIScope(N) {}
 
@@ -495,6 +519,7 @@ namespace llvm {
     DICompositeType getContainingType() const {
       return getFieldAs<DICompositeType>(13);
     }
+
     unsigned isArtificial() const    { 
       if (getVersion() <= llvm::LLVMDebugVersion8)
         return getUnsignedField(14); 
@@ -543,6 +568,11 @@ namespace llvm {
       return getFieldAs<DIFile>(6).getDirectory(); 
     }
 
+    /// getScopeLineNumber - Get the beginning of the scope of the
+    /// function, not necessarily where the name of the program
+    /// starts.
+    unsigned getScopeLineNumber() const { return getUnsignedField(20); }
+
     /// Verify - Verify that a subprogram descriptor is well formed.
     bool Verify() const;
 
@@ -621,7 +651,7 @@ namespace llvm {
 
     DIScope getContext() const          { return getFieldAs<DIScope>(1); }
     StringRef getName() const           { return getStringField(2);     }
-    DICompileUnit getCompileUnit() const{ 
+    DICompileUnit getCompileUnit() const { 
       assert (getVersion() <= LLVMDebugVersion10 && "Invalid getCompileUnit!");
       if (getVersion() == llvm::LLVMDebugVersion7)
         return getFieldAs<DICompileUnit>(3);
@@ -687,6 +717,7 @@ namespace llvm {
 
   /// DILexicalBlock - This is a wrapper for a lexical block.
   class DILexicalBlock : public DIScope {
+    virtual void anchor();
   public:
     explicit DILexicalBlock(const MDNode *N = 0) : DIScope(N) {}
     DIScope getContext() const       { return getFieldAs<DIScope>(1);      }
@@ -705,6 +736,7 @@ namespace llvm {
   /// DILexicalBlockFile - This is a wrapper for a lexical block with
   /// a filename change.
   class DILexicalBlockFile : public DIScope {
+    virtual void anchor();
   public:
     explicit DILexicalBlockFile(const MDNode *N = 0) : DIScope(N) {}
     DIScope getContext() const { return getScope().getContext(); }
@@ -724,6 +756,7 @@ namespace llvm {
 
   /// DINameSpace - A wrapper for a C++ style name space.
   class DINameSpace : public DIScope { 
+    virtual void anchor();
   public:
     explicit DINameSpace(const MDNode *N = 0) : DIScope(N) {}
     DIScope getContext() const     { return getFieldAs<DIScope>(1);      }
@@ -760,6 +793,51 @@ namespace llvm {
     bool Verify() const;
   };
 
+  class DIObjCProperty : public DIDescriptor {
+  public:
+    explicit DIObjCProperty(const MDNode *N) : DIDescriptor(N) { }
+
+    StringRef getObjCPropertyName() const { return getStringField(1); }
+    DIFile getFile() const { return getFieldAs<DIFile>(2); }
+    unsigned getLineNumber() const { return getUnsignedField(3); }
+
+    StringRef getObjCPropertyGetterName() const {
+      return getStringField(4);
+    }
+    StringRef getObjCPropertySetterName() const {
+      return getStringField(5);
+    }
+    bool isReadOnlyObjCProperty() {
+      return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_readonly) != 0;
+    }
+    bool isReadWriteObjCProperty() {
+      return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_readwrite) != 0;
+    }
+    bool isAssignObjCProperty() {
+      return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_assign) != 0;
+    }
+    bool isRetainObjCProperty() {
+      return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_retain) != 0;
+    }
+    bool isCopyObjCProperty() {
+      return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_copy) != 0;
+    }
+    bool isNonAtomicObjCProperty() {
+      return (getUnsignedField(6) & dwarf::DW_APPLE_PROPERTY_nonatomic) != 0;
+    }
+
+    DIType getType() const { return getFieldAs<DIType>(7); }
+
+    /// Verify - Verify that a derived type descriptor is well formed.
+    bool Verify() const;
+
+    /// print - print derived type.
+    void print(raw_ostream &OS) const;
+
+    /// dump - print derived type to dbgs() with a newline.
+    void dump() const;
+  };
+
   /// getDISubprogram - Find subprogram that is enclosing this scope.
   DISubprogram getDISubprogram(const MDNode *Scope);
 
@@ -816,7 +894,7 @@ namespace llvm {
     /// addGlobalVariable - Add global variable into GVs.
     bool addGlobalVariable(DIGlobalVariable DIG);
 
-    // addSubprogram - Add subprgoram into SPs.
+    // addSubprogram - Add subprogram into SPs.
     bool addSubprogram(DISubprogram SP);
 
     /// addType - Add type into Tys.
diff --git a/include/llvm/Analysis/DominanceFrontier.h b/include/llvm/Analysis/DominanceFrontier.h
index d7f74af1c65c..a2e0675e92b7 100644
--- a/include/llvm/Analysis/DominanceFrontier.h
+++ b/include/llvm/Analysis/DominanceFrontier.h
@@ -154,6 +154,7 @@ public:
 /// used to compute a forward dominator frontiers.
 ///
 class DominanceFrontier : public DominanceFrontierBase {
+  virtual void anchor();
 public:
   static char ID; // Pass ID, replacement for typeid
   DominanceFrontier() :
diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h
index ae552b05abff..0c29236dde96 100644
--- a/include/llvm/Analysis/DominatorInternals.h
+++ b/include/llvm/Analysis/DominatorInternals.h
@@ -171,7 +171,7 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
 
   // it might be that some blocks did not get a DFS number (e.g., blocks of 
   // infinite loops). In these cases an artificial exit node is required.
-  MultipleRoots |= (DT.isPostDominator() && N != F.size());
+  MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F));
 
   // When naively implemented, the Lengauer-Tarjan algorithm requires a separate
   // bucket for each vertex. However, this is unnecessary, because each vertex
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 230e83d30121..6e8e4246367e 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -185,6 +185,18 @@ void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType>& DT,
 
 template<class NodeT>
 class DominatorTreeBase : public DominatorBase<NodeT> {
+  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
+                               const DomTreeNodeBase<NodeT> *B) const {
+    assert(A != B);
+    assert(isReachableFromEntry(B));
+    assert(isReachableFromEntry(A));
+
+    const DomTreeNodeBase<NodeT> *IDom;
+    while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
+      B = IDom;   // Walk up the tree
+    return IDom != 0;
+  }
+
 protected:
   typedef DenseMap<NodeT*, DomTreeNodeBase<NodeT>*> DomTreeNodeMapType;
   DomTreeNodeMapType DomTreeNodes;
@@ -321,8 +333,7 @@ public:
   /// block.  This is the same as using operator[] on this class.
   ///
   inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
-    typename DomTreeNodeMapType::const_iterator I = DomTreeNodes.find(BB);
-    return I != DomTreeNodes.end() ? I->second : 0;
+    return DomTreeNodes.lookup(BB);
   }
 
   /// getRootNode - This returns the entry node for the CFG of the function.  If
@@ -339,38 +350,26 @@ public:
   /// Note that this is not a constant time operation!
   ///
   bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
-                         const DomTreeNodeBase<NodeT> *B) const {
-    if (A == 0 || B == 0) return false;
-    return dominatedBySlowTreeWalk(A, B);
-  }
-
-  inline bool properlyDominates(const NodeT *A, const NodeT *B) {
+                         const DomTreeNodeBase<NodeT> *B) {
+    if (A == 0 || B == 0)
+      return false;
     if (A == B)
       return false;
-
-    // Cast away the const qualifiers here. This is ok since
-    // this function doesn't actually return the values returned
-    // from getNode.
-    return properlyDominates(getNode(const_cast<NodeT *>(A)),
-                             getNode(const_cast<NodeT *>(B)));
-  }
-
-  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
-                               const DomTreeNodeBase<NodeT> *B) const {
-    const DomTreeNodeBase<NodeT> *IDom;
-    if (A == 0 || B == 0) return false;
-    while ((IDom = B->getIDom()) != 0 && IDom != A && IDom != B)
-      B = IDom;   // Walk up the tree
-    return IDom != 0;
+    return dominates(A, B);
   }
 
+  bool properlyDominates(const NodeT *A, const NodeT *B);
 
   /// isReachableFromEntry - Return true if A is dominated by the entry
   /// block of the function containing it.
-  bool isReachableFromEntry(const NodeT* A) {
+  bool isReachableFromEntry(const NodeT* A) const {
     assert(!this->isPostDominator() &&
            "This is not implemented for post dominators");
-    return dominates(&A->getParent()->front(), A);
+    return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
+  }
+
+  inline bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const {
+    return A;
   }
 
   /// dominates - Returns true iff A dominates B.  Note that this is not a
@@ -378,10 +377,16 @@ public:
   ///
   inline bool dominates(const DomTreeNodeBase<NodeT> *A,
                         const DomTreeNodeBase<NodeT> *B) {
+    // A node trivially dominates itself.
     if (B == A)
-      return true;  // A node trivially dominates itself.
+      return true;
 
-    if (A == 0 || B == 0)
+    // An unreachable node is dominated by anything.
+    if (!isReachableFromEntry(B))
+      return true;
+
+    // And dominates nothing.
+    if (!isReachableFromEntry(A))
       return false;
 
     // Compare the result of the tree walk and the dfs numbers, if expensive
@@ -406,16 +411,7 @@ public:
     return dominatedBySlowTreeWalk(A, B);
   }
 
-  inline bool dominates(const NodeT *A, const NodeT *B) {
-    if (A == B)
-      return true;
-
-    // Cast away the const qualifiers here. This is ok since
-    // this function doesn't actually return the values returned
-    // from getNode.
-    return dominates(getNode(const_cast<NodeT *>(A)),
-                     getNode(const_cast<NodeT *>(B)));
-  }
+  bool dominates(const NodeT *A, const NodeT *B);
 
   NodeT *getRoot() const {
     assert(this->Roots.size() == 1 && "Should always have entry node!");
@@ -623,9 +619,8 @@ protected:
   }
 
   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
-    typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.find(BB);
-    if (I != this->DomTreeNodes.end() && I->second)
-      return I->second;
+    if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
+      return Node;
 
     // Haven't calculated this node yet?  Get or calculate the node for the
     // immediate dominator.
@@ -641,8 +636,7 @@ protected:
   }
 
   inline NodeT *getIDom(NodeT *BB) const {
-    typename DenseMap<NodeT*, NodeT*>::const_iterator I = IDoms.find(BB);
-    return I != IDoms.end() ? I->second : 0;
+    return IDoms.lookup(BB);
   }
 
   inline void addRoot(NodeT* BB) {
@@ -653,21 +647,24 @@ public:
   /// recalculate - compute a dominator tree for the given function
   template<class FT>
   void recalculate(FT& F) {
+    typedef GraphTraits<FT*> TraitsTy;
     reset();
     this->Vertex.push_back(0);
 
     if (!this->IsPostDominators) {
       // Initialize root
-      this->Roots.push_back(&F.front());
-      this->IDoms[&F.front()] = 0;
-      this->DomTreeNodes[&F.front()] = 0;
+      NodeT *entry = TraitsTy::getEntryNode(&F);
+      this->Roots.push_back(entry);
+      this->IDoms[entry] = 0;
+      this->DomTreeNodes[entry] = 0;
 
       Calculate<FT, NodeT*>(*this, F);
     } else {
       // Initialize the roots list
-      for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) {
-        if (std::distance(GraphTraits<FT*>::child_begin(I),
-                          GraphTraits<FT*>::child_end(I)) == 0)
+      for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F),
+                                        E = TraitsTy::nodes_end(&F); I != E; ++I) {
+        if (std::distance(TraitsTy::child_begin(I),
+                          TraitsTy::child_end(I)) == 0)
           addRoot(I);
 
         // Prepopulate maps so that we don't get iterator invalidation issues later.
@@ -680,6 +677,32 @@ public:
   }
 };
 
+// These two functions are declared out of line as a workaround for building
+// with old (< r147295) versions of clang because of pr11642.
+template<class NodeT>
+bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) {
+  if (A == B)
+    return true;
+
+  // Cast away the const qualifiers here. This is ok since
+  // this function doesn't actually return the values returned
+  // from getNode.
+  return dominates(getNode(const_cast<NodeT *>(A)),
+                   getNode(const_cast<NodeT *>(B)));
+}
+template<class NodeT>
+bool
+DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A, const NodeT *B) {
+  if (A == B)
+    return false;
+
+  // Cast away the const qualifiers here. This is ok since
+  // this function doesn't actually return the values returned
+  // from getNode.
+  return dominates(getNode(const_cast<NodeT *>(A)),
+                   getNode(const_cast<NodeT *>(B)));
+}
+
 EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>);
 
 //===-------------------------------------
@@ -749,9 +772,12 @@ public:
     return DT->dominates(A, B);
   }
 
-  // dominates - Return true if A dominates B. This performs the
-  // special checks necessary if A and B are in the same basic block.
-  bool dominates(const Instruction *A, const Instruction *B) const;
+  // dominates - Return true if Def dominates a use in User. This performs
+  // the special checks necessary if Def and User are in the same basic block.
+  // Note that Def doesn't dominate a use in Def itself!
+  bool dominates(const Instruction *Def, const Use &U) const;
+  bool dominates(const Instruction *Def, const Instruction *User) const;
+  bool dominates(const Instruction *Def, const BasicBlock *BB) const;
 
   bool properlyDominates(const DomTreeNode *A, const DomTreeNode *B) const {
     return DT->properlyDominates(A, B);
@@ -814,10 +840,12 @@ public:
     DT->splitBlock(NewBB);
   }
 
-  bool isReachableFromEntry(const BasicBlock* A) {
+  bool isReachableFromEntry(const BasicBlock* A) const {
     return DT->isReachableFromEntry(A);
   }
 
+  bool isReachableFromEntry(const Use &U) const;
+
 
   virtual void releaseMemory() {
     DT->releaseMemory();
diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h
index 2fb607cc5c37..2bf79b9c932b 100644
--- a/include/llvm/Analysis/IVUsers.h
+++ b/include/llvm/Analysis/IVUsers.h
@@ -166,10 +166,16 @@ public:
   const_iterator end() const   { return IVUses.end(); }
   bool empty() const { return IVUses.empty(); }
 
+  bool isIVUserOrOperand(Instruction *Inst) const {
+    return Processed.count(Inst);
+  }
+
   void print(raw_ostream &OS, const Module* = 0) const;
 
   /// dump - This method is used for debugging.
   void dump() const;
+protected:
+  bool AddUsersImpl(Instruction *I, SmallPtrSet<Loop*,16> &SimpleLoopNests);
 };
 
 Pass *createIVUsersPass();
diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h
index 36a16e68df07..691c2d19be9a 100644
--- a/include/llvm/Analysis/InlineCost.h
+++ b/include/llvm/Analysis/InlineCost.h
@@ -14,171 +14,118 @@
 #ifndef LLVM_ANALYSIS_INLINECOST_H
 #define LLVM_ANALYSIS_INLINECOST_H
 
-#include <cassert>
-#include <climits>
-#include <vector>
+#include "llvm/Function.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/ValueMap.h"
 #include "llvm/Analysis/CodeMetrics.h"
+#include <cassert>
+#include <climits>
+#include <vector>
 
 namespace llvm {
 
-  class Value;
-  class Function;
-  class BasicBlock;
   class CallSite;
-  template<class PtrType, unsigned SmallSize>
-  class SmallPtrSet;
   class TargetData;
 
   namespace InlineConstants {
     // Various magic constants used to adjust heuristics.
     const int InstrCost = 5;
-    const int IndirectCallBonus = -100;
+    const int IndirectCallThreshold = 100;
     const int CallPenalty = 25;
     const int LastCallToStaticBonus = -15000;
     const int ColdccPenalty = 2000;
     const int NoreturnPenalty = 10000;
   }
 
-  /// InlineCost - Represent the cost of inlining a function. This
-  /// supports special values for functions which should "always" or
-  /// "never" be inlined. Otherwise, the cost represents a unitless
-  /// amount; smaller values increase the likelihood of the function
-  /// being inlined.
+  /// \brief Represents the cost of inlining a function.
+  ///
+  /// This supports special values for functions which should "always" or
+  /// "never" be inlined. Otherwise, the cost represents a unitless amount;
+  /// smaller values increase the likelihood of the function being inlined.
+  ///
+  /// Objects of this type also provide the adjusted threshold for inlining
+  /// based on the information available for a particular callsite. They can be
+  /// directly tested to determine if inlining should occur given the cost and
+  /// threshold for this cost metric.
   class InlineCost {
-    enum Kind {
-      Value,
-      Always,
-      Never
+    enum SentinelValues {
+      AlwaysInlineCost = INT_MIN,
+      NeverInlineCost = INT_MAX
     };
 
-    // This is a do-it-yourself implementation of
-    //   int Cost : 30;
-    //   unsigned Type : 2;
-    // We used to use bitfields, but they were sometimes miscompiled (PR3822).
-    enum { TYPE_BITS = 2 };
-    enum { COST_BITS = unsigned(sizeof(unsigned)) * CHAR_BIT - TYPE_BITS };
-    unsigned TypedCost; // int Cost : COST_BITS; unsigned Type : TYPE_BITS;
+    /// \brief The estimated cost of inlining this callsite.
+    const int Cost;
 
-    Kind getType() const {
-      return Kind(TypedCost >> COST_BITS);
-    }
+    /// \brief The adjusted threshold against which this cost was computed.
+    const int Threshold;
 
-    int getCost() const {
-      // Sign-extend the bottom COST_BITS bits.
-      return (int(TypedCost << TYPE_BITS)) >> TYPE_BITS;
-    }
+    // Trivial constructor, interesting logic in the factory functions below.
+    InlineCost(int Cost, int Threshold)
+      : Cost(Cost), Threshold(Threshold) {}
 
-    InlineCost(int C, int T) {
-      TypedCost = (unsigned(C << TYPE_BITS) >> TYPE_BITS) | (T << COST_BITS);
-      assert(getCost() == C && "Cost exceeds InlineCost precision");
-    }
   public:
-    static InlineCost get(int Cost) { return InlineCost(Cost, Value); }
-    static InlineCost getAlways() { return InlineCost(0, Always); }
-    static InlineCost getNever() { return InlineCost(0, Never); }
-
-    bool isVariable() const { return getType() == Value; }
-    bool isAlways() const { return getType() == Always; }
-    bool isNever() const { return getType() == Never; }
-
-    /// getValue() - Return a "variable" inline cost's amount. It is
-    /// an error to call this on an "always" or "never" InlineCost.
-    int getValue() const {
-      assert(getType() == Value && "Invalid access of InlineCost");
-      return getCost();
+    static InlineCost get(int Cost, int Threshold) {
+      assert(Cost > AlwaysInlineCost && "Cost crosses sentinel value");
+      assert(Cost < NeverInlineCost && "Cost crosses sentinel value");
+      return InlineCost(Cost, Threshold);
+    }
+    static InlineCost getAlways() {
+      return InlineCost(AlwaysInlineCost, 0);
+    }
+    static InlineCost getNever() {
+      return InlineCost(NeverInlineCost, 0);
     }
-  };
-
-  /// InlineCostAnalyzer - Cost analyzer used by inliner.
-  class InlineCostAnalyzer {
-    struct ArgInfo {
-    public:
-      unsigned ConstantWeight;
-      unsigned AllocaWeight;
-
-      ArgInfo(unsigned CWeight, unsigned AWeight)
-        : ConstantWeight(CWeight), AllocaWeight(AWeight)
-          {}
-    };
-
-    struct FunctionInfo {
-      CodeMetrics Metrics;
 
-      /// ArgumentWeights - Each formal argument of the function is inspected to
-      /// see if it is used in any contexts where making it a constant or alloca
-      /// would reduce the code size.  If so, we add some value to the argument
-      /// entry here.
-      std::vector<ArgInfo> ArgumentWeights;
+    /// \brief Test whether the inline cost is low enough for inlining.
+    operator bool() const {
+      return Cost < Threshold;
+    }
 
-      /// analyzeFunction - Add information about the specified function
-      /// to the current structure.
-      void analyzeFunction(Function *F, const TargetData *TD);
+    bool isAlways() const   { return Cost == AlwaysInlineCost; }
+    bool isNever() const    { return Cost == NeverInlineCost; }
+    bool isVariable() const { return !isAlways() && !isNever(); }
 
-      /// NeverInline - Returns true if the function should never be
-      /// inlined into any caller.
-      bool NeverInline();
-    };
+    /// \brief Get the inline cost estimate.
+    /// It is an error to call this on an "always" or "never" InlineCost.
+    int getCost() const {
+      assert(isVariable() && "Invalid access of InlineCost");
+      return Cost;
+    }
 
-    // The Function* for a function can be changed (by ArgumentPromotion);
-    // the ValueMap will update itself when this happens.
-    ValueMap<const Function *, FunctionInfo> CachedFunctionInfo;
+    /// \brief Get the cost delta from the threshold for inlining.
+    /// Only valid if the cost is of the variable kind. Returns a negative
+    /// value if the cost is too high to inline.
+    int getCostDelta() const { return Threshold - getCost(); }
+  };
 
+  /// InlineCostAnalyzer - Cost analyzer used by inliner.
+  class InlineCostAnalyzer {
     // TargetData if available, or null.
     const TargetData *TD;
 
-    int CountBonusForConstant(Value *V, Constant *C = NULL);
-    int ConstantFunctionBonus(CallSite CS, Constant *C);
-    int getInlineSize(CallSite CS, Function *Callee);
-    int getInlineBonuses(CallSite CS, Function *Callee);
   public:
     InlineCostAnalyzer(): TD(0) {}
 
     void setTargetData(const TargetData *TData) { TD = TData; }
 
-    /// getInlineCost - The heuristic used to determine if we should inline the
-    /// function call or not.
+    /// \brief Get an InlineCost object representing the cost of inlining this
+    /// callsite.
     ///
-    InlineCost getInlineCost(CallSite CS,
-                             SmallPtrSet<const Function *, 16> &NeverInline);
+    /// Note that threshold is passed into this function. Only costs below the
+    /// threshold are computed with any accuracy. The threshold can be used to
+    /// bound the computation necessary to determine whether the cost is
+    /// sufficiently low to warrant inlining.
+    InlineCost getInlineCost(CallSite CS, int Threshold);
     /// getCalledFunction - The heuristic used to determine if we should inline
     /// the function call or not.  The callee is explicitly specified, to allow
-    /// you to calculate the cost of inlining a function via a pointer.  The
-    /// result assumes that the inlined version will always be used.  You should
-    /// weight it yourself in cases where this callee will not always be called.
-    InlineCost getInlineCost(CallSite CS,
-                             Function *Callee,
-                             SmallPtrSet<const Function *, 16> &NeverInline);
-
-    /// getSpecializationBonus - The heuristic used to determine the per-call
-    /// performance boost for using a specialization of Callee with argument
-    /// SpecializedArgNos replaced by a constant.
-    int getSpecializationBonus(Function *Callee,
-             SmallVectorImpl<unsigned> &SpecializedArgNo);
-
-    /// getSpecializationCost - The heuristic used to determine the code-size
-    /// impact of creating a specialized version of Callee with argument
-    /// SpecializedArgNo replaced by a constant.
-    InlineCost getSpecializationCost(Function *Callee,
-               SmallVectorImpl<unsigned> &SpecializedArgNo);
-
-    /// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a
-    /// higher threshold to determine if the function call should be inlined.
-    float getInlineFudgeFactor(CallSite CS);
-
-    /// resetCachedFunctionInfo - erase any cached cost info for this function.
-    void resetCachedCostInfo(Function* Caller) {
-      CachedFunctionInfo[Caller] = FunctionInfo();
-    }
-
-    /// growCachedCostInfo - update the cached cost info for Caller after Callee
-    /// has been inlined. If Callee is NULL it means a dead call has been
-    /// eliminated.
-    void growCachedCostInfo(Function* Caller, Function* Callee);
-
-    /// clear - empty the cache of inline costs
-    void clear();
+    /// you to calculate the cost of inlining a function via a pointer.  This
+    /// behaves exactly as the version with no explicit callee parameter in all
+    /// other respects.
+    //
+    //  Note: This is used by out-of-tree passes, please do not remove without
+    //  adding a replacement API.
+    InlineCost getInlineCost(CallSite CS, Function *Callee, int Threshold);
   };
 
   /// callIsSmall - If a call is likely to lower to a single target instruction,
diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h
index c1d87d3f7712..152e885bf667 100644
--- a/include/llvm/Analysis/InstructionSimplify.h
+++ b/include/llvm/Analysis/InstructionSimplify.h
@@ -20,147 +20,198 @@
 #define LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
 
 namespace llvm {
+  template<typename T>
+  class ArrayRef;
   class DominatorTree;
   class Instruction;
-  class Value;
   class TargetData;
-  template<typename T>
-  class ArrayRef;
+  class TargetLibraryInfo;
+  class Type;
+  class Value;
 
   /// SimplifyAddInst - Given operands for an Add, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyAddInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
-                         const TargetData *TD = 0, const DominatorTree *DT = 0);
+                         const TargetData *TD = 0,
+                         const TargetLibraryInfo *TLI = 0,
+                         const DominatorTree *DT = 0);
 
   /// SimplifySubInst - Given operands for a Sub, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifySubInst(Value *LHS, Value *RHS, bool isNSW, bool isNUW,
-                         const TargetData *TD = 0, const DominatorTree *DT = 0);
+                         const TargetData *TD = 0,
+                         const TargetLibraryInfo *TLI = 0,
+                         const DominatorTree *DT = 0);
 
   /// SimplifyMulInst - Given operands for a Mul, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyMulInst(Value *LHS, Value *RHS, const TargetData *TD = 0,
+                         const TargetLibraryInfo *TLI = 0,
                          const DominatorTree *DT = 0);
 
   /// SimplifySDivInst - Given operands for an SDiv, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifySDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0,
+                          const TargetLibraryInfo *TLI = 0,
                           const DominatorTree *DT = 0);
 
   /// SimplifyUDivInst - Given operands for a UDiv, see if we can
   /// fold the result.  If not, this returns null.
-  Value *SimplifyUDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0,
+  Value *SimplifyUDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0, 
+                          const TargetLibraryInfo *TLI = 0,
                           const DominatorTree *DT = 0);
 
   /// SimplifyFDivInst - Given operands for an FDiv, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyFDivInst(Value *LHS, Value *RHS, const TargetData *TD = 0,
+                          const TargetLibraryInfo *TLI = 0,
                           const DominatorTree *DT = 0);
 
   /// SimplifySRemInst - Given operands for an SRem, see if we can
   /// fold the result.  If not, this returns null.
-  Value *SimplifySRemInst(Value *LHS, Value *RHS, const TargetData *TD = 0,
+  Value *SimplifySRemInst(Value *LHS, Value *RHS, const TargetData *TD = 0, 
+                          const TargetLibraryInfo *TLI = 0,
                           const DominatorTree *DT = 0);
 
   /// SimplifyURemInst - Given operands for a URem, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyURemInst(Value *LHS, Value *RHS, const TargetData *TD = 0,
+                          const TargetLibraryInfo *TLI = 0,
                           const DominatorTree *DT = 0);
 
   /// SimplifyFRemInst - Given operands for an FRem, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyFRemInst(Value *LHS, Value *RHS, const TargetData *TD = 0,
+                          const TargetLibraryInfo *TLI = 0,
                           const DominatorTree *DT = 0);
 
   /// SimplifyShlInst - Given operands for a Shl, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyShlInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
-                         const TargetData *TD = 0, const DominatorTree *DT = 0);
+                         const TargetData *TD = 0, 
+                         const TargetLibraryInfo *TLI = 0,
+                         const DominatorTree *DT = 0);
 
   /// SimplifyLShrInst - Given operands for a LShr, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyLShrInst(Value *Op0, Value *Op1, bool isExact,
-                          const TargetData *TD = 0, const DominatorTree *DT=0);
+                          const TargetData *TD = 0,
+                          const TargetLibraryInfo *TLI = 0,
+                          const DominatorTree *DT = 0);
 
   /// SimplifyAShrInst - Given operands for a AShr, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyAShrInst(Value *Op0, Value *Op1, bool isExact,
                           const TargetData *TD = 0,
+                          const TargetLibraryInfo *TLI = 0,
                           const DominatorTree *DT = 0);
 
   /// SimplifyAndInst - Given operands for an And, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyAndInst(Value *LHS, Value *RHS, const TargetData *TD = 0,
+                         const TargetLibraryInfo *TLI = 0,
                          const DominatorTree *DT = 0);
 
   /// SimplifyOrInst - Given operands for an Or, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyOrInst(Value *LHS, Value *RHS, const TargetData *TD = 0,
+                        const TargetLibraryInfo *TLI = 0,
                         const DominatorTree *DT = 0);
 
   /// SimplifyXorInst - Given operands for a Xor, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyXorInst(Value *LHS, Value *RHS, const TargetData *TD = 0,
+                         const TargetLibraryInfo *TLI = 0,
                          const DominatorTree *DT = 0);
 
   /// SimplifyICmpInst - Given operands for an ICmpInst, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS,
-                          const TargetData *TD = 0,
+                          const TargetData *TD = 0, 
+                          const TargetLibraryInfo *TLI = 0,
                           const DominatorTree *DT = 0);
 
   /// SimplifyFCmpInst - Given operands for an FCmpInst, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
-                          const TargetData *TD = 0,
+                          const TargetData *TD = 0, 
+                          const TargetLibraryInfo *TLI = 0,
                           const DominatorTree *DT = 0);
 
   /// SimplifySelectInst - Given operands for a SelectInst, see if we can fold
   /// the result.  If not, this returns null.
   Value *SimplifySelectInst(Value *Cond, Value *TrueVal, Value *FalseVal,
                             const TargetData *TD = 0,
+                            const TargetLibraryInfo *TLI = 0,
                             const DominatorTree *DT = 0);
 
   /// SimplifyGEPInst - Given operands for an GetElementPtrInst, see if we can
   /// fold the result.  If not, this returns null.
-  Value *SimplifyGEPInst(ArrayRef<Value *> Ops,
-                         const TargetData *TD = 0, const DominatorTree *DT = 0);
+  Value *SimplifyGEPInst(ArrayRef<Value *> Ops, const TargetData *TD = 0,
+                         const TargetLibraryInfo *TLI = 0,
+                         const DominatorTree *DT = 0);
 
   /// SimplifyInsertValueInst - Given operands for an InsertValueInst, see if we
   /// can fold the result.  If not, this returns null.
   Value *SimplifyInsertValueInst(Value *Agg, Value *Val,
                                  ArrayRef<unsigned> Idxs,
                                  const TargetData *TD = 0,
+                                 const TargetLibraryInfo *TLI = 0,
                                  const DominatorTree *DT = 0);
 
+  /// SimplifyTruncInst - Given operands for an TruncInst, see if we can fold
+  /// the result.  If not, this returns null.
+  Value *SimplifyTruncInst(Value *Op, Type *Ty, const TargetData *TD = 0,
+                           const TargetLibraryInfo *TLI = 0,
+                           const DominatorTree *DT = 0);
+
   //=== Helper functions for higher up the class hierarchy.
 
 
   /// SimplifyCmpInst - Given operands for a CmpInst, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyCmpInst(unsigned Predicate, Value *LHS, Value *RHS,
-                         const TargetData *TD = 0, const DominatorTree *DT = 0);
+                         const TargetData *TD = 0,
+                         const TargetLibraryInfo *TLI = 0,
+                         const DominatorTree *DT = 0);
 
   /// SimplifyBinOp - Given operands for a BinaryOperator, see if we can
   /// fold the result.  If not, this returns null.
   Value *SimplifyBinOp(unsigned Opcode, Value *LHS, Value *RHS,
-                       const TargetData *TD = 0, const DominatorTree *DT = 0);
+                       const TargetData *TD = 0, 
+                       const TargetLibraryInfo *TLI = 0,
+                       const DominatorTree *DT = 0);
 
   /// SimplifyInstruction - See if we can compute a simplified version of this
   /// instruction.  If not, this returns null.
   Value *SimplifyInstruction(Instruction *I, const TargetData *TD = 0,
+                             const TargetLibraryInfo *TLI = 0,
                              const DominatorTree *DT = 0);
 
 
-  /// ReplaceAndSimplifyAllUses - Perform From->replaceAllUsesWith(To) and then
-  /// delete the From instruction.  In addition to a basic RAUW, this does a
-  /// recursive simplification of the updated instructions.  This catches
-  /// things where one simplification exposes other opportunities.  This only
-  /// simplifies and deletes scalar operations, it does not change the CFG.
+  /// \brief Replace all uses of 'I' with 'SimpleV' and simplify the uses
+  /// recursively.
   ///
-  void ReplaceAndSimplifyAllUses(Instruction *From, Value *To,
-                                 const TargetData *TD = 0,
-                                 const DominatorTree *DT = 0);
+  /// This first performs a normal RAUW of I with SimpleV. It then recursively
+  /// attempts to simplify those users updated by the operation. The 'I'
+  /// instruction must not be equal to the simplified value 'SimpleV'.
+  ///
+  /// The function returns true if any simplifications were performed.
+  bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV,
+                                     const TargetData *TD = 0,
+                                     const TargetLibraryInfo *TLI = 0,
+                                     const DominatorTree *DT = 0);
+
+  /// \brief Recursively attempt to simplify an instruction.
+  ///
+  /// This routine uses SimplifyInstruction to simplify 'I', and if successful
+  /// replaces uses of 'I' with the simplified value. It then recurses on each
+  /// of the users impacted. It returns true if any simplifications were
+  /// performed.
+  bool recursivelySimplifyInstruction(Instruction *I,
+                                      const TargetData *TD = 0,
+                                      const TargetLibraryInfo *TLI = 0,
+                                      const DominatorTree *DT = 0);
 } // end namespace llvm
 
 #endif
diff --git a/include/llvm/Analysis/IntervalIterator.h b/include/llvm/Analysis/IntervalIterator.h
index 82b3294cc504..0968c7468e68 100644
--- a/include/llvm/Analysis/IntervalIterator.h
+++ b/include/llvm/Analysis/IntervalIterator.h
@@ -101,14 +101,14 @@ public:
   IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
     OrigContainer = M;
     if (!ProcessInterval(&M->front())) {
-      assert(0 && "ProcessInterval should never fail for first interval!");
+      llvm_unreachable("ProcessInterval should never fail for first interval!");
     }
   }
 
   IntervalIterator(IntervalPartition &IP, bool OwnMemory) : IOwnMem(OwnMemory) {
     OrigContainer = &IP;
     if (!ProcessInterval(IP.getRootInterval())) {
-      assert(0 && "ProcessInterval should never fail for first interval!");
+      llvm_unreachable("ProcessInterval should never fail for first interval!");
     }
   }
 
diff --git a/include/llvm/Analysis/LazyValueInfo.h b/include/llvm/Analysis/LazyValueInfo.h
index fc4d0af920e9..065c230fb2fd 100644
--- a/include/llvm/Analysis/LazyValueInfo.h
+++ b/include/llvm/Analysis/LazyValueInfo.h
@@ -20,12 +20,14 @@
 namespace llvm {
   class Constant;
   class TargetData;
+  class TargetLibraryInfo;
   class Value;
   
 /// LazyValueInfo - This pass computes, caches, and vends lazy value constraint
 /// information.
 class LazyValueInfo : public FunctionPass {
   class TargetData *TD;
+  class TargetLibraryInfo *TLI;
   void *PImpl;
   LazyValueInfo(const LazyValueInfo&); // DO NOT IMPLEMENT.
   void operator=(const LazyValueInfo&); // DO NOT IMPLEMENT.
@@ -68,9 +70,7 @@ public:
   
   // Implementation boilerplate.
   
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-    AU.setPreservesAll();
-  }
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
   virtual void releaseMemory();
   virtual bool runOnFunction(Function &F);
 };
diff --git a/include/llvm/Analysis/Loads.h b/include/llvm/Analysis/Loads.h
index 1574262dd6d3..5f0aefbeb015 100644
--- a/include/llvm/Analysis/Loads.h
+++ b/include/llvm/Analysis/Loads.h
@@ -20,6 +20,7 @@ namespace llvm {
 
 class AliasAnalysis;
 class TargetData;
+class MDNode;
 
 /// isSafeToLoadUnconditionally - Return true if we know that executing a load
 /// from this value cannot trap.  If it is not obviously safe to load from the
@@ -41,10 +42,15 @@ bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom,
 /// MaxInstsToScan specifies the maximum instructions to scan in the block.
 /// If it is set to 0, it will scan the whole block. You can also optionally
 /// specify an alias analysis implementation, which makes this more precise.
+///
+/// If TBAATag is non-null and a load or store is found, the TBAA tag from the
+/// load or store is recorded there.  If there is no TBAA tag or if no access
+/// is found, it is left unmodified.
 Value *FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB,
                                 BasicBlock::iterator &ScanFrom,
                                 unsigned MaxInstsToScan = 6,
-                                AliasAnalysis *AA = 0);
+                                AliasAnalysis *AA = 0,
+                                MDNode **TBAATag = 0);
 
 }
 
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 12cb6c5cc480..91feaaac038d 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -23,7 +23,6 @@
 //  * whether or not a particular block branches out of the loop
 //  * the successor blocks of the loop
 //  * the loop depth
-//  * the trip count
 //  * etc...
 //
 //===----------------------------------------------------------------------===//
@@ -416,14 +415,26 @@ public:
 #ifndef NDEBUG
     assert(!Blocks.empty() && "Loop header is missing");
 
+    // Setup for using a depth-first iterator to visit every block in the loop.
+    SmallVector<BlockT*, 8> ExitBBs;
+    getExitBlocks(ExitBBs);
+    llvm::SmallPtrSet<BlockT*, 8> VisitSet;
+    VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
+    df_ext_iterator<BlockT*, llvm::SmallPtrSet<BlockT*, 8> >
+        BI = df_ext_begin(getHeader(), VisitSet),
+        BE = df_ext_end(getHeader(), VisitSet);
+
+    // Keep track of the number of BBs visited.
+    unsigned NumVisited = 0;
+
     // Sort the blocks vector so that we can use binary search to do quick
     // lookups.
     SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
     std::sort(LoopBBs.begin(), LoopBBs.end());
 
     // Check the individual blocks.
-    for (block_iterator I = block_begin(), E = block_end(); I != E; ++I) {
-      BlockT *BB = *I;
+    for ( ; BI != BE; ++BI) {
+      BlockT *BB = *BI;
       bool HasInsideLoopSuccs = false;
       bool HasInsideLoopPreds = false;
       SmallVector<BlockT *, 2> OutsideLoopPreds;
@@ -440,7 +451,7 @@ public:
       for (typename InvBlockTraits::ChildIteratorType PI =
            InvBlockTraits::child_begin(BB), PE = InvBlockTraits::child_end(BB);
            PI != PE; ++PI) {
-        typename InvBlockTraits::NodeType *N = *PI;
+        BlockT *N = *PI;
         if (std::binary_search(LoopBBs.begin(), LoopBBs.end(), N))
           HasInsideLoopPreds = true;
         else
@@ -464,8 +475,12 @@ public:
       assert(HasInsideLoopSuccs && "Loop block has no in-loop successors!");
       assert(BB != getHeader()->getParent()->begin() &&
              "Loop contains function entry block!");
+
+      NumVisited++;
     }
 
+    assert(NumVisited == getNumBlocks() && "Unreachable block in loop");
+
     // Check the subloops.
     for (iterator I = begin(), E = end(); I != E; ++I)
       // Each block in each subloop should be contained within this loop.
@@ -571,37 +586,6 @@ public:
   ///
   PHINode *getCanonicalInductionVariable() const;
 
-  /// getTripCount - Return a loop-invariant LLVM value indicating the number of
-  /// times the loop will be executed.  Note that this means that the backedge
-  /// of the loop executes N-1 times.  If the trip-count cannot be determined,
-  /// this returns null.
-  ///
-  /// The IndVarSimplify pass transforms loops to have a form that this
-  /// function easily understands.
-  ///
-  Value *getTripCount() const;
-
-  /// getSmallConstantTripCount - Returns the trip count of this loop as a
-  /// normal unsigned value, if possible. Returns 0 if the trip count is unknown
-  /// of not constant. Will also return 0 if the trip count is very large
-  /// (>= 2^32)
-  ///
-  /// The IndVarSimplify pass transforms loops to have a form that this
-  /// function easily understands.
-  ///
-  unsigned getSmallConstantTripCount() const;
-
-  /// getSmallConstantTripMultiple - Returns the largest constant divisor of the
-  /// trip count of this loop as a normal unsigned value, if possible. This
-  /// means that the actual trip count is always a multiple of the returned
-  /// value (don't forget the trip count could very well be zero as well!).
-  ///
-  /// Returns 1 if the trip count is unknown or not guaranteed to be the
-  /// multiple of a constant (which is also the case if the trip count is simply
-  /// constant, use getSmallConstantTripCount for that case), Will also return 1
-  /// if the trip count is very large (>= 2^32).
-  unsigned getSmallConstantTripMultiple() const;
-
   /// isLCSSAForm - Return true if the Loop is in LCSSA form
   bool isLCSSAForm(DominatorTree &DT) const;
 
@@ -610,6 +594,9 @@ public:
   /// normal form.
   bool isLoopSimplifyForm() const;
 
+  /// isSafeToClone - Return true if the loop body is safe to clone in practice.
+  bool isSafeToClone() const;
+
   /// hasDedicatedExits - Return true if no exit block for the loop
   /// has a predecessor that is outside the loop.
   bool hasDedicatedExits() const;
@@ -671,9 +658,7 @@ public:
   /// block is in no loop (for example the entry node), null is returned.
   ///
   LoopT *getLoopFor(const BlockT *BB) const {
-    typename DenseMap<BlockT *, LoopT *>::const_iterator I=
-      BBMap.find(const_cast<BlockT*>(BB));
-    return I != BBMap.end() ? I->second : 0;
+    return BBMap.lookup(const_cast<BlockT*>(BB));
   }
 
   /// operator[] - same as getLoopFor...
@@ -712,9 +697,7 @@ public:
   /// the loop hierarchy tree.
   void changeLoopFor(BlockT *BB, LoopT *L) {
     if (!L) {
-      typename DenseMap<BlockT *, LoopT *>::iterator I = BBMap.find(BB);
-      if (I != BBMap.end())
-        BBMap.erase(I);
+      BBMap.erase(BB);
       return;
     }
     BBMap[BB] = L;
@@ -771,7 +754,7 @@ public:
   }
 
   LoopT *ConsiderForLoop(BlockT *BB, DominatorTreeBase<BlockT> &DT) {
-    if (BBMap.find(BB) != BBMap.end()) return 0;// Haven't processed this node?
+    if (BBMap.count(BB)) return 0; // Haven't processed this node?
 
     std::vector<BlockT *> TodoStack;
 
@@ -782,7 +765,8 @@ public:
          InvBlockTraits::child_begin(BB), E = InvBlockTraits::child_end(BB);
          I != E; ++I) {
       typename InvBlockTraits::NodeType *N = *I;
-      if (DT.dominates(BB, N))   // If BB dominates its predecessor...
+      // If BB dominates its predecessor...
+      if (DT.dominates(BB, N) && DT.isReachableFromEntry(N))
           TodoStack.push_back(N);
     }
 
@@ -792,14 +776,12 @@ public:
     LoopT *L = new LoopT(BB);
     BBMap[BB] = L;
 
-    BlockT *EntryBlock = BB->getParent()->begin();
-
     while (!TodoStack.empty()) {  // Process all the nodes in the loop
       BlockT *X = TodoStack.back();
       TodoStack.pop_back();
 
       if (!L->contains(X) &&         // As of yet unprocessed??
-          DT.dominates(EntryBlock, X)) {   // X is reachable from entry block?
+          DT.isReachableFromEntry(X)) {
         // Check to see if this block already belongs to a loop.  If this occurs
         // then we have a case where a loop that is supposed to be a child of
         // the current loop was processed before the current loop.  When this
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index e18d937f6916..68ce364f4413 100644
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -324,6 +324,7 @@ namespace llvm {
     /// Current AA implementation, just a cache.
     AliasAnalysis *AA;
     TargetData *TD;
+    DominatorTree *DT;
     OwningPtr<PredIteratorCache> PredCache;
   public:
     MemoryDependenceAnalysis();
@@ -430,6 +431,9 @@ namespace llvm {
 
     void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
     
+    AliasAnalysis::ModRefResult
+    getModRefInfo(const Instruction *Inst, const AliasAnalysis::Location &Loc);
+
     /// verifyRemoved - Verify that the specified instruction does not occur
     /// in our internal data structures.
     void verifyRemoved(Instruction *Inst) const;
diff --git a/include/llvm/Analysis/PHITransAddr.h b/include/llvm/Analysis/PHITransAddr.h
index 033efba3e742..ff9a24790a99 100644
--- a/include/llvm/Analysis/PHITransAddr.h
+++ b/include/llvm/Analysis/PHITransAddr.h
@@ -20,7 +20,8 @@
 namespace llvm {
   class DominatorTree;
   class TargetData;
-  
+  class TargetLibraryInfo;
+
 /// PHITransAddr - An address value which tracks and handles phi translation.
 /// As we walk "up" the CFG through predecessors, we need to ensure that the
 /// address we're tracking is kept up to date.  For example, if we're analyzing
@@ -37,11 +38,14 @@ class PHITransAddr {
   
   /// TD - The target data we are playing with if known, otherwise null.
   const TargetData *TD;
+
+  /// TLI - The target library info if known, otherwise null.
+  const TargetLibraryInfo *TLI;
   
   /// InstInputs - The inputs for our symbolic address.
   SmallVector<Instruction*, 4> InstInputs;
 public:
-  PHITransAddr(Value *addr, const TargetData *td) : Addr(addr), TD(td) {
+  PHITransAddr(Value *addr, const TargetData *td) : Addr(addr), TD(td), TLI(0) {
     // If the address is an instruction, the whole thing is considered an input.
     if (Instruction *I = dyn_cast<Instruction>(Addr))
       InstInputs.push_back(I);
diff --git a/include/llvm/Analysis/ProfileInfo.h b/include/llvm/Analysis/ProfileInfo.h
index 300a0279042c..6c2e2732d344 100644
--- a/include/llvm/Analysis/ProfileInfo.h
+++ b/include/llvm/Analysis/ProfileInfo.h
@@ -22,6 +22,7 @@
 #define LLVM_ANALYSIS_PROFILEINFO_H
 
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
 #include <cassert>
@@ -85,13 +86,11 @@ namespace llvm {
 
     // getFunction() - Returns the Function for an Edge, checking for validity.
     static const FType* getFunction(Edge e) {
-      if (e.first) {
+      if (e.first)
         return e.first->getParent();
-      } else if (e.second) {
+      if (e.second)
         return e.second->getParent();
-      }
-      assert(0 && "Invalid ProfileInfo::Edge");
-      return (const FType*)0;
+      llvm_unreachable("Invalid ProfileInfo::Edge");
     }
 
     // getEdge() - Creates an Edge from two BasicBlocks.
diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h
index 9d8954595d61..b098eeaa3db8 100644
--- a/include/llvm/Analysis/RegionInfo.h
+++ b/include/llvm/Analysis/RegionInfo.h
@@ -681,7 +681,7 @@ inline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node) {
   if (Node.isSubRegion())
     return OS << Node.getNodeAs<Region>()->getNameStr();
   else
-    return OS << Node.getNodeAs<BasicBlock>()->getNameStr();
+    return OS << Node.getNodeAs<BasicBlock>()->getName();
 }
 } // End llvm namespace
 #endif
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 10d933e68f5b..72408f773840 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -41,6 +41,7 @@ namespace llvm {
   class Type;
   class ScalarEvolution;
   class TargetData;
+  class TargetLibraryInfo;
   class LLVMContext;
   class Loop;
   class LoopInfo;
@@ -118,6 +119,10 @@ namespace llvm {
     ///
     bool isAllOnesValue() const;
 
+    /// isNonConstantNegative - Return true if the specified scev is negated,
+    /// but not a constant.
+    bool isNonConstantNegative() const;
+
     /// print - Print out the internal representation of this scalar to the
     /// specified stream.  This should really only be used for debugging
     /// purposes.
@@ -135,7 +140,7 @@ namespace llvm {
       ID = X.FastID;
     }
     static bool Equals(const SCEV &X, const FoldingSetNodeID &ID,
-                       FoldingSetNodeID &TempID) {
+                       unsigned IDHash, FoldingSetNodeID &TempID) {
       return ID == X.FastID;
     }
     static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
@@ -224,6 +229,10 @@ namespace llvm {
     ///
     TargetData *TD;
 
+    /// TLI - The target library information for the target we are targeting.
+    ///
+    TargetLibraryInfo *TLI;
+
     /// DT - The dominator tree.
     ///
     DominatorTree *DT;
@@ -721,16 +730,21 @@ namespace llvm {
                                      const SCEV *LHS, const SCEV *RHS);
 
     /// getSmallConstantTripCount - Returns the maximum trip count of this loop
-    /// as a normal unsigned value, if possible. Returns 0 if the trip count is
-    /// unknown or not constant.
-    unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitBlock);
+    /// as a normal unsigned value. Returns 0 if the trip count is unknown or
+    /// not constant. This "trip count" assumes that control exits via
+    /// ExitingBlock. More precisely, it is the number of times that control may
+    /// reach ExitingBlock before taking the branch. For loops with multiple
+    /// exits, it may not be the number times that the loop header executes if
+    /// the loop exits prematurely via another branch.
+    unsigned getSmallConstantTripCount(Loop *L, BasicBlock *ExitingBlock);
 
     /// getSmallConstantTripMultiple - Returns the largest constant divisor of
     /// the trip count of this loop as a normal unsigned value, if
     /// possible. This means that the actual trip count is always a multiple of
     /// the returned value (don't forget the trip count could very well be zero
-    /// as well!).
-    unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitBlock);
+    /// as well!). As explained in the comments for getSmallConstantTripCount,
+    /// this assumes that control exits the loop via ExitingBlock.
+    unsigned getSmallConstantTripMultiple(Loop *L, BasicBlock *ExitingBlock);
 
     // getExitCount - Get the expression for the number of loop iterations for
     // which this loop is guaranteed not to exit via ExitingBlock. Otherwise
diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
index a4ad1451d412..c22fc3ab74b7 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -22,6 +22,8 @@
 #include <set>
 
 namespace llvm {
+  class TargetLowering;
+
   /// SCEVExpander - This class uses information about analyze scalars to
   /// rewrite expressions in canonical form.
   ///
@@ -58,6 +60,9 @@ namespace llvm {
     /// insert the IV increment at this position.
     Instruction *IVIncInsertPos;
 
+    /// Phis that complete an IV chain. Reuse
+    std::set<AssertingVH<PHINode> > ChainedPhis;
+
     /// CanonicalMode - When true, expressions are expanded in "canonical"
     /// form. In particular, addrecs are expanded as arithmetic based on
     /// a canonical induction variable. When false, expression are expanded
@@ -100,6 +105,7 @@ namespace llvm {
       InsertedExpressions.clear();
       InsertedValues.clear();
       InsertedPostIncValues.clear();
+      ChainedPhis.clear();
     }
 
     /// getOrInsertCanonicalInductionVariable - This method returns the
@@ -108,14 +114,18 @@ namespace llvm {
     /// starts at zero and steps by one on each iteration.
     PHINode *getOrInsertCanonicalInductionVariable(const Loop *L, Type *Ty);
 
-    /// hoistStep - Utility for hoisting an IV increment.
-    static bool hoistStep(Instruction *IncV, Instruction *InsertPos,
-                          const DominatorTree *DT);
+    /// getIVIncOperand - Return the induction variable increment's IV operand.
+    Instruction *getIVIncOperand(Instruction *IncV, Instruction *InsertPos,
+                                 bool allowScale);
+
+    /// hoistIVInc - Utility for hoisting an IV increment.
+    bool hoistIVInc(Instruction *IncV, Instruction *InsertPos);
 
     /// replaceCongruentIVs - replace congruent phis with their most canonical
     /// representative. Return the number of phis eliminated.
     unsigned replaceCongruentIVs(Loop *L, const DominatorTree *DT,
-                                 SmallVectorImpl<WeakVH> &DeadInsts);
+                                 SmallVectorImpl<WeakVH> &DeadInsts,
+                                 const TargetLowering *TLI = NULL);
 
     /// expandCodeFor - Insert code to directly compute the specified SCEV
     /// expression into the program.  The inserted code is inserted into the
@@ -161,6 +171,16 @@ namespace llvm {
     void clearInsertPoint() {
       Builder.ClearInsertionPoint();
     }
+
+    /// isInsertedInstruction - Return true if the specified instruction was
+    /// inserted by the code rewriter.  If so, the client should not modify the
+    /// instruction.
+    bool isInsertedInstruction(Instruction *I) const {
+      return InsertedValues.count(I) || InsertedPostIncValues.count(I);
+    }
+
+    void setChainedPhi(PHINode *PN) { ChainedPhis.insert(PN); }
+
   private:
     LLVMContext &getContext() const { return SE.getContext(); }
 
@@ -195,13 +215,6 @@ namespace llvm {
     /// result will be expanded to have that type, with a cast if necessary.
     Value *expandCodeFor(const SCEV *SH, Type *Ty = 0);
 
-    /// isInsertedInstruction - Return true if the specified instruction was
-    /// inserted by the code rewriter.  If so, the client should not modify the
-    /// instruction.
-    bool isInsertedInstruction(Instruction *I) const {
-      return InsertedValues.count(I) || InsertedPostIncValues.count(I);
-    }
-
     /// getRelevantLoop - Determine the most "relevant" loop for the given SCEV.
     const Loop *getRelevantLoop(const SCEV *);
 
@@ -244,6 +257,8 @@ namespace llvm {
                                        const Loop *L,
                                        Type *ExpandTy,
                                        Type *IntTy);
+    Value *expandIVInc(PHINode *PN, Value *StepV, const Loop *L,
+                       Type *ExpandTy, Type *IntTy, bool useSubtract);
   };
 }
 
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index b6f0ae54cfa0..47b371029186 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -491,7 +491,6 @@ namespace llvm {
 
     RetVal visitCouldNotCompute(const SCEVCouldNotCompute *S) {
       llvm_unreachable("Invalid use of SCEVCouldNotCompute!");
-      return RetVal();
     }
   };
 }
diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
index 68263300c726..f2f9db4ce4e8 100644
--- a/include/llvm/Analysis/ValueTracking.h
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -17,15 +17,15 @@
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/DataTypes.h"
-#include <string>
 
 namespace llvm {
-  template <typename T> class SmallVectorImpl;
   class Value;
   class Instruction;
   class APInt;
   class TargetData;
-  
+  class StringRef;
+  class MDNode;
+
   /// ComputeMaskedBits - Determine which of the bits specified in Mask are
   /// known to be either zero or one and return them in the KnownZero/KnownOne
   /// bit sets.  This code only analyzes bits in Mask, in order to short-circuit
@@ -36,10 +36,10 @@ namespace llvm {
   /// where V is a vector, the mask, known zero, and known one values are the
   /// same width as the vector element, and the bit is set only if it is true
   /// for all of the elements in the vector.
-  void ComputeMaskedBits(Value *V, const APInt &Mask, APInt &KnownZero,
-                         APInt &KnownOne, const TargetData *TD = 0,
-                         unsigned Depth = 0);
-  
+  void ComputeMaskedBits(Value *V,  APInt &KnownZero, APInt &KnownOne,
+                         const TargetData *TD = 0, unsigned Depth = 0);
+  void computeMaskedBitsLoad(const MDNode &Ranges, APInt &KnownZero);
+
   /// ComputeSignBit - Determine whether the sign bit is known to be zero or
   /// one.  Convenience wrapper around ComputeMaskedBits.
   void ComputeSignBit(Value *V, bool &KnownZero, bool &KnownOne,
@@ -48,8 +48,10 @@ namespace llvm {
   /// isPowerOfTwo - Return true if the given value is known to have exactly one
   /// bit set when defined. For vectors return true if every element is known to
   /// be a power of two when defined.  Supports values with integer or pointer
-  /// type and vectors of integers.
-  bool isPowerOfTwo(Value *V, const TargetData *TD = 0, unsigned Depth = 0);
+  /// type and vectors of integers.  If 'OrZero' is set then returns true if the
+  /// given value is either a power of two or zero.
+  bool isPowerOfTwo(Value *V, const TargetData *TD = 0, bool OrZero = false,
+                    unsigned Depth = 0);
 
   /// isKnownNonZero - Return true if the given value is known to be non-zero
   /// when defined.  For vectors return true if every element is known to be
@@ -123,16 +125,15 @@ namespace llvm {
     return GetPointerBaseWithConstantOffset(const_cast<Value*>(Ptr), Offset,TD);
   }
   
-  /// GetConstantStringInfo - This function computes the length of a
+  /// getConstantStringInfo - This function computes the length of a
   /// null-terminated C string pointed to by V.  If successful, it returns true
-  /// and returns the string in Str.  If unsuccessful, it returns false.  If
-  /// StopAtNul is set to true (the default), the returned string is truncated
-  /// by a nul character in the global.  If StopAtNul is false, the nul
-  /// character is included in the result string.
-  bool GetConstantStringInfo(const Value *V, std::string &Str,
-                             uint64_t Offset = 0,
-                             bool StopAtNul = true);
-                        
+  /// and returns the string in Str.  If unsuccessful, it returns false.  This
+  /// does not include the trailing nul character by default.  If TrimAtNul is
+  /// set to false, then this returns any trailing nul characters as well as any
+  /// other characters that come after it.
+  bool getConstantStringInfo(const Value *V, StringRef &Str,
+                             uint64_t Offset = 0, bool TrimAtNul = true);
+
   /// GetStringLength - If we can compute the length of the string pointed to by
   /// the specified pointer, return 'len+1'.  If we can't, return 0.
   uint64_t GetStringLength(Value *V);
@@ -154,6 +155,27 @@ namespace llvm {
   /// are lifetime markers.
   bool onlyUsedByLifetimeMarkers(const Value *V);
 
+  /// isSafeToSpeculativelyExecute - Return true if the instruction does not
+  /// have any effects besides calculating the result and does not have
+  /// undefined behavior.
+  ///
+  /// This method never returns true for an instruction that returns true for
+  /// mayHaveSideEffects; however, this method also does some other checks in
+  /// addition. It checks for undefined behavior, like dividing by zero or
+  /// loading from an invalid pointer (but not for undefined results, like a
+  /// shift with a shift amount larger than the width of the result). It checks
+  /// for malloc and alloca because speculatively executing them might cause a
+  /// memory leak. It also returns false for instructions related to control
+  /// flow, specifically terminators and PHI nodes.
+  ///
+  /// This method only looks at the instruction itself and its operands, so if
+  /// this method returns true, it is safe to move the instruction as long as
+  /// the correct dominance relationships for the operands and users hold.
+  /// However, this method can return true for instructions that read memory;
+  /// for such instructions, moving them may change the resulting value.
+  bool isSafeToSpeculativelyExecute(const Value *V,
+                                    const TargetData *TD = 0);
+
 } // end namespace llvm
 
 #endif