Merge commit '279b9184c2ff4fea93b198a3519b8cb3a1d8d195'

Conflicts:
	include/llvm/CodeGen/LexicalScopes.h
	include/llvm/MC/MCAsmInfo.h
	lib/Linker/LinkArchives.cpp
	lib/Linker/LinkItems.cpp
	lib/MC/MCAsmInfo.cpp
	lib/MC/MCDwarf.cpp
	lib/Target/ARM/ARMInstrInfo.td
	lib/Target/ARM/ARMSubtarget.cpp
	lib/Target/ARM/MCTargetDesc/ARMMCTargetDesc.cpp
	lib/Target/Mips/MCTargetDesc/MipsELFObjectWriter.cpp
	lib/Target/Mips/MCTargetDesc/MipsMCTargetDesc.cpp
	lib/Target/Mips/MipsAsmPrinter.cpp
	lib/Target/Mips/MipsDelaySlotFiller.cpp
	lib/Target/Mips/MipsISelDAGToDAG.cpp
	lib/Target/Mips/MipsSubtarget.cpp
	lib/Target/Mips/MipsSubtarget.h
	lib/Target/Mips/MipsTargetObjectFile.cpp
	lib/Target/X86/MCTargetDesc/X86MCAsmInfo.cpp
	lib/Target/X86/X86FastISel.cpp
	lib/Target/X86/X86ISelLowering.cpp
	lib/Target/X86/X86TargetMachine.cpp
	lib/Transforms/CMakeLists.txt
	lib/Transforms/LLVMBuild.txt
	lib/Transforms/Makefile
	test/MC/ARM/arm_instructions.s
	test/MC/X86/AlignedBundling/pad-align-to-bundle-end.s

13 files changed, 523 insertions, 229 deletions

diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h
index 72fc950b60..d703f21c02 100644
--- a/include/llvm/Analysis/AliasAnalysis.h
+++ b/include/llvm/Analysis/AliasAnalysis.h
@@ -593,11 +593,6 @@ 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/CodeMetrics.h b/include/llvm/Analysis/CodeMetrics.h
index 35eabec6ee..086934d0e6 100644
--- a/include/llvm/Analysis/CodeMetrics.h
+++ b/include/llvm/Analysis/CodeMetrics.h
@@ -19,80 +19,75 @@
 #include "llvm/Support/CallSite.h"
 
 namespace llvm {
-  class BasicBlock;
-  class Function;
-  class Instruction;
-  class DataLayout;
-  class Value;
+class BasicBlock;
+class Function;
+class Instruction;
+class DataLayout;
+class TargetTransformInfo;
+class Value;
+
+/// \brief Check whether a call will lower to something small.
+///
+/// This tests checks whether this callsite will lower to something
+/// significantly cheaper than a traditional call, often a single
+/// instruction. Note that if isInstructionFree(CS.getInstruction()) would
+/// return true, so will this function.
+bool callIsSmall(ImmutableCallSite CS);
+
+/// \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;
+
+  /// \brief True if this function calls itself.
+  bool isRecursive;
+
+  /// \brief True if this function cannot be duplicated.
+  ///
+  /// True if this function contains one or more indirect branches, or it contains
+  /// one or more 'noduplicate' instructions.
+  bool notDuplicatable;
+
+  /// \brief True if this function calls alloca (in the C sense).
+  bool usesDynamicAlloca;
+
+  /// \brief Number of instructions in the analyzed blocks.
+  unsigned NumInsts;
 
-  /// \brief Check whether an instruction is likely to be "free" when lowered.
-  bool isInstructionFree(const Instruction *I, const DataLayout *TD = 0);
+  /// \brief Number of analyzed blocks.
+  unsigned NumBlocks;
 
-  /// \brief Check whether a call will lower to something small.
+  /// \brief Keeps track of basic block code size estimates.
+  DenseMap<const BasicBlock *, unsigned> NumBBInsts;
+
+  /// \brief Keep track of the number of calls to 'big' functions.
+  unsigned NumCalls;
+
+  /// \brief The number of calls to internal functions with a single caller.
   ///
-  /// This tests checks whether this callsite will lower to something
-  /// significantly cheaper than a traditional call, often a single
-  /// instruction. Note that if isInstructionFree(CS.getInstruction()) would
-  /// return true, so will this function.
-  bool callIsSmall(ImmutableCallSite CS);
-
-  /// \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;
-
-    /// \brief True if this function calls itself.
-    bool isRecursive;
-
-    /// \brief True if this function cannot be duplicated.
-    ///
-    /// True if this function contains one or more indirect branches, or it contains
-    /// one or more 'noduplicate' instructions.
-    bool notDuplicatable;
-
-    /// \brief True if this function calls alloca (in the C sense).
-    bool usesDynamicAlloca;
-
-    /// \brief Number of instructions in the analyzed blocks.
-    unsigned NumInsts;
-
-    /// \brief Number of analyzed blocks.
-    unsigned NumBlocks;
-
-    /// \brief Keeps track of basic block code size estimates.
-    DenseMap<const BasicBlock *, unsigned> NumBBInsts;
-
-    /// \brief Keep track of the number of calls to 'big' functions.
-    unsigned NumCalls;
-
-    /// \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;
-
-    /// \brief How many instructions produce vector values.
-    ///
-    /// The inliner is more aggressive with inlining vector kernels.
-    unsigned NumVectorInsts;
-
-    /// \brief How many 'ret' instructions the blocks contain.
-    unsigned NumRets;
-
-    CodeMetrics() : exposesReturnsTwice(false), isRecursive(false),
-                    notDuplicatable(false), usesDynamicAlloca(false),
-                    NumInsts(0), NumBlocks(0), NumCalls(0),
-                    NumInlineCandidates(0), NumVectorInsts(0),
-                    NumRets(0) {}
-
-    /// \brief Add information about a block to the current state.
-    void analyzeBasicBlock(const BasicBlock *BB, const DataLayout *TD = 0);
-
-    /// \brief Add information about a function to the current state.
-    void analyzeFunction(Function *F, const DataLayout *TD = 0);
-  };
+  /// These are likely targets for future inlining, likely exposed by
+  /// interleaved devirtualization.
+  unsigned NumInlineCandidates;
+
+  /// \brief How many instructions produce vector values.
+  ///
+  /// The inliner is more aggressive with inlining vector kernels.
+  unsigned NumVectorInsts;
+
+  /// \brief How many 'ret' instructions the blocks contain.
+  unsigned NumRets;
+
+  CodeMetrics()
+      : exposesReturnsTwice(false), isRecursive(false), notDuplicatable(false),
+        usesDynamicAlloca(false), NumInsts(0), NumBlocks(0), NumCalls(0),
+        NumInlineCandidates(0), NumVectorInsts(0), NumRets(0) {}
+
+  /// \brief Add information about a block to the current state.
+  void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI);
+};
+
 }
 
 #endif
