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); NonLiveFrameStateSlotReplacer(StateValuesCache * state_values_cache,Node * replacement,size_t local_count,Zone * local_zone)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 MarkPermanentlyLive(int var)34 void MarkPermanentlyLive(int var) { permanently_live_.Add(var); } 35 36 private: 37 Node* ClearNonLiveStateValues(Node* frame_state, BitVector* liveness); 38 state_values_cache()39 StateValuesCache* state_values_cache() { return state_values_cache_; } local_zone()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 zone()63 Zone* zone() { return zone_; } 64 65 void Print(std::ostream& os); 66 local_count()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 Lookup(int var)84 void Lookup(int var) { entries_.push_back(Entry(Entry::kLookup, var)); } Bind(int var)85 void Bind(int var) { entries_.push_back(Entry(Entry::kBind, var)); } Checkpoint(Node * node)86 void Checkpoint(Node* node) { entries_.push_back(Entry(node)); } AddPredecessor(LivenessAnalyzerBlock * b)87 void AddPredecessor(LivenessAnalyzerBlock* b) { predecessors_.push_back(b); } GetPredecessor()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 kind()98 Kind kind() const { return kind_; } node()99 Node* node() const { 100 DCHECK(kind() == kCheckpoint); 101 return node_; 102 } var()103 int var() const { 104 DCHECK(kind() != kCheckpoint); 105 return var_; 106 } 107 Entry(Node * node)108 explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {} Entry(Kind kind,int var)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 SetQueued()123 void SetQueued() { queued_ = true; } IsQueued()124 bool IsQueued() { return queued_; } 125 pred_begin()126 ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_begin() { 127 return predecessors_.begin(); 128 } pred_end()129 ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_end() { 130 return predecessors_.end(); 131 } 132 id()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