Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(10)

Side by Side Diff: src/hydrogen-dce.cc

Issue 18791002: Turn dead code elimination into a proper HPhase. (Closed) Base URL: https://v8.googlecode.com/svn/branches/bleeding_edge
Patch Set: Use local worklists. Created 7 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « src/hydrogen-dce.h ('k') | tools/gyp/v8.gyp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
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 bool HDeadCodeEliminationPhase::MarkLive(HValue* ref, HValue* instr) {
35 if (instr->CheckFlag(HValue::kIsLive)) return false;
36 instr->SetFlag(HValue::kIsLive);
37
38 if (FLAG_trace_dead_code_elimination) {
39 HeapStringAllocator allocator;
40 StringStream stream(&allocator);
41 if (ref != NULL) {
42 ref->PrintTo(&stream);
43 } else {
44 stream.Add("root ");
45 }
46 stream.Add(" -> ");
47 instr->PrintTo(&stream);
48 PrintF("[MarkLive %s]\n", *stream.ToCString());
49 }
50
51 return true;
52 }
53
54
55 void HDeadCodeEliminationPhase::MarkLiveInstructions() {
56 ZoneList<HValue*> worklist(graph()->blocks()->length(), zone());
57
58 // Mark initial root instructions for dead code elimination.
59 for (int i = 0; i < graph()->blocks()->length(); ++i) {
60 HBasicBlock* block = graph()->blocks()->at(i);
61 for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
62 HInstruction* instr = it.Current();
63 if (instr->CannotBeEliminated() && MarkLive(NULL, instr)) {
64 worklist.Add(instr, zone());
65 }
66 }
67 for (int j = 0; j < block->phis()->length(); j++) {
68 HPhi* phi = block->phis()->at(j);
69 if (phi->CannotBeEliminated() && MarkLive(NULL, phi)) {
70 worklist.Add(phi, zone());
71 }
72 }
73 }
74
75 // Transitively mark all inputs of live instructions live.
76 while (!worklist.is_empty()) {
77 HValue* instr = worklist.RemoveLast();
78 for (int i = 0; i < instr->OperandCount(); ++i) {
79 if (MarkLive(instr, instr->OperandAt(i))) {
80 worklist.Add(instr->OperandAt(i), zone());
81 }
82 }
83 }
84 }
85
86
87 void HDeadCodeEliminationPhase::RemoveDeadInstructions() {
88 ZoneList<HPhi*> worklist(graph()->blocks()->length(), zone());
89
90 // Remove any instruction not marked kIsLive.
91 for (int i = 0; i < graph()->blocks()->length(); ++i) {
92 HBasicBlock* block = graph()->blocks()->at(i);
93 for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
94 HInstruction* instr = it.Current();
95 if (!instr->CheckFlag(HValue::kIsLive)) {
96 // Instruction has not been marked live; assume it is dead and remove.
97 // TODO(titzer): we don't remove constants because some special ones
98 // might be used by later phases and are assumed to be in the graph
99 if (!instr->IsConstant()) instr->DeleteAndReplaceWith(NULL);
100 } else {
101 // Clear the liveness flag to leave the graph clean for the next DCE.
102 instr->ClearFlag(HValue::kIsLive);
103 }
104 }
105 // Collect phis that are dead and remove them in the next pass.
106 for (int j = 0; j < block->phis()->length(); j++) {
107 HPhi* phi = block->phis()->at(j);
108 if (!phi->CheckFlag(HValue::kIsLive)) {
109 worklist.Add(phi, zone());
110 } else {
111 phi->ClearFlag(HValue::kIsLive);
112 }
113 }
114 }
115
116 // Process phis separately to avoid simultaneously mutating the phi list.
117 while (!worklist.is_empty()) {
118 HPhi* phi = worklist.RemoveLast();
119 HBasicBlock* block = phi->block();
120 phi->DeleteAndReplaceWith(NULL);
121 block->RecordDeletedPhi(phi->merged_index());
122 }
123 }
124
125 } } // namespace v8::internal
OLDNEW
« no previous file with comments | « src/hydrogen-dce.h ('k') | tools/gyp/v8.gyp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698