v8  3.25.30(node0.11.13)
V8 is Google's open source JavaScript engine
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
hydrogen-dce.cc
Go to the documentation of this file.
1 // Copyright 2013 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 #include "hydrogen-dce.h"
29 #include "v8.h"
30 
31 namespace v8 {
32 namespace internal {
33 
34 void HDeadCodeEliminationPhase::MarkLive(
35  HValue* instr, ZoneList<HValue*>* worklist) {
36  if (instr->CheckFlag(HValue::kIsLive)) return; // Already live.
37 
38  if (FLAG_trace_dead_code_elimination) PrintLive(NULL, instr);
39 
40  // Transitively mark all inputs of live instructions live.
41  worklist->Add(instr, zone());
42  while (!worklist->is_empty()) {
43  HValue* instr = worklist->RemoveLast();
44  instr->SetFlag(HValue::kIsLive);
45  for (int i = 0; i < instr->OperandCount(); ++i) {
46  HValue* input = instr->OperandAt(i);
47  if (!input->CheckFlag(HValue::kIsLive)) {
48  input->SetFlag(HValue::kIsLive);
49  worklist->Add(input, zone());
50  if (FLAG_trace_dead_code_elimination) PrintLive(instr, input);
51  }
52  }
53  }
54 }
55 
56 
57 void HDeadCodeEliminationPhase::PrintLive(HValue* ref, HValue* instr) {
58  HeapStringAllocator allocator;
59  StringStream stream(&allocator);
60  if (ref != NULL) {
61  ref->PrintTo(&stream);
62  } else {
63  stream.Add("root ");
64  }
65  stream.Add(" -> ");
66  instr->PrintTo(&stream);
67  PrintF("[MarkLive %s]\n", stream.ToCString().get());
68 }
69 
70 
71 void HDeadCodeEliminationPhase::MarkLiveInstructions() {
72  ZoneList<HValue*> worklist(10, zone());
73 
74  // Transitively mark all live instructions, starting from roots.
75  for (int i = 0; i < graph()->blocks()->length(); ++i) {
76  HBasicBlock* block = graph()->blocks()->at(i);
77  for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
78  HInstruction* instr = it.Current();
79  if (instr->CannotBeEliminated()) MarkLive(instr, &worklist);
80  }
81  for (int j = 0; j < block->phis()->length(); j++) {
82  HPhi* phi = block->phis()->at(j);
83  if (phi->CannotBeEliminated()) MarkLive(phi, &worklist);
84  }
85  }
86 
87  ASSERT(worklist.is_empty()); // Should have processed everything.
88 }
89 
90 
91 void HDeadCodeEliminationPhase::RemoveDeadInstructions() {
92  ZoneList<HPhi*> worklist(graph()->blocks()->length(), zone());
93 
94  // Remove any instruction not marked kIsLive.
95  for (int i = 0; i < graph()->blocks()->length(); ++i) {
96  HBasicBlock* block = graph()->blocks()->at(i);
97  for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
98  HInstruction* instr = it.Current();
99  if (!instr->CheckFlag(HValue::kIsLive)) {
100  // Instruction has not been marked live, so remove it.
101  instr->DeleteAndReplaceWith(NULL);
102  } else {
103  // Clear the liveness flag to leave the graph clean for the next DCE.
104  instr->ClearFlag(HValue::kIsLive);
105  }
106  }
107  // Collect phis that are dead and remove them in the next pass.
108  for (int j = 0; j < block->phis()->length(); j++) {
109  HPhi* phi = block->phis()->at(j);
110  if (!phi->CheckFlag(HValue::kIsLive)) {
111  worklist.Add(phi, zone());
112  } else {
113  phi->ClearFlag(HValue::kIsLive);
114  }
115  }
116  }
117 
118  // Process phis separately to avoid simultaneously mutating the phi list.
119  while (!worklist.is_empty()) {
120  HPhi* phi = worklist.RemoveLast();
121  HBasicBlock* block = phi->block();
122  phi->DeleteAndReplaceWith(NULL);
123  if (phi->HasMergedIndex()) {
124  block->RecordDeletedPhi(phi->merged_index());
125  }
126  }
127 }
128 
129 } } // namespace v8::internal
enable upcoming ES6 features enable harmony block scoping enable harmony enable harmony proxies enable harmony generators enable harmony numeric enable harmony string enable harmony math functions harmony_scoping harmony_symbols harmony_collections harmony_iteration harmony_strings harmony_scoping harmony_maths tracks arrays with only smi values Optimize object Array DOM strings and string pretenure call new trace pretenuring decisions of HAllocate instructions track fields with only smi values track fields with heap values track_fields track_fields Enables optimizations which favor memory size over execution speed use string slices optimization filter maximum number of GVN fix point iterations use function inlining use allocation folding eliminate write barriers targeting allocations in optimized code maximum source size in bytes considered for a single inlining maximum cumulative number of AST nodes considered for inlining crankshaft harvests type feedback from stub cache trace check elimination phase hydrogen tracing filter NULL
Definition: flags.cc:269
void PrintF(const char *format,...)
Definition: v8utils.cc:40
#define ASSERT(condition)
Definition: checks.h:329
HGraph * graph() const
Definition: hydrogen.h:2695