src/v8/src/hydrogen-environment-liveness.cc

   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
  32 namespace v8 {
  33 namespace internal {
  34
  35
  36 HEnvironmentLivenessAnalysisPhase::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
  59 void 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
  70 void 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
  95 void 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
 106 void 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
 117 void 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
 181 void 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->last(); 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