1 // Implementation of basic-block-related functions for RTL SSA -*- C++ -*-
2 // Copyright (C) 2020-2024 Free Software Foundation, Inc.
4 // This file is part of GCC.
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
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
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/>.
20 #define INCLUDE_ALGORITHM
21 #define INCLUDE_FUNCTIONAL
25 #include "coretypes.h"
30 #include "rtl-ssa/internals.h"
31 #include "rtl-ssa/internals.inl"
37 using namespace rtl_ssa
;
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
42 function_info::build_info::build_info (unsigned int num_regs
,
43 unsigned int num_bb_indices
)
44 : current_bb (nullptr),
45 current_ebb (nullptr),
46 last_access (num_regs
+ 1),
47 ebb_live_in_for_debug (nullptr),
48 potential_phi_regs (num_regs
),
49 bb_phis (num_bb_indices
),
50 bb_mem_live_out (num_bb_indices
),
51 bb_to_rpo (num_bb_indices
),
52 exit_block_dominator (nullptr)
54 last_access
.safe_grow_cleared (num_regs
+ 1);
56 bitmap_clear (potential_phi_regs
);
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 bb_phis
.quick_grow_cleared (num_bb_indices
);
63 bb_mem_live_out
.quick_grow (num_bb_indices
);
64 bb_to_rpo
.quick_grow (num_bb_indices
);
67 // Can't do this for bb_phis because it has a constructor.
68 memset (bb_mem_live_out
.address (), 0xaf,
69 num_bb_indices
* sizeof (bb_mem_live_out
[0]));
70 memset (bb_to_rpo
.address (), 0xaf,
71 num_bb_indices
* sizeof (bb_to_rpo
[0]));
74 // Start off with an empty set of phi nodes for each block.
75 for (bb_phi_info
&info
: bb_phis
)
76 bitmap_initialize (&info
.regs
, &bitmap_default_obstack
);
79 function_info::build_info::~build_info ()
81 for (bb_phi_info
&info
: bb_phis
)
82 bitmap_release (&info
.regs
);
85 // A dom_walker for populating the basic blocks.
86 class function_info::bb_walker
: public dom_walker
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
;
94 // Information about the function we're building.
95 function_info
*m_function
;
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
;
103 // Prepare to walk the blocks in FUNCTION using BI.
104 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 m_function (function
),
108 m_exit_block_dominator (bi
.exit_block_dominator
)
110 // If the exit block is unreachable, process it last.
111 if (!m_exit_block_dominator
)
112 m_exit_block_dominator
= ENTRY_BLOCK_PTR_FOR_FN (m_function
->m_fn
);
116 function_info::bb_walker::before_dom_children (basic_block bb
)
118 m_function
->start_block (m_bi
, m_function
->bb (bb
));
123 function_info::bb_walker::after_dom_children (basic_block bb
)
125 // See the comment in the constructor for details.
126 if (bb
== m_exit_block_dominator
)
128 before_dom_children (EXIT_BLOCK_PTR_FOR_FN (m_function
->m_fn
));
129 after_dom_children (EXIT_BLOCK_PTR_FOR_FN (m_function
->m_fn
));
131 m_function
->end_block (m_bi
, m_function
->bb (bb
));
134 // See the comment above the declaration.
136 bb_info::print_identifier (pretty_printer
*pp
) const
138 char tmp
[3 * sizeof (index ()) + 3];
139 snprintf (tmp
, sizeof (tmp
), "bb%d", index ());
141 if (ebb_info
*ebb
= this->ebb ())
144 pp_left_bracket (pp
);
145 ebb
->print_identifier (pp
);
146 pp_right_bracket (pp
);
150 // See the comment above the declaration.
152 bb_info::print_full (pretty_printer
*pp
) const
154 pp_string (pp
, "basic block ");
155 print_identifier (pp
);
158 auto print_insn
= [pp
](const char *header
, const insn_info
*insn
)
160 pp_newline_and_indent (pp
, 2);
161 pp_string (pp
, header
);
162 pp_newline_and_indent (pp
, 2);
166 pp_string (pp
, "<uninitialized>");
167 pp_indentation (pp
) -= 4;
170 print_insn ("head:", head_insn ());
173 pp_newline_and_indent (pp
, 2);
174 pp_string (pp
, "contents:");
177 pp_newline_and_indent (pp
, 2);
178 pp_string (pp
, "<uninitialized>");
179 pp_indentation (pp
) -= 2;
181 else if (auto insns
= real_insns ())
183 bool is_first
= true;
184 for (const insn_info
*insn
: insns
)
190 pp_newline_and_indent (pp
, 2);
192 pp_indentation (pp
) -= 2;
197 pp_newline_and_indent (pp
, 2);
198 pp_string (pp
, "none");
199 pp_indentation (pp
) -= 2;
201 pp_indentation (pp
) -= 2;
204 print_insn ("end:", end_insn ());
207 // See the comment above the declaration.
209 ebb_call_clobbers_info::print_summary (pretty_printer
*pp
) const
211 pp_string (pp
, "call clobbers for ABI ");
213 pp_decimal_int (pp
, m_abi
->id ());
215 pp_string (pp
, "<null>");
218 // See the comment above the declaration.
220 ebb_call_clobbers_info::print_full (pretty_printer
*pp
) const
224 pp_newline_and_indent (pp
, 2);
225 auto print_node
= [](pretty_printer
*pp
,
226 const insn_call_clobbers_note
*note
)
228 if (insn_info
*insn
= note
->insn ())
229 insn
->print_identifier_and_location (pp
);
231 pp_string (pp
, "<null>");
233 print (pp
, root (), print_node
);
234 pp_indentation (pp
) -= 2;
237 // See the comment above the declaration.
239 ebb_info::print_identifier (pretty_printer
*pp
) const
241 // first_bb is populated by the constructor and so should always
243 auto index
= first_bb ()->index ();
244 char tmp
[3 * sizeof (index
) + 4];
245 snprintf (tmp
, sizeof (tmp
), "ebb%d", index
);
249 // See the comment above the declaration.
251 ebb_info::print_full (pretty_printer
*pp
) const
253 pp_string (pp
, "extended basic block ");
254 print_identifier (pp
);
257 pp_newline_and_indent (pp
, 2);
258 if (insn_info
*phi_insn
= this->phi_insn ())
260 phi_insn
->print_identifier_and_location (pp
);
262 if (auto phis
= this->phis ())
264 bool is_first
= true;
265 for (const phi_info
*phi
: phis
)
271 pp_newline_and_indent (pp
, 2);
272 pp_access (pp
, phi
, PP_ACCESS_SETTER
);
273 pp_indentation (pp
) -= 2;
278 pp_newline_and_indent (pp
, 2);
279 pp_string (pp
, "no phi nodes");
280 pp_indentation (pp
) -= 2;
284 pp_string (pp
, "no phi insn");
285 pp_indentation (pp
) -= 2;
287 for (const bb_info
*bb
: bbs ())
290 pp_newline_and_indent (pp
, 2);
292 pp_indentation (pp
) -= 2;
295 for (ebb_call_clobbers_info
*ecc
: call_clobbers ())
298 pp_newline_and_indent (pp
, 2);
299 pp_ebb_call_clobbers (pp
, ecc
);
300 pp_indentation (pp
) -= 2;
304 // Add a dummy use to mark that DEF is live out of BB's EBB at the end of BB.
306 function_info::add_live_out_use (bb_info
*bb
, set_info
*def
)
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 if (def
->insn () == bb
->end_insn ())
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 use_info
*use
= def
->last_nondebug_insn_use ();
319 if (use
&& use
->insn () == bb
->end_insn ())
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
326 use
= allocate
<use_info
> (bb
->end_insn (), def
->resource (), def
);
327 use
->set_is_live_out_use (true);
331 // Return true if all nondebug uses of DEF are live-out uses.
333 all_uses_are_live_out_uses (set_info
*def
)
335 for (use_info
*use
: def
->all_uses ())
336 if (!use
->is_in_debug_insn () && !use
->is_live_out_use ())
341 // SET, if nonnull, is a definition of something that is live out from BB.
342 // Return the live-out value itself.
344 function_info::live_out_value (bb_info
*bb
, set_info
*set
)
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 if (auto *phi
= safe_dyn_cast
<phi_info
*> (set
))
349 if (phi
->is_degenerate ())
351 set
= phi
->input_value (0);
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 if (bb
== bb
->ebb ()->last_bb () && all_uses_are_live_out_uses (phi
))
357 replace_phi (phi
, set
);
363 // Add PHI to EBB and enter it into the function's hash table.
365 function_info::append_phi (ebb_info
*ebb
, phi_info
*phi
)
367 phi_info
*first_phi
= ebb
->first_phi ();
369 first_phi
->set_prev_phi (phi
);
370 phi
->set_next_phi (first_phi
);
371 ebb
->set_first_phi (phi
);
375 // Remove PHI from its current position in the SSA graph.
377 function_info::remove_phi (phi_info
*phi
)
379 phi_info
*next
= phi
->next_phi ();
380 phi_info
*prev
= phi
->prev_phi ();
383 next
->set_prev_phi (prev
);
386 prev
->set_next_phi (next
);
388 phi
->ebb ()->set_first_phi (next
);
391 phi
->clear_phi_links ();
394 // Remove PHI from the SSA graph and free its memory.
396 function_info::delete_phi (phi_info
*phi
)
398 gcc_assert (!phi
->has_any_uses ());
400 // Remove the inputs to the phi.
401 for (use_info
*input
: phi
->inputs ())
406 phi
->set_next_phi (m_free_phis
);
410 // If possible, remove PHI and replace all uses with NEW_VALUE.
412 function_info::replace_phi (phi_info
*phi
, set_info
*new_value
)
414 auto update_use
= [&](use_info
*use
)
417 use
->set_def (new_value
);
422 for (use_info
*use
: phi
->nondebug_insn_uses ())
423 if (!use
->is_live_out_use ())
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 use_info
*use
= phi
->input_use (0);
428 if (use
->def () != new_value
)
431 if (phi
->is_degenerate ())
434 phi
->make_degenerate (use
);
436 // Redirect all phi users to NEW_VALUE.
437 while (use_info
*phi_use
= phi
->last_phi_use ())
438 update_use (phi_use
);
443 // Replace the uses. We can discard uses that only existed for the
444 // sake of marking live-out values, since the resource is now transparent
446 while (use_info
*use
= phi
->last_use ())
447 if (use
->is_live_out_use ())
455 // Create and return a phi node for EBB. RESOURCE is the resource that
456 // the phi node sets (and thus that all the inputs set too). NUM_INPUTS
457 // is the number of inputs, which is 1 for a degenerate phi. INPUTS[I]
458 // is a set_info that gives the value of input I, or null if the value
459 // is either unknown or uninitialized. If NUM_INPUTS > 1, this array
460 // is allocated on the main obstack and can be reused for the use array.
462 // Add the created phi node to its basic block and enter it into the
463 // function's hash table.
465 function_info::create_phi (ebb_info
*ebb
, resource_info resource
,
466 access_info
**inputs
, unsigned int num_inputs
)
468 phi_info
*phi
= m_free_phis
;
471 m_free_phis
= phi
->next_phi ();
472 *phi
= phi_info (ebb
->phi_insn (), resource
, phi
->uid ());
476 phi
= allocate
<phi_info
> (ebb
->phi_insn (), resource
, m_next_phi_uid
);
480 // Convert the array of set_infos into an array of use_infos. Also work
481 // out what mode the phi should have.
482 machine_mode new_mode
= resource
.mode
;
483 for (unsigned int i
= 0; i
< num_inputs
; ++i
)
485 auto *input
= safe_as_a
<set_info
*> (inputs
[i
]);
486 auto *use
= allocate
<use_info
> (phi
, resource
, input
);
490 new_mode
= combine_modes (new_mode
, input
->mode ());
493 phi
->set_inputs (use_array (inputs
, num_inputs
));
494 phi
->set_mode (new_mode
);
496 append_phi (ebb
, phi
);
501 // Create and return a degenerate phi for EBB whose input comes from DEF.
502 // This is used in cases where DEF is known to be available on entry to
503 // EBB but was not previously used within it. If DEF is for a register,
504 // there are two cases:
506 // (1) DEF was already live on entry to EBB but was previously transparent
509 // (2) DEF was not previously live on entry to EBB and is being made live
512 // At the moment, this function only handles the case in which EBB has a
513 // single predecessor block and DEF is defined in that block's EBB.
515 function_info::create_degenerate_phi (ebb_info
*ebb
, set_info
*def
)
517 // Allow the function to be called twice in succession for the same def.
518 def_lookup dl
= find_def (def
->resource (), ebb
->phi_insn ());
519 if (set_info
*set
= dl
.matching_set ())
520 return as_a
<phi_info
*> (set
);
522 access_info
*input
= def
;
523 phi_info
*phi
= create_phi (ebb
, def
->resource (), &input
, 1);
526 unsigned int regno
= def
->regno ();
528 // Find the single predecessor mentioned above.
529 basic_block pred_cfg_bb
= single_pred (ebb
->first_bb ()->cfg_bb ());
530 bb_info
*pred_bb
= this->bb (pred_cfg_bb
);
532 if (!bitmap_set_bit (DF_LR_IN (ebb
->first_bb ()->cfg_bb ()), regno
))
534 // The register was not previously live on entry to EBB and
535 // might not have been live on exit from PRED_BB either.
536 if (bitmap_set_bit (DF_LR_OUT (pred_cfg_bb
), regno
))
537 add_live_out_use (pred_bb
, def
);
541 // The register was previously live in to EBB. Add live-out uses
542 // at the appropriate points.
543 insn_info
*next_insn
= nullptr;
544 if (def_info
*next_def
= phi
->next_def ())
545 next_insn
= next_def
->insn ();
546 for (bb_info
*bb
: ebb
->bbs ())
548 if ((next_insn
&& *next_insn
<= *bb
->end_insn ())
549 || !bitmap_bit_p (DF_LR_OUT (bb
->cfg_bb ()), regno
))
551 add_live_out_use (bb
, def
);
558 // Create a bb_info for CFG_BB, given that no such structure currently exists.
560 function_info::create_bb_info (basic_block cfg_bb
)
562 bb_info
*bb
= allocate
<bb_info
> (cfg_bb
);
563 gcc_checking_assert (!m_bbs
[cfg_bb
->index
]);
564 m_bbs
[cfg_bb
->index
] = bb
;
568 // Add BB to the end of the list of blocks.
570 function_info::append_bb (bb_info
*bb
)
573 m_last_bb
->set_next_bb (bb
);
576 bb
->set_prev_bb (m_last_bb
);
580 // Calculate BI.potential_phi_regs and BI.potential_phi_regs_for_debug.
582 function_info::calculate_potential_phi_regs (build_info
&bi
)
584 auto *lr_info
= DF_LR_BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (m_fn
));
585 bool is_debug
= MAY_HAVE_DEBUG_INSNS
;
586 for (unsigned int regno
= 0; regno
< m_num_regs
; ++regno
)
587 if (regno
>= DF_REG_SIZE (DF
)
588 // Exclude registers that have a single definition that dominates
589 // all uses. If the definition does not dominate all uses,
590 // the register will be exposed upwards to the entry block but
591 // will not be defined by the entry block.
592 || DF_REG_DEF_COUNT (regno
) > 1
593 || (!bitmap_bit_p (&lr_info
->def
, regno
)
594 && bitmap_bit_p (&lr_info
->out
, regno
)))
596 bitmap_set_bit (bi
.potential_phi_regs
, regno
);
598 bitmap_set_bit (bi
.potential_phi_regs_for_debug
, regno
);
602 // Called while building SSA form using BI. Decide where phi nodes
603 // should be placed for each register and initialize BI.bb_phis accordingly.
605 function_info::place_phis (build_info
&bi
)
607 unsigned int num_bb_indices
= last_basic_block_for_fn (m_fn
);
609 // Calculate dominance frontiers.
610 auto_vec
<bitmap_head
> frontiers
;
611 frontiers
.safe_grow_cleared (num_bb_indices
);
612 for (unsigned int i
= 0; i
< num_bb_indices
; ++i
)
613 bitmap_initialize (&frontiers
[i
], &bitmap_default_obstack
);
614 compute_dominance_frontiers (frontiers
.address ());
616 // The normal dominance information doesn't calculate dominators for
617 // the exit block, so we don't get dominance frontiers for them either.
618 // Calculate them by hand.
619 for (edge e
: EXIT_BLOCK_PTR_FOR_FN (m_fn
)->preds
)
621 basic_block bb
= e
->src
;
622 while (bb
!= bi
.exit_block_dominator
)
624 bitmap_set_bit (&frontiers
[bb
->index
], EXIT_BLOCK
);
625 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
629 // In extreme cases, the number of live-in registers can be much
630 // greater than the number of phi nodes needed in a block (see PR98863).
631 // Try to reduce the number of operations involving live-in sets by using
632 // PENDING as a staging area: registers in PENDING need phi nodes if
633 // they are live on entry to the corresponding block, but do not need
634 // phi nodes otherwise.
635 auto_vec
<bitmap_head
> unfiltered
;
636 unfiltered
.safe_grow_cleared (num_bb_indices
);
637 for (unsigned int i
= 0; i
< num_bb_indices
; ++i
)
638 bitmap_initialize (&unfiltered
[i
], &bitmap_default_obstack
);
640 // If block B1 defines R and if B2 is in the dominance frontier of B1,
641 // queue a possible phi node for R in B2.
642 auto_bitmap worklist
;
643 for (unsigned int b1
= 0; b1
< num_bb_indices
; ++b1
)
645 // Only access DF information for blocks that are known to exist.
646 if (bitmap_empty_p (&frontiers
[b1
]))
649 // Defs in B1 that are possibly in LR_IN in the dominance frontier
652 bitmap_and (b1_def
, &DF_LR_BB_INFO (BASIC_BLOCK_FOR_FN (m_fn
, b1
))->def
,
653 DF_LR_OUT (BASIC_BLOCK_FOR_FN (m_fn
, b1
)));
657 EXECUTE_IF_SET_IN_BITMAP (&frontiers
[b1
], 0, b2
, bmi
)
658 if (bitmap_ior_into (&unfiltered
[b2
], b1_def
)
659 && !bitmap_empty_p (&frontiers
[b2
]))
660 // Propagate the (potential) new phi node definitions in B2.
661 bitmap_set_bit (worklist
, b2
);
664 while (!bitmap_empty_p (worklist
))
666 unsigned int b1
= bitmap_first_set_bit (worklist
);
667 bitmap_clear_bit (worklist
, b1
);
669 // Restrict the phi nodes to registers that are live on entry to
671 bitmap b1_in
= DF_LR_IN (BASIC_BLOCK_FOR_FN (m_fn
, b1
));
672 bitmap b1_phis
= &bi
.bb_phis
[b1
].regs
;
673 if (!bitmap_ior_and_into (b1_phis
, &unfiltered
[b1
], b1_in
))
676 // If block B1 has a phi node for R and if B2 is in the dominance
677 // frontier of B1, queue a possible phi node for R in B2.
680 EXECUTE_IF_SET_IN_BITMAP (&frontiers
[b1
], 0, b2
, bmi
)
681 if (bitmap_ior_into (&unfiltered
[b2
], b1_phis
)
682 && !bitmap_empty_p (&frontiers
[b2
]))
683 bitmap_set_bit (worklist
, b2
);
687 FOR_ALL_BB_FN (cfg_bb
, m_fn
)
689 // Calculate the set of phi nodes for blocks that don't have any
690 // dominance frontiers. We only need to do this once per block.
691 unsigned int i
= cfg_bb
->index
;
692 bb_phi_info
&phis
= bi
.bb_phis
[i
];
693 if (bitmap_empty_p (&frontiers
[i
]))
694 bitmap_and (&phis
.regs
, &unfiltered
[i
], DF_LR_IN (cfg_bb
));
696 // Create an array that contains all phi inputs for this block.
697 // See the comment above the member variables for more information.
698 phis
.num_phis
= bitmap_count_bits (&phis
.regs
);
699 phis
.num_preds
= EDGE_COUNT (cfg_bb
->preds
);
700 unsigned int num_inputs
= phis
.num_phis
* phis
.num_preds
;
703 phis
.inputs
= XOBNEWVEC (&m_temp_obstack
, set_info
*, num_inputs
);
704 memset (phis
.inputs
, 0, num_inputs
* sizeof (phis
.inputs
[0]));
708 // Free the temporary bitmaps.
709 for (unsigned int i
= 0; i
< num_bb_indices
; ++i
)
711 bitmap_release (&frontiers
[i
]);
712 bitmap_release (&unfiltered
[i
]);
716 // Called while building SSA form using BI, with BI.current_bb being
719 // Create the entry block instructions and their definitions. The only
720 // useful instruction is the end instruction, which carries definitions
721 // for the values that are live on entry to the function. However, it
722 // seems simpler to create a head instruction too, rather than force all
723 // users of the block information to treat the entry block as a special case.
725 function_info::add_entry_block_defs (build_info
&bi
)
727 bb_info
*bb
= bi
.current_bb
;
728 basic_block cfg_bb
= bi
.current_bb
->cfg_bb ();
729 auto *lr_info
= DF_LR_BB_INFO (cfg_bb
);
731 bb
->set_head_insn (append_artificial_insn (bb
));
732 insn_info
*insn
= append_artificial_insn (bb
);
733 bb
->set_end_insn (insn
);
735 start_insn_accesses ();
737 // Using LR to derive the liveness information means that we create an
738 // entry block definition for upwards exposed registers. These registers
739 // are sometimes genuinely uninitialized. However, some targets also
740 // create a pseudo PIC base register and only initialize it later.
741 // Handling that case correctly seems more important than optimizing
742 // uninitialized uses.
744 bitmap_iterator in_bi
;
745 EXECUTE_IF_SET_IN_BITMAP (&lr_info
->out
, 0, regno
, in_bi
)
747 auto *set
= allocate
<set_info
> (insn
, full_register (regno
));
749 m_temp_defs
.safe_push (set
);
750 bi
.record_reg_def (set
);
753 // Create a definition that reflects the state of memory on entry to
755 auto *set
= allocate
<set_info
> (insn
, memory
);
757 m_temp_defs
.safe_push (set
);
758 bi
.record_mem_def (set
);
760 finish_insn_accesses (insn
);
763 // Lazily calculate the value of BI.ebb_live_in_for_debug for BI.current_ebb.
765 function_info::calculate_ebb_live_in_for_debug (build_info
&bi
)
767 gcc_checking_assert (bitmap_empty_p (bi
.tmp_ebb_live_in_for_debug
));
768 bi
.ebb_live_in_for_debug
= bi
.tmp_ebb_live_in_for_debug
;
769 bitmap_and (bi
.ebb_live_in_for_debug
, bi
.potential_phi_regs_for_debug
,
770 DF_LR_IN (bi
.current_ebb
->first_bb ()->cfg_bb ()));
771 bitmap_tree_view (bi
.ebb_live_in_for_debug
);
774 // Called while building SSA form using BI. Create phi nodes for the
777 function_info::add_phi_nodes (build_info
&bi
)
779 ebb_info
*ebb
= bi
.current_ebb
;
780 basic_block cfg_bb
= ebb
->first_bb ()->cfg_bb ();
782 // Create the register phis for this EBB.
783 bb_phi_info
&phis
= bi
.bb_phis
[cfg_bb
->index
];
784 unsigned int num_preds
= phis
.num_preds
;
786 bitmap_iterator in_bi
;
787 EXECUTE_IF_SET_IN_BITMAP (&phis
.regs
, 0, regno
, in_bi
)
789 gcc_checking_assert (bitmap_bit_p (bi
.potential_phi_regs
, regno
));
791 // Create an array of phi inputs, to be filled in later.
792 auto *inputs
= XOBNEWVEC (&m_obstack
, access_info
*, num_preds
);
793 memset (inputs
, 0, sizeof (access_info
*) * num_preds
);
795 // Later code works out the correct mode of the phi. Use BLKmode
796 // as a placeholder for now.
797 phi_info
*phi
= create_phi (ebb
, { E_BLKmode
, regno
},
799 bi
.record_reg_def (phi
);
802 bitmap_copy (bi
.ebb_def_regs
, &phis
.regs
);
804 // Collect the live-in memory definitions and record whether they're
806 m_temp_defs
.reserve (num_preds
);
807 set_info
*mem_value
= nullptr;
808 bool mem_phi_is_degenerate
= true;
811 FOR_EACH_EDGE (e
, ei
, cfg_bb
->preds
)
813 bb_info
*pred_bb
= this->bb (e
->src
);
814 if (pred_bb
&& pred_bb
->head_insn ())
816 mem_value
= bi
.bb_mem_live_out
[pred_bb
->index ()];
817 m_temp_defs
.quick_push (mem_value
);
818 if (mem_value
!= m_temp_defs
[0])
819 mem_phi_is_degenerate
= false;
823 m_temp_defs
.quick_push (nullptr);
824 mem_phi_is_degenerate
= false;
828 // Create a phi for memory, on the assumption that something in the
830 if (mem_phi_is_degenerate
)
832 access_info
*input
[] = { mem_value
};
833 mem_value
= create_phi (ebb
, memory
, input
, 1);
837 obstack_grow (&m_obstack
, m_temp_defs
.address (),
838 num_preds
* sizeof (access_info
*));
839 auto *inputs
= static_cast<access_info
**> (obstack_finish (&m_obstack
));
840 mem_value
= create_phi (ebb
, memory
, inputs
, num_preds
);
842 bi
.record_mem_def (mem_value
);
843 m_temp_defs
.truncate (0);
846 // Called while building SSA form using BI.
848 // If FLAGS is DF_REF_AT_TOP, create the head insn for BI.current_bb
849 // and populate its uses and definitions. If FLAGS is 0, do the same
852 function_info::add_artificial_accesses (build_info
&bi
, df_ref_flags flags
)
854 bb_info
*bb
= bi
.current_bb
;
855 basic_block cfg_bb
= bb
->cfg_bb ();
856 auto *lr_info
= DF_LR_BB_INFO (cfg_bb
);
860 if (flags
== DF_REF_AT_TOP
)
862 if (cfg_bb
->index
== EXIT_BLOCK
)
863 insn
= append_artificial_insn (bb
);
865 insn
= append_artificial_insn (bb
, bb_note (cfg_bb
));
866 bb
->set_head_insn (insn
);
870 insn
= append_artificial_insn (bb
);
871 bb
->set_end_insn (insn
);
874 start_insn_accesses ();
876 HARD_REG_SET added_regs
= {};
877 FOR_EACH_ARTIFICIAL_USE (ref
, cfg_bb
->index
)
878 if ((DF_REF_FLAGS (ref
) & DF_REF_AT_TOP
) == flags
)
880 unsigned int regno
= DF_REF_REGNO (ref
);
881 machine_mode mode
= GET_MODE (DF_REF_REAL_REG (ref
));
882 if (HARD_REGISTER_NUM_P (regno
))
883 SET_HARD_REG_BIT (added_regs
, regno
);
885 // A definition must be available.
886 gcc_checking_assert (bitmap_bit_p (&lr_info
->in
, regno
)
887 || (flags
!= DF_REF_AT_TOP
888 && bitmap_bit_p (&lr_info
->def
, regno
)));
889 m_temp_uses
.safe_push (create_reg_use (bi
, insn
, { mode
, regno
}));
892 // Ensure that global registers and memory are live at the end of any
893 // block that has no successors, such as the exit block and non-local gotos.
894 // Global registers have to be singled out because they are not part of
895 // the DF artifical use list (they are instead treated as used within
897 if (flags
== 0 && EDGE_COUNT (cfg_bb
->succs
) == 0)
899 for (unsigned int i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
900 if (global_regs
[i
] && !TEST_HARD_REG_BIT (added_regs
, i
))
902 auto mode
= reg_raw_mode
[i
];
903 m_temp_uses
.safe_push (create_reg_use (bi
, insn
, { mode
, i
}));
906 auto *use
= allocate
<use_info
> (insn
, memory
, bi
.current_mem_value ());
908 m_temp_uses
.safe_push (use
);
911 FOR_EACH_ARTIFICIAL_DEF (ref
, cfg_bb
->index
)
912 if ((DF_REF_FLAGS (ref
) & DF_REF_AT_TOP
) == flags
)
914 unsigned int regno
= DF_REF_REGNO (ref
);
915 machine_mode mode
= GET_MODE (DF_REF_REAL_REG (ref
));
916 resource_info resource
{ mode
, regno
};
918 // We rely on the def set being correct.
919 gcc_checking_assert (bitmap_bit_p (&lr_info
->def
, regno
));
921 // If the value isn't used later in the block and isn't live
922 // on exit, we could instead represent the definition as a
923 // clobber_info. However, that case should be relatively
924 // rare and set_info is any case more compact than clobber_info.
925 set_info
*def
= allocate
<set_info
> (insn
, resource
);
927 m_temp_defs
.safe_push (def
);
928 bi
.record_reg_def (def
);
931 // Model the effect of a memory clobber on an incoming edge by adding
932 // a fake definition of memory at the start of the block. We don't need
933 // to add a use of the phi node because memory is implicitly always live.
934 if (flags
== DF_REF_AT_TOP
&& has_abnormal_call_or_eh_pred_edge_p (cfg_bb
))
936 set_info
*def
= allocate
<set_info
> (insn
, memory
);
938 m_temp_defs
.safe_push (def
);
939 bi
.record_mem_def (def
);
942 finish_insn_accesses (insn
);
945 // Called while building SSA form using BI. Create insn_infos for all
946 // relevant instructions in BI.current_bb.
948 function_info::add_block_contents (build_info
&bi
)
950 basic_block cfg_bb
= bi
.current_bb
->cfg_bb ();
952 FOR_BB_INSNS (cfg_bb
, insn
)
954 add_insn_to_block (bi
, insn
);
957 // Called while building SSA form using BI. Record live-out register values
958 // in the phi inputs of successor blocks and create live-out uses where
959 // appropriate. Record the live-out memory value in BI.bb_mem_live_out.
961 function_info::record_block_live_out (build_info
&bi
)
963 bb_info
*bb
= bi
.current_bb
;
964 ebb_info
*ebb
= bi
.current_ebb
;
965 basic_block cfg_bb
= bb
->cfg_bb ();
967 // Record the live-out register values in the phi inputs of
971 FOR_EACH_EDGE (e
, ei
, cfg_bb
->succs
)
973 bb_phi_info
&phis
= bi
.bb_phis
[e
->dest
->index
];
974 unsigned int input_i
= e
->dest_idx
* phis
.num_phis
;
976 bitmap_iterator out_bi
;
977 EXECUTE_IF_SET_IN_BITMAP (&phis
.regs
, 0, regno
, out_bi
)
980 = live_out_value (bb
, bi
.current_reg_value (regno
));
985 // Add the set of registers that were defined in this BB to the set
986 // of potentially-live registers defined in the EBB.
987 bitmap_ior_into (bi
.ebb_def_regs
, &DF_LR_BB_INFO (cfg_bb
)->def
);
989 // Iterate through the registers in LIVE_OUT and see whether we need
990 // to add a live-out use for them.
991 auto record_live_out_regs
= [&](bitmap live_out
)
994 bitmap_iterator out_bi
;
995 EXECUTE_IF_AND_IN_BITMAP (bi
.ebb_def_regs
, live_out
, 0, regno
, out_bi
)
997 set_info
*value
= live_out_value (bb
, bi
.current_reg_value (regno
));
998 if (value
&& value
->ebb () == ebb
)
999 add_live_out_use (bb
, value
);
1003 if (bb
== ebb
->last_bb ())
1004 // All live-out registers might need live-out uses.
1005 record_live_out_regs (DF_LR_OUT (cfg_bb
));
1007 // Registers might need live-out uses if they are live on entry
1008 // to a successor block in a different EBB.
1009 FOR_EACH_EDGE (e
, ei
, cfg_bb
->succs
)
1011 bb_info
*dest_bb
= this->bb (e
->dest
);
1012 if (dest_bb
->ebb () != ebb
|| dest_bb
== ebb
->first_bb ())
1013 record_live_out_regs (DF_LR_IN (e
->dest
));
1016 // Record the live-out memory value.
1017 bi
.bb_mem_live_out
[cfg_bb
->index
]
1018 = live_out_value (bb
, bi
.current_mem_value ());
1021 // Add BB and its contents to the SSA information.
1023 function_info::start_block (build_info
&bi
, bb_info
*bb
)
1025 ebb_info
*ebb
= bb
->ebb ();
1027 // We (need to) add all blocks from one EBB before moving on to the next.
1029 if (bb
== ebb
->first_bb ())
1030 bi
.current_ebb
= ebb
;
1032 gcc_assert (bi
.current_ebb
== ebb
);
1034 // Record the start of this block's definitions in the definitions stack.
1035 bi
.old_def_stack_limit
.safe_push (bi
.def_stack
.length ());
1037 // Add the block itself.
1040 // If the block starts an EBB, create the phi insn. This insn should exist
1041 // for all EBBs, even if they don't (yet) need phis.
1042 if (bb
== ebb
->first_bb ())
1043 ebb
->set_phi_insn (append_artificial_insn (bb
));
1045 if (bb
->index () == ENTRY_BLOCK
)
1047 add_entry_block_defs (bi
);
1048 record_block_live_out (bi
);
1052 if (EDGE_COUNT (bb
->cfg_bb ()->preds
) == 0)
1054 // Leave unreachable blocks empty, since there is no useful
1055 // liveness information for them, and anything they do will
1056 // be wasted work. In a cleaned-up cfg, the only unreachable
1057 // block we should see is the exit block of a noreturn function.
1058 bb
->set_head_insn (append_artificial_insn (bb
));
1059 bb
->set_end_insn (append_artificial_insn (bb
));
1063 // If the block starts an EBB, create the phi nodes.
1064 if (bb
== ebb
->first_bb ())
1067 // Process the contents of the block.
1068 add_artificial_accesses (bi
, DF_REF_AT_TOP
);
1069 if (bb
->index () != EXIT_BLOCK
)
1070 add_block_contents (bi
);
1071 add_artificial_accesses (bi
, df_ref_flags ());
1072 record_block_live_out (bi
);
1074 // If we needed to calculate a live-in set for debug purposes,
1075 // reset it to null at the end of the EBB. Convert the underlying
1076 // bitmap to an empty list view, ready for the next calculation.
1077 if (bi
.ebb_live_in_for_debug
&& bb
== ebb
->last_bb ())
1079 bitmap_clear (bi
.tmp_ebb_live_in_for_debug
);
1080 bitmap_list_view (bi
.tmp_ebb_live_in_for_debug
);
1081 bi
.ebb_live_in_for_debug
= nullptr;
1085 // Finish adding BB and the blocks that it dominates to the SSA information.
1087 function_info::end_block (build_info
&bi
, bb_info
*bb
)
1089 // Restore the register last_access information to the state it was
1090 // in before we started processing BB.
1091 unsigned int old_limit
= bi
.old_def_stack_limit
.pop ();
1092 while (bi
.def_stack
.length () > old_limit
)
1094 // We pushed a definition in BB if it was the first dominating
1095 // definition (and so the previous entry was null). In other
1096 // cases we pushed the previous dominating definition.
1097 def_info
*def
= bi
.def_stack
.pop ();
1098 unsigned int regno
= def
->regno ();
1099 if (def
->bb () == bb
)
1101 bi
.last_access
[regno
+ 1] = def
;
1105 // Finish setting up the phi nodes for each block, now that we've added
1106 // the contents of all blocks.
1108 function_info::populate_phi_inputs (build_info
&bi
)
1110 auto_vec
<phi_info
*, 32> sorted_phis
;
1111 for (ebb_info
*ebb
: ebbs ())
1113 if (!ebb
->first_phi ())
1116 // Get a sorted array of EBB's phi nodes.
1117 basic_block cfg_bb
= ebb
->first_bb ()->cfg_bb ();
1118 bb_phi_info
&phis
= bi
.bb_phis
[cfg_bb
->index
];
1119 sorted_phis
.truncate (0);
1120 for (phi_info
*phi
: ebb
->phis ())
1121 sorted_phis
.safe_push (phi
);
1122 std::sort (sorted_phis
.address (),
1123 sorted_phis
.address () + sorted_phis
.length (),
1124 compare_access_infos
);
1126 // Set the inputs of the non-degenerate register phis. All inputs
1127 // for one edge come before all inputs for the next edge.
1128 set_info
**inputs
= phis
.inputs
;
1129 unsigned int phi_i
= 0;
1130 bitmap_iterator bmi
;
1132 EXECUTE_IF_SET_IN_BITMAP (&phis
.regs
, 0, regno
, bmi
)
1134 // Skip intervening degenerate phis.
1135 while (sorted_phis
[phi_i
]->regno () < regno
)
1137 phi_info
*phi
= sorted_phis
[phi_i
];
1138 gcc_assert (phi
->regno () == regno
);
1139 for (unsigned int input_i
= 0; input_i
< phis
.num_preds
; ++input_i
)
1140 if (set_info
*input
= inputs
[input_i
* phis
.num_phis
])
1142 use_info
*use
= phi
->input_use (input_i
);
1143 gcc_assert (!use
->def ());
1144 use
->set_def (input
);
1151 // Fill in the backedge inputs to any memory phi.
1152 phi_info
*mem_phi
= sorted_phis
.last ();
1153 if (mem_phi
->is_mem () && !mem_phi
->is_degenerate ())
1157 FOR_EACH_EDGE (e
, ei
, cfg_bb
->preds
)
1159 use_info
*use
= mem_phi
->input_use (e
->dest_idx
);
1162 use
->set_def (bi
.bb_mem_live_out
[e
->src
->index
]);
1170 // Return true if it would be better to continue an EBB across NEW_EDGE
1171 // rather than across OLD_EDGE, given that both edges are viable candidates.
1172 // This is not a total ordering.
1174 better_ebb_edge_p (edge new_edge
, edge old_edge
)
1176 // Prefer the likeliest edge.
1177 if (new_edge
->probability
.initialized_p ()
1178 && old_edge
->probability
.initialized_p ()
1179 && !(old_edge
->probability
== new_edge
->probability
))
1180 return old_edge
->probability
< new_edge
->probability
;
1182 // If both edges are equally likely, prefer a fallthru edge.
1183 if (new_edge
->flags
& EDGE_FALLTHRU
)
1185 if (old_edge
->flags
& EDGE_FALLTHRU
)
1188 // Otherwise just stick with OLD_EDGE.
1192 // Pick and return the next basic block in an EBB that currently ends with BB.
1193 // Return null if the EBB must end with BB.
1195 choose_next_block_in_ebb (basic_block bb
)
1197 // Although there's nothing in principle wrong with having an EBB that
1198 // starts with the entry block and includes later blocks, there's not
1199 // really much point either. Keeping the entry block separate means
1200 // that uses of arguments consistently occur through phi nodes, rather
1201 // than the arguments sometimes appearing to come from an EBB-local
1202 // definition instead.
1203 if (bb
->index
== ENTRY_BLOCK
)
1206 bool optimize_for_speed_p
= optimize_bb_for_speed_p (bb
);
1207 edge best_edge
= nullptr;
1210 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1211 if (!(e
->flags
& EDGE_COMPLEX
)
1212 && e
->dest
->index
!= EXIT_BLOCK
1213 && single_pred_p (e
->dest
)
1214 && optimize_for_speed_p
== optimize_bb_for_speed_p (e
->dest
)
1215 && (!best_edge
|| better_ebb_edge_p (e
, best_edge
)))
1218 return best_edge
? best_edge
->dest
: nullptr;
1221 // Partition the function into extended basic blocks. Create the
1222 // associated ebb_infos and bb_infos, but don't add the bb_infos
1223 // to the function list yet.
1225 function_info::create_ebbs (build_info
&bi
)
1227 // Compute the starting reverse postorder. We tweak this later to try
1228 // to get better EBB assignments.
1229 auto *postorder
= new int[n_basic_blocks_for_fn (m_fn
)];
1230 unsigned int postorder_num
1231 = pre_and_rev_post_order_compute (nullptr, postorder
, true);
1232 gcc_assert (int (postorder_num
) <= n_basic_blocks_for_fn (m_fn
));
1234 // Iterate over the blocks in reverse postorder. In cases where
1235 // multiple possible orders exist, prefer orders that chain blocks
1236 // together into EBBs. If multiple possible EBBs exist, try to pick
1237 // the ones that are most likely to be profitable.
1238 auto_vec
<bb_info
*, 16> bbs
;
1239 unsigned int next_bb_index
= 0;
1240 for (unsigned int i
= 0; i
< postorder_num
; ++i
)
1241 if (!m_bbs
[postorder
[i
]])
1243 // Choose and create the blocks that should form the next EBB.
1244 basic_block cfg_bb
= BASIC_BLOCK_FOR_FN (m_fn
, postorder
[i
]);
1247 // Record the chosen block order in a new RPO.
1248 bi
.bb_to_rpo
[cfg_bb
->index
] = next_bb_index
++;
1249 bbs
.safe_push (create_bb_info (cfg_bb
));
1250 cfg_bb
= choose_next_block_in_ebb (cfg_bb
);
1254 // Create the EBB itself.
1255 auto *ebb
= allocate
<ebb_info
> (bbs
[0], bbs
.last ());
1256 for (bb_info
*bb
: bbs
)
1264 // Partition the function's blocks into EBBs and build SSA form for all
1265 // EBBs in the function.
1267 function_info::process_all_blocks ()
1269 auto temps
= temp_watermark ();
1270 unsigned int num_bb_indices
= last_basic_block_for_fn (m_fn
);
1272 build_info
bi (m_num_regs
, num_bb_indices
);
1274 // ??? There is no dominance information associated with the exit block,
1275 // so work out its immediate dominator using predecessor blocks.
1276 for (edge e
: EXIT_BLOCK_PTR_FOR_FN (m_fn
)->preds
)
1277 if (bi
.exit_block_dominator
)
1278 bi
.exit_block_dominator
1279 = nearest_common_dominator (CDI_DOMINATORS
,
1280 bi
.exit_block_dominator
, e
->src
);
1282 bi
.exit_block_dominator
= e
->src
;
1284 calculate_potential_phi_regs (bi
);
1287 bb_walker (this, bi
).walk (ENTRY_BLOCK_PTR_FOR_FN (m_fn
));
1288 populate_phi_inputs (bi
);
1292 // The definition stack should be empty and all register definitions
1293 // should be back in their original undefined state.
1294 gcc_assert (bi
.def_stack
.is_empty ()
1295 && bi
.old_def_stack_limit
.is_empty ());
1296 for (unsigned int regno
= 0; regno
< m_num_regs
; ++regno
)
1297 gcc_assert (!bi
.last_access
[regno
+ 1]);
1301 // Print a description of CALL_CLOBBERS to PP.
1303 rtl_ssa::pp_ebb_call_clobbers (pretty_printer
*pp
,
1304 const ebb_call_clobbers_info
*call_clobbers
)
1307 pp_string (pp
, "<null>");
1309 call_clobbers
->print_full (pp
);
1312 // Print a description of BB to PP.
1314 rtl_ssa::pp_bb (pretty_printer
*pp
, const bb_info
*bb
)
1317 pp_string (pp
, "<null>");
1319 bb
->print_full (pp
);
1322 // Print a description of EBB to PP
1324 rtl_ssa::pp_ebb (pretty_printer
*pp
, const ebb_info
*ebb
)
1327 pp_string (pp
, "<null>");
1329 ebb
->print_full (pp
);
1332 // Print a description of CALL_CLOBBERS to FILE.
1334 dump (FILE *file
, const ebb_call_clobbers_info
*call_clobbers
)
1336 dump_using (file
, pp_ebb_call_clobbers
, call_clobbers
);
1339 // Print a description of BB to FILE.
1341 dump (FILE *file
, const bb_info
*bb
)
1343 dump_using (file
, pp_bb
, bb
);
1346 // Print a description of EBB to FILE.
1348 dump (FILE *file
, const ebb_info
*ebb
)
1350 dump_using (file
, pp_ebb
, ebb
);
1353 // Debug interfaces to the dump routines above.
1354 void debug (const ebb_call_clobbers_info
*x
) { dump (stderr
, x
); }
1355 void debug (const bb_info
*x
) { dump (stderr
, x
); }
1356 void debug (const ebb_info
*x
) { dump (stderr
, x
); }