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.
57 #include "coretypes.h"
62 #include "fold-const.h"
65 #include "hard-reg-set.h"
67 #include "dominance.h"
69 #include "basic-block.h"
70 #include "tree-ssa-alias.h"
71 #include "internal-fn.h"
72 #include "gimple-expr.h"
76 #include "insn-config.h"
85 #include "gimple-iterator.h"
86 #include "gimple-ssa.h"
88 #include "tree-phinodes.h"
89 #include "stringpool.h"
90 #include "tree-ssanames.h"
92 #include "tree-pass.h"
93 #include "gimple-pretty-print.h"
95 #include "alloc-pool.h"
96 #include "symbol-summary.h"
98 #include "ipa-inline.h"
101 #include "coverage.h"
103 #include "print-tree.h"
104 #include "lto-streamer.h"
105 #include "data-streamer.h"
106 #include "ipa-utils.h"
107 #include "ipa-icf-gimple.h"
109 #include "stor-layout.h"
112 using namespace ipa_icf_gimple
;
116 /* Initialization and computation of symtab node hash, there data
117 are propagated later on. */
119 static sem_item_optimizer
*optimizer
= NULL
;
123 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
125 m_references
.create (0);
126 m_interposables
.create (0);
130 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
133 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
135 if (ref
->address_matters_p ())
136 m_references
.safe_push (ref
->referred
);
138 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
140 if (ref
->address_matters_p ())
141 m_references
.safe_push (ref
->referred
);
143 m_interposables
.safe_push (ref
->referred
);
147 if (is_a
<cgraph_node
*> (node
))
149 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
151 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
152 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
153 m_interposables
.safe_push (e
->callee
);
157 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
159 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
160 item (_item
), index (_index
)
164 /* Semantic item constructor for a node of _TYPE, where STACK is used
165 for bitmap memory allocation. */
167 sem_item::sem_item (sem_item_type _type
,
168 bitmap_obstack
*stack
): type(_type
), hash(0)
173 /* Semantic item constructor for a node of _TYPE, where STACK is used
174 for bitmap memory allocation. The item is based on symtab node _NODE
175 with computed _HASH. */
177 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
178 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
179 node (_node
), hash (_hash
)
185 /* Add reference to a semantic TARGET. */
188 sem_item::add_reference (sem_item
*target
)
190 refs
.safe_push (target
);
191 unsigned index
= refs
.length ();
192 target
->usages
.safe_push (new sem_usage_pair(this, index
));
193 bitmap_set_bit (target
->usage_index_bitmap
, index
);
194 refs_set
.add (target
->node
);
197 /* Initialize internal data structures. Bitmap STACK is used for
198 bitmap memory allocation process. */
201 sem_item::setup (bitmap_obstack
*stack
)
203 gcc_checking_assert (node
);
206 tree_refs
.create (0);
208 usage_index_bitmap
= BITMAP_ALLOC (stack
);
211 sem_item::~sem_item ()
213 for (unsigned i
= 0; i
< usages
.length (); i
++)
217 tree_refs
.release ();
220 BITMAP_FREE (usage_index_bitmap
);
223 /* Dump function for debugging purpose. */
226 sem_item::dump (void)
230 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
231 node
->name(), node
->order
, (void *) node
->decl
);
232 fprintf (dump_file
, " hash: %u\n", get_hash ());
233 fprintf (dump_file
, " references: ");
235 for (unsigned i
= 0; i
< refs
.length (); i
++)
236 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
237 i
< refs
.length() - 1 ? "," : "");
239 fprintf (dump_file
, "\n");
243 /* Return true if target supports alias symbols. */
246 sem_item::target_supports_symbol_aliases_p (void)
248 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
255 /* Semantic function constructor that uses STACK as bitmap memory stack. */
257 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
258 m_checker (NULL
), m_compared_func (NULL
)
261 bb_sorted
.create (0);
264 /* Constructor based on callgraph node _NODE with computed hash _HASH.
265 Bitmap STACK is used for memory allocation. */
266 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
267 bitmap_obstack
*stack
):
268 sem_item (FUNC
, node
, hash
, stack
),
269 m_checker (NULL
), m_compared_func (NULL
)
272 bb_sorted
.create (0);
275 sem_function::~sem_function ()
277 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
278 delete (bb_sorted
[i
]);
281 bb_sorted
.release ();
284 /* Calculates hash value based on a BASIC_BLOCK. */
287 sem_function::get_bb_hash (const sem_bb
*basic_block
)
289 inchash::hash hstate
;
291 hstate
.add_int (basic_block
->nondbg_stmt_count
);
292 hstate
.add_int (basic_block
->edge_count
);
294 return hstate
.end ();
297 /* References independent hash function. */
300 sem_function::get_hash (void)
304 inchash::hash hstate
;
305 hstate
.add_int (177454); /* Random number for function type. */
307 hstate
.add_int (arg_count
);
308 hstate
.add_int (cfg_checksum
);
309 hstate
.add_int (gcode_hash
);
311 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
312 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
314 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
315 hstate
.add_int (bb_sizes
[i
]);
318 /* Add common features of declaration itself. */
319 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
321 (cl_target_option_hash
322 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
323 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
324 (cl_optimization_hash
325 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
326 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
327 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
329 hash
= hstate
.end ();
335 /* Return ture if A1 and A2 represent equivalent function attribute lists.
336 Based on comp_type_attributes. */
339 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
344 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
346 const struct attribute_spec
*as
;
349 as
= lookup_attribute_spec (get_attribute_name (a
));
350 /* TODO: We can introduce as->affects_decl_identity
351 and as->affects_decl_reference_identity if attribute mismatch
352 gets a common reason to give up on merging. It may not be worth
354 For example returns_nonnull affects only references, while
355 optimize attribute can be ignored because it is already lowered
356 into flags representation and compared separately. */
360 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
361 if (!attr
|| !attribute_value_equal (a
, attr
))
366 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
368 const struct attribute_spec
*as
;
370 as
= lookup_attribute_spec (get_attribute_name (a
));
374 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
376 /* We don't need to compare trees again, as we did this
377 already in first loop. */
382 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
386 /* Compare properties of symbols N1 and N2 that does not affect semantics of
387 symbol itself but affects semantics of its references from USED_BY (which
388 may be NULL if it is unknown). If comparsion is false, symbols
389 can still be merged but any symbols referring them can't.
391 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
393 TODO: We can also split attributes to those that determine codegen of
394 a function body/variable constructor itself and those that are used when
398 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
403 if (is_a
<cgraph_node
*> (n1
))
405 /* Inline properties matters: we do now want to merge uses of inline
406 function to uses of normal function because inline hint would be lost.
407 We however can merge inline function to noinline because the alias
408 will keep its DECL_DECLARED_INLINE flag.
410 Also ignore inline flag when optimizing for size or when function
411 is known to not be inlinable.
413 TODO: the optimize_size checks can also be assumed to be true if
414 unit has no !optimize_size functions. */
416 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
417 || !opt_for_fn (used_by
->decl
, optimize_size
))
418 && !opt_for_fn (n1
->decl
, optimize_size
)
419 && n1
->get_availability () > AVAIL_INTERPOSABLE
420 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
422 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
423 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
424 return return_false_with_msg
425 ("DECL_DISREGARD_INLINE_LIMITS are different");
427 if (DECL_DECLARED_INLINE_P (n1
->decl
)
428 != DECL_DECLARED_INLINE_P (n2
->decl
))
429 return return_false_with_msg ("inline attributes are different");
432 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
433 != DECL_IS_OPERATOR_NEW (n2
->decl
))
434 return return_false_with_msg ("operator new flags are different");
437 /* Merging two definitions with a reference to equivalent vtables, but
438 belonging to a different type may result in ipa-polymorphic-call analysis
439 giving a wrong answer about the dynamic type of instance. */
440 if (is_a
<varpool_node
*> (n1
))
442 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
443 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
444 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
445 DECL_CONTEXT (n2
->decl
)))
446 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
447 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
448 return return_false_with_msg
449 ("references to virtual tables can not be merged");
451 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
452 return return_false_with_msg ("alignment mismatch");
454 /* For functions we compare attributes in equals_wpa, because we do
455 not know what attributes may cause codegen differences, but for
456 variables just compare attributes for references - the codegen
457 for constructors is affected only by those attributes that we lower
458 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
459 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
460 DECL_ATTRIBUTES (n2
->decl
)))
461 return return_false_with_msg ("different var decl attributes");
462 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
463 TREE_TYPE (n2
->decl
)) != 1)
464 return return_false_with_msg ("different var type attributes");
467 /* When matching virtual tables, be sure to also match information
468 relevant for polymorphic call analysis. */
469 if (used_by
&& is_a
<varpool_node
*> (used_by
)
470 && DECL_VIRTUAL_P (used_by
->decl
))
472 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
473 return return_false_with_msg ("virtual flag mismatch");
474 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
475 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
476 return return_false_with_msg ("final flag mismatch");
481 /* Hash properties that are compared by compare_referenced_symbol_properties. */
484 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
485 inchash::hash
&hstate
,
488 if (is_a
<cgraph_node
*> (ref
))
490 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
491 && !opt_for_fn (ref
->decl
, optimize_size
)
492 && !DECL_UNINLINABLE (ref
->decl
))
494 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
495 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
497 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
499 else if (is_a
<varpool_node
*> (ref
))
501 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
503 hstate
.add_int (DECL_ALIGN (ref
->decl
));
508 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
509 point to a same function. Comparison can be skipped if IGNORED_NODES
510 contains these nodes. ADDRESS indicate if address is taken. */
513 sem_item::compare_symbol_references (
514 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
515 symtab_node
*n1
, symtab_node
*n2
, bool address
)
517 enum availability avail1
, avail2
;
522 /* Never match variable and function. */
523 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
526 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
528 if (address
&& n1
->equal_address_to (n2
) == 1)
530 if (!address
&& n1
->semantically_equivalent_p (n2
))
533 n1
= n1
->ultimate_alias_target (&avail1
);
534 n2
= n2
->ultimate_alias_target (&avail2
);
536 if (avail1
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
537 && avail2
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
540 return return_false_with_msg ("different references");
543 /* If cgraph edges E1 and E2 are indirect calls, verify that
544 ECF flags are the same. */
546 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
548 if (e1
->indirect_info
&& e2
->indirect_info
)
550 int e1_flags
= e1
->indirect_info
->ecf_flags
;
551 int e2_flags
= e2
->indirect_info
->ecf_flags
;
553 if (e1_flags
!= e2_flags
)
554 return return_false_with_msg ("ICF flags are different");
556 else if (e1
->indirect_info
|| e2
->indirect_info
)
562 /* Return true if parameter I may be used. */
565 sem_function::param_used_p (unsigned int i
)
567 if (ipa_node_params_sum
== NULL
)
570 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
572 if (parms_info
->descriptors
.is_empty ()
573 || parms_info
->descriptors
.length () <= i
)
576 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
579 /* Perform additional check needed to match types function parameters that are
580 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
581 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
584 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
586 /* Be sure that parameters are TBAA compatible. */
587 if (!func_checker::compatible_types_p (parm1
, parm2
))
588 return return_false_with_msg ("parameter type is not compatible");
590 if (POINTER_TYPE_P (parm1
)
591 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
592 return return_false_with_msg ("argument restrict flag mismatch");
594 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
595 if (POINTER_TYPE_P (parm1
)
596 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
597 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
598 return return_false_with_msg ("pointer wrt reference mismatch");
603 /* Fast equality function based on knowledge known in WPA. */
606 sem_function::equals_wpa (sem_item
*item
,
607 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
609 gcc_assert (item
->type
== FUNC
);
610 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
611 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
613 m_compared_func
= static_cast<sem_function
*> (item
);
615 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
616 return return_false_with_msg ("thunk_p mismatch");
618 if (cnode
->thunk
.thunk_p
)
620 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
621 return return_false_with_msg ("thunk fixed_offset mismatch");
622 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
623 return return_false_with_msg ("thunk virtual_value mismatch");
624 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
625 return return_false_with_msg ("thunk this_adjusting mismatch");
626 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
627 return return_false_with_msg ("thunk virtual_offset_p mismatch");
628 if (cnode
->thunk
.add_pointer_bounds_args
629 != cnode2
->thunk
.add_pointer_bounds_args
)
630 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
633 /* Compare special function DECL attributes. */
634 if (DECL_FUNCTION_PERSONALITY (decl
)
635 != DECL_FUNCTION_PERSONALITY (item
->decl
))
636 return return_false_with_msg ("function personalities are different");
638 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
639 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
640 return return_false_with_msg ("intrument function entry exit "
641 "attributes are different");
643 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
644 return return_false_with_msg ("no stack limit attributes are different");
646 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
647 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
649 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
650 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
652 /* TODO: pure/const flags mostly matters only for references, except for
653 the fact that codegen takes LOOPING flag as a hint that loops are
654 finite. We may arrange the code to always pick leader that has least
655 specified flags and then this can go into comparing symbol properties. */
656 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
657 return return_false_with_msg ("decl_or_type flags are different");
659 /* Do not match polymorphic constructors of different types. They calls
660 type memory location for ipa-polymorphic-call and we do not want
661 it to get confused by wrong type. */
662 if (DECL_CXX_CONSTRUCTOR_P (decl
)
663 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
665 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
666 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
667 else if (!func_checker::compatible_polymorphic_types_p
668 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
669 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
670 return return_false_with_msg ("ctor polymorphic type mismatch");
673 /* Checking function TARGET and OPTIMIZATION flags. */
674 cl_target_option
*tar1
= target_opts_for_fn (decl
);
675 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
677 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
679 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
681 fprintf (dump_file
, "target flags difference");
682 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
685 return return_false_with_msg ("Target flags are different");
688 cl_optimization
*opt1
= opts_for_fn (decl
);
689 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
691 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
693 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
695 fprintf (dump_file
, "optimization flags difference");
696 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
699 return return_false_with_msg ("optimization flags are different");
702 /* Result type checking. */
703 if (!func_checker::compatible_types_p
704 (TREE_TYPE (TREE_TYPE (decl
)),
705 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
706 return return_false_with_msg ("result types are different");
708 /* Checking types of arguments. */
709 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
710 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
711 for (unsigned i
= 0; list1
&& list2
;
712 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
714 tree parm1
= TREE_VALUE (list1
);
715 tree parm2
= TREE_VALUE (list2
);
717 /* This guard is here for function pointer with attributes (pr59927.c). */
718 if (!parm1
|| !parm2
)
719 return return_false_with_msg ("NULL argument type");
721 /* Verify that types are compatible to ensure that both functions
722 have same calling conventions. */
723 if (!types_compatible_p (parm1
, parm2
))
724 return return_false_with_msg ("parameter types are not compatible");
726 if (!param_used_p (i
))
729 /* Perform additional checks for used parameters. */
730 if (!compatible_parm_types_p (parm1
, parm2
))
735 return return_false_with_msg ("Mismatched number of parameters");
737 if (node
->num_references () != item
->node
->num_references ())
738 return return_false_with_msg ("different number of references");
740 /* Checking function attributes.
741 This is quadratic in number of attributes */
742 if (comp_type_attributes (TREE_TYPE (decl
),
743 TREE_TYPE (item
->decl
)) != 1)
744 return return_false_with_msg ("different type attributes");
745 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
746 DECL_ATTRIBUTES (item
->decl
)))
747 return return_false_with_msg ("different decl attributes");
749 /* The type of THIS pointer type memory location for
750 ipa-polymorphic-call-analysis. */
751 if (opt_for_fn (decl
, flag_devirtualize
)
752 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
753 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
755 && compare_polymorphic_p ())
757 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
758 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
759 if (!func_checker::compatible_polymorphic_types_p
760 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
761 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
762 return return_false_with_msg ("THIS pointer ODR type mismatch");
765 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
766 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
768 item
->node
->iterate_reference (i
, ref2
);
770 if (ref
->use
!= ref2
->use
)
771 return return_false_with_msg ("reference use mismatch");
773 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
775 ref
->address_matters_p ()))
779 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
780 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
784 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
787 if (!compare_edge_flags (e1
, e2
))
790 e1
= e1
->next_callee
;
791 e2
= e2
->next_callee
;
795 return return_false_with_msg ("different number of calls");
797 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
798 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
802 if (!compare_edge_flags (e1
, e2
))
805 e1
= e1
->next_callee
;
806 e2
= e2
->next_callee
;
810 return return_false_with_msg ("different number of indirect calls");
815 /* Update hash by address sensitive references. We iterate over all
816 sensitive references (address_matters_p) and we hash ultime alias
817 target of these nodes, which can improve a semantic item hash.
819 Also hash in referenced symbols properties. This can be done at any time
820 (as the properties should not change), but it is convenient to do it here
821 while we walk the references anyway. */
824 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
825 sem_item
*> &m_symtab_node_map
)
828 inchash::hash
hstate (hash
);
830 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
832 hstate
.add_int (ref
->use
);
833 hash_referenced_symbol_properties (ref
->referred
, hstate
,
834 ref
->use
== IPA_REF_ADDR
);
835 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
836 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
839 if (is_a
<cgraph_node
*> (node
))
841 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
844 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
845 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
847 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
851 hash
= hstate
.end ();
854 /* Update hash by computed local hash values taken from different
856 TODO: stronger SCC based hashing would be desirable here. */
859 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
860 sem_item
*> &m_symtab_node_map
)
863 inchash::hash
state (hash
);
865 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
867 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
869 state
.merge_hash ((*result
)->hash
);
874 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
877 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
879 state
.merge_hash ((*result
)->hash
);
883 global_hash
= state
.end ();
886 /* Returns true if the item equals to ITEM given as argument. */
889 sem_function::equals (sem_item
*item
,
890 hash_map
<symtab_node
*, sem_item
*> &)
892 gcc_assert (item
->type
== FUNC
);
893 bool eq
= equals_private (item
);
895 if (m_checker
!= NULL
)
901 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
903 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
904 xstrdup_for_dump (node
->name()),
905 xstrdup_for_dump (item
->node
->name ()),
908 xstrdup_for_dump (node
->asm_name ()),
909 xstrdup_for_dump (item
->node
->asm_name ()),
910 eq
? "true" : "false");
915 /* Processes function equality comparison. */
918 sem_function::equals_private (sem_item
*item
)
920 if (item
->type
!= FUNC
)
923 basic_block bb1
, bb2
;
925 edge_iterator ei1
, ei2
;
929 m_compared_func
= static_cast<sem_function
*> (item
);
931 gcc_assert (decl
!= item
->decl
);
933 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
934 || edge_count
!= m_compared_func
->edge_count
935 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
936 return return_false ();
938 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
939 compare_polymorphic_p (),
942 &m_compared_func
->refs_set
);
943 arg1
= DECL_ARGUMENTS (decl
);
944 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
946 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
948 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
949 return return_false_with_msg ("argument types are not compatible");
950 if (!param_used_p (i
))
952 /* Perform additional checks for used parameters. */
953 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
955 if (!m_checker
->compare_decl (arg1
, arg2
))
956 return return_false ();
959 return return_false_with_msg ("Mismatched number of arguments");
961 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
964 /* Fill-up label dictionary. */
965 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
967 m_checker
->parse_labels (bb_sorted
[i
]);
968 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
971 /* Checking all basic blocks. */
972 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
973 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
974 return return_false();
976 dump_message ("All BBs are equal\n");
978 auto_vec
<int> bb_dict
;
980 /* Basic block edges check. */
981 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
983 bb1
= bb_sorted
[i
]->bb
;
984 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
986 ei2
= ei_start (bb2
->preds
);
988 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
992 if (e1
->flags
!= e2
->flags
)
993 return return_false_with_msg ("flags comparison returns false");
995 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
996 return return_false_with_msg ("edge comparison returns false");
998 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
999 return return_false_with_msg ("BB comparison returns false");
1001 if (!m_checker
->compare_edge (e1
, e2
))
1002 return return_false_with_msg ("edge comparison returns false");
1008 /* Basic block PHI nodes comparison. */
1009 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
1010 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
1011 return return_false_with_msg ("PHI node comparison returns false");
1016 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
1017 Helper for call_for_symbol_thunks_and_aliases. */
1020 set_local (cgraph_node
*node
, void *data
)
1022 node
->local
.local
= data
!= NULL
;
1026 /* TREE_ADDRESSABLE of NODE to true.
1027 Helper for call_for_symbol_thunks_and_aliases. */
1030 set_addressable (varpool_node
*node
, void *)
1032 TREE_ADDRESSABLE (node
->decl
) = 1;
1036 /* Clear DECL_RTL of NODE.
1037 Helper for call_for_symbol_thunks_and_aliases. */
1040 clear_decl_rtl (symtab_node
*node
, void *)
1042 SET_DECL_RTL (node
->decl
, NULL
);
1046 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1047 possible. Return number of redirections made. */
1050 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1052 int nredirected
= 0;
1054 cgraph_edge
*e
= n
->callers
;
1058 /* Redirecting thunks to interposable symbols or symbols in other sections
1059 may not be supported by target output code. Play safe for now and
1060 punt on redirection. */
1061 if (!e
->caller
->thunk
.thunk_p
)
1063 struct cgraph_edge
*nexte
= e
->next_caller
;
1064 e
->redirect_callee (to
);
1071 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1073 bool removed
= false;
1074 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1076 if ((DECL_COMDAT_GROUP (n
->decl
)
1077 && (DECL_COMDAT_GROUP (n
->decl
)
1078 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1079 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1080 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1082 nredirected
+= redirect_all_callers (n_alias
, to
);
1083 if (n_alias
->can_remove_if_no_direct_calls_p ()
1084 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1086 && !n_alias
->has_aliases_p ())
1095 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1099 sem_function::merge (sem_item
*alias_item
)
1101 gcc_assert (alias_item
->type
== FUNC
);
1103 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1105 cgraph_node
*original
= get_node ();
1106 cgraph_node
*local_original
= NULL
;
1107 cgraph_node
*alias
= alias_func
->get_node ();
1109 bool create_wrapper
= false;
1110 bool create_alias
= false;
1111 bool redirect_callers
= false;
1112 bool remove
= false;
1114 bool original_discardable
= false;
1115 bool original_discarded
= false;
1117 bool original_address_matters
= original
->address_matters_p ();
1118 bool alias_address_matters
= alias
->address_matters_p ();
1120 if (DECL_EXTERNAL (alias
->decl
))
1123 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1127 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1128 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1133 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1137 /* Do not attempt to mix functions from different user sections;
1138 we do not know what user intends with those. */
1139 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1140 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1141 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1146 "original and alias are in different sections.\n\n");
1150 /* See if original is in a section that can be discarded if the main
1151 symbol is not used. */
1153 if (original
->can_be_discarded_p ())
1154 original_discardable
= true;
1155 /* Also consider case where we have resolution info and we know that
1156 original's definition is not going to be used. In this case we can not
1157 create alias to original. */
1158 if (node
->resolution
!= LDPR_UNKNOWN
1159 && !decl_binds_to_current_def_p (node
->decl
))
1160 original_discardable
= original_discarded
= true;
1162 /* Creating a symtab alias is the optimal way to merge.
1163 It however can not be used in the following cases:
1165 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1166 2) if ORIGINAL is in a section that may be discarded by linker or if
1167 it is an external functions where we can not create an alias
1168 (ORIGINAL_DISCARDABLE)
1169 3) if target do not support symbol aliases.
1170 4) original and alias lie in different comdat groups.
1172 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1173 and/or redirect all callers from ALIAS to ORIGINAL. */
1174 if ((original_address_matters
&& alias_address_matters
)
1175 || (original_discardable
1176 && (!DECL_COMDAT_GROUP (alias
->decl
)
1177 || (DECL_COMDAT_GROUP (alias
->decl
)
1178 != DECL_COMDAT_GROUP (original
->decl
))))
1179 || original_discarded
1180 || !sem_item::target_supports_symbol_aliases_p ()
1181 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1183 /* First see if we can produce wrapper. */
1185 /* Symbol properties that matter for references must be preserved.
1186 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1187 with proper properties. */
1188 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1189 alias
->address_taken
))
1193 "Wrapper cannot be created because referenced symbol "
1194 "properties mismatch\n");
1196 /* Do not turn function in one comdat group into wrapper to another
1197 comdat group. Other compiler producing the body of the
1198 another comdat group may make opossite decision and with unfortunate
1199 linker choices this may close a loop. */
1200 else if (DECL_COMDAT_GROUP (original
->decl
)
1201 && DECL_COMDAT_GROUP (alias
->decl
)
1202 && (DECL_COMDAT_GROUP (alias
->decl
)
1203 != DECL_COMDAT_GROUP (original
->decl
)))
1207 "Wrapper cannot be created because of COMDAT\n");
1209 else if (DECL_STATIC_CHAIN (alias
->decl
))
1213 "Can not create wrapper of nested functions.\n");
1215 /* TODO: We can also deal with variadic functions never calling
1217 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1221 "can not create wrapper of stdarg function.\n");
1223 else if (inline_summaries
1224 && inline_summaries
->get (alias
)->self_size
<= 2)
1227 fprintf (dump_file
, "Wrapper creation is not "
1228 "profitable (function is too small).\n");
1230 /* If user paid attention to mark function noinline, assume it is
1231 somewhat special and do not try to turn it into a wrapper that can
1232 not be undone by inliner. */
1233 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1236 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1239 create_wrapper
= true;
1241 /* We can redirect local calls in the case both alias and orignal
1242 are not interposable. */
1244 = alias
->get_availability () > AVAIL_INTERPOSABLE
1245 && original
->get_availability () > AVAIL_INTERPOSABLE
1246 && !alias
->instrumented_version
;
1247 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1248 with proper properties. */
1249 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1250 alias
->address_taken
))
1251 redirect_callers
= false;
1253 if (!redirect_callers
&& !create_wrapper
)
1256 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1257 "produce wrapper\n\n");
1261 /* Work out the symbol the wrapper should call.
1262 If ORIGINAL is interposable, we need to call a local alias.
1263 Also produce local alias (if possible) as an optimization.
1265 Local aliases can not be created inside comdat groups because that
1266 prevents inlining. */
1267 if (!original_discardable
&& !original
->get_comdat_group ())
1270 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1272 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1273 local_original
= original
;
1275 /* If we can not use local alias, fallback to the original
1277 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1278 local_original
= original
;
1280 /* If original is COMDAT local, we can not really redirect calls outside
1281 of its comdat group to it. */
1282 if (original
->comdat_local_p ())
1283 redirect_callers
= false;
1284 if (!local_original
)
1287 fprintf (dump_file
, "Not unifying; "
1288 "can not produce local alias.\n\n");
1292 if (!redirect_callers
&& !create_wrapper
)
1295 fprintf (dump_file
, "Not unifying; "
1296 "can not redirect callers nor produce a wrapper\n\n");
1300 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1302 && !alias
->can_remove_if_no_direct_calls_p ())
1305 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1306 "function has other uses than direct calls\n\n");
1311 create_alias
= true;
1313 if (redirect_callers
)
1315 int nredirected
= redirect_all_callers (alias
, local_original
);
1319 alias
->icf_merged
= true;
1320 local_original
->icf_merged
= true;
1322 if (dump_file
&& nredirected
)
1323 fprintf (dump_file
, "%i local calls have been "
1324 "redirected.\n", nredirected
);
1327 /* If all callers was redirected, do not produce wrapper. */
1328 if (alias
->can_remove_if_no_direct_calls_p ()
1329 && !alias
->has_aliases_p ())
1331 create_wrapper
= false;
1334 gcc_assert (!create_alias
);
1336 else if (create_alias
)
1338 alias
->icf_merged
= true;
1340 /* Remove the function's body. */
1341 ipa_merge_profiles (original
, alias
);
1342 alias
->release_body (true);
1344 /* Notice global symbol possibly produced RTL. */
1345 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1348 /* Create the alias. */
1349 cgraph_node::create_alias (alias_func
->decl
, decl
);
1350 alias
->resolve_alias (original
);
1352 original
->call_for_symbol_thunks_and_aliases
1353 (set_local
, (void *)(size_t) original
->local_p (), true);
1356 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1360 gcc_assert (!create_alias
);
1361 alias
->icf_merged
= true;
1362 local_original
->icf_merged
= true;
1364 ipa_merge_profiles (local_original
, alias
, true);
1365 alias
->create_wrapper (local_original
);
1368 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1371 /* It's possible that redirection can hit thunks that block
1372 redirection opportunities. */
1373 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1374 original
->icf_merged
= true;
1376 /* Inform the inliner about cross-module merging. */
1377 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1378 && original
->lto_file_data
!= alias
->lto_file_data
)
1379 local_original
->merged
= original
->merged
= true;
1383 ipa_merge_profiles (original
, alias
);
1384 alias
->release_body ();
1386 alias
->body_removed
= true;
1387 alias
->icf_merged
= true;
1389 fprintf (dump_file
, "Unified; Function body was removed.\n");
1395 /* Semantic item initialization function. */
1398 sem_function::init (void)
1401 get_node ()->get_untransformed_body ();
1403 tree fndecl
= node
->decl
;
1404 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1407 gcc_assert (SSANAMES (func
));
1409 ssa_names_size
= SSANAMES (func
)->length ();
1413 region_tree
= func
->eh
->region_tree
;
1415 /* iterating all function arguments. */
1416 arg_count
= count_formal_params (fndecl
);
1418 edge_count
= n_edges_for_fn (func
);
1419 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1420 if (!cnode
->thunk
.thunk_p
)
1422 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1424 inchash::hash hstate
;
1427 FOR_EACH_BB_FN (bb
, func
)
1429 unsigned nondbg_stmt_count
= 0;
1432 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1434 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1437 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1440 gimple stmt
= gsi_stmt (gsi
);
1442 if (gimple_code (stmt
) != GIMPLE_DEBUG
1443 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1445 hash_stmt (stmt
, hstate
);
1446 nondbg_stmt_count
++;
1450 gcode_hash
= hstate
.end ();
1451 bb_sizes
.safe_push (nondbg_stmt_count
);
1453 /* Inserting basic block to hash table. */
1454 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1455 EDGE_COUNT (bb
->preds
)
1456 + EDGE_COUNT (bb
->succs
));
1458 bb_sorted
.safe_push (semantic_bb
);
1464 inchash::hash hstate
;
1465 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1466 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1467 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1468 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1469 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1470 gcode_hash
= hstate
.end ();
1474 /* Accumulate to HSTATE a hash of expression EXP.
1475 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1476 and DECL equality classes. */
1479 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1481 if (exp
== NULL_TREE
)
1483 hstate
.merge_hash (0);
1487 /* Handled component can be matched in a cureful way proving equivalence
1488 even if they syntactically differ. Just skip them. */
1490 while (handled_component_p (exp
))
1491 exp
= TREE_OPERAND (exp
, 0);
1493 enum tree_code code
= TREE_CODE (exp
);
1494 hstate
.add_int (code
);
1498 /* Use inchash::add_expr for everything that is LTO stable. */
1506 inchash::add_expr (exp
, hstate
);
1510 unsigned HOST_WIDE_INT idx
;
1513 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1515 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1517 add_expr (value
, hstate
);
1522 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1528 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1531 case POINTER_PLUS_EXPR
:
1534 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1535 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1539 inchash::hash one
, two
;
1540 add_expr (TREE_OPERAND (exp
, 0), one
);
1541 add_expr (TREE_OPERAND (exp
, 1), two
);
1542 hstate
.add_commutative (one
, two
);
1546 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1547 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1553 /* Accumulate to HSTATE a hash of type t.
1554 TYpes that may end up being compatible after LTO type merging needs to have
1558 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1560 if (type
== NULL_TREE
)
1562 hstate
.merge_hash (0);
1566 type
= TYPE_MAIN_VARIANT (type
);
1567 if (TYPE_CANONICAL (type
))
1568 type
= TYPE_CANONICAL (type
);
1570 if (!AGGREGATE_TYPE_P (type
))
1571 hstate
.add_int (TYPE_MODE (type
));
1573 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1575 hstate
.add_int (COMPLEX_TYPE
);
1576 sem_item::add_type (TREE_TYPE (type
), hstate
);
1578 else if (INTEGRAL_TYPE_P (type
))
1580 hstate
.add_int (INTEGER_TYPE
);
1581 hstate
.add_flag (TYPE_UNSIGNED (type
));
1582 hstate
.add_int (TYPE_PRECISION (type
));
1584 else if (VECTOR_TYPE_P (type
))
1586 hstate
.add_int (VECTOR_TYPE
);
1587 hstate
.add_int (TYPE_PRECISION (type
));
1588 sem_item::add_type (TREE_TYPE (type
), hstate
);
1590 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1592 hstate
.add_int (ARRAY_TYPE
);
1593 /* Do not hash size, so complete and incomplete types can match. */
1594 sem_item::add_type (TREE_TYPE (type
), hstate
);
1596 else if (RECORD_OR_UNION_TYPE_P (type
))
1598 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1602 inchash::hash hstate2
;
1607 hstate2
.add_int (RECORD_TYPE
);
1608 gcc_assert (COMPLETE_TYPE_P (type
));
1610 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1611 if (TREE_CODE (f
) == FIELD_DECL
)
1613 add_type (TREE_TYPE (f
), hstate2
);
1617 hstate2
.add_int (nf
);
1618 hash
= hstate2
.end ();
1619 hstate
.add_wide_int (hash
);
1620 optimizer
->m_type_hash_cache
.put (type
, hash
);
1623 hstate
.add_wide_int (*val
);
1627 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1630 sem_function::hash_stmt (gimple stmt
, inchash::hash
&hstate
)
1632 enum gimple_code code
= gimple_code (stmt
);
1634 hstate
.add_int (code
);
1639 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1642 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1643 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1644 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1646 inchash::hash one
, two
;
1648 add_expr (gimple_assign_rhs1 (stmt
), one
);
1649 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1650 add_expr (gimple_assign_rhs2 (stmt
), two
);
1651 hstate
.add_commutative (one
, two
);
1652 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1654 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1655 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1657 add_expr (gimple_assign_lhs (stmt
), hstate
);
1658 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1661 /* ... fall through ... */
1667 /* All these statements are equivalent if their operands are. */
1668 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1670 add_expr (gimple_op (stmt
, i
), hstate
);
1671 if (gimple_op (stmt
, i
))
1672 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1680 /* Return true if polymorphic comparison must be processed. */
1683 sem_function::compare_polymorphic_p (void)
1685 struct cgraph_edge
*e
;
1687 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1689 if (get_node ()->indirect_calls
!= NULL
)
1691 /* TODO: We can do simple propagation determining what calls may lead to
1692 a polymorphic call. */
1693 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1694 if (e
->callee
->definition
1695 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1700 /* For a given call graph NODE, the function constructs new
1701 semantic function item. */
1704 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1706 tree fndecl
= node
->decl
;
1707 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1709 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1712 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1715 sem_function
*f
= new sem_function (node
, 0, stack
);
1722 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1723 return true if phi nodes are semantically equivalent in these blocks . */
1726 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1728 gphi_iterator si1
, si2
;
1730 unsigned size1
, size2
, i
;
1734 gcc_assert (bb1
!= NULL
);
1735 gcc_assert (bb2
!= NULL
);
1737 si2
= gsi_start_phis (bb2
);
1738 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1741 gsi_next_nonvirtual_phi (&si1
);
1742 gsi_next_nonvirtual_phi (&si2
);
1744 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1747 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1748 return return_false();
1753 tree phi_result1
= gimple_phi_result (phi1
);
1754 tree phi_result2
= gimple_phi_result (phi2
);
1756 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1757 return return_false_with_msg ("PHI results are different");
1759 size1
= gimple_phi_num_args (phi1
);
1760 size2
= gimple_phi_num_args (phi2
);
1763 return return_false ();
1765 for (i
= 0; i
< size1
; ++i
)
1767 t1
= gimple_phi_arg (phi1
, i
)->def
;
1768 t2
= gimple_phi_arg (phi2
, i
)->def
;
1770 if (!m_checker
->compare_operand (t1
, t2
))
1771 return return_false ();
1773 e1
= gimple_phi_arg_edge (phi1
, i
);
1774 e2
= gimple_phi_arg_edge (phi2
, i
);
1776 if (!m_checker
->compare_edge (e1
, e2
))
1777 return return_false ();
1786 /* Returns true if tree T can be compared as a handled component. */
1789 sem_function::icf_handled_component_p (tree t
)
1791 tree_code tc
= TREE_CODE (t
);
1793 return (handled_component_p (t
)
1794 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1797 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1798 corresponds to TARGET. */
1801 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1806 if (bb_dict
->length () <= (unsigned)source
)
1807 bb_dict
->safe_grow_cleared (source
+ 1);
1809 if ((*bb_dict
)[source
] == 0)
1811 (*bb_dict
)[source
] = target
;
1815 return (*bb_dict
)[source
] == target
;
1819 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1821 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1825 /* Constructor based on varpool node _NODE with computed hash _HASH.
1826 Bitmap STACK is used for memory allocation. */
1828 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1829 bitmap_obstack
*stack
): sem_item(VAR
,
1832 gcc_checking_assert (node
);
1833 gcc_checking_assert (get_node ());
1836 /* Fast equality function based on knowledge known in WPA. */
1839 sem_variable::equals_wpa (sem_item
*item
,
1840 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1842 gcc_assert (item
->type
== VAR
);
1844 if (node
->num_references () != item
->node
->num_references ())
1845 return return_false_with_msg ("different number of references");
1847 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1848 return return_false_with_msg ("TLS model");
1850 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1851 alignment out of all aliases. */
1853 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1854 return return_false_with_msg ("Virtual flag mismatch");
1856 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1857 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1858 || !operand_equal_p (DECL_SIZE (decl
),
1859 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1860 return return_false_with_msg ("size mismatch");
1862 /* Do not attempt to mix data from different user sections;
1863 we do not know what user intends with those. */
1864 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1865 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1866 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1867 return return_false_with_msg ("user section mismatch");
1869 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1870 return return_false_with_msg ("text section");
1872 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1873 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1875 item
->node
->iterate_reference (i
, ref2
);
1877 if (ref
->use
!= ref2
->use
)
1878 return return_false_with_msg ("reference use mismatch");
1880 if (!compare_symbol_references (ignored_nodes
,
1881 ref
->referred
, ref2
->referred
,
1882 ref
->address_matters_p ()))
1889 /* Returns true if the item equals to ITEM given as argument. */
1892 sem_variable::equals (sem_item
*item
,
1893 hash_map
<symtab_node
*, sem_item
*> &)
1895 gcc_assert (item
->type
== VAR
);
1898 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1899 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1900 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1901 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1903 /* As seen in PR ipa/65303 we have to compare variables types. */
1904 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1905 TREE_TYPE (item
->decl
)))
1906 return return_false_with_msg ("variables types are different");
1908 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1909 DECL_INITIAL (item
->node
->decl
));
1910 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1912 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1913 xstrdup_for_dump (node
->name()),
1914 xstrdup_for_dump (item
->node
->name ()),
1915 node
->order
, item
->node
->order
,
1916 xstrdup_for_dump (node
->asm_name ()),
1917 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1922 /* Compares trees T1 and T2 for semantic equality. */
1925 sem_variable::equals (tree t1
, tree t2
)
1928 return return_with_debug (t1
== t2
);
1931 tree_code tc1
= TREE_CODE (t1
);
1932 tree_code tc2
= TREE_CODE (t2
);
1935 return return_false_with_msg ("TREE_CODE mismatch");
1941 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1942 unsigned HOST_WIDE_INT idx
;
1944 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1945 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1946 return return_false_with_msg ("constructor type mismatch");
1948 if (typecode
== ARRAY_TYPE
)
1950 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1951 /* For arrays, check that the sizes all match. */
1952 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1954 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1955 return return_false_with_msg ("constructor array size mismatch");
1957 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1959 return return_false_with_msg ("constructor type incompatible");
1961 v1
= CONSTRUCTOR_ELTS (t1
);
1962 v2
= CONSTRUCTOR_ELTS (t2
);
1963 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1964 return return_false_with_msg ("constructor number of elts mismatch");
1966 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1968 constructor_elt
*c1
= &(*v1
)[idx
];
1969 constructor_elt
*c2
= &(*v2
)[idx
];
1971 /* Check that each value is the same... */
1972 if (!sem_variable::equals (c1
->value
, c2
->value
))
1974 /* ... and that they apply to the same fields! */
1975 if (!sem_variable::equals (c1
->index
, c2
->index
))
1982 tree x1
= TREE_OPERAND (t1
, 0);
1983 tree x2
= TREE_OPERAND (t2
, 0);
1984 tree y1
= TREE_OPERAND (t1
, 1);
1985 tree y2
= TREE_OPERAND (t2
, 1);
1987 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1988 return return_false ();
1990 /* Type of the offset on MEM_REF does not matter. */
1991 return return_with_debug (sem_variable::equals (x1
, x2
)
1992 && wi::to_offset (y1
)
1993 == wi::to_offset (y2
));
1998 tree op1
= TREE_OPERAND (t1
, 0);
1999 tree op2
= TREE_OPERAND (t2
, 0);
2000 return sem_variable::equals (op1
, op2
);
2002 /* References to other vars/decls are compared using ipa-ref. */
2005 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
2007 return return_false_with_msg ("Declaration mismatch");
2009 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
2010 need to process its VAR/FUNCTION references without relying on ipa-ref
2014 return return_false_with_msg ("Declaration mismatch");
2016 /* Integer constants are the same only if the same width of type. */
2017 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2018 return return_false_with_msg ("INTEGER_CST precision mismatch");
2019 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2020 return return_false_with_msg ("INTEGER_CST mode mismatch");
2021 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2023 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2024 return return_false_with_msg ("STRING_CST mode mismatch");
2025 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2026 return return_false_with_msg ("STRING_CST length mismatch");
2027 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2028 TREE_STRING_LENGTH (t1
)))
2029 return return_false_with_msg ("STRING_CST mismatch");
2032 /* Fixed constants are the same only if the same width of type. */
2033 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2034 return return_false_with_msg ("FIXED_CST precision mismatch");
2036 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2037 TREE_FIXED_CST (t2
)));
2039 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2040 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2042 /* Real constants are the same only if the same width of type. */
2043 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2044 return return_false_with_msg ("REAL_CST precision mismatch");
2045 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1
),
2046 TREE_REAL_CST (t2
)));
2051 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2052 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2054 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2055 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2056 VECTOR_CST_ELT (t2
, i
)))
2062 case ARRAY_RANGE_REF
:
2064 tree x1
= TREE_OPERAND (t1
, 0);
2065 tree x2
= TREE_OPERAND (t2
, 0);
2066 tree y1
= TREE_OPERAND (t1
, 1);
2067 tree y2
= TREE_OPERAND (t2
, 1);
2069 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2071 if (!sem_variable::equals (array_ref_low_bound (t1
),
2072 array_ref_low_bound (t2
)))
2074 if (!sem_variable::equals (array_ref_element_size (t1
),
2075 array_ref_element_size (t2
)))
2081 case POINTER_PLUS_EXPR
:
2086 tree x1
= TREE_OPERAND (t1
, 0);
2087 tree x2
= TREE_OPERAND (t2
, 0);
2088 tree y1
= TREE_OPERAND (t1
, 1);
2089 tree y2
= TREE_OPERAND (t2
, 1);
2091 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2095 case VIEW_CONVERT_EXPR
:
2096 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2097 return return_false ();
2098 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2100 return return_false_with_msg ("ERROR_MARK");
2102 return return_false_with_msg ("Unknown TREE code reached");
2106 /* Parser function that visits a varpool NODE. */
2109 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2111 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2115 sem_variable
*v
= new sem_variable (node
, 0, stack
);
2122 /* References independent hash function. */
2125 sem_variable::get_hash (void)
2130 /* All WPA streamed in symbols should have their hashes computed at compile
2131 time. At this point, the constructor may not be in memory at all.
2132 DECL_INITIAL (decl) would be error_mark_node in that case. */
2133 gcc_assert (!node
->lto_file_data
);
2134 tree ctor
= DECL_INITIAL (decl
);
2135 inchash::hash hstate
;
2137 hstate
.add_int (456346417);
2138 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2139 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2140 add_expr (ctor
, hstate
);
2141 hash
= hstate
.end ();
2146 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2150 sem_variable::merge (sem_item
*alias_item
)
2152 gcc_assert (alias_item
->type
== VAR
);
2154 if (!sem_item::target_supports_symbol_aliases_p ())
2157 fprintf (dump_file
, "Not unifying; "
2158 "Symbol aliases are not supported by target\n\n");
2162 if (DECL_EXTERNAL (alias_item
->decl
))
2165 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2169 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2171 varpool_node
*original
= get_node ();
2172 varpool_node
*alias
= alias_var
->get_node ();
2173 bool original_discardable
= false;
2175 bool original_address_matters
= original
->address_matters_p ();
2176 bool alias_address_matters
= alias
->address_matters_p ();
2178 /* See if original is in a section that can be discarded if the main
2180 Also consider case where we have resolution info and we know that
2181 original's definition is not going to be used. In this case we can not
2182 create alias to original. */
2183 if (original
->can_be_discarded_p ()
2184 || (node
->resolution
!= LDPR_UNKNOWN
2185 && !decl_binds_to_current_def_p (node
->decl
)))
2186 original_discardable
= true;
2188 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2190 /* Constant pool machinery is not quite ready for aliases.
2191 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2192 For LTO merging does not happen that is an important missing feature.
2193 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2194 flag is dropped and non-local symbol name is assigned. */
2195 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2196 || DECL_IN_CONSTANT_POOL (original
->decl
))
2200 "Not unifying; constant pool variables.\n\n");
2204 /* Do not attempt to mix functions from different user sections;
2205 we do not know what user intends with those. */
2206 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2207 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2208 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2213 "original and alias are in different sections.\n\n");
2217 /* We can not merge if address comparsion metters. */
2218 if (original_address_matters
&& alias_address_matters
2219 && flag_merge_constants
< 2)
2224 "adress of original and alias may be compared.\n\n");
2227 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2230 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2231 "across comdat group boundary\n\n");
2236 if (original_discardable
)
2239 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2240 "target is discardable\n\n");
2246 gcc_assert (!original
->alias
);
2247 gcc_assert (!alias
->alias
);
2249 alias
->analyzed
= false;
2251 DECL_INITIAL (alias
->decl
) = NULL
;
2252 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2254 alias
->need_bounds_init
= false;
2255 alias
->remove_all_references ();
2256 if (TREE_ADDRESSABLE (alias
->decl
))
2257 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2259 varpool_node::create_alias (alias_var
->decl
, decl
);
2260 alias
->resolve_alias (original
);
2263 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
2269 /* Dump symbol to FILE. */
2272 sem_variable::dump_to_file (FILE *file
)
2276 print_node (file
, "", decl
, 0);
2277 fprintf (file
, "\n\n");
2280 unsigned int sem_item_optimizer::class_id
= 0;
2282 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2283 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2286 bitmap_obstack_initialize (&m_bmstack
);
2289 sem_item_optimizer::~sem_item_optimizer ()
2291 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2294 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2295 it
!= m_classes
.end (); ++it
)
2297 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2298 delete (*it
)->classes
[i
];
2300 (*it
)->classes
.release ();
2306 bitmap_obstack_release (&m_bmstack
);
2309 /* Write IPA ICF summary for symbols. */
2312 sem_item_optimizer::write_summary (void)
2314 unsigned int count
= 0;
2316 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2317 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2320 /* Calculate number of symbols to be serialized. */
2321 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2323 lsei_next_in_partition (&lsei
))
2325 symtab_node
*node
= lsei_node (lsei
);
2327 if (m_symtab_node_map
.get (node
))
2331 streamer_write_uhwi (ob
, count
);
2333 /* Process all of the symbols. */
2334 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2336 lsei_next_in_partition (&lsei
))
2338 symtab_node
*node
= lsei_node (lsei
);
2340 sem_item
**item
= m_symtab_node_map
.get (node
);
2344 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2345 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2347 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2351 streamer_write_char_stream (ob
->main_stream
, 0);
2352 produce_asm (ob
, NULL
);
2353 destroy_output_block (ob
);
2356 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2357 contains LEN bytes. */
2360 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2361 const char *data
, size_t len
)
2363 const lto_function_header
*header
=
2364 (const lto_function_header
*) data
;
2365 const int cfg_offset
= sizeof (lto_function_header
);
2366 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2367 const int string_offset
= main_offset
+ header
->main_size
;
2372 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2373 header
->main_size
, file_data
->mode_table
);
2376 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2377 header
->string_size
, vNULL
);
2379 count
= streamer_read_uhwi (&ib_main
);
2381 for (i
= 0; i
< count
; i
++)
2385 lto_symtab_encoder_t encoder
;
2387 index
= streamer_read_uhwi (&ib_main
);
2388 encoder
= file_data
->symtab_node_encoder
;
2389 node
= lto_symtab_encoder_deref (encoder
, index
);
2391 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2393 gcc_assert (node
->definition
);
2396 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2397 node
->asm_name (), (void *) node
->decl
, node
->order
);
2399 if (is_a
<cgraph_node
*> (node
))
2401 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2403 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2407 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2409 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2413 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2415 lto_data_in_delete (data_in
);
2418 /* Read IPA IPA ICF summary for symbols. */
2421 sem_item_optimizer::read_summary (void)
2423 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2424 lto_file_decl_data
*file_data
;
2427 while ((file_data
= file_data_vec
[j
++]))
2430 const char *data
= lto_get_section_data (file_data
,
2431 LTO_section_ipa_icf
, NULL
, &len
);
2434 read_section (file_data
, data
, len
);
2438 /* Register callgraph and varpool hooks. */
2441 sem_item_optimizer::register_hooks (void)
2443 if (!m_cgraph_node_hooks
)
2444 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2445 (&sem_item_optimizer::cgraph_removal_hook
, this);
2447 if (!m_varpool_node_hooks
)
2448 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2449 (&sem_item_optimizer::varpool_removal_hook
, this);
2452 /* Unregister callgraph and varpool hooks. */
2455 sem_item_optimizer::unregister_hooks (void)
2457 if (m_cgraph_node_hooks
)
2458 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2460 if (m_varpool_node_hooks
)
2461 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2464 /* Adds a CLS to hashtable associated by hash value. */
2467 sem_item_optimizer::add_class (congruence_class
*cls
)
2469 gcc_assert (cls
->members
.length ());
2471 congruence_class_group
*group
= get_group_by_hash (
2472 cls
->members
[0]->get_hash (),
2473 cls
->members
[0]->type
);
2474 group
->classes
.safe_push (cls
);
2477 /* Gets a congruence class group based on given HASH value and TYPE. */
2479 congruence_class_group
*
2480 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2482 congruence_class_group
*item
= XNEW (congruence_class_group
);
2486 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2492 item
->classes
.create (1);
2499 /* Callgraph removal hook called for a NODE with a custom DATA. */
2502 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2504 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2505 optimizer
->remove_symtab_node (node
);
2508 /* Varpool removal hook called for a NODE with a custom DATA. */
2511 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2513 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2514 optimizer
->remove_symtab_node (node
);
2517 /* Remove symtab NODE triggered by symtab removal hooks. */
2520 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2522 gcc_assert (!m_classes
.elements());
2524 m_removed_items_set
.add (node
);
2528 sem_item_optimizer::remove_item (sem_item
*item
)
2530 if (m_symtab_node_map
.get (item
->node
))
2531 m_symtab_node_map
.remove (item
->node
);
2535 /* Removes all callgraph and varpool nodes that are marked by symtab
2539 sem_item_optimizer::filter_removed_items (void)
2541 auto_vec
<sem_item
*> filtered
;
2543 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2545 sem_item
*item
= m_items
[i
];
2547 if (m_removed_items_set
.contains (item
->node
))
2553 if (item
->type
== FUNC
)
2555 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2557 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2560 filtered
.safe_push (item
);
2564 if (!flag_ipa_icf_variables
)
2568 /* Filter out non-readonly variables. */
2569 tree decl
= item
->decl
;
2570 if (TREE_READONLY (decl
))
2571 filtered
.safe_push (item
);
2578 /* Clean-up of released semantic items. */
2581 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2582 m_items
.safe_push (filtered
[i
]);
2585 /* Optimizer entry point which returns true in case it processes
2586 a merge operation. True is returned if there's a merge operation
2590 sem_item_optimizer::execute (void)
2592 filter_removed_items ();
2593 unregister_hooks ();
2596 update_hash_by_addr_refs ();
2597 build_hash_based_classes ();
2600 fprintf (dump_file
, "Dump after hash based groups\n");
2601 dump_cong_classes ();
2603 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2604 m_items
[i
]->init_wpa ();
2606 subdivide_classes_by_equality (true);
2609 fprintf (dump_file
, "Dump after WPA based types groups\n");
2611 dump_cong_classes ();
2613 process_cong_reduction ();
2617 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2619 dump_cong_classes ();
2621 parse_nonsingleton_classes ();
2622 subdivide_classes_by_equality ();
2625 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2627 dump_cong_classes ();
2629 unsigned int prev_class_count
= m_classes_count
;
2631 process_cong_reduction ();
2632 dump_cong_classes ();
2634 bool merged_p
= merge_classes (prev_class_count
);
2636 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2637 symtab_node::dump_table (dump_file
);
2642 /* Function responsible for visiting all potential functions and
2643 read-only variables that can be merged. */
2646 sem_item_optimizer::parse_funcs_and_vars (void)
2650 if (flag_ipa_icf_functions
)
2651 FOR_EACH_DEFINED_FUNCTION (cnode
)
2653 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2656 m_items
.safe_push (f
);
2657 m_symtab_node_map
.put (cnode
, f
);
2660 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2662 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2663 f
->dump_to_file (dump_file
);
2666 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2669 varpool_node
*vnode
;
2671 if (flag_ipa_icf_variables
)
2672 FOR_EACH_DEFINED_VARIABLE (vnode
)
2674 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2678 m_items
.safe_push (v
);
2679 m_symtab_node_map
.put (vnode
, v
);
2684 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2687 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2689 item
->index_in_class
= cls
->members
.length ();
2690 cls
->members
.safe_push (item
);
2694 /* For each semantic item, append hash values of references. */
2697 sem_item_optimizer::update_hash_by_addr_refs ()
2699 /* First, append to hash sensitive references and class type if it need to
2700 be matched for ODR. */
2701 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2703 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2704 if (m_items
[i
]->type
== FUNC
)
2706 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2707 && contains_polymorphic_type_p
2708 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2709 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2710 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2711 && static_cast<sem_function
*> (m_items
[i
])
2712 ->compare_polymorphic_p ())))
2715 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2716 inchash::hash
hstate (m_items
[i
]->hash
);
2718 if (TYPE_NAME (class_type
)
2719 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2721 (IDENTIFIER_HASH_VALUE
2722 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2724 m_items
[i
]->hash
= hstate
.end ();
2729 /* Once all symbols have enhanced hash value, we can append
2730 hash values of symbols that are seen by IPA ICF and are
2731 references by a semantic item. Newly computed values
2732 are saved to global_hash member variable. */
2733 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2734 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2736 /* Global hash value replace current hash values. */
2737 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2738 m_items
[i
]->hash
= m_items
[i
]->global_hash
;
2741 /* Congruence classes are built by hash value. */
2744 sem_item_optimizer::build_hash_based_classes (void)
2746 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2748 sem_item
*item
= m_items
[i
];
2750 congruence_class_group
*group
= get_group_by_hash (item
->hash
,
2753 if (!group
->classes
.length ())
2756 group
->classes
.safe_push (new congruence_class (class_id
++));
2759 add_item_to_class (group
->classes
[0], item
);
2763 /* Build references according to call graph. */
2766 sem_item_optimizer::build_graph (void)
2768 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2770 sem_item
*item
= m_items
[i
];
2771 m_symtab_node_map
.put (item
->node
, item
);
2774 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2776 sem_item
*item
= m_items
[i
];
2778 if (item
->type
== FUNC
)
2780 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2782 cgraph_edge
*e
= cnode
->callees
;
2785 sem_item
**slot
= m_symtab_node_map
.get
2786 (e
->callee
->ultimate_alias_target ());
2788 item
->add_reference (*slot
);
2794 ipa_ref
*ref
= NULL
;
2795 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2797 sem_item
**slot
= m_symtab_node_map
.get
2798 (ref
->referred
->ultimate_alias_target ());
2800 item
->add_reference (*slot
);
2805 /* Semantic items in classes having more than one element and initialized.
2806 In case of WPA, we load function body. */
2809 sem_item_optimizer::parse_nonsingleton_classes (void)
2811 unsigned int init_called_count
= 0;
2813 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2814 if (m_items
[i
]->cls
->members
.length () > 1)
2816 m_items
[i
]->init ();
2817 init_called_count
++;
2821 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2822 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2825 /* Equality function for semantic items is used to subdivide existing
2826 classes. If IN_WPA, fast equality function is invoked. */
2829 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2831 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2832 it
!= m_classes
.end (); ++it
)
2834 unsigned int class_count
= (*it
)->classes
.length ();
2836 for (unsigned i
= 0; i
< class_count
; i
++)
2838 congruence_class
*c
= (*it
)->classes
[i
];
2840 if (c
->members
.length() > 1)
2842 auto_vec
<sem_item
*> new_vector
;
2844 sem_item
*first
= c
->members
[0];
2845 new_vector
.safe_push (first
);
2847 unsigned class_split_first
= (*it
)->classes
.length ();
2849 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2851 sem_item
*item
= c
->members
[j
];
2853 bool equals
= in_wpa
? first
->equals_wpa (item
,
2854 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2857 new_vector
.safe_push (item
);
2860 bool integrated
= false;
2862 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2864 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2865 bool equals
= in_wpa
? x
->equals_wpa (item
,
2866 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2871 add_item_to_class ((*it
)->classes
[k
], item
);
2879 congruence_class
*c
= new congruence_class (class_id
++);
2881 add_item_to_class (c
, item
);
2883 (*it
)->classes
.safe_push (c
);
2888 // we replace newly created new_vector for the class we've just splitted
2889 c
->members
.release ();
2890 c
->members
.create (new_vector
.length ());
2892 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2893 add_item_to_class (c
, new_vector
[j
]);
2901 /* Subdivide classes by address references that members of the class
2902 reference. Example can be a pair of functions that have an address
2903 taken from a function. If these addresses are different the class
2907 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2909 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2911 unsigned newly_created_classes
= 0;
2913 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2914 it
!= m_classes
.end (); ++it
)
2916 unsigned int class_count
= (*it
)->classes
.length ();
2917 auto_vec
<congruence_class
*> new_classes
;
2919 for (unsigned i
= 0; i
< class_count
; i
++)
2921 congruence_class
*c
= (*it
)->classes
[i
];
2923 if (c
->members
.length() > 1)
2925 subdivide_hash_map split_map
;
2927 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2929 sem_item
*source_node
= c
->members
[j
];
2931 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2934 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2936 gcc_checking_assert (slot
);
2938 slot
->safe_push (source_node
);
2944 /* If the map contains more than one key, we have to split the map
2946 if (split_map
.elements () != 1)
2948 bool first_class
= true;
2950 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2951 it2
!= split_map
.end (); ++it2
)
2953 congruence_class
*new_cls
;
2954 new_cls
= new congruence_class (class_id
++);
2956 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2957 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2959 worklist_push (new_cls
);
2960 newly_created_classes
++;
2964 (*it
)->classes
[i
] = new_cls
;
2965 first_class
= false;
2969 new_classes
.safe_push (new_cls
);
2975 /* Release memory. */
2976 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2977 it2
!= split_map
.end (); ++it2
)
2979 delete (*it2
).first
;
2980 (*it2
).second
.release ();
2985 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2986 (*it
)->classes
.safe_push (new_classes
[i
]);
2989 return newly_created_classes
;
2992 /* Verify congruence classes if checking is enabled. */
2995 sem_item_optimizer::verify_classes (void)
2998 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2999 it
!= m_classes
.end (); ++it
)
3001 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3003 congruence_class
*cls
= (*it
)->classes
[i
];
3005 gcc_checking_assert (cls
);
3006 gcc_checking_assert (cls
->members
.length () > 0);
3008 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3010 sem_item
*item
= cls
->members
[j
];
3012 gcc_checking_assert (item
);
3013 gcc_checking_assert (item
->cls
== cls
);
3015 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3017 sem_usage_pair
*usage
= item
->usages
[k
];
3018 gcc_checking_assert (usage
->item
->index_in_class
<
3019 usage
->item
->cls
->members
.length ());
3027 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3028 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3029 but unused argument. */
3032 sem_item_optimizer::release_split_map (congruence_class
* const &,
3033 bitmap
const &b
, traverse_split_pair
*)
3042 /* Process split operation for a class given as pointer CLS_PTR,
3043 where bitmap B splits congruence class members. DATA is used
3044 as argument of split pair. */
3047 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3048 bitmap
const &b
, traverse_split_pair
*pair
)
3050 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3051 const congruence_class
*splitter_cls
= pair
->cls
;
3053 /* If counted bits are greater than zero and less than the number of members
3054 a group will be splitted. */
3055 unsigned popcount
= bitmap_count_bits (b
);
3057 if (popcount
> 0 && popcount
< cls
->members
.length ())
3059 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
3061 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3063 int target
= bitmap_bit_p (b
, i
);
3064 congruence_class
*tc
= newclasses
[target
];
3066 add_item_to_class (tc
, cls
->members
[i
]);
3069 #ifdef ENABLE_CHECKING
3070 for (unsigned int i
= 0; i
< 2; i
++)
3071 gcc_checking_assert (newclasses
[i
]->members
.length ());
3074 if (splitter_cls
== cls
)
3075 optimizer
->splitter_class_removed
= true;
3077 /* Remove old class from worklist if presented. */
3078 bool in_worklist
= cls
->in_worklist
;
3081 cls
->in_worklist
= false;
3083 congruence_class_group g
;
3084 g
.hash
= cls
->members
[0]->get_hash ();
3085 g
.type
= cls
->members
[0]->type
;
3087 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3089 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3090 if (slot
->classes
[i
] == cls
)
3092 slot
->classes
.ordered_remove (i
);
3096 /* New class will be inserted and integrated to work list. */
3097 for (unsigned int i
= 0; i
< 2; i
++)
3098 optimizer
->add_class (newclasses
[i
]);
3100 /* Two classes replace one, so that increment just by one. */
3101 optimizer
->m_classes_count
++;
3103 /* If OLD class was presented in the worklist, we remove the class
3104 and replace it will both newly created classes. */
3106 for (unsigned int i
= 0; i
< 2; i
++)
3107 optimizer
->worklist_push (newclasses
[i
]);
3108 else /* Just smaller class is inserted. */
3110 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3111 newclasses
[1]->members
.length () ?
3113 optimizer
->worklist_push (newclasses
[smaller_index
]);
3116 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3118 fprintf (dump_file
, " congruence class splitted:\n");
3119 cls
->dump (dump_file
, 4);
3121 fprintf (dump_file
, " newly created groups:\n");
3122 for (unsigned int i
= 0; i
< 2; i
++)
3123 newclasses
[i
]->dump (dump_file
, 4);
3126 /* Release class if not presented in work list. */
3135 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3136 Bitmap stack BMSTACK is used for bitmap allocation. */
3139 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3142 hash_map
<congruence_class
*, bitmap
> split_map
;
3144 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3146 sem_item
*item
= cls
->members
[i
];
3148 /* Iterate all usages that have INDEX as usage of the item. */
3149 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3151 sem_usage_pair
*usage
= item
->usages
[j
];
3153 if (usage
->index
!= index
)
3156 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3161 b
= BITMAP_ALLOC (&m_bmstack
);
3162 split_map
.put (usage
->item
->cls
, b
);
3168 gcc_checking_assert (usage
->item
->cls
);
3169 gcc_checking_assert (usage
->item
->index_in_class
<
3170 usage
->item
->cls
->members
.length ());
3173 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3177 traverse_split_pair pair
;
3178 pair
.optimizer
= this;
3181 splitter_class_removed
= false;
3183 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3185 /* Bitmap clean-up. */
3187 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3190 /* Every usage of a congruence class CLS is a candidate that can split the
3191 collection of classes. Bitmap stack BMSTACK is used for bitmap
3195 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3200 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3202 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3203 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3205 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3207 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3208 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
3211 do_congruence_step_for_index (cls
, i
);
3213 if (splitter_class_removed
)
3217 BITMAP_FREE (usage
);
3220 /* Adds a newly created congruence class CLS to worklist. */
3223 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3225 /* Return if the class CLS is already presented in work list. */
3226 if (cls
->in_worklist
)
3229 cls
->in_worklist
= true;
3230 worklist
.push_back (cls
);
3233 /* Pops a class from worklist. */
3236 sem_item_optimizer::worklist_pop (void)
3238 congruence_class
*cls
;
3240 while (!worklist
.empty ())
3242 cls
= worklist
.front ();
3243 worklist
.pop_front ();
3244 if (cls
->in_worklist
)
3246 cls
->in_worklist
= false;
3252 /* Work list item was already intended to be removed.
3253 The only reason for doing it is to split a class.
3254 Thus, the class CLS is deleted. */
3262 /* Iterative congruence reduction function. */
3265 sem_item_optimizer::process_cong_reduction (void)
3267 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3268 it
!= m_classes
.end (); ++it
)
3269 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3270 if ((*it
)->classes
[i
]->is_class_used ())
3271 worklist_push ((*it
)->classes
[i
]);
3274 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3275 (unsigned long) worklist
.size ());
3277 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3278 fprintf (dump_file
, "Congruence class reduction\n");
3280 congruence_class
*cls
;
3282 /* Process complete congruence reduction. */
3283 while ((cls
= worklist_pop ()) != NULL
)
3284 do_congruence_step (cls
);
3286 /* Subdivide newly created classes according to references. */
3287 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3290 fprintf (dump_file
, "Address reference subdivision created: %u "
3291 "new classes.\n", new_classes
);
3294 /* Debug function prints all informations about congruence classes. */
3297 sem_item_optimizer::dump_cong_classes (void)
3303 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3304 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3306 /* Histogram calculation. */
3307 unsigned int max_index
= 0;
3308 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3310 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3311 it
!= m_classes
.end (); ++it
)
3313 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3315 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3323 "Class size histogram [num of members]: number of classe number of classess\n");
3325 for (unsigned int i
= 0; i
<= max_index
; i
++)
3327 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3329 fprintf (dump_file
, "\n\n");
3332 if (dump_flags
& TDF_DETAILS
)
3333 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3334 it
!= m_classes
.end (); ++it
)
3336 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3338 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3340 (*it
)->classes
[i
]->dump (dump_file
, 4);
3342 if(i
< (*it
)->classes
.length () - 1)
3343 fprintf (dump_file
, " ");
3350 /* After reduction is done, we can declare all items in a group
3351 to be equal. PREV_CLASS_COUNT is start number of classes
3352 before reduction. True is returned if there's a merge operation
3356 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3358 unsigned int item_count
= m_items
.length ();
3359 unsigned int class_count
= m_classes_count
;
3360 unsigned int equal_items
= item_count
- class_count
;
3362 unsigned int non_singular_classes_count
= 0;
3363 unsigned int non_singular_classes_sum
= 0;
3365 bool merged_p
= false;
3367 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3368 it
!= m_classes
.end (); ++it
)
3369 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3371 congruence_class
*c
= (*it
)->classes
[i
];
3372 if (c
->members
.length () > 1)
3374 non_singular_classes_count
++;
3375 non_singular_classes_sum
+= c
->members
.length ();
3381 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3382 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3383 prev_class_count
, class_count
);
3384 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3385 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3386 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3387 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3388 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3389 non_singular_classes_count
: 0.0f
,
3390 non_singular_classes_count
);
3391 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3392 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3393 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3396 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3397 it
!= m_classes
.end (); ++it
)
3398 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3400 congruence_class
*c
= (*it
)->classes
[i
];
3402 if (c
->members
.length () == 1)
3405 gcc_assert (c
->members
.length ());
3407 sem_item
*source
= c
->members
[0];
3409 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
3411 sem_item
*alias
= c
->members
[j
];
3415 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3416 xstrdup_for_dump (source
->node
->name ()),
3417 xstrdup_for_dump (alias
->node
->name ()));
3418 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3419 xstrdup_for_dump (source
->node
->asm_name ()),
3420 xstrdup_for_dump (alias
->node
->asm_name ()));
3423 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3427 "Merge operation is skipped due to no_icf "
3433 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3435 source
->dump_to_file (dump_file
);
3436 alias
->dump_to_file (dump_file
);
3439 if (dbg_cnt (merged_ipa_icf
))
3440 merged_p
|= source
->merge (alias
);
3447 /* Dump function prints all class members to a FILE with an INDENT. */
3450 congruence_class::dump (FILE *file
, unsigned int indent
) const
3452 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3453 id
, members
[0]->get_hash (), members
.length ());
3455 FPUTS_SPACES (file
, indent
+ 2, "");
3456 for (unsigned i
= 0; i
< members
.length (); i
++)
3457 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3458 (void *) members
[i
]->decl
,
3459 members
[i
]->node
->order
);
3461 fprintf (file
, "\n");
3464 /* Returns true if there's a member that is used from another group. */
3467 congruence_class::is_class_used (void)
3469 for (unsigned int i
= 0; i
< members
.length (); i
++)
3470 if (members
[i
]->usages
.length ())
3476 /* Generate pass summary for IPA ICF pass. */
3479 ipa_icf_generate_summary (void)
3482 optimizer
= new sem_item_optimizer ();
3484 optimizer
->register_hooks ();
3485 optimizer
->parse_funcs_and_vars ();
3488 /* Write pass summary for IPA ICF pass. */
3491 ipa_icf_write_summary (void)
3493 gcc_assert (optimizer
);
3495 optimizer
->write_summary ();
3498 /* Read pass summary for IPA ICF pass. */
3501 ipa_icf_read_summary (void)
3504 optimizer
= new sem_item_optimizer ();
3506 optimizer
->read_summary ();
3507 optimizer
->register_hooks ();
3510 /* Semantic equality exection function. */
3513 ipa_icf_driver (void)
3515 gcc_assert (optimizer
);
3517 bool merged_p
= optimizer
->execute ();
3522 return merged_p
? TODO_remove_functions
: 0;
3525 const pass_data pass_data_ipa_icf
=
3527 IPA_PASS
, /* type */
3529 OPTGROUP_IPA
, /* optinfo_flags */
3530 TV_IPA_ICF
, /* tv_id */
3531 0, /* properties_required */
3532 0, /* properties_provided */
3533 0, /* properties_destroyed */
3534 0, /* todo_flags_start */
3535 0, /* todo_flags_finish */
3538 class pass_ipa_icf
: public ipa_opt_pass_d
3541 pass_ipa_icf (gcc::context
*ctxt
)
3542 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3543 ipa_icf_generate_summary
, /* generate_summary */
3544 ipa_icf_write_summary
, /* write_summary */
3545 ipa_icf_read_summary
, /* read_summary */
3547 write_optimization_summary */
3549 read_optimization_summary */
3550 NULL
, /* stmt_fixup */
3551 0, /* function_transform_todo_flags_start */
3552 NULL
, /* function_transform */
3553 NULL
) /* variable_transform */
3556 /* opt_pass methods: */
3557 virtual bool gate (function
*)
3559 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3562 virtual unsigned int execute (function
*)
3564 return ipa_icf_driver();
3566 }; // class pass_ipa_icf
3568 } // ipa_icf namespace
3571 make_pass_ipa_icf (gcc::context
*ctxt
)
3573 return new ipa_icf::pass_ipa_icf (ctxt
);