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   // Copy debug location to newly added instruction, if it wasn't already set
00215   // by the caller.
00216   if (!I->getDebugLoc())
00217     I->setDebugLoc(BI->getDebugLoc());
00218 
00219   // Insert the new instruction into the basic block...
00220   BasicBlock::iterator New = BIL.insert(BI, I);
00221 
00222   // Replace all uses of the old instruction, and delete it.
00223   ReplaceInstWithValue(BIL, BI, I);
00224 
00225   // Move BI back to point to the newly inserted instruction
00226   BI = New;
00227 }
00228 
00229 /// ReplaceInstWithInst - Replace the instruction specified by From with the
00230 /// instruction specified by To.
00231 ///
00232 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
00233   BasicBlock::iterator BI(From);
00234   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
00235 }
00236 
00237 /// SplitEdge -  Split the edge connecting specified block. Pass P must
00238 /// not be NULL.
00239 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,
00240                             LoopInfo *LI) {
00241   unsigned SuccNum = GetSuccessorNumber(BB, Succ);
00242 
00243   // If this is a critical edge, let SplitCriticalEdge do it.
00244   TerminatorInst *LatchTerm = BB->getTerminator();
00245   if (SplitCriticalEdge(LatchTerm, SuccNum, CriticalEdgeSplittingOptions(DT, LI)
00246                                                 .setPreserveLCSSA()))
00247     return LatchTerm->getSuccessor(SuccNum);
00248 
00249   // If the edge isn't critical, then BB has a single successor or Succ has a
00250   // single pred.  Split the block.
00251   if (BasicBlock *SP = Succ->getSinglePredecessor()) {
00252     // If the successor only has a single pred, split the top of the successor
00253     // block.
00254     assert(SP == BB && "CFG broken");
00255     SP = nullptr;
00256     return SplitBlock(Succ, Succ->begin(), DT, LI);
00257   }
00258 
00259   // Otherwise, if BB has a single successor, split it at the bottom of the
00260   // block.
00261   assert(BB->getTerminator()->getNumSuccessors() == 1 &&
00262          "Should have a single succ!");
00263   return SplitBlock(BB, BB->getTerminator(), DT, LI);
00264 }
00265 
00266 unsigned
00267 llvm::SplitAllCriticalEdges(Function &F,
00268                             const CriticalEdgeSplittingOptions &Options) {
00269   unsigned NumBroken = 0;
00270   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
00271     TerminatorInst *TI = I->getTerminator();
00272     if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
00273       for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00274         if (SplitCriticalEdge(TI, i, Options))
00275           ++NumBroken;
00276   }
00277   return NumBroken;
00278 }
00279 
00280 /// SplitBlock - Split the specified block at the specified instruction - every
00281 /// thing before SplitPt stays in Old and everything starting with SplitPt moves
00282 /// to a new block.  The two blocks are joined by an unconditional branch and
00283 /// the loop info is updated.
00284 ///
00285 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt,
00286                              DominatorTree *DT, LoopInfo *LI) {
00287   BasicBlock::iterator SplitIt = SplitPt;
00288   while (isa<PHINode>(SplitIt) || isa<LandingPadInst>(SplitIt))
00289     ++SplitIt;
00290   BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
00291 
00292   // The new block lives in whichever loop the old one did. This preserves
00293   // LCSSA as well, because we force the split point to be after any PHI nodes.
00294   if (LI)
00295     if (Loop *L = LI->getLoopFor(Old))
00296       L->addBasicBlockToLoop(New, *LI);
00297 
00298   if (DT)
00299     // Old dominates New. New node dominates all other nodes dominated by Old.
00300     if (DomTreeNode *OldNode = DT->getNode(Old)) {
00301       std::vector<DomTreeNode *> Children;
00302       for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end();
00303            I != E; ++I)
00304         Children.push_back(*I);
00305 
00306       DomTreeNode *NewNode = DT->addNewBlock(New, Old);
00307       for (std::vector<DomTreeNode *>::iterator I = Children.begin(),
00308              E = Children.end(); I != E; ++I)
00309         DT->changeImmediateDominator(*I, NewNode);
00310     }
00311 
00312   return New;
00313 }
00314 
00315 /// UpdateAnalysisInformation - Update DominatorTree, LoopInfo, and LCCSA
00316 /// analysis information.
00317 static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,
00318                                       ArrayRef<BasicBlock *> Preds,
00319                                       DominatorTree *DT, LoopInfo *LI,
00320                                       bool PreserveLCSSA, bool &HasLoopExit) {
00321   // Update dominator tree if available.
00322   if (DT)
00323     DT->splitBlock(NewBB);
00324 
00325   // The rest of the logic is only relevant for updating the loop structures.
00326   if (!LI)
00327     return;
00328 
00329   Loop *L = LI->getLoopFor(OldBB);
00330 
00331   // If we need to preserve loop analyses, collect some information about how
00332   // this split will affect loops.
00333   bool IsLoopEntry = !!L;
00334   bool SplitMakesNewLoopHeader = false;
00335   for (ArrayRef<BasicBlock *>::iterator i = Preds.begin(), e = Preds.end();
00336        i != e; ++i) {
00337     BasicBlock *Pred = *i;
00338 
00339     // If we need to preserve LCSSA, determine if any of the preds is a loop
00340     // exit.
00341     if (PreserveLCSSA)
00342       if (Loop *PL = LI->getLoopFor(Pred))
00343         if (!PL->contains(OldBB))
00344           HasLoopExit = true;
00345 
00346     // If we need to preserve LoopInfo, note whether any of the preds crosses
00347     // an interesting loop boundary.
00348     if (!L)
00349       continue;
00350     if (L->contains(Pred))
00351       IsLoopEntry = false;
00352     else
00353       SplitMakesNewLoopHeader = true;
00354   }
00355 
00356   // Unless we have a loop for OldBB, nothing else to do here.
00357   if (!L)
00358     return;
00359 
00360   if (IsLoopEntry) {
00361     // Add the new block to the nearest enclosing loop (and not an adjacent
00362     // loop). To find this, examine each of the predecessors and determine which
00363     // loops enclose them, and select the most-nested loop which contains the
00364     // loop containing the block being split.
00365     Loop *InnermostPredLoop = nullptr;
00366     for (ArrayRef<BasicBlock*>::iterator
00367            i = Preds.begin(), e = Preds.end(); i != e; ++i) {
00368       BasicBlock *Pred = *i;
00369       if (Loop *PredLoop = LI->getLoopFor(Pred)) {
00370         // Seek a loop which actually contains the block being split (to avoid
00371         // adjacent loops).
00372         while (PredLoop && !PredLoop->contains(OldBB))
00373           PredLoop = PredLoop->getParentLoop();
00374 
00375         // Select the most-nested of these loops which contains the block.
00376         if (PredLoop && PredLoop->contains(OldBB) &&
00377             (!InnermostPredLoop ||
00378              InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
00379           InnermostPredLoop = PredLoop;
00380       }
00381     }
00382 
00383     if (InnermostPredLoop)
00384       InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
00385   } else {
00386     L->addBasicBlockToLoop(NewBB, *LI);
00387     if (SplitMakesNewLoopHeader)
00388       L->moveToHeader(NewBB);
00389   }
00390 }
00391 
00392 /// UpdatePHINodes - Update the PHI nodes in OrigBB to include the values coming
00393 /// from NewBB. This also updates AliasAnalysis, if available.
00394 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
00395                            ArrayRef<BasicBlock *> Preds, BranchInst *BI,
00396                            AliasAnalysis *AA, bool HasLoopExit) {
00397   // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
00398   SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
00399   for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
00400     PHINode *PN = cast<PHINode>(I++);
00401 
00402     // Check to see if all of the values coming in are the same.  If so, we
00403     // don't need to create a new PHI node, unless it's needed for LCSSA.
00404     Value *InVal = nullptr;
00405     if (!HasLoopExit) {
00406       InVal = PN->getIncomingValueForBlock(Preds[0]);
00407       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00408         if (!PredSet.count(PN->getIncomingBlock(i)))
00409           continue;
00410         if (!InVal)
00411           InVal = PN->getIncomingValue(i);
00412         else if (InVal != PN->getIncomingValue(i)) {
00413           InVal = nullptr;
00414           break;
00415         }
00416       }
00417     }
00418 
00419     if (InVal) {
00420       // If all incoming values for the new PHI would be the same, just don't
00421       // make a new PHI.  Instead, just remove the incoming values from the old
00422       // PHI.
00423 
00424       // NOTE! This loop walks backwards for a reason! First off, this minimizes
00425       // the cost of removal if we end up removing a large number of values, and
00426       // second off, this ensures that the indices for the incoming values
00427       // aren't invalidated when we remove one.
00428       for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
00429         if (PredSet.count(PN->getIncomingBlock(i)))
00430           PN->removeIncomingValue(i, false);
00431 
00432       // Add an incoming value to the PHI node in the loop for the preheader
00433       // edge.
00434       PN->addIncoming(InVal, NewBB);
00435       continue;
00436     }
00437 
00438     // If the values coming into the block are not the same, we need a new
00439     // PHI.
00440     // Create the new PHI node, insert it into NewBB at the end of the block
00441     PHINode *NewPHI =
00442         PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
00443     if (AA)
00444       AA->copyValue(PN, NewPHI);
00445 
00446     // NOTE! This loop walks backwards for a reason! First off, this minimizes
00447     // the cost of removal if we end up removing a large number of values, and
00448     // second off, this ensures that the indices for the incoming values aren't
00449     // invalidated when we remove one.
00450     for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
00451       BasicBlock *IncomingBB = PN->getIncomingBlock(i);
00452       if (PredSet.count(IncomingBB)) {
00453         Value *V = PN->removeIncomingValue(i, false);
00454         NewPHI->addIncoming(V, IncomingBB);
00455       }
00456     }
00457 
00458     PN->addIncoming(NewPHI, NewBB);
00459   }
00460 }
00461 
00462 /// SplitBlockPredecessors - This method introduces at least one new basic block
00463 /// into the function and moves some of the predecessors of BB to be
00464 /// predecessors of the new block. The new predecessors are indicated by the
00465 /// Preds array. The new block is given a suffix of 'Suffix'. Returns new basic
00466 /// block to which predecessors from Preds are now pointing.
00467 ///
00468 /// If BB is a landingpad block then additional basicblock might be introduced.
00469 /// It will have suffix of 'Suffix'+".split_lp".
00470 /// See SplitLandingPadPredecessors for more details on this case.
00471 ///
00472 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
00473 /// LoopInfo, and LCCSA but no other analyses. In particular, it does not
00474 /// preserve LoopSimplify (because it's complicated to handle the case where one
00475 /// of the edges being split is an exit of a loop with other exits).
00476 ///
00477 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
00478                                          ArrayRef<BasicBlock *> Preds,
00479                                          const char *Suffix, AliasAnalysis *AA,
00480                                          DominatorTree *DT, LoopInfo *LI,
00481                                          bool PreserveLCSSA) {
00482   // For the landingpads we need to act a bit differently.
00483   // Delegate this work to the SplitLandingPadPredecessors.
00484   if (BB->isLandingPad()) {
00485     SmallVector<BasicBlock*, 2> NewBBs;
00486     std::string NewName = std::string(Suffix) + ".split-lp";
00487 
00488     SplitLandingPadPredecessors(BB, Preds, Suffix, NewName.c_str(),
00489                                 NewBBs, AA, DT, LI, PreserveLCSSA);
00490     return NewBBs[0];
00491   }
00492 
00493   // Create new basic block, insert right before the original block.
00494   BasicBlock *NewBB = BasicBlock::Create(
00495       BB->getContext(), BB->getName() + Suffix, BB->getParent(), BB);
00496 
00497   // The new block unconditionally branches to the old block.
00498   BranchInst *BI = BranchInst::Create(BB, NewBB);
00499   BI->setDebugLoc(BB->getFirstNonPHI()->getDebugLoc());
00500 
00501   // Move the edges from Preds to point to NewBB instead of BB.
00502   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
00503     // This is slightly more strict than necessary; the minimum requirement
00504     // is that there be no more than one indirectbr branching to BB. And
00505     // all BlockAddress uses would need to be updated.
00506     assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
00507            "Cannot split an edge from an IndirectBrInst");
00508     Preds[i]->getTerminator()->replaceUsesOfWith(BB, NewBB);
00509   }
00510 
00511   // Insert a new PHI node into NewBB for every PHI node in BB and that new PHI
00512   // node becomes an incoming value for BB's phi node.  However, if the Preds
00513   // list is empty, we need to insert dummy entries into the PHI nodes in BB to
00514   // account for the newly created predecessor.
00515   if (Preds.size() == 0) {
00516     // Insert dummy values as the incoming value.
00517     for (BasicBlock::iterator I = BB->begin(); isa<PHINode>(I); ++I)
00518       cast<PHINode>(I)->addIncoming(UndefValue::get(I->getType()), NewBB);
00519     return NewBB;
00520   }
00521 
00522   // Update DominatorTree, LoopInfo, and LCCSA analysis information.
00523   bool HasLoopExit = false;
00524   UpdateAnalysisInformation(BB, NewBB, Preds, DT, LI, PreserveLCSSA,
00525                             HasLoopExit);
00526 
00527   // Update the PHI nodes in BB with the values coming from NewBB.
00528   UpdatePHINodes(BB, NewBB, Preds, BI, AA, HasLoopExit);
00529   return NewBB;
00530 }
00531 
00532 /// SplitLandingPadPredecessors - This method transforms the landing pad,
00533 /// OrigBB, by introducing two new basic blocks into the function. One of those
00534 /// new basic blocks gets the predecessors listed in Preds. The other basic
00535 /// block gets the remaining predecessors of OrigBB. The landingpad instruction
00536 /// OrigBB is clone into both of the new basic blocks. The new blocks are given
00537 /// the suffixes 'Suffix1' and 'Suffix2', and are returned in the NewBBs vector.
00538 ///
00539 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
00540 /// DominanceFrontier, LoopInfo, and LCCSA but no other analyses. In particular,
00541 /// it does not preserve LoopSimplify (because it's complicated to handle the
00542 /// case where one of the edges being split is an exit of a loop with other
00543 /// exits).
00544 ///
00545 void llvm::SplitLandingPadPredecessors(BasicBlock *OrigBB,
00546                                        ArrayRef<BasicBlock *> Preds,
00547                                        const char *Suffix1, const char *Suffix2,
00548                                        SmallVectorImpl<BasicBlock *> &NewBBs,
00549                                        AliasAnalysis *AA, DominatorTree *DT,
00550                                        LoopInfo *LI, bool PreserveLCSSA) {
00551   assert(OrigBB->isLandingPad() && "Trying to split a non-landing pad!");
00552 
00553   // Create a new basic block for OrigBB's predecessors listed in Preds. Insert
00554   // it right before the original block.
00555   BasicBlock *NewBB1 = BasicBlock::Create(OrigBB->getContext(),
00556                                           OrigBB->getName() + Suffix1,
00557                                           OrigBB->getParent(), OrigBB);
00558   NewBBs.push_back(NewBB1);
00559 
00560   // The new block unconditionally branches to the old block.
00561   BranchInst *BI1 = BranchInst::Create(OrigBB, NewBB1);
00562   BI1->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
00563 
00564   // Move the edges from Preds to point to NewBB1 instead of OrigBB.
00565   for (unsigned i = 0, e = Preds.size(); i != e; ++i) {
00566     // This is slightly more strict than necessary; the minimum requirement
00567     // is that there be no more than one indirectbr branching to BB. And
00568     // all BlockAddress uses would need to be updated.
00569     assert(!isa<IndirectBrInst>(Preds[i]->getTerminator()) &&
00570            "Cannot split an edge from an IndirectBrInst");
00571     Preds[i]->getTerminator()->replaceUsesOfWith(OrigBB, NewBB1);
00572   }
00573 
00574   bool HasLoopExit = false;
00575   UpdateAnalysisInformation(OrigBB, NewBB1, Preds, DT, LI, PreserveLCSSA,
00576                             HasLoopExit);
00577 
00578   // Update the PHI nodes in OrigBB with the values coming from NewBB1.
00579   UpdatePHINodes(OrigBB, NewBB1, Preds, BI1, AA, HasLoopExit);
00580 
00581   // Move the remaining edges from OrigBB to point to NewBB2.
00582   SmallVector<BasicBlock*, 8> NewBB2Preds;
00583   for (pred_iterator i = pred_begin(OrigBB), e = pred_end(OrigBB);
00584        i != e; ) {
00585     BasicBlock *Pred = *i++;
00586     if (Pred == NewBB1) continue;
00587     assert(!isa<IndirectBrInst>(Pred->getTerminator()) &&
00588            "Cannot split an edge from an IndirectBrInst");
00589     NewBB2Preds.push_back(Pred);
00590     e = pred_end(OrigBB);
00591   }
00592 
00593   BasicBlock *NewBB2 = nullptr;
00594   if (!NewBB2Preds.empty()) {
00595     // Create another basic block for the rest of OrigBB's predecessors.
00596     NewBB2 = BasicBlock::Create(OrigBB->getContext(),
00597                                 OrigBB->getName() + Suffix2,
00598                                 OrigBB->getParent(), OrigBB);
00599     NewBBs.push_back(NewBB2);
00600 
00601     // The new block unconditionally branches to the old block.
00602     BranchInst *BI2 = BranchInst::Create(OrigBB, NewBB2);
00603     BI2->setDebugLoc(OrigBB->getFirstNonPHI()->getDebugLoc());
00604 
00605     // Move the remaining edges from OrigBB to point to NewBB2.
00606     for (SmallVectorImpl<BasicBlock*>::iterator
00607            i = NewBB2Preds.begin(), e = NewBB2Preds.end(); i != e; ++i)
00608       (*i)->getTerminator()->replaceUsesOfWith(OrigBB, NewBB2);
00609 
00610     // Update DominatorTree, LoopInfo, and LCCSA analysis information.
00611     HasLoopExit = false;
00612     UpdateAnalysisInformation(OrigBB, NewBB2, NewBB2Preds, DT, LI,
00613                               PreserveLCSSA, HasLoopExit);
00614 
00615     // Update the PHI nodes in OrigBB with the values coming from NewBB2.
00616     UpdatePHINodes(OrigBB, NewBB2, NewBB2Preds, BI2, AA, HasLoopExit);
00617   }
00618 
00619   LandingPadInst *LPad = OrigBB->getLandingPadInst();
00620   Instruction *Clone1 = LPad->clone();
00621   Clone1->setName(Twine("lpad") + Suffix1);
00622   NewBB1->getInstList().insert(NewBB1->getFirstInsertionPt(), Clone1);
00623 
00624   if (NewBB2) {
00625     Instruction *Clone2 = LPad->clone();
00626     Clone2->setName(Twine("lpad") + Suffix2);
00627     NewBB2->getInstList().insert(NewBB2->getFirstInsertionPt(), Clone2);
00628 
00629     // Create a PHI node for the two cloned landingpad instructions.
00630     PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
00631     PN->addIncoming(Clone1, NewBB1);
00632     PN->addIncoming(Clone2, NewBB2);
00633     LPad->replaceAllUsesWith(PN);
00634     LPad->eraseFromParent();
00635   } else {
00636     // There is no second clone. Just replace the landing pad with the first
00637     // clone.
00638     LPad->replaceAllUsesWith(Clone1);
00639     LPad->eraseFromParent();
00640   }
00641 }
00642 
00643 /// FoldReturnIntoUncondBranch - This method duplicates the specified return
00644 /// instruction into a predecessor which ends in an unconditional branch. If
00645 /// the return instruction returns a value defined by a PHI, propagate the
00646 /// right value into the return. It returns the new return instruction in the
00647 /// predecessor.
00648 ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
00649                                              BasicBlock *Pred) {
00650   Instruction *UncondBranch = Pred->getTerminator();
00651   // Clone the return and add it to the end of the predecessor.
00652   Instruction *NewRet = RI->clone();
00653   Pred->getInstList().push_back(NewRet);
00654 
00655   // If the return instruction returns a value, and if the value was a
00656   // PHI node in "BB", propagate the right value into the return.
00657   for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
00658        i != e; ++i) {
00659     Value *V = *i;
00660     Instruction *NewBC = nullptr;
00661     if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
00662       // Return value might be bitcasted. Clone and insert it before the
00663       // return instruction.
00664       V = BCI->getOperand(0);
00665       NewBC = BCI->clone();
00666       Pred->getInstList().insert(NewRet, NewBC);
00667       *i = NewBC;
00668     }
00669     if (PHINode *PN = dyn_cast<PHINode>(V)) {
00670       if (PN->getParent() == BB) {
00671         if (NewBC)
00672           NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
00673         else
00674           *i = PN->getIncomingValueForBlock(Pred);
00675       }
00676     }
00677   }
00678 
00679   // Update any PHI nodes in the returning block to realize that we no
00680   // longer branch to them.
00681   BB->removePredecessor(Pred);
00682   UncondBranch->eraseFromParent();
00683   return cast<ReturnInst>(NewRet);
00684 }
00685 
00686 /// SplitBlockAndInsertIfThen - Split the containing block at the
00687 /// specified instruction - everything before and including SplitBefore stays
00688 /// in the old basic block, and everything after SplitBefore is moved to a
00689 /// new block. The two blocks are connected by a conditional branch
00690 /// (with value of Cmp being the condition).
00691 /// Before:
00692 ///   Head
00693 ///   SplitBefore
00694 ///   Tail
00695 /// After:
00696 ///   Head
00697 ///   if (Cond)
00698 ///     ThenBlock
00699 ///   SplitBefore
00700 ///   Tail
00701 ///
00702 /// If Unreachable is true, then ThenBlock ends with
00703 /// UnreachableInst, otherwise it branches to Tail.
00704 /// Returns the NewBasicBlock's terminator.
00705 
00706 TerminatorInst *llvm::SplitBlockAndInsertIfThen(Value *Cond,
00707                                                 Instruction *SplitBefore,
00708                                                 bool Unreachable,
00709                                                 MDNode *BranchWeights,
00710                                                 DominatorTree *DT) {
00711   BasicBlock *Head = SplitBefore->getParent();
00712   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore);
00713   TerminatorInst *HeadOldTerm = Head->getTerminator();
00714   LLVMContext &C = Head->getContext();
00715   BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00716   TerminatorInst *CheckTerm;
00717   if (Unreachable)
00718     CheckTerm = new UnreachableInst(C, ThenBlock);
00719   else
00720     CheckTerm = BranchInst::Create(Tail, ThenBlock);
00721   CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
00722   BranchInst *HeadNewTerm =
00723     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
00724   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
00725   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
00726 
00727   if (DT) {
00728     if (DomTreeNode *OldNode = DT->getNode(Head)) {
00729       std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
00730 
00731       DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
00732       for (auto Child : Children)
00733         DT->changeImmediateDominator(Child, NewNode);
00734 
00735       // Head dominates ThenBlock.
00736       DT->addNewBlock(ThenBlock, Head);
00737     }
00738   }
00739 
00740   return CheckTerm;
00741 }
00742 
00743 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
00744 /// but also creates the ElseBlock.
00745 /// Before:
00746 ///   Head
00747 ///   SplitBefore
00748 ///   Tail
00749 /// After:
00750 ///   Head
00751 ///   if (Cond)
00752 ///     ThenBlock
00753 ///   else
00754 ///     ElseBlock
00755 ///   SplitBefore
00756 ///   Tail
00757 void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
00758                                          TerminatorInst **ThenTerm,
00759                                          TerminatorInst **ElseTerm,
00760                                          MDNode *BranchWeights) {
00761   BasicBlock *Head = SplitBefore->getParent();
00762   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore);
00763   TerminatorInst *HeadOldTerm = Head->getTerminator();
00764   LLVMContext &C = Head->getContext();
00765   BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00766   BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00767   *ThenTerm = BranchInst::Create(Tail, ThenBlock);
00768   (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
00769   *ElseTerm = BranchInst::Create(Tail, ElseBlock);
00770   (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
00771   BranchInst *HeadNewTerm =
00772     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
00773   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
00774   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
00775 }
00776 
00777 
00778 /// GetIfCondition - Given a basic block (BB) with two predecessors,
00779 /// check to see if the merge at this block is due
00780 /// to an "if condition".  If so, return the boolean condition that determines
00781 /// which entry into BB will be taken.  Also, return by references the block
00782 /// that will be entered from if the condition is true, and the block that will
00783 /// be entered if the condition is false.
00784 ///
00785 /// This does no checking to see if the true/false blocks have large or unsavory
00786 /// instructions in them.
00787 Value *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
00788                              BasicBlock *&IfFalse) {
00789   PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
00790   BasicBlock *Pred1 = nullptr;
00791   BasicBlock *Pred2 = nullptr;
00792 
00793   if (SomePHI) {
00794     if (SomePHI->getNumIncomingValues() != 2)
00795       return nullptr;
00796     Pred1 = SomePHI->getIncomingBlock(0);
00797     Pred2 = SomePHI->getIncomingBlock(1);
00798   } else {
00799     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
00800     if (PI == PE) // No predecessor
00801       return nullptr;
00802     Pred1 = *PI++;
00803     if (PI == PE) // Only one predecessor
00804       return nullptr;
00805     Pred2 = *PI++;
00806     if (PI != PE) // More than two predecessors
00807       return nullptr;
00808   }
00809 
00810   // We can only handle branches.  Other control flow will be lowered to
00811   // branches if possible anyway.
00812   BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
00813   BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
00814   if (!Pred1Br || !Pred2Br)
00815     return nullptr;
00816 
00817   // Eliminate code duplication by ensuring that Pred1Br is conditional if
00818   // either are.
00819   if (Pred2Br->isConditional()) {
00820     // If both branches are conditional, we don't have an "if statement".  In
00821     // reality, we could transform this case, but since the condition will be
00822     // required anyway, we stand no chance of eliminating it, so the xform is
00823     // probably not profitable.
00824     if (Pred1Br->isConditional())
00825       return nullptr;
00826 
00827     std::swap(Pred1, Pred2);
00828     std::swap(Pred1Br, Pred2Br);
00829   }
00830 
00831   if (Pred1Br->isConditional()) {
00832     // The only thing we have to watch out for here is to make sure that Pred2
00833     // doesn't have incoming edges from other blocks.  If it does, the condition
00834     // doesn't dominate BB.
00835     if (!Pred2->getSinglePredecessor())
00836       return nullptr;
00837 
00838     // If we found a conditional branch predecessor, make sure that it branches
00839     // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
00840     if (Pred1Br->getSuccessor(0) == BB &&
00841         Pred1Br->getSuccessor(1) == Pred2) {
00842       IfTrue = Pred1;
00843       IfFalse = Pred2;
00844     } else if (Pred1Br->getSuccessor(0) == Pred2 &&
00845                Pred1Br->getSuccessor(1) == BB) {
00846       IfTrue = Pred2;
00847       IfFalse = Pred1;
00848     } else {
00849       // We know that one arm of the conditional goes to BB, so the other must
00850       // go somewhere unrelated, and this must not be an "if statement".
00851       return nullptr;
00852     }
00853 
00854     return Pred1Br->getCondition();
00855   }
00856 
00857   // Ok, if we got here, both predecessors end with an unconditional branch to
00858   // BB.  Don't panic!  If both blocks only have a single (identical)
00859   // predecessor, and THAT is a conditional branch, then we're all ok!
00860   BasicBlock *CommonPred = Pred1->getSinglePredecessor();
00861   if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
00862     return nullptr;
00863 
00864   // Otherwise, if this is a conditional branch, then we can use it!
00865   BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
00866   if (!BI) return nullptr;
00867 
00868   assert(BI->isConditional() && "Two successors but not conditional?");
00869   if (BI->getSuccessor(0) == Pred1) {
00870     IfTrue = Pred1;
00871     IfFalse = Pred2;
00872   } else {
00873     IfTrue = Pred2;
00874     IfFalse = Pred1;
00875   }
00876   return BI->getCondition();
00877 }