LLVM  10.0.0svn
PackedVector.h
Go to the documentation of this file.
1 //===- llvm/ADT/PackedVector.h - Packed values vector -----------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the PackedVector class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_PACKEDVECTOR_H
14 #define LLVM_ADT_PACKEDVECTOR_H
15 
16 #include "llvm/ADT/BitVector.h"
17 #include <cassert>
18 #include <limits>
19 
20 namespace llvm {
21 
22 template <typename T, unsigned BitNum, typename BitVectorTy, bool isSigned>
24 
25 // This won't be necessary if we can specialize members without specializing
26 // the parent template.
27 template <typename T, unsigned BitNum, typename BitVectorTy>
28 class PackedVectorBase<T, BitNum, BitVectorTy, false> {
29 protected:
30  static T getValue(const BitVectorTy &Bits, unsigned Idx) {
31  T val = T();
32  for (unsigned i = 0; i != BitNum; ++i)
33  val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
34  return val;
35  }
36 
37  static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
38  assert((val >> BitNum) == 0 && "value is too big");
39  for (unsigned i = 0; i != BitNum; ++i)
40  Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
41  }
42 };
43 
44 template <typename T, unsigned BitNum, typename BitVectorTy>
45 class PackedVectorBase<T, BitNum, BitVectorTy, true> {
46 protected:
47  static T getValue(const BitVectorTy &Bits, unsigned Idx) {
48  T val = T();
49  for (unsigned i = 0; i != BitNum-1; ++i)
50  val = T(val | ((Bits[(Idx << (BitNum-1)) + i] ? 1UL : 0UL) << i));
51  if (Bits[(Idx << (BitNum-1)) + BitNum-1])
52  val = ~val;
53  return val;
54  }
55 
56  static void setValue(BitVectorTy &Bits, unsigned Idx, T val) {
57  if (val < 0) {
58  val = ~val;
59  Bits.set((Idx << (BitNum-1)) + BitNum-1);
60  }
61  assert((val >> (BitNum-1)) == 0 && "value is too big");
62  for (unsigned i = 0; i != BitNum-1; ++i)
63  Bits[(Idx << (BitNum-1)) + i] = val & (T(1) << i);
64  }
65 };
66 
67 /// Store a vector of values using a specific number of bits for each
68 /// value. Both signed and unsigned types can be used, e.g
69 /// @code
70 /// PackedVector<signed, 2> vec;
71 /// @endcode
72 /// will create a vector accepting values -2, -1, 0, 1. Any other value will hit
73 /// an assertion.
74 template <typename T, unsigned BitNum, typename BitVectorTy = BitVector>
75 class PackedVector : public PackedVectorBase<T, BitNum, BitVectorTy,
76  std::numeric_limits<T>::is_signed> {
77  BitVectorTy Bits;
78  using base = PackedVectorBase<T, BitNum, BitVectorTy,
79  std::numeric_limits<T>::is_signed>;
80 
81 public:
82  class reference {
83  PackedVector &Vec;
84  const unsigned Idx;
85 
86  public:
87  reference() = delete;
88  reference(PackedVector &vec, unsigned idx) : Vec(vec), Idx(idx) {}
89 
90  reference &operator=(T val) {
91  Vec.setValue(Vec.Bits, Idx, val);
92  return *this;
93  }
94 
95  operator T() const {
96  return Vec.getValue(Vec.Bits, Idx);
97  }
98  };
99 
100  PackedVector() = default;
101  explicit PackedVector(unsigned size) : Bits(size << (BitNum-1)) {}
102 
103  bool empty() const { return Bits.empty(); }
104 
105  unsigned size() const { return Bits.size() >> (BitNum - 1); }
106 
107  void clear() { Bits.clear(); }
108 
109  void resize(unsigned N) { Bits.resize(N << (BitNum - 1)); }
110 
111  void reserve(unsigned N) { Bits.reserve(N << (BitNum-1)); }
112 
114  Bits.reset();
115  return *this;
116  }
117 
118  void push_back(T val) {
119  resize(size()+1);
120  (*this)[size()-1] = val;
121  }
122 
123  reference operator[](unsigned Idx) {
124  return reference(*this, Idx);
125  }
126 
127  T operator[](unsigned Idx) const {
128  return base::getValue(Bits, Idx);
129  }
130 
131  bool operator==(const PackedVector &RHS) const {
132  return Bits == RHS.Bits;
133  }
134 
135  bool operator!=(const PackedVector &RHS) const {
136  return Bits != RHS.Bits;
137  }
138 
140  Bits |= RHS.Bits;
141  return *this;
142  }
143 };
144 
145 // Leave BitNum=0 undefined.
146 template <typename T> class PackedVector<T, 0>;
147 
148 } // end namespace llvm
149 
150 #endif // LLVM_ADT_PACKEDVECTOR_H
PackedVector & operator|=(const PackedVector &RHS)
Definition: PackedVector.h:139
unsigned size() const
Definition: PackedVector.h:105
void reserve(unsigned N)
Definition: PackedVector.h:111
This class represents lattice values for constants.
Definition: AllocatorList.h:23
PackedVector & reset()
Definition: PackedVector.h:113
bool operator==(const PackedVector &RHS) const
Definition: PackedVector.h:131
static T getValue(const BitVectorTy &Bits, unsigned Idx)
Definition: PackedVector.h:47
block Block Frequency true
void resize(unsigned N)
Definition: PackedVector.h:109
reference operator[](unsigned Idx)
Definition: PackedVector.h:123
static T getValue(const BitVectorTy &Bits, unsigned Idx)
Definition: PackedVector.h:30
static void setValue(BitVectorTy &Bits, unsigned Idx, T val)
Definition: PackedVector.h:37
Store a vector of values using a specific number of bits for each value.
Definition: PackedVector.h:75
PackedVector(unsigned size)
Definition: PackedVector.h:101
bool operator!=(const PackedVector &RHS) const
Definition: PackedVector.h:135
bool empty() const
Definition: PackedVector.h:103
reference(PackedVector &vec, unsigned idx)
Definition: PackedVector.h:88
static void setValue(BitVectorTy &Bits, unsigned Idx, T val)
Definition: PackedVector.h:56
void push_back(T val)
Definition: PackedVector.h:118
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1173
T operator[](unsigned Idx) const
Definition: PackedVector.h:127
#define N
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
reference & operator=(T val)
Definition: PackedVector.h:90