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
 156 /* Return vector containing possible targets of polymorphic call E.
 157    If FINALP is non-NULL, store true if the list is complette.
 158    CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
 159    in the target cache.  If user needs to visit every target list
 160    just once, it can memoize them.
 161
 162    Returned vector is placed into cache.  It is NOT caller's responsibility
 163    to free it.  The vector can be freed on cgraph_remove_node call if
 164    the particular node is a virtual function present in the cache.  */
 165
 166 inline vec <cgraph_node *>
 167 possible_polymorphic_call_targets (struct cgraph_edge *e,
 168                                    bool *final = NULL,
 169                                    void **cache_token = NULL,
 170                                    int *nonconstruction_targets = NULL)
 171 {
 172   gcc_checking_assert (e->indirect_info->polymorphic);
 173   ipa_polymorphic_call_context context(e);
 174   return possible_polymorphic_call_targets (e->indirect_info->otr_type,
 175                                             e->indirect_info->otr_token,
 176                                             context,
 177                                             final, cache_token,
 178                                             nonconstruction_targets);
 179 }
 180
 181 /* Same as above but taking OBJ_TYPE_REF as an parameter.  */
 182
 183 inline vec <cgraph_node *>
 184 possible_polymorphic_call_targets (tree ref,
 185                                    gimple call,
 186                                    bool *final = NULL,
 187                                    void **cache_token = NULL)
 188 {
 189   tree otr_type;
 190   HOST_WIDE_INT otr_token;
 191   ipa_polymorphic_call_context context;
 192
 193   get_polymorphic_call_info (current_function_decl,
 194                              ref,
 195                              &otr_type, &otr_token, &context, call);
 196   return possible_polymorphic_call_targets (obj_type_ref_class (ref),
 197                                             tree_to_uhwi
 198                                               (OBJ_TYPE_REF_TOKEN (ref)),
 199                                             context,
 200                                             final, cache_token);
 201 }
 202
 203 /* Dump possible targets of a polymorphic call E into F.  */
 204
 205 inline void
 206 dump_possible_polymorphic_call_targets (FILE *f, struct cgraph_edge *e)
 207 {
 208   gcc_checking_assert (e->indirect_info->polymorphic);
 209   ipa_polymorphic_call_context context(e);
 210   dump_possible_polymorphic_call_targets (f, e->indirect_info->otr_type,
 211                                           e->indirect_info->otr_token,
 212                                           context);
 213 }
 214
 215 /* Return true if N can be possibly target of a polymorphic call of
 216    E.  */
 217
 218 inline bool
 219 possible_polymorphic_call_target_p (struct cgraph_edge *e,
 220                                     struct cgraph_node *n)
 221 {
 222   ipa_polymorphic_call_context context(e);
 223   return possible_polymorphic_call_target_p (e->indirect_info->otr_type,
 224                                              e->indirect_info->otr_token,
 225                                              context, n);
 226 }
 227
 228 /* Return true if N can be possibly target of a polymorphic call of
 229    OBJ_TYPE_REF expression CALL.  */
 230
 231 inline bool
 232 possible_polymorphic_call_target_p (tree call,
 233                                     struct cgraph_node *n)
 234 {
 235   ipa_polymorphic_call_context context;
 236   return possible_polymorphic_call_target_p (obj_type_ref_class (call),
 237                                              tree_to_uhwi
 238                                                (OBJ_TYPE_REF_TOKEN (call)),
 239                                              context,
 240                                              n);
 241 }
 242 #endif  /* GCC_IPA_UTILS_H  */
 243
 244