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
25using namespace llvm;
26
27ValueSymbolTable *BasicBlock::getValueSymbolTable() {
28  if (Function *F = getParent())
29    return &F->getValueSymbolTable();
30  return nullptr;
31}
32
33LLVMContext &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...
39template class llvm::SymbolTableListTraits<Instruction>;
40
41BasicBlock::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
54void 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
64BasicBlock::~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
88void BasicBlock::setParent(Function *parent) {
89  // Set Parent=parent, updating instruction symtab entries as appropriate.
90  InstList.setSymTabObject(&Parent, parent);
91}
92
93void BasicBlock::removeFromParent() {
94  getParent()->getBasicBlockList().remove(getIterator());
95}
96
97iplist<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.
103void 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.
110void BasicBlock::moveAfter(BasicBlock *MovePos) {
111  MovePos->getParent()->getBasicBlockList().splice(
112      ++MovePos->getIterator(), getParent()->getBasicBlockList(),
113      getIterator());
114}
115
116const Module *BasicBlock::getModule() const {
117  return getParent()->getParent();
118}
119
120Module *BasicBlock::getModule() {
121  return getParent()->getParent();
122}
123
124TerminatorInst *BasicBlock::getTerminator() {
125  if (InstList.empty()) return nullptr;
126  return dyn_cast<TerminatorInst>(&InstList.back());
127}
128
129const TerminatorInst *BasicBlock::getTerminator() const {
130  if (InstList.empty()) return nullptr;
131  return dyn_cast<TerminatorInst>(&InstList.back());
132}
133
134CallInst *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
165CallInst *BasicBlock::getTerminatingDeoptimizeCall() {
166  if (InstList.empty())
167    return nullptr;
168  auto *RI = dyn_cast<ReturnInst>(&InstList.back());
169  if (!RI || RI == &InstList.front())
170    return nullptr;
171
172  if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
173    if (Function *F = CI->getCalledFunction())
174      if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
175        return CI;
176
177  return nullptr;
178}
179
180Instruction* BasicBlock::getFirstNonPHI() {
181  for (Instruction &I : *this)
182    if (!isa<PHINode>(I))
183      return &I;
184  return nullptr;
185}
186
187Instruction* BasicBlock::getFirstNonPHIOrDbg() {
188  for (Instruction &I : *this)
189    if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I))
190      return &I;
191  return nullptr;
192}
193
194Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() {
195  for (Instruction &I : *this) {
196    if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
197      continue;
198
199    if (auto *II = dyn_cast<IntrinsicInst>(&I))
200      if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
201          II->getIntrinsicID() == Intrinsic::lifetime_end)
202        continue;
203
204    return &I;
205  }
206  return nullptr;
207}
208
209BasicBlock::iterator BasicBlock::getFirstInsertionPt() {
210  Instruction *FirstNonPHI = getFirstNonPHI();
211  if (!FirstNonPHI)
212    return end();
213
214  iterator InsertPt = FirstNonPHI->getIterator();
215  if (InsertPt->isEHPad()) ++InsertPt;
216  return InsertPt;
217}
218
219void BasicBlock::dropAllReferences() {
220  for (Instruction &I : *this)
221    I.dropAllReferences();
222}
223
224/// If this basic block has a single predecessor block,
225/// return the block, otherwise return a null pointer.
226BasicBlock *BasicBlock::getSinglePredecessor() {
227  pred_iterator PI = pred_begin(this), E = pred_end(this);
228  if (PI == E) return nullptr;         // No preds.
229  BasicBlock *ThePred = *PI;
230  ++PI;
231  return (PI == E) ? ThePred : nullptr /*multiple preds*/;
232}
233
234/// If this basic block has a unique predecessor block,
235/// return the block, otherwise return a null pointer.
236/// Note that unique predecessor doesn't mean single edge, there can be
237/// multiple edges from the unique predecessor to this block (for example
238/// a switch statement with multiple cases having the same destination).
239BasicBlock *BasicBlock::getUniquePredecessor() {
240  pred_iterator PI = pred_begin(this), E = pred_end(this);
241  if (PI == E) return nullptr; // No preds.
242  BasicBlock *PredBB = *PI;
243  ++PI;
244  for (;PI != E; ++PI) {
245    if (*PI != PredBB)
246      return nullptr;
247    // The same predecessor appears multiple times in the predecessor list.
248    // This is OK.
249  }
250  return PredBB;
251}
252
253BasicBlock *BasicBlock::getSingleSuccessor() {
254  succ_iterator SI = succ_begin(this), E = succ_end(this);
255  if (SI == E) return nullptr; // no successors
256  BasicBlock *TheSucc = *SI;
257  ++SI;
258  return (SI == E) ? TheSucc : nullptr /* multiple successors */;
259}
260
261BasicBlock *BasicBlock::getUniqueSuccessor() {
262  succ_iterator SI = succ_begin(this), E = succ_end(this);
263  if (SI == E) return nullptr; // No successors
264  BasicBlock *SuccBB = *SI;
265  ++SI;
266  for (;SI != E; ++SI) {
267    if (*SI != SuccBB)
268      return nullptr;
269    // The same successor appears multiple times in the successor list.
270    // This is OK.
271  }
272  return SuccBB;
273}
274
275/// This method is used to notify a BasicBlock that the
276/// specified Predecessor of the block is no longer able to reach it.  This is
277/// actually not used to update the Predecessor list, but is actually used to
278/// update the PHI nodes that reside in the block.  Note that this should be
279/// called while the predecessor still refers to this block.
280///
281void BasicBlock::removePredecessor(BasicBlock *Pred,
282                                   bool DontDeleteUselessPHIs) {
283  assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
284          find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
285         "removePredecessor: BB is not a predecessor!");
286
287  if (InstList.empty()) return;
288  PHINode *APN = dyn_cast<PHINode>(&front());
289  if (!APN) return;   // Quick exit.
290
291  // If there are exactly two predecessors, then we want to nuke the PHI nodes
292  // altogether.  However, we cannot do this, if this in this case:
293  //
294  //  Loop:
295  //    %x = phi [X, Loop]
296  //    %x2 = add %x, 1         ;; This would become %x2 = add %x2, 1
297  //    br Loop                 ;; %x2 does not dominate all uses
298  //
299  // This is because the PHI node input is actually taken from the predecessor
300  // basic block.  The only case this can happen is with a self loop, so we
301  // check for this case explicitly now.
302  //
303  unsigned max_idx = APN->getNumIncomingValues();
304  assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
305  if (max_idx == 2) {
306    BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
307
308    // Disable PHI elimination!
309    if (this == Other) max_idx = 3;
310  }
311
312  // <= Two predecessors BEFORE I remove one?
313  if (max_idx <= 2 && !DontDeleteUselessPHIs) {
314    // Yup, loop through and nuke the PHI nodes
315    while (PHINode *PN = dyn_cast<PHINode>(&front())) {
316      // Remove the predecessor first.
317      PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs);
318
319      // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
320      if (max_idx == 2) {
321        if (PN->getIncomingValue(0) != PN)
322          PN->replaceAllUsesWith(PN->getIncomingValue(0));
323        else
324          // We are left with an infinite loop with no entries: kill the PHI.
325          PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
326        getInstList().pop_front();    // Remove the PHI node
327      }
328
329      // If the PHI node already only had one entry, it got deleted by
330      // removeIncomingValue.
331    }
332  } else {
333    // Okay, now we know that we need to remove predecessor #pred_idx from all
334    // PHI nodes.  Iterate over each PHI node fixing them up
335    PHINode *PN;
336    for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
337      ++II;
338      PN->removeIncomingValue(Pred, false);
339      // If all incoming values to the Phi are the same, we can replace the Phi
340      // with that value.
341      Value* PNV = nullptr;
342      if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue()))
343        if (PNV != PN) {
344          PN->replaceAllUsesWith(PNV);
345          PN->eraseFromParent();
346        }
347    }
348  }
349}
350
351bool BasicBlock::canSplitPredecessors() const {
352  const Instruction *FirstNonPHI = getFirstNonPHI();
353  if (isa<LandingPadInst>(FirstNonPHI))
354    return true;
355  // This is perhaps a little conservative because constructs like
356  // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
357  // cannot handle such things just yet.
358  if (FirstNonPHI->isEHPad())
359    return false;
360  return true;
361}
362
363/// This splits a basic block into two at the specified
364/// instruction.  Note that all instructions BEFORE the specified iterator stay
365/// as part of the original basic block, an unconditional branch is added to
366/// the new BB, and the rest of the instructions in the BB are moved to the new
367/// BB, including the old terminator.  This invalidates the iterator.
368///
369/// Note that this only works on well formed basic blocks (must have a
370/// terminator), and 'I' must not be the end of instruction list (which would
371/// cause a degenerate basic block to be formed, having a terminator inside of
372/// the basic block).
373///
374BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
375  assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
376  assert(I != InstList.end() &&
377         "Trying to get me to create degenerate basic block!");
378
379  BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
380                                       this->getNextNode());
381
382  // Save DebugLoc of split point before invalidating iterator.
383  DebugLoc Loc = I->getDebugLoc();
384  // Move all of the specified instructions from the original basic block into
385  // the new basic block.
386  New->getInstList().splice(New->end(), this->getInstList(), I, end());
387
388  // Add a branch instruction to the newly formed basic block.
389  BranchInst *BI = BranchInst::Create(New, this);
390  BI->setDebugLoc(Loc);
391
392  // Now we must loop through all of the successors of the New block (which
393  // _were_ the successors of the 'this' block), and update any PHI nodes in
394  // successors.  If there were PHI nodes in the successors, then they need to
395  // know that incoming branches will be from New, not from Old.
396  //
397  for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) {
398    // Loop over any phi nodes in the basic block, updating the BB field of
399    // incoming values...
400    BasicBlock *Successor = *I;
401    PHINode *PN;
402    for (BasicBlock::iterator II = Successor->begin();
403         (PN = dyn_cast<PHINode>(II)); ++II) {
404      int IDX = PN->getBasicBlockIndex(this);
405      while (IDX != -1) {
406        PN->setIncomingBlock((unsigned)IDX, New);
407        IDX = PN->getBasicBlockIndex(this);
408      }
409    }
410  }
411  return New;
412}
413
414void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
415  TerminatorInst *TI = getTerminator();
416  if (!TI)
417    // Cope with being called on a BasicBlock that doesn't have a terminator
418    // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
419    return;
420  for (BasicBlock *Succ : TI->successors()) {
421    // N.B. Succ might not be a complete BasicBlock, so don't assume
422    // that it ends with a non-phi instruction.
423    for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) {
424      PHINode *PN = dyn_cast<PHINode>(II);
425      if (!PN)
426        break;
427      int i;
428      while ((i = PN->getBasicBlockIndex(this)) >= 0)
429        PN->setIncomingBlock(i, New);
430    }
431  }
432}
433
434/// Return true if this basic block is a landing pad. I.e., it's
435/// the destination of the 'unwind' edge of an invoke instruction.
436bool BasicBlock::isLandingPad() const {
437  return isa<LandingPadInst>(getFirstNonPHI());
438}
439
440/// Return the landingpad instruction associated with the landing pad.
441LandingPadInst *BasicBlock::getLandingPadInst() {
442  return dyn_cast<LandingPadInst>(getFirstNonPHI());
443}
444const LandingPadInst *BasicBlock::getLandingPadInst() const {
445  return dyn_cast<LandingPadInst>(getFirstNonPHI());
446}
447