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 279505 : HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase(
14 279505 : HGraph* graph)
15 : : HPhase("H_Environment liveness analysis", graph),
16 279505 : 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 559010 : went_live_since_last_simulate_(maximum_environment_size_, zone()) {
25 : DCHECK(maximum_environment_size_ > 0);
26 4581321 : for (int i = 0; i < block_count_; ++i) {
27 : live_at_block_start_.Add(
28 4301816 : new(zone()) BitVector(maximum_environment_size_, zone()), zone());
29 : first_simulate_.Add(NULL, zone());
30 : first_simulate_invalid_for_index_.Add(
31 4301814 : new(zone()) BitVector(maximum_environment_size_, zone()), zone());
32 : }
33 279505 : }
34 :
35 :
36 488617 : void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot(
37 : int index, HSimulate* simulate) {
38 : int operand_index = simulate->ToOperandIndex(index);
39 488617 : if (operand_index == -1) {
40 488617 : simulate->AddAssignedValue(index, graph()->GetConstantOptimizedOut());
41 : } else {
42 123400 : simulate->SetOperandAt(operand_index, graph()->GetConstantOptimizedOut());
43 : }
44 488616 : }
45 :
46 :
47 4301809 : void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors(
48 8955190 : 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 9154092 : for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
52 4852286 : HBasicBlock* successor = it.Current();
53 : int successor_id = successor->block_id();
54 10299739 : BitVector* live_in_successor = live_at_block_start_[successor_id];
55 4852286 : if (live_in_successor->Equals(*live)) continue;
56 4653381 : for (int i = 0; i < live->length(); ++i) {
57 2203014 : if (!live->Contains(i)) continue;
58 595167 : if (live_in_successor->Contains(i)) continue;
59 585248 : if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) {
60 : continue;
61 : }
62 292553 : HSimulate* simulate = first_simulate_.at(successor_id);
63 292553 : if (simulate == NULL) continue;
64 : DCHECK(VerifyClosures(simulate->closure(),
65 : block->last_environment()->closure()));
66 273830 : ZapEnvironmentSlot(i, simulate);
67 : }
68 : }
69 4301806 : }
70 :
71 :
72 1280945 : void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction(
73 628795 : HEnvironmentMarker* marker) {
74 3842834 : if (!marker->CheckFlag(HValue::kEndsLiveRange)) return;
75 : HSimulate* simulate = marker->next_simulate();
76 414008 : if (simulate != NULL) {
77 : DCHECK(VerifyClosures(simulate->closure(), marker->closure()));
78 214787 : ZapEnvironmentSlot(marker->index(), simulate);
79 : }
80 : }
81 :
82 :
83 8865874 : void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd(
84 8865874 : HBasicBlock* block,
85 18890735 : BitVector* live) {
86 : // Liveness at the end of each block: union of liveness in successors.
87 : live->Clear();
88 18890693 : for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
89 20049722 : live->Union(*live_at_block_start_[it.Current()->block_id()]);
90 : }
91 8865816 : }
92 :
93 :
94 30611111 : void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction(
95 : HInstruction* instr,
96 3773843 : BitVector* live) {
97 30611111 : switch (instr->opcode()) {
98 : case HValue::kEnvironmentMarker: {
99 : HEnvironmentMarker* marker = HEnvironmentMarker::cast(instr);
100 3145486 : int index = marker->index();
101 1572743 : if (!live->Contains(index)) {
102 : marker->SetFlag(HValue::kEndsLiveRange);
103 : } else {
104 : marker->ClearFlag(HValue::kEndsLiveRange);
105 : }
106 8839894 : if (!went_live_since_last_simulate_.Contains(index)) {
107 1498299 : marker->set_next_simulate(last_simulate_);
108 : }
109 1572743 : 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 1572743 : if (collect_markers_) {
117 : // Populate |markers_| list during the first pass.
118 1280947 : 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 522442 : 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 522442 : 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 125375 : for (int i = 0; i < enter->return_targets()->length(); ++i) {
142 125375 : int return_id = enter->return_targets()->at(i)->block_id();
143 250750 : live->Union(*live_at_block_start_[return_id]);
144 : }
145 105915 : last_simulate_ = NULL;
146 105915 : break;
147 : }
148 : case HValue::kSimulate:
149 5093990 : last_simulate_ = HSimulate::cast(instr);
150 : went_live_since_last_simulate_.Clear();
151 : break;
152 : default:
153 : break;
154 : }
155 30611056 : }
156 :
157 :
158 279505 : 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 279505 : BitVector live(maximum_environment_size_, zone());
166 279506 : BitVector worklist(block_count_, zone());
167 4581330 : for (int i = 0; i < block_count_; ++i) {
168 4301821 : worklist.Add(i);
169 : }
170 1162316 : while (!worklist.IsEmpty()) {
171 7361860 : for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
172 14120422 : if (!worklist.Contains(block_id)) {
173 : continue;
174 : }
175 : worklist.Remove(block_id);
176 4564117 : last_simulate_ = NULL;
177 :
178 18019028 : HBasicBlock* block = graph()->blocks()->at(block_id);
179 4564117 : UpdateLivenessAtBlockEnd(block, &live);
180 :
181 35175236 : for (HInstruction* instr = block->end(); instr != NULL;
182 : instr = instr->previous()) {
183 30611118 : 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 4564118 : first_simulate_.Set(block_id, last_simulate_);
190 4564118 : first_simulate_invalid_for_index_[block_id]->CopyFrom(
191 4564118 : went_live_since_last_simulate_);
192 13692354 : if (live_at_block_start_[block_id]->UnionIsChanged(live)) {
193 1363731 : for (int i = 0; i < block->predecessors()->length(); ++i) {
194 1363731 : worklist.Add(block->predecessors()->at(i)->block_id());
195 : }
196 1170482 : if (block->IsInlineReturnTarget()) {
197 24840 : worklist.Add(block->inlined_entry_block()->block_id());
198 : }
199 : }
200 : }
201 : // Only collect bind/lookup instructions during the first pass.
202 301649 : collect_markers_ = false;
203 : }
204 :
205 : // Analysis finished. Zap dead environment slots.
206 2841400 : for (int i = 0; i < markers_.length(); ++i) {
207 6963753 : ZapEnvironmentSlotsForInstruction(markers_[i]);
208 : }
209 4581312 : for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
210 4301805 : HBasicBlock* block = graph()->blocks()->at(block_id);
211 4301805 : UpdateLivenessAtBlockEnd(block, &live);
212 4301808 : ZapEnvironmentSlotsInSuccessors(block, &live);
213 : }
214 :
215 : // Finally, remove the HEnvironment{Bind,Lookup} markers.
216 2841403 : for (int i = 0; i < markers_.length(); ++i) {
217 1280949 : markers_[i]->DeleteAndReplaceWith(NULL);
218 : }
219 279506 : }
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
|
