Line data Source code
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 33390211 : ValueSymbolTable *BasicBlock::getValueSymbolTable() {
28 33390211 : if (Function *F = getParent())
29 20043689 : return F->getValueSymbolTable();
30 : return nullptr;
31 : }
32 :
33 9871909 : LLVMContext &BasicBlock::getContext() const {
34 9871909 : return getType()->getContext();
35 : }
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 8075093 : BasicBlock::BasicBlock(LLVMContext &C, const Twine &Name, Function *NewParent,
42 8075093 : BasicBlock *InsertBefore)
43 8075093 : : Value(Type::getLabelTy(C), Value::BasicBlockVal), Parent(nullptr) {
44 :
45 8075093 : if (NewParent)
46 1812922 : insertInto(NewParent, InsertBefore);
47 : else
48 : assert(!InsertBefore &&
49 : "Cannot insert block before another block with no function!");
50 :
51 8075093 : setName(Name);
52 8075093 : }
53 :
54 1812994 : void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) {
55 : assert(NewParent && "Expected a parent");
56 : assert(!Parent && "Already has a parent");
57 :
58 1812994 : if (InsertBefore)
59 433314 : NewParent->getBasicBlockList().insert(InsertBefore->getIterator(), this);
60 : else
61 1379680 : NewParent->getBasicBlockList().push_back(this);
62 1812994 : }
63 :
64 10162083 : BasicBlock::~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 5081041 : if (hasAddressTaken()) {
72 : assert(!use_empty() && "There should be at least one blockaddress!");
73 : Constant *Replacement =
74 878 : ConstantInt::get(llvm::Type::getInt32Ty(getContext()), 1);
75 1756 : while (!use_empty()) {
76 : BlockAddress *BA = cast<BlockAddress>(user_back());
77 878 : BA->replaceAllUsesWith(ConstantExpr::getIntToPtr(Replacement,
78 : BA->getType()));
79 878 : BA->destroyConstant();
80 : }
81 : }
82 :
83 : assert(getParent() == nullptr && "BasicBlock still linked into the program!");
84 5081041 : dropAllReferences();
85 5081042 : InstList.clear();
86 5081042 : }
87 :
88 11536666 : void BasicBlock::setParent(Function *parent) {
89 : // Set Parent=parent, updating instruction symtab entries as appropriate.
90 11536666 : InstList.setSymTabObject(&Parent, parent);
91 11536666 : }
92 :
93 : iterator_range<filter_iterator<BasicBlock::const_iterator,
94 : std::function<bool(const Instruction &)>>>
95 1616 : BasicBlock::instructionsWithoutDebug() const {
96 : std::function<bool(const Instruction &)> Fn = [](const Instruction &I) {
97 3894 : return !isa<DbgInfoIntrinsic>(I);
98 : };
99 3232 : return make_filter_range(*this, Fn);
100 : }
101 :
102 : iterator_range<filter_iterator<BasicBlock::iterator,
103 : std::function<bool(Instruction &)>>>
104 909727 : BasicBlock::instructionsWithoutDebug() {
105 : std::function<bool(Instruction &)> Fn = [](Instruction &I) {
106 1669518 : return !isa<DbgInfoIntrinsic>(I);
107 : };
108 1819454 : return make_filter_range(*this, Fn);
109 : }
110 :
111 31999 : void BasicBlock::removeFromParent() {
112 31999 : getParent()->getBasicBlockList().remove(getIterator());
113 31999 : }
114 :
115 2823819 : iplist<BasicBlock>::iterator BasicBlock::eraseFromParent() {
116 2823819 : return getParent()->getBasicBlockList().erase(getIterator());
117 : }
118 :
119 : /// Unlink this basic block from its current function and
120 : /// insert it into the function that MovePos lives in, right before MovePos.
121 2946 : void BasicBlock::moveBefore(BasicBlock *MovePos) {
122 5892 : MovePos->getParent()->getBasicBlockList().splice(
123 2946 : MovePos->getIterator(), getParent()->getBasicBlockList(), getIterator());
124 2946 : }
125 :
126 : /// Unlink this basic block from its current function and
127 : /// insert it into the function that MovePos lives in, right after MovePos.
128 6395 : void BasicBlock::moveAfter(BasicBlock *MovePos) {
129 12790 : MovePos->getParent()->getBasicBlockList().splice(
130 6395 : ++MovePos->getIterator(), getParent()->getBasicBlockList(),
131 : getIterator());
132 6395 : }
133 :
134 109468077 : const Module *BasicBlock::getModule() const {
135 109468077 : return getParent()->getParent();
136 : }
137 :
138 239971268 : const Instruction *BasicBlock::getTerminator() const {
139 479180093 : if (InstList.empty() || !InstList.back().isTerminator())
140 1252576 : return nullptr;
141 : return &InstList.back();
142 : }
143 :
144 318140 : const CallInst *BasicBlock::getTerminatingMustTailCall() const {
145 318140 : if (InstList.empty())
146 : return nullptr;
147 : const ReturnInst *RI = dyn_cast<ReturnInst>(&InstList.back());
148 60147 : if (!RI || RI == &InstList.front())
149 : return nullptr;
150 :
151 : const Instruction *Prev = RI->getPrevNode();
152 55046 : if (!Prev)
153 : return nullptr;
154 :
155 : if (Value *RV = RI->getReturnValue()) {
156 26968 : if (RV != Prev)
157 : return nullptr;
158 :
159 : // Look through the optional bitcast.
160 : if (auto *BI = dyn_cast<BitCastInst>(Prev)) {
161 : RV = BI->getOperand(0);
162 : Prev = BI->getPrevNode();
163 2048 : if (!Prev || RV != Prev)
164 : return nullptr;
165 : }
166 : }
167 :
168 : if (auto *CI = dyn_cast<CallInst>(Prev)) {
169 27742 : if (CI->isMustTailCall())
170 69 : return CI;
171 : }
172 : return nullptr;
173 : }
174 :
175 918877 : const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const {
176 918877 : if (InstList.empty())
177 : return nullptr;
178 : auto *RI = dyn_cast<ReturnInst>(&InstList.back());
179 897882 : if (!RI || RI == &InstList.front())
180 : return nullptr;
181 :
182 : if (auto *CI = dyn_cast_or_null<CallInst>(RI->getPrevNode()))
183 : if (Function *F = CI->getCalledFunction())
184 169912 : if (F->getIntrinsicID() == Intrinsic::experimental_deoptimize)
185 17 : return CI;
186 :
187 : return nullptr;
188 : }
189 :
190 19041423 : const Instruction* BasicBlock::getFirstNonPHI() const {
191 20733747 : for (const Instruction &I : *this)
192 20733669 : if (!isa<PHINode>(I))
193 : return &I;
194 : return nullptr;
195 : }
196 :
197 1617662 : const Instruction* BasicBlock::getFirstNonPHIOrDbg() const {
198 2566527 : for (const Instruction &I : *this)
199 2566527 : if (!isa<PHINode>(I) && !isa<DbgInfoIntrinsic>(I))
200 : return &I;
201 : return nullptr;
202 : }
203 :
204 109 : const Instruction* BasicBlock::getFirstNonPHIOrDbgOrLifetime() const {
205 154 : for (const Instruction &I : *this) {
206 154 : if (isa<PHINode>(I) || isa<DbgInfoIntrinsic>(I))
207 : continue;
208 :
209 : if (auto *II = dyn_cast<IntrinsicInst>(&I))
210 1 : if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
211 : II->getIntrinsicID() == Intrinsic::lifetime_end)
212 : continue;
213 :
214 : return &I;
215 : }
216 : return nullptr;
217 : }
218 :
219 299994 : BasicBlock::const_iterator BasicBlock::getFirstInsertionPt() const {
220 299994 : const Instruction *FirstNonPHI = getFirstNonPHI();
221 299994 : if (!FirstNonPHI)
222 : return end();
223 :
224 299925 : const_iterator InsertPt = FirstNonPHI->getIterator();
225 : if (InsertPt->isEHPad()) ++InsertPt;
226 299925 : return InsertPt;
227 : }
228 :
229 7151415 : void BasicBlock::dropAllReferences() {
230 51135680 : for (Instruction &I : *this)
231 43984265 : I.dropAllReferences();
232 7151415 : }
233 :
234 : /// If this basic block has a single predecessor block,
235 : /// return the block, otherwise return a null pointer.
236 12906665 : const BasicBlock *BasicBlock::getSinglePredecessor() const {
237 12906665 : const_pred_iterator PI = pred_begin(this), E = pred_end(this);
238 12906665 : if (PI == E) return nullptr; // No preds.
239 : const BasicBlock *ThePred = *PI;
240 : ++PI;
241 11806158 : return (PI == E) ? ThePred : nullptr /*multiple preds*/;
242 : }
243 :
244 : /// If this basic block has a unique predecessor block,
245 : /// return the block, otherwise return a null pointer.
246 : /// Note that unique predecessor doesn't mean single edge, there can be
247 : /// multiple edges from the unique predecessor to this block (for example
248 : /// a switch statement with multiple cases having the same destination).
249 3190039 : const BasicBlock *BasicBlock::getUniquePredecessor() const {
250 3190039 : const_pred_iterator PI = pred_begin(this), E = pred_end(this);
251 3190039 : if (PI == E) return nullptr; // No preds.
252 : const BasicBlock *PredBB = *PI;
253 : ++PI;
254 2789855 : for (;PI != E; ++PI) {
255 799624 : if (*PI != PredBB)
256 : return nullptr;
257 : // The same predecessor appears multiple times in the predecessor list.
258 : // This is OK.
259 : }
260 : return PredBB;
261 : }
262 :
263 1205269 : const BasicBlock *BasicBlock::getSingleSuccessor() const {
264 1205269 : succ_const_iterator SI = succ_begin(this), E = succ_end(this);
265 1205269 : if (SI == E) return nullptr; // no successors
266 : const BasicBlock *TheSucc = *SI;
267 : ++SI;
268 1100800 : return (SI == E) ? TheSucc : nullptr /* multiple successors */;
269 : }
270 :
271 887236 : const BasicBlock *BasicBlock::getUniqueSuccessor() const {
272 887236 : succ_const_iterator SI = succ_begin(this), E = succ_end(this);
273 887236 : if (SI == E) return nullptr; // No successors
274 : const BasicBlock *SuccBB = *SI;
275 : ++SI;
276 887761 : for (;SI != E; ++SI) {
277 822802 : if (*SI != SuccBB)
278 : return nullptr;
279 : // The same successor appears multiple times in the successor list.
280 : // This is OK.
281 : }
282 : return SuccBB;
283 : }
284 :
285 10584407 : iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
286 10584407 : PHINode *P = empty() ? nullptr : dyn_cast<PHINode>(&*begin());
287 10584407 : return make_range<phi_iterator>(P, nullptr);
288 : }
289 :
290 : /// This method is used to notify a BasicBlock that the
291 : /// specified Predecessor of the block is no longer able to reach it. This is
292 : /// actually not used to update the Predecessor list, but is actually used to
293 : /// update the PHI nodes that reside in the block. Note that this should be
294 : /// called while the predecessor still refers to this block.
295 : ///
296 432767 : void BasicBlock::removePredecessor(BasicBlock *Pred,
297 : bool DontDeleteUselessPHIs) {
298 : assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
299 : find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
300 : "removePredecessor: BB is not a predecessor!");
301 :
302 432767 : if (InstList.empty()) return;
303 : PHINode *APN = dyn_cast<PHINode>(&front());
304 : if (!APN) return; // Quick exit.
305 :
306 : // If there are exactly two predecessors, then we want to nuke the PHI nodes
307 : // altogether. However, we cannot do this, if this in this case:
308 : //
309 : // Loop:
310 : // %x = phi [X, Loop]
311 : // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1
312 : // br Loop ;; %x2 does not dominate all uses
313 : //
314 : // This is because the PHI node input is actually taken from the predecessor
315 : // basic block. The only case this can happen is with a self loop, so we
316 : // check for this case explicitly now.
317 : //
318 : unsigned max_idx = APN->getNumIncomingValues();
319 : assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
320 16049 : if (max_idx == 2) {
321 9851 : BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
322 :
323 : // Disable PHI elimination!
324 9851 : if (this == Other) max_idx = 3;
325 : }
326 :
327 : // <= Two predecessors BEFORE I remove one?
328 16049 : if (max_idx <= 2 && !DontDeleteUselessPHIs) {
329 : // Yup, loop through and nuke the PHI nodes
330 : while (PHINode *PN = dyn_cast<PHINode>(&front())) {
331 : // Remove the predecessor first.
332 9615 : PN->removeIncomingValue(Pred, !DontDeleteUselessPHIs);
333 :
334 : // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
335 9615 : if (max_idx == 2) {
336 9399 : if (PN->getIncomingValue(0) != PN)
337 18792 : PN->replaceAllUsesWith(PN->getIncomingValue(0));
338 : else
339 : // We are left with an infinite loop with no entries: kill the PHI.
340 3 : PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
341 9399 : getInstList().pop_front(); // Remove the PHI node
342 : }
343 :
344 : // If the PHI node already only had one entry, it got deleted by
345 : // removeIncomingValue.
346 : }
347 : } else {
348 : // Okay, now we know that we need to remove predecessor #pred_idx from all
349 : // PHI nodes. Iterate over each PHI node fixing them up
350 : PHINode *PN;
351 : for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
352 : ++II;
353 12098 : PN->removeIncomingValue(Pred, false);
354 : // If all incoming values to the Phi are the same, we can replace the Phi
355 : // with that value.
356 : Value* PNV = nullptr;
357 12098 : if (!DontDeleteUselessPHIs && (PNV = PN->hasConstantValue()))
358 370 : if (PNV != PN) {
359 370 : PN->replaceAllUsesWith(PNV);
360 370 : PN->eraseFromParent();
361 : }
362 : }
363 : }
364 : }
365 :
366 26905 : bool BasicBlock::canSplitPredecessors() const {
367 26905 : const Instruction *FirstNonPHI = getFirstNonPHI();
368 26905 : if (isa<LandingPadInst>(FirstNonPHI))
369 : return true;
370 : // This is perhaps a little conservative because constructs like
371 : // CleanupBlockInst are pretty easy to split. However, SplitBlockPredecessors
372 : // cannot handle such things just yet.
373 : if (FirstNonPHI->isEHPad())
374 8 : return false;
375 : return true;
376 : }
377 :
378 323937 : bool BasicBlock::isLegalToHoistInto() const {
379 323937 : auto *Term = getTerminator();
380 : // No terminator means the block is under construction.
381 323937 : if (!Term)
382 : return true;
383 :
384 : // If the block has no successors, there can be no instructions to hoist.
385 : assert(Term->getNumSuccessors() > 0);
386 :
387 : // Instructions should not be hoisted across exception handling boundaries.
388 323937 : return !Term->isExceptionalTerminator();
389 : }
390 :
391 : /// This splits a basic block into two at the specified
392 : /// instruction. Note that all instructions BEFORE the specified iterator stay
393 : /// as part of the original basic block, an unconditional branch is added to
394 : /// the new BB, and the rest of the instructions in the BB are moved to the new
395 : /// BB, including the old terminator. This invalidates the iterator.
396 : ///
397 : /// Note that this only works on well formed basic blocks (must have a
398 : /// terminator), and 'I' must not be the end of instruction list (which would
399 : /// cause a degenerate basic block to be formed, having a terminator inside of
400 : /// the basic block).
401 : ///
402 522135 : BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
403 : assert(getTerminator() && "Can't use splitBasicBlock on degenerate BB!");
404 : assert(I != InstList.end() &&
405 : "Trying to get me to create degenerate basic block!");
406 :
407 522135 : BasicBlock *New = BasicBlock::Create(getContext(), BBName, getParent(),
408 : this->getNextNode());
409 :
410 : // Save DebugLoc of split point before invalidating iterator.
411 : DebugLoc Loc = I->getDebugLoc();
412 : // Move all of the specified instructions from the original basic block into
413 : // the new basic block.
414 1566405 : New->getInstList().splice(New->end(), this->getInstList(), I, end());
415 :
416 : // Add a branch instruction to the newly formed basic block.
417 : BranchInst *BI = BranchInst::Create(New, this);
418 522135 : BI->setDebugLoc(Loc);
419 :
420 : // Now we must loop through all of the successors of the New block (which
421 : // _were_ the successors of the 'this' block), and update any PHI nodes in
422 : // successors. If there were PHI nodes in the successors, then they need to
423 : // know that incoming branches will be from New, not from Old.
424 : //
425 1078439 : for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) {
426 : // Loop over any phi nodes in the basic block, updating the BB field of
427 : // incoming values...
428 : BasicBlock *Successor = *I;
429 1173563 : for (auto &PN : Successor->phis()) {
430 60955 : int Idx = PN.getBasicBlockIndex(this);
431 119446 : while (Idx != -1) {
432 58491 : PN.setIncomingBlock((unsigned)Idx, New);
433 58491 : Idx = PN.getBasicBlockIndex(this);
434 : }
435 : }
436 : }
437 522135 : return New;
438 : }
439 :
440 1485769 : void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
441 : Instruction *TI = getTerminator();
442 1485769 : if (!TI)
443 : // Cope with being called on a BasicBlock that doesn't have a terminator
444 : // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
445 : return;
446 2163856 : for (BasicBlock *Succ : successors(TI)) {
447 : // N.B. Succ might not be a complete BasicBlock, so don't assume
448 : // that it ends with a non-phi instruction.
449 1137914 : for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) {
450 : PHINode *PN = dyn_cast<PHINode>(II);
451 : if (!PN)
452 : break;
453 : int i;
454 114781 : while ((i = PN->getBasicBlockIndex(this)) >= 0)
455 40952 : PN->setIncomingBlock(i, New);
456 : }
457 : }
458 : }
459 :
460 : /// Return true if this basic block is a landing pad. I.e., it's
461 : /// the destination of the 'unwind' edge of an invoke instruction.
462 367557 : bool BasicBlock::isLandingPad() const {
463 367557 : return isa<LandingPadInst>(getFirstNonPHI());
464 : }
465 :
466 : /// Return the landingpad instruction associated with the landing pad.
467 3189756 : const LandingPadInst *BasicBlock::getLandingPadInst() const {
468 3189756 : return dyn_cast<LandingPadInst>(getFirstNonPHI());
469 : }
470 :
471 3267202 : Optional<uint64_t> BasicBlock::getIrrLoopHeaderWeight() const {
472 3267202 : const Instruction *TI = getTerminator();
473 202867 : if (MDNode *MDIrrLoopHeader =
474 : TI->getMetadata(LLVMContext::MD_irr_loop)) {
475 : MDString *MDName = cast<MDString>(MDIrrLoopHeader->getOperand(0));
476 64 : if (MDName->getString().equals("loop_header_weight")) {
477 : auto *CI = mdconst::extract<ConstantInt>(MDIrrLoopHeader->getOperand(1));
478 : return Optional<uint64_t>(CI->getValue().getZExtValue());
479 : }
480 : }
481 : return Optional<uint64_t>();
482 : }
483 :
484 1 : BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) {
485 2 : while (isa<DbgInfoIntrinsic>(It))
486 : ++It;
487 1 : return It;
488 : }
|
