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"
58 #include "basic-block.h"
59 #include "tree-ssa-alias.h"
60 #include "internal-fn.h"
61 #include "gimple-expr.h"
65 #include "gimple-iterator.h"
66 #include "gimple-ssa.h"
68 #include "tree-phinodes.h"
69 #include "stringpool.h"
70 #include "tree-ssanames.h"
72 #include "tree-pass.h"
73 #include "gimple-pretty-print.h"
74 #include "ipa-inline.h"
77 #include "hash-table.h"
80 #include "print-tree.h"
81 #include "lto-streamer.h"
82 #include "data-streamer.h"
83 #include "ipa-utils.h"
85 #include "ipa-icf-gimple.h"
88 using namespace ipa_icf_gimple
;
91 /* Constructor for key value pair, where _ITEM is key and _INDEX is a target. */
93 sem_usage_pair::sem_usage_pair (sem_item
*_item
, unsigned int _index
):
94 item (_item
), index (_index
)
98 /* Semantic item constructor for a node of _TYPE, where STACK is used
99 for bitmap memory allocation. */
101 sem_item::sem_item (sem_item_type _type
,
102 bitmap_obstack
*stack
): type(_type
), hash(0)
107 /* Semantic item constructor for a node of _TYPE, where STACK is used
108 for bitmap memory allocation. The item is based on symtab node _NODE
109 with computed _HASH. */
111 sem_item::sem_item (sem_item_type _type
, symtab_node
*_node
,
112 hashval_t _hash
, bitmap_obstack
*stack
): type(_type
),
113 node (_node
), hash (_hash
)
119 /* Add reference to a semantic TARGET. */
122 sem_item::add_reference (sem_item
*target
)
124 refs
.safe_push (target
);
125 unsigned index
= refs
.length ();
126 target
->usages
.safe_push (new sem_usage_pair(this, index
));
127 bitmap_set_bit (target
->usage_index_bitmap
, index
);
128 refs_set
.add (target
->node
);
131 /* Initialize internal data structures. Bitmap STACK is used for
132 bitmap memory allocation process. */
135 sem_item::setup (bitmap_obstack
*stack
)
137 gcc_checking_assert (node
);
140 tree_refs
.create (0);
142 usage_index_bitmap
= BITMAP_ALLOC (stack
);
145 sem_item::~sem_item ()
147 for (unsigned i
= 0; i
< usages
.length (); i
++)
151 tree_refs
.release ();
154 BITMAP_FREE (usage_index_bitmap
);
157 /* Dump function for debugging purpose. */
160 sem_item::dump (void)
164 fprintf (dump_file
, "[%s] %s (%u) (tree:%p)\n", type
== FUNC
? "func" : "var",
165 name(), node
->order
, (void *) node
->decl
);
166 fprintf (dump_file
, " hash: %u\n", get_hash ());
167 fprintf (dump_file
, " references: ");
169 for (unsigned i
= 0; i
< refs
.length (); i
++)
170 fprintf (dump_file
, "%s%s ", refs
[i
]->name (),
171 i
< refs
.length() - 1 ? "," : "");
173 fprintf (dump_file
, "\n");
177 /* Semantic function constructor that uses STACK as bitmap memory stack. */
179 sem_function::sem_function (bitmap_obstack
*stack
): sem_item (FUNC
, stack
),
180 m_checker (NULL
), m_compared_func (NULL
)
182 arg_types
.create (0);
184 bb_sorted
.create (0);
187 /* Constructor based on callgraph node _NODE with computed hash _HASH.
188 Bitmap STACK is used for memory allocation. */
189 sem_function::sem_function (cgraph_node
*node
, hashval_t hash
,
190 bitmap_obstack
*stack
):
191 sem_item (FUNC
, node
, hash
, stack
),
192 m_checker (NULL
), m_compared_func (NULL
)
194 arg_types
.create (0);
196 bb_sorted
.create (0);
199 sem_function::~sem_function ()
201 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
204 arg_types
.release ();
206 bb_sorted
.release ();
209 /* Calculates hash value based on a BASIC_BLOCK. */
212 sem_function::get_bb_hash (const sem_bb
*basic_block
)
214 inchash::hash hstate
;
216 hstate
.add_int (basic_block
->nondbg_stmt_count
);
217 hstate
.add_int (basic_block
->edge_count
);
219 return hstate
.end ();
222 /* References independent hash function. */
225 sem_function::get_hash (void)
229 inchash::hash hstate
;
230 hstate
.add_int (177454); /* Random number for function type. */
232 hstate
.add_int (arg_count
);
233 hstate
.add_int (cfg_checksum
);
234 hstate
.add_int (gcode_hash
);
236 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
237 hstate
.merge_hash (get_bb_hash (bb_sorted
[i
]));
239 for (unsigned i
= 0; i
< bb_sizes
.length (); i
++)
240 hstate
.add_int (bb_sizes
[i
]);
242 hash
= hstate
.end ();
248 /* For a given symbol table nodes N1 and N2, we check that FUNCTION_DECLs
249 point to a same function. Comparison can be skipped if IGNORED_NODES
250 contains these nodes. */
253 sem_function::compare_cgraph_references (hash_map
<symtab_node
*, sem_item
*>
255 symtab_node
*n1
, symtab_node
*n2
)
257 if (n1
== n2
|| (ignored_nodes
.get (n1
) && ignored_nodes
.get (n2
)))
260 /* TODO: add more precise comparison for weakrefs, etc. */
262 return return_false_with_msg ("different references");
265 /* If cgraph edges E1 and E2 are indirect calls, verify that
266 ECF flags are the same. */
268 bool sem_function::compare_edge_flags (cgraph_edge
*e1
, cgraph_edge
*e2
)
270 if (e1
->indirect_info
&& e2
->indirect_info
)
272 int e1_flags
= e1
->indirect_info
->ecf_flags
;
273 int e2_flags
= e2
->indirect_info
->ecf_flags
;
275 if (e1_flags
!= e2_flags
)
276 return return_false_with_msg ("ICF flags are different");
278 else if (e1
->indirect_info
|| e2
->indirect_info
)
284 /* Fast equality function based on knowledge known in WPA. */
287 sem_function::equals_wpa (sem_item
*item
,
288 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
290 gcc_assert (item
->type
== FUNC
);
292 m_compared_func
= static_cast<sem_function
*> (item
);
294 if (arg_types
.length () != m_compared_func
->arg_types
.length ())
295 return return_false_with_msg ("different number of arguments");
297 /* Checking types of arguments. */
298 for (unsigned i
= 0; i
< arg_types
.length (); i
++)
300 /* This guard is here for function pointer with attributes (pr59927.c). */
301 if (!arg_types
[i
] || !m_compared_func
->arg_types
[i
])
302 return return_false_with_msg ("NULL argument type");
304 /* Polymorphic comparison is executed just for non-leaf functions. */
305 bool is_not_leaf
= get_node ()->callees
!= NULL
;
307 if (!func_checker::compatible_types_p (arg_types
[i
],
308 m_compared_func
->arg_types
[i
],
309 is_not_leaf
, i
== 0))
310 return return_false_with_msg ("argument type is different");
313 /* Result type checking. */
314 if (!func_checker::compatible_types_p (result_type
,
315 m_compared_func
->result_type
))
316 return return_false_with_msg ("result types are different");
318 if (node
->num_references () != item
->node
->num_references ())
319 return return_false_with_msg ("different number of references");
321 ipa_ref
*ref
= NULL
, *ref2
= NULL
;
322 for (unsigned i
= 0; node
->iterate_reference (i
, ref
); i
++)
324 item
->node
->iterate_reference (i
, ref2
);
326 if (!compare_cgraph_references (ignored_nodes
, ref
->referred
, ref2
->referred
))
330 cgraph_edge
*e1
= dyn_cast
<cgraph_node
*> (node
)->callees
;
331 cgraph_edge
*e2
= dyn_cast
<cgraph_node
*> (item
->node
)->callees
;
335 if (!compare_cgraph_references (ignored_nodes
, e1
->callee
, e2
->callee
))
338 e1
= e1
->next_callee
;
339 e2
= e2
->next_callee
;
343 return return_false_with_msg ("different number of edges");
348 /* Returns true if the item equals to ITEM given as argument. */
351 sem_function::equals (sem_item
*item
,
352 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
354 gcc_assert (item
->type
== FUNC
);
355 bool eq
= equals_private (item
, ignored_nodes
);
357 if (m_checker
!= NULL
)
363 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
365 "Equals called for:%s:%s (%u:%u) (%s:%s) with result: %s\n\n",
366 name(), item
->name (), node
->order
, item
->node
->order
, asm_name (),
367 item
->asm_name (), eq
? "true" : "false");
372 /* Processes function equality comparison. */
375 sem_function::equals_private (sem_item
*item
,
376 hash_map
<symtab_node
*, sem_item
*> &ignored_nodes
)
378 if (item
->type
!= FUNC
)
381 basic_block bb1
, bb2
;
383 edge_iterator ei1
, ei2
;
388 m_compared_func
= static_cast<sem_function
*> (item
);
390 gcc_assert (decl
!= item
->decl
);
392 if (bb_sorted
.length () != m_compared_func
->bb_sorted
.length ()
393 || edge_count
!= m_compared_func
->edge_count
394 || cfg_checksum
!= m_compared_func
->cfg_checksum
)
395 return return_false ();
397 if (!equals_wpa (item
, ignored_nodes
))
400 /* Checking function arguments. */
401 tree decl1
= DECL_ATTRIBUTES (decl
);
402 tree decl2
= DECL_ATTRIBUTES (m_compared_func
->decl
);
404 m_checker
= new func_checker (decl
, m_compared_func
->decl
,
405 compare_polymorphic_p (),
408 &m_compared_func
->refs_set
);
412 return return_false ();
414 if (get_attribute_name (decl1
) != get_attribute_name (decl2
))
415 return return_false ();
417 tree attr_value1
= TREE_VALUE (decl1
);
418 tree attr_value2
= TREE_VALUE (decl2
);
420 if (attr_value1
&& attr_value2
)
422 bool ret
= m_checker
->compare_operand (TREE_VALUE (attr_value1
),
423 TREE_VALUE (attr_value2
));
425 return return_false_with_msg ("attribute values are different");
427 else if (!attr_value1
&& !attr_value2
)
430 return return_false ();
432 decl1
= TREE_CHAIN (decl1
);
433 decl2
= TREE_CHAIN (decl2
);
437 return return_false();
440 for (arg1
= DECL_ARGUMENTS (decl
),
441 arg2
= DECL_ARGUMENTS (m_compared_func
->decl
);
442 arg1
; arg1
= DECL_CHAIN (arg1
), arg2
= DECL_CHAIN (arg2
))
443 if (!m_checker
->compare_decl (arg1
, arg2
))
444 return return_false ();
446 /* Fill-up label dictionary. */
447 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
449 m_checker
->parse_labels (bb_sorted
[i
]);
450 m_checker
->parse_labels (m_compared_func
->bb_sorted
[i
]);
453 /* Checking all basic blocks. */
454 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
455 if(!m_checker
->compare_bb (bb_sorted
[i
], m_compared_func
->bb_sorted
[i
]))
456 return return_false();
458 dump_message ("All BBs are equal\n");
460 /* Basic block edges check. */
461 for (unsigned i
= 0; i
< bb_sorted
.length (); ++i
)
463 bb_dict
= XNEWVEC (int, bb_sorted
.length () + 2);
464 memset (bb_dict
, -1, (bb_sorted
.length () + 2) * sizeof (int));
466 bb1
= bb_sorted
[i
]->bb
;
467 bb2
= m_compared_func
->bb_sorted
[i
]->bb
;
469 ei2
= ei_start (bb2
->preds
);
471 for (ei1
= ei_start (bb1
->preds
); ei_cond (ei1
, &e1
); ei_next (&ei1
))
475 if (e1
->flags
!= e2
->flags
)
476 return return_false_with_msg ("flags comparison returns false");
478 if (!bb_dict_test (bb_dict
, e1
->src
->index
, e2
->src
->index
))
479 return return_false_with_msg ("edge comparison returns false");
481 if (!bb_dict_test (bb_dict
, e1
->dest
->index
, e2
->dest
->index
))
482 return return_false_with_msg ("BB comparison returns false");
484 if (!m_checker
->compare_edge (e1
, e2
))
485 return return_false_with_msg ("edge comparison returns false");
491 /* Basic block PHI nodes comparison. */
492 for (unsigned i
= 0; i
< bb_sorted
.length (); i
++)
493 if (!compare_phi_node (bb_sorted
[i
]->bb
, m_compared_func
->bb_sorted
[i
]->bb
))
494 return return_false_with_msg ("PHI node comparison returns false");
499 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
502 sem_function::merge (sem_item
*alias_item
)
504 gcc_assert (alias_item
->type
== FUNC
);
506 sem_function
*alias_func
= static_cast<sem_function
*> (alias_item
);
508 cgraph_node
*original
= get_node ();
509 cgraph_node
*local_original
= original
;
510 cgraph_node
*alias
= alias_func
->get_node ();
511 bool original_address_matters
;
512 bool alias_address_matters
;
514 bool create_thunk
= false;
515 bool create_alias
= false;
516 bool redirect_callers
= false;
517 bool original_discardable
= false;
519 /* Do not attempt to mix functions from different user sections;
520 we do not know what user intends with those. */
521 if (((DECL_SECTION_NAME (original
->decl
) && !original
->implicit_section
)
522 || (DECL_SECTION_NAME (alias
->decl
) && !alias
->implicit_section
))
523 && DECL_SECTION_NAME (original
->decl
) != DECL_SECTION_NAME (alias
->decl
))
527 "Not unifying; original and alias are in different sections.\n\n");
531 /* See if original is in a section that can be discarded if the main
532 symbol is not used. */
533 if (DECL_EXTERNAL (original
->decl
))
534 original_discardable
= true;
535 if (original
->resolution
== LDPR_PREEMPTED_REG
536 || original
->resolution
== LDPR_PREEMPTED_IR
)
537 original_discardable
= true;
538 if (original
->can_be_discarded_p ())
539 original_discardable
= true;
541 /* See if original and/or alias address can be compared for equality. */
542 original_address_matters
543 = (!DECL_VIRTUAL_P (original
->decl
)
544 && (original
->externally_visible
545 || original
->address_taken_from_non_vtable_p ()));
546 alias_address_matters
547 = (!DECL_VIRTUAL_P (alias
->decl
)
548 && (alias
->externally_visible
549 || alias
->address_taken_from_non_vtable_p ()));
551 /* If alias and original can be compared for address equality, we need
552 to create a thunk. Also we can not create extra aliases into discardable
553 section (or we risk link failures when section is discarded). */
554 if ((original_address_matters
555 && alias_address_matters
)
556 || original_discardable
)
558 create_thunk
= !stdarg_p (TREE_TYPE (alias
->decl
));
559 create_alias
= false;
560 /* When both alias and original are not overwritable, we can save
561 the extra thunk wrapper for direct calls. */
563 = (!original_discardable
564 && alias
->get_availability () > AVAIL_INTERPOSABLE
565 && original
->get_availability () > AVAIL_INTERPOSABLE
);
570 create_thunk
= false;
571 redirect_callers
= false;
574 if (create_alias
&& DECL_COMDAT_GROUP (alias
->decl
))
576 create_alias
= false;
580 /* We want thunk to always jump to the local function body
581 unless the body is comdat and may be optimized out. */
582 if ((create_thunk
|| redirect_callers
)
583 && (!original_discardable
584 || (DECL_COMDAT_GROUP (original
->decl
)
585 && (DECL_COMDAT_GROUP (original
->decl
)
586 == DECL_COMDAT_GROUP (alias
->decl
)))))
588 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
590 if (redirect_callers
)
592 /* If alias is non-overwritable then
593 all direct calls are safe to be redirected to the original. */
594 bool redirected
= false;
595 while (alias
->callers
)
597 cgraph_edge
*e
= alias
->callers
;
598 e
->redirect_callee (local_original
);
599 push_cfun (DECL_STRUCT_FUNCTION (e
->caller
->decl
));
602 e
->redirect_call_stmt_to_callee ();
608 alias
->icf_merged
= true;
610 /* The alias function is removed if symbol address
612 if (!alias_address_matters
)
615 if (dump_file
&& redirected
)
616 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
618 /* If the condtion above is not met, we are lucky and can turn the
619 function into real alias. */
620 else if (create_alias
)
622 alias
->icf_merged
= true;
624 /* Remove the function's body. */
625 ipa_merge_profiles (original
, alias
);
626 alias
->release_body (true);
629 /* Create the alias. */
630 cgraph_node::create_alias (alias_func
->decl
, decl
);
631 alias
->resolve_alias (original
);
633 /* Workaround for PR63566 that forces equal calling convention
635 alias
->local
.local
= false;
636 original
->local
.local
= false;
639 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
641 else if (create_thunk
)
643 if (DECL_COMDAT_GROUP (alias
->decl
))
646 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
651 alias
->icf_merged
= true;
652 ipa_merge_profiles (local_original
, alias
);
653 alias
->create_wrapper (local_original
);
656 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
659 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
664 /* Semantic item initialization function. */
667 sem_function::init (void)
670 get_node ()->get_body ();
672 tree fndecl
= node
->decl
;
673 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
676 gcc_assert (SSANAMES (func
));
678 ssa_names_size
= SSANAMES (func
)->length ();
682 region_tree
= func
->eh
->region_tree
;
684 /* iterating all function arguments. */
685 arg_count
= count_formal_params (fndecl
);
687 edge_count
= n_edges_for_fn (func
);
688 cfg_checksum
= coverage_compute_cfg_checksum (func
);
690 inchash::hash hstate
;
693 FOR_EACH_BB_FN (bb
, func
)
695 unsigned nondbg_stmt_count
= 0;
698 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
699 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
702 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
705 gimple stmt
= gsi_stmt (gsi
);
707 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
709 hash_stmt (&hstate
, stmt
);
714 gcode_hash
= hstate
.end ();
715 bb_sizes
.safe_push (nondbg_stmt_count
);
717 /* Inserting basic block to hash table. */
718 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
719 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
721 bb_sorted
.safe_push (semantic_bb
);
727 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
730 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
732 enum gimple_code code
= gimple_code (stmt
);
734 hstate
->add_int (code
);
736 if (code
== GIMPLE_CALL
)
738 /* Checking of argument. */
739 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
741 tree argument
= gimple_call_arg (stmt
, i
);
743 switch (TREE_CODE (argument
))
746 if (tree_fits_shwi_p (argument
))
747 hstate
->add_wide_int (tree_to_shwi (argument
));
748 else if (tree_fits_uhwi_p (argument
))
749 hstate
->add_wide_int (tree_to_uhwi (argument
));
755 c
= TREE_REAL_CST (argument
);
756 n
= real_to_integer (&c
);
758 hstate
->add_wide_int (n
);
762 tree addr_operand
= TREE_OPERAND (argument
, 0);
764 if (TREE_CODE (addr_operand
) == STRING_CST
)
765 hstate
->add (TREE_STRING_POINTER (addr_operand
),
766 TREE_STRING_LENGTH (addr_operand
));
777 /* Return true if polymorphic comparison must be processed. */
780 sem_function::compare_polymorphic_p (void)
782 return get_node ()->callees
!= NULL
783 || m_compared_func
->get_node ()->callees
!= NULL
;
786 /* For a given call graph NODE, the function constructs new
787 semantic function item. */
790 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
792 tree fndecl
= node
->decl
;
793 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
795 /* TODO: add support for thunks and aliases. */
797 if (!func
|| !node
->has_gimple_body_p ())
800 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
803 sem_function
*f
= new sem_function (node
, 0, stack
);
810 /* Parses function arguments and result type. */
813 sem_function::parse_tree_args (void)
817 if (arg_types
.exists ())
818 arg_types
.release ();
820 arg_types
.create (4);
821 tree fnargs
= DECL_ARGUMENTS (decl
);
823 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
824 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
826 /* Function result type. */
827 result
= DECL_RESULT (decl
);
828 result_type
= result
? TREE_TYPE (result
) : NULL
;
830 /* During WPA, we can get arguments by following method. */
833 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
834 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
835 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
837 result_type
= TREE_TYPE (TREE_TYPE (decl
));
841 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
842 return true if phi nodes are semantically equivalent in these blocks . */
845 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
847 gimple_stmt_iterator si1
, si2
;
849 unsigned size1
, size2
, i
;
853 gcc_assert (bb1
!= NULL
);
854 gcc_assert (bb2
!= NULL
);
856 si2
= gsi_start_phis (bb2
);
857 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
860 gsi_next_nonvirtual_phi (&si1
);
861 gsi_next_nonvirtual_phi (&si2
);
863 if (gsi_end_p (si1
) && gsi_end_p (si2
))
866 if (gsi_end_p (si1
) || gsi_end_p (si2
))
867 return return_false();
869 phi1
= gsi_stmt (si1
);
870 phi2
= gsi_stmt (si2
);
872 size1
= gimple_phi_num_args (phi1
);
873 size2
= gimple_phi_num_args (phi2
);
876 return return_false ();
878 for (i
= 0; i
< size1
; ++i
)
880 t1
= gimple_phi_arg (phi1
, i
)->def
;
881 t2
= gimple_phi_arg (phi2
, i
)->def
;
883 if (!m_checker
->compare_operand (t1
, t2
))
884 return return_false ();
886 e1
= gimple_phi_arg_edge (phi1
, i
);
887 e2
= gimple_phi_arg_edge (phi2
, i
);
889 if (!m_checker
->compare_edge (e1
, e2
))
890 return return_false ();
899 /* Returns true if tree T can be compared as a handled component. */
902 sem_function::icf_handled_component_p (tree t
)
904 tree_code tc
= TREE_CODE (t
);
906 return ((handled_component_p (t
))
907 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
908 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
911 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
912 corresponds to TARGET. */
915 sem_function::bb_dict_test (int* bb_dict
, int source
, int target
)
917 if (bb_dict
[source
] == -1)
919 bb_dict
[source
] = target
;
923 return bb_dict
[source
] == target
;
926 /* Iterates all tree types in T1 and T2 and returns true if all types
927 are compatible. If COMPARE_POLYMORPHIC is set to true,
928 more strict comparison is executed. */
931 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
939 while (t1
!= NULL
&& t2
!= NULL
)
941 tv1
= TREE_VALUE (t1
);
942 tv2
= TREE_VALUE (t2
);
944 tc1
= TREE_CODE (tv1
);
945 tc2
= TREE_CODE (tv2
);
947 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
949 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
951 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
954 t1
= TREE_CHAIN (t1
);
955 t2
= TREE_CHAIN (t2
);
962 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
964 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
968 /* Constructor based on varpool node _NODE with computed hash _HASH.
969 Bitmap STACK is used for memory allocation. */
971 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
972 bitmap_obstack
*stack
): sem_item(VAR
,
975 gcc_checking_assert (node
);
976 gcc_checking_assert (get_node ());
979 /* Returns true if the item equals to ITEM given as argument. */
982 sem_variable::equals (sem_item
*item
,
983 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
985 gcc_assert (item
->type
== VAR
);
987 sem_variable
*v
= static_cast<sem_variable
*>(item
);
989 if (!ctor
|| !v
->ctor
)
990 return return_false_with_msg ("ctor is missing for semantic variable");
992 return sem_variable::equals (ctor
, v
->ctor
);
995 /* Compares trees T1 and T2 for semantic equality. */
998 sem_variable::equals (tree t1
, tree t2
)
1000 tree_code tc1
= TREE_CODE (t1
);
1001 tree_code tc2
= TREE_CODE (t2
);
1010 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1011 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1016 for (unsigned i
= 0; i
< len1
; i
++)
1017 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1018 CONSTRUCTOR_ELT (t2
, i
)->value
)
1019 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1026 tree x1
= TREE_OPERAND (t1
, 0);
1027 tree x2
= TREE_OPERAND (t2
, 0);
1028 tree y1
= TREE_OPERAND (t1
, 1);
1029 tree y2
= TREE_OPERAND (t2
, 1);
1031 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1033 return return_false ();
1035 /* Type of the offset on MEM_REF does not matter. */
1036 return sem_variable::equals (x1
, x2
)
1037 && wi::to_offset (y1
) == wi::to_offset (y2
);
1042 tree op1
= TREE_OPERAND (t1
, 0);
1043 tree op2
= TREE_OPERAND (t2
, 0);
1044 return sem_variable::equals (op1
, op2
);
1052 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1054 && wi::to_offset (t1
) == wi::to_offset (t2
);
1058 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1061 case POINTER_PLUS_EXPR
:
1063 tree x1
= TREE_OPERAND (t1
, 0);
1064 tree x2
= TREE_OPERAND (t2
, 0);
1065 tree y1
= TREE_OPERAND (t1
, 1);
1066 tree y2
= TREE_OPERAND (t2
, 1);
1068 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1071 return return_false_with_msg ("ERROR_MARK");
1073 return return_false_with_msg ("Unknown TREE code reached");
1077 /* Parser function that visits a varpool NODE. */
1080 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1082 tree decl
= node
->decl
;
1084 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1085 bool can_handle
= readonly
&& (DECL_VIRTUAL_P (decl
)
1086 || !TREE_ADDRESSABLE (decl
));
1091 tree ctor
= ctor_for_folding (decl
);
1095 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1102 /* References independent hash function. */
1105 sem_variable::get_hash (void)
1110 inchash::hash hstate
;
1112 hstate
.add_int (456346417);
1113 hstate
.add_int (TREE_CODE (ctor
));
1115 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1117 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1118 hstate
.add_int (length
);
1121 hash
= hstate
.end ();
1126 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1130 sem_variable::merge (sem_item
*alias_item
)
1132 gcc_assert (alias_item
->type
== VAR
);
1134 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1136 varpool_node
*original
= get_node ();
1137 varpool_node
*alias
= alias_var
->get_node ();
1138 bool original_discardable
= false;
1140 /* See if original is in a section that can be discarded if the main
1141 symbol is not used. */
1142 if (DECL_EXTERNAL (original
->decl
))
1143 original_discardable
= true;
1144 if (original
->resolution
== LDPR_PREEMPTED_REG
1145 || original
->resolution
== LDPR_PREEMPTED_IR
)
1146 original_discardable
= true;
1147 if (original
->can_be_discarded_p ())
1148 original_discardable
= true;
1150 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1152 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1153 !compare_sections (alias_var
))
1156 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1162 // alias cycle creation check
1163 varpool_node
*n
= original
;
1167 n
= n
->get_alias_target ();
1171 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1177 alias
->analyzed
= false;
1179 DECL_INITIAL (alias
->decl
) = NULL
;
1180 alias
->remove_all_references ();
1182 varpool_node::create_alias (alias_var
->decl
, decl
);
1183 alias
->resolve_alias (original
);
1186 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1193 sem_variable::compare_sections (sem_variable
*alias
)
1195 const char *source
= node
->get_section ();
1196 const char *target
= alias
->node
->get_section();
1198 if (source
== NULL
&& target
== NULL
)
1200 else if(!source
|| !target
)
1203 return strcmp (source
, target
) == 0;
1206 /* Dump symbol to FILE. */
1209 sem_variable::dump_to_file (FILE *file
)
1213 print_node (file
, "", decl
, 0);
1214 fprintf (file
, "\n\n");
1217 /* Iterates though a constructor and identifies tree references
1218 we are interested in semantic function equality. */
1221 sem_variable::parse_tree_refs (tree t
)
1223 switch (TREE_CODE (t
))
1227 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1229 for (unsigned i
= 0; i
< length
; i
++)
1230 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1237 tree op
= TREE_OPERAND (t
, 0);
1238 parse_tree_refs (op
);
1243 tree_refs
.safe_push (t
);
1251 unsigned int sem_item_optimizer::class_id
= 0;
1253 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1254 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1257 bitmap_obstack_initialize (&m_bmstack
);
1260 sem_item_optimizer::~sem_item_optimizer ()
1262 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1265 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1266 it
!= m_classes
.end (); ++it
)
1268 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1269 delete (*it
)->classes
[i
];
1271 (*it
)->classes
.release ();
1276 bitmap_obstack_release (&m_bmstack
);
1279 /* Write IPA ICF summary for symbols. */
1282 sem_item_optimizer::write_summary (void)
1284 unsigned int count
= 0;
1286 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1287 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1290 /* Calculate number of symbols to be serialized. */
1291 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1293 lsei_next_in_partition (&lsei
))
1295 symtab_node
*node
= lsei_node (lsei
);
1297 if (m_symtab_node_map
.get (node
))
1301 streamer_write_uhwi (ob
, count
);
1303 /* Process all of the symbols. */
1304 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1306 lsei_next_in_partition (&lsei
))
1308 symtab_node
*node
= lsei_node (lsei
);
1310 sem_item
**item
= m_symtab_node_map
.get (node
);
1314 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1315 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1317 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1321 streamer_write_char_stream (ob
->main_stream
, 0);
1322 produce_asm (ob
, NULL
);
1323 destroy_output_block (ob
);
1326 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1327 contains LEN bytes. */
1330 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1331 const char *data
, size_t len
)
1333 const lto_function_header
*header
=
1334 (const lto_function_header
*) data
;
1335 const int cfg_offset
= sizeof (lto_function_header
);
1336 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1337 const int string_offset
= main_offset
+ header
->main_size
;
1342 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1346 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1347 header
->string_size
, vNULL
);
1349 count
= streamer_read_uhwi (&ib_main
);
1351 for (i
= 0; i
< count
; i
++)
1355 lto_symtab_encoder_t encoder
;
1357 index
= streamer_read_uhwi (&ib_main
);
1358 encoder
= file_data
->symtab_node_encoder
;
1359 node
= lto_symtab_encoder_deref (encoder
, index
);
1361 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1363 gcc_assert (node
->definition
);
1366 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1367 (void *) node
->decl
, node
->order
);
1369 if (is_a
<cgraph_node
*> (node
))
1371 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1373 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1377 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1379 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1383 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1385 lto_data_in_delete (data_in
);
1388 /* Read IPA IPA ICF summary for symbols. */
1391 sem_item_optimizer::read_summary (void)
1393 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1394 lto_file_decl_data
*file_data
;
1397 while ((file_data
= file_data_vec
[j
++]))
1400 const char *data
= lto_get_section_data (file_data
,
1401 LTO_section_ipa_icf
, NULL
, &len
);
1404 read_section (file_data
, data
, len
);
1408 /* Register callgraph and varpool hooks. */
1411 sem_item_optimizer::register_hooks (void)
1413 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1414 (&sem_item_optimizer::cgraph_removal_hook
, this);
1416 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1417 (&sem_item_optimizer::varpool_removal_hook
, this);
1420 /* Unregister callgraph and varpool hooks. */
1423 sem_item_optimizer::unregister_hooks (void)
1425 if (m_cgraph_node_hooks
)
1426 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1428 if (m_varpool_node_hooks
)
1429 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1432 /* Adds a CLS to hashtable associated by hash value. */
1435 sem_item_optimizer::add_class (congruence_class
*cls
)
1437 gcc_assert (cls
->members
.length ());
1439 congruence_class_group
*group
= get_group_by_hash (
1440 cls
->members
[0]->get_hash (),
1441 cls
->members
[0]->type
);
1442 group
->classes
.safe_push (cls
);
1445 /* Gets a congruence class group based on given HASH value and TYPE. */
1447 congruence_class_group
*
1448 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1450 congruence_class_group
*item
= XNEW (congruence_class_group
);
1454 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1460 item
->classes
.create (1);
1467 /* Callgraph removal hook called for a NODE with a custom DATA. */
1470 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1472 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1473 optimizer
->remove_symtab_node (node
);
1476 /* Varpool removal hook called for a NODE with a custom DATA. */
1479 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1481 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1482 optimizer
->remove_symtab_node (node
);
1485 /* Remove symtab NODE triggered by symtab removal hooks. */
1488 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1490 gcc_assert (!m_classes
.elements());
1492 m_removed_items_set
.add (node
);
1496 sem_item_optimizer::remove_item (sem_item
*item
)
1498 if (m_symtab_node_map
.get (item
->node
))
1499 m_symtab_node_map
.remove (item
->node
);
1503 /* Removes all callgraph and varpool nodes that are marked by symtab
1507 sem_item_optimizer::filter_removed_items (void)
1509 auto_vec
<sem_item
*> filtered
;
1511 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1513 sem_item
*item
= m_items
[i
];
1515 if (!flag_ipa_icf_functions
&& item
->type
== FUNC
)
1521 if (!flag_ipa_icf_variables
&& item
->type
== VAR
)
1527 bool no_body_function
= false;
1529 if (item
->type
== FUNC
)
1531 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1533 no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1536 if(!m_removed_items_set
.contains (m_items
[i
]->node
)
1537 && !no_body_function
)
1539 if (item
->type
== VAR
|| (!DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1540 && !DECL_CXX_DESTRUCTOR_P (item
->decl
)))
1542 filtered
.safe_push (m_items
[i
]);
1550 /* Clean-up of released semantic items. */
1553 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1554 m_items
.safe_push (filtered
[i
]);
1557 /* Optimizer entry point. */
1560 sem_item_optimizer::execute (void)
1562 filter_removed_items ();
1563 build_hash_based_classes ();
1566 fprintf (dump_file
, "Dump after hash based groups\n");
1567 dump_cong_classes ();
1569 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1570 m_items
[i
]->init_wpa ();
1574 subdivide_classes_by_equality (true);
1577 fprintf (dump_file
, "Dump after WPA based types groups\n");
1579 dump_cong_classes ();
1581 process_cong_reduction ();
1585 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1587 dump_cong_classes ();
1589 parse_nonsingleton_classes ();
1590 subdivide_classes_by_equality ();
1593 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1595 dump_cong_classes ();
1597 unsigned int prev_class_count
= m_classes_count
;
1599 process_cong_reduction ();
1600 dump_cong_classes ();
1602 merge_classes (prev_class_count
);
1604 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1605 symtab_node::dump_table (dump_file
);
1608 /* Function responsible for visiting all potential functions and
1609 read-only variables that can be merged. */
1612 sem_item_optimizer::parse_funcs_and_vars (void)
1616 if (flag_ipa_icf_functions
)
1617 FOR_EACH_DEFINED_FUNCTION (cnode
)
1619 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1622 m_items
.safe_push (f
);
1623 m_symtab_node_map
.put (cnode
, f
);
1626 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1628 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1629 f
->dump_to_file (dump_file
);
1632 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1635 varpool_node
*vnode
;
1637 if (flag_ipa_icf_variables
)
1638 FOR_EACH_DEFINED_VARIABLE (vnode
)
1640 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1644 m_items
.safe_push (v
);
1645 m_symtab_node_map
.put (vnode
, v
);
1650 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1653 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1655 item
->index_in_class
= cls
->members
.length ();
1656 cls
->members
.safe_push (item
);
1660 /* Congruence classes are built by hash value. */
1663 sem_item_optimizer::build_hash_based_classes (void)
1665 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1667 sem_item
*item
= m_items
[i
];
1669 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1672 if (!group
->classes
.length ())
1675 group
->classes
.safe_push (new congruence_class (class_id
++));
1678 add_item_to_class (group
->classes
[0], item
);
1682 /* Build references according to call graph. */
1685 sem_item_optimizer::build_graph (void)
1687 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1689 sem_item
*item
= m_items
[i
];
1690 m_symtab_node_map
.put (item
->node
, item
);
1693 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1695 sem_item
*item
= m_items
[i
];
1697 if (item
->type
== FUNC
)
1699 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1701 cgraph_edge
*e
= cnode
->callees
;
1704 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1706 item
->add_reference (*slot
);
1712 ipa_ref
*ref
= NULL
;
1713 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1715 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1717 item
->add_reference (*slot
);
1722 /* Semantic items in classes having more than one element and initialized.
1723 In case of WPA, we load function body. */
1726 sem_item_optimizer::parse_nonsingleton_classes (void)
1728 unsigned int init_called_count
= 0;
1730 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1731 if (m_items
[i
]->cls
->members
.length () > 1)
1733 m_items
[i
]->init ();
1734 init_called_count
++;
1738 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1739 100.0f
* init_called_count
/ m_items
.length ());
1742 /* Equality function for semantic items is used to subdivide existing
1743 classes. If IN_WPA, fast equality function is invoked. */
1746 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1748 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1749 it
!= m_classes
.end (); ++it
)
1751 unsigned int class_count
= (*it
)->classes
.length ();
1753 for (unsigned i
= 0; i
< class_count
; i
++)
1755 congruence_class
*c
= (*it
)->classes
[i
];
1757 if (c
->members
.length() > 1)
1759 auto_vec
<sem_item
*> new_vector
;
1761 sem_item
*first
= c
->members
[0];
1762 new_vector
.safe_push (first
);
1764 unsigned class_split_first
= (*it
)->classes
.length ();
1766 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1768 sem_item
*item
= c
->members
[j
];
1770 bool equals
= in_wpa
? first
->equals_wpa (item
,
1771 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1774 new_vector
.safe_push (item
);
1777 bool integrated
= false;
1779 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1781 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1782 bool equals
= in_wpa
? x
->equals_wpa (item
,
1783 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1788 add_item_to_class ((*it
)->classes
[k
], item
);
1796 congruence_class
*c
= new congruence_class (class_id
++);
1798 add_item_to_class (c
, item
);
1800 (*it
)->classes
.safe_push (c
);
1805 // we replace newly created new_vector for the class we've just splitted
1806 c
->members
.release ();
1807 c
->members
.create (new_vector
.length ());
1809 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1810 add_item_to_class (c
, new_vector
[j
]);
1818 /* Verify congruence classes if checking is enabled. */
1821 sem_item_optimizer::verify_classes (void)
1824 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1825 it
!= m_classes
.end (); ++it
)
1827 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1829 congruence_class
*cls
= (*it
)->classes
[i
];
1831 gcc_checking_assert (cls
);
1832 gcc_checking_assert (cls
->members
.length () > 0);
1834 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1836 sem_item
*item
= cls
->members
[j
];
1838 gcc_checking_assert (item
);
1839 gcc_checking_assert (item
->cls
== cls
);
1841 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1843 sem_usage_pair
*usage
= item
->usages
[k
];
1844 gcc_checking_assert (usage
->item
->index_in_class
<
1845 usage
->item
->cls
->members
.length ());
1853 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1854 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1855 but unused argument. */
1858 sem_item_optimizer::release_split_map (congruence_class
* const &,
1859 bitmap
const &b
, traverse_split_pair
*)
1868 /* Process split operation for a class given as pointer CLS_PTR,
1869 where bitmap B splits congruence class members. DATA is used
1870 as argument of split pair. */
1873 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
1874 bitmap
const &b
, traverse_split_pair
*pair
)
1876 sem_item_optimizer
*optimizer
= pair
->optimizer
;
1877 const congruence_class
*splitter_cls
= pair
->cls
;
1879 /* If counted bits are greater than zero and less than the number of members
1880 a group will be splitted. */
1881 unsigned popcount
= bitmap_count_bits (b
);
1883 if (popcount
> 0 && popcount
< cls
->members
.length ())
1885 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
1887 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1889 int target
= bitmap_bit_p (b
, i
);
1890 congruence_class
*tc
= newclasses
[target
];
1892 add_item_to_class (tc
, cls
->members
[i
]);
1895 #ifdef ENABLE_CHECKING
1896 for (unsigned int i
= 0; i
< 2; i
++)
1897 gcc_checking_assert (newclasses
[i
]->members
.length ());
1900 if (splitter_cls
== cls
)
1901 optimizer
->splitter_class_removed
= true;
1903 /* Remove old class from worklist if presented. */
1904 bool in_worklist
= cls
->in_worklist
;
1907 cls
->in_worklist
= false;
1909 congruence_class_group g
;
1910 g
.hash
= cls
->members
[0]->get_hash ();
1911 g
.type
= cls
->members
[0]->type
;
1913 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
1915 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
1916 if (slot
->classes
[i
] == cls
)
1918 slot
->classes
.ordered_remove (i
);
1922 /* New class will be inserted and integrated to work list. */
1923 for (unsigned int i
= 0; i
< 2; i
++)
1924 optimizer
->add_class (newclasses
[i
]);
1926 /* Two classes replace one, so that increment just by one. */
1927 optimizer
->m_classes_count
++;
1929 /* If OLD class was presented in the worklist, we remove the class
1930 and replace it will both newly created classes. */
1932 for (unsigned int i
= 0; i
< 2; i
++)
1933 optimizer
->worklist_push (newclasses
[i
]);
1934 else /* Just smaller class is inserted. */
1936 unsigned int smaller_index
= newclasses
[0]->members
.length () <
1937 newclasses
[1]->members
.length () ?
1939 optimizer
->worklist_push (newclasses
[smaller_index
]);
1942 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1944 fprintf (dump_file
, " congruence class splitted:\n");
1945 cls
->dump (dump_file
, 4);
1947 fprintf (dump_file
, " newly created groups:\n");
1948 for (unsigned int i
= 0; i
< 2; i
++)
1949 newclasses
[i
]->dump (dump_file
, 4);
1952 /* Release class if not presented in work list. */
1961 /* Tests if a class CLS used as INDEXth splits any congruence classes.
1962 Bitmap stack BMSTACK is used for bitmap allocation. */
1965 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
1968 hash_map
<congruence_class
*, bitmap
> split_map
;
1970 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1972 sem_item
*item
= cls
->members
[i
];
1974 /* Iterate all usages that have INDEX as usage of the item. */
1975 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
1977 sem_usage_pair
*usage
= item
->usages
[j
];
1979 if (usage
->index
!= index
)
1982 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
1987 b
= BITMAP_ALLOC (&m_bmstack
);
1988 split_map
.put (usage
->item
->cls
, b
);
1994 gcc_checking_assert (usage
->item
->cls
);
1995 gcc_checking_assert (usage
->item
->index_in_class
<
1996 usage
->item
->cls
->members
.length ());
1999 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2003 traverse_split_pair pair
;
2004 pair
.optimizer
= this;
2007 splitter_class_removed
= false;
2009 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2011 /* Bitmap clean-up. */
2013 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2016 /* Every usage of a congruence class CLS is a candidate that can split the
2017 collection of classes. Bitmap stack BMSTACK is used for bitmap
2021 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2026 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2028 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2029 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2031 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2034 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2037 do_congruence_step_for_index (cls
, i
);
2039 if (splitter_class_removed
)
2043 BITMAP_FREE (usage
);
2046 /* Adds a newly created congruence class CLS to worklist. */
2049 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2051 /* Return if the class CLS is already presented in work list. */
2052 if (cls
->in_worklist
)
2055 cls
->in_worklist
= true;
2056 worklist
.push_back (cls
);
2059 /* Pops a class from worklist. */
2062 sem_item_optimizer::worklist_pop (void)
2064 congruence_class
*cls
;
2066 while (!worklist
.empty ())
2068 cls
= worklist
.front ();
2069 worklist
.pop_front ();
2070 if (cls
->in_worklist
)
2072 cls
->in_worklist
= false;
2078 /* Work list item was already intended to be removed.
2079 The only reason for doing it is to split a class.
2080 Thus, the class CLS is deleted. */
2088 /* Iterative congruence reduction function. */
2091 sem_item_optimizer::process_cong_reduction (void)
2093 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2094 it
!= m_classes
.end (); ++it
)
2095 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2096 if ((*it
)->classes
[i
]->is_class_used ())
2097 worklist_push ((*it
)->classes
[i
]);
2100 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2101 (unsigned long) worklist
.size ());
2103 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2104 fprintf (dump_file
, "Congruence class reduction\n");
2106 congruence_class
*cls
;
2107 while ((cls
= worklist_pop ()) != NULL
)
2108 do_congruence_step (cls
);
2111 /* Debug function prints all informations about congruence classes. */
2114 sem_item_optimizer::dump_cong_classes (void)
2120 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2121 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2123 /* Histogram calculation. */
2124 unsigned int max_index
= 0;
2125 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2127 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2128 it
!= m_classes
.end (); ++it
)
2130 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2132 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2140 "Class size histogram [num of members]: number of classe number of classess\n");
2142 for (unsigned int i
= 0; i
<= max_index
; i
++)
2144 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2146 fprintf (dump_file
, "\n\n");
2149 if (dump_flags
& TDF_DETAILS
)
2150 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2151 it
!= m_classes
.end (); ++it
)
2153 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2155 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2157 (*it
)->classes
[i
]->dump (dump_file
, 4);
2159 if(i
< (*it
)->classes
.length () - 1)
2160 fprintf (dump_file
, " ");
2167 /* After reduction is done, we can declare all items in a group
2168 to be equal. PREV_CLASS_COUNT is start number of classes
2169 before reduction. */
2172 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2174 unsigned int item_count
= m_items
.length ();
2175 unsigned int class_count
= m_classes_count
;
2176 unsigned int equal_items
= item_count
- class_count
;
2178 unsigned int non_singular_classes_count
= 0;
2179 unsigned int non_singular_classes_sum
= 0;
2181 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2182 it
!= m_classes
.end (); ++it
)
2183 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2185 congruence_class
*c
= (*it
)->classes
[i
];
2186 if (c
->members
.length () > 1)
2188 non_singular_classes_count
++;
2189 non_singular_classes_sum
+= c
->members
.length ();
2195 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2196 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2197 prev_class_count
, class_count
);
2198 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2199 1.0f
* item_count
/ prev_class_count
,
2200 1.0f
* item_count
/ class_count
);
2201 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2202 1.0f
* non_singular_classes_sum
/ non_singular_classes_count
,
2203 non_singular_classes_count
);
2204 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2205 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2206 100.0f
* equal_items
/ item_count
);
2209 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2210 it
!= m_classes
.end (); ++it
)
2211 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2213 congruence_class
*c
= (*it
)->classes
[i
];
2215 if (c
->members
.length () == 1)
2218 gcc_assert (c
->members
.length ());
2220 sem_item
*source
= c
->members
[0];
2222 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2224 sem_item
*alias
= c
->members
[j
];
2225 source
->equals (alias
, m_symtab_node_map
);
2229 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2230 source
->name (), alias
->name ());
2231 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2232 source
->asm_name (), alias
->asm_name ());
2235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2237 source
->dump_to_file (dump_file
);
2238 alias
->dump_to_file (dump_file
);
2241 source
->merge (alias
);
2246 /* Dump function prints all class members to a FILE with an INDENT. */
2249 congruence_class::dump (FILE *file
, unsigned int indent
) const
2251 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2252 id
, members
[0]->get_hash (), members
.length ());
2254 FPUTS_SPACES (file
, indent
+ 2, "");
2255 for (unsigned i
= 0; i
< members
.length (); i
++)
2256 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2257 members
[i
]->node
->order
);
2259 fprintf (file
, "\n");
2262 /* Returns true if there's a member that is used from another group. */
2265 congruence_class::is_class_used (void)
2267 for (unsigned int i
= 0; i
< members
.length (); i
++)
2268 if (members
[i
]->usages
.length ())
2274 /* Initialization and computation of symtab node hash, there data
2275 are propagated later on. */
2277 static sem_item_optimizer
*optimizer
= NULL
;
2279 /* Generate pass summary for IPA ICF pass. */
2282 ipa_icf_generate_summary (void)
2285 optimizer
= new sem_item_optimizer ();
2287 optimizer
->parse_funcs_and_vars ();
2290 /* Write pass summary for IPA ICF pass. */
2293 ipa_icf_write_summary (void)
2295 gcc_assert (optimizer
);
2297 optimizer
->write_summary ();
2300 /* Read pass summary for IPA ICF pass. */
2303 ipa_icf_read_summary (void)
2306 optimizer
= new sem_item_optimizer ();
2308 optimizer
->read_summary ();
2309 optimizer
->register_hooks ();
2312 /* Semantic equality exection function. */
2315 ipa_icf_driver (void)
2317 gcc_assert (optimizer
);
2319 optimizer
->execute ();
2320 optimizer
->unregister_hooks ();
2328 const pass_data pass_data_ipa_icf
=
2330 IPA_PASS
, /* type */
2332 OPTGROUP_IPA
, /* optinfo_flags */
2333 TV_IPA_ICF
, /* tv_id */
2334 0, /* properties_required */
2335 0, /* properties_provided */
2336 0, /* properties_destroyed */
2337 0, /* todo_flags_start */
2338 0, /* todo_flags_finish */
2341 class pass_ipa_icf
: public ipa_opt_pass_d
2344 pass_ipa_icf (gcc::context
*ctxt
)
2345 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2346 ipa_icf_generate_summary
, /* generate_summary */
2347 ipa_icf_write_summary
, /* write_summary */
2348 ipa_icf_read_summary
, /* read_summary */
2350 write_optimization_summary */
2352 read_optimization_summary */
2353 NULL
, /* stmt_fixup */
2354 0, /* function_transform_todo_flags_start */
2355 NULL
, /* function_transform */
2356 NULL
) /* variable_transform */
2359 /* opt_pass methods: */
2360 virtual bool gate (function
*)
2362 return flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2365 virtual unsigned int execute (function
*)
2367 return ipa_icf_driver();
2369 }; // class pass_ipa_icf
2371 } // ipa_icf namespace
2374 make_pass_ipa_icf (gcc::context
*ctxt
)
2376 return new ipa_icf::pass_ipa_icf (ctxt
);