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