Branch data Line data Source code
1 : : /* Code for range operators.
2 : : Copyright (C) 2017-2024 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 : 7618798 : void update_bitmask (irange &r, const irange &lh, const irange &rh) const
66 : 7618798 : { update_known_bitmask (r, POINTER_PLUS_EXPR, lh, rh); }
67 : : } op_pointer_plus;
68 : :
69 : : void
70 : 8246947 : 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 : 8260373 : if (lh_lb == 0 && lh_ub == 0 && rh_lb == rh_ub)
78 : : {
79 : 6685 : r.set (type, rh_lb, rh_lb);
80 : 6685 : 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 : 8240262 : if ((!wi_includes_zero_p (type, lh_lb, lh_ub)
100 : 4614552 : || !wi_includes_zero_p (type, rh_lb, rh_ub))
101 : 5390582 : && !TYPE_OVERFLOW_WRAPS (type)
102 : 13630548 : && (flag_delete_null_pointer_checks
103 : 1412 : || !wi::sign_mask (rh_ub)))
104 : 5389926 : r = range_nonzero (type);
105 : 2854803 : else if (lh_lb == lh_ub && lh_lb == 0
106 : 2854803 : && rh_lb == rh_ub && rh_lb == 0)
107 : 0 : r = range_zero (type);
108 : : else
109 : 2850336 : r.set_varying (type);
110 : : }
111 : :
112 : : bool
113 : 126709 : 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 : 126709 : relation_kind rel = trio.lhs_op1 ();
119 : 126709 : r.set_varying (type);
120 : :
121 : : // If the LHS and OP1 are equal, the op2 must be zero.
122 : 126709 : if (rel == VREL_EQ)
123 : 4176 : r.set_zero (type);
124 : : // If the LHS and OP1 are not equal, the offset must be non-zero.
125 : 122533 : else if (rel == VREL_NE)
126 : 6707 : 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 : 1545 : 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 : 1545 : if (!wi_includes_zero_p (type, lh_lb, lh_ub)
152 : 1545 : && !wi_includes_zero_p (type, rh_lb, rh_ub))
153 : 256 : r = range_nonzero (type);
154 : 1289 : else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
155 : 0 : r = range_zero (type);
156 : : else
157 : 1289 : r.set_varying (type);
158 : 1545 : }
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 : 752 : 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 : 752 : if (wi_zero_p (type, lh_lb, lh_ub) || wi_zero_p (type, lh_lb, lh_ub))
178 : 0 : r = range_zero (type);
179 : : else
180 : 752 : r.set_varying (type);
181 : 752 : }
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 : 0 : 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 : 0 : if (lhs.undefined_p ())
209 : : return false;
210 : 0 : if (lhs.zero_p ())
211 : : {
212 : 0 : r.set_zero (type);
213 : 0 : return true;
214 : : }
215 : 0 : r.set_varying (type);
216 : 0 : return true;
217 : : }
218 : :
219 : : bool
220 : 0 : pointer_or_operator::op2_range (irange &r, tree type,
221 : : const irange &lhs,
222 : : const irange &op1,
223 : : relation_trio) const
224 : : {
225 : 0 : return pointer_or_operator::op1_range (r, type, lhs, op1);
226 : : }
227 : :
228 : : void
229 : 0 : 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 : 0 : if (!wi_includes_zero_p (type, lh_lb, lh_ub)
238 : 0 : && !wi_includes_zero_p (type, rh_lb, rh_ub))
239 : 0 : r = range_nonzero (type);
240 : 0 : else if (wi_zero_p (type, lh_lb, lh_ub) && wi_zero_p (type, rh_lb, rh_ub))
241 : 0 : r = range_zero (type);
242 : : else
243 : 0 : r.set_varying (type);
244 : 0 : }
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 : 1609280 : void update_bitmask (irange &r, const irange &lh, const irange &rh) const
254 : 1609280 : { update_known_bitmask (r, POINTER_DIFF_EXPR, lh, rh); }
255 : : } op_pointer_diff;
256 : :
257 : : bool
258 : 1609280 : 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 : 1609280 : return minus_op1_op2_relation_effect (lhs_range, type, op1_range, op2_range,
264 : 1609280 : 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 : 2077551 : 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 : 2077551 : if (INTEGRAL_TYPE_P (type))
285 : 2077551 : return operator_bitwise_and::op1_range (r, type, lhs, op2, rel);
286 : : else
287 : : return false;
288 : : }
289 : 687503 : 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 : 687503 : if (INTEGRAL_TYPE_P (type))
294 : 687503 : return operator_bitwise_and::op2_range (r, type, lhs, op1, rel);
295 : : else
296 : : return false;
297 : : }
298 : 5680125 : relation_kind lhs_op1_relation (const irange &lhs,
299 : : const irange &op1, const irange &op2,
300 : : relation_kind rel) const final override
301 : : {
302 : 5680125 : if (!lhs.undefined_p () && INTEGRAL_TYPE_P (lhs.type ()))
303 : 5679373 : return operator_bitwise_and::lhs_op1_relation (lhs, op1, op2, rel);
304 : : else
305 : 752 : return VREL_VARYING;
306 : : }
307 : 5807832 : void update_bitmask (irange &r, const irange &lh,
308 : : const irange &rh) const final override
309 : : {
310 : 5807832 : if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ()))
311 : 5807080 : operator_bitwise_and::update_bitmask (r, lh, rh);
312 : 5807832 : }
313 : :
314 : 11846846 : 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 : 11846846 : if (INTEGRAL_TYPE_P (type))
319 : 11846094 : return operator_bitwise_and::wi_fold (r, type, lh_lb, lh_ub,
320 : 11846094 : rh_lb, rh_ub);
321 : : else
322 : 752 : 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 : 247650 : 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 : 247650 : if (INTEGRAL_TYPE_P (type))
341 : 247650 : return operator_bitwise_or::op1_range (r, type, lhs, op2, rel);
342 : : else
343 : 0 : return op_pointer_or.op1_range (r, type, lhs, op2, rel);
344 : : }
345 : 246768 : 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 : 246768 : if (INTEGRAL_TYPE_P (type))
350 : 246768 : return operator_bitwise_or::op2_range (r, type, lhs, op1, rel);
351 : : else
352 : 0 : return op_pointer_or.op2_range (r, type, lhs, op1, rel);
353 : : }
354 : 2141625 : void update_bitmask (irange &r, const irange &lh,
355 : : const irange &rh) const final override
356 : : {
357 : 2141625 : if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ()))
358 : 2141625 : operator_bitwise_or::update_bitmask (r, lh, rh);
359 : 2141625 : }
360 : :
361 : 6183788 : 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 : 6183788 : if (INTEGRAL_TYPE_P (type))
366 : 6183788 : return operator_bitwise_or::wi_fold (r, type, lh_lb, lh_ub,
367 : 6183788 : rh_lb, rh_ub);
368 : : else
369 : 0 : 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 : 567969 : void update_bitmask (irange &r, const irange &lh,
381 : : const irange &rh) const final override
382 : : {
383 : 567969 : if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ()))
384 : 567259 : operator_min::update_bitmask (r, lh, rh);
385 : 567969 : }
386 : :
387 : 727036 : 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 : 727036 : if (INTEGRAL_TYPE_P (type))
392 : 726326 : return operator_min::wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
393 : : else
394 : 710 : 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 : 493063 : void update_bitmask (irange &r, const irange &lh,
402 : : const irange &rh) const final override
403 : : {
404 : 493063 : if (!r.undefined_p () && INTEGRAL_TYPE_P (r.type ()))
405 : 492228 : operator_max::update_bitmask (r, lh, rh);
406 : 493063 : }
407 : :
408 : 584252 : 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 : 584252 : if (INTEGRAL_TYPE_P (type))
413 : 583417 : return operator_max::wi_fold (r, type, lh_lb, lh_ub, rh_lb, rh_ub);
414 : : else
415 : 835 : 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 : 284188 : range_op_table::initialize_pointer_ops ()
423 : : {
424 : 284188 : set (POINTER_PLUS_EXPR, op_pointer_plus);
425 : 284188 : set (POINTER_DIFF_EXPR, op_pointer_diff);
426 : 284188 : set (BIT_AND_EXPR, op_hybrid_and);
427 : 284188 : set (BIT_IOR_EXPR, op_hybrid_or);
428 : 284188 : set (MIN_EXPR, op_hybrid_min);
429 : 284188 : set (MAX_EXPR, op_hybrid_max);
430 : 284188 : }
|
