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