1 /* Interprocedural semantic function equality pass
2 Copyright (C) 2014-2023 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 (dump_file, " 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 (dump_file, " 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 (dump_file, " 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 {
130 m_source_ssa_names.create (0);
131 m_target_ssa_names.create (0);
132 }
133
134 /* Initialize internal structures for a given SOURCE_FUNC_DECL and
135 TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
136 an option COMPARE_POLYMORPHIC is true. For special cases, one can
137 set IGNORE_LABELS to skip label comparison.
138 Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets
139 of declarations that can be skipped. */
140 func_checker (tree source_func_decl, tree target_func_decl,
141 bool ignore_labels = false,
142 bool tbaa = true,
143 hash_set<symtab_node *> *ignored_source_nodes = NULL,
144 hash_set<symtab_node *> *ignored_target_nodes = NULL);
145
146 /* Memory release routine. */
147 virtual ~func_checker ();
148
149 /* Function visits all gimple labels and creates corresponding
150 mapping between basic blocks and labels. */
151 void parse_labels (sem_bb *bb);
152
153 /* Basic block equivalence comparison function that returns true if
154 basic blocks BB1 and BB2 correspond. */
155 bool compare_bb (sem_bb *bb1, sem_bb *bb2);
156
157 /* Verifies that trees T1 and T2 are equivalent from perspective of ICF. */
158 bool compare_ssa_name (const_tree t1, const_tree t2);
159
160 /* Verification function for edges E1 and E2. */
161 bool compare_edge (edge e1, edge e2);
162
163 /* Verifies for given GIMPLEs S1 and S2 that
164 call statements are semantically equivalent. */
165 bool compare_gimple_call (gcall *s1, gcall *s2);
166
167 /* Verifies for given GIMPLEs S1 and S2 that
168 assignment statements are semantically equivalent. */
169 bool compare_gimple_assign (gimple *s1, gimple *s2);
170
171 /* Verifies for given GIMPLEs S1 and S2 that
172 condition statements are semantically equivalent. */
173 bool compare_gimple_cond (gimple *s1, gimple *s2);
174
175 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
176 label statements are semantically equivalent. */
177 bool compare_gimple_label (const glabel *s1, const glabel *s2);
178
179 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
180 switch statements are semantically equivalent. */
181 bool compare_gimple_switch (const gswitch *s1, const gswitch *s2);
182
183 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
184 return statements are semantically equivalent. */
185 bool compare_gimple_return (const greturn *s1, const greturn *s2);
186
187 /* Verifies for given GIMPLEs S1 and S2 that
188 goto statements are semantically equivalent. */
189 bool compare_gimple_goto (gimple *s1, gimple *s2);
190
191 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
192 resx statements are semantically equivalent. */
193 bool compare_gimple_resx (const gresx *s1, const gresx *s2);
194
195 /* Verifies for given GIMPLE_ASM stmts S1 and S2 that ASM statements
196 are equivalent.
197 For the beginning, the pass only supports equality for
198 '__asm__ __volatile__ ("", "", "", "memory")'. */
199 bool compare_gimple_asm (const gasm *s1, const gasm *s2);
200
201 /* Verification function for declaration trees T1 and T2. */
202 bool compare_decl (const_tree t1, const_tree t2);
203
204 /* Compute hash map MAP that determines loads and stores of STMT. */
205 enum operand_access_type {OP_MEMORY, OP_NORMAL};
206 typedef hash_set<tree> operand_access_type_map;
207
208 /* Function responsible for comparison of various operands T1 and T2.
209 If these components, from functions FUNC1 and FUNC2, are equal, true
210 is returned. */
211 bool compare_operand (tree t1, tree t2, operand_access_type type);
212
213 /* Compares GIMPLE ASM inputs (or outputs) where we iterate tree chain
214 and compare both TREE_PURPOSEs and TREE_VALUEs. */
215 bool compare_asm_inputs_outputs (tree t1, tree t2,
216 operand_access_type_map *map);
217
218 /* Verifies that trees T1 and T2, representing function declarations
219 are equivalent from perspective of ICF. */
220 bool compare_function_decl (tree t1, tree t2);
221
222 /* Verifies that trees T1 and T2 do correspond. */
223 bool compare_variable_decl (const_tree t1, const_tree t2);
224
225 /* Compare loop information for basic blocks BB1 and BB2. */
226 bool compare_loops (basic_block bb1, basic_block bb2);
227
228 /* Return true if types are compatible for polymorphic call analysis.
229 COMPARE_PTR indicates if polymorphic type comparison should be
230 done for pointers, too. */
231 static bool compatible_polymorphic_types_p (tree t1, tree t2,
232 bool compare_ptr);
233
234 /* Return true if types are compatible from perspective of ICF.
235 FIRST_ARGUMENT indicates if the comparison is called for
236 first parameter of a function. */
237 static bool compatible_types_p (tree t1, tree t2);
238
239 /* Compute hash map determining access types of operands. */
240 static void classify_operands (const gimple *stmt,
241 operand_access_type_map *map);
242
243 /* Return access type of a given operand. */
244 static operand_access_type get_operand_access_type
245 (operand_access_type_map *map, tree);
246 private:
247 /* Vector mapping source SSA names to target ones. */
248 vec <int> m_source_ssa_names;
249
250 /* Vector mapping target SSA names to source ones. */
251 vec <int> m_target_ssa_names;
252
253 /* Source TREE function declaration. */
254 tree m_source_func_decl;
255
256 /* Target TREE function declaration. */
257 tree m_target_func_decl;
258
259 /* Source symbol nodes that should be skipped by
260 declaration comparison. */
261 hash_set<symtab_node *> *m_ignored_source_nodes;
262
263 /* Target symbol nodes that should be skipped by
264 declaration comparison. */
265 hash_set<symtab_node *> *m_ignored_target_nodes;
266
267 /* Source to target edge map. */
268 hash_map <edge, edge> m_edge_map;
269
270 /* Source to target declaration map. */
271 hash_map <const_tree, const_tree> m_decl_map;
272
273 /* Label to basic block index mapping. */
274 hash_map <const_tree, int> m_label_bb_map;
275
276 /* Flag if ignore labels in comparison. */
277 bool m_ignore_labels;
278
279 /* Flag if we should compare type based alias analysis info. */
280 bool m_tbaa;
281
282 public:
283 /* Return true if two operands are equal. The flags fields can be used
284 to specify OEP flags described above. */
285 bool operand_equal_p (const_tree, const_tree, unsigned int flags)
286 final override;
287
288 /* Generate a hash value for an expression. This can be used iteratively
289 by passing a previous result as the HSTATE argument. */
290 void hash_operand (const_tree, inchash::hash &, unsigned flags)
291 final override;
292 void hash_operand (const_tree, inchash::hash &, unsigned flags,
293 operand_access_type access);
294 };
295
296 } // ipa_icf_gimple namespace