1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
56 #include "coretypes.h"
62 #include "alloc-pool.h"
63 #include "tree-pass.h"
67 #include "gimple-pretty-print.h"
68 #include "data-streamer.h"
70 #include "fold-const.h"
73 #include "gimple-iterator.h"
75 #include "symbol-summary.h"
77 #include "ipa-inline.h"
80 #include "print-tree.h"
81 #include "ipa-utils.h"
82 #include "ipa-icf-gimple.h"
84 #include "stor-layout.h"
87 using namespace ipa_icf_gimple
;
91 /* Initialization and computation of symtab node hash, there data
92 are propagated later on. */
94 static sem_item_optimizer
*optimizer
= NULL
;
98 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
100 m_references
.create (0);
101 m_interposables
.create (0);
105 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
108 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
110 if (ref
->address_matters_p ())
111 m_references
.safe_push (ref
->referred
);
113 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
115 if (ref
->address_matters_p ())
116 m_references
.safe_push (ref
->referred
);
118 m_interposables
.safe_push (ref
->referred
);
122 if (is_a
<cgraph_node
*> (node
))
124 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
126 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
127 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
128 m_interposables
.safe_push (e
->callee
);
132 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
134 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
135 item (_item
), index (_index
)
139 /* Semantic item constructor for a node of _TYPE, where STACK is used
140 for bitmap memory allocation. */
142 sem_item::sem_item (sem_item_type _type
,
143 bitmap_obstack
*stack
): type(_type
), hash(0)
148 /* Semantic item constructor for a node of _TYPE, where STACK is used
149 for bitmap memory allocation. The item is based on symtab node _NODE
150 with computed _HASH. */
152 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
153 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
154 node (_node
), hash (_hash
)
160 /* Add reference to a semantic TARGET. */
163 sem_item::add_reference (sem_item
*target
)
165 refs
.safe_push (target
);
166 unsigned index
= refs
.length ();
167 target
->usages
.safe_push (new sem_usage_pair(this, index
));
168 bitmap_set_bit (target
->usage_index_bitmap
, index
);
169 refs_set
.add (target
->node
);
172 /* Initialize internal data structures. Bitmap STACK is used for
173 bitmap memory allocation process. */
176 sem_item::setup (bitmap_obstack
*stack
)
178 gcc_checking_assert (node
);
181 tree_refs
.create (0);
183 usage_index_bitmap
= BITMAP_ALLOC (stack
);
186 sem_item::~sem_item ()
188 for (unsigned i
= 0; i
< usages
.length (); i
++)
192 tree_refs
.release ();
195 BITMAP_FREE (usage_index_bitmap
);
198 /* Dump function for debugging purpose. */
201 sem_item::dump (void)
205 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
206 node
->name(), node
->order
, (void *) node
->decl
);
207 fprintf (dump_file
, " hash: %u\n", get_hash ());
208 fprintf (dump_file
, " references: ");
210 for (unsigned i
= 0; i
< refs
.length (); i
++)
211 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
212 i
< refs
.length() - 1 ? "," : "");
214 fprintf (dump_file
, "\n");
218 /* Return true if target supports alias symbols. */
221 sem_item::target_supports_symbol_aliases_p (void)
223 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
230 /* Semantic function constructor that uses STACK as bitmap memory stack. */
232 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
233 m_checker (NULL
), m_compared_func (NULL
)
236 bb_sorted
.create (0);
239 /* Constructor based on callgraph node _NODE with computed hash _HASH.
240 Bitmap STACK is used for memory allocation. */
241 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
242 bitmap_obstack
*stack
):
243 sem_item (FUNC
, node
, hash
, stack
),
244 m_checker (NULL
), m_compared_func (NULL
)
247 bb_sorted
.create (0);
250 sem_function::~sem_function ()
252 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
253 delete (bb_sorted
[i
]);
256 bb_sorted
.release ();
259 /* Calculates hash value based on a BASIC_BLOCK. */
262 sem_function::get_bb_hash (const sem_bb
*basic_block
)
264 inchash::hash hstate
;
266 hstate
.add_int (basic_block
->nondbg_stmt_count
);
267 hstate
.add_int (basic_block
->edge_count
);
269 return hstate
.end ();
272 /* References independent hash function. */
275 sem_function::get_hash (void)
279 inchash::hash hstate
;
280 hstate
.add_int (177454); /* Random number for function type. */
282 hstate
.add_int (arg_count
);
283 hstate
.add_int (cfg_checksum
);
284 hstate
.add_int (gcode_hash
);
286 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
287 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
289 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
290 hstate
.add_int (bb_sizes
[i
]);
293 /* Add common features of declaration itself. */
294 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
296 (cl_target_option_hash
297 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
298 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
299 (cl_optimization_hash
300 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
301 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
302 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
304 hash
= hstate
.end ();
310 /* Return ture if A1 and A2 represent equivalent function attribute lists.
311 Based on comp_type_attributes. */
314 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
319 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
321 const struct attribute_spec
*as
;
324 as
= lookup_attribute_spec (get_attribute_name (a
));
325 /* TODO: We can introduce as->affects_decl_identity
326 and as->affects_decl_reference_identity if attribute mismatch
327 gets a common reason to give up on merging. It may not be worth
329 For example returns_nonnull affects only references, while
330 optimize attribute can be ignored because it is already lowered
331 into flags representation and compared separately. */
335 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
336 if (!attr
|| !attribute_value_equal (a
, attr
))
341 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
343 const struct attribute_spec
*as
;
345 as
= lookup_attribute_spec (get_attribute_name (a
));
349 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
351 /* We don't need to compare trees again, as we did this
352 already in first loop. */
357 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
361 /* Compare properties of symbols N1 and N2 that does not affect semantics of
362 symbol itself but affects semantics of its references from USED_BY (which
363 may be NULL if it is unknown). If comparsion is false, symbols
364 can still be merged but any symbols referring them can't.
366 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
368 TODO: We can also split attributes to those that determine codegen of
369 a function body/variable constructor itself and those that are used when
373 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
378 if (is_a
<cgraph_node
*> (n1
))
380 /* Inline properties matters: we do now want to merge uses of inline
381 function to uses of normal function because inline hint would be lost.
382 We however can merge inline function to noinline because the alias
383 will keep its DECL_DECLARED_INLINE flag.
385 Also ignore inline flag when optimizing for size or when function
386 is known to not be inlinable.
388 TODO: the optimize_size checks can also be assumed to be true if
389 unit has no !optimize_size functions. */
391 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
392 || !opt_for_fn (used_by
->decl
, optimize_size
))
393 && !opt_for_fn (n1
->decl
, optimize_size
)
394 && n1
->get_availability () > AVAIL_INTERPOSABLE
395 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
397 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
398 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
399 return return_false_with_msg
400 ("DECL_DISREGARD_INLINE_LIMITS are different");
402 if (DECL_DECLARED_INLINE_P (n1
->decl
)
403 != DECL_DECLARED_INLINE_P (n2
->decl
))
404 return return_false_with_msg ("inline attributes are different");
407 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
408 != DECL_IS_OPERATOR_NEW (n2
->decl
))
409 return return_false_with_msg ("operator new flags are different");
412 /* Merging two definitions with a reference to equivalent vtables, but
413 belonging to a different type may result in ipa-polymorphic-call analysis
414 giving a wrong answer about the dynamic type of instance. */
415 if (is_a
<varpool_node
*> (n1
))
417 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
418 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
419 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
420 DECL_CONTEXT (n2
->decl
)))
421 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
422 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
423 return return_false_with_msg
424 ("references to virtual tables can not be merged");
426 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
427 return return_false_with_msg ("alignment mismatch");
429 /* For functions we compare attributes in equals_wpa, because we do
430 not know what attributes may cause codegen differences, but for
431 variables just compare attributes for references - the codegen
432 for constructors is affected only by those attributes that we lower
433 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
434 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
435 DECL_ATTRIBUTES (n2
->decl
)))
436 return return_false_with_msg ("different var decl attributes");
437 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
438 TREE_TYPE (n2
->decl
)) != 1)
439 return return_false_with_msg ("different var type attributes");
442 /* When matching virtual tables, be sure to also match information
443 relevant for polymorphic call analysis. */
444 if (used_by
&& is_a
<varpool_node
*> (used_by
)
445 && DECL_VIRTUAL_P (used_by
->decl
))
447 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
448 return return_false_with_msg ("virtual flag mismatch");
449 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
450 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
451 return return_false_with_msg ("final flag mismatch");
456 /* Hash properties that are compared by compare_referenced_symbol_properties. */
459 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
460 inchash::hash
&hstate
,
463 if (is_a
<cgraph_node
*> (ref
))
465 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
466 && !opt_for_fn (ref
->decl
, optimize_size
)
467 && !DECL_UNINLINABLE (ref
->decl
))
469 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
470 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
472 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
474 else if (is_a
<varpool_node
*> (ref
))
476 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
478 hstate
.add_int (DECL_ALIGN (ref
->decl
));
483 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
484 point to a same function. Comparison can be skipped if IGNORED_NODES
485 contains these nodes. ADDRESS indicate if address is taken. */
488 sem_item::compare_symbol_references (
489 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
490 symtab_node
*n1
, symtab_node
*n2
, bool address
)
492 enum availability avail1
, avail2
;
497 /* Never match variable and function. */
498 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
501 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
503 if (address
&& n1
->equal_address_to (n2
) == 1)
505 if (!address
&& n1
->semantically_equivalent_p (n2
))
508 n1
= n1
->ultimate_alias_target (&avail1
);
509 n2
= n2
->ultimate_alias_target (&avail2
);
511 if (avail1
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
512 && avail2
> AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
515 return return_false_with_msg ("different references");
518 /* If cgraph edges E1 and E2 are indirect calls, verify that
519 ECF flags are the same. */
521 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
523 if (e1
->indirect_info
&& e2
->indirect_info
)
525 int e1_flags
= e1
->indirect_info
->ecf_flags
;
526 int e2_flags
= e2
->indirect_info
->ecf_flags
;
528 if (e1_flags
!= e2_flags
)
529 return return_false_with_msg ("ICF flags are different");
531 else if (e1
->indirect_info
|| e2
->indirect_info
)
537 /* Return true if parameter I may be used. */
540 sem_function::param_used_p (unsigned int i
)
542 if (ipa_node_params_sum
== NULL
)
545 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
547 if (parms_info
->descriptors
.is_empty ()
548 || parms_info
->descriptors
.length () <= i
)
551 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
554 /* Perform additional check needed to match types function parameters that are
555 used. Unlike for normal decls it matters if type is TYPE_RESTRICT and we
556 make an assumption that REFERENCE_TYPE parameters are always non-NULL. */
559 sem_function::compatible_parm_types_p (tree parm1
, tree parm2
)
561 /* Be sure that parameters are TBAA compatible. */
562 if (!func_checker::compatible_types_p (parm1
, parm2
))
563 return return_false_with_msg ("parameter type is not compatible");
565 if (POINTER_TYPE_P (parm1
)
566 && (TYPE_RESTRICT (parm1
) != TYPE_RESTRICT (parm2
)))
567 return return_false_with_msg ("argument restrict flag mismatch");
569 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
570 if (POINTER_TYPE_P (parm1
)
571 && TREE_CODE (parm1
) != TREE_CODE (parm2
)
572 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
573 return return_false_with_msg ("pointer wrt reference mismatch");
578 /* Fast equality function based on knowledge known in WPA. */
581 sem_function::equals_wpa (sem_item
*item
,
582 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
584 gcc_assert (item
->type
== FUNC
);
585 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
586 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
588 m_compared_func
= static_cast<sem_function
*> (item
);
590 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
591 return return_false_with_msg ("thunk_p mismatch");
593 if (cnode
->thunk
.thunk_p
)
595 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
596 return return_false_with_msg ("thunk fixed_offset mismatch");
597 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
598 return return_false_with_msg ("thunk virtual_value mismatch");
599 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
600 return return_false_with_msg ("thunk this_adjusting mismatch");
601 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
602 return return_false_with_msg ("thunk virtual_offset_p mismatch");
603 if (cnode
->thunk
.add_pointer_bounds_args
604 != cnode2
->thunk
.add_pointer_bounds_args
)
605 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
608 /* Compare special function DECL attributes. */
609 if (DECL_FUNCTION_PERSONALITY (decl
)
610 != DECL_FUNCTION_PERSONALITY (item
->decl
))
611 return return_false_with_msg ("function personalities are different");
613 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
614 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
615 return return_false_with_msg ("intrument function entry exit "
616 "attributes are different");
618 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
619 return return_false_with_msg ("no stack limit attributes are different");
621 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
622 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
624 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
625 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
627 /* TODO: pure/const flags mostly matters only for references, except for
628 the fact that codegen takes LOOPING flag as a hint that loops are
629 finite. We may arrange the code to always pick leader that has least
630 specified flags and then this can go into comparing symbol properties. */
631 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
632 return return_false_with_msg ("decl_or_type flags are different");
634 /* Do not match polymorphic constructors of different types. They calls
635 type memory location for ipa-polymorphic-call and we do not want
636 it to get confused by wrong type. */
637 if (DECL_CXX_CONSTRUCTOR_P (decl
)
638 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
640 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
641 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
642 else if (!func_checker::compatible_polymorphic_types_p
643 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
644 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
645 return return_false_with_msg ("ctor polymorphic type mismatch");
648 /* Checking function TARGET and OPTIMIZATION flags. */
649 cl_target_option
*tar1
= target_opts_for_fn (decl
);
650 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
652 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
654 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
656 fprintf (dump_file
, "target flags difference");
657 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
660 return return_false_with_msg ("Target flags are different");
663 cl_optimization
*opt1
= opts_for_fn (decl
);
664 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
666 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
668 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
670 fprintf (dump_file
, "optimization flags difference");
671 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
674 return return_false_with_msg ("optimization flags are different");
677 /* Result type checking. */
678 if (!func_checker::compatible_types_p
679 (TREE_TYPE (TREE_TYPE (decl
)),
680 TREE_TYPE (TREE_TYPE (m_compared_func
->decl
))))
681 return return_false_with_msg ("result types are different");
683 /* Checking types of arguments. */
684 tree list1
= TYPE_ARG_TYPES (TREE_TYPE (decl
)),
685 list2
= TYPE_ARG_TYPES (TREE_TYPE (m_compared_func
->decl
));
686 for (unsigned i
= 0; list1
&& list2
;
687 list1
= TREE_CHAIN (list1
), list2
= TREE_CHAIN (list2
), i
++)
689 tree parm1
= TREE_VALUE (list1
);
690 tree parm2
= TREE_VALUE (list2
);
692 /* This guard is here for function pointer with attributes (pr59927.c). */
693 if (!parm1
|| !parm2
)
694 return return_false_with_msg ("NULL argument type");
696 /* Verify that types are compatible to ensure that both functions
697 have same calling conventions. */
698 if (!types_compatible_p (parm1
, parm2
))
699 return return_false_with_msg ("parameter types are not compatible");
701 if (!param_used_p (i
))
704 /* Perform additional checks for used parameters. */
705 if (!compatible_parm_types_p (parm1
, parm2
))
710 return return_false_with_msg ("Mismatched number of parameters");
712 if (node
->num_references () != item
->node
->num_references ())
713 return return_false_with_msg ("different number of references");
715 /* Checking function attributes.
716 This is quadratic in number of attributes */
717 if (comp_type_attributes (TREE_TYPE (decl
),
718 TREE_TYPE (item
->decl
)) != 1)
719 return return_false_with_msg ("different type attributes");
720 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
721 DECL_ATTRIBUTES (item
->decl
)))
722 return return_false_with_msg ("different decl attributes");
724 /* The type of THIS pointer type memory location for
725 ipa-polymorphic-call-analysis. */
726 if (opt_for_fn (decl
, flag_devirtualize
)
727 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
728 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
730 && compare_polymorphic_p ())
732 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
733 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
734 if (!func_checker::compatible_polymorphic_types_p
735 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
736 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
737 return return_false_with_msg ("THIS pointer ODR type mismatch");
740 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
741 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
743 item
->node
->iterate_reference (i
, ref2
);
745 if (ref
->use
!= ref2
->use
)
746 return return_false_with_msg ("reference use mismatch");
748 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
750 ref
->address_matters_p ()))
754 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
755 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
759 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
762 if (!compare_edge_flags (e1
, e2
))
765 e1
= e1
->next_callee
;
766 e2
= e2
->next_callee
;
770 return return_false_with_msg ("different number of calls");
772 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
773 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
777 if (!compare_edge_flags (e1
, e2
))
780 e1
= e1
->next_callee
;
781 e2
= e2
->next_callee
;
785 return return_false_with_msg ("different number of indirect calls");
790 /* Update hash by address sensitive references. We iterate over all
791 sensitive references (address_matters_p) and we hash ultime alias
792 target of these nodes, which can improve a semantic item hash.
794 Also hash in referenced symbols properties. This can be done at any time
795 (as the properties should not change), but it is convenient to do it here
796 while we walk the references anyway. */
799 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
800 sem_item
*> &m_symtab_node_map
)
803 inchash::hash
hstate (hash
);
805 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
807 hstate
.add_int (ref
->use
);
808 hash_referenced_symbol_properties (ref
->referred
, hstate
,
809 ref
->use
== IPA_REF_ADDR
);
810 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
811 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
814 if (is_a
<cgraph_node
*> (node
))
816 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
819 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
820 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
822 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
826 hash
= hstate
.end ();
829 /* Update hash by computed local hash values taken from different
831 TODO: stronger SCC based hashing would be desirable here. */
834 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
835 sem_item
*> &m_symtab_node_map
)
838 inchash::hash
state (hash
);
840 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
842 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
844 state
.merge_hash ((*result
)->hash
);
849 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
852 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
854 state
.merge_hash ((*result
)->hash
);
858 global_hash
= state
.end ();
861 /* Returns true if the item equals to ITEM given as argument. */
864 sem_function::equals (sem_item
*item
,
865 hash_map
<symtab_node
*, sem_item
*> &)
867 gcc_assert (item
->type
== FUNC
);
868 bool eq
= equals_private (item
);
870 if (m_checker
!= NULL
)
876 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
878 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
879 xstrdup_for_dump (node
->name()),
880 xstrdup_for_dump (item
->node
->name ()),
883 xstrdup_for_dump (node
->asm_name ()),
884 xstrdup_for_dump (item
->node
->asm_name ()),
885 eq
? "true" : "false");
890 /* Processes function equality comparison. */
893 sem_function::equals_private (sem_item
*item
)
895 if (item
->type
!= FUNC
)
898 basic_block bb1
, bb2
;
900 edge_iterator ei1
, ei2
;
904 m_compared_func
= static_cast<sem_function
*> (item
);
906 gcc_assert (decl
!= item
->decl
);
908 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
909 || edge_count
!= m_compared_func
->edge_count
910 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
911 return return_false ();
913 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
914 compare_polymorphic_p (),
917 &m_compared_func
->refs_set
);
918 arg1
= DECL_ARGUMENTS (decl
);
919 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
921 arg1
&& arg2
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
), i
++)
923 if (!types_compatible_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
924 return return_false_with_msg ("argument types are not compatible");
925 if (!param_used_p (i
))
927 /* Perform additional checks for used parameters. */
928 if (!compatible_parm_types_p (TREE_TYPE (arg1
), TREE_TYPE (arg2
)))
930 if (!m_checker
->compare_decl (arg1
, arg2
))
931 return return_false ();
934 return return_false_with_msg ("Mismatched number of arguments");
936 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
939 /* Fill-up label dictionary. */
940 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
942 m_checker
->parse_labels (bb_sorted
[i
]);
943 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
946 /* Checking all basic blocks. */
947 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
948 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
949 return return_false();
951 dump_message ("All BBs are equal\n");
953 auto_vec
<int> bb_dict
;
955 /* Basic block edges check. */
956 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
958 bb1
= bb_sorted
[i
]->bb
;
959 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
961 ei2
= ei_start (bb2
->preds
);
963 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
967 if (e1
->flags
!= e2
->flags
)
968 return return_false_with_msg ("flags comparison returns false");
970 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
971 return return_false_with_msg ("edge comparison returns false");
973 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
974 return return_false_with_msg ("BB comparison returns false");
976 if (!m_checker
->compare_edge (e1
, e2
))
977 return return_false_with_msg ("edge comparison returns false");
983 /* Basic block PHI nodes comparison. */
984 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
985 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
986 return return_false_with_msg ("PHI node comparison returns false");
991 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
992 Helper for call_for_symbol_thunks_and_aliases. */
995 set_local (cgraph_node
*node
, void *data
)
997 node
->local
.local
= data
!= NULL
;
1001 /* TREE_ADDRESSABLE of NODE to true.
1002 Helper for call_for_symbol_thunks_and_aliases. */
1005 set_addressable (varpool_node
*node
, void *)
1007 TREE_ADDRESSABLE (node
->decl
) = 1;
1011 /* Clear DECL_RTL of NODE.
1012 Helper for call_for_symbol_thunks_and_aliases. */
1015 clear_decl_rtl (symtab_node
*node
, void *)
1017 SET_DECL_RTL (node
->decl
, NULL
);
1021 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1022 possible. Return number of redirections made. */
1025 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1027 int nredirected
= 0;
1029 cgraph_edge
*e
= n
->callers
;
1033 /* Redirecting thunks to interposable symbols or symbols in other sections
1034 may not be supported by target output code. Play safe for now and
1035 punt on redirection. */
1036 if (!e
->caller
->thunk
.thunk_p
)
1038 struct cgraph_edge
*nexte
= e
->next_caller
;
1039 e
->redirect_callee (to
);
1046 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1048 bool removed
= false;
1049 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1051 if ((DECL_COMDAT_GROUP (n
->decl
)
1052 && (DECL_COMDAT_GROUP (n
->decl
)
1053 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1054 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1055 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1057 nredirected
+= redirect_all_callers (n_alias
, to
);
1058 if (n_alias
->can_remove_if_no_direct_calls_p ()
1059 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1061 && !n_alias
->has_aliases_p ())
1070 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1074 sem_function::merge (sem_item
*alias_item
)
1076 gcc_assert (alias_item
->type
== FUNC
);
1078 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1080 cgraph_node
*original
= get_node ();
1081 cgraph_node
*local_original
= NULL
;
1082 cgraph_node
*alias
= alias_func
->get_node ();
1084 bool create_wrapper
= false;
1085 bool create_alias
= false;
1086 bool redirect_callers
= false;
1087 bool remove
= false;
1089 bool original_discardable
= false;
1090 bool original_discarded
= false;
1092 bool original_address_matters
= original
->address_matters_p ();
1093 bool alias_address_matters
= alias
->address_matters_p ();
1095 if (DECL_EXTERNAL (alias
->decl
))
1098 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1102 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1103 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1108 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1112 /* Do not attempt to mix functions from different user sections;
1113 we do not know what user intends with those. */
1114 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1115 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1116 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1121 "original and alias are in different sections.\n\n");
1125 /* See if original is in a section that can be discarded if the main
1126 symbol is not used. */
1128 if (original
->can_be_discarded_p ())
1129 original_discardable
= true;
1130 /* Also consider case where we have resolution info and we know that
1131 original's definition is not going to be used. In this case we can not
1132 create alias to original. */
1133 if (node
->resolution
!= LDPR_UNKNOWN
1134 && !decl_binds_to_current_def_p (node
->decl
))
1135 original_discardable
= original_discarded
= true;
1137 /* Creating a symtab alias is the optimal way to merge.
1138 It however can not be used in the following cases:
1140 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1141 2) if ORIGINAL is in a section that may be discarded by linker or if
1142 it is an external functions where we can not create an alias
1143 (ORIGINAL_DISCARDABLE)
1144 3) if target do not support symbol aliases.
1145 4) original and alias lie in different comdat groups.
1147 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1148 and/or redirect all callers from ALIAS to ORIGINAL. */
1149 if ((original_address_matters
&& alias_address_matters
)
1150 || (original_discardable
1151 && (!DECL_COMDAT_GROUP (alias
->decl
)
1152 || (DECL_COMDAT_GROUP (alias
->decl
)
1153 != DECL_COMDAT_GROUP (original
->decl
))))
1154 || original_discarded
1155 || !sem_item::target_supports_symbol_aliases_p ()
1156 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1158 /* First see if we can produce wrapper. */
1160 /* Symbol properties that matter for references must be preserved.
1161 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1162 with proper properties. */
1163 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1164 alias
->address_taken
))
1168 "Wrapper cannot be created because referenced symbol "
1169 "properties mismatch\n");
1171 /* Do not turn function in one comdat group into wrapper to another
1172 comdat group. Other compiler producing the body of the
1173 another comdat group may make opossite decision and with unfortunate
1174 linker choices this may close a loop. */
1175 else if (DECL_COMDAT_GROUP (original
->decl
)
1176 && DECL_COMDAT_GROUP (alias
->decl
)
1177 && (DECL_COMDAT_GROUP (alias
->decl
)
1178 != DECL_COMDAT_GROUP (original
->decl
)))
1182 "Wrapper cannot be created because of COMDAT\n");
1184 else if (DECL_STATIC_CHAIN (alias
->decl
))
1188 "Can not create wrapper of nested functions.\n");
1190 /* TODO: We can also deal with variadic functions never calling
1192 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1196 "can not create wrapper of stdarg function.\n");
1198 else if (inline_summaries
1199 && inline_summaries
->get (alias
)->self_size
<= 2)
1202 fprintf (dump_file
, "Wrapper creation is not "
1203 "profitable (function is too small).\n");
1205 /* If user paid attention to mark function noinline, assume it is
1206 somewhat special and do not try to turn it into a wrapper that can
1207 not be undone by inliner. */
1208 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1211 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1214 create_wrapper
= true;
1216 /* We can redirect local calls in the case both alias and orignal
1217 are not interposable. */
1219 = alias
->get_availability () > AVAIL_INTERPOSABLE
1220 && original
->get_availability () > AVAIL_INTERPOSABLE
1221 && !alias
->instrumented_version
;
1222 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1223 with proper properties. */
1224 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1225 alias
->address_taken
))
1226 redirect_callers
= false;
1228 if (!redirect_callers
&& !create_wrapper
)
1231 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1232 "produce wrapper\n\n");
1236 /* Work out the symbol the wrapper should call.
1237 If ORIGINAL is interposable, we need to call a local alias.
1238 Also produce local alias (if possible) as an optimization.
1240 Local aliases can not be created inside comdat groups because that
1241 prevents inlining. */
1242 if (!original_discardable
&& !original
->get_comdat_group ())
1245 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1247 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1248 local_original
= original
;
1250 /* If we can not use local alias, fallback to the original
1252 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1253 local_original
= original
;
1255 /* If original is COMDAT local, we can not really redirect calls outside
1256 of its comdat group to it. */
1257 if (original
->comdat_local_p ())
1258 redirect_callers
= false;
1259 if (!local_original
)
1262 fprintf (dump_file
, "Not unifying; "
1263 "can not produce local alias.\n\n");
1267 if (!redirect_callers
&& !create_wrapper
)
1270 fprintf (dump_file
, "Not unifying; "
1271 "can not redirect callers nor produce a wrapper\n\n");
1275 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1277 && !alias
->can_remove_if_no_direct_calls_p ())
1280 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1281 "function has other uses than direct calls\n\n");
1286 create_alias
= true;
1288 if (redirect_callers
)
1290 int nredirected
= redirect_all_callers (alias
, local_original
);
1294 alias
->icf_merged
= true;
1295 local_original
->icf_merged
= true;
1297 if (dump_file
&& nredirected
)
1298 fprintf (dump_file
, "%i local calls have been "
1299 "redirected.\n", nredirected
);
1302 /* If all callers was redirected, do not produce wrapper. */
1303 if (alias
->can_remove_if_no_direct_calls_p ()
1304 && !alias
->has_aliases_p ())
1306 create_wrapper
= false;
1309 gcc_assert (!create_alias
);
1311 else if (create_alias
)
1313 alias
->icf_merged
= true;
1315 /* Remove the function's body. */
1316 ipa_merge_profiles (original
, alias
);
1317 alias
->release_body (true);
1319 /* Notice global symbol possibly produced RTL. */
1320 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1323 /* Create the alias. */
1324 cgraph_node::create_alias (alias_func
->decl
, decl
);
1325 alias
->resolve_alias (original
);
1327 original
->call_for_symbol_thunks_and_aliases
1328 (set_local
, (void *)(size_t) original
->local_p (), true);
1331 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1335 gcc_assert (!create_alias
);
1336 alias
->icf_merged
= true;
1337 local_original
->icf_merged
= true;
1339 ipa_merge_profiles (local_original
, alias
, true);
1340 alias
->create_wrapper (local_original
);
1343 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1346 /* It's possible that redirection can hit thunks that block
1347 redirection opportunities. */
1348 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1349 original
->icf_merged
= true;
1351 /* Inform the inliner about cross-module merging. */
1352 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1353 && original
->lto_file_data
!= alias
->lto_file_data
)
1354 local_original
->merged
= original
->merged
= true;
1358 ipa_merge_profiles (original
, alias
);
1359 alias
->release_body ();
1361 alias
->body_removed
= true;
1362 alias
->icf_merged
= true;
1364 fprintf (dump_file
, "Unified; Function body was removed.\n");
1370 /* Semantic item initialization function. */
1373 sem_function::init (void)
1376 get_node ()->get_untransformed_body ();
1378 tree fndecl
= node
->decl
;
1379 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1382 gcc_assert (SSANAMES (func
));
1384 ssa_names_size
= SSANAMES (func
)->length ();
1388 region_tree
= func
->eh
->region_tree
;
1390 /* iterating all function arguments. */
1391 arg_count
= count_formal_params (fndecl
);
1393 edge_count
= n_edges_for_fn (func
);
1394 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1395 if (!cnode
->thunk
.thunk_p
)
1397 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1399 inchash::hash hstate
;
1402 FOR_EACH_BB_FN (bb
, func
)
1404 unsigned nondbg_stmt_count
= 0;
1407 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1409 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1412 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1415 gimple
*stmt
= gsi_stmt (gsi
);
1417 if (gimple_code (stmt
) != GIMPLE_DEBUG
1418 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1420 hash_stmt (stmt
, hstate
);
1421 nondbg_stmt_count
++;
1425 gcode_hash
= hstate
.end ();
1426 bb_sizes
.safe_push (nondbg_stmt_count
);
1428 /* Inserting basic block to hash table. */
1429 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1430 EDGE_COUNT (bb
->preds
)
1431 + EDGE_COUNT (bb
->succs
));
1433 bb_sorted
.safe_push (semantic_bb
);
1439 inchash::hash hstate
;
1440 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1441 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1442 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1443 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1444 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1445 gcode_hash
= hstate
.end ();
1449 /* Accumulate to HSTATE a hash of expression EXP.
1450 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1451 and DECL equality classes. */
1454 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1456 if (exp
== NULL_TREE
)
1458 hstate
.merge_hash (0);
1462 /* Handled component can be matched in a cureful way proving equivalence
1463 even if they syntactically differ. Just skip them. */
1465 while (handled_component_p (exp
))
1466 exp
= TREE_OPERAND (exp
, 0);
1468 enum tree_code code
= TREE_CODE (exp
);
1469 hstate
.add_int (code
);
1473 /* Use inchash::add_expr for everything that is LTO stable. */
1481 inchash::add_expr (exp
, hstate
);
1485 unsigned HOST_WIDE_INT idx
;
1488 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1490 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1492 add_expr (value
, hstate
);
1497 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1503 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1506 case POINTER_PLUS_EXPR
:
1509 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1510 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1514 inchash::hash one
, two
;
1515 add_expr (TREE_OPERAND (exp
, 0), one
);
1516 add_expr (TREE_OPERAND (exp
, 1), two
);
1517 hstate
.add_commutative (one
, two
);
1521 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1522 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1528 /* Accumulate to HSTATE a hash of type t.
1529 TYpes that may end up being compatible after LTO type merging needs to have
1533 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1535 if (type
== NULL_TREE
)
1537 hstate
.merge_hash (0);
1541 type
= TYPE_MAIN_VARIANT (type
);
1542 if (TYPE_CANONICAL (type
))
1543 type
= TYPE_CANONICAL (type
);
1545 if (!AGGREGATE_TYPE_P (type
))
1546 hstate
.add_int (TYPE_MODE (type
));
1548 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1550 hstate
.add_int (COMPLEX_TYPE
);
1551 sem_item::add_type (TREE_TYPE (type
), hstate
);
1553 else if (INTEGRAL_TYPE_P (type
))
1555 hstate
.add_int (INTEGER_TYPE
);
1556 hstate
.add_flag (TYPE_UNSIGNED (type
));
1557 hstate
.add_int (TYPE_PRECISION (type
));
1559 else if (VECTOR_TYPE_P (type
))
1561 hstate
.add_int (VECTOR_TYPE
);
1562 hstate
.add_int (TYPE_PRECISION (type
));
1563 sem_item::add_type (TREE_TYPE (type
), hstate
);
1565 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1567 hstate
.add_int (ARRAY_TYPE
);
1568 /* Do not hash size, so complete and incomplete types can match. */
1569 sem_item::add_type (TREE_TYPE (type
), hstate
);
1571 else if (RECORD_OR_UNION_TYPE_P (type
))
1573 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1577 inchash::hash hstate2
;
1582 hstate2
.add_int (RECORD_TYPE
);
1583 gcc_assert (COMPLETE_TYPE_P (type
));
1585 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1586 if (TREE_CODE (f
) == FIELD_DECL
)
1588 add_type (TREE_TYPE (f
), hstate2
);
1592 hstate2
.add_int (nf
);
1593 hash
= hstate2
.end ();
1594 hstate
.add_wide_int (hash
);
1595 optimizer
->m_type_hash_cache
.put (type
, hash
);
1598 hstate
.add_wide_int (*val
);
1602 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1605 sem_function::hash_stmt (gimple
*stmt
, inchash::hash
&hstate
)
1607 enum gimple_code code
= gimple_code (stmt
);
1609 hstate
.add_int (code
);
1614 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1617 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1618 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1619 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1621 inchash::hash one
, two
;
1623 add_expr (gimple_assign_rhs1 (stmt
), one
);
1624 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1625 add_expr (gimple_assign_rhs2 (stmt
), two
);
1626 hstate
.add_commutative (one
, two
);
1627 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1629 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1630 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1632 add_expr (gimple_assign_lhs (stmt
), hstate
);
1633 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1636 /* ... fall through ... */
1642 /* All these statements are equivalent if their operands are. */
1643 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1645 add_expr (gimple_op (stmt
, i
), hstate
);
1646 if (gimple_op (stmt
, i
))
1647 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1655 /* Return true if polymorphic comparison must be processed. */
1658 sem_function::compare_polymorphic_p (void)
1660 struct cgraph_edge
*e
;
1662 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1664 if (get_node ()->indirect_calls
!= NULL
)
1666 /* TODO: We can do simple propagation determining what calls may lead to
1667 a polymorphic call. */
1668 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1669 if (e
->callee
->definition
1670 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1675 /* For a given call graph NODE, the function constructs new
1676 semantic function item. */
1679 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1681 tree fndecl
= node
->decl
;
1682 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1684 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1687 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1690 sem_function
*f
= new sem_function (node
, 0, stack
);
1697 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1698 return true if phi nodes are semantically equivalent in these blocks . */
1701 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1703 gphi_iterator si1
, si2
;
1705 unsigned size1
, size2
, i
;
1709 gcc_assert (bb1
!= NULL
);
1710 gcc_assert (bb2
!= NULL
);
1712 si2
= gsi_start_phis (bb2
);
1713 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1716 gsi_next_nonvirtual_phi (&si1
);
1717 gsi_next_nonvirtual_phi (&si2
);
1719 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1722 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1723 return return_false();
1728 tree phi_result1
= gimple_phi_result (phi1
);
1729 tree phi_result2
= gimple_phi_result (phi2
);
1731 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1732 return return_false_with_msg ("PHI results are different");
1734 size1
= gimple_phi_num_args (phi1
);
1735 size2
= gimple_phi_num_args (phi2
);
1738 return return_false ();
1740 for (i
= 0; i
< size1
; ++i
)
1742 t1
= gimple_phi_arg (phi1
, i
)->def
;
1743 t2
= gimple_phi_arg (phi2
, i
)->def
;
1745 if (!m_checker
->compare_operand (t1
, t2
))
1746 return return_false ();
1748 e1
= gimple_phi_arg_edge (phi1
, i
);
1749 e2
= gimple_phi_arg_edge (phi2
, i
);
1751 if (!m_checker
->compare_edge (e1
, e2
))
1752 return return_false ();
1761 /* Returns true if tree T can be compared as a handled component. */
1764 sem_function::icf_handled_component_p (tree t
)
1766 tree_code tc
= TREE_CODE (t
);
1768 return (handled_component_p (t
)
1769 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1772 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1773 corresponds to TARGET. */
1776 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1781 if (bb_dict
->length () <= (unsigned)source
)
1782 bb_dict
->safe_grow_cleared (source
+ 1);
1784 if ((*bb_dict
)[source
] == 0)
1786 (*bb_dict
)[source
] = target
;
1790 return (*bb_dict
)[source
] == target
;
1794 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1796 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1800 /* Constructor based on varpool node _NODE with computed hash _HASH.
1801 Bitmap STACK is used for memory allocation. */
1803 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1804 bitmap_obstack
*stack
): sem_item(VAR
,
1807 gcc_checking_assert (node
);
1808 gcc_checking_assert (get_node ());
1811 /* Fast equality function based on knowledge known in WPA. */
1814 sem_variable::equals_wpa (sem_item
*item
,
1815 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1817 gcc_assert (item
->type
== VAR
);
1819 if (node
->num_references () != item
->node
->num_references ())
1820 return return_false_with_msg ("different number of references");
1822 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1823 return return_false_with_msg ("TLS model");
1825 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1826 alignment out of all aliases. */
1828 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1829 return return_false_with_msg ("Virtual flag mismatch");
1831 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1832 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1833 || !operand_equal_p (DECL_SIZE (decl
),
1834 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1835 return return_false_with_msg ("size mismatch");
1837 /* Do not attempt to mix data from different user sections;
1838 we do not know what user intends with those. */
1839 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1840 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1841 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1842 return return_false_with_msg ("user section mismatch");
1844 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1845 return return_false_with_msg ("text section");
1847 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1848 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1850 item
->node
->iterate_reference (i
, ref2
);
1852 if (ref
->use
!= ref2
->use
)
1853 return return_false_with_msg ("reference use mismatch");
1855 if (!compare_symbol_references (ignored_nodes
,
1856 ref
->referred
, ref2
->referred
,
1857 ref
->address_matters_p ()))
1864 /* Returns true if the item equals to ITEM given as argument. */
1867 sem_variable::equals (sem_item
*item
,
1868 hash_map
<symtab_node
*, sem_item
*> &)
1870 gcc_assert (item
->type
== VAR
);
1873 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1874 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1875 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1876 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1878 /* As seen in PR ipa/65303 we have to compare variables types. */
1879 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1880 TREE_TYPE (item
->decl
)))
1881 return return_false_with_msg ("variables types are different");
1883 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1884 DECL_INITIAL (item
->node
->decl
));
1885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1887 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1888 xstrdup_for_dump (node
->name()),
1889 xstrdup_for_dump (item
->node
->name ()),
1890 node
->order
, item
->node
->order
,
1891 xstrdup_for_dump (node
->asm_name ()),
1892 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1897 /* Compares trees T1 and T2 for semantic equality. */
1900 sem_variable::equals (tree t1
, tree t2
)
1903 return return_with_debug (t1
== t2
);
1906 tree_code tc1
= TREE_CODE (t1
);
1907 tree_code tc2
= TREE_CODE (t2
);
1910 return return_false_with_msg ("TREE_CODE mismatch");
1916 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1917 unsigned HOST_WIDE_INT idx
;
1919 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1920 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1921 return return_false_with_msg ("constructor type mismatch");
1923 if (typecode
== ARRAY_TYPE
)
1925 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1926 /* For arrays, check that the sizes all match. */
1927 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1929 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1930 return return_false_with_msg ("constructor array size mismatch");
1932 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1934 return return_false_with_msg ("constructor type incompatible");
1936 v1
= CONSTRUCTOR_ELTS (t1
);
1937 v2
= CONSTRUCTOR_ELTS (t2
);
1938 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1939 return return_false_with_msg ("constructor number of elts mismatch");
1941 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1943 constructor_elt
*c1
= &(*v1
)[idx
];
1944 constructor_elt
*c2
= &(*v2
)[idx
];
1946 /* Check that each value is the same... */
1947 if (!sem_variable::equals (c1
->value
, c2
->value
))
1949 /* ... and that they apply to the same fields! */
1950 if (!sem_variable::equals (c1
->index
, c2
->index
))
1957 tree x1
= TREE_OPERAND (t1
, 0);
1958 tree x2
= TREE_OPERAND (t2
, 0);
1959 tree y1
= TREE_OPERAND (t1
, 1);
1960 tree y2
= TREE_OPERAND (t2
, 1);
1962 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1963 return return_false ();
1965 /* Type of the offset on MEM_REF does not matter. */
1966 return return_with_debug (sem_variable::equals (x1
, x2
)
1967 && wi::to_offset (y1
)
1968 == wi::to_offset (y2
));
1973 tree op1
= TREE_OPERAND (t1
, 0);
1974 tree op2
= TREE_OPERAND (t2
, 0);
1975 return sem_variable::equals (op1
, op2
);
1977 /* References to other vars/decls are compared using ipa-ref. */
1980 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1982 return return_false_with_msg ("Declaration mismatch");
1984 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1985 need to process its VAR/FUNCTION references without relying on ipa-ref
1989 return return_false_with_msg ("Declaration mismatch");
1991 /* Integer constants are the same only if the same width of type. */
1992 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1993 return return_false_with_msg ("INTEGER_CST precision mismatch");
1994 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1995 return return_false_with_msg ("INTEGER_CST mode mismatch");
1996 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1998 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1999 return return_false_with_msg ("STRING_CST mode mismatch");
2000 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2001 return return_false_with_msg ("STRING_CST length mismatch");
2002 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2003 TREE_STRING_LENGTH (t1
)))
2004 return return_false_with_msg ("STRING_CST mismatch");
2007 /* Fixed constants are the same only if the same width of type. */
2008 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2009 return return_false_with_msg ("FIXED_CST precision mismatch");
2011 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2012 TREE_FIXED_CST (t2
)));
2014 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2015 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2017 /* Real constants are the same only if the same width of type. */
2018 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2019 return return_false_with_msg ("REAL_CST precision mismatch");
2020 return return_with_debug (real_identical (&TREE_REAL_CST (t1
),
2021 &TREE_REAL_CST (t2
)));
2026 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2027 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2029 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2030 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2031 VECTOR_CST_ELT (t2
, i
)))
2037 case ARRAY_RANGE_REF
:
2039 tree x1
= TREE_OPERAND (t1
, 0);
2040 tree x2
= TREE_OPERAND (t2
, 0);
2041 tree y1
= TREE_OPERAND (t1
, 1);
2042 tree y2
= TREE_OPERAND (t2
, 1);
2044 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2046 if (!sem_variable::equals (array_ref_low_bound (t1
),
2047 array_ref_low_bound (t2
)))
2049 if (!sem_variable::equals (array_ref_element_size (t1
),
2050 array_ref_element_size (t2
)))
2056 case POINTER_PLUS_EXPR
:
2061 tree x1
= TREE_OPERAND (t1
, 0);
2062 tree x2
= TREE_OPERAND (t2
, 0);
2063 tree y1
= TREE_OPERAND (t1
, 1);
2064 tree y2
= TREE_OPERAND (t2
, 1);
2066 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2070 case VIEW_CONVERT_EXPR
:
2071 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2072 return return_false ();
2073 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2075 return return_false_with_msg ("ERROR_MARK");
2077 return return_false_with_msg ("Unknown TREE code reached");
2081 /* Parser function that visits a varpool NODE. */
2084 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2086 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2090 sem_variable
*v
= new sem_variable (node
, 0, stack
);
2097 /* References independent hash function. */
2100 sem_variable::get_hash (void)
2105 /* All WPA streamed in symbols should have their hashes computed at compile
2106 time. At this point, the constructor may not be in memory at all.
2107 DECL_INITIAL (decl) would be error_mark_node in that case. */
2108 gcc_assert (!node
->lto_file_data
);
2109 tree ctor
= DECL_INITIAL (decl
);
2110 inchash::hash hstate
;
2112 hstate
.add_int (456346417);
2113 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2114 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2115 add_expr (ctor
, hstate
);
2116 hash
= hstate
.end ();
2121 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2125 sem_variable::merge (sem_item
*alias_item
)
2127 gcc_assert (alias_item
->type
== VAR
);
2129 if (!sem_item::target_supports_symbol_aliases_p ())
2132 fprintf (dump_file
, "Not unifying; "
2133 "Symbol aliases are not supported by target\n\n");
2137 if (DECL_EXTERNAL (alias_item
->decl
))
2140 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2144 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2146 varpool_node
*original
= get_node ();
2147 varpool_node
*alias
= alias_var
->get_node ();
2148 bool original_discardable
= false;
2150 bool original_address_matters
= original
->address_matters_p ();
2151 bool alias_address_matters
= alias
->address_matters_p ();
2153 /* See if original is in a section that can be discarded if the main
2155 Also consider case where we have resolution info and we know that
2156 original's definition is not going to be used. In this case we can not
2157 create alias to original. */
2158 if (original
->can_be_discarded_p ()
2159 || (node
->resolution
!= LDPR_UNKNOWN
2160 && !decl_binds_to_current_def_p (node
->decl
)))
2161 original_discardable
= true;
2163 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2165 /* Constant pool machinery is not quite ready for aliases.
2166 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2167 For LTO merging does not happen that is an important missing feature.
2168 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2169 flag is dropped and non-local symbol name is assigned. */
2170 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2171 || DECL_IN_CONSTANT_POOL (original
->decl
))
2175 "Not unifying; constant pool variables.\n\n");
2179 /* Do not attempt to mix functions from different user sections;
2180 we do not know what user intends with those. */
2181 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2182 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2183 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2188 "original and alias are in different sections.\n\n");
2192 /* We can not merge if address comparsion metters. */
2193 if (original_address_matters
&& alias_address_matters
2194 && flag_merge_constants
< 2)
2199 "adress of original and alias may be compared.\n\n");
2202 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2205 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2206 "across comdat group boundary\n\n");
2211 if (original_discardable
)
2214 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2215 "target is discardable\n\n");
2221 gcc_assert (!original
->alias
);
2222 gcc_assert (!alias
->alias
);
2224 alias
->analyzed
= false;
2226 DECL_INITIAL (alias
->decl
) = NULL
;
2227 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2229 alias
->need_bounds_init
= false;
2230 alias
->remove_all_references ();
2231 if (TREE_ADDRESSABLE (alias
->decl
))
2232 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2234 varpool_node::create_alias (alias_var
->decl
, decl
);
2235 alias
->resolve_alias (original
);
2238 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
2244 /* Dump symbol to FILE. */
2247 sem_variable::dump_to_file (FILE *file
)
2251 print_node (file
, "", decl
, 0);
2252 fprintf (file
, "\n\n");
2255 unsigned int sem_item_optimizer::class_id
= 0;
2257 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2258 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2261 bitmap_obstack_initialize (&m_bmstack
);
2264 sem_item_optimizer::~sem_item_optimizer ()
2266 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2269 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2270 it
!= m_classes
.end (); ++it
)
2272 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2273 delete (*it
)->classes
[i
];
2275 (*it
)->classes
.release ();
2281 bitmap_obstack_release (&m_bmstack
);
2284 /* Write IPA ICF summary for symbols. */
2287 sem_item_optimizer::write_summary (void)
2289 unsigned int count
= 0;
2291 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2292 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2295 /* Calculate number of symbols to be serialized. */
2296 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2298 lsei_next_in_partition (&lsei
))
2300 symtab_node
*node
= lsei_node (lsei
);
2302 if (m_symtab_node_map
.get (node
))
2306 streamer_write_uhwi (ob
, count
);
2308 /* Process all of the symbols. */
2309 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2311 lsei_next_in_partition (&lsei
))
2313 symtab_node
*node
= lsei_node (lsei
);
2315 sem_item
**item
= m_symtab_node_map
.get (node
);
2319 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2320 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2322 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2326 streamer_write_char_stream (ob
->main_stream
, 0);
2327 produce_asm (ob
, NULL
);
2328 destroy_output_block (ob
);
2331 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2332 contains LEN bytes. */
2335 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2336 const char *data
, size_t len
)
2338 const lto_function_header
*header
=
2339 (const lto_function_header
*) data
;
2340 const int cfg_offset
= sizeof (lto_function_header
);
2341 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2342 const int string_offset
= main_offset
+ header
->main_size
;
2347 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2348 header
->main_size
, file_data
->mode_table
);
2351 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2352 header
->string_size
, vNULL
);
2354 count
= streamer_read_uhwi (&ib_main
);
2356 for (i
= 0; i
< count
; i
++)
2360 lto_symtab_encoder_t encoder
;
2362 index
= streamer_read_uhwi (&ib_main
);
2363 encoder
= file_data
->symtab_node_encoder
;
2364 node
= lto_symtab_encoder_deref (encoder
, index
);
2366 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2368 gcc_assert (node
->definition
);
2371 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2372 node
->asm_name (), (void *) node
->decl
, node
->order
);
2374 if (is_a
<cgraph_node
*> (node
))
2376 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2378 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2382 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2384 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2388 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2390 lto_data_in_delete (data_in
);
2393 /* Read IPA ICF summary for symbols. */
2396 sem_item_optimizer::read_summary (void)
2398 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2399 lto_file_decl_data
*file_data
;
2402 while ((file_data
= file_data_vec
[j
++]))
2405 const char *data
= lto_get_section_data (file_data
,
2406 LTO_section_ipa_icf
, NULL
, &len
);
2409 read_section (file_data
, data
, len
);
2413 /* Register callgraph and varpool hooks. */
2416 sem_item_optimizer::register_hooks (void)
2418 if (!m_cgraph_node_hooks
)
2419 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2420 (&sem_item_optimizer::cgraph_removal_hook
, this);
2422 if (!m_varpool_node_hooks
)
2423 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2424 (&sem_item_optimizer::varpool_removal_hook
, this);
2427 /* Unregister callgraph and varpool hooks. */
2430 sem_item_optimizer::unregister_hooks (void)
2432 if (m_cgraph_node_hooks
)
2433 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2435 if (m_varpool_node_hooks
)
2436 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2439 /* Adds a CLS to hashtable associated by hash value. */
2442 sem_item_optimizer::add_class (congruence_class
*cls
)
2444 gcc_assert (cls
->members
.length ());
2446 congruence_class_group
*group
= get_group_by_hash (
2447 cls
->members
[0]->get_hash (),
2448 cls
->members
[0]->type
);
2449 group
->classes
.safe_push (cls
);
2452 /* Gets a congruence class group based on given HASH value and TYPE. */
2454 congruence_class_group
*
2455 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2457 congruence_class_group
*item
= XNEW (congruence_class_group
);
2461 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2467 item
->classes
.create (1);
2474 /* Callgraph removal hook called for a NODE with a custom DATA. */
2477 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2479 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2480 optimizer
->remove_symtab_node (node
);
2483 /* Varpool removal hook called for a NODE with a custom DATA. */
2486 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2488 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2489 optimizer
->remove_symtab_node (node
);
2492 /* Remove symtab NODE triggered by symtab removal hooks. */
2495 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2497 gcc_assert (!m_classes
.elements());
2499 m_removed_items_set
.add (node
);
2503 sem_item_optimizer::remove_item (sem_item
*item
)
2505 if (m_symtab_node_map
.get (item
->node
))
2506 m_symtab_node_map
.remove (item
->node
);
2510 /* Removes all callgraph and varpool nodes that are marked by symtab
2514 sem_item_optimizer::filter_removed_items (void)
2516 auto_vec
<sem_item
*> filtered
;
2518 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2520 sem_item
*item
= m_items
[i
];
2522 if (m_removed_items_set
.contains (item
->node
))
2528 if (item
->type
== FUNC
)
2530 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2532 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2535 filtered
.safe_push (item
);
2539 if (!flag_ipa_icf_variables
)
2543 /* Filter out non-readonly variables. */
2544 tree decl
= item
->decl
;
2545 if (TREE_READONLY (decl
))
2546 filtered
.safe_push (item
);
2553 /* Clean-up of released semantic items. */
2556 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2557 m_items
.safe_push (filtered
[i
]);
2560 /* Optimizer entry point which returns true in case it processes
2561 a merge operation. True is returned if there's a merge operation
2565 sem_item_optimizer::execute (void)
2567 filter_removed_items ();
2568 unregister_hooks ();
2571 update_hash_by_addr_refs ();
2572 build_hash_based_classes ();
2575 fprintf (dump_file
, "Dump after hash based groups\n");
2576 dump_cong_classes ();
2578 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2579 m_items
[i
]->init_wpa ();
2581 subdivide_classes_by_equality (true);
2584 fprintf (dump_file
, "Dump after WPA based types groups\n");
2586 dump_cong_classes ();
2588 process_cong_reduction ();
2589 checking_verify_classes ();
2592 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2594 dump_cong_classes ();
2596 parse_nonsingleton_classes ();
2597 subdivide_classes_by_equality ();
2600 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2602 dump_cong_classes ();
2604 unsigned int prev_class_count
= m_classes_count
;
2606 process_cong_reduction ();
2607 dump_cong_classes ();
2608 checking_verify_classes ();
2609 bool merged_p
= merge_classes (prev_class_count
);
2611 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2612 symtab_node::dump_table (dump_file
);
2617 /* Function responsible for visiting all potential functions and
2618 read-only variables that can be merged. */
2621 sem_item_optimizer::parse_funcs_and_vars (void)
2625 if (flag_ipa_icf_functions
)
2626 FOR_EACH_DEFINED_FUNCTION (cnode
)
2628 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2631 m_items
.safe_push (f
);
2632 m_symtab_node_map
.put (cnode
, f
);
2635 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2637 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2638 f
->dump_to_file (dump_file
);
2641 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2644 varpool_node
*vnode
;
2646 if (flag_ipa_icf_variables
)
2647 FOR_EACH_DEFINED_VARIABLE (vnode
)
2649 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2653 m_items
.safe_push (v
);
2654 m_symtab_node_map
.put (vnode
, v
);
2659 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2662 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2664 item
->index_in_class
= cls
->members
.length ();
2665 cls
->members
.safe_push (item
);
2669 /* For each semantic item, append hash values of references. */
2672 sem_item_optimizer::update_hash_by_addr_refs ()
2674 /* First, append to hash sensitive references and class type if it need to
2675 be matched for ODR. */
2676 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2678 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2679 if (m_items
[i
]->type
== FUNC
)
2681 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2682 && contains_polymorphic_type_p
2683 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2684 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2685 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2686 && static_cast<sem_function
*> (m_items
[i
])
2687 ->compare_polymorphic_p ())))
2690 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2691 inchash::hash
hstate (m_items
[i
]->hash
);
2693 if (TYPE_NAME (class_type
)
2694 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2696 (IDENTIFIER_HASH_VALUE
2697 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2699 m_items
[i
]->hash
= hstate
.end ();
2704 /* Once all symbols have enhanced hash value, we can append
2705 hash values of symbols that are seen by IPA ICF and are
2706 references by a semantic item. Newly computed values
2707 are saved to global_hash member variable. */
2708 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2709 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2711 /* Global hash value replace current hash values. */
2712 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2713 m_items
[i
]->hash
= m_items
[i
]->global_hash
;
2716 /* Congruence classes are built by hash value. */
2719 sem_item_optimizer::build_hash_based_classes (void)
2721 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2723 sem_item
*item
= m_items
[i
];
2725 congruence_class_group
*group
= get_group_by_hash (item
->hash
,
2728 if (!group
->classes
.length ())
2731 group
->classes
.safe_push (new congruence_class (class_id
++));
2734 add_item_to_class (group
->classes
[0], item
);
2738 /* Build references according to call graph. */
2741 sem_item_optimizer::build_graph (void)
2743 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2745 sem_item
*item
= m_items
[i
];
2746 m_symtab_node_map
.put (item
->node
, item
);
2749 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2751 sem_item
*item
= m_items
[i
];
2753 if (item
->type
== FUNC
)
2755 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2757 cgraph_edge
*e
= cnode
->callees
;
2760 sem_item
**slot
= m_symtab_node_map
.get
2761 (e
->callee
->ultimate_alias_target ());
2763 item
->add_reference (*slot
);
2769 ipa_ref
*ref
= NULL
;
2770 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2772 sem_item
**slot
= m_symtab_node_map
.get
2773 (ref
->referred
->ultimate_alias_target ());
2775 item
->add_reference (*slot
);
2780 /* Semantic items in classes having more than one element and initialized.
2781 In case of WPA, we load function body. */
2784 sem_item_optimizer::parse_nonsingleton_classes (void)
2786 unsigned int init_called_count
= 0;
2788 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2789 if (m_items
[i
]->cls
->members
.length () > 1)
2791 m_items
[i
]->init ();
2792 init_called_count
++;
2796 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2797 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2800 /* Equality function for semantic items is used to subdivide existing
2801 classes. If IN_WPA, fast equality function is invoked. */
2804 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2806 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2807 it
!= m_classes
.end (); ++it
)
2809 unsigned int class_count
= (*it
)->classes
.length ();
2811 for (unsigned i
= 0; i
< class_count
; i
++)
2813 congruence_class
*c
= (*it
)->classes
[i
];
2815 if (c
->members
.length() > 1)
2817 auto_vec
<sem_item
*> new_vector
;
2819 sem_item
*first
= c
->members
[0];
2820 new_vector
.safe_push (first
);
2822 unsigned class_split_first
= (*it
)->classes
.length ();
2824 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2826 sem_item
*item
= c
->members
[j
];
2828 bool equals
= in_wpa
? first
->equals_wpa (item
,
2829 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2832 new_vector
.safe_push (item
);
2835 bool integrated
= false;
2837 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2839 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2840 bool equals
= in_wpa
? x
->equals_wpa (item
,
2841 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2846 add_item_to_class ((*it
)->classes
[k
], item
);
2854 congruence_class
*c
= new congruence_class (class_id
++);
2856 add_item_to_class (c
, item
);
2858 (*it
)->classes
.safe_push (c
);
2863 // we replace newly created new_vector for the class we've just splitted
2864 c
->members
.release ();
2865 c
->members
.create (new_vector
.length ());
2867 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2868 add_item_to_class (c
, new_vector
[j
]);
2873 checking_verify_classes ();
2876 /* Subdivide classes by address references that members of the class
2877 reference. Example can be a pair of functions that have an address
2878 taken from a function. If these addresses are different the class
2882 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2884 typedef hash_map
<symbol_compare_hash
, vec
<sem_item
*> > subdivide_hash_map
;
2886 unsigned newly_created_classes
= 0;
2888 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2889 it
!= m_classes
.end (); ++it
)
2891 unsigned int class_count
= (*it
)->classes
.length ();
2892 auto_vec
<congruence_class
*> new_classes
;
2894 for (unsigned i
= 0; i
< class_count
; i
++)
2896 congruence_class
*c
= (*it
)->classes
[i
];
2898 if (c
->members
.length() > 1)
2900 subdivide_hash_map split_map
;
2902 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2904 sem_item
*source_node
= c
->members
[j
];
2906 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2909 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2911 gcc_checking_assert (slot
);
2913 slot
->safe_push (source_node
);
2919 /* If the map contains more than one key, we have to split the map
2921 if (split_map
.elements () != 1)
2923 bool first_class
= true;
2925 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2926 it2
!= split_map
.end (); ++it2
)
2928 congruence_class
*new_cls
;
2929 new_cls
= new congruence_class (class_id
++);
2931 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2932 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2934 worklist_push (new_cls
);
2935 newly_created_classes
++;
2939 (*it
)->classes
[i
] = new_cls
;
2940 first_class
= false;
2944 new_classes
.safe_push (new_cls
);
2950 /* Release memory. */
2951 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2952 it2
!= split_map
.end (); ++it2
)
2954 delete (*it2
).first
;
2955 (*it2
).second
.release ();
2960 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2961 (*it
)->classes
.safe_push (new_classes
[i
]);
2964 return newly_created_classes
;
2967 /* Verify congruence classes, if checking is enabled. */
2970 sem_item_optimizer::checking_verify_classes (void)
2976 /* Verify congruence classes. */
2979 sem_item_optimizer::verify_classes (void)
2981 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2982 it
!= m_classes
.end (); ++it
)
2984 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2986 congruence_class
*cls
= (*it
)->classes
[i
];
2989 gcc_assert (cls
->members
.length () > 0);
2991 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2993 sem_item
*item
= cls
->members
[j
];
2996 gcc_assert (item
->cls
== cls
);
2998 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3000 sem_usage_pair
*usage
= item
->usages
[k
];
3001 gcc_assert (usage
->item
->index_in_class
<
3002 usage
->item
->cls
->members
.length ());
3009 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3010 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3011 but unused argument. */
3014 sem_item_optimizer::release_split_map (congruence_class
* const &,
3015 bitmap
const &b
, traverse_split_pair
*)
3024 /* Process split operation for a class given as pointer CLS_PTR,
3025 where bitmap B splits congruence class members. DATA is used
3026 as argument of split pair. */
3029 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3030 bitmap
const &b
, traverse_split_pair
*pair
)
3032 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3033 const congruence_class
*splitter_cls
= pair
->cls
;
3035 /* If counted bits are greater than zero and less than the number of members
3036 a group will be splitted. */
3037 unsigned popcount
= bitmap_count_bits (b
);
3039 if (popcount
> 0 && popcount
< cls
->members
.length ())
3041 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
3043 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3045 int target
= bitmap_bit_p (b
, i
);
3046 congruence_class
*tc
= newclasses
[target
];
3048 add_item_to_class (tc
, cls
->members
[i
]);
3053 for (unsigned int i
= 0; i
< 2; i
++)
3054 gcc_assert (newclasses
[i
]->members
.length ());
3057 if (splitter_cls
== cls
)
3058 optimizer
->splitter_class_removed
= true;
3060 /* Remove old class from worklist if presented. */
3061 bool in_worklist
= cls
->in_worklist
;
3064 cls
->in_worklist
= false;
3066 congruence_class_group g
;
3067 g
.hash
= cls
->members
[0]->get_hash ();
3068 g
.type
= cls
->members
[0]->type
;
3070 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3072 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3073 if (slot
->classes
[i
] == cls
)
3075 slot
->classes
.ordered_remove (i
);
3079 /* New class will be inserted and integrated to work list. */
3080 for (unsigned int i
= 0; i
< 2; i
++)
3081 optimizer
->add_class (newclasses
[i
]);
3083 /* Two classes replace one, so that increment just by one. */
3084 optimizer
->m_classes_count
++;
3086 /* If OLD class was presented in the worklist, we remove the class
3087 and replace it will both newly created classes. */
3089 for (unsigned int i
= 0; i
< 2; i
++)
3090 optimizer
->worklist_push (newclasses
[i
]);
3091 else /* Just smaller class is inserted. */
3093 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3094 newclasses
[1]->members
.length () ?
3096 optimizer
->worklist_push (newclasses
[smaller_index
]);
3099 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3101 fprintf (dump_file
, " congruence class splitted:\n");
3102 cls
->dump (dump_file
, 4);
3104 fprintf (dump_file
, " newly created groups:\n");
3105 for (unsigned int i
= 0; i
< 2; i
++)
3106 newclasses
[i
]->dump (dump_file
, 4);
3109 /* Release class if not presented in work list. */
3118 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3119 Bitmap stack BMSTACK is used for bitmap allocation. */
3122 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3125 hash_map
<congruence_class
*, bitmap
> split_map
;
3127 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3129 sem_item
*item
= cls
->members
[i
];
3131 /* Iterate all usages that have INDEX as usage of the item. */
3132 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3134 sem_usage_pair
*usage
= item
->usages
[j
];
3136 if (usage
->index
!= index
)
3139 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3144 b
= BITMAP_ALLOC (&m_bmstack
);
3145 split_map
.put (usage
->item
->cls
, b
);
3150 gcc_checking_assert (usage
->item
->cls
);
3151 gcc_checking_assert (usage
->item
->index_in_class
<
3152 usage
->item
->cls
->members
.length ());
3154 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3158 traverse_split_pair pair
;
3159 pair
.optimizer
= this;
3162 splitter_class_removed
= false;
3164 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3166 /* Bitmap clean-up. */
3168 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3171 /* Every usage of a congruence class CLS is a candidate that can split the
3172 collection of classes. Bitmap stack BMSTACK is used for bitmap
3176 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3181 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3183 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3184 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3186 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3188 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3189 fprintf (dump_file
, " processing congruence step for class: %u, index: %u\n",
3192 do_congruence_step_for_index (cls
, i
);
3194 if (splitter_class_removed
)
3198 BITMAP_FREE (usage
);
3201 /* Adds a newly created congruence class CLS to worklist. */
3204 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3206 /* Return if the class CLS is already presented in work list. */
3207 if (cls
->in_worklist
)
3210 cls
->in_worklist
= true;
3211 worklist
.push_back (cls
);
3214 /* Pops a class from worklist. */
3217 sem_item_optimizer::worklist_pop (void)
3219 congruence_class
*cls
;
3221 while (!worklist
.empty ())
3223 cls
= worklist
.front ();
3224 worklist
.pop_front ();
3225 if (cls
->in_worklist
)
3227 cls
->in_worklist
= false;
3233 /* Work list item was already intended to be removed.
3234 The only reason for doing it is to split a class.
3235 Thus, the class CLS is deleted. */
3243 /* Iterative congruence reduction function. */
3246 sem_item_optimizer::process_cong_reduction (void)
3248 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3249 it
!= m_classes
.end (); ++it
)
3250 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3251 if ((*it
)->classes
[i
]->is_class_used ())
3252 worklist_push ((*it
)->classes
[i
]);
3255 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3256 (unsigned long) worklist
.size ());
3258 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3259 fprintf (dump_file
, "Congruence class reduction\n");
3261 congruence_class
*cls
;
3263 /* Process complete congruence reduction. */
3264 while ((cls
= worklist_pop ()) != NULL
)
3265 do_congruence_step (cls
);
3267 /* Subdivide newly created classes according to references. */
3268 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3271 fprintf (dump_file
, "Address reference subdivision created: %u "
3272 "new classes.\n", new_classes
);
3275 /* Debug function prints all informations about congruence classes. */
3278 sem_item_optimizer::dump_cong_classes (void)
3284 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3285 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3287 /* Histogram calculation. */
3288 unsigned int max_index
= 0;
3289 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3291 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3292 it
!= m_classes
.end (); ++it
)
3294 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3296 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3304 "Class size histogram [num of members]: number of classe number of classess\n");
3306 for (unsigned int i
= 0; i
<= max_index
; i
++)
3308 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3310 fprintf (dump_file
, "\n\n");
3313 if (dump_flags
& TDF_DETAILS
)
3314 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3315 it
!= m_classes
.end (); ++it
)
3317 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3319 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3321 (*it
)->classes
[i
]->dump (dump_file
, 4);
3323 if(i
< (*it
)->classes
.length () - 1)
3324 fprintf (dump_file
, " ");
3331 /* After reduction is done, we can declare all items in a group
3332 to be equal. PREV_CLASS_COUNT is start number of classes
3333 before reduction. True is returned if there's a merge operation
3337 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3339 unsigned int item_count
= m_items
.length ();
3340 unsigned int class_count
= m_classes_count
;
3341 unsigned int equal_items
= item_count
- class_count
;
3343 unsigned int non_singular_classes_count
= 0;
3344 unsigned int non_singular_classes_sum
= 0;
3346 bool merged_p
= false;
3348 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3349 it
!= m_classes
.end (); ++it
)
3350 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3352 congruence_class
*c
= (*it
)->classes
[i
];
3353 if (c
->members
.length () > 1)
3355 non_singular_classes_count
++;
3356 non_singular_classes_sum
+= c
->members
.length ();
3362 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3363 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3364 prev_class_count
, class_count
);
3365 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3366 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3367 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3368 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3369 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3370 non_singular_classes_count
: 0.0f
,
3371 non_singular_classes_count
);
3372 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3373 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3374 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3377 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3378 it
!= m_classes
.end (); ++it
)
3379 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3381 congruence_class
*c
= (*it
)->classes
[i
];
3383 if (c
->members
.length () == 1)
3386 gcc_assert (c
->members
.length ());
3388 sem_item
*source
= c
->members
[0];
3390 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
3392 sem_item
*alias
= c
->members
[j
];
3396 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3397 xstrdup_for_dump (source
->node
->name ()),
3398 xstrdup_for_dump (alias
->node
->name ()));
3399 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3400 xstrdup_for_dump (source
->node
->asm_name ()),
3401 xstrdup_for_dump (alias
->node
->asm_name ()));
3404 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3408 "Merge operation is skipped due to no_icf "
3414 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3416 source
->dump_to_file (dump_file
);
3417 alias
->dump_to_file (dump_file
);
3420 if (dbg_cnt (merged_ipa_icf
))
3421 merged_p
|= source
->merge (alias
);
3428 /* Dump function prints all class members to a FILE with an INDENT. */
3431 congruence_class::dump (FILE *file
, unsigned int indent
) const
3433 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3434 id
, members
[0]->get_hash (), members
.length ());
3436 FPUTS_SPACES (file
, indent
+ 2, "");
3437 for (unsigned i
= 0; i
< members
.length (); i
++)
3438 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3439 (void *) members
[i
]->decl
,
3440 members
[i
]->node
->order
);
3442 fprintf (file
, "\n");
3445 /* Returns true if there's a member that is used from another group. */
3448 congruence_class::is_class_used (void)
3450 for (unsigned int i
= 0; i
< members
.length (); i
++)
3451 if (members
[i
]->usages
.length ())
3457 /* Generate pass summary for IPA ICF pass. */
3460 ipa_icf_generate_summary (void)
3463 optimizer
= new sem_item_optimizer ();
3465 optimizer
->register_hooks ();
3466 optimizer
->parse_funcs_and_vars ();
3469 /* Write pass summary for IPA ICF pass. */
3472 ipa_icf_write_summary (void)
3474 gcc_assert (optimizer
);
3476 optimizer
->write_summary ();
3479 /* Read pass summary for IPA ICF pass. */
3482 ipa_icf_read_summary (void)
3485 optimizer
= new sem_item_optimizer ();
3487 optimizer
->read_summary ();
3488 optimizer
->register_hooks ();
3491 /* Semantic equality exection function. */
3494 ipa_icf_driver (void)
3496 gcc_assert (optimizer
);
3498 bool merged_p
= optimizer
->execute ();
3503 return merged_p
? TODO_remove_functions
: 0;
3506 const pass_data pass_data_ipa_icf
=
3508 IPA_PASS
, /* type */
3510 OPTGROUP_IPA
, /* optinfo_flags */
3511 TV_IPA_ICF
, /* tv_id */
3512 0, /* properties_required */
3513 0, /* properties_provided */
3514 0, /* properties_destroyed */
3515 0, /* todo_flags_start */
3516 0, /* todo_flags_finish */
3519 class pass_ipa_icf
: public ipa_opt_pass_d
3522 pass_ipa_icf (gcc::context
*ctxt
)
3523 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3524 ipa_icf_generate_summary
, /* generate_summary */
3525 ipa_icf_write_summary
, /* write_summary */
3526 ipa_icf_read_summary
, /* read_summary */
3528 write_optimization_summary */
3530 read_optimization_summary */
3531 NULL
, /* stmt_fixup */
3532 0, /* function_transform_todo_flags_start */
3533 NULL
, /* function_transform */
3534 NULL
) /* variable_transform */
3537 /* opt_pass methods: */
3538 virtual bool gate (function
*)
3540 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3543 virtual unsigned int execute (function
*)
3545 return ipa_icf_driver();
3547 }; // class pass_ipa_icf
3549 } // ipa_icf namespace
3552 make_pass_ipa_icf (gcc::context
*ctxt
)
3554 return new ipa_icf::pass_ipa_icf (ctxt
);