gcc/mux-utils.h

   1 // Multiplexer utilities
   2 // Copyright (C) 2020-2024 Free Software Foundation, Inc.
   3 //
   4 // This file is part of GCC.
   5 //
   6 // GCC is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU General Public License as published by the Free
   8 // Software Foundation; either version 3, or (at your option) any later
   9 // version.
  10 //
  11 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 // for more details.
  15 //
  16 // You should have received a copy of the GNU General Public License
  17 // along with GCC; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20 #ifndef GCC_MUX_UTILS_H
  21 #define GCC_MUX_UTILS_H 1
  22
  23 // A class that stores a choice "A or B", where A has type T1 * and B has
  24 // type T2 *.  Both T1 and T2 must have an alignment greater than 1, since
  25 // the low bit is used to identify B over A.  T1 and T2 can be the same.
  26 //
  27 // A can be a null pointer but B cannot.
  28 //
  29 // Barring the requirement that B must be nonnull, using the class is
  30 // equivalent to using:
  31 //
  32 //     union { T1 *A; T2 *B; };
  33 //
  34 // and having a separate tag bit to indicate which alternative is active.
  35 // However, using this class can have two advantages over a union:
  36 //
  37 // - It avoids the need to find somewhere to store the tag bit.
  38 //
  39 // - The compiler is aware that B cannot be null, which can make checks
  40 //   of the form:
  41 //
  42 //       if (auto *B = mux.dyn_cast<T2 *> ())
  43 //
  44 //   more efficient.  With a union-based representation, the dyn_cast
  45 //   check could fail either because MUX is an A or because MUX is a
  46 //   null B, both of which require a run-time test.  With a pointer_mux,
  47 //   only a check for MUX being A is needed.
  48 template<typename T1, typename T2 = T1>
  49 class pointer_mux
  50 {
  51 public:
  52   // Return an A pointer with the given value.
  53   static pointer_mux first (T1 *);
  54
  55   // Return a B pointer with the given (nonnull) value.
  56   static pointer_mux second (T2 *);
  57
  58   pointer_mux () = default;
  59
  60   // Create a null A pointer.
  61   pointer_mux (std::nullptr_t) : m_ptr (nullptr) {}
  62
  63   // Create an A or B pointer with the given value.  This is only valid
  64   // if T1 and T2 are distinct and if T can be resolved to exactly one
  65   // of them.
  66   template<typename T,
  67            typename Enable = typename
  68              std::enable_if<std::is_convertible<T *, T1 *>::value
  69                             != std::is_convertible<T *, T2 *>::value>::type>
  70   pointer_mux (T *ptr);
  71
  72   // Return true unless the pointer is a null A pointer.
  73   explicit operator bool () const { return m_ptr; }
  74
  75   // Assign A and B pointers respectively.
  76   void set_first (T1 *ptr) { *this = first (ptr); }
  77   void set_second (T2 *ptr) { *this = second (ptr); }
  78
  79   // Return true if the pointer is an A pointer.
  80   bool is_first () const { return !(uintptr_t (m_ptr) & 1); }
  81
  82   // Return true if the pointer is a B pointer.
  83   bool is_second () const { return uintptr_t (m_ptr) & 1; }
  84
  85   // Return the contents of the pointer, given that it is known to be
  86   // an A pointer.
  87   T1 *known_first () const { return reinterpret_cast<T1 *> (m_ptr); }
  88
  89   // Return the contents of the pointer, given that it is known to be
  90   // a B pointer.
  91   T2 *known_second () const { return reinterpret_cast<T2 *> (m_ptr - 1); }
  92
  93   // If the pointer is an A pointer, return its contents, otherwise
  94   // return null.  Thus a null return can mean that the pointer is
  95   // either a null A pointer or a B pointer.
  96   //
  97   // If all A pointers are nonnull, it is more efficient to use:
  98   //
  99   //    if (ptr.is_first ())
 100   //      ...use ptr.known_first ()...
 101   //
 102   // over:
 103   //
 104   //    if (T1 *a = ptr.first_or_null ())
 105   //      ...use a...
 106   T1 *first_or_null () const;
 107
 108   // If the pointer is a B pointer, return its contents, otherwise
 109   // return null.  Using:
 110   //
 111   //    if (T1 *b = ptr.second_or_null ())
 112   //      ...use b...
 113   //
 114   // should be at least as efficient as:
 115   //
 116   //    if (ptr.is_second ())
 117   //      ...use ptr.known_second ()...
 118   T2 *second_or_null () const;
 119
 120   bool operator == (const pointer_mux &pm) const { return m_ptr == pm.m_ptr; }
 121
 122   bool operator != (const pointer_mux &pm) const { return m_ptr != pm.m_ptr; }
 123
 124   // Return true if the pointer is a T.
 125   //
 126   // This is only valid if T1 and T2 are distinct and if T can be
 127   // resolved to exactly one of them.  The condition is checked using
 128   // a static assertion rather than SFINAE because it gives a clearer
 129   // error message.
 130   template<typename T>
 131   bool is_a () const;
 132
 133   // Assert that the pointer is a T and return it as such.  See is_a
 134   // for the restrictions on T.
 135   template<typename T>
 136   T as_a () const;
 137
 138   // If the pointer is a T, return it as such, otherwise return null.
 139   // See is_a for the restrictions on T.
 140   template<typename T>
 141   T dyn_cast () const;
 142
 143 private:
 144   pointer_mux (char *ptr) : m_ptr (ptr) {}
 145
 146   // Points to the first byte of an object for A pointers or the second
 147   // byte of an object for B pointers.  Using a pointer rather than a
 148   // uintptr_t tells the compiler that second () can never return null,
 149   // and that second_or_null () is only null if is_first ().
 150   char *m_ptr;
 151 };
 152
 153 template<typename T1, typename T2>
 154 inline pointer_mux<T1, T2>
 155 pointer_mux<T1, T2>::first (T1 *ptr)
 156 {
 157   gcc_checking_assert (!(uintptr_t (ptr) & 1));
 158   return reinterpret_cast<char *> (ptr);
 159 }
 160
 161 template<typename T1, typename T2>
 162 inline pointer_mux<T1, T2>
 163 pointer_mux<T1, T2>::second (T2 *ptr)
 164 {
 165   gcc_checking_assert (ptr && !(uintptr_t (ptr) & 1));
 166   return reinterpret_cast<char *> (ptr) + 1;
 167 }
 168
 169 template<typename T1, typename T2>
 170 template<typename T, typename Enable>
 171 inline pointer_mux<T1, T2>::pointer_mux (T *ptr)
 172   : m_ptr (reinterpret_cast<char *> (ptr))
 173 {
 174   if (std::is_convertible<T *, T2 *>::value)
 175     {
 176       gcc_checking_assert (m_ptr);
 177       m_ptr += 1;
 178     }
 179 }
 180
 181 template<typename T1, typename T2>
 182 inline T1 *
 183 pointer_mux<T1, T2>::first_or_null () const
 184 {
 185   return is_first () ? known_first () : nullptr;
 186 }
 187
 188 template<typename T1, typename T2>
 189 inline T2 *
 190 pointer_mux<T1, T2>::second_or_null () const
 191 {
 192   // Micro optimization that's effective as of GCC 11: compute the value
 193   // of the second pointer as an integer and test that, so that the integer
 194   // result can be reused as the pointer and so that all computation can
 195   // happen before a branch on null.  This reduces the number of branches
 196   // needed for loops.
 197   return (uintptr_t (m_ptr) - 1) & 1 ? nullptr : known_second ();
 198 }
 199
 200 template<typename T1, typename T2>
 201 template<typename T>
 202 inline bool
 203 pointer_mux<T1, T2>::is_a () const
 204 {
 205   static_assert (std::is_convertible<T1 *, T>::value
 206                  != std::is_convertible<T2 *, T>::value,
 207                  "Ambiguous pointer type");
 208   if (std::is_convertible<T2 *, T>::value)
 209     return is_second ();
 210   else
 211     return is_first ();
 212 }
 213
 214 template<typename T1, typename T2>
 215 template<typename T>
 216 inline T
 217 pointer_mux<T1, T2>::as_a () const
 218 {
 219   static_assert (std::is_convertible<T1 *, T>::value
 220                  != std::is_convertible<T2 *, T>::value,
 221                  "Ambiguous pointer type");
 222   if (std::is_convertible<T2 *, T>::value)
 223     {
 224       gcc_checking_assert (is_second ());
 225       return reinterpret_cast<T> (m_ptr - 1);
 226     }
 227   else
 228     {
 229       gcc_checking_assert (is_first ());
 230       return reinterpret_cast<T> (m_ptr);
 231     }
 232 }
 233
 234 template<typename T1, typename T2>
 235 template<typename T>
 236 inline T
 237 pointer_mux<T1, T2>::dyn_cast () const
 238 {
 239   static_assert (std::is_convertible<T1 *, T>::value
 240                  != std::is_convertible<T2 *, T>::value,
 241                  "Ambiguous pointer type");
 242   if (std::is_convertible<T2 *, T>::value)
 243     {
 244       if (is_second ())
 245         return reinterpret_cast<T> (m_ptr - 1);
 246     }
 247   else
 248     {
 249       if (is_first ())
 250         return reinterpret_cast<T> (m_ptr);
 251     }
 252   return nullptr;
 253 }
 254
 255 #endif