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 
     17 LivenessAnalyzer::LivenessAnalyzer(size_t local_count, Zone* zone)
     18     : zone_(zone), blocks_(zone), local_count_(local_count), queue_(zone) {}
     19 
     20 
     21 void LivenessAnalyzer::Print(std::ostream& os) {
     22   for (auto block : blocks_) {
     23     block->Print(os);
     24     os << std::endl;
     25   }
     26 }
     27 
     28 
     29 LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock() {
     30   LivenessAnalyzerBlock* result =
     31       new (zone()->New(sizeof(LivenessAnalyzerBlock)))
     32           LivenessAnalyzerBlock(blocks_.size(), local_count_, zone());
     33   blocks_.push_back(result);
     34   return result;
     35 }
     36 
     37 
     38 LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock(
     39     LivenessAnalyzerBlock* predecessor) {
     40   LivenessAnalyzerBlock* result = NewBlock();
     41   result->AddPredecessor(predecessor);
     42   return result;
     43 }
     44 
     45 
     46 void LivenessAnalyzer::Queue(LivenessAnalyzerBlock* block) {
     47   if (!block->IsQueued()) {
     48     block->SetQueued();
     49     queue_.push(block);
     50   }
     51 }
     52 
     53 
     54 void LivenessAnalyzer::Run(NonLiveFrameStateSlotReplacer* replacer) {
     55   if (local_count_ == 0) {
     56     // No local variables => nothing to do.
     57     return;
     58   }
     59 
     60   // Put all blocks into the queue.
     61   DCHECK(queue_.empty());
     62   for (auto block : blocks_) {
     63     Queue(block);
     64   }
     65 
     66   // Compute the fix-point.
     67   BitVector working_area(static_cast<int>(local_count_), zone_);
     68   while (!queue_.empty()) {
     69     LivenessAnalyzerBlock* block = queue_.front();
     70     queue_.pop();
     71     block->Process(&working_area, nullptr);
     72 
     73     for (auto i = block->pred_begin(); i != block->pred_end(); i++) {
     74       if ((*i)->UpdateLive(&working_area)) {
     75         Queue(*i);
     76       }
     77     }
     78   }
     79 
     80   // Update the frame states according to the liveness.
     81   for (auto block : blocks_) {
     82     block->Process(&working_area, replacer);
     83   }
     84 }
     85 
     86 LivenessAnalyzerBlock::LivenessAnalyzerBlock(size_t id, size_t local_count,
     87                                              Zone* zone)
     88     : entries_(zone),
     89       predecessors_(zone),
     90       live_(local_count == 0 ? 1 : static_cast<int>(local_count), zone),
     91       queued_(false),
     92       id_(id) {}
     93 
     94 void LivenessAnalyzerBlock::Process(BitVector* result,
     95                                     NonLiveFrameStateSlotReplacer* replacer) {
     96   queued_ = false;
     97 
     98   // Copy the bitvector to the target bit vector.
     99   result->CopyFrom(live_);
    100 
    101   for (auto entry : base::Reversed(entries_)) {
    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
    201