vendor/llvm/llvm-r74788

8 files changed, 123 insertions, 75 deletions

diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h
index 20de3a4575ef..06110d040d62 100644
--- a/include/llvm/Analysis/DebugInfo.h
+++ b/include/llvm/Analysis/DebugInfo.h
@@ -33,6 +33,11 @@ namespace llvm {
   class Value;
   struct DbgStopPointInst;
   struct DbgDeclareInst;
+  struct DbgFuncStartInst;
+  struct DbgRegionStartInst;
+  struct DbgRegionEndInst;
+  class DebugLoc;
+  class DebugLocTracker;
   class Instruction;
 
   class DIDescriptor {
@@ -548,6 +553,47 @@ namespace llvm {
                                SmallVector<GlobalVariable *, 4> &GlobalVars,
                                SmallVector<GlobalVariable *, 4> &Subprograms);
 
+  /// isValidDebugInfoIntrinsic - Return true if SPI is a valid debug 
+  /// info intrinsic.
+  bool isValidDebugInfoIntrinsic(DbgStopPointInst &SPI, 
+                                 CodeGenOpt::Level OptLev);
+
+  /// isValidDebugInfoIntrinsic - Return true if FSI is a valid debug 
+  /// info intrinsic.
+  bool isValidDebugInfoIntrinsic(DbgFuncStartInst &FSI,
+                                 CodeGenOpt::Level OptLev);
+
+  /// isValidDebugInfoIntrinsic - Return true if RSI is a valid debug 
+  /// info intrinsic.
+  bool isValidDebugInfoIntrinsic(DbgRegionStartInst &RSI,
+                                 CodeGenOpt::Level OptLev);
+
+  /// isValidDebugInfoIntrinsic - Return true if REI is a valid debug 
+  /// info intrinsic.
+  bool isValidDebugInfoIntrinsic(DbgRegionEndInst &REI,
+                                 CodeGenOpt::Level OptLev);
+
+  /// isValidDebugInfoIntrinsic - Return true if DI is a valid debug 
+  /// info intrinsic.
+  bool isValidDebugInfoIntrinsic(DbgDeclareInst &DI,
+                                 CodeGenOpt::Level OptLev);
+
+  /// ExtractDebugLocation - Extract debug location information 
+  /// from llvm.dbg.stoppoint intrinsic.
+  DebugLoc ExtractDebugLocation(DbgStopPointInst &SPI,
+                                DebugLocTracker &DebugLocInfo);
+
+  /// ExtractDebugLocation - Extract debug location information 
+  /// from llvm.dbg.func_start intrinsic.
+  DebugLoc ExtractDebugLocation(DbgFuncStartInst &FSI,
+                                DebugLocTracker &DebugLocInfo);
+
+  /// isInlinedFnStart - Return true if FSI is starting an inlined function.
+  bool isInlinedFnStart(DbgFuncStartInst &FSI, const Function *CurrentFn);
+
+  /// isInlinedFnEnd - Return true if REI is ending an inlined function.
+  bool isInlinedFnEnd(DbgRegionEndInst &REI, const Function *CurrentFn);
+
 } // end namespace llvm
 
 #endif
diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h
index 347e239d8ea7..366d492b1145 100644
--- a/include/llvm/Analysis/Dominators.h
+++ b/include/llvm/Analysis/Dominators.h
@@ -618,8 +618,9 @@ protected:
   }
   
   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
-    if (DomTreeNodeBase<NodeT> *BBNode = this->DomTreeNodes[BB])
-      return BBNode;
+    typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.find(BB);
+    if (I != this->DomTreeNodes.end() && I->second)
+      return I->second;
 
     // Haven't calculated this node yet?  Get or calculate the node for the
     // immediate dominator.
