It's not necessary to do rounding for alloca operations when the requested

alignment is equal to the stack alignment.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@40004 91177308-0d34-0410-b5e6-96231b3b80d8

11 files changed, 1184 insertions, 0 deletions

diff --git a/include/llvm/Transforms/IPO.h b/include/llvm/Transforms/IPO.h
new file mode 100644
index 0000000..6ab6d7b
--- /dev/null
+++ b/include/llvm/Transforms/IPO.h
@@ -0,0 +1,173 @@
+//===- llvm/Transforms/IPO.h - Interprocedural Transformations --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and 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;
+
+//===----------------------------------------------------------------------===//
+//
+// 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);
+
+//===----------------------------------------------------------------------===//
+/// 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();
+
+
+//===----------------------------------------------------------------------===//
+/// createFunctionExtractionPass - If deleteFn is true, this pass deletes as
+/// the specified function. Otherwise, it deletes as much of the module as
+/// possible, except for the function specified.
+///
+ModulePass *createFunctionExtractionPass(Function *F, 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();
+
+//===----------------------------------------------------------------------===//
+/// 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, looking for a main function.  If a list of symbols is
+/// specified with the -internalize-public-api-* command line options, those
+/// symbols are internalized.  Otherwise if InternalizeEverything is set and
+/// the main function is found, all other globals are marked as internal.
+///
+ModulePass *createInternalizePass(bool InternalizeEverything);
+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.
+///
+Pass *createArgumentPromotionPass();
+
+//===----------------------------------------------------------------------===//
+/// 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(std::vector<BasicBlock*> &BTNE);
+
+/// createOptimizeWellKnownCallsPass - This pass optimizes specific calls to
+/// specific well-known (library) functions.
+ModulePass *createSimplifyLibCallsPass();
+
+
+/// 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();
+
+} // 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..01f1aff
--- /dev/null
+++ b/include/llvm/Transforms/IPO/InlinerPass.h
@@ -0,0 +1,64 @@
+//===- InlinerPass.h - Code common to all inliners --------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and 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"
+
+namespace llvm {
+  class CallSite;
+
+/// Inliner - This class contains all of the helper code which is used to
+/// perform the inlining operations that does not depend on the policy.
+///
+struct Inliner : public CallGraphSCCPass {
+  Inliner(const void *ID);
+
+  /// 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);
+
+
+  /// 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 int getInlineCost(CallSite CS) = 0;
+
+private:
+  // InlineThreshold - Cache the value here for easy access.
+  unsigned InlineThreshold;
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/Instrumentation.h b/include/llvm/Transforms/Instrumentation.h
new file mode 100644
index 0000000..82e4676
--- /dev/null
+++ b/include/llvm/Transforms/Instrumentation.h
@@ -0,0 +1,37 @@
+//===- Transforms/Instrumentation.h - Instrumentation passes ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This files 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..b5cb302
--- /dev/null
+++ b/include/llvm/Transforms/RSProfiling.h
@@ -0,0 +1,33 @@
+//===- RSProfiling.cpp - Various profiling using random sampling ----------===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and 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.
+//
+//===----------------------------------------------------------------------===//
+
+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((intptr_t)&ID) {}
+
+    /// isProfiling - This method returns true if the value passed it was 
+    /// inserted by the profiler.
+    virtual bool isProfiling(Value* v) = 0;
+  };
+}
diff --git a/include/llvm/Transforms/Scalar.h b/include/llvm/Transforms/Scalar.h
new file mode 100644
index 0000000..4fea3f7
--- /dev/null
+++ b/include/llvm/Transforms/Scalar.h
@@ -0,0 +1,341 @@
+//===-- Scalar.h - Scalar Transformations -----------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and 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
+
+#include <cstdlib>
+
+namespace llvm {
+
+class FunctionPass;
+class LoopPass;
+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);
+
+//===----------------------------------------------------------------------===//
+//
+// GCSE - This pass is designed to be a very quick global transformation that
+// eliminates global common subexpressions from a function.  It does this by
+// examining the SSA value graph of the function, instead of doing slow
+// bit-vector computations.
+//
+FunctionPass *createGCSEPass();
+
+//===----------------------------------------------------------------------===//
+//
+// InductionVariableSimplify - Transform induction variables in a program to all
+// use a single canonical induction variable per loop.
+//
+LoopPass *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.
+//
+LoopPass *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.
+//
+LoopPass *createLoopStrengthReducePass(const TargetLowering *TLI = 0);
+
+//===----------------------------------------------------------------------===//
+//
+// LoopUnswitch - This pass is a simple loop unswitching pass.
+//
+LoopPass *createLoopUnswitchPass(bool OptimizeForSize = false);
+
+//===----------------------------------------------------------------------===//
+//
+// LoopUnroll - This pass is a simple loop unrolling pass.
+//
+LoopPass *createLoopUnrollPass();
+
+//===----------------------------------------------------------------------===//
+//
+// LoopRotate - This pass is a simple loop rotating pass.
+//
+LoopPass *createLoopRotatePass();
+
+
+//===----------------------------------------------------------------------===//
+//
+// 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 *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 *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();
+
+//===----------------------------------------------------------------------===//
+//
+// CorrelatedExpressionElimination - This pass eliminates correlated
+// conditions, such as these:
+//  if (X == 0)
+//    if (X > 2) ;   // Known false
+//    else
+//      Y = X * Z;   // = 0
+//
+FunctionPass *createCorrelatedExpressionEliminationPass();
+
+//===----------------------------------------------------------------------===//
+//
+// 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();
+
+//===----------------------------------------------------------------------===//
+//
+// 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 *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 *LoopSimplifyID;
+
+//===----------------------------------------------------------------------===//
+//
+// LowerSelect - This pass converts SelectInst instructions into conditional
+// branch and PHI instructions. If the OnlyFP flag is set to true, then only
+// floating point select instructions are lowered.
+//
+FunctionPass *createLowerSelectPass(bool OnlyFP = false);
+extern const PassInfo *LowerSelectID;
+
+//===----------------------------------------------------------------------===//
+//
+// LowerAllocations - Turn malloc and free instructions into %malloc and %free
+// calls.
+//
+//   AU.addRequiredID(LowerAllocationsID);
+//
+Pass *createLowerAllocationsPass(bool LowerMallocArgToInteger = false);
+extern const PassInfo *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 *LowerSwitchID;
+
+//===----------------------------------------------------------------------===//
+//
+// LowerPacked - This pass converts VectorType operations into low-level scalar
+// operations.
+//
+FunctionPass *createLowerPackedPass();
+
+//===----------------------------------------------------------------------===//
+//
+// 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 = NULL);
+extern const PassInfo *LowerInvokePassID;
+
+//===----------------------------------------------------------------------===//
+//
+// LowerGCPass - This function returns an instance of the "lowergc" pass, which
+// lowers garbage collection intrinsics to normal LLVM code.
+//
+FunctionPass *createLowerGCPass();
+
+//===----------------------------------------------------------------------===//
+//
+// 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.
+//
+LoopPass *createLCSSAPass();
+extern const PassInfo *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();
+
+//===----------------------------------------------------------------------===//
+//
+// FastDeadStoreElimination - This pass deletes stores that are post-dominated by
+// must-aliased stores and are not loaded used between the stores.
+//
+FunctionPass *createFastDeadStoreEliminationPass();
+
+//===----------------------------------------------------------------------===//
+//
+// CodeGenPrepare - This pass prepares a function for instruction selection.
+//
+FunctionPass *createCodeGenPreparePass(const TargetLowering *TLI = 0);
+
+} // 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..47bbcbe
--- /dev/null
+++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h
@@ -0,0 +1,123 @@
+//===-- Transform/Utils/BasicBlockUtils.h - BasicBlock Utils ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and 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;
+
+// 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);
+
+
+// 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 (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);
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/Transforms/Utils/Cloning.h b/include/llvm/Transforms/Utils/Cloning.h
new file mode 100644
index 0000000..9f1aad7
--- /dev/null
+++ b/include/llvm/Transforms/Utils/Cloning.h
@@ -0,0 +1,181 @@
+//===- Cloning.h - Clone various parts of LLVM programs ---------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and 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 BasicBlock;
+class Value;
+class CallInst;
+class InvokeInst;
+class ReturnInst;
+class CallSite;
+class Trace;
+class CallGraph;
+class TargetData;
+
+/// 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);
+
+
+/// 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..cf8abdf
--- /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 was developed by the LLVM research group and 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/Dominators.h>
+#include <vector>
+
+namespace llvm {
+  class BasicBlock;
+  class Function;
+  class Loop;
+
+  /// 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/Local.h b/include/llvm/Transforms/Utils/Local.h
new file mode 100644
index 0000000..c2b95db
--- /dev/null
+++ b/include/llvm/Transforms/Utils/Local.h
@@ -0,0 +1,90 @@
+//===-- Local.h - Functions to perform local transformations ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and 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
+
+#include "llvm/Function.h"
+
+namespace llvm {
+
+class Pass;
+class PHINode;
+class AllocaInst;
+class ConstantExpr;
+class TargetData;
+
+//===----------------------------------------------------------------------===//
+//  Local constant propagation...
+//
+
+/// doConstantPropagation - Constant prop a specific instruction.  Returns true
+/// and potentially moves the iterator if constant propagation was performed.
+///
+bool doConstantPropagation(BasicBlock::iterator &I, const TargetData *TD = 0);
+
+/// 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);
+
+
+/// dceInstruction - Inspect the instruction at *BBI and figure out if it
+/// isTriviallyDead.  If so, remove the instruction and update the iterator to
+/// point to the instruction that immediately succeeded the original
+/// instruction.
+///
+bool dceInstruction(BasicBlock::iterator &BBI);
+
+//===----------------------------------------------------------------------===//
+//  Control Flow Graph Restructuring...
+//
+
+/// 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);
+
+/// 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);
+
+} // 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..4e8bfeb
--- /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 was developed by the LLVM research group and 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..1898c30
--- /dev/null
+++ b/include/llvm/Transforms/Utils/UnifyFunctionExitNodes.h
@@ -0,0 +1,55 @@
+//===-- UnifyFunctionExitNodes.h - Ensure fn's have one return --*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and 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((intptr_t)&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);
+  
+  // Force linking the impl of this class into anything that uses this header.
+  static int stub;
+};
+
+Pass *createUnifyFunctionExitNodesPass();
+
+static IncludeFile
+UNIFY_FUNCTION_EXIT_NODES_INCLUDE_FILE(&UnifyFunctionExitNodes::stub);
+
+} // End llvm namespace
+
+#endif