Vendor import of llvm r114020 (from the release_28 branch):

http://llvm.org/svn/llvm-project/llvm/branches/release_28@114020 Approved by: rpaulo (mentor)
author: dim <dim@FreeBSD.org> 2010-09-17 15:48:55 +0000
committer: dim <dim@FreeBSD.org> 2010-09-17 15:48:55 +0000
commit: 5d5cc59cc77afe655b3707cb0e69e0827b444cad (patch)
tree: 36453626c792cccd91f783a38a169d610a6b9db9 /include/llvm/Analysis
parent: 786a18553586229ad99ecb5ecde8a9d914c45e27 (diff)
download: FreeBSD-src-5d5cc59cc77afe655b3707cb0e69e0827b444cad.zip
FreeBSD-src-5d5cc59cc77afe655b3707cb0e69e0827b444cad.tar.gz
23 files changed, 1258 insertions, 170 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h
index e611a35..ad68d48 100644
--- a/include/llvm/Analysis/AliasAnalysis.h
+++ b/include/llvm/Analysis/AliasAnalysis.h
@@ -18,12 +18,9 @@
 //
 // 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.
+// of an area is being queried, or UnknownSize if the size is not known.
+// Pointers that point to two completely different objects in memory never
+// alias, regardless of the value of the Size component.
 //
 //===----------------------------------------------------------------------===//
 
