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"
105 using namespace ipa_icf_gimple
;
108 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
110 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
111 item (_item
), index (_index
)
115 /* Semantic item constructor for a node of _TYPE, where STACK is used
116 for bitmap memory allocation. */
118 sem_item::sem_item (sem_item_type _type
,
119 bitmap_obstack
*stack
): type(_type
), hash(0)
124 /* Semantic item constructor for a node of _TYPE, where STACK is used
125 for bitmap memory allocation. The item is based on symtab node _NODE
126 with computed _HASH. */
128 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
129 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
130 node (_node
), hash (_hash
)
136 /* Add reference to a semantic TARGET. */
139 sem_item::add_reference (sem_item
*target
)
141 refs
.safe_push (target
);
142 unsigned index
= refs
.length ();
143 target
->usages
.safe_push (new sem_usage_pair(this, index
));
144 bitmap_set_bit (target
->usage_index_bitmap
, index
);
145 refs_set
.add (target
->node
);
148 /* Initialize internal data structures. Bitmap STACK is used for
149 bitmap memory allocation process. */
152 sem_item::setup (bitmap_obstack
*stack
)
154 gcc_checking_assert (node
);
157 tree_refs
.create (0);
159 usage_index_bitmap
= BITMAP_ALLOC (stack
);
162 sem_item::~sem_item ()
164 for (unsigned i
= 0; i
< usages
.length (); i
++)
168 tree_refs
.release ();
171 BITMAP_FREE (usage_index_bitmap
);
174 /* Dump function for debugging purpose. */
177 sem_item::dump (void)
181 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
182 name(), node
->order
, (void *) node
->decl
);
183 fprintf (dump_file
, " hash: %u\n", get_hash ());
184 fprintf (dump_file
, " references: ");
186 for (unsigned i
= 0; i
< refs
.length (); i
++)
187 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
188 i
< refs
.length() - 1 ? "," : "");
190 fprintf (dump_file
, "\n");
194 /* Semantic function constructor that uses STACK as bitmap memory stack. */
196 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
197 m_checker (NULL
), m_compared_func (NULL
)
199 arg_types
.create (0);
201 bb_sorted
.create (0);
204 /* Constructor based on callgraph node _NODE with computed hash _HASH.
205 Bitmap STACK is used for memory allocation. */
206 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
207 bitmap_obstack
*stack
):
208 sem_item (FUNC
, node
, hash
, stack
),
209 m_checker (NULL
), m_compared_func (NULL
)
211 arg_types
.create (0);
213 bb_sorted
.create (0);
216 sem_function::~sem_function ()
218 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
221 arg_types
.release ();
223 bb_sorted
.release ();
226 /* Calculates hash value based on a BASIC_BLOCK. */
229 sem_function::get_bb_hash (const sem_bb
*basic_block
)
231 inchash::hash hstate
;
233 hstate
.add_int (basic_block
->nondbg_stmt_count
);
234 hstate
.add_int (basic_block
->edge_count
);
236 return hstate
.end ();
239 /* References independent hash function. */
242 sem_function::get_hash (void)
246 inchash::hash hstate
;
247 hstate
.add_int (177454); /* Random number for function type. */
249 hstate
.add_int (arg_count
);
250 hstate
.add_int (cfg_checksum
);
251 hstate
.add_int (gcode_hash
);
253 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
254 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
256 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
257 hstate
.add_int (bb_sizes
[i
]);
259 hash
= hstate
.end ();
265 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
266 point to a same function. Comparison can be skipped if IGNORED_NODES
267 contains these nodes. */
270 sem_function::compare_cgraph_references (hash_map
<symtab_node
*, sem_item
*>
272 symtab_node
*n1
, symtab_node
*n2
)
274 if (n1
== n2
|| (ignored_nodes
.get (n1
) && ignored_nodes
.get (n2
)))
277 /* TODO: add more precise comparison for weakrefs, etc. */
279 return return_false_with_msg ("different references");
282 /* If cgraph edges E1 and E2 are indirect calls, verify that
283 ECF flags are the same. */
285 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
287 if (e1
->indirect_info
&& e2
->indirect_info
)
289 int e1_flags
= e1
->indirect_info
->ecf_flags
;
290 int e2_flags
= e2
->indirect_info
->ecf_flags
;
292 if (e1_flags
!= e2_flags
)
293 return return_false_with_msg ("ICF flags are different");
295 else if (e1
->indirect_info
|| e2
->indirect_info
)
301 /* Fast equality function based on knowledge known in WPA. */
304 sem_function::equals_wpa (sem_item
*item
,
305 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
307 gcc_assert (item
->type
== FUNC
);
309 m_compared_func
= static_cast<sem_function
*> (item
);
311 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
312 return return_false_with_msg ("different number of arguments");
314 /* Checking types of arguments. */
315 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
317 /* This guard is here for function pointer with attributes (pr59927.c). */
318 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
319 return return_false_with_msg ("NULL argument type");
321 /* Polymorphic comparison is executed just for non-leaf functions. */
322 bool is_not_leaf
= get_node ()->callees
!= NULL
;
324 if (!func_checker::compatible_types_p (arg_types
[i
],
325 m_compared_func
->arg_types
[i
],
326 is_not_leaf
, i
== 0))
327 return return_false_with_msg ("argument type is different");
330 /* Result type checking. */
331 if (!func_checker::compatible_types_p (result_type
,
332 m_compared_func
->result_type
))
333 return return_false_with_msg ("result types are different");
335 if (node
->num_references () != item
->node
->num_references ())
336 return return_false_with_msg ("different number of references");
338 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
339 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
341 item
->node
->iterate_reference (i
, ref2
);
343 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
, ref2
->referred
))
347 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
348 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
352 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
, e2
->callee
))
355 e1
= e1
->next_callee
;
356 e2
= e2
->next_callee
;
360 return return_false_with_msg ("different number of edges");
365 /* Returns true if the item equals to ITEM given as argument. */
368 sem_function::equals (sem_item
*item
,
369 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
371 gcc_assert (item
->type
== FUNC
);
372 bool eq
= equals_private (item
, ignored_nodes
);
374 if (m_checker
!= NULL
)
380 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
382 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
383 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
384 item
->asm_name (), eq
? "true" : "false");
389 /* Processes function equality comparison. */
392 sem_function::equals_private (sem_item
*item
,
393 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
395 if (item
->type
!= FUNC
)
398 basic_block bb1
, bb2
;
400 edge_iterator ei1
, ei2
;
405 m_compared_func
= static_cast<sem_function
*> (item
);
407 gcc_assert (decl
!= item
->decl
);
409 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
410 || edge_count
!= m_compared_func
->edge_count
411 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
412 return return_false ();
414 if (!equals_wpa (item
, ignored_nodes
))
417 /* Checking function arguments. */
418 tree decl1
= DECL_ATTRIBUTES (decl
);
419 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
421 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
422 compare_polymorphic_p (),
425 &m_compared_func
->refs_set
);
429 return return_false ();
431 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
432 return return_false ();
434 tree attr_value1
= TREE_VALUE (decl1
);
435 tree attr_value2
= TREE_VALUE (decl2
);
437 if (attr_value1
&& attr_value2
)
439 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
440 TREE_VALUE (attr_value2
));
442 return return_false_with_msg ("attribute values are different");
444 else if (!attr_value1
&& !attr_value2
)
447 return return_false ();
449 decl1
= TREE_CHAIN (decl1
);
450 decl2
= TREE_CHAIN (decl2
);
454 return return_false();
457 for (arg1
= DECL_ARGUMENTS (decl
),
458 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
459 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
460 if (!m_checker
->compare_decl (arg1
, arg2
))
461 return return_false ();
463 /* Fill-up label dictionary. */
464 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
466 m_checker
->parse_labels (bb_sorted
[i
]);
467 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
470 /* Checking all basic blocks. */
471 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
472 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
473 return return_false();
475 dump_message ("All BBs are equal\n");
477 /* Basic block edges check. */
478 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
480 bb_dict
= XNEWVEC (int, bb_sorted
.length () + 2);
481 memset (bb_dict
, -1, (bb_sorted
.length () + 2) * sizeof (int));
483 bb1
= bb_sorted
[i
]->bb
;
484 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
486 ei2
= ei_start (bb2
->preds
);
488 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
492 if (e1
->flags
!= e2
->flags
)
493 return return_false_with_msg ("flags comparison returns false");
495 if (!bb_dict_test (bb_dict
, e1
->src
->index
, e2
->src
->index
))
496 return return_false_with_msg ("edge comparison returns false");
498 if (!bb_dict_test (bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
499 return return_false_with_msg ("BB comparison returns false");
501 if (!m_checker
->compare_edge (e1
, e2
))
502 return return_false_with_msg ("edge comparison returns false");
508 /* Basic block PHI nodes comparison. */
509 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
510 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
511 return return_false_with_msg ("PHI node comparison returns false");
516 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
519 sem_function::merge (sem_item
*alias_item
)
521 gcc_assert (alias_item
->type
== FUNC
);
523 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
525 cgraph_node
*original
= get_node ();
526 cgraph_node
*local_original
= original
;
527 cgraph_node
*alias
= alias_func
->get_node ();
528 bool original_address_matters
;
529 bool alias_address_matters
;
531 bool create_thunk
= false;
532 bool create_alias
= false;
533 bool redirect_callers
= false;
534 bool original_discardable
= false;
536 /* Do not attempt to mix functions from different user sections;
537 we do not know what user intends with those. */
538 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
539 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
540 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
544 "Not unifying; original and alias are in different sections.\n\n");
548 /* See if original is in a section that can be discarded if the main
549 symbol is not used. */
550 if (DECL_EXTERNAL (original
->decl
))
551 original_discardable
= true;
552 if (original
->resolution
== LDPR_PREEMPTED_REG
553 || original
->resolution
== LDPR_PREEMPTED_IR
)
554 original_discardable
= true;
555 if (original
->can_be_discarded_p ())
556 original_discardable
= true;
558 /* See if original and/or alias address can be compared for equality. */
559 original_address_matters
560 = (!DECL_VIRTUAL_P (original
->decl
)
561 && (original
->externally_visible
562 || original
->address_taken_from_non_vtable_p ()));
563 alias_address_matters
564 = (!DECL_VIRTUAL_P (alias
->decl
)
565 && (alias
->externally_visible
566 || alias
->address_taken_from_non_vtable_p ()));
568 /* If alias and original can be compared for address equality, we need
569 to create a thunk. Also we can not create extra aliases into discardable
570 section (or we risk link failures when section is discarded). */
571 if ((original_address_matters
572 && alias_address_matters
)
573 || original_discardable
)
575 create_thunk
= !stdarg_p (TREE_TYPE (alias
->decl
));
576 create_alias
= false;
577 /* When both alias and original are not overwritable, we can save
578 the extra thunk wrapper for direct calls. */
580 = (!original_discardable
581 && alias
->get_availability () > AVAIL_INTERPOSABLE
582 && original
->get_availability () > AVAIL_INTERPOSABLE
);
587 create_thunk
= false;
588 redirect_callers
= false;
591 if (create_alias
&& DECL_COMDAT_GROUP (alias
->decl
))
593 create_alias
= false;
597 /* We want thunk to always jump to the local function body
598 unless the body is comdat and may be optimized out. */
599 if ((create_thunk
|| redirect_callers
)
600 && (!original_discardable
601 || (DECL_COMDAT_GROUP (original
->decl
)
602 && (DECL_COMDAT_GROUP (original
->decl
)
603 == DECL_COMDAT_GROUP (alias
->decl
)))))
605 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
607 if (redirect_callers
)
609 /* If alias is non-overwritable then
610 all direct calls are safe to be redirected to the original. */
611 bool redirected
= false;
612 while (alias
->callers
)
614 cgraph_edge
*e
= alias
->callers
;
615 e
->redirect_callee (local_original
);
616 push_cfun (DECL_STRUCT_FUNCTION (e
->caller
->decl
));
619 e
->redirect_call_stmt_to_callee ();
625 alias
->icf_merged
= true;
627 /* The alias function is removed if symbol address
629 if (!alias_address_matters
)
632 if (dump_file
&& redirected
)
633 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
635 /* If the condtion above is not met, we are lucky and can turn the
636 function into real alias. */
637 else if (create_alias
)
639 alias
->icf_merged
= true;
641 /* Remove the function's body. */
642 ipa_merge_profiles (original
, alias
);
643 alias
->release_body (true);
646 /* Create the alias. */
647 cgraph_node::create_alias (alias_func
->decl
, decl
);
648 alias
->resolve_alias (original
);
650 /* Workaround for PR63566 that forces equal calling convention
652 alias
->local
.local
= false;
653 original
->local
.local
= false;
656 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
658 else if (create_thunk
)
660 if (DECL_COMDAT_GROUP (alias
->decl
))
663 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
668 alias
->icf_merged
= true;
669 ipa_merge_profiles (local_original
, alias
);
670 alias
->create_wrapper (local_original
);
673 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
676 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
681 /* Semantic item initialization function. */
684 sem_function::init (void)
687 get_node ()->get_body ();
689 tree fndecl
= node
->decl
;
690 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
693 gcc_assert (SSANAMES (func
));
695 ssa_names_size
= SSANAMES (func
)->length ();
699 region_tree
= func
->eh
->region_tree
;
701 /* iterating all function arguments. */
702 arg_count
= count_formal_params (fndecl
);
704 edge_count
= n_edges_for_fn (func
);
705 cfg_checksum
= coverage_compute_cfg_checksum (func
);
707 inchash::hash hstate
;
710 FOR_EACH_BB_FN (bb
, func
)
712 unsigned nondbg_stmt_count
= 0;
715 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
716 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
719 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
722 gimple stmt
= gsi_stmt (gsi
);
724 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
726 hash_stmt (&hstate
, stmt
);
731 gcode_hash
= hstate
.end ();
732 bb_sizes
.safe_push (nondbg_stmt_count
);
734 /* Inserting basic block to hash table. */
735 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
736 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
738 bb_sorted
.safe_push (semantic_bb
);
744 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
747 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
749 enum gimple_code code
= gimple_code (stmt
);
751 hstate
->add_int (code
);
753 if (code
== GIMPLE_CALL
)
755 /* Checking of argument. */
756 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
758 tree argument
= gimple_call_arg (stmt
, i
);
760 switch (TREE_CODE (argument
))
763 if (tree_fits_shwi_p (argument
))
764 hstate
->add_wide_int (tree_to_shwi (argument
));
765 else if (tree_fits_uhwi_p (argument
))
766 hstate
->add_wide_int (tree_to_uhwi (argument
));
772 c
= TREE_REAL_CST (argument
);
773 n
= real_to_integer (&c
);
775 hstate
->add_wide_int (n
);
779 tree addr_operand
= TREE_OPERAND (argument
, 0);
781 if (TREE_CODE (addr_operand
) == STRING_CST
)
782 hstate
->add (TREE_STRING_POINTER (addr_operand
),
783 TREE_STRING_LENGTH (addr_operand
));
794 /* Return true if polymorphic comparison must be processed. */
797 sem_function::compare_polymorphic_p (void)
799 return get_node ()->callees
!= NULL
800 || m_compared_func
->get_node ()->callees
!= NULL
;
803 /* For a given call graph NODE, the function constructs new
804 semantic function item. */
807 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
809 tree fndecl
= node
->decl
;
810 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
812 /* TODO: add support for thunks and aliases. */
814 if (!func
|| !node
->has_gimple_body_p ())
817 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
820 sem_function
*f
= new sem_function (node
, 0, stack
);
827 /* Parses function arguments and result type. */
830 sem_function::parse_tree_args (void)
834 if (arg_types
.exists ())
835 arg_types
.release ();
837 arg_types
.create (4);
838 tree fnargs
= DECL_ARGUMENTS (decl
);
840 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
841 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
843 /* Function result type. */
844 result
= DECL_RESULT (decl
);
845 result_type
= result
? TREE_TYPE (result
) : NULL
;
847 /* During WPA, we can get arguments by following method. */
850 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
851 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
852 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
854 result_type
= TREE_TYPE (TREE_TYPE (decl
));
858 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
859 return true if phi nodes are semantically equivalent in these blocks . */
862 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
864 gimple_stmt_iterator si1
, si2
;
866 unsigned size1
, size2
, i
;
870 gcc_assert (bb1
!= NULL
);
871 gcc_assert (bb2
!= NULL
);
873 si2
= gsi_start_phis (bb2
);
874 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
877 gsi_next_nonvirtual_phi (&si1
);
878 gsi_next_nonvirtual_phi (&si2
);
880 if (gsi_end_p (si1
) && gsi_end_p (si2
))
883 if (gsi_end_p (si1
) || gsi_end_p (si2
))
884 return return_false();
886 phi1
= gsi_stmt (si1
);
887 phi2
= gsi_stmt (si2
);
889 tree phi_result1
= gimple_phi_result (phi1
);
890 tree phi_result2
= gimple_phi_result (phi2
);
892 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
893 return return_false_with_msg ("PHI results are different");
895 size1
= gimple_phi_num_args (phi1
);
896 size2
= gimple_phi_num_args (phi2
);
899 return return_false ();
901 for (i
= 0; i
< size1
; ++i
)
903 t1
= gimple_phi_arg (phi1
, i
)->def
;
904 t2
= gimple_phi_arg (phi2
, i
)->def
;
906 if (!m_checker
->compare_operand (t1
, t2
))
907 return return_false ();
909 e1
= gimple_phi_arg_edge (phi1
, i
);
910 e2
= gimple_phi_arg_edge (phi2
, i
);
912 if (!m_checker
->compare_edge (e1
, e2
))
913 return return_false ();
922 /* Returns true if tree T can be compared as a handled component. */
925 sem_function::icf_handled_component_p (tree t
)
927 tree_code tc
= TREE_CODE (t
);
929 return ((handled_component_p (t
))
930 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
931 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
934 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
935 corresponds to TARGET. */
938 sem_function::bb_dict_test (int* bb_dict
, int source
, int target
)
940 if (bb_dict
[source
] == -1)
942 bb_dict
[source
] = target
;
946 return bb_dict
[source
] == target
;
949 /* Iterates all tree types in T1 and T2 and returns true if all types
950 are compatible. If COMPARE_POLYMORPHIC is set to true,
951 more strict comparison is executed. */
954 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
962 while (t1
!= NULL
&& t2
!= NULL
)
964 tv1
= TREE_VALUE (t1
);
965 tv2
= TREE_VALUE (t2
);
967 tc1
= TREE_CODE (tv1
);
968 tc2
= TREE_CODE (tv2
);
970 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
972 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
974 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
977 t1
= TREE_CHAIN (t1
);
978 t2
= TREE_CHAIN (t2
);
985 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
987 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
991 /* Constructor based on varpool node _NODE with computed hash _HASH.
992 Bitmap STACK is used for memory allocation. */
994 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
995 bitmap_obstack
*stack
): sem_item(VAR
,
998 gcc_checking_assert (node
);
999 gcc_checking_assert (get_node ());
1002 /* Returns true if the item equals to ITEM given as argument. */
1005 sem_variable::equals (sem_item
*item
,
1006 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1008 gcc_assert (item
->type
== VAR
);
1010 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1012 if (!ctor
|| !v
->ctor
)
1013 return return_false_with_msg ("ctor is missing for semantic variable");
1015 return sem_variable::equals (ctor
, v
->ctor
);
1018 /* Compares trees T1 and T2 for semantic equality. */
1021 sem_variable::equals (tree t1
, tree t2
)
1023 tree_code tc1
= TREE_CODE (t1
);
1024 tree_code tc2
= TREE_CODE (t2
);
1033 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1034 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1039 for (unsigned i
= 0; i
< len1
; i
++)
1040 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1041 CONSTRUCTOR_ELT (t2
, i
)->value
)
1042 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1049 tree x1
= TREE_OPERAND (t1
, 0);
1050 tree x2
= TREE_OPERAND (t2
, 0);
1051 tree y1
= TREE_OPERAND (t1
, 1);
1052 tree y2
= TREE_OPERAND (t2
, 1);
1054 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1056 return return_false ();
1058 /* Type of the offset on MEM_REF does not matter. */
1059 return sem_variable::equals (x1
, x2
)
1060 && wi::to_offset (y1
) == wi::to_offset (y2
);
1065 tree op1
= TREE_OPERAND (t1
, 0);
1066 tree op2
= TREE_OPERAND (t2
, 0);
1067 return sem_variable::equals (op1
, op2
);
1075 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1077 && wi::to_offset (t1
) == wi::to_offset (t2
);
1081 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1084 case POINTER_PLUS_EXPR
:
1086 tree x1
= TREE_OPERAND (t1
, 0);
1087 tree x2
= TREE_OPERAND (t2
, 0);
1088 tree y1
= TREE_OPERAND (t1
, 1);
1089 tree y2
= TREE_OPERAND (t2
, 1);
1091 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1094 return return_false_with_msg ("ERROR_MARK");
1096 return return_false_with_msg ("Unknown TREE code reached");
1100 /* Parser function that visits a varpool NODE. */
1103 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1105 tree decl
= node
->decl
;
1107 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1108 bool can_handle
= readonly
&& (DECL_VIRTUAL_P (decl
)
1109 || !TREE_ADDRESSABLE (decl
));
1114 tree ctor
= ctor_for_folding (decl
);
1118 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1125 /* References independent hash function. */
1128 sem_variable::get_hash (void)
1133 inchash::hash hstate
;
1135 hstate
.add_int (456346417);
1136 hstate
.add_int (TREE_CODE (ctor
));
1138 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1140 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1141 hstate
.add_int (length
);
1144 hash
= hstate
.end ();
1149 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1153 sem_variable::merge (sem_item
*alias_item
)
1155 gcc_assert (alias_item
->type
== VAR
);
1157 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1159 varpool_node
*original
= get_node ();
1160 varpool_node
*alias
= alias_var
->get_node ();
1161 bool original_discardable
= false;
1163 /* See if original is in a section that can be discarded if the main
1164 symbol is not used. */
1165 if (DECL_EXTERNAL (original
->decl
))
1166 original_discardable
= true;
1167 if (original
->resolution
== LDPR_PREEMPTED_REG
1168 || original
->resolution
== LDPR_PREEMPTED_IR
)
1169 original_discardable
= true;
1170 if (original
->can_be_discarded_p ())
1171 original_discardable
= true;
1173 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1175 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1176 !compare_sections (alias_var
))
1179 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1185 // alias cycle creation check
1186 varpool_node
*n
= original
;
1190 n
= n
->get_alias_target ();
1194 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1200 alias
->analyzed
= false;
1202 DECL_INITIAL (alias
->decl
) = NULL
;
1203 alias
->remove_all_references ();
1205 varpool_node::create_alias (alias_var
->decl
, decl
);
1206 alias
->resolve_alias (original
);
1209 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1216 sem_variable::compare_sections (sem_variable
*alias
)
1218 const char *source
= node
->get_section ();
1219 const char *target
= alias
->node
->get_section();
1221 if (source
== NULL
&& target
== NULL
)
1223 else if(!source
|| !target
)
1226 return strcmp (source
, target
) == 0;
1229 /* Dump symbol to FILE. */
1232 sem_variable::dump_to_file (FILE *file
)
1236 print_node (file
, "", decl
, 0);
1237 fprintf (file
, "\n\n");
1240 /* Iterates though a constructor and identifies tree references
1241 we are interested in semantic function equality. */
1244 sem_variable::parse_tree_refs (tree t
)
1246 switch (TREE_CODE (t
))
1250 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1252 for (unsigned i
= 0; i
< length
; i
++)
1253 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1260 tree op
= TREE_OPERAND (t
, 0);
1261 parse_tree_refs (op
);
1266 tree_refs
.safe_push (t
);
1274 unsigned int sem_item_optimizer::class_id
= 0;
1276 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1277 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1280 bitmap_obstack_initialize (&m_bmstack
);
1283 sem_item_optimizer::~sem_item_optimizer ()
1285 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1288 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1289 it
!= m_classes
.end (); ++it
)
1291 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1292 delete (*it
)->classes
[i
];
1294 (*it
)->classes
.release ();
1299 bitmap_obstack_release (&m_bmstack
);
1302 /* Write IPA ICF summary for symbols. */
1305 sem_item_optimizer::write_summary (void)
1307 unsigned int count
= 0;
1309 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1310 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1313 /* Calculate number of symbols to be serialized. */
1314 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1316 lsei_next_in_partition (&lsei
))
1318 symtab_node
*node
= lsei_node (lsei
);
1320 if (m_symtab_node_map
.get (node
))
1324 streamer_write_uhwi (ob
, count
);
1326 /* Process all of the symbols. */
1327 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1329 lsei_next_in_partition (&lsei
))
1331 symtab_node
*node
= lsei_node (lsei
);
1333 sem_item
**item
= m_symtab_node_map
.get (node
);
1337 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1338 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1340 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1344 streamer_write_char_stream (ob
->main_stream
, 0);
1345 produce_asm (ob
, NULL
);
1346 destroy_output_block (ob
);
1349 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1350 contains LEN bytes. */
1353 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1354 const char *data
, size_t len
)
1356 const lto_function_header
*header
=
1357 (const lto_function_header
*) data
;
1358 const int cfg_offset
= sizeof (lto_function_header
);
1359 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1360 const int string_offset
= main_offset
+ header
->main_size
;
1365 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1369 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1370 header
->string_size
, vNULL
);
1372 count
= streamer_read_uhwi (&ib_main
);
1374 for (i
= 0; i
< count
; i
++)
1378 lto_symtab_encoder_t encoder
;
1380 index
= streamer_read_uhwi (&ib_main
);
1381 encoder
= file_data
->symtab_node_encoder
;
1382 node
= lto_symtab_encoder_deref (encoder
, index
);
1384 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1386 gcc_assert (node
->definition
);
1389 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1390 (void *) node
->decl
, node
->order
);
1392 if (is_a
<cgraph_node
*> (node
))
1394 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1396 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1400 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1402 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1406 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1408 lto_data_in_delete (data_in
);
1411 /* Read IPA IPA ICF summary for symbols. */
1414 sem_item_optimizer::read_summary (void)
1416 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1417 lto_file_decl_data
*file_data
;
1420 while ((file_data
= file_data_vec
[j
++]))
1423 const char *data
= lto_get_section_data (file_data
,
1424 LTO_section_ipa_icf
, NULL
, &len
);
1427 read_section (file_data
, data
, len
);
1431 /* Register callgraph and varpool hooks. */
1434 sem_item_optimizer::register_hooks (void)
1436 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1437 (&sem_item_optimizer::cgraph_removal_hook
, this);
1439 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1440 (&sem_item_optimizer::varpool_removal_hook
, this);
1443 /* Unregister callgraph and varpool hooks. */
1446 sem_item_optimizer::unregister_hooks (void)
1448 if (m_cgraph_node_hooks
)
1449 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1451 if (m_varpool_node_hooks
)
1452 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1455 /* Adds a CLS to hashtable associated by hash value. */
1458 sem_item_optimizer::add_class (congruence_class
*cls
)
1460 gcc_assert (cls
->members
.length ());
1462 congruence_class_group
*group
= get_group_by_hash (
1463 cls
->members
[0]->get_hash (),
1464 cls
->members
[0]->type
);
1465 group
->classes
.safe_push (cls
);
1468 /* Gets a congruence class group based on given HASH value and TYPE. */
1470 congruence_class_group
*
1471 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1473 congruence_class_group
*item
= XNEW (congruence_class_group
);
1477 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1483 item
->classes
.create (1);
1490 /* Callgraph removal hook called for a NODE with a custom DATA. */
1493 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1495 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1496 optimizer
->remove_symtab_node (node
);
1499 /* Varpool removal hook called for a NODE with a custom DATA. */
1502 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1504 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1505 optimizer
->remove_symtab_node (node
);
1508 /* Remove symtab NODE triggered by symtab removal hooks. */
1511 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1513 gcc_assert (!m_classes
.elements());
1515 m_removed_items_set
.add (node
);
1519 sem_item_optimizer::remove_item (sem_item
*item
)
1521 if (m_symtab_node_map
.get (item
->node
))
1522 m_symtab_node_map
.remove (item
->node
);
1526 /* Removes all callgraph and varpool nodes that are marked by symtab
1530 sem_item_optimizer::filter_removed_items (void)
1532 auto_vec
<sem_item
*> filtered
;
1534 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1536 sem_item
*item
= m_items
[i
];
1538 if (!flag_ipa_icf_functions
&& item
->type
== FUNC
)
1544 if (!flag_ipa_icf_variables
&& item
->type
== VAR
)
1550 bool no_body_function
= false;
1552 if (item
->type
== FUNC
)
1554 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1556 no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1559 if(!m_removed_items_set
.contains (m_items
[i
]->node
)
1560 && !no_body_function
)
1562 if (item
->type
== VAR
|| (!DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1563 && !DECL_CXX_DESTRUCTOR_P (item
->decl
)))
1565 filtered
.safe_push (m_items
[i
]);
1573 /* Clean-up of released semantic items. */
1576 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1577 m_items
.safe_push (filtered
[i
]);
1580 /* Optimizer entry point. */
1583 sem_item_optimizer::execute (void)
1585 filter_removed_items ();
1586 build_hash_based_classes ();
1589 fprintf (dump_file
, "Dump after hash based groups\n");
1590 dump_cong_classes ();
1592 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1593 m_items
[i
]->init_wpa ();
1597 subdivide_classes_by_equality (true);
1600 fprintf (dump_file
, "Dump after WPA based types groups\n");
1602 dump_cong_classes ();
1604 process_cong_reduction ();
1608 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1610 dump_cong_classes ();
1612 parse_nonsingleton_classes ();
1613 subdivide_classes_by_equality ();
1616 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1618 dump_cong_classes ();
1620 unsigned int prev_class_count
= m_classes_count
;
1622 process_cong_reduction ();
1623 dump_cong_classes ();
1625 merge_classes (prev_class_count
);
1627 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1628 symtab_node::dump_table (dump_file
);
1631 /* Function responsible for visiting all potential functions and
1632 read-only variables that can be merged. */
1635 sem_item_optimizer::parse_funcs_and_vars (void)
1639 if (flag_ipa_icf_functions
)
1640 FOR_EACH_DEFINED_FUNCTION (cnode
)
1642 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1645 m_items
.safe_push (f
);
1646 m_symtab_node_map
.put (cnode
, f
);
1649 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1651 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1652 f
->dump_to_file (dump_file
);
1655 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1658 varpool_node
*vnode
;
1660 if (flag_ipa_icf_variables
)
1661 FOR_EACH_DEFINED_VARIABLE (vnode
)
1663 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1667 m_items
.safe_push (v
);
1668 m_symtab_node_map
.put (vnode
, v
);
1673 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1676 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1678 item
->index_in_class
= cls
->members
.length ();
1679 cls
->members
.safe_push (item
);
1683 /* Congruence classes are built by hash value. */
1686 sem_item_optimizer::build_hash_based_classes (void)
1688 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1690 sem_item
*item
= m_items
[i
];
1692 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1695 if (!group
->classes
.length ())
1698 group
->classes
.safe_push (new congruence_class (class_id
++));
1701 add_item_to_class (group
->classes
[0], item
);
1705 /* Build references according to call graph. */
1708 sem_item_optimizer::build_graph (void)
1710 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1712 sem_item
*item
= m_items
[i
];
1713 m_symtab_node_map
.put (item
->node
, item
);
1716 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1718 sem_item
*item
= m_items
[i
];
1720 if (item
->type
== FUNC
)
1722 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1724 cgraph_edge
*e
= cnode
->callees
;
1727 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1729 item
->add_reference (*slot
);
1735 ipa_ref
*ref
= NULL
;
1736 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1738 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1740 item
->add_reference (*slot
);
1745 /* Semantic items in classes having more than one element and initialized.
1746 In case of WPA, we load function body. */
1749 sem_item_optimizer::parse_nonsingleton_classes (void)
1751 unsigned int init_called_count
= 0;
1753 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1754 if (m_items
[i
]->cls
->members
.length () > 1)
1756 m_items
[i
]->init ();
1757 init_called_count
++;
1761 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1762 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
1765 /* Equality function for semantic items is used to subdivide existing
1766 classes. If IN_WPA, fast equality function is invoked. */
1769 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1771 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1772 it
!= m_classes
.end (); ++it
)
1774 unsigned int class_count
= (*it
)->classes
.length ();
1776 for (unsigned i
= 0; i
< class_count
; i
++)
1778 congruence_class
*c
= (*it
)->classes
[i
];
1780 if (c
->members
.length() > 1)
1782 auto_vec
<sem_item
*> new_vector
;
1784 sem_item
*first
= c
->members
[0];
1785 new_vector
.safe_push (first
);
1787 unsigned class_split_first
= (*it
)->classes
.length ();
1789 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1791 sem_item
*item
= c
->members
[j
];
1793 bool equals
= in_wpa
? first
->equals_wpa (item
,
1794 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1797 new_vector
.safe_push (item
);
1800 bool integrated
= false;
1802 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1804 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1805 bool equals
= in_wpa
? x
->equals_wpa (item
,
1806 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1811 add_item_to_class ((*it
)->classes
[k
], item
);
1819 congruence_class
*c
= new congruence_class (class_id
++);
1821 add_item_to_class (c
, item
);
1823 (*it
)->classes
.safe_push (c
);
1828 // we replace newly created new_vector for the class we've just splitted
1829 c
->members
.release ();
1830 c
->members
.create (new_vector
.length ());
1832 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1833 add_item_to_class (c
, new_vector
[j
]);
1841 /* Verify congruence classes if checking is enabled. */
1844 sem_item_optimizer::verify_classes (void)
1847 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1848 it
!= m_classes
.end (); ++it
)
1850 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1852 congruence_class
*cls
= (*it
)->classes
[i
];
1854 gcc_checking_assert (cls
);
1855 gcc_checking_assert (cls
->members
.length () > 0);
1857 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1859 sem_item
*item
= cls
->members
[j
];
1861 gcc_checking_assert (item
);
1862 gcc_checking_assert (item
->cls
== cls
);
1864 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1866 sem_usage_pair
*usage
= item
->usages
[k
];
1867 gcc_checking_assert (usage
->item
->index_in_class
<
1868 usage
->item
->cls
->members
.length ());
1876 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1877 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1878 but unused argument. */
1881 sem_item_optimizer::release_split_map (congruence_class
* const &,
1882 bitmap
const &b
, traverse_split_pair
*)
1891 /* Process split operation for a class given as pointer CLS_PTR,
1892 where bitmap B splits congruence class members. DATA is used
1893 as argument of split pair. */
1896 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
1897 bitmap
const &b
, traverse_split_pair
*pair
)
1899 sem_item_optimizer
*optimizer
= pair
->optimizer
;
1900 const congruence_class
*splitter_cls
= pair
->cls
;
1902 /* If counted bits are greater than zero and less than the number of members
1903 a group will be splitted. */
1904 unsigned popcount
= bitmap_count_bits (b
);
1906 if (popcount
> 0 && popcount
< cls
->members
.length ())
1908 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
1910 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1912 int target
= bitmap_bit_p (b
, i
);
1913 congruence_class
*tc
= newclasses
[target
];
1915 add_item_to_class (tc
, cls
->members
[i
]);
1918 #ifdef ENABLE_CHECKING
1919 for (unsigned int i
= 0; i
< 2; i
++)
1920 gcc_checking_assert (newclasses
[i
]->members
.length ());
1923 if (splitter_cls
== cls
)
1924 optimizer
->splitter_class_removed
= true;
1926 /* Remove old class from worklist if presented. */
1927 bool in_worklist
= cls
->in_worklist
;
1930 cls
->in_worklist
= false;
1932 congruence_class_group g
;
1933 g
.hash
= cls
->members
[0]->get_hash ();
1934 g
.type
= cls
->members
[0]->type
;
1936 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
1938 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
1939 if (slot
->classes
[i
] == cls
)
1941 slot
->classes
.ordered_remove (i
);
1945 /* New class will be inserted and integrated to work list. */
1946 for (unsigned int i
= 0; i
< 2; i
++)
1947 optimizer
->add_class (newclasses
[i
]);
1949 /* Two classes replace one, so that increment just by one. */
1950 optimizer
->m_classes_count
++;
1952 /* If OLD class was presented in the worklist, we remove the class
1953 and replace it will both newly created classes. */
1955 for (unsigned int i
= 0; i
< 2; i
++)
1956 optimizer
->worklist_push (newclasses
[i
]);
1957 else /* Just smaller class is inserted. */
1959 unsigned int smaller_index
= newclasses
[0]->members
.length () <
1960 newclasses
[1]->members
.length () ?
1962 optimizer
->worklist_push (newclasses
[smaller_index
]);
1965 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1967 fprintf (dump_file
, " congruence class splitted:\n");
1968 cls
->dump (dump_file
, 4);
1970 fprintf (dump_file
, " newly created groups:\n");
1971 for (unsigned int i
= 0; i
< 2; i
++)
1972 newclasses
[i
]->dump (dump_file
, 4);
1975 /* Release class if not presented in work list. */
1984 /* Tests if a class CLS used as INDEXth splits any congruence classes.
1985 Bitmap stack BMSTACK is used for bitmap allocation. */
1988 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
1991 hash_map
<congruence_class
*, bitmap
> split_map
;
1993 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1995 sem_item
*item
= cls
->members
[i
];
1997 /* Iterate all usages that have INDEX as usage of the item. */
1998 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2000 sem_usage_pair
*usage
= item
->usages
[j
];
2002 if (usage
->index
!= index
)
2005 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2010 b
= BITMAP_ALLOC (&m_bmstack
);
2011 split_map
.put (usage
->item
->cls
, b
);
2017 gcc_checking_assert (usage
->item
->cls
);
2018 gcc_checking_assert (usage
->item
->index_in_class
<
2019 usage
->item
->cls
->members
.length ());
2022 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2026 traverse_split_pair pair
;
2027 pair
.optimizer
= this;
2030 splitter_class_removed
= false;
2032 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2034 /* Bitmap clean-up. */
2036 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2039 /* Every usage of a congruence class CLS is a candidate that can split the
2040 collection of classes. Bitmap stack BMSTACK is used for bitmap
2044 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2049 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2051 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2052 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2054 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2056 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2057 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2060 do_congruence_step_for_index (cls
, i
);
2062 if (splitter_class_removed
)
2066 BITMAP_FREE (usage
);
2069 /* Adds a newly created congruence class CLS to worklist. */
2072 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2074 /* Return if the class CLS is already presented in work list. */
2075 if (cls
->in_worklist
)
2078 cls
->in_worklist
= true;
2079 worklist
.push_back (cls
);
2082 /* Pops a class from worklist. */
2085 sem_item_optimizer::worklist_pop (void)
2087 congruence_class
*cls
;
2089 while (!worklist
.empty ())
2091 cls
= worklist
.front ();
2092 worklist
.pop_front ();
2093 if (cls
->in_worklist
)
2095 cls
->in_worklist
= false;
2101 /* Work list item was already intended to be removed.
2102 The only reason for doing it is to split a class.
2103 Thus, the class CLS is deleted. */
2111 /* Iterative congruence reduction function. */
2114 sem_item_optimizer::process_cong_reduction (void)
2116 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2117 it
!= m_classes
.end (); ++it
)
2118 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2119 if ((*it
)->classes
[i
]->is_class_used ())
2120 worklist_push ((*it
)->classes
[i
]);
2123 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2124 (unsigned long) worklist
.size ());
2126 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2127 fprintf (dump_file
, "Congruence class reduction\n");
2129 congruence_class
*cls
;
2130 while ((cls
= worklist_pop ()) != NULL
)
2131 do_congruence_step (cls
);
2134 /* Debug function prints all informations about congruence classes. */
2137 sem_item_optimizer::dump_cong_classes (void)
2143 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2144 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2146 /* Histogram calculation. */
2147 unsigned int max_index
= 0;
2148 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2150 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2151 it
!= m_classes
.end (); ++it
)
2153 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2155 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2163 "Class size histogram [num of members]: number of classe number of classess\n");
2165 for (unsigned int i
= 0; i
<= max_index
; i
++)
2167 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2169 fprintf (dump_file
, "\n\n");
2172 if (dump_flags
& TDF_DETAILS
)
2173 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2174 it
!= m_classes
.end (); ++it
)
2176 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2178 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2180 (*it
)->classes
[i
]->dump (dump_file
, 4);
2182 if(i
< (*it
)->classes
.length () - 1)
2183 fprintf (dump_file
, " ");
2190 /* After reduction is done, we can declare all items in a group
2191 to be equal. PREV_CLASS_COUNT is start number of classes
2192 before reduction. */
2195 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2197 unsigned int item_count
= m_items
.length ();
2198 unsigned int class_count
= m_classes_count
;
2199 unsigned int equal_items
= item_count
- class_count
;
2201 unsigned int non_singular_classes_count
= 0;
2202 unsigned int non_singular_classes_sum
= 0;
2204 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2205 it
!= m_classes
.end (); ++it
)
2206 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2208 congruence_class
*c
= (*it
)->classes
[i
];
2209 if (c
->members
.length () > 1)
2211 non_singular_classes_count
++;
2212 non_singular_classes_sum
+= c
->members
.length ();
2218 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2219 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2220 prev_class_count
, class_count
);
2221 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2222 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2223 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2224 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2225 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2226 non_singular_classes_count
: 0.0f
,
2227 non_singular_classes_count
);
2228 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2229 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2230 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2233 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2234 it
!= m_classes
.end (); ++it
)
2235 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2237 congruence_class
*c
= (*it
)->classes
[i
];
2239 if (c
->members
.length () == 1)
2242 gcc_assert (c
->members
.length ());
2244 sem_item
*source
= c
->members
[0];
2246 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2248 sem_item
*alias
= c
->members
[j
];
2249 source
->equals (alias
, m_symtab_node_map
);
2253 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2254 source
->name (), alias
->name ());
2255 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2256 source
->asm_name (), alias
->asm_name ());
2259 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2261 source
->dump_to_file (dump_file
);
2262 alias
->dump_to_file (dump_file
);
2265 source
->merge (alias
);
2270 /* Dump function prints all class members to a FILE with an INDENT. */
2273 congruence_class::dump (FILE *file
, unsigned int indent
) const
2275 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2276 id
, members
[0]->get_hash (), members
.length ());
2278 FPUTS_SPACES (file
, indent
+ 2, "");
2279 for (unsigned i
= 0; i
< members
.length (); i
++)
2280 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2281 members
[i
]->node
->order
);
2283 fprintf (file
, "\n");
2286 /* Returns true if there's a member that is used from another group. */
2289 congruence_class::is_class_used (void)
2291 for (unsigned int i
= 0; i
< members
.length (); i
++)
2292 if (members
[i
]->usages
.length ())
2298 /* Initialization and computation of symtab node hash, there data
2299 are propagated later on. */
2301 static sem_item_optimizer
*optimizer
= NULL
;
2303 /* Generate pass summary for IPA ICF pass. */
2306 ipa_icf_generate_summary (void)
2309 optimizer
= new sem_item_optimizer ();
2311 optimizer
->parse_funcs_and_vars ();
2314 /* Write pass summary for IPA ICF pass. */
2317 ipa_icf_write_summary (void)
2319 gcc_assert (optimizer
);
2321 optimizer
->write_summary ();
2324 /* Read pass summary for IPA ICF pass. */
2327 ipa_icf_read_summary (void)
2330 optimizer
= new sem_item_optimizer ();
2332 optimizer
->read_summary ();
2333 optimizer
->register_hooks ();
2336 /* Semantic equality exection function. */
2339 ipa_icf_driver (void)
2341 gcc_assert (optimizer
);
2343 optimizer
->execute ();
2344 optimizer
->unregister_hooks ();
2352 const pass_data pass_data_ipa_icf
=
2354 IPA_PASS
, /* type */
2356 OPTGROUP_IPA
, /* optinfo_flags */
2357 TV_IPA_ICF
, /* tv_id */
2358 0, /* properties_required */
2359 0, /* properties_provided */
2360 0, /* properties_destroyed */
2361 0, /* todo_flags_start */
2362 0, /* todo_flags_finish */
2365 class pass_ipa_icf
: public ipa_opt_pass_d
2368 pass_ipa_icf (gcc::context
*ctxt
)
2369 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2370 ipa_icf_generate_summary
, /* generate_summary */
2371 ipa_icf_write_summary
, /* write_summary */
2372 ipa_icf_read_summary
, /* read_summary */
2374 write_optimization_summary */
2376 read_optimization_summary */
2377 NULL
, /* stmt_fixup */
2378 0, /* function_transform_todo_flags_start */
2379 NULL
, /* function_transform */
2380 NULL
) /* variable_transform */
2383 /* opt_pass methods: */
2384 virtual bool gate (function
*)
2386 return flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2389 virtual unsigned int execute (function
*)
2391 return ipa_icf_driver();
2393 }; // class pass_ipa_icf
2395 } // ipa_icf namespace
2398 make_pass_ipa_icf (gcc::context
*ctxt
)
2400 return new ipa_icf::pass_ipa_icf (ctxt
);