Branch data Line data Source code
1 : : /* Support routines for Value Range Propagation (VRP).
2 : : Copyright (C) 2005-2025 Free Software Foundation, Inc.
3 : : Contributed by Diego Novillo <dnovillo@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify
8 : : it under the terms of the GNU General Public License as published by
9 : : the Free Software Foundation; either version 3, or (at your option)
10 : : any later version.
11 : :
12 : : GCC is distributed in the hope that it will be useful,
13 : : but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : GNU General Public License for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : #include "config.h"
22 : : #include "system.h"
23 : : #include "coretypes.h"
24 : : #include "basic-block.h"
25 : : #include "bitmap.h"
26 : : #include "sbitmap.h"
27 : : #include "options.h"
28 : : #include "dominance.h"
29 : : #include "function.h"
30 : : #include "cfg.h"
31 : : #include "tree.h"
32 : : #include "gimple.h"
33 : : #include "tree-pass.h"
34 : : #include "ssa.h"
35 : : #include "gimple-pretty-print.h"
36 : : #include "fold-const.h"
37 : : #include "cfganal.h"
38 : : #include "gimple-iterator.h"
39 : : #include "tree-cfg.h"
40 : : #include "tree-ssa-loop-manip.h"
41 : : #include "tree-ssa-loop-niter.h"
42 : : #include "tree-into-ssa.h"
43 : : #include "cfgloop.h"
44 : : #include "tree-scalar-evolution.h"
45 : : #include "tree-ssa-propagate.h"
46 : : #include "domwalk.h"
47 : : #include "vr-values.h"
48 : : #include "gimple-array-bounds.h"
49 : : #include "gimple-range.h"
50 : : #include "gimple-range-path.h"
51 : : #include "value-pointer-equiv.h"
52 : : #include "gimple-fold.h"
53 : : #include "tree-dfa.h"
54 : : #include "tree-ssa-dce.h"
55 : : #include "alloc-pool.h"
56 : : #include "cgraph.h"
57 : : #include "symbol-summary.h"
58 : : #include "ipa-utils.h"
59 : : #include "sreal.h"
60 : : #include "ipa-cp.h"
61 : : #include "ipa-prop.h"
62 : : #include "attribs.h"
63 : : #include "diagnostic-core.h"
64 : :
65 : : // This class is utilized by VRP and ranger to remove __builtin_unreachable
66 : : // calls, and reflect any resulting global ranges.
67 : : //
68 : : // maybe_register() is called on condition statements , and if that
69 : : // matches the pattern of one branch being a builtin_unreachable, either check
70 : : // for early removal or register the resulting executable edge in a list.
71 : : //
72 : : // During early/non-final processing, we check to see if ALL exports from the
73 : : // block can be safely updated with a new global value. If they can, then
74 : : // we rewrite the condition and update those values immediately. Otherwise
75 : : // the unreachable condition is left in the IL until the final pass.
76 : : //
77 : : // During final processing, after all blocks have been registered,
78 : : // remove_and_update_globals() will
79 : : // - check all exports from registered blocks
80 : : // - ensure the cache entry of each export is set with the appropriate range
81 : : // - rewrite the conditions to take the executable edge
82 : : // - perform DCE on any feeding instructions to those rewritten conditions
83 : : //
84 : : // Then each of the immediate use chain of each export is walked, and a new
85 : : // global range created by unioning the ranges at all remaining use locations.
86 : :
87 : : class remove_unreachable {
88 : : public:
89 : 4005389 : remove_unreachable (range_query &r, bool all) : m_ranger (r), final_p (all)
90 : 8010778 : { m_list.create (30); }
91 : 8010774 : ~remove_unreachable () { m_list.release (); }
92 : : void handle_early (gimple *s, edge e);
93 : : void maybe_register (gimple *s);
94 : : bool remove ();
95 : : bool remove_and_update_globals ();
96 : : vec<std::pair<int, int> > m_list;
97 : : range_query &m_ranger;
98 : : bool final_p;
99 : : };
100 : :
101 : : // Check if block BB has a __builtin_unreachable () call on one arm, and
102 : : // register the executable edge if so.
103 : :
104 : : void
105 : 7752015 : remove_unreachable::maybe_register (gimple *s)
106 : : {
107 : 7752015 : gcc_checking_assert (gimple_code (s) == GIMPLE_COND);
108 : 7752015 : basic_block bb = gimple_bb (s);
109 : :
110 : 7752015 : edge e0 = EDGE_SUCC (bb, 0);
111 : 7752015 : basic_block bb0 = e0->dest;
112 : 8911461 : bool un0 = EDGE_COUNT (bb0->succs) == 0
113 : 8911461 : && gimple_seq_unreachable_p (bb_seq (bb0));
114 : 7752015 : edge e1 = EDGE_SUCC (bb, 1);
115 : 7752015 : basic_block bb1 = e1->dest;
116 : 7955633 : bool un1 = EDGE_COUNT (bb1->succs) == 0
117 : 7955633 : && gimple_seq_unreachable_p (bb_seq (bb1));
118 : :
119 : : // If the 2 blocks are not different, ignore.
120 : 7752015 : if (un0 == un1)
121 : : return;
122 : :
123 : : // Constant expressions are ignored.
124 : 277928 : if (TREE_CODE (gimple_cond_lhs (s)) != SSA_NAME
125 : 277928 : && TREE_CODE (gimple_cond_rhs (s)) != SSA_NAME)
126 : : return;
127 : :
128 : 277840 : edge e = un0 ? e1 : e0;
129 : :
130 : 277840 : if (!final_p)
131 : 183605 : handle_early (s, e);
132 : : else
133 : 94235 : m_list.safe_push (std::make_pair (e->src->index, e->dest->index));
134 : : }
135 : :
136 : : // Return true if all uses of NAME are dominated by block BB. 1 use
137 : : // is allowed in block BB, This is one we hope to remove.
138 : : // ie
139 : : // _2 = _1 & 7;
140 : : // if (_2 != 0)
141 : : // goto <bb 3>; [0.00%]
142 : : // Any additional use of _1 or _2 in this block invalidates early replacement.
143 : :
144 : : static bool
145 : 184605 : fully_replaceable (tree name, basic_block bb)
146 : : {
147 : 184605 : use_operand_p use_p;
148 : 184605 : imm_use_iterator iter;
149 : 184605 : bool saw_in_bb = false;
150 : :
151 : : // If a name loads from memory, we may lose information used in
152 : : // commoning opportunities later. See tree-ssa/ssa-pre-34.c.
153 : 184605 : gimple *def_stmt = SSA_NAME_DEF_STMT (name);
154 : 367501 : if (gimple_vuse (def_stmt))
155 : : return false;
156 : :
157 : 16752 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
158 : : {
159 : 13213 : gimple *use_stmt = USE_STMT (use_p);
160 : : // Ignore debug stmts and the branch.
161 : 13213 : if (is_gimple_debug (use_stmt))
162 : 3258 : continue;
163 : 9955 : basic_block use_bb = gimple_bb (use_stmt);
164 : : // Only one use in the block allowed to avoid complicated cases.
165 : 9955 : if (use_bb == bb)
166 : : {
167 : 4825 : if (saw_in_bb)
168 : : return false;
169 : : else
170 : : saw_in_bb = true;
171 : : }
172 : 5130 : else if (!dominated_by_p (CDI_DOMINATORS, use_bb, bb))
173 : : return false;
174 : : }
175 : : return true;
176 : : }
177 : :
178 : : // This routine is called to check builtin_unreachable calls during any
179 : : // time before final removal. The only way we can be sure it does not
180 : : // provide any additional information is to expect that we can update the
181 : : // global values of all exports from a block. This means the branch
182 : : // to the unreachable call must dominate all uses of those ssa-names, with
183 : : // the exception that there can be a single use in the block containing
184 : : // the branch. IF the name used in the branch is defined in the block, it may
185 : : // contain the name of something else that will be an export. And likewise
186 : : // that may also use another name that is an export etc.
187 : : //
188 : : // As long as there is only a single use, we can be sure that there are no other
189 : : // side effects (like being passed to a call, or stored to a global, etc.
190 : : // This means we will miss cases where there are 2 or more uses that have
191 : : // no interveneing statements that may had side effects, but it catches most
192 : : // of the caes we care about, and prevents expensive in depth analysis.
193 : : //
194 : : // Ranger will still reflect the proper ranges at other places in these missed
195 : : // cases, we simply will not remove/set globals early.
196 : :
197 : : void
198 : 183605 : remove_unreachable::handle_early (gimple *s, edge e)
199 : : {
200 : : // If there is no gori_ssa, there is no early processsing.
201 : 183605 : if (!m_ranger.gori_ssa ())
202 : : return ;
203 : 183605 : bool lhs_p = TREE_CODE (gimple_cond_lhs (s)) == SSA_NAME;
204 : 183605 : bool rhs_p = TREE_CODE (gimple_cond_rhs (s)) == SSA_NAME;
205 : : // Do not remove __builtin_unreachable if it confers a relation, or
206 : : // that relation may be lost in subsequent passes.
207 : 183605 : if (lhs_p && rhs_p)
208 : : return;
209 : : // Do not remove addresses early. ie if (x == &y)
210 : 182147 : if (lhs_p && TREE_CODE (gimple_cond_rhs (s)) == ADDR_EXPR)
211 : : return;
212 : :
213 : 182146 : gcc_checking_assert (gimple_outgoing_range_stmt_p (e->src) == s);
214 : 182146 : gcc_checking_assert (!final_p);
215 : :
216 : : // Check if every export use is dominated by this branch.
217 : 182146 : tree name;
218 : 185685 : FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori_ssa (), e->src, name)
219 : : {
220 : 184605 : if (!fully_replaceable (name, e->src))
221 : 181066 : return;
222 : : }
223 : :
224 : : // Set the global value for each.
225 : 2505 : FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori_ssa (), e->src, name)
226 : : {
227 : 1425 : value_range r (TREE_TYPE (name));
228 : 1425 : m_ranger.range_on_entry (r, e->dest, name);
229 : : // Nothing at this late stage we can do if the write fails.
230 : 1425 : if (!set_range_info (name, r))
231 : 191 : continue;
232 : 1425 : }
233 : :
234 : 1080 : tree ssa = lhs_p ? gimple_cond_lhs (s) : gimple_cond_rhs (s);
235 : :
236 : : // Rewrite the condition.
237 : 1080 : if (e->flags & EDGE_TRUE_VALUE)
238 : 295 : gimple_cond_make_true (as_a<gcond *> (s));
239 : : else
240 : 785 : gimple_cond_make_false (as_a<gcond *> (s));
241 : 1080 : update_stmt (s);
242 : :
243 : : // If the name on S is defined in this block, see if there is DCE work to do.
244 : 1080 : if (gimple_bb (SSA_NAME_DEF_STMT (ssa)) == e->src)
245 : : {
246 : 364 : auto_bitmap dce;
247 : 364 : bitmap_set_bit (dce, SSA_NAME_VERSION (ssa));
248 : 364 : simple_dce_from_worklist (dce);
249 : 364 : }
250 : : }
251 : :
252 : : // Process the edges in the list, change the conditions and removing any
253 : : // dead code feeding those conditions. This removes the unreachables, but
254 : : // makes no attempt to set globals values.
255 : :
256 : : bool
257 : 2 : remove_unreachable::remove ()
258 : : {
259 : 2 : if (!final_p || m_list.length () == 0)
260 : : return false;
261 : :
262 : : bool change = false;
263 : : unsigned i;
264 : 0 : for (i = 0; i < m_list.length (); i++)
265 : : {
266 : 0 : auto eb = m_list[i];
267 : 0 : basic_block src = BASIC_BLOCK_FOR_FN (cfun, eb.first);
268 : 0 : basic_block dest = BASIC_BLOCK_FOR_FN (cfun, eb.second);
269 : 0 : if (!src || !dest)
270 : 0 : continue;
271 : 0 : edge e = find_edge (src, dest);
272 : 0 : gimple *s = gimple_outgoing_range_stmt_p (e->src);
273 : 0 : gcc_checking_assert (gimple_code (s) == GIMPLE_COND);
274 : :
275 : 0 : tree name = gimple_range_ssa_p (gimple_cond_lhs (s));
276 : 0 : if (!name)
277 : 0 : name = gimple_range_ssa_p (gimple_cond_rhs (s));
278 : : // Check if global value can be set for NAME.
279 : 0 : if (name && fully_replaceable (name, src))
280 : : {
281 : 0 : value_range r (TREE_TYPE (name));
282 : 0 : if (gori_name_on_edge (r, name, e, &m_ranger))
283 : 0 : set_range_info (name, r);
284 : 0 : }
285 : :
286 : 0 : change = true;
287 : : // Rewrite the condition.
288 : 0 : if (e->flags & EDGE_TRUE_VALUE)
289 : 0 : gimple_cond_make_true (as_a<gcond *> (s));
290 : : else
291 : 0 : gimple_cond_make_false (as_a<gcond *> (s));
292 : 0 : update_stmt (s);
293 : : }
294 : :
295 : : return change;
296 : : }
297 : :
298 : :
299 : : // Process the edges in the list, change the conditions and removing any
300 : : // dead code feeding those conditions. Calculate the range of any
301 : : // names that may have been exported from those blocks, and determine if
302 : : // there is any updates to their global ranges..
303 : : // Return true if any builtin_unreachables/globals eliminated/updated.
304 : :
305 : : bool
306 : 4005387 : remove_unreachable::remove_and_update_globals ()
307 : : {
308 : 4005387 : if (m_list.length () == 0)
309 : : return false;
310 : :
311 : : // If there is no import/export info, Do basic removal.
312 : 24643 : if (!m_ranger.gori_ssa ())
313 : 0 : return remove ();
314 : :
315 : 24643 : bool change = false;
316 : 24643 : tree name;
317 : 24643 : unsigned i;
318 : 24643 : bitmap_iterator bi;
319 : 24643 : auto_bitmap all_exports;
320 : 118878 : for (i = 0; i < m_list.length (); i++)
321 : : {
322 : 94235 : auto eb = m_list[i];
323 : 94235 : basic_block src = BASIC_BLOCK_FOR_FN (cfun, eb.first);
324 : 94235 : basic_block dest = BASIC_BLOCK_FOR_FN (cfun, eb.second);
325 : 94235 : if (!src || !dest)
326 : 94235 : continue;
327 : 94235 : edge e = find_edge (src, dest);
328 : 94235 : gimple *s = gimple_outgoing_range_stmt_p (e->src);
329 : 94235 : gcc_checking_assert (gimple_code (s) == GIMPLE_COND);
330 : :
331 : 94235 : bool dominate_exit_p = true;
332 : 215549 : FOR_EACH_GORI_EXPORT_NAME (m_ranger.gori_ssa (), e->src, name)
333 : : {
334 : : // Ensure the cache is set for NAME in the succ block.
335 : 121314 : value_range r(TREE_TYPE (name));
336 : 121314 : value_range ex(TREE_TYPE (name));
337 : 121314 : m_ranger.range_on_entry (r, e->dest, name);
338 : 121314 : m_ranger.range_on_entry (ex, EXIT_BLOCK_PTR_FOR_FN (cfun), name);
339 : : // If the range produced by this __builtin_unreachacble expression
340 : : // is not fully reflected in the range at exit, then it does not
341 : : // dominate the exit of the function.
342 : 121314 : if (ex.intersect (r))
343 : 21297 : dominate_exit_p = false;
344 : 121314 : }
345 : :
346 : : // If the exit is dominated, add to the export list. Otherwise if this
347 : : // isn't the final VRP pass, leave the call in the IL.
348 : 94235 : if (dominate_exit_p)
349 : 75500 : bitmap_ior_into (all_exports,
350 : 75500 : m_ranger.gori_ssa ()->exports (e->src));
351 : 18735 : else if (!final_p)
352 : 0 : continue;
353 : :
354 : 94235 : change = true;
355 : : // Rewrite the condition.
356 : 94235 : if (e->flags & EDGE_TRUE_VALUE)
357 : 2080 : gimple_cond_make_true (as_a<gcond *> (s));
358 : : else
359 : 92155 : gimple_cond_make_false (as_a<gcond *> (s));
360 : 94235 : update_stmt (s);
361 : : }
362 : :
363 : 24643 : if (bitmap_empty_p (all_exports))
364 : : return false;
365 : : // Invoke DCE on all exported names to eliminate dead feeding defs.
366 : 21317 : auto_bitmap dce;
367 : 21317 : bitmap_copy (dce, all_exports);
368 : : // Don't attempt to DCE parameters.
369 : 111186 : EXECUTE_IF_SET_IN_BITMAP (all_exports, 0, i, bi)
370 : 89869 : if (!ssa_name (i) || SSA_NAME_IS_DEFAULT_DEF (ssa_name (i)))
371 : 753 : bitmap_clear_bit (dce, i);
372 : 21317 : simple_dce_from_worklist (dce);
373 : :
374 : : // Loop over all uses of each name and find maximal range. This is the
375 : : // new global range.
376 : 21317 : use_operand_p use_p;
377 : 21317 : imm_use_iterator iter;
378 : 111186 : EXECUTE_IF_SET_IN_BITMAP (all_exports, 0, i, bi)
379 : : {
380 : 89869 : name = ssa_name (i);
381 : 122835 : if (!name || SSA_NAME_IN_FREE_LIST (name))
382 : 89448 : continue;
383 : 32966 : value_range r (TREE_TYPE (name));
384 : 32966 : value_range exp_range (TREE_TYPE (name));
385 : 32966 : r.set_undefined ();
386 : 93896 : FOR_EACH_IMM_USE_FAST (use_p, iter, name)
387 : : {
388 : 83429 : gimple *use_stmt = USE_STMT (use_p);
389 : 83429 : if (is_gimple_debug (use_stmt))
390 : 26354 : continue;
391 : 57075 : if (!m_ranger.range_of_expr (exp_range, name, use_stmt))
392 : 0 : exp_range.set_varying (TREE_TYPE (name));
393 : 57075 : r.union_ (exp_range);
394 : 57075 : if (r.varying_p ())
395 : : break;
396 : : }
397 : : // Include the on-exit range to ensure non-dominated unreachables
398 : : // don't incorrectly impact the global range.
399 : 32966 : m_ranger.range_on_entry (exp_range, EXIT_BLOCK_PTR_FOR_FN (cfun), name);
400 : 32966 : r.union_ (exp_range);
401 : 32966 : if (r.varying_p () || r.undefined_p ())
402 : 22531 : continue;
403 : 10435 : if (!set_range_info (name, r))
404 : 10014 : continue;
405 : 421 : change = true;
406 : 32966 : }
407 : 21317 : return change;
408 : 45960 : }
409 : :
410 : : /* VR_TYPE describes a range with minimum value *MIN and maximum
411 : : value *MAX. Restrict the range to the set of values that have
412 : : no bits set outside NONZERO_BITS. Update *MIN and *MAX and
413 : : return the new range type.
414 : :
415 : : SGN gives the sign of the values described by the range. */
416 : :
417 : : enum value_range_kind
418 : 15327492 : intersect_range_with_nonzero_bits (enum value_range_kind vr_type,
419 : : wide_int *min, wide_int *max,
420 : : const wide_int &nonzero_bits,
421 : : signop sgn)
422 : : {
423 : 15327492 : if (vr_type == VR_ANTI_RANGE)
424 : : {
425 : : /* The VR_ANTI_RANGE is equivalent to the union of the ranges
426 : : A: [-INF, *MIN) and B: (*MAX, +INF]. First use NONZERO_BITS
427 : : to create an inclusive upper bound for A and an inclusive lower
428 : : bound for B. */
429 : 695903 : wide_int a_max = wi::round_down_for_mask (*min - 1, nonzero_bits);
430 : 695903 : wide_int b_min = wi::round_up_for_mask (*max + 1, nonzero_bits);
431 : :
432 : : /* If the calculation of A_MAX wrapped, A is effectively empty
433 : : and A_MAX is the highest value that satisfies NONZERO_BITS.
434 : : Likewise if the calculation of B_MIN wrapped, B is effectively
435 : : empty and B_MIN is the lowest value that satisfies NONZERO_BITS. */
436 : 695903 : bool a_empty = wi::ge_p (a_max, *min, sgn);
437 : 695903 : bool b_empty = wi::le_p (b_min, *max, sgn);
438 : :
439 : : /* If both A and B are empty, there are no valid values. */
440 : 695903 : if (a_empty && b_empty)
441 : : return VR_UNDEFINED;
442 : :
443 : : /* If exactly one of A or B is empty, return a VR_RANGE for the
444 : : other one. */
445 : 695903 : if (a_empty || b_empty)
446 : : {
447 : 813 : *min = b_min;
448 : 813 : *max = a_max;
449 : 813 : gcc_checking_assert (wi::le_p (*min, *max, sgn));
450 : : return VR_RANGE;
451 : : }
452 : :
453 : : /* Update the VR_ANTI_RANGE bounds. */
454 : 695090 : *min = a_max + 1;
455 : 695090 : *max = b_min - 1;
456 : 695090 : gcc_checking_assert (wi::le_p (*min, *max, sgn));
457 : :
458 : : /* Now check whether the excluded range includes any values that
459 : : satisfy NONZERO_BITS. If not, switch to a full VR_RANGE. */
460 : 695090 : if (wi::round_up_for_mask (*min, nonzero_bits) == b_min)
461 : : {
462 : 240381 : unsigned int precision = min->get_precision ();
463 : 240381 : *min = wi::min_value (precision, sgn);
464 : 240381 : *max = wi::max_value (precision, sgn);
465 : 240381 : vr_type = VR_RANGE;
466 : : }
467 : 695903 : }
468 : 15326679 : if (vr_type == VR_RANGE || vr_type == VR_VARYING)
469 : : {
470 : 14871970 : *max = wi::round_down_for_mask (*max, nonzero_bits);
471 : :
472 : : /* Check that the range contains at least one valid value. */
473 : 14871970 : if (wi::gt_p (*min, *max, sgn))
474 : : return VR_UNDEFINED;
475 : :
476 : 14871970 : *min = wi::round_up_for_mask (*min, nonzero_bits);
477 : 14871970 : gcc_checking_assert (wi::le_p (*min, *max, sgn));
478 : : }
479 : : return vr_type;
480 : : }
481 : :
482 : : /* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE
483 : : otherwise. We only handle additive operations and set NEG to true if the
484 : : symbol is negated and INV to the invariant part, if any. */
485 : :
486 : : static tree
487 : 4284260 : get_single_symbol (tree t, bool *neg, tree *inv)
488 : : {
489 : 4284260 : bool neg_;
490 : 4284260 : tree inv_;
491 : :
492 : 4284260 : *inv = NULL_TREE;
493 : 4284260 : *neg = false;
494 : :
495 : 4284260 : if (TREE_CODE (t) == PLUS_EXPR
496 : 4284260 : || TREE_CODE (t) == POINTER_PLUS_EXPR
497 : 4284260 : || TREE_CODE (t) == MINUS_EXPR)
498 : : {
499 : 0 : if (is_gimple_min_invariant (TREE_OPERAND (t, 0)))
500 : : {
501 : 0 : neg_ = (TREE_CODE (t) == MINUS_EXPR);
502 : 0 : inv_ = TREE_OPERAND (t, 0);
503 : 0 : t = TREE_OPERAND (t, 1);
504 : : }
505 : 0 : else if (is_gimple_min_invariant (TREE_OPERAND (t, 1)))
506 : : {
507 : 0 : neg_ = false;
508 : 0 : inv_ = TREE_OPERAND (t, 1);
509 : 0 : t = TREE_OPERAND (t, 0);
510 : : }
511 : : else
512 : : return NULL_TREE;
513 : : }
514 : : else
515 : : {
516 : : neg_ = false;
517 : : inv_ = NULL_TREE;
518 : : }
519 : :
520 : 4284260 : if (TREE_CODE (t) == NEGATE_EXPR)
521 : : {
522 : 0 : t = TREE_OPERAND (t, 0);
523 : 0 : neg_ = !neg_;
524 : : }
525 : :
526 : 4284260 : if (TREE_CODE (t) != SSA_NAME)
527 : : return NULL_TREE;
528 : :
529 : 0 : if (inv_ && TREE_OVERFLOW_P (inv_))
530 : 0 : inv_ = drop_tree_overflow (inv_);
531 : :
532 : 0 : *neg = neg_;
533 : 0 : *inv = inv_;
534 : 0 : return t;
535 : : }
536 : :
537 : : /* Compare two values VAL1 and VAL2. Return
538 : :
539 : : -2 if VAL1 and VAL2 cannot be compared at compile-time,
540 : : -1 if VAL1 < VAL2,
541 : : 0 if VAL1 == VAL2,
542 : : +1 if VAL1 > VAL2, and
543 : : +2 if VAL1 != VAL2
544 : :
545 : : This is similar to tree_int_cst_compare but supports pointer values
546 : : and values that cannot be compared at compile time.
547 : :
548 : : If STRICT_OVERFLOW_P is not NULL, then set *STRICT_OVERFLOW_P to
549 : : true if the return value is only valid if we assume that signed
550 : : overflow is undefined. */
551 : :
552 : : int
553 : 2471496 : compare_values_warnv (tree val1, tree val2, bool *strict_overflow_p)
554 : : {
555 : 2471496 : if (val1 == val2)
556 : : return 0;
557 : :
558 : : /* Below we rely on the fact that VAL1 and VAL2 are both pointers or
559 : : both integers. */
560 : 2142130 : gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
561 : : == POINTER_TYPE_P (TREE_TYPE (val2)));
562 : :
563 : : /* Convert the two values into the same type. This is needed because
564 : : sizetype causes sign extension even for unsigned types. */
565 : 2142130 : if (!useless_type_conversion_p (TREE_TYPE (val1), TREE_TYPE (val2)))
566 : 0 : val2 = fold_convert (TREE_TYPE (val1), val2);
567 : :
568 : 2142130 : const bool overflow_undefined
569 : 4279675 : = INTEGRAL_TYPE_P (TREE_TYPE (val1))
570 : 4279675 : && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1));
571 : 2142130 : tree inv1, inv2;
572 : 2142130 : bool neg1, neg2;
573 : 2142130 : tree sym1 = get_single_symbol (val1, &neg1, &inv1);
574 : 2142130 : tree sym2 = get_single_symbol (val2, &neg2, &inv2);
575 : :
576 : : /* If VAL1 and VAL2 are of the form '[-]NAME [+ CST]', return -1 or +1
577 : : accordingly. If VAL1 and VAL2 don't use the same name, return -2. */
578 : 2142130 : if (sym1 && sym2)
579 : : {
580 : : /* Both values must use the same name with the same sign. */
581 : 0 : if (sym1 != sym2 || neg1 != neg2)
582 : : return -2;
583 : :
584 : : /* [-]NAME + CST == [-]NAME + CST. */
585 : 0 : if (inv1 == inv2)
586 : : return 0;
587 : :
588 : : /* If overflow is defined we cannot simplify more. */
589 : 0 : if (!overflow_undefined)
590 : : return -2;
591 : :
592 : 0 : if (strict_overflow_p != NULL
593 : : /* Symbolic range building sets the no-warning bit to declare
594 : : that overflow doesn't happen. */
595 : 0 : && (!inv1 || !warning_suppressed_p (val1, OPT_Woverflow))
596 : 0 : && (!inv2 || !warning_suppressed_p (val2, OPT_Woverflow)))
597 : 0 : *strict_overflow_p = true;
598 : :
599 : 0 : if (!inv1)
600 : 0 : inv1 = build_int_cst (TREE_TYPE (val1), 0);
601 : 0 : if (!inv2)
602 : 0 : inv2 = build_int_cst (TREE_TYPE (val2), 0);
603 : :
604 : 0 : return wi::cmp (wi::to_wide (inv1), wi::to_wide (inv2),
605 : 0 : TYPE_SIGN (TREE_TYPE (val1)));
606 : : }
607 : :
608 : 2142130 : const bool cst1 = is_gimple_min_invariant (val1);
609 : 2142130 : const bool cst2 = is_gimple_min_invariant (val2);
610 : :
611 : : /* If one is of the form '[-]NAME + CST' and the other is constant, then
612 : : it might be possible to say something depending on the constants. */
613 : 2142130 : if ((sym1 && inv1 && cst2) || (sym2 && inv2 && cst1))
614 : : {
615 : 0 : if (!overflow_undefined)
616 : : return -2;
617 : :
618 : 0 : if (strict_overflow_p != NULL
619 : : /* Symbolic range building sets the no-warning bit to declare
620 : : that overflow doesn't happen. */
621 : 0 : && (!sym1 || !warning_suppressed_p (val1, OPT_Woverflow))
622 : 0 : && (!sym2 || !warning_suppressed_p (val2, OPT_Woverflow)))
623 : 0 : *strict_overflow_p = true;
624 : :
625 : 0 : const signop sgn = TYPE_SIGN (TREE_TYPE (val1));
626 : 0 : tree cst = cst1 ? val1 : val2;
627 : 0 : tree inv = cst1 ? inv2 : inv1;
628 : :
629 : : /* Compute the difference between the constants. If it overflows or
630 : : underflows, this means that we can trivially compare the NAME with
631 : : it and, consequently, the two values with each other. */
632 : 0 : wide_int diff = wi::to_wide (cst) - wi::to_wide (inv);
633 : 0 : if (wi::cmp (0, wi::to_wide (inv), sgn)
634 : 0 : != wi::cmp (diff, wi::to_wide (cst), sgn))
635 : : {
636 : 0 : const int res = wi::cmp (wi::to_wide (cst), wi::to_wide (inv), sgn);
637 : 0 : return cst1 ? res : -res;
638 : : }
639 : :
640 : : return -2;
641 : 0 : }
642 : :
643 : : /* We cannot say anything more for non-constants. */
644 : 2142130 : if (!cst1 || !cst2)
645 : : return -2;
646 : :
647 : 2142130 : if (!POINTER_TYPE_P (TREE_TYPE (val1)))
648 : : {
649 : : /* We cannot compare overflowed values. */
650 : 2142130 : if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
651 : : return -2;
652 : :
653 : 2142130 : if (TREE_CODE (val1) == INTEGER_CST
654 : 2142130 : && TREE_CODE (val2) == INTEGER_CST)
655 : 2142130 : return tree_int_cst_compare (val1, val2);
656 : :
657 : 0 : if (poly_int_tree_p (val1) && poly_int_tree_p (val2))
658 : : {
659 : 0 : if (known_eq (wi::to_poly_widest (val1),
660 : : wi::to_poly_widest (val2)))
661 : : return 0;
662 : 0 : if (known_lt (wi::to_poly_widest (val1),
663 : : wi::to_poly_widest (val2)))
664 : : return -1;
665 : 0 : if (known_gt (wi::to_poly_widest (val1),
666 : : wi::to_poly_widest (val2)))
667 : : return 1;
668 : : }
669 : :
670 : 0 : return -2;
671 : : }
672 : : else
673 : : {
674 : 0 : if (TREE_CODE (val1) == INTEGER_CST && TREE_CODE (val2) == INTEGER_CST)
675 : : {
676 : : /* We cannot compare overflowed values. */
677 : 0 : if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
678 : : return -2;
679 : :
680 : 0 : return tree_int_cst_compare (val1, val2);
681 : : }
682 : :
683 : : /* First see if VAL1 and VAL2 are not the same. */
684 : 0 : if (operand_equal_p (val1, val2, 0))
685 : : return 0;
686 : :
687 : 0 : fold_defer_overflow_warnings ();
688 : :
689 : : /* If VAL1 is a lower address than VAL2, return -1. */
690 : 0 : tree t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val1, val2);
691 : 0 : if (t && integer_onep (t))
692 : : {
693 : 0 : fold_undefer_and_ignore_overflow_warnings ();
694 : 0 : return -1;
695 : : }
696 : :
697 : : /* If VAL1 is a higher address than VAL2, return +1. */
698 : 0 : t = fold_binary_to_constant (LT_EXPR, boolean_type_node, val2, val1);
699 : 0 : if (t && integer_onep (t))
700 : : {
701 : 0 : fold_undefer_and_ignore_overflow_warnings ();
702 : 0 : return 1;
703 : : }
704 : :
705 : : /* If VAL1 is different than VAL2, return +2. */
706 : 0 : t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2);
707 : 0 : fold_undefer_and_ignore_overflow_warnings ();
708 : 0 : if (t && integer_onep (t))
709 : : return 2;
710 : :
711 : 0 : return -2;
712 : : }
713 : : }
714 : :
715 : : /* Compare values like compare_values_warnv. */
716 : :
717 : : int
718 : 2471496 : compare_values (tree val1, tree val2)
719 : : {
720 : 2471496 : bool sop;
721 : 2471496 : return compare_values_warnv (val1, val2, &sop);
722 : : }
723 : :
724 : : /* Helper for overflow_comparison_p
725 : :
726 : : OP0 CODE OP1 is a comparison. Examine the comparison and potentially
727 : : OP1's defining statement to see if it ultimately has the form
728 : : OP0 CODE (OP0 PLUS INTEGER_CST)
729 : :
730 : : If so, return TRUE indicating this is an overflow test and store into
731 : : *NEW_CST an updated constant that can be used in a narrowed range test.
732 : :
733 : : REVERSED indicates if the comparison was originally:
734 : :
735 : : OP1 CODE' OP0.
736 : :
737 : : This affects how we build the updated constant. */
738 : :
739 : : static bool
740 : 36403383 : overflow_comparison_p_1 (enum tree_code code, tree op0, tree op1,
741 : : bool reversed, tree *new_cst)
742 : : {
743 : : /* See if this is a relational operation between two SSA_NAMES with
744 : : unsigned, overflow wrapping values. If so, check it more deeply. */
745 : 36403383 : if ((code == LT_EXPR || code == LE_EXPR
746 : 31090366 : || code == GE_EXPR || code == GT_EXPR)
747 : 8346121 : && TREE_CODE (op0) == SSA_NAME
748 : 5884562 : && TREE_CODE (op1) == SSA_NAME
749 : 3423149 : && INTEGRAL_TYPE_P (TREE_TYPE (op0))
750 : 3164739 : && TYPE_UNSIGNED (TREE_TYPE (op0))
751 : 37628472 : && TYPE_OVERFLOW_WRAPS (TREE_TYPE (op0)))
752 : : {
753 : 1225089 : gimple *op1_def = SSA_NAME_DEF_STMT (op1);
754 : :
755 : : /* Now look at the defining statement of OP1 to see if it adds
756 : : or subtracts a nonzero constant from another operand. */
757 : 1225089 : if (op1_def
758 : 1225089 : && is_gimple_assign (op1_def)
759 : 928062 : && gimple_assign_rhs_code (op1_def) == PLUS_EXPR
760 : 281207 : && TREE_CODE (gimple_assign_rhs2 (op1_def)) == INTEGER_CST
761 : 1381941 : && !integer_zerop (gimple_assign_rhs2 (op1_def)))
762 : : {
763 : 156852 : tree target = gimple_assign_rhs1 (op1_def);
764 : :
765 : : /* If we did not find our target SSA_NAME, then this is not
766 : : an overflow test. */
767 : 156852 : if (op0 != target)
768 : : return false;
769 : :
770 : 1147 : tree type = TREE_TYPE (op0);
771 : 1147 : wide_int max = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
772 : 1147 : tree inc = gimple_assign_rhs2 (op1_def);
773 : 1147 : if (reversed)
774 : 180 : *new_cst = wide_int_to_tree (type, max + wi::to_wide (inc));
775 : : else
776 : 967 : *new_cst = wide_int_to_tree (type, max - wi::to_wide (inc));
777 : 1147 : return true;
778 : 1147 : }
779 : : }
780 : : return false;
781 : : }
782 : :
783 : : /* OP0 CODE OP1 is a comparison. Examine the comparison and potentially
784 : : OP1's defining statement to see if it ultimately has the form
785 : : OP0 CODE (OP0 PLUS INTEGER_CST)
786 : :
787 : : If so, return TRUE indicating this is an overflow test and store into
788 : : *NEW_CST an updated constant that can be used in a narrowed range test.
789 : :
790 : : These statements are left as-is in the IL to facilitate discovery of
791 : : {ADD,SUB}_OVERFLOW sequences later in the optimizer pipeline. But
792 : : the alternate range representation is often useful within VRP. */
793 : :
794 : : bool
795 : 18202175 : overflow_comparison_p (tree_code code, tree name, tree val, tree *new_cst)
796 : : {
797 : 18202175 : if (overflow_comparison_p_1 (code, name, val, false, new_cst))
798 : : return true;
799 : 18201208 : return overflow_comparison_p_1 (swap_tree_comparison (code), val, name,
800 : 18201208 : true, new_cst);
801 : : }
802 : :
803 : : /* Searches the case label vector VEC for the index *IDX of the CASE_LABEL
804 : : that includes the value VAL. The search is restricted to the range
805 : : [START_IDX, n - 1] where n is the size of VEC.
806 : :
807 : : If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
808 : : returned.
809 : :
810 : : If there is no CASE_LABEL for VAL and there is one that is larger than VAL,
811 : : it is placed in IDX and false is returned.
812 : :
813 : : If VAL is larger than any CASE_LABEL, n is placed on IDX and false is
814 : : returned. */
815 : :
816 : : bool
817 : 198202 : find_case_label_index (gswitch *stmt, size_t start_idx, tree val, size_t *idx)
818 : : {
819 : 198202 : size_t n = gimple_switch_num_labels (stmt);
820 : 198202 : size_t low, high;
821 : :
822 : : /* Find case label for minimum of the value range or the next one.
823 : : At each iteration we are searching in [low, high - 1]. */
824 : :
825 : 786597 : for (low = start_idx, high = n; high != low; )
826 : : {
827 : 471533 : tree t;
828 : 471533 : int cmp;
829 : : /* Note that i != high, so we never ask for n. */
830 : 471533 : size_t i = (high + low) / 2;
831 : 471533 : t = gimple_switch_label (stmt, i);
832 : :
833 : : /* Cache the result of comparing CASE_LOW and val. */
834 : 471533 : cmp = tree_int_cst_compare (CASE_LOW (t), val);
835 : :
836 : 471533 : if (cmp == 0)
837 : : {
838 : : /* Ranges cannot be empty. */
839 : 79339 : *idx = i;
840 : 79339 : return true;
841 : : }
842 : 392194 : else if (cmp > 0)
843 : : high = i;
844 : : else
845 : : {
846 : 177216 : low = i + 1;
847 : 177216 : if (CASE_HIGH (t) != NULL
848 : 177216 : && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
849 : : {
850 : 2001 : *idx = i;
851 : 2001 : return true;
852 : : }
853 : : }
854 : : }
855 : :
856 : 116862 : *idx = high;
857 : 116862 : return false;
858 : : }
859 : :
860 : : /* Searches the case label vector VEC for the range of CASE_LABELs that is used
861 : : for values between MIN and MAX. The first index is placed in MIN_IDX. The
862 : : last index is placed in MAX_IDX. If the range of CASE_LABELs is empty
863 : : then MAX_IDX < MIN_IDX.
864 : : Returns true if the default label is not needed. */
865 : :
866 : : bool
867 : 99093 : find_case_label_range (gswitch *stmt, tree min, tree max, size_t *min_idx,
868 : : size_t *max_idx)
869 : : {
870 : 99093 : size_t i, j;
871 : 99093 : bool min_take_default = !find_case_label_index (stmt, 1, min, &i);
872 : 99093 : bool max_take_default = !find_case_label_index (stmt, i, max, &j);
873 : :
874 : 99093 : if (i == j
875 : : && min_take_default
876 : 9334 : && max_take_default)
877 : : {
878 : : /* Only the default case label reached.
879 : : Return an empty range. */
880 : 5574 : *min_idx = 1;
881 : 5574 : *max_idx = 0;
882 : 5574 : return false;
883 : : }
884 : : else
885 : : {
886 : 93519 : bool take_default = min_take_default || max_take_default;
887 : 93519 : tree low, high;
888 : 93519 : size_t k;
889 : :
890 : 93519 : if (max_take_default)
891 : 68339 : j--;
892 : :
893 : : /* If the case label range is continuous, we do not need
894 : : the default case label. Verify that. */
895 : 93519 : high = CASE_LOW (gimple_switch_label (stmt, i));
896 : 93519 : if (CASE_HIGH (gimple_switch_label (stmt, i)))
897 : 3630 : high = CASE_HIGH (gimple_switch_label (stmt, i));
898 : 249146 : for (k = i + 1; k <= j; ++k)
899 : : {
900 : 209093 : low = CASE_LOW (gimple_switch_label (stmt, k));
901 : 209093 : if (!integer_onep (int_const_binop (MINUS_EXPR, low, high)))
902 : : {
903 : : take_default = true;
904 : : break;
905 : : }
906 : 155627 : high = low;
907 : 155627 : if (CASE_HIGH (gimple_switch_label (stmt, k)))
908 : 7766 : high = CASE_HIGH (gimple_switch_label (stmt, k));
909 : : }
910 : :
911 : 93519 : *min_idx = i;
912 : 93519 : *max_idx = j;
913 : 93519 : return !take_default;
914 : : }
915 : : }
916 : :
917 : : /* Given a SWITCH_STMT, return the case label that encompasses the
918 : : known possible values for the switch operand. RANGE_OF_OP is a
919 : : range for the known values of the switch operand. */
920 : :
921 : : tree
922 : 85621 : find_case_label_range (gswitch *switch_stmt, const irange *range_of_op)
923 : : {
924 : 85621 : if (range_of_op->undefined_p ()
925 : 85621 : || range_of_op->varying_p ())
926 : : return NULL_TREE;
927 : :
928 : 67995 : size_t i, j;
929 : 67995 : tree op = gimple_switch_index (switch_stmt);
930 : 67995 : tree type = TREE_TYPE (op);
931 : 67995 : tree tmin = wide_int_to_tree (type, range_of_op->lower_bound ());
932 : 67995 : tree tmax = wide_int_to_tree (type, range_of_op->upper_bound ());
933 : 67995 : find_case_label_range (switch_stmt, tmin, tmax, &i, &j);
934 : 67995 : if (i == j)
935 : : {
936 : : /* Look for exactly one label that encompasses the range of
937 : : the operand. */
938 : 4773 : tree label = gimple_switch_label (switch_stmt, i);
939 : 4773 : tree case_high
940 : 4773 : = CASE_HIGH (label) ? CASE_HIGH (label) : CASE_LOW (label);
941 : 4773 : wide_int wlow = wi::to_wide (CASE_LOW (label));
942 : 4773 : wide_int whigh = wi::to_wide (case_high);
943 : 4773 : int_range_max label_range (TREE_TYPE (case_high), wlow, whigh);
944 : 4773 : if (!types_compatible_p (label_range.type (), range_of_op->type ()))
945 : 1 : range_cast (label_range, range_of_op->type ());
946 : 4773 : label_range.intersect (*range_of_op);
947 : 4773 : if (label_range == *range_of_op)
948 : 3117 : return label;
949 : 4773 : }
950 : 63222 : else if (i > j)
951 : : {
952 : : /* If there are no labels at all, take the default. */
953 : 1172 : return gimple_switch_label (switch_stmt, 0);
954 : : }
955 : : else
956 : : {
957 : : /* Otherwise, there are various labels that can encompass
958 : : the range of operand. In which case, see if the range of
959 : : the operand is entirely *outside* the bounds of all the
960 : : (non-default) case labels. If so, take the default. */
961 : 62050 : unsigned n = gimple_switch_num_labels (switch_stmt);
962 : 62050 : tree min_label = gimple_switch_label (switch_stmt, 1);
963 : 62050 : tree max_label = gimple_switch_label (switch_stmt, n - 1);
964 : 62050 : tree case_high = CASE_HIGH (max_label);
965 : 62050 : if (!case_high)
966 : 60015 : case_high = CASE_LOW (max_label);
967 : 62050 : int_range_max label_range (TREE_TYPE (CASE_LOW (min_label)),
968 : 62050 : wi::to_wide (CASE_LOW (min_label)),
969 : 186150 : wi::to_wide (case_high));
970 : 62050 : if (!types_compatible_p (label_range.type (), range_of_op->type ()))
971 : 24 : range_cast (label_range, range_of_op->type ());
972 : 62050 : label_range.intersect (*range_of_op);
973 : 62050 : if (label_range.undefined_p ())
974 : 147 : return gimple_switch_label (switch_stmt, 0);
975 : 62050 : }
976 : : return NULL_TREE;
977 : : }
978 : :
979 : : struct case_info
980 : : {
981 : : tree expr;
982 : : basic_block bb;
983 : : };
984 : :
985 : : // This is a ranger based folder which continues to use the dominator
986 : : // walk to access the substitute and fold machinery. Ranges are calculated
987 : : // on demand.
988 : :
989 : : class rvrp_folder : public substitute_and_fold_engine
990 : : {
991 : : public:
992 : :
993 : 4005387 : rvrp_folder (gimple_ranger *r, bool all)
994 : 4005387 : : substitute_and_fold_engine (),
995 : 8010774 : m_unreachable (*r, all),
996 : 4005387 : m_simplifier (r, r->non_executable_edge_flag)
997 : : {
998 : 4005387 : m_ranger = r;
999 : 4005387 : m_pta = new pointer_equiv_analyzer (m_ranger);
1000 : 4005387 : m_last_bb_stmt = NULL;
1001 : 4005387 : }
1002 : :
1003 : 4005387 : ~rvrp_folder ()
1004 : 4005387 : {
1005 : 4005387 : delete m_pta;
1006 : 4005387 : }
1007 : :
1008 : 109296035 : tree value_of_expr (tree name, gimple *s = NULL) override
1009 : : {
1010 : : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1011 : 109296035 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1012 : : return NULL;
1013 : 109283920 : tree ret = m_ranger->value_of_expr (name, s);
1014 : 109283920 : if (!ret && supported_pointer_equiv_p (name))
1015 : 46419149 : ret = m_pta->get_equiv (name);
1016 : : return ret;
1017 : : }
1018 : :
1019 : 22866215 : tree value_on_edge (edge e, tree name) override
1020 : : {
1021 : : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1022 : 22866215 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1023 : : return NULL;
1024 : 22843697 : tree ret = m_ranger->value_on_edge (e, name);
1025 : 22843697 : if (!ret && supported_pointer_equiv_p (name))
1026 : 6517580 : ret = m_pta->get_equiv (name);
1027 : : return ret;
1028 : : }
1029 : :
1030 : 44786042 : tree value_of_stmt (gimple *s, tree name = NULL) override
1031 : : {
1032 : : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1033 : 44786042 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1034 : : return NULL;
1035 : 44784152 : return m_ranger->value_of_stmt (s, name);
1036 : : }
1037 : :
1038 : 34933031 : void pre_fold_bb (basic_block bb) override
1039 : : {
1040 : 34933031 : m_pta->enter (bb);
1041 : 49082935 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1042 : 14149904 : gsi_next (&gsi))
1043 : 14149904 : m_ranger->register_inferred_ranges (gsi.phi ());
1044 : 34933031 : m_last_bb_stmt = last_nondebug_stmt (bb);
1045 : 34933031 : }
1046 : :
1047 : 34933031 : void post_fold_bb (basic_block bb) override
1048 : : {
1049 : 34933031 : m_pta->leave (bb);
1050 : 34933031 : }
1051 : :
1052 : 209520706 : void pre_fold_stmt (gimple *stmt) override
1053 : : {
1054 : 209520706 : m_pta->visit_stmt (stmt);
1055 : : // If this is the last stmt and there are inferred ranges, reparse the
1056 : : // block for transitive inferred ranges that occur earlier in the block.
1057 : 209520706 : if (stmt == m_last_bb_stmt)
1058 : : {
1059 : 28731150 : m_ranger->register_transitive_inferred_ranges (gimple_bb (stmt));
1060 : : // Also check for builtin_unreachable calls.
1061 : 28731150 : if (cfun->after_inlining && gimple_code (stmt) == GIMPLE_COND)
1062 : 7752006 : m_unreachable.maybe_register (stmt);
1063 : : }
1064 : 209520706 : }
1065 : :
1066 : 209294601 : bool fold_stmt (gimple_stmt_iterator *gsi) override
1067 : : {
1068 : 209294601 : bool ret = m_simplifier.simplify (gsi);
1069 : 209294601 : if (!ret)
1070 : 208762014 : ret = m_ranger->fold_stmt (gsi, follow_single_use_edges);
1071 : 209294601 : m_ranger->register_inferred_ranges (gsi_stmt (*gsi));
1072 : 209294601 : return ret;
1073 : : }
1074 : :
1075 : : remove_unreachable m_unreachable;
1076 : : private:
1077 : : DISABLE_COPY_AND_ASSIGN (rvrp_folder);
1078 : : gimple_ranger *m_ranger;
1079 : : simplify_using_ranges m_simplifier;
1080 : : pointer_equiv_analyzer *m_pta;
1081 : : gimple *m_last_bb_stmt;
1082 : : };
1083 : :
1084 : : /* Main entry point for a VRP pass using just ranger. This can be called
1085 : : from anywhere to perform a VRP pass, including from EVRP. */
1086 : :
1087 : : unsigned int
1088 : 4005387 : execute_ranger_vrp (struct function *fun, bool final_p)
1089 : : {
1090 : 4005387 : loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1091 : 4005387 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1092 : 4005387 : scev_initialize ();
1093 : 4005387 : calculate_dominance_info (CDI_DOMINATORS);
1094 : :
1095 : 4005387 : set_all_edges_as_executable (fun);
1096 : 4005387 : gimple_ranger *ranger = enable_ranger (fun, false);
1097 : 4005387 : rvrp_folder folder (ranger, final_p);
1098 : 4005387 : phi_analysis_initialize (ranger->const_query ());
1099 : 4005387 : folder.substitute_and_fold ();
1100 : : // Ensure the cache in SCEV has been cleared before processing
1101 : : // globals to be removed.
1102 : 4005387 : scev_reset ();
1103 : : // Remove tagged builtin-unreachable and maybe update globals.
1104 : 4005387 : folder.m_unreachable.remove_and_update_globals ();
1105 : 4005387 : if (dump_file && (dump_flags & TDF_DETAILS))
1106 : 46 : ranger->dump (dump_file);
1107 : :
1108 : 4005387 : if (value_range::supports_type_p (TREE_TYPE
1109 : : (TREE_TYPE (current_function_decl)))
1110 : 1721224 : && flag_ipa_vrp
1111 : 5725790 : && !lookup_attribute ("noipa", DECL_ATTRIBUTES (current_function_decl)))
1112 : : {
1113 : 1691649 : edge e;
1114 : 1691649 : edge_iterator ei;
1115 : 1691649 : bool found = false;
1116 : 1691649 : value_range return_range (TREE_TYPE (TREE_TYPE (current_function_decl)));
1117 : 3357296 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
1118 : 4996094 : if (greturn *ret = dyn_cast <greturn *> (*gsi_last_bb (e->src)))
1119 : : {
1120 : 1664800 : tree retval = gimple_return_retval (ret);
1121 : 1664800 : if (!retval)
1122 : : {
1123 : 10583 : return_range.set_varying (TREE_TYPE (TREE_TYPE (current_function_decl)));
1124 : 10583 : found = true;
1125 : 10583 : continue;
1126 : : }
1127 : 1654217 : value_range r (TREE_TYPE (retval));
1128 : 1654217 : if (ranger->range_of_expr (r, retval, ret)
1129 : 1654217 : && !r.undefined_p ()
1130 : 3307767 : && !r.varying_p ())
1131 : : {
1132 : 671670 : if (!found)
1133 : 669625 : return_range = r;
1134 : : else
1135 : 2045 : return_range.union_ (r);
1136 : : }
1137 : : else
1138 : 982547 : return_range.set_varying (TREE_TYPE (retval));
1139 : 1654217 : found = true;
1140 : 1654217 : }
1141 : 1691649 : if (found && !return_range.varying_p ())
1142 : : {
1143 : 669565 : ipa_record_return_value_range (return_range);
1144 : 1235620 : if (POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (current_function_decl)))
1145 : 223671 : && return_range.nonzero_p ()
1146 : 885465 : && cgraph_node::get (current_function_decl)
1147 : 215900 : ->add_detected_attribute ("returns_nonnull"))
1148 : 185562 : warn_function_returns_nonnull (current_function_decl);
1149 : : }
1150 : 1691649 : }
1151 : :
1152 : 4005387 : phi_analysis_finalize ();
1153 : 4005387 : disable_ranger (fun);
1154 : 4005387 : scev_finalize ();
1155 : 4005387 : loop_optimizer_finalize ();
1156 : 8010774 : return 0;
1157 : 4005387 : }
1158 : :
1159 : : // Implement a Fast VRP folder. Not quite as effective but faster.
1160 : :
1161 : : class fvrp_folder : public substitute_and_fold_engine
1162 : : {
1163 : : public:
1164 : 6 : fvrp_folder (dom_ranger *dr, bool final_p) : substitute_and_fold_engine (),
1165 : 6 : m_simplifier (dr)
1166 : : {
1167 : 6 : m_dom_ranger = dr;
1168 : 6 : if (final_p)
1169 : 2 : m_unreachable = new remove_unreachable (*dr, final_p);
1170 : : else
1171 : 4 : m_unreachable = NULL;
1172 : 6 : }
1173 : :
1174 : 6 : ~fvrp_folder () { }
1175 : :
1176 : 162 : tree value_of_expr (tree name, gimple *s = NULL) override
1177 : : {
1178 : : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1179 : 162 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1180 : : return NULL;
1181 : 162 : return m_dom_ranger->value_of_expr (name, s);
1182 : : }
1183 : :
1184 : 17 : tree value_on_edge (edge e, tree name) override
1185 : : {
1186 : : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1187 : 17 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1188 : : return NULL;
1189 : 17 : return m_dom_ranger->value_on_edge (e, name);
1190 : : }
1191 : :
1192 : 116 : tree value_of_stmt (gimple *s, tree name = NULL) override
1193 : : {
1194 : : // Shortcircuit subst_and_fold callbacks for abnormal ssa_names.
1195 : 116 : if (TREE_CODE (name) == SSA_NAME && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
1196 : : return NULL;
1197 : 116 : return m_dom_ranger->value_of_stmt (s, name);
1198 : : }
1199 : :
1200 : 31 : void pre_fold_bb (basic_block bb) override
1201 : : {
1202 : 31 : m_dom_ranger->pre_bb (bb);
1203 : : // Now process the PHIs in advance.
1204 : 31 : gphi_iterator psi = gsi_start_phis (bb);
1205 : 50 : for ( ; !gsi_end_p (psi); gsi_next (&psi))
1206 : : {
1207 : 19 : tree name = gimple_range_ssa_p (PHI_RESULT (psi.phi ()));
1208 : 19 : if (name)
1209 : : {
1210 : 9 : value_range vr(TREE_TYPE (name));
1211 : 9 : m_dom_ranger->range_of_stmt (vr, psi.phi (), name);
1212 : 9 : }
1213 : : }
1214 : 31 : }
1215 : :
1216 : 31 : void post_fold_bb (basic_block bb) override
1217 : : {
1218 : 31 : m_dom_ranger->post_bb (bb);
1219 : 31 : }
1220 : :
1221 : 144 : void pre_fold_stmt (gimple *s) override
1222 : : {
1223 : : // Ensure range_of_stmt has been called.
1224 : 144 : tree type = gimple_range_type (s);
1225 : 144 : if (type)
1226 : : {
1227 : 126 : value_range vr(type);
1228 : 126 : m_dom_ranger->range_of_stmt (vr, s);
1229 : 126 : }
1230 : 144 : if (m_unreachable && gimple_code (s) == GIMPLE_COND)
1231 : 9 : m_unreachable->maybe_register (s);
1232 : :
1233 : 144 : }
1234 : :
1235 : 135 : bool fold_stmt (gimple_stmt_iterator *gsi) override
1236 : : {
1237 : 135 : bool ret = m_simplifier.simplify (gsi);
1238 : 135 : if (!ret)
1239 : 132 : ret = ::fold_stmt (gsi, follow_single_use_edges);
1240 : 135 : return ret;
1241 : : }
1242 : :
1243 : : remove_unreachable *m_unreachable;
1244 : : private:
1245 : : DISABLE_COPY_AND_ASSIGN (fvrp_folder);
1246 : : simplify_using_ranges m_simplifier;
1247 : : dom_ranger *m_dom_ranger;
1248 : : };
1249 : :
1250 : :
1251 : : // Main entry point for a FAST VRP pass using a dom ranger.
1252 : :
1253 : : unsigned int
1254 : 6 : execute_fast_vrp (struct function *fun, bool final_p)
1255 : : {
1256 : 6 : calculate_dominance_info (CDI_DOMINATORS);
1257 : 6 : dom_ranger dr;
1258 : 6 : fvrp_folder folder (&dr, final_p);
1259 : :
1260 : 6 : gcc_checking_assert (!fun->x_range_query);
1261 : 6 : set_all_edges_as_executable (fun);
1262 : 6 : fun->x_range_query = &dr;
1263 : : // Create a relation oracle without transitives.
1264 : 6 : get_range_query (fun)->create_relation_oracle (false);
1265 : :
1266 : 6 : folder.substitute_and_fold ();
1267 : 6 : if (folder.m_unreachable)
1268 : 2 : folder.m_unreachable->remove ();
1269 : :
1270 : 6 : get_range_query (fun)->destroy_relation_oracle ();
1271 : 6 : fun->x_range_query = NULL;
1272 : 12 : return 0;
1273 : 6 : }
1274 : :
1275 : : namespace {
1276 : :
1277 : : const pass_data pass_data_vrp =
1278 : : {
1279 : : GIMPLE_PASS, /* type */
1280 : : "vrp", /* name */
1281 : : OPTGROUP_NONE, /* optinfo_flags */
1282 : : TV_TREE_VRP, /* tv_id */
1283 : : PROP_ssa, /* properties_required */
1284 : : 0, /* properties_provided */
1285 : : 0, /* properties_destroyed */
1286 : : 0, /* todo_flags_start */
1287 : : ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
1288 : : };
1289 : :
1290 : : const pass_data pass_data_early_vrp =
1291 : : {
1292 : : GIMPLE_PASS, /* type */
1293 : : "evrp", /* name */
1294 : : OPTGROUP_NONE, /* optinfo_flags */
1295 : : TV_TREE_EARLY_VRP, /* tv_id */
1296 : : PROP_ssa, /* properties_required */
1297 : : 0, /* properties_provided */
1298 : : 0, /* properties_destroyed */
1299 : : 0, /* todo_flags_start */
1300 : : ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
1301 : : };
1302 : :
1303 : : const pass_data pass_data_fast_vrp =
1304 : : {
1305 : : GIMPLE_PASS, /* type */
1306 : : "fvrp", /* name */
1307 : : OPTGROUP_NONE, /* optinfo_flags */
1308 : : TV_TREE_FAST_VRP, /* tv_id */
1309 : : PROP_ssa, /* properties_required */
1310 : : 0, /* properties_provided */
1311 : : 0, /* properties_destroyed */
1312 : : 0, /* todo_flags_start */
1313 : : ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ),
1314 : : };
1315 : :
1316 : :
1317 : : class pass_vrp : public gimple_opt_pass
1318 : : {
1319 : : public:
1320 : 842493 : pass_vrp (gcc::context *ctxt, const pass_data &data_)
1321 : 1684986 : : gimple_opt_pass (data_, ctxt), data (data_), final_p (false)
1322 : : { }
1323 : :
1324 : : /* opt_pass methods: */
1325 : 280831 : opt_pass * clone () final override
1326 : 280831 : { return new pass_vrp (m_ctxt, data); }
1327 : 561662 : void set_pass_param (unsigned int n, bool param) final override
1328 : : {
1329 : 561662 : gcc_assert (n == 0);
1330 : 561662 : final_p = param;
1331 : 561662 : }
1332 : 4252191 : bool gate (function *) final override { return flag_tree_vrp != 0; }
1333 : 4005393 : unsigned int execute (function *fun) final override
1334 : : {
1335 : : // Check for fast vrp.
1336 : 4005393 : bool use_fvrp = (&data == &pass_data_fast_vrp);
1337 : 4005393 : if (!use_fvrp && last_basic_block_for_fn (fun) > param_vrp_block_limit)
1338 : : {
1339 : 6 : use_fvrp = true;
1340 : 6 : warning (OPT_Wdisabled_optimization,
1341 : : "using fast VRP algorithm; %d basic blocks"
1342 : : " exceeds %<--param=vrp-block-limit=%d%> limit",
1343 : : n_basic_blocks_for_fn (fun),
1344 : : param_vrp_block_limit);
1345 : : }
1346 : 4005393 : if (use_fvrp)
1347 : 6 : return execute_fast_vrp (fun, final_p);
1348 : 4005387 : return execute_ranger_vrp (fun, final_p);
1349 : : }
1350 : :
1351 : : private:
1352 : : const pass_data &data;
1353 : : bool final_p;
1354 : : }; // class pass_vrp
1355 : : } // anon namespace
1356 : :
1357 : : gimple_opt_pass *
1358 : 280831 : make_pass_vrp (gcc::context *ctxt)
1359 : : {
1360 : 280831 : return new pass_vrp (ctxt, pass_data_vrp);
1361 : : }
1362 : :
1363 : : gimple_opt_pass *
1364 : 280831 : make_pass_early_vrp (gcc::context *ctxt)
1365 : : {
1366 : 280831 : return new pass_vrp (ctxt, pass_data_early_vrp);
1367 : : }
1368 : :
1369 : : gimple_opt_pass *
1370 : 0 : make_pass_fast_vrp (gcc::context *ctxt)
1371 : : {
1372 : 0 : return new pass_vrp (ctxt, pass_data_fast_vrp);
1373 : : }
|
