138fd1498Szrj /* Utilities for ipa analysis.
238fd1498Szrj Copyright (C) 2004-2018 Free Software Foundation, Inc.
338fd1498Szrj Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
438fd1498Szrj
538fd1498Szrj This file is part of GCC.
638fd1498Szrj
738fd1498Szrj GCC is free software; you can redistribute it and/or modify it under
838fd1498Szrj the terms of the GNU General Public License as published by the Free
938fd1498Szrj Software Foundation; either version 3, or (at your option) any later
1038fd1498Szrj version.
1138fd1498Szrj
1238fd1498Szrj GCC is distributed in the hope that it will be useful, but WITHOUT ANY
1338fd1498Szrj WARRANTY; without even the implied warranty of MERCHANTABILITY or
1438fd1498Szrj FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1538fd1498Szrj for more details.
1638fd1498Szrj
1738fd1498Szrj You should have received a copy of the GNU General Public License
1838fd1498Szrj along with GCC; see the file COPYING3. If not see
1938fd1498Szrj <http://www.gnu.org/licenses/>. */
2038fd1498Szrj
2138fd1498Szrj #ifndef GCC_IPA_UTILS_H
2238fd1498Szrj #define GCC_IPA_UTILS_H
2338fd1498Szrj
2438fd1498Szrj struct ipa_dfs_info {
2538fd1498Szrj int dfn_number;
2638fd1498Szrj int low_link;
2738fd1498Szrj /* This field will have the samy value for any two nodes in the same strongly
2838fd1498Szrj connected component. */
2938fd1498Szrj int scc_no;
3038fd1498Szrj bool new_node;
3138fd1498Szrj bool on_stack;
3238fd1498Szrj struct cgraph_node* next_cycle;
3338fd1498Szrj PTR aux;
3438fd1498Szrj };
3538fd1498Szrj
3638fd1498Szrj
3738fd1498Szrj /* In ipa-utils.c */
3838fd1498Szrj void ipa_print_order (FILE*, const char *, struct cgraph_node**, int);
39*58e805e6Szrj int ipa_reduced_postorder (struct cgraph_node **, bool,
4038fd1498Szrj bool (*ignore_edge) (struct cgraph_edge *));
4138fd1498Szrj void ipa_free_postorder_info (void);
4238fd1498Szrj vec<cgraph_node *> ipa_get_nodes_in_cycle (struct cgraph_node *);
4338fd1498Szrj bool ipa_edge_within_scc (struct cgraph_edge *);
4438fd1498Szrj int ipa_reverse_postorder (struct cgraph_node **);
4538fd1498Szrj tree get_base_var (tree);
4638fd1498Szrj void ipa_merge_profiles (struct cgraph_node *dst,
4738fd1498Szrj struct cgraph_node *src, bool preserve_body = false);
4838fd1498Szrj bool recursive_call_p (tree, tree);
4938fd1498Szrj
5038fd1498Szrj /* In ipa-profile.c */
5138fd1498Szrj bool ipa_propagate_frequency (struct cgraph_node *node);
5238fd1498Szrj
5338fd1498Szrj /* In ipa-devirt.c */
5438fd1498Szrj
5538fd1498Szrj struct odr_type_d;
5638fd1498Szrj typedef odr_type_d *odr_type;
5738fd1498Szrj void build_type_inheritance_graph (void);
5838fd1498Szrj void rebuild_type_inheritance_graph (void);
5938fd1498Szrj void update_type_inheritance_graph (void);
6038fd1498Szrj vec <cgraph_node *>
6138fd1498Szrj possible_polymorphic_call_targets (tree, HOST_WIDE_INT,
6238fd1498Szrj ipa_polymorphic_call_context,
6338fd1498Szrj bool *copletep = NULL,
6438fd1498Szrj void **cache_token = NULL,
6538fd1498Szrj bool speuclative = false);
6638fd1498Szrj odr_type get_odr_type (tree, bool insert = false);
6738fd1498Szrj bool odr_type_p (const_tree);
6838fd1498Szrj bool possible_polymorphic_call_target_p (tree ref, gimple *stmt, struct cgraph_node *n);
6938fd1498Szrj void dump_possible_polymorphic_call_targets (FILE *, tree, HOST_WIDE_INT,
7038fd1498Szrj const ipa_polymorphic_call_context &);
7138fd1498Szrj bool possible_polymorphic_call_target_p (tree, HOST_WIDE_INT,
7238fd1498Szrj const ipa_polymorphic_call_context &,
7338fd1498Szrj struct cgraph_node *);
7438fd1498Szrj tree polymorphic_ctor_dtor_p (tree, bool);
7538fd1498Szrj tree inlined_polymorphic_ctor_dtor_block_p (tree, bool);
7638fd1498Szrj bool decl_maybe_in_construction_p (tree, tree, gimple *, tree);
7738fd1498Szrj tree vtable_pointer_value_to_binfo (const_tree);
7838fd1498Szrj bool vtable_pointer_value_to_vtable (const_tree, tree *, unsigned HOST_WIDE_INT *);
7938fd1498Szrj tree subbinfo_with_vtable_at_offset (tree, unsigned HOST_WIDE_INT, tree);
8038fd1498Szrj void compare_virtual_tables (varpool_node *, varpool_node *);
8138fd1498Szrj bool type_all_derivations_known_p (const_tree);
8238fd1498Szrj bool type_known_to_have_no_derivations_p (tree);
8338fd1498Szrj bool contains_polymorphic_type_p (const_tree);
8438fd1498Szrj void register_odr_type (tree);
8538fd1498Szrj bool types_must_be_same_for_odr (tree, tree);
8638fd1498Szrj bool types_odr_comparable (tree, tree, bool strict = false);
8738fd1498Szrj cgraph_node *try_speculative_devirtualization (tree, HOST_WIDE_INT,
8838fd1498Szrj ipa_polymorphic_call_context);
8938fd1498Szrj void warn_types_mismatch (tree t1, tree t2, location_t loc1 = UNKNOWN_LOCATION,
9038fd1498Szrj location_t loc2 = UNKNOWN_LOCATION);
9138fd1498Szrj bool odr_or_derived_type_p (const_tree t);
9238fd1498Szrj bool odr_types_equivalent_p (tree type1, tree type2);
9338fd1498Szrj
9438fd1498Szrj /* Return vector containing possible targets of polymorphic call E.
9538fd1498Szrj If COMPLETEP is non-NULL, store true if the list is complete.
9638fd1498Szrj CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
9738fd1498Szrj in the target cache. If user needs to visit every target list
9838fd1498Szrj just once, it can memoize them.
9938fd1498Szrj
10038fd1498Szrj Returned vector is placed into cache. It is NOT caller's responsibility
10138fd1498Szrj to free it. The vector can be freed on cgraph_remove_node call if
10238fd1498Szrj the particular node is a virtual function present in the cache. */
10338fd1498Szrj
10438fd1498Szrj inline vec <cgraph_node *>
10538fd1498Szrj possible_polymorphic_call_targets (struct cgraph_edge *e,
10638fd1498Szrj bool *completep = NULL,
10738fd1498Szrj void **cache_token = NULL,
10838fd1498Szrj bool speculative = false)
10938fd1498Szrj {
11038fd1498Szrj ipa_polymorphic_call_context context(e);
11138fd1498Szrj
11238fd1498Szrj return possible_polymorphic_call_targets (e->indirect_info->otr_type,
11338fd1498Szrj e->indirect_info->otr_token,
11438fd1498Szrj context,
11538fd1498Szrj completep, cache_token,
11638fd1498Szrj speculative);
11738fd1498Szrj }
11838fd1498Szrj
11938fd1498Szrj /* Same as above but taking OBJ_TYPE_REF as an parameter. */
12038fd1498Szrj
12138fd1498Szrj inline vec <cgraph_node *>
12238fd1498Szrj possible_polymorphic_call_targets (tree ref,
12338fd1498Szrj gimple *call,
12438fd1498Szrj bool *completep = NULL,
12538fd1498Szrj void **cache_token = NULL)
12638fd1498Szrj {
12738fd1498Szrj ipa_polymorphic_call_context context (current_function_decl, ref, call);
12838fd1498Szrj
12938fd1498Szrj return possible_polymorphic_call_targets (obj_type_ref_class (ref),
13038fd1498Szrj tree_to_uhwi
13138fd1498Szrj (OBJ_TYPE_REF_TOKEN (ref)),
13238fd1498Szrj context,
13338fd1498Szrj completep, cache_token);
13438fd1498Szrj }
13538fd1498Szrj
13638fd1498Szrj /* Dump possible targets of a polymorphic call E into F. */
13738fd1498Szrj
13838fd1498Szrj inline void
dump_possible_polymorphic_call_targets(FILE * f,struct cgraph_edge * e)13938fd1498Szrj dump_possible_polymorphic_call_targets (FILE *f, struct cgraph_edge *e)
14038fd1498Szrj {
14138fd1498Szrj ipa_polymorphic_call_context context(e);
14238fd1498Szrj
14338fd1498Szrj dump_possible_polymorphic_call_targets (f, e->indirect_info->otr_type,
14438fd1498Szrj e->indirect_info->otr_token,
14538fd1498Szrj context);
14638fd1498Szrj }
14738fd1498Szrj
14838fd1498Szrj /* Return true if N can be possibly target of a polymorphic call of
14938fd1498Szrj E. */
15038fd1498Szrj
15138fd1498Szrj inline bool
possible_polymorphic_call_target_p(struct cgraph_edge * e,struct cgraph_node * n)15238fd1498Szrj possible_polymorphic_call_target_p (struct cgraph_edge *e,
15338fd1498Szrj struct cgraph_node *n)
15438fd1498Szrj {
15538fd1498Szrj ipa_polymorphic_call_context context(e);
15638fd1498Szrj
15738fd1498Szrj return possible_polymorphic_call_target_p (e->indirect_info->otr_type,
15838fd1498Szrj e->indirect_info->otr_token,
15938fd1498Szrj context, n);
16038fd1498Szrj }
16138fd1498Szrj
16238fd1498Szrj /* Return true if BINFO corresponds to a type with virtual methods.
16338fd1498Szrj
16438fd1498Szrj Every type has several BINFOs. One is the BINFO associated by the type
16538fd1498Szrj while other represents bases of derived types. The BINFOs representing
16638fd1498Szrj bases do not have BINFO_VTABLE pointer set when this is the single
16738fd1498Szrj inheritance (because vtables are shared). Look up the BINFO of type
16838fd1498Szrj and check presence of its vtable. */
16938fd1498Szrj
17038fd1498Szrj inline bool
polymorphic_type_binfo_p(const_tree binfo)17138fd1498Szrj polymorphic_type_binfo_p (const_tree binfo)
17238fd1498Szrj {
17338fd1498Szrj return (BINFO_TYPE (binfo) && TYPE_BINFO (BINFO_TYPE (binfo))
17438fd1498Szrj && BINFO_VTABLE (TYPE_BINFO (BINFO_TYPE (binfo))));
17538fd1498Szrj }
17638fd1498Szrj
17738fd1498Szrj /* Return true if T is a type with linkage defined. */
17838fd1498Szrj
17938fd1498Szrj inline bool
type_with_linkage_p(const_tree t)18038fd1498Szrj type_with_linkage_p (const_tree t)
18138fd1498Szrj {
18238fd1498Szrj if (!TYPE_NAME (t) || TREE_CODE (TYPE_NAME (t)) != TYPE_DECL
18338fd1498Szrj || !TYPE_STUB_DECL (t))
18438fd1498Szrj return false;
18538fd1498Szrj /* In LTO do not get confused by non-C++ produced types or types built
18638fd1498Szrj with -fno-lto-odr-type-merigng. */
18738fd1498Szrj if (in_lto_p)
18838fd1498Szrj {
18938fd1498Szrj /* To support -fno-lto-odr-type-merigng recognize types with vtables
19038fd1498Szrj to have linkage. */
19138fd1498Szrj if (RECORD_OR_UNION_TYPE_P (t)
19238fd1498Szrj && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)))
19338fd1498Szrj return true;
19438fd1498Szrj /* With -flto-odr-type-merging C++ FE specify mangled names
19538fd1498Szrj for all types with the linkage. */
19638fd1498Szrj return DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t));
19738fd1498Szrj }
19838fd1498Szrj
19938fd1498Szrj if (!RECORD_OR_UNION_TYPE_P (t) && TREE_CODE (t) != ENUMERAL_TYPE)
20038fd1498Szrj return false;
20138fd1498Szrj
20238fd1498Szrj /* Builtin types do not define linkage, their TYPE_CONTEXT is NULL. */
20338fd1498Szrj if (!TYPE_CONTEXT (t))
20438fd1498Szrj return false;
20538fd1498Szrj
20638fd1498Szrj return true;
20738fd1498Szrj }
20838fd1498Szrj
20938fd1498Szrj /* Return true if T is in anonymous namespace.
21038fd1498Szrj This works only on those C++ types with linkage defined. */
21138fd1498Szrj
21238fd1498Szrj inline bool
type_in_anonymous_namespace_p(const_tree t)21338fd1498Szrj type_in_anonymous_namespace_p (const_tree t)
21438fd1498Szrj {
21538fd1498Szrj gcc_checking_assert (type_with_linkage_p (t));
21638fd1498Szrj
21738fd1498Szrj if (!TREE_PUBLIC (TYPE_STUB_DECL (t)))
21838fd1498Szrj {
21938fd1498Szrj /* C++ FE uses magic <anon> as assembler names of anonymous types.
22038fd1498Szrj verify that this match with type_in_anonymous_namespace_p. */
22138fd1498Szrj gcc_checking_assert (!in_lto_p
22238fd1498Szrj || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t))
22338fd1498Szrj || !strcmp ("<anon>",
22438fd1498Szrj IDENTIFIER_POINTER
22538fd1498Szrj (DECL_ASSEMBLER_NAME (TYPE_NAME (t)))));
22638fd1498Szrj return true;
22738fd1498Szrj }
22838fd1498Szrj return false;
22938fd1498Szrj }
23038fd1498Szrj
23138fd1498Szrj /* Return true of T is type with One Definition Rule info attached.
23238fd1498Szrj It means that either it is anonymous type or it has assembler name
23338fd1498Szrj set. */
23438fd1498Szrj
23538fd1498Szrj inline bool
odr_type_p(const_tree t)23638fd1498Szrj odr_type_p (const_tree t)
23738fd1498Szrj {
23838fd1498Szrj /* We do not have this information when not in LTO, but we do not need
23938fd1498Szrj to care, since it is used only for type merging. */
24038fd1498Szrj gcc_checking_assert (in_lto_p || flag_lto);
24138fd1498Szrj
24238fd1498Szrj if (!type_with_linkage_p (t))
24338fd1498Szrj return false;
24438fd1498Szrj
24538fd1498Szrj /* To support -fno-lto-odr-type-merging consider types with vtables ODR. */
24638fd1498Szrj if (type_in_anonymous_namespace_p (t))
24738fd1498Szrj return true;
24838fd1498Szrj
24938fd1498Szrj if (TYPE_NAME (t) && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t)))
25038fd1498Szrj {
25138fd1498Szrj /* C++ FE uses magic <anon> as assembler names of anonymous types.
25238fd1498Szrj verify that this match with type_in_anonymous_namespace_p. */
25338fd1498Szrj gcc_checking_assert (strcmp ("<anon>",
25438fd1498Szrj IDENTIFIER_POINTER
25538fd1498Szrj (DECL_ASSEMBLER_NAME (TYPE_NAME (t)))));
25638fd1498Szrj return true;
25738fd1498Szrj }
25838fd1498Szrj return false;
25938fd1498Szrj }
26038fd1498Szrj
26138fd1498Szrj #endif /* GCC_IPA_UTILS_H */
26238fd1498Szrj
26338fd1498Szrj
264