Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/IR/BasicBlock.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- BasicBlock.cpp - Implement BasicBlock related methods -------------===//
2
//
3
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4
// See https://llvm.org/LICENSE.txt for license information.
5
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6
//
7
//===----------------------------------------------------------------------===//
8
//
9
// This file implements the BasicBlock class for the IR library.
10
//
11
//===----------------------------------------------------------------------===//
12
13
#include "llvm/IR/BasicBlock.h"
14
#include "SymbolTableListTraitsImpl.h"
15
#include "llvm/ADT/STLExtras.h"
16
#include "llvm/IR/CFG.h"
17
#include "llvm/IR/Constants.h"
18
#include "llvm/IR/Instructions.h"
19
#include "llvm/IR/IntrinsicInst.h"
20
#include "llvm/IR/LLVMContext.h"
21
#include "llvm/IR/Type.h"
22
#include <algorithm>
23
24
using namespace llvm;
25
26
35.8M
ValueSymbolTable *BasicBlock::getValueSymbolTable() {
27
35.8M
  if (Function *F = getParent())
28
21.2M
    return F->getValueSymbolTable();
29
14.5M
  return nullptr;
30
14.5M
}
31
32
54.4M
LLVMContext &BasicBlock::getContext() const {
33
54.4M
  return getType()->getContext();
34
54.4M
}
35
36
// Explicit instantiation of SymbolTableListTraits since some of the methods
37
// are not in the public header file...
38
template class llvm::SymbolTableListTraits<Instruction>;
39
40
BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
41
                       BasicBlock *InsertBefore)
42
7.46M
  : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
43
7.46M
44
7.46M
  if (NewParent)
45
4.16M
    insertInto(NewParent, InsertBefore);
46
7.46M
  else
47
7.46M
    assert(!InsertBefore &&
48
7.46M
           "Cannot insert block before another block with no function!");
49
7.46M
50
7.46M
  setName(Name);
51
7.46M
}
52
53
4.16M
void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
54
4.16M
  assert(NewParent && "Expected a parent");
55
4.16M
  assert(!Parent && "Already has a parent");
56
4.16M
57
4.16M
  if (InsertBefore)
58
1.70M
    NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
59
2.46M
  else
60
2.46M
    NewParent->getBasicBlockList().push_back(this);
61
4.16M
}
62
63
5.16M
BasicBlock::~BasicBlock() {
64
5.16M
  // If the address of the block is taken and it is being deleted (e.g. because
65
5.16M
  // it is dead), this means that there is either a dangling constant expr
66
5.16M
  // hanging off the block, or an undefined use of the block (source code
67
5.16M
  // expecting the address of a label to keep the block alive even though there
68
5.16M
  // is no indirect branch).  Handle these cases by zapping the BlockAddress
69
5.16M
  // nodes.  There are no other possible uses at this point.
70
5.16M
  if (hasAddressTaken()) {
71
938
    assert(!use_empty() && "There should be at least one blockaddress!");
72
938
    Constant *Replacement =
73
938
      ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
74
1.87k
    while (!use_empty()) {
75
938
      BlockAddress *BA = cast<BlockAddress>(user_back());
76
938
      BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
77
938
                                                       BA->getType()));
78
938
      BA->destroyConstant();
79
938
    }
80
938
  }
81
5.16M
82
5.16M
  assert(getParent() == nullptr && "BasicBlock still linked into the program!");
83
5.16M
  dropAllReferences();
84
5.16M
  InstList.clear();
85
5.16M
}
86
87
11.9M
void BasicBlock::setParent(Function *parent) {
88
11.9M
  // Set Parent=parent, updating instruction symtab entries as appropriate.
89
11.9M
  InstList.setSymTabObject(&Parent, parent);
90
11.9M
}
91
92
iterator_range<filter_iterator<BasicBlock::const_iterator,
93
                               std::function<bool(const Instruction &)>>>
94
1.92k
BasicBlock::instructionsWithoutDebug() const {
95
4.47k
  std::function<bool(const Instruction &)> Fn = [](const Instruction &I) {
96
4.47k
    return !isa<DbgInfoIntrinsic>(I);
97
4.47k
  };
98
1.92k
  return make_filter_range(*this, Fn);
99
1.92k
}
100
101
iterator_range<filter_iterator<BasicBlock::iterator,
102
                               std::function<bool(Instruction &)>>>
