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