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 LivenessAnalyzerBlock* GetPredecessor() { 89 DCHECK(predecessors_.size() == 1); 90 return predecessors_[0]; 91 } 92 93 private: 94 class Entry { 95 public: 96 enum Kind { kBind, kLookup, kCheckpoint }; 97 98 Kind kind() const { return kind_; } 99 Node* node() const { 100 DCHECK(kind() == kCheckpoint); 101 return node_; 102 } 103 int var() const { 104 DCHECK(kind() != kCheckpoint); 105 return var_; 106 } 107 108 explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {} 109 Entry(Kind kind, int var) : kind_(kind), var_(var), node_(nullptr) { 110 DCHECK(kind != kCheckpoint); 111 } 112 113 private: 114 Kind kind_; 115 int var_; 116 Node* node_; 117 }; 118 119 LivenessAnalyzerBlock(size_t id, size_t local_count, Zone* zone); 120 void Process(BitVector* result, NonLiveFrameStateSlotReplacer* relaxer); 121 bool UpdateLive(BitVector* working_area); 122 123 void SetQueued() { queued_ = true; } 124 bool IsQueued() { return queued_; } 125 126 ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_begin() { 127 return predecessors_.begin(); 128 } 129 ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_end() { 130 return predecessors_.end(); 131 } 132 133 size_t id() { return id_; } 134 void Print(std::ostream& os); 135 136 ZoneDeque<Entry> entries_; 137 ZoneDeque<LivenessAnalyzerBlock*> predecessors_; 138 139 BitVector live_; 140 bool queued_; 141 142 size_t id_; 143 }; 144 145 146 } // namespace compiler 147 } // namespace internal 148 } // namespace v8 149 150 #endif // V8_COMPILER_AST_GRAPH_BUILDER_H_ 151