gcc/ipa-utils.h

   1 /* Utilities for ipa analysis.
   2    Copyright (C) 2004-2014 Free Software Foundation, Inc.
   3    Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 3, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #ifndef GCC_IPA_UTILS_H
  22 #define GCC_IPA_UTILS_H
  23 #include "cgraph.h"
  24
  25 struct ipa_dfs_info {
  26   int dfn_number;
  27   int low_link;
  28   /* This field will have the samy value for any two nodes in the same strongly
  29      connected component.  */
  30   int scc_no;
  31   bool new_node;
  32   bool on_stack;
  33   struct cgraph_node* next_cycle;
  34   PTR aux;
  35 };
  36
  37 /* Context of polymorphic call.  This is used by ipa-devirt walkers of the
  38    type inheritance graph.  */
  39
  40 class ipa_polymorphic_call_context {
  41 public:
  42   /* The called object appears in an object of type OUTER_TYPE
  43      at offset OFFSET.  When information is not 100% reliable, we
  44      use SPECULATIVE_OUTER_TYPE and SPECULATIVE_OFFSET. */
  45   HOST_WIDE_INT offset;
  46   HOST_WIDE_INT speculative_offset;
  47   tree outer_type;
  48   tree speculative_outer_type;
  49   /* True if outer object may be in construction or destruction.  */
  50   bool maybe_in_construction;
  51   /* True if outer object may be of derived type.  */
  52   bool maybe_derived_type;
  53   /* True if speculative outer object may be of derived type.  We always
  54      speculate that construction does not happen.  */
  55   bool speculative_maybe_derived_type;
  56   /* True if the context is invalid and all calls should be redirected
  57      to BUILTIN_UNREACHABLE.  */
  58   bool invalid;
  59
  60   /* Build empty "I know nothing" context.  */
  61   ipa_polymorphic_call_context ();
  62   /* Build polymorphic call context for indirect call E.  */
  63   ipa_polymorphic_call_context (cgraph_edge *e);
  64   /* Build polymorphic call context for IP invariant CST.
  65      If specified, OTR_TYPE specify the type of polymorphic call
  66      that takes CST+OFFSET as a prameter.  */
  67   ipa_polymorphic_call_context (tree cst, tree otr_type = NULL,
  68                                 HOST_WIDE_INT offset = 0);
  69   /* Build context for pointer REF contained in FNDECL at statement STMT.
  70      if INSTANCE is non-NULL, return pointer to the object described by
  71      the context.  */
  72   ipa_polymorphic_call_context (tree fndecl, tree ref, gimple stmt,
  73                                 tree *instance = NULL);
  74
  75   /* Look for vtable stores or constructor calls to work out dynamic type
  76      of memory location.  */
  77   bool get_dynamic_type (tree, tree, tree, gimple);
  78
  79   /* Make context non-speculative.  */
  80   void clear_speculation ();
  81
  82   /* Walk container types and modify context to point to actual class
  83      containing EXPECTED_TYPE as base class.  */
  84   bool restrict_to_inner_class (tree expected_type);
  85
  86 private:
  87   void set_by_decl (tree, HOST_WIDE_INT);
  88   bool set_by_invariant (tree, tree, HOST_WIDE_INT);
  89 };
  90
  91 /* Build polymorphic call context for indirect call E.  */
  92
  93 inline
  94 ipa_polymorphic_call_context::ipa_polymorphic_call_context (cgraph_edge *e)
  95 {
  96   gcc_checking_assert (e->indirect_info->polymorphic);
  97
  98   offset = e->indirect_info->offset;
  99   speculative_offset = e->indirect_info->speculative_offset;
 100   outer_type = e->indirect_info->outer_type;
 101   speculative_outer_type = e->indirect_info->speculative_outer_type;
 102   maybe_in_construction = e->indirect_info->maybe_in_construction;
 103   maybe_derived_type = e->indirect_info->maybe_derived_type;
 104   speculative_maybe_derived_type = e->indirect_info->speculative_maybe_derived_type;
 105   invalid = false;
 106 }
 107
 108 /* Build empty "I know nothing" context.  */
 109
 110 inline
 111 ipa_polymorphic_call_context::ipa_polymorphic_call_context ()
 112 {
 113   offset = 0;
 114   speculative_offset = 0;
 115   outer_type = NULL;
 116   speculative_outer_type = NULL;
 117   maybe_in_construction = true;
 118   maybe_derived_type = true;
 119   speculative_maybe_derived_type = false;
 120   invalid = false;
 121 }
 122
 123 /* Make context non-speculative.  */
 124
 125 inline void
 126 ipa_polymorphic_call_context::clear_speculation ()
 127 {
 128   speculative_outer_type = NULL;
 129   speculative_offset = 0;
 130   speculative_maybe_derived_type = false;
 131 }
 132
 133 /* In ipa-utils.c  */
 134 void ipa_print_order (FILE*, const char *, struct cgraph_node**, int);
 135 int ipa_reduced_postorder (struct cgraph_node **, bool, bool,
 136                           bool (*ignore_edge) (struct cgraph_edge *));
 137 void ipa_free_postorder_info (void);
 138 vec<cgraph_node *> ipa_get_nodes_in_cycle (struct cgraph_node *);
 139 bool ipa_edge_within_scc (struct cgraph_edge *);
 140 int ipa_reverse_postorder (struct cgraph_node **);
 141 tree get_base_var (tree);
 142 void ipa_merge_profiles (struct cgraph_node *dst,
 143                          struct cgraph_node *src);
 144 bool recursive_call_p (tree, tree);
 145
 146 /* In ipa-profile.c  */
 147 bool ipa_propagate_frequency (struct cgraph_node *node);
 148
 149 /* In ipa-devirt.c  */
 150
 151 struct odr_type_d;
 152 typedef odr_type_d *odr_type;
 153 void build_type_inheritance_graph (void);
 154 void update_type_inheritance_graph (void);
 155 vec <cgraph_node *>
 156 possible_polymorphic_call_targets (tree, HOST_WIDE_INT,
 157                                    ipa_polymorphic_call_context,
 158                                    bool *copletep = NULL,
 159                                    void **cache_token = NULL,
 160                                    int *nonconstruction_targets = NULL);
 161 odr_type get_odr_type (tree, bool insert = false);
 162 bool possible_polymorphic_call_target_p (tree ref, gimple stmt, struct cgraph_node *n);
 163 void dump_possible_polymorphic_call_targets (FILE *, tree, HOST_WIDE_INT,
 164                                              const ipa_polymorphic_call_context &);
 165 bool possible_polymorphic_call_target_p (tree, HOST_WIDE_INT,
 166                                          const ipa_polymorphic_call_context &,
 167                                          struct cgraph_node *);
 168 tree method_class_type (const_tree);
 169 bool decl_maybe_in_construction_p (tree, tree, gimple, tree);
 170 tree vtable_pointer_value_to_binfo (const_tree);
 171 bool vtable_pointer_value_to_vtable (const_tree, tree *, unsigned HOST_WIDE_INT *);
 172 void compare_virtual_tables (varpool_node *, varpool_node *);
 173 bool contains_polymorphic_type_p (const_tree);
 174 void register_odr_type (tree);
 175
 176 /* Return vector containing possible targets of polymorphic call E.
 177    If COMPLETEP is non-NULL, store true if the list is complette.
 178    CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
 179    in the target cache.  If user needs to visit every target list
 180    just once, it can memoize them.
 181
 182    Returned vector is placed into cache.  It is NOT caller's responsibility
 183    to free it.  The vector can be freed on cgraph_remove_node call if
 184    the particular node is a virtual function present in the cache.  */
 185
 186 inline vec <cgraph_node *>
 187 possible_polymorphic_call_targets (struct cgraph_edge *e,
 188                                    bool *completep = NULL,
 189                                    void **cache_token = NULL,
 190                                    int *nonconstruction_targets = NULL)
 191 {
 192   ipa_polymorphic_call_context context(e);
 193
 194   return possible_polymorphic_call_targets (e->indirect_info->otr_type,
 195                                             e->indirect_info->otr_token,
 196                                             context,
 197                                             completep, cache_token,
 198                                             nonconstruction_targets);
 199 }
 200
 201 /* Same as above but taking OBJ_TYPE_REF as an parameter.  */
 202
 203 inline vec <cgraph_node *>
 204 possible_polymorphic_call_targets (tree ref,
 205                                    gimple call,
 206                                    bool *completep = NULL,
 207                                    void **cache_token = NULL)
 208 {
 209   ipa_polymorphic_call_context context (current_function_decl, ref, call);
 210
 211   return possible_polymorphic_call_targets (obj_type_ref_class (ref),
 212                                             tree_to_uhwi
 213                                               (OBJ_TYPE_REF_TOKEN (ref)),
 214                                             context,
 215                                             completep, cache_token);
 216 }
 217
 218 /* Dump possible targets of a polymorphic call E into F.  */
 219
 220 inline void
 221 dump_possible_polymorphic_call_targets (FILE *f, struct cgraph_edge *e)
 222 {
 223   ipa_polymorphic_call_context context(e);
 224
 225   dump_possible_polymorphic_call_targets (f, e->indirect_info->otr_type,
 226                                           e->indirect_info->otr_token,
 227                                           context);
 228 }
 229
 230 /* Return true if N can be possibly target of a polymorphic call of
 231    E.  */
 232
 233 inline bool
 234 possible_polymorphic_call_target_p (struct cgraph_edge *e,
 235                                     struct cgraph_node *n)
 236 {
 237   ipa_polymorphic_call_context context(e);
 238
 239   return possible_polymorphic_call_target_p (e->indirect_info->otr_type,
 240                                              e->indirect_info->otr_token,
 241                                              context, n);
 242 }
 243
 244 /* Return true of T is type with One Definition Rule info attached.
 245    It means that either it is anonymous type or it has assembler name
 246    set.  */
 247
 248 static inline bool
 249 odr_type_p (const_tree t)
 250 {
 251   if (type_in_anonymous_namespace_p (t))
 252     return true;
 253   /* We do not have this information when not in LTO, but we do not need
 254      to care, since it is used only for type merging.  */
 255   gcc_assert (in_lto_p || flag_lto);
 256
 257   return (TYPE_NAME (t)
 258           && (DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t))));
 259 }
 260 #endif  /* GCC_IPA_UTILS_H  */
 261
 262