Update llvm to r84119.

11 files changed, 165 insertions, 65 deletions

diff --git a/include/llvm/Transforms/Utils/AddrModeMatcher.h b/include/llvm/Transforms/Utils/AddrModeMatcher.h
index 913a541..be601e2 100644
--- a/include/llvm/Transforms/Utils/AddrModeMatcher.h
+++ b/include/llvm/Transforms/Utils/AddrModeMatcher.h
@@ -20,7 +20,6 @@
 #define LLVM_TRANSFORMS_UTILS_ADDRMODEMATCHER_H
 
 #include "llvm/ADT/SmallVector.h"
-#include "llvm/Support/Streams.h"
 #include "llvm/Target/TargetLowering.h"
 
 namespace llvm {
@@ -30,18 +29,19 @@ class Instruction;
 class Value;
 class Type;
 class User;
-  
+class raw_ostream;
+
 /// ExtAddrMode - This is an extended version of TargetLowering::AddrMode
 /// which holds actual Value*'s for register values.
 struct ExtAddrMode : public TargetLowering::AddrMode {
   Value *BaseReg;
   Value *ScaledReg;
   ExtAddrMode() : BaseReg(0), ScaledReg(0) {}
-  void print(OStream &OS) const;
+  void print(raw_ostream &OS) const;
   void dump() const;
 };
 
-static inline OStream &operator<<(OStream &OS, const ExtAddrMode &AM) {
+static inline raw_ostream &operator<<(raw_ostream &OS, const ExtAddrMode &AM) {
   AM.print(OS);
   return OS;
 }
diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h
index 95ffa46..e766d72 100644
--- a/include/llvm/Transforms/Utils/BasicBlockUtils.h
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -126,10 +126,10 @@ bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
 /// dest go to one block instead of each going to a different block, but isn't 
 /// the standard definition of a "critical edge".
 ///
-bool SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P = 0,
-                       bool MergeIdenticalEdges = false);
+BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum,
+                              Pass *P = 0, bool MergeIdenticalEdges = false);
 
-inline bool SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) {
+inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) {
   return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), P);
 }
 
@@ -143,7 +143,7 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) {
   TerminatorInst *TI = (*PI)->getTerminator();
   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
     if (TI->getSuccessor(i) == Succ)
-      MadeChange |= SplitCriticalEdge(TI, i, P);
+      MadeChange |= !!SplitCriticalEdge(TI, i, P);
   return MadeChange;
 }
 
