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
15namespace v8 {
16namespace internal {
17
18class Register;
19
20template <typename RegisterT>
21class 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;
42  constexpr RegListBase(std::initializer_list<RegisterT> regs) {
43    for (RegisterT reg : regs) {
44      set(reg);
45    }
46  }
47
48  constexpr void set(RegisterT reg) {
49    if (!reg.is_valid()) return;
50    regs_ |= storage_t{1} << reg.code();
51  }
52
53  constexpr void clear(RegisterT reg) {
54    if (!reg.is_valid()) return;
55    regs_ &= ~(storage_t{1} << reg.code());
56  }
57
58  constexpr bool has(RegisterT reg) const {
59    if (!reg.is_valid()) return false;
60    return (regs_ & (storage_t{1} << reg.code())) != 0;
61  }
62
63  constexpr void clear(RegListBase other) { regs_ &= ~other.regs_; }
64
65  constexpr bool is_empty() const { return regs_ == 0; }
66
67  constexpr unsigned Count() const {
68    return base::bits::CountPopulation(regs_);
69  }
70
71  constexpr RegListBase operator&(const RegListBase other) const {
72    return RegListBase(regs_ & other.regs_);
73  }
74
75  constexpr RegListBase operator|(const RegListBase other) const {
76    return RegListBase(regs_ | other.regs_);
77  }
78
79  constexpr RegListBase operator^(const RegListBase other) const {
80    return RegListBase(regs_ ^ other.regs_);
81  }
82
83  constexpr RegListBase operator-(const RegListBase other) const {
84    return RegListBase(regs_ & ~other.regs_);
85  }
86
87  constexpr RegListBase operator|(const RegisterT reg) const {
88    return *this | RegListBase{reg};
89  }
90
91  constexpr RegListBase operator-(const RegisterT reg) const {
92    return *this - RegListBase{reg};
93  }
94
95  constexpr RegListBase& operator&=(const RegListBase other) {
96    regs_ &= other.regs_;
97    return *this;
98  }
99
100  constexpr RegListBase& operator|=(const RegListBase other) {
101    regs_ |= other.regs_;
102    return *this;
103  }
104
105  constexpr bool operator==(const RegListBase other) const {
106    return regs_ == other.regs_;
107  }
108  constexpr bool operator!=(const RegListBase other) const {
109    return regs_ != other.regs_;
110  }
111
112  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
118  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
125  constexpr RegisterT PopFirst() {
126    RegisterT reg = first();
127    clear(reg);
128    return reg;
129  }
130
131  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
139  static RegListBase FromBits(storage_t bits) { return RegListBase(bits); }
140
141  template <storage_t bits>
142  static constexpr RegListBase FromBits() {
143    return RegListBase{bits};
144  }
145
146 private:
147  // Unchecked constructor. Only use for valid bits.
148  explicit constexpr RegListBase(storage_t bits) : regs_(bits) {}
149
150  storage_t regs_ = 0;
151};
152
153template <typename RegisterT>
154class RegListBase<RegisterT>::Iterator
155    : public base::iterator<std::forward_iterator_tag, RegisterT> {
156 public:
157  RegisterT operator*() { return remaining_.first(); }
158  Iterator& operator++() {
159    remaining_.clear(remaining_.first());
160    return *this;
161  }
162  bool operator==(Iterator other) { return remaining_ == other.remaining_; }
163  bool operator!=(Iterator other) { return remaining_ != other.remaining_; }
164
165 private:
166  explicit Iterator(RegListBase<RegisterT> remaining) : remaining_(remaining) {}
167  friend class RegListBase;
168
169  RegListBase<RegisterT> remaining_;
170};
171
172template <typename RegisterT>
173class RegListBase<RegisterT>::ReverseIterator
174    : public base::iterator<std::forward_iterator_tag, RegisterT> {
175 public:
176  RegisterT operator*() { return remaining_.last(); }
177  ReverseIterator& operator++() {
178    remaining_.clear(remaining_.last());
179    return *this;
180  }
181  bool operator==(ReverseIterator other) {
182    return remaining_ == other.remaining_;
183  }
184  bool operator!=(ReverseIterator other) {
185    return remaining_ != other.remaining_;
186  }
187
188 private:
189  explicit ReverseIterator(RegListBase<RegisterT> remaining)
190      : remaining_(remaining) {}
191  friend class RegListBase;
192
193  RegListBase<RegisterT> remaining_;
194};
195
196template <typename RegisterT>
197typename RegListBase<RegisterT>::Iterator RegListBase<RegisterT>::begin()
198    const {
199  return Iterator{*this};
200}
201template <typename RegisterT>
202typename RegListBase<RegisterT>::Iterator RegListBase<RegisterT>::end() const {
203  return Iterator{RegListBase<RegisterT>{}};
204}
205
206template <typename RegisterT>
207typename RegListBase<RegisterT>::ReverseIterator
208RegListBase<RegisterT>::rbegin() const {
209  return ReverseIterator{*this};
210}
211template <typename RegisterT>
212typename RegListBase<RegisterT>::ReverseIterator RegListBase<RegisterT>::rend()
213    const {
214  return ReverseIterator{RegListBase<RegisterT>{}};
215}
216
217template <typename RegisterT>
218inline 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