Branch data Line data Source code
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 : 1547215 : return_false_with_message_1 (const char *message, const char *filename,
44 : : const char *func, unsigned int line)
45 : : {
46 : 1547215 : if (dump_file && (dump_flags & TDF_DETAILS))
47 : 32 : fprintf (dump_file, " false returned: '%s' in %s at %s:%u\n", message, func,
48 : : filename, line);
49 : 1547215 : 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 : 662621 : return_with_result (bool result, const char *filename,
64 : : const char *func, unsigned int line)
65 : : {
66 : 662621 : 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 : 662621 : 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 : 35467 : return_different_stmts_1 (gimple *s1, gimple *s2, const char *code,
82 : : const char *func, unsigned int line)
83 : : {
84 : 35467 : 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 : 35467 : 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 : 5714302 : sem_bb (basic_block bb_, unsigned nondbg_stmt_count_, unsigned edge_count_):
107 : 5714302 : 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 : 241376 : func_checker ():
126 : 241376 : m_source_func_decl (NULL_TREE), m_target_func_decl (NULL_TREE),
127 : 241376 : m_ignored_source_nodes (NULL), m_ignored_target_nodes (NULL),
128 : 241376 : m_ignore_labels (false), m_tbaa (true)
129 : : {
130 : 241376 : m_source_ssa_names.create (0);
131 : 241376 : m_target_ssa_names.create (0);
132 : 241376 : }
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
|