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