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 m_cache
.get_global_range (r
, expr
);
106 // Pick up implied context information from the on-entry cache
107 // if current_bb is set. Do not attempt any new calculations.
108 if (current_bb
&& m_cache
.block_range (tmp
, current_bb
, expr
, false))
112 sprintf (str
, "picked up range from bb %d\n",current_bb
->index
);
114 tracer
.print (idx
, str
);
117 // For a debug stmt, pick the best value currently available, do not
118 // trigger new value calculations. PR 100781.
119 else if (is_gimple_debug (stmt
))
120 m_cache
.range_of_expr (r
, expr
, stmt
);
123 basic_block bb
= gimple_bb (stmt
);
124 gimple
*def_stmt
= SSA_NAME_DEF_STMT (expr
);
126 // If name is defined in this block, try to get an range from S.
127 if (def_stmt
&& gimple_bb (def_stmt
) == bb
)
129 // Declared in this block, if it has a global set, check for an
130 // override from a block walk, otherwise calculate it.
131 if (m_cache
.get_global_range (r
, expr
))
132 m_cache
.block_range (r
, bb
, expr
, false);
134 range_of_stmt (r
, def_stmt
, expr
);
136 // Otherwise OP comes from outside this block, use range on entry.
138 range_on_entry (r
, bb
, expr
);
141 tracer
.trailer (idx
, "range_of_expr", true, expr
, r
);
145 // Return the range of NAME on entry to block BB in R.
148 gimple_ranger::range_on_entry (vrange
&r
, basic_block bb
, tree name
)
150 Value_Range
entry_range (TREE_TYPE (name
));
151 gcc_checking_assert (gimple_range_ssa_p (name
));
154 if ((idx
= tracer
.header ("range_on_entry (")))
156 print_generic_expr (dump_file
, name
, TDF_SLIM
);
157 fprintf (dump_file
, ") to BB %d\n", bb
->index
);
160 // Start with any known range
161 range_of_stmt (r
, SSA_NAME_DEF_STMT (name
), name
);
163 // Now see if there is any on_entry value which may refine it.
164 if (m_cache
.block_range (entry_range
, bb
, name
))
165 r
.intersect (entry_range
);
168 tracer
.trailer (idx
, "range_on_entry", true, name
, r
);
171 // Calculate the range for NAME at the end of block BB and return it in R.
172 // Return false if no range can be calculated.
175 gimple_ranger::range_on_exit (vrange
&r
, basic_block bb
, tree name
)
177 // on-exit from the exit block?
178 gcc_checking_assert (gimple_range_ssa_p (name
));
181 if ((idx
= tracer
.header ("range_on_exit (")))
183 print_generic_expr (dump_file
, name
, TDF_SLIM
);
184 fprintf (dump_file
, ") from BB %d\n", bb
->index
);
187 gimple
*s
= SSA_NAME_DEF_STMT (name
);
188 basic_block def_bb
= gimple_bb (s
);
189 // If this is not the definition block, get the range on the last stmt in
190 // the block... if there is one.
192 s
= last_nondebug_stmt (bb
);
193 // If there is no statement provided, get the range_on_entry for this block.
195 range_of_expr (r
, name
, s
);
197 range_on_entry (r
, bb
, name
);
198 gcc_checking_assert (r
.undefined_p ()
199 || range_compatible_p (r
.type (), TREE_TYPE (name
)));
202 tracer
.trailer (idx
, "range_on_exit", true, name
, r
);
205 // Calculate a range for NAME on edge E and return it in R.
208 gimple_ranger::range_on_edge (vrange
&r
, edge e
, tree name
)
210 Value_Range
edge_range (TREE_TYPE (name
));
212 if (!r
.supports_type_p (TREE_TYPE (name
)))
215 // Do not process values along abnormal edges.
216 if (e
->flags
& EDGE_ABNORMAL
)
217 return get_tree_range (r
, name
, NULL
);
220 if ((idx
= tracer
.header ("range_on_edge (")))
222 print_generic_expr (dump_file
, name
, TDF_SLIM
);
223 fprintf (dump_file
, ") on edge %d->%d\n", e
->src
->index
, e
->dest
->index
);
226 // Check to see if the edge is executable.
227 if ((e
->flags
& non_executable_edge_flag
))
231 tracer
.trailer (idx
, "range_on_edge [Unexecutable] ", true,
237 if (!gimple_range_ssa_p (name
))
238 res
= get_tree_range (r
, name
, NULL
);
241 range_on_exit (r
, e
->src
, name
);
242 // If this is not an abnormal edge, check for a non-null exit .
243 if ((e
->flags
& (EDGE_EH
| EDGE_ABNORMAL
)) == 0)
244 m_cache
.m_exit
.maybe_adjust_range (r
, name
, e
->src
);
245 gcc_checking_assert (r
.undefined_p ()
246 || range_compatible_p (r
.type(), TREE_TYPE (name
)));
248 // Check to see if NAME is defined on edge e.
249 if (m_cache
.range_on_edge (edge_range
, e
, name
))
250 r
.intersect (edge_range
);
254 tracer
.trailer (idx
, "range_on_edge", res
, name
, r
);
258 // fold_range wrapper for range_of_stmt to use as an internal client.
261 gimple_ranger::fold_range_internal (vrange
&r
, gimple
*s
, tree name
)
264 fur_depend
src (s
, &(gori ()), this);
265 return f
.fold_stmt (r
, s
, src
, name
);
268 // Calculate a range for statement S and return it in R. If NAME is
269 // provided it represents the SSA_NAME on the LHS of the statement.
270 // It is only required if there is more than one lhs/output. Check
271 // the global cache for NAME first to see if the evaluation can be
272 // avoided. If a range cannot be calculated, return false and UNDEFINED.
275 gimple_ranger::range_of_stmt (vrange
&r
, gimple
*s
, tree name
)
281 if ((idx
= tracer
.header ("range_of_stmt (")))
284 print_generic_expr (dump_file
, name
, TDF_SLIM
);
285 fputs (") at stmt ", dump_file
);
286 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
290 name
= gimple_get_lhs (s
);
292 // If no name, simply call the base routine.
295 res
= fold_range_internal (r
, s
, NULL_TREE
);
296 if (res
&& is_a
<gcond
*> (s
))
298 // Update any exports in the cache if this is a gimple cond statement.
300 basic_block bb
= gimple_bb (s
);
301 FOR_EACH_GORI_EXPORT_NAME (m_cache
.m_gori
, bb
, exp
)
302 m_cache
.propagate_updated_value (exp
, bb
);
305 else if (!gimple_range_ssa_p (name
))
306 res
= get_tree_range (r
, name
, NULL
);
310 // Check if the stmt has already been processed.
311 if (m_cache
.get_global_range (r
, name
, current
))
313 // If it isn't stale, use this cached value.
317 tracer
.trailer (idx
, " cached", true, name
, r
);
322 prefill_stmt_dependencies (name
);
324 // Calculate a new value.
325 Value_Range
tmp (TREE_TYPE (name
));
326 fold_range_internal (tmp
, s
, name
);
328 // Combine the new value with the old value. This is required because
329 // the way value propagation works, when the IL changes on the fly we
330 // can sometimes get different results. See PR 97741.
331 bool changed
= r
.intersect (tmp
);
332 m_cache
.set_global_range (name
, r
, changed
);
337 tracer
.trailer (idx
, "range_of_stmt", res
, name
, r
);
342 // Check if NAME is a dependency that needs resolving, and push it on the
343 // stack if so. R is a scratch range.
346 gimple_ranger::prefill_name (vrange
&r
, tree name
)
348 if (!gimple_range_ssa_p (name
))
350 gimple
*stmt
= SSA_NAME_DEF_STMT (name
);
351 if (!gimple_range_op_handler::supported_p (stmt
) && !is_a
<gphi
*> (stmt
))
354 // If this op has not been processed yet, then push it on the stack
355 if (!m_cache
.get_global_range (r
, name
))
358 // Set the global cache value and mark as alway_current.
359 m_cache
.get_global_range (r
, name
, current
);
360 m_stmt_list
.safe_push (name
);
364 // This routine will seed the global cache with most of the dependencies of
365 // NAME. This prevents excessive call depth through the normal API.
368 gimple_ranger::prefill_stmt_dependencies (tree ssa
)
370 if (SSA_NAME_IS_DEFAULT_DEF (ssa
))
374 gimple
*stmt
= SSA_NAME_DEF_STMT (ssa
);
375 gcc_checking_assert (stmt
&& gimple_bb (stmt
));
377 // Only pre-process range-ops and phis.
378 if (!gimple_range_op_handler::supported_p (stmt
) && !is_a
<gphi
*> (stmt
))
381 // Mark where on the stack we are starting.
382 unsigned start
= m_stmt_list
.length ();
383 m_stmt_list
.safe_push (ssa
);
385 idx
= tracer
.header ("ROS dependence fill\n");
387 // Loop until back at the start point.
388 while (m_stmt_list
.length () > start
)
390 tree name
= m_stmt_list
.last ();
391 // NULL is a marker which indicates the next name in the stack has now
392 // been fully resolved, so we can fold it.
395 // Pop the NULL, then pop the name.
397 name
= m_stmt_list
.pop ();
398 // Don't fold initial request, it will be calculated upon return.
399 if (m_stmt_list
.length () > start
)
401 // Fold and save the value for NAME.
402 stmt
= SSA_NAME_DEF_STMT (name
);
403 Value_Range
r (TREE_TYPE (name
));
404 fold_range_internal (r
, stmt
, name
);
405 // Make sure we don't lose any current global info.
406 Value_Range
tmp (TREE_TYPE (name
));
407 m_cache
.get_global_range (tmp
, name
);
408 bool changed
= tmp
.intersect (r
);
409 m_cache
.set_global_range (name
, tmp
, changed
);
414 // Add marker indicating previous NAME in list should be folded
415 // when we get to this NULL.
416 m_stmt_list
.safe_push (NULL_TREE
);
417 stmt
= SSA_NAME_DEF_STMT (name
);
421 tracer
.print (idx
, "ROS dep fill (");
422 print_generic_expr (dump_file
, name
, TDF_SLIM
);
423 fputs (") at stmt ", dump_file
);
424 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
427 gphi
*phi
= dyn_cast
<gphi
*> (stmt
);
430 Value_Range
r (TREE_TYPE (gimple_phi_result (phi
)));
431 for (unsigned x
= 0; x
< gimple_phi_num_args (phi
); x
++)
432 prefill_name (r
, gimple_phi_arg_def (phi
, x
));
436 gimple_range_op_handler
handler (stmt
);
439 tree op
= handler
.operand2 ();
442 Value_Range
r (TREE_TYPE (op
));
443 prefill_name (r
, op
);
445 op
= handler
.operand1 ();
448 Value_Range
r (TREE_TYPE (op
));
449 prefill_name (r
, op
);
457 tracer
.trailer (idx
, "ROS ", false, ssa
, r
);
462 // This routine will invoke the gimple fold_stmt routine, providing context to
463 // range_of_expr calls via an private internal API.
466 gimple_ranger::fold_stmt (gimple_stmt_iterator
*gsi
, tree (*valueize
) (tree
))
468 gimple
*stmt
= gsi_stmt (*gsi
);
469 current_bb
= gimple_bb (stmt
);
470 bool ret
= ::fold_stmt (gsi
, valueize
);
475 // Called during dominator walks to register any inferred ranges that take
476 // effect from this point forward.
479 gimple_ranger::register_inferred_ranges (gimple
*s
)
481 // First, export the LHS if it is a new global range.
482 tree lhs
= gimple_get_lhs (s
);
485 Value_Range
tmp (TREE_TYPE (lhs
));
486 if (range_of_stmt (tmp
, s
, lhs
) && !tmp
.varying_p ()
487 && set_range_info (lhs
, tmp
) && dump_file
)
489 fprintf (dump_file
, "Global Exported: ");
490 print_generic_expr (dump_file
, lhs
, TDF_SLIM
);
491 fprintf (dump_file
, " = ");
492 tmp
.dump (dump_file
);
493 fputc ('\n', dump_file
);
496 m_cache
.apply_inferred_ranges (s
);
499 // This function will walk the statements in BB to determine if any
500 // discovered inferred ranges in the block have any transitive effects,
501 // and if so, register those effects in BB.
504 gimple_ranger::register_transitive_inferred_ranges (basic_block bb
)
506 // Return if there are no inferred ranges in BB.
507 infer_range_manager
&infer
= m_cache
.m_exit
;
508 if (!infer
.has_range_p (bb
))
511 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
512 fprintf (dump_file
, "Checking for transitive inferred ranges in BB %d\n",
515 for (gimple_stmt_iterator si
= gsi_start_bb (bb
); !gsi_end_p (si
);
518 gimple
*s
= gsi_stmt (si
);
519 tree lhs
= gimple_get_lhs (s
);
520 // If the LHS already has an inferred effect, leave it be.
521 if (!gimple_range_ssa_p (lhs
) || infer
.has_range_p (lhs
, bb
))
523 // Pick up global value.
524 Value_Range
g (TREE_TYPE (lhs
));
525 range_of_expr (g
, lhs
);
527 // If either dependency has an inferred range, check if recalculating
528 // the LHS is different than the global value. If so, register it as
529 // an inferred range as well.
530 Value_Range
r (TREE_TYPE (lhs
));
532 tree name1
= gori ().depend1 (lhs
);
533 tree name2
= gori ().depend2 (lhs
);
534 if ((name1
&& infer
.has_range_p (name1
, bb
))
535 || (name2
&& infer
.has_range_p (name2
, bb
)))
537 // Check if folding S produces a different result.
538 if (fold_range (r
, s
, this) && g
!= r
)
540 infer
.add_range (lhs
, bb
, r
);
541 m_cache
.register_inferred_value (r
, lhs
, bb
);
547 // This routine will export whatever global ranges are known to GCC
548 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
551 gimple_ranger::export_global_ranges ()
553 /* Cleared after the table header has been printed. */
554 bool print_header
= true;
555 for (unsigned x
= 1; x
< num_ssa_names
; x
++)
557 tree name
= ssa_name (x
);
560 Value_Range
r (TREE_TYPE (name
));
561 if (name
&& !SSA_NAME_IN_FREE_LIST (name
)
562 && gimple_range_ssa_p (name
)
563 && m_cache
.get_global_range (r
, name
)
566 bool updated
= set_range_info (name
, r
);
567 if (!updated
|| !dump_file
)
572 /* Print the header only when there's something else
574 fprintf (dump_file
, "Exported global range table:\n");
575 fprintf (dump_file
, "============================\n");
576 print_header
= false;
579 print_generic_expr (dump_file
, name
, TDF_SLIM
);
580 fprintf (dump_file
, " : ");
582 fprintf (dump_file
, "\n");
587 // Print the known table values to file F.
590 gimple_ranger::dump_bb (FILE *f
, basic_block bb
)
595 fprintf (f
, "\n=========== BB %d ============\n", bb
->index
);
596 m_cache
.dump_bb (f
, bb
);
598 ::dump_bb (f
, bb
, 4, TDF_NONE
);
600 // Now find any globals defined in this block.
601 for (x
= 1; x
< num_ssa_names
; x
++)
603 tree name
= ssa_name (x
);
604 if (!gimple_range_ssa_p (name
) || !SSA_NAME_DEF_STMT (name
))
606 Value_Range
range (TREE_TYPE (name
));
607 if (gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
608 && m_cache
.get_global_range (range
, name
))
610 if (!range
.varying_p ())
612 print_generic_expr (f
, name
, TDF_SLIM
);
621 // And now outgoing edges, if they define anything.
622 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
624 for (x
= 1; x
< num_ssa_names
; x
++)
626 tree name
= gimple_range_ssa_p (ssa_name (x
));
627 if (!name
|| !gori ().has_edge_range_p (name
, e
))
630 Value_Range
range (TREE_TYPE (name
));
631 if (m_cache
.range_on_edge (range
, e
, name
))
633 gimple
*s
= SSA_NAME_DEF_STMT (name
);
634 Value_Range
tmp_range (TREE_TYPE (name
));
635 // Only print the range if this is the def block, or
636 // the on entry cache for either end of the edge is
638 if ((s
&& bb
== gimple_bb (s
)) ||
639 m_cache
.block_range (tmp_range
, bb
, name
, false) ||
640 m_cache
.block_range (tmp_range
, e
->dest
, name
, false))
642 if (!range
.varying_p ())
644 fprintf (f
, "%d->%d ", e
->src
->index
,
647 if (e
->flags
& EDGE_TRUE_VALUE
)
648 fprintf (f
, " (T)%c", c
);
649 else if (e
->flags
& EDGE_FALSE_VALUE
)
650 fprintf (f
, " (F)%c", c
);
653 print_generic_expr (f
, name
, TDF_SLIM
);
664 // Print the known table values to file F.
667 gimple_ranger::dump (FILE *f
)
671 FOR_EACH_BB_FN (bb
, cfun
)
678 gimple_ranger::debug ()
683 /* Create a new ranger instance and associate it with function FUN.
684 Each call must be paired with a call to disable_ranger to release
688 enable_ranger (struct function
*fun
, bool use_imm_uses
)
692 bitmap_obstack_initialize (NULL
);
694 gcc_checking_assert (!fun
->x_range_query
);
695 r
= new gimple_ranger (use_imm_uses
);
696 fun
->x_range_query
= r
;
701 /* Destroy and release the ranger instance associated with function FUN
702 and replace it the global ranger. */
705 disable_ranger (struct function
*fun
)
707 gcc_checking_assert (fun
->x_range_query
);
708 delete fun
->x_range_query
;
709 fun
->x_range_query
= NULL
;
711 bitmap_obstack_release (NULL
);
714 // ------------------------------------------------------------------------
716 // If there is a non-varying value associated with NAME, return true and the
720 assume_query::assume_range_p (vrange
&r
, tree name
)
722 if (global
.get_range (r
, name
))
723 return !r
.varying_p ();
727 // Query used by GORI to pick up any known value on entry to a block.
730 assume_query::range_of_expr (vrange
&r
, tree expr
, gimple
*stmt
)
732 if (!gimple_range_ssa_p (expr
))
733 return get_tree_range (r
, expr
, stmt
);
735 if (!global
.get_range (r
, expr
))
736 r
.set_varying (TREE_TYPE (expr
));
740 // If the current function returns an integral value, and has a single return
741 // statement, it will calculate any SSA_NAMES it can determine ranges for
742 // assuming the function returns 1.
744 assume_query::assume_query ()
746 basic_block exit_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
);
747 if (single_pred_p (exit_bb
))
749 basic_block bb
= single_pred (exit_bb
);
750 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
753 gimple
*s
= gsi_stmt (gsi
);
754 if (!is_a
<greturn
*> (s
))
756 greturn
*gret
= as_a
<greturn
*> (s
);
757 tree op
= gimple_return_retval (gret
);
758 if (!gimple_range_ssa_p (op
))
760 tree lhs_type
= TREE_TYPE (op
);
761 if (!irange::supports_p (lhs_type
))
764 unsigned prec
= TYPE_PRECISION (lhs_type
);
765 int_range
<2> lhs_range (lhs_type
, wi::one (prec
), wi::one (prec
));
766 global
.set_range (op
, lhs_range
);
768 gimple
*def
= SSA_NAME_DEF_STMT (op
);
769 if (!def
|| gimple_get_lhs (def
) != op
)
771 fur_stmt
src (gret
, this);
772 calculate_stmt (def
, lhs_range
, src
);
776 // Evaluate operand OP on statement S, using the provided LHS range.
777 // If successful, set the range in the global table, then visit OP's def stmt.
780 assume_query::calculate_op (tree op
, gimple
*s
, vrange
&lhs
, fur_source
&src
)
782 Value_Range
op_range (TREE_TYPE (op
));
783 if (m_gori
.compute_operand_range (op_range
, s
, lhs
, op
, src
)
784 && !op_range
.varying_p ())
786 // Set the global range, merging if there is already a range.
787 global
.merge_range (op
, op_range
);
788 gimple
*def_stmt
= SSA_NAME_DEF_STMT (op
);
789 if (def_stmt
&& gimple_get_lhs (def_stmt
) == op
)
790 calculate_stmt (def_stmt
, op_range
, src
);
794 // Evaluate PHI statement, using the provided LHS range.
795 // Check each constant argument predecessor if it can be taken
796 // provide LHS to any symbolic arguments, and process their def statements.
799 assume_query::calculate_phi (gphi
*phi
, vrange
&lhs_range
, fur_source
&src
)
801 for (unsigned x
= 0; x
< gimple_phi_num_args (phi
); x
++)
803 tree arg
= gimple_phi_arg_def (phi
, x
);
804 Value_Range
arg_range (TREE_TYPE (arg
));
805 if (gimple_range_ssa_p (arg
))
807 // A symbol arg will be the LHS value.
808 arg_range
= lhs_range
;
809 range_cast (arg_range
, TREE_TYPE (arg
));
810 if (!global
.get_range (arg_range
, arg
))
812 global
.set_range (arg
, arg_range
);
813 gimple
*def_stmt
= SSA_NAME_DEF_STMT (arg
);
814 if (def_stmt
&& gimple_get_lhs (def_stmt
) == arg
)
815 calculate_stmt (def_stmt
, arg_range
, src
);
818 else if (get_tree_range (arg_range
, arg
, NULL
))
820 // If this is a constant value that differs from LHS, this
821 // edge cannot be taken.
822 arg_range
.intersect (lhs_range
);
823 if (arg_range
.undefined_p ())
825 // Otherwise check the condition feeding this edge.
826 edge e
= gimple_phi_arg_edge (phi
, x
);
827 check_taken_edge (e
, src
);
832 // If an edge is known to be taken, examine the outgoing edge to see
833 // if it carries any range information that can also be evaluated.
836 assume_query::check_taken_edge (edge e
, fur_source
&src
)
838 gimple
*stmt
= gimple_outgoing_range_stmt_p (e
->src
);
839 if (stmt
&& is_a
<gcond
*> (stmt
))
842 gcond_edge_range (cond
, e
);
843 calculate_stmt (stmt
, cond
, src
);
847 // Evaluate statement S which produces range LHS_RANGE.
850 assume_query::calculate_stmt (gimple
*s
, vrange
&lhs_range
, fur_source
&src
)
852 gimple_range_op_handler
handler (s
);
855 tree op
= gimple_range_ssa_p (handler
.operand1 ());
857 calculate_op (op
, s
, lhs_range
, src
);
858 op
= gimple_range_ssa_p (handler
.operand2 ());
860 calculate_op (op
, s
, lhs_range
, src
);
862 else if (is_a
<gphi
*> (s
))
864 calculate_phi (as_a
<gphi
*> (s
), lhs_range
, src
);
865 // Don't further check predecessors of blocks with PHIs.
869 // Even if the walk back terminates before the top, if this is a single
870 // predecessor block, see if the predecessor provided any ranges to get here.
871 if (single_pred_p (gimple_bb (s
)))
872 check_taken_edge (single_pred_edge (gimple_bb (s
)), src
);
875 // Show everything that was calculated.
878 assume_query::dump (FILE *f
)
880 fprintf (f
, "Assumption details calculated:\n");
881 for (unsigned i
= 0; i
< num_ssa_names
; i
++)
883 tree name
= ssa_name (i
);
884 if (!name
|| !gimple_range_ssa_p (name
))
886 tree type
= TREE_TYPE (name
);
887 if (!Value_Range::supports_type_p (type
))
890 Value_Range
assume_range (type
);
891 if (assume_range_p (assume_range
, name
))
893 print_generic_expr (f
, name
, TDF_SLIM
);
895 assume_range
.dump (f
);
899 fprintf (f
, "------------------------------\n");
902 // ---------------------------------------------------------------------------
905 // Create a DOM based ranger for use by a DOM walk pass.
907 dom_ranger::dom_ranger () : m_global (), m_out ()
909 m_freelist
.create (0);
910 m_freelist
.truncate (0);
912 m_e0
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
914 m_e1
.safe_grow_cleared (last_basic_block_for_fn (cfun
));
915 m_pop_list
= BITMAP_ALLOC (NULL
);
916 if (dump_file
&& (param_ranger_debug
& RANGER_DEBUG_TRACE
))
917 tracer
.enable_trace ();
920 // Dispose of a DOM ranger.
922 dom_ranger::~dom_ranger ()
924 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
926 fprintf (dump_file
, "Non-varying global ranges:\n");
927 fprintf (dump_file
, "=========================:\n");
928 m_global
.dump (dump_file
);
930 BITMAP_FREE (m_pop_list
);
933 m_freelist
.release ();
936 // Implement range of EXPR on stmt S, and return it in R.
937 // Return false if no range can be calculated.
940 dom_ranger::range_of_expr (vrange
&r
, tree expr
, gimple
*s
)
943 if (!gimple_range_ssa_p (expr
))
944 return get_tree_range (r
, expr
, s
);
946 if ((idx
= tracer
.header ("range_of_expr ")))
948 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
951 fprintf (dump_file
, " at ");
952 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
955 fprintf (dump_file
, "\n");
959 range_in_bb (r
, gimple_bb (s
), expr
);
961 m_global
.range_of_expr (r
, expr
, s
);
964 tracer
.trailer (idx
, " ", true, expr
, r
);
969 // Return TRUE and the range if edge E has a range set for NAME in
973 dom_ranger::edge_range (vrange
&r
, edge e
, tree name
)
976 basic_block bb
= e
->src
;
978 // Check if BB has any outgoing ranges on edge E.
979 ssa_lazy_cache
*out
= NULL
;
980 if (EDGE_SUCC (bb
, 0) == e
)
981 out
= m_e0
[bb
->index
];
982 else if (EDGE_SUCC (bb
, 1) == e
)
983 out
= m_e1
[bb
->index
];
985 // If there is an edge vector and it has a range, pick it up.
986 if (out
&& out
->has_range (name
))
987 ret
= out
->get_range (r
, name
);
993 // Return the range of EXPR on edge E in R.
994 // Return false if no range can be calculated.
997 dom_ranger::range_on_edge (vrange
&r
, edge e
, tree expr
)
999 basic_block bb
= e
->src
;
1001 if ((idx
= tracer
.header ("range_on_edge ")))
1003 fprintf (dump_file
, "%d->%d for ",e
->src
->index
, e
->dest
->index
);
1004 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
1005 fputc ('\n',dump_file
);
1008 if (!gimple_range_ssa_p (expr
))
1009 return get_tree_range (r
, expr
, NULL
);
1011 if (!edge_range (r
, e
, expr
))
1012 range_in_bb (r
, bb
, expr
);
1015 tracer
.trailer (idx
, " ", true, expr
, r
);
1019 // Return the range of NAME as it exists at the end of block BB in R.
1022 dom_ranger::range_in_bb (vrange
&r
, basic_block bb
, tree name
)
1024 basic_block def_bb
= gimple_bb (SSA_NAME_DEF_STMT (name
));
1025 // Loop through dominators until we get to the entry block, or we find
1026 // either the defintion block for NAME, or a single pred edge with a range.
1027 while (bb
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1029 // If we hit the deifntion block, pick up the global value.
1032 m_global
.range_of_expr (r
, name
);
1035 // If its a single pred, check the outgoing range of the edge.
1036 if (EDGE_COUNT (bb
->preds
) == 1
1037 && edge_range (r
, EDGE_PRED (bb
, 0), name
))
1039 // Otherwise move up to the dominator, and check again.
1040 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
1042 m_global
.range_of_expr (r
, name
);
1046 // Calculate the range of NAME, as the def of stmt S and return it in R.
1047 // Return FALSE if no range cqn be calculated.
1048 // Also set the global range for NAME as this should only be called within
1049 // the def block during a DOM walk.
1050 // Outgoing edges were pre-calculated, so when we establish a global defintion
1051 // check if any outgoing edges hav ranges that can be combined with the
1055 dom_ranger::range_of_stmt (vrange
&r
, gimple
*s
, tree name
)
1060 name
= gimple_range_ssa_p (gimple_get_lhs (s
));
1062 gcc_checking_assert (!name
|| name
== gimple_get_lhs (s
));
1064 if ((idx
= tracer
.header ("range_of_stmt ")))
1065 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
1067 // Its already been calculated.
1068 if (name
&& m_global
.has_range (name
))
1070 ret
= m_global
.range_of_expr (r
, name
, s
);
1072 tracer
.trailer (idx
, " Already had value ", ret
, name
, r
);
1076 // If there is a new calculated range and it is not varying, set
1078 ret
= fold_range (r
, s
, this);
1079 if (ret
&& name
&& m_global
.merge_range (name
, r
) && !r
.varying_p ())
1081 if (set_range_info (name
, r
) && dump_file
)
1083 fprintf (dump_file
, "Global Exported: ");
1084 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1085 fprintf (dump_file
, " = ");
1087 fputc ('\n', dump_file
);
1089 basic_block bb
= gimple_bb (s
);
1090 unsigned bbi
= bb
->index
;
1091 Value_Range
vr (TREE_TYPE (name
));
1092 // If there is a range on edge 0, update it.
1093 if (m_e0
[bbi
] && m_e0
[bbi
]->has_range (name
))
1095 if (m_e0
[bbi
]->merge_range (name
, r
) && dump_file
1096 && (dump_flags
& TDF_DETAILS
))
1098 fprintf (dump_file
, "Outgoing range for ");
1099 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1100 fprintf (dump_file
, " updated on edge %d->%d : ", bbi
,
1101 EDGE_SUCC (bb
, 0)->dest
->index
);
1102 if (m_e0
[bbi
]->get_range (vr
, name
))
1103 vr
.dump (dump_file
);
1104 fputc ('\n', dump_file
);
1107 // If there is a range on edge 1, update it.
1108 if (m_e1
[bbi
] && m_e1
[bbi
]->has_range (name
))
1110 if (m_e1
[bbi
]->merge_range (name
, r
) && dump_file
1111 && (dump_flags
& TDF_DETAILS
))
1113 fprintf (dump_file
, "Outgoing range for ");
1114 print_generic_expr (dump_file
, name
, TDF_SLIM
);
1115 fprintf (dump_file
, " updated on edge %d->%d : ", bbi
,
1116 EDGE_SUCC (bb
, 1)->dest
->index
);
1117 if (m_e1
[bbi
]->get_range (vr
, name
))
1118 vr
.dump (dump_file
);
1119 fputc ('\n', dump_file
);
1124 tracer
.trailer (idx
, " ", ret
, name
, r
);
1128 // Check if GORI has an ranges on edge E. If there re, store them in
1129 // either the E0 or E1 vector based on EDGE_0.
1130 // If there are no ranges, put the empty lazy_cache entry on the freelist
1131 // for use next time.
1134 dom_ranger::maybe_push_edge (edge e
, bool edge_0
)
1136 ssa_lazy_cache
*e_cache
;
1137 if (!m_freelist
.is_empty ())
1138 e_cache
= m_freelist
.pop ();
1140 e_cache
= new ssa_lazy_cache
;
1141 gori_on_edge (*e_cache
, e
, this, &m_out
);
1142 if (e_cache
->empty_p ())
1143 m_freelist
.safe_push (e_cache
);
1147 m_e0
[e
->src
->index
] = e_cache
;
1149 m_e1
[e
->src
->index
] = e_cache
;
1153 // Preprocess block BB. If there are any outgoing edges, precalculate
1154 // the outgoing ranges and store them. Note these are done before
1155 // we process the block, so global values have not been set yet.
1156 // These are "pure" outgoing ranges inflicted by the condition.
1159 dom_ranger::pre_bb (basic_block bb
)
1161 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1162 fprintf (dump_file
, "#FVRP entering BB %d\n", bb
->index
);
1164 // Next, see if this block needs outgoing edges calculated.
1165 gimple_stmt_iterator gsi
= gsi_last_nondebug_bb (bb
);
1166 if (!gsi_end_p (gsi
))
1168 gimple
*s
= gsi_stmt (gsi
);
1169 if (is_a
<gcond
*> (s
) && gimple_range_op_handler::supported_p (s
))
1171 maybe_push_edge (EDGE_SUCC (bb
, 0), true);
1172 maybe_push_edge (EDGE_SUCC (bb
, 1), false);
1174 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1176 if (m_e0
[bb
->index
])
1178 fprintf (dump_file
, "\nEdge ranges BB %d->%d\n",
1179 bb
->index
, EDGE_SUCC (bb
, 0)->dest
->index
);
1180 m_e0
[bb
->index
]->dump(dump_file
);
1182 if (m_e1
[bb
->index
])
1184 fprintf (dump_file
, "\nEdge ranges BB %d->%d\n",
1185 bb
->index
, EDGE_SUCC (bb
, 1)->dest
->index
);
1186 m_e1
[bb
->index
]->dump(dump_file
);
1191 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1192 fprintf (dump_file
, "#FVRP DONE entering BB %d\n", bb
->index
);
1195 // Perform any post block processing.
1198 dom_ranger::post_bb (basic_block
)