LLVM API Documentation

Local.cpp
Go to the documentation of this file.
00001 //===-- Local.cpp - Functions to perform local transformations ------------===//
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 various local transformations to the
00011 // program.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #include "llvm/Transforms/Utils/Local.h"
00016 #include "llvm/ADT/DenseMap.h"
00017 #include "llvm/ADT/STLExtras.h"
00018 #include "llvm/ADT/SmallPtrSet.h"
00019 #include "llvm/ADT/Statistic.h"
00020 #include "llvm/Analysis/InstructionSimplify.h"
00021 #include "llvm/Analysis/MemoryBuiltins.h"
00022 #include "llvm/Analysis/ValueTracking.h"
00023 #include "llvm/IR/CFG.h"
00024 #include "llvm/IR/Constants.h"
00025 #include "llvm/IR/DIBuilder.h"
00026 #include "llvm/IR/DataLayout.h"
00027 #include "llvm/IR/DebugInfo.h"
00028 #include "llvm/IR/DerivedTypes.h"
00029 #include "llvm/IR/Dominators.h"
00030 #include "llvm/IR/GetElementPtrTypeIterator.h"
00031 #include "llvm/IR/GlobalAlias.h"
00032 #include "llvm/IR/GlobalVariable.h"
00033 #include "llvm/IR/IRBuilder.h"
00034 #include "llvm/IR/Instructions.h"
00035 #include "llvm/IR/IntrinsicInst.h"
00036 #include "llvm/IR/Intrinsics.h"
00037 #include "llvm/IR/MDBuilder.h"
00038 #include "llvm/IR/Metadata.h"
00039 #include "llvm/IR/Operator.h"
00040 #include "llvm/IR/ValueHandle.h"
00041 #include "llvm/Support/Debug.h"
00042 #include "llvm/Support/MathExtras.h"
00043 #include "llvm/Support/raw_ostream.h"
00044 using namespace llvm;
00045 
00046 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
00047 
00048 //===----------------------------------------------------------------------===//
00049 //  Local constant propagation.
00050 //
00051 
00052 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
00053 /// constant value, convert it into an unconditional branch to the constant
00054 /// destination.  This is a nontrivial operation because the successors of this
00055 /// basic block must have their PHI nodes updated.
00056 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
00057 /// conditions and indirectbr addresses this might make dead if
00058 /// DeleteDeadConditions is true.
00059 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
00060                                   const TargetLibraryInfo *TLI) {
00061   TerminatorInst *T = BB->getTerminator();
00062   IRBuilder<> Builder(T);
00063 
00064   // Branch - See if we are conditional jumping on constant
00065   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
00066     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
00067     BasicBlock *Dest1 = BI->getSuccessor(0);
00068     BasicBlock *Dest2 = BI->getSuccessor(1);
00069 
00070     if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
00071       // Are we branching on constant?
00072       // YES.  Change to unconditional branch...
00073       BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
00074       BasicBlock *OldDest     = Cond->getZExtValue() ? Dest2 : Dest1;
00075 
00076       //cerr << "Function: " << T->getParent()->getParent()
00077       //     << "\nRemoving branch from " << T->getParent()
00078       //     << "\n\nTo: " << OldDest << endl;
00079 
00080       // Let the basic block know that we are letting go of it.  Based on this,
00081       // it will adjust it's PHI nodes.
00082       OldDest->removePredecessor(BB);
00083 
00084       // Replace the conditional branch with an unconditional one.
00085       Builder.CreateBr(Destination);
00086       BI->eraseFromParent();
00087       return true;
00088     }
00089 
00090     if (Dest2 == Dest1) {       // Conditional branch to same location?
00091       // This branch matches something like this:
00092       //     br bool %cond, label %Dest, label %Dest
00093       // and changes it into:  br label %Dest
00094 
00095       // Let the basic block know that we are letting go of one copy of it.
00096       assert(BI->getParent() && "Terminator not inserted in block!");
00097       Dest1->removePredecessor(BI->getParent());
00098 
00099       // Replace the conditional branch with an unconditional one.
00100       Builder.CreateBr(Dest1);
00101       Value *Cond = BI->getCondition();
00102       BI->eraseFromParent();
00103       if (DeleteDeadConditions)
00104         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
00105       return true;
00106     }
00107     return false;
00108   }
00109 
00110   if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
00111     // If we are switching on a constant, we can convert the switch into a
00112     // single branch instruction!
00113     ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
00114     BasicBlock *TheOnlyDest = SI->getDefaultDest();
00115     BasicBlock *DefaultDest = TheOnlyDest;
00116 
00117     // Figure out which case it goes to.
00118     for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
00119          i != e; ++i) {
00120       // Found case matching a constant operand?
00121       if (i.getCaseValue() == CI) {
00122         TheOnlyDest = i.getCaseSuccessor();
00123         break;
00124       }
00125 
00126       // Check to see if this branch is going to the same place as the default
00127       // dest.  If so, eliminate it as an explicit compare.
00128       if (i.getCaseSuccessor() == DefaultDest) {
00129         MDNode* MD = SI->getMetadata(LLVMContext::MD_prof);
00130         unsigned NCases = SI->getNumCases();
00131         // Fold the case metadata into the default if there will be any branches
00132         // left, unless the metadata doesn't match the switch.
00133         if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) {
00134           // Collect branch weights into a vector.
00135           SmallVector<uint32_t, 8> Weights;
00136           for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
00137                ++MD_i) {
00138             ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(MD_i));
00139             assert(CI);
00140             Weights.push_back(CI->getValue().getZExtValue());
00141           }
00142           // Merge weight of this case to the default weight.
00143           unsigned idx = i.getCaseIndex();
00144           Weights[0] += Weights[idx+1];
00145           // Remove weight for this case.
00146           std::swap(Weights[idx+1], Weights.back());
00147           Weights.pop_back();
00148           SI->setMetadata(LLVMContext::MD_prof,
00149                           MDBuilder(BB->getContext()).
00150                           createBranchWeights(Weights));
00151         }
00152         // Remove this entry.
00153         DefaultDest->removePredecessor(SI->getParent());
00154         SI->removeCase(i);
00155         --i; --e;
00156         continue;
00157       }
00158 
00159       // Otherwise, check to see if the switch only branches to one destination.
00160       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
00161       // destinations.
00162       if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = 0;
00163     }
00164 
00165     if (CI && !TheOnlyDest) {
00166       // Branching on a constant, but not any of the cases, go to the default
00167       // successor.
00168       TheOnlyDest = SI->getDefaultDest();
00169     }
00170 
00171     // If we found a single destination that we can fold the switch into, do so
00172     // now.
00173     if (TheOnlyDest) {
00174       // Insert the new branch.
00175       Builder.CreateBr(TheOnlyDest);
00176       BasicBlock *BB = SI->getParent();
00177 
00178       // Remove entries from PHI nodes which we no longer branch to...
00179       for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
00180         // Found case matching a constant operand?
00181         BasicBlock *Succ = SI->getSuccessor(i);
00182         if (Succ == TheOnlyDest)
00183           TheOnlyDest = 0;  // Don't modify the first branch to TheOnlyDest
00184         else
00185           Succ->removePredecessor(BB);
00186       }
00187 
00188       // Delete the old switch.
00189       Value *Cond = SI->getCondition();
00190       SI->eraseFromParent();
00191       if (DeleteDeadConditions)
00192         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
00193       return true;
00194     }
00195 
00196     if (SI->getNumCases() == 1) {
00197       // Otherwise, we can fold this switch into a conditional branch
00198       // instruction if it has only one non-default destination.
00199       SwitchInst::CaseIt FirstCase = SI->case_begin();
00200       Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
00201           FirstCase.getCaseValue(), "cond");
00202 
00203       // Insert the new branch.
00204       BranchInst *NewBr = Builder.CreateCondBr(Cond,
00205                                                FirstCase.getCaseSuccessor(),
00206                                                SI->getDefaultDest());
00207       MDNode* MD = SI->getMetadata(LLVMContext::MD_prof);
00208       if (MD && MD->getNumOperands() == 3) {
00209         ConstantInt *SICase = dyn_cast<ConstantInt>(MD->getOperand(2));
00210         ConstantInt *SIDef = dyn_cast<ConstantInt>(MD->getOperand(1));
00211         assert(SICase && SIDef);
00212         // The TrueWeight should be the weight for the single case of SI.
00213         NewBr->setMetadata(LLVMContext::MD_prof,
00214                         MDBuilder(BB->getContext()).
00215                         createBranchWeights(SICase->getValue().getZExtValue(),
00216                                             SIDef->getValue().getZExtValue()));
00217       }
00218 
00219       // Delete the old switch.
00220       SI->eraseFromParent();
00221       return true;
00222     }
00223     return false;
00224   }
00225 
00226   if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {
00227     // indirectbr blockaddress(@F, @BB) -> br label @BB
00228     if (BlockAddress *BA =
00229           dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
00230       BasicBlock *TheOnlyDest = BA->getBasicBlock();
00231       // Insert the new branch.
00232       Builder.CreateBr(TheOnlyDest);
00233 
00234       for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
00235         if (IBI->getDestination(i) == TheOnlyDest)
00236           TheOnlyDest = 0;
00237         else
00238           IBI->getDestination(i)->removePredecessor(IBI->getParent());
00239       }
00240       Value *Address = IBI->getAddress();
00241       IBI->eraseFromParent();
00242       if (DeleteDeadConditions)
00243         RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);
00244 
00245       // If we didn't find our destination in the IBI successor list, then we
00246       // have undefined behavior.  Replace the unconditional branch with an
00247       // 'unreachable' instruction.
00248       if (TheOnlyDest) {
00249         BB->getTerminator()->eraseFromParent();
00250         new UnreachableInst(BB->getContext(), BB);
00251       }
00252 
00253       return true;
00254     }
00255   }
00256 
00257   return false;
00258 }
00259 
00260 
00261 //===----------------------------------------------------------------------===//
00262 //  Local dead code elimination.
00263 //
00264 
00265 /// isInstructionTriviallyDead - Return true if the result produced by the
00266 /// instruction is not used, and the instruction has no side effects.
00267 ///
00268 bool llvm::isInstructionTriviallyDead(Instruction *I,
00269                                       const TargetLibraryInfo *TLI) {
00270   if (!I->use_empty() || isa<TerminatorInst>(I)) return false;
00271 
00272   // We don't want the landingpad instruction removed by anything this general.
00273   if (isa<LandingPadInst>(I))
00274     return false;
00275 
00276   // We don't want debug info removed by anything this general, unless
00277   // debug info is empty.
00278   if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
00279     if (DDI->getAddress())
00280       return false;
00281     return true;
00282   }
00283   if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
00284     if (DVI->getValue())
00285       return false;
00286     return true;
00287   }
00288 
00289   if (!I->mayHaveSideEffects()) return true;
00290 
00291   // Special case intrinsics that "may have side effects" but can be deleted
00292   // when dead.
00293   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
00294     // Safe to delete llvm.stacksave if dead.
00295     if (II->getIntrinsicID() == Intrinsic::stacksave)
00296       return true;
00297 
00298     // Lifetime intrinsics are dead when their right-hand is undef.
00299     if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
00300         II->getIntrinsicID() == Intrinsic::lifetime_end)
00301       return isa<UndefValue>(II->getArgOperand(1));
00302   }
00303 
00304   if (isAllocLikeFn(I, TLI)) return true;
00305 
00306   if (CallInst *CI = isFreeCall(I, TLI))
00307     if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
00308       return C->isNullValue() || isa<UndefValue>(C);
00309 
00310   return false;
00311 }
00312 
00313 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
00314 /// trivially dead instruction, delete it.  If that makes any of its operands
00315 /// trivially dead, delete them too, recursively.  Return true if any
00316 /// instructions were deleted.
00317 bool
00318 llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
00319                                                  const TargetLibraryInfo *TLI) {
00320   Instruction *I = dyn_cast<Instruction>(V);
00321   if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI))
00322     return false;
00323 
00324   SmallVector<Instruction*, 16> DeadInsts;
00325   DeadInsts.push_back(I);
00326 
00327   do {
00328     I = DeadInsts.pop_back_val();
00329 
00330     // Null out all of the instruction's operands to see if any operand becomes
00331     // dead as we go.
00332     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
00333       Value *OpV = I->getOperand(i);
00334       I->setOperand(i, 0);
00335 
00336       if (!OpV->use_empty()) continue;
00337 
00338       // If the operand is an instruction that became dead as we nulled out the
00339       // operand, and if it is 'trivially' dead, delete it in a future loop
00340       // iteration.
00341       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
00342         if (isInstructionTriviallyDead(OpI, TLI))
00343           DeadInsts.push_back(OpI);
00344     }
00345 
00346     I->eraseFromParent();
00347   } while (!DeadInsts.empty());
00348 
00349   return true;
00350 }
00351 
00352 /// areAllUsesEqual - Check whether the uses of a value are all the same.
00353 /// This is similar to Instruction::hasOneUse() except this will also return
00354 /// true when there are no uses or multiple uses that all refer to the same
00355 /// value.
00356 static bool areAllUsesEqual(Instruction *I) {
00357   Value::user_iterator UI = I->user_begin();
00358   Value::user_iterator UE = I->user_end();
00359   if (UI == UE)
00360     return true;
00361 
00362   User *TheUse = *UI;
00363   for (++UI; UI != UE; ++UI) {
00364     if (*UI != TheUse)
00365       return false;
00366   }
00367   return true;
00368 }
00369 
00370 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
00371 /// dead PHI node, due to being a def-use chain of single-use nodes that
00372 /// either forms a cycle or is terminated by a trivially dead instruction,
00373 /// delete it.  If that makes any of its operands trivially dead, delete them
00374 /// too, recursively.  Return true if a change was made.
00375 bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN,
00376                                         const TargetLibraryInfo *TLI) {
00377   SmallPtrSet<Instruction*, 4> Visited;
00378   for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
00379        I = cast<Instruction>(*I->user_begin())) {
00380     if (I->use_empty())
00381       return RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
00382 
00383     // If we find an instruction more than once, we're on a cycle that
00384     // won't prove fruitful.
00385     if (!Visited.insert(I)) {
00386       // Break the cycle and delete the instruction and its operands.
00387       I->replaceAllUsesWith(UndefValue::get(I->getType()));
00388       (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
00389       return true;
00390     }
00391   }
00392   return false;
00393 }
00394 
00395 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to
00396 /// simplify any instructions in it and recursively delete dead instructions.
00397 ///
00398 /// This returns true if it changed the code, note that it can delete
00399 /// instructions in other blocks as well in this block.
00400 bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD,
00401                                        const TargetLibraryInfo *TLI) {
00402   bool MadeChange = false;
00403 
00404 #ifndef NDEBUG
00405   // In debug builds, ensure that the terminator of the block is never replaced
00406   // or deleted by these simplifications. The idea of simplification is that it
00407   // cannot introduce new instructions, and there is no way to replace the
00408   // terminator of a block without introducing a new instruction.
00409   AssertingVH<Instruction> TerminatorVH(--BB->end());
00410 #endif
00411 
00412   for (BasicBlock::iterator BI = BB->begin(), E = --BB->end(); BI != E; ) {
00413     assert(!BI->isTerminator());
00414     Instruction *Inst = BI++;
00415 
00416     WeakVH BIHandle(BI);
00417     if (recursivelySimplifyInstruction(Inst, TD, TLI)) {
00418       MadeChange = true;
00419       if (BIHandle != BI)
00420         BI = BB->begin();
00421       continue;
00422     }
00423 
00424     MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI);
00425     if (BIHandle != BI)
00426       BI = BB->begin();
00427   }
00428   return MadeChange;
00429 }
00430 
00431 //===----------------------------------------------------------------------===//
00432 //  Control Flow Graph Restructuring.
00433 //
00434 
00435 
00436 /// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this
00437 /// method is called when we're about to delete Pred as a predecessor of BB.  If
00438 /// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred.
00439 ///
00440 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
00441 /// nodes that collapse into identity values.  For example, if we have:
00442 ///   x = phi(1, 0, 0, 0)
00443 ///   y = and x, z
00444 ///
00445 /// .. and delete the predecessor corresponding to the '1', this will attempt to
00446 /// recursively fold the and to 0.
00447 void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
00448                                         DataLayout *TD) {
00449   // This only adjusts blocks with PHI nodes.
00450   if (!isa<PHINode>(BB->begin()))
00451     return;
00452 
00453   // Remove the entries for Pred from the PHI nodes in BB, but do not simplify
00454   // them down.  This will leave us with single entry phi nodes and other phis
00455   // that can be removed.
00456   BB->removePredecessor(Pred, true);
00457 
00458   WeakVH PhiIt = &BB->front();
00459   while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
00460     PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
00461     Value *OldPhiIt = PhiIt;
00462 
00463     if (!recursivelySimplifyInstruction(PN, TD))
00464       continue;
00465 
00466     // If recursive simplification ended up deleting the next PHI node we would
00467     // iterate to, then our iterator is invalid, restart scanning from the top
00468     // of the block.
00469     if (PhiIt != OldPhiIt) PhiIt = &BB->front();
00470   }
00471 }
00472 
00473 
00474 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
00475 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
00476 /// between them, moving the instructions in the predecessor into DestBB and
00477 /// deleting the predecessor block.
00478 ///
00479 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) {
00480   // If BB has single-entry PHI nodes, fold them.
00481   while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
00482     Value *NewVal = PN->getIncomingValue(0);
00483     // Replace self referencing PHI with undef, it must be dead.
00484     if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
00485     PN->replaceAllUsesWith(NewVal);
00486     PN->eraseFromParent();
00487   }
00488 
00489   BasicBlock *PredBB = DestBB->getSinglePredecessor();
00490   assert(PredBB && "Block doesn't have a single predecessor!");
00491 
00492   // Zap anything that took the address of DestBB.  Not doing this will give the
00493   // address an invalid value.
00494   if (DestBB->hasAddressTaken()) {
00495     BlockAddress *BA = BlockAddress::get(DestBB);
00496     Constant *Replacement =
00497       ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1);
00498     BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
00499                                                      BA->getType()));
00500     BA->destroyConstant();
00501   }
00502 
00503   // Anything that branched to PredBB now branches to DestBB.
00504   PredBB->replaceAllUsesWith(DestBB);
00505 
00506   // Splice all the instructions from PredBB to DestBB.
00507   PredBB->getTerminator()->eraseFromParent();
00508   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
00509 
00510   if (P) {
00511     if (DominatorTreeWrapperPass *DTWP =
00512             P->getAnalysisIfAvailable<DominatorTreeWrapperPass>()) {
00513       DominatorTree &DT = DTWP->getDomTree();
00514       BasicBlock *PredBBIDom = DT.getNode(PredBB)->getIDom()->getBlock();
00515       DT.changeImmediateDominator(DestBB, PredBBIDom);
00516       DT.eraseNode(PredBB);
00517     }
00518   }
00519   // Nuke BB.
00520   PredBB->eraseFromParent();
00521 }
00522 
00523 /// CanMergeValues - Return true if we can choose one of these values to use
00524 /// in place of the other. Note that we will always choose the non-undef
00525 /// value to keep.
00526 static bool CanMergeValues(Value *First, Value *Second) {
00527   return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
00528 }
00529 
00530 /// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an
00531 /// almost-empty BB ending in an unconditional branch to Succ, into Succ.
00532 ///
00533 /// Assumption: Succ is the single successor for BB.
00534 ///
00535 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
00536   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
00537 
00538   DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
00539         << Succ->getName() << "\n");
00540   // Shortcut, if there is only a single predecessor it must be BB and merging
00541   // is always safe
00542   if (Succ->getSinglePredecessor()) return true;
00543 
00544   // Make a list of the predecessors of BB
00545   SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));
00546 
00547   // Look at all the phi nodes in Succ, to see if they present a conflict when
00548   // merging these blocks
00549   for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
00550     PHINode *PN = cast<PHINode>(I);
00551 
00552     // If the incoming value from BB is again a PHINode in
00553     // BB which has the same incoming value for *PI as PN does, we can
00554     // merge the phi nodes and then the blocks can still be merged
00555     PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
00556     if (BBPN && BBPN->getParent() == BB) {
00557       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
00558         BasicBlock *IBB = PN->getIncomingBlock(PI);
00559         if (BBPreds.count(IBB) &&
00560             !CanMergeValues(BBPN->getIncomingValueForBlock(IBB),
00561                             PN->getIncomingValue(PI))) {
00562           DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
00563                 << Succ->getName() << " is conflicting with "
00564                 << BBPN->getName() << " with regard to common predecessor "
00565                 << IBB->getName() << "\n");
00566           return false;
00567         }
00568       }
00569     } else {
00570       Value* Val = PN->getIncomingValueForBlock(BB);
00571       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
00572         // See if the incoming value for the common predecessor is equal to the
00573         // one for BB, in which case this phi node will not prevent the merging
00574         // of the block.
00575         BasicBlock *IBB = PN->getIncomingBlock(PI);
00576         if (BBPreds.count(IBB) &&
00577             !CanMergeValues(Val, PN->getIncomingValue(PI))) {
00578           DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
00579                 << Succ->getName() << " is conflicting with regard to common "
00580                 << "predecessor " << IBB->getName() << "\n");
00581           return false;
00582         }
00583       }
00584     }
00585   }
00586 
00587   return true;
00588 }
00589 
00590 typedef SmallVector<BasicBlock *, 16> PredBlockVector;
00591 typedef DenseMap<BasicBlock *, Value *> IncomingValueMap;
00592 
00593 /// \brief Determines the value to use as the phi node input for a block.
00594 ///
00595 /// Select between \p OldVal any value that we know flows from \p BB
00596 /// to a particular phi on the basis of which one (if either) is not
00597 /// undef. Update IncomingValues based on the selected value.
00598 ///
00599 /// \param OldVal The value we are considering selecting.
00600 /// \param BB The block that the value flows in from.
00601 /// \param IncomingValues A map from block-to-value for other phi inputs
00602 /// that we have examined.
00603 ///
00604 /// \returns the selected value.
00605 static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB,
00606                                           IncomingValueMap &IncomingValues) {
00607   if (!isa<UndefValue>(OldVal)) {
00608     assert((!IncomingValues.count(BB) ||
00609             IncomingValues.find(BB)->second == OldVal) &&
00610            "Expected OldVal to match incoming value from BB!");
00611 
00612     IncomingValues.insert(std::make_pair(BB, OldVal));
00613     return OldVal;
00614   }
00615 
00616   IncomingValueMap::const_iterator It = IncomingValues.find(BB);
00617   if (It != IncomingValues.end()) return It->second;
00618 
00619   return OldVal;
00620 }
00621 
00622 /// \brief Create a map from block to value for the operands of a
00623 /// given phi.
00624 ///
00625 /// Create a map from block to value for each non-undef value flowing
00626 /// into \p PN.
00627 ///
00628 /// \param PN The phi we are collecting the map for.
00629 /// \param IncomingValues [out] The map from block to value for this phi.
00630 static void gatherIncomingValuesToPhi(PHINode *PN,
00631                                       IncomingValueMap &IncomingValues) {
00632   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00633     BasicBlock *BB = PN->getIncomingBlock(i);
00634     Value *V = PN->getIncomingValue(i);
00635 
00636     if (!isa<UndefValue>(V))
00637       IncomingValues.insert(std::make_pair(BB, V));
00638   }
00639 }
00640 
00641 /// \brief Replace the incoming undef values to a phi with the values
00642 /// from a block-to-value map.
00643 ///
00644 /// \param PN The phi we are replacing the undefs in.
00645 /// \param IncomingValues A map from block to value.
00646 static void replaceUndefValuesInPhi(PHINode *PN,
00647                                     const IncomingValueMap &IncomingValues) {
00648   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00649     Value *V = PN->getIncomingValue(i);
00650 
00651     if (!isa<UndefValue>(V)) continue;
00652 
00653     BasicBlock *BB = PN->getIncomingBlock(i);
00654     IncomingValueMap::const_iterator It = IncomingValues.find(BB);
00655     if (It == IncomingValues.end()) continue;
00656 
00657     PN->setIncomingValue(i, It->second);
00658   }
00659 }
00660 
00661 /// \brief Replace a value flowing from a block to a phi with
00662 /// potentially multiple instances of that value flowing from the
00663 /// block's predecessors to the phi.
00664 ///
00665 /// \param BB The block with the value flowing into the phi.
00666 /// \param BBPreds The predecessors of BB.
00667 /// \param PN The phi that we are updating.
00668 static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
00669                                                 const PredBlockVector &BBPreds,
00670                                                 PHINode *PN) {
00671   Value *OldVal = PN->removeIncomingValue(BB, false);
00672   assert(OldVal && "No entry in PHI for Pred BB!");
00673 
00674   IncomingValueMap IncomingValues;
00675 
00676   // We are merging two blocks - BB, and the block containing PN - and
00677   // as a result we need to redirect edges from the predecessors of BB
00678   // to go to the block containing PN, and update PN
00679   // accordingly. Since we allow merging blocks in the case where the
00680   // predecessor and successor blocks both share some predecessors,
00681   // and where some of those common predecessors might have undef
00682   // values flowing into PN, we want to rewrite those values to be
00683   // consistent with the non-undef values.
00684 
00685   gatherIncomingValuesToPhi(PN, IncomingValues);
00686 
00687   // If this incoming value is one of the PHI nodes in BB, the new entries
00688   // in the PHI node are the entries from the old PHI.
00689   if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
00690     PHINode *OldValPN = cast<PHINode>(OldVal);
00691     for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
00692       // Note that, since we are merging phi nodes and BB and Succ might
00693       // have common predecessors, we could end up with a phi node with
00694       // identical incoming branches. This will be cleaned up later (and
00695       // will trigger asserts if we try to clean it up now, without also
00696       // simplifying the corresponding conditional branch).
00697       BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
00698       Value *PredVal = OldValPN->getIncomingValue(i);
00699       Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
00700                                                     IncomingValues);
00701 
00702       // And add a new incoming value for this predecessor for the
00703       // newly retargeted branch.
00704       PN->addIncoming(Selected, PredBB);
00705     }
00706   } else {
00707     for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
00708       // Update existing incoming values in PN for this
00709       // predecessor of BB.
00710       BasicBlock *PredBB = BBPreds[i];
00711       Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
00712                                                     IncomingValues);
00713 
00714       // And add a new incoming value for this predecessor for the
00715       // newly retargeted branch.
00716       PN->addIncoming(Selected, PredBB);
00717     }
00718   }
00719 
00720   replaceUndefValuesInPhi(PN, IncomingValues);
00721 }
00722 
00723 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
00724 /// unconditional branch, and contains no instructions other than PHI nodes,
00725 /// potential side-effect free intrinsics and the branch.  If possible,
00726 /// eliminate BB by rewriting all the predecessors to branch to the successor
00727 /// block and return true.  If we can't transform, return false.
00728 bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) {
00729   assert(BB != &BB->getParent()->getEntryBlock() &&
00730          "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
00731 
00732   // We can't eliminate infinite loops.
00733   BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
00734   if (BB == Succ) return false;
00735 
00736   // Check to see if merging these blocks would cause conflicts for any of the
00737   // phi nodes in BB or Succ. If not, we can safely merge.
00738   if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
00739 
00740   // Check for cases where Succ has multiple predecessors and a PHI node in BB
00741   // has uses which will not disappear when the PHI nodes are merged.  It is
00742   // possible to handle such cases, but difficult: it requires checking whether
00743   // BB dominates Succ, which is non-trivial to calculate in the case where
00744   // Succ has multiple predecessors.  Also, it requires checking whether
00745   // constructing the necessary self-referential PHI node doesn't introduce any
00746   // conflicts; this isn't too difficult, but the previous code for doing this
00747   // was incorrect.
00748   //
00749   // Note that if this check finds a live use, BB dominates Succ, so BB is
00750   // something like a loop pre-header (or rarely, a part of an irreducible CFG);
00751   // folding the branch isn't profitable in that case anyway.
00752   if (!Succ->getSinglePredecessor()) {
00753     BasicBlock::iterator BBI = BB->begin();
00754     while (isa<PHINode>(*BBI)) {
00755       for (Use &U : BBI->uses()) {
00756         if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
00757           if (PN->getIncomingBlock(U) != BB)
00758             return false;
00759         } else {
00760           return false;
00761         }
00762       }
00763       ++BBI;
00764     }
00765   }
00766 
00767   DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
00768 
00769   if (isa<PHINode>(Succ->begin())) {
00770     // If there is more than one pred of succ, and there are PHI nodes in
00771     // the successor, then we need to add incoming edges for the PHI nodes
00772     //
00773     const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
00774 
00775     // Loop over all of the PHI nodes in the successor of BB.
00776     for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
00777       PHINode *PN = cast<PHINode>(I);
00778 
00779       redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
00780     }
00781   }
00782 
00783   if (Succ->getSinglePredecessor()) {
00784     // BB is the only predecessor of Succ, so Succ will end up with exactly
00785     // the same predecessors BB had.
00786 
00787     // Copy over any phi, debug or lifetime instruction.
00788     BB->getTerminator()->eraseFromParent();
00789     Succ->getInstList().splice(Succ->getFirstNonPHI(), BB->getInstList());
00790   } else {
00791     while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
00792       // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
00793       assert(PN->use_empty() && "There shouldn't be any uses here!");
00794       PN->eraseFromParent();
00795     }
00796   }
00797 
00798   // Everything that jumped to BB now goes to Succ.
00799   BB->replaceAllUsesWith(Succ);
00800   if (!Succ->hasName()) Succ->takeName(BB);
00801   BB->eraseFromParent();              // Delete the old basic block.
00802   return true;
00803 }
00804 
00805 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
00806 /// nodes in this block. This doesn't try to be clever about PHI nodes
00807 /// which differ only in the order of the incoming values, but instcombine
00808 /// orders them so it usually won't matter.
00809 ///
00810 bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
00811   bool Changed = false;
00812 
00813   // This implementation doesn't currently consider undef operands
00814   // specially. Theoretically, two phis which are identical except for
00815   // one having an undef where the other doesn't could be collapsed.
00816 
00817   // Map from PHI hash values to PHI nodes. If multiple PHIs have
00818   // the same hash value, the element is the first PHI in the
00819   // linked list in CollisionMap.
00820   DenseMap<uintptr_t, PHINode *> HashMap;
00821 
00822   // Maintain linked lists of PHI nodes with common hash values.
00823   DenseMap<PHINode *, PHINode *> CollisionMap;
00824 
00825   // Examine each PHI.
00826   for (BasicBlock::iterator I = BB->begin();
00827        PHINode *PN = dyn_cast<PHINode>(I++); ) {
00828     // Compute a hash value on the operands. Instcombine will likely have sorted
00829     // them, which helps expose duplicates, but we have to check all the
00830     // operands to be safe in case instcombine hasn't run.
00831     uintptr_t Hash = 0;
00832     // This hash algorithm is quite weak as hash functions go, but it seems
00833     // to do a good enough job for this particular purpose, and is very quick.
00834     for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) {
00835       Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I));
00836       Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7));
00837     }
00838     for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end();
00839          I != E; ++I) {
00840       Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I));
00841       Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7));
00842     }
00843     // Avoid colliding with the DenseMap sentinels ~0 and ~0-1.
00844     Hash >>= 1;
00845     // If we've never seen this hash value before, it's a unique PHI.
00846     std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair =
00847       HashMap.insert(std::make_pair(Hash, PN));
00848     if (Pair.second) continue;
00849     // Otherwise it's either a duplicate or a hash collision.
00850     for (PHINode *OtherPN = Pair.first->second; ; ) {
00851       if (OtherPN->isIdenticalTo(PN)) {
00852         // A duplicate. Replace this PHI with its duplicate.
00853         PN->replaceAllUsesWith(OtherPN);
00854         PN->eraseFromParent();
00855         Changed = true;
00856         break;
00857       }
00858       // A non-duplicate hash collision.
00859       DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN);
00860       if (I == CollisionMap.end()) {
00861         // Set this PHI to be the head of the linked list of colliding PHIs.
00862         PHINode *Old = Pair.first->second;
00863         Pair.first->second = PN;
00864         CollisionMap[PN] = Old;
00865         break;
00866       }
00867       // Proceed to the next PHI in the list.
00868       OtherPN = I->second;
00869     }
00870   }
00871 
00872   return Changed;
00873 }
00874 
00875 /// enforceKnownAlignment - If the specified pointer points to an object that
00876 /// we control, modify the object's alignment to PrefAlign. This isn't
00877 /// often possible though. If alignment is important, a more reliable approach
00878 /// is to simply align all global variables and allocation instructions to
00879 /// their preferred alignment from the beginning.
00880 ///
00881 static unsigned enforceKnownAlignment(Value *V, unsigned Align,
00882                                       unsigned PrefAlign, const DataLayout *TD) {
00883   V = V->stripPointerCasts();
00884 
00885   if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
00886     // If the preferred alignment is greater than the natural stack alignment
00887     // then don't round up. This avoids dynamic stack realignment.
00888     if (TD && TD->exceedsNaturalStackAlignment(PrefAlign))
00889       return Align;
00890     // If there is a requested alignment and if this is an alloca, round up.
00891     if (AI->getAlignment() >= PrefAlign)
00892       return AI->getAlignment();
00893     AI->setAlignment(PrefAlign);
00894     return PrefAlign;
00895   }
00896 
00897   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
00898     // If there is a large requested alignment and we can, bump up the alignment
00899     // of the global.
00900     if (GV->isDeclaration()) return Align;
00901     // If the memory we set aside for the global may not be the memory used by
00902     // the final program then it is impossible for us to reliably enforce the
00903     // preferred alignment.
00904     if (GV->isWeakForLinker()) return Align;
00905 
00906     if (GV->getAlignment() >= PrefAlign)
00907       return GV->getAlignment();
00908     // We can only increase the alignment of the global if it has no alignment
00909     // specified or if it is not assigned a section.  If it is assigned a
00910     // section, the global could be densely packed with other objects in the
00911     // section, increasing the alignment could cause padding issues.
00912     if (!GV->hasSection() || GV->getAlignment() == 0)
00913       GV->setAlignment(PrefAlign);
00914     return GV->getAlignment();
00915   }
00916 
00917   return Align;
00918 }
00919 
00920 /// getOrEnforceKnownAlignment - If the specified pointer has an alignment that
00921 /// we can determine, return it, otherwise return 0.  If PrefAlign is specified,
00922 /// and it is more than the alignment of the ultimate object, see if we can
00923 /// increase the alignment of the ultimate object, making this check succeed.
00924 unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
00925                                           const DataLayout *DL) {
00926   assert(V->getType()->isPointerTy() &&
00927          "getOrEnforceKnownAlignment expects a pointer!");
00928   unsigned BitWidth = DL ? DL->getPointerTypeSizeInBits(V->getType()) : 64;
00929 
00930   APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
00931   ComputeMaskedBits(V, KnownZero, KnownOne, DL);
00932   unsigned TrailZ = KnownZero.countTrailingOnes();
00933 
00934   // Avoid trouble with ridiculously large TrailZ values, such as
00935   // those computed from a null pointer.
00936   TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1));
00937 
00938   unsigned Align = 1u << std::min(BitWidth - 1, TrailZ);
00939 
00940   // LLVM doesn't support alignments larger than this currently.
00941   Align = std::min(Align, +Value::MaximumAlignment);
00942 
00943   if (PrefAlign > Align)
00944     Align = enforceKnownAlignment(V, Align, PrefAlign, DL);
00945 
00946   // We don't need to make any adjustment.
00947   return Align;
00948 }
00949 
00950 ///===---------------------------------------------------------------------===//
00951 ///  Dbg Intrinsic utilities
00952 ///
00953 
00954 /// See if there is a dbg.value intrinsic for DIVar before I.
00955 static bool LdStHasDebugValue(DIVariable &DIVar, Instruction *I) {
00956   // Since we can't guarantee that the original dbg.declare instrinsic
00957   // is removed by LowerDbgDeclare(), we need to make sure that we are
00958   // not inserting the same dbg.value intrinsic over and over.
00959   llvm::BasicBlock::InstListType::iterator PrevI(I);
00960   if (PrevI != I->getParent()->getInstList().begin()) {
00961     --PrevI;
00962     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI))
00963       if (DVI->getValue() == I->getOperand(0) &&
00964           DVI->getOffset() == 0 &&
00965           DVI->getVariable() == DIVar)
00966         return true;
00967   }
00968   return false;
00969 }
00970 
00971 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
00972 /// that has an associated llvm.dbg.decl intrinsic.
00973 bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
00974                                            StoreInst *SI, DIBuilder &Builder) {
00975   DIVariable DIVar(DDI->getVariable());
00976   assert((!DIVar || DIVar.isVariable()) &&
00977          "Variable in DbgDeclareInst should be either null or a DIVariable.");
00978   if (!DIVar)
00979     return false;
00980 
00981   if (LdStHasDebugValue(DIVar, SI))
00982     return true;
00983 
00984   Instruction *DbgVal = NULL;
00985   // If an argument is zero extended then use argument directly. The ZExt
00986   // may be zapped by an optimization pass in future.
00987   Argument *ExtendedArg = NULL;
00988   if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0)))
00989     ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0));
00990   if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0)))
00991     ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0));
00992   if (ExtendedArg)
00993     DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, SI);
00994   else
00995     DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, SI);
00996 
00997   // Propagate any debug metadata from the store onto the dbg.value.
00998   DebugLoc SIDL = SI->getDebugLoc();
00999   if (!SIDL.isUnknown())
01000     DbgVal->setDebugLoc(SIDL);
01001   // Otherwise propagate debug metadata from dbg.declare.
01002   else
01003     DbgVal->setDebugLoc(DDI->getDebugLoc());
01004   return true;
01005 }
01006 
01007 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
01008 /// that has an associated llvm.dbg.decl intrinsic.
01009 bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
01010                                            LoadInst *LI, DIBuilder &Builder) {
01011   DIVariable DIVar(DDI->getVariable());
01012   assert((!DIVar || DIVar.isVariable()) &&
01013          "Variable in DbgDeclareInst should be either null or a DIVariable.");
01014   if (!DIVar)
01015     return false;
01016 
01017   if (LdStHasDebugValue(DIVar, LI))
01018     return true;
01019 
01020   Instruction *DbgVal =
01021     Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0,
01022                                     DIVar, LI);
01023 
01024   // Propagate any debug metadata from the store onto the dbg.value.
01025   DebugLoc LIDL = LI->getDebugLoc();
01026   if (!LIDL.isUnknown())
01027     DbgVal->setDebugLoc(LIDL);
01028   // Otherwise propagate debug metadata from dbg.declare.
01029   else
01030     DbgVal->setDebugLoc(DDI->getDebugLoc());
01031   return true;
01032 }
01033 
01034 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
01035 /// of llvm.dbg.value intrinsics.
01036 bool llvm::LowerDbgDeclare(Function &F) {
01037   DIBuilder DIB(*F.getParent());
01038   SmallVector<DbgDeclareInst *, 4> Dbgs;
01039   for (auto &FI : F)
01040     for (BasicBlock::iterator BI : FI)
01041       if (auto DDI = dyn_cast<DbgDeclareInst>(BI))
01042         Dbgs.push_back(DDI);
01043 
01044   if (Dbgs.empty())
01045     return false;
01046 
01047   for (auto &I : Dbgs) {
01048     DbgDeclareInst *DDI = I;
01049     AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
01050     // If this is an alloca for a scalar variable, insert a dbg.value
01051     // at each load and store to the alloca and erase the dbg.declare.
01052     if (AI && !AI->isArrayAllocation()) {
01053 
01054       // We only remove the dbg.declare intrinsic if all uses are
01055       // converted to dbg.value intrinsics.
01056       bool RemoveDDI = true;
01057       for (User *U : AI->users())
01058         if (StoreInst *SI = dyn_cast<StoreInst>(U))
01059           ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
01060         else if (LoadInst *LI = dyn_cast<LoadInst>(U))
01061           ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
01062         else
01063           RemoveDDI = false;
01064       if (RemoveDDI)
01065         DDI->eraseFromParent();
01066     }
01067   }
01068   return true;
01069 }
01070 
01071 /// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the
01072 /// alloca 'V', if any.
01073 DbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) {
01074   if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), V))
01075     for (User *U : DebugNode->users())
01076       if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U))
01077         return DDI;
01078 
01079   return 0;
01080 }
01081 
01082 bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
01083                                       DIBuilder &Builder) {
01084   DbgDeclareInst *DDI = FindAllocaDbgDeclare(AI);
01085   if (!DDI)
01086     return false;
01087   DIVariable DIVar(DDI->getVariable());
01088   assert((!DIVar || DIVar.isVariable()) &&
01089          "Variable in DbgDeclareInst should be either null or a DIVariable.");
01090   if (!DIVar)
01091     return false;
01092 
01093   // Create a copy of the original DIDescriptor for user variable, appending
01094   // "deref" operation to a list of address elements, as new llvm.dbg.declare
01095   // will take a value storing address of the memory for variable, not
01096   // alloca itself.
01097   Type *Int64Ty = Type::getInt64Ty(AI->getContext());
01098   SmallVector<Value*, 4> NewDIVarAddress;
01099   if (DIVar.hasComplexAddress()) {
01100     for (unsigned i = 0, n = DIVar.getNumAddrElements(); i < n; ++i) {
01101       NewDIVarAddress.push_back(
01102           ConstantInt::get(Int64Ty, DIVar.getAddrElement(i)));
01103     }
01104   }
01105   NewDIVarAddress.push_back(ConstantInt::get(Int64Ty, DIBuilder::OpDeref));
01106   DIVariable NewDIVar = Builder.createComplexVariable(
01107       DIVar.getTag(), DIVar.getContext(), DIVar.getName(),
01108       DIVar.getFile(), DIVar.getLineNumber(), DIVar.getType(),
01109       NewDIVarAddress, DIVar.getArgNumber());
01110 
01111   // Insert llvm.dbg.declare in the same basic block as the original alloca,
01112   // and remove old llvm.dbg.declare.
01113   BasicBlock *BB = AI->getParent();
01114   Builder.insertDeclare(NewAllocaAddress, NewDIVar, BB);
01115   DDI->eraseFromParent();
01116   return true;
01117 }
01118 
01119 /// changeToUnreachable - Insert an unreachable instruction before the specified
01120 /// instruction, making it and the rest of the code in the block dead.
01121 static void changeToUnreachable(Instruction *I, bool UseLLVMTrap) {
01122   BasicBlock *BB = I->getParent();
01123   // Loop over all of the successors, removing BB's entry from any PHI
01124   // nodes.
01125   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
01126     (*SI)->removePredecessor(BB);
01127 
01128   // Insert a call to llvm.trap right before this.  This turns the undefined
01129   // behavior into a hard fail instead of falling through into random code.
01130   if (UseLLVMTrap) {
01131     Function *TrapFn =
01132       Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
01133     CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
01134     CallTrap->setDebugLoc(I->getDebugLoc());
01135   }
01136   new UnreachableInst(I->getContext(), I);
01137 
01138   // All instructions after this are dead.
01139   BasicBlock::iterator BBI = I, BBE = BB->end();
01140   while (BBI != BBE) {
01141     if (!BBI->use_empty())
01142       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
01143     BB->getInstList().erase(BBI++);
01144   }
01145 }
01146 
01147 /// changeToCall - Convert the specified invoke into a normal call.
01148 static void changeToCall(InvokeInst *II) {
01149   SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
01150   CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, "", II);
01151   NewCall->takeName(II);
01152   NewCall->setCallingConv(II->getCallingConv());
01153   NewCall->setAttributes(II->getAttributes());
01154   NewCall->setDebugLoc(II->getDebugLoc());
01155   II->replaceAllUsesWith(NewCall);
01156 
01157   // Follow the call by a branch to the normal destination.
01158   BranchInst::Create(II->getNormalDest(), II);
01159 
01160   // Update PHI nodes in the unwind destination
01161   II->getUnwindDest()->removePredecessor(II->getParent());
01162   II->eraseFromParent();
01163 }
01164 
01165 static bool markAliveBlocks(BasicBlock *BB,
01166                             SmallPtrSet<BasicBlock*, 128> &Reachable) {
01167 
01168   SmallVector<BasicBlock*, 128> Worklist;
01169   Worklist.push_back(BB);
01170   Reachable.insert(BB);
01171   bool Changed = false;
01172   do {
01173     BB = Worklist.pop_back_val();
01174 
01175     // Do a quick scan of the basic block, turning any obviously unreachable
01176     // instructions into LLVM unreachable insts.  The instruction combining pass
01177     // canonicalizes unreachable insts into stores to null or undef.
01178     for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){
01179       if (CallInst *CI = dyn_cast<CallInst>(BBI)) {
01180         if (CI->doesNotReturn()) {
01181           // If we found a call to a no-return function, insert an unreachable
01182           // instruction after it.  Make sure there isn't *already* one there
01183           // though.
01184           ++BBI;
01185           if (!isa<UnreachableInst>(BBI)) {
01186             // Don't insert a call to llvm.trap right before the unreachable.
01187             changeToUnreachable(BBI, false);
01188             Changed = true;
01189           }
01190           break;
01191         }
01192       }
01193 
01194       // Store to undef and store to null are undefined and used to signal that
01195       // they should be changed to unreachable by passes that can't modify the
01196       // CFG.
01197       if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
01198         // Don't touch volatile stores.
01199         if (SI->isVolatile()) continue;
01200 
01201         Value *Ptr = SI->getOperand(1);
01202 
01203         if (isa<UndefValue>(Ptr) ||
01204             (isa<ConstantPointerNull>(Ptr) &&
01205              SI->getPointerAddressSpace() == 0)) {
01206           changeToUnreachable(SI, true);
01207           Changed = true;
01208           break;
01209         }
01210       }
01211     }
01212 
01213     // Turn invokes that call 'nounwind' functions into ordinary calls.
01214     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
01215       Value *Callee = II->getCalledValue();
01216       if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
01217         changeToUnreachable(II, true);
01218         Changed = true;
01219       } else if (II->doesNotThrow()) {
01220         if (II->use_empty() && II->onlyReadsMemory()) {
01221           // jump to the normal destination branch.
01222           BranchInst::Create(II->getNormalDest(), II);
01223           II->getUnwindDest()->removePredecessor(II->getParent());
01224           II->eraseFromParent();
01225         } else
01226           changeToCall(II);
01227         Changed = true;
01228       }
01229     }
01230 
01231     Changed |= ConstantFoldTerminator(BB, true);
01232     for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
01233       if (Reachable.insert(*SI))
01234         Worklist.push_back(*SI);
01235   } while (!Worklist.empty());
01236   return Changed;
01237 }
01238 
01239 /// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even
01240 /// if they are in a dead cycle.  Return true if a change was made, false
01241 /// otherwise.
01242 bool llvm::removeUnreachableBlocks(Function &F) {
01243   SmallPtrSet<BasicBlock*, 128> Reachable;
01244   bool Changed = markAliveBlocks(F.begin(), Reachable);
01245 
01246   // If there are unreachable blocks in the CFG...
01247   if (Reachable.size() == F.size())
01248     return Changed;
01249 
01250   assert(Reachable.size() < F.size());
01251   NumRemoved += F.size()-Reachable.size();
01252 
01253   // Loop over all of the basic blocks that are not reachable, dropping all of
01254   // their internal references...
01255   for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
01256     if (Reachable.count(BB))
01257       continue;
01258 
01259     for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
01260       if (Reachable.count(*SI))
01261         (*SI)->removePredecessor(BB);
01262     BB->dropAllReferences();
01263   }
01264 
01265   for (Function::iterator I = ++F.begin(); I != F.end();)
01266     if (!Reachable.count(I))
01267       I = F.getBasicBlockList().erase(I);
01268     else
01269       ++I;
01270 
01271   return true;
01272 }