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