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 27881050 : gimple_ranger::gimple_ranger (bool use_imm_uses) :
41 55762100 : non_executable_edge_flag (cfun),
42 27881050 : m_cache (non_executable_edge_flag, use_imm_uses),
43 27881050 : tracer (""),
44 27881050 : current_bb (NULL)
45 : {
46 : // Share the oracle from the cache.
47 27881050 : share_query (m_cache);
48 27881050 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
49 0 : tracer.enable_trace ();
50 27881050 : m_stmt_list.create (0);
51 55762100 : m_stmt_list.safe_grow (num_ssa_names);
52 27881050 : m_stmt_list.truncate (0);
53 :
54 : // Ensure the not_executable flag is clear everywhere.
55 27881050 : if (flag_checking)
56 : {
57 27880660 : basic_block bb;
58 339312195 : FOR_ALL_BB_FN (bb, cfun)
59 : {
60 311431535 : edge_iterator ei;
61 311431535 : edge e;
62 695952510 : FOR_EACH_EDGE (e, ei, bb->succs)
63 384520975 : gcc_checking_assert ((e->flags & non_executable_edge_flag) == 0);
64 : }
65 : }
66 27881050 : }
67 :
68 55761626 : gimple_ranger::~gimple_ranger ()
69 : {
70 27881049 : m_stmt_list.release ();
71 55761626 : }
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 555861628 : gimple_ranger::range_of_expr (vrange &r, tree expr, gimple *stmt)
83 : {
84 555861628 : unsigned idx;
85 555861628 : if (!gimple_range_ssa_p (expr))
86 90534361 : return get_tree_range (r, expr, stmt);
87 :
88 465327267 : 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 465327267 : if (!stmt)
103 : {
104 43719111 : 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 43719111 : if (!m_cache.get_global_range (r, expr))
108 : {
109 4634505 : gimple *s = SSA_NAME_DEF_STMT (expr);
110 : // Calculate a range for S if it is safe to do so.
111 4634505 : if (s && gimple_bb (s) && gimple_get_lhs (s) == expr)
112 4401552 : 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 39317559 : if (current_bb && m_cache.block_range (tmp, current_bb, expr, false))
117 : {
118 1036710 : r.intersect (tmp);
119 1036710 : char str[80];
120 1036710 : sprintf (str, "picked up range from bb %d\n",current_bb->index);
121 1036710 : if (idx)
122 0 : tracer.print (idx, str);
123 : }
124 43719111 : }
125 : // For a debug stmt, pick the best value currently available, do not
126 : // trigger new value calculations. PR 100781.
127 421608156 : else if (is_gimple_debug (stmt))
128 41625050 : m_cache.range_of_expr (r, expr, stmt);
129 : else
130 : {
131 379983106 : basic_block bb = gimple_bb (stmt);
132 379983106 : 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 379983106 : 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 233121219 : if (m_cache.get_global_range (r, expr))
140 197753410 : m_cache.block_range (r, bb, expr, false);
141 : else
142 35367809 : range_of_stmt (r, def_stmt, expr);
143 : }
144 : // Otherwise OP comes from outside this block, use range on entry.
145 : else
146 146861887 : range_on_entry (r, bb, expr);
147 : }
148 460925715 : 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 181065415 : gimple_ranger::range_on_entry (vrange &r, basic_block bb, tree name)
157 : {
158 181065415 : if (!gimple_range_ssa_p (name))
159 0 : return get_tree_range (r, name, NULL, bb, NULL);
160 :
161 181065415 : value_range entry_range (TREE_TYPE (name));
162 :
163 181065415 : unsigned idx;
164 181065415 : 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 181065415 : 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 181065415 : if (bb && m_cache.block_range (entry_range, bb, name))
175 119020279 : r.intersect (entry_range);
176 :
177 181065415 : if (idx)
178 0 : tracer.trailer (idx, "range_on_entry", true, name, r);
179 181065415 : return true;
180 181065415 : }
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 64410222 : gimple_ranger::range_on_exit (vrange &r, basic_block bb, tree name)
187 : {
188 64410222 : if (!gimple_range_ssa_p (name))
189 0 : return get_tree_range (r, name, NULL, NULL, bb);
190 :
191 64410222 : unsigned idx;
192 64410222 : 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 64410222 : gimple *s = SSA_NAME_DEF_STMT (name);
199 64410222 : 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 64410222 : if (def_bb != bb)
203 : {
204 29936688 : if (bb->flags & BB_RTL)
205 : s = NULL;
206 : else
207 29921626 : s = last_nondebug_stmt (bb);
208 : }
209 : // If there is no statement provided, get the range_on_entry for this block.
210 29921626 : if (s)
211 51216673 : range_of_expr (r, name, s);
212 : else
213 13193549 : range_on_entry (r, bb, name);
214 64410222 : gcc_checking_assert (r.undefined_p ()
215 : || range_compatible_p (r.type (), TREE_TYPE (name)));
216 :
217 64410222 : 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 79081898 : gimple_ranger::range_on_edge (vrange &r, edge e, tree name)
226 : {
227 79081898 : value_range edge_range (TREE_TYPE (name));
228 :
229 79081898 : if (!r.supports_type_p (TREE_TYPE (name)))
230 : return false;
231 :
232 : // Do not process values along abnormal edges.
233 79081898 : if (e->flags & EDGE_ABNORMAL)
234 77 : return get_tree_range (r, name, NULL);
235 :
236 79081821 : unsigned idx;
237 79081821 : 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 79081821 : if ((e->flags & non_executable_edge_flag))
245 : {
246 238608 : r.set_undefined ();
247 238608 : if (idx)
248 0 : tracer.trailer (idx, "range_on_edge [Unexecutable] ", true,
249 : name, r);
250 238608 : return true;
251 : }
252 :
253 78843213 : bool res = true;
254 78843213 : if (!gimple_range_ssa_p (name))
255 14432991 : res = get_tree_range (r, name, NULL, NULL, NULL, e);
256 : else
257 : {
258 64410222 : range_on_exit (r, e->src, name);
259 : // If this is not an abnormal edge, check for a non-null exit .
260 64410222 : if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
261 64114960 : infer_oracle ().maybe_adjust_range (r, name, e->src);
262 64410222 : 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 64410222 : if (m_cache.range_on_edge (edge_range, e, name))
267 64410222 : r.intersect (edge_range);
268 : }
269 :
270 78843213 : if (idx)
271 0 : tracer.trailer (idx, "range_on_edge", res, name, r);
272 : return res;
273 79081898 : }
274 :
275 : // fold_range wrapper for range_of_stmt to use as an internal client.
276 :
277 : bool
278 159781526 : gimple_ranger::fold_range_internal (vrange &r, gimple *s, tree name)
279 : {
280 159781526 : fold_using_range f;
281 159781526 : fur_depend src (s, this, &m_cache);
282 159781526 : 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 375116364 : gimple_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
293 : {
294 375116364 : bool res;
295 375116364 : r.set_undefined ();
296 :
297 375116364 : unsigned idx;
298 375116364 : 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 375116364 : if (!name)
307 25646137 : name = gimple_get_lhs (s);
308 :
309 : // If no name, simply call the base routine.
310 25646137 : if (!name)
311 : {
312 21244585 : res = fold_range_internal (r, s, NULL_TREE);
313 21244585 : if (res && is_a <gcond *> (s))
314 : {
315 : // Update any exports in the cache if this is a gimple cond statement.
316 21199270 : tree exp;
317 21199270 : basic_block bb = gimple_bb (s);
318 63710110 : FOR_EACH_GORI_EXPORT_NAME (gori_ssa (), bb, exp)
319 42510840 : m_cache.propagate_updated_value (exp, bb);
320 : }
321 : }
322 353871779 : else if (!gimple_range_ssa_p (name))
323 34404978 : res = get_tree_range (r, name, NULL);
324 : else
325 : {
326 319466801 : bool current;
327 : // Check if the stmt has already been processed.
328 319466801 : if (m_cache.get_global_range (r, name, current))
329 : {
330 : // If it isn't stale, use this cached value.
331 217099680 : if (current)
332 : {
333 205591289 : if (idx)
334 0 : tracer.trailer (idx, " cached", true, name, r);
335 205591289 : return true;
336 : }
337 : }
338 : else
339 102367121 : prefill_stmt_dependencies (name);
340 :
341 : // Calculate a new value.
342 113875512 : value_range tmp (TREE_TYPE (name));
343 113875512 : 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 113875512 : bool changed = r.intersect (tmp);
349 113875512 : m_cache.set_global_range (name, r, changed);
350 113875512 : res = true;
351 113875512 : }
352 :
353 169525075 : 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 137896314 : gimple_ranger::prefill_name (vrange &r, tree name)
364 : {
365 137896314 : if (!gimple_range_ssa_p (name))
366 : return;
367 101207359 : gimple *stmt = SSA_NAME_DEF_STMT (name);
368 101207359 : 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 71955321 : if (!m_cache.get_global_range (r, name))
373 : {
374 24661429 : bool current;
375 : // Set the global cache value and mark as alway_current.
376 24661429 : m_cache.get_global_range (r, name, current);
377 24661429 : 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 102367121 : gimple_ranger::prefill_stmt_dependencies (tree ssa)
386 : {
387 102367121 : if (SSA_NAME_IS_DEFAULT_DEF (ssa))
388 : return;
389 :
390 92147288 : unsigned idx;
391 92147288 : gimple *stmt = SSA_NAME_DEF_STMT (ssa);
392 92147288 : gcc_checking_assert (stmt);
393 92147288 : if (!gimple_bb (stmt))
394 : return;
395 :
396 : // Only pre-process range-ops and phis.
397 92147286 : 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 51088901 : unsigned start = m_stmt_list.length ();
402 51088901 : m_stmt_list.safe_push (ssa);
403 :
404 51088901 : idx = tracer.header ("ROS dependence fill\n");
405 :
406 : // Loop until back at the start point.
407 202589561 : while (m_stmt_list.length () > start)
408 : {
409 151500660 : 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 151500660 : if (!name)
413 : {
414 : // Pop the NULL, then pop the name.
415 75750330 : m_stmt_list.pop ();
416 75750330 : name = m_stmt_list.pop ();
417 : // Don't fold initial request, it will be calculated upon return.
418 75750330 : if (m_stmt_list.length () > start)
419 : {
420 : // Fold and save the value for NAME.
421 24661429 : stmt = SSA_NAME_DEF_STMT (name);
422 24661429 : value_range r (TREE_TYPE (name));
423 24661429 : fold_range_internal (r, stmt, name);
424 : // Make sure we don't lose any current global info.
425 24661429 : value_range tmp (TREE_TYPE (name));
426 24661429 : m_cache.get_global_range (tmp, name);
427 24661429 : bool changed = tmp.intersect (r);
428 24661429 : m_cache.set_global_range (name, tmp, changed);
429 24661429 : }
430 75750330 : continue;
431 75750330 : }
432 :
433 : // Add marker indicating previous NAME in list should be folded
434 : // when we get to this NULL.
435 75750330 : m_stmt_list.safe_push (NULL_TREE);
436 75750330 : stmt = SSA_NAME_DEF_STMT (name);
437 :
438 75750330 : 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 75750330 : gphi *phi = dyn_cast <gphi *> (stmt);
447 75750330 : if (phi)
448 : {
449 18952205 : value_range r (TREE_TYPE (gimple_phi_result (phi)));
450 62831558 : for (unsigned x = 0; x < gimple_phi_num_args (phi); x++)
451 43879353 : prefill_name (r, gimple_phi_arg_def (phi, x));
452 18952205 : }
453 : else
454 : {
455 56798125 : gimple_range_op_handler handler (stmt);
456 56798125 : if (handler)
457 : {
458 56680274 : tree op = handler.operand2 ();
459 56680274 : if (op)
460 : {
461 37337527 : value_range r (TREE_TYPE (op));
462 37337527 : prefill_name (r, op);
463 37337527 : }
464 56680274 : op = handler.operand1 ();
465 56680274 : if (op)
466 : {
467 56679434 : value_range r (TREE_TYPE (op));
468 56679434 : prefill_name (r, op);
469 56679434 : }
470 : }
471 : }
472 : }
473 51088901 : 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 237658815 : gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
486 : {
487 237658815 : gimple *stmt = gsi_stmt (*gsi);
488 237658815 : current_bb = gimple_bb (stmt);
489 237658815 : bool ret = ::fold_stmt (gsi, valueize);
490 237658815 : current_bb = NULL;
491 237658815 : 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 252911694 : gimple_ranger::register_inferred_ranges (gimple *s)
499 : {
500 : // First, export the LHS if it is a new global range.
501 252911694 : tree lhs = gimple_get_lhs (s);
502 252911694 : if (lhs)
503 : {
504 87507394 : value_range tmp (TREE_TYPE (lhs));
505 87507394 : if (range_of_stmt (tmp, s, lhs) && !tmp.varying_p ())
506 18244035 : set_range_info (lhs, tmp);
507 87507394 : }
508 252911694 : m_cache.apply_inferred_ranges (s);
509 252911694 : }
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 30735921 : gimple_ranger::register_transitive_inferred_ranges (basic_block bb)
517 : {
518 : // Return if there are no inferred ranges in BB.
519 30735921 : if (!infer_oracle ().has_range_p (bb))
520 : return;
521 :
522 2515970 : 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 47913057 : for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
527 42881117 : gsi_next (&si))
528 : {
529 42881117 : gimple *s = gsi_stmt (si);
530 42881117 : tree lhs = gimple_get_lhs (s);
531 : // If the LHS already has an inferred effect, leave it be.
532 42881117 : if (!gimple_range_ssa_p (lhs) || infer_oracle ().has_range_p (bb, lhs))
533 33603206 : continue;
534 : // Pick up global value.
535 9277911 : value_range g (TREE_TYPE (lhs));
536 9277911 : 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 9277911 : value_range r (TREE_TYPE (lhs));
542 9277911 : r.set_undefined ();
543 9277911 : tree name1 = gori_ssa ()->depend1 (lhs);
544 9277911 : tree name2 = gori_ssa ()->depend2 (lhs);
545 4668719 : if ((name1 && infer_oracle ().has_range_p (bb, name1))
546 13644441 : || (name2 && infer_oracle ().has_range_p (bb, name2)))
547 : {
548 : // Check if folding S produces a different result.
549 609250 : if (fold_range (r, s, this) && g != r)
550 : {
551 19875 : gimple_infer_range ir (lhs, r);
552 19875 : infer_oracle ().add_ranges (s, ir);
553 19875 : m_cache.register_inferred_value (r, lhs, bb);
554 19875 : }
555 : }
556 9277911 : }
557 : }
558 :
559 : // This is called to update ranger's concept of a global value for NAME
560 : // with range R by an outside entity.
561 :
562 : void
563 11419816 : gimple_ranger::update_range_info (tree name, const vrange &r)
564 : {
565 11419816 : value_range current (TREE_TYPE (name));
566 11419816 : m_cache.get_global_range (current, name);
567 11419816 : if (current.intersect (r))
568 233166 : m_cache.set_global_range (name, current, true);
569 11419816 : }
570 :
571 : // This routine will export whatever global ranges are known to GCC
572 : // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
573 :
574 : void
575 2083233 : gimple_ranger::export_global_ranges ()
576 : {
577 2083233 : if (dump_file)
578 : {
579 : /* Print the header only when there's something else
580 : to print below. */
581 296 : fprintf (dump_file, "Exporting new global ranges:\n");
582 296 : fprintf (dump_file, "============================\n");
583 : }
584 106811947 : for (unsigned x = 1; x < num_ssa_names; x++)
585 : {
586 104728714 : tree name = ssa_name (x);
587 104728714 : if (!name)
588 29350881 : continue;
589 75377833 : value_range r (TREE_TYPE (name));
590 75377833 : if (name && !SSA_NAME_IN_FREE_LIST (name) && gimple_range_ssa_p (name)
591 43370070 : && m_cache.get_global_range (r, name) && !r.varying_p())
592 12470553 : set_range_info (name, r);
593 75377833 : }
594 2083233 : if (dump_file)
595 296 : fprintf (dump_file, "========= Done =============\n");
596 2083233 : }
597 :
598 : // Print the known table values to file F.
599 :
600 : void
601 248 : gimple_ranger::dump_bb (FILE *f, basic_block bb)
602 : {
603 248 : unsigned x;
604 248 : edge_iterator ei;
605 248 : edge e;
606 248 : fprintf (f, "\n=========== BB %d ============\n", bb->index);
607 248 : m_cache.dump_bb (f, bb);
608 :
609 248 : ::dump_bb (f, bb, 4, TDF_NONE);
610 :
611 : // Now find any globals defined in this block.
612 12593 : for (x = 1; x < num_ssa_names; x++)
613 : {
614 12345 : tree name = ssa_name (x);
615 17557 : if (!gimple_range_ssa_p (name) || !SSA_NAME_DEF_STMT (name))
616 7133 : continue;
617 5212 : value_range range (TREE_TYPE (name));
618 5212 : if (gimple_bb (SSA_NAME_DEF_STMT (name)) == bb
619 5212 : && m_cache.get_global_range (range, name))
620 : {
621 288 : if (!range.varying_p ())
622 : {
623 153 : print_generic_expr (f, name, TDF_SLIM);
624 153 : fprintf (f, " : ");
625 153 : range.dump (f);
626 153 : fprintf (f, "\n");
627 : }
628 :
629 : }
630 5212 : }
631 :
632 : // And now outgoing edges, if they define anything.
633 609 : FOR_EACH_EDGE (e, ei, bb->succs)
634 : {
635 20946 : for (x = 1; x < num_ssa_names; x++)
636 : {
637 20585 : tree name = gimple_range_ssa_p (ssa_name (x));
638 20585 : if (!name || !gori ().has_edge_range_p (name, e))
639 19965 : continue;
640 :
641 620 : value_range range (TREE_TYPE (name));
642 620 : if (m_cache.range_on_edge (range, e, name))
643 : {
644 620 : gimple *s = SSA_NAME_DEF_STMT (name);
645 620 : value_range tmp_range (TREE_TYPE (name));
646 : // Only print the range if this is the def block, or
647 : // the on entry cache for either end of the edge is
648 : // set.
649 946 : if ((s && bb == gimple_bb (s)) ||
650 1082 : m_cache.block_range (tmp_range, bb, name, false) ||
651 136 : m_cache.block_range (tmp_range, e->dest, name, false))
652 : {
653 484 : if (!range.varying_p ())
654 : {
655 426 : fprintf (f, "%d->%d ", e->src->index,
656 426 : e->dest->index);
657 426 : char c = ' ';
658 426 : if (e->flags & EDGE_TRUE_VALUE)
659 204 : fprintf (f, " (T)%c", c);
660 222 : else if (e->flags & EDGE_FALSE_VALUE)
661 222 : fprintf (f, " (F)%c", c);
662 : else
663 0 : fprintf (f, " ");
664 426 : print_generic_expr (f, name, TDF_SLIM);
665 426 : fprintf(f, " : \t");
666 426 : range.dump(f);
667 426 : fprintf (f, "\n");
668 : }
669 : }
670 620 : }
671 620 : }
672 : }
673 248 : }
674 :
675 : // Print the known table values to file F.
676 :
677 : void
678 45 : gimple_ranger::dump (FILE *f)
679 : {
680 45 : basic_block bb;
681 :
682 293 : FOR_EACH_BB_FN (bb, cfun)
683 248 : dump_bb (f, bb);
684 :
685 45 : m_cache.dump (f);
686 45 : }
687 :
688 : void
689 0 : gimple_ranger::debug ()
690 : {
691 0 : dump (stderr);
692 0 : }
693 :
694 : /* Create a new ranger instance and associate it with function FUN.
695 : Each call must be paired with a call to disable_ranger to release
696 : resources. */
697 :
698 : gimple_ranger *
699 21162565 : enable_ranger (struct function *fun, bool use_imm_uses)
700 : {
701 21162565 : gimple_ranger *r;
702 :
703 21162565 : gcc_checking_assert (!fun->x_range_query);
704 21162565 : r = new gimple_ranger (use_imm_uses);
705 21162565 : fun->x_range_query = r;
706 :
707 21162565 : return r;
708 : }
709 :
710 : /* Destroy and release the ranger instance associated with function FUN
711 : and replace it the global ranger. */
712 :
713 : void
714 21162564 : disable_ranger (struct function *fun)
715 : {
716 21162564 : gcc_checking_assert (fun->x_range_query);
717 21162564 : delete fun->x_range_query;
718 21162564 : fun->x_range_query = NULL;
719 21162564 : }
720 :
721 : // ---------------------------------------------------------------------------
722 : //
723 : // The DOM based ranger assumes a single DOM walk through the IL, and is
724 : // used by the fvrp_folder as a fast VRP.
725 : // During the dom walk, the current block has an ssa_lazy_cache pointer
726 : // m_bb[bb->index] which represents all the cumulative contextual ranges
727 : // active in the block.
728 : // These ranges are pure static ranges generated by branches, and must be
729 : // combined with the equivlaent global range to produce the final range.
730 : // A NULL pointer means there are no contextual ranges.
731 :
732 : // Create a DOM based ranger for use by a DOM walk pass.
733 :
734 6 : dom_ranger::dom_ranger () : m_global ()
735 : {
736 6 : bitmap_obstack_initialize (&m_bitmaps);
737 6 : m_freelist.create (0);
738 6 : m_freelist.truncate (0);
739 6 : m_bb.create (0);
740 6 : m_bb.safe_grow_cleared (last_basic_block_for_fn (cfun));
741 6 : if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
742 0 : tracer.enable_trace ();
743 6 : }
744 :
745 : // Dispose of a DOM ranger.
746 :
747 6 : dom_ranger::~dom_ranger ()
748 : {
749 6 : if (dump_file && (dump_flags & TDF_DETAILS))
750 : {
751 2 : fprintf (dump_file, "Non-varying global ranges:\n");
752 2 : fprintf (dump_file, "=========================:\n");
753 2 : m_global.dump (dump_file);
754 : }
755 6 : m_bb.release ();
756 6 : m_freelist.release ();
757 6 : bitmap_obstack_release (&m_bitmaps);
758 6 : }
759 :
760 : // Implement range of EXPR on stmt S, and return it in R.
761 : // Return false if no range can be calculated.
762 :
763 : bool
764 494 : dom_ranger::range_of_expr (vrange &r, tree expr, gimple *s)
765 : {
766 494 : unsigned idx;
767 494 : if (!gimple_range_ssa_p (expr))
768 98 : return get_tree_range (r, expr, s);
769 :
770 396 : if ((idx = tracer.header ("range_of_expr ")))
771 : {
772 0 : print_generic_expr (dump_file, expr, TDF_SLIM);
773 0 : if (s)
774 : {
775 0 : fprintf (dump_file, " at ");
776 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
777 : }
778 : else
779 0 : fprintf (dump_file, "\n");
780 : }
781 :
782 : // If there is a statement, return the range in that statements block.
783 396 : if (s)
784 385 : range_in_bb (r, gimple_bb (s), expr);
785 : else
786 11 : m_global.range_of_expr (r, expr, s);
787 :
788 396 : if (idx)
789 0 : tracer.trailer (idx, " ", true, expr, r);
790 : return true;
791 : }
792 :
793 : // Return the range of EXPR on edge E in R.
794 : // Return false if no range can be calculated.
795 :
796 : bool
797 28 : dom_ranger::range_on_edge (vrange &r, edge e, tree expr)
798 : {
799 28 : if (!gimple_range_ssa_p (expr))
800 7 : return get_tree_range (r, expr, NULL, NULL, NULL, e);
801 :
802 21 : basic_block bb = e->src;
803 21 : unsigned idx;
804 21 : if ((idx = tracer.header ("range_on_edge ")))
805 : {
806 0 : fprintf (dump_file, "%d->%d for ",e->src->index, e->dest->index);
807 0 : print_generic_expr (dump_file, expr, TDF_SLIM);
808 0 : fputc ('\n',dump_file);
809 : }
810 :
811 21 : range_in_bb (r, bb, expr);
812 21 : value_range vr(TREE_TYPE (expr));
813 21 : if (gori_name_on_edge (vr, expr, e, this))
814 4 : r.intersect (vr);
815 :
816 21 : if (idx)
817 0 : tracer.trailer (idx, " ", true, expr, r);
818 21 : return true;
819 21 : }
820 :
821 : // Return the range of NAME as it exists at the end of block BB in R.
822 :
823 : void
824 406 : dom_ranger::range_in_bb (vrange &r, basic_block bb, tree name)
825 : {
826 : // Start with the global value.
827 406 : m_global.range_of_expr (r, name);
828 :
829 : // If there is a contextual range, intersect it with the global range
830 406 : ssa_lazy_cache *context = m_bb[bb->index];
831 406 : if (context && context->has_range (name))
832 : {
833 27 : value_range cr (TREE_TYPE (name));
834 27 : context->get_range (cr, name);
835 27 : r.intersect (cr);
836 27 : }
837 406 : }
838 :
839 : // Calculate the range of NAME, as the def of stmt S and return it in R.
840 : // Return FALSE if no range can be calculated.
841 : // Also set the global range for NAME as this should only be called within
842 : // the def block during a DOM walk.
843 :
844 : bool
845 263 : dom_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
846 : {
847 263 : unsigned idx;
848 263 : bool ret;
849 263 : if (!name)
850 142 : name = gimple_get_lhs (s);
851 :
852 263 : if (name && !gimple_range_ssa_p (name))
853 3 : return get_tree_range (r, name, NULL);
854 :
855 260 : if ((idx = tracer.header ("range_of_stmt ")))
856 0 : print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
857 :
858 : // Its already been calculated.
859 260 : if (name && m_global.has_range (name))
860 : {
861 115 : ret = m_global.range_of_expr (r, name, s);
862 115 : if (idx)
863 0 : tracer.trailer (idx, " Already had value ", ret, name, r);
864 115 : return ret;
865 : }
866 :
867 : // Fold using a fur_depend object so that relations are registered.
868 145 : fold_using_range f;
869 145 : fur_depend src (s, this);
870 145 : ret = f.fold_stmt (r, s, src, name);
871 :
872 : // If there is a new calculated range and it is not varying, set
873 : // a global range.
874 145 : if (ret && name && m_global.merge_range (name, r) && !r.varying_p ())
875 64 : set_range_info (name, r);
876 :
877 145 : if (idx)
878 0 : tracer.trailer (idx, " ", ret, name, r);
879 : return ret;
880 : }
881 :
882 : // Preprocess block BB. If there is a single predecessor, start with any
883 : // contextual ranges on the incoming edge, otherwise the initial list
884 : // of ranges i empty for this block. Then Merge in any contextual ranges
885 : // from the dominator block. Tihs will become the contextual ranges
886 : // that apply to this block.
887 :
888 : void
889 25 : dom_ranger::pre_bb (basic_block bb)
890 : {
891 25 : if (dump_file && (dump_flags & TDF_DETAILS))
892 15 : fprintf (dump_file, "#FVRP entering BB %d\n", bb->index);
893 :
894 25 : m_bb[bb->index] = NULL;
895 25 : basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
896 :
897 25 : ssa_lazy_cache *e_cache;
898 25 : if (!m_freelist.is_empty ())
899 16 : e_cache = m_freelist.pop ();
900 : else
901 9 : e_cache = new ssa_lazy_cache (&m_bitmaps);
902 25 : gcc_checking_assert (e_cache->empty_p ());
903 :
904 : // If there is a single pred, check if there are any ranges on
905 : // the edge and start with those.
906 25 : if (single_pred_p (bb))
907 : {
908 14 : gori_on_edge (*e_cache, EDGE_PRED (bb, 0), this);
909 14 : if (!e_cache->empty_p () && dump_file && (dump_flags & TDF_DETAILS))
910 : {
911 10 : fprintf (dump_file, "\nEdge ranges BB %d->%d\n",
912 5 : EDGE_PRED (bb, 0)->src->index, bb->index);
913 5 : e_cache->dump(dump_file);
914 : }
915 : }
916 : // If the dominator had any ranges registered, integrate those.
917 25 : if (dom_bb && m_bb [dom_bb->index])
918 7 : e_cache->merge (*(m_bb[dom_bb->index]));
919 :
920 : // If there are no ranges, this block has no contextual ranges.
921 25 : if (e_cache->empty_p ())
922 14 : m_freelist.safe_push (e_cache);
923 : else
924 11 : m_bb[bb->index] = e_cache;
925 :
926 25 : if (dump_file && (dump_flags & TDF_DETAILS))
927 : {
928 15 : if (m_bb[bb->index])
929 : {
930 9 : fprintf (dump_file, "all contextual ranges active:\n");
931 9 : m_bb[bb->index]->dump (dump_file);
932 : }
933 : else
934 6 : fprintf (dump_file, " NO contextual ranges active:\n");
935 : }
936 25 : }
937 :
938 : // Perform any post block processing.
939 :
940 : void
941 25 : dom_ranger::post_bb (basic_block bb)
942 : {
943 25 : if (dump_file && (dump_flags & TDF_DETAILS))
944 15 : fprintf (dump_file, "#FVRP POST BB %d\n", bb->index);
945 : // If there were contextual ranges, clear them and put the
946 : // object on the freelist.
947 25 : if (m_bb[bb->index])
948 : {
949 11 : m_bb[bb->index]->clear ();
950 11 : m_freelist.safe_push (m_bb[bb->index]);
951 11 : m_bb[bb->index] = NULL;
952 : }
953 25 : }
|
