1 /* Code for GIMPLE range related routines.
2 Copyright (C) 2019-2021 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"
38 gimple_ranger::gimple_ranger () :
39 non_executable_edge_flag (cfun
),
40 m_cache (non_executable_edge_flag
),
43 // If the cache has a relation oracle, use it.
44 m_oracle
= m_cache
.oracle ();
45 if (dump_file
&& (param_evrp_mode
& EVRP_MODE_TRACE
))
46 tracer
.enable_trace ();
48 // Ensure the not_executable flag is clear everywhere.
52 FOR_ALL_BB_FN (bb
, cfun
)
56 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
57 gcc_checking_assert ((e
->flags
& non_executable_edge_flag
) == 0);
63 gimple_ranger::range_of_expr (irange
&r
, tree expr
, gimple
*stmt
)
66 if (!gimple_range_ssa_p (expr
))
67 return get_tree_range (r
, expr
, stmt
);
69 if ((idx
= tracer
.header ("range_of_expr(")))
71 print_generic_expr (dump_file
, expr
, TDF_SLIM
);
72 fputs (")", dump_file
);
75 fputs (" at stmt ", dump_file
);
76 print_gimple_stmt (dump_file
, stmt
, 0, TDF_SLIM
);
79 fputs ("\n", dump_file
);
82 // If there is no statement, just get the global value.
85 if (!m_cache
.get_global_range (r
, expr
))
86 r
= gimple_range_global (expr
);
88 // For a debug stmt, pick the best value currently available, do not
89 // trigger new value calculations. PR 100781.
90 else if (is_gimple_debug (stmt
))
91 m_cache
.range_of_expr (r
, expr
, stmt
);
94 basic_block bb
= gimple_bb (stmt
);
95 gimple
*def_stmt
= SSA_NAME_DEF_STMT (expr
);
97 // If name is defined in this block, try to get an range from S.
98 if (def_stmt
&& gimple_bb (def_stmt
) == bb
)
100 range_of_stmt (r
, def_stmt
, expr
);
101 m_cache
.m_non_null
.adjust_range (r
, expr
, bb
, true);
103 // Otherwise OP comes from outside this block, use range on entry.
105 range_on_entry (r
, bb
, expr
);
108 tracer
.trailer (idx
, "range_of_expr", true, expr
, r
);
112 // Return the range of NAME on entry to block BB in R.
115 gimple_ranger::range_on_entry (irange
&r
, basic_block bb
, tree name
)
117 int_range_max entry_range
;
118 gcc_checking_assert (gimple_range_ssa_p (name
));
121 if ((idx
= tracer
.header ("range_on_entry (")))
123 print_generic_expr (dump_file
, name
, TDF_SLIM
);
124 fprintf (dump_file
, ") to BB %d\n", bb
->index
);
127 // Start with any known range
128 range_of_stmt (r
, SSA_NAME_DEF_STMT (name
), name
);
130 // Now see if there is any on_entry value which may refine it.
131 if (m_cache
.block_range (entry_range
, bb
, name
))
132 r
.intersect (entry_range
);
134 m_cache
.m_non_null
.adjust_range (r
, name
, bb
, true);
137 tracer
.trailer (idx
, "range_on_entry", true, name
, r
);
140 // Calculate the range for NAME at the end of block BB and return it in R.
141 // Return false if no range can be calculated.
144 gimple_ranger::range_on_exit (irange
&r
, basic_block bb
, tree name
)
146 // on-exit from the exit block?
147 gcc_checking_assert (bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
));
148 gcc_checking_assert (gimple_range_ssa_p (name
));
151 if ((idx
= tracer
.header ("range_on_exit (")))
153 print_generic_expr (dump_file
, name
, TDF_SLIM
);
154 fprintf (dump_file
, ") from BB %d\n", bb
->index
);
157 gimple
*s
= SSA_NAME_DEF_STMT (name
);
158 basic_block def_bb
= gimple_bb (s
);
159 // If this is not the definition block, get the range on the last stmt in
160 // the block... if there is one.
163 // If there is no statement provided, get the range_on_entry for this block.
165 range_of_expr (r
, name
, s
);
167 range_on_entry (r
, bb
, name
);
168 gcc_checking_assert (r
.undefined_p ()
169 || range_compatible_p (r
.type (), TREE_TYPE (name
)));
172 tracer
.trailer (idx
, "range_on_exit", true, name
, r
);
175 // Calculate a range for NAME on edge E and return it in R.
178 gimple_ranger::range_on_edge (irange
&r
, edge e
, tree name
)
180 int_range_max edge_range
;
181 gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name
)));
184 if ((idx
= tracer
.header ("range_on_edge (")))
186 print_generic_expr (dump_file
, name
, TDF_SLIM
);
187 fprintf (dump_file
, ") on edge %d->%d\n", e
->src
->index
, e
->dest
->index
);
190 // Check to see if the edge is executable.
191 if ((e
->flags
& non_executable_edge_flag
))
195 tracer
.trailer (idx
, "range_on_edge [Unexecutable] ", true,
201 if (!gimple_range_ssa_p (name
))
202 res
= range_of_expr (r
, name
);
205 range_on_exit (r
, e
->src
, name
);
206 gcc_checking_assert (r
.undefined_p ()
207 || range_compatible_p (r
.type(), TREE_TYPE (name
)));
209 // Check to see if NAME is defined on edge e.
210 if (m_cache
.range_on_edge (edge_range
, e
, name
))
211 r
.intersect (edge_range
);
215 tracer
.trailer (idx
, "range_on_edge", res
, name
, r
);
219 // fold_range wrapper for range_of_stmt to use as an internal client.
222 gimple_ranger::fold_range_internal (irange
&r
, gimple
*s
, tree name
)
225 fur_depend
src (s
, &(gori ()), this);
226 return f
.fold_stmt (r
, s
, src
, name
);
229 // Calculate a range for statement S and return it in R. If NAME is
230 // provided it represents the SSA_NAME on the LHS of the statement.
231 // It is only required if there is more than one lhs/output. Check
232 // the global cache for NAME first to see if the evaluation can be
233 // avoided. If a range cannot be calculated, return false and UNDEFINED.
236 gimple_ranger::range_of_stmt (irange
&r
, gimple
*s
, tree name
)
242 if ((idx
= tracer
.header ("range_of_stmt (")))
245 print_generic_expr (dump_file
, name
, TDF_SLIM
);
246 fputs (") at stmt ", dump_file
);
247 print_gimple_stmt (dump_file
, s
, 0, TDF_SLIM
);
251 name
= gimple_get_lhs (s
);
253 // If no name, simply call the base routine.
255 res
= fold_range_internal (r
, s
, NULL_TREE
);
256 else if (!gimple_range_ssa_p (name
))
258 // Check if the stmt has already been processed, and is not stale.
259 else if (m_cache
.get_non_stale_global_range (r
, name
))
262 tracer
.trailer (idx
, " cached", true, name
, r
);
267 // Otherwise calculate a new value.
269 fold_range_internal (tmp
, s
, name
);
271 // Combine the new value with the old value. This is required because
272 // the way value propagation works, when the IL changes on the fly we
273 // can sometimes get different results. See PR 97741.
275 m_cache
.set_global_range (name
, r
);
280 tracer
.trailer (idx
, "range_of_stmt", res
, name
, r
);
284 // This routine will export whatever global ranges are known to GCC
285 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
288 gimple_ranger::export_global_ranges ()
290 /* Cleared after the table header has been printed. */
291 bool print_header
= true;
292 for (unsigned x
= 1; x
< num_ssa_names
; x
++)
295 tree name
= ssa_name (x
);
296 if (name
&& !SSA_NAME_IN_FREE_LIST (name
)
297 && gimple_range_ssa_p (name
)
298 && m_cache
.get_global_range (r
, name
)
301 bool updated
= update_global_range (r
, name
);
302 if (!updated
|| !dump_file
|| !(dump_flags
& TDF_DETAILS
))
307 /* Print the header only when there's something else
309 fprintf (dump_file
, "Exported global range table:\n");
310 fprintf (dump_file
, "============================\n");
311 print_header
= false;
315 print_generic_expr (dump_file
, name
, TDF_SLIM
);
316 fprintf (dump_file
, " : ");
318 fprintf (dump_file
, "\n");
319 int_range_max same
= vr
;
322 fprintf (dump_file
, " irange : ");
324 fprintf (dump_file
, "\n");
330 // Print the known table values to file F.
333 gimple_ranger::dump_bb (FILE *f
, basic_block bb
)
338 int_range_max range
, tmp_range
;
339 fprintf (f
, "\n=========== BB %d ============\n", bb
->index
);
340 m_cache
.dump_bb (f
, bb
);
342 ::dump_bb (f
, bb
, 4, TDF_NONE
);
344 // Now find any globals defined in this block.
345 for (x
= 1; x
< num_ssa_names
; x
++)
347 tree name
= ssa_name (x
);
348 if (gimple_range_ssa_p (name
) && SSA_NAME_DEF_STMT (name
) &&
349 gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
&&
350 m_cache
.get_global_range (range
, name
))
352 if (!range
.varying_p ())
354 print_generic_expr (f
, name
, TDF_SLIM
);
363 // And now outgoing edges, if they define anything.
364 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
366 for (x
= 1; x
< num_ssa_names
; x
++)
368 tree name
= gimple_range_ssa_p (ssa_name (x
));
369 if (name
&& gori ().has_edge_range_p (name
, e
)
370 && m_cache
.range_on_edge (range
, e
, name
))
372 gimple
*s
= SSA_NAME_DEF_STMT (name
);
373 // Only print the range if this is the def block, or
374 // the on entry cache for either end of the edge is
376 if ((s
&& bb
== gimple_bb (s
)) ||
377 m_cache
.block_range (tmp_range
, bb
, name
, false) ||
378 m_cache
.block_range (tmp_range
, e
->dest
, name
, false))
380 if (!range
.varying_p ())
382 fprintf (f
, "%d->%d ", e
->src
->index
,
385 if (e
->flags
& EDGE_TRUE_VALUE
)
386 fprintf (f
, " (T)%c", c
);
387 else if (e
->flags
& EDGE_FALSE_VALUE
)
388 fprintf (f
, " (F)%c", c
);
391 print_generic_expr (f
, name
, TDF_SLIM
);
402 // Print the known table values to file F.
405 gimple_ranger::dump (FILE *f
)
409 FOR_EACH_BB_FN (bb
, cfun
)
415 /* Create a new ranger instance and associate it with function FUN.
416 Each call must be paired with a call to disable_ranger to release
420 enable_ranger (struct function
*fun
)
424 r
= new gimple_ranger
;
425 fun
->x_range_query
= r
;
430 /* Destroy and release the ranger instance associated with function FUN
431 and replace it the global ranger. */
434 disable_ranger (struct function
*fun
)
436 delete fun
->x_range_query
;
438 fun
->x_range_query
= &global_ranges
;