From 1a84bd38efa9d3f638781e2502b2bee150a3471c Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 17 Feb 2005 19:28:49 +0000 Subject: [PATCH] Do not mark obviously unreachable blocks live when processing PHI nodes, and handle incomplete control dependences correctly. This fixes: Regression/Transforms/ADCE/dead-phi-edge.ll -> a missed optimization Regression/Transforms/ADCE/dead-phi-edge.ll -> a compiler crash distilled from QT4 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@20227 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/ADCE.cpp | 101 ++++++++++++++++++++------------- 1 file changed, 61 insertions(+), 40 deletions(-) diff --git a/lib/Transforms/Scalar/ADCE.cpp b/lib/Transforms/Scalar/ADCE.cpp index ca876de681c..cb09a4e6fc6 100644 --- a/lib/Transforms/Scalar/ADCE.cpp +++ b/lib/Transforms/Scalar/ADCE.cpp @@ -253,7 +253,7 @@ bool ADCE::doADCE() { // function which unwinds, exits or has side-effects, we don't want to delete // the infinite loop or those blocks leading up to it. for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) - if (DT[I] == 0) + if (DT[I] == 0 && ReachableBBs.count(I)) for (pred_iterator PI = pred_begin(I), E = pred_end(I); PI != E; ++PI) markInstructionLive((*PI)->getTerminator()); @@ -281,17 +281,28 @@ bool ADCE::doADCE() { // defined in the predecessor nodes of this block, meaning that the PHI // makes the predecessors alive. // - if (PHINode *PN = dyn_cast(I)) - for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) - if (AliveBlocks.insert(PN->getIncomingBlock(i)).second) - markBlockAlive(PN->getIncomingBlock(i)); // Block is newly ALIVE! - - // Loop over all of the operands of the live instruction, making sure that - // they are known to be alive as well. - // - for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) - if (Instruction *Operand = dyn_cast(I->getOperand(op))) - markInstructionLive(Operand); + if (PHINode *PN = dyn_cast(I)) { + for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { + // If the incoming edge is clearly dead, it won't have control + // dependence information. Do not mark it live. + BasicBlock *PredBB = PN->getIncomingBlock(i); + if (ReachableBBs.count(PredBB)) { + // FIXME: This should mark the control dependent edge as live, not + // necessarily the predecessor itself! + if (AliveBlocks.insert(PredBB).second) + markBlockAlive(PN->getIncomingBlock(i)); // Block is newly ALIVE! + if (Instruction *Op = dyn_cast(PN->getIncomingValue(i))) + markInstructionLive(Op); + } + } + } else { + // Loop over all of the operands of the live instruction, making sure that + // they are known to be alive as well. + // + for (unsigned op = 0, End = I->getNumOperands(); op != End; ++op) + if (Instruction *Operand = dyn_cast(I->getOperand(op))) + markInstructionLive(Operand); + } } DEBUG( @@ -359,7 +370,7 @@ bool ADCE::doADCE() { // Loop over all of the successors, looking for ones that are not alive. // We cannot save the number of successors in the terminator instruction - // here because we may remove them if we don't have a postdominator... + // here because we may remove them if we don't have a postdominator. // for (unsigned i = 0; i != TI->getNumSuccessors(); ++i) if (!AliveBlocks.count(TI->getSuccessor(i))) { @@ -368,39 +379,49 @@ bool ADCE::doADCE() { // dead... // PostDominatorTree::Node *LastNode = DT[TI->getSuccessor(i)]; + PostDominatorTree::Node *NextNode = 0; + + if (LastNode) { + NextNode = LastNode->getIDom(); + while (!AliveBlocks.count(NextNode->getBlock())) { + LastNode = NextNode; + NextNode = NextNode->getIDom(); + if (NextNode == 0) { + LastNode = 0; + break; + } + } + } // There is a special case here... if there IS no post-dominator for - // the block we have no owhere to point our branch to. Instead, - // convert it to a return. This can only happen if the code branched - // into an infinite loop. Note that this may not be desirable, - // because we _are_ altering the behavior of the code. This is a well - // known drawback of ADCE, so in the future if we choose to revisit - // the decision, this is where it should be. + // the block we have nowhere to point our branch to. Instead, convert + // it to a return. This can only happen if the code branched into an + // infinite loop. Note that this may not be desirable, because we + // _are_ altering the behavior of the code. This is a well known + // drawback of ADCE, so in the future if we choose to revisit the + // decision, this is where it should be. // if (LastNode == 0) { // No postdominator! - // Call RemoveSuccessor to transmogrify the terminator instruction - // to not contain the outgoing branch, or to create a new terminator - // if the form fundamentally changes (i.e., unconditional branch to - // return). Note that this will change a branch into an infinite - // loop into a return instruction! - // - RemoveSuccessor(TI, i); - - // RemoveSuccessor may replace TI... make sure we have a fresh - // pointer... and e variable. - // - TI = BB->getTerminator(); - - // Rescan this successor... - --i; - } else { - PostDominatorTree::Node *NextNode = LastNode->getIDom(); + if (!isa(TI)) { + // Call RemoveSuccessor to transmogrify the terminator instruction + // to not contain the outgoing branch, or to create a new + // terminator if the form fundamentally changes (i.e., + // unconditional branch to return). Note that this will change a + // branch into an infinite loop into a return instruction! + // + RemoveSuccessor(TI, i); + + // RemoveSuccessor may replace TI... make sure we have a fresh + // pointer. + // + TI = BB->getTerminator(); + + // Rescan this successor... + --i; + } else { - while (!AliveBlocks.count(NextNode->getBlock())) { - LastNode = NextNode; - NextNode = NextNode->getIDom(); } - + } else { // Get the basic blocks that we need... BasicBlock *LastDead = LastNode->getBlock(); BasicBlock *NextAlive = NextNode->getBlock(); -- 2.34.1