@@ -46,8 +43,11 @@ class AnalysisUsage;
 class AliasAnalysis {
 protected:
   const TargetData *TD;
+
+private:
   AliasAnalysis *AA;       // Previous Alias Analysis to chain to.
 
+protected:
   /// 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
@@ -64,6 +64,11 @@ public:
   AliasAnalysis() : TD(0), AA(0) {}
   virtual ~AliasAnalysis();  // We want to be subclassed
 
+  /// UnknownSize - This is a special value which can be used with the
+  /// size arguments in alias queries to indicate that the caller does not
+  /// know the sizes of the potential memory references.
+  static unsigned const UnknownSize = ~0u;
+
   /// getTargetData - Return a pointer to the current TargetData object, or
   /// null if no TargetData object is available.
   ///
@@ -84,6 +89,9 @@ public:
   ///     if (AA.alias(P1, P2)) { ... }
   /// to check to see if two pointers might alias.
   ///
+  /// See docs/AliasAnalysis.html for more information on the specific meanings
+  /// of these values.
+  ///
   enum AliasResult { NoAlias = 0, MayAlias = 1, MustAlias = 2 };
 
   /// alias - The main low level interface to the alias analysis implementation.
@@ -94,6 +102,11 @@ public:
   virtual AliasResult alias(const Value *V1, unsigned V1Size,
                             const Value *V2, unsigned V2Size);
 
+  /// alias - A convenience wrapper for the case where the sizes are unknown.
+  AliasResult alias(const Value *V1, const Value *V2) {
+    return alias(V1, UnknownSize, V2, UnknownSize);
+  }
+
   /// isNoAlias - A trivial helper function to check to see if the specified
   /// pointers are no-alias.
   bool isNoAlias(const Value *V1, unsigned V1Size,
@@ -130,17 +143,11 @@ public:
 
     // AccessesArguments - This function accesses function arguments in well
     // known (possibly volatile) ways, but does not access any other memory.
-    //
-    // Clients may use the Info parameter of getModRefBehavior to get specific
-    // information about how pointer arguments are used.
     AccessesArguments,
 
     // AccessesArgumentsAndGlobals - This function has accesses function
     // arguments and global variables well known (possibly volatile) ways, but
     // does not access any other memory.
-    //
-    // Clients may use the Info parameter of getModRefBehavior to get specific
-    // information about how pointer arguments are used.
     AccessesArgumentsAndGlobals,
 
     // OnlyReadsMemory - This function does not perform any non-local stores or
@@ -154,31 +161,17 @@ public:
     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;
-  };
-
   /// getModRefBehavior - Return the behavior when calling the given call site.
-  virtual ModRefBehavior getModRefBehavior(CallSite CS,
-                                   std::vector<PointerAccessInfo> *Info = 0);
+  virtual ModRefBehavior getModRefBehavior(ImmutableCallSite CS);
 
   /// getModRefBehavior - Return the behavior when calling the given function.
   /// For use when the call site is not known.
-  virtual ModRefBehavior getModRefBehavior(Function *F,
-                                   std::vector<PointerAccessInfo> *Info = 0);
+  virtual ModRefBehavior getModRefBehavior(const Function *F);
 
-  /// getModRefBehavior - Return the modref behavior of the intrinsic with the
-  /// given id.
-  static ModRefBehavior getModRefBehavior(unsigned iid);
+  /// getIntrinsicModRefBehavior - Return the modref behavior of the intrinsic
+  /// with the given id.  Most clients won't need this, because the regular
+  /// getModRefBehavior incorporates this information.
+  static ModRefBehavior getIntrinsicModRefBehavior(unsigned iid);
 
   /// doesNotAccessMemory - If the specified call is known to never read or
   /// write memory, return true.  If the call only reads from known-constant
@@ -191,14 +184,14 @@ public:
   ///
   /// This property corresponds to the GCC 'const' attribute.
   ///
-  bool doesNotAccessMemory(CallSite CS) {
+  bool doesNotAccessMemory(ImmutableCallSite CS) {
     return getModRefBehavior(CS) == DoesNotAccessMemory;
   }
 
   /// doesNotAccessMemory - If the specified function is known to never read or
   /// write memory, return true.  For use when the call site is not known.
   ///
-  bool doesNotAccessMemory(Function *F) {
+  bool doesNotAccessMemory(const Function *F) {
     return getModRefBehavior(F) == DoesNotAccessMemory;
   }
 
@@ -211,7 +204,7 @@ public:
   ///
   /// This property corresponds to the GCC 'pure' attribute.
   ///
-  bool onlyReadsMemory(CallSite CS) {
+  bool onlyReadsMemory(ImmutableCallSite CS) {
     ModRefBehavior MRB = getModRefBehavior(CS);
     return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory;
   }
@@ -220,7 +213,7 @@ public:
   /// non-volatile memory (or not access memory at all), return true.  For use
   /// when the call site is not known.
   ///
-  bool onlyReadsMemory(Function *F) {
+  bool onlyReadsMemory(const Function *F) {
     ModRefBehavior MRB = getModRefBehavior(F);
     return MRB == DoesNotAccessMemory || MRB == OnlyReadsMemory;
   }
@@ -234,36 +227,36 @@ public:
   /// a particular call site modifies or reads the memory specified by the
   /// pointer.
   ///
-  virtual ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
+  virtual ModRefResult getModRefInfo(ImmutableCallSite CS,
+                                     const 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);
+  /// to the same set of memory locations.  See 
+  ///   http://llvm.org/docs/AliasAnalysis.html#ModRefInfo
+  /// for details.
+  virtual ModRefResult getModRefInfo(ImmutableCallSite CS1,
+                                     ImmutableCallSite CS2);
 
 public:
   /// 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(const LoadInst *L, const Value *P, unsigned Size);
+  ModRefResult getModRefInfo(const StoreInst *S, const Value *P, unsigned Size);
+  ModRefResult getModRefInfo(const VAArgInst* I, const Value* P, unsigned Size);
+  ModRefResult getModRefInfo(const CallInst *C, const Value *P, unsigned Size) {
+    return getModRefInfo(ImmutableCallSite(C), P, Size);
   }
-  ModRefResult getModRefInfo(VAArgInst* I, Value* P, unsigned Size) {
-    return AliasAnalysis::ModRef;
+  ModRefResult getModRefInfo(const InvokeInst *I,
+                             const Value *P, unsigned Size) {
+    return getModRefInfo(ImmutableCallSite(I), P, Size);
   }
-  ModRefResult getModRefInfo(Instruction *I, Value *P, unsigned Size) {
+  ModRefResult getModRefInfo(const Instruction *I,
+                             const 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);
+    case Instruction::VAArg:  return getModRefInfo((const VAArgInst*)I, P,Size);
+    case Instruction::Load:   return getModRefInfo((const LoadInst*)I, P, Size);
+    case Instruction::Store:  return getModRefInfo((const StoreInst*)I, P,Size);
+    case Instruction::Call:   return getModRefInfo((const CallInst*)I, P, Size);
+    case Instruction::Invoke: return getModRefInfo((const InvokeInst*)I,P,Size);
     default:                  return NoModRef;
     }
   }
diff --git a/include/llvm/Analysis/AliasSetTracker.h b/include/llvm/Analysis/AliasSetTracker.h
index 09f12ad..8e2f7fd 100644
--- a/include/llvm/Analysis/AliasSetTracker.h
+++ b/include/llvm/Analysis/AliasSetTracker.h
@@ -92,7 +92,8 @@ class AliasSet : public ilist_node<AliasSet> {
   AliasSet *Forward;             // Forwarding pointer.
   AliasSet *Next, *Prev;         // Doubly linked list of AliasSets.
 
-  std::vector<CallSite> CallSites; // All calls & invokes in this alias set.
+  // All calls & invokes in this alias set.
+  std::vector<AssertingVH<Instruction> > CallSites;
 
   // RefCount - Number of nodes pointing to this AliasSet plus the number of
   // AliasSets forwarding to it.
@@ -127,6 +128,11 @@ class AliasSet : public ilist_node<AliasSet> {
       removeFromTracker(AST);
   }
 
+  CallSite getCallSite(unsigned i) const {
+    assert(i < CallSites.size());
+    return CallSite(CallSites[i]);
+  }
+  
 public:
   /// Accessors...
   bool isRef() const { return AccessTy & Refs; }
@@ -229,7 +235,7 @@ private:
   void addCallSite(CallSite CS, AliasAnalysis &AA);
   void removeCallSite(CallSite CS) {
     for (size_t i = 0, e = CallSites.size(); i != e; ++i)
-      if (CallSites[i].getInstruction() == CS.getInstruction()) {
+      if (CallSites[i] == CS.getInstruction()) {
         CallSites[i] = CallSites.back();
         CallSites.pop_back();
       }
diff --git a/include/llvm/Analysis/DOTGraphTraitsPass.h b/include/llvm/Analysis/DOTGraphTraitsPass.h
index 4828eba..d8daf51 100644
--- a/include/llvm/Analysis/DOTGraphTraitsPass.h
+++ b/include/llvm/Analysis/DOTGraphTraitsPass.h
@@ -22,7 +22,7 @@ template <class Analysis, bool Simple>
 struct DOTGraphTraitsViewer : public FunctionPass {
   std::string Name;
 
-  DOTGraphTraitsViewer(std::string GraphName, const void *ID) : FunctionPass(ID) {
+  DOTGraphTraitsViewer(std::string GraphName, char &ID) : FunctionPass(ID) {
     Name = GraphName;
   }
 
@@ -48,7 +48,7 @@ struct DOTGraphTraitsPrinter : public FunctionPass {
 
   std::string Name;
 
-  DOTGraphTraitsPrinter(std::string GraphName, const void *ID)
+  DOTGraphTraitsPrinter(std::string GraphName, char &ID)
     : FunctionPass(ID) {
     Name = GraphName;
   }
diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h
index a85b6bc..2d1418d 100644
--- a/include/llvm/Analysis/DebugInfo.h
+++ b/include/llvm/Analysis/DebugInfo.h
@@ -36,6 +36,12 @@ namespace llvm {
   class LLVMContext;
   class raw_ostream;
 
+  class DIFile;
+  class DISubprogram;
+  class DILexicalBlock;
+  class DIVariable;
+  class DIType;
+
   /// DIDescriptor - A thin wraper around MDNode to access encoded debug info.
   /// This should not be stored in a container, because underly MDNode may
   /// change in certain situations.
@@ -56,11 +62,17 @@ namespace llvm {
     }
 
     GlobalVariable *getGlobalVariableField(unsigned Elt) const;
+    Constant *getConstantField(unsigned Elt) const;
     Function *getFunctionField(unsigned Elt) const;
 
   public:
     explicit DIDescriptor() : DbgNode(0) {}
     explicit DIDescriptor(const MDNode *N) : DbgNode(N) {}
+    explicit DIDescriptor(const DIFile F);
+    explicit DIDescriptor(const DISubprogram F);
+    explicit DIDescriptor(const DILexicalBlock F);
+    explicit DIDescriptor(const DIVariable F);
+    explicit DIDescriptor(const DIType F);
 
     bool Verify() const { return DbgNode != 0; }
 
@@ -134,7 +146,7 @@ namespace llvm {
   public:
     explicit DICompileUnit(const MDNode *N = 0) : DIScope(N) {}
 
-    unsigned getLanguage() const     { return getUnsignedField(2); }
+    unsigned getLanguage() const   { return getUnsignedField(2); }
     StringRef getFilename() const  { return getStringField(3);   }
     StringRef getDirectory() const { return getStringField(4);   }
     StringRef getProducer() const  { return getStringField(5);   }
@@ -260,6 +272,10 @@ namespace llvm {
     StringRef getFilename() const    { return getCompileUnit().getFilename();}
     StringRef getDirectory() const   { return getCompileUnit().getDirectory();}
 
+    /// replaceAllUsesWith - Replace all uses of debug info referenced by
+    /// this descriptor.
+    void replaceAllUsesWith(DIDescriptor &D);
+
     /// print - print type.
     void print(raw_ostream &OS) const;
 
@@ -274,6 +290,9 @@ namespace llvm {
 
     unsigned getEncoding() const { return getUnsignedField(9); }
 
+    /// Verify - Verify that a basic type descriptor is well formed.
+    bool Verify() const;
+
     /// print - print basic type.
     void print(raw_ostream &OS) const;
 
@@ -297,16 +316,14 @@ namespace llvm {
     /// return base type size.
     uint64_t getOriginalTypeSize() const;
 
+    /// Verify - Verify that a derived type descriptor is well formed.
+    bool Verify() const;
+
     /// print - print derived type.
     void print(raw_ostream &OS) const;
 
     /// dump - print derived type to dbgs() with a newline.
     void dump() const;
-
-    /// replaceAllUsesWith - Replace all uses of debug info referenced by
-    /// this descriptor. After this completes, the current debug info value
-    /// is erased.
-    void replaceAllUsesWith(DIDescriptor &D);
   };
 
   /// DICompositeType - This descriptor holds a type that can refer to multiple
@@ -437,6 +454,7 @@ namespace llvm {
     unsigned isDefinition() const       { return getUnsignedField(10); }
 
     GlobalVariable *getGlobal() const { return getGlobalVariableField(11); }
+    Constant *getConstant() const   { return getConstantField(11); }
 
     /// Verify - Verify that a global variable descriptor is well formed.
     bool Verify() const;
@@ -504,10 +522,18 @@ namespace llvm {
   public:
     explicit DILexicalBlock(const MDNode *N = 0) : DIScope(N) {}
     DIScope getContext() const       { return getFieldAs<DIScope>(1);      }
-    StringRef getDirectory() const   { return getContext().getDirectory(); }
-    StringRef getFilename() const    { return getContext().getFilename();  }
     unsigned getLineNumber() const   { return getUnsignedField(2);         }
     unsigned getColumnNumber() const { return getUnsignedField(3);         }
+    StringRef getDirectory() const {
+      DIFile F = getFieldAs<DIFile>(4);
+      StringRef dir = F.getDirectory();
+      return !dir.empty() ? dir : getContext().getDirectory();
+    }
+    StringRef getFilename() const {
+      DIFile F = getFieldAs<DIFile>(4);
+      StringRef filename = F.getFilename();
+      return !filename.empty() ? filename : getContext().getFilename();
+    }
   };
 
   /// DINameSpace - A wrapper for a C++ style name space.
@@ -634,6 +660,9 @@ namespace llvm {
                                         unsigned RunTimeLang = 0,
                                         MDNode *ContainingType = 0);
 
+    /// CreateTemporaryType - Create a temporary forward-declared type.
+    DIType CreateTemporaryType();
+
     /// CreateArtificialType - Create a new DIType with "artificial" flag set.
     DIType CreateArtificialType(DIType Ty);
 
@@ -648,7 +677,8 @@ namespace llvm {
                                           unsigned Flags,
                                           DIType DerivedFrom,
                                           DIArray Elements,
-                                          unsigned RunTimeLang = 0);
+                                          unsigned RunTimeLang = 0,
+                                          MDNode *ContainingType = 0);
 
     /// CreateSubprogram - Create a new descriptor for the specified subprogram.
     /// See comments in DISubprogram for descriptions of these fields.
@@ -678,6 +708,15 @@ namespace llvm {
                          unsigned LineNo, DIType Ty, bool isLocalToUnit,
                          bool isDefinition, llvm::GlobalVariable *GV);
 
+    /// CreateGlobalVariable - Create a new descriptor for the specified constant.
+    DIGlobalVariable
+    CreateGlobalVariable(DIDescriptor Context, StringRef Name,
+                         StringRef DisplayName,
+                         StringRef LinkageName,
+                         DIFile F,
+                         unsigned LineNo, DIType Ty, bool isLocalToUnit,
+                         bool isDefinition, llvm::Constant *C);
+
     /// CreateVariable - Create a new descriptor for the specified variable.
     DIVariable CreateVariable(unsigned Tag, DIDescriptor Context,
                               StringRef Name,
@@ -694,8 +733,8 @@ namespace llvm {
 
     /// CreateLexicalBlock - This creates a descriptor for a lexical block
     /// with the specified parent context.
-    DILexicalBlock CreateLexicalBlock(DIDescriptor Context, unsigned Line = 0,
-                                      unsigned Col = 0);
+    DILexicalBlock CreateLexicalBlock(DIDescriptor Context, DIFile F,
+                                      unsigned Line = 0, unsigned Col = 0);
 
     /// CreateNameSpace - This creates new descriptor for a namespace
     /// with the specified parent context.
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 1979d3f..73c6e62 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -702,7 +702,7 @@ public:
   static char ID; // Pass ID, replacement for typeid
   DominatorTreeBase<BasicBlock>* DT;
 
-  DominatorTree() : FunctionPass(&ID) {
+  DominatorTree() : FunctionPass(ID) {
     DT = new DominatorTreeBase<BasicBlock>(false);
   }
 
@@ -890,7 +890,7 @@ protected:
   const bool IsPostDominators;
 
 public:
-  DominanceFrontierBase(void *ID, bool isPostDom)
+  DominanceFrontierBase(char &ID, bool isPostDom)
     : FunctionPass(ID), IsPostDominators(isPostDom) {}
 
   /// getRoots - Return the root blocks of the current CFG.  This may include
@@ -995,6 +995,9 @@ public:
   /// print - Convert to human readable form
   ///
   virtual void print(raw_ostream &OS, const Module* = 0) const;
+
+  /// dump - Dump the dominance frontier to dbgs().
+  void dump() const;
 };
 
 
@@ -1006,7 +1009,7 @@ class DominanceFrontier : public DominanceFrontierBase {
 public:
   static char ID; // Pass ID, replacement for typeid
   DominanceFrontier() :
-    DominanceFrontierBase(&ID, false) {}
+    DominanceFrontierBase(ID, false) {}
 
   BasicBlock *getRoot() const {
     assert(Roots.size() == 1 && "Should always have entry node!");
diff --git a/include/llvm/Analysis/FindUsedTypes.h b/include/llvm/Analysis/FindUsedTypes.h
index 1337385..8a78eb6 100644
--- a/include/llvm/Analysis/FindUsedTypes.h
+++ b/include/llvm/Analysis/FindUsedTypes.h
@@ -26,7 +26,7 @@ class FindUsedTypes : public ModulePass {
   std::set<const Type *> UsedTypes;
 public:
   static char ID; // Pass identification, replacement for typeid
-  FindUsedTypes() : ModulePass(&ID) {}
+  FindUsedTypes() : ModulePass(ID) {}
 
   /// getTypes - After the pass has been run, return the set containing all of
   /// the types used in the module.
diff --git a/include/llvm/Analysis/IntervalPartition.h b/include/llvm/Analysis/IntervalPartition.h
index c1214e7..75a5cdf 100644
--- a/include/llvm/Analysis/IntervalPartition.h
+++ b/include/llvm/Analysis/IntervalPartition.h
@@ -48,7 +48,7 @@ class IntervalPartition : public FunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid
 
-  IntervalPartition() : FunctionPass(&ID), RootInterval(0) {}
+  IntervalPartition() : FunctionPass(ID), RootInterval(0) {}
 
   // run - Calculate the interval partition for this function
   virtual bool runOnFunction(Function &F);
diff --git a/include/llvm/Analysis/LazyValueInfo.h b/include/llvm/Analysis/LazyValueInfo.h
index 566788d..b2a3afb 100644
--- a/include/llvm/Analysis/LazyValueInfo.h
+++ b/include/llvm/Analysis/LazyValueInfo.h
@@ -12,8 +12,8 @@
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_ANALYSIS_LIVEVALUES_H
-#define LLVM_ANALYSIS_LIVEVALUES_H
+#ifndef LLVM_ANALYSIS_LAZYVALUEINFO_H
+#define LLVM_ANALYSIS_LAZYVALUEINFO_H
 
 #include "llvm/Pass.h"
 
@@ -31,7 +31,7 @@ class LazyValueInfo : public FunctionPass {
   void operator=(const LazyValueInfo&); // DO NOT IMPLEMENT.
 public:
   static char ID;
-  LazyValueInfo() : FunctionPass(&ID), PImpl(0) {}
+  LazyValueInfo() : FunctionPass(ID), PImpl(0) {}
   ~LazyValueInfo() { assert(PImpl == 0 && "releaseMemory not called"); }
 
   /// Tristate - This is used to return true/false/dunno results.
@@ -57,6 +57,12 @@ public:
   /// constant on the specified edge.  Return null if not.
   Constant *getConstantOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB);
   
+  /// threadEdge - Inform the analysis cache that we have threaded an edge from
+  /// PredBB to OldSucc to be from PredBB to NewSucc instead.
+  void threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc, BasicBlock *NewSucc);
+  
+  /// eraseBlock - Inform the analysis cache that we have erased a block.
+  void eraseBlock(BasicBlock *BB);
   
   // Implementation boilerplate.
   
diff --git a/include/llvm/Analysis/LibCallAliasAnalysis.h b/include/llvm/Analysis/LibCallAliasAnalysis.h
index 01f108d..c9adf3f 100644
--- a/include/llvm/Analysis/LibCallAliasAnalysis.h
+++ b/include/llvm/Analysis/LibCallAliasAnalysis.h
@@ -28,18 +28,20 @@ namespace llvm {
     LibCallInfo *LCI;
     
     explicit LibCallAliasAnalysis(LibCallInfo *LC = 0)
-      : FunctionPass(&ID), LCI(LC) {
+      : FunctionPass(ID), LCI(LC) {
     }
-    explicit LibCallAliasAnalysis(const void *ID, LibCallInfo *LC)
+    explicit LibCallAliasAnalysis(char &ID, LibCallInfo *LC)
       : FunctionPass(ID), LCI(LC) {
     }
     ~LibCallAliasAnalysis();
     
-    ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
+    ModRefResult getModRefInfo(ImmutableCallSite CS,
+                               const Value *P, unsigned Size);
     
-    ModRefResult getModRefInfo(CallSite CS1, CallSite CS2) {
+    ModRefResult getModRefInfo(ImmutableCallSite CS1,
+                               ImmutableCallSite CS2) {
       // TODO: Could compare two direct calls against each other if we cared to.
-      return AliasAnalysis::getModRefInfo(CS1,CS2);
+      return AliasAnalysis::getModRefInfo(CS1, CS2);
     }
     
     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
@@ -49,9 +51,20 @@ namespace llvm {
       return false;
     }
     
+    /// getAdjustedAnalysisPointer - This method is used when a pass implements
+    /// an analysis interface through multiple inheritance.  If needed, it
+    /// should override this to adjust the this pointer as needed for the
+    /// specified pass info.
+    virtual void *getAdjustedAnalysisPointer(const void *PI) {
+      if (PI == &AliasAnalysis::ID)
+        return (AliasAnalysis*)this;
+      return this;
+    }
+    
   private:
     ModRefResult AnalyzeLibCallDetails(const LibCallFunctionInfo *FI,
-                                       CallSite CS, Value *P, unsigned Size);
+                                       ImmutableCallSite CS,
+                                       const Value *P, unsigned Size);
   };
 }  // End of llvm namespace
 
diff --git a/include/llvm/Analysis/LibCallSemantics.h b/include/llvm/Analysis/LibCallSemantics.h
index 74e8401..31d7cc5 100644
--- a/include/llvm/Analysis/LibCallSemantics.h
+++ b/include/llvm/Analysis/LibCallSemantics.h
@@ -47,7 +47,8 @@ namespace llvm {
     enum LocResult {
       Yes, No, Unknown
     };
-    LocResult (*isLocation)(CallSite CS, const Value *Ptr, unsigned Size);
+    LocResult (*isLocation)(ImmutableCallSite CS,
+                            const Value *Ptr, unsigned Size);
   };
   
   /// LibCallFunctionInfo - Each record in the array of FunctionInfo structs
@@ -142,7 +143,7 @@ namespace llvm {
     
     /// getFunctionInfo - Return the LibCallFunctionInfo object corresponding to
     /// the specified function if we have it.  If not, return null.
-    const LibCallFunctionInfo *getFunctionInfo(Function *F) const;
+    const LibCallFunctionInfo *getFunctionInfo(const Function *F) const;
     
     
     //===------------------------------------------------------------------===//
diff --git a/include/llvm/Analysis/LoopDependenceAnalysis.h b/include/llvm/Analysis/LoopDependenceAnalysis.h
index a1a5637..94fd990 100644
--- a/include/llvm/Analysis/LoopDependenceAnalysis.h
+++ b/include/llvm/Analysis/LoopDependenceAnalysis.h
@@ -91,7 +91,7 @@ class LoopDependenceAnalysis : public LoopPass {
 
 public:
   static char ID; // Class identification, replacement for typeinfo
-  LoopDependenceAnalysis() : LoopPass(&ID) {}
+  LoopDependenceAnalysis() : LoopPass(ID) {}
 
   /// isDependencePair - Check whether two values can possibly give rise to
   /// a data dependence: that is the case if both are instructions accessing
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 9455fd8..462620f 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -35,6 +35,7 @@
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/Dominators.h"
 #include "llvm/Support/CFG.h"
 #include "llvm/Support/raw_ostream.h"
@@ -229,13 +230,16 @@ public:
     return 0;
   }
 
+  /// Edge type.
+  typedef std::pair<BlockT*, BlockT*> Edge;
+
   /// getExitEdges - Return all pairs of (_inside_block_,_outside_block_).
-  typedef std::pair<const BlockT*,const BlockT*> Edge;
-  void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const {
+  template <typename EdgeT>
+  void getExitEdges(SmallVectorImpl<EdgeT> &ExitEdges) const {
     // Sort the blocks vector so that we can use binary search to do quick
     // lookups.
     SmallVector<BlockT*, 128> LoopBBs(block_begin(), block_end());
-    std::sort(LoopBBs.begin(), LoopBBs.end());
+    array_pod_sort(LoopBBs.begin(), LoopBBs.end());
 
     typedef GraphTraits<BlockT*> BlockTraits;
     for (block_iterator BI = block_begin(), BE = block_end(); BI != BE; ++BI)
@@ -244,7 +248,7 @@ public:
            I != E; ++I)
         if (!std::binary_search(LoopBBs.begin(), LoopBBs.end(), *I))
           // Not in current loop? It must be an exit block.
-          ExitEdges.push_back(std::make_pair(*BI, *I));
+          ExitEdges.push_back(EdgeT(*BI, *I));
   }
 
   /// getLoopPreheader - If there is a preheader for this loop, return it.  A
@@ -505,6 +509,12 @@ protected:
   }
 };
 
+template<class BlockT, class LoopT>
+raw_ostream& operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
+  Loop.print(OS);
+  return OS;
+}
+
 class Loop : public LoopBase<BasicBlock, Loop> {
 public:
   Loop() {}
@@ -552,12 +562,6 @@ public:
   ///
   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,
@@ -936,7 +940,7 @@ class LoopInfo : public FunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid
 
-  LoopInfo() : FunctionPass(&ID) {}
+  LoopInfo() : FunctionPass(ID) {}
 
   LoopInfoBase<BasicBlock, Loop>& getBase() { return LI; }
 
diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h
index 6f77d01..1603d2e 100644
--- a/include/llvm/Analysis/LoopPass.h
+++ b/include/llvm/Analysis/LoopPass.h
@@ -19,6 +19,7 @@
 #include "llvm/Pass.h"
 #include "llvm/PassManagers.h"
 #include "llvm/Function.h"
+#include <deque>
 
 namespace llvm {
 
@@ -28,8 +29,7 @@ class PMStack;
 
 class LoopPass : public Pass {
 public:
-  explicit LoopPass(intptr_t pid) : Pass(PT_Loop, pid) {}
-  explicit LoopPass(void *pid) : Pass(PT_Loop, pid) {}
+  explicit LoopPass(char &pid) : Pass(PT_Loop, pid) {}
 
   /// getPrinterPass - Get a pass to print the function corresponding
   /// to a Loop.
@@ -58,7 +58,7 @@ public:
 
   /// Assign pass manager to manage this pass
   virtual void assignPassManager(PMStack &PMS,
-                                 PassManagerType PMT = PMT_LoopPassManager);
+                                 PassManagerType PMT);
 
   ///  Return what kind of Pass Manager can manage this pass.
   virtual PassManagerType getPotentialPassManagerType() const {
@@ -104,10 +104,10 @@ public:
   /// Print passes managed by this manager
   void dumpPassStructure(unsigned Offset);
 
-  Pass *getContainedPass(unsigned N) {
+  LoopPass *getContainedPass(unsigned N) {
     assert(N < PassVector.size() && "Pass number out of range!");
-    Pass *FP = static_cast<Pass *>(PassVector[N]);
-    return FP;
+    LoopPass *LP = static_cast<LoopPass *>(PassVector[N]);
+    return LP;
   }
 
   virtual PassManagerType getPassManagerType() const {
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h
index ce3f7a6..37425eb 100644
--- a/include/llvm/Analysis/Passes.h
+++ b/include/llvm/Analysis/Passes.h
@@ -81,11 +81,18 @@ namespace llvm {
 
   //===--------------------------------------------------------------------===//
   //
+  // createTypeBasedAliasAnalysisPass - This pass implements metadata-based
+  // type-based alias analysis.
+  //
+  ImmutablePass *createTypeBasedAliasAnalysisPass();
+
+  //===--------------------------------------------------------------------===//
+  //
   // createProfileLoaderPass - This pass loads information from a profile dump
   // file.
   //
   ModulePass *createProfileLoaderPass();
-  extern const PassInfo *ProfileLoaderPassID;
+  extern char &ProfileLoaderPassID;
 
   //===--------------------------------------------------------------------===//
   //
@@ -99,7 +106,7 @@ namespace llvm {
   // instead of loading it from a previous run.
   //
   FunctionPass *createProfileEstimatorPass();
-  extern const PassInfo *ProfileEstimatorPassID;
+  extern char &ProfileEstimatorPassID;
 
   //===--------------------------------------------------------------------===//
   //
@@ -154,6 +161,13 @@ namespace llvm {
   // print debug info intrinsics in human readable form
   FunctionPass *createDbgInfoPrinterPass();
 
+  //===--------------------------------------------------------------------===//
+  //
+  // createRegionInfoPass - This pass finds all single entry single exit regions
+  // in a function and builds the region hierarchy.
+  //
+  FunctionPass *createRegionInfoPass();
+
   // Print module-level debug info metadata in human-readable form.
   ModulePass *createModuleDebugInfoPrinterPass();
 }
diff --git a/include/llvm/Analysis/PointerTracking.h b/include/llvm/Analysis/PointerTracking.h
index 6c4f838..6b49e18 100644
--- a/include/llvm/Analysis/PointerTracking.h
+++ b/include/llvm/Analysis/PointerTracking.h
@@ -98,6 +98,7 @@ namespace llvm {
     virtual bool runOnFunction(Function &F);
     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
     void print(raw_ostream &OS, const Module* = 0) const;
+    Value *computeAllocationCountValue(Value *P, const Type *&Ty) const;
   private:
     Function *FF;
     TargetData *TD;
diff --git a/include/llvm/Analysis/PostDominators.h b/include/llvm/Analysis/PostDominators.h
index 5552017..46ce820 100644
--- a/include/llvm/Analysis/PostDominators.h
+++ b/include/llvm/Analysis/PostDominators.h
@@ -25,7 +25,7 @@ struct PostDominatorTree : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   DominatorTreeBase<BasicBlock>* DT;
 
-  PostDominatorTree() : FunctionPass(&ID) {
+  PostDominatorTree() : FunctionPass(ID) {
     DT = new DominatorTreeBase<BasicBlock>(true);
   }
 
@@ -106,7 +106,7 @@ template <> struct GraphTraits<PostDominatorTree*>
 struct PostDominanceFrontier : public DominanceFrontierBase {
   static char ID;
   PostDominanceFrontier()
-    : DominanceFrontierBase(&ID, true) {}
+    : DominanceFrontierBase(ID, true) {}
 
   virtual bool runOnFunction(Function &) {
     Frontiers.clear();
diff --git a/include/llvm/Analysis/RegionInfo.h b/include/llvm/Analysis/RegionInfo.h
new file mode 100644
index 0000000..7a2670f
--- /dev/null
+++ b/include/llvm/Analysis/RegionInfo.h
@@ -0,0 +1,630 @@
+//===- RegionInfo.h - SESE region analysis ----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Calculate a program structure tree built out of single entry single exit
+// regions.
+// The basic ideas are taken from "The Program Structure Tree - Richard Johnson,
+// David Pearson, Keshav Pingali - 1994", however enriched with ideas from "The
+// Refined Process Structure Tree - Jussi Vanhatalo, Hagen Voelyer, Jana
+// Koehler - 2009".
+// The algorithm to calculate these data structures however is completely
+// different, as it takes advantage of existing information already available
+// in (Post)dominace tree and dominance frontier passes. This leads to a simpler
+// and in practice hopefully better performing algorithm. The runtime of the
+// algorithms described in the papers above are both linear in graph size,
+// O(V+E), whereas this algorithm is not, as the dominance frontier information
+// itself is not, but in practice runtime seems to be in the order of magnitude
+// of dominance tree calculation.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_REGION_INFO_H
+#define LLVM_ANALYSIS_REGION_INFO_H
+
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Support/Allocator.h"
+
+namespace llvm {
+
+class Region;
+class RegionInfo;
+class raw_ostream;
+class Loop;
+class LoopInfo;
+
+/// @brief Marker class to iterate over the elements of a Region in flat mode.
+///
+/// The class is used to either iterate in Flat mode or by not using it to not
+/// iterate in Flat mode.  During a Flat mode iteration all Regions are entered
+/// and the iteration returns every BasicBlock.  If the Flat mode is not
+/// selected for SubRegions just one RegionNode containing the subregion is
+/// returned.
+template <class GraphType>
+class FlatIt {};
+
+/// @brief A RegionNode represents a subregion or a BasicBlock that is part of a
+/// Region.
+class RegionNode {
+  // DO NOT IMPLEMENT
+  RegionNode(const RegionNode &);
+  // DO NOT IMPLEMENT
+  const RegionNode &operator=(const RegionNode &);
+
+  /// This is the entry basic block that starts this region node.  If this is a
+  /// BasicBlock RegionNode, then entry is just the basic block, that this
+  /// RegionNode represents.  Otherwise it is the entry of this (Sub)RegionNode.
+  ///
+  /// In the BBtoRegionNode map of the parent of this node, BB will always map
+  /// to this node no matter which kind of node this one is.
+  ///
+  /// The node can hold either a Region or a BasicBlock.
+  /// Use one bit to save, if this RegionNode is a subregion or BasicBlock
+  /// RegionNode.
+  PointerIntPair<BasicBlock*, 1, bool> entry;
+
+protected:
+  /// @brief The parent Region of this RegionNode.
+  /// @see getParent()
+  Region* parent;
+
+public:
+  /// @brief Create a RegionNode.
+  ///
+  /// @param Parent      The parent of this RegionNode.
+  /// @param Entry       The entry BasicBlock of the RegionNode.  If this
+  ///                    RegionNode represents a BasicBlock, this is the
+  ///                    BasicBlock itself.  If it represents a subregion, this
+  ///                    is the entry BasicBlock of the subregion.
+  /// @param isSubRegion If this RegionNode represents a SubRegion.
+  inline RegionNode(Region* Parent, BasicBlock* Entry, bool isSubRegion = 0)
+    : entry(Entry, isSubRegion), parent(Parent) {}
+
+  /// @brief Get the parent Region of this RegionNode.
+  ///
+  /// The parent Region is the Region this RegionNode belongs to. If for
+  /// example a BasicBlock is element of two Regions, there exist two
+  /// RegionNodes for this BasicBlock. Each with the getParent() function
+  /// pointing to the Region this RegionNode belongs to.
+  ///
+  /// @return Get the parent Region of this RegionNode.
+  inline Region* getParent() const { return parent; }
+
+  /// @brief Get the entry BasicBlock of this RegionNode.
+  ///
+  /// If this RegionNode represents a BasicBlock this is just the BasicBlock
+  /// itself, otherwise we return the entry BasicBlock of the Subregion
+  ///
+  /// @return The entry BasicBlock of this RegionNode.
+  inline BasicBlock* getEntry() const { return entry.getPointer(); }
+
+  /// @brief Get the content of this RegionNode.
+  ///
+  /// This can be either a BasicBlock or a subregion. Before calling getNodeAs()
+  /// check the type of the content with the isSubRegion() function call.
+  ///
+  /// @return The content of this RegionNode.
+  template<class T>
+  inline T* getNodeAs() const;
+
+  /// @brief Is this RegionNode a subregion?
+  ///
+  /// @return True if it contains a subregion. False if it contains a
+  ///         BasicBlock.
+  inline bool isSubRegion() const {
+    return entry.getInt();
+  }
+};
+
+/// Print a RegionNode.
+inline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node);
+
+template<>
+inline BasicBlock* RegionNode::getNodeAs<BasicBlock>() const {
+  assert(!isSubRegion() && "This is not a BasicBlock RegionNode!");
+  return getEntry();
+}
+
+template<>
+inline Region* RegionNode::getNodeAs<Region>() const {
+  assert(isSubRegion() && "This is not a subregion RegionNode!");
+  return reinterpret_cast<Region*>(const_cast<RegionNode*>(this));
+}
+
+//===----------------------------------------------------------------------===//
+/// @brief A single entry single exit Region.
+///
+/// A Region is a connected subgraph of a control flow graph that has exactly
+/// two connections to the remaining graph. It can be used to analyze or
+/// optimize parts of the control flow graph.
+///
+/// A <em> simple Region </em> is connected to the remaing graph by just two
+/// edges. One edge entering the Region and another one leaving the Region.
+///
+/// An <em> extended Region </em> (or just Region) is a subgraph that can be
+/// transform into a simple Region. The transformation is done by adding
+/// BasicBlocks that merge several entry or exit edges so that after the merge
+/// just one entry and one exit edge exists.
+///
+/// The \e Entry of a Region is the first BasicBlock that is passed after
+/// entering the Region. It is an element of the Region. The entry BasicBlock
+/// dominates all BasicBlocks in the Region.
+///
+/// The \e Exit of a Region is the first BasicBlock that is passed after
+/// leaving the Region. It is not an element of the Region. The exit BasicBlock,
+/// postdominates all BasicBlocks in the Region.
+///
+/// A <em> canonical Region </em> cannot be constructed by combining smaller
+/// Regions.
+///
+/// Region A is the \e parent of Region B, if B is completely contained in A.
+///
+/// Two canonical Regions either do not intersect at all or one is
+/// the parent of the other.
+///
+/// The <em> Program Structure Tree</em> is a graph (V, E) where V is the set of
+/// Regions in the control flow graph and E is the \e parent relation of these
+/// Regions.
+///
+/// Example:
+///
+/// \verbatim
+/// A simple control flow graph, that contains two regions.
+///
+///        1
+///       / |
+///      2   |
+///     / \   3
+///    4   5  |
+///    |   |  |
+///    6   7  8
+///     \  | /
+///      \ |/       Region A: 1 -> 9 {1,2,3,4,5,6,7,8}
+///        9        Region B: 2 -> 9 {2,4,5,6,7}
+/// \endverbatim
+///
+/// You can obtain more examples by either calling
+///
+/// <tt> "opt -regions -analyze anyprogram.ll" </tt>
+/// or
+/// <tt> "opt -view-regions-only anyprogram.ll" </tt>
+///
+/// on any LLVM file you are interested in.
+///
+/// The first call returns a textual representation of the program structure
+/// tree, the second one creates a graphical representation using graphviz.
+class Region : public RegionNode {
+  friend class RegionInfo;
+  // DO NOT IMPLEMENT
+  Region(const Region &);
+  // DO NOT IMPLEMENT
+  const Region &operator=(const Region &);
+
+  // Information necessary to manage this Region.
+  RegionInfo* RI;
+  DominatorTree *DT;
+
+  // The exit BasicBlock of this region.
+  // (The entry BasicBlock is part of RegionNode)
+  BasicBlock *exit;
+
+  typedef std::vector<Region*> RegionSet;
+
+  // The subregions of this region.
+  RegionSet children;
+
+  typedef std::map<BasicBlock*, RegionNode*> BBNodeMapT;
+
+  // Save the BasicBlock RegionNodes that are element of this Region.
+  mutable BBNodeMapT BBNodeMap;
+
+  /// verifyBBInRegion - Check if a BB is in this Region. This check also works
+  /// if the region is incorrectly built. (EXPENSIVE!)
+  void verifyBBInRegion(BasicBlock* BB) const;
+
+  /// verifyWalk - Walk over all the BBs of the region starting from BB and
+  /// verify that all reachable basic blocks are elements of the region.
+  /// (EXPENSIVE!)
+  void verifyWalk(BasicBlock* BB, std::set<BasicBlock*>* visitedBB) const;
+
+  /// verifyRegionNest - Verify if the region and its children are valid
+  /// regions (EXPENSIVE!)
+  void verifyRegionNest() const;
+
+public:
+  /// @brief Create a new region.
+  ///
+  /// @param Entry  The entry basic block of the region.
+  /// @param Exit   The exit basic block of the region.
+  /// @param RI     The region info object that is managing this region.
+  /// @param DT     The dominator tree of the current function.
+  /// @param Parent The surrounding region or NULL if this is a top level
+  ///               region.
+  Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RI,
+         DominatorTree *DT, Region *Parent = 0);
+
+  /// Delete the Region and all its subregions.
+  ~Region();
+
+  /// @brief Get the entry BasicBlock of the Region.
+  /// @return The entry BasicBlock of the region.
+  BasicBlock *getEntry() const { return RegionNode::getEntry(); }
+
+  /// @brief Get the exit BasicBlock of the Region.
+  /// @return The exit BasicBlock of the Region, NULL if this is the TopLevel
+  ///         Region.
+  BasicBlock *getExit() const { return exit; }
+
+  /// @brief Get the parent of the Region.
+  /// @return The parent of the Region or NULL if this is a top level
+  ///         Region.
+  Region *getParent() const { return RegionNode::getParent(); }
+
+  /// @brief Get the RegionNode representing the current Region.
+  /// @return The RegionNode representing the current Region.
+  RegionNode* getNode() const {
+    return const_cast<RegionNode*>(reinterpret_cast<const RegionNode*>(this));
+  }
+
+  /// @brief Get the nesting level of this Region.
+  ///
+  /// An toplevel Region has depth 0.
+  ///
+  /// @return The depth of the region.
+  unsigned getDepth() const;
+
+  /// @brief Is this a simple region?
+  ///
+  /// A region is simple if it has exactly one exit and one entry edge.
+  ///
+  /// @return True if the Region is simple.
+  bool isSimple() const;
+
+  /// @brief Returns the name of the Region.
+  /// @return The Name of the Region.
+  std::string getNameStr() const;
+
+  /// @brief Return the RegionInfo object, that belongs to this Region.
+  RegionInfo *getRegionInfo() const {
+    return RI;
+  }
+
+  /// @brief Print the region.
+  ///
+  /// @param OS The output stream the Region is printed to.
+  /// @param printTree Print also the tree of subregions.
+  /// @param level The indentation level used for printing.
+  void print(raw_ostream& OS, bool printTree = true, unsigned level = 0) const;
+
+  /// @brief Print the region to stderr.
+  void dump() const;
+
+  /// @brief Check if the region contains a BasicBlock.
+  ///
+  /// @param BB The BasicBlock that might be contained in this Region.
+  /// @return True if the block is contained in the region otherwise false.
+  bool contains(const BasicBlock *BB) const;
+
+  /// @brief Check if the region contains another region.
+  ///
+  /// @param SubRegion The region that might be contained in this Region.
+  /// @return True if SubRegion is contained in the region otherwise false.
+  bool contains(const Region *SubRegion) const {
+    // Toplevel Region.
+    if (!getExit())
+      return true;
+
+    return contains(SubRegion->getEntry())
+      && (contains(SubRegion->getExit()) || SubRegion->getExit() == getExit());
+  }
+
+  /// @brief Check if the region contains an Instruction.
+  ///
+  /// @param Inst The Instruction that might be contained in this region.
+  /// @return True if the Instruction is contained in the region otherwise false.
+  bool contains(const Instruction *Inst) const {
+    return contains(Inst->getParent());
+  }
+
+  /// @brief Check if the region contains a loop.
+  ///
+  /// @param L The loop that might be contained in this region.
+  /// @return True if the loop is contained in the region otherwise false.
+  ///         In case a NULL pointer is passed to this function the result
+  ///         is false, except for the region that describes the whole function.
+  ///         In that case true is returned.
+  bool contains(const Loop *L) const;
+
+  /// @brief Get the outermost loop in the region that contains a loop.
+  ///
+  /// Find for a Loop L the outermost loop OuterL that is a parent loop of L
+  /// and is itself contained in the region.
+  ///
+  /// @param L The loop the lookup is started.
+  /// @return The outermost loop in the region, NULL if such a loop does not
+  ///         exist or if the region describes the whole function.
+  Loop *outermostLoopInRegion(Loop *L) const;
+
+  /// @brief Get the outermost loop in the region that contains a basic block.
+  ///
+  /// Find for a basic block BB the outermost loop L that contains BB and is
+  /// itself contained in the region.
+  ///
+  /// @param LI A pointer to a LoopInfo analysis.
+  /// @param BB The basic block surrounded by the loop.
+  /// @return The outermost loop in the region, NULL if such a loop does not
+  ///         exist or if the region describes the whole function.
+  Loop *outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const;
+
+  /// @brief Get the subregion that starts at a BasicBlock
+  ///
+  /// @param BB The BasicBlock the subregion should start.
+  /// @return The Subregion if available, otherwise NULL.
+  Region* getSubRegionNode(BasicBlock *BB) const;
+
+  /// @brief Get the RegionNode for a BasicBlock
+  ///
+  /// @param BB The BasicBlock at which the RegionNode should start.
+  /// @return If available, the RegionNode that represents the subregion
+  ///         starting at BB. If no subregion starts at BB, the RegionNode
+  ///         representing BB.
+  RegionNode* getNode(BasicBlock *BB) const;
+
+  /// @brief Get the BasicBlock RegionNode for a BasicBlock
+  ///
+  /// @param BB The BasicBlock for which the RegionNode is requested.
+  /// @return The RegionNode representing the BB.
+  RegionNode* getBBNode(BasicBlock *BB) const;
+
+  /// @brief Add a new subregion to this Region.
+  ///
+  /// @param SubRegion The new subregion that will be added.
+  void addSubRegion(Region *SubRegion);
+
+  /// @brief Remove a subregion from this Region.
+  ///
+  /// The subregion is not deleted, as it will probably be inserted into another
+  /// region.
+  /// @param SubRegion The SubRegion that will be removed.
+  Region *removeSubRegion(Region *SubRegion);
+
+  /// @brief Move all direct child nodes of this Region to another Region.
+  ///
+  /// @param To The Region the child nodes will be transfered to.
+  void transferChildrenTo(Region *To);
+
+  /// @brief Verify if the region is a correct region.
+  ///
+  /// Check if this is a correctly build Region. This is an expensive check, as
+  /// the complete CFG of the Region will be walked.
+  void verifyRegion() const;
+
+  /// @brief Clear the cache for BB RegionNodes.
+  ///
+  /// After calling this function the BasicBlock RegionNodes will be stored at
+  /// different memory locations. RegionNodes obtained before this function is
+  /// called are therefore not comparable to RegionNodes abtained afterwords.
+  void clearNodeCache();
+
+  /// @name Subregion Iterators
+  ///
+  /// These iterators iterator over all subregions of this Region.
+  //@{
+  typedef RegionSet::iterator iterator;
+  typedef RegionSet::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(); }
+  //@}
+
+  /// @name BasicBlock Iterators
+  ///
+  /// These iterators iterate over all BasicBlock RegionNodes that are
+  /// contained in this Region. The iterator also iterates over BasicBlocks
+  /// that are elements of a subregion of this Region. It is therefore called a
+  /// flat iterator.
+  //@{
+  typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false,
+                      GraphTraits<FlatIt<RegionNode*> > > block_iterator;
+
+  typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>,
+                      false, GraphTraits<FlatIt<const RegionNode*> > >
+            const_block_iterator;
+
+  block_iterator block_begin();
+  block_iterator block_end();
+
+  const_block_iterator block_begin() const;
+  const_block_iterator block_end() const;
+  //@}
+
+  /// @name Element Iterators
+  ///
+  /// These iterators iterate over all BasicBlock and subregion RegionNodes that
+  /// are direct children of this Region. It does not iterate over any
+  /// RegionNodes that are also element of a subregion of this Region.
+  //@{
+  typedef df_iterator<RegionNode*, SmallPtrSet<RegionNode*, 8>, false,
+                      GraphTraits<RegionNode*> > element_iterator;
+
+  typedef df_iterator<const RegionNode*, SmallPtrSet<const RegionNode*, 8>,
+                      false, GraphTraits<const RegionNode*> >
+            const_element_iterator;
+
+  element_iterator element_begin();
+  element_iterator element_end();
+
+  const_element_iterator element_begin() const;
+  const_element_iterator element_end() const;
+  //@}
+};
+
+//===----------------------------------------------------------------------===//
+/// @brief Analysis that detects all canonical Regions.
+///
+/// The RegionInfo pass detects all canonical regions in a function. The Regions
+/// are connected using the parent relation. This builds a Program Structure
+/// Tree.
+class RegionInfo : public FunctionPass {
+  typedef DenseMap<BasicBlock*,BasicBlock*> BBtoBBMap;
+  typedef DenseMap<BasicBlock*, Region*> BBtoRegionMap;
+  typedef SmallPtrSet<Region*, 4> RegionSet;
+
+  // DO NOT IMPLEMENT
+  RegionInfo(const RegionInfo &);
+  // DO NOT IMPLEMENT
+  const RegionInfo &operator=(const RegionInfo &);
+
+  DominatorTree *DT;
+  PostDominatorTree *PDT;
+  DominanceFrontier *DF;
+
+  /// The top level region.
+  Region *TopLevelRegion;
+
+  /// Map every BB to the smallest region, that contains BB.
+  BBtoRegionMap BBtoRegion;
+
+  // isCommonDomFrontier - Returns true if BB is in the dominance frontier of
+  // entry, because it was inherited from exit. In the other case there is an
+  // edge going from entry to BB without passing exit.
+  bool isCommonDomFrontier(BasicBlock* BB, BasicBlock* entry,
+                           BasicBlock* exit) const;
+
+  // isRegion - Check if entry and exit surround a valid region, based on
+  // dominance tree and dominance frontier.
+  bool isRegion(BasicBlock* entry, BasicBlock* exit) const;
+
+  // insertShortCut - Saves a shortcut pointing from entry to exit.
+  // This function may extend this shortcut if possible.
+  void insertShortCut(BasicBlock* entry, BasicBlock* exit,
+                      BBtoBBMap* ShortCut) const;
+
+  // getNextPostDom - Returns the next BB that postdominates N, while skipping
+  // all post dominators that cannot finish a canonical region.
+  DomTreeNode *getNextPostDom(DomTreeNode* N, BBtoBBMap *ShortCut) const;
+
+  // isTrivialRegion - A region is trivial, if it contains only one BB.
+  bool isTrivialRegion(BasicBlock *entry, BasicBlock *exit) const;
+
+  // createRegion - Creates a single entry single exit region.
+  Region *createRegion(BasicBlock *entry, BasicBlock *exit);
+
+  // findRegionsWithEntry - Detect all regions starting with bb 'entry'.
+  void findRegionsWithEntry(BasicBlock *entry, BBtoBBMap *ShortCut);
+
+  // scanForRegions - Detects regions in F.
+  void scanForRegions(Function &F, BBtoBBMap *ShortCut);
+
+  // getTopMostParent - Get the top most parent with the same entry block.
+  Region *getTopMostParent(Region *region);
+
+  // buildRegionsTree - build the region hierarchy after all region detected.
+  void buildRegionsTree(DomTreeNode *N, Region *region);
+
+  // Calculate - detecte all regions in function and build the region tree.
+  void Calculate(Function& F);
+
+  void releaseMemory();
+
+  // updateStatistics - Update statistic about created regions.
+  void updateStatistics(Region *R);
+
+  // isSimple - Check if a region is a simple region with exactly one entry
+  // edge and exactly one exit edge.
+  bool isSimple(Region* R) const;
+
+public:
+  static char ID;
+  explicit RegionInfo();
+
+  ~RegionInfo();
+
+  /// @name FunctionPass interface
+  //@{
+  virtual bool runOnFunction(Function &F);
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+  virtual void print(raw_ostream &OS, const Module *) const;
+  virtual void verifyAnalysis() const;
+  //@}
+
+  /// @brief Get the smallest region that contains a BasicBlock.
+  ///
+  /// @param BB The basic block.
+  /// @return The smallest region, that contains BB or NULL, if there is no
+  /// region containing BB.
+  Region *getRegionFor(BasicBlock *BB) const;
+
+  /// @brief A shortcut for getRegionFor().
+  ///
+  /// @param BB The basic block.
+  /// @return The smallest region, that contains BB or NULL, if there is no
+  /// region containing BB.
+  Region *operator[](BasicBlock *BB) const;
+
+  /// @brief Return the exit of the maximal refined region, that starts at a
+  /// BasicBlock.
+  ///
+  /// @param BB The BasicBlock the refined region starts.
+  BasicBlock *getMaxRegionExit(BasicBlock *BB) const;
+
+  /// @brief Find the smallest region that contains two regions.
+  ///
+  /// @param A The first region.
+  /// @param B The second region.
+  /// @return The smallest region containing A and B.
+  Region *getCommonRegion(Region* A, Region *B) const;
+
+  /// @brief Find the smallest region that contains two basic blocks.
+  ///
+  /// @param A The first basic block.
+  /// @param B The second basic block.
+  /// @return The smallest region that contains A and B.
+  Region* getCommonRegion(BasicBlock* A, BasicBlock *B) const {
+    return getCommonRegion(getRegionFor(A), getRegionFor(B));
+  }
+
+  /// @brief Find the smallest region that contains a set of regions.
+  ///
+  /// @param Regions A vector of regions.
+  /// @return The smallest region that contains all regions in Regions.
+  Region* getCommonRegion(SmallVectorImpl<Region*> &Regions) const;
+
+  /// @brief Find the smallest region that contains a set of basic blocks.
+  ///
+  /// @param BBs A vector of basic blocks.
+  /// @return The smallest region that contains all basic blocks in BBS.
+  Region* getCommonRegion(SmallVectorImpl<BasicBlock*> &BBs) const;
+
+  Region *getTopLevelRegion() const {
+    return TopLevelRegion;
+  }
+
+  /// @brief Clear the Node Cache for all Regions.
+  ///
+  /// @see Region::clearNodeCache()
+  void clearNodeCache() {
+    if (TopLevelRegion)
+      TopLevelRegion->clearNodeCache();
+  }
+};
+
+inline raw_ostream &operator<<(raw_ostream &OS, const RegionNode &Node) {
+  if (Node.isSubRegion())
+    return OS << Node.getNodeAs<Region>()->getNameStr();
+  else
+    return OS << Node.getNodeAs<BasicBlock>()->getNameStr();
+}
+} // End llvm namespace
+#endif
+
diff --git a/include/llvm/Analysis/RegionIterator.h b/include/llvm/Analysis/RegionIterator.h
new file mode 100644
index 0000000..ced5b52
--- /dev/null
+++ b/include/llvm/Analysis/RegionIterator.h
@@ -0,0 +1,342 @@
+//===- RegionIterator.h - Iterators to iteratate over Regions ---*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// This file defines the iterators to iterate over the elements of a Region.
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_ANALYSIS_REGION_ITERATOR_H
+#define LLVM_ANALYSIS_REGION_ITERATOR_H
+
+#include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/Analysis/RegionInfo.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Support/raw_ostream.h"
+
+namespace llvm {
+//===----------------------------------------------------------------------===//
+/// @brief Hierachical RegionNode successor iterator.
+///
+/// This iterator iterates over all successors of a RegionNode.
+///
+/// For a BasicBlock RegionNode it skips all BasicBlocks that are not part of
+/// the parent Region.  Furthermore for BasicBlocks that start a subregion, a
+/// RegionNode representing the subregion is returned.
+///
+/// For a subregion RegionNode there is just one successor. The RegionNode
+/// representing the exit of the subregion.
+template<class NodeType>
+class RNSuccIterator : public std::iterator<std::forward_iterator_tag,
+                                           NodeType, ptrdiff_t>
+{
+  typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
+  // The iterator works in two modes, bb mode or region mode.
+  enum ItMode{
+    // In BB mode it returns all successors of this BasicBlock as its
+    // successors.
+    ItBB,
+    // In region mode there is only one successor, thats the regionnode mapping
+    // to the exit block of the regionnode
+    ItRgBegin, // At the beginning of the regionnode successor.
+    ItRgEnd    // At the end of the regionnode successor.
+  };
+
+  // Use two bit to represent the mode iterator.
+  PointerIntPair<NodeType*, 2, enum ItMode> Node;
+
+  // The block successor iterator.
+  succ_iterator BItor;
+
+  // advanceRegionSucc - A region node has only one successor. It reaches end
+  // once we advance it.
+  void advanceRegionSucc() {
+    assert(Node.getInt() == ItRgBegin && "Cannot advance region successor!");
+    Node.setInt(ItRgEnd);
+  }
+
+  NodeType* getNode() const{ return Node.getPointer(); }
+
+  // isRegionMode - Is the current iterator in region mode?
+  bool isRegionMode() const { return Node.getInt() != ItBB; }
+
+  // Get the immediate successor. This function may return a Basic Block
+  // RegionNode or a subregion RegionNode.
+  RegionNode* getISucc(BasicBlock* BB) const {
+    RegionNode *succ;
+    succ = getNode()->getParent()->getNode(BB);
+    assert(succ && "BB not in Region or entered subregion!");
+    return succ;
+  }
+
+  // getRegionSucc - Return the successor basic block of a SubRegion RegionNode.
+  inline BasicBlock* getRegionSucc() const {
+    assert(Node.getInt() == ItRgBegin && "Cannot get the region successor!");
+    return getNode()->template getNodeAs<Region>()->getExit();
+  }
+
+  // isExit - Is this the exit BB of the Region?
+  inline bool isExit(BasicBlock* BB) const {
+    return getNode()->getParent()->getExit() == BB;
+  }
+public:
+  typedef RNSuccIterator<NodeType> Self;
+
+  typedef typename super::pointer pointer;
+
+  /// @brief Create begin iterator of a RegionNode.
+  inline RNSuccIterator(NodeType* node)
+    : Node(node, node->isSubRegion() ? ItRgBegin : ItBB),
+    BItor(succ_begin(node->getEntry())) {
+
+
+    // Skip the exit block
+    if (!isRegionMode())
+      while (succ_end(node->getEntry()) != BItor && isExit(*BItor))
+        ++BItor;
+
+    if (isRegionMode() && isExit(getRegionSucc()))
+      advanceRegionSucc();
+  }
+
+  /// @brief Create an end iterator.
+  inline RNSuccIterator(NodeType* node, bool)
+    : Node(node, node->isSubRegion() ? ItRgEnd : ItBB),
+    BItor(succ_end(node->getEntry())) {}
+
+  inline bool operator==(const Self& x) const {
+    assert(isRegionMode() == x.isRegionMode() && "Broken iterator!");
+    if (isRegionMode())
+      return Node.getInt() == x.Node.getInt();
+    else
+      return BItor == x.BItor;
+  }
+
+  inline bool operator!=(const Self& x) const { return !operator==(x); }
+
+  inline pointer operator*() const {
+    BasicBlock* BB = isRegionMode() ? getRegionSucc() : *BItor;
+    assert(!isExit(BB) && "Iterator out of range!");
+    return getISucc(BB);
+  }
+
+  inline Self& operator++() {
+    if(isRegionMode()) {
+      // The Region only has 1 successor.
+      advanceRegionSucc();
+    } else {
+      // Skip the exit.
+      do
+        ++BItor;
+      while (BItor != succ_end(getNode()->getEntry())
+          && isExit(*BItor));
+    }
+    return *this;
+  }
+
+  inline Self operator++(int) {
+    Self tmp = *this;
+    ++*this;
+    return tmp;
+  }
+
+  inline const Self &operator=(const Self &I) {
+    if (this != &I) {
+      assert(getNode()->getParent() == I.getNode()->getParent()
+             && "Cannot assign iterators of two different regions!");
+      Node = I.Node;
+      BItor = I.BItor;
+    }
+    return *this;
+  }
+};
+
+
+//===----------------------------------------------------------------------===//
+/// @brief Flat RegionNode iterator.
+///
+/// The Flat Region iterator will iterate over all BasicBlock RegionNodes that
+/// are contained in the Region and its subregions. This is close to a virtual
+/// control flow graph of the Region.
+template<class NodeType>
+class RNSuccIterator<FlatIt<NodeType> >
+  : public std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t>
+{
+  typedef std::iterator<std::forward_iterator_tag, NodeType, ptrdiff_t> super;
+  NodeType* Node;
+  succ_iterator Itor;
+
+public:
+  typedef RNSuccIterator<FlatIt<NodeType> > Self;
+  typedef typename super::pointer pointer;
+
+  /// @brief Create the iterator from a RegionNode.
+  ///
+  /// Note that the incoming node must be a bb node, otherwise it will trigger
+  /// an assertion when we try to get a BasicBlock.
+  inline RNSuccIterator(NodeType* node) : Node(node),
+    Itor(succ_begin(node->getEntry())) {
+      assert(!Node->isSubRegion()
+             && "Subregion node not allowed in flat iterating mode!");
+      assert(Node->getParent() && "A BB node must have a parent!");
+
+      // Skip the exit block of the iterating region.
+      while (succ_end(Node->getEntry()) != Itor
+          && Node->getParent()->getExit() == *Itor)
+        ++Itor;
+  }
+  /// @brief Create an end iterator
+  inline RNSuccIterator(NodeType* node, bool) : Node(node),
+    Itor(succ_end(node->getEntry())) {
+      assert(!Node->isSubRegion()
+             && "Subregion node not allowed in flat iterating mode!");
+  }
+
+  inline bool operator==(const Self& x) const {
+    assert(Node->getParent() == x.Node->getParent()
+           && "Cannot compare iterators of different regions!");
+
+    return Itor == x.Itor && Node == x.Node;
+  }
+
+  inline bool operator!=(const Self& x) const { return !operator==(x); }
+
+  inline pointer operator*() const {
+    BasicBlock* BB = *Itor;
+
+    // Get the iterating region.
+    Region* Parent = Node->getParent();
+
+    // The only case that the successor reaches out of the region is it reaches
+    // the exit of the region.
+    assert(Parent->getExit() != BB && "iterator out of range!");
+
+    return Parent->getBBNode(BB);
+  }
+
+  inline Self& operator++() {
+    // Skip the exit block of the iterating region.
+    do
+      ++Itor;
+    while (Itor != succ_end(Node->getEntry())
+        && Node->getParent()->getExit() == *Itor);
+
+    return *this;
+  }
+
+  inline Self operator++(int) {
+    Self tmp = *this;
+    ++*this;
+    return tmp;
+  }
+
+  inline const Self &operator=(const Self &I) {
+    if (this != &I) {
+      assert(Node->getParent() == I.Node->getParent()
+             && "Cannot assign iterators to two different regions!");
+      Node = I.Node;
+      Itor = I.Itor;
+    }
+    return *this;
+  }
+};
+
+template<class NodeType>
+inline RNSuccIterator<NodeType> succ_begin(NodeType* Node) {
+  return RNSuccIterator<NodeType>(Node);
+}
+
+template<class NodeType>
+inline RNSuccIterator<NodeType> succ_end(NodeType* Node) {
+  return RNSuccIterator<NodeType>(Node, true);
+}
+
+//===--------------------------------------------------------------------===//
+// RegionNode GraphTraits specialization so the bbs in the region can be
+// iterate by generic graph iterators.
+//
+// NodeT can either be region node or const region node, otherwise child_begin
+// and child_end fail.
+
+#define RegionNodeGraphTraits(NodeT) \
+  template<> struct GraphTraits<NodeT*> { \
+  typedef NodeT NodeType; \
+  typedef RNSuccIterator<NodeType> ChildIteratorType; \
+  static NodeType *getEntryNode(NodeType* N) { return N; } \
+  static inline ChildIteratorType child_begin(NodeType *N) { \
+    return RNSuccIterator<NodeType>(N); \
+  } \
+  static inline ChildIteratorType child_end(NodeType *N) { \
+    return RNSuccIterator<NodeType>(N, true); \
+  } \
+}; \
+template<> struct GraphTraits<FlatIt<NodeT*> > { \
+  typedef NodeT NodeType; \
+  typedef RNSuccIterator<FlatIt<NodeT> > ChildIteratorType; \
+  static NodeType *getEntryNode(NodeType* N) { return N; } \
+  static inline ChildIteratorType child_begin(NodeType *N) { \
+    return RNSuccIterator<FlatIt<NodeType> >(N); \
+  } \
+  static inline ChildIteratorType child_end(NodeType *N) { \
+    return RNSuccIterator<FlatIt<NodeType> >(N, true); \
+  } \
+}
+
+#define RegionGraphTraits(RegionT, NodeT) \
+template<> struct GraphTraits<RegionT*> \
+  : public GraphTraits<NodeT*> { \
+  typedef df_iterator<NodeType*> nodes_iterator; \
+  static NodeType *getEntryNode(RegionT* R) { \
+    return R->getNode(R->getEntry()); \
+  } \
+  static nodes_iterator nodes_begin(RegionT* R) { \
+    return nodes_iterator::begin(getEntryNode(R)); \
+  } \
+  static nodes_iterator nodes_end(RegionT* R) { \
+    return nodes_iterator::end(getEntryNode(R)); \
+  } \
+}; \
+template<> struct GraphTraits<FlatIt<RegionT*> > \
+  : public GraphTraits<FlatIt<NodeT*> > { \
+  typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false, \
+  GraphTraits<FlatIt<NodeType*> > > nodes_iterator; \
+  static NodeType *getEntryNode(RegionT* R) { \
+    return R->getBBNode(R->getEntry()); \
+  } \
+  static nodes_iterator nodes_begin(RegionT* R) { \
+    return nodes_iterator::begin(getEntryNode(R)); \
+  } \
+  static nodes_iterator nodes_end(RegionT* R) { \
+    return nodes_iterator::end(getEntryNode(R)); \
+  } \
+}
+
+RegionNodeGraphTraits(RegionNode);
+RegionNodeGraphTraits(const RegionNode);
+
+RegionGraphTraits(Region, RegionNode);
+RegionGraphTraits(const Region, const RegionNode);
+
+template <> struct GraphTraits<RegionInfo*>
+  : public GraphTraits<FlatIt<RegionNode*> > {
+  typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
+                      GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
+
+  static NodeType *getEntryNode(RegionInfo *RI) {
+    return GraphTraits<FlatIt<Region*> >::getEntryNode(RI->getTopLevelRegion());
+  }
+  static nodes_iterator nodes_begin(RegionInfo* RI) {
+    return nodes_iterator::begin(getEntryNode(RI));
+  }
+  static nodes_iterator nodes_end(RegionInfo *RI) {
+    return nodes_iterator::end(getEntryNode(RI));
+  }
+};
+
+} // End namespace llvm
+
+#endif
diff --git a/include/llvm/Analysis/RegionPrinter.h b/include/llvm/Analysis/RegionPrinter.h
new file mode 100644
index 0000000..758748a
--- /dev/null
+++ b/include/llvm/Analysis/RegionPrinter.h
@@ -0,0 +1,26 @@
+//===-- RegionPrinter.h - Region printer external interface -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines external functions that can be called to explicitly
+// instantiate the region printer.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_REGIONPRINTER_H
+#define LLVM_ANALYSIS_REGIONPRINTER_H
+
+namespace llvm {
+  class FunctionPass;
+  FunctionPass *createRegionViewerPass();
+  FunctionPass *createRegionOnlyViewerPass();
+  FunctionPass *createRegionPrinterPass();
+  FunctionPass *createRegionOnlyPrinterPass();
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 8da3af0..1fa94e9 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -44,12 +44,17 @@ namespace llvm {
   class Loop;
   class LoopInfo;
   class Operator;
+  class SCEVUnknown;
+  class SCEV;
+  template<> struct FoldingSetTrait<SCEV>;
 
   /// SCEV - This class represents an analyzed expression in the program.  These
   /// are opaque objects that the client is not allowed to do much with
   /// directly.
   ///
   class SCEV : public FoldingSetNode {
+    friend struct FoldingSetTrait<SCEV>;
+
     /// FastID - A reference to an Interned FoldingSetNodeID for this node.
     /// The ScalarEvolution's BumpPtrAllocator holds the data.
     FoldingSetNodeIDRef FastID;
@@ -73,9 +78,6 @@ namespace llvm {
 
     unsigned getSCEVType() const { return SCEVType; }
 
-    /// Profile - FoldingSet support.
-    void Profile(FoldingSetNodeID& ID) { ID = FastID; }
-
     /// isLoopInvariant - Return true if the value of this SCEV is unchanging in
     /// the specified loop.
     virtual bool isLoopInvariant(const Loop *L) const = 0;
@@ -125,6 +127,21 @@ namespace llvm {
     void dump() const;
   };
 
+  // Specialize FoldingSetTrait for SCEV to avoid needing to compute
+  // temporary FoldingSetNodeID values.
+  template<> struct FoldingSetTrait<SCEV> : DefaultFoldingSetTrait<SCEV> {
+    static void Profile(const SCEV &X, FoldingSetNodeID& ID) {
+      ID = X.FastID;
+    }
+    static bool Equals(const SCEV &X, const FoldingSetNodeID &ID,
+                       FoldingSetNodeID &TempID) {
+      return ID == X.FastID;
+    }
+    static unsigned ComputeHash(const SCEV &X, FoldingSetNodeID &TempID) {
+      return X.FastID.ComputeHash();
+    }
+  };
+
   inline raw_ostream &operator<<(raw_ostream &OS, const SCEV &S) {
     S.print(OS);
     return OS;
@@ -175,6 +192,7 @@ namespace llvm {
 
     friend class SCEVCallbackVH;
     friend class SCEVExpander;
+    friend class SCEVUnknown;
 
     /// F - The function we are analyzing.
     ///
@@ -196,9 +214,14 @@ namespace llvm {
     /// counts and things.
     SCEVCouldNotCompute CouldNotCompute;
 
-    /// Scalars - This is a cache of the scalars we have analyzed so far.
+    /// ValueExprMapType - The typedef for ValueExprMap.
     ///
-    std::map<SCEVCallbackVH, const SCEV *> Scalars;
+    typedef DenseMap<SCEVCallbackVH, const SCEV *, DenseMapInfo<Value *> >
+      ValueExprMapType;
+
+    /// ValueExprMap - This is a cache of the values we have analyzed so far.
+    ///
+    ValueExprMapType ValueExprMap;
 
     /// BackedgeTakenInfo - Information about the backedge-taken count
     /// of a loop. This currently includes an exact count and a maximum count.
@@ -263,7 +286,7 @@ namespace llvm {
 
     /// ForgetSymbolicValue - This looks up computed SCEV values for all
     /// instructions that depend on the given instruction and removes them from
-    /// the Scalars map if they reference SymName. This is used during PHI
+    /// the ValueExprMap map if they reference SymName. This is used during PHI
     /// resolution.
     void ForgetSymbolicName(Instruction *I, const SCEV *SymName);
 
@@ -350,10 +373,11 @@ namespace llvm {
     std::pair<BasicBlock *, BasicBlock *>
     getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
 
-    /// isImpliedCond - Test whether the condition described by Pred, LHS,
-    /// and RHS is true whenever the given Cond value evaluates to true.
-    bool isImpliedCond(Value *Cond, ICmpInst::Predicate Pred,
+    /// isImpliedCond - Test whether the condition described by Pred, LHS, and
+    /// RHS is true whenever the given FoundCondValue value evaluates to true.
+    bool isImpliedCond(ICmpInst::Predicate Pred,
                        const SCEV *LHS, const SCEV *RHS,
+                       Value *FoundCondValue,
                        bool Inverse);
 
     /// isImpliedCondOperands - Test whether the condition described by Pred,
@@ -659,6 +683,11 @@ namespace llvm {
   private:
     FoldingSet<SCEV> UniqueSCEVs;
     BumpPtrAllocator SCEVAllocator;
+
+    /// FirstUnknown - The head of a linked list of all SCEVUnknown
+    /// values that have been allocated. This is used by releaseMemory
+    /// to locate them all and call their destructors.
+    SCEVUnknown *FirstUnknown;
   };
 }
 
diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
index 9501555..4b02f82 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -18,6 +18,7 @@
 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
 #include "llvm/Support/IRBuilder.h"
 #include "llvm/Support/TargetFolder.h"
+#include "llvm/Support/ValueHandle.h"
 #include <set>
 
 namespace llvm {
@@ -31,8 +32,8 @@ namespace llvm {
     ScalarEvolution &SE;
     std::map<std::pair<const SCEV *, Instruction *>, AssertingVH<Value> >
       InsertedExpressions;
-    std::set<Value*> InsertedValues;
-    std::set<Value*> InsertedPostIncValues;
+    std::set<AssertingVH<Value> > InsertedValues;
+    std::set<AssertingVH<Value> > InsertedPostIncValues;
 
     /// PostIncLoops - Addrecs referring to any of the given loops are expanded
     /// in post-inc mode. For example, expanding {1,+,1}<L> in post-inc mode
@@ -70,13 +71,18 @@ namespace llvm {
     /// 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(); }
+    void clear() {
+      InsertedExpressions.clear();
+      InsertedValues.clear();
+      InsertedPostIncValues.clear();
+    }
 
     /// 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);
+    PHINode *getOrInsertCanonicalInductionVariable(const Loop *L,
+                                                   const Type *Ty);
 
     /// expandCodeFor - Insert code to directly compute the specified SCEV
     /// expression into the program.  The inserted code is inserted into the
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 7424203..4213a28 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -202,33 +202,14 @@ namespace llvm {
     op_iterator op_begin() const { return Operands; }
     op_iterator op_end() const { return Operands + NumOperands; }
 
-    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;
-    }
+    virtual bool isLoopInvariant(const Loop *L) const;
 
     // hasComputableLoopEvolution - N-ary 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;
-    }
+    virtual bool hasComputableLoopEvolution(const Loop *L) const;
 
-    virtual bool hasOperand(const SCEV *O) const {
-      for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
-        if (O == getOperand(i) || getOperand(i)->hasOperand(O))
-          return true;
-      return false;
-    }
+    virtual bool hasOperand(const SCEV *O) const;
 
     bool dominates(BasicBlock *BB, DominatorTree *DT) const;
 
@@ -520,15 +501,28 @@ namespace llvm {
   /// value, and only represent it as its LLVM Value.  This is the "bottom"
   /// value for the analysis.
   ///
-  class SCEVUnknown : public SCEV {
+  class SCEVUnknown : public SCEV, private CallbackVH {
     friend class ScalarEvolution;
 
-    Value *V;
-    SCEVUnknown(const FoldingSetNodeIDRef ID, Value *v) :
-      SCEV(ID, scUnknown), V(v) {}
+    // Implement CallbackVH.
+    virtual void deleted();
+    virtual void allUsesReplacedWith(Value *New);
+
+    /// SE - The parent ScalarEvolution value. This is used to update
+    /// the parent's maps when the value associated with a SCEVUnknown
+    /// is deleted or RAUW'd.
+    ScalarEvolution *SE;
+
+    /// Next - The next pointer in the linked list of all
+    /// SCEVUnknown instances owned by a ScalarEvolution.
+    SCEVUnknown *Next;
+
+    SCEVUnknown(const FoldingSetNodeIDRef ID, Value *V,
+                ScalarEvolution *se, SCEVUnknown *next) :
+      SCEV(ID, scUnknown), CallbackVH(V), SE(se), Next(next) {}
 
   public:
-    Value *getValue() const { return V; }
+    Value *getValue() const { return getValPtr(); }
 
     /// isSizeOf, isAlignOf, isOffsetOf - Test whether this is a special
     /// constant representing a type size, alignment, or field offset in
diff --git a/include/llvm/Analysis/ValueTracking.h b/include/llvm/Analysis/ValueTracking.h
index b9634f0..7b6026f 100644
--- a/include/llvm/Analysis/ValueTracking.h
+++ b/include/llvm/Analysis/ValueTracking.h
@@ -77,25 +77,6 @@ namespace llvm {
   ///
   bool CannotBeNegativeZero(const Value *V, unsigned Depth = 0);
 
-  /// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose
-  /// it into a base pointer with a constant offset and a number of scaled
-  /// symbolic offsets.
-  ///
-  /// The scaled symbolic offsets (represented by pairs of a Value* and a scale
-  /// in the VarIndices vector) are Value*'s that are known to be scaled by the
-  /// specified amount, but which may have other unrepresented high bits. As
-  /// such, the gep cannot necessarily be reconstructed from its decomposed
-  /// form.
-  ///
-  /// When TargetData is around, this function is capable of analyzing
-  /// everything that Value::getUnderlyingObject() can look through.  When not,
-  /// it just looks through pointer casts.
-  ///
-  const Value *DecomposeGEPExpression(const Value *V, int64_t &BaseOffs,
-                 SmallVectorImpl<std::pair<const Value*, int64_t> > &VarIndices,
-                                      const TargetData *TD);
-    
-  
   
   /// FindInsertedValue - Given an aggregrate and an sequence of indices, see if
   /// the scalar value indexed is already around as a register, for example if
author	dim <dim@FreeBSD.org>	2010-09-17 15:48:55 +0000
committer	dim <dim@FreeBSD.org>	2010-09-17 15:48:55 +0000
commit	5d5cc59cc77afe655b3707cb0e69e0827b444cad (patch)
tree	36453626c792cccd91f783a38a169d610a6b9db9 /include/llvm/Analysis
parent	786a18553586229ad99ecb5ecde8a9d914c45e27 (diff)
download	FreeBSD-src-5d5cc59cc77afe655b3707cb0e69e0827b444cad.zip FreeBSD-src-5d5cc59cc77afe655b3707cb0e69e0827b444cad.tar.gz