1 // Multiplexer utilities
2 // Copyright (C) 2020-2023 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 avoides 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 // Return true if the pointer is a T.
121 //
122 // This is only valid if T1 and T2 are distinct and if T can be
123 // resolved to exactly one of them. The condition is checked using
124 // a static assertion rather than SFINAE because it gives a clearer
125 // error message.
126 template<typename T>
127 bool is_a () const;
128
129 // Assert that the pointer is a T and return it as such. See is_a
130 // for the restrictions on T.
131 template<typename T>
132 T as_a () const;
133
134 // If the pointer is a T, return it as such, otherwise return null.
135 // See is_a for the restrictions on T.
136 template<typename T>
137 T dyn_cast () const;
138
139 private:
140 pointer_mux (char *ptr) : m_ptr (ptr) {}
141
142 // Points to the first byte of an object for A pointers or the second
143 // byte of an object for B pointers. Using a pointer rather than a
144 // uintptr_t tells the compiler that second () can never return null,
145 // and that second_or_null () is only null if is_first ().
146 char *m_ptr;
147 };
148
149 template<typename T1, typename T2>
150 inline pointer_mux<T1, T2>
151 pointer_mux<T1, T2>::first (T1 *ptr)
152 {
153 gcc_checking_assert (!(uintptr_t (ptr) & 1));
154 return reinterpret_cast<char *> (ptr);
155 }
156
157 template<typename T1, typename T2>
158 inline pointer_mux<T1, T2>
159 pointer_mux<T1, T2>::second (T2 *ptr)
160 {
161 gcc_checking_assert (ptr && !(uintptr_t (ptr) & 1));
162 return reinterpret_cast<char *> (ptr) + 1;
163 }
164
165 template<typename T1, typename T2>
166 template<typename T, typename Enable>
167 inline pointer_mux<T1, T2>::pointer_mux (T *ptr)
168 : m_ptr (reinterpret_cast<char *> (ptr))
169 {
170 if (std::is_convertible<T *, T2 *>::value)
171 {
172 gcc_checking_assert (m_ptr);
173 m_ptr += 1;
174 }
175 }
176
177 template<typename T1, typename T2>
178 inline T1 *
179 pointer_mux<T1, T2>::first_or_null () const
180 {
181 return is_first () ? known_first () : nullptr;
182 }
183
184 template<typename T1, typename T2>
185 inline T2 *
186 pointer_mux<T1, T2>::second_or_null () const
187 {
188 // Micro optimization that's effective as of GCC 11: compute the value
189 // of the second pointer as an integer and test that, so that the integer
190 // result can be reused as the pointer and so that all computation can
191 // happen before a branch on null. This reduces the number of branches
192 // needed for loops.
193 return (uintptr_t (m_ptr) - 1) & 1 ? nullptr : known_second ();
194 }
195
196 template<typename T1, typename T2>
197 template<typename T>
198 inline bool
199 pointer_mux<T1, T2>::is_a () const
200 {
201 static_assert (std::is_convertible<T1 *, T>::value
202 != std::is_convertible<T2 *, T>::value,
203 "Ambiguous pointer type");
204 if (std::is_convertible<T2 *, T>::value)
205 return is_second ();
206 else
207 return is_first ();
208 }
209
210 template<typename T1, typename T2>
211 template<typename T>
212 inline T
213 pointer_mux<T1, T2>::as_a () const
214 {
215 static_assert (std::is_convertible<T1 *, T>::value
216 != std::is_convertible<T2 *, T>::value,
217 "Ambiguous pointer type");
218 if (std::is_convertible<T2 *, T>::value)
219 {
220 gcc_checking_assert (is_second ());
221 return reinterpret_cast<T> (m_ptr - 1);
222 }
223 else
224 {
225 gcc_checking_assert (is_first ());
226 return reinterpret_cast<T> (m_ptr);
227 }
228 }
229
230 template<typename T1, typename T2>
231 template<typename T>
232 inline T
233 pointer_mux<T1, T2>::dyn_cast () const
234 {
235 static_assert (std::is_convertible<T1 *, T>::value
236 != std::is_convertible<T2 *, T>::value,
237 "Ambiguous pointer type");
238 if (std::is_convertible<T2 *, T>::value)
239 {
240 if (is_second ())
241 return reinterpret_cast<T> (m_ptr - 1);
242 }
243 else
244 {
245 if (is_first ())
246 return reinterpret_cast<T> (m_ptr);
247 }
248 return nullptr;
249 }
250
251 #endif