]>
Commit | Line | Data |
---|---|---|
73b75827 | 1 | // Implementation of function-related RTL SSA functions -*- C++ -*- |
7adcbafe | 2 | // Copyright (C) 2020-2022 Free Software Foundation, Inc. |
73b75827 RS |
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" | |
abe07a74 | 29 | #include "rtl-ssa/internals.h" |
73b75827 RS |
30 | #include "rtl-ssa/internals.inl" |
31 | ||
32 | using namespace rtl_ssa; | |
33 | ||
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 | ||
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 | ||
73b75827 RS |
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 (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; | |
73b75827 RS |
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 *> (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 | |
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 | |
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 | |
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, pp_function, function); | |
304 | } | |
305 | ||
306 | // Debug interface to the dump routine above. | |
307 | void debug (const function_info *x) { dump (stderr, x); } |