deps/v8/src/compiler/liveness-analyzer.cc

   1 // Copyright 2014 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 #include "src/compiler/liveness-analyzer.h"
   6 #include "src/compiler/js-graph.h"
   7 #include "src/compiler/node.h"
   8 #include "src/compiler/node-matchers.h"
   9 #include "src/compiler/state-values-utils.h"
  10
  11 namespace v8 {
  12 namespace internal {
  13 namespace compiler {
  14
  15
  16 LivenessAnalyzer::LivenessAnalyzer(size_t local_count, Zone* zone)
  17     : zone_(zone), blocks_(zone), local_count_(local_count), queue_(zone) {}
  18
  19
  20 void LivenessAnalyzer::Print(std::ostream& os) {
  21   for (auto block : blocks_) {
  22     block->Print(os);
  23     os << std::endl;
  24   }
  25 }
  26
  27
  28 LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock() {
  29   LivenessAnalyzerBlock* result =
  30       new (zone()->New(sizeof(LivenessAnalyzerBlock)))
  31           LivenessAnalyzerBlock(blocks_.size(), local_count_, zone());
  32   blocks_.push_back(result);
  33   return result;
  34 }
  35
  36
  37 LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock(
  38     LivenessAnalyzerBlock* predecessor) {
  39   LivenessAnalyzerBlock* result = NewBlock();
  40   result->AddPredecessor(predecessor);
  41   return result;
  42 }
  43
  44
  45 void LivenessAnalyzer::Queue(LivenessAnalyzerBlock* block) {
  46   if (!block->IsQueued()) {
  47     block->SetQueued();
  48     queue_.push(block);
  49   }
  50 }
  51
  52
  53 void LivenessAnalyzer::Run(NonLiveFrameStateSlotReplacer* replacer) {
  54   if (local_count_ == 0) {
  55     // No local variables => nothing to do.
  56     return;
  57   }
  58
  59   // Put all blocks into the queue.
  60   DCHECK(queue_.empty());
  61   for (auto block : blocks_) {
  62     Queue(block);
  63   }
  64
  65   // Compute the fix-point.
  66   BitVector working_area(static_cast<int>(local_count_), zone_);
  67   while (!queue_.empty()) {
  68     LivenessAnalyzerBlock* block = queue_.front();
  69     queue_.pop();
  70     block->Process(&working_area, nullptr);
  71
  72     for (auto i = block->pred_begin(); i != block->pred_end(); i++) {
  73       if ((*i)->UpdateLive(&working_area)) {
  74         Queue(*i);
  75       }
  76     }
  77   }
  78
  79   // Update the frame states according to the liveness.
  80   for (auto block : blocks_) {
  81     block->Process(&working_area, replacer);
  82   }
  83 }
  84
  85 LivenessAnalyzerBlock::LivenessAnalyzerBlock(size_t id, size_t local_count,
  86                                              Zone* zone)
  87     : entries_(zone),
  88       predecessors_(zone),
  89       live_(local_count == 0 ? 1 : static_cast<int>(local_count), zone),
  90       queued_(false),
  91       id_(id) {}
  92
  93 void LivenessAnalyzerBlock::Process(BitVector* result,
  94                                     NonLiveFrameStateSlotReplacer* replacer) {
  95   queued_ = false;
  96
  97   // Copy the bitvector to the target bit vector.
  98   result->CopyFrom(live_);
  99
 100   for (auto i = entries_.rbegin(); i != entries_.rend(); i++) {
 101     auto entry = *i;
 102     switch (entry.kind()) {
 103       case Entry::kLookup:
 104         result->Add(entry.var());
 105         break;
 106       case Entry::kBind:
 107         result->Remove(entry.var());
 108         break;
 109       case Entry::kCheckpoint:
 110         if (replacer != nullptr) {
 111           replacer->ClearNonLiveFrameStateSlots(entry.node(), result);
 112         }
 113         break;
 114     }
 115   }
 116 }
 117
 118
 119 bool LivenessAnalyzerBlock::UpdateLive(BitVector* working_area) {
 120   return live_.UnionIsChanged(*working_area);
 121 }
 122
 123
 124 void NonLiveFrameStateSlotReplacer::ClearNonLiveFrameStateSlots(
 125     Node* frame_state, BitVector* liveness) {
 126   DCHECK_EQ(frame_state->opcode(), IrOpcode::kFrameState);
 127   Node* locals_state = frame_state->InputAt(1);
 128   DCHECK_EQ(locals_state->opcode(), IrOpcode::kStateValues);
 129   int count = static_cast<int>(StateValuesAccess(locals_state).size());
 130   DCHECK_EQ(count == 0 ? 1 : count, liveness->length());
 131   for (int i = 0; i < count; i++) {
 132     bool live = liveness->Contains(i) || permanently_live_.Contains(i);
 133     if (!live || locals_state->InputAt(i) != replacement_node_) {
 134       Node* new_values = ClearNonLiveStateValues(locals_state, liveness);
 135       frame_state->ReplaceInput(1, new_values);
 136       break;
 137     }
 138   }
 139 }
 140
 141
 142 Node* NonLiveFrameStateSlotReplacer::ClearNonLiveStateValues(
 143     Node* values, BitVector* liveness) {
 144   DCHECK(inputs_buffer_.empty());
 145   for (StateValuesAccess::TypedNode node : StateValuesAccess(values)) {
 146     // Index of the next variable is its furure index in the inputs buffer,
 147     // i.e., the buffer's size.
 148     int var = static_cast<int>(inputs_buffer_.size());
 149     bool live = liveness->Contains(var) || permanently_live_.Contains(var);
 150     inputs_buffer_.push_back(live ? node.node : replacement_node_);
 151   }
 152   Node* result = state_values_cache()->GetNodeForValues(
 153       inputs_buffer_.empty() ? nullptr : &(inputs_buffer_.front()),
 154       inputs_buffer_.size());
 155   inputs_buffer_.clear();
 156   return result;
 157 }
 158
 159
 160 void LivenessAnalyzerBlock::Print(std::ostream& os) {
 161   os << "Block " << id();
 162   bool first = true;
 163   for (LivenessAnalyzerBlock* pred : predecessors_) {
 164     if (!first) {
 165       os << ", ";
 166     } else {
 167       os << "; predecessors: ";
 168       first = false;
 169     }
 170     os << pred->id();
 171   }
 172   os << std::endl;
 173
 174   for (auto entry : entries_) {
 175     os << "    ";
 176     switch (entry.kind()) {
 177       case Entry::kLookup:
 178         os << "- Lookup " << entry.var() << std::endl;
 179         break;
 180       case Entry::kBind:
 181         os << "- Bind " << entry.var() << std::endl;
 182         break;
 183       case Entry::kCheckpoint:
 184         os << "- Checkpoint " << entry.node()->id() << std::endl;
 185         break;
 186     }
 187   }
 188
 189   if (live_.length() > 0) {
 190     os << "    Live set: ";
 191     for (int i = 0; i < live_.length(); i++) {
 192       os << (live_.Contains(i) ? "L" : ".");
 193     }
 194     os << std::endl;
 195   }
 196 }
 197
 198 }  // namespace compiler
 199 }  // namespace internal
 200 }  // namespace v8