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