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

6 files changed, 536 insertions, 0 deletions

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