]>
git.ipfire.org Git - thirdparty/gcc.git/blob - gcc/gimple-range-path.cc
1 /* Basic block path solver.
2 Copyright (C) 2021 Free Software Foundation, Inc.
3 Contributed by Aldy Hernandez <aldyh@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "value-range.h"
29 #include "gimple-range.h"
30 #include "tree-pretty-print.h"
31 #include "gimple-range-path.h"
34 #include "gimple-iterator.h"
36 // Internal construct to help facilitate debugging of solver.
37 #define DEBUG_SOLVER (dump_file && (param_threader_debug == THREADER_DEBUG_ALL))
39 path_range_query::path_range_query (bool resolve
, gimple_ranger
*ranger
)
40 : m_cache (new ssa_global_cache
),
41 m_has_cache_entry (BITMAP_ALLOC (NULL
)),
43 m_alloced_ranger (!ranger
)
46 m_ranger
= new gimple_ranger
;
50 m_oracle
= new path_oracle (m_ranger
->oracle ());
53 path_range_query::~path_range_query ()
58 BITMAP_FREE (m_has_cache_entry
);
62 // Return TRUE if NAME is in the import bitmap.
65 path_range_query::import_p (tree name
)
67 return (TREE_CODE (name
) == SSA_NAME
68 && bitmap_bit_p (m_imports
, SSA_NAME_VERSION (name
)));
71 // Mark cache entry for NAME as unused.
74 path_range_query::clear_cache (tree name
)
76 unsigned v
= SSA_NAME_VERSION (name
);
77 bitmap_clear_bit (m_has_cache_entry
, v
);
80 // If NAME has a cache entry, return it in R, and return TRUE.
83 path_range_query::get_cache (irange
&r
, tree name
)
85 if (!gimple_range_ssa_p (name
))
86 return get_global_range_query ()->range_of_expr (r
, name
);
88 unsigned v
= SSA_NAME_VERSION (name
);
89 if (bitmap_bit_p (m_has_cache_entry
, v
))
90 return m_cache
->get_global_range (r
, name
);
95 // Set the cache entry for NAME to R.
98 path_range_query::set_cache (const irange
&r
, tree name
)
100 unsigned v
= SSA_NAME_VERSION (name
);
101 bitmap_set_bit (m_has_cache_entry
, v
);
102 m_cache
->set_global_range (name
, r
);
106 path_range_query::dump (FILE *dump_file
)
108 push_dump_file
save (dump_file
, dump_flags
& ~TDF_DETAILS
);
110 if (m_path
.is_empty ())
116 dump_ranger (dump_file
, m_path
);
118 fprintf (dump_file
, "Imports:\n");
119 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
121 tree name
= ssa_name (i
);
122 print_generic_expr (dump_file
, name
, TDF_SLIM
);
123 fprintf (dump_file
, "\n");
126 m_cache
->dump (dump_file
);
130 path_range_query::debug ()
135 // Return TRUE if NAME is defined outside the current path.
138 path_range_query::defined_outside_path (tree name
)
140 gimple
*def
= SSA_NAME_DEF_STMT (name
);
141 basic_block bb
= gimple_bb (def
);
143 return !bb
|| !m_path
.contains (bb
);
146 // Return the range of NAME on entry to the path.
149 path_range_query::range_on_path_entry (irange
&r
, tree name
)
151 gcc_checking_assert (defined_outside_path (name
));
152 basic_block entry
= entry_bb ();
154 // Prefer to use range_of_expr if we have a statement to look at,
155 // since it has better caching than range_on_edge.
156 gimple
*last
= last_stmt (entry
);
159 if (m_ranger
->range_of_expr (r
, name
, last
))
164 // If we have no statement, look at all the incoming ranges to the
165 // block. This can happen when we're querying a block with only an
166 // outgoing edge (no statement but the fall through edge), but for
167 // which we can determine a range on entry to the block.
169 bool changed
= false;
171 for (unsigned i
= 0; i
< EDGE_COUNT (entry
->preds
); ++i
)
173 edge e
= EDGE_PRED (entry
, i
);
174 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
175 && m_ranger
->range_on_edge (tmp
, e
, name
))
182 // Make sure we don't return UNDEFINED by mistake.
184 r
.set_varying (TREE_TYPE (name
));
187 // Return the range of NAME at the end of the path being analyzed.
190 path_range_query::internal_range_of_expr (irange
&r
, tree name
, gimple
*stmt
)
192 if (!irange::supports_type_p (TREE_TYPE (name
)))
195 if (get_cache (r
, name
))
198 if (m_resolve
&& defined_outside_path (name
))
200 range_on_path_entry (r
, name
);
206 && range_defined_in_block (r
, name
, gimple_bb (stmt
)))
208 if (TREE_CODE (name
) == SSA_NAME
)
209 r
.intersect (gimple_range_global (name
));
215 r
= gimple_range_global (name
);
220 path_range_query::range_of_expr (irange
&r
, tree name
, gimple
*stmt
)
222 if (internal_range_of_expr (r
, name
, stmt
))
224 if (r
.undefined_p ())
225 m_undefined_path
= true;
233 path_range_query::unreachable_path_p ()
235 return m_undefined_path
;
238 // Initialize the current path to PATH. The current block is set to
239 // the entry block to the path.
241 // Note that the blocks are in reverse order, so the exit block is
245 path_range_query::set_path (const vec
<basic_block
> &path
)
247 gcc_checking_assert (path
.length () > 1);
248 m_path
= path
.copy ();
249 m_pos
= m_path
.length () - 1;
250 bitmap_clear (m_has_cache_entry
);
254 path_range_query::ssa_defined_in_bb (tree name
, basic_block bb
)
256 return (TREE_CODE (name
) == SSA_NAME
257 && SSA_NAME_DEF_STMT (name
)
258 && gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
);
261 // Return the range of the result of PHI in R.
263 // Since PHIs are calculated in parallel at the beginning of the
264 // block, we must be careful to never save anything to the cache here.
265 // It is the caller's responsibility to adjust the cache. Also,
266 // calculating the PHI's range must not trigger additional lookups.
269 path_range_query::ssa_range_in_phi (irange
&r
, gphi
*phi
)
271 tree name
= gimple_phi_result (phi
);
272 basic_block bb
= gimple_bb (phi
);
273 unsigned nargs
= gimple_phi_num_args (phi
);
277 if (m_resolve
&& m_ranger
->range_of_expr (r
, name
, phi
))
280 // Try to fold the phi exclusively with global or cached values.
281 // This will get things like PHI <5(99), 6(88)>. We do this by
282 // calling range_of_expr with no context.
283 int_range_max arg_range
;
285 for (size_t i
= 0; i
< nargs
; ++i
)
287 tree arg
= gimple_phi_arg_def (phi
, i
);
288 if (range_of_expr (arg_range
, arg
, /*stmt=*/NULL
))
289 r
.union_ (arg_range
);
292 r
.set_varying (TREE_TYPE (name
));
299 basic_block prev
= prev_bb ();
300 edge e_in
= find_edge (prev
, bb
);
302 for (size_t i
= 0; i
< nargs
; ++i
)
303 if (e_in
== gimple_phi_arg_edge (phi
, i
))
305 tree arg
= gimple_phi_arg_def (phi
, i
);
306 // Avoid using the cache for ARGs defined in this block, as
307 // that could create an ordering problem.
308 if (ssa_defined_in_bb (arg
, bb
) || !get_cache (r
, arg
))
313 // Using both the range on entry to the path, and the
314 // range on this edge yields significantly better
316 if (defined_outside_path (arg
))
317 range_on_path_entry (r
, arg
);
319 r
.set_varying (TREE_TYPE (name
));
320 m_ranger
->range_on_edge (tmp
, e_in
, arg
);
324 r
.set_varying (TREE_TYPE (name
));
331 // If NAME is defined in BB, set R to the range of NAME, and return
332 // TRUE. Otherwise, return FALSE.
335 path_range_query::range_defined_in_block (irange
&r
, tree name
, basic_block bb
)
337 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
338 basic_block def_bb
= gimple_bb (def_stmt
);
343 if (get_cache (r
, name
))
346 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
347 ssa_range_in_phi (r
, as_a
<gphi
*> (def_stmt
));
351 get_path_oracle ()->killing_def (name
);
353 if (!range_of_stmt (r
, def_stmt
, name
))
354 r
.set_varying (TREE_TYPE (name
));
358 m_non_null
.adjust_range (r
, name
, bb
);
360 if (DEBUG_SOLVER
&& (bb
|| !r
.varying_p ()))
362 fprintf (dump_file
, "range_defined_in_block (BB%d) for ", bb
? bb
->index
: -1);
363 print_generic_expr (dump_file
, name
, TDF_SLIM
);
364 fprintf (dump_file
, " is ");
366 fprintf (dump_file
, "\n");
372 // Compute ranges defined in the PHIs in this block.
375 path_range_query::compute_ranges_in_phis (basic_block bb
)
380 // PHIs must be resolved simultaneously on entry to the block
381 // because any dependencies must be satistifed with values on entry.
382 // Thus, we calculate all PHIs first, and then update the cache at
385 m_tmp_phi_cache
.clear ();
386 for (iter
= gsi_start_phis (bb
); !gsi_end_p (iter
); gsi_next (&iter
))
388 gphi
*phi
= iter
.phi ();
389 tree name
= gimple_phi_result (phi
);
391 if (import_p (name
) && range_defined_in_block (r
, name
, bb
))
392 m_tmp_phi_cache
.set_global_range (name
, r
);
394 for (iter
= gsi_start_phis (bb
); !gsi_end_p (iter
); gsi_next (&iter
))
396 gphi
*phi
= iter
.phi ();
397 tree name
= gimple_phi_result (phi
);
399 if (m_tmp_phi_cache
.get_global_range (r
, name
))
404 // Compute ranges defined in the current block, or exported to the
408 path_range_query::compute_ranges_in_block (basic_block bb
)
411 int_range_max r
, cached_range
;
414 if (m_resolve
&& !at_entry ())
415 compute_phi_relations (bb
, prev_bb ());
417 // Force recalculation of any names in the cache that are defined in
418 // this block. This can happen on interdependent SSA/phis in loops.
419 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
421 tree name
= ssa_name (i
);
422 if (ssa_defined_in_bb (name
, bb
))
426 // Solve imports defined in this block, starting with the PHIs...
427 compute_ranges_in_phis (bb
);
428 // ...and then the rest of the imports.
429 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
431 tree name
= ssa_name (i
);
433 if (gimple_code (SSA_NAME_DEF_STMT (name
)) != GIMPLE_PHI
434 && range_defined_in_block (r
, name
, bb
))
441 // Solve imports that are exported to the next block.
442 basic_block next
= next_bb ();
443 edge e
= find_edge (bb
, next
);
444 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
446 tree name
= ssa_name (i
);
447 gori_compute
&g
= m_ranger
->gori ();
448 bitmap exports
= g
.exports (bb
);
450 if (bitmap_bit_p (exports
, i
))
452 if (g
.outgoing_edge_range_p (r
, e
, name
, *this))
454 if (get_cache (cached_range
, name
))
455 r
.intersect (cached_range
);
460 fprintf (dump_file
, "outgoing_edge_range_p for ");
461 print_generic_expr (dump_file
, name
, TDF_SLIM
);
462 fprintf (dump_file
, " on edge %d->%d ",
463 e
->src
->index
, e
->dest
->index
);
464 fprintf (dump_file
, "is ");
466 fprintf (dump_file
, "\n");
473 compute_outgoing_relations (bb
, next
);
476 // Adjust all pointer imports in BB with non-null information.
479 path_range_query::adjust_for_non_null_uses (basic_block bb
)
485 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
487 tree name
= ssa_name (i
);
489 if (!POINTER_TYPE_P (TREE_TYPE (name
)))
492 if (get_cache (r
, name
))
498 r
.set_varying (TREE_TYPE (name
));
500 if (m_non_null
.adjust_range (r
, name
, bb
))
505 // If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS.
508 path_range_query::add_to_imports (tree name
, bitmap imports
)
510 if (TREE_CODE (name
) == SSA_NAME
511 && irange::supports_type_p (TREE_TYPE (name
)))
512 return bitmap_set_bit (imports
, SSA_NAME_VERSION (name
));
516 // Compute the imports to the path ending in EXIT. These are
517 // essentially the SSA names used to calculate the final conditional
520 // They are hints for the solver. Adding more elements doesn't slow
521 // us down, because we don't solve anything that doesn't appear in the
522 // path. On the other hand, not having enough imports will limit what
526 path_range_query::compute_imports (bitmap imports
, basic_block exit
)
528 // Start with the imports from the exit block...
529 gori_compute
&gori
= m_ranger
->gori ();
530 bitmap r_imports
= gori
.imports (exit
);
531 bitmap_copy (imports
, r_imports
);
533 auto_vec
<tree
> worklist (bitmap_count_bits (imports
));
536 EXECUTE_IF_SET_IN_BITMAP (imports
, 0, i
, bi
)
538 tree name
= ssa_name (i
);
539 worklist
.quick_push (name
);
542 // ...and add any operands used to define these imports.
543 while (!worklist
.is_empty ())
545 tree name
= worklist
.pop ();
546 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
548 if (is_gimple_assign (def_stmt
))
550 add_to_imports (gimple_assign_rhs1 (def_stmt
), imports
);
551 tree rhs
= gimple_assign_rhs2 (def_stmt
);
552 if (rhs
&& add_to_imports (rhs
, imports
))
553 worklist
.safe_push (rhs
);
554 rhs
= gimple_assign_rhs3 (def_stmt
);
555 if (rhs
&& add_to_imports (rhs
, imports
))
556 worklist
.safe_push (rhs
);
558 else if (gphi
*phi
= dyn_cast
<gphi
*> (def_stmt
))
560 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
562 edge e
= gimple_phi_arg_edge (phi
, i
);
563 tree arg
= gimple_phi_arg (phi
, i
)->def
;
565 if (TREE_CODE (arg
) == SSA_NAME
566 && m_path
.contains (e
->src
)
567 && bitmap_set_bit (imports
, SSA_NAME_VERSION (arg
)))
568 worklist
.safe_push (arg
);
572 // Exported booleans along the path, may help conditionals.
574 for (i
= 0; i
< m_path
.length (); ++i
)
576 basic_block bb
= m_path
[i
];
578 FOR_EACH_GORI_EXPORT_NAME (gori
, bb
, name
)
579 if (TREE_CODE (TREE_TYPE (name
)) == BOOLEAN_TYPE
)
580 bitmap_set_bit (imports
, SSA_NAME_VERSION (name
));
584 // Compute the ranges for IMPORTS along PATH.
586 // IMPORTS are the set of SSA names, any of which could potentially
587 // change the value of the final conditional in PATH. Default to the
588 // imports of the last block in the path if none is given.
591 path_range_query::compute_ranges (const vec
<basic_block
> &path
,
592 const bitmap_head
*imports
)
595 fprintf (dump_file
, "\n==============================================\n");
598 m_undefined_path
= false;
601 bitmap_copy (m_imports
, imports
);
603 compute_imports (m_imports
, exit_bb ());
606 get_path_oracle ()->reset_path ();
610 fprintf (dump_file
, "path_range_query: compute_ranges for path: ");
611 for (unsigned i
= path
.length (); i
> 0; --i
)
613 basic_block bb
= path
[i
- 1];
614 fprintf (dump_file
, "%d", bb
->index
);
616 fprintf (dump_file
, "->");
618 fprintf (dump_file
, "\n");
623 basic_block bb
= curr_bb ();
625 compute_ranges_in_block (bb
);
626 adjust_for_non_null_uses (bb
);
636 get_path_oracle ()->dump (dump_file
);
641 // Convenience function to compute ranges along a path consisting of
642 // E->SRC and E->DEST.
645 path_range_query::compute_ranges (edge e
)
647 auto_vec
<basic_block
> bbs (2);
648 bbs
.quick_push (e
->dest
);
649 bbs
.quick_push (e
->src
);
650 compute_ranges (bbs
);
653 // A folding aid used to register and query relations along a path.
654 // When queried, it returns relations as they would appear on exit to
657 // Relations are registered on entry so the path_oracle knows which
658 // block to query the root oracle at when a relation lies outside the
659 // path. However, when queried we return the relation on exit to the
660 // path, since the root_oracle ignores the registered.
662 class jt_fur_source
: public fur_depend
665 jt_fur_source (gimple
*s
, path_range_query
*, gori_compute
*,
666 const vec
<basic_block
> &);
667 relation_kind
query_relation (tree op1
, tree op2
) override
;
668 void register_relation (gimple
*, relation_kind
, tree op1
, tree op2
) override
;
669 void register_relation (edge
, relation_kind
, tree op1
, tree op2
) override
;
674 jt_fur_source::jt_fur_source (gimple
*s
,
675 path_range_query
*query
,
677 const vec
<basic_block
> &path
)
678 : fur_depend (s
, gori
, query
)
680 gcc_checking_assert (!path
.is_empty ());
682 m_entry
= path
[path
.length () - 1];
684 if (dom_info_available_p (CDI_DOMINATORS
))
685 m_oracle
= query
->oracle ();
690 // Ignore statement and register relation on entry to path.
693 jt_fur_source::register_relation (gimple
*, relation_kind k
, tree op1
, tree op2
)
696 m_oracle
->register_relation (m_entry
, k
, op1
, op2
);
699 // Ignore edge and register relation on entry to path.
702 jt_fur_source::register_relation (edge
, relation_kind k
, tree op1
, tree op2
)
705 m_oracle
->register_relation (m_entry
, k
, op1
, op2
);
709 jt_fur_source::query_relation (tree op1
, tree op2
)
714 if (TREE_CODE (op1
) != SSA_NAME
|| TREE_CODE (op2
) != SSA_NAME
)
717 return m_oracle
->query_relation (m_entry
, op1
, op2
);
720 // Return the range of STMT at the end of the path being analyzed.
723 path_range_query::range_of_stmt (irange
&r
, gimple
*stmt
, tree
)
725 tree type
= gimple_range_type (stmt
);
727 if (!irange::supports_type_p (type
))
730 // If resolving unknowns, fold the statement making use of any
731 // relations along the path.
735 jt_fur_source
src (stmt
, this, &m_ranger
->gori (), m_path
);
736 if (!f
.fold_stmt (r
, stmt
, src
))
737 r
.set_varying (type
);
739 // Otherwise, fold without relations.
740 else if (!fold_range (r
, stmt
, this))
741 r
.set_varying (type
);
747 path_range_query::maybe_register_phi_relation (gphi
*phi
, tree arg
)
749 basic_block bb
= gimple_bb (phi
);
750 tree result
= gimple_phi_result (phi
);
752 // Avoid recording the equivalence if the arg is defined in this
753 // block, as that could create an ordering problem.
754 if (ssa_defined_in_bb (arg
, bb
))
757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
758 fprintf (dump_file
, " from bb%d:", bb
->index
);
760 get_path_oracle ()->killing_def (result
);
761 m_oracle
->register_relation (entry_bb (), EQ_EXPR
, arg
, result
);
764 // Compute relations for each PHI in BB. For example:
766 // x_5 = PHI<y_9(5),...>
768 // If the path flows through BB5, we can register that x_5 == y_9.
771 path_range_query::compute_phi_relations (basic_block bb
, basic_block prev
)
776 edge e_in
= find_edge (prev
, bb
);
778 for (gphi_iterator iter
= gsi_start_phis (bb
); !gsi_end_p (iter
);
781 gphi
*phi
= iter
.phi ();
782 tree result
= gimple_phi_result (phi
);
783 unsigned nargs
= gimple_phi_num_args (phi
);
785 if (!import_p (result
))
788 for (size_t i
= 0; i
< nargs
; ++i
)
789 if (e_in
== gimple_phi_arg_edge (phi
, i
))
791 tree arg
= gimple_phi_arg_def (phi
, i
);
793 if (gimple_range_ssa_p (arg
))
794 maybe_register_phi_relation (phi
, arg
);
800 // Compute outgoing relations from BB to NEXT.
803 path_range_query::compute_outgoing_relations (basic_block bb
, basic_block next
)
805 gimple
*stmt
= last_stmt (bb
);
808 && gimple_code (stmt
) == GIMPLE_COND
809 && (import_p (gimple_cond_lhs (stmt
))
810 || import_p (gimple_cond_rhs (stmt
))))
813 gcond
*cond
= as_a
<gcond
*> (stmt
);
814 edge e0
= EDGE_SUCC (bb
, 0);
815 edge e1
= EDGE_SUCC (bb
, 1);
817 if (e0
->dest
== next
)
818 gcond_edge_range (r
, e0
);
819 else if (e1
->dest
== next
)
820 gcond_edge_range (r
, e1
);
824 jt_fur_source
src (NULL
, this, &m_ranger
->gori (), m_path
);
825 src
.register_outgoing_edges (cond
, r
, e0
, e1
);