1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014-2015 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka <hubicka@ucw.cz> and Martin Liska <mliska@suse.cz>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Interprocedural Identical Code Folding for functions and
25 The goal of this transformation is to discover functions and read-only
26 variables which do have exactly the same semantics.
29 we could either create a virtual clone or do a simple function wrapper
30 that will call equivalent function. If the function is just locally visible,
31 all function calls can be redirected. For read-only variables, we create
34 Optimization pass arranges as follows:
35 1) All functions and read-only variables are visited and internal
36 data structure, either sem_function or sem_variables is created.
37 2) For every symbol from the previous step, VAR_DECL and FUNCTION_DECL are
38 saved and matched to corresponding sem_items.
39 3) These declaration are ignored for equality check and are solved
40 by Value Numbering algorithm published by Alpert, Zadeck in 1992.
41 4) We compute hash value for each symbol.
42 5) Congruence classes are created based on hash value. If hash value are
43 equal, equals function is called and symbols are deeply compared.
44 We must prove that all SSA names, declarations and other items
46 6) Value Numbering is executed for these classes. At the end of the process
47 all symbol members in remaining classes can be merged.
48 7) Merge operation creates alias in case of read-only variables. For
49 callgraph node, we must decide if we can redirect local calls,
50 create an alias or a thunk.
56 #include "coretypes.h"
60 #include "double-int.h"
68 #include "fold-const.h"
71 #include "hard-reg-set.h"
73 #include "dominance.h"
75 #include "basic-block.h"
76 #include "tree-ssa-alias.h"
77 #include "internal-fn.h"
78 #include "gimple-expr.h"
84 #include "statistics.h"
86 #include "fixed-value.h"
87 #include "insn-config.h"
96 #include "gimple-iterator.h"
97 #include "gimple-ssa.h"
99 #include "tree-phinodes.h"
100 #include "stringpool.h"
101 #include "tree-ssanames.h"
102 #include "tree-dfa.h"
103 #include "tree-pass.h"
104 #include "gimple-pretty-print.h"
105 #include "hash-map.h"
106 #include "plugin-api.h"
109 #include "alloc-pool.h"
110 #include "symbol-summary.h"
111 #include "ipa-prop.h"
112 #include "ipa-inline.h"
115 #include "hash-table.h"
116 #include "coverage.h"
118 #include "print-tree.h"
119 #include "lto-streamer.h"
120 #include "data-streamer.h"
121 #include "ipa-utils.h"
123 #include "ipa-icf-gimple.h"
126 using namespace ipa_icf_gimple
;
129 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
131 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
132 item (_item
), index (_index
)
136 /* Semantic item constructor for a node of _TYPE, where STACK is used
137 for bitmap memory allocation. */
139 sem_item::sem_item (sem_item_type _type
,
140 bitmap_obstack
*stack
): type(_type
), hash(0)
145 /* Semantic item constructor for a node of _TYPE, where STACK is used
146 for bitmap memory allocation. The item is based on symtab node _NODE
147 with computed _HASH. */
149 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
150 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
151 node (_node
), hash (_hash
)
157 /* Add reference to a semantic TARGET. */
160 sem_item::add_reference (sem_item
*target
)
162 refs
.safe_push (target
);
163 unsigned index
= refs
.length ();
164 target
->usages
.safe_push (new sem_usage_pair(this, index
));
165 bitmap_set_bit (target
->usage_index_bitmap
, index
);
166 refs_set
.add (target
->node
);
169 /* Initialize internal data structures. Bitmap STACK is used for
170 bitmap memory allocation process. */
173 sem_item::setup (bitmap_obstack
*stack
)
175 gcc_checking_assert (node
);
178 tree_refs
.create (0);
180 usage_index_bitmap
= BITMAP_ALLOC (stack
);
183 sem_item::~sem_item ()
185 for (unsigned i
= 0; i
< usages
.length (); i
++)
189 tree_refs
.release ();
192 BITMAP_FREE (usage_index_bitmap
);
195 /* Dump function for debugging purpose. */
198 sem_item::dump (void)
202 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
203 name(), node
->order
, (void *) node
->decl
);
204 fprintf (dump_file
, " hash: %u\n", get_hash ());
205 fprintf (dump_file
, " references: ");
207 for (unsigned i
= 0; i
< refs
.length (); i
++)
208 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
209 i
< refs
.length() - 1 ? "," : "");
211 fprintf (dump_file
, "\n");
215 /* Return true if target supports alias symbols. */
218 sem_item::target_supports_symbol_aliases_p (void)
220 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
227 /* Semantic function constructor that uses STACK as bitmap memory stack. */
229 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
230 m_checker (NULL
), m_compared_func (NULL
)
232 arg_types
.create (0);
234 bb_sorted
.create (0);
237 /* Constructor based on callgraph node _NODE with computed hash _HASH.
238 Bitmap STACK is used for memory allocation. */
239 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
240 bitmap_obstack
*stack
):
241 sem_item (FUNC
, node
, hash
, stack
),
242 m_checker (NULL
), m_compared_func (NULL
)
244 arg_types
.create (0);
246 bb_sorted
.create (0);
249 sem_function::~sem_function ()
251 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
252 delete (bb_sorted
[i
]);
254 arg_types
.release ();
256 bb_sorted
.release ();
259 /* Calculates hash value based on a BASIC_BLOCK. */
262 sem_function::get_bb_hash (const sem_bb
*basic_block
)
264 inchash::hash hstate
;
266 hstate
.add_int (basic_block
->nondbg_stmt_count
);
267 hstate
.add_int (basic_block
->edge_count
);
269 return hstate
.end ();
272 /* References independent hash function. */
275 sem_function::get_hash (void)
279 inchash::hash hstate
;
280 hstate
.add_int (177454); /* Random number for function type. */
282 hstate
.add_int (arg_count
);
283 hstate
.add_int (cfg_checksum
);
284 hstate
.add_int (gcode_hash
);
286 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
287 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
289 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
290 hstate
.add_int (bb_sizes
[i
]);
292 hash
= hstate
.end ();
298 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
299 point to a same function. Comparison can be skipped if IGNORED_NODES
300 contains these nodes. */
303 sem_function::compare_cgraph_references (hash_map
<symtab_node
*, sem_item
*>
305 symtab_node
*n1
, symtab_node
*n2
)
307 if (n1
== n2
|| (ignored_nodes
.get (n1
) && ignored_nodes
.get (n2
)))
310 /* TODO: add more precise comparison for weakrefs, etc. */
312 return return_false_with_msg ("different references");
315 /* If cgraph edges E1 and E2 are indirect calls, verify that
316 ECF flags are the same. */
318 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
320 if (e1
->indirect_info
&& e2
->indirect_info
)
322 int e1_flags
= e1
->indirect_info
->ecf_flags
;
323 int e2_flags
= e2
->indirect_info
->ecf_flags
;
325 if (e1_flags
!= e2_flags
)
326 return return_false_with_msg ("ICF flags are different");
328 else if (e1
->indirect_info
|| e2
->indirect_info
)
334 /* Fast equality function based on knowledge known in WPA. */
337 sem_function::equals_wpa (sem_item
*item
,
338 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
340 gcc_assert (item
->type
== FUNC
);
342 m_compared_func
= static_cast<sem_function
*> (item
);
344 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
345 return return_false_with_msg ("different number of arguments");
347 /* Checking types of arguments. */
348 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
350 /* This guard is here for function pointer with attributes (pr59927.c). */
351 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
352 return return_false_with_msg ("NULL argument type");
354 /* Polymorphic comparison is executed just for non-leaf functions. */
355 bool is_not_leaf
= get_node ()->callees
!= NULL
356 || get_node ()->indirect_calls
!= NULL
;
358 if (!func_checker::compatible_types_p (arg_types
[i
],
359 m_compared_func
->arg_types
[i
],
360 is_not_leaf
, i
== 0))
361 return return_false_with_msg ("argument type is different");
364 /* Result type checking. */
365 if (!func_checker::compatible_types_p (result_type
,
366 m_compared_func
->result_type
))
367 return return_false_with_msg ("result types are different");
369 if (node
->num_references () != item
->node
->num_references ())
370 return return_false_with_msg ("different number of references");
372 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
373 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
375 item
->node
->iterate_reference (i
, ref2
);
377 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
, ref2
->referred
))
381 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
382 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
386 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
, e2
->callee
))
389 e1
= e1
->next_callee
;
390 e2
= e2
->next_callee
;
394 return return_false_with_msg ("different number of edges");
399 /* Returns true if the item equals to ITEM given as argument. */
402 sem_function::equals (sem_item
*item
,
403 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
405 gcc_assert (item
->type
== FUNC
);
406 bool eq
= equals_private (item
, ignored_nodes
);
408 if (m_checker
!= NULL
)
414 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
416 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
417 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
418 item
->asm_name (), eq
? "true" : "false");
423 /* Processes function equality comparison. */
426 sem_function::equals_private (sem_item
*item
,
427 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
429 if (item
->type
!= FUNC
)
432 basic_block bb1
, bb2
;
434 edge_iterator ei1
, ei2
;
438 m_compared_func
= static_cast<sem_function
*> (item
);
440 gcc_assert (decl
!= item
->decl
);
442 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
443 || edge_count
!= m_compared_func
->edge_count
444 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
445 return return_false ();
447 if (!equals_wpa (item
, ignored_nodes
))
450 /* Checking function TARGET and OPTIMIZATION flags. */
451 cl_target_option
*tar1
= target_opts_for_fn (decl
);
452 cl_target_option
*tar2
= target_opts_for_fn (m_compared_func
->decl
);
454 if (tar1
!= NULL
&& tar2
!= NULL
)
456 if (!cl_target_option_eq (tar1
, tar2
))
458 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
460 fprintf (dump_file
, "target flags difference");
461 cl_target_option_print_diff (dump_file
, 2, tar1
, tar2
);
464 return return_false_with_msg ("Target flags are different");
467 else if (tar1
!= NULL
|| tar2
!= NULL
)
468 return return_false_with_msg ("Target flags are different");
470 cl_optimization
*opt1
= opts_for_fn (decl
);
471 cl_optimization
*opt2
= opts_for_fn (m_compared_func
->decl
);
473 if (opt1
!= NULL
&& opt2
!= NULL
)
475 if (memcmp (opt1
, opt2
, sizeof(cl_optimization
)))
477 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
479 fprintf (dump_file
, "optimization flags difference");
480 cl_optimization_print_diff (dump_file
, 2, opt1
, opt2
);
483 return return_false_with_msg ("optimization flags are different");
486 else if (opt1
!= NULL
|| opt2
!= NULL
)
487 return return_false_with_msg ("optimization flags are different");
489 /* Checking function arguments. */
490 tree decl1
= DECL_ATTRIBUTES (decl
);
491 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
493 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
494 compare_polymorphic_p (),
497 &m_compared_func
->refs_set
);
501 return return_false ();
503 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
504 return return_false ();
506 tree attr_value1
= TREE_VALUE (decl1
);
507 tree attr_value2
= TREE_VALUE (decl2
);
509 if (attr_value1
&& attr_value2
)
511 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
512 TREE_VALUE (attr_value2
));
514 return return_false_with_msg ("attribute values are different");
516 else if (!attr_value1
&& !attr_value2
)
519 return return_false ();
521 decl1
= TREE_CHAIN (decl1
);
522 decl2
= TREE_CHAIN (decl2
);
526 return return_false();
529 for (arg1
= DECL_ARGUMENTS (decl
),
530 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
531 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
532 if (!m_checker
->compare_decl (arg1
, arg2
))
533 return return_false ();
535 /* Fill-up label dictionary. */
536 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
538 m_checker
->parse_labels (bb_sorted
[i
]);
539 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
542 /* Checking all basic blocks. */
543 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
544 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
545 return return_false();
547 dump_message ("All BBs are equal\n");
549 auto_vec
<int> bb_dict
;
551 /* Basic block edges check. */
552 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
554 bb1
= bb_sorted
[i
]->bb
;
555 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
557 ei2
= ei_start (bb2
->preds
);
559 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
563 if (e1
->flags
!= e2
->flags
)
564 return return_false_with_msg ("flags comparison returns false");
566 if (!bb_dict_test (bb_dict
, e1
->src
->index
, e2
->src
->index
))
567 return return_false_with_msg ("edge comparison returns false");
569 if (!bb_dict_test (bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
570 return return_false_with_msg ("BB comparison returns false");
572 if (!m_checker
->compare_edge (e1
, e2
))
573 return return_false_with_msg ("edge comparison returns false");
579 /* Basic block PHI nodes comparison. */
580 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
581 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
582 return return_false_with_msg ("PHI node comparison returns false");
587 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
590 sem_function::merge (sem_item
*alias_item
)
592 gcc_assert (alias_item
->type
== FUNC
);
594 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
596 cgraph_node
*original
= get_node ();
597 cgraph_node
*local_original
= original
;
598 cgraph_node
*alias
= alias_func
->get_node ();
599 bool original_address_matters
;
600 bool alias_address_matters
;
602 bool create_thunk
= false;
603 bool create_alias
= false;
604 bool redirect_callers
= false;
605 bool original_discardable
= false;
607 /* Do not attempt to mix functions from different user sections;
608 we do not know what user intends with those. */
609 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
610 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
611 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
615 "Not unifying; original and alias are in different sections.\n\n");
619 /* See if original is in a section that can be discarded if the main
620 symbol is not used. */
621 if (DECL_EXTERNAL (original
->decl
))
622 original_discardable
= true;
623 if (original
->resolution
== LDPR_PREEMPTED_REG
624 || original
->resolution
== LDPR_PREEMPTED_IR
)
625 original_discardable
= true;
626 if (original
->can_be_discarded_p ())
627 original_discardable
= true;
629 /* See if original and/or alias address can be compared for equality. */
630 original_address_matters
631 = (!DECL_VIRTUAL_P (original
->decl
)
632 && (original
->externally_visible
633 || original
->address_taken_from_non_vtable_p ()));
634 alias_address_matters
635 = (!DECL_VIRTUAL_P (alias
->decl
)
636 && (alias
->externally_visible
637 || alias
->address_taken_from_non_vtable_p ()));
639 /* If alias and original can be compared for address equality, we need
640 to create a thunk. Also we can not create extra aliases into discardable
641 section (or we risk link failures when section is discarded). */
642 if ((original_address_matters
643 && alias_address_matters
)
644 || original_discardable
)
646 create_thunk
= !stdarg_p (TREE_TYPE (alias
->decl
));
647 create_alias
= false;
648 /* When both alias and original are not overwritable, we can save
649 the extra thunk wrapper for direct calls. */
651 = (!original_discardable
652 && alias
->get_availability () > AVAIL_INTERPOSABLE
653 && original
->get_availability () > AVAIL_INTERPOSABLE
654 && !alias
->instrumented_version
);
659 create_thunk
= false;
660 redirect_callers
= false;
663 if (create_alias
&& (DECL_COMDAT_GROUP (alias
->decl
)
664 || !sem_item::target_supports_symbol_aliases_p ()))
666 create_alias
= false;
670 /* We want thunk to always jump to the local function body
671 unless the body is comdat and may be optimized out. */
672 if ((create_thunk
|| redirect_callers
)
673 && (!original_discardable
674 || (DECL_COMDAT_GROUP (original
->decl
)
675 && (DECL_COMDAT_GROUP (original
->decl
)
676 == DECL_COMDAT_GROUP (alias
->decl
)))))
678 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
683 fprintf (dump_file
, "Noninterposable alias cannot be created.\n\n");
688 if (!decl_binds_to_current_def_p (alias
->decl
))
691 fprintf (dump_file
, "Declaration does not bind to currect definition.\n\n");
695 if (redirect_callers
)
697 /* If alias is non-overwritable then
698 all direct calls are safe to be redirected to the original. */
699 bool redirected
= false;
700 while (alias
->callers
)
702 cgraph_edge
*e
= alias
->callers
;
703 e
->redirect_callee (local_original
);
704 push_cfun (DECL_STRUCT_FUNCTION (e
->caller
->decl
));
707 e
->redirect_call_stmt_to_callee ();
713 alias
->icf_merged
= true;
715 /* The alias function is removed if symbol address
717 if (!alias_address_matters
)
720 if (dump_file
&& redirected
)
721 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
723 /* If the condtion above is not met, we are lucky and can turn the
724 function into real alias. */
725 else if (create_alias
)
727 alias
->icf_merged
= true;
729 /* Remove the function's body. */
730 ipa_merge_profiles (original
, alias
);
731 alias
->release_body (true);
734 /* Create the alias. */
735 cgraph_node::create_alias (alias_func
->decl
, decl
);
736 alias
->resolve_alias (original
);
738 /* Workaround for PR63566 that forces equal calling convention
740 alias
->local
.local
= false;
741 original
->local
.local
= false;
744 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
746 else if (create_thunk
)
748 if (DECL_COMDAT_GROUP (alias
->decl
))
751 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
756 if (DECL_STATIC_CHAIN (alias
->decl
))
759 fprintf (dump_file
, "Thunk creation is risky for static-chain functions.\n\n");
764 alias
->icf_merged
= true;
765 ipa_merge_profiles (local_original
, alias
);
766 alias
->create_wrapper (local_original
);
769 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
772 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
777 /* Semantic item initialization function. */
780 sem_function::init (void)
783 get_node ()->get_untransformed_body ();
785 tree fndecl
= node
->decl
;
786 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
789 gcc_assert (SSANAMES (func
));
791 ssa_names_size
= SSANAMES (func
)->length ();
795 region_tree
= func
->eh
->region_tree
;
797 /* iterating all function arguments. */
798 arg_count
= count_formal_params (fndecl
);
800 edge_count
= n_edges_for_fn (func
);
801 cfg_checksum
= coverage_compute_cfg_checksum (func
);
803 inchash::hash hstate
;
806 FOR_EACH_BB_FN (bb
, func
)
808 unsigned nondbg_stmt_count
= 0;
811 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
812 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
815 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
818 gimple stmt
= gsi_stmt (gsi
);
820 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
822 hash_stmt (&hstate
, stmt
);
827 gcode_hash
= hstate
.end ();
828 bb_sizes
.safe_push (nondbg_stmt_count
);
830 /* Inserting basic block to hash table. */
831 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
832 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
834 bb_sorted
.safe_push (semantic_bb
);
840 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
843 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
845 enum gimple_code code
= gimple_code (stmt
);
847 hstate
->add_int (code
);
849 if (code
== GIMPLE_CALL
)
851 /* Checking of argument. */
852 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
854 tree argument
= gimple_call_arg (stmt
, i
);
856 switch (TREE_CODE (argument
))
859 if (tree_fits_shwi_p (argument
))
860 hstate
->add_wide_int (tree_to_shwi (argument
));
861 else if (tree_fits_uhwi_p (argument
))
862 hstate
->add_wide_int (tree_to_uhwi (argument
));
868 c
= TREE_REAL_CST (argument
);
869 n
= real_to_integer (&c
);
871 hstate
->add_wide_int (n
);
875 tree addr_operand
= TREE_OPERAND (argument
, 0);
877 if (TREE_CODE (addr_operand
) == STRING_CST
)
878 hstate
->add (TREE_STRING_POINTER (addr_operand
),
879 TREE_STRING_LENGTH (addr_operand
));
890 /* Return true if polymorphic comparison must be processed. */
893 sem_function::compare_polymorphic_p (void)
895 return get_node ()->callees
!= NULL
896 || get_node ()->indirect_calls
!= NULL
897 || m_compared_func
->get_node ()->callees
!= NULL
898 || m_compared_func
->get_node ()->indirect_calls
!= NULL
;
901 /* For a given call graph NODE, the function constructs new
902 semantic function item. */
905 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
907 tree fndecl
= node
->decl
;
908 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
910 /* TODO: add support for thunks and aliases. */
912 if (!func
|| !node
->has_gimple_body_p ())
915 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
918 sem_function
*f
= new sem_function (node
, 0, stack
);
925 /* Parses function arguments and result type. */
928 sem_function::parse_tree_args (void)
932 if (arg_types
.exists ())
933 arg_types
.release ();
935 arg_types
.create (4);
936 tree fnargs
= DECL_ARGUMENTS (decl
);
938 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
939 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
941 /* Function result type. */
942 result
= DECL_RESULT (decl
);
943 result_type
= result
? TREE_TYPE (result
) : NULL
;
945 /* During WPA, we can get arguments by following method. */
948 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
949 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
950 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
952 result_type
= TREE_TYPE (TREE_TYPE (decl
));
956 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
957 return true if phi nodes are semantically equivalent in these blocks . */
960 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
962 gphi_iterator si1
, si2
;
964 unsigned size1
, size2
, i
;
968 gcc_assert (bb1
!= NULL
);
969 gcc_assert (bb2
!= NULL
);
971 si2
= gsi_start_phis (bb2
);
972 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
975 gsi_next_nonvirtual_phi (&si1
);
976 gsi_next_nonvirtual_phi (&si2
);
978 if (gsi_end_p (si1
) && gsi_end_p (si2
))
981 if (gsi_end_p (si1
) || gsi_end_p (si2
))
982 return return_false();
987 tree phi_result1
= gimple_phi_result (phi1
);
988 tree phi_result2
= gimple_phi_result (phi2
);
990 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
991 return return_false_with_msg ("PHI results are different");
993 size1
= gimple_phi_num_args (phi1
);
994 size2
= gimple_phi_num_args (phi2
);
997 return return_false ();
999 for (i
= 0; i
< size1
; ++i
)
1001 t1
= gimple_phi_arg (phi1
, i
)->def
;
1002 t2
= gimple_phi_arg (phi2
, i
)->def
;
1004 if (!m_checker
->compare_operand (t1
, t2
))
1005 return return_false ();
1007 e1
= gimple_phi_arg_edge (phi1
, i
);
1008 e2
= gimple_phi_arg_edge (phi2
, i
);
1010 if (!m_checker
->compare_edge (e1
, e2
))
1011 return return_false ();
1020 /* Returns true if tree T can be compared as a handled component. */
1023 sem_function::icf_handled_component_p (tree t
)
1025 tree_code tc
= TREE_CODE (t
);
1027 return ((handled_component_p (t
))
1028 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1029 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1032 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1033 corresponds to TARGET. */
1036 sem_function::bb_dict_test (auto_vec
<int> bb_dict
, int source
, int target
)
1041 if (bb_dict
.length () <= (unsigned)source
)
1042 bb_dict
.safe_grow_cleared (source
+ 1);
1044 if (bb_dict
[source
] == 0)
1046 bb_dict
[source
] = target
;
1050 return bb_dict
[source
] == target
;
1053 /* Iterates all tree types in T1 and T2 and returns true if all types
1054 are compatible. If COMPARE_POLYMORPHIC is set to true,
1055 more strict comparison is executed. */
1058 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
1066 while (t1
!= NULL
&& t2
!= NULL
)
1068 tv1
= TREE_VALUE (t1
);
1069 tv2
= TREE_VALUE (t2
);
1071 tc1
= TREE_CODE (tv1
);
1072 tc2
= TREE_CODE (tv2
);
1074 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
1076 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
1078 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
1081 t1
= TREE_CHAIN (t1
);
1082 t2
= TREE_CHAIN (t2
);
1089 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1091 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1095 /* Constructor based on varpool node _NODE with computed hash _HASH.
1096 Bitmap STACK is used for memory allocation. */
1098 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1099 bitmap_obstack
*stack
): sem_item(VAR
,
1102 gcc_checking_assert (node
);
1103 gcc_checking_assert (get_node ());
1106 /* Returns true if the item equals to ITEM given as argument. */
1109 sem_variable::equals (sem_item
*item
,
1110 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1112 gcc_assert (item
->type
== VAR
);
1114 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1116 if (!ctor
|| !v
->ctor
)
1117 return return_false_with_msg ("ctor is missing for semantic variable");
1119 return sem_variable::equals (ctor
, v
->ctor
);
1122 /* Compares trees T1 and T2 for semantic equality. */
1125 sem_variable::equals (tree t1
, tree t2
)
1127 tree_code tc1
= TREE_CODE (t1
);
1128 tree_code tc2
= TREE_CODE (t2
);
1137 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1138 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1143 for (unsigned i
= 0; i
< len1
; i
++)
1144 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1145 CONSTRUCTOR_ELT (t2
, i
)->value
)
1146 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1153 tree x1
= TREE_OPERAND (t1
, 0);
1154 tree x2
= TREE_OPERAND (t2
, 0);
1155 tree y1
= TREE_OPERAND (t1
, 1);
1156 tree y2
= TREE_OPERAND (t2
, 1);
1158 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1160 return return_false ();
1162 /* Type of the offset on MEM_REF does not matter. */
1163 return sem_variable::equals (x1
, x2
)
1164 && wi::to_offset (y1
) == wi::to_offset (y2
);
1169 tree op1
= TREE_OPERAND (t1
, 0);
1170 tree op2
= TREE_OPERAND (t2
, 0);
1171 return sem_variable::equals (op1
, op2
);
1179 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1181 && wi::to_offset (t1
) == wi::to_offset (t2
);
1185 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1188 case POINTER_PLUS_EXPR
:
1190 tree x1
= TREE_OPERAND (t1
, 0);
1191 tree x2
= TREE_OPERAND (t2
, 0);
1192 tree y1
= TREE_OPERAND (t1
, 1);
1193 tree y2
= TREE_OPERAND (t2
, 1);
1195 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1198 return return_false_with_msg ("ERROR_MARK");
1200 return return_false_with_msg ("Unknown TREE code reached");
1204 /* Parser function that visits a varpool NODE. */
1207 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1209 tree decl
= node
->decl
;
1211 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1215 bool can_handle
= DECL_VIRTUAL_P (decl
)
1216 || flag_merge_constants
>= 2
1217 || (!TREE_ADDRESSABLE (decl
) && !node
->externally_visible
);
1219 if (!can_handle
|| DECL_EXTERNAL (decl
))
1222 tree ctor
= ctor_for_folding (decl
);
1226 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1233 /* References independent hash function. */
1236 sem_variable::get_hash (void)
1241 inchash::hash hstate
;
1243 hstate
.add_int (456346417);
1244 hstate
.add_int (TREE_CODE (ctor
));
1246 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1248 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1249 hstate
.add_int (length
);
1252 hash
= hstate
.end ();
1257 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1261 sem_variable::merge (sem_item
*alias_item
)
1263 gcc_assert (alias_item
->type
== VAR
);
1265 if (!sem_item::target_supports_symbol_aliases_p ())
1268 fprintf (dump_file
, "Symbol aliases are not supported by target\n\n");
1272 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1274 varpool_node
*original
= get_node ();
1275 varpool_node
*alias
= alias_var
->get_node ();
1276 bool original_discardable
= false;
1278 /* See if original is in a section that can be discarded if the main
1279 symbol is not used. */
1280 if (DECL_EXTERNAL (original
->decl
))
1281 original_discardable
= true;
1282 if (original
->resolution
== LDPR_PREEMPTED_REG
1283 || original
->resolution
== LDPR_PREEMPTED_IR
)
1284 original_discardable
= true;
1285 if (original
->can_be_discarded_p ())
1286 original_discardable
= true;
1288 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1290 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1291 !compare_sections (alias_var
))
1294 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1300 // alias cycle creation check
1301 varpool_node
*n
= original
;
1305 n
= n
->get_alias_target ();
1309 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1315 alias
->analyzed
= false;
1317 DECL_INITIAL (alias
->decl
) = NULL
;
1318 alias
->need_bounds_init
= false;
1319 alias
->remove_all_references ();
1321 varpool_node::create_alias (alias_var
->decl
, decl
);
1322 alias
->resolve_alias (original
);
1325 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1332 sem_variable::compare_sections (sem_variable
*alias
)
1334 const char *source
= node
->get_section ();
1335 const char *target
= alias
->node
->get_section();
1337 if (source
== NULL
&& target
== NULL
)
1339 else if(!source
|| !target
)
1342 return strcmp (source
, target
) == 0;
1345 /* Dump symbol to FILE. */
1348 sem_variable::dump_to_file (FILE *file
)
1352 print_node (file
, "", decl
, 0);
1353 fprintf (file
, "\n\n");
1356 /* Iterates though a constructor and identifies tree references
1357 we are interested in semantic function equality. */
1360 sem_variable::parse_tree_refs (tree t
)
1362 switch (TREE_CODE (t
))
1366 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1368 for (unsigned i
= 0; i
< length
; i
++)
1369 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1376 tree op
= TREE_OPERAND (t
, 0);
1377 parse_tree_refs (op
);
1382 tree_refs
.safe_push (t
);
1390 unsigned int sem_item_optimizer::class_id
= 0;
1392 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1393 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1396 bitmap_obstack_initialize (&m_bmstack
);
1399 sem_item_optimizer::~sem_item_optimizer ()
1401 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1404 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1405 it
!= m_classes
.end (); ++it
)
1407 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1408 delete (*it
)->classes
[i
];
1410 (*it
)->classes
.release ();
1416 bitmap_obstack_release (&m_bmstack
);
1419 /* Write IPA ICF summary for symbols. */
1422 sem_item_optimizer::write_summary (void)
1424 unsigned int count
= 0;
1426 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1427 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1430 /* Calculate number of symbols to be serialized. */
1431 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1433 lsei_next_in_partition (&lsei
))
1435 symtab_node
*node
= lsei_node (lsei
);
1437 if (m_symtab_node_map
.get (node
))
1441 streamer_write_uhwi (ob
, count
);
1443 /* Process all of the symbols. */
1444 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1446 lsei_next_in_partition (&lsei
))
1448 symtab_node
*node
= lsei_node (lsei
);
1450 sem_item
**item
= m_symtab_node_map
.get (node
);
1454 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1455 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1457 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1461 streamer_write_char_stream (ob
->main_stream
, 0);
1462 produce_asm (ob
, NULL
);
1463 destroy_output_block (ob
);
1466 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1467 contains LEN bytes. */
1470 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1471 const char *data
, size_t len
)
1473 const lto_function_header
*header
=
1474 (const lto_function_header
*) data
;
1475 const int cfg_offset
= sizeof (lto_function_header
);
1476 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1477 const int string_offset
= main_offset
+ header
->main_size
;
1482 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1486 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1487 header
->string_size
, vNULL
);
1489 count
= streamer_read_uhwi (&ib_main
);
1491 for (i
= 0; i
< count
; i
++)
1495 lto_symtab_encoder_t encoder
;
1497 index
= streamer_read_uhwi (&ib_main
);
1498 encoder
= file_data
->symtab_node_encoder
;
1499 node
= lto_symtab_encoder_deref (encoder
, index
);
1501 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1503 gcc_assert (node
->definition
);
1506 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1507 (void *) node
->decl
, node
->order
);
1509 if (is_a
<cgraph_node
*> (node
))
1511 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1513 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1517 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1519 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1523 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1525 lto_data_in_delete (data_in
);
1528 /* Read IPA IPA ICF summary for symbols. */
1531 sem_item_optimizer::read_summary (void)
1533 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1534 lto_file_decl_data
*file_data
;
1537 while ((file_data
= file_data_vec
[j
++]))
1540 const char *data
= lto_get_section_data (file_data
,
1541 LTO_section_ipa_icf
, NULL
, &len
);
1544 read_section (file_data
, data
, len
);
1548 /* Register callgraph and varpool hooks. */
1551 sem_item_optimizer::register_hooks (void)
1553 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1554 (&sem_item_optimizer::cgraph_removal_hook
, this);
1556 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1557 (&sem_item_optimizer::varpool_removal_hook
, this);
1560 /* Unregister callgraph and varpool hooks. */
1563 sem_item_optimizer::unregister_hooks (void)
1565 if (m_cgraph_node_hooks
)
1566 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1568 if (m_varpool_node_hooks
)
1569 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1572 /* Adds a CLS to hashtable associated by hash value. */
1575 sem_item_optimizer::add_class (congruence_class
*cls
)
1577 gcc_assert (cls
->members
.length ());
1579 congruence_class_group
*group
= get_group_by_hash (
1580 cls
->members
[0]->get_hash (),
1581 cls
->members
[0]->type
);
1582 group
->classes
.safe_push (cls
);
1585 /* Gets a congruence class group based on given HASH value and TYPE. */
1587 congruence_class_group
*
1588 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1590 congruence_class_group
*item
= XNEW (congruence_class_group
);
1594 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1600 item
->classes
.create (1);
1607 /* Callgraph removal hook called for a NODE with a custom DATA. */
1610 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1612 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1613 optimizer
->remove_symtab_node (node
);
1616 /* Varpool removal hook called for a NODE with a custom DATA. */
1619 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1621 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1622 optimizer
->remove_symtab_node (node
);
1625 /* Remove symtab NODE triggered by symtab removal hooks. */
1628 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1630 gcc_assert (!m_classes
.elements());
1632 m_removed_items_set
.add (node
);
1636 sem_item_optimizer::remove_item (sem_item
*item
)
1638 if (m_symtab_node_map
.get (item
->node
))
1639 m_symtab_node_map
.remove (item
->node
);
1643 /* Removes all callgraph and varpool nodes that are marked by symtab
1647 sem_item_optimizer::filter_removed_items (void)
1649 auto_vec
<sem_item
*> filtered
;
1651 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1653 sem_item
*item
= m_items
[i
];
1655 if (item
->type
== FUNC
1656 && !opt_for_fn (item
->decl
, flag_ipa_icf_functions
))
1662 if (!flag_ipa_icf_variables
&& item
->type
== VAR
)
1668 bool no_body_function
= false;
1670 if (item
->type
== FUNC
)
1672 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1674 no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1677 if(!m_removed_items_set
.contains (m_items
[i
]->node
)
1678 && !no_body_function
)
1680 if (item
->type
== VAR
|| (!DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1681 && !DECL_CXX_DESTRUCTOR_P (item
->decl
)))
1683 filtered
.safe_push (m_items
[i
]);
1691 /* Clean-up of released semantic items. */
1694 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1695 m_items
.safe_push (filtered
[i
]);
1698 /* Optimizer entry point. */
1701 sem_item_optimizer::execute (void)
1703 filter_removed_items ();
1704 build_hash_based_classes ();
1707 fprintf (dump_file
, "Dump after hash based groups\n");
1708 dump_cong_classes ();
1710 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1711 m_items
[i
]->init_wpa ();
1715 subdivide_classes_by_equality (true);
1718 fprintf (dump_file
, "Dump after WPA based types groups\n");
1720 dump_cong_classes ();
1722 process_cong_reduction ();
1726 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1728 dump_cong_classes ();
1730 parse_nonsingleton_classes ();
1731 subdivide_classes_by_equality ();
1734 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1736 dump_cong_classes ();
1738 unsigned int prev_class_count
= m_classes_count
;
1740 process_cong_reduction ();
1741 dump_cong_classes ();
1743 merge_classes (prev_class_count
);
1745 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1746 symtab_node::dump_table (dump_file
);
1749 /* Function responsible for visiting all potential functions and
1750 read-only variables that can be merged. */
1753 sem_item_optimizer::parse_funcs_and_vars (void)
1757 if (flag_ipa_icf_functions
)
1758 FOR_EACH_DEFINED_FUNCTION (cnode
)
1760 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1763 m_items
.safe_push (f
);
1764 m_symtab_node_map
.put (cnode
, f
);
1767 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1770 f
->dump_to_file (dump_file
);
1773 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1776 varpool_node
*vnode
;
1778 if (flag_ipa_icf_variables
)
1779 FOR_EACH_DEFINED_VARIABLE (vnode
)
1781 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1785 m_items
.safe_push (v
);
1786 m_symtab_node_map
.put (vnode
, v
);
1791 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1794 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1796 item
->index_in_class
= cls
->members
.length ();
1797 cls
->members
.safe_push (item
);
1801 /* Congruence classes are built by hash value. */
1804 sem_item_optimizer::build_hash_based_classes (void)
1806 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1808 sem_item
*item
= m_items
[i
];
1810 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1813 if (!group
->classes
.length ())
1816 group
->classes
.safe_push (new congruence_class (class_id
++));
1819 add_item_to_class (group
->classes
[0], item
);
1823 /* Build references according to call graph. */
1826 sem_item_optimizer::build_graph (void)
1828 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1830 sem_item
*item
= m_items
[i
];
1831 m_symtab_node_map
.put (item
->node
, item
);
1834 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1836 sem_item
*item
= m_items
[i
];
1838 if (item
->type
== FUNC
)
1840 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1842 cgraph_edge
*e
= cnode
->callees
;
1845 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1847 item
->add_reference (*slot
);
1853 ipa_ref
*ref
= NULL
;
1854 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1856 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1858 item
->add_reference (*slot
);
1863 /* Semantic items in classes having more than one element and initialized.
1864 In case of WPA, we load function body. */
1867 sem_item_optimizer::parse_nonsingleton_classes (void)
1869 unsigned int init_called_count
= 0;
1871 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1872 if (m_items
[i
]->cls
->members
.length () > 1)
1874 m_items
[i
]->init ();
1875 init_called_count
++;
1879 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1880 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
1883 /* Equality function for semantic items is used to subdivide existing
1884 classes. If IN_WPA, fast equality function is invoked. */
1887 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1889 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1890 it
!= m_classes
.end (); ++it
)
1892 unsigned int class_count
= (*it
)->classes
.length ();
1894 for (unsigned i
= 0; i
< class_count
; i
++)
1896 congruence_class
*c
= (*it
)->classes
[i
];
1898 if (c
->members
.length() > 1)
1900 auto_vec
<sem_item
*> new_vector
;
1902 sem_item
*first
= c
->members
[0];
1903 new_vector
.safe_push (first
);
1905 unsigned class_split_first
= (*it
)->classes
.length ();
1907 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1909 sem_item
*item
= c
->members
[j
];
1911 bool equals
= in_wpa
? first
->equals_wpa (item
,
1912 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1915 new_vector
.safe_push (item
);
1918 bool integrated
= false;
1920 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1922 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1923 bool equals
= in_wpa
? x
->equals_wpa (item
,
1924 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1929 add_item_to_class ((*it
)->classes
[k
], item
);
1937 congruence_class
*c
= new congruence_class (class_id
++);
1939 add_item_to_class (c
, item
);
1941 (*it
)->classes
.safe_push (c
);
1946 // we replace newly created new_vector for the class we've just splitted
1947 c
->members
.release ();
1948 c
->members
.create (new_vector
.length ());
1950 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1951 add_item_to_class (c
, new_vector
[j
]);
1959 /* Verify congruence classes if checking is enabled. */
1962 sem_item_optimizer::verify_classes (void)
1965 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1966 it
!= m_classes
.end (); ++it
)
1968 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1970 congruence_class
*cls
= (*it
)->classes
[i
];
1972 gcc_checking_assert (cls
);
1973 gcc_checking_assert (cls
->members
.length () > 0);
1975 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1977 sem_item
*item
= cls
->members
[j
];
1979 gcc_checking_assert (item
);
1980 gcc_checking_assert (item
->cls
== cls
);
1982 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1984 sem_usage_pair
*usage
= item
->usages
[k
];
1985 gcc_checking_assert (usage
->item
->index_in_class
<
1986 usage
->item
->cls
->members
.length ());
1994 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1995 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1996 but unused argument. */
1999 sem_item_optimizer::release_split_map (congruence_class
* const &,
2000 bitmap
const &b
, traverse_split_pair
*)
2009 /* Process split operation for a class given as pointer CLS_PTR,
2010 where bitmap B splits congruence class members. DATA is used
2011 as argument of split pair. */
2014 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2015 bitmap
const &b
, traverse_split_pair
*pair
)
2017 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2018 const congruence_class
*splitter_cls
= pair
->cls
;
2020 /* If counted bits are greater than zero and less than the number of members
2021 a group will be splitted. */
2022 unsigned popcount
= bitmap_count_bits (b
);
2024 if (popcount
> 0 && popcount
< cls
->members
.length ())
2026 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2028 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2030 int target
= bitmap_bit_p (b
, i
);
2031 congruence_class
*tc
= newclasses
[target
];
2033 add_item_to_class (tc
, cls
->members
[i
]);
2036 #ifdef ENABLE_CHECKING
2037 for (unsigned int i
= 0; i
< 2; i
++)
2038 gcc_checking_assert (newclasses
[i
]->members
.length ());
2041 if (splitter_cls
== cls
)
2042 optimizer
->splitter_class_removed
= true;
2044 /* Remove old class from worklist if presented. */
2045 bool in_worklist
= cls
->in_worklist
;
2048 cls
->in_worklist
= false;
2050 congruence_class_group g
;
2051 g
.hash
= cls
->members
[0]->get_hash ();
2052 g
.type
= cls
->members
[0]->type
;
2054 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2056 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2057 if (slot
->classes
[i
] == cls
)
2059 slot
->classes
.ordered_remove (i
);
2063 /* New class will be inserted and integrated to work list. */
2064 for (unsigned int i
= 0; i
< 2; i
++)
2065 optimizer
->add_class (newclasses
[i
]);
2067 /* Two classes replace one, so that increment just by one. */
2068 optimizer
->m_classes_count
++;
2070 /* If OLD class was presented in the worklist, we remove the class
2071 and replace it will both newly created classes. */
2073 for (unsigned int i
= 0; i
< 2; i
++)
2074 optimizer
->worklist_push (newclasses
[i
]);
2075 else /* Just smaller class is inserted. */
2077 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2078 newclasses
[1]->members
.length () ?
2080 optimizer
->worklist_push (newclasses
[smaller_index
]);
2083 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2085 fprintf (dump_file
, " congruence class splitted:\n");
2086 cls
->dump (dump_file
, 4);
2088 fprintf (dump_file
, " newly created groups:\n");
2089 for (unsigned int i
= 0; i
< 2; i
++)
2090 newclasses
[i
]->dump (dump_file
, 4);
2093 /* Release class if not presented in work list. */
2102 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2103 Bitmap stack BMSTACK is used for bitmap allocation. */
2106 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2109 hash_map
<congruence_class
*, bitmap
> split_map
;
2111 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2113 sem_item
*item
= cls
->members
[i
];
2115 /* Iterate all usages that have INDEX as usage of the item. */
2116 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2118 sem_usage_pair
*usage
= item
->usages
[j
];
2120 if (usage
->index
!= index
)
2123 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2128 b
= BITMAP_ALLOC (&m_bmstack
);
2129 split_map
.put (usage
->item
->cls
, b
);
2135 gcc_checking_assert (usage
->item
->cls
);
2136 gcc_checking_assert (usage
->item
->index_in_class
<
2137 usage
->item
->cls
->members
.length ());
2140 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2144 traverse_split_pair pair
;
2145 pair
.optimizer
= this;
2148 splitter_class_removed
= false;
2150 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2152 /* Bitmap clean-up. */
2154 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2157 /* Every usage of a congruence class CLS is a candidate that can split the
2158 collection of classes. Bitmap stack BMSTACK is used for bitmap
2162 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2167 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2169 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2170 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2172 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2174 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2175 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2178 do_congruence_step_for_index (cls
, i
);
2180 if (splitter_class_removed
)
2184 BITMAP_FREE (usage
);
2187 /* Adds a newly created congruence class CLS to worklist. */
2190 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2192 /* Return if the class CLS is already presented in work list. */
2193 if (cls
->in_worklist
)
2196 cls
->in_worklist
= true;
2197 worklist
.push_back (cls
);
2200 /* Pops a class from worklist. */
2203 sem_item_optimizer::worklist_pop (void)
2205 congruence_class
*cls
;
2207 while (!worklist
.empty ())
2209 cls
= worklist
.front ();
2210 worklist
.pop_front ();
2211 if (cls
->in_worklist
)
2213 cls
->in_worklist
= false;
2219 /* Work list item was already intended to be removed.
2220 The only reason for doing it is to split a class.
2221 Thus, the class CLS is deleted. */
2229 /* Iterative congruence reduction function. */
2232 sem_item_optimizer::process_cong_reduction (void)
2234 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2235 it
!= m_classes
.end (); ++it
)
2236 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2237 if ((*it
)->classes
[i
]->is_class_used ())
2238 worklist_push ((*it
)->classes
[i
]);
2241 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2242 (unsigned long) worklist
.size ());
2244 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2245 fprintf (dump_file
, "Congruence class reduction\n");
2247 congruence_class
*cls
;
2248 while ((cls
= worklist_pop ()) != NULL
)
2249 do_congruence_step (cls
);
2252 /* Debug function prints all informations about congruence classes. */
2255 sem_item_optimizer::dump_cong_classes (void)
2261 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2262 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2264 /* Histogram calculation. */
2265 unsigned int max_index
= 0;
2266 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2268 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2269 it
!= m_classes
.end (); ++it
)
2271 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2273 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2281 "Class size histogram [num of members]: number of classe number of classess\n");
2283 for (unsigned int i
= 0; i
<= max_index
; i
++)
2285 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2287 fprintf (dump_file
, "\n\n");
2290 if (dump_flags
& TDF_DETAILS
)
2291 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2292 it
!= m_classes
.end (); ++it
)
2294 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2296 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2298 (*it
)->classes
[i
]->dump (dump_file
, 4);
2300 if(i
< (*it
)->classes
.length () - 1)
2301 fprintf (dump_file
, " ");
2308 /* After reduction is done, we can declare all items in a group
2309 to be equal. PREV_CLASS_COUNT is start number of classes
2310 before reduction. */
2313 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2315 unsigned int item_count
= m_items
.length ();
2316 unsigned int class_count
= m_classes_count
;
2317 unsigned int equal_items
= item_count
- class_count
;
2319 unsigned int non_singular_classes_count
= 0;
2320 unsigned int non_singular_classes_sum
= 0;
2322 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2323 it
!= m_classes
.end (); ++it
)
2324 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2326 congruence_class
*c
= (*it
)->classes
[i
];
2327 if (c
->members
.length () > 1)
2329 non_singular_classes_count
++;
2330 non_singular_classes_sum
+= c
->members
.length ();
2336 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2337 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2338 prev_class_count
, class_count
);
2339 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2340 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2341 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2342 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2343 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2344 non_singular_classes_count
: 0.0f
,
2345 non_singular_classes_count
);
2346 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2347 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2348 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2351 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2352 it
!= m_classes
.end (); ++it
)
2353 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2355 congruence_class
*c
= (*it
)->classes
[i
];
2357 if (c
->members
.length () == 1)
2360 gcc_assert (c
->members
.length ());
2362 sem_item
*source
= c
->members
[0];
2364 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2366 sem_item
*alias
= c
->members
[j
];
2370 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2371 source
->name (), alias
->name ());
2372 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2373 source
->asm_name (), alias
->asm_name ());
2376 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
2380 "Merge operation is skipped due to no_icf "
2386 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2388 source
->dump_to_file (dump_file
);
2389 alias
->dump_to_file (dump_file
);
2392 source
->merge (alias
);
2397 /* Dump function prints all class members to a FILE with an INDENT. */
2400 congruence_class::dump (FILE *file
, unsigned int indent
) const
2402 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2403 id
, members
[0]->get_hash (), members
.length ());
2405 FPUTS_SPACES (file
, indent
+ 2, "");
2406 for (unsigned i
= 0; i
< members
.length (); i
++)
2407 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2408 members
[i
]->node
->order
);
2410 fprintf (file
, "\n");
2413 /* Returns true if there's a member that is used from another group. */
2416 congruence_class::is_class_used (void)
2418 for (unsigned int i
= 0; i
< members
.length (); i
++)
2419 if (members
[i
]->usages
.length ())
2425 /* Initialization and computation of symtab node hash, there data
2426 are propagated later on. */
2428 static sem_item_optimizer
*optimizer
= NULL
;
2430 /* Generate pass summary for IPA ICF pass. */
2433 ipa_icf_generate_summary (void)
2436 optimizer
= new sem_item_optimizer ();
2438 optimizer
->parse_funcs_and_vars ();
2441 /* Write pass summary for IPA ICF pass. */
2444 ipa_icf_write_summary (void)
2446 gcc_assert (optimizer
);
2448 optimizer
->write_summary ();
2451 /* Read pass summary for IPA ICF pass. */
2454 ipa_icf_read_summary (void)
2457 optimizer
= new sem_item_optimizer ();
2459 optimizer
->read_summary ();
2460 optimizer
->register_hooks ();
2463 /* Semantic equality exection function. */
2466 ipa_icf_driver (void)
2468 gcc_assert (optimizer
);
2470 optimizer
->execute ();
2471 optimizer
->unregister_hooks ();
2479 const pass_data pass_data_ipa_icf
=
2481 IPA_PASS
, /* type */
2483 OPTGROUP_IPA
, /* optinfo_flags */
2484 TV_IPA_ICF
, /* tv_id */
2485 0, /* properties_required */
2486 0, /* properties_provided */
2487 0, /* properties_destroyed */
2488 0, /* todo_flags_start */
2489 0, /* todo_flags_finish */
2492 class pass_ipa_icf
: public ipa_opt_pass_d
2495 pass_ipa_icf (gcc::context
*ctxt
)
2496 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2497 ipa_icf_generate_summary
, /* generate_summary */
2498 ipa_icf_write_summary
, /* write_summary */
2499 ipa_icf_read_summary
, /* read_summary */
2501 write_optimization_summary */
2503 read_optimization_summary */
2504 NULL
, /* stmt_fixup */
2505 0, /* function_transform_todo_flags_start */
2506 NULL
, /* function_transform */
2507 NULL
) /* variable_transform */
2510 /* opt_pass methods: */
2511 virtual bool gate (function
*)
2513 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2516 virtual unsigned int execute (function
*)
2518 return ipa_icf_driver();
2520 }; // class pass_ipa_icf
2522 } // ipa_icf namespace
2525 make_pass_ipa_icf (gcc::context
*ctxt
)
2527 return new ipa_icf::pass_ipa_icf (ctxt
);