Line data    Source code

       1             : // Copyright 2015 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             : #ifndef V8_COMPILER_LIVENESS_ANAYZER_H_
       6             : #define V8_COMPILER_LIVENESS_ANAYZER_H_
       7             : 
       8             : #include "src/bit-vector.h"
       9             : #include "src/compiler/node.h"
      10             : #include "src/globals.h"
      11             : #include "src/zone/zone-containers.h"
      12             : 
      13             : namespace v8 {
      14             : namespace internal {
      15             : namespace compiler {
      16             : 
      17             : class LivenessAnalyzerBlock;
      18             : class Node;
      19             : class StateValuesCache;
      20             : 
      21             : class NonLiveFrameStateSlotReplacer {
      22             :  public:
      23             :   void ClearNonLiveFrameStateSlots(Node* frame_state, BitVector* liveness);
      24             :   NonLiveFrameStateSlotReplacer(StateValuesCache* state_values_cache,
      25             :                                 Node* replacement, size_t local_count,
      26             :                                 bool has_accumulator, Zone* local_zone)
      27             :       : replacement_node_(replacement),
      28             :         state_values_cache_(state_values_cache),
      29             :         local_zone_(local_zone),
      30             :         permanently_live_(
      31             :             static_cast<int>(local_count) + (has_accumulator ? 1 : 0),
      32             :             local_zone),
      33             :         inputs_buffer_(local_zone),
      34         876 :         has_accumulator_(has_accumulator) {}
      35             : 
      36             :   // TODO(leszeks): Not used by bytecode, remove once AST graph builder is gone.
      37           4 :   void MarkPermanentlyLive(int var) { permanently_live_.Add(var); }
      38             : 
      39             :  private:
      40             :   Node* ClearNonLiveStateValues(Node* frame_state, BitVector* liveness);
      41             : 
      42             :   StateValuesCache* state_values_cache() { return state_values_cache_; }
      43             :   Zone* local_zone() { return local_zone_; }
      44             : 
      45             :   // Node that replaces dead values.
      46             :   Node* replacement_node_;
      47             :   // Reference to state values cache so that we can create state values
      48             :   // nodes.
      49             :   StateValuesCache* state_values_cache_;
      50             : 
      51             :   Zone* local_zone_;
      52             :   BitVector permanently_live_;
      53             :   NodeVector inputs_buffer_;
      54             : 
      55             :   bool has_accumulator_;
      56             : };
      57             : 
      58             : class V8_EXPORT_PRIVATE LivenessAnalyzer {
      59             :  public:
      60             :   LivenessAnalyzer(size_t local_count, bool has_accumulator, Zone* zone);
      61             : 
      62             :   LivenessAnalyzerBlock* NewBlock();
      63             :   LivenessAnalyzerBlock* NewBlock(LivenessAnalyzerBlock* predecessor);
      64             : 
      65             :   void Run(NonLiveFrameStateSlotReplacer* relaxer);
      66             : 
      67             :   Zone* zone() { return zone_; }
      68             : 
      69             :   void Print(std::ostream& os);
      70             : 
      71             :   size_t local_count() { return local_count_; }
      72             : 
      73             :  private:
      74             :   void Queue(LivenessAnalyzerBlock* block);
      75             : 
      76             :   Zone* zone_;
      77             :   ZoneDeque<LivenessAnalyzerBlock*> blocks_;
      78             :   size_t local_count_;
      79             : 
      80             :   // TODO(leszeks): Always true for bytecode, remove once AST graph builder is
      81             :   // gone.
      82             :   bool has_accumulator_;
      83             : 
      84             :   ZoneQueue<LivenessAnalyzerBlock*> queue_;
      85             : };
      86             : 
      87             : 
      88             : class LivenessAnalyzerBlock {
      89             :  public:
      90             :   friend class LivenessAnalyzer;
      91             : 
      92         248 :   void Lookup(int var) { entries_.push_back(Entry(Entry::kLookup, var)); }
      93         308 :   void Bind(int var) { entries_.push_back(Entry(Entry::kBind, var)); }
      94             :   void LookupAccumulator() {
      95             :     DCHECK(has_accumulator_);
      96             :     // The last entry is the accumulator entry.
      97             :     entries_.push_back(Entry(Entry::kLookup, live_.length() - 1));
      98             :   }
      99             :   void BindAccumulator() {
     100             :     DCHECK(has_accumulator_);
     101             :     // The last entry is the accumulator entry.
     102             :     entries_.push_back(Entry(Entry::kBind, live_.length() - 1));
     103             :   }
     104             : 
     105        3232 :   void Checkpoint(Node* node) { entries_.push_back(Entry(node)); }
     106         597 :   void AddPredecessor(LivenessAnalyzerBlock* b) { predecessors_.push_back(b); }
     107           0 :   LivenessAnalyzerBlock* GetPredecessor() {
     108             :     DCHECK(predecessors_.size() == 1);
     109           0 :     return predecessors_[0];
     110             :   }
     111             : 
     112             :  private:
     113             :   class Entry {
     114             :    public:
     115             :     enum Kind { kBind, kLookup, kCheckpoint };
     116             : 
     117             :     Kind kind() const { return kind_; }
     118             :     Node* node() const {
     119             :       DCHECK(kind() == kCheckpoint);
     120             :       return node_;
     121             :     }
     122             :     int var() const {
     123             :       DCHECK(kind() != kCheckpoint);
     124             :       return var_;
     125             :     }
     126             : 
     127        1616 :     explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {}
     128         278 :     Entry(Kind kind, int var) : kind_(kind), var_(var), node_(nullptr) {
     129             :       DCHECK(kind != kCheckpoint);
     130             :     }
     131             : 
     132             :    private:
     133             :     Kind kind_;
     134             :     int var_;
     135             :     Node* node_;
     136             :   };
     137             : 
     138             :   LivenessAnalyzerBlock(size_t id, size_t local_count, bool has_accumulator,
     139             :                         Zone* zone);
     140             :   void Process(BitVector* result, NonLiveFrameStateSlotReplacer* relaxer);
     141             :   bool UpdateLive(BitVector* working_area);
     142             : 
     143         480 :   void SetQueued() { queued_ = true; }
     144             :   bool IsQueued() { return queued_; }
     145             : 
     146             :   ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_begin() {
     147             :     return predecessors_.begin();
     148             :   }
     149             :   ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_end() {
     150             :     return predecessors_.end();
     151             :   }
     152             : 
     153             :   size_t id() { return id_; }
     154             :   void Print(std::ostream& os);
     155             : 
     156             :   ZoneDeque<Entry> entries_;
     157             :   ZoneDeque<LivenessAnalyzerBlock*> predecessors_;
     158             : 
     159             :   BitVector live_;
     160             :   bool queued_;
     161             :   bool has_accumulator_;
     162             : 
     163             :   size_t id_;
     164             : };
     165             : 
     166             : 
     167             : }  // namespace compiler
     168             : }  // namespace internal
     169             : }  // namespace v8
     170             : 
     171             : #endif  // V8_COMPILER_AST_GRAPH_BUILDER_H_