1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2015 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 && !alias
->has_aliases_p ())
1310 create_wrapper
= false;
1313 gcc_assert (!create_alias
);
1315 else if (create_alias
)
1317 alias
->icf_merged
= true;
1319 /* Remove the function's body. */
1320 ipa_merge_profiles (original
, alias
);
1321 alias
->release_body (true);
1323 /* Notice global symbol possibly produced RTL. */
1324 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1327 /* Create the alias. */
1328 cgraph_node::create_alias (alias_func
->decl
, decl
);
1329 alias
->resolve_alias (original
);
1331 original
->call_for_symbol_thunks_and_aliases
1332 (set_local
, (void *)(size_t) original
->local_p (), true);
1335 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1339 gcc_assert (!create_alias
);
1340 alias
->icf_merged
= true;
1341 local_original
->icf_merged
= true;
1343 ipa_merge_profiles (local_original
, alias
, true);
1344 alias
->create_wrapper (local_original
);
1347 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1350 /* It's possible that redirection can hit thunks that block
1351 redirection opportunities. */
1352 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1353 original
->icf_merged
= true;
1355 /* Inform the inliner about cross-module merging. */
1356 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1357 && original
->lto_file_data
!= alias
->lto_file_data
)
1358 local_original
->merged
= original
->merged
= true;
1362 ipa_merge_profiles (original
, alias
);
1363 alias
->release_body ();
1365 alias
->body_removed
= true;
1366 alias
->icf_merged
= true;
1368 fprintf (dump_file
, "Unified; Function body was removed.\n");
1374 /* Semantic item initialization function. */
1377 sem_function::init (void)
1380 get_node ()->get_untransformed_body ();
1382 tree fndecl
= node
->decl
;
1383 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1386 gcc_assert (SSANAMES (func
));
1388 ssa_names_size
= SSANAMES (func
)->length ();
1392 region_tree
= func
->eh
->region_tree
;
1394 /* iterating all function arguments. */
1395 arg_count
= count_formal_params (fndecl
);
1397 edge_count
= n_edges_for_fn (func
);
1398 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1399 if (!cnode
->thunk
.thunk_p
)
1401 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1403 inchash::hash hstate
;
1406 FOR_EACH_BB_FN (bb
, func
)
1408 unsigned nondbg_stmt_count
= 0;
1411 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1413 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1416 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1419 gimple
*stmt
= gsi_stmt (gsi
);
1421 if (gimple_code (stmt
) != GIMPLE_DEBUG
1422 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1424 hash_stmt (stmt
, hstate
);
1425 nondbg_stmt_count
++;
1429 gcode_hash
= hstate
.end ();
1430 bb_sizes
.safe_push (nondbg_stmt_count
);
1432 /* Inserting basic block to hash table. */
1433 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1434 EDGE_COUNT (bb
->preds
)
1435 + EDGE_COUNT (bb
->succs
));
1437 bb_sorted
.safe_push (semantic_bb
);
1443 inchash::hash hstate
;
1444 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1445 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1446 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1447 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1448 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1449 gcode_hash
= hstate
.end ();
1453 /* Accumulate to HSTATE a hash of expression EXP.
1454 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1455 and DECL equality classes. */
1458 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1460 if (exp
== NULL_TREE
)
1462 hstate
.merge_hash (0);
1466 /* Handled component can be matched in a cureful way proving equivalence
1467 even if they syntactically differ. Just skip them. */
1469 while (handled_component_p (exp
))
1470 exp
= TREE_OPERAND (exp
, 0);
1472 enum tree_code code
= TREE_CODE (exp
);
1473 hstate
.add_int (code
);
1477 /* Use inchash::add_expr for everything that is LTO stable. */
1485 inchash::add_expr (exp
, hstate
);
1489 unsigned HOST_WIDE_INT idx
;
1492 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1494 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1496 add_expr (value
, hstate
);
1501 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1507 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1510 case POINTER_PLUS_EXPR
:
1513 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1514 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1518 inchash::hash one
, two
;
1519 add_expr (TREE_OPERAND (exp
, 0), one
);
1520 add_expr (TREE_OPERAND (exp
, 1), two
);
1521 hstate
.add_commutative (one
, two
);
1525 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1526 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1532 /* Accumulate to HSTATE a hash of type t.
1533 TYpes that may end up being compatible after LTO type merging needs to have
1537 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1539 if (type
== NULL_TREE
)
1541 hstate
.merge_hash (0);
1545 type
= TYPE_MAIN_VARIANT (type
);
1547 hstate
.add_int (TYPE_MODE (type
));
1549 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1551 hstate
.add_int (COMPLEX_TYPE
);
1552 sem_item::add_type (TREE_TYPE (type
), hstate
);
1554 else if (INTEGRAL_TYPE_P (type
))
1556 hstate
.add_int (INTEGER_TYPE
);
1557 hstate
.add_flag (TYPE_UNSIGNED (type
));
1558 hstate
.add_int (TYPE_PRECISION (type
));
1560 else if (VECTOR_TYPE_P (type
))
1562 hstate
.add_int (VECTOR_TYPE
);
1563 hstate
.add_int (TYPE_PRECISION (type
));
1564 sem_item::add_type (TREE_TYPE (type
), hstate
);
1566 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1568 hstate
.add_int (ARRAY_TYPE
);
1569 /* Do not hash size, so complete and incomplete types can match. */
1570 sem_item::add_type (TREE_TYPE (type
), hstate
);
1572 else if (RECORD_OR_UNION_TYPE_P (type
))
1574 gcc_checking_assert (COMPLETE_TYPE_P (type
));
1575 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1579 inchash::hash hstate2
;
1584 hstate2
.add_int (RECORD_TYPE
);
1585 gcc_assert (COMPLETE_TYPE_P (type
));
1587 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1588 if (TREE_CODE (f
) == FIELD_DECL
)
1590 add_type (TREE_TYPE (f
), hstate2
);
1594 hstate2
.add_int (nf
);
1595 hash
= hstate2
.end ();
1596 hstate
.add_wide_int (hash
);
1597 optimizer
->m_type_hash_cache
.put (type
, hash
);
1600 hstate
.add_wide_int (*val
);
1604 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1607 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1609 enum gimple_code code
= gimple_code (stmt
);
1611 hstate
.add_int (code
);
1616 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1619 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1620 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1621 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1623 inchash::hash one
, two
;
1625 add_expr (gimple_assign_rhs1 (stmt
), one
);
1626 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1627 add_expr (gimple_assign_rhs2 (stmt
), two
);
1628 hstate
.add_commutative (one
, two
);
1629 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1631 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1632 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1634 add_expr (gimple_assign_lhs (stmt
), hstate
);
1635 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1638 /* ... fall through ... */
1644 /* All these statements are equivalent if their operands are. */
1645 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1647 add_expr (gimple_op (stmt
, i
), hstate
);
1648 if (gimple_op (stmt
, i
))
1649 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1657 /* Return true if polymorphic comparison must be processed. */
1660 sem_function::compare_polymorphic_p (void)
1662 struct cgraph_edge
*e
;
1664 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1666 if (get_node ()->indirect_calls
!= NULL
)
1668 /* TODO: We can do simple propagation determining what calls may lead to
1669 a polymorphic call. */
1670 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1671 if (e
->callee
->definition
1672 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1677 /* For a given call graph NODE, the function constructs new
1678 semantic function item. */
1681 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1683 tree fndecl
= node
->decl
;
1684 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1686 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1689 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1692 sem_function
*f
= new sem_function (node
, 0, stack
);
1699 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1700 return true if phi nodes are semantically equivalent in these blocks . */
1703 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1705 gphi_iterator si1
, si2
;
1707 unsigned size1
, size2
, i
;
1711 gcc_assert (bb1
!= NULL
);
1712 gcc_assert (bb2
!= NULL
);
1714 si2
= gsi_start_phis (bb2
);
1715 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1718 gsi_next_nonvirtual_phi (&si1
);
1719 gsi_next_nonvirtual_phi (&si2
);
1721 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1724 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1725 return return_false();
1730 tree phi_result1
= gimple_phi_result (phi1
);
1731 tree phi_result2
= gimple_phi_result (phi2
);
1733 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1734 return return_false_with_msg ("PHI results are different");
1736 size1
= gimple_phi_num_args (phi1
);
1737 size2
= gimple_phi_num_args (phi2
);
1740 return return_false ();
1742 for (i
= 0; i
< size1
; ++i
)
1744 t1
= gimple_phi_arg (phi1
, i
)->def
;
1745 t2
= gimple_phi_arg (phi2
, i
)->def
;
1747 if (!m_checker
->compare_operand (t1
, t2
))
1748 return return_false ();
1750 e1
= gimple_phi_arg_edge (phi1
, i
);
1751 e2
= gimple_phi_arg_edge (phi2
, i
);
1753 if (!m_checker
->compare_edge (e1
, e2
))
1754 return return_false ();
1763 /* Returns true if tree T can be compared as a handled component. */
1766 sem_function::icf_handled_component_p (tree t
)
1768 tree_code tc
= TREE_CODE (t
);
1770 return (handled_component_p (t
)
1771 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1774 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1775 corresponds to TARGET. */
1778 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1783 if (bb_dict
->length () <= (unsigned)source
)
1784 bb_dict
->safe_grow_cleared (source
+ 1);
1786 if ((*bb_dict
)[source
] == 0)
1788 (*bb_dict
)[source
] = target
;
1792 return (*bb_dict
)[source
] == target
;
1796 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1798 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1802 /* Constructor based on varpool node _NODE with computed hash _HASH.
1803 Bitmap STACK is used for memory allocation. */
1805 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1806 bitmap_obstack
*stack
): sem_item(VAR
,
1809 gcc_checking_assert (node
);
1810 gcc_checking_assert (get_node ());
1813 /* Fast equality function based on knowledge known in WPA. */
1816 sem_variable::equals_wpa (sem_item
*item
,
1817 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1819 gcc_assert (item
->type
== VAR
);
1821 if (node
->num_references () != item
->node
->num_references ())
1822 return return_false_with_msg ("different number of references");
1824 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1825 return return_false_with_msg ("TLS model");
1827 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1828 alignment out of all aliases. */
1830 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1831 return return_false_with_msg ("Virtual flag mismatch");
1833 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1834 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1835 || !operand_equal_p (DECL_SIZE (decl
),
1836 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1837 return return_false_with_msg ("size mismatch");
1839 /* Do not attempt to mix data from different user sections;
1840 we do not know what user intends with those. */
1841 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1842 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1843 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1844 return return_false_with_msg ("user section mismatch");
1846 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1847 return return_false_with_msg ("text section");
1849 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1850 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1852 item
->node
->iterate_reference (i
, ref2
);
1854 if (ref
->use
!= ref2
->use
)
1855 return return_false_with_msg ("reference use mismatch");
1857 if (!compare_symbol_references (ignored_nodes
,
1858 ref
->referred
, ref2
->referred
,
1859 ref
->address_matters_p ()))
1866 /* Returns true if the item equals to ITEM given as argument. */
1869 sem_variable::equals (sem_item
*item
,
1870 hash_map
<symtab_node
*, sem_item
*> &)
1872 gcc_assert (item
->type
== VAR
);
1875 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1876 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1877 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1878 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1880 /* As seen in PR ipa/65303 we have to compare variables types. */
1881 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1882 TREE_TYPE (item
->decl
)))
1883 return return_false_with_msg ("variables types are different");
1885 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1886 DECL_INITIAL (item
->node
->decl
));
1887 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1889 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1890 xstrdup_for_dump (node
->name()),
1891 xstrdup_for_dump (item
->node
->name ()),
1892 node
->order
, item
->node
->order
,
1893 xstrdup_for_dump (node
->asm_name ()),
1894 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1899 /* Compares trees T1 and T2 for semantic equality. */
1902 sem_variable::equals (tree t1
, tree t2
)
1905 return return_with_debug (t1
== t2
);
1908 tree_code tc1
= TREE_CODE (t1
);
1909 tree_code tc2
= TREE_CODE (t2
);
1912 return return_false_with_msg ("TREE_CODE mismatch");
1918 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1919 unsigned HOST_WIDE_INT idx
;
1921 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1922 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1923 return return_false_with_msg ("constructor type mismatch");
1925 if (typecode
== ARRAY_TYPE
)
1927 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1928 /* For arrays, check that the sizes all match. */
1929 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1931 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1932 return return_false_with_msg ("constructor array size mismatch");
1934 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1936 return return_false_with_msg ("constructor type incompatible");
1938 v1
= CONSTRUCTOR_ELTS (t1
);
1939 v2
= CONSTRUCTOR_ELTS (t2
);
1940 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1941 return return_false_with_msg ("constructor number of elts mismatch");
1943 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1945 constructor_elt
*c1
= &(*v1
)[idx
];
1946 constructor_elt
*c2
= &(*v2
)[idx
];
1948 /* Check that each value is the same... */
1949 if (!sem_variable::equals (c1
->value
, c2
->value
))
1951 /* ... and that they apply to the same fields! */
1952 if (!sem_variable::equals (c1
->index
, c2
->index
))
1959 tree x1
= TREE_OPERAND (t1
, 0);
1960 tree x2
= TREE_OPERAND (t2
, 0);
1961 tree y1
= TREE_OPERAND (t1
, 1);
1962 tree y2
= TREE_OPERAND (t2
, 1);
1964 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1965 return return_false ();
1967 /* Type of the offset on MEM_REF does not matter. */
1968 return return_with_debug (sem_variable::equals (x1
, x2
)
1969 && wi::to_offset (y1
)
1970 == wi::to_offset (y2
));
1975 tree op1
= TREE_OPERAND (t1
, 0);
1976 tree op2
= TREE_OPERAND (t2
, 0);
1977 return sem_variable::equals (op1
, op2
);
1979 /* References to other vars/decls are compared using ipa-ref. */
1982 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1984 return return_false_with_msg ("Declaration mismatch");
1986 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1987 need to process its VAR/FUNCTION references without relying on ipa-ref
1991 return return_false_with_msg ("Declaration mismatch");
1993 /* Integer constants are the same only if the same width of type. */
1994 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1995 return return_false_with_msg ("INTEGER_CST precision mismatch");
1996 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1997 return return_false_with_msg ("INTEGER_CST mode mismatch");
1998 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2000 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2001 return return_false_with_msg ("STRING_CST mode mismatch");
2002 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2003 return return_false_with_msg ("STRING_CST length mismatch");
2004 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2005 TREE_STRING_LENGTH (t1
)))
2006 return return_false_with_msg ("STRING_CST mismatch");
2009 /* Fixed constants are the same only if the same width of type. */
2010 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2011 return return_false_with_msg ("FIXED_CST precision mismatch");
2013 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2014 TREE_FIXED_CST (t2
)));
2016 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2017 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2019 /* Real constants are the same only if the same width of type. */
2020 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2021 return return_false_with_msg ("REAL_CST precision mismatch");
2022 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2023 &TREE_REAL_CST (t2
)));
2028 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2029 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2031 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2032 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2033 VECTOR_CST_ELT (t2
, i
)))
2039 case ARRAY_RANGE_REF
:
2041 tree x1
= TREE_OPERAND (t1
, 0);
2042 tree x2
= TREE_OPERAND (t2
, 0);
2043 tree y1
= TREE_OPERAND (t1
, 1);
2044 tree y2
= TREE_OPERAND (t2
, 1);
2046 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2048 if (!sem_variable::equals (array_ref_low_bound (t1
),
2049 array_ref_low_bound (t2
)))
2051 if (!sem_variable::equals (array_ref_element_size (t1
),
2052 array_ref_element_size (t2
)))
2058 case POINTER_PLUS_EXPR
:
2063 tree x1
= TREE_OPERAND (t1
, 0);
2064 tree x2
= TREE_OPERAND (t2
, 0);
2065 tree y1
= TREE_OPERAND (t1
, 1);
2066 tree y2
= TREE_OPERAND (t2
, 1);
2068 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2072 case VIEW_CONVERT_EXPR
:
2073 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2074 return return_false ();
2075 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2077 return return_false_with_msg ("ERROR_MARK");
2079 return return_false_with_msg ("Unknown TREE code reached");
2083 /* Parser function that visits a varpool NODE. */
2086 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2088 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2092 sem_variable
*v
= new sem_variable (node
, 0, stack
);
2099 /* References independent hash function. */
2102 sem_variable::get_hash (void)
2107 /* All WPA streamed in symbols should have their hashes computed at compile
2108 time. At this point, the constructor may not be in memory at all.
2109 DECL_INITIAL (decl) would be error_mark_node in that case. */
2110 gcc_assert (!node
->lto_file_data
);
2111 tree ctor
= DECL_INITIAL (decl
);
2112 inchash::hash hstate
;
2114 hstate
.add_int (456346417);
2115 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2116 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2117 add_expr (ctor
, hstate
);
2118 set_hash (hstate
.end ());
2123 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2127 sem_variable::merge (sem_item
*alias_item
)
2129 gcc_assert (alias_item
->type
== VAR
);
2131 if (!sem_item::target_supports_symbol_aliases_p ())
2134 fprintf (dump_file
, "Not unifying; "
2135 "Symbol aliases are not supported by target\n\n");
2139 if (DECL_EXTERNAL (alias_item
->decl
))
2142 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2146 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2148 varpool_node
*original
= get_node ();
2149 varpool_node
*alias
= alias_var
->get_node ();
2150 bool original_discardable
= false;
2152 bool original_address_matters
= original
->address_matters_p ();
2153 bool alias_address_matters
= alias
->address_matters_p ();
2155 /* See if original is in a section that can be discarded if the main
2157 Also consider case where we have resolution info and we know that
2158 original's definition is not going to be used. In this case we can not
2159 create alias to original. */
2160 if (original
->can_be_discarded_p ()
2161 || (node
->resolution
!= LDPR_UNKNOWN
2162 && !decl_binds_to_current_def_p (node
->decl
)))
2163 original_discardable
= true;
2165 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2167 /* Constant pool machinery is not quite ready for aliases.
2168 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2169 For LTO merging does not happen that is an important missing feature.
2170 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2171 flag is dropped and non-local symbol name is assigned. */
2172 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2173 || DECL_IN_CONSTANT_POOL (original
->decl
))
2177 "Not unifying; constant pool variables.\n\n");
2181 /* Do not attempt to mix functions from different user sections;
2182 we do not know what user intends with those. */
2183 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2184 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2185 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2190 "original and alias are in different sections.\n\n");
2194 /* We can not merge if address comparsion metters. */
2195 if (original_address_matters
&& alias_address_matters
2196 && flag_merge_constants
< 2)
2201 "adress of original and alias may be compared.\n\n");
2204 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2207 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2208 "across comdat group boundary\n\n");
2213 if (original_discardable
)
2216 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2217 "target is discardable\n\n");
2223 gcc_assert (!original
->alias
);
2224 gcc_assert (!alias
->alias
);
2226 alias
->analyzed
= false;
2228 DECL_INITIAL (alias
->decl
) = NULL
;
2229 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2231 alias
->need_bounds_init
= false;
2232 alias
->remove_all_references ();
2233 if (TREE_ADDRESSABLE (alias
->decl
))
2234 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2236 varpool_node::create_alias (alias_var
->decl
, decl
);
2237 alias
->resolve_alias (original
);
2240 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
2246 /* Dump symbol to FILE. */
2249 sem_variable::dump_to_file (FILE *file
)
2253 print_node (file
, "", decl
, 0);
2254 fprintf (file
, "\n\n");
2257 unsigned int sem_item_optimizer::class_id
= 0;
2259 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2260 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2263 bitmap_obstack_initialize (&m_bmstack
);
2266 sem_item_optimizer::~sem_item_optimizer ()
2268 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2271 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2272 it
!= m_classes
.end (); ++it
)
2274 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2275 delete (*it
)->classes
[i
];
2277 (*it
)->classes
.release ();
2283 bitmap_obstack_release (&m_bmstack
);
2286 /* Write IPA ICF summary for symbols. */
2289 sem_item_optimizer::write_summary (void)
2291 unsigned int count
= 0;
2293 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2294 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2297 /* Calculate number of symbols to be serialized. */
2298 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2300 lsei_next_in_partition (&lsei
))
2302 symtab_node
*node
= lsei_node (lsei
);
2304 if (m_symtab_node_map
.get (node
))
2308 streamer_write_uhwi (ob
, count
);
2310 /* Process all of the symbols. */
2311 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2313 lsei_next_in_partition (&lsei
))
2315 symtab_node
*node
= lsei_node (lsei
);
2317 sem_item
**item
= m_symtab_node_map
.get (node
);
2321 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2322 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2324 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2328 streamer_write_char_stream (ob
->main_stream
, 0);
2329 produce_asm (ob
, NULL
);
2330 destroy_output_block (ob
);
2333 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2334 contains LEN bytes. */
2337 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2338 const char *data
, size_t len
)
2340 const lto_function_header
*header
=
2341 (const lto_function_header
*) data
;
2342 const int cfg_offset
= sizeof (lto_function_header
);
2343 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2344 const int string_offset
= main_offset
+ header
->main_size
;
2349 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2350 header
->main_size
, file_data
->mode_table
);
2353 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2354 header
->string_size
, vNULL
);
2356 count
= streamer_read_uhwi (&ib_main
);
2358 for (i
= 0; i
< count
; i
++)
2362 lto_symtab_encoder_t encoder
;
2364 index
= streamer_read_uhwi (&ib_main
);
2365 encoder
= file_data
->symtab_node_encoder
;
2366 node
= lto_symtab_encoder_deref (encoder
, index
);
2368 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2370 gcc_assert (node
->definition
);
2373 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2374 node
->asm_name (), (void *) node
->decl
, node
->order
);
2376 if (is_a
<cgraph_node
*> (node
))
2378 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2380 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2384 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2386 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2390 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2392 lto_data_in_delete (data_in
);
2395 /* Read IPA ICF summary for symbols. */
2398 sem_item_optimizer::read_summary (void)
2400 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2401 lto_file_decl_data
*file_data
;
2404 while ((file_data
= file_data_vec
[j
++]))
2407 const char *data
= lto_get_section_data (file_data
,
2408 LTO_section_ipa_icf
, NULL
, &len
);
2411 read_section (file_data
, data
, len
);
2415 /* Register callgraph and varpool hooks. */
2418 sem_item_optimizer::register_hooks (void)
2420 if (!m_cgraph_node_hooks
)
2421 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2422 (&sem_item_optimizer::cgraph_removal_hook
, this);
2424 if (!m_varpool_node_hooks
)
2425 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2426 (&sem_item_optimizer::varpool_removal_hook
, this);
2429 /* Unregister callgraph and varpool hooks. */
2432 sem_item_optimizer::unregister_hooks (void)
2434 if (m_cgraph_node_hooks
)
2435 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2437 if (m_varpool_node_hooks
)
2438 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2441 /* Adds a CLS to hashtable associated by hash value. */
2444 sem_item_optimizer::add_class (congruence_class
*cls
)
2446 gcc_assert (cls
->members
.length ());
2448 congruence_class_group
*group
= get_group_by_hash (
2449 cls
->members
[0]->get_hash (),
2450 cls
->members
[0]->type
);
2451 group
->classes
.safe_push (cls
);
2454 /* Gets a congruence class group based on given HASH value and TYPE. */
2456 congruence_class_group
*
2457 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2459 congruence_class_group
*item
= XNEW (congruence_class_group
);
2463 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2469 item
->classes
.create (1);
2476 /* Callgraph removal hook called for a NODE with a custom DATA. */
2479 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2481 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2482 optimizer
->remove_symtab_node (node
);
2485 /* Varpool removal hook called for a NODE with a custom DATA. */
2488 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2490 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2491 optimizer
->remove_symtab_node (node
);
2494 /* Remove symtab NODE triggered by symtab removal hooks. */
2497 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2499 gcc_assert (!m_classes
.elements());
2501 m_removed_items_set
.add (node
);
2505 sem_item_optimizer::remove_item (sem_item
*item
)
2507 if (m_symtab_node_map
.get (item
->node
))
2508 m_symtab_node_map
.remove (item
->node
);
2512 /* Removes all callgraph and varpool nodes that are marked by symtab
2516 sem_item_optimizer::filter_removed_items (void)
2518 auto_vec
<sem_item
*> filtered
;
2520 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2522 sem_item
*item
= m_items
[i
];
2524 if (m_removed_items_set
.contains (item
->node
))
2530 if (item
->type
== FUNC
)
2532 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2534 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2537 filtered
.safe_push (item
);
2541 if (!flag_ipa_icf_variables
)
2545 /* Filter out non-readonly variables. */
2546 tree decl
= item
->decl
;
2547 if (TREE_READONLY (decl
))
2548 filtered
.safe_push (item
);
2555 /* Clean-up of released semantic items. */
2558 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2559 m_items
.safe_push (filtered
[i
]);
2562 /* Optimizer entry point which returns true in case it processes
2563 a merge operation. True is returned if there's a merge operation
2567 sem_item_optimizer::execute (void)
2569 filter_removed_items ();
2570 unregister_hooks ();
2573 update_hash_by_addr_refs ();
2574 build_hash_based_classes ();
2577 fprintf (dump_file
, "Dump after hash based groups\n");
2578 dump_cong_classes ();
2580 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2581 m_items
[i
]->init_wpa ();
2583 subdivide_classes_by_equality (true);
2586 fprintf (dump_file
, "Dump after WPA based types groups\n");
2588 dump_cong_classes ();
2590 process_cong_reduction ();
2591 checking_verify_classes ();
2594 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2596 dump_cong_classes ();
2598 parse_nonsingleton_classes ();
2599 subdivide_classes_by_equality ();
2602 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2604 dump_cong_classes ();
2606 unsigned int prev_class_count
= m_classes_count
;
2608 process_cong_reduction ();
2609 dump_cong_classes ();
2610 checking_verify_classes ();
2611 bool merged_p
= merge_classes (prev_class_count
);
2613 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2614 symtab_node::dump_table (dump_file
);
2619 /* Function responsible for visiting all potential functions and
2620 read-only variables that can be merged. */
2623 sem_item_optimizer::parse_funcs_and_vars (void)
2627 if (flag_ipa_icf_functions
)
2628 FOR_EACH_DEFINED_FUNCTION (cnode
)
2630 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2633 m_items
.safe_push (f
);
2634 m_symtab_node_map
.put (cnode
, f
);
2637 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2639 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2640 f
->dump_to_file (dump_file
);
2643 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2646 varpool_node
*vnode
;
2648 if (flag_ipa_icf_variables
)
2649 FOR_EACH_DEFINED_VARIABLE (vnode
)
2651 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2655 m_items
.safe_push (v
);
2656 m_symtab_node_map
.put (vnode
, v
);
2661 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2664 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2666 item
->index_in_class
= cls
->members
.length ();
2667 cls
->members
.safe_push (item
);
2671 /* For each semantic item, append hash values of references. */
2674 sem_item_optimizer::update_hash_by_addr_refs ()
2676 /* First, append to hash sensitive references and class type if it need to
2677 be matched for ODR. */
2678 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2680 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2681 if (m_items
[i
]->type
== FUNC
)
2683 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2684 && contains_polymorphic_type_p
2685 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2686 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2687 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2688 && static_cast<sem_function
*> (m_items
[i
])
2689 ->compare_polymorphic_p ())))
2692 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2693 inchash::hash
hstate (m_items
[i
]->get_hash ());
2695 if (TYPE_NAME (class_type
)
2696 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2698 (IDENTIFIER_HASH_VALUE
2699 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2701 m_items
[i
]->set_hash (hstate
.end ());
2706 /* Once all symbols have enhanced hash value, we can append
2707 hash values of symbols that are seen by IPA ICF and are
2708 references by a semantic item. Newly computed values
2709 are saved to global_hash member variable. */
2710 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2711 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2713 /* Global hash value replace current hash values. */
2714 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2715 m_items
[i
]->set_hash (m_items
[i
]->global_hash
);
2718 /* Congruence classes are built by hash value. */
2721 sem_item_optimizer::build_hash_based_classes (void)
2723 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2725 sem_item
*item
= m_items
[i
];
2727 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2730 if (!group
->classes
.length ())
2733 group
->classes
.safe_push (new congruence_class (class_id
++));
2736 add_item_to_class (group
->classes
[0], item
);
2740 /* Build references according to call graph. */
2743 sem_item_optimizer::build_graph (void)
2745 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2747 sem_item
*item
= m_items
[i
];
2748 m_symtab_node_map
.put (item
->node
, item
);
2750 /* Initialize hash values if we are not in LTO mode. */
2755 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2757 sem_item
*item
= m_items
[i
];
2759 if (item
->type
== FUNC
)
2761 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2763 cgraph_edge
*e
= cnode
->callees
;
2766 sem_item
**slot
= m_symtab_node_map
.get
2767 (e
->callee
->ultimate_alias_target ());
2769 item
->add_reference (*slot
);
2775 ipa_ref
*ref
= NULL
;
2776 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2778 sem_item
**slot
= m_symtab_node_map
.get
2779 (ref
->referred
->ultimate_alias_target ());
2781 item
->add_reference (*slot
);
2786 /* Semantic items in classes having more than one element and initialized.
2787 In case of WPA, we load function body. */
2790 sem_item_optimizer::parse_nonsingleton_classes (void)
2792 unsigned int init_called_count
= 0;
2794 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2795 if (m_items
[i
]->cls
->members
.length () > 1)
2797 m_items
[i
]->init ();
2798 init_called_count
++;
2802 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2803 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2806 /* Equality function for semantic items is used to subdivide existing
2807 classes. If IN_WPA, fast equality function is invoked. */
2810 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2812 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2813 it
!= m_classes
.end (); ++it
)
2815 unsigned int class_count
= (*it
)->classes
.length ();
2817 for (unsigned i
= 0; i
< class_count
; i
++)
2819 congruence_class
*c
= (*it
)->classes
[i
];
2821 if (c
->members
.length() > 1)
2823 auto_vec
<sem_item
*> new_vector
;
2825 sem_item
*first
= c
->members
[0];
2826 new_vector
.safe_push (first
);
2828 unsigned class_split_first
= (*it
)->classes
.length ();
2830 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2832 sem_item
*item
= c
->members
[j
];
2834 bool equals
= in_wpa
? first
->equals_wpa (item
,
2835 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2838 new_vector
.safe_push (item
);
2841 bool integrated
= false;
2843 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2845 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2846 bool equals
= in_wpa
? x
->equals_wpa (item
,
2847 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2852 add_item_to_class ((*it
)->classes
[k
], item
);
2860 congruence_class
*c
= new congruence_class (class_id
++);
2862 add_item_to_class (c
, item
);
2864 (*it
)->classes
.safe_push (c
);
2869 // we replace newly created new_vector for the class we've just splitted
2870 c
->members
.release ();
2871 c
->members
.create (new_vector
.length ());
2873 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2874 add_item_to_class (c
, new_vector
[j
]);
2879 checking_verify_classes ();
2882 /* Subdivide classes by address references that members of the class
2883 reference. Example can be a pair of functions that have an address
2884 taken from a function. If these addresses are different the class
2888 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2890 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2892 unsigned newly_created_classes
= 0;
2894 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2895 it
!= m_classes
.end (); ++it
)
2897 unsigned int class_count
= (*it
)->classes
.length ();
2898 auto_vec
<congruence_class
*> new_classes
;
2900 for (unsigned i
= 0; i
< class_count
; i
++)
2902 congruence_class
*c
= (*it
)->classes
[i
];
2904 if (c
->members
.length() > 1)
2906 subdivide_hash_map split_map
;
2908 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2910 sem_item
*source_node
= c
->members
[j
];
2912 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2915 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2917 gcc_checking_assert (slot
);
2919 slot
->safe_push (source_node
);
2925 /* If the map contains more than one key, we have to split the map
2927 if (split_map
.elements () != 1)
2929 bool first_class
= true;
2931 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2932 it2
!= split_map
.end (); ++it2
)
2934 congruence_class
*new_cls
;
2935 new_cls
= new congruence_class (class_id
++);
2937 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2938 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2940 worklist_push (new_cls
);
2941 newly_created_classes
++;
2945 (*it
)->classes
[i
] = new_cls
;
2946 first_class
= false;
2950 new_classes
.safe_push (new_cls
);
2956 /* Release memory. */
2957 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2958 it2
!= split_map
.end (); ++it2
)
2960 delete (*it2
).first
;
2961 (*it2
).second
.release ();
2966 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2967 (*it
)->classes
.safe_push (new_classes
[i
]);
2970 return newly_created_classes
;
2973 /* Verify congruence classes, if checking is enabled. */
2976 sem_item_optimizer::checking_verify_classes (void)
2982 /* Verify congruence classes. */
2985 sem_item_optimizer::verify_classes (void)
2987 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2988 it
!= m_classes
.end (); ++it
)
2990 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2992 congruence_class
*cls
= (*it
)->classes
[i
];
2995 gcc_assert (cls
->members
.length () > 0);
2997 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2999 sem_item
*item
= cls
->members
[j
];
3002 gcc_assert (item
->cls
== cls
);
3004 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3006 sem_usage_pair
*usage
= item
->usages
[k
];
3007 gcc_assert (usage
->item
->index_in_class
<
3008 usage
->item
->cls
->members
.length ());
3015 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3016 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3017 but unused argument. */
3020 sem_item_optimizer::release_split_map (congruence_class
* const &,
3021 bitmap
const &b
, traverse_split_pair
*)
3030 /* Process split operation for a class given as pointer CLS_PTR,
3031 where bitmap B splits congruence class members. DATA is used
3032 as argument of split pair. */
3035 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3036 bitmap
const &b
, traverse_split_pair
*pair
)
3038 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3039 const congruence_class
*splitter_cls
= pair
->cls
;
3041 /* If counted bits are greater than zero and less than the number of members
3042 a group will be splitted. */
3043 unsigned popcount
= bitmap_count_bits (b
);
3045 if (popcount
> 0 && popcount
< cls
->members
.length ())
3047 auto_vec
<congruence_class
*, 2> newclasses
;
3048 newclasses
.quick_push (new congruence_class (class_id
++));
3049 newclasses
.quick_push (new congruence_class (class_id
++));
3051 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3053 int target
= bitmap_bit_p (b
, i
);
3054 congruence_class
*tc
= newclasses
[target
];
3056 add_item_to_class (tc
, cls
->members
[i
]);
3061 for (unsigned int i
= 0; i
< 2; i
++)
3062 gcc_assert (newclasses
[i
]->members
.length ());
3065 if (splitter_cls
== cls
)
3066 optimizer
->splitter_class_removed
= true;
3068 /* Remove old class from worklist if presented. */
3069 bool in_worklist
= cls
->in_worklist
;
3072 cls
->in_worklist
= false;
3074 congruence_class_group g
;
3075 g
.hash
= cls
->members
[0]->get_hash ();
3076 g
.type
= cls
->members
[0]->type
;
3078 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3080 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3081 if (slot
->classes
[i
] == cls
)
3083 slot
->classes
.ordered_remove (i
);
3087 /* New class will be inserted and integrated to work list. */
3088 for (unsigned int i
= 0; i
< 2; i
++)
3089 optimizer
->add_class (newclasses
[i
]);
3091 /* Two classes replace one, so that increment just by one. */
3092 optimizer
->m_classes_count
++;
3094 /* If OLD class was presented in the worklist, we remove the class
3095 and replace it will both newly created classes. */
3097 for (unsigned int i
= 0; i
< 2; i
++)
3098 optimizer
->worklist_push (newclasses
[i
]);
3099 else /* Just smaller class is inserted. */
3101 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3102 newclasses
[1]->members
.length () ?
3104 optimizer
->worklist_push (newclasses
[smaller_index
]);
3107 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3109 fprintf (dump_file
, " congruence class splitted:\n");
3110 cls
->dump (dump_file
, 4);
3112 fprintf (dump_file
, " newly created groups:\n");
3113 for (unsigned int i
= 0; i
< 2; i
++)
3114 newclasses
[i
]->dump (dump_file
, 4);
3117 /* Release class if not presented in work list. */
3126 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3127 Bitmap stack BMSTACK is used for bitmap allocation. */
3130 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3133 hash_map
<congruence_class
*, bitmap
> split_map
;
3135 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3137 sem_item
*item
= cls
->members
[i
];
3139 /* Iterate all usages that have INDEX as usage of the item. */
3140 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3142 sem_usage_pair
*usage
= item
->usages
[j
];
3144 if (usage
->index
!= index
)
3147 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3152 b
= BITMAP_ALLOC (&m_bmstack
);
3153 split_map
.put (usage
->item
->cls
, b
);
3158 gcc_checking_assert (usage
->item
->cls
);
3159 gcc_checking_assert (usage
->item
->index_in_class
<
3160 usage
->item
->cls
->members
.length ());
3162 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3166 traverse_split_pair pair
;
3167 pair
.optimizer
= this;
3170 splitter_class_removed
= false;
3172 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3174 /* Bitmap clean-up. */
3176 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3179 /* Every usage of a congruence class CLS is a candidate that can split the
3180 collection of classes. Bitmap stack BMSTACK is used for bitmap
3184 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3189 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3191 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3192 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3194 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3196 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3197 fprintf (dump_file
, " processing congruence step for class: %u, index: %u\n",
3200 do_congruence_step_for_index (cls
, i
);
3202 if (splitter_class_removed
)
3206 BITMAP_FREE (usage
);
3209 /* Adds a newly created congruence class CLS to worklist. */
3212 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3214 /* Return if the class CLS is already presented in work list. */
3215 if (cls
->in_worklist
)
3218 cls
->in_worklist
= true;
3219 worklist
.push_back (cls
);
3222 /* Pops a class from worklist. */
3225 sem_item_optimizer::worklist_pop (void)
3227 congruence_class
*cls
;
3229 while (!worklist
.empty ())
3231 cls
= worklist
.front ();
3232 worklist
.pop_front ();
3233 if (cls
->in_worklist
)
3235 cls
->in_worklist
= false;
3241 /* Work list item was already intended to be removed.
3242 The only reason for doing it is to split a class.
3243 Thus, the class CLS is deleted. */
3251 /* Iterative congruence reduction function. */
3254 sem_item_optimizer::process_cong_reduction (void)
3256 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3257 it
!= m_classes
.end (); ++it
)
3258 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3259 if ((*it
)->classes
[i
]->is_class_used ())
3260 worklist_push ((*it
)->classes
[i
]);
3263 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3264 (unsigned long) worklist
.size ());
3266 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3267 fprintf (dump_file
, "Congruence class reduction\n");
3269 congruence_class
*cls
;
3271 /* Process complete congruence reduction. */
3272 while ((cls
= worklist_pop ()) != NULL
)
3273 do_congruence_step (cls
);
3275 /* Subdivide newly created classes according to references. */
3276 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3279 fprintf (dump_file
, "Address reference subdivision created: %u "
3280 "new classes.\n", new_classes
);
3283 /* Debug function prints all informations about congruence classes. */
3286 sem_item_optimizer::dump_cong_classes (void)
3292 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3293 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3295 /* Histogram calculation. */
3296 unsigned int max_index
= 0;
3297 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3299 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3300 it
!= m_classes
.end (); ++it
)
3302 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3304 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3312 "Class size histogram [num of members]: number of classe number of classess\n");
3314 for (unsigned int i
= 0; i
<= max_index
; i
++)
3316 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3318 fprintf (dump_file
, "\n\n");
3321 if (dump_flags
& TDF_DETAILS
)
3322 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3323 it
!= m_classes
.end (); ++it
)
3325 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3327 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3329 (*it
)->classes
[i
]->dump (dump_file
, 4);
3331 if(i
< (*it
)->classes
.length () - 1)
3332 fprintf (dump_file
, " ");
3339 /* After reduction is done, we can declare all items in a group
3340 to be equal. PREV_CLASS_COUNT is start number of classes
3341 before reduction. True is returned if there's a merge operation
3345 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3347 unsigned int item_count
= m_items
.length ();
3348 unsigned int class_count
= m_classes_count
;
3349 unsigned int equal_items
= item_count
- class_count
;
3351 unsigned int non_singular_classes_count
= 0;
3352 unsigned int non_singular_classes_sum
= 0;
3354 bool merged_p
= false;
3356 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3357 it
!= m_classes
.end (); ++it
)
3358 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3360 congruence_class
*c
= (*it
)->classes
[i
];
3361 if (c
->members
.length () > 1)
3363 non_singular_classes_count
++;
3364 non_singular_classes_sum
+= c
->members
.length ();
3370 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3371 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3372 prev_class_count
, class_count
);
3373 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3374 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3375 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3376 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3377 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3378 non_singular_classes_count
: 0.0f
,
3379 non_singular_classes_count
);
3380 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3381 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3382 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3385 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3386 it
!= m_classes
.end (); ++it
)
3387 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3389 congruence_class
*c
= (*it
)->classes
[i
];
3391 if (c
->members
.length () == 1)
3394 gcc_assert (c
->members
.length ());
3396 sem_item
*source
= c
->members
[0];
3398 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
3400 sem_item
*alias
= c
->members
[j
];
3404 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3405 xstrdup_for_dump (source
->node
->name ()),
3406 xstrdup_for_dump (alias
->node
->name ()));
3407 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3408 xstrdup_for_dump (source
->node
->asm_name ()),
3409 xstrdup_for_dump (alias
->node
->asm_name ()));
3412 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3416 "Merge operation is skipped due to no_icf "
3422 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3424 source
->dump_to_file (dump_file
);
3425 alias
->dump_to_file (dump_file
);
3428 if (dbg_cnt (merged_ipa_icf
))
3429 merged_p
|= source
->merge (alias
);
3436 /* Dump function prints all class members to a FILE with an INDENT. */
3439 congruence_class::dump (FILE *file
, unsigned int indent
) const
3441 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3442 id
, members
[0]->get_hash (), members
.length ());
3444 FPUTS_SPACES (file
, indent
+ 2, "");
3445 for (unsigned i
= 0; i
< members
.length (); i
++)
3446 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3447 (void *) members
[i
]->decl
,
3448 members
[i
]->node
->order
);
3450 fprintf (file
, "\n");
3453 /* Returns true if there's a member that is used from another group. */
3456 congruence_class::is_class_used (void)
3458 for (unsigned int i
= 0; i
< members
.length (); i
++)
3459 if (members
[i
]->usages
.length ())
3465 /* Generate pass summary for IPA ICF pass. */
3468 ipa_icf_generate_summary (void)
3471 optimizer
= new sem_item_optimizer ();
3473 optimizer
->register_hooks ();
3474 optimizer
->parse_funcs_and_vars ();
3477 /* Write pass summary for IPA ICF pass. */
3480 ipa_icf_write_summary (void)
3482 gcc_assert (optimizer
);
3484 optimizer
->write_summary ();
3487 /* Read pass summary for IPA ICF pass. */
3490 ipa_icf_read_summary (void)
3493 optimizer
= new sem_item_optimizer ();
3495 optimizer
->read_summary ();
3496 optimizer
->register_hooks ();
3499 /* Semantic equality exection function. */
3502 ipa_icf_driver (void)
3504 gcc_assert (optimizer
);
3506 bool merged_p
= optimizer
->execute ();
3511 return merged_p
? TODO_remove_functions
: 0;
3514 const pass_data pass_data_ipa_icf
=
3516 IPA_PASS
, /* type */
3518 OPTGROUP_IPA
, /* optinfo_flags */
3519 TV_IPA_ICF
, /* tv_id */
3520 0, /* properties_required */
3521 0, /* properties_provided */
3522 0, /* properties_destroyed */
3523 0, /* todo_flags_start */
3524 0, /* todo_flags_finish */
3527 class pass_ipa_icf
: public ipa_opt_pass_d
3530 pass_ipa_icf (gcc::context
*ctxt
)
3531 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3532 ipa_icf_generate_summary
, /* generate_summary */
3533 ipa_icf_write_summary
, /* write_summary */
3534 ipa_icf_read_summary
, /* read_summary */
3536 write_optimization_summary */
3538 read_optimization_summary */
3539 NULL
, /* stmt_fixup */
3540 0, /* function_transform_todo_flags_start */
3541 NULL
, /* function_transform */
3542 NULL
) /* variable_transform */
3545 /* opt_pass methods: */
3546 virtual bool gate (function
*)
3548 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3551 virtual unsigned int execute (function
*)
3553 return ipa_icf_driver();
3555 }; // class pass_ipa_icf
3557 } // ipa_icf namespace
3560 make_pass_ipa_icf (gcc::context
*ctxt
)
3562 return new ipa_icf::pass_ipa_icf (ctxt
);