Branch data Line data Source code
1 : : /* Code for GIMPLE range related routines.
2 : : Copyright (C) 2019-2025 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 : 492731072 : fur_source::fur_source (range_query *q)
58 : : {
59 : 492731072 : if (q)
60 : 492730091 : m_query = q;
61 : : else
62 : 1962 : m_query = get_range_query (cfun);
63 : 492731072 : m_depend_p = false;
64 : 492731072 : }
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 : 5237930 : fur_source::query_relation (tree op1 ATTRIBUTE_UNUSED,
87 : : tree op2 ATTRIBUTE_UNUSED)
88 : : {
89 : 5237930 : return VREL_VARYING;
90 : : }
91 : :
92 : : // Default registers nothing.
93 : :
94 : : void
95 : 25440904 : 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 : 25440904 : }
101 : :
102 : : // Default registers nothing.
103 : :
104 : : void
105 : 6363700 : fur_source::register_relation (edge e ATTRIBUTE_UNUSED,
106 : : relation_kind k ATTRIBUTE_UNUSED,
107 : : tree op1 ATTRIBUTE_UNUSED,
108 : : tree op2 ATTRIBUTE_UNUSED)
109 : : {
110 : 6363700 : }
111 : :
112 : : // Get the value of EXPR on edge m_edge.
113 : :
114 : : bool
115 : 69269781 : fur_edge::get_operand (vrange &r, tree expr)
116 : : {
117 : 69269781 : return m_query->range_on_edge (r, m_edge, expr);
118 : : }
119 : :
120 : : // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
121 : : // range_query to get the range on the edge.
122 : :
123 : : bool
124 : 0 : fur_edge::get_phi_operand (vrange &r, tree expr, edge e)
125 : : {
126 : : // Edge to edge recalculations not supported yet, until we sort it out.
127 : 0 : gcc_checking_assert (e == m_edge);
128 : 0 : return m_query->range_on_edge (r, e, expr);
129 : : }
130 : :
131 : : // Instantiate a stmt based fur_source.
132 : :
133 : 426919913 : fur_stmt::fur_stmt (gimple *s, range_query *q) : fur_source (q)
134 : : {
135 : 426919913 : m_stmt = s;
136 : 426919913 : }
137 : :
138 : : // Retrieve range of EXPR as it occurs as a use on stmt M_STMT.
139 : :
140 : : bool
141 : 558178853 : fur_stmt::get_operand (vrange &r, tree expr)
142 : : {
143 : 558178853 : return m_query->range_of_expr (r, expr, m_stmt);
144 : : }
145 : :
146 : : // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
147 : : // range_query to get the range on the edge.
148 : :
149 : : bool
150 : 57871076 : fur_stmt::get_phi_operand (vrange &r, tree expr, edge e)
151 : : {
152 : : // Pick up the range of expr from edge E.
153 : 57871076 : fur_edge e_src (e, m_query);
154 : 57871076 : return e_src.get_operand (r, expr);
155 : : }
156 : :
157 : : // Return relation based from m_stmt.
158 : :
159 : : relation_kind
160 : 108719741 : fur_stmt::query_relation (tree op1, tree op2)
161 : : {
162 : 108719741 : return m_query->relation ().query (m_stmt, op1, op2);
163 : : }
164 : :
165 : : // Instantiate a stmt based fur_source with a GORI object and a ranger cache.
166 : :
167 : 239559283 : fur_depend::fur_depend (gimple *s, range_query *q, ranger_cache *c)
168 : 239559283 : : fur_stmt (s, q), m_cache (c)
169 : : {
170 : 239559283 : m_depend_p = true;
171 : 239559283 : }
172 : :
173 : : // Register a relation on a stmt if there is an oracle.
174 : :
175 : : void
176 : 33929957 : fur_depend::register_relation (gimple *s, relation_kind k, tree op1, tree op2)
177 : : {
178 : 33929957 : m_query->relation ().record (s, k, op1, op2);
179 : : // This new relation could cause different calculations, so mark the operands
180 : : // with a new timestamp, forcing recalculations.
181 : 33929957 : if (m_cache)
182 : : {
183 : 33929919 : m_cache->update_consumers (op1);
184 : 33929919 : m_cache->update_consumers (op2);
185 : : }
186 : 33929957 : }
187 : :
188 : : // Register a relation on an edge if there is an oracle.
189 : :
190 : : void
191 : 6577525 : fur_depend::register_relation (edge e, relation_kind k, tree op1, tree op2)
192 : : {
193 : 6577525 : m_query->relation ().record (e, k, op1, op2);
194 : : // This new relation could cause different calculations, so mark the operands
195 : : // with a new timestamp, forcing recalculations.
196 : 6577525 : if (m_cache)
197 : : {
198 : 6577522 : m_cache->update_consumers (op1);
199 : 6577522 : m_cache->update_consumers (op2);
200 : : }
201 : 6577525 : }
202 : :
203 : : // This version of fur_source will pick a range up from a list of ranges
204 : : // supplied by the caller.
205 : :
206 : : class fur_list : public fur_source
207 : : {
208 : : public:
209 : : fur_list (vrange &r1, range_query *q = NULL);
210 : : fur_list (vrange &r1, vrange &r2, range_query *q = NULL);
211 : : fur_list (unsigned num, vrange **list, range_query *q = NULL);
212 : : virtual bool get_operand (vrange &r, tree expr) override;
213 : : virtual bool get_phi_operand (vrange &r, tree expr, edge e) override;
214 : : private:
215 : : vrange *m_local[2];
216 : : vrange **m_list;
217 : : unsigned m_index;
218 : : unsigned m_limit;
219 : : };
220 : :
221 : : // One range supplied for unary operations.
222 : :
223 : 900876 : fur_list::fur_list (vrange &r1, range_query *q) : fur_source (q)
224 : : {
225 : 900876 : m_list = m_local;
226 : 900876 : m_index = 0;
227 : 900876 : m_limit = 1;
228 : 900876 : m_local[0] = &r1;
229 : 900876 : }
230 : :
231 : : // Two ranges supplied for binary operations.
232 : :
233 : 0 : fur_list::fur_list (vrange &r1, vrange &r2, range_query *q) : fur_source (q)
234 : : {
235 : 0 : m_list = m_local;
236 : 0 : m_index = 0;
237 : 0 : m_limit = 2;
238 : 0 : m_local[0] = &r1;
239 : 0 : m_local[1] = &r2;
240 : 0 : }
241 : :
242 : : // Arbitrary number of ranges in a vector.
243 : :
244 : 0 : fur_list::fur_list (unsigned num, vrange **list, range_query *q)
245 : 0 : : fur_source (q)
246 : : {
247 : 0 : m_list = list;
248 : 0 : m_index = 0;
249 : 0 : m_limit = num;
250 : 0 : }
251 : :
252 : : // Get the next operand from the vector, ensure types are compatible.
253 : :
254 : : bool
255 : 1794187 : fur_list::get_operand (vrange &r, tree expr)
256 : : {
257 : : // Do not use the vector for non-ssa-names, or if it has been emptied.
258 : 1794187 : if (TREE_CODE (expr) != SSA_NAME || m_index >= m_limit)
259 : 893311 : return m_query->range_of_expr (r, expr);
260 : 900876 : r = *m_list[m_index++];
261 : 900876 : gcc_checking_assert (range_compatible_p (TREE_TYPE (expr), r.type ()));
262 : : return true;
263 : : }
264 : :
265 : : // This will simply pick the next operand from the vector.
266 : : bool
267 : 0 : fur_list::get_phi_operand (vrange &r, tree expr, edge e ATTRIBUTE_UNUSED)
268 : : {
269 : 0 : return get_operand (r, expr);
270 : : }
271 : :
272 : : // Fold stmt S into range R using R1 as the first operand.
273 : :
274 : : bool
275 : 900876 : fold_range (vrange &r, gimple *s, vrange &r1, range_query *q)
276 : : {
277 : 900876 : fold_using_range f;
278 : 900876 : fur_list src (r1, q);
279 : 900876 : return f.fold_stmt (r, s, src);
280 : : }
281 : :
282 : : // Fold stmt S into range R using R1 and R2 as the first two operands.
283 : :
284 : : bool
285 : 0 : fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2, range_query *q)
286 : : {
287 : 0 : fold_using_range f;
288 : 0 : fur_list src (r1, r2, q);
289 : 0 : return f.fold_stmt (r, s, src);
290 : : }
291 : :
292 : : // Fold stmt S into range R using NUM_ELEMENTS from VECTOR as the initial
293 : : // operands encountered.
294 : :
295 : : bool
296 : 0 : fold_range (vrange &r, gimple *s, unsigned num_elements, vrange **vector,
297 : : range_query *q)
298 : : {
299 : 0 : fold_using_range f;
300 : 0 : fur_list src (num_elements, vector, q);
301 : 0 : return f.fold_stmt (r, s, src);
302 : : }
303 : :
304 : : // Fold stmt S into range R using range query Q.
305 : :
306 : : bool
307 : 77704742 : fold_range (vrange &r, gimple *s, range_query *q)
308 : : {
309 : 77704742 : fold_using_range f;
310 : 77704742 : fur_stmt src (s, q);
311 : 77704742 : return f.fold_stmt (r, s, src);
312 : : }
313 : :
314 : : // Recalculate stmt S into R using range query Q as if it were on edge ON_EDGE.
315 : :
316 : : bool
317 : 7039202 : fold_range (vrange &r, gimple *s, edge on_edge, range_query *q)
318 : : {
319 : 7039202 : fold_using_range f;
320 : 7039202 : fur_edge src (on_edge, q);
321 : 7039202 : return f.fold_stmt (r, s, src);
322 : : }
323 : :
324 : : // Calculate op1 on statetemt S with LHS into range R using range query Q
325 : : // to resolve any other operands.
326 : :
327 : : bool
328 : 0 : op1_range (vrange &r, gimple *s, const vrange &lhs, range_query *q)
329 : : {
330 : 0 : gimple_range_op_handler handler (s);
331 : 0 : if (!handler)
332 : : return false;
333 : :
334 : 0 : fur_stmt src (s, q);
335 : :
336 : 0 : tree op2_expr = handler.operand2 ();
337 : 0 : if (!op2_expr)
338 : 0 : return handler.calc_op1 (r, lhs);
339 : :
340 : 0 : value_range op2 (TREE_TYPE (op2_expr));
341 : 0 : if (!src.get_operand (op2, op2_expr))
342 : : return false;
343 : :
344 : 0 : return handler.calc_op1 (r, lhs, op2);
345 : 0 : }
346 : :
347 : : // Calculate op1 on statetemt S into range R using range query Q.
348 : : // LHS is set to VARYING in this case.
349 : :
350 : : bool
351 : 0 : op1_range (vrange &r, gimple *s, range_query *q)
352 : : {
353 : 0 : tree lhs_type = gimple_range_type (s);
354 : 0 : if (!lhs_type)
355 : : return false;
356 : 0 : value_range lhs_range;
357 : 0 : lhs_range.set_varying (lhs_type);
358 : 0 : return op1_range (r, s, lhs_range, q);
359 : 0 : }
360 : :
361 : : // Calculate op2 on statetemt S with LHS into range R using range query Q
362 : : // to resolve any other operands.
363 : :
364 : : bool
365 : 0 : op2_range (vrange &r, gimple *s, const vrange &lhs, range_query *q)
366 : : {
367 : :
368 : 0 : gimple_range_op_handler handler (s);
369 : 0 : if (!handler)
370 : : return false;
371 : :
372 : 0 : fur_stmt src (s, q);
373 : :
374 : 0 : value_range op1 (TREE_TYPE (handler.operand1 ()));
375 : 0 : if (!src.get_operand (op1, handler.operand1 ()))
376 : : return false;
377 : :
378 : 0 : return handler.calc_op2 (r, lhs, op1);
379 : 0 : }
380 : :
381 : : // Calculate op2 on statetemt S into range R using range query Q.
382 : : // LHS is set to VARYING in this case.
383 : :
384 : : bool
385 : 0 : op2_range (vrange &r, gimple *s, range_query *q)
386 : : {
387 : 0 : tree lhs_type = gimple_range_type (s);
388 : 0 : if (!lhs_type)
389 : : return false;
390 : 0 : value_range lhs_range;
391 : 0 : lhs_range.set_varying (lhs_type);
392 : 0 : return op2_range (r, s, lhs_range, q);
393 : 0 : }
394 : :
395 : : // Provide a fur_source which can be used to determine any relations on
396 : : // a statement. It manages the callback from fold_using_ranges to determine
397 : : // a relation_trio for a statement.
398 : :
399 : : class fur_relation : public fur_stmt
400 : : {
401 : : public:
402 : : fur_relation (gimple *s, range_query *q = NULL);
403 : : virtual void register_relation (gimple *stmt, relation_kind k, tree op1,
404 : : tree op2);
405 : : virtual void register_relation (edge e, relation_kind k, tree op1,
406 : : tree op2);
407 : : relation_trio trio() const;
408 : : private:
409 : : relation_kind def_op1, def_op2, op1_op2;
410 : : };
411 : :
412 : 1059163 : fur_relation::fur_relation (gimple *s, range_query *q) : fur_stmt (s, q)
413 : : {
414 : 1059163 : def_op1 = def_op2 = op1_op2 = VREL_VARYING;
415 : 1059163 : }
416 : :
417 : : // Construct a trio from what is known.
418 : :
419 : : relation_trio
420 : 1059163 : fur_relation::trio () const
421 : : {
422 : 1059163 : return relation_trio (def_op1, def_op2, op1_op2);
423 : : }
424 : :
425 : : // Don't support edges, but avoid a compiler warning by providing the routine.
426 : :
427 : : void
428 : 0 : fur_relation::register_relation (edge, relation_kind, tree, tree)
429 : : {
430 : 0 : }
431 : :
432 : : // Register relation K between OP1 and OP2 on STMT.
433 : :
434 : : void
435 : 1041969 : fur_relation::register_relation (gimple *stmt, relation_kind k, tree op1,
436 : : tree op2)
437 : : {
438 : 1041969 : tree lhs = gimple_get_lhs (stmt);
439 : 1041969 : tree a1 = NULL_TREE;
440 : 1041969 : tree a2 = NULL_TREE;
441 : 1041969 : switch (gimple_code (stmt))
442 : : {
443 : 0 : case GIMPLE_COND:
444 : 0 : a1 = gimple_cond_lhs (stmt);
445 : 0 : a2 = gimple_cond_rhs (stmt);
446 : 0 : break;
447 : 1041969 : case GIMPLE_ASSIGN:
448 : 1041969 : a1 = gimple_assign_rhs1 (stmt);
449 : 1041969 : if (gimple_num_ops (stmt) >= 3)
450 : 1041969 : a2 = gimple_assign_rhs2 (stmt);
451 : : break;
452 : : default:
453 : : break;
454 : : }
455 : : // STMT is of the form LHS = A1 op A2, now map the relation to these
456 : : // operands, if possible.
457 : 1041969 : if (op1 == lhs)
458 : : {
459 : 1041969 : if (op2 == a1)
460 : 1041969 : def_op1 = k;
461 : 0 : else if (op2 == a2)
462 : 0 : def_op2 = k;
463 : : }
464 : 0 : else if (op2 == lhs)
465 : : {
466 : 0 : if (op1 == a1)
467 : 0 : def_op1 = relation_swap (k);
468 : 0 : else if (op1 == a2)
469 : 0 : def_op2 = relation_swap (k);
470 : : }
471 : : else
472 : : {
473 : 0 : if (op1 == a1 && op2 == a2)
474 : 0 : op1_op2 = k;
475 : 0 : else if (op2 == a1 && op1 == a2)
476 : 0 : op1_op2 = relation_swap (k);
477 : : }
478 : 1041969 : }
479 : :
480 : : // Return the relation trio for stmt S using query Q.
481 : :
482 : : relation_trio
483 : 1059163 : fold_relations (gimple *s, range_query *q)
484 : : {
485 : 1059163 : fold_using_range f;
486 : 1059163 : fur_relation src (s, q);
487 : 1059163 : tree lhs = gimple_range_ssa_p (gimple_get_lhs (s));
488 : 1059163 : if (lhs)
489 : : {
490 : 1059163 : value_range vr(TREE_TYPE (lhs));
491 : 1059163 : if (f.fold_stmt (vr, s, src))
492 : 1059163 : return src.trio ();
493 : 1059163 : }
494 : 0 : return TRIO_VARYING;
495 : : }
496 : :
497 : : // -------------------------------------------------------------------------
498 : :
499 : : // Adjust the range for a pointer difference where the operands came
500 : : // from a memchr.
501 : : //
502 : : // This notices the following sequence:
503 : : //
504 : : // def = __builtin_memchr (arg, 0, sz)
505 : : // n = def - arg
506 : : //
507 : : // The range for N can be narrowed to [0, PTRDIFF_MAX - 1].
508 : :
509 : : static void
510 : 2685671 : adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt)
511 : : {
512 : 2685671 : tree op0 = gimple_assign_rhs1 (diff_stmt);
513 : 2685671 : tree op1 = gimple_assign_rhs2 (diff_stmt);
514 : 2685671 : tree op0_ptype = TREE_TYPE (TREE_TYPE (op0));
515 : 2685671 : tree op1_ptype = TREE_TYPE (TREE_TYPE (op1));
516 : 2685671 : gimple *call;
517 : :
518 : 2685671 : if (TREE_CODE (op0) == SSA_NAME
519 : 2653735 : && TREE_CODE (op1) == SSA_NAME
520 : 2597940 : && (call = SSA_NAME_DEF_STMT (op0))
521 : 2597940 : && is_gimple_call (call)
522 : 122807 : && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
523 : 93352 : && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node)
524 : 93072 : && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node)
525 : 93072 : && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node)
526 : 92988 : && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node)
527 : 92988 : && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
528 : 92988 : && vrp_operand_equal_p (op1, gimple_call_arg (call, 0))
529 : 2764676 : && integer_zerop (gimple_call_arg (call, 1)))
530 : : {
531 : 10 : wide_int maxm1 = irange_val_max (ptrdiff_type_node) - 1;
532 : 10 : res.intersect (int_range<2> (ptrdiff_type_node,
533 : 20 : wi::zero (TYPE_PRECISION (ptrdiff_type_node)),
534 : 10 : maxm1));
535 : 10 : }
536 : 2685671 : }
537 : :
538 : : // Adjust the range for an IMAGPART_EXPR.
539 : :
540 : : static void
541 : 658535 : adjust_imagpart_expr (vrange &res, const gimple *stmt)
542 : : {
543 : 658535 : tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
544 : :
545 : 658535 : if (TREE_CODE (name) != SSA_NAME || !SSA_NAME_DEF_STMT (name))
546 : : return;
547 : :
548 : 532967 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
549 : 532967 : if (is_gimple_call (def_stmt) && gimple_call_internal_p (def_stmt))
550 : : {
551 : 404286 : switch (gimple_call_internal_fn (def_stmt))
552 : : {
553 : 386654 : case IFN_ADD_OVERFLOW:
554 : 386654 : case IFN_SUB_OVERFLOW:
555 : 386654 : case IFN_MUL_OVERFLOW:
556 : 386654 : case IFN_UADDC:
557 : 386654 : case IFN_USUBC:
558 : 386654 : case IFN_ATOMIC_COMPARE_EXCHANGE:
559 : 386654 : {
560 : 386654 : int_range<2> r;
561 : 386654 : r.set_varying (boolean_type_node);
562 : 386654 : tree type = TREE_TYPE (gimple_assign_lhs (stmt));
563 : 386654 : range_cast (r, type);
564 : 386654 : res.intersect (r);
565 : 386654 : }
566 : 404286 : default:
567 : 404286 : break;
568 : : }
569 : 404286 : return;
570 : : }
571 : 128681 : if (is_gimple_assign (def_stmt)
572 : 128681 : && gimple_assign_rhs_code (def_stmt) == COMPLEX_CST)
573 : : {
574 : 15 : tree cst = gimple_assign_rhs1 (def_stmt);
575 : 15 : if (TREE_CODE (cst) == COMPLEX_CST
576 : 15 : && TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) == INTEGER_TYPE)
577 : : {
578 : 4 : wide_int w = wi::to_wide (TREE_IMAGPART (cst));
579 : 4 : int_range<1> imag (TREE_TYPE (TREE_IMAGPART (cst)), w, w);
580 : 4 : res.intersect (imag);
581 : 4 : }
582 : : }
583 : : }
584 : :
585 : : // Adjust the range for a REALPART_EXPR.
586 : :
587 : : static void
588 : 659897 : adjust_realpart_expr (vrange &res, const gimple *stmt)
589 : : {
590 : 659897 : tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
591 : :
592 : 659897 : if (TREE_CODE (name) != SSA_NAME)
593 : : return;
594 : :
595 : 526956 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
596 : 526956 : if (!SSA_NAME_DEF_STMT (name))
597 : : return;
598 : :
599 : 526956 : if (is_gimple_assign (def_stmt)
600 : 526956 : && gimple_assign_rhs_code (def_stmt) == COMPLEX_CST)
601 : : {
602 : 10 : tree cst = gimple_assign_rhs1 (def_stmt);
603 : 10 : if (TREE_CODE (cst) == COMPLEX_CST
604 : 10 : && TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) == INTEGER_TYPE)
605 : : {
606 : 0 : wide_int imag = wi::to_wide (TREE_REALPART (cst));
607 : 0 : int_range<2> tmp (TREE_TYPE (TREE_REALPART (cst)), imag, imag);
608 : 0 : res.intersect (tmp);
609 : 0 : }
610 : : }
611 : : }
612 : :
613 : : // This function looks for situations when walking the use/def chains
614 : : // may provide additional contextual range information not exposed on
615 : : // this statement.
616 : :
617 : : static void
618 : 188805092 : gimple_range_adjustment (vrange &res, const gimple *stmt)
619 : : {
620 : 188805092 : switch (gimple_expr_code (stmt))
621 : : {
622 : 2685671 : case POINTER_DIFF_EXPR:
623 : 2685671 : adjust_pointer_diff_expr (as_a <irange> (res), stmt);
624 : 2685671 : return;
625 : :
626 : 658535 : case IMAGPART_EXPR:
627 : 658535 : adjust_imagpart_expr (res, stmt);
628 : 658535 : return;
629 : :
630 : 659897 : case REALPART_EXPR:
631 : 659897 : adjust_realpart_expr (res, stmt);
632 : 659897 : return;
633 : :
634 : : default:
635 : : break;
636 : : }
637 : : }
638 : :
639 : : // Calculate a range for statement S and return it in R. If NAME is provided it
640 : : // represents the SSA_NAME on the LHS of the statement. It is only required
641 : : // if there is more than one lhs/output. If a range cannot
642 : : // be calculated, return false.
643 : :
644 : : bool
645 : 302991451 : fold_using_range::fold_stmt (vrange &r, gimple *s, fur_source &src, tree name)
646 : : {
647 : 302991451 : bool res = false;
648 : : // If name and S are specified, make sure it is an LHS of S.
649 : 302991451 : gcc_checking_assert (!name || !gimple_get_lhs (s) ||
650 : : name == gimple_get_lhs (s));
651 : :
652 : 162218213 : if (!name)
653 : 162218213 : name = gimple_get_lhs (s);
654 : :
655 : : // Process addresses.
656 : 302991451 : if (gimple_code (s) == GIMPLE_ASSIGN
657 : 302991451 : && gimple_assign_rhs_code (s) == ADDR_EXPR)
658 : 4113267 : return range_of_address (as_a <prange> (r), s, src);
659 : :
660 : 298878184 : gimple_range_op_handler handler (s);
661 : 298878184 : if (handler)
662 : 188806208 : res = range_of_range_op (r, handler, src);
663 : 110071976 : else if (is_a<gphi *>(s))
664 : 28119926 : res = range_of_phi (r, as_a<gphi *> (s), src);
665 : 81952050 : else if (is_a<gcall *>(s))
666 : 13006023 : res = range_of_call (r, as_a<gcall *> (s), src);
667 : 68946027 : else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
668 : 155383 : res = range_of_cond_expr (r, as_a<gassign *> (s), src);
669 : :
670 : : // If the result is varying, check for basic nonnegativeness.
671 : : // Specifically this helps for now with strict enum in cases like
672 : : // g++.dg/warn/pr33738.C.
673 : 230087540 : bool so_p;
674 : 230087540 : if (res && r.varying_p () && INTEGRAL_TYPE_P (r.type ())
675 : 350769051 : && gimple_stmt_nonnegative_warnv_p (s, &so_p))
676 : 40708603 : r.set_nonnegative (r.type ());
677 : :
678 : 298878184 : if (!res)
679 : : {
680 : : // If no name specified or range is unsupported, bail.
681 : 68790644 : if (!name || !gimple_range_ssa_p (name))
682 : 50892 : return false;
683 : : // We don't understand the stmt, so return the global range.
684 : 68739752 : gimple_range_global (r, name);
685 : 68739752 : return true;
686 : : }
687 : :
688 : 230087540 : if (r.undefined_p ())
689 : : return true;
690 : :
691 : : // We sometimes get compatible types copied from operands, make sure
692 : : // the correct type is being returned.
693 : 230036739 : if (name && TREE_TYPE (name) != r.type ())
694 : : {
695 : 3378150 : gcc_checking_assert (range_compatible_p (r.type (), TREE_TYPE (name)));
696 : 3378150 : range_cast (r, TREE_TYPE (name));
697 : : }
698 : : return true;
699 : : }
700 : :
701 : : // Calculate a range for range_op statement S and return it in R. If any
702 : : // If a range cannot be calculated, return false.
703 : :
704 : : bool
705 : 188806208 : fold_using_range::range_of_range_op (vrange &r,
706 : : gimple_range_op_handler &handler,
707 : : fur_source &src)
708 : : {
709 : 188806208 : gcc_checking_assert (handler);
710 : 188806208 : gimple *s = handler.stmt ();
711 : 188806208 : tree type = gimple_range_type (s);
712 : 188806208 : if (!type)
713 : : return false;
714 : :
715 : 188806208 : tree lhs = handler.lhs ();
716 : 188806208 : tree op1 = handler.operand1 ();
717 : 188806208 : tree op2 = handler.operand2 ();
718 : :
719 : : // Certain types of builtin functions may have no arguments.
720 : 188806208 : if (!op1)
721 : : {
722 : 1116 : value_range r1 (type);
723 : 1116 : if (!handler.fold_range (r, type, r1, r1))
724 : 0 : r.set_varying (type);
725 : 1116 : return true;
726 : 1116 : }
727 : :
728 : 188805092 : value_range range1 (TREE_TYPE (op1));
729 : 188805092 : value_range range2 (op2 ? TREE_TYPE (op2) : TREE_TYPE (op1));
730 : :
731 : 188805092 : if (src.get_operand (range1, op1))
732 : : {
733 : 188805092 : if (!op2)
734 : : {
735 : : // Fold range, and register any dependency if available.
736 : 37490781 : value_range r2 (type);
737 : 37490781 : r2.set_varying (type);
738 : 37490781 : if (!handler.fold_range (r, type, range1, r2))
739 : 251633 : r.set_varying (type);
740 : 37490781 : if (lhs && gimple_range_ssa_p (op1))
741 : : {
742 : 55310245 : if (src.gori_ssa ())
743 : 20666451 : src.gori_ssa ()->register_dependency (lhs, op1);
744 : 34643761 : relation_kind rel;
745 : 34643761 : rel = handler.lhs_op1_relation (r, range1, range1);
746 : 34643761 : if (rel != VREL_VARYING)
747 : 25431544 : src.register_relation (s, rel, lhs, op1);
748 : : }
749 : 37490781 : }
750 : 151314311 : else if (src.get_operand (range2, op2))
751 : : {
752 : 151314311 : relation_kind rel = src.query_relation (op1, op2);
753 : 151314311 : if (dump_file && (dump_flags & TDF_DETAILS) && rel != VREL_VARYING)
754 : : {
755 : 132 : fprintf (dump_file, " folding with relation ");
756 : 132 : print_generic_expr (dump_file, op1, TDF_SLIM);
757 : 132 : print_relation (dump_file, rel);
758 : 132 : print_generic_expr (dump_file, op2, TDF_SLIM);
759 : 132 : fputc ('\n', dump_file);
760 : : }
761 : : // Fold range, and register any dependency if available.
762 : 151314311 : if (!handler.fold_range (r, type, range1, range2,
763 : : relation_trio::op1_op2 (rel)))
764 : 0 : r.set_varying (type);
765 : 151314311 : if (irange::supports_p (type))
766 : 137578490 : relation_fold_and_or (as_a <irange> (r), s, src, range1, range2);
767 : 151314311 : if (lhs)
768 : : {
769 : 155366085 : if (src.gori_ssa ())
770 : : {
771 : 60542544 : src.gori_ssa ()->register_dependency (lhs, op1);
772 : 121085088 : src.gori_ssa ()->register_dependency (lhs, op2);
773 : : }
774 : 94823481 : if (gimple_range_ssa_p (op1))
775 : : {
776 : 92172847 : relation_kind rel2 = handler.lhs_op1_relation (r, range1,
777 : 92172847 : range2, rel);
778 : 92172847 : if (rel2 != VREL_VARYING)
779 : 40534321 : src.register_relation (s, rel2, lhs, op1);
780 : : }
781 : 94823481 : if (gimple_range_ssa_p (op2))
782 : : {
783 : 37491062 : relation_kind rel2 = handler.lhs_op2_relation (r, range1,
784 : 37491062 : range2, rel);
785 : 37491062 : if (rel2 != VREL_VARYING)
786 : 2309824 : src.register_relation (s, rel2, lhs, op2);
787 : : }
788 : : }
789 : : // Check for an existing BB, as we maybe asked to fold an
790 : : // artificial statement not in the CFG.
791 : 56490830 : else if (is_a<gcond *> (s) && gimple_bb (s))
792 : : {
793 : 47877060 : basic_block bb = gimple_bb (s);
794 : 47877060 : edge e0 = EDGE_SUCC (bb, 0);
795 : : /* During RTL expansion one of the edges can be removed
796 : : if expansion proves the jump is unconditional. */
797 : 47877060 : edge e1 = single_succ_p (bb) ? NULL : EDGE_SUCC (bb, 1);
798 : :
799 : 47877060 : gcc_checking_assert (e1 || currently_expanding_to_rtl);
800 : 47877060 : if (!single_pred_p (e0->dest))
801 : 12124757 : e0 = NULL;
802 : 47877060 : if (e1 && !single_pred_p (e1->dest))
803 : : e1 = NULL;
804 : 47877060 : src.register_outgoing_edges (as_a<gcond *> (s),
805 : : as_a <irange> (r), e0, e1);
806 : : }
807 : : }
808 : : else
809 : 0 : r.set_varying (type);
810 : : }
811 : : else
812 : 0 : r.set_varying (type);
813 : : // Make certain range-op adjustments that aren't handled any other way.
814 : 188805092 : gimple_range_adjustment (r, s);
815 : 188805092 : return true;
816 : 188805092 : }
817 : :
818 : : // Calculate the range of an assignment containing an ADDR_EXPR.
819 : : // Return the range in R.
820 : : // If a range cannot be calculated, set it to VARYING and return true.
821 : :
822 : : bool
823 : 4113267 : fold_using_range::range_of_address (prange &r, gimple *stmt, fur_source &src)
824 : : {
825 : 4113267 : gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
826 : 4113267 : gcc_checking_assert (gimple_assign_rhs_code (stmt) == ADDR_EXPR);
827 : :
828 : 4113267 : bool strict_overflow_p;
829 : 4113267 : tree expr = gimple_assign_rhs1 (stmt);
830 : 4113267 : poly_int64 bitsize, bitpos;
831 : 4113267 : tree offset;
832 : 4113267 : machine_mode mode;
833 : 4113267 : int unsignedp, reversep, volatilep;
834 : 4113267 : tree base = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize,
835 : : &bitpos, &offset, &mode, &unsignedp,
836 : : &reversep, &volatilep);
837 : :
838 : :
839 : 4113267 : if (base != NULL_TREE
840 : 4113267 : && TREE_CODE (base) == MEM_REF
841 : 8078644 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
842 : : {
843 : 3965334 : tree ssa = TREE_OPERAND (base, 0);
844 : 3965334 : tree lhs = gimple_get_lhs (stmt);
845 : 6418058 : if (lhs && gimple_range_ssa_p (ssa) && src.gori_ssa ())
846 : 2452724 : src.gori_ssa ()->register_dependency (lhs, ssa);
847 : 3965334 : src.get_operand (r, ssa);
848 : 3965334 : range_cast (r, TREE_TYPE (gimple_assign_rhs1 (stmt)));
849 : :
850 : 3965334 : poly_offset_int off = 0;
851 : 3965334 : bool off_cst = false;
852 : 3965334 : if (offset == NULL_TREE || TREE_CODE (offset) == INTEGER_CST)
853 : : {
854 : 3888135 : off = mem_ref_offset (base);
855 : 3888135 : if (offset)
856 : 48 : off += poly_offset_int::from (wi::to_poly_wide (offset),
857 : 48 : SIGNED);
858 : 3888135 : off <<= LOG2_BITS_PER_UNIT;
859 : 3888135 : off += bitpos;
860 : : off_cst = true;
861 : : }
862 : : /* If &X->a is equal to X, the range of X is the result. */
863 : 3888135 : if (off_cst && known_eq (off, 0))
864 : 1453371 : return true;
865 : 2511963 : else if (flag_delete_null_pointer_checks
866 : 2511963 : && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)))
867 : : {
868 : : /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
869 : : allow going from non-NULL pointer to NULL. */
870 : 2510585 : if (r.undefined_p ()
871 : 5021170 : || !r.contains_p (wi::zero (TYPE_PRECISION (TREE_TYPE (expr)))))
872 : : {
873 : : /* We could here instead adjust r by off >> LOG2_BITS_PER_UNIT
874 : : using POINTER_PLUS_EXPR if off_cst and just fall back to
875 : : this. */
876 : 1813177 : r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
877 : 1813177 : return true;
878 : : }
879 : : }
880 : : /* If MEM_REF has a "positive" offset, consider it non-NULL
881 : : always, for -fdelete-null-pointer-checks also "negative"
882 : : ones. Punt for unknown offsets (e.g. variable ones). */
883 : 698786 : if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))
884 : 698583 : && off_cst
885 : 642838 : && known_ne (off, 0)
886 : 1341624 : && (flag_delete_null_pointer_checks || known_gt (off, 0)))
887 : : {
888 : 642838 : r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
889 : 642838 : return true;
890 : : }
891 : 55948 : r.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt)));
892 : 55948 : return true;
893 : : }
894 : :
895 : : // Handle "= &a".
896 : 147933 : if (tree_single_nonzero_warnv_p (expr, &strict_overflow_p))
897 : : {
898 : 146993 : r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
899 : 146993 : return true;
900 : : }
901 : :
902 : : // Otherwise return varying.
903 : 940 : r.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt)));
904 : 940 : return true;
905 : : }
906 : :
907 : : // Calculate a range for phi statement S and return it in R.
908 : : // If a range cannot be calculated, return false.
909 : :
910 : : bool
911 : 28119926 : fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
912 : : {
913 : 28119926 : tree phi_def = gimple_phi_result (phi);
914 : 28119926 : tree type = gimple_range_type (phi);
915 : 28119926 : value_range arg_range (type);
916 : 28119926 : value_range equiv_range (type);
917 : 28119926 : unsigned x;
918 : :
919 : 28119926 : if (!type)
920 : : return false;
921 : :
922 : : // Track if all executable arguments are the same.
923 : 28119926 : tree single_arg = NULL_TREE;
924 : 28119926 : bool seen_arg = false;
925 : :
926 : 28119926 : relation_oracle *oracle = &(src.query()->relation ());
927 : : // Start with an empty range, unioning in each argument's range.
928 : 28119926 : r.set_undefined ();
929 : 72228338 : for (x = 0; x < gimple_phi_num_args (phi); x++)
930 : : {
931 : 57903519 : tree arg = gimple_phi_arg_def (phi, x);
932 : : // An argument that is the same as the def provides no new range.
933 : 57903519 : if (arg == phi_def)
934 : 32443 : continue;
935 : :
936 : 57871076 : edge e = gimple_phi_arg_edge (phi, x);
937 : :
938 : : // Get the range of the argument on its edge.
939 : 57871076 : src.get_phi_operand (arg_range, arg, e);
940 : :
941 : 57871076 : if (!arg_range.undefined_p ())
942 : : {
943 : : // Register potential dependencies for stale value tracking.
944 : : // Likewise, if the incoming PHI argument is equivalent to this
945 : : // PHI definition, it provides no new info. Accumulate these ranges
946 : : // in case all arguments are equivalences.
947 : 57608096 : if (oracle->query (e, arg, phi_def) == VREL_EQ)
948 : 642831 : equiv_range.union_(arg_range);
949 : : else
950 : 56965265 : r.union_ (arg_range);
951 : :
952 : 95129800 : if (gimple_range_ssa_p (arg) && src.gori_ssa ())
953 : 37521698 : src.gori_ssa ()->register_dependency (phi_def, arg);
954 : : }
955 : :
956 : : // Track if all arguments are the same.
957 : 57871076 : if (!seen_arg)
958 : : {
959 : : seen_arg = true;
960 : : single_arg = arg;
961 : : }
962 : 29751150 : else if (single_arg != arg)
963 : 28209014 : single_arg = NULL_TREE;
964 : :
965 : : // Once the value reaches varying, stop looking.
966 : 57871076 : if (r.varying_p () && single_arg == NULL_TREE)
967 : : break;
968 : : }
969 : :
970 : : // If all arguments were equivalences, use the equivalence ranges as no
971 : : // arguments were processed.
972 : 28119926 : if (r.undefined_p () && !equiv_range.undefined_p ())
973 : 477941 : r = equiv_range;
974 : :
975 : : // If the PHI boils down to a single effective argument, look at it.
976 : 28119926 : if (single_arg)
977 : : {
978 : : // Symbolic arguments can be equivalences.
979 : 2951475 : if (gimple_range_ssa_p (single_arg))
980 : : {
981 : : // Only allow the equivalence if the PHI definition does not
982 : : // dominate any incoming edge for SINGLE_ARG.
983 : : // See PR 108139 and 109462.
984 : 2438912 : basic_block bb = gimple_bb (phi);
985 : 2438912 : if (!dom_info_available_p (CDI_DOMINATORS))
986 : : single_arg = NULL;
987 : : else
988 : 5266934 : for (x = 0; x < gimple_phi_num_args (phi); x++)
989 : 2833340 : if (gimple_phi_arg_def (phi, x) == single_arg
990 : 5653234 : && dominated_by_p (CDI_DOMINATORS,
991 : 2819894 : gimple_phi_arg_edge (phi, x)->src,
992 : : bb))
993 : : {
994 : : single_arg = NULL;
995 : : break;
996 : : }
997 : 2438018 : if (single_arg)
998 : 2433594 : src.register_relation (phi, VREL_EQ, phi_def, single_arg);
999 : : }
1000 : 512563 : else if (src.get_operand (arg_range, single_arg)
1001 : 1025126 : && arg_range.singleton_p ())
1002 : : {
1003 : : // Numerical arguments that are a constant can be returned as
1004 : : // the constant. This can help fold later cases where even this
1005 : : // constant might have been UNDEFINED via an unreachable edge.
1006 : 493056 : r = arg_range;
1007 : 493056 : return true;
1008 : : }
1009 : : }
1010 : :
1011 : : // Incorporate any global value. If a PHI analysis phase was run, there may
1012 : : // be a restricted global range already. Query the range with no context
1013 : : // to get a global range.
1014 : :
1015 : : // If SCEV is available, query if this PHI has any known values.
1016 : 27626870 : if (scev_initialized_p ()
1017 : 27626870 : && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
1018 : : {
1019 : 11756907 : class loop *l = loop_containing_stmt (phi);
1020 : 11756907 : if (l && loop_outer (l))
1021 : : {
1022 : 9006936 : value_range loop_range (type);
1023 : 9006936 : range_of_ssa_name_with_loop_info (loop_range, phi_def, l, phi, src);
1024 : 9006936 : if (!loop_range.varying_p ())
1025 : : {
1026 : 2437502 : if (dump_file && (dump_flags & TDF_DETAILS))
1027 : : {
1028 : 13505 : fprintf (dump_file, "Loops range found for ");
1029 : 13505 : print_generic_expr (dump_file, phi_def, TDF_SLIM);
1030 : 13505 : fprintf (dump_file, ": ");
1031 : 13505 : loop_range.dump (dump_file);
1032 : 13505 : fprintf (dump_file, " and calculated range :");
1033 : 13505 : r.dump (dump_file);
1034 : 13505 : fprintf (dump_file, "\n");
1035 : : }
1036 : 2437502 : r.intersect (loop_range);
1037 : : }
1038 : 9006936 : }
1039 : : }
1040 : :
1041 : : return true;
1042 : 28119926 : }
1043 : :
1044 : : // Calculate a range for call statement S and return it in R.
1045 : : // If a range cannot be calculated, return false.
1046 : :
1047 : : bool
1048 : 13006023 : fold_using_range::range_of_call (vrange &r, gcall *call, fur_source &)
1049 : : {
1050 : 13006023 : tree type = gimple_range_type (call);
1051 : 13006023 : if (!type)
1052 : : return false;
1053 : :
1054 : 13006023 : tree lhs = gimple_call_lhs (call);
1055 : 13006023 : bool strict_overflow_p;
1056 : :
1057 : 13006023 : if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p))
1058 : 39917 : r.set_nonnegative (type);
1059 : 12966106 : else if (gimple_call_nonnull_result_p (call)
1060 : 12966106 : || gimple_call_nonnull_arg (call))
1061 : 439933 : r.set_nonzero (type);
1062 : : else
1063 : 12526173 : r.set_varying (type);
1064 : :
1065 : 13006023 : tree callee = gimple_call_fndecl (call);
1066 : 13006023 : if (callee
1067 : 13006023 : && useless_type_conversion_p (TREE_TYPE (TREE_TYPE (callee)), type))
1068 : : {
1069 : 11809913 : value_range val;
1070 : 11809913 : if (ipa_return_value_range (val, callee))
1071 : : {
1072 : 583858 : r.intersect (val);
1073 : 583858 : if (dump_file && (dump_flags & TDF_DETAILS))
1074 : : {
1075 : 27 : fprintf (dump_file, "Using return value range of ");
1076 : 27 : print_generic_expr (dump_file, callee, TDF_SLIM);
1077 : 27 : fprintf (dump_file, ": ");
1078 : 27 : val.dump (dump_file);
1079 : 27 : fprintf (dump_file, "\n");
1080 : : }
1081 : : }
1082 : 11809913 : }
1083 : :
1084 : : // If there is an LHS, intersect that with what is known.
1085 : 13006023 : if (gimple_range_ssa_p (lhs))
1086 : : {
1087 : 13006023 : value_range def (TREE_TYPE (lhs));
1088 : 13006023 : gimple_range_global (def, lhs);
1089 : 13006023 : r.intersect (def);
1090 : 13006023 : }
1091 : : return true;
1092 : : }
1093 : :
1094 : : // Given COND ? OP1 : OP2 with ranges R1 for OP1 and R2 for OP2, Use gori
1095 : : // to further resolve R1 and R2 if there are any dependencies between
1096 : : // OP1 and COND or OP2 and COND. All values can are to be calculated using SRC
1097 : : // as the origination source location for operands..
1098 : : // Effectively, use COND an the edge condition and solve for OP1 on the true
1099 : : // edge and OP2 on the false edge.
1100 : :
1101 : : bool
1102 : 155383 : fold_using_range::condexpr_adjust (vrange &r1, vrange &r2, gimple *, tree cond,
1103 : : tree op1, tree op2, fur_source &src)
1104 : : {
1105 : 155383 : if (!src.gori () || !src.gori_ssa ())
1106 : : return false;
1107 : :
1108 : 107750 : tree ssa1 = gimple_range_ssa_p (op1);
1109 : 107750 : tree ssa2 = gimple_range_ssa_p (op2);
1110 : 107750 : if (!ssa1 && !ssa2)
1111 : : return false;
1112 : 97519 : if (TREE_CODE (cond) != SSA_NAME)
1113 : : return false;
1114 : 228197 : gassign *cond_def = dyn_cast <gassign *> (SSA_NAME_DEF_STMT (cond));
1115 : 97390 : if (!cond_def
1116 : 97390 : || TREE_CODE_CLASS (gimple_assign_rhs_code (cond_def)) != tcc_comparison)
1117 : : return false;
1118 : 92938 : tree type = TREE_TYPE (gimple_assign_rhs1 (cond_def));
1119 : 92938 : if (!value_range::supports_type_p (type)
1120 : 185872 : || !range_compatible_p (type, TREE_TYPE (gimple_assign_rhs2 (cond_def))))
1121 : : return false;
1122 : 92934 : range_op_handler hand (gimple_assign_rhs_code (cond_def));
1123 : 92934 : if (!hand)
1124 : : return false;
1125 : :
1126 : 92934 : tree c1 = gimple_range_ssa_p (gimple_assign_rhs1 (cond_def));
1127 : 185868 : tree c2 = gimple_range_ssa_p (gimple_assign_rhs2 (cond_def));
1128 : :
1129 : : // Only solve if there is one SSA name in the condition.
1130 : 92934 : if ((!c1 && !c2) || (c1 && c2))
1131 : : return false;
1132 : :
1133 : : // Pick up the current values of each part of the condition.
1134 : 24576 : tree rhs1 = gimple_assign_rhs1 (cond_def);
1135 : 24576 : tree rhs2 = gimple_assign_rhs2 (cond_def);
1136 : 24576 : value_range cl (TREE_TYPE (rhs1));
1137 : 24576 : value_range cr (TREE_TYPE (rhs2));
1138 : 24576 : src.get_operand (cl, rhs1);
1139 : 24576 : src.get_operand (cr, rhs2);
1140 : :
1141 : 24576 : tree cond_name = c1 ? c1 : c2;
1142 : 24576 : gimple *def_stmt = SSA_NAME_DEF_STMT (cond_name);
1143 : :
1144 : : // Evaluate the value of COND_NAME on the true and false edges, using either
1145 : : // the op1 or op2 routines based on its location.
1146 : 24576 : value_range cond_true (type), cond_false (type);
1147 : 24576 : if (c1)
1148 : : {
1149 : 24576 : if (!hand.op1_range (cond_false, type, range_false (), cr))
1150 : : return false;
1151 : 24576 : if (!hand.op1_range (cond_true, type, range_true (), cr))
1152 : : return false;
1153 : 24576 : cond_false.intersect (cl);
1154 : 24576 : cond_true.intersect (cl);
1155 : : }
1156 : : else
1157 : : {
1158 : 0 : if (!hand.op2_range (cond_false, type, range_false (), cl))
1159 : : return false;
1160 : 0 : if (!hand.op2_range (cond_true, type, range_true (), cl))
1161 : : return false;
1162 : 0 : cond_false.intersect (cr);
1163 : 0 : cond_true.intersect (cr);
1164 : : }
1165 : :
1166 : : // Now solve for SSA1 or SSA2 if they are in the dependency chain.
1167 : 45769 : if (ssa1 && src.gori_ssa()->in_chain_p (ssa1, cond_name))
1168 : : {
1169 : 871 : value_range tmp1 (TREE_TYPE (ssa1));
1170 : 1742 : if (src.gori ()->compute_operand_range (tmp1, def_stmt, cond_true,
1171 : : ssa1, src))
1172 : 556 : r1.intersect (tmp1);
1173 : 871 : }
1174 : 39699 : if (ssa2 && src.gori_ssa ()->in_chain_p (ssa2, cond_name))
1175 : : {
1176 : 248 : value_range tmp2 (TREE_TYPE (ssa2));
1177 : 496 : if (src.gori ()->compute_operand_range (tmp2, def_stmt, cond_false,
1178 : : ssa2, src))
1179 : 200 : r2.intersect (tmp2);
1180 : 248 : }
1181 : : // If the same name is specified in the condition and COND_EXPR,
1182 : : // combine the calculated condition range and the other one provided. ie:
1183 : : // c_1 = b_2 < 10
1184 : : // f_3 = c_1 ? 0 : b_2
1185 : : // With b_2 providing the false value, the value of f_3 will be
1186 : : // either 0 UNION (0 = b_2 < 10), which is [-INF, 9].
1187 : : // COND_EXPR is
1188 : 24576 : if (ssa1 && cond_name == ssa1)
1189 : 1903 : r1 = cond_true;
1190 : 22673 : else if (ssa2 && cond_name == ssa2)
1191 : 2784 : r2 = cond_false;
1192 : : return true;
1193 : 24576 : }
1194 : :
1195 : : // Calculate a range for COND_EXPR statement S and return it in R.
1196 : : // If a range cannot be calculated, return false.
1197 : :
1198 : : bool
1199 : 155383 : fold_using_range::range_of_cond_expr (vrange &r, gassign *s, fur_source &src)
1200 : : {
1201 : 155383 : tree cond = gimple_assign_rhs1 (s);
1202 : 155383 : tree op1 = gimple_assign_rhs2 (s);
1203 : 155383 : tree op2 = gimple_assign_rhs3 (s);
1204 : :
1205 : 155383 : tree type = gimple_range_type (s);
1206 : 155383 : if (!type)
1207 : : return false;
1208 : :
1209 : 155383 : value_range range1 (TREE_TYPE (op1));
1210 : 155383 : value_range range2 (TREE_TYPE (op2));
1211 : 155383 : value_range cond_range (TREE_TYPE (cond));
1212 : 155383 : gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR);
1213 : 155383 : gcc_checking_assert (range_compatible_p (TREE_TYPE (op1), TREE_TYPE (op2)));
1214 : 155383 : src.get_operand (cond_range, cond);
1215 : 155383 : src.get_operand (range1, op1);
1216 : 155383 : src.get_operand (range2, op2);
1217 : :
1218 : : // Try to see if there is a dependence between the COND and either operand
1219 : 155383 : if (condexpr_adjust (range1, range2, s, cond, op1, op2, src))
1220 : 24576 : if (dump_file && (dump_flags & TDF_DETAILS))
1221 : : {
1222 : 562 : fprintf (dump_file, "Possible COND_EXPR adjustment. Range op1 : ");
1223 : 562 : range1.dump(dump_file);
1224 : 562 : fprintf (dump_file, " and Range op2: ");
1225 : 562 : range2.dump(dump_file);
1226 : 562 : fprintf (dump_file, "\n");
1227 : : }
1228 : :
1229 : : // If the condition is known, choose the appropriate expression.
1230 : 155383 : if (cond_range.singleton_p ())
1231 : : {
1232 : : // False, pick second operand.
1233 : 2480 : if (cond_range.zero_p ())
1234 : 1250 : r = range2;
1235 : : else
1236 : 1230 : r = range1;
1237 : : }
1238 : : else
1239 : : {
1240 : 152903 : r = range1;
1241 : 152903 : r.union_ (range2);
1242 : : }
1243 : 155383 : gcc_checking_assert (r.undefined_p ()
1244 : : || range_compatible_p (r.type (), type));
1245 : 155383 : return true;
1246 : 155383 : }
1247 : :
1248 : : // If SCEV has any information about phi node NAME, return it as a range in R.
1249 : :
1250 : : void
1251 : 9006936 : fold_using_range::range_of_ssa_name_with_loop_info (vrange &r, tree name,
1252 : : class loop *l, gphi *phi,
1253 : : fur_source &src)
1254 : : {
1255 : 9006936 : static bool in_scev_call = false;
1256 : 9006936 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
1257 : : // Avoid SCEV callbacks causing infinite recursion.
1258 : 9006936 : if (in_scev_call)
1259 : 387439 : r.set_varying (TREE_TYPE (name));
1260 : : // SCEV currently invokes get_range_query () for values. If the query
1261 : : // being passed in is not the same SCEV will use, do not invoke SCEV.
1262 : : // This can be remove if/when SCEV uses a passed in range-query.
1263 : 17238994 : else if (src.query () != get_range_query (cfun))
1264 : : {
1265 : 1790644 : r.set_varying (TREE_TYPE (name));
1266 : : // Report the msmatch if SRC is not the global query. The cache
1267 : : // uses a global query and would provide numerous false positives.
1268 : 110 : if (dump_file && (dump_flags & TDF_DETAILS)
1269 : 1790704 : && src.query () != get_global_range_query ())
1270 : 33 : fprintf (dump_file,
1271 : : "fold_using-range:: SCEV not invoked due to mismatched queries\n");
1272 : : }
1273 : : else
1274 : : {
1275 : 6828853 : in_scev_call = true;
1276 : 6828853 : if (!range_of_var_in_loop (r, name, l, phi, src.query ()))
1277 : 2731 : r.set_varying (TREE_TYPE (name));
1278 : 6828853 : in_scev_call = false;
1279 : : }
1280 : 9006936 : }
1281 : :
1282 : : // -----------------------------------------------------------------------
1283 : :
1284 : : // Check if an && or || expression can be folded based on relations. ie
1285 : : // c_2 = a_6 > b_7
1286 : : // c_3 = a_6 < b_7
1287 : : // c_4 = c_2 && c_3
1288 : : // c_2 and c_3 can never be true at the same time,
1289 : : // Therefore c_4 can always resolve to false based purely on the relations.
1290 : :
1291 : : void
1292 : 137578490 : fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s,
1293 : : fur_source &src, vrange &op1,
1294 : : vrange &op2)
1295 : : {
1296 : : // No queries or already folded.
1297 : 137578490 : if (!src.gori () || lhs_range.singleton_p ())
1298 : 46617796 : return;
1299 : :
1300 : : // Only care about AND and OR expressions.
1301 : 90960694 : enum tree_code code = gimple_expr_code (s);
1302 : 90960694 : bool is_and = false;
1303 : 90960694 : if (code == BIT_AND_EXPR || code == TRUTH_AND_EXPR)
1304 : : is_and = true;
1305 : 87008791 : else if (code != BIT_IOR_EXPR && code != TRUTH_OR_EXPR)
1306 : : return;
1307 : :
1308 : 5507811 : gimple_range_op_handler handler (s);
1309 : 5507811 : tree lhs = handler.lhs ();
1310 : 5507811 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
1311 : 5507811 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
1312 : :
1313 : : // Deal with || and && only when there is a full set of symbolics.
1314 : 5507624 : if (!lhs || !ssa1 || !ssa2
1315 : 2879284 : || (TREE_CODE (TREE_TYPE (lhs)) != BOOLEAN_TYPE)
1316 : 1997202 : || (TREE_CODE (TREE_TYPE (ssa1)) != BOOLEAN_TYPE)
1317 : 7504381 : || (TREE_CODE (TREE_TYPE (ssa2)) != BOOLEAN_TYPE))
1318 : : return;
1319 : :
1320 : : // Now we know its a boolean AND or OR expression with boolean operands.
1321 : : // Ideally we search dependencies for common names, and see what pops out.
1322 : : // until then, simply try to resolve direct dependencies.
1323 : :
1324 : 1993275 : gimple *ssa1_stmt = SSA_NAME_DEF_STMT (ssa1);
1325 : 1993275 : gimple *ssa2_stmt = SSA_NAME_DEF_STMT (ssa2);
1326 : :
1327 : 1993275 : gimple_range_op_handler handler1 (ssa1_stmt);
1328 : 1993275 : gimple_range_op_handler handler2 (ssa2_stmt);
1329 : :
1330 : : // If either handler is not present, no relation can be found.
1331 : 1993275 : if (!handler1 || !handler2)
1332 : 151907 : return;
1333 : :
1334 : : // Both stmts will need to have 2 ssa names in the stmt.
1335 : 1841368 : tree ssa1_dep1 = gimple_range_ssa_p (handler1.operand1 ());
1336 : 1841368 : tree ssa1_dep2 = gimple_range_ssa_p (handler1.operand2 ());
1337 : 1841368 : tree ssa2_dep1 = gimple_range_ssa_p (handler2.operand1 ());
1338 : 1841368 : tree ssa2_dep2 = gimple_range_ssa_p (handler2.operand2 ());
1339 : :
1340 : 1841368 : if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
1341 : : return;
1342 : :
1343 : 240445 : if (HONOR_NANS (TREE_TYPE (ssa1_dep1)))
1344 : : return;
1345 : :
1346 : : // Make sure they are the same dependencies, and detect the order of the
1347 : : // relationship.
1348 : 228628 : bool reverse_op2 = true;
1349 : 228628 : if (ssa1_dep1 == ssa2_dep1 && ssa1_dep2 == ssa2_dep2)
1350 : : reverse_op2 = false;
1351 : 228444 : else if (ssa1_dep1 != ssa2_dep2 || ssa1_dep2 != ssa2_dep1)
1352 : : return;
1353 : :
1354 : 200 : int_range<2> bool_one = range_true ();
1355 : 200 : relation_kind relation1 = handler1.op1_op2_relation (bool_one, op1, op2);
1356 : 200 : relation_kind relation2 = handler2.op1_op2_relation (bool_one, op1, op2);
1357 : 200 : if (relation1 == VREL_VARYING || relation2 == VREL_VARYING)
1358 : : return;
1359 : :
1360 : 152 : if (reverse_op2)
1361 : 0 : relation2 = relation_negate (relation2);
1362 : :
1363 : : // x && y is false if the relation intersection of the true cases is NULL.
1364 : 152 : if (is_and && relation_intersect (relation1, relation2) == VREL_UNDEFINED)
1365 : 0 : lhs_range = range_false (boolean_type_node);
1366 : : // x || y is true if the union of the true cases is NO-RELATION..
1367 : : // ie, one or the other being true covers the full range of possibilities.
1368 : 152 : else if (!is_and && relation_union (relation1, relation2) == VREL_VARYING)
1369 : 0 : lhs_range = bool_one;
1370 : : else
1371 : 152 : return;
1372 : :
1373 : 0 : range_cast (lhs_range, TREE_TYPE (lhs));
1374 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1375 : : {
1376 : 0 : fprintf (dump_file, " Relation adjustment: ");
1377 : 0 : print_generic_expr (dump_file, ssa1, TDF_SLIM);
1378 : 0 : fprintf (dump_file, " and ");
1379 : 0 : print_generic_expr (dump_file, ssa2, TDF_SLIM);
1380 : 0 : fprintf (dump_file, " combine to produce ");
1381 : 0 : lhs_range.dump (dump_file);
1382 : 0 : fputc ('\n', dump_file);
1383 : : }
1384 : :
1385 : : return;
1386 : 200 : }
1387 : :
1388 : : // Register any outgoing edge relations from a conditional branch.
1389 : :
1390 : : void
1391 : 71148798 : fur_source::register_outgoing_edges (gcond *s, irange &lhs_range,
1392 : : edge e0, edge e1)
1393 : : {
1394 : 71148798 : int_range<2> e0_range, e1_range;
1395 : 71148798 : tree name;
1396 : 71148798 : basic_block bb = gimple_bb (s);
1397 : :
1398 : 71148798 : gimple_range_op_handler handler (s);
1399 : 71148798 : if (!handler)
1400 : : return;
1401 : :
1402 : 71137933 : if (e0)
1403 : : {
1404 : : // If this edge is never taken, ignore it.
1405 : 59013176 : gcond_edge_range (e0_range, e0);
1406 : 59013176 : e0_range.intersect (lhs_range);
1407 : 59013176 : if (e0_range.undefined_p ())
1408 : 26142532 : e0 = NULL;
1409 : : }
1410 : :
1411 : 71137933 : if (e1)
1412 : : {
1413 : : // If this edge is never taken, ignore it.
1414 : 51985973 : gcond_edge_range (e1_range, e1);
1415 : 51985973 : e1_range.intersect (lhs_range);
1416 : 51985973 : if (e1_range.undefined_p ())
1417 : 29756224 : e1 = NULL;
1418 : : }
1419 : :
1420 : 71137933 : if (!e0 && !e1)
1421 : : return;
1422 : :
1423 : : // First, register the gcond itself. This will catch statements like
1424 : : // if (a_2 < b_5)
1425 : 67893063 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
1426 : 67893063 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
1427 : 67893063 : value_range r1,r2;
1428 : 67893063 : if (ssa1 && ssa2)
1429 : : {
1430 : 20182261 : r1.set_varying (TREE_TYPE (ssa1));
1431 : 20182261 : r2.set_varying (TREE_TYPE (ssa2));
1432 : 20182261 : if (e0)
1433 : : {
1434 : 13542951 : relation_kind relation = handler.op1_op2_relation (e0_range, r1, r2);
1435 : 13542951 : if (relation != VREL_VARYING)
1436 : 13467062 : register_relation (e0, relation, ssa1, ssa2);
1437 : : }
1438 : 20182261 : if (e1)
1439 : : {
1440 : 11916253 : relation_kind relation = handler.op1_op2_relation (e1_range, r1, r2);
1441 : 11916253 : if (relation != VREL_VARYING)
1442 : 11858255 : register_relation (e1, relation, ssa1, ssa2);
1443 : : }
1444 : : }
1445 : :
1446 : : // Outgoing relations of GORI exports require a gori engine.
1447 : 122645611 : if (!gori_ssa ())
1448 : 13140527 : return;
1449 : :
1450 : : // Now look for other relations in the exports. This will find stmts
1451 : : // leading to the condition such as:
1452 : : // c_2 = a_4 < b_7
1453 : : // if (c_2)
1454 : 173786592 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, name)
1455 : : {
1456 : 119034056 : if (TREE_CODE (TREE_TYPE (name)) != BOOLEAN_TYPE)
1457 : 113446558 : continue;
1458 : 9321150 : gimple *stmt = SSA_NAME_DEF_STMT (name);
1459 : 9321150 : gimple_range_op_handler handler (stmt);
1460 : 9321150 : if (!handler)
1461 : 3733652 : continue;
1462 : 5587498 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
1463 : 5587498 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
1464 : 5587498 : value_range r (TREE_TYPE (name));
1465 : 5587498 : if (ssa1 && ssa2)
1466 : : {
1467 : 2496340 : r1.set_varying (TREE_TYPE (ssa1));
1468 : 2496340 : r2.set_varying (TREE_TYPE (ssa2));
1469 : 1536933 : if (e0 && gori ()->edge_range_p (r, e0, name, *m_query)
1470 : 3998654 : && r.singleton_p ())
1471 : : {
1472 : 1370540 : relation_kind relation = handler.op1_op2_relation (r, r1, r2);
1473 : 1370540 : if (relation != VREL_VARYING)
1474 : 485053 : register_relation (e0, relation, ssa1, ssa2);
1475 : : }
1476 : 1586975 : if (e1 && gori ()->edge_range_p (r, e1, name, *m_query)
1477 : 4038026 : && r.singleton_p ())
1478 : : {
1479 : 1129071 : relation_kind relation = handler.op1_op2_relation (r, r1, r2);
1480 : 1129071 : if (relation != VREL_VARYING)
1481 : 181291 : register_relation (e1, relation, ssa1, ssa2);
1482 : : }
1483 : : }
1484 : 5587498 : }
1485 : 71148798 : }
|
