1 | // Implementation of basic-block-related functions for RTL SSA -*- C++ -*- |
2 | // Copyright (C) 2020-2023 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 | #include "cfganal.h" |
32 | #include "cfgrtl.h" |
33 | #include "predict.h" |
34 | #include "domwalk.h" |
35 | |
36 | using namespace rtl_ssa; |
37 | |
38 | // Prepare to build information for a function in which all register numbers |
39 | // are less than NUM_REGS and all basic block indices are less than |
40 | // NUM_BB_INDICES |
41 | function_info::build_info::build_info (unsigned int num_regs, |
42 | unsigned int num_bb_indices) |
43 | : current_bb (nullptr), |
44 | current_ebb (nullptr), |
45 | last_access (num_regs + 1), |
46 | ebb_live_in_for_debug (nullptr), |
47 | potential_phi_regs (num_regs), |
48 | bb_phis (num_bb_indices), |
49 | bb_mem_live_out (num_bb_indices), |
50 | bb_to_rpo (num_bb_indices), |
51 | exit_block_dominator (nullptr) |
52 | { |
53 | last_access.safe_grow_cleared (len: num_regs + 1); |
54 | |
55 | bitmap_clear (potential_phi_regs); |
56 | |
57 | // These arrays shouldn't need to be initialized, since we'll always |
58 | // write to an entry before reading from it. But poison the contents |
59 | // when checking, just to make sure we don't accidentally use an |
60 | // uninitialized value. |
61 | bb_phis.quick_grow_cleared (len: num_bb_indices); |
62 | bb_mem_live_out.quick_grow (len: num_bb_indices); |
63 | bb_to_rpo.quick_grow (len: num_bb_indices); |
64 | if (flag_checking) |
65 | { |
66 | // Can't do this for bb_phis because it has a constructor. |
67 | memset (s: bb_mem_live_out.address (), c: 0xaf, |
68 | n: num_bb_indices * sizeof (bb_mem_live_out[0])); |
69 | memset (s: bb_to_rpo.address (), c: 0xaf, |
70 | n: num_bb_indices * sizeof (bb_to_rpo[0])); |
71 | } |
72 | |
73 | // Start off with an empty set of phi nodes for each block. |
74 | for (bb_phi_info &info : bb_phis) |
75 | bitmap_initialize (head: &info.regs, obstack: &bitmap_default_obstack); |
76 | } |
77 | |
78 | function_info::build_info::~build_info () |
79 | { |
80 | for (bb_phi_info &info : bb_phis) |
81 | bitmap_release (head: &info.regs); |
82 | } |
83 | |
84 | // A dom_walker for populating the basic blocks. |
85 | class function_info::bb_walker : public dom_walker |
86 | { |
87 | public: |
88 | bb_walker (function_info *, build_info &); |
89 | edge before_dom_children (basic_block) final override; |
90 | void after_dom_children (basic_block) final override; |
91 | |
92 | private: |
93 | // Information about the function we're building. |
94 | function_info *m_function; |
95 | build_info &m_bi; |
96 | |
97 | // We should treat the exit block as being the last child of this one. |
98 | // See the comment in the constructor for more information. |
99 | basic_block m_exit_block_dominator; |
100 | }; |
101 | |
102 | // Prepare to walk the blocks in FUNCTION using BI. |
103 | function_info::bb_walker::bb_walker (function_info *function, build_info &bi) |
104 | : dom_walker (CDI_DOMINATORS, ALL_BLOCKS, bi.bb_to_rpo.address ()), |
105 | m_function (function), |
106 | m_bi (bi), |
107 | m_exit_block_dominator (bi.exit_block_dominator) |
108 | { |
109 | // If the exit block is unreachable, process it last. |
110 | if (!m_exit_block_dominator) |
111 | m_exit_block_dominator = ENTRY_BLOCK_PTR_FOR_FN (m_function->m_fn); |
112 | } |
113 | |
114 | edge |
115 | function_info::bb_walker::before_dom_children (basic_block bb) |
116 | { |
117 | m_function->start_block (m_bi, m_function->bb (cfg_bb: bb)); |
118 | return nullptr; |
119 | } |
120 | |
121 | void |
122 | function_info::bb_walker::after_dom_children (basic_block bb) |
123 | { |
124 | // See the comment in the constructor for details. |
125 | if (bb == m_exit_block_dominator) |
126 | { |
127 | before_dom_children (EXIT_BLOCK_PTR_FOR_FN (m_function->m_fn)); |
128 | after_dom_children (EXIT_BLOCK_PTR_FOR_FN (m_function->m_fn)); |
129 | } |
130 | m_function->end_block (m_bi, m_function->bb (cfg_bb: bb)); |
131 | } |
132 | |
133 | // See the comment above the declaration. |
134 | void |
135 | bb_info::print_identifier (pretty_printer *pp) const |
136 | { |
137 | char tmp[3 * sizeof (index ()) + 3]; |
138 | snprintf (s: tmp, maxlen: sizeof (tmp), format: "bb%d" , index ()); |
139 | pp_string (pp, tmp); |
140 | if (ebb_info *ebb = this->ebb ()) |
141 | { |
142 | pp_space (pp); |
143 | pp_left_bracket (pp); |
144 | ebb->print_identifier (pp); |
145 | pp_right_bracket (pp); |
146 | } |
147 | } |
148 | |
149 | // See the comment above the declaration. |
150 | void |
151 | bb_info::print_full (pretty_printer *pp) const |
152 | { |
153 | pp_string (pp, "basic block " ); |
154 | print_identifier (pp); |
155 | pp_colon (pp); |
156 | |
157 | auto print_insn = [pp](const char *, const insn_info *insn) |
158 | { |
159 | pp_newline_and_indent (pp, 2); |
160 | pp_string (pp, header); |
161 | pp_newline_and_indent (pp, 2); |
162 | if (insn) |
163 | pp_insn (pp, insn); |
164 | else |
165 | pp_string (pp, "<uninitialized>" ); |
166 | pp_indentation (pp) -= 4; |
167 | }; |
168 | |
169 | print_insn ("head:" , head_insn ()); |
170 | |
171 | pp_newline (pp); |
172 | pp_newline_and_indent (pp, 2); |
173 | pp_string (pp, "contents:" ); |
174 | if (!head_insn ()) |
175 | { |
176 | pp_newline_and_indent (pp, 2); |
177 | pp_string (pp, "<uninitialized>" ); |
178 | pp_indentation (pp) -= 2; |
179 | } |
180 | else if (auto insns = real_insns ()) |
181 | { |
182 | bool is_first = true; |
183 | for (const insn_info *insn : insns) |
184 | { |
185 | if (is_first) |
186 | is_first = false; |
187 | else |
188 | pp_newline (pp); |
189 | pp_newline_and_indent (pp, 2); |
190 | pp_insn (pp, insn); |
191 | pp_indentation (pp) -= 2; |
192 | } |
193 | } |
194 | else |
195 | { |
196 | pp_newline_and_indent (pp, 2); |
197 | pp_string (pp, "none" ); |
198 | pp_indentation (pp) -= 2; |
199 | } |
200 | pp_indentation (pp) -= 2; |
201 | |
202 | pp_newline (pp); |
203 | print_insn ("end:" , end_insn ()); |
204 | } |
205 | |
206 | // See the comment above the declaration. |
207 | void |
208 | ebb_call_clobbers_info::print_summary (pretty_printer *pp) const |
209 | { |
210 | pp_string (pp, "call clobbers for ABI " ); |
211 | if (m_abi) |
212 | pp_decimal_int (pp, m_abi->id ()); |
213 | else |
214 | pp_string (pp, "<null>" ); |
215 | } |
216 | |
217 | // See the comment above the declaration. |
218 | void |
219 | ebb_call_clobbers_info::print_full (pretty_printer *pp) const |
220 | { |
221 | print_summary (pp); |
222 | pp_colon (pp); |
223 | pp_newline_and_indent (pp, 2); |
224 | auto print_node = [](pretty_printer *pp, |
225 | const insn_call_clobbers_note *note) |
226 | { |
227 | if (insn_info *insn = note->insn ()) |
228 | insn->print_identifier_and_location (pp); |
229 | else |
230 | pp_string (pp, "<null>" ); |
231 | }; |
232 | print (pp, node: root (), printer: print_node); |
233 | pp_indentation (pp) -= 2; |
234 | } |
235 | |
236 | // See the comment above the declaration. |
237 | void |
238 | ebb_info::print_identifier (pretty_printer *pp) const |
239 | { |
240 | // first_bb is populated by the constructor and so should always |
241 | // be nonnull. |
242 | auto index = first_bb ()->index (); |
243 | char tmp[3 * sizeof (index) + 4]; |
244 | snprintf (s: tmp, maxlen: sizeof (tmp), format: "ebb%d" , index); |
245 | pp_string (pp, tmp); |
246 | } |
247 | |
248 | // See the comment above the declaration. |
249 | void |
250 | ebb_info::print_full (pretty_printer *pp) const |
251 | { |
252 | pp_string (pp, "extended basic block " ); |
253 | print_identifier (pp); |
254 | pp_colon (pp); |
255 | |
256 | pp_newline_and_indent (pp, 2); |
257 | if (insn_info *phi_insn = this->phi_insn ()) |
258 | { |
259 | phi_insn->print_identifier_and_location (pp); |
260 | pp_colon (pp); |
261 | if (auto phis = this->phis ()) |
262 | { |
263 | bool is_first = true; |
264 | for (const phi_info *phi : phis) |
265 | { |
266 | if (is_first) |
267 | is_first = false; |
268 | else |
269 | pp_newline (pp); |
270 | pp_newline_and_indent (pp, 2); |
271 | pp_access (pp, phi, flags: PP_ACCESS_SETTER); |
272 | pp_indentation (pp) -= 2; |
273 | } |
274 | } |
275 | else |
276 | { |
277 | pp_newline_and_indent (pp, 2); |
278 | pp_string (pp, "no phi nodes" ); |
279 | pp_indentation (pp) -= 2; |
280 | } |
281 | } |
282 | else |
283 | pp_string (pp, "no phi insn" ); |
284 | pp_indentation (pp) -= 2; |
285 | |
286 | for (const bb_info *bb : bbs ()) |
287 | { |
288 | pp_newline (pp); |
289 | pp_newline_and_indent (pp, 2); |
290 | pp_bb (pp, bb); |
291 | pp_indentation (pp) -= 2; |
292 | } |
293 | |
294 | for (ebb_call_clobbers_info *ecc : call_clobbers ()) |
295 | { |
296 | pp_newline (pp); |
297 | pp_newline_and_indent (pp, 2); |
298 | pp_ebb_call_clobbers (pp, ecc); |
299 | pp_indentation (pp) -= 2; |
300 | } |
301 | } |
302 | |
303 | // Add a dummy use to mark that DEF is live out of BB's EBB at the end of BB. |
304 | void |
305 | function_info::add_live_out_use (bb_info *bb, set_info *def) |
306 | { |
307 | // There is nothing to do if DEF is an artificial definition at the end |
308 | // of BB. In that case the definitino is rooted at the end of the block |
309 | // and we wouldn't gain anything by inserting a use immediately after it. |
310 | // If we did want to insert a use, we'd need to associate it with a new |
311 | // instruction that comes after bb->end_insn (). |
312 | if (def->insn () == bb->end_insn ()) |
313 | return; |
314 | |
315 | // If the end of the block already has an artificial use, that use |
316 | // acts to make DEF live at the appropriate point. |
317 | use_info *use = def->last_nondebug_insn_use (); |
318 | if (use && use->insn () == bb->end_insn ()) |
319 | return; |
320 | |
321 | // Currently there is no need to maintain a backward link from the end |
322 | // instruction to the list of live-out uses. Such a list would be |
323 | // expensive to update if it was represented using the usual insn_info |
324 | // access arrays. |
325 | use = allocate<use_info> (args: bb->end_insn (), args: def->resource (), args: def); |
326 | use->set_is_live_out_use (true); |
327 | add_use (use); |
328 | } |
329 | |
330 | // Return true if all nondebug uses of DEF are live-out uses. |
331 | static bool |
332 | all_uses_are_live_out_uses (set_info *def) |
333 | { |
334 | for (use_info *use : def->all_uses ()) |
335 | if (!use->is_in_debug_insn () && !use->is_live_out_use ()) |
336 | return false; |
337 | return true; |
338 | } |
339 | |
340 | // SET, if nonnull, is a definition of something that is live out from BB. |
341 | // Return the live-out value itself. |
342 | set_info * |
343 | function_info::live_out_value (bb_info *bb, set_info *set) |
344 | { |
345 | // Degenerate phis only exist to provide a definition for uses in the |
346 | // same EBB. The live-out value is the same as the live-in value. |
347 | if (auto *phi = safe_dyn_cast<phi_info *> (p: set)) |
348 | if (phi->is_degenerate ()) |
349 | { |
350 | set = phi->input_value (i: 0); |
351 | |
352 | // Remove the phi if it turned out to be useless. This is |
353 | // mainly useful for memory, because we don't know ahead of time |
354 | // whether a block will use memory or not. |
355 | if (bb == bb->ebb ()->last_bb () && all_uses_are_live_out_uses (def: phi)) |
356 | replace_phi (phi, set); |
357 | } |
358 | |
359 | return set; |
360 | } |
361 | |
362 | // Add PHI to EBB and enter it into the function's hash table. |
363 | void |
364 | function_info::append_phi (ebb_info *ebb, phi_info *phi) |
365 | { |
366 | phi_info *first_phi = ebb->first_phi (); |
367 | if (first_phi) |
368 | first_phi->set_prev_phi (phi); |
369 | phi->set_next_phi (first_phi); |
370 | ebb->set_first_phi (phi); |
371 | add_def (phi); |
372 | } |
373 | |
374 | // Remove PHI from its current position in the SSA graph. |
375 | void |
376 | function_info::remove_phi (phi_info *phi) |
377 | { |
378 | phi_info *next = phi->next_phi (); |
379 | phi_info *prev = phi->prev_phi (); |
380 | |
381 | if (next) |
382 | next->set_prev_phi (prev); |
383 | |
384 | if (prev) |
385 | prev->set_next_phi (next); |
386 | else |
387 | phi->ebb ()->set_first_phi (next); |
388 | |
389 | remove_def (phi); |
390 | phi->clear_phi_links (); |
391 | } |
392 | |
393 | // Remove PHI from the SSA graph and free its memory. |
394 | void |
395 | function_info::delete_phi (phi_info *phi) |
396 | { |
397 | gcc_assert (!phi->has_any_uses ()); |
398 | |
399 | // Remove the inputs to the phi. |
400 | for (use_info *input : phi->inputs ()) |
401 | remove_use (input); |
402 | |
403 | remove_phi (phi); |
404 | |
405 | phi->set_next_phi (m_free_phis); |
406 | m_free_phis = phi; |
407 | } |
408 | |
409 | // If possible, remove PHI and replace all uses with NEW_VALUE. |
410 | void |
411 | function_info::replace_phi (phi_info *phi, set_info *new_value) |
412 | { |
413 | auto update_use = [&](use_info *use) |
414 | { |
415 | remove_use (use); |
416 | use->set_def (new_value); |
417 | add_use (use); |
418 | }; |
419 | |
420 | if (new_value) |
421 | for (use_info *use : phi->nondebug_insn_uses ()) |
422 | if (!use->is_live_out_use ()) |
423 | { |
424 | // We need to keep the phi around for its local uses. |
425 | // Turn it into a degenerate phi, if it isn't already. |
426 | use_info *use = phi->input_use (i: 0); |
427 | if (use->def () != new_value) |
428 | update_use (use); |
429 | |
430 | if (phi->is_degenerate ()) |
431 | return; |
432 | |
433 | phi->make_degenerate (input: use); |
434 | |
435 | // Redirect all phi users to NEW_VALUE. |
436 | while (use_info *phi_use = phi->last_phi_use ()) |
437 | update_use (phi_use); |
438 | |
439 | return; |
440 | } |
441 | |
442 | // Replace the uses. We can discard uses that only existed for the |
443 | // sake of marking live-out values, since the resource is now transparent |
444 | // in the phi's EBB. |
445 | while (use_info *use = phi->last_use ()) |
446 | if (use->is_live_out_use ()) |
447 | remove_use (use); |
448 | else |
449 | update_use (use); |
450 | |
451 | delete_phi (phi); |
452 | } |
453 | |
454 | // Create and return a phi node for EBB. RESOURCE is the resource that |
455 | // the phi node sets (and thus that all the inputs set too). NUM_INPUTS |
456 | // is the number of inputs, which is 1 for a degenerate phi. INPUTS[I] |
457 | // is a set_info that gives the value of input I, or null if the value |
458 | // is either unknown or uninitialized. If NUM_INPUTS > 1, this array |
459 | // is allocated on the main obstack and can be reused for the use array. |
460 | // |
461 | // Add the created phi node to its basic block and enter it into the |
462 | // function's hash table. |
463 | phi_info * |
464 | function_info::create_phi (ebb_info *ebb, resource_info resource, |
465 | access_info **inputs, unsigned int num_inputs) |
466 | { |
467 | phi_info *phi = m_free_phis; |
468 | if (phi) |
469 | { |
470 | m_free_phis = phi->next_phi (); |
471 | *phi = phi_info (ebb->phi_insn (), resource, phi->uid ()); |
472 | } |
473 | else |
474 | { |
475 | phi = allocate<phi_info> (args: ebb->phi_insn (), args: resource, args: m_next_phi_uid); |
476 | m_next_phi_uid += 1; |
477 | } |
478 | |
479 | // Convert the array of set_infos into an array of use_infos. Also work |
480 | // out what mode the phi should have. |
481 | machine_mode new_mode = resource.mode; |
482 | for (unsigned int i = 0; i < num_inputs; ++i) |
483 | { |
484 | auto *input = safe_as_a<set_info *> (p: inputs[i]); |
485 | auto *use = allocate<use_info> (args: phi, args: resource, args: input); |
486 | add_use (use); |
487 | inputs[i] = use; |
488 | if (input) |
489 | new_mode = combine_modes (mode1: new_mode, mode2: input->mode ()); |
490 | } |
491 | |
492 | phi->set_inputs (use_array (inputs, num_inputs)); |
493 | phi->set_mode (new_mode); |
494 | |
495 | append_phi (ebb, phi); |
496 | |
497 | return phi; |
498 | } |
499 | |
500 | // Create and return a degenerate phi for EBB whose input comes from DEF. |
501 | // This is used in cases where DEF is known to be available on entry to |
502 | // EBB but was not previously used within it. If DEF is for a register, |
503 | // there are two cases: |
504 | // |
505 | // (1) DEF was already live on entry to EBB but was previously transparent |
506 | // within it. |
507 | // |
508 | // (2) DEF was not previously live on entry to EBB and is being made live |
509 | // by this update. |
510 | // |
511 | // At the moment, this function only handles the case in which EBB has a |
512 | // single predecessor block and DEF is defined in that block's EBB. |
513 | phi_info * |
514 | function_info::create_degenerate_phi (ebb_info *ebb, set_info *def) |
515 | { |
516 | // Allow the function to be called twice in succession for the same def. |
517 | def_lookup dl = find_def (resource: def->resource (), insn: ebb->phi_insn ()); |
518 | if (set_info *set = dl.matching_set ()) |
519 | return as_a<phi_info *> (p: set); |
520 | |
521 | access_info *input = def; |
522 | phi_info *phi = create_phi (ebb, resource: def->resource (), inputs: &input, num_inputs: 1); |
523 | if (def->is_reg ()) |
524 | { |
525 | unsigned int regno = def->regno (); |
526 | |
527 | // Find the single predecessor mentioned above. |
528 | basic_block pred_cfg_bb = single_pred (bb: ebb->first_bb ()->cfg_bb ()); |
529 | bb_info *pred_bb = this->bb (cfg_bb: pred_cfg_bb); |
530 | |
531 | if (!bitmap_set_bit (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno)) |
532 | { |
533 | // The register was not previously live on entry to EBB and |
534 | // might not have been live on exit from PRED_BB either. |
535 | if (bitmap_set_bit (DF_LR_OUT (pred_cfg_bb), regno)) |
536 | add_live_out_use (bb: pred_bb, def); |
537 | } |
538 | else |
539 | { |
540 | // The register was previously live in to EBB. Add live-out uses |
541 | // at the appropriate points. |
542 | insn_info *next_insn = nullptr; |
543 | if (def_info *next_def = phi->next_def ()) |
544 | next_insn = next_def->insn (); |
545 | for (bb_info *bb : ebb->bbs ()) |
546 | { |
547 | if ((next_insn && *next_insn <= *bb->end_insn ()) |
548 | || !bitmap_bit_p (DF_LR_OUT (bb->cfg_bb ()), regno)) |
549 | break; |
550 | add_live_out_use (bb, def); |
551 | } |
552 | } |
553 | } |
554 | return phi; |
555 | } |
556 | |
557 | // Create a bb_info for CFG_BB, given that no such structure currently exists. |
558 | bb_info * |
559 | function_info::create_bb_info (basic_block cfg_bb) |
560 | { |
561 | bb_info *bb = allocate<bb_info> (args: cfg_bb); |
562 | gcc_checking_assert (!m_bbs[cfg_bb->index]); |
563 | m_bbs[cfg_bb->index] = bb; |
564 | return bb; |
565 | } |
566 | |
567 | // Add BB to the end of the list of blocks. |
568 | void |
569 | function_info::append_bb (bb_info *bb) |
570 | { |
571 | if (m_last_bb) |
572 | m_last_bb->set_next_bb (bb); |
573 | else |
574 | m_first_bb = bb; |
575 | bb->set_prev_bb (m_last_bb); |
576 | m_last_bb = bb; |
577 | } |
578 | |
579 | // Calculate BI.potential_phi_regs and BI.potential_phi_regs_for_debug. |
580 | void |
581 | function_info::calculate_potential_phi_regs (build_info &bi) |
582 | { |
583 | auto *lr_info = DF_LR_BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (m_fn)); |
584 | bool is_debug = MAY_HAVE_DEBUG_INSNS; |
585 | for (unsigned int regno = 0; regno < m_num_regs; ++regno) |
586 | if (regno >= DF_REG_SIZE (DF) |
587 | // Exclude registers that have a single definition that dominates |
588 | // all uses. If the definition does not dominate all uses, |
589 | // the register will be exposed upwards to the entry block but |
590 | // will not be defined by the entry block. |
591 | || DF_REG_DEF_COUNT (regno) > 1 |
592 | || (!bitmap_bit_p (&lr_info->def, regno) |
593 | && bitmap_bit_p (&lr_info->out, regno))) |
594 | { |
595 | bitmap_set_bit (map: bi.potential_phi_regs, bitno: regno); |
596 | if (is_debug) |
597 | bitmap_set_bit (bi.potential_phi_regs_for_debug, regno); |
598 | } |
599 | } |
600 | |
601 | // Called while building SSA form using BI. Decide where phi nodes |
602 | // should be placed for each register and initialize BI.bb_phis accordingly. |
603 | void |
604 | function_info::place_phis (build_info &bi) |
605 | { |
606 | unsigned int num_bb_indices = last_basic_block_for_fn (m_fn); |
607 | |
608 | // Calculate dominance frontiers. |
609 | auto_vec<bitmap_head> frontiers; |
610 | frontiers.safe_grow_cleared (len: num_bb_indices); |
611 | for (unsigned int i = 0; i < num_bb_indices; ++i) |
612 | bitmap_initialize (head: &frontiers[i], obstack: &bitmap_default_obstack); |
613 | compute_dominance_frontiers (frontiers.address ()); |
614 | |
615 | // The normal dominance information doesn't calculate dominators for |
616 | // the exit block, so we don't get dominance frontiers for them either. |
617 | // Calculate them by hand. |
618 | for (edge e : EXIT_BLOCK_PTR_FOR_FN (m_fn)->preds) |
619 | { |
620 | basic_block bb = e->src; |
621 | while (bb != bi.exit_block_dominator) |
622 | { |
623 | bitmap_set_bit (&frontiers[bb->index], EXIT_BLOCK); |
624 | bb = get_immediate_dominator (CDI_DOMINATORS, bb); |
625 | } |
626 | } |
627 | |
628 | // In extreme cases, the number of live-in registers can be much |
629 | // greater than the number of phi nodes needed in a block (see PR98863). |
630 | // Try to reduce the number of operations involving live-in sets by using |
631 | // PENDING as a staging area: registers in PENDING need phi nodes if |
632 | // they are live on entry to the corresponding block, but do not need |
633 | // phi nodes otherwise. |
634 | auto_vec<bitmap_head> unfiltered; |
635 | unfiltered.safe_grow_cleared (len: num_bb_indices); |
636 | for (unsigned int i = 0; i < num_bb_indices; ++i) |
637 | bitmap_initialize (head: &unfiltered[i], obstack: &bitmap_default_obstack); |
638 | |
639 | // If block B1 defines R and if B2 is in the dominance frontier of B1, |
640 | // queue a possible phi node for R in B2. |
641 | auto_bitmap worklist; |
642 | for (unsigned int b1 = 0; b1 < num_bb_indices; ++b1) |
643 | { |
644 | // Only access DF information for blocks that are known to exist. |
645 | if (bitmap_empty_p (map: &frontiers[b1])) |
646 | continue; |
647 | |
648 | bitmap b1_def = &DF_LR_BB_INFO (BASIC_BLOCK_FOR_FN (m_fn, b1))->def; |
649 | bitmap_iterator bmi; |
650 | unsigned int b2; |
651 | EXECUTE_IF_SET_IN_BITMAP (&frontiers[b1], 0, b2, bmi) |
652 | if (bitmap_ior_into (&unfiltered[b2], b1_def) |
653 | && !bitmap_empty_p (map: &frontiers[b2])) |
654 | // Propagate the (potential) new phi node definitions in B2. |
655 | bitmap_set_bit (worklist, b2); |
656 | } |
657 | |
658 | while (!bitmap_empty_p (map: worklist)) |
659 | { |
660 | unsigned int b1 = bitmap_first_set_bit (worklist); |
661 | bitmap_clear_bit (worklist, b1); |
662 | |
663 | // Restrict the phi nodes to registers that are live on entry to |
664 | // the block. |
665 | bitmap b1_in = DF_LR_IN (BASIC_BLOCK_FOR_FN (m_fn, b1)); |
666 | bitmap b1_phis = &bi.bb_phis[b1].regs; |
667 | if (!bitmap_ior_and_into (DST: b1_phis, B: &unfiltered[b1], C: b1_in)) |
668 | continue; |
669 | |
670 | // If block B1 has a phi node for R and if B2 is in the dominance |
671 | // frontier of B1, queue a possible phi node for R in B2. |
672 | bitmap_iterator bmi; |
673 | unsigned int b2; |
674 | EXECUTE_IF_SET_IN_BITMAP (&frontiers[b1], 0, b2, bmi) |
675 | if (bitmap_ior_into (&unfiltered[b2], b1_phis) |
676 | && !bitmap_empty_p (map: &frontiers[b2])) |
677 | bitmap_set_bit (worklist, b2); |
678 | } |
679 | |
680 | basic_block cfg_bb; |
681 | FOR_ALL_BB_FN (cfg_bb, m_fn) |
682 | { |
683 | // Calculate the set of phi nodes for blocks that don't have any |
684 | // dominance frontiers. We only need to do this once per block. |
685 | unsigned int i = cfg_bb->index; |
686 | bb_phi_info &phis = bi.bb_phis[i]; |
687 | if (bitmap_empty_p (map: &frontiers[i])) |
688 | bitmap_and (&phis.regs, &unfiltered[i], DF_LR_IN (cfg_bb)); |
689 | |
690 | // Create an array that contains all phi inputs for this block. |
691 | // See the comment above the member variables for more information. |
692 | phis.num_phis = bitmap_count_bits (&phis.regs); |
693 | phis.num_preds = EDGE_COUNT (cfg_bb->preds); |
694 | unsigned int num_inputs = phis.num_phis * phis.num_preds; |
695 | if (num_inputs != 0) |
696 | { |
697 | phis.inputs = XOBNEWVEC (&m_temp_obstack, set_info *, num_inputs); |
698 | memset (s: phis.inputs, c: 0, n: num_inputs * sizeof (phis.inputs[0])); |
699 | } |
700 | } |
701 | |
702 | // Free the temporary bitmaps. |
703 | for (unsigned int i = 0; i < num_bb_indices; ++i) |
704 | { |
705 | bitmap_release (head: &frontiers[i]); |
706 | bitmap_release (head: &unfiltered[i]); |
707 | } |
708 | } |
709 | |
710 | // Called while building SSA form using BI, with BI.current_bb being |
711 | // the entry block. |
712 | // |
713 | // Create the entry block instructions and their definitions. The only |
714 | // useful instruction is the end instruction, which carries definitions |
715 | // for the values that are live on entry to the function. However, it |
716 | // seems simpler to create a head instruction too, rather than force all |
717 | // users of the block information to treat the entry block as a special case. |
718 | void |
719 | function_info::add_entry_block_defs (build_info &bi) |
720 | { |
721 | bb_info *bb = bi.current_bb; |
722 | basic_block cfg_bb = bi.current_bb->cfg_bb (); |
723 | auto *lr_info = DF_LR_BB_INFO (cfg_bb); |
724 | |
725 | bb->set_head_insn (append_artificial_insn (bb)); |
726 | insn_info *insn = append_artificial_insn (bb); |
727 | bb->set_end_insn (insn); |
728 | |
729 | start_insn_accesses (); |
730 | |
731 | // Using LR to derive the liveness information means that we create an |
732 | // entry block definition for upwards exposed registers. These registers |
733 | // are sometimes genuinely uninitialized. However, some targets also |
734 | // create a pseudo PIC base register and only initialize it later. |
735 | // Handling that case correctly seems more important than optimizing |
736 | // uninitialized uses. |
737 | unsigned int regno; |
738 | bitmap_iterator in_bi; |
739 | EXECUTE_IF_SET_IN_BITMAP (&lr_info->out, 0, regno, in_bi) |
740 | { |
741 | auto *set = allocate<set_info> (args: insn, args: full_register (regno)); |
742 | append_def (set); |
743 | m_temp_defs.safe_push (obj: set); |
744 | bi.record_reg_def (def: set); |
745 | } |
746 | |
747 | // Create a definition that reflects the state of memory on entry to |
748 | // the function. |
749 | auto *set = allocate<set_info> (args: insn, args: memory); |
750 | append_def (set); |
751 | m_temp_defs.safe_push (obj: set); |
752 | bi.record_mem_def (def: set); |
753 | |
754 | finish_insn_accesses (insn); |
755 | } |
756 | |
757 | // Lazily calculate the value of BI.ebb_live_in_for_debug for BI.current_ebb. |
758 | void |
759 | function_info::calculate_ebb_live_in_for_debug (build_info &bi) |
760 | { |
761 | gcc_checking_assert (bitmap_empty_p (bi.tmp_ebb_live_in_for_debug)); |
762 | bi.ebb_live_in_for_debug = bi.tmp_ebb_live_in_for_debug; |
763 | bitmap_and (bi.ebb_live_in_for_debug, bi.potential_phi_regs_for_debug, |
764 | DF_LR_IN (bi.current_ebb->first_bb ()->cfg_bb ())); |
765 | bitmap_tree_view (bi.ebb_live_in_for_debug); |
766 | } |
767 | |
768 | // Called while building SSA form using BI. Create phi nodes for the |
769 | // current EBB. |
770 | void |
771 | function_info::add_phi_nodes (build_info &bi) |
772 | { |
773 | ebb_info *ebb = bi.current_ebb; |
774 | basic_block cfg_bb = ebb->first_bb ()->cfg_bb (); |
775 | |
776 | // Create the register phis for this EBB. |
777 | bb_phi_info &phis = bi.bb_phis[cfg_bb->index]; |
778 | unsigned int num_preds = phis.num_preds; |
779 | unsigned int regno; |
780 | bitmap_iterator in_bi; |
781 | EXECUTE_IF_SET_IN_BITMAP (&phis.regs, 0, regno, in_bi) |
782 | { |
783 | gcc_checking_assert (bitmap_bit_p (bi.potential_phi_regs, regno)); |
784 | |
785 | // Create an array of phi inputs, to be filled in later. |
786 | auto *inputs = XOBNEWVEC (&m_obstack, access_info *, num_preds); |
787 | memset (s: inputs, c: 0, n: sizeof (access_info *) * num_preds); |
788 | |
789 | // Later code works out the correct mode of the phi. Use BLKmode |
790 | // as a placeholder for now. |
791 | phi_info *phi = create_phi (ebb, resource: { .mode: E_BLKmode, .regno: regno }, |
792 | inputs, num_inputs: num_preds); |
793 | bi.record_reg_def (def: phi); |
794 | } |
795 | |
796 | bitmap_copy (bi.ebb_def_regs, &phis.regs); |
797 | |
798 | // Collect the live-in memory definitions and record whether they're |
799 | // all the same. |
800 | m_temp_defs.reserve (nelems: num_preds); |
801 | set_info *mem_value = nullptr; |
802 | bool mem_phi_is_degenerate = true; |
803 | edge e; |
804 | edge_iterator ei; |
805 | FOR_EACH_EDGE (e, ei, cfg_bb->preds) |
806 | { |
807 | bb_info *pred_bb = this->bb (cfg_bb: e->src); |
808 | if (pred_bb && pred_bb->head_insn ()) |
809 | { |
810 | mem_value = bi.bb_mem_live_out[pred_bb->index ()]; |
811 | m_temp_defs.quick_push (obj: mem_value); |
812 | if (mem_value != m_temp_defs[0]) |
813 | mem_phi_is_degenerate = false; |
814 | } |
815 | else |
816 | { |
817 | m_temp_defs.quick_push (obj: nullptr); |
818 | mem_phi_is_degenerate = false; |
819 | } |
820 | } |
821 | |
822 | // Create a phi for memory, on the assumption that something in the |
823 | // EBB will need it. |
824 | if (mem_phi_is_degenerate) |
825 | { |
826 | access_info *input[] = { mem_value }; |
827 | mem_value = create_phi (ebb, resource: memory, inputs: input, num_inputs: 1); |
828 | } |
829 | else |
830 | { |
831 | obstack_grow (&m_obstack, m_temp_defs.address (), |
832 | num_preds * sizeof (access_info *)); |
833 | auto *inputs = static_cast<access_info **> (obstack_finish (&m_obstack)); |
834 | mem_value = create_phi (ebb, resource: memory, inputs, num_inputs: num_preds); |
835 | } |
836 | bi.record_mem_def (def: mem_value); |
837 | m_temp_defs.truncate (size: 0); |
838 | } |
839 | |
840 | // Called while building SSA form using BI. |
841 | // |
842 | // If FLAGS is DF_REF_AT_TOP, create the head insn for BI.current_bb |
843 | // and populate its uses and definitions. If FLAGS is 0, do the same |
844 | // for the end insn. |
845 | void |
846 | function_info::add_artificial_accesses (build_info &bi, df_ref_flags flags) |
847 | { |
848 | bb_info *bb = bi.current_bb; |
849 | basic_block cfg_bb = bb->cfg_bb (); |
850 | auto *lr_info = DF_LR_BB_INFO (cfg_bb); |
851 | df_ref ref; |
852 | |
853 | insn_info *insn; |
854 | if (flags == DF_REF_AT_TOP) |
855 | { |
856 | if (cfg_bb->index == EXIT_BLOCK) |
857 | insn = append_artificial_insn (bb); |
858 | else |
859 | insn = append_artificial_insn (bb, bb_note (cfg_bb)); |
860 | bb->set_head_insn (insn); |
861 | } |
862 | else |
863 | { |
864 | insn = append_artificial_insn (bb); |
865 | bb->set_end_insn (insn); |
866 | } |
867 | |
868 | start_insn_accesses (); |
869 | |
870 | HARD_REG_SET added_regs = {}; |
871 | FOR_EACH_ARTIFICIAL_USE (ref, cfg_bb->index) |
872 | if ((DF_REF_FLAGS (ref) & DF_REF_AT_TOP) == flags) |
873 | { |
874 | unsigned int regno = DF_REF_REGNO (ref); |
875 | machine_mode mode = GET_MODE (DF_REF_REAL_REG (ref)); |
876 | if (HARD_REGISTER_NUM_P (regno)) |
877 | SET_HARD_REG_BIT (set&: added_regs, bit: regno); |
878 | |
879 | // A definition must be available. |
880 | gcc_checking_assert (bitmap_bit_p (&lr_info->in, regno) |
881 | || (flags != DF_REF_AT_TOP |
882 | && bitmap_bit_p (&lr_info->def, regno))); |
883 | m_temp_uses.safe_push (obj: create_reg_use (bi, insn, { .mode: mode, .regno: regno })); |
884 | } |
885 | |
886 | // Ensure that global registers and memory are live at the end of any |
887 | // block that has no successors, such as the exit block and non-local gotos. |
888 | // Global registers have to be singled out because they are not part of |
889 | // the DF artifical use list (they are instead treated as used within |
890 | // every block). |
891 | if (flags == 0 && EDGE_COUNT (cfg_bb->succs) == 0) |
892 | { |
893 | for (unsigned int i = 0; i < FIRST_PSEUDO_REGISTER; ++i) |
894 | if (global_regs[i] && !TEST_HARD_REG_BIT (set: added_regs, bit: i)) |
895 | { |
896 | auto mode = reg_raw_mode[i]; |
897 | m_temp_uses.safe_push (obj: create_reg_use (bi, insn, { .mode: mode, .regno: i })); |
898 | } |
899 | |
900 | auto *use = allocate<use_info> (args: insn, args: memory, args: bi.current_mem_value ()); |
901 | add_use (use); |
902 | m_temp_uses.safe_push (obj: use); |
903 | } |
904 | |
905 | FOR_EACH_ARTIFICIAL_DEF (ref, cfg_bb->index) |
906 | if ((DF_REF_FLAGS (ref) & DF_REF_AT_TOP) == flags) |
907 | { |
908 | unsigned int regno = DF_REF_REGNO (ref); |
909 | machine_mode mode = GET_MODE (DF_REF_REAL_REG (ref)); |
910 | resource_info resource { .mode: mode, .regno: regno }; |
911 | |
912 | // We rely on the def set being correct. |
913 | gcc_checking_assert (bitmap_bit_p (&lr_info->def, regno)); |
914 | |
915 | // If the value isn't used later in the block and isn't live |
916 | // on exit, we could instead represent the definition as a |
917 | // clobber_info. However, that case should be relatively |
918 | // rare and set_info is any case more compact than clobber_info. |
919 | set_info *def = allocate<set_info> (args: insn, args: resource); |
920 | append_def (def); |
921 | m_temp_defs.safe_push (obj: def); |
922 | bi.record_reg_def (def); |
923 | } |
924 | |
925 | // Model the effect of a memory clobber on an incoming edge by adding |
926 | // a fake definition of memory at the start of the block. We don't need |
927 | // to add a use of the phi node because memory is implicitly always live. |
928 | if (flags == DF_REF_AT_TOP && has_abnormal_call_or_eh_pred_edge_p (bb: cfg_bb)) |
929 | { |
930 | set_info *def = allocate<set_info> (args: insn, args: memory); |
931 | append_def (def); |
932 | m_temp_defs.safe_push (obj: def); |
933 | bi.record_mem_def (def); |
934 | } |
935 | |
936 | finish_insn_accesses (insn); |
937 | } |
938 | |
939 | // Called while building SSA form using BI. Create insn_infos for all |
940 | // relevant instructions in BI.current_bb. |
941 | void |
942 | function_info::add_block_contents (build_info &bi) |
943 | { |
944 | basic_block cfg_bb = bi.current_bb->cfg_bb (); |
945 | rtx_insn *insn; |
946 | FOR_BB_INSNS (cfg_bb, insn) |
947 | if (INSN_P (insn)) |
948 | add_insn_to_block (bi, insn); |
949 | } |
950 | |
951 | // Called while building SSA form using BI. Record live-out register values |
952 | // in the phi inputs of successor blocks and create live-out uses where |
953 | // appropriate. Record the live-out memory value in BI.bb_mem_live_out. |
954 | void |
955 | function_info::record_block_live_out (build_info &bi) |
956 | { |
957 | bb_info *bb = bi.current_bb; |
958 | ebb_info *ebb = bi.current_ebb; |
959 | basic_block cfg_bb = bb->cfg_bb (); |
960 | |
961 | // Record the live-out register values in the phi inputs of |
962 | // successor blocks. |
963 | edge e; |
964 | edge_iterator ei; |
965 | FOR_EACH_EDGE (e, ei, cfg_bb->succs) |
966 | { |
967 | bb_phi_info &phis = bi.bb_phis[e->dest->index]; |
968 | unsigned int input_i = e->dest_idx * phis.num_phis; |
969 | unsigned int regno; |
970 | bitmap_iterator out_bi; |
971 | EXECUTE_IF_SET_IN_BITMAP (&phis.regs, 0, regno, out_bi) |
972 | { |
973 | phis.inputs[input_i] |
974 | = live_out_value (bb, set: bi.current_reg_value (regno)); |
975 | input_i += 1; |
976 | } |
977 | } |
978 | |
979 | // Add the set of registers that were defined in this BB to the set |
980 | // of potentially-live registers defined in the EBB. |
981 | bitmap_ior_into (bi.ebb_def_regs, &DF_LR_BB_INFO (cfg_bb)->def); |
982 | |
983 | // Iterate through the registers in LIVE_OUT and see whether we need |
984 | // to add a live-out use for them. |
985 | auto record_live_out_regs = [&](bitmap live_out) |
986 | { |
987 | unsigned int regno; |
988 | bitmap_iterator out_bi; |
989 | EXECUTE_IF_AND_IN_BITMAP (bi.ebb_def_regs, live_out, 0, regno, out_bi) |
990 | { |
991 | set_info *value = live_out_value (bb, set: bi.current_reg_value (regno)); |
992 | if (value && value->ebb () == ebb) |
993 | add_live_out_use (bb, def: value); |
994 | } |
995 | }; |
996 | |
997 | if (bb == ebb->last_bb ()) |
998 | // All live-out registers might need live-out uses. |
999 | record_live_out_regs (DF_LR_OUT (cfg_bb)); |
1000 | else |
1001 | // Registers might need live-out uses if they are live on entry |
1002 | // to a successor block in a different EBB. |
1003 | FOR_EACH_EDGE (e, ei, cfg_bb->succs) |
1004 | { |
1005 | bb_info *dest_bb = this->bb (cfg_bb: e->dest); |
1006 | if (dest_bb->ebb () != ebb || dest_bb == ebb->first_bb ()) |
1007 | record_live_out_regs (DF_LR_IN (e->dest)); |
1008 | } |
1009 | |
1010 | // Record the live-out memory value. |
1011 | bi.bb_mem_live_out[cfg_bb->index] |
1012 | = live_out_value (bb, set: bi.current_mem_value ()); |
1013 | } |
1014 | |
1015 | // Add BB and its contents to the SSA information. |
1016 | void |
1017 | function_info::start_block (build_info &bi, bb_info *bb) |
1018 | { |
1019 | ebb_info *ebb = bb->ebb (); |
1020 | |
1021 | // We (need to) add all blocks from one EBB before moving on to the next. |
1022 | bi.current_bb = bb; |
1023 | if (bb == ebb->first_bb ()) |
1024 | bi.current_ebb = ebb; |
1025 | else |
1026 | gcc_assert (bi.current_ebb == ebb); |
1027 | |
1028 | // Record the start of this block's definitions in the definitions stack. |
1029 | bi.old_def_stack_limit.safe_push (obj: bi.def_stack.length ()); |
1030 | |
1031 | // Add the block itself. |
1032 | append_bb (bb); |
1033 | |
1034 | // If the block starts an EBB, create the phi insn. This insn should exist |
1035 | // for all EBBs, even if they don't (yet) need phis. |
1036 | if (bb == ebb->first_bb ()) |
1037 | ebb->set_phi_insn (append_artificial_insn (bb)); |
1038 | |
1039 | if (bb->index () == ENTRY_BLOCK) |
1040 | { |
1041 | add_entry_block_defs (bi); |
1042 | record_block_live_out (bi); |
1043 | return; |
1044 | } |
1045 | |
1046 | if (EDGE_COUNT (bb->cfg_bb ()->preds) == 0) |
1047 | { |
1048 | // Leave unreachable blocks empty, since there is no useful |
1049 | // liveness information for them, and anything they do will |
1050 | // be wasted work. In a cleaned-up cfg, the only unreachable |
1051 | // block we should see is the exit block of a noreturn function. |
1052 | bb->set_head_insn (append_artificial_insn (bb)); |
1053 | bb->set_end_insn (append_artificial_insn (bb)); |
1054 | return; |
1055 | } |
1056 | |
1057 | // If the block starts an EBB, create the phi nodes. |
1058 | if (bb == ebb->first_bb ()) |
1059 | add_phi_nodes (bi); |
1060 | |
1061 | // Process the contents of the block. |
1062 | add_artificial_accesses (bi, flags: DF_REF_AT_TOP); |
1063 | if (bb->index () != EXIT_BLOCK) |
1064 | add_block_contents (bi); |
1065 | add_artificial_accesses (bi, flags: df_ref_flags ()); |
1066 | record_block_live_out (bi); |
1067 | |
1068 | // If we needed to calculate a live-in set for debug purposes, |
1069 | // reset it to null at the end of the EBB. Convert the underlying |
1070 | // bitmap to an empty list view, ready for the next calculation. |
1071 | if (bi.ebb_live_in_for_debug && bb == ebb->last_bb ()) |
1072 | { |
1073 | bitmap_clear (bi.tmp_ebb_live_in_for_debug); |
1074 | bitmap_list_view (bi.tmp_ebb_live_in_for_debug); |
1075 | bi.ebb_live_in_for_debug = nullptr; |
1076 | } |
1077 | } |
1078 | |
1079 | // Finish adding BB and the blocks that it dominates to the SSA information. |
1080 | void |
1081 | function_info::end_block (build_info &bi, bb_info *bb) |
1082 | { |
1083 | // Restore the register last_access information to the state it was |
1084 | // in before we started processing BB. |
1085 | unsigned int old_limit = bi.old_def_stack_limit.pop (); |
1086 | while (bi.def_stack.length () > old_limit) |
1087 | { |
1088 | // We pushed a definition in BB if it was the first dominating |
1089 | // definition (and so the previous entry was null). In other |
1090 | // cases we pushed the previous dominating definition. |
1091 | def_info *def = bi.def_stack.pop (); |
1092 | unsigned int regno = def->regno (); |
1093 | if (def->bb () == bb) |
1094 | def = nullptr; |
1095 | bi.last_access[regno + 1] = def; |
1096 | } |
1097 | } |
1098 | |
1099 | // Finish setting up the phi nodes for each block, now that we've added |
1100 | // the contents of all blocks. |
1101 | void |
1102 | function_info::populate_phi_inputs (build_info &bi) |
1103 | { |
1104 | auto_vec<phi_info *, 32> sorted_phis; |
1105 | for (ebb_info *ebb : ebbs ()) |
1106 | { |
1107 | if (!ebb->first_phi ()) |
1108 | continue; |
1109 | |
1110 | // Get a sorted array of EBB's phi nodes. |
1111 | basic_block cfg_bb = ebb->first_bb ()->cfg_bb (); |
1112 | bb_phi_info &phis = bi.bb_phis[cfg_bb->index]; |
1113 | sorted_phis.truncate (size: 0); |
1114 | for (phi_info *phi : ebb->phis ()) |
1115 | sorted_phis.safe_push (obj: phi); |
1116 | std::sort (first: sorted_phis.address (), |
1117 | last: sorted_phis.address () + sorted_phis.length (), |
1118 | comp: compare_access_infos); |
1119 | |
1120 | // Set the inputs of the non-degenerate register phis. All inputs |
1121 | // for one edge come before all inputs for the next edge. |
1122 | set_info **inputs = phis.inputs; |
1123 | unsigned int phi_i = 0; |
1124 | bitmap_iterator bmi; |
1125 | unsigned int regno; |
1126 | EXECUTE_IF_SET_IN_BITMAP (&phis.regs, 0, regno, bmi) |
1127 | { |
1128 | // Skip intervening degenerate phis. |
1129 | while (sorted_phis[phi_i]->regno () < regno) |
1130 | phi_i += 1; |
1131 | phi_info *phi = sorted_phis[phi_i]; |
1132 | gcc_assert (phi->regno () == regno); |
1133 | for (unsigned int input_i = 0; input_i < phis.num_preds; ++input_i) |
1134 | if (set_info *input = inputs[input_i * phis.num_phis]) |
1135 | { |
1136 | use_info *use = phi->input_use (i: input_i); |
1137 | gcc_assert (!use->def ()); |
1138 | use->set_def (input); |
1139 | add_use (use); |
1140 | } |
1141 | phi_i += 1; |
1142 | inputs += 1; |
1143 | } |
1144 | |
1145 | // Fill in the backedge inputs to any memory phi. |
1146 | phi_info *mem_phi = sorted_phis.last (); |
1147 | if (mem_phi->is_mem () && !mem_phi->is_degenerate ()) |
1148 | { |
1149 | edge e; |
1150 | edge_iterator ei; |
1151 | FOR_EACH_EDGE (e, ei, cfg_bb->preds) |
1152 | { |
1153 | use_info *use = mem_phi->input_use (i: e->dest_idx); |
1154 | if (!use->def ()) |
1155 | { |
1156 | use->set_def (bi.bb_mem_live_out[e->src->index]); |
1157 | add_use (use); |
1158 | } |
1159 | } |
1160 | } |
1161 | } |
1162 | } |
1163 | |
1164 | // Return true if it would be better to continue an EBB across NEW_EDGE |
1165 | // rather than across OLD_EDGE, given that both edges are viable candidates. |
1166 | // This is not a total ordering. |
1167 | static bool |
1168 | better_ebb_edge_p (edge new_edge, edge old_edge) |
1169 | { |
1170 | // Prefer the likeliest edge. |
1171 | if (new_edge->probability.initialized_p () |
1172 | && old_edge->probability.initialized_p () |
1173 | && !(old_edge->probability == new_edge->probability)) |
1174 | return old_edge->probability < new_edge->probability; |
1175 | |
1176 | // If both edges are equally likely, prefer a fallthru edge. |
1177 | if (new_edge->flags & EDGE_FALLTHRU) |
1178 | return true; |
1179 | if (old_edge->flags & EDGE_FALLTHRU) |
1180 | return false; |
1181 | |
1182 | // Otherwise just stick with OLD_EDGE. |
1183 | return false; |
1184 | } |
1185 | |
1186 | // Pick and return the next basic block in an EBB that currently ends with BB. |
1187 | // Return null if the EBB must end with BB. |
1188 | static basic_block |
1189 | choose_next_block_in_ebb (basic_block bb) |
1190 | { |
1191 | // Although there's nothing in principle wrong with having an EBB that |
1192 | // starts with the entry block and includes later blocks, there's not |
1193 | // really much point either. Keeping the entry block separate means |
1194 | // that uses of arguments consistently occur through phi nodes, rather |
1195 | // than the arguments sometimes appearing to come from an EBB-local |
1196 | // definition instead. |
1197 | if (bb->index == ENTRY_BLOCK) |
1198 | return nullptr; |
1199 | |
1200 | bool optimize_for_speed_p = optimize_bb_for_speed_p (bb); |
1201 | edge best_edge = nullptr; |
1202 | edge e; |
1203 | edge_iterator ei; |
1204 | FOR_EACH_EDGE (e, ei, bb->succs) |
1205 | if (!(e->flags & EDGE_COMPLEX) |
1206 | && e->dest->index != EXIT_BLOCK |
1207 | && single_pred_p (bb: e->dest) |
1208 | && optimize_for_speed_p == optimize_bb_for_speed_p (e->dest) |
1209 | && (!best_edge || better_ebb_edge_p (new_edge: e, old_edge: best_edge))) |
1210 | best_edge = e; |
1211 | |
1212 | return best_edge ? best_edge->dest : nullptr; |
1213 | } |
1214 | |
1215 | // Partition the function into extended basic blocks. Create the |
1216 | // associated ebb_infos and bb_infos, but don't add the bb_infos |
1217 | // to the function list yet. |
1218 | void |
1219 | function_info::create_ebbs (build_info &bi) |
1220 | { |
1221 | // Compute the starting reverse postorder. We tweak this later to try |
1222 | // to get better EBB assignments. |
1223 | auto *postorder = new int[n_basic_blocks_for_fn (m_fn)]; |
1224 | unsigned int postorder_num |
1225 | = pre_and_rev_post_order_compute (nullptr, postorder, true); |
1226 | gcc_assert (int (postorder_num) <= n_basic_blocks_for_fn (m_fn)); |
1227 | |
1228 | // Iterate over the blocks in reverse postorder. In cases where |
1229 | // multiple possible orders exist, prefer orders that chain blocks |
1230 | // together into EBBs. If multiple possible EBBs exist, try to pick |
1231 | // the ones that are most likely to be profitable. |
1232 | auto_vec<bb_info *, 16> bbs; |
1233 | unsigned int next_bb_index = 0; |
1234 | for (unsigned int i = 0; i < postorder_num; ++i) |
1235 | if (!m_bbs[postorder[i]]) |
1236 | { |
1237 | // Choose and create the blocks that should form the next EBB. |
1238 | basic_block cfg_bb = BASIC_BLOCK_FOR_FN (m_fn, postorder[i]); |
1239 | do |
1240 | { |
1241 | // Record the chosen block order in a new RPO. |
1242 | bi.bb_to_rpo[cfg_bb->index] = next_bb_index++; |
1243 | bbs.safe_push (obj: create_bb_info (cfg_bb)); |
1244 | cfg_bb = choose_next_block_in_ebb (bb: cfg_bb); |
1245 | } |
1246 | while (cfg_bb); |
1247 | |
1248 | // Create the EBB itself. |
1249 | auto *ebb = allocate<ebb_info> (args: bbs[0], args: bbs.last ()); |
1250 | for (bb_info *bb : bbs) |
1251 | bb->set_ebb (ebb); |
1252 | bbs.truncate (size: 0); |
1253 | } |
1254 | |
1255 | delete[] postorder; |
1256 | } |
1257 | |
1258 | // Partition the function's blocks into EBBs and build SSA form for all |
1259 | // EBBs in the function. |
1260 | void |
1261 | function_info::process_all_blocks () |
1262 | { |
1263 | auto temps = temp_watermark (); |
1264 | unsigned int num_bb_indices = last_basic_block_for_fn (m_fn); |
1265 | |
1266 | build_info bi (m_num_regs, num_bb_indices); |
1267 | |
1268 | // ??? There is no dominance information associated with the exit block, |
1269 | // so work out its immediate dominator using predecessor blocks. |
1270 | for (edge e : EXIT_BLOCK_PTR_FOR_FN (m_fn)->preds) |
1271 | if (bi.exit_block_dominator) |
1272 | bi.exit_block_dominator |
1273 | = nearest_common_dominator (CDI_DOMINATORS, |
1274 | bi.exit_block_dominator, e->src); |
1275 | else |
1276 | bi.exit_block_dominator = e->src; |
1277 | |
1278 | calculate_potential_phi_regs (bi); |
1279 | create_ebbs (bi); |
1280 | place_phis (bi); |
1281 | bb_walker (this, bi).walk (ENTRY_BLOCK_PTR_FOR_FN (m_fn)); |
1282 | populate_phi_inputs (bi); |
1283 | |
1284 | if (flag_checking) |
1285 | { |
1286 | // The definition stack should be empty and all register definitions |
1287 | // should be back in their original undefined state. |
1288 | gcc_assert (bi.def_stack.is_empty () |
1289 | && bi.old_def_stack_limit.is_empty ()); |
1290 | for (unsigned int regno = 0; regno < m_num_regs; ++regno) |
1291 | gcc_assert (!bi.last_access[regno + 1]); |
1292 | } |
1293 | } |
1294 | |
1295 | // Print a description of CALL_CLOBBERS to PP. |
1296 | void |
1297 | rtl_ssa::pp_ebb_call_clobbers (pretty_printer *pp, |
1298 | const ebb_call_clobbers_info *call_clobbers) |
1299 | { |
1300 | if (!call_clobbers) |
1301 | pp_string (pp, "<null>" ); |
1302 | else |
1303 | call_clobbers->print_full (pp); |
1304 | } |
1305 | |
1306 | // Print a description of BB to PP. |
1307 | void |
1308 | rtl_ssa::pp_bb (pretty_printer *pp, const bb_info *bb) |
1309 | { |
1310 | if (!bb) |
1311 | pp_string (pp, "<null>" ); |
1312 | else |
1313 | bb->print_full (pp); |
1314 | } |
1315 | |
1316 | // Print a description of EBB to PP |
1317 | void |
1318 | rtl_ssa::pp_ebb (pretty_printer *pp, const ebb_info *ebb) |
1319 | { |
1320 | if (!ebb) |
1321 | pp_string (pp, "<null>" ); |
1322 | else |
1323 | ebb->print_full (pp); |
1324 | } |
1325 | |
1326 | // Print a description of CALL_CLOBBERS to FILE. |
1327 | void |
1328 | dump (FILE *file, const ebb_call_clobbers_info *call_clobbers) |
1329 | { |
1330 | dump_using (file, printer: pp_ebb_call_clobbers, args: call_clobbers); |
1331 | } |
1332 | |
1333 | // Print a description of BB to FILE. |
1334 | void |
1335 | dump (FILE *file, const bb_info *bb) |
1336 | { |
1337 | dump_using (file, printer: pp_bb, args: bb); |
1338 | } |
1339 | |
1340 | // Print a description of EBB to FILE. |
1341 | void |
1342 | dump (FILE *file, const ebb_info *ebb) |
1343 | { |
1344 | dump_using (file, printer: pp_ebb, args: ebb); |
1345 | } |
1346 | |
1347 | // Debug interfaces to the dump routines above. |
1348 | void debug (const ebb_call_clobbers_info *x) { dump (stderr, call_clobbers: x); } |
1349 | void debug (const bb_info *x) { dump (stderr, bb: x); } |
1350 | void debug (const ebb_info *x) { dump (stderr, ebb: x); } |
1351 | |