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