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 29449302 : gimple_ranger::gimple_ranger (bool use_imm_uses) :
42 58898604 : non_executable_edge_flag (cfun),
43 29449302 : m_cache (non_executable_edge_flag, use_imm_uses),
44 29449302 : tracer (""),
45 29449302 : current_bb (NULL)
46 : {
47 : // Share the oracle from the cache.
48 29449302 : share_query (m_cache);
49 29449302 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
50 0 : tracer.enable_trace ();
51 29449302 : m_stmt_list.create (0);
52 58898604 : m_stmt_list.safe_grow (num_ssa_names);
53 29449302 : m_stmt_list.truncate (0);
54 29449302 : m_prefill_stack.create (0);
55 29449302 : m_active_prefill = BITMAP_ALLOC (NULL);
56 :
57 : // Ensure the not_executable flag is clear everywhere.
58 29449302 : if (flag_checking)
59 : {
60 29448896 : basic_block bb;
61 359272234 : FOR_ALL_BB_FN (bb, cfun)
62 : {
63 329823338 : edge_iterator ei;
64 329823338 : edge e;
65 736697227 : FOR_EACH_EDGE (e, ei, bb->succs)
66 406873889 : gcc_checking_assert ((e->flags & non_executable_edge_flag) == 0);
67 : }
68 : }
69 29449302 : }
70 :
71 58898600 : gimple_ranger::~gimple_ranger ()
72 : {
73 29449302 : BITMAP_FREE (m_active_prefill);
74 29449302 : m_prefill_stack.release ();
75 29449302 : m_stmt_list.release ();
76 58898600 : }
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 586919163 : gimple_ranger::range_of_expr (vrange &r, tree expr, gimple *stmt)
91 : {
92 586919163 : if (!dbg_cnt (ranger_cnt))
93 0 : return get_global_range_query ()->range_of_expr (r, expr, stmt);
94 :
95 586919163 : unsigned idx;
96 586919163 : if (!gimple_range_ssa_p (expr))
97 91937392 : return get_tree_range (r, expr, stmt);
98 :
99 494981771 : 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 494981771 : if (!stmt || !gimple_bb (stmt))
115 : {
116 44539624 : 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 44539624 : if (!m_cache.get_global_range (r, expr))
120 : {
121 4206089 : gimple *s = SSA_NAME_DEF_STMT (expr);
122 : // Calculate a range for S if it is safe to do so.
123 4206089 : if (s && gimple_bb (s) && gimple_get_lhs (s) == expr)
124 4043808 : 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 40495816 : if (current_bb && m_cache.block_range (tmp, current_bb, expr, false))
129 : {
130 1110653 : r.intersect (tmp);
131 1110653 : char str[80];
132 1110653 : sprintf (str, "picked up range from bb %d\n",current_bb->index);
133 1110653 : if (idx)
134 0 : tracer.print (idx, str);
135 : }
136 44539624 : }
137 : // For a debug stmt, pick the best value currently available, do not
138 : // trigger new value calculations. PR 100781.
139 450442147 : else if (is_gimple_debug (stmt))
140 43801507 : m_cache.range_of_expr (r, expr, stmt);
141 : else
142 : {
143 406640640 : basic_block bb = gimple_bb (stmt);
144 406640640 : 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 406640640 : 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 248913712 : if (m_cache.get_global_range (r, expr))
152 212880193 : m_cache.block_range (r, bb, expr, false);
153 : else
154 36033519 : range_of_stmt (r, def_stmt, expr);
155 : }
156 : // Otherwise OP comes from outside this block, use range on entry.
157 : else
158 157726928 : range_on_entry (r, bb, expr);
159 : }
160 490937963 : 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 192663169 : gimple_ranger::range_on_entry (vrange &r, basic_block bb, tree name)
169 : {
170 192663169 : if (!dbg_cnt (ranger_cnt))
171 0 : return get_global_range_query ()->range_on_entry (r, bb, name);
172 :
173 192663169 : if (!gimple_range_ssa_p (name))
174 127946 : return get_tree_range (r, name, NULL, bb, NULL);
175 :
176 192535223 : value_range entry_range (TREE_TYPE (name));
177 :
178 192535223 : unsigned idx;
179 192535223 : 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 192535223 : 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 192535223 : if (bb && m_cache.block_range (entry_range, bb, name))
190 127798505 : r.intersect (entry_range);
191 :
192 192535223 : if (idx)
193 0 : tracer.trailer (idx, "range_on_entry", true, name, r);
194 192535223 : return true;
195 192535223 : }
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 62465502 : gimple_ranger::range_on_exit (vrange &r, basic_block bb, tree name)
202 : {
203 62465502 : if (!dbg_cnt (ranger_cnt))
204 0 : return get_global_range_query ()->range_on_exit (r, bb, name);
205 :
206 62465502 : if (!gimple_range_ssa_p (name))
207 0 : return get_tree_range (r, name, NULL, NULL, bb);
208 :
209 62465502 : unsigned idx;
210 62465502 : 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 62465502 : gimple *s = SSA_NAME_DEF_STMT (name);
217 62465502 : 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 62465502 : if (def_bb != bb)
221 : {
222 29677176 : if (bb->flags & BB_RTL)
223 : s = NULL;
224 : else
225 29661108 : s = last_nondebug_stmt (bb);
226 : }
227 : // If there is no statement provided, get the range_on_entry for this block.
228 29661108 : if (s)
229 49787510 : range_of_expr (r, name, s);
230 : else
231 12677992 : range_on_entry (r, bb, name);
232 62465502 : gcc_checking_assert (r.undefined_p ()
233 : || range_compatible_p (r.type (), TREE_TYPE (name)));
234 :
235 62465502 : 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 76474936 : gimple_ranger::range_on_edge (vrange &r, edge e, tree name)
244 : {
245 76474936 : if (!dbg_cnt (ranger_cnt))
246 0 : return get_global_range_query ()->range_on_edge (r, e, name);
247 :
248 76474936 : value_range edge_range (TREE_TYPE (name));
249 :
250 76474936 : if (!r.supports_type_p (TREE_TYPE (name)))
251 : return false;
252 :
253 : // Do not process values along abnormal edges.
254 76474936 : if (e->flags & EDGE_ABNORMAL)
255 20059 : return get_tree_range (r, name, NULL);
256 :
257 76454877 : unsigned idx;
258 76454877 : 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 76454877 : if ((e->flags & non_executable_edge_flag))
266 : {
267 229331 : r.set_undefined ();
268 229331 : if (idx)
269 0 : tracer.trailer (idx, "range_on_edge [Unexecutable] ", true,
270 : name, r);
271 : return true;
272 : }
273 :
274 76225546 : bool res = true;
275 76225546 : if (!gimple_range_ssa_p (name))
276 13760044 : res = get_tree_range (r, name, NULL, NULL, NULL, e);
277 : else
278 : {
279 62465502 : range_on_exit (r, e->src, name);
280 : // If this is not an abnormal edge, check for a non-null exit .
281 62465502 : if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
282 62150447 : infer_oracle ().maybe_adjust_range (r, name, e->src);
283 62465502 : 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 62465502 : if (m_cache.range_on_edge (edge_range, e, name))
288 62465502 : r.intersect (edge_range);
289 : }
290 :
291 76225546 : if (idx)
292 0 : tracer.trailer (idx, "range_on_edge", res, name, r);
293 : return res;
294 76474936 : }
295 :
296 : // fold_range wrapper for range_of_stmt to use as an internal client.
297 :
298 : bool
299 158460102 : gimple_ranger::fold_range_internal (vrange &r, gimple *s, tree name)
300 : {
301 158460102 : fold_using_range f;
302 158460102 : fur_depend src (s, this, &m_cache);
303 158460102 : 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 392566965 : gimple_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
314 : {
315 392566965 : if (!dbg_cnt (ranger_cnt))
316 0 : return get_global_range_query ()->range_of_stmt (r, s, name);
317 :
318 392566965 : bool res;
319 392566965 : r.set_undefined ();
320 :
321 392566965 : unsigned idx;
322 392566965 : 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 392566965 : if (!name)
331 25743030 : name = gimple_get_lhs (s);
332 :
333 : // If no name, simply call the base routine.
334 25743030 : if (!name)
335 : {
336 21699222 : res = fold_range_internal (r, s, NULL_TREE);
337 21699222 : if (res && is_a <gcond *> (s))
338 : {
339 : // Update any exports in the cache if this is a gimple cond statement.
340 21653848 : tree exp;
341 21653848 : basic_block bb = gimple_bb (s);
342 65031107 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, exp)
343 43377259 : m_cache.propagate_updated_value (exp, bb);
344 : }
345 : }
346 370867743 : else if (!gimple_range_ssa_p (name))
347 36237312 : res = get_tree_range (r, name, NULL);
348 : else
349 : {
350 334630431 : bool current;
351 : // Check if the stmt has already been processed.
352 334630431 : if (m_cache.get_global_range (r, name, current))
353 : {
354 : // If it isn't stale, use this cached value.
355 229735969 : if (current)
356 : {
357 222957694 : if (idx)
358 0 : tracer.trailer (idx, " cached", true, name, r);
359 222957694 : return true;
360 : }
361 : }
362 : else
363 104894462 : prefill_stmt_dependencies (name);
364 :
365 : // Calculate a new value.
366 111672737 : value_range tmp (TREE_TYPE (name));
367 111672737 : 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 111672737 : bool changed = r.intersect (tmp);
373 111672737 : m_cache.set_global_range (name, r, changed);
374 111672737 : res = true;
375 111672737 : }
376 :
377 169609271 : 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 140630469 : gimple_ranger::prefill_name (tree name)
387 : {
388 140630469 : if (!gimple_range_ssa_p (name))
389 : return false;
390 :
391 103387276 : unsigned v = SSA_NAME_VERSION (name);
392 :
393 : // Already active cycle. Use seeded value and do not chase it.
394 103387276 : if (bitmap_bit_p (m_active_prefill, v))
395 : return false;
396 :
397 : // Process only range-ops and PHIs.
398 93973820 : gimple *stmt = SSA_NAME_DEF_STMT (name);
399 93973820 : if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt))
400 : return false;
401 :
402 : // Already calculated.
403 64089891 : value_range r (TREE_TYPE (name));
404 64089891 : if (m_cache.get_global_range (r, name))
405 : return false;
406 :
407 24946246 : bool current;
408 : // Seed the initial cache value to avoid cycles.
409 24946246 : m_cache.get_global_range (r, name, current);
410 :
411 24946246 : bitmap_set_bit (m_active_prefill, v);
412 24946246 : m_prefill_stack.safe_push ({ name, 0 });
413 24946246 : return true;
414 64089891 : }
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 104894462 : gimple_ranger::prefill_stmt_dependencies (tree ssa)
425 : {
426 104894462 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
427 : return;
428 :
429 94500639 : gimple *stmt = SSA_NAME_DEF_STMT (ssa);
430 94500639 : gcc_checking_assert (stmt);
431 94500639 : if (!gimple_bb (stmt))
432 : return;
433 :
434 : // Process only range-ops and PHIs.
435 94500638 : if (!gimple_range_op_handler::supported_p (stmt) && !is_a<gphi *> (stmt))
436 : return;
437 :
438 52422325 : unsigned idx = tracer.header ("ROS dependence fill\n");
439 :
440 52422325 : bitmap_set_bit (m_active_prefill, SSA_NAME_VERSION (ssa));
441 52422325 : m_prefill_stack.safe_push ({ ssa, 0 });
442 :
443 154737142 : while (!m_prefill_stack.is_empty ())
444 : {
445 102314817 : prefill_frame &frame = m_prefill_stack.last ();
446 102314817 : tree name = frame.name;
447 102314817 : stmt = SSA_NAME_DEF_STMT (name);
448 :
449 : // Print the ROS (Range Of Stmt) data the first time it is seen.
450 102314817 : 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 102314817 : if (gphi *phi = dyn_cast <gphi *> (stmt))
459 : {
460 63143236 : while (frame.next_op < gimple_phi_num_args (phi))
461 : {
462 44203166 : tree op = gimple_phi_arg_def (phi, frame.next_op++);
463 44203166 : if (prefill_name (op))
464 : break;
465 : }
466 : }
467 : else
468 : {
469 71404360 : gimple_range_op_handler handler (stmt);
470 246445625 : while (handler && frame.next_op < 2)
471 : {
472 116612764 : tree op = (frame.next_op++ == 0) ? handler.operand2 ()
473 58306382 : : handler.operand1 ();
474 116612764 : if (!op)
475 20185461 : continue;
476 96427303 : if (prefill_name (op))
477 : break;
478 : }
479 : }
480 :
481 : // If the same name is not top of stack, keep processing.
482 102314817 : if (m_prefill_stack.last ().name != name)
483 77226674 : continue;
484 :
485 : // All dependencies have been handled. Pop and fold.
486 77368571 : m_prefill_stack.pop ();
487 77368571 : bitmap_clear_bit (m_active_prefill, SSA_NAME_VERSION (name));
488 :
489 : // Do not fold the original request. The caller will calculate it.
490 77368571 : if (name == ssa)
491 52280428 : continue;
492 :
493 25088143 : value_range r (TREE_TYPE (name));
494 25088143 : fold_range_internal (r, stmt, name);
495 :
496 25088143 : value_range tmp (TREE_TYPE (name));
497 25088143 : m_cache.get_global_range (tmp, name);
498 25088143 : bool changed = tmp.intersect (r);
499 25088143 : m_cache.set_global_range (name, tmp, changed);
500 25088143 : }
501 :
502 52422325 : 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 258712994 : gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
514 : {
515 258712994 : gimple *stmt = gsi_stmt (*gsi);
516 258712994 : current_bb = gimple_bb (stmt);
517 258712994 : bool ret = ::fold_stmt (gsi, valueize);
518 258712994 : current_bb = NULL;
519 258712994 : 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 274233913 : gimple_ranger::register_inferred_ranges (gimple *s)
527 : {
528 : // First, export the LHS if it is a new global range.
529 274233913 : tree lhs = gimple_get_lhs (s);
530 274233913 : if (lhs)
531 : {
532 91074978 : value_range tmp (TREE_TYPE (lhs));
533 91074978 : if (range_of_stmt (tmp, s, lhs) && !tmp.varying_p ())
534 18780071 : set_range_info (lhs, tmp);
535 91074978 : }
536 274233913 : m_cache.apply_inferred_ranges (s);
537 274233913 : }
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 31718820 : gimple_ranger::register_transitive_inferred_ranges (basic_block bb)
545 : {
546 : // Return if there are no inferred ranges in BB.
547 31718820 : if (!infer_oracle ().has_range_p (bb))
548 : return;
549 :
550 2560395 : 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 51164752 : for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
555 46043962 : gsi_next (&si))
556 : {
557 46043962 : gimple *s = gsi_stmt (si);
558 46043962 : tree lhs = gimple_get_lhs (s);
559 : // If the LHS already has an inferred effect, leave it be.
560 46043962 : if (!gimple_range_ssa_p (lhs) || infer_oracle ().has_range_p (bb, lhs))
561 36566654 : continue;
562 : // Pick up global value.
563 9477308 : value_range g (TREE_TYPE (lhs));
564 9477308 : 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 9477308 : value_range r (TREE_TYPE (lhs));
570 9477308 : r.set_undefined ();
571 9477308 : tree name1 = gori_ssa ()->depend1 (lhs);
572 9477308 : tree name2 = gori_ssa ()->depend2 (lhs);
573 4790347 : if ((name1 && infer_oracle ().has_range_p (bb, name1))
574 13950681 : || (name2 && infer_oracle ().has_range_p (bb, name2)))
575 : {
576 : // Check if folding S produces a different result.
577 637870 : 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 9477308 : }
585 : }
586 :
587 : // Indicate NAME should have its range recalculated next time it is used.
588 :
589 : void
590 12602506 : gimple_ranger::update_range_info (tree name)
591 : {
592 12602506 : m_cache.mark_stale (name);
593 12602506 : }
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 11655022 : gimple_ranger::update_range_info (tree name, const vrange &r)
600 : {
601 11655022 : value_range current (TREE_TYPE (name));
602 11655022 : m_cache.get_global_range (current, name);
603 11655022 : if (current.intersect (r))
604 : {
605 236837 : m_cache.set_global_range (name, current, true);
606 236837 : m_cache.mark_stale (name);
607 : }
608 11655022 : }
609 :
610 : // Reset range information for NAME.
611 :
612 : void
613 440 : gimple_ranger::reset_range_info (tree name)
614 : {
615 : // Clearing the cache will also clear all the shared oracles.
616 440 : m_cache.reset_range_info (name);
617 440 : }
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 2125077 : gimple_ranger::export_global_ranges ()
624 : {
625 2125077 : if (dump_file)
626 : {
627 : /* Print the header only when there's something else
628 : to print below. */
629 294 : fprintf (dump_file, "Exporting new global ranges:\n");
630 294 : fprintf (dump_file, "============================\n");
631 : }
632 110400759 : for (unsigned x = 1; x < num_ssa_names; x++)
633 : {
634 108275682 : tree name = ssa_name (x);
635 108275682 : if (!name)
636 30443927 : continue;
637 77831755 : value_range r (TREE_TYPE (name));
638 77831755 : if (name && !SSA_NAME_IN_FREE_LIST (name) && gimple_range_ssa_p (name)
639 44681794 : && m_cache.get_global_range (r, name) && !r.varying_p())
640 12806819 : set_range_info (name, r);
641 77831755 : }
642 2125077 : if (dump_file)
643 294 : fprintf (dump_file, "========= Done =============\n");
644 2125077 : }
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 22515134 : enable_ranger (struct function *fun, bool use_imm_uses)
748 : {
749 22515134 : gimple_ranger *r;
750 :
751 22515134 : r = new gimple_ranger (use_imm_uses);
752 22515134 : range_query *q = set_range_query (fun, r);
753 :
754 : // Ranger should be the first and only instance.
755 22515134 : gcc_checking_assert (q == get_global_range_query ());
756 22515134 : return r;
757 : }
758 :
759 : /* Destroy and release the ranger instance associated with function FUN
760 : and replace it the global ranger. */
761 :
762 : void
763 22515134 : disable_ranger (struct function *fun)
764 : {
765 : // Ensure this is the query being removed.
766 22515134 : range_query *q = set_range_query (fun, get_global_range_query ());
767 22515134 : delete q;
768 22515134 : }
769 :
770 : // ---------------------------------------------------------------------------
771 : //
772 : // The DOM based ranger assumes a single DOM walk through the IL, and is
773 : // used by the fvrp_folder as a fast VRP.
774 : // During the dom walk, the current block has an ssa_lazy_cache pointer
775 : // m_bb[bb->index] which represents all the cumulative contextual ranges
776 : // active in the block.
777 : // These ranges are pure static ranges generated by branches, and must be
778 : // combined with the equivlaent global range to produce the final range.
779 : // A NULL pointer means there are no contextual ranges.
780 :
781 : // Create a DOM based ranger for use by a DOM walk pass.
782 :
783 9 : dom_ranger::dom_ranger () : m_global ()
784 : {
785 9 : bitmap_obstack_initialize (&m_bitmaps);
786 9 : m_freelist.create (0);
787 9 : m_freelist.truncate (0);
788 9 : m_bb.create (0);
789 9 : m_bb.safe_grow_cleared (last_basic_block_for_fn (cfun));
790 9 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
791 0 : tracer.enable_trace ();
792 9 : }
793 :
794 : // Dispose of a DOM ranger.
795 :
796 9 : dom_ranger::~dom_ranger ()
797 : {
798 9 : if (dump_file && (dump_flags & TDF_DETAILS))
799 : {
800 2 : fprintf (dump_file, "Non-varying global ranges:\n");
801 2 : fprintf (dump_file, "=========================:\n");
802 2 : m_global.dump (dump_file);
803 : }
804 9 : m_bb.release ();
805 9 : m_freelist.release ();
806 9 : bitmap_obstack_release (&m_bitmaps);
807 9 : }
808 :
809 : // Implement range of EXPR on stmt S, and return it in R.
810 : // Return false if no range can be calculated.
811 :
812 : bool
813 4638 : dom_ranger::range_of_expr (vrange &r, tree expr, gimple *s)
814 : {
815 4638 : if (!dbg_cnt (ranger_cnt))
816 0 : return get_global_range_query ()->range_of_expr (r, expr, s);
817 :
818 4638 : unsigned idx;
819 4638 : if (!gimple_range_ssa_p (expr))
820 1108 : return get_tree_range (r, expr, s);
821 :
822 3530 : if ((idx = tracer.header ("range_of_expr ")))
823 : {
824 0 : print_generic_expr (dump_file, expr, TDF_SLIM);
825 0 : if (s)
826 : {
827 0 : fprintf (dump_file, " at ");
828 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
829 : }
830 : else
831 0 : fprintf (dump_file, "\n");
832 : }
833 :
834 : // If there is a statement, return the range in that statements block.
835 3530 : if (s)
836 3516 : range_in_bb (r, gimple_bb (s), expr);
837 : else
838 14 : m_global.range_of_expr (r, expr, s);
839 :
840 3530 : if (idx)
841 0 : tracer.trailer (idx, " ", true, expr, r);
842 : return true;
843 : }
844 :
845 : // Return the range of EXPR on edge E in R.
846 : // Return false if no range can be calculated.
847 :
848 : bool
849 46 : dom_ranger::range_on_edge (vrange &r, edge e, tree expr)
850 : {
851 46 : if (!dbg_cnt (ranger_cnt))
852 0 : return get_global_range_query ()->range_on_edge (r, e, expr);
853 :
854 46 : if (!gimple_range_ssa_p (expr))
855 7 : return get_tree_range (r, expr, NULL, NULL, NULL, e);
856 :
857 39 : basic_block bb = e->src;
858 39 : unsigned idx;
859 39 : if ((idx = tracer.header ("range_on_edge ")))
860 : {
861 0 : fprintf (dump_file, "%d->%d for ",e->src->index, e->dest->index);
862 0 : print_generic_expr (dump_file, expr, TDF_SLIM);
863 0 : fputc ('\n',dump_file);
864 : }
865 :
866 39 : range_in_bb (r, bb, expr);
867 39 : value_range vr(TREE_TYPE (expr));
868 39 : if (gori_name_on_edge (vr, expr, e, this))
869 4 : r.intersect (vr);
870 :
871 39 : if (idx)
872 0 : tracer.trailer (idx, " ", true, expr, r);
873 39 : return true;
874 39 : }
875 :
876 : // Return the range of NAME as it exists at the end of block BB in R.
877 :
878 : void
879 3555 : dom_ranger::range_in_bb (vrange &r, basic_block bb, tree name)
880 : {
881 : // Start with the global value.
882 3555 : m_global.range_of_expr (r, name);
883 :
884 : // If there is a contextual range, intersect it with the global range
885 3555 : ssa_lazy_cache *context = m_bb[bb->index];
886 3555 : if (context && context->has_range (name))
887 : {
888 27 : value_range cr (TREE_TYPE (name));
889 27 : context->get_range (cr, name);
890 27 : r.intersect (cr);
891 27 : }
892 3555 : }
893 :
894 : // Calculate the range of NAME, as the def of stmt S and return it in R.
895 : // Return FALSE if no range can be calculated.
896 : // Also set the global range for NAME as this should only be called within
897 : // the def block during a DOM walk.
898 :
899 : bool
900 824 : dom_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
901 : {
902 824 : if (!dbg_cnt (ranger_cnt))
903 0 : return get_global_range_query ()->range_of_stmt (r, s, name);
904 :
905 824 : unsigned idx;
906 824 : bool ret;
907 824 : if (!name)
908 424 : name = gimple_get_lhs (s);
909 :
910 824 : if (name && !gimple_range_ssa_p (name))
911 3 : return get_tree_range (r, name, NULL);
912 :
913 821 : if ((idx = tracer.header ("range_of_stmt ")))
914 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
915 :
916 : // Its already been calculated.
917 821 : if (name && m_global.has_range (name))
918 : {
919 391 : ret = m_global.range_of_expr (r, name, s);
920 391 : if (idx)
921 0 : tracer.trailer (idx, " Already had value ", ret, name, r);
922 : return ret;
923 : }
924 :
925 : // Fold using a fur_depend object so that relations are registered.
926 430 : fold_using_range f;
927 430 : fur_depend src (s, this);
928 430 : ret = f.fold_stmt (r, s, src, name);
929 :
930 : // If there is a new calculated range and it is not varying, set
931 : // a global range.
932 430 : if (ret && name && m_global.merge_range (name, r) && !r.varying_p ())
933 337 : set_range_info (name, r);
934 :
935 430 : if (idx)
936 0 : tracer.trailer (idx, " ", ret, name, r);
937 : return ret;
938 : }
939 :
940 : // Preprocess block BB. If there is a single predecessor, start with any
941 : // contextual ranges on the incoming edge, otherwise the initial list
942 : // of ranges i empty for this block. Then Merge in any contextual ranges
943 : // from the dominator block. This will become the contextual ranges
944 : // that apply to this block.
945 :
946 : void
947 37 : dom_ranger::pre_bb (basic_block bb)
948 : {
949 37 : if (dump_file && (dump_flags & TDF_DETAILS))
950 15 : fprintf (dump_file, "#FVRP entering BB %d\n", bb->index);
951 :
952 37 : m_bb[bb->index] = NULL;
953 37 : basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
954 :
955 37 : ssa_lazy_cache *e_cache;
956 37 : if (!m_freelist.is_empty ())
957 25 : e_cache = m_freelist.pop ();
958 : else
959 12 : e_cache = new ssa_lazy_cache (&m_bitmaps);
960 37 : gcc_checking_assert (e_cache->empty_p ());
961 :
962 : // If there is a single pred, check if there are any ranges on
963 : // the edge and start with those.
964 37 : if (single_pred_p (bb))
965 : {
966 20 : gori_on_edge (*e_cache, EDGE_PRED (bb, 0), this);
967 20 : if (!e_cache->empty_p () && dump_file && (dump_flags & TDF_DETAILS))
968 : {
969 10 : fprintf (dump_file, "\nEdge ranges BB %d->%d\n",
970 5 : EDGE_PRED (bb, 0)->src->index, bb->index);
971 5 : e_cache->dump(dump_file);
972 : }
973 : }
974 : // If the dominator had any ranges registered, integrate those.
975 37 : if (dom_bb && m_bb [dom_bb->index])
976 7 : e_cache->merge (*(m_bb[dom_bb->index]));
977 :
978 : // If there are no ranges, this block has no contextual ranges.
979 37 : if (e_cache->empty_p ())
980 23 : m_freelist.safe_push (e_cache);
981 : else
982 14 : m_bb[bb->index] = e_cache;
983 :
984 37 : if (dump_file && (dump_flags & TDF_DETAILS))
985 : {
986 15 : if (m_bb[bb->index])
987 : {
988 9 : fprintf (dump_file, "all contextual ranges active:\n");
989 9 : m_bb[bb->index]->dump (dump_file);
990 : }
991 : else
992 6 : fprintf (dump_file, " NO contextual ranges active:\n");
993 : }
994 37 : }
995 :
996 : // Perform any post block processing.
997 :
998 : void
999 37 : dom_ranger::post_bb (basic_block bb)
1000 : {
1001 37 : if (dump_file && (dump_flags & TDF_DETAILS))
1002 15 : fprintf (dump_file, "#FVRP POST BB %d\n", bb->index);
1003 : // If there were contextual ranges, clear them and put the
1004 : // object on the freelist.
1005 37 : if (m_bb[bb->index])
1006 : {
1007 14 : m_bb[bb->index]->clear ();
1008 14 : m_freelist.safe_push (m_bb[bb->index]);
1009 14 : m_bb[bb->index] = NULL;
1010 : }
1011 37 : }
|
