1 /* Interprocedural semantic function equality pass
2 Copyright (C) 2014-2019 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
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
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
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/>. */
22 /* Gimple identical code folding (class func_checker) is an infastructure
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.
27 To use the infrastructure, create an instanse of func_checker and call
28 a comparsion function based on type of gimple statement. */
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, " ");
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__);
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. */
43 return_false_with_message_1 (const char *message
, const char *filename
,
44 const char *func
, unsigned int line
)
46 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
47 fprintf (dump_file
, " false returned: '%s' in %s at %s:%u\n", message
, func
,
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__)
56 /* Return false and log that false value is returned. */
57 #define return_false() return_false_with_msg ("")
59 /* Logs return value if RESULT is false. FUNC is name of function and LINE
60 is location in the source file. */
63 return_with_result (bool result
, const char *filename
,
64 const char *func
, unsigned int line
)
66 if (!result
&& dump_file
&& (dump_flags
& TDF_DETAILS
))
67 fprintf (dump_file
, " false returned: '' in %s at %s:%u\n", func
,
73 /* Logs return value if RESULT is false. */
74 #define return_with_debug(result) return_with_result \
75 (result, __FILE__, __func__, __LINE__)
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. */
81 return_different_stmts_1 (gimple
*s1
, gimple
*s2
, const char *code
,
82 const char *func
, unsigned int line
)
84 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
86 fprintf (dump_file
, " different statement for code: %s (%s:%u):\n",
89 print_gimple_stmt (dump_file
, s1
, 3, TDF_DETAILS
);
90 print_gimple_stmt (dump_file
, s2
, 3, TDF_DETAILS
);
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__)
100 namespace ipa_icf_gimple
{
102 /* Basic block struct for semantic equality pass. */
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_
) {}
109 /* Basic block the structure belongs to. */
112 /* Number of non-debug statements in the basic block. */
113 unsigned nondbg_stmt_count
;
115 /* Number of edges connected to the block. */
119 /* A class aggregating all connections and semantic equivalents
120 for a given pair of semantic function candidates. */
121 class func_checker
: operand_compare
124 /* Initialize internal structures for a given SOURCE_FUNC_DECL and
125 TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
126 an option COMPARE_POLYMORPHIC is true. For special cases, one can
127 set IGNORE_LABELS to skip label comparison.
128 Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets
129 of declarations that can be skipped. */
130 func_checker (tree source_func_decl
, tree target_func_decl
,
131 bool ignore_labels
= false,
132 hash_set
<symtab_node
*> *ignored_source_nodes
= NULL
,
133 hash_set
<symtab_node
*> *ignored_target_nodes
= NULL
);
135 /* Memory release routine. */
136 virtual ~func_checker ();
138 /* Function visits all gimple labels and creates corresponding
139 mapping between basic blocks and labels. */
140 void parse_labels (sem_bb
*bb
);
142 /* Basic block equivalence comparison function that returns true if
143 basic blocks BB1 and BB2 correspond. */
144 bool compare_bb (sem_bb
*bb1
, sem_bb
*bb2
);
146 /* Verifies that trees T1 and T2 are equivalent from perspective of ICF. */
147 bool compare_ssa_name (const_tree t1
, const_tree t2
);
149 /* Verification function for edges E1 and E2. */
150 bool compare_edge (edge e1
, edge e2
);
152 /* Verifies for given GIMPLEs S1 and S2 that
153 call statements are semantically equivalent. */
154 bool compare_gimple_call (gcall
*s1
, gcall
*s2
);
156 /* Verifies for given GIMPLEs S1 and S2 that
157 assignment statements are semantically equivalent. */
158 bool compare_gimple_assign (gimple
*s1
, gimple
*s2
);
160 /* Verifies for given GIMPLEs S1 and S2 that
161 condition statements are semantically equivalent. */
162 bool compare_gimple_cond (gimple
*s1
, gimple
*s2
);
164 /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
165 label statements are semantically equivalent. */
166 bool compare_gimple_label (const glabel
*s1
, const glabel
*s2
);
168 /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
169 switch statements are semantically equivalent. */
170 bool compare_gimple_switch (const gswitch
*s1
, const gswitch
*s2
);
172 /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
173 return statements are semantically equivalent. */
174 bool compare_gimple_return (const greturn
*s1
, const greturn
*s2
);
176 /* Verifies for given GIMPLEs S1 and S2 that
177 goto statements are semantically equivalent. */
178 bool compare_gimple_goto (gimple
*s1
, gimple
*s2
);
180 /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
181 resx statements are semantically equivalent. */
182 bool compare_gimple_resx (const gresx
*s1
, const gresx
*s2
);
184 /* Verifies for given GIMPLE_ASM stmts S1 and S2 that ASM statements
186 For the beginning, the pass only supports equality for
187 '__asm__ __volatile__ ("", "", "", "memory")'. */
188 bool compare_gimple_asm (const gasm
*s1
, const gasm
*s2
);
190 /* Verification function for declaration trees T1 and T2. */
191 bool compare_decl (const_tree t1
, const_tree t2
);
193 /* Function responsible for comparison of various operands T1 and T2.
194 If these components, from functions FUNC1 and FUNC2, are equal, true
196 bool compare_operand (tree t1
, tree t2
);
198 /* Compares GIMPLE ASM inputs (or outputs) where we iterate tree chain
199 and compare both TREE_PURPOSEs and TREE_VALUEs. */
200 bool compare_asm_inputs_outputs (tree t1
, tree t2
);
202 /* Verifies that trees T1 and T2, representing function declarations
203 are equivalent from perspective of ICF. */
204 bool compare_function_decl (tree t1
, tree t2
);
206 /* Verifies that trees T1 and T2 do correspond. */
207 bool compare_variable_decl (const_tree t1
, const_tree t2
);
209 /* Compare loop information for basic blocks BB1 and BB2. */
210 bool compare_loops (basic_block bb1
, basic_block bb2
);
212 /* Return true if types are compatible for polymorphic call analysis.
213 COMPARE_PTR indicates if polymorphic type comparsion should be
214 done for pointers, too. */
215 static bool compatible_polymorphic_types_p (tree t1
, tree t2
,
218 /* Return true if types are compatible from perspective of ICF.
219 FIRST_ARGUMENT indicates if the comparison is called for
220 first parameter of a function. */
221 static bool compatible_types_p (tree t1
, tree t2
);
225 /* Vector mapping source SSA names to target ones. */
226 vec
<int> m_source_ssa_names
;
228 /* Vector mapping target SSA names to source ones. */
229 vec
<int> m_target_ssa_names
;
231 /* Source TREE function declaration. */
232 tree m_source_func_decl
;
234 /* Target TREE function declaration. */
235 tree m_target_func_decl
;
237 /* Source symbol nodes that should be skipped by
238 declaration comparison. */
239 hash_set
<symtab_node
*> *m_ignored_source_nodes
;
241 /* Target symbol nodes that should be skipped by
242 declaration comparison. */
243 hash_set
<symtab_node
*> *m_ignored_target_nodes
;
245 /* Source to target edge map. */
246 hash_map
<edge
, edge
> m_edge_map
;
248 /* Source to target declaration map. */
249 hash_map
<const_tree
, const_tree
> m_decl_map
;
251 /* Label to basic block index mapping. */
252 hash_map
<const_tree
, int> m_label_bb_map
;
254 /* Flag if ignore labels in comparison. */
255 bool m_ignore_labels
;
257 /* Return true if two operands are equal. The flags fields can be used
258 to specify OEP flags described above. */
259 virtual bool operand_equal_p (const_tree
, const_tree
, unsigned int flags
);
261 /* Generate a hash value for an expression. This can be used iteratively
262 by passing a previous result as the HSTATE argument. */
263 virtual void hash_operand (const_tree
, inchash::hash
&, unsigned flags
);
266 } // ipa_icf_gimple namespace