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
165Instruction* BasicBlock::getFirstNonPHI() {
166  for (Instruction &I : *this)
167    if (!isa<PHINode>(I))
168      return &I;
169  return nullptr;
170}
171
172Instruction* BasicBlock::getFirstNonPHIOrDbg() {
173  for (Instruction &I : *this)
174    if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I))
175      return &I;
176  return nullptr;
177}
178
179Instruction* 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
194BasicBlock::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
204void 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.
211BasicBlock *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).
224BasicBlock *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
238BasicBlock *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
246BasicBlock *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///
266void 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
336bool 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///
359BasicBlock *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
401void 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.
423bool BasicBlock::isLandingPad() const {
424  return isa<LandingPadInst>(getFirstNonPHI());
425}
426
427/// Return the landingpad instruction associated with the landing pad.
428LandingPadInst *BasicBlock::getLandingPadInst() {
429  return dyn_cast<LandingPadInst>(getFirstNonPHI());
430}
431const LandingPadInst *BasicBlock::getLandingPadInst() const {
432  return dyn_cast<LandingPadInst>(getFirstNonPHI());
433}
434