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 && (TREE_PUBLIC (target
)
574 || target_node
->symbol
.definition
)
575 && symtab_real_symbol_p ((symtab_node
)target_node
))
577 pointer_set_insert (cached_polymorphic_call_targets
,
579 nodes
.safe_push (target_node
);
583 /* See if BINFO's type match OTR_TYPE. If so, lookup method
584 in vtable of TYPE_BINFO and insert method to NODES array.
585 Otherwise recurse to base BINFOs.
586 This match what get_binfo_at_offset does, but with offset
589 TYPE_BINFO is binfo holding an virtual table matching
590 BINFO's type. In the case of single inheritance, this
591 is binfo of BINFO's type ancestor (vtable is shared),
592 otherwise it is binfo of BINFO's type.
594 MATCHED_VTABLES tracks virtual tables we already did lookup
595 for virtual function in.
597 ANONYMOUS is true if BINFO is part of anonymous namespace.
601 record_binfo (vec
<cgraph_node
*> &nodes
,
605 HOST_WIDE_INT otr_token
,
606 pointer_set_t
*inserted
,
607 pointer_set_t
*matched_vtables
,
610 tree type
= BINFO_TYPE (binfo
);
614 gcc_checking_assert (BINFO_VTABLE (type_binfo
));
616 if (types_same_for_odr (type
, otr_type
)
617 && !pointer_set_insert (matched_vtables
, BINFO_VTABLE (type_binfo
)))
619 /* For types in anonymous namespace first check if the respective vtable
620 is alive. If not, we know the type can't be called. */
621 if (!flag_ltrans
&& anonymous
)
623 tree vtable
= BINFO_VTABLE (type_binfo
);
624 struct varpool_node
*vnode
;
626 if (TREE_CODE (vtable
) == POINTER_PLUS_EXPR
)
627 vtable
= TREE_OPERAND (TREE_OPERAND (vtable
, 0), 0);
628 vnode
= varpool_get_node (vtable
);
629 if (!vnode
|| !vnode
->symbol
.definition
)
632 tree target
= gimple_get_virt_method_for_binfo (otr_token
, type_binfo
);
634 maybe_record_node (nodes
, target
, inserted
);
639 for (i
= 0; BINFO_BASE_ITERATE (binfo
, i
, base_binfo
); i
++)
640 /* Walking bases that have no virtual method is pointless excercise. */
641 if (polymorphic_type_binfo_p (base_binfo
))
642 record_binfo (nodes
, base_binfo
, otr_type
,
643 /* In the case of single inheritance, the virtual table
644 is shared with the outer type. */
645 BINFO_VTABLE (base_binfo
) ? base_binfo
: type_binfo
,
647 matched_vtables
, anonymous
);
650 /* Lookup virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN)
651 of TYPE, insert them to NODES, recurse into derived nodes.
652 INSERTED is used to avoid duplicate insertions of methods into NODES.
653 MATCHED_VTABLES are used to avoid duplicate walking vtables. */
656 possible_polymorphic_call_targets_1 (vec
<cgraph_node
*> &nodes
,
657 pointer_set_t
*inserted
,
658 pointer_set_t
*matched_vtables
,
661 HOST_WIDE_INT otr_token
)
663 tree binfo
= TYPE_BINFO (type
->type
);
666 record_binfo (nodes
, binfo
, otr_type
, binfo
, otr_token
, inserted
,
667 matched_vtables
, type
->anonymous_namespace
);
668 for (i
= 0; i
< type
->derived_types
.length (); i
++)
669 possible_polymorphic_call_targets_1 (nodes
, inserted
,
672 type
->derived_types
[i
],
676 /* Cache of queries for polymorphic call targets.
678 Enumerating all call targets may get expensive when there are many
679 polymorphic calls in the program, so we memoize all the previous
680 queries and avoid duplicated work. */
682 struct polymorphic_call_target_d
685 HOST_WIDE_INT otr_token
;
686 vec
<cgraph_node
*> targets
;
689 /* Polymorphic call target cache helpers. */
691 struct polymorphic_call_target_hasher
693 typedef polymorphic_call_target_d value_type
;
694 typedef polymorphic_call_target_d compare_type
;
695 static inline hashval_t
hash (const value_type
*);
696 static inline bool equal (const value_type
*, const compare_type
*);
697 static inline void remove (value_type
*);
700 /* Return the computed hashcode for ODR_QUERY. */
703 polymorphic_call_target_hasher::hash (const value_type
*odr_query
)
705 return iterative_hash_hashval_t (odr_query
->type
->id
,
706 odr_query
->otr_token
);
709 /* Compare cache entries T1 and T2. */
712 polymorphic_call_target_hasher::equal (const value_type
*t1
,
713 const compare_type
*t2
)
715 return t1
->type
== t2
->type
&& t1
->otr_token
== t2
->otr_token
;
718 /* Remove entry in polymorphic call target cache hash. */
721 polymorphic_call_target_hasher::remove (value_type
*v
)
723 v
->targets
.release ();
727 /* Polymorphic call target query cache. */
729 typedef hash_table
<polymorphic_call_target_hasher
>
730 polymorphic_call_target_hash_type
;
731 static polymorphic_call_target_hash_type polymorphic_call_target_hash
;
733 /* Destroy polymorphic call target query cache. */
736 free_polymorphic_call_targets_hash ()
738 if (cached_polymorphic_call_targets
)
740 polymorphic_call_target_hash
.dispose ();
741 pointer_set_destroy (cached_polymorphic_call_targets
);
742 cached_polymorphic_call_targets
= NULL
;
746 /* When virtual function is removed, we may need to flush the cache. */
749 devirt_node_removal_hook (struct cgraph_node
*n
, void *d ATTRIBUTE_UNUSED
)
751 if (cached_polymorphic_call_targets
752 && pointer_set_contains (cached_polymorphic_call_targets
, n
))
753 free_polymorphic_call_targets_hash ();
756 /* When virtual table is removed, we may need to flush the cache. */
759 devirt_variable_node_removal_hook (struct varpool_node
*n
,
760 void *d ATTRIBUTE_UNUSED
)
762 if (cached_polymorphic_call_targets
763 && DECL_VIRTUAL_P (n
->symbol
.decl
)
764 && type_in_anonymous_namespace_p (DECL_CONTEXT (n
->symbol
.decl
)))
765 free_polymorphic_call_targets_hash ();
768 /* Return vector containing possible targets of polymorphic call of type
769 OTR_TYPE caling method OTR_TOKEN with OFFSET. If FINALp is non-NULL,
770 store true if the list is complette.
771 CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
772 in the target cache. If user needs to visit every target list
773 just once, it can memoize them.
775 Returned vector is placed into cache. It is NOT caller's responsibility
776 to free it. The vector can be freed on cgraph_remove_node call if
777 the particular node is a virtual function present in the cache. */
780 possible_polymorphic_call_targets (tree otr_type
,
781 HOST_WIDE_INT otr_token
,
785 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
786 pointer_set_t
*inserted
;
787 pointer_set_t
*matched_vtables
;
788 vec
<cgraph_node
*> nodes
=vNULL
;
790 polymorphic_call_target_d key
;
791 polymorphic_call_target_d
**slot
;
798 type
= get_odr_type (otr_type
, false);
799 /* If we do not have type in our hash it means we never seen any method
804 /* For anonymous namespace types we can attempt to build full type.
805 All derivations must be in this unit. */
806 if (type
->anonymous_namespace
&& finalp
&& !flag_ltrans
)
809 /* Initialize query cache. */
810 if (!cached_polymorphic_call_targets
)
812 cached_polymorphic_call_targets
= pointer_set_create ();
813 polymorphic_call_target_hash
.create (23);
814 if (!node_removal_hook_holder
)
816 node_removal_hook_holder
=
817 cgraph_add_node_removal_hook (&devirt_node_removal_hook
, NULL
);
818 varpool_add_node_removal_hook (&devirt_variable_node_removal_hook
,
823 /* Lookup cached answer. */
825 key
.otr_token
= otr_token
;
826 slot
= polymorphic_call_target_hash
.find_slot (&key
, INSERT
);
828 *cache_token
= (void *)*slot
;
830 return (*slot
)->targets
;
832 /* Do actual search. */
833 timevar_push (TV_IPA_VIRTUAL_CALL
);
834 *slot
= XCNEW (polymorphic_call_target_d
);
836 *cache_token
= (void *)*slot
;
837 (*slot
)->type
= type
;
838 (*slot
)->otr_token
= otr_token
;
840 inserted
= pointer_set_create ();
841 matched_vtables
= pointer_set_create ();
843 /* First see virtual method of type itself. */
845 binfo
= TYPE_BINFO (type
->type
);
846 target
= gimple_get_virt_method_for_binfo (otr_token
, binfo
);
848 maybe_record_node (nodes
, target
, inserted
);
849 pointer_set_insert (matched_vtables
, BINFO_VTABLE (binfo
));
851 /* TODO: If method is final, we can stop here and signaize that
852 list is final. We need C++ FE to pass our info about final
853 methods and classes. */
855 /* Walk recursively all derived types. Here we need to lookup proper basetype
856 via their BINFO walk that is done by record_binfo */
857 for (i
= 0; i
< type
->derived_types
.length (); i
++)
858 possible_polymorphic_call_targets_1 (nodes
, inserted
,
860 otr_type
, type
->derived_types
[i
],
862 (*slot
)->targets
= nodes
;
864 pointer_set_destroy (inserted
);
865 pointer_set_destroy (matched_vtables
);
866 timevar_pop (TV_IPA_VIRTUAL_CALL
);
870 /* Dump all possible targets of a polymorphic call. */
873 dump_possible_polymorphic_call_targets (FILE *f
,
875 HOST_WIDE_INT otr_token
)
877 vec
<cgraph_node
*> targets
;
879 odr_type type
= get_odr_type (otr_type
, false);
884 targets
= possible_polymorphic_call_targets (otr_type
, otr_token
,
886 fprintf (f
, "Targets of polymorphic call of type %i ", type
->id
);
887 print_generic_expr (f
, type
->type
, TDF_SLIM
);
888 fprintf (f
, " token %i%s:",
890 final
? " (full list)" : " (partial list, may call to other unit)");
891 for (i
= 0; i
< targets
.length (); i
++)
892 fprintf (f
, " %s/%i", cgraph_node_name (targets
[i
]),
893 targets
[i
]->symbol
.order
);
898 /* Return true if N can be possibly target of a polymorphic call of
899 OTR_TYPE/OTR_TOKEN. */
902 possible_polymorphic_call_target_p (tree otr_type
,
903 HOST_WIDE_INT otr_token
,
904 struct cgraph_node
*n
)
906 vec
<cgraph_node
*> targets
;
910 if (!odr_hash
.is_created ())
912 targets
= possible_polymorphic_call_targets (otr_type
, otr_token
, &final
);
913 for (i
= 0; i
< targets
.length (); i
++)
917 /* At a moment we allow middle end to dig out new external declarations
918 as a targets of polymorphic calls. */
919 if (!final
&& !n
->symbol
.definition
)
925 /* After callgraph construction new external nodes may appear.
926 Add them into the graph. */
929 update_type_inheritance_graph (void)
931 struct cgraph_node
*n
;
933 if (!odr_hash
.is_created ())
935 free_polymorphic_call_targets_hash ();
936 timevar_push (TV_IPA_INHERITANCE
);
937 /* We reconstruct the graph starting of types of all methods seen in the
939 FOR_EACH_FUNCTION (n
)
940 if (DECL_VIRTUAL_P (n
->symbol
.decl
)
941 && !n
->symbol
.definition
942 && symtab_real_symbol_p ((symtab_node
)n
))
943 get_odr_type (method_class_type (TREE_TYPE (n
->symbol
.decl
)), true);
944 timevar_pop (TV_IPA_INHERITANCE
);
948 /* Return true if N looks like likely target of a polymorphic call.
949 Rule out cxa_pure_virtual, noreturns, function declared cold and
950 other obvious cases. */
953 likely_target_p (struct cgraph_node
*n
)
956 /* cxa_pure_virtual and similar things are not likely. */
957 if (TREE_CODE (TREE_TYPE (n
->symbol
.decl
)) != METHOD_TYPE
)
959 flags
= flags_from_decl_or_type (n
->symbol
.decl
);
960 if (flags
& ECF_NORETURN
)
962 if (lookup_attribute ("cold",
963 DECL_ATTRIBUTES (n
->symbol
.decl
)))
965 if (n
->frequency
< NODE_FREQUENCY_NORMAL
)
970 /* The ipa-devirt pass.
971 When polymorphic call has only one likely target in the unit,
972 turn it into speculative call. */
977 struct cgraph_node
*n
;
978 struct pointer_set_t
*bad_call_targets
= pointer_set_create ();
979 struct cgraph_edge
*e
;
981 int npolymorphic
= 0, nspeculated
= 0, nconverted
= 0, ncold
= 0;
982 int nmultiple
= 0, noverwritable
= 0, ndevirtualized
= 0, nnotdefined
= 0;
983 int nwrong
= 0, nok
= 0, nexternal
= 0;;
985 FOR_EACH_DEFINED_FUNCTION (n
)
988 if (dump_file
&& n
->indirect_calls
)
989 fprintf (dump_file
, "\n\nProcesing function %s/%i\n",
990 cgraph_node_name (n
), n
->symbol
.order
);
991 for (e
= n
->indirect_calls
; e
; e
= e
->next_callee
)
992 if (e
->indirect_info
->polymorphic
)
994 struct cgraph_node
*likely_target
= NULL
;
997 vec
<cgraph_node
*>targets
998 = possible_polymorphic_call_targets
999 (e
, &final
, &cache_token
);
1003 dump_possible_polymorphic_call_targets
1008 if (!cgraph_maybe_hot_edge_p (e
))
1011 fprintf (dump_file
, "Call is cold\n");
1018 fprintf (dump_file
, "Call is aready speculated\n");
1021 /* When dumping see if we agree with speculation. */
1025 if (pointer_set_contains (bad_call_targets
,
1029 fprintf (dump_file
, "Target list is known to be useless\n");
1033 for (i
= 0; i
< targets
.length (); i
++)
1034 if (likely_target_p (targets
[i
]))
1038 likely_target
= NULL
;
1040 fprintf (dump_file
, "More than one likely target\n");
1044 likely_target
= targets
[i
];
1048 pointer_set_insert (bad_call_targets
, cache_token
);
1051 /* This is reached only when dumping; check if we agree or disagree
1052 with the speculation. */
1055 struct cgraph_edge
*e2
;
1056 struct ipa_ref
*ref
;
1057 cgraph_speculative_call_info (e
, e2
, e
, ref
);
1058 if (cgraph_function_or_thunk_node (e2
->callee
, NULL
)
1059 == cgraph_function_or_thunk_node (likely_target
, NULL
))
1061 fprintf (dump_file
, "We agree with speculation\n");
1066 fprintf (dump_file
, "We disagree with speculation\n");
1071 if (!likely_target
->symbol
.definition
)
1074 fprintf (dump_file
, "Target is not an definition\n");
1078 /* Do not introduce new references to external symbols. While we
1079 can handle these just well, it is common for programs to
1080 incorrectly with headers defining methods they are linked
1082 if (DECL_EXTERNAL (likely_target
->symbol
.decl
))
1085 fprintf (dump_file
, "Target is external\n");
1089 if (cgraph_function_body_availability (likely_target
)
1090 <= AVAIL_OVERWRITABLE
1091 && symtab_can_be_discarded ((symtab_node
) likely_target
))
1094 fprintf (dump_file
, "Target is overwritable\n");
1102 "Speculatively devirtualizing call in %s/%i to %s/%i\n",
1103 cgraph_node_name (n
), n
->symbol
.order
,
1104 cgraph_node_name (likely_target
),
1105 likely_target
->symbol
.order
);
1106 if (!symtab_can_be_discarded ((symtab_node
) likely_target
))
1109 alias
= cgraph (symtab_nonoverwritable_alias
1110 ((symtab_node
)likely_target
));
1112 likely_target
= alias
;
1116 cgraph_turn_edge_to_speculative
1117 (e
, likely_target
, e
->count
* 8 / 10, e
->frequency
* 8 / 10);
1121 inline_update_overall_summary (n
);
1123 pointer_set_destroy (bad_call_targets
);
1127 "%i polymorphic calls, %i devirtualized,"
1128 " %i speculatively devirtualized, %i cold\n"
1129 "%i have multiple targets, %i overwritable,"
1130 " %i already speculated (%i agree, %i disagree),"
1131 " %i external, %i not defined\n",
1132 npolymorphic
, ndevirtualized
, nconverted
, ncold
,
1133 nmultiple
, noverwritable
, nspeculated
, nok
, nwrong
,
1134 nexternal
, nnotdefined
);
1135 return ndevirtualized
? TODO_remove_functions
: 0;
1138 /* Gate for IPCP optimization. */
1141 gate_ipa_devirt (void)
1143 return flag_devirtualize_speculatively
&& optimize
;
1148 const pass_data pass_data_ipa_devirt
=
1150 IPA_PASS
, /* type */
1151 "devirt", /* name */
1152 OPTGROUP_NONE
, /* optinfo_flags */
1153 true, /* has_gate */
1154 true, /* has_execute */
1155 TV_IPA_DEVIRT
, /* tv_id */
1156 0, /* properties_required */
1157 0, /* properties_provided */
1158 0, /* properties_destroyed */
1159 0, /* todo_flags_start */
1160 ( TODO_dump_symtab
), /* todo_flags_finish */
1163 class pass_ipa_devirt
: public ipa_opt_pass_d
1166 pass_ipa_devirt (gcc::context
*ctxt
)
1167 : ipa_opt_pass_d (pass_data_ipa_devirt
, ctxt
,
1168 NULL
, /* generate_summary */
1169 NULL
, /* write_summary */
1170 NULL
, /* read_summary */
1171 NULL
, /* write_optimization_summary */
1172 NULL
, /* read_optimization_summary */
1173 NULL
, /* stmt_fixup */
1174 0, /* function_transform_todo_flags_start */
1175 NULL
, /* function_transform */
1176 NULL
) /* variable_transform */
1179 /* opt_pass methods: */
1180 bool gate () { return gate_ipa_devirt (); }
1181 unsigned int execute () { return ipa_devirt (); }
1183 }; // class pass_ipa_devirt
1188 make_pass_ipa_devirt (gcc::context
*ctxt
)
1190 return new pass_ipa_devirt (ctxt
);
1193 #include "gt-ipa-devirt.h"