It's not necessary to do rounding for alloca operations when the requested

alignment is equal to the stack alignment.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40004 91177308-0d34-0410-b5e6-96231b3b80d8

26 files changed, 4486 insertions, 0 deletions

diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h
new file mode 100644
index 0000000..1cd6afc
--- /dev/null
+++ b/include/llvm/Analysis/AliasAnalysis.h
@@ -0,0 +1,332 @@
+//===- llvm/Analysis/AliasAnalysis.h - Alias Analysis Interface -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the generic AliasAnalysis interface, which is used as the
+// common interface used by all clients of alias analysis information, and
+// implemented by all alias analysis implementations.  Mod/Ref information is
+// also captured by this interface.
+//
+// Implementations of this interface must implement the various virtual methods,
+// which automatically provides functionality for the entire suite of client
+// APIs.
+//
+// This API represents memory as a (Pointer, Size) pair.  The Pointer component
+// specifies the base memory address of the region, the Size specifies how large
+// of an area is being queried.  If Size is 0, two pointers only alias if they
+// are exactly equal.  If size is greater than zero, but small, the two pointers
+// alias if the areas pointed to overlap.  If the size is very large (ie, ~0U),
+// then the two pointers alias if they may be pointing to components of the same
+// memory object.  Pointers that point to two completely different objects in
+// memory never alias, regardless of the value of the Size component.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ALIAS_ANALYSIS_H
+#define LLVM_ANALYSIS_ALIAS_ANALYSIS_H
+
+#include "llvm/Support/CallSite.h"
+#include "llvm/System/IncludeFile.h"
+#include <vector>
+
+namespace llvm {
+
+class LoadInst;
+class StoreInst;
+class VAArgInst;
+class TargetData;
+class Pass;
+class AnalysisUsage;
+
+class AliasAnalysis {
+protected:
+  const TargetData *TD;
+  AliasAnalysis *AA;       // Previous Alias Analysis to chain to.
+
+  /// InitializeAliasAnalysis - Subclasses must call this method to initialize
+  /// the AliasAnalysis interface before any other methods are called.  This is
+  /// typically called by the run* methods of these subclasses.  This may be
+  /// called multiple times.
+  ///
+  void InitializeAliasAnalysis(Pass *P);
+
+  // getAnalysisUsage - All alias analysis implementations should invoke this
+  // directly (using AliasAnalysis::getAnalysisUsage(AU)) to make sure that
+  // TargetData is required by the pass.
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
+public:
+  static char ID; // Class identification, replacement for typeinfo
+  AliasAnalysis() : TD(0), AA(0) {}
+  virtual ~AliasAnalysis();  // We want to be subclassed
+
+  /// getTargetData - Every alias analysis implementation depends on the size of
+  /// data items in the current Target.  This provides a uniform way to handle
+  /// it.
+  ///
+  const TargetData &getTargetData() const { return *TD; }
+
+  //===--------------------------------------------------------------------===//
+  /// Alias Queries...
+  ///
+
+  /// Alias analysis result - Either we know for sure that it does not alias, we
+  /// know for sure it must alias, or we don't know anything: The two pointers
+  /// _might_ alias.  This enum is designed so you can do things like:
+  ///     if (AA.alias(P1, P2)) { ... }
+  /// to check to see if two pointers might alias.
+  ///
+  enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 };
+
+  /// alias - The main low level interface to the alias analysis implementation.
+  /// Returns a Result indicating whether the two pointers are aliased to each
+  /// other.  This is the interface that must be implemented by specific alias
+  /// analysis implementations.
+  ///
+  virtual AliasResult alias(const Value *V1, unsigned V1Size,
+                            const Value *V2, unsigned V2Size);
+
+  /// getMustAliases - If there are any pointers known that must alias this
+  /// pointer, return them now.  This allows alias-set based alias analyses to
+  /// perform a form a value numbering (which is exposed by load-vn).  If an
+  /// alias analysis supports this, it should ADD any must aliased pointers to
+  /// the specified vector.
+  ///
+  virtual void getMustAliases(Value *P, std::vector<Value*> &RetVals);
+
+  /// pointsToConstantMemory - If the specified pointer is known to point into
+  /// constant global memory, return true.  This allows disambiguation of store
+  /// instructions from constant pointers.
+  ///
+  virtual bool pointsToConstantMemory(const Value *P);
+
+  //===--------------------------------------------------------------------===//
+  /// Simple mod/ref information...
+  ///
+
+  /// ModRefResult - Represent the result of a mod/ref query.  Mod and Ref are
+  /// bits which may be or'd together.
+  ///
+  enum ModRefResult { NoModRef = 0, Ref = 1, Mod = 2, ModRef = 3 };
+
+
+  /// ModRefBehavior - Summary of how a function affects memory in the program.
+  /// Loads from constant globals are not considered memory accesses for this
+  /// interface.  Also, functions may freely modify stack space local to their
+  /// invocation without having to report it through these interfaces.
+  enum ModRefBehavior {
+    // DoesNotAccessMemory - This function does not perform any non-local loads
+    // or stores to memory.
+    //
+    // This property corresponds to the GCC 'const' attribute.
+    DoesNotAccessMemory,
+
+    // AccessesArguments - This function accesses function arguments in
+    // non-volatile and well known ways, but does not access any other memory.
+    //
+    // Clients may call getArgumentAccesses to get specific information about
+    // how pointer arguments are used.
+    AccessesArguments,
+
+    // AccessesArgumentsAndGlobals - This function has accesses function
+    // arguments and global variables in non-volatile and well-known ways, but
+    // does not access any other memory.
+    //
+    // Clients may call getArgumentAccesses to get specific information about
+    // how pointer arguments and globals are used.
+    AccessesArgumentsAndGlobals,
+
+    // OnlyReadsMemory - This function does not perform any non-local stores or
+    // volatile loads, but may read from any memory location.
+    //
+    // This property corresponds to the GCC 'pure' attribute.
+    OnlyReadsMemory,
+
+    // UnknownModRefBehavior - This indicates that the function could not be
+    // classified into one of the behaviors above.
+    UnknownModRefBehavior
+  };
+
+  /// PointerAccessInfo - This struct is used to return results for pointers,
+  /// globals, and the return value of a function.
+  struct PointerAccessInfo {
+    /// V - The value this record corresponds to.  This may be an Argument for
+    /// the function, a GlobalVariable, or null, corresponding to the return
+    /// value for the function.
+    Value *V;
+
+    /// ModRefInfo - Whether the pointer is loaded or stored to/from.
+    ///
+    ModRefResult ModRefInfo;
+
+    /// AccessType - Specific fine-grained access information for the argument.
+    /// If none of these classifications is general enough, the
+    /// getModRefBehavior method should not return AccessesArguments*.  If a
+    /// record is not returned for a particular argument, the argument is never
+    /// dead and never dereferenced.
+    enum AccessType {
+      /// ScalarAccess - The pointer is dereferenced.
+      ///
+      ScalarAccess,
+
+      /// ArrayAccess - The pointer is indexed through as an array of elements.
+      ///
+      ArrayAccess,
+
+      /// ElementAccess ?? P->F only?
+
+      /// CallsThrough - Indirect calls are made through the specified function
+      /// pointer.
+      CallsThrough
+    };
+  };
+
+  /// getModRefBehavior - Return the behavior of the specified function if
+  /// called from the specified call site.  The call site may be null in which
+  /// case the most generic behavior of this function should be returned.
+  virtual ModRefBehavior getModRefBehavior(Function *F, CallSite CS,
+                                     std::vector<PointerAccessInfo> *Info = 0);
+
+  /// doesNotAccessMemory - If the specified function is known to never read or
+  /// write memory, return true.  If the function only reads from known-constant
+  /// memory, it is also legal to return true.  Functions that unwind the stack
+  /// are not legal for this predicate.
+  ///
+  /// Many optimizations (such as CSE and LICM) can be performed on calls to it,
+  /// without worrying about aliasing properties, and many functions have this
+  /// property (e.g. 'sin' and 'cos').
+  ///
+  /// This property corresponds to the GCC 'const' attribute.
+  ///
+  bool doesNotAccessMemory(Function *F) {
+    return getModRefBehavior(F, CallSite()) == DoesNotAccessMemory;
+  }
+
+  /// onlyReadsMemory - If the specified function is known to only read from
+  /// non-volatile memory (or not access memory at all), return true.  Functions
+  /// that unwind the stack are not legal for this predicate.
+  ///
+  /// This property allows many common optimizations to be performed in the
+  /// absence of interfering store instructions, such as CSE of strlen calls.
+  ///
+  /// This property corresponds to the GCC 'pure' attribute.
+  ///
+  bool onlyReadsMemory(Function *F) {
+    /// FIXME: If the analysis returns more precise info, we can reduce it to
+    /// this.
+    ModRefBehavior MRB = getModRefBehavior(F, CallSite());
+    return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory;
+  }
+
+
+  /// getModRefInfo - Return information about whether or not an instruction may
+  /// read or write memory specified by the pointer operand.  An instruction
+  /// that doesn't read or write memory may be trivially LICM'd for example.
+
+  /// getModRefInfo (for call sites) - Return whether information about whether
+  /// a particular call site modifies or reads the memory specified by the
+  /// pointer.
+  ///
+  virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
+
+  /// getModRefInfo - Return information about whether two call sites may refer
+  /// to the same set of memory locations.  This function returns NoModRef if
+  /// the two calls refer to disjoint memory locations, Ref if CS1 reads memory
+  /// written by CS2, Mod if CS1 writes to memory read or written by CS2, or
+  /// ModRef if CS1 might read or write memory accessed by CS2.
+  ///
+  virtual ModRefResult getModRefInfo(CallSite CS1, CallSite CS2);
+
+  /// hasNoModRefInfoForCalls - Return true if the analysis has no mod/ref
+  /// information for pairs of function calls (other than "pure" and "const"
+  /// functions).  This can be used by clients to avoid many pointless queries.
+  /// Remember that if you override this and chain to another analysis, you must
+  /// make sure that it doesn't have mod/ref info either.
+  ///
+  virtual bool hasNoModRefInfoForCalls() const;
+
+  /// Convenience functions...
+  ModRefResult getModRefInfo(LoadInst *L, Value *P, unsigned Size);
+  ModRefResult getModRefInfo(StoreInst *S, Value *P, unsigned Size);
+  ModRefResult getModRefInfo(CallInst *C, Value *P, unsigned Size) {
+    return getModRefInfo(CallSite(C), P, Size);
+  }
+  ModRefResult getModRefInfo(InvokeInst *I, Value *P, unsigned Size) {
+    return getModRefInfo(CallSite(I), P, Size);
+  }
+  ModRefResult getModRefInfo(VAArgInst* I, Value* P, unsigned Size) {
+    return AliasAnalysis::Mod;
+  }
+  ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) {
+    switch (I->getOpcode()) {
+    case Instruction::VAArg:  return getModRefInfo((VAArgInst*)I, P, Size);
+    case Instruction::Load:   return getModRefInfo((LoadInst*)I, P, Size);
+    case Instruction::Store:  return getModRefInfo((StoreInst*)I, P, Size);
+    case Instruction::Call:   return getModRefInfo((CallInst*)I, P, Size);
+    case Instruction::Invoke: return getModRefInfo((InvokeInst*)I, P, Size);
+    default:                  return NoModRef;
+    }
+  }
+
+  //===--------------------------------------------------------------------===//
+  /// Higher level methods for querying mod/ref information.
+  ///
+
+  /// canBasicBlockModify - Return true if it is possible for execution of the
+  /// specified basic block to modify the value pointed to by Ptr.
+  ///
+  bool canBasicBlockModify(const BasicBlock &BB, const Value *P, unsigned Size);
+
+  /// canInstructionRangeModify - Return true if it is possible for the
+  /// execution of the specified instructions to modify the value pointed to by
+  /// Ptr.  The instructions to consider are all of the instructions in the
+  /// range of [I1,I2] INCLUSIVE.  I1 and I2 must be in the same basic block.
+  ///
+  bool canInstructionRangeModify(const Instruction &I1, const Instruction &I2,
+                                 const Value *Ptr, unsigned Size);
+
+  //===--------------------------------------------------------------------===//
+  /// Methods that clients should call when they transform the program to allow
+  /// alias analyses to update their internal data structures.  Note that these
+  /// methods may be called on any instruction, regardless of whether or not
+  /// they have pointer-analysis implications.
+  ///
+
+  /// deleteValue - This method should be called whenever an LLVM Value is
+  /// deleted from the program, for example when an instruction is found to be
+  /// redundant and is eliminated.
+  ///
+  virtual void deleteValue(Value *V);
+
+  /// copyValue - This method should be used whenever a preexisting value in the
+  /// program is copied or cloned, introducing a new value.  Note that analysis
+  /// implementations should tolerate clients that use this method to introduce
+  /// the same value multiple times: if the analysis already knows about a
+  /// value, it should ignore the request.
+  ///
+  virtual void copyValue(Value *From, Value *To);
+
+  /// replaceWithNewValue - This method is the obvious combination of the two
+  /// above, and it provided as a helper to simplify client code.
+  ///
+  void replaceWithNewValue(Value *Old, Value *New) {
+    copyValue(Old, New);
+    deleteValue(Old);
+  }
+};
+
+} // End llvm namespace
+
+// Because of the way .a files work, we must force the BasicAA implementation to
+// be pulled in if the AliasAnalysis header is included.  Otherwise we run
+// the risk of AliasAnalysis being used, but the default implementation not
+// being linked into the tool that uses it.
+FORCE_DEFINING_FILE_TO_BE_LINKED(AliasAnalysis)
+FORCE_DEFINING_FILE_TO_BE_LINKED(BasicAliasAnalysis)
+
+#endif
diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h
new file mode 100644
index 0000000..cd6450f
--- /dev/null
+++ b/include/llvm/Analysis/AliasSetTracker.h
@@ -0,0 +1,392 @@
+//===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines two classes: AliasSetTracker and AliasSet.  These interface
+// are used to classify a collection of pointer references into a maximal number
+// of disjoint sets.  Each AliasSet object constructed by the AliasSetTracker
+// object refers to memory disjoint from the other sets.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
+#define LLVM_ANALYSIS_ALIASSETTRACKER_H
+
+#include "llvm/Support/CallSite.h"
+#include "llvm/Support/Streams.h"
+#include "llvm/ADT/iterator"
+#include "llvm/ADT/hash_map"
+#include "llvm/ADT/ilist"
+
+namespace llvm {
+
+class AliasAnalysis;
+class LoadInst;
+class StoreInst;
+class FreeInst;
+class AliasSetTracker;
+class AliasSet;
+
+class AliasSet {
+  friend class AliasSetTracker;
+
+  class PointerRec;
+  typedef std::pair<Value* const, PointerRec> HashNodePair;
+
+  class PointerRec {
+    HashNodePair **PrevInList, *NextInList;
+    AliasSet *AS;
+    unsigned Size;
+  public:
+    PointerRec() : PrevInList(0), NextInList(0), AS(0), Size(0) {}
+
+    HashNodePair *getNext() const { return NextInList; }
+    bool hasAliasSet() const { return AS != 0; }
+
+    HashNodePair** setPrevInList(HashNodePair **PIL) {
+      PrevInList = PIL;
+      return &NextInList;
+    }
+
+    void updateSize(unsigned NewSize) {
+      if (NewSize > Size) Size = NewSize;
+    }
+
+    unsigned getSize() const { return Size; }
+
+    AliasSet *getAliasSet(AliasSetTracker &AST) {
+      assert(AS && "No AliasSet yet!");
+      if (AS->Forward) {
+        AliasSet *OldAS = AS;
+        AS = OldAS->getForwardedTarget(AST);
+        AS->addRef();
+        OldAS->dropRef(AST);
+      }
+      return AS;
+    }
+
+    void setAliasSet(AliasSet *as) {
+      assert(AS == 0 && "Already have an alias set!");
+      AS = as;
+    }
+
+    void removeFromList() {
+      if (NextInList) NextInList->second.PrevInList = PrevInList;
+      *PrevInList = NextInList;
+      if (AS->PtrListEnd == &NextInList) {
+        AS->PtrListEnd = PrevInList;
+        assert(*AS->PtrListEnd == 0 && "List not terminated right!");
+      }
+    }
+  };
+
+  HashNodePair *PtrList, **PtrListEnd;  // Doubly linked list of nodes
+  AliasSet *Forward;             // Forwarding pointer
+  AliasSet *Next, *Prev;         // Doubly linked list of AliasSets
+
+  std::vector<CallSite> CallSites; // All calls & invokes in this node
+
+  // RefCount - Number of nodes pointing to this AliasSet plus the number of
+  // AliasSets forwarding to it.
+  unsigned RefCount : 28;
+
+  /// AccessType - Keep track of whether this alias set merely refers to the
+  /// locations of memory, whether it modifies the memory, or whether it does
+  /// both.  The lattice goes from "NoModRef" to either Refs or Mods, then to
+  /// ModRef as necessary.
+  ///
+  enum AccessType {
+    NoModRef = 0, Refs = 1,         // Ref = bit 1
+    Mods     = 2, ModRef = 3        // Mod = bit 2
+  };
+  unsigned AccessTy : 2;
+
+  /// AliasType - Keep track the relationships between the pointers in the set.
+  /// Lattice goes from MustAlias to MayAlias.
+  ///
+  enum AliasType {
+    MustAlias = 0, MayAlias = 1
+  };
+  unsigned AliasTy : 1;
+
+  // Volatile - True if this alias set contains volatile loads or stores.
+  bool Volatile : 1;
+
+  friend struct ilist_traits<AliasSet>;
+  AliasSet *getPrev() const { return Prev; }
+  AliasSet *getNext() const { return Next; }
+  void setPrev(AliasSet *P) { Prev = P; }
+  void setNext(AliasSet *N) { Next = N; }
+
+  void addRef() { ++RefCount; }
+  void dropRef(AliasSetTracker &AST) {
+    assert(RefCount >= 1 && "Invalid reference count detected!");
+    if (--RefCount == 0)
+      removeFromTracker(AST);
+  }
+
+public:
+  /// Accessors...
+  bool isRef() const { return AccessTy & Refs; }
+  bool isMod() const { return AccessTy & Mods; }
+  bool isMustAlias() const { return AliasTy == MustAlias; }
+  bool isMayAlias()  const { return AliasTy == MayAlias; }
+
+  // isVolatile - Return true if this alias set contains volatile loads or
+  // stores.
+  bool isVolatile() const { return Volatile; }
+
+  /// isForwardingAliasSet - Return true if this alias set should be ignored as
+  /// part of the AliasSetTracker object.
+  bool isForwardingAliasSet() const { return Forward; }
+
+  /// mergeSetIn - Merge the specified alias set into this alias set...
+  ///
+  void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
+
+  // Alias Set iteration - Allow access to all of the pointer which are part of
+  // this alias set...
+  class iterator;
+  iterator begin() const { return iterator(PtrList); }
+  iterator end()   const { return iterator(); }
+  bool empty() const { return PtrList == 0; }
+
+  void print(std::ostream &OS) const;
+  void print(std::ostream *OS) const { if (OS) print(*OS); }
+  void dump() const;
+
+  /// Define an iterator for alias sets... this is just a forward iterator.
+  class iterator : public forward_iterator<HashNodePair, ptrdiff_t> {
+    HashNodePair *CurNode;
+  public:
+    iterator(HashNodePair *CN = 0) : CurNode(CN) {}
+
+    bool operator==(const iterator& x) const {
+      return CurNode == x.CurNode;
+    }
+    bool operator!=(const iterator& x) const { return !operator==(x); }
+
+    const iterator &operator=(const iterator &I) {
+      CurNode = I.CurNode;
+      return *this;
+    }
+
+    value_type &operator*() const {
+      assert(CurNode && "Dereferencing AliasSet.end()!");
+      return *CurNode;
+    }
+    value_type *operator->() const { return &operator*(); }
+
+    Value *getPointer() const { return CurNode->first; }
+    unsigned getSize() const { return CurNode->second.getSize(); }
+
+    iterator& operator++() {                // Preincrement
+      assert(CurNode && "Advancing past AliasSet.end()!");
+      CurNode = CurNode->second.getNext();
+      return *this;
+    }
+    iterator operator++(int) { // Postincrement
+      iterator tmp = *this; ++*this; return tmp;
+    }
+  };
+
+private:
+  // Can only be created by AliasSetTracker
+  AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0),
+               AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) {
+  }
+
+  AliasSet(const AliasSet &AS) {
+    assert(0 && "Copy ctor called!?!?!");
+    abort();
+  }
+
+  HashNodePair *getSomePointer() const {
+    return PtrList;
+  }
+
+  /// getForwardedTarget - Return the real alias set this represents.  If this
+  /// has been merged with another set and is forwarding, return the ultimate
+  /// destination set.  This also implements the union-find collapsing as well.
+  AliasSet *getForwardedTarget(AliasSetTracker &AST) {
+    if (!Forward) return this;
+
+    AliasSet *Dest = Forward->getForwardedTarget(AST);
+    if (Dest != Forward) {
+      Dest->addRef();
+      Forward->dropRef(AST);
+      Forward = Dest;
+    }
+    return Dest;
+  }
+
+  void removeFromTracker(AliasSetTracker &AST);
+
+  void addPointer(AliasSetTracker &AST, HashNodePair &Entry, unsigned Size,
+                  bool KnownMustAlias = false);
+  void addCallSite(CallSite CS, AliasAnalysis &AA);
+  void removeCallSite(CallSite CS) {
+    for (unsigned i = 0, e = CallSites.size(); i != e; ++i)
+      if (CallSites[i].getInstruction() == CS.getInstruction()) {
+        CallSites[i] = CallSites.back();
+        CallSites.pop_back();
+      }
+  }
+  void setVolatile() { Volatile = true; }
+
+  /// aliasesPointer - Return true if the specified pointer "may" (or must)
+  /// alias one of the members in the set.
+  ///
+  bool aliasesPointer(const Value *Ptr, unsigned Size, AliasAnalysis &AA) const;
+  bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const;
+};
+
+inline std::ostream& operator<<(std::ostream &OS, const AliasSet &AS) {
+  AS.print(OS);
+  return OS;
+}
+
+
+class AliasSetTracker {
+  AliasAnalysis &AA;
+  ilist<AliasSet> AliasSets;
+
+  // Map from pointers to their node
+  hash_map<Value*, AliasSet::PointerRec> PointerMap;
+public:
+  /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use
+  /// the specified alias analysis object to disambiguate load and store
+  /// addresses.
+  AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
+
+  /// add methods - These methods are used to add different types of
+  /// instructions to the alias sets.  Adding a new instruction can result in
+  /// one of three actions happening:
+  ///
+  ///   1. If the instruction doesn't alias any other sets, create a new set.
+  ///   2. If the instruction aliases exactly one set, add it to the set
+  ///   3. If the instruction aliases multiple sets, merge the sets, and add
+  ///      the instruction to the result.
+  ///
+  /// These methods return true if inserting the instruction resulted in the
+  /// addition of a new alias set (i.e., the pointer did not alias anything).
+  ///
+  bool add(Value *Ptr, unsigned Size);  // Add a location
+  bool add(LoadInst *LI);
+  bool add(StoreInst *SI);
+  bool add(FreeInst *FI);
+  bool add(CallSite CS);          // Call/Invoke instructions
+  bool add(CallInst *CI)   { return add(CallSite(CI)); }
+  bool add(InvokeInst *II) { return add(CallSite(II)); }
+  bool add(Instruction *I);       // Dispatch to one of the other add methods...
+  void add(BasicBlock &BB);       // Add all instructions in basic block
+  void add(const AliasSetTracker &AST); // Add alias relations from another AST
+
+  /// remove methods - These methods are used to remove all entries that might
+  /// be aliased by the specified instruction.  These methods return true if any
+  /// alias sets were eliminated.
+  bool remove(Value *Ptr, unsigned Size);  // Remove a location
+  bool remove(LoadInst *LI);
+  bool remove(StoreInst *SI);
+  bool remove(FreeInst *FI);
+  bool remove(CallSite CS);
+  bool remove(CallInst *CI)   { return remove(CallSite(CI)); }
+  bool remove(InvokeInst *II) { return remove(CallSite(II)); }
+  bool remove(Instruction *I);
+  void remove(AliasSet &AS);
+  
+  void clear() {
+    PointerMap.clear();
+    AliasSets.clear();
+  }
+
+  /// getAliasSets - Return the alias sets that are active.
+  ///
+  const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
+
+  /// getAliasSetForPointer - Return the alias set that the specified pointer
+  /// lives in.  If the New argument is non-null, this method sets the value to
+  /// true if a new alias set is created to contain the pointer (because the
+  /// pointer didn't alias anything).
+  AliasSet &getAliasSetForPointer(Value *P, unsigned Size, bool *New = 0);
+
+  /// getAliasSetForPointerIfExists - Return the alias set containing the
+  /// location specified if one exists, otherwise return null.
+  AliasSet *getAliasSetForPointerIfExists(Value *P, unsigned Size) {
+    return findAliasSetForPointer(P, Size);
+  }
+
+  /// containsPointer - Return true if the specified location is represented by
+  /// this alias set, false otherwise.  This does not modify the AST object or
+  /// alias sets.
+  bool containsPointer(Value *P, unsigned Size) const;
+
+  /// getAliasAnalysis - Return the underlying alias analysis object used by
+  /// this tracker.
+  AliasAnalysis &getAliasAnalysis() const { return AA; }
+
+  /// deleteValue method - This method is used to remove a pointer value from
+  /// the AliasSetTracker entirely.  It should be used when an instruction is
+  /// deleted from the program to update the AST.  If you don't use this, you
+  /// would have dangling pointers to deleted instructions.
+  ///
+  void deleteValue(Value *PtrVal);
+
+  /// copyValue - This method should be used whenever a preexisting value in the
+  /// program is copied or cloned, introducing a new value.  Note that it is ok
+  /// for clients that use this method to introduce the same value multiple
+  /// times: if the tracker already knows about a value, it will ignore the
+  /// request.
+  ///
+  void copyValue(Value *From, Value *To);
+
+
+  typedef ilist<AliasSet>::iterator iterator;
+  typedef ilist<AliasSet>::const_iterator const_iterator;
+
+  const_iterator begin() const { return AliasSets.begin(); }
+  const_iterator end()   const { return AliasSets.end(); }
+
+  iterator begin() { return AliasSets.begin(); }
+  iterator end()   { return AliasSets.end(); }
+
+  void print(std::ostream &OS) const;
+  void print(std::ostream *OS) const { if (OS) print(*OS); }
+  void dump() const;
+
+private:
+  friend class AliasSet;
+  void removeAliasSet(AliasSet *AS);
+
+  AliasSet::HashNodePair &getEntryFor(Value *V) {
+    // Standard operator[], except that it returns the whole pair, not just
+    // ->second.
+    return *PointerMap.insert(AliasSet::HashNodePair(V,
+                                            AliasSet::PointerRec())).first;
+  }
+
+  AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E,
+                       bool &NewSet) {
+    NewSet = false;
+    AliasSet &AS = getAliasSetForPointer(P, Size, &NewSet);
+    AS.AccessTy |= E;
+    return AS;
+  }
+  AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size);
+
+  AliasSet *findAliasSetForCallSite(CallSite CS);
+};
+
+inline std::ostream& operator<<(std::ostream &OS, const AliasSetTracker &AST) {
+  AST.print(OS);
+  return OS;
+}
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/CFGPrinter.h b/include/llvm/Analysis/CFGPrinter.h
new file mode 100644
index 0000000..3567db1
--- /dev/null
+++ b/include/llvm/Analysis/CFGPrinter.h
@@ -0,0 +1,24 @@
+//===-- CFGPrinter.h - CFG printer external interface ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines external functions that can be called to explicitly
+// instantiate the CFG printer.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CFGPRINTER_H
+#define LLVM_ANALYSIS_CFGPRINTER_H
+
+namespace llvm {
+  class FunctionPass;
+  FunctionPass *createCFGPrinterPass ();
+  FunctionPass *createCFGOnlyPrinterPass ();
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h
new file mode 100644
index 0000000..4f4ce0e
--- /dev/null
+++ b/include/llvm/Analysis/CallGraph.h
@@ -0,0 +1,315 @@
+//===- CallGraph.h - Build a Module's call graph ----------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This interface is used to build and manipulate a call graph, which is a very
+// useful tool for interprocedural optimization.
+//
+// Every function in a module is represented as a node in the call graph.  The
+// callgraph node keeps track of which functions the are called by the function
+// corresponding to the node.
+//
+// A call graph may contain nodes where the function that they correspond to is
+// null.  These 'external' nodes are used to represent control flow that is not
+// represented (or analyzable) in the module.  In particular, this analysis
+// builds one external node such that:
+//   1. All functions in the module without internal linkage will have edges
+//      from this external node, indicating that they could be called by
+//      functions outside of the module.
+//   2. All functions whose address is used for something more than a direct
+//      call, for example being stored into a memory location will also have an
+//      edge from this external node.  Since they may be called by an unknown
+//      caller later, they must be tracked as such.
+//
+// There is a second external node added for calls that leave this module.
+// Functions have a call edge to the external node iff:
+//   1. The function is external, reflecting the fact that they could call
+//      anything without internal linkage or that has its address taken.
+//   2. The function contains an indirect function call.
+//
+// As an extension in the future, there may be multiple nodes with a null
+// function.  These will be used when we can prove (through pointer analysis)
+// that an indirect call site can call only a specific set of functions.
+//
+// Because of these properties, the CallGraph captures a conservative superset
+// of all of the caller-callee relationships, which is useful for
+// transformations.
+//
+// The CallGraph class also attempts to figure out what the root of the
+// CallGraph is, which it currently does by looking for a function named 'main'.
+// If no function named 'main' is found, the external node is used as the entry
+// node, reflecting the fact that any function without internal linkage could
+// be called into (which is common for libraries).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CALLGRAPH_H
+#define LLVM_ANALYSIS_CALLGRAPH_H
+
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CallSite.h"
+
+namespace llvm {
+
+class Function;
+class Module;
+class CallGraphNode;
+
+//===----------------------------------------------------------------------===//
+// CallGraph class definition
+//
+class CallGraph {
+protected:
+  Module *Mod;              // The module this call graph represents
+
+  typedef std::map<const Function *, CallGraphNode *> FunctionMapTy;
+  FunctionMapTy FunctionMap;    // Map from a function to its node
+
+public:
+  static char ID; // Class identification, replacement for typeinfo
+  //===---------------------------------------------------------------------
+  // Accessors...
+  //
+  typedef FunctionMapTy::iterator iterator;
+  typedef FunctionMapTy::const_iterator const_iterator;
+
+  /// getModule - Return the module the call graph corresponds to.
+  ///
+  Module &getModule() const { return *Mod; }
+
+  inline       iterator begin()       { return FunctionMap.begin(); }
+  inline       iterator end()         { return FunctionMap.end();   }
+  inline const_iterator begin() const { return FunctionMap.begin(); }
+  inline const_iterator end()   const { return FunctionMap.end();   }
+
+  // Subscripting operators, return the call graph node for the provided
+  // function
+  inline const CallGraphNode *operator[](const Function *F) const {
+    const_iterator I = FunctionMap.find(F);
+    assert(I != FunctionMap.end() && "Function not in callgraph!");
+    return I->second;
+  }
+  inline CallGraphNode *operator[](const Function *F) {
+    const_iterator I = FunctionMap.find(F);
+    assert(I != FunctionMap.end() && "Function not in callgraph!");
+    return I->second;
+  }
+
+  //Returns the CallGraphNode which is used to represent undetermined calls 
+  // into the callgraph.  Override this if you want behavioural inheritance.
+  virtual CallGraphNode* getExternalCallingNode() const { return 0; }
+  
+  //Return the root/main method in the module, or some other root node, such
+  // as the externalcallingnode.  Overload these if you behavioural 
+  // inheritance.
+  virtual CallGraphNode* getRoot() { return 0; }
+  virtual const CallGraphNode* getRoot() const { return 0; }
+  
+  //===---------------------------------------------------------------------
+  // Functions to keep a call graph up to date with a function that has been
+  // modified.
+  //
+
+  /// removeFunctionFromModule - Unlink the function from this module, returning
+  /// it.  Because this removes the function from the module, the call graph
+  /// node is destroyed.  This is only valid if the function does not call any
+  /// other functions (ie, there are no edges in it's CGN).  The easiest way to
+  /// do this is to dropAllReferences before calling this.
+  ///
+  Function *removeFunctionFromModule(CallGraphNode *CGN);
+  Function *removeFunctionFromModule(Function *F) {
+    return removeFunctionFromModule((*this)[F]);
+  }
+
+  /// changeFunction - This method changes the function associated with this
+  /// CallGraphNode, for use by transformations that need to change the
+  /// prototype of a Function (thus they must create a new Function and move the
+  /// old code over).
+  void changeFunction(Function *OldF, Function *NewF);
+
+  /// getOrInsertFunction - This method is identical to calling operator[], but
+  /// it will insert a new CallGraphNode for the specified function if one does
+  /// not already exist.
+  CallGraphNode *getOrInsertFunction(const Function *F);
+  
+  //===---------------------------------------------------------------------
+  // Pass infrastructure interface glue code...
+  //
+protected:
+  CallGraph() {}
+  
+public:
+  virtual ~CallGraph() { destroy(); }
+
+  /// initialize - Call this method before calling other methods, 
+  /// re/initializes the state of the CallGraph.
+  ///
+  void initialize(Module &M);
+
+  virtual void print(std::ostream &o, const Module *M) const;
+  void print(std::ostream *o, const Module *M) const { if (o) print(*o, M); }
+  void dump() const;
+  
+  // stub - dummy function, just ignore it
+  static int stub;
+protected:
+
+  // destroy - Release memory for the call graph
+  virtual void destroy();
+};
+
+//===----------------------------------------------------------------------===//
+// CallGraphNode class definition
+//
+class CallGraphNode {
+  Function *F;
+  typedef std::pair<CallSite,CallGraphNode*> CallRecord;
+  std::vector<CallRecord> CalledFunctions;
+
+  CallGraphNode(const CallGraphNode &);           // Do not implement
+public:
+  //===---------------------------------------------------------------------
+  // Accessor methods...
+  //
+
+  typedef std::vector<CallRecord>::iterator iterator;
+  typedef std::vector<CallRecord>::const_iterator const_iterator;
+
+  // getFunction - Return the function that this call graph node represents...
+  Function *getFunction() const { return F; }
+
+  inline iterator begin() { return CalledFunctions.begin(); }
+  inline iterator end()   { return CalledFunctions.end();   }
+  inline const_iterator begin() const { return CalledFunctions.begin(); }
+  inline const_iterator end()   const { return CalledFunctions.end();   }
+  inline unsigned size() const { return CalledFunctions.size(); }
+
+  // Subscripting operator - Return the i'th called function...
+  //
+  CallGraphNode *operator[](unsigned i) const {
+    return CalledFunctions[i].second;
+  }
+
+  /// dump - Print out this call graph node.
+  ///
+  void dump() const;
+  void print(std::ostream &OS) const;
+  void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+  //===---------------------------------------------------------------------
+  // Methods to keep a call graph up to date with a function that has been
+  // modified
+  //
+
+  /// removeAllCalledFunctions - As the name implies, this removes all edges
+  /// from this CallGraphNode to any functions it calls.
+  void removeAllCalledFunctions() {
+    CalledFunctions.clear();
+  }
+
+  /// addCalledFunction add a function to the list of functions called by this
+  /// one.
+  void addCalledFunction(CallSite CS, CallGraphNode *M) {
+    CalledFunctions.push_back(std::make_pair(CS, M));
+  }
+
+  /// removeCallEdgeTo - This method removes a *single* edge to the specified
+  /// callee function.  Note that this method takes linear time, so it should be
+  /// used sparingly.
+  void removeCallEdgeTo(CallGraphNode *Callee);
+
+  /// removeAnyCallEdgeTo - This method removes any call edges from this node to
+  /// the specified callee function.  This takes more time to execute than
+  /// removeCallEdgeTo, so it should not be used unless necessary.
+  void removeAnyCallEdgeTo(CallGraphNode *Callee);
+
+  friend class CallGraph;
+
+  // CallGraphNode ctor - Create a node for the specified function.
+  inline CallGraphNode(Function *f) : F(f) {}
+};
+
+//===----------------------------------------------------------------------===//
+// GraphTraits specializations for call graphs so that they can be treated as
+// graphs by the generic graph algorithms.
+//
+
+// Provide graph traits for tranversing call graphs using standard graph
+// traversals.
+template <> struct GraphTraits<CallGraphNode*> {
+  typedef CallGraphNode NodeType;
+
+  typedef std::pair<CallSite, CallGraphNode*> CGNPairTy;
+  typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode*> CGNDerefFun;
+  
+  static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; }
+  
+  typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
+  
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
+  }
+  static inline ChildIteratorType child_end  (NodeType *N) {
+    return map_iterator(N->end(), CGNDerefFun(CGNDeref));
+  }
+  
+  static CallGraphNode *CGNDeref(CGNPairTy P) {
+    return P.second;
+  }
+  
+};
+
+template <> struct GraphTraits<const CallGraphNode*> {
+  typedef const CallGraphNode NodeType;
+  typedef NodeType::const_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; }
+  static inline ChildIteratorType child_begin(NodeType *N) { return N->begin();}
+  static inline ChildIteratorType child_end  (NodeType *N) { return N->end(); }
+};
+
+template<> struct GraphTraits<CallGraph*> : public GraphTraits<CallGraphNode*> {
+  static NodeType *getEntryNode(CallGraph *CGN) {
+    return CGN->getExternalCallingNode();  // Start at the external node!
+  }
+  typedef std::pair<const Function*, CallGraphNode*> PairTy;
+  typedef std::pointer_to_unary_function<PairTy, CallGraphNode&> DerefFun;
+
+  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+  typedef mapped_iterator<CallGraph::iterator, DerefFun> nodes_iterator;
+  static nodes_iterator nodes_begin(CallGraph *CG) {
+    return map_iterator(CG->begin(), DerefFun(CGdereference));
+  }
+  static nodes_iterator nodes_end  (CallGraph *CG) {
+    return map_iterator(CG->end(), DerefFun(CGdereference));
+  }
+
+  static CallGraphNode &CGdereference(PairTy P) {
+    return *P.second;
+  }
+};
+
+template<> struct GraphTraits<const CallGraph*> :
+  public GraphTraits<const CallGraphNode*> {
+  static NodeType *getEntryNode(const CallGraph *CGN) {
+    return CGN->getExternalCallingNode();
+  }
+  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+  typedef CallGraph::const_iterator nodes_iterator;
+  static nodes_iterator nodes_begin(const CallGraph *CG) { return CG->begin(); }
+  static nodes_iterator nodes_end  (const CallGraph *CG) { return CG->end(); }
+};
+
+} // End llvm namespace
+
+// Make sure that any clients of this file link in CallGraph.cpp
+FORCE_DEFINING_FILE_TO_BE_LINKED(CallGraph)
+
+#endif
diff --git a/include/llvm/Analysis/ConstantFolding.h b/include/llvm/Analysis/ConstantFolding.h
new file mode 100644
index 0000000..9c19f11
--- /dev/null
+++ b/include/llvm/Analysis/ConstantFolding.h
@@ -0,0 +1,61 @@
+//===-- ConstantFolding.h - Analyze constant folding possibilities --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions determines the possibility of performing constant
+// folding.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CONSTANTFOLDING_H
+#define LLVM_ANALYSIS_CONSTANTFOLDING_H
+
+namespace llvm {
+  class Constant;
+  class ConstantExpr;
+  class Instruction;
+  class TargetData;
+  class Function;
+
+/// ConstantFoldInstruction - Attempt to constant fold the specified
+/// instruction.  If successful, the constant result is returned, if not, null
+/// is returned.  Note that 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);
+
+/// ConstantFoldInstOperands - Attempt to constant fold an instruction with the
+/// specified operands.  If successful, the constant result is returned, if not,
+/// null is returned.  Note that this function can fail when attempting to 
+/// fold instructions like loads and stores, which have no constant expression 
+/// form.
+///
+Constant *ConstantFoldInstOperands(
+  const Instruction *I, ///< The model instruction
+  Constant** Ops,       ///< The array of constant operands to use.
+  unsigned NumOps,      ///< The number of operands provided.
+  const TargetData *TD = 0 ///< Optional target information.
+);
+
+
+/// ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a
+/// 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);
+  
+/// canConstantFoldCallTo - Return true if its even possible to fold a call to
+/// the specified function.
+bool canConstantFoldCallTo(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, Constant** Operands, unsigned NumOperands);
+}
+
+#endif
diff --git a/include/llvm/Analysis/ConstantsScanner.h b/include/llvm/Analysis/ConstantsScanner.h
new file mode 100644
index 0000000..9ea9ed6
--- /dev/null
+++ b/include/llvm/Analysis/ConstantsScanner.h
@@ -0,0 +1,94 @@
+//==- llvm/Analysis/ConstantsScanner.h - Iterate over constants -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This class implements an iterator to walk through the constants referenced by
+// a method.  This is used by the Bitcode & Assembly writers to build constant
+// pools.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CONSTANTSSCANNER_H
+#define LLVM_ANALYSIS_CONSTANTSSCANNER_H
+
+#include "llvm/Support/InstIterator.h"
+#include "llvm/Instruction.h"
+#include "llvm/ADT/iterator"
+
+namespace llvm {
+
+class Constant;
+
+class constant_iterator : public forward_iterator<const Constant, ptrdiff_t> {
+  const_inst_iterator InstI;                // Method instruction iterator
+  unsigned OpIdx;                           // Operand index
+
+  typedef constant_iterator _Self;
+
+  inline bool isAtConstant() const {
+    assert(!InstI.atEnd() && OpIdx < InstI->getNumOperands() &&
+           "isAtConstant called with invalid arguments!");
+    return isa<Constant>(InstI->getOperand(OpIdx));
+  }
+
+public:
+  inline constant_iterator(const Function *F) : InstI(inst_begin(F)), OpIdx(0) {
+    // Advance to first constant... if we are not already at constant or end
+    if (InstI != inst_end(F) &&                            // InstI is valid?
+        (InstI->getNumOperands() == 0 || !isAtConstant())) // Not at constant?
+      operator++();
+  }
+
+  inline constant_iterator(const Function *F, bool)   // end ctor
+    : InstI(inst_end(F)), OpIdx(0) {
+  }
+
+  inline bool operator==(const _Self& x) const { return OpIdx == x.OpIdx &&
+                                                        InstI == x.InstI; }
+  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+
+  inline pointer operator*() const {
+    assert(isAtConstant() && "Dereferenced an iterator at the end!");
+    return cast<Constant>(InstI->getOperand(OpIdx));
+  }
+  inline pointer operator->() const { return operator*(); }
+
+  inline _Self& operator++() {   // Preincrement implementation
+    ++OpIdx;
+    do {
+      unsigned NumOperands = InstI->getNumOperands();
+      while (OpIdx < NumOperands && !isAtConstant()) {
+        ++OpIdx;
+      }
+
+      if (OpIdx < NumOperands) return *this;  // Found a constant!
+      ++InstI;
+      OpIdx = 0;
+    } while (!InstI.atEnd());
+
+    return *this;  // At the end of the method
+  }
+
+  inline _Self operator++(int) { // Postincrement
+    _Self tmp = *this; ++*this; return tmp;
+  }
+
+  inline bool atEnd() const { return InstI.atEnd(); }
+};
+
+inline constant_iterator constant_begin(const Function *F) {
+  return constant_iterator(F);
+}
+
+inline constant_iterator constant_end(const Function *F) {
+  return constant_iterator(F, true);
+}
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
new file mode 100644
index 0000000..f0b4672
--- /dev/null
+++ b/include/llvm/Analysis/Dominators.h
@@ -0,0 +1,431 @@
+//===- llvm/Analysis/Dominators.h - Dominator Info Calculation --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the following classes:
+//  1. DominatorTree: Represent dominators as an explicit tree structure.
+//  2. DominanceFrontier: Calculate and hold the dominance frontier for a
+//     function.
+//
+//  These data structures are listed in increasing order of complexity.  It
+//  takes longer to calculate the dominator frontier, for example, than the
+//  DominatorTree mapping.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_DOMINATORS_H
+#define LLVM_ANALYSIS_DOMINATORS_H
+
+#include "llvm/Pass.h"
+#include <set>
+
+namespace llvm {
+
+class Instruction;
+
+template <typename GraphType> struct GraphTraits;
+
+//===----------------------------------------------------------------------===//
+/// DominatorBase - Base class that other, more interesting dominator analyses
+/// inherit from.
+///
+class DominatorBase : public FunctionPass {
+protected:
+  std::vector<BasicBlock*> Roots;
+  const bool IsPostDominators;
+  inline DominatorBase(intptr_t ID, bool isPostDom) : 
+    FunctionPass(ID), Roots(), IsPostDominators(isPostDom) {}
+public:
+
+  /// getRoots -  Return the root blocks of the current CFG.  This may include
+  /// multiple blocks if we are computing post dominators.  For forward
+  /// dominators, this will always be a single block (the entry node).
+  ///
+  inline const std::vector<BasicBlock*> &getRoots() const { return Roots; }
+
+  /// isPostDominator - Returns true if analysis based of postdoms
+  ///
+  bool isPostDominator() const { return IsPostDominators; }
+};
+
+
+//===----------------------------------------------------------------------===//
+// DomTreeNode - Dominator Tree Node
+class DominatorTreeBase;
+class PostDominatorTree;
+class DomTreeNode {
+  BasicBlock *TheBB;
+  DomTreeNode *IDom;
+  std::vector<DomTreeNode*> Children;
+  int DFSNumIn, DFSNumOut;
+
+  friend class DominatorTreeBase;
+  friend class PostDominatorTree;
+public:
+  typedef std::vector<DomTreeNode*>::iterator iterator;
+  typedef std::vector<DomTreeNode*>::const_iterator const_iterator;
+  
+  iterator begin()             { return Children.begin(); }
+  iterator end()               { return Children.end(); }
+  const_iterator begin() const { return Children.begin(); }
+  const_iterator end()   const { return Children.end(); }
+  
+  inline BasicBlock *getBlock() const { return TheBB; }
+  inline DomTreeNode *getIDom() const { return IDom; }
+  inline const std::vector<DomTreeNode*> &getChildren() const { return Children; }
+  
+  inline DomTreeNode(BasicBlock *BB, DomTreeNode *iDom)
+    : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) { }
+  inline DomTreeNode *addChild(DomTreeNode *C) { Children.push_back(C); return C; }
+  void setIDom(DomTreeNode *NewIDom);
+
+private:
+  // Return true if this node is dominated by other. Use this only if DFS info is valid.
+  bool DominatedBy(const DomTreeNode *other) const {
+    return this->DFSNumIn >= other->DFSNumIn &&
+      this->DFSNumOut <= other->DFSNumOut;
+  }
+
+  /// assignDFSNumber - Assign In and Out numbers while walking dominator tree
+  /// in dfs order.
+  void assignDFSNumber(int num);
+};
+
+//===----------------------------------------------------------------------===//
+/// DominatorTree - Calculate the immediate dominator tree for a function.
+///
+class DominatorTreeBase : public DominatorBase {
+
+protected:
+  void reset();
+  typedef std::map<BasicBlock*, DomTreeNode*> DomTreeNodeMapType;
+  DomTreeNodeMapType DomTreeNodes;
+  DomTreeNode *RootNode;
+
+  bool DFSInfoValid;
+  unsigned int SlowQueries;
+  // Information record used during immediate dominators computation.
+  struct InfoRec {
+    unsigned Semi;
+    unsigned Size;
+    BasicBlock *Label, *Parent, *Child, *Ancestor;
+
+    std::vector<BasicBlock*> Bucket;
+
+    InfoRec() : Semi(0), Size(0), Label(0), Parent(0), Child(0), Ancestor(0){}
+  };
+
+  std::map<BasicBlock*, BasicBlock*> IDoms;
+
+  // Vertex - Map the DFS number to the BasicBlock*
+  std::vector<BasicBlock*> Vertex;
+
+  // Info - Collection of information used during the computation of idoms.
+  std::map<BasicBlock*, InfoRec> Info;
+
+  void updateDFSNumbers();
+
+  public:
+  DominatorTreeBase(intptr_t ID, bool isPostDom) 
+    : DominatorBase(ID, isPostDom), DFSInfoValid(false), SlowQueries(0) {}
+  ~DominatorTreeBase() { reset(); }
+
+  virtual void releaseMemory() { reset(); }
+
+  /// getNode - return the (Post)DominatorTree node for the specified basic
+  /// block.  This is the same as using operator[] on this class.
+  ///
+  inline DomTreeNode *getNode(BasicBlock *BB) const {
+    DomTreeNodeMapType::const_iterator i = DomTreeNodes.find(BB);
+    return (i != DomTreeNodes.end()) ? i->second : 0;
+  }
+
+  inline DomTreeNode *operator[](BasicBlock *BB) const {
+    return getNode(BB);
+  }
+
+  /// getRootNode - This returns the entry node for the CFG of the function.  If
+  /// this tree represents the post-dominance relations for a function, however,
+  /// this root may be a node with the block == NULL.  This is the case when
+  /// there are multiple exit nodes from a particular function.  Consumers of
+  /// post-dominance information must be capable of dealing with this
+  /// possibility.
+  ///
+  DomTreeNode *getRootNode() { return RootNode; }
+  const DomTreeNode *getRootNode() const { return RootNode; }
+
+  /// properlyDominates - Returns true iff this dominates N and this != N.
+  /// Note that this is not a constant time operation!
+  ///
+  bool properlyDominates(const DomTreeNode *A, DomTreeNode *B) const {
+    if (A == 0 || B == 0) return false;
+    return dominatedBySlowTreeWalk(A, B);
+  }
+
+  inline bool properlyDominates(BasicBlock *A, BasicBlock *B) {
+    return properlyDominates(getNode(A), getNode(B));
+  }
+
+  bool dominatedBySlowTreeWalk(const DomTreeNode *A, 
+                               const DomTreeNode *B) const {
+    const DomTreeNode *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;
+  }
+
+
+  /// isReachableFromEntry - Return true if A is dominated by the entry
+  /// block of the function containing it.
+  const bool isReachableFromEntry(BasicBlock* A);
+  
+  /// dominates - Returns true iff A dominates B.  Note that this is not a
+  /// constant time operation!
+  ///
+  inline bool dominates(const DomTreeNode *A, DomTreeNode *B) {
+    if (B == A) 
+      return true;  // A node trivially dominates itself.
+
+    if (A == 0 || B == 0)
+      return false;
+
+    if (DFSInfoValid)
+      return B->DominatedBy(A);
+
+    // If we end up with too many slow queries, just update the
+    // DFS numbers on the theory that we are going to keep querying.
+    SlowQueries++;
+    if (SlowQueries > 32) {
+      updateDFSNumbers();
+      return B->DominatedBy(A);
+    }
+
+    return dominatedBySlowTreeWalk(A, B);
+  }
+
+  inline bool dominates(BasicBlock *A, BasicBlock *B) {
+    if (A == B) 
+      return true;
+    
+    return dominates(getNode(A), getNode(B));
+  }
+
+  /// findNearestCommonDominator - Find nearest common dominator basic block
+  /// for basic block A and B. If there is no such block then return NULL.
+  BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *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(Instruction *A, Instruction *B);
+
+  //===--------------------------------------------------------------------===//
+  // API to update (Post)DominatorTree information based on modifications to
+  // the CFG...
+
+  /// addNewBlock - Add a new node to the dominator tree information.  This
+  /// creates a new node as a child of DomBB dominator node,linking it into 
+  /// the children list of the immediate dominator.
+  DomTreeNode *addNewBlock(BasicBlock *BB, BasicBlock *DomBB) {
+    assert(getNode(BB) == 0 && "Block already in dominator tree!");
+    DomTreeNode *IDomNode = getNode(DomBB);
+    assert(IDomNode && "Not immediate dominator specified for block!");
+    DFSInfoValid = false;
+    return DomTreeNodes[BB] = 
+      IDomNode->addChild(new DomTreeNode(BB, IDomNode));
+  }
+
+  /// changeImmediateDominator - This method is used to update the dominator
+  /// tree information when a node's immediate dominator changes.
+  ///
+  void changeImmediateDominator(DomTreeNode *N, DomTreeNode *NewIDom) {
+    assert(N && NewIDom && "Cannot change null node pointers!");
+    DFSInfoValid = false;
+    N->setIDom(NewIDom);
+  }
+
+  void changeImmediateDominator(BasicBlock *BB, BasicBlock *NewBB) {
+    changeImmediateDominator(getNode(BB), getNode(NewBB));
+  }
+
+  /// removeNode - Removes a node from the dominator tree.  Block must not
+  /// dominate any other blocks.  Invalidates any node pointing to removed
+  /// block.
+  void removeNode(BasicBlock *BB) {
+    assert(getNode(BB) && "Removing node that isn't in dominator tree.");
+    DomTreeNodes.erase(BB);
+  }
+
+  /// print - Convert to human readable form
+  ///
+  virtual void print(std::ostream &OS, const Module* = 0) const;
+  void print(std::ostream *OS, const Module* M = 0) const {
+    if (OS) print(*OS, M);
+  }
+  virtual void dump();
+};
+
+//===-------------------------------------
+/// DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to
+/// compute a normal dominator tree.
+///
+class DominatorTree : public DominatorTreeBase {
+public:
+  static char ID; // Pass ID, replacement for typeid
+  DominatorTree() : DominatorTreeBase((intptr_t)&ID, false) {}
+  
+  BasicBlock *getRoot() const {
+    assert(Roots.size() == 1 && "Should always have entry node!");
+    return Roots[0];
+  }
+  
+  virtual bool runOnFunction(Function &F);
+  
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+  }
+
+  /// splitBlock
+  /// BB is split and now it has one successor. Update dominator tree to
+  /// reflect this change.
+  void splitBlock(BasicBlock *BB);
+private:
+  void calculate(Function& F);
+  DomTreeNode *getNodeForBlock(BasicBlock *BB);
+  unsigned DFSPass(BasicBlock *V, InfoRec &VInfo, unsigned N);
+  void Compress(BasicBlock *V);
+  BasicBlock *Eval(BasicBlock *v);
+  void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
+  inline BasicBlock *getIDom(BasicBlock *BB) const {
+      std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
+      return I != IDoms.end() ? I->second : 0;
+    }
+};
+
+//===-------------------------------------
+/// DominatorTree GraphTraits specialization so the DominatorTree can be
+/// iterable by generic graph iterators.
+///
+template <> struct GraphTraits<DomTreeNode*> {
+  typedef DomTreeNode NodeType;
+  typedef NodeType::iterator  ChildIteratorType;
+  
+  static NodeType *getEntryNode(NodeType *N) {
+    return N;
+  }
+  static inline ChildIteratorType child_begin(NodeType* N) {
+    return N->begin();
+  }
+  static inline ChildIteratorType child_end(NodeType* N) {
+    return N->end();
+  }
+};
+
+template <> struct GraphTraits<DominatorTree*>
+  : public GraphTraits<DomTreeNode*> {
+  static NodeType *getEntryNode(DominatorTree *DT) {
+    return DT->getRootNode();
+  }
+};
+
+
+//===----------------------------------------------------------------------===//
+/// DominanceFrontierBase - Common base class for computing forward and inverse
+/// dominance frontiers for a function.
+///
+class DominanceFrontierBase : public DominatorBase {
+public:
+  typedef std::set<BasicBlock*>             DomSetType;    // Dom set for a bb
+  typedef std::map<BasicBlock*, DomSetType> DomSetMapType; // Dom set map
+protected:
+  DomSetMapType Frontiers;
+public:
+  DominanceFrontierBase(intptr_t ID, bool isPostDom) 
+    : DominatorBase(ID, isPostDom) {}
+
+  virtual void releaseMemory() { Frontiers.clear(); }
+
+  // Accessor interface:
+  typedef DomSetMapType::iterator iterator;
+  typedef DomSetMapType::const_iterator const_iterator;
+  iterator       begin()       { return Frontiers.begin(); }
+  const_iterator begin() const { return Frontiers.begin(); }
+  iterator       end()         { return Frontiers.end(); }
+  const_iterator end()   const { return Frontiers.end(); }
+  iterator       find(BasicBlock *B)       { return Frontiers.find(B); }
+  const_iterator find(BasicBlock *B) const { return Frontiers.find(B); }
+
+  void addBasicBlock(BasicBlock *BB, const DomSetType &frontier) {
+    assert(find(BB) == end() && "Block already in DominanceFrontier!");
+    Frontiers.insert(std::make_pair(BB, frontier));
+  }
+
+  void addToFrontier(iterator I, BasicBlock *Node) {
+    assert(I != end() && "BB is not in DominanceFrontier!");
+    I->second.insert(Node);
+  }
+
+  void removeFromFrontier(iterator I, BasicBlock *Node) {
+    assert(I != end() && "BB is not in DominanceFrontier!");
+    assert(I->second.count(Node) && "Node is not in DominanceFrontier of BB");
+    I->second.erase(Node);
+  }
+
+  /// print - Convert to human readable form
+  ///
+  virtual void print(std::ostream &OS, const Module* = 0) const;
+  void print(std::ostream *OS, const Module* M = 0) const {
+    if (OS) print(*OS, M);
+  }
+  virtual void dump();
+};
+
+
+//===-------------------------------------
+/// DominanceFrontier Class - Concrete subclass of DominanceFrontierBase that is
+/// used to compute a forward dominator frontiers.
+///
+class DominanceFrontier : public DominanceFrontierBase {
+public:
+  static char ID; // Pass ID, replacement for typeid
+  DominanceFrontier() : 
+    DominanceFrontierBase((intptr_t)& ID, false) {}
+
+  BasicBlock *getRoot() const {
+    assert(Roots.size() == 1 && "Should always have entry node!");
+    return Roots[0];
+  }
+
+  virtual bool runOnFunction(Function &) {
+    Frontiers.clear();
+    DominatorTree &DT = getAnalysis<DominatorTree>();
+    Roots = DT.getRoots();
+    assert(Roots.size() == 1 && "Only one entry block for forward domfronts!");
+    calculate(DT, DT[Roots[0]]);
+    return false;
+  }
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<DominatorTree>();
+  }
+
+  /// splitBlock
+  /// BB is split and now it has one successor. Update dominace frontier to
+  /// reflect this change.
+  void splitBlock(BasicBlock *BB);
+
+private:
+  const DomSetType &calculate(const DominatorTree &DT,
+                              const DomTreeNode *Node);
+};
+
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/FindUsedTypes.h b/include/llvm/Analysis/FindUsedTypes.h
new file mode 100644
index 0000000..6cafc89
--- /dev/null
+++ b/include/llvm/Analysis/FindUsedTypes.h
@@ -0,0 +1,67 @@
+//===- llvm/Analysis/FindUsedTypes.h - Find all Types in use ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass is used to seek out all of the types in use by the program.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_FINDUSEDTYPES_H
+#define LLVM_ANALYSIS_FINDUSEDTYPES_H
+
+#include "llvm/Pass.h"
+#include <set>
+
+namespace llvm {
+
+class Type;
+
+class FindUsedTypes : public ModulePass {
+  std::set<const Type *> UsedTypes;
+public:
+  static char ID; // Pass identification, replacement for typeid
+  FindUsedTypes() : ModulePass((intptr_t)&ID) {}
+
+  /// getTypes - After the pass has been run, return the set containing all of
+  /// the types used in the module.
+  ///
+  const std::set<const Type *> &getTypes() const { return UsedTypes; }
+
+  /// Print the types found in the module.  If the optional Module parameter is
+  /// passed in, then the types are printed symbolically if possible, using the
+  /// symbol table from the module.
+  ///
+  void print(std::ostream &o, const Module *M) const;
+  void print(std::ostream *o, const Module *M) const { if (o) print(*o, M); }
+
+private:
+  /// IncorporateType - Incorporate one type and all of its subtypes into the
+  /// collection of used types.
+  ///
+  void IncorporateType(const Type *Ty);
+
+  /// IncorporateValue - Incorporate all of the types used by this value.
+  ///
+  void IncorporateValue(const Value *V);
+
+public:
+  /// run - This incorporates all types used by the specified module
+  bool runOnModule(Module &M);
+
+  /// getAnalysisUsage - We do not modify anything.
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+  }
+};
+
+} // End llvm namespace
+
+// Make sure that any clients of this file link in PostDominators.cpp
+FORCE_DEFINING_FILE_TO_BE_LINKED(FindUsedTypes)
+
+#endif
diff --git a/include/llvm/Analysis/Interval.h b/include/llvm/Analysis/Interval.h
new file mode 100644
index 0000000..bed815a
--- /dev/null
+++ b/include/llvm/Analysis/Interval.h
@@ -0,0 +1,154 @@
+//===- llvm/Analysis/Interval.h - Interval Class Declaration ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the declaration of the Interval class, which
+// represents a set of CFG nodes and is a portion of an interval partition.
+//
+// Intervals have some interesting and useful properties, including the
+// following:
+//    1. The header node of an interval dominates all of the elements of the
+//       interval
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_INTERVAL_H
+#define LLVM_INTERVAL_H
+
+#include "llvm/ADT/GraphTraits.h"
+#include <vector>
+#include <iosfwd>
+
+namespace llvm {
+
+class BasicBlock;
+
+//===----------------------------------------------------------------------===//
+//
+/// Interval Class - An Interval is a set of nodes defined such that every node
+/// in the interval has all of its predecessors in the interval (except for the
+/// header)
+///
+class Interval {
+  /// HeaderNode - The header BasicBlock, which dominates all BasicBlocks in this
+  /// interval.  Also, any loops in this interval must go through the HeaderNode.
+  ///
+  BasicBlock *HeaderNode;
+public:
+  typedef std::vector<BasicBlock*>::iterator succ_iterator;
+  typedef std::vector<BasicBlock*>::iterator pred_iterator;
+  typedef std::vector<BasicBlock*>::iterator node_iterator;
+
+  inline Interval(BasicBlock *Header) : HeaderNode(Header) {
+    Nodes.push_back(Header);
+  }
+
+  inline Interval(const Interval &I) // copy ctor
+    : HeaderNode(I.HeaderNode), Nodes(I.Nodes), Successors(I.Successors) {}
+
+  inline BasicBlock *getHeaderNode() const { return HeaderNode; }
+
+  /// Nodes - The basic blocks in this interval.
+  ///
+  std::vector<BasicBlock*> Nodes;
+
+  /// Successors - List of BasicBlocks that are reachable directly from nodes in
+  /// this interval, but are not in the interval themselves.
+  /// These nodes necessarily must be header nodes for other intervals.
+  ///
+  std::vector<BasicBlock*> Successors;
+
+  /// Predecessors - List of BasicBlocks that have this Interval's header block
+  /// as one of their successors.
+  ///
+  std::vector<BasicBlock*> Predecessors;
+
+  /// contains - Find out if a basic block is in this interval
+  inline bool contains(BasicBlock *BB) const {
+    for (unsigned i = 0; i < Nodes.size(); ++i)
+      if (Nodes[i] == BB) return true;
+    return false;
+    // I don't want the dependency on <algorithm>
+    //return find(Nodes.begin(), Nodes.end(), BB) != Nodes.end();
+  }
+
+  /// isSuccessor - find out if a basic block is a successor of this Interval
+  inline bool isSuccessor(BasicBlock *BB) const {
+    for (unsigned i = 0; i < Successors.size(); ++i)
+      if (Successors[i] == BB) return true;
+    return false;
+    // I don't want the dependency on <algorithm>
+    //return find(Successors.begin(), Successors.end(), BB) != Successors.end();
+  }
+
+  /// Equality operator.  It is only valid to compare two intervals from the
+  /// same partition, because of this, all we have to check is the header node
+  /// for equality.
+  ///
+  inline bool operator==(const Interval &I) const {
+    return HeaderNode == I.HeaderNode;
+  }
+
+  /// isLoop - Find out if there is a back edge in this interval...
+  bool isLoop() const;
+
+  /// print - Show contents in human readable format...
+  void print(std::ostream &O) const;
+  void print(std::ostream *O) const { if (O) print(*O); }
+};
+
+/// succ_begin/succ_end - define methods so that Intervals may be used
+/// just like BasicBlocks can with the succ_* functions, and *::succ_iterator.
+///
+inline Interval::succ_iterator succ_begin(Interval *I) {
+  return I->Successors.begin();
+}
+inline Interval::succ_iterator succ_end(Interval *I)   {
+  return I->Successors.end();
+}
+
+/// pred_begin/pred_end - define methods so that Intervals may be used
+/// just like BasicBlocks can with the pred_* functions, and *::pred_iterator.
+///
+inline Interval::pred_iterator pred_begin(Interval *I) {
+  return I->Predecessors.begin();
+}
+inline Interval::pred_iterator pred_end(Interval *I)   {
+  return I->Predecessors.end();
+}
+
+template <> struct GraphTraits<Interval*> {
+  typedef Interval NodeType;
+  typedef Interval::succ_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(Interval *I) { return I; }
+
+  /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return succ_begin(N);
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return succ_end(N);
+  }
+};
+
+template <> struct GraphTraits<Inverse<Interval*> > {
+  typedef Interval NodeType;
+  typedef Interval::pred_iterator ChildIteratorType;
+  static NodeType *getEntryNode(Inverse<Interval *> G) { return G.Graph; }
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return pred_begin(N);
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return pred_end(N);
+  }
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/IntervalIterator.h b/include/llvm/Analysis/IntervalIterator.h
new file mode 100644
index 0000000..dfa983c
--- /dev/null
+++ b/include/llvm/Analysis/IntervalIterator.h
@@ -0,0 +1,258 @@
+//===- IntervalIterator.h - Interval Iterator Declaration -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines an iterator that enumerates the intervals in a control flow
+// graph of some sort.  This iterator is parametric, allowing iterator over the
+// following types of graphs:
+//
+//  1. A Function* object, composed of BasicBlock nodes.
+//  2. An IntervalPartition& object, composed of Interval nodes.
+//
+// This iterator is defined to walk the control flow graph, returning intervals
+// in depth first order.  These intervals are completely filled in except for
+// the predecessor fields (the successor information is filled in however).
+//
+// By default, the intervals created by this iterator are deleted after they
+// are no longer any use to the iterator.  This behavior can be changed by
+// passing a false value into the intervals_begin() function. This causes the
+// IOwnMem member to be set, and the intervals to not be deleted.
+//
+// It is only safe to use this if all of the intervals are deleted by the caller
+// and all of the intervals are processed.  However, the user of the iterator is
+// not allowed to modify or delete the intervals until after the iterator has
+// been used completely.  The IntervalPartition class uses this functionality.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_INTERVAL_ITERATOR_H
+#define LLVM_INTERVAL_ITERATOR_H
+
+#include "llvm/Analysis/IntervalPartition.h"
+#include "llvm/Function.h"
+#include "llvm/Support/CFG.h"
+#include <stack>
+#include <set>
+#include <algorithm>
+
+namespace llvm {
+
+// getNodeHeader - Given a source graph node and the source graph, return the
+// BasicBlock that is the header node.  This is the opposite of
+// getSourceGraphNode.
+//
+inline BasicBlock *getNodeHeader(BasicBlock *BB) { return BB; }
+inline BasicBlock *getNodeHeader(Interval *I) { return I->getHeaderNode(); }
+
+// getSourceGraphNode - Given a BasicBlock and the source graph, return the
+// source graph node that corresponds to the BasicBlock.  This is the opposite
+// of getNodeHeader.
+//
+inline BasicBlock *getSourceGraphNode(Function *, BasicBlock *BB) {
+  return BB;
+}
+inline Interval *getSourceGraphNode(IntervalPartition *IP, BasicBlock *BB) {
+  return IP->getBlockInterval(BB);
+}
+
+// addNodeToInterval - This method exists to assist the generic ProcessNode
+// with the task of adding a node to the new interval, depending on the
+// type of the source node.  In the case of a CFG source graph (BasicBlock
+// case), the BasicBlock itself is added to the interval.
+//
+inline void addNodeToInterval(Interval *Int, BasicBlock *BB) {
+  Int->Nodes.push_back(BB);
+}
+
+// addNodeToInterval - This method exists to assist the generic ProcessNode
+// with the task of adding a node to the new interval, depending on the
+// type of the source node.  In the case of a CFG source graph (BasicBlock
+// case), the BasicBlock itself is added to the interval.  In the case of
+// an IntervalPartition source graph (Interval case), all of the member
+// BasicBlocks are added to the interval.
+//
+inline void addNodeToInterval(Interval *Int, Interval *I) {
+  // Add all of the nodes in I as new nodes in Int.
+  copy(I->Nodes.begin(), I->Nodes.end(), back_inserter(Int->Nodes));
+}
+
+
+
+
+
+template<class NodeTy, class OrigContainer_t, class GT = GraphTraits<NodeTy*>,
+         class IGT = GraphTraits<Inverse<NodeTy*> > >
+class IntervalIterator {
+  std::stack<std::pair<Interval*, typename Interval::succ_iterator> > IntStack;
+  std::set<BasicBlock*> Visited;
+  OrigContainer_t *OrigContainer;
+  bool IOwnMem;     // If True, delete intervals when done with them
+                    // See file header for conditions of use
+public:
+  typedef IntervalIterator<NodeTy, OrigContainer_t> _Self;
+  typedef std::forward_iterator_tag iterator_category;
+
+  IntervalIterator() {} // End iterator, empty stack
+  IntervalIterator(Function *M, bool OwnMemory) : IOwnMem(OwnMemory) {
+    OrigContainer = M;
+    if (!ProcessInterval(&M->front())) {
+      assert(0 && "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!");
+    }
+  }
+
+  inline ~IntervalIterator() {
+    if (IOwnMem)
+      while (!IntStack.empty()) {
+        delete operator*();
+        IntStack.pop();
+      }
+  }
+
+  inline bool operator==(const _Self& x) const { return IntStack == x.IntStack;}
+  inline bool operator!=(const _Self& x) const { return !operator==(x); }
+
+  inline const Interval *operator*() const { return IntStack.top().first; }
+  inline       Interval *operator*()       { return IntStack.top().first; }
+  inline const Interval *operator->() const { return operator*(); }
+  inline       Interval *operator->()       { return operator*(); }
+
+  _Self& operator++() {  // Preincrement
+    assert(!IntStack.empty() && "Attempting to use interval iterator at end!");
+    do {
+      // All of the intervals on the stack have been visited.  Try visiting
+      // their successors now.
+      Interval::succ_iterator &SuccIt = IntStack.top().second,
+                                EndIt = succ_end(IntStack.top().first);
+      while (SuccIt != EndIt) {                 // Loop over all interval succs
+        bool Done = ProcessInterval(getSourceGraphNode(OrigContainer, *SuccIt));
+        ++SuccIt;                               // Increment iterator
+        if (Done) return *this;                 // Found a new interval! Use it!
+      }
+
+      // Free interval memory... if necessary
+      if (IOwnMem) delete IntStack.top().first;
+
+      // We ran out of successors for this interval... pop off the stack
+      IntStack.pop();
+    } while (!IntStack.empty());
+
+    return *this;
+  }
+  inline _Self operator++(int) { // Postincrement
+    _Self tmp = *this; ++*this; return tmp;
+  }
+
+private:
+  // ProcessInterval - This method is used during the construction of the
+  // interval graph.  It walks through the source graph, recursively creating
+  // an interval per invokation until the entire graph is covered.  This uses
+  // the ProcessNode method to add all of the nodes to the interval.
+  //
+  // This method is templated because it may operate on two different source
+  // graphs: a basic block graph, or a preexisting interval graph.
+  //
+  bool ProcessInterval(NodeTy *Node) {
+    BasicBlock *Header = getNodeHeader(Node);
+    if (Visited.count(Header)) return false;
+
+    Interval *Int = new Interval(Header);
+    Visited.insert(Header);   // The header has now been visited!
+
+    // Check all of our successors to see if they are in the interval...
+    for (typename GT::ChildIteratorType I = GT::child_begin(Node),
+           E = GT::child_end(Node); I != E; ++I)
+      ProcessNode(Int, getSourceGraphNode(OrigContainer, *I));
+
+    IntStack.push(std::make_pair(Int, succ_begin(Int)));
+    return true;
+  }
+
+  // ProcessNode - This method is called by ProcessInterval to add nodes to the
+  // interval being constructed, and it is also called recursively as it walks
+  // the source graph.  A node is added to the current interval only if all of
+  // its predecessors are already in the graph.  This also takes care of keeping
+  // the successor set of an interval up to date.
+  //
+  // This method is templated because it may operate on two different source
+  // graphs: a basic block graph, or a preexisting interval graph.
+  //
+  void ProcessNode(Interval *Int, NodeTy *Node) {
+    assert(Int && "Null interval == bad!");
+    assert(Node && "Null Node == bad!");
+
+    BasicBlock *NodeHeader = getNodeHeader(Node);
+
+    if (Visited.count(NodeHeader)) {     // Node already been visited?
+      if (Int->contains(NodeHeader)) {   // Already in this interval...
+        return;
+      } else {                           // In other interval, add as successor
+        if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
+          Int->Successors.push_back(NodeHeader);
+      }
+    } else {                             // Otherwise, not in interval yet
+      for (typename IGT::ChildIteratorType I = IGT::child_begin(Node),
+             E = IGT::child_end(Node); I != E; ++I) {
+        if (!Int->contains(*I)) {        // If pred not in interval, we can't be
+          if (!Int->isSuccessor(NodeHeader)) // Add only if not already in set
+            Int->Successors.push_back(NodeHeader);
+          return;                        // See you later
+        }
+      }
+
+      // If we get here, then all of the predecessors of BB are in the interval
+      // already.  In this case, we must add BB to the interval!
+      addNodeToInterval(Int, Node);
+      Visited.insert(NodeHeader);     // The node has now been visited!
+
+      if (Int->isSuccessor(NodeHeader)) {
+        // If we were in the successor list from before... remove from succ list
+        Int->Successors.erase(std::remove(Int->Successors.begin(),
+                                          Int->Successors.end(), NodeHeader),
+                              Int->Successors.end());
+      }
+
+      // Now that we have discovered that Node is in the interval, perhaps some
+      // of its successors are as well?
+      for (typename GT::ChildIteratorType It = GT::child_begin(Node),
+             End = GT::child_end(Node); It != End; ++It)
+        ProcessNode(Int, getSourceGraphNode(OrigContainer, *It));
+    }
+  }
+};
+
+typedef IntervalIterator<BasicBlock, Function> function_interval_iterator;
+typedef IntervalIterator<Interval, IntervalPartition> interval_part_interval_iterator;
+
+
+inline function_interval_iterator intervals_begin(Function *F,
+                                                  bool DeleteInts = true) {
+  return function_interval_iterator(F, DeleteInts);
+}
+inline function_interval_iterator intervals_end(Function *) {
+  return function_interval_iterator();
+}
+
+inline interval_part_interval_iterator
+   intervals_begin(IntervalPartition &IP, bool DeleteIntervals = true) {
+  return interval_part_interval_iterator(IP, DeleteIntervals);
+}
+
+inline interval_part_interval_iterator intervals_end(IntervalPartition &IP) {
+  return interval_part_interval_iterator();
+}
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/IntervalPartition.h b/include/llvm/Analysis/IntervalPartition.h
new file mode 100644
index 0000000..1f985e3
--- /dev/null
+++ b/include/llvm/Analysis/IntervalPartition.h
@@ -0,0 +1,114 @@
+//===- IntervalPartition.h - Interval partition Calculation -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains the declaration of the IntervalPartition class, which
+// calculates and represents the interval partition of a function, or a
+// preexisting interval partition.
+//
+// In this way, the interval partition may be used to reduce a flow graph down
+// to its degenerate single node interval partition (unless it is irreducible).
+//
+// TODO: The IntervalPartition class should take a bool parameter that tells
+// whether it should add the "tails" of an interval to an interval itself or if
+// they should be represented as distinct intervals.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_INTERVAL_PARTITION_H
+#define LLVM_INTERVAL_PARTITION_H
+
+#include "llvm/Analysis/Interval.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+
+//===----------------------------------------------------------------------===//
+//
+// IntervalPartition - This class builds and holds an "interval partition" for
+// a function.  This partition divides the control flow graph into a set of
+// maximal intervals, as defined with the properties above.  Intuitively, a
+// BasicBlock is a (possibly nonexistent) loop with a "tail" of non looping
+// nodes following it.
+//
+class IntervalPartition : public FunctionPass {
+  typedef std::map<BasicBlock*, Interval*> IntervalMapTy;
+  IntervalMapTy IntervalMap;
+
+  typedef std::vector<Interval*> IntervalListTy;
+  Interval *RootInterval;
+  std::vector<Interval*> Intervals;
+
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  IntervalPartition() : FunctionPass((intptr_t)&ID), RootInterval(0) {}
+
+  // run - Calculate the interval partition for this function
+  virtual bool runOnFunction(Function &F);
+
+  // IntervalPartition ctor - Build a reduced interval partition from an
+  // existing interval graph.  This takes an additional boolean parameter to
+  // distinguish it from a copy constructor.  Always pass in false for now.
+  //
+  IntervalPartition(IntervalPartition &I, bool);
+
+  // Destructor - Free memory
+  ~IntervalPartition() { destroy(); }
+
+  // print - Show contents in human readable format...
+  virtual void print(std::ostream &O, const Module* = 0) const;
+  void print(std::ostream *O, const Module* M = 0) const {
+    if (O) print(*O, M);
+  }
+
+  // getRootInterval() - Return the root interval that contains the starting
+  // block of the function.
+  inline Interval *getRootInterval() { return RootInterval; }
+
+  // isDegeneratePartition() - Returns true if the interval partition contains
+  // a single interval, and thus cannot be simplified anymore.
+  bool isDegeneratePartition() { return Intervals.size() == 1; }
+
+  // TODO: isIrreducible - look for triangle graph.
+
+  // getBlockInterval - Return the interval that a basic block exists in.
+  inline Interval *getBlockInterval(BasicBlock *BB) {
+    IntervalMapTy::iterator I = IntervalMap.find(BB);
+    return I != IntervalMap.end() ? I->second : 0;
+  }
+
+  // getAnalysisUsage - Implement the Pass API
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+  }
+
+  // Interface to Intervals vector...
+  const std::vector<Interval*> &getIntervals() const { return Intervals; }
+
+private:
+  // destroy - Reset state back to before function was analyzed
+  void destroy();
+
+  // addIntervalToPartition - Add an interval to the internal list of intervals,
+  // and then add mappings from all of the basic blocks in the interval to the
+  // interval itself (in the IntervalMap).
+  //
+  void addIntervalToPartition(Interval *I);
+
+  // updatePredecessors - Interval generation only sets the successor fields of
+  // the interval data structures.  After interval generation is complete,
+  // run through all of the intervals and propagate successor info as
+  // predecessor info.
+  //
+  void updatePredecessors(Interval *Int);
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/LoadValueNumbering.h b/include/llvm/Analysis/LoadValueNumbering.h
new file mode 100644
index 0000000..b924595
--- /dev/null
+++ b/include/llvm/Analysis/LoadValueNumbering.h
@@ -0,0 +1,35 @@
+//===- llvm/Analysis/LoadValueNumbering.h - Value # Load Insts --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a value numbering pass that value #'s load instructions.
+// To do this, it finds lexically identical load instructions, and uses alias
+// analysis to determine which loads are guaranteed to produce the same value.
+//
+// This pass builds off of another value numbering pass to implement value
+// numbering for non-load instructions.  It uses Alias Analysis so that it can
+// disambiguate the load instructions.  The more powerful these base analyses
+// are, the more powerful the resultant analysis will be.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOAD_VALUE_NUMBERING_H
+#define LLVM_ANALYSIS_LOAD_VALUE_NUMBERING_H
+
+namespace llvm {
+
+class FunctionPass;
+
+/// createLoadValueNumberingPass - Create and return a new pass that implements
+/// the ValueNumbering interface.
+///
+FunctionPass *createLoadValueNumberingPass();
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
new file mode 100644
index 0000000..b332fd1
--- /dev/null
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -0,0 +1,363 @@
+//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the LoopInfo class that is used to identify natural loops
+// and determine the loop depth of various nodes of the CFG.  Note that natural
+// loops may actually be several loops that share the same header node.
+//
+// This analysis calculates the nesting structure of loops in a function.  For
+// each natural loop identified, this analysis identifies natural loops
+// contained entirely within the loop and the basic blocks the make up the loop.
+//
+// It can calculate on the fly various bits of information, for example:
+//
+//  * whether there is a preheader for the loop
+//  * the number of back edges to the header
+//  * whether or not a particular block branches out of the loop
+//  * the successor blocks of the loop
+//  * the loop depth
+//  * the trip count
+//  * etc...
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOP_INFO_H
+#define LLVM_ANALYSIS_LOOP_INFO_H
+
+#include "llvm/Pass.h"
+#include "llvm/ADT/GraphTraits.h"
+
+namespace llvm {
+
+class DominatorTree;
+class LoopInfo;
+class PHINode;
+class Instruction;
+
+//===----------------------------------------------------------------------===//
+/// Loop class - Instances of this class are used to represent loops that are
+/// detected in the flow graph
+///
+class Loop {
+  Loop *ParentLoop;
+  std::vector<Loop*> SubLoops;       // Loops contained entirely within this one
+  std::vector<BasicBlock*> Blocks;   // First entry is the header node
+
+  Loop(const Loop &);                  // DO NOT IMPLEMENT
+  const Loop &operator=(const Loop &); // DO NOT IMPLEMENT
+public:
+  /// Loop ctor - This creates an empty loop.
+  Loop() : ParentLoop(0) {}
+  ~Loop() {
+    for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
+      delete SubLoops[i];
+  }
+
+  unsigned getLoopDepth() const {
+    unsigned D = 0;
+    for (const Loop *CurLoop = this; CurLoop; CurLoop = CurLoop->ParentLoop)
+      ++D;
+    return D;
+  }
+  BasicBlock *getHeader() const { return Blocks.front(); }
+  Loop *getParentLoop() const { return ParentLoop; }
+
+  /// contains - Return true of the specified basic block is in this loop
+  ///
+  bool contains(const BasicBlock *BB) const;
+
+  /// iterator/begin/end - Return the loops contained entirely within this loop.
+  ///
+  const std::vector<Loop*> &getSubLoops() const { return SubLoops; }
+  typedef std::vector<Loop*>::const_iterator iterator;
+  iterator begin() const { return SubLoops.begin(); }
+  iterator end() const { return SubLoops.end(); }
+
+  /// getBlocks - Get a list of the basic blocks which make up this loop.
+  ///
+  const std::vector<BasicBlock*> &getBlocks() const { return Blocks; }
+  typedef std::vector<BasicBlock*>::const_iterator block_iterator;
+  block_iterator block_begin() const { return Blocks.begin(); }
+  block_iterator block_end() const { return Blocks.end(); }
+
+  /// isLoopExit - True if terminator in the block can branch to another block
+  /// that is outside of the current loop.
+  ///
+  bool isLoopExit(const BasicBlock *BB) const;
+
+  /// getNumBackEdges - Calculate the number of back edges to the loop header
+  ///
+  unsigned getNumBackEdges() const;
+
+  /// isLoopInvariant - Return true if the specified value is loop invariant
+  ///
+  bool isLoopInvariant(Value *V) const;
+
+  //===--------------------------------------------------------------------===//
+  // APIs for simple analysis of the loop.
+  //
+  // Note that all of these methods can fail on general loops (ie, there may not
+  // be a preheader, etc).  For best success, the loop simplification and
+  // induction variable canonicalization pass should be used to normalize loops
+  // for easy analysis.  These methods assume canonical loops.
+
+  /// getExitingBlocks - Return all blocks inside the loop that have successors
+  /// outside of the loop.  These are the blocks _inside of the current loop_
+  /// which branch out.  The returned list is always unique.
+  ///
+  void getExitingBlocks(std::vector<BasicBlock*> &Blocks) const;
+
+  /// getExitBlocks - Return all of the successor blocks of this loop.  These
+  /// are the blocks _outside of the current loop_ which are branched to.
+  ///
+  void getExitBlocks(std::vector<BasicBlock*> &Blocks) const;
+
+  /// getUniqueExitBlocks - Return all unique successor blocks of this loop. 
+  /// These are the blocks _outside of the current loop_ which are branched to.
+  /// This assumes that loop is in canonical form.
+  ///
+  void getUniqueExitBlocks(std::vector<BasicBlock*> &ExitBlocks) const;
+
+  /// getLoopPreheader - If there is a preheader for this loop, return it.  A
+  /// loop has a preheader if there is only one edge to the header of the loop
+  /// from outside of the loop.  If this is the case, the block branching to the
+  /// header of the loop is the preheader node.
+  ///
+  /// This method returns null if there is no preheader for the loop.
+  ///
+  BasicBlock *getLoopPreheader() const;
+
+  /// getLoopLatch - If there is a latch block for this loop, return it.  A
+  /// latch block is the canonical backedge for a loop.  A loop header in normal
+  /// form has two edges into it: one from a preheader and one from a latch
+  /// block.
+  BasicBlock *getLoopLatch() const;
+  
+  /// getCanonicalInductionVariable - Check to see if the loop has a canonical
+  /// induction variable: an integer recurrence that starts at 0 and increments
+  /// by one each time through the loop.  If so, return the phi node that
+  /// corresponds to it.
+  ///
+  PHINode *getCanonicalInductionVariable() const;
+
+  /// getCanonicalInductionVariableIncrement - Return the LLVM value that holds
+  /// the canonical induction variable value for the "next" iteration of the
+  /// loop.  This always succeeds if getCanonicalInductionVariable succeeds.
+  ///
+  Instruction *getCanonicalInductionVariableIncrement() 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.
+  ///
+  Value *getTripCount() const;
+  
+  /// isLCSSAForm - Return true if the Loop is in LCSSA form
+  bool isLCSSAForm() const;
+
+  //===--------------------------------------------------------------------===//
+  // APIs for updating loop information after changing the CFG
+  //
+
+  /// addBasicBlockToLoop - This method is used by other analyses to update loop
+  /// information.  NewBB is set to be a new member of the current loop.
+  /// Because of this, it is added as a member of all parent loops, and is added
+  /// to the specified LoopInfo object as being in the current basic block.  It
+  /// is not valid to replace the loop header with this method.
+  ///
+  void addBasicBlockToLoop(BasicBlock *NewBB, LoopInfo &LI);
+
+  /// replaceChildLoopWith - This is used when splitting loops up.  It replaces
+  /// the OldChild entry in our children list with NewChild, and updates the
+  /// parent pointer of OldChild to be null and the NewChild to be this loop.
+  /// This updates the loop depth of the new child.
+  void replaceChildLoopWith(Loop *OldChild, Loop *NewChild);
+
+  /// addChildLoop - Add the specified loop to be a child of this loop.  This
+  /// updates the loop depth of the new child.
+  ///
+  void addChildLoop(Loop *NewChild);
+
+  /// removeChildLoop - This removes the specified child from being a subloop of
+  /// this loop.  The loop is not deleted, as it will presumably be inserted
+  /// into another loop.
+  Loop *removeChildLoop(iterator OldChild);
+
+  /// addBlockEntry - This adds a basic block directly to the basic block list.
+  /// This should only be used by transformations that create new loops.  Other
+  /// transformations should use addBasicBlockToLoop.
+  void addBlockEntry(BasicBlock *BB) {
+    Blocks.push_back(BB);
+  }
+
+  /// moveToHeader - This method is used to move BB (which must be part of this
+  /// loop) to be the loop header of the loop (the block that dominates all
+  /// others).
+  void moveToHeader(BasicBlock *BB) {
+    if (Blocks[0] == BB) return;
+    for (unsigned i = 0; ; ++i) {
+      assert(i != Blocks.size() && "Loop does not contain BB!");
+      if (Blocks[i] == BB) {
+        Blocks[i] = Blocks[0];
+        Blocks[0] = BB;
+        return;
+      }
+    }
+  }
+
+  /// removeBlockFromLoop - This removes the specified basic block from the
+  /// current loop, updating the Blocks as appropriate.  This does not update
+  /// the mapping in the LoopInfo class.
+  void removeBlockFromLoop(BasicBlock *BB);
+
+  void print(std::ostream &O, unsigned Depth = 0) const;
+  void print(std::ostream *O, unsigned Depth = 0) const {
+    if (O) print(*O, Depth);
+  }
+  void dump() const;
+private:
+  friend class LoopInfo;
+  Loop(BasicBlock *BB) : ParentLoop(0) {
+    Blocks.push_back(BB);
+  }
+};
+
+
+
+//===----------------------------------------------------------------------===//
+/// LoopInfo - This class builds and contains all of the top level loop
+/// structures in the specified function.
+///
+class LoopInfo : public FunctionPass {
+  // BBMap - Mapping of basic blocks to the inner most loop they occur in
+  std::map<BasicBlock*, Loop*> BBMap;
+  std::vector<Loop*> TopLevelLoops;
+  friend class Loop;
+public:
+  static char ID; // Pass identification, replacement for typeid
+
+  LoopInfo() : FunctionPass((intptr_t)&ID) {}
+  ~LoopInfo() { releaseMemory(); }
+
+  /// iterator/begin/end - The interface to the top-level loops in the current
+  /// function.
+  ///
+  typedef std::vector<Loop*>::const_iterator iterator;
+  iterator begin() const { return TopLevelLoops.begin(); }
+  iterator end() const { return TopLevelLoops.end(); }
+
+  /// getLoopFor - Return the inner most loop that BB lives in.  If a basic
+  /// block is in no loop (for example the entry node), null is returned.
+  ///
+  Loop *getLoopFor(const BasicBlock *BB) const {
+    std::map<BasicBlock *, Loop*>::const_iterator I=
+      BBMap.find(const_cast<BasicBlock*>(BB));
+    return I != BBMap.end() ? I->second : 0;
+  }
+
+  /// operator[] - same as getLoopFor...
+  ///
+  const Loop *operator[](const BasicBlock *BB) const {
+    return getLoopFor(BB);
+  }
+
+  /// getLoopDepth - Return the loop nesting level of the specified block...
+  ///
+  unsigned getLoopDepth(const BasicBlock *BB) const {
+    const Loop *L = getLoopFor(BB);
+    return L ? L->getLoopDepth() : 0;
+  }
+
+  // isLoopHeader - True if the block is a loop header node
+  bool isLoopHeader(BasicBlock *BB) const {
+    const Loop *L = getLoopFor(BB);
+    return L && L->getHeader() == BB;
+  }
+
+  /// runOnFunction - Calculate the natural loop information.
+  ///
+  virtual bool runOnFunction(Function &F);
+
+  virtual void releaseMemory();
+
+  void print(std::ostream &O, const Module* = 0) const;
+  void print(std::ostream *O, const Module* M = 0) const {
+    if (O) print(*O, M);
+  }
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
+  /// removeLoop - This removes the specified top-level loop from this loop info
+  /// object.  The loop is not deleted, as it will presumably be inserted into
+  /// another loop.
+  Loop *removeLoop(iterator I);
+
+  /// changeLoopFor - Change the top-level loop that contains BB to the
+  /// specified loop.  This should be used by transformations that restructure
+  /// the loop hierarchy tree.
+  void changeLoopFor(BasicBlock *BB, Loop *L);
+
+  /// changeTopLevelLoop - Replace the specified loop in the top-level loops
+  /// list with the indicated loop.
+  void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop);
+
+  /// addTopLevelLoop - This adds the specified loop to the collection of
+  /// top-level loops.
+  void addTopLevelLoop(Loop *New) {
+    assert(New->getParentLoop() == 0 && "Loop already in subloop!");
+    TopLevelLoops.push_back(New);
+  }
+
+  /// removeBlock - This method completely removes BB from all data structures,
+  /// including all of the Loop objects it is nested in and our mapping from
+  /// BasicBlocks to loops.
+  void removeBlock(BasicBlock *BB);
+
+private:
+  void Calculate(DominatorTree &DT);
+  Loop *ConsiderForLoop(BasicBlock *BB, DominatorTree &DT);
+  void MoveSiblingLoopInto(Loop *NewChild, Loop *NewParent);
+  void InsertLoopInto(Loop *L, Loop *Parent);
+};
+
+
+// Allow clients to walk the list of nested loops...
+template <> struct GraphTraits<const Loop*> {
+  typedef const Loop NodeType;
+  typedef std::vector<Loop*>::const_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(const Loop *L) { return L; }
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->begin();
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->end();
+  }
+};
+
+template <> struct GraphTraits<Loop*> {
+  typedef Loop NodeType;
+  typedef std::vector<Loop*>::const_iterator ChildIteratorType;
+
+  static NodeType *getEntryNode(Loop *L) { return L; }
+  static inline ChildIteratorType child_begin(NodeType *N) {
+    return N->begin();
+  }
+  static inline ChildIteratorType child_end(NodeType *N) {
+    return N->end();
+  }
+};
+
+} // End llvm namespace
+
+// Make sure that any clients of this file link in LoopInfo.cpp
+FORCE_DEFINING_FILE_TO_BE_LINKED(LoopInfo)
+
+#endif
diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h
new file mode 100644
index 0000000..08c2bcb
--- /dev/null
+++ b/include/llvm/Analysis/LoopPass.h
@@ -0,0 +1,132 @@
+//===- LoopPass.h - LoopPass class ----------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by Devang Patel and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines LoopPass class. All loop optimization
+// and transformation passes are derived from LoopPass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_LOOP_PASS_H
+#define LLVM_LOOP_PASS_H
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Pass.h"
+#include "llvm/PassManagers.h"
+#include "llvm/Function.h"
+
+namespace llvm {
+
+class LPPassManager;
+class Loop;
+class Function;
+
+class LoopPass : public Pass {
+
+ public:
+ explicit LoopPass(intptr_t pid) : Pass(pid) {}
+
+  // runOnLoop - This method should be implemented by the subclass to perform
+  // whatever action is necessary for the specfied Loop. 
+  virtual bool runOnLoop (Loop *L, LPPassManager &LPM) = 0;
+  virtual bool runOnFunctionBody (Function &F, LPPassManager &LPM) { 
+    return false; 
+  }
+
+  // Initialization and finalization hooks.
+  virtual bool doInitialization(Loop *L, LPPassManager &LPM) { 
+    return false; 
+  }
+
+  // Finalization hook does not supply Loop because at this time
+  // loop nest is completely different.
+  virtual bool doFinalization() { return false; }
+
+  // Check if this pass is suitable for the current LPPassManager, if
+  // available. This pass P is not suitable for a LPPassManager if P
+  // is not preserving higher level analysis info used by other
+  // LPPassManager passes. In such case, pop LPPassManager from the
+  // stack. This will force assignPassManager() to create new
+  // LPPassManger as expected.
+  void preparePassManager(PMStack &PMS);
+
+  /// Assign pass manager to manager this pass
+  virtual void assignPassManager(PMStack &PMS,
+                                 PassManagerType PMT = PMT_LoopPassManager);
+
+  ///  Return what kind of Pass Manager can manage this pass.
+  virtual PassManagerType getPotentialPassManagerType() const {
+    return PMT_LoopPassManager;
+  }
+};
+
+class LPPassManager : public FunctionPass, public PMDataManager {
+
+public:
+  static char ID;
+  LPPassManager(int Depth);
+
+  /// run - Execute all of the passes scheduled for execution.  Keep track of
+  /// whether any of the passes modifies the module, and if so, return true.
+  bool runOnFunction(Function &F);
+
+  /// Pass Manager itself does not invalidate any analysis info.
+  // LPPassManager needs LoopInfo. 
+  void getAnalysisUsage(AnalysisUsage &Info) const; 
+  
+  virtual const char *getPassName() const {
+    return "Loop Pass Manager";
+  }
+  
+  // Print passes managed by this manager
+  void dumpPassStructure(unsigned Offset) {
+    llvm::cerr << std::string(Offset*2, ' ') << "Loop Pass Manager\n";
+    for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
+      Pass *P = getContainedPass(Index);
+      P->dumpPassStructure(Offset + 1);
+      dumpLastUses(P, Offset+1);
+    }
+  }
+  
+  Pass *getContainedPass(unsigned N) {
+    assert ( N < PassVector.size() && "Pass number out of range!");
+    Pass *FP = static_cast<Pass *>(PassVector[N]);
+    return FP;
+  }
+
+  virtual PassManagerType getPassManagerType() const { 
+    return PMT_LoopPassManager; 
+  }
+
+public:
+  // Delete loop from the loop queue and loop nest (LoopInfo).
+  void deleteLoopFromQueue(Loop *L);
+  
+  // Inset loop into the loop nest(LoopInfo) and loop queue(LQ).
+  void insertLoop(Loop *L, Loop *ParentLoop);
+
+  // Reoptimize this loop. LPPassManager will re-insert this loop into the
+  // queue. This allows LoopPass to change loop nest for the loop. This
+  // utility may send LPPassManager into infinite loops so use caution.
+  void redoLoop(Loop *L);
+
+private:
+  /// verifyLoopInfo - Verify loop nest.
+  void verifyLoopInfo();
+
+private:
+  std::deque<Loop *> LQ;
+  bool skipThisLoop;
+  bool redoThisLoop;
+  LoopInfo *LI;
+  Loop *CurrentLoop;
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/MemoryDependenceAnalysis.h b/include/llvm/Analysis/MemoryDependenceAnalysis.h
new file mode 100644
index 0000000..014922e
--- /dev/null
+++ b/include/llvm/Analysis/MemoryDependenceAnalysis.h
@@ -0,0 +1,75 @@
+//===- llvm/Analysis/MemoryDependenceAnalysis.h - Memory Deps  --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the Owen Anderson and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines 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, caching interface to a common kind
+// of alias information query.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
+#define LLVM_ANALYSIS_MEMORY_DEPENDENCE_H
+
+#include "llvm/Pass.h"
+#include "llvm/Support/CallSite.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/Support/Compiler.h"
+#include <map>
+
+namespace llvm {
+
+class Function;
+class FunctionPass;
+class Instruction;
+
+class MemoryDependenceAnalysis : public FunctionPass {
+  private:
+    
+    DenseMap<Instruction*, std::pair<Instruction*, bool> > depGraphLocal;
+    std::multimap<Instruction*, Instruction*> reverseDep;
+  
+    Instruction* getCallSiteDependency(CallSite C, Instruction* start,
+                                       bool local = true);
+  public:
+    
+    static Instruction* NonLocal;
+    static Instruction* None;
+    
+    static char ID; // Class identification, replacement for typeinfo
+    MemoryDependenceAnalysis() : FunctionPass((intptr_t)&ID) {}
+
+    /// Pass Implementation stuff.  This doesn't do any analysis.
+    ///
+    bool runOnFunction(Function &) {return false; }
+    
+    /// Clean up memory in between runs
+    void releaseMemory() {
+      depGraphLocal.clear();
+      reverseDep.clear();
+    }
+
+    /// 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, starting with start.
+    Instruction* getDependency(Instruction* query, Instruction* start = 0,
+                               bool local = true);
+    
+    /// removeInstruction - Remove an instruction from the dependence analysis,
+    /// updating the dependence of instructions that previously depended on it.
+    void removeInstruction(Instruction* rem);
+  };
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h
new file mode 100644
index 0000000..854128e
--- /dev/null
+++ b/include/llvm/Analysis/Passes.h
@@ -0,0 +1,117 @@
+//===-- llvm/Analysis/Passes.h - Constructors for analyses ------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This header file defines prototypes for accessor functions that expose passes
+// in the analysis libraries.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_PASSES_H
+#define LLVM_ANALYSIS_PASSES_H
+
+namespace llvm {
+  class FunctionPass;
+  class ImmutablePass;
+  class ModulePass;
+  class Pass;
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createGlobalsModRefPass - This pass provides alias and mod/ref info for
+  // global values that do not have their addresses taken.
+  //
+  Pass *createGlobalsModRefPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createAliasDebugger - This pass helps debug clients of AA
+  //
+  Pass *createAliasDebugger();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createAliasAnalysisCounterPass - This pass counts alias queries and how the
+  // alias analysis implementation responds.
+  //
+  ModulePass *createAliasAnalysisCounterPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createAAEvalPass - This pass implements a simple N^2 alias analysis
+  // accuracy evaluator.
+  //
+  FunctionPass *createAAEvalPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createNoAAPass - This pass implements a "I don't know" alias analysis.
+  //
+  ImmutablePass *createNoAAPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createBasicAliasAnalysisPass - This pass implements the default alias
+  // analysis.
+  //
+  ImmutablePass *createBasicAliasAnalysisPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createAndersensPass - This pass implements Andersen's interprocedural alias
+  // analysis.
+  //
+  ModulePass *createAndersensPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createBasicVNPass - This pass walks SSA def-use chains to trivially
+  // identify lexically identical expressions.
+  //
+  ImmutablePass *createBasicVNPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createProfileLoaderPass - This pass loads information from a profile dump
+  // file.
+  //
+  ModulePass *createProfileLoaderPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createNoProfileInfoPass - This pass implements the default "no profile".
+  //
+  ImmutablePass *createNoProfileInfoPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createDSAAPass - This pass implements simple context sensitive alias
+  // analysis.
+  //
+  ModulePass *createDSAAPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createDSOptPass - This pass uses DSA to do a series of simple
+  // optimizations.
+  //
+  ModulePass *createDSOptPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createSteensgaardPass - This pass uses the data structure graphs to do a
+  // simple context insensitive alias analysis.
+  //
+  ModulePass *createSteensgaardPass();
+  
+  // Minor pass prototypes, allowing us to expose them through bugpoint and
+  // analyze.
+  FunctionPass *createInstCountPass();
+}
+
+#endif
diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h
new file mode 100644
index 0000000..091925e
--- /dev/null
+++ b/include/llvm/Analysis/PostDominators.h
@@ -0,0 +1,86 @@
+//=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file exposes interfaces to post dominance information.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_POST_DOMINATORS_H
+#define LLVM_ANALYSIS_POST_DOMINATORS_H
+
+#include "llvm/Analysis/Dominators.h"
+
+namespace llvm {
+
+/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
+/// compute the a post-dominator tree.
+///
+struct PostDominatorTree : public DominatorTreeBase {
+  static char ID; // Pass identification, replacement for typeid
+
+  PostDominatorTree() : 
+    DominatorTreeBase((intptr_t)&ID, true) {}
+
+  virtual bool runOnFunction(Function &F) {
+    reset();     // Reset from the last time we were run...
+    calculate(F);
+    return false;
+  }
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+  }
+private:
+  void calculate(Function &F);
+  DomTreeNode *getNodeForBlock(BasicBlock *BB);
+  unsigned DFSPass(BasicBlock *V, InfoRec &VInfo,unsigned N);
+  void Compress(BasicBlock *V, InfoRec &VInfo);
+  BasicBlock *Eval(BasicBlock *V);
+  void Link(BasicBlock *V, BasicBlock *W, InfoRec &WInfo);
+
+  inline BasicBlock *getIDom(BasicBlock *BB) const {
+    std::map<BasicBlock*, BasicBlock*>::const_iterator I = IDoms.find(BB);
+    return I != IDoms.end() ? I->second : 0;
+  }
+};
+
+
+/// PostDominanceFrontier Class - Concrete subclass of DominanceFrontier that is
+/// used to compute the a post-dominance frontier.
+///
+struct PostDominanceFrontier : public DominanceFrontierBase {
+  static char ID;
+  PostDominanceFrontier() 
+    : DominanceFrontierBase((intptr_t) &ID, true) {}
+
+  virtual bool runOnFunction(Function &) {
+    Frontiers.clear();
+    PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
+    Roots = DT.getRoots();
+    if (const DomTreeNode *Root = DT.getRootNode())
+      calculate(DT, Root);
+    return false;
+  }
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.setPreservesAll();
+    AU.addRequired<PostDominatorTree>();
+  }
+
+private:
+  const DomSetType &calculate(const PostDominatorTree &DT,
+                              const DomTreeNode *Node);
+};
+
+} // End llvm namespace
+
+// Make sure that any clients of this file link in PostDominators.cpp
+FORCE_DEFINING_FILE_TO_BE_LINKED(PostDominanceFrontier)
+
+#endif
diff --git a/include/llvm/Analysis/ProfileInfo.h b/include/llvm/Analysis/ProfileInfo.h
new file mode 100644
index 0000000..74e3bc2
--- /dev/null
+++ b/include/llvm/Analysis/ProfileInfo.h
@@ -0,0 +1,67 @@
+//===- llvm/Analysis/ProfileInfo.h - Profile Info Interface -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the generic ProfileInfo interface, which is used as the
+// common interface used by all clients of profiling information, and
+// implemented either by making static guestimations, or by actually reading in
+// profiling information gathered by running the program.
+//
+// Note that to be useful, all profile-based optimizations should preserve
+// ProfileInfo, which requires that they notify it when changes to the CFG are
+// made.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_PROFILEINFO_H
+#define LLVM_ANALYSIS_PROFILEINFO_H
+
+#include <string>
+#include <map>
+
+namespace llvm {
+  class BasicBlock;
+  class Pass;
+
+  /// ProfileInfo Class - This class holds and maintains edge profiling
+  /// information for some unit of code.
+  class ProfileInfo {
+  protected:
+    // EdgeCounts - Count the number of times a transition between two blocks is
+    // executed.  As a special case, we also hold an edge from the null
+    // BasicBlock to the entry block to indicate how many times the function was
+    // entered.
+    std::map<std::pair<BasicBlock*, BasicBlock*>, unsigned> EdgeCounts;
+  public:
+    static char ID; // Class identification, replacement for typeinfo
+    virtual ~ProfileInfo();  // We want to be subclassed
+
+    //===------------------------------------------------------------------===//
+    /// Profile Information Queries
+    ///
+    unsigned getExecutionCount(BasicBlock *BB) const;
+
+    unsigned getEdgeWeight(BasicBlock *Src, BasicBlock *Dest) const {
+      std::map<std::pair<BasicBlock*, BasicBlock*>, unsigned>::const_iterator I=
+        EdgeCounts.find(std::make_pair(Src, Dest));
+      return I != EdgeCounts.end() ? I->second : 0;
+    }
+
+    //===------------------------------------------------------------------===//
+    /// Analysis Update Methods
+    ///
+
+  };
+
+  /// createProfileLoaderPass - This function returns a Pass that loads the
+  /// profiling information for the module from the specified filename, making
+  /// it available to the optimizers.
+  Pass *createProfileLoaderPass(const std::string &Filename);
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/ProfileInfoLoader.h b/include/llvm/Analysis/ProfileInfoLoader.h
new file mode 100644
index 0000000..6c3c41d
--- /dev/null
+++ b/include/llvm/Analysis/ProfileInfoLoader.h
@@ -0,0 +1,89 @@
+//===- ProfileInfoLoader.h - Load & convert profile information -*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The ProfileInfoLoader class is used to load and represent profiling
+// information read in from the dump file.  If conversions between formats are
+// needed, it can also do this.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_PROFILEINFOLOADER_H
+#define LLVM_ANALYSIS_PROFILEINFOLOADER_H
+
+#include <vector>
+#include <string>
+#include <utility>
+
+namespace llvm {
+
+class Module;
+class Function;
+class BasicBlock;
+
+class ProfileInfoLoader {
+  Module &M;
+  std::vector<std::string> CommandLines;
+  std::vector<unsigned>    FunctionCounts;
+  std::vector<unsigned>    BlockCounts;
+  std::vector<unsigned>    EdgeCounts;
+  std::vector<unsigned>    BBTrace;
+public:
+  // ProfileInfoLoader ctor - Read the specified profiling data file, exiting
+  // the program if the file is invalid or broken.
+  ProfileInfoLoader(const char *ToolName, const std::string &Filename,
+                    Module &M);
+
+  unsigned getNumExecutions() const { return CommandLines.size(); }
+  const std::string &getExecution(unsigned i) const { return CommandLines[i]; }
+
+  // getFunctionCounts - This method is used by consumers of function counting
+  // information.  If we do not directly have function count information, we
+  // compute it from other, more refined, types of profile information.
+  //
+  void getFunctionCounts(std::vector<std::pair<Function*, unsigned> > &Counts);
+
+  // hasAccurateBlockCounts - Return true if we can synthesize accurate block
+  // frequency information from whatever we have.
+  //
+  bool hasAccurateBlockCounts() const {
+    return !BlockCounts.empty() || !EdgeCounts.empty();
+  }
+
+  // hasAccurateEdgeCounts - Return true if we can synthesize accurate edge
+  // frequency information from whatever we have.
+  //
+  bool hasAccurateEdgeCounts() const {
+    return !EdgeCounts.empty();
+  }
+
+  // getBlockCounts - This method is used by consumers of block counting
+  // information.  If we do not directly have block count information, we
+  // compute it from other, more refined, types of profile information.
+  //
+  void getBlockCounts(std::vector<std::pair<BasicBlock*, unsigned> > &Counts);
+
+  // getEdgeCounts - This method is used by consumers of edge counting
+  // information.  If we do not directly have edge count information, we compute
+  // it from other, more refined, types of profile information.
+  //
+  // Edges are represented as a pair, where the first element is the basic block
+  // and the second element is the successor number.
+  //
+  typedef std::pair<BasicBlock*, unsigned> Edge;
+  void getEdgeCounts(std::vector<std::pair<Edge, unsigned> > &Counts);
+
+  // getBBTrace - This method is used by consumers of basic-block trace
+  // information.
+  //
+  void getBBTrace(std::vector<BasicBlock *> &Trace);
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/ProfileInfoTypes.h b/include/llvm/Analysis/ProfileInfoTypes.h
new file mode 100644
index 0000000..c662c3c
--- /dev/null
+++ b/include/llvm/Analysis/ProfileInfoTypes.h
@@ -0,0 +1,28 @@
+/*===-- ProfileInfoTypes.h - Profiling info shared constants ------*- C -*-===*\
+|*
+|*                     The LLVM Compiler Infrastructure
+|*
+|* This file was developed by the LLVM research group and is distributed under
+|* the University of Illinois Open Source License. See LICENSE.TXT for details.
+|*
+|*===----------------------------------------------------------------------===*|
+|*
+|* This file defines constants shared by the various different profiling
+|* runtime libraries and the LLVM C++ profile info loader. It must be a
+|* C header because, at present, the profiling runtimes are written in C.
+|*
+\*===----------------------------------------------------------------------===*/
+
+#ifndef LLVM_ANALYSIS_PROFILEINFOTYPES_H
+#define LLVM_ANALYSIS_PROFILEINFOTYPES_H
+
+enum ProfilingType {
+  ArgumentInfo  = 1,   /* The command line argument block */
+  FunctionInfo  = 2,   /* Function profiling information  */
+  BlockInfo     = 3,   /* Block profiling information     */
+  EdgeInfo      = 4,   /* Edge profiling information      */
+  PathInfo      = 5,   /* Path profiling information      */
+  BBTraceInfo   = 6    /* Basic block trace information   */
+};
+
+#endif /* LLVM_ANALYSIS_PROFILEINFOTYPES_H */
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
new file mode 100644
index 0000000..b6a58fe
--- /dev/null
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -0,0 +1,250 @@
+//===- llvm/Analysis/ScalarEvolution.h - Scalar Evolution -------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// The ScalarEvolution class is an LLVM pass which can be used to analyze and
+// catagorize scalar expressions in loops.  It specializes in recognizing
+// general induction variables, representing them with the abstract and opaque
+// SCEV class.  Given this analysis, trip counts of loops and other important
+// properties can be obtained.
+//
+// This analysis is primarily useful for induction variable substitution and
+// strength reduction.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_H
+#define LLVM_ANALYSIS_SCALAREVOLUTION_H
+
+#include "llvm/Pass.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/Streams.h"
+#include <set>
+
+namespace llvm {
+  class Instruction;
+  class Type;
+  class ConstantRange;
+  class Loop;
+  class LoopInfo;
+  class SCEVHandle;
+
+  /// SCEV - This class represent an analyzed expression in the program.  These
+  /// are reference counted opaque objects that the client is not allowed to
+  /// do much with directly.
+  ///
+  class SCEV {
+    const unsigned SCEVType;      // The SCEV baseclass this node corresponds to
+    mutable unsigned RefCount;
+
+    friend class SCEVHandle;
+    void addRef() const { ++RefCount; }
+    void dropRef() const {
+      if (--RefCount == 0)
+        delete this;
+    }
+
+    SCEV(const SCEV &);            // DO NOT IMPLEMENT
+    void operator=(const SCEV &);  // DO NOT IMPLEMENT
+  protected:
+    virtual ~SCEV();
+  public:
+    explicit SCEV(unsigned SCEVTy) : SCEVType(SCEVTy), RefCount(0) {}
+
+    /// getNegativeSCEV - Return the SCEV object corresponding to -V.
+    ///
+    static SCEVHandle getNegativeSCEV(const SCEVHandle &V);
+
+    /// getMinusSCEV - Return LHS-RHS.
+    ///
+    static SCEVHandle getMinusSCEV(const SCEVHandle &LHS,
+                                   const SCEVHandle &RHS);
+
+
+    unsigned getSCEVType() const { return SCEVType; }
+
+    /// getValueRange - Return the tightest constant bounds that this value is
+    /// known to have.  This method is only valid on integer SCEV objects.
+    virtual ConstantRange getValueRange() const;
+
+    /// isLoopInvariant - Return true if the value of this SCEV is unchanging in
+    /// the specified loop.
+    virtual bool isLoopInvariant(const Loop *L) const = 0;
+
+    /// hasComputableLoopEvolution - Return true if this SCEV changes value in a
+    /// known way in the specified loop.  This property being true implies that
+    /// the value is variant in the loop AND that we can emit an expression to
+    /// compute the value of the expression at any particular loop iteration.
+    virtual bool hasComputableLoopEvolution(const Loop *L) const = 0;
+
+    /// getType - Return the LLVM type of this SCEV expression.
+    ///
+    virtual const Type *getType() const = 0;
+
+    /// getBitWidth - Get the bit width of the type, if it has one, 0 otherwise.
+    /// 
+    uint32_t getBitWidth() const;
+
+    /// replaceSymbolicValuesWithConcrete - If this SCEV internally references
+    /// the symbolic value "Sym", construct and return a new SCEV that produces
+    /// the same value, but which uses the concrete value Conc instead of the
+    /// symbolic value.  If this SCEV does not use the symbolic value, it
+    /// returns itself.
+    virtual SCEVHandle
+    replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                      const SCEVHandle &Conc) const = 0;
+
+    /// print - Print out the internal representation of this scalar to the
+    /// specified stream.  This should really only be used for debugging
+    /// purposes.
+    virtual void print(std::ostream &OS) const = 0;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+    /// dump - This method is used for debugging.
+    ///
+    void dump() const;
+  };
+
+  inline std::ostream &operator<<(std::ostream &OS, const SCEV &S) {
+    S.print(OS);
+    return OS;
+  }
+
+  /// SCEVCouldNotCompute - An object of this class is returned by queries that
+  /// could not be answered.  For example, if you ask for the number of
+  /// iterations of a linked-list traversal loop, you will get one of these.
+  /// None of the standard SCEV operations are valid on this class, it is just a
+  /// marker.
+  struct SCEVCouldNotCompute : public SCEV {
+    SCEVCouldNotCompute();
+
+    // None of these methods are valid for this object.
+    virtual bool isLoopInvariant(const Loop *L) const;
+    virtual const Type *getType() const;
+    virtual bool hasComputableLoopEvolution(const Loop *L) const;
+    virtual void print(std::ostream &OS) const;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+    virtual SCEVHandle
+    replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                      const SCEVHandle &Conc) const;
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVCouldNotCompute *S) { return true; }
+    static bool classof(const SCEV *S);
+  };
+
+  /// SCEVHandle - This class is used to maintain the SCEV object's refcounts,
+  /// freeing the objects when the last reference is dropped.
+  class SCEVHandle {
+    SCEV *S;
+    SCEVHandle();  // DO NOT IMPLEMENT
+  public:
+    SCEVHandle(const SCEV *s) : S(const_cast<SCEV*>(s)) {
+      assert(S && "Cannot create a handle to a null SCEV!");
+      S->addRef();
+    }
+    SCEVHandle(const SCEVHandle &RHS) : S(RHS.S) {
+      S->addRef();
+    }
+    ~SCEVHandle() { S->dropRef(); }
+
+    operator SCEV*() const { return S; }
+
+    SCEV &operator*() const { return *S; }
+    SCEV *operator->() const { return S; }
+
+    bool operator==(SCEV *RHS) const { return S == RHS; }
+    bool operator!=(SCEV *RHS) const { return S != RHS; }
+
+    const SCEVHandle &operator=(SCEV *RHS) {
+      if (S != RHS) {
+        S->dropRef();
+        S = RHS;
+        S->addRef();
+      }
+      return *this;
+    }
+
+    const SCEVHandle &operator=(const SCEVHandle &RHS) {
+      if (S != RHS.S) {
+        S->dropRef();
+        S = RHS.S;
+        S->addRef();
+      }
+      return *this;
+    }
+  };
+
+  template<typename From> struct simplify_type;
+  template<> struct simplify_type<const SCEVHandle> {
+    typedef SCEV* SimpleType;
+    static SimpleType getSimplifiedValue(const SCEVHandle &Node) {
+      return Node;
+    }
+  };
+  template<> struct simplify_type<SCEVHandle>
+    : public simplify_type<const SCEVHandle> {};
+
+  /// ScalarEvolution - This class is the main scalar evolution driver.  Because
+  /// client code (intentionally) can't do much with the SCEV objects directly,
+  /// they must ask this class for services.
+  ///
+  class ScalarEvolution : public FunctionPass {
+    void *Impl;    // ScalarEvolution uses the pimpl pattern
+  public:
+    static char ID; // Pass identification, replacement for typeid
+    ScalarEvolution() : FunctionPass((intptr_t)&ID), Impl(0) {}
+
+    /// getSCEV - Return a SCEV expression handle for the full generality of the
+    /// specified expression.
+    SCEVHandle getSCEV(Value *V) const;
+
+    /// hasSCEV - Return true if the SCEV for this value has already been
+    /// computed.
+    bool hasSCEV(Value *V) const;
+
+    /// setSCEV - Insert the specified SCEV into the map of current SCEVs for
+    /// the specified value.
+    void setSCEV(Value *V, const SCEVHandle &H);
+
+    /// getSCEVAtScope - Return a SCEV expression handle for the specified value
+    /// at the specified scope in the program.  The L value specifies a loop
+    /// nest to evaluate the expression at, where null is the top-level or a
+    /// specified loop is immediately inside of the loop.
+    ///
+    /// This method can be used to compute the exit value for a variable defined
+    /// in a loop by querying what the value will hold in the parent loop.
+    ///
+    /// If this value is not computable at this scope, a SCEVCouldNotCompute
+    /// object is returned.
+    SCEVHandle getSCEVAtScope(Value *V, const Loop *L) const;
+
+    /// getIterationCount - If the specified loop has a predictable iteration
+    /// count, return it, otherwise return a SCEVCouldNotCompute object.
+    SCEVHandle getIterationCount(const Loop *L) const;
+
+    /// hasLoopInvariantIterationCount - Return true if the specified loop has
+    /// an analyzable loop-invariant iteration count.
+    bool hasLoopInvariantIterationCount(const Loop *L) const;
+
+    /// deleteValueFromRecords - This method should be called by the
+    /// client before it removes a Value from the program, to make sure
+    /// that no dangling references are left around.
+    void deleteValueFromRecords(Value *V) const;
+
+    virtual bool runOnFunction(Function &F);
+    virtual void releaseMemory();
+    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+    virtual void print(std::ostream &OS, const Module* = 0) const;
+    void print(std::ostream *OS, const Module* M = 0) const {
+      if (OS) print(*OS, M);
+    }
+  };
+}
+
+#endif
diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
new file mode 100644
index 0000000..a5cc713
--- /dev/null
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -0,0 +1,153 @@
+//===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the classes used to generate code from scalar expressions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H
+#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H
+
+#include "llvm/BasicBlock.h"
+#include "llvm/Constants.h"
+#include "llvm/Instructions.h"
+#include "llvm/Type.h"
+#include "llvm/Analysis/ScalarEvolution.h"
+#include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Support/CFG.h"
+
+namespace llvm {
+  /// SCEVExpander - This class uses information about analyze scalars to
+  /// rewrite expressions in canonical form.
+  ///
+  /// Clients should create an instance of this class when rewriting is needed,
+  /// and destroy it when finished to allow the release of the associated 
+  /// memory.
+  struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
+    ScalarEvolution &SE;
+    LoopInfo &LI;
+    std::map<SCEVHandle, Value*> InsertedExpressions;
+    std::set<Instruction*> InsertedInstructions;
+
+    Instruction *InsertPt;
+
+    friend struct SCEVVisitor<SCEVExpander, Value*>;
+  public:
+    SCEVExpander(ScalarEvolution &se, LoopInfo &li) : SE(se), LI(li) {}
+
+    LoopInfo &getLoopInfo() const { return LI; }
+
+    /// clear - Erase the contents of the InsertedExpressions map so that users
+    /// trying to expand the same expression into multiple BasicBlocks or
+    /// different places within the same BasicBlock can do so.
+    void clear() { InsertedExpressions.clear(); }
+
+    /// 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 InsertedInstructions.count(I);
+    }
+
+    /// getOrInsertCanonicalInductionVariable - This method returns the
+    /// canonical induction variable of the specified type for the specified
+    /// loop (inserting one if there is none).  A canonical induction variable
+    /// starts at zero and steps by one on each iteration.
+    Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty){
+      assert(Ty->isInteger() && "Can only insert integer induction variables!");
+      SCEVHandle H = SCEVAddRecExpr::get(SCEVUnknown::getIntegerSCEV(0, Ty),
+                                         SCEVUnknown::getIntegerSCEV(1, Ty), L);
+      return expand(H);
+    }
+
+    /// addInsertedValue - Remember the specified instruction as being the
+    /// canonical form for the specified SCEV.
+    void addInsertedValue(Instruction *I, SCEV *S) {
+      InsertedExpressions[S] = (Value*)I;
+      InsertedInstructions.insert(I);
+    }
+
+    Instruction *getInsertionPoint() const { return InsertPt; }
+    
+    /// expandCodeFor - Insert code to directly compute the specified SCEV
+    /// expression into the program.  The inserted code is inserted into the
+    /// specified block.
+    Value *expandCodeFor(SCEVHandle SH, Instruction *IP) {
+      // Expand the code for this SCEV.
+      this->InsertPt = IP;
+      return expand(SH);
+    }
+
+    /// InsertCastOfTo - Insert a cast of V to the specified type, doing what
+    /// we can to share the casts.
+    static Value *InsertCastOfTo(Instruction::CastOps opcode, Value *V, 
+                                 const Type *Ty);
+    /// InsertBinop - Insert the specified binary operator, doing a small amount
+    /// of work to avoid inserting an obviously redundant operation.
+    static Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
+                              Value *RHS, Instruction *&InsertPt);
+  protected:
+    Value *expand(SCEV *S) {
+      // Check to see if we already expanded this.
+      std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S);
+      if (I != InsertedExpressions.end())
+        return I->second;
+
+      Value *V = visit(S);
+      InsertedExpressions[S] = V;
+      return V;
+    }
+
+    Value *visitConstant(SCEVConstant *S) {
+      return S->getValue();
+    }
+
+    Value *visitTruncateExpr(SCEVTruncateExpr *S) {
+      Value *V = expand(S->getOperand());
+      return CastInst::createTruncOrBitCast(V, S->getType(), "tmp.", InsertPt);
+    }
+
+    Value *visitZeroExtendExpr(SCEVZeroExtendExpr *S) {
+      Value *V = expand(S->getOperand());
+      return CastInst::createZExtOrBitCast(V, S->getType(), "tmp.", InsertPt);
+    }
+
+    Value *visitSignExtendExpr(SCEVSignExtendExpr *S) {
+      Value *V = expand(S->getOperand());
+      return CastInst::createSExtOrBitCast(V, S->getType(), "tmp.", InsertPt);
+    }
+
+    Value *visitAddExpr(SCEVAddExpr *S) {
+      Value *V = expand(S->getOperand(S->getNumOperands()-1));
+
+      // Emit a bunch of add instructions
+      for (int i = S->getNumOperands()-2; i >= 0; --i)
+        V = InsertBinop(Instruction::Add, V, expand(S->getOperand(i)),
+                        InsertPt);
+      return V;
+    }
+
+    Value *visitMulExpr(SCEVMulExpr *S);
+
+    Value *visitSDivExpr(SCEVSDivExpr *S) {
+      Value *LHS = expand(S->getLHS());
+      Value *RHS = expand(S->getRHS());
+      return InsertBinop(Instruction::SDiv, LHS, RHS, InsertPt);
+    }
+
+    Value *visitAddRecExpr(SCEVAddRecExpr *S);
+
+    Value *visitUnknown(SCEVUnknown *S) {
+      return S->getValue();
+    }
+  };
+}
+
+#endif
+
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
new file mode 100644
index 0000000..af1656e
--- /dev/null
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -0,0 +1,580 @@
+//===- llvm/Analysis/ScalarEvolutionExpressions.h - SCEV Exprs --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the classes used to represent and build scalar expressions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
+#define LLVM_ANALYSIS_SCALAREVOLUTION_EXPRESSIONS_H
+
+#include "llvm/Analysis/ScalarEvolution.h"
+
+namespace llvm {
+  class ConstantInt;
+  class ConstantRange;
+  class APInt;
+
+  enum SCEVTypes {
+    // These should be ordered in terms of increasing complexity to make the
+    // folders simpler.
+    scConstant, scTruncate, scZeroExtend, scSignExtend, scAddExpr, scMulExpr,
+    scSDivExpr, scAddRecExpr, scUnknown, scCouldNotCompute
+  };
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVConstant - This class represents a constant integer value.
+  ///
+  class SCEVConstant : public SCEV {
+    ConstantInt *V;
+    explicit SCEVConstant(ConstantInt *v) : SCEV(scConstant), V(v) {}
+
+    virtual ~SCEVConstant();
+  public:
+    /// get method - This just gets and returns a new SCEVConstant object.
+    ///
+    static SCEVHandle get(ConstantInt *V);
+    static SCEVHandle get(const APInt& Val);
+
+    ConstantInt *getValue() const { return V; }
+
+    /// getValueRange - Return the tightest constant bounds that this value is
+    /// known to have.  This method is only valid on integer SCEV objects.
+    virtual ConstantRange getValueRange() const;
+
+    virtual bool isLoopInvariant(const Loop *L) const {
+      return true;
+    }
+
+    virtual bool hasComputableLoopEvolution(const Loop *L) const {
+      return false;  // Not loop variant
+    }
+
+    virtual const Type *getType() const;
+
+    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                                 const SCEVHandle &Conc) const {
+      return this;
+    }
+
+    virtual void print(std::ostream &OS) const;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVConstant *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scConstant;
+    }
+  };
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVTruncateExpr - This class represents a truncation of an integer value
+  /// to a smaller integer value.
+  ///
+  class SCEVTruncateExpr : public SCEV {
+    SCEVHandle Op;
+    const Type *Ty;
+    SCEVTruncateExpr(const SCEVHandle &op, const Type *ty);
+    virtual ~SCEVTruncateExpr();
+  public:
+    /// get method - This just gets and returns a new SCEVTruncate object
+    ///
+    static SCEVHandle get(const SCEVHandle &Op, const Type *Ty);
+
+    const SCEVHandle &getOperand() const { return Op; }
+    virtual const Type *getType() const { return Ty; }
+
+    virtual bool isLoopInvariant(const Loop *L) const {
+      return Op->isLoopInvariant(L);
+    }
+
+    virtual bool hasComputableLoopEvolution(const Loop *L) const {
+      return Op->hasComputableLoopEvolution(L);
+    }
+
+    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                                 const SCEVHandle &Conc) const {
+      SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc);
+      if (H == Op)
+        return this;
+      return get(H, Ty);
+    }
+
+    /// getValueRange - Return the tightest constant bounds that this value is
+    /// known to have.  This method is only valid on integer SCEV objects.
+    virtual ConstantRange getValueRange() const;
+
+    virtual void print(std::ostream &OS) const;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVTruncateExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scTruncate;
+    }
+  };
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVZeroExtendExpr - This class represents a zero extension of a small
+  /// integer value to a larger integer value.
+  ///
+  class SCEVZeroExtendExpr : public SCEV {
+    SCEVHandle Op;
+    const Type *Ty;
+    SCEVZeroExtendExpr(const SCEVHandle &op, const Type *ty);
+    virtual ~SCEVZeroExtendExpr();
+  public:
+    /// get method - This just gets and returns a new SCEVZeroExtend object
+    ///
+    static SCEVHandle get(const SCEVHandle &Op, const Type *Ty);
+
+    const SCEVHandle &getOperand() const { return Op; }
+    virtual const Type *getType() const { return Ty; }
+
+    virtual bool isLoopInvariant(const Loop *L) const {
+      return Op->isLoopInvariant(L);
+    }
+
+    virtual bool hasComputableLoopEvolution(const Loop *L) const {
+      return Op->hasComputableLoopEvolution(L);
+    }
+
+    /// getValueRange - Return the tightest constant bounds that this value is
+    /// known to have.  This method is only valid on integer SCEV objects.
+    virtual ConstantRange getValueRange() const;
+
+    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                                 const SCEVHandle &Conc) const {
+      SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc);
+      if (H == Op)
+        return this;
+      return get(H, Ty);
+    }
+
+    virtual void print(std::ostream &OS) const;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVZeroExtendExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scZeroExtend;
+    }
+  };
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVSignExtendExpr - This class represents a sign extension of a small
+  /// integer value to a larger integer value.
+  ///
+  class SCEVSignExtendExpr : public SCEV {
+    SCEVHandle Op;
+    const Type *Ty;
+    SCEVSignExtendExpr(const SCEVHandle &op, const Type *ty);
+    virtual ~SCEVSignExtendExpr();
+  public:
+    /// get method - This just gets and returns a new SCEVSignExtend object
+    ///
+    static SCEVHandle get(const SCEVHandle &Op, const Type *Ty);
+
+    const SCEVHandle &getOperand() const { return Op; }
+    virtual const Type *getType() const { return Ty; }
+
+    virtual bool isLoopInvariant(const Loop *L) const {
+      return Op->isLoopInvariant(L);
+    }
+
+    virtual bool hasComputableLoopEvolution(const Loop *L) const {
+      return Op->hasComputableLoopEvolution(L);
+    }
+
+    /// getValueRange - Return the tightest constant bounds that this value is
+    /// known to have.  This method is only valid on integer SCEV objects.
+    virtual ConstantRange getValueRange() const;
+
+    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                                 const SCEVHandle &Conc) const {
+      SCEVHandle H = Op->replaceSymbolicValuesWithConcrete(Sym, Conc);
+      if (H == Op)
+        return this;
+      return get(H, Ty);
+    }
+
+    virtual void print(std::ostream &OS) const;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVSignExtendExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scSignExtend;
+    }
+  };
+
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVCommutativeExpr - This node is the base class for n'ary commutative
+  /// operators.
+  ///
+  class SCEVCommutativeExpr : public SCEV {
+    std::vector<SCEVHandle> Operands;
+
+  protected:
+    SCEVCommutativeExpr(enum SCEVTypes T, const std::vector<SCEVHandle> &ops)
+      : SCEV(T) {
+      Operands.reserve(ops.size());
+      Operands.insert(Operands.end(), ops.begin(), ops.end());
+    }
+    ~SCEVCommutativeExpr();
+
+  public:
+    unsigned getNumOperands() const { return Operands.size(); }
+    const SCEVHandle &getOperand(unsigned i) const {
+      assert(i < Operands.size() && "Operand index out of range!");
+      return Operands[i];
+    }
+
+    const std::vector<SCEVHandle> &getOperands() const { return Operands; }
+    typedef std::vector<SCEVHandle>::const_iterator op_iterator;
+    op_iterator op_begin() const { return Operands.begin(); }
+    op_iterator op_end() const { return Operands.end(); }
+
+
+    virtual bool isLoopInvariant(const Loop *L) const {
+      for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
+        if (!getOperand(i)->isLoopInvariant(L)) return false;
+      return true;
+    }
+
+    // hasComputableLoopEvolution - Commutative expressions have computable loop
+    // evolutions iff they have at least one operand that varies with the loop,
+    // but that all varying operands are computable.
+    virtual bool hasComputableLoopEvolution(const Loop *L) const {
+      bool HasVarying = false;
+      for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
+        if (!getOperand(i)->isLoopInvariant(L))
+          if (getOperand(i)->hasComputableLoopEvolution(L))
+            HasVarying = true;
+          else
+            return false;
+      return HasVarying;
+    }
+
+    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                                 const SCEVHandle &Conc) const;
+
+    virtual const char *getOperationStr() const = 0;
+
+    virtual const Type *getType() const { return getOperand(0)->getType(); }
+    virtual void print(std::ostream &OS) const;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVCommutativeExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scAddExpr ||
+             S->getSCEVType() == scMulExpr;
+    }
+  };
+
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVAddExpr - This node represents an addition of some number of SCEVs.
+  ///
+  class SCEVAddExpr : public SCEVCommutativeExpr {
+    SCEVAddExpr(const std::vector<SCEVHandle> &ops)
+      : SCEVCommutativeExpr(scAddExpr, ops) {
+    }
+
+  public:
+    static SCEVHandle get(std::vector<SCEVHandle> &Ops);
+
+    static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+      std::vector<SCEVHandle> Ops;
+      Ops.push_back(LHS);
+      Ops.push_back(RHS);
+      return get(Ops);
+    }
+
+    static SCEVHandle get(const SCEVHandle &Op0, const SCEVHandle &Op1,
+                          const SCEVHandle &Op2) {
+      std::vector<SCEVHandle> Ops;
+      Ops.push_back(Op0);
+      Ops.push_back(Op1);
+      Ops.push_back(Op2);
+      return get(Ops);
+    }
+
+    virtual const char *getOperationStr() const { return " + "; }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVAddExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scAddExpr;
+    }
+  };
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVMulExpr - This node represents multiplication of some number of SCEVs.
+  ///
+  class SCEVMulExpr : public SCEVCommutativeExpr {
+    SCEVMulExpr(const std::vector<SCEVHandle> &ops)
+      : SCEVCommutativeExpr(scMulExpr, ops) {
+    }
+
+  public:
+    static SCEVHandle get(std::vector<SCEVHandle> &Ops);
+
+    static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS) {
+      std::vector<SCEVHandle> Ops;
+      Ops.push_back(LHS);
+      Ops.push_back(RHS);
+      return get(Ops);
+    }
+
+    virtual const char *getOperationStr() const { return " * "; }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVMulExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scMulExpr;
+    }
+  };
+
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVSDivExpr - This class represents a binary signed division operation.
+  ///
+  class SCEVSDivExpr : public SCEV {
+    SCEVHandle LHS, RHS;
+    SCEVSDivExpr(const SCEVHandle &lhs, const SCEVHandle &rhs)
+      : SCEV(scSDivExpr), LHS(lhs), RHS(rhs) {}
+
+    virtual ~SCEVSDivExpr();
+  public:
+    /// get method - This just gets and returns a new SCEVSDiv object.
+    ///
+    static SCEVHandle get(const SCEVHandle &LHS, const SCEVHandle &RHS);
+
+    const SCEVHandle &getLHS() const { return LHS; }
+    const SCEVHandle &getRHS() const { return RHS; }
+
+    virtual bool isLoopInvariant(const Loop *L) const {
+      return LHS->isLoopInvariant(L) && RHS->isLoopInvariant(L);
+    }
+
+    virtual bool hasComputableLoopEvolution(const Loop *L) const {
+      return LHS->hasComputableLoopEvolution(L) &&
+             RHS->hasComputableLoopEvolution(L);
+    }
+
+    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                                 const SCEVHandle &Conc) const {
+      SCEVHandle L = LHS->replaceSymbolicValuesWithConcrete(Sym, Conc);
+      SCEVHandle R = RHS->replaceSymbolicValuesWithConcrete(Sym, Conc);
+      if (L == LHS && R == RHS)
+        return this;
+      else
+        return get(L, R);
+    }
+
+
+    virtual const Type *getType() const;
+
+    void print(std::ostream &OS) const;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVSDivExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scSDivExpr;
+    }
+  };
+
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVAddRecExpr - This node represents a polynomial recurrence on the trip
+  /// count of the specified loop.
+  ///
+  /// All operands of an AddRec are required to be loop invariant.
+  ///
+  class SCEVAddRecExpr : public SCEV {
+    std::vector<SCEVHandle> Operands;
+    const Loop *L;
+
+    SCEVAddRecExpr(const std::vector<SCEVHandle> &ops, const Loop *l)
+      : SCEV(scAddRecExpr), Operands(ops), L(l) {
+      for (unsigned i = 0, e = Operands.size(); i != e; ++i)
+        assert(Operands[i]->isLoopInvariant(l) &&
+               "Operands of AddRec must be loop-invariant!");
+    }
+    ~SCEVAddRecExpr();
+  public:
+    static SCEVHandle get(const SCEVHandle &Start, const SCEVHandle &Step,
+                          const Loop *);
+    static SCEVHandle get(std::vector<SCEVHandle> &Operands,
+                          const Loop *);
+    static SCEVHandle get(const std::vector<SCEVHandle> &Operands,
+                          const Loop *L) {
+      std::vector<SCEVHandle> NewOp(Operands);
+      return get(NewOp, L);
+    }
+
+    typedef std::vector<SCEVHandle>::const_iterator op_iterator;
+    op_iterator op_begin() const { return Operands.begin(); }
+    op_iterator op_end() const { return Operands.end(); }
+
+    unsigned getNumOperands() const { return Operands.size(); }
+    const SCEVHandle &getOperand(unsigned i) const { return Operands[i]; }
+    const SCEVHandle &getStart() const { return Operands[0]; }
+    const Loop *getLoop() const { return L; }
+
+
+    /// getStepRecurrence - This method constructs and returns the recurrence
+    /// indicating how much this expression steps by.  If this is a polynomial
+    /// of degree N, it returns a chrec of degree N-1.
+    SCEVHandle getStepRecurrence() const {
+      if (getNumOperands() == 2) return getOperand(1);
+      return SCEVAddRecExpr::get(std::vector<SCEVHandle>(op_begin()+1,op_end()),
+                                 getLoop());
+    }
+
+    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
+      if (L == QL) return true;
+      return false;
+    }
+
+    virtual bool isLoopInvariant(const Loop *QueryLoop) const;
+
+    virtual const Type *getType() const { return Operands[0]->getType(); }
+
+    /// isAffine - Return true if this is an affine AddRec (i.e., it represents
+    /// an expressions A+B*x where A and B are loop invariant values.
+    bool isAffine() const {
+      // We know that the start value is invariant.  This expression is thus
+      // affine iff the step is also invariant.
+      return getNumOperands() == 2;
+    }
+
+    /// isQuadratic - Return true if this is an quadratic AddRec (i.e., it
+    /// represents an expressions A+B*x+C*x^2 where A, B and C are loop
+    /// invariant values.  This corresponds to an addrec of the form {L,+,M,+,N}
+    bool isQuadratic() const {
+      return getNumOperands() == 3;
+    }
+
+    /// evaluateAtIteration - Return the value of this chain of recurrences at
+    /// the specified iteration number.
+    SCEVHandle evaluateAtIteration(SCEVHandle It) const;
+
+    /// getNumIterationsInRange - Return the number of iterations of this loop
+    /// that produce values in the specified constant range.  Another way of
+    /// looking at this is that it returns the first iteration number where the
+    /// value is not in the condition, thus computing the exit count.  If the
+    /// iteration count can't be computed, an instance of SCEVCouldNotCompute is
+    /// returned.
+    SCEVHandle getNumIterationsInRange(ConstantRange Range) const;
+
+    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                                 const SCEVHandle &Conc) const;
+
+    virtual void print(std::ostream &OS) const;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVAddRecExpr *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scAddRecExpr;
+    }
+  };
+
+  //===--------------------------------------------------------------------===//
+  /// SCEVUnknown - This means that we are dealing with an entirely unknown SCEV
+  /// value, and only represent it as it's LLVM Value.  This is the "bottom"
+  /// value for the analysis.
+  ///
+  class SCEVUnknown : public SCEV {
+    Value *V;
+    SCEVUnknown(Value *v) : SCEV(scUnknown), V(v) {}
+
+  protected:
+    ~SCEVUnknown();
+  public:
+    /// get method - For SCEVUnknown, this just gets and returns a new
+    /// SCEVUnknown.
+    static SCEVHandle get(Value *V);
+
+    /// getIntegerSCEV - Given an integer or FP type, create a constant for the
+    /// specified signed integer value and return a SCEV for the constant.
+    static SCEVHandle getIntegerSCEV(int Val, const Type *Ty);
+
+    Value *getValue() const { return V; }
+
+    virtual bool isLoopInvariant(const Loop *L) const;
+    virtual bool hasComputableLoopEvolution(const Loop *QL) const {
+      return false; // not computable
+    }
+
+    SCEVHandle replaceSymbolicValuesWithConcrete(const SCEVHandle &Sym,
+                                                 const SCEVHandle &Conc) const {
+      if (&*Sym == this) return Conc;
+      return this;
+    }
+
+    virtual const Type *getType() const;
+
+    virtual void print(std::ostream &OS) const;
+    void print(std::ostream *OS) const { if (OS) print(*OS); }
+
+    /// Methods for support type inquiry through isa, cast, and dyn_cast:
+    static inline bool classof(const SCEVUnknown *S) { return true; }
+    static inline bool classof(const SCEV *S) {
+      return S->getSCEVType() == scUnknown;
+    }
+  };
+
+  /// SCEVVisitor - This class defines a simple visitor class that may be used
+  /// for various SCEV analysis purposes.
+  template<typename SC, typename RetVal=void>
+  struct SCEVVisitor {
+    RetVal visit(SCEV *S) {
+      switch (S->getSCEVType()) {
+      case scConstant:
+        return ((SC*)this)->visitConstant((SCEVConstant*)S);
+      case scTruncate:
+        return ((SC*)this)->visitTruncateExpr((SCEVTruncateExpr*)S);
+      case scZeroExtend:
+        return ((SC*)this)->visitZeroExtendExpr((SCEVZeroExtendExpr*)S);
+      case scSignExtend:
+        return ((SC*)this)->visitSignExtendExpr((SCEVSignExtendExpr*)S);
+      case scAddExpr:
+        return ((SC*)this)->visitAddExpr((SCEVAddExpr*)S);
+      case scMulExpr:
+        return ((SC*)this)->visitMulExpr((SCEVMulExpr*)S);
+      case scSDivExpr:
+        return ((SC*)this)->visitSDivExpr((SCEVSDivExpr*)S);
+      case scAddRecExpr:
+        return ((SC*)this)->visitAddRecExpr((SCEVAddRecExpr*)S);
+      case scUnknown:
+        return ((SC*)this)->visitUnknown((SCEVUnknown*)S);
+      case scCouldNotCompute:
+        return ((SC*)this)->visitCouldNotCompute((SCEVCouldNotCompute*)S);
+      default:
+        assert(0 && "Unknown SCEV type!");
+        abort();
+      }
+    }
+
+    RetVal visitCouldNotCompute(SCEVCouldNotCompute *S) {
+      assert(0 && "Invalid use of SCEVCouldNotCompute!");
+      abort();
+      return RetVal();
+    }
+  };
+}
+
+#endif
+
diff --git a/include/llvm/Analysis/Trace.h b/include/llvm/Analysis/Trace.h
new file mode 100644
index 0000000..65aa593c8
--- /dev/null
+++ b/include/llvm/Analysis/Trace.h
@@ -0,0 +1,120 @@
+//===- llvm/Analysis/Trace.h - Represent one trace of LLVM code -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This class represents a single trace of LLVM basic blocks.  A trace is a
+// single entry, multiple exit, region of code that is often hot.  Trace-based
+// optimizations treat traces almost like they are a large, strange, basic
+// block: because the trace path is assumed to be hot, optimizations for the
+// fall-through path are made at the expense of the non-fall-through paths.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_TRACE_H
+#define LLVM_ANALYSIS_TRACE_H
+
+#include "llvm/Support/Streams.h"
+#include <vector>
+#include <cassert>
+
+namespace llvm {
+  class BasicBlock;
+  class Function;
+  class Module;
+
+class Trace {
+  typedef std::vector<BasicBlock *> BasicBlockListType;
+  BasicBlockListType BasicBlocks;
+
+public:
+  /// Trace ctor - Make a new trace from a vector of basic blocks,
+  /// residing in the function which is the parent of the first
+  /// basic block in the vector.
+  ///
+  Trace(const std::vector<BasicBlock *> &vBB) : BasicBlocks (vBB) {}
+
+  /// getEntryBasicBlock - Return the entry basic block (first block)
+  /// of the trace.
+  ///
+  BasicBlock *getEntryBasicBlock () const { return BasicBlocks[0]; }
+
+  /// operator[]/getBlock - Return basic block N in the trace.
+  ///
+  BasicBlock *operator[](unsigned i) const { return BasicBlocks[i]; }
+  BasicBlock *getBlock(unsigned i)   const { return BasicBlocks[i]; }
+
+  /// getFunction - Return this trace's parent function.
+  ///
+  Function *getFunction () const;
+
+  /// getModule - Return this Module that contains this trace's parent
+  /// function.
+  ///
+  Module *getModule () const;
+
+  /// getBlockIndex - Return the index of the specified basic block in the
+  /// trace, or -1 if it is not in the trace.
+  int getBlockIndex(const BasicBlock *X) const {
+    for (unsigned i = 0, e = BasicBlocks.size(); i != e; ++i)
+      if (BasicBlocks[i] == X)
+        return i;
+    return -1;
+  }
+
+  /// contains - Returns true if this trace contains the given basic
+  /// block.
+  ///
+  bool contains(const BasicBlock *X) const {
+    return getBlockIndex(X) != -1;
+  }
+
+  /// Returns true if B1 occurs before B2 in the trace, or if it is the same
+  /// block as B2..  Both blocks must be in the trace.
+  ///
+  bool dominates(const BasicBlock *B1, const BasicBlock *B2) const {
+    int B1Idx = getBlockIndex(B1), B2Idx = getBlockIndex(B2);
+    assert(B1Idx != -1 && B2Idx != -1 && "Block is not in the trace!");
+    return B1Idx <= B2Idx;
+  }
+
+  // BasicBlock iterators...
+  typedef BasicBlockListType::iterator iterator;
+  typedef BasicBlockListType::const_iterator const_iterator;
+  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+  typedef std::reverse_iterator<iterator> reverse_iterator;
+
+  iterator                begin()       { return BasicBlocks.begin(); }
+  const_iterator          begin() const { return BasicBlocks.begin(); }
+  iterator                end  ()       { return BasicBlocks.end();   }
+  const_iterator          end  () const { return BasicBlocks.end();   }
+
+  reverse_iterator       rbegin()       { return BasicBlocks.rbegin(); }
+  const_reverse_iterator rbegin() const { return BasicBlocks.rbegin(); }
+  reverse_iterator       rend  ()       { return BasicBlocks.rend();   }
+  const_reverse_iterator rend  () const { return BasicBlocks.rend();   }
+
+  unsigned                 size() const { return BasicBlocks.size(); }
+  bool                    empty() const { return BasicBlocks.empty(); }
+
+  iterator erase(iterator q)               { return BasicBlocks.erase (q); }
+  iterator erase(iterator q1, iterator q2) { return BasicBlocks.erase (q1, q2); }
+
+  /// print - Write trace to output stream.
+  ///
+  void print (std::ostream &O) const;
+  void print (std::ostream *O) const { if (O) print(*O); }
+
+  /// dump - Debugger convenience method; writes trace to standard error
+  /// output stream.
+  ///
+  void dump () const;
+};
+
+} // end namespace llvm
+
+#endif // TRACE_H
diff --git a/include/llvm/Analysis/ValueNumbering.h b/include/llvm/Analysis/ValueNumbering.h
new file mode 100644
index 0000000..64d528e
--- /dev/null
+++ b/include/llvm/Analysis/ValueNumbering.h
@@ -0,0 +1,74 @@
+//===- llvm/Analysis/ValueNumbering.h - Value #'ing Interface ---*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the abstract ValueNumbering interface, which is used as the
+// common interface used by all clients of value numbering information, and
+// implemented by all value numbering implementations.
+//
+// Implementations of this interface must implement the various virtual methods,
+// which automatically provides functionality for the entire suite of client
+// APIs.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_VALUE_NUMBERING_H
+#define LLVM_ANALYSIS_VALUE_NUMBERING_H
+
+#include <vector>
+#include "llvm/Pass.h"
+
+namespace llvm {
+
+class Value;
+class Instruction;
+
+struct ValueNumbering {
+  static char ID; // Class identification, replacement for typeinfo
+  virtual ~ValueNumbering();    // We want to be subclassed
+
+  /// getEqualNumberNodes - Return nodes with the same value number as the
+  /// specified Value.  This fills in the argument vector with any equal values.
+  ///
+  virtual void getEqualNumberNodes(Value *V1,
+                                   std::vector<Value*> &RetVals) const = 0;
+
+  ///===-------------------------------------------------------------------===//
+  /// Interfaces to update value numbering analysis information as the client
+  /// changes the program.
+  ///
+
+  /// deleteValue - This method should be called whenever an LLVM Value is
+  /// deleted from the program, for example when an instruction is found to be
+  /// redundant and is eliminated.
+  ///
+  virtual void deleteValue(Value *V) {}
+
+  /// copyValue - This method should be used whenever a preexisting value in the
+  /// program is copied or cloned, introducing a new value.  Note that analysis
+  /// implementations should tolerate clients that use this method to introduce
+  /// the same value multiple times: if the analysis already knows about a
+  /// value, it should ignore the request.
+  ///
+  virtual void copyValue(Value *From, Value *To) {}
+
+  /// replaceWithNewValue - This method is the obvious combination of the two
+  /// above, and it provided as a helper to simplify client code.
+  ///
+  void replaceWithNewValue(Value *Old, Value *New) {
+    copyValue(Old, New);
+    deleteValue(Old);
+  }
+};
+
+} // End llvm namespace
+
+// Force any file including this header to get the implementation as well
+FORCE_DEFINING_FILE_TO_BE_LINKED(BasicValueNumbering)
+
+#endif
diff --git a/include/llvm/Analysis/Verifier.h b/include/llvm/Analysis/Verifier.h
new file mode 100644
index 0000000..dd914a4
--- /dev/null
+++ b/include/llvm/Analysis/Verifier.h
@@ -0,0 +1,75 @@
+//===-- llvm/Analysis/Verifier.h - Module Verifier --------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the function verifier interface, that can be used for some
+// sanity checking of input to the system, and for checking that transformations
+// haven't done something bad.
+//
+// Note that this does not provide full 'java style' security and verifications,
+// instead it just tries to ensure that code is well formed.
+//
+// To see what specifically is checked, look at the top of Verifier.cpp
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_VERIFIER_H
+#define LLVM_ANALYSIS_VERIFIER_H
+
+#include <string>
+
+namespace llvm {
+
+class FunctionPass;
+class Module;
+class Function;
+
+/// @brief An enumeration to specify the action to be taken if errors found.
+///
+/// This enumeration is used in the functions below to indicate what should
+/// happen if the verifier finds errors. Each of the functions that uses
+/// this enumeration as an argument provides a default value for it. The
+/// actions are listed below.
+enum VerifierFailureAction {
+  AbortProcessAction,   ///< verifyModule will print to stderr and abort()
+  PrintMessageAction,   ///< verifyModule will print to stderr and return true
+  ReturnStatusAction    ///< verifyModule will just return true
+};
+
+/// @brief Create a verifier pass.
+///
+/// Check a module or function for validity.  When the pass is used, the
+/// action indicated by the \p action argument will be used if errors are
+/// found.
+FunctionPass *createVerifierPass(
+  VerifierFailureAction action = AbortProcessAction ///< Action to take
+);
+
+/// @brief Check a module for errors.
+///
+/// If there are no errors, the function returns false. If an error is found,
+/// the action taken depends on the \p action parameter.
+/// This should only be used for debugging, because it plays games with
+/// PassManagers and stuff.
+
+bool verifyModule(
+  const Module &M,  ///< The module to be verified
+  VerifierFailureAction action = AbortProcessAction, ///< Action to take
+  std::string *ErrorInfo = 0      ///< Information about failures.
+);
+
+// verifyFunction - Check a function for errors, useful for use when debugging a
+// pass.
+bool verifyFunction(
+  const Function &F,  ///< The function to be verified
+  VerifierFailureAction action = AbortProcessAction ///< Action to take
+);
+
+} // End llvm namespace
+
+#endif