Line data Source code
1 : /* Code for GIMPLE range related routines.
2 : Copyright (C) 2019-2026 Free Software Foundation, Inc.
3 : Contributed by Andrew MacLeod <amacleod@redhat.com>
4 : and Aldy Hernandez <aldyh@redhat.com>.
5 :
6 : This file is part of GCC.
7 :
8 : GCC is free software; you can redistribute it and/or modify
9 : it under the terms of the GNU General Public License as published by
10 : the Free Software Foundation; either version 3, or (at your option)
11 : any later version.
12 :
13 : GCC is distributed in the hope that it will be useful,
14 : but WITHOUT ANY WARRANTY; without even the implied warranty of
15 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 : GNU General Public License for more details.
17 :
18 : You should have received a copy of the GNU General Public License
19 : along with GCC; see the file COPYING3. If not see
20 : <http://www.gnu.org/licenses/>. */
21 :
22 : #include "config.h"
23 : #include "system.h"
24 : #include "coretypes.h"
25 : #include "backend.h"
26 : #include "tree.h"
27 : #include "gimple.h"
28 : #include "ssa.h"
29 : #include "gimple-pretty-print.h"
30 : #include "gimple-iterator.h"
31 : #include "tree-cfg.h"
32 : #include "fold-const.h"
33 : #include "cfgloop.h"
34 : #include "tree-scalar-evolution.h"
35 : #include "gimple-range.h"
36 : #include "gimple-fold.h"
37 : #include "gimple-walk.h"
38 : #include "dbgcnt.h"
39 :
40 29893232 : gimple_ranger::gimple_ranger (bool use_imm_uses) :
41 59786464 : non_executable_edge_flag (cfun),
42 29893232 : m_cache (non_executable_edge_flag, use_imm_uses),
43 29893232 : tracer (""),
44 29893232 : current_bb (NULL)
45 : {
46 : // Share the oracle from the cache.
47 29893232 : share_query (m_cache);
48 29893232 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
49 0 : tracer.enable_trace ();
50 29893232 : m_stmt_list.create (0);
51 59786464 : m_stmt_list.safe_grow (num_ssa_names);
52 29893232 : m_stmt_list.truncate (0);
53 29893232 : m_prefill_stack.create (0);
54 29893232 : m_active_prefill = BITMAP_ALLOC (NULL);
55 :
56 : // Ensure the not_executable flag is clear everywhere.
57 29893232 : if (flag_checking)
58 : {
59 29892820 : basic_block bb;
60 372001477 : FOR_ALL_BB_FN (bb, cfun)
61 : {
62 342108657 : edge_iterator ei;
63 342108657 : edge e;
64 765844537 : FOR_EACH_EDGE (e, ei, bb->succs)
65 423735880 : gcc_checking_assert ((e->flags & non_executable_edge_flag) == 0);
66 : }
67 : }
68 29893232 : }
69 :
70 59786460 : gimple_ranger::~gimple_ranger ()
71 : {
72 29893232 : BITMAP_FREE (m_active_prefill);
73 29893232 : m_prefill_stack.release ();
74 29893232 : m_stmt_list.release ();
75 59786460 : }
76 :
77 : // Return a range_query which accesses just the known global values.
78 :
79 : range_query &
80 0 : gimple_ranger::const_query ()
81 : {
82 0 : return m_cache.const_query ();
83 : }
84 :
85 : // Implement range of EXPR on stmt S, and return it in R.
86 : // Return false if no range can be calculated.
87 :
88 : bool
89 632246137 : gimple_ranger::range_of_expr (vrange &r, tree expr, gimple *stmt)
90 : {
91 632246137 : if (!dbg_cnt (ranger_cnt))
92 0 : return get_global_range_query ()->range_of_expr (r, expr, stmt);
93 :
94 632246137 : unsigned idx;
95 632246137 : if (!gimple_range_ssa_p (expr))
96 117753287 : return get_tree_range (r, expr, stmt);
97 :
98 514492850 : if ((idx = tracer.header ("range_of_expr(")))
99 : {
100 0 : print_generic_expr (dump_file, expr, TDF_SLIM);
101 0 : fputs (")", dump_file);
102 0 : if (stmt)
103 : {
104 0 : fputs (" at stmt ", dump_file);
105 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
106 : }
107 : else
108 0 : fputs ("\n", dump_file);
109 : }
110 :
111 : // If there is no statement or stmt happens to be not in the IL,
112 : // just get the global value.
113 514492850 : if (!stmt || !gimple_bb (stmt))
114 : {
115 42492869 : value_range tmp (TREE_TYPE (expr));
116 : // If there is no global range for EXPR yet, try to evaluate it.
117 : // This call sets R to a global range regardless.
118 42492869 : if (!m_cache.get_global_range (r, expr))
119 : {
120 4733526 : gimple *s = SSA_NAME_DEF_STMT (expr);
121 : // Calculate a range for S if it is safe to do so.
122 4733526 : if (s && gimple_bb (s) && gimple_get_lhs (s) == expr)
123 4406720 : return range_of_stmt (r, s);
124 : }
125 : // Pick up implied context information from the on-entry cache
126 : // if current_bb is set. Do not attempt any new calculations.
127 38086149 : if (current_bb && m_cache.block_range (tmp, current_bb, expr, false))
128 : {
129 1120278 : r.intersect (tmp);
130 1120278 : char str[80];
131 1120278 : sprintf (str, "picked up range from bb %d\n",current_bb->index);
132 1120278 : if (idx)
133 0 : tracer.print (idx, str);
134 : }
135 42492869 : }
136 : // For a debug stmt, pick the best value currently available, do not
137 : // trigger new value calculations. PR 100781.
138 471999981 : else if (is_gimple_debug (stmt))
139 44670957 : m_cache.range_of_expr (r, expr, stmt);
140 : else
141 : {
142 427329024 : basic_block bb = gimple_bb (stmt);
143 427329024 : gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
144 :
145 : // If name is defined in this block, try to get an range from S.
146 427329024 : if (def_stmt && gimple_bb (def_stmt) == bb)
147 : {
148 : // Declared in this block, if it has a global set, check for an
149 : // override from a block walk, otherwise calculate it.
150 261432121 : if (m_cache.get_global_range (r, expr))
151 250976572 : m_cache.block_range (r, bb, expr, false);
152 : else
153 10455549 : range_of_stmt (r, def_stmt, expr);
154 : }
155 : // Otherwise OP comes from outside this block, use range on entry.
156 : else
157 165896903 : range_on_entry (r, bb, expr);
158 : }
159 510086130 : if (idx)
160 0 : tracer.trailer (idx, "range_of_expr", true, expr, r);
161 : return true;
162 : }
163 :
164 : // Return the range of NAME on entry to block BB in R.
165 :
166 : bool
167 205084824 : gimple_ranger::range_on_entry (vrange &r, basic_block bb, tree name)
168 : {
169 205084824 : if (!dbg_cnt (ranger_cnt))
170 0 : return get_global_range_query ()->range_on_entry (r, bb, name);
171 :
172 205084824 : if (!gimple_range_ssa_p (name))
173 186164 : return get_tree_range (r, name, NULL, bb, NULL);
174 :
175 204898660 : value_range entry_range (TREE_TYPE (name));
176 :
177 204898660 : unsigned idx;
178 204898660 : if ((idx = tracer.header ("range_on_entry (")))
179 : {
180 0 : print_generic_expr (dump_file, name, TDF_SLIM);
181 0 : fprintf (dump_file, ") to BB %d\n", bb->index);
182 : }
183 :
184 : // Start with any known range
185 204898660 : range_of_stmt (r, SSA_NAME_DEF_STMT (name), name);
186 :
187 : // Now see if there is any on_entry value which may refine it.
188 204898660 : if (bb && m_cache.block_range (entry_range, bb, name))
189 137739262 : r.intersect (entry_range);
190 :
191 204898660 : if (idx)
192 0 : tracer.trailer (idx, "range_on_entry", true, name, r);
193 204898660 : return true;
194 204898660 : }
195 :
196 : // Calculate the range for NAME at the end of block BB and return it in R.
197 : // Return false if no range can be calculated.
198 :
199 : bool
200 65241986 : gimple_ranger::range_on_exit (vrange &r, basic_block bb, tree name)
201 : {
202 65241986 : if (!dbg_cnt (ranger_cnt))
203 0 : return get_global_range_query ()->range_on_exit (r, bb, name);
204 :
205 65241986 : if (!gimple_range_ssa_p (name))
206 0 : return get_tree_range (r, name, NULL, NULL, bb);
207 :
208 65241986 : unsigned idx;
209 65241986 : if ((idx = tracer.header ("range_on_exit (")))
210 : {
211 0 : print_generic_expr (dump_file, name, TDF_SLIM);
212 0 : fprintf (dump_file, ") from BB %d\n", bb->index);
213 : }
214 :
215 65241986 : gimple *s = SSA_NAME_DEF_STMT (name);
216 65241986 : basic_block def_bb = gimple_bb (s);
217 : // If this is not the definition block, get the range on the last stmt in
218 : // the block... if there is one.
219 65241986 : if (def_bb != bb)
220 : {
221 31284755 : if (bb->flags & BB_RTL)
222 : s = NULL;
223 : else
224 31268420 : s = last_nondebug_stmt (bb);
225 : }
226 : // If there is no statement provided, get the range_on_entry for this block.
227 31268420 : if (s)
228 51840751 : range_of_expr (r, name, s);
229 : else
230 13401235 : range_on_entry (r, bb, name);
231 65241986 : gcc_checking_assert (r.undefined_p ()
232 : || range_compatible_p (r.type (), TREE_TYPE (name)));
233 :
234 65241986 : if (idx)
235 0 : tracer.trailer (idx, "range_on_exit", true, name, r);
236 : return true;
237 : }
238 :
239 : // Calculate a range for NAME on edge E and return it in R.
240 :
241 : bool
242 80260965 : gimple_ranger::range_on_edge (vrange &r, edge e, tree name)
243 : {
244 80260965 : if (!dbg_cnt (ranger_cnt))
245 0 : return get_global_range_query ()->range_on_edge (r, e, name);
246 :
247 80260965 : value_range edge_range (TREE_TYPE (name));
248 :
249 80260965 : if (!r.supports_type_p (TREE_TYPE (name)))
250 : return false;
251 :
252 : // Do not process values along abnormal edges.
253 80260965 : if (e->flags & EDGE_ABNORMAL)
254 20544 : return get_tree_range (r, name, NULL);
255 :
256 80240421 : unsigned idx;
257 80240421 : if ((idx = tracer.header ("range_on_edge (")))
258 : {
259 0 : print_generic_expr (dump_file, name, TDF_SLIM);
260 0 : fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index);
261 : }
262 :
263 : // Check to see if the edge is executable.
264 80240421 : if ((e->flags & non_executable_edge_flag))
265 : {
266 245131 : r.set_undefined ();
267 245131 : if (idx)
268 0 : tracer.trailer (idx, "range_on_edge [Unexecutable] ", true,
269 : name, r);
270 : return true;
271 : }
272 :
273 79995290 : bool res = true;
274 79995290 : if (!gimple_range_ssa_p (name))
275 14753304 : res = get_tree_range (r, name, NULL, NULL, NULL, e);
276 : else
277 : {
278 65241986 : range_on_exit (r, e->src, name);
279 : // If this is not an abnormal edge, check for a non-null exit .
280 65241986 : if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
281 64920133 : infer_oracle ().maybe_adjust_range (r, name, e->src);
282 65241986 : gcc_checking_assert (r.undefined_p ()
283 : || range_compatible_p (r.type(), TREE_TYPE (name)));
284 :
285 : // Check to see if NAME is defined on edge e.
286 65241986 : if (m_cache.range_on_edge (edge_range, e, name))
287 65241986 : r.intersect (edge_range);
288 : }
289 :
290 79995290 : if (idx)
291 0 : tracer.trailer (idx, "range_on_edge", res, name, r);
292 : return res;
293 80260965 : }
294 :
295 : // fold_range wrapper for range_of_stmt to use as an internal client.
296 :
297 : bool
298 166322777 : gimple_ranger::fold_range_internal (vrange &r, gimple *s, tree name)
299 : {
300 166322777 : fold_using_range f;
301 166322777 : fur_depend src (s, this, &m_cache);
302 166322777 : return f.fold_stmt (r, s, src, name);
303 : }
304 :
305 : // Calculate a range for statement S and return it in R. If NAME is
306 : // provided it represents the SSA_NAME on the LHS of the statement.
307 : // It is only required if there is more than one lhs/output. Check
308 : // the global cache for NAME first to see if the evaluation can be
309 : // avoided. If a range cannot be calculated, return false and UNDEFINED.
310 :
311 : bool
312 429539351 : gimple_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
313 : {
314 429539351 : if (!dbg_cnt (ranger_cnt))
315 0 : return get_global_range_query ()->range_of_stmt (r, s, name);
316 :
317 429539351 : bool res;
318 429539351 : r.set_undefined ();
319 :
320 429539351 : unsigned idx;
321 429539351 : if ((idx = tracer.header ("range_of_stmt (")))
322 : {
323 0 : if (name)
324 0 : print_generic_expr (dump_file, name, TDF_SLIM);
325 0 : fputs (") at stmt ", dump_file);
326 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
327 : }
328 :
329 429539351 : if (!name)
330 26331616 : name = gimple_get_lhs (s);
331 :
332 : // If no name, simply call the base routine.
333 26331616 : if (!name)
334 : {
335 21924896 : res = fold_range_internal (r, s, NULL_TREE);
336 21924896 : if (res && is_a <gcond *> (s))
337 : {
338 : // Update any exports in the cache if this is a gimple cond statement.
339 21879660 : tree exp;
340 21879660 : basic_block bb = gimple_bb (s);
341 65566973 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, exp)
342 43687313 : m_cache.propagate_updated_value (exp, bb);
343 : }
344 : }
345 407614455 : else if (!gimple_range_ssa_p (name))
346 47566851 : res = get_tree_range (r, name, NULL);
347 : else
348 : {
349 360047604 : bool current;
350 : // Check if the stmt has already been processed.
351 360047604 : if (m_cache.get_global_range (r, name, current))
352 : {
353 : // If it isn't stale, use this cached value.
354 249820138 : if (current)
355 : {
356 241077059 : if (idx)
357 0 : tracer.trailer (idx, " cached", true, name, r);
358 241077059 : return true;
359 : }
360 : }
361 : else
362 110227466 : prefill_stmt_dependencies (name);
363 :
364 : // Calculate a new value.
365 118970545 : value_range tmp (TREE_TYPE (name));
366 118970545 : fold_range_internal (tmp, s, name);
367 :
368 : // Combine the new value with the old value. This is required because
369 : // the way value propagation works, when the IL changes on the fly we
370 : // can sometimes get different results. See PR 97741.
371 118970545 : bool changed = r.intersect (tmp);
372 118970545 : m_cache.set_global_range (name, r, changed);
373 118970545 : res = true;
374 118970545 : }
375 :
376 188462292 : if (idx)
377 0 : tracer.trailer (idx, "range_of_stmt", res, name, r);
378 : return res;
379 : }
380 :
381 : // Return true if NAME has not been calculated yet and is pushed onto
382 : // the prefill to be processed.
383 :
384 : inline bool
385 146983745 : gimple_ranger::prefill_name (tree name)
386 : {
387 146983745 : if (!gimple_range_ssa_p (name))
388 : return false;
389 :
390 107856321 : unsigned v = SSA_NAME_VERSION (name);
391 :
392 : // Already active cycle. Use seeded value and do not chase it.
393 107856321 : if (bitmap_bit_p (m_active_prefill, v))
394 : return false;
395 :
396 : // Process only range-ops and PHIs.
397 98058454 : gimple *stmt = SSA_NAME_DEF_STMT (name);
398 98058454 : if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt))
399 : return false;
400 :
401 : // Already calculated.
402 66726057 : value_range r (TREE_TYPE (name));
403 66726057 : if (m_cache.get_global_range (r, name))
404 : return false;
405 :
406 25275573 : bool current;
407 : // Seed the initial cache value to avoid cycles.
408 25275573 : m_cache.get_global_range (r, name, current);
409 :
410 25275573 : bitmap_set_bit (m_active_prefill, v);
411 25275573 : m_prefill_stack.safe_push ({ name, 0 });
412 25275573 : return true;
413 66726057 : }
414 :
415 :
416 : // This Prefills the global cache with the dependencies of SSA before it is
417 : // evaluated. Dependencies are traversed iteratively in depth-first order,
418 : // ensuring each operand is calculated and cached before the statement which
419 : // uses it. This avoids deep recursion through the normal range_of_stmt /
420 : // range_of_expr interfaces while preserving the natural dependency ordering.
421 :
422 : void
423 110227466 : gimple_ranger::prefill_stmt_dependencies (tree ssa)
424 : {
425 110227466 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
426 : return;
427 :
428 99699696 : gimple *stmt = SSA_NAME_DEF_STMT (ssa);
429 99699696 : gcc_checking_assert (stmt);
430 99699696 : if (!gimple_bb (stmt))
431 : return;
432 :
433 : // Process only range-ops and PHIs.
434 99699695 : if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt))
435 : return;
436 :
437 56411180 : unsigned idx = tracer.header ("ROS dependence fill\n");
438 :
439 56411180 : bitmap_set_bit (m_active_prefill, SSA_NAME_VERSION (ssa));
440 56411180 : m_prefill_stack.safe_push ({ ssa, 0 });
441 :
442 163373506 : while (!m_prefill_stack.is_empty ())
443 : {
444 106962326 : prefill_frame &frame = m_prefill_stack.last ();
445 106962326 : tree name = frame.name;
446 106962326 : stmt = SSA_NAME_DEF_STMT (name);
447 :
448 : // Print the ROS (Range Of Stmt) data the first time it is seen.
449 106962326 : if (idx && frame.next_op == 0)
450 : {
451 0 : tracer.print (idx, "ROS dep fill (");
452 0 : print_generic_expr (dump_file, name, TDF_SLIM);
453 0 : fputs (") at stmt ", dump_file);
454 0 : print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
455 : }
456 :
457 106962326 : if (gphi *phi = dyn_cast <gphi *> (stmt))
458 : {
459 66373627 : while (frame.next_op < gimple_phi_num_args (phi))
460 : {
461 46309767 : tree op = gimple_phi_arg_def (phi, frame.next_op++);
462 46309767 : if (prefill_name (op))
463 : break;
464 : }
465 : }
466 : else
467 : {
468 75513806 : gimple_range_op_handler handler (stmt);
469 259997549 : while (handler && frame.next_op < 2)
470 : {
471 122860850 : tree op = (frame.next_op++ == 0) ? handler.operand2 ()
472 61430425 : : handler.operand1 ();
473 122860850 : if (!op)
474 22186872 : continue;
475 100673978 : if (prefill_name (op))
476 : break;
477 : }
478 : }
479 :
480 : // If the same name is not top of stack, keep processing.
481 106962326 : if (m_prefill_stack.last ().name != name)
482 81534990 : continue;
483 :
484 : // All dependencies have been handled. Pop and fold.
485 81686753 : m_prefill_stack.pop ();
486 81686753 : bitmap_clear_bit (m_active_prefill, SSA_NAME_VERSION (name));
487 :
488 : // Do not fold the original request. The caller will calculate it.
489 81686753 : if (name == ssa)
490 56259417 : continue;
491 :
492 25427336 : value_range r (TREE_TYPE (name));
493 25427336 : fold_range_internal (r, stmt, name);
494 :
495 25427336 : value_range tmp (TREE_TYPE (name));
496 25427336 : m_cache.get_global_range (tmp, name);
497 25427336 : bool changed = tmp.intersect (r);
498 25427336 : m_cache.set_global_range (name, tmp, changed);
499 25427336 : }
500 :
501 56411180 : if (idx)
502 : {
503 0 : unsupported_range r;
504 0 : tracer.trailer (idx, "ROS ", false, ssa, r);
505 0 : }
506 : }
507 :
508 : // This routine will invoke the gimple fold_stmt routine, providing context to
509 : // range_of_expr calls via an private internal API.
510 :
511 : bool
512 263263791 : gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
513 : {
514 263263791 : gimple *stmt = gsi_stmt (*gsi);
515 263263791 : current_bb = gimple_bb (stmt);
516 263263791 : bool ret = ::fold_stmt (gsi, valueize);
517 263263791 : current_bb = NULL;
518 263263791 : return ret;
519 : }
520 :
521 : // Called during dominator walks to register any inferred ranges that take
522 : // effect from this point forward.
523 :
524 : void
525 278954714 : gimple_ranger::register_inferred_ranges (gimple *s)
526 : {
527 : // First, export the LHS if it is a new global range.
528 278954714 : tree lhs = gimple_get_lhs (s);
529 278954714 : if (lhs)
530 : {
531 91833710 : value_range tmp (TREE_TYPE (lhs));
532 91833710 : if (range_of_stmt (tmp, s, lhs) && !tmp.varying_p ())
533 18918327 : set_range_info (lhs, tmp);
534 91833710 : }
535 278954714 : m_cache.apply_inferred_ranges (s);
536 278954714 : }
537 :
538 : // This function will walk the statements in BB to determine if any
539 : // discovered inferred ranges in the block have any transitive effects,
540 : // and if so, register those effects in BB.
541 :
542 : void
543 32155227 : gimple_ranger::register_transitive_inferred_ranges (basic_block bb)
544 : {
545 : // Return if there are no inferred ranges in BB.
546 32155227 : if (!infer_oracle ().has_range_p (bb))
547 : return;
548 :
549 2596650 : if (dump_file && (dump_flags & TDF_DETAILS))
550 9 : fprintf (dump_file, "Checking for transitive inferred ranges in BB %d\n",
551 : bb->index);
552 :
553 51924250 : for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
554 46730950 : gsi_next (&si))
555 : {
556 46730950 : gimple *s = gsi_stmt (si);
557 46730950 : tree lhs = gimple_get_lhs (s);
558 : // If the LHS already has an inferred effect, leave it be.
559 46730950 : if (!gimple_range_ssa_p (lhs) || infer_oracle ().has_range_p (bb, lhs))
560 37174466 : continue;
561 : // Pick up global value.
562 9556484 : value_range g (TREE_TYPE (lhs));
563 9556484 : range_of_expr (g, lhs);
564 :
565 : // If either dependency has an inferred range, check if recalculating
566 : // the LHS is different than the global value. If so, register it as
567 : // an inferred range as well.
568 9556484 : value_range r (TREE_TYPE (lhs));
569 9556484 : r.set_undefined ();
570 9556484 : tree name1 = gori_ssa ()->depend1 (lhs);
571 9556484 : tree name2 = gori_ssa ()->depend2 (lhs);
572 4820932 : if ((name1 && infer_oracle ().has_range_p (bb, name1))
573 14056497 : || (name2 && infer_oracle ().has_range_p (bb, name2)))
574 : {
575 : // Check if folding S produces a different result.
576 645704 : if (fold_range (r, s, this) && g != r)
577 : {
578 26519 : gimple_infer_range ir (lhs, r);
579 26519 : infer_oracle ().add_ranges (s, ir);
580 26519 : m_cache.register_inferred_value (r, lhs, bb);
581 26519 : }
582 : }
583 9556484 : }
584 : }
585 :
586 : // Indicate NAME should have its range recalculated next time it is used.
587 :
588 : void
589 14540105 : gimple_ranger::update_range_info (tree name)
590 : {
591 14540105 : m_cache.mark_stale (name);
592 14540105 : }
593 :
594 : // This is called to update ranger's concept of a global value for NAME
595 : // with range R by an outside entity.
596 :
597 : void
598 12656144 : gimple_ranger::update_range_info (tree name, const vrange &r)
599 : {
600 12656144 : value_range current (TREE_TYPE (name));
601 12656144 : m_cache.get_global_range (current, name);
602 12656144 : if (current.intersect (r))
603 : {
604 241596 : m_cache.set_global_range (name, current, true);
605 241596 : m_cache.mark_stale (name);
606 : }
607 12656144 : }
608 :
609 : // Reset range information for NAME.
610 :
611 : void
612 277349 : gimple_ranger::reset_range_info (tree name)
613 : {
614 : // Clearing the cache will also clear all the shared oracles.
615 277349 : m_cache.reset_range_info (name);
616 277349 : }
617 :
618 : // This routine will export whatever global ranges are known to GCC
619 : // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
620 :
621 : void
622 2136688 : gimple_ranger::export_global_ranges ()
623 : {
624 2136688 : if (dump_file)
625 : {
626 : /* Print the header only when there's something else
627 : to print below. */
628 306 : fprintf (dump_file, "Exporting new global ranges:\n");
629 306 : fprintf (dump_file, "============================\n");
630 : }
631 111375058 : for (unsigned x = 1; x < num_ssa_names; x++)
632 : {
633 109238370 : tree name = ssa_name (x);
634 109238370 : if (!name)
635 30841153 : continue;
636 78397217 : value_range r (TREE_TYPE (name));
637 78397217 : if (name && !SSA_NAME_IN_FREE_LIST (name) && gimple_range_ssa_p (name)
638 44893222 : && m_cache.get_global_range (r, name) && !r.varying_p())
639 14267287 : set_range_info (name, r);
640 78397217 : }
641 2136688 : if (dump_file)
642 306 : fprintf (dump_file, "========= Done =============\n");
643 2136688 : }
644 :
645 : // Print the known table values to file F.
646 :
647 : void
648 257 : gimple_ranger::dump_bb (FILE *f, basic_block bb)
649 : {
650 257 : unsigned x;
651 257 : edge_iterator ei;
652 257 : edge e;
653 257 : fprintf (f, "\n=========== BB %d ============\n", bb->index);
654 257 : m_cache.dump_bb (f, bb);
655 :
656 257 : ::dump_bb (f, bb, 4, TDF_NONE);
657 :
658 : // Now find any globals defined in this block.
659 12764 : for (x = 1; x < num_ssa_names; x++)
660 : {
661 12250 : tree name = ssa_name (x);
662 17500 : if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
663 7000 : continue;
664 5250 : value_range range (TREE_TYPE (name));
665 5250 : if (gimple_bb (SSA_NAME_DEF_STMT (name)) == bb
666 5250 : && m_cache.get_global_range (range, name))
667 : {
668 293 : if (!range.varying_p ())
669 : {
670 155 : print_generic_expr (f, name, TDF_SLIM);
671 155 : fprintf (f, " : ");
672 155 : range.dump (f);
673 155 : fprintf (f, "\n");
674 : }
675 :
676 : }
677 5250 : }
678 :
679 : // And now outgoing edges, if they define anything.
680 630 : FOR_EACH_EDGE (e, ei, bb->succs)
681 : {
682 20706 : for (x = 1; x < num_ssa_names; x++)
683 : {
684 20333 : tree name = gimple_range_ssa_p (ssa_name (x));
685 20333 : if (!name || !gori ().has_edge_range_p (name, e))
686 19697 : continue;
687 :
688 636 : value_range range (TREE_TYPE (name));
689 636 : if (m_cache.range_on_edge (range, e, name))
690 : {
691 636 : gimple *s = SSA_NAME_DEF_STMT (name);
692 636 : value_range tmp_range (TREE_TYPE (name));
693 : // Only print the range if this is the def block, or
694 : // the on entry cache for either end of the edge is
695 : // set.
696 974 : if ((s && bb == gimple_bb (s)) ||
697 1112 : m_cache.block_range (tmp_range, bb, name, false) ||
698 138 : m_cache.block_range (tmp_range, e->dest, name, false))
699 : {
700 498 : if (!range.varying_p ())
701 : {
702 433 : fprintf (f, "%d->%d ", e->src->index,
703 433 : e->dest->index);
704 433 : char c = ' ';
705 433 : if (e->flags & EDGE_TRUE_VALUE)
706 206 : fprintf (f, " (T)%c", c);
707 227 : else if (e->flags & EDGE_FALSE_VALUE)
708 227 : fprintf (f, " (F)%c", c);
709 : else
710 0 : fprintf (f, " ");
711 433 : print_generic_expr (f, name, TDF_SLIM);
712 433 : fprintf(f, " : \t");
713 433 : range.dump(f);
714 433 : fprintf (f, "\n");
715 : }
716 : }
717 636 : }
718 636 : }
719 : }
720 257 : }
721 :
722 : // Print the known table values to file F.
723 :
724 : void
725 48 : gimple_ranger::dump (FILE *f)
726 : {
727 48 : basic_block bb;
728 :
729 305 : FOR_EACH_BB_FN (bb, cfun)
730 257 : dump_bb (f, bb);
731 :
732 48 : m_cache.dump (f);
733 48 : }
734 :
735 : void
736 0 : gimple_ranger::debug ()
737 : {
738 0 : dump (stderr);
739 0 : }
740 :
741 : /* Create a new ranger instance and associate it with function FUN.
742 : Each call must be paired with a call to disable_ranger to release
743 : resources. */
744 :
745 : gimple_ranger *
746 22909022 : enable_ranger (struct function *fun, bool use_imm_uses)
747 : {
748 22909022 : gimple_ranger *r;
749 :
750 22909022 : r = new gimple_ranger (use_imm_uses);
751 22909022 : range_query *q = set_range_query (fun, r);
752 :
753 : // Ranger should be the first and only instance.
754 22909022 : gcc_checking_assert (q == get_global_range_query ());
755 22909022 : return r;
756 : }
757 :
758 : /* Destroy and release the ranger instance associated with function FUN
759 : and replace it the global ranger. */
760 :
761 : void
762 22909022 : disable_ranger (struct function *fun)
763 : {
764 : // Ensure this is the query being removed.
765 22909022 : range_query *q = set_range_query (fun, get_global_range_query ());
766 22909022 : delete q;
767 22909022 : }
768 :
769 : // ---------------------------------------------------------------------------
770 : //
771 : // The DOM based ranger assumes a single DOM walk through the IL, and is
772 : // used by the fvrp_folder as a fast VRP.
773 : // During the dom walk, the current block has an ssa_lazy_cache pointer
774 : // m_bb[bb->index] which represents all the cumulative contextual ranges
775 : // active in the block.
776 : // These ranges are pure static ranges generated by branches, and must be
777 : // combined with the equivlaent global range to produce the final range.
778 : // A NULL pointer means there are no contextual ranges.
779 :
780 : // Create a DOM based ranger for use by a DOM walk pass.
781 :
782 9 : dom_ranger::dom_ranger () : m_global ()
783 : {
784 9 : bitmap_obstack_initialize (&m_bitmaps);
785 9 : m_freelist.create (0);
786 9 : m_freelist.truncate (0);
787 9 : m_bb.create (0);
788 9 : m_bb.safe_grow_cleared (last_basic_block_for_fn (cfun));
789 9 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
790 0 : tracer.enable_trace ();
791 9 : }
792 :
793 : // Dispose of a DOM ranger.
794 :
795 9 : dom_ranger::~dom_ranger ()
796 : {
797 9 : if (dump_file && (dump_flags & TDF_DETAILS))
798 : {
799 2 : fprintf (dump_file, "Non-varying global ranges:\n");
800 2 : fprintf (dump_file, "=========================:\n");
801 2 : m_global.dump (dump_file);
802 : }
803 9 : m_bb.release ();
804 9 : m_freelist.release ();
805 9 : bitmap_obstack_release (&m_bitmaps);
806 9 : }
807 :
808 : // Implement range of EXPR on stmt S, and return it in R.
809 : // Return false if no range can be calculated.
810 :
811 : bool
812 4638 : dom_ranger::range_of_expr (vrange &r, tree expr, gimple *s)
813 : {
814 4638 : if (!dbg_cnt (ranger_cnt))
815 0 : return get_global_range_query ()->range_of_expr (r, expr, s);
816 :
817 4638 : unsigned idx;
818 4638 : if (!gimple_range_ssa_p (expr))
819 1108 : return get_tree_range (r, expr, s);
820 :
821 3530 : if ((idx = tracer.header ("range_of_expr ")))
822 : {
823 0 : print_generic_expr (dump_file, expr, TDF_SLIM);
824 0 : if (s)
825 : {
826 0 : fprintf (dump_file, " at ");
827 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
828 : }
829 : else
830 0 : fprintf (dump_file, "\n");
831 : }
832 :
833 : // If there is a statement, return the range in that statements block.
834 3530 : if (s)
835 3516 : range_in_bb (r, gimple_bb (s), expr);
836 : else
837 14 : m_global.range_of_expr (r, expr, s);
838 :
839 3530 : if (idx)
840 0 : tracer.trailer (idx, " ", true, expr, r);
841 : return true;
842 : }
843 :
844 : // Return the range of EXPR on edge E in R.
845 : // Return false if no range can be calculated.
846 :
847 : bool
848 46 : dom_ranger::range_on_edge (vrange &r, edge e, tree expr)
849 : {
850 46 : if (!dbg_cnt (ranger_cnt))
851 0 : return get_global_range_query ()->range_on_edge (r, e, expr);
852 :
853 46 : if (!gimple_range_ssa_p (expr))
854 7 : return get_tree_range (r, expr, NULL, NULL, NULL, e);
855 :
856 39 : basic_block bb = e->src;
857 39 : unsigned idx;
858 39 : if ((idx = tracer.header ("range_on_edge ")))
859 : {
860 0 : fprintf (dump_file, "%d->%d for ",e->src->index, e->dest->index);
861 0 : print_generic_expr (dump_file, expr, TDF_SLIM);
862 0 : fputc ('\n',dump_file);
863 : }
864 :
865 39 : range_in_bb (r, bb, expr);
866 39 : value_range vr(TREE_TYPE (expr));
867 39 : if (gori_name_on_edge (vr, expr, e, this))
868 4 : r.intersect (vr);
869 :
870 39 : if (idx)
871 0 : tracer.trailer (idx, " ", true, expr, r);
872 39 : return true;
873 39 : }
874 :
875 : // Return the range of NAME as it exists at the end of block BB in R.
876 :
877 : void
878 3555 : dom_ranger::range_in_bb (vrange &r, basic_block bb, tree name)
879 : {
880 : // Start with the global value.
881 3555 : m_global.range_of_expr (r, name);
882 :
883 : // If there is a contextual range, intersect it with the global range
884 3555 : ssa_lazy_cache *context = m_bb[bb->index];
885 3555 : if (context && context->has_range (name))
886 : {
887 27 : value_range cr (TREE_TYPE (name));
888 27 : context->get_range (cr, name);
889 27 : r.intersect (cr);
890 27 : }
891 3555 : }
892 :
893 : // Calculate the range of NAME, as the def of stmt S and return it in R.
894 : // Return FALSE if no range can be calculated.
895 : // Also set the global range for NAME as this should only be called within
896 : // the def block during a DOM walk.
897 :
898 : bool
899 824 : dom_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
900 : {
901 824 : if (!dbg_cnt (ranger_cnt))
902 0 : return get_global_range_query ()->range_of_stmt (r, s, name);
903 :
904 824 : unsigned idx;
905 824 : bool ret;
906 824 : if (!name)
907 424 : name = gimple_get_lhs (s);
908 :
909 824 : if (name && !gimple_range_ssa_p (name))
910 3 : return get_tree_range (r, name, NULL);
911 :
912 821 : if ((idx = tracer.header ("range_of_stmt ")))
913 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
914 :
915 : // Its already been calculated.
916 821 : if (name && m_global.has_range (name))
917 : {
918 391 : ret = m_global.range_of_expr (r, name, s);
919 391 : if (idx)
920 0 : tracer.trailer (idx, " Already had value ", ret, name, r);
921 : return ret;
922 : }
923 :
924 : // Fold using a fur_depend object so that relations are registered.
925 430 : fold_using_range f;
926 430 : fur_depend src (s, this);
927 430 : ret = f.fold_stmt (r, s, src, name);
928 :
929 : // If there is a new calculated range and it is not varying, set
930 : // a global range.
931 430 : if (ret && name && m_global.merge_range (name, r) && !r.varying_p ())
932 337 : set_range_info (name, r);
933 :
934 430 : if (idx)
935 0 : tracer.trailer (idx, " ", ret, name, r);
936 : return ret;
937 : }
938 :
939 : // Preprocess block BB. If there is a single predecessor, start with any
940 : // contextual ranges on the incoming edge, otherwise the initial list
941 : // of ranges i empty for this block. Then Merge in any contextual ranges
942 : // from the dominator block. This will become the contextual ranges
943 : // that apply to this block.
944 :
945 : void
946 37 : dom_ranger::pre_bb (basic_block bb)
947 : {
948 37 : if (dump_file && (dump_flags & TDF_DETAILS))
949 15 : fprintf (dump_file, "#FVRP entering BB %d\n", bb->index);
950 :
951 37 : m_bb[bb->index] = NULL;
952 37 : basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
953 :
954 37 : ssa_lazy_cache *e_cache;
955 37 : if (!m_freelist.is_empty ())
956 25 : e_cache = m_freelist.pop ();
957 : else
958 12 : e_cache = new ssa_lazy_cache (&m_bitmaps);
959 37 : gcc_checking_assert (e_cache->empty_p ());
960 :
961 : // If there is a single pred, check if there are any ranges on
962 : // the edge and start with those.
963 37 : if (single_pred_p (bb))
964 : {
965 20 : gori_on_edge (*e_cache, EDGE_PRED (bb, 0), this);
966 20 : if (!e_cache->empty_p () && dump_file && (dump_flags & TDF_DETAILS))
967 : {
968 10 : fprintf (dump_file, "\nEdge ranges BB %d->%d\n",
969 5 : EDGE_PRED (bb, 0)->src->index, bb->index);
970 5 : e_cache->dump(dump_file);
971 : }
972 : }
973 : // If the dominator had any ranges registered, integrate those.
974 37 : if (dom_bb && m_bb [dom_bb->index])
975 7 : e_cache->merge (*(m_bb[dom_bb->index]));
976 :
977 : // If there are no ranges, this block has no contextual ranges.
978 37 : if (e_cache->empty_p ())
979 23 : m_freelist.safe_push (e_cache);
980 : else
981 14 : m_bb[bb->index] = e_cache;
982 :
983 37 : if (dump_file && (dump_flags & TDF_DETAILS))
984 : {
985 15 : if (m_bb[bb->index])
986 : {
987 9 : fprintf (dump_file, "all contextual ranges active:\n");
988 9 : m_bb[bb->index]->dump (dump_file);
989 : }
990 : else
991 6 : fprintf (dump_file, " NO contextual ranges active:\n");
992 : }
993 37 : }
994 :
995 : // Perform any post block processing.
996 :
997 : void
998 37 : dom_ranger::post_bb (basic_block bb)
999 : {
1000 37 : if (dump_file && (dump_flags & TDF_DETAILS))
1001 15 : fprintf (dump_file, "#FVRP POST BB %d\n", bb->index);
1002 : // If there were contextual ranges, clear them and put the
1003 : // object on the freelist.
1004 37 : if (m_bb[bb->index])
1005 : {
1006 14 : m_bb[bb->index]->clear ();
1007 14 : m_freelist.safe_push (m_bb[bb->index]);
1008 14 : m_bb[bb->index] = NULL;
1009 : }
1010 37 : }
|
