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 29420773 : gimple_ranger::gimple_ranger (bool use_imm_uses) :
42 58841546 : non_executable_edge_flag (cfun),
43 29420773 : m_cache (non_executable_edge_flag, use_imm_uses),
44 29420773 : tracer (""),
45 29420773 : current_bb (NULL)
46 : {
47 : // Share the oracle from the cache.
48 29420773 : share_query (m_cache);
49 29420773 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
50 0 : tracer.enable_trace ();
51 29420773 : m_stmt_list.create (0);
52 58841546 : m_stmt_list.safe_grow (num_ssa_names);
53 29420773 : m_stmt_list.truncate (0);
54 29420773 : m_prefill_stack.create (0);
55 29420773 : m_active_prefill = BITMAP_ALLOC (NULL);
56 :
57 : // Ensure the not_executable flag is clear everywhere.
58 29420773 : if (flag_checking)
59 : {
60 29420367 : basic_block bb;
61 359578895 : FOR_ALL_BB_FN (bb, cfun)
62 : {
63 330158528 : edge_iterator ei;
64 330158528 : edge e;
65 737393687 : FOR_EACH_EDGE (e, ei, bb->succs)
66 407235159 : gcc_checking_assert ((e->flags & non_executable_edge_flag) == 0);
67 : }
68 : }
69 29420773 : }
70 :
71 58841542 : gimple_ranger::~gimple_ranger ()
72 : {
73 29420773 : BITMAP_FREE (m_active_prefill);
74 29420773 : m_prefill_stack.release ();
75 29420773 : m_stmt_list.release ();
76 58841542 : }
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 585666400 : gimple_ranger::range_of_expr (vrange &r, tree expr, gimple *stmt)
91 : {
92 585666400 : if (!dbg_cnt (ranger_cnt))
93 0 : return get_global_range_query ()->range_of_expr (r, expr, stmt);
94 :
95 585666400 : unsigned idx;
96 585666400 : if (!gimple_range_ssa_p (expr))
97 91852651 : return get_tree_range (r, expr, stmt);
98 :
99 493813749 : 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 493813749 : if (!stmt || !gimple_bb (stmt))
115 : {
116 44518615 : 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 44518615 : if (!m_cache.get_global_range (r, expr))
120 : {
121 4232039 : gimple *s = SSA_NAME_DEF_STMT (expr);
122 : // Calculate a range for S if it is safe to do so.
123 4232039 : if (s && gimple_bb (s) && gimple_get_lhs (s) == expr)
124 4070472 : 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 40448143 : if (current_bb && m_cache.block_range (tmp, current_bb, expr, false))
129 : {
130 1109303 : r.intersect (tmp);
131 1109303 : char str[80];
132 1109303 : sprintf (str, "picked up range from bb %d\n",current_bb->index);
133 1109303 : if (idx)
134 0 : tracer.print (idx, str);
135 : }
136 44518615 : }
137 : // For a debug stmt, pick the best value currently available, do not
138 : // trigger new value calculations. PR 100781.
139 449295134 : else if (is_gimple_debug (stmt))
140 43835771 : m_cache.range_of_expr (r, expr, stmt);
141 : else
142 : {
143 405459363 : basic_block bb = gimple_bb (stmt);
144 405459363 : 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 405459363 : 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 248422309 : if (m_cache.get_global_range (r, expr))
152 212394654 : m_cache.block_range (r, bb, expr, false);
153 : else
154 36027655 : range_of_stmt (r, def_stmt, expr);
155 : }
156 : // Otherwise OP comes from outside this block, use range on entry.
157 : else
158 157037054 : range_on_entry (r, bb, expr);
159 : }
160 489743277 : 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 192184957 : gimple_ranger::range_on_entry (vrange &r, basic_block bb, tree name)
169 : {
170 192184957 : if (!dbg_cnt (ranger_cnt))
171 0 : return get_global_range_query ()->range_on_entry (r, bb, name);
172 :
173 192184957 : if (!gimple_range_ssa_p (name))
174 126916 : return get_tree_range (r, name, NULL, bb, NULL);
175 :
176 192058041 : value_range entry_range (TREE_TYPE (name));
177 :
178 192058041 : unsigned idx;
179 192058041 : 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 192058041 : 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 192058041 : if (bb && m_cache.block_range (entry_range, bb, name))
190 127861269 : r.intersect (entry_range);
191 :
192 192058041 : if (idx)
193 0 : tracer.trailer (idx, "range_on_entry", true, name, r);
194 192058041 : return true;
195 192058041 : }
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 62425608 : gimple_ranger::range_on_exit (vrange &r, basic_block bb, tree name)
202 : {
203 62425608 : if (!dbg_cnt (ranger_cnt))
204 0 : return get_global_range_query ()->range_on_exit (r, bb, name);
205 :
206 62425608 : if (!gimple_range_ssa_p (name))
207 0 : return get_tree_range (r, name, NULL, NULL, bb);
208 :
209 62425608 : unsigned idx;
210 62425608 : 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 62425608 : gimple *s = SSA_NAME_DEF_STMT (name);
217 62425608 : 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 62425608 : if (def_bb != bb)
221 : {
222 29584506 : if (bb->flags & BB_RTL)
223 : s = NULL;
224 : else
225 29568399 : s = last_nondebug_stmt (bb);
226 : }
227 : // If there is no statement provided, get the range_on_entry for this block.
228 29568399 : if (s)
229 49782710 : range_of_expr (r, name, s);
230 : else
231 12642898 : range_on_entry (r, bb, name);
232 62425608 : gcc_checking_assert (r.undefined_p ()
233 : || range_compatible_p (r.type (), TREE_TYPE (name)));
234 :
235 62425608 : 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 76451300 : gimple_ranger::range_on_edge (vrange &r, edge e, tree name)
244 : {
245 76451300 : if (!dbg_cnt (ranger_cnt))
246 0 : return get_global_range_query ()->range_on_edge (r, e, name);
247 :
248 76451300 : value_range edge_range (TREE_TYPE (name));
249 :
250 76451300 : if (!r.supports_type_p (TREE_TYPE (name)))
251 : return false;
252 :
253 : // Do not process values along abnormal edges.
254 76451300 : if (e->flags & EDGE_ABNORMAL)
255 20028 : return get_tree_range (r, name, NULL);
256 :
257 76431272 : unsigned idx;
258 76431272 : 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 76431272 : if ((e->flags & non_executable_edge_flag))
266 : {
267 230166 : r.set_undefined ();
268 230166 : if (idx)
269 0 : tracer.trailer (idx, "range_on_edge [Unexecutable] ", true,
270 : name, r);
271 : return true;
272 : }
273 :
274 76201106 : bool res = true;
275 76201106 : if (!gimple_range_ssa_p (name))
276 13775498 : res = get_tree_range (r, name, NULL, NULL, NULL, e);
277 : else
278 : {
279 62425608 : range_on_exit (r, e->src, name);
280 : // If this is not an abnormal edge, check for a non-null exit .
281 62425608 : if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
282 62108007 : infer_oracle ().maybe_adjust_range (r, name, e->src);
283 62425608 : 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 62425608 : if (m_cache.range_on_edge (edge_range, e, name))
288 62425608 : r.intersect (edge_range);
289 : }
290 :
291 76201106 : if (idx)
292 0 : tracer.trailer (idx, "range_on_edge", res, name, r);
293 : return res;
294 76451300 : }
295 :
296 : // fold_range wrapper for range_of_stmt to use as an internal client.
297 :
298 : bool
299 158604224 : gimple_ranger::fold_range_internal (vrange &r, gimple *s, tree name)
300 : {
301 158604224 : fold_using_range f;
302 158604224 : fur_depend src (s, this, &m_cache);
303 158604224 : 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 392088569 : gimple_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
314 : {
315 392088569 : if (!dbg_cnt (ranger_cnt))
316 0 : return get_global_range_query ()->range_of_stmt (r, s, name);
317 :
318 392088569 : bool res;
319 392088569 : r.set_undefined ();
320 :
321 392088569 : unsigned idx;
322 392088569 : 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 392088569 : if (!name)
331 25795798 : name = gimple_get_lhs (s);
332 :
333 : // If no name, simply call the base routine.
334 25795798 : if (!name)
335 : {
336 21725326 : res = fold_range_internal (r, s, NULL_TREE);
337 21725326 : if (res && is_a <gcond *> (s))
338 : {
339 : // Update any exports in the cache if this is a gimple cond statement.
340 21680072 : tree exp;
341 21680072 : basic_block bb = gimple_bb (s);
342 65214809 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, exp)
343 43534737 : m_cache.propagate_updated_value (exp, bb);
344 : }
345 : }
346 370363243 : else if (!gimple_range_ssa_p (name))
347 36203072 : res = get_tree_range (r, name, NULL);
348 : else
349 : {
350 334160171 : bool current;
351 : // Check if the stmt has already been processed.
352 334160171 : if (m_cache.get_global_range (r, name, current))
353 : {
354 : // If it isn't stale, use this cached value.
355 229220428 : if (current)
356 : {
357 222383394 : if (idx)
358 0 : tracer.trailer (idx, " cached", true, name, r);
359 222383394 : return true;
360 : }
361 : }
362 : else
363 104939743 : prefill_stmt_dependencies (name);
364 :
365 : // Calculate a new value.
366 111776777 : value_range tmp (TREE_TYPE (name));
367 111776777 : 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 111776777 : bool changed = r.intersect (tmp);
373 111776777 : m_cache.set_global_range (name, r, changed);
374 111776777 : res = true;
375 111776777 : }
376 :
377 169705175 : 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 140755552 : gimple_ranger::prefill_name (tree name)
387 : {
388 140755552 : if (!gimple_range_ssa_p (name))
389 : return false;
390 :
391 103542870 : unsigned v = SSA_NAME_VERSION (name);
392 :
393 : // Already active cycle. Use seeded value and do not chase it.
394 103542870 : if (bitmap_bit_p (m_active_prefill, v))
395 : return false;
396 :
397 : // Process only range-ops and PHIs.
398 94168778 : gimple *stmt = SSA_NAME_DEF_STMT (name);
399 94168778 : if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt))
400 : return false;
401 :
402 : // Already calculated.
403 64223357 : value_range r (TREE_TYPE (name));
404 64223357 : if (m_cache.get_global_range (r, name))
405 : return false;
406 :
407 24957914 : bool current;
408 : // Seed the initial cache value to avoid cycles.
409 24957914 : m_cache.get_global_range (r, name, current);
410 :
411 24957914 : bitmap_set_bit (m_active_prefill, v);
412 24957914 : m_prefill_stack.safe_push ({ name, 0 });
413 24957914 : return true;
414 64223357 : }
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 104939743 : gimple_ranger::prefill_stmt_dependencies (tree ssa)
425 : {
426 104939743 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
427 : return;
428 :
429 94563748 : gimple *stmt = SSA_NAME_DEF_STMT (ssa);
430 94563748 : gcc_checking_assert (stmt);
431 94563748 : if (!gimple_bb (stmt))
432 : return;
433 :
434 : // Process only range-ops and PHIs.
435 94563747 : if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt))
436 : return;
437 :
438 52462789 : unsigned idx = tracer.header ("ROS dependence fill\n");
439 :
440 52462789 : bitmap_set_bit (m_active_prefill, SSA_NAME_VERSION (ssa));
441 52462789 : m_prefill_stack.safe_push ({ ssa, 0 });
442 :
443 154841406 : while (!m_prefill_stack.is_empty ())
444 : {
445 102378617 : prefill_frame &frame = m_prefill_stack.last ();
446 102378617 : tree name = frame.name;
447 102378617 : stmt = SSA_NAME_DEF_STMT (name);
448 :
449 : // Print the ROS (Range Of Stmt) data the first time it is seen.
450 102378617 : 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 102378617 : if (gphi *phi = dyn_cast <gphi *> (stmt))
459 : {
460 63127220 : while (frame.next_op < gimple_phi_num_args (phi))
461 : {
462 44182427 : tree op = gimple_phi_arg_def (phi, frame.next_op++);
463 44182427 : if (prefill_name (op))
464 : break;
465 : }
466 : }
467 : else
468 : {
469 71517629 : gimple_range_op_handler handler (stmt);
470 246701497 : while (handler && frame.next_op < 2)
471 : {
472 116707958 : tree op = (frame.next_op++ == 0) ? handler.operand2 ()
473 58353979 : : handler.operand1 ();
474 116707958 : if (!op)
475 20134833 : continue;
476 96573125 : if (prefill_name (op))
477 : break;
478 : }
479 : }
480 :
481 : // If the same name is not top of stack, keep processing.
482 102378617 : if (m_prefill_stack.last ().name != name)
483 77276496 : continue;
484 :
485 : // All dependencies have been handled. Pop and fold.
486 77420703 : m_prefill_stack.pop ();
487 77420703 : bitmap_clear_bit (m_active_prefill, SSA_NAME_VERSION (name));
488 :
489 : // Do not fold the original request. The caller will calculate it.
490 77420703 : if (name == ssa)
491 52318582 : continue;
492 :
493 25102121 : value_range r (TREE_TYPE (name));
494 25102121 : fold_range_internal (r, stmt, name);
495 :
496 25102121 : value_range tmp (TREE_TYPE (name));
497 25102121 : m_cache.get_global_range (tmp, name);
498 25102121 : bool changed = tmp.intersect (r);
499 25102121 : m_cache.set_global_range (name, tmp, changed);
500 25102121 : }
501 :
502 52462789 : 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 258713321 : gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
514 : {
515 258713321 : gimple *stmt = gsi_stmt (*gsi);
516 258713321 : current_bb = gimple_bb (stmt);
517 258713321 : bool ret = ::fold_stmt (gsi, valueize);
518 258713321 : current_bb = NULL;
519 258713321 : 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 274244584 : gimple_ranger::register_inferred_ranges (gimple *s)
527 : {
528 : // First, export the LHS if it is a new global range.
529 274244584 : tree lhs = gimple_get_lhs (s);
530 274244584 : if (lhs)
531 : {
532 91034020 : value_range tmp (TREE_TYPE (lhs));
533 91034020 : if (range_of_stmt (tmp, s, lhs) && !tmp.varying_p ())
534 18770883 : set_range_info (lhs, tmp);
535 91034020 : }
536 274244584 : m_cache.apply_inferred_ranges (s);
537 274244584 : }
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 31760977 : gimple_ranger::register_transitive_inferred_ranges (basic_block bb)
545 : {
546 : // Return if there are no inferred ranges in BB.
547 31760977 : if (!infer_oracle ().has_range_p (bb))
548 : return;
549 :
550 2561305 : if (dump_file && (dump_flags & TDF_DETAILS))
551 9 : fprintf (dump_file, "Checking for transitive inferred ranges in BB %d\n",
552 : bb->index);
553 :
554 51148824 : for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
555 46026214 : gsi_next (&si))
556 : {
557 46026214 : gimple *s = gsi_stmt (si);
558 46026214 : tree lhs = gimple_get_lhs (s);
559 : // If the LHS already has an inferred effect, leave it be.
560 46026214 : if (!gimple_range_ssa_p (lhs) || infer_oracle ().has_range_p (bb, lhs))
561 36570504 : continue;
562 : // Pick up global value.
563 9455710 : value_range g (TREE_TYPE (lhs));
564 9455710 : 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 9455710 : value_range r (TREE_TYPE (lhs));
570 9455710 : r.set_undefined ();
571 9455710 : tree name1 = gori_ssa ()->depend1 (lhs);
572 9455710 : tree name2 = gori_ssa ()->depend2 (lhs);
573 4771526 : if ((name1 && infer_oracle ().has_range_p (bb, name1))
574 13910388 : || (name2 && infer_oracle ().has_range_p (bb, name2)))
575 : {
576 : // Check if folding S produces a different result.
577 637640 : if (fold_range (r, s, this) && g != r)
578 : {
579 25707 : gimple_infer_range ir (lhs, r);
580 25707 : infer_oracle ().add_ranges (s, ir);
581 25707 : m_cache.register_inferred_value (r, lhs, bb);
582 25707 : }
583 : }
584 9455710 : }
585 : }
586 :
587 : // Indicate NAME should have its range recalculated next time it is used.
588 :
589 : void
590 12724241 : gimple_ranger::update_range_info (tree name)
591 : {
592 12724241 : m_cache.mark_stale (name);
593 12724241 : }
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 11658465 : gimple_ranger::update_range_info (tree name, const vrange &r)
600 : {
601 11658465 : value_range current (TREE_TYPE (name));
602 11658465 : m_cache.get_global_range (current, name);
603 11658465 : if (current.intersect (r))
604 : {
605 234756 : m_cache.set_global_range (name, current, true);
606 234756 : m_cache.mark_stale (name);
607 : }
608 11658465 : }
609 :
610 : // Reset range information for NAME.
611 :
612 : void
613 1157 : gimple_ranger::reset_range_info (tree name)
614 : {
615 : // Clearing the cache will also clear all the shared oracles.
616 1157 : m_cache.reset_range_info (name);
617 1157 : }
618 :
619 : // This routine will export whatever global ranges are known to GCC
620 : // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
621 :
622 : void
623 2121033 : gimple_ranger::export_global_ranges ()
624 : {
625 2121033 : if (dump_file)
626 : {
627 : /* Print the header only when there's something else
628 : to print below. */
629 297 : fprintf (dump_file, "Exporting new global ranges:\n");
630 297 : fprintf (dump_file, "============================\n");
631 : }
632 110309539 : for (unsigned x = 1; x < num_ssa_names; x++)
633 : {
634 108188506 : tree name = ssa_name (x);
635 108188506 : if (!name)
636 30403344 : continue;
637 77785162 : value_range r (TREE_TYPE (name));
638 77785162 : if (name && !SSA_NAME_IN_FREE_LIST (name) && gimple_range_ssa_p (name)
639 44651347 : && m_cache.get_global_range (r, name) && !r.varying_p())
640 12787930 : set_range_info (name, r);
641 77785162 : }
642 2121033 : if (dump_file)
643 297 : fprintf (dump_file, "========= Done =============\n");
644 2121033 : }
645 :
646 : // Print the known table values to file F.
647 :
648 : void
649 257 : gimple_ranger::dump_bb (FILE *f, basic_block bb)
650 : {
651 257 : unsigned x;
652 257 : edge_iterator ei;
653 257 : edge e;
654 257 : fprintf (f, "\n=========== BB %d ============\n", bb->index);
655 257 : m_cache.dump_bb (f, bb);
656 :
657 257 : ::dump_bb (f, bb, 4, TDF_NONE);
658 :
659 : // Now find any globals defined in this block.
660 12764 : for (x = 1; x < num_ssa_names; x++)
661 : {
662 12250 : tree name = ssa_name (x);
663 17500 : if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
664 7000 : continue;
665 5250 : value_range range (TREE_TYPE (name));
666 5250 : if (gimple_bb (SSA_NAME_DEF_STMT (name)) == bb
667 5250 : && m_cache.get_global_range (range, name))
668 : {
669 293 : if (!range.varying_p ())
670 : {
671 155 : print_generic_expr (f, name, TDF_SLIM);
672 155 : fprintf (f, " : ");
673 155 : range.dump (f);
674 155 : fprintf (f, "\n");
675 : }
676 :
677 : }
678 5250 : }
679 :
680 : // And now outgoing edges, if they define anything.
681 630 : FOR_EACH_EDGE (e, ei, bb->succs)
682 : {
683 20706 : for (x = 1; x < num_ssa_names; x++)
684 : {
685 20333 : tree name = gimple_range_ssa_p (ssa_name (x));
686 20333 : if (!name || !gori ().has_edge_range_p (name, e))
687 19697 : continue;
688 :
689 636 : value_range range (TREE_TYPE (name));
690 636 : if (m_cache.range_on_edge (range, e, name))
691 : {
692 636 : gimple *s = SSA_NAME_DEF_STMT (name);
693 636 : value_range tmp_range (TREE_TYPE (name));
694 : // Only print the range if this is the def block, or
695 : // the on entry cache for either end of the edge is
696 : // set.
697 974 : if ((s && bb == gimple_bb (s)) ||
698 1112 : m_cache.block_range (tmp_range, bb, name, false) ||
699 138 : m_cache.block_range (tmp_range, e->dest, name, false))
700 : {
701 498 : if (!range.varying_p ())
702 : {
703 433 : fprintf (f, "%d->%d ", e->src->index,
704 433 : e->dest->index);
705 433 : char c = ' ';
706 433 : if (e->flags & EDGE_TRUE_VALUE)
707 206 : fprintf (f, " (T)%c", c);
708 227 : else if (e->flags & EDGE_FALSE_VALUE)
709 227 : fprintf (f, " (F)%c", c);
710 : else
711 0 : fprintf (f, " ");
712 433 : print_generic_expr (f, name, TDF_SLIM);
713 433 : fprintf(f, " : \t");
714 433 : range.dump(f);
715 433 : fprintf (f, "\n");
716 : }
717 : }
718 636 : }
719 636 : }
720 : }
721 257 : }
722 :
723 : // Print the known table values to file F.
724 :
725 : void
726 48 : gimple_ranger::dump (FILE *f)
727 : {
728 48 : basic_block bb;
729 :
730 305 : FOR_EACH_BB_FN (bb, cfun)
731 257 : dump_bb (f, bb);
732 :
733 48 : m_cache.dump (f);
734 48 : }
735 :
736 : void
737 0 : gimple_ranger::debug ()
738 : {
739 0 : dump (stderr);
740 0 : }
741 :
742 : /* Create a new ranger instance and associate it with function FUN.
743 : Each call must be paired with a call to disable_ranger to release
744 : resources. */
745 :
746 : gimple_ranger *
747 22497828 : enable_ranger (struct function *fun, bool use_imm_uses)
748 : {
749 22497828 : gimple_ranger *r;
750 :
751 22497828 : gcc_checking_assert (!fun->x_range_query);
752 22497828 : r = new gimple_ranger (use_imm_uses);
753 22497828 : fun->x_range_query = r;
754 :
755 22497828 : 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 22497828 : disable_ranger (struct function *fun)
763 : {
764 22497828 : gcc_checking_assert (fun->x_range_query);
765 22497828 : delete fun->x_range_query;
766 22497828 : fun->x_range_query = NULL;
767 22497828 : }
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 4636 : dom_ranger::range_of_expr (vrange &r, tree expr, gimple *s)
813 : {
814 4636 : if (!dbg_cnt (ranger_cnt))
815 0 : return get_global_range_query ()->range_of_expr (r, expr, s);
816 :
817 4636 : unsigned idx;
818 4636 : if (!gimple_range_ssa_p (expr))
819 1108 : return get_tree_range (r, expr, s);
820 :
821 3528 : 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 3528 : if (s)
835 3514 : range_in_bb (r, gimple_bb (s), expr);
836 : else
837 14 : m_global.range_of_expr (r, expr, s);
838 :
839 3528 : 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 3553 : dom_ranger::range_in_bb (vrange &r, basic_block bb, tree name)
879 : {
880 : // Start with the global value.
881 3553 : m_global.range_of_expr (r, name);
882 :
883 : // If there is a contextual range, intersect it with the global range
884 3553 : ssa_lazy_cache *context = m_bb[bb->index];
885 3553 : 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 3553 : }
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 : }
|
