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