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