Home | History | Annotate | Download | only in compiler 
      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         has_accumulator_(has_accumulator) {}
     35 
     36   // TODO(leszeks): Not used by bytecode, remove once AST graph builder is gone.
     37   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   void Lookup(int var) { entries_.push_back(Entry(Entry::kLookup, var)); }
     93   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   void Checkpoint(Node* node) { entries_.push_back(Entry(node)); }
    106   void AddPredecessor(LivenessAnalyzerBlock* b) { predecessors_.push_back(b); }
    107   LivenessAnalyzerBlock* GetPredecessor() {
    108     DCHECK(predecessors_.size() == 1);
    109     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     explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {}
    128     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   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_
    172