hydrogen-environment-liveness.cc 7.95 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


6
#include "src/crankshaft/hydrogen-environment-liveness.h"
7 8 9 10 11 12


namespace v8 {
namespace internal {


13
HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase(
14
    HGraph* graph)
15
    : HPhase("H_Environment liveness analysis", graph),
16 17
      block_count_(graph->blocks()->length()),
      maximum_environment_size_(graph->maximum_environment_size()),
18 19 20 21
      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()),
22
      collect_markers_(true),
23 24
      last_simulate_(NULL),
      went_live_since_last_simulate_(maximum_environment_size_, zone()) {
25
  DCHECK(maximum_environment_size_ > 0);
26
  for (int i = 0; i < block_count_; ++i) {
27
    live_at_block_start_.Add(
28
        new(zone()) BitVector(maximum_environment_size_, zone()), zone());
29 30
    first_simulate_.Add(NULL, zone());
    first_simulate_invalid_for_index_.Add(
31 32 33 34 35
        new(zone()) BitVector(maximum_environment_size_, zone()), zone());
  }
}


36 37
void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot(
    int index, HSimulate* simulate) {
38 39
  int operand_index = simulate->ToOperandIndex(index);
  if (operand_index == -1) {
40
    simulate->AddAssignedValue(index, graph()->GetConstantUndefined());
41
  } else {
42
    simulate->SetOperandAt(operand_index, graph()->GetConstantUndefined());
43 44 45 46
  }
}


47 48
void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors(
    HBasicBlock* block, BitVector* live) {
49 50 51 52 53
  // 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();
54
    BitVector* live_in_successor = live_at_block_start_[successor_id];
55 56 57 58
    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;
59
      if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) {
60 61
        continue;
      }
62
      HSimulate* simulate = first_simulate_.at(successor_id);
63
      if (simulate == NULL) continue;
64
      DCHECK(VerifyClosures(simulate->closure(),
65
          block->last_environment()->closure()));
66 67 68 69 70 71
      ZapEnvironmentSlot(i, simulate);
    }
  }
}


72
void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction(
73 74 75 76
    HEnvironmentMarker* marker) {
  if (!marker->CheckFlag(HValue::kEndsLiveRange)) return;
  HSimulate* simulate = marker->next_simulate();
  if (simulate != NULL) {
77
    DCHECK(VerifyClosures(simulate->closure(), marker->closure()));
78 79 80 81 82
    ZapEnvironmentSlot(marker->index(), simulate);
  }
}


83
void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd(
84 85 86 87 88
    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()) {
89
    live->Union(*live_at_block_start_[it.Current()->block_id()]);
90 91 92 93
  }
}


94
void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction(
95 96 97 98 99 100 101 102 103 104 105
    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);
      }
106
      if (!went_live_since_last_simulate_.Contains(index)) {
107 108 109 110 111
        marker->set_next_simulate(last_simulate_);
      }
      if (marker->kind() == HEnvironmentMarker::LOOKUP) {
        live->Add(index);
      } else {
112
        DCHECK(marker->kind() == HEnvironmentMarker::BIND);
113
        live->Remove(index);
114
        went_live_since_last_simulate_.Add(index);
115 116 117
      }
      if (collect_markers_) {
        // Populate |markers_| list during the first pass.
118
        markers_.Add(marker, zone());
119 120 121 122 123 124 125 126
      }
      break;
    }
    case HValue::kLeaveInlined:
      // No environment values are live at the end of an inlined section.
      live->Clear();
      last_simulate_ = NULL;

127
      // The following DCHECKs guard the assumption used in case
128
      // kEnterInlined below:
129 130
      DCHECK(instr->next()->IsSimulate());
      DCHECK(instr->next()->next()->IsGoto());
131 132 133 134 135 136 137

      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
138
      // between (see DCHECKs above).
139 140 141 142
      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();
143
        live->Union(*live_at_block_start_[return_id]);
144 145 146 147 148 149
      }
      last_simulate_ = NULL;
      break;
    }
    case HValue::kSimulate:
      last_simulate_ = HSimulate::cast(instr);
150
      went_live_since_last_simulate_.Clear();
151 152 153 154 155 156 157
      break;
    default:
      break;
  }
}


158
void HEnvironmentLivenessAnalysisPhase::Run() {
159
  DCHECK(maximum_environment_size_ > 0);
160 161 162 163 164

  // 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.
165 166
  BitVector live(maximum_environment_size_, zone());
  BitVector worklist(block_count_, zone());
167
  for (int i = 0; i < block_count_; ++i) {
168
    worklist.Add(i);
169
  }
170
  while (!worklist.IsEmpty()) {
171
    for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
172
      if (!worklist.Contains(block_id)) {
173 174
        continue;
      }
175
      worklist.Remove(block_id);
176 177
      last_simulate_ = NULL;

178 179
      HBasicBlock* block = graph()->blocks()->at(block_id);
      UpdateLivenessAtBlockEnd(block, &live);
180

181
      for (HInstruction* instr = block->end(); instr != NULL;
182
           instr = instr->previous()) {
183
        UpdateLivenessAtInstruction(instr, &live);
184 185 186 187 188
      }

      // Reached the start of the block, do necessary bookkeeping:
      // store computed information for this block and add predecessors
      // to the work list as necessary.
189 190 191 192
      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)) {
193
        for (int i = 0; i < block->predecessors()->length(); ++i) {
194
          worklist.Add(block->predecessors()->at(i)->block_id());
195 196
        }
        if (block->IsInlineReturnTarget()) {
197
          worklist.Add(block->inlined_entry_block()->block_id());
198 199 200 201 202 203 204 205
        }
      }
    }
    // Only collect bind/lookup instructions during the first pass.
    collect_markers_ = false;
  }

  // Analysis finished. Zap dead environment slots.
206 207
  for (int i = 0; i < markers_.length(); ++i) {
    ZapEnvironmentSlotsForInstruction(markers_[i]);
208 209
  }
  for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
210 211 212
    HBasicBlock* block = graph()->blocks()->at(block_id);
    UpdateLivenessAtBlockEnd(block, &live);
    ZapEnvironmentSlotsInSuccessors(block, &live);
213 214 215
  }

  // Finally, remove the HEnvironment{Bind,Lookup} markers.
216 217
  for (int i = 0; i < markers_.length(); ++i) {
    markers_[i]->DeleteAndReplaceWith(NULL);
218 219 220
  }
}

221 222 223 224 225 226 227 228 229 230

#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

231 232
}  // namespace internal
}  // namespace v8