1/* Code for GIMPLE range related routines.
2 Copyright (C) 2019-2023 Free Software Foundation, Inc.
3 Contributed by Andrew MacLeod <amacleod@redhat.com>
4 and Aldy Hernandez <aldyh@redhat.com>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
40gimple_ranger::gimple_ranger (bool use_imm_uses) :
41 non_executable_edge_flag (cfun),
42 m_cache (non_executable_edge_flag, use_imm_uses),
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 (nelems: 0);
51 m_stmt_list.safe_grow (num_ssa_names);
52 m_stmt_list.truncate (size: 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
68gimple_ranger::~gimple_ranger ()
69{
70 m_stmt_list.release ();
71}
72
73// Return a range_query which accesses just the known global values.
74
75range_query &
76gimple_ranger::const_query ()
77{
78 return m_cache.const_query ();
79}
80
81bool
82gimple_ranger::range_of_expr (vrange &r, tree expr, gimple *stmt)
83{
84 unsigned idx;
85 if (!gimple_range_ssa_p (exp: expr))
86 return get_tree_range (v&: r, expr, stmt);
87
88 if ((idx = tracer.header (str: "range_of_expr(")))
89 {
90 print_generic_expr (dump_file, expr, TDF_SLIM);
91 fputs (s: ")", stream: dump_file);
92 if (stmt)
93 {
94 fputs (s: " at stmt ", stream: dump_file);
95 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
96 }
97 else
98 fputs (s: "\n", stream: dump_file);
99 }
100
101 // If there is no statement, just get the global value.
102 if (!stmt)
103 {
104 Value_Range tmp (TREE_TYPE (expr));
105 m_cache.get_global_range (r, name: 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 (r&: tmp, bb: current_bb, name: expr, calc: false))
109 {
110 r.intersect (tmp);
111 char str[80];
112 sprintf (s: str, format: "picked up range from bb %d\n",current_bb->index);
113 if (idx)
114 tracer.print (counter: idx, str);
115 }
116 }
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 (gs: stmt))
120 m_cache.range_of_expr (r, name: expr, stmt);
121 else
122 {
123 basic_block bb = gimple_bb (g: stmt);
124 gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
125
126 // If name is defined in this block, try to get an range from S.
127 if (def_stmt && gimple_bb (g: def_stmt) == bb)
128 {
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, name: expr))
132 m_cache.block_range (r, bb, name: expr, calc: false);
133 else
134 range_of_stmt (r, def_stmt, name: expr);
135 }
136 // Otherwise OP comes from outside this block, use range on entry.
137 else
138 range_on_entry (r, bb, name: expr);
139 }
140 if (idx)
141 tracer.trailer (counter: idx, caller: "range_of_expr", result: true, name: expr, r);
142 return true;
143}
144
145// Return the range of NAME on entry to block BB in R.
146
147void
148gimple_ranger::range_on_entry (vrange &r, basic_block bb, tree name)
149{
150 Value_Range entry_range (TREE_TYPE (name));
151 gcc_checking_assert (gimple_range_ssa_p (name));
152
153 unsigned idx;
154 if ((idx = tracer.header (str: "range_on_entry (")))
155 {
156 print_generic_expr (dump_file, name, TDF_SLIM);
157 fprintf (stream: dump_file, format: ") to BB %d\n", bb->index);
158 }
159
160 // Start with any known range
161 range_of_stmt (r, SSA_NAME_DEF_STMT (name), name);
162
163 // Now see if there is any on_entry value which may refine it.
164 if (m_cache.block_range (r&: entry_range, bb, name))
165 r.intersect (entry_range);
166
167 if (idx)
168 tracer.trailer (counter: idx, caller: "range_on_entry", result: true, name, r);
169}
170
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.
173
174void
175gimple_ranger::range_on_exit (vrange &r, basic_block bb, tree name)
176{
177 // on-exit from the exit block?
178 gcc_checking_assert (gimple_range_ssa_p (name));
179
180 unsigned idx;
181 if ((idx = tracer.header (str: "range_on_exit (")))
182 {
183 print_generic_expr (dump_file, name, TDF_SLIM);
184 fprintf (stream: dump_file, format: ") from BB %d\n", bb->index);
185 }
186
187 gimple *s = SSA_NAME_DEF_STMT (name);
188 basic_block def_bb = gimple_bb (g: s);
189 // If this is not the definition block, get the range on the last stmt in
190 // the block... if there is one.
191 if (def_bb != bb)
192 s = last_nondebug_stmt (bb);
193 // If there is no statement provided, get the range_on_entry for this block.
194 if (s)
195 range_of_expr (r, expr: name, stmt: s);
196 else
197 range_on_entry (r, bb, name);
198 gcc_checking_assert (r.undefined_p ()
199 || range_compatible_p (r.type (), TREE_TYPE (name)));
200
201 if (idx)
202 tracer.trailer (counter: idx, caller: "range_on_exit", result: true, name, r);
203}
204
205// Calculate a range for NAME on edge E and return it in R.
206
207bool
208gimple_ranger::range_on_edge (vrange &r, edge e, tree name)
209{
210 Value_Range edge_range (TREE_TYPE (name));
211
212 if (!r.supports_type_p (TREE_TYPE (name)))
213 return false;
214
215 // Do not process values along abnormal edges.
216 if (e->flags & EDGE_ABNORMAL)
217 return get_tree_range (v&: r, expr: name, NULL);
218
219 unsigned idx;
220 if ((idx = tracer.header (str: "range_on_edge (")))
221 {
222 print_generic_expr (dump_file, name, TDF_SLIM);
223 fprintf (stream: dump_file, format: ") on edge %d->%d\n", e->src->index, e->dest->index);
224 }
225
226 // Check to see if the edge is executable.
227 if ((e->flags & non_executable_edge_flag))
228 {
229 r.set_undefined ();
230 if (idx)
231 tracer.trailer (counter: idx, caller: "range_on_edge [Unexecutable] ", result: true,
232 name, r);
233 return true;
234 }
235
236 bool res = true;
237 if (!gimple_range_ssa_p (exp: name))
238 res = get_tree_range (v&: r, expr: name, NULL);
239 else
240 {
241 range_on_exit (r, bb: 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, bb: e->src);
245 gcc_checking_assert (r.undefined_p ()
246 || range_compatible_p (r.type(), TREE_TYPE (name)));
247
248 // Check to see if NAME is defined on edge e.
249 if (m_cache.range_on_edge (r&: edge_range, e, expr: name))
250 r.intersect (edge_range);
251 }
252
253 if (idx)
254 tracer.trailer (counter: idx, caller: "range_on_edge", result: res, name, r);
255 return res;
256}
257
258// fold_range wrapper for range_of_stmt to use as an internal client.
259
260bool
261gimple_ranger::fold_range_internal (vrange &r, gimple *s, tree name)
262{
263 fold_using_range f;
264 fur_depend src (s, &(gori ()), this);
265 return f.fold_stmt (r, s, src, name);
266}
267
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.
273
274bool
275gimple_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
276{
277 bool res;
278 r.set_undefined ();
279
280 unsigned idx;
281 if ((idx = tracer.header (str: "range_of_stmt (")))
282 {
283 if (name)
284 print_generic_expr (dump_file, name, TDF_SLIM);
285 fputs (s: ") at stmt ", stream: dump_file);
286 print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
287 }
288
289 if (!name)
290 name = gimple_get_lhs (s);
291
292 // If no name, simply call the base routine.
293 if (!name)
294 {
295 res = fold_range_internal (r, s, NULL_TREE);
296 if (res && is_a <gcond *> (p: s))
297 {
298 // Update any exports in the cache if this is a gimple cond statement.
299 tree exp;
300 basic_block bb = gimple_bb (g: s);
301 FOR_EACH_GORI_EXPORT_NAME (m_cache.m_gori, bb, exp)
302 m_cache.propagate_updated_value (name: exp, bb);
303 }
304 }
305 else if (!gimple_range_ssa_p (exp: name))
306 res = get_tree_range (v&: r, expr: name, NULL);
307 else
308 {
309 bool current;
310 // Check if the stmt has already been processed.
311 if (m_cache.get_global_range (r, name, current_p&: current))
312 {
313 // If it isn't stale, use this cached value.
314 if (current)
315 {
316 if (idx)
317 tracer.trailer (counter: idx, caller: " cached", result: true, name, r);
318 return true;
319 }
320 }
321 else
322 prefill_stmt_dependencies (ssa: name);
323
324 // Calculate a new value.
325 Value_Range tmp (TREE_TYPE (name));
326 fold_range_internal (r&: tmp, s, name);
327
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);
333 res = true;
334 }
335
336 if (idx)
337 tracer.trailer (counter: idx, caller: "range_of_stmt", result: res, name, r);
338 return res;
339}
340
341
342// Check if NAME is a dependency that needs resolving, and push it on the
343// stack if so. R is a scratch range.
344
345inline void
346gimple_ranger::prefill_name (vrange &r, tree name)
347{
348 if (!gimple_range_ssa_p (exp: name))
349 return;
350 gimple *stmt = SSA_NAME_DEF_STMT (name);
351 if (!gimple_range_op_handler::supported_p (s: stmt) && !is_a<gphi *> (p: stmt))
352 return;
353
354 // If this op has not been processed yet, then push it on the stack
355 if (!m_cache.get_global_range (r, name))
356 {
357 bool current;
358 // Set the global cache value and mark as alway_current.
359 m_cache.get_global_range (r, name, current_p&: current);
360 m_stmt_list.safe_push (obj: name);
361 }
362}
363
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.
366
367void
368gimple_ranger::prefill_stmt_dependencies (tree ssa)
369{
370 if (SSA_NAME_IS_DEFAULT_DEF (ssa))
371 return;
372
373 unsigned idx;
374 gimple *stmt = SSA_NAME_DEF_STMT (ssa);
375 gcc_checking_assert (stmt && gimple_bb (stmt));
376
377 // Only pre-process range-ops and phis.
378 if (!gimple_range_op_handler::supported_p (s: stmt) && !is_a<gphi *> (p: stmt))
379 return;
380
381 // Mark where on the stack we are starting.
382 unsigned start = m_stmt_list.length ();
383 m_stmt_list.safe_push (obj: ssa);
384
385 idx = tracer.header (str: "ROS dependence fill\n");
386
387 // Loop until back at the start point.
388 while (m_stmt_list.length () > start)
389 {
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.
393 if (!name)
394 {
395 // Pop the NULL, then pop the name.
396 m_stmt_list.pop ();
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)
400 {
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, s: 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 (r&: tmp, name);
408 bool changed = tmp.intersect (r);
409 m_cache.set_global_range (name, r: tmp, changed);
410 }
411 continue;
412 }
413
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);
418
419 if (idx)
420 {
421 tracer.print (counter: idx, str: "ROS dep fill (");
422 print_generic_expr (dump_file, name, TDF_SLIM);
423 fputs (s: ") at stmt ", stream: dump_file);
424 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
425 }
426
427 gphi *phi = dyn_cast <gphi *> (p: stmt);
428 if (phi)
429 {
430 Value_Range r (TREE_TYPE (gimple_phi_result (phi)));
431 for (unsigned x = 0; x < gimple_phi_num_args (gs: phi); x++)
432 prefill_name (r, name: gimple_phi_arg_def (gs: phi, index: x));
433 }
434 else
435 {
436 gimple_range_op_handler handler (stmt);
437 if (handler)
438 {
439 tree op = handler.operand2 ();
440 if (op)
441 {
442 Value_Range r (TREE_TYPE (op));
443 prefill_name (r, name: op);
444 }
445 op = handler.operand1 ();
446 if (op)
447 {
448 Value_Range r (TREE_TYPE (op));
449 prefill_name (r, name: op);
450 }
451 }
452 }
453 }
454 if (idx)
455 {
456 unsupported_range r;
457 tracer.trailer (counter: idx, caller: "ROS ", result: false, name: ssa, r);
458 }
459}
460
461
462// This routine will invoke the gimple fold_stmt routine, providing context to
463// range_of_expr calls via an private internal API.
464
465bool
466gimple_ranger::fold_stmt (gimple_stmt_iterator *gsi, tree (*valueize) (tree))
467{
468 gimple *stmt = gsi_stmt (i: *gsi);
469 current_bb = gimple_bb (g: stmt);
470 bool ret = ::fold_stmt (gsi, valueize);
471 current_bb = NULL;
472 return ret;
473}
474
475// Called during dominator walks to register any inferred ranges that take
476// effect from this point forward.
477
478void
479gimple_ranger::register_inferred_ranges (gimple *s)
480{
481 // First, export the LHS if it is a new global range.
482 tree lhs = gimple_get_lhs (s);
483 if (lhs)
484 {
485 Value_Range tmp (TREE_TYPE (lhs));
486 if (range_of_stmt (r&: tmp, s, name: lhs) && !tmp.varying_p ()
487 && set_range_info (lhs, tmp) && dump_file)
488 {
489 fprintf (stream: dump_file, format: "Global Exported: ");
490 print_generic_expr (dump_file, lhs, TDF_SLIM);
491 fprintf (stream: dump_file, format: " = ");
492 tmp.dump (dump_file);
493 fputc (c: '\n', stream: dump_file);
494 }
495 }
496 m_cache.apply_inferred_ranges (s);
497}
498
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.
502
503void
504gimple_ranger::register_transitive_inferred_ranges (basic_block bb)
505{
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))
509 return;
510
511 if (dump_file && (dump_flags & TDF_DETAILS))
512 fprintf (stream: dump_file, format: "Checking for transitive inferred ranges in BB %d\n",
513 bb->index);
514
515 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (i: si);
516 gsi_next (i: &si))
517 {
518 gimple *s = gsi_stmt (i: 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 (exp: lhs) || infer.has_range_p (name: lhs, bb))
522 continue;
523 // Pick up global value.
524 Value_Range g (TREE_TYPE (lhs));
525 range_of_expr (r&: g, expr: lhs);
526
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));
531 r.set_undefined ();
532 tree name1 = gori ().depend1 (name: lhs);
533 tree name2 = gori ().depend2 (name: lhs);
534 if ((name1 && infer.has_range_p (name: name1, bb))
535 || (name2 && infer.has_range_p (name: name2, bb)))
536 {
537 // Check if folding S produces a different result.
538 if (fold_range (r, s, q: this) && g != r)
539 {
540 infer.add_range (name: lhs, bb, r);
541 m_cache.register_inferred_value (r, name: lhs, bb);
542 }
543 }
544 }
545}
546
547// When a statement S has changed since the result was cached, re-evaluate
548// and update the global cache.
549
550void
551gimple_ranger::update_stmt (gimple *s)
552{
553 tree lhs = gimple_get_lhs (s);
554 if (!lhs || !gimple_range_ssa_p (exp: lhs))
555 return;
556 Value_Range r (TREE_TYPE (lhs));
557 // Only update if it already had a value.
558 if (m_cache.get_global_range (r, name: lhs))
559 {
560 // Re-calculate a new value using just cache values.
561 Value_Range tmp (TREE_TYPE (lhs));
562 fold_using_range f;
563 fur_stmt src (s, &m_cache);
564 f.fold_stmt (r&: tmp, s, src, name: lhs);
565
566 // Combine the new value with the old value to check for a change.
567 if (r.intersect (r: tmp))
568 {
569 if (dump_file && (dump_flags & TDF_DETAILS))
570 {
571 print_generic_expr (dump_file, lhs, TDF_SLIM);
572 fprintf (stream: dump_file, format: " : global value re-evaluated to ");
573 r.dump (dump_file);
574 fputc (c: '\n', stream: dump_file);
575 }
576 m_cache.set_global_range (name: lhs, r);
577 }
578 }
579}
580
581// This routine will export whatever global ranges are known to GCC
582// SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
583
584void
585gimple_ranger::export_global_ranges ()
586{
587 /* Cleared after the table header has been printed. */
588 bool print_header = true;
589 for (unsigned x = 1; x < num_ssa_names; x++)
590 {
591 tree name = ssa_name (x);
592 if (!name)
593 continue;
594 Value_Range r (TREE_TYPE (name));
595 if (name && !SSA_NAME_IN_FREE_LIST (name)
596 && gimple_range_ssa_p (exp: name)
597 && m_cache.get_global_range (r, name)
598 && !r.varying_p())
599 {
600 bool updated = set_range_info (name, r);
601 if (!updated || !dump_file)
602 continue;
603
604 if (print_header)
605 {
606 /* Print the header only when there's something else
607 to print below. */
608 fprintf (stream: dump_file, format: "Exported global range table:\n");
609 fprintf (stream: dump_file, format: "============================\n");
610 print_header = false;
611 }
612
613 print_generic_expr (dump_file, name , TDF_SLIM);
614 fprintf (stream: dump_file, format: " : ");
615 r.dump (dump_file);
616 fprintf (stream: dump_file, format: "\n");
617 }
618 }
619}
620
621// Print the known table values to file F.
622
623void
624gimple_ranger::dump_bb (FILE *f, basic_block bb)
625{
626 unsigned x;
627 edge_iterator ei;
628 edge e;
629 fprintf (stream: f, format: "\n=========== BB %d ============\n", bb->index);
630 m_cache.dump_bb (f, bb);
631
632 ::dump_bb (f, bb, 4, TDF_NONE);
633
634 // Now find any globals defined in this block.
635 for (x = 1; x < num_ssa_names; x++)
636 {
637 tree name = ssa_name (x);
638 if (!gimple_range_ssa_p (exp: name) || !SSA_NAME_DEF_STMT (name))
639 continue;
640 Value_Range range (TREE_TYPE (name));
641 if (gimple_bb (SSA_NAME_DEF_STMT (name)) == bb
642 && m_cache.get_global_range (r&: range, name))
643 {
644 if (!range.varying_p ())
645 {
646 print_generic_expr (f, name, TDF_SLIM);
647 fprintf (stream: f, format: " : ");
648 range.dump (f);
649 fprintf (stream: f, format: "\n");
650 }
651
652 }
653 }
654
655 // And now outgoing edges, if they define anything.
656 FOR_EACH_EDGE (e, ei, bb->succs)
657 {
658 for (x = 1; x < num_ssa_names; x++)
659 {
660 tree name = gimple_range_ssa_p (ssa_name (x));
661 if (!name || !gori ().has_edge_range_p (name, e))
662 continue;
663
664 Value_Range range (TREE_TYPE (name));
665 if (m_cache.range_on_edge (r&: range, e, expr: name))
666 {
667 gimple *s = SSA_NAME_DEF_STMT (name);
668 Value_Range tmp_range (TREE_TYPE (name));
669 // Only print the range if this is the def block, or
670 // the on entry cache for either end of the edge is
671 // set.
672 if ((s && bb == gimple_bb (g: s)) ||
673 m_cache.block_range (r&: tmp_range, bb, name, calc: false) ||
674 m_cache.block_range (r&: tmp_range, bb: e->dest, name, calc: false))
675 {
676 if (!range.varying_p ())
677 {
678 fprintf (stream: f, format: "%d->%d ", e->src->index,
679 e->dest->index);
680 char c = ' ';
681 if (e->flags & EDGE_TRUE_VALUE)
682 fprintf (stream: f, format: " (T)%c", c);
683 else if (e->flags & EDGE_FALSE_VALUE)
684 fprintf (stream: f, format: " (F)%c", c);
685 else
686 fprintf (stream: f, format: " ");
687 print_generic_expr (f, name, TDF_SLIM);
688 fprintf(stream: f, format: " : \t");
689 range.dump(f);
690 fprintf (stream: f, format: "\n");
691 }
692 }
693 }
694 }
695 }
696}
697
698// Print the known table values to file F.
699
700void
701gimple_ranger::dump (FILE *f)
702{
703 basic_block bb;
704
705 FOR_EACH_BB_FN (bb, cfun)
706 dump_bb (f, bb);
707
708 m_cache.dump (f);
709}
710
711void
712gimple_ranger::debug ()
713{
714 dump (stderr);
715}
716
717/* Create a new ranger instance and associate it with function FUN.
718 Each call must be paired with a call to disable_ranger to release
719 resources. */
720
721gimple_ranger *
722enable_ranger (struct function *fun, bool use_imm_uses)
723{
724 gimple_ranger *r;
725
726 gcc_checking_assert (!fun->x_range_query);
727 r = new gimple_ranger (use_imm_uses);
728 fun->x_range_query = r;
729
730 return r;
731}
732
733/* Destroy and release the ranger instance associated with function FUN
734 and replace it the global ranger. */
735
736void
737disable_ranger (struct function *fun)
738{
739 gcc_checking_assert (fun->x_range_query);
740 delete fun->x_range_query;
741 fun->x_range_query = NULL;
742}
743
744// ------------------------------------------------------------------------
745
746// If there is a non-varying value associated with NAME, return true and the
747// range in R.
748
749bool
750assume_query::assume_range_p (vrange &r, tree name)
751{
752 if (global.get_range (r, name))
753 return !r.varying_p ();
754 return false;
755}
756
757// Query used by GORI to pick up any known value on entry to a block.
758
759bool
760assume_query::range_of_expr (vrange &r, tree expr, gimple *stmt)
761{
762 if (!gimple_range_ssa_p (exp: expr))
763 return get_tree_range (v&: r, expr, stmt);
764
765 if (!global.get_range (r, name: expr))
766 r.set_varying (TREE_TYPE (expr));
767 return true;
768}
769
770// If the current function returns an integral value, and has a single return
771// statement, it will calculate any SSA_NAMES it can determine ranges for
772// assuming the function returns 1.
773
774assume_query::assume_query ()
775{
776 basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
777 if (single_pred_p (bb: exit_bb))
778 {
779 basic_block bb = single_pred (bb: exit_bb);
780 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
781 if (gsi_end_p (i: gsi))
782 return;
783 gimple *s = gsi_stmt (i: gsi);
784 if (!is_a<greturn *> (p: s))
785 return;
786 greturn *gret = as_a<greturn *> (p: s);
787 tree op = gimple_return_retval (gs: gret);
788 if (!gimple_range_ssa_p (exp: op))
789 return;
790 tree lhs_type = TREE_TYPE (op);
791 if (!irange::supports_p (type: lhs_type))
792 return;
793
794 unsigned prec = TYPE_PRECISION (lhs_type);
795 int_range<2> lhs_range (lhs_type, wi::one (precision: prec), wi::one (precision: prec));
796 global.set_range (name: op, r: lhs_range);
797
798 gimple *def = SSA_NAME_DEF_STMT (op);
799 if (!def || gimple_get_lhs (def) != op)
800 return;
801 fur_stmt src (gret, this);
802 calculate_stmt (s: def, lhs_range, src);
803 }
804}
805
806// Evaluate operand OP on statement S, using the provided LHS range.
807// If successful, set the range in the global table, then visit OP's def stmt.
808
809void
810assume_query::calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src)
811{
812 Value_Range op_range (TREE_TYPE (op));
813 if (m_gori.compute_operand_range (r&: op_range, stmt: s, lhs, name: op, src)
814 && !op_range.varying_p ())
815 {
816 // Set the global range, merging if there is already a range.
817 global.merge_range (name: op, r: op_range);
818 gimple *def_stmt = SSA_NAME_DEF_STMT (op);
819 if (def_stmt && gimple_get_lhs (def_stmt) == op)
820 calculate_stmt (s: def_stmt, lhs_range&: op_range, src);
821 }
822}
823
824// Evaluate PHI statement, using the provided LHS range.
825// Check each constant argument predecessor if it can be taken
826// provide LHS to any symbolic arguments, and process their def statements.
827
828void
829assume_query::calculate_phi (gphi *phi, vrange &lhs_range, fur_source &src)
830{
831 for (unsigned x= 0; x < gimple_phi_num_args (gs: phi); x++)
832 {
833 tree arg = gimple_phi_arg_def (gs: phi, index: x);
834 Value_Range arg_range (TREE_TYPE (arg));
835 if (gimple_range_ssa_p (exp: arg))
836 {
837 // A symbol arg will be the LHS value.
838 arg_range = lhs_range;
839 range_cast (r&: arg_range, TREE_TYPE (arg));
840 if (!global.get_range (r&: arg_range, name: arg))
841 {
842 global.set_range (name: arg, r: arg_range);
843 gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
844 if (def_stmt && gimple_get_lhs (def_stmt) == arg)
845 calculate_stmt (s: def_stmt, lhs_range&: arg_range, src);
846 }
847 }
848 else if (get_tree_range (v&: arg_range, expr: arg, NULL))
849 {
850 // If this is a constant value that differs from LHS, this
851 // edge cannot be taken.
852 arg_range.intersect (r: lhs_range);
853 if (arg_range.undefined_p ())
854 continue;
855 // Otherwise check the condition feeding this edge.
856 edge e = gimple_phi_arg_edge (phi, i: x);
857 check_taken_edge (e, src);
858 }
859 }
860}
861
862// If an edge is known to be taken, examine the outgoing edge to see
863// if it carries any range information that can also be evaluated.
864
865void
866assume_query::check_taken_edge (edge e, fur_source &src)
867{
868 gimple *stmt = gimple_outgoing_range_stmt_p (bb: e->src);
869 if (stmt && is_a<gcond *> (p: stmt))
870 {
871 int_range<2> cond;
872 gcond_edge_range (r&: cond, e);
873 calculate_stmt (s: stmt, lhs_range&: cond, src);
874 }
875}
876
877// Evaluate statement S which produces range LHS_RANGE.
878
879void
880assume_query::calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src)
881{
882 gimple_range_op_handler handler (s);
883 if (handler)
884 {
885 tree op = gimple_range_ssa_p (exp: handler.operand1 ());
886 if (op)
887 calculate_op (op, s, lhs&: lhs_range, src);
888 op = gimple_range_ssa_p (exp: handler.operand2 ());
889 if (op)
890 calculate_op (op, s, lhs&: lhs_range, src);
891 }
892 else if (is_a<gphi *> (p: s))
893 {
894 calculate_phi (phi: as_a<gphi *> (p: s), lhs_range, src);
895 // Don't further check predecessors of blocks with PHIs.
896 return;
897 }
898
899 // Even if the walk back terminates before the top, if this is a single
900 // predecessor block, see if the predecessor provided any ranges to get here.
901 if (single_pred_p (bb: gimple_bb (g: s)))
902 check_taken_edge (e: single_pred_edge (bb: gimple_bb (g: s)), src);
903}
904
905// Show everything that was calculated.
906
907void
908assume_query::dump (FILE *f)
909{
910 fprintf (stream: f, format: "Assumption details calculated:\n");
911 for (unsigned i = 0; i < num_ssa_names; i++)
912 {
913 tree name = ssa_name (i);
914 if (!name || !gimple_range_ssa_p (exp: name))
915 continue;
916 tree type = TREE_TYPE (name);
917 if (!Value_Range::supports_type_p (type))
918 continue;
919
920 Value_Range assume_range (type);
921 if (assume_range_p (r&: assume_range, name))
922 {
923 print_generic_expr (f, name, TDF_SLIM);
924 fprintf (stream: f, format: " -> ");
925 assume_range.dump (f);
926 fputc (c: '\n', stream: f);
927 }
928 }
929 fprintf (stream: f, format: "------------------------------\n");
930}
931
932// ---------------------------------------------------------------------------
933
934
935// Create a DOM based ranger for use by a DOM walk pass.
936
937dom_ranger::dom_ranger () : m_global (), m_out ()
938{
939 m_freelist.create (nelems: 0);
940 m_freelist.truncate (size: 0);
941 m_e0.create (nelems: 0);
942 m_e0.safe_grow_cleared (last_basic_block_for_fn (cfun));
943 m_e1.create (nelems: 0);
944 m_e1.safe_grow_cleared (last_basic_block_for_fn (cfun));
945 m_pop_list = BITMAP_ALLOC (NULL);
946 if (dump_file && (param_ranger_debug & RANGER_DEBUG_TRACE))
947 tracer.enable_trace ();
948}
949
950// Dispose of a DOM ranger.
951
952dom_ranger::~dom_ranger ()
953{
954 if (dump_file && (dump_flags & TDF_DETAILS))
955 {
956 fprintf (stream: dump_file, format: "Non-varying global ranges:\n");
957 fprintf (stream: dump_file, format: "=========================:\n");
958 m_global.dump (f: dump_file);
959 }
960 BITMAP_FREE (m_pop_list);
961 m_e1.release ();
962 m_e0.release ();
963 m_freelist.release ();
964}
965
966// Implement range of EXPR on stmt S, and return it in R.
967// Return false if no range can be calculated.
968
969bool
970dom_ranger::range_of_expr (vrange &r, tree expr, gimple *s)
971{
972 unsigned idx;
973 if (!gimple_range_ssa_p (exp: expr))
974 return get_tree_range (v&: r, expr, stmt: s);
975
976 if ((idx = tracer.header (str: "range_of_expr ")))
977 {
978 print_generic_expr (dump_file, expr, TDF_SLIM);
979 if (s)
980 {
981 fprintf (stream: dump_file, format: " at ");
982 print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
983 }
984 else
985 fprintf (stream: dump_file, format: "\n");
986 }
987
988 if (s)
989 range_in_bb (r, bb: gimple_bb (g: s), name: expr);
990 else
991 m_global.range_of_expr (r, expr, stmt: s);
992
993 if (idx)
994 tracer.trailer (counter: idx, caller: " ", result: true, name: expr, r);
995 return true;
996}
997
998
999// Return TRUE and the range if edge E has a range set for NAME in
1000// block E->src.
1001
1002bool
1003dom_ranger::edge_range (vrange &r, edge e, tree name)
1004{
1005 bool ret = false;
1006 basic_block bb = e->src;
1007
1008 // Check if BB has any outgoing ranges on edge E.
1009 ssa_lazy_cache *out = NULL;
1010 if (EDGE_SUCC (bb, 0) == e)
1011 out = m_e0[bb->index];
1012 else if (EDGE_SUCC (bb, 1) == e)
1013 out = m_e1[bb->index];
1014
1015 // If there is an edge vector and it has a range, pick it up.
1016 if (out && out->has_range (name))
1017 ret = out->get_range (r, name);
1018
1019 return ret;
1020}
1021
1022
1023// Return the range of EXPR on edge E in R.
1024// Return false if no range can be calculated.
1025
1026bool
1027dom_ranger::range_on_edge (vrange &r, edge e, tree expr)
1028{
1029 basic_block bb = e->src;
1030 unsigned idx;
1031 if ((idx = tracer.header (str: "range_on_edge ")))
1032 {
1033 fprintf (stream: dump_file, format: "%d->%d for ",e->src->index, e->dest->index);
1034 print_generic_expr (dump_file, expr, TDF_SLIM);
1035 fputc (c: '\n',stream: dump_file);
1036 }
1037
1038 if (!gimple_range_ssa_p (exp: expr))
1039 return get_tree_range (v&: r, expr, NULL);
1040
1041 if (!edge_range (r, e, name: expr))
1042 range_in_bb (r, bb, name: expr);
1043
1044 if (idx)
1045 tracer.trailer (counter: idx, caller: " ", result: true, name: expr, r);
1046 return true;
1047}
1048
1049// Return the range of NAME as it exists at the end of block BB in R.
1050
1051void
1052dom_ranger::range_in_bb (vrange &r, basic_block bb, tree name)
1053{
1054 basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (name));
1055 // Loop through dominators until we get to the entry block, or we find
1056 // either the defintion block for NAME, or a single pred edge with a range.
1057 while (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1058 {
1059 // If we hit the deifntion block, pick up the global value.
1060 if (bb == def_bb)
1061 {
1062 m_global.range_of_expr (r, expr: name);
1063 return;
1064 }
1065 // If its a single pred, check the outgoing range of the edge.
1066 if (EDGE_COUNT (bb->preds) == 1
1067 && edge_range (r, EDGE_PRED (bb, 0), name))
1068 return;
1069 // Otherwise move up to the dominator, and check again.
1070 bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1071 }
1072 m_global.range_of_expr (r, expr: name);
1073}
1074
1075
1076// Calculate the range of NAME, as the def of stmt S and return it in R.
1077// Return FALSE if no range cqn be calculated.
1078// Also set the global range for NAME as this should only be called within
1079// the def block during a DOM walk.
1080// Outgoing edges were pre-calculated, so when we establish a global defintion
1081// check if any outgoing edges hav ranges that can be combined with the
1082// global.
1083
1084bool
1085dom_ranger::range_of_stmt (vrange &r, gimple *s, tree name)
1086{
1087 unsigned idx;
1088 bool ret;
1089 if (!name)
1090 name = gimple_range_ssa_p (exp: gimple_get_lhs (s));
1091
1092 gcc_checking_assert (!name || name == gimple_get_lhs (s));
1093
1094 if ((idx = tracer.header (str: "range_of_stmt ")))
1095 print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
1096
1097 // Its already been calculated.
1098 if (name && m_global.has_range (name))
1099 {
1100 ret = m_global.range_of_expr (r, expr: name, stmt: s);
1101 if (idx)
1102 tracer.trailer (counter: idx, caller: " Already had value ", result: ret, name, r);
1103 return ret;
1104 }
1105
1106 // If there is a new calculated range and it is not varying, set
1107 // a global range.
1108 ret = fold_range (r, s, q: this);
1109 if (ret && name && m_global.merge_range (name, r) && !r.varying_p ())
1110 {
1111 if (set_range_info (name, r) && dump_file)
1112 {
1113 fprintf (stream: dump_file, format: "Global Exported: ");
1114 print_generic_expr (dump_file, name, TDF_SLIM);
1115 fprintf (stream: dump_file, format: " = ");
1116 r.dump (dump_file);
1117 fputc (c: '\n', stream: dump_file);
1118 }
1119 basic_block bb = gimple_bb (g: s);
1120 unsigned bbi = bb->index;
1121 Value_Range vr (TREE_TYPE (name));
1122 // If there is a range on edge 0, update it.
1123 if (m_e0[bbi] && m_e0[bbi]->has_range (name))
1124 {
1125 if (m_e0[bbi]->merge_range (name, r) && dump_file
1126 && (dump_flags & TDF_DETAILS))
1127 {
1128 fprintf (stream: dump_file, format: "Outgoing range for ");
1129 print_generic_expr (dump_file, name, TDF_SLIM);
1130 fprintf (stream: dump_file, format: " updated on edge %d->%d : ", bbi,
1131 EDGE_SUCC (bb, 0)->dest->index);
1132 if (m_e0[bbi]->get_range (r&: vr, name))
1133 vr.dump (dump_file);
1134 fputc (c: '\n', stream: dump_file);
1135 }
1136 }
1137 // If there is a range on edge 1, update it.
1138 if (m_e1[bbi] && m_e1[bbi]->has_range (name))
1139 {
1140 if (m_e1[bbi]->merge_range (name, r) && dump_file
1141 && (dump_flags & TDF_DETAILS))
1142 {
1143 fprintf (stream: dump_file, format: "Outgoing range for ");
1144 print_generic_expr (dump_file, name, TDF_SLIM);
1145 fprintf (stream: dump_file, format: " updated on edge %d->%d : ", bbi,
1146 EDGE_SUCC (bb, 1)->dest->index);
1147 if (m_e1[bbi]->get_range (r&: vr, name))
1148 vr.dump (dump_file);
1149 fputc (c: '\n', stream: dump_file);
1150 }
1151 }
1152 }
1153 if (idx)
1154 tracer.trailer (counter: idx, caller: " ", result: ret, name, r);
1155 return ret;
1156}
1157
1158// Check if GORI has an ranges on edge E. If there re, store them in
1159// either the E0 or E1 vector based on EDGE_0.
1160// If there are no ranges, put the empty lazy_cache entry on the freelist
1161// for use next time.
1162
1163void
1164dom_ranger::maybe_push_edge (edge e, bool edge_0)
1165{
1166 ssa_lazy_cache *e_cache;
1167 if (!m_freelist.is_empty ())
1168 e_cache = m_freelist.pop ();
1169 else
1170 e_cache = new ssa_lazy_cache;
1171 gori_on_edge (r&: *e_cache, e, query: this, ogr: &m_out);
1172 if (e_cache->empty_p ())
1173 m_freelist.safe_push (obj: e_cache);
1174 else
1175 {
1176 if (edge_0)
1177 m_e0[e->src->index] = e_cache;
1178 else
1179 m_e1[e->src->index] = e_cache;
1180 }
1181}
1182
1183// Preprocess block BB. If there are any outgoing edges, precalculate
1184// the outgoing ranges and store them. Note these are done before
1185// we process the block, so global values have not been set yet.
1186// These are "pure" outgoing ranges inflicted by the condition.
1187
1188void
1189dom_ranger::pre_bb (basic_block bb)
1190{
1191 if (dump_file && (dump_flags & TDF_DETAILS))
1192 fprintf (stream: dump_file, format: "#FVRP entering BB %d\n", bb->index);
1193
1194 // Next, see if this block needs outgoing edges calculated.
1195 gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
1196 if (!gsi_end_p (i: gsi))
1197 {
1198 gimple *s = gsi_stmt (i: gsi);
1199 if (is_a<gcond *> (p: s) && gimple_range_op_handler::supported_p (s))
1200 {
1201 maybe_push_edge (EDGE_SUCC (bb, 0), edge_0: true);
1202 maybe_push_edge (EDGE_SUCC (bb, 1), edge_0: false);
1203
1204 if (dump_file && (dump_flags & TDF_DETAILS))
1205 {
1206 if (m_e0[bb->index])
1207 {
1208 fprintf (stream: dump_file, format: "\nEdge ranges BB %d->%d\n",
1209 bb->index, EDGE_SUCC (bb, 0)->dest->index);
1210 m_e0[bb->index]->dump(f: dump_file);
1211 }
1212 if (m_e1[bb->index])
1213 {
1214 fprintf (stream: dump_file, format: "\nEdge ranges BB %d->%d\n",
1215 bb->index, EDGE_SUCC (bb, 1)->dest->index);
1216 m_e1[bb->index]->dump(f: dump_file);
1217 }
1218 }
1219 }
1220 }
1221 if (dump_file && (dump_flags & TDF_DETAILS))
1222 fprintf (stream: dump_file, format: "#FVRP DONE entering BB %d\n", bb->index);
1223}
1224
1225// Perform any post block processing.
1226
1227void
1228dom_ranger::post_bb (basic_block)
1229{
1230}
1231

source code of gcc/gimple-range.cc