Branch data Line data Source code
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 : :
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 : 119030 : 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 : 119030 : hash_set<symtab_node *> *ignored_target_nodes)
59 : 119030 : : m_source_func_decl (source_func_decl), m_target_func_decl (target_func_decl),
60 : 119030 : m_ignored_source_nodes (ignored_source_nodes),
61 : 119030 : m_ignored_target_nodes (ignored_target_nodes),
62 : 119030 : m_ignore_labels (ignore_labels), m_tbaa (tbaa)
63 : : {
64 : 119030 : function *source_func = DECL_STRUCT_FUNCTION (source_func_decl);
65 : 119030 : function *target_func = DECL_STRUCT_FUNCTION (target_func_decl);
66 : :
67 : 119030 : unsigned ssa_source = SSANAMES (source_func)->length ();
68 : 119030 : unsigned ssa_target = SSANAMES (target_func)->length ();
69 : :
70 : 119030 : m_source_ssa_names.create (ssa_source);
71 : 119030 : m_target_ssa_names.create (ssa_target);
72 : :
73 : 1008203 : for (unsigned i = 0; i < ssa_source; i++)
74 : 889173 : m_source_ssa_names.safe_push (-1);
75 : :
76 : 1008193 : for (unsigned i = 0; i < ssa_target; i++)
77 : 889163 : m_target_ssa_names.safe_push (-1);
78 : 119030 : }
79 : :
80 : : /* Memory release routine. */
81 : :
82 : 479436 : func_checker::~func_checker ()
83 : : {
84 : 360406 : m_source_ssa_names.release();
85 : 360406 : m_target_ssa_names.release();
86 : 479436 : }
87 : :
88 : : /* Verifies that trees T1 and T2 are equivalent from perspective of ICF. */
89 : :
90 : : bool
91 : 1150147 : func_checker::compare_ssa_name (const_tree t1, const_tree t2)
92 : : {
93 : 1150147 : gcc_assert (TREE_CODE (t1) == SSA_NAME);
94 : 1150147 : gcc_assert (TREE_CODE (t2) == SSA_NAME);
95 : :
96 : 1150147 : unsigned i1 = SSA_NAME_VERSION (t1);
97 : 1150147 : unsigned i2 = SSA_NAME_VERSION (t2);
98 : :
99 : 1150147 : if (SSA_NAME_IS_DEFAULT_DEF (t1) != SSA_NAME_IS_DEFAULT_DEF (t2))
100 : : return false;
101 : :
102 : 1150146 : if (m_source_ssa_names[i1] == -1)
103 : 340418 : m_source_ssa_names[i1] = i2;
104 : 809728 : else if (m_source_ssa_names[i1] != (int) i2)
105 : : return false;
106 : :
107 : 1149980 : if(m_target_ssa_names[i2] == -1)
108 : 340417 : m_target_ssa_names[i2] = i1;
109 : 809563 : else if (m_target_ssa_names[i2] != (int) i1)
110 : : return false;
111 : :
112 : 1149979 : if (SSA_NAME_IS_DEFAULT_DEF (t1))
113 : : {
114 : 245609 : tree b1 = SSA_NAME_VAR (t1);
115 : 245609 : tree b2 = SSA_NAME_VAR (t2);
116 : :
117 : 245609 : return compare_operand (b1, b2, OP_NORMAL);
118 : : }
119 : :
120 : : return true;
121 : : }
122 : :
123 : : /* Verification function for edges E1 and E2. */
124 : :
125 : : bool
126 : 487719 : func_checker::compare_edge (edge e1, edge e2)
127 : : {
128 : 487719 : if (e1->flags != e2->flags)
129 : : return false;
130 : :
131 : 487719 : bool existed_p;
132 : :
133 : 487719 : edge &slot = m_edge_map.get_or_insert (e1, &existed_p);
134 : 487719 : if (existed_p)
135 : 215874 : return return_with_debug (slot == e2);
136 : : else
137 : 271845 : slot = e2;
138 : :
139 : : /* TODO: filter edge probabilities for profile feedback match. */
140 : :
141 : 271845 : 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 : 477446 : func_checker::compare_decl (const_tree t1, const_tree t2)
149 : : {
150 : 477446 : if (!auto_var_in_fn_p (t1, m_source_func_decl)
151 : 477446 : || !auto_var_in_fn_p (t2, m_target_func_decl))
152 : 6 : return return_with_debug (t1 == t2);
153 : :
154 : 477440 : tree_code t = TREE_CODE (t1);
155 : 477440 : if ((t == VAR_DECL || t == PARM_DECL || t == RESULT_DECL)
156 : 477440 : && DECL_BY_REFERENCE (t1) != DECL_BY_REFERENCE (t2))
157 : 0 : 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 : 477440 : if (t != VAR_DECL)
164 : : {
165 : 414204 : if (!compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
166 : 0 : return return_false ();
167 : : }
168 : : else
169 : : {
170 : 63236 : if (!operand_equal_p (DECL_SIZE (t1), DECL_SIZE (t2),
171 : : OEP_MATCH_SIDE_EFFECTS))
172 : 0 : return return_false_with_msg ("DECL_SIZEs are different");
173 : : }
174 : :
175 : 477440 : bool existed_p;
176 : 477440 : const_tree &slot = m_decl_map.get_or_insert (t1, &existed_p);
177 : 477440 : if (existed_p)
178 : 305886 : return return_with_debug (slot == t2);
179 : : else
180 : 171554 : slot = t2;
181 : :
182 : 171554 : 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 : 9781 : func_checker::compatible_polymorphic_types_p (tree t1, tree t2,
191 : : bool compare_ptr)
192 : : {
193 : 9781 : gcc_assert (TREE_CODE (t1) != FUNCTION_TYPE && TREE_CODE (t1) != METHOD_TYPE);
194 : :
195 : : /* Pointer types generally give no information. */
196 : 9781 : if (POINTER_TYPE_P (t1))
197 : : {
198 : 0 : if (!compare_ptr)
199 : : return true;
200 : 0 : return func_checker::compatible_polymorphic_types_p (TREE_TYPE (t1),
201 : 0 : TREE_TYPE (t2),
202 : 0 : false);
203 : : }
204 : :
205 : : /* If types contain a polymorphic types, match them. */
206 : 9781 : bool c1 = contains_polymorphic_type_p (t1);
207 : 9781 : bool c2 = contains_polymorphic_type_p (t2);
208 : 9781 : if (!c1 && !c2)
209 : : return true;
210 : 785 : if (!c1 || !c2)
211 : 0 : return return_false_with_msg ("one type is not polymorphic");
212 : 785 : if (!types_must_be_same_for_odr (t1, t2))
213 : 0 : 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 : 3496194 : func_checker::compatible_types_p (tree t1, tree t2)
220 : : {
221 : 3496194 : if (TREE_CODE (t1) != TREE_CODE (t2))
222 : 62710 : return return_false_with_msg ("different tree types");
223 : :
224 : 3433484 : if (TYPE_RESTRICT (t1) != TYPE_RESTRICT (t2))
225 : 78 : return return_false_with_msg ("restrict flags are different");
226 : :
227 : 3433406 : if (!types_compatible_p (t1, t2))
228 : 495096 : 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 : 115831177 : func_checker::hash_operand (const_tree arg, inchash::hash &hstate,
238 : : unsigned int flags)
239 : : {
240 : 120188198 : if (arg == NULL_TREE)
241 : : {
242 : 13318211 : hstate.merge_hash (0);
243 : 13318211 : return;
244 : : }
245 : :
246 : 106869987 : switch (TREE_CODE (arg))
247 : : {
248 : 4947244 : case PARM_DECL:
249 : 4947244 : {
250 : 4947244 : unsigned int index = 0;
251 : 4947244 : if (DECL_CONTEXT (arg))
252 : 4947244 : for (tree p = DECL_ARGUMENTS (DECL_CONTEXT (arg));
253 : 9899593 : p && index < 32; p = DECL_CHAIN (p), index++)
254 : 9891851 : if (p == arg)
255 : : break;
256 : 4947244 : hstate.add_int (PARM_DECL);
257 : 4947244 : hstate.add_int (index);
258 : : }
259 : 4947244 : return;
260 : 12587221 : case FUNCTION_DECL:
261 : 12587221 : case VAR_DECL:
262 : 12587221 : case LABEL_DECL:
263 : 12587221 : case RESULT_DECL:
264 : 12587221 : case CONST_DECL:
265 : 12587221 : hstate.add_int (TREE_CODE (arg));
266 : 12587221 : return;
267 : 27141463 : case SSA_NAME:
268 : 27141463 : hstate.add_int (SSA_NAME);
269 : 27141463 : if (SSA_NAME_IS_DEFAULT_DEF (arg))
270 : 4357021 : hash_operand (SSA_NAME_VAR (arg), hstate, flags);
271 : : return;
272 : 293 : case FIELD_DECL:
273 : 293 : inchash::add_expr (DECL_FIELD_OFFSET (arg), hstate, flags);
274 : 293 : inchash::add_expr (DECL_FIELD_BIT_OFFSET (arg), hstate, flags);
275 : 293 : return;
276 : 62193766 : default:
277 : 62193766 : 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 : 62193766 : if (TREE_CLOBBER_P (arg))
283 : : {
284 : 989938 : hstate.add_int (0xc10bbe5);
285 : 989938 : return;
286 : : }
287 : 61203828 : gcc_assert (!DECL_P (arg));
288 : 61203828 : gcc_assert (!TYPE_P (arg));
289 : :
290 : 61203828 : 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 : 53185456 : func_checker::hash_operand (const_tree arg, inchash::hash &hstate,
298 : : unsigned int flags, operand_access_type access)
299 : : {
300 : 53185456 : if (access == OP_MEMORY)
301 : : {
302 : 6764726 : ao_ref ref;
303 : 6764726 : ao_ref_init (&ref, const_cast <tree> (arg));
304 : 6764726 : return hash_ao_ref (&ref, lto_streaming_expected_p (), m_tbaa, hstate);
305 : : }
306 : : else
307 : 46420730 : return hash_operand (arg, hstate, flags);
308 : : }
309 : :
310 : : bool
311 : 4502134 : func_checker::operand_equal_p (const_tree t1, const_tree t2,
312 : : unsigned int flags)
313 : : {
314 : 4502134 : bool r;
315 : 4502134 : if (verify_hash_value (t1, t2, flags, &r))
316 : 1981141 : return r;
317 : :
318 : 2520993 : if (t1 == t2)
319 : : return true;
320 : 1916690 : else if (!t1 || !t2)
321 : : return false;
322 : :
323 : 1916690 : if (TREE_CODE (t1) != TREE_CODE (t2))
324 : 266 : return return_false ();
325 : :
326 : 1916424 : 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 : 63265 : case VAR_DECL:
333 : 63265 : return return_with_debug (compare_variable_decl (t1, t2));
334 : 2900 : case LABEL_DECL:
335 : 2900 : {
336 : 2900 : int *bb1 = m_label_bb_map.get (t1);
337 : 2900 : int *bb2 = m_label_bb_map.get (t2);
338 : : /* Labels can point to another function (non-local GOTOs). */
339 : 2905 : return return_with_debug (bb1 != NULL && bb2 != NULL && *bb1 == *bb2);
340 : : }
341 : :
342 : 254428 : case PARM_DECL:
343 : 254428 : case RESULT_DECL:
344 : 254428 : case CONST_DECL:
345 : 254428 : return compare_decl (t1, t2);
346 : 1150147 : case SSA_NAME:
347 : 1150147 : return compare_ssa_name (t1, t2);
348 : 431520 : default:
349 : 431520 : break;
350 : : }
351 : : /* In gimple all clobbers can be considered equal. We match the left hand
352 : : memory accesses. */
353 : 431520 : if (TREE_CLOBBER_P (t1) || TREE_CLOBBER_P (t2))
354 : 19705 : return TREE_CLOBBER_P (t1) == TREE_CLOBBER_P (t2);
355 : :
356 : 411815 : 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 : 2292964 : func_checker::compare_operand (tree t1, tree t2, operand_access_type access)
366 : : {
367 : 2292964 : if (!t1 && !t2)
368 : : return true;
369 : 1901481 : else if (!t1 || !t2)
370 : : return false;
371 : 1901481 : if (access == OP_MEMORY)
372 : : {
373 : 136607 : ao_ref ref1, ref2;
374 : 136607 : ao_ref_init (&ref1, const_cast <tree> (t1));
375 : 136607 : ao_ref_init (&ref2, const_cast <tree> (t2));
376 : 273214 : int flags = compare_ao_refs (&ref1, &ref2,
377 : 136607 : lto_streaming_expected_p (), m_tbaa);
378 : :
379 : 136607 : if (!flags)
380 : : return true;
381 : 527 : if (flags & SEMANTICS)
382 : 285 : return return_false_with_msg
383 : : ("compare_ao_refs failed (semantic difference)");
384 : 242 : if (flags & BASE_ALIAS_SET)
385 : 40 : return return_false_with_msg
386 : : ("compare_ao_refs failed (base alias set difference)");
387 : 202 : if (flags & REF_ALIAS_SET)
388 : 1 : return return_false_with_msg
389 : : ("compare_ao_refs failed (ref alias set difference)");
390 : 201 : if (flags & ACCESS_PATH)
391 : 130 : return return_false_with_msg
392 : : ("compare_ao_refs failed (access path difference)");
393 : 71 : if (flags & DEPENDENCE_CLIQUE)
394 : 71 : return return_false_with_msg
395 : : ("compare_ao_refs failed (dependence clique difference)");
396 : 0 : gcc_unreachable ();
397 : : }
398 : : else
399 : : {
400 : 1764874 : if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
401 : : return true;
402 : 1914 : return return_false_with_msg
403 : : ("operand_equal_p failed");
404 : : }
405 : : }
406 : :
407 : : bool
408 : 926 : func_checker::compare_asm_inputs_outputs (tree t1, tree t2,
409 : : operand_access_type_map *map)
410 : : {
411 : 926 : gcc_assert (TREE_CODE (t1) == TREE_LIST);
412 : 926 : gcc_assert (TREE_CODE (t2) == TREE_LIST);
413 : :
414 : 1824 : for (; t1; t1 = TREE_CHAIN (t1))
415 : : {
416 : 926 : if (!t2)
417 : : return false;
418 : :
419 : 926 : if (!compare_operand (TREE_VALUE (t1), TREE_VALUE (t2),
420 : : get_operand_access_type (map, t1)))
421 : 5 : return return_false ();
422 : :
423 : 921 : tree p1 = TREE_PURPOSE (t1);
424 : 921 : tree p2 = TREE_PURPOSE (t2);
425 : :
426 : 921 : gcc_assert (TREE_CODE (p1) == TREE_LIST);
427 : 921 : gcc_assert (TREE_CODE (p2) == TREE_LIST);
428 : :
429 : 921 : if (strcmp (TREE_STRING_POINTER (TREE_VALUE (p1)),
430 : 921 : TREE_STRING_POINTER (TREE_VALUE (p2))) != 0)
431 : 23 : return return_false ();
432 : :
433 : 898 : t2 = TREE_CHAIN (t2);
434 : : }
435 : :
436 : 898 : if (t2)
437 : 0 : return return_false ();
438 : :
439 : : return true;
440 : : }
441 : :
442 : : /* Verifies that trees T1 and T2 do correspond. */
443 : :
444 : : bool
445 : 427474 : func_checker::compare_variable_decl (const_tree t1, const_tree t2)
446 : : {
447 : 427474 : bool ret = false;
448 : :
449 : 427474 : if (t1 == t2)
450 : : return true;
451 : :
452 : 63273 : if (DECL_ALIGN (t1) != DECL_ALIGN (t2))
453 : 6 : return return_false_with_msg ("alignments are different");
454 : :
455 : 63267 : if (DECL_HARD_REGISTER (t1) != DECL_HARD_REGISTER (t2))
456 : 0 : return return_false_with_msg ("DECL_HARD_REGISTER are different");
457 : :
458 : 63267 : if (DECL_HARD_REGISTER (t1)
459 : 63267 : && DECL_ASSEMBLER_NAME_RAW (t1) != DECL_ASSEMBLER_NAME_RAW (t2))
460 : 9 : 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 : 63258 : if (decl_in_symtab_p (t1))
465 : 22 : return decl_in_symtab_p (t2);
466 : 63236 : ret = compare_decl (t1, t2);
467 : :
468 : 63236 : return return_with_debug (ret);
469 : : }
470 : :
471 : : /* Compare loop information for basic blocks BB1 and BB2. */
472 : :
473 : : bool
474 : 364231 : func_checker::compare_loops (basic_block bb1, basic_block bb2)
475 : : {
476 : 364231 : if ((bb1->loop_father == NULL) != (bb2->loop_father == NULL))
477 : 0 : return return_false ();
478 : :
479 : 364231 : class loop *l1 = bb1->loop_father;
480 : 364231 : class loop *l2 = bb2->loop_father;
481 : 364231 : if (l1 == NULL)
482 : : return true;
483 : :
484 : 364231 : if ((bb1 == l1->header) != (bb2 == l2->header))
485 : 0 : return return_false_with_msg ("header");
486 : 364231 : if ((bb1 == l1->latch) != (bb2 == l2->latch))
487 : 0 : return return_false_with_msg ("latch");
488 : 364231 : if (l1->simdlen != l2->simdlen)
489 : 5 : return return_false_with_msg ("simdlen");
490 : 364226 : if (l1->safelen != l2->safelen)
491 : 11 : return return_false_with_msg ("safelen");
492 : 364215 : if (l1->can_be_parallel != l2->can_be_parallel)
493 : 0 : return return_false_with_msg ("can_be_parallel");
494 : 364215 : if (l1->dont_vectorize != l2->dont_vectorize)
495 : 0 : return return_false_with_msg ("dont_vectorize");
496 : 364215 : if (l1->force_vectorize != l2->force_vectorize)
497 : 0 : return return_false_with_msg ("force_vectorize");
498 : 364215 : if (l1->finite_p != l2->finite_p)
499 : 6 : return return_false_with_msg ("finite_p");
500 : 364209 : if (l1->unroll != l2->unroll)
501 : 0 : return return_false_with_msg ("unroll");
502 : 364209 : if (!compare_variable_decl (l1->simduid, l2->simduid))
503 : 0 : 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 : 1057714 : func_checker::parse_labels (sem_bb *bb)
513 : : {
514 : 5702868 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb->bb); !gsi_end_p (gsi);
515 : 3587440 : gsi_next (&gsi))
516 : : {
517 : 3587440 : gimple *stmt = gsi_stmt (gsi);
518 : :
519 : 3603072 : if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
520 : : {
521 : 15632 : const_tree t = gimple_label_label (label_stmt);
522 : 15632 : gcc_assert (TREE_CODE (t) == LABEL_DECL);
523 : :
524 : 15632 : m_label_bb_map.put (t, bb->bb->index);
525 : : }
526 : : }
527 : 1057714 : }
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 : 399713 : func_checker::compare_bb (sem_bb *bb1, sem_bb *bb2)
538 : : {
539 : 399713 : gimple_stmt_iterator gsi1, gsi2;
540 : 399713 : gimple *s1, *s2;
541 : :
542 : 399713 : gsi1 = gsi_start_nondebug_bb (bb1->bb);
543 : 399713 : gsi2 = gsi_start_nondebug_bb (bb2->bb);
544 : :
545 : 1227749 : while (!gsi_end_p (gsi1))
546 : : {
547 : 863518 : if (gsi_end_p (gsi2))
548 : 0 : return return_false ();
549 : :
550 : 863518 : s1 = gsi_stmt (gsi1);
551 : 863518 : s2 = gsi_stmt (gsi2);
552 : :
553 : 863518 : int eh1 = lookup_stmt_eh_lp_fn
554 : 863518 : (DECL_STRUCT_FUNCTION (m_source_func_decl), s1);
555 : 863518 : int eh2 = lookup_stmt_eh_lp_fn
556 : 863518 : (DECL_STRUCT_FUNCTION (m_target_func_decl), s2);
557 : :
558 : 863518 : if (eh1 != eh2)
559 : 15 : return return_false_with_msg ("EH regions are different");
560 : :
561 : 863503 : if (gimple_code (s1) != gimple_code (s2))
562 : 0 : return return_false_with_msg ("gimple codes are different");
563 : :
564 : 863503 : switch (gimple_code (s1))
565 : : {
566 : 230832 : case GIMPLE_CALL:
567 : 230832 : if (!compare_gimple_call (as_a <gcall *> (s1),
568 : : as_a <gcall *> (s2)))
569 : 30359 : return return_different_stmts (s1, s2, "GIMPLE_CALL");
570 : : break;
571 : 367300 : case GIMPLE_ASSIGN:
572 : 367300 : if (!compare_gimple_assign (s1, s2))
573 : 1685 : return return_different_stmts (s1, s2, "GIMPLE_ASSIGN");
574 : : break;
575 : 104368 : case GIMPLE_COND:
576 : 104368 : if (!compare_gimple_cond (s1, s2))
577 : 3310 : return return_different_stmts (s1, s2, "GIMPLE_COND");
578 : : break;
579 : 366 : case GIMPLE_SWITCH:
580 : 366 : if (!compare_gimple_switch (as_a <gswitch *> (s1),
581 : 366 : as_a <gswitch *> (s2)))
582 : 2 : return return_different_stmts (s1, s2, "GIMPLE_SWITCH");
583 : : break;
584 : : case GIMPLE_DEBUG:
585 : : break;
586 : 194 : case GIMPLE_EH_DISPATCH:
587 : 194 : if (gimple_eh_dispatch_region (as_a <geh_dispatch *> (s1))
588 : 194 : != gimple_eh_dispatch_region (as_a <geh_dispatch *> (s2)))
589 : 0 : return return_different_stmts (s1, s2, "GIMPLE_EH_DISPATCH");
590 : : break;
591 : 3560 : case GIMPLE_RESX:
592 : 3560 : if (!compare_gimple_resx (as_a <gresx *> (s1),
593 : 3560 : as_a <gresx *> (s2)))
594 : 0 : return return_different_stmts (s1, s2, "GIMPLE_RESX");
595 : : break;
596 : 7470 : case GIMPLE_LABEL:
597 : 7470 : if (!compare_gimple_label (as_a <glabel *> (s1),
598 : 7470 : as_a <glabel *> (s2)))
599 : 12 : return return_different_stmts (s1, s2, "GIMPLE_LABEL");
600 : : break;
601 : 143369 : case GIMPLE_RETURN:
602 : 143369 : if (!compare_gimple_return (as_a <greturn *> (s1),
603 : 143369 : as_a <greturn *> (s2)))
604 : 36 : return return_different_stmts (s1, s2, "GIMPLE_RETURN");
605 : : break;
606 : 0 : case GIMPLE_GOTO:
607 : 0 : if (!compare_gimple_goto (s1, s2))
608 : 0 : return return_different_stmts (s1, s2, "GIMPLE_GOTO");
609 : : break;
610 : 5419 : case GIMPLE_ASM:
611 : 5419 : if (!compare_gimple_asm (as_a <gasm *> (s1),
612 : 5419 : as_a <gasm *> (s2)))
613 : 63 : return return_different_stmts (s1, s2, "GIMPLE_ASM");
614 : : break;
615 : : case GIMPLE_PREDICT:
616 : : case GIMPLE_NOP:
617 : : break;
618 : 0 : default:
619 : 0 : return return_false_with_msg ("Unknown GIMPLE code reached");
620 : : }
621 : :
622 : 828036 : gsi_next_nondebug (&gsi1);
623 : 828036 : gsi_next_nondebug (&gsi2);
624 : : }
625 : :
626 : 364231 : if (!gsi_end_p (gsi2))
627 : 0 : return return_false ();
628 : :
629 : 364231 : if (!compare_loops (bb1->bb, bb2->bb))
630 : 22 : 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 : 230832 : func_checker::compare_gimple_call (gcall *s1, gcall *s2)
640 : : {
641 : 230832 : unsigned i;
642 : 230832 : tree t1, t2;
643 : :
644 : 230832 : if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
645 : : return false;
646 : :
647 : 230832 : operand_access_type_map map (5);
648 : 230832 : classify_operands (s1, &map);
649 : :
650 : 230832 : t1 = gimple_call_fn (s1);
651 : 230832 : t2 = gimple_call_fn (s2);
652 : 230832 : if (!compare_operand (t1, t2, get_operand_access_type (&map, t1)))
653 : 0 : return return_false ();
654 : :
655 : : /* Compare flags. */
656 : 230832 : if (gimple_call_internal_p (s1) != gimple_call_internal_p (s2)
657 : 230832 : || gimple_call_ctrl_altering_p (s1) != gimple_call_ctrl_altering_p (s2)
658 : 230832 : || gimple_call_tail_p (s1) != gimple_call_tail_p (s2)
659 : 230832 : || gimple_call_return_slot_opt_p (s1) != gimple_call_return_slot_opt_p (s2)
660 : 230832 : || gimple_call_from_thunk_p (s1) != gimple_call_from_thunk_p (s2)
661 : 230832 : || gimple_call_from_new_or_delete (s1) != gimple_call_from_new_or_delete (s2)
662 : 230832 : || gimple_call_va_arg_pack_p (s1) != gimple_call_va_arg_pack_p (s2)
663 : 461664 : || gimple_call_alloca_for_var_p (s1) != gimple_call_alloca_for_var_p (s2))
664 : : return false;
665 : :
666 : 230832 : if (gimple_call_internal_p (s1)
667 : 230832 : && gimple_call_internal_fn (s1) != gimple_call_internal_fn (s2))
668 : : return false;
669 : :
670 : 203425 : tree fntype1 = gimple_call_fntype (s1);
671 : 203425 : tree fntype2 = gimple_call_fntype (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 : 203425 : if (!gimple_call_fndecl (s1))
677 : : {
678 : 66578 : if ((fntype1 && !fntype2)
679 : 66578 : || (!fntype1 && fntype2)
680 : 66578 : || (fntype1 && !types_compatible_p (fntype1, fntype2)))
681 : 16 : return return_false_with_msg ("call function types are not compatible");
682 : : }
683 : :
684 : 203409 : if (fntype1 && fntype2 && comp_type_attributes (fntype1, fntype2) != 1)
685 : 0 : return return_false_with_msg ("different fntype attributes");
686 : :
687 : 203409 : tree chain1 = gimple_call_chain (s1);
688 : 203409 : tree chain2 = gimple_call_chain (s2);
689 : 203409 : if ((chain1 && !chain2)
690 : 203409 : || (!chain1 && chain2)
691 : 203409 : || !compare_operand (chain1, chain2,
692 : : get_operand_access_type (&map, chain1)))
693 : 0 : return return_false_with_msg ("static call chains are different");
694 : :
695 : : /* Checking of argument. */
696 : 474896 : for (i = 0; i < gimple_call_num_args (s1); ++i)
697 : : {
698 : 271527 : t1 = gimple_call_arg (s1, i);
699 : 271527 : t2 = gimple_call_arg (s2, i);
700 : :
701 : 271527 : if (!compare_operand (t1, t2, get_operand_access_type (&map, t1)))
702 : 40 : return return_false_with_msg ("GIMPLE call operands are different");
703 : : }
704 : :
705 : : /* Return value checking. */
706 : 203369 : t1 = gimple_get_lhs (s1);
707 : 203369 : 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 : 203369 : if (gimple_call_internal_p (s1)
712 : 58073 : && t1
713 : 58073 : && t2
714 : 261259 : && !compatible_types_p (TREE_TYPE (t1), TREE_TYPE (t2)))
715 : 2890 : return return_false_with_msg ("GIMPLE internal call LHS type mismatch");
716 : :
717 : 200479 : return compare_operand (t1, t2, get_operand_access_type (&map, t1));
718 : 230832 : }
719 : :
720 : :
721 : : /* Verifies for given GIMPLEs S1 and S2 that
722 : : assignment statements are semantically equivalent. */
723 : :
724 : : bool
725 : 367300 : func_checker::compare_gimple_assign (gimple *s1, gimple *s2)
726 : : {
727 : 367300 : tree arg1, arg2;
728 : 367300 : tree_code code1, code2;
729 : 367300 : unsigned i;
730 : :
731 : 367300 : code1 = gimple_assign_rhs_code (s1);
732 : 367300 : code2 = gimple_assign_rhs_code (s2);
733 : :
734 : 367300 : if (code1 != code2)
735 : : return false;
736 : :
737 : 367300 : operand_access_type_map map (5);
738 : 367300 : classify_operands (s1, &map);
739 : :
740 : 1546594 : for (i = 0; i < gimple_num_ops (s1); i++)
741 : : {
742 : 813679 : arg1 = gimple_op (s1, i);
743 : 813679 : arg2 = gimple_op (s2, i);
744 : :
745 : : /* Compare types for LHS. */
746 : 813679 : if (i == 0 && !gimple_store_p (s1))
747 : : {
748 : 298427 : if (!compatible_types_p (TREE_TYPE (arg1), TREE_TYPE (arg2)))
749 : 1097 : return return_false_with_msg ("GIMPLE LHS type mismatch");
750 : : }
751 : :
752 : 812582 : if (!compare_operand (arg1, arg2, get_operand_access_type (&map, arg1)))
753 : 588 : return return_false_with_msg ("GIMPLE assignment operands "
754 : : "are different");
755 : : }
756 : :
757 : :
758 : : return true;
759 : 367300 : }
760 : :
761 : : /* Verifies for given GIMPLEs S1 and S2 that
762 : : condition statements are semantically equivalent. */
763 : :
764 : : bool
765 : 104368 : func_checker::compare_gimple_cond (gimple *s1, gimple *s2)
766 : : {
767 : 104368 : tree t1, t2;
768 : 104368 : tree_code code1, code2;
769 : :
770 : 104368 : code1 = gimple_cond_code (s1);
771 : 104368 : code2 = gimple_cond_code (s2);
772 : :
773 : 104368 : if (code1 != code2)
774 : : return false;
775 : :
776 : 101058 : t1 = gimple_cond_lhs (s1);
777 : 101058 : t2 = gimple_cond_lhs (s2);
778 : :
779 : 101058 : if (!compare_operand (t1, t2, OP_NORMAL))
780 : : return false;
781 : :
782 : 101058 : t1 = gimple_cond_rhs (s1);
783 : 101058 : t2 = gimple_cond_rhs (s2);
784 : :
785 : 101058 : return compare_operand (t1, t2, 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 : 7470 : func_checker::compare_gimple_label (const glabel *g1, const glabel *g2)
793 : : {
794 : 7470 : if (m_ignore_labels)
795 : : return true;
796 : :
797 : 7470 : tree t1 = gimple_label_label (g1);
798 : 7470 : tree t2 = gimple_label_label (g2);
799 : :
800 : 14928 : if (FORCED_LABEL (t1) || FORCED_LABEL (t2))
801 : 12 : 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 : 366 : func_checker::compare_gimple_switch (const gswitch *g1, const gswitch *g2)
812 : : {
813 : 366 : unsigned lsize1, lsize2, i;
814 : :
815 : 366 : lsize1 = gimple_switch_num_labels (g1);
816 : 366 : lsize2 = gimple_switch_num_labels (g2);
817 : :
818 : 366 : if (lsize1 != lsize2)
819 : : return false;
820 : :
821 : 365 : tree t1 = gimple_switch_index (g1);
822 : 365 : tree t2 = gimple_switch_index (g2);
823 : :
824 : 365 : if (!compare_operand (t1, t2, OP_NORMAL))
825 : : return false;
826 : :
827 : 3256 : for (i = 0; i < lsize1; i++)
828 : : {
829 : 2892 : tree label1 = gimple_switch_label (g1, i);
830 : 2892 : tree label2 = gimple_switch_label (g2, i);
831 : :
832 : : /* Label LOW and HIGH comparison. */
833 : 2892 : tree low1 = CASE_LOW (label1);
834 : 2892 : tree low2 = CASE_LOW (label2);
835 : :
836 : 2892 : if (!tree_int_cst_equal (low1, low2))
837 : 1 : return return_false_with_msg ("case low values are different");
838 : :
839 : 2891 : tree high1 = CASE_HIGH (label1);
840 : 2891 : tree high2 = CASE_HIGH (label2);
841 : :
842 : 2891 : if (!tree_int_cst_equal (high1, high2))
843 : 0 : return return_false_with_msg ("case high values are different");
844 : :
845 : 2891 : if (TREE_CODE (label1) == CASE_LABEL_EXPR
846 : 2891 : && TREE_CODE (label2) == CASE_LABEL_EXPR)
847 : : {
848 : 2891 : label1 = CASE_LABEL (label1);
849 : 2891 : label2 = CASE_LABEL (label2);
850 : :
851 : 2891 : if (!compare_operand (label1, label2, OP_NORMAL))
852 : 0 : return return_false_with_msg ("switch label_exprs are different");
853 : : }
854 : 0 : else if (!tree_int_cst_equal (label1, label2))
855 : 0 : 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 : 143369 : func_checker::compare_gimple_return (const greturn *g1, const greturn *g2)
866 : : {
867 : 143369 : tree t1, t2;
868 : :
869 : 143369 : t1 = gimple_return_retval (g1);
870 : 143369 : t2 = gimple_return_retval (g2);
871 : :
872 : : /* Void return type. */
873 : 143369 : if (t1 == NULL && t2 == NULL)
874 : : return true;
875 : : else
876 : : {
877 : 75883 : operand_access_type_map map (3);
878 : 75883 : return compare_operand (t1, t2, get_operand_access_type (&map, t1));
879 : 75883 : }
880 : : }
881 : :
882 : : /* Verifies for given GIMPLEs S1 and S2 that
883 : : goto statements are semantically equivalent. */
884 : :
885 : : bool
886 : 0 : func_checker::compare_gimple_goto (gimple *g1, gimple *g2)
887 : : {
888 : 0 : tree dest1, dest2;
889 : :
890 : 0 : dest1 = gimple_goto_dest (g1);
891 : 0 : dest2 = gimple_goto_dest (g2);
892 : :
893 : 0 : if (TREE_CODE (dest1) != TREE_CODE (dest2) || TREE_CODE (dest1) != SSA_NAME)
894 : : return false;
895 : :
896 : 0 : return compare_operand (dest1, dest2, 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 : 3560 : func_checker::compare_gimple_resx (const gresx *g1, const gresx *g2)
904 : : {
905 : 3560 : return gimple_resx_region (g1) == gimple_resx_region (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 : 5419 : func_checker::compare_gimple_asm (const gasm *g1, const gasm *g2)
914 : : {
915 : 5419 : if (gimple_asm_volatile_p (g1) != gimple_asm_volatile_p (g2))
916 : : return false;
917 : :
918 : 5415 : if (gimple_asm_input_p (g1) != gimple_asm_input_p (g2))
919 : : return false;
920 : :
921 : 5415 : if (gimple_asm_inline_p (g1) != gimple_asm_inline_p (g2))
922 : : return false;
923 : :
924 : 5415 : if (gimple_asm_ninputs (g1) != gimple_asm_ninputs (g2))
925 : : return false;
926 : :
927 : 5413 : if (gimple_asm_noutputs (g1) != gimple_asm_noutputs (g2))
928 : : return false;
929 : :
930 : : /* We do not suppport goto ASM statement comparison. */
931 : 5413 : if (gimple_asm_nlabels (g1) || gimple_asm_nlabels (g2))
932 : : return false;
933 : :
934 : 5389 : if (gimple_asm_nclobbers (g1) != gimple_asm_nclobbers (g2))
935 : : return false;
936 : :
937 : 5389 : if (strcmp (gimple_asm_string (g1), gimple_asm_string (g2)) != 0)
938 : 5 : return return_false_with_msg ("ASM strings are different");
939 : :
940 : 5384 : operand_access_type_map map (5);
941 : 5384 : classify_operands (g1, &map);
942 : :
943 : 5774 : for (unsigned i = 0; i < gimple_asm_ninputs (g1); i++)
944 : : {
945 : 417 : tree input1 = gimple_asm_input_op (g1, i);
946 : 417 : tree input2 = gimple_asm_input_op (g2, i);
947 : :
948 : 417 : if (!compare_asm_inputs_outputs (input1, input2, &map))
949 : 27 : return return_false_with_msg ("ASM input is different");
950 : : }
951 : :
952 : 5865 : for (unsigned i = 0; i < gimple_asm_noutputs (g1); i++)
953 : : {
954 : 509 : tree output1 = gimple_asm_output_op (g1, i);
955 : 509 : tree output2 = gimple_asm_output_op (g2, i);
956 : :
957 : 509 : if (!compare_asm_inputs_outputs (output1, output2, &map))
958 : 1 : return return_false_with_msg ("ASM output is different");
959 : : }
960 : :
961 : 18232 : for (unsigned i = 0; i < gimple_asm_nclobbers (g1); i++)
962 : : {
963 : 12876 : tree clobber1 = gimple_asm_clobber_op (g1, i);
964 : 12876 : tree clobber2 = gimple_asm_clobber_op (g2, i);
965 : :
966 : 12876 : if (!operand_equal_p (TREE_VALUE (clobber1), TREE_VALUE (clobber2),
967 : : OEP_ONLY_CONST))
968 : 0 : return return_false_with_msg ("ASM clobber is different");
969 : : }
970 : :
971 : : return true;
972 : 5384 : }
973 : :
974 : : /* Helper for func_checker::classify_operands. Record that T is a load. */
975 : :
976 : : static bool
977 : 6909408 : visit_load_store (gimple *, tree, tree t, void *data)
978 : : {
979 : 6909408 : func_checker::operand_access_type_map *map =
980 : : (func_checker::operand_access_type_map *) data;
981 : 6909408 : map->add (t);
982 : 6909408 : return false;
983 : : }
984 : :
985 : : /* Compute hash map determining access types of operands. */
986 : :
987 : : void
988 : 18362460 : func_checker::classify_operands (const gimple *stmt,
989 : : operand_access_type_map *map)
990 : : {
991 : 18362460 : walk_stmt_load_store_ops (const_cast <gimple *> (stmt),
992 : : (void *)map, visit_load_store, visit_load_store);
993 : 18362460 : }
994 : :
995 : : /* Return access type of a given operand. */
996 : :
997 : : func_checker::operand_access_type
998 : 54962908 : func_checker::get_operand_access_type (operand_access_type_map *map, tree t)
999 : : {
1000 : 54962908 : if (map->contains (t))
1001 : 6901333 : return OP_MEMORY;
1002 : : return OP_NORMAL;
1003 : : }
1004 : :
1005 : : } // ipa_icf_gimple namespace
|