103
29.6M
BasicBlock::instructionsWithoutDebug() {
104
38.1M
  std::function<bool(Instruction &)> Fn = [](Instruction &I) {
105
38.1M
    return !isa<DbgInfoIntrinsic>(I);
106
38.1M
  };
107
29.6M
  return make_filter_range(*this, Fn);
108
29.6M
}
109
110
617k
void BasicBlock::removeFromParent() {
111
617k
  getParent()->getBasicBlockList().remove(getIterator());
112
617k
}
113
114
3.54M
iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
115
3.54M
  return getParent()->getBasicBlockList().erase(getIterator());
116
3.54M
}
117
118
/// Unlink this basic block from its current function and
119
/// insert it into the function that MovePos lives in, right before MovePos.
120
52.1k
void BasicBlock::moveBefore(BasicBlock *MovePos) {
121
52.1k
  MovePos->getParent()->getBasicBlockList().splice(
122
52.1k
      MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
123
52.1k
}
124
125
/// Unlink this basic block from its current function and
126
/// insert it into the function that MovePos lives in, right after MovePos.
127
261k
void BasicBlock::moveAfter(BasicBlock *MovePos) {
128
261k
  MovePos->getParent()->getBasicBlockList().splice(
129
261k
      ++MovePos->getIterator(), getParent()->getBasicBlockList(),
130
261k
      getIterator());
131
261k
}
132
133
291M
const Module *BasicBlock::getModule() const {
134
291M
  return getParent()->getParent();
135
291M
}
136
137
2.12G
const Instruction *BasicBlock::getTerminator() const {
138
2.12G
  if (InstList.empty() || 
!InstList.back().isTerminator()2.12G
)
139
1.28M
    return nullptr;
140
2.12G
  return &InstList.back();
141
2.12G
}
142
143
2.98M
const CallInst *BasicBlock::getTerminatingMustTailCall() const {
144
2.98M
  if (InstList.empty())
145
0
    return nullptr;
146
2.98M
  const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
147
2.98M
  if (!RI || 
RI == &InstList.front()568k
)
148
2.51M
    return nullptr;
149
470k
150
470k
  const Instruction *Prev = RI->getPrevNode();
151
470k
  if (!Prev)
152
0
    return nullptr;
153
470k
154
470k
  if (Value *RV = RI->getReturnValue()) {
155
331k
    if (RV != Prev)
156
122k
      return nullptr;
157
209k
158
209k
    // Look through the optional bitcast.
159
209k
    if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
160
17.4k
      RV = BI->getOperand(0);
161
17.4k
      Prev = BI->getPrevNode();
162
17.4k
      if (!Prev || 
RV != Prev8.20k
)
163
10.7k
        return nullptr;
164
336k
    }
165
209k
  }
166
336k
167
336k
  if (auto *CI = dyn_cast<CallInst>(Prev)) {
168
169k
    if (CI->isMustTailCall())
169
71
      return CI;
170
336k
  }
171
336k
  return nullptr;
172
336k
}
173
174
3.02M
const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
175
3.02M
  if (InstList.empty())
176
0
    return nullptr;
177
3.02M
  auto *RI = dyn_cast<ReturnInst>(&InstList.back());
178
3.02M
  if (!RI || 
RI == &InstList.front()2.91M
)
179
559k
    return nullptr;
180
2.46M
181
2.46M
  if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
182
1.09M
    if (Function *F = CI->getCalledFunction())
183
979k
      if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
184
76
        return CI;
185
2.46M
186
2.46M
  return nullptr;
187
2.46M
}
188
189
20.4M
const Instruction* BasicBlock::getFirstNonPHI() const {
190
20.4M
  for (const Instruction &I : *this)
191
29.0M
    if (!isa<PHINode>(I))
192
20.4M
      return &I;
193
20.4M
  
return nullptr76
;
194
20.4M
}
195
196
24.4M
const Instruction* BasicBlock::getFirstNonPHIOrDbg() const {
197
24.4M
  for (const Instruction &I : *this)
198
28.8M
    if (!isa<PHINode>(I) && 
!isa<DbgInfoIntrinsic>(I)24.4M
)
199
24.4M
      return &I;
200
18.4E
  return nullptr;
201
24.4M
}
202
203
282
const Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() const {
204
314
  for (const Instruction &I : *this) {
205
314
    if (isa<PHINode>(I) || 
isa<DbgInfoIntrinsic>(I)288
)
206
32
      continue;
207
282
208
282
    if (I.isLifetimeStartOrEnd())
209
0
      continue;
210
282
211
282
    return &I;
212
282
  }
213
282
  
return nullptr0
;
214
282
}
215
216
1.98M
BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
217
1.98M
  const Instruction *FirstNonPHI = getFirstNonPHI();
