1 // Copyright 2016 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_BYTECODE_LIVENESS_MAP_H_ 6 #define V8_COMPILER_BYTECODE_LIVENESS_MAP_H_ 7 8 #include <string> 9 10 #include "src/utils/bit-vector.h" 11 #include "src/zone/zone.h" 12 13 namespace v8 { 14 namespace internal { 15 16 class Zone; 17 18 namespace compiler { 19 20 class BytecodeLivenessState : public ZoneObject { 21 public: 22 class Iterator { 23 public: 24 int operator*() const { 25 // Subtract one to compensate for the accumulator at the start of the 26 // bit vector. 27 return *it_ - 1; 28 } 29 30 void operator++() { return ++it_; } 31 32 bool operator!=(const Iterator& other) const { return it_ != other.it_; } 33 34 private: 35 static constexpr struct StartTag { 36 } kStartTag = {}; 37 static constexpr struct EndTag { 38 } kEndTag = {}; Iterator(const BytecodeLivenessState & liveness,StartTag)39 explicit Iterator(const BytecodeLivenessState& liveness, StartTag) 40 : it_(liveness.bit_vector_.begin()) { 41 // If we're not at the end, and the current value is the accumulator, skip 42 // over it. 43 if (it_ != liveness.bit_vector_.end() && *it_ == 0) { 44 ++it_; 45 } 46 } Iterator(const BytecodeLivenessState & liveness,EndTag)47 explicit Iterator(const BytecodeLivenessState& liveness, EndTag) 48 : it_(liveness.bit_vector_.end()) {} 49 50 BitVector::Iterator it_; 51 friend class BytecodeLivenessState; 52 }; 53 BytecodeLivenessState(int register_count,Zone * zone)54 BytecodeLivenessState(int register_count, Zone* zone) 55 : bit_vector_(register_count + 1, zone) {} 56 BytecodeLivenessState(const BytecodeLivenessState&) = delete; 57 BytecodeLivenessState& operator=(const BytecodeLivenessState&) = delete; 58 BytecodeLivenessState(const BytecodeLivenessState & other,Zone * zone)59 BytecodeLivenessState(const BytecodeLivenessState& other, Zone* zone) 60 : bit_vector_(other.bit_vector_, zone) {} 61 RegisterIsLive(int index)62 bool RegisterIsLive(int index) const { 63 DCHECK_GE(index, 0); 64 DCHECK_LT(index, bit_vector_.length() - 1); 65 return bit_vector_.Contains(index + 1); 66 } 67 AccumulatorIsLive()68 bool AccumulatorIsLive() const { return bit_vector_.Contains(0); } 69 Equals(const BytecodeLivenessState & other)70 bool Equals(const BytecodeLivenessState& other) const { 71 return bit_vector_.Equals(other.bit_vector_); 72 } 73 MarkRegisterLive(int index)74 void MarkRegisterLive(int index) { 75 DCHECK_GE(index, 0); 76 DCHECK_LT(index, bit_vector_.length() - 1); 77 bit_vector_.Add(index + 1); 78 } 79 MarkRegisterDead(int index)80 void MarkRegisterDead(int index) { 81 DCHECK_GE(index, 0); 82 DCHECK_LT(index, bit_vector_.length() - 1); 83 bit_vector_.Remove(index + 1); 84 } 85 MarkAccumulatorLive()86 void MarkAccumulatorLive() { bit_vector_.Add(0); } 87 MarkAccumulatorDead()88 void MarkAccumulatorDead() { bit_vector_.Remove(0); } 89 MarkAllLive()90 void MarkAllLive() { bit_vector_.AddAll(); } 91 Union(const BytecodeLivenessState & other)92 void Union(const BytecodeLivenessState& other) { 93 bit_vector_.Union(other.bit_vector_); 94 } 95 UnionIsChanged(const BytecodeLivenessState & other)96 bool UnionIsChanged(const BytecodeLivenessState& other) { 97 return bit_vector_.UnionIsChanged(other.bit_vector_); 98 } 99 CopyFrom(const BytecodeLivenessState & other)100 void CopyFrom(const BytecodeLivenessState& other) { 101 bit_vector_.CopyFrom(other.bit_vector_); 102 } 103 register_count()104 int register_count() const { return bit_vector_.length() - 1; } 105 106 // Number of live values, including the accumulator. live_value_count()107 int live_value_count() const { return bit_vector_.Count(); } 108 begin()109 Iterator begin() const { return Iterator(*this, Iterator::kStartTag); } 110 end()111 Iterator end() const { return Iterator(*this, Iterator::kEndTag); } 112 113 private: 114 BitVector bit_vector_; 115 }; 116 117 struct BytecodeLiveness { 118 BytecodeLivenessState* in; 119 BytecodeLivenessState* out; 120 }; 121 122 class V8_EXPORT_PRIVATE BytecodeLivenessMap { 123 public: BytecodeLivenessMap(int bytecode_size,Zone * zone)124 BytecodeLivenessMap(int bytecode_size, Zone* zone) 125 : liveness_(zone->NewArray<BytecodeLiveness>(bytecode_size)) 126 #ifdef DEBUG 127 , 128 size_(bytecode_size) 129 #endif 130 { 131 } 132 InsertNewLiveness(int offset)133 BytecodeLiveness& InsertNewLiveness(int offset) { 134 DCHECK_GE(offset, 0); 135 DCHECK_LT(offset, size_); 136 #ifdef DEBUG 137 // Null out the in/out liveness, so that later DCHECKs know whether these 138 // have been correctly initialised or not. That code does initialise them 139 // unconditionally though, so we can skip the nulling out in release. 140 liveness_[offset].in = nullptr; 141 liveness_[offset].out = nullptr; 142 #endif 143 return liveness_[offset]; 144 } 145 GetLiveness(int offset)146 BytecodeLiveness& GetLiveness(int offset) { 147 DCHECK_GE(offset, 0); 148 DCHECK_LT(offset, size_); 149 return liveness_[offset]; 150 } GetLiveness(int offset)151 const BytecodeLiveness& GetLiveness(int offset) const { 152 DCHECK_GE(offset, 0); 153 DCHECK_LT(offset, size_); 154 return liveness_[offset]; 155 } 156 GetInLiveness(int offset)157 BytecodeLivenessState* GetInLiveness(int offset) { 158 return GetLiveness(offset).in; 159 } GetInLiveness(int offset)160 const BytecodeLivenessState* GetInLiveness(int offset) const { 161 return GetLiveness(offset).in; 162 } 163 GetOutLiveness(int offset)164 BytecodeLivenessState* GetOutLiveness(int offset) { 165 return GetLiveness(offset).out; 166 } GetOutLiveness(int offset)167 const BytecodeLivenessState* GetOutLiveness(int offset) const { 168 return GetLiveness(offset).out; 169 } 170 171 private: 172 BytecodeLiveness* liveness_; 173 #ifdef DEBUG 174 size_t size_; 175 #endif 176 }; 177 178 V8_EXPORT_PRIVATE std::string ToString(const BytecodeLivenessState& liveness); 179 180 } // namespace compiler 181 } // namespace internal 182 } // namespace v8 183 184 #endif // V8_COMPILER_BYTECODE_LIVENESS_MAP_H_ 185