deps/v8/src/compiler/liveness-analyzer.h

   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_