1 | /* Code for range operators. |
2 | Copyright (C) 2017-2023 Free Software Foundation, Inc. |
3 | Contributed by Andrew MacLeod <amacleod@redhat.com> |
4 | and Aldy Hernandez <aldyh@redhat.com>. |
5 | |
6 | This file is part of GCC. |
7 | |
8 | GCC is free software; you can redistribute it and/or modify |
9 | it under the terms of the GNU General Public License as published by |
10 | the Free Software Foundation; either version 3, or (at your option) |
11 | any later version. |
12 | |
13 | GCC is distributed in the hope that it will be useful, |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
16 | GNU General Public License for more details. |
17 | |
18 | You should have received a copy of the GNU General Public License |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ |
21 | |
22 | #include "config.h" |
23 | #include "system.h" |
24 | #include "coretypes.h" |
25 | #include "backend.h" |
26 | #include "insn-codes.h" |
27 | #include "rtl.h" |
28 | #include "tree.h" |
29 | #include "gimple.h" |
30 | #include "cfghooks.h" |
31 | #include "tree-pass.h" |
32 | #include "ssa.h" |
33 | #include "optabs-tree.h" |
34 | #include "gimple-pretty-print.h" |
35 | #include "diagnostic-core.h" |
36 | #include "flags.h" |
37 | #include "fold-const.h" |
38 | #include "stor-layout.h" |
39 | #include "calls.h" |
40 | #include "cfganal.h" |
41 | #include "gimple-iterator.h" |
42 | #include "gimple-fold.h" |
43 | #include "tree-eh.h" |
44 | #include "gimple-walk.h" |
45 | #include "tree-cfg.h" |
46 | #include "wide-int.h" |
47 | #include "value-relation.h" |
48 | #include "range-op.h" |
49 | #include "tree-ssa-ccp.h" |
50 | #include "range-op-mixed.h" |
51 | |
52 | class pointer_plus_operator : public range_operator |
53 | { |
54 | using range_operator::op2_range; |
55 | public: |
56 | virtual void wi_fold (irange &r, tree type, |
57 | const wide_int &lh_lb, |
58 | const wide_int &lh_ub, |
59 | const wide_int &rh_lb, |
60 | const wide_int &rh_ub) const; |
61 | virtual bool op2_range (irange &r, tree type, |
62 | const irange &lhs, |
63 | const irange &op1, |
64 | relation_trio = TRIO_VARYING) const; |
65 | void update_bitmask (irange &r, const irange &lh, const irange &rh) const |
66 | { update_known_bitmask (r, POINTER_PLUS_EXPR, lh, rh); } |
67 | } op_pointer_plus; |
68 | |
69 | void |
70 | pointer_plus_operator::wi_fold (irange &r, tree type, |
71 | const wide_int &lh_lb, |
72 | const wide_int &lh_ub, |
73 | const wide_int &rh_lb, |
74 | const wide_int &rh_ub) const |
75 | { |
76 | // Check for [0,0] + const, and simply return the const. |
77 | if (lh_lb == 0 && lh_ub == 0 && rh_lb == rh_ub) |
78 | { |
79 | r.set (type, rh_lb, rh_lb); |
80 | return; |
81 | } |
82 | |
83 | // For pointer types, we are really only interested in asserting |
84 | // whether the expression evaluates to non-NULL. |
85 | // |
86 | // With -fno-delete-null-pointer-checks we need to be more |
87 | // conservative. As some object might reside at address 0, |
88 | // then some offset could be added to it and the same offset |
89 | // subtracted again and the result would be NULL. |
90 | // E.g. |
91 | // static int a[12]; where &a[0] is NULL and |
92 | // ptr = &a[6]; |
93 | // ptr -= 6; |
94 | // ptr will be NULL here, even when there is POINTER_PLUS_EXPR |
95 | // where the first range doesn't include zero and the second one |
96 | // doesn't either. As the second operand is sizetype (unsigned), |
97 | // consider all ranges where the MSB could be set as possible |
98 | // subtractions where the result might be NULL. |
99 | if ((!wi_includes_zero_p (type, wmin: lh_lb, wmax: lh_ub) |
100 | || !wi_includes_zero_p (type, wmin: rh_lb, wmax: rh_ub)) |
101 | && !TYPE_OVERFLOW_WRAPS (type) |
102 | && (flag_delete_null_pointer_checks |
103 | || !wi::sign_mask (x: rh_ub))) |
104 | r = range_nonzero (type); |
105 | else if (lh_lb == lh_ub && lh_lb == 0 |
106 | && rh_lb == rh_ub && rh_lb == 0) |
107 | r = range_zero (type); |
108 | else |
109 | r.set_varying (type); |
110 | } |
111 | |
112 | bool |
113 | pointer_plus_operator::op2_range (irange &r, tree type, |
114 | const irange &lhs ATTRIBUTE_UNUSED, |
115 | const irange &op1 ATTRIBUTE_UNUSED, |
116 | relation_trio trio) const |
117 | { |
118 | relation_kind rel = trio.lhs_op1 (); |
119 | r.set_varying (type); |
120 | |
121 | // If the LHS and OP1 are equal, the op2 must be zero. |
122 | if (rel == VREL_EQ) |
123 | r.set_zero (type); |
124 | // If the LHS and OP1 are not equal, the offset must be non-zero. |
125 | else if (rel == VREL_NE) |
126 | r.set_nonzero (type); |
127 | else |
128 | return false; |
129 | return true; |
130 | } |
131 | |
132 | class pointer_min_max_operator : public range_operator |
133 | { |
134 | public: |
135 | virtual void wi_fold (irange & r, tree type, |
136 | const wide_int &lh_lb, const wide_int &lh_ub, |
137 | const wide_int &rh_lb, const wide_int &rh_ub) const; |
138 | } op_ptr_min_max; |
139 | |
140 | void |
141 | pointer_min_max_operator::wi_fold (irange &r, tree type, |
142 | const wide_int &lh_lb, |
143 | const wide_int &lh_ub, |
144 | const wide_int &rh_lb, |
145 | const wide_int &rh_ub) const |
146 | { |
147 | // For MIN/MAX expressions with pointers, we only care about |
148 | // nullness. If both are non null, then the result is nonnull. |
149 | // If both are null, then the result is null. Otherwise they |
150 | // are varying. |
151 | if (!wi_includes_zero_p (type, wmin: lh_lb, wmax: lh_ub) |
152 | && !wi_includes_zero_p (type, wmin: rh_lb, wmax: rh_ub)) |
153 | r = range_nonzero (type); |
154 | else if (wi_zero_p (type, wmin: lh_lb, wmax: lh_ub) && wi_zero_p (type, wmin: rh_lb, wmax: rh_ub)) |
155 | r = range_zero (type); |
156 | else |
157 | r.set_varying (type); |
158 | } |
159 | |
160 | class pointer_and_operator : public range_operator |
161 | { |
162 | public: |
163 | virtual void wi_fold (irange &r, tree type, |
164 | const wide_int &lh_lb, const wide_int &lh_ub, |
165 | const wide_int &rh_lb, const wide_int &rh_ub) const; |
166 | } op_pointer_and; |
167 | |
168 | void |
169 | pointer_and_operator::wi_fold (irange &r, tree type, |
170 | const wide_int &lh_lb, |
171 | const wide_int &lh_ub, |
172 | const wide_int &rh_lb ATTRIBUTE_UNUSED, |
173 | const wide_int &rh_ub ATTRIBUTE_UNUSED) const |
174 | { |
175 | // For pointer types, we are really only interested in asserting |
176 | // whether the expression evaluates to non-NULL. |
177 | if (wi_zero_p (type, wmin: lh_lb, wmax: lh_ub) || wi_zero_p (type, wmin: lh_lb, wmax: lh_ub)) |
178 | r = range_zero (type); |
179 | else |
180 | r.set_varying (type); |
181 | } |
182 | |
183 | |
184 | class pointer_or_operator : public range_operator |
185 | { |
186 | public: |
187 | using range_operator::op1_range; |
188 | using range_operator::op2_range; |
189 | virtual bool op1_range (irange &r, tree type, |
190 | const irange &lhs, |
191 | const irange &op2, |
192 | relation_trio rel = TRIO_VARYING) const; |
193 | virtual bool op2_range (irange &r, tree type, |
194 | const irange &lhs, |
195 | const irange &op1, |
196 | relation_trio rel = TRIO_VARYING) const; |
197 | virtual void wi_fold (irange &r, tree type, |
198 | const wide_int &lh_lb, const wide_int &lh_ub, |
199 | const wide_int &rh_lb, const wide_int &rh_ub) const; |
200 | } op_pointer_or; |
201 | |
202 | bool |
203 | pointer_or_operator::op1_range (irange &r, tree type, |
204 | const irange &lhs, |
205 | const irange &op2 ATTRIBUTE_UNUSED, |
206 | relation_trio) const |
207 | { |
208 | if (lhs.undefined_p ()) |
209 | return false; |
210 | if (lhs.zero_p ()) |
211 | { |
212 | r.set_zero (type); |
213 | return true; |
214 | } |
215 | r.set_varying (type); |
216 | return true; |
217 | } |
218 | |
219 | bool |
220 | pointer_or_operator::op2_range (irange &r, tree type, |
221 | const irange &lhs, |
222 | const irange &op1, |
223 | relation_trio) const |
224 | { |
225 | return pointer_or_operator::op1_range (r, type, lhs, op2: op1); |
226 | } |
227 | |
228 | void |
229 | pointer_or_operator::wi_fold (irange &r, tree type, |
230 | const wide_int &lh_lb, |
231 | const wide_int &lh_ub, |
232 | const wide_int &rh_lb, |
233 | const wide_int &rh_ub) const |
234 | { |
235 | // For pointer types, we are really only interested in asserting |
236 | // whether the expression evaluates to non-NULL. |
237 | if (!wi_includes_zero_p (type, wmin: lh_lb, wmax: lh_ub) |
238 | && !wi_includes_zero_p (type, wmin: rh_lb, wmax: rh_ub)) |
239 | r = range_nonzero (type); |
240 | else if (wi_zero_p (type, wmin: lh_lb, wmax: lh_ub) && wi_zero_p (type, wmin: rh_lb, wmax: rh_ub)) |
241 | r = range_zero (type); |
242 | else |
243 | r.set_varying (type); |
244 | } |
245 | |
246 | class operator_pointer_diff : public range_operator |
247 | { |
248 | virtual bool op1_op2_relation_effect (irange &lhs_range, |
249 | tree type, |
250 | const irange &op1_range, |
251 | const irange &op2_range, |
252 | relation_kind rel) const; |
253 | void update_bitmask (irange &r, const irange &lh, const irange &rh) const |
254 | { update_known_bitmask (r, POINTER_DIFF_EXPR, lh, rh); } |
255 | } op_pointer_diff; |
256 | |
257 | bool |
258 | operator_pointer_diff::op1_op2_relation_effect (irange &lhs_range, tree type, |
259 | const irange &op1_range, |
260 | const irange &op2_range, |
261 | relation_kind rel) const |
262 | { |
263 | return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range, |
264 | rel); |
265 | } |
266 | |
267 | // ---------------------------------------------------------------------- |
268 | // Hybrid operators for the 4 operations which integer and pointers share, |
269 | // but which have different implementations. Simply check the type in |
270 | // the call and choose the appropriate method. |
271 | // Once there is a PRANGE signature, simply add the appropriate |
272 | // prototypes in the rmixed range class, and remove these hybrid classes. |
273 | |
274 | class hybrid_and_operator : public operator_bitwise_and |
275 | { |
276 | public: |
277 | using range_operator::op1_range; |
278 | using range_operator::op2_range; |
279 | using range_operator::lhs_op1_relation; |
280 | bool op1_range (irange &r, tree type, |
281 | const irange &lhs, const irange &op2, |
282 | relation_trio rel = TRIO_VARYING) const final override |
283 | { |
284 | if (INTEGRAL_TYPE_P (type)) |
285 | return operator_bitwise_and::op1_range (r, type, lhs, op2, rel); |
286 | else |
287 | return false; |
288 | } |
289 | bool op2_range (irange &r, tree type, |
290 | const irange &lhs, const irange &op1, |
291 | relation_trio rel = TRIO_VARYING) const final override |
292 | { |
293 | if (INTEGRAL_TYPE_P (type)) |
294 | return operator_bitwise_and::op2_range (r, type, lhs, op1, rel); |
295 | else |
296 | return false; |
297 | } |
298 | relation_kind lhs_op1_relation (const irange &lhs, |
299 | const irange &op1, const irange &op2, |
300 | relation_kind rel) const final override |
301 | { |
302 | if (!lhs.undefined_p () && INTEGRAL_TYPE_P (lhs.type ())) |
303 | return operator_bitwise_and::lhs_op1_relation (lhs, op1, op2, rel); |
304 | else |
305 | return VREL_VARYING; |
306 | } |
307 | void update_bitmask (irange &r, const irange &lh, |
308 | const irange &rh) const final override |
309 | { |
310 | if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ())) |
311 | operator_bitwise_and::update_bitmask (r, lh, rh); |
312 | } |
313 | |
314 | void wi_fold (irange &r, tree type, const wide_int &lh_lb, |
315 | const wide_int &lh_ub, const wide_int &rh_lb, |
316 | const wide_int &rh_ub) const final override |
317 | { |
318 | if (INTEGRAL_TYPE_P (type)) |
319 | return operator_bitwise_and::wi_fold (r, type, lh_lb, lh_ub, |
320 | rh_lb, rh_ub); |
321 | else |
322 | return op_pointer_and.wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub); |
323 | } |
324 | } op_hybrid_and; |
325 | |
326 | // Temporary class which dispatches routines to either the INT version or |
327 | // the pointer version depending on the type. Once PRANGE is a range |
328 | // class, we can remove the hybrid. |
329 | |
330 | class hybrid_or_operator : public operator_bitwise_or |
331 | { |
332 | public: |
333 | using range_operator::op1_range; |
334 | using range_operator::op2_range; |
335 | using range_operator::lhs_op1_relation; |
336 | bool op1_range (irange &r, tree type, |
337 | const irange &lhs, const irange &op2, |
338 | relation_trio rel = TRIO_VARYING) const final override |
339 | { |
340 | if (INTEGRAL_TYPE_P (type)) |
341 | return operator_bitwise_or::op1_range (r, type, lhs, op2, rel); |
342 | else |
343 | return op_pointer_or.op1_range (r, type, lhs, op2, rel); |
344 | } |
345 | bool op2_range (irange &r, tree type, |
346 | const irange &lhs, const irange &op1, |
347 | relation_trio rel = TRIO_VARYING) const final override |
348 | { |
349 | if (INTEGRAL_TYPE_P (type)) |
350 | return operator_bitwise_or::op2_range (r, type, lhs, op1, rel); |
351 | else |
352 | return op_pointer_or.op2_range (r, type, lhs, op1, rel); |
353 | } |
354 | void update_bitmask (irange &r, const irange &lh, |
355 | const irange &rh) const final override |
356 | { |
357 | if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ())) |
358 | operator_bitwise_or::update_bitmask (r, lh, rh); |
359 | } |
360 | |
361 | void wi_fold (irange &r, tree type, const wide_int &lh_lb, |
362 | const wide_int &lh_ub, const wide_int &rh_lb, |
363 | const wide_int &rh_ub) const final override |
364 | { |
365 | if (INTEGRAL_TYPE_P (type)) |
366 | return operator_bitwise_or::wi_fold (r, type, lh_lb, lh_ub, |
367 | rh_lb, rh_ub); |
368 | else |
369 | return op_pointer_or.wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub); |
370 | } |
371 | } op_hybrid_or; |
372 | |
373 | // Temporary class which dispatches routines to either the INT version or |
374 | // the pointer version depending on the type. Once PRANGE is a range |
375 | // class, we can remove the hybrid. |
376 | |
377 | class hybrid_min_operator : public operator_min |
378 | { |
379 | public: |
380 | void update_bitmask (irange &r, const irange &lh, |
381 | const irange &rh) const final override |
382 | { |
383 | if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ())) |
384 | operator_min::update_bitmask (r, lh, rh); |
385 | } |
386 | |
387 | void wi_fold (irange &r, tree type, const wide_int &lh_lb, |
388 | const wide_int &lh_ub, const wide_int &rh_lb, |
389 | const wide_int &rh_ub) const final override |
390 | { |
391 | if (INTEGRAL_TYPE_P (type)) |
392 | return operator_min::wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub); |
393 | else |
394 | return op_ptr_min_max.wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub); |
395 | } |
396 | } op_hybrid_min; |
397 | |
398 | class hybrid_max_operator : public operator_max |
399 | { |
400 | public: |
401 | void update_bitmask (irange &r, const irange &lh, |
402 | const irange &rh) const final override |
403 | { |
404 | if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ())) |
405 | operator_max::update_bitmask (r, lh, rh); |
406 | } |
407 | |
408 | void wi_fold (irange &r, tree type, const wide_int &lh_lb, |
409 | const wide_int &lh_ub, const wide_int &rh_lb, |
410 | const wide_int &rh_ub) const final override |
411 | { |
412 | if (INTEGRAL_TYPE_P (type)) |
413 | return operator_max::wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub); |
414 | else |
415 | return op_ptr_min_max.wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub); |
416 | } |
417 | } op_hybrid_max; |
418 | |
419 | // Initialize any pointer operators to the primary table |
420 | |
421 | void |
422 | range_op_table::initialize_pointer_ops () |
423 | { |
424 | set (code: POINTER_PLUS_EXPR, op&: op_pointer_plus); |
425 | set (code: POINTER_DIFF_EXPR, op&: op_pointer_diff); |
426 | set (code: BIT_AND_EXPR, op&: op_hybrid_and); |
427 | set (code: BIT_IOR_EXPR, op&: op_hybrid_or); |
428 | set (code: MIN_EXPR, op&: op_hybrid_min); |
429 | set (code: MAX_EXPR, op&: op_hybrid_max); |
430 | } |
431 | |