Branch data Line data Source code
1 : : /* Support routines for Value Range Propagation (VRP).
2 : : Copyright (C) 2005-2025 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 : 481822 : simplify_using_ranges::op_with_boolean_value_range_p (tree op, gimple *s)
59 : : {
60 : 481822 : if (TYPE_PRECISION (TREE_TYPE (op)) == 1)
61 : : return true;
62 : :
63 : 469340 : if (integer_zerop (op)
64 : 469340 : || integer_onep (op))
65 : 10162 : return true;
66 : :
67 : 459178 : 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 : 459178 : int_range_max vr;
73 : 459178 : return (query->range_of_expr (vr, op, s)
74 : 459178 : && vr == range_true_and_false (TREE_TYPE (op)));
75 : 459178 : }
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 : 144633 : 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 : 144633 : relation_kind rel = VREL_VARYING;
89 : : /* For subtraction see if relations could simplify it. */
90 : 144633 : if (s
91 : 144633 : && subcode == MINUS_EXPR
92 : 144633 : && types_compatible_p (TREE_TYPE (op0), TREE_TYPE (op1)))
93 : : {
94 : 28859 : 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 : 28859 : if (rel == VREL_EQ)
99 : : return true;
100 : : }
101 : :
102 : 144632 : int_range_max vr0, vr1;
103 : 144632 : if (!query->range_of_expr (vr0, op0, s) || vr0.undefined_p ())
104 : 12 : vr0.set_varying (TREE_TYPE (op0));
105 : 144632 : if (!query->range_of_expr (vr1, op1, s) || vr1.undefined_p ())
106 : 4 : vr1.set_varying (TREE_TYPE (op1));
107 : :
108 : 144632 : tree vr0min = wide_int_to_tree (TREE_TYPE (op0), vr0.lower_bound ());
109 : 144632 : tree vr0max = wide_int_to_tree (TREE_TYPE (op0), vr0.upper_bound ());
110 : 144632 : tree vr1min = wide_int_to_tree (TREE_TYPE (op1), vr1.lower_bound ());
111 : 144632 : 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 : 144632 : if ((rel == VREL_GT || rel == VREL_GE)
117 : 20 : && tree_int_cst_sgn (vr1min) >= 0
118 : 144649 : && !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 : 144615 : if (rel == VREL_LT
125 : 1 : && tree_int_cst_sgn (vr1min) >= 0
126 : 144616 : && TYPE_UNSIGNED (type))
127 : : {
128 : 1 : *ovf = true;
129 : 1 : return true;
130 : : }
131 : :
132 : 237587 : *ovf = arith_overflowed_p (subcode, type, vr0min,
133 : : subcode == MINUS_EXPR ? vr1max : vr1min);
134 : 237587 : if (arith_overflowed_p (subcode, type, vr0max,
135 : 144614 : subcode == MINUS_EXPR ? vr1min : vr1max) != *ovf)
136 : : return false;
137 : 39273 : if (subcode == MULT_EXPR)
138 : : {
139 : 23871 : if (arith_overflowed_p (subcode, type, vr0min, vr1max) != *ovf
140 : 23871 : || arith_overflowed_p (subcode, type, vr0max, vr1min) != *ovf)
141 : 376 : return false;
142 : : }
143 : 38897 : 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 : 36939 : widest2_int wmin, wmax;
151 : 332489 : widest2_int w[4];
152 : 36939 : int i;
153 : 36939 : signop sign0 = TYPE_SIGN (TREE_TYPE (op0));
154 : 36939 : signop sign1 = TYPE_SIGN (TREE_TYPE (op1));
155 : 36953 : w[0] = widest2_int::from (vr0.lower_bound (), sign0);
156 : 36953 : w[1] = widest2_int::from (vr0.upper_bound (), sign0);
157 : 36944 : w[2] = widest2_int::from (vr1.lower_bound (), sign1);
158 : 36944 : w[3] = widest2_int::from (vr1.upper_bound (), sign1);
159 : 184695 : for (i = 0; i < 4; i++)
160 : : {
161 : 147756 : widest2_int wt;
162 : 147756 : switch (subcode)
163 : : {
164 : 26760 : case PLUS_EXPR:
165 : 26760 : wt = wi::add (w[i & 1], w[2 + (i & 2) / 2]);
166 : 26760 : break;
167 : 27624 : case MINUS_EXPR:
168 : 27624 : wt = wi::sub (w[i & 1], w[2 + (i & 2) / 2]);
169 : 27624 : break;
170 : 93372 : case MULT_EXPR:
171 : 93372 : wt = wi::mul (w[i & 1], w[2 + (i & 2) / 2]);
172 : 93372 : break;
173 : 0 : default:
174 : 0 : gcc_unreachable ();
175 : : }
176 : 147756 : if (i == 0)
177 : : {
178 : 36939 : wmin = wt;
179 : 36939 : wmax = wt;
180 : : }
181 : : else
182 : : {
183 : 110817 : wmin = wi::smin (wmin, wt);
184 : 111473 : wmax = wi::smax (wmax, wt);
185 : : }
186 : 147756 : }
187 : : /* The result of op0 CODE op1 is known to be in range
188 : : [wmin, wmax]. */
189 : 36939 : widest2_int wtmin
190 : 73878 : = widest2_int::from (irange_val_min (type), TYPE_SIGN (type));
191 : 36939 : widest2_int wtmax
192 : 73878 : = 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 : 72868 : if (wmax < wtmin || wmin > wtmax)
197 : 1652 : return true;
198 : : return false;
199 : 221844 : }
200 : : return true;
201 : 144632 : }
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 : 6343649 : get_scev_info (vrange &r, tree name, gimple *stmt, class loop *l,
209 : : tree &init, tree &step, enum ev_direction &dir)
210 : : {
211 : 6343649 : tree ev = analyze_scalar_evolution (l, name);
212 : 6343649 : tree chrec = instantiate_parameters (l, ev);
213 : 6343649 : tree type = TREE_TYPE (name);
214 : 6343649 : if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
215 : : {
216 : 3136982 : r.set_varying (type);
217 : 3136982 : return false;
218 : : }
219 : 3206667 : 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 : 0 : return false;
226 : : }
227 : :
228 : 3206667 : init = initial_condition_in_loop_num (chrec, l->num);
229 : 3206667 : step = evolution_part_in_loop_num (chrec, l->num);
230 : 3206667 : if (!init || !step)
231 : : {
232 : 0 : r.set_varying (type);
233 : 0 : return false;
234 : : }
235 : 3206667 : dir = scev_direction (chrec);
236 : 3206667 : if (dir == EV_DIR_UNKNOWN
237 : 3206667 : || scev_probably_wraps_p (NULL, init, step, stmt,
238 : : get_chrec_loop (chrec), true))
239 : : {
240 : 780412 : r.set_varying (type);
241 : 780412 : 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 : 2070711 : induction_variable_may_overflow_p (tree type,
250 : : const wide_int &step, const widest_int &nit)
251 : : {
252 : 2070711 : wi::overflow_type ovf;
253 : 2070711 : signop sign = TYPE_SIGN (type);
254 : 2070711 : widest_int max_step = wi::mul (widest_int::from (step, sign),
255 : 2070711 : nit, sign, &ovf);
256 : :
257 : 2070711 : if (ovf || !wi::fits_to_tree_p (max_step, type))
258 : 23271 : 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 : 2047440 : return (sign == SIGNED
264 : 4094539 : && wi::gts_p (max_step, 0) != wi::gts_p (step, 0));
265 : 2070711 : }
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 : 2425849 : range_from_loop_direction (irange &r, tree type,
272 : : const irange &begin, const irange &end,
273 : : ev_direction dir)
274 : : {
275 : 2425849 : signop sign = TYPE_SIGN (type);
276 : :
277 : 2425849 : if (begin.undefined_p () || end.undefined_p ())
278 : 8291 : r.set_varying (type);
279 : 2417558 : else if (dir == EV_DIR_GROWS)
280 : : {
281 : 2255214 : if (wi::gt_p (begin.lower_bound (), end.upper_bound (), sign))
282 : 555 : r.set_varying (type);
283 : : else
284 : 2254659 : r = int_range<1> (type, begin.lower_bound (), end.upper_bound ());
285 : : }
286 : : else
287 : : {
288 : 162352 : if (wi::gt_p (end.lower_bound (), begin.upper_bound (), sign))
289 : 86 : r.set_varying (type);
290 : : else
291 : 162266 : r = int_range<1> (type, end.lower_bound (), begin.upper_bound ());
292 : : }
293 : 2425849 : }
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 : 6343649 : range_of_var_in_loop (vrange &v, tree name, class loop *l, gimple *stmt,
300 : : range_query *query)
301 : : {
302 : 6343649 : tree init, step;
303 : 6343649 : enum ev_direction dir;
304 : 6343649 : if (!get_scev_info (v, name, stmt, l, init, step, dir))
305 : : return true;
306 : :
307 : : // Calculate ranges for the values from SCEV.
308 : 2426255 : irange &r = as_a <irange> (v);
309 : 2426255 : tree type = TREE_TYPE (init);
310 : 2426255 : int_range<2> rinit (type), rstep (type), max_init (type);
311 : 2426255 : if (!query->range_of_expr (rinit, init, stmt)
312 : 2426255 : || !query->range_of_expr (rstep, step, stmt))
313 : 0 : return false;
314 : :
315 : : // Calculate the final range of NAME if possible.
316 : 2426255 : if (rinit.singleton_p () && rstep.singleton_p ())
317 : : {
318 : 2071117 : widest_int nit;
319 : 2071117 : if (!max_loop_iterations (l, &nit))
320 : : return false;
321 : :
322 : 2070711 : if (!induction_variable_may_overflow_p (type, rstep.lower_bound (), nit))
323 : : {
324 : : // Calculate the max bounds for init (init + niter * step).
325 : 2047099 : wide_int w = wide_int::from (nit, TYPE_PRECISION (type), TYPE_SIGN (type));
326 : 2047099 : int_range<1> niter (type, w, w);
327 : 2047099 : int_range_max max_step;
328 : 2047099 : range_op_handler mult_handler (MULT_EXPR);
329 : 2047099 : range_op_handler plus_handler (PLUS_EXPR);
330 : 2047099 : if (!mult_handler.fold_range (max_step, type, niter, rstep)
331 : 2047099 : || !plus_handler.fold_range (max_init, type, rinit, max_step))
332 : 0 : return false;
333 : 2047099 : }
334 : 2071117 : }
335 : 2425849 : range_from_loop_direction (r, type, rinit, max_init, dir);
336 : 2425849 : return true;
337 : 2426255 : }
338 : :
339 : : /* Helper function for vrp_evaluate_conditional_warnv & other
340 : : optimizers. */
341 : :
342 : : tree
343 : 20136430 : simplify_using_ranges::fold_cond_with_ops (enum tree_code code,
344 : : tree op0, tree op1, gimple *s)
345 : : {
346 : 20136430 : value_range r0 (TREE_TYPE (op0));
347 : 20136430 : value_range r1 (TREE_TYPE (op1));
348 : 20136430 : if (!query->range_of_expr (r0, op0, s)
349 : 20136430 : || !query->range_of_expr (r1, op1, s))
350 : 5938 : return NULL_TREE;
351 : :
352 : 20130492 : int_range<1> res;
353 : 20130492 : range_op_handler handler (code);
354 : :
355 : : // Find any relation between op0 and op1 and pass it to fold_range.
356 : 20130492 : relation_kind rel = VREL_VARYING;
357 : 20130492 : if (gimple_range_ssa_p (op0) && gimple_range_ssa_p (op1))
358 : 4432766 : rel = query->relation ().query (s, op0, op1);
359 : :
360 : 20130492 : if (handler && handler.fold_range (res, boolean_type_node, r0, r1,
361 : : relation_trio::op1_op2 (rel)))
362 : : {
363 : 20130492 : if (res == range_true ())
364 : 10172 : return boolean_true_node;
365 : 20120320 : if (res == range_false ())
366 : 4337 : return boolean_false_node;
367 : : }
368 : : return NULL;
369 : 20136430 : }
370 : :
371 : : /* Helper function for legacy_fold_cond. */
372 : :
373 : : tree
374 : 20561058 : simplify_using_ranges::legacy_fold_cond_overflow (gimple *stmt)
375 : : {
376 : 20561058 : tree ret;
377 : 20561058 : tree_code code = gimple_cond_code (stmt);
378 : 20561058 : tree op0 = gimple_cond_lhs (stmt);
379 : 20561058 : tree op1 = gimple_cond_rhs (stmt);
380 : :
381 : : /* We only deal with integral and pointer types. */
382 : 40731662 : if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
383 : 25014794 : && !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 : 19731650 : tree x;
395 : 19731650 : if (overflow_comparison_p (code, op0, op1, &x))
396 : : {
397 : 1345 : 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 : 1345 : if (integer_zerop (x))
403 : : {
404 : 162 : op1 = x;
405 : 162 : 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 : 1183 : else if (wi::to_wide (x) == max - 1)
412 : : {
413 : 847 : op0 = op1;
414 : 847 : op1 = wide_int_to_tree (TREE_TYPE (op0), 0);
415 : 847 : code = (code == GT_EXPR || code == GE_EXPR) ? EQ_EXPR : NE_EXPR;
416 : : }
417 : : else
418 : : {
419 : 336 : int_range_max vro, vri;
420 : 336 : tree type = TREE_TYPE (op0);
421 : 336 : if (code == GT_EXPR || code == GE_EXPR)
422 : : {
423 : 118 : vro.set (type,
424 : 236 : wi::to_wide (TYPE_MIN_VALUE (type)),
425 : 118 : wi::to_wide (x), VR_ANTI_RANGE);
426 : 118 : vri.set (type,
427 : 236 : wi::to_wide (TYPE_MIN_VALUE (type)),
428 : 236 : wi::to_wide (x));
429 : : }
430 : 218 : else if (code == LT_EXPR || code == LE_EXPR)
431 : : {
432 : 218 : vro.set (type,
433 : 436 : wi::to_wide (TYPE_MIN_VALUE (type)),
434 : 218 : wi::to_wide (x));
435 : 218 : vri.set (type,
436 : 436 : wi::to_wide (TYPE_MIN_VALUE (type)),
437 : 436 : wi::to_wide (x),
438 : : VR_ANTI_RANGE);
439 : : }
440 : : else
441 : 0 : gcc_unreachable ();
442 : 336 : int_range_max vr0;
443 : 336 : 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 : 336 : vro.intersect (vr0);
456 : 336 : if (vro.undefined_p ())
457 : 8 : return boolean_false_node;
458 : 328 : vri.intersect (vr0);
459 : 328 : if (vri.undefined_p ())
460 : 0 : return boolean_true_node;
461 : 336 : }
462 : 1345 : }
463 : :
464 : 19731642 : 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 : 20561058 : simplify_using_ranges::legacy_fold_cond (gcond *stmt, edge *taken_edge_p)
475 : : {
476 : 20561058 : tree val;
477 : :
478 : 20561058 : *taken_edge_p = NULL;
479 : :
480 : 20561058 : if (dump_file && (dump_flags & TDF_DETAILS))
481 : : {
482 : 377 : tree use;
483 : 377 : ssa_op_iter i;
484 : :
485 : 377 : fprintf (dump_file, "\nVisiting conditional with predicate: ");
486 : 377 : print_gimple_stmt (dump_file, stmt, 0);
487 : 377 : fprintf (dump_file, "\nWith known ranges\n");
488 : :
489 : 844 : FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
490 : : {
491 : 467 : fprintf (dump_file, "\t");
492 : 467 : print_generic_expr (dump_file, use);
493 : 467 : fprintf (dump_file, ": ");
494 : 467 : value_range r (TREE_TYPE (use));
495 : 467 : query->range_of_expr (r, use, stmt);
496 : 467 : r.dump (dump_file);
497 : 467 : }
498 : :
499 : 377 : fprintf (dump_file, "\n");
500 : : }
501 : :
502 : 20561058 : val = legacy_fold_cond_overflow (stmt);
503 : 20561058 : if (val)
504 : 8 : *taken_edge_p = find_taken_edge (gimple_bb (stmt), val);
505 : :
506 : 20561058 : if (dump_file && (dump_flags & TDF_DETAILS))
507 : : {
508 : 377 : fprintf (dump_file, "\nPredicate evaluates to: ");
509 : 377 : if (val == NULL_TREE)
510 : 377 : fprintf (dump_file, "DON'T KNOW\n");
511 : : else
512 : 0 : print_generic_stmt (dump_file, val);
513 : : }
514 : 20561058 : }
515 : :
516 : : /* Simplify boolean operations if the source is known
517 : : to be already a boolean. */
518 : : bool
519 : 464955 : simplify_using_ranges::simplify_truth_ops_using_ranges
520 : : (gimple_stmt_iterator *gsi,
521 : : gimple *stmt)
522 : : {
523 : 464955 : enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
524 : 464955 : tree lhs, op0, op1;
525 : 464955 : bool need_conversion;
526 : :
527 : : /* We handle only !=/== case here. */
528 : 464955 : gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR);
529 : :
530 : 464955 : op0 = gimple_assign_rhs1 (stmt);
531 : 464955 : if (!op_with_boolean_value_range_p (op0, stmt))
532 : : return false;
533 : :
534 : 16867 : op1 = gimple_assign_rhs2 (stmt);
535 : 16867 : 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 : 16468 : if (rhs_code == EQ_EXPR)
541 : : {
542 : 7557 : if (TREE_CODE (op1) == INTEGER_CST)
543 : 3205 : op1 = int_const_binop (BIT_XOR_EXPR, op1,
544 : 6410 : build_int_cst (TREE_TYPE (op1), 1));
545 : : else
546 : : return false;
547 : : }
548 : :
549 : 12116 : lhs = gimple_assign_lhs (stmt);
550 : 12116 : need_conversion
551 : 12116 : = !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 : 12116 : if (need_conversion
555 : 10633 : && !TYPE_UNSIGNED (TREE_TYPE (op0))
556 : 4561 : && TYPE_PRECISION (TREE_TYPE (op0)) == 1
557 : 12139 : && TYPE_PRECISION (TREE_TYPE (lhs)) > 1)
558 : : return false;
559 : :
560 : : /* For A != 0 we can substitute A itself. */
561 : 12116 : if (integer_zerop (op1))
562 : 7702 : 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 : 4414 : else if (need_conversion)
567 : : {
568 : 2931 : tree tem = make_ssa_name (TREE_TYPE (op0));
569 : 2931 : gassign *newop
570 : 2931 : = gimple_build_assign (tem, BIT_XOR_EXPR, op0, op1);
571 : 2931 : gsi_insert_before (gsi, newop, GSI_SAME_STMT);
572 : 5839 : if (INTEGRAL_TYPE_P (TREE_TYPE (tem))
573 : 5839 : && TYPE_PRECISION (TREE_TYPE (tem)) > 1)
574 : : {
575 : 5680 : int_range<1> vr (TREE_TYPE (tem),
576 : 5680 : wi::zero (TYPE_PRECISION (TREE_TYPE (tem))),
577 : 5680 : wi::one (TYPE_PRECISION (TREE_TYPE (tem))));
578 : 2840 : set_range_info (tem, vr);
579 : 2840 : }
580 : 2931 : gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem);
581 : : }
582 : : /* Or without. */
583 : : else
584 : 1483 : gimple_assign_set_rhs_with_ops (gsi, BIT_XOR_EXPR, op0, op1);
585 : 12116 : update_stmt (gsi_stmt (*gsi));
586 : 12116 : fold_stmt (gsi, follow_single_use_edges);
587 : :
588 : 12116 : 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 : 322862 : simplify_using_ranges::simplify_div_or_mod_using_ranges
601 : : (gimple_stmt_iterator *gsi,
602 : : gimple *stmt)
603 : : {
604 : 322862 : enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
605 : 322862 : tree val = NULL;
606 : 322862 : tree op0 = gimple_assign_rhs1 (stmt);
607 : 322862 : tree op1 = gimple_assign_rhs2 (stmt);
608 : 322862 : tree op0min = NULL_TREE, op0max = NULL_TREE;
609 : 322862 : tree op1min = op1;
610 : 322862 : int_range_max vr;
611 : :
612 : 322862 : if (TREE_CODE (op0) == INTEGER_CST)
613 : : {
614 : : op0min = op0;
615 : : op0max = op0;
616 : : }
617 : : else
618 : : {
619 : 298578 : if (!query->range_of_expr (vr, op0, stmt))
620 : 0 : vr.set_varying (TREE_TYPE (op0));
621 : 298578 : if (!vr.varying_p () && !vr.undefined_p ())
622 : : {
623 : 147567 : tree type = vr.type ();
624 : 147567 : op0min = wide_int_to_tree (type, vr.lower_bound ());
625 : 147576 : op0max = wide_int_to_tree (type, vr.upper_bound ());
626 : : }
627 : : }
628 : :
629 : 322862 : if (rhs_code == TRUNC_MOD_EXPR
630 : 148384 : && TREE_CODE (op1) == SSA_NAME)
631 : : {
632 : 86529 : int_range_max vr1;
633 : 86529 : if (!query->range_of_expr (vr1, op1, stmt))
634 : 0 : vr1.set_varying (TREE_TYPE (op1));
635 : 86529 : if (!vr1.varying_p () && !vr1.undefined_p ())
636 : 25187 : op1min = wide_int_to_tree (vr1.type (), vr1.lower_bound ());
637 : 86529 : }
638 : 148384 : if (rhs_code == TRUNC_MOD_EXPR
639 : 148384 : && TREE_CODE (op1min) == INTEGER_CST
640 : 87038 : && tree_int_cst_sgn (op1min) == 1
641 : 66546 : && op0max
642 : 39734 : && tree_int_cst_lt (op0max, op1min))
643 : : {
644 : 1159 : if (TYPE_UNSIGNED (TREE_TYPE (op0))
645 : 473 : || tree_int_cst_sgn (op0min) >= 0
646 : 1324 : || 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 : 1125 : gimple_assign_set_rhs_from_tree (gsi, op0);
652 : 1125 : return true;
653 : : }
654 : : }
655 : :
656 : 321737 : if (TREE_CODE (op0) != SSA_NAME)
657 : : return false;
658 : :
659 : 297460 : 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 : 258644 : if (rhs_code == TRUNC_MOD_EXPR
666 : 258644 : && fold_stmt (gsi, follow_single_use_edges))
667 : : return true;
668 : 258644 : return false;
669 : : }
670 : :
671 : 38816 : if (TYPE_UNSIGNED (TREE_TYPE (op0)))
672 : 0 : val = integer_one_node;
673 : : else
674 : : {
675 : 38816 : tree zero = build_zero_cst (TREE_TYPE (op0));
676 : 38816 : val = fold_cond_with_ops (GE_EXPR, op0, zero, stmt);
677 : : }
678 : :
679 : 38816 : if (val && integer_onep (val))
680 : : {
681 : 5971 : tree t;
682 : :
683 : 5971 : if (rhs_code == TRUNC_DIV_EXPR)
684 : : {
685 : 3617 : t = build_int_cst (integer_type_node, tree_log2 (op1));
686 : 3617 : gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR);
687 : 3617 : gimple_assign_set_rhs1 (stmt, op0);
688 : 3617 : gimple_assign_set_rhs2 (stmt, t);
689 : : }
690 : : else
691 : : {
692 : 2354 : t = build_int_cst (TREE_TYPE (op1), 1);
693 : 2354 : t = int_const_binop (MINUS_EXPR, op1, t);
694 : 2354 : t = fold_convert (TREE_TYPE (op0), t);
695 : :
696 : 2354 : gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR);
697 : 2354 : gimple_assign_set_rhs1 (stmt, op0);
698 : 2354 : gimple_assign_set_rhs2 (stmt, t);
699 : : }
700 : :
701 : 5971 : update_stmt (stmt);
702 : 5971 : fold_stmt (gsi, follow_single_use_edges);
703 : 5971 : return true;
704 : : }
705 : :
706 : : return false;
707 : 322862 : }
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 : 179980 : simplify_using_ranges::simplify_min_or_max_using_ranges
714 : : (gimple_stmt_iterator *gsi,
715 : : gimple *stmt)
716 : : {
717 : 179980 : tree op0 = gimple_assign_rhs1 (stmt);
718 : 179980 : tree op1 = gimple_assign_rhs2 (stmt);
719 : 179980 : tree val;
720 : :
721 : 179980 : val = fold_cond_with_ops (LE_EXPR, op0, op1, stmt);
722 : 179980 : if (!val)
723 : 172581 : val = fold_cond_with_ops (LT_EXPR, op0, op1, stmt);
724 : :
725 : 172581 : if (val)
726 : : {
727 : : /* VAL == TRUE -> OP0 < or <= op1
728 : : VAL == FALSE -> OP0 > or >= op1. */
729 : 8079 : tree res = ((gimple_assign_rhs_code (stmt) == MAX_EXPR)
730 : 8079 : == integer_zerop (val)) ? op0 : op1;
731 : 8079 : gimple_assign_set_rhs_from_tree (gsi, res);
732 : 8079 : 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 : 6828 : simplify_using_ranges::simplify_abs_using_ranges (gimple_stmt_iterator *gsi,
744 : : gimple *stmt)
745 : : {
746 : 6828 : tree op = gimple_assign_rhs1 (stmt);
747 : 6828 : tree zero = build_zero_cst (TREE_TYPE (op));
748 : 6828 : tree val = fold_cond_with_ops (LE_EXPR, op, zero, stmt);
749 : :
750 : 6828 : if (!val)
751 : : {
752 : : /* The range is neither <= 0 nor > 0. Now see if it is
753 : : either < 0 or >= 0. */
754 : 6583 : val = fold_cond_with_ops (LT_EXPR, op, zero, stmt);
755 : : }
756 : 6583 : if (val)
757 : : {
758 : 458 : gimple_assign_set_rhs1 (stmt, op);
759 : 458 : if (integer_zerop (val))
760 : 294 : gimple_assign_set_rhs_code (stmt, SSA_NAME);
761 : : else
762 : 164 : gimple_assign_set_rhs_code (stmt, NEGATE_EXPR);
763 : 458 : update_stmt (stmt);
764 : 458 : fold_stmt (gsi, follow_single_use_edges);
765 : 458 : 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 : 1683078 : 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 : 1683078 : if (vr->varying_p () || vr->undefined_p ())
782 : : {
783 : 989191 : *may_be_nonzero = wi::minus_one (TYPE_PRECISION (expr_type));
784 : 989191 : *must_be_nonzero = wi::zero (TYPE_PRECISION (expr_type));
785 : 989191 : return false;
786 : : }
787 : 693889 : wi_set_zero_nonzero_bits (expr_type, vr->lower_bound (), vr->upper_bound (),
788 : : *may_be_nonzero, *must_be_nonzero);
789 : 693887 : 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 : 1317856 : simplify_using_ranges::simplify_bit_ops_using_ranges
800 : : (gimple_stmt_iterator *gsi,
801 : : gimple *stmt)
802 : : {
803 : 1317856 : tree op0 = gimple_assign_rhs1 (stmt);
804 : 1317856 : tree op1 = gimple_assign_rhs2 (stmt);
805 : 1317856 : tree op = NULL_TREE;
806 : 1317856 : int_range_max vr0, vr1;
807 : 1317856 : wide_int may_be_nonzero0, may_be_nonzero1;
808 : 1317856 : wide_int must_be_nonzero0, must_be_nonzero1;
809 : 1317856 : wide_int mask;
810 : :
811 : 1317856 : if (!query->range_of_expr (vr0, op0, stmt)
812 : 1317856 : || vr0.undefined_p ())
813 : : return false;
814 : 1317135 : if (!query->range_of_expr (vr1, op1, stmt)
815 : 1317135 : || vr1.undefined_p ())
816 : : return false;
817 : :
818 : 1316802 : if (!vr_set_zero_nonzero_bits (TREE_TYPE (op0), &vr0, &may_be_nonzero0,
819 : : &must_be_nonzero0))
820 : : return false;
821 : 366276 : if (!vr_set_zero_nonzero_bits (TREE_TYPE (op1), &vr1, &may_be_nonzero1,
822 : : &must_be_nonzero1))
823 : : return false;
824 : :
825 : 327611 : switch (gimple_assign_rhs_code (stmt))
826 : : {
827 : 230557 : case BIT_AND_EXPR:
828 : 230557 : mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
829 : 230557 : if (mask == 0)
830 : : {
831 : : op = op0;
832 : : break;
833 : : }
834 : 225533 : mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
835 : 225533 : if (mask == 0)
836 : : {
837 : : op = op1;
838 : : break;
839 : : }
840 : : break;
841 : 97054 : case BIT_IOR_EXPR:
842 : 97054 : mask = wi::bit_and_not (may_be_nonzero0, must_be_nonzero1);
843 : 97054 : if (mask == 0)
844 : : {
845 : : op = op1;
846 : : break;
847 : : }
848 : 97053 : mask = wi::bit_and_not (may_be_nonzero1, must_be_nonzero0);
849 : 97053 : if (mask == 0)
850 : : {
851 : : op = op0;
852 : : break;
853 : : }
854 : : break;
855 : 0 : default:
856 : 0 : gcc_unreachable ();
857 : : }
858 : :
859 : 5242 : if (op == NULL_TREE)
860 : 322369 : return false;
861 : :
862 : 5242 : gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op);
863 : 5242 : update_stmt (gsi_stmt (*gsi));
864 : 5242 : return true;
865 : 1317868 : }
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 : : If signed overflow must be undefined for the value to satisfy
874 : : the conditional, then set *STRICT_OVERFLOW_P to true. */
875 : :
876 : : static tree
877 : 1485794 : test_for_singularity (enum tree_code cond_code, tree op0,
878 : : tree op1, const irange *vr)
879 : : {
880 : 1485794 : tree min = NULL;
881 : 1485794 : tree max = NULL;
882 : :
883 : : /* Extract minimum/maximum values which satisfy the conditional as it was
884 : : written. */
885 : 1485794 : if (cond_code == LE_EXPR || cond_code == LT_EXPR)
886 : : {
887 : 648090 : min = TYPE_MIN_VALUE (TREE_TYPE (op0));
888 : :
889 : 648090 : max = op1;
890 : 648090 : if (cond_code == LT_EXPR)
891 : : {
892 : 90102 : tree one = build_int_cst (TREE_TYPE (op0), 1);
893 : 90102 : max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
894 : : /* Signal to compare_values_warnv this expr doesn't overflow. */
895 : 90102 : if (EXPR_P (max))
896 : 0 : suppress_warning (max, OPT_Woverflow);
897 : : }
898 : : }
899 : 837704 : else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
900 : : {
901 : 723310 : max = TYPE_MAX_VALUE (TREE_TYPE (op0));
902 : :
903 : 723310 : min = op1;
904 : 723310 : if (cond_code == GT_EXPR)
905 : : {
906 : 634757 : tree one = build_int_cst (TREE_TYPE (op0), 1);
907 : 634757 : min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
908 : : /* Signal to compare_values_warnv this expr doesn't overflow. */
909 : 634757 : if (EXPR_P (min))
910 : 0 : suppress_warning (min, OPT_Woverflow);
911 : : }
912 : : }
913 : :
914 : : /* Now refine the minimum and maximum values using any
915 : : value range information we have for op0. */
916 : 1485794 : if (min && max)
917 : : {
918 : 1371400 : tree type = TREE_TYPE (op0);
919 : 1371400 : tree tmin = wide_int_to_tree (type, vr->lower_bound ());
920 : 1371400 : tree tmax = wide_int_to_tree (type, vr->upper_bound ());
921 : 1371400 : if (compare_values (tmin, min) == 1)
922 : 410760 : min = tmin;
923 : 1371400 : if (compare_values (tmax, max) == -1)
924 : 519764 : max = tmax;
925 : :
926 : : /* If the new min/max values have converged to a single value,
927 : : then there is only one value which can satisfy the condition,
928 : : return that value. */
929 : 1371400 : if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
930 : : return min;
931 : : }
932 : : return NULL;
933 : : }
934 : :
935 : : /* Return whether the value range *VR fits in an integer type specified
936 : : by PRECISION and UNSIGNED_P. */
937 : :
938 : : bool
939 : 237114 : range_fits_type_p (const irange *vr,
940 : : unsigned dest_precision, signop dest_sgn)
941 : : {
942 : 237114 : tree src_type;
943 : 237114 : unsigned src_precision;
944 : 237114 : widest_int tem;
945 : 237114 : signop src_sgn;
946 : :
947 : : /* Now we can only handle ranges with constant bounds. */
948 : 237114 : if (vr->undefined_p () || vr->varying_p ())
949 : : return false;
950 : :
951 : : /* We can only handle integral and pointer types. */
952 : 187229 : src_type = vr->type ();
953 : 187229 : if (!INTEGRAL_TYPE_P (src_type)
954 : 0 : && !POINTER_TYPE_P (src_type))
955 : : return false;
956 : :
957 : : /* An extension is fine unless VR is SIGNED and dest_sgn is UNSIGNED,
958 : : and so is an identity transform. */
959 : 187229 : src_precision = TYPE_PRECISION (src_type);
960 : 187229 : src_sgn = TYPE_SIGN (src_type);
961 : 187229 : if ((src_precision < dest_precision
962 : 7460 : && !(dest_sgn == UNSIGNED && src_sgn == SIGNED))
963 : 180869 : || (src_precision == dest_precision && src_sgn == dest_sgn))
964 : : return true;
965 : :
966 : 180768 : wide_int vrmin = vr->lower_bound ();
967 : 180768 : wide_int vrmax = vr->upper_bound ();
968 : :
969 : : /* For sign changes, the MSB of the wide_int has to be clear.
970 : : An unsigned value with its MSB set cannot be represented by
971 : : a signed wide_int, while a negative value cannot be represented
972 : : by an unsigned wide_int. */
973 : 180768 : if (src_sgn != dest_sgn
974 : 180768 : && (wi::lts_p (vrmin, 0) || wi::lts_p (vrmax, 0)))
975 : 54826 : return false;
976 : :
977 : : /* Then we can perform the conversion on both ends and compare
978 : : the result for equality. */
979 : 125942 : signop sign = TYPE_SIGN (vr->type ());
980 : 125942 : tem = wi::ext (widest_int::from (vrmin, sign), dest_precision, dest_sgn);
981 : 125942 : if (tem != widest_int::from (vrmin, sign))
982 : : return false;
983 : 119262 : tem = wi::ext (widest_int::from (vrmax, sign), dest_precision, dest_sgn);
984 : 119262 : if (tem != widest_int::from (vrmax, sign))
985 : : return false;
986 : :
987 : : return true;
988 : 180768 : }
989 : :
990 : : // Clear edge E of EDGE_EXECUTABLE (it is unexecutable). If it wasn't
991 : : // previously clear, propagate to successor blocks if appropriate.
992 : :
993 : : void
994 : 302681 : simplify_using_ranges::set_and_propagate_unexecutable (edge e)
995 : : {
996 : : // If not_executable is already set, we're done.
997 : : // This works in the absence of a flag as well.
998 : 302681 : if ((e->flags & m_not_executable_flag) == m_not_executable_flag)
999 : 213741 : return;
1000 : :
1001 : 195387 : e->flags |= m_not_executable_flag;
1002 : 195387 : m_flag_set_edges.safe_push (e);
1003 : :
1004 : : // Check if the destination block needs to propagate the property.
1005 : 195387 : basic_block bb = e->dest;
1006 : :
1007 : : // If any incoming edge is executable, we are done.
1008 : 195387 : edge_iterator ei;
1009 : 326488 : FOR_EACH_EDGE (e, ei, bb->preds)
1010 : 237548 : if ((e->flags & m_not_executable_flag) == 0)
1011 : : return;
1012 : :
1013 : : // This block is also unexecutable, propagate to all exit edges as well.
1014 : 156509 : FOR_EACH_EDGE (e, ei, bb->succs)
1015 : 67569 : set_and_propagate_unexecutable (e);
1016 : : }
1017 : :
1018 : : /* If COND can be folded entirely as TRUE or FALSE, rewrite the
1019 : : conditional as such, and return TRUE. */
1020 : :
1021 : : bool
1022 : 20866797 : simplify_using_ranges::fold_cond (gcond *cond)
1023 : : {
1024 : 20866797 : int_range_max r;
1025 : 20866797 : if (query->range_of_stmt (r, cond) && r.singleton_p ())
1026 : : {
1027 : : // COND has already been folded if arguments are constant.
1028 : 305739 : if (TREE_CODE (gimple_cond_lhs (cond)) != SSA_NAME
1029 : 305739 : && TREE_CODE (gimple_cond_rhs (cond)) != SSA_NAME)
1030 : : return false;
1031 : 228146 : if (dump_file)
1032 : : {
1033 : 184 : fprintf (dump_file, "Folding predicate ");
1034 : 184 : print_gimple_expr (dump_file, cond, 0);
1035 : 184 : fprintf (dump_file, " to ");
1036 : : }
1037 : 228146 : edge e0 = EDGE_SUCC (gimple_bb (cond), 0);
1038 : 228146 : edge e1 = EDGE_SUCC (gimple_bb (cond), 1);
1039 : 228146 : if (r.zero_p ())
1040 : : {
1041 : 142957 : if (dump_file)
1042 : 128 : fprintf (dump_file, "0\n");
1043 : 142957 : gimple_cond_make_false (cond);
1044 : 142957 : if (e0->flags & EDGE_TRUE_VALUE)
1045 : 141462 : set_and_propagate_unexecutable (e0);
1046 : : else
1047 : 1495 : set_and_propagate_unexecutable (e1);
1048 : : }
1049 : : else
1050 : : {
1051 : 85189 : if (dump_file)
1052 : 56 : fprintf (dump_file, "1\n");
1053 : 85189 : gimple_cond_make_true (cond);
1054 : 85189 : if (e0->flags & EDGE_FALSE_VALUE)
1055 : 817 : set_and_propagate_unexecutable (e0);
1056 : : else
1057 : 84372 : set_and_propagate_unexecutable (e1);
1058 : : }
1059 : 228146 : update_stmt (cond);
1060 : 228146 : return true;
1061 : : }
1062 : :
1063 : : // FIXME: Audit the code below and make sure it never finds anything.
1064 : 20561058 : edge taken_edge;
1065 : 20561058 : legacy_fold_cond (cond, &taken_edge);
1066 : :
1067 : 20561058 : if (taken_edge)
1068 : : {
1069 : 8 : if (taken_edge->flags & EDGE_TRUE_VALUE)
1070 : : {
1071 : 0 : if (dump_file && (dump_flags & TDF_DETAILS))
1072 : 0 : fprintf (dump_file, "\nVRP Predicate evaluates to: 1\n");
1073 : 0 : gimple_cond_make_true (cond);
1074 : : }
1075 : 8 : else if (taken_edge->flags & EDGE_FALSE_VALUE)
1076 : : {
1077 : 8 : if (dump_file && (dump_flags & TDF_DETAILS))
1078 : 0 : fprintf (dump_file, "\nVRP Predicate evaluates to: 0\n");
1079 : 8 : gimple_cond_make_false (cond);
1080 : : }
1081 : : else
1082 : 0 : gcc_unreachable ();
1083 : 8 : update_stmt (cond);
1084 : 8 : return true;
1085 : : }
1086 : : return false;
1087 : 20866797 : }
1088 : :
1089 : : /* Simplify a conditional using a relational operator to an equality
1090 : : test if the range information indicates only one value can satisfy
1091 : : the original conditional. */
1092 : :
1093 : : bool
1094 : 11994600 : simplify_using_ranges::simplify_cond_using_ranges_1 (gcond *stmt)
1095 : : {
1096 : 11994600 : tree op0 = gimple_cond_lhs (stmt);
1097 : 11994600 : tree op1 = gimple_cond_rhs (stmt);
1098 : 11994600 : enum tree_code cond_code = gimple_cond_code (stmt);
1099 : :
1100 : 11994600 : if (fold_cond (stmt))
1101 : : return true;
1102 : :
1103 : 11873335 : if (simplify_compare_using_ranges_1 (cond_code, op0, op1, stmt))
1104 : : {
1105 : 338579 : if (dump_file)
1106 : : {
1107 : 26 : fprintf (dump_file, "Simplified relational ");
1108 : 26 : print_gimple_stmt (dump_file, stmt, 0);
1109 : 26 : fprintf (dump_file, " into ");
1110 : : }
1111 : :
1112 : 338579 : gimple_cond_set_code (stmt, cond_code);
1113 : 338579 : gimple_cond_set_lhs (stmt, op0);
1114 : 338579 : gimple_cond_set_rhs (stmt, op1);
1115 : :
1116 : 338579 : update_stmt (stmt);
1117 : :
1118 : 338579 : if (dump_file)
1119 : : {
1120 : 26 : print_gimple_stmt (dump_file, stmt, 0);
1121 : 26 : fprintf (dump_file, "\n");
1122 : : }
1123 : 338579 : return true;
1124 : : }
1125 : : return false;
1126 : : }
1127 : :
1128 : : /* Like simplify_cond_using_ranges_1 but for assignments rather
1129 : : than GIMPLE_COND. */
1130 : :
1131 : : bool
1132 : 1219804 : simplify_using_ranges::simplify_compare_assign_using_ranges_1
1133 : : (gimple_stmt_iterator *gsi,
1134 : : gimple *stmt)
1135 : : {
1136 : 1219804 : enum tree_code code = gimple_assign_rhs_code (stmt);
1137 : 1219804 : tree op0 = gimple_assign_rhs1 (stmt);
1138 : 1219804 : tree op1 = gimple_assign_rhs2 (stmt);
1139 : 1219804 : gcc_assert (TREE_CODE_CLASS (code) == tcc_comparison);
1140 : 1219804 : bool happened = false;
1141 : :
1142 : 1219804 : if (simplify_compare_using_ranges_1 (code, op0, op1, stmt))
1143 : : {
1144 : 6754 : if (dump_file)
1145 : : {
1146 : 3 : fprintf (dump_file, "Simplified relational ");
1147 : 3 : print_gimple_stmt (dump_file, stmt, 0);
1148 : 3 : fprintf (dump_file, " into ");
1149 : : }
1150 : :
1151 : 6754 : gimple_assign_set_rhs_code (stmt, code);
1152 : 6754 : gimple_assign_set_rhs1 (stmt, op0);
1153 : 6754 : gimple_assign_set_rhs2 (stmt, op1);
1154 : :
1155 : 6754 : update_stmt (stmt);
1156 : :
1157 : 6754 : if (dump_file)
1158 : : {
1159 : 3 : print_gimple_stmt (dump_file, stmt, 0);
1160 : 3 : fprintf (dump_file, "\n");
1161 : : }
1162 : : happened = true;
1163 : : }
1164 : :
1165 : : /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
1166 : : if the RHS is zero or one, and the LHS are known to be boolean
1167 : : values. */
1168 : 1219804 : if ((code == EQ_EXPR || code == NE_EXPR)
1169 : 664951 : && INTEGRAL_TYPE_P (TREE_TYPE (op0))
1170 : 1684759 : && simplify_truth_ops_using_ranges (gsi, stmt))
1171 : : happened = true;
1172 : :
1173 : 1219804 : return happened;
1174 : : }
1175 : :
1176 : : /* Try to simplify OP0 COND_CODE OP1 using a relational operator to an
1177 : : equality test if the range information indicates only one value can
1178 : : satisfy the original conditional. */
1179 : :
1180 : : bool
1181 : 13093139 : simplify_using_ranges::simplify_compare_using_ranges_1 (tree_code &cond_code, tree &op0, tree &op1, gimple *stmt)
1182 : : {
1183 : 13093139 : bool happened = false;
1184 : 13093139 : if (cond_code != NE_EXPR
1185 : 13093139 : && cond_code != EQ_EXPR
1186 : 3373635 : && TREE_CODE (op0) == SSA_NAME
1187 : 3373198 : && INTEGRAL_TYPE_P (TREE_TYPE (op0))
1188 : 16123188 : && is_gimple_min_invariant (op1))
1189 : : {
1190 : 1806260 : int_range_max vr;
1191 : :
1192 : 1806260 : if (!query->range_of_expr (vr, op0, stmt))
1193 : 0 : vr.set_undefined ();
1194 : :
1195 : : /* If we have range information for OP0, then we might be
1196 : : able to simplify this conditional. */
1197 : 1806260 : if (!vr.undefined_p () && !vr.varying_p ())
1198 : : {
1199 : 742897 : tree new_tree = test_for_singularity (cond_code, op0, op1, &vr);
1200 : 742897 : if (new_tree)
1201 : : {
1202 : 114394 : cond_code = EQ_EXPR;
1203 : 114394 : op1 = new_tree;
1204 : 114394 : happened = true;
1205 : : }
1206 : :
1207 : : /* Try again after inverting the condition. We only deal
1208 : : with integral types here, so no need to worry about
1209 : : issues with inverting FP comparisons. */
1210 : 742897 : new_tree = test_for_singularity
1211 : 742897 : (invert_tree_comparison (cond_code, false),
1212 : : op0, op1, &vr);
1213 : 742897 : if (new_tree)
1214 : : {
1215 : 163034 : cond_code = NE_EXPR;
1216 : 163034 : op1 = new_tree;
1217 : 163034 : happened = true;
1218 : : }
1219 : : }
1220 : 1806260 : }
1221 : : // Try to simplify casted conditions.
1222 : 13093139 : if (simplify_casted_compare (cond_code, op0, op1))
1223 : 75312 : happened = true;
1224 : 13093139 : return happened;
1225 : : }
1226 : :
1227 : : /* Simplify OP0 code OP1 when OP1 is a constant and OP0 was a SSA_NAME
1228 : : defined by a type conversion. Replacing OP0 with RHS of the type conversion.
1229 : : Doing so makes the conversion dead which helps subsequent passes. */
1230 : :
1231 : : bool
1232 : 13093139 : simplify_using_ranges::simplify_casted_compare (tree_code &, tree &op0, tree &op1)
1233 : : {
1234 : :
1235 : : /* If we have a comparison of an SSA_NAME (OP0) against a constant,
1236 : : see if OP0 was set by a type conversion where the source of
1237 : : the conversion is another SSA_NAME with a range that fits
1238 : : into the range of OP0's type.
1239 : :
1240 : : If so, the conversion is redundant as the earlier SSA_NAME can be
1241 : : used for the comparison directly if we just massage the constant in the
1242 : : comparison. */
1243 : 13093139 : if (TREE_CODE (op0) == SSA_NAME
1244 : 13011488 : && TREE_CODE (op1) == INTEGER_CST)
1245 : : {
1246 : 9173047 : gimple *def_stmt = SSA_NAME_DEF_STMT (op0);
1247 : 9173047 : tree innerop;
1248 : :
1249 : 9173047 : if (!is_gimple_assign (def_stmt))
1250 : : return false;
1251 : :
1252 : 5646048 : switch (gimple_assign_rhs_code (def_stmt))
1253 : : {
1254 : 463846 : CASE_CONVERT:
1255 : 463846 : innerop = gimple_assign_rhs1 (def_stmt);
1256 : 463846 : break;
1257 : 48066 : case VIEW_CONVERT_EXPR:
1258 : 48066 : innerop = TREE_OPERAND (gimple_assign_rhs1 (def_stmt), 0);
1259 : 48066 : if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop)))
1260 : : return false;
1261 : : break;
1262 : : default:
1263 : : return false;
1264 : : }
1265 : :
1266 : 510940 : if (TREE_CODE (innerop) == SSA_NAME
1267 : 510912 : && !POINTER_TYPE_P (TREE_TYPE (innerop))
1268 : 505221 : && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop)
1269 : 1016148 : && desired_pro_or_demotion_p (TREE_TYPE (innerop), TREE_TYPE (op0)))
1270 : : {
1271 : 474549 : int_range_max vr;
1272 : :
1273 : 474549 : if (query->range_of_expr (vr, innerop)
1274 : 474546 : && !vr.varying_p ()
1275 : 149800 : && !vr.undefined_p ()
1276 : 149675 : && range_fits_type_p (&vr,
1277 : 149675 : TYPE_PRECISION (TREE_TYPE (op0)),
1278 : 149675 : TYPE_SIGN (TREE_TYPE (op0)))
1279 : 549861 : && int_fits_type_p (op1, TREE_TYPE (innerop)))
1280 : : {
1281 : 75312 : tree newconst = fold_convert (TREE_TYPE (innerop), op1);
1282 : 75312 : op0 = innerop;
1283 : 75312 : op1 = newconst;
1284 : 75312 : return true;
1285 : : }
1286 : 474549 : }
1287 : : }
1288 : : return false;
1289 : : }
1290 : :
1291 : : /* Simplify a switch statement using the value range of the switch
1292 : : argument. */
1293 : :
1294 : : bool
1295 : 65999 : simplify_using_ranges::simplify_switch_using_ranges (gswitch *stmt)
1296 : : {
1297 : 65999 : tree op = gimple_switch_index (stmt);
1298 : 65999 : tree type = TREE_TYPE (op);
1299 : 65999 : int_range_max op_range (type);
1300 : 65999 : int_range_max default_range (type);
1301 : 65999 : auto_vec<unsigned> cases;
1302 : 65999 : cases.truncate (0);
1303 : 65999 : edge e;
1304 : 65999 : switch_update su;
1305 : :
1306 : : // Abort if we don't have a useful range for the switch index.
1307 : 65999 : if (!query->range_of_expr (op_range, op, stmt)
1308 : 65999 : || op_range.varying_p () || op_range.undefined_p ())
1309 : : return false;
1310 : :
1311 : : // Default range starts with full known range of op.
1312 : 15737 : default_range = op_range;
1313 : 15737 : edge default_edge = gimple_switch_default_edge (cfun, stmt);
1314 : :
1315 : 15737 : unsigned x, lim = gimple_switch_num_labels (stmt);
1316 : 94098 : for (x = 1; x < lim; x++)
1317 : : {
1318 : 79086 : e = gimple_switch_edge (cfun, stmt, x);
1319 : 79086 : tree label = gimple_switch_label (stmt, x);
1320 : :
1321 : : // If this edge is the same as the default edge, do nothing else.
1322 : 79086 : if (e == default_edge)
1323 : 6178 : continue;
1324 : : // Ada sometimes has mismatched labels and index. Just bail.
1325 : 79080 : if (TREE_TYPE (CASE_LOW (label)) != type)
1326 : 725 : return false;
1327 : :
1328 : 78355 : wide_int low = wi::to_wide (CASE_LOW (label));
1329 : 78355 : wide_int high;
1330 : : // Singleton cases have no CASE_HIGH.
1331 : 78355 : tree tree_high = CASE_HIGH (label);
1332 : 78355 : if (tree_high)
1333 : 3620 : high = wi::to_wide (tree_high);
1334 : : else
1335 : 74735 : high = low;
1336 : :
1337 : : // If the case range is fully contained in op_range, leave the
1338 : : // case as it is, otherwise adjust the labels.
1339 : 78355 : int_range_max case_range (type, low, high);
1340 : 78355 : if (case_range.intersect (op_range))
1341 : : {
1342 : : // If none of the label is in op_range, skip this label.
1343 : 6208 : if (case_range.undefined_p ())
1344 : 6172 : continue;
1345 : :
1346 : : // Part of the label is in op_range, but not all of it. CASE_RANGE
1347 : : // contains the part that is. Adjust the case range to
1348 : : // the new min/max.
1349 : 36 : if (case_range.lower_bound () != low)
1350 : 10 : CASE_LOW (label) = wide_int_to_tree (type,
1351 : 20 : case_range.lower_bound ());
1352 : 36 : if (case_range.singleton_p ())
1353 : 4 : CASE_HIGH (label) = NULL_TREE;
1354 : : else
1355 : 32 : if (case_range.upper_bound () != high)
1356 : 7 : CASE_HIGH (label) = wide_int_to_tree (type,
1357 : 14 : case_range.upper_bound ());
1358 : : }
1359 : : // Add case label to the keep list.
1360 : 72183 : cases.safe_push (x);
1361 : : // Remove case_range from needing to be handled by the default.
1362 : 72183 : case_range.invert ();
1363 : 72183 : default_range.intersect (case_range);
1364 : 78355 : }
1365 : :
1366 : : // An undefined DEFAULT range means the current default case is not needed.
1367 : 15012 : unsigned idx = default_range.undefined_p () ? 0 : 1;
1368 : 15012 : unsigned vec_size = cases.length () + idx;
1369 : 15012 : if (vec_size == lim)
1370 : : return false;
1371 : :
1372 : 4037 : tree vec2 = make_tree_vec (vec_size);
1373 : : // Add default label if there is one.
1374 : 4037 : if (idx)
1375 : : {
1376 : 3102 : TREE_VEC_ELT (vec2, 0) = gimple_switch_default_label (stmt);
1377 : 3102 : e = gimple_switch_edge (cfun, stmt, 0);
1378 : 3102 : e->aux = (void *)-1;
1379 : : }
1380 : :
1381 : 15880 : for (x = 0; x < cases.length (); x++)
1382 : : {
1383 : 11843 : unsigned swi = cases[x];
1384 : 11843 : TREE_VEC_ELT (vec2, idx++) = gimple_switch_label (stmt, swi);
1385 : 11843 : e = gimple_switch_edge (cfun, stmt, swi);
1386 : 11843 : e->aux = (void *)-1;
1387 : : }
1388 : :
1389 : : /* Queue not needed edges for later removal. */
1390 : 4037 : edge_iterator ei;
1391 : 25300 : FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->succs)
1392 : : {
1393 : 21263 : if (e->aux == (void *)-1)
1394 : : {
1395 : 14297 : e->aux = NULL;
1396 : 14297 : continue;
1397 : : }
1398 : :
1399 : 6966 : if (dump_file && (dump_flags & TDF_DETAILS))
1400 : : {
1401 : 0 : fprintf (dump_file, "removing unreachable case label\n");
1402 : : }
1403 : 6966 : to_remove_edges.safe_push (e);
1404 : 6966 : set_and_propagate_unexecutable (e);
1405 : 6966 : e->flags &= ~EDGE_EXECUTABLE;
1406 : 6966 : e->flags |= EDGE_IGNORE;
1407 : : }
1408 : :
1409 : : /* And queue an update for the stmt. */
1410 : 4037 : su.stmt = stmt;
1411 : 4037 : su.vec = vec2;
1412 : 4037 : to_update_switch_stmts.safe_push (su);
1413 : 4037 : return true;
1414 : 65999 : }
1415 : :
1416 : : void
1417 : 13096104 : simplify_using_ranges::cleanup_edges_and_switches (void)
1418 : : {
1419 : 13096104 : int i;
1420 : 13096104 : edge e;
1421 : 13096104 : switch_update *su;
1422 : :
1423 : : /* Clear any edges marked as not executable. */
1424 : 13096104 : if (m_not_executable_flag)
1425 : : {
1426 : 4419288 : FOR_EACH_VEC_ELT (m_flag_set_edges, i, e)
1427 : 195387 : e->flags &= ~m_not_executable_flag;
1428 : : }
1429 : : /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
1430 : : CFG in a broken state and requires a cfg_cleanup run. */
1431 : 13106821 : FOR_EACH_VEC_ELT (to_remove_edges, i, e)
1432 : 6966 : remove_edge (e);
1433 : :
1434 : : /* Update SWITCH_EXPR case label vector. */
1435 : 13100141 : FOR_EACH_VEC_ELT (to_update_switch_stmts, i, su)
1436 : : {
1437 : 4037 : size_t j;
1438 : 4037 : size_t n = TREE_VEC_LENGTH (su->vec);
1439 : 4037 : tree label;
1440 : 4037 : gimple_switch_set_num_labels (su->stmt, n);
1441 : 23019 : for (j = 0; j < n; j++)
1442 : 14945 : gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
1443 : : /* As we may have replaced the default label with a regular one
1444 : : make sure to make it a real default label again. This ensures
1445 : : optimal expansion. */
1446 : 4037 : label = gimple_switch_label (su->stmt, 0);
1447 : 4037 : CASE_LOW (label) = NULL_TREE;
1448 : 4037 : CASE_HIGH (label) = NULL_TREE;
1449 : : }
1450 : :
1451 : 13096104 : if (!to_remove_edges.is_empty ())
1452 : : {
1453 : 3751 : free_dominance_info (CDI_DOMINATORS);
1454 : 3751 : loops_state_set (LOOPS_NEED_FIXUP);
1455 : : }
1456 : :
1457 : 13096104 : to_remove_edges.release ();
1458 : 13096104 : to_update_switch_stmts.release ();
1459 : 13096104 : }
1460 : :
1461 : : /* Simplify an integral conversion from an SSA name in STMT. */
1462 : :
1463 : : static bool
1464 : 4726794 : simplify_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
1465 : : {
1466 : 4726794 : tree innerop, middleop, finaltype;
1467 : 4726794 : gimple *def_stmt;
1468 : 4726794 : signop inner_sgn, middle_sgn, final_sgn;
1469 : 4726794 : unsigned inner_prec, middle_prec, final_prec;
1470 : 4726794 : widest_int innermin, innermed, innermax, middlemin, middlemed, middlemax;
1471 : :
1472 : 4726794 : finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
1473 : 4726794 : if (!INTEGRAL_TYPE_P (finaltype))
1474 : : return false;
1475 : 4355999 : middleop = gimple_assign_rhs1 (stmt);
1476 : 4355999 : def_stmt = SSA_NAME_DEF_STMT (middleop);
1477 : 4355999 : if (!is_gimple_assign (def_stmt)
1478 : 4355999 : || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
1479 : : return false;
1480 : 154756 : innerop = gimple_assign_rhs1 (def_stmt);
1481 : 154756 : if (TREE_CODE (innerop) != SSA_NAME
1482 : 154756 : || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
1483 : : return false;
1484 : :
1485 : : /* Get the value-range of the inner operand. Use global ranges in
1486 : : case innerop was created during substitute-and-fold. */
1487 : 151515 : wide_int imin, imax;
1488 : 151515 : int_range_max vr;
1489 : 151515 : if (!INTEGRAL_TYPE_P (TREE_TYPE (innerop)))
1490 : : return false;
1491 : 255812 : get_range_query (cfun)->range_of_expr (vr, innerop, stmt);
1492 : 127906 : if (vr.undefined_p () || vr.varying_p ())
1493 : : return false;
1494 : 73127 : innermin = widest_int::from (vr.lower_bound (), TYPE_SIGN (TREE_TYPE (innerop)));
1495 : 73127 : innermax = widest_int::from (vr.upper_bound (), TYPE_SIGN (TREE_TYPE (innerop)));
1496 : :
1497 : : /* Simulate the conversion chain to check if the result is equal if
1498 : : the middle conversion is removed. */
1499 : 73127 : inner_prec = TYPE_PRECISION (TREE_TYPE (innerop));
1500 : 73127 : middle_prec = TYPE_PRECISION (TREE_TYPE (middleop));
1501 : 73127 : final_prec = TYPE_PRECISION (finaltype);
1502 : :
1503 : : /* If the first conversion is not injective, the second must not
1504 : : be widening. */
1505 : 73127 : if (wi::gtu_p (innermax - innermin,
1506 : 146254 : wi::mask <widest_int> (middle_prec, false))
1507 : 73127 : && middle_prec < final_prec)
1508 : : return false;
1509 : : /* We also want a medium value so that we can track the effect that
1510 : : narrowing conversions with sign change have. */
1511 : 59493 : inner_sgn = TYPE_SIGN (TREE_TYPE (innerop));
1512 : 59493 : if (inner_sgn == UNSIGNED)
1513 : 45486 : innermed = wi::shifted_mask <widest_int> (1, inner_prec - 1, false);
1514 : : else
1515 : 14007 : innermed = 0;
1516 : 59493 : if (wi::cmp (innermin, innermed, inner_sgn) >= 0
1517 : 59493 : || wi::cmp (innermed, innermax, inner_sgn) >= 0)
1518 : 46745 : innermed = innermin;
1519 : :
1520 : 59493 : middle_sgn = TYPE_SIGN (TREE_TYPE (middleop));
1521 : 59493 : middlemin = wi::ext (innermin, middle_prec, middle_sgn);
1522 : 59493 : middlemed = wi::ext (innermed, middle_prec, middle_sgn);
1523 : 59493 : middlemax = wi::ext (innermax, middle_prec, middle_sgn);
1524 : :
1525 : : /* Require that the final conversion applied to both the original
1526 : : and the intermediate range produces the same result. */
1527 : 59493 : final_sgn = TYPE_SIGN (finaltype);
1528 : 118986 : if (wi::ext (middlemin, final_prec, final_sgn)
1529 : 118986 : != wi::ext (innermin, final_prec, final_sgn)
1530 : 113488 : || wi::ext (middlemed, final_prec, final_sgn)
1531 : 229725 : != wi::ext (innermed, final_prec, final_sgn)
1532 : 155557 : || wi::ext (middlemax, final_prec, final_sgn)
1533 : 203589 : != wi::ext (innermax, final_prec, final_sgn))
1534 : : return false;
1535 : :
1536 : 46870 : gimple_assign_set_rhs1 (stmt, innerop);
1537 : 46870 : fold_stmt (gsi, follow_single_use_edges);
1538 : 46870 : return true;
1539 : 4878309 : }
1540 : :
1541 : : /* Simplify a conversion from integral SSA name to float in STMT. */
1542 : :
1543 : : bool
1544 : 254565 : simplify_using_ranges::simplify_float_conversion_using_ranges
1545 : : (gimple_stmt_iterator *gsi,
1546 : : gimple *stmt)
1547 : : {
1548 : 254565 : tree rhs1 = gimple_assign_rhs1 (stmt);
1549 : 254565 : int_range_max vr;
1550 : 254565 : scalar_float_mode fltmode
1551 : 254565 : = SCALAR_FLOAT_TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt)));
1552 : 254565 : scalar_int_mode mode;
1553 : 254565 : tree tem;
1554 : 254565 : gassign *conv;
1555 : :
1556 : : /* We can only handle constant ranges. */
1557 : 254565 : if (!query->range_of_expr (vr, rhs1, stmt)
1558 : 254565 : || vr.varying_p ()
1559 : 354678 : || vr.undefined_p ())
1560 : : return false;
1561 : :
1562 : : /* The code below doesn't work for large/huge _BitInt, nor is really
1563 : : needed for those, bitint lowering does use ranges already. */
1564 : 99430 : if (TREE_CODE (TREE_TYPE (rhs1)) == BITINT_TYPE
1565 : 99430 : && TYPE_MODE (TREE_TYPE (rhs1)) == BLKmode)
1566 : : return false;
1567 : : /* First check if we can use a signed type in place of an unsigned. */
1568 : 99428 : scalar_int_mode rhs_mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (rhs1));
1569 : 99428 : if (TYPE_UNSIGNED (TREE_TYPE (rhs1))
1570 : 5572 : && can_float_p (fltmode, rhs_mode, 0) != CODE_FOR_nothing
1571 : 103248 : && range_fits_type_p (&vr, TYPE_PRECISION (TREE_TYPE (rhs1)), SIGNED))
1572 : : mode = rhs_mode;
1573 : : /* If we can do the conversion in the current input mode do nothing. */
1574 : 97966 : else if (can_float_p (fltmode, rhs_mode,
1575 : 97966 : TYPE_UNSIGNED (TREE_TYPE (rhs1))) != CODE_FOR_nothing)
1576 : : return false;
1577 : : /* Otherwise search for a mode we can use, starting from the narrowest
1578 : : integer mode available. */
1579 : : else
1580 : : {
1581 : 4395 : mode = NARROWEST_INT_MODE;
1582 : 15852 : for (;;)
1583 : : {
1584 : : /* If we cannot do a signed conversion to float from mode
1585 : : or if the value-range does not fit in the signed type
1586 : : try with a wider mode. */
1587 : 15852 : if (can_float_p (fltmode, mode, 0) != CODE_FOR_nothing
1588 : 15852 : && range_fits_type_p (&vr, GET_MODE_PRECISION (mode), SIGNED))
1589 : : break;
1590 : :
1591 : : /* But do not widen the input. Instead leave that to the
1592 : : optabs expansion code. */
1593 : 31444 : if (!GET_MODE_WIDER_MODE (mode).exists (&mode)
1594 : 15722 : || GET_MODE_PRECISION (mode) > TYPE_PRECISION (TREE_TYPE (rhs1)))
1595 : : return false;
1596 : : }
1597 : : }
1598 : :
1599 : : /* It works, insert a truncation or sign-change before the
1600 : : float conversion. */
1601 : 1592 : tem = make_ssa_name (build_nonstandard_integer_type
1602 : 1592 : (GET_MODE_PRECISION (mode), 0));
1603 : 1592 : conv = gimple_build_assign (tem, NOP_EXPR, rhs1);
1604 : 1592 : gsi_insert_before (gsi, conv, GSI_SAME_STMT);
1605 : 1592 : gimple_assign_set_rhs1 (stmt, tem);
1606 : 1592 : fold_stmt (gsi, follow_single_use_edges);
1607 : :
1608 : 1592 : return true;
1609 : 254565 : }
1610 : :
1611 : : /* Simplify an internal fn call using ranges if possible. */
1612 : :
1613 : : bool
1614 : 361846 : simplify_using_ranges::simplify_internal_call_using_ranges
1615 : : (gimple_stmt_iterator *gsi,
1616 : : gimple *stmt)
1617 : : {
1618 : 361846 : enum tree_code subcode;
1619 : 361846 : bool is_ubsan = false;
1620 : 361846 : bool ovf = false;
1621 : 361846 : switch (gimple_call_internal_fn (stmt))
1622 : : {
1623 : : case IFN_UBSAN_CHECK_ADD:
1624 : : subcode = PLUS_EXPR;
1625 : : is_ubsan = true;
1626 : : break;
1627 : 2455 : case IFN_UBSAN_CHECK_SUB:
1628 : 2455 : subcode = MINUS_EXPR;
1629 : 2455 : is_ubsan = true;
1630 : 2455 : break;
1631 : 2122 : case IFN_UBSAN_CHECK_MUL:
1632 : 2122 : subcode = MULT_EXPR;
1633 : 2122 : is_ubsan = true;
1634 : 2122 : break;
1635 : 41267 : case IFN_ADD_OVERFLOW:
1636 : 41267 : subcode = PLUS_EXPR;
1637 : 41267 : break;
1638 : 49613 : case IFN_SUB_OVERFLOW:
1639 : 49613 : subcode = MINUS_EXPR;
1640 : 49613 : break;
1641 : 47481 : case IFN_MUL_OVERFLOW:
1642 : 47481 : subcode = MULT_EXPR;
1643 : 47481 : break;
1644 : : default:
1645 : : return false;
1646 : : }
1647 : :
1648 : 145503 : tree op0 = gimple_call_arg (stmt, 0);
1649 : 145503 : tree op1 = gimple_call_arg (stmt, 1);
1650 : 145503 : tree type;
1651 : 145503 : if (is_ubsan)
1652 : : {
1653 : 7142 : type = TREE_TYPE (op0);
1654 : 7142 : if (VECTOR_TYPE_P (type))
1655 : : return false;
1656 : : }
1657 : 138361 : else if (gimple_call_lhs (stmt) == NULL_TREE)
1658 : : return false;
1659 : : else
1660 : 138361 : type = TREE_TYPE (TREE_TYPE (gimple_call_lhs (stmt)));
1661 : 144633 : if (!check_for_binary_op_overflow (query, subcode, type, op0, op1, &ovf, stmt)
1662 : 144633 : || (is_ubsan && ovf))
1663 : : return false;
1664 : :
1665 : 3460 : gimple *g;
1666 : 3460 : location_t loc = gimple_location (stmt);
1667 : 3460 : if (is_ubsan)
1668 : 568 : g = gimple_build_assign (gimple_call_lhs (stmt), subcode, op0, op1);
1669 : : else
1670 : : {
1671 : 2892 : tree utype = type;
1672 : 2892 : if (ovf
1673 : 1408 : || !useless_type_conversion_p (type, TREE_TYPE (op0))
1674 : 3581 : || !useless_type_conversion_p (type, TREE_TYPE (op1)))
1675 : 2487 : utype = unsigned_type_for (type);
1676 : 2892 : if (TREE_CODE (op0) == INTEGER_CST)
1677 : 1174 : op0 = fold_convert (utype, op0);
1678 : 1718 : else if (!useless_type_conversion_p (utype, TREE_TYPE (op0)))
1679 : : {
1680 : 719 : g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op0);
1681 : 719 : gimple_set_location (g, loc);
1682 : 719 : gsi_insert_before (gsi, g, GSI_SAME_STMT);
1683 : 719 : op0 = gimple_assign_lhs (g);
1684 : : }
1685 : 2892 : if (TREE_CODE (op1) == INTEGER_CST)
1686 : 1663 : op1 = fold_convert (utype, op1);
1687 : 1229 : else if (!useless_type_conversion_p (utype, TREE_TYPE (op1)))
1688 : : {
1689 : 21 : g = gimple_build_assign (make_ssa_name (utype), NOP_EXPR, op1);
1690 : 21 : gimple_set_location (g, loc);
1691 : 21 : gsi_insert_before (gsi, g, GSI_SAME_STMT);
1692 : 21 : op1 = gimple_assign_lhs (g);
1693 : : }
1694 : 2892 : g = gimple_build_assign (make_ssa_name (utype), subcode, op0, op1);
1695 : 2892 : gimple_set_location (g, loc);
1696 : 2892 : gsi_insert_before (gsi, g, GSI_SAME_STMT);
1697 : 2892 : if (utype != type)
1698 : : {
1699 : 1334 : g = gimple_build_assign (make_ssa_name (type), NOP_EXPR,
1700 : : gimple_assign_lhs (g));
1701 : 1334 : gimple_set_location (g, loc);
1702 : 1334 : gsi_insert_before (gsi, g, GSI_SAME_STMT);
1703 : : }
1704 : 2892 : g = gimple_build_assign (gimple_call_lhs (stmt), COMPLEX_EXPR,
1705 : : gimple_assign_lhs (g),
1706 : 2892 : build_int_cst (type, ovf));
1707 : : }
1708 : 3460 : gimple_set_location (g, loc);
1709 : 3460 : gsi_replace (gsi, g, false);
1710 : 3460 : return true;
1711 : : }
1712 : :
1713 : : /* Return true if VAR is a two-valued variable. Set a and b with the
1714 : : two-values when it is true. Return false otherwise. */
1715 : :
1716 : : bool
1717 : 516121 : simplify_using_ranges::two_valued_val_range_p (tree var, tree *a, tree *b,
1718 : : gimple *s)
1719 : : {
1720 : 516121 : int_range_max vr;
1721 : 516121 : if (!query->range_of_expr (vr, var, s))
1722 : : return false;
1723 : 516121 : if (vr.varying_p () || vr.undefined_p ())
1724 : : return false;
1725 : :
1726 : 811693 : if ((vr.num_pairs () == 1 && vr.upper_bound () - vr.lower_bound () == 1)
1727 : 419912 : || (vr.num_pairs () == 2
1728 : 289743 : && vr.lower_bound (0) == vr.upper_bound (0)
1729 : 246443 : && vr.lower_bound (1) == vr.upper_bound (1)))
1730 : : {
1731 : 6646 : *a = wide_int_to_tree (TREE_TYPE (var), vr.lower_bound ());
1732 : 6646 : *b = wide_int_to_tree (TREE_TYPE (var), vr.upper_bound ());
1733 : 6646 : return true;
1734 : : }
1735 : : return false;
1736 : 516121 : }
1737 : :
1738 : 13096104 : simplify_using_ranges::simplify_using_ranges (range_query *query,
1739 : 13096104 : int not_executable_flag)
1740 : 13096104 : : query (query)
1741 : : {
1742 : 13096104 : to_remove_edges = vNULL;
1743 : 13096104 : to_update_switch_stmts = vNULL;
1744 : 13096104 : m_not_executable_flag = not_executable_flag;
1745 : 13096104 : m_flag_set_edges = vNULL;
1746 : 13096104 : }
1747 : :
1748 : 13096104 : simplify_using_ranges::~simplify_using_ranges ()
1749 : : {
1750 : 13096104 : cleanup_edges_and_switches ();
1751 : 13096104 : m_flag_set_edges.release ();
1752 : 13096104 : }
1753 : :
1754 : : /* Simplify STMT using ranges if possible. */
1755 : :
1756 : : bool
1757 : 234974072 : simplify_using_ranges::simplify (gimple_stmt_iterator *gsi)
1758 : : {
1759 : 234974072 : gcc_checking_assert (query);
1760 : :
1761 : 234974072 : gimple *stmt = gsi_stmt (*gsi);
1762 : 234974072 : if (is_gimple_assign (stmt))
1763 : : {
1764 : 67641412 : enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
1765 : 67641412 : tree rhs1 = gimple_assign_rhs1 (stmt);
1766 : 67641412 : tree rhs2 = gimple_assign_rhs2 (stmt);
1767 : 67641412 : tree lhs = gimple_assign_lhs (stmt);
1768 : 67641412 : tree val1 = NULL_TREE, val2 = NULL_TREE;
1769 : 67641412 : use_operand_p use_p;
1770 : 67641412 : gimple *use_stmt;
1771 : :
1772 : : /* Convert:
1773 : : LHS = CST BINOP VAR
1774 : : Where VAR is two-valued and LHS is used in GIMPLE_COND only
1775 : : To:
1776 : : LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2)
1777 : :
1778 : : Also handles:
1779 : : LHS = VAR BINOP CST
1780 : : Where VAR is two-valued and LHS is used in GIMPLE_COND only
1781 : : To:
1782 : : LHS = VAR == VAL1 ? (VAL1 BINOP CST) : (VAL2 BINOP CST) */
1783 : :
1784 : 67641412 : if (TREE_CODE_CLASS (rhs_code) == tcc_binary
1785 : 14136997 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1786 : 10043088 : && ((TREE_CODE (rhs1) == INTEGER_CST
1787 : 178425 : && TREE_CODE (rhs2) == SSA_NAME)
1788 : 9865263 : || (TREE_CODE (rhs2) == INTEGER_CST
1789 : 6613736 : && TREE_CODE (rhs1) == SSA_NAME))
1790 : 6790961 : && single_imm_use (lhs, &use_p, &use_stmt)
1791 : 72867345 : && gimple_code (use_stmt) == GIMPLE_COND)
1792 : :
1793 : : {
1794 : 516121 : tree new_rhs1 = NULL_TREE;
1795 : 516121 : tree new_rhs2 = NULL_TREE;
1796 : 516121 : tree cmp_var = NULL_TREE;
1797 : :
1798 : 516121 : if (TREE_CODE (rhs2) == SSA_NAME
1799 : 516121 : && two_valued_val_range_p (rhs2, &val1, &val2, stmt))
1800 : : {
1801 : : /* Optimize RHS1 OP [VAL1, VAL2]. */
1802 : 188 : new_rhs1 = int_const_binop (rhs_code, rhs1, val1);
1803 : 188 : new_rhs2 = int_const_binop (rhs_code, rhs1, val2);
1804 : 188 : cmp_var = rhs2;
1805 : : }
1806 : 515933 : else if (TREE_CODE (rhs1) == SSA_NAME
1807 : 515933 : && two_valued_val_range_p (rhs1, &val1, &val2, stmt))
1808 : : {
1809 : : /* Optimize [VAL1, VAL2] OP RHS2. */
1810 : 6458 : new_rhs1 = int_const_binop (rhs_code, val1, rhs2);
1811 : 6458 : new_rhs2 = int_const_binop (rhs_code, val2, rhs2);
1812 : 6458 : cmp_var = rhs1;
1813 : : }
1814 : :
1815 : : /* If we could not find two-vals or the optimzation is invalid as
1816 : : in divide by zero, new_rhs1 / new_rhs will be NULL_TREE. */
1817 : 516121 : if (new_rhs1 && new_rhs2)
1818 : : {
1819 : 6646 : tree cond = gimple_build (gsi, true, GSI_SAME_STMT,
1820 : : UNKNOWN_LOCATION,
1821 : : EQ_EXPR, boolean_type_node,
1822 : : cmp_var, val1);
1823 : 6646 : gimple_assign_set_rhs_with_ops (gsi,
1824 : : COND_EXPR, cond,
1825 : : new_rhs1,
1826 : : new_rhs2);
1827 : 6646 : update_stmt (gsi_stmt (*gsi));
1828 : 6646 : fold_stmt (gsi, follow_single_use_edges);
1829 : 8118702 : return true;
1830 : : }
1831 : : }
1832 : :
1833 : 67634766 : if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
1834 : 1219804 : return simplify_compare_assign_using_ranges_1 (gsi, stmt);
1835 : :
1836 : 66414962 : switch (rhs_code)
1837 : : {
1838 : :
1839 : : /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
1840 : : and BIT_AND_EXPR respectively if the first operand is greater
1841 : : than zero and the second operand is an exact power of two.
1842 : : Also optimize TRUNC_MOD_EXPR away if the second operand is
1843 : : constant and the first operand already has the right value
1844 : : range. */
1845 : 324076 : case TRUNC_DIV_EXPR:
1846 : 324076 : case TRUNC_MOD_EXPR:
1847 : 324076 : if ((TREE_CODE (rhs1) == SSA_NAME
1848 : 324076 : || TREE_CODE (rhs1) == INTEGER_CST)
1849 : 324076 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
1850 : 322862 : return simplify_div_or_mod_using_ranges (gsi, stmt);
1851 : : break;
1852 : :
1853 : : /* Transform ABS (X) into X or -X as appropriate. */
1854 : 55186 : case ABS_EXPR:
1855 : 55186 : if (TREE_CODE (rhs1) == SSA_NAME
1856 : 55186 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
1857 : 6828 : return simplify_abs_using_ranges (gsi, stmt);
1858 : : break;
1859 : :
1860 : 1347350 : case BIT_AND_EXPR:
1861 : 1347350 : case BIT_IOR_EXPR:
1862 : : /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR if all the bits
1863 : : being cleared are already cleared or all the bits being set
1864 : : are already set. Beware that boolean types must be handled
1865 : : logically (see range-op.cc) unless they have precision 1. */
1866 : 2590202 : if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1867 : 2560708 : && (TREE_CODE (TREE_TYPE (rhs1)) != BOOLEAN_TYPE
1868 : 301396 : || TYPE_PRECISION (TREE_TYPE (rhs1)) == 1))
1869 : 1317856 : return simplify_bit_ops_using_ranges (gsi, stmt);
1870 : : break;
1871 : :
1872 : 5800477 : CASE_CONVERT:
1873 : 5800477 : if (TREE_CODE (rhs1) == SSA_NAME
1874 : 5800477 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
1875 : 4726794 : return simplify_conversion_using_ranges (gsi, stmt);
1876 : : break;
1877 : :
1878 : 256916 : case FLOAT_EXPR:
1879 : 256916 : if (TREE_CODE (rhs1) == SSA_NAME
1880 : 256916 : && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
1881 : 254565 : return simplify_float_conversion_using_ranges (gsi, stmt);
1882 : : break;
1883 : :
1884 : 179980 : case MIN_EXPR:
1885 : 179980 : case MAX_EXPR:
1886 : 179980 : return simplify_min_or_max_using_ranges (gsi, stmt);
1887 : :
1888 : 395125 : case RSHIFT_EXPR:
1889 : 395125 : {
1890 : 395125 : tree op0 = gimple_assign_rhs1 (stmt);
1891 : 395125 : tree type = TREE_TYPE (op0);
1892 : 395125 : int_range_max range;
1893 : 395125 : if (TYPE_SIGN (type) == SIGNED
1894 : 395125 : && query->range_of_expr (range, op0, stmt))
1895 : : {
1896 : 83367 : unsigned prec = TYPE_PRECISION (TREE_TYPE (op0));
1897 : 166734 : int_range<2> nzm1 (type, wi::minus_one (prec), wi::zero (prec),
1898 : 83367 : VR_ANTI_RANGE);
1899 : 83367 : range.intersect (nzm1);
1900 : : // If there are no ranges other than [-1, 0] remove the shift.
1901 : 83367 : if (range.undefined_p ())
1902 : : {
1903 : 57 : gimple_assign_set_rhs_from_tree (gsi, op0);
1904 : 57 : return true;
1905 : : }
1906 : : return false;
1907 : 83367 : }
1908 : 311758 : break;
1909 : 395125 : }
1910 : : default:
1911 : : break;
1912 : : }
1913 : : }
1914 : 167332660 : else if (gimple_code (stmt) == GIMPLE_COND)
1915 : 11994600 : return simplify_cond_using_ranges_1 (as_a <gcond *> (stmt));
1916 : 155338060 : else if (gimple_code (stmt) == GIMPLE_SWITCH)
1917 : 65999 : return simplify_switch_using_ranges (as_a <gswitch *> (stmt));
1918 : 155272061 : else if (is_gimple_call (stmt)
1919 : 155272061 : && gimple_call_internal_p (stmt))
1920 : 361846 : return simplify_internal_call_using_ranges (gsi, stmt);
1921 : :
1922 : : return false;
1923 : : }
|