218
1.98M
  if (!FirstNonPHI)
219
80
    return end();
220
1.98M
221
1.98M
  const_iterator InsertPt = FirstNonPHI->getIterator();
222
1.98M
  if (InsertPt->isEHPad()) 
++InsertPt27.0k
;
223
1.98M
  return InsertPt;
224
1.98M
}
225
226
6.63M
void BasicBlock::dropAllReferences() {
227
6.63M
  for (Instruction &I : *this)
228
18.4M
    I.dropAllReferences();
229
6.63M
}
230
231
/// If this basic block has a single predecessor block,
232
/// return the block, otherwise return a null pointer.
233
201M
const BasicBlock *BasicBlock::getSinglePredecessor() const {
234
201M
  const_pred_iterator PI = pred_begin(this), E = pred_end(this);
235
201M
  if (PI == E) 
return nullptr15.5M
; // No preds.
236
185M
  const BasicBlock *ThePred = *PI;
237
185M
  ++PI;
238
185M
  return (PI == E) ? 
ThePred110M
:
nullptr75.4M
/*multiple preds*/;
239
185M
}
240
241
/// If this basic block has a unique predecessor block,
242
/// return the block, otherwise return a null pointer.
243
/// Note that unique predecessor doesn't mean single edge, there can be
244
/// multiple edges from the unique predecessor to this block (for example
245
/// a switch statement with multiple cases having the same destination).
246
37.8M
const BasicBlock *BasicBlock::getUniquePredecessor() const {
247
37.8M
  const_pred_iterator PI = pred_begin(this), E = pred_end(this);
248
37.8M
  if (PI == E) 
return nullptr4.66M
; // No preds.
249
33.2M
  const BasicBlock *PredBB = *PI;
250
33.2M
  ++PI;
251
33.4M
  for (;PI != E; 
++PI211k
) {
252
12.1M
    if (*PI != PredBB)
253
11.9M
      return nullptr;
254
12.1M
    // The same predecessor appears multiple times in the predecessor list.
255
12.1M
    // This is OK.
256
12.1M
  }
257
33.2M
  
return PredBB21.2M
;
258
33.2M
}
259
260
1.63M
bool BasicBlock::hasNPredecessors(unsigned N) const {
261
1.63M
  return hasNItems(pred_begin(this), pred_end(this), N);
262
1.63M
}
263
264
10.0M
bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const {
265
10.0M
  return hasNItemsOrMore(pred_begin(this), pred_end(this), N);
266
10.0M
}
267
268
46.4M
const BasicBlock *BasicBlock::getSingleSuccessor() const {
269
46.4M
  succ_const_iterator SI = succ_begin(this), E = succ_end(this);
270
46.4M
  if (SI == E) 
return nullptr3.28M
; // no successors
271
43.1M
  const BasicBlock *TheSucc = *SI;
272
43.1M
  ++SI;
273
43.1M
  return (SI == E) ? 
TheSucc18.2M
:
nullptr24.9M
/* multiple successors */;
274
43.1M
}
275
276
19.9M
const BasicBlock *BasicBlock::getUniqueSuccessor() const {
277
19.9M
  succ_const_iterator SI = succ_begin(this), E = succ_end(this);
278
19.9M
  if (SI == E) 
return nullptr4
; // No successors
279
19.9M
  const BasicBlock *SuccBB = *SI;
280
19.9M
  ++SI;
281
19.9M
  for (;SI != E; 
++SI16.3k
) {
282
19.4M
    if (*SI != SuccBB)
283
19.4M
      return nullptr;
284
19.4M
    // The same successor appears multiple times in the successor list.
285
19.4M
    // This is OK.
286
19.4M
  }
287
19.9M
  
return SuccBB504k
;
288
19.9M
}
289
290
46.0M
iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
291
46.0M
  PHINode *P = empty() ? 
nullptr351
:
dyn_cast<PHINode>(&*begin())46.0M
;
292
46.0M
  return make_range<phi_iterator>(P, nullptr);
293
46.0M
}
294
295
/// This method is used to notify a BasicBlock that the
296
/// specified Predecessor of the block is no longer able to reach it.  This is
297
/// actually not used to update the Predecessor list, but is actually used to
298
/// update the PHI nodes that reside in the block.  Note that this should be
299
/// called while the predecessor still refers to this block.
300
///
301
void BasicBlock::removePredecessor(BasicBlock *Pred,
302
542k
                                   bool KeepOneInputPHIs) {
303
542k
  assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
304
542k
          find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
305
542k
         "removePredecessor: BB is not a predecessor!");