diff --git a/include/llvm/Analysis/IVUsers.h b/include/llvm/Analysis/IVUsers.h
index 30a457ace811..40396e2fcaf2 100644
--- a/include/llvm/Analysis/IVUsers.h
+++ b/include/llvm/Analysis/IVUsers.h
@@ -17,7 +17,7 @@
 
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
-#include <llvm/ADT/SmallVector.h>
+#include "llvm/ADT/SmallVector.h"
 #include <map>
 
 namespace llvm {
diff --git a/include/llvm/Analysis/LoopDependenceAnalysis.h b/include/llvm/Analysis/LoopDependenceAnalysis.h
index c69bc60bead2..67da2e7fbc1b 100644
--- a/include/llvm/Analysis/LoopDependenceAnalysis.h
+++ b/include/llvm/Analysis/LoopDependenceAnalysis.h
@@ -21,24 +21,35 @@
 #define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
 
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Support/raw_ostream.h"
+#include <iosfwd>
 
 namespace llvm {
 
+  class AliasAnalysis;
   class AnalysisUsage;
-  class LoopPass;
   class ScalarEvolution;
+  class Value;
 
   class LoopDependenceAnalysis : public LoopPass {
     Loop *L;
+    AliasAnalysis *AA;
     ScalarEvolution *SE;
 
   public:
     static char ID; // Class identification, replacement for typeinfo
     LoopDependenceAnalysis() : LoopPass(&ID) {}
 
+    /// TODO: docs
+    bool isDependencePair(const Value*, const Value*) const;
+    bool depends(Value*, Value*);
+
     bool runOnLoop(Loop*, LPPassManager&);
 
     virtual void getAnalysisUsage(AnalysisUsage&) const;
+
+    void print(raw_ostream&, const Module* = 0) const;
+    virtual void print(std::ostream&, const Module* = 0) const;
   }; // class LoopDependenceAnalysis
 
 
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index 9e5f57e9a199..8b293cb7b986 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -662,7 +662,9 @@ class LoopInfoBase {
   std::map<BlockT*, LoopBase<BlockT>*> BBMap;
   std::vector<LoopBase<BlockT>*> TopLevelLoops;
   friend class LoopBase<BlockT>;
-  
+
+  void operator=(const LoopInfoBase &); // do not implement
+  LoopInfoBase(const LoopInfo &);       // do not implement
 public:
   LoopInfoBase() { }
   ~LoopInfoBase() { releaseMemory(); }
@@ -962,61 +964,59 @@ public:
 };
 
 class LoopInfo : public FunctionPass {
-  LoopInfoBase<BasicBlock>* LI;
+  LoopInfoBase<BasicBlock> LI;
   friend class LoopBase<BasicBlock>;
-  
+
+  void operator=(const LoopInfo &); // do not implement
+  LoopInfo(const LoopInfo &);       // do not implement
 public:
   static char ID; // Pass identification, replacement for typeid
 
-  LoopInfo() : FunctionPass(&ID) {
-    LI = new LoopInfoBase<BasicBlock>();
-  }
-  
-  ~LoopInfo() { delete LI; }
+  LoopInfo() : FunctionPass(&ID) {}
 
-  LoopInfoBase<BasicBlock>& getBase() { return *LI; }
+  LoopInfoBase<BasicBlock>& getBase() { return LI; }
 
   /// iterator/begin/end - The interface to the top-level loops in the current
   /// function.
   ///
-  typedef std::vector<Loop*>::const_iterator iterator;
-  inline iterator begin() const { return LI->begin(); }
-  inline iterator end() const { return LI->end(); }
-  bool empty() const { return LI->empty(); }
+  typedef LoopInfoBase<BasicBlock>::iterator iterator;
+  inline iterator begin() const { return LI.begin(); }
+  inline iterator end() const { return LI.end(); }
+  bool empty() const { return LI.empty(); }
 
   /// getLoopFor - Return the inner most loop that BB lives in.  If a basic
   /// block is in no loop (for example the entry node), null is returned.
   ///
   inline Loop *getLoopFor(const BasicBlock *BB) const {
-    return LI->getLoopFor(BB);
+    return LI.getLoopFor(BB);
   }
 
   /// operator[] - same as getLoopFor...
   ///
   inline const Loop *operator[](const BasicBlock *BB) const {
-    return LI->getLoopFor(BB);
+    return LI.getLoopFor(BB);
   }
 
   /// getLoopDepth - Return the loop nesting level of the specified block.  A
   /// depth of 0 means the block is not inside any loop.
   ///
   inline unsigned getLoopDepth(const BasicBlock *BB) const {
-    return LI->getLoopDepth(BB);
+    return LI.getLoopDepth(BB);
   }
 
   // isLoopHeader - True if the block is a loop header node
   inline bool isLoopHeader(BasicBlock *BB) const {
-    return LI->isLoopHeader(BB);
+    return LI.isLoopHeader(BB);
   }
 
   /// runOnFunction - Calculate the natural loop information.
   ///
   virtual bool runOnFunction(Function &F);
 
-  virtual void releaseMemory() { LI->releaseMemory(); }
+  virtual void releaseMemory() { LI.releaseMemory(); }
 
   virtual void print(std::ostream &O, const Module* M = 0) const {
-    if (O) LI->print(O, M);
+    LI.print(O, M);
   }
 
   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
@@ -1024,32 +1024,32 @@ public:
   /// removeLoop - This removes the specified top-level loop from this loop info
   /// object.  The loop is not deleted, as it will presumably be inserted into
   /// another loop.
-  inline Loop *removeLoop(iterator I) { return LI->removeLoop(I); }
+  inline Loop *removeLoop(iterator I) { return LI.removeLoop(I); }
 
   /// changeLoopFor - Change the top-level loop that contains BB to the
   /// specified loop.  This should be used by transformations that restructure
   /// the loop hierarchy tree.
   inline void changeLoopFor(BasicBlock *BB, Loop *L) {
-    LI->changeLoopFor(BB, L);
+    LI.changeLoopFor(BB, L);
   }
 
   /// changeTopLevelLoop - Replace the specified loop in the top-level loops
   /// list with the indicated loop.
   inline void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop) {
-    LI->changeTopLevelLoop(OldLoop, NewLoop);
+    LI.changeTopLevelLoop(OldLoop, NewLoop);
   }
 
   /// addTopLevelLoop - This adds the specified loop to the collection of
   /// top-level loops.
   inline void addTopLevelLoop(Loop *New) {
-    LI->addTopLevelLoop(New);
+    LI.addTopLevelLoop(New);
   }
 
   /// removeBlock - This method completely removes BB from all data structures,
   /// including all of the Loop objects it is nested in and our mapping from
   /// BasicBlocks to loops.
   void removeBlock(BasicBlock *BB) {
-    LI->removeBlock(BB);
+    LI.removeBlock(BB);
   }
 };
 
@@ -1057,7 +1057,7 @@ public:
 // Allow clients to walk the list of nested loops...
 template <> struct GraphTraits<const Loop*> {
   typedef const Loop NodeType;
-  typedef std::vector<Loop*>::const_iterator ChildIteratorType;
+  typedef LoopInfo::iterator ChildIteratorType;
 
   static NodeType *getEntryNode(const Loop *L) { return L; }
   static inline ChildIteratorType child_begin(NodeType *N) {
@@ -1070,7 +1070,7 @@ template <> struct GraphTraits<const Loop*> {
 
 template <> struct GraphTraits<Loop*> {
   typedef Loop NodeType;
-  typedef std::vector<Loop*>::const_iterator ChildIteratorType;
+  typedef LoopInfo::iterator ChildIteratorType;
 
   static NodeType *getEntryNode(Loop *L) { return L; }
   static inline ChildIteratorType child_begin(NodeType *N) {
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index d699775a67a9..9da5c59a5e54 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -25,6 +25,8 @@
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Support/DataTypes.h"
 #include "llvm/Support/ValueHandle.h"
+#include "llvm/Support/Allocator.h"
+#include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/DenseMap.h"
 #include <iosfwd>
 
@@ -34,20 +36,12 @@ namespace llvm {
   class Type;
   class ScalarEvolution;
   class TargetData;
-  class SCEVConstant;
-  class SCEVTruncateExpr;
-  class SCEVZeroExtendExpr;
-  class SCEVCommutativeExpr;
-  class SCEVUDivExpr;
-  class SCEVSignExtendExpr;
-  class SCEVAddRecExpr;
-  class SCEVUnknown;
 
   /// 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 {
+  class SCEV : public FoldingSetNode {
     const unsigned SCEVType;      // The SCEV baseclass this node corresponds to
 
     SCEV(const SCEV &);            // DO NOT IMPLEMENT
@@ -58,6 +52,8 @@ namespace llvm {
     explicit SCEV(unsigned SCEVTy) : 
       SCEVType(SCEVTy) {}
 
+    virtual void Profile(FoldingSetNodeID &ID) const = 0;
+
     unsigned getSCEVType() const { return SCEVType; }
 
     /// isLoopInvariant - Return true if the value of this SCEV is unchanging in
@@ -132,6 +128,7 @@ namespace llvm {
     SCEVCouldNotCompute();
 
     // None of these methods are valid for this object.
+    virtual void Profile(FoldingSetNodeID &ID) const;
     virtual bool isLoopInvariant(const Loop *L) const;
     virtual const Type *getType() const;
     virtual bool hasComputableLoopEvolution(const Loop *L) const;
@@ -182,7 +179,7 @@ namespace llvm {
 
     /// CouldNotCompute - This SCEV is used to represent unknown trip
     /// counts and things.
-    const SCEV* CouldNotCompute;
+    SCEVCouldNotCompute CouldNotCompute;
 
     /// Scalars - This is a cache of the scalars we have analyzed so far.
     ///
@@ -566,23 +563,10 @@ namespace llvm {
     void print(std::ostream *OS, const Module* M = 0) const {
       if (OS) print(*OS, M);
     }
-    
+
   private:
-    // Uniquing tables.
-    std::map<ConstantInt*, SCEVConstant*> SCEVConstants;
-    std::map<std::pair<const SCEV*, const Type*>,
-             SCEVTruncateExpr*> SCEVTruncates;
-    std::map<std::pair<const SCEV*, const Type*>,
-             SCEVZeroExtendExpr*> SCEVZeroExtends;
-    std::map<std::pair<unsigned, std::vector<const SCEV*> >,
-             SCEVCommutativeExpr*> SCEVCommExprs;
-    std::map<std::pair<const SCEV*, const SCEV*>,
-             SCEVUDivExpr*> SCEVUDivs;
-    std::map<std::pair<const SCEV*, const Type*>,
-             SCEVSignExtendExpr*> SCEVSignExtends;
-    std::map<std::pair<const Loop *, std::vector<const SCEV*> >,
-             SCEVAddRecExpr*> SCEVAddRecExprs;
-    std::map<Value*, SCEVUnknown*> SCEVUnknowns;
+    FoldingSet<SCEV> UniqueSCEVs;
+    BumpPtrAllocator SCEVAllocator;
   };
 }
 
diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
index 90dba8bcc04a..60a23c504310 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -14,10 +14,9 @@
 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H
 #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H
 
-#include "llvm/Instructions.h"
-#include "llvm/Type.h"
-#include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
+#include "llvm/Support/IRBuilder.h"
+#include "llvm/Support/TargetFolder.h"
 
 namespace llvm {
   /// SCEVExpander - This class uses information about analyze scalars to
@@ -32,12 +31,13 @@ namespace llvm {
       InsertedExpressions;
     std::set<Value*> InsertedValues;
 
-    BasicBlock::iterator InsertPt;
+    typedef IRBuilder<true, TargetFolder> BuilderType;
+    BuilderType Builder;
 
     friend struct SCEVVisitor<SCEVExpander, Value*>;
   public:
     explicit SCEVExpander(ScalarEvolution &se)
-      : SE(se) {}
+      : SE(se), Builder(TargetFolder(se.TD)) {}
 
     /// clear - Erase the contents of the InsertedExpressions map so that users
     /// trying to expand the same expression into multiple BasicBlocks or
@@ -53,27 +53,21 @@ namespace llvm {
     /// expandCodeFor - Insert code to directly compute the specified SCEV
     /// expression into the program.  The inserted code is inserted into the
     /// specified block.
-    Value *expandCodeFor(const SCEV* SH, const Type *Ty,
-                         BasicBlock::iterator IP) {
-      InsertPt = IP;
+    Value *expandCodeFor(const SCEV* SH, const Type *Ty, Instruction *IP) {
+      Builder.SetInsertPoint(IP->getParent(), IP);
       return expandCodeFor(SH, Ty);
     }
 
-    /// InsertCastOfTo - Insert a cast of V to the specified type, doing what
-    /// we can to share the casts.
-    Value *InsertCastOfTo(Instruction::CastOps opcode, Value *V,
-                          const Type *Ty);
+  private:
+    /// InsertBinop - Insert the specified binary operator, doing a small amount
+    /// of work to avoid inserting an obviously redundant operation.
+    Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS);
 
     /// InsertNoopCastOfTo - Insert a cast of V to the specified type,
-    /// which must be possible with a noop cast.
+    /// which must be possible with a noop cast, doing what we can to
+    /// share the casts.
     Value *InsertNoopCastOfTo(Value *V, const Type *Ty);
 
-    /// InsertBinop - Insert the specified binary operator, doing a small amount
-    /// of work to avoid inserting an obviously redundant operation.
-    Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS,
-                       Value *RHS, BasicBlock::iterator InsertPt);
-
-  private:
     /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP
     /// instead of using ptrtoint+arithmetic+inttoptr.
     Value *expandAddToGEP(const SCEV* const *op_begin,
diff --git a/include/llvm/Analysis/ScalarEvolutionExpressions.h b/include/llvm/Analysis/ScalarEvolutionExpressions.h
index 8be1a934bc13..c54c86556c36 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpressions.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpressions.h
@@ -39,6 +39,8 @@ namespace llvm {
     explicit SCEVConstant(ConstantInt *v) :
       SCEV(scConstant), V(v) {}
   public:
+    virtual void Profile(FoldingSetNodeID &ID) const;
+
     ConstantInt *getValue() const { return V; }
 
     virtual bool isLoopInvariant(const Loop *L) const {
@@ -81,6 +83,8 @@ namespace llvm {
     SCEVCastExpr(unsigned SCEVTy, const SCEV* op, const Type *ty);
 
   public:
+    virtual void Profile(FoldingSetNodeID &ID) const;
+
     const SCEV* getOperand() const { return Op; }
     virtual const Type *getType() const { return Ty; }
 
@@ -200,6 +204,8 @@ namespace llvm {
       : SCEV(T), Operands(ops.begin(), ops.end()) {}
 
   public:
+    virtual void Profile(FoldingSetNodeID &ID) const;
+
     unsigned getNumOperands() const { return (unsigned)Operands.size(); }
     const SCEV* getOperand(unsigned i) const {
       assert(i < Operands.size() && "Operand index out of range!");
@@ -330,6 +336,8 @@ namespace llvm {
       : SCEV(scUDivExpr), LHS(lhs), RHS(rhs) {}
 
   public:
+    virtual void Profile(FoldingSetNodeID &ID) const;
+
     const SCEV* getLHS() const { return LHS; }
     const SCEV* getRHS() const { return RHS; }
 
@@ -389,6 +397,8 @@ namespace llvm {
     }
 
   public:
+    virtual void Profile(FoldingSetNodeID &ID) const;
+
     const SCEV* getStart() const { return Operands[0]; }
     const Loop *getLoop() const { return L; }
 
@@ -505,6 +515,8 @@ namespace llvm {
       SCEV(scUnknown), V(v) {}
       
   public:
+    virtual void Profile(FoldingSetNodeID &ID) const;
+
     Value *getValue() const { return V; }
 
     virtual bool isLoopInvariant(const Loop *L) const;