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;
714 if (local_original
->lto_file_data
715 && alias
->lto_file_data
716 && local_original
->lto_file_data
!= alias
->lto_file_data
)
717 local_original
->merged
= true;
719 /* The alias function is removed if symbol address
721 if (!alias_address_matters
)
724 if (dump_file
&& redirected
)
725 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
727 /* If the condtion above is not met, we are lucky and can turn the
728 function into real alias. */
729 else if (create_alias
)
731 alias
->icf_merged
= true;
732 if (local_original
->lto_file_data
733 && alias
->lto_file_data
734 && local_original
->lto_file_data
!= alias
->lto_file_data
)
735 local_original
->merged
= true;
737 /* Remove the function's body. */
738 ipa_merge_profiles (original
, alias
);
739 alias
->release_body (true);
742 /* Create the alias. */
743 cgraph_node::create_alias (alias_func
->decl
, decl
);
744 alias
->resolve_alias (original
);
746 /* Workaround for PR63566 that forces equal calling convention
748 alias
->local
.local
= false;
749 original
->local
.local
= false;
752 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
754 else if (create_thunk
)
756 if (DECL_COMDAT_GROUP (alias
->decl
))
759 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
764 if (DECL_STATIC_CHAIN (alias
->decl
))
767 fprintf (dump_file
, "Thunk creation is risky for static-chain functions.\n\n");
772 alias
->icf_merged
= true;
773 if (local_original
->lto_file_data
774 && alias
->lto_file_data
775 && local_original
->lto_file_data
!= alias
->lto_file_data
)
776 local_original
->merged
= true;
777 ipa_merge_profiles (local_original
, alias
, true);
778 alias
->create_wrapper (local_original
);
781 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
784 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
789 /* Semantic item initialization function. */
792 sem_function::init (void)
795 get_node ()->get_untransformed_body ();
797 tree fndecl
= node
->decl
;
798 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
801 gcc_assert (SSANAMES (func
));
803 ssa_names_size
= SSANAMES (func
)->length ();
807 region_tree
= func
->eh
->region_tree
;
809 /* iterating all function arguments. */
810 arg_count
= count_formal_params (fndecl
);
812 edge_count
= n_edges_for_fn (func
);
813 cfg_checksum
= coverage_compute_cfg_checksum (func
);
815 inchash::hash hstate
;
818 FOR_EACH_BB_FN (bb
, func
)
820 unsigned nondbg_stmt_count
= 0;
823 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
824 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
827 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
830 gimple stmt
= gsi_stmt (gsi
);
832 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
834 hash_stmt (&hstate
, stmt
);
839 gcode_hash
= hstate
.end ();
840 bb_sizes
.safe_push (nondbg_stmt_count
);
842 /* Inserting basic block to hash table. */
843 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
844 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
846 bb_sorted
.safe_push (semantic_bb
);
852 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
855 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
857 enum gimple_code code
= gimple_code (stmt
);
859 hstate
->add_int (code
);
861 if (code
== GIMPLE_CALL
)
863 /* Checking of argument. */
864 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
866 tree argument
= gimple_call_arg (stmt
, i
);
868 switch (TREE_CODE (argument
))
871 if (tree_fits_shwi_p (argument
))
872 hstate
->add_wide_int (tree_to_shwi (argument
));
873 else if (tree_fits_uhwi_p (argument
))
874 hstate
->add_wide_int (tree_to_uhwi (argument
));
880 c
= TREE_REAL_CST (argument
);
881 n
= real_to_integer (&c
);
883 hstate
->add_wide_int (n
);
887 tree addr_operand
= TREE_OPERAND (argument
, 0);
889 if (TREE_CODE (addr_operand
) == STRING_CST
)
890 hstate
->add (TREE_STRING_POINTER (addr_operand
),
891 TREE_STRING_LENGTH (addr_operand
));
902 /* Return true if polymorphic comparison must be processed. */
905 sem_function::compare_polymorphic_p (void)
907 return get_node ()->callees
!= NULL
908 || get_node ()->indirect_calls
!= NULL
909 || m_compared_func
->get_node ()->callees
!= NULL
910 || m_compared_func
->get_node ()->indirect_calls
!= NULL
;
913 /* For a given call graph NODE, the function constructs new
914 semantic function item. */
917 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
919 tree fndecl
= node
->decl
;
920 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
922 /* TODO: add support for thunks and aliases. */
924 if (!func
|| !node
->has_gimple_body_p ())
927 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
930 sem_function
*f
= new sem_function (node
, 0, stack
);
937 /* Parses function arguments and result type. */
940 sem_function::parse_tree_args (void)
944 if (arg_types
.exists ())
945 arg_types
.release ();
947 arg_types
.create (4);
948 tree fnargs
= DECL_ARGUMENTS (decl
);
950 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
951 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
953 /* Function result type. */
954 result
= DECL_RESULT (decl
);
955 result_type
= result
? TREE_TYPE (result
) : NULL
;
957 /* During WPA, we can get arguments by following method. */
960 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
961 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
962 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
964 result_type
= TREE_TYPE (TREE_TYPE (decl
));
968 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
969 return true if phi nodes are semantically equivalent in these blocks . */
972 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
974 gphi_iterator si1
, si2
;
976 unsigned size1
, size2
, i
;
980 gcc_assert (bb1
!= NULL
);
981 gcc_assert (bb2
!= NULL
);
983 si2
= gsi_start_phis (bb2
);
984 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
987 gsi_next_nonvirtual_phi (&si1
);
988 gsi_next_nonvirtual_phi (&si2
);
990 if (gsi_end_p (si1
) && gsi_end_p (si2
))
993 if (gsi_end_p (si1
) || gsi_end_p (si2
))
994 return return_false();
999 tree phi_result1
= gimple_phi_result (phi1
);
1000 tree phi_result2
= gimple_phi_result (phi2
);
1002 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
1003 return return_false_with_msg ("PHI results are different");
1005 size1
= gimple_phi_num_args (phi1
);
1006 size2
= gimple_phi_num_args (phi2
);
1009 return return_false ();
1011 for (i
= 0; i
< size1
; ++i
)
1013 t1
= gimple_phi_arg (phi1
, i
)->def
;
1014 t2
= gimple_phi_arg (phi2
, i
)->def
;
1016 if (!m_checker
->compare_operand (t1
, t2
))
1017 return return_false ();
1019 e1
= gimple_phi_arg_edge (phi1
, i
);
1020 e2
= gimple_phi_arg_edge (phi2
, i
);
1022 if (!m_checker
->compare_edge (e1
, e2
))
1023 return return_false ();
1032 /* Returns true if tree T can be compared as a handled component. */
1035 sem_function::icf_handled_component_p (tree t
)
1037 tree_code tc
= TREE_CODE (t
);
1039 return ((handled_component_p (t
))
1040 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
1041 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
1044 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
1045 corresponds to TARGET. */
1048 sem_function::bb_dict_test (auto_vec
<int> bb_dict
, int source
, int target
)
1053 if (bb_dict
.length () <= (unsigned)source
)
1054 bb_dict
.safe_grow_cleared (source
+ 1);
1056 if (bb_dict
[source
] == 0)
1058 bb_dict
[source
] = target
;
1062 return bb_dict
[source
] == target
;
1065 /* Iterates all tree types in T1 and T2 and returns true if all types
1066 are compatible. If COMPARE_POLYMORPHIC is set to true,
1067 more strict comparison is executed. */
1070 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
1078 while (t1
!= NULL
&& t2
!= NULL
)
1080 tv1
= TREE_VALUE (t1
);
1081 tv2
= TREE_VALUE (t2
);
1083 tc1
= TREE_CODE (tv1
);
1084 tc2
= TREE_CODE (tv2
);
1086 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
1088 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
1090 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
1093 t1
= TREE_CHAIN (t1
);
1094 t2
= TREE_CHAIN (t2
);
1101 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1103 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1107 /* Constructor based on varpool node _NODE with computed hash _HASH.
1108 Bitmap STACK is used for memory allocation. */
1110 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1111 bitmap_obstack
*stack
): sem_item(VAR
,
1114 gcc_checking_assert (node
);
1115 gcc_checking_assert (get_node ());
1118 /* Returns true if the item equals to ITEM given as argument. */
1121 sem_variable::equals (sem_item
*item
,
1122 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1124 gcc_assert (item
->type
== VAR
);
1126 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1128 if (!ctor
|| !v
->ctor
)
1129 return return_false_with_msg ("ctor is missing for semantic variable");
1131 return sem_variable::equals (ctor
, v
->ctor
);
1134 /* Compares trees T1 and T2 for semantic equality. */
1137 sem_variable::equals (tree t1
, tree t2
)
1139 tree_code tc1
= TREE_CODE (t1
);
1140 tree_code tc2
= TREE_CODE (t2
);
1149 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1150 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1155 for (unsigned i
= 0; i
< len1
; i
++)
1156 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1157 CONSTRUCTOR_ELT (t2
, i
)->value
)
1158 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1165 tree x1
= TREE_OPERAND (t1
, 0);
1166 tree x2
= TREE_OPERAND (t2
, 0);
1167 tree y1
= TREE_OPERAND (t1
, 1);
1168 tree y2
= TREE_OPERAND (t2
, 1);
1170 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1172 return return_false ();
1174 /* Type of the offset on MEM_REF does not matter. */
1175 return sem_variable::equals (x1
, x2
)
1176 && wi::to_offset (y1
) == wi::to_offset (y2
);
1181 tree op1
= TREE_OPERAND (t1
, 0);
1182 tree op2
= TREE_OPERAND (t2
, 0);
1183 return sem_variable::equals (op1
, op2
);
1191 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1193 && wi::to_offset (t1
) == wi::to_offset (t2
);
1197 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1200 case POINTER_PLUS_EXPR
:
1202 tree x1
= TREE_OPERAND (t1
, 0);
1203 tree x2
= TREE_OPERAND (t2
, 0);
1204 tree y1
= TREE_OPERAND (t1
, 1);
1205 tree y2
= TREE_OPERAND (t2
, 1);
1207 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1210 return return_false_with_msg ("ERROR_MARK");
1212 return return_false_with_msg ("Unknown TREE code reached");
1216 /* Parser function that visits a varpool NODE. */
1219 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1221 tree decl
= node
->decl
;
1223 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1227 bool can_handle
= DECL_VIRTUAL_P (decl
)
1228 || flag_merge_constants
>= 2
1229 || (!TREE_ADDRESSABLE (decl
) && !node
->externally_visible
);
1231 if (!can_handle
|| DECL_EXTERNAL (decl
))
1234 tree ctor
= ctor_for_folding (decl
);
1238 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1245 /* References independent hash function. */
1248 sem_variable::get_hash (void)
1253 inchash::hash hstate
;
1255 hstate
.add_int (456346417);
1256 hstate
.add_int (TREE_CODE (ctor
));
1258 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1260 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1261 hstate
.add_int (length
);
1264 hash
= hstate
.end ();
1269 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1273 sem_variable::merge (sem_item
*alias_item
)
1275 gcc_assert (alias_item
->type
== VAR
);
1277 if (!sem_item::target_supports_symbol_aliases_p ())
1280 fprintf (dump_file
, "Symbol aliases are not supported by target\n\n");
1284 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1286 varpool_node
*original
= get_node ();
1287 varpool_node
*alias
= alias_var
->get_node ();
1288 bool original_discardable
= false;
1290 /* See if original is in a section that can be discarded if the main
1291 symbol is not used. */
1292 if (DECL_EXTERNAL (original
->decl
))
1293 original_discardable
= true;
1294 if (original
->resolution
== LDPR_PREEMPTED_REG
1295 || original
->resolution
== LDPR_PREEMPTED_IR
)
1296 original_discardable
= true;
1297 if (original
->can_be_discarded_p ())
1298 original_discardable
= true;
1300 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1302 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1303 !compare_sections (alias_var
))
1306 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1312 // alias cycle creation check
1313 varpool_node
*n
= original
;
1317 n
= n
->get_alias_target ();
1321 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1327 alias
->analyzed
= false;
1329 DECL_INITIAL (alias
->decl
) = NULL
;
1330 alias
->need_bounds_init
= false;
1331 alias
->remove_all_references ();
1333 varpool_node::create_alias (alias_var
->decl
, decl
);
1334 alias
->resolve_alias (original
);
1337 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1344 sem_variable::compare_sections (sem_variable
*alias
)
1346 const char *source
= node
->get_section ();
1347 const char *target
= alias
->node
->get_section();
1349 if (source
== NULL
&& target
== NULL
)
1351 else if(!source
|| !target
)
1354 return strcmp (source
, target
) == 0;
1357 /* Dump symbol to FILE. */
1360 sem_variable::dump_to_file (FILE *file
)
1364 print_node (file
, "", decl
, 0);
1365 fprintf (file
, "\n\n");
1368 /* Iterates though a constructor and identifies tree references
1369 we are interested in semantic function equality. */
1372 sem_variable::parse_tree_refs (tree t
)
1374 switch (TREE_CODE (t
))
1378 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1380 for (unsigned i
= 0; i
< length
; i
++)
1381 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1388 tree op
= TREE_OPERAND (t
, 0);
1389 parse_tree_refs (op
);
1394 tree_refs
.safe_push (t
);
1402 unsigned int sem_item_optimizer::class_id
= 0;
1404 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1405 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1408 bitmap_obstack_initialize (&m_bmstack
);
1411 sem_item_optimizer::~sem_item_optimizer ()
1413 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1416 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1417 it
!= m_classes
.end (); ++it
)
1419 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1420 delete (*it
)->classes
[i
];
1422 (*it
)->classes
.release ();
1428 bitmap_obstack_release (&m_bmstack
);
1431 /* Write IPA ICF summary for symbols. */
1434 sem_item_optimizer::write_summary (void)
1436 unsigned int count
= 0;
1438 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1439 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1442 /* Calculate number of symbols to be serialized. */
1443 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1445 lsei_next_in_partition (&lsei
))
1447 symtab_node
*node
= lsei_node (lsei
);
1449 if (m_symtab_node_map
.get (node
))
1453 streamer_write_uhwi (ob
, count
);
1455 /* Process all of the symbols. */
1456 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1458 lsei_next_in_partition (&lsei
))
1460 symtab_node
*node
= lsei_node (lsei
);
1462 sem_item
**item
= m_symtab_node_map
.get (node
);
1466 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1467 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1469 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1473 streamer_write_char_stream (ob
->main_stream
, 0);
1474 produce_asm (ob
, NULL
);
1475 destroy_output_block (ob
);
1478 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1479 contains LEN bytes. */
1482 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1483 const char *data
, size_t len
)
1485 const lto_function_header
*header
=
1486 (const lto_function_header
*) data
;
1487 const int cfg_offset
= sizeof (lto_function_header
);
1488 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1489 const int string_offset
= main_offset
+ header
->main_size
;
1494 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1498 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1499 header
->string_size
, vNULL
);
1501 count
= streamer_read_uhwi (&ib_main
);
1503 for (i
= 0; i
< count
; i
++)
1507 lto_symtab_encoder_t encoder
;
1509 index
= streamer_read_uhwi (&ib_main
);
1510 encoder
= file_data
->symtab_node_encoder
;
1511 node
= lto_symtab_encoder_deref (encoder
, index
);
1513 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1515 gcc_assert (node
->definition
);
1518 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1519 (void *) node
->decl
, node
->order
);
1521 if (is_a
<cgraph_node
*> (node
))
1523 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1525 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1529 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1531 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1535 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1537 lto_data_in_delete (data_in
);
1540 /* Read IPA IPA ICF summary for symbols. */
1543 sem_item_optimizer::read_summary (void)
1545 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1546 lto_file_decl_data
*file_data
;
1549 while ((file_data
= file_data_vec
[j
++]))
1552 const char *data
= lto_get_section_data (file_data
,
1553 LTO_section_ipa_icf
, NULL
, &len
);
1556 read_section (file_data
, data
, len
);
1560 /* Register callgraph and varpool hooks. */
1563 sem_item_optimizer::register_hooks (void)
1565 if (!m_cgraph_node_hooks
)
1566 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1567 (&sem_item_optimizer::cgraph_removal_hook
, this);
1569 if (!m_varpool_node_hooks
)
1570 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1571 (&sem_item_optimizer::varpool_removal_hook
, this);
1574 /* Unregister callgraph and varpool hooks. */
1577 sem_item_optimizer::unregister_hooks (void)
1579 if (m_cgraph_node_hooks
)
1580 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1582 if (m_varpool_node_hooks
)
1583 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1586 /* Adds a CLS to hashtable associated by hash value. */
1589 sem_item_optimizer::add_class (congruence_class
*cls
)
1591 gcc_assert (cls
->members
.length ());
1593 congruence_class_group
*group
= get_group_by_hash (
1594 cls
->members
[0]->get_hash (),
1595 cls
->members
[0]->type
);
1596 group
->classes
.safe_push (cls
);
1599 /* Gets a congruence class group based on given HASH value and TYPE. */
1601 congruence_class_group
*
1602 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1604 congruence_class_group
*item
= XNEW (congruence_class_group
);
1608 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1614 item
->classes
.create (1);
1621 /* Callgraph removal hook called for a NODE with a custom DATA. */
1624 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1626 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1627 optimizer
->remove_symtab_node (node
);
1630 /* Varpool removal hook called for a NODE with a custom DATA. */
1633 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1635 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1636 optimizer
->remove_symtab_node (node
);
1639 /* Remove symtab NODE triggered by symtab removal hooks. */
1642 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1644 gcc_assert (!m_classes
.elements());
1646 m_removed_items_set
.add (node
);
1650 sem_item_optimizer::remove_item (sem_item
*item
)
1652 if (m_symtab_node_map
.get (item
->node
))
1653 m_symtab_node_map
.remove (item
->node
);
1657 /* Removes all callgraph and varpool nodes that are marked by symtab
1661 sem_item_optimizer::filter_removed_items (void)
1663 auto_vec
<sem_item
*> filtered
;
1665 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1667 sem_item
*item
= m_items
[i
];
1669 if (m_removed_items_set
.contains (item
->node
))
1675 if (item
->type
== FUNC
)
1677 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1679 bool no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1680 if (no_body_function
|| !opt_for_fn (item
->decl
, flag_ipa_icf_functions
)
1681 || DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1682 || DECL_CXX_DESTRUCTOR_P (item
->decl
))
1685 filtered
.safe_push (item
);
1689 if (!flag_ipa_icf_variables
)
1692 filtered
.safe_push (item
);
1696 /* Clean-up of released semantic items. */
1699 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1700 m_items
.safe_push (filtered
[i
]);
1703 /* Optimizer entry point. */
1706 sem_item_optimizer::execute (void)
1708 filter_removed_items ();
1709 build_hash_based_classes ();
1712 fprintf (dump_file
, "Dump after hash based groups\n");
1713 dump_cong_classes ();
1715 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1716 m_items
[i
]->init_wpa ();
1720 subdivide_classes_by_equality (true);
1723 fprintf (dump_file
, "Dump after WPA based types groups\n");
1725 dump_cong_classes ();
1727 process_cong_reduction ();
1731 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1733 dump_cong_classes ();
1735 parse_nonsingleton_classes ();
1736 subdivide_classes_by_equality ();
1739 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1741 dump_cong_classes ();
1743 unsigned int prev_class_count
= m_classes_count
;
1745 process_cong_reduction ();
1746 dump_cong_classes ();
1748 merge_classes (prev_class_count
);
1750 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1751 symtab_node::dump_table (dump_file
);
1754 /* Function responsible for visiting all potential functions and
1755 read-only variables that can be merged. */
1758 sem_item_optimizer::parse_funcs_and_vars (void)
1762 if (flag_ipa_icf_functions
)
1763 FOR_EACH_DEFINED_FUNCTION (cnode
)
1765 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1768 m_items
.safe_push (f
);
1769 m_symtab_node_map
.put (cnode
, f
);
1772 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1774 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1775 f
->dump_to_file (dump_file
);
1778 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1781 varpool_node
*vnode
;
1783 if (flag_ipa_icf_variables
)
1784 FOR_EACH_DEFINED_VARIABLE (vnode
)
1786 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1790 m_items
.safe_push (v
);
1791 m_symtab_node_map
.put (vnode
, v
);
1796 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1799 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1801 item
->index_in_class
= cls
->members
.length ();
1802 cls
->members
.safe_push (item
);
1806 /* Congruence classes are built by hash value. */
1809 sem_item_optimizer::build_hash_based_classes (void)
1811 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1813 sem_item
*item
= m_items
[i
];
1815 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1818 if (!group
->classes
.length ())
1821 group
->classes
.safe_push (new congruence_class (class_id
++));
1824 add_item_to_class (group
->classes
[0], item
);
1828 /* Build references according to call graph. */
1831 sem_item_optimizer::build_graph (void)
1833 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1835 sem_item
*item
= m_items
[i
];
1836 m_symtab_node_map
.put (item
->node
, item
);
1839 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1841 sem_item
*item
= m_items
[i
];
1843 if (item
->type
== FUNC
)
1845 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1847 cgraph_edge
*e
= cnode
->callees
;
1850 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1852 item
->add_reference (*slot
);
1858 ipa_ref
*ref
= NULL
;
1859 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1861 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1863 item
->add_reference (*slot
);
1868 /* Semantic items in classes having more than one element and initialized.
1869 In case of WPA, we load function body. */
1872 sem_item_optimizer::parse_nonsingleton_classes (void)
1874 unsigned int init_called_count
= 0;
1876 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1877 if (m_items
[i
]->cls
->members
.length () > 1)
1879 m_items
[i
]->init ();
1880 init_called_count
++;
1884 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1885 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
1888 /* Equality function for semantic items is used to subdivide existing
1889 classes. If IN_WPA, fast equality function is invoked. */
1892 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1894 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1895 it
!= m_classes
.end (); ++it
)
1897 unsigned int class_count
= (*it
)->classes
.length ();
1899 for (unsigned i
= 0; i
< class_count
; i
++)
1901 congruence_class
*c
= (*it
)->classes
[i
];
1903 if (c
->members
.length() > 1)
1905 auto_vec
<sem_item
*> new_vector
;
1907 sem_item
*first
= c
->members
[0];
1908 new_vector
.safe_push (first
);
1910 unsigned class_split_first
= (*it
)->classes
.length ();
1912 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1914 sem_item
*item
= c
->members
[j
];
1916 bool equals
= in_wpa
? first
->equals_wpa (item
,
1917 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1920 new_vector
.safe_push (item
);
1923 bool integrated
= false;
1925 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1927 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1928 bool equals
= in_wpa
? x
->equals_wpa (item
,
1929 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1934 add_item_to_class ((*it
)->classes
[k
], item
);
1942 congruence_class
*c
= new congruence_class (class_id
++);
1944 add_item_to_class (c
, item
);
1946 (*it
)->classes
.safe_push (c
);
1951 // we replace newly created new_vector for the class we've just splitted
1952 c
->members
.release ();
1953 c
->members
.create (new_vector
.length ());
1955 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1956 add_item_to_class (c
, new_vector
[j
]);
1964 /* Verify congruence classes if checking is enabled. */
1967 sem_item_optimizer::verify_classes (void)
1970 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1971 it
!= m_classes
.end (); ++it
)
1973 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1975 congruence_class
*cls
= (*it
)->classes
[i
];
1977 gcc_checking_assert (cls
);
1978 gcc_checking_assert (cls
->members
.length () > 0);
1980 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1982 sem_item
*item
= cls
->members
[j
];
1984 gcc_checking_assert (item
);
1985 gcc_checking_assert (item
->cls
== cls
);
1987 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1989 sem_usage_pair
*usage
= item
->usages
[k
];
1990 gcc_checking_assert (usage
->item
->index_in_class
<
1991 usage
->item
->cls
->members
.length ());
1999 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
2000 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
2001 but unused argument. */
2004 sem_item_optimizer::release_split_map (congruence_class
* const &,
2005 bitmap
const &b
, traverse_split_pair
*)
2014 /* Process split operation for a class given as pointer CLS_PTR,
2015 where bitmap B splits congruence class members. DATA is used
2016 as argument of split pair. */
2019 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
2020 bitmap
const &b
, traverse_split_pair
*pair
)
2022 sem_item_optimizer
*optimizer
= pair
->optimizer
;
2023 const congruence_class
*splitter_cls
= pair
->cls
;
2025 /* If counted bits are greater than zero and less than the number of members
2026 a group will be splitted. */
2027 unsigned popcount
= bitmap_count_bits (b
);
2029 if (popcount
> 0 && popcount
< cls
->members
.length ())
2031 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
2033 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2035 int target
= bitmap_bit_p (b
, i
);
2036 congruence_class
*tc
= newclasses
[target
];
2038 add_item_to_class (tc
, cls
->members
[i
]);
2041 #ifdef ENABLE_CHECKING
2042 for (unsigned int i
= 0; i
< 2; i
++)
2043 gcc_checking_assert (newclasses
[i
]->members
.length ());
2046 if (splitter_cls
== cls
)
2047 optimizer
->splitter_class_removed
= true;
2049 /* Remove old class from worklist if presented. */
2050 bool in_worklist
= cls
->in_worklist
;
2053 cls
->in_worklist
= false;
2055 congruence_class_group g
;
2056 g
.hash
= cls
->members
[0]->get_hash ();
2057 g
.type
= cls
->members
[0]->type
;
2059 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
2061 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
2062 if (slot
->classes
[i
] == cls
)
2064 slot
->classes
.ordered_remove (i
);
2068 /* New class will be inserted and integrated to work list. */
2069 for (unsigned int i
= 0; i
< 2; i
++)
2070 optimizer
->add_class (newclasses
[i
]);
2072 /* Two classes replace one, so that increment just by one. */
2073 optimizer
->m_classes_count
++;
2075 /* If OLD class was presented in the worklist, we remove the class
2076 and replace it will both newly created classes. */
2078 for (unsigned int i
= 0; i
< 2; i
++)
2079 optimizer
->worklist_push (newclasses
[i
]);
2080 else /* Just smaller class is inserted. */
2082 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2083 newclasses
[1]->members
.length () ?
2085 optimizer
->worklist_push (newclasses
[smaller_index
]);
2088 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2090 fprintf (dump_file
, " congruence class splitted:\n");
2091 cls
->dump (dump_file
, 4);
2093 fprintf (dump_file
, " newly created groups:\n");
2094 for (unsigned int i
= 0; i
< 2; i
++)
2095 newclasses
[i
]->dump (dump_file
, 4);
2098 /* Release class if not presented in work list. */
2107 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2108 Bitmap stack BMSTACK is used for bitmap allocation. */
2111 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2114 hash_map
<congruence_class
*, bitmap
> split_map
;
2116 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2118 sem_item
*item
= cls
->members
[i
];
2120 /* Iterate all usages that have INDEX as usage of the item. */
2121 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2123 sem_usage_pair
*usage
= item
->usages
[j
];
2125 if (usage
->index
!= index
)
2128 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2133 b
= BITMAP_ALLOC (&m_bmstack
);
2134 split_map
.put (usage
->item
->cls
, b
);
2140 gcc_checking_assert (usage
->item
->cls
);
2141 gcc_checking_assert (usage
->item
->index_in_class
<
2142 usage
->item
->cls
->members
.length ());
2145 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2149 traverse_split_pair pair
;
2150 pair
.optimizer
= this;
2153 splitter_class_removed
= false;
2155 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2157 /* Bitmap clean-up. */
2159 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2162 /* Every usage of a congruence class CLS is a candidate that can split the
2163 collection of classes. Bitmap stack BMSTACK is used for bitmap
2167 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2172 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2174 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2175 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2177 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2179 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2180 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2183 do_congruence_step_for_index (cls
, i
);
2185 if (splitter_class_removed
)
2189 BITMAP_FREE (usage
);
2192 /* Adds a newly created congruence class CLS to worklist. */
2195 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2197 /* Return if the class CLS is already presented in work list. */
2198 if (cls
->in_worklist
)
2201 cls
->in_worklist
= true;
2202 worklist
.push_back (cls
);
2205 /* Pops a class from worklist. */
2208 sem_item_optimizer::worklist_pop (void)
2210 congruence_class
*cls
;
2212 while (!worklist
.empty ())
2214 cls
= worklist
.front ();
2215 worklist
.pop_front ();
2216 if (cls
->in_worklist
)
2218 cls
->in_worklist
= false;
2224 /* Work list item was already intended to be removed.
2225 The only reason for doing it is to split a class.
2226 Thus, the class CLS is deleted. */
2234 /* Iterative congruence reduction function. */
2237 sem_item_optimizer::process_cong_reduction (void)
2239 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2240 it
!= m_classes
.end (); ++it
)
2241 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2242 if ((*it
)->classes
[i
]->is_class_used ())
2243 worklist_push ((*it
)->classes
[i
]);
2246 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2247 (unsigned long) worklist
.size ());
2249 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2250 fprintf (dump_file
, "Congruence class reduction\n");
2252 congruence_class
*cls
;
2253 while ((cls
= worklist_pop ()) != NULL
)
2254 do_congruence_step (cls
);
2257 /* Debug function prints all informations about congruence classes. */
2260 sem_item_optimizer::dump_cong_classes (void)
2266 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2267 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2269 /* Histogram calculation. */
2270 unsigned int max_index
= 0;
2271 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2273 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2274 it
!= m_classes
.end (); ++it
)
2276 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2278 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2286 "Class size histogram [num of members]: number of classe number of classess\n");
2288 for (unsigned int i
= 0; i
<= max_index
; i
++)
2290 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2292 fprintf (dump_file
, "\n\n");
2295 if (dump_flags
& TDF_DETAILS
)
2296 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2297 it
!= m_classes
.end (); ++it
)
2299 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2301 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2303 (*it
)->classes
[i
]->dump (dump_file
, 4);
2305 if(i
< (*it
)->classes
.length () - 1)
2306 fprintf (dump_file
, " ");
2313 /* After reduction is done, we can declare all items in a group
2314 to be equal. PREV_CLASS_COUNT is start number of classes
2315 before reduction. */
2318 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2320 unsigned int item_count
= m_items
.length ();
2321 unsigned int class_count
= m_classes_count
;
2322 unsigned int equal_items
= item_count
- class_count
;
2324 unsigned int non_singular_classes_count
= 0;
2325 unsigned int non_singular_classes_sum
= 0;
2327 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2328 it
!= m_classes
.end (); ++it
)
2329 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2331 congruence_class
*c
= (*it
)->classes
[i
];
2332 if (c
->members
.length () > 1)
2334 non_singular_classes_count
++;
2335 non_singular_classes_sum
+= c
->members
.length ();
2341 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2342 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2343 prev_class_count
, class_count
);
2344 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2345 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2346 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2347 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2348 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2349 non_singular_classes_count
: 0.0f
,
2350 non_singular_classes_count
);
2351 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2352 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2353 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2356 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2357 it
!= m_classes
.end (); ++it
)
2358 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2360 congruence_class
*c
= (*it
)->classes
[i
];
2362 if (c
->members
.length () == 1)
2365 gcc_assert (c
->members
.length ());
2367 sem_item
*source
= c
->members
[0];
2369 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2371 sem_item
*alias
= c
->members
[j
];
2375 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2376 source
->name (), alias
->name ());
2377 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2378 source
->asm_name (), alias
->asm_name ());
2381 if (lookup_attribute ("no_icf", DECL_ATTRIBUTES (alias
->decl
)))
2385 "Merge operation is skipped due to no_icf "
2391 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2393 source
->dump_to_file (dump_file
);
2394 alias
->dump_to_file (dump_file
);
2397 source
->merge (alias
);
2402 /* Dump function prints all class members to a FILE with an INDENT. */
2405 congruence_class::dump (FILE *file
, unsigned int indent
) const
2407 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2408 id
, members
[0]->get_hash (), members
.length ());
2410 FPUTS_SPACES (file
, indent
+ 2, "");
2411 for (unsigned i
= 0; i
< members
.length (); i
++)
2412 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2413 members
[i
]->node
->order
);
2415 fprintf (file
, "\n");
2418 /* Returns true if there's a member that is used from another group. */
2421 congruence_class::is_class_used (void)
2423 for (unsigned int i
= 0; i
< members
.length (); i
++)
2424 if (members
[i
]->usages
.length ())
2430 /* Initialization and computation of symtab node hash, there data
2431 are propagated later on. */
2433 static sem_item_optimizer
*optimizer
= NULL
;
2435 /* Generate pass summary for IPA ICF pass. */
2438 ipa_icf_generate_summary (void)
2441 optimizer
= new sem_item_optimizer ();
2443 optimizer
->register_hooks ();
2444 optimizer
->parse_funcs_and_vars ();
2447 /* Write pass summary for IPA ICF pass. */
2450 ipa_icf_write_summary (void)
2452 gcc_assert (optimizer
);
2454 optimizer
->write_summary ();
2457 /* Read pass summary for IPA ICF pass. */
2460 ipa_icf_read_summary (void)
2463 optimizer
= new sem_item_optimizer ();
2465 optimizer
->read_summary ();
2466 optimizer
->register_hooks ();
2469 /* Semantic equality exection function. */
2472 ipa_icf_driver (void)
2474 gcc_assert (optimizer
);
2476 optimizer
->execute ();
2477 optimizer
->unregister_hooks ();
2485 const pass_data pass_data_ipa_icf
=
2487 IPA_PASS
, /* type */
2489 OPTGROUP_IPA
, /* optinfo_flags */
2490 TV_IPA_ICF
, /* tv_id */
2491 0, /* properties_required */
2492 0, /* properties_provided */
2493 0, /* properties_destroyed */
2494 0, /* todo_flags_start */
2495 0, /* todo_flags_finish */
2498 class pass_ipa_icf
: public ipa_opt_pass_d
2501 pass_ipa_icf (gcc::context
*ctxt
)
2502 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2503 ipa_icf_generate_summary
, /* generate_summary */
2504 ipa_icf_write_summary
, /* write_summary */
2505 ipa_icf_read_summary
, /* read_summary */
2507 write_optimization_summary */
2509 read_optimization_summary */
2510 NULL
, /* stmt_fixup */
2511 0, /* function_transform_todo_flags_start */
2512 NULL
, /* function_transform */
2513 NULL
) /* variable_transform */
2516 /* opt_pass methods: */
2517 virtual bool gate (function
*)
2519 return in_lto_p
|| flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2522 virtual unsigned int execute (function
*)
2524 return ipa_icf_driver();
2526 }; // class pass_ipa_icf
2528 } // ipa_icf namespace
2531 make_pass_ipa_icf (gcc::context
*ctxt
)
2533 return new ipa_icf::pass_ipa_icf (ctxt
);