Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/IR/BasicBlock.cpp
Line
Count
Source (jump to first uncovered line)
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
39.9M
ValueSymbolTable *BasicBlock::getValueSymbolTable() {
28
39.9M
  if (Function *F = getParent())
29
24.7M
    return F->getValueSymbolTable();
30
15.2M
  return nullptr;
31
15.2M
}
32
33
74.1M
LLVMContext &BasicBlock::getContext() const {
34
74.1M
  return getType()->getContext();
35
74.1M
}
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
8.30M
  : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
44
8.30M
45
8.30M
  if (NewParent)
46
5.72M
    insertInto(NewParent, InsertBefore);
47
8.30M
  else
48
8.30M
    assert(!InsertBefore &&
49
8.30M
           "Cannot insert block before another block with no function!");
50
8.30M
51
8.30M
  setName(Name);
52
8.30M
}
53
54
5.72M
void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
55
5.72M
  assert(NewParent && "Expected a parent");
56
5.72M
  assert(!Parent && "Already has a parent");
57
5.72M
58
5.72M
  if (InsertBefore)
59
2.01M
    NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
60
5.72M
  else
61
3.71M
    NewParent->getBasicBlockList().push_back(this);
62
5.72M
}
63
64
4.74M
BasicBlock::~BasicBlock() {
65
4.74M
  // If the address of the block is taken and it is being deleted (e.g. because
66
4.74M
  // it is dead), this means that there is either a dangling constant expr
67
4.74M
  // hanging off the block, or an undefined use of the block (source code
68
4.74M
  // expecting the address of a label to keep the block alive even though there
69
4.74M
  // is no indirect branch).  Handle these cases by zapping the BlockAddress
70
4.74M
  // nodes.  There are no other possible uses at this point.
71
4.74M
  if (
hasAddressTaken()4.74M
) {
72
614
    assert(!use_empty() && "There should be at least one blockaddress!");
73
614
    Constant *Replacement =
74
614
      ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
75
1.22k
    while (
!use_empty()1.22k
) {
76
614
      BlockAddress *BA = cast<BlockAddress>(user_back());
77
614
      BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
78
614
                                                       BA->getType()));
79
614
      BA->destroyConstant();
80
614
    }
81
614
  }
82
4.74M
83
4.74M
  assert(getParent() == nullptr && "BasicBlock still linked into the program!");
84
4.74M
  dropAllReferences();
85
4.74M
  InstList.clear();
86
4.74M
}
87
88
12.7M
void BasicBlock::setParent(Function *parent) {
89
12.7M
  // Set Parent=parent, updating instruction symtab entries as appropriate.
90
12.7M
  InstList.setSymTabObject(&Parent, parent);
91
12.7M
}
92
93
1
void BasicBlock::removeFromParent() {
94
1
  getParent()->getBasicBlockList().remove(getIterator());
95
1
}
96
97
4.05M
iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
98
4.05M
  return getParent()->getBasicBlockList().erase(getIterator());
