hydrogen-escape-analysis.cc 12.1 KB
Newer Older
1
// Copyright 2013 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5
#include "src/crankshaft/hydrogen-escape-analysis.h"
6
#include "src/objects-inl.h"
7 8 9 10 11

namespace v8 {
namespace internal {


12
bool HEscapeAnalysisPhase::HasNoEscapingUses(HValue* value, int size) {
13
  for (HUseIterator it(value->uses()); !it.Done(); it.Advance()) {
14 15 16
    HValue* use = it.value();
    if (use->HasEscapingOperandAt(it.index())) {
      if (FLAG_trace_escape_analysis) {
17 18
        PrintF("#%d (%s) escapes through #%d (%s) @%d\n", value->id(),
               value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
19
      }
20 21
      return false;
    }
22 23 24 25 26 27 28 29 30
    if (use->HasOutOfBoundsAccess(size)) {
      if (FLAG_trace_escape_analysis) {
        PrintF("#%d (%s) out of bounds at #%d (%s) @%d\n", value->id(),
               value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
      }
      return false;
    }
    int redefined_index = use->RedefinedOperandIndex();
    if (redefined_index == it.index() && !HasNoEscapingUses(use, size)) {
31 32 33 34 35
      if (FLAG_trace_escape_analysis) {
        PrintF("#%d (%s) escapes redefinition #%d (%s) @%d\n", value->id(),
               value->Mnemonic(), use->id(), use->Mnemonic(), it.index());
      }
      return false;
36 37
    }
  }
38
  return true;
39 40 41
}


42 43
void HEscapeAnalysisPhase::CollectCapturedValues() {
  int block_count = graph()->blocks()->length();
44
  for (int i = 0; i < block_count; ++i) {
45
    HBasicBlock* block = graph()->blocks()->at(i);
46 47
    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
      HInstruction* instr = it.Current();
48 49 50 51 52
      if (!instr->IsAllocate()) continue;
      HAllocate* allocate = HAllocate::cast(instr);
      if (!allocate->size()->IsInteger32Constant()) continue;
      int size_in_bytes = allocate->size()->GetInteger32Constant();
      if (HasNoEscapingUses(instr, size_in_bytes)) {
53 54 55 56 57
        if (FLAG_trace_escape_analysis) {
          PrintF("#%d (%s) is being captured\n", instr->id(),
                 instr->Mnemonic());
        }
        captured_.Add(instr, zone());
58 59 60 61 62 63
      }
    }
  }
}


64 65
HCapturedObject* HEscapeAnalysisPhase::NewState(HInstruction* previous) {
  Zone* zone = graph()->zone();
66 67
  HCapturedObject* state =
      new(zone) HCapturedObject(number_of_values_, number_of_objects_, zone);
68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
  state->InsertAfter(previous);
  return state;
}


// Create a new state for replacing HAllocate instructions.
HCapturedObject* HEscapeAnalysisPhase::NewStateForAllocation(
    HInstruction* previous) {
  HConstant* undefined = graph()->GetConstantUndefined();
  HCapturedObject* state = NewState(previous);
  for (int index = 0; index < number_of_values_; index++) {
    state->SetOperandAt(index, undefined);
  }
  return state;
}


// Create a new state full of phis for loop header entries.
HCapturedObject* HEscapeAnalysisPhase::NewStateForLoopHeader(
87 88
    HInstruction* previous,
    HCapturedObject* old_state) {
89 90 91 92 93 94 95 96 97 98 99 100 101
  HBasicBlock* block = previous->block();
  HCapturedObject* state = NewState(previous);
  for (int index = 0; index < number_of_values_; index++) {
    HValue* operand = old_state->OperandAt(index);
    HPhi* phi = NewPhiAndInsert(block, operand, index);
    state->SetOperandAt(index, phi);
  }
  return state;
}


// Create a new state by copying an existing one.
HCapturedObject* HEscapeAnalysisPhase::NewStateCopy(
102 103
    HInstruction* previous,
    HCapturedObject* old_state) {
104 105 106 107 108 109 110 111 112 113
  HCapturedObject* state = NewState(previous);
  for (int index = 0; index < number_of_values_; index++) {
    HValue* operand = old_state->OperandAt(index);
    state->SetOperandAt(index, operand);
  }
  return state;
}


// Insert a newly created phi into the given block and fill all incoming
114
// edges with the given value.
115 116 117
HPhi* HEscapeAnalysisPhase::NewPhiAndInsert(HBasicBlock* block,
                                            HValue* incoming_value,
                                            int index) {
118
  Zone* zone = graph()->zone();
119
  HPhi* phi = new(zone) HPhi(HPhi::kInvalidMergedIndex, zone);
120 121 122 123 124 125 126 127
  for (int i = 0; i < block->predecessors()->length(); i++) {
    phi->AddInput(incoming_value);
  }
  block->AddPhi(phi);
  return phi;
}


128 129 130 131 132 133 134
// Insert a newly created value check as a replacement for map checks.
HValue* HEscapeAnalysisPhase::NewMapCheckAndInsert(HCapturedObject* state,
                                                   HCheckMaps* mapcheck) {
  Zone* zone = graph()->zone();
  HValue* value = state->map_value();
  // TODO(mstarzinger): This will narrow a map check against a set of maps
  // down to the first element in the set. Revisit and fix this.
135 136
  HCheckValue* check = HCheckValue::New(graph()->isolate(), zone, NULL, value,
                                        mapcheck->maps()->at(0), false);
137 138 139 140 141
  check->InsertBefore(mapcheck);
  return check;
}


142 143 144 145 146 147
// Replace a field load with a given value, forcing Smi representation if
// necessary.
HValue* HEscapeAnalysisPhase::NewLoadReplacement(
    HLoadNamedField* load, HValue* load_value) {
  HValue* replacement = load_value;
  Representation representation = load->representation();
148
  if (representation.IsSmiOrInteger32() || representation.IsDouble()) {
149
    Zone* zone = graph()->zone();
150 151
    HInstruction* new_instr = HForceRepresentation::New(
        graph()->isolate(), zone, NULL, load_value, representation);
152 153 154 155 156 157 158
    new_instr->InsertAfter(load);
    replacement = new_instr;
  }
  return replacement;
}


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
// Performs a forward data-flow analysis of all loads and stores on the
// given captured allocation. This uses a reverse post-order iteration
// over affected basic blocks. All non-escaping instructions are handled
// and replaced during the analysis.
void HEscapeAnalysisPhase::AnalyzeDataFlow(HInstruction* allocate) {
  HBasicBlock* allocate_block = allocate->block();
  block_states_.AddBlock(NULL, graph()->blocks()->length(), zone());

  // Iterate all blocks starting with the allocation block, since the
  // allocation cannot dominate blocks that come before.
  int start = allocate_block->block_id();
  for (int i = start; i < graph()->blocks()->length(); i++) {
    HBasicBlock* block = graph()->blocks()->at(i);
    HCapturedObject* state = StateAt(block);

    // Skip blocks that are not dominated by the captured allocation.
    if (!allocate_block->Dominates(block) && allocate_block != block) continue;
    if (FLAG_trace_escape_analysis) {
      PrintF("Analyzing data-flow in B%d\n", block->block_id());
    }

    // Go through all instructions of the current block.
    for (HInstructionIterator it(block); !it.Done(); it.Advance()) {
      HInstruction* instr = it.Current();
      switch (instr->opcode()) {
        case HValue::kAllocate: {
          if (instr != allocate) continue;
          state = NewStateForAllocation(allocate);
          break;
        }
        case HValue::kLoadNamedField: {
          HLoadNamedField* load = HLoadNamedField::cast(instr);
          int index = load->access().offset() / kPointerSize;
          if (load->object() != allocate) continue;
193
          DCHECK(load->access().IsInobject());
194 195
          HValue* replacement =
            NewLoadReplacement(load, state->OperandAt(index));
196 197
          load->DeleteAndReplaceWith(replacement);
          if (FLAG_trace_escape_analysis) {
198
            PrintF("Replacing load #%d with #%d (%s)\n", load->id(),
199 200 201 202 203 204 205 206
                   replacement->id(), replacement->Mnemonic());
          }
          break;
        }
        case HValue::kStoreNamedField: {
          HStoreNamedField* store = HStoreNamedField::cast(instr);
          int index = store->access().offset() / kPointerSize;
          if (store->object() != allocate) continue;
207
          DCHECK(store->access().IsInobject());
208
          state = NewStateCopy(store->previous(), state);
209
          state->SetOperandAt(index, store->value());
210 211 212
          if (store->has_transition()) {
            state->SetOperandAt(0, store->transition());
          }
213 214 215
          if (store->HasObservableSideEffects()) {
            state->ReuseSideEffectsFromStore(store);
          }
216
          store->DeleteAndReplaceWith(store->ActualValue());
217
          if (FLAG_trace_escape_analysis) {
218 219
            PrintF("Replacing store #%d%s\n", instr->id(),
                   store->has_transition() ? " (with transition)" : "");
220 221 222 223
          }
          break;
        }
        case HValue::kArgumentsObject:
224 225
        case HValue::kCapturedObject:
        case HValue::kSimulate: {
226 227 228 229 230 231 232 233 234
          for (int i = 0; i < instr->OperandCount(); i++) {
            if (instr->OperandAt(i) != allocate) continue;
            instr->SetOperandAt(i, state);
          }
          break;
        }
        case HValue::kCheckHeapObject: {
          HCheckHeapObject* check = HCheckHeapObject::cast(instr);
          if (check->value() != allocate) continue;
235
          check->DeleteAndReplaceWith(check->ActualValue());
236 237 238 239 240
          break;
        }
        case HValue::kCheckMaps: {
          HCheckMaps* mapcheck = HCheckMaps::cast(instr);
          if (mapcheck->value() != allocate) continue;
241
          NewMapCheckAndInsert(state, mapcheck);
242
          mapcheck->DeleteAndReplaceWith(mapcheck->ActualValue());
243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289
          break;
        }
        default:
          // Nothing to see here, move along ...
          break;
      }
    }

    // Propagate the block state forward to all successor blocks.
    for (int i = 0; i < block->end()->SuccessorCount(); i++) {
      HBasicBlock* succ = block->end()->SuccessorAt(i);
      if (!allocate_block->Dominates(succ)) continue;
      if (succ->predecessors()->length() == 1) {
        // Case 1: This is the only predecessor, just reuse state.
        SetStateAt(succ, state);
      } else if (StateAt(succ) == NULL && succ->IsLoopHeader()) {
        // Case 2: This is a state that enters a loop header, be
        // pessimistic about loop headers, add phis for all values.
        SetStateAt(succ, NewStateForLoopHeader(succ->first(), state));
      } else if (StateAt(succ) == NULL) {
        // Case 3: This is the first state propagated forward to the
        // successor, leave a copy of the current state.
        SetStateAt(succ, NewStateCopy(succ->first(), state));
      } else {
        // Case 4: This is a state that needs merging with previously
        // propagated states, potentially introducing new phis lazily or
        // adding values to existing phis.
        HCapturedObject* succ_state = StateAt(succ);
        for (int index = 0; index < number_of_values_; index++) {
          HValue* operand = state->OperandAt(index);
          HValue* succ_operand = succ_state->OperandAt(index);
          if (succ_operand->IsPhi() && succ_operand->block() == succ) {
            // Phi already exists, add operand.
            HPhi* phi = HPhi::cast(succ_operand);
            phi->SetOperandAt(succ->PredecessorIndexOf(block), operand);
          } else if (succ_operand != operand) {
            // Phi does not exist, introduce one.
            HPhi* phi = NewPhiAndInsert(succ, succ_operand, index);
            phi->SetOperandAt(succ->PredecessorIndexOf(block), operand);
            succ_state->SetOperandAt(index, phi);
          }
        }
      }
    }
  }

  // All uses have been handled.
290
  DCHECK(allocate->HasNoUses());
291 292 293 294 295 296 297 298 299 300 301
  allocate->DeleteAndReplaceWith(NULL);
}


void HEscapeAnalysisPhase::PerformScalarReplacement() {
  for (int i = 0; i < captured_.length(); i++) {
    HAllocate* allocate = HAllocate::cast(captured_.at(i));

    // Compute number of scalar values and start with clean slate.
    int size_in_bytes = allocate->size()->GetInteger32Constant();
    number_of_values_ = size_in_bytes / kPointerSize;
302
    number_of_objects_++;
303
    block_states_.Rewind(0);
304

305
    // Perform actual analysis step.
306 307 308
    AnalyzeDataFlow(allocate);

    cumulative_values_ += number_of_values_;
309 310
    DCHECK(allocate->HasNoUses());
    DCHECK(!allocate->IsLinked());
311 312 313 314
  }
}


315 316 317 318
void HEscapeAnalysisPhase::Run() {
  // TODO(mstarzinger): We disable escape analysis with OSR for now, because
  // spill slots might be uninitialized. Needs investigation.
  if (graph()->has_osr()) return;
319 320 321 322 323
  int max_fixpoint_iteration_count = FLAG_escape_analysis_iterations;
  for (int i = 0; i < max_fixpoint_iteration_count; i++) {
    CollectCapturedValues();
    if (captured_.is_empty()) break;
    PerformScalarReplacement();
324
    captured_.Rewind(0);
325
  }
326 327 328
}


329 330
}  // namespace internal
}  // namespace v8