Branch data Line data Source code
1 : : /* Header file for SSA dominator optimizations.
2 : : Copyright (C) 2013-2025 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 : 8771502 : tree vop (void) { return m_vop; }
78 : 1745428 : tree lhs (void) { return m_lhs; }
79 : 521727897 : struct hashable_expr *expr (void) { return &m_expr; }
80 : 235452869 : expr_hash_elt *stamp (void) { return m_stamp; }
81 : 189072315 : 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 : 312446192 : static inline hashval_t hash (const value_type &p)
112 : 312446192 : { return p->hash (); }
113 : : static bool equal (const value_type &, const compare_type &);
114 : 103828811 : static inline void remove (value_type &element)
115 : 103828811 : { 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 : 2005950 : avail_exprs_stack (hash_table<expr_elt_hasher> *table)
131 : 2005950 : { m_stack.create (20); m_avail_exprs = table; }
132 : 2005950 : ~avail_exprs_stack (void) { m_stack.release (); }
133 : :
134 : : /* Push the unwinding marker onto the stack. */
135 : 60515709 : 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 : 2005950 : const_and_copies (void) { m_stack.create (20); };
180 : 2005950 : ~const_and_copies (void) { m_stack.release (); }
181 : :
182 : : /* Push the unwinding marker onto the stack. */
183 : 50683983 : 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 */
|
