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); } 88 89 private: 90 class Entry { 91 public: 92 enum Kind { kBind, kLookup, kCheckpoint }; 93 kind()94 Kind kind() const { return kind_; } node()95 Node* node() const { 96 DCHECK(kind() == kCheckpoint); 97 return node_; 98 } var()99 int var() const { 100 DCHECK(kind() != kCheckpoint); 101 return var_; 102 } 103 Entry(Node * node)104 explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {} Entry(Kind kind,int var)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 SetQueued()119 void SetQueued() { queued_ = true; } IsQueued()120 bool IsQueued() { return queued_; } 121 pred_begin()122 ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_begin() { 123 return predecessors_.begin(); 124 } pred_end()125 ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_end() { 126 return predecessors_.end(); 127 } 128 id()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