Home | History | Annotate | Line # | Download | only in rtl-ssa
      1  1.1  mrg // Implementation of instruction-related RTL SSA functions          -*- C++ -*-
      2  1.1  mrg // Copyright (C) 2020-2022 Free Software Foundation, Inc.
      3  1.1  mrg //
      4  1.1  mrg // This file is part of GCC.
      5  1.1  mrg //
      6  1.1  mrg // GCC is free software; you can redistribute it and/or modify it under
      7  1.1  mrg // the terms of the GNU General Public License as published by the Free
      8  1.1  mrg // Software Foundation; either version 3, or (at your option) any later
      9  1.1  mrg // version.
     10  1.1  mrg //
     11  1.1  mrg // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
     12  1.1  mrg // WARRANTY; without even the implied warranty of MERCHANTABILITY or
     13  1.1  mrg // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
     14  1.1  mrg // for more details.
     15  1.1  mrg //
     16  1.1  mrg // You should have received a copy of the GNU General Public License
     17  1.1  mrg // along with GCC; see the file COPYING3.  If not see
     18  1.1  mrg // <http://www.gnu.org/licenses/>.
     19  1.1  mrg 
     20  1.1  mrg #define INCLUDE_ALGORITHM
     21  1.1  mrg #define INCLUDE_FUNCTIONAL
     22  1.1  mrg #include "config.h"
     23  1.1  mrg #include "system.h"
     24  1.1  mrg #include "coretypes.h"
     25  1.1  mrg #include "backend.h"
     26  1.1  mrg #include "rtl.h"
     27  1.1  mrg #include "df.h"
     28  1.1  mrg #include "rtl-ssa.h"
     29  1.1  mrg #include "rtl-ssa/internals.h"
     30  1.1  mrg #include "rtl-ssa/internals.inl"
     31  1.1  mrg #include "predict.h"
     32  1.1  mrg #include "print-rtl.h"
     33  1.1  mrg #include "rtl-iter.h"
     34  1.1  mrg 
     35  1.1  mrg using namespace rtl_ssa;
     36  1.1  mrg 
     37  1.1  mrg // The gap to leave between program points when building up the list
     38  1.1  mrg // of instructions for the first time.  Using 2 allows an instruction
     39  1.1  mrg // to be inserted between two others without resorting to splay tree
     40  1.1  mrg // ordering.  Using 0 is useful as a debugging aid to stress the
     41  1.1  mrg // splay tree code.
     42  1.1  mrg static const unsigned int POINT_INCREASE = 2;
     43  1.1  mrg 
     44  1.1  mrg // Calculate and record the cost of the instruction, based on the
     45  1.1  mrg // form it had before any in-progress changes were made.
     46  1.1  mrg void
     47  1.1  mrg insn_info::calculate_cost () const
     48  1.1  mrg {
     49  1.1  mrg   basic_block cfg_bb = BLOCK_FOR_INSN (m_rtl);
     50  1.1  mrg   temporarily_undo_changes (0);
     51  1.1  mrg   m_cost_or_uid = insn_cost (m_rtl, optimize_bb_for_speed_p (cfg_bb));
     52  1.1  mrg   redo_changes (0);
     53  1.1  mrg }
     54  1.1  mrg 
     55  1.1  mrg // Add NOTE to the instruction's notes.
     56  1.1  mrg void
     57  1.1  mrg insn_info::add_note (insn_note *note)
     58  1.1  mrg {
     59  1.1  mrg   insn_note **ptr = &m_first_note;
     60  1.1  mrg   // Always put the order node first, since it's the one that's likely
     61  1.1  mrg   // to be used most often.
     62  1.1  mrg   if (*ptr && (*ptr)->kind () == insn_note_kind::ORDER_NODE)
     63  1.1  mrg     ptr = &(*ptr)->m_next_note;
     64  1.1  mrg   note->m_next_note = *ptr;
     65  1.1  mrg   *ptr = note;
     66  1.1  mrg }
     67  1.1  mrg 
     68  1.1  mrg // Implement compare_with for the case in which this insn and OTHER
     69  1.1  mrg // have the same program point.
     70  1.1  mrg int
     71  1.1  mrg insn_info::slow_compare_with (const insn_info &other) const
     72  1.1  mrg {
     73  1.1  mrg   return order_splay_tree::compare_nodes (get_known_order_node (),
     74  1.1  mrg 					  other.get_known_order_node ());
     75  1.1  mrg }
     76  1.1  mrg 
     77  1.1  mrg // Print insn uid UID to PP, where UID has the same form as insn_info::uid.
     78  1.1  mrg void
     79  1.1  mrg insn_info::print_uid (pretty_printer *pp, int uid)
     80  1.1  mrg {
     81  1.1  mrg   char tmp[3 * sizeof (uid) + 2];
     82  1.1  mrg   if (uid < 0)
     83  1.1  mrg     // An artificial instruction.
     84  1.1  mrg     snprintf (tmp, sizeof (tmp), "a%d", -uid);
     85  1.1  mrg   else
     86  1.1  mrg     // A real RTL instruction.
     87  1.1  mrg     snprintf (tmp, sizeof (tmp), "i%d", uid);
     88  1.1  mrg   pp_string (pp, tmp);
     89  1.1  mrg }
     90  1.1  mrg 
     91  1.1  mrg // See comment above declaration.
     92  1.1  mrg void
     93  1.1  mrg insn_info::print_identifier (pretty_printer *pp) const
     94  1.1  mrg {
     95  1.1  mrg   print_uid (pp, uid ());
     96  1.1  mrg }
     97  1.1  mrg 
     98  1.1  mrg // See comment above declaration.
     99  1.1  mrg void
    100  1.1  mrg insn_info::print_location (pretty_printer *pp) const
    101  1.1  mrg {
    102  1.1  mrg   if (bb_info *bb = this->bb ())
    103  1.1  mrg     {
    104  1.1  mrg       ebb_info *ebb = bb->ebb ();
    105  1.1  mrg       if (ebb && is_phi ())
    106  1.1  mrg 	ebb->print_identifier (pp);
    107  1.1  mrg       else
    108  1.1  mrg 	bb->print_identifier (pp);
    109  1.1  mrg       pp_string (pp, " at point ");
    110  1.1  mrg       pp_decimal_int (pp, m_point);
    111  1.1  mrg     }
    112  1.1  mrg   else
    113  1.1  mrg     pp_string (pp, "<unknown location>");
    114  1.1  mrg }
    115  1.1  mrg 
    116  1.1  mrg // See comment above declaration.
    117  1.1  mrg void
    118  1.1  mrg insn_info::print_identifier_and_location (pretty_printer *pp) const
    119  1.1  mrg {
    120  1.1  mrg   if (m_is_asm)
    121  1.1  mrg     pp_string (pp, "asm ");
    122  1.1  mrg   if (m_is_debug_insn)
    123  1.1  mrg     pp_string (pp, "debug ");
    124  1.1  mrg   pp_string (pp, "insn ");
    125  1.1  mrg   print_identifier (pp);
    126  1.1  mrg   pp_string (pp, " in ");
    127  1.1  mrg   print_location (pp);
    128  1.1  mrg }
    129  1.1  mrg 
    130  1.1  mrg // See comment above declaration.
    131  1.1  mrg void
    132  1.1  mrg insn_info::print_full (pretty_printer *pp) const
    133  1.1  mrg {
    134  1.1  mrg   print_identifier_and_location (pp);
    135  1.1  mrg   pp_colon (pp);
    136  1.1  mrg   if (is_real ())
    137  1.1  mrg     {
    138  1.1  mrg       pp_newline_and_indent (pp, 2);
    139  1.1  mrg       if (has_been_deleted ())
    140  1.1  mrg 	pp_string (pp, "deleted");
    141  1.1  mrg       else
    142  1.1  mrg 	{
    143  1.1  mrg 	  // Print the insn pattern to a temporary printer.
    144  1.1  mrg 	  pretty_printer sub_pp;
    145  1.1  mrg 	  print_insn_with_notes (&sub_pp, rtl ());
    146  1.1  mrg 	  const char *text = pp_formatted_text (&sub_pp);
    147  1.1  mrg 
    148  1.1  mrg 	  // Calculate the length of the maximum line in the pattern.
    149  1.1  mrg 	  unsigned int max_len = 0;
    150  1.1  mrg 	  const char *start = text;
    151  1.1  mrg 	  while (const char *end = strchr (start, '\n'))
    152  1.1  mrg 	    {
    153  1.1  mrg 	      max_len = MAX (max_len, (unsigned int) (end - start));
    154  1.1  mrg 	      start = end + 1;
    155  1.1  mrg 	    }
    156  1.1  mrg 
    157  1.1  mrg 	  // Print a separator before or after the pattern.
    158  1.1  mrg 	  auto print_top_bottom = [&]()
    159  1.1  mrg 	    {
    160  1.1  mrg 	      pp_character (pp, '+');
    161  1.1  mrg 	      for (unsigned int i = 0; i < max_len + 2; ++i)
    162  1.1  mrg 		pp_character (pp, '-');
    163  1.1  mrg 	    };
    164  1.1  mrg 
    165  1.1  mrg 	  print_top_bottom ();
    166  1.1  mrg 	  start = text;
    167  1.1  mrg 	  while (const char *end = strchr (start, '\n'))
    168  1.1  mrg 	    {
    169  1.1  mrg 	      pp_newline_and_indent (pp, 0);
    170  1.1  mrg 	      pp_character (pp, '|');
    171  1.1  mrg 	      // Each line of the pattern already starts with a space.
    172  1.1  mrg 	      // so we don't need to add another one here.
    173  1.1  mrg 	      pp_append_text (pp, start, end);
    174  1.1  mrg 	      start = end + 1;
    175  1.1  mrg 	    }
    176  1.1  mrg 	  pp_newline_and_indent (pp, 0);
    177  1.1  mrg 	  print_top_bottom ();
    178  1.1  mrg 
    179  1.1  mrg 	  if (m_cost_or_uid != UNKNOWN_COST)
    180  1.1  mrg 	    {
    181  1.1  mrg 	      pp_newline_and_indent (pp, 0);
    182  1.1  mrg 	      pp_string (pp, "cost: ");
    183  1.1  mrg 	      pp_decimal_int (pp, m_cost_or_uid);
    184  1.1  mrg 	    }
    185  1.1  mrg 	  if (m_has_pre_post_modify)
    186  1.1  mrg 	    {
    187  1.1  mrg 	      pp_newline_and_indent (pp, 0);
    188  1.1  mrg 	      pp_string (pp, "has pre/post-modify operations");
    189  1.1  mrg 	    }
    190  1.1  mrg 	  if (m_has_volatile_refs)
    191  1.1  mrg 	    {
    192  1.1  mrg 	      pp_newline_and_indent (pp, 0);
    193  1.1  mrg 	      pp_string (pp, "has volatile refs");
    194  1.1  mrg 	    }
    195  1.1  mrg 	}
    196  1.1  mrg       pp_indentation (pp) -= 2;
    197  1.1  mrg     }
    198  1.1  mrg 
    199  1.1  mrg   auto print_accesses = [&](const char *heading, access_array accesses,
    200  1.1  mrg 			    unsigned int flags)
    201  1.1  mrg     {
    202  1.1  mrg       if (!accesses.empty ())
    203  1.1  mrg 	{
    204  1.1  mrg 	  pp_newline_and_indent (pp, 2);
    205  1.1  mrg 	  pp_string (pp, heading);
    206  1.1  mrg 	  pp_newline_and_indent (pp, 2);
    207  1.1  mrg 	  pp_accesses (pp, accesses, flags);
    208  1.1  mrg 	  pp_indentation (pp) -= 4;
    209  1.1  mrg 	}
    210  1.1  mrg     };
    211  1.1  mrg 
    212  1.1  mrg   print_accesses ("uses:", uses (), PP_ACCESS_USER);
    213  1.1  mrg   auto *call_clobbers_note = find_note<insn_call_clobbers_note> ();
    214  1.1  mrg   if (call_clobbers_note)
    215  1.1  mrg     {
    216  1.1  mrg       pp_newline_and_indent (pp, 2);
    217  1.1  mrg       pp_string (pp, "has call clobbers for ABI ");
    218  1.1  mrg       pp_decimal_int (pp, call_clobbers_note->abi_id ());
    219  1.1  mrg       pp_indentation (pp) -= 2;
    220  1.1  mrg     }
    221  1.1  mrg   print_accesses ("defines:", defs (), PP_ACCESS_SETTER);
    222  1.1  mrg   if (num_uses () == 0 && !call_clobbers_note && num_defs () == 0)
    223  1.1  mrg     {
    224  1.1  mrg       pp_newline_and_indent (pp, 2);
    225  1.1  mrg       pp_string (pp, "has no uses or defs");
    226  1.1  mrg       pp_indentation (pp) -= 2;
    227  1.1  mrg     }
    228  1.1  mrg 
    229  1.1  mrg   if (order_node *node = get_order_node ())
    230  1.1  mrg     {
    231  1.1  mrg       while (node->m_parent)
    232  1.1  mrg 	node = node->m_parent;
    233  1.1  mrg 
    234  1.1  mrg       pp_newline_and_indent (pp, 2);
    235  1.1  mrg       pp_string (pp, "insn order: ");
    236  1.1  mrg       pp_newline_and_indent (pp, 2);
    237  1.1  mrg       auto print_order = [](pretty_printer *pp, order_node *node)
    238  1.1  mrg 	{
    239  1.1  mrg 	  print_uid (pp, node->uid ());
    240  1.1  mrg 	};
    241  1.1  mrg       order_splay_tree::print (pp, node, print_order);
    242  1.1  mrg       pp_indentation (pp) -= 4;
    243  1.1  mrg     }
    244  1.1  mrg }
    245  1.1  mrg 
    246  1.1  mrg // Return an insn_info::order_node for INSN, creating one if necessary.
    247  1.1  mrg insn_info::order_node *
    248  1.1  mrg function_info::need_order_node (insn_info *insn)
    249  1.1  mrg {
    250  1.1  mrg   insn_info::order_node *order = insn->get_order_node ();
    251  1.1  mrg   if (!order)
    252  1.1  mrg     {
    253  1.1  mrg       order = allocate<insn_info::order_node> (insn->uid ());
    254  1.1  mrg       insn->add_note (order);
    255  1.1  mrg     }
    256  1.1  mrg   return order;
    257  1.1  mrg }
    258  1.1  mrg 
    259  1.1  mrg // Add instruction INSN immediately after AFTER in the reverse postorder list.
    260  1.1  mrg // INSN is not currently in the list.
    261  1.1  mrg void
    262  1.1  mrg function_info::add_insn_after (insn_info *insn, insn_info *after)
    263  1.1  mrg {
    264  1.1  mrg   gcc_checking_assert (!insn->has_insn_links ());
    265  1.1  mrg 
    266  1.1  mrg   insn->copy_next_from (after);
    267  1.1  mrg   after->set_next_any_insn (insn);
    268  1.1  mrg 
    269  1.1  mrg   // The prev link is easy if AFTER and INSN are the same type.
    270  1.1  mrg   // Handle the other cases below.
    271  1.1  mrg   if (after->is_debug_insn () == insn->is_debug_insn ())
    272  1.1  mrg     insn->set_prev_sametype_insn (after);
    273  1.1  mrg 
    274  1.1  mrg   if (insn_info *next = insn->next_any_insn ())
    275  1.1  mrg     {
    276  1.1  mrg       if (insn->is_debug_insn () == next->is_debug_insn ())
    277  1.1  mrg 	{
    278  1.1  mrg 	  // INSN might now be the start of the subsequence of debug insns,
    279  1.1  mrg 	  // and so its prev pointer might point to the end of the subsequence
    280  1.1  mrg 	  // instead of AFTER.
    281  1.1  mrg 	  insn->copy_prev_from (next);
    282  1.1  mrg 	  next->set_prev_sametype_insn (insn);
    283  1.1  mrg 	}
    284  1.1  mrg       else if (insn->is_debug_insn ()) // && !next->is_debug_insn ()
    285  1.1  mrg 	{
    286  1.1  mrg 	  // INSN ends a subsequence of debug instructions.  Find the
    287  1.1  mrg 	  // first debug instruction in the subsequence, which might
    288  1.1  mrg 	  // be INSN itself.  (If it isn't, then AFTER is also a debug
    289  1.1  mrg 	  // instruction and we updated INSN's prev link above.)
    290  1.1  mrg 	  insn_info *first = next->prev_nondebug_insn ()->next_any_insn ();
    291  1.1  mrg 	  first->set_last_debug_insn (insn);
    292  1.1  mrg 	}
    293  1.1  mrg       else // !insn->is_debug_insn () && next->is_debug_insn ()
    294  1.1  mrg 	// At present we don't (need to) support inserting a nondebug
    295  1.1  mrg 	// instruction between two existing debug instructions.
    296  1.1  mrg 	gcc_assert (!after->is_debug_insn ());
    297  1.1  mrg 
    298  1.1  mrg       // If AFTER and NEXT are separated by at least two points, we can
    299  1.1  mrg       // use a unique point number for INSN.  Otherwise INSN will have
    300  1.1  mrg       // the same point number as AFTER.
    301  1.1  mrg       insn->set_point ((next->point () + after->point ()) / 2);
    302  1.1  mrg     }
    303  1.1  mrg   else
    304  1.1  mrg     {
    305  1.1  mrg       if (!insn->is_debug_insn ())
    306  1.1  mrg 	{
    307  1.1  mrg 	  insn->set_prev_sametype_insn (m_last_nondebug_insn);
    308  1.1  mrg 	  m_last_nondebug_insn = insn;
    309  1.1  mrg 	}
    310  1.1  mrg       else
    311  1.1  mrg 	// There is now at least one debug instruction after
    312  1.1  mrg 	// m_last_nondebug_insn: either INSN itself, or the start of
    313  1.1  mrg 	// a longer subsequence of debug insns that now ends with AFTER
    314  1.1  mrg 	// followed by INSN.
    315  1.1  mrg 	m_last_nondebug_insn->next_any_insn ()->set_last_debug_insn (insn);
    316  1.1  mrg       m_last_insn = insn;
    317  1.1  mrg 
    318  1.1  mrg       insn->set_point (after->point () + POINT_INCREASE);
    319  1.1  mrg     }
    320  1.1  mrg 
    321  1.1  mrg   // If INSN's program point is the same as AFTER's, we need to use the
    322  1.1  mrg   // splay tree to record their relative order.
    323  1.1  mrg   if (insn->point () == after->point ())
    324  1.1  mrg     {
    325  1.1  mrg       insn_info::order_node *after_node = need_order_node (after);
    326  1.1  mrg       insn_info::order_node *insn_node = need_order_node (insn);
    327  1.1  mrg       insn_info::order_splay_tree::insert_child (after_node, 1, insn_node);
    328  1.1  mrg     }
    329  1.1  mrg }
    330  1.1  mrg 
    331  1.1  mrg // Remove INSN from the function's list of instructions.
    332  1.1  mrg void
    333  1.1  mrg function_info::remove_insn (insn_info *insn)
    334  1.1  mrg {
    335  1.1  mrg   if (insn_info::order_node *order = insn->get_order_node ())
    336  1.1  mrg     insn_info::order_splay_tree::remove_node (order);
    337  1.1  mrg 
    338  1.1  mrg   if (auto *note = insn->find_note<insn_call_clobbers_note> ())
    339  1.1  mrg     {
    340  1.1  mrg       ebb_call_clobbers_info *ecc = insn->ebb ()->first_call_clobbers ();
    341  1.1  mrg       while (ecc->abi ()->id () != note->abi_id ())
    342  1.1  mrg 	ecc = ecc->next ();
    343  1.1  mrg       int comparison = lookup_call_clobbers (*ecc, insn);
    344  1.1  mrg       gcc_assert (comparison == 0);
    345  1.1  mrg       ecc->remove_root ();
    346  1.1  mrg     }
    347  1.1  mrg 
    348  1.1  mrg   insn_info *prev = insn->prev_any_insn ();
    349  1.1  mrg   insn_info *next = insn->next_any_insn ();
    350  1.1  mrg   insn_info *prev_nondebug = insn->prev_nondebug_insn ();
    351  1.1  mrg   insn_info *next_nondebug = insn->next_nondebug_insn ();
    352  1.1  mrg 
    353  1.1  mrg   // We should never remove the entry or exit block's instructions.
    354  1.1  mrg   // At present we also don't remove entire blocks, so should never
    355  1.1  mrg   // remove debug instructions.
    356  1.1  mrg   gcc_checking_assert (prev_nondebug
    357  1.1  mrg 		       && next_nondebug
    358  1.1  mrg 		       && !insn->is_debug_insn ());
    359  1.1  mrg 
    360  1.1  mrg   if (prev->is_debug_insn () && next->is_debug_insn ())
    361  1.1  mrg     {
    362  1.1  mrg       // We need to stitch together two subsequences of debug insns.
    363  1.1  mrg       insn_info *last = next->last_debug_insn ();
    364  1.1  mrg       next->set_prev_sametype_insn (prev);
    365  1.1  mrg       prev_nondebug->next_any_insn ()->set_last_debug_insn (last);
    366  1.1  mrg     }
    367  1.1  mrg   prev->set_next_any_insn (next);
    368  1.1  mrg   next_nondebug->set_prev_sametype_insn (prev_nondebug);
    369  1.1  mrg 
    370  1.1  mrg   insn->clear_insn_links ();
    371  1.1  mrg }
    372  1.1  mrg 
    373  1.1  mrg // Create an artificial instruction for BB, associating it with RTL (which can
    374  1.1  mrg // be null).  Add the new instruction to the end of the function's list and
    375  1.1  mrg // return the new instruction.
    376  1.1  mrg insn_info *
    377  1.1  mrg function_info::append_artificial_insn (bb_info *bb, rtx_insn *rtl)
    378  1.1  mrg {
    379  1.1  mrg   insn_info *insn = allocate<insn_info> (bb, rtl, m_next_artificial_uid);
    380  1.1  mrg   m_next_artificial_uid -= 1;
    381  1.1  mrg   append_insn (insn);
    382  1.1  mrg   return insn;
    383  1.1  mrg }
    384  1.1  mrg 
    385  1.1  mrg // Finish building a new list of uses and definitions for instruction INSN.
    386  1.1  mrg void
    387  1.1  mrg function_info::finish_insn_accesses (insn_info *insn)
    388  1.1  mrg {
    389  1.1  mrg   unsigned int num_defs = m_temp_defs.length ();
    390  1.1  mrg   unsigned int num_uses = m_temp_uses.length ();
    391  1.1  mrg   obstack_make_room (&m_obstack, num_defs + num_uses);
    392  1.1  mrg   if (num_defs)
    393  1.1  mrg     {
    394  1.1  mrg       sort_accesses (m_temp_defs);
    395  1.1  mrg       obstack_grow (&m_obstack, m_temp_defs.address (),
    396  1.1  mrg 		    num_defs * sizeof (access_info *));
    397  1.1  mrg       m_temp_defs.truncate (0);
    398  1.1  mrg     }
    399  1.1  mrg   if (num_uses)
    400  1.1  mrg     {
    401  1.1  mrg       sort_accesses (m_temp_uses);
    402  1.1  mrg       obstack_grow (&m_obstack, m_temp_uses.address (),
    403  1.1  mrg 		    num_uses * sizeof (access_info *));
    404  1.1  mrg       m_temp_uses.truncate (0);
    405  1.1  mrg     }
    406  1.1  mrg   void *addr = obstack_finish (&m_obstack);
    407  1.1  mrg   insn->set_accesses (static_cast<access_info **> (addr), num_defs, num_uses);
    408  1.1  mrg }
    409  1.1  mrg 
    410  1.1  mrg // Called while building SSA form using BI.  Create and return a use of
    411  1.1  mrg // register RESOURCE in INSN.  Create a degenerate phi where necessary.
    412  1.1  mrg use_info *
    413  1.1  mrg function_info::create_reg_use (build_info &bi, insn_info *insn,
    414  1.1  mrg 			       resource_info resource)
    415  1.1  mrg {
    416  1.1  mrg   set_info *value = bi.current_reg_value (resource.regno);
    417  1.1  mrg   if (value && value->ebb () != bi.current_ebb)
    418  1.1  mrg     {
    419  1.1  mrg       if (insn->is_debug_insn ())
    420  1.1  mrg 	value = look_through_degenerate_phi (value);
    421  1.1  mrg       else if (bitmap_bit_p (bi.potential_phi_regs, resource.regno))
    422  1.1  mrg 	{
    423  1.1  mrg 	  // VALUE is defined by a previous EBB and RESOURCE has multiple
    424  1.1  mrg 	  // definitions.  Create a degenerate phi in the current EBB
    425  1.1  mrg 	  // so that all definitions and uses follow a linear RPO view;
    426  1.1  mrg 	  // see rtl.texi for details.
    427  1.1  mrg 	  access_info *inputs[] = { look_through_degenerate_phi (value) };
    428  1.1  mrg 	  value = create_phi (bi.current_ebb, value->resource (), inputs, 1);
    429  1.1  mrg 	  bi.record_reg_def (value);
    430  1.1  mrg 	}
    431  1.1  mrg     }
    432  1.1  mrg   auto *use = allocate<use_info> (insn, resource, value);
    433  1.1  mrg   add_use (use);
    434  1.1  mrg   return use;
    435  1.1  mrg }
    436  1.1  mrg 
    437  1.1  mrg // Called while building SSA form using BI.  Record that INSN contains
    438  1.1  mrg // read reference REF.  If this requires new entries to be added to
    439  1.1  mrg // INSN->uses (), add those entries to the list we're building in
    440  1.1  mrg // m_temp_uses.
    441  1.1  mrg void
    442  1.1  mrg function_info::record_use (build_info &bi, insn_info *insn,
    443  1.1  mrg 			   rtx_obj_reference ref)
    444  1.1  mrg {
    445  1.1  mrg   unsigned int regno = ref.regno;
    446  1.1  mrg   machine_mode mode = ref.is_reg () ? ref.mode : BLKmode;
    447  1.1  mrg   access_info *access = bi.last_access[ref.regno + 1];
    448  1.1  mrg   use_info *use = safe_dyn_cast<use_info *> (access);
    449  1.1  mrg   if (!use)
    450  1.1  mrg     {
    451  1.1  mrg       set_info *value = safe_dyn_cast<set_info *> (access);
    452  1.1  mrg       // In order to ensure that -g doesn't affect codegen, uses in debug
    453  1.1  mrg       // instructions do not affect liveness, either in DF or here.
    454  1.1  mrg       // This means that there might be no correct definition of the resource
    455  1.1  mrg       // available (e.g. if it would require a phi node that the nondebug
    456  1.1  mrg       // code doesn't need).  Perhaps we could have "debug phi nodes" as
    457  1.1  mrg       // well as "debug instructions", but that would require a method
    458  1.1  mrg       // of building phi nodes that didn't depend on DF liveness information,
    459  1.1  mrg       // and so might be significantly more expensive.
    460  1.1  mrg       //
    461  1.1  mrg       // Therefore, the only value we try to attach to a use by a debug
    462  1.1  mrg       // instruction is VALUE itself (as we would for nondebug instructions).
    463  1.1  mrg       // We then need to make a conservative check for whether VALUE is
    464  1.1  mrg       // actually correct.
    465  1.1  mrg       auto value_is_valid = [&]()
    466  1.1  mrg 	{
    467  1.1  mrg 	  // Memmory always has a valid definition.
    468  1.1  mrg 	  if (ref.is_mem ())
    469  1.1  mrg 	    return true;
    470  1.1  mrg 
    471  1.1  mrg 	  // If VALUE would lead to an uninitialized use anyway, there's
    472  1.1  mrg 	  // nothing to check.
    473  1.1  mrg 	  if (!value)
    474  1.1  mrg 	    return false;
    475  1.1  mrg 
    476  1.1  mrg 	  // If the previous definition occurs in the same EBB then it
    477  1.1  mrg 	  // is certainly correct.
    478  1.1  mrg 	  if (value->ebb () == bi.current_ebb)
    479  1.1  mrg 	    return true;
    480  1.1  mrg 
    481  1.1  mrg 	  // Check if VALUE is the function's only definition of REGNO.
    482  1.1  mrg 	  // (We already know that it dominates the use.)
    483  1.1  mrg 	  if (!bitmap_bit_p (bi.potential_phi_regs, regno))
    484  1.1  mrg 	    return true;
    485  1.1  mrg 
    486  1.1  mrg 	  // If the register is live on entry to the EBB but not used
    487  1.1  mrg 	  // within it, VALUE is the correct live-in value.
    488  1.1  mrg 	  if (!bi.ebb_live_in_for_debug)
    489  1.1  mrg 	    calculate_ebb_live_in_for_debug (bi);
    490  1.1  mrg 	  if (bitmap_bit_p (bi.ebb_live_in_for_debug, regno))
    491  1.1  mrg 	    return true;
    492  1.1  mrg 
    493  1.1  mrg 	  // Punt for other cases.
    494  1.1  mrg 	  return false;
    495  1.1  mrg 	};
    496  1.1  mrg       if (insn->is_debug_insn () && !value_is_valid ())
    497  1.1  mrg 	value = nullptr;
    498  1.1  mrg 
    499  1.1  mrg       use = create_reg_use (bi, insn, { mode, regno });
    500  1.1  mrg       m_temp_uses.safe_push (use);
    501  1.1  mrg       bi.last_access[ref.regno + 1] = use;
    502  1.1  mrg       use->record_reference (ref, true);
    503  1.1  mrg     }
    504  1.1  mrg   else
    505  1.1  mrg     {
    506  1.1  mrg       // Record the mode of the largest use.  The choice is arbitrary if
    507  1.1  mrg       // the instruction (unusually) references the same register in two
    508  1.1  mrg       // different but equal-sized modes.
    509  1.1  mrg       gcc_checking_assert (use->insn () == insn);
    510  1.1  mrg       if (HARD_REGISTER_NUM_P (regno)
    511  1.1  mrg 	  && partial_subreg_p (use->mode (), mode))
    512  1.1  mrg 	use->set_mode (mode);
    513  1.1  mrg       use->record_reference (ref, false);
    514  1.1  mrg     }
    515  1.1  mrg }
    516  1.1  mrg 
    517  1.1  mrg // Called while building SSA form for INSN using BI.  Record the effect
    518  1.1  mrg // of call clobbers in RTL.  We have already added the explicit sets and
    519  1.1  mrg // clobbers for RTL, which have priority over any call clobbers.
    520  1.1  mrg void
    521  1.1  mrg function_info::record_call_clobbers (build_info &bi, insn_info *insn,
    522  1.1  mrg 				     rtx_call_insn *rtl)
    523  1.1  mrg {
    524  1.1  mrg   // See whether we should record this call in the EBB's list of
    525  1.1  mrg   // call clobbers.  Three things affect this choice:
    526  1.1  mrg   //
    527  1.1  mrg   // (1) The list is the only way we have of recording partial clobbers.
    528  1.1  mrg   //     All calls that only partially clobber registers must therefore
    529  1.1  mrg   //     be in the list.
    530  1.1  mrg   //
    531  1.1  mrg   // (2) Adding calls to the list is much more memory-efficient than
    532  1.1  mrg   //     creating a long list of clobber_infos.
    533  1.1  mrg   //
    534  1.1  mrg   // (3) Adding calls to the list limits the ability to move definitions
    535  1.1  mrg   //     of registers that are normally fully or partially clobbered
    536  1.1  mrg   //     by the associated predefined ABI.  So adding calls to the list
    537  1.1  mrg   //     can hamper optimization if (thanks to -fipa-ra) the number of
    538  1.1  mrg   //     clobbers is much smaller than the usual set.
    539  1.1  mrg   //
    540  1.1  mrg   // The trade-off that we currently take is to use the list if there
    541  1.1  mrg   // are some registers that the call only partially clobbers or if
    542  1.1  mrg   // the set of clobbers is the standard set.
    543  1.1  mrg   function_abi abi = insn_callee_abi (rtl);
    544  1.1  mrg   if (abi.base_abi ().full_reg_clobbers () == abi.full_reg_clobbers ()
    545  1.1  mrg       || abi.full_and_partial_reg_clobbers () != abi.full_reg_clobbers ())
    546  1.1  mrg     {
    547  1.1  mrg       // Find an entry for this predefined ABI, creating one if necessary.
    548  1.1  mrg       ebb_call_clobbers_info *ecc = bi.current_ebb->first_call_clobbers ();
    549  1.1  mrg       while (ecc && ecc->abi () != &abi.base_abi ())
    550  1.1  mrg 	ecc = ecc->next ();
    551  1.1  mrg       if (!ecc)
    552  1.1  mrg 	{
    553  1.1  mrg 	  ecc = allocate<ebb_call_clobbers_info> (&abi.base_abi ());
    554  1.1  mrg 	  ecc->m_next = bi.current_ebb->first_call_clobbers ();
    555  1.1  mrg 	  bi.current_ebb->set_first_call_clobbers (ecc);
    556  1.1  mrg 	}
    557  1.1  mrg 
    558  1.1  mrg       auto abi_id = abi.base_abi ().id ();
    559  1.1  mrg       auto *insn_clobbers = allocate<insn_call_clobbers_note> (abi_id, insn);
    560  1.1  mrg       insn->add_note (insn_clobbers);
    561  1.1  mrg 
    562  1.1  mrg       ecc->insert_max_node (insn_clobbers);
    563  1.1  mrg     }
    564  1.1  mrg   else
    565  1.1  mrg     for (unsigned int regno = 0; regno < FIRST_PSEUDO_REGISTER; ++regno)
    566  1.1  mrg       if (TEST_HARD_REG_BIT (abi.full_reg_clobbers (), regno))
    567  1.1  mrg 	{
    568  1.1  mrg 	  def_info *def = m_defs[regno + 1];
    569  1.1  mrg 	  if (!def || def->last_def ()->insn () != insn)
    570  1.1  mrg 	    {
    571  1.1  mrg 	      def = allocate<clobber_info> (insn, regno);
    572  1.1  mrg 	      def->m_is_call_clobber = true;
    573  1.1  mrg 	      append_def (def);
    574  1.1  mrg 	      m_temp_defs.safe_push (def);
    575  1.1  mrg 	      bi.record_reg_def (def);
    576  1.1  mrg 	    }
    577  1.1  mrg 	}
    578  1.1  mrg }
    579  1.1  mrg 
    580  1.1  mrg // Called while building SSA form using BI.  Record that INSN contains
    581  1.1  mrg // write reference REF.  Add associated def_infos to the list of accesses
    582  1.1  mrg // that we're building in m_temp_defs.  Record the register's new live
    583  1.1  mrg // value in BI.
    584  1.1  mrg void
    585  1.1  mrg function_info::record_def (build_info &bi, insn_info *insn,
    586  1.1  mrg 			   rtx_obj_reference ref)
    587  1.1  mrg {
    588  1.1  mrg   // Punt if we see multiple definitions of the same resource.
    589  1.1  mrg   // This can happen for several reasons:
    590  1.1  mrg   //
    591  1.1  mrg   // - An instruction might store two values to memory at once, giving two
    592  1.1  mrg   //   distinct memory references.
    593  1.1  mrg   //
    594  1.1  mrg   // - An instruction might assign to multiple pieces of a wide pseudo
    595  1.1  mrg   //   register.  For example, on 32-bit targets, an instruction might
    596  1.1  mrg   //   assign to both the upper and lower halves of a 64-bit pseudo register.
    597  1.1  mrg   //
    598  1.1  mrg   // - It's possible for the same register to be clobbered by the
    599  1.1  mrg   //   CALL_INSN_FUNCTION_USAGE and to be set by the main instruction
    600  1.1  mrg   //   pattern as well.  In that case, the clobber conceptually happens
    601  1.1  mrg   //   before the set and can essentially be ignored.
    602  1.1  mrg   //
    603  1.1  mrg   // - Similarly, global registers are implicitly set by a call but can
    604  1.1  mrg   //   be explicitly set or clobbered as well.  In that situation, the sets
    605  1.1  mrg   //   are listed first and should win over a clobber.
    606  1.1  mrg   unsigned int regno = ref.regno;
    607  1.1  mrg   machine_mode mode = ref.is_reg () ? ref.mode : BLKmode;
    608  1.1  mrg   def_info *def = safe_dyn_cast<def_info *> (bi.last_access[ref.regno + 1]);
    609  1.1  mrg   if (def && def->insn () == insn)
    610  1.1  mrg     {
    611  1.1  mrg       if (!ref.is_clobber ())
    612  1.1  mrg 	{
    613  1.1  mrg 	  gcc_checking_assert (!is_a<clobber_info *> (def));
    614  1.1  mrg 	  def->record_reference (ref, false);
    615  1.1  mrg 	}
    616  1.1  mrg       return;
    617  1.1  mrg     }
    618  1.1  mrg 
    619  1.1  mrg   // Memory is always well-defined, so only use clobber_infos for registers.
    620  1.1  mrg   if (ref.is_reg () && ref.is_clobber ())
    621  1.1  mrg     def = allocate<clobber_info> (insn, regno);
    622  1.1  mrg   else
    623  1.1  mrg     def = allocate<set_info> (insn, resource_info { mode, regno });
    624  1.1  mrg   def->record_reference (ref, true);
    625  1.1  mrg   append_def (def);
    626  1.1  mrg   m_temp_defs.safe_push (def);
    627  1.1  mrg   bi.record_reg_def (def);
    628  1.1  mrg }
    629  1.1  mrg 
    630  1.1  mrg // Called while building SSA form using BI.  Add an insn_info for RTL
    631  1.1  mrg // to the block that we're current building.
    632  1.1  mrg void
    633  1.1  mrg function_info::add_insn_to_block (build_info &bi, rtx_insn *rtl)
    634  1.1  mrg {
    635  1.1  mrg   insn_info *insn = allocate<insn_info> (bi.current_bb, rtl, UNKNOWN_COST);
    636  1.1  mrg   append_insn (insn);
    637  1.1  mrg 
    638  1.1  mrg   vec_rtx_properties properties;
    639  1.1  mrg   properties.add_insn (rtl, true);
    640  1.1  mrg   insn->set_properties (properties);
    641  1.1  mrg 
    642  1.1  mrg   start_insn_accesses ();
    643  1.1  mrg 
    644  1.1  mrg   // Record the uses.
    645  1.1  mrg   for (rtx_obj_reference ref : properties.refs ())
    646  1.1  mrg     if (ref.is_read ())
    647  1.1  mrg       record_use (bi, insn, ref);
    648  1.1  mrg 
    649  1.1  mrg   // Restore the contents of bi.last_access, which we used as a cache
    650  1.1  mrg   // when assembling the uses.
    651  1.1  mrg   for (access_info *access : m_temp_uses)
    652  1.1  mrg     {
    653  1.1  mrg       unsigned int regno = access->regno ();
    654  1.1  mrg       gcc_checking_assert (bi.last_access[regno + 1] == access);
    655  1.1  mrg       bi.last_access[regno + 1] = as_a<use_info *> (access)->def ();
    656  1.1  mrg     }
    657  1.1  mrg 
    658  1.1  mrg   // Record the definitions.
    659  1.1  mrg   for (rtx_obj_reference ref : properties.refs ())
    660  1.1  mrg     if (ref.is_write ())
    661  1.1  mrg       record_def (bi, insn, ref);
    662  1.1  mrg 
    663  1.1  mrg   // Logically these happen before the explicit definitions, but if the
    664  1.1  mrg   // explicit definitions and call clobbers reference the same register,
    665  1.1  mrg   // the explicit definition should win.
    666  1.1  mrg   if (auto *call_rtl = dyn_cast<rtx_call_insn *> (rtl))
    667  1.1  mrg     record_call_clobbers (bi, insn, call_rtl);
    668  1.1  mrg 
    669  1.1  mrg   finish_insn_accesses (insn);
    670  1.1  mrg }
    671  1.1  mrg 
    672  1.1  mrg // Check whether INSN sets any registers that are never subsequently used.
    673  1.1  mrg // If so, add REG_UNUSED notes for them.  The caller has already removed
    674  1.1  mrg // any previous REG_UNUSED notes.
    675  1.1  mrg void
    676  1.1  mrg function_info::add_reg_unused_notes (insn_info *insn)
    677  1.1  mrg {
    678  1.1  mrg   rtx_insn *rtl = insn->rtl ();
    679  1.1  mrg 
    680  1.1  mrg   auto handle_potential_set = [&](rtx pattern)
    681  1.1  mrg     {
    682  1.1  mrg       if (GET_CODE (pattern) != SET)
    683  1.1  mrg 	return;
    684  1.1  mrg 
    685  1.1  mrg       rtx dest = SET_DEST (pattern);
    686  1.1  mrg       if (!REG_P (dest))
    687  1.1  mrg 	return;
    688  1.1  mrg 
    689  1.1  mrg       def_array defs = insn->defs ();
    690  1.1  mrg       unsigned int index = find_access_index (defs, REGNO (dest));
    691  1.1  mrg       for (unsigned int i = 0; i < REG_NREGS (dest); ++i)
    692  1.1  mrg 	{
    693  1.1  mrg 	  def_info *def = defs[index + i];
    694  1.1  mrg 	  gcc_checking_assert (def->regno () == REGNO (dest) + i);
    695  1.1  mrg 	  set_info *set = dyn_cast<set_info *> (def);
    696  1.1  mrg 	  if (set && set->has_nondebug_uses ())
    697  1.1  mrg 	    return;
    698  1.1  mrg 	}
    699  1.1  mrg       add_reg_note (rtl, REG_UNUSED, dest);
    700  1.1  mrg     };
    701  1.1  mrg 
    702  1.1  mrg   rtx pattern = PATTERN (rtl);
    703  1.1  mrg   if (GET_CODE (pattern) == PARALLEL)
    704  1.1  mrg     for (int i = 0; i < XVECLEN (pattern, 0); ++i)
    705  1.1  mrg       handle_potential_set (XVECEXP (pattern, 0, i));
    706  1.1  mrg   else
    707  1.1  mrg     handle_potential_set (pattern);
    708  1.1  mrg }
    709  1.1  mrg 
    710  1.1  mrg // Search TREE for call clobbers at INSN.  Return:
    711  1.1  mrg //
    712  1.1  mrg // - less than zero if INSN occurs before the root of TREE
    713  1.1  mrg // - 0 if INSN is the root of TREE
    714  1.1  mrg // - greater than zero if INSN occurs after the root of TREE
    715  1.1  mrg int
    716  1.1  mrg rtl_ssa::lookup_call_clobbers (insn_call_clobbers_tree &tree, insn_info *insn)
    717  1.1  mrg {
    718  1.1  mrg   auto compare = [&](insn_call_clobbers_note *clobbers)
    719  1.1  mrg     {
    720  1.1  mrg       return insn->compare_with (clobbers->insn ());
    721  1.1  mrg     };
    722  1.1  mrg   return tree.lookup (compare);
    723  1.1  mrg }
    724  1.1  mrg 
    725  1.1  mrg // Print a description of INSN to PP.
    726  1.1  mrg void
    727  1.1  mrg rtl_ssa::pp_insn (pretty_printer *pp, const insn_info *insn)
    728  1.1  mrg {
    729  1.1  mrg   if (!insn)
    730  1.1  mrg     pp_string (pp, "<null>");
    731  1.1  mrg   else
    732  1.1  mrg     insn->print_full (pp);
    733  1.1  mrg }
    734  1.1  mrg 
    735  1.1  mrg // Print a description of INSN to FILE.
    736  1.1  mrg void
    737  1.1  mrg dump (FILE *file, const insn_info *insn)
    738  1.1  mrg {
    739  1.1  mrg   dump_using (file, pp_insn, insn);
    740  1.1  mrg }
    741  1.1  mrg 
    742  1.1  mrg // Debug interface to the dump routine above.
    743  1.1  mrg void debug (const insn_info *x) { dump (stderr, x); }
    744