Branch data Line data Source code
1 : : // Implementation of function-related RTL SSA functions -*- 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 : : #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 : :
34 : 1975264 : function_info::function_info (function *fn)
35 : 3950528 : : m_fn (fn), m_clobbered_by_calls ()
36 : : {
37 : : // Force the alignment to be obstack_alignment. Everything else is normal.
38 : 1975264 : obstack_specify_allocation (&m_obstack, OBSTACK_CHUNK_SIZE,
39 : : obstack_alignment, obstack_chunk_alloc,
40 : : obstack_chunk_free);
41 : 1975264 : 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 : 1975264 : m_obstack_start = XOBNEWVAR (&m_obstack, char, 0);
47 : 1975264 : m_temp_obstack_start = XOBNEWVAR (&m_temp_obstack, char, 0);
48 : :
49 : 1975264 : init_function_data ();
50 : 1975264 : process_all_blocks ();
51 : 1975264 : simplify_phis ();
52 : 1975264 : }
53 : :
54 : 1975264 : function_info::~function_info ()
55 : : {
56 : : // Anything using the temporary obstack should free it afterwards,
57 : : // preferably via temp_watermark ().
58 : 1975264 : gcc_assert (XOBNEWVAR (&m_temp_obstack, char, 0) == m_temp_obstack_start);
59 : :
60 : 1975264 : obstack_free (&m_temp_obstack, nullptr);
61 : 1975264 : obstack_free (&m_obstack, nullptr);
62 : 1975264 : }
63 : :
64 : : // See the comment above the declaration.
65 : : void
66 : 0 : function_info::print (pretty_printer *pp) const
67 : : {
68 : 0 : pp_string (pp, "Function: ");
69 : 0 : pp_string (pp, function_name (m_fn));
70 : 0 : for (ebb_info *ebb : ebbs ())
71 : : {
72 : 0 : pp_newline (pp);
73 : 0 : pp_newline_and_indent (pp, 0);
74 : 0 : pp_ebb (pp, ebb);
75 : : }
76 : 0 : }
77 : :
78 : : // Initialize all member variables in preparation for (re)building
79 : : // SSA form from scratch.
80 : : void
81 : 1975264 : function_info::init_function_data ()
82 : : {
83 : 1975264 : m_next_artificial_uid = -1;
84 : 1975264 : m_next_phi_uid = 0;
85 : 1975264 : m_num_regs = max_reg_num ();
86 : 1975264 : m_defs.safe_grow_cleared (m_num_regs + 1);
87 : 1975264 : m_bbs.safe_grow_cleared (last_basic_block_for_fn (m_fn));
88 : 1975264 : m_first_bb = nullptr;
89 : 1975264 : m_last_bb = nullptr;
90 : 1975264 : m_first_insn = nullptr;
91 : 1975264 : m_last_insn = nullptr;
92 : 1975264 : m_last_nondebug_insn = nullptr;
93 : 1975264 : m_free_phis = nullptr;
94 : 1975264 : }
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
110 : 25449971 : 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 : 25449971 : unsigned int phi_uid = phi->uid ();
117 : 25449971 : bool is_first_input = true;
118 : 25449971 : set_info *new_value = nullptr;
119 : 25449971 : machine_mode phi_mode = phi->mode ();
120 : 93960058 : for (use_info *input : phi->inputs ())
121 : : {
122 : 43060116 : set_info *def = input->def ();
123 : :
124 : 43060116 : if (auto *input_phi = safe_dyn_cast<phi_info *> (def))
125 : : {
126 : : // Ignore backedges for now.
127 : 10509830 : unsigned int input_phi_uid = input_phi->uid ();
128 : 10509830 : if (phi_uid <= input_phi_uid)
129 : 933169 : continue;
130 : :
131 : 9576661 : def = assumed_values[input_phi_uid];
132 : : }
133 : :
134 : : // Compare this definition with previous ones.
135 : 42126947 : if (is_first_input)
136 : : {
137 : : new_value = def;
138 : : is_first_input = false;
139 : : }
140 : 16676976 : else if (new_value != def)
141 : 15864157 : 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 : 42126947 : if (def)
146 : 42095720 : phi_mode = combine_modes (phi_mode, def->mode ());
147 : : }
148 : 25449971 : if (phi->mode () != phi_mode)
149 : 8386967 : phi->set_mode (phi_mode);
150 : :
151 : : // Since we use a reverse postorder traversal, no phi can consist
152 : : // entirely of backedges.
153 : 25449971 : gcc_checking_assert (!is_first_input);
154 : 25449971 : assumed_values[phi_uid] = new_value;
155 : :
156 : : // See whether any assumptions for earlier phis are now invalid.
157 : 25449971 : simplify_phi_propagate (phi, assumed_values, nullptr, worklist);
158 : 25449971 : }
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
170 : 26407611 : 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 : 26407611 : unsigned int phi_uid = phi->uid ();
177 : 26407611 : machine_mode phi_mode = phi->mode ();
178 : 26407611 : set_info *phi_value = assumed_values[phi_uid];
179 : 65250964 : for (use_info *use : phi->phi_uses ())
180 : : {
181 : 12435742 : 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 : 12435742 : if (use->mode () != phi_mode)
187 : 6835390 : use->set_mode (phi_mode);
188 : :
189 : 12435742 : if (user_phi == phi)
190 : 409921 : continue;
191 : :
192 : : // If this is a phi we should be looking at, see whether it needs
193 : : // an update.
194 : 12025821 : unsigned int user_phi_uid = user_phi->uid ();
195 : 12025821 : if (user_phi_uid < phi_uid || curr_worklist)
196 : : {
197 : 2449160 : bool needs_update = false;
198 : :
199 : : // Make sure that USER_PHI's mode is at least as big as PHI_MODE.
200 : 2449160 : machine_mode user_phi_mode = user_phi->mode ();
201 : 2449160 : machine_mode new_mode = combine_modes (user_phi_mode, phi_mode);
202 : 2449160 : if (user_phi_mode != new_mode)
203 : : {
204 : 0 : user_phi->set_mode (new_mode);
205 : 0 : needs_update = true;
206 : : }
207 : :
208 : : // If USER_PHI optimistically assumed an incorrect value,
209 : : // adjust it now.
210 : 2449160 : if (assumed_values[user_phi_uid] != user_phi
211 : 1041828 : && assumed_values[user_phi_uid] != phi_value)
212 : : {
213 : 957640 : assumed_values[user_phi_uid] = user_phi;
214 : 957640 : needs_update = true;
215 : : }
216 : :
217 : 2449160 : if (needs_update)
218 : : {
219 : 957640 : if (user_phi_uid < phi_uid)
220 : 467608 : bitmap_set_bit (next_worklist, user_phi_uid);
221 : : else
222 : 490032 : bitmap_set_bit (curr_worklist, user_phi_uid);
223 : : }
224 : : }
225 : : }
226 : 26407611 : }
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
231 : 1975264 : function_info::simplify_phis ()
232 : : {
233 : 1975264 : auto temps = temp_watermark ();
234 : :
235 : : // See the comment above simplify_phi_setup for details about this array.
236 : 1975264 : 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 : 1975264 : auto *phis = XOBNEWVEC (&m_temp_obstack, phi_info *, m_next_phi_uid);
241 : :
242 : : // Which phi uids are actually in use.
243 : 1975264 : auto_sbitmap valid_phi_uids (m_next_phi_uid);
244 : 1975264 : bitmap_clear (valid_phi_uids);
245 : :
246 : : // Bitmaps used for the main double-queue propagation phase.
247 : 1975264 : auto_bitmap worklist1;
248 : 1975264 : auto_bitmap worklist2;
249 : 1975264 : bitmap curr_worklist = worklist1;
250 : 1975264 : bitmap next_worklist = worklist2;
251 : :
252 : : // Perform the set-up phase; see simplify_phi_setup for details.
253 : 31214362 : for (ebb_info *ebb : ebbs ())
254 : 40069520 : for (phi_info *phi : ebb->phis ())
255 : : {
256 : 25449971 : bitmap_set_bit (valid_phi_uids, phi->uid ());
257 : 25449971 : phis[phi->uid ()] = phi;
258 : 25449971 : 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 : 2088941 : while (!bitmap_empty_p (curr_worklist))
266 : : {
267 : 957640 : do
268 : : {
269 : 957640 : unsigned int uid = bitmap_first_set_bit (curr_worklist);
270 : 957640 : bitmap_clear_bit (curr_worklist, uid);
271 : 957640 : simplify_phi_propagate (phis[uid], assumed_values,
272 : : curr_worklist, next_worklist);
273 : : }
274 : 957640 : 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 : 1975264 : if (flag_checking)
281 : 27427398 : for (unsigned int i = 0; i < m_next_phi_uid; ++i)
282 : 25452178 : if (bitmap_bit_p (valid_phi_uids, i))
283 : 50900707 : if (auto *new_phi = safe_dyn_cast<phi_info *> (assumed_values[i]))
284 : 12701735 : 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 : 27427614 : for (unsigned int i = 0; i < m_next_phi_uid; ++i)
288 : 25452350 : if (bitmap_bit_p (valid_phi_uids, i) && phis[i] != assumed_values[i])
289 : 15932326 : replace_phi (phis[i], assumed_values[i]);
290 : 1975264 : }
291 : :
292 : : // Print a description of FUNCTION to PP.
293 : : void
294 : 0 : rtl_ssa::pp_function (pretty_printer *pp, const function_info *function)
295 : : {
296 : 0 : function->print (pp);
297 : 0 : }
298 : :
299 : : // Print a description of FUNCTION to FILE.
300 : : void
301 : 0 : dump (FILE *file, const function_info *function)
302 : : {
303 : 0 : dump_using (file, pp_function, function);
304 : 0 : }
305 : :
306 : : // Debug interface to the dump routine above.
307 : 0 : void debug (const function_info *x) { dump (stderr, x); }
|
