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
6#include "src/hydrogen-environment-liveness.h"
7
8
9namespace v8 {
10namespace internal {
11
12
13HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase(
14    HGraph* graph)
15    : HPhase("H_Environment liveness analysis", graph),
16      block_count_(graph->blocks()->length()),
17      maximum_environment_size_(graph->maximum_environment_size()),
18      live_at_block_start_(block_count_, zone()),
19      first_simulate_(block_count_, zone()),
20      first_simulate_invalid_for_index_(block_count_, zone()),
21      markers_(maximum_environment_size_, zone()),
22      collect_markers_(true),
23      last_simulate_(NULL),
24      went_live_since_last_simulate_(maximum_environment_size_, zone()) {
25  ASSERT(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    first_simulate_.Add(NULL, zone());
30    first_simulate_invalid_for_index_.Add(
31        new(zone()) BitVector(maximum_environment_size_, zone()), zone());
32  }
33}
34
35
36void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot(
37    int index, HSimulate* simulate) {
38  int operand_index = simulate->ToOperandIndex(index);
39  if (operand_index == -1) {
40    simulate->AddAssignedValue(index, graph()->GetConstantUndefined());
41  } else {
42    simulate->SetOperandAt(operand_index, graph()->GetConstantUndefined());
43  }
44}
45
46
47void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors(
48    HBasicBlock* block, BitVector* live) {
49  // When a value is live in successor A but dead in B, we must
50  // explicitly zap it in B.
51  for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
52    HBasicBlock* successor = it.Current();
53    int successor_id = successor->block_id();
54    BitVector* live_in_successor = live_at_block_start_[successor_id];
55    if (live_in_successor->Equals(*live)) continue;
56    for (int i = 0; i < live->length(); ++i) {
57      if (!live->Contains(i)) continue;
58      if (live_in_successor->Contains(i)) continue;
59      if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) {
60        continue;
61      }
62      HSimulate* simulate = first_simulate_.at(successor_id);
63      if (simulate == NULL) continue;
64      ASSERT(VerifyClosures(simulate->closure(),
65          block->last_environment()->closure()));
66      ZapEnvironmentSlot(i, simulate);
67    }
68  }
69}
70
71
72void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction(
73    HEnvironmentMarker* marker) {
74  if (!marker->CheckFlag(HValue::kEndsLiveRange)) return;
75  HSimulate* simulate = marker->next_simulate();
76  if (simulate != NULL) {
77    ASSERT(VerifyClosures(simulate->closure(), marker->closure()));
78    ZapEnvironmentSlot(marker->index(), simulate);
79  }
80}
81
82
83void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd(
84    HBasicBlock* block,
85    BitVector* live) {
86  // Liveness at the end of each block: union of liveness in successors.
87  live->Clear();
88  for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
89    live->Union(*live_at_block_start_[it.Current()->block_id()]);
90  }
91}
92
93
94void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction(
95    HInstruction* instr,
96    BitVector* live) {
97  switch (instr->opcode()) {
98    case HValue::kEnvironmentMarker: {
99      HEnvironmentMarker* marker = HEnvironmentMarker::cast(instr);
100      int index = marker->index();
101      if (!live->Contains(index)) {
102        marker->SetFlag(HValue::kEndsLiveRange);
103      } else {
104        marker->ClearFlag(HValue::kEndsLiveRange);
105      }
106      if (!went_live_since_last_simulate_.Contains(index)) {
107        marker->set_next_simulate(last_simulate_);
108      }
109      if (marker->kind() == HEnvironmentMarker::LOOKUP) {
110        live->Add(index);
111      } else {
112        ASSERT(marker->kind() == HEnvironmentMarker::BIND);
113        live->Remove(index);
114        went_live_since_last_simulate_.Add(index);
115      }
116      if (collect_markers_) {
117        // Populate |markers_| list during the first pass.
118        markers_.Add(marker, zone());
119      }
120      break;
121    }
122    case HValue::kLeaveInlined:
123      // No environment values are live at the end of an inlined section.
124      live->Clear();
125      last_simulate_ = NULL;
126
127      // The following ASSERTs guard the assumption used in case
128      // kEnterInlined below:
129      ASSERT(instr->next()->IsSimulate());
130      ASSERT(instr->next()->next()->IsGoto());
131
132      break;
133    case HValue::kEnterInlined: {
134      // Those environment values are live that are live at any return
135      // target block. Here we make use of the fact that the end of an
136      // inline sequence always looks like this: HLeaveInlined, HSimulate,
137      // HGoto (to return_target block), with no environment lookups in
138      // between (see ASSERTs above).
139      HEnterInlined* enter = HEnterInlined::cast(instr);
140      live->Clear();
141      for (int i = 0; i < enter->return_targets()->length(); ++i) {
142        int return_id = enter->return_targets()->at(i)->block_id();
143        live->Union(*live_at_block_start_[return_id]);
144      }
145      last_simulate_ = NULL;
146      break;
147    }
148    case HValue::kSimulate:
149      last_simulate_ = HSimulate::cast(instr);
150      went_live_since_last_simulate_.Clear();
151      break;
152    default:
153      break;
154  }
155}
156
157
158void HEnvironmentLivenessAnalysisPhase::Run() {
159  ASSERT(maximum_environment_size_ > 0);
160
161  // Main iteration. Compute liveness of environment slots, and store it
162  // for each block until it doesn't change any more. For efficiency, visit
163  // blocks in reverse order and walk backwards through each block. We
164  // need several iterations to propagate liveness through nested loops.
165  BitVector live(maximum_environment_size_, zone());
166  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        continue;
174      }
175      worklist.Remove(block_id);
176      last_simulate_ = NULL;
177
178      HBasicBlock* block = graph()->blocks()->at(block_id);
179      UpdateLivenessAtBlockEnd(block, &live);
180
181      for (HInstruction* instr = block->end(); instr != NULL;
182           instr = instr->previous()) {
183        UpdateLivenessAtInstruction(instr, &live);
184      }
185
186      // Reached the start of the block, do necessary bookkeeping:
187      // store computed information for this block and add predecessors
188      // to the work list as necessary.
189      first_simulate_.Set(block_id, last_simulate_);
190      first_simulate_invalid_for_index_[block_id]->CopyFrom(
191          went_live_since_last_simulate_);
192      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    // Only collect bind/lookup instructions during the first pass.
202    collect_markers_ = false;
203  }
204
205  // Analysis finished. Zap dead environment slots.
206  for (int i = 0; i < markers_.length(); ++i) {
207    ZapEnvironmentSlotsForInstruction(markers_[i]);
208  }
209  for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
210    HBasicBlock* block = graph()->blocks()->at(block_id);
211    UpdateLivenessAtBlockEnd(block, &live);
212    ZapEnvironmentSlotsInSuccessors(block, &live);
213  }
214
215  // Finally, remove the HEnvironment{Bind,Lookup} markers.
216  for (int i = 0; i < markers_.length(); ++i) {
217    markers_[i]->DeleteAndReplaceWith(NULL);
218  }
219}
220
221
222#ifdef DEBUG
223bool HEnvironmentLivenessAnalysisPhase::VerifyClosures(
224    Handle<JSFunction> a, Handle<JSFunction> b) {
225  Heap::RelocationLock for_heap_access(isolate()->heap());
226  AllowHandleDereference for_verification;
227  return a.is_identical_to(b);
228}
229#endif
230
231} }  // namespace v8::internal
232