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 
7 namespace v8 {
8 namespace internal {
9 
10 
HasNoEscapingUses(HValue * value,int size)11 bool HEscapeAnalysisPhase::HasNoEscapingUses(HValue* value, int size) {
12   for (HUseIterator it(value->uses()); !it.Done(); it.Advance()) {
13     HValue* use = it.value();
14     if (use->HasEscapingOperandAt(it.index())) {
15       if (FLAG_trace_escape_analysis) {
16         PrintF("#%d (%s) escapes through #%d (%s) @%d\n", value->id(),
17                value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
18       }
19       return false;
20     }
21     if (use->HasOutOfBoundsAccess(size)) {
22       if (FLAG_trace_escape_analysis) {
23         PrintF("#%d (%s) out of bounds at #%d (%s) @%d\n", value->id(),
24                value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
25       }
26       return false;
27     }
28     int redefined_index = use->RedefinedOperandIndex();
29     if (redefined_index == it.index() && !HasNoEscapingUses(use, size)) {
30       if (FLAG_trace_escape_analysis) {
31         PrintF("#%d (%s) escapes redefinition #%d (%s) @%d\n", value->id(),
32                value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
33       }
34       return false;
35     }
36   }
37   return true;
38 }
39 
40 
CollectCapturedValues()41 void HEscapeAnalysisPhase::CollectCapturedValues() {
42   int block_count = graph()->blocks()->length();
43   for (int i = 0; i < block_count; ++i) {
44     HBasicBlock* block = graph()->blocks()->at(i);
45     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
46       HInstruction* instr = it.Current();
47       if (!instr->IsAllocate()) continue;
48       HAllocate* allocate = HAllocate::cast(instr);
49       if (!allocate->size()->IsInteger32Constant()) continue;
50       int size_in_bytes = allocate->size()->GetInteger32Constant();
51       if (HasNoEscapingUses(instr, size_in_bytes)) {
52         if (FLAG_trace_escape_analysis) {
53           PrintF("#%d (%s) is being captured\n", instr->id(),
54                  instr->Mnemonic());
55         }
56         captured_.Add(instr, zone());
57       }
58     }
59   }
60 }
61 
62 
NewState(HInstruction * previous)63 HCapturedObject* HEscapeAnalysisPhase::NewState(HInstruction* previous) {
64   Zone* zone = graph()->zone();
65   HCapturedObject* state =
66       new(zone) HCapturedObject(number_of_values_, number_of_objects_, zone);
67   state->InsertAfter(previous);
68   return state;
69 }
70 
71 
72 // Create a new state for replacing HAllocate instructions.
NewStateForAllocation(HInstruction * previous)73 HCapturedObject* HEscapeAnalysisPhase::NewStateForAllocation(
74     HInstruction* previous) {
75   HConstant* undefined = graph()->GetConstantUndefined();
76   HCapturedObject* state = NewState(previous);
77   for (int index = 0; index < number_of_values_; index++) {
78     state->SetOperandAt(index, undefined);
79   }
80   return state;
81 }
82 
83 
84 // Create a new state full of phis for loop header entries.
NewStateForLoopHeader(HInstruction * previous,HCapturedObject * old_state)85 HCapturedObject* HEscapeAnalysisPhase::NewStateForLoopHeader(
86     HInstruction* previous,
87     HCapturedObject* old_state) {
88   HBasicBlock* block = previous->block();
89   HCapturedObject* state = NewState(previous);
90   for (int index = 0; index < number_of_values_; index++) {
91     HValue* operand = old_state->OperandAt(index);
92     HPhi* phi = NewPhiAndInsert(block, operand, index);
93     state->SetOperandAt(index, phi);
94   }
95   return state;
96 }
97 
98 
99 // Create a new state by copying an existing one.
NewStateCopy(HInstruction * previous,HCapturedObject * old_state)100 HCapturedObject* HEscapeAnalysisPhase::NewStateCopy(
101     HInstruction* previous,
102     HCapturedObject* old_state) {
103   HCapturedObject* state = NewState(previous);
104   for (int index = 0; index < number_of_values_; index++) {
105     HValue* operand = old_state->OperandAt(index);
106     state->SetOperandAt(index, operand);
107   }
108   return state;
109 }
110 
111 
112 // Insert a newly created phi into the given block and fill all incoming
113 // edges with the given value.
NewPhiAndInsert(HBasicBlock * block,HValue * incoming_value,int index)114 HPhi* HEscapeAnalysisPhase::NewPhiAndInsert(HBasicBlock* block,
115                                             HValue* incoming_value,
116                                             int index) {
117   Zone* zone = graph()->zone();
118   HPhi* phi = new(zone) HPhi(HPhi::kInvalidMergedIndex, zone);
119   for (int i = 0; i < block->predecessors()->length(); i++) {
120     phi->AddInput(incoming_value);
121   }
122   block->AddPhi(phi);
123   return phi;
124 }
125 
126 
127 // Insert a newly created value check as a replacement for map checks.
NewMapCheckAndInsert(HCapturedObject * state,HCheckMaps * mapcheck)128 HValue* HEscapeAnalysisPhase::NewMapCheckAndInsert(HCapturedObject* state,
129                                                    HCheckMaps* mapcheck) {
130   Zone* zone = graph()->zone();
131   HValue* value = state->map_value();
132   // TODO(mstarzinger): This will narrow a map check against a set of maps
133   // down to the first element in the set. Revisit and fix this.
134   HCheckValue* check = HCheckValue::New(graph()->isolate(), zone, NULL, value,
135                                         mapcheck->maps()->at(0), false);
136   check->InsertBefore(mapcheck);
137   return check;
138 }
139 
140 
141 // Replace a field load with a given value, forcing Smi representation if
142 // necessary.
NewLoadReplacement(HLoadNamedField * load,HValue * load_value)143 HValue* HEscapeAnalysisPhase::NewLoadReplacement(
144     HLoadNamedField* load, HValue* load_value) {
145   isolate()->counters()->crankshaft_escape_loads_replaced()->Increment();
146   HValue* replacement = load_value;
147   Representation representation = load->representation();
148   if (representation.IsSmiOrInteger32() || representation.IsDouble()) {
149     Zone* zone = graph()->zone();
150     HInstruction* new_instr = HForceRepresentation::New(
151         graph()->isolate(), zone, NULL, load_value, representation);
152     new_instr->InsertAfter(load);
153     replacement = new_instr;
154   }
155   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.
AnalyzeDataFlow(HInstruction * allocate)163 void HEscapeAnalysisPhase::AnalyzeDataFlow(HInstruction* allocate) {
164   HBasicBlock* allocate_block = allocate->block();
165   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   for (int i = start; i < graph()->blocks()->length(); i++) {
171     HBasicBlock* block = graph()->blocks()->at(i);
172     HCapturedObject* state = StateAt(block);
173 
174     // Skip blocks that are not dominated by the captured allocation.
175     if (!allocate_block->Dominates(block) && allocate_block != block) continue;
176     if (FLAG_trace_escape_analysis) {
177       PrintF("Analyzing data-flow in B%d\n", block->block_id());
178     }
179 
180     // Go through all instructions of the current block.
181     for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
182       HInstruction* instr = it.Current();
183       switch (instr->opcode()) {
184         case HValue::kAllocate: {
185           if (instr != allocate) continue;
186           state = NewStateForAllocation(allocate);
187           break;
188         }
189         case HValue::kLoadNamedField: {
190           HLoadNamedField* load = HLoadNamedField::cast(instr);
191           int index = load->access().offset() / kPointerSize;
192           if (load->object() != allocate) continue;
193           DCHECK(load->access().IsInobject());
194           HValue* replacement =
195             NewLoadReplacement(load, state->OperandAt(index));
196           load->DeleteAndReplaceWith(replacement);
197           if (FLAG_trace_escape_analysis) {
198             PrintF("Replacing load #%d with #%d (%s)\n", load->id(),
199                    replacement->id(), replacement->Mnemonic());
200           }
201           break;
202         }
203         case HValue::kStoreNamedField: {
204           HStoreNamedField* store = HStoreNamedField::cast(instr);
205           int index = store->access().offset() / kPointerSize;
206           if (store->object() != allocate) continue;
207           DCHECK(store->access().IsInobject());
208           state = NewStateCopy(store->previous(), state);
209           state->SetOperandAt(index, store->value());
210           if (store->has_transition()) {
211             state->SetOperandAt(0, store->transition());
212           }
213           if (store->HasObservableSideEffects()) {
214             state->ReuseSideEffectsFromStore(store);
215           }
216           store->DeleteAndReplaceWith(store->ActualValue());
217           if (FLAG_trace_escape_analysis) {
218             PrintF("Replacing store #%d%s\n", instr->id(),
219                    store->has_transition() ? " (with transition)" : "");
220           }
221           break;
222         }
223         case HValue::kArgumentsObject:
224         case HValue::kCapturedObject:
225         case HValue::kSimulate: {
226           for (int i = 0; i < instr->OperandCount(); i++) {
227             if (instr->OperandAt(i) != allocate) continue;
228             instr->SetOperandAt(i, state);
229           }
230           break;
231         }
232         case HValue::kCheckHeapObject: {
233           HCheckHeapObject* check = HCheckHeapObject::cast(instr);
234           if (check->value() != allocate) continue;
235           check->DeleteAndReplaceWith(check->ActualValue());
236           break;
237         }
238         case HValue::kCheckMaps: {
239           HCheckMaps* mapcheck = HCheckMaps::cast(instr);
240           if (mapcheck->value() != allocate) continue;
241           NewMapCheckAndInsert(state, mapcheck);
242           mapcheck->DeleteAndReplaceWith(mapcheck->ActualValue());
243           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     for (int i = 0; i < block->end()->SuccessorCount(); i++) {
253       HBasicBlock* succ = block->end()->SuccessorAt(i);
254       if (!allocate_block->Dominates(succ)) continue;
255       if (succ->predecessors()->length() == 1) {
256         // Case 1: This is the only predecessor, just reuse state.
257         SetStateAt(succ, state);
258       } 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         SetStateAt(succ, NewStateForLoopHeader(succ->first(), state));
262       } 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         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         for (int index = 0; index < number_of_values_; index++) {
272           HValue* operand = state->OperandAt(index);
273           HValue* succ_operand = succ_state->OperandAt(index);
274           if (succ_operand->IsPhi() && succ_operand->block() == succ) {
275             // Phi already exists, add operand.
276             HPhi* phi = HPhi::cast(succ_operand);
277             phi->SetOperandAt(succ->PredecessorIndexOf(block), operand);
278           } else if (succ_operand != operand) {
279             // Phi does not exist, introduce one.
280             HPhi* phi = NewPhiAndInsert(succ, succ_operand, index);
281             phi->SetOperandAt(succ->PredecessorIndexOf(block), operand);
282             succ_state->SetOperandAt(index, phi);
283           }
284         }
285       }
286     }
287   }
288 
289   // All uses have been handled.
290   DCHECK(allocate->HasNoUses());
291   allocate->DeleteAndReplaceWith(NULL);
292 }
293 
294 
PerformScalarReplacement()295 void HEscapeAnalysisPhase::PerformScalarReplacement() {
296   for (int i = 0; i < captured_.length(); i++) {
297     HAllocate* allocate = HAllocate::cast(captured_.at(i));
298 
299     // Compute number of scalar values and start with clean slate.
300     int size_in_bytes = allocate->size()->GetInteger32Constant();
301     number_of_values_ = size_in_bytes / kPointerSize;
302     number_of_objects_++;
303     block_states_.Rewind(0);
304 
305     // Perform actual analysis step.
306     AnalyzeDataFlow(allocate);
307 
308     cumulative_values_ += number_of_values_;
309     DCHECK(allocate->HasNoUses());
310     DCHECK(!allocate->IsLinked());
311   }
312 }
313 
314 
Run()315 void HEscapeAnalysisPhase::Run() {
316   // TODO(mstarzinger): We disable escape analysis with OSR for now, because
317   // spill slots might be uninitialized. Needs investigation.
318   if (graph()->has_osr()) return;
319   int max_fixpoint_iteration_count = FLAG_escape_analysis_iterations;
320   for (int i = 0; i < max_fixpoint_iteration_count; i++) {
321     CollectCapturedValues();
322     if (captured_.is_empty()) break;
323     isolate()->counters()->crankshaft_escape_allocs_replaced()->Increment(
324         captured_.length());
325     PerformScalarReplacement();
326     captured_.Rewind(0);
327   }
328 }
329 
330 
331 }  // namespace internal
332 }  // namespace v8
333