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 | |
6 | This file is part of GCC. |
7 | |
8 | GCC is free software; you can redistribute it and/or modify it under |
9 | the terms of the GNU General Public License as published by the Free |
10 | Software Foundation; either version 3, or (at your option) any later |
11 | version. |
12 | |
13 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
14 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |
15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
16 | for more details. |
17 | |
18 | You should have received a copy of the GNU General Public License |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ |
21 | |
22 | #include "config.h" |
23 | #include "system.h" |
24 | #include "coretypes.h" |
25 | #include "backend.h" |
26 | #include "rtl.h" |
27 | #include "tree.h" |
28 | #include "gimple.h" |
29 | #include "tree-pass.h" |
30 | #include "ssa.h" |
31 | #include "cgraph.h" |
32 | #include "data-streamer.h" |
33 | #include "gimple-pretty-print.h" |
34 | #include "fold-const.h" |
35 | #include "gimple-iterator.h" |
36 | #include "ipa-utils.h" |
37 | #include "tree-eh.h" |
38 | #include "builtins.h" |
39 | #include "cfgloop.h" |
40 | #include "attribs.h" |
41 | #include "gimple-walk.h" |
42 | #include "tree-sra.h" |
43 | |
44 | #include "tree-ssa-alias-compare.h" |
45 | #include "alloc-pool.h" |
46 | #include "symbol-summary.h" |
47 | #include "ipa-icf-gimple.h" |
48 | #include "sreal.h" |
49 | #include "ipa-cp.h" |
50 | #include "ipa-prop.h" |
51 | |
52 | namespace ipa_icf_gimple { |
53 | |
54 | /* Initialize internal structures for a given SOURCE_FUNC_DECL and |
55 | TARGET_FUNC_DECL. Strict polymorphic comparison is processed if |
56 | an option COMPARE_POLYMORPHIC is true. For special cases, one can |
57 | set IGNORE_LABELS to skip label comparison. |
58 | Similarly, IGNORE_SOURCE_DECLS and IGNORE_TARGET_DECLS are sets |
59 | of declarations that can be skipped. */ |
60 | |
61 | func_checker::func_checker (tree source_func_decl, tree target_func_decl, |
62 | bool ignore_labels, bool tbaa, |
63 | hash_set<symtab_node *> *ignored_source_nodes, |
64 | hash_set<symtab_node *> *ignored_target_nodes) |
65 | : 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 | |
89 | func_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 | |
97 | bool |
98 | func_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 | |
132 | bool |
133 | func_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 | |
154 | bool |
155 | func_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 | |
196 | bool |
197 | func_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. */ |
225 | bool |
226 | func_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 | |
243 | void |
244 | func_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 | |
303 | void |
304 | func_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 | |
317 | bool |
318 | func_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 | |
369 | bool |
370 | func_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 | |
401 | bool |
402 | func_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 | |
449 | bool |
450 | func_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 | |
486 | bool |
487 | func_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 | |
515 | bool |
516 | func_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 | |
553 | void |
554 | func_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 | |
578 | bool |
579 | func_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 | |
680 | bool |
681 | func_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 | |
791 | bool |
792 | func_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 | |
831 | bool |
832 | func_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 | |
858 | bool |
859 | func_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 | |
877 | bool |
878 | func_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 | |
931 | bool |
932 | func_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 | |
952 | bool |
953 | func_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 | |
969 | bool |
970 | func_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 | |
979 | bool |
980 | func_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 | |
1043 | static bool |
1044 | visit_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 | |
1054 | void |
1055 | func_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 | |
1064 | func_checker::operand_access_type |
1065 | func_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 | |