1// Copyright 2013 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6//     * Redistributions of source code must retain the above copyright
7//       notice, this list of conditions and the following disclaimer.
8//     * Redistributions in binary form must reproduce the above
9//       copyright notice, this list of conditions and the following
10//       disclaimer in the documentation and/or other materials provided
11//       with the distribution.
12//     * Neither the name of Google Inc. nor the names of its
13//       contributors may be used to endorse or promote products derived
14//       from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28
29#include "hydrogen-environment-liveness.h"
30
31
32namespace v8 {
33namespace internal {
34
35
36HEnvironmentLivenessAnalysisPhase::HEnvironmentLivenessAnalysisPhase(
37    HGraph* graph)
38    : HPhase("H_Environment liveness analysis", graph),
39      block_count_(graph->blocks()->length()),
40      maximum_environment_size_(graph->maximum_environment_size()),
41      live_at_block_start_(block_count_, zone()),
42      first_simulate_(block_count_, zone()),
43      first_simulate_invalid_for_index_(block_count_, zone()),
44      markers_(maximum_environment_size_, zone()),
45      collect_markers_(true),
46      last_simulate_(NULL),
47      went_live_since_last_simulate_(maximum_environment_size_, zone()) {
48  ASSERT(maximum_environment_size_ > 0);
49  for (int i = 0; i < block_count_; ++i) {
50    live_at_block_start_.Add(
51        new(zone()) BitVector(maximum_environment_size_, zone()), zone());
52    first_simulate_.Add(NULL, zone());
53    first_simulate_invalid_for_index_.Add(
54        new(zone()) BitVector(maximum_environment_size_, zone()), zone());
55  }
56}
57
58
59void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlot(
60    int index, HSimulate* simulate) {
61  int operand_index = simulate->ToOperandIndex(index);
62  if (operand_index == -1) {
63    simulate->AddAssignedValue(index, graph()->GetConstantUndefined());
64  } else {
65    simulate->SetOperandAt(operand_index, graph()->GetConstantUndefined());
66  }
67}
68
69
70void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsInSuccessors(
71    HBasicBlock* block, BitVector* live) {
72  // When a value is live in successor A but dead in B, we must
73  // explicitly zap it in B.
74  for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
75    HBasicBlock* successor = it.Current();
76    int successor_id = successor->block_id();
77    BitVector* live_in_successor = live_at_block_start_[successor_id];
78    if (live_in_successor->Equals(*live)) continue;
79    for (int i = 0; i < live->length(); ++i) {
80      if (!live->Contains(i)) continue;
81      if (live_in_successor->Contains(i)) continue;
82      if (first_simulate_invalid_for_index_.at(successor_id)->Contains(i)) {
83        continue;
84      }
85      HSimulate* simulate = first_simulate_.at(successor_id);
86      if (simulate == NULL) continue;
87      ASSERT(simulate->closure().is_identical_to(
88                 block->last_environment()->closure()));
89      ZapEnvironmentSlot(i, simulate);
90    }
91  }
92}
93
94
95void HEnvironmentLivenessAnalysisPhase::ZapEnvironmentSlotsForInstruction(
96    HEnvironmentMarker* marker) {
97  if (!marker->CheckFlag(HValue::kEndsLiveRange)) return;
98  HSimulate* simulate = marker->next_simulate();
99  if (simulate != NULL) {
100    ASSERT(simulate->closure().is_identical_to(marker->closure()));
101    ZapEnvironmentSlot(marker->index(), simulate);
102  }
103}
104
105
106void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtBlockEnd(
107    HBasicBlock* block,
108    BitVector* live) {
109  // Liveness at the end of each block: union of liveness in successors.
110  live->Clear();
111  for (HSuccessorIterator it(block->end()); !it.Done(); it.Advance()) {
112    live->Union(*live_at_block_start_[it.Current()->block_id()]);
113  }
114}
115
116
117void HEnvironmentLivenessAnalysisPhase::UpdateLivenessAtInstruction(
118    HInstruction* instr,
119    BitVector* live) {
120  switch (instr->opcode()) {
121    case HValue::kEnvironmentMarker: {
122      HEnvironmentMarker* marker = HEnvironmentMarker::cast(instr);
123      int index = marker->index();
124      if (!live->Contains(index)) {
125        marker->SetFlag(HValue::kEndsLiveRange);
126      } else {
127        marker->ClearFlag(HValue::kEndsLiveRange);
128      }
129      if (!went_live_since_last_simulate_.Contains(index)) {
130        marker->set_next_simulate(last_simulate_);
131      }
132      if (marker->kind() == HEnvironmentMarker::LOOKUP) {
133        live->Add(index);
134      } else {
135        ASSERT(marker->kind() == HEnvironmentMarker::BIND);
136        live->Remove(index);
137        went_live_since_last_simulate_.Add(index);
138      }
139      if (collect_markers_) {
140        // Populate |markers_| list during the first pass.
141        markers_.Add(marker, zone());
142      }
143      break;
144    }
145    case HValue::kLeaveInlined:
146      // No environment values are live at the end of an inlined section.
147      live->Clear();
148      last_simulate_ = NULL;
149
150      // The following ASSERTs guard the assumption used in case
151      // kEnterInlined below:
152      ASSERT(instr->next()->IsSimulate());
153      ASSERT(instr->next()->next()->IsGoto());
154
155      break;
156    case HValue::kEnterInlined: {
157      // Those environment values are live that are live at any return
158      // target block. Here we make use of the fact that the end of an
159      // inline sequence always looks like this: HLeaveInlined, HSimulate,
160      // HGoto (to return_target block), with no environment lookups in
161      // between (see ASSERTs above).
162      HEnterInlined* enter = HEnterInlined::cast(instr);
163      live->Clear();
164      for (int i = 0; i < enter->return_targets()->length(); ++i) {
165        int return_id = enter->return_targets()->at(i)->block_id();
166        live->Union(*live_at_block_start_[return_id]);
167      }
168      last_simulate_ = NULL;
169      break;
170    }
171    case HValue::kSimulate:
172      last_simulate_ = HSimulate::cast(instr);
173      went_live_since_last_simulate_.Clear();
174      break;
175    default:
176      break;
177  }
178}
179
180
181void HEnvironmentLivenessAnalysisPhase::Run() {
182  ASSERT(maximum_environment_size_ > 0);
183
184  // Main iteration. Compute liveness of environment slots, and store it
185  // for each block until it doesn't change any more. For efficiency, visit
186  // blocks in reverse order and walk backwards through each block. We
187  // need several iterations to propagate liveness through nested loops.
188  BitVector live(maximum_environment_size_, zone());
189  BitVector worklist(block_count_, zone());
190  for (int i = 0; i < block_count_; ++i) {
191    worklist.Add(i);
192  }
193  while (!worklist.IsEmpty()) {
194    for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
195      if (!worklist.Contains(block_id)) {
196        continue;
197      }
198      worklist.Remove(block_id);
199      last_simulate_ = NULL;
200
201      HBasicBlock* block = graph()->blocks()->at(block_id);
202      UpdateLivenessAtBlockEnd(block, &live);
203
204      for (HInstruction* instr = block->end(); instr != NULL;
205           instr = instr->previous()) {
206        UpdateLivenessAtInstruction(instr, &live);
207      }
208
209      // Reached the start of the block, do necessary bookkeeping:
210      // store computed information for this block and add predecessors
211      // to the work list as necessary.
212      first_simulate_.Set(block_id, last_simulate_);
213      first_simulate_invalid_for_index_[block_id]->CopyFrom(
214          went_live_since_last_simulate_);
215      if (live_at_block_start_[block_id]->UnionIsChanged(live)) {
216        for (int i = 0; i < block->predecessors()->length(); ++i) {
217          worklist.Add(block->predecessors()->at(i)->block_id());
218        }
219        if (block->IsInlineReturnTarget()) {
220          worklist.Add(block->inlined_entry_block()->block_id());
221        }
222      }
223    }
224    // Only collect bind/lookup instructions during the first pass.
225    collect_markers_ = false;
226  }
227
228  // Analysis finished. Zap dead environment slots.
229  for (int i = 0; i < markers_.length(); ++i) {
230    ZapEnvironmentSlotsForInstruction(markers_[i]);
231  }
232  for (int block_id = block_count_ - 1; block_id >= 0; --block_id) {
233    HBasicBlock* block = graph()->blocks()->at(block_id);
234    UpdateLivenessAtBlockEnd(block, &live);
235    ZapEnvironmentSlotsInSuccessors(block, &live);
236  }
237
238  // Finally, remove the HEnvironment{Bind,Lookup} markers.
239  for (int i = 0; i < markers_.length(); ++i) {
240    markers_[i]->DeleteAndReplaceWith(NULL);
241  }
242}
243
244} }  // namespace v8::internal
245