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
,
47 m_oracle
= new path_oracle (m_ranger
.oracle ());
49 reset_path (path
, dependencies
);
52 path_range_query::path_range_query (gimple_ranger
&ranger
, bool resolve
)
57 m_oracle
= new path_oracle (m_ranger
.oracle ());
60 path_range_query::~path_range_query ()
65 // Return TRUE if NAME is an exit dependency for the path.
68 path_range_query::exit_dependency_p (tree name
)
70 return (TREE_CODE (name
) == SSA_NAME
71 && bitmap_bit_p (m_exit_dependencies
, SSA_NAME_VERSION (name
)));
74 // If NAME has a cache entry, return it in R, and return TRUE.
77 path_range_query::get_cache (vrange
&r
, tree name
)
79 if (!gimple_range_ssa_p (name
))
80 return get_global_range_query ()->range_of_expr (r
, name
);
82 return m_cache
.get_range (r
, name
);
86 path_range_query::dump (FILE *dump_file
)
88 push_dump_file
save (dump_file
, dump_flags
& ~TDF_DETAILS
);
90 if (m_path
.is_empty ())
96 dump_ranger (dump_file
, m_path
);
98 fprintf (dump_file
, "Exit dependencies:\n");
99 EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies
, 0, i
, bi
)
101 tree name
= ssa_name (i
);
102 print_generic_expr (dump_file
, name
, TDF_SLIM
);
103 fprintf (dump_file
, "\n");
106 m_cache
.dump (dump_file
);
110 path_range_query::debug ()
115 // Return TRUE if NAME is defined outside the current path.
118 path_range_query::defined_outside_path (tree name
)
120 gimple
*def
= SSA_NAME_DEF_STMT (name
);
121 basic_block bb
= gimple_bb (def
);
123 return !bb
|| !m_path
.contains (bb
);
126 // Return the range of NAME on entry to the path.
129 path_range_query::range_on_path_entry (vrange
&r
, tree name
)
131 gcc_checking_assert (defined_outside_path (name
));
132 basic_block entry
= entry_bb ();
133 m_ranger
.range_on_entry (r
, entry
, name
);
136 // Return the range of NAME at the end of the path being analyzed.
139 path_range_query::internal_range_of_expr (vrange
&r
, tree name
, gimple
*stmt
)
141 if (!r
.supports_type_p (TREE_TYPE (name
)))
144 if (get_cache (r
, name
))
147 if (m_resolve
&& defined_outside_path (name
))
149 range_on_path_entry (r
, name
);
150 m_cache
.set_range (name
, r
);
155 && range_defined_in_block (r
, name
, gimple_bb (stmt
)))
157 if (TREE_CODE (name
) == SSA_NAME
)
159 Value_Range
glob (TREE_TYPE (name
));
160 gimple_range_global (glob
, name
);
164 m_cache
.set_range (name
, r
);
168 gimple_range_global (r
, name
);
173 path_range_query::range_of_expr (vrange
&r
, tree name
, gimple
*stmt
)
175 if (internal_range_of_expr (r
, name
, stmt
))
177 if (r
.undefined_p ())
178 m_undefined_path
= true;
186 path_range_query::unreachable_path_p ()
188 return m_undefined_path
;
191 // Reset the current path to PATH.
194 path_range_query::reset_path (const vec
<basic_block
> &path
,
195 const bitmap_head
*dependencies
)
197 gcc_checking_assert (path
.length () > 1);
198 m_path
= path
.copy ();
199 m_pos
= m_path
.length () - 1;
200 m_undefined_path
= false;
203 compute_ranges (dependencies
);
207 path_range_query::ssa_defined_in_bb (tree name
, basic_block bb
)
209 return (TREE_CODE (name
) == SSA_NAME
210 && SSA_NAME_DEF_STMT (name
)
211 && gimple_bb (SSA_NAME_DEF_STMT (name
)) == bb
);
214 // Return the range of the result of PHI in R.
216 // Since PHIs are calculated in parallel at the beginning of the
217 // block, we must be careful to never save anything to the cache here.
218 // It is the caller's responsibility to adjust the cache. Also,
219 // calculating the PHI's range must not trigger additional lookups.
222 path_range_query::ssa_range_in_phi (vrange
&r
, gphi
*phi
)
224 tree name
= gimple_phi_result (phi
);
228 if (m_resolve
&& m_ranger
.range_of_expr (r
, name
, phi
))
231 // Try to fold the phi exclusively with global values.
232 // This will get things like PHI <5(99), 6(88)>. We do this by
233 // calling range_of_expr with no context.
234 unsigned nargs
= gimple_phi_num_args (phi
);
235 Value_Range
arg_range (TREE_TYPE (name
));
237 for (size_t i
= 0; i
< nargs
; ++i
)
239 tree arg
= gimple_phi_arg_def (phi
, i
);
240 if (m_ranger
.range_of_expr (arg_range
, arg
, /*stmt=*/NULL
))
241 r
.union_ (arg_range
);
244 r
.set_varying (TREE_TYPE (name
));
251 basic_block bb
= gimple_bb (phi
);
252 basic_block prev
= prev_bb ();
253 edge e_in
= find_edge (prev
, bb
);
254 tree arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e_in
);
255 // Avoid using the cache for ARGs defined in this block, as
256 // that could create an ordering problem.
257 if (ssa_defined_in_bb (arg
, bb
) || !get_cache (r
, arg
))
261 Value_Range
tmp (TREE_TYPE (name
));
262 // Using both the range on entry to the path, and the
263 // range on this edge yields significantly better
265 if (TREE_CODE (arg
) == SSA_NAME
266 && defined_outside_path (arg
))
267 range_on_path_entry (r
, arg
);
269 r
.set_varying (TREE_TYPE (name
));
270 m_ranger
.range_on_edge (tmp
, e_in
, arg
);
274 r
.set_varying (TREE_TYPE (name
));
278 // If NAME is defined in BB, set R to the range of NAME, and return
279 // TRUE. Otherwise, return FALSE.
282 path_range_query::range_defined_in_block (vrange
&r
, tree name
, basic_block bb
)
284 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
285 basic_block def_bb
= gimple_bb (def_stmt
);
290 if (get_cache (r
, name
))
293 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
294 ssa_range_in_phi (r
, as_a
<gphi
*> (def_stmt
));
298 get_path_oracle ()->killing_def (name
);
300 if (!range_of_stmt (r
, def_stmt
, name
))
301 r
.set_varying (TREE_TYPE (name
));
304 if (bb
&& POINTER_TYPE_P (TREE_TYPE (name
)))
305 m_ranger
.m_cache
.m_exit
.maybe_adjust_range (r
, name
, bb
);
307 if (DEBUG_SOLVER
&& (bb
|| !r
.varying_p ()))
309 fprintf (dump_file
, "range_defined_in_block (BB%d) for ", bb
? bb
->index
: -1);
310 print_generic_expr (dump_file
, name
, TDF_SLIM
);
311 fprintf (dump_file
, " is ");
313 fprintf (dump_file
, "\n");
319 // Compute ranges defined in the PHIs in this block.
322 path_range_query::compute_ranges_in_phis (basic_block bb
)
324 // PHIs must be resolved simultaneously on entry to the block
325 // because any dependencies must be satisfied with values on entry.
326 // Thus, we calculate all PHIs first, and then update the cache at
329 for (auto iter
= gsi_start_phis (bb
); !gsi_end_p (iter
); gsi_next (&iter
))
331 gphi
*phi
= iter
.phi ();
332 tree name
= gimple_phi_result (phi
);
334 if (!exit_dependency_p (name
))
337 Value_Range
r (TREE_TYPE (name
));
338 if (range_defined_in_block (r
, name
, bb
))
339 m_cache
.set_range (name
, r
);
343 // Return TRUE if relations may be invalidated after crossing edge E.
346 path_range_query::relations_may_be_invalidated (edge e
)
348 // As soon as the path crosses a back edge, we can encounter
349 // definitions of SSA_NAMEs that may have had a use in the path
350 // already, so this will then be a new definition. The relation
351 // code is all designed around seeing things in dominator order, and
352 // crossing a back edge in the path violates this assumption.
353 return (e
->flags
& EDGE_DFS_BACK
);
356 // Compute ranges defined in the current block, or exported to the
360 path_range_query::compute_ranges_in_block (basic_block bb
)
365 if (m_resolve
&& !at_entry ())
366 compute_phi_relations (bb
, prev_bb ());
368 // Force recalculation of any names in the cache that are defined in
369 // this block. This can happen on interdependent SSA/phis in loops.
370 EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies
, 0, i
, bi
)
372 tree name
= ssa_name (i
);
373 if (ssa_defined_in_bb (name
, bb
))
374 m_cache
.clear_range (name
);
377 // Solve dependencies defined in this block, starting with the PHIs...
378 compute_ranges_in_phis (bb
);
379 // ...and then the rest of the dependencies.
380 EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies
, 0, i
, bi
)
382 tree name
= ssa_name (i
);
383 Value_Range
r (TREE_TYPE (name
));
385 if (gimple_code (SSA_NAME_DEF_STMT (name
)) != GIMPLE_PHI
386 && range_defined_in_block (r
, name
, bb
))
387 m_cache
.set_range (name
, r
);
393 // Solve dependencies that are exported to the next block.
394 basic_block next
= next_bb ();
395 edge e
= find_edge (bb
, next
);
397 if (m_resolve
&& relations_may_be_invalidated (e
))
401 "Resetting relations as they may be invalidated in %d->%d.\n",
402 e
->src
->index
, e
->dest
->index
);
404 path_oracle
*p
= get_path_oracle ();
405 // ?? Instead of nuking the root oracle altogether, we could
406 // reset the path oracle to search for relations from the top of
407 // the loop with the root oracle. Something for future development.
411 gori_compute
&g
= m_ranger
.gori ();
412 bitmap exports
= g
.exports (bb
);
413 EXECUTE_IF_AND_IN_BITMAP (m_exit_dependencies
, exports
, 0, i
, bi
)
415 tree name
= ssa_name (i
);
416 Value_Range
r (TREE_TYPE (name
));
417 if (g
.outgoing_edge_range_p (r
, e
, name
, *this))
419 Value_Range
cached_range (TREE_TYPE (name
));
420 if (get_cache (cached_range
, name
))
421 r
.intersect (cached_range
);
423 m_cache
.set_range (name
, r
);
426 fprintf (dump_file
, "outgoing_edge_range_p for ");
427 print_generic_expr (dump_file
, name
, TDF_SLIM
);
428 fprintf (dump_file
, " on edge %d->%d ",
429 e
->src
->index
, e
->dest
->index
);
430 fprintf (dump_file
, "is ");
432 fprintf (dump_file
, "\n");
438 compute_outgoing_relations (bb
, next
);
441 // Adjust all pointer exit dependencies in BB with non-null information.
444 path_range_query::adjust_for_non_null_uses (basic_block bb
)
450 EXECUTE_IF_SET_IN_BITMAP (m_exit_dependencies
, 0, i
, bi
)
452 tree name
= ssa_name (i
);
454 if (!POINTER_TYPE_P (TREE_TYPE (name
)))
457 if (get_cache (r
, name
))
463 r
.set_varying (TREE_TYPE (name
));
465 if (m_ranger
.m_cache
.m_exit
.maybe_adjust_range (r
, name
, bb
))
466 m_cache
.set_range (name
, r
);
470 // If NAME is a supported SSA_NAME, add it to the bitmap in dependencies.
473 path_range_query::add_to_exit_dependencies (tree name
, bitmap dependencies
)
475 if (TREE_CODE (name
) == SSA_NAME
476 && Value_Range::supports_type_p (TREE_TYPE (name
)))
477 return bitmap_set_bit (dependencies
, SSA_NAME_VERSION (name
));
481 // Compute the exit dependencies to PATH. These are essentially the
482 // SSA names used to calculate the final conditional along the path.
485 path_range_query::compute_exit_dependencies (bitmap dependencies
)
487 // Start with the imports from the exit block...
488 basic_block exit
= m_path
[0];
489 gori_compute
&gori
= m_ranger
.gori ();
490 bitmap_copy (dependencies
, gori
.imports (exit
));
492 auto_vec
<tree
> worklist (bitmap_count_bits (dependencies
));
495 EXECUTE_IF_SET_IN_BITMAP (dependencies
, 0, i
, bi
)
497 tree name
= ssa_name (i
);
498 worklist
.quick_push (name
);
501 // ...and add any operands used to define these imports.
502 while (!worklist
.is_empty ())
504 tree name
= worklist
.pop ();
505 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
506 if (SSA_NAME_IS_DEFAULT_DEF (name
)
507 || !m_path
.contains (gimple_bb (def_stmt
)))
510 if (gphi
*phi
= dyn_cast
<gphi
*> (def_stmt
))
512 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
514 edge e
= gimple_phi_arg_edge (phi
, i
);
515 tree arg
= gimple_phi_arg (phi
, i
)->def
;
517 if (TREE_CODE (arg
) == SSA_NAME
518 && m_path
.contains (e
->src
)
519 && bitmap_set_bit (dependencies
, SSA_NAME_VERSION (arg
)))
520 worklist
.safe_push (arg
);
523 else if (gassign
*ass
= dyn_cast
<gassign
*> (def_stmt
))
526 unsigned count
= gimple_range_ssa_names (ssa
, 3, ass
);
527 for (unsigned j
= 0; j
< count
; ++j
)
528 if (add_to_exit_dependencies (ssa
[j
], dependencies
))
529 worklist
.safe_push (ssa
[j
]);
532 // Exported booleans along the path, may help conditionals.
534 for (i
= 0; i
< m_path
.length (); ++i
)
536 basic_block bb
= m_path
[i
];
538 FOR_EACH_GORI_EXPORT_NAME (gori
, bb
, name
)
539 if (TREE_CODE (TREE_TYPE (name
)) == BOOLEAN_TYPE
)
540 bitmap_set_bit (dependencies
, SSA_NAME_VERSION (name
));
544 // Compute the ranges for DEPENDENCIES along PATH.
546 // DEPENDENCIES are path exit dependencies. They are the set of SSA
547 // names, any of which could potentially change the value of the final
548 // conditional in PATH. If none is given, the exit dependencies are
549 // calculated from the final conditional in the path.
552 path_range_query::compute_ranges (const bitmap_head
*dependencies
)
555 fprintf (dump_file
, "\n==============================================\n");
558 bitmap_copy (m_exit_dependencies
, dependencies
);
560 compute_exit_dependencies (m_exit_dependencies
);
564 path_oracle
*p
= get_path_oracle ();
565 p
->reset_path (m_ranger
.oracle ());
570 fprintf (dump_file
, "path_range_query: compute_ranges for path: ");
571 for (unsigned i
= m_path
.length (); i
> 0; --i
)
573 basic_block bb
= m_path
[i
- 1];
574 fprintf (dump_file
, "%d", bb
->index
);
576 fprintf (dump_file
, "->");
578 fprintf (dump_file
, "\n");
583 basic_block bb
= curr_bb ();
585 compute_ranges_in_block (bb
);
586 adjust_for_non_null_uses (bb
);
596 get_path_oracle ()->dump (dump_file
);
601 // A folding aid used to register and query relations along a path.
602 // When queried, it returns relations as they would appear on exit to
605 // Relations are registered on entry so the path_oracle knows which
606 // block to query the root oracle at when a relation lies outside the
607 // path. However, when queried we return the relation on exit to the
608 // path, since the root_oracle ignores the registered.
610 class jt_fur_source
: public fur_depend
613 jt_fur_source (gimple
*s
, path_range_query
*, gori_compute
*,
614 const vec
<basic_block
> &);
615 relation_kind
query_relation (tree op1
, tree op2
) override
;
616 void register_relation (gimple
*, relation_kind
, tree op1
, tree op2
) override
;
617 void register_relation (edge
, relation_kind
, tree op1
, tree op2
) override
;
622 jt_fur_source::jt_fur_source (gimple
*s
,
623 path_range_query
*query
,
625 const vec
<basic_block
> &path
)
626 : fur_depend (s
, gori
, query
)
628 gcc_checking_assert (!path
.is_empty ());
630 m_entry
= path
[path
.length () - 1];
632 if (dom_info_available_p (CDI_DOMINATORS
))
633 m_oracle
= query
->oracle ();
638 // Ignore statement and register relation on entry to path.
641 jt_fur_source::register_relation (gimple
*, relation_kind k
, tree op1
, tree op2
)
644 m_oracle
->register_relation (m_entry
, k
, op1
, op2
);
647 // Ignore edge and register relation on entry to path.
650 jt_fur_source::register_relation (edge
, relation_kind k
, tree op1
, tree op2
)
653 m_oracle
->register_relation (m_entry
, k
, op1
, op2
);
657 jt_fur_source::query_relation (tree op1
, tree op2
)
662 if (TREE_CODE (op1
) != SSA_NAME
|| TREE_CODE (op2
) != SSA_NAME
)
665 return m_oracle
->query_relation (m_entry
, op1
, op2
);
668 // Return the range of STMT at the end of the path being analyzed.
671 path_range_query::range_of_stmt (vrange
&r
, gimple
*stmt
, tree
)
673 tree type
= gimple_range_type (stmt
);
675 if (!type
|| !r
.supports_type_p (type
))
678 // If resolving unknowns, fold the statement making use of any
679 // relations along the path.
683 jt_fur_source
src (stmt
, this, &m_ranger
.gori (), m_path
);
684 if (!f
.fold_stmt (r
, stmt
, src
))
685 r
.set_varying (type
);
687 // Otherwise, fold without relations.
688 else if (!fold_range (r
, stmt
, this))
689 r
.set_varying (type
);
694 // If possible, register the relation on the incoming edge E into PHI.
697 path_range_query::maybe_register_phi_relation (gphi
*phi
, edge e
)
699 tree arg
= gimple_phi_arg_def (phi
, e
->dest_idx
);
701 if (!gimple_range_ssa_p (arg
))
704 if (relations_may_be_invalidated (e
))
707 basic_block bb
= gimple_bb (phi
);
708 tree result
= gimple_phi_result (phi
);
710 // Avoid recording the equivalence if the arg is defined in this
711 // block, as that could create an ordering problem.
712 if (ssa_defined_in_bb (arg
, bb
))
715 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
716 fprintf (dump_file
, "maybe_register_phi_relation in bb%d:", bb
->index
);
718 get_path_oracle ()->killing_def (result
);
719 m_oracle
->register_relation (entry_bb (), VREL_EQ
, arg
, result
);
722 // Compute relations for each PHI in BB. For example:
724 // x_5 = PHI<y_9(5),...>
726 // If the path flows through BB5, we can register that x_5 == y_9.
729 path_range_query::compute_phi_relations (basic_block bb
, basic_block prev
)
734 edge e_in
= find_edge (prev
, bb
);
736 for (gphi_iterator iter
= gsi_start_phis (bb
); !gsi_end_p (iter
);
739 gphi
*phi
= iter
.phi ();
740 tree result
= gimple_phi_result (phi
);
741 unsigned nargs
= gimple_phi_num_args (phi
);
743 if (!exit_dependency_p (result
))
746 for (size_t i
= 0; i
< nargs
; ++i
)
747 if (e_in
== gimple_phi_arg_edge (phi
, i
))
749 maybe_register_phi_relation (phi
, e_in
);
755 // Compute outgoing relations from BB to NEXT.
758 path_range_query::compute_outgoing_relations (basic_block bb
, basic_block next
)
760 if (gcond
*cond
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (bb
)))
763 edge e0
= EDGE_SUCC (bb
, 0);
764 edge e1
= EDGE_SUCC (bb
, 1);
766 if (e0
->dest
== next
)
767 gcond_edge_range (r
, e0
);
768 else if (e1
->dest
== next
)
769 gcond_edge_range (r
, e1
);
773 jt_fur_source
src (NULL
, this, &m_ranger
.gori (), m_path
);
774 src
.register_outgoing_edges (cond
, r
, e0
, e1
);