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 :
6 : #include "src/crankshaft/hydrogen-environment-liveness.h"
7 : #include "src/objects-inl.h"
8 :
9 : namespace v8 {
10 : namespace internal {
11 :
12 :
13 280033 : HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase(
14 280033 : HGraph* graph)
15 : : HPhase("H_Environment liveness analysis", graph),
16 280033 : block_count_(graph->blocks()->length()),
17 : maximum_environment_size_(graph->maximum_environment_size()),
18 : live_at_block_start_(block_count_, zone()),
19 : first_simulate_(block_count_, zone()),
20 : first_simulate_invalid_for_index_(block_count_, zone()),
21 : markers_(maximum_environment_size_, zone()),
22 : collect_markers_(true),
23 : last_simulate_(NULL),
24 560066 : went_live_since_last_simulate_(maximum_environment_size_, zone()) {
25 : DCHECK(maximum_environment_size_ > 0);
26 4599894 : for (int i = 0; i < block_count_; ++i) {
27 : live_at_block_start_.Add(
28 4319851 : new(zone()) BitVector(maximum_environment_size_, zone()), zone());
29 : first_simulate_.Add(NULL, zone());
30 : first_simulate_invalid_for_index_.Add(
31 4319856 : new(zone()) BitVector(maximum_environment_size_, zone()), zone());
32 : }
33 280036 : }
34 :
35 :
36 486222 : void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot(
37 : int index, HSimulate* simulate) {
38 : int operand_index = simulate->ToOperandIndex(index);
39 486222 : if (operand_index == -1) {
40 486222 : simulate->AddAssignedValue(index, graph()->GetConstantOptimizedOut());
41 : } else {
42 120975 : simulate->SetOperandAt(operand_index, graph()->GetConstantOptimizedOut());
43 : }
44 486222 : }
45 :
46 :
47 4319848 : void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors(
48 8991822 : HBasicBlock* block, BitVector* live) {
49 : // When a value is live in successor A but dead in B, we must
50 : // explicitly zap it in B.
51 9193481 : for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
52 4873636 : HBasicBlock* successor = it.Current();
53 : int successor_id = successor->block_id();
54 10344734 : BitVector* live_in_successor = live_at_block_start_[successor_id];
55 4873636 : if (live_in_successor->Equals(*live)) continue;
56 4671974 : for (int i = 0; i < live->length(); ++i) {
57 2211736 : if (!live->Contains(i)) continue;
58 597462 : if (live_in_successor->Contains(i)) continue;
59 589670 : if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) {
60 : continue;
61 : }
62 294764 : HSimulate* simulate = first_simulate_.at(successor_id);
63 294764 : if (simulate == NULL) continue;
64 : DCHECK(VerifyClosures(simulate->closure(),
65 : block->last_environment()->closure()));
66 274495 : ZapEnvironmentSlot(i, simulate);
67 : }
68 : }
69 4319851 : }
70 :
71 :
72 1275638 : void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction(
73 623167 : HEnvironmentMarker* marker) {
74 3826914 : if (!marker->CheckFlag(HValue::kEndsLiveRange)) return;
75 : HSimulate* simulate = marker->next_simulate();
76 411440 : if (simulate != NULL) {
77 : DCHECK(VerifyClosures(simulate->closure(), marker->closure()));
78 211727 : ZapEnvironmentSlot(marker->index(), simulate);
79 : }
80 : }
81 :
82 :
83 8902815 : void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd(
84 8902815 : HBasicBlock* block,
85 18971552 : BitVector* live) {
86 : // Liveness at the end of each block: union of liveness in successors.
87 : live->Clear();
88 18971530 : for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
89 20137474 : live->Union(*live_at_block_start_[it.Current()->block_id()]);
90 : }
91 8902788 : }
92 :
93 :
94 30685792 : void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction(
95 : HInstruction* instr,
96 3766691 : BitVector* live) {
97 30685792 : switch (instr->opcode()) {
98 : case HValue::kEnvironmentMarker: {
99 : HEnvironmentMarker* marker = HEnvironmentMarker::cast(instr);
100 3136804 : int index = marker->index();
101 1568402 : if (!live->Contains(index)) {
102 : marker->SetFlag(HValue::kEndsLiveRange);
103 : } else {
104 : marker->ClearFlag(HValue::kEndsLiveRange);
105 : }
106 8839439 : if (!went_live_since_last_simulate_.Contains(index)) {
107 1493781 : marker->set_next_simulate(last_simulate_);
108 : }
109 1568402 : if (marker->kind() == HEnvironmentMarker::LOOKUP) {
110 : live->Add(index);
111 : } else {
112 : DCHECK(marker->kind() == HEnvironmentMarker::BIND);
113 : live->Remove(index);
114 : went_live_since_last_simulate_.Add(index);
115 : }
116 1568402 : if (collect_markers_) {
117 : // Populate |markers_| list during the first pass.
118 1275636 : markers_.Add(marker, zone());
119 : }
120 : break;
121 : }
122 : case HValue::kLeaveInlined:
123 : // No environment values are live at the end of an inlined section.
124 : live->Clear();
125 524031 : last_simulate_ = NULL;
126 :
127 : // The following DCHECKs guard the assumption used in case
128 : // kEnterInlined below:
129 : DCHECK(instr->next()->IsSimulate());
130 : DCHECK(instr->next()->next()->IsGoto());
131 :
132 524031 : break;
133 : case HValue::kEnterInlined: {
134 : // Those environment values are live that are live at any return
135 : // target block. Here we make use of the fact that the end of an
136 : // inline sequence always looks like this: HLeaveInlined, HSimulate,
137 : // HGoto (to return_target block), with no environment lookups in
138 : // between (see DCHECKs above).
139 : HEnterInlined* enter = HEnterInlined::cast(instr);
140 : live->Clear();
141 125447 : for (int i = 0; i < enter->return_targets()->length(); ++i) {
142 125447 : int return_id = enter->return_targets()->at(i)->block_id();
143 250894 : live->Union(*live_at_block_start_[return_id]);
144 : }
145 105856 : last_simulate_ = NULL;
146 105856 : break;
147 : }
148 : case HValue::kSimulate:
149 5104352 : last_simulate_ = HSimulate::cast(instr);
150 : went_live_since_last_simulate_.Clear();
151 : break;
152 : default:
153 : break;
154 : }
155 30685760 : }
156 :
157 :
158 280036 : void HEnvironmentLivenessAnalysisPhase::Run() {
159 : DCHECK(maximum_environment_size_ > 0);
160 :
161 : // Main iteration. Compute liveness of environment slots, and store it
162 : // for each block until it doesn't change any more. For efficiency, visit
163 : // blocks in reverse order and walk backwards through each block. We
164 : // need several iterations to propagate liveness through nested loops.
165 280036 : BitVector live(maximum_environment_size_, zone());
166 280036 : BitVector worklist(block_count_, zone());
167 4599900 : for (int i = 0; i < block_count_; ++i) {
168 4319864 : worklist.Add(i);
169 : }
170 1164534 : while (!worklist.IsEmpty()) {
171 7392608 : for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
172 14180754 : if (!worklist.Contains(block_id)) {
173 : continue;
174 : }
175 : worklist.Remove(block_id);
176 4583012 : last_simulate_ = NULL;
177 :
178 18093777 : HBasicBlock* block = graph()->blocks()->at(block_id);
179 4583012 : UpdateLivenessAtBlockEnd(block, &live);
180 :
181 35268807 : for (HInstruction* instr = block->end(); instr != NULL;
182 : instr = instr->previous()) {
183 30685795 : UpdateLivenessAtInstruction(instr, &live);
184 : }
185 :
186 : // Reached the start of the block, do necessary bookkeeping:
187 : // store computed information for this block and add predecessors
188 : // to the work list as necessary.
189 4583012 : first_simulate_.Set(block_id, last_simulate_);
190 4583012 : first_simulate_invalid_for_index_[block_id]->CopyFrom(
191 4583012 : went_live_since_last_simulate_);
192 13749036 : if (live_at_block_start_[block_id]->UnionIsChanged(live)) {
193 1371136 : for (int i = 0; i < block->predecessors()->length(); ++i) {
194 1371136 : worklist.Add(block->predecessors()->at(i)->block_id());
195 : }
196 1176639 : if (block->IsInlineReturnTarget()) {
197 24858 : worklist.Add(block->inlined_entry_block()->block_id());
198 : }
199 : }
200 : }
201 : // Only collect bind/lookup instructions during the first pass.
202 302231 : collect_markers_ = false;
203 : }
204 :
205 : // Analysis finished. Zap dead environment slots.
206 2831312 : for (int i = 0; i < markers_.length(); ++i) {
207 6938257 : ZapEnvironmentSlotsForInstruction(markers_[i]);
208 : }
209 4599887 : for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
210 4319851 : HBasicBlock* block = graph()->blocks()->at(block_id);
211 4319851 : UpdateLivenessAtBlockEnd(block, &live);
212 4319849 : ZapEnvironmentSlotsInSuccessors(block, &live);
213 : }
214 :
215 : // Finally, remove the HEnvironment{Bind,Lookup} markers.
216 2831306 : for (int i = 0; i < markers_.length(); ++i) {
217 1275636 : markers_[i]->DeleteAndReplaceWith(NULL);
218 : }
219 280035 : }
220 :
221 :
222 : #ifdef DEBUG
223 : bool HEnvironmentLivenessAnalysisPhase::VerifyClosures(
224 : Handle<JSFunction> a, Handle<JSFunction> b) {
225 : Heap::RelocationLock for_heap_access(isolate()->heap());
226 : AllowHandleDereference for_verification;
227 : return a.is_identical_to(b);
228 : }
229 : #endif
230 :
231 : } // namespace internal
232 : } // namespace v8
|
