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
7namespace v8 {
8namespace internal {
9
10
11bool 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
41void 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
63HCapturedObject* 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.
73HCapturedObject* 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.
85HCapturedObject* 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.
100HCapturedObject* 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.
114HPhi* 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.
128HValue* 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.
143HValue* 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.
163void 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
295void 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
315void 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