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
  57   /* Build empty "I know nothing" context.  */
  58   ipa_polymorphic_call_context ();
  59
  60   /* Build polymorphic call context for indirect call E.  */
  61   ipa_polymorphic_call_context (cgraph_edge *e);
  62
  63   /* Make context non-speculative.  */
  64   void clear_speculation ();
  65
  66   /* Walk container types and modify context to point to actual class
  67      containing EXPECTED_TYPE as base class.  */
  68   bool restrict_to_inner_class (tree expected_type);
  69
  70   /* Look for vtable stores or constructor calls to work out dynamic type
  71      of memory location.  */
  72   bool get_dynamic_type (tree, tree, tree, gimple);
  73 };
  74
  75 /* Build polymorphic call context for indirect call E.  */
  76
  77 inline
  78 ipa_polymorphic_call_context::ipa_polymorphic_call_context (cgraph_edge *e)
  79 {
  80   offset = e->indirect_info->offset;
  81   speculative_offset = e->indirect_info->speculative_offset;
  82   outer_type = e->indirect_info->outer_type;
  83   speculative_outer_type = e->indirect_info->speculative_outer_type;
  84   maybe_in_construction = e->indirect_info->maybe_in_construction;
  85   maybe_derived_type = e->indirect_info->maybe_derived_type;
  86   speculative_maybe_derived_type = e->indirect_info->speculative_maybe_derived_type;
  87 }
  88
  89 /* Build empty "I know nothing" context.  */
  90
  91 inline
  92 ipa_polymorphic_call_context::ipa_polymorphic_call_context ()
  93  : offset(0), speculative_offset(0), outer_type(NULL),
  94    speculative_outer_type(NULL), maybe_in_construction(false),
  95    maybe_derived_type(false), speculative_maybe_derived_type(false)
  96 {
  97 }
  98
  99 /* Make context non-speculative.  */
 100
 101 inline void
 102 ipa_polymorphic_call_context::clear_speculation ()
 103 {
 104   speculative_outer_type = NULL;
 105   speculative_offset = 0;
 106   speculative_maybe_derived_type = false;
 107 }
 108
 109 /* In ipa-utils.c  */
 110 void ipa_print_order (FILE*, const char *, struct cgraph_node**, int);
 111 int ipa_reduced_postorder (struct cgraph_node **, bool, bool,
 112                           bool (*ignore_edge) (struct cgraph_edge *));
 113 void ipa_free_postorder_info (void);
 114 vec<cgraph_node *> ipa_get_nodes_in_cycle (struct cgraph_node *);
 115 bool ipa_edge_within_scc (struct cgraph_edge *);
 116 int ipa_reverse_postorder (struct cgraph_node **);
 117 tree get_base_var (tree);
 118 void ipa_merge_profiles (struct cgraph_node *dst,
 119                          struct cgraph_node *src);
 120 bool recursive_call_p (tree, tree);
 121
 122 /* In ipa-profile.c  */
 123 bool ipa_propagate_frequency (struct cgraph_node *node);
 124
 125 /* In ipa-devirt.c  */
 126
 127 struct odr_type_d;
 128 typedef odr_type_d *odr_type;
 129 void build_type_inheritance_graph (void);
 130 void update_type_inheritance_graph (void);
 131 vec <cgraph_node *>
 132 possible_polymorphic_call_targets (tree, HOST_WIDE_INT,
 133                                    ipa_polymorphic_call_context,
 134                                    bool *final = NULL,
 135                                    void **cache_token = NULL,
 136                                    int *nonconstruction_targets = NULL);
 137 odr_type get_odr_type (tree, bool insert = false);
 138 void dump_possible_polymorphic_call_targets (FILE *, tree, HOST_WIDE_INT,
 139                                              const ipa_polymorphic_call_context &);
 140 bool possible_polymorphic_call_target_p (tree, HOST_WIDE_INT,
 141                                          const ipa_polymorphic_call_context &,
 142                                          struct cgraph_node *);
 143 tree method_class_type (const_tree);
 144 tree get_polymorphic_call_info (tree, tree, tree *,
 145                                 HOST_WIDE_INT *,
 146                                 ipa_polymorphic_call_context *,
 147                                 gimple call = NULL);
 148 bool get_polymorphic_call_info_from_invariant (ipa_polymorphic_call_context *,
 149                                                tree, tree, HOST_WIDE_INT);
 150 bool decl_maybe_in_construction_p (tree, tree, gimple, tree);
 151 tree vtable_pointer_value_to_binfo (const_tree);
 152 bool vtable_pointer_value_to_vtable (const_tree, tree *, unsigned HOST_WIDE_INT *);
 153 void compare_virtual_tables (varpool_node *, varpool_node *);
 154 bool contains_polymorphic_type_p (const_tree);
 155 void register_odr_type (tree);
 156
 157 /* Return vector containing possible targets of polymorphic call E.
 158    If FINALP is non-NULL, store true if the list is complette.
 159    CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
 160    in the target cache.  If user needs to visit every target list
 161    just once, it can memoize them.
 162
 163    Returned vector is placed into cache.  It is NOT caller's responsibility
 164    to free it.  The vector can be freed on cgraph_remove_node call if
 165    the particular node is a virtual function present in the cache.  */
 166
 167 inline vec <cgraph_node *>
 168 possible_polymorphic_call_targets (struct cgraph_edge *e,
 169                                    bool *final = NULL,
 170                                    void **cache_token = NULL,
 171                                    int *nonconstruction_targets = NULL)
 172 {
 173   gcc_checking_assert (e->indirect_info->polymorphic);
 174   ipa_polymorphic_call_context context(e);
 175   return possible_polymorphic_call_targets (e->indirect_info->otr_type,
 176                                             e->indirect_info->otr_token,
 177                                             context,
 178                                             final, cache_token,
 179                                             nonconstruction_targets);
 180 }
 181
 182 /* Same as above but taking OBJ_TYPE_REF as an parameter.  */
 183
 184 inline vec <cgraph_node *>
 185 possible_polymorphic_call_targets (tree ref,
 186                                    gimple call,
 187                                    bool *final = NULL,
 188                                    void **cache_token = NULL)
 189 {
 190   tree otr_type;
 191   HOST_WIDE_INT otr_token;
 192   ipa_polymorphic_call_context context;
 193
 194   get_polymorphic_call_info (current_function_decl,
 195                              ref,
 196                              &otr_type, &otr_token, &context, call);
 197   return possible_polymorphic_call_targets (obj_type_ref_class (ref),
 198                                             tree_to_uhwi
 199                                               (OBJ_TYPE_REF_TOKEN (ref)),
 200                                             context,
 201                                             final, cache_token);
 202 }
 203
 204 /* Dump possible targets of a polymorphic call E into F.  */
 205
 206 inline void
 207 dump_possible_polymorphic_call_targets (FILE *f, struct cgraph_edge *e)
 208 {
 209   gcc_checking_assert (e->indirect_info->polymorphic);
 210   ipa_polymorphic_call_context context(e);
 211   dump_possible_polymorphic_call_targets (f, e->indirect_info->otr_type,
 212                                           e->indirect_info->otr_token,
 213                                           context);
 214 }
 215
 216 /* Return true if N can be possibly target of a polymorphic call of
 217    E.  */
 218
 219 inline bool
 220 possible_polymorphic_call_target_p (struct cgraph_edge *e,
 221                                     struct cgraph_node *n)
 222 {
 223   ipa_polymorphic_call_context context(e);
 224   return possible_polymorphic_call_target_p (e->indirect_info->otr_type,
 225                                              e->indirect_info->otr_token,
 226                                              context, n);
 227 }
 228
 229 /* Return true if N can be possibly target of a polymorphic call of
 230    OBJ_TYPE_REF expression CALL.  */
 231
 232 inline bool
 233 possible_polymorphic_call_target_p (tree call,
 234                                     struct cgraph_node *n)
 235 {
 236   ipa_polymorphic_call_context context;
 237   return possible_polymorphic_call_target_p (obj_type_ref_class (call),
 238                                              tree_to_uhwi
 239                                                (OBJ_TYPE_REF_TOKEN (call)),
 240                                              context,
 241                                              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