99
4.05M
}
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
44.9k
void BasicBlock::moveBefore(BasicBlock *MovePos) {
104
44.9k
  MovePos->getParent()->getBasicBlockList().splice(
105
44.9k
      MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
106
44.9k
}
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
115k
void BasicBlock::moveAfter(BasicBlock *MovePos) {
111
115k
  MovePos->getParent()->getBasicBlockList().splice(
112
115k
      ++MovePos->getIterator(), getParent()->getBasicBlockList(),
113
115k
      getIterator());
114
115k
}
115
116
388M
const Module *BasicBlock::getModule() const {
117
388M
  return getParent()->getParent();
118
388M
}
119
120
3.02G
const TerminatorInst *BasicBlock::getTerminator() const {
121
3.02G
  if (
InstList.empty()3.02G
)
return nullptr720k
;
122
3.02G
  return dyn_cast<TerminatorInst>(&InstList.back());
123
3.02G
}
124
125
26
const CallInst *BasicBlock::getTerminatingMustTailCall() const {
126
26
  if (InstList.empty())
127
0
    return nullptr;
128
26
  const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
129
26
  if (
!RI || 26
RI == &InstList.front()26
)
130
0
    return nullptr;
131
26
132
26
  const Instruction *Prev = RI->getPrevNode();
133
26
  if (!Prev)
134
0
    return nullptr;
135
26
136
26
  
if (Value *26
RV26
= RI->getReturnValue()) {
137
10
    if (RV != Prev)
138
0
      return nullptr;
139
10
140
10
    // Look through the optional bitcast.
141
10
    
if (auto *10
BI10
= dyn_cast<BitCastInst>(Prev)) {
142
6
      RV = BI->getOperand(0);
143
6
      Prev = BI->getPrevNode();
144
6
      if (
!Prev || 6
RV != Prev6
)
145
0
        return nullptr;
146
26
    }
147
10
  }
148
26
149
26
  
if (auto *26
CI26
= dyn_cast<CallInst>(Prev)) {
150
24
    if (CI->isMustTailCall())
151
24
      return CI;
152
2
  }
153
2
  return nullptr;
154
2
}
155
156
3.71M
const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
157
3.71M
  if (InstList.empty())
158
0
    return nullptr;
159
3.71M
  auto *RI = dyn_cast<ReturnInst>(&InstList.back());
160
3.71M
  if (
!RI || 3.71M
RI == &InstList.front()3.70M
)
161
572k
    return nullptr;
162
3.14M
163
3.14M
  
if (auto *3.14M
CI3.14M
= dyn_cast_or_null<CallInst>(RI->getPrevNode()))
164
1.73M
    
if (Function *1.73M
F1.73M
= CI->getCalledFunction())
165
1.53M
      
if (1.53M
F->getIntrinsicID() == Intrinsic::experimental_deoptimize1.53M
)
166
14
        return CI;
167
3.14M
168
3.14M
  return nullptr;
169
3.14M
}
170
171
35.6M
const Instruction* BasicBlock::getFirstNonPHI() const {
172
35.6M
  for (const Instruction &I : *this)
173
49.2M
    
if (49.2M
!isa<PHINode>(I)49.2M
)
174
35.6M
      return &I;
175
108
  return nullptr;
176
108
}
177
178
34.4M
const Instruction* BasicBlock::getFirstNonPHIOrDbg() const {
179
34.4M
  for (const Instruction &I : *this)
180
40.9M
    
if (40.9M
!isa<PHINode>(I) && 40.9M
!isa<DbgInfoIntrinsic>(I)34.4M
)
181
34.4M
      return &I;
182
18.4E
  return nullptr;
183
18.4E
}
184
185
81
const Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() const {
186
115
  for (const Instruction &I : *this) {
187
115
    if (
isa<PHINode>(I) || 115
isa<DbgInfoIntrinsic>(I)89
)
188
34
      continue;
189
81
190
81
    
if (auto *81
II81
= dyn_cast<IntrinsicInst>(&I))
191
0
      
if (0
II->getIntrinsicID() == Intrinsic::lifetime_start ||
192
0
          II->getIntrinsicID() == Intrinsic::lifetime_end)
193
0
        continue;
194
81
195
81
    return &I;
196
81
  }
197
0
  return nullptr;
198
0
}
199
200
2.95M
BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
201
2.95M
  const Instruction *FirstNonPHI = getFirstNonPHI();
202
2.95M
  if (!FirstNonPHI)
203
111
    return end();
204
2.95M
205
2.95M
  const_iterator InsertPt = FirstNonPHI->getIterator();
206
2.95M
  if (
InsertPt->isEHPad()2.95M
)
++InsertPt15.4k
;
207
2.95M
  return InsertPt;
