9 files changed, 144 insertions, 23 deletions
diff --git a/include/llvm/Analysis/AliasAnalysis.h b/include/llvm/Analysis/AliasAnalysis.h
index 8f9708b..5d8edd1 100644
--- a/include/llvm/Analysis/AliasAnalysis.h
+++ b/include/llvm/Analysis/AliasAnalysis.h
@@ -38,6 +38,7 @@
 #define LLVM_ANALYSIS_ALIAS_ANALYSIS_H
 
 #include "llvm/Support/CallSite.h"
+#include "llvm/ADT/DenseMap.h"
 
 namespace llvm {
 
@@ -488,6 +489,32 @@ public:
   }
 };
 
+// Specialize DenseMapInfo for Location.
+template<>
+struct DenseMapInfo<AliasAnalysis::Location> {
+  static inline AliasAnalysis::Location getEmptyKey() {
+    return
+      AliasAnalysis::Location(DenseMapInfo<const Value *>::getEmptyKey(),
+                              0, 0);
+  }
+  static inline AliasAnalysis::Location getTombstoneKey() {
+    return
+      AliasAnalysis::Location(DenseMapInfo<const Value *>::getTombstoneKey(),
+                              0, 0);
+  }
+  static unsigned getHashValue(const AliasAnalysis::Location &Val) {
+    return DenseMapInfo<const Value *>::getHashValue(Val.Ptr) ^
+           DenseMapInfo<uint64_t>::getHashValue(Val.Size) ^
+           DenseMapInfo<const MDNode *>::getHashValue(Val.TBAATag);
+  }
+  static bool isEqual(const AliasAnalysis::Location &LHS,
+                      const AliasAnalysis::Location &RHS) {
+    return LHS.Ptr == RHS.Ptr &&
+           LHS.Size == RHS.Size &&
+           LHS.TBAATag == RHS.TBAATag;
+  }
+};
+
 /// isNoAliasCall - Return true if this pointer is returned by a noalias
 /// function.
 bool isNoAliasCall(const Value *V);
diff --git a/include/llvm/Analysis/BranchProbabilityInfo.h b/include/llvm/Analysis/BranchProbabilityInfo.h
new file mode 100644
index 0000000..91f289d
--- /dev/null
+++ b/include/llvm/Analysis/BranchProbabilityInfo.h
@@ -0,0 +1,78 @@
+//===--- BranchProbabilityInfo.h - Branch Probability Analysis --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass is used to evaluate branch probabilties.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
+#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
+
+#include "llvm/InitializePasses.h"
+#include "llvm/Support/BranchProbability.h"
+#include "llvm/Analysis/LoopInfo.h"
+
+namespace llvm {
+
+class raw_ostream;
+
+class BranchProbabilityInfo : public FunctionPass {
+
+  // Default weight value. Used when we don't have information about the edge.
+  static const uint32_t DEFAULT_WEIGHT = 16;
+
+  typedef std::pair<BasicBlock *, BasicBlock *> Edge;
+
+  DenseMap<Edge, uint32_t> Weights;
+
+  // Get sum of the block successors' weights.
+  uint32_t getSumForBlock(BasicBlock *BB) const;
+
+public:
+  static char ID;
+
+  BranchProbabilityInfo() : FunctionPass(ID) {
+    initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry());
+  }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.addRequired<LoopInfo>();
+    AU.setPreservesAll();
+  }
+
+  bool runOnFunction(Function &F);
+
+  // Returned value is between 1 and UINT32_MAX. Look at
+  // BranchProbabilityInfo.cpp for details.
+  uint32_t getEdgeWeight(BasicBlock *Src, BasicBlock *Dst) const;
+
+  // Look at BranchProbabilityInfo.cpp for details. Use it with caution!
+  void setEdgeWeight(BasicBlock *Src, BasicBlock *Dst, uint32_t Weight);
+
+  // A 'Hot' edge is an edge which probability is >= 80%.
+  bool isEdgeHot(BasicBlock *Src, BasicBlock *Dst) const;
+
+  // Return a hot successor for the block BB or null if there isn't one.
+  BasicBlock *getHotSucc(BasicBlock *BB) const;
+
+  // Return a probability as a fraction between 0 (0% probability) and
+  // 1 (100% probability), however the value is never equal to 0, and can be 1
+  // only iff SRC block has only one successor.
+  BranchProbability getEdgeProbability(BasicBlock *Src, BasicBlock *Dst) const;
+
+  // Print value between 0 (0% probability) and 1 (100% probability),
+  // however the value is never equal to 0, and can be 1 only iff SRC block
+  // has only one successor.
+  raw_ostream &printEdgeProbability(raw_ostream &OS, BasicBlock *Src,
+                                    BasicBlock *Dst) const;
+};
+
+}
+
+#endif
diff --git a/include/llvm/Analysis/CallGraph.h b/include/llvm/Analysis/CallGraph.h
index 089f322..fb77da7 100644
--- a/include/llvm/Analysis/CallGraph.h
+++ b/include/llvm/Analysis/CallGraph.h
@@ -259,6 +259,9 @@ public:
   /// addCalledFunction - Add a function to the list of functions called by this
   /// one.
   void addCalledFunction(CallSite CS, CallGraphNode *M) {
+    assert(!CS.getInstruction() ||
+           !CS.getCalledFunction() ||
+           !CS.getCalledFunction()->isIntrinsic());
     CalledFunctions.push_back(std::make_pair(CS.getInstruction(), M));
     M->AddRef();
   }
