LLVM API Documentation

BasicBlockUtils.cpp
Go to the documentation of this file.
00001 //===-- BasicBlockUtils.cpp - BasicBlock Utilities -------------------------==//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This family of functions perform manipulations on basic blocks, and
00011 // instructions contained within basic blocks.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00016 #include "llvm/Analysis/AliasAnalysis.h"
00017 #include "llvm/Analysis/CFG.h"
00018 #include "llvm/Analysis/LoopInfo.h"
00019 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
00020 #include "llvm/IR/Constant.h"
00021 #include "llvm/IR/DataLayout.h"
00022 #include "llvm/IR/Dominators.h"
00023 #include "llvm/IR/Function.h"
00024 #include "llvm/IR/Instructions.h"
00025 #include "llvm/IR/IntrinsicInst.h"
00026 #include "llvm/IR/Type.h"
00027 #include "llvm/IR/ValueHandle.h"
00028 #include "llvm/Support/ErrorHandling.h"
00029 #include "llvm/Transforms/Scalar.h"
00030 #include "llvm/Transforms/Utils/Local.h"
00031 #include <algorithm>
00032 using namespace llvm;
00033 
00034 /// DeleteDeadBlock - Delete the specified block, which must have no
00035 /// predecessors.
00036 void llvm::DeleteDeadBlock(BasicBlock *BB) {
00037   assert((pred_begin(BB) == pred_end(BB) ||
00038          // Can delete self loop.
00039          BB->getSinglePredecessor() == BB) && "Block is not dead!");
00040   TerminatorInst *BBTerm = BB->getTerminator();
00041 
00042   // Loop through all of our successors and make sure they know that one
00043   // of their predecessors is going away.
00044   for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i)
00045     BBTerm->getSuccessor(i)->removePredecessor(BB);
00046 
00047   // Zap all the instructions in the block.
00048   while (!BB->empty()) {
00049     Instruction &I = BB->back();
00050     // If this instruction is used, replace uses with an arbitrary value.
00051     // Because control flow can't get here, we don't care what we replace the
00052     // value with.  Note that since this block is unreachable, and all values
00053     // contained within it must dominate their uses, that all uses will
00054     // eventually be removed (they are themselves dead).
00055     if (!I.use_empty())
00056       I.replaceAllUsesWith(UndefValue::get(I.getType()));
00057     BB->getInstList().pop_back();
00058   }
00059 
00060   // Zap the block!
00061   BB->eraseFromParent();
00062 }
00063 
00064 /// FoldSingleEntryPHINodes - We know that BB has one predecessor.  If there are
00065 /// any single-entry PHI nodes in it, fold them away.  This handles the case
00066 /// when all entries to the PHI nodes in a block are guaranteed equal, such as
00067 /// when the block has exactly one predecessor.
00068 void llvm::FoldSingleEntryPHINodes(BasicBlock *BB, AliasAnalysis *AA,
00069                                    MemoryDependenceAnalysis *MemDep) {
00070   if (!isa<PHINode>(BB->begin())) return;
00071 
00072   while (PHINode *PN = dyn_cast<PHINode>(BB->begin())) {
00073     if (PN->getIncomingValue(0) != PN)
00074       PN->replaceAllUsesWith(PN->getIncomingValue(0));
00075     else
00076       PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
00077 
00078     if (MemDep)
00079       MemDep->removeInstruction(PN);  // Memdep updates AA itself.
00080     else if (AA && isa<PointerType>(PN->getType()))
00081       AA->deleteValue(PN);
00082 
00083     PN->eraseFromParent();
00084   }
00085 }
00086 
00087 
00088 /// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it
00089 /// is dead. Also recursively delete any operands that become dead as
00090 /// a result. This includes tracing the def-use list from the PHI to see if
00091 /// it is ultimately unused or if it reaches an unused cycle.
00092 bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI) {
00093   // Recursively deleting a PHI may cause multiple PHIs to be deleted
00094   // or RAUW'd undef, so use an array of WeakVH for the PHIs to delete.
00095   SmallVector<WeakVH, 8> PHIs;
00096   for (BasicBlock::iterator I = BB->begin();
00097        PHINode *PN = dyn_cast<PHINode>(I); ++I)
00098     PHIs.push_back(PN);
00099 
00100   bool Changed = false;
00101   for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
00102     if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
00103       Changed |= RecursivelyDeleteDeadPHINode(PN, TLI);
00104 
00105   return Changed;
00106 }
00107 
00108 /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor,
00109 /// if possible.  The return value indicates success or failure.
00110 bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT,
00111                                      LoopInfo *LI, AliasAnalysis *AA,
00112                                      MemoryDependenceAnalysis *MemDep) {
00113   // Don't merge away blocks who have their address taken.
00114   if (BB->hasAddressTaken()) return false;
00115 
00116   // Can't merge if there are multiple predecessors, or no predecessors.
00117   BasicBlock *PredBB = BB->getUniquePredecessor();
00118   if (!PredBB) return false;
00119 
00120   // Don't break self-loops.
00121   if (PredBB == BB) return false;
00122   // Don't break invokes.
00123   if (isa<InvokeInst>(PredBB->getTerminator())) return false;
00124 
00125   succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB));
00126   BasicBlock *OnlySucc = BB;
00127   for (; SI != SE; ++SI)
00128     if (*SI != OnlySucc) {
00129       OnlySucc = nullptr;     // There are multiple distinct successors!
00130       break;
00131     }
00132 
00133   // Can't merge if there are multiple successors.
00134   if (!OnlySucc) return false;
00135 
00136   // Can't merge if there is PHI loop.
00137   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) {
00138     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
00139       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00140         if (PN->getIncomingValue(i) == PN)
00141           return false;
00142     } else
00143       break;
00144   }
00145 
00146   // Begin by getting rid of unneeded PHIs.
00147   if (isa<PHINode>(BB->front()))
00148     FoldSingleEntryPHINodes(BB, AA, MemDep);
00149 
00150   // Delete the unconditional branch from the predecessor...
00151   PredBB->getInstList().pop_back();
00152 
00153   // Make all PHI nodes that referred to BB now refer to Pred as their
00154   // source...
00155   BB->replaceAllUsesWith(PredBB);
00156 
00157   // Move all definitions in the successor to the predecessor...
00158   PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
00159 
00160   // Inherit predecessors name if it exists.
00161   if (!PredBB->hasName())
00162     PredBB->takeName(BB);
00163 
00164   // Finally, erase the old block and update dominator info.
00165   if (DT)
00166     if (DomTreeNode *DTN = DT->getNode(BB)) {
00167       DomTreeNode *PredDTN = DT->getNode(PredBB);
00168       SmallVector<DomTreeNode *, 8> Children(DTN->begin(), DTN->end());
00169       for (SmallVectorImpl<DomTreeNode *>::iterator DI = Children.begin(),
00170                                                     DE = Children.end();
00171            DI != DE; ++DI)
00172         DT->changeImmediateDominator(*DI, PredDTN);
00173 
00174       DT->eraseNode(BB);
00175     }
00176 
00177   if (LI)
00178     LI->removeBlock(BB);
00179 
00180   if (MemDep)
00181     MemDep->invalidateCachedPredecessors();
00182 
00183   BB->eraseFromParent();
00184   return true;
00185 }
00186 
00187 /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
00188 /// with a value, then remove and delete the original instruction.
00189 ///
00190 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
00191                                 BasicBlock::iterator &BI, Value *V) {
00192   Instruction &I = *BI;
00193   // Replaces all of the uses of the instruction with uses of the value
00194   I.replaceAllUsesWith(V);
00195 
00196   // Make sure to propagate a name if there is one already.
00197   if (I.hasName() && !V->hasName())
00198     V->takeName(&I);
00199 
00200   // Delete the unnecessary instruction now...
00201   BI = BIL.erase(BI);
00202 }
00203 
00204 
00205 /// ReplaceInstWithInst - Replace the instruction specified by BI with the
00206 /// instruction specified by I.  The original instruction is deleted and BI is
00207 /// updated to point to the new instruction.
00208 ///
00209 void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
00210                                BasicBlock::iterator &BI, Instruction *I) {
00211   assert(I->getParent() == nullptr &&
00212          "ReplaceInstWithInst: Instruction already inserted into basic block!");
00213 
00214   // Insert the new instruction into the basic block...
00215   BasicBlock::iterator New = BIL.insert(BI, I);
00216 
00217   // Replace all uses of the old instruction, and delete it.
00218   ReplaceInstWithValue(BIL, BI, I);
00219 
00220   // Move BI back to point to the newly inserted instruction
00221   BI = New;
00222 }
00223 
00224 /// ReplaceInstWithInst - Replace the instruction specified by From with the
00225 /// instruction specified by To.
00226 ///
00227 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
00228   BasicBlock::iterator BI(From);
00229   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
00230 }
00231 
00232 /// SplitEdge -  Split the edge connecting specified block. Pass P must
00233 /// not be NULL.
00234 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,
00235                             LoopInfo *LI) {
00236   unsigned SuccNum = GetSuccessorNumber(BB, Succ);
00237 
00238   // If this is a critical edge, let SplitCriticalEdge do it.
00239   TerminatorInst *LatchTerm = BB->getTerminator();
00240   if (SplitCriticalEdge(LatchTerm, SuccNum, CriticalEdgeSplittingOptions(DT, LI)
00241                                                 .setPreserveLCSSA()))
00242     return LatchTerm->getSuccessor(SuccNum);
00243 
00244   // If the edge isn't critical, then BB has a single successor or Succ has a
00245   // single pred.  Split the block.
00246   if (BasicBlock *SP = Succ->getSinglePredecessor()) {
00247     // If the successor only has a single pred, split the top of the successor
00248     // block.
00249     assert(SP == BB && "CFG broken");
00250     SP = nullptr;
00251     return SplitBlock(Succ, Succ->begin(), DT, LI);
00252   }
00253 
00254   // Otherwise, if BB has a single successor, split it at the bottom of the
00255   // block.
00256   assert(BB->getTerminator()->getNumSuccessors() == 1 &&
00257          "Should have a single succ!");
00258   return SplitBlock(BB, BB->getTerminator(), DT, LI);
00259 }
00260 
00261 unsigned
00262 llvm::SplitAllCriticalEdges(Function &F,
00263                             const CriticalEdgeSplittingOptions &Options) {
00264   unsigned NumBroken = 0;
00265   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
00266     TerminatorInst *TI = I->getTerminator();
00267     if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
00268       for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00269         if (SplitCriticalEdge(TI, i, Options))
00270           ++NumBroken;
00271   }
00272   return NumBroken;
00273 }
00274 
00275 /// SplitBlock - Split the specified block at the specified instruction - every
00276 /// thing before SplitPt stays in Old and everything starting with SplitPt moves
00277 /// to a new block.  The two blocks are joined by an unconditional branch and
00278 /// the loop info is updated.
00279 ///
00280 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt,
00281                              DominatorTree *DT, LoopInfo *LI) {
00282   BasicBlock::iterator SplitIt = SplitPt;
00283   while (isa<PHINode>(SplitIt) || isa<LandingPadInst>(SplitIt))
00284     ++SplitIt;
00285   BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
00286 
00287   // The new block lives in whichever loop the old one did. This preserves
00288   // LCSSA as well, because we force the split point to be after any PHI nodes.
00289   if (LI)
00290     if (Loop *L = LI->getLoopFor(Old))
00291       L->addBasicBlockToLoop(New, *LI);
00292 
00293   if (DT)
00294     // Old dominates New. New node dominates all other nodes dominated by Old.
00295     if (DomTreeNode *OldNode = DT->getNode(Old)) {
00296       std::vector<DomTreeNode *> Children;
00297       for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end();
00298            I != E; ++I)
00299         Children.push_back(*I);
00300 
00301       DomTreeNode *NewNode = DT->addNewBlock(New, Old);
00302       for (std::vector<DomTreeNode *>::iterator I = Children.begin(),
00303              E = Children.end(); I != E; ++I)
00304         DT->changeImmediateDominator(*I, NewNode);
00305     }
00306 
00307   return New;
00308 }
00309 
00310 /// UpdateAnalysisInformation - Update DominatorTree, LoopInfo, and LCCSA
00311 /// analysis information.
00312 static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,
00313                                       ArrayRef<BasicBlock *> Preds,
00314                                       DominatorTree *DT, LoopInfo *LI,
00315                                       bool PreserveLCSSA, bool &HasLoopExit) {
00316   // Update dominator tree if available.
00317   if (DT)
00318     DT->splitBlock(NewBB);
00319 
00320   // The rest of the logic is only relevant for updating the loop structures.
00321   if (!LI)
00322     return;
00323 
00324   Loop *L = LI->getLoopFor(OldBB);
00325 
00326   // If we need to preserve loop analyses, collect some information about how
00327   // this split will affect loops.
00328   bool IsLoopEntry = !!L;
00329   bool SplitMakesNewLoopHeader = false;
00330   for (ArrayRef<BasicBlock *>::iterator i = Preds.begin(), e = Preds.end();
00331        i != e; ++i) {
00332     BasicBlock *Pred = *i;
00333 
00334     // If we need to preserve LCSSA, determine if any of the preds is a loop
00335     // exit.
00336     if (PreserveLCSSA)
00337       if (Loop *PL = LI->getLoopFor(Pred))
00338         if (!PL->contains(OldBB))
00339           HasLoopExit = true;
00340 
00341     // If we need to preserve LoopInfo, note whether any of the preds crosses
00342     // an interesting loop boundary.
00343     if (!L)
00344       continue;
00345     if (L->contains(Pred))
00346       IsLoopEntry = false;
00347     else
00348       SplitMakesNewLoopHeader = true;
00349   }
00350 
00351   // Unless we have a loop for OldBB, nothing else to do here.
00352   if (!L)
00353     return;
00354 
00355   if (IsLoopEntry) {
00356     // Add the new block to the nearest enclosing loop (and not an adjacent
00357     // loop). To find this, examine each of the predecessors and determine which
00358     // loops enclose them, and select the most-nested loop which contains the
00359     // loop containing the block being split.
00360     Loop *InnermostPredLoop = nullptr;
00361     for (ArrayRef<BasicBlock*>::iterator
00362            i = Preds.begin(), e = Preds.end(); i != e; ++i) {
00363       BasicBlock *Pred = *i;
00364       if (Loop *PredLoop = LI->getLoopFor(Pred)) {
00365         // Seek a loop which actually contains the block being split (to avoid
00366         // adjacent loops).
00367         while (PredLoop && !PredLoop->contains(OldBB))
00368           PredLoop = PredLoop->getParentLoop();
00369 
00370         // Select the most-nested of these loops which contains the block.
00371         if (PredLoop && PredLoop->contains(OldBB) &&
00372             (!InnermostPredLoop ||
00373              InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
00374           InnermostPredLoop = PredLoop;
00375       }
00376     }
00377 
00378     if (InnermostPredLoop)
00379       InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
00380   } else {
00381     L->addBasicBlockToLoop(NewBB, *LI);
00382     if (SplitMakesNewLoopHeader)
00383       L->moveToHeader(NewBB);
00384   }
00385 }
00386 
00387 /// UpdatePHINodes - Update the PHI nodes in OrigBB to include the values coming
00388 /// from NewBB. This also updates AliasAnalysis, if available.
00389 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
00390                            ArrayRef<BasicBlock *> Preds, BranchInst *BI,
00391                            AliasAnalysis *AA, bool HasLoopExit) {
00392   // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
00393   SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
00394   for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
00395     PHINode *PN = cast<PHINode>(I++);
00396 
00397     // Check to see if all of the values coming in are the same.  If so, we
00398     // don't need to create a new PHI node, unless it's needed for LCSSA.
00399     Value *InVal = nullptr;
00400     if (!HasLoopExit) {
00401       InVal = PN->getIncomingValueForBlock(Preds[0]);
00402       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00403         if (!PredSet.count(PN->getIncomingBlock(i)))
00404           continue;
00405         if (!InVal)
00406           InVal = PN->getIncomingValue(i);
00407         else if (InVal != PN->getIncomingValue(i)) {
00408           InVal = nullptr;
00409           break;
00410         }
00411       }
00412     }
00413 
00414     if (InVal) {
00415       // If all incoming values for the new PHI would be the same, just don't
00416       // make a new PHI.  Instead, just remove the incoming values from the old
00417       // PHI.
00418 
00419       // NOTE! This loop walks backwards for a reason! First off, this minimizes
00420       // the cost of removal if we end up removing a large number of values, and
00421       // second off, this ensures that the indices for the incoming values
00422       // aren't invalidated when we remove one.
00423       for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
00424         if (PredSet.count(PN->getIncomingBlock(i)))
00425           PN->removeIncomingValue(i, false);
00426 
00427       // Add an incoming value to the PHI node in the loop for the preheader
00428       // edge.
00429       PN->addIncoming(InVal, NewBB);
00430       continue;
00431     }
00432 
00433     // If the values coming into the block are not the same, we need a new
00434     // PHI.
00435     // Create the new PHI node, insert it into NewBB at the end of the block
00436     PHINode *NewPHI =
00437         PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
00438     if (AA)
00439       AA->copyValue(PN, NewPHI);
00440 
00441     // NOTE! This loop walks backwards for a reason! First off, this minimizes
00442     // the cost of removal if we end up removing a large number of values, and
00443     // second off, this ensures that the indices for the incoming values aren't
00444     // invalidated when we remove one.
00445     for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
00446       BasicBlock *IncomingBB = PN->getIncomingBlock(i);
00447       if (PredSet.count(IncomingBB)) {
00448         Value *V = PN->removeIncomingValue(i, false);
00449         NewPHI->addIncoming(V, IncomingBB);
00450       }
00451     }
00452 
00453     PN->addIncoming(NewPHI, NewBB);
00454   }
00455 }
00456 
00457 /// SplitBlockPredecessors - This method transforms BB by introducing a new
00458 /// basic block into the function, and moving some of the predecessors of BB to
00459 /// be predecessors of the new block.  The new predecessors are indicated by the
00460 /// Preds array, which has NumPreds elements in it.  The new block is given a
00461 /// suffix of 'Suffix'.
00462 ///
00463 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
00464 /// LoopInfo, and LCCSA but no other analyses. In particular, it does not
00465 /// preserve LoopSimplify (because it's complicated to handle the case where one
00466 /// of the edges being split is an exit of a loop with other exits).
00467 ///
00468 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
00469                                          ArrayRef<BasicBlock *> Preds,
00470                                          const char *Suffix, AliasAnalysis *AA,
00471                                          DominatorTree *DT, LoopInfo *LI,
00472                                          bool PreserveLCSSA) {
00473   // Create new basic block, insert right before the original block.
00474   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix,
00475                                          BB->getParent(), BB);
00476 
00477   // The new block unconditionally branches to the old block.
00478   BranchInst *BI = BranchInst::Create(BB, NewBB);
00479 
00480   // Move the edges from Preds to point to NewBB instead of BB.
00481   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
00482     // This is slightly more strict than necessary; the minimum requirement
00483     // is that there be no more than one indirectbr branching to BB. And
00484     // all BlockAddress uses would need to be updated.
00485     assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
00486            "Cannot split an edge from an IndirectBrInst");
00487     Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
00488   }
00489 
00490   // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
00491   // node becomes an incoming value for BB's phi node.  However, if the Preds
00492   // list is empty, we need to insert dummy entries into the PHI nodes in BB to
00493   // account for the newly created predecessor.
00494   if (Preds.size() == 0) {
00495     // Insert dummy values as the incoming value.
00496     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
00497       cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
00498     return NewBB;
00499   }
00500 
00501   // Update DominatorTree, LoopInfo, and LCCSA analysis information.
00502   bool HasLoopExit = false;
00503   UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, PreserveLCSSA,
00504                             HasLoopExit);
00505 
00506   // Update the PHI nodes in BB with the values coming from NewBB.
00507   UpdatePHINodes(BB, NewBB, Preds, BI, AA, HasLoopExit);
00508   return NewBB;
00509 }
00510 
00511 /// SplitLandingPadPredecessors - This method transforms the landing pad,
00512 /// OrigBB, by introducing two new basic blocks into the function. One of those
00513 /// new basic blocks gets the predecessors listed in Preds. The other basic
00514 /// block gets the remaining predecessors of OrigBB. The landingpad instruction
00515 /// OrigBB is clone into both of the new basic blocks. The new blocks are given
00516 /// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector.
00517 ///
00518 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
00519 /// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. In particular,
00520 /// it does not preserve LoopSimplify (because it's complicated to handle the
00521 /// case where one of the edges being split is an exit of a loop with other
00522 /// exits).
00523 ///
00524 void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,
00525                                        ArrayRef<BasicBlock *> Preds,
00526                                        const char *Suffix1, const char *Suffix2,
00527                                        SmallVectorImpl<BasicBlock *> &NewBBs,
00528                                        AliasAnalysis *AA, DominatorTree *DT,
00529                                        LoopInfo *LI, bool PreserveLCSSA) {
00530   assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
00531 
00532   // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
00533   // it right before the original block.
00534   BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
00535                                           OrigBB->getName() + Suffix1,
00536                                           OrigBB->getParent(), OrigBB);
00537   NewBBs.push_back(NewBB1);
00538 
00539   // The new block unconditionally branches to the old block.
00540   BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
00541 
00542   // Move the edges from Preds to point to NewBB1 instead of OrigBB.
00543   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
00544     // This is slightly more strict than necessary; the minimum requirement
00545     // is that there be no more than one indirectbr branching to BB. And
00546     // all BlockAddress uses would need to be updated.
00547     assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
00548            "Cannot split an edge from an IndirectBrInst");
00549     Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
00550   }
00551 
00552   bool HasLoopExit = false;
00553   UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, PreserveLCSSA,
00554                             HasLoopExit);
00555 
00556   // Update the PHI nodes in OrigBB with the values coming from NewBB1.
00557   UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, AA, HasLoopExit);
00558 
00559   // Move the remaining edges from OrigBB to point to NewBB2.
00560   SmallVector<BasicBlock*, 8> NewBB2Preds;
00561   for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
00562        i != e; ) {
00563     BasicBlock *Pred = *i++;
00564     if (Pred == NewBB1) continue;
00565     assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
00566            "Cannot split an edge from an IndirectBrInst");
00567     NewBB2Preds.push_back(Pred);
00568     e = pred_end(OrigBB);
00569   }
00570 
00571   BasicBlock *NewBB2 = nullptr;
00572   if (!NewBB2Preds.empty()) {
00573     // Create another basic block for the rest of OrigBB's predecessors.
00574     NewBB2 = BasicBlock::Create(OrigBB->getContext(),
00575                                 OrigBB->getName() + Suffix2,
00576                                 OrigBB->getParent(), OrigBB);
00577     NewBBs.push_back(NewBB2);
00578 
00579     // The new block unconditionally branches to the old block.
00580     BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
00581 
00582     // Move the remaining edges from OrigBB to point to NewBB2.
00583     for (SmallVectorImpl<BasicBlock*>::iterator
00584            i = NewBB2Preds.begin(), e = NewBB2Preds.end(); i != e; ++i)
00585       (*i)->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
00586 
00587     // Update DominatorTree, LoopInfo, and LCCSA analysis information.
00588     HasLoopExit = false;
00589     UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI,
00590                               PreserveLCSSA, HasLoopExit);
00591 
00592     // Update the PHI nodes in OrigBB with the values coming from NewBB2.
00593     UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, AA, HasLoopExit);
00594   }
00595 
00596   LandingPadInst *LPad = OrigBB->getLandingPadInst();
00597   Instruction *Clone1 = LPad->clone();
00598   Clone1->setName(Twine("lpad") + Suffix1);
00599   NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
00600 
00601   if (NewBB2) {
00602     Instruction *Clone2 = LPad->clone();
00603     Clone2->setName(Twine("lpad") + Suffix2);
00604     NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
00605 
00606     // Create a PHI node for the two cloned landingpad instructions.
00607     PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
00608     PN->addIncoming(Clone1, NewBB1);
00609     PN->addIncoming(Clone2, NewBB2);
00610     LPad->replaceAllUsesWith(PN);
00611     LPad->eraseFromParent();
00612   } else {
00613     // There is no second clone. Just replace the landing pad with the first
00614     // clone.
00615     LPad->replaceAllUsesWith(Clone1);
00616     LPad->eraseFromParent();
00617   }
00618 }
00619 
00620 /// FoldReturnIntoUncondBranch - This method duplicates the specified return
00621 /// instruction into a predecessor which ends in an unconditional branch. If
00622 /// the return instruction returns a value defined by a PHI, propagate the
00623 /// right value into the return. It returns the new return instruction in the
00624 /// predecessor.
00625 ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
00626                                              BasicBlock *Pred) {
00627   Instruction *UncondBranch = Pred->getTerminator();
00628   // Clone the return and add it to the end of the predecessor.
00629   Instruction *NewRet = RI->clone();
00630   Pred->getInstList().push_back(NewRet);
00631 
00632   // If the return instruction returns a value, and if the value was a
00633   // PHI node in "BB", propagate the right value into the return.
00634   for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
00635        i != e; ++i) {
00636     Value *V = *i;
00637     Instruction *NewBC = nullptr;
00638     if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
00639       // Return value might be bitcasted. Clone and insert it before the
00640       // return instruction.
00641       V = BCI->getOperand(0);
00642       NewBC = BCI->clone();
00643       Pred->getInstList().insert(NewRet, NewBC);
00644       *i = NewBC;
00645     }
00646     if (PHINode *PN = dyn_cast<PHINode>(V)) {
00647       if (PN->getParent() == BB) {
00648         if (NewBC)
00649           NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
00650         else
00651           *i = PN->getIncomingValueForBlock(Pred);
00652       }
00653     }
00654   }
00655 
00656   // Update any PHI nodes in the returning block to realize that we no
00657   // longer branch to them.
00658   BB->removePredecessor(Pred);
00659   UncondBranch->eraseFromParent();
00660   return cast<ReturnInst>(NewRet);
00661 }
00662 
00663 /// SplitBlockAndInsertIfThen - Split the containing block at the
00664 /// specified instruction - everything before and including SplitBefore stays
00665 /// in the old basic block, and everything after SplitBefore is moved to a
00666 /// new block. The two blocks are connected by a conditional branch
00667 /// (with value of Cmp being the condition).
00668 /// Before:
00669 ///   Head
00670 ///   SplitBefore
00671 ///   Tail
00672 /// After:
00673 ///   Head
00674 ///   if (Cond)
00675 ///     ThenBlock
00676 ///   SplitBefore
00677 ///   Tail
00678 ///
00679 /// If Unreachable is true, then ThenBlock ends with
00680 /// UnreachableInst, otherwise it branches to Tail.
00681 /// Returns the NewBasicBlock's terminator.
00682 
00683 TerminatorInst *llvm::SplitBlockAndInsertIfThen(Value *Cond,
00684                                                 Instruction *SplitBefore,
00685                                                 bool Unreachable,
00686                                                 MDNode *BranchWeights,
00687                                                 DominatorTree *DT) {
00688   BasicBlock *Head = SplitBefore->getParent();
00689   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore);
00690   TerminatorInst *HeadOldTerm = Head->getTerminator();
00691   LLVMContext &C = Head->getContext();
00692   BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00693   TerminatorInst *CheckTerm;
00694   if (Unreachable)
00695     CheckTerm = new UnreachableInst(C, ThenBlock);
00696   else
00697     CheckTerm = BranchInst::Create(Tail, ThenBlock);
00698   CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
00699   BranchInst *HeadNewTerm =
00700     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
00701   HeadNewTerm->setDebugLoc(SplitBefore->getDebugLoc());
00702   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
00703   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
00704 
00705   if (DT) {
00706     if (DomTreeNode *OldNode = DT->getNode(Head)) {
00707       std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
00708 
00709       DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
00710       for (auto Child : Children)
00711         DT->changeImmediateDominator(Child, NewNode);
00712 
00713       // Head dominates ThenBlock.
00714       DT->addNewBlock(ThenBlock, Head);
00715     }
00716   }
00717 
00718   return CheckTerm;
00719 }
00720 
00721 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
00722 /// but also creates the ElseBlock.
00723 /// Before:
00724 ///   Head
00725 ///   SplitBefore
00726 ///   Tail
00727 /// After:
00728 ///   Head
00729 ///   if (Cond)
00730 ///     ThenBlock
00731 ///   else
00732 ///     ElseBlock
00733 ///   SplitBefore
00734 ///   Tail
00735 void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
00736                                          TerminatorInst **ThenTerm,
00737                                          TerminatorInst **ElseTerm,
00738                                          MDNode *BranchWeights) {
00739   BasicBlock *Head = SplitBefore->getParent();
00740   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore);
00741   TerminatorInst *HeadOldTerm = Head->getTerminator();
00742   LLVMContext &C = Head->getContext();
00743   BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00744   BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00745   *ThenTerm = BranchInst::Create(Tail, ThenBlock);
00746   (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
00747   *ElseTerm = BranchInst::Create(Tail, ElseBlock);
00748   (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
00749   BranchInst *HeadNewTerm =
00750     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
00751   HeadNewTerm->setDebugLoc(SplitBefore->getDebugLoc());
00752   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
00753   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
00754 }
00755 
00756 
00757 /// GetIfCondition - Given a basic block (BB) with two predecessors,
00758 /// check to see if the merge at this block is due
00759 /// to an "if condition".  If so, return the boolean condition that determines
00760 /// which entry into BB will be taken.  Also, return by references the block
00761 /// that will be entered from if the condition is true, and the block that will
00762 /// be entered if the condition is false.
00763 ///
00764 /// This does no checking to see if the true/false blocks have large or unsavory
00765 /// instructions in them.
00766 Value *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
00767                              BasicBlock *&IfFalse) {
00768   PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
00769   BasicBlock *Pred1 = nullptr;
00770   BasicBlock *Pred2 = nullptr;
00771 
00772   if (SomePHI) {
00773     if (SomePHI->getNumIncomingValues() != 2)
00774       return nullptr;
00775     Pred1 = SomePHI->getIncomingBlock(0);
00776     Pred2 = SomePHI->getIncomingBlock(1);
00777   } else {
00778     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
00779     if (PI == PE) // No predecessor
00780       return nullptr;
00781     Pred1 = *PI++;
00782     if (PI == PE) // Only one predecessor
00783       return nullptr;
00784     Pred2 = *PI++;
00785     if (PI != PE) // More than two predecessors
00786       return nullptr;
00787   }
00788 
00789   // We can only handle branches.  Other control flow will be lowered to
00790   // branches if possible anyway.
00791   BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
00792   BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
00793   if (!Pred1Br || !Pred2Br)
00794     return nullptr;
00795 
00796   // Eliminate code duplication by ensuring that Pred1Br is conditional if
00797   // either are.
00798   if (Pred2Br->isConditional()) {
00799     // If both branches are conditional, we don't have an "if statement".  In
00800     // reality, we could transform this case, but since the condition will be
00801     // required anyway, we stand no chance of eliminating it, so the xform is
00802     // probably not profitable.
00803     if (Pred1Br->isConditional())
00804       return nullptr;
00805 
00806     std::swap(Pred1, Pred2);
00807     std::swap(Pred1Br, Pred2Br);
00808   }
00809 
00810   if (Pred1Br->isConditional()) {
00811     // The only thing we have to watch out for here is to make sure that Pred2
00812     // doesn't have incoming edges from other blocks.  If it does, the condition
00813     // doesn't dominate BB.
00814     if (!Pred2->getSinglePredecessor())
00815       return nullptr;
00816 
00817     // If we found a conditional branch predecessor, make sure that it branches
00818     // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
00819     if (Pred1Br->getSuccessor(0) == BB &&
00820         Pred1Br->getSuccessor(1) == Pred2) {
00821       IfTrue = Pred1;
00822       IfFalse = Pred2;
00823     } else if (Pred1Br->getSuccessor(0) == Pred2 &&
00824                Pred1Br->getSuccessor(1) == BB) {
00825       IfTrue = Pred2;
00826       IfFalse = Pred1;
00827     } else {
00828       // We know that one arm of the conditional goes to BB, so the other must
00829       // go somewhere unrelated, and this must not be an "if statement".
00830       return nullptr;
00831     }
00832 
00833     return Pred1Br->getCondition();
00834   }
00835 
00836   // Ok, if we got here, both predecessors end with an unconditional branch to
00837   // BB.  Don't panic!  If both blocks only have a single (identical)
00838   // predecessor, and THAT is a conditional branch, then we're all ok!
00839   BasicBlock *CommonPred = Pred1->getSinglePredecessor();
00840   if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
00841     return nullptr;
00842 
00843   // Otherwise, if this is a conditional branch, then we can use it!
00844   BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
00845   if (!BI) return nullptr;
00846 
00847   assert(BI->isConditional() && "Two successors but not conditional?");
00848   if (BI->getSuccessor(0) == Pred1) {
00849     IfTrue = Pred1;
00850     IfFalse = Pred2;
00851   } else {
00852     IfTrue = Pred2;
00853     IfFalse = Pred1;
00854   }
00855   return BI->getCondition();
00856 }