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
|