8 files changed, 141 insertions, 78 deletions
diff --git a/include/llvm/Analysis/DebugInfo.h b/include/llvm/Analysis/DebugInfo.h
index 972bb07..20de3a4 100644
--- a/include/llvm/Analysis/DebugInfo.h
+++ b/include/llvm/Analysis/DebugInfo.h
@@ -20,6 +20,7 @@
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Dwarf.h"
 
 namespace llvm {
@@ -36,7 +37,7 @@ namespace llvm {
 
   class DIDescriptor {
   protected:    
-    GlobalVariable *GV;
+    GlobalVariable *DbgGV;
 
     /// DIDescriptor constructor.  If the specified GV is non-null, this checks
     /// to make sure that the tag in the descriptor matches 'RequiredTag'.  If
@@ -58,12 +59,12 @@ namespace llvm {
     GlobalVariable *getGlobalVariableField(unsigned Elt) const;
 
   public:
-    explicit DIDescriptor() : GV(0) {}
-    explicit DIDescriptor(GlobalVariable *gv) : GV(gv) {}
+    explicit DIDescriptor() : DbgGV(0) {}
+    explicit DIDescriptor(GlobalVariable *GV) : DbgGV(GV) {}
 
-    bool isNull() const { return GV == 0; }
+    bool isNull() const { return DbgGV == 0; }
 
-    GlobalVariable *getGV() const { return GV; }
+    GlobalVariable *getGV() const { return DbgGV; }
 
     unsigned getVersion() const {
       return getUnsignedField(0) & LLVMDebugVersionMask;
@@ -80,15 +81,6 @@ namespace llvm {
     void dump() const;
   };
 
-  /// DIAnchor - A wrapper for various anchor descriptors.
-  class DIAnchor : public DIDescriptor {
-  public:
-    explicit DIAnchor(GlobalVariable *GV = 0)
-      : DIDescriptor(GV, dwarf::DW_TAG_anchor) {}
-
-    unsigned getAnchorTag() const { return getUnsignedField(1); }
-  };
-
   /// DISubrange - This is used to represent ranges, for array bounds.
   class DISubrange : public DIDescriptor {
   public:
@@ -245,7 +237,7 @@ namespace llvm {
     explicit DIDerivedType(GlobalVariable *GV)
       : DIType(GV, true, true) {
       if (GV && !isDerivedType(getTag()))
-        GV = 0;
+        DbgGV = 0;
     }
 
     DIType getTypeDerivedFrom() const { return getFieldAs<DIType>(9); }
@@ -265,7 +257,7 @@ namespace llvm {
     explicit DICompositeType(GlobalVariable *GV)
       : DIDerivedType(GV, true, true) {
       if (GV && !isCompositeType(getTag()))
-        GV = 0;
+        DbgGV = 0;
     }
 
     DIArray getTypeArray() const { return getFieldAs<DIArray>(10); }
@@ -330,6 +322,19 @@ namespace llvm {
 
     DICompositeType getType() const { return getFieldAs<DICompositeType>(8); }
 
+    /// getReturnTypeName - Subprogram return types are encoded either as
+    /// DIType or as DICompositeType.
+    const std::string &getReturnTypeName(std::string &F) const {
+      DICompositeType DCT(getFieldAs<DICompositeType>(8));
+      if (!DCT.isNull()) {
+        DIArray A = DCT.getTypeArray();
+        DIType T(A.getElement(0).getGV());
+        return T.getName(F);
+      }
+      DIType T(getFieldAs<DIType>(8));
+      return T.getName(F);
+    }
+
     /// Verify - Verify that a subprogram descriptor is well formed.
     bool Verify() const;
 
@@ -360,10 +365,10 @@ namespace llvm {
   /// global etc).
   class DIVariable : public DIDescriptor {
   public:
-    explicit DIVariable(GlobalVariable *gv = 0)
-      : DIDescriptor(gv) {
-      if (gv && !isVariable(getTag()))
-        GV = 0;
+    explicit DIVariable(GlobalVariable *GV = 0)
+      : DIDescriptor(GV) {
+      if (GV && !isVariable(getTag()))
+        DbgGV = 0;
     }
 
     DIDescriptor getContext() const { return getDescriptorField(1); }
@@ -398,7 +403,6 @@ namespace llvm {
   class DIFactory {
     Module &M;
     // Cached values for uniquing and faster lookups.
-    DIAnchor CompileUnitAnchor, SubProgramAnchor, GlobalVariableAnchor;
     const Type *EmptyStructPtr; // "{}*".
     Function *StopPointFn;   // llvm.dbg.stoppoint
     Function *FuncStartFn;   // llvm.dbg.func.start
@@ -413,18 +417,6 @@ namespace llvm {
   public:
     explicit DIFactory(Module &m);
 
-    /// GetOrCreateCompileUnitAnchor - Return the anchor for compile units,
-    /// creating a new one if there isn't already one in the module.
-    DIAnchor GetOrCreateCompileUnitAnchor();
-
-    /// GetOrCreateSubprogramAnchor - Return the anchor for subprograms,
-    /// creating a new one if there isn't already one in the module.
-    DIAnchor GetOrCreateSubprogramAnchor();
-
-    /// GetOrCreateGlobalVariableAnchor - Return the anchor for globals,
-    /// creating a new one if there isn't already one in the module.
-    DIAnchor GetOrCreateGlobalVariableAnchor();
-
     /// GetOrCreateArray - Create an descriptor for an array of descriptors. 
     /// This implicitly uniques the arrays created.
     DIArray GetOrCreateArray(DIDescriptor *Tys, unsigned NumTys);
@@ -527,7 +519,6 @@ namespace llvm {
   private:
     Constant *GetTagConstant(unsigned TAG);
     Constant *GetStringConstant(const std::string &String);
-    DIAnchor GetOrCreateAnchor(unsigned TAG, const char *Name);
 
     /// getCastToEmpty - Return the descriptor as a Constant* with type '{}*'.
     Constant *getCastToEmpty(DIDescriptor D);
@@ -550,6 +541,13 @@ namespace llvm {
 
   bool getLocationInfo(const Value *V, std::string &DisplayName, std::string &Type, 
                        unsigned &LineNo, std::string &File, std::string &Dir); 
+
+  /// CollectDebugInfoAnchors - Collect debugging information anchors.
+  void CollectDebugInfoAnchors(Module &M,
+                               SmallVector<GlobalVariable *, 2> &CompileUnits,
+                               SmallVector<GlobalVariable *, 4> &GlobalVars,
+                               SmallVector<GlobalVariable *, 4> &Subprograms);
+
 } // end namespace llvm
 
 #endif
diff --git a/include/llvm/Analysis/LoopDependenceAnalysis.h b/include/llvm/Analysis/LoopDependenceAnalysis.h
new file mode 100644
index 0000000..c69bc60
--- /dev/null
+++ b/include/llvm/Analysis/LoopDependenceAnalysis.h
@@ -0,0 +1,52 @@
+//===- llvm/Analysis/LoopDependenceAnalysis.h --------------- -*- C++ -*---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// LoopDependenceAnalysis is an LLVM pass that analyses dependences in memory
+// accesses in loops.
+//
+// Please note that this is work in progress and the interface is subject to
+// change.
+//
+// TODO: adapt as interface progresses
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
+#define LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H
+
+#include "llvm/Analysis/LoopPass.h"
+
+namespace llvm {
+
+  class AnalysisUsage;
+  class LoopPass;
+  class ScalarEvolution;
+
+  class LoopDependenceAnalysis : public LoopPass {
+    Loop *L;
+    ScalarEvolution *SE;
+
+  public:
+    static char ID; // Class identification, replacement for typeinfo
+    LoopDependenceAnalysis() : LoopPass(&ID) {}
+
+    bool runOnLoop(Loop*, LPPassManager&);
+
+    virtual void getAnalysisUsage(AnalysisUsage&) const;
+  }; // class LoopDependenceAnalysis
+
+
+  // createLoopDependenceAnalysisPass - This creates an instance of the
+  // LoopDependenceAnalysis pass.
+  //
+  LoopPass *createLoopDependenceAnalysisPass();
+
+} // namespace llvm
+
+#endif /* LLVM_ANALYSIS_LOOP_DEPENDENCE_ANALYSIS_H */
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h
index fb0b584..9e5f57e 100644
--- a/include/llvm/Analysis/LoopInfo.h
+++ b/include/llvm/Analysis/LoopInfo.h
@@ -281,6 +281,16 @@ public:
     }
   }
 
+  /// getUniqueExitBlock - If getUniqueExitBlocks would return exactly one
+  /// block, return that block. Otherwise return null.
+  BlockT *getUniqueExitBlock() const {
+    SmallVector<BlockT*, 8> UniqueExitBlocks;
+    getUniqueExitBlocks(UniqueExitBlocks);
+    if (UniqueExitBlocks.size() == 1)
+      return UniqueExitBlocks[0];
+    return 0;
+  }
+
   /// getLoopPreheader - If there is a preheader for this loop, return it.  A
   /// loop has a preheader if there is only one edge to the header of the loop
   /// from outside of the loop.  If this is the case, the block branching to the
diff --git a/include/llvm/Analysis/LoopPass.h b/include/llvm/Analysis/LoopPass.h
index ca41e51..7659b5b 100644
--- a/include/llvm/Analysis/LoopPass.h
+++ b/include/llvm/Analysis/LoopPass.h
@@ -34,9 +34,6 @@ public:
   // runOnLoop - This method should be implemented by the subclass to perform
   // whatever action is necessary for the specified Loop.
   virtual bool runOnLoop(Loop *L, LPPassManager &LPM) = 0;
-  virtual bool runOnFunctionBody(Function &F, LPPassManager &LPM) {
-    return false;
-  }
 
   // Initialization and finalization hooks.
   virtual bool doInitialization(Loop *L, LPPassManager &LPM) {
diff --git a/include/llvm/Analysis/Passes.h b/include/llvm/Analysis/Passes.h
index d9121a8..35bd821 100644
--- a/include/llvm/Analysis/Passes.h
+++ b/include/llvm/Analysis/Passes.h
@@ -18,6 +18,7 @@
 namespace llvm {
   class FunctionPass;
   class ImmutablePass;
+  class LoopPass;
   class ModulePass;
   class Pass;
   class LibCallInfo;
@@ -116,6 +117,13 @@ namespace llvm {
   // createLiveValuesPass - This creates an instance of the LiveValues pass.
   //
   FunctionPass *createLiveValuesPass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createLoopDependenceAnalysisPass - This creates an instance of the
+  // LoopDependenceAnalysis pass.
+  //
+  LoopPass *createLoopDependenceAnalysisPass();
   
   // Minor pass prototypes, allowing us to expose them through bugpoint and
   // analyze.
diff --git a/include/llvm/Analysis/ProfileInfoLoader.h b/include/llvm/Analysis/ProfileInfoLoader.h
index 8a5141a..9076fbc 100644
--- a/include/llvm/Analysis/ProfileInfoLoader.h
+++ b/include/llvm/Analysis/ProfileInfoLoader.h
@@ -33,6 +33,7 @@ class ProfileInfoLoader {
   std::vector<unsigned>    BlockCounts;
   std::vector<unsigned>    EdgeCounts;
   std::vector<unsigned>    BBTrace;
+  bool Warned;
 public:
   // ProfileInfoLoader ctor - Read the specified profiling data file, exiting
   // the program if the file is invalid or broken.
diff --git a/include/llvm/Analysis/ScalarEvolution.h b/include/llvm/Analysis/ScalarEvolution.h
index 1c1298a..d699775 100644
--- a/include/llvm/Analysis/ScalarEvolution.h
+++ b/include/llvm/Analysis/ScalarEvolution.h
@@ -44,8 +44,8 @@ namespace llvm {
   class SCEVUnknown;
 
   /// SCEV - This class represents an analyzed expression in the program.  These
-  /// are reference-counted opaque objects that the client is not allowed to
-  /// do much with directly.
+  /// are opaque objects that the client is not allowed to do much with
+  /// directly.
   ///
   class SCEV {
     const unsigned SCEVType;      // The SCEV baseclass this node corresponds to
@@ -82,6 +82,11 @@ namespace llvm {
     ///
     bool isOne() const;
 
+    /// isAllOnesValue - Return true if the expression is a constant
+    /// all-ones value.
+    ///
+    bool isAllOnesValue() const;
+
     /// replaceSymbolicValuesWithConcrete - If this SCEV internally references
     /// the symbolic value "Sym", construct and return a new SCEV that produces
     /// the same value, but which uses the concrete value Conc instead of the
@@ -300,8 +305,9 @@ namespace llvm {
     /// try to evaluate a few iterations of the loop until we get the exit
     /// condition gets a value of ExitWhen (true or false).  If we cannot
     /// evaluate the trip count of the loop, return CouldNotCompute.
-    const SCEV* ComputeBackedgeTakenCountExhaustively(const Loop *L, Value *Cond,
-                                                     bool ExitWhen);
+    const SCEV* ComputeBackedgeTakenCountExhaustively(const Loop *L,
+                                                      Value *Cond,
+                                                      bool ExitWhen);
 
     /// HowFarToZero - Return the number of times a backedge comparing the
     /// specified value to zero will execute.  If not computable, return
@@ -329,6 +335,12 @@ namespace llvm {
     /// found.
     BasicBlock* getPredecessorWithUniqueSuccessorForBB(BasicBlock *BB);
 
+    /// isNecessaryCond - Test whether the given CondValue value is a condition
+    /// which is at least as strict as the one described by Pred, LHS, and RHS.
+    bool isNecessaryCond(Value *Cond, ICmpInst::Predicate Pred,
+                         const SCEV *LHS, const SCEV *RHS,
+                         bool Inverse);
+
     /// getConstantEvolutionLoopExitValue - If we know that the specified Phi is
     /// in the header of its containing loop, we know the loop executes a
     /// constant number of times, and the PHI node is just a recurrence
@@ -457,7 +469,7 @@ namespace llvm {
     /// widening.
     const SCEV* getTruncateOrNoop(const SCEV* V, const Type *Ty);
 
-    /// getIntegerSCEV - Given an integer or FP type, create a constant for the
+    /// getIntegerSCEV - Given a SCEVable type, create a constant for the
     /// specified signed integer value and return a SCEV for the constant.
     const SCEV* getIntegerSCEV(int Val, const Type *Ty);
 
@@ -531,10 +543,11 @@ namespace llvm {
     /// is deleted.
     void forgetLoopBackedgeTakenCount(const Loop *L);
 
-    /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is
-    /// guaranteed to end in (at every loop iteration).  It is, at the same time,
-    /// the minimum number of times S is divisible by 2.  For example, given {4,+,8}
-    /// it returns 2.  If S is guaranteed to be 0, it returns the bitwidth of S.
+    /// GetMinTrailingZeros - Determine the minimum number of zero bits that S
+    /// is guaranteed to end in (at every loop iteration).  It is, at the same
+    /// time, the minimum number of times S is divisible by 2.  For example,
+    /// given {4,+,8} it returns 2.  If S is guaranteed to be 0, it returns the
+    /// bitwidth of S.
     uint32_t GetMinTrailingZeros(const SCEV* S);
 
     /// GetMinLeadingZeros - Determine the minimum number of zero bits that S is
diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h
index 730c97f..90dba8b 100644
--- a/include/llvm/Analysis/ScalarEvolutionExpander.h
+++ b/include/llvm/Analysis/ScalarEvolutionExpander.h
@@ -28,7 +28,8 @@ namespace llvm {
   /// memory.
   struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
     ScalarEvolution &SE;
-    std::map<const SCEV*, AssertingVH<Value> > InsertedExpressions;
+    std::map<std::pair<const SCEV *, Instruction *>, AssertingVH<Value> >
+      InsertedExpressions;
     std::set<Value*> InsertedValues;
 
     BasicBlock::iterator InsertPt;
@@ -43,48 +44,18 @@ namespace llvm {
     /// different places within the same BasicBlock can do so.
     void clear() { InsertedExpressions.clear(); }
 
-    /// isInsertedInstruction - Return true if the specified instruction was
-    /// inserted by the code rewriter.  If so, the client should not modify the
-    /// instruction.
-    bool isInsertedInstruction(Instruction *I) const {
-      return InsertedValues.count(I);
-    }
-
-    /// isInsertedExpression - Return true if the the code rewriter has a
-    /// Value* recorded for the given expression.
-    bool isInsertedExpression(const SCEV *S) const {
-      return InsertedExpressions.count(S);
-    }
-
     /// 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);
 
-    /// addInsertedValue - Remember the specified instruction as being the
-    /// canonical form for the specified SCEV.
-    void addInsertedValue(Value *V, const SCEV *S) {
-      InsertedExpressions[S] = V;
-      InsertedValues.insert(V);
-    }
-
-    void setInsertionPoint(BasicBlock::iterator NewIP) { InsertPt = NewIP; }
-
-    BasicBlock::iterator getInsertionPoint() const { return InsertPt; }
-
-    /// expandCodeFor - Insert code to directly compute the specified SCEV
-    /// expression into the program.  The inserted code is inserted into the
-    /// SCEVExpander's current insertion point. If a type is specified, the
-    /// result will be expanded to have that type, with a cast if necessary.
-    Value *expandCodeFor(const SCEV* SH, const Type *Ty = 0);
-
     /// 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) {
-      setInsertionPoint(IP);
+      InsertPt = IP;
       return expandCodeFor(SH, Ty);
     }
 
@@ -111,6 +82,19 @@ namespace llvm {
 
     Value *expand(const SCEV *S);
 
+    /// expandCodeFor - Insert code to directly compute the specified SCEV
+    /// expression into the program.  The inserted code is inserted into the
+    /// SCEVExpander's current insertion point. If a type is specified, the
+    /// result will be expanded to have that type, with a cast if necessary.
+    Value *expandCodeFor(const SCEV* SH, const Type *Ty = 0);
+
+    /// isInsertedInstruction - Return true if the specified instruction was
+    /// inserted by the code rewriter.  If so, the client should not modify the
+    /// instruction.
+    bool isInsertedInstruction(Instruction *I) const {
+      return InsertedValues.count(I);
+    }
+
     Value *visitConstant(const SCEVConstant *S) {
       return S->getValue();
     }