- // Delete the old branch itself...
- BB->getInstList().erase(TI);
- return NB;
-}
-
-
-// doADCE() - Run the Aggressive Dead Code Elimination algorithm, returning
-// true if the function was modified.
-//
-bool ADCE::doADCE() {
- bool MadeChanges = false;
-
- // Iterate over all of the instructions in the function, eliminating trivially
- // dead instructions, and marking instructions live that are known to be
- // needed. Perform the walk in depth first order so that we avoid marking any
- // instructions live in basic blocks that are unreachable. These blocks will
- // be eliminated later, along with the instructions inside.
- //
- for (df_iterator<Function*> BBI = df_begin(Func), BBE = df_end(Func);
- BBI != BBE; ++BBI) {
- BasicBlock *BB = *BBI;
- for (BasicBlock::iterator II = BB->begin(), EI = BB->end(); II != EI; ) {
- if (II->mayWriteToMemory() || isa<ReturnInst>(II) || isa<UnwindInst>(II)){
- markInstructionLive(II);
- ++II; // Increment the inst iterator if the inst wasn't deleted
- } else if (isInstructionTriviallyDead(II)) {
- // Remove the instruction from it's basic block...
- II = BB->getInstList().erase(II);
- ++NumInstRemoved;
- MadeChanges = true;
- } else {
- ++II; // Increment the inst iterator if the inst wasn't deleted
- }
- }
- }
-
- // Check to ensure we have an exit node for this CFG. If we don't, we won't
- // have any post-dominance information, thus we cannot perform our
- // transformations safely.
- //
- PostDominatorTree &DT = getAnalysis<PostDominatorTree>();
- if (DT[&Func->getEntryBlock()] == 0) {
- WorkList.clear();
- return MadeChanges;
- }
-
- DEBUG(std::cerr << "Processing work list\n");
-
- // AliveBlocks - Set of basic blocks that we know have instructions that are
- // alive in them...
- //
- std::set<BasicBlock*> AliveBlocks;
-
- // Process the work list of instructions that just became live... if they
- // became live, then that means that all of their operands are necessary as
- // well... make them live as well.
- //
- while (!WorkList.empty()) {
- Instruction *I = WorkList.back(); // Get an instruction that became live...
- WorkList.pop_back();
-
- BasicBlock *BB = I->getParent();
- if (!AliveBlocks.count(BB)) { // Basic block not alive yet...
- AliveBlocks.insert(BB); // Block is now ALIVE!
- markBlockAlive(BB); // Make it so now!
- }
-
- // PHI nodes are a special case, because the incoming values are actually
- // defined in the predecessor nodes of this block, meaning that the PHI
- // makes the predecessors alive.
- //
- if (PHINode *PN = dyn_cast<PHINode>(I))
- for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
- if (!AliveBlocks.count(*PI)) {
- AliveBlocks.insert(BB); // Block is now ALIVE!
- markBlockAlive(*PI);
- }
-
- // 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<Instruction>(I->getOperand(op)))
- markInstructionLive(Operand);
- }
-
- DEBUG(
- std::cerr << "Current Function: X = Live\n";
- for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I){
- std::cerr << I->getName() << ":\t"
- << (AliveBlocks.count(I) ? "LIVE\n" : "DEAD\n");
- for (BasicBlock::iterator BI = I->begin(), BE = I->end(); BI != BE; ++BI){
- if (LiveSet.count(BI)) std::cerr << "X ";
- std::cerr << *BI;
- }
- });
-
- // Find the first postdominator of the entry node that is alive. Make it the
- // new entry node...
- //
- if (AliveBlocks.size() == Func->size()) { // No dead blocks?
- for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I) {
- // Loop over all of the instructions in the function, telling dead
- // instructions to drop their references. This is so that the next sweep
- // over the program can safely delete dead instructions without other dead
- // instructions still referring to them.
- //
- dropReferencesOfDeadInstructionsInLiveBlock(I);
-
- // Check to make sure the terminator instruction is live. If it isn't,
- // this means that the condition that it branches on (we know it is not an
- // unconditional branch), is not needed to make the decision of where to
- // go to, because all outgoing edges go to the same place. We must remove
- // the use of the condition (because it's probably dead), so we convert
- // the terminator to a conditional branch.
- //
- TerminatorInst *TI = I->getTerminator();
- if (!LiveSet.count(TI))
- convertToUnconditionalBranch(TI);
- }
-
- } else { // If there are some blocks dead...
- // If the entry node is dead, insert a new entry node to eliminate the entry
- // node as a special case.
- //
- if (!AliveBlocks.count(&Func->front())) {
- BasicBlock *NewEntry = new BasicBlock();
- NewEntry->getInstList().push_back(new BranchInst(&Func->front()));
- Func->getBasicBlockList().push_front(NewEntry);
- AliveBlocks.insert(NewEntry); // This block is always alive!
- LiveSet.insert(NewEntry->getTerminator()); // The branch is live