Branch data Line data Source code
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 : :
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 : 1563527 : return_false_with_message_1 (const char *message, const char *filename,
44 : : const char *func, unsigned int line)
45 : : {
46 : 1563527 : 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 : 1563527 : 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 : 718785 : return_with_result (bool result, const char *filename,
64 : : const char *func, unsigned int line)
65 : : {
66 : 718785 : 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 : 718785 : 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 : 38042 : return_different_stmts_1 (gimple *s1, gimple *s2, const char *code,
82 : : const char *func, unsigned int line)
83 : : {
84 : 38042 : 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 : 38042 : 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 : 6229498 : sem_bb (basic_block bb_, unsigned nondbg_stmt_count_, unsigned edge_count_):
107 : 6229498 : 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 : 246836 : func_checker ():
126 : 246836 : m_source_func_decl (NULL_TREE), m_target_func_decl (NULL_TREE),
127 : 246836 : m_ignored_source_nodes (NULL), m_ignored_target_nodes (NULL),
128 : 246836 : m_ignore_labels (false), m_tbaa (true),
129 : 246836 : m_total_scalarization_limit_known_p (false)
130 : : {
131 : 246836 : m_source_ssa_names.create (0);
132 : 246836 : m_target_ssa_names.create (0);
133 : 246836 : }
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
|
