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