gcc/ipa-modref-tree.h

   1 /* Data structure for the modref pass.
   2    Copyright (C) 2020 Free Software Foundation, Inc.
   3    Contributed by David Cepelik and Jan Hubicka
   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 /* modref_tree represent a decision tree that can be used by alias analysis
  22    oracle to determine whether given memory access can be affected by a function
  23    call.  For every function we collect two trees, one for loads and other
  24    for stores.  Tree consist of following levels:
  25
  26    1) Base: this level represent base alias set of the acecess and refers
  27       to sons (ref nodes). Flag all_refs means that all possible references
  28       are aliasing.
  29
  30       Because for LTO streaming we need to stream types rahter than alias sets
  31       modref_base_node is implemented as a template.
  32    2) Ref: this level represent ref alias set and links to acesses unless
  33       all_refs flag is et.
  34       Again ref is an template to allow LTO streaming.
  35    3) Access: this level represent info about individual accesses.  Presently
  36       we record whether access is trhough a dereference of a function parameter
  37 */
  38
  39 #ifndef GCC_MODREF_TREE_H
  40 #define GCC_MODREF_TREE_H
  41
  42 struct ipa_modref_summary;
  43
  44 /* Memory access.  */
  45 struct GTY(()) modref_access_node
  46 {
  47   /* Index of parameter which specifies the base of access. -1 if base is not
  48      a function parameter.  */
  49   int parm_index;
  50
  51   /* Return true if access node holds no useful info.  */
  52   bool useful_p ()
  53     {
  54       return parm_index != -1;
  55     }
  56 };
  57
  58 template <typename T>
  59 struct GTY((user)) modref_ref_node
  60 {
  61   T ref;
  62   bool every_access;
  63   vec <modref_access_node, va_gc> *accesses;
  64
  65   modref_ref_node (T ref):
  66     ref (ref),
  67     every_access (false),
  68     accesses (NULL)
  69   {}
  70
  71   /* Search REF; return NULL if failed.  */
  72   modref_access_node *search (modref_access_node access)
  73   {
  74     size_t i;
  75     modref_access_node *a;
  76     FOR_EACH_VEC_SAFE_ELT (accesses, i, a)
  77       if (a->parm_index == access.parm_index)
  78         return a;
  79     return NULL;
  80   }
  81
  82   /* Collapse the tree.  */
  83   void collapse ()
  84   {
  85     vec_free (accesses);
  86     accesses = NULL;
  87     every_access = true;
  88   }
  89
  90   /* Insert access with OFFSET and SIZE.
  91      Collapse tree if it has more than MAX_ACCESSES entries.  */
  92   void insert_access (modref_access_node a, size_t max_accesses)
  93   {
  94     /* If this base->ref pair has no access information, bail out.  */
  95     if (every_access)
  96       return;
  97
  98     /* Otherwise, insert a node for the ref of the access under the base.  */
  99     modref_access_node *access_node = search (a);
 100     if (access_node)
 101       return;
 102
 103     /* If this base->ref pair has too many accesses stored, we will clear
 104        all accesses and bail out.  */
 105     if ((accesses && accesses->length () >= max_accesses)
 106         || !a.useful_p ())
 107       {
 108         if (dump_file && a.useful_p ())
 109           fprintf (dump_file,
 110                    "--param param=modref-max-accesses limit reached\n");
 111         collapse ();
 112         return;
 113       }
 114     vec_safe_push (accesses, a);
 115   }
 116 };
 117
 118 /* Base of an access.  */
 119 template <typename T>
 120 struct GTY((user)) modref_base_node
 121 {
 122   T base;
 123   vec <modref_ref_node <T> *, va_gc> *refs;
 124   bool every_ref;
 125
 126   modref_base_node (T base):
 127     base (base),
 128     refs (NULL),
 129     every_ref (false) {}
 130
 131   /* Search REF; return NULL if failed.  */
 132   modref_ref_node <T> *search (T ref)
 133   {
 134     size_t i;
 135     modref_ref_node <T> *n;
 136     FOR_EACH_VEC_SAFE_ELT (refs, i, n)
 137       if (n->ref == ref)
 138         return n;
 139     return NULL;
 140   }
 141
 142   /* Insert REF; collapse tree if there are more than MAX_REFS.  */
 143   modref_ref_node <T> *insert_ref (T ref, size_t max_refs)
 144   {
 145     modref_ref_node <T> *ref_node;
 146
 147     /* If the node is collapsed, don't do anything.  */
 148     if (every_ref)
 149       return NULL;
 150
 151     /* Otherwise, insert a node for the ref of the access under the base.  */
 152     ref_node = search (ref);
 153     if (ref_node)
 154       return ref_node;
 155
 156     /* Collapse the node if too full already.  */
 157     if (refs && refs->length () >= max_refs)
 158       {
 159         if (dump_file)
 160           fprintf (dump_file, "--param param=modref-max-refs limit reached\n");
 161         collapse ();
 162         return NULL;
 163       }
 164
 165     ref_node = new (ggc_alloc <modref_ref_node <T> > ())modref_ref_node <T>
 166                                                                  (ref);
 167     vec_safe_push (refs, ref_node);
 168     return ref_node;
 169   }
 170
 171   void collapse ()
 172   {
 173     size_t i;
 174     modref_ref_node <T> *r;
 175
 176     if (refs)
 177       {
 178         FOR_EACH_VEC_SAFE_ELT (refs, i, r)
 179           {
 180             r->collapse ();
 181             ggc_free (r);
 182           }
 183         vec_free (refs);
 184       }
 185     refs = NULL;
 186     every_ref = true;
 187   }
 188 };
 189
 190 /* Access tree for a single function.  */
 191 template <typename T>
 192 struct GTY((user)) modref_tree
 193 {
 194   vec <modref_base_node <T> *, va_gc> *bases;
 195   size_t max_bases;
 196   size_t max_refs;
 197   size_t max_accesses;
 198   bool every_base;
 199
 200   modref_tree (size_t max_bases, size_t max_refs, size_t max_accesses):
 201     bases (NULL),
 202     max_bases (max_bases),
 203     max_refs (max_refs),
 204     max_accesses (max_accesses),
 205     every_base (false) {}
 206
 207   modref_base_node <T> *insert_base (T base)
 208   {
 209     modref_base_node <T> *base_node;
 210
 211     /* If the node is collapsed, don't do anything.  */
 212     if (every_base)
 213       return NULL;
 214
 215     /* Otherwise, insert a node for the base of the access into the tree.  */
 216     base_node = search (base);
 217     if (base_node)
 218       return base_node;
 219
 220     /* Collapse the node if too full already.  */
 221     if (bases && bases->length () >= max_bases)
 222       {
 223         if (dump_file)
 224           fprintf (dump_file, "--param param=modref-max-bases limit reached\n");
 225         collapse ();
 226         return NULL;
 227       }
 228
 229     base_node = new (ggc_alloc <modref_base_node <T> > ())
 230                          modref_base_node <T> (base);
 231     vec_safe_push (bases, base_node);
 232     return base_node;
 233   }
 234
 235   /* Insert memory access to the tree.  */
 236   void insert (T base, T ref, modref_access_node a)
 237   {
 238     /* No useful information tracked; collapse everything.  */
 239     if (!base && !ref && !a.useful_p ())
 240       {
 241         collapse ();
 242         return;
 243       }
 244
 245     modref_base_node <T> *base_node = insert_base (base);
 246     if (!base_node)
 247       return;
 248     gcc_assert (search (base) != NULL);
 249
 250     modref_ref_node <T> *ref_node = base_node->insert_ref (ref, max_refs);
 251
 252     /* No useful ref information and no useful base; collapse everyting.  */
 253     if (!base && base_node->every_ref)
 254       {
 255         collapse ();
 256         return;
 257       }
 258     if (ref_node)
 259       {
 260         /* No useful ref and access; collapse ref.  */
 261         if (!ref && !a.useful_p ())
 262           ref_node->collapse ();
 263         else
 264           {
 265             ref_node->insert_access (a, max_accesses);
 266             /* If ref has collapses and there is no useful base; collapse
 267                everything.  */
 268             if (!base && !ref && ref_node->every_access)
 269               collapse ();
 270           }
 271       }
 272   }
 273
 274  /* Remove tree branches that are not useful (i.e. they will allways pass).  */
 275
 276  void cleanup ()
 277  {
 278    size_t i, j;
 279    modref_base_node <T> *base_node;
 280    modref_ref_node <T> *ref_node;
 281
 282    if (!bases)
 283      return;
 284
 285    for (i = 0; vec_safe_iterate (bases, i, &base_node);)
 286      {
 287        if (base_node->refs)
 288          for (j = 0; vec_safe_iterate (base_node->refs, j, &ref_node);)
 289            {
 290              if (!ref_node->every_access
 291                  && (!ref_node->accesses
 292                      || !ref_node->accesses->length ()))
 293                {
 294                  base_node->refs->unordered_remove (j);
 295                  vec_free (ref_node->accesses);
 296                  ggc_delete (ref_node);
 297                }
 298              else
 299                j++;
 300            }
 301        if (!base_node->every_ref
 302            && (!base_node->refs || !base_node->refs->length ()))
 303          {
 304            bases->unordered_remove (i);
 305            vec_free (base_node->refs);
 306            ggc_delete (base_node);
 307          }
 308        else
 309          i++;
 310      }
 311    if (bases && !bases->length ())
 312      {
 313        vec_free (bases);
 314        bases = NULL;
 315      }
 316  }
 317
 318   /* Merge OTHER into the tree.
 319      PARM_MAP, if non-NULL, maps parm indexes of callee to caller.  -2 is used
 320      to signalize that parameter is local and does not need to be tracked.  */
 321   void merge (modref_tree <T> *other, vec <int> *parm_map)
 322   {
 323     if (!other)
 324       return;
 325     if (other->every_base)
 326       {
 327         collapse ();
 328         return;
 329       }
 330
 331     size_t i, j, k;
 332     modref_base_node <T> *base_node, *my_base_node;
 333     modref_ref_node <T> *ref_node, *my_ref_node;
 334     modref_access_node *access_node;
 335     FOR_EACH_VEC_SAFE_ELT (other->bases, i, base_node)
 336       {
 337         my_base_node = insert_base (base_node->base);
 338         if (!my_base_node)
 339           continue;
 340
 341         if (base_node->every_ref)
 342           {
 343             my_base_node->collapse ();
 344             continue;
 345           }
 346
 347         FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
 348           {
 349             my_ref_node = my_base_node->insert_ref (ref_node->ref, max_refs);
 350             if (!my_ref_node)
 351               continue;
 352
 353             if (ref_node->every_access)
 354               {
 355                 my_ref_node->collapse ();
 356                 continue;
 357               }
 358             FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
 359               {
 360                 modref_access_node a = *access_node;
 361                 if (a.parm_index != -1 && parm_map)
 362                   {
 363                     if (a.parm_index >= (int)parm_map->length ())
 364                       a.parm_index = -1;
 365                     else if ((*parm_map) [a.parm_index] == -2)
 366                       continue;
 367                     else
 368                       a.parm_index = (*parm_map) [a.parm_index];
 369                   }
 370                 my_ref_node->insert_access (a, max_accesses);
 371               }
 372           }
 373       }
 374     if (parm_map)
 375       cleanup ();
 376   }
 377
 378   /* Copy OTHER to THIS.  */
 379   void copy_from (modref_tree <T> *other)
 380   {
 381     merge (other, NULL);
 382   }
 383
 384   /* Search BASE in tree; return NULL if failed.  */
 385   modref_base_node <T> *search (T base)
 386   {
 387     size_t i;
 388     modref_base_node <T> *n;
 389     FOR_EACH_VEC_SAFE_ELT (bases, i, n)
 390       if (n->base == base)
 391         return n;
 392     return NULL;
 393   }
 394
 395   /* Return ggc allocated instance.  We explicitly call destructors via
 396      ggc_delete and do not want finalizers to be registered and
 397      called at the garbage collection time.  */
 398   static modref_tree<T> *create_ggc (size_t max_bases, size_t max_refs,
 399                                      size_t max_accesses)
 400   {
 401     return new (ggc_alloc_no_dtor<modref_tree<T>> ())
 402          modref_tree<T> (max_bases, max_refs, max_accesses);
 403   }
 404
 405   /* Remove all records and mark tree to alias with everything.  */
 406   void collapse ()
 407   {
 408     size_t i;
 409     modref_base_node <T> *n;
 410
 411     if (bases)
 412       {
 413         FOR_EACH_VEC_SAFE_ELT (bases, i, n)
 414           {
 415             n->collapse ();
 416             ggc_free (n);
 417           }
 418         vec_free (bases);
 419       }
 420     bases = NULL;
 421     every_base = true;
 422   }
 423
 424   /* Release memory.  */
 425   ~modref_tree ()
 426   {
 427     collapse ();
 428   }
 429 };
 430
 431 void modref_c_tests ();
 432
 433 void gt_ggc_mx (modref_tree <int>* const&);
 434 void gt_ggc_mx (modref_tree <tree_node*>* const&);
 435 void gt_pch_nx (modref_tree <int>* const&);
 436 void gt_pch_nx (modref_tree <tree_node*>* const&);
 437 void gt_pch_nx (modref_tree <int>* const&, gt_pointer_operator op, void *cookie);
 438 void gt_pch_nx (modref_tree <tree_node*>* const&, gt_pointer_operator op,
 439                 void *cookie);
 440
 441 void gt_ggc_mx (modref_base_node <int>*);
 442 void gt_ggc_mx (modref_base_node <tree_node*>* &);
 443 void gt_pch_nx (modref_base_node <int>* const&);
 444 void gt_pch_nx (modref_base_node <tree_node*>* const&);
 445 void gt_pch_nx (modref_base_node <int>* const&, gt_pointer_operator op,
 446                 void *cookie);
 447 void gt_pch_nx (modref_base_node <tree_node*>* const&, gt_pointer_operator op,
 448                 void *cookie);
 449
 450 void gt_ggc_mx (modref_ref_node <int>*);
 451 void gt_ggc_mx (modref_ref_node <tree_node*>* &);
 452 void gt_pch_nx (modref_ref_node <int>* const&);
 453 void gt_pch_nx (modref_ref_node <tree_node*>* const&);
 454 void gt_pch_nx (modref_ref_node <int>* const&, gt_pointer_operator op,
 455                 void *cookie);
 456 void gt_pch_nx (modref_ref_node <tree_node*>* const&, gt_pointer_operator op,
 457                 void *cookie);
 458
 459 #endif