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