Line data    Source code

       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       14502 : void HDeadCodeEliminationPhase::MarkLive(
      12             :     HValue* instr, ZoneList<HValue*>* worklist) {
      13       43506 :   if (instr->CheckFlag(HValue::kIsLive)) return;  // Already live.
      14             : 
      15       14481 :   if (FLAG_trace_dead_code_elimination) PrintLive(NULL, instr);
      16             : 
      17             :   // Transitively mark all inputs of live instructions live.
      18       14481 :   worklist->Add(instr, zone());
      19       34126 :   while (!worklist->is_empty()) {
      20       34126 :     HValue* instr = worklist->RemoveLast();
      21             :     instr->SetFlag(HValue::kIsLive);
      22       34880 :     for (int i = 0; i < instr->OperandCount(); ++i) {
      23       15235 :       HValue* input = instr->OperandAt(i);
      24       30470 :       if (!input->CheckFlag(HValue::kIsLive)) {
      25             :         input->SetFlag(HValue::kIsLive);
      26             :         worklist->Add(input, zone());
      27        5164 :         if (FLAG_trace_dead_code_elimination) PrintLive(instr, input);
      28             :       }
      29             :     }
      30             :   }
      31             : }
      32             : 
      33             : 
      34           0 : void HDeadCodeEliminationPhase::PrintLive(HValue* ref, HValue* instr) {
      35             :   AllowHandleDereference allow_deref;
      36           0 :   OFStream os(stdout);
      37           0 :   os << "[MarkLive ";
      38           0 :   if (ref != NULL) {
      39           0 :     os << *ref;
      40             :   } else {
      41           0 :     os << "root";
      42             :   }
      43           0 :   os << " -> " << *instr << "]" << std::endl;
      44           0 : }
      45             : 
      46             : 
      47         358 : void HDeadCodeEliminationPhase::MarkLiveInstructions() {
      48         358 :   ZoneList<HValue*> worklist(10, zone());
      49             : 
      50             :   // Transitively mark all live instructions, starting from roots.
      51        7520 :   for (int i = 0; i < graph()->blocks()->length(); ++i) {
      52        7162 :     HBasicBlock* block = graph()->blocks()->at(i);
      53       23172 :     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
      54             :       HInstruction* instr = it.Current();
      55       19770 :       if (instr->CannotBeEliminated()) MarkLive(instr, &worklist);
      56             :     }
      57        3626 :     for (int j = 0; j < block->phis()->length(); j++) {
      58         224 :       HPhi* phi = block->phis()->at(j);
      59         224 :       if (phi->CannotBeEliminated()) MarkLive(phi, &worklist);
      60             :     }
      61             :   }
      62             : 
      63             :   DCHECK(worklist.is_empty());  // Should have processed everything.
      64         358 : }
      65             : 
      66             : 
      67         358 : void HDeadCodeEliminationPhase::RemoveDeadInstructions() {
      68        4118 :   ZoneList<HPhi*> worklist(graph()->blocks()->length(), zone());
      69             : 
      70             :   // Remove any instruction not marked kIsLive.
      71        7520 :   for (int i = 0; i < graph()->blocks()->length(); ++i) {
      72        3402 :     HBasicBlock* block = graph()->blocks()->at(i);
      73       23172 :     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
      74             :       HInstruction* instr = it.Current();
      75       39540 :       if (!instr->CheckFlag(HValue::kIsLive)) {
      76             :         // Instruction has not been marked live, so remove it.
      77         324 :         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        3626 :     for (int j = 0; j < block->phis()->length(); j++) {
      85         224 :       HPhi* phi = block->phis()->at(j);
      86         448 :       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         383 :   while (!worklist.is_empty()) {
      96          25 :     HPhi* phi = worklist.RemoveLast();
      97          25 :     HBasicBlock* block = phi->block();
      98          25 :     phi->DeleteAndReplaceWith(NULL);
      99          25 :     if (phi->HasMergedIndex()) {
     100             :       block->RecordDeletedPhi(phi->merged_index());
     101             :     }
     102             :   }
     103         358 : }
     104             : 
     105             : }  // namespace internal
     106             : }  // namespace v8