Index: include/llvm/IR/BasicBlock.h =================================================================== --- include/llvm/IR/BasicBlock.h +++ include/llvm/IR/BasicBlock.h @@ -152,6 +152,17 @@ return const_cast(this)->getFirstNonPHIOrDbgOrLifetime(); } + /// \brief Returns a pointer to the first instruction in this block that is + /// not + /// a PHINode, a debug intrinsic, a lifetime intrinsic, or a bitcast + /// instruction + /// coupled with the following lifetime intrinsic. + Instruction *getFirstNonPHIOrDbgOrLifetimeOrBitCast(); + const Instruction *getFirstNonPHIOrDbgOrLifetimeOrBitCast() const { + return const_cast(this) + ->getFirstNonPHIOrDbgOrLifetimeOrBitCast(); + } + /// \brief Returns an iterator to the first instruction in this block that is /// suitable for inserting a non-PHI instruction. /// Index: lib/IR/BasicBlock.cpp =================================================================== --- lib/IR/BasicBlock.cpp +++ lib/IR/BasicBlock.cpp @@ -206,6 +206,27 @@ return nullptr; } +Instruction *BasicBlock::getFirstNonPHIOrDbgOrLifetimeOrBitCast() { + for (Instruction &I : *this) { + BasicBlock::iterator TI = I.getIterator(); + if (isa(I) || isa(I)) + continue; + + if (auto *II = dyn_cast(&I)) + if (II->getIntrinsicID() == Intrinsic::lifetime_end) + continue; + + if (auto *II = dyn_cast(&I)) + if (auto *TII = dyn_cast(++TI)) + if (TII->getIntrinsicID() == Intrinsic::lifetime_end) + if (TII->getOperand(1) == II) + continue; + + return &I; + } + return nullptr; +} + BasicBlock::iterator BasicBlock::getFirstInsertionPt() { Instruction *FirstNonPHI = getFirstNonPHI(); if (!FirstNonPHI) Index: lib/Transforms/Utils/Local.cpp =================================================================== --- lib/Transforms/Utils/Local.cpp +++ lib/Transforms/Utils/Local.cpp @@ -796,6 +796,93 @@ replaceUndefValuesInPhi(PN, IncomingValues); } +/// hasLifetimeEnd - Return true if BB has lifetime.end intrinsic. +/// +static bool hasLifetimeEnd(BasicBlock *BB) { + BasicBlock::iterator I = BB->begin(); + while (!I->isTerminator()) { + if (const IntrinsicInst *II = dyn_cast(I)) + if (II->getIntrinsicID() == Intrinsic::lifetime_end) + return true; + ++I; + } + return false; +} + +/// hasPHI - Return true if BB has phi. +/// +static bool hasPHI(BasicBlock *BB) { + BasicBlock::iterator I = BB->begin(); + return isa(I) ? true : false; +} + +/// hoistLifetimeFromEmptyBlockToPred - Hoist lifetime.end intrinsics and +/// related +/// bitcast instructions from BB to predecessors of BB. +/// +static bool hoistLifetimeFromEmptyBlockToPred(BasicBlock *BB) { + BasicBlock::iterator I = BB->begin(); + BasicBlock::iterator NI = BB->begin(); + + // Check to see if all Pred's terminators are unconditional branches and if + // not, + // we cannot hoist lifetime.end intrinsics because it would change semantics. + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + BasicBlock *Pred = *PI; + Instruction *PTI = Pred->getTerminator(); + if (auto *BI = dyn_cast(PTI)) { + if (BI->isUnconditional()) + continue; + else + return false; + } else + return false; + } + + // Hoist all lifetime.end intrinsics and related bitcast instrunctions in BB + // to Preds. + while (!I->isTerminator()) { + if (isa(I)) { + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) { + BasicBlock *Pred = *PI; + pred_iterator NPI = PI; + if (++NPI == E) { + Pred->getInstList().splice(Pred->getTerminator()->getIterator(), + BB->getInstList(), I); + } else + I->clone()->insertBefore(Pred->getTerminator()); + } + I = BB->begin(); + NI = BB->begin(); + } else if (auto *II = dyn_cast(I)) { + if (II->getIntrinsicID() == Intrinsic::lifetime_end) { + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; + ++PI) { + BasicBlock *Pred = *PI; + pred_iterator NPI = PI; + if (++NPI == E) { + Pred->getInstList().splice(Pred->getTerminator()->getIterator(), + BB->getInstList(), I); + } else { + I->clone()->insertBefore(Pred->getTerminator()); + BasicBlock::iterator PEI = Pred->end(); + --PEI; + --PEI; + BasicBlock::iterator NPEI = PEI; + if ((PEI != Pred->begin()) && isa(--PEI)) + NPEI->setOperand(1, &*(PEI)); + } + } + I = BB->begin(); + NI = BB->begin(); + } else + return false; + } else + return false; + } + return true; +} + /// TryToSimplifyUncondBranchFromEmptyBlock - BB is known to contain an /// unconditional branch, and contains no instructions other than PHI nodes, /// potential side-effect free intrinsics and the branch. If possible, @@ -809,74 +896,121 @@ BasicBlock *Succ = cast(BB->getTerminator())->getSuccessor(0); if (BB == Succ) return false; - // Check to see if merging these blocks would cause conflicts for any of the - // phi nodes in BB or Succ. If not, we can safely merge. - if (!CanPropagatePredecessorsForPHIs(BB, Succ)) return false; - - // Check for cases where Succ has multiple predecessors and a PHI node in BB - // has uses which will not disappear when the PHI nodes are merged. It is - // possible to handle such cases, but difficult: it requires checking whether - // BB dominates Succ, which is non-trivial to calculate in the case where - // Succ has multiple predecessors. Also, it requires checking whether - // constructing the necessary self-referential PHI node doesn't introduce any - // conflicts; this isn't too difficult, but the previous code for doing this - // was incorrect. - // - // Note that if this check finds a live use, BB dominates Succ, so BB is - // something like a loop pre-header (or rarely, a part of an irreducible CFG); - // folding the branch isn't profitable in that case anyway. - if (!Succ->getSinglePredecessor()) { - BasicBlock::iterator BBI = BB->begin(); - while (isa(*BBI)) { - for (Use &U : BBI->uses()) { - if (PHINode* PN = dyn_cast(U.getUser())) { - if (PN->getIncomingBlock(U) != BB) + // If BB has lifetime.end intrinsics, simplify BB under more constraints. + if (hasLifetimeEnd(BB)) { + // Check to see if BB and its predecessors and successors have PHI. + if (hasPHI(BB)) + return false; + + for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) + if (hasPHI(*PI)) + return false; + + for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI) + if (hasPHI(*SI)) + return false; + + if (Succ->getSinglePredecessor()) { + // BB is the only predecessor of Succ, so Succ will end up with exactly + // the same predecessors BB had. + + // Copy over any phi, debug or lifetime instruction. + BB->getTerminator()->eraseFromParent(); + Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(), + BB->getInstList()); + + } else { + // Unless BB is the only predecessor of Succ, hoist lifetime intrinsics to + // predecessors of BB and simplify BB. + if (!hoistLifetimeFromEmptyBlockToPred(BB)) { + return false; + } + } + + DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); + + // Everything that jumped to BB now goes to Succ. + BB->replaceAllUsesWith(Succ); + if (!Succ->hasName()) + Succ->takeName(BB); + BB->eraseFromParent(); // Delete the old basic block. + return true; + + } else { + // Check to see if merging these blocks would cause conflicts for any of the + // phi nodes in BB or Succ. If not, we can safely merge. + if (!CanPropagatePredecessorsForPHIs(BB, Succ)) + return false; + + // Check for cases where Succ has multiple predecessors and a PHI node in BB + // has uses which will not disappear when the PHI nodes are merged. It is + // possible to handle such cases, but difficult: it requires checking + // whether + // BB dominates Succ, which is non-trivial to calculate in the case where + // Succ has multiple predecessors. Also, it requires checking whether + // constructing the necessary self-referential PHI node doesn't introduce + // any + // conflicts; this isn't too difficult, but the previous code for doing this + // was incorrect. + // + // Note that if this check finds a live use, BB dominates Succ, so BB is + // something like a loop pre-header (or rarely, a part of an irreducible + // CFG); + // folding the branch isn't profitable in that case anyway. + if (!Succ->getSinglePredecessor()) { + BasicBlock::iterator BBI = BB->begin(); + while (isa(*BBI)) { + for (Use &U : BBI->uses()) { + if (PHINode *PN = dyn_cast(U.getUser())) { + if (PN->getIncomingBlock(U) != BB) + return false; + } else { return false; - } else { - return false; + } } + ++BBI; } - ++BBI; } - } - DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); + DEBUG(dbgs() << "Killing Trivial BB: \n" << *BB); - if (isa(Succ->begin())) { - // If there is more than one pred of succ, and there are PHI nodes in - // the successor, then we need to add incoming edges for the PHI nodes - // - const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB)); + if (isa(Succ->begin())) { + // If there is more than one pred of succ, and there are PHI nodes in + // the successor, then we need to add incoming edges for the PHI nodes + // + const PredBlockVector BBPreds(pred_begin(BB), pred_end(BB)); - // Loop over all of the PHI nodes in the successor of BB. - for (BasicBlock::iterator I = Succ->begin(); isa(I); ++I) { - PHINode *PN = cast(I); + // Loop over all of the PHI nodes in the successor of BB. + for (BasicBlock::iterator I = Succ->begin(); isa(I); ++I) { + PHINode *PN = cast(I); - redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN); + redirectValuesFromPredecessorsToPhi(BB, BBPreds, PN); + } } - } - if (Succ->getSinglePredecessor()) { - // BB is the only predecessor of Succ, so Succ will end up with exactly - // the same predecessors BB had. + if (Succ->getSinglePredecessor()) { + // BB is the only predecessor of Succ, so Succ will end up with exactly + // the same predecessors BB had. - // Copy over any phi, debug or lifetime instruction. - BB->getTerminator()->eraseFromParent(); - Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(), - BB->getInstList()); - } else { - while (PHINode *PN = dyn_cast(&BB->front())) { - // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. - assert(PN->use_empty() && "There shouldn't be any uses here!"); - PN->eraseFromParent(); + // Copy over any phi, debug or lifetime instruction. + BB->getTerminator()->eraseFromParent(); + Succ->getInstList().splice(Succ->getFirstNonPHI()->getIterator(), + BB->getInstList()); + } else { + while (PHINode *PN = dyn_cast(&BB->front())) { + // We explicitly check for such uses in CanPropagatePredecessorsForPHIs. + assert(PN->use_empty() && "There shouldn't be any uses here!"); + PN->eraseFromParent(); + } } - } - // Everything that jumped to BB now goes to Succ. - BB->replaceAllUsesWith(Succ); - if (!Succ->hasName()) Succ->takeName(BB); - BB->eraseFromParent(); // Delete the old basic block. - return true; + // Everything that jumped to BB now goes to Succ. + BB->replaceAllUsesWith(Succ); + if (!Succ->hasName()) + Succ->takeName(BB); + BB->eraseFromParent(); // Delete the old basic block. + return true; + } } /// EliminateDuplicatePHINodes - Check for and eliminate duplicate PHI Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -5068,13 +5068,15 @@ if (SinkCommon && SinkThenElseCodeToEnd(BI)) return true; - // If the Terminator is the only non-phi instruction, simplify the block. - // if LoopHeader is provided, check if the block is a loop header + // If the Terminator is the only non-phi instruction except for bitcast + // instruction coupled with the following lifetime intrinsic, simplify the + // block. If LoopHeader is provided, check if the block is a loop header // (This is for early invocations before loop simplify and vectorization // to keep canonical loop forms for nested loops. // These blocks can be eliminated when the pass is invoked later // in the back-end.) - BasicBlock::iterator I = BB->getFirstNonPHIOrDbg()->getIterator(); + BasicBlock::iterator I = + BB->getFirstNonPHIOrDbgOrLifetimeOrBitCast()->getIterator(); if (I->isTerminator() && BB != &BB->getParent()->getEntryBlock() && (!LoopHeaders || !LoopHeaders->count(BB)) && TryToSimplifyUncondBranchFromEmptyBlock(BB))