Branch data Line data Source code
1 : : // Implementation of basic-block-related functions for RTL SSA -*- C++ -*-
2 : : // Copyright (C) 2020-2025 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 : 3861376 : function_info::build_info::build_info (unsigned int num_regs,
43 : 3861376 : unsigned int num_bb_indices)
44 : 3861376 : : current_bb (nullptr),
45 : 3861376 : current_ebb (nullptr),
46 : 3861376 : last_access (num_regs + 1),
47 : 3861376 : ebb_live_in_for_debug (nullptr),
48 : 3861376 : potential_phi_regs (num_regs),
49 : 3861376 : bb_phis (num_bb_indices),
50 : 3861376 : bb_mem_live_out (num_bb_indices),
51 : 3861376 : bb_to_rpo (num_bb_indices),
52 : 7722752 : exit_block_dominator (nullptr)
53 : : {
54 : 3861376 : last_access.safe_grow_cleared (num_regs + 1);
55 : :
56 : 3861376 : 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 : 3861376 : bb_phis.quick_grow_cleared (num_bb_indices);
63 : 3861376 : bb_mem_live_out.quick_grow (num_bb_indices);
64 : 3861376 : bb_to_rpo.quick_grow (num_bb_indices);
65 : 3861376 : if (flag_checking)
66 : : {
67 : : // Can't do this for bb_phis because it has a constructor.
68 : 7722624 : memset (bb_mem_live_out.address (), 0xaf,
69 : 3861312 : num_bb_indices * sizeof (bb_mem_live_out[0]));
70 : 7722624 : 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 : 59177190 : for (bb_phi_info &info : bb_phis)
76 : 47593062 : bitmap_initialize (&info.regs, &bitmap_default_obstack);
77 : 3861376 : }
78 : :
79 : 3861376 : function_info::build_info::~build_info ()
80 : : {
81 : 59177190 : for (bb_phi_info &info : bb_phis)
82 : 47593062 : bitmap_release (&info.regs);
83 : 3861376 : }
84 : :
85 : : // A dom_walker for populating the basic blocks.
86 : 7722752 : 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 : 3861376 : 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 : 3861376 : m_function (function),
107 : 3861376 : m_bi (bi),
108 : 7722752 : m_exit_block_dominator (bi.exit_block_dominator)
109 : : {
110 : : // If the exit block is unreachable, process it last.
111 : 3861376 : if (!m_exit_block_dominator)
112 : 94650 : m_exit_block_dominator = ENTRY_BLOCK_PTR_FOR_FN (m_function->m_fn);
113 : 3861376 : }
114 : :
115 : : edge
116 : 46295491 : function_info::bb_walker::before_dom_children (basic_block bb)
117 : : {
118 : 46295491 : m_function->start_block (m_bi, m_function->bb (bb));
119 : 46295491 : return nullptr;
120 : : }
121 : :
122 : : void
123 : 46295491 : function_info::bb_walker::after_dom_children (basic_block bb)
124 : : {
125 : : // See the comment in the constructor for details.
126 : 46295491 : if (bb == m_exit_block_dominator)
127 : : {
128 : 3861376 : before_dom_children (EXIT_BLOCK_PTR_FOR_FN (m_function->m_fn));
129 : 3861376 : after_dom_children (EXIT_BLOCK_PTR_FOR_FN (m_function->m_fn));
130 : : }
131 : 46295491 : m_function->end_block (m_bi, m_function->bb (bb));
132 : 46295491 : }
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 : 71353072 : 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 : 71353072 : 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 : 53435567 : use_info *use = def->last_nondebug_insn_use ();
319 : 30103907 : if (use && use->insn () == bb->end_insn ())
320 : : return;
321 : :
322 : : // Currently there is no need to maintain a backward link from the end
323 : : // instruction to the list of live-out uses. Such a list would be
324 : : // expensive to update if it was represented using the usual insn_info
325 : : // access arrays.
326 : 47035323 : use = allocate<use_info> (bb->end_insn (), def->resource (), def);
327 : 47035323 : use->set_is_live_out_use (true);
328 : 47035323 : add_use (use);
329 : : }
330 : :
331 : : // Return true if all nondebug uses of DEF are live-out uses.
332 : : static bool
333 : 10214787 : all_uses_are_live_out_uses (set_info *def)
334 : : {
335 : 10235314 : for (use_info *use : def->all_uses ())
336 : 12909690 : if (!use->is_in_debug_insn () && !use->is_live_out_use ())
337 : 10214787 : return false;
338 : : return true;
339 : : }
340 : :
341 : : // SET, if nonnull, is a definition of something that is live out from BB.
342 : : // Return the live-out value itself.
343 : : set_info *
344 : 150529618 : function_info::live_out_value (bb_info *bb, set_info *set)
345 : : {
346 : : // Degenerate phis only exist to provide a definition for uses in the
347 : : // same EBB. The live-out value is the same as the live-in value.
348 : 150529618 : if (auto *phi = safe_dyn_cast<phi_info *> (set))
349 : 39709579 : if (phi->is_degenerate ())
350 : : {
351 : 15924932 : set = phi->input_value (0);
352 : :
353 : : // Remove the phi if it turned out to be useless. This is
354 : : // mainly useful for memory, because we don't know ahead of time
355 : : // whether a block will use memory or not.
356 : 15924932 : if (bb == bb->ebb ()->last_bb () && all_uses_are_live_out_uses (phi))
357 : 3780469 : replace_phi (phi, set);
358 : : }
359 : :
360 : 150529618 : return set;
361 : : }
362 : :
363 : : // Add PHI to EBB and enter it into the function's hash table.
364 : : void
365 : 57422439 : function_info::append_phi (ebb_info *ebb, phi_info *phi)
366 : : {
367 : 57422439 : phi_info *first_phi = ebb->first_phi ();
368 : 57422439 : if (first_phi)
369 : 32579019 : first_phi->set_prev_phi (phi);
370 : 57422439 : phi->set_next_phi (first_phi);
371 : 57422439 : ebb->set_first_phi (phi);
372 : 57422439 : add_def (phi);
373 : 57422439 : }
374 : :
375 : : // Remove PHI from its current position in the SSA graph.
376 : : void
377 : 6709116 : function_info::remove_phi (phi_info *phi)
378 : : {
379 : 6709116 : phi_info *next = phi->next_phi ();
380 : 6709116 : phi_info *prev = phi->prev_phi ();
381 : :
382 : 6709116 : if (next)
383 : 888432 : next->set_prev_phi (prev);
384 : :
385 : 6709116 : if (prev)
386 : 3412046 : prev->set_next_phi (next);
387 : : else
388 : 3297070 : phi->ebb ()->set_first_phi (next);
389 : :
390 : 6709116 : remove_def (phi);
391 : 6709116 : phi->clear_phi_links ();
392 : 6709116 : }
393 : :
394 : : // Remove PHI from the SSA graph and free its memory.
395 : : void
396 : 6709116 : function_info::delete_phi (phi_info *phi)
397 : : {
398 : 6709116 : gcc_assert (!phi->has_any_uses ());
399 : :
400 : : // Remove the inputs to the phi.
401 : 20749619 : for (use_info *input : phi->inputs ())
402 : 7331387 : remove_use (input);
403 : :
404 : 6709116 : remove_phi (phi);
405 : :
406 : 6709116 : phi->set_next_phi (m_free_phis);
407 : 6709116 : m_free_phis = phi;
408 : 6709116 : }
409 : :
410 : : // If possible, remove PHI and replace all uses with NEW_VALUE.
411 : : void
412 : 37736836 : function_info::replace_phi (phi_info *phi, set_info *new_value)
413 : : {
414 : 39632008 : auto update_use = [&](use_info *use)
415 : : {
416 : 1895172 : remove_use (use);
417 : 1895172 : use->set_def (new_value);
418 : 1895172 : add_use (use);
419 : 39632008 : };
420 : :
421 : 37736836 : if (new_value)
422 : 75470468 : for (use_info *use : phi->nondebug_insn_uses ())
423 : 31057456 : if (!use->is_live_out_use ())
424 : : {
425 : : // We need to keep the phi around for its local uses.
426 : : // Turn it into a degenerate phi, if it isn't already.
427 : 31057454 : use_info *single_use = nullptr;
428 : 94114072 : for (auto *use : phi->inputs ())
429 : 31999164 : if (!single_use)
430 : : single_use = use;
431 : 941710 : else if (use->def () == new_value)
432 : : {
433 : 760873 : remove_use (single_use);
434 : 760873 : single_use = use;
435 : : }
436 : : else
437 : 180837 : remove_use (use);
438 : :
439 : 31057454 : if (single_use->def () != new_value)
440 : 0 : update_use (single_use);
441 : :
442 : 31057454 : if (phi->is_degenerate ())
443 : 31057454 : return;
444 : :
445 : 767754 : phi->make_degenerate (single_use);
446 : :
447 : : // Redirect all phi users to NEW_VALUE.
448 : 33207002 : while (use_info *phi_use = phi->last_phi_use ())
449 : 1381794 : update_use (phi_use);
450 : :
451 : : return;
452 : : }
453 : :
454 : : // Replace the uses. We can discard uses that only existed for the
455 : : // sake of marking live-out values, since the resource is now transparent
456 : : // in the phi's EBB.
457 : 7195552 : while (use_info *use = phi->last_use ())
458 : 516170 : if (use->is_live_out_use ())
459 : 2792 : remove_use (use);
460 : : else
461 : 513378 : update_use (use);
462 : :
463 : 6679382 : delete_phi (phi);
464 : : }
465 : :
466 : : // Create and return a phi node for EBB. RESOURCE is the resource that
467 : : // the phi node sets (and thus that all the inputs set too). NUM_INPUTS
468 : : // is the number of inputs, which is 1 for a degenerate phi. INPUTS[I]
469 : : // is a set_info that gives the value of input I, or null if the value
470 : : // is either unknown or uninitialized. If NUM_INPUTS > 1, this array
471 : : // is allocated on the main obstack and can be reused for the use array.
472 : : //
473 : : // Add the created phi node to its basic block and enter it into the
474 : : // function's hash table.
475 : : phi_info *
476 : 57422439 : function_info::create_phi (ebb_info *ebb, resource_info resource,
477 : : access_info **inputs, unsigned int num_inputs)
478 : : {
479 : 57422439 : phi_info *phi = m_free_phis;
480 : 57422439 : if (phi)
481 : : {
482 : 3784642 : m_free_phis = phi->next_phi ();
483 : 3784642 : *phi = phi_info (ebb->phi_insn (), resource, phi->uid ());
484 : : }
485 : : else
486 : : {
487 : 53637797 : phi = allocate<phi_info> (ebb->phi_insn (), resource, m_next_phi_uid);
488 : 53637797 : m_next_phi_uid += 1;
489 : : }
490 : :
491 : : // Convert the array of set_infos into an array of use_infos. Also work
492 : : // out what mode the phi should have.
493 : 57422439 : machine_mode new_mode = resource.mode;
494 : 150407056 : for (unsigned int i = 0; i < num_inputs; ++i)
495 : : {
496 : 92984617 : auto *input = safe_as_a<set_info *> (inputs[i]);
497 : 92984617 : auto *use = allocate<use_info> (phi, resource, input);
498 : 92984617 : add_use (use);
499 : 92984617 : inputs[i] = use;
500 : 92984617 : if (input)
501 : 57629294 : new_mode = combine_modes (new_mode, input->mode ());
502 : : }
503 : :
504 : 57422439 : phi->set_inputs (use_array (inputs, num_inputs));
505 : 57422439 : phi->set_mode (new_mode);
506 : :
507 : 57422439 : append_phi (ebb, phi);
508 : :
509 : 57422439 : return phi;
510 : : }
511 : :
512 : : // Create and return a degenerate phi for EBB whose input comes from DEF.
513 : : // This is used in cases where DEF is known to be available on entry to
514 : : // EBB but was not previously used within it. If DEF is for a register,
515 : : // there are two cases:
516 : : //
517 : : // (1) DEF was already live on entry to EBB but was previously transparent
518 : : // within it.
519 : : //
520 : : // (2) DEF was not previously live on entry to EBB and is being made live
521 : : // by this update.
522 : : //
523 : : // At the moment, this function only handles the case in which EBB has a
524 : : // single predecessor block and DEF is defined in that block's EBB.
525 : : phi_info *
526 : 11766 : function_info::create_degenerate_phi (ebb_info *ebb, set_info *def)
527 : : {
528 : : // Allow the function to be called twice in succession for the same def.
529 : 11766 : def_lookup dl = find_def (def->resource (), ebb->phi_insn ());
530 : 11766 : if (set_info *set = dl.matching_set ())
531 : 637 : return as_a<phi_info *> (set);
532 : :
533 : 11129 : access_info *input = def;
534 : 11129 : phi_info *phi = create_phi (ebb, def->resource (), &input, 1);
535 : 11129 : if (def->is_reg ())
536 : : {
537 : 9284 : unsigned int regno = def->regno ();
538 : :
539 : : // Find the single predecessor mentioned above.
540 : 9284 : basic_block pred_cfg_bb = single_pred (ebb->first_bb ()->cfg_bb ());
541 : 9284 : bb_info *pred_bb = this->bb (pred_cfg_bb);
542 : :
543 : 18568 : if (!bitmap_set_bit (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno))
544 : : {
545 : : // The register was not previously live on entry to EBB and
546 : : // might not have been live on exit from PRED_BB either.
547 : 4288 : if (bitmap_set_bit (DF_LR_OUT (pred_cfg_bb), regno))
548 : 0 : add_live_out_use (pred_bb, def);
549 : : }
550 : : else
551 : : {
552 : : // The register was previously live in to EBB. Add live-out uses
553 : : // at the appropriate points.
554 : 7140 : insn_info *next_insn = nullptr;
555 : 7140 : if (def_info *next_def = phi->next_def ())
556 : 4874 : next_insn = next_def->insn ();
557 : 7140 : for (bb_info *bb : ebb->bbs ())
558 : : {
559 : 4874 : if ((next_insn && *next_insn <= *bb->end_insn ())
560 : 15494 : || !bitmap_bit_p (DF_LR_OUT (bb->cfg_bb ()), regno))
561 : : break;
562 : 0 : add_live_out_use (bb, def);
563 : : }
564 : : }
565 : : }
566 : : return phi;
567 : : }
568 : :
569 : : // Create a bb_info for CFG_BB, given that no such structure currently exists.
570 : : bb_info *
571 : 46295491 : function_info::create_bb_info (basic_block cfg_bb)
572 : : {
573 : 46295491 : bb_info *bb = allocate<bb_info> (cfg_bb);
574 : 46295491 : gcc_checking_assert (!m_bbs[cfg_bb->index]);
575 : 46295491 : m_bbs[cfg_bb->index] = bb;
576 : 46295491 : return bb;
577 : : }
578 : :
579 : : // Add BB to the end of the list of blocks.
580 : : void
581 : 46295491 : function_info::append_bb (bb_info *bb)
582 : : {
583 : 46295491 : if (m_last_bb)
584 : 42434115 : m_last_bb->set_next_bb (bb);
585 : : else
586 : 3861376 : m_first_bb = bb;
587 : 46295491 : bb->set_prev_bb (m_last_bb);
588 : 46295491 : m_last_bb = bb;
589 : 46295491 : }
590 : :
591 : : // Calculate BI.potential_phi_regs and BI.potential_phi_regs_for_debug.
592 : : void
593 : 3861376 : function_info::calculate_potential_phi_regs (build_info &bi)
594 : : {
595 : 3861376 : auto *lr_info = DF_LR_BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (m_fn));
596 : 3861376 : bool is_debug = MAY_HAVE_DEBUG_INSNS;
597 : 543015984 : for (unsigned int regno = 0; regno < m_num_regs; ++regno)
598 : 539154608 : if (regno >= DF_REG_SIZE (DF)
599 : : // Exclude registers that have a single definition that dominates
600 : : // all uses. If the definition does not dominate all uses,
601 : : // the register will be exposed upwards to the entry block but
602 : : // will not be defined by the entry block.
603 : 539136874 : || DF_REG_DEF_COUNT (regno) > 1
604 : 923819819 : || (!bitmap_bit_p (&lr_info->def, regno)
605 : 353980901 : && bitmap_bit_p (&lr_info->out, regno)))
606 : : {
607 : 154723677 : bitmap_set_bit (bi.potential_phi_regs, regno);
608 : 154723677 : if (is_debug)
609 : 92426830 : bitmap_set_bit (bi.potential_phi_regs_for_debug, regno);
610 : : }
611 : 3861376 : }
612 : :
613 : : // Called while building SSA form using BI. Decide where phi nodes
614 : : // should be placed for each register and initialize BI.bb_phis accordingly.
615 : : void
616 : 3861376 : function_info::place_phis (build_info &bi)
617 : : {
618 : 3861376 : unsigned int num_bb_indices = last_basic_block_for_fn (m_fn);
619 : :
620 : : // Calculate dominance frontiers.
621 : 3861376 : auto_vec<bitmap_head> frontiers;
622 : 3861376 : frontiers.safe_grow_cleared (num_bb_indices);
623 : 51454438 : for (unsigned int i = 0; i < num_bb_indices; ++i)
624 : 47593062 : bitmap_initialize (&frontiers[i], &bitmap_default_obstack);
625 : 7722752 : compute_dominance_frontiers (frontiers.address ());
626 : :
627 : : // The normal dominance information doesn't calculate dominators for
628 : : // the exit block, so we don't get dominance frontiers for them either.
629 : : // Calculate them by hand.
630 : 15563480 : for (edge e : EXIT_BLOCK_PTR_FOR_FN (m_fn)->preds)
631 : : {
632 : 3979352 : basic_block bb = e->src;
633 : 4811643 : while (bb != bi.exit_block_dominator)
634 : : {
635 : 832291 : bitmap_set_bit (&frontiers[bb->index], EXIT_BLOCK);
636 : 832291 : bb = get_immediate_dominator (CDI_DOMINATORS, bb);
637 : : }
638 : : }
639 : :
640 : : // In extreme cases, the number of live-in registers can be much
641 : : // greater than the number of phi nodes needed in a block (see PR98863).
642 : : // Try to reduce the number of operations involving live-in sets by using
643 : : // PENDING as a staging area: registers in PENDING need phi nodes if
644 : : // they are live on entry to the corresponding block, but do not need
645 : : // phi nodes otherwise.
646 : 3861376 : auto_vec<bitmap_head> unfiltered;
647 : 3861376 : unfiltered.safe_grow_cleared (num_bb_indices);
648 : 51454438 : for (unsigned int i = 0; i < num_bb_indices; ++i)
649 : 47593062 : bitmap_initialize (&unfiltered[i], &bitmap_default_obstack);
650 : :
651 : : // If block B1 defines R and if B2 is in the dominance frontier of B1,
652 : : // queue a possible phi node for R in B2.
653 : 3861376 : auto_bitmap worklist;
654 : 51454438 : for (unsigned int b1 = 0; b1 < num_bb_indices; ++b1)
655 : : {
656 : : // Only access DF information for blocks that are known to exist.
657 : 47593062 : if (bitmap_empty_p (&frontiers[b1]))
658 : 18563135 : continue;
659 : :
660 : : // Defs in B1 that are possibly in LR_IN in the dominance frontier
661 : : // blocks.
662 : 29029927 : auto_bitmap b1_def;
663 : 58059854 : bitmap_and (b1_def, &DF_LR_BB_INFO (BASIC_BLOCK_FOR_FN (m_fn, b1))->def,
664 : 58059854 : DF_LR_OUT (BASIC_BLOCK_FOR_FN (m_fn, b1)));
665 : :
666 : 29029927 : bitmap_iterator bmi;
667 : 29029927 : unsigned int b2;
668 : 74514960 : EXECUTE_IF_SET_IN_BITMAP (&frontiers[b1], 0, b2, bmi)
669 : 45485033 : if (bitmap_ior_into (&unfiltered[b2], b1_def)
670 : 45485033 : && !bitmap_empty_p (&frontiers[b2]))
671 : : // Propagate the (potential) new phi node definitions in B2.
672 : 12814925 : bitmap_set_bit (worklist, b2);
673 : 29029927 : }
674 : :
675 : 10146667 : while (!bitmap_empty_p (worklist))
676 : : {
677 : 6285291 : unsigned int b1 = bitmap_first_set_bit (worklist);
678 : 6285291 : bitmap_clear_bit (worklist, b1);
679 : :
680 : : // Restrict the phi nodes to registers that are live on entry to
681 : : // the block.
682 : 6285291 : bitmap b1_in = DF_LR_IN (BASIC_BLOCK_FOR_FN (m_fn, b1));
683 : 6285291 : bitmap b1_phis = &bi.bb_phis[b1].regs;
684 : 6285291 : if (!bitmap_ior_and_into (b1_phis, &unfiltered[b1], b1_in))
685 : 1007849 : continue;
686 : :
687 : : // If block B1 has a phi node for R and if B2 is in the dominance
688 : : // frontier of B1, queue a possible phi node for R in B2.
689 : 5277442 : bitmap_iterator bmi;
690 : 5277442 : unsigned int b2;
691 : 14843539 : EXECUTE_IF_SET_IN_BITMAP (&frontiers[b1], 0, b2, bmi)
692 : 9566097 : if (bitmap_ior_into (&unfiltered[b2], b1_phis)
693 : 9566097 : && !bitmap_empty_p (&frontiers[b2]))
694 : 1442753 : bitmap_set_bit (worklist, b2);
695 : : }
696 : :
697 : 3861376 : basic_block cfg_bb;
698 : 50156867 : FOR_ALL_BB_FN (cfg_bb, m_fn)
699 : : {
700 : : // Calculate the set of phi nodes for blocks that don't have any
701 : : // dominance frontiers. We only need to do this once per block.
702 : 46295491 : unsigned int i = cfg_bb->index;
703 : 46295491 : bb_phi_info &phis = bi.bb_phis[i];
704 : 46295491 : if (bitmap_empty_p (&frontiers[i]))
705 : 34531128 : bitmap_and (&phis.regs, &unfiltered[i], DF_LR_IN (cfg_bb));
706 : :
707 : : // Create an array that contains all phi inputs for this block.
708 : : // See the comment above the member variables for more information.
709 : 46295491 : phis.num_phis = bitmap_count_bits (&phis.regs);
710 : 46295491 : phis.num_preds = EDGE_COUNT (cfg_bb->preds);
711 : 46295491 : unsigned int num_inputs = phis.num_phis * phis.num_preds;
712 : 46295491 : if (num_inputs != 0)
713 : : {
714 : 6279581 : phis.inputs = XOBNEWVEC (&m_temp_obstack, set_info *, num_inputs);
715 : 6279581 : memset (phis.inputs, 0, num_inputs * sizeof (phis.inputs[0]));
716 : : }
717 : : }
718 : :
719 : : // Free the temporary bitmaps.
720 : 51454438 : for (unsigned int i = 0; i < num_bb_indices; ++i)
721 : : {
722 : 47593062 : bitmap_release (&frontiers[i]);
723 : 47593062 : bitmap_release (&unfiltered[i]);
724 : : }
725 : 3861376 : }
726 : :
727 : : // Called while building SSA form using BI, with BI.current_bb being
728 : : // the entry block.
729 : : //
730 : : // Create the entry block instructions and their definitions. The only
731 : : // useful instruction is the end instruction, which carries definitions
732 : : // for the values that are live on entry to the function. However, it
733 : : // seems simpler to create a head instruction too, rather than force all
734 : : // users of the block information to treat the entry block as a special case.
735 : : void
736 : 3861376 : function_info::add_entry_block_defs (build_info &bi)
737 : : {
738 : 3861376 : bb_info *bb = bi.current_bb;
739 : 3861376 : basic_block cfg_bb = bi.current_bb->cfg_bb ();
740 : 3861376 : auto *lr_info = DF_LR_BB_INFO (cfg_bb);
741 : :
742 : 3861376 : bb->set_head_insn (append_artificial_insn (bb));
743 : 3861376 : insn_info *insn = append_artificial_insn (bb);
744 : 3861376 : bb->set_end_insn (insn);
745 : :
746 : 3861376 : start_insn_accesses ();
747 : :
748 : : // Using LR to derive the liveness information means that we create an
749 : : // entry block definition for upwards exposed registers. These registers
750 : : // are sometimes genuinely uninitialized. However, some targets also
751 : : // create a pseudo PIC base register and only initialize it later.
752 : : // Handling that case correctly seems more important than optimizing
753 : : // uninitialized uses.
754 : 3861376 : unsigned int regno;
755 : 3861376 : bitmap_iterator in_bi;
756 : 22382234 : EXECUTE_IF_SET_IN_BITMAP (&lr_info->out, 0, regno, in_bi)
757 : : {
758 : 18520858 : auto *set = allocate<set_info> (insn, full_register (regno));
759 : 18520858 : append_def (set);
760 : 18520858 : m_temp_defs.safe_push (set);
761 : 18520858 : bi.record_reg_def (set);
762 : : }
763 : :
764 : : // Create a definition that reflects the state of memory on entry to
765 : : // the function.
766 : 3861376 : auto *set = allocate<set_info> (insn, memory);
767 : 3861376 : append_def (set);
768 : 3861376 : m_temp_defs.safe_push (set);
769 : 3861376 : bi.record_mem_def (set);
770 : :
771 : 3861376 : finish_insn_accesses (insn);
772 : 3861376 : }
773 : :
774 : : // Lazily calculate the value of BI.ebb_live_in_for_debug for BI.current_ebb.
775 : : void
776 : 979047 : function_info::calculate_ebb_live_in_for_debug (build_info &bi)
777 : : {
778 : 979047 : gcc_checking_assert (bitmap_empty_p (bi.tmp_ebb_live_in_for_debug));
779 : 979047 : bi.ebb_live_in_for_debug = bi.tmp_ebb_live_in_for_debug;
780 : 1958094 : bitmap_and (bi.ebb_live_in_for_debug, bi.potential_phi_regs_for_debug,
781 : 1958094 : DF_LR_IN (bi.current_ebb->first_bb ()->cfg_bb ()));
782 : 979047 : bitmap_tree_view (bi.ebb_live_in_for_debug);
783 : 979047 : }
784 : :
785 : : // Called while building SSA form using BI. Create phi nodes for the
786 : : // current EBB.
787 : : void
788 : 24842519 : function_info::add_phi_nodes (build_info &bi)
789 : : {
790 : 24842519 : ebb_info *ebb = bi.current_ebb;
791 : 24842519 : basic_block cfg_bb = ebb->first_bb ()->cfg_bb ();
792 : :
793 : : // Create the register phis for this EBB.
794 : 24842519 : bb_phi_info &phis = bi.bb_phis[cfg_bb->index];
795 : 24842519 : unsigned int num_preds = phis.num_preds;
796 : 24842519 : unsigned int regno;
797 : 24842519 : bitmap_iterator in_bi;
798 : 36762849 : EXECUTE_IF_SET_IN_BITMAP (&phis.regs, 0, regno, in_bi)
799 : : {
800 : 11920330 : gcc_checking_assert (bitmap_bit_p (bi.potential_phi_regs, regno));
801 : :
802 : : // Create an array of phi inputs, to be filled in later.
803 : 11920330 : auto *inputs = XOBNEWVEC (&m_obstack, access_info *, num_preds);
804 : 11920330 : memset (inputs, 0, sizeof (access_info *) * num_preds);
805 : :
806 : : // Later code works out the correct mode of the phi. Use BLKmode
807 : : // as a placeholder for now.
808 : 11920330 : phi_info *phi = create_phi (ebb, { E_BLKmode, regno },
809 : : inputs, num_preds);
810 : 11920330 : bi.record_reg_def (phi);
811 : : }
812 : :
813 : 24842519 : bitmap_copy (bi.ebb_def_regs, &phis.regs);
814 : :
815 : : // Collect the live-in memory definitions and record whether they're
816 : : // all the same.
817 : 24842519 : m_temp_defs.reserve (num_preds);
818 : 24842519 : set_info *mem_value = nullptr;
819 : 24842519 : bool mem_phi_is_degenerate = true;
820 : 24842519 : edge e;
821 : 24842519 : edge_iterator ei;
822 : 67616402 : FOR_EACH_EDGE (e, ei, cfg_bb->preds)
823 : : {
824 : 42773883 : bb_info *pred_bb = this->bb (e->src);
825 : 42773883 : if (pred_bb && pred_bb->head_insn ())
826 : : {
827 : 40346124 : mem_value = bi.bb_mem_live_out[pred_bb->index ()];
828 : 40346124 : m_temp_defs.quick_push (mem_value);
829 : 40346124 : if (mem_value != m_temp_defs[0])
830 : 13017030 : mem_phi_is_degenerate = false;
831 : : }
832 : : else
833 : : {
834 : 2427759 : m_temp_defs.quick_push (nullptr);
835 : 2427759 : mem_phi_is_degenerate = false;
836 : : }
837 : : }
838 : :
839 : : // Create a phi for memory, on the assumption that something in the
840 : : // EBB will need it.
841 : 24842519 : if (mem_phi_is_degenerate)
842 : : {
843 : 16919576 : access_info *input[] = { mem_value };
844 : 16919576 : mem_value = create_phi (ebb, memory, input, 1);
845 : : }
846 : : else
847 : : {
848 : 7922943 : obstack_grow (&m_obstack, m_temp_defs.address (),
849 : : num_preds * sizeof (access_info *));
850 : 7922943 : auto *inputs = static_cast<access_info **> (obstack_finish (&m_obstack));
851 : 7922943 : mem_value = create_phi (ebb, memory, inputs, num_preds);
852 : : }
853 : 24842519 : bi.record_mem_def (mem_value);
854 : 24842519 : m_temp_defs.truncate (0);
855 : 24842519 : }
856 : :
857 : : // Called while building SSA form using BI.
858 : : //
859 : : // If FLAGS is DF_REF_AT_TOP, create the head insn for BI.current_bb
860 : : // and populate its uses and definitions. If FLAGS is 0, do the same
861 : : // for the end insn.
862 : : void
863 : 84678930 : function_info::add_artificial_accesses (build_info &bi, df_ref_flags flags)
864 : : {
865 : 84678930 : bb_info *bb = bi.current_bb;
866 : 84678930 : basic_block cfg_bb = bb->cfg_bb ();
867 : 84678930 : auto *lr_info = DF_LR_BB_INFO (cfg_bb);
868 : 84678930 : df_ref ref;
869 : :
870 : 84678930 : insn_info *insn;
871 : 84678930 : if (flags == DF_REF_AT_TOP)
872 : : {
873 : 42339465 : if (cfg_bb->index == EXIT_BLOCK)
874 : 3766726 : insn = append_artificial_insn (bb);
875 : : else
876 : 38572739 : insn = append_artificial_insn (bb, bb_note (cfg_bb));
877 : 42339465 : bb->set_head_insn (insn);
878 : : }
879 : : else
880 : : {
881 : 42339465 : insn = append_artificial_insn (bb);
882 : 42339465 : bb->set_end_insn (insn);
883 : : }
884 : :
885 : 84678930 : start_insn_accesses ();
886 : :
887 : 84678930 : HARD_REG_SET added_regs = {};
888 : 446722620 : FOR_EACH_ARTIFICIAL_USE (ref, cfg_bb->index)
889 : 277364760 : if ((DF_REF_FLAGS (ref) & DF_REF_AT_TOP) == flags)
890 : : {
891 : 138682380 : unsigned int regno = DF_REF_REGNO (ref);
892 : 138682380 : machine_mode mode = GET_MODE (DF_REF_REAL_REG (ref));
893 : 138682380 : if (HARD_REGISTER_NUM_P (regno))
894 : 138682380 : SET_HARD_REG_BIT (added_regs, regno);
895 : :
896 : : // A definition must be available.
897 : 138682380 : gcc_checking_assert (bitmap_bit_p (&lr_info->in, regno)
898 : : || (flags != DF_REF_AT_TOP
899 : : && bitmap_bit_p (&lr_info->def, regno)));
900 : 138682380 : m_temp_uses.safe_push (create_reg_use (bi, insn, { mode, regno }));
901 : : }
902 : :
903 : : // Ensure that global registers and memory are live at the end of any
904 : : // block that has no successors, such as the exit block and non-local gotos.
905 : : // Global registers have to be singled out because they are not part of
906 : : // the DF artifical use list (they are instead treated as used within
907 : : // every block).
908 : 84678930 : if (flags == 0 && EDGE_COUNT (cfg_bb->succs) == 0)
909 : : {
910 : 532963935 : for (unsigned int i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
911 : 527233140 : if (global_regs[i] && !TEST_HARD_REG_BIT (added_regs, i))
912 : : {
913 : 30 : auto mode = reg_raw_mode[i];
914 : 30 : m_temp_uses.safe_push (create_reg_use (bi, insn, { mode, i }));
915 : : }
916 : :
917 : 5730795 : auto *use = allocate<use_info> (insn, memory, bi.current_mem_value ());
918 : 5730795 : add_use (use);
919 : 5730795 : m_temp_uses.safe_push (use);
920 : : }
921 : :
922 : 172257716 : FOR_EACH_ARTIFICIAL_DEF (ref, cfg_bb->index)
923 : 2899856 : if ((DF_REF_FLAGS (ref) & DF_REF_AT_TOP) == flags)
924 : : {
925 : 1449928 : unsigned int regno = DF_REF_REGNO (ref);
926 : 1449928 : machine_mode mode = GET_MODE (DF_REF_REAL_REG (ref));
927 : 1449928 : resource_info resource { mode, regno };
928 : :
929 : : // We rely on the def set being correct.
930 : 1449928 : gcc_checking_assert (bitmap_bit_p (&lr_info->def, regno));
931 : :
932 : : // If the value isn't used later in the block and isn't live
933 : : // on exit, we could instead represent the definition as a
934 : : // clobber_info. However, that case should be relatively
935 : : // rare and set_info is any case more compact than clobber_info.
936 : 1449928 : set_info *def = allocate<set_info> (insn, resource);
937 : 1449928 : append_def (def);
938 : 1449928 : m_temp_defs.safe_push (def);
939 : 1449928 : bi.record_reg_def (def);
940 : : }
941 : :
942 : : // Model the effect of a memory clobber on an incoming edge by adding
943 : : // a fake definition of memory at the start of the block. We don't need
944 : : // to add a use of the phi node because memory is implicitly always live.
945 : 84678930 : if (flags == DF_REF_AT_TOP && has_abnormal_call_or_eh_pred_edge_p (cfg_bb))
946 : : {
947 : 726882 : set_info *def = allocate<set_info> (insn, memory);
948 : 726882 : append_def (def);
949 : 726882 : m_temp_defs.safe_push (def);
950 : 726882 : bi.record_mem_def (def);
951 : : }
952 : :
953 : 84678930 : finish_insn_accesses (insn);
954 : 84678930 : }
955 : :
956 : : // Called while building SSA form using BI. Create insn_infos for all
957 : : // relevant instructions in BI.current_bb.
958 : : void
959 : 38572739 : function_info::add_block_contents (build_info &bi)
960 : : {
961 : 38572739 : basic_block cfg_bb = bi.current_bb->cfg_bb ();
962 : 38572739 : rtx_insn *insn;
963 : 488361133 : FOR_BB_INSNS (cfg_bb, insn)
964 : 449788394 : if (INSN_P (insn))
965 : 380068651 : add_insn_to_block (bi, insn);
966 : 38572739 : }
967 : :
968 : : // Called while building SSA form using BI. Record live-out register values
969 : : // in the phi inputs of successor blocks and create live-out uses where
970 : : // appropriate. Record the live-out memory value in BI.bb_mem_live_out.
971 : : void
972 : 46200841 : function_info::record_block_live_out (build_info &bi)
973 : : {
974 : 46200841 : bb_info *bb = bi.current_bb;
975 : 46200841 : ebb_info *ebb = bi.current_ebb;
976 : 46200841 : basic_block cfg_bb = bb->cfg_bb ();
977 : :
978 : : // Record the live-out register values in the phi inputs of
979 : : // successor blocks.
980 : 46200841 : edge e;
981 : 46200841 : edge_iterator ei;
982 : 106471670 : FOR_EACH_EDGE (e, ei, cfg_bb->succs)
983 : : {
984 : 60270829 : bb_phi_info &phis = bi.bb_phis[e->dest->index];
985 : 60270829 : unsigned int input_i = e->dest_idx * phis.num_phis;
986 : 60270829 : unsigned int regno;
987 : 60270829 : bitmap_iterator out_bi;
988 : 93198393 : EXECUTE_IF_SET_IN_BITMAP (&phis.regs, 0, regno, out_bi)
989 : : {
990 : 65855128 : phis.inputs[input_i]
991 : 32927564 : = live_out_value (bb, bi.current_reg_value (regno));
992 : 32927564 : input_i += 1;
993 : : }
994 : : }
995 : :
996 : : // Add the set of registers that were defined in this BB to the set
997 : : // of potentially-live registers defined in the EBB.
998 : 92401682 : bitmap_ior_into (bi.ebb_def_regs, &DF_LR_BB_INFO (cfg_bb)->def);
999 : :
1000 : : // Iterate through the registers in LIVE_OUT and see whether we need
1001 : : // to add a live-out use for them.
1002 : 92246845 : auto record_live_out_regs = [&](bitmap live_out)
1003 : : {
1004 : 46046004 : unsigned int regno;
1005 : 46046004 : bitmap_iterator out_bi;
1006 : 117447217 : EXECUTE_IF_AND_IN_BITMAP (bi.ebb_def_regs, live_out, 0, regno, out_bi)
1007 : : {
1008 : 71401213 : set_info *value = live_out_value (bb, bi.current_reg_value (regno));
1009 : 71401213 : if (value && value->ebb () == ebb)
1010 : 71353072 : add_live_out_use (bb, value);
1011 : : }
1012 : 92246845 : };
1013 : :
1014 : 46200841 : if (bb == ebb->last_bb ())
1015 : : // All live-out registers might need live-out uses.
1016 : 57407790 : record_live_out_regs (DF_LR_OUT (cfg_bb));
1017 : : else
1018 : : // Registers might need live-out uses if they are live on entry
1019 : : // to a successor block in a different EBB.
1020 : 52336001 : FOR_EACH_EDGE (e, ei, cfg_bb->succs)
1021 : : {
1022 : 34839055 : bb_info *dest_bb = this->bb (e->dest);
1023 : 34839055 : if (dest_bb->ebb () != ebb || dest_bb == ebb->first_bb ())
1024 : 34684218 : record_live_out_regs (DF_LR_IN (e->dest));
1025 : : }
1026 : :
1027 : : // Record the live-out memory value.
1028 : 46200841 : bi.bb_mem_live_out[cfg_bb->index]
1029 : 46200841 : = live_out_value (bb, bi.current_mem_value ());
1030 : 46200841 : }
1031 : :
1032 : : // Add BB and its contents to the SSA information.
1033 : : void
1034 : 46295491 : function_info::start_block (build_info &bi, bb_info *bb)
1035 : : {
1036 : 46295491 : ebb_info *ebb = bb->ebb ();
1037 : :
1038 : : // We (need to) add all blocks from one EBB before moving on to the next.
1039 : 46295491 : bi.current_bb = bb;
1040 : 46295491 : if (bb == ebb->first_bb ())
1041 : 28798545 : bi.current_ebb = ebb;
1042 : : else
1043 : 17496946 : gcc_assert (bi.current_ebb == ebb);
1044 : :
1045 : : // Record the start of this block's definitions in the definitions stack.
1046 : 88729606 : bi.old_def_stack_limit.safe_push (bi.def_stack.length ());
1047 : :
1048 : : // Add the block itself.
1049 : 46295491 : append_bb (bb);
1050 : :
1051 : : // If the block starts an EBB, create the phi insn. This insn should exist
1052 : : // for all EBBs, even if they don't (yet) need phis.
1053 : 46295491 : if (bb == ebb->first_bb ())
1054 : 28798545 : ebb->set_phi_insn (append_artificial_insn (bb));
1055 : :
1056 : 46295491 : if (bb->index () == ENTRY_BLOCK)
1057 : : {
1058 : 3861376 : add_entry_block_defs (bi);
1059 : 3861376 : record_block_live_out (bi);
1060 : 3861376 : return;
1061 : : }
1062 : :
1063 : 42434115 : if (EDGE_COUNT (bb->cfg_bb ()->preds) == 0)
1064 : : {
1065 : : // Leave unreachable blocks empty, since there is no useful
1066 : : // liveness information for them, and anything they do will
1067 : : // be wasted work. In a cleaned-up cfg, the only unreachable
1068 : : // block we should see is the exit block of a noreturn function.
1069 : 94650 : bb->set_head_insn (append_artificial_insn (bb));
1070 : 94650 : bb->set_end_insn (append_artificial_insn (bb));
1071 : 94650 : return;
1072 : : }
1073 : :
1074 : : // If the block starts an EBB, create the phi nodes.
1075 : 42339465 : if (bb == ebb->first_bb ())
1076 : 24842519 : add_phi_nodes (bi);
1077 : :
1078 : : // Process the contents of the block.
1079 : 42339465 : add_artificial_accesses (bi, DF_REF_AT_TOP);
1080 : 42339465 : if (bb->index () != EXIT_BLOCK)
1081 : 38572739 : add_block_contents (bi);
1082 : 42339465 : add_artificial_accesses (bi, df_ref_flags ());
1083 : 42339465 : record_block_live_out (bi);
1084 : :
1085 : : // If we needed to calculate a live-in set for debug purposes,
1086 : : // reset it to null at the end of the EBB. Convert the underlying
1087 : : // bitmap to an empty list view, ready for the next calculation.
1088 : 42339465 : if (bi.ebb_live_in_for_debug && bb == ebb->last_bb ())
1089 : : {
1090 : 979047 : bitmap_clear (bi.tmp_ebb_live_in_for_debug);
1091 : 979047 : bitmap_list_view (bi.tmp_ebb_live_in_for_debug);
1092 : 979047 : bi.ebb_live_in_for_debug = nullptr;
1093 : : }
1094 : : }
1095 : :
1096 : : // Finish adding BB and the blocks that it dominates to the SSA information.
1097 : : void
1098 : 46295491 : function_info::end_block (build_info &bi, bb_info *bb)
1099 : : {
1100 : : // Restore the register last_access information to the state it was
1101 : : // in before we started processing BB.
1102 : 46295491 : unsigned int old_limit = bi.old_def_stack_limit.pop ();
1103 : 270342379 : while (bi.def_stack.length () > old_limit)
1104 : : {
1105 : : // We pushed a definition in BB if it was the first dominating
1106 : : // definition (and so the previous entry was null). In other
1107 : : // cases we pushed the previous dominating definition.
1108 : 224046888 : def_info *def = bi.def_stack.pop ();
1109 : 224046888 : unsigned int regno = def->regno ();
1110 : 224046888 : if (def->bb () == bb)
1111 : 123062632 : def = nullptr;
1112 : 224046888 : bi.last_access[regno + 1] = def;
1113 : : }
1114 : 46295491 : }
1115 : :
1116 : : // Finish setting up the phi nodes for each block, now that we've added
1117 : : // the contents of all blocks.
1118 : : void
1119 : 3861376 : function_info::populate_phi_inputs (build_info &bi)
1120 : : {
1121 : 3861376 : auto_vec<phi_info *, 32> sorted_phis;
1122 : 61458466 : for (ebb_info *ebb : ebbs ())
1123 : : {
1124 : 28798545 : if (!ebb->first_phi ())
1125 : 6053102 : continue;
1126 : :
1127 : : // Get a sorted array of EBB's phi nodes.
1128 : 22745443 : basic_block cfg_bb = ebb->first_bb ()->cfg_bb ();
1129 : 22745443 : bb_phi_info &phis = bi.bb_phis[cfg_bb->index];
1130 : 22745443 : sorted_phis.truncate (0);
1131 : 76376284 : for (phi_info *phi : ebb->phis ())
1132 : 53630841 : sorted_phis.safe_push (phi);
1133 : 22745443 : std::sort (sorted_phis.address (),
1134 : 45490886 : sorted_phis.address () + sorted_phis.length (),
1135 : : compare_access_infos);
1136 : :
1137 : : // Set the inputs of the non-degenerate register phis. All inputs
1138 : : // for one edge come before all inputs for the next edge.
1139 : 22745443 : set_info **inputs = phis.inputs;
1140 : 22745443 : unsigned int phi_i = 0;
1141 : 22745443 : bitmap_iterator bmi;
1142 : 22745443 : unsigned int regno;
1143 : 34665773 : EXECUTE_IF_SET_IN_BITMAP (&phis.regs, 0, regno, bmi)
1144 : : {
1145 : : // Skip intervening degenerate phis.
1146 : 14507702 : while (sorted_phis[phi_i]->regno () < regno)
1147 : 2587372 : phi_i += 1;
1148 : 11920330 : phi_info *phi = sorted_phis[phi_i];
1149 : 11920330 : gcc_assert (phi->regno () == regno);
1150 : 44847894 : for (unsigned int input_i = 0; input_i < phis.num_preds; ++input_i)
1151 : 32927564 : if (set_info *input = inputs[input_i * phis.num_phis])
1152 : : {
1153 : 32891379 : use_info *use = phi->input_use (input_i);
1154 : 32891379 : gcc_assert (!use->def ());
1155 : 32891379 : use->set_def (input);
1156 : 32891379 : add_use (use);
1157 : : }
1158 : 11920330 : phi_i += 1;
1159 : 11920330 : inputs += 1;
1160 : : }
1161 : :
1162 : : // Fill in the backedge inputs to any memory phi.
1163 : 22745443 : phi_info *mem_phi = sorted_phis.last ();
1164 : 22745443 : if (mem_phi->is_mem () && !mem_phi->is_degenerate ())
1165 : : {
1166 : 7922943 : edge e;
1167 : 7922943 : edge_iterator ei;
1168 : 30400830 : FOR_EACH_EDGE (e, ei, cfg_bb->preds)
1169 : : {
1170 : 22477887 : use_info *use = mem_phi->input_use (e->dest_idx);
1171 : 22477887 : if (!use->def ())
1172 : : {
1173 : 2427759 : use->set_def (bi.bb_mem_live_out[e->src->index]);
1174 : 2427759 : add_use (use);
1175 : : }
1176 : : }
1177 : : }
1178 : : }
1179 : 3861376 : }
1180 : :
1181 : : // Return true if it would be better to continue an EBB across NEW_EDGE
1182 : : // rather than across OLD_EDGE, given that both edges are viable candidates.
1183 : : // This is not a total ordering.
1184 : : static bool
1185 : 4680625 : better_ebb_edge_p (edge new_edge, edge old_edge)
1186 : : {
1187 : : // Prefer the likeliest edge.
1188 : 4680625 : if (new_edge->probability.initialized_p ()
1189 : 4679661 : && old_edge->probability.initialized_p ()
1190 : 9360286 : && !(old_edge->probability == new_edge->probability))
1191 : 3892906 : return old_edge->probability < new_edge->probability;
1192 : :
1193 : : // If both edges are equally likely, prefer a fallthru edge.
1194 : 787719 : if (new_edge->flags & EDGE_FALLTHRU)
1195 : : return true;
1196 : : if (old_edge->flags & EDGE_FALLTHRU)
1197 : : return false;
1198 : :
1199 : : // Otherwise just stick with OLD_EDGE.
1200 : : return false;
1201 : : }
1202 : :
1203 : : // Pick and return the next basic block in an EBB that currently ends with BB.
1204 : : // Return null if the EBB must end with BB.
1205 : : static basic_block
1206 : 46295491 : choose_next_block_in_ebb (basic_block bb)
1207 : : {
1208 : : // Although there's nothing in principle wrong with having an EBB that
1209 : : // starts with the entry block and includes later blocks, there's not
1210 : : // really much point either. Keeping the entry block separate means
1211 : : // that uses of arguments consistently occur through phi nodes, rather
1212 : : // than the arguments sometimes appearing to come from an EBB-local
1213 : : // definition instead.
1214 : 46295491 : if (bb->index == ENTRY_BLOCK)
1215 : : return nullptr;
1216 : :
1217 : 42434115 : bool optimize_for_speed_p = optimize_bb_for_speed_p (bb);
1218 : 42434115 : edge best_edge = nullptr;
1219 : 42434115 : edge e;
1220 : 42434115 : edge_iterator ei;
1221 : 98843568 : FOR_EACH_EDGE (e, ei, bb->succs)
1222 : 56409453 : if (!(e->flags & EDGE_COMPLEX)
1223 : 52982645 : && e->dest->index != EXIT_BLOCK
1224 : 105884236 : && single_pred_p (e->dest)
1225 : 24086469 : && optimize_for_speed_p == optimize_bb_for_speed_p (e->dest)
1226 : 78587024 : && (!best_edge || better_ebb_edge_p (e, best_edge)))
1227 : : best_edge = e;
1228 : :
1229 : 42434115 : return best_edge ? best_edge->dest : nullptr;
1230 : : }
1231 : :
1232 : : // Partition the function into extended basic blocks. Create the
1233 : : // associated ebb_infos and bb_infos, but don't add the bb_infos
1234 : : // to the function list yet.
1235 : : void
1236 : 3861376 : function_info::create_ebbs (build_info &bi)
1237 : : {
1238 : : // Compute the starting reverse postorder. We tweak this later to try
1239 : : // to get better EBB assignments.
1240 : 3861376 : auto *postorder = new int[n_basic_blocks_for_fn (m_fn)];
1241 : 3861376 : unsigned int postorder_num
1242 : 3861376 : = pre_and_rev_post_order_compute (nullptr, postorder, true);
1243 : 3861376 : gcc_assert (int (postorder_num) <= n_basic_blocks_for_fn (m_fn));
1244 : :
1245 : : // Iterate over the blocks in reverse postorder. In cases where
1246 : : // multiple possible orders exist, prefer orders that chain blocks
1247 : : // together into EBBs. If multiple possible EBBs exist, try to pick
1248 : : // the ones that are most likely to be profitable.
1249 : 3861376 : auto_vec<bb_info *, 16> bbs;
1250 : 3861376 : unsigned int next_bb_index = 0;
1251 : 50156867 : for (unsigned int i = 0; i < postorder_num; ++i)
1252 : 46295491 : if (!m_bbs[postorder[i]])
1253 : : {
1254 : : // Choose and create the blocks that should form the next EBB.
1255 : 28798545 : basic_block cfg_bb = BASIC_BLOCK_FOR_FN (m_fn, postorder[i]);
1256 : 46295491 : do
1257 : : {
1258 : : // Record the chosen block order in a new RPO.
1259 : 46295491 : bi.bb_to_rpo[cfg_bb->index] = next_bb_index++;
1260 : 46295491 : bbs.safe_push (create_bb_info (cfg_bb));
1261 : 46295491 : cfg_bb = choose_next_block_in_ebb (cfg_bb);
1262 : : }
1263 : 46295491 : while (cfg_bb);
1264 : :
1265 : : // Create the EBB itself.
1266 : 28798545 : auto *ebb = allocate<ebb_info> (bbs[0], bbs.last ());
1267 : 132691126 : for (bb_info *bb : bbs)
1268 : 46295491 : bb->set_ebb (ebb);
1269 : 28798545 : bbs.truncate (0);
1270 : : }
1271 : :
1272 : 3861376 : delete[] postorder;
1273 : 3861376 : }
1274 : :
1275 : : // Partition the function's blocks into EBBs and build SSA form for all
1276 : : // EBBs in the function.
1277 : : void
1278 : 3861376 : function_info::process_all_blocks ()
1279 : : {
1280 : 3861376 : auto temps = temp_watermark ();
1281 : 3861376 : unsigned int num_bb_indices = last_basic_block_for_fn (m_fn);
1282 : :
1283 : 3861376 : build_info bi (m_num_regs, num_bb_indices);
1284 : :
1285 : : // ??? There is no dominance information associated with the exit block,
1286 : : // so work out its immediate dominator using predecessor blocks.
1287 : 15563480 : for (edge e : EXIT_BLOCK_PTR_FOR_FN (m_fn)->preds)
1288 : 3979352 : if (bi.exit_block_dominator)
1289 : 212626 : bi.exit_block_dominator
1290 : 212626 : = nearest_common_dominator (CDI_DOMINATORS,
1291 : : bi.exit_block_dominator, e->src);
1292 : : else
1293 : 3766726 : bi.exit_block_dominator = e->src;
1294 : :
1295 : 3861376 : calculate_potential_phi_regs (bi);
1296 : 3861376 : create_ebbs (bi);
1297 : 3861376 : place_phis (bi);
1298 : 3861376 : bb_walker (this, bi).walk (ENTRY_BLOCK_PTR_FOR_FN (m_fn));
1299 : 3861376 : populate_phi_inputs (bi);
1300 : :
1301 : 3861376 : if (flag_checking)
1302 : : {
1303 : : // The definition stack should be empty and all register definitions
1304 : : // should be back in their original undefined state.
1305 : 7722624 : gcc_assert (bi.def_stack.is_empty ()
1306 : : && bi.old_def_stack_limit.is_empty ());
1307 : 543009287 : for (unsigned int regno = 0; regno < m_num_regs; ++regno)
1308 : 539147975 : gcc_assert (!bi.last_access[regno + 1]);
1309 : : }
1310 : 3861376 : }
1311 : :
1312 : : // Print a description of CALL_CLOBBERS to PP.
1313 : : void
1314 : 0 : rtl_ssa::pp_ebb_call_clobbers (pretty_printer *pp,
1315 : : const ebb_call_clobbers_info *call_clobbers)
1316 : : {
1317 : 0 : if (!call_clobbers)
1318 : 0 : pp_string (pp, "<null>");
1319 : : else
1320 : 0 : call_clobbers->print_full (pp);
1321 : 0 : }
1322 : :
1323 : : // Print a description of BB to PP.
1324 : : void
1325 : 0 : rtl_ssa::pp_bb (pretty_printer *pp, const bb_info *bb)
1326 : : {
1327 : 0 : if (!bb)
1328 : 0 : pp_string (pp, "<null>");
1329 : : else
1330 : 0 : bb->print_full (pp);
1331 : 0 : }
1332 : :
1333 : : // Print a description of EBB to PP
1334 : : void
1335 : 0 : rtl_ssa::pp_ebb (pretty_printer *pp, const ebb_info *ebb)
1336 : : {
1337 : 0 : if (!ebb)
1338 : 0 : pp_string (pp, "<null>");
1339 : : else
1340 : 0 : ebb->print_full (pp);
1341 : 0 : }
1342 : :
1343 : : // Print a description of CALL_CLOBBERS to FILE.
1344 : : void
1345 : 0 : dump (FILE *file, const ebb_call_clobbers_info *call_clobbers)
1346 : : {
1347 : 0 : dump_using (file, pp_ebb_call_clobbers, call_clobbers);
1348 : 0 : }
1349 : :
1350 : : // Print a description of BB to FILE.
1351 : : void
1352 : 0 : dump (FILE *file, const bb_info *bb)
1353 : : {
1354 : 0 : dump_using (file, pp_bb, bb);
1355 : 0 : }
1356 : :
1357 : : // Print a description of EBB to FILE.
1358 : : void
1359 : 0 : dump (FILE *file, const ebb_info *ebb)
1360 : : {
1361 : 0 : dump_using (file, pp_ebb, ebb);
1362 : 0 : }
1363 : :
1364 : : // Debug interfaces to the dump routines above.
1365 : 0 : void debug (const ebb_call_clobbers_info *x) { dump (stderr, x); }
1366 : 0 : void debug (const bb_info *x) { dump (stderr, x); }
1367 : 0 : void debug (const ebb_info *x) { dump (stderr, x); }
|