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 (BasicBlock *Succ : BBTerm->successors())
00045     Succ->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,
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 
00081     PN->eraseFromParent();
00082   }
00083 }
00084 
00085 
00086 /// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it
00087 /// is dead. Also recursively delete any operands that become dead as
00088 /// a result. This includes tracing the def-use list from the PHI to see if
00089 /// it is ultimately unused or if it reaches an unused cycle.
00090 bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI) {
00091   // Recursively deleting a PHI may cause multiple PHIs to be deleted
00092   // or RAUW'd undef, so use an array of WeakVH for the PHIs to delete.
00093   SmallVector<WeakVH, 8> PHIs;
00094   for (BasicBlock::iterator I = BB->begin();
00095        PHINode *PN = dyn_cast<PHINode>(I); ++I)
00096     PHIs.push_back(PN);
00097 
00098   bool Changed = false;
00099   for (unsigned i = 0, e = PHIs.size(); i != e; ++i)
00100     if (PHINode *PN = dyn_cast_or_null<PHINode>(PHIs[i].operator Value*()))
00101       Changed |= RecursivelyDeleteDeadPHINode(PN, TLI);
00102 
00103   return Changed;
00104 }
00105 
00106 /// MergeBlockIntoPredecessor - Attempts to merge a block into its predecessor,
00107 /// if possible.  The return value indicates success or failure.
00108 bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT,
00109                                      LoopInfo *LI,
00110                                      MemoryDependenceAnalysis *MemDep) {
00111   // Don't merge away blocks who have their address taken.
00112   if (BB->hasAddressTaken()) return false;
00113 
00114   // Can't merge if there are multiple predecessors, or no predecessors.
00115   BasicBlock *PredBB = BB->getUniquePredecessor();
00116   if (!PredBB) return false;
00117 
00118   // Don't break self-loops.
00119   if (PredBB == BB) return false;
00120   // Don't break unwinding instructions.
00121   if (PredBB->getTerminator()->isExceptional())
00122     return false;
00123 
00124   succ_iterator SI(succ_begin(PredBB)), SE(succ_end(PredBB));
00125   BasicBlock *OnlySucc = BB;
00126   for (; SI != SE; ++SI)
00127     if (*SI != OnlySucc) {
00128       OnlySucc = nullptr;     // There are multiple distinct successors!
00129       break;
00130     }
00131 
00132   // Can't merge if there are multiple successors.
00133   if (!OnlySucc) return false;
00134 
00135   // Can't merge if there is PHI loop.
00136   for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE; ++BI) {
00137     if (PHINode *PN = dyn_cast<PHINode>(BI)) {
00138       for (Value *IncValue : PN->incoming_values())
00139         if (IncValue == PN)
00140           return false;
00141     } else
00142       break;
00143   }
00144 
00145   // Begin by getting rid of unneeded PHIs.
00146   if (isa<PHINode>(BB->front()))
00147     FoldSingleEntryPHINodes(BB, MemDep);
00148 
00149   // Delete the unconditional branch from the predecessor...
00150   PredBB->getInstList().pop_back();
00151 
00152   // Make all PHI nodes that referred to BB now refer to Pred as their
00153   // source...
00154   BB->replaceAllUsesWith(PredBB);
00155 
00156   // Move all definitions in the successor to the predecessor...
00157   PredBB->getInstList().splice(PredBB->end(), BB->getInstList());
00158 
00159   // Inherit predecessors name if it exists.
00160   if (!PredBB->hasName())
00161     PredBB->takeName(BB);
00162 
00163   // Finally, erase the old block and update dominator info.
00164   if (DT)
00165     if (DomTreeNode *DTN = DT->getNode(BB)) {
00166       DomTreeNode *PredDTN = DT->getNode(PredBB);
00167       SmallVector<DomTreeNode *, 8> Children(DTN->begin(), DTN->end());
00168       for (SmallVectorImpl<DomTreeNode *>::iterator DI = Children.begin(),
00169                                                     DE = Children.end();
00170            DI != DE; ++DI)
00171         DT->changeImmediateDominator(*DI, PredDTN);
00172 
00173       DT->eraseNode(BB);
00174     }
00175 
00176   if (LI)
00177     LI->removeBlock(BB);
00178 
00179   if (MemDep)
00180     MemDep->invalidateCachedPredecessors();
00181 
00182   BB->eraseFromParent();
00183   return true;
00184 }
00185 
00186 /// ReplaceInstWithValue - Replace all uses of an instruction (specified by BI)
00187 /// with a value, then remove and delete the original instruction.
00188 ///
00189 void llvm::ReplaceInstWithValue(BasicBlock::InstListType &BIL,
00190                                 BasicBlock::iterator &BI, Value *V) {
00191   Instruction &I = *BI;
00192   // Replaces all of the uses of the instruction with uses of the value
00193   I.replaceAllUsesWith(V);
00194 
00195   // Make sure to propagate a name if there is one already.
00196   if (I.hasName() && !V->hasName())
00197     V->takeName(&I);
00198 
00199   // Delete the unnecessary instruction now...
00200   BI = BIL.erase(BI);
00201 }
00202 
00203 
00204 /// ReplaceInstWithInst - Replace the instruction specified by BI with the
00205 /// instruction specified by I.  The original instruction is deleted and BI is
00206 /// updated to point to the new instruction.
00207 ///
00208 void llvm::ReplaceInstWithInst(BasicBlock::InstListType &BIL,
00209                                BasicBlock::iterator &BI, Instruction *I) {
00210   assert(I->getParent() == nullptr &&
00211          "ReplaceInstWithInst: Instruction already inserted into basic block!");
00212 
00213   // Copy debug location to newly added instruction, if it wasn't already set
00214   // by the caller.
00215   if (!I->getDebugLoc())
00216     I->setDebugLoc(BI->getDebugLoc());
00217 
00218   // Insert the new instruction into the basic block...
00219   BasicBlock::iterator New = BIL.insert(BI, I);
00220 
00221   // Replace all uses of the old instruction, and delete it.
00222   ReplaceInstWithValue(BIL, BI, I);
00223 
00224   // Move BI back to point to the newly inserted instruction
00225   BI = New;
00226 }
00227 
00228 /// ReplaceInstWithInst - Replace the instruction specified by From with the
00229 /// instruction specified by To.
00230 ///
00231 void llvm::ReplaceInstWithInst(Instruction *From, Instruction *To) {
00232   BasicBlock::iterator BI(From);
00233   ReplaceInstWithInst(From->getParent()->getInstList(), BI, To);
00234 }
00235 
00236 /// SplitEdge -  Split the edge connecting specified block. Pass P must
00237 /// not be NULL.
00238 BasicBlock *llvm::SplitEdge(BasicBlock *BB, BasicBlock *Succ, DominatorTree *DT,
00239                             LoopInfo *LI) {
00240   unsigned SuccNum = GetSuccessorNumber(BB, Succ);
00241 
00242   // If this is a critical edge, let SplitCriticalEdge do it.
00243   TerminatorInst *LatchTerm = BB->getTerminator();
00244   if (SplitCriticalEdge(LatchTerm, SuccNum, CriticalEdgeSplittingOptions(DT, LI)
00245                                                 .setPreserveLCSSA()))
00246     return LatchTerm->getSuccessor(SuccNum);
00247 
00248   // If the edge isn't critical, then BB has a single successor or Succ has a
00249   // single pred.  Split the block.
00250   if (BasicBlock *SP = Succ->getSinglePredecessor()) {
00251     // If the successor only has a single pred, split the top of the successor
00252     // block.
00253     assert(SP == BB && "CFG broken");
00254     SP = nullptr;
00255     return SplitBlock(Succ, &Succ->front(), DT, LI);
00256   }
00257 
00258   // Otherwise, if BB has a single successor, split it at the bottom of the
00259   // block.
00260   assert(BB->getTerminator()->getNumSuccessors() == 1 &&
00261          "Should have a single succ!");
00262   return SplitBlock(BB, BB->getTerminator(), DT, LI);
00263 }
00264 
00265 unsigned
00266 llvm::SplitAllCriticalEdges(Function &F,
00267                             const CriticalEdgeSplittingOptions &Options) {
00268   unsigned NumBroken = 0;
00269   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) {
00270     TerminatorInst *TI = I->getTerminator();
00271     if (TI->getNumSuccessors() > 1 && !isa<IndirectBrInst>(TI))
00272       for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
00273         if (SplitCriticalEdge(TI, i, Options))
00274           ++NumBroken;
00275   }
00276   return NumBroken;
00277 }
00278 
00279 /// SplitBlock - Split the specified block at the specified instruction - every
00280 /// thing before SplitPt stays in Old and everything starting with SplitPt moves
00281 /// to a new block.  The two blocks are joined by an unconditional branch and
00282 /// the loop info is updated.
00283 ///
00284 BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt,
00285                              DominatorTree *DT, LoopInfo *LI) {
00286   BasicBlock::iterator SplitIt = SplitPt->getIterator();
00287   while (isa<PHINode>(SplitIt) || SplitIt->isEHPad())
00288     ++SplitIt;
00289   BasicBlock *New = Old->splitBasicBlock(SplitIt, Old->getName()+".split");
00290 
00291   // The new block lives in whichever loop the old one did. This preserves
00292   // LCSSA as well, because we force the split point to be after any PHI nodes.
00293   if (LI)
00294     if (Loop *L = LI->getLoopFor(Old))
00295       L->addBasicBlockToLoop(New, *LI);
00296 
00297   if (DT)
00298     // Old dominates New. New node dominates all other nodes dominated by Old.
00299     if (DomTreeNode *OldNode = DT->getNode(Old)) {
00300       std::vector<DomTreeNode *> Children;
00301       for (DomTreeNode::iterator I = OldNode->begin(), E = OldNode->end();
00302            I != E; ++I)
00303         Children.push_back(*I);
00304 
00305       DomTreeNode *NewNode = DT->addNewBlock(New, Old);
00306       for (std::vector<DomTreeNode *>::iterator I = Children.begin(),
00307              E = Children.end(); I != E; ++I)
00308         DT->changeImmediateDominator(*I, NewNode);
00309     }
00310 
00311   return New;
00312 }
00313 
00314 /// UpdateAnalysisInformation - Update DominatorTree, LoopInfo, and LCCSA
00315 /// analysis information.
00316 static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB,
00317                                       ArrayRef<BasicBlock *> Preds,
00318                                       DominatorTree *DT, LoopInfo *LI,
00319                                       bool PreserveLCSSA, bool &HasLoopExit) {
00320   // Update dominator tree if available.
00321   if (DT)
00322     DT->splitBlock(NewBB);
00323 
00324   // The rest of the logic is only relevant for updating the loop structures.
00325   if (!LI)
00326     return;
00327 
00328   Loop *L = LI->getLoopFor(OldBB);
00329 
00330   // If we need to preserve loop analyses, collect some information about how
00331   // this split will affect loops.
00332   bool IsLoopEntry = !!L;
00333   bool SplitMakesNewLoopHeader = false;
00334   for (ArrayRef<BasicBlock *>::iterator i = Preds.begin(), e = Preds.end();
00335        i != e; ++i) {
00336     BasicBlock *Pred = *i;
00337 
00338     // If we need to preserve LCSSA, determine if any of the preds is a loop
00339     // exit.
00340     if (PreserveLCSSA)
00341       if (Loop *PL = LI->getLoopFor(Pred))
00342         if (!PL->contains(OldBB))
00343           HasLoopExit = true;
00344 
00345     // If we need to preserve LoopInfo, note whether any of the preds crosses
00346     // an interesting loop boundary.
00347     if (!L)
00348       continue;
00349     if (L->contains(Pred))
00350       IsLoopEntry = false;
00351     else
00352       SplitMakesNewLoopHeader = true;
00353   }
00354 
00355   // Unless we have a loop for OldBB, nothing else to do here.
00356   if (!L)
00357     return;
00358 
00359   if (IsLoopEntry) {
00360     // Add the new block to the nearest enclosing loop (and not an adjacent
00361     // loop). To find this, examine each of the predecessors and determine which
00362     // loops enclose them, and select the most-nested loop which contains the
00363     // loop containing the block being split.
00364     Loop *InnermostPredLoop = nullptr;
00365     for (ArrayRef<BasicBlock*>::iterator
00366            i = Preds.begin(), e = Preds.end(); i != e; ++i) {
00367       BasicBlock *Pred = *i;
00368       if (Loop *PredLoop = LI->getLoopFor(Pred)) {
00369         // Seek a loop which actually contains the block being split (to avoid
00370         // adjacent loops).
00371         while (PredLoop && !PredLoop->contains(OldBB))
00372           PredLoop = PredLoop->getParentLoop();
00373 
00374         // Select the most-nested of these loops which contains the block.
00375         if (PredLoop && PredLoop->contains(OldBB) &&
00376             (!InnermostPredLoop ||
00377              InnermostPredLoop->getLoopDepth() < PredLoop->getLoopDepth()))
00378           InnermostPredLoop = PredLoop;
00379       }
00380     }
00381 
00382     if (InnermostPredLoop)
00383       InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI);
00384   } else {
00385     L->addBasicBlockToLoop(NewBB, *LI);
00386     if (SplitMakesNewLoopHeader)
00387       L->moveToHeader(NewBB);
00388   }
00389 }
00390 
00391 /// UpdatePHINodes - Update the PHI nodes in OrigBB to include the values coming
00392 /// from NewBB. This also updates AliasAnalysis, if available.
00393 static void UpdatePHINodes(BasicBlock *OrigBB, BasicBlock *NewBB,
00394                            ArrayRef<BasicBlock *> Preds, BranchInst *BI,
00395                            bool HasLoopExit) {
00396   // Otherwise, create a new PHI node in NewBB for each PHI node in OrigBB.
00397   SmallPtrSet<BasicBlock *, 16> PredSet(Preds.begin(), Preds.end());
00398   for (BasicBlock::iterator I = OrigBB->begin(); isa<PHINode>(I); ) {
00399     PHINode *PN = cast<PHINode>(I++);
00400 
00401     // Check to see if all of the values coming in are the same.  If so, we
00402     // don't need to create a new PHI node, unless it's needed for LCSSA.
00403     Value *InVal = nullptr;
00404     if (!HasLoopExit) {
00405       InVal = PN->getIncomingValueForBlock(Preds[0]);
00406       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00407         if (!PredSet.count(PN->getIncomingBlock(i)))
00408           continue;
00409         if (!InVal)
00410           InVal = PN->getIncomingValue(i);
00411         else if (InVal != PN->getIncomingValue(i)) {
00412           InVal = nullptr;
00413           break;
00414         }
00415       }
00416     }
00417 
00418     if (InVal) {
00419       // If all incoming values for the new PHI would be the same, just don't
00420       // make a new PHI.  Instead, just remove the incoming values from the old
00421       // PHI.
00422 
00423       // NOTE! This loop walks backwards for a reason! First off, this minimizes
00424       // the cost of removal if we end up removing a large number of values, and
00425       // second off, this ensures that the indices for the incoming values
00426       // aren't invalidated when we remove one.
00427       for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i)
00428         if (PredSet.count(PN->getIncomingBlock(i)))
00429           PN->removeIncomingValue(i, false);
00430 
00431       // Add an incoming value to the PHI node in the loop for the preheader
00432       // edge.
00433       PN->addIncoming(InVal, NewBB);
00434       continue;
00435     }
00436 
00437     // If the values coming into the block are not the same, we need a new
00438     // PHI.
00439     // Create the new PHI node, insert it into NewBB at the end of the block
00440     PHINode *NewPHI =
00441         PHINode::Create(PN->getType(), Preds.size(), PN->getName() + ".ph", BI);
00442 
00443     // NOTE! This loop walks backwards for a reason! First off, this minimizes
00444     // the cost of removal if we end up removing a large number of values, and
00445     // second off, this ensures that the indices for the incoming values aren't
00446     // invalidated when we remove one.
00447     for (int64_t i = PN->getNumIncomingValues() - 1; i >= 0; --i) {
00448       BasicBlock *IncomingBB = PN->getIncomingBlock(i);
00449       if (PredSet.count(IncomingBB)) {
00450         Value *V = PN->removeIncomingValue(i, false);
00451         NewPHI->addIncoming(V, IncomingBB);
00452       }
00453     }
00454 
00455     PN->addIncoming(NewPHI, NewBB);
00456   }
00457 }
00458 
00459 /// SplitBlockPredecessors - This method introduces at least one new basic block
00460 /// into the function and moves some of the predecessors of BB to be
00461 /// predecessors of the new block. The new predecessors are indicated by the
00462 /// Preds array. The new block is given a suffix of 'Suffix'. Returns new basic
00463 /// block to which predecessors from Preds are now pointing.
00464 ///
00465 /// If BB is a landingpad block then additional basicblock might be introduced.
00466 /// It will have suffix of 'Suffix'+".split_lp".
00467 /// See SplitLandingPadPredecessors for more details on this case.
00468 ///
00469 /// This currently updates the LLVM IR, AliasAnalysis, DominatorTree,
00470 /// LoopInfo, and LCCSA but no other analyses. In particular, it does not
00471 /// preserve LoopSimplify (because it's complicated to handle the case where one
00472 /// of the edges being split is an exit of a loop with other exits).
00473 ///
00474 BasicBlock *llvm::SplitBlockPredecessors(BasicBlock *BB,
00475                                          ArrayRef<BasicBlock *> Preds,
00476                                          const char *Suffix, DominatorTree *DT,
00477                                          LoopInfo *LI, bool PreserveLCSSA) {
00478   // Do not attempt to split that which cannot be split.
00479   if (!BB->canSplitPredecessors())
00480     return nullptr;
00481 
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(), NewBBs, DT,
00489                                 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, 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                                        DominatorTree *DT, LoopInfo *LI,
00550                                        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, 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, 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 only
00630     // if the original landingpad instruction has some uses.
00631     if (!LPad->use_empty()) {
00632       assert(!LPad->getType()->isTokenTy() &&
00633              "Split cannot be applied if LPad is token type. Otherwise an "
00634              "invalid PHINode of token type would be created.");
00635       PHINode *PN = PHINode::Create(LPad->getType(), 2, "lpad.phi", LPad);
00636       PN->addIncoming(Clone1, NewBB1);
00637       PN->addIncoming(Clone2, NewBB2);
00638       LPad->replaceAllUsesWith(PN);
00639     }
00640     LPad->eraseFromParent();
00641   } else {
00642     // There is no second clone. Just replace the landing pad with the first
00643     // clone.
00644     LPad->replaceAllUsesWith(Clone1);
00645     LPad->eraseFromParent();
00646   }
00647 }
00648 
00649 /// FoldReturnIntoUncondBranch - This method duplicates the specified return
00650 /// instruction into a predecessor which ends in an unconditional branch. If
00651 /// the return instruction returns a value defined by a PHI, propagate the
00652 /// right value into the return. It returns the new return instruction in the
00653 /// predecessor.
00654 ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
00655                                              BasicBlock *Pred) {
00656   Instruction *UncondBranch = Pred->getTerminator();
00657   // Clone the return and add it to the end of the predecessor.
00658   Instruction *NewRet = RI->clone();
00659   Pred->getInstList().push_back(NewRet);
00660 
00661   // If the return instruction returns a value, and if the value was a
00662   // PHI node in "BB", propagate the right value into the return.
00663   for (User::op_iterator i = NewRet->op_begin(), e = NewRet->op_end();
00664        i != e; ++i) {
00665     Value *V = *i;
00666     Instruction *NewBC = nullptr;
00667     if (BitCastInst *BCI = dyn_cast<BitCastInst>(V)) {
00668       // Return value might be bitcasted. Clone and insert it before the
00669       // return instruction.
00670       V = BCI->getOperand(0);
00671       NewBC = BCI->clone();
00672       Pred->getInstList().insert(NewRet->getIterator(), NewBC);
00673       *i = NewBC;
00674     }
00675     if (PHINode *PN = dyn_cast<PHINode>(V)) {
00676       if (PN->getParent() == BB) {
00677         if (NewBC)
00678           NewBC->setOperand(0, PN->getIncomingValueForBlock(Pred));
00679         else
00680           *i = PN->getIncomingValueForBlock(Pred);
00681       }
00682     }
00683   }
00684 
00685   // Update any PHI nodes in the returning block to realize that we no
00686   // longer branch to them.
00687   BB->removePredecessor(Pred);
00688   UncondBranch->eraseFromParent();
00689   return cast<ReturnInst>(NewRet);
00690 }
00691 
00692 /// SplitBlockAndInsertIfThen - Split the containing block at the
00693 /// specified instruction - everything before and including SplitBefore stays
00694 /// in the old basic block, and everything after SplitBefore is moved to a
00695 /// new block. The two blocks are connected by a conditional branch
00696 /// (with value of Cmp being the condition).
00697 /// Before:
00698 ///   Head
00699 ///   SplitBefore
00700 ///   Tail
00701 /// After:
00702 ///   Head
00703 ///   if (Cond)
00704 ///     ThenBlock
00705 ///   SplitBefore
00706 ///   Tail
00707 ///
00708 /// If Unreachable is true, then ThenBlock ends with
00709 /// UnreachableInst, otherwise it branches to Tail.
00710 /// Returns the NewBasicBlock's terminator.
00711 
00712 TerminatorInst *llvm::SplitBlockAndInsertIfThen(Value *Cond,
00713                                                 Instruction *SplitBefore,
00714                                                 bool Unreachable,
00715                                                 MDNode *BranchWeights,
00716                                                 DominatorTree *DT) {
00717   BasicBlock *Head = SplitBefore->getParent();
00718   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
00719   TerminatorInst *HeadOldTerm = Head->getTerminator();
00720   LLVMContext &C = Head->getContext();
00721   BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00722   TerminatorInst *CheckTerm;
00723   if (Unreachable)
00724     CheckTerm = new UnreachableInst(C, ThenBlock);
00725   else
00726     CheckTerm = BranchInst::Create(Tail, ThenBlock);
00727   CheckTerm->setDebugLoc(SplitBefore->getDebugLoc());
00728   BranchInst *HeadNewTerm =
00729     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/Tail, Cond);
00730   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
00731   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
00732 
00733   if (DT) {
00734     if (DomTreeNode *OldNode = DT->getNode(Head)) {
00735       std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
00736 
00737       DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
00738       for (auto Child : Children)
00739         DT->changeImmediateDominator(Child, NewNode);
00740 
00741       // Head dominates ThenBlock.
00742       DT->addNewBlock(ThenBlock, Head);
00743     }
00744   }
00745 
00746   return CheckTerm;
00747 }
00748 
00749 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,
00750 /// but also creates the ElseBlock.
00751 /// Before:
00752 ///   Head
00753 ///   SplitBefore
00754 ///   Tail
00755 /// After:
00756 ///   Head
00757 ///   if (Cond)
00758 ///     ThenBlock
00759 ///   else
00760 ///     ElseBlock
00761 ///   SplitBefore
00762 ///   Tail
00763 void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
00764                                          TerminatorInst **ThenTerm,
00765                                          TerminatorInst **ElseTerm,
00766                                          MDNode *BranchWeights) {
00767   BasicBlock *Head = SplitBefore->getParent();
00768   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
00769   TerminatorInst *HeadOldTerm = Head->getTerminator();
00770   LLVMContext &C = Head->getContext();
00771   BasicBlock *ThenBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00772   BasicBlock *ElseBlock = BasicBlock::Create(C, "", Head->getParent(), Tail);
00773   *ThenTerm = BranchInst::Create(Tail, ThenBlock);
00774   (*ThenTerm)->setDebugLoc(SplitBefore->getDebugLoc());
00775   *ElseTerm = BranchInst::Create(Tail, ElseBlock);
00776   (*ElseTerm)->setDebugLoc(SplitBefore->getDebugLoc());
00777   BranchInst *HeadNewTerm =
00778     BranchInst::Create(/*ifTrue*/ThenBlock, /*ifFalse*/ElseBlock, Cond);
00779   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
00780   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
00781 }
00782 
00783 
00784 /// GetIfCondition - Given a basic block (BB) with two predecessors,
00785 /// check to see if the merge at this block is due
00786 /// to an "if condition".  If so, return the boolean condition that determines
00787 /// which entry into BB will be taken.  Also, return by references the block
00788 /// that will be entered from if the condition is true, and the block that will
00789 /// be entered if the condition is false.
00790 ///
00791 /// This does no checking to see if the true/false blocks have large or unsavory
00792 /// instructions in them.
00793 Value *llvm::GetIfCondition(BasicBlock *BB, BasicBlock *&IfTrue,
00794                              BasicBlock *&IfFalse) {
00795   PHINode *SomePHI = dyn_cast<PHINode>(BB->begin());
00796   BasicBlock *Pred1 = nullptr;
00797   BasicBlock *Pred2 = nullptr;
00798 
00799   if (SomePHI) {
00800     if (SomePHI->getNumIncomingValues() != 2)
00801       return nullptr;
00802     Pred1 = SomePHI->getIncomingBlock(0);
00803     Pred2 = SomePHI->getIncomingBlock(1);
00804   } else {
00805     pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
00806     if (PI == PE) // No predecessor
00807       return nullptr;
00808     Pred1 = *PI++;
00809     if (PI == PE) // Only one predecessor
00810       return nullptr;
00811     Pred2 = *PI++;
00812     if (PI != PE) // More than two predecessors
00813       return nullptr;
00814   }
00815 
00816   // We can only handle branches.  Other control flow will be lowered to
00817   // branches if possible anyway.
00818   BranchInst *Pred1Br = dyn_cast<BranchInst>(Pred1->getTerminator());
00819   BranchInst *Pred2Br = dyn_cast<BranchInst>(Pred2->getTerminator());
00820   if (!Pred1Br || !Pred2Br)
00821     return nullptr;
00822 
00823   // Eliminate code duplication by ensuring that Pred1Br is conditional if
00824   // either are.
00825   if (Pred2Br->isConditional()) {
00826     // If both branches are conditional, we don't have an "if statement".  In
00827     // reality, we could transform this case, but since the condition will be
00828     // required anyway, we stand no chance of eliminating it, so the xform is
00829     // probably not profitable.
00830     if (Pred1Br->isConditional())
00831       return nullptr;
00832 
00833     std::swap(Pred1, Pred2);
00834     std::swap(Pred1Br, Pred2Br);
00835   }
00836 
00837   if (Pred1Br->isConditional()) {
00838     // The only thing we have to watch out for here is to make sure that Pred2
00839     // doesn't have incoming edges from other blocks.  If it does, the condition
00840     // doesn't dominate BB.
00841     if (!Pred2->getSinglePredecessor())
00842       return nullptr;
00843 
00844     // If we found a conditional branch predecessor, make sure that it branches
00845     // to BB and Pred2Br.  If it doesn't, this isn't an "if statement".
00846     if (Pred1Br->getSuccessor(0) == BB &&
00847         Pred1Br->getSuccessor(1) == Pred2) {
00848       IfTrue = Pred1;
00849       IfFalse = Pred2;
00850     } else if (Pred1Br->getSuccessor(0) == Pred2 &&
00851                Pred1Br->getSuccessor(1) == BB) {
00852       IfTrue = Pred2;
00853       IfFalse = Pred1;
00854     } else {
00855       // We know that one arm of the conditional goes to BB, so the other must
00856       // go somewhere unrelated, and this must not be an "if statement".
00857       return nullptr;
00858     }
00859 
00860     return Pred1Br->getCondition();
00861   }
00862 
00863   // Ok, if we got here, both predecessors end with an unconditional branch to
00864   // BB.  Don't panic!  If both blocks only have a single (identical)
00865   // predecessor, and THAT is a conditional branch, then we're all ok!
00866   BasicBlock *CommonPred = Pred1->getSinglePredecessor();
00867   if (CommonPred == nullptr || CommonPred != Pred2->getSinglePredecessor())
00868     return nullptr;
00869 
00870   // Otherwise, if this is a conditional branch, then we can use it!
00871   BranchInst *BI = dyn_cast<BranchInst>(CommonPred->getTerminator());
00872   if (!BI) return nullptr;
00873 
00874   assert(BI->isConditional() && "Two successors but not conditional?");
00875   if (BI->getSuccessor(0) == Pred1) {
00876     IfTrue = Pred1;
00877     IfFalse = Pred2;
00878   } else {
00879     IfTrue = Pred2;
00880     IfFalse = Pred1;
00881   }
00882   return BI->getCondition();
00883 }