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