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