Line data Source code
1 : /* Code for GIMPLE range related routines.
2 : Copyright (C) 2019-2026 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 "tree.h"
28 : #include "gimple.h"
29 : #include "ssa.h"
30 : #include "gimple-pretty-print.h"
31 : #include "optabs-tree.h"
32 : #include "gimple-iterator.h"
33 : #include "gimple-fold.h"
34 : #include "wide-int.h"
35 : #include "fold-const.h"
36 : #include "case-cfn-macros.h"
37 : #include "omp-general.h"
38 : #include "cfgloop.h"
39 : #include "tree-ssa-loop.h"
40 : #include "tree-scalar-evolution.h"
41 : #include "langhooks.h"
42 : #include "vr-values.h"
43 : #include "range.h"
44 : #include "value-query.h"
45 : #include "gimple-range-op.h"
46 : #include "gimple-range.h"
47 : #include "cgraph.h"
48 : #include "alloc-pool.h"
49 : #include "symbol-summary.h"
50 : #include "ipa-utils.h"
51 : #include "sreal.h"
52 : #include "ipa-cp.h"
53 : #include "ipa-prop.h"
54 : #include "rtl.h"
55 : // Construct a fur_source, and set the m_query field.
56 :
57 533697213 : fur_source::fur_source (range_query *q)
58 : {
59 533697213 : if (q)
60 533696257 : m_query = q;
61 : else
62 1912 : m_query = get_range_query (cfun);
63 533697213 : m_depend_p = false;
64 533697213 : }
65 :
66 : // Invoke range_of_expr on EXPR.
67 :
68 : bool
69 0 : fur_source::get_operand (vrange &r, tree expr)
70 : {
71 0 : return m_query->range_of_expr (r, expr);
72 : }
73 :
74 : // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
75 : // range_query to get the range on the edge.
76 :
77 : bool
78 0 : fur_source::get_phi_operand (vrange &r, tree expr, edge e)
79 : {
80 0 : return m_query->range_on_edge (r, e, expr);
81 : }
82 :
83 : // Default is no relation.
84 :
85 : relation_kind
86 6947460 : fur_source::query_relation (tree op1 ATTRIBUTE_UNUSED,
87 : tree op2 ATTRIBUTE_UNUSED)
88 : {
89 6947460 : return VREL_VARYING;
90 : }
91 :
92 : // Default registers nothing and returns false meaning nothing changed.
93 :
94 : bool
95 27502695 : fur_source::register_relation (gimple *s ATTRIBUTE_UNUSED,
96 : relation_kind k ATTRIBUTE_UNUSED,
97 : tree op1 ATTRIBUTE_UNUSED,
98 : tree op2 ATTRIBUTE_UNUSED)
99 : {
100 27502695 : return false;
101 : }
102 :
103 : // Default registers nothing and returns false meaning nothing changed.
104 :
105 : bool
106 7490246 : fur_source::register_relation (edge e ATTRIBUTE_UNUSED,
107 : relation_kind k ATTRIBUTE_UNUSED,
108 : tree op1 ATTRIBUTE_UNUSED,
109 : tree op2 ATTRIBUTE_UNUSED)
110 : {
111 7490246 : return false;
112 : }
113 :
114 : // Get the value of EXPR on edge m_edge.
115 :
116 : bool
117 65157528 : fur_edge::get_operand (vrange &r, tree expr)
118 : {
119 65157528 : return m_query->range_on_edge (r, m_edge, expr);
120 : }
121 :
122 : // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
123 : // range_query to get the range on the edge.
124 :
125 : bool
126 0 : fur_edge::get_phi_operand (vrange &r, tree expr, edge e)
127 : {
128 : // Edge to edge recalculations not supported yet, until we sort it out.
129 0 : gcc_checking_assert (e == m_edge);
130 0 : return m_query->range_on_edge (r, e, expr);
131 : }
132 :
133 : // Instantiate a stmt based fur_source.
134 :
135 473646800 : fur_stmt::fur_stmt (gimple *s, range_query *q) : fur_source (q)
136 : {
137 473646800 : m_stmt = s;
138 473646800 : }
139 :
140 : // Retrieve range of EXPR as it occurs as a use on stmt M_STMT.
141 :
142 : bool
143 719665684 : fur_stmt::get_operand (vrange &r, tree expr)
144 : {
145 719665684 : return m_query->range_of_expr (r, expr, m_stmt);
146 : }
147 :
148 : // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
149 : // range_query to get the range on the edge.
150 :
151 : bool
152 49563939 : fur_stmt::get_phi_operand (vrange &r, tree expr, edge e)
153 : {
154 : // Pick up the range of expr from edge E.
155 49563939 : fur_edge e_src (e, m_query);
156 49563939 : return e_src.get_operand (r, expr);
157 : }
158 :
159 : // Return relation based from m_stmt.
160 :
161 : relation_kind
162 110992214 : fur_stmt::query_relation (tree op1, tree op2)
163 : {
164 110992214 : return m_query->relation ().query (m_stmt, op1, op2);
165 : }
166 :
167 : // Instantiate a stmt based fur_source with a GORI object and a ranger cache.
168 :
169 247917657 : fur_depend::fur_depend (gimple *s, range_query *q, ranger_cache *c)
170 247917657 : : fur_stmt (s, q), m_cache (c)
171 : {
172 247917657 : m_depend_p = true;
173 247917657 : }
174 :
175 : // Register a relation on a stmt if there is an oracle. Return false if
176 : // no new relation is registered.
177 :
178 : bool
179 34419937 : fur_depend::register_relation (gimple *s, relation_kind k, tree op1, tree op2)
180 : {
181 34419937 : if (!m_query->relation ().record (s, k, op1, op2))
182 : return false;
183 :
184 : // This new relation could cause different calculations, so mark the operands
185 : // with a new timestamp, forcing recalculations.
186 25768815 : if (m_cache)
187 : {
188 25768644 : m_cache->update_consumers (op1);
189 25768644 : m_cache->update_consumers (op2);
190 : }
191 : return true;
192 : }
193 :
194 : // Register a relation on an edge if there is an oracle. Return false if
195 : // no new relation is registered.
196 :
197 : bool
198 7459190 : fur_depend::register_relation (edge e, relation_kind k, tree op1, tree op2)
199 : {
200 7459190 : if (!m_query->relation ().record (e, k, op1, op2))
201 : return false;
202 :
203 : // This new relation could cause different calculations, so mark the operands
204 : // with a new timestamp, forcing recalculations.
205 7440967 : if (m_cache)
206 : {
207 7440965 : m_cache->update_consumers (op1);
208 7440965 : m_cache->update_consumers (op2);
209 : }
210 : return true;
211 : }
212 :
213 : // This version of fur_source will pick a range up from a list of ranges
214 : // supplied by the caller.
215 :
216 : class fur_list : public fur_source
217 : {
218 : public:
219 : fur_list (vrange &r1, range_query *q = NULL);
220 : fur_list (vrange &r1, vrange &r2, range_query *q = NULL);
221 : fur_list (unsigned num, vrange **list, range_query *q = NULL);
222 : virtual bool get_operand (vrange &r, tree expr) override;
223 : virtual bool get_phi_operand (vrange &r, tree expr, edge e) override;
224 : private:
225 : vrange *m_local[2];
226 : vrange **m_list;
227 : unsigned m_index;
228 : unsigned m_limit;
229 : };
230 :
231 : // One range supplied for unary operations.
232 :
233 924072 : fur_list::fur_list (vrange &r1, range_query *q) : fur_source (q)
234 : {
235 924072 : m_list = m_local;
236 924072 : m_index = 0;
237 924072 : m_limit = 1;
238 924072 : m_local[0] = &r1;
239 924072 : }
240 :
241 : // Two ranges supplied for binary operations.
242 :
243 0 : fur_list::fur_list (vrange &r1, vrange &r2, range_query *q) : fur_source (q)
244 : {
245 0 : m_list = m_local;
246 0 : m_index = 0;
247 0 : m_limit = 2;
248 0 : m_local[0] = &r1;
249 0 : m_local[1] = &r2;
250 0 : }
251 :
252 : // Arbitrary number of ranges in a vector.
253 :
254 0 : fur_list::fur_list (unsigned num, vrange **list, range_query *q)
255 0 : : fur_source (q)
256 : {
257 0 : m_list = list;
258 0 : m_index = 0;
259 0 : m_limit = num;
260 0 : }
261 :
262 : // Get the next operand from the vector, ensure types are compatible.
263 :
264 : bool
265 1840351 : fur_list::get_operand (vrange &r, tree expr)
266 : {
267 : // Do not use the vector for non-ssa-names, or if it has been emptied.
268 1840351 : if (TREE_CODE (expr) != SSA_NAME || m_index >= m_limit)
269 916279 : return m_query->range_of_expr (r, expr);
270 924072 : r = *m_list[m_index++];
271 924072 : gcc_checking_assert (range_compatible_p (TREE_TYPE (expr), r.type ()));
272 : return true;
273 : }
274 :
275 : // This will simply pick the next operand from the vector.
276 : bool
277 0 : fur_list::get_phi_operand (vrange &r, tree expr, edge e ATTRIBUTE_UNUSED)
278 : {
279 0 : return get_operand (r, expr);
280 : }
281 :
282 : // Fold stmt S into range R using R1 as the first operand.
283 :
284 : bool
285 924072 : fold_range (vrange &r, gimple *s, vrange &r1, range_query *q)
286 : {
287 924072 : fold_using_range f;
288 924072 : fur_list src (r1, q);
289 924072 : return f.fold_stmt (r, s, src);
290 : }
291 :
292 : // Fold stmt S into range R using R1 and R2 as the first two operands.
293 :
294 : bool
295 0 : fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2, range_query *q)
296 : {
297 0 : fold_using_range f;
298 0 : fur_list src (r1, r2, q);
299 0 : return f.fold_stmt (r, s, src);
300 : }
301 :
302 : // Fold stmt S into range R using NUM_ELEMENTS from VECTOR as the initial
303 : // operands encountered.
304 :
305 : bool
306 0 : fold_range (vrange &r, gimple *s, unsigned num_elements, vrange **vector,
307 : range_query *q)
308 : {
309 0 : fold_using_range f;
310 0 : fur_list src (num_elements, vector, q);
311 0 : return f.fold_stmt (r, s, src);
312 : }
313 :
314 : // Fold stmt S into range R using range query Q.
315 :
316 : bool
317 75818852 : fold_range (vrange &r, gimple *s, range_query *q)
318 : {
319 75818852 : fold_using_range f;
320 75818852 : fur_stmt src (s, q);
321 75818852 : return f.fold_stmt (r, s, src);
322 : }
323 :
324 : // Recalculate stmt S into R using range query Q as if it were on edge ON_EDGE.
325 :
326 : bool
327 9562396 : fold_range (vrange &r, gimple *s, edge on_edge, range_query *q)
328 : {
329 9562396 : fold_using_range f;
330 9562396 : fur_edge src (on_edge, q);
331 9562396 : return f.fold_stmt (r, s, src);
332 : }
333 :
334 : // Calculate op1 on statetemt S with LHS into range R using range query Q
335 : // to resolve any other operands.
336 :
337 : bool
338 0 : op1_range (vrange &r, gimple *s, const vrange &lhs, range_query *q)
339 : {
340 0 : gimple_range_op_handler handler (s);
341 0 : if (!handler)
342 : return false;
343 :
344 0 : fur_stmt src (s, q);
345 :
346 0 : tree op2_expr = handler.operand2 ();
347 0 : if (!op2_expr)
348 0 : return handler.calc_op1 (r, lhs);
349 :
350 0 : value_range op2 (TREE_TYPE (op2_expr));
351 0 : if (!src.get_operand (op2, op2_expr))
352 : return false;
353 :
354 0 : return handler.calc_op1 (r, lhs, op2);
355 0 : }
356 :
357 : // Calculate op1 on statetemt S into range R using range query Q.
358 : // LHS is set to VARYING in this case.
359 :
360 : bool
361 0 : op1_range (vrange &r, gimple *s, range_query *q)
362 : {
363 0 : tree lhs_type = gimple_range_type (s);
364 0 : if (!lhs_type)
365 : return false;
366 0 : value_range lhs_range;
367 0 : lhs_range.set_varying (lhs_type);
368 0 : return op1_range (r, s, lhs_range, q);
369 0 : }
370 :
371 : // Calculate op2 on statetemt S with LHS into range R using range query Q
372 : // to resolve any other operands.
373 :
374 : bool
375 0 : op2_range (vrange &r, gimple *s, const vrange &lhs, range_query *q)
376 : {
377 :
378 0 : gimple_range_op_handler handler (s);
379 0 : if (!handler)
380 : return false;
381 :
382 0 : fur_stmt src (s, q);
383 :
384 0 : value_range op1 (TREE_TYPE (handler.operand1 ()));
385 0 : if (!src.get_operand (op1, handler.operand1 ()))
386 : return false;
387 :
388 0 : return handler.calc_op2 (r, lhs, op1);
389 0 : }
390 :
391 : // Calculate op2 on statetemt S into range R using range query Q.
392 : // LHS is set to VARYING in this case.
393 :
394 : bool
395 0 : op2_range (vrange &r, gimple *s, range_query *q)
396 : {
397 0 : tree lhs_type = gimple_range_type (s);
398 0 : if (!lhs_type)
399 : return false;
400 0 : value_range lhs_range;
401 0 : lhs_range.set_varying (lhs_type);
402 0 : return op2_range (r, s, lhs_range, q);
403 0 : }
404 :
405 : // Provide a fur_source which can be used to determine any relations on
406 : // a statement. It manages the callback from fold_using_ranges to determine
407 : // a relation_trio for a statement.
408 :
409 : class fur_relation : public fur_stmt
410 : {
411 : public:
412 : fur_relation (gimple *s, range_query *q = NULL);
413 : virtual bool register_relation (gimple *stmt, relation_kind k, tree op1,
414 : tree op2);
415 : virtual bool register_relation (edge e, relation_kind k, tree op1,
416 : tree op2);
417 : relation_trio trio() const;
418 : private:
419 : relation_kind def_op1, def_op2, op1_op2;
420 : };
421 :
422 1108031 : fur_relation::fur_relation (gimple *s, range_query *q) : fur_stmt (s, q)
423 : {
424 1108031 : def_op1 = def_op2 = op1_op2 = VREL_VARYING;
425 1108031 : }
426 :
427 : // Construct a trio from what is known.
428 :
429 : relation_trio
430 1108031 : fur_relation::trio () const
431 : {
432 1108031 : return relation_trio (def_op1, def_op2, op1_op2);
433 : }
434 :
435 : // Don't support edges, but avoid a compiler warning by providing the routine.
436 : // Return false indicating nothing has changed.
437 :
438 : bool
439 0 : fur_relation::register_relation (edge, relation_kind, tree, tree)
440 : {
441 0 : return false;
442 : }
443 :
444 : // Register relation K between OP1 and OP2 on STMT. Return false if there
445 : // is no relation.
446 :
447 : bool
448 1089225 : fur_relation::register_relation (gimple *stmt, relation_kind k, tree op1,
449 : tree op2)
450 : {
451 1089225 : tree lhs = gimple_get_lhs (stmt);
452 1089225 : tree a1 = NULL_TREE;
453 1089225 : tree a2 = NULL_TREE;
454 1089225 : switch (gimple_code (stmt))
455 : {
456 0 : case GIMPLE_COND:
457 0 : a1 = gimple_cond_lhs (stmt);
458 0 : a2 = gimple_cond_rhs (stmt);
459 0 : break;
460 1089225 : case GIMPLE_ASSIGN:
461 1089225 : a1 = gimple_assign_rhs1 (stmt);
462 1089225 : if (gimple_num_ops (stmt) >= 3)
463 1089225 : a2 = gimple_assign_rhs2 (stmt);
464 : break;
465 : default:
466 : break;
467 : }
468 : // STMT is of the form LHS = A1 op A2, now map the relation to these
469 : // operands, if possible.
470 1089225 : if (op1 == lhs)
471 : {
472 1089225 : if (op2 == a1)
473 1089225 : def_op1 = k;
474 0 : else if (op2 == a2)
475 0 : def_op2 = k;
476 : }
477 0 : else if (op2 == lhs)
478 : {
479 0 : if (op1 == a1)
480 0 : def_op1 = relation_swap (k);
481 0 : else if (op1 == a2)
482 0 : def_op2 = relation_swap (k);
483 : }
484 : else
485 : {
486 0 : if (op1 == a1 && op2 == a2)
487 0 : op1_op2 = k;
488 0 : else if (op2 == a1 && op1 == a2)
489 0 : op1_op2 = relation_swap (k);
490 : }
491 0 : return def_op1 == VREL_VARYING && def_op2 == VREL_VARYING
492 1089225 : && op1_op2 == VREL_VARYING;
493 : }
494 :
495 : // Return the relation trio for stmt S using query Q.
496 :
497 : relation_trio
498 1108031 : fold_relations (gimple *s, range_query *q)
499 : {
500 1108031 : fold_using_range f;
501 1108031 : fur_relation src (s, q);
502 1108031 : tree lhs = gimple_range_ssa_p (gimple_get_lhs (s));
503 1108031 : if (lhs)
504 : {
505 1108031 : value_range vr(TREE_TYPE (lhs));
506 1108031 : if (f.fold_stmt (vr, s, src))
507 1108031 : return src.trio ();
508 1108031 : }
509 0 : return TRIO_VARYING;
510 : }
511 :
512 : // -------------------------------------------------------------------------
513 :
514 : // Adjust the range for a pointer difference where the operands came
515 : // from a memchr.
516 : //
517 : // This notices the following sequence:
518 : //
519 : // def = __builtin_memchr (arg, 0, sz)
520 : // n = def - arg
521 : //
522 : // The range for N can be narrowed to [0, PTRDIFF_MAX - 1].
523 :
524 : static void
525 3193818 : adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt)
526 : {
527 3193818 : tree op0 = gimple_assign_rhs1 (diff_stmt);
528 3193818 : tree op1 = gimple_assign_rhs2 (diff_stmt);
529 3193818 : tree op0_ptype = TREE_TYPE (TREE_TYPE (op0));
530 3193818 : tree op1_ptype = TREE_TYPE (TREE_TYPE (op1));
531 3193818 : gimple *call;
532 :
533 3193818 : if (TREE_CODE (op0) == SSA_NAME
534 3160275 : && TREE_CODE (op1) == SSA_NAME
535 3113389 : && (call = SSA_NAME_DEF_STMT (op0))
536 3113389 : && is_gimple_call (call)
537 89301 : && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
538 67821 : && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node)
539 67570 : && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node)
540 67570 : && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node)
541 66992 : && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node)
542 66992 : && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
543 66992 : && vrp_operand_equal_p (op1, gimple_call_arg (call, 0))
544 3239695 : && integer_zerop (gimple_call_arg (call, 1)))
545 : {
546 26 : wide_int maxm1 = irange_val_max (ptrdiff_type_node) - 1;
547 26 : res.intersect (int_range<2> (ptrdiff_type_node,
548 52 : wi::zero (TYPE_PRECISION (ptrdiff_type_node)),
549 26 : maxm1));
550 26 : }
551 3193818 : }
552 :
553 : // Adjust the range for an IMAGPART_EXPR.
554 :
555 : static void
556 987099 : adjust_imagpart_expr (vrange &res, const gimple *stmt)
557 : {
558 987099 : tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
559 :
560 987099 : if (TREE_CODE (name) != SSA_NAME || !SSA_NAME_DEF_STMT (name))
561 : return;
562 :
563 857869 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
564 857869 : if (is_gimple_call (def_stmt) && gimple_call_internal_p (def_stmt))
565 : {
566 407353 : switch (gimple_call_internal_fn (def_stmt))
567 : {
568 389413 : case IFN_ADD_OVERFLOW:
569 389413 : case IFN_SUB_OVERFLOW:
570 389413 : case IFN_MUL_OVERFLOW:
571 389413 : case IFN_UADDC:
572 389413 : case IFN_USUBC:
573 389413 : case IFN_ATOMIC_COMPARE_EXCHANGE:
574 389413 : {
575 389413 : int_range<2> r;
576 389413 : r.set_varying (boolean_type_node);
577 389413 : tree type = TREE_TYPE (gimple_assign_lhs (stmt));
578 389413 : range_cast (r, type);
579 389413 : res.intersect (r);
580 389413 : }
581 : default:
582 : break;
583 : }
584 : return;
585 : }
586 450516 : if (is_gimple_assign (def_stmt)
587 450516 : && gimple_assign_rhs_code (def_stmt) == COMPLEX_CST)
588 : {
589 19 : tree cst = gimple_assign_rhs1 (def_stmt);
590 19 : if (TREE_CODE (cst) == COMPLEX_CST
591 19 : && TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) == INTEGER_TYPE)
592 : {
593 8 : wide_int w = wi::to_wide (TREE_IMAGPART (cst));
594 8 : int_range<1> imag (TREE_TYPE (TREE_IMAGPART (cst)), w, w);
595 8 : res.intersect (imag);
596 8 : }
597 : }
598 : }
599 :
600 : // Adjust the range for a REALPART_EXPR.
601 :
602 : static void
603 939580 : adjust_realpart_expr (vrange &res, const gimple *stmt)
604 : {
605 939580 : tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
606 :
607 939580 : if (TREE_CODE (name) != SSA_NAME)
608 : return;
609 :
610 802608 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
611 802608 : if (!SSA_NAME_DEF_STMT (name))
612 : return;
613 :
614 802608 : if (is_gimple_assign (def_stmt)
615 802608 : && gimple_assign_rhs_code (def_stmt) == COMPLEX_CST)
616 : {
617 10 : tree cst = gimple_assign_rhs1 (def_stmt);
618 10 : if (TREE_CODE (cst) == COMPLEX_CST
619 10 : && TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) == INTEGER_TYPE)
620 : {
621 0 : wide_int imag = wi::to_wide (TREE_REALPART (cst));
622 0 : int_range<2> tmp (TREE_TYPE (TREE_REALPART (cst)), imag, imag);
623 0 : res.intersect (tmp);
624 0 : }
625 : }
626 : }
627 :
628 : // This function looks for situations when walking the use/def chains
629 : // may provide additional contextual range information not exposed on
630 : // this statement.
631 :
632 : static void
633 199999849 : gimple_range_adjustment (vrange &res, const gimple *stmt)
634 : {
635 199999849 : switch (gimple_expr_code (stmt))
636 : {
637 3193818 : case POINTER_DIFF_EXPR:
638 3193818 : adjust_pointer_diff_expr (as_a <irange> (res), stmt);
639 3193818 : return;
640 :
641 987099 : case IMAGPART_EXPR:
642 987099 : adjust_imagpart_expr (res, stmt);
643 987099 : return;
644 :
645 939580 : case REALPART_EXPR:
646 939580 : adjust_realpart_expr (res, stmt);
647 939580 : return;
648 :
649 : default:
650 : break;
651 : }
652 : }
653 :
654 : // Provide context to the gimple fold callback.
655 :
656 : static struct
657 : {
658 : gimple *m_stmt;
659 : range_query *m_query;
660 : } x_fold_context;
661 :
662 : // Gimple fold callback.
663 :
664 : static tree
665 91621260 : pta_valueize (tree name)
666 : {
667 91621260 : tree ret
668 91621260 : = x_fold_context.m_query->value_of_expr (name, x_fold_context.m_stmt);
669 :
670 91621260 : return ret ? ret : name;
671 : }
672 :
673 : // Calculate a range for statement S and return it in R. If NAME is provided it
674 : // represents the SSA_NAME on the LHS of the statement. It is only required
675 : // if there is more than one lhs/output. If a range cannot
676 : // be calculated, return false.
677 :
678 : bool
679 311363054 : fold_using_range::fold_stmt (vrange &r, gimple *s, fur_source &src, tree name)
680 : {
681 311363054 : bool res = false;
682 : // If name and S are specified, make sure it is an LHS of S.
683 311363054 : gcc_checking_assert (!name || !gimple_get_lhs (s) ||
684 : name == gimple_get_lhs (s));
685 :
686 : if (!name)
687 167250803 : name = gimple_get_lhs (s);
688 :
689 : // Process addresses and loads from static constructors.
690 311363054 : if (gimple_code (s) == GIMPLE_ASSIGN && range_from_readonly_var (r, s, src))
691 : return true;
692 :
693 : // Save the current range query and restore it before returning.
694 : // If the specified query is different, make it the current one.
695 : // PR 125854 - The fold machinery may make a query call.
696 : // PR 126814 - tree_expr_nonnegative_p may make a call.
697 : // PR 126942 - path_ranger queries should never be the current query.
698 : // set_range_query will revert to a global query for this.
699 311233461 : range_query *saved_query = set_range_query (cfun, src.query ());
700 :
701 311233461 : gimple_range_op_handler handler (s);
702 311233461 : if (gimple_code (s) == GIMPLE_ASSIGN
703 311233461 : && gimple_assign_rhs_code (s) == ADDR_EXPR)
704 3746032 : res = range_of_address (as_a <prange> (r), s, src);
705 307487429 : else if (handler)
706 200022931 : res = range_of_range_op (r, handler, src);
707 107464498 : else if (is_a<gphi *>(s))
708 24325895 : res = range_of_phi (r, as_a<gphi *> (s), src);
709 83138603 : else if (is_a<gcall *>(s))
710 13435524 : res = range_of_call (r, as_a<gcall *> (s), src);
711 69703079 : else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
712 183453 : res = range_of_cond_expr (r, as_a<gassign *> (s), src);
713 :
714 : // If the result is varying, use the type's min/max if either is not
715 : // the same as the full precision min/max. This helps with strict enum
716 : // e.g. `g++.dg/warn/pr33738.C`.
717 241713835 : if (res && r.varying_p () && INTEGRAL_TYPE_P (r.type ()))
718 : {
719 122287204 : irange &ir = as_a <irange> (r);
720 122287204 : tree type = r.type ();
721 122287204 : auto typemax = wi::to_wide (TYPE_MAX_VALUE (type));
722 122287204 : auto typemin = wi::to_wide (TYPE_MIN_VALUE (type));
723 122287204 : auto precisionmax = wi::max_value (TYPE_PRECISION (type),
724 244574408 : TYPE_SIGN (type));
725 122287204 : auto precisionmin = wi::min_value (TYPE_PRECISION (type),
726 244574408 : TYPE_SIGN (type));
727 244502660 : if (typemax != precisionmax || typemin != precisionmin)
728 71748 : ir.set (type, typemin, typemax);
729 122288165 : }
730 :
731 311233461 : if (!res)
732 : {
733 : // Restore the original query.
734 69519626 : if (saved_query)
735 14792970 : set_range_query (cfun, saved_query);
736 : // If no name specified or range is unsupported, bail.
737 69519626 : if (!name || !gimple_range_ssa_p (name))
738 : return false;
739 : // We don't understand the stmt, so return the global range.
740 69469220 : gimple_range_global (r, name);
741 69469220 : return true;
742 : }
743 :
744 241713835 : if (r.undefined_p ())
745 : {
746 : // Restore the original query.
747 62621 : if (saved_query)
748 1565 : set_range_query (cfun, saved_query);
749 : return true;
750 : }
751 :
752 : // We sometimes get compatible types copied from operands, make sure
753 : // the correct type is being returned.
754 241651214 : if (name && TREE_TYPE (name) != r.type ())
755 : {
756 3666256 : gcc_checking_assert (range_compatible_p (r.type (), TREE_TYPE (name)));
757 3666256 : range_cast (r, TREE_TYPE (name));
758 : }
759 :
760 241651214 : if (is_a <prange> (r))
761 : {
762 26724092 : prange &p = as_a <prange> (r);
763 : // Check to see if points_to should be set.
764 26724092 : if (p.addr_unknown_p () && name && gimple_code (s) == GIMPLE_ASSIGN)
765 : {
766 16076706 : tree rhs = gimple_assign_rhs1 (s);
767 16076706 : tree_code code = gimple_assign_rhs_code (s);
768 : // If code is SSA_NAME, any points to would already be copied.
769 16076706 : if (code != SSA_NAME
770 14090723 : && get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
771 20057682 : && TREE_CODE (rhs) == ADDR_EXPR)
772 3743759 : p.set_addr (rhs, true);
773 : else
774 : {
775 : // If we couldn't find anything, try fold.
776 12332947 : x_fold_context = { s, get_range_query (cfun) };
777 12332947 : rhs = gimple_fold_stmt_to_constant_1 (s, pta_valueize,
778 : pta_valueize);
779 12332947 : if (rhs && TREE_CODE (rhs) == ADDR_EXPR)
780 23570 : p.set_addr (rhs, true);
781 : }
782 : }
783 : }
784 : // Restore the original query.
785 241651214 : if (saved_query)
786 57020193 : set_range_query (cfun, saved_query);
787 : return true;
788 : }
789 :
790 : // Calculate a range for range_op statement S and return it in R. If any
791 : // If a range cannot be calculated, return false.
792 :
793 : bool
794 200022931 : fold_using_range::range_of_range_op (vrange &r,
795 : gimple_range_op_handler &handler,
796 : fur_source &src)
797 : {
798 200022931 : gcc_checking_assert (handler);
799 200022931 : gimple *s = handler.stmt ();
800 200022931 : tree type = gimple_range_type (s);
801 200022931 : if (!type)
802 : return false;
803 :
804 200022931 : tree lhs = handler.lhs ();
805 200022931 : tree op1 = handler.operand1 ();
806 200022931 : tree op2 = handler.operand2 ();
807 :
808 : // Certain types of builtin functions may have no arguments.
809 200022931 : if (!op1)
810 : {
811 23082 : value_range r1 (type);
812 23082 : if (!handler.fold_range (r, type, r1, r1))
813 0 : r.set_varying (type);
814 23082 : return true;
815 23082 : }
816 :
817 199999849 : value_range range1 (TREE_TYPE (op1));
818 199999849 : value_range range2 (op2 ? TREE_TYPE (op2) : TREE_TYPE (op1));
819 :
820 199999849 : if (src.get_operand (range1, op1))
821 : {
822 199999849 : if (!op2)
823 : {
824 : // Fold range, and register any dependency if available.
825 42114667 : value_range r2 (type);
826 42114667 : r2.set_varying (type);
827 42114667 : if (!handler.fold_range (r, type, range1, r2))
828 328760 : r.set_varying (type);
829 42114667 : if (lhs && gimple_range_ssa_p (op1))
830 : {
831 61002221 : if (src.gori_ssa ())
832 22897115 : src.gori_ssa ()->register_dependency (lhs, op1);
833 38105073 : relation_kind rel;
834 38105073 : rel = handler.lhs_op1_relation (r, range1, range1);
835 38105073 : if (rel != VREL_VARYING)
836 28436650 : src.register_relation (s, rel, lhs, op1);
837 : }
838 42114667 : }
839 157885182 : else if (src.get_operand (range2, op2))
840 : {
841 157885182 : relation_kind rel = src.query_relation (op1, op2);
842 157885182 : if (dump_file && (dump_flags & TDF_DETAILS) && rel != VREL_VARYING)
843 : {
844 160 : fprintf (dump_file, " folding with relation ");
845 160 : print_generic_expr (dump_file, op1, TDF_SLIM);
846 160 : print_relation (dump_file, rel);
847 160 : print_generic_expr (dump_file, op2, TDF_SLIM);
848 160 : fputc ('\n', dump_file);
849 : }
850 : // Fold range, and register any dependency if available.
851 157885182 : if (!handler.fold_range (r, type, range1, range2,
852 : relation_trio::op1_op2 (rel)))
853 261 : r.set_varying (type);
854 157885182 : if (irange::supports_p (type))
855 145001662 : relation_fold_and_or (as_a <irange> (r), s, src, range1, range2);
856 157885182 : if (lhs)
857 : {
858 160745936 : if (src.gori_ssa ())
859 : {
860 62237411 : src.gori_ssa ()->register_dependency (lhs, op1);
861 124474822 : src.gori_ssa ()->register_dependency (lhs, op2);
862 : }
863 98508192 : if (gimple_range_ssa_p (op1))
864 : {
865 95845814 : relation_kind rel2 = handler.lhs_op1_relation (r, range1,
866 95845814 : range2, rel);
867 95845814 : if (rel2 != VREL_VARYING)
868 41234366 : src.register_relation (s, rel2, lhs, op1);
869 : }
870 98508192 : if (gimple_range_ssa_p (op2))
871 : {
872 39238188 : relation_kind rel2 = handler.lhs_op2_relation (r, range1,
873 39238188 : range2, rel);
874 39238188 : if (rel2 != VREL_VARYING)
875 2587448 : src.register_relation (s, rel2, lhs, op2);
876 : }
877 : }
878 : // Check for an existing BB, as we maybe asked to fold an
879 : // artificial statement not in the CFG.
880 59376990 : else if (is_a<gcond *> (s) && gimple_bb (s))
881 : {
882 50668074 : basic_block bb = gimple_bb (s);
883 50668074 : edge e0 = EDGE_SUCC (bb, 0);
884 : /* During RTL expansion one of the edges can be removed
885 : if expansion proves the jump is unconditional. */
886 50668074 : edge e1 = single_succ_p (bb) ? NULL : EDGE_SUCC (bb, 1);
887 :
888 50668074 : gcc_checking_assert (e1 || currently_expanding_to_rtl);
889 50668074 : if (!single_pred_p (e0->dest))
890 12263463 : e0 = NULL;
891 50668074 : if (e1 && !single_pred_p (e1->dest))
892 : e1 = NULL;
893 50668074 : src.register_outgoing_edges (as_a<gcond *> (s),
894 : as_a <irange> (r), e0, e1);
895 : }
896 : }
897 : else
898 0 : r.set_varying (type);
899 : }
900 : else
901 0 : r.set_varying (type);
902 : // Make certain range-op adjustments that aren't handled any other way.
903 199999849 : gimple_range_adjustment (r, s);
904 199999849 : return true;
905 199999849 : }
906 :
907 : // Calculate the range of an assignment containing an ADDR_EXPR.
908 : // Return the range in R.
909 : // If a range cannot be calculated, set it to VARYING and return true.
910 :
911 : bool
912 3746032 : fold_using_range::range_of_address (prange &r, gimple *stmt, fur_source &src)
913 : {
914 3746032 : gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
915 3746032 : gcc_checking_assert (gimple_assign_rhs_code (stmt) == ADDR_EXPR);
916 :
917 3746032 : tree expr = gimple_assign_rhs1 (stmt);
918 3746032 : poly_int64 bitsize, bitpos;
919 3746032 : tree offset;
920 3746032 : machine_mode mode;
921 3746032 : int unsignedp, reversep, volatilep;
922 3746032 : tree base = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize,
923 : &bitpos, &offset, &mode, &unsignedp,
924 : &reversep, &volatilep);
925 :
926 :
927 3746032 : if (base != NULL_TREE
928 3746032 : && TREE_CODE (base) == MEM_REF
929 7275825 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
930 : {
931 3529732 : tree ssa = TREE_OPERAND (base, 0);
932 3529732 : tree lhs = gimple_get_lhs (stmt);
933 6036254 : if (lhs && gimple_range_ssa_p (ssa) && src.gori_ssa ())
934 2506522 : src.gori_ssa ()->register_dependency (lhs, ssa);
935 3529732 : src.get_operand (r, ssa);
936 3529732 : range_cast (r, TREE_TYPE (gimple_assign_rhs1 (stmt)));
937 :
938 3529732 : poly_offset_int off = 0;
939 3529732 : bool off_cst = false;
940 3529732 : if (offset == NULL_TREE || TREE_CODE (offset) == INTEGER_CST)
941 : {
942 3444742 : off = mem_ref_offset (base);
943 3444742 : if (offset)
944 48 : off += poly_offset_int::from (wi::to_poly_wide (offset),
945 48 : SIGNED);
946 3444742 : off <<= LOG2_BITS_PER_UNIT;
947 3444742 : off += bitpos;
948 : off_cst = true;
949 : }
950 : /* If &X->a is equal to X, the range of X is the result. */
951 3444742 : if (off_cst && known_eq (off, 0))
952 1264394 : return true;
953 2265338 : else if (flag_delete_null_pointer_checks
954 2265338 : && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)))
955 : {
956 : /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
957 : allow going from non-NULL pointer to NULL. */
958 2263867 : if (r.undefined_p ()
959 4527734 : || !r.contains_p (wi::zero (TYPE_PRECISION (TREE_TYPE (expr)))))
960 : {
961 : /* We could here instead adjust r by off >> LOG2_BITS_PER_UNIT
962 : using POINTER_PLUS_EXPR if off_cst and just fall back to
963 : this. */
964 1637306 : r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
965 1637306 : return true;
966 : }
967 : }
968 : /* If MEM_REF has a "positive" offset, consider it non-NULL
969 : always, for -fdelete-null-pointer-checks also "negative"
970 : ones. Punt for unknown offsets (e.g. variable ones). */
971 628032 : if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))
972 627816 : && off_cst
973 564761 : && known_ne (off, 0)
974 1192793 : && (flag_delete_null_pointer_checks || known_gt (off, 0)))
975 : {
976 564761 : r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
977 564761 : return true;
978 : }
979 63271 : r.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt)));
980 63271 : return true;
981 : }
982 :
983 : // Handle "= &a".
984 216300 : if (tree_single_nonzero_p (expr))
985 : {
986 215195 : r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
987 215195 : return true;
988 : }
989 :
990 : // Otherwise return varying.
991 1105 : r.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt)));
992 1105 : return true;
993 : }
994 :
995 : // Does R contain anything in [LO, HI]?
996 :
997 : static bool
998 88 : intersects_p (const irange &r, const wide_int &lo, const wide_int &hi)
999 : {
1000 88 : int_range_max tmp (r);
1001 88 : tmp.intersect (int_range<1> (r.type (), lo, hi));
1002 88 : return !tmp.undefined_p ();
1003 88 : }
1004 :
1005 : // The range of a load from a read-only aggregate: walk its initializer along
1006 : // the component path of the reference, COMPONENT_PATH, from the aggregate out,
1007 : // unioning into R the constants the load can reach. For example:
1008 : //
1009 : // static const struct { int a, b[2]; } tbl[2] = { { 1, { 2, 3 } },
1010 : // { 4, { 5, 6 } } };
1011 : // ... = tbl[i].b[1];
1012 : //
1013 : // COMPONENT_PATH is { tbl[i], tbl[i].b, tbl[i].b[1] } and R is [3, 3][6, 6].
1014 : // The methods return false when a range cannot be determined.
1015 :
1016 : class ctor_ref_range
1017 : {
1018 : public:
1019 131494 : ctor_ref_range (vrange &r, tree type, const vec<tree> &component_path,
1020 : fur_source &src)
1021 131494 : : m_r (r), m_type (type), m_component_path (component_path),
1022 131494 : m_src (src) { }
1023 : bool accumulate_range (tree init, unsigned i);
1024 : private:
1025 : bool accumulate_range_from_scalar (tree init);
1026 : bool accumulate_range_from_component_ref (tree init, unsigned i, tree fld);
1027 : bool accumulate_range_from_array_ref (tree init, unsigned i, tree idx);
1028 : void accumulate_range_from_missing_constructor_elt ();
1029 :
1030 : vrange &m_r;
1031 : tree m_type;
1032 : const vec<tree> &m_component_path;
1033 : fur_source &m_src;
1034 : };
1035 :
1036 : // Accumulate the range of the load from INIT, the initializer reached after
1037 : // I steps of the component path.
1038 :
1039 : bool
1040 891942 : ctor_ref_range::accumulate_range (tree init, unsigned i)
1041 : {
1042 1783884 : if (i == m_component_path.length ())
1043 739743 : return accumulate_range_from_scalar (init);
1044 152199 : if (TREE_CODE (init) != CONSTRUCTOR && TREE_CODE (init) != STRING_CST)
1045 : return false;
1046 :
1047 152199 : tree ref = m_component_path[i];
1048 152199 : if (TREE_CODE (ref) == COMPONENT_REF)
1049 14266 : return accumulate_range_from_component_ref (init, i + 1,
1050 28532 : TREE_OPERAND (ref, 1));
1051 :
1052 137933 : gcc_assert (TREE_CODE (ref) == ARRAY_REF);
1053 137933 : return accumulate_range_from_array_ref (init, i + 1, TREE_OPERAND (ref, 1));
1054 : }
1055 :
1056 : // Accumulate the range from the scalar INIT at the end of the component path.
1057 : // For example, for t[1] with static const int t[2] = { 4, 5 }, INIT is 5 and
1058 : // the range is [5, 5].
1059 :
1060 : bool
1061 739743 : ctor_ref_range::accumulate_range_from_scalar (tree init)
1062 : {
1063 739743 : if (!useless_type_conversion_p (m_type, TREE_TYPE (init)))
1064 : return false;
1065 :
1066 739743 : if (POINTER_TYPE_P (m_type))
1067 : {
1068 173086 : prange elt;
1069 173086 : if (integer_zerop (init))
1070 102 : elt.set_zero (m_type);
1071 172984 : else if (tree_single_nonzero_p (init))
1072 172956 : elt.set_nonzero (m_type);
1073 : else
1074 : return false;
1075 173058 : m_r.union_ (elt);
1076 173058 : return true;
1077 173086 : }
1078 :
1079 566657 : if (TREE_CODE (init) == REAL_CST)
1080 : {
1081 67088 : const REAL_VALUE_TYPE *rv = TREE_REAL_CST_PTR (init);
1082 67088 : frange elt;
1083 67088 : if (real_isnan (rv))
1084 680 : elt.set_nan (m_type, real_isneg (rv));
1085 : else
1086 66408 : elt.set (m_type, *rv, *rv, nan_state (false));
1087 67088 : m_r.union_ (elt);
1088 67088 : return true;
1089 67088 : }
1090 :
1091 499569 : if (TREE_CODE (init) != INTEGER_CST)
1092 : return false;
1093 :
1094 499498 : wide_int wi_cst = wi::to_wide (init);
1095 499498 : m_r.union_ (int_range<1> (m_type, wi_cst, wi_cst));
1096 499498 : return true;
1097 499498 : }
1098 :
1099 : // Accumulate the range from field FLD of the record or union initializer
1100 : // INIT. FLD is the field of a COMPONENT_REF in the component path and I the
1101 : // step after it. For example, when walking s.b in:
1102 : //
1103 : // static const struct { int a, b; } s = { 1, 2 };
1104 : //
1105 : // INIT is { 1, 2 }, FLD is b, and I is 1, the end of the path, and the range
1106 : // is [2, 2].
1107 :
1108 : bool
1109 14266 : ctor_ref_range::accumulate_range_from_component_ref (tree init, unsigned i,
1110 : tree fld)
1111 : {
1112 14266 : unsigned ix;
1113 14266 : tree index, val;
1114 14266 : if (TREE_CODE (init) != CONSTRUCTOR)
1115 : return false;
1116 14266 : if (TYPE_MAIN_VARIANT (TREE_TYPE (init)) == DECL_CONTEXT (fld))
1117 22475 : FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init), ix, index, val)
1118 : {
1119 22424 : if (index != fld)
1120 8275 : continue;
1121 14149 : return accumulate_range (val, i);
1122 : }
1123 66 : else if (TYPE_CANONICAL (TYPE_MAIN_VARIANT (TREE_TYPE (init)))
1124 66 : == TYPE_CANONICAL (DECL_CONTEXT (fld)))
1125 : {
1126 : // If fld is from a different record/union than the CONSTRUCTOR,
1127 : // fallback to bit offset/size comparison. This happens e.g.
1128 : // with C++ pointer-to-members, where we can get different
1129 : // __ptrmemfunc_type RECORD_TYPEs with __pfn and __delta
1130 : // FIELD_DECLs at the same offsets.
1131 66 : tree off = bit_position (fld);
1132 66 : tree sz = DECL_SIZE (fld);
1133 66 : if (TREE_CODE (off) != INTEGER_CST
1134 66 : || TREE_CODE (sz) != INTEGER_CST
1135 132 : || int_size_in_bytes (TREE_TYPE (init)) == -1)
1136 66 : return false;
1137 66 : offset_int woff = wi::to_offset (off);
1138 66 : offset_int wsz = wi::to_offset (sz);
1139 80 : FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init), ix, index, val)
1140 : {
1141 80 : off = bit_position (index);
1142 80 : sz = DECL_SIZE (index);
1143 80 : if (TREE_CODE (off) != INTEGER_CST || TREE_CODE (sz) != INTEGER_CST)
1144 : return false;
1145 146 : if (wi::to_offset (off) != woff || wi::to_offset (sz) != wsz)
1146 14 : continue;
1147 66 : return accumulate_range (val, i);
1148 : }
1149 : }
1150 : else
1151 : return false;
1152 51 : if (TREE_CODE (TREE_TYPE (init)) == RECORD_TYPE)
1153 : {
1154 9 : accumulate_range_from_missing_constructor_elt ();
1155 9 : return true;
1156 : }
1157 : else
1158 : /* Missing constructor of a union field just isn't like other missing
1159 : constructor parts. */
1160 : return false;
1161 : }
1162 :
1163 : // Accumulate the range from the element at IDX of the array initializer INIT,
1164 : // or from every element when IDX is not a constant. IDX is the index of an
1165 : // ARRAY_REF in the component path and I the step after it. For example,
1166 : // when walking t[1] or t[n] in:
1167 : //
1168 : // static const int t[2] = { 4, 5 };
1169 : //
1170 : // INIT is { 4, 5 } and I is 1, the end of the path. For t[1] the range is
1171 : // [5, 5] and for t[n] it is [4, 5]. When every element is loaded, whatever
1172 : // the initializer leaves out reads as zero: take each element's indices out
1173 : // of the domain to see if anything is left.
1174 :
1175 : bool
1176 137933 : ctor_ref_range::accumulate_range_from_array_ref (tree init, unsigned i,
1177 : tree idx)
1178 : {
1179 137933 : tree domain = TYPE_DOMAIN (TREE_TYPE (init));
1180 137933 : if (!TYPE_MIN_VALUE (domain)
1181 137933 : || !TYPE_MAX_VALUE (domain)
1182 137933 : || !tree_fits_uhwi_p (TYPE_MIN_VALUE (domain))
1183 275866 : || !tree_fits_uhwi_p (TYPE_MAX_VALUE (domain)))
1184 : return false;
1185 :
1186 : // Unsigned bounds that look reversed are signed, as they are for
1187 : // get_array_ctor_element_at_index: Ada's -1 .. 5 has a lower bound of
1188 : // SIZE_MAX.
1189 137792 : tree type = TREE_TYPE (TYPE_MIN_VALUE (domain));
1190 137792 : if (TYPE_UNSIGNED (type)
1191 137792 : && tree_int_cst_lt (TYPE_MAX_VALUE (domain), TYPE_MIN_VALUE (domain)))
1192 0 : type = signed_type_for (type);
1193 137792 : wide_int min = wi::to_wide (TYPE_MIN_VALUE (domain));
1194 137792 : wide_int max = wi::to_wide (TYPE_MAX_VALUE (domain));
1195 :
1196 : // Ada represents an empty array with reversed bounds.
1197 137792 : if (wi::gt_p (min, max, TYPE_SIGN (type)))
1198 : return true;
1199 :
1200 137792 : unsigned prec = TYPE_PRECISION (type);
1201 137792 : int_range<1> domain_r (type, min, max);
1202 :
1203 : // Narrow IDX to the ranges it can actually take.
1204 137792 : int_range_max idx_r;
1205 137792 : m_src.get_operand (idx_r, idx);
1206 137792 : range_cast (idx_r, type);
1207 137792 : idx_r.intersect (domain_r);
1208 137792 : if (idx_r.undefined_p ())
1209 : return false;
1210 :
1211 137788 : int_range_max missing (idx_r);
1212 137788 : wide_int next = domain_r.lower_bound ();
1213 137788 : unsigned ix;
1214 137788 : tree index, val;
1215 :
1216 137788 : if (TREE_CODE (init) == STRING_CST)
1217 : {
1218 14785 : if (i != m_component_path.length ()
1219 14785 : || !INTEGRAL_TYPE_P (m_type)
1220 14785 : || TYPE_PRECISION (m_type) != CHAR_BIT
1221 14670 : || !useless_type_conversion_p (m_type, TREE_TYPE (TREE_TYPE (init)))
1222 44240 : || wi::gtu_p (max + 1 - min, TREE_STRING_LENGTH (init)))
1223 : return false;
1224 28923 : for (unsigned j = 0; j < idx_r.num_pairs (); ++j)
1225 : {
1226 14469 : wide_int l = idx_r.lower_bound (j);
1227 14469 : wide_int u = idx_r.upper_bound (j);
1228 14469 : if (wi::lt_p (u, min, TYPE_SIGN (type))
1229 14469 : || wi::gt_p (l, max, TYPE_SIGN (type)))
1230 0 : continue;
1231 14469 : l = wi::max (l, min, TYPE_SIGN (type));
1232 14469 : u = wi::min (u, max, TYPE_SIGN (type));
1233 14469 : unsigned n = (l - min).to_uhwi ();
1234 14469 : unsigned e = (u - min).to_uhwi ();
1235 : /* Note, if we'd have more than 256 iterations of the loops
1236 : below or even across all the outer loop iterations, it might
1237 : be more efficient to have a 256 bools array or 256-bit bitmask,
1238 : gather which bytes are seen and then union_ those which were
1239 : seen. Given the current param limits this can't ever happen. */
1240 14469 : wide_int wi_cst;
1241 14469 : if (TYPE_UNSIGNED (m_type))
1242 10567 : for (; n <= e; ++n)
1243 : {
1244 7229 : wi_cst
1245 7229 : = wi::uhwi ((unsigned char) TREE_STRING_POINTER (init)[n],
1246 7229 : CHAR_BIT);
1247 7229 : m_r.union_ (int_range<1> (m_type, wi_cst, wi_cst));
1248 : }
1249 : else
1250 177684 : for (; n <= e; ++n)
1251 : {
1252 166553 : wi_cst
1253 166553 : = wi::shwi ((signed char) TREE_STRING_POINTER (init)[n],
1254 166553 : CHAR_BIT);
1255 166553 : m_r.union_ (int_range<1> (m_type, wi_cst, wi_cst));
1256 : }
1257 14469 : }
1258 : return true;
1259 : }
1260 :
1261 : // Build a range with the entire domain, and take out any elements which are
1262 : // initialized. If there's anything left in that range, it means there are
1263 : // missing elements and we should add a [0, 0] to the final range.
1264 969262 : FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init), ix, index, val)
1265 : {
1266 846718 : wide_int lo, hi;
1267 :
1268 : // A null index means the element follows the previous one.
1269 846718 : if (!index)
1270 0 : lo = hi = next;
1271 846718 : else if (TREE_CODE (index) == RANGE_EXPR)
1272 : {
1273 80 : lo = wi::to_wide (TREE_OPERAND (index, 0), prec);
1274 80 : hi = wi::to_wide (TREE_OPERAND (index, 1), prec);
1275 : }
1276 : else
1277 : {
1278 846638 : gcc_checking_assert (TREE_CODE (index) == INTEGER_CST);
1279 846638 : lo = hi = wi::to_wide (index, prec);
1280 : }
1281 : // A RAW_DATA_CST holds one element per byte.
1282 846718 : if (TREE_CODE (val) == RAW_DATA_CST)
1283 8 : hi = wi::add (hi, RAW_DATA_LENGTH (val) - 1);
1284 846718 : missing.intersect (int_range<2> (type, lo, hi, VR_ANTI_RANGE));
1285 846718 : next = wi::add (hi, 1);
1286 :
1287 846718 : if (TREE_CODE (val) == RAW_DATA_CST)
1288 : {
1289 8 : if (!intersects_p (idx_r, lo, hi))
1290 0 : continue;
1291 :
1292 8 : if (i != m_component_path.length ()
1293 8 : || !INTEGRAL_TYPE_P (m_type)
1294 8 : || TYPE_PRECISION (m_type) != CHAR_BIT
1295 16 : || !useless_type_conversion_p (m_type,
1296 8 : TREE_TYPE (val)))
1297 : return false;
1298 :
1299 16 : for (unsigned j = 0; j < idx_r.num_pairs (); ++j)
1300 : {
1301 8 : wide_int l = idx_r.lower_bound (j);
1302 8 : wide_int u = idx_r.upper_bound (j);
1303 8 : if (wi::lt_p (u, lo, TYPE_SIGN (type))
1304 8 : || wi::gt_p (l, hi, TYPE_SIGN (type)))
1305 0 : continue;
1306 8 : l = wi::max (l, lo, TYPE_SIGN (type));
1307 8 : u = wi::min (u, hi, TYPE_SIGN (type));
1308 8 : unsigned n = (l - lo).to_uhwi ();
1309 8 : unsigned e = (u - lo).to_uhwi ();
1310 : /* Note, if we'd have more than 256 iterations of the loops
1311 : below or even across all the outer loop iterations, it might
1312 : be more efficient to have a 256 bools array or 256-bit
1313 : bitmask, gather which bytes are seen and then union_ those
1314 : which were seen. Given the current param limits this can't
1315 : ever happen. */
1316 8 : wide_int wi_cst;
1317 8 : if (TYPE_UNSIGNED (m_type))
1318 1790 : for (; n <= e; ++n)
1319 : {
1320 1782 : wi_cst = wi::uhwi (RAW_DATA_UCHAR_ELT (val, n), CHAR_BIT);
1321 1782 : m_r.union_ (int_range<1> (m_type, wi_cst, wi_cst));
1322 : }
1323 : else
1324 0 : for (; n <= e; ++n)
1325 : {
1326 0 : wi_cst = wi::shwi (RAW_DATA_SCHAR_ELT (val, n), CHAR_BIT);
1327 0 : m_r.union_ (int_range<1> (m_type, wi_cst, wi_cst));
1328 : }
1329 8 : }
1330 8 : continue;
1331 8 : }
1332 :
1333 846710 : if (lo == hi)
1334 : {
1335 846630 : if (!idx_r.contains_p (lo))
1336 100477 : continue;
1337 : }
1338 80 : else if (!intersects_p (idx_r, lo, hi))
1339 0 : continue;
1340 :
1341 746233 : if (!accumulate_range (val, i))
1342 : return false;
1343 846718 : }
1344 :
1345 122544 : if (!missing.undefined_p ())
1346 1020 : accumulate_range_from_missing_constructor_elt ();
1347 : return true;
1348 275584 : }
1349 :
1350 : // Accumulate [0, 0] for a constructor element the initializer leaves out.
1351 : // For example, when loading t[1] in:
1352 : //
1353 : // static const int t[2] = { 4 };
1354 :
1355 : void
1356 1029 : ctor_ref_range::accumulate_range_from_missing_constructor_elt ()
1357 : {
1358 1029 : value_range zero (m_type);
1359 1029 : zero.set_zero (m_type);
1360 1029 : m_r.union_ (zero);
1361 1029 : }
1362 :
1363 : // Attempt to calculate the range of value loaded by STMT (which must be an
1364 : // assignment) if it is a load from a read-only aggregate variable. If
1365 : // successful, return true and set the discovered range in R. Otherwise return
1366 : // false and leave R untouched.
1367 :
1368 : bool
1369 202403744 : fold_using_range::range_from_readonly_var (vrange &r, gimple *stmt,
1370 : fur_source &src)
1371 : {
1372 202403744 : gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
1373 202403744 : tree type = TREE_TYPE (gimple_assign_lhs (stmt));
1374 202403744 : if (!irange::supports_p (type)
1375 49725121 : && !prange::supports_p (type)
1376 212526306 : && !frange::supports_p (type))
1377 : return false;
1378 :
1379 202403744 : unsigned HOST_WIDE_INT limit = param_vrp_cstload_limit;
1380 202403744 : if (!limit)
1381 : return false;
1382 :
1383 202383181 : tree t = gimple_assign_rhs1 (stmt);
1384 202383181 : if (!tree_fits_uhwi_p (TYPE_SIZE_UNIT (TREE_TYPE (t))))
1385 : return false;
1386 202383181 : limit *= tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (t)));
1387 :
1388 : // The component path of the reference, from the aggregate out.
1389 202383181 : auto_vec <tree, 4> component_path;
1390 202383181 : while (TREE_CODE (t) == ARRAY_REF
1391 254460832 : || TREE_CODE (t) == COMPONENT_REF)
1392 : {
1393 52077651 : component_path.safe_push (t);
1394 52077651 : t = TREE_OPERAND (t, 0);
1395 : }
1396 202383181 : component_path.reverse ();
1397 404766362 : if (component_path.is_empty ()
1398 33590523 : || (TREE_CODE (t) != VAR_DECL
1399 33590523 : && TREE_CODE (t) != CONST_DECL))
1400 : return false;
1401 :
1402 9564335 : if (!tree_fits_uhwi_p (DECL_SIZE_UNIT (t))
1403 9564335 : || tree_to_uhwi (DECL_SIZE_UNIT (t)) > limit)
1404 : return false;
1405 :
1406 : /* TODO: We perhaps should try to handle at least some cases when the
1407 : declaration is wrapped in a MEM_REF, but we need to be careful to look at
1408 : the right part of the constructor then. */
1409 8378601 : tree ctor = ctor_for_folding (t);
1410 8378601 : if (!ctor
1411 8378594 : || (TREE_CODE (ctor) != CONSTRUCTOR
1412 8378594 : && TREE_CODE (ctor) != STRING_CST))
1413 : return false;
1414 :
1415 131494 : value_range tmp (type);
1416 131494 : ctor_ref_range load (tmp, type, component_path, src);
1417 131494 : bool res = load.accumulate_range (ctor, 0) && !tmp.varying_p ();
1418 129593 : if (res)
1419 129593 : r = tmp;
1420 131494 : return res;
1421 202514675 : }
1422 :
1423 : // Calculate a range for phi statement S and return it in R.
1424 : // If a range cannot be calculated, return false.
1425 :
1426 : bool
1427 24325895 : fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
1428 : {
1429 24325895 : tree phi_def = gimple_phi_result (phi);
1430 24325895 : tree type = gimple_range_type (phi);
1431 24325895 : value_range arg_range (type);
1432 24325895 : value_range equiv_range (type);
1433 24325895 : unsigned x;
1434 :
1435 24325895 : if (!type)
1436 : return false;
1437 :
1438 : // Track if all executable arguments are the same.
1439 24325895 : tree single_arg = NULL_TREE;
1440 24325895 : bool seen_arg = false;
1441 :
1442 24325895 : relation_oracle *oracle = &(src.query()->relation ());
1443 : // Start with an empty range, unioning in each argument's range.
1444 24325895 : r.set_undefined ();
1445 87138983 : for (x = 0; x < gimple_phi_num_args (phi); x++)
1446 : {
1447 49580207 : tree arg = gimple_phi_arg_def (phi, x);
1448 : // An argument that is the same as the def provides no new range.
1449 49580207 : if (arg == phi_def)
1450 16268 : continue;
1451 :
1452 49563939 : edge e = gimple_phi_arg_edge (phi, x);
1453 :
1454 : // Get the range of the argument on its edge.
1455 49563939 : src.get_phi_operand (arg_range, arg, e);
1456 :
1457 49563939 : if (!arg_range.undefined_p ())
1458 : {
1459 : // Register potential dependencies for stale value tracking.
1460 : // Likewise, if the incoming PHI argument is equivalent to this
1461 : // PHI definition, it provides no new info. Accumulate these ranges
1462 : // in case all arguments are equivalences.
1463 49305569 : if (oracle->query (e, arg, phi_def) == VREL_EQ)
1464 270323 : equiv_range.union_(arg_range);
1465 : else
1466 49035246 : r.union_ (arg_range);
1467 :
1468 83354344 : if (gimple_range_ssa_p (arg) && src.gori_ssa ())
1469 34048763 : src.gori_ssa ()->register_dependency (phi_def, arg);
1470 : }
1471 :
1472 : // Track if all arguments are the same.
1473 49563939 : if (!seen_arg)
1474 : {
1475 : seen_arg = true;
1476 : single_arg = arg;
1477 : }
1478 25238044 : else if (!vrp_operand_equal_p (single_arg, arg))
1479 23992383 : single_arg = NULL_TREE;
1480 :
1481 : // Once the value reaches varying, stop looking.
1482 49563939 : if (r.varying_p () && single_arg == NULL_TREE)
1483 : break;
1484 : }
1485 :
1486 : // If all arguments were equivalences, use the equivalence ranges as no
1487 : // arguments were processed.
1488 24325895 : if (r.undefined_p () && !equiv_range.undefined_p ())
1489 121565 : r = equiv_range;
1490 :
1491 : // If the PHI boils down to a single effective argument, look at it.
1492 24325895 : if (single_arg)
1493 : {
1494 : // Symbolic arguments can be equivalences.
1495 2928510 : if (gimple_range_ssa_p (single_arg))
1496 : {
1497 : // Only allow the equivalence if the PHI definition does not
1498 : // dominate any incoming edge for SINGLE_ARG.
1499 : // See PR 108139 and 109462.
1500 2203858 : basic_block bb = gimple_bb (phi);
1501 2203858 : if (!dom_info_available_p (CDI_DOMINATORS))
1502 : single_arg = NULL;
1503 : else
1504 4707336 : for (x = 0; x < gimple_phi_num_args (phi); x++)
1505 2508221 : if (gimple_phi_arg_def (phi, x) == single_arg
1506 5006122 : && dominated_by_p (CDI_DOMINATORS,
1507 2497901 : gimple_phi_arg_edge (phi, x)->src,
1508 : bb))
1509 : {
1510 : single_arg = NULL;
1511 : break;
1512 : }
1513 2202926 : if (single_arg)
1514 2199115 : src.register_relation (phi, VREL_EQ, phi_def, single_arg);
1515 : }
1516 724652 : else if (src.get_operand (arg_range, single_arg))
1517 : {
1518 : // Check if the single argument points to a specific object.
1519 724652 : if (is_a <prange> (arg_range))
1520 : {
1521 66093 : prange &ptr = as_a <prange> (arg_range);
1522 : // If it doesn't already point at something, set points to.
1523 66093 : if (ptr.addr_unknown_p () && TREE_CODE (single_arg) == ADDR_EXPR)
1524 0 : ptr.set_addr (single_arg, true);
1525 66093 : r = ptr;
1526 66093 : return true;
1527 : }
1528 : // Numerical arguments that are a constant can be returned as
1529 : // the constant. This can help fold later cases where even this
1530 : // constant might have been UNDEFINED via an unreachable edge.
1531 658559 : if (arg_range.singleton_p ())
1532 : {
1533 656895 : r = arg_range;
1534 656895 : return true;
1535 : }
1536 : }
1537 : }
1538 :
1539 : // Incorporate any global value. If a PHI analysis phase was run, there may
1540 : // be a restricted global range already. Query the range with no context
1541 : // to get a global range.
1542 :
1543 : // If SCEV is available, query if this PHI has any known values.
1544 23602907 : if (scev_initialized_p ()
1545 23602907 : && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
1546 : {
1547 9908579 : class loop *l = loop_containing_stmt (phi);
1548 9908579 : if (l && loop_outer (l))
1549 : {
1550 7297532 : value_range loop_range (type);
1551 7297532 : range_of_ssa_name_with_loop_info (loop_range, phi_def, l, phi, src);
1552 7297532 : if (!loop_range.varying_p ())
1553 : {
1554 2476939 : if (dump_file && (dump_flags & TDF_DETAILS))
1555 : {
1556 14320 : fprintf (dump_file, "Loops range found for ");
1557 14320 : print_generic_expr (dump_file, phi_def, TDF_SLIM);
1558 14320 : fprintf (dump_file, ": ");
1559 14320 : loop_range.dump (dump_file);
1560 14320 : fprintf (dump_file, " and calculated range :");
1561 14320 : r.dump (dump_file);
1562 14320 : fprintf (dump_file, "\n");
1563 : }
1564 2476939 : r.intersect (loop_range);
1565 : }
1566 7297532 : }
1567 : }
1568 :
1569 : return true;
1570 24325895 : }
1571 :
1572 : // Calculate a range for call statement S and return it in R.
1573 : // If a range cannot be calculated, return false.
1574 :
1575 : bool
1576 13435524 : fold_using_range::range_of_call (vrange &r, gcall *call, fur_source &)
1577 : {
1578 13435524 : tree type = gimple_range_type (call);
1579 13435524 : if (!type)
1580 : return false;
1581 :
1582 13435524 : tree lhs = gimple_call_lhs (call);
1583 :
1584 13435524 : if (gimple_stmt_nonnegative_p (call))
1585 16982 : r.set_nonnegative (type);
1586 13418542 : else if (gimple_call_nonnull_result_p (call)
1587 13418542 : || gimple_call_nonnull_arg (call))
1588 642957 : r.set_nonzero (type);
1589 : else
1590 12775585 : r.set_varying (type);
1591 :
1592 13435524 : tree callee = gimple_call_fndecl (call);
1593 13435524 : if (callee
1594 13435524 : && useless_type_conversion_p (TREE_TYPE (TREE_TYPE (callee)), type))
1595 : {
1596 12260645 : value_range val;
1597 12260645 : if (ipa_return_value_range (val, callee))
1598 : {
1599 589031 : r.intersect (val);
1600 589031 : if (dump_file && (dump_flags & TDF_DETAILS))
1601 : {
1602 28 : fprintf (dump_file, "Using return value range of ");
1603 28 : print_generic_expr (dump_file, callee, TDF_SLIM);
1604 28 : fprintf (dump_file, ": ");
1605 28 : val.dump (dump_file);
1606 28 : fprintf (dump_file, "\n");
1607 : }
1608 : }
1609 12260645 : }
1610 :
1611 : // If there is an LHS, intersect that with what is known.
1612 13435524 : if (gimple_range_ssa_p (lhs))
1613 : {
1614 13435524 : value_range def (TREE_TYPE (lhs));
1615 13435524 : gimple_range_global (def, lhs);
1616 13435524 : r.intersect (def);
1617 13435524 : }
1618 : return true;
1619 : }
1620 :
1621 : // Given COND ? OP1 : OP2 with ranges R1 for OP1 and R2 for OP2, Use gori
1622 : // to further resolve R1 and R2 if there are any dependencies between
1623 : // OP1 and COND or OP2 and COND. All values can are to be calculated using SRC
1624 : // as the origination source location for operands..
1625 : // Effectively, use COND an the edge condition and solve for OP1 on the true
1626 : // edge and OP2 on the false edge.
1627 :
1628 : bool
1629 183453 : fold_using_range::condexpr_adjust (vrange &r1, vrange &r2, gimple *, tree cond,
1630 : tree op1, tree op2, fur_source &src)
1631 : {
1632 183453 : if (!src.gori () || !src.gori_ssa ())
1633 : return false;
1634 :
1635 130514 : tree ssa1 = gimple_range_ssa_p (op1);
1636 130514 : tree ssa2 = gimple_range_ssa_p (op2);
1637 130514 : if (!ssa1 && !ssa2)
1638 : return false;
1639 118911 : if (TREE_CODE (cond) != SSA_NAME)
1640 : return false;
1641 118911 : gassign *cond_def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (cond));
1642 118756 : if (!cond_def
1643 118756 : || TREE_CODE_CLASS (gimple_assign_rhs_code (cond_def)) != tcc_comparison)
1644 : return false;
1645 113854 : tree type = TREE_TYPE (gimple_assign_rhs1 (cond_def));
1646 113854 : if (!value_range::supports_type_p (type)
1647 227708 : || !range_compatible_p (type, TREE_TYPE (gimple_assign_rhs2 (cond_def))))
1648 : return false;
1649 113854 : range_op_handler hand (gimple_assign_rhs_code (cond_def));
1650 113854 : if (!hand)
1651 : return false;
1652 :
1653 113854 : tree c1 = gimple_range_ssa_p (gimple_assign_rhs1 (cond_def));
1654 227708 : tree c2 = gimple_range_ssa_p (gimple_assign_rhs2 (cond_def));
1655 :
1656 : // Only solve if there is one SSA name in the condition.
1657 113854 : if ((!c1 && !c2) || (c1 && c2))
1658 : return false;
1659 :
1660 : // Pick up the current values of each part of the condition.
1661 29534 : tree rhs1 = gimple_assign_rhs1 (cond_def);
1662 29534 : tree rhs2 = gimple_assign_rhs2 (cond_def);
1663 29534 : value_range cl (TREE_TYPE (rhs1));
1664 29534 : value_range cr (TREE_TYPE (rhs2));
1665 29534 : src.get_operand (cl, rhs1);
1666 29534 : src.get_operand (cr, rhs2);
1667 :
1668 29534 : tree cond_name = c1 ? c1 : c2;
1669 29534 : gimple *def_stmt = SSA_NAME_DEF_STMT (cond_name);
1670 :
1671 : // Evaluate the value of COND_NAME on the true and false edges, using either
1672 : // the op1 or op2 routines based on its location.
1673 29534 : value_range cond_true (type), cond_false (type);
1674 29534 : if (c1)
1675 : {
1676 29534 : if (!hand.op1_range (cond_false, type, range_false (), cr))
1677 : return false;
1678 29534 : if (!hand.op1_range (cond_true, type, range_true (), cr))
1679 : return false;
1680 29534 : cond_false.intersect (cl);
1681 29534 : cond_true.intersect (cl);
1682 : }
1683 : else
1684 : {
1685 0 : if (!hand.op2_range (cond_false, type, range_false (), cl))
1686 : return false;
1687 0 : if (!hand.op2_range (cond_true, type, range_true (), cl))
1688 : return false;
1689 0 : cond_false.intersect (cr);
1690 0 : cond_true.intersect (cr);
1691 : }
1692 :
1693 : // Now solve for SSA1 or SSA2 if they are in the dependency chain.
1694 54409 : if (ssa1 && src.gori_ssa()->in_chain_p (ssa1, cond_name))
1695 : {
1696 1964 : value_range tmp1 (TREE_TYPE (ssa1));
1697 3928 : if (src.gori ()->compute_operand_range (tmp1, def_stmt, cond_true,
1698 : ssa1, src))
1699 1386 : r1.intersect (tmp1);
1700 1964 : }
1701 48780 : if (ssa2 && src.gori_ssa ()->in_chain_p (ssa2, cond_name))
1702 : {
1703 261 : value_range tmp2 (TREE_TYPE (ssa2));
1704 522 : if (src.gori ()->compute_operand_range (tmp2, def_stmt, cond_false,
1705 : ssa2, src))
1706 217 : r2.intersect (tmp2);
1707 261 : }
1708 : // If the same name is specified in the condition and COND_EXPR,
1709 : // combine the calculated condition range and the other one provided. ie:
1710 : // c_1 = b_2 < 10
1711 : // f_3 = c_1 ? 0 : b_2
1712 : // With b_2 providing the false value, the value of f_3 will be
1713 : // either 0 UNION (0 = b_2 < 10), which is [-INF, 9].
1714 : // COND_EXPR is
1715 29534 : if (ssa1 && cond_name == ssa1)
1716 2377 : r1 = cond_true;
1717 27157 : else if (ssa2 && cond_name == ssa2)
1718 3113 : r2 = cond_false;
1719 : return true;
1720 29534 : }
1721 :
1722 : // Calculate a range for COND_EXPR statement S and return it in R.
1723 : // If a range cannot be calculated, return false.
1724 :
1725 : bool
1726 183453 : fold_using_range::range_of_cond_expr (vrange &r, gassign *s, fur_source &src)
1727 : {
1728 183453 : tree cond = gimple_assign_rhs1 (s);
1729 183453 : tree op1 = gimple_assign_rhs2 (s);
1730 183453 : tree op2 = gimple_assign_rhs3 (s);
1731 :
1732 183453 : tree type = gimple_range_type (s);
1733 183453 : if (!type)
1734 : return false;
1735 :
1736 183453 : value_range range1 (TREE_TYPE (op1));
1737 183453 : value_range range2 (TREE_TYPE (op2));
1738 183453 : value_range cond_range (TREE_TYPE (cond));
1739 183453 : gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR);
1740 183453 : gcc_checking_assert (range_compatible_p (TREE_TYPE (op1), TREE_TYPE (op2)));
1741 183453 : src.get_operand (cond_range, cond);
1742 183453 : src.get_operand (range1, op1);
1743 183453 : src.get_operand (range2, op2);
1744 :
1745 : // Try to see if there is a dependence between the COND and either operand
1746 183453 : if (condexpr_adjust (range1, range2, s, cond, op1, op2, src))
1747 29534 : if (dump_file && (dump_flags & TDF_DETAILS))
1748 : {
1749 636 : fprintf (dump_file, "Possible COND_EXPR adjustment. Range op1 : ");
1750 636 : range1.dump(dump_file);
1751 636 : fprintf (dump_file, " and Range op2: ");
1752 636 : range2.dump(dump_file);
1753 636 : fprintf (dump_file, "\n");
1754 : }
1755 :
1756 : // If the condition is known, choose the appropriate expression.
1757 183453 : if (cond_range.singleton_p ())
1758 : {
1759 : // False, pick second operand.
1760 2554 : if (cond_range.zero_p ())
1761 1221 : r = range2;
1762 : else
1763 1333 : r = range1;
1764 : }
1765 : else
1766 : {
1767 180899 : r = range1;
1768 180899 : r.union_ (range2);
1769 : }
1770 183453 : gcc_checking_assert (r.undefined_p ()
1771 : || range_compatible_p (r.type (), type));
1772 183453 : return true;
1773 183453 : }
1774 :
1775 : // If SCEV has any information about phi node NAME, return it as a range in R.
1776 :
1777 : void
1778 7297532 : fold_using_range::range_of_ssa_name_with_loop_info (vrange &r, tree name,
1779 : class loop *l, gphi *phi,
1780 : fur_source &src)
1781 : {
1782 7297532 : static bool in_scev_call = false;
1783 7297532 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
1784 : // Avoid SCEV callbacks causing infinite recursion.
1785 7297532 : if (in_scev_call)
1786 425317 : r.set_varying (TREE_TYPE (name));
1787 : // SCEV currently invokes get_range_query () for values. If the query
1788 : // being passed in is not the same SCEV will use, do not invoke SCEV.
1789 : // This can be remove if/when SCEV uses a passed in range-query.
1790 13744430 : else if (src.query () != get_range_query (cfun))
1791 : {
1792 755859 : r.set_varying (TREE_TYPE (name));
1793 : // Report the msmatch if SRC is not the global query. The cache
1794 : // uses a global query and would provide numerous false positives.
1795 46 : if (dump_file && (dump_flags & TDF_DETAILS)
1796 755881 : && src.query () != get_global_range_query ())
1797 22 : fprintf (dump_file,
1798 : "fold_using-range:: SCEV not invoked due to mismatched queries\n");
1799 : }
1800 : else
1801 : {
1802 6116356 : in_scev_call = true;
1803 6116356 : if (!range_of_var_in_loop (r, name, l, phi, src.query ()))
1804 873 : r.set_varying (TREE_TYPE (name));
1805 6116356 : in_scev_call = false;
1806 : }
1807 7297532 : }
1808 :
1809 : // -----------------------------------------------------------------------
1810 :
1811 : // Check if an && or || expression can be folded based on relations. ie
1812 : // c_2 = a_6 > b_7
1813 : // c_3 = a_6 < b_7
1814 : // c_4 = c_2 && c_3
1815 : // c_2 and c_3 can never be true at the same time,
1816 : // Therefore c_4 can always resolve to false based purely on the relations.
1817 :
1818 : void
1819 145001662 : fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s,
1820 : fur_source &src, vrange &op1,
1821 : vrange &op2)
1822 : {
1823 : // No queries or already folded.
1824 145001662 : if (!src.gori () || lhs_range.singleton_p ())
1825 : return;
1826 :
1827 : // Only care about AND and OR expressions.
1828 93546601 : enum tree_code code = gimple_expr_code (s);
1829 93546601 : bool is_and = false;
1830 93546601 : if (code == BIT_AND_EXPR || code == TRUTH_AND_EXPR)
1831 : is_and = true;
1832 89695223 : else if (code != BIT_IOR_EXPR && code != TRUTH_OR_EXPR)
1833 : return;
1834 :
1835 5417573 : gimple_range_op_handler handler (s);
1836 5417573 : tree lhs = handler.lhs ();
1837 5417573 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
1838 5417573 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
1839 :
1840 : // Deal with || and && only when there is a full set of symbolics.
1841 5417561 : if (!lhs || !ssa1 || !ssa2
1842 2929361 : || (TREE_CODE (TREE_TYPE (lhs)) != BOOLEAN_TYPE)
1843 1951037 : || (TREE_CODE (TREE_TYPE (ssa1)) != BOOLEAN_TYPE)
1844 7367205 : || (TREE_CODE (TREE_TYPE (ssa2)) != BOOLEAN_TYPE))
1845 : return;
1846 :
1847 : // Now we know its a boolean AND or OR expression with boolean operands.
1848 : // Ideally we search dependencies for common names, and see what pops out.
1849 : // until then, simply try to resolve direct dependencies.
1850 :
1851 1946827 : gimple *ssa1_stmt = SSA_NAME_DEF_STMT (ssa1);
1852 1946827 : gimple *ssa2_stmt = SSA_NAME_DEF_STMT (ssa2);
1853 :
1854 1946827 : gimple_range_op_handler handler1 (ssa1_stmt);
1855 1946827 : gimple_range_op_handler handler2 (ssa2_stmt);
1856 :
1857 : // If either handler is not present, no relation can be found.
1858 1946827 : if (!handler1 || !handler2)
1859 : return;
1860 :
1861 : // Both stmts will need to have 2 ssa names in the stmt.
1862 1821970 : tree ssa1_dep1 = gimple_range_ssa_p (handler1.operand1 ());
1863 1821970 : tree ssa1_dep2 = gimple_range_ssa_p (handler1.operand2 ());
1864 1821970 : tree ssa2_dep1 = gimple_range_ssa_p (handler2.operand1 ());
1865 1821970 : tree ssa2_dep2 = gimple_range_ssa_p (handler2.operand2 ());
1866 :
1867 1821970 : if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
1868 : return;
1869 :
1870 169323 : if (HONOR_NANS (TREE_TYPE (ssa1_dep1)))
1871 : return;
1872 :
1873 : // Make sure they are the same dependencies, and detect the order of the
1874 : // relationship.
1875 153651 : bool reverse_op2 = true;
1876 153651 : if (ssa1_dep1 == ssa2_dep1 && ssa1_dep2 == ssa2_dep2)
1877 : reverse_op2 = false;
1878 153583 : else if (ssa1_dep1 != ssa2_dep2 || ssa1_dep2 != ssa2_dep1)
1879 : return;
1880 :
1881 73 : int_range<2> bool_one = range_true ();
1882 73 : relation_kind relation1 = handler1.op1_op2_relation (bool_one, op1, op2);
1883 73 : relation_kind relation2 = handler2.op1_op2_relation (bool_one, op1, op2);
1884 73 : if (relation1 == VREL_VARYING || relation2 == VREL_VARYING)
1885 : return;
1886 :
1887 37 : if (reverse_op2)
1888 5 : relation2 = relation_swap (relation2);
1889 :
1890 : // x && y is false if the relation intersection of the true cases is NULL.
1891 37 : if (is_and && relation_intersect (relation1, relation2) == VREL_UNDEFINED)
1892 0 : lhs_range = range_false (boolean_type_node);
1893 : // x || y is true if the union of the true cases is NO-RELATION..
1894 : // ie, one or the other being true covers the full range of possibilities.
1895 37 : else if (!is_and && relation_union (relation1, relation2) == VREL_VARYING)
1896 0 : lhs_range = bool_one;
1897 : else
1898 : return;
1899 :
1900 0 : range_cast (lhs_range, TREE_TYPE (lhs));
1901 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1902 : {
1903 0 : fprintf (dump_file, " Relation adjustment: ");
1904 0 : print_generic_expr (dump_file, ssa1, TDF_SLIM);
1905 0 : fprintf (dump_file, " and ");
1906 0 : print_generic_expr (dump_file, ssa2, TDF_SLIM);
1907 0 : fprintf (dump_file, " combine to produce ");
1908 0 : lhs_range.dump (dump_file);
1909 0 : fputc ('\n', dump_file);
1910 : }
1911 :
1912 : return;
1913 73 : }
1914 :
1915 : // Register any outgoing edge relations from a conditional branch.
1916 :
1917 : void
1918 74635917 : fur_source::register_outgoing_edges (gcond *s, irange &lhs_range,
1919 : edge e0, edge e1)
1920 : {
1921 74635917 : int_range<2> e0_range, e1_range;
1922 74635917 : tree name;
1923 74635917 : basic_block bb = gimple_bb (s);
1924 :
1925 74635917 : gimple_range_op_handler handler (s);
1926 74635917 : if (!handler)
1927 : return;
1928 :
1929 74624885 : if (e0)
1930 : {
1931 : // If this edge is never taken, ignore it.
1932 62361422 : gcond_edge_range (e0_range, e0);
1933 62361422 : e0_range.intersect (lhs_range);
1934 62361422 : if (e0_range.undefined_p ())
1935 27003919 : e0 = NULL;
1936 : }
1937 :
1938 74624885 : if (e1)
1939 : {
1940 : // If this edge is never taken, ignore it.
1941 54424638 : gcond_edge_range (e1_range, e1);
1942 54424638 : e1_range.intersect (lhs_range);
1943 54424638 : if (e1_range.undefined_p ())
1944 31860085 : e1 = NULL;
1945 : }
1946 :
1947 74624885 : if (!e0 && !e1)
1948 : return;
1949 :
1950 : // First, register the gcond itself. This will catch statements like
1951 : // if (a_2 < b_5)
1952 71171320 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
1953 71171320 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
1954 71171320 : value_range r1,r2;
1955 71171320 : if (ssa1 && ssa2)
1956 : {
1957 22139311 : r1.set_varying (TREE_TYPE (ssa1));
1958 22139311 : r2.set_varying (TREE_TYPE (ssa2));
1959 22139311 : if (e0)
1960 : {
1961 15240348 : relation_kind relation = handler.op1_op2_relation (e0_range, r1, r2);
1962 15240348 : if (relation != VREL_VARYING)
1963 15168788 : register_relation (e0, relation, ssa1, ssa2);
1964 : }
1965 22139311 : if (e1)
1966 : {
1967 12973428 : relation_kind relation = handler.op1_op2_relation (e1_range, r1, r2);
1968 12973428 : if (relation != VREL_VARYING)
1969 12915561 : register_relation (e1, relation, ssa1, ssa2);
1970 : }
1971 : }
1972 :
1973 : // Outgoing relations of GORI exports require a gori engine.
1974 127953341 : if (!gori_ssa ())
1975 14389317 : return;
1976 :
1977 : // Now look for other relations in the exports. This will find stmts
1978 : // leading to the condition such as:
1979 : // c_2 = a_4 < b_7
1980 : // if (c_2)
1981 : // as well as relations implied by a known result, such as:
1982 : // c_2 = a_4 - b_7
1983 : // if (c_2 == 0)
1984 181139694 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, name)
1985 : {
1986 124357691 : if (!INTEGRAL_TYPE_P (TREE_TYPE (name)))
1987 80754589 : continue;
1988 99152468 : gimple *stmt = SSA_NAME_DEF_STMT (name);
1989 99152468 : gimple_range_op_handler handler (stmt);
1990 99152468 : if (!handler)
1991 55549366 : continue;
1992 43603102 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
1993 43603102 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
1994 43603102 : value_range r (TREE_TYPE (name));
1995 43603102 : if (ssa1 && ssa2)
1996 : {
1997 11248655 : r1.set_varying (TREE_TYPE (ssa1));
1998 11248655 : r2.set_varying (TREE_TYPE (ssa2));
1999 6834651 : if (e0 && gori ()->edge_range_p (r, e0, name, *m_query)
2000 6017076 : && !r.undefined_p ()
2001 17236494 : && !r.varying_p ())
2002 : {
2003 10450626 : if (!gori ()->edge_range_p (r1, e0, ssa1, *m_query)
2004 5225313 : || r1.undefined_p ())
2005 1625167 : r1.set_varying (TREE_TYPE (ssa1));
2006 10450626 : if (!gori ()->edge_range_p (r2, e0, ssa2, *m_query)
2007 5225313 : || r2.undefined_p ())
2008 1652564 : r2.set_varying (TREE_TYPE (ssa2));
2009 5225313 : relation_kind relation = handler.op1_op2_relation (r, r1, r2);
2010 5225313 : if (relation != VREL_VARYING)
2011 1657908 : register_relation (e0, relation, ssa1, ssa2);
2012 : }
2013 6672552 : if (e1 && gori ()->edge_range_p (r, e1, name, *m_query)
2014 5856148 : && !r.undefined_p ()
2015 17081367 : && !r.varying_p ())
2016 : {
2017 9174646 : if (!gori ()->edge_range_p (r1, e1, ssa1, *m_query)
2018 4587323 : || r1.undefined_p ())
2019 1546891 : r1.set_varying (TREE_TYPE (ssa1));
2020 9174646 : if (!gori ()->edge_range_p (r2, e1, ssa2, *m_query)
2021 4587323 : || r2.undefined_p ())
2022 1546637 : r2.set_varying (TREE_TYPE (ssa2));
2023 4587323 : relation_kind relation = handler.op1_op2_relation (r, r1, r2);
2024 4587323 : if (relation != VREL_VARYING)
2025 1285404 : register_relation (e1, relation, ssa1, ssa2);
2026 : }
2027 : }
2028 43603102 : }
2029 74635917 : }
|