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"
61 #include "double-int.h"
69 #include "fold-const.h"
72 #include "hard-reg-set.h"
74 #include "dominance.h"
76 #include "basic-block.h"
77 #include "tree-ssa-alias.h"
78 #include "internal-fn.h"
79 #include "gimple-expr.h"
85 #include "statistics.h"
87 #include "fixed-value.h"
88 #include "insn-config.h"
97 #include "gimple-iterator.h"
98 #include "gimple-ssa.h"
100 #include "tree-phinodes.h"
101 #include "stringpool.h"
102 #include "tree-ssanames.h"
103 #include "tree-dfa.h"
104 #include "tree-pass.h"
105 #include "gimple-pretty-print.h"
106 #include "hash-map.h"
107 #include "plugin-api.h"
110 #include "alloc-pool.h"
111 #include "symbol-summary.h"
112 #include "ipa-prop.h"
113 #include "ipa-inline.h"
116 #include "hash-table.h"
117 #include "coverage.h"
119 #include "print-tree.h"
120 #include "lto-streamer.h"
121 #include "data-streamer.h"
122 #include "ipa-utils.h"
123 #include "ipa-icf-gimple.h"
125 #include "stor-layout.h"
127 using namespace ipa_icf_gimple
;
133 symbol_compare_collection::symbol_compare_collection (symtab_node
*node
)
135 m_references
.create (0);
136 m_interposables
.create (0);
140 if (is_a
<varpool_node
*> (node
) && DECL_VIRTUAL_P (node
->decl
))
143 for (unsigned i
= 0; i
< node
->num_references (); i
++)
145 ref
= node
->iterate_reference (i
, ref
);
146 if (ref
->address_matters_p ())
147 m_references
.safe_push (ref
->referred
);
149 if (ref
->referred
->get_availability () <= AVAIL_INTERPOSABLE
)
151 if (ref
->address_matters_p ())
152 m_references
.safe_push (ref
->referred
);
154 m_interposables
.safe_push (ref
->referred
);
158 if (is_a
<cgraph_node
*> (node
))
160 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
162 for (cgraph_edge
*e
= cnode
->callees
; e
; e
= e
->next_callee
)
163 if (e
->callee
->get_availability () <= AVAIL_INTERPOSABLE
)
164 m_interposables
.safe_push (e
->callee
);
168 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
170 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
171 item (_item
), index (_index
)
175 /* Semantic item constructor for a node of _TYPE, where STACK is used
176 for bitmap memory allocation. */
178 sem_item::sem_item (sem_item_type _type
,
179 bitmap_obstack
*stack
): type(_type
), hash(0)
184 /* Semantic item constructor for a node of _TYPE, where STACK is used
185 for bitmap memory allocation. The item is based on symtab node _NODE
186 with computed _HASH. */
188 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
189 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
190 node (_node
), hash (_hash
)
196 /* Add reference to a semantic TARGET. */
199 sem_item::add_reference (sem_item
*target
)
201 refs
.safe_push (target
);
202 unsigned index
= refs
.length ();
203 target
->usages
.safe_push (new sem_usage_pair(this, index
));
204 bitmap_set_bit (target
->usage_index_bitmap
, index
);
205 refs_set
.add (target
->node
);
208 /* Initialize internal data structures. Bitmap STACK is used for
209 bitmap memory allocation process. */
212 sem_item::setup (bitmap_obstack
*stack
)
214 gcc_checking_assert (node
);
217 tree_refs
.create (0);
219 usage_index_bitmap
= BITMAP_ALLOC (stack
);
222 sem_item::~sem_item ()
224 for (unsigned i
= 0; i
< usages
.length (); i
++)
228 tree_refs
.release ();
231 BITMAP_FREE (usage_index_bitmap
);
234 /* Dump function for debugging purpose. */
237 sem_item::dump (void)
241 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
242 node
->name(), node
->order
, (void *) node
->decl
);
243 fprintf (dump_file
, " hash: %u\n", get_hash ());
244 fprintf (dump_file
, " references: ");
246 for (unsigned i
= 0; i
< refs
.length (); i
++)
247 fprintf (dump_file
, "%s%s ", refs
[i
]->node
->name (),
248 i
< refs
.length() - 1 ? "," : "");
250 fprintf (dump_file
, "\n");
254 /* Return true if target supports alias symbols. */
257 sem_item::target_supports_symbol_aliases_p (void)
259 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
266 /* Semantic function constructor that uses STACK as bitmap memory stack. */
268 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
269 m_checker (NULL
), m_compared_func (NULL
)
271 arg_types
.create (0);
273 bb_sorted
.create (0);
276 /* Constructor based on callgraph node _NODE with computed hash _HASH.
277 Bitmap STACK is used for memory allocation. */
278 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
279 bitmap_obstack
*stack
):
280 sem_item (FUNC
, node
, hash
, stack
),
281 m_checker (NULL
), m_compared_func (NULL
)
283 arg_types
.create (0);
285 bb_sorted
.create (0);
288 sem_function::~sem_function ()
290 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
291 delete (bb_sorted
[i
]);
293 arg_types
.release ();
295 bb_sorted
.release ();
298 /* Calculates hash value based on a BASIC_BLOCK. */
301 sem_function::get_bb_hash (const sem_bb
*basic_block
)
303 inchash::hash hstate
;
305 hstate
.add_int (basic_block
->nondbg_stmt_count
);
306 hstate
.add_int (basic_block
->edge_count
);
308 return hstate
.end ();
311 /* References independent hash function. */
314 sem_function::get_hash (void)
318 inchash::hash hstate
;
319 hstate
.add_int (177454); /* Random number for function type. */
321 hstate
.add_int (arg_count
);
322 hstate
.add_int (cfg_checksum
);
323 hstate
.add_int (gcode_hash
);
325 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
326 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
328 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
329 hstate
.add_int (bb_sizes
[i
]);
331 hash
= hstate
.end ();
337 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
338 point to a same function. Comparison can be skipped if IGNORED_NODES
339 contains these nodes. ADDRESS indicate if address is taken. */
342 sem_item::compare_cgraph_references (
343 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
,
344 symtab_node
*n1
, symtab_node
*n2
, bool address
)
346 enum availability avail1
, avail2
;
351 /* Merging two definitions with a reference to equivalent vtables, but
352 belonging to a different type may result in ipa-polymorphic-call analysis
353 giving a wrong answer about the dynamic type of instance. */
354 if (is_a
<varpool_node
*> (n1
)
355 && (DECL_VIRTUAL_P (n1
->decl
) || DECL_VIRTUAL_P (n2
->decl
))
356 && (DECL_VIRTUAL_P (n1
->decl
) != DECL_VIRTUAL_P (n2
->decl
)
357 || !types_must_be_same_for_odr (DECL_CONTEXT (n1
->decl
),
358 DECL_CONTEXT (n2
->decl
))))
359 return return_false_with_msg
360 ("references to virtual tables can not be merged");
362 if (address
&& n1
->equal_address_to (n2
) == 1)
364 if (!address
&& n1
->semantically_equivalent_p (n2
))
367 n1
= n1
->ultimate_alias_target (&avail1
);
368 n2
= n2
->ultimate_alias_target (&avail2
);
370 if (avail1
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n1
)
371 && avail2
>= AVAIL_INTERPOSABLE
&& ignored_nodes
.get (n2
))
374 return return_false_with_msg ("different references");
377 /* If cgraph edges E1 and E2 are indirect calls, verify that
378 ECF flags are the same. */
380 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
382 if (e1
->indirect_info
&& e2
->indirect_info
)
384 int e1_flags
= e1
->indirect_info
->ecf_flags
;
385 int e2_flags
= e2
->indirect_info
->ecf_flags
;
387 if (e1_flags
!= e2_flags
)
388 return return_false_with_msg ("ICF flags are different");
390 else if (e1
->indirect_info
|| e2
->indirect_info
)
396 /* Fast equality function based on knowledge known in WPA. */
399 sem_function::equals_wpa (sem_item
*item
,
400 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
402 gcc_assert (item
->type
== FUNC
);
404 m_compared_func
= static_cast<sem_function
*> (item
);
406 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
407 return return_false_with_msg ("different number of arguments");
409 /* Compare special function DECL attributes. */
410 if (DECL_FUNCTION_PERSONALITY (decl
)
411 != DECL_FUNCTION_PERSONALITY (item
->decl
))
412 return return_false_with_msg ("function personalities are different");
414 if (DECL_DISREGARD_INLINE_LIMITS (decl
)
415 != DECL_DISREGARD_INLINE_LIMITS (item
->decl
))
416 return return_false_with_msg ("DECL_DISREGARD_INLINE_LIMITS are different");
418 if (DECL_DECLARED_INLINE_P (decl
) != DECL_DECLARED_INLINE_P (item
->decl
))
419 return return_false_with_msg ("inline attributes are different");
421 if (DECL_IS_OPERATOR_NEW (decl
) != DECL_IS_OPERATOR_NEW (item
->decl
))
422 return return_false_with_msg ("operator new flags are different");
424 if (DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl
)
425 != DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (item
->decl
))
426 return return_false_with_msg ("intrument function entry exit "
427 "attributes are different");
429 if (DECL_NO_LIMIT_STACK (decl
) != DECL_NO_LIMIT_STACK (item
->decl
))
430 return return_false_with_msg ("no stack limit attributes are different");
432 if (DECL_CXX_CONSTRUCTOR_P (decl
) != DECL_CXX_CONSTRUCTOR_P (item
->decl
))
433 return return_false_with_msg ("DELC_CXX_CONSTRUCTOR mismatch");
435 if (DECL_CXX_DESTRUCTOR_P (decl
) != DECL_CXX_DESTRUCTOR_P (item
->decl
))
436 return return_false_with_msg ("DELC_CXX_DESTRUCTOR mismatch");
438 if (flags_from_decl_or_type (decl
) != flags_from_decl_or_type (item
->decl
))
439 return return_false_with_msg ("decl_or_type flags are different");
441 /* Do not match polymorphic constructors of different types. They calls
442 type memory location for ipa-polymorphic-call and we do not want
443 it to get confused by wrong type. */
444 if (DECL_CXX_CONSTRUCTOR_P (decl
)
445 && TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
)
447 if (TREE_CODE (TREE_TYPE (item
->decl
)) != METHOD_TYPE
)
448 return return_false_with_msg ("DECL_CXX_CONSTURCTOR type mismatch");
449 else if (!func_checker::compatible_polymorphic_types_p
450 (method_class_type (TREE_TYPE (decl
)),
451 method_class_type (TREE_TYPE (item
->decl
)), false))
452 return return_false_with_msg ("ctor polymorphic type mismatch");
455 /* Checking function TARGET and OPTIMIZATION flags. */
456 cl_target_option
*tar1
= target_opts_for_fn (decl
);
457 cl_target_option
*tar2
= target_opts_for_fn (item
->decl
);
459 if (tar1
!= tar2
&& !cl_target_option_eq (tar1
, tar2
))
461 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
463 fprintf (dump_file
, "target flags difference");
464 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
467 return return_false_with_msg ("Target flags are different");
470 cl_optimization
*opt1
= opts_for_fn (decl
);
471 cl_optimization
*opt2
= opts_for_fn (item
->decl
);
473 if (opt1
!= opt2
&& memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
475 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
477 fprintf (dump_file
, "optimization flags difference");
478 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
481 return return_false_with_msg ("optimization flags are different");
484 /* Result type checking. */
485 if (!func_checker::compatible_types_p (result_type
,
486 m_compared_func
->result_type
))
487 return return_false_with_msg ("result types are different");
489 /* Checking types of arguments. */
490 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
492 /* This guard is here for function pointer with attributes (pr59927.c). */
493 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
494 return return_false_with_msg ("NULL argument type");
496 if (!func_checker::compatible_types_p (arg_types
[i
],
497 m_compared_func
->arg_types
[i
]))
498 return return_false_with_msg ("argument type is different");
499 if (POINTER_TYPE_P (arg_types
[i
])
500 && (TYPE_RESTRICT (arg_types
[i
])
501 != TYPE_RESTRICT (m_compared_func
->arg_types
[i
])))
502 return return_false_with_msg ("argument restrict flag mismatch");
505 if (node
->num_references () != item
->node
->num_references ())
506 return return_false_with_msg ("different number of references");
508 if (comp_type_attributes (TREE_TYPE (decl
),
509 TREE_TYPE (item
->decl
)) != 1)
510 return return_false_with_msg ("different type attributes");
512 /* The type of THIS pointer type memory location for
513 ipa-polymorphic-call-analysis. */
514 if (opt_for_fn (decl
, flag_devirtualize
)
515 && (TREE_CODE (TREE_TYPE (decl
)) == METHOD_TYPE
516 || TREE_CODE (TREE_TYPE (item
->decl
)) == METHOD_TYPE
)
518 || ipa_is_param_used (IPA_NODE_REF (dyn_cast
<cgraph_node
*>(node
)),
520 && compare_polymorphic_p ())
522 if (TREE_CODE (TREE_TYPE (decl
)) != TREE_CODE (TREE_TYPE (item
->decl
)))
523 return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
524 if (!func_checker::compatible_polymorphic_types_p
525 (method_class_type (TREE_TYPE (decl
)),
526 method_class_type (TREE_TYPE (item
->decl
)), false))
527 return return_false_with_msg ("THIS pointer ODR type mismatch");
530 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
531 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
533 item
->node
->iterate_reference (i
, ref2
);
535 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
,
537 ref
->address_matters_p ()))
541 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
542 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
546 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
,
550 e1
= e1
->next_callee
;
551 e2
= e2
->next_callee
;
555 return return_false_with_msg ("different number of edges");
560 /* Returns true if the item equals to ITEM given as argument. */
563 sem_function::equals (sem_item
*item
,
564 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
566 gcc_assert (item
->type
== FUNC
);
567 bool eq
= equals_private (item
, ignored_nodes
);
569 if (m_checker
!= NULL
)
575 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
577 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
578 xstrdup_for_dump (node
->name()),
579 xstrdup_for_dump (item
->node
->name ()),
582 xstrdup_for_dump (node
->asm_name ()),
583 xstrdup_for_dump (item
->node
->asm_name ()),
584 eq
? "true" : "false");
589 /* Processes function equality comparison. */
592 sem_function::equals_private (sem_item
*item
,
593 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
595 if (item
->type
!= FUNC
)
598 basic_block bb1
, bb2
;
600 edge_iterator ei1
, ei2
;
604 m_compared_func
= static_cast<sem_function
*> (item
);
606 gcc_assert (decl
!= item
->decl
);
608 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
609 || edge_count
!= m_compared_func
->edge_count
610 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
611 return return_false ();
613 if (!equals_wpa (item
, ignored_nodes
))
616 /* Checking function arguments. */
617 tree decl1
= DECL_ATTRIBUTES (decl
);
618 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
620 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
621 compare_polymorphic_p (),
624 &m_compared_func
->refs_set
);
628 return return_false ();
630 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
631 return return_false ();
633 tree attr_value1
= TREE_VALUE (decl1
);
634 tree attr_value2
= TREE_VALUE (decl2
);
636 if (attr_value1
&& attr_value2
)
638 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
639 TREE_VALUE (attr_value2
));
641 return return_false_with_msg ("attribute values are different");
643 else if (!attr_value1
&& !attr_value2
)
646 return return_false ();
648 decl1
= TREE_CHAIN (decl1
);
649 decl2
= TREE_CHAIN (decl2
);
653 return return_false();
655 for (arg1
= DECL_ARGUMENTS (decl
),
656 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
657 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
658 if (!m_checker
->compare_decl (arg1
, arg2
))
659 return return_false ();
661 /* Fill-up label dictionary. */
662 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
664 m_checker
->parse_labels (bb_sorted
[i
]);
665 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
668 /* Checking all basic blocks. */
669 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
670 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
671 return return_false();
673 dump_message ("All BBs are equal\n");
675 auto_vec
<int> bb_dict
;
677 /* Basic block edges check. */
678 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
680 bb1
= bb_sorted
[i
]->bb
;
681 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
683 ei2
= ei_start (bb2
->preds
);
685 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
689 if (e1
->flags
!= e2
->flags
)
690 return return_false_with_msg ("flags comparison returns false");
692 if (!bb_dict_test (&bb_dict
, e1
->src
->index
, e2
->src
->index
))
693 return return_false_with_msg ("edge comparison returns false");
695 if (!bb_dict_test (&bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
696 return return_false_with_msg ("BB comparison returns false");
698 if (!m_checker
->compare_edge (e1
, e2
))
699 return return_false_with_msg ("edge comparison returns false");
705 /* Basic block PHI nodes comparison. */
706 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
707 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
708 return return_false_with_msg ("PHI node comparison returns false");
713 /* Set LOCAL_P of NODE to true if DATA is non-NULL.
714 Helper for call_for_symbol_thunks_and_aliases. */
717 set_local (cgraph_node
*node
, void *data
)
719 node
->local
.local
= data
!= NULL
;
723 /* TREE_ADDRESSABLE of NODE to true.
724 Helper for call_for_symbol_thunks_and_aliases. */
727 set_addressable (varpool_node
*node
, void *)
729 TREE_ADDRESSABLE (node
->decl
) = 1;
733 /* Clear DECL_RTL of NODE.
734 Helper for call_for_symbol_thunks_and_aliases. */
737 clear_decl_rtl (symtab_node
*node
, void *)
739 SET_DECL_RTL (node
->decl
, NULL
);
743 /* Redirect all callers of N and its aliases to TO. Remove aliases if
744 possible. Return number of redirections made. */
747 redirect_all_callers (cgraph_node
*n
, cgraph_node
*to
)
751 cgraph_edge
*e
= n
->callers
;
755 /* Redirecting thunks to interposable symbols or symbols in other sections
756 may not be supported by target output code. Play safe for now and
757 punt on redirection. */
758 if (!e
->caller
->thunk
.thunk_p
)
760 struct cgraph_edge
*nexte
= e
->next_caller
;
761 e
->redirect_callee (to
);
768 for (unsigned i
= 0; n
->iterate_direct_aliases (i
, ref
);)
770 bool removed
= false;
771 cgraph_node
*n_alias
= dyn_cast
<cgraph_node
*> (ref
->referring
);
773 if ((DECL_COMDAT_GROUP (n
->decl
)
774 && (DECL_COMDAT_GROUP (n
->decl
)
775 == DECL_COMDAT_GROUP (n_alias
->decl
)))
776 || (n_alias
->get_availability () > AVAIL_INTERPOSABLE
777 && n
->get_availability () > AVAIL_INTERPOSABLE
))
779 nredirected
+= redirect_all_callers (n_alias
, to
);
780 if (n_alias
->can_remove_if_no_direct_calls_p ()
781 && !n_alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
783 && !n_alias
->has_aliases_p ())
792 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
796 sem_function::merge (sem_item
*alias_item
)
798 gcc_assert (alias_item
->type
== FUNC
);
800 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
802 cgraph_node
*original
= get_node ();
803 cgraph_node
*local_original
= NULL
;
804 cgraph_node
*alias
= alias_func
->get_node ();
806 bool create_wrapper
= false;
807 bool create_alias
= false;
808 bool redirect_callers
= false;
811 bool original_discardable
= false;
812 bool original_discarded
= false;
814 bool original_address_matters
= original
->address_matters_p ();
815 bool alias_address_matters
= alias
->address_matters_p ();
817 if (DECL_NO_INLINE_WARNING_P (original
->decl
)
818 != DECL_NO_INLINE_WARNING_P (alias
->decl
))
823 "DECL_NO_INLINE_WARNING mismatch.\n\n");
827 /* Do not attempt to mix functions from different user sections;
828 we do not know what user intends with those. */
829 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
830 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
831 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
836 "original and alias are in different sections.\n\n");
840 /* See if original is in a section that can be discarded if the main
841 symbol is not used. */
843 if (original
->can_be_discarded_p ())
844 original_discardable
= true;
845 /* Also consider case where we have resolution info and we know that
846 original's definition is not going to be used. In this case we can not
847 create alias to original. */
848 if (node
->resolution
!= LDPR_UNKNOWN
849 && !decl_binds_to_current_def_p (node
->decl
))
850 original_discardable
= original_discarded
= true;
852 /* Creating a symtab alias is the optimal way to merge.
853 It however can not be used in the following cases:
855 1) if ORIGINAL and ALIAS may be possibly compared for address equality.
856 2) if ORIGINAL is in a section that may be discarded by linker or if
857 it is an external functions where we can not create an alias
858 (ORIGINAL_DISCARDABLE)
859 3) if target do not support symbol aliases.
860 4) original and alias lie in different comdat groups.
862 If we can not produce alias, we will turn ALIAS into WRAPPER of ORIGINAL
863 and/or redirect all callers from ALIAS to ORIGINAL. */
864 if ((original_address_matters
&& alias_address_matters
)
865 || (original_discardable
866 && (!DECL_COMDAT_GROUP (alias
->decl
)
867 || (DECL_COMDAT_GROUP (alias
->decl
)
868 != DECL_COMDAT_GROUP (original
->decl
))))
869 || original_discarded
870 || !sem_item::target_supports_symbol_aliases_p ()
871 || DECL_COMDAT_GROUP (alias
->decl
) != DECL_COMDAT_GROUP (original
->decl
))
873 /* First see if we can produce wrapper. */
875 /* Do not turn function in one comdat group into wrapper to another
876 comdat group. Other compiler producing the body of the
877 another comdat group may make opossite decision and with unfortunate
878 linker choices this may close a loop. */
879 if (DECL_COMDAT_GROUP (original
->decl
) && DECL_COMDAT_GROUP (alias
->decl
)
880 && (DECL_COMDAT_GROUP (alias
->decl
)
881 != DECL_COMDAT_GROUP (original
->decl
)))
885 "Wrapper cannot be created because of COMDAT\n");
887 else if (DECL_STATIC_CHAIN (alias
->decl
))
891 "Can not create wrapper of nested functions.\n");
893 /* TODO: We can also deal with variadic functions never calling
895 else if (stdarg_p (TREE_TYPE (alias
->decl
)))
899 "can not create wrapper of stdarg function.\n");
901 else if (inline_summaries
902 && inline_summaries
->get (alias
)->self_size
<= 2)
905 fprintf (dump_file
, "Wrapper creation is not "
906 "profitable (function is too small).\n");
908 /* If user paid attention to mark function noinline, assume it is
909 somewhat special and do not try to turn it into a wrapper that can
910 not be undone by inliner. */
911 else if (lookup_attribute ("noinline", DECL_ATTRIBUTES (alias
->decl
)))
914 fprintf (dump_file
, "Wrappers are not created for noinline.\n");
917 create_wrapper
= true;
919 /* We can redirect local calls in the case both alias and orignal
920 are not interposable. */
922 = alias
->get_availability () > AVAIL_INTERPOSABLE
923 && original
->get_availability () > AVAIL_INTERPOSABLE
924 && !alias
->instrumented_version
;
926 if (!redirect_callers
&& !create_wrapper
)
929 fprintf (dump_file
, "Not unifying; can not redirect callers nor "
930 "produce wrapper\n\n");
934 /* Work out the symbol the wrapper should call.
935 If ORIGINAL is interposable, we need to call a local alias.
936 Also produce local alias (if possible) as an optimization.
938 Local aliases can not be created inside comdat groups because that
939 prevents inlining. */
940 if (!original_discardable
&& !original
->get_comdat_group ())
943 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
945 && original
->get_availability () > AVAIL_INTERPOSABLE
)
946 local_original
= original
;
948 /* If we can not use local alias, fallback to the original
950 else if (original
->get_availability () > AVAIL_INTERPOSABLE
)
951 local_original
= original
;
953 /* If original is COMDAT local, we can not really redirect calls outside
954 of its comdat group to it. */
955 if (original
->comdat_local_p ())
956 redirect_callers
= false;
960 fprintf (dump_file
, "Not unifying; "
961 "can not produce local alias.\n\n");
965 if (!redirect_callers
&& !create_wrapper
)
968 fprintf (dump_file
, "Not unifying; "
969 "can not redirect callers nor produce a wrapper\n\n");
973 && !alias
->call_for_symbol_and_aliases (cgraph_node::has_thunk_p
,
975 && !alias
->can_remove_if_no_direct_calls_p ())
978 fprintf (dump_file
, "Not unifying; can not make wrapper and "
979 "function has other uses than direct calls\n\n");
986 if (redirect_callers
)
988 int nredirected
= redirect_all_callers (alias
, local_original
);
992 alias
->icf_merged
= true;
993 local_original
->icf_merged
= true;
995 if (dump_file
&& nredirected
)
996 fprintf (dump_file
, "%i local calls have been "
997 "redirected.\n", nredirected
);
1000 /* If all callers was redirected, do not produce wrapper. */
1001 if (alias
->can_remove_if_no_direct_calls_p ()
1002 && !alias
->has_aliases_p ())
1004 create_wrapper
= false;
1007 gcc_assert (!create_alias
);
1009 else if (create_alias
)
1011 alias
->icf_merged
= true;
1013 /* Remove the function's body. */
1014 ipa_merge_profiles (original
, alias
);
1015 alias
->release_body (true);
1017 /* Notice global symbol possibly produced RTL. */
1018 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1021 /* Create the alias. */
1022 cgraph_node::create_alias (alias_func
->decl
, decl
);
1023 alias
->resolve_alias (original
);
1025 original
->call_for_symbol_thunks_and_aliases
1026 (set_local
, (void *)(size_t) original
->local_p (), true);
1029 fprintf (dump_file
, "Unified; Function alias has been created.\n\n");
1033 gcc_assert (!create_alias
);
1034 alias
->icf_merged
= true;
1035 local_original
->icf_merged
= true;
1037 ipa_merge_profiles (local_original
, alias
, true);
1038 alias
->create_wrapper (local_original
);
1041 fprintf (dump_file
, "Unified; Wrapper has been created.\n\n");
1044 /* It's possible that redirection can hit thunks that block
1045 redirection opportunities. */
1046 gcc_assert (alias
->icf_merged
|| remove
|| redirect_callers
);
1047 original
->icf_merged
= true;
1049 /* Inform the inliner about cross-module merging. */
1050 if ((original
->lto_file_data
|| alias
->lto_file_data
)
1051 && original
->lto_file_data
!= alias
->lto_file_data
)
1052 local_original
->merged
= original
->merged
= true;
1056 ipa_merge_profiles (original
, alias
);
1057 alias
->release_body ();
1059 alias
->body_removed
= true;
1060 alias
->icf_merged
= true;
1062 fprintf (dump_file
, "Unified; Function body was removed.\n");
1068 /* Semantic item initialization function. */
1071 sem_function::init (void)
1074 get_node ()->get_untransformed_body ();
1076 tree fndecl
= node
->decl
;
1077 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1080 gcc_assert (SSANAMES (func
));
1082 ssa_names_size
= SSANAMES (func
)->length ();
1086 region_tree
= func
->eh
->region_tree
;
1088 /* iterating all function arguments. */
1089 arg_count
= count_formal_params (fndecl
);
1091 edge_count
= n_edges_for_fn (func
);
1092 cfg_checksum
= coverage_compute_cfg_checksum (func
);
1094 inchash::hash hstate
;
1097 FOR_EACH_BB_FN (bb
, func
)
1099 unsigned nondbg_stmt_count
= 0;
1102 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
);
1104 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
1107 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1110 gimple stmt
= gsi_stmt (gsi
);
1112 if (gimple_code (stmt
) != GIMPLE_DEBUG
1113 && gimple_code (stmt
) != GIMPLE_PREDICT
)
1115 hash_stmt (stmt
, hstate
);
1116 nondbg_stmt_count
++;
1120 gcode_hash
= hstate
.end ();
1121 bb_sizes
.safe_push (nondbg_stmt_count
);
1123 /* Inserting basic block to hash table. */
1124 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
1125 EDGE_COUNT (bb
->preds
)
1126 + EDGE_COUNT (bb
->succs
));
1128 bb_sorted
.safe_push (semantic_bb
);
1134 /* Accumulate to HSTATE a hash of expression EXP.
1135 Identical to inchash::add_expr, but guaranteed to be stable across LTO
1136 and DECL equality classes. */
1139 sem_item::add_expr (const_tree exp
, inchash::hash
&hstate
)
1141 if (exp
== NULL_TREE
)
1143 hstate
.merge_hash (0);
1147 /* Handled component can be matched in a cureful way proving equivalence
1148 even if they syntactically differ. Just skip them. */
1150 while (handled_component_p (exp
))
1151 exp
= TREE_OPERAND (exp
, 0);
1153 enum tree_code code
= TREE_CODE (exp
);
1154 hstate
.add_int (code
);
1158 /* Use inchash::add_expr for everything that is LTO stable. */
1166 inchash::add_expr (exp
, hstate
);
1170 unsigned HOST_WIDE_INT idx
;
1173 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1175 FOR_EACH_CONSTRUCTOR_VALUE (CONSTRUCTOR_ELTS (exp
), idx
, value
)
1177 add_expr (value
, hstate
);
1182 add_expr (get_base_address (TREE_OPERAND (exp
, 0)), hstate
);
1188 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1191 case POINTER_PLUS_EXPR
:
1194 add_expr (TREE_OPERAND (exp
, 0), hstate
);
1195 add_expr (TREE_OPERAND (exp
, 1), hstate
);
1199 inchash::hash one
, two
;
1200 add_expr (TREE_OPERAND (exp
, 0), one
);
1201 add_expr (TREE_OPERAND (exp
, 1), two
);
1202 hstate
.add_commutative (one
, two
);
1206 hstate
.add_wide_int (int_size_in_bytes (TREE_TYPE (exp
)));
1207 return add_expr (TREE_OPERAND (exp
, 0), hstate
);
1213 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
1216 sem_function::hash_stmt (gimple stmt
, inchash::hash
&hstate
)
1218 enum gimple_code code
= gimple_code (stmt
);
1220 hstate
.add_int (code
);
1225 if (commutative_tree_code (gimple_assign_rhs_code (stmt
))
1226 || commutative_ternary_tree_code (gimple_assign_rhs_code (stmt
)))
1228 inchash::hash one
, two
;
1230 add_expr (gimple_assign_rhs1 (stmt
), one
);
1231 add_expr (gimple_assign_rhs2 (stmt
), two
);
1232 hstate
.add_commutative (one
, two
);
1233 add_expr (gimple_assign_lhs (stmt
), hstate
);
1236 /* ... fall through ... */
1242 /* All these statements are equivalent if their operands are. */
1243 for (unsigned i
= 0; i
< gimple_num_ops (stmt
); ++i
)
1244 add_expr (gimple_op (stmt
, i
), hstate
);
1251 /* Return true if polymorphic comparison must be processed. */
1254 sem_function::compare_polymorphic_p (void)
1256 struct cgraph_edge
*e
;
1258 if (!opt_for_fn (decl
, flag_devirtualize
))
1260 if (get_node ()->indirect_calls
!= NULL
1261 || m_compared_func
->get_node ()->indirect_calls
!= NULL
)
1263 /* TODO: We can do simple propagation determining what calls may lead to
1264 a polymorphic call. */
1265 for (e
= m_compared_func
->get_node ()->callees
; e
; e
= e
->next_callee
)
1266 if (e
->callee
->definition
1267 && opt_for_fn (e
->callee
->decl
, flag_devirtualize
))
1272 /* For a given call graph NODE, the function constructs new
1273 semantic function item. */
1276 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
1278 tree fndecl
= node
->decl
;
1279 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
1281 /* TODO: add support for thunks. */
1283 if (!func
|| !node
->has_gimple_body_p ())
1286 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
1289 sem_function
*f
= new sem_function (node
, 0, stack
);
1296 /* Parses function arguments and result type. */
1299 sem_function::parse_tree_args (void)
1303 if (arg_types
.exists ())
1304 arg_types
.release ();
1306 arg_types
.create (4);
1307 tree fnargs
= DECL_ARGUMENTS (decl
);
1309 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
1310 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
1312 /* Function result type. */
1313 result
= DECL_RESULT (decl
);
1314 result_type
= result
? TREE_TYPE (result
) : NULL
;
1316 /* During WPA, we can get arguments by following method. */
1319 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
1320 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
1321 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
1323 result_type
= TREE_TYPE (TREE_TYPE (decl
));
1327 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
1328 return true if phi nodes are semantically equivalent in these blocks . */
1331 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
1333 gphi_iterator si1
, si2
;
1335 unsigned size1
, size2
, i
;
1339 gcc_assert (bb1
!= NULL
);
1340 gcc_assert (bb2
!= NULL
);
1342 si2
= gsi_start_phis (bb2
);
1343 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
1346 gsi_next_nonvirtual_phi (&si1
);
1347 gsi_next_nonvirtual_phi (&si2
);
1349 if (gsi_end_p (si1
) && gsi_end_p (si2
))
1352 if (gsi_end_p (si1
) || gsi_end_p (si2
))
1353 return return_false();
1358 tree phi_result1
= gimple_phi_result (phi1
);
1359 tree phi_result2
= gimple_phi_result (phi2
);
1361 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1362 return return_false_with_msg ("PHI results are different");
1364 size1
= gimple_phi_num_args (phi1
);
1365 size2
= gimple_phi_num_args (phi2
);
1368 return return_false ();
1370 for (i
= 0; i
< size1
; ++i
)
1372 t1
= gimple_phi_arg (phi1
, i
)->def
;
1373 t2
= gimple_phi_arg (phi2
, i
)->def
;
1375 if (!m_checker
->compare_operand (t1
, t2
))
1376 return return_false ();
1378 e1
= gimple_phi_arg_edge (phi1
, i
);
1379 e2
= gimple_phi_arg_edge (phi2
, i
);
1381 if (!m_checker
->compare_edge (e1
, e2
))
1382 return return_false ();
1391 /* Returns true if tree T can be compared as a handled component. */
1394 sem_function::icf_handled_component_p (tree t
)
1396 tree_code tc
= TREE_CODE (t
);
1398 return ((handled_component_p (t
))
1399 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1400 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1403 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1404 corresponds to TARGET. */
1407 sem_function::bb_dict_test (vec
<int> *bb_dict
, int source
, int target
)
1412 if (bb_dict
->length () <= (unsigned)source
)
1413 bb_dict
->safe_grow_cleared (source
+ 1);
1415 if ((*bb_dict
)[source
] == 0)
1417 (*bb_dict
)[source
] = target
;
1421 return (*bb_dict
)[source
] == target
;
1425 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1427 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1431 /* Constructor based on varpool node _NODE with computed hash _HASH.
1432 Bitmap STACK is used for memory allocation. */
1434 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1435 bitmap_obstack
*stack
): sem_item(VAR
,
1438 gcc_checking_assert (node
);
1439 gcc_checking_assert (get_node ());
1442 /* Fast equality function based on knowledge known in WPA. */
1445 sem_variable::equals_wpa (sem_item
*item
,
1446 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
1448 gcc_assert (item
->type
== VAR
);
1450 if (node
->num_references () != item
->node
->num_references ())
1451 return return_false_with_msg ("different number of references");
1453 if (DECL_TLS_MODEL (decl
) || DECL_TLS_MODEL (item
->decl
))
1454 return return_false_with_msg ("TLS model");
1456 if (DECL_ALIGN (decl
) != DECL_ALIGN (item
->decl
))
1457 return return_false_with_msg ("alignment mismatch");
1459 if (DECL_VIRTUAL_P (decl
) != DECL_VIRTUAL_P (item
->decl
))
1460 return return_false_with_msg ("Virtual flag mismatch");
1462 if (DECL_SIZE (decl
) != DECL_SIZE (item
->decl
)
1463 && ((!DECL_SIZE (decl
) || !DECL_SIZE (item
->decl
))
1464 || !operand_equal_p (DECL_SIZE (decl
),
1465 DECL_SIZE (item
->decl
), OEP_ONLY_CONST
)))
1466 return return_false_with_msg ("size mismatch");
1468 /* Do not attempt to mix data from different user sections;
1469 we do not know what user intends with those. */
1470 if (((DECL_SECTION_NAME (decl
) && !node
->implicit_section
)
1471 || (DECL_SECTION_NAME (item
->decl
) && !item
->node
->implicit_section
))
1472 && DECL_SECTION_NAME (decl
) != DECL_SECTION_NAME (item
->decl
))
1473 return return_false_with_msg ("user section mismatch");
1475 if (DECL_IN_TEXT_SECTION (decl
) != DECL_IN_TEXT_SECTION (item
->decl
))
1476 return return_false_with_msg ("text section");
1478 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
1479 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
1481 item
->node
->iterate_reference (i
, ref2
);
1483 if (!compare_cgraph_references (ignored_nodes
,
1484 ref
->referred
, ref2
->referred
,
1485 ref
->address_matters_p ()))
1488 /* DECL_FINAL_P flag on methods referred by virtual tables is used
1489 to decide on completeness possible_polymorphic_call_targets lists
1490 and therefore it must match. */
1491 if ((DECL_VIRTUAL_P (decl
) || DECL_VIRTUAL_P (item
->decl
))
1492 && (DECL_VIRTUAL_P (ref
->referred
->decl
)
1493 || DECL_VIRTUAL_P (ref2
->referred
->decl
))
1494 && ((DECL_VIRTUAL_P (ref
->referred
->decl
)
1495 != DECL_VIRTUAL_P (ref2
->referred
->decl
))
1496 || (DECL_FINAL_P (ref
->referred
->decl
)
1497 != DECL_FINAL_P (ref2
->referred
->decl
))))
1498 return return_false_with_msg ("virtual or final flag mismatch");
1504 /* Returns true if the item equals to ITEM given as argument. */
1506 /* Returns true if the item equals to ITEM given as argument. */
1509 sem_variable::equals (sem_item
*item
,
1510 hash_map
<symtab_node
*, sem_item
*> &)
1512 gcc_assert (item
->type
== VAR
);
1515 if (DECL_INITIAL (decl
) == error_mark_node
&& in_lto_p
)
1516 dyn_cast
<varpool_node
*>(node
)->get_constructor ();
1517 if (DECL_INITIAL (item
->decl
) == error_mark_node
&& in_lto_p
)
1518 dyn_cast
<varpool_node
*>(item
->node
)->get_constructor ();
1520 /* As seen in PR ipa/65303 we have to compare variables types. */
1521 if (!func_checker::compatible_types_p (TREE_TYPE (decl
),
1522 TREE_TYPE (item
->decl
)))
1523 return return_false_with_msg ("variables types are different");
1525 ret
= sem_variable::equals (DECL_INITIAL (decl
),
1526 DECL_INITIAL (item
->node
->decl
));
1527 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1529 "Equals called for vars:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
1530 xstrdup_for_dump (node
->name()),
1531 xstrdup_for_dump (item
->node
->name ()),
1532 node
->order
, item
->node
->order
,
1533 xstrdup_for_dump (node
->asm_name ()),
1534 xstrdup_for_dump (item
->node
->asm_name ()), ret
? "true" : "false");
1539 /* Compares trees T1 and T2 for semantic equality. */
1542 sem_variable::equals (tree t1
, tree t2
)
1545 return return_with_debug (t1
== t2
);
1548 tree_code tc1
= TREE_CODE (t1
);
1549 tree_code tc2
= TREE_CODE (t2
);
1552 return return_false_with_msg ("TREE_CODE mismatch");
1558 vec
<constructor_elt
, va_gc
> *v1
, *v2
;
1559 unsigned HOST_WIDE_INT idx
;
1561 enum tree_code typecode
= TREE_CODE (TREE_TYPE (t1
));
1562 if (typecode
!= TREE_CODE (TREE_TYPE (t2
)))
1563 return return_false_with_msg ("constructor type mismatch");
1565 if (typecode
== ARRAY_TYPE
)
1567 HOST_WIDE_INT size_1
= int_size_in_bytes (TREE_TYPE (t1
));
1568 /* For arrays, check that the sizes all match. */
1569 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
))
1571 || size_1
!= int_size_in_bytes (TREE_TYPE (t2
)))
1572 return return_false_with_msg ("constructor array size mismatch");
1574 else if (!func_checker::compatible_types_p (TREE_TYPE (t1
),
1576 return return_false_with_msg ("constructor type incompatible");
1578 v1
= CONSTRUCTOR_ELTS (t1
);
1579 v2
= CONSTRUCTOR_ELTS (t2
);
1580 if (vec_safe_length (v1
) != vec_safe_length (v2
))
1581 return return_false_with_msg ("constructor number of elts mismatch");
1583 for (idx
= 0; idx
< vec_safe_length (v1
); ++idx
)
1585 constructor_elt
*c1
= &(*v1
)[idx
];
1586 constructor_elt
*c2
= &(*v2
)[idx
];
1588 /* Check that each value is the same... */
1589 if (!sem_variable::equals (c1
->value
, c2
->value
))
1591 /* ... and that they apply to the same fields! */
1592 if (!sem_variable::equals (c1
->index
, c2
->index
))
1599 tree x1
= TREE_OPERAND (t1
, 0);
1600 tree x2
= TREE_OPERAND (t2
, 0);
1601 tree y1
= TREE_OPERAND (t1
, 1);
1602 tree y2
= TREE_OPERAND (t2
, 1);
1604 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
)))
1605 return return_false ();
1607 /* Type of the offset on MEM_REF does not matter. */
1608 return return_with_debug (sem_variable::equals (x1
, x2
)
1609 && wi::to_offset (y1
)
1610 == wi::to_offset (y2
));
1615 tree op1
= TREE_OPERAND (t1
, 0);
1616 tree op2
= TREE_OPERAND (t2
, 0);
1617 return sem_variable::equals (op1
, op2
);
1619 /* References to other vars/decls are compared using ipa-ref. */
1622 if (decl_in_symtab_p (t1
) && decl_in_symtab_p (t2
))
1624 return return_false_with_msg ("Declaration mismatch");
1626 /* TODO: We can check CONST_DECL by its DECL_INITIAL, but for that we
1627 need to process its VAR/FUNCTION references without relying on ipa-ref
1631 return return_false_with_msg ("Declaration mismatch");
1633 /* Integer constants are the same only if the same width of type. */
1634 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1635 return return_false_with_msg ("INTEGER_CST precision mismatch");
1636 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1637 return return_false_with_msg ("INTEGER_CST mode mismatch");
1638 return return_with_debug (tree_int_cst_equal (t1
, t2
));
1640 if (TYPE_MODE (TREE_TYPE (t1
)) != TYPE_MODE (TREE_TYPE (t2
)))
1641 return return_false_with_msg ("STRING_CST mode mismatch");
1642 if (TREE_STRING_LENGTH (t1
) != TREE_STRING_LENGTH (t2
))
1643 return return_false_with_msg ("STRING_CST length mismatch");
1644 if (memcmp (TREE_STRING_POINTER (t1
), TREE_STRING_POINTER (t2
),
1645 TREE_STRING_LENGTH (t1
)))
1646 return return_false_with_msg ("STRING_CST mismatch");
1649 /* Fixed constants are the same only if the same width of type. */
1650 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1651 return return_false_with_msg ("FIXED_CST precision mismatch");
1653 return return_with_debug (FIXED_VALUES_IDENTICAL (TREE_FIXED_CST (t1
),
1654 TREE_FIXED_CST (t2
)));
1656 return (sem_variable::equals (TREE_REALPART (t1
), TREE_REALPART (t2
))
1657 && sem_variable::equals (TREE_IMAGPART (t1
), TREE_IMAGPART (t2
)));
1659 /* Real constants are the same only if the same width of type. */
1660 if (TYPE_PRECISION (TREE_TYPE (t1
)) != TYPE_PRECISION (TREE_TYPE (t2
)))
1661 return return_false_with_msg ("REAL_CST precision mismatch");
1662 return return_with_debug (REAL_VALUES_IDENTICAL (TREE_REAL_CST (t1
),
1663 TREE_REAL_CST (t2
)));
1668 if (VECTOR_CST_NELTS (t1
) != VECTOR_CST_NELTS (t2
))
1669 return return_false_with_msg ("VECTOR_CST nelts mismatch");
1671 for (i
= 0; i
< VECTOR_CST_NELTS (t1
); ++i
)
1672 if (!sem_variable::equals (VECTOR_CST_ELT (t1
, i
),
1673 VECTOR_CST_ELT (t2
, i
)))
1679 case ARRAY_RANGE_REF
:
1681 tree x1
= TREE_OPERAND (t1
, 0);
1682 tree x2
= TREE_OPERAND (t2
, 0);
1683 tree y1
= TREE_OPERAND (t1
, 1);
1684 tree y2
= TREE_OPERAND (t2
, 1);
1686 if (!sem_variable::equals (x1
, x2
) || !sem_variable::equals (y1
, y2
))
1688 if (!sem_variable::equals (array_ref_low_bound (t1
),
1689 array_ref_low_bound (t2
)))
1691 if (!sem_variable::equals (array_ref_element_size (t1
),
1692 array_ref_element_size (t2
)))
1698 case POINTER_PLUS_EXPR
:
1703 tree x1
= TREE_OPERAND (t1
, 0);
1704 tree x2
= TREE_OPERAND (t2
, 0);
1705 tree y1
= TREE_OPERAND (t1
, 1);
1706 tree y2
= TREE_OPERAND (t2
, 1);
1708 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1712 case VIEW_CONVERT_EXPR
:
1713 if (!func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
)))
1714 return return_false ();
1715 return sem_variable::equals (TREE_OPERAND (t1
, 0), TREE_OPERAND (t2
, 0));
1717 return return_false_with_msg ("ERROR_MARK");
1719 return return_false_with_msg ("Unknown TREE code reached");
1723 /* Parser function that visits a varpool NODE. */
1726 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1728 if (TREE_THIS_VOLATILE (node
->decl
) || DECL_HARD_REGISTER (node
->decl
)
1732 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1739 /* References independent hash function. */
1742 sem_variable::get_hash (void)
1747 /* All WPA streamed in symbols should have their hashes computed at compile
1748 time. At this point, the constructor may not be in memory at all.
1749 DECL_INITIAL (decl) would be error_mark_node in that case. */
1750 gcc_assert (!node
->lto_file_data
);
1751 tree ctor
= DECL_INITIAL (decl
);
1752 inchash::hash hstate
;
1754 hstate
.add_int (456346417);
1755 if (DECL_SIZE (decl
) && tree_fits_shwi_p (DECL_SIZE (decl
)))
1756 hstate
.add_wide_int (tree_to_shwi (DECL_SIZE (decl
)));
1757 add_expr (ctor
, hstate
);
1758 hash
= hstate
.end ();
1763 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1767 sem_variable::merge (sem_item
*alias_item
)
1769 gcc_assert (alias_item
->type
== VAR
);
1771 if (!sem_item::target_supports_symbol_aliases_p ())
1774 fprintf (dump_file
, "Not unifying; "
1775 "Symbol aliases are not supported by target\n\n");
1779 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1781 varpool_node
*original
= get_node ();
1782 varpool_node
*alias
= alias_var
->get_node ();
1783 bool original_discardable
= false;
1785 bool original_address_matters
= original
->address_matters_p ();
1786 bool alias_address_matters
= alias
->address_matters_p ();
1788 /* See if original is in a section that can be discarded if the main
1790 Also consider case where we have resolution info and we know that
1791 original's definition is not going to be used. In this case we can not
1792 create alias to original. */
1793 if (original
->can_be_discarded_p ()
1794 || (node
->resolution
!= LDPR_UNKNOWN
1795 && !decl_binds_to_current_def_p (node
->decl
)))
1796 original_discardable
= true;
1798 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1800 /* Constant pool machinery is not quite ready for aliases.
1801 TODO: varasm code contains logic for merging DECL_IN_CONSTANT_POOL.
1802 For LTO merging does not happen that is an important missing feature.
1803 We can enable merging with LTO if the DECL_IN_CONSTANT_POOL
1804 flag is dropped and non-local symbol name is assigned. */
1805 if (DECL_IN_CONSTANT_POOL (alias
->decl
)
1806 || DECL_IN_CONSTANT_POOL (original
->decl
))
1810 "Not unifying; constant pool variables.\n\n");
1814 /* Do not attempt to mix functions from different user sections;
1815 we do not know what user intends with those. */
1816 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
1817 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
1818 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
1823 "original and alias are in different sections.\n\n");
1827 /* We can not merge if address comparsion metters. */
1828 if (original_address_matters
&& alias_address_matters
1829 && flag_merge_constants
< 2)
1834 "adress of original and alias may be compared.\n\n");
1837 if (DECL_COMDAT_GROUP (original
->decl
) != DECL_COMDAT_GROUP (alias
->decl
))
1840 fprintf (dump_file
, "Not unifying; alias cannot be created; "
1841 "across comdat group boundary\n\n");
1846 if (original_discardable
)
1849 fprintf (dump_file
, "Not unifying; alias cannot be created; "
1850 "target is discardable\n\n");
1856 gcc_assert (!original
->alias
);
1857 gcc_assert (!alias
->alias
);
1859 alias
->analyzed
= false;
1861 DECL_INITIAL (alias
->decl
) = NULL
;
1862 ((symtab_node
*)alias
)->call_for_symbol_and_aliases (clear_decl_rtl
,
1864 alias
->need_bounds_init
= false;
1865 alias
->remove_all_references ();
1866 if (TREE_ADDRESSABLE (alias
->decl
))
1867 original
->call_for_symbol_and_aliases (set_addressable
, NULL
, true);
1869 varpool_node::create_alias (alias_var
->decl
, decl
);
1870 alias
->resolve_alias (original
);
1873 fprintf (dump_file
, "Unified; Variable alias has been created.\n\n");
1879 /* Dump symbol to FILE. */
1882 sem_variable::dump_to_file (FILE *file
)
1886 print_node (file
, "", decl
, 0);
1887 fprintf (file
, "\n\n");
1890 unsigned int sem_item_optimizer::class_id
= 0;
1892 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1893 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1896 bitmap_obstack_initialize (&m_bmstack
);
1899 sem_item_optimizer::~sem_item_optimizer ()
1901 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1904 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1905 it
!= m_classes
.end (); ++it
)
1907 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1908 delete (*it
)->classes
[i
];
1910 (*it
)->classes
.release ();
1916 bitmap_obstack_release (&m_bmstack
);
1919 /* Write IPA ICF summary for symbols. */
1922 sem_item_optimizer::write_summary (void)
1924 unsigned int count
= 0;
1926 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1927 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1930 /* Calculate number of symbols to be serialized. */
1931 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1933 lsei_next_in_partition (&lsei
))
1935 symtab_node
*node
= lsei_node (lsei
);
1937 if (m_symtab_node_map
.get (node
))
1941 streamer_write_uhwi (ob
, count
);
1943 /* Process all of the symbols. */
1944 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1946 lsei_next_in_partition (&lsei
))
1948 symtab_node
*node
= lsei_node (lsei
);
1950 sem_item
**item
= m_symtab_node_map
.get (node
);
1954 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1955 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1957 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1961 streamer_write_char_stream (ob
->main_stream
, 0);
1962 produce_asm (ob
, NULL
);
1963 destroy_output_block (ob
);
1966 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1967 contains LEN bytes. */
1970 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1971 const char *data
, size_t len
)
1973 const lto_function_header
*header
=
1974 (const lto_function_header
*) data
;
1975 const int cfg_offset
= sizeof (lto_function_header
);
1976 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1977 const int string_offset
= main_offset
+ header
->main_size
;
1982 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1983 header
->main_size
, file_data
->mode_table
);
1986 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1987 header
->string_size
, vNULL
);
1989 count
= streamer_read_uhwi (&ib_main
);
1991 for (i
= 0; i
< count
; i
++)
1995 lto_symtab_encoder_t encoder
;
1997 index
= streamer_read_uhwi (&ib_main
);
1998 encoder
= file_data
->symtab_node_encoder
;
1999 node
= lto_symtab_encoder_deref (encoder
, index
);
2001 hashval_t hash
= streamer_read_uhwi (&ib_main
);
2003 gcc_assert (node
->definition
);
2006 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n",
2007 node
->asm_name (), (void *) node
->decl
, node
->order
);
2009 if (is_a
<cgraph_node
*> (node
))
2011 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
2013 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
2017 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
2019 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
2023 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
2025 lto_data_in_delete (data_in
);
2028 /* Read IPA IPA ICF summary for symbols. */
2031 sem_item_optimizer::read_summary (void)
2033 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
2034 lto_file_decl_data
*file_data
;
2037 while ((file_data
= file_data_vec
[j
++]))
2040 const char *data
= lto_get_section_data (file_data
,
2041 LTO_section_ipa_icf
, NULL
, &len
);
2044 read_section (file_data
, data
, len
);
2048 /* Register callgraph and varpool hooks. */
2051 sem_item_optimizer::register_hooks (void)
2053 if (!m_cgraph_node_hooks
)
2054 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
2055 (&sem_item_optimizer::cgraph_removal_hook
, this);
2057 if (!m_varpool_node_hooks
)
2058 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
2059 (&sem_item_optimizer::varpool_removal_hook
, this);
2062 /* Unregister callgraph and varpool hooks. */
2065 sem_item_optimizer::unregister_hooks (void)
2067 if (m_cgraph_node_hooks
)
2068 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
2070 if (m_varpool_node_hooks
)
2071 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
2074 /* Adds a CLS to hashtable associated by hash value. */
2077 sem_item_optimizer::add_class (congruence_class
*cls
)
2079 gcc_assert (cls
->members
.length ());
2081 congruence_class_group
*group
= get_group_by_hash (
2082 cls
->members
[0]->get_hash (),
2083 cls
->members
[0]->type
);
2084 group
->classes
.safe_push (cls
);
2087 /* Gets a congruence class group based on given HASH value and TYPE. */
2089 congruence_class_group
*
2090 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
2092 congruence_class_group
*item
= XNEW (congruence_class_group
);
2096 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
2102 item
->classes
.create (1);
2109 /* Callgraph removal hook called for a NODE with a custom DATA. */
2112 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
2114 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2115 optimizer
->remove_symtab_node (node
);
2118 /* Varpool removal hook called for a NODE with a custom DATA. */
2121 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
2123 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
2124 optimizer
->remove_symtab_node (node
);
2127 /* Remove symtab NODE triggered by symtab removal hooks. */
2130 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
2132 gcc_assert (!m_classes
.elements());
2134 m_removed_items_set
.add (node
);
2138 sem_item_optimizer::remove_item (sem_item
*item
)
2140 if (m_symtab_node_map
.get (item
->node
))
2141 m_symtab_node_map
.remove (item
->node
);
2145 /* Removes all callgraph and varpool nodes that are marked by symtab
2149 sem_item_optimizer::filter_removed_items (void)
2151 auto_vec
<sem_item
*> filtered
;
2153 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2155 sem_item
*item
= m_items
[i
];
2157 if (m_removed_items_set
.contains (item
->node
))
2163 if (item
->type
== FUNC
)
2165 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
2167 if (in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
))
2170 filtered
.safe_push (item
);
2174 if (!flag_ipa_icf_variables
)
2178 /* Filter out non-readonly variables. */
2179 tree decl
= item
->decl
;
2180 if (TREE_READONLY (decl
))
2181 filtered
.safe_push (item
);
2188 /* Clean-up of released semantic items. */
2191 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
2192 m_items
.safe_push (filtered
[i
]);
2195 /* Optimizer entry point which returns true in case it processes
2196 a merge operation. True is returned if there's a merge operation
2200 sem_item_optimizer::execute (void)
2202 filter_removed_items ();
2203 unregister_hooks ();
2205 build_hash_based_classes ();
2208 fprintf (dump_file
, "Dump after hash based groups\n");
2209 dump_cong_classes ();
2211 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
2212 m_items
[i
]->init_wpa ();
2216 subdivide_classes_by_equality (true);
2219 fprintf (dump_file
, "Dump after WPA based types groups\n");
2221 dump_cong_classes ();
2223 process_cong_reduction ();
2227 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
2229 dump_cong_classes ();
2231 parse_nonsingleton_classes ();
2232 subdivide_classes_by_equality ();
2235 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
2237 dump_cong_classes ();
2239 unsigned int prev_class_count
= m_classes_count
;
2241 process_cong_reduction ();
2242 dump_cong_classes ();
2244 bool merged_p
= merge_classes (prev_class_count
);
2246 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2247 symtab_node::dump_table (dump_file
);
2252 /* Function responsible for visiting all potential functions and
2253 read-only variables that can be merged. */
2256 sem_item_optimizer::parse_funcs_and_vars (void)
2260 if (flag_ipa_icf_functions
)
2261 FOR_EACH_DEFINED_FUNCTION (cnode
)
2263 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
2266 m_items
.safe_push (f
);
2267 m_symtab_node_map
.put (cnode
, f
);
2270 fprintf (dump_file
, "Parsed function:%s\n", f
->node
->asm_name ());
2272 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2273 f
->dump_to_file (dump_file
);
2276 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
2279 varpool_node
*vnode
;
2281 if (flag_ipa_icf_variables
)
2282 FOR_EACH_DEFINED_VARIABLE (vnode
)
2284 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
2288 m_items
.safe_push (v
);
2289 m_symtab_node_map
.put (vnode
, v
);
2294 /* Makes pairing between a congruence class CLS and semantic ITEM. */
2297 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
2299 item
->index_in_class
= cls
->members
.length ();
2300 cls
->members
.safe_push (item
);
2304 /* Congruence classes are built by hash value. */
2307 sem_item_optimizer::build_hash_based_classes (void)
2309 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2311 sem_item
*item
= m_items
[i
];
2313 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
2316 if (!group
->classes
.length ())
2319 group
->classes
.safe_push (new congruence_class (class_id
++));
2322 add_item_to_class (group
->classes
[0], item
);
2326 /* Build references according to call graph. */
2329 sem_item_optimizer::build_graph (void)
2331 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2333 sem_item
*item
= m_items
[i
];
2334 m_symtab_node_map
.put (item
->node
, item
);
2337 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2339 sem_item
*item
= m_items
[i
];
2341 if (item
->type
== FUNC
)
2343 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
2345 cgraph_edge
*e
= cnode
->callees
;
2348 sem_item
**slot
= m_symtab_node_map
.get
2349 (e
->callee
->ultimate_alias_target ());
2351 item
->add_reference (*slot
);
2357 ipa_ref
*ref
= NULL
;
2358 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
2360 sem_item
**slot
= m_symtab_node_map
.get
2361 (ref
->referred
->ultimate_alias_target ());
2363 item
->add_reference (*slot
);
2368 /* Semantic items in classes having more than one element and initialized.
2369 In case of WPA, we load function body. */
2372 sem_item_optimizer::parse_nonsingleton_classes (void)
2374 unsigned int init_called_count
= 0;
2376 for (unsigned i
= 0; i
< m_items
.length (); i
++)
2377 if (m_items
[i
]->cls
->members
.length () > 1)
2379 m_items
[i
]->init ();
2380 init_called_count
++;
2384 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
2385 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
2388 /* Equality function for semantic items is used to subdivide existing
2389 classes. If IN_WPA, fast equality function is invoked. */
2392 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
2394 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2395 it
!= m_classes
.end (); ++it
)
2397 unsigned int class_count
= (*it
)->classes
.length ();
2399 for (unsigned i
= 0; i
< class_count
; i
++)
2401 congruence_class
*c
= (*it
)->classes
[i
];
2403 if (c
->members
.length() > 1)
2405 auto_vec
<sem_item
*> new_vector
;
2407 sem_item
*first
= c
->members
[0];
2408 new_vector
.safe_push (first
);
2410 unsigned class_split_first
= (*it
)->classes
.length ();
2412 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
2414 sem_item
*item
= c
->members
[j
];
2416 bool equals
= in_wpa
? first
->equals_wpa (item
,
2417 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
2420 new_vector
.safe_push (item
);
2423 bool integrated
= false;
2425 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
2427 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
2428 bool equals
= in_wpa
? x
->equals_wpa (item
,
2429 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
2434 add_item_to_class ((*it
)->classes
[k
], item
);
2442 congruence_class
*c
= new congruence_class (class_id
++);
2444 add_item_to_class (c
, item
);
2446 (*it
)->classes
.safe_push (c
);
2451 // we replace newly created new_vector for the class we've just splitted
2452 c
->members
.release ();
2453 c
->members
.create (new_vector
.length ());
2455 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
2456 add_item_to_class (c
, new_vector
[j
]);
2464 /* Subdivide classes by address references that members of the class
2465 reference. Example can be a pair of functions that have an address
2466 taken from a function. If these addresses are different the class
2470 sem_item_optimizer::subdivide_classes_by_sensitive_refs ()
2472 unsigned newly_created_classes
= 0;
2474 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2475 it
!= m_classes
.end (); ++it
)
2477 unsigned int class_count
= (*it
)->classes
.length ();
2478 auto_vec
<congruence_class
*> new_classes
;
2480 for (unsigned i
= 0; i
< class_count
; i
++)
2482 congruence_class
*c
= (*it
)->classes
[i
];
2484 if (c
->members
.length() > 1)
2486 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2487 symbol_compare_hashmap_traits
> split_map
;
2489 for (unsigned j
= 0; j
< c
->members
.length (); j
++)
2491 sem_item
*source_node
= c
->members
[j
];
2493 symbol_compare_collection
*collection
= new symbol_compare_collection (source_node
->node
);
2495 vec
<sem_item
*> *slot
= &split_map
.get_or_insert (collection
);
2496 gcc_checking_assert (slot
);
2498 slot
->safe_push (source_node
);
2501 /* If the map contains more than one key, we have to split the map
2503 if (split_map
.elements () != 1)
2505 bool first_class
= true;
2507 hash_map
<symbol_compare_collection
*, vec
<sem_item
*>,
2508 symbol_compare_hashmap_traits
>::iterator it2
= split_map
.begin ();
2509 for (; it2
!= split_map
.end (); ++it2
)
2511 congruence_class
*new_cls
;
2512 new_cls
= new congruence_class (class_id
++);
2514 for (unsigned k
= 0; k
< (*it2
).second
.length (); k
++)
2515 add_item_to_class (new_cls
, (*it2
).second
[k
]);
2517 worklist_push (new_cls
);
2518 newly_created_classes
++;
2522 (*it
)->classes
[i
] = new_cls
;
2523 first_class
= false;
2527 new_classes
.safe_push (new_cls
);
2535 for (unsigned i
= 0; i
< new_classes
.length (); i
++)
2536 (*it
)->classes
.safe_push (new_classes
[i
]);
2539 return newly_created_classes
;
2542 /* Verify congruence classes if checking is enabled. */
2545 sem_item_optimizer::verify_classes (void)
2548 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2549 it
!= m_classes
.end (); ++it
)
2551 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2553 congruence_class
*cls
= (*it
)->classes
[i
];
2555 gcc_checking_assert (cls
);
2556 gcc_checking_assert (cls
->members
.length () > 0);
2558 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
2560 sem_item
*item
= cls
->members
[j
];
2562 gcc_checking_assert (item
);
2563 gcc_checking_assert (item
->cls
== cls
);
2565 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
2567 sem_usage_pair
*usage
= item
->usages
[k
];
2568 gcc_checking_assert (usage
->item
->index_in_class
<
2569 usage
->item
->cls
->members
.length ());
2577 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2578 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2579 but unused argument. */
2582 sem_item_optimizer::release_split_map (congruence_class
* const &,
2583 bitmap
const &b
, traverse_split_pair
*)
2592 /* Process split operation for a class given as pointer CLS_PTR,
2593 where bitmap B splits congruence class members. DATA is used
2594 as argument of split pair. */
2597 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2598 bitmap
const &b
, traverse_split_pair
*pair
)
2600 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2601 const congruence_class
*splitter_cls
= pair
->cls
;
2603 /* If counted bits are greater than zero and less than the number of members
2604 a group will be splitted. */
2605 unsigned popcount
= bitmap_count_bits (b
);
2607 if (popcount
> 0 && popcount
< cls
->members
.length ())
2609 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2611 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2613 int target
= bitmap_bit_p (b
, i
);
2614 congruence_class
*tc
= newclasses
[target
];
2616 add_item_to_class (tc
, cls
->members
[i
]);
2619 #ifdef ENABLE_CHECKING
2620 for (unsigned int i
= 0; i
< 2; i
++)
2621 gcc_checking_assert (newclasses
[i
]->members
.length ());
2624 if (splitter_cls
== cls
)
2625 optimizer
->splitter_class_removed
= true;
2627 /* Remove old class from worklist if presented. */
2628 bool in_worklist
= cls
->in_worklist
;
2631 cls
->in_worklist
= false;
2633 congruence_class_group g
;
2634 g
.hash
= cls
->members
[0]->get_hash ();
2635 g
.type
= cls
->members
[0]->type
;
2637 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2639 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2640 if (slot
->classes
[i
] == cls
)
2642 slot
->classes
.ordered_remove (i
);
2646 /* New class will be inserted and integrated to work list. */
2647 for (unsigned int i
= 0; i
< 2; i
++)
2648 optimizer
->add_class (newclasses
[i
]);
2650 /* Two classes replace one, so that increment just by one. */
2651 optimizer
->m_classes_count
++;
2653 /* If OLD class was presented in the worklist, we remove the class
2654 and replace it will both newly created classes. */
2656 for (unsigned int i
= 0; i
< 2; i
++)
2657 optimizer
->worklist_push (newclasses
[i
]);
2658 else /* Just smaller class is inserted. */
2660 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2661 newclasses
[1]->members
.length () ?
2663 optimizer
->worklist_push (newclasses
[smaller_index
]);
2666 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2668 fprintf (dump_file
, " congruence class splitted:\n");
2669 cls
->dump (dump_file
, 4);
2671 fprintf (dump_file
, " newly created groups:\n");
2672 for (unsigned int i
= 0; i
< 2; i
++)
2673 newclasses
[i
]->dump (dump_file
, 4);
2676 /* Release class if not presented in work list. */
2685 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2686 Bitmap stack BMSTACK is used for bitmap allocation. */
2689 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2692 hash_map
<congruence_class
*, bitmap
> split_map
;
2694 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2696 sem_item
*item
= cls
->members
[i
];
2698 /* Iterate all usages that have INDEX as usage of the item. */
2699 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2701 sem_usage_pair
*usage
= item
->usages
[j
];
2703 if (usage
->index
!= index
)
2706 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2711 b
= BITMAP_ALLOC (&m_bmstack
);
2712 split_map
.put (usage
->item
->cls
, b
);
2718 gcc_checking_assert (usage
->item
->cls
);
2719 gcc_checking_assert (usage
->item
->index_in_class
<
2720 usage
->item
->cls
->members
.length ());
2723 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2727 traverse_split_pair pair
;
2728 pair
.optimizer
= this;
2731 splitter_class_removed
= false;
2733 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2735 /* Bitmap clean-up. */
2737 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2740 /* Every usage of a congruence class CLS is a candidate that can split the
2741 collection of classes. Bitmap stack BMSTACK is used for bitmap
2745 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2750 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2752 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2753 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2755 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2757 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2758 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2761 do_congruence_step_for_index (cls
, i
);
2763 if (splitter_class_removed
)
2767 BITMAP_FREE (usage
);
2770 /* Adds a newly created congruence class CLS to worklist. */
2773 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2775 /* Return if the class CLS is already presented in work list. */
2776 if (cls
->in_worklist
)
2779 cls
->in_worklist
= true;
2780 worklist
.push_back (cls
);
2783 /* Pops a class from worklist. */
2786 sem_item_optimizer::worklist_pop (void)
2788 congruence_class
*cls
;
2790 while (!worklist
.empty ())
2792 cls
= worklist
.front ();
2793 worklist
.pop_front ();
2794 if (cls
->in_worklist
)
2796 cls
->in_worklist
= false;
2802 /* Work list item was already intended to be removed.
2803 The only reason for doing it is to split a class.
2804 Thus, the class CLS is deleted. */
2812 /* Iterative congruence reduction function. */
2815 sem_item_optimizer::process_cong_reduction (void)
2817 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2818 it
!= m_classes
.end (); ++it
)
2819 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2820 if ((*it
)->classes
[i
]->is_class_used ())
2821 worklist_push ((*it
)->classes
[i
]);
2824 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2825 (unsigned long) worklist
.size ());
2827 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2828 fprintf (dump_file
, "Congruence class reduction\n");
2830 congruence_class
*cls
;
2832 /* Process complete congruence reduction. */
2833 while ((cls
= worklist_pop ()) != NULL
)
2834 do_congruence_step (cls
);
2836 /* Subdivide newly created classes according to references. */
2837 unsigned new_classes
= subdivide_classes_by_sensitive_refs ();
2840 fprintf (dump_file
, "Address reference subdivision created: %u "
2841 "new classes.\n", new_classes
);
2844 /* Debug function prints all informations about congruence classes. */
2847 sem_item_optimizer::dump_cong_classes (void)
2853 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2854 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2856 /* Histogram calculation. */
2857 unsigned int max_index
= 0;
2858 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2860 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2861 it
!= m_classes
.end (); ++it
)
2863 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2865 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2873 "Class size histogram [num of members]: number of classe number of classess\n");
2875 for (unsigned int i
= 0; i
<= max_index
; i
++)
2877 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2879 fprintf (dump_file
, "\n\n");
2882 if (dump_flags
& TDF_DETAILS
)
2883 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2884 it
!= m_classes
.end (); ++it
)
2886 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2888 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2890 (*it
)->classes
[i
]->dump (dump_file
, 4);
2892 if(i
< (*it
)->classes
.length () - 1)
2893 fprintf (dump_file
, " ");
2900 /* After reduction is done, we can declare all items in a group
2901 to be equal. PREV_CLASS_COUNT is start number of classes
2902 before reduction. True is returned if there's a merge operation
2906 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2908 unsigned int item_count
= m_items
.length ();
2909 unsigned int class_count
= m_classes_count
;
2910 unsigned int equal_items
= item_count
- class_count
;
2912 unsigned int non_singular_classes_count
= 0;
2913 unsigned int non_singular_classes_sum
= 0;
2915 bool merged_p
= false;
2917 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2918 it
!= m_classes
.end (); ++it
)
2919 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2921 congruence_class
*c
= (*it
)->classes
[i
];
2922 if (c
->members
.length () > 1)
2924 non_singular_classes_count
++;
2925 non_singular_classes_sum
+= c
->members
.length ();
2931 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2932 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2933 prev_class_count
, class_count
);
2934 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2935 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2936 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2937 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2938 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2939 non_singular_classes_count
: 0.0f
,
2940 non_singular_classes_count
);
2941 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2942 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2943 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2946 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2947 it
!= m_classes
.end (); ++it
)
2948 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2950 congruence_class
*c
= (*it
)->classes
[i
];
2952 if (c
->members
.length () == 1)
2955 gcc_assert (c
->members
.length ());
2957 sem_item
*source
= c
->members
[0];
2959 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2961 sem_item
*alias
= c
->members
[j
];
2965 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2966 xstrdup_for_dump (source
->node
->name ()),
2967 xstrdup_for_dump (alias
->node
->name ()));
2968 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2969 xstrdup_for_dump (source
->node
->asm_name ()),
2970 xstrdup_for_dump (alias
->node
->asm_name ()));
2973 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
2977 "Merge operation is skipped due to no_icf "
2983 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2985 source
->dump_to_file (dump_file
);
2986 alias
->dump_to_file (dump_file
);
2989 merged_p
|= source
->merge (alias
);
2996 /* Dump function prints all class members to a FILE with an INDENT. */
2999 congruence_class::dump (FILE *file
, unsigned int indent
) const
3001 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
3002 id
, members
[0]->get_hash (), members
.length ());
3004 FPUTS_SPACES (file
, indent
+ 2, "");
3005 for (unsigned i
= 0; i
< members
.length (); i
++)
3006 fprintf (file
, "%s(%p/%u) ", members
[i
]->node
->asm_name (),
3007 (void *) members
[i
]->decl
,
3008 members
[i
]->node
->order
);
3010 fprintf (file
, "\n");
3013 /* Returns true if there's a member that is used from another group. */
3016 congruence_class::is_class_used (void)
3018 for (unsigned int i
= 0; i
< members
.length (); i
++)
3019 if (members
[i
]->usages
.length ())
3025 /* Initialization and computation of symtab node hash, there data
3026 are propagated later on. */
3028 static sem_item_optimizer
*optimizer
= NULL
;
3030 /* Generate pass summary for IPA ICF pass. */
3033 ipa_icf_generate_summary (void)
3036 optimizer
= new sem_item_optimizer ();
3038 optimizer
->register_hooks ();
3039 optimizer
->parse_funcs_and_vars ();
3042 /* Write pass summary for IPA ICF pass. */
3045 ipa_icf_write_summary (void)
3047 gcc_assert (optimizer
);
3049 optimizer
->write_summary ();
3052 /* Read pass summary for IPA ICF pass. */
3055 ipa_icf_read_summary (void)
3058 optimizer
= new sem_item_optimizer ();
3060 optimizer
->read_summary ();
3061 optimizer
->register_hooks ();
3064 /* Semantic equality exection function. */
3067 ipa_icf_driver (void)
3069 gcc_assert (optimizer
);
3071 bool merged_p
= optimizer
->execute ();
3076 return merged_p
? TODO_remove_functions
: 0;
3079 const pass_data pass_data_ipa_icf
=
3081 IPA_PASS
, /* type */
3083 OPTGROUP_IPA
, /* optinfo_flags */
3084 TV_IPA_ICF
, /* tv_id */
3085 0, /* properties_required */
3086 0, /* properties_provided */
3087 0, /* properties_destroyed */
3088 0, /* todo_flags_start */
3089 0, /* todo_flags_finish */
3092 class pass_ipa_icf
: public ipa_opt_pass_d
3095 pass_ipa_icf (gcc::context
*ctxt
)
3096 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
3097 ipa_icf_generate_summary
, /* generate_summary */
3098 ipa_icf_write_summary
, /* write_summary */
3099 ipa_icf_read_summary
, /* read_summary */
3101 write_optimization_summary */
3103 read_optimization_summary */
3104 NULL
, /* stmt_fixup */
3105 0, /* function_transform_todo_flags_start */
3106 NULL
, /* function_transform */
3107 NULL
) /* variable_transform */
3110 /* opt_pass methods: */
3111 virtual bool gate (function
*)
3113 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
3116 virtual unsigned int execute (function
*)
3118 return ipa_icf_driver();
3120 }; // class pass_ipa_icf
3122 } // ipa_icf namespace
3125 make_pass_ipa_icf (gcc::context
*ctxt
)
3127 return new ipa_icf::pass_ipa_icf (ctxt
);