hphp/runtime/vm/jit/alias-id-set.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15 */
  16
  17 #ifndef incl_HPHP_JIT_ALIAS_IDSET_
  18 #define incl_HPHP_JIT_ALIAS_IDSET_
  19
  20 #include "hphp/util/assertions.h"
  21
  22 #include <folly/Optional.h>
  23
  24 #include <string>
  25
  26 namespace HPHP { namespace jit {
  27 ///////////////////////////////////////////////////////////////////////////
  28
  29 /*
  30  * Use 64 bits to represent a set of non-negative integer IDs less than
  31  * `Max', encoded in one of the following modes.
  32  *
  33  * (1) 'Bitset' mode, when MSB (63th bit) is set.
  34  *
  35  *     It uses the lower 62 bits as a bitset, where each bit indicates the
  36  *     presence of the corresponding number. Bit 62 indicates the presence
  37  *     of 'the upper range', i.e., [62, Max).
  38  *
  39  *     Special cases in this mode:
  40  *         `Any'   when all bits are set.
  41  *         `Empty' when only MSB is set.
  42  *
  43  * (2) 'Big-integer' mode, when MSB is not set.
  44  *
  45  *     It uses the lower 32 bits to represent a single integer in the range
  46  *     of [62, Max).
  47  *
  48  *     Note that for a single integer below 62, we always use bitset
  49  *     mode, to make sure there is a single unique representation. The
  50  *     implementation depends on this invariant.
  51  *
  52  * This is designed to be used in alias classes. In most cases, a set that
  53  * cannot be precisely represented will be enlarged (as indicated by the
  54  * presence of the upper range).  However, we guarantee precise representation
  55  * of any single ID, and any subset of of IDs below 62. Hopefully, these cover
  56  * most practical cases.
  57  */
  58 struct AliasIdSet {
  59   static constexpr auto Any = ~0ull;
  60   static constexpr auto Empty = 1ull << 63;
  61   static constexpr auto UpperRange = 1ull << 62; // indicating [62, Max)
  62   static constexpr auto Max = std::numeric_limits<uint32_t>::max();
  63   static constexpr auto BitsetMax = 61u; // any subset of [0, BitsetMax]
  64
  65   /*
  66    * We can construct the set directly from 0 or 1 integer, or a range of
  67    * integers.
  68    */
  69   AliasIdSet() : m_bits(Empty) {}
  70   /* implicit */ AliasIdSet(uint32_t id);
  71
  72   /*
  73    * A range of unsigned integers [l, h).
  74    */
  75   struct IdRange {
  76     static constexpr auto Max = AliasIdSet::Max;
  77
  78     explicit IdRange(uint32_t a, uint32_t b = Max)
  79       : l(a)
  80       , h(std::max(a, b))
  81     {
  82       assertx(l <= h);
  83     }
  84
  85     uint32_t size() const       { return h == Max ? Max : h - l; }
  86     bool empty() const          { return l == h; }
  87     bool hasSingleValue() const { return h - l == 1; }
  88
  89     uint32_t l;
  90     uint32_t h;
  91   };
  92
  93   /* implicit */ AliasIdSet(IdRange r);
  94
  95   /*
  96    * A fancier constructor that initializes the set from an arbitrary
  97    * number of integers and ranges, e.g.,
  98    *
  99    *   `AliasIdSet { 0, IdRange { 3, x }, y, IdRange { 12 } }'.
 100    */
 101   template<typename... Args>
 102   explicit AliasIdSet(Args... args) : m_bits(Empty) {
 103     set(args...);
 104   }
 105
 106   AliasIdSet(const AliasIdSet&) = default;
 107   AliasIdSet& operator=(const AliasIdSet&) = default;
 108
 109   /*
 110    * Check if the set is in a specific mode.
 111    */
 112   bool isBitset() const     { return m_bits & Empty; }
 113   bool isBigInteger() const { return !isBitset(); }
 114
 115   /*
 116    * @returns: the number of elements in the set, `Max' when the set is
 117    * unbounded.
 118    *
 119    * Note: If you want to see whether the set has exactly 0 or 1 element,
 120    * use `empty()' or `hasSingleValue()' instead. If you want to see if the
 121    * set is unbounded, use `hasUpperRange()' instead. Those methods are
 122    * slightly cheaper.
 123    */
 124   uint32_t size() const;
 125
 126   /*
 127    * Check if `size()' is 0/1/Max.
 128    */
 129   bool empty() const           { return m_bits == Empty; }
 130   bool hasSingleValue() const;
 131   bool hasUpperRange() const   { return m_bits & UpperRange; }
 132
 133   bool isAny() const           { return m_bits == Any; }
 134
 135   /*
 136    * Return the single value represented by the set.
 137    *
 138    * @requires: hasSingleValue()
 139    */
 140   uint32_t singleValue() const;
 141
 142   /*
 143    * Convert to bitset mode, possibly enlarging the set, and return *this.
 144    */
 145   AliasIdSet& toBitset() {
 146     if (isBigInteger()) {
 147       m_bits = Empty | UpperRange;
 148     }
 149     return *this;
 150   }
 151
 152   /*
 153    * Expose internal data.
 154    *
 155    * Note: since every set has a unique representation, this can be used
 156    * for hashing.
 157    */
 158   uint32_t raw() const {
 159     assertx(checkInvariants());
 160     return m_bits;
 161   }
 162
 163   /*
 164    * Add an element or a range to the set.
 165    */
 166   void set(uint32_t id);
 167   void set(IdRange range);
 168
 169   /*
 170    * Add elements, list of integers, ranges, or mixture of them.
 171    */
 172   template<class T, class... Tail> void set(T first, Tail... tail) {
 173     set(first);
 174     set(tail...);
 175   }
 176
 177   /*
 178    * Add upper range to the set, possibly enlarging the set.
 179    */
 180   void setUpperRange() {
 181     if (isBigInteger()) {
 182       m_bits = Empty | UpperRange;
 183     } else {
 184       m_bits |= UpperRange;
 185     }
 186   }
 187
 188   /*
 189    * Unset an element.
 190    */
 191   void unset(uint32_t id);
 192
 193   /*
 194    * Test if an element is in the set.
 195    */
 196   bool test(uint32_t id) const;
 197
 198   void clear() { m_bits = Empty; }
 199
 200   /*
 201    * Does this have nonempty intersection with another set?
 202    */
 203   bool maybe(const AliasIdSet other) const;
 204
 205   friend bool operator==(const AliasIdSet lhs, const AliasIdSet rhs) {
 206     return lhs.m_bits == rhs.m_bits;
 207   }
 208
 209   friend bool operator!=(const AliasIdSet lhs, const AliasIdSet rhs) {
 210     return !(lhs == rhs);
 211   }
 212
 213   /*
 214    * @returns: whether `lhs' is a subset of `rhs'.
 215    */
 216   friend bool operator<=(const AliasIdSet lhs, const AliasIdSet rhs) {
 217     return lhs.isSubsetOf(rhs);
 218   }
 219
 220   /*
 221    * @returns: the union of `lhs' and `rhs'.
 222    *
 223    * Note: result is possibly larger than the real union when it has upper
 224    * range.  Communitivity is guaranteed.
 225    */
 226   AliasIdSet operator|=(const AliasIdSet rhs);
 227
 228   friend AliasIdSet operator|(const AliasIdSet lhs, const AliasIdSet rhs) {
 229     auto res = lhs;
 230     res |= rhs;
 231     return res;
 232   }
 233
 234   friend std::string show(const AliasIdSet ids) { return ids.toString(); }
 235
 236 private:
 237   bool isSubsetOf(const AliasIdSet rhs) const;
 238   bool checkInvariants() const;
 239   std::string toString() const;
 240
 241 private:
 242   uint64_t m_bits;
 243 };
 244
 245 ///////////////////////////////////////////////////////////////////////////////
 246
 247 using IdRange = AliasIdSet::IdRange;
 248
 249 static_assert(sizeof(AliasIdSet) == sizeof(uint64_t), "");
 250
 251 ///////////////////////////////////////////////////////////////////////////////
 252 }}
 253
 254 #endif