gcc/rtl-ssa/access-utils.h

   1 // Access-related utilities for RTL SSA                             -*- C++ -*-
   2 // Copyright (C) 2020-2023 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 sorted array ACCESSES includes an access to memory.
  37 inline bool
  38 accesses_include_memory (const access_array &accesses)
  39 {
  40   return accesses.size () && accesses.back ()->is_mem ();
  41 }
  42
  43 // If sorted array ACCESSES includes an access to memory, return the access,
  44 // otherwise return null.
  45 template<typename T>
  46 inline auto
  47 memory_access (T accesses) -> decltype (accesses[0])
  48 {
  49   if (accesses.size () && accesses.back ()->is_mem ())
  50     return accesses.back ();
  51   return nullptr;
  52 }
  53
  54 // If sorted array ACCESSES includes a reference to REGNO, return the
  55 // access, otherwise return null.
  56 template<typename T>
  57 inline auto
  58 find_access (T accesses, unsigned int regno) -> decltype (accesses[0])
  59 {
  60   unsigned int start = 0;
  61   unsigned int end = accesses.size ();
  62   while (start < end)
  63     {
  64       unsigned int mid = (start + end) / 2;
  65       unsigned int found = accesses[mid]->regno ();
  66       if (found == regno)
  67         return accesses[mid];
  68       if (found < regno)
  69         start = mid + 1;
  70       else
  71         end = mid;
  72     }
  73   return nullptr;
  74 }
  75
  76 // If sorted array ACCESSES includes a reference to REGNO, return the
  77 // index of the access, otherwise return -1.
  78 inline int
  79 find_access_index (access_array accesses, unsigned int regno)
  80 {
  81   unsigned int start = 0;
  82   unsigned int end = accesses.size ();
  83   while (start < end)
  84     {
  85       unsigned int mid = (start + end) / 2;
  86       unsigned int found = accesses[mid]->regno ();
  87       if (found == regno)
  88         return mid;
  89       if (found < regno)
  90         start = mid + 1;
  91       else
  92         end = mid;
  93     }
  94   return -1;
  95 }
  96
  97 // If ACCESS is a set whose result is used by at least one instruction,
  98 // return the access as a set_info, otherwise return null.
  99 inline const set_info *
 100 set_with_nondebug_insn_uses (const access_info *access)
 101 {
 102   if (access->is_set_with_nondebug_insn_uses ())
 103     // No need for as_a; this test is just as definitive.
 104     return static_cast<const set_info *> (access);
 105   return nullptr;
 106 }
 107
 108 // A non-const version of the above.
 109 inline set_info *
 110 set_with_nondebug_insn_uses (access_info *access)
 111 {
 112   if (access->is_set_with_nondebug_insn_uses ())
 113     return static_cast<set_info *> (access);
 114   return nullptr;
 115 }
 116
 117 // Return true if SET is the only set of SET->resource () and if it
 118 // dominates all uses (excluding uses of SET->resource () at points
 119 // where SET->resource () is always undefined).
 120 inline bool
 121 is_single_dominating_def (const set_info *set)
 122 {
 123   return set->is_first_def () && set->is_last_def ();
 124 }
 125
 126 // SET is known to be available on entry to BB.  Return true if it is
 127 // also available on exit from BB.  (The value might or might not be live.)
 128 inline bool
 129 remains_available_on_exit (const set_info *set, bb_info *bb)
 130 {
 131   return (set->is_last_def ()
 132           || *set->next_def ()->insn () > *bb->end_insn ());
 133 }
 134
 135 // ACCESS is known to be associated with an instruction rather than
 136 // a phi node.  Return which instruction that is.
 137 inline insn_info *
 138 access_insn (const access_info *access)
 139 {
 140   // In release builds this function reduces to a single pointer reference.
 141   if (auto *def = dyn_cast<const def_info *> (access))
 142     return def->insn ();
 143   return as_a<const use_info *> (access)->insn ();
 144 }
 145
 146 // If ACCESS records a use, return the value that it uses.  If ACCESS records
 147 // a set, return that set.  If ACCESS records a clobber, return null.
 148 inline const set_info *
 149 access_value (const access_info *access)
 150 {
 151   if (!access)
 152     return nullptr;
 153
 154   if (auto *use = dyn_cast<const use_info *> (access))
 155     return use->def ();
 156
 157   return dyn_cast<const set_info *> (access);
 158 }
 159
 160 // A non-const version of the above.
 161 inline set_info *
 162 access_value (access_info *access)
 163 {
 164   auto *const_access = const_cast<const access_info *> (access);
 165   return const_cast<set_info *> (access_value (const_access));
 166 }
 167
 168 // If ACCESS is a degenerate phi, return the set_info that defines its input,
 169 // otherwise return ACCESS itself.
 170 template<typename T>
 171 inline const T *
 172 look_through_degenerate_phi (const T *access)
 173 {
 174   if (auto *phi = dyn_cast<const phi_info *> (access))
 175     if (phi->is_degenerate ())
 176       return phi->input_value (0);
 177   return access;
 178 }
 179
 180 // A non-const version of the above.
 181 template<typename T>
 182 inline T *
 183 look_through_degenerate_phi (T *access)
 184 {
 185   auto *const_access = const_cast<const T *> (access);
 186   return const_cast<T *> (look_through_degenerate_phi (const_access));
 187 }
 188
 189 // If CLOBBER is in a group, return the first clobber in the group,
 190 // otherwise return CLOBBER itself.
 191 inline clobber_info *
 192 first_clobber_in_group (clobber_info *clobber)
 193 {
 194   if (clobber->is_in_group ())
 195     return clobber->group ()->first_clobber ();
 196   return clobber;
 197 }
 198
 199 // If CLOBBER is in a group, return the last clobber in the group,
 200 // otherwise return CLOBBER itself.
 201 inline clobber_info *
 202 last_clobber_in_group (clobber_info *clobber)
 203 {
 204   if (clobber->is_in_group ())
 205     return clobber->group ()->last_clobber ();
 206   return clobber;
 207 }
 208
 209 // If DEF is a clobber in a group, return the containing group,
 210 // otherwise return DEF.
 211 inline def_mux
 212 clobber_group_or_single_def (def_info *def)
 213 {
 214   if (auto *clobber = dyn_cast<clobber_info *> (def))
 215     if (clobber->is_in_group ())
 216       return clobber->group ();
 217   return def;
 218 }
 219
 220 // Return the first definition associated with NODE.  If NODE holds
 221 // a single set, the result is that set.  If NODE holds a clobber_group,
 222 // the result is the first clobber in the group.
 223 inline def_info *
 224 first_def (def_node *node)
 225 {
 226   return node->first_def ();
 227 }
 228
 229 // Likewise for something that is either a node or a single definition.
 230 inline def_info *
 231 first_def (def_mux mux)
 232 {
 233   return mux.first_def ();
 234 }
 235
 236 // Return the last definition associated with NODE.  If NODE holds
 237 // a single set, the result is that set.  If NODE holds a clobber_group,
 238 // the result is the last clobber in the group.
 239 inline def_info *
 240 last_def (def_node *node)
 241 {
 242   if (auto *group = dyn_cast<clobber_group *> (node))
 243     return group->last_clobber ();
 244   return node->first_def ();
 245 }
 246
 247 // Likewise for something that is either a node or a single definition.
 248 inline def_info *
 249 last_def (def_mux mux)
 250 {
 251   return mux.last_def ();
 252 }
 253
 254 int lookup_use (splay_tree<use_info *> &, insn_info *);
 255 int lookup_def (def_splay_tree &, insn_info *);
 256 int lookup_clobber (clobber_tree &, insn_info *);
 257 int lookup_call_clobbers (insn_call_clobbers_tree &, insn_info *);
 258
 259 // Search backwards from immediately before INSN for the first instruction
 260 // recorded in TREE, ignoring any instruction I for which IGNORE (I) is true.
 261 // Return null if no such instruction exists.
 262 template<typename IgnorePredicate>
 263 insn_info *
 264 prev_call_clobbers_ignoring (insn_call_clobbers_tree &tree, insn_info *insn,
 265                              IgnorePredicate ignore)
 266 {
 267   if (!tree)
 268     return nullptr;
 269
 270   int comparison = lookup_call_clobbers (tree, insn);
 271   while (comparison <= 0 || ignore (tree->insn ()))
 272     {
 273       if (!tree.splay_prev_node ())
 274         return nullptr;
 275
 276       comparison = 1;
 277     }
 278   return tree->insn ();
 279 }
 280
 281 // Search forwards from immediately after INSN for the first instruction
 282 // recorded in TREE, ignoring any instruction I for which IGNORE (I) is true.
 283 // Return null if no such instruction exists.
 284 template<typename IgnorePredicate>
 285 insn_info *
 286 next_call_clobbers_ignoring (insn_call_clobbers_tree &tree, insn_info *insn,
 287                              IgnorePredicate ignore)
 288 {
 289   if (!tree)
 290     return nullptr;
 291
 292   int comparison = lookup_call_clobbers (tree, insn);
 293   while (comparison >= 0 || ignore (tree->insn ()))
 294     {
 295       if (!tree.splay_next_node ())
 296         return nullptr;
 297
 298       comparison = -1;
 299     }
 300   return tree->insn ();
 301 }
 302
 303 // If ACCESS is a set, return the first use of ACCESS by a nondebug insn I
 304 // for which IGNORE (I) is false.  Return null if ACCESS is not a set or if
 305 // no such use exists.
 306 template<typename IgnorePredicate>
 307 inline use_info *
 308 first_nondebug_insn_use_ignoring (const access_info *access,
 309                                   IgnorePredicate ignore)
 310 {
 311   if (const set_info *set = set_with_nondebug_insn_uses (access))
 312     {
 313       // Written this way to emphasize to the compiler that first_use
 314       // must be nonnull in this situation.
 315       use_info *use = set->first_use ();
 316       do
 317         {
 318           if (!ignore (use->insn ()))
 319             return use;
 320           use = use->next_nondebug_insn_use ();
 321         }
 322       while (use);
 323     }
 324   return nullptr;
 325 }
 326
 327 // If ACCESS is a set, return the last use of ACCESS by a nondebug insn I for
 328 // which IGNORE (I) is false.  Return null if ACCESS is not a set or if no
 329 // such use exists.
 330 template<typename IgnorePredicate>
 331 inline use_info *
 332 last_nondebug_insn_use_ignoring (const access_info *access,
 333                                  IgnorePredicate ignore)
 334 {
 335   if (const set_info *set = set_with_nondebug_insn_uses (access))
 336     {
 337       // Written this way to emphasize to the compiler that
 338       // last_nondebug_insn_use must be nonnull in this situation.
 339       use_info *use = set->last_nondebug_insn_use ();
 340       do
 341         {
 342           if (!ignore (use->insn ()))
 343             return use;
 344           use = use->prev_use ();
 345         }
 346       while (use);
 347     }
 348   return nullptr;
 349 }
 350
 351 // If DEF is null, return null.
 352 //
 353 // Otherwise, search backwards for an access to DEF->resource (), starting at
 354 // the end of DEF's live range.  Ignore clobbers if IGNORE_CLOBBERS_SETTING
 355 // is YES, otherwise treat them like any other access.  Also ignore any
 356 // access A for which IGNORE (access_insn (A)) is true.
 357 //
 358 // Thus if DEF is a set that is used by nondebug insns, the first access
 359 // that the function considers is the last such use of the set.  Otherwise,
 360 // the first access that the function considers is DEF itself.
 361 //
 362 // Return the access found, or null if there is no access that meets
 363 // the criteria.
 364 //
 365 // Note that this function does not consider separately-recorded call clobbers,
 366 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
 367 template<typename IgnorePredicate>
 368 access_info *
 369 last_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
 370                       IgnorePredicate ignore)
 371 {
 372   while (def)
 373     {
 374       auto *clobber = dyn_cast<clobber_info *> (def);
 375       if (clobber && ignore_clobbers_setting == ignore_clobbers::YES)
 376         def = first_clobber_in_group (clobber);
 377       else
 378         {
 379           if (use_info *use = last_nondebug_insn_use_ignoring (def, ignore))
 380             return use;
 381
 382           insn_info *insn = def->insn ();
 383           if (!ignore (insn))
 384             return def;
 385         }
 386       def = def->prev_def ();
 387     }
 388   return nullptr;
 389 }
 390
 391 // Search backwards for an access to DEF->resource (), starting
 392 // immediately before the point at which DEF occurs.  Ignore clobbers
 393 // if IGNORE_CLOBBERS_SETTING is YES, otherwise treat them like any other
 394 // access.  Also ignore any access A for which IGNORE (access_insn (A))
 395 // is true.
 396 //
 397 // Thus if DEF->insn () uses DEF->resource (), that use is the first access
 398 // that the function considers, since an instruction's uses occur strictly
 399 // before its definitions.
 400 //
 401 // Note that this function does not consider separately-recorded call clobbers,
 402 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
 403 template<typename IgnorePredicate>
 404 inline access_info *
 405 prev_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
 406                       IgnorePredicate ignore)
 407 {
 408   return last_access_ignoring (def->prev_def (), ignore_clobbers_setting,
 409                                ignore);
 410 }
 411
 412 // If DEF is null, return null.
 413 //
 414 // Otherwise, search forwards for a definition of DEF->resource (),
 415 // starting at DEF itself.  Ignore clobbers if IGNORE_CLOBBERS_SETTING
 416 // is YES, otherwise treat them like any other access.  Also ignore any
 417 // definition D for which IGNORE (D->insn ()) is true.
 418 //
 419 // Return the definition found, or null if there is no access that meets
 420 // the criteria.
 421 //
 422 // Note that this function does not consider separately-recorded call clobbers,
 423 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
 424 template<typename IgnorePredicate>
 425 def_info *
 426 first_def_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
 427                     IgnorePredicate ignore)
 428 {
 429   while (def)
 430     {
 431       auto *clobber = dyn_cast<clobber_info *> (def);
 432       if (clobber && ignore_clobbers_setting == ignore_clobbers::YES)
 433         def = last_clobber_in_group (clobber);
 434       else if (!ignore (def->insn ()))
 435         return def;
 436
 437       def = def->next_def ();
 438     }
 439   return nullptr;
 440 }
 441
 442 // Search forwards for the next access to DEF->resource (),
 443 // starting immediately after DEF's instruction.  Ignore clobbers if
 444 // IGNORE_CLOBBERS_SETTING is YES, otherwise treat them like any other access.
 445 // Also ignore any access A for which IGNORE (access_insn (A)) is true;
 446 // in this context, ignoring a set includes ignoring all uses of the set.
 447 //
 448 // Thus if DEF is a set with uses by nondebug insns, the first access that the
 449 // function considers is the first such use of the set.
 450 //
 451 // Return the access found, or null if there is no access that meets the
 452 // criteria.
 453 //
 454 // Note that this function does not consider separately-recorded call clobbers,
 455 // although such clobbers are only relevant if IGNORE_CLOBBERS_SETTING is NO.
 456 template<typename IgnorePredicate>
 457 access_info *
 458 next_access_ignoring (def_info *def, ignore_clobbers ignore_clobbers_setting,
 459                       IgnorePredicate ignore)
 460 {
 461   if (use_info *use = first_nondebug_insn_use_ignoring (def, ignore))
 462     return use;
 463
 464   return first_def_ignoring (def->next_def (), ignore_clobbers_setting,
 465                              ignore);
 466 }
 467
 468 // Return true if ACCESS1 should before ACCESS2 in an access_array.
 469 inline bool
 470 compare_access_infos (const access_info *access1, const access_info *access2)
 471 {
 472   gcc_checking_assert (access1 == access2
 473                        || access1->regno () != access2->regno ());
 474   return access1->regno () < access2->regno ();
 475 }
 476
 477 // Sort [BEGIN, END) into ascending regno order.  The sequence must have
 478 // at most one access to a given a regno.
 479 inline void
 480 sort_accesses (access_info **begin, access_info **end)
 481 {
 482   auto count = end - begin;
 483   if (count <= 1)
 484     return;
 485
 486   if (count == 2)
 487     {
 488       gcc_checking_assert (begin[0]->regno () != begin[1]->regno ());
 489       if (begin[0]->regno () > begin[1]->regno ())
 490         std::swap (begin[0], begin[1]);
 491       return;
 492     }
 493
 494   std::sort (begin, end, compare_access_infos);
 495 }
 496
 497 // Sort the accesses in CONTAINER, which contains pointers to access_infos.
 498 template<typename T>
 499 inline void
 500 sort_accesses (T &container)
 501 {
 502   return sort_accesses (container.begin (), container.end ());
 503 }
 504
 505 // The underlying non-template implementation of merge_access_arrays.
 506 access_array merge_access_arrays_base (obstack_watermark &, access_array,
 507                                        access_array);
 508 // Merge access arrays ACCESSES1 and ACCESSES2, including the allocation
 509 // in the area governed by WATERMARK.  Return an invalid access_array if
 510 // ACCESSES1 and ACCESSES2 contain conflicting accesses to the same resource.
 511 //
 512 // T can be an access_array, a def_array or a use_array.
 513 template<typename T>
 514 inline T
 515 merge_access_arrays (obstack_watermark &watermark, T accesses1, T accesses2)
 516 {
 517   return T (merge_access_arrays_base (watermark, accesses1, accesses2));
 518 }
 519
 520 // The underlying non-template implementation of insert_access.
 521 access_array insert_access_base (obstack_watermark &, access_info *,
 522                                  access_array);
 523
 524 // Return a new access_array that contains the result of inserting ACCESS1
 525 // into sorted access array ACCESSES2.  Allocate the returned array in the
 526 // area governed by WATERMARK.  Return an invalid access_array if ACCESSES2
 527 // contains a conflicting access to the same resource as ACCESS1.
 528 //
 529 // T can be an access_array, a def_array or a use_array.
 530 template<typename T>
 531 inline T
 532 insert_access (obstack_watermark &watermark,
 533                typename T::value_type access1, T accesses2)
 534 {
 535   return T (insert_access_base (watermark, access1, accesses2));
 536 }
 537
 538 // The underlying non-template implementation of remove_note_accesses.
 539 access_array remove_note_accesses_base (obstack_watermark &, access_array);
 540
 541 // If ACCESSES contains accesses that only occur in notes, return a new
 542 // array without such accesses, allocating it in the area governed by
 543 // WATERMARK.  Return ACCESSES itself otherwise.
 544 //
 545 // T can be an access_array, a def_array or a use_array.
 546 template<typename T>
 547 inline T
 548 remove_note_accesses (obstack_watermark &watermark, T accesses)
 549 {
 550   return T (remove_note_accesses_base (watermark, accesses));
 551 }
 552
 553 }