208
2.95M
}
209
210
5.92M
void BasicBlock::dropAllReferences() {
211
5.92M
  for (Instruction &I : *this)
212
12.9M
    I.dropAllReferences();
213
5.92M
}
214
215
/// If this basic block has a single predecessor block,
216
/// return the block, otherwise return a null pointer.
217
278M
const BasicBlock *BasicBlock::getSinglePredecessor() const {
218
278M
  const_pred_iterator PI = pred_begin(this), E = pred_end(this);
219
278M
  if (
PI == E278M
)
return nullptr18.0M
; // No preds.
220
260M
  const BasicBlock *ThePred = *PI;
221
260M
  ++PI;
222
260M
  return (PI == E) ? 
ThePred158M
:
nullptr101M
/*multiple preds*/;
223
278M
}
224
225
/// If this basic block has a unique predecessor block,
226
/// return the block, otherwise return a null pointer.
227
/// Note that unique predecessor doesn't mean single edge, there can be
228
/// multiple edges from the unique predecessor to this block (for example
229
/// a switch statement with multiple cases having the same destination).
230
54.7M
const BasicBlock *BasicBlock::getUniquePredecessor() const {
231
54.7M
  const_pred_iterator PI = pred_begin(this), E = pred_end(this);
232
54.7M
  if (
PI == E54.7M
)
return nullptr5.83M
; // No preds.
233
48.9M
  const BasicBlock *PredBB = *PI;
234
48.9M
  ++PI;
235
49.2M
  for (;
PI != E49.2M
;
++PI340k
) {
236
17.6M
    if (*PI != PredBB)
237
17.3M
      return nullptr;
238
17.6M
    // The same predecessor appears multiple times in the predecessor list.
239
17.6M
    // This is OK.
240
17.6M
  }
241
31.5M
  return PredBB;
242
54.7M
}
243
244
66.7M
const BasicBlock *BasicBlock::getSingleSuccessor() const {
245
66.7M
  succ_const_iterator SI = succ_begin(this), E = succ_end(this);
246
66.7M
  if (
SI == E66.7M
)
return nullptr4.14M
; // no successors
247
62.5M
  const BasicBlock *TheSucc = *SI;
248
62.5M
  ++SI;
249
62.5M
  return (SI == E) ? 
TheSucc28.3M
:
nullptr34.2M
/* multiple successors */;
250
66.7M
}
251
252
34.8k
const BasicBlock *BasicBlock::getUniqueSuccessor() const {
253
34.8k
  succ_const_iterator SI = succ_begin(this), E = succ_end(this);
254
34.8k
  if (
SI == E34.8k
)
return nullptr3
; // No successors
255
34.8k
  const BasicBlock *SuccBB = *SI;
256
34.8k
  ++SI;
257
34.8k
  for (;
SI != E34.8k
;
++SI2
) {
258
20
    if (*SI != SuccBB)
259
18
      return nullptr;
260
20
    // The same successor appears multiple times in the successor list.
261
20
    // This is OK.
262
20
  }
263
34.7k
  return SuccBB;
264
34.8k
}
265
266
363k
iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
267
363k
  return make_range<phi_iterator>(dyn_cast<PHINode>(&front()), nullptr);
268
363k
}
269
270
/// This method is used to notify a BasicBlock that the
271
/// specified Predecessor of the block is no longer able to reach it.  This is
272
/// actually not used to update the Predecessor list, but is actually used to
273
/// update the PHI nodes that reside in the block.  Note that this should be
274
/// called while the predecessor still refers to this block.
275
///
276
void BasicBlock::removePredecessor(BasicBlock *Pred,
277
669k
                                   bool DontDeleteUselessPHIs) {
278
669k
  assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
279
669k
          find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
280
669k
         "removePredecessor: BB is not a predecessor!");
281
669k
282
669k
  if (
InstList.empty()669k
)
return0
;
283
669k
  PHINode *APN = dyn_cast<PHINode>(&front());
284
669k
  if (
!APN669k
)
return349k
; // Quick exit.
285
319k
286
319k
  // If there are exactly two predecessors, then we want to nuke the PHI nodes
287
319k
  // altogether.  However, we cannot do this, if this in this case:
288
319k
  //
289
319k
  //  Loop:
290
319k
  //    %x = phi [X, Loop]
291
319k
  //    %x2 = add %x, 1         ;; This would become %x2 = add %x2, 1