diff --git a/include/llvm/Analysis/DependenceAnalysis.h b/include/llvm/Analysis/DependenceAnalysis.h
index f49efd970a..d0ead39694 100644
--- a/include/llvm/Analysis/DependenceAnalysis.h
+++ b/include/llvm/Analysis/DependenceAnalysis.h
@@ -244,8 +244,8 @@ namespace llvm {
   /// DependenceAnalysis - This class is the main dependence-analysis driver.
   ///
   class DependenceAnalysis : public FunctionPass {
-    void operator=(const DependenceAnalysis &);     // do not implement
-    DependenceAnalysis(const DependenceAnalysis &); // do not implement
+    void operator=(const DependenceAnalysis &) LLVM_DELETED_FUNCTION;
+    DependenceAnalysis(const DependenceAnalysis &) LLVM_DELETED_FUNCTION;
   public:
     /// depends - Tests for a dependence between the Src and Dst instructions.
     /// Returns NULL if no dependence; otherwise, returns a Dependence (or a
diff --git a/include/llvm/Analysis/InlineCost.h b/include/llvm/Analysis/InlineCost.h
index 209c3c0667..bc7924e10f 100644
--- a/include/llvm/Analysis/InlineCost.h
+++ b/include/llvm/Analysis/InlineCost.h
@@ -15,120 +15,129 @@
 #define LLVM_ANALYSIS_INLINECOST_H
 
 #include "llvm/Analysis/CodeMetrics.h"
+#include "llvm/Analysis/CallGraphSCCPass.h"
 #include <cassert>
 #include <climits>
 
 namespace llvm {
+class CallSite;
+class DataLayout;
+class Function;
+class TargetTransformInfo;
+
+namespace InlineConstants {
+  // Various magic constants used to adjust heuristics.
+  const int InstrCost = 5;
+  const int IndirectCallThreshold = 100;
+  const int CallPenalty = 25;
+  const int LastCallToStaticBonus = -15000;
+  const int ColdccPenalty = 2000;
+  const int NoreturnPenalty = 10000;
+  /// Do not inline functions which allocate this many bytes on the stack
+  /// when the caller is recursive.
+  const unsigned TotalAllocaSizeRecursiveCaller = 1024;
+}
+
+/// \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 SentinelValues {
+    AlwaysInlineCost = INT_MIN,
+    NeverInlineCost = INT_MAX
+  };
+
+  /// \brief The estimated cost of inlining this callsite.
+  const int Cost;
+
+  /// \brief The adjusted threshold against which this cost was computed.
+  const int Threshold;
+
+  // Trivial constructor, interesting logic in the factory functions below.
+  InlineCost(int Cost, int Threshold) : Cost(Cost), Threshold(Threshold) {}
+
+public:
+  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);
+  }
 
-  class CallSite;
-  class DataLayout;
-  class Function;
-
-  namespace InlineConstants {
-    // Various magic constants used to adjust heuristics.
-    const int InstrCost = 5;
-    const int IndirectCallThreshold = 100;
-    const int CallPenalty = 25;
-    const int LastCallToStaticBonus = -15000;
-    const int ColdccPenalty = 2000;
-    const int NoreturnPenalty = 10000;
-    /// Do not inline functions which allocate this many bytes on the stack
-    /// when the caller is recursive.
-    const unsigned TotalAllocaSizeRecursiveCaller = 1024;
+  /// \brief Test whether the inline cost is low enough for inlining.
+  operator bool() const {
+    return Cost < Threshold;
   }
 
-  /// \brief Represents the cost of inlining a function.
+  bool isAlways() const { return Cost == AlwaysInlineCost; }
+  bool isNever() const { return Cost == NeverInlineCost; }
+  bool isVariable() const { return !isAlways() && !isNever(); }
+
+  /// \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;
+  }
+
+  /// \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(); }
+};
+
+/// \brief Cost analyzer used by inliner.
+class InlineCostAnalysis : public CallGraphSCCPass {
+  const DataLayout *TD;
+  const TargetTransformInfo *TTI;
+
+public:
+  static char ID;
+
+  InlineCostAnalysis();
+  ~InlineCostAnalysis();
+
+  // Pass interface implementation.
+  void getAnalysisUsage(AnalysisUsage &AU) const;
+  bool runOnSCC(CallGraphSCC &SCC);
+
+  /// \brief Get an InlineCost object representing the cost of inlining this
+  /// callsite.
   ///
-  /// 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.
+  /// 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.
   ///
-  /// 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 SentinelValues {
-      AlwaysInlineCost = INT_MIN,
-      NeverInlineCost = INT_MAX
-    };
-
-    /// \brief The estimated cost of inlining this callsite.
-    const int Cost;
-
-    /// \brief The adjusted threshold against which this cost was computed.
-    const int Threshold;
-
-    // Trivial constructor, interesting logic in the factory functions below.
-    InlineCost(int Cost, int Threshold)
-      : Cost(Cost), Threshold(Threshold) {}
-
-  public:
-    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);
-    }
-
-    /// \brief Test whether the inline cost is low enough for inlining.
-    operator bool() const {
-      return Cost < Threshold;
-    }
-
-    bool isAlways() const   { return Cost == AlwaysInlineCost; }
-    bool isNever() const    { return Cost == NeverInlineCost; }
-    bool isVariable() const { return !isAlways() && !isNever(); }
-
-    /// \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;
-    }
-
-    /// \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(); }
-  };
+  /// Also note that calling this function *dynamically* computes the cost of
+  /// inlining the callsite. It is an expensive, heavyweight call.
+  InlineCost getInlineCost(CallSite CS, int Threshold);
+
+  /// \brief Get an InlineCost with the callee explicitly specified.
+  /// This allows 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);
+
+  /// \brief Minimal filter to detect invalid constructs for inlining.
+  bool isInlineViable(Function &Callee);
+};
 
