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 && dump_flags & TDF_THREADING)
39 path_range_query::path_range_query (gimple_ranger
&ranger
, bool resolve
)
42 m_cache
= new ssa_global_cache
;
43 m_has_cache_entry
= BITMAP_ALLOC (NULL
);
46 m_oracle
= new path_oracle (ranger
.oracle ());
49 path_range_query::~path_range_query ()
51 BITMAP_FREE (m_has_cache_entry
);
56 // Mark cache entry for NAME as unused.
59 path_range_query::clear_cache (tree name
)
61 unsigned v
= SSA_NAME_VERSION (name
);
62 bitmap_clear_bit (m_has_cache_entry
, v
);
65 // If NAME has a cache entry, return it in R, and return TRUE.
68 path_range_query::get_cache (irange
&r
, tree name
)
70 if (!gimple_range_ssa_p (name
))
71 return get_global_range_query ()->range_of_expr (r
, name
);
73 unsigned v
= SSA_NAME_VERSION (name
);
74 if (bitmap_bit_p (m_has_cache_entry
, v
))
75 return m_cache
->get_global_range (r
, name
);
80 // Set the cache entry for NAME to R.
83 path_range_query::set_cache (const irange
&r
, tree name
)
85 unsigned v
= SSA_NAME_VERSION (name
);
86 bitmap_set_bit (m_has_cache_entry
, v
);
87 m_cache
->set_global_range (name
, r
);
91 path_range_query::dump (FILE *dump_file
)
93 push_dump_file
save (dump_file
, dump_flags
& ~TDF_DETAILS
);
95 if (m_path
->is_empty ())
101 fprintf (dump_file
, "\nPath is (length=%d):\n", m_path
->length ());
102 dump_ranger (dump_file
, *m_path
);
104 fprintf (dump_file
, "Imports:\n");
105 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
107 tree name
= ssa_name (i
);
108 print_generic_expr (dump_file
, name
, TDF_SLIM
);
109 fprintf (dump_file
, "\n");
112 m_cache
->dump (dump_file
);
116 path_range_query::debug ()
121 // Return TRUE if NAME is defined outside the current path.
124 path_range_query::defined_outside_path (tree name
)
126 gimple
*def
= SSA_NAME_DEF_STMT (name
);
127 basic_block bb
= gimple_bb (def
);
129 return !bb
|| !m_path
->contains (bb
);
132 // Return the range of NAME on entry to the path.
135 path_range_query::range_on_path_entry (irange
&r
, tree name
)
138 basic_block entry
= entry_bb ();
139 bool changed
= false;
142 for (unsigned i
= 0; i
< EDGE_COUNT (entry
->preds
); ++i
)
144 edge e
= EDGE_PRED (entry
, i
);
145 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
146 && m_ranger
.range_on_edge (tmp
, e
, name
))
153 // Make sure we don't return UNDEFINED by mistake.
155 r
.set_varying (TREE_TYPE (name
));
158 // Return the range of NAME at the end of the path being analyzed.
161 path_range_query::internal_range_of_expr (irange
&r
, tree name
, gimple
*stmt
)
163 if (!irange::supports_type_p (TREE_TYPE (name
)))
166 if (get_cache (r
, name
))
169 if (m_resolve
&& defined_outside_path (name
))
171 range_on_path_entry (r
, name
);
176 basic_block bb
= stmt
? gimple_bb (stmt
) : exit_bb ();
177 if (stmt
&& range_defined_in_block (r
, name
, bb
))
179 if (TREE_CODE (name
) == SSA_NAME
)
180 r
.intersect (gimple_range_global (name
));
186 r
.set_varying (TREE_TYPE (name
));
191 path_range_query::range_of_expr (irange
&r
, tree name
, gimple
*stmt
)
193 if (internal_range_of_expr (r
, name
, stmt
))
195 if (r
.undefined_p ())
196 m_undefined_path
= true;
204 path_range_query::unreachable_path_p ()
206 return m_undefined_path
;
209 // Initialize the current path to PATH. The current block is set to
210 // the entry block to the path.
212 // Note that the blocks are in reverse order, so the exit block is
216 path_range_query::set_path (const vec
<basic_block
> &path
)
218 gcc_checking_assert (path
.length () > 1);
220 m_pos
= m_path
->length () - 1;
221 bitmap_clear (m_has_cache_entry
);
224 // Return the range of the result of PHI in R.
227 path_range_query::ssa_range_in_phi (irange
&r
, gphi
*phi
)
229 tree name
= gimple_phi_result (phi
);
230 basic_block bb
= gimple_bb (phi
);
234 if (m_resolve
&& m_ranger
.range_of_expr (r
, name
, phi
))
237 // Try fold just in case we can resolve simple things like PHI <5(99), 6(88)>.
238 if (!fold_range (r
, phi
, this))
239 r
.set_varying (TREE_TYPE (name
));
244 basic_block prev
= prev_bb ();
245 edge e_in
= find_edge (prev
, bb
);
246 unsigned nargs
= gimple_phi_num_args (phi
);
248 for (size_t i
= 0; i
< nargs
; ++i
)
249 if (e_in
== gimple_phi_arg_edge (phi
, i
))
251 tree arg
= gimple_phi_arg_def (phi
, i
);
253 if (!get_cache (r
, arg
))
258 // Using both the range on entry to the path, and the
259 // range on this edge yields significantly better
261 range_on_path_entry (r
, arg
);
262 m_ranger
.range_on_edge (tmp
, e_in
, arg
);
266 r
.set_varying (TREE_TYPE (name
));
273 // If NAME is defined in BB, set R to the range of NAME, and return
274 // TRUE. Otherwise, return FALSE.
277 path_range_query::range_defined_in_block (irange
&r
, tree name
, basic_block bb
)
279 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
280 basic_block def_bb
= gimple_bb (def_stmt
);
285 if (gimple_code (def_stmt
) == GIMPLE_PHI
)
286 ssa_range_in_phi (r
, as_a
<gphi
*> (def_stmt
));
287 else if (!range_of_stmt (r
, def_stmt
, name
))
288 r
.set_varying (TREE_TYPE (name
));
291 m_non_null
.adjust_range (r
, name
, bb
);
293 if (DEBUG_SOLVER
&& (bb
|| !r
.varying_p ()))
295 fprintf (dump_file
, "range_defined_in_block (BB%d) for ", bb
? bb
->index
: -1);
296 print_generic_expr (dump_file
, name
, TDF_SLIM
);
297 fprintf (dump_file
, " is ");
299 fprintf (dump_file
, "\n");
305 // Compute ranges defined in the current block, or exported to the
309 path_range_query::compute_ranges_in_block (basic_block bb
)
312 int_range_max r
, cached_range
;
315 // Force recalculation of any names in the cache that are defined in
316 // this block. This can happen on interdependent SSA/phis in loops.
317 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
319 tree name
= ssa_name (i
);
320 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
321 basic_block def_bb
= gimple_bb (def_stmt
);
327 // Solve imports defined in this block.
328 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
330 tree name
= ssa_name (i
);
332 if (range_defined_in_block (r
, name
, bb
))
339 // Solve imports that are exported to the next block.
340 edge e
= find_edge (bb
, next_bb ());
341 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
343 tree name
= ssa_name (i
);
344 gori_compute
&g
= m_ranger
.gori ();
345 bitmap exports
= g
.exports (bb
);
347 if (bitmap_bit_p (exports
, i
))
349 if (g
.outgoing_edge_range_p (r
, e
, name
, *this))
351 if (get_cache (cached_range
, name
))
352 r
.intersect (cached_range
);
357 fprintf (dump_file
, "outgoing_edge_range_p for ");
358 print_generic_expr (dump_file
, name
, TDF_SLIM
);
359 fprintf (dump_file
, " on edge %d->%d ",
360 e
->src
->index
, e
->dest
->index
);
361 fprintf (dump_file
, "is ");
363 fprintf (dump_file
, "\n");
370 // Adjust all pointer imports in BB with non-null information.
373 path_range_query::adjust_for_non_null_uses (basic_block bb
)
379 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
381 tree name
= ssa_name (i
);
383 if (!POINTER_TYPE_P (TREE_TYPE (name
)))
386 if (get_cache (r
, name
))
392 r
.set_varying (TREE_TYPE (name
));
394 if (m_non_null
.adjust_range (r
, name
, bb
))
399 // If NAME is a supported SSA_NAME, add it the bitmap in IMPORTS.
402 path_range_query::add_to_imports (tree name
, bitmap imports
)
404 if (TREE_CODE (name
) == SSA_NAME
405 && irange::supports_type_p (TREE_TYPE (name
)))
406 return bitmap_set_bit (imports
, SSA_NAME_VERSION (name
));
410 // Add the copies of any SSA names in IMPORTS to IMPORTS.
412 // These are hints for the solver. Adding more elements (within
413 // reason) doesn't slow us down, because we don't solve anything that
414 // doesn't appear in the path. On the other hand, not having enough
415 // imports will limit what we can solve.
418 path_range_query::add_copies_to_imports ()
420 auto_vec
<tree
> worklist (bitmap_count_bits (m_imports
));
424 EXECUTE_IF_SET_IN_BITMAP (m_imports
, 0, i
, bi
)
426 tree name
= ssa_name (i
);
427 worklist
.quick_push (name
);
430 while (!worklist
.is_empty ())
432 tree name
= worklist
.pop ();
433 gimple
*def_stmt
= SSA_NAME_DEF_STMT (name
);
435 if (is_gimple_assign (def_stmt
))
437 // ?? Adding assignment copies doesn't get us much. At the
438 // time of writing, we got 63 more threaded paths across the
439 // .ii files from a bootstrap.
440 add_to_imports (gimple_assign_rhs1 (def_stmt
), m_imports
);
441 tree rhs
= gimple_assign_rhs2 (def_stmt
);
442 if (rhs
&& add_to_imports (rhs
, m_imports
))
443 worklist
.safe_push (rhs
);
444 rhs
= gimple_assign_rhs3 (def_stmt
);
445 if (rhs
&& add_to_imports (rhs
, m_imports
))
446 worklist
.safe_push (rhs
);
448 else if (gphi
*phi
= dyn_cast
<gphi
*> (def_stmt
))
450 for (size_t i
= 0; i
< gimple_phi_num_args (phi
); ++i
)
452 edge e
= gimple_phi_arg_edge (phi
, i
);
453 tree arg
= gimple_phi_arg (phi
, i
)->def
;
455 if (TREE_CODE (arg
) == SSA_NAME
456 && m_path
->contains (e
->src
)
457 && bitmap_set_bit (m_imports
, SSA_NAME_VERSION (arg
)))
458 worklist
.safe_push (arg
);
464 // Compute the ranges for IMPORTS along PATH.
466 // IMPORTS are the set of SSA names, any of which could potentially
467 // change the value of the final conditional in PATH.
470 path_range_query::compute_ranges (const vec
<basic_block
> &path
,
471 const bitmap_head
*imports
)
474 fprintf (dump_file
, "\n*********** path_range_query ******************\n");
477 bitmap_copy (m_imports
, imports
);
478 m_undefined_path
= false;
482 add_copies_to_imports ();
483 get_path_oracle ()->reset_path ();
484 compute_relations (path
);
489 fprintf (dump_file
, "\npath_range_query: compute_ranges for path: ");
490 for (unsigned i
= path
.length (); i
> 0; --i
)
492 basic_block bb
= path
[i
- 1];
493 fprintf (dump_file
, "BB %d", bb
->index
);
495 fprintf (dump_file
, ", ");
497 fprintf (dump_file
, "\n");
502 basic_block bb
= curr_bb ();
506 gori_compute
&gori
= m_ranger
.gori ();
509 // Exported booleans along the path, may help conditionals.
510 // Add them as interesting imports.
511 FOR_EACH_GORI_EXPORT_NAME (gori
, bb
, name
)
512 if (TREE_CODE (TREE_TYPE (name
)) == BOOLEAN_TYPE
)
513 bitmap_set_bit (m_imports
, SSA_NAME_VERSION (name
));
516 compute_ranges_in_block (bb
);
517 adjust_for_non_null_uses (bb
);
529 // A folding aid used to register and query relations along a path.
530 // When queried, it returns relations as they would appear on exit to
533 // Relations are registered on entry so the path_oracle knows which
534 // block to query the root oracle at when a relation lies outside the
535 // path. However, when queried we return the relation on exit to the
536 // path, since the root_oracle ignores the registered.
538 class jt_fur_source
: public fur_depend
541 jt_fur_source (gimple
*s
, path_range_query
*, gori_compute
*,
542 const vec
<basic_block
> &);
543 relation_kind
query_relation (tree op1
, tree op2
) override
;
544 void register_relation (gimple
*, relation_kind
, tree op1
, tree op2
) override
;
545 void register_relation (edge
, relation_kind
, tree op1
, tree op2
) override
;
550 jt_fur_source::jt_fur_source (gimple
*s
,
551 path_range_query
*query
,
553 const vec
<basic_block
> &path
)
554 : fur_depend (s
, gori
, query
)
556 gcc_checking_assert (!path
.is_empty ());
558 m_entry
= path
[path
.length () - 1];
560 if (dom_info_available_p (CDI_DOMINATORS
))
561 m_oracle
= query
->oracle ();
566 // Ignore statement and register relation on entry to path.
569 jt_fur_source::register_relation (gimple
*, relation_kind k
, tree op1
, tree op2
)
572 m_oracle
->register_relation (m_entry
, k
, op1
, op2
);
575 // Ignore edge and register relation on entry to path.
578 jt_fur_source::register_relation (edge
, relation_kind k
, tree op1
, tree op2
)
581 m_oracle
->register_relation (m_entry
, k
, op1
, op2
);
585 jt_fur_source::query_relation (tree op1
, tree op2
)
590 if (TREE_CODE (op1
) != SSA_NAME
|| TREE_CODE (op2
) != SSA_NAME
)
593 return m_oracle
->query_relation (m_entry
, op1
, op2
);
596 // Return the range of STMT at the end of the path being analyzed.
599 path_range_query::range_of_stmt (irange
&r
, gimple
*stmt
, tree
)
601 tree type
= gimple_range_type (stmt
);
603 if (!irange::supports_type_p (type
))
606 // If resolving unknowns, fold the statement as it would have
607 // appeared at the end of the path.
611 jt_fur_source
src (stmt
, this, &m_ranger
.gori (), *m_path
);
612 if (!f
.fold_stmt (r
, stmt
, src
))
613 r
.set_varying (type
);
615 // Otherwise, use the global ranger to fold it as it would appear in
616 // the original IL. This is more conservative, but faster.
617 else if (!fold_range (r
, stmt
, this))
618 r
.set_varying (type
);
623 // Compute relations on a path. This involves two parts: relations
624 // along the conditionals joining a path, and relations determined by
628 path_range_query::compute_relations (const vec
<basic_block
> &path
)
630 if (!dom_info_available_p (CDI_DOMINATORS
))
633 jt_fur_source
src (NULL
, this, &m_ranger
.gori (), path
);
634 basic_block prev
= NULL
;
635 for (unsigned i
= path
.length (); i
> 0; --i
)
637 basic_block bb
= path
[i
- 1];
638 gimple
*stmt
= last_stmt (bb
);
640 compute_phi_relations (bb
, prev
);
642 // Compute relations in outgoing edges along the path. Skip the
643 // final conditional which we don't know yet.
646 && gimple_code (stmt
) == GIMPLE_COND
647 && irange::supports_type_p (TREE_TYPE (gimple_cond_lhs (stmt
))))
649 basic_block next
= path
[i
- 2];
651 gcond
*cond
= as_a
<gcond
*> (stmt
);
652 edge e0
= EDGE_SUCC (bb
, 0);
653 edge e1
= EDGE_SUCC (bb
, 1);
655 if (e0
->dest
== next
)
656 gcond_edge_range (r
, e0
);
657 else if (e1
->dest
== next
)
658 gcond_edge_range (r
, e1
);
662 src
.register_outgoing_edges (cond
, r
, e0
, e1
);
668 // Compute relations for each PHI in BB. For example:
670 // x_5 = PHI<y_9(5),...>
672 // If the path flows through BB5, we can register that x_5 == y_9.
675 path_range_query::compute_phi_relations (basic_block bb
, basic_block prev
)
680 basic_block entry
= entry_bb ();
681 edge e_in
= find_edge (prev
, bb
);
682 gcc_checking_assert (e_in
);
684 for (gphi_iterator iter
= gsi_start_phis (bb
); !gsi_end_p (iter
);
687 gphi
*phi
= iter
.phi ();
688 tree result
= gimple_phi_result (phi
);
689 unsigned nargs
= gimple_phi_num_args (phi
);
691 for (size_t i
= 0; i
< nargs
; ++i
)
692 if (e_in
== gimple_phi_arg_edge (phi
, i
))
694 tree arg
= gimple_phi_arg_def (phi
, i
);
696 if (gimple_range_ssa_p (arg
))
697 m_oracle
->register_relation (entry
, EQ_EXPR
, arg
, result
);