xref: /netbsd-src/external/gpl3/gcc/dist/gcc/rtl-ssa/functions.cc (revision b1e838363e3c6fc78a55519254d99869742dd33c)
1 // Implementation of function-related RTL SSA functions             -*- C++ -*-
2 // Copyright (C) 2020-2022 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 #define INCLUDE_ALGORITHM
21 #define INCLUDE_FUNCTIONAL
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "backend.h"
26 #include "rtl.h"
27 #include "df.h"
28 #include "rtl-ssa.h"
29 #include "rtl-ssa/internals.h"
30 #include "rtl-ssa/internals.inl"
31 
32 using namespace rtl_ssa;
33 
function_info(function * fn)34 function_info::function_info (function *fn)
35   : m_fn (fn)
36 {
37   // Force the alignment to be obstack_alignment.  Everything else is normal.
38   obstack_specify_allocation (&m_obstack, OBSTACK_CHUNK_SIZE,
39 			      obstack_alignment, obstack_chunk_alloc,
40 			      obstack_chunk_free);
41   obstack_specify_allocation (&m_temp_obstack, OBSTACK_CHUNK_SIZE,
42 			      obstack_alignment, obstack_chunk_alloc,
43 			      obstack_chunk_free);
44 
45   // Record the start of the obstacks.
46   m_obstack_start = XOBNEWVAR (&m_obstack, char, 0);
47   m_temp_obstack_start = XOBNEWVAR (&m_temp_obstack, char, 0);
48 
49   init_function_data ();
50   process_all_blocks ();
51   simplify_phis ();
52 }
53 
~function_info()54 function_info::~function_info ()
55 {
56   // Anything using the temporary obstack should free it afterwards,
57   // preferably via temp_watermark ().
58   gcc_assert (XOBNEWVAR (&m_temp_obstack, char, 0) == m_temp_obstack_start);
59 
60   obstack_free (&m_temp_obstack, nullptr);
61   obstack_free (&m_obstack, nullptr);
62 }
63 
64 // See the comment above the declaration.
65 void
print(pretty_printer * pp) const66 function_info::print (pretty_printer *pp) const
67 {
68   pp_string (pp, "Function: ");
69   pp_string (pp, function_name (m_fn));
70   for (ebb_info *ebb : ebbs ())
71     {
72       pp_newline (pp);
73       pp_newline_and_indent (pp, 0);
74       pp_ebb (pp, ebb);
75     }
76 }
77 
78 // Initialize all member variables in preparation for (re)building
79 // SSA form from scratch.
80 void
init_function_data()81 function_info::init_function_data ()
82 {
83   m_next_artificial_uid = -1;
84   m_next_phi_uid = 0;
85   m_num_regs = max_reg_num ();
86   m_defs.safe_grow_cleared (m_num_regs + 1);
87   m_bbs.safe_grow_cleared (last_basic_block_for_fn (m_fn));
88   m_first_bb = nullptr;
89   m_last_bb = nullptr;
90   m_first_insn = nullptr;
91   m_last_insn = nullptr;
92   m_last_nondebug_insn = nullptr;
93   m_free_phis = nullptr;
94 }
95 
96 // The initial phase of the phi simplification process.  The cumulative
97 // effect of the initial phase is to set up ASSUMED_VALUES such that,
98 // for a phi P with uid ID:
99 //
100 // - if we think all inputs to P have the same value, ASSUMED_VALUES[ID]
101 //   is that value
102 //
103 // - otherwise, ASSUMED_VALUES[ID] is P.
104 //
105 // This has already been done for phis with a lower uid than PHI,
106 // initially making optimistic assumptions about backedge inputs.
107 // Now do the same for PHI.  If this might invalidate any assumptions
108 // made for earlier phis, add the uids of those phis to WORKLIST.
109 void
simplify_phi_setup(phi_info * phi,set_info ** assumed_values,bitmap worklist)110 function_info::simplify_phi_setup (phi_info *phi, set_info **assumed_values,
111 				   bitmap worklist)
112 {
113   // If all non-backedge inputs have the same value, set NEW_VALUE
114   // to that value.  Otherwise set NEW_VALUE to PHI, to indicate
115   // that PHI cannot be simplified.
116   unsigned int phi_uid = phi->uid ();
117   bool is_first_input = true;
118   set_info *new_value = nullptr;
119   machine_mode phi_mode = phi->mode ();
120   for (use_info *input : phi->inputs ())
121     {
122       set_info *def = input->def ();
123 
124       if (auto *input_phi = safe_dyn_cast<phi_info *> (def))
125 	{
126 	  // Ignore backedges for now.
127 	  unsigned int input_phi_uid = input_phi->uid ();
128 	  if (phi_uid <= input_phi_uid)
129 	    continue;
130 
131 	  def = assumed_values[input_phi_uid];
132 	}
133 
134       // Compare this definition with previous ones.
135       if (is_first_input)
136 	{
137 	  new_value = def;
138 	  is_first_input = false;
139 	}
140       else if (new_value != def)
141 	new_value = phi;
142 
143       // If the input has a known mode (i.e. not BLKmode), make sure
144       // that the phi's mode is at least as large.
145       if (def)
146 	phi_mode = combine_modes (phi_mode, def->mode ());
147     }
148   if (phi->mode () != phi_mode)
149     phi->set_mode (phi_mode);
150 
151   // Since we use a reverse postorder traversal, no phi can consist
152   // entirely of backedges.
153   gcc_checking_assert (!is_first_input);
154   assumed_values[phi_uid] = new_value;
155 
156   // See whether any assumptions for earlier phis are now invalid.
157   simplify_phi_propagate (phi, assumed_values, nullptr, worklist);
158 }
159 
160 // The propagation phase of the phi simplification process, with
161 // ASSUMED_VALUES as described above simplify_phi_setup.  Iteratively
162 // update the phis that use PHI based on PHI's entry in ASSUMED_VALUES.
163 // If CURR_WORKLIST is null, consider only phi uses with a lower uid
164 // than PHI, otherwise consider all phi uses.
165 //
166 // If a phi with a higher uid than PHI needs updating, add its uid to
167 // CURR_WORKLIST; if a phi with a lower uid than PHI needs updating,
168 // add its uid to NEXT_WORKLIST.
169 void
simplify_phi_propagate(phi_info * phi,set_info ** assumed_values,bitmap curr_worklist,bitmap next_worklist)170 function_info::simplify_phi_propagate (phi_info *phi,
171 				       set_info **assumed_values,
172 				       bitmap curr_worklist,
173 				       bitmap next_worklist)
174 {
175   // Go through each phi user of PHI to see whether it needs updating.
176   unsigned int phi_uid = phi->uid ();
177   machine_mode phi_mode = phi->mode ();
178   set_info *phi_value = assumed_values[phi_uid];
179   for (use_info *use : phi->phi_uses ())
180     {
181       phi_info *user_phi = use->phi ();
182 
183       // Propagate the phi's new mode to all phi users.  Insn uses should
184       // not be updated, since their modes reflect a property of the insns
185       // rather than the phi.
186       if (use->mode () != phi_mode)
187 	use->set_mode (phi_mode);
188 
189       if (user_phi == phi)
190 	continue;
191 
192       // If this is a phi we should be looking at, see whether it needs
193       // an update.
194       unsigned int user_phi_uid = user_phi->uid ();
195       if (user_phi_uid < phi_uid || curr_worklist)
196 	{
197 	  bool needs_update = false;
198 
199 	  // Make sure that USER_PHI's mode is at least as big as PHI_MODE.
200 	  machine_mode user_phi_mode = user_phi->mode ();
201 	  machine_mode new_mode = combine_modes (user_phi_mode, phi_mode);
202 	  if (user_phi_mode != new_mode)
203 	    {
204 	      user_phi->set_mode (new_mode);
205 	      needs_update = true;
206 	    }
207 
208 	  // If USER_PHI optimistically assumed an incorrect value,
209 	  // adjust it now.
210 	  if (assumed_values[user_phi_uid] != user_phi
211 	      && assumed_values[user_phi_uid] != phi_value)
212 	    {
213 	      assumed_values[user_phi_uid] = user_phi;
214 	      needs_update = true;
215 	    }
216 
217 	  if (needs_update)
218 	    {
219 	      if (user_phi_uid < phi_uid)
220 		bitmap_set_bit (next_worklist, user_phi_uid);
221 	      else
222 		bitmap_set_bit (curr_worklist, user_phi_uid);
223 	    }
224 	}
225     }
226 }
227 
228 // Update the modes of all phis so that they are at least as big as
229 // all inputs.  Remove any non-degenerate phis whose inputs are all equal.
230 void
simplify_phis()231 function_info::simplify_phis ()
232 {
233   auto temps = temp_watermark ();
234 
235   // See the comment above simplify_phi_setup for details about this array.
236   auto *assumed_values = XOBNEWVEC (&m_temp_obstack, set_info *,
237 				    m_next_phi_uid);
238 
239   // An array of all phis, indexed by uid.
240   auto *phis = XOBNEWVEC (&m_temp_obstack, phi_info *, m_next_phi_uid);
241 
242   // Which phi uids are actually in use.
243   auto_sbitmap valid_phi_uids (m_next_phi_uid);
244   bitmap_clear (valid_phi_uids);
245 
246   // Bitmaps used for the main double-queue propagation phase.
247   auto_bitmap worklist1;
248   auto_bitmap worklist2;
249   bitmap curr_worklist = worklist1;
250   bitmap next_worklist = worklist2;
251 
252   // Perform the set-up phase; see simplify_phi_setup for details.
253   for (ebb_info *ebb : ebbs ())
254     for (phi_info *phi : ebb->phis ())
255       {
256 	bitmap_set_bit (valid_phi_uids, phi->uid ());
257 	phis[phi->uid ()] = phi;
258 	simplify_phi_setup (phi, assumed_values, curr_worklist);
259       }
260 
261   // Iteratively process any phis that need updating; see
262   // simplify_phi_propagate for details.  Using a double queue
263   // should reduce the number of times that any given phi node
264   // needs to be revisited.
265   while (!bitmap_empty_p (curr_worklist))
266     {
267       do
268 	{
269 	  unsigned int uid = bitmap_first_set_bit (curr_worklist);
270 	  bitmap_clear_bit (curr_worklist, uid);
271 	  simplify_phi_propagate (phis[uid], assumed_values,
272 				  curr_worklist, next_worklist);
273 	}
274       while (!bitmap_empty_p (curr_worklist));
275       std::swap (next_worklist, curr_worklist);
276     }
277 
278   // Make sure that assumed_values is a transitive closure.  This ensures
279   // that each use_info is only updated once.
280   if (flag_checking)
281     for (unsigned int i = 0; i < m_next_phi_uid; ++i)
282       if (bitmap_bit_p (valid_phi_uids, i))
283 	if (auto *new_phi = safe_dyn_cast<phi_info *> (assumed_values[i]))
284 	  gcc_assert (assumed_values[new_phi->uid ()] == new_phi);
285 
286   // Update any phis that turned out to be equivalent to a single input.
287   for (unsigned int i = 0; i < m_next_phi_uid; ++i)
288     if (bitmap_bit_p (valid_phi_uids, i) && phis[i] != assumed_values[i])
289       replace_phi (phis[i], assumed_values[i]);
290 }
291 
292 // Print a description of FUNCTION to PP.
293 void
pp_function(pretty_printer * pp,const function_info * function)294 rtl_ssa::pp_function (pretty_printer *pp, const function_info *function)
295 {
296   function->print (pp);
297 }
298 
299 // Print a description of FUNCTION to FILE.
300 void
dump(FILE * file,const function_info * function)301 dump (FILE *file, const function_info *function)
302 {
303   dump_using (file, pp_function, function);
304 }
305 
306 // Debug interface to the dump routine above.
debug(const function_info * x)307 void debug (const function_info *x) { dump (stderr, x); }
308