-  /// InlineCostAnalyzer - Cost analyzer used by inliner.
-  class InlineCostAnalyzer {
-    // DataLayout if available, or null.
-    const DataLayout *TD;
-
-  public:
-    InlineCostAnalyzer(): TD(0) {}
-
-    void setDataLayout(const DataLayout *TData) { TD = TData; }
-
-    /// \brief Get an InlineCost object representing the cost of inlining this
-    /// callsite.
-    ///
-    /// 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);
-
-    /// \brief Get an InlineCost with the callee explicitly specified.
-    /// This allows 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);
-
-    /// \brief Minimal filter to detect invalid constructs for inlining.
-    bool isInlineViable(Function &Callee);
-  };
 }
 
 #endif
diff --git a/include/llvm/Analysis/InstructionSimplify.h b/include/llvm/Analysis/InstructionSimplify.h
index b653e799f7..d760a4cba1 100644
--- a/include/llvm/Analysis/InstructionSimplify.h
+++ b/include/llvm/Analysis/InstructionSimplify.h
@@ -14,6 +14,19 @@
 // ("and i32 %x, %x" -> "%x").  If the simplification is also an instruction
 // then it dominates the original instruction.
 //
+// These routines implicitly resolve undef uses. The easiest way to be safe when
+// using these routines to obtain simplified values for existing instructions is
+// to always replace all uses of the instructions with the resulting simplified
+// values. This will prevent other code from seeing the same undef uses and
+// resolving them to different values.
+//
+// These routines are designed to tolerate moderately incomplete IR, such as
+// instructions that are not connected to basic blocks yet. However, they do
+// require that all the IR that they encounter be valid. In particular, they
+// require that all non-constant values be defined in the same function, and the
+// same call context of that function (and not split between caller and callee
+// contexts of a directly recursive call, for example).
+//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_INSTRUCTIONSIMPLIFY_H
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 6cdecf4114..a20e065785 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -32,16 +32,12 @@
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
-#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Pass.h"
-#include "llvm/Support/CFG.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
-#include <map>
 
 namespace llvm {
 
@@ -381,6 +377,20 @@ public:
   /// isSafeToClone - Return true if the loop body is safe to clone in practice.
   bool isSafeToClone() const;
 
+  /// Returns true if the loop is annotated parallel.
+  ///
+  /// A parallel loop can be assumed to not contain any dependencies between
+  /// iterations by the compiler. That is, any loop-carried dependency checking
+  /// can be skipped completely when parallelizing the loop on the target
+  /// machine. Thus, if the parallel loop information originates from the
+  /// programmer, e.g. via the OpenMP parallel for pragma, it is the
+  /// programmer's responsibility to ensure there are no loop-carried
+  /// dependencies. The final execution order of the instructions across
+  /// iterations is not guaranteed, thus, the end result might or might not
+  /// implement actual concurrent execution of instructions across multiple
+  /// iterations.
+  bool isAnnotatedParallel() const;
+
   /// hasDedicatedExits - Return true if no exit block for the loop
   /// has a predecessor that is outside the loop.
   bool hasDedicatedExits() const;
diff --git a/include/llvm/Analysis/LoopInfoImpl.h b/include/llvm/Analysis/LoopInfoImpl.h
index cc7ddc4857..5485f3c0c0 100644
--- a/include/llvm/Analysis/LoopInfoImpl.h
+++ b/include/llvm/Analysis/LoopInfoImpl.h
@@ -16,6 +16,7 @@
 #define LLVM_ANALYSIS_LOOPINFOIMPL_H
 
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/LoopInfo.h"
 
 namespace llvm {
diff --git a/include/llvm/Analysis/LoopIterator.h b/include/llvm/Analysis/LoopIterator.h
index e3ca94bd7e..e3dd96354c 100644
--- a/include/llvm/Analysis/LoopIterator.h
+++ b/include/llvm/Analysis/LoopIterator.h
@@ -24,7 +24,6 @@
 #ifndef LLVM_ANALYSIS_LOOPITERATOR_H
 #define LLVM_ANALYSIS_LOOPITERATOR_H
 
-#include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/Analysis/LoopInfo.h"
 
diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h
index 2a9cd75ee7..f07658fbc6 100644
--- a/include/llvm/Analysis/MemoryBuiltins.h
+++ b/include/llvm/Analysis/MemoryBuiltins.h
@@ -153,14 +153,12 @@ typedef std::pair<APInt, APInt> SizeOffsetType;
 class ObjectSizeOffsetVisitor
   : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
 
-  typedef DenseMap<const Value*, SizeOffsetType> CacheMapTy;
-
   const DataLayout *TD;
   const TargetLibraryInfo *TLI;
   bool RoundToAlign;
   unsigned IntTyBits;
   APInt Zero;
-  CacheMapTy CacheMap;
+  SmallPtrSet<Instruction *, 8> SeenInsts;
 
   APInt align(APInt Size, uint64_t Align);
 
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
index d29d96c0be..b87f886c00 100644
--- a/include/llvm/Analysis/MemoryDependenceAnalysis.h
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -34,14 +34,14 @@ namespace llvm {
   class PredIteratorCache;
   class DominatorTree;
   class PHITransAddr;
-  
+
   /// MemDepResult - A memory dependence query can return one of three different
   /// answers, described below.
   class MemDepResult {
     enum DepType {
       /// Invalid - Clients of MemDep never see this.
       Invalid = 0,
-      
+
       /// Clobber - This is a dependence on the specified instruction which
       /// clobbers the desired value.  The pointer member of the MemDepResult
       /// pair holds the instruction that clobbers the memory.  For example,
@@ -72,7 +72,7 @@ namespace llvm {
       ///      and no intervening clobbers.  No validation is done that the
       ///      operands to the calls are the same.
       Def,
-      
+
       /// Other - This marker indicates that the query has no known dependency
       /// in the specified block.  More detailed state info is encoded in the
       /// upper part of the pair (i.e. the Instruction*)
@@ -99,7 +99,7 @@ namespace llvm {
     explicit MemDepResult(PairTy V) : Value(V) {}
   public:
     MemDepResult() : Value(0, Invalid) {}
-    
+
     /// get methods: These are static ctor methods for creating various
     /// MemDepResult kinds.
     static MemDepResult getDef(Instruction *Inst) {
@@ -130,7 +130,7 @@ namespace llvm {
     /// isDef - Return true if this MemDepResult represents a query that is
     /// an instruction definition dependency.
     bool isDef() const { return Value.getInt() == Def; }
-    
+
     /// isNonLocal - Return true if this MemDepResult represents a query that
     /// is transparent to the start of the block, but where a non-local hasn't
     /// been done.
@@ -145,7 +145,7 @@ namespace llvm {
       return Value.getInt() == Other
         && Value.getPointer() == reinterpret_cast<Instruction*>(NonFuncLocal);
     }
-    
+
     /// isUnknown - Return true if this MemDepResult represents a query which
     /// cannot and/or will not be computed.
     bool isUnknown() const {
@@ -159,7 +159,7 @@ namespace llvm {
       if (Value.getInt() == Other) return NULL;
       return Value.getPointer();
     }
-    
+
     bool operator==(const MemDepResult &M) const { return Value == M.Value; }
     bool operator!=(const MemDepResult &M) const { return Value != M.Value; }
     bool operator<(const MemDepResult &M) const { return Value < M.Value; }
@@ -175,11 +175,11 @@ namespace llvm {
     /// In a default-constructed MemDepResult object, the type will be Dirty
     /// and the instruction pointer will be null.
     ///
-         
+
     /// isDirty - Return true if this is a MemDepResult in its dirty/invalid.
     /// state.
     bool isDirty() const { return Value.getInt() == Invalid; }
-    
+
     static MemDepResult getDirty(Instruction *Inst) {
       return MemDepResult(PairTy(Inst, Invalid));
     }
@@ -199,16 +199,16 @@ namespace llvm {
 
     // BB is the sort key, it can't be changed.
     BasicBlock *getBB() const { return BB; }
-    
+
     void setResult(const MemDepResult &R) { Result = R; }
 
     const MemDepResult &getResult() const { return Result; }
-    
+
     bool operator<(const NonLocalDepEntry &RHS) const {
       return BB < RHS.BB;
     }
   };
-  
+
   /// NonLocalDepResult - This is a result from a NonLocal dependence query.
   /// For each BasicBlock (the BB entry) it keeps a MemDepResult and the
   /// (potentially phi translated) address that was live in the block.
@@ -218,17 +218,17 @@ namespace llvm {
   public:
     NonLocalDepResult(BasicBlock *bb, MemDepResult result, Value *address)
       : Entry(bb, result), Address(address) {}
-    
+
     // BB is the sort key, it can't be changed.
     BasicBlock *getBB() const { return Entry.getBB(); }
-    
+
     void setResult(const MemDepResult &R, Value *Addr) {
       Entry.setResult(R);
       Address = Addr;
     }
-    
+
     const MemDepResult &getResult() const { return Entry.getResult(); }
-    
+
     /// getAddress - Return the address of this pointer in this block.  This can
     /// be different than the address queried for the non-local result because
     /// of phi translation.  This returns null if the address was not available
@@ -238,7 +238,7 @@ namespace llvm {
     /// The address is always null for a non-local 'call' dependence.
     Value *getAddress() const { return Address; }
   };
-  
+
   /// MemoryDependenceAnalysis - This is an analysis that determines, for a
   /// given memory operation, what preceding memory operations it depends on.
   /// It builds on alias analysis information, and tries to provide a lazy,
@@ -297,30 +297,30 @@ namespace llvm {
     CachedNonLocalPointerInfo NonLocalPointerDeps;
 
     // A map from instructions to their non-local pointer dependencies.
-    typedef DenseMap<Instruction*, 
+    typedef DenseMap<Instruction*,
                      SmallPtrSet<ValueIsLoadPair, 4> > ReverseNonLocalPtrDepTy;
     ReverseNonLocalPtrDepTy ReverseNonLocalPtrDeps;
 
-    
+
     /// PerInstNLInfo - This is the instruction we keep for each cached access
     /// that we have for an instruction.  The pointer is an owning pointer and
     /// the bool indicates whether we have any dirty bits in the set.
     typedef std::pair<NonLocalDepInfo, bool> PerInstNLInfo;
-    
+
     // A map from instructions to their non-local dependencies.
     typedef DenseMap<Instruction*, PerInstNLInfo> NonLocalDepMapType;
-      
+
     NonLocalDepMapType NonLocalDeps;
-    
+
     // A reverse mapping from dependencies to the dependees.  This is
     // used when removing instructions to keep the cache coherent.
     typedef DenseMap<Instruction*,
                      SmallPtrSet<Instruction*, 4> > ReverseDepMapType;
     ReverseDepMapType ReverseLocalDeps;
-    
+
     // A reverse mapping from dependencies to the non-local dependees.
     ReverseDepMapType ReverseNonLocalDeps;
-    
+
     /// Current AA implementation, just a cache.
     AliasAnalysis *AA;
     DataLayout *TD;
@@ -333,15 +333,15 @@ namespace llvm {
 
     /// Pass Implementation stuff.  This doesn't do any analysis eagerly.
     bool runOnFunction(Function &);
-    
+
     /// Clean up memory in between runs
     void releaseMemory();
-    
+
     /// getAnalysisUsage - Does not modify anything.  It uses Value Numbering
     /// and Alias Analysis.
     ///
     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
-    
+
     /// getDependency - Return the instruction on which a memory operation
     /// depends.  See the class comment for more details.  It is illegal to call
     /// this on non-memory instructions.
@@ -360,8 +360,8 @@ namespace llvm {
     /// removed.  Clients must copy this data if they want it around longer than
     /// that.
     const NonLocalDepInfo &getNonLocalCallDependency(CallSite QueryCS);
-    
-    
+
+
     /// getNonLocalPointerDependency - Perform a full dependency query for an
     /// access to the specified (non-volatile) memory location, returning the
     /// set of instructions that either define or clobber the value.
@@ -374,7 +374,7 @@ namespace llvm {
     /// removeInstruction - Remove an instruction from the dependence analysis,
     /// updating the dependence of instructions that previously depended on it.
     void removeInstruction(Instruction *InstToRemove);
-    
+
     /// invalidateCachedPointerInfo - This method is used to invalidate cached
     /// information about the specified pointer, because it may be too
     /// conservative in memdep.  This is an optional call that can be used when
@@ -387,7 +387,7 @@ namespace llvm {
     /// This needs to be done when the CFG changes, e.g., due to splitting
     /// critical edges.
     void invalidateCachedPredecessors();
-    
+
     /// getPointerDependencyFrom - Return the instruction on which a memory
     /// location depends.  If isLoad is true, this routine ignores may-aliases
     /// with read-only operations.  If isLoad is false, this routine ignores
@@ -396,11 +396,11 @@ namespace llvm {
     /// Note that this is an uncached query, and thus may be inefficient.
     ///
     MemDepResult getPointerDependencyFrom(const AliasAnalysis::Location &Loc,
-                                          bool isLoad, 
+                                          bool isLoad,
                                           BasicBlock::iterator ScanIt,
                                           BasicBlock *BB);
-    
-    
+
+
     /// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that
     /// looks at a memory location for a load (specified by MemLocBase, Offs,
     /// and Size) and compares it against a load.  If the specified load could
@@ -413,7 +413,7 @@ namespace llvm {
                                                     unsigned MemLocSize,
                                                     const LoadInst *LI,
                                                     const DataLayout &TD);
-    
+
   private:
     MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall,
                                            BasicBlock::iterator ScanIt,
@@ -430,11 +430,11 @@ namespace llvm {
                                          unsigned NumSortedEntries);
 
     void RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P);
-    
+
     /// verifyRemoved - Verify that the specified instruction does not occur
     /// in our internal data structures.
     void verifyRemoved(Instruction *Inst) const;
-    
+
   };
 
 } // End llvm namespace
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 301ac1b660..eac91131ad 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -548,6 +548,151 @@ namespace llvm {
     SCEVTraversal<SV> T(Visitor);
     T.visitAll(Root);
   }
+
+  /// The SCEVRewriter takes a scalar evolution expression and copies all its
+  /// components. The result after a rewrite is an identical SCEV.
+  struct SCEVRewriter
+    : public SCEVVisitor<SCEVRewriter, const SCEV*> {
+  public:
+    SCEVRewriter(ScalarEvolution &S) : SE(S) {}
+
+    virtual ~SCEVRewriter() {}
+
+    virtual const SCEV *visitConstant(const SCEVConstant *Constant) {
+      return Constant;
+    }
+
+    virtual const SCEV *visitTruncateExpr(const SCEVTruncateExpr *Ex