1 /* Code for GIMPLE range related routines.
2 Copyright (C) 2019-2022 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
gimple_ranger()40 gimple_ranger::gimple_ranger () :
41 non_executable_edge_flag (cfun),
42 m_cache (non_executable_edge_flag),
43 tracer (""),
44 current_bb (NULL)
45 {
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);
53
54 // Ensure the not_executable flag is clear everywhere.
55 if (flag_checking)
56 {
57 basic_block bb;
58 FOR_ALL_BB_FN (bb, cfun)
59 {
60 edge_iterator ei;
61 edge e;
62 FOR_EACH_EDGE (e, ei, bb->succs)
63 gcc_checking_assert ((e->flags & non_executable_edge_flag) == 0);
64 }
65 }
66 }
67
~gimple_ranger()68 gimple_ranger::~gimple_ranger ()
69 {
70 m_stmt_list.release ();
71 }
72
73 bool
range_of_expr(irange & r,tree expr,gimple * stmt)74 gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
75 {
76 unsigned idx;
77 if (!gimple_range_ssa_p (expr))
78 return get_tree_range (r, expr, stmt);
79
80 if ((idx = tracer.header ("range_of_expr(")))
81 {
82 print_generic_expr (dump_file, expr, TDF_SLIM);
83 fputs (")", dump_file);
84 if (stmt)
85 {
86 fputs (" at stmt ", dump_file);
87 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
88 }
89 else
90 fputs ("\n", dump_file);
91 }
92
93 // If there is no statement, just get the global value.
94 if (!stmt)
95 {
96 int_range_max tmp;
97 m_cache.get_global_range (r, expr);
98 // Pick up implied context information from the on-entry cache
99 // if current_bb is set. Do not attempt any new calculations.
100 if (current_bb && m_cache.block_range (tmp, current_bb, expr, false))
101 {
102 r.intersect (tmp);
103 char str[80];
104 sprintf (str, "picked up range from bb %d\n",current_bb->index);
105 if (idx)
106 tracer.print (idx, str);
107 }
108 }
109 // For a debug stmt, pick the best value currently available, do not
110 // trigger new value calculations. PR 100781.
111 else if (is_gimple_debug (stmt))
112 m_cache.range_of_expr (r, expr, stmt);
113 else
114 {
115 basic_block bb = gimple_bb (stmt);
116 gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
117
118 // If name is defined in this block, try to get an range from S.
119 if (def_stmt && gimple_bb (def_stmt) == bb)
120 {
121 // Check for a definition override from a block walk.
122 if (!POINTER_TYPE_P (TREE_TYPE (expr))
123 || !m_cache.block_range (r, bb, expr, false))
124 range_of_stmt (r, def_stmt, expr);
125 }
126 // Otherwise OP comes from outside this block, use range on entry.
127 else
128 range_on_entry (r, bb, expr);
129 }
130 if (idx)
131 tracer.trailer (idx, "range_of_expr", true, expr, r);
132 return true;
133 }
134
135 // Return the range of NAME on entry to block BB in R.
136
137 void
range_on_entry(irange & r,basic_block bb,tree name)138 gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name)
139 {
140 int_range_max entry_range;
141 gcc_checking_assert (gimple_range_ssa_p (name));
142
143 unsigned idx;
144 if ((idx = tracer.header ("range_on_entry (")))
145 {
146 print_generic_expr (dump_file, name, TDF_SLIM);
147 fprintf (dump_file, ") to BB %d\n", bb->index);
148 }
149
150 // Start with any known range
151 range_of_stmt (r, SSA_NAME_DEF_STMT (name), name);
152
153 // Now see if there is any on_entry value which may refine it.
154 if (m_cache.block_range (entry_range, bb, name))
155 r.intersect (entry_range);
156
157 if (dom_info_available_p (CDI_DOMINATORS))
158 {
159 basic_block dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
160 if (dom_bb)
161 m_cache.m_non_null.adjust_range (r, name, dom_bb, true);
162 }
163
164 if (idx)
165 tracer.trailer (idx, "range_on_entry", true, name, r);
166 }
167
168 // Calculate the range for NAME at the end of block BB and return it in R.
169 // Return false if no range can be calculated.
170
171 void
range_on_exit(irange & r,basic_block bb,tree name)172 gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name)
173 {
174 // on-exit from the exit block?
175 gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
176 gcc_checking_assert (gimple_range_ssa_p (name));
177
178 unsigned idx;
179 if ((idx = tracer.header ("range_on_exit (")))
180 {
181 print_generic_expr (dump_file, name, TDF_SLIM);
182 fprintf (dump_file, ") from BB %d\n", bb->index);
183 }
184
185 gimple *s = SSA_NAME_DEF_STMT (name);
186 basic_block def_bb = gimple_bb (s);
187 // If this is not the definition block, get the range on the last stmt in
188 // the block... if there is one.
189 if (def_bb != bb)
190 s = last_stmt (bb);
191 // If there is no statement provided, get the range_on_entry for this block.
192 if (s)
193 range_of_expr (r, name, s);
194 else
195 range_on_entry (r, bb, name);
196 gcc_checking_assert (r.undefined_p ()
197 || range_compatible_p (r.type (), TREE_TYPE (name)));
198
199 if (idx)
200 tracer.trailer (idx, "range_on_exit", true, name, r);
201 }
202
203 // Calculate a range for NAME on edge E and return it in R.
204
205 bool
range_on_edge(irange & r,edge e,tree name)206 gimple_ranger::range_on_edge (irange &r, edge e, tree name)
207 {
208 int_range_max edge_range;
209 gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name)));
210
211 // Do not process values along abnormal edges.
212 if (e->flags & EDGE_ABNORMAL)
213 return get_tree_range (r, name, NULL);
214
215 unsigned idx;
216 if ((idx = tracer.header ("range_on_edge (")))
217 {
218 print_generic_expr (dump_file, name, TDF_SLIM);
219 fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index);
220 }
221
222 // Check to see if the edge is executable.
223 if ((e->flags & non_executable_edge_flag))
224 {
225 r.set_undefined ();
226 if (idx)
227 tracer.trailer (idx, "range_on_edge [Unexecutable] ", true,
228 name, r);
229 return true;
230 }
231
232 bool res = true;
233 if (!gimple_range_ssa_p (name))
234 res = get_tree_range (r, name, NULL);
235 else
236 {
237 range_on_exit (r, e->src, name);
238 // If this is not an abnormal edge, check for a non-null exit .
239 if ((e->flags & (EDGE_EH | EDGE_ABNORMAL)) == 0)
240 m_cache.m_non_null.adjust_range (r, name, e->src, false);
241 gcc_checking_assert (r.undefined_p ()
242 || range_compatible_p (r.type(), TREE_TYPE (name)));
243
244 // Check to see if NAME is defined on edge e.
245 if (m_cache.range_on_edge (edge_range, e, name))
246 r.intersect (edge_range);
247 }
248
249 if (idx)
250 tracer.trailer (idx, "range_on_edge", res, name, r);
251 return res;
252 }
253
254 // fold_range wrapper for range_of_stmt to use as an internal client.
255
256 bool
fold_range_internal(irange & r,gimple * s,tree name)257 gimple_ranger::fold_range_internal (irange &r, gimple *s, tree name)
258 {
259 fold_using_range f;
260 fur_depend src (s, &(gori ()), this);
261 return f.fold_stmt (r, s, src, name);
262 }
263
264 // Calculate a range for statement S and return it in R. If NAME is
265 // provided it represents the SSA_NAME on the LHS of the statement.
266 // It is only required if there is more than one lhs/output. Check
267 // the global cache for NAME first to see if the evaluation can be
268 // avoided. If a range cannot be calculated, return false and UNDEFINED.
269
270 bool
range_of_stmt(irange & r,gimple * s,tree name)271 gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
272 {
273 bool res;
274 r.set_undefined ();
275
276 unsigned idx;
277 if ((idx = tracer.header ("range_of_stmt (")))
278 {
279 if (name)
280 print_generic_expr (dump_file, name, TDF_SLIM);
281 fputs (") at stmt ", dump_file);
282 print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
283 }
284
285 if (!name)
286 name = gimple_get_lhs (s);
287
288 // If no name, simply call the base routine.
289 if (!name)
290 {
291 res = fold_range_internal (r, s, NULL_TREE);
292 if (res && is_a <gcond *> (s))
293 {
294 // Update any exports in the cache if this is a gimple cond statement.
295 tree exp;
296 basic_block bb = gimple_bb (s);
297 FOR_EACH_GORI_EXPORT_NAME (m_cache.m_gori, bb, exp)
298 m_cache.propagate_updated_value (exp, bb);
299 }
300 }
301 else if (!gimple_range_ssa_p (name))
302 res = get_tree_range (r, name, NULL);
303 else
304 {
305 bool current;
306 // Check if the stmt has already been processed.
307 if (m_cache.get_global_range (r, name, current))
308 {
309 // If it isn't stale, use this cached value.
310 if (current)
311 {
312 if (idx)
313 tracer.trailer (idx, " cached", true, name, r);
314 return true;
315 }
316 }
317 else
318 prefill_stmt_dependencies (name);
319
320 // Calculate a new value.
321 int_range_max tmp;
322 fold_range_internal (tmp, s, name);
323
324 // Combine the new value with the old value. This is required because
325 // the way value propagation works, when the IL changes on the fly we
326 // can sometimes get different results. See PR 97741.
327 r.intersect (tmp);
328 m_cache.set_global_range (name, r);
329 res = true;
330 }
331
332 if (idx)
333 tracer.trailer (idx, "range_of_stmt", res, name, r);
334 return res;
335 }
336
337
338 // Check if NAME is a dependency that needs resolving, and push it on the
339 // stack if so. R is a scratch range.
340
341 inline void
prefill_name(irange & r,tree name)342 gimple_ranger::prefill_name (irange &r, tree name)
343 {
344 if (!gimple_range_ssa_p (name))
345 return;
346 gimple *stmt = SSA_NAME_DEF_STMT (name);
347 if (!gimple_range_handler (stmt) && !is_a<gphi *> (stmt))
348 return;
349
350 bool current;
351 // If this op has not been processed yet, then push it on the stack
352 if (!m_cache.get_global_range (r, name, current))
353 m_stmt_list.safe_push (name);
354 }
355
356 // This routine will seed the global cache with most of the depnedencies of
357 // NAME. This prevents excessive call depth through the normal API.
358
359 void
prefill_stmt_dependencies(tree ssa)360 gimple_ranger::prefill_stmt_dependencies (tree ssa)
361 {
362 if (SSA_NAME_IS_DEFAULT_DEF (ssa))
363 return;
364
365 int_range_max r;
366 unsigned idx;
367 gimple *stmt = SSA_NAME_DEF_STMT (ssa);
368 gcc_checking_assert (stmt && gimple_bb (stmt));
369
370 // Only pre-process range-ops and phis.
371 if (!gimple_range_handler (stmt) && !is_a<gphi *> (stmt))
372 return;
373
374 // Mark where on the stack we are starting.
375 unsigned start = m_stmt_list.length ();
376 m_stmt_list.safe_push (ssa);
377
378 idx = tracer.header ("ROS dependence fill\n");
379
380 // Loop until back at the start point.
381 while (m_stmt_list.length () > start)
382 {
383 tree name = m_stmt_list.last ();
384 // NULL is a marker which indicates the next name in the stack has now
385 // been fully resolved, so we can fold it.
386 if (!name)
387 {
388 // Pop the NULL, then pop the name.
389 m_stmt_list.pop ();
390 name = m_stmt_list.pop ();
391 // Don't fold initial request, it will be calculated upon return.
392 if (m_stmt_list.length () > start)
393 {
394 // Fold and save the value for NAME.
395 stmt = SSA_NAME_DEF_STMT (name);
396 fold_range_internal (r, stmt, name);
397 // Make sure we don't lose any current global info.
398 int_range_max tmp;
399 m_cache.get_global_range (tmp, name);
400 r.intersect (tmp);
401 m_cache.set_global_range (name, r);
402 }
403 continue;
404 }
405
406 // Add marker indicating previous NAME in list should be folded
407 // when we get to this NULL.
408 m_stmt_list.safe_push (NULL_TREE);
409 stmt = SSA_NAME_DEF_STMT (name);
410
411 if (idx)
412 {
413 tracer.print (idx, "ROS dep fill (");
414 print_generic_expr (dump_file, name, TDF_SLIM);
415 fputs (") at stmt ", dump_file);
416 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
417 }
418
419 gphi *phi = dyn_cast <gphi *> (stmt);
420 if (phi)
421 {
422 for (unsigned x = 0; x < gimple_phi_num_args (phi); x++)
423 prefill_name (r, gimple_phi_arg_def (phi, x));
424 }
425 else
426 {
427 gcc_checking_assert (gimple_range_handler (stmt));
428 tree op = gimple_range_operand2 (stmt);
429 if (op)
430 prefill_name (r, op);
431 op = gimple_range_operand1 (stmt);
432 if (op)
433 prefill_name (r, op);
434 }
435 }
436 if (idx)
437 tracer.trailer (idx, "ROS ", false, ssa, r);
438 }
439
440
441 // This routine will invoke the gimple fold_stmt routine, providing context to
442 // range_of_expr calls via an private interal API.
443
444 bool
fold_stmt(gimple_stmt_iterator * gsi,tree (* valueize)(tree))445 gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
446 {
447 gimple *stmt = gsi_stmt (*gsi);
448 current_bb = gimple_bb (stmt);
449 bool ret = ::fold_stmt (gsi, valueize);
450 current_bb = NULL;
451 return ret;
452 }
453
454 // Called during dominator walks to register any side effects that take effect
455 // from this point forward. Current release is only for tracking non-null
456 // within a block.
457
458 void
register_side_effects(gimple * s)459 gimple_ranger::register_side_effects (gimple *s)
460 {
461 m_cache.block_apply_nonnull (s);
462 }
463
464 // This routine will export whatever global ranges are known to GCC
465 // SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
466
467 void
export_global_ranges()468 gimple_ranger::export_global_ranges ()
469 {
470 /* Cleared after the table header has been printed. */
471 bool print_header = true;
472 for (unsigned x = 1; x < num_ssa_names; x++)
473 {
474 int_range_max r;
475 tree name = ssa_name (x);
476 if (name && !SSA_NAME_IN_FREE_LIST (name)
477 && gimple_range_ssa_p (name)
478 && m_cache.get_global_range (r, name)
479 && !r.varying_p())
480 {
481 bool updated = update_global_range (r, name);
482 if (!updated || !dump_file)
483 continue;
484
485 if (print_header)
486 {
487 /* Print the header only when there's something else
488 to print below. */
489 fprintf (dump_file, "Exported global range table:\n");
490 fprintf (dump_file, "============================\n");
491 print_header = false;
492 }
493
494 value_range vr = r;
495 print_generic_expr (dump_file, name , TDF_SLIM);
496 fprintf (dump_file, " : ");
497 vr.dump (dump_file);
498 fprintf (dump_file, "\n");
499 int_range_max same = vr;
500 if (same != r)
501 {
502 fprintf (dump_file, " irange : ");
503 r.dump (dump_file);
504 fprintf (dump_file, "\n");
505 }
506 }
507 }
508 }
509
510 // Print the known table values to file F.
511
512 void
dump_bb(FILE * f,basic_block bb)513 gimple_ranger::dump_bb (FILE *f, basic_block bb)
514 {
515 unsigned x;
516 edge_iterator ei;
517 edge e;
518 int_range_max range, tmp_range;
519 fprintf (f, "\n=========== BB %d ============\n", bb->index);
520 m_cache.dump_bb (f, bb);
521
522 ::dump_bb (f, bb, 4, TDF_NONE);
523
524 // Now find any globals defined in this block.
525 for (x = 1; x < num_ssa_names; x++)
526 {
527 tree name = ssa_name (x);
528 if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) &&
529 gimple_bb (SSA_NAME_DEF_STMT (name)) == bb &&
530 m_cache.get_global_range (range, name))
531 {
532 if (!range.varying_p ())
533 {
534 print_generic_expr (f, name, TDF_SLIM);
535 fprintf (f, " : ");
536 range.dump (f);
537 fprintf (f, "\n");
538 }
539
540 }
541 }
542
543 // And now outgoing edges, if they define anything.
544 FOR_EACH_EDGE (e, ei, bb->succs)
545 {
546 for (x = 1; x < num_ssa_names; x++)
547 {
548 tree name = gimple_range_ssa_p (ssa_name (x));
549 if (name && gori ().has_edge_range_p (name, e)
550 && m_cache.range_on_edge (range, e, name))
551 {
552 gimple *s = SSA_NAME_DEF_STMT (name);
553 // Only print the range if this is the def block, or
554 // the on entry cache for either end of the edge is
555 // set.
556 if ((s && bb == gimple_bb (s)) ||
557 m_cache.block_range (tmp_range, bb, name, false) ||
558 m_cache.block_range (tmp_range, e->dest, name, false))
559 {
560 if (!range.varying_p ())
561 {
562 fprintf (f, "%d->%d ", e->src->index,
563 e->dest->index);
564 char c = ' ';
565 if (e->flags & EDGE_TRUE_VALUE)
566 fprintf (f, " (T)%c", c);
567 else if (e->flags & EDGE_FALSE_VALUE)
568 fprintf (f, " (F)%c", c);
569 else
570 fprintf (f, " ");
571 print_generic_expr (f, name, TDF_SLIM);
572 fprintf(f, " : \t");
573 range.dump(f);
574 fprintf (f, "\n");
575 }
576 }
577 }
578 }
579 }
580 }
581
582 // Print the known table values to file F.
583
584 void
dump(FILE * f)585 gimple_ranger::dump (FILE *f)
586 {
587 basic_block bb;
588
589 FOR_EACH_BB_FN (bb, cfun)
590 dump_bb (f, bb);
591
592 m_cache.dump (f);
593 }
594
595 void
debug()596 gimple_ranger::debug ()
597 {
598 dump (stderr);
599 }
600
601 /* Create a new ranger instance and associate it with function FUN.
602 Each call must be paired with a call to disable_ranger to release
603 resources. */
604
605 gimple_ranger *
enable_ranger(struct function * fun)606 enable_ranger (struct function *fun)
607 {
608 gimple_ranger *r;
609
610 gcc_checking_assert (!fun->x_range_query);
611 r = new gimple_ranger;
612 fun->x_range_query = r;
613
614 return r;
615 }
616
617 /* Destroy and release the ranger instance associated with function FUN
618 and replace it the global ranger. */
619
620 void
disable_ranger(struct function * fun)621 disable_ranger (struct function *fun)
622 {
623 gcc_checking_assert (fun->x_range_query);
624 delete fun->x_range_query;
625 fun->x_range_query = NULL;
626 }
627