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