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 | function_info::function_info (function *fn) |
35 | : m_fn (fn), m_clobbered_by_calls () |
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 | |
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 |
66 | 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 |
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 (len: 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 |
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 *> (p: 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 (mode1: phi_mode, mode2: 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 |
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 (mode1: user_phi_mode, mode2: 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 |
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 (map: valid_phi_uids, bitno: phi->uid ()); |
257 | phis[phi->uid ()] = phi; |
258 | simplify_phi_setup (phi, assumed_values, worklist: 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 (map: 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 (phi: phis[uid], assumed_values, |
272 | curr_worklist, next_worklist); |
273 | } |
274 | while (!bitmap_empty_p (map: curr_worklist)); |
275 | std::swap (a&: next_worklist, b&: 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 (map: valid_phi_uids, bitno: i)) |
283 | if (auto *new_phi = safe_dyn_cast<phi_info *> (p: 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 (map: valid_phi_uids, bitno: 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 |
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 |
301 | dump (FILE *file, const function_info *function) |
302 | { |
303 | dump_using (file, printer: pp_function, args: function); |
304 | } |
305 | |
306 | // Debug interface to the dump routine above. |
307 | void debug (const function_info *x) { dump (stderr, function: x); } |
308 | |