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