Line data Source code
1 : /* Support routines for Value Range Propagation (VRP).
2 : Copyright (C) 2005-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
6 : GCC is free software; you can redistribute it and/or modify
7 : it under the terms of the GNU General Public License as published by
8 : the Free Software Foundation; either version 3, or (at your option)
9 : any later version.
10 :
11 : GCC is distributed in the hope that it will be useful,
12 : but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : GNU General Public License for more details.
15 :
16 : You should have received a copy of the GNU General Public License
17 : along with GCC; see the file COPYING3. If not see
18 : <http://www.gnu.org/licenses/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "backend.h"
24 : #include "insn-codes.h"
25 : #include "tree.h"
26 : #include "gimple.h"
27 : #include "ssa.h"
28 : #include "optabs-tree.h"
29 : #include "gimple-pretty-print.h"
30 : #include "diagnostic-core.h"
31 : #include "flags.h"
32 : #include "fold-const.h"
33 : #include "calls.h"
34 : #include "cfganal.h"
35 : #include "gimple-iterator.h"
36 : #include "gimple-fold.h"
37 : #include "tree-cfg.h"
38 : #include "tree-ssa-loop-niter.h"
39 : #include "tree-ssa-loop.h"
40 : #include "intl.h"
41 : #include "cfgloop.h"
42 : #include "tree-scalar-evolution.h"
43 : #include "tree-ssa-propagate.h"
44 : #include "tree-chrec.h"
45 : #include "omp-general.h"
46 : #include "case-cfn-macros.h"
47 : #include "alloc-pool.h"
48 : #include "attribs.h"
49 : #include "range.h"
50 : #include "vr-values.h"
51 : #include "cfghooks.h"
52 : #include "range-op.h"
53 : #include "gimple-range.h"
54 :
55 : /* Return true if op is in a boolean [0, 1] value-range. */
56 :
57 : bool
58 513298 : simplify_using_ranges::op_with_boolean_value_range_p (tree op, gimple *s)
59 : {
60 513298 : if (TYPE_PRECISION (TREE_TYPE (op)) == 1)
61 : return true;
62 :
63 500218 : if (integer_zerop (op)
64 500218 : || integer_onep (op))
65 : return true;
66 :
67 490294 : if (TREE_CODE (op) != SSA_NAME)
68 : return false;
69 :
70 : /* ?? Errr, this should probably check for [0,0] and [1,1] as well
71 : as [0,1]. */
72 490294 : int_range_max vr;
73 490294 : return (query->range_of_expr (vr, op, s)
74 490294 : && vr == range_true_and_false (TREE_TYPE (op)));
75 490294 : }
76 :
77 : /* Helper function for simplify_internal_call_using_ranges and
78 : extract_range_basic. Return true if OP0 SUBCODE OP1 for
79 : SUBCODE {PLUS,MINUS,MULT}_EXPR is known to never overflow or
80 : always overflow. Set *OVF to true if it is known to always
81 : overflow. */
82 :
83 : static bool
84 144482 : check_for_binary_op_overflow (range_query *query,
85 : enum tree_code subcode, tree type,
86 : tree op0, tree op1, bool *ovf, gimple *s = NULL)
87 : {
88 144482 : relation_kind rel = VREL_VARYING;
89 : /* For subtraction see if relations could simplify it. */
90 144482 : if (s
91 144482 : && subcode == MINUS_EXPR
92 144482 : && types_compatible_p (TREE_TYPE (op0), TREE_TYPE (op1)))
93 : {
94 29039 : rel = query->relation().query (s, op0, op1);
95 : /* The result of the infinite precision subtraction of
96 : the same values will be always 0. That will fit into any result
97 : type. */
98 29039 : if (rel == VREL_EQ)
99 : return true;
100 : }
101 :
102 144481 : int_range_max vr0, vr1;
103 144481 : if (!query->range_of_expr (vr0, op0, s) || vr0.undefined_p ())
104 12 : vr0.set_varying (TREE_TYPE (op0));
105 144481 : if (!query->range_of_expr (vr1, op1, s) || vr1.undefined_p ())
106 8 : vr1.set_varying (TREE_TYPE (op1));
107 :
108 144481 : tree vr0min = wide_int_to_tree (TREE_TYPE (op0), vr0.lower_bound ());
109 144481 : tree vr0max = wide_int_to_tree (TREE_TYPE (op0), vr0.upper_bound ());
110 144481 : tree vr1min = wide_int_to_tree (TREE_TYPE (op1), vr1.lower_bound ());
111 144481 : tree vr1max = wide_int_to_tree (TREE_TYPE (op1), vr1.upper_bound ());
112 :
113 : /* If op1 is not negative, op0 - op1 in infinite precision for op0 >= op1
114 : will be always in [0, op0] and so if vr0max - vr1min fits into type,
115 : there won't be any overflow. */
116 144481 : if ((rel == VREL_GT || rel == VREL_GE)
117 28 : && tree_int_cst_sgn (vr1min) >= 0
118 144503 : && !arith_overflowed_p (MINUS_EXPR, type, vr0max, vr1min))
119 : return true;
120 :
121 : /* If op1 is not negative, op0 - op1 in infinite precision for op0 < op1
122 : will be always in [-inf, -1] and so will always overflow if type is
123 : unsigned. */
124 144459 : if (rel == VREL_LT
125 1 : && tree_int_cst_sgn (vr1min) >= 0
126 144460 : && TYPE_UNSIGNED (type))
127 : {
128 1 : *ovf = true;
129 1 : return true;
130 : }
131 :
132 237086 : *ovf = arith_overflowed_p (subcode, type, vr0min,
133 : subcode == MINUS_EXPR ? vr1max : vr1min);
134 237086 : if (arith_overflowed_p (subcode, type, vr0max,
135 144458 : subcode == MINUS_EXPR ? vr1min : vr1max) != *ovf)
136 : return false;
137 39554 : if (subcode == MULT_EXPR)
138 : {
139 23973 : if (arith_overflowed_p (subcode, type, vr0min, vr1max) != *ovf
140 23973 : || arith_overflowed_p (subcode, type, vr0max, vr1min) != *ovf)
141 : return false;
142 : }
143 39178 : if (*ovf)
144 : {
145 : /* So far we found that there is an overflow on the boundaries.
146 : That doesn't prove that there is an overflow even for all values
147 : in between the boundaries. For that compute widest2_int range
148 : of the result and see if it doesn't overlap the range of
149 : type. */
150 37194 : widest2_int wmin, wmax;
151 334938 : widest2_int w[4];
152 37194 : int i;
153 37194 : signop sign0 = TYPE_SIGN (TREE_TYPE (op0));
154 37194 : signop sign1 = TYPE_SIGN (TREE_TYPE (op1));
155 37245 : w[0] = widest2_int::from (vr0.lower_bound (), sign0);
156 37253 : w[1] = widest2_int::from (vr0.upper_bound (), sign0);
157 37231 : w[2] = widest2_int::from (vr1.lower_bound (), sign1);
158 37239 : w[3] = widest2_int::from (vr1.upper_bound (), sign1);
159 185970 : for (i = 0; i < 4; i++)
160 : {
161 148776 : widest2_int wt;
162 148776 : switch (subcode)
163 : {
164 27228 : case PLUS_EXPR:
165 27228 : wt = wi::add (w[i & 1], w[2 + (i & 2) / 2]);
166 27228 : break;
167 27904 : case MINUS_EXPR:
168 27904 : wt = wi::sub (w[i & 1], w[2 + (i & 2) / 2]);
169 27904 : break;
170 93644 : case MULT_EXPR:
171 93644 : wt = wi::mul (w[i & 1], w[2 + (i & 2) / 2]);
172 93644 : break;
173 0 : default:
174 0 : gcc_unreachable ();
175 : }
176 148776 : if (i == 0)
177 : {
178 37194 : wmin = wt;
179 37194 : wmax = wt;
180 : }
181 : else
182 : {
183 111582 : wmin = wi::smin (wmin, wt);
184 112432 : wmax = wi::smax (wmax, wt);
185 : }
186 148776 : }
187 : /* The result of op0 CODE op1 is known to be in range
188 : [wmin, wmax]. */
189 37194 : widest2_int wtmin
190 74388 : = widest2_int::from (irange_val_min (type), TYPE_SIGN (type));
191 37194 : widest2_int wtmax
192 74388 : = widest2_int::from (irange_val_max (type), TYPE_SIGN (type));
193 : /* If all values in [wmin, wmax] are smaller than
194 : [wtmin, wtmax] or all are larger than [wtmin, wtmax],
195 : the arithmetic operation will always overflow. */
196 73378 : if (wmax < wtmin || wmin > wtmax)
197 1661 : return true;
198 : return false;
199 223444 : }
200 : return true;
201 144481 : }
202 :
203 : /* Set INIT, STEP, and DIRECTION to the corresponding values of NAME
204 : within LOOP, and return TRUE. Otherwise return FALSE, and set R to
205 : the conservative range of NAME within the loop. */
206 :
207 : static bool
208 6077739 : get_scev_info (vrange &r, tree name, gimple *stmt, class loop *l,
209 : tree &init, tree &step, enum ev_direction &dir)
210 : {
211 6077739 : tree ev = analyze_scalar_evolution (l, name);
212 6077739 : tree chrec = instantiate_parameters (l, ev);
213 6077739 : tree type = TREE_TYPE (name);
214 6077739 : if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
215 : {
216 2855920 : r.set_varying (type);
217 2855920 : return false;
218 : }
219 3221819 : if (is_gimple_min_invariant (chrec))
220 : {
221 0 : if (is_gimple_constant (chrec))
222 0 : r.set (chrec, chrec);
223 : else
224 0 : r.set_varying (type);
225 : return false;
226 : }
227 :
228 3221819 : init = initial_condition_in_loop_num (chrec, l->num);
229 3221819 : step = evolution_part_in_loop_num (chrec, l->num);
230 3221819 : if (!init || !step)
231 : {
232 0 : r.set_varying (type);
233 0 : return false;
234 : }
235 3221819 : dir = scev_direction (chrec);
236 3221819 : if (dir == EV_DIR_UNKNOWN
237 3221819 : || scev_probably_wraps_p (NULL, init, step, stmt,
238 : get_chrec_loop (chrec), true))
239 : {
240 549644 : r.set_varying (type);
241 549644 : return false;
242 : }
243 : return true;
244 : }
245 :
246 : /* Return TRUE if STEP * NIT may overflow when calculated in TYPE. */
247 :
248 : static bool
249 2246097 : induction_variable_may_overflow_p (tree type,
250 : const wide_int &step, const widest_int &nit)
251 : {
252 2246097 : wi::overflow_type ovf;
253 2246097 : signop sign = TYPE_SIGN (type);
254 2246097 : widest_int max_step = wi::mul (widest_int::from (step, sign),
255 2246097 : nit, sign, &ovf);
256 :
257 2246097 : if (ovf || !wi::fits_to_tree_p (max_step, type))
258 : return true;
259 :
260 : /* For a signed type we have to check whether the result has the
261 : expected signedness which is that of the step as number of
262 : iterations is unsigned. */
263 2124604 : return (sign == SIGNED
264 4248570 : && wi::gts_p (max_step, 0) != wi::gts_p (step, 0));
265 2246097 : }
266 :
267 : /* Set R to the range from BEGIN to END, assuming the direction of the
268 : loop is DIR. */
269 :
270 : static void
271 2671327 : range_from_loop_direction (irange &r, tree type,
272 : const irange &begin, const irange &end,
273 : ev_direction dir)
274 : {
275 2671327 : signop sign = TYPE_SIGN (type);
276 :
277 2671327 : if (begin.undefined_p () || end.undefined_p ())
278 3652 : r.set_varying (type);
279 2667675 : else if (dir == EV_DIR_GROWS)
280 : {
281 2391286 : if (wi::ge_p (begin.lower_bound (), end.upper_bound (), sign))
282 212 : r.set_varying (type);
283 : else
284 2391074 : r = int_range<1> (type, begin.lower_bound (), end.upper_bound ());
285 : }
286 : else
287 : {
288 276411 : if (wi::ge_p (end.lower_bound (), begin.upper_bound (), sign))
289 223 : r.set_varying (type);
290 : else
291 276188 : r = int_range<1> (type, end.lower_bound (), begin.upper_bound ());
292 : }
293 2671327 : }
294 :
295 : /* Set V to the range of NAME in STMT within LOOP. Return TRUE if a
296 : range was found. */
297 :
298 : bool
299 6077739 : range_of_var_in_loop (vrange &v, tree name, class loop *l, gimple *stmt,
300 : range_query *query)
301 : {
302 6077739 : tree init, step;
303 6077739 : enum ev_direction dir;
304 6077739 : if (!get_scev_info (v, name, stmt, l, init, step, dir))
305 : return true;
306 :
307 : // Calculate ranges for the values from SCEV.
308 2672175 : irange &r = as_a <irange> (v);
309 2672175 : tree type = TREE_TYPE (init);
310 2672175 : int_range<2> rinit (type), rstep (type), max_init (type);
311 2672175 : if (!query->range_of_expr (rinit, init, stmt)
312 2672175 : || !query->range_of_expr (rstep, step, stmt))
313 : return false;
314 :
315 : // Calculate the final range of NAME if possible.
316 2672175 : if (rinit.singleton_p () && rstep.singleton_p ())
317 : {
318 2246945 : widest_int nit;
319 2246945 : if (!max_loop_iterations (l, &nit))
320 : return false;
321 :
322 2246098 : if (!induction_variable_may_overflow_p (type, rstep.lower_bound (), nit))
323 : {
324 : // Calculate the max bounds for init (init + niter * step).
325 2123966 : wide_int w = wide_int::from (nit, TYPE_PRECISION (type), TYPE_SIGN (type));
326 2123966 : int_range<1> niter (type, w, w);
327 2123966 : int_range_max max_step;
328 2123966 : range_op_handler mult_handler (MULT_EXPR);
329 2123966 : range_op_handler plus_handler (PLUS_EXPR);
330 2123966 : if (!mult_handler.fold_range (max_step, type, niter, rstep)
331 2123966 : || !plus_handler.fold_range (max_init, type, rinit, max_step))
332 0 : return false;
333 2123967 : }
334 2246945 : }
335 2671327 : range_from_loop_direction (r, type, rinit, max_init, dir);
336 2671327 : return true;
337 2672175 : }
338 :
339 : /* Helper function for vrp_evaluate_conditional_warnv & other
340 : optimizers. */
341 :
342 : tree
343 21218521 : simplify_using_ranges::fold_cond_with_ops (enum tree_code code,
344 : tree op0, tree op1, gimple *s)
345 : {
346 21218521 : value_range r0 (TREE_TYPE (op0));
347 21218521 : value_range r1 (TREE_TYPE (op1));
348 21218521 : if (!query->range_of_expr (r0, op0, s)
349 21218521 : || !query->range_of_expr (r1, op1, s))
350 : return NULL_TREE;
351 :
352 21211017 : int_range<1> res;
353 21211017 : range_op_handler handler (code);
354 :
355 : // Find any relation between op0 and op1 and pass it to fold_range.
356 21211017 : relation_kind rel = VREL_VARYING;
357 21211017 : if (gimple_range_ssa_p (op0) && gimple_range_ssa_p (op1))
358 4660237 : rel = query->relation ().query (s, op0, op1);
359 :
360 21211017 : if (handler && handler.fold_range (res, boolean_type_node, r0, r1,
361 : relation_trio::op1_op2 (rel)))
362 : {
363 21211017 : if (res == range_true ())
364 8724 : return boolean_true_node;
365 21202293 : if (res == range_false ())
366 3318 : return boolean_false_node;
367 : }
368 : return NULL;
369 21218521 : }
370 :
371 : /* Helper function for legacy_fold_cond. */
372 :
373 : tree
374 21530799 : simplify_using_ranges::legacy_fold_cond_overflow (gimple *stmt)
375 : {
376 21530799 : tree ret;
377 21530799 : tree_code code = gimple_cond_code (stmt);
378 21530799 : tree op0 = gimple_cond_lhs (stmt);
379 21530799 : tree op1 = gimple_cond_rhs (stmt);
380 :
381 : /* We only deal with integral and pointer types. */
382 42692952 : if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
383 26356210 : && !POINTER_TYPE_P (TREE_TYPE (op0)))
384 : return NULL_TREE;
385 :
386 : /* If OP0 CODE OP1 is an overflow comparison, if it can be expressed
387 : as a simple equality test, then prefer that over its current form
388 : for evaluation.
389 :
390 : An overflow test which collapses to an equality test can always be
391 : expressed as a comparison of one argument against zero. Overflow
392 : occurs when the chosen argument is zero and does not occur if the
393 : chosen argument is not zero. */
394 20665034 : tree x;
395 20665034 : if (overflow_comparison_p (code, op0, op1, &x))
396 : {
397 1163 : wide_int max = wi::max_value (TYPE_PRECISION (TREE_TYPE (op0)), UNSIGNED);
398 : /* B = A - 1; if (A < B) -> B = A - 1; if (A == 0)
399 : B = A - 1; if (A > B) -> B = A - 1; if (A != 0)
400 : B = A + 1; if (B < A) -> B = A + 1; if (B == 0)
401 : B = A + 1; if (B > A) -> B = A + 1; if (B != 0) */
402 1163 : if (integer_zerop (x))
403 : {
404 170 : op1 = x;
405 170 : code = (code == LT_EXPR || code == LE_EXPR) ? EQ_EXPR : NE_EXPR;
406 : }
407 : /* B = A + 1; if (A > B) -> B = A + 1; if (B == 0)
408 : B = A + 1; if (A < B) -> B = A + 1; if (B != 0)
409 : B = A - 1; if (B > A) -> B = A - 1; if (A == 0)
410 : B = A - 1; if (B < A) -> B = A - 1; if (A != 0) */
411 993 : else if (wi::to_wide (x) == max - 1)
412 : {
413 651 : op0 = op1;
414 651 : op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
415 651 : code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
416 : }
417 : else
418 : {
419 342 : int_range_max vro, vri;
420 342 : tree type = TREE_TYPE (op0);
421 342 : if (code == GT_EXPR || code == GE_EXPR)
422 : {
423 92 : vro.set (type,
424 184 : wi::to_wide (TYPE_MIN_VALUE (type)),
425 92 : wi::to_wide (x), VR_ANTI_RANGE);
426 92 : vri.set (type,
427 184 : wi::to_wide (TYPE_MIN_VALUE (type)),
428 184 : wi::to_wide (x));
429 : }
430 250 : else if (code == LT_EXPR || code == LE_EXPR)
431 : {
432 250 : vro.set (type,
433 500 : wi::to_wide (TYPE_MIN_VALUE (type)),
434 250 : wi::to_wide (x));
435 250 : vri.set (type,
436 500 : wi::to_wide (TYPE_MIN_VALUE (type)),
437 500 : wi::to_wide (x),
438 : VR_ANTI_RANGE);
439 : }
440 : else
441 0 : gcc_unreachable ();
442 342 : int_range_max vr0;
443 342 : if (!query->range_of_expr (vr0, op0, stmt))
444 0 : vr0.set_varying (TREE_TYPE (op0));
445 : /* If vro, the range for OP0 to pass the overflow test, has
446 : no intersection with *vr0, OP0's known range, then the
447 : overflow test can't pass, so return the node for false.
448 : If it is the inverted range, vri, that has no
449 : intersection, then the overflow test must pass, so return
450 : the node for true. In other cases, we could proceed with
451 : a simplified condition comparing OP0 and X, with LE_EXPR
452 : for previously LE_ or LT_EXPR and GT_EXPR otherwise, but
453 : the comments next to the enclosing if suggest it's not
454 : generally profitable to do so. */
455 342 : vro.intersect (vr0);
456 342 : if (vro.undefined_p ())
457 8 : return boolean_false_node;
458 334 : vri.intersect (vr0);
459 334 : if (vri.undefined_p ())
460 0 : return boolean_true_node;
461 342 : }
462 1163 : }
463 :
464 20665026 : if ((ret = fold_cond_with_ops (code, op0, op1, stmt)))
465 : return ret;
466 : return NULL_TREE;
467 : }
468 :
469 : /* Visit conditional statement STMT. If we can determine which edge
470 : will be taken out of STMT's basic block, record it in
471 : *TAKEN_EDGE_P. Otherwise, set *TAKEN_EDGE_P to NULL. */
472 :
473 : void
474 21530799 : simplify_using_ranges::legacy_fold_cond (gcond *stmt, edge *taken_edge_p)
475 : {
476 21530799 : tree val;
477 :
478 21530799 : *taken_edge_p = NULL;
479 :
480 21530799 : if (dump_file && (dump_flags & TDF_DETAILS))
481 : {
482 390 : tree use;
483 390 : ssa_op_iter i;
484 :
485 390 : fprintf (dump_file, "\nVisiting conditional with predicate: ");
486 390 : print_gimple_stmt (dump_file, stmt, 0);
487 390 : fprintf (dump_file, "\nWith known ranges\n");
488 :
489 869 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
490 : {
491 479 : fprintf (dump_file, "\t");
492 479 : print_generic_expr (dump_file, use);
493 479 : fprintf (dump_file, ": ");
494 479 : value_range r (TREE_TYPE (use));
495 479 : query->range_of_expr (r, use, stmt);
496 479 : r.dump (dump_file);
497 479 : }
498 :
499 390 : fprintf (dump_file, "\n");
500 : }
501 :
502 21530799 : val = legacy_fold_cond_overflow (stmt);
503 21530799 : if (val)
504 8 : *taken_edge_p = find_taken_edge (gimple_bb (stmt), val);
505 :
506 21530799 : if (dump_file && (dump_flags & TDF_DETAILS))
507 : {
508 390 : fprintf (dump_file, "\nPredicate evaluates to: ");
509 390 : if (val == NULL_TREE)
510 390 : fprintf (dump_file, "DON'T KNOW\n");
511 : else
512 0 : print_generic_stmt (dump_file, val);
513 : }
514 21530799 : }
515 :
516 : /* Simplify boolean operations if the source is known
517 : to be already a boolean. */
518 : bool
519 496244 : simplify_using_ranges::simplify_truth_ops_using_ranges
520 : (gimple_stmt_iterator *gsi,
521 : gimple *stmt)
522 : {
523 496244 : enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
524 496244 : tree lhs, op0, op1;
525 496244 : bool need_conversion;
526 :
527 : /* We handle only !=/== case here. */
528 496244 : gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR);
529 :
530 496244 : op0 = gimple_assign_rhs1 (stmt);
531 496244 : if (!op_with_boolean_value_range_p (op0, stmt))
532 : return false;
533 :
534 17054 : op1 = gimple_assign_rhs2 (stmt);
535 17054 : if (!op_with_boolean_value_range_p (op1, stmt))
536 : return false;
537 :
538 : /* Reduce number of cases to handle to NE_EXPR. As there is no
539 : BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
540 16538 : if (rhs_code == EQ_EXPR)
541 : {
542 8253 : if (TREE_CODE (op1) == INTEGER_CST)
543 3512 : op1 = int_const_binop (BIT_XOR_EXPR, op1,
544 7024 : build_int_cst (TREE_TYPE (op1), 1));
545 : else
546 : return false;
547 : }
548 :
549 11797 : lhs = gimple_assign_lhs (stmt);
550 11797 : need_conversion
551 11797 : = !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0));
552 :
553 : /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
554 11797 : if (need_conversion
555 10409 : && !TYPE_UNSIGNED (TREE_TYPE (op0))
556 3898 : && TYPE_PRECISION (TREE_TYPE (op0)) == 1
557 11819 : && TYPE_PRECISION (TREE_TYPE (lhs)) > 1)
558 : return false;
559 :
560 : /* For A != 0 we can substitute A itself. */
561 11797 : if (integer_zerop (op1))
562 7133 : gimple_assign_set_rhs_with_ops (gsi,
563 : need_conversion
564 0 : ? NOP_EXPR : TREE_CODE (op0), op0);
565 : /* For A != B we substitute A ^ B. Either with conversion. */
566 4664 : else if (need_conversion)
567 : {
568 3276 : tree tem = make_ssa_name (TREE_TYPE (op0));
569 3276 : gassign *newop
570 3276 : = gimple_build_assign (tem, BIT_XOR_EXPR, op0, op1);
571 3276 : gsi_insert_before (gsi, newop, GSI_SAME_STMT);
572 6526 : if (INTEGRAL_TYPE_P (TREE_TYPE (tem))
573 6526 : && TYPE_PRECISION (TREE_TYPE (tem)) > 1)
574 : {
575 6378 : int_range<1> vr (TREE_TYPE (tem),
576 6378 : wi::zero (TYPE_PRECISION (TREE_TYPE (tem))),
577 6378 : wi::one (TYPE_PRECISION (TREE_TYPE (tem))));
578 3189 : set_range_info (tem, vr);
579 3189 : }
580 3276 : gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem);
581 : }
582 : /* Or without. */
583 : else
584 1388 : gimple_assign_set_rhs_with_ops (gsi, BIT_XOR_EXPR, op0, op1);
585 11797 : update_stmt (gsi_stmt (*gsi));
586 11797 : fold_stmt (gsi, follow_single_use_edges);
587 :
588 11797 : return true;
589 : }
590 :
591 : /* Simplify a division or modulo operator to a right shift or bitwise and
592 : if the first operand is unsigned or is greater than zero and the second
593 : operand is an exact power of two. For TRUNC_MOD_EXPR op0 % op1 with
594 : constant op1 (op1min = op1) or with op1 in [op1min, op1max] range,
595 : optimize it into just op0 if op0's range is known to be a subset of
596 : [-op1min + 1, op1min - 1] for signed and [0, op1min - 1] for unsigned
597 : modulo. */
598 :
599 : bool
600 337094 : simplify_using_ranges::simplify_div_or_mod_using_ranges
601 : (gimple_stmt_iterator *gsi,
602 : gimple *stmt)
603 : {
604 337094 : enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
605 337094 : tree val = NULL;
606 337094 : tree op0 = gimple_assign_rhs1 (stmt);
607 337094 : tree op1 = gimple_assign_rhs2 (stmt);
608 337094 : tree op0min = NULL_TREE, op0max = NULL_TREE;
609 337094 : tree op1min = op1;
610 337094 : int_range_max vr;
611 :
612 337094 : if (TREE_CODE (op0) == INTEGER_CST)
613 : {
614 : op0min = op0;
615 : op0max = op0;
616 : }
617 : else
618 : {
619 310940 : if (!query->range_of_expr (vr, op0, stmt))
620 0 : vr.set_varying (TREE_TYPE (op0));
621 310940 : if (!vr.varying_p () && !vr.undefined_p ())
622 : {
623 154724 : tree type = vr.type ();
624 154724 : op0min = wide_int_to_tree (type, vr.lower_bound ());
625 154733 : op0max = wide_int_to_tree (type, vr.upper_bound ());
626 : }
627 : }
628 :
629 337094 : if (rhs_code == TRUNC_MOD_EXPR
630 158401 : && TREE_CODE (op1) == SSA_NAME)
631 : {
632 103477 : int_range_max vr1;
633 103477 : if (!query->range_of_expr (vr1, op1, stmt))
634 0 : vr1.set_varying (TREE_TYPE (op1));
635 103477 : if (!vr1.varying_p () && !vr1.undefined_p ())
636 27120 : op1min = wide_int_to_tree (vr1.type (), vr1.lower_bound ());
637 103477 : }
638 158401 : if (rhs_code == TRUNC_MOD_EXPR
639 158401 : && TREE_CODE (op1min) == INTEGER_CST
640 82040 : && tree_int_cst_sgn (op1min) == 1
641 60405 : && op0max
642 34804 : && tree_int_cst_lt (op0max, op1min))
643 : {
644 1218 : if (TYPE_UNSIGNED (TREE_TYPE (op0))
645 530 : || tree_int_cst_sgn (op0min) >= 0
646 1447 : || tree_int_cst_lt (fold_unary (NEGATE_EXPR, TREE_TYPE (op1min), op1min),
647 : op0min))
648 : {
649 : /* If op0 already has the range op0 % op1 has,
650 : then TRUNC_MOD_EXPR won't change anything. */
651 1181 : gimple_assign_set_rhs_from_tree (gsi, op0);
652 1181 : return true;
653 : }
654 : }
655 :
656 335913 : if (TREE_CODE (op0) != SSA_NAME)
657 : return false;
658 :
659 309759 : if (!integer_pow2p (op1))
660 : {
661 : /* X % -Y can be only optimized into X % Y either if
662 : X is not INT_MIN, or Y is not -1. Fold it now, as after
663 : remove_range_assertions the range info might be not available
664 : anymore. */
665 269346 : if (rhs_code == TRUNC_MOD_EXPR
666 269346 : && fold_stmt (gsi, follow_single_use_edges))
667 12 : return true;
668 : return false;
669 : }
670 :
671 40413 : if (TYPE_UNSIGNED (TREE_TYPE (op0)))
672 0 : val = integer_one_node;
673 : else
674 : {
675 40413 : tree zero = build_zero_cst (TREE_TYPE (op0));
676 40413 : val = fold_cond_with_ops (GE_EXPR, op0, zero, stmt);
677 : }
678 :
679 40413 : if (val && integer_onep (val))
680 : {
681 6643 : tree t;
682 :
683 6643 : if (rhs_code == TRUNC_DIV_EXPR)
684 : {
685 4380 : t = build_int_cst (integer_type_node, tree_log2 (op1));
686 4380 : gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR);
687 4380 : gimple_assign_set_rhs1 (stmt, op0);
688 4380 : gimple_assign_set_rhs2 (stmt, t);
689 : }
690 : else
691 : {
692 2263 : t = build_int_cst (TREE_TYPE (op1), 1);
693 2263 : t = int_const_binop (MINUS_EXPR, op1, t);
694 2263 : t = fold_convert (TREE_TYPE (op0), t);
695 :
696 2263 : gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR);
697 2263 : gimple_assign_set_rhs1 (stmt, op0);
698 2263 : gimple_assign_set_rhs2 (stmt, t);
699 : }
700 :
701 6643 : update_stmt (stmt);
702 6643 : fold_stmt (gsi, follow_single_use_edges);
703 6643 : return true;
704 : }
705 :
706 : return false;
707 337094 : }
708 :
709 : /* Simplify a min or max if the ranges of the two operands are
710 : disjoint. Return true if we do simplify. */
711 :
712 : bool
713 249369 : simplify_using_ranges::simplify_min_or_max_using_ranges
714 : (gimple_stmt_iterator *gsi,
715 : gimple *stmt)
716 : {
717 249369 : tree op0 = gimple_assign_rhs1 (stmt);
718 249369 : tree op1 = gimple_assign_rhs2 (stmt);
719 249369 : tree val;
720 :
721 249369 : val = fold_cond_with_ops (LE_EXPR, op0, op1, stmt);
722 249369 : if (!val)
723 245213 : val = fold_cond_with_ops (LT_EXPR, op0, op1, stmt);
724 :
725 245213 : if (val)
726 : {
727 : /* VAL == TRUE -> OP0 < or <= op1
728 : VAL == FALSE -> OP0 > or >= op1. */
729 5032 : tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR)
730 5032 : == integer_zerop (val)) ? op0 : op1;
731 5032 : gimple_assign_set_rhs_from_tree (gsi, res);
732 5032 : return true;
733 : }
734 :
735 : return false;
736 : }
737 :
738 : /* If the operand to an ABS_EXPR is >= 0, then eliminate the
739 : ABS_EXPR. If the operand is <= 0, then simplify the
740 : ABS_EXPR into a NEGATE_EXPR. */
741 :
742 : bool
743 9375 : simplify_using_ranges::simplify_abs_using_ranges (gimple_stmt_iterator *gsi,
744 : gimple *stmt)
745 : {
746 9375 : tree op = gimple_assign_rhs1 (stmt);
747 9375 : tree zero = build_zero_cst (TREE_TYPE (op));
748 9375 : tree val = fold_cond_with_ops (LE_EXPR, op, zero, stmt);
749 :
750 9375 : if (!val)
751 : {
752 : /* The range is neither <= 0 nor > 0. Now see if it is
753 : either < 0 or >= 0. */
754 9125 : val = fold_cond_with_ops (LT_EXPR, op, zero, stmt);
755 : }
756 9125 : if (val)
757 : {
758 366 : gimple_assign_set_rhs1 (stmt, op);
759 366 : if (integer_zerop (val))
760 166 : gimple_assign_set_rhs_code (stmt, SSA_NAME);
761 : else
762 200 : gimple_assign_set_rhs_code (stmt, NEGATE_EXPR);
763 366 : update_stmt (stmt);
764 366 : fold_stmt (gsi, follow_single_use_edges);
765 366 : return true;
766 : }
767 : return false;
768 : }
769 :
770 : /* irange wrapper for wi_set_zero_nonzero_bits.
771 :
772 : Return TRUE if VR was a constant range and we were able to compute
773 : the bit masks. */
774 :
775 : static bool
776 1649058 : vr_set_zero_nonzero_bits (const tree expr_type,
777 : const irange *vr,
778 : wide_int *may_be_nonzero,
779 : wide_int *must_be_nonzero)
780 : {
781 1649058 : if (vr->varying_p () || vr->undefined_p ())
782 : {
783 970105 : *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type));
784 970105 : *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type));
785 970105 : return false;
786 : }
787 678955 : wi_set_zero_nonzero_bits (expr_type, vr->lower_bound (), vr->upper_bound (),
788 : *may_be_nonzero, *must_be_nonzero);
789 678953 : return true;
790 : }
791 :
792 : /* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
793 : If all the bits that are being cleared by & are already
794 : known to be zero from VR, or all the bits that are being
795 : set by | are already known to be one from VR, the bit
796 : operation is redundant. */
797 :
798 : bool
799 1288401 : simplify_using_ranges::simplify_bit_ops_using_ranges
800 : (gimple_stmt_iterator *gsi,
801 : gimple *stmt)
802 : {
803 1288401 : tree op0 = gimple_assign_rhs1 (stmt);
804 1288401 : tree op1 = gimple_assign_rhs2 (stmt);
805 1288401 : tree op = NULL_TREE;
806 1288401 : int_range_max vr0, vr1;
807 1288401 : wide_int may_be_nonzero0, may_be_nonzero1;
808 1288401 : wide_int must_be_nonzero0, must_be_nonzero1;
809 1288401 : wide_int mask;
810 :
811 1288401 : if (!query->range_of_expr (vr0, op0, stmt)
812 1288401 : || vr0.undefined_p ())
813 : return false;
814 1287719 : if (!query->range_of_expr (vr1, op1, stmt)
815 1287719 : || vr1.undefined_p ())
816 : return false;
817 :
818 1287363 : if (!vr_set_zero_nonzero_bits (TREE_TYPE (op0), &vr0, &may_be_nonzero0,
819 : &must_be_nonzero0))
820 : return false;
821 361695 : if (!vr_set_zero_nonzero_bits (TREE_TYPE (op1), &vr1, &may_be_nonzero1,
822 : &must_be_nonzero1))
823 : return false;
824 :
825 317258 : switch (gimple_assign_rhs_code (stmt))
826 : {
827 224312 : case BIT_AND_EXPR:
828 224312 : mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
829 224312 : if (mask == 0)
830 : {
831 : op = op0;
832 : break;
833 : }
834 219509 : mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
835 219509 : if (mask == 0)
836 : {
837 : op = op1;
838 : break;
839 : }
840 : break;
841 92946 : case BIT_IOR_EXPR:
842 92946 : mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
843 92946 : if (mask == 0)
844 : {
845 : op = op1;
846 : break;
847 : }
848 92946 : mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
849 92946 : if (mask == 0)
850 : {
851 : op = op0;
852 : break;
853 : }
854 : break;
855 0 : default:
856 0 : gcc_unreachable ();
857 : }
858 :
859 4999 : if (op == NULL_TREE)
860 : return false;
861 :
862 4999 : gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op);
863 4999 : update_stmt (gsi_stmt (*gsi));
864 4999 : return true;
865 1288413 : }
866 :
867 : /* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
868 : a known value range VR.
869 :
870 : If there is one and only one value which will satisfy the
871 : conditional, then return that value. Else return NULL. */
872 :
873 : static tree
874 1662572 : test_for_singularity (enum tree_code cond_code, tree op0,
875 : tree op1, const irange *vr)
876 : {
877 1662572 : tree min = NULL;
878 1662572 : tree max = NULL;
879 :
880 : /* Extract minimum/maximum values which satisfy the conditional as it was
881 : written. */
882 1662572 : if (cond_code == LE_EXPR || cond_code == LT_EXPR)
883 : {
884 726614 : min = TYPE_MIN_VALUE (TREE_TYPE (op0));
885 :
886 726614 : max = op1;
887 726614 : if (cond_code == LT_EXPR)
888 : {
889 92370 : tree one = build_int_cst (TREE_TYPE (op0), 1);
890 92370 : max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
891 : }
892 : }
893 935958 : else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
894 : {
895 797047 : max = TYPE_MAX_VALUE (TREE_TYPE (op0));
896 :
897 797047 : min = op1;
898 797047 : if (cond_code == GT_EXPR)
899 : {
900 706175 : tree one = build_int_cst (TREE_TYPE (op0), 1);
901 706175 : min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
902 : }
903 : }
904 :
905 : /* Now refine the minimum and maximum values using any
906 : value range information we have for op0. */
907 1662572 : if (min && max)
908 : {
909 1523661 : tree type = TREE_TYPE (op0);
910 1523661 : tree tmin = wide_int_to_tree (type, vr->lower_bound ());
911 1523661 : tree tmax = wide_int_to_tree (type, vr->upper_bound ());
912 1523661 : if (compare_values (tmin, min) == 1)
913 458577 : min = tmin;
914 1523661 : if (compare_values (tmax, max) == -1)
915 572009 : max = tmax;
916 :
917 : /* If the new min/max values have converged to a single value,
918 : then there is only one value which can satisfy the condition,
919 : return that value. */
920 1523661 : if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
921 319759 : return min;
922 : }
923 : return NULL;
924 : }
925 :
926 : /* Return whether the value range *VR fits in an integer type specified
927 : by PRECISION and UNSIGNED_P. */
928 :
929 : bool
930 329459 : range_fits_type_p (const irange *vr,
931 : unsigned dest_precision, signop dest_sgn)
932 : {
933 329459 : tree src_type;
934 329459 : unsigned src_precision;
935 329459 : widest_int tem;
936 329459 : signop src_sgn;
937 :
938 : /* Now we can only handle ranges with constant bounds. */
939 329459 : if (vr->undefined_p () || vr->varying_p ())
940 : return false;
941 :
942 : /* We can only handle integral and pointer types. */
943 258550 : src_type = vr->type ();
944 258550 : if (!INTEGRAL_TYPE_P (src_type)
945 0 : && !POINTER_TYPE_P (src_type))
946 : return false;
947 :
948 : /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
949 : and so is an identity transform. */
950 258550 : src_precision = TYPE_PRECISION (src_type);
951 258550 : src_sgn = TYPE_SIGN (src_type);
952 258550 : if ((src_precision < dest_precision
953 15517 : && !(dest_sgn == UNSIGNED && src_sgn == SIGNED))
954 244457 : || (src_precision == dest_precision && src_sgn == dest_sgn))
955 : return true;
956 :
957 244301 : wide_int vrmin = vr->lower_bound ();
958 244301 : wide_int vrmax = vr->upper_bound ();
959 :
960 : /* For sign changes, the MSB of the wide_int has to be clear.
961 : An unsigned value with its MSB set cannot be represented by
962 : a signed wide_int, while a negative value cannot be represented
963 : by an unsigned wide_int. */
964 244301 : if (src_sgn != dest_sgn
965 244301 : && (wi::lts_p (vrmin, 0) || wi::lts_p (vrmax, 0)))
966 : return false;
967 :
968 : /* Then we can perform the conversion on both ends and compare
969 : the result for equality. */
970 133738 : signop sign = TYPE_SIGN (vr->type ());
971 133738 : tem = wi::ext (widest_int::from (vrmin, sign), dest_precision, dest_sgn);
972 133738 : if (tem != widest_int::from (vrmin, sign))
973 : return false;
974 128075 : tem = wi::ext (widest_int::from (vrmax, sign), dest_precision, dest_sgn);
975 128075 : if (tem != widest_int::from (vrmax, sign))
976 : return false;
977 :
978 : return true;
979 244301 : }
980 :
981 : // Clear edge E of EDGE_EXECUTABLE (it is unexecutable). If it wasn't
982 : // previously clear, propagate to successor blocks if appropriate.
983 :
984 : void
985 311053 : simplify_using_ranges::set_and_propagate_unexecutable (edge e)
986 : {
987 : // If not_executable is already set, we're done.
988 : // This works in the absence of a flag as well.
989 311053 : if ((e->flags & m_not_executable_flag) == m_not_executable_flag)
990 217629 : return;
991 :
992 223794 : e->flags |= m_not_executable_flag;
993 223794 : m_flag_set_edges.safe_push (e);
994 :
995 : // Check if the destination block needs to propagate the property.
996 223794 : basic_block bb = e->dest;
997 :
998 : // If any incoming edge is executable, we are done.
999 223794 : edge_iterator ei;
1000 358943 : FOR_EACH_EDGE (e, ei, bb->preds)
1001 265519 : if ((e->flags & m_not_executable_flag) == 0)
1002 : return;
1003 :
1004 : // This block is also unexecutable, propagate to all exit edges as well.
1005 164559 : FOR_EACH_EDGE (e, ei, bb->succs)
1006 71135 : set_and_propagate_unexecutable (e);
1007 : }
1008 :
1009 : /* If COND can be folded entirely as TRUE or FALSE, rewrite the
1010 : conditional as such, and return TRUE. */
1011 :
1012 : bool
1013 21924908 : simplify_using_ranges::fold_cond (gcond *cond)
1014 : {
1015 21924908 : int_range_max r;
1016 21924908 : if (query->range_of_stmt (r, cond) && r.singleton_p ())
1017 : {
1018 : // COND has already been folded if arguments are constant.
1019 394109 : if (TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
1020 394109 : && TREE_CODE (gimple_cond_rhs (cond)) != SSA_NAME)
1021 : return false;
1022 232777 : if (dump_file)
1023 : {
1024 205 : fprintf (dump_file, "Folding predicate ");
1025 205 : print_gimple_expr (dump_file, cond, 0);
1026 205 : fprintf (dump_file, " to ");
1027 : }
1028 232777 : edge e0 = EDGE_SUCC (gimple_bb (cond), 0);
1029 232777 : edge e1 = EDGE_SUCC (gimple_bb (cond), 1);
1030 232777 : if (r.zero_p ())
1031 : {
1032 150262 : if (dump_file)
1033 141 : fprintf (dump_file, "0\n");
1034 150262 : gimple_cond_make_false (cond);
1035 150262 : if (e0->flags & EDGE_TRUE_VALUE)
1036 148715 : set_and_propagate_unexecutable (e0);
1037 : else
1038 1547 : set_and_propagate_unexecutable (e1);
1039 : }
1040 : else
1041 : {
1042 82515 : if (dump_file)
1043 64 : fprintf (dump_file, "1\n");
1044 82515 : gimple_cond_make_true (cond);
1045 82515 : if (e0->flags & EDGE_FALSE_VALUE)
1046 607 : set_and_propagate_unexecutable (e0);
1047 : else
1048 81908 : set_and_propagate_unexecutable (e1);
1049 : }
1050 232777 : update_stmt (cond);
1051 232777 : return true;
1052 : }
1053 :
1054 : // FIXME: Audit the code below and make sure it never finds anything.
1055 21530799 : edge taken_edge;
1056 21530799 : legacy_fold_cond (cond, &taken_edge);
1057 :
1058 21530799 : if (taken_edge)
1059 : {
1060 8 : if (taken_edge->flags & EDGE_TRUE_VALUE)
1061 : {
1062 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1063 0 : fprintf (dump_file, "\nVRP Predicate evaluates to: 1\n");
1064 0 : gimple_cond_make_true (cond);
1065 : }
1066 8 : else if (taken_edge->flags & EDGE_FALSE_VALUE)
1067 : {
1068 8 : if (dump_file && (dump_flags & TDF_DETAILS))
1069 0 : fprintf (dump_file, "\nVRP Predicate evaluates to: 0\n");
1070 8 : gimple_cond_make_false (cond);
1071 : }
1072 : else
1073 0 : gcc_unreachable ();
1074 8 : update_stmt (cond);
1075 8 : return true;
1076 : }
1077 : return false;
1078 21924908 : }
1079 :
1080 : /* Simplify a conditional using a relational operator to an equality
1081 : test if the range information indicates only one value can satisfy
1082 : the original conditional. */
1083 :
1084 : bool
1085 12652336 : simplify_using_ranges::simplify_cond_using_ranges_1 (gcond *stmt)
1086 : {
1087 12652336 : tree op0 = gimple_cond_lhs (stmt);
1088 12652336 : tree op1 = gimple_cond_rhs (stmt);
1089 12652336 : enum tree_code cond_code = gimple_cond_code (stmt);
1090 :
1091 12652336 : if (fold_cond (stmt))
1092 : return true;
1093 :
1094 12506453 : if (simplify_compare_using_ranges_1 (cond_code, op0, op1, stmt))
1095 : {
1096 385095 : if (dump_file)
1097 : {
1098 27 : fprintf (dump_file, "Simplified relational ");
1099 27 : print_gimple_stmt (dump_file, stmt, 0);
1100 27 : fprintf (dump_file, " into ");
1101 : }
1102 :
1103 385095 : gimple_cond_set_code (stmt, cond_code);
1104 385095 : gimple_cond_set_lhs (stmt, op0);
1105 385095 : gimple_cond_set_rhs (stmt, op1);
1106 :
1107 385095 : update_stmt (stmt);
1108 :
1109 385095 : if (dump_file)
1110 : {
1111 27 : print_gimple_stmt (dump_file, stmt, 0);
1112 27 : fprintf (dump_file, "\n");
1113 : }
1114 : return true;
1115 : }
1116 : return false;
1117 : }
1118 :
1119 : /* Like simplify_cond_using_ranges_1 but for assignments rather
1120 : than GIMPLE_COND. */
1121 :
1122 : bool
1123 1267476 : simplify_using_ranges::simplify_compare_assign_using_ranges_1
1124 : (gimple_stmt_iterator *gsi,
1125 : gimple *stmt)
1126 : {
1127 1267476 : enum tree_code code = gimple_assign_rhs_code (stmt);
1128 1267476 : tree op0 = gimple_assign_rhs1 (stmt);
1129 1267476 : tree op1 = gimple_assign_rhs2 (stmt);
1130 1267476 : gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
1131 1267476 : bool happened = false;
1132 :
1133 1267476 : if (simplify_compare_using_ranges_1 (code, op0, op1, stmt))
1134 : {
1135 6944 : if (dump_file)
1136 : {
1137 3 : fprintf (dump_file, "Simplified relational ");
1138 3 : print_gimple_stmt (dump_file, stmt, 0);
1139 3 : fprintf (dump_file, " into ");
1140 : }
1141 :
1142 6944 : gimple_assign_set_rhs_code (stmt, code);
1143 6944 : gimple_assign_set_rhs1 (stmt, op0);
1144 6944 : gimple_assign_set_rhs2 (stmt, op1);
1145 :
1146 6944 : update_stmt (stmt);
1147 :
1148 6944 : if (dump_file)
1149 : {
1150 3 : print_gimple_stmt (dump_file, stmt, 0);
1151 3 : fprintf (dump_file, "\n");
1152 : }
1153 : happened = true;
1154 : }
1155 :
1156 : /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
1157 : if the RHS is zero or one, and the LHS are known to be boolean
1158 : values. */
1159 1267476 : if ((code == EQ_EXPR || code == NE_EXPR)
1160 712469 : && INTEGRAL_TYPE_P (TREE_TYPE (op0))
1161 1763720 : && simplify_truth_ops_using_ranges (gsi, stmt))
1162 : happened = true;
1163 :
1164 1267476 : return happened;
1165 : }
1166 :
1167 : /* Try to simplify OP0 COND_CODE OP1 using a relational operator to an
1168 : equality test if the range information indicates only one value can
1169 : satisfy the original conditional. */
1170 :
1171 : bool
1172 13773929 : simplify_using_ranges::simplify_compare_using_ranges_1 (tree_code &cond_code, tree &op0, tree &op1, gimple *stmt)
1173 : {
1174 13773929 : bool happened = false;
1175 13773929 : if (cond_code != NE_EXPR
1176 13773929 : && cond_code != EQ_EXPR
1177 3561652 : && TREE_CODE (op0) == SSA_NAME
1178 3561177 : && INTEGRAL_TYPE_P (TREE_TYPE (op0))
1179 16973176 : && is_gimple_min_invariant (op1))
1180 : {
1181 1967678 : int_range_max vr;
1182 :
1183 1967678 : if (!query->range_of_expr (vr, op0, stmt))
1184 0 : vr.set_undefined ();
1185 :
1186 : /* If we have range information for OP0, then we might be
1187 : able to simplify this conditional. */
1188 1967678 : if (!vr.undefined_p () && !vr.varying_p ())
1189 : {
1190 831286 : tree new_tree = test_for_singularity (cond_code, op0, op1, &vr);
1191 831286 : if (new_tree)
1192 : {
1193 138911 : cond_code = EQ_EXPR;
1194 138911 : op1 = new_tree;
1195 138911 : happened = true;
1196 : }
1197 :
1198 : /* Try again after inverting the condition. We only deal
1199 : with integral types here, so no need to worry about
1200 : issues with inverting FP comparisons. */
1201 831286 : new_tree = test_for_singularity
1202 831286 : (invert_tree_comparison (cond_code, false),
1203 : op0, op1, &vr);
1204 831286 : if (new_tree)
1205 : {
1206 180848 : cond_code = NE_EXPR;
1207 180848 : op1 = new_tree;
1208 180848 : happened = true;
1209 : }
1210 : }
1211 1967678 : }
1212 : // If OP0 >= OP1 and the relation between them is VREL_LE (or vice
1213 : // versa), we know OP0 == OP1.
1214 11806251 : else if ((cond_code == LE_EXPR || cond_code == GE_EXPR)
1215 391897 : && gimple_range_ssa_p (op0)
1216 12190826 : && gimple_range_ssa_p (op1))
1217 : {
1218 353628 : relation_kind rel = query->relation ().query (stmt, op0, op1);
1219 535726 : if (relation_intersect (cond_code == LE_EXPR ? VREL_LE : VREL_GE, rel)
1220 : == VREL_EQ)
1221 : {
1222 641 : cond_code = EQ_EXPR;
1223 641 : happened = true;
1224 : }
1225 : }
1226 : // Try to simplify casted conditions.
1227 13773929 : if (simplify_casted_compare (cond_code, op0, op1))
1228 84297 : happened = true;
1229 13773929 : return happened;
1230 : }
1231 :
1232 : /* Simplify OP0 code OP1 when OP1 is a constant and OP0 was a SSA_NAME
1233 : defined by a type conversion. Replacing OP0 with RHS of the type conversion.
1234 : Doing so makes the conversion dead which helps subsequent passes. */
1235 :
1236 : bool
1237 13773929 : simplify_using_ranges::simplify_casted_compare (tree_code &, tree &op0, tree &op1)
1238 : {
1239 :
1240 : /* If we have a comparison of an SSA_NAME (OP0) against a constant,
1241 : see if OP0 was set by a type conversion where the source of
1242 : the conversion is another SSA_NAME with a range that fits
1243 : into the range of OP0's type.
1244 :
1245 : If so, the conversion is redundant as the earlier SSA_NAME can be
1246 : used for the comparison directly if we just massage the constant in the
1247 : comparison. */
1248 13773929 : if (TREE_CODE (op0) == SSA_NAME
1249 13679548 : && TREE_CODE (op1) == INTEGER_CST)
1250 : {
1251 9645452 : gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
1252 9645452 : tree innerop;
1253 :
1254 9645452 : if (!is_gimple_assign (def_stmt))
1255 : return false;
1256 :
1257 5944092 : switch (gimple_assign_rhs_code (def_stmt))
1258 : {
1259 502117 : CASE_CONVERT:
1260 502117 : innerop = gimple_assign_rhs1 (def_stmt);
1261 502117 : break;
1262 52332 : case VIEW_CONVERT_EXPR:
1263 52332 : innerop = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0);
1264 52332 : if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop)))
1265 : return false;
1266 : break;
1267 : default:
1268 : return false;
1269 : }
1270 :
1271 551603 : if (TREE_CODE (innerop) == SSA_NAME
1272 551575 : && !POINTER_TYPE_P (TREE_TYPE (innerop))
1273 546050 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)
1274 1097640 : && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (op0)))
1275 : {
1276 516308 : int_range_max vr;
1277 :
1278 516308 : if (query->range_of_expr (vr, innerop)
1279 516305 : && !vr.varying_p ()
1280 175397 : && !vr.undefined_p ()
1281 175276 : && range_fits_type_p (&vr,
1282 175276 : TYPE_PRECISION (TREE_TYPE (op0)),
1283 175276 : TYPE_SIGN (TREE_TYPE (op0)))
1284 600605 : && int_fits_type_p (op1, TREE_TYPE (innerop)))
1285 : {
1286 84297 : tree newconst = fold_convert (TREE_TYPE (innerop), op1);
1287 84297 : op0 = innerop;
1288 84297 : op1 = newconst;
1289 84297 : return true;
1290 : }
1291 516308 : }
1292 : }
1293 : return false;
1294 : }
1295 :
1296 : /* Simplify a switch statement using the value range of the switch
1297 : argument. */
1298 :
1299 : bool
1300 63869 : simplify_using_ranges::simplify_switch_using_ranges (gswitch *stmt)
1301 : {
1302 63869 : tree op = gimple_switch_index (stmt);
1303 63869 : tree type = TREE_TYPE (op);
1304 63869 : int_range_max op_range (type);
1305 63869 : int_range_max default_range (type);
1306 63869 : auto_vec<unsigned> cases;
1307 63869 : cases.truncate (0);
1308 63869 : edge e;
1309 63869 : switch_update su;
1310 :
1311 : // Abort if we don't have a useful range for the switch index.
1312 63869 : if (!query->range_of_expr (op_range, op, stmt)
1313 63869 : || op_range.varying_p () || op_range.undefined_p ())
1314 : return false;
1315 :
1316 : // Default range starts with full known range of op.
1317 16615 : default_range = op_range;
1318 16615 : edge default_edge = gimple_switch_default_edge (cfun, stmt);
1319 :
1320 16615 : unsigned x, lim = gimple_switch_num_labels (stmt);
1321 98701 : for (x = 1; x < lim; x++)
1322 : {
1323 83251 : e = gimple_switch_edge (cfun, stmt, x);
1324 83251 : tree label = gimple_switch_label (stmt, x);
1325 :
1326 : // If this edge is the same as the default edge, do nothing else.
1327 83251 : if (e == default_edge)
1328 6240 : continue;
1329 : // Ada sometimes has mismatched labels and index. Just bail.
1330 83245 : if (TREE_TYPE (CASE_LOW (label)) != type)
1331 1165 : return false;
1332 :
1333 82082 : wide_int low = wi::to_wide (CASE_LOW (label));
1334 82082 : wide_int high;
1335 : // Singleton cases have no CASE_HIGH.
1336 82082 : tree tree_high = CASE_HIGH (label);
1337 82082 : if (tree_high)
1338 3505 : high = wi::to_wide (tree_high);
1339 : else
1340 78577 : high = low;
1341 :
1342 : // If the case range is fully contained in op_range, leave the
1343 : // case as it is, otherwise adjust the labels.
1344 82082 : int_range_max case_range (type, low, high);
1345 82082 : if (case_range.intersect (op_range))
1346 : {
1347 : // If none of the label is in op_range, skip this label.
1348 51444 : if (case_range.undefined_p ())
1349 6234 : continue;
1350 :
1351 : // Part of the label is in op_range, but not all of it. CASE_RANGE
1352 : // contains the part that is. Adjust the case range to
1353 : // the new min/max.
1354 45210 : if (case_range.lower_bound () != low)
1355 13 : CASE_LOW (label) = wide_int_to_tree (type,
1356 26 : case_range.lower_bound ());
1357 45210 : if (case_range.singleton_p ())
1358 43720 : CASE_HIGH (label) = NULL_TREE;
1359 : else
1360 1490 : if (case_range.upper_bound () != high)
1361 8 : CASE_HIGH (label) = wide_int_to_tree (type,
1362 16 : case_range.upper_bound ());
1363 : }
1364 : // Add case label to the keep list.
1365 75848 : cases.safe_push (x);
1366 : // Remove case_range from needing to be handled by the default.
1367 75848 : if (!case_range.invert ())
1368 2 : return false;
1369 75846 : default_range.intersect (case_range);
1370 82082 : }
1371 :
1372 : // An undefined DEFAULT range means the current default case is not needed.
1373 15450 : unsigned idx = default_range.undefined_p () ? 0 : 1;
1374 15450 : unsigned vec_size = cases.length () + idx;
1375 15450 : if (vec_size == lim)
1376 : return false;
1377 :
1378 4148 : tree vec2 = make_tree_vec (vec_size);
1379 : // Add default label if there is one.
1380 4148 : if (idx)
1381 : {
1382 3114 : TREE_VEC_ELT (vec2, 0) = gimple_switch_default_label (stmt);
1383 3114 : e = gimple_switch_edge (cfun, stmt, 0);
1384 3114 : e->aux = (void *)-1;
1385 : }
1386 :
1387 17315 : for (x = 0; x < cases.length (); x++)
1388 : {
1389 13167 : unsigned swi = cases[x];
1390 13167 : TREE_VEC_ELT (vec2, idx++) = gimple_switch_label (stmt, swi);
1391 13167 : e = gimple_switch_edge (cfun, stmt, swi);
1392 13167 : e->aux = (void *)-1;
1393 : }
1394 :
1395 : /* Queue not needed edges for later removal. */
1396 4148 : edge_iterator ei;
1397 26596 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1398 : {
1399 22448 : if (e->aux == (void *)-1)
1400 : {
1401 15307 : e->aux = NULL;
1402 15307 : continue;
1403 : }
1404 :
1405 7141 : if (dump_file && (dump_flags & TDF_DETAILS))
1406 : {
1407 0 : fprintf (dump_file, "removing unreachable case label\n");
1408 : }
1409 7141 : to_remove_edges.safe_push (e);
1410 7141 : set_and_propagate_unexecutable (e);
1411 7141 : e->flags &= ~EDGE_EXECUTABLE;
1412 7141 : e->flags |= EDGE_IGNORE;
1413 : }
1414 :
1415 : /* And queue an update for the stmt. */
1416 4148 : su.stmt = stmt;
1417 4148 : su.vec = vec2;
1418 4148 : to_update_switch_stmts.safe_push (su);
1419 4148 : return true;
1420 63869 : }
1421 :
1422 : void
1423 13708884 : simplify_using_ranges::cleanup_edges_and_switches (void)
1424 : {
1425 13708884 : int i;
1426 13708884 : edge e;
1427 13708884 : switch_update *su;
1428 :
1429 : /* Clear any edges marked as not executable. */
1430 13708884 : if (m_not_executable_flag)
1431 : {
1432 4660097 : FOR_EACH_VEC_ELT (m_flag_set_edges, i, e)
1433 223794 : e->flags &= ~m_not_executable_flag;
1434 : }
1435 : /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
1436 : CFG in a broken state and requires a cfg_cleanup run. */
1437 13719901 : FOR_EACH_VEC_ELT (to_remove_edges, i, e)
1438 7141 : remove_edge (e);
1439 :
1440 : /* Update SWITCH_EXPR case label vector. */
1441 13713032 : FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su)
1442 : {
1443 4148 : size_t j;
1444 4148 : size_t n = TREE_VEC_LENGTH (su->vec);
1445 4148 : tree label;
1446 4148 : gimple_switch_set_num_labels (su->stmt, n);
1447 24577 : for (j = 0; j < n; j++)
1448 16281 : gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
1449 : /* As we may have replaced the default label with a regular one
1450 : make sure to make it a real default label again. This ensures
1451 : optimal expansion. */
1452 4148 : label = gimple_switch_label (su->stmt, 0);
1453 4148 : CASE_LOW (label) = NULL_TREE;
1454 4148 : CASE_HIGH (label) = NULL_TREE;
1455 : }
1456 :
1457 13708884 : if (!to_remove_edges.is_empty ())
1458 : {
1459 3876 : free_dominance_info (CDI_DOMINATORS);
1460 3876 : loops_state_set (LOOPS_NEED_FIXUP);
1461 : }
1462 :
1463 13708884 : to_remove_edges.release ();
1464 13708884 : to_update_switch_stmts.release ();
1465 13708884 : }
1466 :
1467 : /* Simplify an integral conversion from an SSA name in STMT. */
1468 :
1469 : static bool
1470 4943362 : simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
1471 : {
1472 4943362 : tree innerop, middleop, finaltype;
1473 4943362 : gimple *def_stmt;
1474 4943362 : signop inner_sgn, middle_sgn, final_sgn;
1475 4943362 : unsigned inner_prec, middle_prec, final_prec;
1476 4943362 : widest_int innermin, innermed, innermax, middlemin, middlemed, middlemax;
1477 :
1478 4943362 : finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
1479 4943362 : if (!INTEGRAL_TYPE_P (finaltype))
1480 : return false;
1481 4548012 : middleop = gimple_assign_rhs1 (stmt);
1482 4548012 : def_stmt = SSA_NAME_DEF_STMT (middleop);
1483 4548012 : if (!is_gimple_assign (def_stmt)
1484 4548012 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
1485 : return false;
1486 151412 : innerop = gimple_assign_rhs1 (def_stmt);
1487 151412 : if (TREE_CODE (innerop) != SSA_NAME
1488 151412 : || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
1489 : return false;
1490 :
1491 : /* Get the value-range of the inner operand. Use global ranges in
1492 : case innerop was created during substitute-and-fold. */
1493 147958 : wide_int imin, imax;
1494 147958 : int_range_max vr;
1495 147958 : if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop)))
1496 : return false;
1497 245618 : get_range_query (cfun)->range_of_expr (vr, innerop, stmt);
1498 122809 : if (vr.undefined_p () || vr.varying_p ())
1499 : return false;
1500 67986 : innermin = widest_int::from (vr.lower_bound (), TYPE_SIGN (TREE_TYPE (innerop)));
1501 67986 : innermax = widest_int::from (vr.upper_bound (), TYPE_SIGN (TREE_TYPE (innerop)));
1502 :
1503 : /* Simulate the conversion chain to check if the result is equal if
1504 : the middle conversion is removed. */
1505 67986 : inner_prec = TYPE_PRECISION (TREE_TYPE (innerop));
1506 67986 : middle_prec = TYPE_PRECISION (TREE_TYPE (middleop));
1507 67986 : final_prec = TYPE_PRECISION (finaltype);
1508 :
1509 : /* If the first conversion is not injective, the second must not
1510 : be widening. */
1511 67986 : if (wi::gtu_p (innermax - innermin,
1512 135972 : wi::mask <widest_int> (middle_prec, false))
1513 67986 : && middle_prec < final_prec)
1514 : return false;
1515 : /* We also want a medium value so that we can track the effect that
1516 : narrowing conversions with sign change have. */
1517 56385 : inner_sgn = TYPE_SIGN (TREE_TYPE (innerop));
1518 56385 : if (inner_sgn == UNSIGNED)
1519 41412 : innermed = wi::shifted_mask <widest_int> (1, inner_prec - 1, false);
1520 : else
1521 14973 : innermed = 0;
1522 56385 : if (wi::cmp (innermin, innermed, inner_sgn) >= 0
1523 56385 : || wi::cmp (innermed, innermax, inner_sgn) >= 0)
1524 40287 : innermed = innermin;
1525 :
1526 56385 : middle_sgn = TYPE_SIGN (TREE_TYPE (middleop));
1527 56385 : middlemin = wi::ext (innermin, middle_prec, middle_sgn);
1528 56385 : middlemed = wi::ext (innermed, middle_prec, middle_sgn);
1529 56385 : middlemax = wi::ext (innermax, middle_prec, middle_sgn);
1530 :
1531 : /* Require that the final conversion applied to both the original
1532 : and the intermediate range produces the same result. */
1533 56385 : final_sgn = TYPE_SIGN (finaltype);
1534 112770 : if (wi::ext (middlemin, final_prec, final_sgn)
1535 112770 : != wi::ext (innermin, final_prec, final_sgn)
1536 53877 : || wi::ext (middlemed, final_prec, final_sgn)
1537 218016 : != wi::ext (innermed, final_prec, final_sgn)
1538 101623 : || wi::ext (middlemax, final_prec, final_sgn)
1539 192099 : != wi::ext (innermax, final_prec, final_sgn))
1540 : return false;
1541 :
1542 43873 : gimple_assign_set_rhs1 (stmt, innerop);
1543 43873 : fold_stmt (gsi, follow_single_use_edges);
1544 43873 : return true;
1545 5091320 : }
1546 :
1547 : /* Simplify a conversion from integral SSA name to float in STMT. */
1548 :
1549 : bool
1550 259428 : simplify_using_ranges::simplify_float_conversion_using_ranges
1551 : (gimple_stmt_iterator *gsi,
1552 : gimple *stmt)
1553 : {
1554 259428 : tree rhs1 = gimple_assign_rhs1 (stmt);
1555 259428 : int_range_max vr;
1556 259428 : scalar_float_mode fltmode
1557 259428 : = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt)));
1558 259428 : scalar_int_mode mode;
1559 259428 : tree tem;
1560 259428 : gassign *conv;
1561 :
1562 : /* We can only handle constant ranges. */
1563 259428 : if (!query->range_of_expr (vr, rhs1, stmt)
1564 259428 : || vr.varying_p ()
1565 361441 : || vr.undefined_p ())
1566 : return false;
1567 :
1568 : /* The code below doesn't work for large/huge _BitInt, nor is really
1569 : needed for those, bitint lowering does use ranges already. */
1570 202651 : if (BITINT_TYPE_P (TREE_TYPE (rhs1))
1571 101332 : && TYPE_MODE (TREE_TYPE (rhs1)) == BLKmode)
1572 : return false;
1573 : /* First check if we can use a signed type in place of an unsigned. */
1574 101319 : scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1));
1575 101319 : if (TYPE_UNSIGNED (TREE_TYPE (rhs1))
1576 5515 : && can_float_p (fltmode, rhs_mode, 0) != CODE_FOR_nothing
1577 105100 : && range_fits_type_p (&vr, TYPE_PRECISION (TREE_TYPE (rhs1)), SIGNED))
1578 : mode = rhs_mode;
1579 : /* If we can do the conversion in the current input mode do nothing. */
1580 99686 : else if (can_float_p (fltmode, rhs_mode,
1581 99686 : TYPE_UNSIGNED (TREE_TYPE (rhs1))) != CODE_FOR_nothing)
1582 : return false;
1583 : /* Otherwise search for a mode we can use, starting from the narrowest
1584 : integer mode available. */
1585 : else
1586 : {
1587 4425 : mode = NARROWEST_INT_MODE;
1588 15889 : for (;;)
1589 : {
1590 : /* If we cannot do a signed conversion to float from mode
1591 : or if the value-range does not fit in the signed type
1592 : try with a wider mode. */
1593 15889 : if (can_float_p (fltmode, mode, 0) != CODE_FOR_nothing
1594 15889 : && range_fits_type_p (&vr, GET_MODE_PRECISION (mode), SIGNED))
1595 : break;
1596 :
1597 : /* But do not widen the input. Instead leave that to the
1598 : optabs expansion code. */
1599 31512 : if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
1600 15756 : || GET_MODE_PRECISION (mode) > TYPE_PRECISION (TREE_TYPE (rhs1)))
1601 : return false;
1602 : }
1603 : }
1604 :
1605 : /* It works, insert a truncation or sign-change before the
1606 : float conversion. */
1607 1766 : tem = make_ssa_name (build_nonstandard_integer_type
1608 1766 : (GET_MODE_PRECISION (mode), 0));
1609 1766 : conv = gimple_build_assign (tem, NOP_EXPR, rhs1);
1610 1766 : gsi_insert_before (gsi, conv, GSI_SAME_STMT);
1611 1766 : gimple_assign_set_rhs1 (stmt, tem);
1612 1766 : fold_stmt (gsi, follow_single_use_edges);
1613 :
1614 1766 : return true;
1615 259428 : }
1616 :
1617 : /* Simplify an internal fn call using ranges if possible. */
1618 :
1619 : bool
1620 605014 : simplify_using_ranges::simplify_internal_call_using_ranges
1621 : (gimple_stmt_iterator *gsi,
1622 : gimple *stmt)
1623 : {
1624 605014 : enum tree_code subcode;
1625 605014 : bool is_ubsan = false;
1626 605014 : bool ovf = false;
1627 605014 : switch (gimple_call_internal_fn (stmt))
1628 : {
1629 : case IFN_UBSAN_CHECK_ADD:
1630 : subcode = PLUS_EXPR;
1631 : is_ubsan = true;
1632 : break;
1633 2572 : case IFN_UBSAN_CHECK_SUB:
1634 2572 : subcode = MINUS_EXPR;
1635 2572 : is_ubsan = true;
1636 2572 : break;
1637 2138 : case IFN_UBSAN_CHECK_MUL:
1638 2138 : subcode = MULT_EXPR;
1639 2138 : is_ubsan = true;
1640 2138 : break;
1641 41201 : case IFN_ADD_OVERFLOW:
1642 41201 : subcode = PLUS_EXPR;
1643 41201 : break;
1644 49746 : case IFN_SUB_OVERFLOW:
1645 49746 : subcode = MINUS_EXPR;
1646 49746 : break;
1647 47192 : case IFN_MUL_OVERFLOW:
1648 47192 : subcode = MULT_EXPR;
1649 47192 : break;
1650 : default:
1651 : return false;
1652 : }
1653 :
1654 145408 : tree op0 = gimple_call_arg (stmt, 0);
1655 145408 : tree op1 = gimple_call_arg (stmt, 1);
1656 145408 : tree type;
1657 145408 : if (is_ubsan)
1658 : {
1659 7269 : type = TREE_TYPE (op0);
1660 7269 : if (VECTOR_TYPE_P (type))
1661 : return false;
1662 : }
1663 138139 : else if (gimple_call_lhs (stmt) == NULL_TREE)
1664 : return false;
1665 : else
1666 138139 : type = TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt)));
1667 144482 : if (!check_for_binary_op_overflow (query, subcode, type, op0, op1, &ovf, stmt)
1668 144482 : || (is_ubsan && ovf))
1669 : return false;
1670 :
1671 3496 : gimple *g;
1672 3496 : location_t loc = gimple_location (stmt);
1673 3496 : if (is_ubsan)
1674 529 : g = gimple_build_assign (gimple_call_lhs (stmt), subcode, op0, op1);
1675 : else
1676 : {
1677 2967 : tree utype = type;
1678 2967 : if (ovf
1679 1478 : || !useless_type_conversion_p (type, TREE_TYPE (op0))
1680 3704 : || !useless_type_conversion_p (type, TREE_TYPE (op1)))
1681 2519 : utype = unsigned_type_for (type);
1682 2967 : if (TREE_CODE (op0) == INTEGER_CST)
1683 1175 : op0 = fold_convert (utype, op0);
1684 1792 : else if (!useless_type_conversion_p (utype, TREE_TYPE (op0)))
1685 : {
1686 751 : g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op0);
1687 751 : gimple_set_location (g, loc);
1688 751 : gsi_insert_before (gsi, g, GSI_SAME_STMT);
1689 751 : op0 = gimple_assign_lhs (g);
1690 : }
1691 2967 : if (TREE_CODE (op1) == INTEGER_CST)
1692 1720 : op1 = fold_convert (utype, op1);
1693 1247 : else if (!useless_type_conversion_p (utype, TREE_TYPE (op1)))
1694 : {
1695 27 : g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op1);
1696 27 : gimple_set_location (g, loc);
1697 27 : gsi_insert_before (gsi, g, GSI_SAME_STMT);
1698 27 : op1 = gimple_assign_lhs (g);
1699 : }
1700 2967 : g = gimple_build_assign (make_ssa_name (utype), subcode, op0, op1);
1701 2967 : gimple_set_location (g, loc);
1702 2967 : gsi_insert_before (gsi, g, GSI_SAME_STMT);
1703 2967 : if (utype != type)
1704 : {
1705 1361 : g = gimple_build_assign (make_ssa_name (type), NOP_EXPR,
1706 : gimple_assign_lhs (g));
1707 1361 : gimple_set_location (g, loc);
1708 1361 : gsi_insert_before (gsi, g, GSI_SAME_STMT);
1709 : }
1710 2967 : g = gimple_build_assign (gimple_call_lhs (stmt), COMPLEX_EXPR,
1711 : gimple_assign_lhs (g),
1712 2967 : build_int_cst (type, ovf));
1713 : }
1714 3496 : gimple_set_location (g, loc);
1715 3496 : gsi_replace (gsi, g, false);
1716 3496 : return true;
1717 : }
1718 :
1719 : /* Return true if VAR is a two-valued variable. Set a and b with the
1720 : two-values when it is true. Return false otherwise. */
1721 :
1722 : bool
1723 494414 : simplify_using_ranges::two_valued_val_range_p (tree var, tree *a, tree *b,
1724 : gimple *s)
1725 : {
1726 494414 : int_range_max vr;
1727 494414 : if (!query->range_of_expr (vr, var, s))
1728 : return false;
1729 494414 : if (vr.varying_p () || vr.undefined_p ())
1730 : return false;
1731 :
1732 807849 : if ((vr.num_pairs () == 1 && vr.upper_bound () - vr.lower_bound () == 1)
1733 419326 : || (vr.num_pairs () == 2
1734 292368 : && vr.lower_bound (0) == vr.upper_bound (0)
1735 247052 : && vr.lower_bound (1) == vr.upper_bound (1)))
1736 : {
1737 7669 : *a = wide_int_to_tree (TREE_TYPE (var), vr.lower_bound ());
1738 7669 : *b = wide_int_to_tree (TREE_TYPE (var), vr.upper_bound ());
1739 7669 : return true;
1740 : }
1741 : return false;
1742 494414 : }
1743 :
1744 13708884 : simplify_using_ranges::simplify_using_ranges (range_query *query,
1745 : int not_executable_flag)
1746 13708884 : : query (query)
1747 : {
1748 13708884 : to_remove_edges = vNULL;
1749 13708884 : to_update_switch_stmts = vNULL;
1750 13708884 : m_not_executable_flag = not_executable_flag;
1751 13708884 : m_flag_set_edges = vNULL;
1752 13708884 : }
1753 :
1754 13708884 : simplify_using_ranges::~simplify_using_ranges ()
1755 : {
1756 13708884 : cleanup_edges_and_switches ();
1757 13708884 : m_flag_set_edges.release ();
1758 13708884 : }
1759 :
1760 : /* Simplify STMT using ranges if possible. */
1761 :
1762 : bool
1763 263893012 : simplify_using_ranges::simplify (gimple_stmt_iterator *gsi)
1764 : {
1765 263893012 : gcc_checking_assert (query);
1766 :
1767 263893012 : gimple *stmt = gsi_stmt (*gsi);
1768 263893012 : if (is_gimple_assign (stmt))
1769 : {
1770 70098220 : enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
1771 70098220 : tree rhs1 = gimple_assign_rhs1 (stmt);
1772 70098220 : tree rhs2 = gimple_assign_rhs2 (stmt);
1773 70098220 : tree lhs = gimple_assign_lhs (stmt);
1774 70098220 : tree val1 = NULL_TREE, val2 = NULL_TREE;
1775 70098220 : use_operand_p use_p;
1776 70098220 : gimple *use_stmt;
1777 :
1778 : /* Convert:
1779 : LHS = CST BINOP VAR
1780 : Where VAR is two-valued and LHS is used in GIMPLE_COND only
1781 : To:
1782 : LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
1783 :
1784 : Also handles:
1785 : LHS = VAR BINOP CST
1786 : Where VAR is two-valued and LHS is used in GIMPLE_COND only
1787 : To:
1788 : LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
1789 :
1790 70098220 : if (TREE_CODE_CLASS (rhs_code) == tcc_binary
1791 14865890 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1792 10592171 : && ((TREE_CODE (rhs1) == INTEGER_CST
1793 181222 : && TREE_CODE (rhs2) == SSA_NAME)
1794 10411547 : || (TREE_CODE (rhs2) == INTEGER_CST
1795 6965366 : && TREE_CODE (rhs1) == SSA_NAME))
1796 7145392 : && single_imm_use (lhs, &use_p, &use_stmt)
1797 75592646 : && gimple_code (use_stmt) == GIMPLE_COND)
1798 :
1799 : {
1800 494414 : tree new_rhs1 = NULL_TREE;
1801 494414 : tree new_rhs2 = NULL_TREE;
1802 494414 : tree cmp_var = NULL_TREE;
1803 :
1804 494414 : if (TREE_CODE (rhs2) == SSA_NAME
1805 494414 : && two_valued_val_range_p (rhs2, &val1, &val2, stmt))
1806 : {
1807 : /* Optimize RHS1 OP [VAL1, VAL2]. */
1808 244 : new_rhs1 = int_const_binop (rhs_code, rhs1, val1);
1809 244 : new_rhs2 = int_const_binop (rhs_code, rhs1, val2);
1810 244 : cmp_var = rhs2;
1811 : }
1812 494170 : else if (TREE_CODE (rhs1) == SSA_NAME
1813 494170 : && two_valued_val_range_p (rhs1, &val1, &val2, stmt))
1814 : {
1815 : /* Optimize [VAL1, VAL2] OP RHS2. */
1816 7425 : new_rhs1 = int_const_binop (rhs_code, val1, rhs2);
1817 7425 : new_rhs2 = int_const_binop (rhs_code, val2, rhs2);
1818 7425 : cmp_var = rhs1;
1819 : }
1820 :
1821 : /* If we could not find two-vals or the optimization is invalid as
1822 : in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
1823 494414 : if (new_rhs1 && new_rhs2)
1824 : {
1825 7669 : tree cond = gimple_build (gsi, true, GSI_SAME_STMT,
1826 : UNKNOWN_LOCATION,
1827 : EQ_EXPR, boolean_type_node,
1828 : cmp_var, val1);
1829 7669 : gimple_assign_set_rhs_with_ops (gsi,
1830 : COND_EXPR, cond,
1831 : new_rhs1,
1832 : new_rhs2);
1833 7669 : update_stmt (gsi_stmt (*gsi));
1834 7669 : fold_stmt (gsi, follow_single_use_edges);
1835 8475283 : return true;
1836 : }
1837 : }
1838 :
1839 70090551 : if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
1840 1267476 : return simplify_compare_assign_using_ranges_1 (gsi, stmt);
1841 :
1842 68823075 : switch (rhs_code)
1843 : {
1844 :
1845 : /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
1846 : and BIT_AND_EXPR respectively if the first operand is greater
1847 : than zero and the second operand is an exact power of two.
1848 : Also optimize TRUNC_MOD_EXPR away if the second operand is
1849 : constant and the first operand already has the right value
1850 : range. */
1851 338485 : case TRUNC_DIV_EXPR:
1852 338485 : case TRUNC_MOD_EXPR:
1853 338485 : if ((TREE_CODE (rhs1) == SSA_NAME
1854 338485 : || TREE_CODE (rhs1) == INTEGER_CST)
1855 338485 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
1856 337094 : return simplify_div_or_mod_using_ranges (gsi, stmt);
1857 : break;
1858 :
1859 : /* Transform ABS (X) into X or -X as appropriate. */
1860 64974 : case ABS_EXPR:
1861 64974 : if (TREE_CODE (rhs1) == SSA_NAME
1862 64974 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
1863 9375 : return simplify_abs_using_ranges (gsi, stmt);
1864 : break;
1865 :
1866 1327483 : case BIT_AND_EXPR:
1867 1327483 : case BIT_IOR_EXPR:
1868 : /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR if all the bits
1869 : being cleared are already cleared or all the bits being set
1870 : are already set. Beware that boolean types must be handled
1871 : logically (see range-op.cc) unless they have precision 1. */
1872 2564067 : if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1873 2524985 : && (TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE
1874 311955 : || TYPE_PRECISION (TREE_TYPE (rhs1)) == 1))
1875 1288401 : return simplify_bit_ops_using_ranges (gsi, stmt);
1876 : break;
1877 :
1878 6070542 : CASE_CONVERT:
1879 6070542 : if (TREE_CODE (rhs1) == SSA_NAME
1880 6070542 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
1881 4943362 : return simplify_conversion_using_ranges (gsi, stmt);
1882 : break;
1883 :
1884 261844 : case FLOAT_EXPR:
1885 261844 : if (TREE_CODE (rhs1) == SSA_NAME
1886 261844 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
1887 259428 : return simplify_float_conversion_using_ranges (gsi, stmt);
1888 : break;
1889 :
1890 249369 : case MIN_EXPR:
1891 249369 : case MAX_EXPR:
1892 249369 : return simplify_min_or_max_using_ranges (gsi, stmt);
1893 :
1894 421638 : case RSHIFT_EXPR:
1895 421638 : {
1896 421638 : tree op0 = gimple_assign_rhs1 (stmt);
1897 421638 : tree type = TREE_TYPE (op0);
1898 421638 : int_range_max range;
1899 421638 : if (TYPE_SIGN (type) == SIGNED
1900 421638 : && query->range_of_expr (range, op0, stmt))
1901 : {
1902 113109 : unsigned prec = TYPE_PRECISION (TREE_TYPE (op0));
1903 226218 : int_range<2> nzm1 (type, wi::minus_one (prec), wi::zero (prec),
1904 113109 : VR_ANTI_RANGE);
1905 113109 : range.intersect (nzm1);
1906 : // If there are no ranges other than [-1, 0] remove the shift.
1907 113109 : if (range.undefined_p ())
1908 : {
1909 86 : gimple_assign_set_rhs_from_tree (gsi, op0);
1910 86 : return true;
1911 : }
1912 : return false;
1913 113109 : }
1914 308529 : break;
1915 421638 : }
1916 : default:
1917 : break;
1918 : }
1919 : }
1920 193794792 : else if (gimple_code (stmt) == GIMPLE_COND)
1921 12652336 : return simplify_cond_using_ranges_1 (as_a <gcond *> (stmt));
1922 181142456 : else if (gimple_code (stmt) == GIMPLE_SWITCH)
1923 63869 : return simplify_switch_using_ranges (as_a <gswitch *> (stmt));
1924 181078587 : else if (is_gimple_call (stmt)
1925 181078587 : && gimple_call_internal_p (stmt))
1926 605014 : return simplify_internal_call_using_ranges (gsi, stmt);
1927 :
1928 : return false;
1929 : }
|
