Line data Source code
1 : /* Interprocedural Identical Code Folding 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 : #include "config.h"
23 : #include "system.h"
24 : #include "coretypes.h"
25 : #include "backend.h"
26 : #include "rtl.h"
27 : #include "tree.h"
28 : #include "gimple.h"
29 : #include "tree-pass.h"
30 : #include "ssa.h"
31 : #include "cgraph.h"
32 : #include "data-streamer.h"
33 : #include "gimple-pretty-print.h"
34 : #include "fold-const.h"
35 : #include "gimple-iterator.h"
36 : #include "ipa-utils.h"
37 : #include "tree-eh.h"
38 : #include "builtins.h"
39 : #include "cfgloop.h"
40 : #include "attribs.h"
41 : #include "gimple-walk.h"
42 : #include "tree-sra.h"
43 :
44 : #include "tree-ssa-alias-compare.h"
45 : #include "alloc-pool.h"
46 : #include "symbol-summary.h"
47 : #include "ipa-icf-gimple.h"
48 : #include "sreal.h"
49 : #include "ipa-cp.h"
50 : #include "ipa-prop.h"
51 :
52 : namespace ipa_icf_gimple {
53 :
54 : /* Initialize internal structures for a given SOURCE_FUNC_DECL and
55 : TARGET_FUNC_DECL. Strict polymorphic comparison is processed if
56 : an option COMPARE_POLYMORPHIC is true. For special cases, one can
57 : set IGNORE_LABELS to skip label comparison.
58 : Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets
59 : of declarations that can be skipped. */
60 :
61 127551 : func_checker::func_checker (tree source_func_decl, tree target_func_decl,
62 : bool ignore_labels, bool tbaa,
63 : hash_set<symtab_node *> *ignored_source_nodes,
64 : hash_set<symtab_node *> *ignored_target_nodes)
65 127551 : : m_source_func_decl (source_func_decl), m_target_func_decl (target_func_decl),
66 127551 : m_ignored_source_nodes (ignored_source_nodes),
67 127551 : m_ignored_target_nodes (ignored_target_nodes),
68 127551 : m_ignore_labels (ignore_labels), m_tbaa (tbaa),
69 127551 : m_total_scalarization_limit_known_p (false)
70 : {
71 127551 : function *source_func = DECL_STRUCT_FUNCTION (source_func_decl);
72 127551 : function *target_func = DECL_STRUCT_FUNCTION (target_func_decl);
73 :
74 127551 : unsigned ssa_source = SSANAMES (source_func)->length ();
75 127551 : unsigned ssa_target = SSANAMES (target_func)->length ();
76 :
77 127551 : m_source_ssa_names.create (ssa_source);
78 127551 : m_target_ssa_names.create (ssa_target);
79 :
80 1245160 : for (unsigned i = 0; i < ssa_source; i++)
81 990058 : m_source_ssa_names.safe_push (-1);
82 :
83 1117222 : for (unsigned i = 0; i < ssa_target; i++)
84 989671 : m_target_ssa_names.safe_push (-1);
85 127551 : }
86 :
87 : /* Memory release routine. */
88 :
89 514585 : func_checker::~func_checker ()
90 : {
91 387034 : m_source_ssa_names.release();
92 387034 : m_target_ssa_names.release();
93 514585 : }
94 :
95 : /* Verifies that trees T1 and T2 are equivalent from perspective of ICF. */
96 :
97 : bool
98 1059028 : func_checker::compare_ssa_name (const_tree t1, const_tree t2)
99 : {
100 1059028 : gcc_assert (TREE_CODE (t1) == SSA_NAME);
101 1059028 : gcc_assert (TREE_CODE (t2) == SSA_NAME);
102 :
103 1059028 : unsigned i1 = SSA_NAME_VERSION (t1);
104 1059028 : unsigned i2 = SSA_NAME_VERSION (t2);
105 :
106 1059028 : if (SSA_NAME_IS_DEFAULT_DEF (t1) != SSA_NAME_IS_DEFAULT_DEF (t2))
107 : return false;
108 :
109 1059028 : if (m_source_ssa_names[i1] == -1)
110 336116 : m_source_ssa_names[i1] = i2;
111 722912 : else if (m_source_ssa_names[i1] != (int) i2)
112 : return false;
113 :
114 1058835 : if(m_target_ssa_names[i2] == -1)
115 336112 : m_target_ssa_names[i2] = i1;
116 722723 : else if (m_target_ssa_names[i2] != (int) i1)
117 : return false;
118 :
119 1058831 : if (SSA_NAME_IS_DEFAULT_DEF (t1))
120 : {
121 214714 : tree b1 = SSA_NAME_VAR (t1);
122 214714 : tree b2 = SSA_NAME_VAR (t2);
123 :
124 214714 : return compare_operand (b1, b2, OP_NORMAL);
125 : }
126 :
127 : return true;
128 : }
129 :
130 : /* Verification function for edges E1 and E2. */
131 :
132 : bool
133 464595 : func_checker::compare_edge (edge e1, edge e2)
134 : {
135 464595 : if (e1->flags != e2->flags)
136 : return false;
137 :
138 464595 : bool existed_p;
139 :
140 464595 : edge &slot = m_edge_map.get_or_insert (e1, &existed_p);
141 464595 : if (existed_p)
142 206339 : return return_with_debug (slot == e2);
143 : else
144 258256 : slot = e2;
145 :
146 : /* TODO: filter edge probabilities for profile feedback match. */
147 :
148 258256 : return true;
149 : }
150 :
151 : /* Verification function for declaration trees T1 and T2 that
152 : come from functions FUNC1 and FUNC2. */
153 :
154 : bool
155 422391 : func_checker::compare_decl (const_tree t1, const_tree t2)
156 : {
157 422391 : if (!auto_var_in_fn_p (t1, m_source_func_decl)
158 422391 : || !auto_var_in_fn_p (t2, m_target_func_decl))
159 8 : return return_with_debug (t1 == t2);
160 :
161 422383 : tree_code t = TREE_CODE (t1);
162 422383 : if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL)
163 422383 : && DECL_BY_REFERENCE (t1) != DECL_BY_REFERENCE (t2))
164 0 : return return_false_with_msg ("DECL_BY_REFERENCE flags are different");
165 :
166 : /* We do not really need to check types of variables, since they are just
167 : blocks of memory and we verify types of the accesses to them.
168 : However do compare types of other kinds of decls
169 : (parm decls and result decl types may affect ABI conventions). */
170 422383 : if (t != VAR_DECL)
171 : {
172 393439 : if (!compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
173 0 : return return_false ();
174 : }
175 : else
176 : {
177 28944 : if (!operand_equal_p (DECL_SIZE (t1), DECL_SIZE (t2),
178 : OEP_MATCH_SIDE_EFFECTS))
179 0 : return return_false_with_msg ("DECL_SIZEs are different");
180 : }
181 :
182 422383 : bool existed_p;
183 422383 : const_tree &slot = m_decl_map.get_or_insert (t1, &existed_p);
184 422383 : if (existed_p)
185 244457 : return return_with_debug (slot == t2);
186 : else
187 177926 : slot = t2;
188 :
189 177926 : return true;
190 : }
191 :
192 : /* Return true if T1 and T2 are same for purposes of ipa-polymorphic-call
193 : analysis. COMPARE_PTR indicates if types of pointers needs to be
194 : considered. */
195 :
196 : bool
197 15188 : func_checker::compatible_polymorphic_types_p (tree t1, tree t2,
198 : bool compare_ptr)
199 : {
200 15188 : gcc_assert (TREE_CODE (t1) != FUNCTION_TYPE && TREE_CODE (t1) != METHOD_TYPE);
201 :
202 : /* Pointer types generally give no information. */
203 15188 : if (POINTER_TYPE_P (t1))
204 : {
205 0 : if (!compare_ptr)
206 : return true;
207 0 : return func_checker::compatible_polymorphic_types_p (TREE_TYPE (t1),
208 0 : TREE_TYPE (t2),
209 0 : false);
210 : }
211 :
212 : /* If types contain a polymorphic types, match them. */
213 15188 : bool c1 = contains_polymorphic_type_p (t1);
214 15188 : bool c2 = contains_polymorphic_type_p (t2);
215 15188 : if (!c1 && !c2)
216 : return true;
217 768 : if (!c1 || !c2)
218 0 : return return_false_with_msg ("one type is not polymorphic");
219 768 : if (!types_must_be_same_for_odr (t1, t2))
220 0 : return return_false_with_msg ("types are not same for ODR");
221 : return true;
222 : }
223 :
224 : /* Return true if types are compatible from perspective of ICF. */
225 : bool
226 4356289 : func_checker::compatible_types_p (tree t1, tree t2)
227 : {
228 4356289 : if (TREE_CODE (t1) != TREE_CODE (t2))
229 132169 : return return_false_with_msg ("different tree types");
230 :
231 4224120 : if (TYPE_RESTRICT (t1) != TYPE_RESTRICT (t2))
232 134 : return return_false_with_msg ("restrict flags are different");
233 :
234 4223986 : if (!types_compatible_p (t1, t2))
235 960695 : return return_false_with_msg ("types are not compatible");
236 :
237 : return true;
238 : }
239 :
240 : /* Add hash of ARG to HSTATE. FLAGS have same meaning
241 : as for operand_equal_p. Works only if operand access type is OP_NORMAL. */
242 :
243 : void
244 134622140 : func_checker::hash_operand (const_tree arg, inchash::hash &hstate,
245 : unsigned int flags)
246 : {
247 139575584 : if (arg == NULL_TREE)
248 : {
249 15917805 : hstate.merge_hash (0);
250 15917805 : return;
251 : }
252 :
253 123657779 : switch (TREE_CODE (arg))
254 : {
255 5523793 : case PARM_DECL:
256 5523793 : {
257 5523793 : unsigned int index = 0;
258 5523793 : if (DECL_CONTEXT (arg))
259 5523793 : for (tree p = DECL_ARGUMENTS (DECL_CONTEXT (arg));
260 11146464 : p && index < 32; p = DECL_CHAIN (p), index++)
261 11137172 : if (p == arg)
262 : break;
263 5523793 : hstate.add_int (PARM_DECL);
264 5523793 : hstate.add_int (index);
265 : }
266 5523793 : return;
267 14787394 : case FUNCTION_DECL:
268 14787394 : case VAR_DECL:
269 14787394 : case LABEL_DECL:
270 14787394 : case RESULT_DECL:
271 14787394 : case CONST_DECL:
272 14787394 : hstate.add_int (TREE_CODE (arg));
273 14787394 : return;
274 33795429 : case SSA_NAME:
275 33795429 : hstate.add_int (SSA_NAME);
276 33795429 : if (SSA_NAME_IS_DEFAULT_DEF (arg))
277 4953444 : hash_operand (SSA_NAME_VAR (arg), hstate, flags);
278 : return;
279 237 : case FIELD_DECL:
280 237 : inchash::add_expr (DECL_FIELD_OFFSET (arg), hstate, flags);
281 237 : inchash::add_expr (DECL_FIELD_BIT_OFFSET (arg), hstate, flags);
282 237 : return;
283 69550926 : default:
284 69550926 : break;
285 : }
286 :
287 : /* In gimple all clobbers can be considered equal: while comparaing two
288 : gimple clobbers we match the left hand memory accesses. */
289 69550926 : if (TREE_CLOBBER_P (arg))
290 : {
291 1230055 : hstate.add_int (0xc10bbe5);
292 1230055 : return;
293 : }
294 68320871 : gcc_assert (!DECL_P (arg));
295 68320871 : gcc_assert (!TYPE_P (arg));
296 :
297 68320871 : return operand_compare::hash_operand (arg, hstate, flags);
298 : }
299 :
300 : /* Add hash of ARG accesses according to ACCESS to HSTATE.
301 : FLAGS have same meaning as for operand_equal_p. */
302 :
303 : void
304 67312549 : func_checker::hash_operand (const_tree arg, inchash::hash &hstate,
305 : unsigned int flags, operand_access_type access)
306 : {
307 67312549 : if (access == OP_MEMORY)
308 : {
309 8447130 : ao_ref ref;
310 8447130 : ao_ref_init (&ref, const_cast <tree> (arg));
311 8447130 : return hash_ao_ref (&ref, lto_streaming_expected_p (), m_tbaa, hstate);
312 : }
313 : else
314 58865419 : return hash_operand (arg, hstate, flags);
315 : }
316 :
317 : bool
318 4020978 : func_checker::operand_equal_p (const_tree t1, const_tree t2,
319 : unsigned int flags)
320 : {
321 4020978 : bool r;
322 4020978 : if (verify_hash_value (t1, t2, flags, &r))
323 1740251 : return r;
324 :
325 2280727 : if (t1 == t2)
326 : return true;
327 1726969 : else if (!t1 || !t2)
328 : return false;
329 :
330 1726969 : if (TREE_CODE (t1) != TREE_CODE (t2))
331 3 : return return_false ();
332 :
333 1726966 : switch (TREE_CODE (t1))
334 : {
335 : case FUNCTION_DECL:
336 : /* All function decls are in the symbol table and known to match
337 : before we start comparing bodies. */
338 : return true;
339 28968 : case VAR_DECL:
340 28968 : return return_with_debug (compare_variable_decl (t1, t2));
341 1276 : case LABEL_DECL:
342 1276 : {
343 1276 : int *bb1 = m_label_bb_map.get (t1);
344 1276 : int *bb2 = m_label_bb_map.get (t2);
345 : /* Labels can point to another function (non-local GOTOs). */
346 1281 : return return_with_debug (bb1 != NULL && bb2 != NULL && *bb1 == *bb2);
347 : }
348 :
349 228035 : case PARM_DECL:
350 228035 : case RESULT_DECL:
351 228035 : case CONST_DECL:
352 228035 : return compare_decl (t1, t2);
353 1059028 : case SSA_NAME:
354 1059028 : return compare_ssa_name (t1, t2);
355 398472 : default:
356 398472 : break;
357 : }
358 : /* In gimple all clobbers can be considered equal. We match the left hand
359 : memory accesses. */
360 398472 : if (TREE_CLOBBER_P (t1) || TREE_CLOBBER_P (t2))
361 4955 : return TREE_CLOBBER_P (t1) == TREE_CLOBBER_P (t2);
362 :
363 393517 : return operand_compare::operand_equal_p (t1, t2, flags);
364 : }
365 :
366 : /* Return true if either T1 and T2 cannot be totally scalarized or if doing
367 : so would result in copying the same memory. Otherwise return false. */
368 :
369 : bool
370 101396 : func_checker::safe_for_total_scalarization_p (tree t1, tree t2)
371 : {
372 101396 : tree type1 = TREE_TYPE (t1);
373 101396 : tree type2 = TREE_TYPE (t2);
374 :
375 101396 : if (!AGGREGATE_TYPE_P (type1)
376 13789 : || !AGGREGATE_TYPE_P (type2)
377 13789 : || !tree_fits_uhwi_p (TYPE_SIZE (type1))
378 115185 : || !tree_fits_uhwi_p (TYPE_SIZE (type2)))
379 : return true;
380 :
381 13789 : if (!m_total_scalarization_limit_known_p)
382 : {
383 3984 : push_cfun (DECL_STRUCT_FUNCTION (m_target_func_decl));
384 3984 : m_total_scalarization_limit = sra_get_max_scalarization_size ();
385 3984 : pop_cfun ();
386 3984 : m_total_scalarization_limit_known_p = true;
387 : }
388 :
389 13789 : unsigned HOST_WIDE_INT sz = tree_to_uhwi (TYPE_SIZE (type1));
390 13789 : gcc_assert (sz == tree_to_uhwi (TYPE_SIZE (type2)));
391 13789 : if (sz > m_total_scalarization_limit)
392 : return true;
393 13647 : return sra_total_scalarization_would_copy_same_data_p (type1, type2);
394 : }
395 :
396 : /* Function responsible for comparison of various operands T1 and T2
397 : which are accessed as ACCESS.
398 : If these components, from functions FUNC1 and FUNC2, are equal, true
399 : is returned. */
400 :
401 : bool
402 2072445 : func_checker::compare_operand (tree t1, tree t2, operand_access_type access)
403 : {
404 2072445 : if (!t1 && !t2)
405 : return true;
406 1709180 : else if (!t1 || !t2)
407 : return false;
408 1709180 : if (access == OP_MEMORY)
409 : {
410 103599 : ao_ref ref1, ref2;
411 103599 : ao_ref_init (&ref1, const_cast <tree> (t1));
412 103599 : ao_ref_init (&ref2, const_cast <tree> (t2));
413 103599 : int flags = compare_ao_refs (&ref1, &ref2,
414 : lto_streaming_expected_p (), m_tbaa);
415 :
416 103599 : if (!flags)
417 : {
418 101396 : if (!safe_for_total_scalarization_p (t1, t2))
419 3 : return return_false_with_msg
420 : ("total scalarization may not be equivalent");
421 : return true;
422 : }
423 2203 : if (flags & SEMANTICS)
424 396 : return return_false_with_msg
425 : ("compare_ao_refs failed (semantic difference)");
426 1807 : if (flags & BASE_ALIAS_SET)
427 22 : return return_false_with_msg
428 : ("compare_ao_refs failed (base alias set difference)");
429 1785 : if (flags & REF_ALIAS_SET)
430 0 : return return_false_with_msg
431 : ("compare_ao_refs failed (ref alias set difference)");
432 1785 : if (flags & ACCESS_PATH)
433 1706 : return return_false_with_msg
434 : ("compare_ao_refs failed (access path difference)");
435 79 : if (flags & DEPENDENCE_CLIQUE)
436 79 : return return_false_with_msg
437 : ("compare_ao_refs failed (dependence clique difference)");
438 0 : gcc_unreachable ();
439 : }
440 : else
441 : {
442 1605581 : if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS
443 : | OEP_ADDRESS_OF_SAME_FIELD))
444 : return true;
445 3058 : return return_false_with_msg
446 : ("operand_equal_p failed");
447 : }
448 : }
449 :
450 : bool
451 915 : func_checker::compare_asm_inputs_outputs (tree t1, tree t2,
452 : operand_access_type_map *map)
453 : {
454 915 : gcc_assert (TREE_CODE (t1) == TREE_LIST);
455 915 : gcc_assert (TREE_CODE (t2) == TREE_LIST);
456 :
457 1801 : for (; t1; t1 = TREE_CHAIN (t1))
458 : {
459 915 : if (!t2)
460 : return false;
461 :
462 915 : if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2),
463 : get_operand_access_type (map, t1))
464 1826 : || !types_compatible_p (TREE_TYPE (TREE_VALUE (t1)),
465 911 : TREE_TYPE (TREE_VALUE (t2))))
466 6 : return return_false ();
467 :
468 909 : tree p1 = TREE_PURPOSE (t1);
469 909 : tree p2 = TREE_PURPOSE (t2);
470 :
471 909 : gcc_assert (TREE_CODE (p1) == TREE_LIST);
472 909 : gcc_assert (TREE_CODE (p2) == TREE_LIST);
473 :
474 909 : if (strcmp (TREE_STRING_POINTER (TREE_VALUE (p1)),
475 909 : TREE_STRING_POINTER (TREE_VALUE (p2))) != 0)
476 23 : return return_false ();
477 :
478 886 : t2 = TREE_CHAIN (t2);
479 : }
480 :
481 886 : if (t2)
482 0 : return return_false ();
483 :
484 : return true;
485 : }
486 :
487 : /* Verifies that trees T1 and T2 do correspond. */
488 :
489 : bool
490 376355 : func_checker::compare_variable_decl (const_tree t1, const_tree t2)
491 : {
492 376355 : bool ret = false;
493 :
494 376355 : if (t1 == t2)
495 : return true;
496 :
497 28976 : if (DECL_ALIGN (t1) != DECL_ALIGN (t2))
498 6 : return return_false_with_msg ("alignments are different");
499 :
500 28970 : if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2))
501 0 : return return_false_with_msg ("DECL_HARD_REGISTER are different");
502 :
503 28970 : if (DECL_HARD_REGISTER (t1)
504 28970 : && DECL_ASSEMBLER_NAME_RAW (t1) != DECL_ASSEMBLER_NAME_RAW (t2))
505 8 : return return_false_with_msg ("HARD REGISTERS are different");
506 :
507 : /* Symbol table variables are known to match before we start comparing
508 : bodies. */
509 28962 : if (decl_in_symtab_p (t1))
510 18 : return decl_in_symtab_p (t2);
511 28944 : ret = compare_decl (t1, t2);
512 :
513 28944 : return return_with_debug (ret);
514 : }
515 :
516 : /* Compare loop information for basic blocks BB1 and BB2. */
517 :
518 : bool
519 347554 : func_checker::compare_loops (basic_block bb1, basic_block bb2)
520 : {
521 347554 : if ((bb1->loop_father == NULL) != (bb2->loop_father == NULL))
522 0 : return return_false ();
523 :
524 347554 : class loop *l1 = bb1->loop_father;
525 347554 : class loop *l2 = bb2->loop_father;
526 347554 : if (l1 == NULL)
527 : return true;
528 :
529 347554 : if ((bb1 == l1->header) != (bb2 == l2->header))
530 0 : return return_false_with_msg ("header");
531 347554 : if ((bb1 == l1->latch) != (bb2 == l2->latch))
532 0 : return return_false_with_msg ("latch");
533 347554 : if (l1->simdlen != l2->simdlen)
534 5 : return return_false_with_msg ("simdlen");
535 347549 : if (l1->safelen != l2->safelen)
536 10 : return return_false_with_msg ("safelen");
537 347539 : if (l1->can_be_parallel != l2->can_be_parallel)
538 0 : return return_false_with_msg ("can_be_parallel");
539 347539 : if (l1->dont_vectorize != l2->dont_vectorize)
540 149 : return return_false_with_msg ("dont_vectorize");
541 347390 : if (l1->force_vectorize != l2->force_vectorize)
542 0 : return return_false_with_msg ("force_vectorize");
543 347390 : if (l1->finite_p != l2->finite_p)
544 3 : return return_false_with_msg ("finite_p");
545 347387 : if (l1->unroll != l2->unroll)
546 0 : return return_false_with_msg ("unroll");
547 347387 : if (!compare_variable_decl (l1->simduid, l2->simduid))
548 0 : return return_false_with_msg ("simduid");
549 347387 : if ((l1->any_upper_bound != l2->any_upper_bound)
550 347387 : || (l1->any_upper_bound
551 5516 : && (l1->nb_iterations_upper_bound != l2->nb_iterations_upper_bound)))
552 8 : return return_false_with_msg ("nb_iterations_upper_bound");
553 :
554 : return true;
555 : }
556 :
557 : /* Function visits all gimple labels and creates corresponding
558 : mapping between basic blocks and labels. */
559 :
560 : void
561 1195068 : func_checker::parse_labels (sem_bb *bb)
562 : {
563 7721576 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi);
564 5331440 : gsi_next (&gsi))
565 : {
566 5331440 : gimple *stmt = gsi_stmt (gsi);
567 :
568 5363434 : if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
569 : {
570 31994 : const_tree t = gimple_label_label (label_stmt);
571 31994 : gcc_assert (TREE_CODE (t) == LABEL_DECL);
572 :
573 31994 : m_label_bb_map.put (t, bb->bb->index);
574 : }
575 : }
576 1195068 : }
577 :
578 : /* Basic block equivalence comparison function that returns true if
579 : basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
580 :
581 : In general, a collection of equivalence dictionaries is built for types
582 : like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure
583 : is utilized by every statement-by-statement comparison function. */
584 :
585 : bool
586 395228 : func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
587 : {
588 395228 : gimple_stmt_iterator gsi1, gsi2;
589 395228 : gimple *s1, *s2;
590 :
591 395228 : gsi1 = gsi_start_nondebug_bb (bb1->bb);
592 395228 : gsi2 = gsi_start_nondebug_bb (bb2->bb);
593 :
594 1134858 : while (!gsi_end_p (gsi1))
595 : {
596 787304 : if (gsi_end_p (gsi2))
597 0 : return return_false ();
598 :
599 787304 : s1 = gsi_stmt (gsi1);
600 787304 : s2 = gsi_stmt (gsi2);
601 :
602 787304 : int eh1 = lookup_stmt_eh_lp_fn
603 787304 : (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
604 787304 : int eh2 = lookup_stmt_eh_lp_fn
605 787304 : (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
606 :
607 787304 : if (eh1 != eh2)
608 0 : return return_false_with_msg ("EH regions are different");
609 :
610 787304 : if (gimple_code (s1) != gimple_code (s2))
611 0 : return return_false_with_msg ("gimple codes are different");
612 :
613 787304 : switch (gimple_code (s1))
614 : {
615 215041 : case GIMPLE_CALL:
616 215041 : if (!compare_gimple_call (as_a <gcall *> (s1),
617 : as_a <gcall *> (s2)))
618 38695 : return return_different_stmts (s1, s2, "GIMPLE_CALL");
619 : break;
620 326789 : case GIMPLE_ASSIGN:
621 326789 : if (!compare_gimple_assign (s1, s2))
622 6383 : return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
623 : break;
624 105428 : case GIMPLE_COND:
625 105428 : if (!compare_gimple_cond (s1, s2))
626 2465 : return return_different_stmts (s1, s2, "GIMPLE_COND");
627 : break;
628 228 : case GIMPLE_SWITCH:
629 228 : if (!compare_gimple_switch (as_a <gswitch *> (s1),
630 228 : as_a <gswitch *> (s2)))
631 2 : return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
632 : break;
633 : case GIMPLE_DEBUG:
634 : break;
635 148 : case GIMPLE_EH_DISPATCH:
636 148 : if (gimple_eh_dispatch_region (as_a <geh_dispatch *> (s1))
637 148 : != gimple_eh_dispatch_region (as_a <geh_dispatch *> (s2)))
638 0 : return return_different_stmts (s1, s2, "GIMPLE_EH_DISPATCH");
639 : break;
640 785 : case GIMPLE_RESX:
641 785 : if (!compare_gimple_resx (as_a <gresx *> (s1),
642 785 : as_a <gresx *> (s2)))
643 0 : return return_different_stmts (s1, s2, "GIMPLE_RESX");
644 : break;
645 3259 : case GIMPLE_LABEL:
646 3259 : if (!compare_gimple_label (as_a <glabel *> (s1),
647 3259 : as_a <glabel *> (s2)))
648 10 : return return_different_stmts (s1, s2, "GIMPLE_LABEL");
649 : break;
650 134648 : case GIMPLE_RETURN:
651 134648 : if (!compare_gimple_return (as_a <greturn *> (s1),
652 134648 : as_a <greturn *> (s2)))
653 60 : return return_different_stmts (s1, s2, "GIMPLE_RETURN");
654 : break;
655 0 : case GIMPLE_GOTO:
656 0 : if (!compare_gimple_goto (s1, s2))
657 0 : return return_different_stmts (s1, s2, "GIMPLE_GOTO");
658 : break;
659 453 : case GIMPLE_ASM:
660 453 : if (!compare_gimple_asm (as_a <gasm *> (s1),
661 453 : as_a <gasm *> (s2)))
662 59 : return return_different_stmts (s1, s2, "GIMPLE_ASM");
663 : break;
664 : case GIMPLE_PREDICT:
665 : case GIMPLE_NOP:
666 : break;
667 0 : default:
668 0 : return return_false_with_msg ("Unknown GIMPLE code reached");
669 : }
670 :
671 739630 : gsi_next_nondebug (&gsi1);
672 739630 : gsi_next_nondebug (&gsi2);
673 : }
674 :
675 347554 : if (!gsi_end_p (gsi2))
676 0 : return return_false ();
677 :
678 347554 : if (!compare_loops (bb1->bb, bb2->bb))
679 175 : return return_false ();
680 :
681 : return true;
682 : }
683 :
684 : /* Verifies for given GIMPLEs S1 and S2 that
685 : call statements are semantically equivalent. */
686 :
687 : bool
688 215041 : func_checker::compare_gimple_call (gcall *s1, gcall *s2)
689 : {
690 215041 : unsigned i;
691 215041 : tree t1, t2;
692 :
693 215041 : if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
694 : return false;
695 :
696 215041 : operand_access_type_map map (5);
697 215041 : classify_operands (s1, &map);
698 :
699 215041 : t1 = gimple_call_fn (s1);
700 215041 : t2 = gimple_call_fn (s2);
701 215041 : if (!compare_operand (t1, t2, get_operand_access_type (&map, t1)))
702 0 : return return_false ();
703 :
704 : /* Compare flags. */
705 215041 : if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2)
706 215041 : || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2)
707 215041 : || gimple_call_tail_p (s1) != gimple_call_tail_p (s2)
708 215041 : || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2)
709 215041 : || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2)
710 215041 : || gimple_call_from_new_or_delete (s1) != gimple_call_from_new_or_delete (s2)
711 215041 : || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2)
712 215041 : || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_p (s2)
713 430082 : || gimple_call_must_tail_p (s1) != gimple_call_must_tail_p (s2))
714 : return false;
715 :
716 215033 : unsigned check_arg_types_from = 0;
717 215033 : if (gimple_call_internal_p (s1))
718 : {
719 86186 : if (gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2))
720 : return false;
721 : }
722 : else
723 : {
724 128847 : tree fntype1 = gimple_call_fntype (s1);
725 128847 : tree fntype2 = gimple_call_fntype (s2);
726 128847 : if (!types_compatible_p (fntype1, fntype2))
727 1089 : return return_false_with_msg ("call function types are not compatible");
728 :
729 127758 : if (comp_type_attributes (fntype1, fntype2) != 1)
730 0 : return return_false_with_msg ("different fntype attributes");
731 :
732 127758 : check_arg_types_from = gimple_call_num_args (s1);
733 127758 : if (!prototype_p (fntype1) || !prototype_p (fntype2))
734 : check_arg_types_from = 0;
735 127375 : else if (stdarg_p (fntype1))
736 : {
737 1067 : check_arg_types_from = list_length (TYPE_ARG_TYPES (fntype1));
738 1067 : if (stdarg_p (fntype2))
739 : {
740 1067 : unsigned n = list_length (TYPE_ARG_TYPES (fntype2));
741 1067 : check_arg_types_from = MIN (check_arg_types_from, n);
742 : }
743 : }
744 126308 : else if (stdarg_p (fntype2))
745 0 : check_arg_types_from = list_length (TYPE_ARG_TYPES (fntype2));
746 : }
747 :
748 186036 : tree chain1 = gimple_call_chain (s1);
749 186036 : tree chain2 = gimple_call_chain (s2);
750 186036 : if ((chain1 && !chain2)
751 186036 : || (!chain1 && chain2)
752 186036 : || !compare_operand (chain1, chain2,
753 : get_operand_access_type (&map, chain1)))
754 0 : return return_false_with_msg ("static call chains are different");
755 :
756 : /* Checking of argument. */
757 412957 : for (i = 0; i < gimple_call_num_args (s1); ++i)
758 : {
759 227919 : t1 = gimple_call_arg (s1, i);
760 227919 : t2 = gimple_call_arg (s2, i);
761 :
762 227919 : if (!compare_operand (t1, t2, get_operand_access_type (&map, t1)))
763 161 : return return_false_with_msg ("GIMPLE call operands are different");
764 227758 : if (i >= check_arg_types_from
765 227758 : && !types_compatible_p (TREE_TYPE (t1), TREE_TYPE (t2)))
766 837 : return return_false_with_msg ("GIMPLE call operand types are "
767 : "different");
768 : }
769 :
770 : /* Return value checking. */
771 185038 : t1 = gimple_get_lhs (s1);
772 185038 : t2 = gimple_get_lhs (s2);
773 :
774 : /* For internal calls, lhs types need to be verified, as neither fntype nor
775 : callee comparisons can catch that. */
776 185038 : if (gimple_call_internal_p (s1)
777 57658 : && t1
778 57658 : && t2
779 242551 : && !compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
780 2610 : return return_false_with_msg ("GIMPLE internal call LHS type mismatch");
781 :
782 182428 : if (!gimple_call_internal_p (s1))
783 : {
784 127380 : cgraph_edge *e1 = cgraph_node::get (m_source_func_decl)->get_edge (s1);
785 127380 : cgraph_edge *e2 = cgraph_node::get (m_target_func_decl)->get_edge (s2);
786 127380 : class ipa_edge_args *args1 = ipa_edge_args_sum->get (e1);
787 127380 : class ipa_edge_args *args2 = ipa_edge_args_sum->get (e2);
788 127380 : if ((args1 != nullptr) != (args2 != nullptr))
789 0 : return return_false_with_msg ("ipa_edge_args mismatch");
790 127380 : if (args1)
791 : {
792 80666 : int n1 = ipa_get_cs_argument_count (args1);
793 80666 : int n2 = ipa_get_cs_argument_count (args2);
794 80666 : if (n1 != n2)
795 0 : return return_false_with_msg ("ipa_edge_args nargs mismatch");
796 142057 : for (int i = 0; i < n1; i++)
797 : {
798 67467 : struct ipa_jump_func *jf1 = ipa_get_ith_jump_func (args1, i);
799 67467 : struct ipa_jump_func *jf2 = ipa_get_ith_jump_func (args2, i);
800 67467 : if (((jf1 != nullptr) != (jf2 != nullptr))
801 67467 : || (jf1 && !ipa_jump_functions_equivalent_p (jf1, jf2)))
802 6076 : return return_false_with_msg ("jump function mismatch");
803 : }
804 : }
805 : }
806 :
807 176352 : return compare_operand (t1, t2, get_operand_access_type (&map, t1));
808 215041 : }
809 :
810 :
811 : /* Verifies for given GIMPLEs S1 and S2 that
812 : assignment statements are semantically equivalent. */
813 :
814 : bool
815 326789 : func_checker::compare_gimple_assign (gimple *s1, gimple *s2)
816 : {
817 326789 : tree arg1, arg2;
818 326789 : tree_code code1, code2;
819 326789 : unsigned i;
820 :
821 326789 : code1 = gimple_assign_rhs_code (s1);
822 326789 : code2 = gimple_assign_rhs_code (s2);
823 :
824 326789 : if (code1 != code2)
825 : return false;
826 :
827 326789 : operand_access_type_map map (5);
828 326789 : classify_operands (s1, &map);
829 :
830 1368890 : for (i = 0; i < gimple_num_ops (s1); i++)
831 : {
832 721695 : arg1 = gimple_op (s1, i);
833 721695 : arg2 = gimple_op (s2, i);
834 :
835 : /* Compare types for LHS. */
836 721695 : if (i == 0 && !gimple_store_p (s1))
837 : {
838 282497 : if (!compatible_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
839 1390 : return return_false_with_msg ("GIMPLE LHS type mismatch");
840 : }
841 :
842 720305 : if (!compare_operand (arg1, arg2, get_operand_access_type (&map, arg1)))
843 4993 : return return_false_with_msg ("GIMPLE assignment operands "
844 : "are different");
845 : }
846 :
847 :
848 : return true;
849 326789 : }
850 :
851 : /* Verifies for given GIMPLEs S1 and S2 that
852 : condition statements are semantically equivalent. */
853 :
854 : bool
855 105428 : func_checker::compare_gimple_cond (gimple *s1, gimple *s2)
856 : {
857 105428 : tree t1, t2;
858 105428 : tree_code code1, code2;
859 :
860 105428 : code1 = gimple_cond_code (s1);
861 105428 : code2 = gimple_cond_code (s2);
862 :
863 105428 : if (code1 != code2)
864 : return false;
865 :
866 102970 : t1 = gimple_cond_lhs (s1);
867 102970 : t2 = gimple_cond_lhs (s2);
868 :
869 102970 : if (!compare_operand (t1, t2, OP_NORMAL))
870 : return false;
871 :
872 102963 : t1 = gimple_cond_rhs (s1);
873 102963 : t2 = gimple_cond_rhs (s2);
874 :
875 102963 : return compare_operand (t1, t2, OP_NORMAL);
876 : }
877 :
878 : /* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
879 : label statements are semantically equivalent. */
880 :
881 : bool
882 3259 : func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
883 : {
884 3259 : if (m_ignore_labels)
885 : return true;
886 :
887 3259 : tree t1 = gimple_label_label (g1);
888 3259 : tree t2 = gimple_label_label (g2);
889 :
890 6508 : if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
891 10 : return return_false_with_msg ("FORCED_LABEL");
892 :
893 : /* As the pass build BB to label mapping, no further check is needed. */
894 : return true;
895 : }
896 :
897 : /* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
898 : switch statements are semantically equivalent. */
899 :
900 : bool
901 228 : func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
902 : {
903 228 : unsigned lsize1, lsize2, i;
904 :
905 228 : lsize1 = gimple_switch_num_labels (g1);
906 228 : lsize2 = gimple_switch_num_labels (g2);
907 :
908 228 : if (lsize1 != lsize2)
909 : return false;
910 :
911 227 : tree t1 = gimple_switch_index (g1);
912 227 : tree t2 = gimple_switch_index (g2);
913 :
914 227 : if (!compare_operand (t1, t2, OP_NORMAL))
915 : return false;
916 :
917 1494 : for (i = 0; i < lsize1; i++)
918 : {
919 1268 : tree label1 = gimple_switch_label (g1, i);
920 1268 : tree label2 = gimple_switch_label (g2, i);
921 :
922 : /* Label LOW and HIGH comparison. */
923 1268 : tree low1 = CASE_LOW (label1);
924 1268 : tree low2 = CASE_LOW (label2);
925 :
926 1268 : if (!tree_int_cst_equal (low1, low2))
927 1 : return return_false_with_msg ("case low values are different");
928 :
929 1267 : tree high1 = CASE_HIGH (label1);
930 1267 : tree high2 = CASE_HIGH (label2);
931 :
932 1267 : if (!tree_int_cst_equal (high1, high2))
933 0 : return return_false_with_msg ("case high values are different");
934 :
935 1267 : if (!compare_operand (CASE_LABEL (label1), CASE_LABEL (label2), OP_NORMAL))
936 0 : return return_false_with_msg ("switch label_exprs are different");
937 : }
938 :
939 : return true;
940 : }
941 :
942 : /* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
943 : return statements are semantically equivalent. */
944 :
945 : bool
946 134648 : func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
947 : {
948 134648 : tree t1, t2;
949 :
950 134648 : t1 = gimple_return_retval (g1);
951 134648 : t2 = gimple_return_retval (g2);
952 :
953 : /* Void return type. */
954 134648 : if (t1 == NULL && t2 == NULL)
955 : return true;
956 : else
957 : {
958 74113 : operand_access_type_map map (3);
959 74113 : return compare_operand (t1, t2, get_operand_access_type (&map, t1));
960 74113 : }
961 : }
962 :
963 : /* Verifies for given GIMPLEs S1 and S2 that
964 : goto statements are semantically equivalent. */
965 :
966 : bool
967 0 : func_checker::compare_gimple_goto (gimple *g1, gimple *g2)
968 : {
969 0 : tree dest1, dest2;
970 :
971 0 : dest1 = gimple_goto_dest (g1);
972 0 : dest2 = gimple_goto_dest (g2);
973 :
974 0 : if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
975 : return false;
976 :
977 0 : return compare_operand (dest1, dest2, OP_NORMAL);
978 : }
979 :
980 : /* Verifies for given GIMPLE_RESX stmts S1 and S2 that
981 : resx statements are semantically equivalent. */
982 :
983 : bool
984 785 : func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
985 : {
986 785 : return gimple_resx_region (g1) == gimple_resx_region (g2);
987 : }
988 :
989 : /* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
990 : For the beginning, the pass only supports equality for
991 : '__asm__ __volatile__ ("", "", "", "memory")'. */
992 :
993 : bool
994 453 : func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
995 : {
996 453 : if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
997 : return false;
998 :
999 453 : if (gimple_asm_basic_p (g1) != gimple_asm_basic_p (g2))
1000 : return false;
1001 :
1002 453 : if (gimple_asm_inline_p (g1) != gimple_asm_inline_p (g2))
1003 : return false;
1004 :
1005 453 : if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
1006 : return false;
1007 :
1008 452 : if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
1009 : return false;
1010 :
1011 : /* We do not support goto ASM statement comparison. */
1012 452 : if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
1013 : return false;
1014 :
1015 428 : if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
1016 : return false;
1017 :
1018 428 : if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
1019 5 : return return_false_with_msg ("ASM strings are different");
1020 :
1021 423 : operand_access_type_map map (5);
1022 423 : classify_operands (g1, &map);
1023 :
1024 1232 : for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
1025 : {
1026 413 : tree input1 = gimple_asm_input_op (g1, i);
1027 413 : tree input2 = gimple_asm_input_op (g2, i);
1028 :
1029 413 : if (!compare_asm_inputs_outputs (input1, input2, &map))
1030 27 : return return_false_with_msg ("ASM input is different");
1031 : }
1032 :
1033 896 : for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
1034 : {
1035 502 : tree output1 = gimple_asm_output_op (g1, i);
1036 502 : tree output2 = gimple_asm_output_op (g2, i);
1037 :
1038 502 : if (!compare_asm_inputs_outputs (output1, output2, &map))
1039 2 : return return_false_with_msg ("ASM output is different");
1040 : }
1041 :
1042 468 : for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
1043 : {
1044 74 : tree clobber1 = gimple_asm_clobber_op (g1, i);
1045 74 : tree clobber2 = gimple_asm_clobber_op (g2, i);
1046 :
1047 74 : if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
1048 : OEP_ONLY_CONST))
1049 0 : return return_false_with_msg ("ASM clobber is different");
1050 : }
1051 :
1052 : return true;
1053 423 : }
1054 :
1055 : /* Helper for func_checker::classify_operands. Record that T is a load. */
1056 :
1057 : static bool
1058 8563911 : visit_load_store (gimple *, tree, tree t, void *data)
1059 : {
1060 8563911 : func_checker::operand_access_type_map *map =
1061 : (func_checker::operand_access_type_map *) data;
1062 8563911 : map->add (t);
1063 8563911 : return false;
1064 : }
1065 :
1066 : /* Compute hash map determining access types of operands. */
1067 :
1068 : void
1069 21760941 : func_checker::classify_operands (const gimple *stmt,
1070 : operand_access_type_map *map)
1071 : {
1072 21760941 : walk_stmt_load_store_ops (const_cast <gimple *> (stmt),
1073 : (void *)map, visit_load_store, visit_load_store);
1074 21760941 : }
1075 :
1076 : /* Return access type of a given operand. */
1077 :
1078 : func_checker::operand_access_type
1079 65115806 : func_checker::get_operand_access_type (operand_access_type_map *map, tree t)
1080 : {
1081 65115806 : if (map->contains (t))
1082 8550729 : return OP_MEMORY;
1083 : return OP_NORMAL;
1084 : }
1085 :
1086 : } // ipa_icf_gimple namespace
|
