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