292
319k
  //    br Loop                 ;; %x2 does not dominate all uses
293
319k
  //
294
319k
  // This is because the PHI node input is actually taken from the predecessor
295
319k
  // basic block.  The only case this can happen is with a self loop, so we
296
319k
  // check for this case explicitly now.
297
319k
  //
298
319k
  unsigned max_idx = APN->getNumIncomingValues();
299
319k
  assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
300
319k
  if (
max_idx == 2319k
) {
301
71.2k
    BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
302
71.2k
303
71.2k
    // Disable PHI elimination!
304
71.2k
    if (
this == Other71.2k
)
max_idx = 399
;
305
71.2k
  }
306
319k
307
319k
  // <= Two predecessors BEFORE I remove one?
308
319k
  if (
max_idx <= 2 && 319k
!DontDeleteUselessPHIs71.3k
) {
309
41.3k
    // Yup, loop through and nuke the PHI nodes
310
89.3k
    while (PHINode *
PN89.3k
= dyn_cast<PHINode>(&front())) {
311
47.9k
      // Remove the predecessor first.
312
47.9k
      PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs);
313
47.9k
314
47.9k
      // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
315
47.9k
      if (
max_idx == 247.9k
) {
316
47.6k
        if (PN->getIncomingValue(0) != PN)
317
47.6k
          PN->replaceAllUsesWith(PN->getIncomingValue(0));
318
47.6k
        else
319
47.6k
          // We are left with an infinite loop with no entries: kill the PHI.
320
15
          PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
321
47.6k
        getInstList().pop_front();    // Remove the PHI node
322
47.6k
      }
323
47.9k
324
47.9k
      // If the PHI node already only had one entry, it got deleted by
325
47.9k
      // removeIncomingValue.
326
47.9k
    }
327
319k
  } else {
328
277k
    // Okay, now we know that we need to remove predecessor #pred_idx from all
329
277k
    // PHI nodes.  Iterate over each PHI node fixing them up
330
277k
    PHINode *PN;
331
599k
    for (iterator II = begin(); 
(PN = dyn_cast<PHINode>(II))599k
; ) {
332
321k
      ++II;
333
321k
      PN->removeIncomingValue(Pred, false);
334
321k
      // If all incoming values to the Phi are the same, we can replace the Phi
335
321k
      // with that value.
336
321k
      Value* PNV = nullptr;
337
321k
      if (
!DontDeleteUselessPHIs && 321k
(PNV = PN->hasConstantValue())254k
)
338
15.4k
        
if (15.4k
PNV != PN15.4k
) {
339
15.4k
          PN->replaceAllUsesWith(PNV);
340
15.4k
          PN->eraseFromParent();
341
15.4k
        }
342
321k
    }
343
277k
  }
344
669k
}
345
346
1.56M
bool BasicBlock::canSplitPredecessors() const {
347
1.56M
  const Instruction *FirstNonPHI = getFirstNonPHI();
348
1.56M
  if (isa<LandingPadInst>(FirstNonPHI))
349
8.32k
    return true;
350
1.56M
  // This is perhaps a little conservative because constructs like
351
1.56M
  // CleanupBlockInst are pretty easy to split.  However, SplitBlockPredecessors
352
1.56M
  // cannot handle such things just yet.
353
1.56M
  
if (1.56M
FirstNonPHI->isEHPad()1.56M
)
354
2
    return false;
355
1.56M
  return true;
356
1.56M
}
357
358
18.0M
bool BasicBlock::isLegalToHoistInto() const {
359
18.0M
  auto *Term = getTerminator();
360
18.0M
  // No terminator means the block is under construction.
361
18.0M
  if (!Term)
362
0
    return true;
363
18.0M
364
18.0M
  // If the block has no successors, there can be no instructions to hoist.
365
18.0M
  assert(Term->getNumSuccessors() > 0);
366
18.0M
367
18.0M
  // Instructions should not be hoisted across exception handling boundaries.
368
18.0M
  return !Term->isExceptional();
369
18.0M
}
370
371
/// This splits a basic block into two at the specified
372
/// instruction.  Note that all instructions BEFORE the specified iterator stay
373
/// as part of the original basic block, an unconditional branch is added to
374
/// the new BB, and the rest of the instructions in the BB are moved to the new
375
/// BB, including the old terminator.  This invalidates the iterator.
376
///
377
/// Note that this only works on well formed basic blocks (must have a
378
/// terminator), and 'I' must not be the end of instruction list (which would
379
/// cause a degenerate basic block to be formed, having a terminator inside of
380
/// the basic block).
381
///
382
306k
BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
383
306k
  assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
