1 /* Interprocedural Identical Code Folding pass
2 Copyright (C) 2014 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"
64 #include "hard-reg-set.h"
67 #include "dominance.h"
69 #include "basic-block.h"
70 #include "tree-ssa-alias.h"
71 #include "internal-fn.h"
72 #include "gimple-expr.h"
76 #include "gimple-iterator.h"
77 #include "gimple-ssa.h"
79 #include "tree-phinodes.h"
80 #include "stringpool.h"
81 #include "tree-ssanames.h"
83 #include "tree-pass.h"
84 #include "gimple-pretty-print.h"
86 #include "plugin-api.h"
89 #include "alloc-pool.h"
91 #include "ipa-inline.h"
94 #include "hash-table.h"
97 #include "print-tree.h"
98 #include "lto-streamer.h"
99 #include "data-streamer.h"
100 #include "ipa-utils.h"
102 #include "ipa-icf-gimple.h"
106 using namespace ipa_icf_gimple
;
109 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
111 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
112 item (_item
), index (_index
)
116 /* Semantic item constructor for a node of _TYPE, where STACK is used
117 for bitmap memory allocation. */
119 sem_item::sem_item (sem_item_type _type
,
120 bitmap_obstack
*stack
): type(_type
), hash(0)
125 /* Semantic item constructor for a node of _TYPE, where STACK is used
126 for bitmap memory allocation. The item is based on symtab node _NODE
127 with computed _HASH. */
129 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
130 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
131 node (_node
), hash (_hash
)
137 /* Add reference to a semantic TARGET. */
140 sem_item::add_reference (sem_item
*target
)
142 refs
.safe_push (target
);
143 unsigned index
= refs
.length ();
144 target
->usages
.safe_push (new sem_usage_pair(this, index
));
145 bitmap_set_bit (target
->usage_index_bitmap
, index
);
146 refs_set
.add (target
->node
);
149 /* Initialize internal data structures. Bitmap STACK is used for
150 bitmap memory allocation process. */
153 sem_item::setup (bitmap_obstack
*stack
)
155 gcc_checking_assert (node
);
158 tree_refs
.create (0);
160 usage_index_bitmap
= BITMAP_ALLOC (stack
);
163 sem_item::~sem_item ()
165 for (unsigned i
= 0; i
< usages
.length (); i
++)
169 tree_refs
.release ();
172 BITMAP_FREE (usage_index_bitmap
);
175 /* Dump function for debugging purpose. */
178 sem_item::dump (void)
182 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
183 name(), node
->order
, (void *) node
->decl
);
184 fprintf (dump_file
, " hash: %u\n", get_hash ());
185 fprintf (dump_file
, " references: ");
187 for (unsigned i
= 0; i
< refs
.length (); i
++)
188 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
189 i
< refs
.length() - 1 ? "," : "");
191 fprintf (dump_file
, "\n");
195 /* Return true if target supports alias symbols. */
198 sem_item::target_supports_symbol_aliases_p (void)
200 #if !defined (ASM_OUTPUT_DEF) || (!defined(ASM_OUTPUT_WEAK_ALIAS) && !defined (ASM_WEAKEN_DECL))
207 /* Semantic function constructor that uses STACK as bitmap memory stack. */
209 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
210 m_checker (NULL
), m_compared_func (NULL
)
212 arg_types
.create (0);
214 bb_sorted
.create (0);
217 /* Constructor based on callgraph node _NODE with computed hash _HASH.
218 Bitmap STACK is used for memory allocation. */
219 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
220 bitmap_obstack
*stack
):
221 sem_item (FUNC
, node
, hash
, stack
),
222 m_checker (NULL
), m_compared_func (NULL
)
224 arg_types
.create (0);
226 bb_sorted
.create (0);
229 sem_function::~sem_function ()
231 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
232 delete (bb_sorted
[i
]);
234 arg_types
.release ();
236 bb_sorted
.release ();
239 /* Calculates hash value based on a BASIC_BLOCK. */
242 sem_function::get_bb_hash (const sem_bb
*basic_block
)
244 inchash::hash hstate
;
246 hstate
.add_int (basic_block
->nondbg_stmt_count
);
247 hstate
.add_int (basic_block
->edge_count
);
249 return hstate
.end ();
252 /* References independent hash function. */
255 sem_function::get_hash (void)
259 inchash::hash hstate
;
260 hstate
.add_int (177454); /* Random number for function type. */
262 hstate
.add_int (arg_count
);
263 hstate
.add_int (cfg_checksum
);
264 hstate
.add_int (gcode_hash
);
266 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
267 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
269 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
270 hstate
.add_int (bb_sizes
[i
]);
272 hash
= hstate
.end ();
278 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
279 point to a same function. Comparison can be skipped if IGNORED_NODES
280 contains these nodes. */
283 sem_function::compare_cgraph_references (hash_map
<symtab_node
*, sem_item
*>
285 symtab_node
*n1
, symtab_node
*n2
)
287 if (n1
== n2
|| (ignored_nodes
.get (n1
) && ignored_nodes
.get (n2
)))
290 /* TODO: add more precise comparison for weakrefs, etc. */
292 return return_false_with_msg ("different references");
295 /* If cgraph edges E1 and E2 are indirect calls, verify that
296 ECF flags are the same. */
298 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
300 if (e1
->indirect_info
&& e2
->indirect_info
)
302 int e1_flags
= e1
->indirect_info
->ecf_flags
;
303 int e2_flags
= e2
->indirect_info
->ecf_flags
;
305 if (e1_flags
!= e2_flags
)
306 return return_false_with_msg ("ICF flags are different");
308 else if (e1
->indirect_info
|| e2
->indirect_info
)
314 /* Fast equality function based on knowledge known in WPA. */
317 sem_function::equals_wpa (sem_item
*item
,
318 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
320 gcc_assert (item
->type
== FUNC
);
322 m_compared_func
= static_cast<sem_function
*> (item
);
324 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
325 return return_false_with_msg ("different number of arguments");
327 /* Checking types of arguments. */
328 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
330 /* This guard is here for function pointer with attributes (pr59927.c). */
331 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
332 return return_false_with_msg ("NULL argument type");
334 /* Polymorphic comparison is executed just for non-leaf functions. */
335 bool is_not_leaf
= get_node ()->callees
!= NULL
;
337 if (!func_checker::compatible_types_p (arg_types
[i
],
338 m_compared_func
->arg_types
[i
],
339 is_not_leaf
, i
== 0))
340 return return_false_with_msg ("argument type is different");
343 /* Result type checking. */
344 if (!func_checker::compatible_types_p (result_type
,
345 m_compared_func
->result_type
))
346 return return_false_with_msg ("result types are different");
348 if (node
->num_references () != item
->node
->num_references ())
349 return return_false_with_msg ("different number of references");
351 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
352 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
354 item
->node
->iterate_reference (i
, ref2
);
356 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
, ref2
->referred
))
360 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
361 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
365 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
, e2
->callee
))
368 e1
= e1
->next_callee
;
369 e2
= e2
->next_callee
;
373 return return_false_with_msg ("different number of edges");
378 /* Returns true if the item equals to ITEM given as argument. */
381 sem_function::equals (sem_item
*item
,
382 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
384 gcc_assert (item
->type
== FUNC
);
385 bool eq
= equals_private (item
, ignored_nodes
);
387 if (m_checker
!= NULL
)
393 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
395 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
396 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
397 item
->asm_name (), eq
? "true" : "false");
402 /* Processes function equality comparison. */
405 sem_function::equals_private (sem_item
*item
,
406 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
408 if (item
->type
!= FUNC
)
411 basic_block bb1
, bb2
;
413 edge_iterator ei1
, ei2
;
417 m_compared_func
= static_cast<sem_function
*> (item
);
419 gcc_assert (decl
!= item
->decl
);
421 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
422 || edge_count
!= m_compared_func
->edge_count
423 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
424 return return_false ();
426 if (!equals_wpa (item
, ignored_nodes
))
429 /* Checking function arguments. */
430 tree decl1
= DECL_ATTRIBUTES (decl
);
431 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
433 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
434 compare_polymorphic_p (),
437 &m_compared_func
->refs_set
);
441 return return_false ();
443 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
444 return return_false ();
446 tree attr_value1
= TREE_VALUE (decl1
);
447 tree attr_value2
= TREE_VALUE (decl2
);
449 if (attr_value1
&& attr_value2
)
451 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
452 TREE_VALUE (attr_value2
));
454 return return_false_with_msg ("attribute values are different");
456 else if (!attr_value1
&& !attr_value2
)
459 return return_false ();
461 decl1
= TREE_CHAIN (decl1
);
462 decl2
= TREE_CHAIN (decl2
);
466 return return_false();
469 for (arg1
= DECL_ARGUMENTS (decl
),
470 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
471 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
472 if (!m_checker
->compare_decl (arg1
, arg2
))
473 return return_false ();
475 /* Fill-up label dictionary. */
476 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
478 m_checker
->parse_labels (bb_sorted
[i
]);
479 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
482 /* Checking all basic blocks. */
483 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
484 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
485 return return_false();
487 dump_message ("All BBs are equal\n");
489 auto_vec
<int> bb_dict
;
491 /* Basic block edges check. */
492 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
494 bb1
= bb_sorted
[i
]->bb
;
495 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
497 ei2
= ei_start (bb2
->preds
);
499 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
503 if (e1
->flags
!= e2
->flags
)
504 return return_false_with_msg ("flags comparison returns false");
506 if (!bb_dict_test (bb_dict
, e1
->src
->index
, e2
->src
->index
))
507 return return_false_with_msg ("edge comparison returns false");
509 if (!bb_dict_test (bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
510 return return_false_with_msg ("BB comparison returns false");
512 if (!m_checker
->compare_edge (e1
, e2
))
513 return return_false_with_msg ("edge comparison returns false");
519 /* Basic block PHI nodes comparison. */
520 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
521 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
522 return return_false_with_msg ("PHI node comparison returns false");
527 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
530 sem_function::merge (sem_item
*alias_item
)
532 gcc_assert (alias_item
->type
== FUNC
);
534 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
536 cgraph_node
*original
= get_node ();
537 cgraph_node
*local_original
= original
;
538 cgraph_node
*alias
= alias_func
->get_node ();
539 bool original_address_matters
;
540 bool alias_address_matters
;
542 bool create_thunk
= false;
543 bool create_alias
= false;
544 bool redirect_callers
= false;
545 bool original_discardable
= false;
547 /* Do not attempt to mix functions from different user sections;
548 we do not know what user intends with those. */
549 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
550 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
551 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
555 "Not unifying; original and alias are in different sections.\n\n");
559 /* See if original is in a section that can be discarded if the main
560 symbol is not used. */
561 if (DECL_EXTERNAL (original
->decl
))
562 original_discardable
= true;
563 if (original
->resolution
== LDPR_PREEMPTED_REG
564 || original
->resolution
== LDPR_PREEMPTED_IR
)
565 original_discardable
= true;
566 if (original
->can_be_discarded_p ())
567 original_discardable
= true;
569 /* See if original and/or alias address can be compared for equality. */
570 original_address_matters
571 = (!DECL_VIRTUAL_P (original
->decl
)
572 && (original
->externally_visible
573 || original
->address_taken_from_non_vtable_p ()));
574 alias_address_matters
575 = (!DECL_VIRTUAL_P (alias
->decl
)
576 && (alias
->externally_visible
577 || alias
->address_taken_from_non_vtable_p ()));
579 /* If alias and original can be compared for address equality, we need
580 to create a thunk. Also we can not create extra aliases into discardable
581 section (or we risk link failures when section is discarded). */
582 if ((original_address_matters
583 && alias_address_matters
)
584 || original_discardable
)
586 create_thunk
= !stdarg_p (TREE_TYPE (alias
->decl
));
587 create_alias
= false;
588 /* When both alias and original are not overwritable, we can save
589 the extra thunk wrapper for direct calls. */
591 = (!original_discardable
592 && alias
->get_availability () > AVAIL_INTERPOSABLE
593 && original
->get_availability () > AVAIL_INTERPOSABLE
594 && !alias
->instrumented_version
);
599 create_thunk
= false;
600 redirect_callers
= false;
603 if (create_alias
&& (DECL_COMDAT_GROUP (alias
->decl
)
604 || !sem_item::target_supports_symbol_aliases_p ()))
606 create_alias
= false;
610 /* We want thunk to always jump to the local function body
611 unless the body is comdat and may be optimized out. */
612 if ((create_thunk
|| redirect_callers
)
613 && (!original_discardable
614 || (DECL_COMDAT_GROUP (original
->decl
)
615 && (DECL_COMDAT_GROUP (original
->decl
)
616 == DECL_COMDAT_GROUP (alias
->decl
)))))
618 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
623 fprintf (dump_file
, "Noninterposable alias cannot be created.\n\n");
628 if (!decl_binds_to_current_def_p (alias
->decl
))
631 fprintf (dump_file
, "Declaration does not bind to currect definition.\n\n");
635 if (redirect_callers
)
637 /* If alias is non-overwritable then
638 all direct calls are safe to be redirected to the original. */
639 bool redirected
= false;
640 while (alias
->callers
)
642 cgraph_edge
*e
= alias
->callers
;
643 e
->redirect_callee (local_original
);
644 push_cfun (DECL_STRUCT_FUNCTION (e
->caller
->decl
));
647 e
->redirect_call_stmt_to_callee ();
653 alias
->icf_merged
= true;
655 /* The alias function is removed if symbol address
657 if (!alias_address_matters
)
660 if (dump_file
&& redirected
)
661 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
663 /* If the condtion above is not met, we are lucky and can turn the
664 function into real alias. */
665 else if (create_alias
)
667 alias
->icf_merged
= true;
669 /* Remove the function's body. */
670 ipa_merge_profiles (original
, alias
);
671 alias
->release_body (true);
674 /* Create the alias. */
675 cgraph_node::create_alias (alias_func
->decl
, decl
);
676 alias
->resolve_alias (original
);
678 /* Workaround for PR63566 that forces equal calling convention
680 alias
->local
.local
= false;
681 original
->local
.local
= false;
684 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
686 else if (create_thunk
)
688 if (DECL_COMDAT_GROUP (alias
->decl
))
691 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
696 alias
->icf_merged
= true;
697 ipa_merge_profiles (local_original
, alias
);
698 alias
->create_wrapper (local_original
);
701 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
704 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
709 /* Semantic item initialization function. */
712 sem_function::init (void)
715 get_node ()->get_untransformed_body ();
717 tree fndecl
= node
->decl
;
718 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
721 gcc_assert (SSANAMES (func
));
723 ssa_names_size
= SSANAMES (func
)->length ();
727 region_tree
= func
->eh
->region_tree
;
729 /* iterating all function arguments. */
730 arg_count
= count_formal_params (fndecl
);
732 edge_count
= n_edges_for_fn (func
);
733 cfg_checksum
= coverage_compute_cfg_checksum (func
);
735 inchash::hash hstate
;
738 FOR_EACH_BB_FN (bb
, func
)
740 unsigned nondbg_stmt_count
= 0;
743 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
744 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
747 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
750 gimple stmt
= gsi_stmt (gsi
);
752 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
754 hash_stmt (&hstate
, stmt
);
759 gcode_hash
= hstate
.end ();
760 bb_sizes
.safe_push (nondbg_stmt_count
);
762 /* Inserting basic block to hash table. */
763 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
764 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
766 bb_sorted
.safe_push (semantic_bb
);
772 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
775 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
777 enum gimple_code code
= gimple_code (stmt
);
779 hstate
->add_int (code
);
781 if (code
== GIMPLE_CALL
)
783 /* Checking of argument. */
784 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
786 tree argument
= gimple_call_arg (stmt
, i
);
788 switch (TREE_CODE (argument
))
791 if (tree_fits_shwi_p (argument
))
792 hstate
->add_wide_int (tree_to_shwi (argument
));
793 else if (tree_fits_uhwi_p (argument
))
794 hstate
->add_wide_int (tree_to_uhwi (argument
));
800 c
= TREE_REAL_CST (argument
);
801 n
= real_to_integer (&c
);
803 hstate
->add_wide_int (n
);
807 tree addr_operand
= TREE_OPERAND (argument
, 0);
809 if (TREE_CODE (addr_operand
) == STRING_CST
)
810 hstate
->add (TREE_STRING_POINTER (addr_operand
),
811 TREE_STRING_LENGTH (addr_operand
));
822 /* Return true if polymorphic comparison must be processed. */
825 sem_function::compare_polymorphic_p (void)
827 return get_node ()->callees
!= NULL
828 || m_compared_func
->get_node ()->callees
!= NULL
;
831 /* For a given call graph NODE, the function constructs new
832 semantic function item. */
835 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
837 tree fndecl
= node
->decl
;
838 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
840 /* TODO: add support for thunks and aliases. */
842 if (!func
|| !node
->has_gimple_body_p ())
845 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
848 sem_function
*f
= new sem_function (node
, 0, stack
);
855 /* Parses function arguments and result type. */
858 sem_function::parse_tree_args (void)
862 if (arg_types
.exists ())
863 arg_types
.release ();
865 arg_types
.create (4);
866 tree fnargs
= DECL_ARGUMENTS (decl
);
868 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
869 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
871 /* Function result type. */
872 result
= DECL_RESULT (decl
);
873 result_type
= result
? TREE_TYPE (result
) : NULL
;
875 /* During WPA, we can get arguments by following method. */
878 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
879 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
880 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
882 result_type
= TREE_TYPE (TREE_TYPE (decl
));
886 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
887 return true if phi nodes are semantically equivalent in these blocks . */
890 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
892 gphi_iterator si1
, si2
;
894 unsigned size1
, size2
, i
;
898 gcc_assert (bb1
!= NULL
);
899 gcc_assert (bb2
!= NULL
);
901 si2
= gsi_start_phis (bb2
);
902 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
905 gsi_next_nonvirtual_phi (&si1
);
906 gsi_next_nonvirtual_phi (&si2
);
908 if (gsi_end_p (si1
) && gsi_end_p (si2
))
911 if (gsi_end_p (si1
) || gsi_end_p (si2
))
912 return return_false();
917 tree phi_result1
= gimple_phi_result (phi1
);
918 tree phi_result2
= gimple_phi_result (phi2
);
920 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
921 return return_false_with_msg ("PHI results are different");
923 size1
= gimple_phi_num_args (phi1
);
924 size2
= gimple_phi_num_args (phi2
);
927 return return_false ();
929 for (i
= 0; i
< size1
; ++i
)
931 t1
= gimple_phi_arg (phi1
, i
)->def
;
932 t2
= gimple_phi_arg (phi2
, i
)->def
;
934 if (!m_checker
->compare_operand (t1
, t2
))
935 return return_false ();
937 e1
= gimple_phi_arg_edge (phi1
, i
);
938 e2
= gimple_phi_arg_edge (phi2
, i
);
940 if (!m_checker
->compare_edge (e1
, e2
))
941 return return_false ();
950 /* Returns true if tree T can be compared as a handled component. */
953 sem_function::icf_handled_component_p (tree t
)
955 tree_code tc
= TREE_CODE (t
);
957 return ((handled_component_p (t
))
958 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
959 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
962 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
963 corresponds to TARGET. */
966 sem_function::bb_dict_test (auto_vec
<int> bb_dict
, int source
, int target
)
971 if (bb_dict
.length () <= (unsigned)source
)
972 bb_dict
.safe_grow_cleared (source
+ 1);
974 if (bb_dict
[source
] == 0)
976 bb_dict
[source
] = target
;
980 return bb_dict
[source
] == target
;
983 /* Iterates all tree types in T1 and T2 and returns true if all types
984 are compatible. If COMPARE_POLYMORPHIC is set to true,
985 more strict comparison is executed. */
988 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
996 while (t1
!= NULL
&& t2
!= NULL
)
998 tv1
= TREE_VALUE (t1
);
999 tv2
= TREE_VALUE (t2
);
1001 tc1
= TREE_CODE (tv1
);
1002 tc2
= TREE_CODE (tv2
);
1004 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
1006 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
1008 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
1011 t1
= TREE_CHAIN (t1
);
1012 t2
= TREE_CHAIN (t2
);
1019 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
1021 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
1025 /* Constructor based on varpool node _NODE with computed hash _HASH.
1026 Bitmap STACK is used for memory allocation. */
1028 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
1029 bitmap_obstack
*stack
): sem_item(VAR
,
1032 gcc_checking_assert (node
);
1033 gcc_checking_assert (get_node ());
1036 /* Returns true if the item equals to ITEM given as argument. */
1039 sem_variable::equals (sem_item
*item
,
1040 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1042 gcc_assert (item
->type
== VAR
);
1044 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1046 if (!ctor
|| !v
->ctor
)
1047 return return_false_with_msg ("ctor is missing for semantic variable");
1049 return sem_variable::equals (ctor
, v
->ctor
);
1052 /* Compares trees T1 and T2 for semantic equality. */
1055 sem_variable::equals (tree t1
, tree t2
)
1057 tree_code tc1
= TREE_CODE (t1
);
1058 tree_code tc2
= TREE_CODE (t2
);
1067 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1068 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1073 for (unsigned i
= 0; i
< len1
; i
++)
1074 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1075 CONSTRUCTOR_ELT (t2
, i
)->value
)
1076 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1083 tree x1
= TREE_OPERAND (t1
, 0);
1084 tree x2
= TREE_OPERAND (t2
, 0);
1085 tree y1
= TREE_OPERAND (t1
, 1);
1086 tree y2
= TREE_OPERAND (t2
, 1);
1088 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1090 return return_false ();
1092 /* Type of the offset on MEM_REF does not matter. */
1093 return sem_variable::equals (x1
, x2
)
1094 && wi::to_offset (y1
) == wi::to_offset (y2
);
1099 tree op1
= TREE_OPERAND (t1
, 0);
1100 tree op2
= TREE_OPERAND (t2
, 0);
1101 return sem_variable::equals (op1
, op2
);
1109 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1111 && wi::to_offset (t1
) == wi::to_offset (t2
);
1115 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1118 case POINTER_PLUS_EXPR
:
1120 tree x1
= TREE_OPERAND (t1
, 0);
1121 tree x2
= TREE_OPERAND (t2
, 0);
1122 tree y1
= TREE_OPERAND (t1
, 1);
1123 tree y2
= TREE_OPERAND (t2
, 1);
1125 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1128 return return_false_with_msg ("ERROR_MARK");
1130 return return_false_with_msg ("Unknown TREE code reached");
1134 /* Parser function that visits a varpool NODE. */
1137 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1139 tree decl
= node
->decl
;
1141 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1142 bool can_handle
= readonly
&& (DECL_VIRTUAL_P (decl
)
1143 || !TREE_ADDRESSABLE (decl
));
1148 tree ctor
= ctor_for_folding (decl
);
1152 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1159 /* References independent hash function. */
1162 sem_variable::get_hash (void)
1167 inchash::hash hstate
;
1169 hstate
.add_int (456346417);
1170 hstate
.add_int (TREE_CODE (ctor
));
1172 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1174 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1175 hstate
.add_int (length
);
1178 hash
= hstate
.end ();
1183 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1187 sem_variable::merge (sem_item
*alias_item
)
1189 gcc_assert (alias_item
->type
== VAR
);
1191 if (!sem_item::target_supports_symbol_aliases_p ())
1194 fprintf (dump_file
, "Symbol aliases are not supported by target\n\n");
1198 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1200 varpool_node
*original
= get_node ();
1201 varpool_node
*alias
= alias_var
->get_node ();
1202 bool original_discardable
= false;
1204 /* See if original is in a section that can be discarded if the main
1205 symbol is not used. */
1206 if (DECL_EXTERNAL (original
->decl
))
1207 original_discardable
= true;
1208 if (original
->resolution
== LDPR_PREEMPTED_REG
1209 || original
->resolution
== LDPR_PREEMPTED_IR
)
1210 original_discardable
= true;
1211 if (original
->can_be_discarded_p ())
1212 original_discardable
= true;
1214 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1216 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1217 !compare_sections (alias_var
))
1220 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1226 // alias cycle creation check
1227 varpool_node
*n
= original
;
1231 n
= n
->get_alias_target ();
1235 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1241 alias
->analyzed
= false;
1243 DECL_INITIAL (alias
->decl
) = NULL
;
1244 alias
->need_bounds_init
= false;
1245 alias
->remove_all_references ();
1247 varpool_node::create_alias (alias_var
->decl
, decl
);
1248 alias
->resolve_alias (original
);
1251 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1258 sem_variable::compare_sections (sem_variable
*alias
)
1260 const char *source
= node
->get_section ();
1261 const char *target
= alias
->node
->get_section();
1263 if (source
== NULL
&& target
== NULL
)
1265 else if(!source
|| !target
)
1268 return strcmp (source
, target
) == 0;
1271 /* Dump symbol to FILE. */
1274 sem_variable::dump_to_file (FILE *file
)
1278 print_node (file
, "", decl
, 0);
1279 fprintf (file
, "\n\n");
1282 /* Iterates though a constructor and identifies tree references
1283 we are interested in semantic function equality. */
1286 sem_variable::parse_tree_refs (tree t
)
1288 switch (TREE_CODE (t
))
1292 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1294 for (unsigned i
= 0; i
< length
; i
++)
1295 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1302 tree op
= TREE_OPERAND (t
, 0);
1303 parse_tree_refs (op
);
1308 tree_refs
.safe_push (t
);
1316 unsigned int sem_item_optimizer::class_id
= 0;
1318 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1319 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1322 bitmap_obstack_initialize (&m_bmstack
);
1325 sem_item_optimizer::~sem_item_optimizer ()
1327 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1330 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1331 it
!= m_classes
.end (); ++it
)
1333 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1334 delete (*it
)->classes
[i
];
1336 (*it
)->classes
.release ();
1342 bitmap_obstack_release (&m_bmstack
);
1345 /* Write IPA ICF summary for symbols. */
1348 sem_item_optimizer::write_summary (void)
1350 unsigned int count
= 0;
1352 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1353 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1356 /* Calculate number of symbols to be serialized. */
1357 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1359 lsei_next_in_partition (&lsei
))
1361 symtab_node
*node
= lsei_node (lsei
);
1363 if (m_symtab_node_map
.get (node
))
1367 streamer_write_uhwi (ob
, count
);
1369 /* Process all of the symbols. */
1370 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1372 lsei_next_in_partition (&lsei
))
1374 symtab_node
*node
= lsei_node (lsei
);
1376 sem_item
**item
= m_symtab_node_map
.get (node
);
1380 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1381 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1383 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1387 streamer_write_char_stream (ob
->main_stream
, 0);
1388 produce_asm (ob
, NULL
);
1389 destroy_output_block (ob
);
1392 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1393 contains LEN bytes. */
1396 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1397 const char *data
, size_t len
)
1399 const lto_function_header
*header
=
1400 (const lto_function_header
*) data
;
1401 const int cfg_offset
= sizeof (lto_function_header
);
1402 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1403 const int string_offset
= main_offset
+ header
->main_size
;
1408 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1412 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1413 header
->string_size
, vNULL
);
1415 count
= streamer_read_uhwi (&ib_main
);
1417 for (i
= 0; i
< count
; i
++)
1421 lto_symtab_encoder_t encoder
;
1423 index
= streamer_read_uhwi (&ib_main
);
1424 encoder
= file_data
->symtab_node_encoder
;
1425 node
= lto_symtab_encoder_deref (encoder
, index
);
1427 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1429 gcc_assert (node
->definition
);
1432 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1433 (void *) node
->decl
, node
->order
);
1435 if (is_a
<cgraph_node
*> (node
))
1437 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1439 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1443 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1445 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1449 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1451 lto_data_in_delete (data_in
);
1454 /* Read IPA IPA ICF summary for symbols. */
1457 sem_item_optimizer::read_summary (void)
1459 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1460 lto_file_decl_data
*file_data
;
1463 while ((file_data
= file_data_vec
[j
++]))
1466 const char *data
= lto_get_section_data (file_data
,
1467 LTO_section_ipa_icf
, NULL
, &len
);
1470 read_section (file_data
, data
, len
);
1474 /* Register callgraph and varpool hooks. */
1477 sem_item_optimizer::register_hooks (void)
1479 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1480 (&sem_item_optimizer::cgraph_removal_hook
, this);
1482 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1483 (&sem_item_optimizer::varpool_removal_hook
, this);
1486 /* Unregister callgraph and varpool hooks. */
1489 sem_item_optimizer::unregister_hooks (void)
1491 if (m_cgraph_node_hooks
)
1492 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1494 if (m_varpool_node_hooks
)
1495 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1498 /* Adds a CLS to hashtable associated by hash value. */
1501 sem_item_optimizer::add_class (congruence_class
*cls
)
1503 gcc_assert (cls
->members
.length ());
1505 congruence_class_group
*group
= get_group_by_hash (
1506 cls
->members
[0]->get_hash (),
1507 cls
->members
[0]->type
);
1508 group
->classes
.safe_push (cls
);
1511 /* Gets a congruence class group based on given HASH value and TYPE. */
1513 congruence_class_group
*
1514 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1516 congruence_class_group
*item
= XNEW (congruence_class_group
);
1520 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1526 item
->classes
.create (1);
1533 /* Callgraph removal hook called for a NODE with a custom DATA. */
1536 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1538 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1539 optimizer
->remove_symtab_node (node
);
1542 /* Varpool removal hook called for a NODE with a custom DATA. */
1545 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1547 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1548 optimizer
->remove_symtab_node (node
);
1551 /* Remove symtab NODE triggered by symtab removal hooks. */
1554 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1556 gcc_assert (!m_classes
.elements());
1558 m_removed_items_set
.add (node
);
1562 sem_item_optimizer::remove_item (sem_item
*item
)
1564 if (m_symtab_node_map
.get (item
->node
))
1565 m_symtab_node_map
.remove (item
->node
);
1569 /* Removes all callgraph and varpool nodes that are marked by symtab
1573 sem_item_optimizer::filter_removed_items (void)
1575 auto_vec
<sem_item
*> filtered
;
1577 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1579 sem_item
*item
= m_items
[i
];
1581 if (!flag_ipa_icf_functions
&& item
->type
== FUNC
)
1587 if (!flag_ipa_icf_variables
&& item
->type
== VAR
)
1593 bool no_body_function
= false;
1595 if (item
->type
== FUNC
)
1597 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1599 no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1602 if(!m_removed_items_set
.contains (m_items
[i
]->node
)
1603 && !no_body_function
)
1605 if (item
->type
== VAR
|| (!DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1606 && !DECL_CXX_DESTRUCTOR_P (item
->decl
)))
1608 filtered
.safe_push (m_items
[i
]);
1616 /* Clean-up of released semantic items. */
1619 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1620 m_items
.safe_push (filtered
[i
]);
1623 /* Optimizer entry point. */
1626 sem_item_optimizer::execute (void)
1628 filter_removed_items ();
1629 build_hash_based_classes ();
1632 fprintf (dump_file
, "Dump after hash based groups\n");
1633 dump_cong_classes ();
1635 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1636 m_items
[i
]->init_wpa ();
1640 subdivide_classes_by_equality (true);
1643 fprintf (dump_file
, "Dump after WPA based types groups\n");
1645 dump_cong_classes ();
1647 process_cong_reduction ();
1651 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1653 dump_cong_classes ();
1655 parse_nonsingleton_classes ();
1656 subdivide_classes_by_equality ();
1659 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1661 dump_cong_classes ();
1663 unsigned int prev_class_count
= m_classes_count
;
1665 process_cong_reduction ();
1666 dump_cong_classes ();
1668 merge_classes (prev_class_count
);
1670 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1671 symtab_node::dump_table (dump_file
);
1674 /* Function responsible for visiting all potential functions and
1675 read-only variables that can be merged. */
1678 sem_item_optimizer::parse_funcs_and_vars (void)
1682 if (flag_ipa_icf_functions
)
1683 FOR_EACH_DEFINED_FUNCTION (cnode
)
1685 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1688 m_items
.safe_push (f
);
1689 m_symtab_node_map
.put (cnode
, f
);
1692 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1694 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1695 f
->dump_to_file (dump_file
);
1698 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1701 varpool_node
*vnode
;
1703 if (flag_ipa_icf_variables
)
1704 FOR_EACH_DEFINED_VARIABLE (vnode
)
1706 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1710 m_items
.safe_push (v
);
1711 m_symtab_node_map
.put (vnode
, v
);
1716 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1719 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1721 item
->index_in_class
= cls
->members
.length ();
1722 cls
->members
.safe_push (item
);
1726 /* Congruence classes are built by hash value. */
1729 sem_item_optimizer::build_hash_based_classes (void)
1731 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1733 sem_item
*item
= m_items
[i
];
1735 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1738 if (!group
->classes
.length ())
1741 group
->classes
.safe_push (new congruence_class (class_id
++));
1744 add_item_to_class (group
->classes
[0], item
);
1748 /* Build references according to call graph. */
1751 sem_item_optimizer::build_graph (void)
1753 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1755 sem_item
*item
= m_items
[i
];
1756 m_symtab_node_map
.put (item
->node
, item
);
1759 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1761 sem_item
*item
= m_items
[i
];
1763 if (item
->type
== FUNC
)
1765 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1767 cgraph_edge
*e
= cnode
->callees
;
1770 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1772 item
->add_reference (*slot
);
1778 ipa_ref
*ref
= NULL
;
1779 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1781 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1783 item
->add_reference (*slot
);
1788 /* Semantic items in classes having more than one element and initialized.
1789 In case of WPA, we load function body. */
1792 sem_item_optimizer::parse_nonsingleton_classes (void)
1794 unsigned int init_called_count
= 0;
1796 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1797 if (m_items
[i
]->cls
->members
.length () > 1)
1799 m_items
[i
]->init ();
1800 init_called_count
++;
1804 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1805 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
1808 /* Equality function for semantic items is used to subdivide existing
1809 classes. If IN_WPA, fast equality function is invoked. */
1812 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1814 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1815 it
!= m_classes
.end (); ++it
)
1817 unsigned int class_count
= (*it
)->classes
.length ();
1819 for (unsigned i
= 0; i
< class_count
; i
++)
1821 congruence_class
*c
= (*it
)->classes
[i
];
1823 if (c
->members
.length() > 1)
1825 auto_vec
<sem_item
*> new_vector
;
1827 sem_item
*first
= c
->members
[0];
1828 new_vector
.safe_push (first
);
1830 unsigned class_split_first
= (*it
)->classes
.length ();
1832 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1834 sem_item
*item
= c
->members
[j
];
1836 bool equals
= in_wpa
? first
->equals_wpa (item
,
1837 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1840 new_vector
.safe_push (item
);
1843 bool integrated
= false;
1845 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1847 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1848 bool equals
= in_wpa
? x
->equals_wpa (item
,
1849 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1854 add_item_to_class ((*it
)->classes
[k
], item
);
1862 congruence_class
*c
= new congruence_class (class_id
++);
1864 add_item_to_class (c
, item
);
1866 (*it
)->classes
.safe_push (c
);
1871 // we replace newly created new_vector for the class we've just splitted
1872 c
->members
.release ();
1873 c
->members
.create (new_vector
.length ());
1875 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1876 add_item_to_class (c
, new_vector
[j
]);
1884 /* Verify congruence classes if checking is enabled. */
1887 sem_item_optimizer::verify_classes (void)
1890 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1891 it
!= m_classes
.end (); ++it
)
1893 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1895 congruence_class
*cls
= (*it
)->classes
[i
];
1897 gcc_checking_assert (cls
);
1898 gcc_checking_assert (cls
->members
.length () > 0);
1900 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1902 sem_item
*item
= cls
->members
[j
];
1904 gcc_checking_assert (item
);
1905 gcc_checking_assert (item
->cls
== cls
);
1907 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1909 sem_usage_pair
*usage
= item
->usages
[k
];
1910 gcc_checking_assert (usage
->item
->index_in_class
<
1911 usage
->item
->cls
->members
.length ());
1919 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1920 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1921 but unused argument. */
1924 sem_item_optimizer::release_split_map (congruence_class
* const &,
1925 bitmap
const &b
, traverse_split_pair
*)
1934 /* Process split operation for a class given as pointer CLS_PTR,
1935 where bitmap B splits congruence class members. DATA is used
1936 as argument of split pair. */
1939 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
1940 bitmap
const &b
, traverse_split_pair
*pair
)
1942 sem_item_optimizer
*optimizer
= pair
->optimizer
;
1943 const congruence_class
*splitter_cls
= pair
->cls
;
1945 /* If counted bits are greater than zero and less than the number of members
1946 a group will be splitted. */
1947 unsigned popcount
= bitmap_count_bits (b
);
1949 if (popcount
> 0 && popcount
< cls
->members
.length ())
1951 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
1953 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1955 int target
= bitmap_bit_p (b
, i
);
1956 congruence_class
*tc
= newclasses
[target
];
1958 add_item_to_class (tc
, cls
->members
[i
]);
1961 #ifdef ENABLE_CHECKING
1962 for (unsigned int i
= 0; i
< 2; i
++)
1963 gcc_checking_assert (newclasses
[i
]->members
.length ());
1966 if (splitter_cls
== cls
)
1967 optimizer
->splitter_class_removed
= true;
1969 /* Remove old class from worklist if presented. */
1970 bool in_worklist
= cls
->in_worklist
;
1973 cls
->in_worklist
= false;
1975 congruence_class_group g
;
1976 g
.hash
= cls
->members
[0]->get_hash ();
1977 g
.type
= cls
->members
[0]->type
;
1979 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
1981 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
1982 if (slot
->classes
[i
] == cls
)
1984 slot
->classes
.ordered_remove (i
);
1988 /* New class will be inserted and integrated to work list. */
1989 for (unsigned int i
= 0; i
< 2; i
++)
1990 optimizer
->add_class (newclasses
[i
]);
1992 /* Two classes replace one, so that increment just by one. */
1993 optimizer
->m_classes_count
++;
1995 /* If OLD class was presented in the worklist, we remove the class
1996 and replace it will both newly created classes. */
1998 for (unsigned int i
= 0; i
< 2; i
++)
1999 optimizer
->worklist_push (newclasses
[i
]);
2000 else /* Just smaller class is inserted. */
2002 unsigned int smaller_index
= newclasses
[0]->members
.length () <
2003 newclasses
[1]->members
.length () ?
2005 optimizer
->worklist_push (newclasses
[smaller_index
]);
2008 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2010 fprintf (dump_file
, " congruence class splitted:\n");
2011 cls
->dump (dump_file
, 4);
2013 fprintf (dump_file
, " newly created groups:\n");
2014 for (unsigned int i
= 0; i
< 2; i
++)
2015 newclasses
[i
]->dump (dump_file
, 4);
2018 /* Release class if not presented in work list. */
2027 /* Tests if a class CLS used as INDEXth splits any congruence classes.
2028 Bitmap stack BMSTACK is used for bitmap allocation. */
2031 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
2034 hash_map
<congruence_class
*, bitmap
> split_map
;
2036 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2038 sem_item
*item
= cls
->members
[i
];
2040 /* Iterate all usages that have INDEX as usage of the item. */
2041 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2043 sem_usage_pair
*usage
= item
->usages
[j
];
2045 if (usage
->index
!= index
)
2048 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2053 b
= BITMAP_ALLOC (&m_bmstack
);
2054 split_map
.put (usage
->item
->cls
, b
);
2060 gcc_checking_assert (usage
->item
->cls
);
2061 gcc_checking_assert (usage
->item
->index_in_class
<
2062 usage
->item
->cls
->members
.length ());
2065 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2069 traverse_split_pair pair
;
2070 pair
.optimizer
= this;
2073 splitter_class_removed
= false;
2075 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2077 /* Bitmap clean-up. */
2079 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2082 /* Every usage of a congruence class CLS is a candidate that can split the
2083 collection of classes. Bitmap stack BMSTACK is used for bitmap
2087 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2092 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2094 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2095 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2097 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2099 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2100 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2103 do_congruence_step_for_index (cls
, i
);
2105 if (splitter_class_removed
)
2109 BITMAP_FREE (usage
);
2112 /* Adds a newly created congruence class CLS to worklist. */
2115 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2117 /* Return if the class CLS is already presented in work list. */
2118 if (cls
->in_worklist
)
2121 cls
->in_worklist
= true;
2122 worklist
.push_back (cls
);
2125 /* Pops a class from worklist. */
2128 sem_item_optimizer::worklist_pop (void)
2130 congruence_class
*cls
;
2132 while (!worklist
.empty ())
2134 cls
= worklist
.front ();
2135 worklist
.pop_front ();
2136 if (cls
->in_worklist
)
2138 cls
->in_worklist
= false;
2144 /* Work list item was already intended to be removed.
2145 The only reason for doing it is to split a class.
2146 Thus, the class CLS is deleted. */
2154 /* Iterative congruence reduction function. */
2157 sem_item_optimizer::process_cong_reduction (void)
2159 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2160 it
!= m_classes
.end (); ++it
)
2161 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2162 if ((*it
)->classes
[i
]->is_class_used ())
2163 worklist_push ((*it
)->classes
[i
]);
2166 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2167 (unsigned long) worklist
.size ());
2169 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2170 fprintf (dump_file
, "Congruence class reduction\n");
2172 congruence_class
*cls
;
2173 while ((cls
= worklist_pop ()) != NULL
)
2174 do_congruence_step (cls
);
2177 /* Debug function prints all informations about congruence classes. */
2180 sem_item_optimizer::dump_cong_classes (void)
2186 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2187 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2189 /* Histogram calculation. */
2190 unsigned int max_index
= 0;
2191 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2193 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2194 it
!= m_classes
.end (); ++it
)
2196 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2198 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2206 "Class size histogram [num of members]: number of classe number of classess\n");
2208 for (unsigned int i
= 0; i
<= max_index
; i
++)
2210 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2212 fprintf (dump_file
, "\n\n");
2215 if (dump_flags
& TDF_DETAILS
)
2216 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2217 it
!= m_classes
.end (); ++it
)
2219 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2221 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2223 (*it
)->classes
[i
]->dump (dump_file
, 4);
2225 if(i
< (*it
)->classes
.length () - 1)
2226 fprintf (dump_file
, " ");
2233 /* After reduction is done, we can declare all items in a group
2234 to be equal. PREV_CLASS_COUNT is start number of classes
2235 before reduction. */
2238 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2240 unsigned int item_count
= m_items
.length ();
2241 unsigned int class_count
= m_classes_count
;
2242 unsigned int equal_items
= item_count
- class_count
;
2244 unsigned int non_singular_classes_count
= 0;
2245 unsigned int non_singular_classes_sum
= 0;
2247 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2248 it
!= m_classes
.end (); ++it
)
2249 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2251 congruence_class
*c
= (*it
)->classes
[i
];
2252 if (c
->members
.length () > 1)
2254 non_singular_classes_count
++;
2255 non_singular_classes_sum
+= c
->members
.length ();
2261 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2262 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2263 prev_class_count
, class_count
);
2264 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2265 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2266 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2267 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2268 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2269 non_singular_classes_count
: 0.0f
,
2270 non_singular_classes_count
);
2271 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2272 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2273 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2276 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2277 it
!= m_classes
.end (); ++it
)
2278 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2280 congruence_class
*c
= (*it
)->classes
[i
];
2282 if (c
->members
.length () == 1)
2285 gcc_assert (c
->members
.length ());
2287 sem_item
*source
= c
->members
[0];
2289 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2291 sem_item
*alias
= c
->members
[j
];
2292 source
->equals (alias
, m_symtab_node_map
);
2296 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2297 source
->name (), alias
->name ());
2298 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2299 source
->asm_name (), alias
->asm_name ());
2302 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2304 source
->dump_to_file (dump_file
);
2305 alias
->dump_to_file (dump_file
);
2308 source
->merge (alias
);
2313 /* Dump function prints all class members to a FILE with an INDENT. */
2316 congruence_class::dump (FILE *file
, unsigned int indent
) const
2318 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2319 id
, members
[0]->get_hash (), members
.length ());
2321 FPUTS_SPACES (file
, indent
+ 2, "");
2322 for (unsigned i
= 0; i
< members
.length (); i
++)
2323 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2324 members
[i
]->node
->order
);
2326 fprintf (file
, "\n");
2329 /* Returns true if there's a member that is used from another group. */
2332 congruence_class::is_class_used (void)
2334 for (unsigned int i
= 0; i
< members
.length (); i
++)
2335 if (members
[i
]->usages
.length ())
2341 /* Initialization and computation of symtab node hash, there data
2342 are propagated later on. */
2344 static sem_item_optimizer
*optimizer
= NULL
;
2346 /* Generate pass summary for IPA ICF pass. */
2349 ipa_icf_generate_summary (void)
2352 optimizer
= new sem_item_optimizer ();
2354 optimizer
->parse_funcs_and_vars ();
2357 /* Write pass summary for IPA ICF pass. */
2360 ipa_icf_write_summary (void)
2362 gcc_assert (optimizer
);
2364 optimizer
->write_summary ();
2367 /* Read pass summary for IPA ICF pass. */
2370 ipa_icf_read_summary (void)
2373 optimizer
= new sem_item_optimizer ();
2375 optimizer
->read_summary ();
2376 optimizer
->register_hooks ();
2379 /* Semantic equality exection function. */
2382 ipa_icf_driver (void)
2384 gcc_assert (optimizer
);
2386 optimizer
->execute ();
2387 optimizer
->unregister_hooks ();
2395 const pass_data pass_data_ipa_icf
=
2397 IPA_PASS
, /* type */
2399 OPTGROUP_IPA
, /* optinfo_flags */
2400 TV_IPA_ICF
, /* tv_id */
2401 0, /* properties_required */
2402 0, /* properties_provided */
2403 0, /* properties_destroyed */
2404 0, /* todo_flags_start */
2405 0, /* todo_flags_finish */
2408 class pass_ipa_icf
: public ipa_opt_pass_d
2411 pass_ipa_icf (gcc::context
*ctxt
)
2412 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2413 ipa_icf_generate_summary
, /* generate_summary */
2414 ipa_icf_write_summary
, /* write_summary */
2415 ipa_icf_read_summary
, /* read_summary */
2417 write_optimization_summary */
2419 read_optimization_summary */
2420 NULL
, /* stmt_fixup */
2421 0, /* function_transform_todo_flags_start */
2422 NULL
, /* function_transform */
2423 NULL
) /* variable_transform */
2426 /* opt_pass methods: */
2427 virtual bool gate (function
*)
2429 return flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2432 virtual unsigned int execute (function
*)
2434 return ipa_icf_driver();
2436 }; // class pass_ipa_icf
2438 } // ipa_icf namespace
2441 make_pass_ipa_icf (gcc::context
*ctxt
)
2443 return new ipa_icf::pass_ipa_icf (ctxt
);