1 /* Header file for jump threading path solver.
2 Copyright (C) 2021-2023 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 path_oracle *get_path_oracle () { return (path_oracle *)m_oracle; }
55
56 // Cache manipulation.
57 void set_cache (const vrange &r, tree name);
58 bool get_cache (vrange &r, tree name);
59 void clear_cache (tree name);
60
61 // Methods to compute ranges for the given path.
62 bool range_defined_in_block (vrange &, tree name, basic_block bb);
63 void compute_ranges_in_block (basic_block bb);
64 void compute_ranges_in_phis (basic_block bb);
65 void adjust_for_non_null_uses (basic_block bb);
66 void ssa_range_in_phi (vrange &r, gphi *phi);
67 void compute_outgoing_relations (basic_block bb, basic_block next);
68 void compute_phi_relations (basic_block bb, basic_block prev);
69 void maybe_register_phi_relation (gphi *, edge e);
70 bool add_to_exit_dependencies (tree name, bitmap dependencies);
71 bool exit_dependency_p (tree name);
72 bool ssa_defined_in_bb (tree name, basic_block bb);
73 bool relations_may_be_invalidated (edge);
74
75 // Path navigation.
76 basic_block entry_bb () { return m_path[m_path.length () - 1]; }
77 basic_block exit_bb () { return m_path[0]; }
78 basic_block curr_bb () { return m_path[m_pos]; }
79 basic_block prev_bb () { return m_path[m_pos + 1]; }
80 basic_block next_bb () { return m_path[m_pos - 1]; }
81 bool at_entry () { return m_pos == m_path.length () - 1; }
82 bool at_exit () { return m_pos == 0; }
83 void move_next () { --m_pos; }
84
85 // Range cache for SSA names.
86 ssa_global_cache *m_cache;
87
88 // Set for each SSA that has an active entry in the cache.
89 bitmap m_has_cache_entry;
90
91 // Path being analyzed.
92 auto_vec<basic_block> m_path;
93
94 // This is a list of SSA names that may have relevant context
95 // information for solving the final conditional along the path.
96 // Ranges for these SSA names are pre-calculated and cached during a
97 // top-down traversal of the path, and are then used to answer
98 // questions at the path exit.
99 auto_bitmap m_exit_dependencies;
100
101 // A ranger used to resolve ranges for SSA names whose values come
102 // from outside the path.
103 gimple_ranger &m_ranger;
104
105 // Current path position.
106 unsigned m_pos;
107
108 // Use ranger to resolve anything not known on entry.
109 bool m_resolve;
110
111 // Set if there were any undefined expressions while pre-calculating path.
112 bool m_undefined_path;
113 };
114
115 #endif // GCC_TREE_SSA_THREADSOLVER_H