]>
git.ipfire.org Git - people/ms/gcc.git/blob - gcc/gimple-range-path.cc
1 /* Basic block path solver.
2 Copyright (C) 2021-2023 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 (gimple_ranger
&ranger
,
40 const vec
<basic_block
> &path
,
41 const bitmap_head
*dependencies
,
43 : m_cache (new ssa_global_cache
),
44 m_has_cache_entry (BITMAP_ALLOC (NULL
)),
48 m_oracle
= new path_oracle (m_ranger
.oracle ());
50 reset_path (path
, dependencies
);
53 path_range_query::path_range_query (gimple_ranger
&ranger
, bool resolve
)
54 : m_cache (new ssa_global_cache
),
55 m_has_cache_entry (BITMAP_ALLOC (NULL
)),
59 m_oracle
= new path_oracle (m_ranger
.oracle ());
62 path_range_query::~path_range_query ()
65 BITMAP_FREE (m_has_cache_entry
);
69 // Return TRUE if NAME is an exit dependency for the path.
72 path_range_query::exit_dependency_p (tree name
)
74 return (TREE_CODE (name
) == SSA_NAME
75 && bitmap_bit_p (m_exit_dependencies
, SSA_NAME_VERSION (name
)));
78 // Mark cache entry for NAME as unused.
81 path_range_query::clear_cache (tree name
)
83 unsigned v
= SSA_NAME_VERSION (name
);
84 bitmap_clear_bit (m_has_cache_entry
, v
);
87 // If NAME has a cache entry, return it in R, and return TRUE.
90 path_range_query::get_cache (vrange
&r
, tree name
)
92 if (!gimple_range_ssa_p (name
))
93 return get_global_range_query ()->range_of_expr (r
, name
);
95 unsigned v
= SSA_NAME_VERSION (name
);
96 if (bitmap_bit_p (m_has_cache_entry
, v
))
97 return m_cache
->get_global_range (r
, name
);
102 // Set the cache entry for NAME to R.
105 path_range_query::set_cache (const vrange
&r
, tree name
)
107 unsigned v
= SSA_NAME_VERSION (name
);
108 bitmap_set_bit (m_has_cache_entry
, v
);
109 m_cache
->set_global_range (name
, r
);
113 path_range_query::dump (FILE *dump_file
)
115 push_dump_file
save (dump_file
, dump_flags
& ~TDF_DETAILS
);
117 if (m_path
.is_empty ())
123 dump_ranger (dump_file
, m_path
);
125 fprintf (dump_file
, "Exit dependencies:\n");
126 EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies
, 0, i
, bi
)
128 tree name
= ssa_name (i
);
129 print_generic_expr (dump_file
, name
, TDF_SLIM
);
130 fprintf (dump_file
, "\n");
133 m_cache
->dump (dump_file
);
137 path_range_query::debug ()
142 // Return TRUE if NAME is defined outside the current path.
145 path_range_query::defined_outside_path (tree name
)
147 gimple
*def
= SSA_NAME_DEF_STMT (name
);
148 basic_block bb
= gimple_bb (def
);
150 return !bb
|| !m_path
.contains (bb
);
153 // Return the range of NAME on entry to the path.
156 path_range_query::range_on_path_entry (vrange
&r
, tree name
)
158 gcc_checking_assert (defined_outside_path (name
));
159 basic_block entry
= entry_bb ();
160 m_ranger
.range_on_entry (r
, entry
, name
);
163 // Return the range of NAME at the end of the path being analyzed.
166 path_range_query::internal_range_of_expr (vrange
&r
, tree name
, gimple
*stmt
)
168 if (!r
.supports_type_p (TREE_TYPE (name
)))
171 if (get_cache (r
, name
))
174 if (m_resolve
&& defined_outside_path (name
))
176 range_on_path_entry (r
, name
);
182 && range_defined_in_block (r
, name
, gimple_bb (stmt
)))
184 if (TREE_CODE (name
) == SSA_NAME
)
186 Value_Range
glob (TREE_TYPE (name
));
187 gimple_range_global (glob
, name
);
195 gimple_range_global (r
, name
);
200 path_range_query::range_of_expr (vrange
&r
, tree name
, gimple
*stmt
)
202 if (internal_range_of_expr (r
, name
, stmt
))
204 if (r
.undefined_p ())
205 m_undefined_path
= true;
213 path_range_query::unreachable_path_p ()
215 return m_undefined_path
;
218 // Reset the current path to PATH.
221 path_range_query::reset_path (const vec
<basic_block
> &path
,
222 const bitmap_head
*dependencies
)
224 gcc_checking_assert (path
.length () > 1);
225 m_path
= path
.copy ();
226 m_pos
= m_path
.length () - 1;
227 m_undefined_path
= false;
228 bitmap_clear (m_has_cache_entry
);
230 compute_ranges (dependencies
);
234 path_range_query::ssa_defined_in_bb (tree name
, basic_block bb
)
236 return (TREE_CODE (name
) == SSA_NAME
237 && SSA_NAME_DEF_STMT (name
)
238 && gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
);
241 // Return the range of the result of PHI in R.
243 // Since PHIs are calculated in parallel at the beginning of the
244 // block, we must be careful to never save anything to the cache here.
245 // It is the caller's responsibility to adjust the cache. Also,
246 // calculating the PHI's range must not trigger additional lookups.
249 path_range_query::ssa_range_in_phi (vrange
&r
, gphi
*phi
)
251 tree name
= gimple_phi_result (phi
);
255 if (m_resolve
&& m_ranger
.range_of_expr (r
, name
, phi
))
258 // Try to fold the phi exclusively with global or cached values.
259 // This will get things like PHI <5(99), 6(88)>. We do this by
260 // calling range_of_expr with no context.
261 unsigned nargs
= gimple_phi_num_args (phi
);
262 Value_Range
arg_range (TREE_TYPE (name
));
264 for (size_t i
= 0; i
< nargs
; ++i
)
266 tree arg
= gimple_phi_arg_def (phi
, i
);
267 if (range_of_expr (arg_range
, arg
, /*stmt=*/NULL
))
268 r
.union_ (arg_range
);
271 r
.set_varying (TREE_TYPE (name
));
278 basic_block bb
= gimple_bb (phi
);
279 basic_block prev
= prev_bb ();
280 edge e_in
= find_edge (prev
, bb
);
281 tree arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e_in
);
282 // Avoid using the cache for ARGs defined in this block, as
283 // that could create an ordering problem.
284 if (ssa_defined_in_bb (arg
, bb
) || !get_cache (r
, arg
))
288 Value_Range
tmp (TREE_TYPE (name
));
289 // Using both the range on entry to the path, and the
290 // range on this edge yields significantly better
292 if (TREE_CODE (arg
) == SSA_NAME
293 && defined_outside_path (arg
))
294 range_on_path_entry (r
, arg
);
296 r
.set_varying (TREE_TYPE (name
));
297 m_ranger
.range_on_edge (tmp
, e_in
, arg
);
301 r
.set_varying (TREE_TYPE (name
));
305 // If NAME is defined in BB, set R to the range of NAME, and return
306 // TRUE. Otherwise, return FALSE.
309 path_range_query::range_defined_in_block (vrange
&r
, tree name
, basic_block bb
)
311 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
312 basic_block def_bb
= gimple_bb (def_stmt
);
317 if (get_cache (r
, name
))
320 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
321 ssa_range_in_phi (r
, as_a
<gphi
*> (def_stmt
));
325 get_path_oracle ()->killing_def (name
);
327 if (!range_of_stmt (r
, def_stmt
, name
))
328 r
.set_varying (TREE_TYPE (name
));
331 if (bb
&& POINTER_TYPE_P (TREE_TYPE (name
)))
332 m_ranger
.m_cache
.m_exit
.maybe_adjust_range (r
, name
, bb
);
334 if (DEBUG_SOLVER
&& (bb
|| !r
.varying_p ()))
336 fprintf (dump_file
, "range_defined_in_block (BB%d) for ", bb
? bb
->index
: -1);
337 print_generic_expr (dump_file
, name
, TDF_SLIM
);
338 fprintf (dump_file
, " is ");
340 fprintf (dump_file
, "\n");
346 // Compute ranges defined in the PHIs in this block.
349 path_range_query::compute_ranges_in_phis (basic_block bb
)
353 // PHIs must be resolved simultaneously on entry to the block
354 // because any dependencies must be satistifed with values on entry.
355 // Thus, we calculate all PHIs first, and then update the cache at
358 for (auto iter
= gsi_start_phis (bb
); !gsi_end_p (iter
); gsi_next (&iter
))
360 gphi
*phi
= iter
.phi ();
361 tree name
= gimple_phi_result (phi
);
363 if (!exit_dependency_p (name
))
366 Value_Range
r (TREE_TYPE (name
));
367 if (range_defined_in_block (r
, name
, bb
))
369 unsigned v
= SSA_NAME_VERSION (name
);
371 bitmap_set_bit (phi_set
, v
);
372 // Pretend we don't have a cache entry for this name until
373 // we're done with all PHIs.
374 bitmap_clear_bit (m_has_cache_entry
, v
);
377 bitmap_ior_into (m_has_cache_entry
, phi_set
);
380 // Return TRUE if relations may be invalidated after crossing edge E.
383 path_range_query::relations_may_be_invalidated (edge e
)
385 // As soon as the path crosses a back edge, we can encounter
386 // definitions of SSA_NAMEs that may have had a use in the path
387 // already, so this will then be a new definition. The relation
388 // code is all designed around seeing things in dominator order, and
389 // crossing a back edge in the path violates this assumption.
390 return (e
->flags
& EDGE_DFS_BACK
);
393 // Compute ranges defined in the current block, or exported to the
397 path_range_query::compute_ranges_in_block (basic_block bb
)
402 if (m_resolve
&& !at_entry ())
403 compute_phi_relations (bb
, prev_bb ());
405 // Force recalculation of any names in the cache that are defined in
406 // this block. This can happen on interdependent SSA/phis in loops.
407 EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies
, 0, i
, bi
)
409 tree name
= ssa_name (i
);
410 if (ssa_defined_in_bb (name
, bb
))
414 // Solve dependencies defined in this block, starting with the PHIs...
415 compute_ranges_in_phis (bb
);
416 // ...and then the rest of the dependencies.
417 EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies
, 0, i
, bi
)
419 tree name
= ssa_name (i
);
420 Value_Range
r (TREE_TYPE (name
));
422 if (gimple_code (SSA_NAME_DEF_STMT (name
)) != GIMPLE_PHI
423 && range_defined_in_block (r
, name
, bb
))
430 // Solve dependencies that are exported to the next block.
431 basic_block next
= next_bb ();
432 edge e
= find_edge (bb
, next
);
434 if (m_resolve
&& relations_may_be_invalidated (e
))
438 "Resetting relations as they may be invalidated in %d->%d.\n",
439 e
->src
->index
, e
->dest
->index
);
441 path_oracle
*p
= get_path_oracle ();
442 // ?? Instead of nuking the root oracle altogether, we could
443 // reset the path oracle to search for relations from the top of
444 // the loop with the root oracle. Something for future development.
448 gori_compute
&g
= m_ranger
.gori ();
449 bitmap exports
= g
.exports (bb
);
450 EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies
, exports
, 0, i
, bi
)
452 tree name
= ssa_name (i
);
453 Value_Range
r (TREE_TYPE (name
));
454 if (g
.outgoing_edge_range_p (r
, e
, name
, *this))
456 Value_Range
cached_range (TREE_TYPE (name
));
457 if (get_cache (cached_range
, name
))
458 r
.intersect (cached_range
);
463 fprintf (dump_file
, "outgoing_edge_range_p for ");
464 print_generic_expr (dump_file
, name
, TDF_SLIM
);
465 fprintf (dump_file
, " on edge %d->%d ",
466 e
->src
->index
, e
->dest
->index
);
467 fprintf (dump_file
, "is ");
469 fprintf (dump_file
, "\n");
475 compute_outgoing_relations (bb
, next
);
478 // Adjust all pointer exit dependencies in BB with non-null information.
481 path_range_query::adjust_for_non_null_uses (basic_block bb
)
487 EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies
, 0, i
, bi
)
489 tree name
= ssa_name (i
);
491 if (!POINTER_TYPE_P (TREE_TYPE (name
)))
494 if (get_cache (r
, name
))
500 r
.set_varying (TREE_TYPE (name
));
502 if (m_ranger
.m_cache
.m_exit
.maybe_adjust_range (r
, name
, bb
))
507 // If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
510 path_range_query::add_to_exit_dependencies (tree name
, bitmap dependencies
)
512 if (TREE_CODE (name
) == SSA_NAME
513 && Value_Range::supports_type_p (TREE_TYPE (name
)))
514 return bitmap_set_bit (dependencies
, SSA_NAME_VERSION (name
));
518 // Compute the exit dependencies to PATH. These are essentially the
519 // SSA names used to calculate the final conditional along the path.
522 path_range_query::compute_exit_dependencies (bitmap dependencies
)
524 // Start with the imports from the exit block...
525 basic_block exit
= m_path
[0];
526 gori_compute
&gori
= m_ranger
.gori ();
527 bitmap_copy (dependencies
, gori
.imports (exit
));
529 auto_vec
<tree
> worklist (bitmap_count_bits (dependencies
));
532 EXECUTE_IF_SET_IN_BITMAP (dependencies
, 0, i
, bi
)
534 tree name
= ssa_name (i
);
535 worklist
.quick_push (name
);
538 // ...and add any operands used to define these imports.
539 while (!worklist
.is_empty ())
541 tree name
= worklist
.pop ();
542 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
543 if (SSA_NAME_IS_DEFAULT_DEF (name
)
544 || !m_path
.contains (gimple_bb (def_stmt
)))
547 if (gphi
*phi
= dyn_cast
<gphi
*> (def_stmt
))
549 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
551 edge e
= gimple_phi_arg_edge (phi
, i
);
552 tree arg
= gimple_phi_arg (phi
, i
)->def
;
554 if (TREE_CODE (arg
) == SSA_NAME
555 && m_path
.contains (e
->src
)
556 && bitmap_set_bit (dependencies
, SSA_NAME_VERSION (arg
)))
557 worklist
.safe_push (arg
);
560 else if (gassign
*ass
= dyn_cast
<gassign
*> (def_stmt
))
563 unsigned count
= gimple_range_ssa_names (ssa
, 3, ass
);
564 for (unsigned j
= 0; j
< count
; ++j
)
565 if (add_to_exit_dependencies (ssa
[j
], dependencies
))
566 worklist
.safe_push (ssa
[j
]);
569 // Exported booleans along the path, may help conditionals.
571 for (i
= 0; i
< m_path
.length (); ++i
)
573 basic_block bb
= m_path
[i
];
575 FOR_EACH_GORI_EXPORT_NAME (gori
, bb
, name
)
576 if (TREE_CODE (TREE_TYPE (name
)) == BOOLEAN_TYPE
)
577 bitmap_set_bit (dependencies
, SSA_NAME_VERSION (name
));
581 // Compute the ranges for DEPENDENCIES along PATH.
583 // DEPENDENCIES are path exit dependencies. They are the set of SSA
584 // names, any of which could potentially change the value of the final
585 // conditional in PATH. If none is given, the exit dependencies are
586 // calculated from the final conditional in the path.
589 path_range_query::compute_ranges (const bitmap_head
*dependencies
)
592 fprintf (dump_file
, "\n==============================================\n");
595 bitmap_copy (m_exit_dependencies
, dependencies
);
597 compute_exit_dependencies (m_exit_dependencies
);
601 path_oracle
*p
= get_path_oracle ();
602 p
->reset_path (m_ranger
.oracle ());
607 fprintf (dump_file
, "path_range_query: compute_ranges for path: ");
608 for (unsigned i
= m_path
.length (); i
> 0; --i
)
610 basic_block bb
= m_path
[i
- 1];
611 fprintf (dump_file
, "%d", bb
->index
);
613 fprintf (dump_file
, "->");
615 fprintf (dump_file
, "\n");
620 basic_block bb
= curr_bb ();
622 compute_ranges_in_block (bb
);
623 adjust_for_non_null_uses (bb
);
633 get_path_oracle ()->dump (dump_file
);
638 // A folding aid used to register and query relations along a path.
639 // When queried, it returns relations as they would appear on exit to
642 // Relations are registered on entry so the path_oracle knows which
643 // block to query the root oracle at when a relation lies outside the
644 // path. However, when queried we return the relation on exit to the
645 // path, since the root_oracle ignores the registered.
647 class jt_fur_source
: public fur_depend
650 jt_fur_source (gimple
*s
, path_range_query
*, gori_compute
*,
651 const vec
<basic_block
> &);
652 relation_kind
query_relation (tree op1
, tree op2
) override
;
653 void register_relation (gimple
*, relation_kind
, tree op1
, tree op2
) override
;
654 void register_relation (edge
, relation_kind
, tree op1
, tree op2
) override
;
659 jt_fur_source::jt_fur_source (gimple
*s
,
660 path_range_query
*query
,
662 const vec
<basic_block
> &path
)
663 : fur_depend (s
, gori
, query
)
665 gcc_checking_assert (!path
.is_empty ());
667 m_entry
= path
[path
.length () - 1];
669 if (dom_info_available_p (CDI_DOMINATORS
))
670 m_oracle
= query
->oracle ();
675 // Ignore statement and register relation on entry to path.
678 jt_fur_source::register_relation (gimple
*, relation_kind k
, tree op1
, tree op2
)
681 m_oracle
->register_relation (m_entry
, k
, op1
, op2
);
684 // Ignore edge and register relation on entry to path.
687 jt_fur_source::register_relation (edge
, relation_kind k
, tree op1
, tree op2
)
690 m_oracle
->register_relation (m_entry
, k
, op1
, op2
);
694 jt_fur_source::query_relation (tree op1
, tree op2
)
699 if (TREE_CODE (op1
) != SSA_NAME
|| TREE_CODE (op2
) != SSA_NAME
)
702 return m_oracle
->query_relation (m_entry
, op1
, op2
);
705 // Return the range of STMT at the end of the path being analyzed.
708 path_range_query::range_of_stmt (vrange
&r
, gimple
*stmt
, tree
)
710 tree type
= gimple_range_type (stmt
);
712 if (!type
|| !r
.supports_type_p (type
))
715 // If resolving unknowns, fold the statement making use of any
716 // relations along the path.
720 jt_fur_source
src (stmt
, this, &m_ranger
.gori (), m_path
);
721 if (!f
.fold_stmt (r
, stmt
, src
))
722 r
.set_varying (type
);
724 // Otherwise, fold without relations.
725 else if (!fold_range (r
, stmt
, this))
726 r
.set_varying (type
);
731 // If possible, register the relation on the incoming edge E into PHI.
734 path_range_query::maybe_register_phi_relation (gphi
*phi
, edge e
)
736 tree arg
= gimple_phi_arg_def (phi
, e
->dest_idx
);
738 if (!gimple_range_ssa_p (arg
))
741 if (relations_may_be_invalidated (e
))
744 basic_block bb
= gimple_bb (phi
);
745 tree result
= gimple_phi_result (phi
);
747 // Avoid recording the equivalence if the arg is defined in this
748 // block, as that could create an ordering problem.
749 if (ssa_defined_in_bb (arg
, bb
))
752 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
753 fprintf (dump_file
, "maybe_register_phi_relation in bb%d:", bb
->index
);
755 get_path_oracle ()->killing_def (result
);
756 m_oracle
->register_relation (entry_bb (), VREL_EQ
, arg
, result
);
759 // Compute relations for each PHI in BB. For example:
761 // x_5 = PHI<y_9(5),...>
763 // If the path flows through BB5, we can register that x_5 == y_9.
766 path_range_query::compute_phi_relations (basic_block bb
, basic_block prev
)
771 edge e_in
= find_edge (prev
, bb
);
773 for (gphi_iterator iter
= gsi_start_phis (bb
); !gsi_end_p (iter
);
776 gphi
*phi
= iter
.phi ();
777 tree result
= gimple_phi_result (phi
);
778 unsigned nargs
= gimple_phi_num_args (phi
);
780 if (!exit_dependency_p (result
))
783 for (size_t i
= 0; i
< nargs
; ++i
)
784 if (e_in
== gimple_phi_arg_edge (phi
, i
))
786 maybe_register_phi_relation (phi
, e_in
);
792 // Compute outgoing relations from BB to NEXT.
795 path_range_query::compute_outgoing_relations (basic_block bb
, basic_block next
)
797 if (gcond
*cond
= safe_dyn_cast
<gcond
*> (last_stmt (bb
)))
800 edge e0
= EDGE_SUCC (bb
, 0);
801 edge e1
= EDGE_SUCC (bb
, 1);
803 if (e0
->dest
== next
)
804 gcond_edge_range (r
, e0
);
805 else if (e1
->dest
== next
)
806 gcond_edge_range (r
, e1
);
810 jt_fur_source
src (NULL
, this, &m_ranger
.gori (), m_path
);
811 src
.register_outgoing_edges (cond
, r
, e0
, e1
);