Home | History | Annotate | Download | only in src 
      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 
     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 
     34 void HDeadCodeEliminationPhase::PrintLive(HValue* ref, HValue* instr) {
     35   HeapStringAllocator allocator;
     36   StringStream stream(&allocator);
     37   if (ref != NULL) {
     38     ref->PrintTo(&stream);
     39   } else {
     40     stream.Add("root ");
     41   }
     42   stream.Add(" -> ");
     43   instr->PrintTo(&stream);
     44   PrintF("[MarkLive %s]\n", stream.ToCString().get());
     45 }
     46 
     47 
     48 void HDeadCodeEliminationPhase::MarkLiveInstructions() {
     49   ZoneList<HValue*> worklist(10, zone());
     50 
     51   // Transitively mark all live instructions, starting from roots.
     52   for (int i = 0; i < graph()->blocks()->length(); ++i) {
     53     HBasicBlock* block = graph()->blocks()->at(i);
     54     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
     55       HInstruction* instr = it.Current();
     56       if (instr->CannotBeEliminated()) MarkLive(instr, &worklist);
     57     }
     58     for (int j = 0; j < block->phis()->length(); j++) {
     59       HPhi* phi = block->phis()->at(j);
     60       if (phi->CannotBeEliminated()) MarkLive(phi, &worklist);
     61     }
     62   }
     63 
     64   ASSERT(worklist.is_empty());  // Should have processed everything.
     65 }
     66 
     67 
     68 void HDeadCodeEliminationPhase::RemoveDeadInstructions() {
     69   ZoneList<HPhi*> worklist(graph()->blocks()->length(), zone());
     70 
     71   // Remove any instruction not marked kIsLive.
     72   for (int i = 0; i < graph()->blocks()->length(); ++i) {
     73     HBasicBlock* block = graph()->blocks()->at(i);
     74     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
     75       HInstruction* instr = it.Current();
     76       if (!instr->CheckFlag(HValue::kIsLive)) {
     77         // Instruction has not been marked live, so remove it.
     78         instr->DeleteAndReplaceWith(NULL);
     79       } else {
     80         // Clear the liveness flag to leave the graph clean for the next DCE.
     81         instr->ClearFlag(HValue::kIsLive);
     82       }
     83     }
     84     // Collect phis that are dead and remove them in the next pass.
     85     for (int j = 0; j < block->phis()->length(); j++) {
     86       HPhi* phi = block->phis()->at(j);
     87       if (!phi->CheckFlag(HValue::kIsLive)) {
     88         worklist.Add(phi, zone());
     89       } else {
     90         phi->ClearFlag(HValue::kIsLive);
     91       }
     92     }
     93   }
     94 
     95   // Process phis separately to avoid simultaneously mutating the phi list.
     96   while (!worklist.is_empty()) {
     97     HPhi* phi = worklist.RemoveLast();
     98     HBasicBlock* block = phi->block();
     99     phi->DeleteAndReplaceWith(NULL);
    100     if (phi->HasMergedIndex()) {
    101       block->RecordDeletedPhi(phi->merged_index());
    102     }
    103   }
    104 }
    105 
    106 } }  // namespace v8::internal
    107