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 access 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 rather than alias sets
  31       modref_base_node is implemented as a template.
  32    2) Ref: this level represent ref alias set and links to accesses unless
  33       all_refs flag is set.
  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 through 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
  48   /* Access range information (in bits).  */
  49   poly_int64 offset;
  50   poly_int64 size;
  51   poly_int64 max_size;
  52
  53   /* Offset from parameter pointer to the base of the access (in bytes).  */
  54   poly_int64 parm_offset;
  55
  56   /* Index of parameter which specifies the base of access. -1 if base is not
  57      a function parameter.  */
  58   int parm_index;
  59   bool parm_offset_known;
  60
  61   /* Return true if access node holds no useful info.  */
  62   bool useful_p () const
  63     {
  64       return parm_index != -1;
  65     }
  66   /* Return true if range info is useful.  */
  67   bool range_info_useful_p () const
  68     {
  69       return parm_index != -1 && parm_offset_known;
  70     }
  71   /* Return true if both accesses are the same.  */
  72   bool operator == (modref_access_node &a) const
  73     {
  74       if (parm_index != a.parm_index)
  75         return false;
  76       if (parm_index >= 0)
  77         {
  78           if (parm_offset_known != a.parm_offset_known)
  79             return false;
  80           if (parm_offset_known
  81               && !known_eq (parm_offset, a.parm_offset))
  82             return false;
  83         }
  84       if (range_info_useful_p ()
  85           && (!known_eq (a.offset, offset)
  86               || !known_eq (a.size, size)
  87               || !known_eq (a.max_size, max_size)))
  88         return false;
  89       return true;
  90     }
  91 };
  92
  93 /* Access node specifying no useful info.  */
  94 const modref_access_node unspecified_modref_access_node
  95                  = {0, -1, -1, 0, -1, false};
  96
  97 template <typename T>
  98 struct GTY((user)) modref_ref_node
  99 {
 100   T ref;
 101   bool every_access;
 102   vec <modref_access_node, va_gc> *accesses;
 103
 104   modref_ref_node (T ref):
 105     ref (ref),
 106     every_access (false),
 107     accesses (NULL)
 108   {}
 109
 110   /* Search REF; return NULL if failed.  */
 111   modref_access_node *search (modref_access_node access)
 112   {
 113     size_t i;
 114     modref_access_node *a;
 115     FOR_EACH_VEC_SAFE_ELT (accesses, i, a)
 116       if (*a == access)
 117         return a;
 118     return NULL;
 119   }
 120
 121   /* Collapse the tree.  */
 122   void collapse ()
 123   {
 124     vec_free (accesses);
 125     accesses = NULL;
 126     every_access = true;
 127   }
 128
 129   /* Insert access with OFFSET and SIZE.
 130      Collapse tree if it has more than MAX_ACCESSES entries.
 131      Return true if record was changed.  */
 132   bool insert_access (modref_access_node a, size_t max_accesses)
 133   {
 134     /* If this base->ref pair has no access information, bail out.  */
 135     if (every_access)
 136       return false;
 137
 138     /* Otherwise, insert a node for the ref of the access under the base.  */
 139     modref_access_node *access_node = search (a);
 140     if (access_node)
 141       return false;
 142
 143     /* If this base->ref pair has too many accesses stored, we will clear
 144        all accesses and bail out.  */
 145     if ((accesses && accesses->length () >= max_accesses)
 146         || !a.useful_p ())
 147       {
 148         if (dump_file && a.useful_p ())
 149           fprintf (dump_file,
 150                    "--param param=modref-max-accesses limit reached\n");
 151         collapse ();
 152         return true;
 153       }
 154     vec_safe_push (accesses, a);
 155     return true;
 156   }
 157 };
 158
 159 /* Base of an access.  */
 160 template <typename T>
 161 struct GTY((user)) modref_base_node
 162 {
 163   T base;
 164   vec <modref_ref_node <T> *, va_gc> *refs;
 165   bool every_ref;
 166
 167   modref_base_node (T base):
 168     base (base),
 169     refs (NULL),
 170     every_ref (false) {}
 171
 172   /* Search REF; return NULL if failed.  */
 173   modref_ref_node <T> *search (T ref)
 174   {
 175     size_t i;
 176     modref_ref_node <T> *n;
 177     FOR_EACH_VEC_SAFE_ELT (refs, i, n)
 178       if (n->ref == ref)
 179         return n;
 180     return NULL;
 181   }
 182
 183   /* Insert REF; collapse tree if there are more than MAX_REFS.
 184      Return inserted ref and if CHANGED is non-null set it to true if
 185      something changed.  */
 186   modref_ref_node <T> *insert_ref (T ref, size_t max_refs,
 187                                    bool *changed = NULL)
 188   {
 189     modref_ref_node <T> *ref_node;
 190
 191     /* If the node is collapsed, don't do anything.  */
 192     if (every_ref)
 193       return NULL;
 194
 195     /* Otherwise, insert a node for the ref of the access under the base.  */
 196     ref_node = search (ref);
 197     if (ref_node)
 198       return ref_node;
 199
 200     if (changed)
 201       *changed = true;
 202
 203     /* Collapse the node if too full already.  */
 204     if (refs && refs->length () >= max_refs)
 205       {
 206         if (dump_file)
 207           fprintf (dump_file, "--param param=modref-max-refs limit reached\n");
 208         collapse ();
 209         return NULL;
 210       }
 211
 212     ref_node = new (ggc_alloc <modref_ref_node <T> > ())modref_ref_node <T>
 213                                                                  (ref);
 214     vec_safe_push (refs, ref_node);
 215     return ref_node;
 216   }
 217
 218   void collapse ()
 219   {
 220     size_t i;
 221     modref_ref_node <T> *r;
 222
 223     if (refs)
 224       {
 225         FOR_EACH_VEC_SAFE_ELT (refs, i, r)
 226           {
 227             r->collapse ();
 228             ggc_free (r);
 229           }
 230         vec_free (refs);
 231       }
 232     refs = NULL;
 233     every_ref = true;
 234   }
 235 };
 236
 237 /* Map translating parameters across function call.  */
 238
 239 struct modref_parm_map
 240 {
 241   /* Index of parameter we translate to.
 242      -1 indicates that parameter is unknown
 243      -2 indicates that parameter points to local memory and access can be
 244         discarded.  */
 245   int parm_index;
 246   bool parm_offset_known;
 247   poly_int64 parm_offset;
 248 };
 249
 250 /* Access tree for a single function.  */
 251 template <typename T>
 252 struct GTY((user)) modref_tree
 253 {
 254   vec <modref_base_node <T> *, va_gc> *bases;
 255   size_t max_bases;
 256   size_t max_refs;
 257   size_t max_accesses;
 258   bool every_base;
 259
 260   modref_tree (size_t max_bases, size_t max_refs, size_t max_accesses):
 261     bases (NULL),
 262     max_bases (max_bases),
 263     max_refs (max_refs),
 264     max_accesses (max_accesses),
 265     every_base (false) {}
 266
 267   /* Insert BASE; collapse tree if there are more than MAX_REFS.
 268      Return inserted base and if CHANGED is non-null set it to true if
 269      something changed.  */
 270
 271   modref_base_node <T> *insert_base (T base, bool *changed = NULL)
 272   {
 273     modref_base_node <T> *base_node;
 274
 275     /* If the node is collapsed, don't do anything.  */
 276     if (every_base)
 277       return NULL;
 278
 279     /* Otherwise, insert a node for the base of the access into the tree.  */
 280     base_node = search (base);
 281     if (base_node)
 282       return base_node;
 283
 284     if (changed)
 285       *changed = true;
 286
 287     /* Collapse the node if too full already.  */
 288     if (bases && bases->length () >= max_bases)
 289       {
 290         if (dump_file)
 291           fprintf (dump_file, "--param param=modref-max-bases limit reached\n");
 292         collapse ();
 293         return NULL;
 294       }
 295
 296     base_node = new (ggc_alloc <modref_base_node <T> > ())
 297                          modref_base_node <T> (base);
 298     vec_safe_push (bases, base_node);
 299     return base_node;
 300   }
 301
 302   /* Insert memory access to the tree.
 303      Return true if something changed.  */
 304   bool insert (T base, T ref, modref_access_node a)
 305   {
 306     if (every_base)
 307       return false;
 308
 309     bool changed = false;
 310
 311     /* No useful information tracked; collapse everything.  */
 312     if (!base && !ref && !a.useful_p ())
 313       {
 314         collapse ();
 315         return true;
 316       }
 317
 318     modref_base_node <T> *base_node = insert_base (base, &changed);
 319     if (!base_node || base_node->every_ref)
 320       return changed;
 321     gcc_checking_assert (search (base) != NULL);
 322
 323     /* No useful ref info tracked; collapse base.  */
 324     if (!ref && !a.useful_p ())
 325       {
 326         base_node->collapse ();
 327         return true;
 328       }
 329
 330     modref_ref_node <T> *ref_node = base_node->insert_ref (ref, max_refs,
 331                                                            &changed);
 332
 333     /* If we failed to insert ref, just see if there is a cleanup possible.  */
 334     if (!ref_node)
 335       {
 336         /* No useful ref information and no useful base; collapse everything.  */
 337         if (!base && base_node->every_ref)
 338           {
 339             collapse ();
 340             gcc_checking_assert (changed);
 341           }
 342         else if (changed)
 343           cleanup ();
 344       }
 345     else
 346       {
 347         if (ref_node->every_access)
 348           return changed;
 349         changed |= ref_node->insert_access (a, max_accesses);
 350         /* See if we failed to add useful access.  */
 351         if (ref_node->every_access)
 352           {
 353             /* Collapse everything if there is no useful base and ref.  */
 354             if (!base && !ref)
 355               {
 356                 collapse ();
 357                 gcc_checking_assert (changed);
 358               }
 359             /* Collapse base if there is no useful ref.  */
 360             else if (!ref)
 361               {
 362                 base_node->collapse ();
 363                 gcc_checking_assert (changed);
 364               }
 365           }
 366       }
 367     return changed;
 368   }
 369
 370  /* Remove tree branches that are not useful (i.e. they will always pass).  */
 371
 372  void cleanup ()
 373  {
 374    size_t i, j;
 375    modref_base_node <T> *base_node;
 376    modref_ref_node <T> *ref_node;
 377
 378    if (!bases)
 379      return;
 380
 381    for (i = 0; vec_safe_iterate (bases, i, &base_node);)
 382      {
 383        if (base_node->refs)
 384          for (j = 0; vec_safe_iterate (base_node->refs, j, &ref_node);)
 385            {
 386              if (!ref_node->every_access
 387                  && (!ref_node->accesses
 388                      || !ref_node->accesses->length ()))
 389                {
 390                  base_node->refs->unordered_remove (j);
 391                  vec_free (ref_node->accesses);
 392                  ggc_delete (ref_node);
 393                }
 394              else
 395                j++;
 396            }
 397        if (!base_node->every_ref
 398            && (!base_node->refs || !base_node->refs->length ()))
 399          {
 400            bases->unordered_remove (i);
 401            vec_free (base_node->refs);
 402            ggc_delete (base_node);
 403          }
 404        else
 405          i++;
 406      }
 407    if (bases && !bases->length ())
 408      {
 409        vec_free (bases);
 410        bases = NULL;
 411      }
 412  }
 413
 414   /* Merge OTHER into the tree.
 415      PARM_MAP, if non-NULL, maps parm indexes of callee to caller.  -2 is used
 416      to signalize that parameter is local and does not need to be tracked.
 417      Return true if something has changed.  */
 418   bool merge (modref_tree <T> *other, vec <modref_parm_map> *parm_map)
 419   {
 420     if (!other || every_base)
 421       return false;
 422     if (other->every_base)
 423       {
 424         collapse ();
 425         return true;
 426       }
 427
 428     bool changed = false;
 429     size_t i, j, k;
 430     modref_base_node <T> *base_node, *my_base_node;
 431     modref_ref_node <T> *ref_node;
 432     modref_access_node *access_node;
 433     bool release = false;
 434
 435     /* For self-recursive functions we may end up merging summary into itself;
 436        produce copy first so we do not modify summary under our own hands.  */
 437     if (other == this)
 438       {
 439         release = true;
 440         other = modref_tree<T>::create_ggc (max_bases, max_refs, max_accesses);
 441         other->copy_from (this);
 442       }
 443
 444     FOR_EACH_VEC_SAFE_ELT (other->bases, i, base_node)
 445       {
 446         if (base_node->every_ref)
 447           {
 448             my_base_node = insert_base (base_node->base, &changed);
 449             if (my_base_node && !my_base_node->every_ref)
 450               {
 451                 my_base_node->collapse ();
 452                 cleanup ();
 453                 changed = true;
 454               }
 455           }
 456         else
 457           FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
 458             {
 459               if (ref_node->every_access)
 460                 {
 461                   changed |= insert (base_node->base,
 462                                      ref_node->ref,
 463                                      unspecified_modref_access_node);
 464                 }
 465               else
 466                 FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
 467                   {
 468                     modref_access_node a = *access_node;
 469
 470                     if (a.parm_index != -1 && parm_map)
 471                       {
 472                         if (a.parm_index >= (int)parm_map->length ())
 473                           a.parm_index = -1;
 474                         else if ((*parm_map) [a.parm_index].parm_index == -2)
 475                           continue;
 476                         else
 477                           {
 478                             a.parm_offset
 479                                  += (*parm_map) [a.parm_index].parm_offset;
 480                             a.parm_offset_known
 481                                  &= (*parm_map)
 482                                          [a.parm_index].parm_offset_known;
 483                             a.parm_index
 484                                  = (*parm_map) [a.parm_index].parm_index;
 485                           }
 486                       }
 487                     changed |= insert (base_node->base, ref_node->ref, a);
 488                   }
 489             }
 490       }
 491     if (release)
 492       ggc_delete (other);
 493     return changed;
 494   }
 495
 496   /* Copy OTHER to THIS.  */
 497   void copy_from (modref_tree <T> *other)
 498   {
 499     merge (other, NULL);
 500   }
 501
 502   /* Search BASE in tree; return NULL if failed.  */
 503   modref_base_node <T> *search (T base)
 504   {
 505     size_t i;
 506     modref_base_node <T> *n;
 507     FOR_EACH_VEC_SAFE_ELT (bases, i, n)
 508       if (n->base == base)
 509         return n;
 510     return NULL;
 511   }
 512
 513   /* Return ggc allocated instance.  We explicitly call destructors via
 514      ggc_delete and do not want finalizers to be registered and
 515      called at the garbage collection time.  */
 516   static modref_tree<T> *create_ggc (size_t max_bases, size_t max_refs,
 517                                      size_t max_accesses)
 518   {
 519     return new (ggc_alloc_no_dtor<modref_tree<T>> ())
 520          modref_tree<T> (max_bases, max_refs, max_accesses);
 521   }
 522
 523   /* Remove all records and mark tree to alias with everything.  */
 524   void collapse ()
 525   {
 526     size_t i;
 527     modref_base_node <T> *n;
 528
 529     if (bases)
 530       {
 531         FOR_EACH_VEC_SAFE_ELT (bases, i, n)
 532           {
 533             n->collapse ();
 534             ggc_free (n);
 535           }
 536         vec_free (bases);
 537       }
 538     bases = NULL;
 539     every_base = true;
 540   }
 541
 542   /* Release memory.  */
 543   ~modref_tree ()
 544   {
 545     collapse ();
 546   }
 547
 548   /* Update parameter indexes in TT according to MAP.  */
 549   void
 550   remap_params (vec <int> *map)
 551   {
 552     size_t i;
 553     modref_base_node <T> *base_node;
 554     FOR_EACH_VEC_SAFE_ELT (bases, i, base_node)
 555       {
 556         size_t j;
 557         modref_ref_node <T> *ref_node;
 558         FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
 559           {
 560             size_t k;
 561             modref_access_node *access_node;
 562             FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
 563               if (access_node->parm_index > 0)
 564                 {
 565                   if (access_node->parm_index < (int)map->length ())
 566                     access_node->parm_index = (*map)[access_node->parm_index];
 567                   else
 568                     access_node->parm_index = -1;
 569                 }
 570           }
 571       }
 572   }
 573 };
 574
 575 void modref_c_tests ();
 576
 577 void gt_ggc_mx (modref_tree <int>* const&);
 578 void gt_ggc_mx (modref_tree <tree_node*>* const&);
 579 void gt_pch_nx (modref_tree <int>* const&);
 580 void gt_pch_nx (modref_tree <tree_node*>* const&);
 581 void gt_pch_nx (modref_tree <int>* const&, gt_pointer_operator op, void *cookie);
 582 void gt_pch_nx (modref_tree <tree_node*>* const&, gt_pointer_operator op,
 583                 void *cookie);
 584
 585 void gt_ggc_mx (modref_base_node <int>*);
 586 void gt_ggc_mx (modref_base_node <tree_node*>* &);
 587 void gt_pch_nx (modref_base_node <int>* const&);
 588 void gt_pch_nx (modref_base_node <tree_node*>* const&);
 589 void gt_pch_nx (modref_base_node <int>* const&, gt_pointer_operator op,
 590                 void *cookie);
 591 void gt_pch_nx (modref_base_node <tree_node*>* const&, gt_pointer_operator op,
 592                 void *cookie);
 593
 594 void gt_ggc_mx (modref_ref_node <int>*);
 595 void gt_ggc_mx (modref_ref_node <tree_node*>* &);
 596 void gt_pch_nx (modref_ref_node <int>* const&);
 597 void gt_pch_nx (modref_ref_node <tree_node*>* const&);
 598 void gt_pch_nx (modref_ref_node <int>* const&, gt_pointer_operator op,
 599                 void *cookie);
 600 void gt_pch_nx (modref_ref_node <tree_node*>* const&, gt_pointer_operator op,
 601                 void *cookie);
 602
 603 #endif