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