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/zone-containers.h"
     11 
     12 namespace v8 {
     13 namespace internal {
     14 namespace compiler {
     15 
     16 class LivenessAnalyzerBlock;
     17 class Node;
     18 class StateValuesCache;
     19 
     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                                 Zone* local_zone)
     27       : replacement_node_(replacement),
     28         state_values_cache_(state_values_cache),
     29         local_zone_(local_zone),
     30         permanently_live_(local_count == 0 ? 1 : static_cast<int>(local_count),
     31                           local_zone),
     32         inputs_buffer_(local_zone) {}
     33 
     34   void MarkPermanentlyLive(int var) { permanently_live_.Add(var); }
     35 
     36  private:
     37   Node* ClearNonLiveStateValues(Node* frame_state, BitVector* liveness);
     38 
     39   StateValuesCache* state_values_cache() { return state_values_cache_; }
     40   Zone* local_zone() { return local_zone_; }
     41 
     42   // Node that replaces dead values.
     43   Node* replacement_node_;
     44   // Reference to state values cache so that we can create state values
     45   // nodes.
     46   StateValuesCache* state_values_cache_;
     47 
     48   Zone* local_zone_;
     49   BitVector permanently_live_;
     50   NodeVector inputs_buffer_;
     51 };
     52 
     53 
     54 class LivenessAnalyzer {
     55  public:
     56   LivenessAnalyzer(size_t local_count, Zone* zone);
     57 
     58   LivenessAnalyzerBlock* NewBlock();
     59   LivenessAnalyzerBlock* NewBlock(LivenessAnalyzerBlock* predecessor);
     60 
     61   void Run(NonLiveFrameStateSlotReplacer* relaxer);
     62 
     63   Zone* zone() { return zone_; }
     64 
     65   void Print(std::ostream& os);
     66 
     67   size_t local_count() { return local_count_; }
     68 
     69  private:
     70   void Queue(LivenessAnalyzerBlock* block);
     71 
     72   Zone* zone_;
     73   ZoneDeque<LivenessAnalyzerBlock*> blocks_;
     74   size_t local_count_;
     75 
     76   ZoneQueue<LivenessAnalyzerBlock*> queue_;
     77 };
     78 
     79 
     80 class LivenessAnalyzerBlock {
     81  public:
     82   friend class LivenessAnalyzer;
     83 
     84   void Lookup(int var) { entries_.push_back(Entry(Entry::kLookup, var)); }
     85   void Bind(int var) { entries_.push_back(Entry(Entry::kBind, var)); }
     86   void Checkpoint(Node* node) { entries_.push_back(Entry(node)); }
     87   void AddPredecessor(LivenessAnalyzerBlock* b) { predecessors_.push_back(b); }
     88 
     89  private:
     90   class Entry {
     91    public:
     92     enum Kind { kBind, kLookup, kCheckpoint };
     93 
     94     Kind kind() const { return kind_; }
     95     Node* node() const {
     96       DCHECK(kind() == kCheckpoint);
     97       return node_;
     98     }
     99     int var() const {
    100       DCHECK(kind() != kCheckpoint);
    101       return var_;
    102     }
    103 
    104     explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {}
    105     Entry(Kind kind, int var) : kind_(kind), var_(var), node_(nullptr) {
    106       DCHECK(kind != kCheckpoint);
    107     }
    108 
    109    private:
    110     Kind kind_;
    111     int var_;
    112     Node* node_;
    113   };
    114 
    115   LivenessAnalyzerBlock(size_t id, size_t local_count, Zone* zone);
    116   void Process(BitVector* result, NonLiveFrameStateSlotReplacer* relaxer);
    117   bool UpdateLive(BitVector* working_area);
    118 
    119   void SetQueued() { queued_ = true; }
    120   bool IsQueued() { return queued_; }
    121 
    122   ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_begin() {
    123     return predecessors_.begin();
    124   }
    125   ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_end() {
    126     return predecessors_.end();
    127   }
    128 
    129   size_t id() { return id_; }
    130   void Print(std::ostream& os);
    131 
    132   ZoneDeque<Entry> entries_;
    133   ZoneDeque<LivenessAnalyzerBlock*> predecessors_;
    134 
    135   BitVector live_;
    136   bool queued_;
    137 
    138   size_t id_;
    139 };
    140 
    141 
    142 }  // namespace compiler
    143 }  // namespace internal
    144 }  // namespace v8
    145 
    146 #endif  // V8_COMPILER_AST_GRAPH_BUILDER_H_
    147