1 /* Header file for SSA dominator optimizations.
2 Copyright (C) 2013-2023 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20 #ifndef GCC_TREE_SSA_SCOPED_TABLES_H
21 #define GCC_TREE_SSA_SCOPED_TABLES_H
22
23 /* Representation of a "naked" right-hand-side expression, to be used
24 in recording available expressions in the expression hash table. */
25
26 enum expr_kind
27 {
28 EXPR_SINGLE,
29 EXPR_UNARY,
30 EXPR_BINARY,
31 EXPR_TERNARY,
32 EXPR_CALL,
33 EXPR_PHI
34 };
35
36 struct hashable_expr
37 {
38 tree type;
39 enum expr_kind kind;
40 union {
41 struct { tree rhs; } single;
42 struct { enum tree_code op; tree opnd; } unary;
43 struct { enum tree_code op; tree opnd0, opnd1; } binary;
44 struct { enum tree_code op; tree opnd0, opnd1, opnd2; } ternary;
45 struct { gcall *fn_from; bool pure; size_t nargs; tree *args; } call;
46 struct { size_t nargs; tree *args; } phi;
47 } ops;
48 };
49
50 /* Structure for recording known value of a conditional expression.
51
52 Clients build vectors of these objects to record known values
53 that occur on edges. */
54
55 struct cond_equivalence
56 {
57 /* The condition, in a HASHABLE_EXPR form. */
58 struct hashable_expr cond;
59
60 /* The result of the condition (true or false. */
61 tree value;
62 };
63
64 /* Structure for entries in the expression hash table. */
65
66 typedef class expr_hash_elt * expr_hash_elt_t;
67
68 class expr_hash_elt
69 {
70 public:
71 expr_hash_elt (gimple *, tree);
72 expr_hash_elt (tree);
73 expr_hash_elt (struct hashable_expr *, tree);
74 expr_hash_elt (class expr_hash_elt &);
75 ~expr_hash_elt ();
76 void print (FILE *);
77 tree vop (void) { return m_vop; }
78 tree lhs (void) { return m_lhs; }
79 struct hashable_expr *expr (void) { return &m_expr; }
80 expr_hash_elt *stamp (void) { return m_stamp; }
81 hashval_t hash (void) { return m_hash; }
82
83 private:
84 /* The expression (rhs) we want to record. */
85 struct hashable_expr m_expr;
86
87 /* The value (lhs) of this expression. */
88 tree m_lhs;
89
90 /* The virtual operand associated with the nearest dominating stmt
91 loading from or storing to expr. */
92 tree m_vop;
93
94 /* The hash value for RHS. */
95 hashval_t m_hash;
96
97 /* A unique stamp, typically the address of the hash
98 element itself, used in removing entries from the table. */
99 class expr_hash_elt *m_stamp;
100
101 /* We should never be making assignments between objects in this class.
102 Though it might allow us to exploit C++11 move semantics if we
103 defined the move constructor and move assignment operator. */
104 expr_hash_elt& operator= (const expr_hash_elt&);
105 };
106
107 /* Hashtable helpers. */
108
109 struct expr_elt_hasher : pointer_hash <expr_hash_elt>
110 {
111 static inline hashval_t hash (const value_type &p)
112 { return p->hash (); }
113 static bool equal (const value_type &, const compare_type &);
114 static inline void remove (value_type &element)
115 { delete element; }
116 };
117
118
119 /* This class defines a unwindable expression equivalence table
120 layered on top of the expression hash table.
121
122 Essentially it's just a stack of available expression value pairs with
123 a special marker (NULL, NULL) to indicate unwind points. */
124
125 class avail_exprs_stack
126 {
127 public:
128 /* We need access to the AVAIL_EXPR hash table so that we can
129 remove entries from the hash table when unwinding the stack. */
130 avail_exprs_stack (hash_table<expr_elt_hasher> *table)
131 { m_stack.create (20); m_avail_exprs = table; }
132 ~avail_exprs_stack (void) { m_stack.release (); }
133
134 /* Push the unwinding marker onto the stack. */
135 void push_marker (void) { record_expr (NULL, NULL, 'M'); }
136
137 /* Restore the AVAIL_EXPRs table to its state when the last marker
138 was pushed. */
139 void pop_to_marker (void);
140
141 /* Record a single available expression that can be unwound. */
142 void record_expr (expr_hash_elt_t, expr_hash_elt_t, char);
143
144 /* Get the underlying hash table. Would this be better as
145 class inheritance? */
146 hash_table<expr_elt_hasher> *avail_exprs (void)
147 { return m_avail_exprs; }
148
149 /* Lookup and conditionally insert an expression into the table,
150 recording enough information to unwind as needed. */
151 tree lookup_avail_expr (gimple *, bool, bool, expr_hash_elt ** = NULL);
152
153 void record_cond (cond_equivalence *);
154
155 private:
156 vec<std::pair<expr_hash_elt_t, expr_hash_elt_t> > m_stack;
157 hash_table<expr_elt_hasher> *m_avail_exprs;
158
159 /* For some assignments where the RHS is a binary operator, if we know
160 a equality relationship between the operands, we may be able to compute
161 a result, even if we don't know the exact value of the operands. */
162 tree simplify_binary_operation (gimple *, class expr_hash_elt);
163
164 /* We do not allow copying this object or initializing one
165 from another. */
166 avail_exprs_stack& operator= (const avail_exprs_stack&);
167 avail_exprs_stack (class avail_exprs_stack &);
168 };
169
170 /* This class defines an unwindable const/copy equivalence table
171 layered on top of SSA_NAME_VALUE/set_ssa_name_value.
172
173 Essentially it's just a stack of name,prev value pairs with a
174 special marker (NULL) to indicate unwind points. */
175
176 class const_and_copies
177 {
178 public:
179 const_and_copies (void) { m_stack.create (20); };
180 ~const_and_copies (void) { m_stack.release (); }
181
182 /* Push the unwinding marker onto the stack. */
183 void push_marker (void) { m_stack.safe_push (NULL_TREE); }
184
185 /* Restore the const/copies table to its state when the last marker
186 was pushed. */
187 void pop_to_marker (void);
188
189 /* Record a single const/copy pair that can be unwound. This version
190 may follow the value chain for the RHS. */
191 void record_const_or_copy (tree, tree);
192
193 /* Special entry point when we want to provide an explicit previous
194 value for the first argument. Try to get rid of this in the future.
195
196 This version may also follow the value chain for the RHS. */
197 void record_const_or_copy (tree, tree, tree);
198
199 private:
200 /* Record a single const/copy pair that can be unwound. This version
201 does not follow the value chain for the RHS. */
202 void record_const_or_copy_raw (tree, tree, tree);
203
204 vec<tree> m_stack;
205 const_and_copies& operator= (const const_and_copies&);
206 const_and_copies (class const_and_copies &);
207 };
208
209 void initialize_expr_from_cond (tree cond, struct hashable_expr *expr);
210 void record_conditions (vec<cond_equivalence> *p, tree, tree);
211
212 #endif /* GCC_TREE_SSA_SCOPED_TABLES_H */