1014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Copyright 2015 the V8 project authors. All rights reserved. 2014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Use of this source code is governed by a BSD-style license that can be 3014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// found in the LICENSE file. 4014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 5014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#ifndef V8_COMPILER_LIVENESS_ANAYZER_H_ 6014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#define V8_COMPILER_LIVENESS_ANAYZER_H_ 7014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 8014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/bit-vector.h" 9014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/compiler/node.h" 10c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch#include "src/globals.h" 11f3b273f5e6ffd2f6ba1c18a27a17db41dfb113c3Ben Murdoch#include "src/zone/zone-containers.h" 12014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 13014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochnamespace v8 { 14014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochnamespace internal { 15014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochnamespace compiler { 16014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 17014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass LivenessAnalyzerBlock; 18014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass Node; 19014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass StateValuesCache; 20014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 21014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass NonLiveFrameStateSlotReplacer { 22014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 23014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void ClearNonLiveFrameStateSlots(Node* frame_state, BitVector* liveness); 24014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch NonLiveFrameStateSlotReplacer(StateValuesCache* state_values_cache, 25014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* replacement, size_t local_count, 26c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch bool has_accumulator, Zone* local_zone) 27014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : replacement_node_(replacement), 28014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch state_values_cache_(state_values_cache), 29014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch local_zone_(local_zone), 30c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch permanently_live_( 31c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch static_cast<int>(local_count) + (has_accumulator ? 1 : 0), 32c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch local_zone), 33c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch inputs_buffer_(local_zone), 34c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch has_accumulator_(has_accumulator) {} 35014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 36c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch // TODO(leszeks): Not used by bytecode, remove once AST graph builder is gone. 37014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void MarkPermanentlyLive(int var) { permanently_live_.Add(var); } 38014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 39014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 40014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* ClearNonLiveStateValues(Node* frame_state, BitVector* liveness); 41014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 42014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch StateValuesCache* state_values_cache() { return state_values_cache_; } 43014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* local_zone() { return local_zone_; } 44014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 45014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Node that replaces dead values. 46014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* replacement_node_; 47014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Reference to state values cache so that we can create state values 48014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // nodes. 49014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch StateValuesCache* state_values_cache_; 50014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 51014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* local_zone_; 52014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BitVector permanently_live_; 53014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch NodeVector inputs_buffer_; 54014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 55c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch bool has_accumulator_; 56c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch}; 57014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 58c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdochclass V8_EXPORT_PRIVATE LivenessAnalyzer { 59014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 60c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch LivenessAnalyzer(size_t local_count, bool has_accumulator, Zone* zone); 61014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 62014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LivenessAnalyzerBlock* NewBlock(); 63014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch LivenessAnalyzerBlock* NewBlock(LivenessAnalyzerBlock* predecessor); 64014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 65014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Run(NonLiveFrameStateSlotReplacer* relaxer); 66014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 67014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* zone() { return zone_; } 68014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 69014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Print(std::ostream& os); 70014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 71014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t local_count() { return local_count_; } 72014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 73014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 74014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Queue(LivenessAnalyzerBlock* block); 75014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 76014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* zone_; 77014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneDeque<LivenessAnalyzerBlock*> blocks_; 78014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t local_count_; 79014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 80c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch // TODO(leszeks): Always true for bytecode, remove once AST graph builder is 81c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch // gone. 82c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch bool has_accumulator_; 83c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch 84014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneQueue<LivenessAnalyzerBlock*> queue_; 85014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 86014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 87014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 88014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass LivenessAnalyzerBlock { 89014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 90014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch friend class LivenessAnalyzer; 91014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 92014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Lookup(int var) { entries_.push_back(Entry(Entry::kLookup, var)); } 93014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Bind(int var) { entries_.push_back(Entry(Entry::kBind, var)); } 94c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch void LookupAccumulator() { 95c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch DCHECK(has_accumulator_); 96c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch // The last entry is the accumulator entry. 97c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch entries_.push_back(Entry(Entry::kLookup, live_.length() - 1)); 98c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch } 99c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch void BindAccumulator() { 100c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch DCHECK(has_accumulator_); 101c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch // The last entry is the accumulator entry. 102c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch entries_.push_back(Entry(Entry::kBind, live_.length() - 1)); 103c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch } 104c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch 105014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Checkpoint(Node* node) { entries_.push_back(Entry(node)); } 106014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void AddPredecessor(LivenessAnalyzerBlock* b) { predecessors_.push_back(b); } 107109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch LivenessAnalyzerBlock* GetPredecessor() { 108109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch DCHECK(predecessors_.size() == 1); 109109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch return predecessors_[0]; 110109988c7ccb6f3fd1a58574fa3dfb88beaef6632Ben Murdoch } 111014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 112014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 113014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch class Entry { 114014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 115014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch enum Kind { kBind, kLookup, kCheckpoint }; 116014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 117014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Kind kind() const { return kind_; } 118014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* node() const { 119014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(kind() == kCheckpoint); 120014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return node_; 121014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 122014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int var() const { 123014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(kind() != kCheckpoint); 124014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return var_; 125014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 126014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 127014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch explicit Entry(Node* node) : kind_(kCheckpoint), var_(-1), node_(node) {} 128014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Entry(Kind kind, int var) : kind_(kind), var_(var), node_(nullptr) { 129014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch DCHECK(kind != kCheckpoint); 130014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 131014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 132014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 133014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Kind kind_; 134014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch int var_; 135014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* node_; 136014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch }; 137014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 138c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch LivenessAnalyzerBlock(size_t id, size_t local_count, bool has_accumulator, 139c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch Zone* zone); 140014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Process(BitVector* result, NonLiveFrameStateSlotReplacer* relaxer); 141014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool UpdateLive(BitVector* working_area); 142014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 143014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void SetQueued() { queued_ = true; } 144014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool IsQueued() { return queued_; } 145014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 146014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_begin() { 147014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return predecessors_.begin(); 148014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 149014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneDeque<LivenessAnalyzerBlock*>::const_iterator pred_end() { 150014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return predecessors_.end(); 151014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 152014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 153014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t id() { return id_; } 154014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Print(std::ostream& os); 155014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 156014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneDeque<Entry> entries_; 157014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneDeque<LivenessAnalyzerBlock*> predecessors_; 158014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 159014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BitVector live_; 160014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool queued_; 161c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch bool has_accumulator_; 162014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 163014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t id_; 164014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 165014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 166014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 167014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace compiler 168014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace internal 169014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace v8 170014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 171014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#endif // V8_COMPILER_AST_GRAPH_BUILDER_H_ 172