Branch data Line data Source code
1 : : /* Header file for jump threading path solver.
2 : : Copyright (C) 2021-2024 Free Software Foundation, Inc.
3 : : Contributed by Aldy Hernandez <aldyh@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
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
10 : : version.
11 : :
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
15 : : for more details.
16 : :
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/>. */
20 : :
21 : : #ifndef GCC_TREE_SSA_THREADSOLVER_H
22 : : #define GCC_TREE_SSA_THREADSOLVER_H
23 : :
24 : : // This class is a basic block path solver. Given a set of BBs
25 : : // indicating a path through the CFG, range_of_expr and range_of_stmt
26 : : // will calculate the range of an SSA or STMT as if the BBs in the
27 : : // path would have been executed in order.
28 : : //
29 : : // Note that the blocks are in reverse order, thus the exit block is
30 : : // path[0].
31 : :
32 : : class path_range_query : public range_query
33 : : {
34 : : public:
35 : : path_range_query (class gimple_ranger &ranger,
36 : : const vec<basic_block> &path,
37 : : const bitmap_head *dependencies = NULL,
38 : : bool resolve = true);
39 : : path_range_query (gimple_ranger &ranger, bool resolve = true);
40 : : virtual ~path_range_query ();
41 : : void reset_path (const vec<basic_block> &, const bitmap_head *dependencies);
42 : : bool range_of_expr (vrange &r, tree name, gimple * = NULL) override;
43 : : bool range_of_stmt (vrange &r, gimple *, tree name = NULL) override;
44 : : bool unreachable_path_p ();
45 : : void dump (FILE *) override;
46 : : void debug ();
47 : :
48 : : private:
49 : : bool internal_range_of_expr (vrange &r, tree name, gimple *);
50 : : void compute_ranges (const bitmap_head *dependencies);
51 : : void compute_exit_dependencies (bitmap_head *dependencies);
52 : : bool defined_outside_path (tree name);
53 : : void range_on_path_entry (vrange &r, tree name);
54 : 68405003 : path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; }
55 : :
56 : : // Cache manipulation.
57 : : bool get_cache (vrange &r, tree name);
58 : :
59 : : // Methods to compute ranges for the given path.
60 : : bool range_defined_in_block (vrange &, tree name, basic_block bb);
61 : : void compute_ranges_in_block (basic_block bb);
62 : : void compute_ranges_in_phis (basic_block bb);
63 : : void adjust_for_non_null_uses (basic_block bb);
64 : : void ssa_range_in_phi (vrange &r, gphi *phi);
65 : : void compute_outgoing_relations (basic_block bb, basic_block next);
66 : : void compute_phi_relations (basic_block bb, basic_block prev);
67 : : void maybe_register_phi_relation (gphi *, edge e);
68 : : bool add_to_exit_dependencies (tree name, bitmap dependencies);
69 : : bool exit_dependency_p (tree name);
70 : : bool ssa_defined_in_bb (tree name, basic_block bb);
71 : : bool relations_may_be_invalidated (edge);
72 : :
73 : : // Path navigation.
74 : 41936974 : basic_block entry_bb () { return m_path[m_path.length () - 1]; }
75 : : basic_block exit_bb () { return m_path[0]; }
76 : 80767123 : basic_block curr_bb () { return m_path[m_pos]; }
77 : 42909104 : basic_block prev_bb () { return m_path[m_pos + 1]; }
78 : 51076015 : basic_block next_bb () { return m_path[m_pos - 1]; }
79 : 127519220 : bool at_entry () { return m_pos == m_path.length () - 1; }
80 : 161534246 : bool at_exit () { return m_pos == 0; }
81 : 51076015 : void move_next () { --m_pos; }
82 : :
83 : : // Range cache for SSA names.
84 : : ssa_lazy_cache m_cache;
85 : :
86 : : // Path being analyzed.
87 : : auto_vec<basic_block> m_path;
88 : :
89 : : // This is a list of SSA names that may have relevant context
90 : : // information for solving the final conditional along the path.
91 : : // Ranges for these SSA names are pre-calculated and cached during a
92 : : // top-down traversal of the path, and are then used to answer
93 : : // questions at the path exit.
94 : : auto_bitmap m_exit_dependencies;
95 : :
96 : : // A ranger used to resolve ranges for SSA names whose values come
97 : : // from outside the path.
98 : : gimple_ranger &m_ranger;
99 : :
100 : : // Current path position.
101 : : unsigned m_pos;
102 : :
103 : : // Use ranger to resolve anything not known on entry.
104 : : bool m_resolve;
105 : :
106 : : // Set if there were any undefined expressions while pre-calculating path.
107 : : bool m_undefined_path;
108 : : };
109 : :
110 : : #endif // GCC_TREE_SSA_THREADSOLVER_H
|
