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.
56 #include "coretypes.h"
62 #include "alloc-pool.h"
63 #include "tree-pass.h"
67 #include "gimple-pretty-print.h"
68 #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
);
1646 /* ... fall through ... */
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
)
1700 sem_function
*f
= new sem_function (node
, 0, stack
);
1707 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1708 return true if phi nodes are semantically equivalent in these blocks . */
1711 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1713 gphi_iterator si1
, si2
;
1715 unsigned size1
, size2
, i
;
1719 gcc_assert (bb1
!= NULL
);
1720 gcc_assert (bb2
!= NULL
);
1722 si2
= gsi_start_phis (bb2
);
1723 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1726 gsi_next_nonvirtual_phi (&si1
);
1727 gsi_next_nonvirtual_phi (&si2
);
1729 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1732 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1733 return return_false();
1738 tree phi_result1
= gimple_phi_result (phi1
);
1739 tree phi_result2
= gimple_phi_result (phi2
);
1741 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1742 return return_false_with_msg ("PHI results are different");
1744 size1
= gimple_phi_num_args (phi1
);
1745 size2
= gimple_phi_num_args (phi2
);
1748 return return_false ();
1750 for (i
= 0; i
< size1
; ++i
)
1752 t1
= gimple_phi_arg (phi1
, i
)->def
;
1753 t2
= gimple_phi_arg (phi2
, i
)->def
;
1755 if (!m_checker
->compare_operand (t1
, t2
))
1756 return return_false ();
1758 e1
= gimple_phi_arg_edge (phi1
, i
);
1759 e2
= gimple_phi_arg_edge (phi2
, i
);
1761 if (!m_checker
->compare_edge (e1
, e2
))
1762 return return_false ();
1771 /* Returns true if tree T can be compared as a handled component. */
1774 sem_function::icf_handled_component_p (tree t
)
1776 tree_code tc
= TREE_CODE (t
);
1778 return (handled_component_p (t
)
1779 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1782 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1783 corresponds to TARGET. */
1786 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1791 if (bb_dict
->length () <= (unsigned)source
)
1792 bb_dict
->safe_grow_cleared (source
+ 1);
1794 if ((*bb_dict
)[source
] == 0)
1796 (*bb_dict
)[source
] = target
;
1800 return (*bb_dict
)[source
] == target
;
1804 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1806 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1810 /* Constructor based on varpool node _NODE with computed hash _HASH.
1811 Bitmap STACK is used for memory allocation. */
1813 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1814 bitmap_obstack
*stack
): sem_item(VAR
,
1817 gcc_checking_assert (node
);
1818 gcc_checking_assert (get_node ());
1821 /* Fast equality function based on knowledge known in WPA. */
1824 sem_variable::equals_wpa (sem_item
*item
,
1825 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1827 gcc_assert (item
->type
== VAR
);
1829 if (node
->num_references () != item
->node
->num_references ())
1830 return return_false_with_msg ("different number of references");
1832 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1833 return return_false_with_msg ("TLS model");
1835 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1836 alignment out of all aliases. */
1838 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1839 return return_false_with_msg ("Virtual flag mismatch");
1841 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1842 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1843 || !operand_equal_p (DECL_SIZE (decl
),
1844 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1845 return return_false_with_msg ("size mismatch");
1847 /* Do not attempt to mix data from different user sections;
1848 we do not know what user intends with those. */
1849 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1850 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1851 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1852 return return_false_with_msg ("user section mismatch");
1854 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1855 return return_false_with_msg ("text section");
1857 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1858 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1860 item
->node
->iterate_reference (i
, ref2
);
1862 if (ref
->use
!= ref2
->use
)
1863 return return_false_with_msg ("reference use mismatch");
1865 if (!compare_symbol_references (ignored_nodes
,
1866 ref
->referred
, ref2
->referred
,
1867 ref
->address_matters_p ()))
1874 /* Returns true if the item equals to ITEM given as argument. */
1877 sem_variable::equals (sem_item
*item
,
1878 hash_map
<symtab_node
*, sem_item
*> &)
1880 gcc_assert (item
->type
== VAR
);
1883 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1884 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1885 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1886 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1888 /* As seen in PR ipa/65303 we have to compare variables types. */
1889 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1890 TREE_TYPE (item
->decl
)))
1891 return return_false_with_msg ("variables types are different");
1893 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1894 DECL_INITIAL (item
->node
->decl
));
1895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1897 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1898 xstrdup_for_dump (node
->name()),
1899 xstrdup_for_dump (item
->node
->name ()),
1900 node
->order
, item
->node
->order
,
1901 xstrdup_for_dump (node
->asm_name ()),
1902 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1907 /* Compares trees T1 and T2 for semantic equality. */
1910 sem_variable::equals (tree t1
, tree t2
)
1913 return return_with_debug (t1
== t2
);
1916 tree_code tc1
= TREE_CODE (t1
);
1917 tree_code tc2
= TREE_CODE (t2
);
1920 return return_false_with_msg ("TREE_CODE mismatch");
1926 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1927 unsigned HOST_WIDE_INT idx
;
1929 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1930 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1931 return return_false_with_msg ("constructor type mismatch");
1933 if (typecode
== ARRAY_TYPE
)
1935 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1936 /* For arrays, check that the sizes all match. */
1937 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1939 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1940 return return_false_with_msg ("constructor array size mismatch");
1942 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1944 return return_false_with_msg ("constructor type incompatible");
1946 v1
= CONSTRUCTOR_ELTS (t1
);
1947 v2
= CONSTRUCTOR_ELTS (t2
);
1948 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1949 return return_false_with_msg ("constructor number of elts mismatch");
1951 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1953 constructor_elt
*c1
= &(*v1
)[idx
];
1954 constructor_elt
*c2
= &(*v2
)[idx
];
1956 /* Check that each value is the same... */
1957 if (!sem_variable::equals (c1
->value
, c2
->value
))
1959 /* ... and that they apply to the same fields! */
1960 if (!sem_variable::equals (c1
->index
, c2
->index
))
1967 tree x1
= TREE_OPERAND (t1
, 0);
1968 tree x2
= TREE_OPERAND (t2
, 0);
1969 tree y1
= TREE_OPERAND (t1
, 1);
1970 tree y2
= TREE_OPERAND (t2
, 1);
1972 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1973 return return_false ();
1975 /* Type of the offset on MEM_REF does not matter. */
1976 return return_with_debug (sem_variable::equals (x1
, x2
)
1977 && wi::to_offset (y1
)
1978 == wi::to_offset (y2
));
1983 tree op1
= TREE_OPERAND (t1
, 0);
1984 tree op2
= TREE_OPERAND (t2
, 0);
1985 return sem_variable::equals (op1
, op2
);
1987 /* References to other vars/decls are compared using ipa-ref. */
1990 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1992 return return_false_with_msg ("Declaration mismatch");
1994 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1995 need to process its VAR/FUNCTION references without relying on ipa-ref
1999 return return_false_with_msg ("Declaration mismatch");
2001 /* Integer constants are the same only if the same width of type. */
2002 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2003 return return_false_with_msg ("INTEGER_CST precision mismatch");
2004 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2005 return return_false_with_msg ("INTEGER_CST mode mismatch");
2006 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2008 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2009 return return_false_with_msg ("STRING_CST mode mismatch");
2010 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2011 return return_false_with_msg ("STRING_CST length mismatch");
2012 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2013 TREE_STRING_LENGTH (t1
)))
2014 return return_false_with_msg ("STRING_CST mismatch");
2017 /* Fixed constants are the same only if the same width of type. */
2018 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2019 return return_false_with_msg ("FIXED_CST precision mismatch");
2021 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2022 TREE_FIXED_CST (t2
)));
2024 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2025 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2027 /* Real constants are the same only if the same width of type. */
2028 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2029 return return_false_with_msg ("REAL_CST precision mismatch");
2030 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2031 &TREE_REAL_CST (t2
)));
2036 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2037 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2039 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2040 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2041 VECTOR_CST_ELT (t2
, i
)))
2047 case ARRAY_RANGE_REF
:
2049 tree x1
= TREE_OPERAND (t1
, 0);
2050 tree x2
= TREE_OPERAND (t2
, 0);
2051 tree y1
= TREE_OPERAND (t1
, 1);
2052 tree y2
= TREE_OPERAND (t2
, 1);
2054 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2056 if (!sem_variable::equals (array_ref_low_bound (t1
),
2057 array_ref_low_bound (t2
)))
2059 if (!sem_variable::equals (array_ref_element_size (t1
),
2060 array_ref_element_size (t2
)))
2066 case POINTER_PLUS_EXPR
:
2071 tree x1
= TREE_OPERAND (t1
, 0);
2072 tree x2
= TREE_OPERAND (t2
, 0);
2073 tree y1
= TREE_OPERAND (t1
, 1);
2074 tree y2
= TREE_OPERAND (t2
, 1);
2076 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2080 case VIEW_CONVERT_EXPR
:
2081 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2082 return return_false ();
2083 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2085 return return_false_with_msg ("ERROR_MARK");
2087 return return_false_with_msg ("Unknown TREE code reached");
2091 /* Parser function that visits a varpool NODE. */
2094 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2096 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2100 sem_variable
*v
= new sem_variable (node
, 0, stack
);
2107 /* References independent hash function. */
2110 sem_variable::get_hash (void)
2115 /* All WPA streamed in symbols should have their hashes computed at compile
2116 time. At this point, the constructor may not be in memory at all.
2117 DECL_INITIAL (decl) would be error_mark_node in that case. */
2118 gcc_assert (!node
->lto_file_data
);
2119 tree ctor
= DECL_INITIAL (decl
);
2120 inchash::hash hstate
;
2122 hstate
.add_int (456346417);
2123 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2124 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2125 add_expr (ctor
, hstate
);
2126 set_hash (hstate
.end ());
2131 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2135 sem_variable::merge (sem_item
*alias_item
)
2137 gcc_assert (alias_item
->type
== VAR
);
2139 if (!sem_item::target_supports_symbol_aliases_p ())
2142 fprintf (dump_file
, "Not unifying; "
2143 "Symbol aliases are not supported by target\n\n");
2147 if (DECL_EXTERNAL (alias_item
->decl
))
2150 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2154 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2156 varpool_node
*original
= get_node ();
2157 varpool_node
*alias
= alias_var
->get_node ();
2158 bool original_discardable
= false;
2160 bool original_address_matters
= original
->address_matters_p ();
2161 bool alias_address_matters
= alias
->address_matters_p ();
2163 /* See if original is in a section that can be discarded if the main
2165 Also consider case where we have resolution info and we know that
2166 original's definition is not going to be used. In this case we can not
2167 create alias to original. */
2168 if (original
->can_be_discarded_p ()
2169 || (node
->resolution
!= LDPR_UNKNOWN
2170 && !decl_binds_to_current_def_p (node
->decl
)))
2171 original_discardable
= true;
2173 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2175 /* Constant pool machinery is not quite ready for aliases.
2176 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2177 For LTO merging does not happen that is an important missing feature.
2178 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2179 flag is dropped and non-local symbol name is assigned. */
2180 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2181 || DECL_IN_CONSTANT_POOL (original
->decl
))
2185 "Not unifying; constant pool variables.\n\n");
2189 /* Do not attempt to mix functions from different user sections;
2190 we do not know what user intends with those. */
2191 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2192 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2193 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2198 "original and alias are in different sections.\n\n");
2202 /* We can not merge if address comparsion metters. */
2203 if (original_address_matters
&& alias_address_matters
2204 && flag_merge_constants
< 2)
2209 "adress of original and alias may be compared.\n\n");
2213 if (DECL_ALIGN (original
->decl
) < DECL_ALIGN (alias
->decl
))
2216 fprintf (dump_file
, "Not unifying; "
2217 "original and alias have incompatible alignments\n\n");
2222 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2225 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2226 "across comdat group boundary\n\n");
2231 if (original_discardable
)
2234 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2235 "target is discardable\n\n");
2241 gcc_assert (!original
->alias
);
2242 gcc_assert (!alias
->alias
);
2244 alias
->analyzed
= false;
2246 DECL_INITIAL (alias
->decl
) = NULL
;
2247 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2249 alias
->need_bounds_init
= false;
2250 alias
->remove_all_references ();
2251 if (TREE_ADDRESSABLE (alias
->decl
))
2252 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2254 varpool_node::create_alias (alias_var
->decl
, decl
);
2255 alias
->resolve_alias (original
);
2258 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
2264 /* Dump symbol to FILE. */
2267 sem_variable::dump_to_file (FILE *file
)
2271 print_node (file
, "", decl
, 0);
2272 fprintf (file
, "\n\n");
2275 unsigned int sem_item_optimizer::class_id
= 0;
2277 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2278 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2281 bitmap_obstack_initialize (&m_bmstack
);
2284 sem_item_optimizer::~sem_item_optimizer ()
2286 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2289 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2290 it
!= m_classes
.end (); ++it
)
2292 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2293 delete (*it
)->classes
[i
];
2295 (*it
)->classes
.release ();
2301 bitmap_obstack_release (&m_bmstack
);
2304 /* Write IPA ICF summary for symbols. */
2307 sem_item_optimizer::write_summary (void)
2309 unsigned int count
= 0;
2311 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2312 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2315 /* Calculate number of symbols to be serialized. */
2316 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2318 lsei_next_in_partition (&lsei
))
2320 symtab_node
*node
= lsei_node (lsei
);
2322 if (m_symtab_node_map
.get (node
))
2326 streamer_write_uhwi (ob
, count
);
2328 /* Process all of the symbols. */
2329 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2331 lsei_next_in_partition (&lsei
))
2333 symtab_node
*node
= lsei_node (lsei
);
2335 sem_item
**item
= m_symtab_node_map
.get (node
);
2339 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2340 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2342 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2346 streamer_write_char_stream (ob
->main_stream
, 0);
2347 produce_asm (ob
, NULL
);
2348 destroy_output_block (ob
);
2351 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2352 contains LEN bytes. */
2355 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2356 const char *data
, size_t len
)
2358 const lto_function_header
*header
=
2359 (const lto_function_header
*) data
;
2360 const int cfg_offset
= sizeof (lto_function_header
);
2361 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2362 const int string_offset
= main_offset
+ header
->main_size
;
2367 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2368 header
->main_size
, file_data
->mode_table
);
2371 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2372 header
->string_size
, vNULL
);
2374 count
= streamer_read_uhwi (&ib_main
);
2376 for (i
= 0; i
< count
; i
++)
2380 lto_symtab_encoder_t encoder
;
2382 index
= streamer_read_uhwi (&ib_main
);
2383 encoder
= file_data
->symtab_node_encoder
;
2384 node
= lto_symtab_encoder_deref (encoder
, index
);
2386 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2388 gcc_assert (node
->definition
);
2391 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2392 node
->asm_name (), (void *) node
->decl
, node
->order
);
2394 if (is_a
<cgraph_node
*> (node
))
2396 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2398 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2402 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2404 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2408 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2410 lto_data_in_delete (data_in
);
2413 /* Read IPA ICF summary for symbols. */
2416 sem_item_optimizer::read_summary (void)
2418 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2419 lto_file_decl_data
*file_data
;
2422 while ((file_data
= file_data_vec
[j
++]))
2425 const char *data
= lto_get_section_data (file_data
,
2426 LTO_section_ipa_icf
, NULL
, &len
);
2429 read_section (file_data
, data
, len
);
2433 /* Register callgraph and varpool hooks. */
2436 sem_item_optimizer::register_hooks (void)
2438 if (!m_cgraph_node_hooks
)
2439 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2440 (&sem_item_optimizer::cgraph_removal_hook
, this);
2442 if (!m_varpool_node_hooks
)
2443 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2444 (&sem_item_optimizer::varpool_removal_hook
, this);
2447 /* Unregister callgraph and varpool hooks. */
2450 sem_item_optimizer::unregister_hooks (void)
2452 if (m_cgraph_node_hooks
)
2453 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2455 if (m_varpool_node_hooks
)
2456 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2459 /* Adds a CLS to hashtable associated by hash value. */
2462 sem_item_optimizer::add_class (congruence_class
*cls
)
2464 gcc_assert (cls
->members
.length ());
2466 congruence_class_group
*group
= get_group_by_hash (
2467 cls
->members
[0]->get_hash (),
2468 cls
->members
[0]->type
);
2469 group
->classes
.safe_push (cls
);
2472 /* Gets a congruence class group based on given HASH value and TYPE. */
2474 congruence_class_group
*
2475 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2477 congruence_class_group
*item
= XNEW (congruence_class_group
);
2481 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2487 item
->classes
.create (1);
2494 /* Callgraph removal hook called for a NODE with a custom DATA. */
2497 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2499 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2500 optimizer
->remove_symtab_node (node
);
2503 /* Varpool removal hook called for a NODE with a custom DATA. */
2506 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2508 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2509 optimizer
->remove_symtab_node (node
);
2512 /* Remove symtab NODE triggered by symtab removal hooks. */
2515 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2517 gcc_assert (!m_classes
.elements());
2519 m_removed_items_set
.add (node
);
2523 sem_item_optimizer::remove_item (sem_item
*item
)
2525 if (m_symtab_node_map
.get (item
->node
))
2526 m_symtab_node_map
.remove (item
->node
);
2530 /* Removes all callgraph and varpool nodes that are marked by symtab
2534 sem_item_optimizer::filter_removed_items (void)
2536 auto_vec
<sem_item
*> filtered
;
2538 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2540 sem_item
*item
= m_items
[i
];
2542 if (m_removed_items_set
.contains (item
->node
))
2548 if (item
->type
== FUNC
)
2550 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2552 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2555 filtered
.safe_push (item
);
2559 if (!flag_ipa_icf_variables
)
2563 /* Filter out non-readonly variables. */
2564 tree decl
= item
->decl
;
2565 if (TREE_READONLY (decl
))
2566 filtered
.safe_push (item
);
2573 /* Clean-up of released semantic items. */
2576 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2577 m_items
.safe_push (filtered
[i
]);
2580 /* Optimizer entry point which returns true in case it processes
2581 a merge operation. True is returned if there's a merge operation
2585 sem_item_optimizer::execute (void)
2587 filter_removed_items ();
2588 unregister_hooks ();
2591 update_hash_by_addr_refs ();
2592 build_hash_based_classes ();
2595 fprintf (dump_file
, "Dump after hash based groups\n");
2596 dump_cong_classes ();
2598 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2599 m_items
[i
]->init_wpa ();
2601 subdivide_classes_by_equality (true);
2604 fprintf (dump_file
, "Dump after WPA based types groups\n");
2606 dump_cong_classes ();
2608 process_cong_reduction ();
2609 checking_verify_classes ();
2612 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2614 dump_cong_classes ();
2616 parse_nonsingleton_classes ();
2617 subdivide_classes_by_equality ();
2620 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2622 dump_cong_classes ();
2624 unsigned int prev_class_count
= m_classes_count
;
2626 process_cong_reduction ();
2627 dump_cong_classes ();
2628 checking_verify_classes ();
2629 bool merged_p
= merge_classes (prev_class_count
);
2631 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2632 symtab_node::dump_table (dump_file
);
2637 /* Function responsible for visiting all potential functions and
2638 read-only variables that can be merged. */
2641 sem_item_optimizer::parse_funcs_and_vars (void)
2645 if (flag_ipa_icf_functions
)
2646 FOR_EACH_DEFINED_FUNCTION (cnode
)
2648 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2651 m_items
.safe_push (f
);
2652 m_symtab_node_map
.put (cnode
, f
);
2655 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2658 f
->dump_to_file (dump_file
);
2661 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2664 varpool_node
*vnode
;
2666 if (flag_ipa_icf_variables
)
2667 FOR_EACH_DEFINED_VARIABLE (vnode
)
2669 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2673 m_items
.safe_push (v
);
2674 m_symtab_node_map
.put (vnode
, v
);
2679 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2682 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2684 item
->index_in_class
= cls
->members
.length ();
2685 cls
->members
.safe_push (item
);
2689 /* For each semantic item, append hash values of references. */
2692 sem_item_optimizer::update_hash_by_addr_refs ()
2694 /* First, append to hash sensitive references and class type if it need to
2695 be matched for ODR. */
2696 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2698 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2699 if (m_items
[i
]->type
== FUNC
)
2701 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2702 && contains_polymorphic_type_p
2703 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2704 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2705 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2706 && static_cast<sem_function
*> (m_items
[i
])
2707 ->compare_polymorphic_p ())))
2710 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2711 inchash::hash
hstate (m_items
[i
]->get_hash ());
2713 if (TYPE_NAME (class_type
)
2714 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2716 (IDENTIFIER_HASH_VALUE
2717 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2719 m_items
[i
]->set_hash (hstate
.end ());
2724 /* Once all symbols have enhanced hash value, we can append
2725 hash values of symbols that are seen by IPA ICF and are
2726 references by a semantic item. Newly computed values
2727 are saved to global_hash member variable. */
2728 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2729 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2731 /* Global hash value replace current hash values. */
2732 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2733 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2736 /* Congruence classes are built by hash value. */
2739 sem_item_optimizer::build_hash_based_classes (void)
2741 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2743 sem_item
*item
= m_items
[i
];
2745 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2748 if (!group
->classes
.length ())
2751 group
->classes
.safe_push (new congruence_class (class_id
++));
2754 add_item_to_class (group
->classes
[0], item
);
2758 /* Build references according to call graph. */
2761 sem_item_optimizer::build_graph (void)
2763 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2765 sem_item
*item
= m_items
[i
];
2766 m_symtab_node_map
.put (item
->node
, item
);
2768 /* Initialize hash values if we are not in LTO mode. */
2773 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2775 sem_item
*item
= m_items
[i
];
2777 if (item
->type
== FUNC
)
2779 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2781 cgraph_edge
*e
= cnode
->callees
;
2784 sem_item
**slot
= m_symtab_node_map
.get
2785 (e
->callee
->ultimate_alias_target ());
2787 item
->add_reference (*slot
);
2793 ipa_ref
*ref
= NULL
;
2794 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2796 sem_item
**slot
= m_symtab_node_map
.get
2797 (ref
->referred
->ultimate_alias_target ());
2799 item
->add_reference (*slot
);
2804 /* Semantic items in classes having more than one element and initialized.
2805 In case of WPA, we load function body. */
2808 sem_item_optimizer::parse_nonsingleton_classes (void)
2810 unsigned int init_called_count
= 0;
2812 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2813 if (m_items
[i
]->cls
->members
.length () > 1)
2815 m_items
[i
]->init ();
2816 init_called_count
++;
2820 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2821 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2824 /* Equality function for semantic items is used to subdivide existing
2825 classes. If IN_WPA, fast equality function is invoked. */
2828 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2830 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2831 it
!= m_classes
.end (); ++it
)
2833 unsigned int class_count
= (*it
)->classes
.length ();
2835 for (unsigned i
= 0; i
< class_count
; i
++)
2837 congruence_class
*c
= (*it
)->classes
[i
];
2839 if (c
->members
.length() > 1)
2841 auto_vec
<sem_item
*> new_vector
;
2843 sem_item
*first
= c
->members
[0];
2844 new_vector
.safe_push (first
);
2846 unsigned class_split_first
= (*it
)->classes
.length ();
2848 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2850 sem_item
*item
= c
->members
[j
];
2852 bool equals
= in_wpa
? first
->equals_wpa (item
,
2853 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2856 new_vector
.safe_push (item
);
2859 bool integrated
= false;
2861 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2863 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2864 bool equals
= in_wpa
? x
->equals_wpa (item
,
2865 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2870 add_item_to_class ((*it
)->classes
[k
], item
);
2878 congruence_class
*c
= new congruence_class (class_id
++);
2880 add_item_to_class (c
, item
);
2882 (*it
)->classes
.safe_push (c
);
2887 // we replace newly created new_vector for the class we've just splitted
2888 c
->members
.release ();
2889 c
->members
.create (new_vector
.length ());
2891 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2892 add_item_to_class (c
, new_vector
[j
]);
2897 checking_verify_classes ();
2900 /* Subdivide classes by address references that members of the class
2901 reference. Example can be a pair of functions that have an address
2902 taken from a function. If these addresses are different the class
2906 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2908 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2910 unsigned newly_created_classes
= 0;
2912 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2913 it
!= m_classes
.end (); ++it
)
2915 unsigned int class_count
= (*it
)->classes
.length ();
2916 auto_vec
<congruence_class
*> new_classes
;
2918 for (unsigned i
= 0; i
< class_count
; i
++)
2920 congruence_class
*c
= (*it
)->classes
[i
];
2922 if (c
->members
.length() > 1)
2924 subdivide_hash_map split_map
;
2926 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2928 sem_item
*source_node
= c
->members
[j
];
2930 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2933 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2935 gcc_checking_assert (slot
);
2937 slot
->safe_push (source_node
);
2943 /* If the map contains more than one key, we have to split the map
2945 if (split_map
.elements () != 1)
2947 bool first_class
= true;
2949 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2950 it2
!= split_map
.end (); ++it2
)
2952 congruence_class
*new_cls
;
2953 new_cls
= new congruence_class (class_id
++);
2955 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2956 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2958 worklist_push (new_cls
);
2959 newly_created_classes
++;
2963 (*it
)->classes
[i
] = new_cls
;
2964 first_class
= false;
2968 new_classes
.safe_push (new_cls
);
2974 /* Release memory. */
2975 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2976 it2
!= split_map
.end (); ++it2
)
2978 delete (*it2
).first
;
2979 (*it2
).second
.release ();
2984 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2985 (*it
)->classes
.safe_push (new_classes
[i
]);
2988 return newly_created_classes
;
2991 /* Verify congruence classes, if checking is enabled. */
2994 sem_item_optimizer::checking_verify_classes (void)
3000 /* Verify congruence classes. */
3003 sem_item_optimizer::verify_classes (void)
3005 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3006 it
!= m_classes
.end (); ++it
)
3008 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3010 congruence_class
*cls
= (*it
)->classes
[i
];
3013 gcc_assert (cls
->members
.length () > 0);
3015 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3017 sem_item
*item
= cls
->members
[j
];
3020 gcc_assert (item
->cls
== cls
);
3022 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3024 sem_usage_pair
*usage
= item
->usages
[k
];
3025 gcc_assert (usage
->item
->index_in_class
<
3026 usage
->item
->cls
->members
.length ());
3033 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3034 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3035 but unused argument. */
3038 sem_item_optimizer::release_split_map (congruence_class
* const &,
3039 bitmap
const &b
, traverse_split_pair
*)
3048 /* Process split operation for a class given as pointer CLS_PTR,
3049 where bitmap B splits congruence class members. DATA is used
3050 as argument of split pair. */
3053 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3054 bitmap
const &b
, traverse_split_pair
*pair
)
3056 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3057 const congruence_class
*splitter_cls
= pair
->cls
;
3059 /* If counted bits are greater than zero and less than the number of members
3060 a group will be splitted. */
3061 unsigned popcount
= bitmap_count_bits (b
);
3063 if (popcount
> 0 && popcount
< cls
->members
.length ())
3065 auto_vec
<congruence_class
*, 2> newclasses
;
3066 newclasses
.quick_push (new congruence_class (class_id
++));
3067 newclasses
.quick_push (new congruence_class (class_id
++));
3069 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3071 int target
= bitmap_bit_p (b
, i
);
3072 congruence_class
*tc
= newclasses
[target
];
3074 add_item_to_class (tc
, cls
->members
[i
]);
3079 for (unsigned int i
= 0; i
< 2; i
++)
3080 gcc_assert (newclasses
[i
]->members
.length ());
3083 if (splitter_cls
== cls
)
3084 optimizer
->splitter_class_removed
= true;
3086 /* Remove old class from worklist if presented. */
3087 bool in_worklist
= cls
->in_worklist
;
3090 cls
->in_worklist
= false;
3092 congruence_class_group g
;
3093 g
.hash
= cls
->members
[0]->get_hash ();
3094 g
.type
= cls
->members
[0]->type
;
3096 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3098 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3099 if (slot
->classes
[i
] == cls
)
3101 slot
->classes
.ordered_remove (i
);
3105 /* New class will be inserted and integrated to work list. */
3106 for (unsigned int i
= 0; i
< 2; i
++)
3107 optimizer
->add_class (newclasses
[i
]);
3109 /* Two classes replace one, so that increment just by one. */
3110 optimizer
->m_classes_count
++;
3112 /* If OLD class was presented in the worklist, we remove the class
3113 and replace it will both newly created classes. */
3115 for (unsigned int i
= 0; i
< 2; i
++)
3116 optimizer
->worklist_push (newclasses
[i
]);
3117 else /* Just smaller class is inserted. */
3119 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3120 newclasses
[1]->members
.length () ?
3122 optimizer
->worklist_push (newclasses
[smaller_index
]);
3125 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3127 fprintf (dump_file
, " congruence class splitted:\n");
3128 cls
->dump (dump_file
, 4);
3130 fprintf (dump_file
, " newly created groups:\n");
3131 for (unsigned int i
= 0; i
< 2; i
++)
3132 newclasses
[i
]->dump (dump_file
, 4);
3135 /* Release class if not presented in work list. */
3144 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3145 Bitmap stack BMSTACK is used for bitmap allocation. */
3148 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3151 hash_map
<congruence_class
*, bitmap
> split_map
;
3153 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3155 sem_item
*item
= cls
->members
[i
];
3157 /* Iterate all usages that have INDEX as usage of the item. */
3158 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3160 sem_usage_pair
*usage
= item
->usages
[j
];
3162 if (usage
->index
!= index
)
3165 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3170 b
= BITMAP_ALLOC (&m_bmstack
);
3171 split_map
.put (usage
->item
->cls
, b
);
3176 gcc_checking_assert (usage
->item
->cls
);
3177 gcc_checking_assert (usage
->item
->index_in_class
<
3178 usage
->item
->cls
->members
.length ());
3180 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3184 traverse_split_pair pair
;
3185 pair
.optimizer
= this;
3188 splitter_class_removed
= false;
3190 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3192 /* Bitmap clean-up. */
3194 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3197 /* Every usage of a congruence class CLS is a candidate that can split the
3198 collection of classes. Bitmap stack BMSTACK is used for bitmap
3202 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3207 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3209 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3210 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3212 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3215 fprintf (dump_file
, " processing congruence step for class: %u, index: %u\n",
3218 do_congruence_step_for_index (cls
, i
);
3220 if (splitter_class_removed
)
3224 BITMAP_FREE (usage
);
3227 /* Adds a newly created congruence class CLS to worklist. */
3230 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3232 /* Return if the class CLS is already presented in work list. */
3233 if (cls
->in_worklist
)
3236 cls
->in_worklist
= true;
3237 worklist
.push_back (cls
);
3240 /* Pops a class from worklist. */
3243 sem_item_optimizer::worklist_pop (void)
3245 congruence_class
*cls
;
3247 while (!worklist
.empty ())
3249 cls
= worklist
.front ();
3250 worklist
.pop_front ();
3251 if (cls
->in_worklist
)
3253 cls
->in_worklist
= false;
3259 /* Work list item was already intended to be removed.
3260 The only reason for doing it is to split a class.
3261 Thus, the class CLS is deleted. */
3269 /* Iterative congruence reduction function. */
3272 sem_item_optimizer::process_cong_reduction (void)
3274 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3275 it
!= m_classes
.end (); ++it
)
3276 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3277 if ((*it
)->classes
[i
]->is_class_used ())
3278 worklist_push ((*it
)->classes
[i
]);
3281 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3282 (unsigned long) worklist
.size ());
3284 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3285 fprintf (dump_file
, "Congruence class reduction\n");
3287 congruence_class
*cls
;
3289 /* Process complete congruence reduction. */
3290 while ((cls
= worklist_pop ()) != NULL
)
3291 do_congruence_step (cls
);
3293 /* Subdivide newly created classes according to references. */
3294 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3297 fprintf (dump_file
, "Address reference subdivision created: %u "
3298 "new classes.\n", new_classes
);
3301 /* Debug function prints all informations about congruence classes. */
3304 sem_item_optimizer::dump_cong_classes (void)
3310 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3311 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3313 /* Histogram calculation. */
3314 unsigned int max_index
= 0;
3315 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3317 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3318 it
!= m_classes
.end (); ++it
)
3320 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3322 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3330 "Class size histogram [num of members]: number of classe number of classess\n");
3332 for (unsigned int i
= 0; i
<= max_index
; i
++)
3334 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3336 fprintf (dump_file
, "\n\n");
3339 if (dump_flags
& TDF_DETAILS
)
3340 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3341 it
!= m_classes
.end (); ++it
)
3343 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3345 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3347 (*it
)->classes
[i
]->dump (dump_file
, 4);
3349 if(i
< (*it
)->classes
.length () - 1)
3350 fprintf (dump_file
, " ");
3357 /* After reduction is done, we can declare all items in a group
3358 to be equal. PREV_CLASS_COUNT is start number of classes
3359 before reduction. True is returned if there's a merge operation
3363 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3365 unsigned int item_count
= m_items
.length ();
3366 unsigned int class_count
= m_classes_count
;
3367 unsigned int equal_items
= item_count
- class_count
;
3369 unsigned int non_singular_classes_count
= 0;
3370 unsigned int non_singular_classes_sum
= 0;
3372 bool merged_p
= false;
3374 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3375 it
!= m_classes
.end (); ++it
)
3376 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3378 congruence_class
*c
= (*it
)->classes
[i
];
3379 if (c
->members
.length () > 1)
3381 non_singular_classes_count
++;
3382 non_singular_classes_sum
+= c
->members
.length ();
3388 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3389 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3390 prev_class_count
, class_count
);
3391 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3392 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3393 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3394 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3395 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3396 non_singular_classes_count
: 0.0f
,
3397 non_singular_classes_count
);
3398 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3399 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3400 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3403 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3404 it
!= m_classes
.end (); ++it
)
3405 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3407 congruence_class
*c
= (*it
)->classes
[i
];
3409 if (c
->members
.length () == 1)
3412 sem_item
*source
= c
->members
[0];
3414 if (DECL_NAME (source
->decl
)
3415 && MAIN_NAME_P (DECL_NAME (source
->decl
)))
3416 /* If merge via wrappers, picking main as the target can be
3418 source
= c
->members
[1];
3420 for (unsigned int j
= 0; j
< c
->members
.length (); j
++)
3422 sem_item
*alias
= c
->members
[j
];
3424 if (alias
== source
)
3429 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3430 xstrdup_for_dump (source
->node
->name ()),
3431 xstrdup_for_dump (alias
->node
->name ()));
3432 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3433 xstrdup_for_dump (source
->node
->asm_name ()),
3434 xstrdup_for_dump (alias
->node
->asm_name ()));
3437 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3441 "Merge operation is skipped due to no_icf "
3447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3449 source
->dump_to_file (dump_file
);
3450 alias
->dump_to_file (dump_file
);
3453 if (dbg_cnt (merged_ipa_icf
))
3454 merged_p
|= source
->merge (alias
);
3461 /* Dump function prints all class members to a FILE with an INDENT. */
3464 congruence_class::dump (FILE *file
, unsigned int indent
) const
3466 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3467 id
, members
[0]->get_hash (), members
.length ());
3469 FPUTS_SPACES (file
, indent
+ 2, "");
3470 for (unsigned i
= 0; i
< members
.length (); i
++)
3471 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3472 (void *) members
[i
]->decl
,
3473 members
[i
]->node
->order
);
3475 fprintf (file
, "\n");
3478 /* Returns true if there's a member that is used from another group. */
3481 congruence_class::is_class_used (void)
3483 for (unsigned int i
= 0; i
< members
.length (); i
++)
3484 if (members
[i
]->usages
.length ())
3490 /* Generate pass summary for IPA ICF pass. */
3493 ipa_icf_generate_summary (void)
3496 optimizer
= new sem_item_optimizer ();
3498 optimizer
->register_hooks ();
3499 optimizer
->parse_funcs_and_vars ();
3502 /* Write pass summary for IPA ICF pass. */
3505 ipa_icf_write_summary (void)
3507 gcc_assert (optimizer
);
3509 optimizer
->write_summary ();
3512 /* Read pass summary for IPA ICF pass. */
3515 ipa_icf_read_summary (void)
3518 optimizer
= new sem_item_optimizer ();
3520 optimizer
->read_summary ();
3521 optimizer
->register_hooks ();
3524 /* Semantic equality exection function. */
3527 ipa_icf_driver (void)
3529 gcc_assert (optimizer
);
3531 bool merged_p
= optimizer
->execute ();
3536 return merged_p
? TODO_remove_functions
: 0;
3539 const pass_data pass_data_ipa_icf
=
3541 IPA_PASS
, /* type */
3543 OPTGROUP_IPA
, /* optinfo_flags */
3544 TV_IPA_ICF
, /* tv_id */
3545 0, /* properties_required */
3546 0, /* properties_provided */
3547 0, /* properties_destroyed */
3548 0, /* todo_flags_start */
3549 0, /* todo_flags_finish */
3552 class pass_ipa_icf
: public ipa_opt_pass_d
3555 pass_ipa_icf (gcc::context
*ctxt
)
3556 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3557 ipa_icf_generate_summary
, /* generate_summary */
3558 ipa_icf_write_summary
, /* write_summary */
3559 ipa_icf_read_summary
, /* read_summary */
3561 write_optimization_summary */
3563 read_optimization_summary */
3564 NULL
, /* stmt_fixup */
3565 0, /* function_transform_todo_flags_start */
3566 NULL
, /* function_transform */
3567 NULL
) /* variable_transform */
3570 /* opt_pass methods: */
3571 virtual bool gate (function
*)
3573 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3576 virtual unsigned int execute (function
*)
3578 return ipa_icf_driver();
3580 }; // class pass_ipa_icf
3582 } // ipa_icf namespace
3585 make_pass_ipa_icf (gcc::context
*ctxt
)
3587 return new ipa_icf::pass_ipa_icf (ctxt
);