Unbreak the gdb buildbot by not lowering dbg.declare intrinsics for arrays.
[opencl/llvm.git] / lib / Transforms / Utils / Local.cpp
1 //===-- Local.cpp - Functions to perform local transformations ------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This family of functions perform various local transformations to the
11 // program.
12 //
13 //===----------------------------------------------------------------------===//
15 #include "llvm/Transforms/Utils/Local.h"
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/STLExtras.h"
18 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/InstructionSimplify.h"
21 #include "llvm/Analysis/MemoryBuiltins.h"
22 #include "llvm/Analysis/ValueTracking.h"
23 #include "llvm/IR/CFG.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DIBuilder.h"
26 #include "llvm/IR/DataLayout.h"
27 #include "llvm/IR/DebugInfo.h"
28 #include "llvm/IR/DerivedTypes.h"
29 #include "llvm/IR/Dominators.h"
30 #include "llvm/IR/GetElementPtrTypeIterator.h"
31 #include "llvm/IR/GlobalAlias.h"
32 #include "llvm/IR/GlobalVariable.h"
33 #include "llvm/IR/IRBuilder.h"
34 #include "llvm/IR/Instructions.h"
35 #include "llvm/IR/IntrinsicInst.h"
36 #include "llvm/IR/Intrinsics.h"
37 #include "llvm/IR/MDBuilder.h"
38 #include "llvm/IR/Metadata.h"
39 #include "llvm/IR/Operator.h"
40 #include "llvm/IR/ValueHandle.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Support/MathExtras.h"
43 #include "llvm/Support/raw_ostream.h"
44 using namespace llvm;
46 #define DEBUG_TYPE "local"
48 STATISTIC(NumRemoved, "Number of unreachable basic blocks removed");
50 //===----------------------------------------------------------------------===//
51 //  Local constant propagation.
52 //
54 /// ConstantFoldTerminator - If a terminator instruction is predicated on a
55 /// constant value, convert it into an unconditional branch to the constant
56 /// destination.  This is a nontrivial operation because the successors of this
57 /// basic block must have their PHI nodes updated.
58 /// Also calls RecursivelyDeleteTriviallyDeadInstructions() on any branch/switch
59 /// conditions and indirectbr addresses this might make dead if
60 /// DeleteDeadConditions is true.
61 bool llvm::ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions,
62                                   const TargetLibraryInfo *TLI) {
63   TerminatorInst *T = BB->getTerminator();
64   IRBuilder<> Builder(T);
66   // Branch - See if we are conditional jumping on constant
67   if (BranchInst *BI = dyn_cast<BranchInst>(T)) {
68     if (BI->isUnconditional()) return false;  // Can't optimize uncond branch
69     BasicBlock *Dest1 = BI->getSuccessor(0);
70     BasicBlock *Dest2 = BI->getSuccessor(1);
72     if (ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition())) {
73       // Are we branching on constant?
74       // YES.  Change to unconditional branch...
75       BasicBlock *Destination = Cond->getZExtValue() ? Dest1 : Dest2;
76       BasicBlock *OldDest     = Cond->getZExtValue() ? Dest2 : Dest1;
78       //cerr << "Function: " << T->getParent()->getParent()
79       //     << "\nRemoving branch from " << T->getParent()
80       //     << "\n\nTo: " << OldDest << endl;
82       // Let the basic block know that we are letting go of it.  Based on this,
83       // it will adjust it's PHI nodes.
84       OldDest->removePredecessor(BB);
86       // Replace the conditional branch with an unconditional one.
87       Builder.CreateBr(Destination);
88       BI->eraseFromParent();
89       return true;
90     }
92     if (Dest2 == Dest1) {       // Conditional branch to same location?
93       // This branch matches something like this:
94       //     br bool %cond, label %Dest, label %Dest
95       // and changes it into:  br label %Dest
97       // Let the basic block know that we are letting go of one copy of it.
98       assert(BI->getParent() && "Terminator not inserted in block!");
99       Dest1->removePredecessor(BI->getParent());
101       // Replace the conditional branch with an unconditional one.
102       Builder.CreateBr(Dest1);
103       Value *Cond = BI->getCondition();
104       BI->eraseFromParent();
105       if (DeleteDeadConditions)
106         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
107       return true;
108     }
109     return false;
110   }
112   if (SwitchInst *SI = dyn_cast<SwitchInst>(T)) {
113     // If we are switching on a constant, we can convert the switch into a
114     // single branch instruction!
115     ConstantInt *CI = dyn_cast<ConstantInt>(SI->getCondition());
116     BasicBlock *TheOnlyDest = SI->getDefaultDest();
117     BasicBlock *DefaultDest = TheOnlyDest;
119     // Figure out which case it goes to.
120     for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end();
121          i != e; ++i) {
122       // Found case matching a constant operand?
123       if (i.getCaseValue() == CI) {
124         TheOnlyDest = i.getCaseSuccessor();
125         break;
126       }
128       // Check to see if this branch is going to the same place as the default
129       // dest.  If so, eliminate it as an explicit compare.
130       if (i.getCaseSuccessor() == DefaultDest) {
131         MDNode* MD = SI->getMetadata(LLVMContext::MD_prof);
132         unsigned NCases = SI->getNumCases();
133         // Fold the case metadata into the default if there will be any branches
134         // left, unless the metadata doesn't match the switch.
135         if (NCases > 1 && MD && MD->getNumOperands() == 2 + NCases) {
136           // Collect branch weights into a vector.
137           SmallVector<uint32_t, 8> Weights;
138           for (unsigned MD_i = 1, MD_e = MD->getNumOperands(); MD_i < MD_e;
139                ++MD_i) {
140             ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(MD_i));
141             assert(CI);
142             Weights.push_back(CI->getValue().getZExtValue());
143           }
144           // Merge weight of this case to the default weight.
145           unsigned idx = i.getCaseIndex();
146           Weights[0] += Weights[idx+1];
147           // Remove weight for this case.
148           std::swap(Weights[idx+1], Weights.back());
149           Weights.pop_back();
150           SI->setMetadata(LLVMContext::MD_prof,
151                           MDBuilder(BB->getContext()).
152                           createBranchWeights(Weights));
153         }
154         // Remove this entry.
155         DefaultDest->removePredecessor(SI->getParent());
156         SI->removeCase(i);
157         --i; --e;
158         continue;
159       }
161       // Otherwise, check to see if the switch only branches to one destination.
162       // We do this by reseting "TheOnlyDest" to null when we find two non-equal
163       // destinations.
164       if (i.getCaseSuccessor() != TheOnlyDest) TheOnlyDest = nullptr;
165     }
167     if (CI && !TheOnlyDest) {
168       // Branching on a constant, but not any of the cases, go to the default
169       // successor.
170       TheOnlyDest = SI->getDefaultDest();
171     }
173     // If we found a single destination that we can fold the switch into, do so
174     // now.
175     if (TheOnlyDest) {
176       // Insert the new branch.
177       Builder.CreateBr(TheOnlyDest);
178       BasicBlock *BB = SI->getParent();
180       // Remove entries from PHI nodes which we no longer branch to...
181       for (unsigned i = 0, e = SI->getNumSuccessors(); i != e; ++i) {
182         // Found case matching a constant operand?
183         BasicBlock *Succ = SI->getSuccessor(i);
184         if (Succ == TheOnlyDest)
185           TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
186         else
187           Succ->removePredecessor(BB);
188       }
190       // Delete the old switch.
191       Value *Cond = SI->getCondition();
192       SI->eraseFromParent();
193       if (DeleteDeadConditions)
194         RecursivelyDeleteTriviallyDeadInstructions(Cond, TLI);
195       return true;
196     }
198     if (SI->getNumCases() == 1) {
199       // Otherwise, we can fold this switch into a conditional branch
200       // instruction if it has only one non-default destination.
201       SwitchInst::CaseIt FirstCase = SI->case_begin();
202       Value *Cond = Builder.CreateICmpEQ(SI->getCondition(),
203           FirstCase.getCaseValue(), "cond");
205       // Insert the new branch.
206       BranchInst *NewBr = Builder.CreateCondBr(Cond,
207                                                FirstCase.getCaseSuccessor(),
208                                                SI->getDefaultDest());
209       MDNode* MD = SI->getMetadata(LLVMContext::MD_prof);
210       if (MD && MD->getNumOperands() == 3) {
211         ConstantInt *SICase = dyn_cast<ConstantInt>(MD->getOperand(2));
212         ConstantInt *SIDef = dyn_cast<ConstantInt>(MD->getOperand(1));
213         assert(SICase && SIDef);
214         // The TrueWeight should be the weight for the single case of SI.
215         NewBr->setMetadata(LLVMContext::MD_prof,
216                         MDBuilder(BB->getContext()).
217                         createBranchWeights(SICase->getValue().getZExtValue(),
218                                             SIDef->getValue().getZExtValue()));
219       }
221       // Delete the old switch.
222       SI->eraseFromParent();
223       return true;
224     }
225     return false;
226   }
228   if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(T)) {
229     // indirectbr blockaddress(@F, @BB) -> br label @BB
230     if (BlockAddress *BA =
231           dyn_cast<BlockAddress>(IBI->getAddress()->stripPointerCasts())) {
232       BasicBlock *TheOnlyDest = BA->getBasicBlock();
233       // Insert the new branch.
234       Builder.CreateBr(TheOnlyDest);
236       for (unsigned i = 0, e = IBI->getNumDestinations(); i != e; ++i) {
237         if (IBI->getDestination(i) == TheOnlyDest)
238           TheOnlyDest = nullptr;
239         else
240           IBI->getDestination(i)->removePredecessor(IBI->getParent());
241       }
242       Value *Address = IBI->getAddress();
243       IBI->eraseFromParent();
244       if (DeleteDeadConditions)
245         RecursivelyDeleteTriviallyDeadInstructions(Address, TLI);
247       // If we didn't find our destination in the IBI successor list, then we
248       // have undefined behavior.  Replace the unconditional branch with an
249       // 'unreachable' instruction.
250       if (TheOnlyDest) {
251         BB->getTerminator()->eraseFromParent();
252         new UnreachableInst(BB->getContext(), BB);
253       }
255       return true;
256     }
257   }
259   return false;
263 //===----------------------------------------------------------------------===//
264 //  Local dead code elimination.
265 //
267 /// isInstructionTriviallyDead - Return true if the result produced by the
268 /// instruction is not used, and the instruction has no side effects.
269 ///
270 bool llvm::isInstructionTriviallyDead(Instruction *I,
271                                       const TargetLibraryInfo *TLI) {
272   if (!I->use_empty() || isa<TerminatorInst>(I)) return false;
274   // We don't want the landingpad instruction removed by anything this general.
275   if (isa<LandingPadInst>(I))
276     return false;
278   // We don't want debug info removed by anything this general, unless
279   // debug info is empty.
280   if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(I)) {
281     if (DDI->getAddress())
282       return false;
283     return true;
284   }
285   if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(I)) {
286     if (DVI->getValue())
287       return false;
288     return true;
289   }
291   if (!I->mayHaveSideEffects()) return true;
293   // Special case intrinsics that "may have side effects" but can be deleted
294   // when dead.
295   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
296     // Safe to delete llvm.stacksave if dead.
297     if (II->getIntrinsicID() == Intrinsic::stacksave)
298       return true;
300     // Lifetime intrinsics are dead when their right-hand is undef.
301     if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
302         II->getIntrinsicID() == Intrinsic::lifetime_end)
303       return isa<UndefValue>(II->getArgOperand(1));
304   }
306   if (isAllocLikeFn(I, TLI)) return true;
308   if (CallInst *CI = isFreeCall(I, TLI))
309     if (Constant *C = dyn_cast<Constant>(CI->getArgOperand(0)))
310       return C->isNullValue() || isa<UndefValue>(C);
312   return false;
315 /// RecursivelyDeleteTriviallyDeadInstructions - If the specified value is a
316 /// trivially dead instruction, delete it.  If that makes any of its operands
317 /// trivially dead, delete them too, recursively.  Return true if any
318 /// instructions were deleted.
319 bool
320 llvm::RecursivelyDeleteTriviallyDeadInstructions(Value *V,
321                                                  const TargetLibraryInfo *TLI) {
322   Instruction *I = dyn_cast<Instruction>(V);
323   if (!I || !I->use_empty() || !isInstructionTriviallyDead(I, TLI))
324     return false;
326   SmallVector<Instruction*, 16> DeadInsts;
327   DeadInsts.push_back(I);
329   do {
330     I = DeadInsts.pop_back_val();
332     // Null out all of the instruction's operands to see if any operand becomes
333     // dead as we go.
334     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
335       Value *OpV = I->getOperand(i);
336       I->setOperand(i, nullptr);
338       if (!OpV->use_empty()) continue;
340       // If the operand is an instruction that became dead as we nulled out the
341       // operand, and if it is 'trivially' dead, delete it in a future loop
342       // iteration.
343       if (Instruction *OpI = dyn_cast<Instruction>(OpV))
344         if (isInstructionTriviallyDead(OpI, TLI))
345           DeadInsts.push_back(OpI);
346     }
348     I->eraseFromParent();
349   } while (!DeadInsts.empty());
351   return true;
354 /// areAllUsesEqual - Check whether the uses of a value are all the same.
355 /// This is similar to Instruction::hasOneUse() except this will also return
356 /// true when there are no uses or multiple uses that all refer to the same
357 /// value.
358 static bool areAllUsesEqual(Instruction *I) {
359   Value::user_iterator UI = I->user_begin();
360   Value::user_iterator UE = I->user_end();
361   if (UI == UE)
362     return true;
364   User *TheUse = *UI;
365   for (++UI; UI != UE; ++UI) {
366     if (*UI != TheUse)
367       return false;
368   }
369   return true;
372 /// RecursivelyDeleteDeadPHINode - If the specified value is an effectively
373 /// dead PHI node, due to being a def-use chain of single-use nodes that
374 /// either forms a cycle or is terminated by a trivially dead instruction,
375 /// delete it.  If that makes any of its operands trivially dead, delete them
376 /// too, recursively.  Return true if a change was made.
377 bool llvm::RecursivelyDeleteDeadPHINode(PHINode *PN,
378                                         const TargetLibraryInfo *TLI) {
379   SmallPtrSet<Instruction*, 4> Visited;
380   for (Instruction *I = PN; areAllUsesEqual(I) && !I->mayHaveSideEffects();
381        I = cast<Instruction>(*I->user_begin())) {
382     if (I->use_empty())
383       return RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
385     // If we find an instruction more than once, we're on a cycle that
386     // won't prove fruitful.
387     if (!Visited.insert(I)) {
388       // Break the cycle and delete the instruction and its operands.
389       I->replaceAllUsesWith(UndefValue::get(I->getType()));
390       (void)RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
391       return true;
392     }
393   }
394   return false;
397 /// SimplifyInstructionsInBlock - Scan the specified basic block and try to
398 /// simplify any instructions in it and recursively delete dead instructions.
399 ///
400 /// This returns true if it changed the code, note that it can delete
401 /// instructions in other blocks as well in this block.
402 bool llvm::SimplifyInstructionsInBlock(BasicBlock *BB, const DataLayout *TD,
403                                        const TargetLibraryInfo *TLI) {
404   bool MadeChange = false;
406 #ifndef NDEBUG
407   // In debug builds, ensure that the terminator of the block is never replaced
408   // or deleted by these simplifications. The idea of simplification is that it
409   // cannot introduce new instructions, and there is no way to replace the
410   // terminator of a block without introducing a new instruction.
411   AssertingVH<Instruction> TerminatorVH(--BB->end());
412 #endif
414   for (BasicBlock::iterator BI = BB->begin(), E = --BB->end(); BI != E; ) {
415     assert(!BI->isTerminator());
416     Instruction *Inst = BI++;
418     WeakVH BIHandle(BI);
419     if (recursivelySimplifyInstruction(Inst, TD, TLI)) {
420       MadeChange = true;
421       if (BIHandle != BI)
422         BI = BB->begin();
423       continue;
424     }
426     MadeChange |= RecursivelyDeleteTriviallyDeadInstructions(Inst, TLI);
427     if (BIHandle != BI)
428       BI = BB->begin();
429   }
430   return MadeChange;
433 //===----------------------------------------------------------------------===//
434 //  Control Flow Graph Restructuring.
435 //
438 /// RemovePredecessorAndSimplify - Like BasicBlock::removePredecessor, this
439 /// method is called when we're about to delete Pred as a predecessor of BB.  If
440 /// BB contains any PHI nodes, this drops the entries in the PHI nodes for Pred.
441 ///
442 /// Unlike the removePredecessor method, this attempts to simplify uses of PHI
443 /// nodes that collapse into identity values.  For example, if we have:
444 ///   x = phi(1, 0, 0, 0)
445 ///   y = and x, z
446 ///
447 /// .. and delete the predecessor corresponding to the '1', this will attempt to
448 /// recursively fold the and to 0.
449 void llvm::RemovePredecessorAndSimplify(BasicBlock *BB, BasicBlock *Pred,
450                                         DataLayout *TD) {
451   // This only adjusts blocks with PHI nodes.
452   if (!isa<PHINode>(BB->begin()))
453     return;
455   // Remove the entries for Pred from the PHI nodes in BB, but do not simplify
456   // them down.  This will leave us with single entry phi nodes and other phis
457   // that can be removed.
458   BB->removePredecessor(Pred, true);
460   WeakVH PhiIt = &BB->front();
461   while (PHINode *PN = dyn_cast<PHINode>(PhiIt)) {
462     PhiIt = &*++BasicBlock::iterator(cast<Instruction>(PhiIt));
463     Value *OldPhiIt = PhiIt;
465     if (!recursivelySimplifyInstruction(PN, TD))
466       continue;
468     // If recursive simplification ended up deleting the next PHI node we would
469     // iterate to, then our iterator is invalid, restart scanning from the top
470     // of the block.
471     if (PhiIt != OldPhiIt) PhiIt = &BB->front();
472   }
476 /// MergeBasicBlockIntoOnlyPred - DestBB is a block with one predecessor and its
477 /// predecessor is known to have one successor (DestBB!).  Eliminate the edge
478 /// between them, moving the instructions in the predecessor into DestBB and
479 /// deleting the predecessor block.
480 ///
481 void llvm::MergeBasicBlockIntoOnlyPred(BasicBlock *DestBB, Pass *P) {
482   // If BB has single-entry PHI nodes, fold them.
483   while (PHINode *PN = dyn_cast<PHINode>(DestBB->begin())) {
484     Value *NewVal = PN->getIncomingValue(0);
485     // Replace self referencing PHI with undef, it must be dead.
486     if (NewVal == PN) NewVal = UndefValue::get(PN->getType());
487     PN->replaceAllUsesWith(NewVal);
488     PN->eraseFromParent();
489   }
491   BasicBlock *PredBB = DestBB->getSinglePredecessor();
492   assert(PredBB && "Block doesn't have a single predecessor!");
494   // Zap anything that took the address of DestBB.  Not doing this will give the
495   // address an invalid value.
496   if (DestBB->hasAddressTaken()) {
497     BlockAddress *BA = BlockAddress::get(DestBB);
498     Constant *Replacement =
499       ConstantInt::get(llvm::Type::getInt32Ty(BA->getContext()), 1);
500     BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
501                                                      BA->getType()));
502     BA->destroyConstant();
503   }
505   // Anything that branched to PredBB now branches to DestBB.
506   PredBB->replaceAllUsesWith(DestBB);
508   // Splice all the instructions from PredBB to DestBB.
509   PredBB->getTerminator()->eraseFromParent();
510   DestBB->getInstList().splice(DestBB->begin(), PredBB->getInstList());
512   if (P) {
513     if (DominatorTreeWrapperPass *DTWP =
514             P->getAnalysisIfAvailable<DominatorTreeWrapperPass>()) {
515       DominatorTree &DT = DTWP->getDomTree();
516       BasicBlock *PredBBIDom = DT.getNode(PredBB)->getIDom()->getBlock();
517       DT.changeImmediateDominator(DestBB, PredBBIDom);
518       DT.eraseNode(PredBB);
519     }
520   }
521   // Nuke BB.
522   PredBB->eraseFromParent();
525 /// CanMergeValues - Return true if we can choose one of these values to use
526 /// in place of the other. Note that we will always choose the non-undef
527 /// value to keep.
528 static bool CanMergeValues(Value *First, Value *Second) {
529   return First == Second || isa<UndefValue>(First) || isa<UndefValue>(Second);
532 /// CanPropagatePredecessorsForPHIs - Return true if we can fold BB, an
533 /// almost-empty BB ending in an unconditional branch to Succ, into Succ.
534 ///
535 /// Assumption: Succ is the single successor for BB.
536 ///
537 static bool CanPropagatePredecessorsForPHIs(BasicBlock *BB, BasicBlock *Succ) {
538   assert(*succ_begin(BB) == Succ && "Succ is not successor of BB!");
540   DEBUG(dbgs() << "Looking to fold " << BB->getName() << " into "
541         << Succ->getName() << "\n");
542   // Shortcut, if there is only a single predecessor it must be BB and merging
543   // is always safe
544   if (Succ->getSinglePredecessor()) return true;
546   // Make a list of the predecessors of BB
547   SmallPtrSet<BasicBlock*, 16> BBPreds(pred_begin(BB), pred_end(BB));
549   // Look at all the phi nodes in Succ, to see if they present a conflict when
550   // merging these blocks
551   for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
552     PHINode *PN = cast<PHINode>(I);
554     // If the incoming value from BB is again a PHINode in
555     // BB which has the same incoming value for *PI as PN does, we can
556     // merge the phi nodes and then the blocks can still be merged
557     PHINode *BBPN = dyn_cast<PHINode>(PN->getIncomingValueForBlock(BB));
558     if (BBPN && BBPN->getParent() == BB) {
559       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
560         BasicBlock *IBB = PN->getIncomingBlock(PI);
561         if (BBPreds.count(IBB) &&
562             !CanMergeValues(BBPN->getIncomingValueForBlock(IBB),
563                             PN->getIncomingValue(PI))) {
564           DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
565                 << Succ->getName() << " is conflicting with "
566                 << BBPN->getName() << " with regard to common predecessor "
567                 << IBB->getName() << "\n");
568           return false;
569         }
570       }
571     } else {
572       Value* Val = PN->getIncomingValueForBlock(BB);
573       for (unsigned PI = 0, PE = PN->getNumIncomingValues(); PI != PE; ++PI) {
574         // See if the incoming value for the common predecessor is equal to the
575         // one for BB, in which case this phi node will not prevent the merging
576         // of the block.
577         BasicBlock *IBB = PN->getIncomingBlock(PI);
578         if (BBPreds.count(IBB) &&
579             !CanMergeValues(Val, PN->getIncomingValue(PI))) {
580           DEBUG(dbgs() << "Can't fold, phi node " << PN->getName() << " in "
581                 << Succ->getName() << " is conflicting with regard to common "
582                 << "predecessor " << IBB->getName() << "\n");
583           return false;
584         }
585       }
586     }
587   }
589   return true;
592 typedef SmallVector<BasicBlock *, 16> PredBlockVector;
593 typedef DenseMap<BasicBlock *, Value *> IncomingValueMap;
595 /// \brief Determines the value to use as the phi node input for a block.
596 ///
597 /// Select between \p OldVal any value that we know flows from \p BB
598 /// to a particular phi on the basis of which one (if either) is not
599 /// undef. Update IncomingValues based on the selected value.
600 ///
601 /// \param OldVal The value we are considering selecting.
602 /// \param BB The block that the value flows in from.
603 /// \param IncomingValues A map from block-to-value for other phi inputs
604 /// that we have examined.
605 ///
606 /// \returns the selected value.
607 static Value *selectIncomingValueForBlock(Value *OldVal, BasicBlock *BB,
608                                           IncomingValueMap &IncomingValues) {
609   if (!isa<UndefValue>(OldVal)) {
610     assert((!IncomingValues.count(BB) ||
611             IncomingValues.find(BB)->second == OldVal) &&
612            "Expected OldVal to match incoming value from BB!");
614     IncomingValues.insert(std::make_pair(BB, OldVal));
615     return OldVal;
616   }
618   IncomingValueMap::const_iterator It = IncomingValues.find(BB);
619   if (It != IncomingValues.end()) return It->second;
621   return OldVal;
624 /// \brief Create a map from block to value for the operands of a
625 /// given phi.
626 ///
627 /// Create a map from block to value for each non-undef value flowing
628 /// into \p PN.
629 ///
630 /// \param PN The phi we are collecting the map for.
631 /// \param IncomingValues [out] The map from block to value for this phi.
632 static void gatherIncomingValuesToPhi(PHINode *PN,
633                                       IncomingValueMap &IncomingValues) {
634   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
635     BasicBlock *BB = PN->getIncomingBlock(i);
636     Value *V = PN->getIncomingValue(i);
638     if (!isa<UndefValue>(V))
639       IncomingValues.insert(std::make_pair(BB, V));
640   }
643 /// \brief Replace the incoming undef values to a phi with the values
644 /// from a block-to-value map.
645 ///
646 /// \param PN The phi we are replacing the undefs in.
647 /// \param IncomingValues A map from block to value.
648 static void replaceUndefValuesInPhi(PHINode *PN,
649                                     const IncomingValueMap &IncomingValues) {
650   for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
651     Value *V = PN->getIncomingValue(i);
653     if (!isa<UndefValue>(V)) continue;
655     BasicBlock *BB = PN->getIncomingBlock(i);
656     IncomingValueMap::const_iterator It = IncomingValues.find(BB);
657     if (It == IncomingValues.end()) continue;
659     PN->setIncomingValue(i, It->second);
660   }
663 /// \brief Replace a value flowing from a block to a phi with
664 /// potentially multiple instances of that value flowing from the
665 /// block's predecessors to the phi.
666 ///
667 /// \param BB The block with the value flowing into the phi.
668 /// \param BBPreds The predecessors of BB.
669 /// \param PN The phi that we are updating.
670 static void redirectValuesFromPredecessorsToPhi(BasicBlock *BB,
671                                                 const PredBlockVector &BBPreds,
672                                                 PHINode *PN) {
673   Value *OldVal = PN->removeIncomingValue(BB, false);
674   assert(OldVal && "No entry in PHI for Pred BB!");
676   IncomingValueMap IncomingValues;
678   // We are merging two blocks - BB, and the block containing PN - and
679   // as a result we need to redirect edges from the predecessors of BB
680   // to go to the block containing PN, and update PN
681   // accordingly. Since we allow merging blocks in the case where the
682   // predecessor and successor blocks both share some predecessors,
683   // and where some of those common predecessors might have undef
684   // values flowing into PN, we want to rewrite those values to be
685   // consistent with the non-undef values.
687   gatherIncomingValuesToPhi(PN, IncomingValues);
689   // If this incoming value is one of the PHI nodes in BB, the new entries
690   // in the PHI node are the entries from the old PHI.
691   if (isa<PHINode>(OldVal) && cast<PHINode>(OldVal)->getParent() == BB) {
692     PHINode *OldValPN = cast<PHINode>(OldVal);
693     for (unsigned i = 0, e = OldValPN->getNumIncomingValues(); i != e; ++i) {
694       // Note that, since we are merging phi nodes and BB and Succ might
695       // have common predecessors, we could end up with a phi node with
696       // identical incoming branches. This will be cleaned up later (and
697       // will trigger asserts if we try to clean it up now, without also
698       // simplifying the corresponding conditional branch).
699       BasicBlock *PredBB = OldValPN->getIncomingBlock(i);
700       Value *PredVal = OldValPN->getIncomingValue(i);
701       Value *Selected = selectIncomingValueForBlock(PredVal, PredBB,
702                                                     IncomingValues);
704       // And add a new incoming value for this predecessor for the
705       // newly retargeted branch.
706       PN->addIncoming(Selected, PredBB);
707     }
708   } else {
709     for (unsigned i = 0, e = BBPreds.size(); i != e; ++i) {
710       // Update existing incoming values in PN for this
711       // predecessor of BB.
712       BasicBlock *PredBB = BBPreds[i];
713       Value *Selected = selectIncomingValueForBlock(OldVal, PredBB,
714                                                     IncomingValues);
716       // And add a new incoming value for this predecessor for the
717       // newly retargeted branch.
718       PN->addIncoming(Selected, PredBB);
719     }
720   }
722   replaceUndefValuesInPhi(PN, IncomingValues);
725 /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an
726 /// unconditional branch, and contains no instructions other than PHI nodes,
727 /// potential side-effect free intrinsics and the branch.  If possible,
728 /// eliminate BB by rewriting all the predecessors to branch to the successor
729 /// block and return true.  If we can't transform, return false.
730 bool llvm::TryToSimplifyUncondBranchFromEmptyBlock(BasicBlock *BB) {
731   assert(BB != &BB->getParent()->getEntryBlock() &&
732          "TryToSimplifyUncondBranchFromEmptyBlock called on entry block!");
734   // We can't eliminate infinite loops.
735   BasicBlock *Succ = cast<BranchInst>(BB->getTerminator())->getSuccessor(0);
736   if (BB == Succ) return false;
738   // Check to see if merging these blocks would cause conflicts for any of the
739   // phi nodes in BB or Succ. If not, we can safely merge.
740   if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false;
742   // Check for cases where Succ has multiple predecessors and a PHI node in BB
743   // has uses which will not disappear when the PHI nodes are merged.  It is
744   // possible to handle such cases, but difficult: it requires checking whether
745   // BB dominates Succ, which is non-trivial to calculate in the case where
746   // Succ has multiple predecessors.  Also, it requires checking whether
747   // constructing the necessary self-referential PHI node doesn't introduce any
748   // conflicts; this isn't too difficult, but the previous code for doing this
749   // was incorrect.
750   //
751   // Note that if this check finds a live use, BB dominates Succ, so BB is
752   // something like a loop pre-header (or rarely, a part of an irreducible CFG);
753   // folding the branch isn't profitable in that case anyway.
754   if (!Succ->getSinglePredecessor()) {
755     BasicBlock::iterator BBI = BB->begin();
756     while (isa<PHINode>(*BBI)) {
757       for (Use &U : BBI->uses()) {
758         if (PHINode* PN = dyn_cast<PHINode>(U.getUser())) {
759           if (PN->getIncomingBlock(U) != BB)
760             return false;
761         } else {
762           return false;
763         }
764       }
765       ++BBI;
766     }
767   }
769   DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB);
771   if (isa<PHINode>(Succ->begin())) {
772     // If there is more than one pred of succ, and there are PHI nodes in
773     // the successor, then we need to add incoming edges for the PHI nodes
774     //
775     const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB));
777     // Loop over all of the PHI nodes in the successor of BB.
778     for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
779       PHINode *PN = cast<PHINode>(I);
781       redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN);
782     }
783   }
785   if (Succ->getSinglePredecessor()) {
786     // BB is the only predecessor of Succ, so Succ will end up with exactly
787     // the same predecessors BB had.
789     // Copy over any phi, debug or lifetime instruction.
790     BB->getTerminator()->eraseFromParent();
791     Succ->getInstList().splice(Succ->getFirstNonPHI(), BB->getInstList());
792   } else {
793     while (PHINode *PN = dyn_cast<PHINode>(&BB->front())) {
794       // We explicitly check for such uses in CanPropagatePredecessorsForPHIs.
795       assert(PN->use_empty() && "There shouldn't be any uses here!");
796       PN->eraseFromParent();
797     }
798   }
800   // Everything that jumped to BB now goes to Succ.
801   BB->replaceAllUsesWith(Succ);
802   if (!Succ->hasName()) Succ->takeName(BB);
803   BB->eraseFromParent();              // Delete the old basic block.
804   return true;
807 /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI
808 /// nodes in this block. This doesn't try to be clever about PHI nodes
809 /// which differ only in the order of the incoming values, but instcombine
810 /// orders them so it usually won't matter.
811 ///
812 bool llvm::EliminateDuplicatePHINodes(BasicBlock *BB) {
813   bool Changed = false;
815   // This implementation doesn't currently consider undef operands
816   // specially. Theoretically, two phis which are identical except for
817   // one having an undef where the other doesn't could be collapsed.
819   // Map from PHI hash values to PHI nodes. If multiple PHIs have
820   // the same hash value, the element is the first PHI in the
821   // linked list in CollisionMap.
822   DenseMap<uintptr_t, PHINode *> HashMap;
824   // Maintain linked lists of PHI nodes with common hash values.
825   DenseMap<PHINode *, PHINode *> CollisionMap;
827   // Examine each PHI.
828   for (BasicBlock::iterator I = BB->begin();
829        PHINode *PN = dyn_cast<PHINode>(I++); ) {
830     // Compute a hash value on the operands. Instcombine will likely have sorted
831     // them, which helps expose duplicates, but we have to check all the
832     // operands to be safe in case instcombine hasn't run.
833     uintptr_t Hash = 0;
834     // This hash algorithm is quite weak as hash functions go, but it seems
835     // to do a good enough job for this particular purpose, and is very quick.
836     for (User::op_iterator I = PN->op_begin(), E = PN->op_end(); I != E; ++I) {
837       Hash ^= reinterpret_cast<uintptr_t>(static_cast<Value *>(*I));
838       Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7));
839     }
840     for (PHINode::block_iterator I = PN->block_begin(), E = PN->block_end();
841          I != E; ++I) {
842       Hash ^= reinterpret_cast<uintptr_t>(static_cast<BasicBlock *>(*I));
843       Hash = (Hash << 7) | (Hash >> (sizeof(uintptr_t) * CHAR_BIT - 7));
844     }
845     // Avoid colliding with the DenseMap sentinels ~0 and ~0-1.
846     Hash >>= 1;
847     // If we've never seen this hash value before, it's a unique PHI.
848     std::pair<DenseMap<uintptr_t, PHINode *>::iterator, bool> Pair =
849       HashMap.insert(std::make_pair(Hash, PN));
850     if (Pair.second) continue;
851     // Otherwise it's either a duplicate or a hash collision.
852     for (PHINode *OtherPN = Pair.first->second; ; ) {
853       if (OtherPN->isIdenticalTo(PN)) {
854         // A duplicate. Replace this PHI with its duplicate.
855         PN->replaceAllUsesWith(OtherPN);
856         PN->eraseFromParent();
857         Changed = true;
858         break;
859       }
860       // A non-duplicate hash collision.
861       DenseMap<PHINode *, PHINode *>::iterator I = CollisionMap.find(OtherPN);
862       if (I == CollisionMap.end()) {
863         // Set this PHI to be the head of the linked list of colliding PHIs.
864         PHINode *Old = Pair.first->second;
865         Pair.first->second = PN;
866         CollisionMap[PN] = Old;
867         break;
868       }
869       // Proceed to the next PHI in the list.
870       OtherPN = I->second;
871     }
872   }
874   return Changed;
877 /// enforceKnownAlignment - If the specified pointer points to an object that
878 /// we control, modify the object's alignment to PrefAlign. This isn't
879 /// often possible though. If alignment is important, a more reliable approach
880 /// is to simply align all global variables and allocation instructions to
881 /// their preferred alignment from the beginning.
882 ///
883 static unsigned enforceKnownAlignment(Value *V, unsigned Align,
884                                       unsigned PrefAlign, const DataLayout *TD) {
885   V = V->stripPointerCasts();
887   if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
888     // If the preferred alignment is greater than the natural stack alignment
889     // then don't round up. This avoids dynamic stack realignment.
890     if (TD && TD->exceedsNaturalStackAlignment(PrefAlign))
891       return Align;
892     // If there is a requested alignment and if this is an alloca, round up.
893     if (AI->getAlignment() >= PrefAlign)
894       return AI->getAlignment();
895     AI->setAlignment(PrefAlign);
896     return PrefAlign;
897   }
899   if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
900     // If there is a large requested alignment and we can, bump up the alignment
901     // of the global.
902     if (GV->isDeclaration()) return Align;
903     // If the memory we set aside for the global may not be the memory used by
904     // the final program then it is impossible for us to reliably enforce the
905     // preferred alignment.
906     if (GV->isWeakForLinker()) return Align;
908     if (GV->getAlignment() >= PrefAlign)
909       return GV->getAlignment();
910     // We can only increase the alignment of the global if it has no alignment
911     // specified or if it is not assigned a section.  If it is assigned a
912     // section, the global could be densely packed with other objects in the
913     // section, increasing the alignment could cause padding issues.
914     if (!GV->hasSection() || GV->getAlignment() == 0)
915       GV->setAlignment(PrefAlign);
916     return GV->getAlignment();
917   }
919   return Align;
922 /// getOrEnforceKnownAlignment - If the specified pointer has an alignment that
923 /// we can determine, return it, otherwise return 0.  If PrefAlign is specified,
924 /// and it is more than the alignment of the ultimate object, see if we can
925 /// increase the alignment of the ultimate object, making this check succeed.
926 unsigned llvm::getOrEnforceKnownAlignment(Value *V, unsigned PrefAlign,
927                                           const DataLayout *DL) {
928   assert(V->getType()->isPointerTy() &&
929          "getOrEnforceKnownAlignment expects a pointer!");
930   unsigned BitWidth = DL ? DL->getPointerTypeSizeInBits(V->getType()) : 64;
932   APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0);
933   ComputeMaskedBits(V, KnownZero, KnownOne, DL);
934   unsigned TrailZ = KnownZero.countTrailingOnes();
936   // Avoid trouble with ridiculously large TrailZ values, such as
937   // those computed from a null pointer.
938   TrailZ = std::min(TrailZ, unsigned(sizeof(unsigned) * CHAR_BIT - 1));
940   unsigned Align = 1u << std::min(BitWidth - 1, TrailZ);
942   // LLVM doesn't support alignments larger than this currently.
943   Align = std::min(Align, +Value::MaximumAlignment);
945   if (PrefAlign > Align)
946     Align = enforceKnownAlignment(V, Align, PrefAlign, DL);
948   // We don't need to make any adjustment.
949   return Align;
952 ///===---------------------------------------------------------------------===//
953 ///  Dbg Intrinsic utilities
954 ///
956 /// See if there is a dbg.value intrinsic for DIVar before I.
957 static bool LdStHasDebugValue(DIVariable &DIVar, Instruction *I) {
958   // Since we can't guarantee that the original dbg.declare instrinsic
959   // is removed by LowerDbgDeclare(), we need to make sure that we are
960   // not inserting the same dbg.value intrinsic over and over.
961   llvm::BasicBlock::InstListType::iterator PrevI(I);
962   if (PrevI != I->getParent()->getInstList().begin()) {
963     --PrevI;
964     if (DbgValueInst *DVI = dyn_cast<DbgValueInst>(PrevI))
965       if (DVI->getValue() == I->getOperand(0) &&
966           DVI->getOffset() == 0 &&
967           DVI->getVariable() == DIVar)
968         return true;
969   }
970   return false;
973 /// Inserts a llvm.dbg.value intrinsic before a store to an alloca'd value
974 /// that has an associated llvm.dbg.decl intrinsic.
975 bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
976                                            StoreInst *SI, DIBuilder &Builder) {
977   DIVariable DIVar(DDI->getVariable());
978   assert((!DIVar || DIVar.isVariable()) &&
979          "Variable in DbgDeclareInst should be either null or a DIVariable.");
980   if (!DIVar)
981     return false;
983   if (LdStHasDebugValue(DIVar, SI))
984     return true;
986   Instruction *DbgVal = nullptr;
987   // If an argument is zero extended then use argument directly. The ZExt
988   // may be zapped by an optimization pass in future.
989   Argument *ExtendedArg = nullptr;
990   if (ZExtInst *ZExt = dyn_cast<ZExtInst>(SI->getOperand(0)))
991     ExtendedArg = dyn_cast<Argument>(ZExt->getOperand(0));
992   if (SExtInst *SExt = dyn_cast<SExtInst>(SI->getOperand(0)))
993     ExtendedArg = dyn_cast<Argument>(SExt->getOperand(0));
994   if (ExtendedArg)
995     DbgVal = Builder.insertDbgValueIntrinsic(ExtendedArg, 0, DIVar, SI);
996   else
997     DbgVal = Builder.insertDbgValueIntrinsic(SI->getOperand(0), 0, DIVar, SI);
998   DbgVal->setDebugLoc(DDI->getDebugLoc());
999   return true;
1002 /// Inserts a llvm.dbg.value intrinsic before a load of an alloca'd value
1003 /// that has an associated llvm.dbg.decl intrinsic.
1004 bool llvm::ConvertDebugDeclareToDebugValue(DbgDeclareInst *DDI,
1005                                            LoadInst *LI, DIBuilder &Builder) {
1006   DIVariable DIVar(DDI->getVariable());
1007   assert((!DIVar || DIVar.isVariable()) &&
1008          "Variable in DbgDeclareInst should be either null or a DIVariable.");
1009   if (!DIVar)
1010     return false;
1012   if (LdStHasDebugValue(DIVar, LI))
1013     return true;
1015   Instruction *DbgVal =
1016     Builder.insertDbgValueIntrinsic(LI->getOperand(0), 0,
1017                                     DIVar, LI);
1018   DbgVal->setDebugLoc(DDI->getDebugLoc());
1019   return true;
1022 /// Determine whether this alloca is either a VLA or an array.
1023 static bool isArray(AllocaInst *AI) {
1024   return AI->isArrayAllocation() ||
1025     AI->getType()->getElementType()->isArrayTy();
1028 /// LowerDbgDeclare - Lowers llvm.dbg.declare intrinsics into appropriate set
1029 /// of llvm.dbg.value intrinsics.
1030 bool llvm::LowerDbgDeclare(Function &F) {
1031   DIBuilder DIB(*F.getParent());
1032   SmallVector<DbgDeclareInst *, 4> Dbgs;
1033   for (auto &FI : F)
1034     for (BasicBlock::iterator BI : FI)
1035       if (auto DDI = dyn_cast<DbgDeclareInst>(BI))
1036         Dbgs.push_back(DDI);
1038   if (Dbgs.empty())
1039     return false;
1041   for (auto &I : Dbgs) {
1042     DbgDeclareInst *DDI = I;
1043     AllocaInst *AI = dyn_cast_or_null<AllocaInst>(DDI->getAddress());
1044     // If this is an alloca for a scalar variable, insert a dbg.value
1045     // at each load and store to the alloca and erase the dbg.declare.
1046     // The dbg.values allow tracking a variable even if it is not
1047     // stored on the stack, while the dbg.declare can only describe
1048     // the stack slot (and at a lexical-scope granularity). Later
1049     // passes will attempt to elide the stack slot.
1050     if (AI && !isArray(AI)) {
1051       for (User *U : AI->users())
1052         if (StoreInst *SI = dyn_cast<StoreInst>(U))
1053           ConvertDebugDeclareToDebugValue(DDI, SI, DIB);
1054         else if (LoadInst *LI = dyn_cast<LoadInst>(U))
1055           ConvertDebugDeclareToDebugValue(DDI, LI, DIB);
1056         else if (CallInst *CI = dyn_cast<CallInst>(U)) {
1057           // This is a call by-value or some other instruction that
1058           // takes a pointer to the variable. Insert a *value*
1059           // intrinsic that describes the alloca.
1060           auto DbgVal =
1061             DIB.insertDbgValueIntrinsic(AI, 0,
1062                                         DIVariable(DDI->getVariable()), CI);
1063           DbgVal->setDebugLoc(DDI->getDebugLoc());
1064         }
1065       DDI->eraseFromParent();
1066     }
1067   }
1068   return true;
1071 /// FindAllocaDbgDeclare - Finds the llvm.dbg.declare intrinsic describing the
1072 /// alloca 'V', if any.
1073 DbgDeclareInst *llvm::FindAllocaDbgDeclare(Value *V) {
1074   if (MDNode *DebugNode = MDNode::getIfExists(V->getContext(), V))
1075     for (User *U : DebugNode->users())
1076       if (DbgDeclareInst *DDI = dyn_cast<DbgDeclareInst>(U))
1077         return DDI;
1079   return nullptr;
1082 bool llvm::replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
1083                                       DIBuilder &Builder) {
1084   DbgDeclareInst *DDI = FindAllocaDbgDeclare(AI);
1085   if (!DDI)
1086     return false;
1087   DIVariable DIVar(DDI->getVariable());
1088   assert((!DIVar || DIVar.isVariable()) &&
1089          "Variable in DbgDeclareInst should be either null or a DIVariable.");
1090   if (!DIVar)
1091     return false;
1093   // Create a copy of the original DIDescriptor for user variable, appending
1094   // "deref" operation to a list of address elements, as new llvm.dbg.declare
1095   // will take a value storing address of the memory for variable, not
1096   // alloca itself.
1097   Type *Int64Ty = Type::getInt64Ty(AI->getContext());
1098   SmallVector<Value*, 4> NewDIVarAddress;
1099   if (DIVar.hasComplexAddress()) {
1100     for (unsigned i = 0, n = DIVar.getNumAddrElements(); i < n; ++i) {
1101       NewDIVarAddress.push_back(
1102           ConstantInt::get(Int64Ty, DIVar.getAddrElement(i)));
1103     }
1104   }
1105   NewDIVarAddress.push_back(ConstantInt::get(Int64Ty, DIBuilder::OpDeref));
1106   DIVariable NewDIVar = Builder.createComplexVariable(
1107       DIVar.getTag(), DIVar.getContext(), DIVar.getName(),
1108       DIVar.getFile(), DIVar.getLineNumber(), DIVar.getType(),
1109       NewDIVarAddress, DIVar.getArgNumber());
1111   // Insert llvm.dbg.declare in the same basic block as the original alloca,
1112   // and remove old llvm.dbg.declare.
1113   BasicBlock *BB = AI->getParent();
1114   Builder.insertDeclare(NewAllocaAddress, NewDIVar, BB);
1115   DDI->eraseFromParent();
1116   return true;
1119 /// changeToUnreachable - Insert an unreachable instruction before the specified
1120 /// instruction, making it and the rest of the code in the block dead.
1121 static void changeToUnreachable(Instruction *I, bool UseLLVMTrap) {
1122   BasicBlock *BB = I->getParent();
1123   // Loop over all of the successors, removing BB's entry from any PHI
1124   // nodes.
1125   for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
1126     (*SI)->removePredecessor(BB);
1128   // Insert a call to llvm.trap right before this.  This turns the undefined
1129   // behavior into a hard fail instead of falling through into random code.
1130   if (UseLLVMTrap) {
1131     Function *TrapFn =
1132       Intrinsic::getDeclaration(BB->getParent()->getParent(), Intrinsic::trap);
1133     CallInst *CallTrap = CallInst::Create(TrapFn, "", I);
1134     CallTrap->setDebugLoc(I->getDebugLoc());
1135   }
1136   new UnreachableInst(I->getContext(), I);
1138   // All instructions after this are dead.
1139   BasicBlock::iterator BBI = I, BBE = BB->end();
1140   while (BBI != BBE) {
1141     if (!BBI->use_empty())
1142       BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
1143     BB->getInstList().erase(BBI++);
1144   }
1147 /// changeToCall - Convert the specified invoke into a normal call.
1148 static void changeToCall(InvokeInst *II) {
1149   SmallVector<Value*, 8> Args(II->op_begin(), II->op_end() - 3);
1150   CallInst *NewCall = CallInst::Create(II->getCalledValue(), Args, "", II);
1151   NewCall->takeName(II);
1152   NewCall->setCallingConv(II->getCallingConv());
1153   NewCall->setAttributes(II->getAttributes());
1154   NewCall->setDebugLoc(II->getDebugLoc());
1155   II->replaceAllUsesWith(NewCall);
1157   // Follow the call by a branch to the normal destination.
1158   BranchInst::Create(II->getNormalDest(), II);
1160   // Update PHI nodes in the unwind destination
1161   II->getUnwindDest()->removePredecessor(II->getParent());
1162   II->eraseFromParent();
1165 static bool markAliveBlocks(BasicBlock *BB,
1166                             SmallPtrSet<BasicBlock*, 128> &Reachable) {
1168   SmallVector<BasicBlock*, 128> Worklist;
1169   Worklist.push_back(BB);
1170   Reachable.insert(BB);
1171   bool Changed = false;
1172   do {
1173     BB = Worklist.pop_back_val();
1175     // Do a quick scan of the basic block, turning any obviously unreachable
1176     // instructions into LLVM unreachable insts.  The instruction combining pass
1177     // canonicalizes unreachable insts into stores to null or undef.
1178     for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E;++BBI){
1179       if (CallInst *CI = dyn_cast<CallInst>(BBI)) {
1180         if (CI->doesNotReturn()) {
1181           // If we found a call to a no-return function, insert an unreachable
1182           // instruction after it.  Make sure there isn't *already* one there
1183           // though.
1184           ++BBI;
1185           if (!isa<UnreachableInst>(BBI)) {
1186             // Don't insert a call to llvm.trap right before the unreachable.
1187             changeToUnreachable(BBI, false);
1188             Changed = true;
1189           }
1190           break;
1191         }
1192       }
1194       // Store to undef and store to null are undefined and used to signal that
1195       // they should be changed to unreachable by passes that can't modify the
1196       // CFG.
1197       if (StoreInst *SI = dyn_cast<StoreInst>(BBI)) {
1198         // Don't touch volatile stores.
1199         if (SI->isVolatile()) continue;
1201         Value *Ptr = SI->getOperand(1);
1203         if (isa<UndefValue>(Ptr) ||
1204             (isa<ConstantPointerNull>(Ptr) &&
1205              SI->getPointerAddressSpace() == 0)) {
1206           changeToUnreachable(SI, true);
1207           Changed = true;
1208           break;
1209         }
1210       }
1211     }
1213     // Turn invokes that call 'nounwind' functions into ordinary calls.
1214     if (InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator())) {
1215       Value *Callee = II->getCalledValue();
1216       if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
1217         changeToUnreachable(II, true);
1218         Changed = true;
1219       } else if (II->doesNotThrow()) {
1220         if (II->use_empty() && II->onlyReadsMemory()) {
1221           // jump to the normal destination branch.
1222           BranchInst::Create(II->getNormalDest(), II);
1223           II->getUnwindDest()->removePredecessor(II->getParent());
1224           II->eraseFromParent();
1225         } else
1226           changeToCall(II);
1227         Changed = true;
1228       }
1229     }
1231     Changed |= ConstantFoldTerminator(BB, true);
1232     for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
1233       if (Reachable.insert(*SI))
1234         Worklist.push_back(*SI);
1235   } while (!Worklist.empty());
1236   return Changed;
1239 /// removeUnreachableBlocksFromFn - Remove blocks that are not reachable, even
1240 /// if they are in a dead cycle.  Return true if a change was made, false
1241 /// otherwise.
1242 bool llvm::removeUnreachableBlocks(Function &F) {
1243   SmallPtrSet<BasicBlock*, 128> Reachable;
1244   bool Changed = markAliveBlocks(F.begin(), Reachable);
1246   // If there are unreachable blocks in the CFG...
1247   if (Reachable.size() == F.size())
1248     return Changed;
1250   assert(Reachable.size() < F.size());
1251   NumRemoved += F.size()-Reachable.size();
1253   // Loop over all of the basic blocks that are not reachable, dropping all of
1254   // their internal references...
1255   for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB) {
1256     if (Reachable.count(BB))
1257       continue;
1259     for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
1260       if (Reachable.count(*SI))
1261         (*SI)->removePredecessor(BB);
1262     BB->dropAllReferences();
1263   }
1265   for (Function::iterator I = ++F.begin(); I != F.end();)
1266     if (!Reachable.count(I))
1267       I = F.getBasicBlockList().erase(I);
1268     else
1269       ++I;
1271   return true;