306
542k
307
542k
  if (InstList.empty()) 
return0
;
308
542k
  PHINode *APN = dyn_cast<PHINode>(&front());
309
542k
  if (!APN) 
return316k
; // Quick exit.
310
225k
311
225k
  // If there are exactly two predecessors, then we want to nuke the PHI nodes
312
225k
  // altogether.  However, we cannot do this, if this in this case:
313
225k
  //
314
225k
  //  Loop:
315
225k
  //    %x = phi [X, Loop]
316
225k
  //    %x2 = add %x, 1         ;; This would become %x2 = add %x2, 1
317
225k
  //    br Loop                 ;; %x2 does not dominate all uses
318
225k
  //
319
225k
  // This is because the PHI node input is actually taken from the predecessor
320
225k
  // basic block.  The only case this can happen is with a self loop, so we
321
225k
  // check for this case explicitly now.
322
225k
  //
323
225k
  unsigned max_idx = APN->getNumIncomingValues();
324
225k
  assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
325
225k
  if (max_idx == 2) {
326
70.6k
    BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
327
70.6k
328
70.6k
    // Disable PHI elimination!
329
70.6k
    if (this == Other) 
max_idx = 3523
;
330
70.6k
  }
331
225k
332
225k
  // <= Two predecessors BEFORE I remove one?
333
225k
  if (max_idx <= 2 && 
!KeepOneInputPHIs70.3k
) {
334
33.3k
    // Yup, loop through and nuke the PHI nodes
335
72.5k
    while (PHINode *PN = dyn_cast<PHINode>(&front())) {
336
39.2k
      // Remove the predecessor first.
337
39.2k
      PN->removeIncomingValue(Pred, !KeepOneInputPHIs);
338
39.2k
339
39.2k
      // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
340
39.2k
      if (max_idx == 2) {
341
38.9k
        if (PN->getIncomingValue(0) != PN)
342
38.9k
          PN->replaceAllUsesWith(PN->getIncomingValue(0));
343
11
        else
344
11
          // We are left with an infinite loop with no entries: kill the PHI.
345
11
          PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
346
38.9k
        getInstList().pop_front();    // Remove the PHI node
347
38.9k
      }
348
39.2k
349
39.2k
      // If the PHI node already only had one entry, it got deleted by
350
39.2k
      // removeIncomingValue.
351
39.2k
    }
352
192k
  } else {
353
192k
    // Okay, now we know that we need to remove predecessor #pred_idx from all
354
192k
    // PHI nodes.  Iterate over each PHI node fixing them up
355
192k
    PHINode *PN;
356
425k
    for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
357
232k
      ++II;
358
232k
      PN->removeIncomingValue(Pred, false);
359
232k
      // If all incoming values to the Phi are the same, we can replace the Phi
360
232k
      // with that value.
361
232k
      Value* PNV = nullptr;
362
232k
      if (!KeepOneInputPHIs && 
(PNV = PN->hasConstantValue())155k
)
363
12.6k
        if (PNV != PN) {
364
12.6k
          PN->replaceAllUsesWith(PNV);
365
12.6k
          PN->eraseFromParent();
366
12.6k
        }
367
232k
    }
368
192k
  }
369
225k
}
370
371
1.50M
bool BasicBlock::canSplitPredecessors() const {
372
1.50M
  const Instruction *FirstNonPHI = getFirstNonPHI();
373
1.50M
  if (isa<LandingPadInst>(FirstNonPHI))
374
12.7k
    return true;
375
1.49M
  // This is perhaps a little conservative because constructs like
376
1.49M
  // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
377
1.49M
  // cannot handle such things just yet.
378
1.49M
  if (FirstNonPHI->isEHPad())
379
10
    return false;
380
1.49M
  return true;
381
1.49M
}
382
383
11.1M
bool BasicBlock::isLegalToHoistInto() const {
384
11.1M
  auto *Term = getTerminator();
385
11.1M
  // No terminator means the block is under construction.
386
11.1M
  if (!Term)
387
0
    return true;
388
11.1M
389
11.1M
  // If the block has no successors, there can be no instructions to hoist.
390
11.1M
  assert(Term->getNumSuccessors() > 0);
391
11.1M
392
11.1M
  // Instructions should not be hoisted across exception handling boundaries.
393
11.1M
  return !Term->isExceptionalTerminator();
394
11.1M
}
395
396
/// This splits a basic block into two at the specified
397
/// instruction.  Note that all instructions BEFORE the specified iterator stay
398
/// as part of the original basic block, an unconditional branch is added to
399
/// the new BB, and the rest of the instructions in the BB are moved to the new
400
/// BB, including the old terminator.  This invalidates the iterator.
401
///
402
/// Note that this only works on well formed basic blocks (must have a
403
/// terminator), and 'I' must not be the end of instruction list (which would
404
/// cause a degenerate basic block to be formed, having a terminator inside of
405
/// the basic block).
406
///
407
307k
BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
408
307k
  assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
