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