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
++)
219 delete (bb_sorted
[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
583 && !alias
->instrumented_version
);
588 create_thunk
= false;
589 redirect_callers
= false;
592 if (create_alias
&& DECL_COMDAT_GROUP (alias
->decl
))
594 create_alias
= false;
598 /* We want thunk to always jump to the local function body
599 unless the body is comdat and may be optimized out. */
600 if ((create_thunk
|| redirect_callers
)
601 && (!original_discardable
602 || (DECL_COMDAT_GROUP (original
->decl
)
603 && (DECL_COMDAT_GROUP (original
->decl
)
604 == DECL_COMDAT_GROUP (alias
->decl
)))))
606 = dyn_cast
<cgraph_node
*> (original
->noninterposable_alias ());
608 if (redirect_callers
)
610 /* If alias is non-overwritable then
611 all direct calls are safe to be redirected to the original. */
612 bool redirected
= false;
613 while (alias
->callers
)
615 cgraph_edge
*e
= alias
->callers
;
616 e
->redirect_callee (local_original
);
617 push_cfun (DECL_STRUCT_FUNCTION (e
->caller
->decl
));
620 e
->redirect_call_stmt_to_callee ();
626 alias
->icf_merged
= true;
628 /* The alias function is removed if symbol address
630 if (!alias_address_matters
)
633 if (dump_file
&& redirected
)
634 fprintf (dump_file
, "Callgraph local calls have been redirected.\n\n");
636 /* If the condtion above is not met, we are lucky and can turn the
637 function into real alias. */
638 else if (create_alias
)
640 alias
->icf_merged
= true;
642 /* Remove the function's body. */
643 ipa_merge_profiles (original
, alias
);
644 alias
->release_body (true);
647 /* Create the alias. */
648 cgraph_node::create_alias (alias_func
->decl
, decl
);
649 alias
->resolve_alias (original
);
651 /* Workaround for PR63566 that forces equal calling convention
653 alias
->local
.local
= false;
654 original
->local
.local
= false;
657 fprintf (dump_file
, "Callgraph alias has been created.\n\n");
659 else if (create_thunk
)
661 if (DECL_COMDAT_GROUP (alias
->decl
))
664 fprintf (dump_file
, "Callgraph thunk cannot be created because of COMDAT\n");
669 alias
->icf_merged
= true;
670 ipa_merge_profiles (local_original
, alias
);
671 alias
->create_wrapper (local_original
);
674 fprintf (dump_file
, "Callgraph thunk has been created.\n\n");
677 fprintf (dump_file
, "Callgraph merge operation cannot be performed.\n\n");
682 /* Semantic item initialization function. */
685 sem_function::init (void)
688 get_node ()->get_body ();
690 tree fndecl
= node
->decl
;
691 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
694 gcc_assert (SSANAMES (func
));
696 ssa_names_size
= SSANAMES (func
)->length ();
700 region_tree
= func
->eh
->region_tree
;
702 /* iterating all function arguments. */
703 arg_count
= count_formal_params (fndecl
);
705 edge_count
= n_edges_for_fn (func
);
706 cfg_checksum
= coverage_compute_cfg_checksum (func
);
708 inchash::hash hstate
;
711 FOR_EACH_BB_FN (bb
, func
)
713 unsigned nondbg_stmt_count
= 0;
716 for (edge_iterator ei
= ei_start (bb
->preds
); ei_cond (ei
, &e
); ei_next (&ei
))
717 cfg_checksum
= iterative_hash_host_wide_int (e
->flags
,
720 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
723 gimple stmt
= gsi_stmt (gsi
);
725 if (gimple_code (stmt
) != GIMPLE_DEBUG
)
727 hash_stmt (&hstate
, stmt
);
732 gcode_hash
= hstate
.end ();
733 bb_sizes
.safe_push (nondbg_stmt_count
);
735 /* Inserting basic block to hash table. */
736 sem_bb
*semantic_bb
= new sem_bb (bb
, nondbg_stmt_count
,
737 EDGE_COUNT (bb
->preds
) + EDGE_COUNT (bb
->succs
));
739 bb_sorted
.safe_push (semantic_bb
);
745 /* Improve accumulated hash for HSTATE based on a gimple statement STMT. */
748 sem_function::hash_stmt (inchash::hash
*hstate
, gimple stmt
)
750 enum gimple_code code
= gimple_code (stmt
);
752 hstate
->add_int (code
);
754 if (code
== GIMPLE_CALL
)
756 /* Checking of argument. */
757 for (unsigned i
= 0; i
< gimple_call_num_args (stmt
); ++i
)
759 tree argument
= gimple_call_arg (stmt
, i
);
761 switch (TREE_CODE (argument
))
764 if (tree_fits_shwi_p (argument
))
765 hstate
->add_wide_int (tree_to_shwi (argument
));
766 else if (tree_fits_uhwi_p (argument
))
767 hstate
->add_wide_int (tree_to_uhwi (argument
));
773 c
= TREE_REAL_CST (argument
);
774 n
= real_to_integer (&c
);
776 hstate
->add_wide_int (n
);
780 tree addr_operand
= TREE_OPERAND (argument
, 0);
782 if (TREE_CODE (addr_operand
) == STRING_CST
)
783 hstate
->add (TREE_STRING_POINTER (addr_operand
),
784 TREE_STRING_LENGTH (addr_operand
));
795 /* Return true if polymorphic comparison must be processed. */
798 sem_function::compare_polymorphic_p (void)
800 return get_node ()->callees
!= NULL
801 || m_compared_func
->get_node ()->callees
!= NULL
;
804 /* For a given call graph NODE, the function constructs new
805 semantic function item. */
808 sem_function::parse (cgraph_node
*node
, bitmap_obstack
*stack
)
810 tree fndecl
= node
->decl
;
811 function
*func
= DECL_STRUCT_FUNCTION (fndecl
);
813 /* TODO: add support for thunks and aliases. */
815 if (!func
|| !node
->has_gimple_body_p ())
818 if (lookup_attribute_by_prefix ("omp ", DECL_ATTRIBUTES (node
->decl
)) != NULL
)
821 sem_function
*f
= new sem_function (node
, 0, stack
);
828 /* Parses function arguments and result type. */
831 sem_function::parse_tree_args (void)
835 if (arg_types
.exists ())
836 arg_types
.release ();
838 arg_types
.create (4);
839 tree fnargs
= DECL_ARGUMENTS (decl
);
841 for (tree parm
= fnargs
; parm
; parm
= DECL_CHAIN (parm
))
842 arg_types
.safe_push (DECL_ARG_TYPE (parm
));
844 /* Function result type. */
845 result
= DECL_RESULT (decl
);
846 result_type
= result
? TREE_TYPE (result
) : NULL
;
848 /* During WPA, we can get arguments by following method. */
851 tree type
= TYPE_ARG_TYPES (TREE_TYPE (decl
));
852 for (tree parm
= type
; parm
; parm
= TREE_CHAIN (parm
))
853 arg_types
.safe_push (TYPE_CANONICAL (TREE_VALUE (parm
)));
855 result_type
= TREE_TYPE (TREE_TYPE (decl
));
859 /* For given basic blocks BB1 and BB2 (from functions FUNC1 and FUNC),
860 return true if phi nodes are semantically equivalent in these blocks . */
863 sem_function::compare_phi_node (basic_block bb1
, basic_block bb2
)
865 gimple_stmt_iterator si1
, si2
;
867 unsigned size1
, size2
, i
;
871 gcc_assert (bb1
!= NULL
);
872 gcc_assert (bb2
!= NULL
);
874 si2
= gsi_start_phis (bb2
);
875 for (si1
= gsi_start_phis (bb1
); !gsi_end_p (si1
);
878 gsi_next_nonvirtual_phi (&si1
);
879 gsi_next_nonvirtual_phi (&si2
);
881 if (gsi_end_p (si1
) && gsi_end_p (si2
))
884 if (gsi_end_p (si1
) || gsi_end_p (si2
))
885 return return_false();
887 phi1
= gsi_stmt (si1
);
888 phi2
= gsi_stmt (si2
);
890 tree phi_result1
= gimple_phi_result (phi1
);
891 tree phi_result2
= gimple_phi_result (phi2
);
893 if (!m_checker
->compare_operand (phi_result1
, phi_result2
))
894 return return_false_with_msg ("PHI results are different");
896 size1
= gimple_phi_num_args (phi1
);
897 size2
= gimple_phi_num_args (phi2
);
900 return return_false ();
902 for (i
= 0; i
< size1
; ++i
)
904 t1
= gimple_phi_arg (phi1
, i
)->def
;
905 t2
= gimple_phi_arg (phi2
, i
)->def
;
907 if (!m_checker
->compare_operand (t1
, t2
))
908 return return_false ();
910 e1
= gimple_phi_arg_edge (phi1
, i
);
911 e2
= gimple_phi_arg_edge (phi2
, i
);
913 if (!m_checker
->compare_edge (e1
, e2
))
914 return return_false ();
923 /* Returns true if tree T can be compared as a handled component. */
926 sem_function::icf_handled_component_p (tree t
)
928 tree_code tc
= TREE_CODE (t
);
930 return ((handled_component_p (t
))
931 || tc
== ADDR_EXPR
|| tc
== MEM_REF
|| tc
== REALPART_EXPR
932 || tc
== IMAGPART_EXPR
|| tc
== OBJ_TYPE_REF
);
935 /* Basic blocks dictionary BB_DICT returns true if SOURCE index BB
936 corresponds to TARGET. */
939 sem_function::bb_dict_test (int* bb_dict
, int source
, int target
)
941 if (bb_dict
[source
] == -1)
943 bb_dict
[source
] = target
;
947 return bb_dict
[source
] == target
;
950 /* Iterates all tree types in T1 and T2 and returns true if all types
951 are compatible. If COMPARE_POLYMORPHIC is set to true,
952 more strict comparison is executed. */
955 sem_function::compare_type_list (tree t1
, tree t2
, bool compare_polymorphic
)
963 while (t1
!= NULL
&& t2
!= NULL
)
965 tv1
= TREE_VALUE (t1
);
966 tv2
= TREE_VALUE (t2
);
968 tc1
= TREE_CODE (tv1
);
969 tc2
= TREE_CODE (tv2
);
971 if (tc1
== NOP_EXPR
&& tc2
== NOP_EXPR
)
973 else if (tc1
== NOP_EXPR
|| tc2
== NOP_EXPR
)
975 else if (!func_checker::compatible_types_p (tv1
, tv2
, compare_polymorphic
))
978 t1
= TREE_CHAIN (t1
);
979 t2
= TREE_CHAIN (t2
);
986 /* Semantic variable constructor that uses STACK as bitmap memory stack. */
988 sem_variable::sem_variable (bitmap_obstack
*stack
): sem_item (VAR
, stack
)
992 /* Constructor based on varpool node _NODE with computed hash _HASH.
993 Bitmap STACK is used for memory allocation. */
995 sem_variable::sem_variable (varpool_node
*node
, hashval_t _hash
,
996 bitmap_obstack
*stack
): sem_item(VAR
,
999 gcc_checking_assert (node
);
1000 gcc_checking_assert (get_node ());
1003 /* Returns true if the item equals to ITEM given as argument. */
1006 sem_variable::equals (sem_item
*item
,
1007 hash_map
<symtab_node
*, sem_item
*> & ARG_UNUSED (ignored_nodes
))
1009 gcc_assert (item
->type
== VAR
);
1011 sem_variable
*v
= static_cast<sem_variable
*>(item
);
1013 if (!ctor
|| !v
->ctor
)
1014 return return_false_with_msg ("ctor is missing for semantic variable");
1016 return sem_variable::equals (ctor
, v
->ctor
);
1019 /* Compares trees T1 and T2 for semantic equality. */
1022 sem_variable::equals (tree t1
, tree t2
)
1024 tree_code tc1
= TREE_CODE (t1
);
1025 tree_code tc2
= TREE_CODE (t2
);
1034 unsigned len1
= vec_safe_length (CONSTRUCTOR_ELTS (t1
));
1035 unsigned len2
= vec_safe_length (CONSTRUCTOR_ELTS (t2
));
1040 for (unsigned i
= 0; i
< len1
; i
++)
1041 if (!sem_variable::equals (CONSTRUCTOR_ELT (t1
, i
)->value
,
1042 CONSTRUCTOR_ELT (t2
, i
)->value
)
1043 || CONSTRUCTOR_ELT (t1
, i
)->index
!= CONSTRUCTOR_ELT (t2
, i
)->index
)
1050 tree x1
= TREE_OPERAND (t1
, 0);
1051 tree x2
= TREE_OPERAND (t2
, 0);
1052 tree y1
= TREE_OPERAND (t1
, 1);
1053 tree y2
= TREE_OPERAND (t2
, 1);
1055 if (!func_checker::compatible_types_p (TREE_TYPE (x1
), TREE_TYPE (x2
),
1057 return return_false ();
1059 /* Type of the offset on MEM_REF does not matter. */
1060 return sem_variable::equals (x1
, x2
)
1061 && wi::to_offset (y1
) == wi::to_offset (y2
);
1066 tree op1
= TREE_OPERAND (t1
, 0);
1067 tree op2
= TREE_OPERAND (t2
, 0);
1068 return sem_variable::equals (op1
, op2
);
1076 return func_checker::compatible_types_p (TREE_TYPE (t1
), TREE_TYPE (t2
),
1078 && wi::to_offset (t1
) == wi::to_offset (t2
);
1082 return operand_equal_p (t1
, t2
, OEP_ONLY_CONST
);
1085 case POINTER_PLUS_EXPR
:
1087 tree x1
= TREE_OPERAND (t1
, 0);
1088 tree x2
= TREE_OPERAND (t2
, 0);
1089 tree y1
= TREE_OPERAND (t1
, 1);
1090 tree y2
= TREE_OPERAND (t2
, 1);
1092 return sem_variable::equals (x1
, x2
) && sem_variable::equals (y1
, y2
);
1095 return return_false_with_msg ("ERROR_MARK");
1097 return return_false_with_msg ("Unknown TREE code reached");
1101 /* Parser function that visits a varpool NODE. */
1104 sem_variable::parse (varpool_node
*node
, bitmap_obstack
*stack
)
1106 tree decl
= node
->decl
;
1108 bool readonly
= TYPE_P (decl
) ? TYPE_READONLY (decl
) : TREE_READONLY (decl
);
1109 bool can_handle
= readonly
&& (DECL_VIRTUAL_P (decl
)
1110 || !TREE_ADDRESSABLE (decl
));
1115 tree ctor
= ctor_for_folding (decl
);
1119 sem_variable
*v
= new sem_variable (node
, 0, stack
);
1126 /* References independent hash function. */
1129 sem_variable::get_hash (void)
1134 inchash::hash hstate
;
1136 hstate
.add_int (456346417);
1137 hstate
.add_int (TREE_CODE (ctor
));
1139 if (TREE_CODE (ctor
) == CONSTRUCTOR
)
1141 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (ctor
));
1142 hstate
.add_int (length
);
1145 hash
= hstate
.end ();
1150 /* Merges instance with an ALIAS_ITEM, where alias, thunk or redirection can
1154 sem_variable::merge (sem_item
*alias_item
)
1156 gcc_assert (alias_item
->type
== VAR
);
1158 sem_variable
*alias_var
= static_cast<sem_variable
*> (alias_item
);
1160 varpool_node
*original
= get_node ();
1161 varpool_node
*alias
= alias_var
->get_node ();
1162 bool original_discardable
= false;
1164 /* See if original is in a section that can be discarded if the main
1165 symbol is not used. */
1166 if (DECL_EXTERNAL (original
->decl
))
1167 original_discardable
= true;
1168 if (original
->resolution
== LDPR_PREEMPTED_REG
1169 || original
->resolution
== LDPR_PREEMPTED_IR
)
1170 original_discardable
= true;
1171 if (original
->can_be_discarded_p ())
1172 original_discardable
= true;
1174 gcc_assert (!TREE_ASM_WRITTEN (alias
->decl
));
1176 if (original_discardable
|| DECL_EXTERNAL (alias_var
->decl
) ||
1177 !compare_sections (alias_var
))
1180 fprintf (dump_file
, "Varpool alias cannot be created\n\n");
1186 // alias cycle creation check
1187 varpool_node
*n
= original
;
1191 n
= n
->get_alias_target ();
1195 fprintf (dump_file
, "Varpool alias cannot be created (alias cycle).\n\n");
1201 alias
->analyzed
= false;
1203 DECL_INITIAL (alias
->decl
) = NULL
;
1204 alias
->need_bounds_init
= false;
1205 alias
->remove_all_references ();
1207 varpool_node::create_alias (alias_var
->decl
, decl
);
1208 alias
->resolve_alias (original
);
1211 fprintf (dump_file
, "Varpool alias has been created.\n\n");
1218 sem_variable::compare_sections (sem_variable
*alias
)
1220 const char *source
= node
->get_section ();
1221 const char *target
= alias
->node
->get_section();
1223 if (source
== NULL
&& target
== NULL
)
1225 else if(!source
|| !target
)
1228 return strcmp (source
, target
) == 0;
1231 /* Dump symbol to FILE. */
1234 sem_variable::dump_to_file (FILE *file
)
1238 print_node (file
, "", decl
, 0);
1239 fprintf (file
, "\n\n");
1242 /* Iterates though a constructor and identifies tree references
1243 we are interested in semantic function equality. */
1246 sem_variable::parse_tree_refs (tree t
)
1248 switch (TREE_CODE (t
))
1252 unsigned length
= vec_safe_length (CONSTRUCTOR_ELTS (t
));
1254 for (unsigned i
= 0; i
< length
; i
++)
1255 parse_tree_refs(CONSTRUCTOR_ELT (t
, i
)->value
);
1262 tree op
= TREE_OPERAND (t
, 0);
1263 parse_tree_refs (op
);
1268 tree_refs
.safe_push (t
);
1276 unsigned int sem_item_optimizer::class_id
= 0;
1278 sem_item_optimizer::sem_item_optimizer (): worklist (0), m_classes (0),
1279 m_classes_count (0), m_cgraph_node_hooks (NULL
), m_varpool_node_hooks (NULL
)
1282 bitmap_obstack_initialize (&m_bmstack
);
1285 sem_item_optimizer::~sem_item_optimizer ()
1287 for (unsigned int i
= 0; i
< m_items
.length (); i
++)
1290 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1291 it
!= m_classes
.end (); ++it
)
1293 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1294 delete (*it
)->classes
[i
];
1296 (*it
)->classes
.release ();
1301 bitmap_obstack_release (&m_bmstack
);
1304 /* Write IPA ICF summary for symbols. */
1307 sem_item_optimizer::write_summary (void)
1309 unsigned int count
= 0;
1311 output_block
*ob
= create_output_block (LTO_section_ipa_icf
);
1312 lto_symtab_encoder_t encoder
= ob
->decl_state
->symtab_node_encoder
;
1315 /* Calculate number of symbols to be serialized. */
1316 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1318 lsei_next_in_partition (&lsei
))
1320 symtab_node
*node
= lsei_node (lsei
);
1322 if (m_symtab_node_map
.get (node
))
1326 streamer_write_uhwi (ob
, count
);
1328 /* Process all of the symbols. */
1329 for (lto_symtab_encoder_iterator lsei
= lsei_start_in_partition (encoder
);
1331 lsei_next_in_partition (&lsei
))
1333 symtab_node
*node
= lsei_node (lsei
);
1335 sem_item
**item
= m_symtab_node_map
.get (node
);
1339 int node_ref
= lto_symtab_encoder_encode (encoder
, node
);
1340 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
1342 streamer_write_uhwi (ob
, (*item
)->get_hash ());
1346 streamer_write_char_stream (ob
->main_stream
, 0);
1347 produce_asm (ob
, NULL
);
1348 destroy_output_block (ob
);
1351 /* Reads a section from LTO stream file FILE_DATA. Input block for DATA
1352 contains LEN bytes. */
1355 sem_item_optimizer::read_section (lto_file_decl_data
*file_data
,
1356 const char *data
, size_t len
)
1358 const lto_function_header
*header
=
1359 (const lto_function_header
*) data
;
1360 const int cfg_offset
= sizeof (lto_function_header
);
1361 const int main_offset
= cfg_offset
+ header
->cfg_size
;
1362 const int string_offset
= main_offset
+ header
->main_size
;
1367 lto_input_block
ib_main ((const char *) data
+ main_offset
, 0,
1371 lto_data_in_create (file_data
, (const char *) data
+ string_offset
,
1372 header
->string_size
, vNULL
);
1374 count
= streamer_read_uhwi (&ib_main
);
1376 for (i
= 0; i
< count
; i
++)
1380 lto_symtab_encoder_t encoder
;
1382 index
= streamer_read_uhwi (&ib_main
);
1383 encoder
= file_data
->symtab_node_encoder
;
1384 node
= lto_symtab_encoder_deref (encoder
, index
);
1386 hashval_t hash
= streamer_read_uhwi (&ib_main
);
1388 gcc_assert (node
->definition
);
1391 fprintf (dump_file
, "Symbol added:%s (tree: %p, uid:%u)\n", node
->asm_name (),
1392 (void *) node
->decl
, node
->order
);
1394 if (is_a
<cgraph_node
*> (node
))
1396 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (node
);
1398 m_items
.safe_push (new sem_function (cnode
, hash
, &m_bmstack
));
1402 varpool_node
*vnode
= dyn_cast
<varpool_node
*> (node
);
1404 m_items
.safe_push (new sem_variable (vnode
, hash
, &m_bmstack
));
1408 lto_free_section_data (file_data
, LTO_section_ipa_icf
, NULL
, data
,
1410 lto_data_in_delete (data_in
);
1413 /* Read IPA IPA ICF summary for symbols. */
1416 sem_item_optimizer::read_summary (void)
1418 lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1419 lto_file_decl_data
*file_data
;
1422 while ((file_data
= file_data_vec
[j
++]))
1425 const char *data
= lto_get_section_data (file_data
,
1426 LTO_section_ipa_icf
, NULL
, &len
);
1429 read_section (file_data
, data
, len
);
1433 /* Register callgraph and varpool hooks. */
1436 sem_item_optimizer::register_hooks (void)
1438 m_cgraph_node_hooks
= symtab
->add_cgraph_removal_hook
1439 (&sem_item_optimizer::cgraph_removal_hook
, this);
1441 m_varpool_node_hooks
= symtab
->add_varpool_removal_hook
1442 (&sem_item_optimizer::varpool_removal_hook
, this);
1445 /* Unregister callgraph and varpool hooks. */
1448 sem_item_optimizer::unregister_hooks (void)
1450 if (m_cgraph_node_hooks
)
1451 symtab
->remove_cgraph_removal_hook (m_cgraph_node_hooks
);
1453 if (m_varpool_node_hooks
)
1454 symtab
->remove_varpool_removal_hook (m_varpool_node_hooks
);
1457 /* Adds a CLS to hashtable associated by hash value. */
1460 sem_item_optimizer::add_class (congruence_class
*cls
)
1462 gcc_assert (cls
->members
.length ());
1464 congruence_class_group
*group
= get_group_by_hash (
1465 cls
->members
[0]->get_hash (),
1466 cls
->members
[0]->type
);
1467 group
->classes
.safe_push (cls
);
1470 /* Gets a congruence class group based on given HASH value and TYPE. */
1472 congruence_class_group
*
1473 sem_item_optimizer::get_group_by_hash (hashval_t hash
, sem_item_type type
)
1475 congruence_class_group
*item
= XNEW (congruence_class_group
);
1479 congruence_class_group
**slot
= m_classes
.find_slot (item
, INSERT
);
1485 item
->classes
.create (1);
1492 /* Callgraph removal hook called for a NODE with a custom DATA. */
1495 sem_item_optimizer::cgraph_removal_hook (cgraph_node
*node
, void *data
)
1497 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1498 optimizer
->remove_symtab_node (node
);
1501 /* Varpool removal hook called for a NODE with a custom DATA. */
1504 sem_item_optimizer::varpool_removal_hook (varpool_node
*node
, void *data
)
1506 sem_item_optimizer
*optimizer
= (sem_item_optimizer
*) data
;
1507 optimizer
->remove_symtab_node (node
);
1510 /* Remove symtab NODE triggered by symtab removal hooks. */
1513 sem_item_optimizer::remove_symtab_node (symtab_node
*node
)
1515 gcc_assert (!m_classes
.elements());
1517 m_removed_items_set
.add (node
);
1521 sem_item_optimizer::remove_item (sem_item
*item
)
1523 if (m_symtab_node_map
.get (item
->node
))
1524 m_symtab_node_map
.remove (item
->node
);
1528 /* Removes all callgraph and varpool nodes that are marked by symtab
1532 sem_item_optimizer::filter_removed_items (void)
1534 auto_vec
<sem_item
*> filtered
;
1536 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1538 sem_item
*item
= m_items
[i
];
1540 if (!flag_ipa_icf_functions
&& item
->type
== FUNC
)
1546 if (!flag_ipa_icf_variables
&& item
->type
== VAR
)
1552 bool no_body_function
= false;
1554 if (item
->type
== FUNC
)
1556 cgraph_node
*cnode
= static_cast <sem_function
*>(item
)->get_node ();
1558 no_body_function
= in_lto_p
&& (cnode
->alias
|| cnode
->body_removed
);
1561 if(!m_removed_items_set
.contains (m_items
[i
]->node
)
1562 && !no_body_function
)
1564 if (item
->type
== VAR
|| (!DECL_CXX_CONSTRUCTOR_P (item
->decl
)
1565 && !DECL_CXX_DESTRUCTOR_P (item
->decl
)))
1567 filtered
.safe_push (m_items
[i
]);
1575 /* Clean-up of released semantic items. */
1578 for (unsigned int i
= 0; i
< filtered
.length(); i
++)
1579 m_items
.safe_push (filtered
[i
]);
1582 /* Optimizer entry point. */
1585 sem_item_optimizer::execute (void)
1587 filter_removed_items ();
1588 build_hash_based_classes ();
1591 fprintf (dump_file
, "Dump after hash based groups\n");
1592 dump_cong_classes ();
1594 for (unsigned int i
= 0; i
< m_items
.length(); i
++)
1595 m_items
[i
]->init_wpa ();
1599 subdivide_classes_by_equality (true);
1602 fprintf (dump_file
, "Dump after WPA based types groups\n");
1604 dump_cong_classes ();
1606 process_cong_reduction ();
1610 fprintf (dump_file
, "Dump after callgraph-based congruence reduction\n");
1612 dump_cong_classes ();
1614 parse_nonsingleton_classes ();
1615 subdivide_classes_by_equality ();
1618 fprintf (dump_file
, "Dump after full equality comparison of groups\n");
1620 dump_cong_classes ();
1622 unsigned int prev_class_count
= m_classes_count
;
1624 process_cong_reduction ();
1625 dump_cong_classes ();
1627 merge_classes (prev_class_count
);
1629 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1630 symtab_node::dump_table (dump_file
);
1633 /* Function responsible for visiting all potential functions and
1634 read-only variables that can be merged. */
1637 sem_item_optimizer::parse_funcs_and_vars (void)
1641 if (flag_ipa_icf_functions
)
1642 FOR_EACH_DEFINED_FUNCTION (cnode
)
1644 sem_function
*f
= sem_function::parse (cnode
, &m_bmstack
);
1647 m_items
.safe_push (f
);
1648 m_symtab_node_map
.put (cnode
, f
);
1651 fprintf (dump_file
, "Parsed function:%s\n", f
->asm_name ());
1653 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1654 f
->dump_to_file (dump_file
);
1657 fprintf (dump_file
, "Not parsed function:%s\n", cnode
->asm_name ());
1660 varpool_node
*vnode
;
1662 if (flag_ipa_icf_variables
)
1663 FOR_EACH_DEFINED_VARIABLE (vnode
)
1665 sem_variable
*v
= sem_variable::parse (vnode
, &m_bmstack
);
1669 m_items
.safe_push (v
);
1670 m_symtab_node_map
.put (vnode
, v
);
1675 /* Makes pairing between a congruence class CLS and semantic ITEM. */
1678 sem_item_optimizer::add_item_to_class (congruence_class
*cls
, sem_item
*item
)
1680 item
->index_in_class
= cls
->members
.length ();
1681 cls
->members
.safe_push (item
);
1685 /* Congruence classes are built by hash value. */
1688 sem_item_optimizer::build_hash_based_classes (void)
1690 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1692 sem_item
*item
= m_items
[i
];
1694 congruence_class_group
*group
= get_group_by_hash (item
->get_hash (),
1697 if (!group
->classes
.length ())
1700 group
->classes
.safe_push (new congruence_class (class_id
++));
1703 add_item_to_class (group
->classes
[0], item
);
1707 /* Build references according to call graph. */
1710 sem_item_optimizer::build_graph (void)
1712 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1714 sem_item
*item
= m_items
[i
];
1715 m_symtab_node_map
.put (item
->node
, item
);
1718 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1720 sem_item
*item
= m_items
[i
];
1722 if (item
->type
== FUNC
)
1724 cgraph_node
*cnode
= dyn_cast
<cgraph_node
*> (item
->node
);
1726 cgraph_edge
*e
= cnode
->callees
;
1729 sem_item
**slot
= m_symtab_node_map
.get (e
->callee
);
1731 item
->add_reference (*slot
);
1737 ipa_ref
*ref
= NULL
;
1738 for (unsigned i
= 0; item
->node
->iterate_reference (i
, ref
); i
++)
1740 sem_item
**slot
= m_symtab_node_map
.get (ref
->referred
);
1742 item
->add_reference (*slot
);
1747 /* Semantic items in classes having more than one element and initialized.
1748 In case of WPA, we load function body. */
1751 sem_item_optimizer::parse_nonsingleton_classes (void)
1753 unsigned int init_called_count
= 0;
1755 for (unsigned i
= 0; i
< m_items
.length (); i
++)
1756 if (m_items
[i
]->cls
->members
.length () > 1)
1758 m_items
[i
]->init ();
1759 init_called_count
++;
1763 fprintf (dump_file
, "Init called for %u items (%.2f%%).\n", init_called_count
,
1764 m_items
.length () ? 100.0f
* init_called_count
/ m_items
.length (): 0.0f
);
1767 /* Equality function for semantic items is used to subdivide existing
1768 classes. If IN_WPA, fast equality function is invoked. */
1771 sem_item_optimizer::subdivide_classes_by_equality (bool in_wpa
)
1773 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1774 it
!= m_classes
.end (); ++it
)
1776 unsigned int class_count
= (*it
)->classes
.length ();
1778 for (unsigned i
= 0; i
< class_count
; i
++)
1780 congruence_class
*c
= (*it
)->classes
[i
];
1782 if (c
->members
.length() > 1)
1784 auto_vec
<sem_item
*> new_vector
;
1786 sem_item
*first
= c
->members
[0];
1787 new_vector
.safe_push (first
);
1789 unsigned class_split_first
= (*it
)->classes
.length ();
1791 for (unsigned j
= 1; j
< c
->members
.length (); j
++)
1793 sem_item
*item
= c
->members
[j
];
1795 bool equals
= in_wpa
? first
->equals_wpa (item
,
1796 m_symtab_node_map
) : first
->equals (item
, m_symtab_node_map
);
1799 new_vector
.safe_push (item
);
1802 bool integrated
= false;
1804 for (unsigned k
= class_split_first
; k
< (*it
)->classes
.length (); k
++)
1806 sem_item
*x
= (*it
)->classes
[k
]->members
[0];
1807 bool equals
= in_wpa
? x
->equals_wpa (item
,
1808 m_symtab_node_map
) : x
->equals (item
, m_symtab_node_map
);
1813 add_item_to_class ((*it
)->classes
[k
], item
);
1821 congruence_class
*c
= new congruence_class (class_id
++);
1823 add_item_to_class (c
, item
);
1825 (*it
)->classes
.safe_push (c
);
1830 // we replace newly created new_vector for the class we've just splitted
1831 c
->members
.release ();
1832 c
->members
.create (new_vector
.length ());
1834 for (unsigned int j
= 0; j
< new_vector
.length (); j
++)
1835 add_item_to_class (c
, new_vector
[j
]);
1843 /* Verify congruence classes if checking is enabled. */
1846 sem_item_optimizer::verify_classes (void)
1849 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
1850 it
!= m_classes
.end (); ++it
)
1852 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
1854 congruence_class
*cls
= (*it
)->classes
[i
];
1856 gcc_checking_assert (cls
);
1857 gcc_checking_assert (cls
->members
.length () > 0);
1859 for (unsigned int j
= 0; j
< cls
->members
.length (); j
++)
1861 sem_item
*item
= cls
->members
[j
];
1863 gcc_checking_assert (item
);
1864 gcc_checking_assert (item
->cls
== cls
);
1866 for (unsigned k
= 0; k
< item
->usages
.length (); k
++)
1868 sem_usage_pair
*usage
= item
->usages
[k
];
1869 gcc_checking_assert (usage
->item
->index_in_class
<
1870 usage
->item
->cls
->members
.length ());
1878 /* Disposes split map traverse function. CLS_PTR is pointer to congruence
1879 class, BSLOT is bitmap slot we want to release. DATA is mandatory,
1880 but unused argument. */
1883 sem_item_optimizer::release_split_map (congruence_class
* const &,
1884 bitmap
const &b
, traverse_split_pair
*)
1893 /* Process split operation for a class given as pointer CLS_PTR,
1894 where bitmap B splits congruence class members. DATA is used
1895 as argument of split pair. */
1898 sem_item_optimizer::traverse_congruence_split (congruence_class
* const &cls
,
1899 bitmap
const &b
, traverse_split_pair
*pair
)
1901 sem_item_optimizer
*optimizer
= pair
->optimizer
;
1902 const congruence_class
*splitter_cls
= pair
->cls
;
1904 /* If counted bits are greater than zero and less than the number of members
1905 a group will be splitted. */
1906 unsigned popcount
= bitmap_count_bits (b
);
1908 if (popcount
> 0 && popcount
< cls
->members
.length ())
1910 congruence_class
* newclasses
[2] = { new congruence_class (class_id
++), new congruence_class (class_id
++) };
1912 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1914 int target
= bitmap_bit_p (b
, i
);
1915 congruence_class
*tc
= newclasses
[target
];
1917 add_item_to_class (tc
, cls
->members
[i
]);
1920 #ifdef ENABLE_CHECKING
1921 for (unsigned int i
= 0; i
< 2; i
++)
1922 gcc_checking_assert (newclasses
[i
]->members
.length ());
1925 if (splitter_cls
== cls
)
1926 optimizer
->splitter_class_removed
= true;
1928 /* Remove old class from worklist if presented. */
1929 bool in_worklist
= cls
->in_worklist
;
1932 cls
->in_worklist
= false;
1934 congruence_class_group g
;
1935 g
.hash
= cls
->members
[0]->get_hash ();
1936 g
.type
= cls
->members
[0]->type
;
1938 congruence_class_group
*slot
= optimizer
->m_classes
.find(&g
);
1940 for (unsigned int i
= 0; i
< slot
->classes
.length (); i
++)
1941 if (slot
->classes
[i
] == cls
)
1943 slot
->classes
.ordered_remove (i
);
1947 /* New class will be inserted and integrated to work list. */
1948 for (unsigned int i
= 0; i
< 2; i
++)
1949 optimizer
->add_class (newclasses
[i
]);
1951 /* Two classes replace one, so that increment just by one. */
1952 optimizer
->m_classes_count
++;
1954 /* If OLD class was presented in the worklist, we remove the class
1955 and replace it will both newly created classes. */
1957 for (unsigned int i
= 0; i
< 2; i
++)
1958 optimizer
->worklist_push (newclasses
[i
]);
1959 else /* Just smaller class is inserted. */
1961 unsigned int smaller_index
= newclasses
[0]->members
.length () <
1962 newclasses
[1]->members
.length () ?
1964 optimizer
->worklist_push (newclasses
[smaller_index
]);
1967 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1969 fprintf (dump_file
, " congruence class splitted:\n");
1970 cls
->dump (dump_file
, 4);
1972 fprintf (dump_file
, " newly created groups:\n");
1973 for (unsigned int i
= 0; i
< 2; i
++)
1974 newclasses
[i
]->dump (dump_file
, 4);
1977 /* Release class if not presented in work list. */
1986 /* Tests if a class CLS used as INDEXth splits any congruence classes.
1987 Bitmap stack BMSTACK is used for bitmap allocation. */
1990 sem_item_optimizer::do_congruence_step_for_index (congruence_class
*cls
,
1993 hash_map
<congruence_class
*, bitmap
> split_map
;
1995 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
1997 sem_item
*item
= cls
->members
[i
];
1999 /* Iterate all usages that have INDEX as usage of the item. */
2000 for (unsigned int j
= 0; j
< item
->usages
.length (); j
++)
2002 sem_usage_pair
*usage
= item
->usages
[j
];
2004 if (usage
->index
!= index
)
2007 bitmap
*slot
= split_map
.get (usage
->item
->cls
);
2012 b
= BITMAP_ALLOC (&m_bmstack
);
2013 split_map
.put (usage
->item
->cls
, b
);
2019 gcc_checking_assert (usage
->item
->cls
);
2020 gcc_checking_assert (usage
->item
->index_in_class
<
2021 usage
->item
->cls
->members
.length ());
2024 bitmap_set_bit (b
, usage
->item
->index_in_class
);
2028 traverse_split_pair pair
;
2029 pair
.optimizer
= this;
2032 splitter_class_removed
= false;
2034 <traverse_split_pair
*, sem_item_optimizer::traverse_congruence_split
> (&pair
);
2036 /* Bitmap clean-up. */
2038 <traverse_split_pair
*, sem_item_optimizer::release_split_map
> (NULL
);
2041 /* Every usage of a congruence class CLS is a candidate that can split the
2042 collection of classes. Bitmap stack BMSTACK is used for bitmap
2046 sem_item_optimizer::do_congruence_step (congruence_class
*cls
)
2051 bitmap usage
= BITMAP_ALLOC (&m_bmstack
);
2053 for (unsigned int i
= 0; i
< cls
->members
.length (); i
++)
2054 bitmap_ior_into (usage
, cls
->members
[i
]->usage_index_bitmap
);
2056 EXECUTE_IF_SET_IN_BITMAP (usage
, 0, i
, bi
)
2058 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2059 fprintf (dump_file
, " processing congruece step for class: %u, index: %u\n",
2062 do_congruence_step_for_index (cls
, i
);
2064 if (splitter_class_removed
)
2068 BITMAP_FREE (usage
);
2071 /* Adds a newly created congruence class CLS to worklist. */
2074 sem_item_optimizer::worklist_push (congruence_class
*cls
)
2076 /* Return if the class CLS is already presented in work list. */
2077 if (cls
->in_worklist
)
2080 cls
->in_worklist
= true;
2081 worklist
.push_back (cls
);
2084 /* Pops a class from worklist. */
2087 sem_item_optimizer::worklist_pop (void)
2089 congruence_class
*cls
;
2091 while (!worklist
.empty ())
2093 cls
= worklist
.front ();
2094 worklist
.pop_front ();
2095 if (cls
->in_worklist
)
2097 cls
->in_worklist
= false;
2103 /* Work list item was already intended to be removed.
2104 The only reason for doing it is to split a class.
2105 Thus, the class CLS is deleted. */
2113 /* Iterative congruence reduction function. */
2116 sem_item_optimizer::process_cong_reduction (void)
2118 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2119 it
!= m_classes
.end (); ++it
)
2120 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2121 if ((*it
)->classes
[i
]->is_class_used ())
2122 worklist_push ((*it
)->classes
[i
]);
2125 fprintf (dump_file
, "Worklist has been filled with: %lu\n",
2126 (unsigned long) worklist
.size ());
2128 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2129 fprintf (dump_file
, "Congruence class reduction\n");
2131 congruence_class
*cls
;
2132 while ((cls
= worklist_pop ()) != NULL
)
2133 do_congruence_step (cls
);
2136 /* Debug function prints all informations about congruence classes. */
2139 sem_item_optimizer::dump_cong_classes (void)
2145 "Congruence classes: %u (unique hash values: %lu), with total: %u items\n",
2146 m_classes_count
, (unsigned long) m_classes
.elements(), m_items
.length ());
2148 /* Histogram calculation. */
2149 unsigned int max_index
= 0;
2150 unsigned int* histogram
= XCNEWVEC (unsigned int, m_items
.length () + 1);
2152 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2153 it
!= m_classes
.end (); ++it
)
2155 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2157 unsigned int c
= (*it
)->classes
[i
]->members
.length ();
2165 "Class size histogram [num of members]: number of classe number of classess\n");
2167 for (unsigned int i
= 0; i
<= max_index
; i
++)
2169 fprintf (dump_file
, "[%u]: %u classes\n", i
, histogram
[i
]);
2171 fprintf (dump_file
, "\n\n");
2174 if (dump_flags
& TDF_DETAILS
)
2175 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2176 it
!= m_classes
.end (); ++it
)
2178 fprintf (dump_file
, " group: with %u classes:\n", (*it
)->classes
.length ());
2180 for (unsigned i
= 0; i
< (*it
)->classes
.length (); i
++)
2182 (*it
)->classes
[i
]->dump (dump_file
, 4);
2184 if(i
< (*it
)->classes
.length () - 1)
2185 fprintf (dump_file
, " ");
2192 /* After reduction is done, we can declare all items in a group
2193 to be equal. PREV_CLASS_COUNT is start number of classes
2194 before reduction. */
2197 sem_item_optimizer::merge_classes (unsigned int prev_class_count
)
2199 unsigned int item_count
= m_items
.length ();
2200 unsigned int class_count
= m_classes_count
;
2201 unsigned int equal_items
= item_count
- class_count
;
2203 unsigned int non_singular_classes_count
= 0;
2204 unsigned int non_singular_classes_sum
= 0;
2206 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2207 it
!= m_classes
.end (); ++it
)
2208 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2210 congruence_class
*c
= (*it
)->classes
[i
];
2211 if (c
->members
.length () > 1)
2213 non_singular_classes_count
++;
2214 non_singular_classes_sum
+= c
->members
.length ();
2220 fprintf (dump_file
, "\nItem count: %u\n", item_count
);
2221 fprintf (dump_file
, "Congruent classes before: %u, after: %u\n",
2222 prev_class_count
, class_count
);
2223 fprintf (dump_file
, "Average class size before: %.2f, after: %.2f\n",
2224 prev_class_count
? 1.0f
* item_count
/ prev_class_count
: 0.0f
,
2225 class_count
? 1.0f
* item_count
/ class_count
: 0.0f
);
2226 fprintf (dump_file
, "Average non-singular class size: %.2f, count: %u\n",
2227 non_singular_classes_count
? 1.0f
* non_singular_classes_sum
/
2228 non_singular_classes_count
: 0.0f
,
2229 non_singular_classes_count
);
2230 fprintf (dump_file
, "Equal symbols: %u\n", equal_items
);
2231 fprintf (dump_file
, "Fraction of visited symbols: %.2f%%\n\n",
2232 item_count
? 100.0f
* equal_items
/ item_count
: 0.0f
);
2235 for (hash_table
<congruence_class_group_hash
>::iterator it
= m_classes
.begin ();
2236 it
!= m_classes
.end (); ++it
)
2237 for (unsigned int i
= 0; i
< (*it
)->classes
.length (); i
++)
2239 congruence_class
*c
= (*it
)->classes
[i
];
2241 if (c
->members
.length () == 1)
2244 gcc_assert (c
->members
.length ());
2246 sem_item
*source
= c
->members
[0];
2248 for (unsigned int j
= 1; j
< c
->members
.length (); j
++)
2250 sem_item
*alias
= c
->members
[j
];
2251 source
->equals (alias
, m_symtab_node_map
);
2255 fprintf (dump_file
, "Semantic equality hit:%s->%s\n",
2256 source
->name (), alias
->name ());
2257 fprintf (dump_file
, "Assembler symbol names:%s->%s\n",
2258 source
->asm_name (), alias
->asm_name ());
2261 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2263 source
->dump_to_file (dump_file
);
2264 alias
->dump_to_file (dump_file
);
2267 source
->merge (alias
);
2272 /* Dump function prints all class members to a FILE with an INDENT. */
2275 congruence_class::dump (FILE *file
, unsigned int indent
) const
2277 FPRINTF_SPACES (file
, indent
, "class with id: %u, hash: %u, items: %u\n",
2278 id
, members
[0]->get_hash (), members
.length ());
2280 FPUTS_SPACES (file
, indent
+ 2, "");
2281 for (unsigned i
= 0; i
< members
.length (); i
++)
2282 fprintf (file
, "%s(%p/%u) ", members
[i
]->asm_name (), (void *) members
[i
]->decl
,
2283 members
[i
]->node
->order
);
2285 fprintf (file
, "\n");
2288 /* Returns true if there's a member that is used from another group. */
2291 congruence_class::is_class_used (void)
2293 for (unsigned int i
= 0; i
< members
.length (); i
++)
2294 if (members
[i
]->usages
.length ())
2300 /* Initialization and computation of symtab node hash, there data
2301 are propagated later on. */
2303 static sem_item_optimizer
*optimizer
= NULL
;
2305 /* Generate pass summary for IPA ICF pass. */
2308 ipa_icf_generate_summary (void)
2311 optimizer
= new sem_item_optimizer ();
2313 optimizer
->parse_funcs_and_vars ();
2316 /* Write pass summary for IPA ICF pass. */
2319 ipa_icf_write_summary (void)
2321 gcc_assert (optimizer
);
2323 optimizer
->write_summary ();
2326 /* Read pass summary for IPA ICF pass. */
2329 ipa_icf_read_summary (void)
2332 optimizer
= new sem_item_optimizer ();
2334 optimizer
->read_summary ();
2335 optimizer
->register_hooks ();
2338 /* Semantic equality exection function. */
2341 ipa_icf_driver (void)
2343 gcc_assert (optimizer
);
2345 optimizer
->execute ();
2346 optimizer
->unregister_hooks ();
2354 const pass_data pass_data_ipa_icf
=
2356 IPA_PASS
, /* type */
2358 OPTGROUP_IPA
, /* optinfo_flags */
2359 TV_IPA_ICF
, /* tv_id */
2360 0, /* properties_required */
2361 0, /* properties_provided */
2362 0, /* properties_destroyed */
2363 0, /* todo_flags_start */
2364 0, /* todo_flags_finish */
2367 class pass_ipa_icf
: public ipa_opt_pass_d
2370 pass_ipa_icf (gcc::context
*ctxt
)
2371 : ipa_opt_pass_d (pass_data_ipa_icf
, ctxt
,
2372 ipa_icf_generate_summary
, /* generate_summary */
2373 ipa_icf_write_summary
, /* write_summary */
2374 ipa_icf_read_summary
, /* read_summary */
2376 write_optimization_summary */
2378 read_optimization_summary */
2379 NULL
, /* stmt_fixup */
2380 0, /* function_transform_todo_flags_start */
2381 NULL
, /* function_transform */
2382 NULL
) /* variable_transform */
2385 /* opt_pass methods: */
2386 virtual bool gate (function
*)
2388 return flag_ipa_icf_variables
|| flag_ipa_icf_functions
;
2391 virtual unsigned int execute (function
*)
2393 return ipa_icf_driver();
2395 }; // class pass_ipa_icf
2397 } // ipa_icf namespace
2400 make_pass_ipa_icf (gcc::context
*ctxt
)
2402 return new ipa_icf::pass_ipa_icf (ctxt
);