409
307k
  assert(I != InstList.end() &&
410
307k
         "Trying to get me to create degenerate basic block!");
411
307k
412
307k
  BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
413
307k
                                       this->getNextNode());
414
307k
415
307k
  // Save DebugLoc of split point before invalidating iterator.
416
307k
  DebugLoc Loc = I->getDebugLoc();
417
307k
  // Move all of the specified instructions from the original basic block into
418
307k
  // the new basic block.
419
307k
  New->getInstList().splice(New->end(), this->getInstList(), I, end());
420
307k
421
307k
  // Add a branch instruction to the newly formed basic block.
422
307k
  BranchInst *BI = BranchInst::Create(New, this);
423
307k
  BI->setDebugLoc(Loc);
424
307k
425
307k
  // Now we must loop through all of the successors of the New block (which
426
307k
  // _were_ the successors of the 'this' block), and update any PHI nodes in
427
307k
  // successors.  If there were PHI nodes in the successors, then they need to
428
307k
  // know that incoming branches will be from New, not from Old (this).
429
307k
  //
430
307k
  New->replaceSuccessorsPhiUsesWith(this, New);
431
307k
  return New;
432
307k
}
433
434
3.11M
void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) {
435
3.11M
  // N.B. This might not be a complete BasicBlock, so don't assume
436
3.11M
  // that it ends with a non-phi instruction.
437
4.87M
  for (iterator II = begin(), IE = end(); II != IE; 
++II1.75M
) {
438
4.71M
    PHINode *PN = dyn_cast<PHINode>(II);
439
4.71M
    if (!PN)
440
2.96M
      break;
441
1.75M
    PN->replaceIncomingBlockWith(Old, New);
442
1.75M
  }
443
3.11M
}
444
445
void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *Old,
446
3.25M
                                              BasicBlock *New) {
447
3.25M
  Instruction *TI = getTerminator();
448
3.25M
  if (!TI)
449
299k
    // Cope with being called on a BasicBlock that doesn't have a terminator
450
299k
    // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
451
299k
    return;
452
3.11M
  
llvm::for_each(successors(TI), [Old, New](BasicBlock *Succ) 2.95M
{
453
3.11M
    Succ->replacePhiUsesWith(Old, New);
454
3.11M
  });
455
2.95M
}
456
457
2.95M
void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
458
2.95M
  this->replaceSuccessorsPhiUsesWith(this, New);
459
2.95M
}
460
461
/// Return true if this basic block is a landing pad. I.e., it's
462
/// the destination of the 'unwind' edge of an invoke instruction.
463
1.34M
bool BasicBlock::isLandingPad() const {
464
1.34M
  return isa<LandingPadInst>(getFirstNonPHI());
465
1.34M
}
466
467
/// Return the landingpad instruction associated with the landing pad.
468
2.54M
const LandingPadInst *BasicBlock::getLandingPadInst() const {
469
2.54M
  return dyn_cast<LandingPadInst>(getFirstNonPHI());
470
2.54M
}
471
472
3.28M
Optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
473
3.28M
  const Instruction *TI = getTerminator();
474
3.28M
  if (MDNode *MDIrrLoopHeader =
475
32
      TI->getMetadata(LLVMContext::MD_irr_loop)) {
476
32
    MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0));
477
32
    if (MDName->getString().equals("loop_header_weight")) {
478
32
      auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1));
479
32
      return Optional<uint64_t>(CI->getValue().getZExtValue());
480
32
    }
481
3.28M
  }
482
3.28M
  return Optional<uint64_t>();
483
3.28M
}
484
485
1
BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
486
2
  while (isa<DbgInfoIntrinsic>(It))
487
1
    ++It;
488
1
  return It;
489
1
}