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 : #include "src/crankshaft/hydrogen-escape-analysis.h"
6 : #include "src/objects-inl.h"
7 :
8 : namespace v8 {
9 : namespace internal {
10 :
11 :
12 17609 : bool HEscapeAnalysisPhase::HasNoEscapingUses(HValue* value, int size) {
13 22486 : for (HUseIterator it(value->uses()); !it.Done(); it.Advance()) {
14 36629 : HValue* use = it.value();
15 36629 : if (use->HasEscapingOperandAt(it.index())) {
16 13563 : if (FLAG_trace_escape_analysis) {
17 : PrintF("#%d (%s) escapes through #%d (%s) @%d\n", value->id(),
18 0 : value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
19 : }
20 14143 : return false;
21 : }
22 23066 : if (use->HasOutOfBoundsAccess(size)) {
23 0 : if (FLAG_trace_escape_analysis) {
24 : PrintF("#%d (%s) out of bounds at #%d (%s) @%d\n", value->id(),
25 0 : value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
26 : }
27 : return false;
28 : }
29 23066 : int redefined_index = use->RedefinedOperandIndex();
30 23066 : if (redefined_index == it.index() && !HasNoEscapingUses(use, size)) {
31 580 : if (FLAG_trace_escape_analysis) {
32 : PrintF("#%d (%s) escapes redefinition #%d (%s) @%d\n", value->id(),
33 0 : value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
34 : }
35 : return false;
36 : }
37 : }
38 3466 : return true;
39 : }
40 :
41 :
42 281359 : void HEscapeAnalysisPhase::CollectCapturedValues() {
43 4383110 : int block_count = graph()->blocks()->length();
44 4383112 : for (int i = 0; i < block_count; ++i) {
45 4101751 : HBasicBlock* block = graph()->blocks()->at(i);
46 30579050 : for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
47 : HInstruction* instr = it.Current();
48 52954596 : if (!instr->IsAllocate()) continue;
49 : HAllocate* allocate = HAllocate::cast(instr);
50 21850 : if (!allocate->size()->IsInteger32Constant()) continue;
51 14216 : int size_in_bytes = allocate->size()->GetInteger32Constant();
52 14216 : if (HasNoEscapingUses(instr, size_in_bytes)) {
53 653 : if (FLAG_trace_escape_analysis) {
54 : PrintF("#%d (%s) is being captured\n", instr->id(),
55 0 : instr->Mnemonic());
56 : }
57 653 : captured_.Add(instr, zone());
58 : }
59 : }
60 : }
61 281361 : }
62 :
63 :
64 10961 : HCapturedObject* HEscapeAnalysisPhase::NewState(HInstruction* previous) {
65 10961 : Zone* zone = graph()->zone();
66 : HCapturedObject* state =
67 10961 : new(zone) HCapturedObject(number_of_values_, number_of_objects_, zone);
68 10961 : state->InsertAfter(previous);
69 10961 : return state;
70 : }
71 :
72 :
73 : // Create a new state for replacing HAllocate instructions.
74 653 : HCapturedObject* HEscapeAnalysisPhase::NewStateForAllocation(
75 : HInstruction* previous) {
76 653 : HConstant* undefined = graph()->GetConstantUndefined();
77 653 : HCapturedObject* state = NewState(previous);
78 3563 : for (int index = 0; index < number_of_values_; index++) {
79 2910 : state->SetOperandAt(index, undefined);
80 : }
81 653 : return state;
82 : }
83 :
84 :
85 : // Create a new state full of phis for loop header entries.
86 942 : HCapturedObject* HEscapeAnalysisPhase::NewStateForLoopHeader(
87 : HInstruction* previous,
88 : HCapturedObject* old_state) {
89 942 : HBasicBlock* block = previous->block();
90 942 : HCapturedObject* state = NewState(previous);
91 5521 : for (int index = 0; index < number_of_values_; index++) {
92 : HValue* operand = old_state->OperandAt(index);
93 4579 : HPhi* phi = NewPhiAndInsert(block, operand, index);
94 4579 : state->SetOperandAt(index, phi);
95 : }
96 942 : return state;
97 : }
98 :
99 :
100 : // Create a new state by copying an existing one.
101 9366 : HCapturedObject* HEscapeAnalysisPhase::NewStateCopy(
102 : HInstruction* previous,
103 : HCapturedObject* old_state) {
104 9366 : HCapturedObject* state = NewState(previous);
105 55078 : for (int index = 0; index < number_of_values_; index++) {
106 : HValue* operand = old_state->OperandAt(index);
107 45712 : state->SetOperandAt(index, operand);
108 : }
109 9366 : return state;
110 : }
111 :
112 :
113 : // Insert a newly created phi into the given block and fill all incoming
114 : // edges with the given value.
115 15952 : HPhi* HEscapeAnalysisPhase::NewPhiAndInsert(HBasicBlock* block,
116 : HValue* incoming_value,
117 : int index) {
118 15952 : Zone* zone = graph()->zone();
119 15952 : HPhi* phi = new(zone) HPhi(HPhi::kInvalidMergedIndex, zone);
120 132105 : for (int i = 0; i < block->predecessors()->length(); i++) {
121 116153 : phi->AddInput(incoming_value);
122 : }
123 15952 : block->AddPhi(phi);
124 15952 : return phi;
125 : }
126 :
127 :
128 : // Insert a newly created value check as a replacement for map checks.
129 1390 : HValue* HEscapeAnalysisPhase::NewMapCheckAndInsert(HCapturedObject* state,
130 1390 : HCheckMaps* mapcheck) {
131 1390 : Zone* zone = graph()->zone();
132 : HValue* value = state->map_value();
133 : // TODO(mstarzinger): This will narrow a map check against a set of maps
134 : // down to the first element in the set. Revisit and fix this.
135 : HCheckValue* check = HCheckValue::New(graph()->isolate(), zone, NULL, value,
136 2780 : mapcheck->maps()->at(0), false);
137 1390 : check->InsertBefore(mapcheck);
138 1390 : return check;
139 : }
140 :
141 :
142 : // Replace a field load with a given value, forcing Smi representation if
143 : // necessary.
144 843 : HValue* HEscapeAnalysisPhase::NewLoadReplacement(
145 : HLoadNamedField* load, HValue* load_value) {
146 : HValue* replacement = load_value;
147 : Representation representation = load->representation();
148 843 : if (representation.IsSmiOrInteger32() || representation.IsDouble()) {
149 385 : Zone* zone = graph()->zone();
150 : HInstruction* new_instr = HForceRepresentation::New(
151 385 : graph()->isolate(), zone, NULL, load_value, representation);
152 385 : new_instr->InsertAfter(load);
153 : replacement = new_instr;
154 : }
155 843 : return replacement;
156 : }
157 :
158 :
159 : // Performs a forward data-flow analysis of all loads and stores on the
160 : // given captured allocation. This uses a reverse post-order iteration
161 : // over affected basic blocks. All non-escaping instructions are handled
162 : // and replaced during the analysis.
163 653 : void HEscapeAnalysisPhase::AnalyzeDataFlow(HInstruction* allocate) {
164 1306 : HBasicBlock* allocate_block = allocate->block();
165 96212 : block_states_.AddBlock(NULL, graph()->blocks()->length(), zone());
166 :
167 : // Iterate all blocks starting with the allocation block, since the
168 : // allocation cannot dominate blocks that come before.
169 : int start = allocate_block->block_id();
170 191118 : for (int i = start; i < graph()->blocks()->length(); i++) {
171 426462 : HBasicBlock* block = graph()->blocks()->at(i);
172 : HCapturedObject* state = StateAt(block);
173 :
174 : // Skip blocks that are not dominated by the captured allocation.
175 94906 : if (!allocate_block->Dominates(block) && allocate_block != block) continue;
176 94866 : if (FLAG_trace_escape_analysis) {
177 0 : PrintF("Analyzing data-flow in B%d\n", block->block_id());
178 : }
179 :
180 : // Go through all instructions of the current block.
181 567275 : for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
182 : HInstruction* instr = it.Current();
183 472409 : switch (instr->opcode()) {
184 : case HValue::kAllocate: {
185 1138 : if (instr != allocate) continue;
186 653 : state = NewStateForAllocation(allocate);
187 653 : break;
188 : }
189 : case HValue::kLoadNamedField: {
190 : HLoadNamedField* load = HLoadNamedField::cast(instr);
191 3028 : int index = load->access().offset() / kPointerSize;
192 3028 : if (load->object() != allocate) continue;
193 : DCHECK(load->access().IsInobject());
194 0 : HValue* replacement =
195 843 : NewLoadReplacement(load, state->OperandAt(index));
196 843 : load->DeleteAndReplaceWith(replacement);
197 843 : if (FLAG_trace_escape_analysis) {
198 : PrintF("Replacing load #%d with #%d (%s)\n", load->id(),
199 0 : replacement->id(), replacement->Mnemonic());
200 : }
201 : break;
202 : }
203 : case HValue::kStoreNamedField: {
204 4396 : HStoreNamedField* store = HStoreNamedField::cast(instr);
205 7670 : int index = store->access().offset() / kPointerSize;
206 7670 : if (store->object() != allocate) continue;
207 : DCHECK(store->access().IsInobject());
208 4396 : state = NewStateCopy(store->previous(), state);
209 4396 : state->SetOperandAt(index, store->value());
210 4396 : if (store->has_transition()) {
211 287 : state->SetOperandAt(0, store->transition());
212 : }
213 4396 : if (store->HasObservableSideEffects()) {
214 : state->ReuseSideEffectsFromStore(store);
215 : }
216 4396 : store->DeleteAndReplaceWith(store->ActualValue());
217 4396 : if (FLAG_trace_escape_analysis) {
218 : PrintF("Replacing store #%d%s\n", instr->id(),
219 0 : store->has_transition() ? " (with transition)" : "");
220 : }
221 : break;
222 : }
223 : case HValue::kArgumentsObject:
224 : case HValue::kCapturedObject:
225 : case HValue::kSimulate: {
226 106411 : for (int i = 0; i < instr->OperandCount(); i++) {
227 106411 : if (instr->OperandAt(i) != allocate) continue;
228 1428 : instr->SetOperandAt(i, state);
229 : }
230 : break;
231 : }
232 : case HValue::kCheckHeapObject: {
233 : HCheckHeapObject* check = HCheckHeapObject::cast(instr);
234 1472 : if (check->value() != allocate) continue;
235 200 : check->DeleteAndReplaceWith(check->ActualValue());
236 200 : break;
237 : }
238 : case HValue::kCheckMaps: {
239 : HCheckMaps* mapcheck = HCheckMaps::cast(instr);
240 4839 : if (mapcheck->value() != allocate) continue;
241 1390 : NewMapCheckAndInsert(state, mapcheck);
242 1390 : mapcheck->DeleteAndReplaceWith(mapcheck->ActualValue());
243 1390 : break;
244 : }
245 : default:
246 : // Nothing to see here, move along ...
247 : break;
248 : }
249 : }
250 :
251 : // Propagate the block state forward to all successor blocks.
252 426422 : for (int i = 0; i < block->end()->SuccessorCount(); i++) {
253 124257 : HBasicBlock* succ = block->end()->SuccessorAt(i);
254 118345 : if (!allocate_block->Dominates(succ)) continue;
255 118335 : if (succ->predecessors()->length() == 1) {
256 : // Case 1: This is the only predecessor, just reuse state.
257 : SetStateAt(succ, state);
258 35946 : } else if (StateAt(succ) == NULL && succ->IsLoopHeader()) {
259 : // Case 2: This is a state that enters a loop header, be
260 : // pessimistic about loop headers, add phis for all values.
261 942 : SetStateAt(succ, NewStateForLoopHeader(succ->first(), state));
262 29092 : } else if (StateAt(succ) == NULL) {
263 : // Case 3: This is the first state propagated forward to the
264 : // successor, leave a copy of the current state.
265 4970 : SetStateAt(succ, NewStateCopy(succ->first(), state));
266 : } else {
267 : // Case 4: This is a state that needs merging with previously
268 : // propagated states, potentially introducing new phis lazily or
269 : // adding values to existing phis.
270 : HCapturedObject* succ_state = StateAt(succ);
271 120927 : for (int index = 0; index < number_of_values_; index++) {
272 : HValue* operand = state->OperandAt(index);
273 105780 : HValue* succ_operand = succ_state->OperandAt(index);
274 226707 : if (succ_operand->IsPhi() && succ_operand->block() == succ) {
275 : // Phi already exists, add operand.
276 : HPhi* phi = HPhi::cast(succ_operand);
277 52198 : phi->SetOperandAt(succ->PredecessorIndexOf(block), operand);
278 68729 : } else if (succ_operand != operand) {
279 : // Phi does not exist, introduce one.
280 11373 : HPhi* phi = NewPhiAndInsert(succ, succ_operand, index);
281 11373 : phi->SetOperandAt(succ->PredecessorIndexOf(block), operand);
282 11373 : succ_state->SetOperandAt(index, phi);
283 : }
284 : }
285 : }
286 : }
287 : }
288 :
289 : // All uses have been handled.
290 : DCHECK(allocate->HasNoUses());
291 653 : allocate->DeleteAndReplaceWith(NULL);
292 653 : }
293 :
294 :
295 561 : void HEscapeAnalysisPhase::PerformScalarReplacement() {
296 2428 : for (int i = 0; i < captured_.length(); i++) {
297 1867 : HAllocate* allocate = HAllocate::cast(captured_.at(i));
298 :
299 : // Compute number of scalar values and start with clean slate.
300 653 : int size_in_bytes = allocate->size()->GetInteger32Constant();
301 653 : number_of_values_ = size_in_bytes / kPointerSize;
302 653 : number_of_objects_++;
303 : block_states_.Rewind(0);
304 :
305 : // Perform actual analysis step.
306 653 : AnalyzeDataFlow(allocate);
307 :
308 653 : cumulative_values_ += number_of_values_;
309 : DCHECK(allocate->HasNoUses());
310 : DCHECK(!allocate->IsLinked());
311 : }
312 561 : }
313 :
314 :
315 283729 : void HEscapeAnalysisPhase::Run() {
316 : // TODO(mstarzinger): We disable escape analysis with OSR for now, because
317 : // spill slots might be uninitialized. Needs investigation.
318 567457 : if (graph()->has_osr()) return;
319 281361 : int max_fixpoint_iteration_count = FLAG_escape_analysis_iterations;
320 281922 : for (int i = 0; i < max_fixpoint_iteration_count; i++) {
321 281361 : CollectCapturedValues();
322 281360 : if (captured_.is_empty()) break;
323 561 : PerformScalarReplacement();
324 : captured_.Rewind(0);
325 : }
326 : }
327 :
328 :
329 : } // namespace internal
330 : } // namespace v8
|
