1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2017 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
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
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
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/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
57 #include "coretypes.h"
63 #include "alloc-pool.h"
64 #include "tree-pass.h"
68 #include "gimple-pretty-print.h"
69 #include "data-streamer.h"
70 #include "fold-const.h"
73 #include "gimple-iterator.h"
75 #include "symbol-summary.h"
77 #include "ipa-fnsummary.h"
80 #include "print-tree.h"
81 #include "ipa-utils.h"
82 #include "ipa-icf-gimple.h"
84 #include "stor-layout.h"
87 using namespace ipa_icf_gimple
;
91 /* Initialization and computation of symtab node hash, there data
92 are propagated later on. */
94 static sem_item_optimizer
*optimizer
= NULL
;
98 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
100 m_references
.create (0);
101 m_interposables
.create (0);
105 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
108 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
110 if (ref
->address_matters_p ())
111 m_references
.safe_push (ref
->referred
);
113 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
115 if (ref
->address_matters_p ())
116 m_references
.safe_push (ref
->referred
);
118 m_interposables
.safe_push (ref
->referred
);
122 if (is_a
<cgraph_node
*> (node
))
124 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
126 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
127 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
128 m_interposables
.safe_push (e
->callee
);
132 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
134 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
)
135 : item (_item
), index (_index
)
139 sem_item::sem_item (sem_item_type _type
, bitmap_obstack
*stack
)
140 : type (_type
), m_hash (-1), m_hash_set (false)
145 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
146 bitmap_obstack
*stack
)
147 : type (_type
), node (_node
), m_hash (-1), m_hash_set (false)
153 /* Add reference to a semantic TARGET. */
156 sem_item::add_reference (sem_item
*target
)
158 refs
.safe_push (target
);
159 unsigned index
= refs
.length ();
160 target
->usages
.safe_push (new sem_usage_pair(this, index
));
161 bitmap_set_bit (target
->usage_index_bitmap
, index
);
162 refs_set
.add (target
->node
);
165 /* Initialize internal data structures. Bitmap STACK is used for
166 bitmap memory allocation process. */
169 sem_item::setup (bitmap_obstack
*stack
)
171 gcc_checking_assert (node
);
174 tree_refs
.create (0);
176 usage_index_bitmap
= BITMAP_ALLOC (stack
);
179 sem_item::~sem_item ()
181 for (unsigned i
= 0; i
< usages
.length (); i
++)
185 tree_refs
.release ();
188 BITMAP_FREE (usage_index_bitmap
);
191 /* Dump function for debugging purpose. */
194 sem_item::dump (void)
198 fprintf (dump_file
, "[%s] %s (tree:%p)\n", type
== FUNC
? "func" : "var",
199 node
->dump_name (), (void *) node
->decl
);
200 fprintf (dump_file
, " hash: %u\n", get_hash ());
201 fprintf (dump_file
, " references: ");
203 for (unsigned i
= 0; i
< refs
.length (); i
++)
204 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
205 i
< refs
.length() - 1 ? "," : "");
207 fprintf (dump_file
, "\n");
211 /* Return true if target supports alias symbols. */
214 sem_item::target_supports_symbol_aliases_p (void)
216 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
223 void sem_item::set_hash (hashval_t hash
)
229 /* Semantic function constructor that uses STACK as bitmap memory stack. */
231 sem_function::sem_function (bitmap_obstack
*stack
)
232 : sem_item (FUNC
, stack
), m_checker (NULL
), m_compared_func (NULL
)
235 bb_sorted
.create (0);
238 sem_function::sem_function (cgraph_node
*node
, bitmap_obstack
*stack
)
239 : sem_item (FUNC
, node
, stack
), m_checker (NULL
), m_compared_func (NULL
)
242 bb_sorted
.create (0);
245 sem_function::~sem_function ()
247 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
248 delete (bb_sorted
[i
]);
251 bb_sorted
.release ();
254 /* Calculates hash value based on a BASIC_BLOCK. */
257 sem_function::get_bb_hash (const sem_bb
*basic_block
)
259 inchash::hash hstate
;
261 hstate
.add_int (basic_block
->nondbg_stmt_count
);
262 hstate
.add_int (basic_block
->edge_count
);
264 return hstate
.end ();
267 /* References independent hash function. */
270 sem_function::get_hash (void)
274 inchash::hash hstate
;
275 hstate
.add_int (177454); /* Random number for function type. */
277 hstate
.add_int (arg_count
);
278 hstate
.add_int (cfg_checksum
);
279 hstate
.add_int (gcode_hash
);
281 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
282 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
284 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
285 hstate
.add_int (bb_sizes
[i
]);
287 /* Add common features of declaration itself. */
288 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
290 (cl_target_option_hash
291 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
292 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
294 (cl_optimization_hash
295 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
296 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
297 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
299 set_hash (hstate
.end ());
305 /* Return ture if A1 and A2 represent equivalent function attribute lists.
306 Based on comp_type_attributes. */
309 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
314 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
316 const struct attribute_spec
*as
;
319 as
= lookup_attribute_spec (get_attribute_name (a
));
320 /* TODO: We can introduce as->affects_decl_identity
321 and as->affects_decl_reference_identity if attribute mismatch
322 gets a common reason to give up on merging. It may not be worth
324 For example returns_nonnull affects only references, while
325 optimize attribute can be ignored because it is already lowered
326 into flags representation and compared separately. */
330 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
331 if (!attr
|| !attribute_value_equal (a
, attr
))
336 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
338 const struct attribute_spec
*as
;
340 as
= lookup_attribute_spec (get_attribute_name (a
));
344 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
346 /* We don't need to compare trees again, as we did this
347 already in first loop. */
352 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
356 /* Compare properties of symbols N1 and N2 that does not affect semantics of
357 symbol itself but affects semantics of its references from USED_BY (which
358 may be NULL if it is unknown). If comparsion is false, symbols
359 can still be merged but any symbols referring them can't.
361 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
363 TODO: We can also split attributes to those that determine codegen of
364 a function body/variable constructor itself and those that are used when
368 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
373 if (is_a
<cgraph_node
*> (n1
))
375 /* Inline properties matters: we do now want to merge uses of inline
376 function to uses of normal function because inline hint would be lost.
377 We however can merge inline function to noinline because the alias
378 will keep its DECL_DECLARED_INLINE flag.
380 Also ignore inline flag when optimizing for size or when function
381 is known to not be inlinable.
383 TODO: the optimize_size checks can also be assumed to be true if
384 unit has no !optimize_size functions. */
386 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
387 || !opt_for_fn (used_by
->decl
, optimize_size
))
388 && !opt_for_fn (n1
->decl
, optimize_size
)
389 && n1
->get_availability () > AVAIL_INTERPOSABLE
390 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
392 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
393 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
394 return return_false_with_msg
395 ("DECL_DISREGARD_INLINE_LIMITS are different");
397 if (DECL_DECLARED_INLINE_P (n1
->decl
)
398 != DECL_DECLARED_INLINE_P (n2
->decl
))
399 return return_false_with_msg ("inline attributes are different");
402 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
403 != DECL_IS_OPERATOR_NEW (n2
->decl
))
404 return return_false_with_msg ("operator new flags are different");
407 /* Merging two definitions with a reference to equivalent vtables, but
408 belonging to a different type may result in ipa-polymorphic-call analysis
409 giving a wrong answer about the dynamic type of instance. */
410 if (is_a
<varpool_node
*> (n1
))
412 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
413 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
414 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
415 DECL_CONTEXT (n2
->decl
)))
416 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
417 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
418 return return_false_with_msg
419 ("references to virtual tables can not be merged");
421 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
422 return return_false_with_msg ("alignment mismatch");
424 /* For functions we compare attributes in equals_wpa, because we do
425 not know what attributes may cause codegen differences, but for
426 variables just compare attributes for references - the codegen
427 for constructors is affected only by those attributes that we lower
428 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
429 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
430 DECL_ATTRIBUTES (n2
->decl
)))
431 return return_false_with_msg ("different var decl attributes");
432 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
433 TREE_TYPE (n2
->decl
)) != 1)
434 return return_false_with_msg ("different var type attributes");
437 /* When matching virtual tables, be sure to also match information
438 relevant for polymorphic call analysis. */
439 if (used_by
&& is_a
<varpool_node
*> (used_by
)
440 && DECL_VIRTUAL_P (used_by
->decl
))
442 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
443 return return_false_with_msg ("virtual flag mismatch");
444 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
445 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
446 return return_false_with_msg ("final flag mismatch");
451 /* Hash properties that are compared by compare_referenced_symbol_properties. */
454 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
455 inchash::hash
&hstate
,
458 if (is_a
<cgraph_node
*> (ref
))
460 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
461 && !opt_for_fn (ref
->decl
, optimize_size
)
462 && !DECL_UNINLINABLE (ref
->decl
))
464 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
465 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
467 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
469 else if (is_a
<varpool_node
*> (ref
))
471 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
473 hstate
.add_int (DECL_ALIGN (ref
->decl
));
478 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
479 point to a same function. Comparison can be skipped if IGNORED_NODES
480 contains these nodes. ADDRESS indicate if address is taken. */
483 sem_item::compare_symbol_references (
484 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
485 symtab_node
*n1
, symtab_node
*n2
, bool address
)
487 enum availability avail1
, avail2
;
492 /* Never match variable and function. */
493 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
496 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
498 if (address
&& n1
->equal_address_to (n2
) == 1)
500 if (!address
&& n1
->semantically_equivalent_p (n2
))
503 n1
= n1
->ultimate_alias_target (&avail1
);
504 n2
= n2
->ultimate_alias_target (&avail2
);
506 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
507 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
510 return return_false_with_msg ("different references");
513 /* If cgraph edges E1 and E2 are indirect calls, verify that
514 ECF flags are the same. */
516 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
518 if (e1
->indirect_info
&& e2
->indirect_info
)
520 int e1_flags
= e1
->indirect_info
->ecf_flags
;
521 int e2_flags
= e2
->indirect_info
->ecf_flags
;
523 if (e1_flags
!= e2_flags
)
524 return return_false_with_msg ("ICF flags are different");
526 else if (e1
->indirect_info
|| e2
->indirect_info
)
532 /* Return true if parameter I may be used. */
535 sem_function::param_used_p (unsigned int i
)
537 if (ipa_node_params_sum
== NULL
)
540 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
542 if (vec_safe_length (parms_info
->descriptors
) <= i
)
545 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
548 /* Perform additional check needed to match types function parameters that are
549 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
550 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
553 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
555 /* Be sure that parameters are TBAA compatible. */
556 if (!func_checker::compatible_types_p (parm1
, parm2
))
557 return return_false_with_msg ("parameter type is not compatible");
559 if (POINTER_TYPE_P (parm1
)
560 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
561 return return_false_with_msg ("argument restrict flag mismatch");
563 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
564 if (POINTER_TYPE_P (parm1
)
565 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
566 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
567 return return_false_with_msg ("pointer wrt reference mismatch");
572 /* Fast equality function based on knowledge known in WPA. */
575 sem_function::equals_wpa (sem_item
*item
,
576 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
578 gcc_assert (item
->type
== FUNC
);
579 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
580 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
582 m_compared_func
= static_cast<sem_function
*> (item
);
584 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
585 return return_false_with_msg ("thunk_p mismatch");
587 if (cnode
->thunk
.thunk_p
)
589 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
590 return return_false_with_msg ("thunk fixed_offset mismatch");
591 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
592 return return_false_with_msg ("thunk virtual_value mismatch");
593 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
594 return return_false_with_msg ("thunk this_adjusting mismatch");
595 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
596 return return_false_with_msg ("thunk virtual_offset_p mismatch");
597 if (cnode
->thunk
.add_pointer_bounds_args
598 != cnode2
->thunk
.add_pointer_bounds_args
)
599 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
602 /* Compare special function DECL attributes. */
603 if (DECL_FUNCTION_PERSONALITY (decl
)
604 != DECL_FUNCTION_PERSONALITY (item
->decl
))
605 return return_false_with_msg ("function personalities are different");
607 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
608 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
609 return return_false_with_msg ("intrument function entry exit "
610 "attributes are different");
612 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
613 return return_false_with_msg ("no stack limit attributes are different");
615 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
616 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
618 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
619 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
621 /* TODO: pure/const flags mostly matters only for references, except for
622 the fact that codegen takes LOOPING flag as a hint that loops are
623 finite. We may arrange the code to always pick leader that has least
624 specified flags and then this can go into comparing symbol properties. */
625 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
626 return return_false_with_msg ("decl_or_type flags are different");
628 /* Do not match polymorphic constructors of different types. They calls
629 type memory location for ipa-polymorphic-call and we do not want
630 it to get confused by wrong type. */
631 if (DECL_CXX_CONSTRUCTOR_P (decl
)
632 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
634 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
635 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
636 else if (!func_checker::compatible_polymorphic_types_p
637 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
638 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
639 return return_false_with_msg ("ctor polymorphic type mismatch");
642 /* Checking function TARGET and OPTIMIZATION flags. */
643 cl_target_option
*tar1
= target_opts_for_fn (decl
);
644 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
646 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
648 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
650 fprintf (dump_file
, "target flags difference");
651 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
654 return return_false_with_msg ("Target flags are different");
657 cl_optimization
*opt1
= opts_for_fn (decl
);
658 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
660 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
664 fprintf (dump_file
, "optimization flags difference");
665 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
668 return return_false_with_msg ("optimization flags are different");
671 /* Result type checking. */
672 if (!func_checker::compatible_types_p
673 (TREE_TYPE (TREE_TYPE (decl
)),
674 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
675 return return_false_with_msg ("result types are different");
677 /* Checking types of arguments. */
678 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
679 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
680 for (unsigned i
= 0; list1
&& list2
;
681 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
683 tree parm1
= TREE_VALUE (list1
);
684 tree parm2
= TREE_VALUE (list2
);
686 /* This guard is here for function pointer with attributes (pr59927.c). */
687 if (!parm1
|| !parm2
)
688 return return_false_with_msg ("NULL argument type");
690 /* Verify that types are compatible to ensure that both functions
691 have same calling conventions. */
692 if (!types_compatible_p (parm1
, parm2
))
693 return return_false_with_msg ("parameter types are not compatible");
695 if (!param_used_p (i
))
698 /* Perform additional checks for used parameters. */
699 if (!compatible_parm_types_p (parm1
, parm2
))
704 return return_false_with_msg ("Mismatched number of parameters");
706 if (node
->num_references () != item
->node
->num_references ())
707 return return_false_with_msg ("different number of references");
709 /* Checking function attributes.
710 This is quadratic in number of attributes */
711 if (comp_type_attributes (TREE_TYPE (decl
),
712 TREE_TYPE (item
->decl
)) != 1)
713 return return_false_with_msg ("different type attributes");
714 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
715 DECL_ATTRIBUTES (item
->decl
)))
716 return return_false_with_msg ("different decl attributes");
718 /* The type of THIS pointer type memory location for
719 ipa-polymorphic-call-analysis. */
720 if (opt_for_fn (decl
, flag_devirtualize
)
721 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
722 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
724 && compare_polymorphic_p ())
726 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
727 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
728 if (!func_checker::compatible_polymorphic_types_p
729 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
730 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
731 return return_false_with_msg ("THIS pointer ODR type mismatch");
734 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
735 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
737 item
->node
->iterate_reference (i
, ref2
);
739 if (ref
->use
!= ref2
->use
)
740 return return_false_with_msg ("reference use mismatch");
742 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
744 ref
->address_matters_p ()))
748 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
749 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
753 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
756 if (!compare_edge_flags (e1
, e2
))
759 e1
= e1
->next_callee
;
760 e2
= e2
->next_callee
;
764 return return_false_with_msg ("different number of calls");
766 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
767 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
771 if (!compare_edge_flags (e1
, e2
))
774 e1
= e1
->next_callee
;
775 e2
= e2
->next_callee
;
779 return return_false_with_msg ("different number of indirect calls");
784 /* Update hash by address sensitive references. We iterate over all
785 sensitive references (address_matters_p) and we hash ultime alias
786 target of these nodes, which can improve a semantic item hash.
788 Also hash in referenced symbols properties. This can be done at any time
789 (as the properties should not change), but it is convenient to do it here
790 while we walk the references anyway. */
793 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
794 sem_item
*> &m_symtab_node_map
)
797 inchash::hash
hstate (get_hash ());
799 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
801 hstate
.add_int (ref
->use
);
802 hash_referenced_symbol_properties (ref
->referred
, hstate
,
803 ref
->use
== IPA_REF_ADDR
);
804 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
805 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
808 if (is_a
<cgraph_node
*> (node
))
810 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
813 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
814 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
816 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
820 set_hash (hstate
.end ());
823 /* Update hash by computed local hash values taken from different
825 TODO: stronger SCC based hashing would be desirable here. */
828 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
829 sem_item
*> &m_symtab_node_map
)
832 inchash::hash
state (get_hash ());
834 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
836 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
838 state
.merge_hash ((*result
)->get_hash ());
843 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
846 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
848 state
.merge_hash ((*result
)->get_hash ());
852 global_hash
= state
.end ();
855 /* Returns true if the item equals to ITEM given as argument. */
858 sem_function::equals (sem_item
*item
,
859 hash_map
<symtab_node
*, sem_item
*> &)
861 gcc_assert (item
->type
== FUNC
);
862 bool eq
= equals_private (item
);
864 if (m_checker
!= NULL
)
870 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
872 "Equals called for: %s:%s with result: %s\n\n",
874 item
->node
->dump_name (),
875 eq
? "true" : "false");
880 /* Processes function equality comparison. */
883 sem_function::equals_private (sem_item
*item
)
885 if (item
->type
!= FUNC
)
888 basic_block bb1
, bb2
;
890 edge_iterator ei1
, ei2
;
894 m_compared_func
= static_cast<sem_function
*> (item
);
896 gcc_assert (decl
!= item
->decl
);
898 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
899 || edge_count
!= m_compared_func
->edge_count
900 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
901 return return_false ();
903 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
904 compare_polymorphic_p (),
907 &m_compared_func
->refs_set
);
908 arg1
= DECL_ARGUMENTS (decl
);
909 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
911 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
913 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
914 return return_false_with_msg ("argument types are not compatible");
915 if (!param_used_p (i
))
917 /* Perform additional checks for used parameters. */
918 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
920 if (!m_checker
->compare_decl (arg1
, arg2
))
921 return return_false ();
924 return return_false_with_msg ("Mismatched number of arguments");
926 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
929 /* Fill-up label dictionary. */
930 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
932 m_checker
->parse_labels (bb_sorted
[i
]);
933 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
936 /* Checking all basic blocks. */
937 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
938 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
939 return return_false();
941 dump_message ("All BBs are equal\n");
943 auto_vec
<int> bb_dict
;
945 /* Basic block edges check. */
946 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
948 bb1
= bb_sorted
[i
]->bb
;
949 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
951 ei2
= ei_start (bb2
->preds
);
953 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
957 if (e1
->flags
!= e2
->flags
)
958 return return_false_with_msg ("flags comparison returns false");
960 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
961 return return_false_with_msg ("edge comparison returns false");
963 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
964 return return_false_with_msg ("BB comparison returns false");
966 if (!m_checker
->compare_edge (e1
, e2
))
967 return return_false_with_msg ("edge comparison returns false");
973 /* Basic block PHI nodes comparison. */
974 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
975 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
976 return return_false_with_msg ("PHI node comparison returns false");
981 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
982 Helper for call_for_symbol_thunks_and_aliases. */
985 set_local (cgraph_node
*node
, void *data
)
987 node
->local
.local
= data
!= NULL
;
991 /* TREE_ADDRESSABLE of NODE to true.
992 Helper for call_for_symbol_thunks_and_aliases. */
995 set_addressable (varpool_node
*node
, void *)
997 TREE_ADDRESSABLE (node
->decl
) = 1;
1001 /* Clear DECL_RTL of NODE.
1002 Helper for call_for_symbol_thunks_and_aliases. */
1005 clear_decl_rtl (symtab_node
*node
, void *)
1007 SET_DECL_RTL (node
->decl
, NULL
);
1011 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1012 possible. Return number of redirections made. */
1015 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1017 int nredirected
= 0;
1019 cgraph_edge
*e
= n
->callers
;
1023 /* Redirecting thunks to interposable symbols or symbols in other sections
1024 may not be supported by target output code. Play safe for now and
1025 punt on redirection. */
1026 if (!e
->caller
->thunk
.thunk_p
)
1028 struct cgraph_edge
*nexte
= e
->next_caller
;
1029 e
->redirect_callee (to
);
1036 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1038 bool removed
= false;
1039 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1041 if ((DECL_COMDAT_GROUP (n
->decl
)
1042 && (DECL_COMDAT_GROUP (n
->decl
)
1043 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1044 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1045 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1047 nredirected
+= redirect_all_callers (n_alias
, to
);
1048 if (n_alias
->can_remove_if_no_direct_calls_p ()
1049 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1051 && !n_alias
->has_aliases_p ())
1060 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1064 sem_function::merge (sem_item
*alias_item
)
1066 gcc_assert (alias_item
->type
== FUNC
);
1068 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1070 cgraph_node
*original
= get_node ();
1071 cgraph_node
*local_original
= NULL
;
1072 cgraph_node
*alias
= alias_func
->get_node ();
1074 bool create_wrapper
= false;
1075 bool create_alias
= false;
1076 bool redirect_callers
= false;
1077 bool remove
= false;
1079 bool original_discardable
= false;
1080 bool original_discarded
= false;
1082 bool original_address_matters
= original
->address_matters_p ();
1083 bool alias_address_matters
= alias
->address_matters_p ();
1085 if (DECL_EXTERNAL (alias
->decl
))
1088 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1092 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1093 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1098 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1102 /* Do not attempt to mix functions from different user sections;
1103 we do not know what user intends with those. */
1104 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1105 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1106 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1111 "original and alias are in different sections.\n\n");
1115 /* See if original is in a section that can be discarded if the main
1116 symbol is not used. */
1118 if (original
->can_be_discarded_p ())
1119 original_discardable
= true;
1120 /* Also consider case where we have resolution info and we know that
1121 original's definition is not going to be used. In this case we can not
1122 create alias to original. */
1123 if (node
->resolution
!= LDPR_UNKNOWN
1124 && !decl_binds_to_current_def_p (node
->decl
))
1125 original_discardable
= original_discarded
= true;
1127 /* Creating a symtab alias is the optimal way to merge.
1128 It however can not be used in the following cases:
1130 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1131 2) if ORIGINAL is in a section that may be discarded by linker or if
1132 it is an external functions where we can not create an alias
1133 (ORIGINAL_DISCARDABLE)
1134 3) if target do not support symbol aliases.
1135 4) original and alias lie in different comdat groups.
1137 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1138 and/or redirect all callers from ALIAS to ORIGINAL. */
1139 if ((original_address_matters
&& alias_address_matters
)
1140 || (original_discardable
1141 && (!DECL_COMDAT_GROUP (alias
->decl
)
1142 || (DECL_COMDAT_GROUP (alias
->decl
)
1143 != DECL_COMDAT_GROUP (original
->decl
))))
1144 || original_discarded
1145 || !sem_item::target_supports_symbol_aliases_p ()
1146 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1148 /* First see if we can produce wrapper. */
1150 /* Symbol properties that matter for references must be preserved.
1151 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1152 with proper properties. */
1153 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1154 alias
->address_taken
))
1158 "Wrapper cannot be created because referenced symbol "
1159 "properties mismatch\n");
1161 /* Do not turn function in one comdat group into wrapper to another
1162 comdat group. Other compiler producing the body of the
1163 another comdat group may make opossite decision and with unfortunate
1164 linker choices this may close a loop. */
1165 else if (DECL_COMDAT_GROUP (original
->decl
)
1166 && DECL_COMDAT_GROUP (alias
->decl
)
1167 && (DECL_COMDAT_GROUP (alias
->decl
)
1168 != DECL_COMDAT_GROUP (original
->decl
)))
1172 "Wrapper cannot be created because of COMDAT\n");
1174 else if (DECL_STATIC_CHAIN (alias
->decl
)
1175 || DECL_STATIC_CHAIN (original
->decl
))
1179 "Cannot create wrapper of nested function.\n");
1181 /* TODO: We can also deal with variadic functions never calling
1183 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1187 "can not create wrapper of stdarg function.\n");
1189 else if (ipa_fn_summaries
1190 && ipa_fn_summaries
->get (alias
)->self_size
<= 2)
1193 fprintf (dump_file
, "Wrapper creation is not "
1194 "profitable (function is too small).\n");
1196 /* If user paid attention to mark function noinline, assume it is
1197 somewhat special and do not try to turn it into a wrapper that can
1198 not be undone by inliner. */
1199 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1202 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1205 create_wrapper
= true;
1207 /* We can redirect local calls in the case both alias and orignal
1208 are not interposable. */
1210 = alias
->get_availability () > AVAIL_INTERPOSABLE
1211 && original
->get_availability () > AVAIL_INTERPOSABLE
1212 && !alias
->instrumented_version
;
1213 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1214 with proper properties. */
1215 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1216 alias
->address_taken
))
1217 redirect_callers
= false;
1219 if (!redirect_callers
&& !create_wrapper
)
1222 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1223 "produce wrapper\n\n");
1227 /* Work out the symbol the wrapper should call.
1228 If ORIGINAL is interposable, we need to call a local alias.
1229 Also produce local alias (if possible) as an optimization.
1231 Local aliases can not be created inside comdat groups because that
1232 prevents inlining. */
1233 if (!original_discardable
&& !original
->get_comdat_group ())
1236 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1238 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1239 local_original
= original
;
1241 /* If we can not use local alias, fallback to the original
1243 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1244 local_original
= original
;
1246 /* If original is COMDAT local, we can not really redirect calls outside
1247 of its comdat group to it. */
1248 if (original
->comdat_local_p ())
1249 redirect_callers
= false;
1250 if (!local_original
)
1253 fprintf (dump_file
, "Not unifying; "
1254 "can not produce local alias.\n\n");
1258 if (!redirect_callers
&& !create_wrapper
)
1261 fprintf (dump_file
, "Not unifying; "
1262 "can not redirect callers nor produce a wrapper\n\n");
1266 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1268 && !alias
->can_remove_if_no_direct_calls_p ())
1271 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1272 "function has other uses than direct calls\n\n");
1277 create_alias
= true;
1279 if (redirect_callers
)
1281 int nredirected
= redirect_all_callers (alias
, local_original
);
1285 alias
->icf_merged
= true;
1286 local_original
->icf_merged
= true;
1288 if (dump_file
&& nredirected
)
1289 fprintf (dump_file
, "%i local calls have been "
1290 "redirected.\n", nredirected
);
1293 /* If all callers was redirected, do not produce wrapper. */
1294 if (alias
->can_remove_if_no_direct_calls_p ()
1295 && !DECL_VIRTUAL_P (alias
->decl
)
1296 && !alias
->has_aliases_p ())
1298 create_wrapper
= false;
1301 gcc_assert (!create_alias
);
1303 else if (create_alias
)
1305 alias
->icf_merged
= true;
1307 /* Remove the function's body. */
1308 ipa_merge_profiles (original
, alias
);
1309 alias
->release_body (true);
1311 /* Notice global symbol possibly produced RTL. */
1312 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1315 /* Create the alias. */
1316 cgraph_node::create_alias (alias_func
->decl
, decl
);
1317 alias
->resolve_alias (original
);
1319 original
->call_for_symbol_thunks_and_aliases
1320 (set_local
, (void *)(size_t) original
->local_p (), true);
1323 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1327 gcc_assert (!create_alias
);
1328 alias
->icf_merged
= true;
1329 local_original
->icf_merged
= true;
1331 ipa_merge_profiles (local_original
, alias
, true);
1332 alias
->create_wrapper (local_original
);
1335 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1338 /* It's possible that redirection can hit thunks that block
1339 redirection opportunities. */
1340 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1341 original
->icf_merged
= true;
1343 /* We use merged flag to track cases where COMDAT function is known to be
1344 compatible its callers. If we merged in non-COMDAT, we need to give up
1345 on this optimization. */
1346 if (original
->merged_comdat
&& !alias
->merged_comdat
)
1349 fprintf (dump_file
, "Dropping merged_comdat flag.\n\n");
1351 local_original
->merged_comdat
= false;
1352 original
->merged_comdat
= false;
1357 ipa_merge_profiles (original
, alias
);
1358 alias
->release_body ();
1360 alias
->body_removed
= true;
1361 alias
->icf_merged
= true;
1363 fprintf (dump_file
, "Unified; Function body was removed.\n");
1369 /* Semantic item initialization function. */
1372 sem_function::init (void)
1375 get_node ()->get_untransformed_body ();
1377 tree fndecl
= node
->decl
;
1378 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1381 gcc_assert (SSANAMES (func
));
1383 ssa_names_size
= SSANAMES (func
)->length ();
1387 region_tree
= func
->eh
->region_tree
;
1389 /* iterating all function arguments. */
1390 arg_count
= count_formal_params (fndecl
);
1392 edge_count
= n_edges_for_fn (func
);
1393 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1394 if (!cnode
->thunk
.thunk_p
)
1396 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1398 inchash::hash hstate
;
1401 FOR_EACH_BB_FN (bb
, func
)
1403 unsigned nondbg_stmt_count
= 0;
1406 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1408 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1411 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1414 gimple
*stmt
= gsi_stmt (gsi
);
1416 if (gimple_code (stmt
) != GIMPLE_DEBUG
1417 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1419 hash_stmt (stmt
, hstate
);
1420 nondbg_stmt_count
++;
1424 gcode_hash
= hstate
.end ();
1425 bb_sizes
.safe_push (nondbg_stmt_count
);
1427 /* Inserting basic block to hash table. */
1428 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1429 EDGE_COUNT (bb
->preds
)
1430 + EDGE_COUNT (bb
->succs
));
1432 bb_sorted
.safe_push (semantic_bb
);
1438 inchash::hash hstate
;
1439 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1440 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1441 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1442 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1443 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1444 gcode_hash
= hstate
.end ();
1448 /* Accumulate to HSTATE a hash of expression EXP.
1449 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1450 and DECL equality classes. */
1453 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1455 if (exp
== NULL_TREE
)
1457 hstate
.merge_hash (0);
1461 /* Handled component can be matched in a cureful way proving equivalence
1462 even if they syntactically differ. Just skip them. */
1464 while (handled_component_p (exp
))
1465 exp
= TREE_OPERAND (exp
, 0);
1467 enum tree_code code
= TREE_CODE (exp
);
1468 hstate
.add_int (code
);
1472 /* Use inchash::add_expr for everything that is LTO stable. */
1480 inchash::add_expr (exp
, hstate
);
1484 unsigned HOST_WIDE_INT idx
;
1487 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1489 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1491 add_expr (value
, hstate
);
1496 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1502 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1505 case POINTER_PLUS_EXPR
:
1508 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1509 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1513 inchash::hash one
, two
;
1514 add_expr (TREE_OPERAND (exp
, 0), one
);
1515 add_expr (TREE_OPERAND (exp
, 1), two
);
1516 hstate
.add_commutative (one
, two
);
1520 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1521 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1527 /* Accumulate to HSTATE a hash of type t.
1528 TYpes that may end up being compatible after LTO type merging needs to have
1532 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1534 if (type
== NULL_TREE
)
1536 hstate
.merge_hash (0);
1540 type
= TYPE_MAIN_VARIANT (type
);
1542 hstate
.add_int (TYPE_MODE (type
));
1544 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1546 hstate
.add_int (COMPLEX_TYPE
);
1547 sem_item::add_type (TREE_TYPE (type
), hstate
);
1549 else if (INTEGRAL_TYPE_P (type
))
1551 hstate
.add_int (INTEGER_TYPE
);
1552 hstate
.add_flag (TYPE_UNSIGNED (type
));
1553 hstate
.add_int (TYPE_PRECISION (type
));
1555 else if (VECTOR_TYPE_P (type
))
1557 hstate
.add_int (VECTOR_TYPE
);
1558 hstate
.add_int (TYPE_PRECISION (type
));
1559 sem_item::add_type (TREE_TYPE (type
), hstate
);
1561 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1563 hstate
.add_int (ARRAY_TYPE
);
1564 /* Do not hash size, so complete and incomplete types can match. */
1565 sem_item::add_type (TREE_TYPE (type
), hstate
);
1567 else if (RECORD_OR_UNION_TYPE_P (type
))
1569 gcc_checking_assert (COMPLETE_TYPE_P (type
));
1570 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1574 inchash::hash hstate2
;
1579 hstate2
.add_int (RECORD_TYPE
);
1580 gcc_assert (COMPLETE_TYPE_P (type
));
1582 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1583 if (TREE_CODE (f
) == FIELD_DECL
)
1585 add_type (TREE_TYPE (f
), hstate2
);
1589 hstate2
.add_int (nf
);
1590 hash
= hstate2
.end ();
1591 hstate
.add_wide_int (hash
);
1592 optimizer
->m_type_hash_cache
.put (type
, hash
);
1595 hstate
.add_wide_int (*val
);
1599 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1602 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1604 enum gimple_code code
= gimple_code (stmt
);
1606 hstate
.add_int (code
);
1611 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1614 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1615 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1616 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1618 inchash::hash one
, two
;
1620 add_expr (gimple_assign_rhs1 (stmt
), one
);
1621 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1622 add_expr (gimple_assign_rhs2 (stmt
), two
);
1623 hstate
.add_commutative (one
, two
);
1624 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1626 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1627 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1629 add_expr (gimple_assign_lhs (stmt
), hstate
);
1630 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1639 /* All these statements are equivalent if their operands are. */
1640 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1642 add_expr (gimple_op (stmt
, i
), hstate
);
1643 if (gimple_op (stmt
, i
))
1644 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1652 /* Return true if polymorphic comparison must be processed. */
1655 sem_function::compare_polymorphic_p (void)
1657 struct cgraph_edge
*e
;
1659 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1661 if (get_node ()->indirect_calls
!= NULL
)
1663 /* TODO: We can do simple propagation determining what calls may lead to
1664 a polymorphic call. */
1665 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1666 if (e
->callee
->definition
1667 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1672 /* For a given call graph NODE, the function constructs new
1673 semantic function item. */
1676 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1678 tree fndecl
= node
->decl
;
1679 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1681 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1684 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1687 if (lookup_attribute_by_prefix ("oacc ",
1688 DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1692 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1693 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1696 sem_function
*f
= new sem_function (node
, stack
);
1703 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1704 return true if phi nodes are semantically equivalent in these blocks . */
1707 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1709 gphi_iterator si1
, si2
;
1711 unsigned size1
, size2
, i
;
1715 gcc_assert (bb1
!= NULL
);
1716 gcc_assert (bb2
!= NULL
);
1718 si2
= gsi_start_phis (bb2
);
1719 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1722 gsi_next_nonvirtual_phi (&si1
);
1723 gsi_next_nonvirtual_phi (&si2
);
1725 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1728 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1729 return return_false();
1734 tree phi_result1
= gimple_phi_result (phi1
);
1735 tree phi_result2
= gimple_phi_result (phi2
);
1737 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1738 return return_false_with_msg ("PHI results are different");
1740 size1
= gimple_phi_num_args (phi1
);
1741 size2
= gimple_phi_num_args (phi2
);
1744 return return_false ();
1746 for (i
= 0; i
< size1
; ++i
)
1748 t1
= gimple_phi_arg (phi1
, i
)->def
;
1749 t2
= gimple_phi_arg (phi2
, i
)->def
;
1751 if (!m_checker
->compare_operand (t1
, t2
))
1752 return return_false ();
1754 e1
= gimple_phi_arg_edge (phi1
, i
);
1755 e2
= gimple_phi_arg_edge (phi2
, i
);
1757 if (!m_checker
->compare_edge (e1
, e2
))
1758 return return_false ();
1767 /* Returns true if tree T can be compared as a handled component. */
1770 sem_function::icf_handled_component_p (tree t
)
1772 tree_code tc
= TREE_CODE (t
);
1774 return (handled_component_p (t
)
1775 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1778 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1779 corresponds to TARGET. */
1782 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1787 if (bb_dict
->length () <= (unsigned)source
)
1788 bb_dict
->safe_grow_cleared (source
+ 1);
1790 if ((*bb_dict
)[source
] == 0)
1792 (*bb_dict
)[source
] = target
;
1796 return (*bb_dict
)[source
] == target
;
1799 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1803 sem_variable::sem_variable (varpool_node
*node
, bitmap_obstack
*stack
)
1804 : sem_item (VAR
, node
, stack
)
1806 gcc_checking_assert (node
);
1807 gcc_checking_assert (get_node ());
1810 /* Fast equality function based on knowledge known in WPA. */
1813 sem_variable::equals_wpa (sem_item
*item
,
1814 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1816 gcc_assert (item
->type
== VAR
);
1818 if (node
->num_references () != item
->node
->num_references ())
1819 return return_false_with_msg ("different number of references");
1821 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1822 return return_false_with_msg ("TLS model");
1824 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1825 alignment out of all aliases. */
1827 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1828 return return_false_with_msg ("Virtual flag mismatch");
1830 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1831 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1832 || !operand_equal_p (DECL_SIZE (decl
),
1833 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1834 return return_false_with_msg ("size mismatch");
1836 /* Do not attempt to mix data from different user sections;
1837 we do not know what user intends with those. */
1838 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1839 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1840 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1841 return return_false_with_msg ("user section mismatch");
1843 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1844 return return_false_with_msg ("text section");
1846 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1847 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1849 item
->node
->iterate_reference (i
, ref2
);
1851 if (ref
->use
!= ref2
->use
)
1852 return return_false_with_msg ("reference use mismatch");
1854 if (!compare_symbol_references (ignored_nodes
,
1855 ref
->referred
, ref2
->referred
,
1856 ref
->address_matters_p ()))
1863 /* Returns true if the item equals to ITEM given as argument. */
1866 sem_variable::equals (sem_item
*item
,
1867 hash_map
<symtab_node
*, sem_item
*> &)
1869 gcc_assert (item
->type
== VAR
);
1872 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1873 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1874 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1875 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1877 /* As seen in PR ipa/65303 we have to compare variables types. */
1878 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1879 TREE_TYPE (item
->decl
)))
1880 return return_false_with_msg ("variables types are different");
1882 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1883 DECL_INITIAL (item
->node
->decl
));
1884 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1886 "Equals called for vars: %s:%s with result: %s\n\n",
1887 node
->dump_name (), item
->node
->dump_name (),
1888 ret
? "true" : "false");
1893 /* Compares trees T1 and T2 for semantic equality. */
1896 sem_variable::equals (tree t1
, tree t2
)
1899 return return_with_debug (t1
== t2
);
1902 tree_code tc1
= TREE_CODE (t1
);
1903 tree_code tc2
= TREE_CODE (t2
);
1906 return return_false_with_msg ("TREE_CODE mismatch");
1912 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1913 unsigned HOST_WIDE_INT idx
;
1915 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1916 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1917 return return_false_with_msg ("constructor type mismatch");
1919 if (typecode
== ARRAY_TYPE
)
1921 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1922 /* For arrays, check that the sizes all match. */
1923 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1925 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1926 return return_false_with_msg ("constructor array size mismatch");
1928 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1930 return return_false_with_msg ("constructor type incompatible");
1932 v1
= CONSTRUCTOR_ELTS (t1
);
1933 v2
= CONSTRUCTOR_ELTS (t2
);
1934 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1935 return return_false_with_msg ("constructor number of elts mismatch");
1937 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1939 constructor_elt
*c1
= &(*v1
)[idx
];
1940 constructor_elt
*c2
= &(*v2
)[idx
];
1942 /* Check that each value is the same... */
1943 if (!sem_variable::equals (c1
->value
, c2
->value
))
1945 /* ... and that they apply to the same fields! */
1946 if (!sem_variable::equals (c1
->index
, c2
->index
))
1953 tree x1
= TREE_OPERAND (t1
, 0);
1954 tree x2
= TREE_OPERAND (t2
, 0);
1955 tree y1
= TREE_OPERAND (t1
, 1);
1956 tree y2
= TREE_OPERAND (t2
, 1);
1958 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1959 return return_false ();
1961 /* Type of the offset on MEM_REF does not matter. */
1962 return return_with_debug (sem_variable::equals (x1
, x2
)
1963 && wi::to_offset (y1
)
1964 == wi::to_offset (y2
));
1969 tree op1
= TREE_OPERAND (t1
, 0);
1970 tree op2
= TREE_OPERAND (t2
, 0);
1971 return sem_variable::equals (op1
, op2
);
1973 /* References to other vars/decls are compared using ipa-ref. */
1976 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1978 return return_false_with_msg ("Declaration mismatch");
1980 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1981 need to process its VAR/FUNCTION references without relying on ipa-ref
1985 return return_false_with_msg ("Declaration mismatch");
1987 /* Integer constants are the same only if the same width of type. */
1988 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1989 return return_false_with_msg ("INTEGER_CST precision mismatch");
1990 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1991 return return_false_with_msg ("INTEGER_CST mode mismatch");
1992 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1994 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1995 return return_false_with_msg ("STRING_CST mode mismatch");
1996 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1997 return return_false_with_msg ("STRING_CST length mismatch");
1998 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1999 TREE_STRING_LENGTH (t1
)))
2000 return return_false_with_msg ("STRING_CST mismatch");
2003 /* Fixed constants are the same only if the same width of type. */
2004 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2005 return return_false_with_msg ("FIXED_CST precision mismatch");
2007 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2008 TREE_FIXED_CST (t2
)));
2010 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2011 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2013 /* Real constants are the same only if the same width of type. */
2014 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2015 return return_false_with_msg ("REAL_CST precision mismatch");
2016 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2017 &TREE_REAL_CST (t2
)));
2022 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2023 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2025 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2026 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2027 VECTOR_CST_ELT (t2
, i
)))
2033 case ARRAY_RANGE_REF
:
2035 tree x1
= TREE_OPERAND (t1
, 0);
2036 tree x2
= TREE_OPERAND (t2
, 0);
2037 tree y1
= TREE_OPERAND (t1
, 1);
2038 tree y2
= TREE_OPERAND (t2
, 1);
2040 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2042 if (!sem_variable::equals (array_ref_low_bound (t1
),
2043 array_ref_low_bound (t2
)))
2045 if (!sem_variable::equals (array_ref_element_size (t1
),
2046 array_ref_element_size (t2
)))
2052 case POINTER_PLUS_EXPR
:
2057 tree x1
= TREE_OPERAND (t1
, 0);
2058 tree x2
= TREE_OPERAND (t2
, 0);
2059 tree y1
= TREE_OPERAND (t1
, 1);
2060 tree y2
= TREE_OPERAND (t2
, 1);
2062 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2066 case VIEW_CONVERT_EXPR
:
2067 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2068 return return_false ();
2069 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2071 return return_false_with_msg ("ERROR_MARK");
2073 return return_false_with_msg ("Unknown TREE code reached");
2077 /* Parser function that visits a varpool NODE. */
2080 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2082 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2086 sem_variable
*v
= new sem_variable (node
, stack
);
2093 /* References independent hash function. */
2096 sem_variable::get_hash (void)
2101 /* All WPA streamed in symbols should have their hashes computed at compile
2102 time. At this point, the constructor may not be in memory at all.
2103 DECL_INITIAL (decl) would be error_mark_node in that case. */
2104 gcc_assert (!node
->lto_file_data
);
2105 tree ctor
= DECL_INITIAL (decl
);
2106 inchash::hash hstate
;
2108 hstate
.add_int (456346417);
2109 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2110 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2111 add_expr (ctor
, hstate
);
2112 set_hash (hstate
.end ());
2117 /* Set all points-to UIDs of aliases pointing to node N as UID. */
2120 set_alias_uids (symtab_node
*n
, int uid
)
2123 FOR_EACH_ALIAS (n
, ref
)
2126 fprintf (dump_file
, " Setting points-to UID of [%s] as %d\n",
2127 xstrdup_for_dump (ref
->referring
->asm_name ()), uid
);
2129 SET_DECL_PT_UID (ref
->referring
->decl
, uid
);
2130 set_alias_uids (ref
->referring
, uid
);
2134 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2138 sem_variable::merge (sem_item
*alias_item
)
2140 gcc_assert (alias_item
->type
== VAR
);
2142 if (!sem_item::target_supports_symbol_aliases_p ())
2145 fprintf (dump_file
, "Not unifying; "
2146 "Symbol aliases are not supported by target\n\n");
2150 if (DECL_EXTERNAL (alias_item
->decl
))
2153 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2157 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2159 varpool_node
*original
= get_node ();
2160 varpool_node
*alias
= alias_var
->get_node ();
2161 bool original_discardable
= false;
2163 bool alias_address_matters
= alias
->address_matters_p ();
2165 /* See if original is in a section that can be discarded if the main
2167 Also consider case where we have resolution info and we know that
2168 original's definition is not going to be used. In this case we can not
2169 create alias to original. */
2170 if (original
->can_be_discarded_p ()
2171 || (node
->resolution
!= LDPR_UNKNOWN
2172 && !decl_binds_to_current_def_p (node
->decl
)))
2173 original_discardable
= true;
2175 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2177 /* Constant pool machinery is not quite ready for aliases.
2178 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2179 For LTO merging does not happen that is an important missing feature.
2180 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2181 flag is dropped and non-local symbol name is assigned. */
2182 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2183 || DECL_IN_CONSTANT_POOL (original
->decl
))
2187 "Not unifying; constant pool variables.\n\n");
2191 /* Do not attempt to mix functions from different user sections;
2192 we do not know what user intends with those. */
2193 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2194 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2195 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2200 "original and alias are in different sections.\n\n");
2204 /* We can not merge if address comparsion metters. */
2205 if (alias_address_matters
&& flag_merge_constants
< 2)
2209 "Not unifying; address of original may be compared.\n\n");
2213 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2216 fprintf (dump_file
, "Not unifying; "
2217 "original and alias have incompatible alignments\n\n");
2222 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2225 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2226 "across comdat group boundary\n\n");
2231 if (original_discardable
)
2234 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2235 "target is discardable\n\n");
2241 gcc_assert (!original
->alias
);
2242 gcc_assert (!alias
->alias
);
2244 alias
->analyzed
= false;
2246 DECL_INITIAL (alias
->decl
) = NULL
;
2247 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2249 alias
->need_bounds_init
= false;
2250 alias
->remove_all_references ();
2251 if (TREE_ADDRESSABLE (alias
->decl
))
2252 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2254 varpool_node::create_alias (alias_var
->decl
, decl
);
2255 alias
->resolve_alias (original
);
2258 fprintf (dump_file
, "Unified; Variable alias has been created.\n");
2260 set_alias_uids (original
, DECL_UID (original
->decl
));
2265 /* Dump symbol to FILE. */
2268 sem_variable::dump_to_file (FILE *file
)
2272 print_node (file
, "", decl
, 0);
2273 fprintf (file
, "\n\n");
2276 unsigned int sem_item_optimizer::class_id
= 0;
2278 sem_item_optimizer::sem_item_optimizer ()
2279 : worklist (0), m_classes (0), m_classes_count (0), m_cgraph_node_hooks (NULL
),
2280 m_varpool_node_hooks (NULL
)
2283 bitmap_obstack_initialize (&m_bmstack
);
2286 sem_item_optimizer::~sem_item_optimizer ()
2288 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2292 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2293 it
!= m_classes
.end (); ++it
)
2295 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2296 delete (*it
)->classes
[i
];
2298 (*it
)->classes
.release ();
2304 bitmap_obstack_release (&m_bmstack
);
2307 /* Write IPA ICF summary for symbols. */
2310 sem_item_optimizer::write_summary (void)
2312 unsigned int count
= 0;
2314 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2315 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2318 /* Calculate number of symbols to be serialized. */
2319 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2321 lsei_next_in_partition (&lsei
))
2323 symtab_node
*node
= lsei_node (lsei
);
2325 if (m_symtab_node_map
.get (node
))
2329 streamer_write_uhwi (ob
, count
);
2331 /* Process all of the symbols. */
2332 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2334 lsei_next_in_partition (&lsei
))
2336 symtab_node
*node
= lsei_node (lsei
);
2338 sem_item
**item
= m_symtab_node_map
.get (node
);
2342 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2343 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2345 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2349 streamer_write_char_stream (ob
->main_stream
, 0);
2350 produce_asm (ob
, NULL
);
2351 destroy_output_block (ob
);
2354 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2355 contains LEN bytes. */
2358 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2359 const char *data
, size_t len
)
2361 const lto_function_header
*header
2362 = (const lto_function_header
*) data
;
2363 const int cfg_offset
= sizeof (lto_function_header
);
2364 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2365 const int string_offset
= main_offset
+ header
->main_size
;
2370 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2371 header
->main_size
, file_data
->mode_table
);
2374 = lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2375 header
->string_size
, vNULL
);
2377 count
= streamer_read_uhwi (&ib_main
);
2379 for (i
= 0; i
< count
; i
++)
2383 lto_symtab_encoder_t encoder
;
2385 index
= streamer_read_uhwi (&ib_main
);
2386 encoder
= file_data
->symtab_node_encoder
;
2387 node
= lto_symtab_encoder_deref (encoder
, index
);
2389 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2391 gcc_assert (node
->definition
);
2394 fprintf (dump_file
, "Symbol added: %s (tree: %p)\n",
2395 node
->dump_asm_name (), (void *) node
->decl
);
2397 if (is_a
<cgraph_node
*> (node
))
2399 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2401 sem_function
*fn
= new sem_function (cnode
, &m_bmstack
);
2402 fn
->set_hash (hash
);
2403 m_items
.safe_push (fn
);
2407 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2409 sem_variable
*var
= new sem_variable (vnode
, &m_bmstack
);
2410 var
->set_hash (hash
);
2411 m_items
.safe_push (var
);
2415 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2417 lto_data_in_delete (data_in
);
2420 /* Read IPA ICF summary for symbols. */
2423 sem_item_optimizer::read_summary (void)
2425 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2426 lto_file_decl_data
*file_data
;
2429 while ((file_data
= file_data_vec
[j
++]))
2432 const char *data
= lto_get_section_data (file_data
,
2433 LTO_section_ipa_icf
, NULL
, &len
);
2436 read_section (file_data
, data
, len
);
2440 /* Register callgraph and varpool hooks. */
2443 sem_item_optimizer::register_hooks (void)
2445 if (!m_cgraph_node_hooks
)
2446 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2447 (&sem_item_optimizer::cgraph_removal_hook
, this);
2449 if (!m_varpool_node_hooks
)
2450 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2451 (&sem_item_optimizer::varpool_removal_hook
, this);
2454 /* Unregister callgraph and varpool hooks. */
2457 sem_item_optimizer::unregister_hooks (void)
2459 if (m_cgraph_node_hooks
)
2460 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2462 if (m_varpool_node_hooks
)
2463 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2466 /* Adds a CLS to hashtable associated by hash value. */
2469 sem_item_optimizer::add_class (congruence_class
*cls
)
2471 gcc_assert (cls
->members
.length ());
2473 congruence_class_group
*group
2474 = get_group_by_hash (cls
->members
[0]->get_hash (),
2475 cls
->members
[0]->type
);
2476 group
->classes
.safe_push (cls
);
2479 /* Gets a congruence class group based on given HASH value and TYPE. */
2481 congruence_class_group
*
2482 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2484 congruence_class_group
*item
= XNEW (congruence_class_group
);
2488 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2494 item
->classes
.create (1);
2501 /* Callgraph removal hook called for a NODE with a custom DATA. */
2504 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2506 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2507 optimizer
->remove_symtab_node (node
);
2510 /* Varpool removal hook called for a NODE with a custom DATA. */
2513 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2515 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2516 optimizer
->remove_symtab_node (node
);
2519 /* Remove symtab NODE triggered by symtab removal hooks. */
2522 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2524 gcc_assert (!m_classes
.elements ());
2526 m_removed_items_set
.add (node
);
2530 sem_item_optimizer::remove_item (sem_item
*item
)
2532 if (m_symtab_node_map
.get (item
->node
))
2533 m_symtab_node_map
.remove (item
->node
);
2537 /* Removes all callgraph and varpool nodes that are marked by symtab
2541 sem_item_optimizer::filter_removed_items (void)
2543 auto_vec
<sem_item
*> filtered
;
2545 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2547 sem_item
*item
= m_items
[i
];
2549 if (m_removed_items_set
.contains (item
->node
))
2555 if (item
->type
== FUNC
)
2557 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2559 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2562 filtered
.safe_push (item
);
2566 if (!flag_ipa_icf_variables
)
2570 /* Filter out non-readonly variables. */
2571 tree decl
= item
->decl
;
2572 if (TREE_READONLY (decl
))
2573 filtered
.safe_push (item
);
2580 /* Clean-up of released semantic items. */
2583 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2584 m_items
.safe_push (filtered
[i
]);
2587 /* Optimizer entry point which returns true in case it processes
2588 a merge operation. True is returned if there's a merge operation
2592 sem_item_optimizer::execute (void)
2594 filter_removed_items ();
2595 unregister_hooks ();
2598 update_hash_by_addr_refs ();
2599 build_hash_based_classes ();
2602 fprintf (dump_file
, "Dump after hash based groups\n");
2603 dump_cong_classes ();
2605 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2606 m_items
[i
]->init_wpa ();
2608 subdivide_classes_by_equality (true);
2611 fprintf (dump_file
, "Dump after WPA based types groups\n");
2613 dump_cong_classes ();
2615 process_cong_reduction ();
2616 checking_verify_classes ();
2619 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2621 dump_cong_classes ();
2623 parse_nonsingleton_classes ();
2624 subdivide_classes_by_equality ();
2627 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2629 dump_cong_classes ();
2631 unsigned int prev_class_count
= m_classes_count
;
2633 process_cong_reduction ();
2634 dump_cong_classes ();
2635 checking_verify_classes ();
2636 bool merged_p
= merge_classes (prev_class_count
);
2638 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2639 symtab
->dump (dump_file
);
2644 /* Function responsible for visiting all potential functions and
2645 read-only variables that can be merged. */
2648 sem_item_optimizer::parse_funcs_and_vars (void)
2652 if (flag_ipa_icf_functions
)
2653 FOR_EACH_DEFINED_FUNCTION (cnode
)
2655 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2658 m_items
.safe_push (f
);
2659 m_symtab_node_map
.put (cnode
, f
);
2662 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2664 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2665 f
->dump_to_file (dump_file
);
2668 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2671 varpool_node
*vnode
;
2673 if (flag_ipa_icf_variables
)
2674 FOR_EACH_DEFINED_VARIABLE (vnode
)
2676 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2680 m_items
.safe_push (v
);
2681 m_symtab_node_map
.put (vnode
, v
);
2686 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2689 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2691 item
->index_in_class
= cls
->members
.length ();
2692 cls
->members
.safe_push (item
);
2696 /* For each semantic item, append hash values of references. */
2699 sem_item_optimizer::update_hash_by_addr_refs ()
2701 /* First, append to hash sensitive references and class type if it need to
2702 be matched for ODR. */
2703 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2705 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2706 if (m_items
[i
]->type
== FUNC
)
2708 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2709 && contains_polymorphic_type_p
2710 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2711 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2712 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2713 && static_cast<sem_function
*> (m_items
[i
])
2714 ->compare_polymorphic_p ())))
2717 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2718 inchash::hash
hstate (m_items
[i
]->get_hash ());
2720 if (TYPE_NAME (class_type
)
2721 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2723 (IDENTIFIER_HASH_VALUE
2724 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2726 m_items
[i
]->set_hash (hstate
.end ());
2731 /* Once all symbols have enhanced hash value, we can append
2732 hash values of symbols that are seen by IPA ICF and are
2733 references by a semantic item. Newly computed values
2734 are saved to global_hash member variable. */
2735 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2736 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2738 /* Global hash value replace current hash values. */
2739 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2740 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2743 /* Congruence classes are built by hash value. */
2746 sem_item_optimizer::build_hash_based_classes (void)
2748 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2750 sem_item
*item
= m_items
[i
];
2752 congruence_class_group
*group
2753 = get_group_by_hash (item
->get_hash (), item
->type
);
2755 if (!group
->classes
.length ())
2758 group
->classes
.safe_push (new congruence_class (class_id
++));
2761 add_item_to_class (group
->classes
[0], item
);
2765 /* Build references according to call graph. */
2768 sem_item_optimizer::build_graph (void)
2770 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2772 sem_item
*item
= m_items
[i
];
2773 m_symtab_node_map
.put (item
->node
, item
);
2775 /* Initialize hash values if we are not in LTO mode. */
2780 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2782 sem_item
*item
= m_items
[i
];
2784 if (item
->type
== FUNC
)
2786 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2788 cgraph_edge
*e
= cnode
->callees
;
2791 sem_item
**slot
= m_symtab_node_map
.get
2792 (e
->callee
->ultimate_alias_target ());
2794 item
->add_reference (*slot
);
2800 ipa_ref
*ref
= NULL
;
2801 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2803 sem_item
**slot
= m_symtab_node_map
.get
2804 (ref
->referred
->ultimate_alias_target ());
2806 item
->add_reference (*slot
);
2811 /* Semantic items in classes having more than one element and initialized.
2812 In case of WPA, we load function body. */
2815 sem_item_optimizer::parse_nonsingleton_classes (void)
2817 unsigned int init_called_count
= 0;
2819 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2820 if (m_items
[i
]->cls
->members
.length () > 1)
2822 m_items
[i
]->init ();
2823 init_called_count
++;
2827 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n",
2829 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length ()
2833 /* Equality function for semantic items is used to subdivide existing
2834 classes. If IN_WPA, fast equality function is invoked. */
2837 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2839 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2840 it
!= m_classes
.end (); ++it
)
2842 unsigned int class_count
= (*it
)->classes
.length ();
2844 for (unsigned i
= 0; i
< class_count
; i
++)
2846 congruence_class
*c
= (*it
)->classes
[i
];
2848 if (c
->members
.length() > 1)
2850 auto_vec
<sem_item
*> new_vector
;
2852 sem_item
*first
= c
->members
[0];
2853 new_vector
.safe_push (first
);
2855 unsigned class_split_first
= (*it
)->classes
.length ();
2857 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2859 sem_item
*item
= c
->members
[j
];
2862 = in_wpa
? first
->equals_wpa (item
, m_symtab_node_map
)
2863 : first
->equals (item
, m_symtab_node_map
);
2866 new_vector
.safe_push (item
);
2869 bool integrated
= false;
2871 for (unsigned k
= class_split_first
;
2872 k
< (*it
)->classes
.length (); k
++)
2874 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2876 = in_wpa
? x
->equals_wpa (item
, m_symtab_node_map
)
2877 : x
->equals (item
, m_symtab_node_map
);
2882 add_item_to_class ((*it
)->classes
[k
], item
);
2891 = new congruence_class (class_id
++);
2893 add_item_to_class (c
, item
);
2895 (*it
)->classes
.safe_push (c
);
2900 // We replace newly created new_vector for the class we've just
2902 c
->members
.release ();
2903 c
->members
.create (new_vector
.length ());
2905 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2906 add_item_to_class (c
, new_vector
[j
]);
2911 checking_verify_classes ();
2914 /* Subdivide classes by address references that members of the class
2915 reference. Example can be a pair of functions that have an address
2916 taken from a function. If these addresses are different the class
2920 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2922 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2924 unsigned newly_created_classes
= 0;
2926 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
2927 it
!= m_classes
.end (); ++it
)
2929 unsigned int class_count
= (*it
)->classes
.length ();
2930 auto_vec
<congruence_class
*> new_classes
;
2932 for (unsigned i
= 0; i
< class_count
; i
++)
2934 congruence_class
*c
= (*it
)->classes
[i
];
2936 if (c
->members
.length() > 1)
2938 subdivide_hash_map split_map
;
2940 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2942 sem_item
*source_node
= c
->members
[j
];
2944 symbol_compare_collection
*collection
2945 = new symbol_compare_collection (source_node
->node
);
2948 vec
<sem_item
*> *slot
2949 = &split_map
.get_or_insert (collection
, &existed
);
2950 gcc_checking_assert (slot
);
2952 slot
->safe_push (source_node
);
2958 /* If the map contains more than one key, we have to split
2959 the map appropriately. */
2960 if (split_map
.elements () != 1)
2962 bool first_class
= true;
2964 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2965 it2
!= split_map
.end (); ++it2
)
2967 congruence_class
*new_cls
;
2968 new_cls
= new congruence_class (class_id
++);
2970 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2971 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2973 worklist_push (new_cls
);
2974 newly_created_classes
++;
2978 (*it
)->classes
[i
] = new_cls
;
2979 first_class
= false;
2983 new_classes
.safe_push (new_cls
);
2989 /* Release memory. */
2990 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2991 it2
!= split_map
.end (); ++it2
)
2993 delete (*it2
).first
;
2994 (*it2
).second
.release ();
2999 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
3000 (*it
)->classes
.safe_push (new_classes
[i
]);
3003 return newly_created_classes
;
3006 /* Verify congruence classes, if checking is enabled. */
3009 sem_item_optimizer::checking_verify_classes (void)
3015 /* Verify congruence classes. */
3018 sem_item_optimizer::verify_classes (void)
3020 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3021 it
!= m_classes
.end (); ++it
)
3023 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3025 congruence_class
*cls
= (*it
)->classes
[i
];
3028 gcc_assert (cls
->members
.length () > 0);
3030 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3032 sem_item
*item
= cls
->members
[j
];
3035 gcc_assert (item
->cls
== cls
);
3037 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3039 sem_usage_pair
*usage
= item
->usages
[k
];
3040 gcc_assert (usage
->item
->index_in_class
3041 < usage
->item
->cls
->members
.length ());
3048 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3049 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3050 but unused argument. */
3053 sem_item_optimizer::release_split_map (congruence_class
* const &,
3054 bitmap
const &b
, traverse_split_pair
*)
3063 /* Process split operation for a class given as pointer CLS_PTR,
3064 where bitmap B splits congruence class members. DATA is used
3065 as argument of split pair. */
3068 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3070 traverse_split_pair
*pair
)
3072 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3073 const congruence_class
*splitter_cls
= pair
->cls
;
3075 /* If counted bits are greater than zero and less than the number of members
3076 a group will be splitted. */
3077 unsigned popcount
= bitmap_count_bits (b
);
3079 if (popcount
> 0 && popcount
< cls
->members
.length ())
3081 auto_vec
<congruence_class
*, 2> newclasses
;
3082 newclasses
.quick_push (new congruence_class (class_id
++));
3083 newclasses
.quick_push (new congruence_class (class_id
++));
3085 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3087 int target
= bitmap_bit_p (b
, i
);
3088 congruence_class
*tc
= newclasses
[target
];
3090 add_item_to_class (tc
, cls
->members
[i
]);
3095 for (unsigned int i
= 0; i
< 2; i
++)
3096 gcc_assert (newclasses
[i
]->members
.length ());
3099 if (splitter_cls
== cls
)
3100 optimizer
->splitter_class_removed
= true;
3102 /* Remove old class from worklist if presented. */
3103 bool in_worklist
= cls
->in_worklist
;
3106 cls
->in_worklist
= false;
3108 congruence_class_group g
;
3109 g
.hash
= cls
->members
[0]->get_hash ();
3110 g
.type
= cls
->members
[0]->type
;
3112 congruence_class_group
*slot
= optimizer
->m_classes
.find (&g
);
3114 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3115 if (slot
->classes
[i
] == cls
)
3117 slot
->classes
.ordered_remove (i
);
3121 /* New class will be inserted and integrated to work list. */
3122 for (unsigned int i
= 0; i
< 2; i
++)
3123 optimizer
->add_class (newclasses
[i
]);
3125 /* Two classes replace one, so that increment just by one. */
3126 optimizer
->m_classes_count
++;
3128 /* If OLD class was presented in the worklist, we remove the class
3129 and replace it will both newly created classes. */
3131 for (unsigned int i
= 0; i
< 2; i
++)
3132 optimizer
->worklist_push (newclasses
[i
]);
3133 else /* Just smaller class is inserted. */
3135 unsigned int smaller_index
3136 = (newclasses
[0]->members
.length ()
3137 < newclasses
[1]->members
.length ()
3139 optimizer
->worklist_push (newclasses
[smaller_index
]);
3142 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3144 fprintf (dump_file
, " congruence class splitted:\n");
3145 cls
->dump (dump_file
, 4);
3147 fprintf (dump_file
, " newly created groups:\n");
3148 for (unsigned int i
= 0; i
< 2; i
++)
3149 newclasses
[i
]->dump (dump_file
, 4);
3152 /* Release class if not presented in work list. */
3161 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3162 Bitmap stack BMSTACK is used for bitmap allocation. */
3165 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3168 hash_map
<congruence_class
*, bitmap
> split_map
;
3170 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3172 sem_item
*item
= cls
->members
[i
];
3174 /* Iterate all usages that have INDEX as usage of the item. */
3175 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3177 sem_usage_pair
*usage
= item
->usages
[j
];
3179 if (usage
->index
!= index
)
3182 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3187 b
= BITMAP_ALLOC (&m_bmstack
);
3188 split_map
.put (usage
->item
->cls
, b
);
3193 gcc_checking_assert (usage
->item
->cls
);
3194 gcc_checking_assert (usage
->item
->index_in_class
3195 < usage
->item
->cls
->members
.length ());
3197 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3201 traverse_split_pair pair
;
3202 pair
.optimizer
= this;
3205 splitter_class_removed
= false;
3206 split_map
.traverse
<traverse_split_pair
*,
3207 sem_item_optimizer::traverse_congruence_split
> (&pair
);
3209 /* Bitmap clean-up. */
3210 split_map
.traverse
<traverse_split_pair
*,
3211 sem_item_optimizer::release_split_map
> (NULL
);
3214 /* Every usage of a congruence class CLS is a candidate that can split the
3215 collection of classes. Bitmap stack BMSTACK is used for bitmap
3219 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3224 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3226 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3227 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3229 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3231 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3232 fprintf (dump_file
, " processing congruence step for class: %u, "
3233 "index: %u\n", cls
->id
, i
);
3235 do_congruence_step_for_index (cls
, i
);
3237 if (splitter_class_removed
)
3241 BITMAP_FREE (usage
);
3244 /* Adds a newly created congruence class CLS to worklist. */
3247 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3249 /* Return if the class CLS is already presented in work list. */
3250 if (cls
->in_worklist
)
3253 cls
->in_worklist
= true;
3254 worklist
.push_back (cls
);
3257 /* Pops a class from worklist. */
3260 sem_item_optimizer::worklist_pop (void)
3262 congruence_class
*cls
;
3264 while (!worklist
.empty ())
3266 cls
= worklist
.front ();
3267 worklist
.pop_front ();
3268 if (cls
->in_worklist
)
3270 cls
->in_worklist
= false;
3276 /* Work list item was already intended to be removed.
3277 The only reason for doing it is to split a class.
3278 Thus, the class CLS is deleted. */
3286 /* Iterative congruence reduction function. */
3289 sem_item_optimizer::process_cong_reduction (void)
3291 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3292 it
!= m_classes
.end (); ++it
)
3293 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3294 if ((*it
)->classes
[i
]->is_class_used ())
3295 worklist_push ((*it
)->classes
[i
]);
3298 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3299 (unsigned long) worklist
.size ());
3301 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3302 fprintf (dump_file
, "Congruence class reduction\n");
3304 congruence_class
*cls
;
3306 /* Process complete congruence reduction. */
3307 while ((cls
= worklist_pop ()) != NULL
)
3308 do_congruence_step (cls
);
3310 /* Subdivide newly created classes according to references. */
3311 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3314 fprintf (dump_file
, "Address reference subdivision created: %u "
3315 "new classes.\n", new_classes
);
3318 /* Debug function prints all informations about congruence classes. */
3321 sem_item_optimizer::dump_cong_classes (void)
3327 "Congruence classes: %u (unique hash values: %lu), with total: "
3328 "%u items\n", m_classes_count
,
3329 (unsigned long) m_classes
.elements (), m_items
.length ());
3331 /* Histogram calculation. */
3332 unsigned int max_index
= 0;
3333 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3335 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3336 it
!= m_classes
.end (); ++it
)
3337 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3339 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3347 "Class size histogram [num of members]: number of classe number "
3350 for (unsigned int i
= 0; i
<= max_index
; i
++)
3352 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3354 fprintf (dump_file
, "\n\n");
3356 if (dump_flags
& TDF_DETAILS
)
3357 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3358 it
!= m_classes
.end (); ++it
)
3360 fprintf (dump_file
, " group: with %u classes:\n",
3361 (*it
)->classes
.length ());
3363 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3365 (*it
)->classes
[i
]->dump (dump_file
, 4);
3367 if (i
< (*it
)->classes
.length () - 1)
3368 fprintf (dump_file
, " ");
3375 /* Sort pair of sem_items A and B by DECL_UID. */
3378 sort_sem_items_by_decl_uid (const void *a
, const void *b
)
3380 const sem_item
*i1
= *(const sem_item
* const *)a
;
3381 const sem_item
*i2
= *(const sem_item
* const *)b
;
3383 int uid1
= DECL_UID (i1
->decl
);
3384 int uid2
= DECL_UID (i2
->decl
);
3388 else if (uid1
> uid2
)
3394 /* Sort pair of congruence_classes A and B by DECL_UID of the first member. */
3397 sort_congruence_classes_by_decl_uid (const void *a
, const void *b
)
3399 const congruence_class
*c1
= *(const congruence_class
* const *)a
;
3400 const congruence_class
*c2
= *(const congruence_class
* const *)b
;
3402 int uid1
= DECL_UID (c1
->members
[0]->decl
);
3403 int uid2
= DECL_UID (c2
->members
[0]->decl
);
3407 else if (uid1
> uid2
)
3413 /* Sort pair of congruence_class_groups A and B by
3414 DECL_UID of the first member of a first group. */
3417 sort_congruence_class_groups_by_decl_uid (const void *a
, const void *b
)
3419 const congruence_class_group
*g1
3420 = *(const congruence_class_group
* const *)a
;
3421 const congruence_class_group
*g2
3422 = *(const congruence_class_group
* const *)b
;
3424 int uid1
= DECL_UID (g1
->classes
[0]->members
[0]->decl
);
3425 int uid2
= DECL_UID (g2
->classes
[0]->members
[0]->decl
);
3429 else if (uid1
> uid2
)
3435 /* After reduction is done, we can declare all items in a group
3436 to be equal. PREV_CLASS_COUNT is start number of classes
3437 before reduction. True is returned if there's a merge operation
3441 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3443 unsigned int item_count
= m_items
.length ();
3444 unsigned int class_count
= m_classes_count
;
3445 unsigned int equal_items
= item_count
- class_count
;
3447 unsigned int non_singular_classes_count
= 0;
3448 unsigned int non_singular_classes_sum
= 0;
3450 bool merged_p
= false;
3453 Sort functions in congruence classes by DECL_UID and do the same
3454 for the classes to not to break -fcompare-debug. */
3456 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3457 it
!= m_classes
.end (); ++it
)
3459 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3461 congruence_class
*c
= (*it
)->classes
[i
];
3462 c
->members
.qsort (sort_sem_items_by_decl_uid
);
3465 (*it
)->classes
.qsort (sort_congruence_classes_by_decl_uid
);
3468 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3469 it
!= m_classes
.end (); ++it
)
3470 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3472 congruence_class
*c
= (*it
)->classes
[i
];
3473 if (c
->members
.length () > 1)
3475 non_singular_classes_count
++;
3476 non_singular_classes_sum
+= c
->members
.length ();
3480 auto_vec
<congruence_class_group
*> classes (m_classes
.elements ());
3481 for (hash_table
<congruence_class_hash
>::iterator it
= m_classes
.begin ();
3482 it
!= m_classes
.end (); ++it
)
3483 classes
.quick_push (*it
);
3485 classes
.qsort (sort_congruence_class_groups_by_decl_uid
);
3489 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3490 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3491 prev_class_count
, class_count
);
3492 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3493 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3494 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3495 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3496 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3497 non_singular_classes_count
: 0.0f
,
3498 non_singular_classes_count
);
3499 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3500 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3501 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3505 congruence_class_group
*it
;
3506 FOR_EACH_VEC_ELT (classes
, l
, it
)
3507 for (unsigned int i
= 0; i
< it
->classes
.length (); i
++)
3509 congruence_class
*c
= it
->classes
[i
];
3511 if (c
->members
.length () == 1)
3514 sem_item
*source
= c
->members
[0];
3516 if (DECL_NAME (source
->decl
)
3517 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3518 /* If merge via wrappers, picking main as the target can be
3520 source
= c
->members
[1];
3522 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3524 sem_item
*alias
= c
->members
[j
];
3526 if (alias
== source
)
3531 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3532 xstrdup_for_dump (source
->node
->name ()),
3533 xstrdup_for_dump (alias
->node
->name ()));
3534 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3535 xstrdup_for_dump (source
->node
->asm_name ()),
3536 xstrdup_for_dump (alias
->node
->asm_name ()));
3539 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3543 "Merge operation is skipped due to no_icf "
3549 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3551 source
->dump_to_file (dump_file
);
3552 alias
->dump_to_file (dump_file
);
3555 if (dbg_cnt (merged_ipa_icf
))
3556 merged_p
|= source
->merge (alias
);
3563 /* Dump function prints all class members to a FILE with an INDENT. */
3566 congruence_class::dump (FILE *file
, unsigned int indent
) const
3568 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3569 id
, members
[0]->get_hash (), members
.length ());
3571 FPUTS_SPACES (file
, indent
+ 2, "");
3572 for (unsigned i
= 0; i
< members
.length (); i
++)
3573 fprintf (file
, "%s ", members
[i
]->node
->dump_asm_name ());
3575 fprintf (file
, "\n");
3578 /* Returns true if there's a member that is used from another group. */
3581 congruence_class::is_class_used (void)
3583 for (unsigned int i
= 0; i
< members
.length (); i
++)
3584 if (members
[i
]->usages
.length ())
3590 /* Generate pass summary for IPA ICF pass. */
3593 ipa_icf_generate_summary (void)
3596 optimizer
= new sem_item_optimizer ();
3598 optimizer
->register_hooks ();
3599 optimizer
->parse_funcs_and_vars ();
3602 /* Write pass summary for IPA ICF pass. */
3605 ipa_icf_write_summary (void)
3607 gcc_assert (optimizer
);
3609 optimizer
->write_summary ();
3612 /* Read pass summary for IPA ICF pass. */
3615 ipa_icf_read_summary (void)
3618 optimizer
= new sem_item_optimizer ();
3620 optimizer
->read_summary ();
3621 optimizer
->register_hooks ();
3624 /* Semantic equality exection function. */
3627 ipa_icf_driver (void)
3629 gcc_assert (optimizer
);
3631 bool merged_p
= optimizer
->execute ();
3636 return merged_p
? TODO_remove_functions
: 0;
3639 const pass_data pass_data_ipa_icf
=
3641 IPA_PASS
, /* type */
3643 OPTGROUP_IPA
, /* optinfo_flags */
3644 TV_IPA_ICF
, /* tv_id */
3645 0, /* properties_required */
3646 0, /* properties_provided */
3647 0, /* properties_destroyed */
3648 0, /* todo_flags_start */
3649 0, /* todo_flags_finish */
3652 class pass_ipa_icf
: public ipa_opt_pass_d
3655 pass_ipa_icf (gcc::context
*ctxt
)
3656 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3657 ipa_icf_generate_summary
, /* generate_summary */
3658 ipa_icf_write_summary
, /* write_summary */
3659 ipa_icf_read_summary
, /* read_summary */
3661 write_optimization_summary */
3663 read_optimization_summary */
3664 NULL
, /* stmt_fixup */
3665 0, /* function_transform_todo_flags_start */
3666 NULL
, /* function_transform */
3667 NULL
) /* variable_transform */
3670 /* opt_pass methods: */
3671 virtual bool gate (function
*)
3673 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3676 virtual unsigned int execute (function
*)
3678 return ipa_icf_driver();
3680 }; // class pass_ipa_icf
3682 } // ipa_icf namespace
3685 make_pass_ipa_icf (gcc::context
*ctxt
)
3687 return new ipa_icf::pass_ipa_icf (ctxt
);