@@ -151,8 +151,9 @@ inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) {
 /// and return true, otherwise return false.  This method requires that there be
 /// an edge between the two blocks.  If P is specified, it updates the analyses
 /// described above.
-inline bool SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, Pass *P = 0,
-                              bool MergeIdenticalEdges = false) {
+inline BasicBlock *SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst,
+                                     Pass *P = 0,
+                                     bool MergeIdenticalEdges = false) {
   TerminatorInst *TI = Src->getTerminator();
   unsigned i = 0;
   while (1) {
@@ -180,8 +181,12 @@ BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P);
 /// Preds array, which has NumPreds elements in it.  The new block is given a
 /// suffix of 'Suffix'.  This function returns the new block.
 ///
-/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree and
-/// DominanceFrontier, but no other analyses.
+/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
+/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses.
+/// In particular, it does not preserve LoopSimplify (because it's
+/// complicated to handle the case where one of the edges being split
+/// is an exit of a loop with other exits).
+///
 BasicBlock *SplitBlockPredecessors(BasicBlock *BB, BasicBlock *const *Preds,
                                    unsigned NumPreds, const char *Suffix,
                                    Pass *P = 0);
diff --git a/include/llvm/Transforms/Utils/BasicInliner.h b/include/llvm/Transforms/Utils/BasicInliner.h
index 6a57055..4bca6b8 100644
--- a/include/llvm/Transforms/Utils/BasicInliner.h
+++ b/include/llvm/Transforms/Utils/BasicInliner.h
@@ -15,7 +15,7 @@
 #ifndef BASICINLINER_H
 #define BASICINLINER_H
 
-#include "llvm/Transforms/Utils/InlineCost.h"
+#include "llvm/Analysis/InlineCost.h"
 
 namespace llvm {
 
diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h
index 840d970..5b15b5b 100644
--- a/include/llvm/Transforms/Utils/Cloning.h
+++ b/include/llvm/Transforms/Utils/Cloning.h
@@ -18,7 +18,6 @@
 #ifndef LLVM_TRANSFORMS_UTILS_CLONING_H
 #define LLVM_TRANSFORMS_UTILS_CLONING_H
 
-#include <vector>
 #include "llvm/ADT/DenseMap.h"
 
 namespace llvm {
@@ -36,10 +35,11 @@ class CallSite;
 class Trace;
 class CallGraph;
 class TargetData;
+class Loop;
 class LoopInfo;
 class LLVMContext;
-template<class N> class LoopBase;
-typedef LoopBase<BasicBlock> Loop;
+class AllocaInst;
+template <typename T> class SmallVectorImpl;
 
 /// CloneModule - Return an exact copy of the specified module
 ///
@@ -105,9 +105,9 @@ BasicBlock *CloneBasicBlock(const BasicBlock *BB,
                             ClonedCodeInfo *CodeInfo = 0);
 
 
-/// CloneLoop - Clone Loop. Clone dominator info for loop insiders. Populate ValueMap
-/// using old blocks to new blocks mapping.
-Loop *CloneLoop(Loop *L, LPPassManager  *LPM, LoopInfo *LI, 
+/// CloneLoop - Clone Loop. Clone dominator info for loop insiders. Populate
+/// ValueMap using old blocks to new blocks mapping.
+Loop *CloneLoop(Loop *L, LPPassManager *LPM, LoopInfo *LI, 
                 DenseMap<const Value *, Value *> &ValueMap, Pass *P);
 
 /// CloneFunction - Return a copy of the specified function, but without
@@ -138,7 +138,7 @@ inline Function *CloneFunction(const Function *F, ClonedCodeInfo *CodeInfo = 0){
 ///
 void CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
                        DenseMap<const Value*, Value*> &ValueMap,
-                       std::vector<ReturnInst*> &Returns,
+                       SmallVectorImpl<ReturnInst*> &Returns,
                        const char *NameSuffix = "", 
                        ClonedCodeInfo *CodeInfo = 0);
 
@@ -151,25 +151,11 @@ void CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
 /// used for things like CloneFunction or CloneModule.
 void CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
                                DenseMap<const Value*, Value*> &ValueMap,
-                               std::vector<ReturnInst*> &Returns,
+                               SmallVectorImpl<ReturnInst*> &Returns,
                                const char *NameSuffix = "", 
                                ClonedCodeInfo *CodeInfo = 0,
                                const TargetData *TD = 0);
 
-
-/// CloneTraceInto - Clone T into NewFunc. Original<->clone mapping is
-/// saved in ValueMap.
-///
-void CloneTraceInto(Function *NewFunc, Trace &T,
-                    DenseMap<const Value*, Value*> &ValueMap,
-                    const char *NameSuffix);
-
-/// CloneTrace - Returns a copy of the specified trace.
-/// It takes a vector of basic blocks clones the basic blocks, removes internal
-/// phi nodes, adds it to the same function as the original (although there is
-/// no jump to it) and returns the new vector of basic blocks.
-std::vector<BasicBlock *> CloneTrace(const std::vector<BasicBlock*> &origTrace);
-
 /// InlineFunction - This function inlines the called function into the basic
 /// block of the caller.  This returns false if it is not possible to inline
 /// this call.  The program is still in a well defined state if this occurs
@@ -183,9 +169,15 @@ std::vector<BasicBlock *> CloneTrace(const std::vector<BasicBlock*> &origTrace);
 /// If a non-null callgraph pointer is provided, these functions update the
 /// CallGraph to represent the program after inlining.
 ///
-bool InlineFunction(CallInst *C, CallGraph *CG = 0, const TargetData *TD = 0);
-bool InlineFunction(InvokeInst *II, CallGraph *CG = 0, const TargetData *TD =0);
-bool InlineFunction(CallSite CS, CallGraph *CG = 0, const TargetData *TD = 0);
+/// If StaticAllocas is non-null, InlineFunction populates it with all of the
+/// static allocas that it inlines into the caller.
+///
+bool InlineFunction(CallInst *C, CallGraph *CG = 0, const TargetData *TD = 0,
+                    SmallVectorImpl<AllocaInst*> *StaticAllocas = 0);
+bool InlineFunction(InvokeInst *II, CallGraph *CG = 0, const TargetData *TD = 0,
+                    SmallVectorImpl<AllocaInst*> *StaticAllocas = 0);
+bool InlineFunction(CallSite CS, CallGraph *CG = 0, const TargetData *TD = 0,
+                    SmallVectorImpl<AllocaInst*> *StaticAllocas = 0);
 
 } // End llvm namespace
 
diff --git a/include/llvm/Transforms/Utils/FunctionUtils.h b/include/llvm/Transforms/Utils/FunctionUtils.h
index dc7ef23..785b08f 100644
--- a/include/llvm/Transforms/Utils/FunctionUtils.h
+++ b/include/llvm/Transforms/Utils/FunctionUtils.h
@@ -14,13 +14,13 @@
 #ifndef LLVM_TRANSFORMS_UTILS_FUNCTION_H
 #define LLVM_TRANSFORMS_UTILS_FUNCTION_H
 
-#include "llvm/Analysis/LoopInfo.h"
 #include <vector>
 
 namespace llvm {
   class BasicBlock;
   class DominatorTree;
   class Function;
+  class Loop;
 
   /// ExtractCodeRegion - rip out a sequence of basic blocks into a new function
   ///
diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h
index dd423fa..419029f 100644
--- a/include/llvm/Transforms/Utils/Local.h
+++ b/include/llvm/Transforms/Utils/Local.h
@@ -27,6 +27,7 @@ class PHINode;
 class AllocaInst;
 class ConstantExpr;
 class TargetData;
+class LLVMContext;
 struct DbgInfoIntrinsic;
 
 template<typename T> class SmallVectorImpl;
@@ -82,7 +83,7 @@ void RecursivelyDeleteDeadPHINode(PHINode *PN);
 /// between them, moving the instructions in the predecessor into BB.  This
 /// deletes the predecessor block.
 ///
-void MergeBasicBlockIntoOnlyPred(BasicBlock *BB);
+void MergeBasicBlockIntoOnlyPred(BasicBlock *BB, Pass *P = 0);
     
   
 /// SimplifyCFG - This function is used to do simplification of a CFG.  For
@@ -107,7 +108,8 @@ bool FoldBranchToCommonDest(BranchInst *BI);
 /// invalidating the SSA information for the value.  It returns the pointer to
 /// the alloca inserted to create a stack slot for X.
 ///
-AllocaInst *DemoteRegToStack(Instruction &X, bool VolatileLoads = false,
+AllocaInst *DemoteRegToStack(Instruction &X,
+                             bool VolatileLoads = false,
                              Instruction *AllocaPoint = 0);
 
 /// DemotePHIToStack - This function takes a virtual register computed by a phi
diff --git a/include/llvm/Transforms/Utils/PromoteMemToReg.h b/include/llvm/Transforms/Utils/PromoteMemToReg.h
index 35cfadd..71a077e 100644
--- a/include/llvm/Transforms/Utils/PromoteMemToReg.h
+++ b/include/llvm/Transforms/Utils/PromoteMemToReg.h
@@ -23,6 +23,7 @@ class AllocaInst;
 class DominatorTree;
 class DominanceFrontier;
 class AliasSetTracker;
+class LLVMContext;
 
 /// isAllocaPromotable - Return true if this alloca is legal for promotion.
 /// This is true if there are only loads and stores to the alloca...
@@ -39,6 +40,7 @@ bool isAllocaPromotable(const AllocaInst *AI);
 ///
 void PromoteMemToReg(const std::vector<AllocaInst*> &Allocas,
                      DominatorTree &DT, DominanceFrontier &DF,
+                     LLVMContext &Context,
                      AliasSetTracker *AST = 0);
 
 } // End llvm namespace
diff --git a/include/llvm/Transforms/Utils/SSAUpdater.h b/include/llvm/Transforms/Utils/SSAUpdater.h
new file mode 100644
index 0000000..11b90d4
--- /dev/null
+++ b/include/llvm/Transforms/Utils/SSAUpdater.h
@@ -0,0 +1,108 @@
+//===-- SSAUpdater.h - Unstructured SSA Update Tool -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file declares the SSAUpdater class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_SSAUPDATER_H
+#define LLVM_TRANSFORMS_UTILS_SSAUPDATER_H
+
+namespace llvm {
+  class Value;
+  class BasicBlock;
+  class Use;
+  class PHINode;
+  template<typename T>
+  class SmallVectorImpl;
+  
+/// SSAUpdater - This class updates SSA form for a set of values defined in
+/// multiple blocks.  This is used when code duplication or another unstructured
+/// transformation wants to rewrite a set of uses of one value with uses of a
+/// set of values.
+class SSAUpdater {
+  /// AvailableVals - This keeps track of which value to use on a per-block
+  /// basis.  When we insert PHI nodes, we keep track of them here.  We use
+  /// WeakVH's for the value of the map because we RAUW PHI nodes when we
+  /// eliminate them, and want the WeakVH to track this.
+  //typedef DenseMap<BasicBlock*, TrackingVH<Value> > AvailableValsTy;
+  void *AV;
+  
+  /// PrototypeValue is an arbitrary representative value, which we derive names
+  /// and a type for PHI nodes.
+  Value *PrototypeValue;
+  
+  /// IncomingPredInfo - We use this as scratch space when doing our recursive
+  /// walk.  This should only be used in GetValueInBlockInternal, normally it
+  /// should be empty.
+  //std::vector<std::pair<BasicBlock*, TrackingVH<Value> > > IncomingPredInfo;
+  void *IPI;
+  
+  /// InsertedPHIs - If this is non-null, the SSAUpdater adds all PHI nodes that
+  /// it creates to the vector.
+  SmallVectorImpl<PHINode*> *InsertedPHIs;
+public:
+  /// SSAUpdater constructor.  If InsertedPHIs is specified, it will be filled
+  /// in with all PHI Nodes created by rewriting.
+  SSAUpdater(SmallVectorImpl<PHINode*> *InsertedPHIs = 0);
+  ~SSAUpdater();
+  
+  /// Initialize - Reset this object to get ready for a new set of SSA
+  /// updates.  ProtoValue is the value used to name PHI nodes.
+  void Initialize(Value *ProtoValue);
+  
+  /// AddAvailableValue - Indicate that a rewritten value is available at the
+  /// end of the specified block with the specified value.
+  void AddAvailableValue(BasicBlock *BB, Value *V);
+
+  /// HasValueForBlock - Return true if the SSAUpdater already has a value for
+  /// the specified block.
+  bool HasValueForBlock(BasicBlock *BB) const;
+  
+  /// GetValueAtEndOfBlock - Construct SSA form, materializing a value that is
+  /// live at the end of the specified block.
+  Value *GetValueAtEndOfBlock(BasicBlock *BB);
+  
+  /// GetValueInMiddleOfBlock - Construct SSA form, materializing a value that
+  /// is live in the middle of the specified block.
+  ///
+  /// GetValueInMiddleOfBlock is the same as GetValueAtEndOfBlock except in one
+  /// important case: if there is a definition of the rewritten value after the
+  /// 'use' in BB.  Consider code like this:
+  ///
+  ///      X1 = ...
+  ///   SomeBB:
+  ///      use(X)
+  ///      X2 = ...
+  ///      br Cond, SomeBB, OutBB
+  ///
+  /// In this case, there are two values (X1 and X2) added to the AvailableVals
+  /// set by the client of the rewriter, and those values are both live out of
+  /// their respective blocks.  However, the use of X happens in the *middle* of
+  /// a block.  Because of this, we need to insert a new PHI node in SomeBB to
+  /// merge the appropriate values, and this value isn't live out of the block.
+  ///
+  Value *GetValueInMiddleOfBlock(BasicBlock *BB);
+  
+  /// RewriteUse - Rewrite a use of the symbolic value.  This handles PHI nodes,
+  /// which use their value in the corresponding predecessor.  Note that this
+  /// will not work if the use is supposed to be rewritten to a value defined in
+  /// the same block as the use, but above it.  Any 'AddAvailableValue's added
+  /// for the use's block will be considered to be below it.
+  void RewriteUse(Use &U);
+  
+private:
+  Value *GetValueAtEndOfBlockInternal(BasicBlock *BB);
+  void operator=(const SSAUpdater&); // DO NOT IMPLEMENT
+  SSAUpdater(const SSAUpdater&);     // DO NOT IMPLEMENT
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/Utils/SSI.h b/include/llvm/Transforms/Utils/SSI.h
index 59dd6d0..ff5bb7b 100644
--- a/include/llvm/Transforms/Utils/SSI.h
+++ b/include/llvm/Transforms/Utils/SSI.h
@@ -23,7 +23,6 @@
 #define LLVM_TRANSFORMS_UTILS_SSI_H
 
 #include "llvm/Pass.h"
-#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
@@ -44,7 +43,6 @@ namespace llvm {
 
       void getAnalysisUsage(AnalysisUsage &AU) const;
 
-      /// runOnMachineFunction - pass entry point
       bool runOnFunction(Function&);
 
       void createSSI(SmallVectorImpl<Instruction *> &value);
@@ -56,44 +54,36 @@ namespace llvm {
       // Stores variables created by SSI
       SmallPtrSet<Instruction *, 16> created;
 
-      // These variables are only live for each creation
-      unsigned num_values;
-
-      // Has a bit for each variable, true if it needs to be created
-      // and false otherwise
-      BitVector needConstruction;
-
       // Phis created by SSI
-      DenseMap<PHINode *, unsigned> phis;
+      DenseMap<PHINode *, Instruction*> phis;
 
       // Sigmas created by SSI
-      DenseMap<PHINode *, unsigned> sigmas;
+      DenseMap<PHINode *, Instruction*> sigmas;
 
       // Phi nodes that have a phi as operand and has to be fixed
       SmallPtrSet<PHINode *, 1> phisToFix;
 
       // List of definition points for every variable
-      SmallVector<SmallVector<BasicBlock *, 1>, 0> defsites;
+      DenseMap<Instruction*, SmallVector<BasicBlock*, 4> > defsites;
 
       // Basic Block of the original definition of each variable
-      SmallVector<BasicBlock *, 0> value_original;
+      DenseMap<Instruction*, BasicBlock*> value_original;
 
       // Stack of last seen definition of a variable
-      SmallVector<SmallVector<Instruction *, 1>, 0> value_stack;
+      DenseMap<Instruction*, SmallVector<Instruction *, 1> > value_stack;
 
-      void insertSigmaFunctions(SmallVectorImpl<Instruction *> &value);
-      void insertPhiFunctions(SmallVectorImpl<Instruction *> &value);
-      void renameInit(SmallVectorImpl<Instruction *> &value);
+      void insertSigmaFunctions(SmallPtrSet<Instruction*, 4> &value);
+      void insertSigma(TerminatorInst *TI, Instruction *I);
+      void insertPhiFunctions(SmallPtrSet<Instruction*, 4> &value);
+      void renameInit(SmallPtrSet<Instruction*, 4> &value);
       void rename(BasicBlock *BB);
 
       void substituteUse(Instruction *I);
       bool dominateAny(BasicBlock *BB, Instruction *value);
       void fixPhis();
 
-      unsigned getPositionPhi(PHINode *PN);
-      unsigned getPositionSigma(PHINode *PN);
-
-      unsigned isUsedInTerminator(CmpInst *CI);
+      Instruction* getPositionPhi(PHINode *PN);
+      Instruction* getPositionSigma(PHINode *PN);
 
       void init(SmallVectorImpl<Instruction *> &value);
       void clean();
diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h
index a9c0bf6..3d5ee1a 100644
--- a/include/llvm/Transforms/Utils/UnrollLoop.h
+++ b/include/llvm/Transforms/Utils/UnrollLoop.h
@@ -16,10 +16,10 @@
 #ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
 #define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
 
-#include "llvm/Analysis/LoopInfo.h"
-
 namespace llvm {
 
+class Loop;
+class LoopInfo;
 class LPPassManager;
 
 bool UnrollLoop(Loop *L, unsigned Count, LoopInfo* LI, LPPassManager* LPM);
diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h
index ed33413..d31edab 100644
--- a/include/llvm/Transforms/Utils/ValueMapper.h
+++ b/include/llvm/Transforms/Utils/ValueMapper.h
@@ -20,9 +20,10 @@
 namespace llvm {
   class Value;
   class Instruction;
+  class LLVMContext;
   typedef DenseMap<const Value *, Value *> ValueMapTy;
 
-  Value *MapValue(const Value *V, ValueMapTy &VM);
+  Value *MapValue(const Value *V, ValueMapTy &VM, LLVMContext &Context);
   void RemapInstruction(Instruction *I, ValueMapTy &VM);
 } // End llvm namespace