]>
Commit | Line | Data |
---|---|---|
c63539ff ML |
1 | .. |
2 | Copyright 1988-2022 Free Software Foundation, Inc. | |
3 | This is part of the GCC manual. | |
4 | For copying conditions, see the copyright.rst file. | |
5 | ||
6 | Comparisons involving poly_int | |
7 | ****************************** | |
8 | ||
9 | In general we need to compare sizes and offsets in two situations: | |
10 | those in which the values need to be ordered, and those in which | |
11 | the values can be unordered. More loosely, the distinction is often | |
12 | between values that have a definite link (usually because they refer to the | |
13 | same underlying register or memory location) and values that have | |
14 | no definite link. An example of the former is the relationship between | |
15 | the inner and outer sizes of a subreg, where we must know at compile time | |
16 | whether the subreg is paradoxical, partial, or complete. An example of | |
17 | the latter is alias analysis: we might want to check whether two | |
18 | arbitrary memory references overlap. | |
19 | ||
20 | Referring back to the examples in the previous section, it makes sense | |
21 | to ask whether a memory reference of size :samp:`3 + 4{x}` overlaps | |
22 | one of size :samp:`1 + 5{x}`, but it does not make sense to have a | |
23 | subreg in which the outer mode has :samp:`3 + 4{x}` bytes and the | |
24 | inner mode has :samp:`1 + 5{x}` bytes (or vice versa). Such subregs | |
25 | are always invalid and should trigger an internal compiler error | |
26 | if formed. | |
27 | ||
28 | The underlying operators are the same in both cases, but the distinction | |
29 | affects how they are used. | |
30 | ||
31 | .. toctree:: | |
32 | :maxdepth: 2 | |
33 | ||
34 | .. _comparison-functions-for-poly_int: | |
35 | ||
36 | Comparison functions for poly_int | |
37 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | |
38 | ||
39 | ``poly_int`` provides the following routines for checking whether | |
40 | a particular condition 'may be' (might be) true: | |
41 | ||
42 | .. code-block:: c++ | |
43 | ||
44 | maybe_lt maybe_le maybe_eq maybe_ge maybe_gt | |
45 | maybe_ne | |
46 | ||
47 | The functions have their natural meaning: | |
48 | ||
49 | :samp:`maybe_lt({a}, {b})` | |
50 | Return true if :samp:`{a}` might be less than :samp:`{b}`. | |
51 | ||
52 | :samp:`maybe_le({a}, {b})` | |
53 | Return true if :samp:`{a}` might be less than or equal to :samp:`{b}`. | |
54 | ||
55 | :samp:`maybe_eq({a}, {b})` | |
56 | Return true if :samp:`{a}` might be equal to :samp:`{b}`. | |
57 | ||
58 | :samp:`maybe_ne({a}, {b})` | |
59 | Return true if :samp:`{a}` might not be equal to :samp:`{b}`. | |
60 | ||
61 | :samp:`maybe_ge({a}, {b})` | |
62 | Return true if :samp:`{a}` might be greater than or equal to :samp:`{b}`. | |
63 | ||
64 | :samp:`maybe_gt({a}, {b})` | |
65 | Return true if :samp:`{a}` might be greater than :samp:`{b}`. | |
66 | ||
67 | For readability, ``poly_int`` also provides 'known' inverses of these functions: | |
68 | ||
69 | .. code-block:: c++ | |
70 | ||
71 | known_lt (a, b) == !maybe_ge (a, b) | |
72 | known_le (a, b) == !maybe_gt (a, b) | |
73 | known_eq (a, b) == !maybe_ne (a, b) | |
74 | known_ge (a, b) == !maybe_lt (a, b) | |
75 | known_gt (a, b) == !maybe_le (a, b) | |
76 | known_ne (a, b) == !maybe_eq (a, b) | |
77 | ||
78 | Properties of the poly_int comparisons | |
79 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | |
80 | ||
81 | All 'maybe' relations except ``maybe_ne`` are transitive, so for example: | |
82 | ||
83 | .. code-block:: c++ | |
84 | ||
85 | maybe_lt (a, b) && maybe_lt (b, c) implies maybe_lt (a, c) | |
86 | ||
87 | for all :samp:`{a}`, :samp:`{b}` and :samp:`{c}`. ``maybe_lt``, ``maybe_gt`` | |
88 | and ``maybe_ne`` are irreflexive, so for example: | |
89 | ||
90 | .. code-block:: c++ | |
91 | ||
92 | !maybe_lt (a, a) | |
93 | ||
94 | is true for all :samp:`{a}`. ``maybe_le``, ``maybe_eq`` and ``maybe_ge`` | |
95 | are reflexive, so for example: | |
96 | ||
97 | .. code-block:: c++ | |
98 | ||
99 | maybe_le (a, a) | |
100 | ||
101 | is true for all :samp:`{a}`. ``maybe_eq`` and ``maybe_ne`` are symmetric, so: | |
102 | ||
103 | .. code-block:: c++ | |
104 | ||
105 | maybe_eq (a, b) == maybe_eq (b, a) | |
106 | maybe_ne (a, b) == maybe_ne (b, a) | |
107 | ||
108 | for all :samp:`{a}` and :samp:`{b}`. In addition: | |
109 | ||
110 | .. code-block:: c++ | |
111 | ||
112 | maybe_le (a, b) == maybe_lt (a, b) || maybe_eq (a, b) | |
113 | maybe_ge (a, b) == maybe_gt (a, b) || maybe_eq (a, b) | |
114 | maybe_lt (a, b) == maybe_gt (b, a) | |
115 | maybe_le (a, b) == maybe_ge (b, a) | |
116 | ||
117 | However: | |
118 | ||
119 | .. code-block:: c++ | |
120 | ||
121 | maybe_le (a, b) && maybe_le (b, a) does not imply !maybe_ne (a, b) [== known_eq (a, b)] | |
122 | maybe_ge (a, b) && maybe_ge (b, a) does not imply !maybe_ne (a, b) [== known_eq (a, b)] | |
123 | ||
124 | One example is again :samp:`{a} == 3 + 4{x}` | |
125 | and :samp:`{b} == 1 + 5{x}`, where :samp:`maybe_le ({a}, {b})`, | |
126 | :samp:`maybe_ge ({a}, {b})` and :samp:`maybe_ne ({a}, {b})` | |
127 | all hold. ``maybe_le`` and ``maybe_ge`` are therefore not antisymetric | |
128 | and do not form a partial order. | |
129 | ||
130 | From the above, it follows that: | |
131 | ||
132 | * All 'known' relations except ``known_ne`` are transitive. | |
133 | ||
134 | * ``known_lt``, ``known_ne`` and ``known_gt`` are irreflexive. | |
135 | ||
136 | * ``known_le``, ``known_eq`` and ``known_ge`` are reflexive. | |
137 | ||
138 | Also: | |
139 | ||
140 | .. code-block:: c++ | |
141 | ||
142 | known_lt (a, b) == known_gt (b, a) | |
143 | known_le (a, b) == known_ge (b, a) | |
144 | known_lt (a, b) implies !known_lt (b, a) [asymmetry] | |
145 | known_gt (a, b) implies !known_gt (b, a) | |
146 | known_le (a, b) && known_le (b, a) == known_eq (a, b) [== !maybe_ne (a, b)] | |
147 | known_ge (a, b) && known_ge (b, a) == known_eq (a, b) [== !maybe_ne (a, b)] | |
148 | ||
149 | ``known_le`` and ``known_ge`` are therefore antisymmetric and are | |
150 | partial orders. However: | |
151 | ||
152 | .. code-block:: c++ | |
153 | ||
154 | known_le (a, b) does not imply known_lt (a, b) || known_eq (a, b) | |
155 | known_ge (a, b) does not imply known_gt (a, b) || known_eq (a, b) | |
156 | ||
157 | For example, :samp:`known_le (4, 4 + 4{x})` holds because the runtime | |
158 | indeterminate :samp:`{x}` is a nonnegative integer, but neither | |
159 | ``known_lt (4, 4 + 4x)`` nor ``known_eq (4, 4 + 4x)`` hold. | |
160 | ||
161 | Comparing potentially-unordered poly_ints | |
162 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | |
163 | ||
164 | In cases where there is no definite link between two ``poly_int`` s, | |
165 | we can usually make a conservatively-correct assumption. For example, | |
166 | the conservative assumption for alias analysis is that two references | |
167 | *might* alias. | |
168 | ||
169 | One way of checking whether [ :samp:`{begin1}`, :samp:`{end1}`) might overlap | |
170 | [ :samp:`{begin2}`, :samp:`{end2}`) using the ``poly_int`` comparisons is: | |
171 | ||
172 | .. code-block:: c++ | |
173 | ||
174 | maybe_gt (end1, begin2) && maybe_gt (end2, begin1) | |
175 | ||
176 | and another (equivalent) way is: | |
177 | ||
178 | .. code-block:: c++ | |
179 | ||
180 | !(known_le (end1, begin2) || known_le (end2, begin1)) | |
181 | ||
182 | However, in this particular example, it is better to use the range helper | |
183 | functions instead. See :ref:`range-checks-on-poly_ints`. | |
184 | ||
185 | Comparing ordered poly_ints | |
186 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ | |
187 | ||
188 | In cases where there is a definite link between two ``poly_int`` s, | |
189 | such as the outer and inner sizes of subregs, we usually require the sizes | |
190 | to be ordered by the ``known_le`` partial order. ``poly_int`` provides | |
191 | the following utility functions for ordered values: | |
192 | ||
193 | :samp:`ordered_p ({a}, {b})` | |
194 | Return true if :samp:`{a}` and :samp:`{b}` are ordered by the ``known_le`` | |
195 | partial order. | |
196 | ||
197 | :samp:`ordered_min ({a}, {b})` | |
198 | Assert that :samp:`{a}` and :samp:`{b}` are ordered by ``known_le`` and return the | |
199 | minimum of the two. When using this function, please add a comment explaining | |
200 | why the values are known to be ordered. | |
201 | ||
202 | :samp:`ordered_max ({a}, {b})` | |
203 | Assert that :samp:`{a}` and :samp:`{b}` are ordered by ``known_le`` and return the | |
204 | maximum of the two. When using this function, please add a comment explaining | |
205 | why the values are known to be ordered. | |
206 | ||
207 | For example, if a subreg has an outer mode of size :samp:`{outer}` and an | |
208 | inner mode of size :samp:`{inner}` : | |
209 | ||
210 | * the subreg is complete if known_eq (:samp:`{inner}`, :samp:`{outer}`) | |
211 | ||
212 | * otherwise, the subreg is paradoxical if known_le (:samp:`{inner}`, :samp:`{outer}`) | |
213 | ||
214 | * otherwise, the subreg is partial if known_le (:samp:`{outer}`, :samp:`{inner}`) | |
215 | ||
216 | * otherwise, the subreg is ill-formed | |
217 | ||
218 | Thus the subreg is only valid if | |
219 | :samp:`ordered_p ({outer}, {inner})` is true. If this condition | |
220 | is already known to be true then: | |
221 | ||
222 | * the subreg is complete if known_eq (:samp:`{inner}`, :samp:`{outer}`) | |
223 | ||
224 | * the subreg is paradoxical if maybe_lt (:samp:`{inner}`, :samp:`{outer}`) | |
225 | ||
226 | * the subreg is partial if maybe_lt (:samp:`{outer}`, :samp:`{inner}`) | |
227 | ||
228 | with the three conditions being mutually exclusive. | |
229 | ||
230 | Code that checks whether a subreg is valid would therefore generally | |
231 | check whether ``ordered_p`` holds (in addition to whatever other | |
232 | checks are required for subreg validity). Code that is dealing | |
233 | with existing subregs can assert that ``ordered_p`` holds | |
234 | and use either of the classifications above. | |
235 | ||
236 | Checking for a poly_int marker value | |
237 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ | |
238 | ||
239 | It is sometimes useful to have a special 'marker value' that is not | |
240 | meant to be taken literally. For example, some code uses a size | |
241 | of -1 to represent an unknown size, rather than having to carry around | |
242 | a separate boolean to say whether the size is known. | |
243 | ||
244 | The best way of checking whether something is a marker value is | |
245 | ``known_eq``. Conversely the best way of checking whether something | |
246 | is *not* a marker value is ``maybe_ne``. | |
247 | ||
248 | Thus in the size example just mentioned, :samp:`known_eq (size, -1)` would | |
249 | check for an unknown size and :samp:`maybe_ne (size, -1)` would check for a | |
250 | known size. | |
251 | ||
252 | .. _range-checks-on-poly_ints: | |
253 | ||
254 | Range checks on poly_ints | |
255 | ^^^^^^^^^^^^^^^^^^^^^^^^^ | |
256 | ||
257 | As well as the core comparisons | |
258 | (see :ref:`comparison-functions-for-poly_int`), ``poly_int`` provides | |
259 | utilities for various kinds of range check. In each case the range | |
260 | is represented by a start position and a size rather than a start | |
261 | position and an end position; this is because the former is used | |
262 | much more often than the latter in GCC. Also, the sizes can be | |
263 | -1 (or all ones for unsigned sizes) to indicate a range with a known | |
264 | start position but an unknown size. All other sizes must be nonnegative. | |
265 | A range of size 0 does not contain anything or overlap anything. | |
266 | ||
267 | :samp:`known_size_p ({size})` | |
268 | Return true if :samp:`{size}` represents a known range size, false if it | |
269 | is -1 or all ones (for signed and unsigned types respectively). | |
270 | ||
271 | :samp:`ranges_maybe_overlap_p ({pos1}, {size1}, {pos2}, {size2})` | |
272 | Return true if the range described by :samp:`{pos1}` and :samp:`{size1}` *might* | |
273 | overlap the range described by :samp:`{pos2}` and :samp:`{size2}` (in other words, | |
274 | return true if we cannot prove that the ranges are disjoint). | |
275 | ||
276 | :samp:`ranges_known_overlap_p ({pos1}, {size1}, {pos2}, {size2})` | |
277 | Return true if the range described by :samp:`{pos1}` and :samp:`{size1}` is known to | |
278 | overlap the range described by :samp:`{pos2}` and :samp:`{size2}`. | |
279 | ||
280 | :samp:`known_subrange_p ({pos1}, {size1}, {pos2}, {size2})` | |
281 | Return true if the range described by :samp:`{pos1}` and :samp:`{size1}` is known to | |
282 | be contained in the range described by :samp:`{pos2}` and :samp:`{size2}`. | |
283 | ||
284 | :samp:`maybe_in_range_p ({value}, {pos}, {size})` | |
285 | Return true if :samp:`{value}` *might* be in the range described by | |
286 | :samp:`{pos}` and :samp:`{size}` (in other words, return true if we cannot | |
287 | prove that :samp:`{value}` is outside that range). | |
288 | ||
289 | :samp:`known_in_range_p ({value}, {pos}, {size})` | |
290 | Return true if :samp:`{value}` is known to be in the range described | |
291 | by :samp:`{pos}` and :samp:`{size}`. | |
292 | ||
293 | :samp:`endpoint_representable_p ({pos}, {size})` | |
294 | Return true if the range described by :samp:`{pos}` and :samp:`{size}` is | |
295 | open-ended or if the endpoint (:samp:`{pos}` + :samp:`{size}`) is representable | |
296 | in the same type as :samp:`{pos}` and :samp:`{size}`. The function returns false | |
297 | if adding :samp:`{size}` to :samp:`{pos}` makes conceptual sense but could overflow. | |
298 | ||
299 | There is also a ``poly_int`` version of the ``IN_RANGE_P`` macro: | |
300 | ||
301 | :samp:`coeffs_in_range_p ({x}, {lower}, {upper})` | |
302 | Return true if every coefficient of :samp:`{x}` is in the inclusive range | |
303 | [ :samp:`{lower}`, :samp:`{upper}` ]. This function can be useful when testing | |
304 | whether an operation would cause the values of coefficients to | |
305 | overflow. | |
306 | ||
307 | Note that the function does not indicate whether :samp:`{x}` itself is in the | |
308 | given range. :samp:`{x}` can be either a constant or a ``poly_int``. | |
309 | ||
310 | Sorting poly_ints | |
311 | ^^^^^^^^^^^^^^^^^ | |
312 | ||
313 | ``poly_int`` provides the following routine for sorting: | |
314 | ||
315 | :samp:`compare_sizes_for_sort ({a}, {b})` | |
316 | Compare :samp:`{a}` and :samp:`{b}` in reverse lexicographical order (that is, | |
317 | compare the highest-indexed coefficients first). This can be useful when | |
318 | sorting data structures, since it has the effect of separating constant | |
319 | and non-constant values. If all values are nonnegative, the constant | |
320 | values come first. | |
321 | ||
322 | Note that the values do not necessarily end up in numerical order. | |
323 | For example, :samp:`1 + 1{x}` would come after :samp:`100` in the sort order, | |
3ed1b4ce | 324 | but may well be less than :samp:`100` at run time. |