1 /* Basic IPA utilities for type inheritance graph construction and
3 Copyright (C) 2013 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
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/>. */
23 ODR = One Definition Rule
24 In short, the ODR states that:
25 1 In any translation unit, a template, type, function, or object can
26 have no more than one definition. Some of these can have any number
27 of declarations. A definition provides an instance.
28 2 In the entire program, an object or non-inline function cannot have
29 more than one definition; if an object or function is used, it must
30 have exactly one definition. You can declare an object or function
31 that is never used, in which case you don't have to provide
32 a definition. In no event can there be more than one definition.
33 3 Some things, like types, templates, and extern inline functions, can
34 be defined in more than one translation unit. For a given entity,
35 each definition must be the same. Non-extern objects and functions
36 in different translation units are different entities, even if their
37 names and types are the same.
40 This is the Gimple representation of type information of a polymorphic call.
41 It contains two parameters:
42 otr_type is a type of class whose method is called.
43 otr_token is the index into virtual table where address is taken.
46 This is the type inheritance information attached to each tree
47 RECORD_TYPE by the C++ frotend. It provides information about base
48 types and virtual tables.
50 BINFO is linked to the RECORD_TYPE by TYPE_BINFO.
51 BINFO also links to its type by BINFO_TYPE and to the virtual table by
54 Base types of a given type are enumerated by BINFO_BASE_BINFO
55 vector. Members of this vectors are not BINFOs associated
56 with a base type. Rather they are new copies of BINFOs
57 (base BINFOs). Their virtual tables may differ from
58 virtual table of the base type. Also BINFO_OFFSET specifies
59 offset of the base within the type.
61 In the case of single inheritance, the virtual table is shared
62 and BINFO_VTABLE of base BINFO is NULL. In the case of multiple
63 inheritance the individual virtual tables are pointer to by
64 BINFO_VTABLE of base binfos (that differs of BINFO_VTABLE of
65 binfo associated to the base type).
67 BINFO lookup for a given base type and offset can be done by
68 get_binfo_at_offset. It returns proper BINFO whose virtual table
69 can be used for lookup of virtual methods associated with the
73 This is an index of virtual method in virtual table associated
74 to the type defining it. Token can be looked up from OBJ_TYPE_REF
75 or from DECL_VINDEX of a given virtual table.
77 polymorphic (indirect) call
78 This is callgraph represention of virtual method call. Every
79 polymorphic call contains otr_type and otr_token taken from
80 original OBJ_TYPE_REF at callgraph construction time.
84 build_type_inheritance_graph triggers a construction of the type inheritance
87 We reconstruct it based on types of methods we see in the unit.
88 This means that the graph is not complete. Types with no methods are not
89 inserted into the graph. Also types without virtual methods are not
90 represented at all, though it may be easy to add this.
92 The inheritance graph is represented as follows:
94 Vertices are structures odr_type. Every odr_type may correspond
95 to one or more tree type nodes that are equivalent by ODR rule.
96 (the multiple type nodes appear only with linktime optimization)
98 Edges are represented by odr_type->base and odr_type->derived_types.
99 At the moment we do not track offsets of types for multiple inheritance.
102 possible_polymorphic_call_targets returns, given an parameters found in
103 indirect polymorphic edge all possible polymorphic call targets of the call.
105 pass_ipa_devirt performs simple speculative devirtualization.
110 #include "coretypes.h"
113 #include "tree-pass.h"
115 #include "pointer-set.h"
117 #include "hash-table.h"
118 #include "tree-pretty-print.h"
119 #include "ipa-utils.h"
121 #include "ipa-inline.h"
122 #include "diagnostic.h"
124 /* Pointer set of all call targets appearing in the cache. */
125 static pointer_set_t
*cached_polymorphic_call_targets
;
127 /* The node of type inheritance graph. For each type unique in
128 One Defintion Rule (ODR) sense, we produce one node linking all
129 main variants of types equivalent to it, bases and derived types. */
131 struct GTY(()) odr_type_d
136 vec
<odr_type
> GTY((skip
)) bases
;
137 /* All derrived types with virtual methods seen in unit. */
138 vec
<odr_type
> GTY((skip
)) derived_types
;
140 /* All equivalent types, if more than one. */
141 vec
<tree
, va_gc
> *types
;
142 /* Set of all equivalent types, if NON-NULL. */
143 pointer_set_t
* GTY((skip
)) types_set
;
145 /* Unique ID indexing the type in odr_types array. */
147 /* Is it in anonymous namespace? */
148 bool anonymous_namespace
;
152 /* Return true if BINFO corresponds to a type with virtual methods.
154 Every type has several BINFOs. One is the BINFO associated by the type
155 while other represents bases of derived types. The BINFOs representing
156 bases do not have BINFO_VTABLE pointer set when this is the single
157 inheritance (because vtables are shared). Look up the BINFO of type
158 and check presence of its vtable. */
161 polymorphic_type_binfo_p (tree binfo
)
163 /* See if BINFO's type has an virtual table associtated with it. */
164 return BINFO_VTABLE (TYPE_BINFO (BINFO_TYPE (binfo
)));
167 /* One Definition Rule hashtable helpers. */
171 typedef odr_type_d value_type
;
172 typedef union tree_node compare_type
;
173 static inline hashval_t
hash (const value_type
*);
174 static inline bool equal (const value_type
*, const compare_type
*);
175 static inline void remove (value_type
*);
178 /* Produce hash based on type name. */
181 hash_type_name (tree t
)
183 gcc_checking_assert (TYPE_MAIN_VARIANT (t
) == t
);
185 /* If not in LTO, all main variants are unique, so we can do
188 return htab_hash_pointer (t
);
190 /* Anonymous types are unique. */
191 if (type_in_anonymous_namespace_p (t
))
192 return htab_hash_pointer (t
);
194 /* For polymorphic types, we can simply hash the virtual table. */
195 if (TYPE_BINFO (t
) && BINFO_VTABLE (TYPE_BINFO (t
)))
197 tree v
= BINFO_VTABLE (TYPE_BINFO (t
));
200 if (TREE_CODE (v
) == POINTER_PLUS_EXPR
)
202 hash
= TREE_INT_CST_LOW (TREE_OPERAND (v
, 1));
203 v
= TREE_OPERAND (TREE_OPERAND (v
, 0), 0);
206 v
= DECL_ASSEMBLER_NAME (v
);
207 hash
= iterative_hash_hashval_t (hash
, htab_hash_pointer (v
));
211 /* Rest is not implemented yet. */
215 /* Return the computed hashcode for ODR_TYPE. */
218 odr_hasher::hash (const value_type
*odr_type
)
220 return hash_type_name (odr_type
->type
);
223 /* Compare types T1 and T2 and return true if they are
227 odr_hasher::equal (const value_type
*t1
, const compare_type
*ct2
)
229 tree t2
= const_cast <tree
> (ct2
);
231 gcc_checking_assert (TYPE_MAIN_VARIANT (ct2
) == ct2
);
236 return types_same_for_odr (t1
->type
, t2
);
239 /* Free ODR type V. */
242 odr_hasher::remove (value_type
*v
)
245 v
->derived_types
.release ();
247 pointer_set_destroy (v
->types_set
);
251 /* ODR type hash used to lookup ODR type based on tree type node. */
253 typedef hash_table
<odr_hasher
> odr_hash_type
;
254 static odr_hash_type odr_hash
;
256 /* ODR types are also stored into ODR_TYPE vector to allow consistent
257 walking. Bases appear before derived types. Vector is garbage collected
258 so we won't end up visiting empty types. */
260 static GTY(()) vec
<odr_type
, va_gc
> *odr_types_ptr
;
261 #define odr_types (*odr_types_ptr)
263 /* TYPE is equivalent to VAL by ODR, but its tree representation differs
264 from VAL->type. This may happen in LTO where tree merging did not merge
265 all variants of the same type. It may or may not mean the ODR violation.
266 Add it to the list of duplicates and warn on some violations. */
269 add_type_duplicate (odr_type val
, tree type
)
272 val
->types_set
= pointer_set_create ();
274 /* See if this duplicate is new. */
275 if (!pointer_set_insert (val
->types_set
, type
))
278 bool base_mismatch
= false;
279 gcc_assert (in_lto_p
);
280 vec_safe_push (val
->types
, type
);
283 /* First we compare memory layout. */
284 if (!types_compatible_p (val
->type
, type
))
287 if (BINFO_VTABLE (TYPE_BINFO (val
->type
))
288 && warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (type
)), 0,
289 "type %qD violates one definition rule ",
291 inform (DECL_SOURCE_LOCATION (TYPE_NAME (val
->type
)),
292 "a type with the same name but different layout is "
293 "defined in another translation unit");
294 debug_tree (BINFO_VTABLE (TYPE_BINFO (type
)));
295 debug_tree (BINFO_VTABLE (TYPE_BINFO (val
->type
)));
296 if (cgraph_dump_file
)
298 fprintf (cgraph_dump_file
, "ODR violation or merging or ODR type bug?\n");
300 print_node (cgraph_dump_file
, "", val
->type
, 0);
301 putc ('\n',cgraph_dump_file
);
302 print_node (cgraph_dump_file
, "", type
, 0);
303 putc ('\n',cgraph_dump_file
);
307 /* Next sanity check that bases are the same. If not, we will end
308 up producing wrong answers. */
309 for (j
= 0, i
= 0; i
< BINFO_N_BASE_BINFOS (TYPE_BINFO (type
)); i
++)
310 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (TYPE_BINFO (type
), i
)))
312 odr_type base
= get_odr_type
314 (BINFO_BASE_BINFO (TYPE_BINFO (type
),
317 if (val
->bases
.length () <= j
|| val
->bases
[j
] != base
)
318 base_mismatch
= true;
325 if (warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (type
)), 0,
326 "type %qD violates one definition rule ",
328 inform (DECL_SOURCE_LOCATION (TYPE_NAME (val
->type
)),
329 "a type with the same name but different bases is "
330 "defined in another translation unit");
331 if (cgraph_dump_file
)
333 fprintf (cgraph_dump_file
, "ODR bse violation or merging bug?\n");
335 print_node (cgraph_dump_file
, "", val
->type
, 0);
336 putc ('\n',cgraph_dump_file
);
337 print_node (cgraph_dump_file
, "", type
, 0);
338 putc ('\n',cgraph_dump_file
);
342 /* Regularize things a little. During LTO same types may come with
343 different BINFOs. Either because their virtual table was
344 not merged by tree merging and only later at decl merging or
345 because one type comes with external vtable, while other
346 with internal. We want to merge equivalent binfos to conserve
347 memory and streaming overhead.
349 The external vtables are more harmful: they contain references
350 to external declarations of methods that may be defined in the
351 merged LTO unit. For this reason we absolutely need to remove
352 them and replace by internal variants. Not doing so will lead
353 to incomplete answers from possible_polymorphic_call_targets. */
354 if (!flag_ltrans
&& merge
)
356 tree master_binfo
= TYPE_BINFO (val
->type
);
357 tree v1
= BINFO_VTABLE (master_binfo
);
358 tree v2
= BINFO_VTABLE (TYPE_BINFO (type
));
360 if (TREE_CODE (v1
) == POINTER_PLUS_EXPR
)
362 gcc_assert (TREE_CODE (v2
) == POINTER_PLUS_EXPR
363 && operand_equal_p (TREE_OPERAND (v1
, 1),
364 TREE_OPERAND (v2
, 1), 0));
365 v1
= TREE_OPERAND (TREE_OPERAND (v1
, 0), 0);
366 v2
= TREE_OPERAND (TREE_OPERAND (v2
, 0), 0);
368 gcc_assert (DECL_ASSEMBLER_NAME (v1
)
369 == DECL_ASSEMBLER_NAME (v2
));
371 if (DECL_EXTERNAL (v1
) && !DECL_EXTERNAL (v2
))
375 TYPE_BINFO (val
->type
) = TYPE_BINFO (type
);
376 for (i
= 0; i
< val
->types
->length(); i
++)
378 if (TYPE_BINFO ((*val
->types
)[i
])
380 TYPE_BINFO ((*val
->types
)[i
]) = TYPE_BINFO (type
);
384 TYPE_BINFO (type
) = master_binfo
;
389 /* Get ODR type hash entry for TYPE. If INSERT is true, create
390 possibly new entry. */
393 get_odr_type (tree type
, bool insert
)
399 type
= TYPE_MAIN_VARIANT (type
);
400 gcc_checking_assert (TYPE_MAIN_VARIANT (type
) == type
);
401 hash
= hash_type_name (type
);
402 slot
= odr_hash
.find_slot_with_hash (type
, hash
, insert
? INSERT
: NO_INSERT
);
406 /* See if we already have entry for type. */
411 /* With LTO we need to support multiple tree representation of
412 the same ODR type. */
413 if (val
->type
!= type
)
414 add_type_duplicate (val
, type
);
418 tree binfo
= TYPE_BINFO (type
);
421 val
= ggc_alloc_cleared_odr_type_d ();
424 val
->derived_types
= vNULL
;
425 val
->anonymous_namespace
= type_in_anonymous_namespace_p (type
);
427 for (i
= 0; i
< BINFO_N_BASE_BINFOS (binfo
); i
++)
428 /* For now record only polymorphic types. other are
429 pointless for devirtualization and we can not precisely
430 determine ODR equivalency of these during LTO. */
431 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (binfo
, i
)))
433 odr_type base
= get_odr_type (BINFO_TYPE (BINFO_BASE_BINFO (binfo
,
436 base
->derived_types
.safe_push (val
);
437 val
->bases
.safe_push (base
);
439 /* First record bases, then add into array so ids are increasing. */
441 val
->id
= odr_types
.length();
442 vec_safe_push (odr_types_ptr
, val
);
447 /* Dump ODR type T and all its derrived type. INDENT specify indentation for
448 recusive printing. */
451 dump_odr_type (FILE *f
, odr_type t
, int indent
=0)
454 fprintf (f
, "%*s type %i: ", indent
* 2, "", t
->id
);
455 print_generic_expr (f
, t
->type
, TDF_SLIM
);
456 fprintf (f
, "%s\n", t
->anonymous_namespace
? " (anonymous namespace)":"");
457 if (TYPE_NAME (t
->type
))
459 fprintf (f
, "%*s defined at: %s:%i\n", indent
* 2, "",
460 DECL_SOURCE_FILE (TYPE_NAME (t
->type
)),
461 DECL_SOURCE_LINE (TYPE_NAME (t
->type
)));
463 if (t
->bases
.length())
465 fprintf (f
, "%*s base odr type ids: ", indent
* 2, "");
466 for (i
= 0; i
< t
->bases
.length(); i
++)
467 fprintf (f
, " %i", t
->bases
[i
]->id
);
470 if (t
->derived_types
.length())
472 fprintf (f
, "%*s derived types:\n", indent
* 2, "");
473 for (i
= 0; i
< t
->derived_types
.length(); i
++)
474 dump_odr_type (f
, t
->derived_types
[i
], indent
+ 1);
479 /* Dump the type inheritance graph. */
482 dump_type_inheritance_graph (FILE *f
)
487 fprintf (f
, "\n\nType inheritance graph:\n");
488 for (i
= 0; i
< odr_types
.length(); i
++)
490 if (odr_types
[i
]->bases
.length() == 0)
491 dump_odr_type (f
, odr_types
[i
]);
493 for (i
= 0; i
< odr_types
.length(); i
++)
495 if (odr_types
[i
]->types
&& odr_types
[i
]->types
->length())
498 fprintf (f
, "Duplicate tree types for odr type %i\n", i
);
499 print_node (f
, "", odr_types
[i
]->type
, 0);
500 for (j
= 0; j
< odr_types
[i
]->types
->length(); j
++)
503 fprintf (f
, "duplicate #%i\n", j
);
504 print_node (f
, "", (*odr_types
[i
]->types
)[j
], 0);
505 t
= (*odr_types
[i
]->types
)[j
];
506 while (TYPE_P (t
) && TYPE_CONTEXT (t
))
508 t
= TYPE_CONTEXT (t
);
509 print_node (f
, "", t
, 0);
517 /* Given method type T, return type of class it belongs to.
518 Lookup this pointer and get its type. */
521 method_class_type (tree t
)
523 tree first_parm_type
= TREE_VALUE (TYPE_ARG_TYPES (t
));
525 return TREE_TYPE (first_parm_type
);
528 /* Initialize IPA devirt and build inheritance tree graph. */
531 build_type_inheritance_graph (void)
533 struct cgraph_node
*n
;
534 FILE *inheritance_dump_file
;
537 if (odr_hash
.is_created ())
539 timevar_push (TV_IPA_INHERITANCE
);
540 inheritance_dump_file
= dump_begin (TDI_inheritance
, &flags
);
541 odr_hash
.create (23);
543 /* We reconstruct the graph starting of types of all methods seen in the
545 FOR_EACH_FUNCTION (n
)
546 if (DECL_VIRTUAL_P (n
->symbol
.decl
)
547 && symtab_real_symbol_p ((symtab_node
)n
))
548 get_odr_type (method_class_type (TREE_TYPE (n
->symbol
.decl
)), true);
549 if (inheritance_dump_file
)
551 dump_type_inheritance_graph (inheritance_dump_file
);
552 dump_end (TDI_inheritance
, inheritance_dump_file
);
554 timevar_pop (TV_IPA_INHERITANCE
);
557 /* If TARGET has associated node, record it in the NODES array. */
560 maybe_record_node (vec
<cgraph_node
*> &nodes
,
561 tree target
, pointer_set_t
*inserted
)
563 struct cgraph_node
*target_node
;
564 enum built_in_function fcode
;
567 /* Those are used to mark impossible scenarios. */
568 && (fcode
= DECL_FUNCTION_CODE (target
))
569 != BUILT_IN_UNREACHABLE
570 && fcode
!= BUILT_IN_TRAP
571 && !pointer_set_insert (inserted
, target
)
572 && (target_node
= cgraph_get_node (target
)) != NULL
573 && symtab_real_symbol_p ((symtab_node
)target_node
))
575 pointer_set_insert (cached_polymorphic_call_targets
,
577 nodes
.safe_push (target_node
);
581 /* See if BINFO's type match OTR_TYPE. If so, lookup method
582 in vtable of TYPE_BINFO and insert method to NODES array.
583 Otherwise recurse to base BINFOs.
584 This match what get_binfo_at_offset does, but with offset
587 TYPE_BINFO is binfo holding an virtual table matching
588 BINFO's type. In the case of single inheritance, this
589 is binfo of BINFO's type ancestor (vtable is shared),
590 otherwise it is binfo of BINFO's type.
592 MATCHED_VTABLES tracks virtual tables we already did lookup
593 for virtual function in.
597 record_binfo (vec
<cgraph_node
*> &nodes
,
601 HOST_WIDE_INT otr_token
,
602 pointer_set_t
*inserted
,
603 pointer_set_t
*matched_vtables
)
605 tree type
= BINFO_TYPE (binfo
);
609 gcc_checking_assert (BINFO_VTABLE (type_binfo
));
611 if (types_same_for_odr (type
, otr_type
)
612 && !pointer_set_insert (matched_vtables
, BINFO_VTABLE (type_binfo
)))
614 tree target
= gimple_get_virt_method_for_binfo (otr_token
, type_binfo
);
616 maybe_record_node (nodes
, target
, inserted
);
621 for (i
= 0; BINFO_BASE_ITERATE (binfo
, i
, base_binfo
); i
++)
622 /* Walking bases that have no virtual method is pointless excercise. */
623 if (polymorphic_type_binfo_p (base_binfo
))
624 record_binfo (nodes
, base_binfo
, otr_type
,
625 /* In the case of single inheritance, the virtual table
626 is shared with the outer type. */
627 BINFO_VTABLE (base_binfo
) ? base_binfo
: type_binfo
,
632 /* Lookup virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN)
633 of TYPE, insert them to NODES, recurse into derived nodes.
634 INSERTED is used to avoid duplicate insertions of methods into NODES.
635 MATCHED_VTABLES are used to avoid duplicate walking vtables. */
638 possible_polymorphic_call_targets_1 (vec
<cgraph_node
*> &nodes
,
639 pointer_set_t
*inserted
,
640 pointer_set_t
*matched_vtables
,
643 HOST_WIDE_INT otr_token
)
645 tree binfo
= TYPE_BINFO (type
->type
);
648 record_binfo (nodes
, binfo
, otr_type
, binfo
, otr_token
, inserted
,
650 for (i
= 0; i
< type
->derived_types
.length(); i
++)
651 possible_polymorphic_call_targets_1 (nodes
, inserted
,
654 type
->derived_types
[i
],
658 /* Cache of queries for polymorphic call targets.
660 Enumerating all call targets may get expensive when there are many
661 polymorphic calls in the program, so we memoize all the previous
662 queries and avoid duplicated work. */
664 struct polymorphic_call_target_d
667 HOST_WIDE_INT otr_token
;
668 vec
<cgraph_node
*> targets
;
671 /* Polymorphic call target cache helpers. */
673 struct polymorphic_call_target_hasher
675 typedef polymorphic_call_target_d value_type
;
676 typedef polymorphic_call_target_d compare_type
;
677 static inline hashval_t
hash (const value_type
*);
678 static inline bool equal (const value_type
*, const compare_type
*);
679 static inline void remove (value_type
*);
682 /* Return the computed hashcode for ODR_QUERY. */
685 polymorphic_call_target_hasher::hash (const value_type
*odr_query
)
687 return iterative_hash_hashval_t (odr_query
->type
->id
,
688 odr_query
->otr_token
);
691 /* Compare cache entries T1 and T2. */
694 polymorphic_call_target_hasher::equal (const value_type
*t1
,
695 const compare_type
*t2
)
697 return t1
->type
== t2
->type
&& t1
->otr_token
== t2
->otr_token
;
700 /* Remove entry in polymorphic call target cache hash. */
703 polymorphic_call_target_hasher::remove (value_type
*v
)
705 v
->targets
.release ();
709 /* Polymorphic call target query cache. */
711 typedef hash_table
<polymorphic_call_target_hasher
>
712 polymorphic_call_target_hash_type
;
713 static polymorphic_call_target_hash_type polymorphic_call_target_hash
;
715 /* Destroy polymorphic call target query cache. */
718 free_polymorphic_call_targets_hash ()
720 if (cached_polymorphic_call_targets
)
722 polymorphic_call_target_hash
.dispose ();
723 pointer_set_destroy (cached_polymorphic_call_targets
);
724 cached_polymorphic_call_targets
= NULL
;
728 /* When virtual function is removed, we may need to flush the cache. */
731 devirt_node_removal_hook (struct cgraph_node
*n
, void *d ATTRIBUTE_UNUSED
)
733 if (cached_polymorphic_call_targets
734 && pointer_set_contains (cached_polymorphic_call_targets
, n
))
735 free_polymorphic_call_targets_hash ();
738 /* Return vector containing possible targets of polymorphic call of type
739 OTR_TYPE caling method OTR_TOKEN with OFFSET. If FINALp is non-NULL,
740 store true if the list is complette.
741 CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
742 in the target cache. If user needs to visit every target list
743 just once, it can memoize them.
745 Returned vector is placed into cache. It is NOT caller's responsibility
746 to free it. The vector can be freed on cgraph_remove_node call if
747 the particular node is a virtual function present in the cache. */
750 possible_polymorphic_call_targets (tree otr_type
,
751 HOST_WIDE_INT otr_token
,
755 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
756 pointer_set_t
*inserted
;
757 pointer_set_t
*matched_vtables
;
758 vec
<cgraph_node
*> nodes
=vNULL
;
760 polymorphic_call_target_d key
;
761 polymorphic_call_target_d
**slot
;
768 type
= get_odr_type (otr_type
, false);
769 /* If we do not have type in our hash it means we never seen any method
774 /* For anonymous namespace types we can attempt to build full type.
775 All derivations must be in this unit. */
776 if (type
->anonymous_namespace
&& finalp
&& !flag_ltrans
)
779 /* Initialize query cache. */
780 if (!cached_polymorphic_call_targets
)
782 cached_polymorphic_call_targets
= pointer_set_create ();
783 polymorphic_call_target_hash
.create (23);
784 if (!node_removal_hook_holder
)
785 node_removal_hook_holder
=
786 cgraph_add_node_removal_hook (&devirt_node_removal_hook
, NULL
);
789 /* Lookup cached answer. */
791 key
.otr_token
= otr_token
;
792 slot
= polymorphic_call_target_hash
.find_slot (&key
, INSERT
);
794 *cache_token
= (void *)*slot
;
796 return (*slot
)->targets
;
798 /* Do actual search. */
799 timevar_push (TV_IPA_VIRTUAL_CALL
);
800 *slot
= XCNEW (polymorphic_call_target_d
);
802 *cache_token
= (void *)*slot
;
803 (*slot
)->type
= type
;
804 (*slot
)->otr_token
= otr_token
;
806 inserted
= pointer_set_create ();
807 matched_vtables
= pointer_set_create ();
809 /* First see virtual method of type itself. */
811 binfo
= TYPE_BINFO (type
->type
);
812 target
= gimple_get_virt_method_for_binfo (otr_token
, binfo
);
814 maybe_record_node (nodes
, target
, inserted
);
815 pointer_set_insert (matched_vtables
, BINFO_VTABLE (binfo
));
817 /* TODO: If method is final, we can stop here and signaize that
818 list is final. We need C++ FE to pass our info about final
819 methods and classes. */
821 /* Walk recursively all derived types. Here we need to lookup proper basetype
822 via their BINFO walk that is done by record_binfo */
823 for (i
= 0; i
< type
->derived_types
.length(); i
++)
824 possible_polymorphic_call_targets_1 (nodes
, inserted
,
826 otr_type
, type
->derived_types
[i
],
828 (*slot
)->targets
= nodes
;
830 pointer_set_destroy (inserted
);
831 pointer_set_destroy (matched_vtables
);
832 timevar_pop (TV_IPA_VIRTUAL_CALL
);
836 /* Dump all possible targets of a polymorphic call. */
839 dump_possible_polymorphic_call_targets (FILE *f
,
841 HOST_WIDE_INT otr_token
)
843 vec
<cgraph_node
*> targets
;
845 odr_type type
= get_odr_type (otr_type
, false);
850 targets
= possible_polymorphic_call_targets (otr_type
, otr_token
,
852 fprintf (f
, "Targets of polymorphic call of type %i ", type
->id
);
853 print_generic_expr (f
, type
->type
, TDF_SLIM
);
854 fprintf (f
, " token %i%s:",
856 final
? " (full list)" : " (partial list, may call to other unit)");
857 for (i
= 0; i
< targets
.length (); i
++)
858 fprintf (f
, " %s/%i", cgraph_node_name (targets
[i
]),
859 targets
[i
]->symbol
.order
);
864 /* Return true if N can be possibly target of a polymorphic call of
865 OTR_TYPE/OTR_TOKEN. */
868 possible_polymorphic_call_target_p (tree otr_type
,
869 HOST_WIDE_INT otr_token
,
870 struct cgraph_node
*n
)
872 vec
<cgraph_node
*> targets
;
875 if (!odr_hash
.is_created ())
877 targets
= possible_polymorphic_call_targets (otr_type
, otr_token
);
878 for (i
= 0; i
< targets
.length (); i
++)
885 /* After callgraph construction new external nodes may appear.
886 Add them into the graph. */
889 update_type_inheritance_graph (void)
891 struct cgraph_node
*n
;
893 if (!odr_hash
.is_created ())
895 free_polymorphic_call_targets_hash ();
896 timevar_push (TV_IPA_INHERITANCE
);
897 /* We reconstruct the graph starting of types of all methods seen in the
899 FOR_EACH_FUNCTION (n
)
900 if (DECL_VIRTUAL_P (n
->symbol
.decl
)
901 && !n
->symbol
.definition
902 && symtab_real_symbol_p ((symtab_node
)n
))
903 get_odr_type (method_class_type (TREE_TYPE (n
->symbol
.decl
)), true);
904 timevar_pop (TV_IPA_INHERITANCE
);
908 /* Return true if N looks like likely target of a polymorphic call.
909 Rule out cxa_pure_virtual, noreturns, function declared cold and
910 other obvious cases. */
913 likely_target_p (struct cgraph_node
*n
)
916 /* cxa_pure_virtual and similar things are not likely. */
917 if (TREE_CODE (TREE_TYPE (n
->symbol
.decl
)) != METHOD_TYPE
)
919 flags
= flags_from_decl_or_type (n
->symbol
.decl
);
920 if (flags
& ECF_NORETURN
)
922 if (lookup_attribute ("cold",
923 DECL_ATTRIBUTES (n
->symbol
.decl
)))
925 if (n
->frequency
< NODE_FREQUENCY_NORMAL
)
930 /* The ipa-devirt pass.
931 This performs very trivial devirtualization:
932 1) when polymorphic call is known to have precisely one target,
933 turn it into direct call
934 2) when polymorphic call has only one likely target in the unit,
935 turn it into speculative call. */
940 struct cgraph_node
*n
;
941 struct pointer_set_t
*bad_call_targets
= pointer_set_create ();
942 struct cgraph_edge
*e
;
944 int npolymorphic
= 0, nspeculated
= 0, nconverted
= 0, ncold
= 0;
945 int nmultiple
= 0, noverwritable
= 0, ndevirtualized
= 0, nnotdefined
= 0;
946 int nwrong
= 0, nok
= 0, nexternal
= 0;;
948 FOR_EACH_DEFINED_FUNCTION (n
)
951 if (dump_file
&& n
->indirect_calls
)
952 fprintf (dump_file
, "\n\nProcesing function %s/%i\n",
953 cgraph_node_name (n
), n
->symbol
.order
);
954 for (e
= n
->indirect_calls
; e
; e
= e
->next_callee
)
955 if (e
->indirect_info
->polymorphic
)
957 struct cgraph_node
*likely_target
= NULL
;
960 vec
<cgraph_node
*>targets
961 = possible_polymorphic_call_targets
962 (e
, &final
, &cache_token
);
966 dump_possible_polymorphic_call_targets
972 gcc_assert (targets
.length());
973 if (targets
.length() == 1)
977 "Devirtualizing call in %s/%i to %s/%i\n",
978 cgraph_node_name (n
), n
->symbol
.order
,
979 cgraph_node_name (targets
[0]), targets
[0]->symbol
.order
);
980 cgraph_make_edge_direct (e
, targets
[0]);
986 if (!flag_devirtualize_speculatively
)
988 if (!cgraph_maybe_hot_edge_p (e
))
991 fprintf (dump_file
, "Call is cold\n");
998 fprintf (dump_file
, "Call is aready speculated\n");
1001 /* When dumping see if we agree with speculation. */
1005 if (pointer_set_contains (bad_call_targets
,
1009 fprintf (dump_file
, "Target list is known to be useless\n");
1013 for (i
= 0; i
< targets
.length(); i
++)
1014 if (likely_target_p (targets
[i
]))
1018 likely_target
= NULL
;
1020 fprintf (dump_file
, "More than one likely target\n");
1024 likely_target
= targets
[i
];
1028 pointer_set_insert (bad_call_targets
, cache_token
);
1031 /* This is reached only when dumping; check if we agree or disagree
1032 with the speculation. */
1035 struct cgraph_edge
*e2
;
1036 struct ipa_ref
*ref
;
1037 cgraph_speculative_call_info (e
, e2
, e
, ref
);
1038 if (cgraph_function_or_thunk_node (e2
->callee
, NULL
)
1039 == cgraph_function_or_thunk_node (likely_target
, NULL
))
1041 fprintf (dump_file
, "We agree with speculation\n");
1046 fprintf (dump_file
, "We disagree with speculation\n");
1051 if (!likely_target
->symbol
.definition
)
1054 fprintf (dump_file
, "Target is not an definition\n");
1058 /* Do not introduce new references to external symbols. While we
1059 can handle these just well, it is common for programs to
1060 incorrectly with headers defining methods they are linked
1062 if (DECL_EXTERNAL (likely_target
->symbol
.decl
))
1065 fprintf (dump_file
, "Target is external\n");
1069 if (cgraph_function_body_availability (likely_target
)
1070 <= AVAIL_OVERWRITABLE
1071 && symtab_can_be_discarded ((symtab_node
) likely_target
))
1074 fprintf (dump_file
, "Target is overwritable\n");
1082 "Speculatively devirtualizing call in %s/%i to %s/%i\n",
1083 cgraph_node_name (n
), n
->symbol
.order
,
1084 cgraph_node_name (likely_target
),
1085 likely_target
->symbol
.order
);
1086 if (!symtab_can_be_discarded ((symtab_node
) likely_target
))
1087 likely_target
= cgraph (symtab_nonoverwritable_alias ((symtab_node
)likely_target
));
1090 cgraph_turn_edge_to_speculative
1091 (e
, likely_target
, e
->count
* 8 / 10, e
->frequency
* 8 / 10);
1095 inline_update_overall_summary (n
);
1097 pointer_set_destroy (bad_call_targets
);
1101 "%i polymorphic calls, %i devirtualized,"
1102 " %i speculatively devirtualized, %i cold\n"
1103 "%i have multiple targets, %i overwritable,"
1104 " %i already speculated (%i agree, %i disagree),"
1105 " %i external, %i not defined\n",
1106 npolymorphic
, ndevirtualized
, nconverted
, ncold
,
1107 nmultiple
, noverwritable
, nspeculated
, nok
, nwrong
,
1108 nexternal
, nnotdefined
);
1109 return ndevirtualized
? TODO_remove_functions
: 0;
1112 /* Gate for IPCP optimization. */
1115 gate_ipa_devirt (void)
1117 /* FIXME: We should remove the optimize check after we ensure we never run
1118 IPA passes when not optimizing. */
1119 return flag_devirtualize
&& !in_lto_p
;
1124 const pass_data pass_data_ipa_devirt
=
1126 IPA_PASS
, /* type */
1127 "devirt", /* name */
1128 OPTGROUP_NONE
, /* optinfo_flags */
1129 true, /* has_gate */
1130 true, /* has_execute */
1131 TV_IPA_DEVIRT
, /* tv_id */
1132 0, /* properties_required */
1133 0, /* properties_provided */
1134 0, /* properties_destroyed */
1135 0, /* todo_flags_start */
1136 ( TODO_dump_symtab
), /* todo_flags_finish */
1139 class pass_ipa_devirt
: public ipa_opt_pass_d
1142 pass_ipa_devirt(gcc::context
*ctxt
)
1143 : ipa_opt_pass_d(pass_data_ipa_devirt
, ctxt
,
1144 NULL
, /* generate_summary */
1145 NULL
, /* write_summary */
1146 NULL
, /* read_summary */
1147 NULL
, /* write_optimization_summary */
1148 NULL
, /* read_optimization_summary */
1149 NULL
, /* stmt_fixup */
1150 0, /* function_transform_todo_flags_start */
1151 NULL
, /* function_transform */
1152 NULL
) /* variable_transform */
1155 /* opt_pass methods: */
1156 bool gate () { return gate_ipa_devirt (); }
1157 unsigned int execute () { return ipa_devirt (); }
1159 }; // class pass_ipa_devirt
1164 make_pass_ipa_devirt (gcc::context
*ctxt
)
1166 return new pass_ipa_devirt (ctxt
);
1169 #include "gt-ipa-devirt.h"