LLVM  mainline
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 (Value *IncValue : PN->incoming_values())
00140         if (IncValue == 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 introduces at least one new basic block
00458 /// into the function and moves some of the predecessors of BB to be
00459 /// predecessors of the new block. The new predecessors are indicated by the
00460 /// Preds array. The new block is given a suffix of 'Suffix'. Returns new basic
00461 /// block to which predecessors from Preds are now pointing.
00462 ///
00463 /// If BB is a landingpad block then additional basicblock might be introduced.
00464 /// It will have suffix of 'Suffix'+".split_lp".
00465 /// See SplitLandingPadPredecessors for more details on this case.
00466 ///
00467 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
00468 /// LoopInfo, and LCCSA but no other analyses. In particular, it does not
00469 /// preserve LoopSimplify (because it's complicated to handle the case where one
00470 /// of the edges being split is an exit of a loop with other exits).
00471 ///
00472 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
00473                                          ArrayRef<BasicBlock *> Preds,
00474                                          const char *Suffix, AliasAnalysis *AA,
00475                                          DominatorTree *DT, LoopInfo *LI,
00476                                          bool PreserveLCSSA) {
00477   // For the landingpads we need to act a bit differently.
00478   // Delegate this work to the SplitLandingPadPredecessors.
00479   if (BB->isLandingPad()) {
00480     SmallVector<BasicBlock*, 2> NewBBs;
00481     std::string NewName = std::string(Suffix) + ".split-lp";
00482 
00483     SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(),
00484                                 NewBBs, AA, DT, LI, PreserveLCSSA);
00485     return NewBBs[0];
00486   }
00487 
00488   // Create new basic block, insert right before the original block.
00489   BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), BB->getName()+Suffix,
00490                                          BB->getParent(), BB);
00491 
00492   // The new block unconditionally branches to the old block.
00493   BranchInst *BI = BranchInst::Create(BB, NewBB);
00494 
00495   // Move the edges from Preds to point to NewBB instead of BB.
00496   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
00497     // This is slightly more strict than necessary; the minimum requirement
00498     // is that there be no more than one indirectbr branching to BB. And
00499     // all BlockAddress uses would need to be updated.
00500     assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
00501            "Cannot split an edge from an IndirectBrInst");
00502     Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
00503   }
00504 
00505   // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
00506   // node becomes an incoming value for BB's phi node.  However, if the Preds
00507   // list is empty, we need to insert dummy entries into the PHI nodes in BB to
00508   // account for the newly created predecessor.
00509   if (Preds.size() == 0) {
00510     // Insert dummy values as the incoming value.
00511     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
00512       cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
00513     return NewBB;
00514   }
00515 
00516   // Update DominatorTree, LoopInfo, and LCCSA analysis information.
00517   bool HasLoopExit = false;
00518   UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, PreserveLCSSA,
00519                             HasLoopExit);
00520 
00521   // Update the PHI nodes in BB with the values coming from NewBB.
00522   UpdatePHINodes(BB, NewBB, Preds, BI, AA, HasLoopExit);
00523   return NewBB;
00524 }
00525 
00526 /// SplitLandingPadPredecessors - This method transforms the landing pad,
00527 /// OrigBB, by introducing two new basic blocks into the function. One of those
00528 /// new basic blocks gets the predecessors listed in Preds. The other basic
00529 /// block gets the remaining predecessors of OrigBB. The landingpad instruction
00530 /// OrigBB is clone into both of the new basic blocks. The new blocks are given
00531 /// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector.
00532 ///
00533 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
00534 /// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. In particular,
00535 /// it does not preserve LoopSimplify (because it's complicated to handle the
00536 /// case where one of the edges being split is an exit of a loop with other
00537 /// exits).
00538 ///
00539 void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,
00540                                        ArrayRef<BasicBlock *> Preds,
00541                                        const char *Suffix1, const char *Suffix2,
00542                                        SmallVectorImpl<BasicBlock *> &NewBBs,
00543                                        AliasAnalysis *AA, DominatorTree *DT,
00544                                        LoopInfo *LI, bool PreserveLCSSA) {
00545   assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
00546 
00547   // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
00548   // it right before the original block.
00549   BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
00550                                           OrigBB->getName() + Suffix1,
00551                                           OrigBB->getParent(), OrigBB);
00552   NewBBs.push_back(NewBB1);
00553 
00554   // The new block unconditionally branches to the old block.
00555   BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
00556 
00557   // Move the edges from Preds to point to NewBB1 instead of OrigBB.
00558   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
00559     // This is slightly more strict than necessary; the minimum requirement
00560     // is that there be no more than one indirectbr branching to BB. And
00561     // all BlockAddress uses would need to be updated.
00562     assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
00563            "Cannot split an edge from an IndirectBrInst");
00564     Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
00565   }
00566 
00567   bool HasLoopExit = false;
00568   UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, PreserveLCSSA,
00569                             HasLoopExit);
00570 
00571   // Update the PHI nodes in OrigBB with the values coming from NewBB1.
00572   UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, AA, HasLoopExit);
00573 
00574   // Move the remaining edges from OrigBB to point to NewBB2.
00575   SmallVector<BasicBlock*, 8> NewBB2Preds;
00576   for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
00577        i != e; ) {
00578     BasicBlock *Pred = *i++;
00579     if (Pred == NewBB1) continue;
00580     assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
00581            "Cannot split an edge from an IndirectBrInst");
00582     NewBB2Preds.push_back(Pred);
00583     e = pred_end(OrigBB);
00584   }
00585 
00586   BasicBlock *NewBB2 = nullptr;
00587   if (!NewBB2Preds.empty()) {
00588     // Create another basic block for the rest of OrigBB's predecessors.
00589     NewBB2 = BasicBlock::Create(OrigBB->getContext(),
00590                                 OrigBB->getName() + Suffix2,
00591                                 OrigBB->getParent(), OrigBB);
00592     NewBBs.push_back(NewBB2);
00593 
00594     // The new block unconditionally branches to the old block.
00595     BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
00596 
00597     // Move the remaining edges from OrigBB to point to NewBB2.
00598     for (SmallVectorImpl<BasicBlock*>::iterator
00599            i = NewBB2Preds.begin(), e = NewBB2Preds.end(); i != e; ++i)
00600       (*i)->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
00601 
00602     // Update DominatorTree, LoopInfo, and LCCSA analysis information.
00603     HasLoopExit = false;
00604     UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI,
00605                               PreserveLCSSA, HasLoopExit);
00606 
00607     // Update the PHI nodes in OrigBB with the values coming from NewBB2.
00608     UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, AA, HasLoopExit);
00609   }
00610 
00611   LandingPadInst *LPad = OrigBB->getLandingPadInst();
00612   Instruction *Clone1 = LPad->clone();
00613   Clone1->setName(Twine("lpad") + Suffix1);
00614   NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
00615 
00616   if (NewBB2) {
00617     Instruction *Clone2 = LPad->clone();
00618     Clone2->setName(Twine("lpad") + Suffix2);
00619     NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
00620 
00621     // Create a PHI node for the two cloned landingpad instructions.
00622     PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
00623     PN->addIncoming(Clone1, NewBB1);
00624     PN->addIncoming(Clone2, NewBB2);
00625     LPad->replaceAllUsesWith(PN);
00626     LPad->eraseFromParent();
00627   } else {
00628     // There is no second clone. Just replace the landing pad with the first
00629     // clone.
00630     LPad->replaceAllUsesWith(Clone1);
00631     LPad->eraseFromParent();
00632   }
00633 }
00634 
00635 /// FoldReturnIntoUncondBranch - This method duplicates the specified return
00636 /// instruction into a predecessor which ends in an unconditional branch. If
00637 /// the return instruction returns a value defined by a PHI, propagate the
00638 /// right value into the return. It returns the new return instruction in the
00639 /// predecessor.
00640 ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
00641                                              BasicBlock *Pred) {
00642   Instruction *UncondBranch = Pred->getTerminator();
00643   // Clone the return and add it to the end of the predecessor.
00644   Instruction *NewRet = RI->clone();
00645   Pred->getInstList().push_back(NewRet);
00646 
00647   // If the return instruction returns a value, and if the value was a
00648   // PHI node in "BB", propagate the right value into the return.
00649   for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
00650        i != e; ++i) {
00651     Value *V = *i;
00652     Instruction *NewBC = nullptr;
00653     if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
00654       // Return value might be bitcasted. Clone and insert it before the
00655       // return instruction.
00656       V = BCI->getOperand(0);
00657       NewBC = BCI->clone();
00658       Pred->getInstList().insert(NewRet, NewBC);
00659       *i = NewBC;
00660     }
00661     if (PHINode *PN = dyn_cast<PHINode>(V)) {
00662       if (PN->getParent() == BB) {
00663         if (NewBC)
00664           NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
00665         else
00666           *i = PN->getIncomingValueForBlock(Pred);
00667       }
00668     }
00669   }
00670 
00671   // Update any PHI nodes in the returning block to realize that we no
00672   // longer branch to them.
00673   BB->removePredecessor(Pred);
00674   UncondBranch->eraseFromParent();
00675   return cast<ReturnInst>(NewRet);
00676 }
00677 
00678 /// SplitBlockAndInsertIfThen - Split the containing block at the
00679 /// specified instruction - everything before and including SplitBefore stays
00680 /// in the old basic block, and everything after SplitBefore is moved to a
00681 /// new block. The two blocks are connected by a conditional branch
00682 /// (with value of Cmp being the condition).
00683 /// Before:
00684 ///   Head
00685 ///   SplitBefore
00686 ///   Tail
00687 /// After:
00688 ///   Head
00689 ///   if (Cond)
00690 ///     ThenBlock
00691 ///   SplitBefore
00692 ///   Tail
00693 ///
00694 /// If Unreachable is true, then ThenBlock ends with
00695 /// UnreachableInst, otherwise it branches to Tail.
00696 /// Returns the NewBasicBlock's terminator.
00697 
00698 TerminatorInst *llvm::SplitBlockAndInsertIfThen(Value *Cond,
00699                                                 Instruction *SplitBefore,
00700                                                 bool Unreachable,
00701                                                 MDNode *BranchWeights,
00702                                                 DominatorTree *DT) {
00703   BasicBlock *Head = SplitBefore->getParent();
00704   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore);
00705   TerminatorInst *HeadOldTerm = Head->getTerminator();
00706   LLVMContext &C = Head->getContext();
00707   BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00708   TerminatorInst *CheckTerm;
00709   if (Unreachable)
00710     CheckTerm = new UnreachableInst(C, ThenBlock);
00711   else
00712     CheckTerm = BranchInst::Create(Tail, ThenBlock);
00713   CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
00714   BranchInst *HeadNewTerm =
00715     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
00716   HeadNewTerm->setDebugLoc(SplitBefore->getDebugLoc());
00717   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
00718   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
00719 
00720   if (DT) {
00721     if (DomTreeNode *OldNode = DT->getNode(Head)) {
00722       std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
00723 
00724       DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
00725       for (auto Child : Children)
00726         DT->changeImmediateDominator(Child, NewNode);
00727 
00728       // Head dominates ThenBlock.
00729       DT->addNewBlock(ThenBlock, Head);
00730     }
00731   }
00732 
00733   return CheckTerm;
00734 }
00735 
00736 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
00737 /// but also creates the ElseBlock.
00738 /// Before:
00739 ///   Head
00740 ///   SplitBefore
00741 ///   Tail
00742 /// After:
00743 ///   Head
00744 ///   if (Cond)
00745 ///     ThenBlock
00746 ///   else
00747 ///     ElseBlock
00748 ///   SplitBefore
00749 ///   Tail
00750 void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
00751                                          TerminatorInst **ThenTerm,
00752                                          TerminatorInst **ElseTerm,
00753                                          MDNode *BranchWeights) {
00754   BasicBlock *Head = SplitBefore->getParent();
00755   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore);
00756   TerminatorInst *HeadOldTerm = Head->getTerminator();
00757   LLVMContext &C = Head->getContext();
00758   BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00759   BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00760   *ThenTerm = BranchInst::Create(Tail, ThenBlock);
00761   (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
00762   *ElseTerm = BranchInst::Create(Tail, ElseBlock);
00763   (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
00764   BranchInst *HeadNewTerm =
00765     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
00766   HeadNewTerm->setDebugLoc(SplitBefore->getDebugLoc());
00767   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
00768   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
00769 }
00770 
00771 
00772 /// GetIfCondition - Given a basic block (BB) with two predecessors,
00773 /// check to see if the merge at this block is due
00774 /// to an "if condition".  If so, return the boolean condition that determines
00775 /// which entry into BB will be taken.  Also, return by references the block
00776 /// that will be entered from if the condition is true, and the block that will
00777 /// be entered if the condition is false.
00778 ///
00779 /// This does no checking to see if the true/false blocks have large or unsavory
00780 /// instructions in them.
00781 Value *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
00782                              BasicBlock *&IfFalse) {
00783   PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
00784   BasicBlock *Pred1 = nullptr;
00785   BasicBlock *Pred2 = nullptr;
00786 
00787   if (SomePHI) {
00788     if (SomePHI->getNumIncomingValues() != 2)
00789       return nullptr;
00790     Pred1 = SomePHI->getIncomingBlock(0);
00791     Pred2 = SomePHI->getIncomingBlock(1);
00792   } else {
00793     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
00794     if (PI == PE) // No predecessor
00795       return nullptr;
00796     Pred1 = *PI++;
00797     if (PI == PE) // Only one predecessor
00798       return nullptr;
00799     Pred2 = *PI++;
00800     if (PI != PE) // More than two predecessors
00801       return nullptr;
00802   }
00803 
00804   // We can only handle branches.  Other control flow will be lowered to
00805   // branches if possible anyway.
00806   BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
00807   BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
00808   if (!Pred1Br || !Pred2Br)
00809     return nullptr;
00810 
00811   // Eliminate code duplication by ensuring that Pred1Br is conditional if
00812   // either are.
00813   if (Pred2Br->isConditional()) {
00814     // If both branches are conditional, we don't have an "if statement".  In
00815     // reality, we could transform this case, but since the condition will be
00816     // required anyway, we stand no chance of eliminating it, so the xform is
00817     // probably not profitable.
00818     if (Pred1Br->isConditional())
00819       return nullptr;
00820 
00821     std::swap(Pred1, Pred2);
00822     std::swap(Pred1Br, Pred2Br);
00823   }
00824 
00825   if (Pred1Br->isConditional()) {
00826     // The only thing we have to watch out for here is to make sure that Pred2
00827     // doesn't have incoming edges from other blocks.  If it does, the condition
00828     // doesn't dominate BB.
00829     if (!Pred2->getSinglePredecessor())
00830       return nullptr;
00831 
00832     // If we found a conditional branch predecessor, make sure that it branches
00833     // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
00834     if (Pred1Br->getSuccessor(0) == BB &&
00835         Pred1Br->getSuccessor(1) == Pred2) {
00836       IfTrue = Pred1;
00837       IfFalse = Pred2;
00838     } else if (Pred1Br->getSuccessor(0) == Pred2 &&
00839                Pred1Br->getSuccessor(1) == BB) {
00840       IfTrue = Pred2;
00841       IfFalse = Pred1;
00842     } else {
00843       // We know that one arm of the conditional goes to BB, so the other must
00844       // go somewhere unrelated, and this must not be an "if statement".
00845       return nullptr;
00846     }
00847 
00848     return Pred1Br->getCondition();
00849   }
00850 
00851   // Ok, if we got here, both predecessors end with an unconditional branch to
00852   // BB.  Don't panic!  If both blocks only have a single (identical)
00853   // predecessor, and THAT is a conditional branch, then we're all ok!
00854   BasicBlock *CommonPred = Pred1->getSinglePredecessor();
00855   if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
00856     return nullptr;
00857 
00858   // Otherwise, if this is a conditional branch, then we can use it!
00859   BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
00860   if (!BI) return nullptr;
00861 
00862   assert(BI->isConditional() && "Two successors but not conditional?");
00863   if (BI->getSuccessor(0) == Pred1) {
00864     IfTrue = Pred1;
00865     IfFalse = Pred2;
00866   } else {
00867     IfTrue = Pred2;
00868     IfFalse = Pred1;
00869   }
00870   return BI->getCondition();
00871 }