1/* Interprocedural Identical Code Folding 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
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along 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
52namespace 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
61func_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 : m_source_func_decl (source_func_decl), m_target_func_decl (target_func_decl),
66 m_ignored_source_nodes (ignored_source_nodes),
67 m_ignored_target_nodes (ignored_target_nodes),
68 m_ignore_labels (ignore_labels), m_tbaa (tbaa),
69 m_total_scalarization_limit_known_p (false)
70{
71 function *source_func = DECL_STRUCT_FUNCTION (source_func_decl);
72 function *target_func = DECL_STRUCT_FUNCTION (target_func_decl);
73
74 unsigned ssa_source = SSANAMES (source_func)->length ();
75 unsigned ssa_target = SSANAMES (target_func)->length ();
76
77 m_source_ssa_names.create (nelems: ssa_source);
78 m_target_ssa_names.create (nelems: ssa_target);
79
80 for (unsigned i = 0; i < ssa_source; i++)
81 m_source_ssa_names.safe_push (obj: -1);
82
83 for (unsigned i = 0; i < ssa_target; i++)
84 m_target_ssa_names.safe_push (obj: -1);
85}
86
87/* Memory release routine. */
88
89func_checker::~func_checker ()
90{
91 m_source_ssa_names.release();
92 m_target_ssa_names.release();
93}
94
95/* Verifies that trees T1 and T2 are equivalent from perspective of ICF. */
96
97bool
98func_checker::compare_ssa_name (const_tree t1, const_tree t2)
99{
100 gcc_assert (TREE_CODE (t1) == SSA_NAME);
101 gcc_assert (TREE_CODE (t2) == SSA_NAME);
102
103 unsigned i1 = SSA_NAME_VERSION (t1);
104 unsigned i2 = SSA_NAME_VERSION (t2);
105
106 if (SSA_NAME_IS_DEFAULT_DEF (t1) != SSA_NAME_IS_DEFAULT_DEF (t2))
107 return false;
108
109 if (m_source_ssa_names[i1] == -1)
110 m_source_ssa_names[i1] = i2;
111 else if (m_source_ssa_names[i1] != (int) i2)
112 return false;
113
114 if(m_target_ssa_names[i2] == -1)
115 m_target_ssa_names[i2] = i1;
116 else if (m_target_ssa_names[i2] != (int) i1)
117 return false;
118
119 if (SSA_NAME_IS_DEFAULT_DEF (t1))
120 {
121 tree b1 = SSA_NAME_VAR (t1);
122 tree b2 = SSA_NAME_VAR (t2);
123
124 return compare_operand (t1: b1, t2: b2, type: OP_NORMAL);
125 }
126
127 return true;
128}
129
130/* Verification function for edges E1 and E2. */
131
132bool
133func_checker::compare_edge (edge e1, edge e2)
134{
135 if (e1->flags != e2->flags)
136 return false;
137
138 bool existed_p;
139
140 edge &slot = m_edge_map.get_or_insert (k: e1, existed: &existed_p);
141 if (existed_p)
142 return return_with_debug (slot == e2);
143 else
144 slot = e2;
145
146 /* TODO: filter edge probabilities for profile feedback match. */
147
148 return true;
149}
150
151/* Verification function for declaration trees T1 and T2 that
152 come from functions FUNC1 and FUNC2. */
153
154bool
155func_checker::compare_decl (const_tree t1, const_tree t2)
156{
157 if (!auto_var_in_fn_p (t1, m_source_func_decl)
158 || !auto_var_in_fn_p (t2, m_target_func_decl))
159 return return_with_debug (t1 == t2);
160
161 tree_code t = TREE_CODE (t1);
162 if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL)
163 && DECL_BY_REFERENCE (t1) != DECL_BY_REFERENCE (t2))
164 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 convetions). */
170 if (t != VAR_DECL)
171 {
172 if (!compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
173 return return_false ();
174 }
175 else
176 {
177 if (!operand_equal_p (DECL_SIZE (t1), DECL_SIZE (t2),
178 flags: OEP_MATCH_SIDE_EFFECTS))
179 return return_false_with_msg ("DECL_SIZEs are different");
180 }
181
182 bool existed_p;
183 const_tree &slot = m_decl_map.get_or_insert (k: t1, existed: &existed_p);
184 if (existed_p)
185 return return_with_debug (slot == t2);
186 else
187 slot = t2;
188
189 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
196bool
197func_checker::compatible_polymorphic_types_p (tree t1, tree t2,
198 bool compare_ptr)
199{
200 gcc_assert (TREE_CODE (t1) != FUNCTION_TYPE && TREE_CODE (t1) != METHOD_TYPE);
201
202 /* Pointer types generally give no information. */
203 if (POINTER_TYPE_P (t1))
204 {
205 if (!compare_ptr)
206 return true;
207 return func_checker::compatible_polymorphic_types_p (TREE_TYPE (t1),
208 TREE_TYPE (t2),
209 compare_ptr: false);
210 }
211
212 /* If types contain a polymorphic types, match them. */
213 bool c1 = contains_polymorphic_type_p (t1);
214 bool c2 = contains_polymorphic_type_p (t2);
215 if (!c1 && !c2)
216 return true;
217 if (!c1 || !c2)
218 return return_false_with_msg ("one type is not polymorphic");
219 if (!types_must_be_same_for_odr (t1, t2))
220 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. */
225bool
226func_checker::compatible_types_p (tree t1, tree t2)
227{
228 if (TREE_CODE (t1) != TREE_CODE (t2))
229 return return_false_with_msg ("different tree types");
230
231 if (TYPE_RESTRICT (t1) != TYPE_RESTRICT (t2))
232 return return_false_with_msg ("restrict flags are different");
233
234 if (!types_compatible_p (type1: t1, type2: t2))
235 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 acces type is OP_NORMAL. */
242
243void
244func_checker::hash_operand (const_tree arg, inchash::hash &hstate,
245 unsigned int flags)
246{
247 if (arg == NULL_TREE)
248 {
249 hstate.merge_hash (other: 0);
250 return;
251 }
252
253 switch (TREE_CODE (arg))
254 {
255 case PARM_DECL:
256 {
257 unsigned int index = 0;
258 if (DECL_CONTEXT (arg))
259 for (tree p = DECL_ARGUMENTS (DECL_CONTEXT (arg));
260 p && index < 32; p = DECL_CHAIN (p), index++)
261 if (p == arg)
262 break;
263 hstate.add_int (v: PARM_DECL);
264 hstate.add_int (v: index);
265 }
266 return;
267 case FUNCTION_DECL:
268 case VAR_DECL:
269 case LABEL_DECL:
270 case RESULT_DECL:
271 case CONST_DECL:
272 hstate.add_int (TREE_CODE (arg));
273 return;
274 case SSA_NAME:
275 hstate.add_int (v: SSA_NAME);
276 if (SSA_NAME_IS_DEFAULT_DEF (arg))
277 hash_operand (SSA_NAME_VAR (arg), hstate, flags);
278 return;
279 case FIELD_DECL:
280 inchash::add_expr (DECL_FIELD_OFFSET (arg), hstate, flags);
281 inchash::add_expr (DECL_FIELD_BIT_OFFSET (arg), hstate, flags);
282 return;
283 default:
284 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 if (TREE_CLOBBER_P (arg))
290 {
291 hstate.add_int (v: 0xc10bbe5);
292 return;
293 }
294 gcc_assert (!DECL_P (arg));
295 gcc_assert (!TYPE_P (arg));
296
297 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
303void
304func_checker::hash_operand (const_tree arg, inchash::hash &hstate,
305 unsigned int flags, operand_access_type access)
306{
307 if (access == OP_MEMORY)
308 {
309 ao_ref ref;
310 ao_ref_init (&ref, const_cast <tree> (arg));
311 return hash_ao_ref (ref: &ref, lto_streaming_safe: lto_streaming_expected_p (), tbaa: m_tbaa, hstate);
312 }
313 else
314 return hash_operand (arg, hstate, flags);
315}
316
317bool
318func_checker::operand_equal_p (const_tree t1, const_tree t2,
319 unsigned int flags)
320{
321 bool r;
322 if (verify_hash_value (arg0: t1, arg1: t2, flags, ret: &r))
323 return r;
324
325 if (t1 == t2)
326 return true;
327 else if (!t1 || !t2)
328 return false;
329
330 if (TREE_CODE (t1) != TREE_CODE (t2))
331 return return_false ();
332
333 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 case VAR_DECL:
340 return return_with_debug (compare_variable_decl (t1, t2));
341 case LABEL_DECL:
342 {
343 int *bb1 = m_label_bb_map.get (k: t1);
344 int *bb2 = m_label_bb_map.get (k: t2);
345 /* Labels can point to another function (non-local GOTOs). */
346 return return_with_debug (bb1 != NULL && bb2 != NULL && *bb1 == *bb2);
347 }
348
349 case PARM_DECL:
350 case RESULT_DECL:
351 case CONST_DECL:
352 return compare_decl (t1, t2);
353 case SSA_NAME:
354 return compare_ssa_name (t1, t2);
355 default:
356 break;
357 }
358 /* In gimple all clobbers can be considered equal. We match the left hand
359 memory accesses. */
360 if (TREE_CLOBBER_P (t1) || TREE_CLOBBER_P (t2))
361 return TREE_CLOBBER_P (t1) == TREE_CLOBBER_P (t2);
362
363 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
369bool
370func_checker::safe_for_total_scalarization_p (tree t1, tree t2)
371{
372 tree type1 = TREE_TYPE (t1);
373 tree type2 = TREE_TYPE (t2);
374
375 if (!AGGREGATE_TYPE_P (type1)
376 || !AGGREGATE_TYPE_P (type2)
377 || !tree_fits_uhwi_p (TYPE_SIZE (type1))
378 || !tree_fits_uhwi_p (TYPE_SIZE (type2)))
379 return true;
380
381 if (!m_total_scalarization_limit_known_p)
382 {
383 push_cfun (DECL_STRUCT_FUNCTION (m_target_func_decl));
384 m_total_scalarization_limit = sra_get_max_scalarization_size ();
385 pop_cfun ();
386 m_total_scalarization_limit_known_p = true;
387 }
388
389 unsigned HOST_WIDE_INT sz = tree_to_uhwi (TYPE_SIZE (type1));
390 gcc_assert (sz == tree_to_uhwi (TYPE_SIZE (type2)));
391 if (sz > m_total_scalarization_limit)
392 return true;
393 return sra_total_scalarization_would_copy_same_data_p (t1: type1, t2: 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
401bool
402func_checker::compare_operand (tree t1, tree t2, operand_access_type access)
403{
404 if (!t1 && !t2)
405 return true;
406 else if (!t1 || !t2)
407 return false;
408 if (access == OP_MEMORY)
409 {
410 ao_ref ref1, ref2;
411 ao_ref_init (&ref1, const_cast <tree> (t1));
412 ao_ref_init (&ref2, const_cast <tree> (t2));
413 int flags = compare_ao_refs (ref1: &ref1, ref2: &ref2,
414 lto_streaming_safe: lto_streaming_expected_p (), tbaa: m_tbaa);
415
416 if (!flags)
417 {
418 if (!safe_for_total_scalarization_p (t1, t2))
419 return return_false_with_msg
420 ("total scalarization may not be equivalent");
421 return true;
422 }
423 if (flags & SEMANTICS)
424 return return_false_with_msg
425 ("compare_ao_refs failed (semantic difference)");
426 if (flags & BASE_ALIAS_SET)
427 return return_false_with_msg
428 ("compare_ao_refs failed (base alias set difference)");
429 if (flags & REF_ALIAS_SET)
430 return return_false_with_msg
431 ("compare_ao_refs failed (ref alias set difference)");
432 if (flags & ACCESS_PATH)
433 return return_false_with_msg
434 ("compare_ao_refs failed (access path difference)");
435 if (flags & DEPENDENCE_CLIQUE)
436 return return_false_with_msg
437 ("compare_ao_refs failed (dependence clique difference)");
438 gcc_unreachable ();
439 }
440 else
441 {
442 if (operand_equal_p (t1, t2, flags: OEP_MATCH_SIDE_EFFECTS))
443 return true;
444 return return_false_with_msg
445 ("operand_equal_p failed");
446 }
447}
448
449bool
450func_checker::compare_asm_inputs_outputs (tree t1, tree t2,
451 operand_access_type_map *map)
452{
453 gcc_assert (TREE_CODE (t1) == TREE_LIST);
454 gcc_assert (TREE_CODE (t2) == TREE_LIST);
455
456 for (; t1; t1 = TREE_CHAIN (t1))
457 {
458 if (!t2)
459 return false;
460
461 if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2),
462 access: get_operand_access_type (map, t1)))
463 return return_false ();
464
465 tree p1 = TREE_PURPOSE (t1);
466 tree p2 = TREE_PURPOSE (t2);
467
468 gcc_assert (TREE_CODE (p1) == TREE_LIST);
469 gcc_assert (TREE_CODE (p2) == TREE_LIST);
470
471 if (strcmp (TREE_STRING_POINTER (TREE_VALUE (p1)),
472 TREE_STRING_POINTER (TREE_VALUE (p2))) != 0)
473 return return_false ();
474
475 t2 = TREE_CHAIN (t2);
476 }
477
478 if (t2)
479 return return_false ();
480
481 return true;
482}
483
484/* Verifies that trees T1 and T2 do correspond. */
485
486bool
487func_checker::compare_variable_decl (const_tree t1, const_tree t2)
488{
489 bool ret = false;
490
491 if (t1 == t2)
492 return true;
493
494 if (DECL_ALIGN (t1) != DECL_ALIGN (t2))
495 return return_false_with_msg ("alignments are different");
496
497 if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2))
498 return return_false_with_msg ("DECL_HARD_REGISTER are different");
499
500 if (DECL_HARD_REGISTER (t1)
501 && DECL_ASSEMBLER_NAME_RAW (t1) != DECL_ASSEMBLER_NAME_RAW (t2))
502 return return_false_with_msg ("HARD REGISTERS are different");
503
504 /* Symbol table variables are known to match before we start comparing
505 bodies. */
506 if (decl_in_symtab_p (decl: t1))
507 return decl_in_symtab_p (decl: t2);
508 ret = compare_decl (t1, t2);
509
510 return return_with_debug (ret);
511}
512
513/* Compare loop information for basic blocks BB1 and BB2. */
514
515bool
516func_checker::compare_loops (basic_block bb1, basic_block bb2)
517{
518 if ((bb1->loop_father == NULL) != (bb2->loop_father == NULL))
519 return return_false ();
520
521 class loop *l1 = bb1->loop_father;
522 class loop *l2 = bb2->loop_father;
523 if (l1 == NULL)
524 return true;
525
526 if ((bb1 == l1->header) != (bb2 == l2->header))
527 return return_false_with_msg ("header");
528 if ((bb1 == l1->latch) != (bb2 == l2->latch))
529 return return_false_with_msg ("latch");
530 if (l1->simdlen != l2->simdlen)
531 return return_false_with_msg ("simdlen");
532 if (l1->safelen != l2->safelen)
533 return return_false_with_msg ("safelen");
534 if (l1->can_be_parallel != l2->can_be_parallel)
535 return return_false_with_msg ("can_be_parallel");
536 if (l1->dont_vectorize != l2->dont_vectorize)
537 return return_false_with_msg ("dont_vectorize");
538 if (l1->force_vectorize != l2->force_vectorize)
539 return return_false_with_msg ("force_vectorize");
540 if (l1->finite_p != l2->finite_p)
541 return return_false_with_msg ("finite_p");
542 if (l1->unroll != l2->unroll)
543 return return_false_with_msg ("unroll");
544 if (!compare_variable_decl (t1: l1->simduid, t2: l2->simduid))
545 return return_false_with_msg ("simduid");
546
547 return true;
548}
549
550/* Function visits all gimple labels and creates corresponding
551 mapping between basic blocks and labels. */
552
553void
554func_checker::parse_labels (sem_bb *bb)
555{
556 for (gimple_stmt_iterator gsi = gsi_start_bb (bb: bb->bb); !gsi_end_p (i: gsi);
557 gsi_next (i: &gsi))
558 {
559 gimple *stmt = gsi_stmt (i: gsi);
560
561 if (glabel *label_stmt = dyn_cast <glabel *> (p: stmt))
562 {
563 const_tree t = gimple_label_label (gs: label_stmt);
564 gcc_assert (TREE_CODE (t) == LABEL_DECL);
565
566 m_label_bb_map.put (k: t, v: bb->bb->index);
567 }
568 }
569}
570
571/* Basic block equivalence comparison function that returns true if
572 basic blocks BB1 and BB2 (from functions FUNC1 and FUNC2) correspond.
573
574 In general, a collection of equivalence dictionaries is built for types
575 like SSA names, declarations (VAR_DECL, PARM_DECL, ..). This infrastructure
576 is utilized by every statement-by-statement comparison function. */
577
578bool
579func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
580{
581 gimple_stmt_iterator gsi1, gsi2;
582 gimple *s1, *s2;
583
584 gsi1 = gsi_start_nondebug_bb (bb: bb1->bb);
585 gsi2 = gsi_start_nondebug_bb (bb: bb2->bb);
586
587 while (!gsi_end_p (i: gsi1))
588 {
589 if (gsi_end_p (i: gsi2))
590 return return_false ();
591
592 s1 = gsi_stmt (i: gsi1);
593 s2 = gsi_stmt (i: gsi2);
594
595 int eh1 = lookup_stmt_eh_lp_fn
596 (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
597 int eh2 = lookup_stmt_eh_lp_fn
598 (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
599
600 if (eh1 != eh2)
601 return return_false_with_msg ("EH regions are different");
602
603 if (gimple_code (g: s1) != gimple_code (g: s2))
604 return return_false_with_msg ("gimple codes are different");
605
606 switch (gimple_code (g: s1))
607 {
608 case GIMPLE_CALL:
609 if (!compare_gimple_call (s1: as_a <gcall *> (p: s1),
610 s2: as_a <gcall *> (p: s2)))
611 return return_different_stmts (s1, s2, "GIMPLE_CALL");
612 break;
613 case GIMPLE_ASSIGN:
614 if (!compare_gimple_assign (s1, s2))
615 return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
616 break;
617 case GIMPLE_COND:
618 if (!compare_gimple_cond (s1, s2))
619 return return_different_stmts (s1, s2, "GIMPLE_COND");
620 break;
621 case GIMPLE_SWITCH:
622 if (!compare_gimple_switch (s1: as_a <gswitch *> (p: s1),
623 s2: as_a <gswitch *> (p: s2)))
624 return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
625 break;
626 case GIMPLE_DEBUG:
627 break;
628 case GIMPLE_EH_DISPATCH:
629 if (gimple_eh_dispatch_region (eh_dispatch_stmt: as_a <geh_dispatch *> (p: s1))
630 != gimple_eh_dispatch_region (eh_dispatch_stmt: as_a <geh_dispatch *> (p: s2)))
631 return return_different_stmts (s1, s2, "GIMPLE_EH_DISPATCH");
632 break;
633 case GIMPLE_RESX:
634 if (!compare_gimple_resx (s1: as_a <gresx *> (p: s1),
635 s2: as_a <gresx *> (p: s2)))
636 return return_different_stmts (s1, s2, "GIMPLE_RESX");
637 break;
638 case GIMPLE_LABEL:
639 if (!compare_gimple_label (s1: as_a <glabel *> (p: s1),
640 s2: as_a <glabel *> (p: s2)))
641 return return_different_stmts (s1, s2, "GIMPLE_LABEL");
642 break;
643 case GIMPLE_RETURN:
644 if (!compare_gimple_return (s1: as_a <greturn *> (p: s1),
645 s2: as_a <greturn *> (p: s2)))
646 return return_different_stmts (s1, s2, "GIMPLE_RETURN");
647 break;
648 case GIMPLE_GOTO:
649 if (!compare_gimple_goto (s1, s2))
650 return return_different_stmts (s1, s2, "GIMPLE_GOTO");
651 break;
652 case GIMPLE_ASM:
653 if (!compare_gimple_asm (s1: as_a <gasm *> (p: s1),
654 s2: as_a <gasm *> (p: s2)))
655 return return_different_stmts (s1, s2, "GIMPLE_ASM");
656 break;
657 case GIMPLE_PREDICT:
658 case GIMPLE_NOP:
659 break;
660 default:
661 return return_false_with_msg ("Unknown GIMPLE code reached");
662 }
663
664 gsi_next_nondebug (i: &gsi1);
665 gsi_next_nondebug (i: &gsi2);
666 }
667
668 if (!gsi_end_p (i: gsi2))
669 return return_false ();
670
671 if (!compare_loops (bb1: bb1->bb, bb2: bb2->bb))
672 return return_false ();
673
674 return true;
675}
676
677/* Verifies for given GIMPLEs S1 and S2 that
678 call statements are semantically equivalent. */
679
680bool
681func_checker::compare_gimple_call (gcall *s1, gcall *s2)
682{
683 unsigned i;
684 tree t1, t2;
685
686 if (gimple_call_num_args (gs: s1) != gimple_call_num_args (gs: s2))
687 return false;
688
689 operand_access_type_map map (5);
690 classify_operands (stmt: s1, map: &map);
691
692 t1 = gimple_call_fn (gs: s1);
693 t2 = gimple_call_fn (gs: s2);
694 if (!compare_operand (t1, t2, access: get_operand_access_type (map: &map, t1)))
695 return return_false ();
696
697 /* Compare flags. */
698 if (gimple_call_internal_p (gs: s1) != gimple_call_internal_p (gs: s2)
699 || gimple_call_ctrl_altering_p (gs: s1) != gimple_call_ctrl_altering_p (gs: s2)
700 || gimple_call_tail_p (s: s1) != gimple_call_tail_p (s: s2)
701 || gimple_call_return_slot_opt_p (s: s1) != gimple_call_return_slot_opt_p (s: s2)
702 || gimple_call_from_thunk_p (s: s1) != gimple_call_from_thunk_p (s: s2)
703 || gimple_call_from_new_or_delete (s: s1) != gimple_call_from_new_or_delete (s: s2)
704 || gimple_call_va_arg_pack_p (s: s1) != gimple_call_va_arg_pack_p (s: s2)
705 || gimple_call_alloca_for_var_p (s: s1) != gimple_call_alloca_for_var_p (s: s2))
706 return false;
707
708 if (gimple_call_internal_p (gs: s1)
709 && gimple_call_internal_fn (gs: s1) != gimple_call_internal_fn (gs: s2))
710 return false;
711
712 tree fntype1 = gimple_call_fntype (gs: s1);
713 tree fntype2 = gimple_call_fntype (gs: s2);
714
715 /* For direct calls we verify that types are compatible so if we matched
716 callees, callers must match, too. For indirect calls however verify
717 function type. */
718 if (!gimple_call_fndecl (gs: s1))
719 {
720 if ((fntype1 && !fntype2)
721 || (!fntype1 && fntype2)
722 || (fntype1 && !types_compatible_p (type1: fntype1, type2: fntype2)))
723 return return_false_with_msg ("call function types are not compatible");
724 }
725
726 if (fntype1 && fntype2 && comp_type_attributes (fntype1, fntype2) != 1)
727 return return_false_with_msg ("different fntype attributes");
728
729 tree chain1 = gimple_call_chain (gs: s1);
730 tree chain2 = gimple_call_chain (gs: s2);
731 if ((chain1 && !chain2)
732 || (!chain1 && chain2)
733 || !compare_operand (t1: chain1, t2: chain2,
734 access: get_operand_access_type (map: &map, chain1)))
735 return return_false_with_msg ("static call chains are different");
736
737 /* Checking of argument. */
738 for (i = 0; i < gimple_call_num_args (gs: s1); ++i)
739 {
740 t1 = gimple_call_arg (gs: s1, index: i);
741 t2 = gimple_call_arg (gs: s2, index: i);
742
743 if (!compare_operand (t1, t2, access: get_operand_access_type (map: &map, t1)))
744 return return_false_with_msg ("GIMPLE call operands are different");
745 }
746
747 /* Return value checking. */
748 t1 = gimple_get_lhs (s1);
749 t2 = gimple_get_lhs (s2);
750
751 /* For internal calls, lhs types need to be verified, as neither fntype nor
752 callee comparisons can catch that. */
753 if (gimple_call_internal_p (gs: s1)
754 && t1
755 && t2
756 && !compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
757 return return_false_with_msg ("GIMPLE internal call LHS type mismatch");
758
759 if (!gimple_call_internal_p (gs: s1))
760 {
761 cgraph_edge *e1 = cgraph_node::get (decl: m_source_func_decl)->get_edge (call_stmt: s1);
762 cgraph_edge *e2 = cgraph_node::get (decl: m_target_func_decl)->get_edge (call_stmt: s2);
763 class ipa_edge_args *args1 = ipa_edge_args_sum->get (edge: e1);
764 class ipa_edge_args *args2 = ipa_edge_args_sum->get (edge: e2);
765 if ((args1 != nullptr) != (args2 != nullptr))
766 return return_false_with_msg ("ipa_edge_args mismatch");
767 if (args1)
768 {
769 int n1 = ipa_get_cs_argument_count (args: args1);
770 int n2 = ipa_get_cs_argument_count (args: args2);
771 if (n1 != n2)
772 return return_false_with_msg ("ipa_edge_args nargs mismatch");
773 for (int i = 0; i < n1; i++)
774 {
775 struct ipa_jump_func *jf1 = ipa_get_ith_jump_func (args: args1, i);
776 struct ipa_jump_func *jf2 = ipa_get_ith_jump_func (args: args2, i);
777 if (((jf1 != nullptr) != (jf2 != nullptr))
778 || (jf1 && !ipa_jump_functions_equivalent_p (jf1, jf2)))
779 return return_false_with_msg ("jump function mismatch");
780 }
781 }
782 }
783
784 return compare_operand (t1, t2, access: get_operand_access_type (map: &map, t1));
785}
786
787
788/* Verifies for given GIMPLEs S1 and S2 that
789 assignment statements are semantically equivalent. */
790
791bool
792func_checker::compare_gimple_assign (gimple *s1, gimple *s2)
793{
794 tree arg1, arg2;
795 tree_code code1, code2;
796 unsigned i;
797
798 code1 = gimple_assign_rhs_code (gs: s1);
799 code2 = gimple_assign_rhs_code (gs: s2);
800
801 if (code1 != code2)
802 return false;
803
804 operand_access_type_map map (5);
805 classify_operands (stmt: s1, map: &map);
806
807 for (i = 0; i < gimple_num_ops (gs: s1); i++)
808 {
809 arg1 = gimple_op (gs: s1, i);
810 arg2 = gimple_op (gs: s2, i);
811
812 /* Compare types for LHS. */
813 if (i == 0 && !gimple_store_p (gs: s1))
814 {
815 if (!compatible_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
816 return return_false_with_msg ("GIMPLE LHS type mismatch");
817 }
818
819 if (!compare_operand (t1: arg1, t2: arg2, access: get_operand_access_type (map: &map, arg1)))
820 return return_false_with_msg ("GIMPLE assignment operands "
821 "are different");
822 }
823
824
825 return true;
826}
827
828/* Verifies for given GIMPLEs S1 and S2 that
829 condition statements are semantically equivalent. */
830
831bool
832func_checker::compare_gimple_cond (gimple *s1, gimple *s2)
833{
834 tree t1, t2;
835 tree_code code1, code2;
836
837 code1 = gimple_cond_code (gs: s1);
838 code2 = gimple_cond_code (gs: s2);
839
840 if (code1 != code2)
841 return false;
842
843 t1 = gimple_cond_lhs (gs: s1);
844 t2 = gimple_cond_lhs (gs: s2);
845
846 if (!compare_operand (t1, t2, access: OP_NORMAL))
847 return false;
848
849 t1 = gimple_cond_rhs (gs: s1);
850 t2 = gimple_cond_rhs (gs: s2);
851
852 return compare_operand (t1, t2, access: OP_NORMAL);
853}
854
855/* Verifies for given GIMPLE_LABEL stmts S1 and S2 that
856 label statements are semantically equivalent. */
857
858bool
859func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
860{
861 if (m_ignore_labels)
862 return true;
863
864 tree t1 = gimple_label_label (gs: g1);
865 tree t2 = gimple_label_label (gs: g2);
866
867 if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
868 return return_false_with_msg ("FORCED_LABEL");
869
870 /* As the pass build BB to label mapping, no further check is needed. */
871 return true;
872}
873
874/* Verifies for given GIMPLE_SWITCH stmts S1 and S2 that
875 switch statements are semantically equivalent. */
876
877bool
878func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
879{
880 unsigned lsize1, lsize2, i;
881
882 lsize1 = gimple_switch_num_labels (gs: g1);
883 lsize2 = gimple_switch_num_labels (gs: g2);
884
885 if (lsize1 != lsize2)
886 return false;
887
888 tree t1 = gimple_switch_index (gs: g1);
889 tree t2 = gimple_switch_index (gs: g2);
890
891 if (!compare_operand (t1, t2, access: OP_NORMAL))
892 return false;
893
894 for (i = 0; i < lsize1; i++)
895 {
896 tree label1 = gimple_switch_label (gs: g1, index: i);
897 tree label2 = gimple_switch_label (gs: g2, index: i);
898
899 /* Label LOW and HIGH comparison. */
900 tree low1 = CASE_LOW (label1);
901 tree low2 = CASE_LOW (label2);
902
903 if (!tree_int_cst_equal (low1, low2))
904 return return_false_with_msg ("case low values are different");
905
906 tree high1 = CASE_HIGH (label1);
907 tree high2 = CASE_HIGH (label2);
908
909 if (!tree_int_cst_equal (high1, high2))
910 return return_false_with_msg ("case high values are different");
911
912 if (TREE_CODE (label1) == CASE_LABEL_EXPR
913 && TREE_CODE (label2) == CASE_LABEL_EXPR)
914 {
915 label1 = CASE_LABEL (label1);
916 label2 = CASE_LABEL (label2);
917
918 if (!compare_operand (t1: label1, t2: label2, access: OP_NORMAL))
919 return return_false_with_msg ("switch label_exprs are different");
920 }
921 else if (!tree_int_cst_equal (label1, label2))
922 return return_false_with_msg ("switch labels are different");
923 }
924
925 return true;
926}
927
928/* Verifies for given GIMPLE_RETURN stmts S1 and S2 that
929 return statements are semantically equivalent. */
930
931bool
932func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
933{
934 tree t1, t2;
935
936 t1 = gimple_return_retval (gs: g1);
937 t2 = gimple_return_retval (gs: g2);
938
939 /* Void return type. */
940 if (t1 == NULL && t2 == NULL)
941 return true;
942 else
943 {
944 operand_access_type_map map (3);
945 return compare_operand (t1, t2, access: get_operand_access_type (map: &map, t1));
946 }
947}
948
949/* Verifies for given GIMPLEs S1 and S2 that
950 goto statements are semantically equivalent. */
951
952bool
953func_checker::compare_gimple_goto (gimple *g1, gimple *g2)
954{
955 tree dest1, dest2;
956
957 dest1 = gimple_goto_dest (gs: g1);
958 dest2 = gimple_goto_dest (gs: g2);
959
960 if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
961 return false;
962
963 return compare_operand (t1: dest1, t2: dest2, access: OP_NORMAL);
964}
965
966/* Verifies for given GIMPLE_RESX stmts S1 and S2 that
967 resx statements are semantically equivalent. */
968
969bool
970func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
971{
972 return gimple_resx_region (resx_stmt: g1) == gimple_resx_region (resx_stmt: g2);
973}
974
975/* Verifies for given GIMPLEs S1 and S2 that ASM statements are equivalent.
976 For the beginning, the pass only supports equality for
977 '__asm__ __volatile__ ("", "", "", "memory")'. */
978
979bool
980func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
981{
982 if (gimple_asm_volatile_p (asm_stmt: g1) != gimple_asm_volatile_p (asm_stmt: g2))
983 return false;
984
985 if (gimple_asm_input_p (asm_stmt: g1) != gimple_asm_input_p (asm_stmt: g2))
986 return false;
987
988 if (gimple_asm_inline_p (asm_stmt: g1) != gimple_asm_inline_p (asm_stmt: g2))
989 return false;
990
991 if (gimple_asm_ninputs (asm_stmt: g1) != gimple_asm_ninputs (asm_stmt: g2))
992 return false;
993
994 if (gimple_asm_noutputs (asm_stmt: g1) != gimple_asm_noutputs (asm_stmt: g2))
995 return false;
996
997 /* We do not suppport goto ASM statement comparison. */
998 if (gimple_asm_nlabels (asm_stmt: g1) || gimple_asm_nlabels (asm_stmt: g2))
999 return false;
1000
1001 if (gimple_asm_nclobbers (asm_stmt: g1) != gimple_asm_nclobbers (asm_stmt: g2))
1002 return false;
1003
1004 if (strcmp (s1: gimple_asm_string (asm_stmt: g1), s2: gimple_asm_string (asm_stmt: g2)) != 0)
1005 return return_false_with_msg ("ASM strings are different");
1006
1007 operand_access_type_map map (5);
1008 classify_operands (stmt: g1, map: &map);
1009
1010 for (unsigned i = 0; i < gimple_asm_ninputs (asm_stmt: g1); i++)
1011 {
1012 tree input1 = gimple_asm_input_op (asm_stmt: g1, index: i);
1013 tree input2 = gimple_asm_input_op (asm_stmt: g2, index: i);
1014
1015 if (!compare_asm_inputs_outputs (t1: input1, t2: input2, map: &map))
1016 return return_false_with_msg ("ASM input is different");
1017 }
1018
1019 for (unsigned i = 0; i < gimple_asm_noutputs (asm_stmt: g1); i++)
1020 {
1021 tree output1 = gimple_asm_output_op (asm_stmt: g1, index: i);
1022 tree output2 = gimple_asm_output_op (asm_stmt: g2, index: i);
1023
1024 if (!compare_asm_inputs_outputs (t1: output1, t2: output2, map: &map))
1025 return return_false_with_msg ("ASM output is different");
1026 }
1027
1028 for (unsigned i = 0; i < gimple_asm_nclobbers (asm_stmt: g1); i++)
1029 {
1030 tree clobber1 = gimple_asm_clobber_op (asm_stmt: g1, index: i);
1031 tree clobber2 = gimple_asm_clobber_op (asm_stmt: g2, index: i);
1032
1033 if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
1034 flags: OEP_ONLY_CONST))
1035 return return_false_with_msg ("ASM clobber is different");
1036 }
1037
1038 return true;
1039}
1040
1041/* Helper for func_checker::classify_operands. Record that T is a load. */
1042
1043static bool
1044visit_load_store (gimple *, tree, tree t, void *data)
1045{
1046 func_checker::operand_access_type_map *map =
1047 (func_checker::operand_access_type_map *) data;
1048 map->add (k: t);
1049 return false;
1050}
1051
1052/* Compute hash map determining access types of operands. */
1053
1054void
1055func_checker::classify_operands (const gimple *stmt,
1056 operand_access_type_map *map)
1057{
1058 walk_stmt_load_store_ops (const_cast <gimple *> (stmt),
1059 (void *)map, visit_load_store, visit_load_store);
1060}
1061
1062/* Return access type of a given operand. */
1063
1064func_checker::operand_access_type
1065func_checker::get_operand_access_type (operand_access_type_map *map, tree t)
1066{
1067 if (map->contains (k: t))
1068 return OP_MEMORY;
1069 return OP_NORMAL;
1070}
1071
1072} // ipa_icf_gimple namespace
1073

source code of gcc/ipa-icf-gimple.cc