From cfca06d7963fa0909f90483b42a6d7d194d01e08 Mon Sep 17 00:00:00 2001 From: Dimitry Andric Date: Sun, 26 Jul 2020 19:36:28 +0000 Subject: Vendor import of llvm-project master 2e10b7a39b9, the last commit before the llvmorg-12-init tag, from which release/11.x was branched. --- llvm/lib/IR/BasicBlock.cpp | 136 +++++++++++++++++++++++---------------------- 1 file changed, 70 insertions(+), 66 deletions(-) (limited to 'llvm/lib/IR/BasicBlock.cpp') diff --git a/llvm/lib/IR/BasicBlock.cpp b/llvm/lib/IR/BasicBlock.cpp index bdee6990f932..64f1d3f3100c 100644 --- a/llvm/lib/IR/BasicBlock.cpp +++ b/llvm/lib/IR/BasicBlock.cpp @@ -33,6 +33,10 @@ LLVMContext &BasicBlock::getContext() const { return getType()->getContext(); } +template <> void llvm::invalidateParentIListOrdering(BasicBlock *BB) { + BB->invalidateOrders(); +} + // Explicit instantiation of SymbolTableListTraits since some of the methods // are not in the public header file... template class llvm::SymbolTableListTraits; @@ -61,6 +65,8 @@ void BasicBlock::insertInto(Function *NewParent, BasicBlock *InsertBefore) { } BasicBlock::~BasicBlock() { + validateInstrOrdering(); + // If the address of the block is taken and it is being deleted (e.g. because // it is dead), this means that there is either a dangling constant expr // hanging off the block, or an undefined use of the block (source code @@ -193,6 +199,18 @@ const CallInst *BasicBlock::getTerminatingDeoptimizeCall() const { return nullptr; } +const CallInst *BasicBlock::getPostdominatingDeoptimizeCall() const { + const BasicBlock* BB = this; + SmallPtrSet Visited; + Visited.insert(BB); + while (auto *Succ = BB->getUniqueSuccessor()) { + if (!Visited.insert(Succ).second) + return nullptr; + BB = Succ; + } + return BB->getTerminatingDeoptimizeCall(); +} + const Instruction* BasicBlock::getFirstNonPHI() const { for (const Instruction &I : *this) if (!isa(I)) @@ -273,7 +291,7 @@ bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const { } const BasicBlock *BasicBlock::getSingleSuccessor() const { - succ_const_iterator SI = succ_begin(this), E = succ_end(this); + const_succ_iterator SI = succ_begin(this), E = succ_end(this); if (SI == E) return nullptr; // no successors const BasicBlock *TheSucc = *SI; ++SI; @@ -281,7 +299,7 @@ const BasicBlock *BasicBlock::getSingleSuccessor() const { } const BasicBlock *BasicBlock::getUniqueSuccessor() const { - succ_const_iterator SI = succ_begin(this), E = succ_end(this); + const_succ_iterator SI = succ_begin(this), E = succ_end(this); if (SI == E) return nullptr; // No successors const BasicBlock *SuccBB = *SI; ++SI; @@ -299,78 +317,38 @@ iterator_range BasicBlock::phis() { return make_range(P, nullptr); } -/// This method is used to notify a BasicBlock that the -/// specified Predecessor of the block is no longer able to reach it. This is -/// actually not used to update the Predecessor list, but is actually used to -/// update the PHI nodes that reside in the block. Note that this should be -/// called while the predecessor still refers to this block. +/// Update PHI nodes in this BasicBlock before removal of predecessor \p Pred. +/// Note that this function does not actually remove the predecessor. /// +/// If \p KeepOneInputPHIs is true then don't remove PHIs that are left with +/// zero or one incoming values, and don't simplify PHIs with all incoming +/// values the same. void BasicBlock::removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs) { - assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs. + // Use hasNUsesOrMore to bound the cost of this assertion for complex CFGs. + assert((hasNUsesOrMore(16) || find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) && - "removePredecessor: BB is not a predecessor!"); - - if (InstList.empty()) return; - PHINode *APN = dyn_cast(&front()); - if (!APN) return; // Quick exit. - - // If there are exactly two predecessors, then we want to nuke the PHI nodes - // altogether. However, we cannot do this, if this in this case: - // - // Loop: - // %x = phi [X, Loop] - // %x2 = add %x, 1 ;; This would become %x2 = add %x2, 1 - // br Loop ;; %x2 does not dominate all uses - // - // This is because the PHI node input is actually taken from the predecessor - // basic block. The only case this can happen is with a self loop, so we - // check for this case explicitly now. - // - unsigned max_idx = APN->getNumIncomingValues(); - assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!"); - if (max_idx == 2) { - BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred); - - // Disable PHI elimination! - if (this == Other) max_idx = 3; - } + "Pred is not a predecessor!"); - // <= Two predecessors BEFORE I remove one? - if (max_idx <= 2 && !KeepOneInputPHIs) { - // Yup, loop through and nuke the PHI nodes - while (PHINode *PN = dyn_cast(&front())) { - // Remove the predecessor first. - PN->removeIncomingValue(Pred, !KeepOneInputPHIs); - - // If the PHI _HAD_ two uses, replace PHI node with its now *single* value - if (max_idx == 2) { - if (PN->getIncomingValue(0) != PN) - PN->replaceAllUsesWith(PN->getIncomingValue(0)); - else - // We are left with an infinite loop with no entries: kill the PHI. - PN->replaceAllUsesWith(UndefValue::get(PN->getType())); - getInstList().pop_front(); // Remove the PHI node - } - - // If the PHI node already only had one entry, it got deleted by - // removeIncomingValue. - } - } else { - // Okay, now we know that we need to remove predecessor #pred_idx from all - // PHI nodes. Iterate over each PHI node fixing them up - PHINode *PN; - for (iterator II = begin(); (PN = dyn_cast(II)); ) { - ++II; - PN->removeIncomingValue(Pred, false); - // If all incoming values to the Phi are the same, we can replace the Phi - // with that value. - Value* PNV = nullptr; - if (!KeepOneInputPHIs && (PNV = PN->hasConstantValue())) - if (PNV != PN) { + // Return early if there are no PHI nodes to update. + if (!isa(begin())) + return; + unsigned NumPreds = cast(front()).getNumIncomingValues(); + + // Update all PHI nodes. + for (iterator II = begin(); isa(II);) { + PHINode *PN = cast(II++); + PN->removeIncomingValue(Pred, !KeepOneInputPHIs); + if (!KeepOneInputPHIs) { + // If we have a single predecessor, removeIncomingValue erased the PHI + // node itself. + if (NumPreds > 1) { + if (Value *PNV = PN->hasConstantValue()) { + // Replace the PHI node with its constant value. PN->replaceAllUsesWith(PNV); PN->eraseFromParent(); } + } } } } @@ -494,3 +472,29 @@ BasicBlock::iterator llvm::skipDebugIntrinsics(BasicBlock::iterator It) { ++It; return It; } + +void BasicBlock::renumberInstructions() { + unsigned Order = 0; + for (Instruction &I : *this) + I.Order = Order++; + + // Set the bit to indicate that the instruction order valid and cached. + BasicBlockBits Bits = getBasicBlockBits(); + Bits.InstrOrderValid = true; + setBasicBlockBits(Bits); +} + +#ifndef NDEBUG +/// In asserts builds, this checks the numbering. In non-asserts builds, it +/// is defined as a no-op inline function in BasicBlock.h. +void BasicBlock::validateInstrOrdering() const { + if (!isInstrOrderValid()) + return; + const Instruction *Prev = nullptr; + for (const Instruction &I : *this) { + assert((!Prev || Prev->comesBefore(&I)) && + "cached instruction ordering is incorrect"); + Prev = &I; + } +} +#endif -- cgit v1.2.3