Fix crash when printing instructions that have a metadata attached but no parent.
[oota-llvm.git] / lib / IR / BasicBlock.cpp
1 //===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===//
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 file implements the BasicBlock class for the IR library.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/IR/BasicBlock.h"
15 #include "SymbolTableListTraitsImpl.h"
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/IR/CFG.h"
18 #include "llvm/IR/Constants.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/IntrinsicInst.h"
21 #include "llvm/IR/LLVMContext.h"
22 #include "llvm/IR/Type.h"
23 #include <algorithm>
24
25 using namespace llvm;
26
27 ValueSymbolTable *BasicBlock::getValueSymbolTable() {
28   if (Function *F = getParent())
29     return &F->getValueSymbolTable();
30   return nullptr;
31 }
32
33 LLVMContext &BasicBlock::getContext() const {
34   return getType()->getContext();
35 }
36
37 // Explicit instantiation of SymbolTableListTraits since some of the methods
38 // are not in the public header file...
39 template class llvm::SymbolTableListTraits<Instruction>;
40
41 BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
42                        BasicBlock *InsertBefore)
43   : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
44
45   if (NewParent)
46     insertInto(NewParent, InsertBefore);
47   else
48     assert(!InsertBefore &&
49            "Cannot insert block before another block with no function!");
50
51   setName(Name);
52 }
53
54 void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
55   assert(NewParent && "Expected a parent");
56   assert(!Parent && "Already has a parent");
57
58   if (InsertBefore)
59     NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
60   else
61     NewParent->getBasicBlockList().push_back(this);
62 }
63
64 BasicBlock::~BasicBlock() {
65   // If the address of the block is taken and it is being deleted (e.g. because
66   // it is dead), this means that there is either a dangling constant expr
67   // hanging off the block, or an undefined use of the block (source code
68   // expecting the address of a label to keep the block alive even though there
69   // is no indirect branch).  Handle these cases by zapping the BlockAddress
70   // nodes.  There are no other possible uses at this point.
71   if (hasAddressTaken()) {
72     assert(!use_empty() && "There should be at least one blockaddress!");
73     Constant *Replacement =
74       ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
75     while (!use_empty()) {
76       BlockAddress *BA = cast<BlockAddress>(user_back());
77       BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
78                                                        BA->getType()));
79       BA->destroyConstant();
80     }
81   }
82
83   assert(getParent() == nullptr && "BasicBlock still linked into the program!");
84   dropAllReferences();
85   InstList.clear();
86 }
87
88 void BasicBlock::setParent(Function *parent) {
89   // Set Parent=parent, updating instruction symtab entries as appropriate.
90   InstList.setSymTabObject(&Parent, parent);
91 }
92
93 void BasicBlock::removeFromParent() {
94   getParent()->getBasicBlockList().remove(getIterator());
95 }
96
97 iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
98   return getParent()->getBasicBlockList().erase(getIterator());
99 }
100
101 /// Unlink this basic block from its current function and
102 /// insert it into the function that MovePos lives in, right before MovePos.
103 void BasicBlock::moveBefore(BasicBlock *MovePos) {
104   MovePos->getParent()->getBasicBlockList().splice(
105       MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
106 }
107
108 /// Unlink this basic block from its current function and
109 /// insert it into the function that MovePos lives in, right after MovePos.
110 void BasicBlock::moveAfter(BasicBlock *MovePos) {
111   MovePos->getParent()->getBasicBlockList().splice(
112       ++MovePos->getIterator(), getParent()->getBasicBlockList(),
113       getIterator());
114 }
115
116 const Module *BasicBlock::getModule() const {
117   return getParent()->getParent();
118 }
119
120 Module *BasicBlock::getModule() {
121   return getParent()->getParent();
122 }
123
124 TerminatorInst *BasicBlock::getTerminator() {
125   if (InstList.empty()) return nullptr;
126   return dyn_cast<TerminatorInst>(&InstList.back());
127 }
128
129 const TerminatorInst *BasicBlock::getTerminator() const {
130   if (InstList.empty()) return nullptr;
131   return dyn_cast<TerminatorInst>(&InstList.back());
132 }
133
134 CallInst *BasicBlock::getTerminatingMustTailCall() {
135   if (InstList.empty())
136     return nullptr;
137   ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
138   if (!RI || RI == &InstList.front())
139     return nullptr;
140
141   Instruction *Prev = RI->getPrevNode();
142   if (!Prev)
143     return nullptr;
144
145   if (Value *RV = RI->getReturnValue()) {
146     if (RV != Prev)
147       return nullptr;
148
149     // Look through the optional bitcast.
150     if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
151       RV = BI->getOperand(0);
152       Prev = BI->getPrevNode();
153       if (!Prev || RV != Prev)
154         return nullptr;
155     }
156   }
157
158   if (auto *CI = dyn_cast<CallInst>(Prev)) {
159     if (CI->isMustTailCall())
160       return CI;
161   }
162   return nullptr;
163 }
164
165 Instruction* BasicBlock::getFirstNonPHI() {
166   for (Instruction &I : *this)
167     if (!isa<PHINode>(I))
168       return &I;
169   return nullptr;
170 }
171
172 Instruction* BasicBlock::getFirstNonPHIOrDbg() {
173   for (Instruction &I : *this)
174     if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I))
175       return &I;
176   return nullptr;
177 }
178
179 Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() {
180   for (Instruction &I : *this) {
181     if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
182       continue;
183
184     if (auto *II = dyn_cast<IntrinsicInst>(&I))
185       if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
186           II->getIntrinsicID() == Intrinsic::lifetime_end)
187         continue;
188
189     return &I;
190   }
191   return nullptr;
192 }
193
194 BasicBlock::iterator BasicBlock::getFirstInsertionPt() {
195   Instruction *FirstNonPHI = getFirstNonPHI();
196   if (!FirstNonPHI)
197     return end();
198
199   iterator InsertPt = FirstNonPHI->getIterator();
200   if (InsertPt->isEHPad()) ++InsertPt;
201   return InsertPt;
202 }
203
204 void BasicBlock::dropAllReferences() {
205   for(iterator I = begin(), E = end(); I != E; ++I)
206     I->dropAllReferences();
207 }
208
209 /// If this basic block has a single predecessor block,
210 /// return the block, otherwise return a null pointer.
211 BasicBlock *BasicBlock::getSinglePredecessor() {
212   pred_iterator PI = pred_begin(this), E = pred_end(this);
213   if (PI == E) return nullptr;         // No preds.
214   BasicBlock *ThePred = *PI;
215   ++PI;
216   return (PI == E) ? ThePred : nullptr /*multiple preds*/;
217 }
218
219 /// If this basic block has a unique predecessor block,
220 /// return the block, otherwise return a null pointer.
221 /// Note that unique predecessor doesn't mean single edge, there can be
222 /// multiple edges from the unique predecessor to this block (for example
223 /// a switch statement with multiple cases having the same destination).
224 BasicBlock *BasicBlock::getUniquePredecessor() {
225   pred_iterator PI = pred_begin(this), E = pred_end(this);
226   if (PI == E) return nullptr; // No preds.
227   BasicBlock *PredBB = *PI;
228   ++PI;
229   for (;PI != E; ++PI) {
230     if (*PI != PredBB)
231       return nullptr;
232     // The same predecessor appears multiple times in the predecessor list.
233     // This is OK.
234   }
235   return PredBB;
236 }
237
238 BasicBlock *BasicBlock::getSingleSuccessor() {
239   succ_iterator SI = succ_begin(this), E = succ_end(this);
240   if (SI == E) return nullptr; // no successors
241   BasicBlock *TheSucc = *SI;
242   ++SI;
243   return (SI == E) ? TheSucc : nullptr /* multiple successors */;
244 }
245
246 BasicBlock *BasicBlock::getUniqueSuccessor() {
247   succ_iterator SI = succ_begin(this), E = succ_end(this);
248   if (SI == E) return nullptr; // No successors
249   BasicBlock *SuccBB = *SI;
250   ++SI;
251   for (;SI != E; ++SI) {
252     if (*SI != SuccBB)
253       return nullptr;
254     // The same successor appears multiple times in the successor list.
255     // This is OK.
256   }
257   return SuccBB;
258 }
259
260 /// This method is used to notify a BasicBlock that the
261 /// specified Predecessor of the block is no longer able to reach it.  This is
262 /// actually not used to update the Predecessor list, but is actually used to
263 /// update the PHI nodes that reside in the block.  Note that this should be
264 /// called while the predecessor still refers to this block.
265 ///
266 void BasicBlock::removePredecessor(BasicBlock *Pred,
267                                    bool DontDeleteUselessPHIs) {
268   assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
269           find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
270          "removePredecessor: BB is not a predecessor!");
271
272   if (InstList.empty()) return;
273   PHINode *APN = dyn_cast<PHINode>(&front());
274   if (!APN) return;   // Quick exit.
275
276   // If there are exactly two predecessors, then we want to nuke the PHI nodes
277   // altogether.  However, we cannot do this, if this in this case:
278   //
279   //  Loop:
280   //    %x = phi [X, Loop]
281   //    %x2 = add %x, 1         ;; This would become %x2 = add %x2, 1
282   //    br Loop                 ;; %x2 does not dominate all uses
283   //
284   // This is because the PHI node input is actually taken from the predecessor
285   // basic block.  The only case this can happen is with a self loop, so we
286   // check for this case explicitly now.
287   //
288   unsigned max_idx = APN->getNumIncomingValues();
289   assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
290   if (max_idx == 2) {
291     BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
292
293     // Disable PHI elimination!
294     if (this == Other) max_idx = 3;
295   }
296
297   // <= Two predecessors BEFORE I remove one?
298   if (max_idx <= 2 && !DontDeleteUselessPHIs) {
299     // Yup, loop through and nuke the PHI nodes
300     while (PHINode *PN = dyn_cast<PHINode>(&front())) {
301       // Remove the predecessor first.
302       PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs);
303
304       // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
305       if (max_idx == 2) {
306         if (PN->getIncomingValue(0) != PN)
307           PN->replaceAllUsesWith(PN->getIncomingValue(0));
308         else
309           // We are left with an infinite loop with no entries: kill the PHI.
310           PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
311         getInstList().pop_front();    // Remove the PHI node
312       }
313
314       // If the PHI node already only had one entry, it got deleted by
315       // removeIncomingValue.
316     }
317   } else {
318     // Okay, now we know that we need to remove predecessor #pred_idx from all
319     // PHI nodes.  Iterate over each PHI node fixing them up
320     PHINode *PN;
321     for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
322       ++II;
323       PN->removeIncomingValue(Pred, false);
324       // If all incoming values to the Phi are the same, we can replace the Phi
325       // with that value.
326       Value* PNV = nullptr;
327       if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue()))
328         if (PNV != PN) {
329           PN->replaceAllUsesWith(PNV);
330           PN->eraseFromParent();
331         }
332     }
333   }
334 }
335
336 bool BasicBlock::canSplitPredecessors() const {
337   const Instruction *FirstNonPHI = getFirstNonPHI();
338   if (isa<LandingPadInst>(FirstNonPHI))
339     return true;
340   // This is perhaps a little conservative because constructs like
341   // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
342   // cannot handle such things just yet.
343   if (FirstNonPHI->isEHPad())
344     return false;
345   return true;
346 }
347
348 /// This splits a basic block into two at the specified
349 /// instruction.  Note that all instructions BEFORE the specified iterator stay
350 /// as part of the original basic block, an unconditional branch is added to
351 /// the new BB, and the rest of the instructions in the BB are moved to the new
352 /// BB, including the old terminator.  This invalidates the iterator.
353 ///
354 /// Note that this only works on well formed basic blocks (must have a
355 /// terminator), and 'I' must not be the end of instruction list (which would
356 /// cause a degenerate basic block to be formed, having a terminator inside of
357 /// the basic block).
358 ///
359 BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
360   assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
361   assert(I != InstList.end() &&
362          "Trying to get me to create degenerate basic block!");
363
364   BasicBlock *InsertBefore = std::next(Function::iterator(this))
365                                .getNodePtrUnchecked();
366   BasicBlock *New = BasicBlock::Create(getContext(), BBName,
367                                        getParent(), InsertBefore);
368
369   // Save DebugLoc of split point before invalidating iterator.
370   DebugLoc Loc = I->getDebugLoc();
371   // Move all of the specified instructions from the original basic block into
372   // the new basic block.
373   New->getInstList().splice(New->end(), this->getInstList(), I, end());
374
375   // Add a branch instruction to the newly formed basic block.
376   BranchInst *BI = BranchInst::Create(New, this);
377   BI->setDebugLoc(Loc);
378
379   // Now we must loop through all of the successors of the New block (which
380   // _were_ the successors of the 'this' block), and update any PHI nodes in
381   // successors.  If there were PHI nodes in the successors, then they need to
382   // know that incoming branches will be from New, not from Old.
383   //
384   for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) {
385     // Loop over any phi nodes in the basic block, updating the BB field of
386     // incoming values...
387     BasicBlock *Successor = *I;
388     PHINode *PN;
389     for (BasicBlock::iterator II = Successor->begin();
390          (PN = dyn_cast<PHINode>(II)); ++II) {
391       int IDX = PN->getBasicBlockIndex(this);
392       while (IDX != -1) {
393         PN->setIncomingBlock((unsigned)IDX, New);
394         IDX = PN->getBasicBlockIndex(this);
395       }
396     }
397   }
398   return New;
399 }
400
401 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
402   TerminatorInst *TI = getTerminator();
403   if (!TI)
404     // Cope with being called on a BasicBlock that doesn't have a terminator
405     // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
406     return;
407   for (BasicBlock *Succ : TI->successors()) {
408     // N.B. Succ might not be a complete BasicBlock, so don't assume
409     // that it ends with a non-phi instruction.
410     for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) {
411       PHINode *PN = dyn_cast<PHINode>(II);
412       if (!PN)
413         break;
414       int i;
415       while ((i = PN->getBasicBlockIndex(this)) >= 0)
416         PN->setIncomingBlock(i, New);
417     }
418   }
419 }
420
421 /// Return true if this basic block is a landing pad. I.e., it's
422 /// the destination of the 'unwind' edge of an invoke instruction.
423 bool BasicBlock::isLandingPad() const {
424   return isa<LandingPadInst>(getFirstNonPHI());
425 }
426
427 /// Return the landingpad instruction associated with the landing pad.
428 LandingPadInst *BasicBlock::getLandingPadInst() {
429   return dyn_cast<LandingPadInst>(getFirstNonPHI());
430 }
431 const LandingPadInst *BasicBlock::getLandingPadInst() const {
432   return dyn_cast<LandingPadInst>(getFirstNonPHI());
433 }