1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2016 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-inline.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 /* Semantic item constructor for a node of _TYPE, where STACK is used
140 for bitmap memory allocation. */
142 sem_item::sem_item (sem_item_type _type
,
143 bitmap_obstack
*stack
): type (_type
), m_hash (0)
148 /* Semantic item constructor for a node of _TYPE, where STACK is used
149 for bitmap memory allocation. The item is based on symtab node _NODE
150 with computed _HASH. */
152 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
153 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
154 node (_node
), m_hash (_hash
)
160 /* Add reference to a semantic TARGET. */
163 sem_item::add_reference (sem_item
*target
)
165 refs
.safe_push (target
);
166 unsigned index
= refs
.length ();
167 target
->usages
.safe_push (new sem_usage_pair(this, index
));
168 bitmap_set_bit (target
->usage_index_bitmap
, index
);
169 refs_set
.add (target
->node
);
172 /* Initialize internal data structures. Bitmap STACK is used for
173 bitmap memory allocation process. */
176 sem_item::setup (bitmap_obstack
*stack
)
178 gcc_checking_assert (node
);
181 tree_refs
.create (0);
183 usage_index_bitmap
= BITMAP_ALLOC (stack
);
186 sem_item::~sem_item ()
188 for (unsigned i
= 0; i
< usages
.length (); i
++)
192 tree_refs
.release ();
195 BITMAP_FREE (usage_index_bitmap
);
198 /* Dump function for debugging purpose. */
201 sem_item::dump (void)
205 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
206 node
->name(), node
->order
, (void *) node
->decl
);
207 fprintf (dump_file
, " hash: %u\n", get_hash ());
208 fprintf (dump_file
, " references: ");
210 for (unsigned i
= 0; i
< refs
.length (); i
++)
211 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
212 i
< refs
.length() - 1 ? "," : "");
214 fprintf (dump_file
, "\n");
218 /* Return true if target supports alias symbols. */
221 sem_item::target_supports_symbol_aliases_p (void)
223 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
230 void sem_item::set_hash (hashval_t hash
)
235 /* Semantic function constructor that uses STACK as bitmap memory stack. */
237 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
238 m_checker (NULL
), m_compared_func (NULL
)
241 bb_sorted
.create (0);
244 /* Constructor based on callgraph node _NODE with computed hash _HASH.
245 Bitmap STACK is used for memory allocation. */
246 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
247 bitmap_obstack
*stack
):
248 sem_item (FUNC
, node
, hash
, stack
),
249 m_checker (NULL
), m_compared_func (NULL
)
252 bb_sorted
.create (0);
255 sem_function::~sem_function ()
257 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
258 delete (bb_sorted
[i
]);
261 bb_sorted
.release ();
264 /* Calculates hash value based on a BASIC_BLOCK. */
267 sem_function::get_bb_hash (const sem_bb
*basic_block
)
269 inchash::hash hstate
;
271 hstate
.add_int (basic_block
->nondbg_stmt_count
);
272 hstate
.add_int (basic_block
->edge_count
);
274 return hstate
.end ();
277 /* References independent hash function. */
280 sem_function::get_hash (void)
284 inchash::hash hstate
;
285 hstate
.add_int (177454); /* Random number for function type. */
287 hstate
.add_int (arg_count
);
288 hstate
.add_int (cfg_checksum
);
289 hstate
.add_int (gcode_hash
);
291 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
292 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
294 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
295 hstate
.add_int (bb_sizes
[i
]);
297 /* Add common features of declaration itself. */
298 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
300 (cl_target_option_hash
301 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
302 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
303 (cl_optimization_hash
304 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
305 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
306 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
308 set_hash (hstate
.end ());
314 /* Return ture if A1 and A2 represent equivalent function attribute lists.
315 Based on comp_type_attributes. */
318 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
323 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
325 const struct attribute_spec
*as
;
328 as
= lookup_attribute_spec (get_attribute_name (a
));
329 /* TODO: We can introduce as->affects_decl_identity
330 and as->affects_decl_reference_identity if attribute mismatch
331 gets a common reason to give up on merging. It may not be worth
333 For example returns_nonnull affects only references, while
334 optimize attribute can be ignored because it is already lowered
335 into flags representation and compared separately. */
339 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
340 if (!attr
|| !attribute_value_equal (a
, attr
))
345 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
347 const struct attribute_spec
*as
;
349 as
= lookup_attribute_spec (get_attribute_name (a
));
353 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
355 /* We don't need to compare trees again, as we did this
356 already in first loop. */
361 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
365 /* Compare properties of symbols N1 and N2 that does not affect semantics of
366 symbol itself but affects semantics of its references from USED_BY (which
367 may be NULL if it is unknown). If comparsion is false, symbols
368 can still be merged but any symbols referring them can't.
370 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
372 TODO: We can also split attributes to those that determine codegen of
373 a function body/variable constructor itself and those that are used when
377 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
382 if (is_a
<cgraph_node
*> (n1
))
384 /* Inline properties matters: we do now want to merge uses of inline
385 function to uses of normal function because inline hint would be lost.
386 We however can merge inline function to noinline because the alias
387 will keep its DECL_DECLARED_INLINE flag.
389 Also ignore inline flag when optimizing for size or when function
390 is known to not be inlinable.
392 TODO: the optimize_size checks can also be assumed to be true if
393 unit has no !optimize_size functions. */
395 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
396 || !opt_for_fn (used_by
->decl
, optimize_size
))
397 && !opt_for_fn (n1
->decl
, optimize_size
)
398 && n1
->get_availability () > AVAIL_INTERPOSABLE
399 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
401 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
402 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
403 return return_false_with_msg
404 ("DECL_DISREGARD_INLINE_LIMITS are different");
406 if (DECL_DECLARED_INLINE_P (n1
->decl
)
407 != DECL_DECLARED_INLINE_P (n2
->decl
))
408 return return_false_with_msg ("inline attributes are different");
411 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
412 != DECL_IS_OPERATOR_NEW (n2
->decl
))
413 return return_false_with_msg ("operator new flags are different");
416 /* Merging two definitions with a reference to equivalent vtables, but
417 belonging to a different type may result in ipa-polymorphic-call analysis
418 giving a wrong answer about the dynamic type of instance. */
419 if (is_a
<varpool_node
*> (n1
))
421 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
422 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
423 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
424 DECL_CONTEXT (n2
->decl
)))
425 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
426 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
427 return return_false_with_msg
428 ("references to virtual tables can not be merged");
430 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
431 return return_false_with_msg ("alignment mismatch");
433 /* For functions we compare attributes in equals_wpa, because we do
434 not know what attributes may cause codegen differences, but for
435 variables just compare attributes for references - the codegen
436 for constructors is affected only by those attributes that we lower
437 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
438 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
439 DECL_ATTRIBUTES (n2
->decl
)))
440 return return_false_with_msg ("different var decl attributes");
441 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
442 TREE_TYPE (n2
->decl
)) != 1)
443 return return_false_with_msg ("different var type attributes");
446 /* When matching virtual tables, be sure to also match information
447 relevant for polymorphic call analysis. */
448 if (used_by
&& is_a
<varpool_node
*> (used_by
)
449 && DECL_VIRTUAL_P (used_by
->decl
))
451 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
452 return return_false_with_msg ("virtual flag mismatch");
453 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
454 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
455 return return_false_with_msg ("final flag mismatch");
460 /* Hash properties that are compared by compare_referenced_symbol_properties. */
463 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
464 inchash::hash
&hstate
,
467 if (is_a
<cgraph_node
*> (ref
))
469 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
470 && !opt_for_fn (ref
->decl
, optimize_size
)
471 && !DECL_UNINLINABLE (ref
->decl
))
473 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
474 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
476 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
478 else if (is_a
<varpool_node
*> (ref
))
480 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
482 hstate
.add_int (DECL_ALIGN (ref
->decl
));
487 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
488 point to a same function. Comparison can be skipped if IGNORED_NODES
489 contains these nodes. ADDRESS indicate if address is taken. */
492 sem_item::compare_symbol_references (
493 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
494 symtab_node
*n1
, symtab_node
*n2
, bool address
)
496 enum availability avail1
, avail2
;
501 /* Never match variable and function. */
502 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
505 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
507 if (address
&& n1
->equal_address_to (n2
) == 1)
509 if (!address
&& n1
->semantically_equivalent_p (n2
))
512 n1
= n1
->ultimate_alias_target (&avail1
);
513 n2
= n2
->ultimate_alias_target (&avail2
);
515 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
516 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
519 return return_false_with_msg ("different references");
522 /* If cgraph edges E1 and E2 are indirect calls, verify that
523 ECF flags are the same. */
525 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
527 if (e1
->indirect_info
&& e2
->indirect_info
)
529 int e1_flags
= e1
->indirect_info
->ecf_flags
;
530 int e2_flags
= e2
->indirect_info
->ecf_flags
;
532 if (e1_flags
!= e2_flags
)
533 return return_false_with_msg ("ICF flags are different");
535 else if (e1
->indirect_info
|| e2
->indirect_info
)
541 /* Return true if parameter I may be used. */
544 sem_function::param_used_p (unsigned int i
)
546 if (ipa_node_params_sum
== NULL
)
549 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
551 if (parms_info
->descriptors
.is_empty ()
552 || parms_info
->descriptors
.length () <= i
)
555 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
558 /* Perform additional check needed to match types function parameters that are
559 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
560 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
563 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
565 /* Be sure that parameters are TBAA compatible. */
566 if (!func_checker::compatible_types_p (parm1
, parm2
))
567 return return_false_with_msg ("parameter type is not compatible");
569 if (POINTER_TYPE_P (parm1
)
570 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
571 return return_false_with_msg ("argument restrict flag mismatch");
573 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
574 if (POINTER_TYPE_P (parm1
)
575 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
576 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
577 return return_false_with_msg ("pointer wrt reference mismatch");
582 /* Fast equality function based on knowledge known in WPA. */
585 sem_function::equals_wpa (sem_item
*item
,
586 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
588 gcc_assert (item
->type
== FUNC
);
589 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
590 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
592 m_compared_func
= static_cast<sem_function
*> (item
);
594 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
595 return return_false_with_msg ("thunk_p mismatch");
597 if (cnode
->thunk
.thunk_p
)
599 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
600 return return_false_with_msg ("thunk fixed_offset mismatch");
601 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
602 return return_false_with_msg ("thunk virtual_value mismatch");
603 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
604 return return_false_with_msg ("thunk this_adjusting mismatch");
605 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
606 return return_false_with_msg ("thunk virtual_offset_p mismatch");
607 if (cnode
->thunk
.add_pointer_bounds_args
608 != cnode2
->thunk
.add_pointer_bounds_args
)
609 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
612 /* Compare special function DECL attributes. */
613 if (DECL_FUNCTION_PERSONALITY (decl
)
614 != DECL_FUNCTION_PERSONALITY (item
->decl
))
615 return return_false_with_msg ("function personalities are different");
617 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
618 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
619 return return_false_with_msg ("intrument function entry exit "
620 "attributes are different");
622 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
623 return return_false_with_msg ("no stack limit attributes are different");
625 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
626 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
628 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
629 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
631 /* TODO: pure/const flags mostly matters only for references, except for
632 the fact that codegen takes LOOPING flag as a hint that loops are
633 finite. We may arrange the code to always pick leader that has least
634 specified flags and then this can go into comparing symbol properties. */
635 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
636 return return_false_with_msg ("decl_or_type flags are different");
638 /* Do not match polymorphic constructors of different types. They calls
639 type memory location for ipa-polymorphic-call and we do not want
640 it to get confused by wrong type. */
641 if (DECL_CXX_CONSTRUCTOR_P (decl
)
642 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
644 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
645 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
646 else if (!func_checker::compatible_polymorphic_types_p
647 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
648 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
649 return return_false_with_msg ("ctor polymorphic type mismatch");
652 /* Checking function TARGET and OPTIMIZATION flags. */
653 cl_target_option
*tar1
= target_opts_for_fn (decl
);
654 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
656 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
658 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
660 fprintf (dump_file
, "target flags difference");
661 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
664 return return_false_with_msg ("Target flags are different");
667 cl_optimization
*opt1
= opts_for_fn (decl
);
668 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
670 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
674 fprintf (dump_file
, "optimization flags difference");
675 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
678 return return_false_with_msg ("optimization flags are different");
681 /* Result type checking. */
682 if (!func_checker::compatible_types_p
683 (TREE_TYPE (TREE_TYPE (decl
)),
684 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
685 return return_false_with_msg ("result types are different");
687 /* Checking types of arguments. */
688 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
689 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
690 for (unsigned i
= 0; list1
&& list2
;
691 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
693 tree parm1
= TREE_VALUE (list1
);
694 tree parm2
= TREE_VALUE (list2
);
696 /* This guard is here for function pointer with attributes (pr59927.c). */
697 if (!parm1
|| !parm2
)
698 return return_false_with_msg ("NULL argument type");
700 /* Verify that types are compatible to ensure that both functions
701 have same calling conventions. */
702 if (!types_compatible_p (parm1
, parm2
))
703 return return_false_with_msg ("parameter types are not compatible");
705 if (!param_used_p (i
))
708 /* Perform additional checks for used parameters. */
709 if (!compatible_parm_types_p (parm1
, parm2
))
714 return return_false_with_msg ("Mismatched number of parameters");
716 if (node
->num_references () != item
->node
->num_references ())
717 return return_false_with_msg ("different number of references");
719 /* Checking function attributes.
720 This is quadratic in number of attributes */
721 if (comp_type_attributes (TREE_TYPE (decl
),
722 TREE_TYPE (item
->decl
)) != 1)
723 return return_false_with_msg ("different type attributes");
724 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
725 DECL_ATTRIBUTES (item
->decl
)))
726 return return_false_with_msg ("different decl attributes");
728 /* The type of THIS pointer type memory location for
729 ipa-polymorphic-call-analysis. */
730 if (opt_for_fn (decl
, flag_devirtualize
)
731 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
732 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
734 && compare_polymorphic_p ())
736 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
737 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
738 if (!func_checker::compatible_polymorphic_types_p
739 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
740 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
741 return return_false_with_msg ("THIS pointer ODR type mismatch");
744 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
745 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
747 item
->node
->iterate_reference (i
, ref2
);
749 if (ref
->use
!= ref2
->use
)
750 return return_false_with_msg ("reference use mismatch");
752 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
754 ref
->address_matters_p ()))
758 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
759 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
763 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
766 if (!compare_edge_flags (e1
, e2
))
769 e1
= e1
->next_callee
;
770 e2
= e2
->next_callee
;
774 return return_false_with_msg ("different number of calls");
776 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
777 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
781 if (!compare_edge_flags (e1
, e2
))
784 e1
= e1
->next_callee
;
785 e2
= e2
->next_callee
;
789 return return_false_with_msg ("different number of indirect calls");
794 /* Update hash by address sensitive references. We iterate over all
795 sensitive references (address_matters_p) and we hash ultime alias
796 target of these nodes, which can improve a semantic item hash.
798 Also hash in referenced symbols properties. This can be done at any time
799 (as the properties should not change), but it is convenient to do it here
800 while we walk the references anyway. */
803 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
804 sem_item
*> &m_symtab_node_map
)
807 inchash::hash
hstate (get_hash ());
809 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
811 hstate
.add_int (ref
->use
);
812 hash_referenced_symbol_properties (ref
->referred
, hstate
,
813 ref
->use
== IPA_REF_ADDR
);
814 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
815 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
818 if (is_a
<cgraph_node
*> (node
))
820 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
823 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
824 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
826 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
830 set_hash (hstate
.end ());
833 /* Update hash by computed local hash values taken from different
835 TODO: stronger SCC based hashing would be desirable here. */
838 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
839 sem_item
*> &m_symtab_node_map
)
842 inchash::hash
state (get_hash ());
844 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
846 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
848 state
.merge_hash ((*result
)->get_hash ());
853 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
856 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
858 state
.merge_hash ((*result
)->get_hash ());
862 global_hash
= state
.end ();
865 /* Returns true if the item equals to ITEM given as argument. */
868 sem_function::equals (sem_item
*item
,
869 hash_map
<symtab_node
*, sem_item
*> &)
871 gcc_assert (item
->type
== FUNC
);
872 bool eq
= equals_private (item
);
874 if (m_checker
!= NULL
)
880 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
882 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
883 xstrdup_for_dump (node
->name()),
884 xstrdup_for_dump (item
->node
->name ()),
887 xstrdup_for_dump (node
->asm_name ()),
888 xstrdup_for_dump (item
->node
->asm_name ()),
889 eq
? "true" : "false");
894 /* Processes function equality comparison. */
897 sem_function::equals_private (sem_item
*item
)
899 if (item
->type
!= FUNC
)
902 basic_block bb1
, bb2
;
904 edge_iterator ei1
, ei2
;
908 m_compared_func
= static_cast<sem_function
*> (item
);
910 gcc_assert (decl
!= item
->decl
);
912 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
913 || edge_count
!= m_compared_func
->edge_count
914 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
915 return return_false ();
917 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
918 compare_polymorphic_p (),
921 &m_compared_func
->refs_set
);
922 arg1
= DECL_ARGUMENTS (decl
);
923 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
925 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
927 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
928 return return_false_with_msg ("argument types are not compatible");
929 if (!param_used_p (i
))
931 /* Perform additional checks for used parameters. */
932 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
934 if (!m_checker
->compare_decl (arg1
, arg2
))
935 return return_false ();
938 return return_false_with_msg ("Mismatched number of arguments");
940 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
943 /* Fill-up label dictionary. */
944 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
946 m_checker
->parse_labels (bb_sorted
[i
]);
947 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
950 /* Checking all basic blocks. */
951 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
952 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
953 return return_false();
955 dump_message ("All BBs are equal\n");
957 auto_vec
<int> bb_dict
;
959 /* Basic block edges check. */
960 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
962 bb1
= bb_sorted
[i
]->bb
;
963 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
965 ei2
= ei_start (bb2
->preds
);
967 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
971 if (e1
->flags
!= e2
->flags
)
972 return return_false_with_msg ("flags comparison returns false");
974 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
975 return return_false_with_msg ("edge comparison returns false");
977 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
978 return return_false_with_msg ("BB comparison returns false");
980 if (!m_checker
->compare_edge (e1
, e2
))
981 return return_false_with_msg ("edge comparison returns false");
987 /* Basic block PHI nodes comparison. */
988 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
989 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
990 return return_false_with_msg ("PHI node comparison returns false");
995 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
996 Helper for call_for_symbol_thunks_and_aliases. */
999 set_local (cgraph_node
*node
, void *data
)
1001 node
->local
.local
= data
!= NULL
;
1005 /* TREE_ADDRESSABLE of NODE to true.
1006 Helper for call_for_symbol_thunks_and_aliases. */
1009 set_addressable (varpool_node
*node
, void *)
1011 TREE_ADDRESSABLE (node
->decl
) = 1;
1015 /* Clear DECL_RTL of NODE.
1016 Helper for call_for_symbol_thunks_and_aliases. */
1019 clear_decl_rtl (symtab_node
*node
, void *)
1021 SET_DECL_RTL (node
->decl
, NULL
);
1025 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1026 possible. Return number of redirections made. */
1029 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1031 int nredirected
= 0;
1033 cgraph_edge
*e
= n
->callers
;
1037 /* Redirecting thunks to interposable symbols or symbols in other sections
1038 may not be supported by target output code. Play safe for now and
1039 punt on redirection. */
1040 if (!e
->caller
->thunk
.thunk_p
)
1042 struct cgraph_edge
*nexte
= e
->next_caller
;
1043 e
->redirect_callee (to
);
1050 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1052 bool removed
= false;
1053 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1055 if ((DECL_COMDAT_GROUP (n
->decl
)
1056 && (DECL_COMDAT_GROUP (n
->decl
)
1057 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1058 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1059 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1061 nredirected
+= redirect_all_callers (n_alias
, to
);
1062 if (n_alias
->can_remove_if_no_direct_calls_p ()
1063 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1065 && !n_alias
->has_aliases_p ())
1074 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1078 sem_function::merge (sem_item
*alias_item
)
1080 gcc_assert (alias_item
->type
== FUNC
);
1082 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1084 cgraph_node
*original
= get_node ();
1085 cgraph_node
*local_original
= NULL
;
1086 cgraph_node
*alias
= alias_func
->get_node ();
1088 bool create_wrapper
= false;
1089 bool create_alias
= false;
1090 bool redirect_callers
= false;
1091 bool remove
= false;
1093 bool original_discardable
= false;
1094 bool original_discarded
= false;
1096 bool original_address_matters
= original
->address_matters_p ();
1097 bool alias_address_matters
= alias
->address_matters_p ();
1099 if (DECL_EXTERNAL (alias
->decl
))
1102 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1106 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1107 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1112 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1116 /* Do not attempt to mix functions from different user sections;
1117 we do not know what user intends with those. */
1118 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1119 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1120 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1125 "original and alias are in different sections.\n\n");
1129 /* See if original is in a section that can be discarded if the main
1130 symbol is not used. */
1132 if (original
->can_be_discarded_p ())
1133 original_discardable
= true;
1134 /* Also consider case where we have resolution info and we know that
1135 original's definition is not going to be used. In this case we can not
1136 create alias to original. */
1137 if (node
->resolution
!= LDPR_UNKNOWN
1138 && !decl_binds_to_current_def_p (node
->decl
))
1139 original_discardable
= original_discarded
= true;
1141 /* Creating a symtab alias is the optimal way to merge.
1142 It however can not be used in the following cases:
1144 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1145 2) if ORIGINAL is in a section that may be discarded by linker or if
1146 it is an external functions where we can not create an alias
1147 (ORIGINAL_DISCARDABLE)
1148 3) if target do not support symbol aliases.
1149 4) original and alias lie in different comdat groups.
1151 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1152 and/or redirect all callers from ALIAS to ORIGINAL. */
1153 if ((original_address_matters
&& alias_address_matters
)
1154 || (original_discardable
1155 && (!DECL_COMDAT_GROUP (alias
->decl
)
1156 || (DECL_COMDAT_GROUP (alias
->decl
)
1157 != DECL_COMDAT_GROUP (original
->decl
))))
1158 || original_discarded
1159 || !sem_item::target_supports_symbol_aliases_p ()
1160 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1162 /* First see if we can produce wrapper. */
1164 /* Symbol properties that matter for references must be preserved.
1165 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1166 with proper properties. */
1167 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1168 alias
->address_taken
))
1172 "Wrapper cannot be created because referenced symbol "
1173 "properties mismatch\n");
1175 /* Do not turn function in one comdat group into wrapper to another
1176 comdat group. Other compiler producing the body of the
1177 another comdat group may make opossite decision and with unfortunate
1178 linker choices this may close a loop. */
1179 else if (DECL_COMDAT_GROUP (original
->decl
)
1180 && DECL_COMDAT_GROUP (alias
->decl
)
1181 && (DECL_COMDAT_GROUP (alias
->decl
)
1182 != DECL_COMDAT_GROUP (original
->decl
)))
1186 "Wrapper cannot be created because of COMDAT\n");
1188 else if (DECL_STATIC_CHAIN (alias
->decl
))
1192 "Can not create wrapper of nested functions.\n");
1194 /* TODO: We can also deal with variadic functions never calling
1196 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1200 "can not create wrapper of stdarg function.\n");
1202 else if (inline_summaries
1203 && inline_summaries
->get (alias
)->self_size
<= 2)
1206 fprintf (dump_file
, "Wrapper creation is not "
1207 "profitable (function is too small).\n");
1209 /* If user paid attention to mark function noinline, assume it is
1210 somewhat special and do not try to turn it into a wrapper that can
1211 not be undone by inliner. */
1212 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1215 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1218 create_wrapper
= true;
1220 /* We can redirect local calls in the case both alias and orignal
1221 are not interposable. */
1223 = alias
->get_availability () > AVAIL_INTERPOSABLE
1224 && original
->get_availability () > AVAIL_INTERPOSABLE
1225 && !alias
->instrumented_version
;
1226 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1227 with proper properties. */
1228 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1229 alias
->address_taken
))
1230 redirect_callers
= false;
1232 if (!redirect_callers
&& !create_wrapper
)
1235 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1236 "produce wrapper\n\n");
1240 /* Work out the symbol the wrapper should call.
1241 If ORIGINAL is interposable, we need to call a local alias.
1242 Also produce local alias (if possible) as an optimization.
1244 Local aliases can not be created inside comdat groups because that
1245 prevents inlining. */
1246 if (!original_discardable
&& !original
->get_comdat_group ())
1249 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1251 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1252 local_original
= original
;
1254 /* If we can not use local alias, fallback to the original
1256 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1257 local_original
= original
;
1259 /* If original is COMDAT local, we can not really redirect calls outside
1260 of its comdat group to it. */
1261 if (original
->comdat_local_p ())
1262 redirect_callers
= false;
1263 if (!local_original
)
1266 fprintf (dump_file
, "Not unifying; "
1267 "can not produce local alias.\n\n");
1271 if (!redirect_callers
&& !create_wrapper
)
1274 fprintf (dump_file
, "Not unifying; "
1275 "can not redirect callers nor produce a wrapper\n\n");
1279 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1281 && !alias
->can_remove_if_no_direct_calls_p ())
1284 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1285 "function has other uses than direct calls\n\n");
1290 create_alias
= true;
1292 if (redirect_callers
)
1294 int nredirected
= redirect_all_callers (alias
, local_original
);
1298 alias
->icf_merged
= true;
1299 local_original
->icf_merged
= true;
1301 if (dump_file
&& nredirected
)
1302 fprintf (dump_file
, "%i local calls have been "
1303 "redirected.\n", nredirected
);
1306 /* If all callers was redirected, do not produce wrapper. */
1307 if (alias
->can_remove_if_no_direct_calls_p ()
1308 && !DECL_VIRTUAL_P (alias
->decl
)
1309 && !alias
->has_aliases_p ())
1311 create_wrapper
= false;
1314 gcc_assert (!create_alias
);
1316 else if (create_alias
)
1318 alias
->icf_merged
= true;
1320 /* Remove the function's body. */
1321 ipa_merge_profiles (original
, alias
);
1322 alias
->release_body (true);
1324 /* Notice global symbol possibly produced RTL. */
1325 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1328 /* Create the alias. */
1329 cgraph_node::create_alias (alias_func
->decl
, decl
);
1330 alias
->resolve_alias (original
);
1332 original
->call_for_symbol_thunks_and_aliases
1333 (set_local
, (void *)(size_t) original
->local_p (), true);
1336 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1340 gcc_assert (!create_alias
);
1341 alias
->icf_merged
= true;
1342 local_original
->icf_merged
= true;
1344 ipa_merge_profiles (local_original
, alias
, true);
1345 alias
->create_wrapper (local_original
);
1348 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1351 /* It's possible that redirection can hit thunks that block
1352 redirection opportunities. */
1353 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1354 original
->icf_merged
= true;
1356 /* We use merged flag to track cases where COMDAT function is known to be
1357 compatible its callers. If we merged in non-COMDAT, we need to give up
1358 on this optimization. */
1359 if (original
->merged_comdat
&& !alias
->merged_comdat
)
1362 fprintf (dump_file
, "Dropping merged_comdat flag.\n\n");
1364 local_original
->merged_comdat
= false;
1365 original
->merged_comdat
= false;
1370 ipa_merge_profiles (original
, alias
);
1371 alias
->release_body ();
1373 alias
->body_removed
= true;
1374 alias
->icf_merged
= true;
1376 fprintf (dump_file
, "Unified; Function body was removed.\n");
1382 /* Semantic item initialization function. */
1385 sem_function::init (void)
1388 get_node ()->get_untransformed_body ();
1390 tree fndecl
= node
->decl
;
1391 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1394 gcc_assert (SSANAMES (func
));
1396 ssa_names_size
= SSANAMES (func
)->length ();
1400 region_tree
= func
->eh
->region_tree
;
1402 /* iterating all function arguments. */
1403 arg_count
= count_formal_params (fndecl
);
1405 edge_count
= n_edges_for_fn (func
);
1406 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1407 if (!cnode
->thunk
.thunk_p
)
1409 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1411 inchash::hash hstate
;
1414 FOR_EACH_BB_FN (bb
, func
)
1416 unsigned nondbg_stmt_count
= 0;
1419 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1421 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1424 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1427 gimple
*stmt
= gsi_stmt (gsi
);
1429 if (gimple_code (stmt
) != GIMPLE_DEBUG
1430 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1432 hash_stmt (stmt
, hstate
);
1433 nondbg_stmt_count
++;
1437 gcode_hash
= hstate
.end ();
1438 bb_sizes
.safe_push (nondbg_stmt_count
);
1440 /* Inserting basic block to hash table. */
1441 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1442 EDGE_COUNT (bb
->preds
)
1443 + EDGE_COUNT (bb
->succs
));
1445 bb_sorted
.safe_push (semantic_bb
);
1451 inchash::hash hstate
;
1452 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1453 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1454 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1455 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1456 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1457 gcode_hash
= hstate
.end ();
1461 /* Accumulate to HSTATE a hash of expression EXP.
1462 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1463 and DECL equality classes. */
1466 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1468 if (exp
== NULL_TREE
)
1470 hstate
.merge_hash (0);
1474 /* Handled component can be matched in a cureful way proving equivalence
1475 even if they syntactically differ. Just skip them. */
1477 while (handled_component_p (exp
))
1478 exp
= TREE_OPERAND (exp
, 0);
1480 enum tree_code code
= TREE_CODE (exp
);
1481 hstate
.add_int (code
);
1485 /* Use inchash::add_expr for everything that is LTO stable. */
1493 inchash::add_expr (exp
, hstate
);
1497 unsigned HOST_WIDE_INT idx
;
1500 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1502 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1504 add_expr (value
, hstate
);
1509 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1515 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1518 case POINTER_PLUS_EXPR
:
1521 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1522 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1526 inchash::hash one
, two
;
1527 add_expr (TREE_OPERAND (exp
, 0), one
);
1528 add_expr (TREE_OPERAND (exp
, 1), two
);
1529 hstate
.add_commutative (one
, two
);
1533 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1534 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1540 /* Accumulate to HSTATE a hash of type t.
1541 TYpes that may end up being compatible after LTO type merging needs to have
1545 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1547 if (type
== NULL_TREE
)
1549 hstate
.merge_hash (0);
1553 type
= TYPE_MAIN_VARIANT (type
);
1555 hstate
.add_int (TYPE_MODE (type
));
1557 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1559 hstate
.add_int (COMPLEX_TYPE
);
1560 sem_item::add_type (TREE_TYPE (type
), hstate
);
1562 else if (INTEGRAL_TYPE_P (type
))
1564 hstate
.add_int (INTEGER_TYPE
);
1565 hstate
.add_flag (TYPE_UNSIGNED (type
));
1566 hstate
.add_int (TYPE_PRECISION (type
));
1568 else if (VECTOR_TYPE_P (type
))
1570 hstate
.add_int (VECTOR_TYPE
);
1571 hstate
.add_int (TYPE_PRECISION (type
));
1572 sem_item::add_type (TREE_TYPE (type
), hstate
);
1574 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1576 hstate
.add_int (ARRAY_TYPE
);
1577 /* Do not hash size, so complete and incomplete types can match. */
1578 sem_item::add_type (TREE_TYPE (type
), hstate
);
1580 else if (RECORD_OR_UNION_TYPE_P (type
))
1582 gcc_checking_assert (COMPLETE_TYPE_P (type
));
1583 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1587 inchash::hash hstate2
;
1592 hstate2
.add_int (RECORD_TYPE
);
1593 gcc_assert (COMPLETE_TYPE_P (type
));
1595 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1596 if (TREE_CODE (f
) == FIELD_DECL
)
1598 add_type (TREE_TYPE (f
), hstate2
);
1602 hstate2
.add_int (nf
);
1603 hash
= hstate2
.end ();
1604 hstate
.add_wide_int (hash
);
1605 optimizer
->m_type_hash_cache
.put (type
, hash
);
1608 hstate
.add_wide_int (*val
);
1612 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1615 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1617 enum gimple_code code
= gimple_code (stmt
);
1619 hstate
.add_int (code
);
1624 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1627 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1628 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1629 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1631 inchash::hash one
, two
;
1633 add_expr (gimple_assign_rhs1 (stmt
), one
);
1634 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1635 add_expr (gimple_assign_rhs2 (stmt
), two
);
1636 hstate
.add_commutative (one
, two
);
1637 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1639 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1640 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1642 add_expr (gimple_assign_lhs (stmt
), hstate
);
1643 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1652 /* All these statements are equivalent if their operands are. */
1653 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1655 add_expr (gimple_op (stmt
, i
), hstate
);
1656 if (gimple_op (stmt
, i
))
1657 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1665 /* Return true if polymorphic comparison must be processed. */
1668 sem_function::compare_polymorphic_p (void)
1670 struct cgraph_edge
*e
;
1672 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1674 if (get_node ()->indirect_calls
!= NULL
)
1676 /* TODO: We can do simple propagation determining what calls may lead to
1677 a polymorphic call. */
1678 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1679 if (e
->callee
->definition
1680 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1685 /* For a given call graph NODE, the function constructs new
1686 semantic function item. */
1689 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1691 tree fndecl
= node
->decl
;
1692 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1694 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1697 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1701 if (DECL_STATIC_CONSTRUCTOR (node
->decl
)
1702 || DECL_STATIC_DESTRUCTOR (node
->decl
))
1705 sem_function
*f
= new sem_function (node
, 0, stack
);
1712 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1713 return true if phi nodes are semantically equivalent in these blocks . */
1716 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1718 gphi_iterator si1
, si2
;
1720 unsigned size1
, size2
, i
;
1724 gcc_assert (bb1
!= NULL
);
1725 gcc_assert (bb2
!= NULL
);
1727 si2
= gsi_start_phis (bb2
);
1728 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1731 gsi_next_nonvirtual_phi (&si1
);
1732 gsi_next_nonvirtual_phi (&si2
);
1734 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1737 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1738 return return_false();
1743 tree phi_result1
= gimple_phi_result (phi1
);
1744 tree phi_result2
= gimple_phi_result (phi2
);
1746 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1747 return return_false_with_msg ("PHI results are different");
1749 size1
= gimple_phi_num_args (phi1
);
1750 size2
= gimple_phi_num_args (phi2
);
1753 return return_false ();
1755 for (i
= 0; i
< size1
; ++i
)
1757 t1
= gimple_phi_arg (phi1
, i
)->def
;
1758 t2
= gimple_phi_arg (phi2
, i
)->def
;
1760 if (!m_checker
->compare_operand (t1
, t2
))
1761 return return_false ();
1763 e1
= gimple_phi_arg_edge (phi1
, i
);
1764 e2
= gimple_phi_arg_edge (phi2
, i
);
1766 if (!m_checker
->compare_edge (e1
, e2
))
1767 return return_false ();
1776 /* Returns true if tree T can be compared as a handled component. */
1779 sem_function::icf_handled_component_p (tree t
)
1781 tree_code tc
= TREE_CODE (t
);
1783 return (handled_component_p (t
)
1784 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1787 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1788 corresponds to TARGET. */
1791 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1796 if (bb_dict
->length () <= (unsigned)source
)
1797 bb_dict
->safe_grow_cleared (source
+ 1);
1799 if ((*bb_dict
)[source
] == 0)
1801 (*bb_dict
)[source
] = target
;
1805 return (*bb_dict
)[source
] == target
;
1809 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1811 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1815 /* Constructor based on varpool node _NODE with computed hash _HASH.
1816 Bitmap STACK is used for memory allocation. */
1818 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1819 bitmap_obstack
*stack
): sem_item(VAR
,
1822 gcc_checking_assert (node
);
1823 gcc_checking_assert (get_node ());
1826 /* Fast equality function based on knowledge known in WPA. */
1829 sem_variable::equals_wpa (sem_item
*item
,
1830 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1832 gcc_assert (item
->type
== VAR
);
1834 if (node
->num_references () != item
->node
->num_references ())
1835 return return_false_with_msg ("different number of references");
1837 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1838 return return_false_with_msg ("TLS model");
1840 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1841 alignment out of all aliases. */
1843 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1844 return return_false_with_msg ("Virtual flag mismatch");
1846 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1847 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1848 || !operand_equal_p (DECL_SIZE (decl
),
1849 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1850 return return_false_with_msg ("size mismatch");
1852 /* Do not attempt to mix data from different user sections;
1853 we do not know what user intends with those. */
1854 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1855 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1856 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1857 return return_false_with_msg ("user section mismatch");
1859 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1860 return return_false_with_msg ("text section");
1862 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1863 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1865 item
->node
->iterate_reference (i
, ref2
);
1867 if (ref
->use
!= ref2
->use
)
1868 return return_false_with_msg ("reference use mismatch");
1870 if (!compare_symbol_references (ignored_nodes
,
1871 ref
->referred
, ref2
->referred
,
1872 ref
->address_matters_p ()))
1879 /* Returns true if the item equals to ITEM given as argument. */
1882 sem_variable::equals (sem_item
*item
,
1883 hash_map
<symtab_node
*, sem_item
*> &)
1885 gcc_assert (item
->type
== VAR
);
1888 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1889 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1890 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1891 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1893 /* As seen in PR ipa/65303 we have to compare variables types. */
1894 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1895 TREE_TYPE (item
->decl
)))
1896 return return_false_with_msg ("variables types are different");
1898 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1899 DECL_INITIAL (item
->node
->decl
));
1900 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1902 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1903 xstrdup_for_dump (node
->name()),
1904 xstrdup_for_dump (item
->node
->name ()),
1905 node
->order
, item
->node
->order
,
1906 xstrdup_for_dump (node
->asm_name ()),
1907 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1912 /* Compares trees T1 and T2 for semantic equality. */
1915 sem_variable::equals (tree t1
, tree t2
)
1918 return return_with_debug (t1
== t2
);
1921 tree_code tc1
= TREE_CODE (t1
);
1922 tree_code tc2
= TREE_CODE (t2
);
1925 return return_false_with_msg ("TREE_CODE mismatch");
1931 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1932 unsigned HOST_WIDE_INT idx
;
1934 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1935 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1936 return return_false_with_msg ("constructor type mismatch");
1938 if (typecode
== ARRAY_TYPE
)
1940 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1941 /* For arrays, check that the sizes all match. */
1942 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1944 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1945 return return_false_with_msg ("constructor array size mismatch");
1947 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1949 return return_false_with_msg ("constructor type incompatible");
1951 v1
= CONSTRUCTOR_ELTS (t1
);
1952 v2
= CONSTRUCTOR_ELTS (t2
);
1953 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1954 return return_false_with_msg ("constructor number of elts mismatch");
1956 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1958 constructor_elt
*c1
= &(*v1
)[idx
];
1959 constructor_elt
*c2
= &(*v2
)[idx
];
1961 /* Check that each value is the same... */
1962 if (!sem_variable::equals (c1
->value
, c2
->value
))
1964 /* ... and that they apply to the same fields! */
1965 if (!sem_variable::equals (c1
->index
, c2
->index
))
1972 tree x1
= TREE_OPERAND (t1
, 0);
1973 tree x2
= TREE_OPERAND (t2
, 0);
1974 tree y1
= TREE_OPERAND (t1
, 1);
1975 tree y2
= TREE_OPERAND (t2
, 1);
1977 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1978 return return_false ();
1980 /* Type of the offset on MEM_REF does not matter. */
1981 return return_with_debug (sem_variable::equals (x1
, x2
)
1982 && wi::to_offset (y1
)
1983 == wi::to_offset (y2
));
1988 tree op1
= TREE_OPERAND (t1
, 0);
1989 tree op2
= TREE_OPERAND (t2
, 0);
1990 return sem_variable::equals (op1
, op2
);
1992 /* References to other vars/decls are compared using ipa-ref. */
1995 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1997 return return_false_with_msg ("Declaration mismatch");
1999 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
2000 need to process its VAR/FUNCTION references without relying on ipa-ref
2004 return return_false_with_msg ("Declaration mismatch");
2006 /* Integer constants are the same only if the same width of type. */
2007 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2008 return return_false_with_msg ("INTEGER_CST precision mismatch");
2009 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2010 return return_false_with_msg ("INTEGER_CST mode mismatch");
2011 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2013 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2014 return return_false_with_msg ("STRING_CST mode mismatch");
2015 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2016 return return_false_with_msg ("STRING_CST length mismatch");
2017 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2018 TREE_STRING_LENGTH (t1
)))
2019 return return_false_with_msg ("STRING_CST mismatch");
2022 /* Fixed constants are the same only if the same width of type. */
2023 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2024 return return_false_with_msg ("FIXED_CST precision mismatch");
2026 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2027 TREE_FIXED_CST (t2
)));
2029 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2030 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2032 /* Real constants are the same only if the same width of type. */
2033 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2034 return return_false_with_msg ("REAL_CST precision mismatch");
2035 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2036 &TREE_REAL_CST (t2
)));
2041 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2042 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2044 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2045 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2046 VECTOR_CST_ELT (t2
, i
)))
2052 case ARRAY_RANGE_REF
:
2054 tree x1
= TREE_OPERAND (t1
, 0);
2055 tree x2
= TREE_OPERAND (t2
, 0);
2056 tree y1
= TREE_OPERAND (t1
, 1);
2057 tree y2
= TREE_OPERAND (t2
, 1);
2059 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2061 if (!sem_variable::equals (array_ref_low_bound (t1
),
2062 array_ref_low_bound (t2
)))
2064 if (!sem_variable::equals (array_ref_element_size (t1
),
2065 array_ref_element_size (t2
)))
2071 case POINTER_PLUS_EXPR
:
2076 tree x1
= TREE_OPERAND (t1
, 0);
2077 tree x2
= TREE_OPERAND (t2
, 0);
2078 tree y1
= TREE_OPERAND (t1
, 1);
2079 tree y2
= TREE_OPERAND (t2
, 1);
2081 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2085 case VIEW_CONVERT_EXPR
:
2086 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2087 return return_false ();
2088 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2090 return return_false_with_msg ("ERROR_MARK");
2092 return return_false_with_msg ("Unknown TREE code reached");
2096 /* Parser function that visits a varpool NODE. */
2099 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2101 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2105 sem_variable
*v
= new sem_variable (node
, 0, stack
);
2112 /* References independent hash function. */
2115 sem_variable::get_hash (void)
2120 /* All WPA streamed in symbols should have their hashes computed at compile
2121 time. At this point, the constructor may not be in memory at all.
2122 DECL_INITIAL (decl) would be error_mark_node in that case. */
2123 gcc_assert (!node
->lto_file_data
);
2124 tree ctor
= DECL_INITIAL (decl
);
2125 inchash::hash hstate
;
2127 hstate
.add_int (456346417);
2128 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2129 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2130 add_expr (ctor
, hstate
);
2131 set_hash (hstate
.end ());
2136 /* Set all points-to UIDs of aliases pointing to node N as UID. */
2139 set_alias_uids (symtab_node
*n
, int uid
)
2142 FOR_EACH_ALIAS (n
, ref
)
2145 fprintf (dump_file
, " Setting points-to UID of [%s] as %d\n",
2146 xstrdup_for_dump (ref
->referring
->asm_name ()), uid
);
2148 SET_DECL_PT_UID (ref
->referring
->decl
, uid
);
2149 set_alias_uids (ref
->referring
, uid
);
2153 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2157 sem_variable::merge (sem_item
*alias_item
)
2159 gcc_assert (alias_item
->type
== VAR
);
2161 if (!sem_item::target_supports_symbol_aliases_p ())
2164 fprintf (dump_file
, "Not unifying; "
2165 "Symbol aliases are not supported by target\n\n");
2169 if (DECL_EXTERNAL (alias_item
->decl
))
2172 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2176 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2178 varpool_node
*original
= get_node ();
2179 varpool_node
*alias
= alias_var
->get_node ();
2180 bool original_discardable
= false;
2182 bool original_address_matters
= original
->address_matters_p ();
2183 bool alias_address_matters
= alias
->address_matters_p ();
2185 /* See if original is in a section that can be discarded if the main
2187 Also consider case where we have resolution info and we know that
2188 original's definition is not going to be used. In this case we can not
2189 create alias to original. */
2190 if (original
->can_be_discarded_p ()
2191 || (node
->resolution
!= LDPR_UNKNOWN
2192 && !decl_binds_to_current_def_p (node
->decl
)))
2193 original_discardable
= true;
2195 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2197 /* Constant pool machinery is not quite ready for aliases.
2198 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2199 For LTO merging does not happen that is an important missing feature.
2200 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2201 flag is dropped and non-local symbol name is assigned. */
2202 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2203 || DECL_IN_CONSTANT_POOL (original
->decl
))
2207 "Not unifying; constant pool variables.\n\n");
2211 /* Do not attempt to mix functions from different user sections;
2212 we do not know what user intends with those. */
2213 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2214 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2215 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2220 "original and alias are in different sections.\n\n");
2224 /* We can not merge if address comparsion metters. */
2225 if (original_address_matters
&& alias_address_matters
2226 && flag_merge_constants
< 2)
2231 "adress of original and alias may be compared.\n\n");
2235 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2238 fprintf (dump_file
, "Not unifying; "
2239 "original and alias have incompatible alignments\n\n");
2244 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2247 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2248 "across comdat group boundary\n\n");
2253 if (original_discardable
)
2256 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2257 "target is discardable\n\n");
2263 gcc_assert (!original
->alias
);
2264 gcc_assert (!alias
->alias
);
2266 alias
->analyzed
= false;
2268 DECL_INITIAL (alias
->decl
) = NULL
;
2269 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2271 alias
->need_bounds_init
= false;
2272 alias
->remove_all_references ();
2273 if (TREE_ADDRESSABLE (alias
->decl
))
2274 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2276 varpool_node::create_alias (alias_var
->decl
, decl
);
2277 alias
->resolve_alias (original
);
2280 fprintf (dump_file
, "Unified; Variable alias has been created.\n");
2282 set_alias_uids (original
, DECL_UID (original
->decl
));
2287 /* Dump symbol to FILE. */
2290 sem_variable::dump_to_file (FILE *file
)
2294 print_node (file
, "", decl
, 0);
2295 fprintf (file
, "\n\n");
2298 unsigned int sem_item_optimizer::class_id
= 0;
2300 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2301 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2304 bitmap_obstack_initialize (&m_bmstack
);
2307 sem_item_optimizer::~sem_item_optimizer ()
2309 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2312 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2313 it
!= m_classes
.end (); ++it
)
2315 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2316 delete (*it
)->classes
[i
];
2318 (*it
)->classes
.release ();
2324 bitmap_obstack_release (&m_bmstack
);
2327 /* Write IPA ICF summary for symbols. */
2330 sem_item_optimizer::write_summary (void)
2332 unsigned int count
= 0;
2334 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2335 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2338 /* Calculate number of symbols to be serialized. */
2339 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2341 lsei_next_in_partition (&lsei
))
2343 symtab_node
*node
= lsei_node (lsei
);
2345 if (m_symtab_node_map
.get (node
))
2349 streamer_write_uhwi (ob
, count
);
2351 /* Process all of the symbols. */
2352 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2354 lsei_next_in_partition (&lsei
))
2356 symtab_node
*node
= lsei_node (lsei
);
2358 sem_item
**item
= m_symtab_node_map
.get (node
);
2362 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2363 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2365 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2369 streamer_write_char_stream (ob
->main_stream
, 0);
2370 produce_asm (ob
, NULL
);
2371 destroy_output_block (ob
);
2374 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2375 contains LEN bytes. */
2378 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2379 const char *data
, size_t len
)
2381 const lto_function_header
*header
=
2382 (const lto_function_header
*) data
;
2383 const int cfg_offset
= sizeof (lto_function_header
);
2384 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2385 const int string_offset
= main_offset
+ header
->main_size
;
2390 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2391 header
->main_size
, file_data
->mode_table
);
2394 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2395 header
->string_size
, vNULL
);
2397 count
= streamer_read_uhwi (&ib_main
);
2399 for (i
= 0; i
< count
; i
++)
2403 lto_symtab_encoder_t encoder
;
2405 index
= streamer_read_uhwi (&ib_main
);
2406 encoder
= file_data
->symtab_node_encoder
;
2407 node
= lto_symtab_encoder_deref (encoder
, index
);
2409 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2411 gcc_assert (node
->definition
);
2414 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2415 node
->asm_name (), (void *) node
->decl
, node
->order
);
2417 if (is_a
<cgraph_node
*> (node
))
2419 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2421 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2425 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2427 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2431 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2433 lto_data_in_delete (data_in
);
2436 /* Read IPA ICF summary for symbols. */
2439 sem_item_optimizer::read_summary (void)
2441 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2442 lto_file_decl_data
*file_data
;
2445 while ((file_data
= file_data_vec
[j
++]))
2448 const char *data
= lto_get_section_data (file_data
,
2449 LTO_section_ipa_icf
, NULL
, &len
);
2452 read_section (file_data
, data
, len
);
2456 /* Register callgraph and varpool hooks. */
2459 sem_item_optimizer::register_hooks (void)
2461 if (!m_cgraph_node_hooks
)
2462 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2463 (&sem_item_optimizer::cgraph_removal_hook
, this);
2465 if (!m_varpool_node_hooks
)
2466 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2467 (&sem_item_optimizer::varpool_removal_hook
, this);
2470 /* Unregister callgraph and varpool hooks. */
2473 sem_item_optimizer::unregister_hooks (void)
2475 if (m_cgraph_node_hooks
)
2476 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2478 if (m_varpool_node_hooks
)
2479 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2482 /* Adds a CLS to hashtable associated by hash value. */
2485 sem_item_optimizer::add_class (congruence_class
*cls
)
2487 gcc_assert (cls
->members
.length ());
2489 congruence_class_group
*group
= get_group_by_hash (
2490 cls
->members
[0]->get_hash (),
2491 cls
->members
[0]->type
);
2492 group
->classes
.safe_push (cls
);
2495 /* Gets a congruence class group based on given HASH value and TYPE. */
2497 congruence_class_group
*
2498 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2500 congruence_class_group
*item
= XNEW (congruence_class_group
);
2504 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2510 item
->classes
.create (1);
2517 /* Callgraph removal hook called for a NODE with a custom DATA. */
2520 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2522 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2523 optimizer
->remove_symtab_node (node
);
2526 /* Varpool removal hook called for a NODE with a custom DATA. */
2529 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2531 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2532 optimizer
->remove_symtab_node (node
);
2535 /* Remove symtab NODE triggered by symtab removal hooks. */
2538 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2540 gcc_assert (!m_classes
.elements());
2542 m_removed_items_set
.add (node
);
2546 sem_item_optimizer::remove_item (sem_item
*item
)
2548 if (m_symtab_node_map
.get (item
->node
))
2549 m_symtab_node_map
.remove (item
->node
);
2553 /* Removes all callgraph and varpool nodes that are marked by symtab
2557 sem_item_optimizer::filter_removed_items (void)
2559 auto_vec
<sem_item
*> filtered
;
2561 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2563 sem_item
*item
= m_items
[i
];
2565 if (m_removed_items_set
.contains (item
->node
))
2571 if (item
->type
== FUNC
)
2573 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2575 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2578 filtered
.safe_push (item
);
2582 if (!flag_ipa_icf_variables
)
2586 /* Filter out non-readonly variables. */
2587 tree decl
= item
->decl
;
2588 if (TREE_READONLY (decl
))
2589 filtered
.safe_push (item
);
2596 /* Clean-up of released semantic items. */
2599 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2600 m_items
.safe_push (filtered
[i
]);
2603 /* Optimizer entry point which returns true in case it processes
2604 a merge operation. True is returned if there's a merge operation
2608 sem_item_optimizer::execute (void)
2610 filter_removed_items ();
2611 unregister_hooks ();
2614 update_hash_by_addr_refs ();
2615 build_hash_based_classes ();
2618 fprintf (dump_file
, "Dump after hash based groups\n");
2619 dump_cong_classes ();
2621 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2622 m_items
[i
]->init_wpa ();
2624 subdivide_classes_by_equality (true);
2627 fprintf (dump_file
, "Dump after WPA based types groups\n");
2629 dump_cong_classes ();
2631 process_cong_reduction ();
2632 checking_verify_classes ();
2635 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2637 dump_cong_classes ();
2639 parse_nonsingleton_classes ();
2640 subdivide_classes_by_equality ();
2643 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2645 dump_cong_classes ();
2647 unsigned int prev_class_count
= m_classes_count
;
2649 process_cong_reduction ();
2650 dump_cong_classes ();
2651 checking_verify_classes ();
2652 bool merged_p
= merge_classes (prev_class_count
);
2654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2655 symtab_node::dump_table (dump_file
);
2660 /* Function responsible for visiting all potential functions and
2661 read-only variables that can be merged. */
2664 sem_item_optimizer::parse_funcs_and_vars (void)
2668 if (flag_ipa_icf_functions
)
2669 FOR_EACH_DEFINED_FUNCTION (cnode
)
2671 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2674 m_items
.safe_push (f
);
2675 m_symtab_node_map
.put (cnode
, f
);
2678 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2680 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2681 f
->dump_to_file (dump_file
);
2684 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2687 varpool_node
*vnode
;
2689 if (flag_ipa_icf_variables
)
2690 FOR_EACH_DEFINED_VARIABLE (vnode
)
2692 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2696 m_items
.safe_push (v
);
2697 m_symtab_node_map
.put (vnode
, v
);
2702 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2705 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2707 item
->index_in_class
= cls
->members
.length ();
2708 cls
->members
.safe_push (item
);
2712 /* For each semantic item, append hash values of references. */
2715 sem_item_optimizer::update_hash_by_addr_refs ()
2717 /* First, append to hash sensitive references and class type if it need to
2718 be matched for ODR. */
2719 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2721 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2722 if (m_items
[i
]->type
== FUNC
)
2724 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2725 && contains_polymorphic_type_p
2726 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2727 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2728 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2729 && static_cast<sem_function
*> (m_items
[i
])
2730 ->compare_polymorphic_p ())))
2733 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2734 inchash::hash
hstate (m_items
[i
]->get_hash ());
2736 if (TYPE_NAME (class_type
)
2737 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2739 (IDENTIFIER_HASH_VALUE
2740 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2742 m_items
[i
]->set_hash (hstate
.end ());
2747 /* Once all symbols have enhanced hash value, we can append
2748 hash values of symbols that are seen by IPA ICF and are
2749 references by a semantic item. Newly computed values
2750 are saved to global_hash member variable. */
2751 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2752 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2754 /* Global hash value replace current hash values. */
2755 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2756 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2759 /* Congruence classes are built by hash value. */
2762 sem_item_optimizer::build_hash_based_classes (void)
2764 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2766 sem_item
*item
= m_items
[i
];
2768 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2771 if (!group
->classes
.length ())
2774 group
->classes
.safe_push (new congruence_class (class_id
++));
2777 add_item_to_class (group
->classes
[0], item
);
2781 /* Build references according to call graph. */
2784 sem_item_optimizer::build_graph (void)
2786 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2788 sem_item
*item
= m_items
[i
];
2789 m_symtab_node_map
.put (item
->node
, item
);
2791 /* Initialize hash values if we are not in LTO mode. */
2796 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2798 sem_item
*item
= m_items
[i
];
2800 if (item
->type
== FUNC
)
2802 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2804 cgraph_edge
*e
= cnode
->callees
;
2807 sem_item
**slot
= m_symtab_node_map
.get
2808 (e
->callee
->ultimate_alias_target ());
2810 item
->add_reference (*slot
);
2816 ipa_ref
*ref
= NULL
;
2817 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2819 sem_item
**slot
= m_symtab_node_map
.get
2820 (ref
->referred
->ultimate_alias_target ());
2822 item
->add_reference (*slot
);
2827 /* Semantic items in classes having more than one element and initialized.
2828 In case of WPA, we load function body. */
2831 sem_item_optimizer::parse_nonsingleton_classes (void)
2833 unsigned int init_called_count
= 0;
2835 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2836 if (m_items
[i
]->cls
->members
.length () > 1)
2838 m_items
[i
]->init ();
2839 init_called_count
++;
2843 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2844 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2847 /* Equality function for semantic items is used to subdivide existing
2848 classes. If IN_WPA, fast equality function is invoked. */
2851 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2853 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2854 it
!= m_classes
.end (); ++it
)
2856 unsigned int class_count
= (*it
)->classes
.length ();
2858 for (unsigned i
= 0; i
< class_count
; i
++)
2860 congruence_class
*c
= (*it
)->classes
[i
];
2862 if (c
->members
.length() > 1)
2864 auto_vec
<sem_item
*> new_vector
;
2866 sem_item
*first
= c
->members
[0];
2867 new_vector
.safe_push (first
);
2869 unsigned class_split_first
= (*it
)->classes
.length ();
2871 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2873 sem_item
*item
= c
->members
[j
];
2875 bool equals
= in_wpa
? first
->equals_wpa (item
,
2876 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2879 new_vector
.safe_push (item
);
2882 bool integrated
= false;
2884 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2886 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2887 bool equals
= in_wpa
? x
->equals_wpa (item
,
2888 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2893 add_item_to_class ((*it
)->classes
[k
], item
);
2901 congruence_class
*c
= new congruence_class (class_id
++);
2903 add_item_to_class (c
, item
);
2905 (*it
)->classes
.safe_push (c
);
2910 // we replace newly created new_vector for the class we've just splitted
2911 c
->members
.release ();
2912 c
->members
.create (new_vector
.length ());
2914 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2915 add_item_to_class (c
, new_vector
[j
]);
2920 checking_verify_classes ();
2923 /* Subdivide classes by address references that members of the class
2924 reference. Example can be a pair of functions that have an address
2925 taken from a function. If these addresses are different the class
2929 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2931 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2933 unsigned newly_created_classes
= 0;
2935 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2936 it
!= m_classes
.end (); ++it
)
2938 unsigned int class_count
= (*it
)->classes
.length ();
2939 auto_vec
<congruence_class
*> new_classes
;
2941 for (unsigned i
= 0; i
< class_count
; i
++)
2943 congruence_class
*c
= (*it
)->classes
[i
];
2945 if (c
->members
.length() > 1)
2947 subdivide_hash_map split_map
;
2949 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2951 sem_item
*source_node
= c
->members
[j
];
2953 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2956 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2958 gcc_checking_assert (slot
);
2960 slot
->safe_push (source_node
);
2966 /* If the map contains more than one key, we have to split the map
2968 if (split_map
.elements () != 1)
2970 bool first_class
= true;
2972 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2973 it2
!= split_map
.end (); ++it2
)
2975 congruence_class
*new_cls
;
2976 new_cls
= new congruence_class (class_id
++);
2978 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2979 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2981 worklist_push (new_cls
);
2982 newly_created_classes
++;
2986 (*it
)->classes
[i
] = new_cls
;
2987 first_class
= false;
2991 new_classes
.safe_push (new_cls
);
2997 /* Release memory. */
2998 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2999 it2
!= split_map
.end (); ++it2
)
3001 delete (*it2
).first
;
3002 (*it2
).second
.release ();
3007 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
3008 (*it
)->classes
.safe_push (new_classes
[i
]);
3011 return newly_created_classes
;
3014 /* Verify congruence classes, if checking is enabled. */
3017 sem_item_optimizer::checking_verify_classes (void)
3023 /* Verify congruence classes. */
3026 sem_item_optimizer::verify_classes (void)
3028 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3029 it
!= m_classes
.end (); ++it
)
3031 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3033 congruence_class
*cls
= (*it
)->classes
[i
];
3036 gcc_assert (cls
->members
.length () > 0);
3038 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3040 sem_item
*item
= cls
->members
[j
];
3043 gcc_assert (item
->cls
== cls
);
3045 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3047 sem_usage_pair
*usage
= item
->usages
[k
];
3048 gcc_assert (usage
->item
->index_in_class
<
3049 usage
->item
->cls
->members
.length ());
3056 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3057 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3058 but unused argument. */
3061 sem_item_optimizer::release_split_map (congruence_class
* const &,
3062 bitmap
const &b
, traverse_split_pair
*)
3071 /* Process split operation for a class given as pointer CLS_PTR,
3072 where bitmap B splits congruence class members. DATA is used
3073 as argument of split pair. */
3076 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3077 bitmap
const &b
, traverse_split_pair
*pair
)
3079 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3080 const congruence_class
*splitter_cls
= pair
->cls
;
3082 /* If counted bits are greater than zero and less than the number of members
3083 a group will be splitted. */
3084 unsigned popcount
= bitmap_count_bits (b
);
3086 if (popcount
> 0 && popcount
< cls
->members
.length ())
3088 auto_vec
<congruence_class
*, 2> newclasses
;
3089 newclasses
.quick_push (new congruence_class (class_id
++));
3090 newclasses
.quick_push (new congruence_class (class_id
++));
3092 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3094 int target
= bitmap_bit_p (b
, i
);
3095 congruence_class
*tc
= newclasses
[target
];
3097 add_item_to_class (tc
, cls
->members
[i
]);
3102 for (unsigned int i
= 0; i
< 2; i
++)
3103 gcc_assert (newclasses
[i
]->members
.length ());
3106 if (splitter_cls
== cls
)
3107 optimizer
->splitter_class_removed
= true;
3109 /* Remove old class from worklist if presented. */
3110 bool in_worklist
= cls
->in_worklist
;
3113 cls
->in_worklist
= false;
3115 congruence_class_group g
;
3116 g
.hash
= cls
->members
[0]->get_hash ();
3117 g
.type
= cls
->members
[0]->type
;
3119 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3121 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3122 if (slot
->classes
[i
] == cls
)
3124 slot
->classes
.ordered_remove (i
);
3128 /* New class will be inserted and integrated to work list. */
3129 for (unsigned int i
= 0; i
< 2; i
++)
3130 optimizer
->add_class (newclasses
[i
]);
3132 /* Two classes replace one, so that increment just by one. */
3133 optimizer
->m_classes_count
++;
3135 /* If OLD class was presented in the worklist, we remove the class
3136 and replace it will both newly created classes. */
3138 for (unsigned int i
= 0; i
< 2; i
++)
3139 optimizer
->worklist_push (newclasses
[i
]);
3140 else /* Just smaller class is inserted. */
3142 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3143 newclasses
[1]->members
.length () ?
3145 optimizer
->worklist_push (newclasses
[smaller_index
]);
3148 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3150 fprintf (dump_file
, " congruence class splitted:\n");
3151 cls
->dump (dump_file
, 4);
3153 fprintf (dump_file
, " newly created groups:\n");
3154 for (unsigned int i
= 0; i
< 2; i
++)
3155 newclasses
[i
]->dump (dump_file
, 4);
3158 /* Release class if not presented in work list. */
3167 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3168 Bitmap stack BMSTACK is used for bitmap allocation. */
3171 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3174 hash_map
<congruence_class
*, bitmap
> split_map
;
3176 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3178 sem_item
*item
= cls
->members
[i
];
3180 /* Iterate all usages that have INDEX as usage of the item. */
3181 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3183 sem_usage_pair
*usage
= item
->usages
[j
];
3185 if (usage
->index
!= index
)
3188 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3193 b
= BITMAP_ALLOC (&m_bmstack
);
3194 split_map
.put (usage
->item
->cls
, b
);
3199 gcc_checking_assert (usage
->item
->cls
);
3200 gcc_checking_assert (usage
->item
->index_in_class
<
3201 usage
->item
->cls
->members
.length ());
3203 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3207 traverse_split_pair pair
;
3208 pair
.optimizer
= this;
3211 splitter_class_removed
= false;
3213 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3215 /* Bitmap clean-up. */
3217 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3220 /* Every usage of a congruence class CLS is a candidate that can split the
3221 collection of classes. Bitmap stack BMSTACK is used for bitmap
3225 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3230 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3232 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3233 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3235 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3237 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3238 fprintf (dump_file
, " processing congruence step for class: %u, index: %u\n",
3241 do_congruence_step_for_index (cls
, i
);
3243 if (splitter_class_removed
)
3247 BITMAP_FREE (usage
);
3250 /* Adds a newly created congruence class CLS to worklist. */
3253 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3255 /* Return if the class CLS is already presented in work list. */
3256 if (cls
->in_worklist
)
3259 cls
->in_worklist
= true;
3260 worklist
.push_back (cls
);
3263 /* Pops a class from worklist. */
3266 sem_item_optimizer::worklist_pop (void)
3268 congruence_class
*cls
;
3270 while (!worklist
.empty ())
3272 cls
= worklist
.front ();
3273 worklist
.pop_front ();
3274 if (cls
->in_worklist
)
3276 cls
->in_worklist
= false;
3282 /* Work list item was already intended to be removed.
3283 The only reason for doing it is to split a class.
3284 Thus, the class CLS is deleted. */
3292 /* Iterative congruence reduction function. */
3295 sem_item_optimizer::process_cong_reduction (void)
3297 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3298 it
!= m_classes
.end (); ++it
)
3299 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3300 if ((*it
)->classes
[i
]->is_class_used ())
3301 worklist_push ((*it
)->classes
[i
]);
3304 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3305 (unsigned long) worklist
.size ());
3307 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3308 fprintf (dump_file
, "Congruence class reduction\n");
3310 congruence_class
*cls
;
3312 /* Process complete congruence reduction. */
3313 while ((cls
= worklist_pop ()) != NULL
)
3314 do_congruence_step (cls
);
3316 /* Subdivide newly created classes according to references. */
3317 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3320 fprintf (dump_file
, "Address reference subdivision created: %u "
3321 "new classes.\n", new_classes
);
3324 /* Debug function prints all informations about congruence classes. */
3327 sem_item_optimizer::dump_cong_classes (void)
3333 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3334 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3336 /* Histogram calculation. */
3337 unsigned int max_index
= 0;
3338 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3340 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3341 it
!= m_classes
.end (); ++it
)
3343 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3345 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3353 "Class size histogram [num of members]: number of classe number of classess\n");
3355 for (unsigned int i
= 0; i
<= max_index
; i
++)
3357 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3359 fprintf (dump_file
, "\n\n");
3362 if (dump_flags
& TDF_DETAILS
)
3363 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3364 it
!= m_classes
.end (); ++it
)
3366 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3368 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3370 (*it
)->classes
[i
]->dump (dump_file
, 4);
3372 if(i
< (*it
)->classes
.length () - 1)
3373 fprintf (dump_file
, " ");
3380 /* After reduction is done, we can declare all items in a group
3381 to be equal. PREV_CLASS_COUNT is start number of classes
3382 before reduction. True is returned if there's a merge operation
3386 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3388 unsigned int item_count
= m_items
.length ();
3389 unsigned int class_count
= m_classes_count
;
3390 unsigned int equal_items
= item_count
- class_count
;
3392 unsigned int non_singular_classes_count
= 0;
3393 unsigned int non_singular_classes_sum
= 0;
3395 bool merged_p
= false;
3397 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3398 it
!= m_classes
.end (); ++it
)
3399 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3401 congruence_class
*c
= (*it
)->classes
[i
];
3402 if (c
->members
.length () > 1)
3404 non_singular_classes_count
++;
3405 non_singular_classes_sum
+= c
->members
.length ();
3411 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3412 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3413 prev_class_count
, class_count
);
3414 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3415 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3416 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3417 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3418 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3419 non_singular_classes_count
: 0.0f
,
3420 non_singular_classes_count
);
3421 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3422 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3423 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3426 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3427 it
!= m_classes
.end (); ++it
)
3428 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3430 congruence_class
*c
= (*it
)->classes
[i
];
3432 if (c
->members
.length () == 1)
3435 sem_item
*source
= c
->members
[0];
3437 if (DECL_NAME (source
->decl
)
3438 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3439 /* If merge via wrappers, picking main as the target can be
3441 source
= c
->members
[1];
3443 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3445 sem_item
*alias
= c
->members
[j
];
3447 if (alias
== source
)
3452 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3453 xstrdup_for_dump (source
->node
->name ()),
3454 xstrdup_for_dump (alias
->node
->name ()));
3455 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3456 xstrdup_for_dump (source
->node
->asm_name ()),
3457 xstrdup_for_dump (alias
->node
->asm_name ()));
3460 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3464 "Merge operation is skipped due to no_icf "
3470 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3472 source
->dump_to_file (dump_file
);
3473 alias
->dump_to_file (dump_file
);
3476 if (dbg_cnt (merged_ipa_icf
))
3477 merged_p
|= source
->merge (alias
);
3484 /* Dump function prints all class members to a FILE with an INDENT. */
3487 congruence_class::dump (FILE *file
, unsigned int indent
) const
3489 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3490 id
, members
[0]->get_hash (), members
.length ());
3492 FPUTS_SPACES (file
, indent
+ 2, "");
3493 for (unsigned i
= 0; i
< members
.length (); i
++)
3494 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3495 (void *) members
[i
]->decl
,
3496 members
[i
]->node
->order
);
3498 fprintf (file
, "\n");
3501 /* Returns true if there's a member that is used from another group. */
3504 congruence_class::is_class_used (void)
3506 for (unsigned int i
= 0; i
< members
.length (); i
++)
3507 if (members
[i
]->usages
.length ())
3513 /* Generate pass summary for IPA ICF pass. */
3516 ipa_icf_generate_summary (void)
3519 optimizer
= new sem_item_optimizer ();
3521 optimizer
->register_hooks ();
3522 optimizer
->parse_funcs_and_vars ();
3525 /* Write pass summary for IPA ICF pass. */
3528 ipa_icf_write_summary (void)
3530 gcc_assert (optimizer
);
3532 optimizer
->write_summary ();
3535 /* Read pass summary for IPA ICF pass. */
3538 ipa_icf_read_summary (void)
3541 optimizer
= new sem_item_optimizer ();
3543 optimizer
->read_summary ();
3544 optimizer
->register_hooks ();
3547 /* Semantic equality exection function. */
3550 ipa_icf_driver (void)
3552 gcc_assert (optimizer
);
3554 bool merged_p
= optimizer
->execute ();
3559 return merged_p
? TODO_remove_functions
: 0;
3562 const pass_data pass_data_ipa_icf
=
3564 IPA_PASS
, /* type */
3566 OPTGROUP_IPA
, /* optinfo_flags */
3567 TV_IPA_ICF
, /* tv_id */
3568 0, /* properties_required */
3569 0, /* properties_provided */
3570 0, /* properties_destroyed */
3571 0, /* todo_flags_start */
3572 0, /* todo_flags_finish */
3575 class pass_ipa_icf
: public ipa_opt_pass_d
3578 pass_ipa_icf (gcc::context
*ctxt
)
3579 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3580 ipa_icf_generate_summary
, /* generate_summary */
3581 ipa_icf_write_summary
, /* write_summary */
3582 ipa_icf_read_summary
, /* read_summary */
3584 write_optimization_summary */
3586 read_optimization_summary */
3587 NULL
, /* stmt_fixup */
3588 0, /* function_transform_todo_flags_start */
3589 NULL
, /* function_transform */
3590 NULL
) /* variable_transform */
3593 /* opt_pass methods: */
3594 virtual bool gate (function
*)
3596 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3599 virtual unsigned int execute (function
*)
3601 return ipa_icf_driver();
3603 }; // class pass_ipa_icf
3605 } // ipa_icf namespace
3608 make_pass_ipa_icf (gcc::context
*ctxt
)
3610 return new ipa_icf::pass_ipa_icf (ctxt
);