Import LLVM, at r72732.

11 files changed, 1004 insertions, 0 deletions

diff --git a/include/llvm/Transforms/Utils/AddrModeMatcher.h b/include/llvm/Transforms/Utils/AddrModeMatcher.h
new file mode 100644
index 0000000..913a541
--- /dev/null
+++ b/include/llvm/Transforms/Utils/AddrModeMatcher.h
@@ -0,0 +1,102 @@
+//===- AddrModeMatcher.h - Addressing mode matching facility ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// AddressingModeMatcher - This class exposes a single public method, which is
+// used to construct a "maximal munch" of the addressing mode for the target
+// specified by TLI for an access to "V" with an access type of AccessTy.  This
+// returns the addressing mode that is actually matched by value, but also
+// returns the list of instructions involved in that addressing computation in
+// AddrModeInsts.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_ADDRMODEMATCHER_H
+#define LLVM_TRANSFORMS_UTILS_ADDRMODEMATCHER_H
+
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Streams.h"
+#include "llvm/Target/TargetLowering.h"
+
+namespace llvm {
+
+class GlobalValue;
+class Instruction;
+class Value;
+class Type;
+class User;
+  
+/// 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 dump() const;
+};
+
+static inline OStream &operator<<(OStream &OS, const ExtAddrMode &AM) {
+  AM.print(OS);
+  return OS;
+}
+
+class AddressingModeMatcher {
+  SmallVectorImpl<Instruction*> &AddrModeInsts;
+  const TargetLowering &TLI;
+
+  /// AccessTy/MemoryInst - This is the type for the access (e.g. double) and
+  /// the memory instruction that we're computing this address for.
+  const Type *AccessTy;
+  Instruction *MemoryInst;
+  
+  /// AddrMode - This is the addressing mode that we're building up.  This is
+  /// part of the return value of this addressing mode matching stuff.
+  ExtAddrMode &AddrMode;
+  
+  /// IgnoreProfitability - This is set to true when we should not do
+  /// profitability checks.  When true, IsProfitableToFoldIntoAddressingMode
+  /// always returns true.
+  bool IgnoreProfitability;
+  
+  AddressingModeMatcher(SmallVectorImpl<Instruction*> &AMI,
+                        const TargetLowering &T, const Type *AT,
+                        Instruction *MI, ExtAddrMode &AM)
+    : AddrModeInsts(AMI), TLI(T), AccessTy(AT), MemoryInst(MI), AddrMode(AM) {
+    IgnoreProfitability = false;
+  }
+public:
+  
+  /// Match - Find the maximal addressing mode that a load/store of V can fold,
+  /// give an access type of AccessTy.  This returns a list of involved
+  /// instructions in AddrModeInsts.
+  static ExtAddrMode Match(Value *V, const Type *AccessTy,
+                           Instruction *MemoryInst,
+                           SmallVectorImpl<Instruction*> &AddrModeInsts,
+                           const TargetLowering &TLI) {
+    ExtAddrMode Result;
+
+    bool Success = 
+      AddressingModeMatcher(AddrModeInsts, TLI, AccessTy,
+                            MemoryInst, Result).MatchAddr(V, 0);
+    Success = Success; assert(Success && "Couldn't select *anything*?");
+    return Result;
+  }
+private:
+  bool MatchScaledValue(Value *ScaleReg, int64_t Scale, unsigned Depth);
+  bool MatchAddr(Value *V, unsigned Depth);
+  bool MatchOperationAddr(User *Operation, unsigned Opcode, unsigned Depth);
+  bool IsProfitableToFoldIntoAddressingMode(Instruction *I,
+                                            ExtAddrMode &AMBefore,
+                                            ExtAddrMode &AMAfter);
+  bool ValueAlreadyLiveAtInst(Value *Val, Value *KnownLive1, Value *KnownLive2);
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h
new file mode 100644
index 0000000..95ffa46
--- /dev/null
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -0,0 +1,191 @@
+//===-- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions perform manipulations on basic blocks, and
+// instructions contained within basic blocks.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCK_H
+#define LLVM_TRANSFORMS_UTILS_BASICBLOCK_H
+
+// FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock
+
+#include "llvm/BasicBlock.h"
+#include "llvm/Support/CFG.h"
+
+namespace llvm {
+
+class Instruction;
+class Pass;
+class AliasAnalysis;
+
+/// DeleteDeadBlock - Delete the specified block, which must have no
+/// predecessors.
+void DeleteDeadBlock(BasicBlock *BB);
+  
+  
+/// FoldSingleEntryPHINodes - We know that BB has one predecessor.  If there are
+/// any single-entry PHI nodes in it, fold them away.  This handles the case
+/// when all entries to the PHI nodes in a block are guaranteed equal, such as
+/// when the block has exactly one predecessor.
+void FoldSingleEntryPHINodes(BasicBlock *BB);
+
+/// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it
+/// is dead. Also recursively delete any operands that become dead as
+/// a result. This includes tracing the def-use list from the PHI to see if
+/// it is ultimately unused or if it reaches an unused cycle.
+void DeleteDeadPHIs(BasicBlock *BB);
+
+/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor,
+/// if possible.  The return value indicates success or failure.
+bool MergeBlockIntoPredecessor(BasicBlock* BB, Pass* P = 0);
+
+// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
+// with a value, then remove and delete the original instruction.
+//
+void ReplaceInstWithValue(BasicBlock::InstListType &BIL,
+                          BasicBlock::iterator &BI, Value *V);
+
+// ReplaceInstWithInst - Replace the instruction specified by BI with the
+// instruction specified by I.  The original instruction is deleted and BI is
+// updated to point to the new instruction.
+//
+void ReplaceInstWithInst(BasicBlock::InstListType &BIL,
+                         BasicBlock::iterator &BI, Instruction *I);
+
+// ReplaceInstWithInst - Replace the instruction specified by From with the
+// instruction specified by To.
+//
+void ReplaceInstWithInst(Instruction *From, Instruction *To);
+
+/// CopyPrecedingStopPoint - If I is immediately preceded by a StopPoint,
+/// make a copy of the stoppoint before InsertPos (presumably before copying
+/// or moving I).
+void CopyPrecedingStopPoint(Instruction *I, BasicBlock::iterator InsertPos);
+
+/// FindAvailableLoadedValue - Scan the ScanBB block backwards (starting at the
+/// instruction before ScanFrom) checking to see if we have the value at the
+/// memory address *Ptr locally available within a small number of instructions.
+/// If the value is available, return it.
+///
+/// If not, return the iterator for the last validated instruction that the 
+/// value would be live through.  If we scanned the entire block and didn't find
+/// something that invalidates *Ptr or provides it, ScanFrom would be left at
+/// begin() and this returns null.  ScanFrom could also be left 
+///
+/// MaxInstsToScan specifies the maximum instructions to scan in the block.  If
+/// it is set to 0, it will scan the whole block. You can also optionally
+/// specify an alias analysis implementation, which makes this more precise.
+Value *FindAvailableLoadedValue(Value *Ptr, BasicBlock *ScanBB,
+                                BasicBlock::iterator &ScanFrom,
+                                unsigned MaxInstsToScan = 6,
+                                AliasAnalysis *AA = 0);
+
+/// FindFunctionBackedges - Analyze the specified function to find all of the
+/// loop backedges in the function and return them.  This is a relatively cheap
+/// (compared to computing dominators and loop info) analysis.
+///
+/// The output is added to Result, as pairs of <from,to> edge info.
+void FindFunctionBackedges(const Function &F,
+      SmallVectorImpl<std::pair<const BasicBlock*,const BasicBlock*> > &Result);
+  
+
+// RemoveSuccessor - Change the specified terminator instruction such that its
+// successor #SuccNum no longer exists.  Because this reduces the outgoing
+// degree of the current basic block, the actual terminator instruction itself
+// may have to be changed.  In the case where the last successor of the block is
+// deleted, a return instruction is inserted in its place which can cause a
+// suprising change in program behavior if it is not expected.
+//
+void RemoveSuccessor(TerminatorInst *TI, unsigned SuccNum);
+
+/// isCriticalEdge - Return true if the specified edge is a critical edge.
+/// Critical edges are edges from a block with multiple successors to a block
+/// with multiple predecessors.
+///
+bool isCriticalEdge(const TerminatorInst *TI, unsigned SuccNum,
+                    bool AllowIdenticalEdges = false);
+
+/// SplitCriticalEdge - If this edge is a critical edge, insert a new node to
+/// split the critical edge.  This will update DominatorTree and
+/// DominatorFrontier information if it is available, thus calling this pass
+/// will not invalidate either of them. This returns true if the edge was split,
+/// false otherwise.  
+///
+/// If MergeIdenticalEdges is true (not the default), *all* edges from TI to the
+/// specified successor will be merged into the same critical edge block.  
+/// This is most commonly interesting with switch instructions, which may 
+/// have many edges to any one destination.  This ensures that all edges to that
+/// 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);
+
+inline bool SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) {
+  return SplitCriticalEdge(BB->getTerminator(), SI.getSuccessorIndex(), P);
+}
+
+/// SplitCriticalEdge - If the edge from *PI to BB is not critical, return
+/// false.  Otherwise, split all edges between the two blocks and return true.
+/// This updates all of the same analyses as the other SplitCriticalEdge
+/// function.  If P is specified, it updates the analyses
+/// described above.
+inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) {
+  bool MadeChange = false;
+  TerminatorInst *TI = (*PI)->getTerminator();
+  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
+    if (TI->getSuccessor(i) == Succ)
+      MadeChange |= SplitCriticalEdge(TI, i, P);
+  return MadeChange;
+}
+
+/// SplitCriticalEdge - If an edge from Src to Dst is critical, split the edge
+/// 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) {
+  TerminatorInst *TI = Src->getTerminator();
+  unsigned i = 0;
+  while (1) {
+    assert(i != TI->getNumSuccessors() && "Edge doesn't exist!");
+    if (TI->getSuccessor(i) == Dst)
+      return SplitCriticalEdge(TI, i, P, MergeIdenticalEdges);
+    ++i;
+  }
+}
+
+/// SplitEdge -  Split the edge connecting specified block. Pass P must 
+/// not be NULL. 
+BasicBlock *SplitEdge(BasicBlock *From, BasicBlock *To, Pass *P);
+
+/// SplitBlock - Split the specified block at the specified instruction - every
+/// thing before SplitPt stays in Old and everything starting with SplitPt moves
+/// to a new block.  The two blocks are joined by an unconditional branch and
+/// the loop info is updated.
+///
+BasicBlock *SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P);
+ 
+/// SplitBlockPredecessors - This method transforms BB by introducing a new
+/// basic block into the function, and moving some of the predecessors of BB to
+/// be predecessors of the new block.  The new predecessors are indicated by the
+/// 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.
+BasicBlock *SplitBlockPredecessors(BasicBlock *BB, BasicBlock *const *Preds,
+                                   unsigned NumPreds, const char *Suffix,
+                                   Pass *P = 0);
+  
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/Utils/BasicInliner.h b/include/llvm/Transforms/Utils/BasicInliner.h
new file mode 100644
index 0000000..6a57055
--- /dev/null
+++ b/include/llvm/Transforms/Utils/BasicInliner.h
@@ -0,0 +1,55 @@
+//===- BasicInliner.h - Basic function level inliner ------------*- 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 a simple function based inliner that does not use
+// call graph information. 
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef BASICINLINER_H
+#define BASICINLINER_H
+
+#include "llvm/Transforms/Utils/InlineCost.h"
+
+namespace llvm {
+
+  class Function;
+  class TargetData;
+  struct BasicInlinerImpl;
+
+  /// BasicInliner - BasicInliner provides function level inlining interface.
+  /// Clients provide list of functions which are inline without using
+  /// module level call graph information. Note that the BasicInliner is
+  /// free to delete a function if it is inlined into all call sites.
+  class BasicInliner {
+  public:
+    
+    explicit BasicInliner(TargetData *T = NULL);
+    ~BasicInliner();
+
+    /// addFunction - Add function into the list of functions to process.
+    /// All functions must be inserted using this interface before invoking
+    /// inlineFunctions().
+    void addFunction(Function *F);
+
+    /// neverInlineFunction - Sometimes a function is never to be inlined 
+    /// because of one or other reason. 
+    void neverInlineFunction(Function *F);
+
+    /// inlineFuctions - Walk all call sites in all functions supplied by
+    /// client. Inline as many call sites as possible. Delete completely
+    /// inlined functions.
+    void inlineFunctions();
+
+  private:
+    BasicInlinerImpl *Impl;
+  };
+}
+
+#endif
diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h
new file mode 100644
index 0000000..1e2bbaa
--- /dev/null
+++ b/include/llvm/Transforms/Utils/Cloning.h
@@ -0,0 +1,191 @@
+//===- Cloning.h - Clone various parts of LLVM programs ---------*- 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 various functions that are used to clone chunks of LLVM
+// code for various purposes.  This varies from copying whole modules into new
+// modules, to cloning functions with different arguments, to inlining
+// functions, to copying basic blocks to support loop unrolling or superblock
+// formation, etc.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_CLONING_H
+#define LLVM_TRANSFORMS_UTILS_CLONING_H
+
+#include <vector>
+#include "llvm/ADT/DenseMap.h"
+
+namespace llvm {
+
+class Module;
+class Function;
+class Pass;
+class LPPassManager;
+class BasicBlock;
+class Value;
+class CallInst;
+class InvokeInst;
+class ReturnInst;
+class CallSite;
+class Trace;
+class CallGraph;
+class TargetData;
+class LoopInfo;
+template<class N> class LoopBase;
+typedef LoopBase<BasicBlock> Loop;
+
+/// CloneModule - Return an exact copy of the specified module
+///
+Module *CloneModule(const Module *M);
+Module *CloneModule(const Module *M, DenseMap<const Value*, Value*> &ValueMap);
+
+/// ClonedCodeInfo - This struct can be used to capture information about code
+/// being cloned, while it is being cloned.
+struct ClonedCodeInfo {
+  /// ContainsCalls - This is set to true if the cloned code contains a normal
+  /// call instruction.
+  bool ContainsCalls;
+  
+  /// ContainsUnwinds - This is set to true if the cloned code contains an
+  /// unwind instruction.
+  bool ContainsUnwinds;
+  
+  /// ContainsDynamicAllocas - This is set to true if the cloned code contains
+  /// a 'dynamic' alloca.  Dynamic allocas are allocas that are either not in
+  /// the entry block or they are in the entry block but are not a constant
+  /// size.
+  bool ContainsDynamicAllocas;
+  
+  ClonedCodeInfo() {
+    ContainsCalls = false;
+    ContainsUnwinds = false;
+    ContainsDynamicAllocas = false;
+  }
+};
+
+
+/// CloneBasicBlock - Return a copy of the specified basic block, but without
+/// embedding the block into a particular function.  The block returned is an
+/// exact copy of the specified basic block, without any remapping having been
+/// performed.  Because of this, this is only suitable for applications where
+/// the basic block will be inserted into the same function that it was cloned
+/// from (loop unrolling would use this, for example).
+///
+/// Also, note that this function makes a direct copy of the basic block, and
+/// can thus produce illegal LLVM code.  In particular, it will copy any PHI
+/// nodes from the original block, even though there are no predecessors for the
+/// newly cloned block (thus, phi nodes will have to be updated).  Also, this
+/// block will branch to the old successors of the original block: these
+/// successors will have to have any PHI nodes updated to account for the new
+/// incoming edges.
+///
+/// The correlation between instructions in the source and result basic blocks
+/// is recorded in the ValueMap map.
+///
+/// If you have a particular suffix you'd like to use to add to any cloned
+/// names, specify it as the optional third parameter.
+///
+/// If you would like the basic block to be auto-inserted into the end of a
+/// function, you can specify it as the optional fourth parameter.
+///
+/// If you would like to collect additional information about the cloned
+/// function, you can specify a ClonedCodeInfo object with the optional fifth
+/// parameter.
+///
+BasicBlock *CloneBasicBlock(const BasicBlock *BB,
+                            DenseMap<const Value*, Value*> &ValueMap,
+                            const char *NameSuffix = "", Function *F = 0,
+                            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, 
+                DenseMap<const Value *, Value *> &ValueMap, Pass *P);
+
+/// CloneFunction - Return a copy of the specified function, but without
+/// embedding the function into another module.  Also, any references specified
+/// in the ValueMap are changed to refer to their mapped value instead of the
+/// original one.  If any of the arguments to the function are in the ValueMap,
+/// the arguments are deleted from the resultant function.  The ValueMap is
+/// updated to include mappings from all of the instructions and basicblocks in
+/// the function from their old to new values.  The final argument captures
+/// information about the cloned code if non-null.
+///
+Function *CloneFunction(const Function *F,
+                        DenseMap<const Value*, Value*> &ValueMap,
+                        ClonedCodeInfo *CodeInfo = 0);
+
+/// CloneFunction - Version of the function that doesn't need the ValueMap.
+///
+inline Function *CloneFunction(const Function *F, ClonedCodeInfo *CodeInfo = 0){
+  DenseMap<const Value*, Value*> ValueMap;
+  return CloneFunction(F, ValueMap, CodeInfo);
+}
+
+/// Clone OldFunc into NewFunc, transforming the old arguments into references
+/// to ArgMap values.  Note that if NewFunc already has basic blocks, the ones
+/// cloned into it will be added to the end of the function.  This function
+/// fills in a list of return instructions, and can optionally append the
+/// specified suffix to all values cloned.
+///
+void CloneFunctionInto(Function *NewFunc, const Function *OldFunc,
+                       DenseMap<const Value*, Value*> &ValueMap,
+                       std::vector<ReturnInst*> &Returns,
+                       const char *NameSuffix = "", 
+                       ClonedCodeInfo *CodeInfo = 0);
+
+/// CloneAndPruneFunctionInto - This works exactly like CloneFunctionInto,
+/// except that it does some simple constant prop and DCE on the fly.  The
+/// effect of this is to copy significantly less code in cases where (for
+/// example) a function call with constant arguments is inlined, and those
+/// constant arguments cause a significant amount of code in the callee to be
+/// dead.  Since this doesn't produce an exactly copy of the input, it can't be
+/// used for things like CloneFunction or CloneModule.
+void CloneAndPruneFunctionInto(Function *NewFunc, const Function *OldFunc,
+                               DenseMap<const Value*, Value*> &ValueMap,
+                               std::vector<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
+/// though.
+///
+/// Note that this only does one level of inlining.  For example, if the
+/// instruction 'call B' is inlined, and 'B' calls 'C', then the call to 'C' now
+/// exists in the instruction stream.  Similiarly this will inline a recursive
+/// function by one level.
+///
+/// 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);
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/Utils/FunctionUtils.h b/include/llvm/Transforms/Utils/FunctionUtils.h
new file mode 100644
index 0000000..dc7ef23
--- /dev/null
+++ b/include/llvm/Transforms/Utils/FunctionUtils.h
@@ -0,0 +1,41 @@
+//===-- Transform/Utils/FunctionUtils.h - Function Utils --------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of transformations manipulate LLVM functions.
+//
+//===----------------------------------------------------------------------===//
+
+#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;
+
+  /// ExtractCodeRegion - rip out a sequence of basic blocks into a new function
+  ///
+  Function* ExtractCodeRegion(DominatorTree& DT,
+                              const std::vector<BasicBlock*> &code,
+                              bool AggregateArgs = false);
+
+  /// ExtractLoop - rip out a natural loop into a new function
+  ///
+  Function* ExtractLoop(DominatorTree& DT, Loop *L,
+                        bool AggregateArgs = false);
+
+  /// ExtractBasicBlock - rip out a basic block into a new function
+  ///
+  Function* ExtractBasicBlock(BasicBlock *BB, bool AggregateArgs = false);
+}
+
+#endif
diff --git a/include/llvm/Transforms/Utils/InlineCost.h b/include/llvm/Transforms/Utils/InlineCost.h
new file mode 100644
index 0000000..f275b76
--- /dev/null
+++ b/include/llvm/Transforms/Utils/InlineCost.h
@@ -0,0 +1,155 @@
+//===- InlineCost.cpp - Cost analysis for inliner ---------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements heuristics for inlining decisions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_INLINECOST_H
+#define LLVM_TRANSFORMS_UTILS_INLINECOST_H
+
+#include "llvm/ADT/SmallPtrSet.h"
+#include <cassert>
+#include <climits>
+#include <map>
+#include <vector>
+
+namespace llvm {
+
+  class Value;
+  class Function;
+  class CallSite;
+
+  /// InlineCost - Represent the cost of inlining a function. This
+  /// supports special values for functions which should "always" or
+  /// "never" be inlined. Otherwise, the cost represents a unitless
+  /// amount; smaller values increase the likelyhood of the function
+  /// being inlined.
+  class InlineCost {
+    enum Kind {
+      Value,
+      Always,
+      Never
+    };
+
+    // This is a do-it-yourself implementation of
+    //   int Cost : 30;
+    //   unsigned Type : 2;
+    // We used to use bitfields, but they were sometimes miscompiled (PR3822).
+    enum { TYPE_BITS = 2 };
+    enum { COST_BITS = unsigned(sizeof(unsigned)) * CHAR_BIT - TYPE_BITS };
+    unsigned TypedCost; // int Cost : COST_BITS; unsigned Type : TYPE_BITS;
+
+    Kind getType() const {
+      return Kind(TypedCost >> COST_BITS);
+    }
+
+    int getCost() const {
+      // Sign-extend the bottom COST_BITS bits.
+      return (int(TypedCost << TYPE_BITS)) >> TYPE_BITS;
+    }
+
+    InlineCost(int C, int T) {
+      TypedCost = (unsigned(C << TYPE_BITS) >> TYPE_BITS) | (T << COST_BITS);
+      assert(getCost() == C && "Cost exceeds InlineCost precision");
+    }
+  public:
+    static InlineCost get(int Cost) { return InlineCost(Cost, Value); }
+    static InlineCost getAlways() { return InlineCost(0, Always); }
+    static InlineCost getNever() { return InlineCost(0, Never); }
+
+    bool isVariable() const { return getType() == Value; }
+    bool isAlways() const { return getType() == Always; }
+    bool isNever() const { return getType() == Never; }
+
+    /// getValue() - Return a "variable" inline cost's amount. It is
+    /// an error to call this on an "always" or "never" InlineCost.
+    int getValue() const {
+      assert(getType() == Value && "Invalid access of InlineCost");
+      return getCost();
+    }
+  };
+  
+  /// InlineCostAnalyzer - Cost analyzer used by inliner.
+  class InlineCostAnalyzer {
+    struct ArgInfo {
+    public:
+      unsigned ConstantWeight;
+      unsigned AllocaWeight;
+      
+      ArgInfo(unsigned CWeight, unsigned AWeight)
+        : ConstantWeight(CWeight), AllocaWeight(AWeight) {}
+    };
+    
+    // FunctionInfo - For each function, calculate the size of it in blocks and
+    // instructions.
+    struct FunctionInfo {
+      /// NeverInline - True if this callee should never be inlined into a
+      /// caller.
+      bool NeverInline;
+      
+      /// usesDynamicAlloca - True if this function calls alloca (in the C sense).
+      bool usesDynamicAlloca;
+
+      /// NumInsts, NumBlocks - Keep track of how large each function is, which
+      /// is used to estimate the code size cost of inlining it.
+      unsigned NumInsts, NumBlocks;
+
+      /// NumVectorInsts - Keep track of how many instructions produce vector
+      /// values.  The inliner is being more aggressive with inlining vector
+      /// kernels.
+      unsigned NumVectorInsts;
+      
+      /// ArgumentWeights - Each formal argument of the function is inspected to
+      /// see if it is used in any contexts where making it a constant or alloca
+      /// would reduce the code size.  If so, we add some value to the argument
+      /// entry here.
+      std::vector<ArgInfo> ArgumentWeights;
+      
+      FunctionInfo() : NeverInline(false), usesDynamicAlloca(false), NumInsts(0),
+                       NumBlocks(0), NumVectorInsts(0) {}
+      
+      /// analyzeFunction - Fill in the current structure with information
+      /// gleaned from the specified function.
+      void analyzeFunction(Function *F);
+
+      /// CountCodeReductionForConstant - Figure out an approximation for how
+      /// many instructions will be constant folded if the specified value is
+      /// constant.
+      unsigned CountCodeReductionForConstant(Value *V);
+      
+      /// CountCodeReductionForAlloca - Figure out an approximation of how much
+      /// smaller the function will be if it is inlined into a context where an
+      /// argument becomes an alloca.
+      ///
+      unsigned CountCodeReductionForAlloca(Value *V);
+    };
+
+    std::map<const Function *, FunctionInfo> CachedFunctionInfo;
+
+  public:
+
+    /// getInlineCost - The heuristic used to determine if we should inline the
+    /// function call or not.
+    ///
+    InlineCost getInlineCost(CallSite CS,
+                             SmallPtrSet<const Function *, 16> &NeverInline);
+
+    /// getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a
+    /// higher threshold to determine if the function call should be inlined.
+    float getInlineFudgeFactor(CallSite CS);
+
+    /// resetCachedFunctionInfo - erase any cached cost info for this function.
+    void resetCachedCostInfo(Function* Caller) {
+      CachedFunctionInfo[Caller].NumBlocks = 0;
+    }
+  };
+}
+
+#endif
diff --git a/include/llvm/Transforms/Utils/Local.h b/include/llvm/Transforms/Utils/Local.h
new file mode 100644
index 0000000..5ea1a50
--- /dev/null
+++ b/include/llvm/Transforms/Utils/Local.h
@@ -0,0 +1,116 @@
+//===-- Local.h - Functions to perform local transformations ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This family of functions perform various local transformations to the
+// program.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H
+#define LLVM_TRANSFORMS_UTILS_LOCAL_H
+
+namespace llvm {
+
+class User;
+class BasicBlock;
+class Instruction;
+class Value;
+class Pass;
+class PHINode;
+class AllocaInst;
+class ConstantExpr;
+class TargetData;
+struct DbgInfoIntrinsic;
+
+template<typename T> class SmallVectorImpl;
+  
+//===----------------------------------------------------------------------===//
+//  Local constant propagation.
+//
+
+/// ConstantFoldTerminator - If a terminator instruction is predicated on a
+/// constant value, convert it into an unconditional branch to the constant
+/// destination.  This is a nontrivial operation because the successors of this
+/// basic block must have their PHI nodes updated.
+///
+bool ConstantFoldTerminator(BasicBlock *BB);
+
+//===----------------------------------------------------------------------===//
+//  Local dead code elimination.
+//
+
+/// isInstructionTriviallyDead - Return true if the result produced by the
+/// instruction is not used, and the instruction has no side effects.
+///
+bool isInstructionTriviallyDead(Instruction *I);
+
+/// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
+/// trivially dead instruction, delete it.  If that makes any of its operands
+/// trivially dead, delete them too, recursively.
+void RecursivelyDeleteTriviallyDeadInstructions(Value *V);
+
+/// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
+/// dead PHI node, due to being a def-use chain of single-use nodes that
+/// either forms a cycle or is terminated by a trivially dead instruction,
+/// delete it.  If that makes any of its operands trivially dead, delete them
+/// too, recursively.
+void RecursivelyDeleteDeadPHINode(PHINode *PN);
+
+//===----------------------------------------------------------------------===//
+//  Control Flow Graph Restructuring.
+//
+
+/// MergeBasicBlockIntoOnlyPred - BB is a block with one predecessor and its
+/// predecessor is known to have one successor (BB!).  Eliminate the edge
+/// between them, moving the instructions in the predecessor into BB.  This
+/// deletes the predecessor block.
+///
+void MergeBasicBlockIntoOnlyPred(BasicBlock *BB);
+    
+  
+/// SimplifyCFG - This function is used to do simplification of a CFG.  For
+/// example, it adjusts branches to branches to eliminate the extra hop, it
+/// eliminates unreachable basic blocks, and does other "peephole" optimization
+/// of the CFG.  It returns true if a modification was made, possibly deleting
+/// the basic block that was pointed to.
+///
+/// WARNING:  The entry node of a method may not be simplified.
+///
+bool SimplifyCFG(BasicBlock *BB);
+
+/// DemoteRegToStack - This function takes a virtual register computed by an
+/// Instruction and replaces it with a slot in the stack frame, allocated via
+/// alloca.  This allows the CFG to be changed around without fear of
+/// 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,
+                             Instruction *AllocaPoint = 0);
+
+/// DemotePHIToStack - This function takes a virtual register computed by a phi
+/// node and replaces it with a slot in the stack frame, allocated via alloca.
+/// The phi node is deleted and it returns the pointer to the alloca inserted. 
+AllocaInst *DemotePHIToStack(PHINode *P, Instruction *AllocaPoint = 0);
+
+/// OnlyUsedByDbgIntrinsics - Return true if the instruction I is only used
+/// by DbgIntrinsics. If DbgInUses is specified then the vector is filled 
+/// with DbgInfoIntrinsic that use the instruction I.
+bool OnlyUsedByDbgInfoIntrinsics(Instruction *I, 
+                           SmallVectorImpl<DbgInfoIntrinsic *> *DbgInUses = 0);
+
+/// UserIsDebugInfo - Return true if U is a constant expr used by 
+/// llvm.dbg.variable or llvm.dbg.global_variable
+bool UserIsDebugInfo(User *U);
+
+/// RemoveDbgInfoUser - Remove an User which is representing debug info.
+void RemoveDbgInfoUser(User *U);
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/Utils/PromoteMemToReg.h b/include/llvm/Transforms/Utils/PromoteMemToReg.h
new file mode 100644
index 0000000..35cfadd
--- /dev/null
+++ b/include/llvm/Transforms/Utils/PromoteMemToReg.h
@@ -0,0 +1,46 @@
+//===- PromoteMemToReg.h - Promote Allocas to Scalars -----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file exposes an interface to promote alloca instructions to SSA
+// registers, by using the SSA construction algorithm.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef TRANSFORMS_UTILS_PROMOTEMEMTOREG_H
+#define TRANSFORMS_UTILS_PROMOTEMEMTOREG_H
+
+#include <vector>
+
+namespace llvm {
+
+class AllocaInst;
+class DominatorTree;
+class DominanceFrontier;
+class AliasSetTracker;
+
+/// isAllocaPromotable - Return true if this alloca is legal for promotion.
+/// This is true if there are only loads and stores to the alloca...
+///
+bool isAllocaPromotable(const AllocaInst *AI);
+
+/// PromoteMemToReg - Promote the specified list of alloca instructions into
+/// scalar registers, inserting PHI nodes as appropriate.  This function makes
+/// use of DominanceFrontier information.  This function does not modify the CFG
+/// of the function at all.  All allocas must be from the same function.
+///
+/// If AST is specified, the specified tracker is updated to reflect changes
+/// made to the IR.
+///
+void PromoteMemToReg(const std::vector<AllocaInst*> &Allocas,
+                     DominatorTree &DT, DominanceFrontier &DF,
+                     AliasSetTracker *AST = 0);
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h b/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h
new file mode 100644
index 0000000..c2d0993
--- /dev/null
+++ b/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h
@@ -0,0 +1,49 @@
+//===-- UnifyFunctionExitNodes.h - Ensure fn's have one return --*- 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 ensure that functions have at most one return and one
+// unwind instruction in them.  Additionally, it keeps track of which node is
+// the new exit node of the CFG.  If there are no return or unwind instructions
+// in the function, the getReturnBlock/getUnwindBlock methods will return a null
+// pointer.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UNIFYFUNCTIONEXITNODES_H
+#define LLVM_TRANSFORMS_UNIFYFUNCTIONEXITNODES_H
+
+#include "llvm/Pass.h"
+
+namespace llvm {
+
+struct UnifyFunctionExitNodes : public FunctionPass {
+  BasicBlock *ReturnBlock, *UnwindBlock, *UnreachableBlock;
+public:
+  static char ID; // Pass identification, replacement for typeid
+  UnifyFunctionExitNodes() : FunctionPass(&ID),
+                             ReturnBlock(0), UnwindBlock(0) {}
+
+  // We can preserve non-critical-edgeness when we unify function exit nodes
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+
+  // getReturn|Unwind|UnreachableBlock - Return the new single (or nonexistant)
+  // return, unwind, or unreachable  basic blocks in the CFG.
+  //
+  BasicBlock *getReturnBlock() const { return ReturnBlock; }
+  BasicBlock *getUnwindBlock() const { return UnwindBlock; }
+  BasicBlock *getUnreachableBlock() const { return UnreachableBlock; }
+
+  virtual bool runOnFunction(Function &F);
+};
+
+Pass *createUnifyFunctionExitNodesPass();
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/Utils/UnrollLoop.h b/include/llvm/Transforms/Utils/UnrollLoop.h
new file mode 100644
index 0000000..a9c0bf6
--- /dev/null
+++ b/include/llvm/Transforms/Utils/UnrollLoop.h
@@ -0,0 +1,29 @@
+//===- llvm/Transforms/Utils/UnrollLoop.h - Unrolling utilities -*- 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 some loop unrolling utilities. It does not define any
+// actual pass or policy, but provides a single function to perform loop
+// unrolling.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
+#define LLVM_TRANSFORMS_UTILS_UNROLLLOOP_H
+
+#include "llvm/Analysis/LoopInfo.h"
+
+namespace llvm {
+
+class LPPassManager;
+
+bool UnrollLoop(Loop *L, unsigned Count, LoopInfo* LI, LPPassManager* LPM);
+
+}
+
+#endif
diff --git a/include/llvm/Transforms/Utils/ValueMapper.h b/include/llvm/Transforms/Utils/ValueMapper.h
new file mode 100644
index 0000000..ed33413
--- /dev/null
+++ b/include/llvm/Transforms/Utils/ValueMapper.h
@@ -0,0 +1,29 @@
+//===- ValueMapper.h - Interface shared by lib/Transforms/Utils -*- 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 MapValue interface which is used by various parts of
+// the Transforms/Utils library to implement cloning and linking facilities.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef VALUEMAPPER_H
+#define VALUEMAPPER_H
+
+#include "llvm/ADT/DenseMap.h"
+
+namespace llvm {
+  class Value;
+  class Instruction;
+  typedef DenseMap<const Value *, Value *> ValueMapTy;
+
+  Value *MapValue(const Value *V, ValueMapTy &VM);
+  void RemapInstruction(Instruction *I, ValueMapTy &VM);
+} // End llvm namespace
+
+#endif