src/jitcs_int_adt_bitmap.h

   1 //===-- evm/function.h - Class to represent a single basic block --*- C++ -*-===//
   2 //
   3 // A basicblock contains nodes, and must end in a terminal instruction node.
   4 // Nodes can be instructions, constants. Each node may produce more than one
   5 // result.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _JITCS_INT_ADT_BITMAP_H_
  10 #define _JITCS_INT_ADT_BITMAP_H_
  11
  12 #include "jitcs_base.h"
  13 #include "jitcs_adt_ref.h"
  14 #include "jitcs_int_bitfuncs.h"
  15 #include "jitcs_int_power2funcs.h"
  16 #include "jitcs_typefuncs.h"
  17
  18 #include <stdio.h>
  19
  20 namespace jitcs {
  21 class IDumper;
  22 void DumpBitmap(IDumper& o, const size_t*, size_t);
  23
  24 template <unsigned FLAGS>
  25 struct _Bits {
  26   typedef const size_t CType;
  27   typedef size_t NCType;
  28   static const bool IsConstRef = (FLAGS & REF_Const) != 0;
  29   typedef typename std::conditional<IsConstRef, CType, NCType>::type WordType;
  30   typedef WordType* PtrType;
  31   typedef WordType& RefType;
  32
  33   typedef WordType* iterator;
  34   typedef WordType const* const_iterator;
  35
  36   static_assert(sizeof(WordType) == 4 || sizeof(WordType) == 8, "surprising size_t size");
  37   enum {
  38     E_BitsPerWord = sizeof(WordType) * 8, // 32 or 64
  39     E_Log2OfBitsPerWord = Log2CT<E_BitsPerWord>::Val, // 5 or 6
  40     E_MaskOfBitsPerWord = (1 << E_Log2OfBitsPerWord) - 1, // 0x1f or 0x3f
  41   };
  42
  43   struct BitEnumerator {
  44     size_t const *ptr;
  45     size_t nbits;
  46     size_t curpos0, curbit;
  47
  48     BitEnumerator(const WordType* p, size_t n)
  49       : ptr(p)
  50       , curpos0(0)
  51       , curbit(0)
  52       , nbits(n) {
  53       if (!isEmpty()) {
  54         _advance();
  55       }
  56     }
  57     BitEnumerator(const BitEnumerator&) = default;
  58     BitEnumerator& operator =(const BitEnumerator&) = default;
  59
  60     bool isEmpty() const { return curpos0 >= nbits; }
  61     size_t pos() const { return curpos0 + curbit; }
  62     void next() { ++curbit; _advance(); }
  63
  64     bool operator !() const { return isEmpty(); }
  65     size_t operator *() const { assert(!isEmpty()); return pos(); }
  66     void operator ++() { assert(!isEmpty()); next(); }
  67
  68   private:
  69     void _advance() {
  70       _JITCS_DBG_CHECK_(!isEmpty());
  71       while (curbit >= E_BitsPerWord || (*ptr >> curbit) == 0) {
  72         curpos0 += E_BitsPerWord;
  73         if (isEmpty()) return;
  74         ++ptr;
  75         curbit = 0;
  76       }
  77       curbit = t0cntnz(*ptr, curbit);
  78     }
  79   };
  80
  81
  82   _Bits() : _ptr(nullptr), _nbits(0) {}
  83   _Bits(const _Bits&) = default;
  84   _Bits& operator = (const _Bits&) = default;
  85
  86   template <unsigned FLAGS2>
  87   _Bits(_Bits<FLAGS2> o) {
  88     static_assert((~FLAGS & FLAGS2) == 0, "incompatible _Bits flags");
  89     //static_assert(std::is_base_of<T, T2>::value, "incompatible _Bits types");
  90     _ptr = o._ptr;
  91     _nbits = o._nbits;
  92   }
  93   _Bits(PtrType o, size_t n) {
  94     _ptr = o;
  95     _nbits = n;
  96   }
  97
  98   template <unsigned FLAGS2>
  99   _Bits& operator =(_Bits<FLAGS2> o) {
 100     static_assert((~FLAGS & FLAGS2) == 0, "incompatible _Bits flags");
 101     _ptr = o._ptr;
 102     _nbits = o._nbits;
 103   }
 104
 105   PtrType ptr() const { return _ptr; }
 106   size_t bitSize() const { return _nbits; }
 107   size_t wordSize() const { return DivRoundedUpByPowerOf2<E_BitsPerWord>(_nbits); }
 108
 109   bool isEmpty() const { return _nbits == 0; }
 110   bool empty() const { return isEmpty(); }
 111
 112   bool isValidIndex(size_t r) const { return r >= 0 && r < bitSize(); }
 113
 114   iterator wordBegin() { return ptr(); }
 115   iterator wordEnd() { return ptr() + wordSize(); }
 116   const_iterator wordBegin() const { return wordCBegin(); }
 117   const_iterator wordEnd() const { return wordCEnd(); }
 118   const_iterator wordCBegin() const { return ptr(); }
 119   const_iterator wordCEnd() const { return ptr() + wordSize(); }
 120
 121   BitEnumerator enumBits() const { return BitEnumerator(_ptr, _nbits); }
 122
 123   size_t getWordNoForIndex(size_t r) const { return r >> E_Log2OfBitsPerWord; }
 124   size_t getBitNoForIndex(size_t r) const { return r & E_MaskOfBitsPerWord; }
 125   RefType getWordForIndex(size_t r) const { return _ptr[getWordNoForIndex(r)]; }
 126   size_t getBitMaskForIndex(size_t r) const { return 1 << getBitNoForIndex(r); }
 127   size_t getLastWordBitNo() const { return bitSize() & E_MaskOfBitsPerWord; }
 128   size_t getLastWordShift() const { return E_BitsPerWord - getLastWordBitNo(); }
 129   bool hasIncompleteLastWord() const { return getLastWordBitNo() != 0; }
 130
 131   bool test(size_t r) const {
 132     _checkIndex(r);
 133     return (getWordForIndex(r) & getBitMaskForIndex(r)) != 0;
 134   }
 135   bool operator [](size_t i) const { return test(i); }
 136
 137   size_t countSetBits() const {
 138     size_t n = wordSize();
 139     size_t sum = 0;
 140     if (hasIncompleteLastWord()) {
 141       sum += popcnt(_ptr[n - 1] << getLastWordShift());
 142       --n;
 143     }
 144     for (size_t i = 0; i < n; ++i) {
 145       sum += popcnt(_ptr[i]);
 146     }
 147     return sum;
 148   }
 149   bool isAllZeroes() const {
 150     size_t n = wordSize();
 151     if (hasIncompleteLastWord()) {
 152       if ((_ptr[n - 1] << getLastWordShift()) != 0) return false;
 153     }
 154     for (size_t i = 0; i < n; ++i) {
 155       if (_ptr[i] != 0) return false;
 156     }
 157     return true;
 158   }
 159   bool isAllOnes() const {
 160     size_t n = wordSize();
 161     if (hasIncompleteLastWord()) {
 162       if (((~_ptr[n - 1]) << getLastWordShift()) != 0) return false;
 163     }
 164     for (size_t i = 0; i < n; ++i) {
 165       if ((~_ptr[i]) != 0) return false;
 166     }
 167     return true;
 168   }
 169   template <unsigned FLAGS2>
 170   bool isSubsetOf(const _Bits<FLAGS2>& p) const {
 171     _checkNotLongerThan(p);
 172     size_t n = wordSize();
 173     if (hasIncompleteLastWord()) {
 174       if ((_ptr[n - 1] & ~p._ptr[n - 1]) << getLastWordShift()) return false;
 175       --n;
 176     }
 177     for (size_t i = 0; i < n; ++i) {
 178       if (_ptr[i] & ~p._ptr[i]) return false;
 179     }
 180     return true;
 181   }
 182   template <unsigned FLAGS2>
 183   bool equals(const _Bits<FLAGS2>& p) const {
 184     _checkNotLongerThan(p);
 185     //if (bitSize() != p.bitSize()) return false;
 186     size_t n = wordSize();
 187     if (hasIncompleteLastWord()) {
 188       if ((_ptr[n - 1] ^ p._ptr[n - 1]) << getLastWordShift()) return false;
 189       --n;
 190     }
 191     for (size_t i = 0; i < n; ++i) {
 192       if (_ptr[i] != p._ptr[i]) return false;
 193     }
 194     return true;
 195   }
 196
 197   void mark(size_t r) {
 198     guarantee<(FLAGS & REF_Const) == 0>
 199       ("mutation disabled for immutable bitmap views");
 200     _checkIndex(r);
 201     RefType rw = getWordForIndex(r);
 202     rw |= getBitMaskForIndex(r);
 203   }
 204   void clear(size_t r) {
 205     guarantee<(FLAGS & REF_Const) == 0>
 206       ("mutation disabled for immutable bitmap views");
 207     _checkIndex(r);
 208     RefType rw = getWordForIndex(r);
 209     rw &= ~getBitMaskForIndex(r);
 210   }
 211   bool testAndMark(size_t r)  {
 212     guarantee<(FLAGS & REF_Const) == 0>
 213       ("mutation disabled for immutable bitmap views");
 214     _checkIndex(r);
 215     RefType rw = getWordForIndex(r);
 216     WordType m = getBitMaskForIndex(r);
 217     bool res = (rw & m) != 0;
 218     rw |= m;
 219     return res;
 220   }
 221   bool testAndClear(size_t r)  {
 222     guarantee<(FLAGS & REF_Const) == 0>
 223       ("mutation disabled for immutable bitmap views");
 224     _checkIndex(r);
 225     RefType rw = getWordForIndex(r);
 226     WordType m = getBitMaskForIndex(r);
 227     bool res = (rw & m) != 0;
 228     rw &= ~m;
 229     return res;
 230   }
 231   bool testAndComplement(size_t r)  {
 232     guarantee<(FLAGS & REF_Const) == 0>
 233       ("mutation disabled for immutable bitmap views");
 234     _checkIndex(r);
 235     RefType rw = getWordForIndex(r);
 236     WordType m = getBitMaskForIndex(r);
 237     bool res = (rw & m) != 0;
 238     rw ^= m;
 239     return res;
 240   }
 241
 242   void clearAll() {
 243     guarantee<(FLAGS & REF_Const) == 0>
 244       ("mutation disabled for immutable bitmap views");
 245     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 246       _ptr[i] = 0;
 247     }
 248   }
 249   void setAll() {
 250     guarantee<(FLAGS & REF_Const) == 0>
 251       ("mutation disabled for immutable bitmap views");
 252     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 253       _ptr[i] = ~0;
 254     }
 255   }
 256   template <unsigned FLAGS2>
 257   void copyFrom(const _Bits<FLAGS2>& p) {
 258     _checkNotLongerThan(p);
 259     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 260       _ptr[i] = p._ptr[i];
 261     }
 262   }
 263   template <unsigned FLAGS2>
 264   void intersectWith(const _Bits<FLAGS2>& p) {
 265     _checkNotLongerThan(p);
 266     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 267       _ptr[i] &= p._ptr[i];
 268     }
 269   }
 270   template <unsigned FLAGS2>
 271   void uniteWith(const _Bits<FLAGS2>& p) {
 272     _checkNotLongerThan(p);
 273     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 274       _ptr[i] |= p._ptr[i];
 275     }
 276   }
 277   template <unsigned FLAGS2>
 278   void setFrom(const _Bits<FLAGS2>& p) {
 279     return uniteWith(p);
 280   }
 281   template <unsigned FLAGS2>
 282   void clearFrom(const _Bits<FLAGS2>& p) {
 283     _checkNotLongerThan(p);
 284     for (size_t i = 0, n = wordSize(); i < n; ++i) {
 285       _ptr[i] &= ~p._ptr[i];
 286     }
 287   }
 288
 289   void dump(IDumper& o) const { DumpBitmap(o, _ptr, _nbits); }
 290
 291 private:
 292   void _checkIndex(size_t r) const { _JITCS_DBG_CHECK_(isValidIndex(r)); }
 293   template <unsigned FLAGS2>
 294   void _checkNotLongerThan(const _Bits<FLAGS2>& bmp) const {
 295     _JITCS_DBG_CHECK_(bitSize() <= bmp.bitSize());
 296   }
 297
 298 public:
 299   WordType *_ptr;
 300   size_t _nbits;
 301 };
 302
 303 typedef _Bits<REF_Any> BitSlice;
 304 typedef _Bits<REF_Const> ConstBitSlice;
 305
 306 template <size_t N>
 307 struct DynBitSlice : BitSlice {
 308   size_t _short_data[RoundUpToPowerOf2CT<N, E_BitsPerWord>::Val];
 309
 310   DynBitSlice(size_t nbits, bool clear) {
 311     size_t n = DivRoundedUpByPowerOf2< E_BitsPerWord>(nbits);
 312     _ptr = n <= RoundUpToPowerOf2CT<N,  E_BitsPerWord>::Val ? _short_data : new size_t[n];
 313     _nbits = nbits;
 314     if (clear) clearAll();
 315   }
 316   ~DynBitSlice() {
 317     if (isUsingHeap()) delete[] _ptr;
 318   }
 319   bool isUsingHeap() const { return _ptr != _short_data; }
 320 };
 321
 322
 323 } // end of jitcs namespace
 324
 325 #endif
 326 // _JITCS_INT_ADT_BITMAP_H_