384
306k
  assert(I != InstList.end() &&
385
306k
         "Trying to get me to create degenerate basic block!");
386
306k
387
306k
  BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
388
306k
                                       this->getNextNode());
389
306k
390
306k
  // Save DebugLoc of split point before invalidating iterator.
391
306k
  DebugLoc Loc = I->getDebugLoc();
392
306k
  // Move all of the specified instructions from the original basic block into
393
306k
  // the new basic block.
394
306k
  New->getInstList().splice(New->end(), this->getInstList(), I, end());
395
306k
396
306k
  // Add a branch instruction to the newly formed basic block.
397
306k
  BranchInst *BI = BranchInst::Create(New, this);
398
306k
  BI->setDebugLoc(Loc);
399
306k
400
306k
  // Now we must loop through all of the successors of the New block (which
401
306k
  // _were_ the successors of the 'this' block), and update any PHI nodes in
402
306k
  // successors.  If there were PHI nodes in the successors, then they need to
403
306k
  // know that incoming branches will be from New, not from Old.
404
306k
  //
405
669k
  for (succ_iterator I = succ_begin(New), E = succ_end(New); 
I != E669k
;
++I362k
) {
406
362k
    // Loop over any phi nodes in the basic block, updating the BB field of
407
362k
    // incoming values...
408
362k
    BasicBlock *Successor = *I;
409
226k
    for (auto &PN : Successor->phis()) {
410
226k
      int Idx = PN.getBasicBlockIndex(this);
411
452k
      while (
Idx != -1452k
) {
412
226k
        PN.setIncomingBlock((unsigned)Idx, New);
413
226k
        Idx = PN.getBasicBlockIndex(this);
414
226k
      }
415
226k
    }
416
362k
  }
417
306k
  return New;
418
306k
}
419
420
3.19M
void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
421
3.19M
  TerminatorInst *TI = getTerminator();
422
3.19M
  if (!TI)
423
3.19M
    // Cope with being called on a BasicBlock that doesn't have a terminator
424
3.19M
    // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
425
213k
    return;
426
2.98M
  
for (BasicBlock *Succ : TI->successors()) 2.98M
{
427
1.48M
    // N.B. Succ might not be a complete BasicBlock, so don't assume
428
1.48M
    // that it ends with a non-phi instruction.
429
2.11M
    for (iterator II = Succ->begin(), IE = Succ->end(); 
II != IE2.11M
;
++II621k
) {
430
1.99M
      PHINode *PN = dyn_cast<PHINode>(II);
431
1.99M
      if (!PN)
432
1.36M
        break;
433
621k
      int i;
434
1.11M
      while ((i = PN->getBasicBlockIndex(this)) >= 0)
435
491k
        PN->setIncomingBlock(i, New);
436
1.99M
    }
437
1.48M
  }
438
3.19M
}
439
440
/// Return true if this basic block is a landing pad. I.e., it's
441
/// the destination of the 'unwind' edge of an invoke instruction.
442
1.61M
bool BasicBlock::isLandingPad() const {
443
1.61M
  return isa<LandingPadInst>(getFirstNonPHI());
444
1.61M
}
445
446
/// Return the landingpad instruction associated with the landing pad.
447
3.73M
const LandingPadInst *BasicBlock::getLandingPadInst() const {
448
3.73M
  return dyn_cast<LandingPadInst>(getFirstNonPHI());
449
3.73M
}