gcc/rtl-ssa/access-utils.h

   1 // Access-related utilities for RTL SSA                             -*- C++ -*-
   2 // Copyright (C) 2020-2024 Free Software Foundation, Inc.
   3 //
   4 // This file is part of GCC.
   5 //
   6 // GCC is free software; you can redistribute it and/or modify it under
   7 // the terms of the GNU General Public License as published by the Free
   8 // Software Foundation; either version 3, or (at your option) any later
   9 // version.
  10 //
  11 // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  12 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 // for more details.
  15 //
  16 // You should have received a copy of the GNU General Public License
  17 // along with GCC; see the file COPYING3.  If not see
  18 // <http://www.gnu.org/licenses/>.
  19
  20 namespace rtl_ssa {
  21
  22 // Return a referene to the whole of register REGNO.
  23 inline resource_info
  24 full_register (unsigned int regno)
  25 {
  26   return { GET_MODE (regno_reg_rtx[regno]), regno };
  27 }
  28
  29 // Return true if sorted array ACCESSES includes an access to hard registers.
  30 inline bool
  31 accesses_include_hard_registers (const access_array &accesses)
  32 {
  33   return accesses.size () && HARD_REGISTER_NUM_P (accesses.front ()->regno ());
  34 }
  35
  36 // Return true if ACCESSES includes a reference to a non-fixed hard register.
  37 inline bool
  38 accesses_include_nonfixed_hard_registers (access_array accesses)
  39 {
  40   for (access_info *access : accesses)
  41     {
  42       if (!HARD_REGISTER_NUM_P (access->regno ()))
  43         break;
  44       if (!fixed_regs[access->regno ()])
  45         return true;
  46     }
  47   return false;
  48 }
  49
  50 // Return true if sorted array ACCESSES includes an access to memory.
  51 inline bool
  52 accesses_include_memory (const access_array &accesses)
  53 {
  54   return accesses.size () && accesses.back ()->is_mem ();
  55 }
  56
  57 // If sorted array ACCESSES includes an access to memory, return the access,
  58 // otherwise return null.
  59 template<typename T>
  60 inline auto
  61 memory_access (T accesses) -> decltype (accesses[0])
  62 {
  63   if (accesses.size () && accesses.back ()->is_mem ())
  64     return accesses.back ();
  65   return nullptr;
  66 }
  67
  68 // If ACCESSES has a memory access, drop it.  Otherwise, return ACCESSES
  69 // unchanged.
  70 template<typename T>
  71 inline T
  72 drop_memory_access (T accesses)
  73 {
  74   if (!memory_access (accesses))
  75     return accesses;
  76
  77   access_array arr (accesses);
  78   return T (arr.begin (), accesses.size () - 1);
  79 }
  80
  81 // Filter ACCESSES to return an access_array of only those accesses that
  82 // satisfy PREDICATE.  Alocate the new array above WATERMARK.
  83 template<typename T, typename FilterPredicate>
  84 inline T
  85 filter_accesses (obstack_watermark &watermark,
  86                  T accesses,
  87                  FilterPredicate predicate)
  88 {
  89   access_array_builder builder (watermark);
  90   builder.reserve (accesses.size ());
  91   for (auto access : accesses)
  92     if (predicate (access))
  93       builder.quick_push (access);
  94   return T (builder.finish ());
  95 }
  96
  97 // Given an array of ACCESSES, remove any access with regno REGNO.
  98 // Allocate the new access array above WM.
  99 template<typename T>
 100 inline T
 101 remove_regno_access (obstack_watermark &watermark,
 102                      T accesses, unsigned int regno)
 103 {
 104   using Access = decltype (accesses[0]);
 105   auto pred = [regno](Access a) { return a->regno () != regno; };
 106   return filter_accesses (watermark, accesses, pred);
 107 }
 108
 109 // As above, but additionally check that we actually did remove an access.
 110 template<typename T>
 111 inline T
 112 check_remove_regno_access (obstack_watermark &watermark,
 113                            T accesses, unsigned regno)
 114 {
 115   auto orig_size = accesses.size ();
 116   auto result = remove_regno_access (watermark, accesses, regno);
 117   gcc_assert (result.size () < orig_size);
 118   return result;
 119 }
 120
 121 // If sorted array ACCESSES includes a reference to REGNO, return the
 122 // access, otherwise return null.
 123 template<typename T>
 124 inline auto
 125 find_access (T accesses, unsigned int regno) -> decltype (accesses[0])
 126 {
 127   unsigned int start = 0;
 128   unsigned int end = accesses.size ();
 129   while (start < end)
 130     {
 131       unsigned int mid = (start + end) / 2;
 132       unsigned int found = accesses[mid]->regno ();
 133       if (found == regno)
 134         return accesses[mid];
 135       if (found < regno)
 136         start = mid + 1;
 137       else
 138         end = mid;
 139     }
 140   return nullptr;
 141 }
 142
 143 // If sorted array ACCESSES includes a reference to REGNO, return the
 144 // index of the access, otherwise return -1.
 145 inline int
 146 find_access_index (access_array accesses, unsigned int regno)
 147 {
 148   unsigned int start = 0;
 149   unsigned int end = accesses.size ();
 150   while (start < end)
 151     {
 152       unsigned int mid = (start + end) / 2;
 153       unsigned int found = accesses[mid]->regno ();
 154       if (found == regno)
 155         return mid;
 156       if (found < regno)
 157         start = mid + 1;
 158       else
 159         end = mid;
 160     }
 161   return -1;
 162 }
 163
 164 // If ACCESS is a set whose result is used by at least one instruction,
 165 // return the access as a set_info, otherwise return null.
 166 inline const set_info *
 167 set_with_nondebug_insn_uses (const access_info *access)
 168 {
 169   if (access->is_set_with_nondebug_insn_uses ())
 170     // No need for as_a; this test is just as definitive.
 171     return static_cast<const set_info *> (access);
 172   return nullptr;
 173 }
 174
 175 // A non-const version of the above.
 176 inline set_info *
 177 set_with_nondebug_insn_uses (access_info *access)
 178 {
 179   if (access->is_set_with_nondebug_insn_uses ())
 180     return static_cast<set_info *> (access);
 181   return nullptr;
 182 }
 183
 184 // ACCESS is known to be associated with an instruction rather than
 185 // a phi node.  Return which instruction that is.
 186 inline insn_info *
 187 access_insn (const access_info *access)
 188 {
 189   // In release builds this function reduces to a single pointer reference.
 190   if (auto *def = dyn_cast<const def_info *> (access))
 191     return def->insn ();
 192   return as_a<const use_info *> (access)->insn ();
 193 }
 194
 195 // If ACCESS records a use, return the value that it uses.  If ACCESS records
 196 // a set, return that set.  If ACCESS records a clobber, return null.
 197 inline const set_info *
 198 access_value (const access_info *access)
 199 {
 200   if (!access)
 201     return nullptr;
 202
 203   if (auto *use = dyn_cast<const use_info *> (access))
 204     return use->def ();
 205
 206   return dyn_cast<const set_info *> (access);
 207 }
 208
 209 // A non-const version of the above.
 210 inline set_info *
 211 access_value (access_info *access)
 212 {
 213   auto *const_access = const_cast<const access_info *> (access);
 214   return const_cast<set_info *> (access_value (const_access));
 215 }
 216
 217 // If ACCESS is a degenerate phi, return the set_info that defines its input,
 218 // otherwise return ACCESS itself.
 219 template<typename T>
 220 inline const T *
 221 look_through_degenerate_phi (const T *access)
 222 {
 223   if (auto *phi = dyn_cast<const phi_info *> (access))
 224     if (phi->is_degenerate ())
 225       return phi->input_value (0);
 226   return access;
 227 }
 228
 229 // A non-const version of the above.
 230 template<typename T>
 231 inline T *
 232 look_through_degenerate_phi (T *access)
 233 {
 234   auto *const_access = const_cast<const T *> (access);
 235   return const_cast<T *> (look_through_degenerate_phi (const_access));
 236 }
 237
 238 // If CLOBBER is in a group, return the first clobber in the group,
 239 // otherwise return CLOBBER itself.
 240 inline clobber_info *
 241 first_clobber_in_group (clobber_info *clobber)
 242 {
 243   if (clobber->is_in_group ())
 244     return clobber->group ()->first_clobber ();
 245   return clobber;
 246 }
 247
 248 // If CLOBBER is in a group, return the last clobber in the group,
 249 // otherwise return CLOBBER itself.
 250 inline clobber_info *
 251 last_clobber_in_group (clobber_info *clobber)
 252 {
 253   if (clobber->is_in_group ())
 254     return clobber->group ()->last_clobber ();
 255   return clobber;
 256 }
 257
 258 // If DEF is a clobber in a group, return the containing group,
 259 // otherwise return DEF.
 260 inline def_mux
 261 clobber_group_or_single_def (def_info *def)
 262 {
 263   if (auto *clobber = dyn_cast<clobber_info *> (def))
 264     if (clobber->is_in_group ())
 265       return clobber->group ();
 266   return def;
 267 }
 268
 269 // Return the first definition associated with NODE.  If NODE holds
 270 // a single set, the result is that set.  If NODE holds a clobber_group,
 271 // the result is the first clobber in the group.
 272 inline def_info *
 273 first_def (def_node *node)
 274 {
 275   return node->first_def ();
 276 }
 277
 278 // Likewise for something that is either a node or a single definition.
 279 inline def_info *
 280 first_def (def_mux mux)
 281 {
 282   return mux.first_def ();
 283 }
 284
 285 // Return the last definition associated with NODE.  If NODE holds
 286 // a single set, the result is that set.  If NODE holds a clobber_group,
 287 // the result is the last clobber in the group.
 288 inline def_info *
 289 last_def (def_node *node)
 290 {
 291   if (auto *group = dyn_cast<clobber_group *> (node))
 292     return group->last_clobber ();
 293   return node->first_def ();
 294 }
 295
 296 // Likewise for something that is either a node or a single definition.
 297 inline def_info *
 298 last_def (def_mux mux)
 299 {
 300   return mux.last_def ();
 301 }
 302
 303 // If INSN's definitions contain a single set, return that set, otherwise
 304 // return null.
 305 inline set_info *
 306 single_set_info (insn_info *insn)
 307 {
 308   set_info *set = nullptr;
 309   for (auto def : insn->defs ())
 310     if (auto this_set = dyn_cast<set_info *> (def))
 311       {
 312         if (set)
 313           return nullptr;
 314         set = this_set;
 315       }
 316   return set;
 317 }
 318
 319 int lookup_use (splay_tree<use_info *> &, insn_info *);
 320 int lookup_def (def_splay_tree &, insn_info *);
 321 int lookup_clobber (clobber_tree &, insn_info *);
 322 int lookup_call_clobbers (insn_call_clobbers_tree &, insn_info *);
 323
 324 // Search backwards from immediately before INSN for the first instruction
 325 // recorded in TREE, ignoring any instruction I for which IGNORE (I) is true.
 326 // Return null if no such instruction exists.
 327 template<typename IgnorePredicate>
 328 insn_info *
 329 prev_call_clobbers_ignoring (insn_call_clobbers_tree &tree, insn_info *insn,
 330                              IgnorePredicate ignore)
 331 {
 332   if (!tree)
 333     return nullptr;
 334
 335   int comparison = lookup_call_clobbers (tree, insn);
 336   while (comparison <= 0 || ignore (tree->insn ()))
 337     {
 338       if (!tree.splay_prev_node ())
 339         return nullptr;
 340
 341       comparison = 1;
 342     }
 343   return tree->insn ();
 344 }
 345
 346 // Search forwards from immediately after INSN for the first instruction
 347 // recorded in TREE, ignoring any instruction I for which IGNORE (I) is true.
 348 // Return null if no such instruction exists.
 349 template<typename IgnorePredicate>
 350 insn_info *
 351 next_call_clobbers_ignoring (insn_call_clobbers_tree &tree, insn_info *insn,
 352                              IgnorePredicate ignore)
 353 {
 354   if (!tree)
 355     return nullptr;
 356
 357   int comparison = lookup_call_clobbers (tree, insn);
 358   while (comparison >= 0 || ignore (tree->insn ()))
 359     {
 360       if (!tree.splay_next_node ())
 361         return nullptr;
 362
 363       comparison = -1;
 364     }
 365   return tree->insn ();
 366 }
 367
 368 // Search forwards from immediately after INSN for the first instruction
 369 // recorded in TREE.  Return null if no such instruction exists.
 370 inline insn_info *
 371 next_call_clobbers (insn_call_clobbers_tree &tree, insn_info *insn)
 372 {
 373   auto ignore = [](const insn_info *) { return false; };
 374   return next_call_clobbers_ignoring (tree, insn, ignore);
 375 }
 376
 377 // If ACCESS is a set, return the first use of ACCESS by a nondebug insn I
 378 // for which IGNORE (I) is false.  Return null if ACCESS is not a set or if
 379 // no such use exists.
 380 template<typename IgnorePredicate>
 381 inline use_info *
 382 first_nondebug_insn_use_ignoring (const access_info *access,
 383                                   IgnorePredicate ignore)
 384 {
 385   if (const set_info *set = set_with_nondebug_insn_uses (access))
 386     {
 387       // Written this way to emphasize to the compiler that first_use
 388       // must be nonnull in this situation.
 389       use_info *use = set->first_use ();
 390       do
 391         {
 392           if (!ignore (use->insn ()))
 393             return use;
 394           use = use->next_nondebug_insn_use ();
 395         }
 396       while (use);
 397     }
 398   return nullptr;
 399 }
 400
 401 // If ACCESS is a set, return the last use of ACCESS by a nondebug insn I for
 402 // which IGNORE (I) is false.  Return null if ACCESS is not a set or if no
 403 // such use exists.
 404 template<typename IgnorePredicate>
 405 inline use_info *
 406 last_nondebug_insn_use_ignoring (const access_info *access,
 407                                  IgnorePredicate ignore)
 408 {
 409   if (const set_info *set = set_with_nondebug_insn_uses (access))
 410     {
 411       // Written this way to emphasize to the compiler that
 412       // last_nondebug_insn_use must be nonnull in this situation.
 413       use_info *use = set->last_nondebug_insn_use ();
 414       do
 415         {
 416           if (!ignore (use->insn ()))
 417             return use;
 418           use = use->prev_use ();
 419         }
 420       while (use);
 421     }
 422   return nullptr;
 423 }
 424
 425 // If DEF is null, return null.
 426 //
 427 // Otherwise, search backwards for an access to DEF->resource (), starting at
 428 // the end of DEF's live range.  Ignore clobbers if IGNORE_CLOBBERS_SETTING
 429 // is YES, otherwise treat them like any other access.  Also ignore any
 430 // access A for which IGNORE (access_insn (A)) is true.
 431 //
 432 // Thus if DEF is a set that is used by nondebug insns, the first access
 433 // that the function considers is the last such use of the set.  Otherwise,
 434 // the first access that the function considers is DEF itself.
 435 //
 436 // Return the access found, or null if there is no access that meets
 437 // the criteria.
 438 //
 439 // Note that this function does not consider separately-recorded call clobbers,
 440 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
 441 template<typename IgnorePredicate>
 442 access_info *
 443 last_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
 444                       IgnorePredicate ignore)
 445 {
 446   while (def)
 447     {
 448       auto *clobber = dyn_cast<clobber_info *> (def);
 449       if (clobber && ignore_clobbers_setting == ignore_clobbers::YES)
 450         def = first_clobber_in_group (clobber);
 451       else
 452         {
 453           if (use_info *use = last_nondebug_insn_use_ignoring (def, ignore))
 454             return use;
 455
 456           insn_info *insn = def->insn ();
 457           if (!ignore (insn))
 458             return def;
 459         }
 460       def = def->prev_def ();
 461     }
 462   return nullptr;
 463 }
 464
 465 // Search backwards for an access to DEF->resource (), starting
 466 // immediately before the point at which DEF occurs.  Ignore clobbers
 467 // if IGNORE_CLOBBERS_SETTING is YES, otherwise treat them like any other
 468 // access.  Also ignore any access A for which IGNORE (access_insn (A))
 469 // is true.
 470 //
 471 // Thus if DEF->insn () uses DEF->resource (), that use is the first access
 472 // that the function considers, since an instruction's uses occur strictly
 473 // before its definitions.
 474 //
 475 // Note that this function does not consider separately-recorded call clobbers,
 476 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
 477 template<typename IgnorePredicate>
 478 inline access_info *
 479 prev_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
 480                       IgnorePredicate ignore)
 481 {
 482   return last_access_ignoring (def->prev_def (), ignore_clobbers_setting,
 483                                ignore);
 484 }
 485
 486 // If DEF is null, return null.
 487 //
 488 // Otherwise, search forwards for a definition of DEF->resource (),
 489 // starting at DEF itself.  Ignore clobbers if IGNORE_CLOBBERS_SETTING
 490 // is YES, otherwise treat them like any other access.  Also ignore any
 491 // definition D for which IGNORE (D->insn ()) is true.
 492 //
 493 // Return the definition found, or null if there is no access that meets
 494 // the criteria.
 495 //
 496 // Note that this function does not consider separately-recorded call clobbers,
 497 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
 498 template<typename IgnorePredicate>
 499 def_info *
 500 first_def_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
 501                     IgnorePredicate ignore)
 502 {
 503   while (def)
 504     {
 505       auto *clobber = dyn_cast<clobber_info *> (def);
 506       if (clobber && ignore_clobbers_setting == ignore_clobbers::YES)
 507         def = last_clobber_in_group (clobber);
 508       else if (!ignore (def->insn ()))
 509         return def;
 510
 511       def = def->next_def ();
 512     }
 513   return nullptr;
 514 }
 515
 516 // Search forwards for the next access to DEF->resource (),
 517 // starting immediately after DEF's instruction.  Ignore clobbers if
 518 // IGNORE_CLOBBERS_SETTING is YES, otherwise treat them like any other access.
 519 // Also ignore any access A for which IGNORE (access_insn (A)) is true;
 520 // in this context, ignoring a set includes ignoring all uses of the set.
 521 //
 522 // Thus if DEF is a set with uses by nondebug insns, the first access that the
 523 // function considers is the first such use of the set.
 524 //
 525 // Return the access found, or null if there is no access that meets the
 526 // criteria.
 527 //
 528 // Note that this function does not consider separately-recorded call clobbers,
 529 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
 530 template<typename IgnorePredicate>
 531 access_info *
 532 next_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
 533                       IgnorePredicate ignore)
 534 {
 535   if (use_info *use = first_nondebug_insn_use_ignoring (def, ignore))
 536     return use;
 537
 538   return first_def_ignoring (def->next_def (), ignore_clobbers_setting,
 539                              ignore);
 540 }
 541
 542 // Return true if ACCESS1 should before ACCESS2 in an access_array.
 543 inline bool
 544 compare_access_infos (const access_info *access1, const access_info *access2)
 545 {
 546   gcc_checking_assert (access1 == access2
 547                        || access1->regno () != access2->regno ());
 548   return access1->regno () < access2->regno ();
 549 }
 550
 551 // Sort [BEGIN, END) into ascending regno order.  The sequence must have
 552 // at most one access to a given a regno.
 553 inline void
 554 sort_accesses (access_info **begin, access_info **end)
 555 {
 556   auto count = end - begin;
 557   if (count <= 1)
 558     return;
 559
 560   if (count == 2)
 561     {
 562       gcc_checking_assert (begin[0]->regno () != begin[1]->regno ());
 563       if (begin[0]->regno () > begin[1]->regno ())
 564         std::swap (begin[0], begin[1]);
 565       return;
 566     }
 567
 568   std::sort (begin, end, compare_access_infos);
 569 }
 570
 571 // Sort the accesses in CONTAINER, which contains pointers to access_infos.
 572 template<typename T>
 573 inline void
 574 sort_accesses (T &container)
 575 {
 576   return sort_accesses (container.begin (), container.end ());
 577 }
 578
 579 // The underlying non-template implementation of merge_access_arrays.
 580 access_array merge_access_arrays_base (obstack_watermark &, access_array,
 581                                        access_array);
 582 // Merge access arrays ACCESSES1 and ACCESSES2, including the allocation
 583 // in the area governed by WATERMARK.  Return an invalid access_array if
 584 // ACCESSES1 and ACCESSES2 contain conflicting accesses to the same resource.
 585 //
 586 // T can be an access_array, a def_array or a use_array.
 587 template<typename T>
 588 inline T
 589 merge_access_arrays (obstack_watermark &watermark, T accesses1, T accesses2)
 590 {
 591   return T (merge_access_arrays_base (watermark, accesses1, accesses2));
 592 }
 593
 594 // The underlying non-template implementation of insert_access.
 595 access_array insert_access_base (obstack_watermark &, access_info *,
 596                                  access_array);
 597
 598 // Return a new access_array that contains the result of inserting ACCESS1
 599 // into sorted access array ACCESSES2.  Allocate the returned array in the
 600 // area governed by WATERMARK.  Return an invalid access_array if ACCESSES2
 601 // contains a conflicting access to the same resource as ACCESS1.
 602 //
 603 // T can be an access_array, a def_array or a use_array.
 604 template<typename T>
 605 inline T
 606 insert_access (obstack_watermark &watermark,
 607                typename T::value_type access1, T accesses2)
 608 {
 609   return T (insert_access_base (watermark, access1, accesses2));
 610 }
 611
 612 // Return a copy of USES that drops any use of DEF.
 613 use_array remove_uses_of_def (obstack_watermark &, use_array uses,
 614                               def_info *def);
 615
 616 // The underlying non-template implementation of remove_note_accesses.
 617 access_array remove_note_accesses_base (obstack_watermark &, access_array);
 618
 619 // If ACCESSES contains accesses that only occur in notes, return a new
 620 // array without such accesses, allocating it in the area governed by
 621 // WATERMARK.  Return ACCESSES itself otherwise.
 622 //
 623 // T can be an access_array, a def_array or a use_array.
 624 template<typename T>
 625 inline T
 626 remove_note_accesses (obstack_watermark &watermark, T accesses)
 627 {
 628   return T (remove_note_accesses_base (watermark, accesses));
 629 }
 630
 631 // Return true if ACCESSES1 and ACCESSES2 have at least one resource in common.
 632 bool accesses_reference_same_resource (access_array accesses1,
 633                                        access_array accesses2);
 634
 635 // Return true if INSN clobbers the value of any resources in ACCESSES.
 636 bool insn_clobbers_resources (insn_info *insn, access_array accesses);
 637
 638 }