X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FTransforms%2FUtils%2FBasicBlockUtils.h;h=bcafda657c2b34eb9f3b81053fb6a068789194d4;hp=9fe7e47fe8ceb9041d022bb69dd84c9a29752131;hb=ca3c5b87220b162adb684cecebd18ba5b39997a8;hpb=ebccc040e569106b949733d5eb929f75a72dd16c diff --git a/include/llvm/Transforms/Utils/BasicBlockUtils.h b/include/llvm/Transforms/Utils/BasicBlockUtils.h index 9fe7e47fe8c..bcafda657c2 100644 --- a/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -2,8 +2,8 @@ // // 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 is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -12,18 +12,45 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCK_H -#define LLVM_TRANSFORMS_UTILS_BASICBLOCK_H +#ifndef LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H +#define LLVM_TRANSFORMS_UTILS_BASICBLOCKUTILS_H // FIXME: Move to this file: BasicBlock::removePredecessor, BB::splitBasicBlock -#include "llvm/BasicBlock.h" -#include "llvm/Support/CFG.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CFG.h" namespace llvm { +class AliasAnalysis; +class DominatorTree; class Instruction; +class MDNode; class Pass; +class ReturnInst; +class TargetLibraryInfo; +class TerminatorInst; + +/// 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, Pass *P = nullptr); + +/// 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. Return true +/// if any PHIs were deleted. +bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); + +/// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor, +/// if possible. The return value indicates success or failure. +bool MergeBlockIntoPredecessor(BasicBlock *BB, Pass *P = nullptr); // ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) // with a value, then remove and delete the original instruction. @@ -43,53 +70,173 @@ void ReplaceInstWithInst(BasicBlock::InstListType &BIL, // 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); - /// SplitCriticalEdge - If this edge is a critical edge, insert a new node to -/// split the critical edge. This will update DominatorSet, ImmediateDominator, -/// 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. +/// 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 the new block if the edge +/// was split, null otherwise. /// -bool SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, Pass *P = 0); - -inline bool SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, Pass *P = 0) { +/// 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". +/// +/// It is invalid to call this function on a critical edge that starts at an +/// IndirectBrInst. Splitting these edges will almost always create an invalid +/// program because the address of the new block won't be the one that is jumped +/// to. +/// +BasicBlock *SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, + Pass *P = nullptr, + bool MergeIdenticalEdges = false, + bool DontDeleteUselessPHIs = false, + bool SplitLandingPads = false); + +inline BasicBlock *SplitCriticalEdge(BasicBlock *BB, succ_iterator SI, + Pass *P = nullptr) { 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. -inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, Pass *P = 0) { +/// function. If P is specified, it updates the analyses +/// described above. +inline bool SplitCriticalEdge(BasicBlock *Succ, pred_iterator PI, + Pass *P = nullptr) { 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); + MadeChange |= !!SplitCriticalEdge(TI, i, P); return MadeChange; } -inline bool SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, Pass *P = 0) { +/// 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 BasicBlock *SplitCriticalEdge(BasicBlock *Src, BasicBlock *Dst, + Pass *P = nullptr, + bool MergeIdenticalEdges = false, + bool DontDeleteUselessPHIs = false) { TerminatorInst *TI = Src->getTerminator(); - for (unsigned i = 0, e = TI->getNumSuccessors(); ; ++i) + unsigned i = 0; + while (1) { + assert(i != TI->getNumSuccessors() && "Edge doesn't exist!"); if (TI->getSuccessor(i) == Dst) - return SplitCriticalEdge(TI, i, P); + return SplitCriticalEdge(TI, i, P, MergeIdenticalEdges, + DontDeleteUselessPHIs); + ++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, +/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. +/// In particular, it does not preserve LoopSimplify (because it's +/// complicated to handle the case where one of the edges being split +/// is an exit of a loop with other exits). +/// +BasicBlock *SplitBlockPredecessors(BasicBlock *BB, ArrayRef Preds, + const char *Suffix, Pass *P = nullptr); + +/// SplitLandingPadPredecessors - This method transforms the landing pad, +/// OrigBB, by introducing two new basic blocks into the function. One of those +/// new basic blocks gets the predecessors listed in Preds. The other basic +/// block gets the remaining predecessors of OrigBB. The landingpad instruction +/// OrigBB is clone into both of the new basic blocks. The new blocks are given +/// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector. +/// +/// This currently updates the LLVM IR, AliasAnalysis, DominatorTree, +/// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. In particular, +/// it does not preserve LoopSimplify (because it's complicated to handle the +/// case where one of the edges being split is an exit of a loop with other +/// exits). +/// +void SplitLandingPadPredecessors(BasicBlock *OrigBB,ArrayRef Preds, + const char *Suffix, const char *Suffix2, + Pass *P, SmallVectorImpl &NewBBs); + +/// FoldReturnIntoUncondBranch - This method duplicates the specified return +/// instruction into a predecessor which ends in an unconditional branch. If +/// the return instruction returns a value defined by a PHI, propagate the +/// right value into the return. It returns the new return instruction in the +/// predecessor. +ReturnInst *FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, + BasicBlock *Pred); + +/// SplitBlockAndInsertIfThen - Split the containing block at the +/// specified instruction - everything before and including SplitBefore stays +/// in the old basic block, and everything after SplitBefore is moved to a +/// new block. The two blocks are connected by a conditional branch +/// (with value of Cmp being the condition). +/// Before: +/// Head +/// SplitBefore +/// Tail +/// After: +/// Head +/// if (Cond) +/// ThenBlock +/// SplitBefore +/// Tail +/// +/// If Unreachable is true, then ThenBlock ends with +/// UnreachableInst, otherwise it branches to Tail. +/// Returns the NewBasicBlock's terminator. +/// +/// Updates DT if given. +TerminatorInst *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore, + bool Unreachable, + MDNode *BranchWeights = nullptr, + DominatorTree *DT = nullptr); + +/// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, +/// but also creates the ElseBlock. +/// Before: +/// Head +/// SplitBefore +/// Tail +/// After: +/// Head +/// if (Cond) +/// ThenBlock +/// else +/// ElseBlock +/// SplitBefore +/// Tail +void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, + TerminatorInst **ThenTerm, + TerminatorInst **ElseTerm, + MDNode *BranchWeights = nullptr); + +/// +/// GetIfCondition - Check whether BB is the merge point of a if-region. +/// If so, return the boolean condition that determines which entry into +/// BB will be taken. Also, return by references the block that will be +/// entered from if the condition is true, and the block that will be +/// entered if the condition is false. +Value *GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue, + BasicBlock *&IfFalse); } // End llvm namespace #endif