Line data Source code
1 : /* Interprocedural semantic function equality pass
2 : Copyright (C) 2014-2026 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 2766696 : return_false_with_message_1 (const char *message, const char *filename,
44 : const char *func, unsigned int line)
45 : {
46 2766696 : if (dump_file && (dump_flags & TDF_DETAILS))
47 30 : fprintf (dump_file, " false returned: '%s' in %s at %s:%u\n", message, func,
48 : filename, line);
49 2766696 : 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 758073 : return_with_result (bool result, const char *filename,
64 : const char *func, unsigned int line)
65 : {
66 758073 : if (!result && dump_file && (dump_flags & TDF_DETAILS))
67 5 : fprintf (dump_file, " false returned: '' in %s at %s:%u\n", func,
68 : filename, line);
69 :
70 758073 : 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 38673 : return_different_stmts_1 (gimple *s1, gimple *s2, const char *code,
82 : const char *func, unsigned int line)
83 : {
84 38673 : if (dump_file && (dump_flags & TDF_DETAILS))
85 : {
86 6 : fprintf (dump_file, " different statement for code: %s (%s:%u):\n",
87 : code, func, line);
88 :
89 6 : print_gimple_stmt (dump_file, s1, 3, TDF_DETAILS);
90 6 : print_gimple_stmt (dump_file, s2, 3, TDF_DETAILS);
91 : }
92 :
93 38673 : 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 6601023 : sem_bb (basic_block bb_, unsigned nondbg_stmt_count_, unsigned edge_count_):
107 6601023 : 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 252341 : func_checker ():
126 252341 : m_source_func_decl (NULL_TREE), m_target_func_decl (NULL_TREE),
127 252341 : m_ignored_source_nodes (NULL), m_ignored_target_nodes (NULL),
128 252341 : m_ignore_labels (false), m_tbaa (true),
129 252341 : m_total_scalarization_limit_known_p (false)
130 : {
131 252341 : m_source_ssa_names.create (0);
132 252341 : m_target_ssa_names.create (0);
133 252341 : }
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
|
