1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
57 #include "coretypes.h"
63 #include "fold-const.h"
66 #include "hard-reg-set.h"
68 #include "dominance.h"
70 #include "basic-block.h"
71 #include "tree-ssa-alias.h"
72 #include "internal-fn.h"
73 #include "gimple-expr.h"
78 #include "insn-config.h"
87 #include "gimple-iterator.h"
88 #include "gimple-ssa.h"
90 #include "tree-phinodes.h"
91 #include "stringpool.h"
92 #include "tree-ssanames.h"
94 #include "tree-pass.h"
95 #include "gimple-pretty-print.h"
96 #include "plugin-api.h"
99 #include "alloc-pool.h"
100 #include "symbol-summary.h"
101 #include "ipa-prop.h"
102 #include "ipa-inline.h"
105 #include "coverage.h"
107 #include "print-tree.h"
108 #include "lto-streamer.h"
109 #include "data-streamer.h"
110 #include "ipa-utils.h"
111 #include "ipa-icf-gimple.h"
113 #include "stor-layout.h"
116 using namespace ipa_icf_gimple
;
120 /* Initialization and computation of symtab node hash, there data
121 are propagated later on. */
123 static sem_item_optimizer
*optimizer
= NULL
;
127 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
129 m_references
.create (0);
130 m_interposables
.create (0);
134 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
137 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
139 if (ref
->address_matters_p ())
140 m_references
.safe_push (ref
->referred
);
142 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
144 if (ref
->address_matters_p ())
145 m_references
.safe_push (ref
->referred
);
147 m_interposables
.safe_push (ref
->referred
);
151 if (is_a
<cgraph_node
*> (node
))
153 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
155 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
156 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
157 m_interposables
.safe_push (e
->callee
);
161 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
163 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
164 item (_item
), index (_index
)
168 /* Semantic item constructor for a node of _TYPE, where STACK is used
169 for bitmap memory allocation. */
171 sem_item::sem_item (sem_item_type _type
,
172 bitmap_obstack
*stack
): type(_type
), hash(0)
177 /* Semantic item constructor for a node of _TYPE, where STACK is used
178 for bitmap memory allocation. The item is based on symtab node _NODE
179 with computed _HASH. */
181 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
182 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
183 node (_node
), hash (_hash
)
189 /* Add reference to a semantic TARGET. */
192 sem_item::add_reference (sem_item
*target
)
194 refs
.safe_push (target
);
195 unsigned index
= refs
.length ();
196 target
->usages
.safe_push (new sem_usage_pair(this, index
));
197 bitmap_set_bit (target
->usage_index_bitmap
, index
);
198 refs_set
.add (target
->node
);
201 /* Initialize internal data structures. Bitmap STACK is used for
202 bitmap memory allocation process. */
205 sem_item::setup (bitmap_obstack
*stack
)
207 gcc_checking_assert (node
);
210 tree_refs
.create (0);
212 usage_index_bitmap
= BITMAP_ALLOC (stack
);
215 sem_item::~sem_item ()
217 for (unsigned i
= 0; i
< usages
.length (); i
++)
221 tree_refs
.release ();
224 BITMAP_FREE (usage_index_bitmap
);
227 /* Dump function for debugging purpose. */
230 sem_item::dump (void)
234 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
235 node
->name(), node
->order
, (void *) node
->decl
);
236 fprintf (dump_file
, " hash: %u\n", get_hash ());
237 fprintf (dump_file
, " references: ");
239 for (unsigned i
= 0; i
< refs
.length (); i
++)
240 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
241 i
< refs
.length() - 1 ? "," : "");
243 fprintf (dump_file
, "\n");
247 /* Return true if target supports alias symbols. */
250 sem_item::target_supports_symbol_aliases_p (void)
252 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
259 /* Semantic function constructor that uses STACK as bitmap memory stack. */
261 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
262 m_checker (NULL
), m_compared_func (NULL
)
264 arg_types
.create (0);
266 bb_sorted
.create (0);
269 /* Constructor based on callgraph node _NODE with computed hash _HASH.
270 Bitmap STACK is used for memory allocation. */
271 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
272 bitmap_obstack
*stack
):
273 sem_item (FUNC
, node
, hash
, stack
),
274 m_checker (NULL
), m_compared_func (NULL
)
276 arg_types
.create (0);
278 bb_sorted
.create (0);
281 sem_function::~sem_function ()
283 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
284 delete (bb_sorted
[i
]);
286 arg_types
.release ();
288 bb_sorted
.release ();
291 /* Calculates hash value based on a BASIC_BLOCK. */
294 sem_function::get_bb_hash (const sem_bb
*basic_block
)
296 inchash::hash hstate
;
298 hstate
.add_int (basic_block
->nondbg_stmt_count
);
299 hstate
.add_int (basic_block
->edge_count
);
301 return hstate
.end ();
304 /* References independent hash function. */
307 sem_function::get_hash (void)
311 inchash::hash hstate
;
312 hstate
.add_int (177454); /* Random number for function type. */
314 hstate
.add_int (arg_count
);
315 hstate
.add_int (cfg_checksum
);
316 hstate
.add_int (gcode_hash
);
318 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
319 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
321 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
322 hstate
.add_int (bb_sizes
[i
]);
325 /* Add common features of declaration itself. */
326 if (DECL_FUNCTION_SPECIFIC_TARGET (decl
))
328 (cl_target_option_hash
329 (TREE_TARGET_OPTION (DECL_FUNCTION_SPECIFIC_TARGET (decl
))));
330 if (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))
331 (cl_optimization_hash
332 (TREE_OPTIMIZATION (DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl
))));
333 hstate
.add_flag (DECL_CXX_CONSTRUCTOR_P (decl
));
334 hstate
.add_flag (DECL_CXX_DESTRUCTOR_P (decl
));
336 hash
= hstate
.end ();
342 /* Return ture if A1 and A2 represent equivalent function attribute lists.
343 Based on comp_type_attributes. */
346 sem_item::compare_attributes (const_tree a1
, const_tree a2
)
351 for (a
= a1
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
353 const struct attribute_spec
*as
;
356 as
= lookup_attribute_spec (get_attribute_name (a
));
357 /* TODO: We can introduce as->affects_decl_identity
358 and as->affects_decl_reference_identity if attribute mismatch
359 gets a common reason to give up on merging. It may not be worth
361 For example returns_nonnull affects only references, while
362 optimize attribute can be ignored because it is already lowered
363 into flags representation and compared separately. */
367 attr
= lookup_attribute (as
->name
, CONST_CAST_TREE (a2
));
368 if (!attr
|| !attribute_value_equal (a
, attr
))
373 for (a
= a2
; a
!= NULL_TREE
; a
= TREE_CHAIN (a
))
375 const struct attribute_spec
*as
;
377 as
= lookup_attribute_spec (get_attribute_name (a
));
381 if (!lookup_attribute (as
->name
, CONST_CAST_TREE (a1
)))
383 /* We don't need to compare trees again, as we did this
384 already in first loop. */
389 /* TODO: As in comp_type_attributes we may want to introduce target hook. */
393 /* Compare properties of symbols N1 and N2 that does not affect semantics of
394 symbol itself but affects semantics of its references from USED_BY (which
395 may be NULL if it is unknown). If comparsion is false, symbols
396 can still be merged but any symbols referring them can't.
398 If ADDRESS is true, do extra checking needed for IPA_REF_ADDR.
400 TODO: We can also split attributes to those that determine codegen of
401 a function body/variable constructor itself and those that are used when
405 sem_item::compare_referenced_symbol_properties (symtab_node
*used_by
,
410 if (is_a
<cgraph_node
*> (n1
))
412 /* Inline properties matters: we do now want to merge uses of inline
413 function to uses of normal function because inline hint would be lost.
414 We however can merge inline function to noinline because the alias
415 will keep its DECL_DECLARED_INLINE flag.
417 Also ignore inline flag when optimizing for size or when function
418 is known to not be inlinable.
420 TODO: the optimize_size checks can also be assumed to be true if
421 unit has no !optimize_size functions. */
423 if ((!used_by
|| address
|| !is_a
<cgraph_node
*> (used_by
)
424 || !opt_for_fn (used_by
->decl
, optimize_size
))
425 && !opt_for_fn (n1
->decl
, optimize_size
)
426 && n1
->get_availability () > AVAIL_INTERPOSABLE
427 && (!DECL_UNINLINABLE (n1
->decl
) || !DECL_UNINLINABLE (n2
->decl
)))
429 if (DECL_DISREGARD_INLINE_LIMITS (n1
->decl
)
430 != DECL_DISREGARD_INLINE_LIMITS (n2
->decl
))
431 return return_false_with_msg
432 ("DECL_DISREGARD_INLINE_LIMITS are different");
434 if (DECL_DECLARED_INLINE_P (n1
->decl
)
435 != DECL_DECLARED_INLINE_P (n2
->decl
))
436 return return_false_with_msg ("inline attributes are different");
439 if (DECL_IS_OPERATOR_NEW (n1
->decl
)
440 != DECL_IS_OPERATOR_NEW (n2
->decl
))
441 return return_false_with_msg ("operator new flags are different");
444 /* Merging two definitions with a reference to equivalent vtables, but
445 belonging to a different type may result in ipa-polymorphic-call analysis
446 giving a wrong answer about the dynamic type of instance. */
447 if (is_a
<varpool_node
*> (n1
))
449 if ((DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
450 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
451 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
452 DECL_CONTEXT (n2
->decl
)))
453 && (!used_by
|| !is_a
<cgraph_node
*> (used_by
) || address
454 || opt_for_fn (used_by
->decl
, flag_devirtualize
)))
455 return return_false_with_msg
456 ("references to virtual tables can not be merged");
458 if (address
&& DECL_ALIGN (n1
->decl
) != DECL_ALIGN (n2
->decl
))
459 return return_false_with_msg ("alignment mismatch");
461 /* For functions we compare attributes in equals_wpa, because we do
462 not know what attributes may cause codegen differences, but for
463 variables just compare attributes for references - the codegen
464 for constructors is affected only by those attributes that we lower
465 to explicit representation (such as DECL_ALIGN or DECL_SECTION). */
466 if (!compare_attributes (DECL_ATTRIBUTES (n1
->decl
),
467 DECL_ATTRIBUTES (n2
->decl
)))
468 return return_false_with_msg ("different var decl attributes");
469 if (comp_type_attributes (TREE_TYPE (n1
->decl
),
470 TREE_TYPE (n2
->decl
)) != 1)
471 return return_false_with_msg ("different var type attributes");
474 /* When matching virtual tables, be sure to also match information
475 relevant for polymorphic call analysis. */
476 if (used_by
&& is_a
<varpool_node
*> (used_by
)
477 && DECL_VIRTUAL_P (used_by
->decl
))
479 if (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
))
480 return return_false_with_msg ("virtual flag mismatch");
481 if (DECL_VIRTUAL_P (n1
->decl
) && is_a
<cgraph_node
*> (n1
)
482 && (DECL_FINAL_P (n1
->decl
) != DECL_FINAL_P (n2
->decl
)))
483 return return_false_with_msg ("final flag mismatch");
488 /* Hash properties that are compared by compare_referenced_symbol_properties. */
491 sem_item::hash_referenced_symbol_properties (symtab_node
*ref
,
492 inchash::hash
&hstate
,
495 if (is_a
<cgraph_node
*> (ref
))
497 if ((type
!= FUNC
|| address
|| !opt_for_fn (decl
, optimize_size
))
498 && !opt_for_fn (ref
->decl
, optimize_size
)
499 && !DECL_UNINLINABLE (ref
->decl
))
501 hstate
.add_flag (DECL_DISREGARD_INLINE_LIMITS (ref
->decl
));
502 hstate
.add_flag (DECL_DECLARED_INLINE_P (ref
->decl
));
504 hstate
.add_flag (DECL_IS_OPERATOR_NEW (ref
->decl
));
506 else if (is_a
<varpool_node
*> (ref
))
508 hstate
.add_flag (DECL_VIRTUAL_P (ref
->decl
));
510 hstate
.add_int (DECL_ALIGN (ref
->decl
));
515 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
516 point to a same function. Comparison can be skipped if IGNORED_NODES
517 contains these nodes. ADDRESS indicate if address is taken. */
520 sem_item::compare_symbol_references (
521 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
522 symtab_node
*n1
, symtab_node
*n2
, bool address
)
524 enum availability avail1
, avail2
;
529 /* Never match variable and function. */
530 if (is_a
<varpool_node
*> (n1
) != is_a
<varpool_node
*> (n2
))
533 if (!compare_referenced_symbol_properties (node
, n1
, n2
, address
))
535 if (address
&& n1
->equal_address_to (n2
) == 1)
537 if (!address
&& n1
->semantically_equivalent_p (n2
))
540 n1
= n1
->ultimate_alias_target (&avail1
);
541 n2
= n2
->ultimate_alias_target (&avail2
);
543 if (avail1
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
544 && avail2
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
547 return return_false_with_msg ("different references");
550 /* If cgraph edges E1 and E2 are indirect calls, verify that
551 ECF flags are the same. */
553 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
555 if (e1
->indirect_info
&& e2
->indirect_info
)
557 int e1_flags
= e1
->indirect_info
->ecf_flags
;
558 int e2_flags
= e2
->indirect_info
->ecf_flags
;
560 if (e1_flags
!= e2_flags
)
561 return return_false_with_msg ("ICF flags are different");
563 else if (e1
->indirect_info
|| e2
->indirect_info
)
569 /* Return true if parameter I may be used. */
572 sem_function::param_used_p (unsigned int i
)
574 if (ipa_node_params_sum
== NULL
)
577 struct ipa_node_params
*parms_info
= IPA_NODE_REF (get_node ());
579 if (parms_info
->descriptors
.is_empty ()
580 || parms_info
->descriptors
.length () <= i
)
583 return ipa_is_param_used (IPA_NODE_REF (get_node ()), i
);
586 /* Fast equality function based on knowledge known in WPA. */
589 sem_function::equals_wpa (sem_item
*item
,
590 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
592 gcc_assert (item
->type
== FUNC
);
593 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
594 cgraph_node
*cnode2
= dyn_cast
<cgraph_node
*> (item
->node
);
596 m_compared_func
= static_cast<sem_function
*> (item
);
598 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
599 return return_false_with_msg ("different number of arguments");
601 if (cnode
->thunk
.thunk_p
!= cnode2
->thunk
.thunk_p
)
602 return return_false_with_msg ("thunk_p mismatch");
604 if (cnode
->thunk
.thunk_p
)
606 if (cnode
->thunk
.fixed_offset
!= cnode2
->thunk
.fixed_offset
)
607 return return_false_with_msg ("thunk fixed_offset mismatch");
608 if (cnode
->thunk
.virtual_value
!= cnode2
->thunk
.virtual_value
)
609 return return_false_with_msg ("thunk virtual_value mismatch");
610 if (cnode
->thunk
.this_adjusting
!= cnode2
->thunk
.this_adjusting
)
611 return return_false_with_msg ("thunk this_adjusting mismatch");
612 if (cnode
->thunk
.virtual_offset_p
!= cnode2
->thunk
.virtual_offset_p
)
613 return return_false_with_msg ("thunk virtual_offset_p mismatch");
614 if (cnode
->thunk
.add_pointer_bounds_args
615 != cnode2
->thunk
.add_pointer_bounds_args
)
616 return return_false_with_msg ("thunk add_pointer_bounds_args mismatch");
619 /* Compare special function DECL attributes. */
620 if (DECL_FUNCTION_PERSONALITY (decl
)
621 != DECL_FUNCTION_PERSONALITY (item
->decl
))
622 return return_false_with_msg ("function personalities are different");
624 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
625 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
626 return return_false_with_msg ("intrument function entry exit "
627 "attributes are different");
629 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
630 return return_false_with_msg ("no stack limit attributes are different");
632 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
633 return return_false_with_msg ("DECL_CXX_CONSTRUCTOR mismatch");
635 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
636 return return_false_with_msg ("DECL_CXX_DESTRUCTOR mismatch");
638 /* TODO: pure/const flags mostly matters only for references, except for
639 the fact that codegen takes LOOPING flag as a hint that loops are
640 finite. We may arrange the code to always pick leader that has least
641 specified flags and then this can go into comparing symbol properties. */
642 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
643 return return_false_with_msg ("decl_or_type flags are different");
645 /* Do not match polymorphic constructors of different types. They calls
646 type memory location for ipa-polymorphic-call and we do not want
647 it to get confused by wrong type. */
648 if (DECL_CXX_CONSTRUCTOR_P (decl
)
649 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
651 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
652 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
653 else if (!func_checker::compatible_polymorphic_types_p
654 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
655 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
656 return return_false_with_msg ("ctor polymorphic type mismatch");
659 /* Checking function TARGET and OPTIMIZATION flags. */
660 cl_target_option
*tar1
= target_opts_for_fn (decl
);
661 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
663 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
665 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
667 fprintf (dump_file
, "target flags difference");
668 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
671 return return_false_with_msg ("Target flags are different");
674 cl_optimization
*opt1
= opts_for_fn (decl
);
675 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
677 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
679 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
681 fprintf (dump_file
, "optimization flags difference");
682 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
685 return return_false_with_msg ("optimization flags are different");
688 /* Result type checking. */
689 if (!func_checker::compatible_types_p (result_type
,
690 m_compared_func
->result_type
))
691 return return_false_with_msg ("result types are different");
693 /* Checking types of arguments. */
694 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
696 /* This guard is here for function pointer with attributes (pr59927.c). */
697 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
698 return return_false_with_msg ("NULL argument type");
700 /* We always need to match types so we are sure the callin conventions
702 if (!func_checker::compatible_types_p (arg_types
[i
],
703 m_compared_func
->arg_types
[i
]))
704 return return_false_with_msg ("argument type is different");
706 /* On used arguments we need to do a bit more of work. */
707 if (!param_used_p (i
))
709 if (POINTER_TYPE_P (arg_types
[i
])
710 && (TYPE_RESTRICT (arg_types
[i
])
711 != TYPE_RESTRICT (m_compared_func
->arg_types
[i
])))
712 return return_false_with_msg ("argument restrict flag mismatch");
713 /* nonnull_arg_p implies non-zero range to REFERENCE types. */
714 if (POINTER_TYPE_P (arg_types
[i
])
715 && TREE_CODE (arg_types
[i
])
716 != TREE_CODE (m_compared_func
->arg_types
[i
])
717 && opt_for_fn (decl
, flag_delete_null_pointer_checks
))
718 return return_false_with_msg ("pointer wrt reference mismatch");
721 if (node
->num_references () != item
->node
->num_references ())
722 return return_false_with_msg ("different number of references");
724 /* Checking function attributes.
725 This is quadratic in number of attributes */
726 if (comp_type_attributes (TREE_TYPE (decl
),
727 TREE_TYPE (item
->decl
)) != 1)
728 return return_false_with_msg ("different type attributes");
729 if (!compare_attributes (DECL_ATTRIBUTES (decl
),
730 DECL_ATTRIBUTES (item
->decl
)))
731 return return_false_with_msg ("different decl attributes");
733 /* The type of THIS pointer type memory location for
734 ipa-polymorphic-call-analysis. */
735 if (opt_for_fn (decl
, flag_devirtualize
)
736 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
737 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
739 && compare_polymorphic_p ())
741 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
742 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
743 if (!func_checker::compatible_polymorphic_types_p
744 (TYPE_METHOD_BASETYPE (TREE_TYPE (decl
)),
745 TYPE_METHOD_BASETYPE (TREE_TYPE (item
->decl
)), false))
746 return return_false_with_msg ("THIS pointer ODR type mismatch");
749 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
750 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
752 item
->node
->iterate_reference (i
, ref2
);
754 if (ref
->use
!= ref2
->use
)
755 return return_false_with_msg ("reference use mismatch");
757 if (!compare_symbol_references (ignored_nodes
, ref
->referred
,
759 ref
->address_matters_p ()))
763 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
764 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
768 if (!compare_symbol_references (ignored_nodes
, e1
->callee
,
771 if (!compare_edge_flags (e1
, e2
))
774 e1
= e1
->next_callee
;
775 e2
= e2
->next_callee
;
779 return return_false_with_msg ("different number of calls");
781 e1
= dyn_cast
<cgraph_node
*> (node
)->indirect_calls
;
782 e2
= dyn_cast
<cgraph_node
*> (item
->node
)->indirect_calls
;
786 if (!compare_edge_flags (e1
, e2
))
789 e1
= e1
->next_callee
;
790 e2
= e2
->next_callee
;
794 return return_false_with_msg ("different number of indirect calls");
799 /* Update hash by address sensitive references. We iterate over all
800 sensitive references (address_matters_p) and we hash ultime alias
801 target of these nodes, which can improve a semantic item hash.
803 Also hash in referenced symbols properties. This can be done at any time
804 (as the properties should not change), but it is convenient to do it here
805 while we walk the references anyway. */
808 sem_item::update_hash_by_addr_refs (hash_map
<symtab_node
*,
809 sem_item
*> &m_symtab_node_map
)
812 inchash::hash
hstate (hash
);
814 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
816 hstate
.add_int (ref
->use
);
817 hash_referenced_symbol_properties (ref
->referred
, hstate
,
818 ref
->use
== IPA_REF_ADDR
);
819 if (ref
->address_matters_p () || !m_symtab_node_map
.get (ref
->referred
))
820 hstate
.add_int (ref
->referred
->ultimate_alias_target ()->order
);
823 if (is_a
<cgraph_node
*> (node
))
825 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callers
; e
;
828 sem_item
**result
= m_symtab_node_map
.get (e
->callee
);
829 hash_referenced_symbol_properties (e
->callee
, hstate
, false);
831 hstate
.add_int (e
->callee
->ultimate_alias_target ()->order
);
835 hash
= hstate
.end ();
838 /* Update hash by computed local hash values taken from different
840 TODO: stronger SCC based hashing would be desirable here. */
843 sem_item::update_hash_by_local_refs (hash_map
<symtab_node
*,
844 sem_item
*> &m_symtab_node_map
)
847 inchash::hash
state (hash
);
849 for (unsigned j
= 0; node
->iterate_reference (j
, ref
); j
++)
851 sem_item
**result
= m_symtab_node_map
.get (ref
->referring
);
853 state
.merge_hash ((*result
)->hash
);
858 for (cgraph_edge
*e
= dyn_cast
<cgraph_node
*> (node
)->callees
; e
;
861 sem_item
**result
= m_symtab_node_map
.get (e
->caller
);
863 state
.merge_hash ((*result
)->hash
);
867 global_hash
= state
.end ();
870 /* Returns true if the item equals to ITEM given as argument. */
873 sem_function::equals (sem_item
*item
,
874 hash_map
<symtab_node
*, sem_item
*> &)
876 gcc_assert (item
->type
== FUNC
);
877 bool eq
= equals_private (item
);
879 if (m_checker
!= NULL
)
885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
887 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
888 xstrdup_for_dump (node
->name()),
889 xstrdup_for_dump (item
->node
->name ()),
892 xstrdup_for_dump (node
->asm_name ()),
893 xstrdup_for_dump (item
->node
->asm_name ()),
894 eq
? "true" : "false");
899 /* Processes function equality comparison. */
902 sem_function::equals_private (sem_item
*item
)
904 if (item
->type
!= FUNC
)
907 basic_block bb1
, bb2
;
909 edge_iterator ei1
, ei2
;
913 m_compared_func
= static_cast<sem_function
*> (item
);
915 gcc_assert (decl
!= item
->decl
);
917 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
918 || edge_count
!= m_compared_func
->edge_count
919 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
920 return return_false ();
922 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
923 compare_polymorphic_p (),
926 &m_compared_func
->refs_set
);
927 for (arg1
= DECL_ARGUMENTS (decl
),
928 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
929 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
930 if (!m_checker
->compare_decl (arg1
, arg2
))
931 return return_false ();
933 if (!dyn_cast
<cgraph_node
*> (node
)->has_gimple_body_p ())
936 /* Fill-up label dictionary. */
937 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
939 m_checker
->parse_labels (bb_sorted
[i
]);
940 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
943 /* Checking all basic blocks. */
944 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
945 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
946 return return_false();
948 dump_message ("All BBs are equal\n");
950 auto_vec
<int> bb_dict
;
952 /* Basic block edges check. */
953 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
955 bb1
= bb_sorted
[i
]->bb
;
956 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
958 ei2
= ei_start (bb2
->preds
);
960 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
964 if (e1
->flags
!= e2
->flags
)
965 return return_false_with_msg ("flags comparison returns false");
967 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
968 return return_false_with_msg ("edge comparison returns false");
970 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
971 return return_false_with_msg ("BB comparison returns false");
973 if (!m_checker
->compare_edge (e1
, e2
))
974 return return_false_with_msg ("edge comparison returns false");
980 /* Basic block PHI nodes comparison. */
981 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
982 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
983 return return_false_with_msg ("PHI node comparison returns false");
988 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
989 Helper for call_for_symbol_thunks_and_aliases. */
992 set_local (cgraph_node
*node
, void *data
)
994 node
->local
.local
= data
!= NULL
;
998 /* TREE_ADDRESSABLE of NODE to true.
999 Helper for call_for_symbol_thunks_and_aliases. */
1002 set_addressable (varpool_node
*node
, void *)
1004 TREE_ADDRESSABLE (node
->decl
) = 1;
1008 /* Clear DECL_RTL of NODE.
1009 Helper for call_for_symbol_thunks_and_aliases. */
1012 clear_decl_rtl (symtab_node
*node
, void *)
1014 SET_DECL_RTL (node
->decl
, NULL
);
1018 /* Redirect all callers of N and its aliases to TO. Remove aliases if
1019 possible. Return number of redirections made. */
1022 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
1024 int nredirected
= 0;
1026 cgraph_edge
*e
= n
->callers
;
1030 /* Redirecting thunks to interposable symbols or symbols in other sections
1031 may not be supported by target output code. Play safe for now and
1032 punt on redirection. */
1033 if (!e
->caller
->thunk
.thunk_p
)
1035 struct cgraph_edge
*nexte
= e
->next_caller
;
1036 e
->redirect_callee (to
);
1043 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
1045 bool removed
= false;
1046 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
1048 if ((DECL_COMDAT_GROUP (n
->decl
)
1049 && (DECL_COMDAT_GROUP (n
->decl
)
1050 == DECL_COMDAT_GROUP (n_alias
->decl
)))
1051 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
1052 && n
->get_availability () > AVAIL_INTERPOSABLE
))
1054 nredirected
+= redirect_all_callers (n_alias
, to
);
1055 if (n_alias
->can_remove_if_no_direct_calls_p ()
1056 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1058 && !n_alias
->has_aliases_p ())
1067 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1071 sem_function::merge (sem_item
*alias_item
)
1073 gcc_assert (alias_item
->type
== FUNC
);
1075 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
1077 cgraph_node
*original
= get_node ();
1078 cgraph_node
*local_original
= NULL
;
1079 cgraph_node
*alias
= alias_func
->get_node ();
1081 bool create_wrapper
= false;
1082 bool create_alias
= false;
1083 bool redirect_callers
= false;
1084 bool remove
= false;
1086 bool original_discardable
= false;
1087 bool original_discarded
= false;
1089 bool original_address_matters
= original
->address_matters_p ();
1090 bool alias_address_matters
= alias
->address_matters_p ();
1092 if (DECL_EXTERNAL (alias
->decl
))
1095 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
1099 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
1100 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
1105 "DECL_NO_INLINE_WARNING mismatch.\n\n");
1109 /* Do not attempt to mix functions from different user sections;
1110 we do not know what user intends with those. */
1111 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1112 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1113 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1118 "original and alias are in different sections.\n\n");
1122 /* See if original is in a section that can be discarded if the main
1123 symbol is not used. */
1125 if (original
->can_be_discarded_p ())
1126 original_discardable
= true;
1127 /* Also consider case where we have resolution info and we know that
1128 original's definition is not going to be used. In this case we can not
1129 create alias to original. */
1130 if (node
->resolution
!= LDPR_UNKNOWN
1131 && !decl_binds_to_current_def_p (node
->decl
))
1132 original_discardable
= original_discarded
= true;
1134 /* Creating a symtab alias is the optimal way to merge.
1135 It however can not be used in the following cases:
1137 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
1138 2) if ORIGINAL is in a section that may be discarded by linker or if
1139 it is an external functions where we can not create an alias
1140 (ORIGINAL_DISCARDABLE)
1141 3) if target do not support symbol aliases.
1142 4) original and alias lie in different comdat groups.
1144 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
1145 and/or redirect all callers from ALIAS to ORIGINAL. */
1146 if ((original_address_matters
&& alias_address_matters
)
1147 || (original_discardable
1148 && (!DECL_COMDAT_GROUP (alias
->decl
)
1149 || (DECL_COMDAT_GROUP (alias
->decl
)
1150 != DECL_COMDAT_GROUP (original
->decl
))))
1151 || original_discarded
1152 || !sem_item::target_supports_symbol_aliases_p ()
1153 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
1155 /* First see if we can produce wrapper. */
1157 /* Symbol properties that matter for references must be preserved.
1158 TODO: We can produce wrapper, but we need to produce alias of ORIGINAL
1159 with proper properties. */
1160 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1161 alias
->address_taken
))
1165 "Wrapper cannot be created because referenced symbol "
1166 "properties mismatch\n");
1168 /* Do not turn function in one comdat group into wrapper to another
1169 comdat group. Other compiler producing the body of the
1170 another comdat group may make opossite decision and with unfortunate
1171 linker choices this may close a loop. */
1172 else if (DECL_COMDAT_GROUP (original
->decl
)
1173 && DECL_COMDAT_GROUP (alias
->decl
)
1174 && (DECL_COMDAT_GROUP (alias
->decl
)
1175 != DECL_COMDAT_GROUP (original
->decl
)))
1179 "Wrapper cannot be created because of COMDAT\n");
1181 else if (DECL_STATIC_CHAIN (alias
->decl
))
1185 "Can not create wrapper of nested functions.\n");
1187 /* TODO: We can also deal with variadic functions never calling
1189 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
1193 "can not create wrapper of stdarg function.\n");
1195 else if (inline_summaries
1196 && inline_summaries
->get (alias
)->self_size
<= 2)
1199 fprintf (dump_file
, "Wrapper creation is not "
1200 "profitable (function is too small).\n");
1202 /* If user paid attention to mark function noinline, assume it is
1203 somewhat special and do not try to turn it into a wrapper that can
1204 not be undone by inliner. */
1205 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
1208 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
1211 create_wrapper
= true;
1213 /* We can redirect local calls in the case both alias and orignal
1214 are not interposable. */
1216 = alias
->get_availability () > AVAIL_INTERPOSABLE
1217 && original
->get_availability () > AVAIL_INTERPOSABLE
1218 && !alias
->instrumented_version
;
1219 /* TODO: We can redirect, but we need to produce alias of ORIGINAL
1220 with proper properties. */
1221 if (!sem_item::compare_referenced_symbol_properties (NULL
, original
, alias
,
1222 alias
->address_taken
))
1223 redirect_callers
= false;
1225 if (!redirect_callers
&& !create_wrapper
)
1228 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
1229 "produce wrapper\n\n");
1233 /* Work out the symbol the wrapper should call.
1234 If ORIGINAL is interposable, we need to call a local alias.
1235 Also produce local alias (if possible) as an optimization.
1237 Local aliases can not be created inside comdat groups because that
1238 prevents inlining. */
1239 if (!original_discardable
&& !original
->get_comdat_group ())
1242 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
1244 && original
->get_availability () > AVAIL_INTERPOSABLE
)
1245 local_original
= original
;
1247 /* If we can not use local alias, fallback to the original
1249 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
1250 local_original
= original
;
1252 /* If original is COMDAT local, we can not really redirect calls outside
1253 of its comdat group to it. */
1254 if (original
->comdat_local_p ())
1255 redirect_callers
= false;
1256 if (!local_original
)
1259 fprintf (dump_file
, "Not unifying; "
1260 "can not produce local alias.\n\n");
1264 if (!redirect_callers
&& !create_wrapper
)
1267 fprintf (dump_file
, "Not unifying; "
1268 "can not redirect callers nor produce a wrapper\n\n");
1272 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
1274 && !alias
->can_remove_if_no_direct_calls_p ())
1277 fprintf (dump_file
, "Not unifying; can not make wrapper and "
1278 "function has other uses than direct calls\n\n");
1283 create_alias
= true;
1285 if (redirect_callers
)
1287 int nredirected
= redirect_all_callers (alias
, local_original
);
1291 alias
->icf_merged
= true;
1292 local_original
->icf_merged
= true;
1294 if (dump_file
&& nredirected
)
1295 fprintf (dump_file
, "%i local calls have been "
1296 "redirected.\n", nredirected
);
1299 /* If all callers was redirected, do not produce wrapper. */
1300 if (alias
->can_remove_if_no_direct_calls_p ()
1301 && !alias
->has_aliases_p ())
1303 create_wrapper
= false;
1306 gcc_assert (!create_alias
);
1308 else if (create_alias
)
1310 alias
->icf_merged
= true;
1312 /* Remove the function's body. */
1313 ipa_merge_profiles (original
, alias
);
1314 alias
->release_body (true);
1316 /* Notice global symbol possibly produced RTL. */
1317 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1320 /* Create the alias. */
1321 cgraph_node::create_alias (alias_func
->decl
, decl
);
1322 alias
->resolve_alias (original
);
1324 original
->call_for_symbol_thunks_and_aliases
1325 (set_local
, (void *)(size_t) original
->local_p (), true);
1328 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1332 gcc_assert (!create_alias
);
1333 alias
->icf_merged
= true;
1334 local_original
->icf_merged
= true;
1336 ipa_merge_profiles (local_original
, alias
, true);
1337 alias
->create_wrapper (local_original
);
1340 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1343 /* It's possible that redirection can hit thunks that block
1344 redirection opportunities. */
1345 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1346 original
->icf_merged
= true;
1348 /* Inform the inliner about cross-module merging. */
1349 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1350 && original
->lto_file_data
!= alias
->lto_file_data
)
1351 local_original
->merged
= original
->merged
= true;
1355 ipa_merge_profiles (original
, alias
);
1356 alias
->release_body ();
1358 alias
->body_removed
= true;
1359 alias
->icf_merged
= true;
1361 fprintf (dump_file
, "Unified; Function body was removed.\n");
1367 /* Semantic item initialization function. */
1370 sem_function::init (void)
1373 get_node ()->get_untransformed_body ();
1375 tree fndecl
= node
->decl
;
1376 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1379 gcc_assert (SSANAMES (func
));
1381 ssa_names_size
= SSANAMES (func
)->length ();
1385 region_tree
= func
->eh
->region_tree
;
1387 /* iterating all function arguments. */
1388 arg_count
= count_formal_params (fndecl
);
1390 edge_count
= n_edges_for_fn (func
);
1391 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1392 if (!cnode
->thunk
.thunk_p
)
1394 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1396 inchash::hash hstate
;
1399 FOR_EACH_BB_FN (bb
, func
)
1401 unsigned nondbg_stmt_count
= 0;
1404 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1406 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1409 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1412 gimple stmt
= gsi_stmt (gsi
);
1414 if (gimple_code (stmt
) != GIMPLE_DEBUG
1415 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1417 hash_stmt (stmt
, hstate
);
1418 nondbg_stmt_count
++;
1422 gcode_hash
= hstate
.end ();
1423 bb_sizes
.safe_push (nondbg_stmt_count
);
1425 /* Inserting basic block to hash table. */
1426 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1427 EDGE_COUNT (bb
->preds
)
1428 + EDGE_COUNT (bb
->succs
));
1430 bb_sorted
.safe_push (semantic_bb
);
1436 inchash::hash hstate
;
1437 hstate
.add_wide_int (cnode
->thunk
.fixed_offset
);
1438 hstate
.add_wide_int (cnode
->thunk
.virtual_value
);
1439 hstate
.add_flag (cnode
->thunk
.this_adjusting
);
1440 hstate
.add_flag (cnode
->thunk
.virtual_offset_p
);
1441 hstate
.add_flag (cnode
->thunk
.add_pointer_bounds_args
);
1442 gcode_hash
= hstate
.end ();
1448 /* Accumulate to HSTATE a hash of expression EXP.
1449 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1450 and DECL equality classes. */
1453 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1455 if (exp
== NULL_TREE
)
1457 hstate
.merge_hash (0);
1461 /* Handled component can be matched in a cureful way proving equivalence
1462 even if they syntactically differ. Just skip them. */
1464 while (handled_component_p (exp
))
1465 exp
= TREE_OPERAND (exp
, 0);
1467 enum tree_code code
= TREE_CODE (exp
);
1468 hstate
.add_int (code
);
1472 /* Use inchash::add_expr for everything that is LTO stable. */
1480 inchash::add_expr (exp
, hstate
);
1484 unsigned HOST_WIDE_INT idx
;
1487 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1489 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1491 add_expr (value
, hstate
);
1496 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1502 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1505 case POINTER_PLUS_EXPR
:
1508 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1509 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1513 inchash::hash one
, two
;
1514 add_expr (TREE_OPERAND (exp
, 0), one
);
1515 add_expr (TREE_OPERAND (exp
, 1), two
);
1516 hstate
.add_commutative (one
, two
);
1520 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1521 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1527 /* Accumulate to HSTATE a hash of type t.
1528 TYpes that may end up being compatible after LTO type merging needs to have
1532 sem_item::add_type (const_tree type
, inchash::hash
&hstate
)
1534 if (type
== NULL_TREE
)
1536 hstate
.merge_hash (0);
1540 type
= TYPE_MAIN_VARIANT (type
);
1541 if (TYPE_CANONICAL (type
))
1542 type
= TYPE_CANONICAL (type
);
1544 if (!AGGREGATE_TYPE_P (type
))
1545 hstate
.add_int (TYPE_MODE (type
));
1547 if (TREE_CODE (type
) == COMPLEX_TYPE
)
1549 hstate
.add_int (COMPLEX_TYPE
);
1550 sem_item::add_type (TREE_TYPE (type
), hstate
);
1552 else if (INTEGRAL_TYPE_P (type
))
1554 hstate
.add_int (INTEGER_TYPE
);
1555 hstate
.add_flag (TYPE_UNSIGNED (type
));
1556 hstate
.add_int (TYPE_PRECISION (type
));
1558 else if (VECTOR_TYPE_P (type
))
1560 hstate
.add_int (VECTOR_TYPE
);
1561 hstate
.add_int (TYPE_PRECISION (type
));
1562 sem_item::add_type (TREE_TYPE (type
), hstate
);
1564 else if (TREE_CODE (type
) == ARRAY_TYPE
)
1566 hstate
.add_int (ARRAY_TYPE
);
1567 /* Do not hash size, so complete and incomplete types can match. */
1568 sem_item::add_type (TREE_TYPE (type
), hstate
);
1570 else if (RECORD_OR_UNION_TYPE_P (type
))
1572 hashval_t
*val
= optimizer
->m_type_hash_cache
.get (type
);
1576 inchash::hash hstate2
;
1581 hstate2
.add_int (RECORD_TYPE
);
1582 gcc_assert (COMPLETE_TYPE_P (type
));
1584 for (f
= TYPE_FIELDS (type
), nf
= 0; f
; f
= TREE_CHAIN (f
))
1585 if (TREE_CODE (f
) == FIELD_DECL
)
1587 add_type (TREE_TYPE (f
), hstate2
);
1591 hstate2
.add_int (nf
);
1592 hash
= hstate2
.end ();
1593 hstate
.add_wide_int (hash
);
1594 optimizer
->m_type_hash_cache
.put (type
, hash
);
1597 hstate
.add_wide_int (*val
);
1601 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1604 sem_function::hash_stmt (gimple stmt
, inchash::hash
&hstate
)
1606 enum gimple_code code
= gimple_code (stmt
);
1608 hstate
.add_int (code
);
1613 add_expr (gimple_switch_index (as_a
<gswitch
*> (stmt
)), hstate
);
1616 hstate
.add_int (gimple_assign_rhs_code (stmt
));
1617 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1618 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1620 inchash::hash one
, two
;
1622 add_expr (gimple_assign_rhs1 (stmt
), one
);
1623 add_type (TREE_TYPE (gimple_assign_rhs1 (stmt
)), one
);
1624 add_expr (gimple_assign_rhs2 (stmt
), two
);
1625 hstate
.add_commutative (one
, two
);
1626 if (commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1628 add_expr (gimple_assign_rhs3 (stmt
), hstate
);
1629 add_type (TREE_TYPE (gimple_assign_rhs3 (stmt
)), hstate
);
1631 add_expr (gimple_assign_lhs (stmt
), hstate
);
1632 add_type (TREE_TYPE (gimple_assign_lhs (stmt
)), two
);
1635 /* ... fall through ... */
1641 /* All these statements are equivalent if their operands are. */
1642 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1644 add_expr (gimple_op (stmt
, i
), hstate
);
1645 if (gimple_op (stmt
, i
))
1646 add_type (TREE_TYPE (gimple_op (stmt
, i
)), hstate
);
1654 /* Return true if polymorphic comparison must be processed. */
1657 sem_function::compare_polymorphic_p (void)
1659 struct cgraph_edge
*e
;
1661 if (!opt_for_fn (get_node ()->decl
, flag_devirtualize
))
1663 if (get_node ()->indirect_calls
!= NULL
)
1665 /* TODO: We can do simple propagation determining what calls may lead to
1666 a polymorphic call. */
1667 for (e
= get_node ()->callees
; e
; e
= e
->next_callee
)
1668 if (e
->callee
->definition
1669 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1674 /* For a given call graph NODE, the function constructs new
1675 semantic function item. */
1678 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1680 tree fndecl
= node
->decl
;
1681 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1683 if (!func
|| (!node
->has_gimple_body_p () && !node
->thunk
.thunk_p
))
1686 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1689 sem_function
*f
= new sem_function (node
, 0, stack
);
1696 /* Parses function arguments and result type. */
1699 sem_function::parse_tree_args (void)
1703 if (arg_types
.exists ())
1704 arg_types
.release ();
1706 arg_types
.create (4);
1707 tree fnargs
= DECL_ARGUMENTS (decl
);
1709 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
1710 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
1712 /* Function result type. */
1713 result
= DECL_RESULT (decl
);
1714 result_type
= result
? TREE_TYPE (result
) : NULL
;
1716 /* During WPA, we can get arguments by following method. */
1719 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
1720 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
1721 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
1723 result_type
= TREE_TYPE (TREE_TYPE (decl
));
1727 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1728 return true if phi nodes are semantically equivalent in these blocks . */
1731 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1733 gphi_iterator si1
, si2
;
1735 unsigned size1
, size2
, i
;
1739 gcc_assert (bb1
!= NULL
);
1740 gcc_assert (bb2
!= NULL
);
1742 si2
= gsi_start_phis (bb2
);
1743 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1746 gsi_next_nonvirtual_phi (&si1
);
1747 gsi_next_nonvirtual_phi (&si2
);
1749 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1752 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1753 return return_false();
1758 tree phi_result1
= gimple_phi_result (phi1
);
1759 tree phi_result2
= gimple_phi_result (phi2
);
1761 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1762 return return_false_with_msg ("PHI results are different");
1764 size1
= gimple_phi_num_args (phi1
);
1765 size2
= gimple_phi_num_args (phi2
);
1768 return return_false ();
1770 for (i
= 0; i
< size1
; ++i
)
1772 t1
= gimple_phi_arg (phi1
, i
)->def
;
1773 t2
= gimple_phi_arg (phi2
, i
)->def
;
1775 if (!m_checker
->compare_operand (t1
, t2
))
1776 return return_false ();
1778 e1
= gimple_phi_arg_edge (phi1
, i
);
1779 e2
= gimple_phi_arg_edge (phi2
, i
);
1781 if (!m_checker
->compare_edge (e1
, e2
))
1782 return return_false ();
1791 /* Returns true if tree T can be compared as a handled component. */
1794 sem_function::icf_handled_component_p (tree t
)
1796 tree_code tc
= TREE_CODE (t
);
1798 return (handled_component_p (t
)
1799 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== OBJ_TYPE_REF
);
1802 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1803 corresponds to TARGET. */
1806 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1811 if (bb_dict
->length () <= (unsigned)source
)
1812 bb_dict
->safe_grow_cleared (source
+ 1);
1814 if ((*bb_dict
)[source
] == 0)
1816 (*bb_dict
)[source
] = target
;
1820 return (*bb_dict
)[source
] == target
;
1824 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1826 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1830 /* Constructor based on varpool node _NODE with computed hash _HASH.
1831 Bitmap STACK is used for memory allocation. */
1833 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1834 bitmap_obstack
*stack
): sem_item(VAR
,
1837 gcc_checking_assert (node
);
1838 gcc_checking_assert (get_node ());
1841 /* Fast equality function based on knowledge known in WPA. */
1844 sem_variable::equals_wpa (sem_item
*item
,
1845 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1847 gcc_assert (item
->type
== VAR
);
1849 if (node
->num_references () != item
->node
->num_references ())
1850 return return_false_with_msg ("different number of references");
1852 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1853 return return_false_with_msg ("TLS model");
1855 /* DECL_ALIGN is safe to merge, because we will always chose the largest
1856 alignment out of all aliases. */
1858 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1859 return return_false_with_msg ("Virtual flag mismatch");
1861 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1862 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1863 || !operand_equal_p (DECL_SIZE (decl
),
1864 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1865 return return_false_with_msg ("size mismatch");
1867 /* Do not attempt to mix data from different user sections;
1868 we do not know what user intends with those. */
1869 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1870 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1871 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1872 return return_false_with_msg ("user section mismatch");
1874 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1875 return return_false_with_msg ("text section");
1877 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1878 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1880 item
->node
->iterate_reference (i
, ref2
);
1882 if (ref
->use
!= ref2
->use
)
1883 return return_false_with_msg ("reference use mismatch");
1885 if (!compare_symbol_references (ignored_nodes
,
1886 ref
->referred
, ref2
->referred
,
1887 ref
->address_matters_p ()))
1894 /* Returns true if the item equals to ITEM given as argument. */
1897 sem_variable::equals (sem_item
*item
,
1898 hash_map
<symtab_node
*, sem_item
*> &)
1900 gcc_assert (item
->type
== VAR
);
1903 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1904 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1905 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1906 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1908 /* As seen in PR ipa/65303 we have to compare variables types. */
1909 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1910 TREE_TYPE (item
->decl
)))
1911 return return_false_with_msg ("variables types are different");
1913 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1914 DECL_INITIAL (item
->node
->decl
));
1915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1917 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1918 xstrdup_for_dump (node
->name()),
1919 xstrdup_for_dump (item
->node
->name ()),
1920 node
->order
, item
->node
->order
,
1921 xstrdup_for_dump (node
->asm_name ()),
1922 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1927 /* Compares trees T1 and T2 for semantic equality. */
1930 sem_variable::equals (tree t1
, tree t2
)
1933 return return_with_debug (t1
== t2
);
1936 tree_code tc1
= TREE_CODE (t1
);
1937 tree_code tc2
= TREE_CODE (t2
);
1940 return return_false_with_msg ("TREE_CODE mismatch");
1946 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1947 unsigned HOST_WIDE_INT idx
;
1949 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1950 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1951 return return_false_with_msg ("constructor type mismatch");
1953 if (typecode
== ARRAY_TYPE
)
1955 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1956 /* For arrays, check that the sizes all match. */
1957 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1959 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1960 return return_false_with_msg ("constructor array size mismatch");
1962 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1964 return return_false_with_msg ("constructor type incompatible");
1966 v1
= CONSTRUCTOR_ELTS (t1
);
1967 v2
= CONSTRUCTOR_ELTS (t2
);
1968 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1969 return return_false_with_msg ("constructor number of elts mismatch");
1971 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1973 constructor_elt
*c1
= &(*v1
)[idx
];
1974 constructor_elt
*c2
= &(*v2
)[idx
];
1976 /* Check that each value is the same... */
1977 if (!sem_variable::equals (c1
->value
, c2
->value
))
1979 /* ... and that they apply to the same fields! */
1980 if (!sem_variable::equals (c1
->index
, c2
->index
))
1987 tree x1
= TREE_OPERAND (t1
, 0);
1988 tree x2
= TREE_OPERAND (t2
, 0);
1989 tree y1
= TREE_OPERAND (t1
, 1);
1990 tree y2
= TREE_OPERAND (t2
, 1);
1992 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1993 return return_false ();
1995 /* Type of the offset on MEM_REF does not matter. */
1996 return return_with_debug (sem_variable::equals (x1
, x2
)
1997 && wi::to_offset (y1
)
1998 == wi::to_offset (y2
));
2003 tree op1
= TREE_OPERAND (t1
, 0);
2004 tree op2
= TREE_OPERAND (t2
, 0);
2005 return sem_variable::equals (op1
, op2
);
2007 /* References to other vars/decls are compared using ipa-ref. */
2010 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
2012 return return_false_with_msg ("Declaration mismatch");
2014 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
2015 need to process its VAR/FUNCTION references without relying on ipa-ref
2019 return return_false_with_msg ("Declaration mismatch");
2021 /* Integer constants are the same only if the same width of type. */
2022 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2023 return return_false_with_msg ("INTEGER_CST precision mismatch");
2024 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2025 return return_false_with_msg ("INTEGER_CST mode mismatch");
2026 return return_with_debug (tree_int_cst_equal (t1
, t2
));
2028 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
2029 return return_false_with_msg ("STRING_CST mode mismatch");
2030 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
2031 return return_false_with_msg ("STRING_CST length mismatch");
2032 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
2033 TREE_STRING_LENGTH (t1
)))
2034 return return_false_with_msg ("STRING_CST mismatch");
2037 /* Fixed constants are the same only if the same width of type. */
2038 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2039 return return_false_with_msg ("FIXED_CST precision mismatch");
2041 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
2042 TREE_FIXED_CST (t2
)));
2044 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
2045 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
2047 /* Real constants are the same only if the same width of type. */
2048 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
2049 return return_false_with_msg ("REAL_CST precision mismatch");
2050 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1
),
2051 TREE_REAL_CST (t2
)));
2056 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
2057 return return_false_with_msg ("VECTOR_CST nelts mismatch");
2059 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
2060 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
2061 VECTOR_CST_ELT (t2
, i
)))
2067 case ARRAY_RANGE_REF
:
2069 tree x1
= TREE_OPERAND (t1
, 0);
2070 tree x2
= TREE_OPERAND (t2
, 0);
2071 tree y1
= TREE_OPERAND (t1
, 1);
2072 tree y2
= TREE_OPERAND (t2
, 1);
2074 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
2076 if (!sem_variable::equals (array_ref_low_bound (t1
),
2077 array_ref_low_bound (t2
)))
2079 if (!sem_variable::equals (array_ref_element_size (t1
),
2080 array_ref_element_size (t2
)))
2086 case POINTER_PLUS_EXPR
:
2091 tree x1
= TREE_OPERAND (t1
, 0);
2092 tree x2
= TREE_OPERAND (t2
, 0);
2093 tree y1
= TREE_OPERAND (t1
, 1);
2094 tree y2
= TREE_OPERAND (t2
, 1);
2096 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
2100 case VIEW_CONVERT_EXPR
:
2101 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
2102 return return_false ();
2103 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
2105 return return_false_with_msg ("ERROR_MARK");
2107 return return_false_with_msg ("Unknown TREE code reached");
2111 /* Parser function that visits a varpool NODE. */
2114 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
2116 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
2120 sem_variable
*v
= new sem_variable (node
, 0, stack
);
2127 /* References independent hash function. */
2130 sem_variable::get_hash (void)
2135 /* All WPA streamed in symbols should have their hashes computed at compile
2136 time. At this point, the constructor may not be in memory at all.
2137 DECL_INITIAL (decl) would be error_mark_node in that case. */
2138 gcc_assert (!node
->lto_file_data
);
2139 tree ctor
= DECL_INITIAL (decl
);
2140 inchash::hash hstate
;
2142 hstate
.add_int (456346417);
2143 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
2144 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
2145 add_expr (ctor
, hstate
);
2146 hash
= hstate
.end ();
2151 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
2155 sem_variable::merge (sem_item
*alias_item
)
2157 gcc_assert (alias_item
->type
== VAR
);
2159 if (!sem_item::target_supports_symbol_aliases_p ())
2162 fprintf (dump_file
, "Not unifying; "
2163 "Symbol aliases are not supported by target\n\n");
2167 if (DECL_EXTERNAL (alias_item
->decl
))
2170 fprintf (dump_file
, "Not unifying; alias is external.\n\n");
2174 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
2176 varpool_node
*original
= get_node ();
2177 varpool_node
*alias
= alias_var
->get_node ();
2178 bool original_discardable
= false;
2180 bool original_address_matters
= original
->address_matters_p ();
2181 bool alias_address_matters
= alias
->address_matters_p ();
2183 /* See if original is in a section that can be discarded if the main
2185 Also consider case where we have resolution info and we know that
2186 original's definition is not going to be used. In this case we can not
2187 create alias to original. */
2188 if (original
->can_be_discarded_p ()
2189 || (node
->resolution
!= LDPR_UNKNOWN
2190 && !decl_binds_to_current_def_p (node
->decl
)))
2191 original_discardable
= true;
2193 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
2195 /* Constant pool machinery is not quite ready for aliases.
2196 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
2197 For LTO merging does not happen that is an important missing feature.
2198 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
2199 flag is dropped and non-local symbol name is assigned. */
2200 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
2201 || DECL_IN_CONSTANT_POOL (original
->decl
))
2205 "Not unifying; constant pool variables.\n\n");
2209 /* Do not attempt to mix functions from different user sections;
2210 we do not know what user intends with those. */
2211 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
2212 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
2213 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
2218 "original and alias are in different sections.\n\n");
2222 /* We can not merge if address comparsion metters. */
2223 if (original_address_matters
&& alias_address_matters
2224 && flag_merge_constants
< 2)
2229 "adress of original and alias may be compared.\n\n");
2232 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
2235 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2236 "across comdat group boundary\n\n");
2241 if (original_discardable
)
2244 fprintf (dump_file
, "Not unifying; alias cannot be created; "
2245 "target is discardable\n\n");
2251 gcc_assert (!original
->alias
);
2252 gcc_assert (!alias
->alias
);
2254 alias
->analyzed
= false;
2256 DECL_INITIAL (alias
->decl
) = NULL
;
2257 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
2259 alias
->need_bounds_init
= false;
2260 alias
->remove_all_references ();
2261 if (TREE_ADDRESSABLE (alias
->decl
))
2262 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
2264 varpool_node::create_alias (alias_var
->decl
, decl
);
2265 alias
->resolve_alias (original
);
2268 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
2274 /* Dump symbol to FILE. */
2277 sem_variable::dump_to_file (FILE *file
)
2281 print_node (file
, "", decl
, 0);
2282 fprintf (file
, "\n\n");
2285 unsigned int sem_item_optimizer::class_id
= 0;
2287 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
2288 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
2291 bitmap_obstack_initialize (&m_bmstack
);
2294 sem_item_optimizer::~sem_item_optimizer ()
2296 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
2299 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2300 it
!= m_classes
.end (); ++it
)
2302 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2303 delete (*it
)->classes
[i
];
2305 (*it
)->classes
.release ();
2311 bitmap_obstack_release (&m_bmstack
);
2314 /* Write IPA ICF summary for symbols. */
2317 sem_item_optimizer::write_summary (void)
2319 unsigned int count
= 0;
2321 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
2322 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
2325 /* Calculate number of symbols to be serialized. */
2326 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2328 lsei_next_in_partition (&lsei
))
2330 symtab_node
*node
= lsei_node (lsei
);
2332 if (m_symtab_node_map
.get (node
))
2336 streamer_write_uhwi (ob
, count
);
2338 /* Process all of the symbols. */
2339 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
2341 lsei_next_in_partition (&lsei
))
2343 symtab_node
*node
= lsei_node (lsei
);
2345 sem_item
**item
= m_symtab_node_map
.get (node
);
2349 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
2350 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
2352 streamer_write_uhwi (ob
, (*item
)->get_hash ());
2356 streamer_write_char_stream (ob
->main_stream
, 0);
2357 produce_asm (ob
, NULL
);
2358 destroy_output_block (ob
);
2361 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
2362 contains LEN bytes. */
2365 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
2366 const char *data
, size_t len
)
2368 const lto_function_header
*header
=
2369 (const lto_function_header
*) data
;
2370 const int cfg_offset
= sizeof (lto_function_header
);
2371 const int main_offset
= cfg_offset
+ header
->cfg_size
;
2372 const int string_offset
= main_offset
+ header
->main_size
;
2377 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
2378 header
->main_size
, file_data
->mode_table
);
2381 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
2382 header
->string_size
, vNULL
);
2384 count
= streamer_read_uhwi (&ib_main
);
2386 for (i
= 0; i
< count
; i
++)
2390 lto_symtab_encoder_t encoder
;
2392 index
= streamer_read_uhwi (&ib_main
);
2393 encoder
= file_data
->symtab_node_encoder
;
2394 node
= lto_symtab_encoder_deref (encoder
, index
);
2396 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2398 gcc_assert (node
->definition
);
2401 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2402 node
->asm_name (), (void *) node
->decl
, node
->order
);
2404 if (is_a
<cgraph_node
*> (node
))
2406 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2408 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2412 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2414 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2418 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2420 lto_data_in_delete (data_in
);
2423 /* Read IPA IPA ICF summary for symbols. */
2426 sem_item_optimizer::read_summary (void)
2428 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2429 lto_file_decl_data
*file_data
;
2432 while ((file_data
= file_data_vec
[j
++]))
2435 const char *data
= lto_get_section_data (file_data
,
2436 LTO_section_ipa_icf
, NULL
, &len
);
2439 read_section (file_data
, data
, len
);
2443 /* Register callgraph and varpool hooks. */
2446 sem_item_optimizer::register_hooks (void)
2448 if (!m_cgraph_node_hooks
)
2449 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2450 (&sem_item_optimizer::cgraph_removal_hook
, this);
2452 if (!m_varpool_node_hooks
)
2453 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2454 (&sem_item_optimizer::varpool_removal_hook
, this);
2457 /* Unregister callgraph and varpool hooks. */
2460 sem_item_optimizer::unregister_hooks (void)
2462 if (m_cgraph_node_hooks
)
2463 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2465 if (m_varpool_node_hooks
)
2466 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2469 /* Adds a CLS to hashtable associated by hash value. */
2472 sem_item_optimizer::add_class (congruence_class
*cls
)
2474 gcc_assert (cls
->members
.length ());
2476 congruence_class_group
*group
= get_group_by_hash (
2477 cls
->members
[0]->get_hash (),
2478 cls
->members
[0]->type
);
2479 group
->classes
.safe_push (cls
);
2482 /* Gets a congruence class group based on given HASH value and TYPE. */
2484 congruence_class_group
*
2485 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2487 congruence_class_group
*item
= XNEW (congruence_class_group
);
2491 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2497 item
->classes
.create (1);
2504 /* Callgraph removal hook called for a NODE with a custom DATA. */
2507 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2509 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2510 optimizer
->remove_symtab_node (node
);
2513 /* Varpool removal hook called for a NODE with a custom DATA. */
2516 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2518 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2519 optimizer
->remove_symtab_node (node
);
2522 /* Remove symtab NODE triggered by symtab removal hooks. */
2525 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2527 gcc_assert (!m_classes
.elements());
2529 m_removed_items_set
.add (node
);
2533 sem_item_optimizer::remove_item (sem_item
*item
)
2535 if (m_symtab_node_map
.get (item
->node
))
2536 m_symtab_node_map
.remove (item
->node
);
2540 /* Removes all callgraph and varpool nodes that are marked by symtab
2544 sem_item_optimizer::filter_removed_items (void)
2546 auto_vec
<sem_item
*> filtered
;
2548 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2550 sem_item
*item
= m_items
[i
];
2552 if (m_removed_items_set
.contains (item
->node
))
2558 if (item
->type
== FUNC
)
2560 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2562 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2565 filtered
.safe_push (item
);
2569 if (!flag_ipa_icf_variables
)
2573 /* Filter out non-readonly variables. */
2574 tree decl
= item
->decl
;
2575 if (TREE_READONLY (decl
))
2576 filtered
.safe_push (item
);
2583 /* Clean-up of released semantic items. */
2586 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2587 m_items
.safe_push (filtered
[i
]);
2590 /* Optimizer entry point which returns true in case it processes
2591 a merge operation. True is returned if there's a merge operation
2595 sem_item_optimizer::execute (void)
2597 filter_removed_items ();
2598 unregister_hooks ();
2601 update_hash_by_addr_refs ();
2602 build_hash_based_classes ();
2605 fprintf (dump_file
, "Dump after hash based groups\n");
2606 dump_cong_classes ();
2608 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2609 m_items
[i
]->init_wpa ();
2611 subdivide_classes_by_equality (true);
2614 fprintf (dump_file
, "Dump after WPA based types groups\n");
2616 dump_cong_classes ();
2618 process_cong_reduction ();
2622 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2624 dump_cong_classes ();
2626 parse_nonsingleton_classes ();
2627 subdivide_classes_by_equality ();
2630 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2632 dump_cong_classes ();
2634 unsigned int prev_class_count
= m_classes_count
;
2636 process_cong_reduction ();
2637 dump_cong_classes ();
2639 bool merged_p
= merge_classes (prev_class_count
);
2641 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2642 symtab_node::dump_table (dump_file
);
2647 /* Function responsible for visiting all potential functions and
2648 read-only variables that can be merged. */
2651 sem_item_optimizer::parse_funcs_and_vars (void)
2655 if (flag_ipa_icf_functions
)
2656 FOR_EACH_DEFINED_FUNCTION (cnode
)
2658 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2661 m_items
.safe_push (f
);
2662 m_symtab_node_map
.put (cnode
, f
);
2665 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2667 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2668 f
->dump_to_file (dump_file
);
2671 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2674 varpool_node
*vnode
;
2676 if (flag_ipa_icf_variables
)
2677 FOR_EACH_DEFINED_VARIABLE (vnode
)
2679 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2683 m_items
.safe_push (v
);
2684 m_symtab_node_map
.put (vnode
, v
);
2689 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2692 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2694 item
->index_in_class
= cls
->members
.length ();
2695 cls
->members
.safe_push (item
);
2699 /* For each semantic item, append hash values of references. */
2702 sem_item_optimizer::update_hash_by_addr_refs ()
2704 /* First, append to hash sensitive references and class type if it need to
2705 be matched for ODR. */
2706 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2708 m_items
[i
]->update_hash_by_addr_refs (m_symtab_node_map
);
2709 if (m_items
[i
]->type
== FUNC
)
2711 if (TREE_CODE (TREE_TYPE (m_items
[i
]->decl
)) == METHOD_TYPE
2712 && contains_polymorphic_type_p
2713 (TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
)))
2714 && (DECL_CXX_CONSTRUCTOR_P (m_items
[i
]->decl
)
2715 || (static_cast<sem_function
*> (m_items
[i
])->param_used_p (0)
2716 && static_cast<sem_function
*> (m_items
[i
])
2717 ->compare_polymorphic_p ())))
2720 = TYPE_METHOD_BASETYPE (TREE_TYPE (m_items
[i
]->decl
));
2721 inchash::hash
hstate (m_items
[i
]->hash
);
2723 if (TYPE_NAME (class_type
)
2724 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (class_type
)))
2726 (IDENTIFIER_HASH_VALUE
2727 (DECL_ASSEMBLER_NAME (TYPE_NAME (class_type
))));
2729 m_items
[i
]->hash
= hstate
.end ();
2734 /* Once all symbols have enhanced hash value, we can append
2735 hash values of symbols that are seen by IPA ICF and are
2736 references by a semantic item. Newly computed values
2737 are saved to global_hash member variable. */
2738 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2739 m_items
[i
]->update_hash_by_local_refs (m_symtab_node_map
);
2741 /* Global hash value replace current hash values. */
2742 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2743 m_items
[i
]->hash
= m_items
[i
]->global_hash
;
2746 /* Congruence classes are built by hash value. */
2749 sem_item_optimizer::build_hash_based_classes (void)
2751 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2753 sem_item
*item
= m_items
[i
];
2755 congruence_class_group
*group
= get_group_by_hash (item
->hash
,
2758 if (!group
->classes
.length ())
2761 group
->classes
.safe_push (new congruence_class (class_id
++));
2764 add_item_to_class (group
->classes
[0], item
);
2768 /* Build references according to call graph. */
2771 sem_item_optimizer::build_graph (void)
2773 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2775 sem_item
*item
= m_items
[i
];
2776 m_symtab_node_map
.put (item
->node
, item
);
2779 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2781 sem_item
*item
= m_items
[i
];
2783 if (item
->type
== FUNC
)
2785 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2787 cgraph_edge
*e
= cnode
->callees
;
2790 sem_item
**slot
= m_symtab_node_map
.get
2791 (e
->callee
->ultimate_alias_target ());
2793 item
->add_reference (*slot
);
2799 ipa_ref
*ref
= NULL
;
2800 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2802 sem_item
**slot
= m_symtab_node_map
.get
2803 (ref
->referred
->ultimate_alias_target ());
2805 item
->add_reference (*slot
);
2810 /* Semantic items in classes having more than one element and initialized.
2811 In case of WPA, we load function body. */
2814 sem_item_optimizer::parse_nonsingleton_classes (void)
2816 unsigned int init_called_count
= 0;
2818 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2819 if (m_items
[i
]->cls
->members
.length () > 1)
2821 m_items
[i
]->init ();
2822 init_called_count
++;
2826 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2827 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2830 /* Equality function for semantic items is used to subdivide existing
2831 classes. If IN_WPA, fast equality function is invoked. */
2834 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2836 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2837 it
!= m_classes
.end (); ++it
)
2839 unsigned int class_count
= (*it
)->classes
.length ();
2841 for (unsigned i
= 0; i
< class_count
; i
++)
2843 congruence_class
*c
= (*it
)->classes
[i
];
2845 if (c
->members
.length() > 1)
2847 auto_vec
<sem_item
*> new_vector
;
2849 sem_item
*first
= c
->members
[0];
2850 new_vector
.safe_push (first
);
2852 unsigned class_split_first
= (*it
)->classes
.length ();
2854 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2856 sem_item
*item
= c
->members
[j
];
2858 bool equals
= in_wpa
? first
->equals_wpa (item
,
2859 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2862 new_vector
.safe_push (item
);
2865 bool integrated
= false;
2867 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2869 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2870 bool equals
= in_wpa
? x
->equals_wpa (item
,
2871 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2876 add_item_to_class ((*it
)->classes
[k
], item
);
2884 congruence_class
*c
= new congruence_class (class_id
++);
2886 add_item_to_class (c
, item
);
2888 (*it
)->classes
.safe_push (c
);
2893 // we replace newly created new_vector for the class we've just splitted
2894 c
->members
.release ();
2895 c
->members
.create (new_vector
.length ());
2897 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2898 add_item_to_class (c
, new_vector
[j
]);
2906 /* Subdivide classes by address references that members of the class
2907 reference. Example can be a pair of functions that have an address
2908 taken from a function. If these addresses are different the class
2912 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2914 typedef hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2915 symbol_compare_hashmap_traits
> subdivide_hash_map
;
2917 unsigned newly_created_classes
= 0;
2919 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2920 it
!= m_classes
.end (); ++it
)
2922 unsigned int class_count
= (*it
)->classes
.length ();
2923 auto_vec
<congruence_class
*> new_classes
;
2925 for (unsigned i
= 0; i
< class_count
; i
++)
2927 congruence_class
*c
= (*it
)->classes
[i
];
2929 if (c
->members
.length() > 1)
2931 subdivide_hash_map split_map
;
2933 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2935 sem_item
*source_node
= c
->members
[j
];
2937 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2940 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
,
2942 gcc_checking_assert (slot
);
2944 slot
->safe_push (source_node
);
2950 /* If the map contains more than one key, we have to split the map
2952 if (split_map
.elements () != 1)
2954 bool first_class
= true;
2956 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2957 it2
!= split_map
.end (); ++it2
)
2959 congruence_class
*new_cls
;
2960 new_cls
= new congruence_class (class_id
++);
2962 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2963 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2965 worklist_push (new_cls
);
2966 newly_created_classes
++;
2970 (*it
)->classes
[i
] = new_cls
;
2971 first_class
= false;
2975 new_classes
.safe_push (new_cls
);
2981 /* Release memory. */
2982 for (subdivide_hash_map::iterator it2
= split_map
.begin ();
2983 it2
!= split_map
.end (); ++it2
)
2985 delete (*it2
).first
;
2986 (*it2
).second
.release ();
2991 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2992 (*it
)->classes
.safe_push (new_classes
[i
]);
2995 return newly_created_classes
;
2998 /* Verify congruence classes if checking is enabled. */
3001 sem_item_optimizer::verify_classes (void)
3004 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3005 it
!= m_classes
.end (); ++it
)
3007 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3009 congruence_class
*cls
= (*it
)->classes
[i
];
3011 gcc_checking_assert (cls
);
3012 gcc_checking_assert (cls
->members
.length () > 0);
3014 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
3016 sem_item
*item
= cls
->members
[j
];
3018 gcc_checking_assert (item
);
3019 gcc_checking_assert (item
->cls
== cls
);
3021 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
3023 sem_usage_pair
*usage
= item
->usages
[k
];
3024 gcc_checking_assert (usage
->item
->index_in_class
<
3025 usage
->item
->cls
->members
.length ());
3033 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
3034 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
3035 but unused argument. */
3038 sem_item_optimizer::release_split_map (congruence_class
* const &,
3039 bitmap
const &b
, traverse_split_pair
*)
3048 /* Process split operation for a class given as pointer CLS_PTR,
3049 where bitmap B splits congruence class members. DATA is used
3050 as argument of split pair. */
3053 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
3054 bitmap
const &b
, traverse_split_pair
*pair
)
3056 sem_item_optimizer
*optimizer
= pair
->optimizer
;
3057 const congruence_class
*splitter_cls
= pair
->cls
;
3059 /* If counted bits are greater than zero and less than the number of members
3060 a group will be splitted. */
3061 unsigned popcount
= bitmap_count_bits (b
);
3063 if (popcount
> 0 && popcount
< cls
->members
.length ())
3065 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
3067 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3069 int target
= bitmap_bit_p (b
, i
);
3070 congruence_class
*tc
= newclasses
[target
];
3072 add_item_to_class (tc
, cls
->members
[i
]);
3075 #ifdef ENABLE_CHECKING
3076 for (unsigned int i
= 0; i
< 2; i
++)
3077 gcc_checking_assert (newclasses
[i
]->members
.length ());
3080 if (splitter_cls
== cls
)
3081 optimizer
->splitter_class_removed
= true;
3083 /* Remove old class from worklist if presented. */
3084 bool in_worklist
= cls
->in_worklist
;
3087 cls
->in_worklist
= false;
3089 congruence_class_group g
;
3090 g
.hash
= cls
->members
[0]->get_hash ();
3091 g
.type
= cls
->members
[0]->type
;
3093 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
3095 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
3096 if (slot
->classes
[i
] == cls
)
3098 slot
->classes
.ordered_remove (i
);
3102 /* New class will be inserted and integrated to work list. */
3103 for (unsigned int i
= 0; i
< 2; i
++)
3104 optimizer
->add_class (newclasses
[i
]);
3106 /* Two classes replace one, so that increment just by one. */
3107 optimizer
->m_classes_count
++;
3109 /* If OLD class was presented in the worklist, we remove the class
3110 and replace it will both newly created classes. */
3112 for (unsigned int i
= 0; i
< 2; i
++)
3113 optimizer
->worklist_push (newclasses
[i
]);
3114 else /* Just smaller class is inserted. */
3116 unsigned int smaller_index
= newclasses
[0]->members
.length () <
3117 newclasses
[1]->members
.length () ?
3119 optimizer
->worklist_push (newclasses
[smaller_index
]);
3122 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3124 fprintf (dump_file
, " congruence class splitted:\n");
3125 cls
->dump (dump_file
, 4);
3127 fprintf (dump_file
, " newly created groups:\n");
3128 for (unsigned int i
= 0; i
< 2; i
++)
3129 newclasses
[i
]->dump (dump_file
, 4);
3132 /* Release class if not presented in work list. */
3141 /* Tests if a class CLS used as INDEXth splits any congruence classes.
3142 Bitmap stack BMSTACK is used for bitmap allocation. */
3145 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
3148 hash_map
<congruence_class
*, bitmap
> split_map
;
3150 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3152 sem_item
*item
= cls
->members
[i
];
3154 /* Iterate all usages that have INDEX as usage of the item. */
3155 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
3157 sem_usage_pair
*usage
= item
->usages
[j
];
3159 if (usage
->index
!= index
)
3162 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
3167 b
= BITMAP_ALLOC (&m_bmstack
);
3168 split_map
.put (usage
->item
->cls
, b
);
3174 gcc_checking_assert (usage
->item
->cls
);
3175 gcc_checking_assert (usage
->item
->index_in_class
<
3176 usage
->item
->cls
->members
.length ());
3179 bitmap_set_bit (b
, usage
->item
->index_in_class
);
3183 traverse_split_pair pair
;
3184 pair
.optimizer
= this;
3187 splitter_class_removed
= false;
3189 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
3191 /* Bitmap clean-up. */
3193 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
3196 /* Every usage of a congruence class CLS is a candidate that can split the
3197 collection of classes. Bitmap stack BMSTACK is used for bitmap
3201 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
3206 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
3208 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
3209 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
3211 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
3213 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3214 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
3217 do_congruence_step_for_index (cls
, i
);
3219 if (splitter_class_removed
)
3223 BITMAP_FREE (usage
);
3226 /* Adds a newly created congruence class CLS to worklist. */
3229 sem_item_optimizer::worklist_push (congruence_class
*cls
)
3231 /* Return if the class CLS is already presented in work list. */
3232 if (cls
->in_worklist
)
3235 cls
->in_worklist
= true;
3236 worklist
.push_back (cls
);
3239 /* Pops a class from worklist. */
3242 sem_item_optimizer::worklist_pop (void)
3244 congruence_class
*cls
;
3246 while (!worklist
.empty ())
3248 cls
= worklist
.front ();
3249 worklist
.pop_front ();
3250 if (cls
->in_worklist
)
3252 cls
->in_worklist
= false;
3258 /* Work list item was already intended to be removed.
3259 The only reason for doing it is to split a class.
3260 Thus, the class CLS is deleted. */
3268 /* Iterative congruence reduction function. */
3271 sem_item_optimizer::process_cong_reduction (void)
3273 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3274 it
!= m_classes
.end (); ++it
)
3275 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3276 if ((*it
)->classes
[i
]->is_class_used ())
3277 worklist_push ((*it
)->classes
[i
]);
3280 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
3281 (unsigned long) worklist
.size ());
3283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3284 fprintf (dump_file
, "Congruence class reduction\n");
3286 congruence_class
*cls
;
3288 /* Process complete congruence reduction. */
3289 while ((cls
= worklist_pop ()) != NULL
)
3290 do_congruence_step (cls
);
3292 /* Subdivide newly created classes according to references. */
3293 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
3296 fprintf (dump_file
, "Address reference subdivision created: %u "
3297 "new classes.\n", new_classes
);
3300 /* Debug function prints all informations about congruence classes. */
3303 sem_item_optimizer::dump_cong_classes (void)
3309 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
3310 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
3312 /* Histogram calculation. */
3313 unsigned int max_index
= 0;
3314 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
3316 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3317 it
!= m_classes
.end (); ++it
)
3319 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3321 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
3329 "Class size histogram [num of members]: number of classe number of classess\n");
3331 for (unsigned int i
= 0; i
<= max_index
; i
++)
3333 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
3335 fprintf (dump_file
, "\n\n");
3338 if (dump_flags
& TDF_DETAILS
)
3339 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3340 it
!= m_classes
.end (); ++it
)
3342 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
3344 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
3346 (*it
)->classes
[i
]->dump (dump_file
, 4);
3348 if(i
< (*it
)->classes
.length () - 1)
3349 fprintf (dump_file
, " ");
3356 /* After reduction is done, we can declare all items in a group
3357 to be equal. PREV_CLASS_COUNT is start number of classes
3358 before reduction. True is returned if there's a merge operation
3362 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
3364 unsigned int item_count
= m_items
.length ();
3365 unsigned int class_count
= m_classes_count
;
3366 unsigned int equal_items
= item_count
- class_count
;
3368 unsigned int non_singular_classes_count
= 0;
3369 unsigned int non_singular_classes_sum
= 0;
3371 bool merged_p
= false;
3373 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3374 it
!= m_classes
.end (); ++it
)
3375 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3377 congruence_class
*c
= (*it
)->classes
[i
];
3378 if (c
->members
.length () > 1)
3380 non_singular_classes_count
++;
3381 non_singular_classes_sum
+= c
->members
.length ();
3387 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
3388 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
3389 prev_class_count
, class_count
);
3390 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
3391 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
3392 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
3393 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
3394 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
3395 non_singular_classes_count
: 0.0f
,
3396 non_singular_classes_count
);
3397 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
3398 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
3399 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
3402 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
3403 it
!= m_classes
.end (); ++it
)
3404 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
3406 congruence_class
*c
= (*it
)->classes
[i
];
3408 if (c
->members
.length () == 1)
3411 gcc_assert (c
->members
.length ());
3413 sem_item
*source
= c
->members
[0];
3415 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
3417 sem_item
*alias
= c
->members
[j
];
3421 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
3422 xstrdup_for_dump (source
->node
->name ()),
3423 xstrdup_for_dump (alias
->node
->name ()));
3424 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
3425 xstrdup_for_dump (source
->node
->asm_name ()),
3426 xstrdup_for_dump (alias
->node
->asm_name ()));
3429 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
3433 "Merge operation is skipped due to no_icf "
3439 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3441 source
->dump_to_file (dump_file
);
3442 alias
->dump_to_file (dump_file
);
3445 if (dbg_cnt (merged_ipa_icf
))
3446 merged_p
|= source
->merge (alias
);
3453 /* Dump function prints all class members to a FILE with an INDENT. */
3456 congruence_class::dump (FILE *file
, unsigned int indent
) const
3458 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3459 id
, members
[0]->get_hash (), members
.length ());
3461 FPUTS_SPACES (file
, indent
+ 2, "");
3462 for (unsigned i
= 0; i
< members
.length (); i
++)
3463 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3464 (void *) members
[i
]->decl
,
3465 members
[i
]->node
->order
);
3467 fprintf (file
, "\n");
3470 /* Returns true if there's a member that is used from another group. */
3473 congruence_class::is_class_used (void)
3475 for (unsigned int i
= 0; i
< members
.length (); i
++)
3476 if (members
[i
]->usages
.length ())
3482 /* Generate pass summary for IPA ICF pass. */
3485 ipa_icf_generate_summary (void)
3488 optimizer
= new sem_item_optimizer ();
3490 optimizer
->register_hooks ();
3491 optimizer
->parse_funcs_and_vars ();
3494 /* Write pass summary for IPA ICF pass. */
3497 ipa_icf_write_summary (void)
3499 gcc_assert (optimizer
);
3501 optimizer
->write_summary ();
3504 /* Read pass summary for IPA ICF pass. */
3507 ipa_icf_read_summary (void)
3510 optimizer
= new sem_item_optimizer ();
3512 optimizer
->read_summary ();
3513 optimizer
->register_hooks ();
3516 /* Semantic equality exection function. */
3519 ipa_icf_driver (void)
3521 gcc_assert (optimizer
);
3523 bool merged_p
= optimizer
->execute ();
3528 return merged_p
? TODO_remove_functions
: 0;
3531 const pass_data pass_data_ipa_icf
=
3533 IPA_PASS
, /* type */
3535 OPTGROUP_IPA
, /* optinfo_flags */
3536 TV_IPA_ICF
, /* tv_id */
3537 0, /* properties_required */
3538 0, /* properties_provided */
3539 0, /* properties_destroyed */
3540 0, /* todo_flags_start */
3541 0, /* todo_flags_finish */
3544 class pass_ipa_icf
: public ipa_opt_pass_d
3547 pass_ipa_icf (gcc::context
*ctxt
)
3548 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3549 ipa_icf_generate_summary
, /* generate_summary */
3550 ipa_icf_write_summary
, /* write_summary */
3551 ipa_icf_read_summary
, /* read_summary */
3553 write_optimization_summary */
3555 read_optimization_summary */
3556 NULL
, /* stmt_fixup */
3557 0, /* function_transform_todo_flags_start */
3558 NULL
, /* function_transform */
3559 NULL
) /* variable_transform */
3562 /* opt_pass methods: */
3563 virtual bool gate (function
*)
3565 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3568 virtual unsigned int execute (function
*)
3570 return ipa_icf_driver();
3572 }; // class pass_ipa_icf
3574 } // ipa_icf namespace
3577 make_pass_ipa_icf (gcc::context
*ctxt
)
3579 return new ipa_icf::pass_ipa_icf (ctxt
);