diff --git a/include/llvm/Analysis/DIBuilder.h b/include/llvm/Analysis/DIBuilder.h
index 5846dbf..96c6587 100644
--- a/include/llvm/Analysis/DIBuilder.h
+++ b/include/llvm/Analysis/DIBuilder.h
@@ -117,8 +117,9 @@ namespace llvm {
     /// @param Name        Typedef name.
     /// @param File        File where this type is defined.
     /// @param LineNo      Line number.
+    /// @param Context     The surrounding context for the typedef.
     DIType createTypedef(DIType Ty, StringRef Name, DIFile File, 
-                         unsigned LineNo);
+                         unsigned LineNo, DIDescriptor Context);
 
     /// createFriend - Create debugging information entry for a 'friend'.
     DIType createFriend(DIType Ty, DIType FriendTy);
diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h
index c6cc8f7..fbee5a6 100644
--- a/include/llvm/Analysis/DebugInfo.h
+++ b/include/llvm/Analysis/DebugInfo.h
@@ -49,15 +49,16 @@ namespace llvm {
   class DIDescriptor {
   public:
     enum {
-      FlagPrivate          = 1 << 0,
-      FlagProtected        = 1 << 1,
-      FlagFwdDecl          = 1 << 2,
-      FlagAppleBlock       = 1 << 3,
-      FlagBlockByrefStruct = 1 << 4,
-      FlagVirtual          = 1 << 5,
-      FlagArtificial       = 1 << 6,
-      FlagExplicit         = 1 << 7,
-      FlagPrototyped       = 1 << 8
+      FlagPrivate            = 1 << 0,
+      FlagProtected          = 1 << 1,
+      FlagFwdDecl            = 1 << 2,
+      FlagAppleBlock         = 1 << 3,
+      FlagBlockByrefStruct   = 1 << 4,
+      FlagVirtual            = 1 << 5,
+      FlagArtificial         = 1 << 6,
+      FlagExplicit           = 1 << 7,
+      FlagPrototyped         = 1 << 8,
+      FlagObjcClassComplete  = 1 << 9
     };
   protected:
     const MDNode *DbgNode;
@@ -271,6 +272,9 @@ namespace llvm {
     bool isArtificial() const {
       return (getFlags() & FlagArtificial) != 0;
     }
+    bool isObjcClassComplete() const {
+      return (getFlags() & FlagObjcClassComplete) != 0;
+    }
     bool isValid() const {
       return DbgNode && (isBasicType() || isDerivedType() || isCompositeType());
     }
diff --git a/include/llvm/Analysis/FindUsedTypes.h b/include/llvm/Analysis/FindUsedTypes.h
index fc57e1a..3e5da57 100644
--- a/include/llvm/Analysis/FindUsedTypes.h
+++ b/include/llvm/Analysis/FindUsedTypes.h
@@ -14,8 +14,8 @@
 #ifndef LLVM_ANALYSIS_FINDUSEDTYPES_H
 #define LLVM_ANALYSIS_FINDUSEDTYPES_H
 
+#include "llvm/ADT/SetVector.h"
 #include "llvm/Pass.h"
-#include <set>
 
 namespace llvm {
 
@@ -23,7 +23,7 @@ class Type;
 class Value;
 
 class FindUsedTypes : public ModulePass {
-  std::set<const Type *> UsedTypes;
+  SetVector<const Type *> UsedTypes;
 public:
   static char ID; // Pass identification, replacement for typeid
   FindUsedTypes() : ModulePass(ID) {
@@ -33,7 +33,7 @@ public:
   /// 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; }
+  const SetVector<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
diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h
index e56d24d..1b78fe4 100644
--- a/include/llvm/Analysis/IVUsers.h
+++ b/include/llvm/Analysis/IVUsers.h
@@ -37,8 +37,8 @@ class TargetData;
 class IVStrideUse : public CallbackVH, public ilist_node<IVStrideUse> {
   friend class IVUsers;
 public:
-  IVStrideUse(IVUsers *P, Instruction* U, Value *O)
-    : CallbackVH(U), Parent(P), OperandValToReplace(O) {
+  IVStrideUse(IVUsers *P, Instruction* U, Value *O, Value *PN)
+    : CallbackVH(U), Parent(P), OperandValToReplace(O), Phi(PN) {
   }
 
   /// getUser - Return the user instruction for this use.
@@ -51,6 +51,11 @@ public:
     setValPtr(NewUser);
   }
 
+  /// getPhi - Return the phi node that represents this IV.
+  PHINode *getPhi() const {
+    return cast<PHINode>(Phi);
+  }
+
   /// getOperandValToReplace - Return the Value of the operand in the user
   /// instruction that this IVStrideUse is representing.
   Value *getOperandValToReplace() const {
@@ -81,6 +86,9 @@ private:
   /// that this IVStrideUse is representing.
   WeakVH OperandValToReplace;
 
+  /// Phi - The loop header phi that represents this IV.
+  WeakVH Phi;
+
   /// PostIncLoops - The set of loops for which Expr has been adjusted to
   /// use post-inc mode. This corresponds with SCEVExpander's post-inc concept.
   PostIncLoopSet PostIncLoops;
@@ -143,9 +151,9 @@ public:
   /// AddUsersIfInteresting - Inspect the specified Instruction.  If it is a
   /// reducible SCEV, recursively add its users to the IVUsesByStride set and
   /// return true.  Otherwise, return false.
-  bool AddUsersIfInteresting(Instruction *I);
+  bool AddUsersIfInteresting(Instruction *I, PHINode *Phi);
 
-  IVStrideUse &AddUser(Instruction *User, Value *Operand);
+  IVStrideUse &AddUser(Instruction *User, Value *Operand, PHINode *Phi);
 
   /// getReplacementExpr - Return a SCEV expression which computes the
   /// value of the OperandValToReplace of the given IVStrideUse.
diff --git a/include/llvm/Analysis/RegionPass.h b/include/llvm/Analysis/RegionPass.h
index 5403e09..1a93859 100644
--- a/include/llvm/Analysis/RegionPass.h
+++ b/include/llvm/Analysis/RegionPass.h
@@ -109,7 +109,7 @@ public:
   /// @brief Print passes managed by this manager.
   void dumpPassStructure(unsigned Offset);
 
-  /// @brief Print passes contained by this manager.
+  /// @brief Get passes contained by this manager.
   Pass *getContainedPass(unsigned N) {
     assert(N < PassVector.size() && "Pass number out of range!");
     Pass *FP = static_cast<Pass *>(PassVector[N]);
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index a62f6a8..554524a 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -270,30 +270,30 @@ namespace llvm {
 
     /// BackedgeTakenCounts - Cache the backedge-taken count of the loops for
     /// this function as they are computed.
-    std::map<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts;
+    DenseMap<const Loop*, BackedgeTakenInfo> BackedgeTakenCounts;
 
     /// ConstantEvolutionLoopExitValue - This map contains entries for all of
     /// the PHI instructions that we attempt to compute constant evolutions for.
     /// This allows us to avoid potentially expensive recomputation of these
     /// properties.  An instruction maps to null if we are unable to compute its
     /// exit value.
-    std::map<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
+    DenseMap<PHINode*, Constant*> ConstantEvolutionLoopExitValue;
 
     /// ValuesAtScopes - This map contains entries for all the expressions
     /// that we attempt to compute getSCEVAtScope information for, which can
     /// be expensive in extreme cases.
-    std::map<const SCEV *,
+    DenseMap<const SCEV *,
              std::map<const Loop *, const SCEV *> > ValuesAtScopes;
 
     /// LoopDispositions - Memoized computeLoopDisposition results.
-    std::map<const SCEV *,
+    DenseMap<const SCEV *,
              std::map<const Loop *, LoopDisposition> > LoopDispositions;
 
     /// computeLoopDisposition - Compute a LoopDisposition value.
     LoopDisposition computeLoopDisposition(const SCEV *S, const Loop *L);
 
     /// BlockDispositions - Memoized computeBlockDisposition results.
-    std::map<const SCEV *,
+    DenseMap<const SCEV *,
              std::map<const BasicBlock *, BlockDisposition> > BlockDispositions;
 
     /// computeBlockDisposition - Compute a BlockDisposition value.