1 | /* Interprocedural semantic function equality pass |
2 | Copyright (C) 2014-2024 Free Software Foundation, Inc. |
3 | |
4 | Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz> |
5 | |
6 | This file is part of GCC. |
7 | |
8 | GCC is free software; you can redistribute it and/or modify it under |
9 | the terms of the GNU General Public License as published by the Free |
10 | Software Foundation; either version 3, or (at your option) any later |
11 | version. |
12 | |
13 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
14 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |
15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
16 | for more details. |
17 | |
18 | You should have received a copy of the GNU General Public License |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ |
21 | |
22 | /* Gimple identical code folding (class func_checker) is an infrastructure |
23 | capable of comparing two given functions. The class compares every |
24 | gimple statement and uses many dictionaries to map source and target |
25 | SSA_NAMEs, declarations and other components. |
26 | |
27 | To use the infrastructure, create an instance of func_checker and call |
28 | a comparison function based on type of gimple statement. */ |
29 | |
30 | /* Prints string STRING to a FILE with a given number of SPACE_COUNT. */ |
31 | #define FPUTS_SPACES(file, space_count, string) \ |
32 | fprintf (file, "%*s" string, space_count, " "); |
33 | |
34 | /* fprintf function wrapper that transforms given FORMAT to follow given |
35 | number for SPACE_COUNT and call fprintf for a FILE. */ |
36 | #define FPRINTF_SPACES(file, space_count, format, ...) \ |
37 | fprintf (file, "%*s" format, space_count, " ", ##__VA_ARGS__); |
38 | |
39 | /* Logs a MESSAGE to dump_file if exists and returns false. FUNC is name |
40 | of function and LINE is location in the source file. */ |
41 | |
42 | inline bool |
43 | return_false_with_message_1 (const char *message, const char *filename, |
44 | const char *func, unsigned int line) |
45 | { |
46 | if (dump_file && (dump_flags & TDF_DETAILS)) |
47 | fprintf (stream: dump_file, format: " false returned: '%s' in %s at %s:%u\n" , message, func, |
48 | filename, line); |
49 | return false; |
50 | } |
51 | |
52 | /* Logs a MESSAGE to dump_file if exists and returns false. */ |
53 | #define return_false_with_msg(message) \ |
54 | return_false_with_message_1 (message, __FILE__, __func__, __LINE__) |
55 | |
56 | /* Return false and log that false value is returned. */ |
57 | #define return_false() return_false_with_msg ("") |
58 | |
59 | /* Logs return value if RESULT is false. FUNC is name of function and LINE |
60 | is location in the source file. */ |
61 | |
62 | inline bool |
63 | return_with_result (bool result, const char *filename, |
64 | const char *func, unsigned int line) |
65 | { |
66 | if (!result && dump_file && (dump_flags & TDF_DETAILS)) |
67 | fprintf (stream: dump_file, format: " false returned: '' in %s at %s:%u\n" , func, |
68 | filename, line); |
69 | |
70 | return result; |
71 | } |
72 | |
73 | /* Logs return value if RESULT is false. */ |
74 | #define return_with_debug(result) return_with_result \ |
75 | (result, __FILE__, __func__, __LINE__) |
76 | |
77 | /* Verbose logging function logging statements S1 and S2 of a CODE. |
78 | FUNC is name of function and LINE is location in the source file. */ |
79 | |
80 | inline bool |
81 | return_different_stmts_1 (gimple *s1, gimple *s2, const char *code, |
82 | const char *func, unsigned int line) |
83 | { |
84 | if (dump_file && (dump_flags & TDF_DETAILS)) |
85 | { |
86 | fprintf (stream: dump_file, format: " different statement for code: %s (%s:%u):\n" , |
87 | code, func, line); |
88 | |
89 | print_gimple_stmt (dump_file, s1, 3, TDF_DETAILS); |
90 | print_gimple_stmt (dump_file, s2, 3, TDF_DETAILS); |
91 | } |
92 | |
93 | return false; |
94 | } |
95 | |
96 | /* Verbose logging function logging statements S1 and S2 of a CODE. */ |
97 | #define return_different_stmts(s1, s2, code) \ |
98 | return_different_stmts_1 (s1, s2, code, __func__, __LINE__) |
99 | |
100 | namespace ipa_icf_gimple { |
101 | |
102 | /* Basic block struct for semantic equality pass. */ |
103 | class sem_bb |
104 | { |
105 | public: |
106 | sem_bb (basic_block bb_, unsigned nondbg_stmt_count_, unsigned edge_count_): |
107 | bb (bb_), nondbg_stmt_count (nondbg_stmt_count_), edge_count (edge_count_) {} |
108 | |
109 | /* Basic block the structure belongs to. */ |
110 | basic_block bb; |
111 | |
112 | /* Number of non-debug statements in the basic block. */ |
113 | unsigned nondbg_stmt_count; |
114 | |
115 | /* Number of edges connected to the block. */ |
116 | unsigned edge_count; |
117 | }; |
118 | |
119 | /* A class aggregating all connections and semantic equivalents |
120 | for a given pair of semantic function candidates. */ |
121 | class func_checker : ao_compare |
122 | { |
123 | public: |
124 | /* Default constructor. */ |
125 | func_checker (): |
126 | m_source_func_decl (NULL_TREE), m_target_func_decl (NULL_TREE), |
127 | m_ignored_source_nodes (NULL), m_ignored_target_nodes (NULL), |
128 | m_ignore_labels (false), m_tbaa (true), |
129 | m_total_scalarization_limit_known_p (false) |
130 | { |
131 | m_source_ssa_names.create (nelems: 0); |
132 | m_target_ssa_names.create (nelems: 0); |
133 | } |
134 | |
135 | /* Initialize internal structures for a given SOURCE_FUNC_DECL and |
136 | TARGET_FUNC_DECL. Strict polymorphic comparison is processed if |
137 | an option COMPARE_POLYMORPHIC is true. For special cases, one can |
138 | set IGNORE_LABELS to skip label comparison. |
139 | Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets |
140 | of declarations that can be skipped. */ |
141 | func_checker (tree source_func_decl, tree target_func_decl, |
142 | bool ignore_labels = false, |
143 | bool tbaa = true, |
144 | hash_set<symtab_node *> *ignored_source_nodes = NULL, |
145 | hash_set<symtab_node *> *ignored_target_nodes = NULL); |
146 | |
147 | /* Memory release routine. */ |
148 | virtual ~func_checker (); |
149 | |
150 | /* Function visits all gimple labels and creates corresponding |
151 | mapping between basic blocks and labels. */ |
152 | void parse_labels (sem_bb *bb); |
153 | |
154 | /* Basic block equivalence comparison function that returns true if |
155 | basic blocks BB1 and BB2 correspond. */ |
156 | bool compare_bb (sem_bb *bb1, sem_bb *bb2); |
157 | |
158 | /* Verifies that trees T1 and T2 are equivalent from perspective of ICF. */ |
159 | bool compare_ssa_name (const_tree t1, const_tree t2); |
160 | |
161 | /* Verification function for edges E1 and E2. */ |
162 | bool compare_edge (edge e1, edge e2); |
163 | |
164 | /* Verifies for given GIMPLEs S1 and S2 that |
165 | call statements are semantically equivalent. */ |
166 | bool compare_gimple_call (gcall *s1, gcall *s2); |
167 | |
168 | /* Verifies for given GIMPLEs S1 and S2 that |
169 | assignment statements are semantically equivalent. */ |
170 | bool compare_gimple_assign (gimple *s1, gimple *s2); |
171 | |
172 | /* Verifies for given GIMPLEs S1 and S2 that |
173 | condition statements are semantically equivalent. */ |
174 | bool compare_gimple_cond (gimple *s1, gimple *s2); |
175 | |
176 | /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that |
177 | label statements are semantically equivalent. */ |
178 | bool compare_gimple_label (const glabel *s1, const glabel *s2); |
179 | |
180 | /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that |
181 | switch statements are semantically equivalent. */ |
182 | bool compare_gimple_switch (const gswitch *s1, const gswitch *s2); |
183 | |
184 | /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that |
185 | return statements are semantically equivalent. */ |
186 | bool compare_gimple_return (const greturn *s1, const greturn *s2); |
187 | |
188 | /* Verifies for given GIMPLEs S1 and S2 that |
189 | goto statements are semantically equivalent. */ |
190 | bool compare_gimple_goto (gimple *s1, gimple *s2); |
191 | |
192 | /* Verifies for given GIMPLE_RESX stmts S1 and S2 that |
193 | resx statements are semantically equivalent. */ |
194 | bool compare_gimple_resx (const gresx *s1, const gresx *s2); |
195 | |
196 | /* Verifies for given GIMPLE_ASM stmts S1 and S2 that ASM statements |
197 | are equivalent. |
198 | For the beginning, the pass only supports equality for |
199 | '__asm__ __volatile__ ("", "", "", "memory")'. */ |
200 | bool compare_gimple_asm (const gasm *s1, const gasm *s2); |
201 | |
202 | /* Verification function for declaration trees T1 and T2. */ |
203 | bool compare_decl (const_tree t1, const_tree t2); |
204 | |
205 | /* Compute hash map MAP that determines loads and stores of STMT. */ |
206 | enum operand_access_type {OP_MEMORY, OP_NORMAL}; |
207 | typedef hash_set<tree> operand_access_type_map; |
208 | |
209 | /* Return true if either T1 and T2 cannot be totally scalarized or if doing |
210 | so would result in copying the same memory. Otherwise return false. */ |
211 | bool safe_for_total_scalarization_p (tree t1, tree t2); |
212 | |
213 | /* Function responsible for comparison of various operands T1 and T2. |
214 | If these components, from functions FUNC1 and FUNC2, are equal, true |
215 | is returned. */ |
216 | bool compare_operand (tree t1, tree t2, operand_access_type type); |
217 | |
218 | /* Compares GIMPLE ASM inputs (or outputs) where we iterate tree chain |
219 | and compare both TREE_PURPOSEs and TREE_VALUEs. */ |
220 | bool compare_asm_inputs_outputs (tree t1, tree t2, |
221 | operand_access_type_map *map); |
222 | |
223 | /* Verifies that trees T1 and T2, representing function declarations |
224 | are equivalent from perspective of ICF. */ |
225 | bool compare_function_decl (tree t1, tree t2); |
226 | |
227 | /* Verifies that trees T1 and T2 do correspond. */ |
228 | bool compare_variable_decl (const_tree t1, const_tree t2); |
229 | |
230 | /* Compare loop information for basic blocks BB1 and BB2. */ |
231 | bool compare_loops (basic_block bb1, basic_block bb2); |
232 | |
233 | /* Return true if types are compatible for polymorphic call analysis. |
234 | COMPARE_PTR indicates if polymorphic type comparison should be |
235 | done for pointers, too. */ |
236 | static bool compatible_polymorphic_types_p (tree t1, tree t2, |
237 | bool compare_ptr); |
238 | |
239 | /* Return true if types are compatible from perspective of ICF. |
240 | FIRST_ARGUMENT indicates if the comparison is called for |
241 | first parameter of a function. */ |
242 | static bool compatible_types_p (tree t1, tree t2); |
243 | |
244 | /* Compute hash map determining access types of operands. */ |
245 | static void classify_operands (const gimple *stmt, |
246 | operand_access_type_map *map); |
247 | |
248 | /* Return access type of a given operand. */ |
249 | static operand_access_type get_operand_access_type |
250 | (operand_access_type_map *map, tree); |
251 | private: |
252 | /* Vector mapping source SSA names to target ones. */ |
253 | vec <int> m_source_ssa_names; |
254 | |
255 | /* Vector mapping target SSA names to source ones. */ |
256 | vec <int> m_target_ssa_names; |
257 | |
258 | /* Source TREE function declaration. */ |
259 | tree m_source_func_decl; |
260 | |
261 | /* Target TREE function declaration. */ |
262 | tree m_target_func_decl; |
263 | |
264 | /* Source symbol nodes that should be skipped by |
265 | declaration comparison. */ |
266 | hash_set<symtab_node *> *m_ignored_source_nodes; |
267 | |
268 | /* Target symbol nodes that should be skipped by |
269 | declaration comparison. */ |
270 | hash_set<symtab_node *> *m_ignored_target_nodes; |
271 | |
272 | /* Source to target edge map. */ |
273 | hash_map <edge, edge> m_edge_map; |
274 | |
275 | /* Source to target declaration map. */ |
276 | hash_map <const_tree, const_tree> m_decl_map; |
277 | |
278 | /* Label to basic block index mapping. */ |
279 | hash_map <const_tree, int> m_label_bb_map; |
280 | |
281 | /* Flag if ignore labels in comparison. */ |
282 | bool m_ignore_labels; |
283 | |
284 | /* Flag if we should compare type based alias analysis info. */ |
285 | bool m_tbaa; |
286 | |
287 | /* Set to true when total scalarization size has already been determined for |
288 | the functions. */ |
289 | bool m_total_scalarization_limit_known_p; |
290 | |
291 | /* When the above it set to true the determiend total scalarization |
292 | limit. */ |
293 | unsigned HOST_WIDE_INT m_total_scalarization_limit; |
294 | |
295 | public: |
296 | /* Return true if two operands are equal. The flags fields can be used |
297 | to specify OEP flags described above. */ |
298 | bool operand_equal_p (const_tree, const_tree, unsigned int flags) |
299 | final override; |
300 | |
301 | /* Generate a hash value for an expression. This can be used iteratively |
302 | by passing a previous result as the HSTATE argument. */ |
303 | void hash_operand (const_tree, inchash::hash &, unsigned flags) |
304 | final override; |
305 | void hash_operand (const_tree, inchash::hash &, unsigned flags, |
306 | operand_access_type access); |
307 | }; |
308 | |
309 | } // ipa_icf_gimple namespace |
310 | |