LCOV - code coverage report
Current view: top level - src/compiler - liveness-analyzer.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 51 83 61.4 %
Date: 2017-04-26 Functions: 8 12 66.7 %

          Line data    Source code
       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        2512 : 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        5024 :       queue_(zone) {}
      23             : 
      24           0 : void LivenessAnalyzer::Print(std::ostream& os) {
      25           0 :   for (auto block : blocks_) {
      26           0 :     block->Print(os);
      27             :     os << std::endl;
      28             :   }
      29           0 : }
      30             : 
      31             : 
      32        1920 : LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock() {
      33             :   LivenessAnalyzerBlock* result =
      34             :       new (zone()->New(sizeof(LivenessAnalyzerBlock))) LivenessAnalyzerBlock(
      35         960 :           blocks_.size(), local_count_, has_accumulator_, zone());
      36         960 :   blocks_.push_back(result);
      37         960 :   return result;
      38             : }
      39             : 
      40             : 
      41         517 : LivenessAnalyzerBlock* LivenessAnalyzer::NewBlock(
      42             :     LivenessAnalyzerBlock* predecessor) {
      43         517 :   LivenessAnalyzerBlock* result = NewBlock();
      44             :   result->AddPredecessor(predecessor);
      45         517 :   return result;
      46             : }
      47             : 
      48             : 
      49           0 : void LivenessAnalyzer::Queue(LivenessAnalyzerBlock* block) {
      50         484 :   if (!block->IsQueued()) {
      51             :     block->SetQueued();
      52             :     queue_.push(block);
      53             :   }
      54           0 : }
      55             : 
      56             : 
      57         443 : void LivenessAnalyzer::Run(NonLiveFrameStateSlotReplacer* replacer) {
      58         443 :   if (local_count_ == 0 && !has_accumulator_) {
      59             :     // No variables => nothing to do.
      60         342 :     return;
      61             :   }
      62             : 
      63             :   // Put all blocks into the queue.
      64             :   DCHECK(queue_.empty());
      65         865 :   for (auto block : blocks_) {
      66             :     Queue(block);
      67             :   }
      68             : 
      69             :   // Compute the fix-point.
      70             :   BitVector working_area(
      71         101 :       static_cast<int>(local_count_) + (has_accumulator_ ? 1 : 0), zone_);
      72         682 :   while (!queue_.empty()) {
      73         480 :     LivenessAnalyzerBlock* block = queue_.front();
      74             :     queue_.pop();
      75         480 :     block->Process(&working_area, nullptr);
      76             : 
      77         883 :     for (auto i = block->pred_begin(); i != block->pred_end(); i++) {
      78         806 :       if ((*i)->UpdateLive(&working_area)) {
      79             :         Queue(*i);
      80             :       }
      81             :     }
      82             :   }
      83             : 
      84             :   // Update the frame states according to the liveness.
      85         865 :   for (auto block : blocks_) {
      86         382 :     block->Process(&working_area, replacer);
      87             :   }
      88             : }
      89             : 
      90         960 : 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         960 :       id_(id) {}
      98             : 
      99        2424 : void LivenessAnalyzerBlock::Process(BitVector* result,
     100             :                                     NonLiveFrameStateSlotReplacer* replacer) {
     101         862 :   queued_ = false;
     102             : 
     103             :   // Copy the bitvector to the target bit vector.
     104         862 :   result->CopyFrom(live_);
     105             : 
     106        5632 :   for (auto entry : base::Reversed(entries_)) {
     107        1954 :     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        1254 :         if (replacer != nullptr) {
     116         544 :           replacer->ClearNonLiveFrameStateSlots(entry.node(), result);
     117             :         }
     118             :         break;
     119             :     }
     120             :   }
     121         862 : }
     122             : 
     123             : 
     124           0 : bool LivenessAnalyzerBlock::UpdateLive(BitVector* working_area) {
     125         403 :   return live_.UnionIsChanged(*working_area);
     126             : }
     127             : 
     128             : 
     129         544 : void NonLiveFrameStateSlotReplacer::ClearNonLiveFrameStateSlots(
     130        1178 :     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         544 :   int count = liveness->length() - (has_accumulator_ ? 1 : 0);
     137             :   DCHECK_EQ(count, static_cast<int>(StateValuesAccess(locals_state).size()));
     138         754 :   for (int i = 0; i < count; i++) {
     139        1064 :     if (!liveness->Contains(i) && !permanently_live_.Contains(i)) {
     140         424 :       Node* new_values = ClearNonLiveStateValues(locals_state, liveness);
     141         424 :       frame_state->ReplaceInput(1, new_values);
     142         424 :       break;
     143             :     }
     144             :   }
     145             : 
     146         544 :   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           0 :     int index = liveness->length() - 1;
     151           0 :     if (!liveness->Contains(index) && !permanently_live_.Contains(index)) {
     152             :       Node* new_value =
     153           0 :           state_values_cache()->GetNodeForValues(&replacement_node_, 1);
     154           0 :       frame_state->ReplaceInput(2, new_value);
     155             :     }
     156             :   }
     157         544 : }
     158             : 
     159             : 
     160         424 : Node* NonLiveFrameStateSlotReplacer::ClearNonLiveStateValues(
     161        1094 :     Node* values, BitVector* liveness) {
     162             :   DCHECK(inputs_buffer_.empty());
     163             : 
     164             :   int var = 0;
     165        1764 :   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        1224 :     bool live = liveness->Contains(var) || permanently_live_.Contains(var);
     172        1094 :     inputs_buffer_.push_back(live ? value_node : replacement_node_);
     173             : 
     174         670 :     var++;
     175             :   }
     176             : 
     177             :   Node* result = state_values_cache()->GetNodeForValues(
     178             :       inputs_buffer_.empty() ? nullptr : &(inputs_buffer_.front()),
     179         848 :       inputs_buffer_.size());
     180             :   inputs_buffer_.clear();
     181         424 :   return result;
     182             : }
     183             : 
     184             : 
     185           0 : void LivenessAnalyzerBlock::Print(std::ostream& os) {
     186           0 :   os << "Block " << id();
     187             :   bool first = true;
     188           0 :   for (LivenessAnalyzerBlock* pred : predecessors_) {
     189           0 :     if (!first) {
     190           0 :       os << ", ";
     191             :     } else {
     192           0 :       os << "; predecessors: ";
     193             :       first = false;
     194             :     }
     195             :     os << pred->id();
     196             :   }
     197             :   os << std::endl;
     198             : 
     199           0 :   for (auto entry : entries_) {
     200           0 :     os << "    ";
     201           0 :     switch (entry.kind()) {
     202             :       case Entry::kLookup:
     203           0 :         if (has_accumulator_ && entry.var() == live_.length() - 1) {
     204           0 :           os << "- Lookup accumulator" << std::endl;
     205             :         } else {
     206           0 :           os << "- Lookup " << entry.var() << std::endl;
     207             :         }
     208             :         break;
     209             :       case Entry::kBind:
     210           0 :         if (has_accumulator_ && entry.var() == live_.length() - 1) {
     211           0 :           os << "- Bind accumulator" << std::endl;
     212             :         } else {
     213           0 :           os << "- Bind " << entry.var() << std::endl;
     214             :         }
     215             :         break;
     216             :       case Entry::kCheckpoint:
     217           0 :         os << "- Checkpoint " << entry.node()->id() << std::endl;
     218             :         break;
     219             :     }
     220             :   }
     221             : 
     222           0 :   if (live_.length() > 0) {
     223           0 :     os << "    Live set: ";
     224           0 :     for (int i = 0; i < live_.length(); i++) {
     225           0 :       os << (live_.Contains(i) ? "L" : ".");
     226             :     }
     227             :     os << std::endl;
     228             :   }
     229           0 : }
     230             : 
     231             : }  // namespace compiler
     232             : }  // namespace internal
     233             : }  // namespace v8

Generated by: LCOV version 1.10