1/* Interprocedural semantic function equality pass
2 Copyright (C) 2014-2025 Free Software Foundation, Inc.
3
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
42inline bool
43return_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
62inline bool
63return_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
80inline bool
81return_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
100namespace ipa_icf_gimple {
101
102/* Basic block struct for semantic equality pass. */
103class sem_bb
104{
105public:
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. */
121class func_checker : ao_compare
122{
123public:
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);
251private:
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
295public:
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

source code of gcc/ipa-icf-gimple.h