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
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
52class pointer_plus_operator : public range_operator
53{
54 using range_operator::op2_range;
55public:
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
69void
70pointer_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
112bool
113pointer_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
132class pointer_min_max_operator : public range_operator
133{
134public:
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
140void
141pointer_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
160class pointer_and_operator : public range_operator
161{
162public:
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
168void
169pointer_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
184class pointer_or_operator : public range_operator
185{
186public:
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
202bool
203pointer_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
219bool
220pointer_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
228void
229pointer_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
246class 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
257bool
258operator_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
274class hybrid_and_operator : public operator_bitwise_and
275{
276public:
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
330class hybrid_or_operator : public operator_bitwise_or
331{
332public:
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
377class hybrid_min_operator : public operator_min
378{
379public:
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
398class hybrid_max_operator : public operator_max
399{
400public:
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
421void
422range_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

source code of gcc/range-op-ptr.cc