Import LLVM, at r72732.

16 files changed, 1730 insertions, 0 deletions

diff --git a/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h
new file mode 100644
index 0000000..4372ea0
--- /dev/null
+++ b/include/llvm/Transforms/IPO.h
@@ -0,0 +1,219 @@
+//===- llvm/Transforms/IPO.h - Interprocedural Transformations --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This header file defines prototypes for accessor functions that expose passes
+// in the IPO transformations library.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_H
+#define LLVM_TRANSFORMS_IPO_H
+
+#include <vector>
+
+namespace llvm {
+
+class FunctionPass;
+class ModulePass;
+class Pass;
+class Function;
+class BasicBlock;
+class GlobalValue;
+
+//===----------------------------------------------------------------------===//
+//
+// These functions removes symbols from functions and modules.  If OnlyDebugInfo
+// is true, only debugging information is removed from the module.
+//
+ModulePass *createStripSymbolsPass(bool OnlyDebugInfo = false);
+
+//===----------------------------------------------------------------------===//
+//
+// These functions strips symbols from functions and modules.  
+// Only debugging information is not stripped.
+//
+ModulePass *createStripNonDebugSymbolsPass();
+
+//===----------------------------------------------------------------------===//
+//
+// These pass removes llvm.dbg.declare intrinsics.
+ModulePass *createStripDebugDeclarePass();
+
+//===----------------------------------------------------------------------===//
+/// createLowerSetJmpPass - This function lowers the setjmp/longjmp intrinsics
+/// to invoke/unwind instructions.  This should really be part of the C/C++
+/// front-end, but it's so much easier to write transformations in LLVM proper.
+///
+ModulePass *createLowerSetJmpPass();
+
+//===----------------------------------------------------------------------===//
+/// createConstantMergePass - This function returns a new pass that merges
+/// duplicate global constants together into a single constant that is shared.
+/// This is useful because some passes (ie TraceValues) insert a lot of string
+/// constants into the program, regardless of whether or not they duplicate an
+/// existing string.
+///
+ModulePass *createConstantMergePass();
+
+
+//===----------------------------------------------------------------------===//
+/// createGlobalOptimizerPass - This function returns a new pass that optimizes
+/// non-address taken internal globals.
+///
+ModulePass *createGlobalOptimizerPass();
+
+
+//===----------------------------------------------------------------------===//
+/// createRaiseAllocationsPass - Return a new pass that transforms malloc and
+/// free function calls into malloc and free instructions.
+///
+ModulePass *createRaiseAllocationsPass();
+
+
+//===----------------------------------------------------------------------===//
+/// createDeadTypeEliminationPass - Return a new pass that eliminates symbol
+/// table entries for types that are never used.
+///
+ModulePass *createDeadTypeEliminationPass();
+
+
+//===----------------------------------------------------------------------===//
+/// createGlobalDCEPass - This transform is designed to eliminate unreachable
+/// internal globals (functions or global variables)
+///
+ModulePass *createGlobalDCEPass();
+
+
+//===----------------------------------------------------------------------===//
+/// createGVExtractionPass - If deleteFn is true, this pass deletes as
+/// the specified global values. Otherwise, it deletes as much of the module as
+/// possible, except for the global values specified.
+///
+ModulePass *createGVExtractionPass(std::vector<GlobalValue*>& GVs, bool 
+                                   deleteFn = false, 
+                                   bool relinkCallees = false);
+
+//===----------------------------------------------------------------------===//
+/// createFunctionInliningPass - Return a new pass object that uses a heuristic
+/// to inline direct function calls to small functions.
+///
+Pass *createFunctionInliningPass();
+Pass *createFunctionInliningPass(int Threshold);
+
+//===----------------------------------------------------------------------===//
+/// createAlwaysInlinerPass - Return a new pass object that inlines only 
+/// functions that are marked as "always_inline".
+Pass *createAlwaysInlinerPass();
+
+//===----------------------------------------------------------------------===//
+/// createPruneEHPass - Return a new pass object which transforms invoke
+/// instructions into calls, if the callee can _not_ unwind the stack.
+///
+Pass *createPruneEHPass();
+
+//===----------------------------------------------------------------------===//
+/// createInternalizePass - This pass loops over all of the functions in the
+/// input module, internalizing all globals (functions and variables) not part
+/// of the api.  If a list of symbols is specified with the
+/// -internalize-public-api-* command line options, those symbols are not
+/// internalized and all others are.  Otherwise if AllButMain is set and the
+/// main function is found, all other globals are marked as internal. If no api
+/// is supplied and AllButMain is not set, or no main function is found, nothing
+/// is internalized.
+///
+ModulePass *createInternalizePass(bool AllButMain);
+
+/// createInternalizePass - This pass loops over all of the functions in the
+/// input module, internalizing all globals (functions and variables) not in the
+/// given exportList.
+///
+/// Note that commandline options that are used with the above function are not
+/// used now! Also, when exportList is empty, nothing is internalized.
+ModulePass *createInternalizePass(const std::vector<const char *> &exportList);
+
+//===----------------------------------------------------------------------===//
+/// createDeadArgEliminationPass - This pass removes arguments from functions
+/// which are not used by the body of the function.
+///
+ModulePass *createDeadArgEliminationPass();
+
+/// DeadArgHacking pass - Same as DAE, but delete arguments of external
+/// functions as well.  This is definitely not safe, and should only be used by
+/// bugpoint.
+ModulePass *createDeadArgHackingPass();
+
+//===----------------------------------------------------------------------===//
+/// createArgumentPromotionPass - This pass promotes "by reference" arguments to
+/// be passed by value if the number of elements passed is smaller or
+/// equal to maxElements (maxElements == 0 means always promote).
+///
+Pass *createArgumentPromotionPass(unsigned maxElements = 3);
+Pass *createStructRetPromotionPass();
+
+//===----------------------------------------------------------------------===//
+/// createIPConstantPropagationPass - This pass propagates constants from call
+/// sites into the bodies of functions.
+///
+ModulePass *createIPConstantPropagationPass();
+
+//===----------------------------------------------------------------------===//
+/// createIPSCCPPass - This pass propagates constants from call sites into the
+/// bodies of functions, and keeps track of whether basic blocks are executable
+/// in the process.
+///
+ModulePass *createIPSCCPPass();
+
+//===----------------------------------------------------------------------===//
+//
+/// createLoopExtractorPass - This pass extracts all natural loops from the
+/// program into a function if it can.
+///
+FunctionPass *createLoopExtractorPass();
+
+/// createSingleLoopExtractorPass - This pass extracts one natural loop from the
+/// program into a function if it can.  This is used by bugpoint.
+///
+FunctionPass *createSingleLoopExtractorPass();
+
+/// createBlockExtractorPass - This pass extracts all blocks (except those
+/// specified in the argument list) from the functions in the module.
+///
+ModulePass *createBlockExtractorPass(const std::vector<BasicBlock*> &BTNE);
+
+/// createIndMemRemPass - This pass removes potential indirect calls of
+/// malloc and free
+ModulePass *createIndMemRemPass();
+
+/// createStripDeadPrototypesPass - This pass removes any function declarations
+/// (prototypes) that are not used.
+ModulePass *createStripDeadPrototypesPass();
+
+//===----------------------------------------------------------------------===//
+/// createPartialSpecializationPass - This pass specializes functions for
+/// constant arguments.
+///
+ModulePass *createPartialSpecializationPass();
+
+//===----------------------------------------------------------------------===//
+/// createFunctionAttrsPass - This pass discovers functions that do not access
+/// memory, or only read memory, and gives them the readnone/readonly attribute.
+/// It also discovers function arguments that are not captured by the function
+/// and marks them with the nocapture attribute.
+///
+Pass *createFunctionAttrsPass();
+
+//===----------------------------------------------------------------------===//
+/// createMergeFunctionsPass - This pass discovers identical functions and
+/// collapses them.
+///
+ModulePass *createMergeFunctionsPass();
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/IPO/InlinerPass.h b/include/llvm/Transforms/IPO/InlinerPass.h
new file mode 100644
index 0000000..b370e96
--- /dev/null
+++ b/include/llvm/Transforms/IPO/InlinerPass.h
@@ -0,0 +1,90 @@
+//===- InlinerPass.h - Code common to all inliners --------------*- 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 policy-based bottom-up inliner.  This file
+// implements all of the boring mechanics of the bottom-up inlining, while the
+// subclass determines WHAT to inline, which is the much more interesting
+// component.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef INLINER_H
+#define INLINER_H
+
+#include "llvm/CallGraphSCCPass.h"
+#include "llvm/Transforms/Utils/InlineCost.h"
+#include "llvm/Target/TargetData.h"
+
+
+namespace llvm {
+  class CallSite;
+
+/// Inliner - This class contains all of the helper code which is used to
+/// perform the inlining operations that do not depend on the policy.
+///
+struct Inliner : public CallGraphSCCPass {
+  explicit Inliner(void *ID);
+  explicit Inliner(void *ID, int Threshold);
+
+  /// getAnalysisUsage - For this class, we declare that we require and preserve
+  /// the call graph.  If the derived class implements this method, it should
+  /// always explicitly call the implementation here.
+  virtual void getAnalysisUsage(AnalysisUsage &Info) const;
+
+  // Main run interface method, this implements the interface required by the
+  // Pass class.
+  virtual bool runOnSCC(const std::vector<CallGraphNode *> &SCC);
+
+  // doFinalization - Remove now-dead linkonce functions at the end of
+  // processing to avoid breaking the SCC traversal.
+  virtual bool doFinalization(CallGraph &CG);
+
+  // InlineCallIfPossible
+  bool InlineCallIfPossible(CallSite CS, CallGraph &CG,
+                            const SmallPtrSet<Function*, 8> &SCCFunctions,
+                            const TargetData &TD);
+
+  /// This method returns the value specified by the -inline-threshold value,
+  /// specified on the command line.  This is typically not directly needed.
+  ///
+  unsigned getInlineThreshold() const { return InlineThreshold; }
+
+  /// getInlineCost - This method must be implemented by the subclass to
+  /// determine the cost of inlining the specified call site.  If the cost
+  /// returned is greater than the current inline threshold, the call site is
+  /// not inlined.
+  ///
+  virtual InlineCost getInlineCost(CallSite CS) = 0;
+
+  // getInlineFudgeFactor - Return a > 1.0 factor if the inliner should use a
+  // higher threshold to determine if the function call should be inlined.
+  ///
+  virtual float getInlineFudgeFactor(CallSite CS) = 0;
+
+  /// resetCachedCostInfo - erase any cached cost data from the derived class.
+  /// If the derived class has no such data this can be empty.
+  /// 
+  virtual void resetCachedCostInfo(Function* Caller) = 0;
+
+  /// removeDeadFunctions - Remove dead functions that are not included in
+  /// DNR (Do Not Remove) list.
+  bool removeDeadFunctions(CallGraph &CG, 
+                           SmallPtrSet<const Function *, 16> *DNR = NULL);
+private:
+  // InlineThreshold - Cache the value here for easy access.
+  unsigned InlineThreshold;
+
+  /// shouldInline - Return true if the inliner should attempt to
+  /// inline at the given CallSite.
+  bool shouldInline(CallSite CS);
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h
new file mode 100644
index 0000000..698e248
--- /dev/null
+++ b/include/llvm/Transforms/Instrumentation.h
@@ -0,0 +1,37 @@
+//===- Transforms/Instrumentation.h - Instrumentation passes ----*- 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 constructor functions for instrumentation passes.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_INSTRUMENTATION_H
+#define LLVM_TRANSFORMS_INSTRUMENTATION_H
+
+namespace llvm {
+
+class ModulePass;
+class FunctionPass;
+
+// Insert function profiling instrumentation
+ModulePass *createFunctionProfilerPass();
+
+// Insert block profiling instrumentation
+ModulePass *createBlockProfilerPass();
+
+// Insert edge profiling instrumentation
+ModulePass *createEdgeProfilerPass();
+
+// Random Sampling Profiling Framework
+ModulePass* createNullProfilerRSPass();
+FunctionPass* createRSProfilingPass();
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/RSProfiling.h b/include/llvm/Transforms/RSProfiling.h
new file mode 100644
index 0000000..98ec396
--- /dev/null
+++ b/include/llvm/Transforms/RSProfiling.h
@@ -0,0 +1,38 @@
+//===- RSProfiling.cpp - Various profiling using random sampling ----------===//
+//
+//                      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 abstract interface that a profiler must implement to
+// support the random profiling transform.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_RSPROFILING_H
+#define LLVM_TRANSFORMS_RSPROFILING_H
+
+namespace llvm {
+  //===--------------------------------------------------------------------===//
+  /// RSProfilers - The basic Random Sampling Profiler Interface  Any profiler 
+  /// that implements this interface can be transformed by the random sampling
+  /// pass to be sample based rather than always on.
+  ///
+  /// The only exposed function can be queried to find out if an instruction
+  /// was original or if it was inserted by the profiler.  Implementations of
+  /// this interface are expected to chain to other implementations, such that
+  /// multiple profilers can be support simultaniously.
+  struct RSProfilers : public ModulePass {
+    static char ID; // Pass identification, replacement for typeinfo
+    RSProfilers() : ModulePass(&ID) {}
+
+    /// isProfiling - This method returns true if the value passed it was 
+    /// inserted by the profiler.
+    virtual bool isProfiling(Value* v) = 0;
+  };
+}
+
+#endif
diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h
new file mode 100644
index 0000000..2c3fdd4
--- /dev/null
+++ b/include/llvm/Transforms/Scalar.h
@@ -0,0 +1,342 @@
+//===-- Scalar.h - Scalar Transformations -----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This header file defines prototypes for accessor functions that expose passes
+// in the Scalar transformations library.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_H
+#define LLVM_TRANSFORMS_SCALAR_H
+
+namespace llvm {
+
+class FunctionPass;
+class Pass;
+class GetElementPtrInst;
+class PassInfo;
+class TerminatorInst;
+class TargetLowering;
+
+//===----------------------------------------------------------------------===//
+//
+// ConstantPropagation - A worklist driven constant propagation pass
+//
+FunctionPass *createConstantPropagationPass();
+
+//===----------------------------------------------------------------------===//
+//
+// SCCP - Sparse conditional constant propagation.
+//
+FunctionPass *createSCCPPass();
+
+//===----------------------------------------------------------------------===//
+//
+// DeadInstElimination - This pass quickly removes trivially dead instructions
+// without modifying the CFG of the function.  It is a BasicBlockPass, so it
+// runs efficiently when queued next to other BasicBlockPass's.
+//
+Pass *createDeadInstEliminationPass();
+
+//===----------------------------------------------------------------------===//
+//
+// DeadCodeElimination - This pass is more powerful than DeadInstElimination,
+// because it is worklist driven that can potentially revisit instructions when
+// their other instructions become dead, to eliminate chains of dead
+// computations.
+//
+FunctionPass *createDeadCodeEliminationPass();
+
+//===----------------------------------------------------------------------===//
+//
+// DeadStoreElimination - This pass deletes stores that are post-dominated by
+// must-aliased stores and are not loaded used between the stores.
+//
+FunctionPass *createDeadStoreEliminationPass();
+
+//===----------------------------------------------------------------------===//
+//
+// AggressiveDCE - This pass uses the SSA based Aggressive DCE algorithm.  This
+// algorithm assumes instructions are dead until proven otherwise, which makes
+// it more successful are removing non-obviously dead instructions.
+//
+FunctionPass *createAggressiveDCEPass();
+
+//===----------------------------------------------------------------------===//
+//
+// ScalarReplAggregates - Break up alloca's of aggregates into multiple allocas
+// if possible.
+//
+FunctionPass *createScalarReplAggregatesPass(signed Threshold = -1);
+
+//===----------------------------------------------------------------------===//
+//
+// InductionVariableSimplify - Transform induction variables in a program to all
+// use a single canonical induction variable per loop.
+//
+Pass *createIndVarSimplifyPass();
+
+//===----------------------------------------------------------------------===//
+//
+// InstructionCombining - Combine instructions to form fewer, simple
+// instructions. This pass does not modify the CFG, and has a tendency to make
+// instructions dead, so a subsequent DCE pass is useful.
+//
+// This pass combines things like:
+//    %Y = add int 1, %X
+//    %Z = add int 1, %Y
+// into:
+//    %Z = add int 2, %X
+//
+FunctionPass *createInstructionCombiningPass();
+
+//===----------------------------------------------------------------------===//
+//
+// LICM - This pass is a loop invariant code motion and memory promotion pass.
+//
+Pass *createLICMPass();
+
+//===----------------------------------------------------------------------===//
+//
+// LoopStrengthReduce - This pass is strength reduces GEP instructions that use
+// a loop's canonical induction variable as one of their indices.  It takes an
+// optional parameter used to consult the target machine whether certain
+// transformations are profitable.
+//
+Pass *createLoopStrengthReducePass(const TargetLowering *TLI = 0);
+
+//===----------------------------------------------------------------------===//
+//
+// LoopUnswitch - This pass is a simple loop unswitching pass.
+//
+Pass *createLoopUnswitchPass(bool OptimizeForSize = false);
+
+//===----------------------------------------------------------------------===//
+//
+// LoopUnroll - This pass is a simple loop unrolling pass.
+//
+Pass *createLoopUnrollPass();
+
+//===----------------------------------------------------------------------===//
+//
+// LoopRotate - This pass is a simple loop rotating pass.
+//
+Pass *createLoopRotatePass();
+
+//===----------------------------------------------------------------------===//
+//
+// LoopIndexSplit - This pass divides loop's iteration range by spliting loop
+// such that each individual loop is executed efficiently.
+//
+Pass *createLoopIndexSplitPass();
+
+//===----------------------------------------------------------------------===//
+//
+// PromoteMemoryToRegister - This pass is used to promote memory references to
+// be register references. A simple example of the transformation performed by
+// this pass is:
+//
+//        FROM CODE                           TO CODE
+//   %X = alloca int, uint 1                 ret int 42
+//   store int 42, int *%X
+//   %Y = load int* %X
+//   ret int %Y
+//
+FunctionPass *createPromoteMemoryToRegisterPass();
+extern const PassInfo *const PromoteMemoryToRegisterID;
+
+//===----------------------------------------------------------------------===//
+//
+// DemoteRegisterToMemoryPass - This pass is used to demote registers to memory
+// references. In basically undoes the PromoteMemoryToRegister pass to make cfg
+// hacking easier.
+//
+FunctionPass *createDemoteRegisterToMemoryPass();
+extern const PassInfo *const DemoteRegisterToMemoryID;
+
+//===----------------------------------------------------------------------===//
+//
+// Reassociate - This pass reassociates commutative expressions in an order that
+// is designed to promote better constant propagation, GCSE, LICM, PRE...
+//
+// For example:  4 + (x + 5)  ->  x + (4 + 5)
+//
+FunctionPass *createReassociatePass();
+
+//===----------------------------------------------------------------------===//
+//
+// CondPropagationPass - This pass propagates information about conditional
+// expressions through the program, allowing it to eliminate conditional
+// branches in some cases.
+//
+FunctionPass *createCondPropagationPass();
+
+//===----------------------------------------------------------------------===//
+//
+// TailDuplication - Eliminate unconditional branches through controlled code
+// duplication, creating simpler CFG structures.
+//
+FunctionPass *createTailDuplicationPass();
+
+//===----------------------------------------------------------------------===//
+//
+// JumpThreading - Thread control through mult-pred/multi-succ blocks where some
+// preds always go to some succ.
+//
+FunctionPass *createJumpThreadingPass();
+  
+//===----------------------------------------------------------------------===//
+//
+// CFGSimplification - Merge basic blocks, eliminate unreachable blocks,
+// simplify terminator instructions, etc...
+//
+FunctionPass *createCFGSimplificationPass();
+
+//===----------------------------------------------------------------------===//
+//
+// BreakCriticalEdges - Break all of the critical edges in the CFG by inserting
+// a dummy basic block. This pass may be "required" by passes that cannot deal
+// with critical edges. For this usage, a pass must call:
+//
+//   AU.addRequiredID(BreakCriticalEdgesID);
+//
+// This pass obviously invalidates the CFG, but can update forward dominator
+// (set, immediate dominators, tree, and frontier) information.
+//
+FunctionPass *createBreakCriticalEdgesPass();
+extern const PassInfo *const BreakCriticalEdgesID;
+
+//===----------------------------------------------------------------------===//
+//
+// LoopSimplify - Insert Pre-header blocks into the CFG for every function in
+// the module.  This pass updates dominator information, loop information, and
+// does not add critical edges to the CFG.
+//
+//   AU.addRequiredID(LoopSimplifyID);
+//
+FunctionPass *createLoopSimplifyPass();
+extern const PassInfo *const LoopSimplifyID;
+
+//===----------------------------------------------------------------------===//
+//
+// LowerAllocations - Turn malloc and free instructions into %malloc and %free
+// calls.
+//
+//   AU.addRequiredID(LowerAllocationsID);
+//
+Pass *createLowerAllocationsPass(bool LowerMallocArgToInteger = false);
+extern const PassInfo *const LowerAllocationsID;
+
+//===----------------------------------------------------------------------===//
+//
+// TailCallElimination - This pass eliminates call instructions to the current
+// function which occur immediately before return instructions.
+//
+FunctionPass *createTailCallEliminationPass();
+
+//===----------------------------------------------------------------------===//
+//
+// LowerSwitch - This pass converts SwitchInst instructions into a sequence of
+// chained binary branch instructions.
+//
+FunctionPass *createLowerSwitchPass();
+extern const PassInfo *const LowerSwitchID;
+
+//===----------------------------------------------------------------------===//
+//
+// LowerInvoke - This pass converts invoke and unwind instructions to use sjlj
+// exception handling mechanisms.  Note that after this pass runs the CFG is not
+// entirely accurate (exceptional control flow edges are not correct anymore) so
+// only very simple things should be done after the lowerinvoke pass has run
+// (like generation of native code).  This should *NOT* be used as a general
+// purpose "my LLVM-to-LLVM pass doesn't support the invoke instruction yet"
+// lowering pass.
+//
+FunctionPass *createLowerInvokePass(const TargetLowering *TLI = 0);
+extern const PassInfo *const LowerInvokePassID;
+
+//===----------------------------------------------------------------------===//
+//
+// BlockPlacement - This pass reorders basic blocks in order to increase the
+// number of fall-through conditional branches.
+//
+FunctionPass *createBlockPlacementPass();
+
+//===----------------------------------------------------------------------===//
+//
+// LCSSA - This pass inserts phi nodes at loop boundaries to simplify other loop
+// optimizations.
+//
+Pass *createLCSSAPass();
+extern const PassInfo *const LCSSAID;
+
+//===----------------------------------------------------------------------===//
+//
+// PredicateSimplifier - This pass collapses duplicate variables into one
+// canonical form, and tries to simplify expressions along the way.
+//
+FunctionPass *createPredicateSimplifierPass();
+
+//===----------------------------------------------------------------------===//
+//
+// GVN-PRE - This pass performs global value numbering and partial redundancy
+// elimination.
+//
+FunctionPass *createGVNPREPass();
+
+//===----------------------------------------------------------------------===//
+//
+// GVN - This pass performs global value numbering and redundant load 
+// elimination cotemporaneously.
+//
+FunctionPass *createGVNPass();
+
+//===----------------------------------------------------------------------===//
+//
+// MemCpyOpt - This pass performs optimizations related to eliminating memcpy
+// calls and/or combining multiple stores into memset's.
+//
+FunctionPass *createMemCpyOptPass();
+
+//===----------------------------------------------------------------------===//
+//
+// LoopDeletion - This pass performs DCE of non-infinite loops that it
+// can prove are dead.
+//
+Pass *createLoopDeletionPass();
+  
+//===----------------------------------------------------------------------===//
+//
+/// createSimplifyLibCallsPass - This pass optimizes specific calls to
+/// specific well-known (library) functions.
+FunctionPass *createSimplifyLibCallsPass();
+
+//===----------------------------------------------------------------------===//
+//
+/// createSimplifyHalfPowrLibCallsPass - This is an experimental pass that
+/// optimizes specific half_pow functions.
+FunctionPass *createSimplifyHalfPowrLibCallsPass();
+
+//===----------------------------------------------------------------------===//
+//
+// CodeGenPrepare - This pass prepares a function for instruction selection.
+//
+FunctionPass *createCodeGenPreparePass(const TargetLowering *TLI = 0);
+
+  
+//===----------------------------------------------------------------------===//
+//
+// InstructionNamer - Give any unnamed non-void instructions "tmp" names.
+//
+FunctionPass *createInstructionNamerPass();
+extern const PassInfo *const InstructionNamerID;
+  
+} // End llvm namespace
+
+#endif
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