1 // Copyright 2013 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "src/hydrogen-dce.h" 6 #include "src/v8.h" 7 8 namespace v8 { 9 namespace internal { 10 MarkLive(HValue * instr,ZoneList<HValue * > * worklist)11 void HDeadCodeEliminationPhase::MarkLive( 12 HValue* instr, ZoneList<HValue*>* worklist) { 13 if (instr->CheckFlag(HValue::kIsLive)) return; // Already live. 14 15 if (FLAG_trace_dead_code_elimination) PrintLive(NULL, instr); 16 17 // Transitively mark all inputs of live instructions live. 18 worklist->Add(instr, zone()); 19 while (!worklist->is_empty()) { 20 HValue* instr = worklist->RemoveLast(); 21 instr->SetFlag(HValue::kIsLive); 22 for (int i = 0; i < instr->OperandCount(); ++i) { 23 HValue* input = instr->OperandAt(i); 24 if (!input->CheckFlag(HValue::kIsLive)) { 25 input->SetFlag(HValue::kIsLive); 26 worklist->Add(input, zone()); 27 if (FLAG_trace_dead_code_elimination) PrintLive(instr, input); 28 } 29 } 30 } 31 } 32 33 PrintLive(HValue * ref,HValue * instr)34 void HDeadCodeEliminationPhase::PrintLive(HValue* ref, HValue* instr) { 35 OFStream os(stdout); 36 os << "[MarkLive "; 37 if (ref != NULL) { 38 os << *ref; 39 } else { 40 os << "root "; 41 } 42 os << " -> " << *instr << "]" << endl; 43 } 44 45 MarkLiveInstructions()46 void HDeadCodeEliminationPhase::MarkLiveInstructions() { 47 ZoneList<HValue*> worklist(10, zone()); 48 49 // Transitively mark all live instructions, starting from roots. 50 for (int i = 0; i < graph()->blocks()->length(); ++i) { 51 HBasicBlock* block = graph()->blocks()->at(i); 52 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 53 HInstruction* instr = it.Current(); 54 if (instr->CannotBeEliminated()) MarkLive(instr, &worklist); 55 } 56 for (int j = 0; j < block->phis()->length(); j++) { 57 HPhi* phi = block->phis()->at(j); 58 if (phi->CannotBeEliminated()) MarkLive(phi, &worklist); 59 } 60 } 61 62 DCHECK(worklist.is_empty()); // Should have processed everything. 63 } 64 65 RemoveDeadInstructions()66 void HDeadCodeEliminationPhase::RemoveDeadInstructions() { 67 ZoneList<HPhi*> worklist(graph()->blocks()->length(), zone()); 68 69 // Remove any instruction not marked kIsLive. 70 for (int i = 0; i < graph()->blocks()->length(); ++i) { 71 HBasicBlock* block = graph()->blocks()->at(i); 72 for (HInstructionIterator it(block); !it.Done(); it.Advance()) { 73 HInstruction* instr = it.Current(); 74 if (!instr->CheckFlag(HValue::kIsLive)) { 75 // Instruction has not been marked live, so remove it. 76 instr->DeleteAndReplaceWith(NULL); 77 } else { 78 // Clear the liveness flag to leave the graph clean for the next DCE. 79 instr->ClearFlag(HValue::kIsLive); 80 } 81 } 82 // Collect phis that are dead and remove them in the next pass. 83 for (int j = 0; j < block->phis()->length(); j++) { 84 HPhi* phi = block->phis()->at(j); 85 if (!phi->CheckFlag(HValue::kIsLive)) { 86 worklist.Add(phi, zone()); 87 } else { 88 phi->ClearFlag(HValue::kIsLive); 89 } 90 } 91 } 92 93 // Process phis separately to avoid simultaneously mutating the phi list. 94 while (!worklist.is_empty()) { 95 HPhi* phi = worklist.RemoveLast(); 96 HBasicBlock* block = phi->block(); 97 phi->DeleteAndReplaceWith(NULL); 98 if (phi->HasMergedIndex()) { 99 block->RecordDeletedPhi(phi->merged_index()); 100 } 101 } 102 } 103 104 } } // namespace v8::internal 105