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 (struct hashable_expr *, tree);
73 : expr_hash_elt (class expr_hash_elt &);
74 : ~expr_hash_elt ();
75 : void print (FILE *);
76 10048826 : tree vop (void) { return m_vop; }
77 2184862 : tree lhs (void) { return m_lhs; }
78 490198734 : struct hashable_expr *expr (void) { return &m_expr; }
79 201012320 : expr_hash_elt *stamp (void) { return m_stamp; }
80 150015919 : hashval_t hash (void) { return m_hash; }
81 :
82 : private:
83 : /* The expression (rhs) we want to record. */
84 : struct hashable_expr m_expr;
85 :
86 : /* The value (lhs) of this expression. */
87 : tree m_lhs;
88 :
89 : /* The virtual operand associated with the nearest dominating stmt
90 : loading from or storing to expr. */
91 : tree m_vop;
92 :
93 : /* The hash value for RHS. */
94 : hashval_t m_hash;
95 :
96 : /* A unique stamp, typically the address of the hash
97 : element itself, used in removing entries from the table. */
98 : class expr_hash_elt *m_stamp;
99 :
100 : /* We should never be making assignments between objects in this class.
101 : Though it might allow us to exploit C++11 move semantics if we
102 : defined the move constructor and move assignment operator. */
103 : expr_hash_elt& operator= (const expr_hash_elt&);
104 : };
105 :
106 : /* Hashtable helpers. */
107 :
108 : struct expr_elt_hasher : pointer_hash <expr_hash_elt>
109 : {
110 287014222 : static inline hashval_t hash (const value_type &p)
111 287014222 : { return p->hash (); }
112 : static bool equal (const value_type &, const compare_type &);
113 90622564 : static inline void remove (value_type &element)
114 90622564 : { delete element; }
115 : };
116 :
117 :
118 : /* This class defines a unwindable expression equivalence table
119 : layered on top of the expression hash table.
120 :
121 : Essentially it's just a stack of available expression value pairs with
122 : a special marker (NULL, NULL) to indicate unwind points. */
123 :
124 : class avail_exprs_stack
125 : {
126 : public:
127 : /* We need access to the AVAIL_EXPR hash table so that we can
128 : remove entries from the hash table when unwinding the stack. */
129 2136688 : avail_exprs_stack (hash_table<expr_elt_hasher> *table)
130 2136688 : { m_stack.create (20); m_avail_exprs = table; }
131 2136688 : ~avail_exprs_stack (void) { m_stack.release (); }
132 :
133 : /* Push the unwinding marker onto the stack. */
134 65843682 : void push_marker (void) { record_expr (NULL, NULL, 'M'); }
135 :
136 : /* Restore the AVAIL_EXPRs table to its state when the last marker
137 : was pushed. */
138 : void pop_to_marker (void);
139 :
140 : /* Record a single available expression that can be unwound. */
141 : void record_expr (expr_hash_elt_t, expr_hash_elt_t, char);
142 :
143 : /* Get the underlying hash table. Would this be better as
144 : class inheritance? */
145 : hash_table<expr_elt_hasher> *avail_exprs (void)
146 : { return m_avail_exprs; }
147 :
148 : /* Lookup and conditionally insert an expression into the table,
149 : recording enough information to unwind as needed. */
150 : tree lookup_avail_expr (gimple *, bool, bool, expr_hash_elt ** = NULL);
151 :
152 : void record_cond (cond_equivalence *);
153 :
154 : private:
155 : vec<std::pair<expr_hash_elt_t, expr_hash_elt_t> > m_stack;
156 : hash_table<expr_elt_hasher> *m_avail_exprs;
157 :
158 : /* We do not allow copying this object or initializing one
159 : from another. */
160 : avail_exprs_stack& operator= (const avail_exprs_stack&);
161 : avail_exprs_stack (class avail_exprs_stack &);
162 : };
163 :
164 : /* This class defines an unwindable const/copy equivalence table
165 : layered on top of SSA_NAME_VALUE/set_ssa_name_value.
166 :
167 : Essentially it's just a stack of name,prev value pairs with a
168 : special marker (NULL) to indicate unwind points. */
169 :
170 : class const_and_copies
171 : {
172 : public:
173 2136688 : const_and_copies (void) { m_stack.create (20); };
174 2136688 : ~const_and_copies (void) { m_stack.release (); }
175 :
176 : /* Push the unwinding marker onto the stack. */
177 55298111 : void push_marker (void) { m_stack.safe_push (NULL_TREE); }
178 :
179 : /* Restore the const/copies table to its state when the last marker
180 : was pushed. */
181 : void pop_to_marker (void);
182 :
183 : /* Record a single const/copy pair that can be unwound. This version
184 : may follow the value chain for the RHS. */
185 : void record_const_or_copy (tree, tree);
186 :
187 : /* Special entry point when we want to provide an explicit previous
188 : value for the first argument. Try to get rid of this in the future.
189 :
190 : This version may also follow the value chain for the RHS. */
191 : void record_const_or_copy (tree, tree, tree);
192 :
193 : private:
194 : /* Record a single const/copy pair that can be unwound. This version
195 : does not follow the value chain for the RHS. */
196 : void record_const_or_copy_raw (tree, tree, tree);
197 :
198 : vec<tree> m_stack;
199 : const_and_copies& operator= (const const_and_copies&);
200 : const_and_copies (class const_and_copies &);
201 : };
202 :
203 : void record_conditions (vec<cond_equivalence> *p, tree, tree);
204 :
205 : #endif /* GCC_TREE_SSA_SCOPED_TABLES_H */
|
