Branch data Line data Source code
1 : : /* Code for GIMPLE range related routines.
2 : : Copyright (C) 2019-2024 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 : 379287111 : fur_source::fur_source (range_query *q)
57 : : {
58 : 379287111 : if (q)
59 : 379286314 : m_query = q;
60 : : else
61 : 1594 : m_query = get_range_query (cfun);
62 : 379287111 : m_gori = NULL;
63 : 379287111 : }
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 : 4183785 : fur_source::query_relation (tree op1 ATTRIBUTE_UNUSED,
86 : : tree op2 ATTRIBUTE_UNUSED)
87 : : {
88 : 4183785 : return VREL_VARYING;
89 : : }
90 : :
91 : : // Default registers nothing.
92 : :
93 : : void
94 : 16967852 : 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 : 16967852 : }
100 : :
101 : : // Default registers nothing.
102 : :
103 : : void
104 : 4844893 : 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 : 4844893 : }
110 : :
111 : : // This version of fur_source will pick a range up off an edge.
112 : :
113 : : class fur_edge : public fur_source
114 : : {
115 : : public:
116 : : fur_edge (edge e, range_query *q = NULL);
117 : : virtual bool get_operand (vrange &r, tree expr) override;
118 : : virtual bool get_phi_operand (vrange &r, tree expr, edge e) override;
119 : : private:
120 : : edge m_edge;
121 : : };
122 : :
123 : : // Instantiate an edge based fur_source.
124 : :
125 : : inline
126 : 99250666 : fur_edge::fur_edge (edge e, range_query *q) : fur_source (q)
127 : : {
128 : 49625333 : m_edge = e;
129 : : }
130 : :
131 : : // Get the value of EXPR on edge m_edge.
132 : :
133 : : bool
134 : 52651045 : fur_edge::get_operand (vrange &r, tree expr)
135 : : {
136 : 52651045 : return m_query->range_on_edge (r, m_edge, expr);
137 : : }
138 : :
139 : : // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
140 : : // range_query to get the range on the edge.
141 : :
142 : : bool
143 : 0 : fur_edge::get_phi_operand (vrange &r, tree expr, edge e)
144 : : {
145 : : // Edge to edge recalculations not supported yet, until we sort it out.
146 : 0 : gcc_checking_assert (e == m_edge);
147 : 0 : return m_query->range_on_edge (r, e, expr);
148 : : }
149 : :
150 : : // Instantiate a stmt based fur_source.
151 : :
152 : 328493520 : fur_stmt::fur_stmt (gimple *s, range_query *q) : fur_source (q)
153 : : {
154 : 328493520 : m_stmt = s;
155 : 328493520 : }
156 : :
157 : : // Retrieve range of EXPR as it occurs as a use on stmt M_STMT.
158 : :
159 : : bool
160 : 413914981 : fur_stmt::get_operand (vrange &r, tree expr)
161 : : {
162 : 413914981 : return m_query->range_of_expr (r, expr, m_stmt);
163 : : }
164 : :
165 : : // Evaluate EXPR for this stmt as a PHI argument on edge E. Use the current
166 : : // range_query to get the range on the edge.
167 : :
168 : : bool
169 : 44851096 : fur_stmt::get_phi_operand (vrange &r, tree expr, edge e)
170 : : {
171 : : // Pick up the range of expr from edge E.
172 : 44851096 : fur_edge e_src (e, m_query);
173 : 44851096 : return e_src.get_operand (r, expr);
174 : : }
175 : :
176 : : // Return relation based from m_stmt.
177 : :
178 : : relation_kind
179 : 81397130 : fur_stmt::query_relation (tree op1, tree op2)
180 : : {
181 : 81397130 : return m_query->query_relation (m_stmt, op1, op2);
182 : : }
183 : :
184 : : // Instantiate a stmt based fur_source with a GORI object.
185 : :
186 : :
187 : 196746859 : fur_depend::fur_depend (gimple *s, gori_compute *gori, range_query *q)
188 : 196746859 : : fur_stmt (s, q)
189 : : {
190 : 196746859 : gcc_checking_assert (gori);
191 : 196746859 : m_gori = gori;
192 : : // Set relations if there is an oracle in the range_query.
193 : : // This will enable registering of relationships as they are discovered.
194 : 196746859 : m_oracle = q->oracle ();
195 : :
196 : 196746859 : }
197 : :
198 : : // Register a relation on a stmt if there is an oracle.
199 : :
200 : : void
201 : 21892624 : fur_depend::register_relation (gimple *s, relation_kind k, tree op1, tree op2)
202 : : {
203 : 21892624 : if (m_oracle)
204 : 21847008 : m_oracle->register_stmt (s, k, op1, op2);
205 : 21892624 : }
206 : :
207 : : // Register a relation on an edge if there is an oracle.
208 : :
209 : : void
210 : 5544237 : fur_depend::register_relation (edge e, relation_kind k, tree op1, tree op2)
211 : : {
212 : 5544237 : if (m_oracle)
213 : 5544237 : m_oracle->register_edge (e, k, op1, op2);
214 : 5544237 : }
215 : :
216 : : // This version of fur_source will pick a range up from a list of ranges
217 : : // supplied by the caller.
218 : :
219 : : class fur_list : public fur_source
220 : : {
221 : : public:
222 : : fur_list (vrange &r1, range_query *q = NULL);
223 : : fur_list (vrange &r1, vrange &r2, range_query *q = NULL);
224 : : fur_list (unsigned num, vrange **list, range_query *q = NULL);
225 : : virtual bool get_operand (vrange &r, tree expr) override;
226 : : virtual bool get_phi_operand (vrange &r, tree expr, edge e) override;
227 : : private:
228 : : vrange *m_local[2];
229 : : vrange **m_list;
230 : : unsigned m_index;
231 : : unsigned m_limit;
232 : : };
233 : :
234 : : // One range supplied for unary operations.
235 : :
236 : 1168258 : fur_list::fur_list (vrange &r1, range_query *q) : fur_source (q)
237 : : {
238 : 1168258 : m_list = m_local;
239 : 1168258 : m_index = 0;
240 : 1168258 : m_limit = 1;
241 : 1168258 : m_local[0] = &r1;
242 : 1168258 : }
243 : :
244 : : // Two ranges supplied for binary operations.
245 : :
246 : 0 : fur_list::fur_list (vrange &r1, vrange &r2, range_query *q) : fur_source (q)
247 : : {
248 : 0 : m_list = m_local;
249 : 0 : m_index = 0;
250 : 0 : m_limit = 2;
251 : 0 : m_local[0] = &r1;
252 : 0 : m_local[1] = &r2;
253 : 0 : }
254 : :
255 : : // Arbitrary number of ranges in a vector.
256 : :
257 : 0 : fur_list::fur_list (unsigned num, vrange **list, range_query *q)
258 : 0 : : fur_source (q)
259 : : {
260 : 0 : m_list = list;
261 : 0 : m_index = 0;
262 : 0 : m_limit = num;
263 : 0 : }
264 : :
265 : : // Get the next operand from the vector, ensure types are compatible.
266 : :
267 : : bool
268 : 2335437 : fur_list::get_operand (vrange &r, tree expr)
269 : : {
270 : : // Do not use the vector for non-ssa-names, or if it has been emptied.
271 : 2335437 : if (TREE_CODE (expr) != SSA_NAME || m_index >= m_limit)
272 : 1167179 : return m_query->range_of_expr (r, expr);
273 : 1168258 : r = *m_list[m_index++];
274 : 1168258 : gcc_checking_assert (range_compatible_p (TREE_TYPE (expr), r.type ()));
275 : : return true;
276 : : }
277 : :
278 : : // This will simply pick the next operand from the vector.
279 : : bool
280 : 0 : fur_list::get_phi_operand (vrange &r, tree expr, edge e ATTRIBUTE_UNUSED)
281 : : {
282 : 0 : return get_operand (r, expr);
283 : : }
284 : :
285 : : // Fold stmt S into range R using R1 as the first operand.
286 : :
287 : : bool
288 : 1168258 : fold_range (vrange &r, gimple *s, vrange &r1, range_query *q)
289 : : {
290 : 1168258 : fold_using_range f;
291 : 1168258 : fur_list src (r1, q);
292 : 1168258 : return f.fold_stmt (r, s, src);
293 : : }
294 : :
295 : : // Fold stmt S into range R using R1 and R2 as the first two operands.
296 : :
297 : : bool
298 : 0 : fold_range (vrange &r, gimple *s, vrange &r1, vrange &r2, range_query *q)
299 : : {
300 : 0 : fold_using_range f;
301 : 0 : fur_list src (r1, r2, q);
302 : 0 : return f.fold_stmt (r, s, src);
303 : : }
304 : :
305 : : // Fold stmt S into range R using NUM_ELEMENTS from VECTOR as the initial
306 : : // operands encountered.
307 : :
308 : : bool
309 : 0 : fold_range (vrange &r, gimple *s, unsigned num_elements, vrange **vector,
310 : : range_query *q)
311 : : {
312 : 0 : fold_using_range f;
313 : 0 : fur_list src (num_elements, vector, q);
314 : 0 : return f.fold_stmt (r, s, src);
315 : : }
316 : :
317 : : // Fold stmt S into range R using range query Q.
318 : :
319 : : bool
320 : 61239870 : fold_range (vrange &r, gimple *s, range_query *q)
321 : : {
322 : 61239870 : fold_using_range f;
323 : 61239870 : fur_stmt src (s, q);
324 : 61239870 : return f.fold_stmt (r, s, src);
325 : : }
326 : :
327 : : // Recalculate stmt S into R using range query Q as if it were on edge ON_EDGE.
328 : :
329 : : bool
330 : 4774237 : fold_range (vrange &r, gimple *s, edge on_edge, range_query *q)
331 : : {
332 : 4774237 : fold_using_range f;
333 : 4774237 : fur_edge src (on_edge, q);
334 : 4774237 : return f.fold_stmt (r, s, src);
335 : : }
336 : :
337 : : // Provide a fur_source which can be used to determine any relations on
338 : : // a statement. It manages the callback from fold_using_ranges to determine
339 : : // a relation_trio for a statement.
340 : :
341 : : class fur_relation : public fur_stmt
342 : : {
343 : : public:
344 : : fur_relation (gimple *s, range_query *q = NULL);
345 : : virtual void register_relation (gimple *stmt, relation_kind k, tree op1,
346 : : tree op2);
347 : : virtual void register_relation (edge e, relation_kind k, tree op1,
348 : : tree op2);
349 : : relation_trio trio() const;
350 : : private:
351 : : relation_kind def_op1, def_op2, op1_op2;
352 : : };
353 : :
354 : 133721 : fur_relation::fur_relation (gimple *s, range_query *q) : fur_stmt (s, q)
355 : : {
356 : 133721 : def_op1 = def_op2 = op1_op2 = VREL_VARYING;
357 : 133721 : }
358 : :
359 : : // Construct a trio from what is known.
360 : :
361 : : relation_trio
362 : 133721 : fur_relation::trio () const
363 : : {
364 : 133721 : return relation_trio (def_op1, def_op2, op1_op2);
365 : : }
366 : :
367 : : // Don't support edges, but avoid a compiler warning by providing the routine.
368 : :
369 : : void
370 : 0 : fur_relation::register_relation (edge, relation_kind, tree, tree)
371 : : {
372 : 0 : }
373 : :
374 : : // Register relation K between OP1 and OP2 on STMT.
375 : :
376 : : void
377 : 120808 : fur_relation::register_relation (gimple *stmt, relation_kind k, tree op1,
378 : : tree op2)
379 : : {
380 : 120808 : tree lhs = gimple_get_lhs (stmt);
381 : 120808 : tree a1 = NULL_TREE;
382 : 120808 : tree a2 = NULL_TREE;
383 : 120808 : switch (gimple_code (stmt))
384 : : {
385 : 0 : case GIMPLE_COND:
386 : 0 : a1 = gimple_cond_lhs (stmt);
387 : 0 : a2 = gimple_cond_rhs (stmt);
388 : 0 : break;
389 : 120808 : case GIMPLE_ASSIGN:
390 : 120808 : a1 = gimple_assign_rhs1 (stmt);
391 : 120808 : if (gimple_num_ops (stmt) >= 3)
392 : 120797 : a2 = gimple_assign_rhs2 (stmt);
393 : : break;
394 : : default:
395 : : break;
396 : : }
397 : : // STMT is of the form LHS = A1 op A2, now map the relation to these
398 : : // operands, if possible.
399 : 120808 : if (op1 == lhs)
400 : : {
401 : 120808 : if (op2 == a1)
402 : 120808 : def_op1 = k;
403 : 0 : else if (op2 == a2)
404 : 0 : def_op2 = k;
405 : : }
406 : 0 : else if (op2 == lhs)
407 : : {
408 : 0 : if (op1 == a1)
409 : 0 : def_op1 = relation_swap (k);
410 : 0 : else if (op1 == a2)
411 : 0 : def_op2 = relation_swap (k);
412 : : }
413 : : else
414 : : {
415 : 0 : if (op1 == a1 && op2 == a2)
416 : 0 : op1_op2 = k;
417 : 0 : else if (op2 == a1 && op1 == a2)
418 : 0 : op1_op2 = relation_swap (k);
419 : : }
420 : 120808 : }
421 : :
422 : : // Return the relation trio for stmt S using query Q.
423 : :
424 : : relation_trio
425 : 133721 : fold_relations (gimple *s, range_query *q)
426 : : {
427 : 133721 : fold_using_range f;
428 : 133721 : fur_relation src (s, q);
429 : 133721 : tree lhs = gimple_range_ssa_p (gimple_get_lhs (s));
430 : 133721 : if (lhs)
431 : : {
432 : 133721 : Value_Range vr(TREE_TYPE (lhs));
433 : 133721 : if (f.fold_stmt (vr, s, src))
434 : 133721 : return src.trio ();
435 : 133721 : }
436 : 0 : return TRIO_VARYING;
437 : : }
438 : :
439 : : // -------------------------------------------------------------------------
440 : :
441 : : // Adjust the range for a pointer difference where the operands came
442 : : // from a memchr.
443 : : //
444 : : // This notices the following sequence:
445 : : //
446 : : // def = __builtin_memchr (arg, 0, sz)
447 : : // n = def - arg
448 : : //
449 : : // The range for N can be narrowed to [0, PTRDIFF_MAX - 1].
450 : :
451 : : static void
452 : 1655803 : adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt)
453 : : {
454 : 1655803 : tree op0 = gimple_assign_rhs1 (diff_stmt);
455 : 1655803 : tree op1 = gimple_assign_rhs2 (diff_stmt);
456 : 1655803 : tree op0_ptype = TREE_TYPE (TREE_TYPE (op0));
457 : 1655803 : tree op1_ptype = TREE_TYPE (TREE_TYPE (op1));
458 : 1655803 : gimple *call;
459 : :
460 : 1655803 : if (TREE_CODE (op0) == SSA_NAME
461 : 1642702 : && TREE_CODE (op1) == SSA_NAME
462 : 1606707 : && (call = SSA_NAME_DEF_STMT (op0))
463 : 1606707 : && is_gimple_call (call)
464 : 62562 : && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
465 : 44024 : && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node)
466 : 44016 : && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node)
467 : 44016 : && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node)
468 : 43936 : && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node)
469 : 43936 : && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
470 : 43936 : && vrp_operand_equal_p (op1, gimple_call_arg (call, 0))
471 : 1694037 : && integer_zerop (gimple_call_arg (call, 1)))
472 : : {
473 : 13 : wide_int maxm1 = irange_val_max (ptrdiff_type_node) - 1;
474 : 13 : res.intersect (int_range<2> (ptrdiff_type_node,
475 : 26 : wi::zero (TYPE_PRECISION (ptrdiff_type_node)),
476 : : maxm1));
477 : 13 : }
478 : 1655803 : }
479 : :
480 : : // Adjust the range for an IMAGPART_EXPR.
481 : :
482 : : static void
483 : 636926 : adjust_imagpart_expr (vrange &res, const gimple *stmt)
484 : : {
485 : 636926 : tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
486 : :
487 : 636926 : if (TREE_CODE (name) != SSA_NAME || !SSA_NAME_DEF_STMT (name))
488 : : return;
489 : :
490 : 513357 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
491 : 513357 : if (is_gimple_call (def_stmt) && gimple_call_internal_p (def_stmt))
492 : : {
493 : 373670 : switch (gimple_call_internal_fn (def_stmt))
494 : : {
495 : 373163 : case IFN_ADD_OVERFLOW:
496 : 373163 : case IFN_SUB_OVERFLOW:
497 : 373163 : case IFN_MUL_OVERFLOW:
498 : 373163 : case IFN_UADDC:
499 : 373163 : case IFN_USUBC:
500 : 373163 : case IFN_ATOMIC_COMPARE_EXCHANGE:
501 : 373163 : {
502 : 373163 : int_range<2> r;
503 : 373163 : r.set_varying (boolean_type_node);
504 : 373163 : tree type = TREE_TYPE (gimple_assign_lhs (stmt));
505 : 373163 : range_cast (r, type);
506 : 373163 : res.intersect (r);
507 : 373163 : }
508 : 373670 : default:
509 : 373670 : break;
510 : : }
511 : 373670 : return;
512 : : }
513 : 139687 : if (is_gimple_assign (def_stmt)
514 : 139687 : && gimple_assign_rhs_code (def_stmt) == COMPLEX_CST)
515 : : {
516 : 13 : tree cst = gimple_assign_rhs1 (def_stmt);
517 : 13 : if (TREE_CODE (cst) == COMPLEX_CST
518 : 13 : && TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) == INTEGER_TYPE)
519 : : {
520 : 13 : wide_int w = wi::to_wide (TREE_IMAGPART (cst));
521 : 13 : int_range<1> imag (TREE_TYPE (TREE_IMAGPART (cst)), w, w);
522 : 13 : res.intersect (imag);
523 : 13 : }
524 : : }
525 : : }
526 : :
527 : : // Adjust the range for a REALPART_EXPR.
528 : :
529 : : static void
530 : 591178 : adjust_realpart_expr (vrange &res, const gimple *stmt)
531 : : {
532 : 591178 : tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
533 : :
534 : 591178 : if (TREE_CODE (name) != SSA_NAME)
535 : : return;
536 : :
537 : 460163 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
538 : 460163 : if (!SSA_NAME_DEF_STMT (name))
539 : : return;
540 : :
541 : 460163 : if (is_gimple_assign (def_stmt)
542 : 460163 : && gimple_assign_rhs_code (def_stmt) == COMPLEX_CST)
543 : : {
544 : 16 : tree cst = gimple_assign_rhs1 (def_stmt);
545 : 16 : if (TREE_CODE (cst) == COMPLEX_CST
546 : 16 : && TREE_CODE (TREE_TYPE (TREE_TYPE (cst))) == INTEGER_TYPE)
547 : : {
548 : 16 : wide_int imag = wi::to_wide (TREE_REALPART (cst));
549 : 16 : int_range<2> tmp (TREE_TYPE (TREE_REALPART (cst)), imag, imag);
550 : 16 : res.intersect (tmp);
551 : 16 : }
552 : : }
553 : : }
554 : :
555 : : // This function looks for situations when walking the use/def chains
556 : : // may provide additional contextual range information not exposed on
557 : : // this statement.
558 : :
559 : : static void
560 : 146418086 : gimple_range_adjustment (vrange &res, const gimple *stmt)
561 : : {
562 : 146418086 : switch (gimple_expr_code (stmt))
563 : : {
564 : 1655803 : case POINTER_DIFF_EXPR:
565 : 1655803 : adjust_pointer_diff_expr (as_a <irange> (res), stmt);
566 : 1655803 : return;
567 : :
568 : 636926 : case IMAGPART_EXPR:
569 : 636926 : adjust_imagpart_expr (res, stmt);
570 : 636926 : return;
571 : :
572 : 591178 : case REALPART_EXPR:
573 : 591178 : adjust_realpart_expr (res, stmt);
574 : 591178 : return;
575 : :
576 : : default:
577 : : break;
578 : : }
579 : : }
580 : :
581 : : // Calculate a range for statement S and return it in R. If NAME is provided it
582 : : // represents the SSA_NAME on the LHS of the statement. It is only required
583 : : // if there is more than one lhs/output. If a range cannot
584 : : // be calculated, return false.
585 : :
586 : : bool
587 : 244745149 : fold_using_range::fold_stmt (vrange &r, gimple *s, fur_source &src, tree name)
588 : : {
589 : 244745149 : bool res = false;
590 : : // If name and S are specified, make sure it is an LHS of S.
591 : 244745149 : gcc_checking_assert (!name || !gimple_get_lhs (s) ||
592 : : name == gimple_get_lhs (s));
593 : :
594 : 133636565 : if (!name)
595 : 133636565 : name = gimple_get_lhs (s);
596 : :
597 : : // Process addresses.
598 : 244745149 : if (gimple_code (s) == GIMPLE_ASSIGN
599 : 244745149 : && gimple_assign_rhs_code (s) == ADDR_EXPR)
600 : 4358135 : return range_of_address (as_a <irange> (r), s, src);
601 : :
602 : 240387014 : gimple_range_op_handler handler (s);
603 : 240387014 : if (handler)
604 : 146419228 : res = range_of_range_op (r, handler, src);
605 : 93967786 : else if (is_a<gphi *>(s))
606 : 22118605 : res = range_of_phi (r, as_a<gphi *> (s), src);
607 : 71849181 : else if (is_a<gcall *>(s))
608 : 11690091 : res = range_of_call (r, as_a<gcall *> (s), src);
609 : 60159090 : else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
610 : 82926 : res = range_of_cond_expr (r, as_a<gassign *> (s), src);
611 : :
612 : : // If the result is varying, check for basic nonnegativeness.
613 : : // Specifically this helps for now with strict enum in cases like
614 : : // g++.dg/warn/pr33738.C.
615 : 180310850 : bool so_p;
616 : 180310850 : if (res && r.varying_p () && INTEGRAL_TYPE_P (r.type ())
617 : 278914569 : && gimple_stmt_nonnegative_warnv_p (s, &so_p))
618 : 31688046 : r.set_nonnegative (r.type ());
619 : :
620 : 240387014 : if (!res)
621 : : {
622 : : // If no name specified or range is unsupported, bail.
623 : 60076164 : if (!name || !gimple_range_ssa_p (name))
624 : 62624 : return false;
625 : : // We don't understand the stmt, so return the global range.
626 : 60013540 : gimple_range_global (r, name);
627 : 60013540 : return true;
628 : : }
629 : :
630 : 180310850 : if (r.undefined_p ())
631 : : return true;
632 : :
633 : : // We sometimes get compatible types copied from operands, make sure
634 : : // the correct type is being returned.
635 : 180259305 : if (name && TREE_TYPE (name) != r.type ())
636 : : {
637 : 2537279 : gcc_checking_assert (range_compatible_p (r.type (), TREE_TYPE (name)));
638 : 2537279 : range_cast (r, TREE_TYPE (name));
639 : : }
640 : : return true;
641 : : }
642 : :
643 : : // Calculate a range for range_op statement S and return it in R. If any
644 : : // If a range cannot be calculated, return false.
645 : :
646 : : bool
647 : 146419228 : fold_using_range::range_of_range_op (vrange &r,
648 : : gimple_range_op_handler &handler,
649 : : fur_source &src)
650 : : {
651 : 146419228 : gcc_checking_assert (handler);
652 : 146419228 : gimple *s = handler.stmt ();
653 : 146419228 : tree type = gimple_range_type (s);
654 : 146419228 : if (!type)
655 : : return false;
656 : :
657 : 146419228 : tree lhs = handler.lhs ();
658 : 146419228 : tree op1 = handler.operand1 ();
659 : 146419228 : tree op2 = handler.operand2 ();
660 : :
661 : : // Certain types of builtin functions may have no arguments.
662 : 146419228 : if (!op1)
663 : : {
664 : 1142 : Value_Range r1 (type);
665 : 1142 : if (!handler.fold_range (r, type, r1, r1))
666 : 0 : r.set_varying (type);
667 : 1142 : return true;
668 : 1142 : }
669 : :
670 : 146418086 : Value_Range range1 (TREE_TYPE (op1));
671 : 146418086 : Value_Range range2 (op2 ? TREE_TYPE (op2) : TREE_TYPE (op1));
672 : :
673 : 146418086 : if (src.get_operand (range1, op1))
674 : : {
675 : 146418086 : if (!op2)
676 : : {
677 : : // Fold range, and register any dependency if available.
678 : 27809003 : Value_Range r2 (type);
679 : 27809003 : r2.set_varying (type);
680 : 27809003 : if (!handler.fold_range (r, type, range1, r2))
681 : 49536 : r.set_varying (type);
682 : 27809003 : if (lhs && gimple_range_ssa_p (op1))
683 : : {
684 : 25641020 : if (src.gori ())
685 : 15541937 : src.gori ()->register_dependency (lhs, op1);
686 : 25641020 : relation_kind rel;
687 : 25641020 : rel = handler.lhs_op1_relation (r, range1, range1);
688 : 25641020 : if (rel != VREL_VARYING)
689 : 19006038 : src.register_relation (s, rel, lhs, op1);
690 : : }
691 : 27809003 : }
692 : 118609083 : else if (src.get_operand (range2, op2))
693 : : {
694 : 118609083 : relation_kind rel = src.query_relation (op1, op2);
695 : 118609083 : if (dump_file && (dump_flags & TDF_DETAILS) && rel != VREL_VARYING)
696 : : {
697 : 25 : fprintf (dump_file, " folding with relation ");
698 : 25 : print_generic_expr (dump_file, op1, TDF_SLIM);
699 : 25 : print_relation (dump_file, rel);
700 : 25 : print_generic_expr (dump_file, op2, TDF_SLIM);
701 : 25 : fputc ('\n', dump_file);
702 : : }
703 : : // Fold range, and register any dependency if available.
704 : 118609083 : if (!handler.fold_range (r, type, range1, range2,
705 : : relation_trio::op1_op2 (rel)))
706 : 0 : r.set_varying (type);
707 : 118609083 : if (irange::supports_p (type))
708 : 114268128 : relation_fold_and_or (as_a <irange> (r), s, src, range1, range2);
709 : 118609083 : if (lhs)
710 : : {
711 : 70760300 : if (src.gori ())
712 : : {
713 : 47012898 : src.gori ()->register_dependency (lhs, op1);
714 : 47012898 : src.gori ()->register_dependency (lhs, op2);
715 : : }
716 : 70760300 : if (gimple_range_ssa_p (op1))
717 : : {
718 : 68722091 : rel = handler.lhs_op1_relation (r, range1, range2, rel);
719 : 68722091 : if (rel != VREL_VARYING)
720 : 24157794 : src.register_relation (s, rel, lhs, op1);
721 : : }
722 : 70760300 : if (gimple_range_ssa_p (op2))
723 : : {
724 : 28277906 : rel = handler.lhs_op2_relation (r, range1, range2, rel);
725 : 28277906 : if (rel != VREL_VARYING)
726 : 1323865 : src.register_relation (s, rel, lhs, op2);
727 : : }
728 : : }
729 : : // Check for an existing BB, as we maybe asked to fold an
730 : : // artificial statement not in the CFG.
731 : 47848783 : else if (is_a<gcond *> (s) && gimple_bb (s))
732 : : {
733 : 39446289 : basic_block bb = gimple_bb (s);
734 : 39446289 : edge e0 = EDGE_SUCC (bb, 0);
735 : 39446289 : edge e1 = EDGE_SUCC (bb, 1);
736 : :
737 : 78892578 : if (!single_pred_p (e0->dest))
738 : 9884832 : e0 = NULL;
739 : 78892578 : if (!single_pred_p (e1->dest))
740 : 15534800 : e1 = NULL;
741 : 39446289 : src.register_outgoing_edges (as_a<gcond *> (s),
742 : : as_a <irange> (r), e0, e1);
743 : : }
744 : : }
745 : : else
746 : 0 : r.set_varying (type);
747 : : }
748 : : else
749 : 0 : r.set_varying (type);
750 : : // Make certain range-op adjustments that aren't handled any other way.
751 : 146418086 : gimple_range_adjustment (r, s);
752 : 146418086 : return true;
753 : 146418086 : }
754 : :
755 : : // Calculate the range of an assignment containing an ADDR_EXPR.
756 : : // Return the range in R.
757 : : // If a range cannot be calculated, set it to VARYING and return true.
758 : :
759 : : bool
760 : 4358135 : fold_using_range::range_of_address (irange &r, gimple *stmt, fur_source &src)
761 : : {
762 : 4358135 : gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
763 : 4358135 : gcc_checking_assert (gimple_assign_rhs_code (stmt) == ADDR_EXPR);
764 : :
765 : 4358135 : bool strict_overflow_p;
766 : 4358135 : tree expr = gimple_assign_rhs1 (stmt);
767 : 4358135 : poly_int64 bitsize, bitpos;
768 : 4358135 : tree offset;
769 : 4358135 : machine_mode mode;
770 : 4358135 : int unsignedp, reversep, volatilep;
771 : 4358135 : tree base = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize,
772 : : &bitpos, &offset, &mode, &unsignedp,
773 : : &reversep, &volatilep);
774 : :
775 : :
776 : 4358135 : if (base != NULL_TREE
777 : 4358135 : && TREE_CODE (base) == MEM_REF
778 : 8571179 : && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
779 : : {
780 : 4213015 : tree ssa = TREE_OPERAND (base, 0);
781 : 4213015 : tree lhs = gimple_get_lhs (stmt);
782 : 4213015 : if (lhs && gimple_range_ssa_p (ssa) && src.gori ())
783 : 2303015 : src.gori ()->register_dependency (lhs, ssa);
784 : 4213015 : src.get_operand (r, ssa);
785 : 4213015 : range_cast (r, TREE_TYPE (gimple_assign_rhs1 (stmt)));
786 : :
787 : 4213015 : poly_offset_int off = 0;
788 : 4213015 : bool off_cst = false;
789 : 4213015 : if (offset == NULL_TREE || TREE_CODE (offset) == INTEGER_CST)
790 : : {
791 : 4139097 : off = mem_ref_offset (base);
792 : 4139097 : if (offset)
793 : 60 : off += poly_offset_int::from (wi::to_poly_wide (offset),
794 : 60 : SIGNED);
795 : 4139097 : off <<= LOG2_BITS_PER_UNIT;
796 : 4139097 : off += bitpos;
797 : : off_cst = true;
798 : : }
799 : : /* If &X->a is equal to X, the range of X is the result. */
800 : 4139097 : if (off_cst && known_eq (off, 0))
801 : 1441487 : return true;
802 : 2771528 : else if (flag_delete_null_pointer_checks
803 : 2771528 : && !TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)))
804 : : {
805 : : /* For -fdelete-null-pointer-checks -fno-wrapv-pointer we don't
806 : : allow going from non-NULL pointer to NULL. */
807 : 2770342 : if (r.undefined_p ()
808 : 5540684 : || !r.contains_p (wi::zero (TYPE_PRECISION (TREE_TYPE (expr)))))
809 : : {
810 : : /* We could here instead adjust r by off >> LOG2_BITS_PER_UNIT
811 : : using POINTER_PLUS_EXPR if off_cst and just fall back to
812 : : this. */
813 : 2062886 : r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
814 : 2062886 : return true;
815 : : }
816 : : }
817 : : /* If MEM_REF has a "positive" offset, consider it non-NULL
818 : : always, for -fdelete-null-pointer-checks also "negative"
819 : : ones. Punt for unknown offsets (e.g. variable ones). */
820 : 708642 : if (!TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr))
821 : 708600 : && off_cst
822 : 663645 : && known_ne (off, 0)
823 : 1372287 : && (flag_delete_null_pointer_checks || known_gt (off, 0)))
824 : : {
825 : 663645 : r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
826 : 663645 : return true;
827 : : }
828 : 44997 : r.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt)));
829 : 44997 : return true;
830 : : }
831 : :
832 : : // Handle "= &a".
833 : 145120 : if (tree_single_nonzero_warnv_p (expr, &strict_overflow_p))
834 : : {
835 : 144475 : r.set_nonzero (TREE_TYPE (gimple_assign_rhs1 (stmt)));
836 : 144475 : return true;
837 : : }
838 : :
839 : : // Otherwise return varying.
840 : 645 : r.set_varying (TREE_TYPE (gimple_assign_rhs1 (stmt)));
841 : 645 : return true;
842 : : }
843 : :
844 : : // Calculate a range for phi statement S and return it in R.
845 : : // If a range cannot be calculated, return false.
846 : :
847 : : bool
848 : 22118605 : fold_using_range::range_of_phi (vrange &r, gphi *phi, fur_source &src)
849 : : {
850 : 22118605 : tree phi_def = gimple_phi_result (phi);
851 : 22118605 : tree type = gimple_range_type (phi);
852 : 22118605 : Value_Range arg_range (type);
853 : 22118605 : Value_Range equiv_range (type);
854 : 22118605 : unsigned x;
855 : :
856 : 22118605 : if (!type)
857 : : return false;
858 : :
859 : : // Track if all executable arguments are the same.
860 : 22118605 : tree single_arg = NULL_TREE;
861 : 22118605 : bool seen_arg = false;
862 : :
863 : : // Start with an empty range, unioning in each argument's range.
864 : 22118605 : r.set_undefined ();
865 : 55167883 : for (x = 0; x < gimple_phi_num_args (phi); x++)
866 : : {
867 : 44874619 : tree arg = gimple_phi_arg_def (phi, x);
868 : : // An argument that is the same as the def provides no new range.
869 : 44874619 : if (arg == phi_def)
870 : 23523 : continue;
871 : :
872 : 44851096 : edge e = gimple_phi_arg_edge (phi, x);
873 : :
874 : : // Get the range of the argument on its edge.
875 : 44851096 : src.get_phi_operand (arg_range, arg, e);
876 : :
877 : 44851096 : if (!arg_range.undefined_p ())
878 : : {
879 : : // Register potential dependencies for stale value tracking.
880 : : // Likewise, if the incoming PHI argument is equivalent to this
881 : : // PHI definition, it provides no new info. Accumulate these ranges
882 : : // in case all arguments are equivalences.
883 : 44596775 : if (src.query ()->query_relation (e, arg, phi_def, false) == VREL_EQ)
884 : 324972 : equiv_range.union_(arg_range);
885 : : else
886 : 44271803 : r.union_ (arg_range);
887 : :
888 : 44596775 : if (gimple_range_ssa_p (arg) && src.gori ())
889 : 26332183 : src.gori ()->register_dependency (phi_def, arg);
890 : : }
891 : :
892 : : // Track if all arguments are the same.
893 : 44851096 : if (!seen_arg)
894 : : {
895 : : seen_arg = true;
896 : : single_arg = arg;
897 : : }
898 : 22732491 : else if (single_arg != arg)
899 : 21422112 : single_arg = NULL_TREE;
900 : :
901 : : // Once the value reaches varying, stop looking.
902 : 44851096 : if (r.varying_p () && single_arg == NULL_TREE)
903 : : break;
904 : : }
905 : :
906 : : // If all arguments were equivalences, use the equivalence ranges as no
907 : : // arguments were processed.
908 : 22118605 : if (r.undefined_p () && !equiv_range.undefined_p ())
909 : 195338 : r = equiv_range;
910 : :
911 : : // If the PHI boils down to a single effective argument, look at it.
912 : 22118605 : if (single_arg)
913 : : {
914 : : // Symbolic arguments can be equivalences.
915 : 2648595 : if (gimple_range_ssa_p (single_arg))
916 : : {
917 : : // Only allow the equivalence if the PHI definition does not
918 : : // dominate any incoming edge for SINGLE_ARG.
919 : : // See PR 108139 and 109462.
920 : 2150515 : basic_block bb = gimple_bb (phi);
921 : 2150515 : if (!dom_info_available_p (CDI_DOMINATORS))
922 : : single_arg = NULL;
923 : : else
924 : 4592018 : for (x = 0; x < gimple_phi_num_args (phi); x++)
925 : 2443110 : if (gimple_phi_arg_def (phi, x) == single_arg
926 : 4870077 : && dominated_by_p (CDI_DOMINATORS,
927 : 2426967 : gimple_phi_arg_edge (phi, x)->src,
928 : : bb))
929 : : {
930 : : single_arg = NULL;
931 : : break;
932 : : }
933 : 2150247 : if (single_arg)
934 : 2148908 : src.register_relation (phi, VREL_EQ, phi_def, single_arg);
935 : : }
936 : 498080 : else if (src.get_operand (arg_range, single_arg)
937 : 996160 : && arg_range.singleton_p ())
938 : : {
939 : : // Numerical arguments that are a constant can be returned as
940 : : // the constant. This can help fold later cases where even this
941 : : // constant might have been UNDEFINED via an unreachable edge.
942 : 482259 : r = arg_range;
943 : 482259 : return true;
944 : : }
945 : : }
946 : :
947 : : // If PHI analysis is available, see if there is an iniital range.
948 : 21636346 : if (phi_analysis_available_p ()
949 : 21636346 : && irange::supports_p (TREE_TYPE (phi_def)))
950 : : {
951 : 10505053 : phi_group *g = (phi_analysis())[phi_def];
952 : 10505053 : if (g && !(g->range ().varying_p ()))
953 : : {
954 : 421758 : if (dump_file && (dump_flags & TDF_DETAILS))
955 : : {
956 : 0 : fprintf (dump_file, "PHI GROUP query for ");
957 : 0 : print_generic_expr (dump_file, phi_def, TDF_SLIM);
958 : 0 : fprintf (dump_file, " found : ");
959 : 0 : g->range ().dump (dump_file);
960 : 0 : fprintf (dump_file, " and adjusted original range from :");
961 : 0 : r.dump (dump_file);
962 : : }
963 : 421758 : r.intersect (g->range ());
964 : 421758 : if (dump_file && (dump_flags & TDF_DETAILS))
965 : : {
966 : 0 : fprintf (dump_file, " to :");
967 : 0 : r.dump (dump_file);
968 : 0 : fprintf (dump_file, "\n");
969 : : }
970 : : }
971 : : }
972 : :
973 : : // If SCEV is available, query if this PHI has any known values.
974 : 21636346 : if (scev_initialized_p ()
975 : 21636346 : && !POINTER_TYPE_P (TREE_TYPE (phi_def)))
976 : : {
977 : 32324016 : class loop *l = loop_containing_stmt (phi);
978 : 10205411 : if (l && loop_outer (l))
979 : : {
980 : 7584757 : Value_Range loop_range (type);
981 : 7584757 : range_of_ssa_name_with_loop_info (loop_range, phi_def, l, phi, src);
982 : 7584757 : if (!loop_range.varying_p ())
983 : : {
984 : 2999730 : if (dump_file && (dump_flags & TDF_DETAILS))
985 : : {
986 : 43 : fprintf (dump_file, "Loops range found for ");
987 : 43 : print_generic_expr (dump_file, phi_def, TDF_SLIM);
988 : 43 : fprintf (dump_file, ": ");
989 : 43 : loop_range.dump (dump_file);
990 : 43 : fprintf (dump_file, " and calculated range :");
991 : 43 : r.dump (dump_file);
992 : 43 : fprintf (dump_file, "\n");
993 : : }
994 : 2999730 : r.intersect (loop_range);
995 : : }
996 : 7584757 : }
997 : : }
998 : :
999 : : return true;
1000 : 22118605 : }
1001 : :
1002 : : // Calculate a range for call statement S and return it in R.
1003 : : // If a range cannot be calculated, return false.
1004 : :
1005 : : bool
1006 : 11690091 : fold_using_range::range_of_call (vrange &r, gcall *call, fur_source &)
1007 : : {
1008 : 11690091 : tree type = gimple_range_type (call);
1009 : 11690091 : if (!type)
1010 : : return false;
1011 : :
1012 : 11690091 : tree lhs = gimple_call_lhs (call);
1013 : 11690091 : bool strict_overflow_p;
1014 : :
1015 : 11690091 : if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p))
1016 : 36285 : r.set_nonnegative (type);
1017 : 11653806 : else if (gimple_call_nonnull_result_p (call)
1018 : 11653806 : || gimple_call_nonnull_arg (call))
1019 : 415775 : r.set_nonzero (type);
1020 : : else
1021 : 11238031 : r.set_varying (type);
1022 : :
1023 : 11690091 : tree callee = gimple_call_fndecl (call);
1024 : 11690091 : if (callee
1025 : 11690091 : && useless_type_conversion_p (TREE_TYPE (TREE_TYPE (callee)), type))
1026 : : {
1027 : 10822372 : Value_Range val;
1028 : 10822372 : if (ipa_return_value_range (val, callee))
1029 : : {
1030 : 517346 : r.intersect (val);
1031 : 517346 : if (dump_file && (dump_flags & TDF_DETAILS))
1032 : : {
1033 : 8 : fprintf (dump_file, "Using return value range of ");
1034 : 8 : print_generic_expr (dump_file, callee, TDF_SLIM);
1035 : 8 : fprintf (dump_file, ": ");
1036 : 8 : val.dump (dump_file);
1037 : 8 : fprintf (dump_file, "\n");
1038 : : }
1039 : : }
1040 : 10822372 : }
1041 : :
1042 : : // If there is an LHS, intersect that with what is known.
1043 : 11690091 : if (lhs)
1044 : : {
1045 : 11690091 : Value_Range def (TREE_TYPE (lhs));
1046 : 11690091 : gimple_range_global (def, lhs);
1047 : 11690091 : r.intersect (def);
1048 : 11690091 : }
1049 : : return true;
1050 : : }
1051 : :
1052 : : // Calculate a range for COND_EXPR statement S and return it in R.
1053 : : // If a range cannot be calculated, return false.
1054 : :
1055 : : bool
1056 : 82926 : fold_using_range::range_of_cond_expr (vrange &r, gassign *s, fur_source &src)
1057 : : {
1058 : 82926 : tree cond = gimple_assign_rhs1 (s);
1059 : 82926 : tree op1 = gimple_assign_rhs2 (s);
1060 : 82926 : tree op2 = gimple_assign_rhs3 (s);
1061 : :
1062 : 82926 : tree type = gimple_range_type (s);
1063 : 82926 : if (!type)
1064 : : return false;
1065 : :
1066 : 82926 : Value_Range range1 (TREE_TYPE (op1));
1067 : 82926 : Value_Range range2 (TREE_TYPE (op2));
1068 : 82926 : Value_Range cond_range (TREE_TYPE (cond));
1069 : 82926 : gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR);
1070 : 82926 : gcc_checking_assert (range_compatible_p (TREE_TYPE (op1), TREE_TYPE (op2)));
1071 : 82926 : src.get_operand (cond_range, cond);
1072 : 82926 : src.get_operand (range1, op1);
1073 : 82926 : src.get_operand (range2, op2);
1074 : :
1075 : : // Try to see if there is a dependence between the COND and either operand
1076 : 82926 : if (src.gori ())
1077 : 50750 : if (src.gori ()->condexpr_adjust (range1, range2, s, cond, op1, op2, src))
1078 : 14692 : if (dump_file && (dump_flags & TDF_DETAILS))
1079 : : {
1080 : 0 : fprintf (dump_file, "Possible COND_EXPR adjustment. Range op1 : ");
1081 : 0 : range1.dump(dump_file);
1082 : 0 : fprintf (dump_file, " and Range op2: ");
1083 : 0 : range2.dump(dump_file);
1084 : 0 : fprintf (dump_file, "\n");
1085 : : }
1086 : :
1087 : : // If the condition is known, choose the appropriate expression.
1088 : 82926 : if (cond_range.singleton_p ())
1089 : : {
1090 : : // False, pick second operand.
1091 : 2173 : if (cond_range.zero_p ())
1092 : 1213 : r = range2;
1093 : : else
1094 : 960 : r = range1;
1095 : : }
1096 : : else
1097 : : {
1098 : 80753 : r = range1;
1099 : 80753 : r.union_ (range2);
1100 : : }
1101 : 82926 : gcc_checking_assert (r.undefined_p ()
1102 : : || range_compatible_p (r.type (), type));
1103 : 82926 : return true;
1104 : 82926 : }
1105 : :
1106 : : // If SCEV has any information about phi node NAME, return it as a range in R.
1107 : :
1108 : : void
1109 : 7584757 : fold_using_range::range_of_ssa_name_with_loop_info (vrange &r, tree name,
1110 : : class loop *l, gphi *phi,
1111 : : fur_source &src)
1112 : : {
1113 : 7584757 : gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
1114 : 7584757 : if (!range_of_var_in_loop (r, name, l, phi, src.query ()))
1115 : 138 : r.set_varying (TREE_TYPE (name));
1116 : 7584757 : }
1117 : :
1118 : : // -----------------------------------------------------------------------
1119 : :
1120 : : // Check if an && or || expression can be folded based on relations. ie
1121 : : // c_2 = a_6 > b_7
1122 : : // c_3 = a_6 < b_7
1123 : : // c_4 = c_2 && c_3
1124 : : // c_2 and c_3 can never be true at the same time,
1125 : : // Therefore c_4 can always resolve to false based purely on the relations.
1126 : :
1127 : : void
1128 : 114268128 : fold_using_range::relation_fold_and_or (irange& lhs_range, gimple *s,
1129 : : fur_source &src, vrange &op1,
1130 : : vrange &op2)
1131 : : {
1132 : : // No queries or already folded.
1133 : 114268128 : if (!src.gori () || !src.query ()->oracle () || lhs_range.singleton_p ())
1134 : 35883123 : return;
1135 : :
1136 : : // Only care about AND and OR expressions.
1137 : 78385005 : enum tree_code code = gimple_expr_code (s);
1138 : 78385005 : bool is_and = false;
1139 : 78385005 : if (code == BIT_AND_EXPR || code == TRUTH_AND_EXPR)
1140 : : is_and = true;
1141 : 75080072 : else if (code != BIT_IOR_EXPR && code != TRUTH_OR_EXPR)
1142 : : return;
1143 : :
1144 : 4880752 : gimple_range_op_handler handler (s);
1145 : 4880752 : tree lhs = handler.lhs ();
1146 : 4880752 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
1147 : 4880752 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
1148 : :
1149 : : // Deal with || and && only when there is a full set of symbolics.
1150 : 4880596 : if (!lhs || !ssa1 || !ssa2
1151 : 2787637 : || (TREE_CODE (TREE_TYPE (lhs)) != BOOLEAN_TYPE)
1152 : 2045351 : || (TREE_CODE (TREE_TYPE (ssa1)) != BOOLEAN_TYPE)
1153 : 6925475 : || (TREE_CODE (TREE_TYPE (ssa2)) != BOOLEAN_TYPE))
1154 : : return;
1155 : :
1156 : : // Now we know its a boolean AND or OR expression with boolean operands.
1157 : : // Ideally we search dependencies for common names, and see what pops out.
1158 : : // until then, simply try to resolve direct dependencies.
1159 : :
1160 : 2041462 : gimple *ssa1_stmt = SSA_NAME_DEF_STMT (ssa1);
1161 : 2041462 : gimple *ssa2_stmt = SSA_NAME_DEF_STMT (ssa2);
1162 : :
1163 : 2041462 : gimple_range_op_handler handler1 (ssa1_stmt);
1164 : 2041462 : gimple_range_op_handler handler2 (ssa2_stmt);
1165 : :
1166 : : // If either handler is not present, no relation can be found.
1167 : 2041462 : if (!handler1 || !handler2)
1168 : 144940 : return;
1169 : :
1170 : : // Both stmts will need to have 2 ssa names in the stmt.
1171 : 1896522 : tree ssa1_dep1 = gimple_range_ssa_p (handler1.operand1 ());
1172 : 1896522 : tree ssa1_dep2 = gimple_range_ssa_p (handler1.operand2 ());
1173 : 1896522 : tree ssa2_dep1 = gimple_range_ssa_p (handler2.operand1 ());
1174 : 1896522 : tree ssa2_dep2 = gimple_range_ssa_p (handler2.operand2 ());
1175 : :
1176 : 1896522 : if (!ssa1_dep1 || !ssa1_dep2 || !ssa2_dep1 || !ssa2_dep2)
1177 : : return;
1178 : :
1179 : 223319 : if (HONOR_NANS (TREE_TYPE (ssa1_dep1)))
1180 : : return;
1181 : :
1182 : : // Make sure they are the same dependencies, and detect the order of the
1183 : : // relationship.
1184 : 211083 : bool reverse_op2 = true;
1185 : 211083 : if (ssa1_dep1 == ssa2_dep1 && ssa1_dep2 == ssa2_dep2)
1186 : : reverse_op2 = false;
1187 : 211071 : else if (ssa1_dep1 != ssa2_dep2 || ssa1_dep2 != ssa2_dep1)
1188 : : return;
1189 : :
1190 : 12 : int_range<2> bool_one = range_true ();
1191 : 12 : relation_kind relation1 = handler1.op1_op2_relation (bool_one, op1, op2);
1192 : 12 : relation_kind relation2 = handler2.op1_op2_relation (bool_one, op1, op2);
1193 : 12 : if (relation1 == VREL_VARYING || relation2 == VREL_VARYING)
1194 : : return;
1195 : :
1196 : 12 : if (reverse_op2)
1197 : 0 : relation2 = relation_negate (relation2);
1198 : :
1199 : : // x && y is false if the relation intersection of the true cases is NULL.
1200 : 12 : if (is_and && relation_intersect (relation1, relation2) == VREL_UNDEFINED)
1201 : 0 : lhs_range = range_false (boolean_type_node);
1202 : : // x || y is true if the union of the true cases is NO-RELATION..
1203 : : // ie, one or the other being true covers the full range of possibilities.
1204 : 12 : else if (!is_and && relation_union (relation1, relation2) == VREL_VARYING)
1205 : 0 : lhs_range = bool_one;
1206 : : else
1207 : 12 : return;
1208 : :
1209 : 0 : range_cast (lhs_range, TREE_TYPE (lhs));
1210 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1211 : : {
1212 : 0 : fprintf (dump_file, " Relation adjustment: ");
1213 : 0 : print_generic_expr (dump_file, ssa1, TDF_SLIM);
1214 : 0 : fprintf (dump_file, " and ");
1215 : 0 : print_generic_expr (dump_file, ssa2, TDF_SLIM);
1216 : 0 : fprintf (dump_file, " combine to produce ");
1217 : 0 : lhs_range.dump (dump_file);
1218 : 0 : fputc ('\n', dump_file);
1219 : : }
1220 : :
1221 : : return;
1222 : 12 : }
1223 : :
1224 : : // Register any outgoing edge relations from a conditional branch.
1225 : :
1226 : : void
1227 : 58764085 : fur_source::register_outgoing_edges (gcond *s, irange &lhs_range,
1228 : : edge e0, edge e1)
1229 : : {
1230 : 58764085 : int_range<2> e0_range, e1_range;
1231 : 58764085 : tree name;
1232 : 58764085 : basic_block bb = gimple_bb (s);
1233 : :
1234 : 58764085 : gimple_range_op_handler handler (s);
1235 : 58764085 : if (!handler)
1236 : : return;
1237 : :
1238 : 58747100 : if (e0)
1239 : : {
1240 : : // If this edge is never taken, ignore it.
1241 : 48862268 : gcond_edge_range (e0_range, e0);
1242 : 48862268 : e0_range.intersect (lhs_range);
1243 : 48862268 : if (e0_range.undefined_p ())
1244 : 21859793 : e0 = NULL;
1245 : : }
1246 : :
1247 : 58747100 : if (e1)
1248 : : {
1249 : : // If this edge is never taken, ignore it.
1250 : 43212300 : gcond_edge_range (e1_range, e1);
1251 : 43212300 : e1_range.intersect (lhs_range);
1252 : 43212300 : if (e1_range.undefined_p ())
1253 : 23971943 : e1 = NULL;
1254 : : }
1255 : :
1256 : 58747100 : if (!e0 && !e1)
1257 : : return;
1258 : :
1259 : : // First, register the gcond itself. This will catch statements like
1260 : : // if (a_2 < b_5)
1261 : 56290081 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
1262 : 56290081 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
1263 : 56290081 : Value_Range r1,r2;
1264 : 56290081 : if (ssa1 && ssa2)
1265 : : {
1266 : 15866220 : r1.set_varying (TREE_TYPE (ssa1));
1267 : 15866220 : r2.set_varying (TREE_TYPE (ssa2));
1268 : 15866220 : if (e0)
1269 : : {
1270 : 10385337 : relation_kind relation = handler.op1_op2_relation (e0_range, r1, r2);
1271 : 10385337 : if (relation != VREL_VARYING)
1272 : 10308170 : register_relation (e0, relation, ssa1, ssa2);
1273 : : }
1274 : 15866220 : if (e1)
1275 : : {
1276 : 9612458 : relation_kind relation = handler.op1_op2_relation (e1_range, r1, r2);
1277 : 9612458 : if (relation != VREL_VARYING)
1278 : 9551912 : register_relation (e1, relation, ssa1, ssa2);
1279 : : }
1280 : : }
1281 : :
1282 : : // Outgoing relations of GORI exports require a gori engine.
1283 : 56290081 : if (!gori ())
1284 : 10471099 : return;
1285 : :
1286 : : // Now look for other relations in the exports. This will find stmts
1287 : : // leading to the condition such as:
1288 : : // c_2 = a_4 < b_7
1289 : : // if (c_2)
1290 : 144410681 : FOR_EACH_GORI_EXPORT_NAME (*(gori ()), bb, name)
1291 : : {
1292 : 98591699 : if (TREE_CODE (TREE_TYPE (name)) != BOOLEAN_TYPE)
1293 : 92891979 : continue;
1294 : 9227848 : gimple *stmt = SSA_NAME_DEF_STMT (name);
1295 : 9227848 : gimple_range_op_handler handler (stmt);
1296 : 9227848 : if (!handler)
1297 : 3528128 : continue;
1298 : 5699720 : tree ssa1 = gimple_range_ssa_p (handler.operand1 ());
1299 : 5699720 : tree ssa2 = gimple_range_ssa_p (handler.operand2 ());
1300 : 5699720 : Value_Range r (TREE_TYPE (name));
1301 : 5699720 : if (ssa1 && ssa2)
1302 : : {
1303 : 2489304 : r1.set_varying (TREE_TYPE (ssa1));
1304 : 2489304 : r2.set_varying (TREE_TYPE (ssa2));
1305 : 1412377 : if (e0 && gori ()->outgoing_edge_range_p (r, e0, name, *m_query)
1306 : 3870851 : && r.singleton_p ())
1307 : : {
1308 : 1259521 : relation_kind relation = handler.op1_op2_relation (r, r1, r2);
1309 : 1259521 : if (relation != VREL_VARYING)
1310 : 409456 : register_relation (e0, relation, ssa1, ssa2);
1311 : : }
1312 : 1641681 : if (e1 && gori ()->outgoing_edge_range_p (r, e1, name, *m_query)
1313 : 4098670 : && r.singleton_p ())
1314 : : {
1315 : 1255155 : relation_kind relation = handler.op1_op2_relation (r, r1, r2);
1316 : 1255155 : if (relation != VREL_VARYING)
1317 : 192512 : register_relation (e1, relation, ssa1, ssa2);
1318 : : }
1319 : : }
1320 : 5699720 : }
1321 : 58764085 : }
|
