1 // Copyright 2022 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_CODEGEN_REGLIST_BASE_H_
6 #define V8_CODEGEN_REGLIST_BASE_H_
7
8 #include <cstdint>
9 #include <initializer_list>
10
11 #include "src/base/bits.h"
12 #include "src/base/iterator.h"
13 #include "src/base/template-utils.h"
14
15 namespace v8 {
16 namespace internal {
17
18 class Register;
19
20 template <typename RegisterT>
21 class RegListBase {
22 using num_registers_sized_storage_t = typename std::conditional<
23 RegisterT::kNumRegisters <= 16, uint16_t,
24 typename std::conditional<RegisterT::kNumRegisters <= 32, uint32_t,
25 uint64_t>::type>::type;
26 STATIC_ASSERT(RegisterT::kNumRegisters <= 64);
27
28 public:
29 class Iterator;
30 class ReverseIterator;
31
32 #ifdef V8_TARGET_ARCH_ARM64
33 // On ARM64 the sp register has the special value 63 (kSPRegInternalCode)
34 using storage_t = typename std::conditional<
35 std::is_same<RegisterT, v8::internal::Register>::value, uint64_t,
36 num_registers_sized_storage_t>::type;
37 #else
38 using storage_t = num_registers_sized_storage_t;
39 #endif
40
41 constexpr RegListBase() = default;
RegListBase(std::initializer_list<RegisterT> regs)42 constexpr RegListBase(std::initializer_list<RegisterT> regs) {
43 for (RegisterT reg : regs) {
44 set(reg);
45 }
46 }
47
set(RegisterT reg)48 constexpr void set(RegisterT reg) {
49 if (!reg.is_valid()) return;
50 regs_ |= storage_t{1} << reg.code();
51 }
52
clear(RegisterT reg)53 constexpr void clear(RegisterT reg) {
54 if (!reg.is_valid()) return;
55 regs_ &= ~(storage_t{1} << reg.code());
56 }
57
has(RegisterT reg) const58 constexpr bool has(RegisterT reg) const {
59 if (!reg.is_valid()) return false;
60 return (regs_ & (storage_t{1} << reg.code())) != 0;
61 }
62
clear(RegListBase other)63 constexpr void clear(RegListBase other) { regs_ &= ~other.regs_; }
64
is_empty() const65 constexpr bool is_empty() const { return regs_ == 0; }
66
Count() const67 constexpr unsigned Count() const {
68 return base::bits::CountPopulation(regs_);
69 }
70
operator &(const RegListBase other) const71 constexpr RegListBase operator&(const RegListBase other) const {
72 return RegListBase(regs_ & other.regs_);
73 }
74
operator |(const RegListBase other) const75 constexpr RegListBase operator|(const RegListBase other) const {
76 return RegListBase(regs_ | other.regs_);
77 }
78
operator ^(const RegListBase other) const79 constexpr RegListBase operator^(const RegListBase other) const {
80 return RegListBase(regs_ ^ other.regs_);
81 }
82
operator -(const RegListBase other) const83 constexpr RegListBase operator-(const RegListBase other) const {
84 return RegListBase(regs_ & ~other.regs_);
85 }
86
operator |(const RegisterT reg) const87 constexpr RegListBase operator|(const RegisterT reg) const {
88 return *this | RegListBase{reg};
89 }
90
operator -(const RegisterT reg) const91 constexpr RegListBase operator-(const RegisterT reg) const {
92 return *this - RegListBase{reg};
93 }
94
operator &=(const RegListBase other)95 constexpr RegListBase& operator&=(const RegListBase other) {
96 regs_ &= other.regs_;
97 return *this;
98 }
99
operator |=(const RegListBase other)100 constexpr RegListBase& operator|=(const RegListBase other) {
101 regs_ |= other.regs_;
102 return *this;
103 }
104
operator ==(const RegListBase other) const105 constexpr bool operator==(const RegListBase other) const {
106 return regs_ == other.regs_;
107 }
operator !=(const RegListBase other) const108 constexpr bool operator!=(const RegListBase other) const {
109 return regs_ != other.regs_;
110 }
111
first() const112 constexpr RegisterT first() const {
113 DCHECK(!is_empty());
114 int first_code = base::bits::CountTrailingZerosNonZero(regs_);
115 return RegisterT::from_code(first_code);
116 }
117
last() const118 constexpr RegisterT last() const {
119 DCHECK(!is_empty());
120 int last_code =
121 8 * sizeof(regs_) - 1 - base::bits::CountLeadingZeros(regs_);
122 return RegisterT::from_code(last_code);
123 }
124
PopFirst()125 constexpr RegisterT PopFirst() {
126 RegisterT reg = first();
127 clear(reg);
128 return reg;
129 }
130
bits() const131 constexpr storage_t bits() const { return regs_; }
132
133 inline Iterator begin() const;
134 inline Iterator end() const;
135
136 inline ReverseIterator rbegin() const;
137 inline ReverseIterator rend() const;
138
FromBits(storage_t bits)139 static RegListBase FromBits(storage_t bits) { return RegListBase(bits); }
140
141 template <storage_t bits>
FromBits()142 static constexpr RegListBase FromBits() {
143 return RegListBase{bits};
144 }
145
146 private:
147 // Unchecked constructor. Only use for valid bits.
RegListBase(storage_t bits)148 explicit constexpr RegListBase(storage_t bits) : regs_(bits) {}
149
150 storage_t regs_ = 0;
151 };
152
153 template <typename RegisterT>
154 class RegListBase<RegisterT>::Iterator
155 : public base::iterator<std::forward_iterator_tag, RegisterT> {
156 public:
operator *()157 RegisterT operator*() { return remaining_.first(); }
operator ++()158 Iterator& operator++() {
159 remaining_.clear(remaining_.first());
160 return *this;
161 }
operator ==(Iterator other)162 bool operator==(Iterator other) { return remaining_ == other.remaining_; }
operator !=(Iterator other)163 bool operator!=(Iterator other) { return remaining_ != other.remaining_; }
164
165 private:
Iterator(RegListBase<RegisterT> remaining)166 explicit Iterator(RegListBase<RegisterT> remaining) : remaining_(remaining) {}
167 friend class RegListBase;
168
169 RegListBase<RegisterT> remaining_;
170 };
171
172 template <typename RegisterT>
173 class RegListBase<RegisterT>::ReverseIterator
174 : public base::iterator<std::forward_iterator_tag, RegisterT> {
175 public:
operator *()176 RegisterT operator*() { return remaining_.last(); }
operator ++()177 ReverseIterator& operator++() {
178 remaining_.clear(remaining_.last());
179 return *this;
180 }
operator ==(ReverseIterator other)181 bool operator==(ReverseIterator other) {
182 return remaining_ == other.remaining_;
183 }
operator !=(ReverseIterator other)184 bool operator!=(ReverseIterator other) {
185 return remaining_ != other.remaining_;
186 }
187
188 private:
ReverseIterator(RegListBase<RegisterT> remaining)189 explicit ReverseIterator(RegListBase<RegisterT> remaining)
190 : remaining_(remaining) {}
191 friend class RegListBase;
192
193 RegListBase<RegisterT> remaining_;
194 };
195
196 template <typename RegisterT>
begin() const197 typename RegListBase<RegisterT>::Iterator RegListBase<RegisterT>::begin()
198 const {
199 return Iterator{*this};
200 }
201 template <typename RegisterT>
end() const202 typename RegListBase<RegisterT>::Iterator RegListBase<RegisterT>::end() const {
203 return Iterator{RegListBase<RegisterT>{}};
204 }
205
206 template <typename RegisterT>
207 typename RegListBase<RegisterT>::ReverseIterator
rbegin() const208 RegListBase<RegisterT>::rbegin() const {
209 return ReverseIterator{*this};
210 }
211 template <typename RegisterT>
rend() const212 typename RegListBase<RegisterT>::ReverseIterator RegListBase<RegisterT>::rend()
213 const {
214 return ReverseIterator{RegListBase<RegisterT>{}};
215 }
216
217 template <typename RegisterT>
operator <<(std::ostream& os, RegListBase<RegisterT> reglist)218 inline std::ostream& operator<<(std::ostream& os,
219 RegListBase<RegisterT> reglist) {
220 os << "{";
221 for (bool first = true; !reglist.is_empty(); first = false) {
222 RegisterT reg = reglist.first();
223 reglist.clear(reg);
224 os << (first ? "" : ", ") << reg;
225 }
226 return os << "}";
227 }
228
229 } // namespace internal
230 } // namespace v8
231
232 #endif // V8_CODEGEN_REGLIST_BASE_H_
233