1 /* Code for GIMPLE range related routines.
2 Copyright (C) 2019-2024 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
6 This file is part of GCC.
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)
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.
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/>. */
24 #include "coretypes.h"
29 #include "gimple-pretty-print.h"
30 #include "gimple-iterator.h"
32 #include "fold-const.h"
35 #include "tree-scalar-evolution.h"
36 #include "gimple-range.h"
37 #include "gimple-fold.h"
38 #include "gimple-walk.h"
40 gimple_ranger::gimple_ranger (bool use_imm_uses
) :
41 non_executable_edge_flag (cfun
),
42 m_cache (non_executable_edge_flag
, use_imm_uses
),
46 // If the cache has a relation oracle, use it.
47 m_oracle
= m_cache
.oracle ();
48 if (dump_file
&& (param_ranger_debug
& RANGER_DEBUG_TRACE
))
49 tracer
.enable_trace ();
50 m_stmt_list
.create (0);
51 m_stmt_list
.safe_grow (num_ssa_names
);
52 m_stmt_list
.truncate (0);
54 // Ensure the not_executable flag is clear everywhere.
58 FOR_ALL_BB_FN (bb
, cfun
)
62 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
63 gcc_checking_assert ((e
->flags
& non_executable_edge_flag
) == 0);
68 gimple_ranger::~gimple_ranger ()
70 m_stmt_list
.release ();
73 // Return a range_query which accesses just the known global values.
76 gimple_ranger::const_query ()
78 return m_cache
.const_query ();
82 gimple_ranger::range_of_expr (vrange
&r
, tree expr
, gimple
*stmt
)
85 if (!gimple_range_ssa_p (expr
))
86 return get_tree_range (r
, expr
, stmt
);
88 if ((idx
= tracer
.header ("range_of_expr(")))
90 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
91 fputs (")", dump_file
);
94 fputs (" at stmt ", dump_file
);
95 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
98 fputs ("\n", dump_file
);
101 // If there is no statement, just get the global value.
104 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 if (!m_cache
.get_global_range (r
, expr
))
109 gimple
*s
= SSA_NAME_DEF_STMT (expr
);
110 // Calculate a range for S if it is safe to do so.
111 if (s
&& gimple_bb (s
) && gimple_get_lhs (s
) == expr
)
112 return range_of_stmt (r
, s
);
114 // Pick up implied context information from the on-entry cache
115 // if current_bb is set. Do not attempt any new calculations.
116 if (current_bb
&& m_cache
.block_range (tmp
, current_bb
, expr
, false))
120 sprintf (str
, "picked up range from bb %d\n",current_bb
->index
);
122 tracer
.print (idx
, str
);
125 // For a debug stmt, pick the best value currently available, do not
126 // trigger new value calculations. PR 100781.
127 else if (is_gimple_debug (stmt
))
128 m_cache
.range_of_expr (r
, expr
, stmt
);
131 basic_block bb
= gimple_bb (stmt
);
132 gimple
*def_stmt
= SSA_NAME_DEF_STMT (expr
);
134 // If name is defined in this block, try to get an range from S.
135 if (def_stmt
&& gimple_bb (def_stmt
) == bb
)
137 // Declared in this block, if it has a global set, check for an
138 // override from a block walk, otherwise calculate it.
139 if (m_cache
.get_global_range (r
, expr
))
140 m_cache
.block_range (r
, bb
, expr
, false);
142 range_of_stmt (r
, def_stmt
, expr
);
144 // Otherwise OP comes from outside this block, use range on entry.
146 range_on_entry (r
, bb
, expr
);
149 tracer
.trailer (idx
, "range_of_expr", true, expr
, r
);
153 // Return the range of NAME on entry to block BB in R.
156 gimple_ranger::range_on_entry (vrange
&r
, basic_block bb
, tree name
)
158 if (!gimple_range_ssa_p (name
))
159 return get_tree_range (r
, name
, NULL
, bb
, NULL
);
161 Value_Range
entry_range (TREE_TYPE (name
));
164 if ((idx
= tracer
.header ("range_on_entry (")))
166 print_generic_expr (dump_file
, name
, TDF_SLIM
);
167 fprintf (dump_file
, ") to BB %d\n", bb
->index
);
170 // Start with any known range
171 range_of_stmt (r
, SSA_NAME_DEF_STMT (name
), name
);
173 // Now see if there is any on_entry value which may refine it.
174 if (m_cache
.block_range (entry_range
, bb
, name
))
175 r
.intersect (entry_range
);
178 tracer
.trailer (idx
, "range_on_entry", true, name
, r
);
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.
186 gimple_ranger::range_on_exit (vrange
&r
, basic_block bb
, tree name
)
188 if (!gimple_range_ssa_p (name
))
189 return get_tree_range (r
, name
, NULL
, NULL
, bb
);
192 if ((idx
= tracer
.header ("range_on_exit (")))
194 print_generic_expr (dump_file
, name
, TDF_SLIM
);
195 fprintf (dump_file
, ") from BB %d\n", bb
->index
);
198 gimple
*s
= SSA_NAME_DEF_STMT (name
);
199 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.
203 s
= last_nondebug_stmt (bb
);
204 // If there is no statement provided, get the range_on_entry for this block.
206 range_of_expr (r
, name
, s
);
208 range_on_entry (r
, bb
, name
);
209 gcc_checking_assert (r
.undefined_p ()
210 || range_compatible_p (r
.type (), TREE_TYPE (name
)));
213 tracer
.trailer (idx
, "range_on_exit", true, name
, r
);
217 // Calculate a range for NAME on edge E and return it in R.
220 gimple_ranger::range_on_edge (vrange
&r
, edge e
, tree name
)
222 Value_Range
edge_range (TREE_TYPE (name
));
224 if (!r
.supports_type_p (TREE_TYPE (name
)))
227 // Do not process values along abnormal edges.
228 if (e
->flags
& EDGE_ABNORMAL
)
229 return get_tree_range (r
, name
, NULL
);
232 if ((idx
= tracer
.header ("range_on_edge (")))
234 print_generic_expr (dump_file
, name
, TDF_SLIM
);
235 fprintf (dump_file
, ") on edge %d->%d\n", e
->src
->index
, e
->dest
->index
);
238 // Check to see if the edge is executable.
239 if ((e
->flags
& non_executable_edge_flag
))
243 tracer
.trailer (idx
, "range_on_edge [Unexecutable] ", true,
249 if (!gimple_range_ssa_p (name
))
250 res
= get_tree_range (r
, name
, NULL
);
253 range_on_exit (r
, e
->src
, name
);
254 // If this is not an abnormal edge, check for a non-null exit .
255 if ((e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
)) == 0)
256 m_cache
.m_exit
.maybe_adjust_range (r
, name
, e
->src
);
257 gcc_checking_assert (r
.undefined_p ()
258 || range_compatible_p (r
.type(), TREE_TYPE (name
)));
260 // Check to see if NAME is defined on edge e.
261 if (m_cache
.range_on_edge (edge_range
, e
, name
))
262 r
.intersect (edge_range
);
266 tracer
.trailer (idx
, "range_on_edge", res
, name
, r
);
270 // fold_range wrapper for range_of_stmt to use as an internal client.
273 gimple_ranger::fold_range_internal (vrange
&r
, gimple
*s
, tree name
)
276 fur_depend
src (s
, &(gori ()), this);
277 return f
.fold_stmt (r
, s
, src
, name
);
280 // Calculate a range for statement S and return it in R. If NAME is
281 // provided it represents the SSA_NAME on the LHS of the statement.
282 // It is only required if there is more than one lhs/output. Check
283 // the global cache for NAME first to see if the evaluation can be
284 // avoided. If a range cannot be calculated, return false and UNDEFINED.
287 gimple_ranger::range_of_stmt (vrange
&r
, gimple
*s
, tree name
)
293 if ((idx
= tracer
.header ("range_of_stmt (")))
296 print_generic_expr (dump_file
, name
, TDF_SLIM
);
297 fputs (") at stmt ", dump_file
);
298 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
302 name
= gimple_get_lhs (s
);
304 // If no name, simply call the base routine.
307 res
= fold_range_internal (r
, s
, NULL_TREE
);
308 if (res
&& is_a
<gcond
*> (s
))
310 // Update any exports in the cache if this is a gimple cond statement.
312 basic_block bb
= gimple_bb (s
);
313 FOR_EACH_GORI_EXPORT_NAME (m_cache
.m_gori
, bb
, exp
)
314 m_cache
.propagate_updated_value (exp
, bb
);
317 else if (!gimple_range_ssa_p (name
))
318 res
= get_tree_range (r
, name
, NULL
);
322 // Check if the stmt has already been processed.
323 if (m_cache
.get_global_range (r
, name
, current
))
325 // If it isn't stale, use this cached value.
329 tracer
.trailer (idx
, " cached", true, name
, r
);
334 prefill_stmt_dependencies (name
);
336 // Calculate a new value.
337 Value_Range
tmp (TREE_TYPE (name
));
338 fold_range_internal (tmp
, s
, name
);
340 // Combine the new value with the old value. This is required because
341 // the way value propagation works, when the IL changes on the fly we
342 // can sometimes get different results. See PR 97741.
343 bool changed
= r
.intersect (tmp
);
344 m_cache
.set_global_range (name
, r
, changed
);
349 tracer
.trailer (idx
, "range_of_stmt", res
, name
, r
);
354 // Check if NAME is a dependency that needs resolving, and push it on the
355 // stack if so. R is a scratch range.
358 gimple_ranger::prefill_name (vrange
&r
, tree name
)
360 if (!gimple_range_ssa_p (name
))
362 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
363 if (!gimple_range_op_handler::supported_p (stmt
) && !is_a
<gphi
*> (stmt
))
366 // If this op has not been processed yet, then push it on the stack
367 if (!m_cache
.get_global_range (r
, name
))
370 // Set the global cache value and mark as alway_current.
371 m_cache
.get_global_range (r
, name
, current
);
372 m_stmt_list
.safe_push (name
);
376 // This routine will seed the global cache with most of the dependencies of
377 // NAME. This prevents excessive call depth through the normal API.
380 gimple_ranger::prefill_stmt_dependencies (tree ssa
)
382 if (SSA_NAME_IS_DEFAULT_DEF (ssa
))
386 gimple
*stmt
= SSA_NAME_DEF_STMT (ssa
);
387 gcc_checking_assert (stmt
&& gimple_bb (stmt
));
389 // Only pre-process range-ops and phis.
390 if (!gimple_range_op_handler::supported_p (stmt
) && !is_a
<gphi
*> (stmt
))
393 // Mark where on the stack we are starting.
394 unsigned start
= m_stmt_list
.length ();
395 m_stmt_list
.safe_push (ssa
);
397 idx
= tracer
.header ("ROS dependence fill\n");
399 // Loop until back at the start point.
400 while (m_stmt_list
.length () > start
)
402 tree name
= m_stmt_list
.last ();
403 // NULL is a marker which indicates the next name in the stack has now
404 // been fully resolved, so we can fold it.
407 // Pop the NULL, then pop the name.
409 name
= m_stmt_list
.pop ();
410 // Don't fold initial request, it will be calculated upon return.
411 if (m_stmt_list
.length () > start
)
413 // Fold and save the value for NAME.
414 stmt
= SSA_NAME_DEF_STMT (name
);
415 Value_Range
r (TREE_TYPE (name
));
416 fold_range_internal (r
, stmt
, name
);
417 // Make sure we don't lose any current global info.
418 Value_Range
tmp (TREE_TYPE (name
));
419 m_cache
.get_global_range (tmp
, name
);
420 bool changed
= tmp
.intersect (r
);
421 m_cache
.set_global_range (name
, tmp
, changed
);
426 // Add marker indicating previous NAME in list should be folded
427 // when we get to this NULL.
428 m_stmt_list
.safe_push (NULL_TREE
);
429 stmt
= SSA_NAME_DEF_STMT (name
);
433 tracer
.print (idx
, "ROS dep fill (");
434 print_generic_expr (dump_file
, name
, TDF_SLIM
);
435 fputs (") at stmt ", dump_file
);
436 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
439 gphi
*phi
= dyn_cast
<gphi
*> (stmt
);
442 Value_Range
r (TREE_TYPE (gimple_phi_result (phi
)));
443 for (unsigned x
= 0; x
< gimple_phi_num_args (phi
); x
++)
444 prefill_name (r
, gimple_phi_arg_def (phi
, x
));
448 gimple_range_op_handler
handler (stmt
);
451 tree op
= handler
.operand2 ();
454 Value_Range
r (TREE_TYPE (op
));
455 prefill_name (r
, op
);
457 op
= handler
.operand1 ();
460 Value_Range
r (TREE_TYPE (op
));
461 prefill_name (r
, op
);
469 tracer
.trailer (idx
, "ROS ", false, ssa
, r
);
474 // This routine will invoke the gimple fold_stmt routine, providing context to
475 // range_of_expr calls via an private internal API.
478 gimple_ranger::fold_stmt (gimple_stmt_iterator
*gsi
, tree (*valueize
) (tree
))
480 gimple
*stmt
= gsi_stmt (*gsi
);
481 current_bb
= gimple_bb (stmt
);
482 bool ret
= ::fold_stmt (gsi
, valueize
);
487 // Called during dominator walks to register any inferred ranges that take
488 // effect from this point forward.
491 gimple_ranger::register_inferred_ranges (gimple
*s
)
493 // First, export the LHS if it is a new global range.
494 tree lhs
= gimple_get_lhs (s
);
497 Value_Range
tmp (TREE_TYPE (lhs
));
498 if (range_of_stmt (tmp
, s
, lhs
) && !tmp
.varying_p ()
499 && set_range_info (lhs
, tmp
) && dump_file
)
501 fprintf (dump_file
, "Global Exported: ");
502 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
503 fprintf (dump_file
, " = ");
504 tmp
.dump (dump_file
);
505 fputc ('\n', dump_file
);
508 m_cache
.apply_inferred_ranges (s
);
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.
516 gimple_ranger::register_transitive_inferred_ranges (basic_block bb
)
518 // Return if there are no inferred ranges in BB.
519 infer_range_manager
&infer
= m_cache
.m_exit
;
520 if (!infer
.has_range_p (bb
))
523 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
524 fprintf (dump_file
, "Checking for transitive inferred ranges in BB %d\n",
527 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
530 gimple
*s
= gsi_stmt (si
);
531 tree lhs
= gimple_get_lhs (s
);
532 // If the LHS already has an inferred effect, leave it be.
533 if (!gimple_range_ssa_p (lhs
) || infer
.has_range_p (lhs
, bb
))
535 // Pick up global value.
536 Value_Range
g (TREE_TYPE (lhs
));
537 range_of_expr (g
, lhs
);
539 // If either dependency has an inferred range, check if recalculating
540 // the LHS is different than the global value. If so, register it as
541 // an inferred range as well.
542 Value_Range
r (TREE_TYPE (lhs
));
544 tree name1
= gori ().depend1 (lhs
);
545 tree name2
= gori ().depend2 (lhs
);
546 if ((name1
&& infer
.has_range_p (name1
, bb
))
547 || (name2
&& infer
.has_range_p (name2
, bb
)))
549 // Check if folding S produces a different result.
550 if (fold_range (r
, s
, this) && g
!= r
)
552 infer
.add_range (lhs
, bb
, r
);
553 m_cache
.register_inferred_value (r
, lhs
, bb
);
559 // This routine will export whatever global ranges are known to GCC
560 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
563 gimple_ranger::export_global_ranges ()
565 /* Cleared after the table header has been printed. */
566 bool print_header
= true;
567 for (unsigned x
= 1; x
< num_ssa_names
; x
++)
569 tree name
= ssa_name (x
);
572 Value_Range
r (TREE_TYPE (name
));
573 if (name
&& !SSA_NAME_IN_FREE_LIST (name
)
574 && gimple_range_ssa_p (name
)
575 && m_cache
.get_global_range (r
, name
)
578 bool updated
= set_range_info (name
, r
);
579 if (!updated
|| !dump_file
)
584 /* Print the header only when there's something else
586 fprintf (dump_file
, "Exported global range table:\n");
587 fprintf (dump_file
, "============================\n");
588 print_header
= false;
591 print_generic_expr (dump_file
, name
, TDF_SLIM
);
592 fprintf (dump_file
, " : ");
594 fprintf (dump_file
, "\n");
599 // Print the known table values to file F.
602 gimple_ranger::dump_bb (FILE *f
, basic_block bb
)
607 fprintf (f
, "\n=========== BB %d ============\n", bb
->index
);
608 m_cache
.dump_bb (f
, bb
);
610 ::dump_bb (f
, bb
, 4, TDF_NONE
);
612 // Now find any globals defined in this block.
613 for (x
= 1; x
< num_ssa_names
; x
++)
615 tree name
= ssa_name (x
);
616 if (!gimple_range_ssa_p (name
) || !SSA_NAME_DEF_STMT (name
))
618 Value_Range
range (TREE_TYPE (name
));
619 if (gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
620 && m_cache
.get_global_range (range
, name
))
622 if (!range
.varying_p ())
624 print_generic_expr (f
, name
, TDF_SLIM
);
633 // And now outgoing edges, if they define anything.
634 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
636 for (x
= 1; x
< num_ssa_names
; x
++)
638 tree name
= gimple_range_ssa_p (ssa_name (x
));
639 if (!name
|| !gori ().has_edge_range_p (name
, e
))
642 Value_Range
range (TREE_TYPE (name
));
643 if (m_cache
.range_on_edge (range
, e
, name
))
645 gimple
*s
= SSA_NAME_DEF_STMT (name
);
646 Value_Range
tmp_range (TREE_TYPE (name
));
647 // Only print the range if this is the def block, or
648 // the on entry cache for either end of the edge is
650 if ((s
&& bb
== gimple_bb (s
)) ||
651 m_cache
.block_range (tmp_range
, bb
, name
, false) ||
652 m_cache
.block_range (tmp_range
, e
->dest
, name
, false))
654 if (!range
.varying_p ())
656 fprintf (f
, "%d->%d ", e
->src
->index
,
659 if (e
->flags
& EDGE_TRUE_VALUE
)
660 fprintf (f
, " (T)%c", c
);
661 else if (e
->flags
& EDGE_FALSE_VALUE
)
662 fprintf (f
, " (F)%c", c
);
665 print_generic_expr (f
, name
, TDF_SLIM
);
676 // Print the known table values to file F.
679 gimple_ranger::dump (FILE *f
)
683 FOR_EACH_BB_FN (bb
, cfun
)
690 gimple_ranger::debug ()
695 /* Create a new ranger instance and associate it with function FUN.
696 Each call must be paired with a call to disable_ranger to release
700 enable_ranger (struct function
*fun
, bool use_imm_uses
)
704 bitmap_obstack_initialize (NULL
);
706 gcc_checking_assert (!fun
->x_range_query
);
707 r
= new gimple_ranger (use_imm_uses
);
708 fun
->x_range_query
= r
;
713 /* Destroy and release the ranger instance associated with function FUN
714 and replace it the global ranger. */
717 disable_ranger (struct function
*fun
)
719 gcc_checking_assert (fun
->x_range_query
);
720 delete fun
->x_range_query
;
721 fun
->x_range_query
= NULL
;
723 bitmap_obstack_release (NULL
);
726 // ------------------------------------------------------------------------
728 // If there is a non-varying value associated with NAME, return true and the
732 assume_query::assume_range_p (vrange
&r
, tree name
)
734 if (global
.get_range (r
, name
))
735 return !r
.varying_p ();
739 // Query used by GORI to pick up any known value on entry to a block.
742 assume_query::range_of_expr (vrange
&r
, tree expr
, gimple
*stmt
)
744 if (!gimple_range_ssa_p (expr
))
745 return get_tree_range (r
, expr
, stmt
);
747 if (!global
.get_range (r
, expr
))
748 r
.set_varying (TREE_TYPE (expr
));
752 // If the current function returns an integral value, and has a single return
753 // statement, it will calculate any SSA_NAMES it can determine ranges for
754 // assuming the function returns 1.
756 assume_query::assume_query ()
758 basic_block exit_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
759 if (single_pred_p (exit_bb
))
761 basic_block bb
= single_pred (exit_bb
);
762 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
765 gimple
*s
= gsi_stmt (gsi
);
766 if (!is_a
<greturn
*> (s
))
768 greturn
*gret
= as_a
<greturn
*> (s
);
769 tree op
= gimple_return_retval (gret
);
770 if (!gimple_range_ssa_p (op
))
772 tree lhs_type
= TREE_TYPE (op
);
773 if (!irange::supports_p (lhs_type
))
776 unsigned prec
= TYPE_PRECISION (lhs_type
);
777 int_range
<2> lhs_range (lhs_type
, wi::one (prec
), wi::one (prec
));
778 global
.set_range (op
, lhs_range
);
780 gimple
*def
= SSA_NAME_DEF_STMT (op
);
781 if (!def
|| gimple_get_lhs (def
) != op
)
783 fur_stmt
src (gret
, this);
784 calculate_stmt (def
, lhs_range
, src
);
788 // Evaluate operand OP on statement S, using the provided LHS range.
789 // If successful, set the range in the global table, then visit OP's def stmt.
792 assume_query::calculate_op (tree op
, gimple
*s
, vrange
&lhs
, fur_source
&src
)
794 Value_Range
op_range (TREE_TYPE (op
));
795 if (m_gori
.compute_operand_range (op_range
, s
, lhs
, op
, src
)
796 && !op_range
.varying_p ())
798 // Set the global range, merging if there is already a range.
799 global
.merge_range (op
, op_range
);
800 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op
);
801 if (def_stmt
&& gimple_get_lhs (def_stmt
) == op
)
802 calculate_stmt (def_stmt
, op_range
, src
);
806 // Evaluate PHI statement, using the provided LHS range.
807 // Check each constant argument predecessor if it can be taken
808 // provide LHS to any symbolic arguments, and process their def statements.
811 assume_query::calculate_phi (gphi
*phi
, vrange
&lhs_range
, fur_source
&src
)
813 for (unsigned x
= 0; x
< gimple_phi_num_args (phi
); x
++)
815 tree arg
= gimple_phi_arg_def (phi
, x
);
816 Value_Range
arg_range (TREE_TYPE (arg
));
817 if (gimple_range_ssa_p (arg
))
819 // A symbol arg will be the LHS value.
820 arg_range
= lhs_range
;
821 range_cast (arg_range
, TREE_TYPE (arg
));
822 if (!global
.get_range (arg_range
, arg
))
824 global
.set_range (arg
, arg_range
);
825 gimple
*def_stmt
= SSA_NAME_DEF_STMT (arg
);
826 if (def_stmt
&& gimple_get_lhs (def_stmt
) == arg
)
827 calculate_stmt (def_stmt
, arg_range
, src
);
830 else if (get_tree_range (arg_range
, arg
, NULL
))
832 // If this is a constant value that differs from LHS, this
833 // edge cannot be taken.
834 arg_range
.intersect (lhs_range
);
835 if (arg_range
.undefined_p ())
837 // Otherwise check the condition feeding this edge.
838 edge e
= gimple_phi_arg_edge (phi
, x
);
839 check_taken_edge (e
, src
);
844 // If an edge is known to be taken, examine the outgoing edge to see
845 // if it carries any range information that can also be evaluated.
848 assume_query::check_taken_edge (edge e
, fur_source
&src
)
850 gimple
*stmt
= gimple_outgoing_range_stmt_p (e
->src
);
851 if (stmt
&& is_a
<gcond
*> (stmt
))
854 gcond_edge_range (cond
, e
);
855 calculate_stmt (stmt
, cond
, src
);
859 // Evaluate statement S which produces range LHS_RANGE.
862 assume_query::calculate_stmt (gimple
*s
, vrange
&lhs_range
, fur_source
&src
)
864 gimple_range_op_handler
handler (s
);
867 tree op
= gimple_range_ssa_p (handler
.operand1 ());
869 calculate_op (op
, s
, lhs_range
, src
);
870 op
= gimple_range_ssa_p (handler
.operand2 ());
872 calculate_op (op
, s
, lhs_range
, src
);
874 else if (is_a
<gphi
*> (s
))
876 calculate_phi (as_a
<gphi
*> (s
), lhs_range
, src
);
877 // Don't further check predecessors of blocks with PHIs.
881 // Even if the walk back terminates before the top, if this is a single
882 // predecessor block, see if the predecessor provided any ranges to get here.
883 if (single_pred_p (gimple_bb (s
)))
884 check_taken_edge (single_pred_edge (gimple_bb (s
)), src
);
887 // Show everything that was calculated.
890 assume_query::dump (FILE *f
)
892 fprintf (f
, "Assumption details calculated:\n");
893 for (unsigned i
= 0; i
< num_ssa_names
; i
++)
895 tree name
= ssa_name (i
);
896 if (!name
|| !gimple_range_ssa_p (name
))
898 tree type
= TREE_TYPE (name
);
899 if (!Value_Range::supports_type_p (type
))
902 Value_Range
assume_range (type
);
903 if (assume_range_p (assume_range
, name
))
905 print_generic_expr (f
, name
, TDF_SLIM
);
907 assume_range
.dump (f
);
911 fprintf (f
, "------------------------------\n");
914 // ---------------------------------------------------------------------------
917 // Create a DOM based ranger for use by a DOM walk pass.
919 dom_ranger::dom_ranger () : m_global (), m_out ()
921 m_freelist
.create (0);
922 m_freelist
.truncate (0);
924 m_e0
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
926 m_e1
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
927 m_pop_list
= BITMAP_ALLOC (NULL
);
928 if (dump_file
&& (param_ranger_debug
& RANGER_DEBUG_TRACE
))
929 tracer
.enable_trace ();
932 // Dispose of a DOM ranger.
934 dom_ranger::~dom_ranger ()
936 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
938 fprintf (dump_file
, "Non-varying global ranges:\n");
939 fprintf (dump_file
, "=========================:\n");
940 m_global
.dump (dump_file
);
942 BITMAP_FREE (m_pop_list
);
945 m_freelist
.release ();
948 // Implement range of EXPR on stmt S, and return it in R.
949 // Return false if no range can be calculated.
952 dom_ranger::range_of_expr (vrange
&r
, tree expr
, gimple
*s
)
955 if (!gimple_range_ssa_p (expr
))
956 return get_tree_range (r
, expr
, s
);
958 if ((idx
= tracer
.header ("range_of_expr ")))
960 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
963 fprintf (dump_file
, " at ");
964 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
967 fprintf (dump_file
, "\n");
971 range_in_bb (r
, gimple_bb (s
), expr
);
973 m_global
.range_of_expr (r
, expr
, s
);
976 tracer
.trailer (idx
, " ", true, expr
, r
);
981 // Return TRUE and the range if edge E has a range set for NAME in
985 dom_ranger::edge_range (vrange
&r
, edge e
, tree name
)
988 basic_block bb
= e
->src
;
990 // Check if BB has any outgoing ranges on edge E.
991 ssa_lazy_cache
*out
= NULL
;
992 if (EDGE_SUCC (bb
, 0) == e
)
993 out
= m_e0
[bb
->index
];
994 else if (EDGE_SUCC (bb
, 1) == e
)
995 out
= m_e1
[bb
->index
];
997 // If there is an edge vector and it has a range, pick it up.
998 if (out
&& out
->has_range (name
))
999 ret
= out
->get_range (r
, name
);
1005 // Return the range of EXPR on edge E in R.
1006 // Return false if no range can be calculated.
1009 dom_ranger::range_on_edge (vrange
&r
, edge e
, tree expr
)
1011 basic_block bb
= e
->src
;
1013 if ((idx
= tracer
.header ("range_on_edge ")))
1015 fprintf (dump_file
, "%d->%d for ",e
->src
->index
, e
->dest
->index
);
1016 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1017 fputc ('\n',dump_file
);
1020 if (!gimple_range_ssa_p (expr
))
1021 return get_tree_range (r
, expr
, NULL
);
1023 if (!edge_range (r
, e
, expr
))
1024 range_in_bb (r
, bb
, expr
);
1027 tracer
.trailer (idx
, " ", true, expr
, r
);
1031 // Return the range of NAME as it exists at the end of block BB in R.
1034 dom_ranger::range_in_bb (vrange
&r
, basic_block bb
, tree name
)
1036 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
1037 // Loop through dominators until we get to the entry block, or we find
1038 // either the defintion block for NAME, or a single pred edge with a range.
1039 while (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1041 // If we hit the deifntion block, pick up the global value.
1044 m_global
.range_of_expr (r
, name
);
1047 // If its a single pred, check the outgoing range of the edge.
1048 if (EDGE_COUNT (bb
->preds
) == 1
1049 && edge_range (r
, EDGE_PRED (bb
, 0), name
))
1051 // Otherwise move up to the dominator, and check again.
1052 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1054 m_global
.range_of_expr (r
, name
);
1058 // Calculate the range of NAME, as the def of stmt S and return it in R.
1059 // Return FALSE if no range cqn be calculated.
1060 // Also set the global range for NAME as this should only be called within
1061 // the def block during a DOM walk.
1062 // Outgoing edges were pre-calculated, so when we establish a global defintion
1063 // check if any outgoing edges hav ranges that can be combined with the
1067 dom_ranger::range_of_stmt (vrange
&r
, gimple
*s
, tree name
)
1072 name
= gimple_range_ssa_p (gimple_get_lhs (s
));
1074 gcc_checking_assert (!name
|| name
== gimple_get_lhs (s
));
1076 if ((idx
= tracer
.header ("range_of_stmt ")))
1077 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
1079 // Its already been calculated.
1080 if (name
&& m_global
.has_range (name
))
1082 ret
= m_global
.range_of_expr (r
, name
, s
);
1084 tracer
.trailer (idx
, " Already had value ", ret
, name
, r
);
1088 // If there is a new calculated range and it is not varying, set
1090 ret
= fold_range (r
, s
, this);
1091 if (ret
&& name
&& m_global
.merge_range (name
, r
) && !r
.varying_p ())
1093 if (set_range_info (name
, r
) && dump_file
)
1095 fprintf (dump_file
, "Global Exported: ");
1096 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1097 fprintf (dump_file
, " = ");
1099 fputc ('\n', dump_file
);
1101 basic_block bb
= gimple_bb (s
);
1102 unsigned bbi
= bb
->index
;
1103 Value_Range
vr (TREE_TYPE (name
));
1104 // If there is a range on edge 0, update it.
1105 if (m_e0
[bbi
] && m_e0
[bbi
]->has_range (name
))
1107 if (m_e0
[bbi
]->merge_range (name
, r
) && dump_file
1108 && (dump_flags
& TDF_DETAILS
))
1110 fprintf (dump_file
, "Outgoing range for ");
1111 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1112 fprintf (dump_file
, " updated on edge %d->%d : ", bbi
,
1113 EDGE_SUCC (bb
, 0)->dest
->index
);
1114 if (m_e0
[bbi
]->get_range (vr
, name
))
1115 vr
.dump (dump_file
);
1116 fputc ('\n', dump_file
);
1119 // If there is a range on edge 1, update it.
1120 if (m_e1
[bbi
] && m_e1
[bbi
]->has_range (name
))
1122 if (m_e1
[bbi
]->merge_range (name
, r
) && dump_file
1123 && (dump_flags
& TDF_DETAILS
))
1125 fprintf (dump_file
, "Outgoing range for ");
1126 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1127 fprintf (dump_file
, " updated on edge %d->%d : ", bbi
,
1128 EDGE_SUCC (bb
, 1)->dest
->index
);
1129 if (m_e1
[bbi
]->get_range (vr
, name
))
1130 vr
.dump (dump_file
);
1131 fputc ('\n', dump_file
);
1136 tracer
.trailer (idx
, " ", ret
, name
, r
);
1140 // Check if GORI has an ranges on edge E. If there re, store them in
1141 // either the E0 or E1 vector based on EDGE_0.
1142 // If there are no ranges, put the empty lazy_cache entry on the freelist
1143 // for use next time.
1146 dom_ranger::maybe_push_edge (edge e
, bool edge_0
)
1148 ssa_lazy_cache
*e_cache
;
1149 if (!m_freelist
.is_empty ())
1150 e_cache
= m_freelist
.pop ();
1152 e_cache
= new ssa_lazy_cache
;
1153 gori_on_edge (*e_cache
, e
, this, &m_out
);
1154 if (e_cache
->empty_p ())
1155 m_freelist
.safe_push (e_cache
);
1159 m_e0
[e
->src
->index
] = e_cache
;
1161 m_e1
[e
->src
->index
] = e_cache
;
1165 // Preprocess block BB. If there are any outgoing edges, precalculate
1166 // the outgoing ranges and store them. Note these are done before
1167 // we process the block, so global values have not been set yet.
1168 // These are "pure" outgoing ranges inflicted by the condition.
1171 dom_ranger::pre_bb (basic_block bb
)
1173 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1174 fprintf (dump_file
, "#FVRP entering BB %d\n", bb
->index
);
1176 // Next, see if this block needs outgoing edges calculated.
1177 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
1178 if (!gsi_end_p (gsi
))
1180 gimple
*s
= gsi_stmt (gsi
);
1181 if (is_a
<gcond
*> (s
) && gimple_range_op_handler::supported_p (s
))
1183 maybe_push_edge (EDGE_SUCC (bb
, 0), true);
1184 maybe_push_edge (EDGE_SUCC (bb
, 1), false);
1186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1188 if (m_e0
[bb
->index
])
1190 fprintf (dump_file
, "\nEdge ranges BB %d->%d\n",
1191 bb
->index
, EDGE_SUCC (bb
, 0)->dest
->index
);
1192 m_e0
[bb
->index
]->dump(dump_file
);
1194 if (m_e1
[bb
->index
])
1196 fprintf (dump_file
, "\nEdge ranges BB %d->%d\n",
1197 bb
->index
, EDGE_SUCC (bb
, 1)->dest
->index
);
1198 m_e1
[bb
->index
]->dump(dump_file
);
1203 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1204 fprintf (dump_file
, "#FVRP DONE entering BB %d\n", bb
->index
);
1207 // Perform any post block processing.
1210 dom_ranger::post_bb (basic_block
)