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"
123 /* Pointer set of all call targets appearing in the cache. */
124 static pointer_set_t
*cached_polymorphic_call_targets
;
126 /* The node of type inheritance graph. For each type unique in
127 One Defintion Rule (ODR) sense, we produce one node linking all
128 main variants of types equivalent to it, bases and derived types. */
130 struct GTY(()) odr_type_d
135 vec
<odr_type
> GTY((skip
)) bases
;
136 /* All derrived types with virtual methods seen in unit. */
137 vec
<odr_type
> GTY((skip
)) derived_types
;
139 /* Unique ID indexing the type in odr_types array. */
141 /* Is it in anonymous namespace? */
142 bool anonymous_namespace
;
146 /* Return true if BINFO corresponds to a type with virtual methods.
148 Every type has several BINFOs. One is the BINFO associated by the type
149 while other represents bases of derived types. The BINFOs representing
150 bases do not have BINFO_VTABLE pointer set when this is the single
151 inheritance (because vtables are shared). Look up the BINFO of type
152 and check presence of its vtable. */
155 polymorphic_type_binfo_p (tree binfo
)
157 /* See if BINFO's type has an virtual table associtated with it. */
158 return BINFO_VTABLE (TYPE_BINFO (BINFO_TYPE (binfo
)));
161 /* One Definition Rule hashtable helpers. */
165 typedef odr_type_d value_type
;
166 typedef union tree_node compare_type
;
167 static inline hashval_t
hash (const value_type
*);
168 static inline bool equal (const value_type
*, const compare_type
*);
169 static inline void remove (value_type
*);
172 /* Produce hash based on type name. */
175 hash_type_name (tree t
)
177 gcc_checking_assert (TYPE_MAIN_VARIANT (t
) == t
);
179 /* If not in LTO, all main variants are unique, so we can do
182 return htab_hash_pointer (t
);
184 /* Anonymous types are unique. */
185 if (type_in_anonymous_namespace_p (t
))
186 return htab_hash_pointer (t
);
188 /* Rest is not implemented yet. */
192 /* Return the computed hashcode for ODR_TYPE. */
195 odr_hasher::hash (const value_type
*odr_type
)
197 return hash_type_name (odr_type
->type
);
200 /* Compare types T1 and T2 and return true if they are
204 odr_hasher::equal (const value_type
*t1
, const compare_type
*ct2
)
206 tree t2
= const_cast <tree
> (ct2
);
208 gcc_checking_assert (TYPE_MAIN_VARIANT (ct2
) == ct2
);
213 return types_same_for_odr (t1
->type
, t2
);
216 /* Free ODR type V. */
219 odr_hasher::remove (value_type
*v
)
222 v
->derived_types
.release ();
226 /* ODR type hash used to lookup ODR type based on tree type node. */
228 typedef hash_table
<odr_hasher
> odr_hash_type
;
229 static odr_hash_type odr_hash
;
231 /* ODR types are also stored into ODR_TYPE vector to allow consistent
232 walking. Bases appear before derived types. Vector is garbage collected
233 so we won't end up visiting empty types. */
235 static GTY(()) vec
<odr_type
, va_gc
> *odr_types_ptr
;
236 #define odr_types (*odr_types_ptr)
238 /* Get ODR type hash entry for TYPE. If INSERT is true, create
239 possibly new entry. */
242 get_odr_type (tree type
, bool insert
)
248 type
= TYPE_MAIN_VARIANT (type
);
249 gcc_checking_assert (TYPE_MAIN_VARIANT (type
) == type
);
250 hash
= hash_type_name (type
);
251 slot
= odr_hash
.find_slot_with_hash (type
, hash
, insert
? INSERT
: NO_INSERT
);
255 /* See if we already have entry for type. */
260 /* With LTO we will need to support multiple tree representation of
261 the same ODR type. For now we ignore this. */
262 if (val
->type
== type
)
268 tree binfo
= TYPE_BINFO (type
);
271 val
= ggc_alloc_cleared_odr_type_d ();
274 val
->derived_types
= vNULL
;
275 val
->anonymous_namespace
= type_in_anonymous_namespace_p (type
);
277 for (i
= 0; i
< BINFO_N_BASE_BINFOS (binfo
); i
++)
278 /* For now record only polymorphic types. other are
279 pointless for devirtualization and we can not precisely
280 determine ODR equivalency of these during LTO. */
281 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (binfo
, i
)))
283 odr_type base
= get_odr_type (BINFO_TYPE (BINFO_BASE_BINFO (binfo
,
286 base
->derived_types
.safe_push (val
);
287 val
->bases
.safe_push (base
);
289 /* First record bases, then add into array so ids are increasing. */
291 val
->id
= odr_types
.length();
292 vec_safe_push (odr_types_ptr
, val
);
297 /* Dump ODR type T and all its derrived type. INDENT specify indentation for
298 recusive printing. */
301 dump_odr_type (FILE *f
, odr_type t
, int indent
=0)
304 fprintf (f
, "%*s type %i: ", indent
* 2, "", t
->id
);
305 print_generic_expr (f
, t
->type
, TDF_SLIM
);
306 fprintf (f
, "%s\n", t
->anonymous_namespace
? " (anonymous namespace)":"");
307 if (TYPE_NAME (t
->type
))
309 fprintf (f
, "%*s defined at: %s:%i\n", indent
* 2, "",
310 DECL_SOURCE_FILE (TYPE_NAME (t
->type
)),
311 DECL_SOURCE_LINE (TYPE_NAME (t
->type
)));
313 if (t
->bases
.length())
315 fprintf (f
, "%*s base odr type ids: ", indent
* 2, "");
316 for (i
= 0; i
< t
->bases
.length(); i
++)
317 fprintf (f
, " %i", t
->bases
[i
]->id
);
320 if (t
->derived_types
.length())
322 fprintf (f
, "%*s derived types:\n", indent
* 2, "");
323 for (i
= 0; i
< t
->derived_types
.length(); i
++)
324 dump_odr_type (f
, t
->derived_types
[i
], indent
+ 1);
329 /* Dump the type inheritance graph. */
332 dump_type_inheritance_graph (FILE *f
)
337 fprintf (f
, "\n\nType inheritance graph:\n");
338 for (i
= 0; i
< odr_types
.length(); i
++)
340 if (odr_types
[i
]->bases
.length() == 0)
341 dump_odr_type (f
, odr_types
[i
]);
345 /* Given method type T, return type of class it belongs to.
346 Lookup this pointer and get its type. */
349 method_class_type (tree t
)
351 tree first_parm_type
= TREE_VALUE (TYPE_ARG_TYPES (t
));
353 return TREE_TYPE (first_parm_type
);
356 /* Initialize IPA devirt and build inheritance tree graph. */
359 build_type_inheritance_graph (void)
361 struct cgraph_node
*n
;
362 FILE *inheritance_dump_file
;
365 if (odr_hash
.is_created ())
367 timevar_push (TV_IPA_INHERITANCE
);
368 inheritance_dump_file
= dump_begin (TDI_inheritance
, &flags
);
369 odr_hash
.create (23);
371 /* We reconstruct the graph starting of types of all methods seen in the
373 FOR_EACH_FUNCTION (n
)
374 if (DECL_VIRTUAL_P (n
->symbol
.decl
)
375 && symtab_real_symbol_p ((symtab_node
)n
))
376 get_odr_type (method_class_type (TREE_TYPE (n
->symbol
.decl
)), true);
377 if (inheritance_dump_file
)
379 dump_type_inheritance_graph (inheritance_dump_file
);
380 dump_end (TDI_inheritance
, inheritance_dump_file
);
382 timevar_pop (TV_IPA_INHERITANCE
);
385 /* If TARGET has associated node, record it in the NODES array. */
388 maybe_record_node (vec
<cgraph_node
*> &nodes
,
389 tree target
, pointer_set_t
*inserted
)
391 struct cgraph_node
*target_node
;
392 enum built_in_function fcode
;
395 /* Those are used to mark impossible scenarios. */
396 && (fcode
= DECL_FUNCTION_CODE (target
))
397 != BUILT_IN_UNREACHABLE
398 && fcode
!= BUILT_IN_TRAP
399 && !pointer_set_insert (inserted
, target
)
400 && (target_node
= cgraph_get_node (target
)) != NULL
401 && symtab_real_symbol_p ((symtab_node
)target_node
))
403 pointer_set_insert (cached_polymorphic_call_targets
,
405 nodes
.safe_push (target_node
);
409 /* See if BINFO's type match OTR_TYPE. If so, lookup method
410 in vtable of TYPE_BINFO and insert method to NODES array.
411 Otherwise recurse to base BINFOs.
412 This match what get_binfo_at_offset does, but with offset
415 TYPE_BINFO is binfo holding an virtual table matching
416 BINFO's type. In the case of single inheritance, this
417 is binfo of BINFO's type ancestor (vtable is shared),
418 otherwise it is binfo of BINFO's type.
420 MATCHED_VTABLES tracks virtual tables we already did lookup
421 for virtual function in.
425 record_binfo (vec
<cgraph_node
*> &nodes
,
429 HOST_WIDE_INT otr_token
,
430 pointer_set_t
*inserted
,
431 pointer_set_t
*matched_vtables
)
433 tree type
= BINFO_TYPE (binfo
);
437 gcc_checking_assert (BINFO_VTABLE (type_binfo
));
439 if (types_same_for_odr (type
, otr_type
)
440 && !pointer_set_insert (matched_vtables
, BINFO_VTABLE (type_binfo
)))
442 tree target
= gimple_get_virt_method_for_binfo (otr_token
, type_binfo
);
444 maybe_record_node (nodes
, target
, inserted
);
449 for (i
= 0; BINFO_BASE_ITERATE (binfo
, i
, base_binfo
); i
++)
450 /* Walking bases that have no virtual method is pointless excercise. */
451 if (polymorphic_type_binfo_p (base_binfo
))
452 record_binfo (nodes
, base_binfo
, otr_type
,
453 /* In the case of single inheritance, the virtual table
454 is shared with the outer type. */
455 BINFO_VTABLE (base_binfo
) ? base_binfo
: type_binfo
,
460 /* Lookup virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN)
461 of TYPE, insert them to NODES, recurse into derived nodes.
462 INSERTED is used to avoid duplicate insertions of methods into NODES.
463 MATCHED_VTABLES are used to avoid duplicate walking vtables. */
466 possible_polymorphic_call_targets_1 (vec
<cgraph_node
*> &nodes
,
467 pointer_set_t
*inserted
,
468 pointer_set_t
*matched_vtables
,
471 HOST_WIDE_INT otr_token
)
473 tree binfo
= TYPE_BINFO (type
->type
);
476 record_binfo (nodes
, binfo
, otr_type
, binfo
, otr_token
, inserted
,
478 for (i
= 0; i
< type
->derived_types
.length(); i
++)
479 possible_polymorphic_call_targets_1 (nodes
, inserted
,
482 type
->derived_types
[i
],
486 /* Cache of queries for polymorphic call targets.
488 Enumerating all call targets may get expensive when there are many
489 polymorphic calls in the program, so we memoize all the previous
490 queries and avoid duplicated work. */
492 struct polymorphic_call_target_d
495 HOST_WIDE_INT otr_token
;
496 vec
<cgraph_node
*> targets
;
499 /* Polymorphic call target cache helpers. */
501 struct polymorphic_call_target_hasher
503 typedef polymorphic_call_target_d value_type
;
504 typedef polymorphic_call_target_d compare_type
;
505 static inline hashval_t
hash (const value_type
*);
506 static inline bool equal (const value_type
*, const compare_type
*);
507 static inline void remove (value_type
*);
510 /* Return the computed hashcode for ODR_QUERY. */
513 polymorphic_call_target_hasher::hash (const value_type
*odr_query
)
515 return iterative_hash_hashval_t (odr_query
->type
->id
,
516 odr_query
->otr_token
);
519 /* Compare cache entries T1 and T2. */
522 polymorphic_call_target_hasher::equal (const value_type
*t1
,
523 const compare_type
*t2
)
525 return t1
->type
== t2
->type
&& t1
->otr_token
== t2
->otr_token
;
528 /* Remove entry in polymorphic call target cache hash. */
531 polymorphic_call_target_hasher::remove (value_type
*v
)
533 v
->targets
.release ();
537 /* Polymorphic call target query cache. */
539 typedef hash_table
<polymorphic_call_target_hasher
>
540 polymorphic_call_target_hash_type
;
541 static polymorphic_call_target_hash_type polymorphic_call_target_hash
;
543 /* Destroy polymorphic call target query cache. */
546 free_polymorphic_call_targets_hash ()
548 if (cached_polymorphic_call_targets
)
550 polymorphic_call_target_hash
.dispose ();
551 pointer_set_destroy (cached_polymorphic_call_targets
);
552 cached_polymorphic_call_targets
= NULL
;
556 /* When virtual function is removed, we may need to flush the cache. */
559 devirt_node_removal_hook (struct cgraph_node
*n
, void *d ATTRIBUTE_UNUSED
)
561 if (cached_polymorphic_call_targets
562 && pointer_set_contains (cached_polymorphic_call_targets
, n
))
563 free_polymorphic_call_targets_hash ();
566 /* Return vector containing possible targets of polymorphic call of type
567 OTR_TYPE caling method OTR_TOKEN with OFFSET. If FINALp is non-NULL,
568 store true if the list is complette.
569 CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
570 in the target cache. If user needs to visit every target list
571 just once, it can memoize them.
573 Returned vector is placed into cache. It is NOT caller's responsibility
574 to free it. The vector can be freed on cgraph_remove_node call if
575 the particular node is a virtual function present in the cache. */
578 possible_polymorphic_call_targets (tree otr_type
,
579 HOST_WIDE_INT otr_token
,
583 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
584 pointer_set_t
*inserted
;
585 pointer_set_t
*matched_vtables
;
586 vec
<cgraph_node
*> nodes
=vNULL
;
588 polymorphic_call_target_d key
;
589 polymorphic_call_target_d
**slot
;
596 type
= get_odr_type (otr_type
, false);
597 /* If we do not have type in our hash it means we never seen any method
602 /* For anonymous namespace types we can attempt to build full type.
603 All derivations must be in this unit. */
604 if (type
->anonymous_namespace
&& finalp
&& !flag_ltrans
)
607 /* Initialize query cache. */
608 if (!cached_polymorphic_call_targets
)
610 cached_polymorphic_call_targets
= pointer_set_create ();
611 polymorphic_call_target_hash
.create (23);
612 if (!node_removal_hook_holder
)
613 node_removal_hook_holder
=
614 cgraph_add_node_removal_hook (&devirt_node_removal_hook
, NULL
);
617 /* Lookup cached answer. */
619 key
.otr_token
= otr_token
;
620 slot
= polymorphic_call_target_hash
.find_slot (&key
, INSERT
);
622 *cache_token
= (void *)*slot
;
624 return (*slot
)->targets
;
626 /* Do actual search. */
627 timevar_push (TV_IPA_VIRTUAL_CALL
);
628 *slot
= XCNEW (polymorphic_call_target_d
);
630 *cache_token
= (void *)*slot
;
631 (*slot
)->type
= type
;
632 (*slot
)->otr_token
= otr_token
;
634 inserted
= pointer_set_create ();
635 matched_vtables
= pointer_set_create ();
637 /* First see virtual method of type itself. */
639 binfo
= TYPE_BINFO (type
->type
);
640 target
= gimple_get_virt_method_for_binfo (otr_token
, binfo
);
642 maybe_record_node (nodes
, target
, inserted
);
643 pointer_set_insert (matched_vtables
, BINFO_VTABLE (binfo
));
645 /* TODO: If method is final, we can stop here and signaize that
646 list is final. We need C++ FE to pass our info about final
647 methods and classes. */
649 /* Walk recursively all derived types. Here we need to lookup proper basetype
650 via their BINFO walk that is done by record_binfo */
651 for (i
= 0; i
< type
->derived_types
.length(); i
++)
652 possible_polymorphic_call_targets_1 (nodes
, inserted
,
654 otr_type
, type
->derived_types
[i
],
656 (*slot
)->targets
= nodes
;
658 pointer_set_destroy (inserted
);
659 pointer_set_destroy (matched_vtables
);
660 timevar_pop (TV_IPA_VIRTUAL_CALL
);
664 /* Dump all possible targets of a polymorphic call. */
667 dump_possible_polymorphic_call_targets (FILE *f
,
669 HOST_WIDE_INT otr_token
)
671 vec
<cgraph_node
*> targets
;
673 odr_type type
= get_odr_type (otr_type
, false);
678 targets
= possible_polymorphic_call_targets (otr_type
, otr_token
,
680 fprintf (f
, "Targets of polymorphic call of type %i ", type
->id
);
681 print_generic_expr (f
, type
->type
, TDF_SLIM
);
682 fprintf (f
, " token %i%s:",
684 final
? " (full list)" : " (partial list, may call to other unit)");
685 for (i
= 0; i
< targets
.length (); i
++)
686 fprintf (f
, " %s/%i", cgraph_node_name (targets
[i
]),
687 targets
[i
]->symbol
.order
);
692 /* Return true if N can be possibly target of a polymorphic call of
693 OTR_TYPE/OTR_TOKEN. */
696 possible_polymorphic_call_target_p (tree otr_type
,
697 HOST_WIDE_INT otr_token
,
698 struct cgraph_node
*n
)
700 vec
<cgraph_node
*> targets
;
703 if (!odr_hash
.is_created ())
705 targets
= possible_polymorphic_call_targets (otr_type
, otr_token
);
706 for (i
= 0; i
< targets
.length (); i
++)
713 /* After callgraph construction new external nodes may appear.
714 Add them into the graph. */
717 update_type_inheritance_graph (void)
719 struct cgraph_node
*n
;
721 if (!odr_hash
.is_created ())
723 free_polymorphic_call_targets_hash ();
724 timevar_push (TV_IPA_INHERITANCE
);
725 /* We reconstruct the graph starting of types of all methods seen in the
727 FOR_EACH_FUNCTION (n
)
728 if (DECL_VIRTUAL_P (n
->symbol
.decl
)
729 && !n
->symbol
.definition
730 && symtab_real_symbol_p ((symtab_node
)n
))
731 get_odr_type (method_class_type (TREE_TYPE (n
->symbol
.decl
)), true);
732 timevar_pop (TV_IPA_INHERITANCE
);
736 /* Return true if N looks like likely target of a polymorphic call.
737 Rule out cxa_pure_virtual, noreturns, function declared cold and
738 other obvious cases. */
741 likely_target_p (struct cgraph_node
*n
)
744 /* cxa_pure_virtual and similar things are not likely. */
745 if (TREE_CODE (TREE_TYPE (n
->symbol
.decl
)) != METHOD_TYPE
)
747 flags
= flags_from_decl_or_type (n
->symbol
.decl
);
748 if (flags
& ECF_NORETURN
)
750 if (lookup_attribute ("cold",
751 DECL_ATTRIBUTES (n
->symbol
.decl
)))
753 if (n
->frequency
< NODE_FREQUENCY_NORMAL
)
758 /* The ipa-devirt pass.
759 This performs very trivial devirtualization:
760 1) when polymorphic call is known to have precisely one target,
761 turn it into direct call
762 2) when polymorphic call has only one likely target in the unit,
763 turn it into speculative call. */
768 struct cgraph_node
*n
;
769 struct pointer_set_t
*bad_call_targets
= pointer_set_create ();
770 struct cgraph_edge
*e
;
772 int npolymorphic
= 0, nspeculated
= 0, nconverted
= 0, ncold
= 0;
773 int nmultiple
= 0, noverwritable
= 0, ndevirtualized
= 0, nnotdefined
= 0;
774 int nwrong
= 0, nok
= 0, nexternal
= 0;;
776 FOR_EACH_DEFINED_FUNCTION (n
)
779 if (dump_file
&& n
->indirect_calls
)
780 fprintf (dump_file
, "\n\nProcesing function %s/%i\n",
781 cgraph_node_name (n
), n
->symbol
.order
);
782 for (e
= n
->indirect_calls
; e
; e
= e
->next_callee
)
783 if (e
->indirect_info
->polymorphic
)
785 struct cgraph_node
*likely_target
= NULL
;
788 vec
<cgraph_node
*>targets
789 = possible_polymorphic_call_targets
790 (e
, &final
, &cache_token
);
794 dump_possible_polymorphic_call_targets
800 gcc_assert (targets
.length());
801 if (targets
.length() == 1)
805 "Devirtualizing call in %s/%i to %s/%i\n",
806 cgraph_node_name (n
), n
->symbol
.order
,
807 cgraph_node_name (targets
[0]), targets
[0]->symbol
.order
);
808 cgraph_make_edge_direct (e
, targets
[0]);
814 if (!flag_devirtualize_speculatively
)
816 if (!cgraph_maybe_hot_edge_p (e
))
819 fprintf (dump_file
, "Call is cold\n");
826 fprintf (dump_file
, "Call is aready speculated\n");
829 /* When dumping see if we agree with speculation. */
833 if (pointer_set_contains (bad_call_targets
,
837 fprintf (dump_file
, "Target list is known to be useless\n");
841 for (i
= 0; i
< targets
.length(); i
++)
842 if (likely_target_p (targets
[i
]))
846 likely_target
= NULL
;
848 fprintf (dump_file
, "More than one likely target\n");
852 likely_target
= targets
[i
];
856 pointer_set_insert (bad_call_targets
, cache_token
);
859 /* This is reached only when dumping; check if we agree or disagree
860 with the speculation. */
863 struct cgraph_edge
*e2
;
865 cgraph_speculative_call_info (e
, e2
, e
, ref
);
866 if (cgraph_function_or_thunk_node (e2
->callee
, NULL
)
867 == cgraph_function_or_thunk_node (likely_target
, NULL
))
869 fprintf (dump_file
, "We agree with speculation\n");
874 fprintf (dump_file
, "We disagree with speculation\n");
879 if (!likely_target
->symbol
.definition
)
882 fprintf (dump_file
, "Target is not an definition\n");
886 /* Do not introduce new references to external symbols. While we
887 can handle these just well, it is common for programs to
888 incorrectly with headers defining methods they are linked
890 if (DECL_EXTERNAL (likely_target
->symbol
.decl
))
893 fprintf (dump_file
, "Target is external\n");
897 if (cgraph_function_body_availability (likely_target
)
898 <= AVAIL_OVERWRITABLE
899 && symtab_can_be_discarded ((symtab_node
) likely_target
))
902 fprintf (dump_file
, "Target is overwritable\n");
910 "Speculatively devirtualizing call in %s/%i to %s/%i\n",
911 cgraph_node_name (n
), n
->symbol
.order
,
912 cgraph_node_name (likely_target
),
913 likely_target
->symbol
.order
);
914 if (!symtab_can_be_discarded ((symtab_node
) likely_target
))
915 likely_target
= cgraph (symtab_nonoverwritable_alias ((symtab_node
)likely_target
));
918 cgraph_turn_edge_to_speculative
919 (e
, likely_target
, e
->count
* 8 / 10, e
->frequency
* 8 / 10);
923 inline_update_overall_summary (n
);
925 pointer_set_destroy (bad_call_targets
);
929 "%i polymorphic calls, %i devirtualized,"
930 " %i speculatively devirtualized, %i cold\n"
931 "%i have multiple targets, %i overwritable,"
932 " %i already speculated (%i agree, %i disagree),"
933 " %i external, %i not defined\n",
934 npolymorphic
, ndevirtualized
, nconverted
, ncold
,
935 nmultiple
, noverwritable
, nspeculated
, nok
, nwrong
,
936 nexternal
, nnotdefined
);
937 return ndevirtualized
? TODO_remove_functions
: 0;
940 /* Gate for IPCP optimization. */
943 gate_ipa_devirt (void)
945 /* FIXME: We should remove the optimize check after we ensure we never run
946 IPA passes when not optimizing. */
947 return flag_devirtualize
&& !in_lto_p
;
952 const pass_data pass_data_ipa_devirt
=
956 OPTGROUP_NONE
, /* optinfo_flags */
958 true, /* has_execute */
959 TV_IPA_DEVIRT
, /* tv_id */
960 0, /* properties_required */
961 0, /* properties_provided */
962 0, /* properties_destroyed */
963 0, /* todo_flags_start */
964 ( TODO_dump_symtab
), /* todo_flags_finish */
967 class pass_ipa_devirt
: public ipa_opt_pass_d
970 pass_ipa_devirt(gcc::context
*ctxt
)
971 : ipa_opt_pass_d(pass_data_ipa_devirt
, ctxt
,
972 NULL
, /* generate_summary */
973 NULL
, /* write_summary */
974 NULL
, /* read_summary */
975 NULL
, /* write_optimization_summary */
976 NULL
, /* read_optimization_summary */
977 NULL
, /* stmt_fixup */
978 0, /* function_transform_todo_flags_start */
979 NULL
, /* function_transform */
980 NULL
) /* variable_transform */
983 /* opt_pass methods: */
984 bool gate () { return gate_ipa_devirt (); }
985 unsigned int execute () { return ipa_devirt (); }
987 }; // class pass_ipa_devirt
992 make_pass_ipa_devirt (gcc::context
*ctxt
)
994 return new pass_ipa_devirt (ctxt
);
997 #include "gt-ipa-devirt.h"