-void ADCE::doADCE(DominanceFrontier &CDG) {
- DEBUG(cerr << "Function: " << Func);
-
- // 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; ) {
- Instruction *I = *II;
-
- if (I->hasSideEffects() || I->getOpcode() == Instruction::Ret) {
- markInstructionLive(I);
- ++II; // Increment the inst iterator if the inst wasn't deleted
- } else if (isInstructionTriviallyDead(I)) {
- // Remove the instruction from it's basic block...
- delete BB->getInstList().remove(II);
- MadeChanges = true;
- } else {
- ++II; // Increment the inst iterator if the inst wasn't deleted
- }
- }
- }
-
- DEBUG(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 neccesary 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) == 0) { // Basic block not alive yet...
- // Mark the basic block as being newly ALIVE... and mark all branches that
- // this block is control dependant on as being alive also...
- //
- AliveBlocks.insert(BB); // Block is now ALIVE!
- DominanceFrontier::const_iterator It = CDG.find(BB);
- if (It != CDG.end()) {
- // Get the blocks that this node is control dependant on...
- const DominanceFrontier::DomSetType &CDB = It->second;
- for_each(CDB.begin(), CDB.end(), // Mark all their terminators as live
- bind_obj(this, &ADCE::markTerminatorLive));
- }
-
- // If this basic block is live, then the terminator must be as well!
- markTerminatorLive(BB);
- }
-
- // 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);
- }
-
- if (DebugFlag) {
- cerr << "Current Function: X = Live\n";
- for (Function::iterator I = Func->begin(), E = Func->end(); I != E; ++I)
- for (BasicBlock::iterator BI = (*I)->begin(), BE = (*I)->end();
- BI != BE; ++BI) {
- if (LiveSet.count(*BI)) cerr << "X ";
- cerr << *BI;
- }
- }
-
- // After the worklist is processed, recursively walk the CFG in depth first
- // order, patching up references to dead blocks...
- //
- std::set<BasicBlock*> VisitedBlocks;
- BasicBlock *EntryBlock = fixupCFG(Func->front(), VisitedBlocks, AliveBlocks);