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); NonLiveFrameStateSlotReplacer(StateValuesCache * state_values_cache,Node * replacement,size_t local_count,bool has_accumulator,Zone * local_zone)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. MarkPermanentlyLive(int var)37 void MarkPermanentlyLive(int var) { permanently_live_.Add(var); } 38 39 private: 40 Node* ClearNonLiveStateValues(Node* frame_state, BitVector* liveness); 41 state_values_cache()42 StateValuesCache* state_values_cache() { return state_values_cache_; } local_zone()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 zone()67 Zone* zone() { return zone_; } 68 69 void Print(std::ostream& os); 70 local_count()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 Lookup(int var)92 void Lookup(int var) { entries_.push_back(Entry(Entry::kLookup, var)); } Bind(int var)93 void Bind(int var) { entries_.push_back(Entry(Entry::kBind, var)); } LookupAccumulator()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 } BindAccumulator()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 Checkpoint(Node * node)105 void Checkpoint(Node* node) { entries_.push_back(Entry(node)); } AddPredecessor(LivenessAnalyzerBlock * b)106 void AddPredecessor(LivenessAnalyzerBlock* b) { predecessors_.push_back(b); } GetPredecessor()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 kind()117 Kind kind() const { return kind_; } node()118 Node* node() const { 119 DCHECK(kind() == kCheckpoint); 120 return node_; 121 } var()122 int var() const { 123 DCHECK(kind() != kCheckpoint); 124 return var_; 125 } 126 Entry(Node * node)127 explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {} Entry(Kind kind,int var)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 SetQueued()143 void SetQueued() { queued_ = true; } IsQueued()144 bool IsQueued() { return queued_; } 145 pred_begin()146 ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_begin() { 147 return predecessors_.begin(); 148 } pred_end()149 ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_end() { 150 return predecessors_.end(); 151 } 152 id()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