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