1 // Implementation of basic-block-related functions for RTL SSA -*- C++ -*-
2 // Copyright (C) 2020-2023 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
24 #include "coretypes.h"
29 #include "rtl-ssa/internals.h"
30 #include "rtl-ssa/internals.inl"
36 using namespace rtl_ssa
;
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
41 function_info::build_info::build_info (unsigned int num_regs
,
42 unsigned int num_bb_indices
)
43 : current_bb (nullptr),
44 current_ebb (nullptr),
45 last_access (num_regs
+ 1),
46 ebb_live_in_for_debug (nullptr),
47 potential_phi_regs (num_regs
),
48 bb_phis (num_bb_indices
),
49 bb_mem_live_out (num_bb_indices
),
50 bb_to_rpo (num_bb_indices
),
51 exit_block_dominator (nullptr)
53 last_access
.safe_grow_cleared (num_regs
+ 1);
55 bitmap_clear (potential_phi_regs
);
57 // These arrays shouldn't need to be initialized, since we'll always
58 // write to an entry before reading from it. But poison the contents
59 // when checking, just to make sure we don't accidentally use an
60 // uninitialized value.
61 bb_phis
.quick_grow_cleared (num_bb_indices
);
62 bb_mem_live_out
.quick_grow (num_bb_indices
);
63 bb_to_rpo
.quick_grow (num_bb_indices
);
66 // Can't do this for bb_phis because it has a constructor.
67 memset (bb_mem_live_out
.address (), 0xaf,
68 num_bb_indices
* sizeof (bb_mem_live_out
[0]));
69 memset (bb_to_rpo
.address (), 0xaf,
70 num_bb_indices
* sizeof (bb_to_rpo
[0]));
73 // Start off with an empty set of phi nodes for each block.
74 for (bb_phi_info
&info
: bb_phis
)
75 bitmap_initialize (&info
.regs
, &bitmap_default_obstack
);
78 function_info::build_info::~build_info ()
80 for (bb_phi_info
&info
: bb_phis
)
81 bitmap_release (&info
.regs
);
84 // A dom_walker for populating the basic blocks.
85 class function_info::bb_walker
: public dom_walker
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
;
93 // Information about the function we're building.
94 function_info
*m_function
;
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
;
102 // Prepare to walk the blocks in FUNCTION using BI.
103 function_info::bb_walker::bb_walker (function_info
*function
, build_info
&bi
)
104 : dom_walker (CDI_DOMINATORS
, ALL_BLOCKS
, bi
.bb_to_rpo
.address ()),
105 m_function (function
),
107 m_exit_block_dominator (bi
.exit_block_dominator
)
109 // If the exit block is unreachable, process it last.
110 if (!m_exit_block_dominator
)
111 m_exit_block_dominator
= ENTRY_BLOCK_PTR_FOR_FN (m_function
->m_fn
);
115 function_info::bb_walker::before_dom_children (basic_block bb
)
117 m_function
->start_block (m_bi
, m_function
->bb (bb
));
122 function_info::bb_walker::after_dom_children (basic_block bb
)
124 // See the comment in the constructor for details.
125 if (bb
== m_exit_block_dominator
)
127 before_dom_children (EXIT_BLOCK_PTR_FOR_FN (m_function
->m_fn
));
128 after_dom_children (EXIT_BLOCK_PTR_FOR_FN (m_function
->m_fn
));
130 m_function
->end_block (m_bi
, m_function
->bb (bb
));
133 // See the comment above the declaration.
135 bb_info::print_identifier (pretty_printer
*pp
) const
137 char tmp
[3 * sizeof (index ()) + 3];
138 snprintf (tmp
, sizeof (tmp
), "bb%d", index ());
140 if (ebb_info
*ebb
= this->ebb ())
143 pp_left_bracket (pp
);
144 ebb
->print_identifier (pp
);
145 pp_right_bracket (pp
);
149 // See the comment above the declaration.
151 bb_info::print_full (pretty_printer
*pp
) const
153 pp_string (pp
, "basic block ");
154 print_identifier (pp
);
157 auto print_insn
= [pp
](const char *header
, const insn_info
*insn
)
159 pp_newline_and_indent (pp
, 2);
160 pp_string (pp
, header
);
161 pp_newline_and_indent (pp
, 2);
165 pp_string (pp
, "<uninitialized>");
166 pp_indentation (pp
) -= 4;
169 print_insn ("head:", head_insn ());
172 pp_newline_and_indent (pp
, 2);
173 pp_string (pp
, "contents:");
176 pp_newline_and_indent (pp
, 2);
177 pp_string (pp
, "<uninitialized>");
178 pp_indentation (pp
) -= 2;
180 else if (auto insns
= real_insns ())
182 bool is_first
= true;
183 for (const insn_info
*insn
: insns
)
189 pp_newline_and_indent (pp
, 2);
191 pp_indentation (pp
) -= 2;
196 pp_newline_and_indent (pp
, 2);
197 pp_string (pp
, "none");
198 pp_indentation (pp
) -= 2;
200 pp_indentation (pp
) -= 2;
203 print_insn ("end:", end_insn ());
206 // See the comment above the declaration.
208 ebb_call_clobbers_info::print_summary (pretty_printer
*pp
) const
210 pp_string (pp
, "call clobbers for ABI ");
212 pp_decimal_int (pp
, m_abi
->id ());
214 pp_string (pp
, "<null>");
217 // See the comment above the declaration.
219 ebb_call_clobbers_info::print_full (pretty_printer
*pp
) const
223 pp_newline_and_indent (pp
, 2);
224 auto print_node
= [](pretty_printer
*pp
,
225 const insn_call_clobbers_note
*note
)
227 if (insn_info
*insn
= note
->insn ())
228 insn
->print_identifier_and_location (pp
);
230 pp_string (pp
, "<null>");
232 print (pp
, root (), print_node
);
233 pp_indentation (pp
) -= 2;
236 // See the comment above the declaration.
238 ebb_info::print_identifier (pretty_printer
*pp
) const
240 // first_bb is populated by the constructor and so should always
242 auto index
= first_bb ()->index ();
243 char tmp
[3 * sizeof (index
) + 4];
244 snprintf (tmp
, sizeof (tmp
), "ebb%d", index
);
248 // See the comment above the declaration.
250 ebb_info::print_full (pretty_printer
*pp
) const
252 pp_string (pp
, "extended basic block ");
253 print_identifier (pp
);
256 pp_newline_and_indent (pp
, 2);
257 if (insn_info
*phi_insn
= this->phi_insn ())
259 phi_insn
->print_identifier_and_location (pp
);
261 if (auto phis
= this->phis ())
263 bool is_first
= true;
264 for (const phi_info
*phi
: phis
)
270 pp_newline_and_indent (pp
, 2);
271 pp_access (pp
, phi
, PP_ACCESS_SETTER
);
272 pp_indentation (pp
) -= 2;
277 pp_newline_and_indent (pp
, 2);
278 pp_string (pp
, "no phi nodes");
279 pp_indentation (pp
) -= 2;
283 pp_string (pp
, "no phi insn");
284 pp_indentation (pp
) -= 2;
286 for (const bb_info
*bb
: bbs ())
289 pp_newline_and_indent (pp
, 2);
291 pp_indentation (pp
) -= 2;
294 for (ebb_call_clobbers_info
*ecc
: call_clobbers ())
297 pp_newline_and_indent (pp
, 2);
298 pp_ebb_call_clobbers (pp
, ecc
);
299 pp_indentation (pp
) -= 2;
303 // Add a dummy use to mark that DEF is live out of BB's EBB at the end of BB.
305 function_info::add_live_out_use (bb_info
*bb
, set_info
*def
)
307 // There is nothing to do if DEF is an artificial definition at the end
308 // of BB. In that case the definitino is rooted at the end of the block
309 // and we wouldn't gain anything by inserting a use immediately after it.
310 // If we did want to insert a use, we'd need to associate it with a new
311 // instruction that comes after bb->end_insn ().
312 if (def
->insn () == bb
->end_insn ())
315 // If the end of the block already has an artificial use, that use
316 // acts to make DEF live at the appropriate point.
317 use_info
*use
= def
->last_nondebug_insn_use ();
318 if (use
&& use
->insn () == bb
->end_insn ())
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
325 use
= allocate
<use_info
> (bb
->end_insn (), def
->resource (), def
);
326 use
->set_is_live_out_use (true);
330 // Return true if all nondebug uses of DEF are live-out uses.
332 all_uses_are_live_out_uses (set_info
*def
)
334 for (use_info
*use
: def
->all_uses ())
335 if (!use
->is_in_debug_insn () && !use
->is_live_out_use ())
340 // SET, if nonnull, is a definition of something that is live out from BB.
341 // Return the live-out value itself.
343 function_info::live_out_value (bb_info
*bb
, set_info
*set
)
345 // Degenerate phis only exist to provide a definition for uses in the
346 // same EBB. The live-out value is the same as the live-in value.
347 if (auto *phi
= safe_dyn_cast
<phi_info
*> (set
))
348 if (phi
->is_degenerate ())
350 set
= phi
->input_value (0);
352 // Remove the phi if it turned out to be useless. This is
353 // mainly useful for memory, because we don't know ahead of time
354 // whether a block will use memory or not.
355 if (bb
== bb
->ebb ()->last_bb () && all_uses_are_live_out_uses (phi
))
356 replace_phi (phi
, set
);
362 // Add PHI to EBB and enter it into the function's hash table.
364 function_info::append_phi (ebb_info
*ebb
, phi_info
*phi
)
366 phi_info
*first_phi
= ebb
->first_phi ();
368 first_phi
->set_prev_phi (phi
);
369 phi
->set_next_phi (first_phi
);
370 ebb
->set_first_phi (phi
);
374 // Remove PHI from its current position in the SSA graph.
376 function_info::remove_phi (phi_info
*phi
)
378 phi_info
*next
= phi
->next_phi ();
379 phi_info
*prev
= phi
->prev_phi ();
382 next
->set_prev_phi (prev
);
385 prev
->set_next_phi (next
);
387 phi
->ebb ()->set_first_phi (next
);
390 phi
->clear_phi_links ();
393 // Remove PHI from the SSA graph and free its memory.
395 function_info::delete_phi (phi_info
*phi
)
397 gcc_assert (!phi
->has_any_uses ());
399 // Remove the inputs to the phi.
400 for (use_info
*input
: phi
->inputs ())
405 phi
->set_next_phi (m_free_phis
);
409 // If possible, remove PHI and replace all uses with NEW_VALUE.
411 function_info::replace_phi (phi_info
*phi
, set_info
*new_value
)
413 auto update_use
= [&](use_info
*use
)
416 use
->set_def (new_value
);
421 for (use_info
*use
: phi
->nondebug_insn_uses ())
422 if (!use
->is_live_out_use ())
424 // We need to keep the phi around for its local uses.
425 // Turn it into a degenerate phi, if it isn't already.
426 use_info
*use
= phi
->input_use (0);
427 if (use
->def () != new_value
)
430 if (phi
->is_degenerate ())
433 phi
->make_degenerate (use
);
435 // Redirect all phi users to NEW_VALUE.
436 while (use_info
*phi_use
= phi
->last_phi_use ())
437 update_use (phi_use
);
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
445 while (use_info
*use
= phi
->last_use ())
446 if (use
->is_live_out_use ())
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.
461 // Add the created phi node to its basic block and enter it into the
462 // function's hash table.
464 function_info::create_phi (ebb_info
*ebb
, resource_info resource
,
465 access_info
**inputs
, unsigned int num_inputs
)
467 phi_info
*phi
= m_free_phis
;
470 m_free_phis
= phi
->next_phi ();
471 *phi
= phi_info (ebb
->phi_insn (), resource
, phi
->uid ());
475 phi
= allocate
<phi_info
> (ebb
->phi_insn (), resource
, m_next_phi_uid
);
479 // Convert the array of set_infos into an array of use_infos. Also work
480 // out what mode the phi should have.
481 machine_mode new_mode
= resource
.mode
;
482 for (unsigned int i
= 0; i
< num_inputs
; ++i
)
484 auto *input
= safe_as_a
<set_info
*> (inputs
[i
]);
485 auto *use
= allocate
<use_info
> (phi
, resource
, input
);
489 new_mode
= combine_modes (new_mode
, input
->mode ());
492 phi
->set_inputs (use_array (inputs
, num_inputs
));
493 phi
->set_mode (new_mode
);
495 append_phi (ebb
, phi
);
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:
505 // (1) DEF was already live on entry to EBB but was previously transparent
508 // (2) DEF was not previously live on entry to EBB and is being made live
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.
514 function_info::create_degenerate_phi (ebb_info
*ebb
, set_info
*def
)
516 // Allow the function to be called twice in succession for the same def.
517 def_lookup dl
= find_def (def
->resource (), ebb
->phi_insn ());
518 if (set_info
*set
= dl
.matching_set ())
519 return as_a
<phi_info
*> (set
);
521 access_info
*input
= def
;
522 phi_info
*phi
= create_phi (ebb
, def
->resource (), &input
, 1);
525 unsigned int regno
= def
->regno ();
527 // Find the single predecessor mentioned above.
528 basic_block pred_cfg_bb
= single_pred (ebb
->first_bb ()->cfg_bb ());
529 bb_info
*pred_bb
= this->bb (pred_cfg_bb
);
531 if (!bitmap_set_bit (DF_LR_IN (ebb
->first_bb ()->cfg_bb ()), regno
))
533 // The register was not previously live on entry to EBB and
534 // might not have been live on exit from PRED_BB either.
535 if (bitmap_set_bit (DF_LR_OUT (pred_cfg_bb
), regno
))
536 add_live_out_use (pred_bb
, def
);
540 // The register was previously live in to EBB. Add live-out uses
541 // at the appropriate points.
542 insn_info
*next_insn
= nullptr;
543 if (def_info
*next_def
= phi
->next_def ())
544 next_insn
= next_def
->insn ();
545 for (bb_info
*bb
: ebb
->bbs ())
547 if ((next_insn
&& *next_insn
<= *bb
->end_insn ())
548 || !bitmap_bit_p (DF_LR_OUT (bb
->cfg_bb ()), regno
))
550 add_live_out_use (bb
, def
);
557 // Create a bb_info for CFG_BB, given that no such structure currently exists.
559 function_info::create_bb_info (basic_block cfg_bb
)
561 bb_info
*bb
= allocate
<bb_info
> (cfg_bb
);
562 gcc_checking_assert (!m_bbs
[cfg_bb
->index
]);
563 m_bbs
[cfg_bb
->index
] = bb
;
567 // Add BB to the end of the list of blocks.
569 function_info::append_bb (bb_info
*bb
)
572 m_last_bb
->set_next_bb (bb
);
575 bb
->set_prev_bb (m_last_bb
);
579 // Calculate BI.potential_phi_regs and BI.potential_phi_regs_for_debug.
581 function_info::calculate_potential_phi_regs (build_info
&bi
)
583 auto *lr_info
= DF_LR_BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (m_fn
));
584 bool is_debug
= MAY_HAVE_DEBUG_INSNS
;
585 for (unsigned int regno
= 0; regno
< m_num_regs
; ++regno
)
586 if (regno
>= DF_REG_SIZE (DF
)
587 // Exclude registers that have a single definition that dominates
588 // all uses. If the definition does not dominate all uses,
589 // the register will be exposed upwards to the entry block but
590 // will not be defined by the entry block.
591 || DF_REG_DEF_COUNT (regno
) > 1
592 || (!bitmap_bit_p (&lr_info
->def
, regno
)
593 && bitmap_bit_p (&lr_info
->out
, regno
)))
595 bitmap_set_bit (bi
.potential_phi_regs
, regno
);
597 bitmap_set_bit (bi
.potential_phi_regs_for_debug
, regno
);
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.
604 function_info::place_phis (build_info
&bi
)
606 unsigned int num_bb_indices
= last_basic_block_for_fn (m_fn
);
608 // Calculate dominance frontiers.
609 auto_vec
<bitmap_head
> frontiers
;
610 frontiers
.safe_grow_cleared (num_bb_indices
);
611 for (unsigned int i
= 0; i
< num_bb_indices
; ++i
)
612 bitmap_initialize (&frontiers
[i
], &bitmap_default_obstack
);
613 compute_dominance_frontiers (frontiers
.address ());
615 // The normal dominance information doesn't calculate dominators for
616 // the exit block, so we don't get dominance frontiers for them either.
617 // Calculate them by hand.
618 for (edge e
: EXIT_BLOCK_PTR_FOR_FN (m_fn
)->preds
)
620 basic_block bb
= e
->src
;
621 while (bb
!= bi
.exit_block_dominator
)
623 bitmap_set_bit (&frontiers
[bb
->index
], EXIT_BLOCK
);
624 bb
= get_immediate_dominator (CDI_DOMINATORS
, bb
);
628 // In extreme cases, the number of live-in registers can be much
629 // greater than the number of phi nodes needed in a block (see PR98863).
630 // Try to reduce the number of operations involving live-in sets by using
631 // PENDING as a staging area: registers in PENDING need phi nodes if
632 // they are live on entry to the corresponding block, but do not need
633 // phi nodes otherwise.
634 auto_vec
<bitmap_head
> unfiltered
;
635 unfiltered
.safe_grow_cleared (num_bb_indices
);
636 for (unsigned int i
= 0; i
< num_bb_indices
; ++i
)
637 bitmap_initialize (&unfiltered
[i
], &bitmap_default_obstack
);
639 // If block B1 defines R and if B2 is in the dominance frontier of B1,
640 // queue a possible phi node for R in B2.
641 auto_bitmap worklist
;
642 for (unsigned int b1
= 0; b1
< num_bb_indices
; ++b1
)
644 // Only access DF information for blocks that are known to exist.
645 if (bitmap_empty_p (&frontiers
[b1
]))
648 bitmap b1_def
= &DF_LR_BB_INFO (BASIC_BLOCK_FOR_FN (m_fn
, b1
))->def
;
651 EXECUTE_IF_SET_IN_BITMAP (&frontiers
[b1
], 0, b2
, bmi
)
652 if (bitmap_ior_into (&unfiltered
[b2
], b1_def
)
653 && !bitmap_empty_p (&frontiers
[b2
]))
654 // Propagate the (potential) new phi node definitions in B2.
655 bitmap_set_bit (worklist
, b2
);
658 while (!bitmap_empty_p (worklist
))
660 unsigned int b1
= bitmap_first_set_bit (worklist
);
661 bitmap_clear_bit (worklist
, b1
);
663 // Restrict the phi nodes to registers that are live on entry to
665 bitmap b1_in
= DF_LR_IN (BASIC_BLOCK_FOR_FN (m_fn
, b1
));
666 bitmap b1_phis
= &bi
.bb_phis
[b1
].regs
;
667 if (!bitmap_ior_and_into (b1_phis
, &unfiltered
[b1
], b1_in
))
670 // If block B1 has a phi node for R and if B2 is in the dominance
671 // frontier of B1, queue a possible phi node for R in B2.
674 EXECUTE_IF_SET_IN_BITMAP (&frontiers
[b1
], 0, b2
, bmi
)
675 if (bitmap_ior_into (&unfiltered
[b2
], b1_phis
)
676 && !bitmap_empty_p (&frontiers
[b2
]))
677 bitmap_set_bit (worklist
, b2
);
681 FOR_ALL_BB_FN (cfg_bb
, m_fn
)
683 // Calculate the set of phi nodes for blocks that don't have any
684 // dominance frontiers. We only need to do this once per block.
685 unsigned int i
= cfg_bb
->index
;
686 bb_phi_info
&phis
= bi
.bb_phis
[i
];
687 if (bitmap_empty_p (&frontiers
[i
]))
688 bitmap_and (&phis
.regs
, &unfiltered
[i
], DF_LR_IN (cfg_bb
));
690 // Create an array that contains all phi inputs for this block.
691 // See the comment above the member variables for more information.
692 phis
.num_phis
= bitmap_count_bits (&phis
.regs
);
693 phis
.num_preds
= EDGE_COUNT (cfg_bb
->preds
);
694 unsigned int num_inputs
= phis
.num_phis
* phis
.num_preds
;
697 phis
.inputs
= XOBNEWVEC (&m_temp_obstack
, set_info
*, num_inputs
);
698 memset (phis
.inputs
, 0, num_inputs
* sizeof (phis
.inputs
[0]));
702 // Free the temporary bitmaps.
703 for (unsigned int i
= 0; i
< num_bb_indices
; ++i
)
705 bitmap_release (&frontiers
[i
]);
706 bitmap_release (&unfiltered
[i
]);
710 // Called while building SSA form using BI, with BI.current_bb being
713 // Create the entry block instructions and their definitions. The only
714 // useful instruction is the end instruction, which carries definitions
715 // for the values that are live on entry to the function. However, it
716 // seems simpler to create a head instruction too, rather than force all
717 // users of the block information to treat the entry block as a special case.
719 function_info::add_entry_block_defs (build_info
&bi
)
721 bb_info
*bb
= bi
.current_bb
;
722 basic_block cfg_bb
= bi
.current_bb
->cfg_bb ();
723 auto *lr_info
= DF_LR_BB_INFO (cfg_bb
);
725 bb
->set_head_insn (append_artificial_insn (bb
));
726 insn_info
*insn
= append_artificial_insn (bb
);
727 bb
->set_end_insn (insn
);
729 start_insn_accesses ();
731 // Using LR to derive the liveness information means that we create an
732 // entry block definition for upwards exposed registers. These registers
733 // are sometimes genuinely uninitialized. However, some targets also
734 // create a pseudo PIC base register and only initialize it later.
735 // Handling that case correctly seems more important than optimizing
736 // uninitialized uses.
738 bitmap_iterator in_bi
;
739 EXECUTE_IF_SET_IN_BITMAP (&lr_info
->out
, 0, regno
, in_bi
)
741 auto *set
= allocate
<set_info
> (insn
, full_register (regno
));
743 m_temp_defs
.safe_push (set
);
744 bi
.record_reg_def (set
);
747 // Create a definition that reflects the state of memory on entry to
749 auto *set
= allocate
<set_info
> (insn
, memory
);
751 m_temp_defs
.safe_push (set
);
752 bi
.record_mem_def (set
);
754 finish_insn_accesses (insn
);
757 // Lazily calculate the value of BI.ebb_live_in_for_debug for BI.current_ebb.
759 function_info::calculate_ebb_live_in_for_debug (build_info
&bi
)
761 gcc_checking_assert (bitmap_empty_p (bi
.tmp_ebb_live_in_for_debug
));
762 bi
.ebb_live_in_for_debug
= bi
.tmp_ebb_live_in_for_debug
;
763 bitmap_and (bi
.ebb_live_in_for_debug
, bi
.potential_phi_regs_for_debug
,
764 DF_LR_IN (bi
.current_ebb
->first_bb ()->cfg_bb ()));
765 bitmap_tree_view (bi
.ebb_live_in_for_debug
);
768 // Called while building SSA form using BI. Create phi nodes for the
771 function_info::add_phi_nodes (build_info
&bi
)
773 ebb_info
*ebb
= bi
.current_ebb
;
774 basic_block cfg_bb
= ebb
->first_bb ()->cfg_bb ();
776 // Create the register phis for this EBB.
777 bb_phi_info
&phis
= bi
.bb_phis
[cfg_bb
->index
];
778 unsigned int num_preds
= phis
.num_preds
;
780 bitmap_iterator in_bi
;
781 EXECUTE_IF_SET_IN_BITMAP (&phis
.regs
, 0, regno
, in_bi
)
783 gcc_checking_assert (bitmap_bit_p (bi
.potential_phi_regs
, regno
));
785 // Create an array of phi inputs, to be filled in later.
786 auto *inputs
= XOBNEWVEC (&m_obstack
, access_info
*, num_preds
);
787 memset (inputs
, 0, sizeof (access_info
*) * num_preds
);
789 // Later code works out the correct mode of the phi. Use BLKmode
790 // as a placeholder for now.
791 phi_info
*phi
= create_phi (ebb
, { E_BLKmode
, regno
},
793 bi
.record_reg_def (phi
);
796 bitmap_copy (bi
.ebb_def_regs
, &phis
.regs
);
798 // Collect the live-in memory definitions and record whether they're
800 m_temp_defs
.reserve (num_preds
);
801 set_info
*mem_value
= nullptr;
802 bool mem_phi_is_degenerate
= true;
805 FOR_EACH_EDGE (e
, ei
, cfg_bb
->preds
)
807 bb_info
*pred_bb
= this->bb (e
->src
);
808 if (pred_bb
&& pred_bb
->head_insn ())
810 mem_value
= bi
.bb_mem_live_out
[pred_bb
->index ()];
811 m_temp_defs
.quick_push (mem_value
);
812 if (mem_value
!= m_temp_defs
[0])
813 mem_phi_is_degenerate
= false;
817 m_temp_defs
.quick_push (nullptr);
818 mem_phi_is_degenerate
= false;
822 // Create a phi for memory, on the assumption that something in the
824 if (mem_phi_is_degenerate
)
826 access_info
*input
[] = { mem_value
};
827 mem_value
= create_phi (ebb
, memory
, input
, 1);
831 obstack_grow (&m_obstack
, m_temp_defs
.address (),
832 num_preds
* sizeof (access_info
*));
833 auto *inputs
= static_cast<access_info
**> (obstack_finish (&m_obstack
));
834 mem_value
= create_phi (ebb
, memory
, inputs
, num_preds
);
836 bi
.record_mem_def (mem_value
);
837 m_temp_defs
.truncate (0);
840 // Called while building SSA form using BI.
842 // If FLAGS is DF_REF_AT_TOP, create the head insn for BI.current_bb
843 // and populate its uses and definitions. If FLAGS is 0, do the same
846 function_info::add_artificial_accesses (build_info
&bi
, df_ref_flags flags
)
848 bb_info
*bb
= bi
.current_bb
;
849 basic_block cfg_bb
= bb
->cfg_bb ();
850 auto *lr_info
= DF_LR_BB_INFO (cfg_bb
);
854 if (flags
== DF_REF_AT_TOP
)
856 if (cfg_bb
->index
== EXIT_BLOCK
)
857 insn
= append_artificial_insn (bb
);
859 insn
= append_artificial_insn (bb
, bb_note (cfg_bb
));
860 bb
->set_head_insn (insn
);
864 insn
= append_artificial_insn (bb
);
865 bb
->set_end_insn (insn
);
868 start_insn_accesses ();
870 HARD_REG_SET added_regs
= {};
871 FOR_EACH_ARTIFICIAL_USE (ref
, cfg_bb
->index
)
872 if ((DF_REF_FLAGS (ref
) & DF_REF_AT_TOP
) == flags
)
874 unsigned int regno
= DF_REF_REGNO (ref
);
875 machine_mode mode
= GET_MODE (DF_REF_REAL_REG (ref
));
876 if (HARD_REGISTER_NUM_P (regno
))
877 SET_HARD_REG_BIT (added_regs
, regno
);
879 // A definition must be available.
880 gcc_checking_assert (bitmap_bit_p (&lr_info
->in
, regno
)
881 || (flags
!= DF_REF_AT_TOP
882 && bitmap_bit_p (&lr_info
->def
, regno
)));
883 m_temp_uses
.safe_push (create_reg_use (bi
, insn
, { mode
, regno
}));
886 // Ensure that global registers and memory are live at the end of any
887 // block that has no successors, such as the exit block and non-local gotos.
888 // Global registers have to be singled out because they are not part of
889 // the DF artifical use list (they are instead treated as used within
891 if (flags
== 0 && EDGE_COUNT (cfg_bb
->succs
) == 0)
893 for (unsigned int i
= 0; i
< FIRST_PSEUDO_REGISTER
; ++i
)
894 if (global_regs
[i
] && !TEST_HARD_REG_BIT (added_regs
, i
))
896 auto mode
= reg_raw_mode
[i
];
897 m_temp_uses
.safe_push (create_reg_use (bi
, insn
, { mode
, i
}));
900 auto *use
= allocate
<use_info
> (insn
, memory
, bi
.current_mem_value ());
902 m_temp_uses
.safe_push (use
);
905 FOR_EACH_ARTIFICIAL_DEF (ref
, cfg_bb
->index
)
906 if ((DF_REF_FLAGS (ref
) & DF_REF_AT_TOP
) == flags
)
908 unsigned int regno
= DF_REF_REGNO (ref
);
909 machine_mode mode
= GET_MODE (DF_REF_REAL_REG (ref
));
910 resource_info resource
{ mode
, regno
};
912 // We rely on the def set being correct.
913 gcc_checking_assert (bitmap_bit_p (&lr_info
->def
, regno
));
915 // If the value isn't used later in the block and isn't live
916 // on exit, we could instead represent the definition as a
917 // clobber_info. However, that case should be relatively
918 // rare and set_info is any case more compact than clobber_info.
919 set_info
*def
= allocate
<set_info
> (insn
, resource
);
921 m_temp_defs
.safe_push (def
);
922 bi
.record_reg_def (def
);
925 // Model the effect of a memory clobber on an incoming edge by adding
926 // a fake definition of memory at the start of the block. We don't need
927 // to add a use of the phi node because memory is implicitly always live.
928 if (flags
== DF_REF_AT_TOP
&& has_abnormal_call_or_eh_pred_edge_p (cfg_bb
))
930 set_info
*def
= allocate
<set_info
> (insn
, memory
);
932 m_temp_defs
.safe_push (def
);
933 bi
.record_mem_def (def
);
936 finish_insn_accesses (insn
);
939 // Called while building SSA form using BI. Create insn_infos for all
940 // relevant instructions in BI.current_bb.
942 function_info::add_block_contents (build_info
&bi
)
944 basic_block cfg_bb
= bi
.current_bb
->cfg_bb ();
946 FOR_BB_INSNS (cfg_bb
, insn
)
948 add_insn_to_block (bi
, insn
);
951 // Called while building SSA form using BI. Record live-out register values
952 // in the phi inputs of successor blocks and create live-out uses where
953 // appropriate. Record the live-out memory value in BI.bb_mem_live_out.
955 function_info::record_block_live_out (build_info
&bi
)
957 bb_info
*bb
= bi
.current_bb
;
958 ebb_info
*ebb
= bi
.current_ebb
;
959 basic_block cfg_bb
= bb
->cfg_bb ();
961 // Record the live-out register values in the phi inputs of
965 FOR_EACH_EDGE (e
, ei
, cfg_bb
->succs
)
967 bb_phi_info
&phis
= bi
.bb_phis
[e
->dest
->index
];
968 unsigned int input_i
= e
->dest_idx
* phis
.num_phis
;
970 bitmap_iterator out_bi
;
971 EXECUTE_IF_SET_IN_BITMAP (&phis
.regs
, 0, regno
, out_bi
)
974 = live_out_value (bb
, bi
.current_reg_value (regno
));
979 // Add the set of registers that were defined in this BB to the set
980 // of potentially-live registers defined in the EBB.
981 bitmap_ior_into (bi
.ebb_def_regs
, &DF_LR_BB_INFO (cfg_bb
)->def
);
983 // Iterate through the registers in LIVE_OUT and see whether we need
984 // to add a live-out use for them.
985 auto record_live_out_regs
= [&](bitmap live_out
)
988 bitmap_iterator out_bi
;
989 EXECUTE_IF_AND_IN_BITMAP (bi
.ebb_def_regs
, live_out
, 0, regno
, out_bi
)
991 set_info
*value
= live_out_value (bb
, bi
.current_reg_value (regno
));
992 if (value
&& value
->ebb () == ebb
)
993 add_live_out_use (bb
, value
);
997 if (bb
== ebb
->last_bb ())
998 // All live-out registers might need live-out uses.
999 record_live_out_regs (DF_LR_OUT (cfg_bb
));
1001 // Registers might need live-out uses if they are live on entry
1002 // to a successor block in a different EBB.
1003 FOR_EACH_EDGE (e
, ei
, cfg_bb
->succs
)
1005 bb_info
*dest_bb
= this->bb (e
->dest
);
1006 if (dest_bb
->ebb () != ebb
|| dest_bb
== ebb
->first_bb ())
1007 record_live_out_regs (DF_LR_IN (e
->dest
));
1010 // Record the live-out memory value.
1011 bi
.bb_mem_live_out
[cfg_bb
->index
]
1012 = live_out_value (bb
, bi
.current_mem_value ());
1015 // Add BB and its contents to the SSA information.
1017 function_info::start_block (build_info
&bi
, bb_info
*bb
)
1019 ebb_info
*ebb
= bb
->ebb ();
1021 // We (need to) add all blocks from one EBB before moving on to the next.
1023 if (bb
== ebb
->first_bb ())
1024 bi
.current_ebb
= ebb
;
1026 gcc_assert (bi
.current_ebb
== ebb
);
1028 // Record the start of this block's definitions in the definitions stack.
1029 bi
.old_def_stack_limit
.safe_push (bi
.def_stack
.length ());
1031 // Add the block itself.
1034 // If the block starts an EBB, create the phi insn. This insn should exist
1035 // for all EBBs, even if they don't (yet) need phis.
1036 if (bb
== ebb
->first_bb ())
1037 ebb
->set_phi_insn (append_artificial_insn (bb
));
1039 if (bb
->index () == ENTRY_BLOCK
)
1041 add_entry_block_defs (bi
);
1042 record_block_live_out (bi
);
1046 if (EDGE_COUNT (bb
->cfg_bb ()->preds
) == 0)
1048 // Leave unreachable blocks empty, since there is no useful
1049 // liveness information for them, and anything they do will
1050 // be wasted work. In a cleaned-up cfg, the only unreachable
1051 // block we should see is the exit block of a noreturn function.
1052 bb
->set_head_insn (append_artificial_insn (bb
));
1053 bb
->set_end_insn (append_artificial_insn (bb
));
1057 // If the block starts an EBB, create the phi nodes.
1058 if (bb
== ebb
->first_bb ())
1061 // Process the contents of the block.
1062 add_artificial_accesses (bi
, DF_REF_AT_TOP
);
1063 if (bb
->index () != EXIT_BLOCK
)
1064 add_block_contents (bi
);
1065 add_artificial_accesses (bi
, df_ref_flags ());
1066 record_block_live_out (bi
);
1068 // If we needed to calculate a live-in set for debug purposes,
1069 // reset it to null at the end of the EBB. Convert the underlying
1070 // bitmap to an empty list view, ready for the next calculation.
1071 if (bi
.ebb_live_in_for_debug
&& bb
== ebb
->last_bb ())
1073 bitmap_clear (bi
.tmp_ebb_live_in_for_debug
);
1074 bitmap_list_view (bi
.tmp_ebb_live_in_for_debug
);
1075 bi
.ebb_live_in_for_debug
= nullptr;
1079 // Finish adding BB and the blocks that it dominates to the SSA information.
1081 function_info::end_block (build_info
&bi
, bb_info
*bb
)
1083 // Restore the register last_access information to the state it was
1084 // in before we started processing BB.
1085 unsigned int old_limit
= bi
.old_def_stack_limit
.pop ();
1086 while (bi
.def_stack
.length () > old_limit
)
1088 // We pushed a definition in BB if it was the first dominating
1089 // definition (and so the previous entry was null). In other
1090 // cases we pushed the previous dominating definition.
1091 def_info
*def
= bi
.def_stack
.pop ();
1092 unsigned int regno
= def
->regno ();
1093 if (def
->bb () == bb
)
1095 bi
.last_access
[regno
+ 1] = def
;
1099 // Finish setting up the phi nodes for each block, now that we've added
1100 // the contents of all blocks.
1102 function_info::populate_phi_inputs (build_info
&bi
)
1104 auto_vec
<phi_info
*, 32> sorted_phis
;
1105 for (ebb_info
*ebb
: ebbs ())
1107 if (!ebb
->first_phi ())
1110 // Get a sorted array of EBB's phi nodes.
1111 basic_block cfg_bb
= ebb
->first_bb ()->cfg_bb ();
1112 bb_phi_info
&phis
= bi
.bb_phis
[cfg_bb
->index
];
1113 sorted_phis
.truncate (0);
1114 for (phi_info
*phi
: ebb
->phis ())
1115 sorted_phis
.safe_push (phi
);
1116 std::sort (sorted_phis
.address (),
1117 sorted_phis
.address () + sorted_phis
.length (),
1118 compare_access_infos
);
1120 // Set the inputs of the non-degenerate register phis. All inputs
1121 // for one edge come before all inputs for the next edge.
1122 set_info
**inputs
= phis
.inputs
;
1123 unsigned int phi_i
= 0;
1124 bitmap_iterator bmi
;
1126 EXECUTE_IF_SET_IN_BITMAP (&phis
.regs
, 0, regno
, bmi
)
1128 // Skip intervening degenerate phis.
1129 while (sorted_phis
[phi_i
]->regno () < regno
)
1131 phi_info
*phi
= sorted_phis
[phi_i
];
1132 gcc_assert (phi
->regno () == regno
);
1133 for (unsigned int input_i
= 0; input_i
< phis
.num_preds
; ++input_i
)
1134 if (set_info
*input
= inputs
[input_i
* phis
.num_phis
])
1136 use_info
*use
= phi
->input_use (input_i
);
1137 gcc_assert (!use
->def ());
1138 use
->set_def (input
);
1145 // Fill in the backedge inputs to any memory phi.
1146 phi_info
*mem_phi
= sorted_phis
.last ();
1147 if (mem_phi
->is_mem () && !mem_phi
->is_degenerate ())
1151 FOR_EACH_EDGE (e
, ei
, cfg_bb
->preds
)
1153 use_info
*use
= mem_phi
->input_use (e
->dest_idx
);
1156 use
->set_def (bi
.bb_mem_live_out
[e
->src
->index
]);
1164 // Return true if it would be better to continue an EBB across NEW_EDGE
1165 // rather than across OLD_EDGE, given that both edges are viable candidates.
1166 // This is not a total ordering.
1168 better_ebb_edge_p (edge new_edge
, edge old_edge
)
1170 // Prefer the likeliest edge.
1171 if (new_edge
->probability
.initialized_p ()
1172 && old_edge
->probability
.initialized_p ()
1173 && !(old_edge
->probability
== new_edge
->probability
))
1174 return old_edge
->probability
< new_edge
->probability
;
1176 // If both edges are equally likely, prefer a fallthru edge.
1177 if (new_edge
->flags
& EDGE_FALLTHRU
)
1179 if (old_edge
->flags
& EDGE_FALLTHRU
)
1182 // Otherwise just stick with OLD_EDGE.
1186 // Pick and return the next basic block in an EBB that currently ends with BB.
1187 // Return null if the EBB must end with BB.
1189 choose_next_block_in_ebb (basic_block bb
)
1191 // Although there's nothing in principle wrong with having an EBB that
1192 // starts with the entry block and includes later blocks, there's not
1193 // really much point either. Keeping the entry block separate means
1194 // that uses of arguments consistently occur through phi nodes, rather
1195 // than the arguments sometimes appearing to come from an EBB-local
1196 // definition instead.
1197 if (bb
->index
== ENTRY_BLOCK
)
1200 bool optimize_for_speed_p
= optimize_bb_for_speed_p (bb
);
1201 edge best_edge
= nullptr;
1204 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1205 if (!(e
->flags
& EDGE_COMPLEX
)
1206 && e
->dest
->index
!= EXIT_BLOCK
1207 && single_pred_p (e
->dest
)
1208 && optimize_for_speed_p
== optimize_bb_for_speed_p (e
->dest
)
1209 && (!best_edge
|| better_ebb_edge_p (e
, best_edge
)))
1212 return best_edge
? best_edge
->dest
: nullptr;
1215 // Partition the function into extended basic blocks. Create the
1216 // associated ebb_infos and bb_infos, but don't add the bb_infos
1217 // to the function list yet.
1219 function_info::create_ebbs (build_info
&bi
)
1221 // Compute the starting reverse postorder. We tweak this later to try
1222 // to get better EBB assignments.
1223 auto *postorder
= new int[n_basic_blocks_for_fn (m_fn
)];
1224 unsigned int postorder_num
1225 = pre_and_rev_post_order_compute (nullptr, postorder
, true);
1226 gcc_assert (int (postorder_num
) <= n_basic_blocks_for_fn (m_fn
));
1228 // Iterate over the blocks in reverse postorder. In cases where
1229 // multiple possible orders exist, prefer orders that chain blocks
1230 // together into EBBs. If multiple possible EBBs exist, try to pick
1231 // the ones that are most likely to be profitable.
1232 auto_vec
<bb_info
*, 16> bbs
;
1233 unsigned int next_bb_index
= 0;
1234 for (unsigned int i
= 0; i
< postorder_num
; ++i
)
1235 if (!m_bbs
[postorder
[i
]])
1237 // Choose and create the blocks that should form the next EBB.
1238 basic_block cfg_bb
= BASIC_BLOCK_FOR_FN (m_fn
, postorder
[i
]);
1241 // Record the chosen block order in a new RPO.
1242 bi
.bb_to_rpo
[cfg_bb
->index
] = next_bb_index
++;
1243 bbs
.safe_push (create_bb_info (cfg_bb
));
1244 cfg_bb
= choose_next_block_in_ebb (cfg_bb
);
1248 // Create the EBB itself.
1249 auto *ebb
= allocate
<ebb_info
> (bbs
[0], bbs
.last ());
1250 for (bb_info
*bb
: bbs
)
1258 // Partition the function's blocks into EBBs and build SSA form for all
1259 // EBBs in the function.
1261 function_info::process_all_blocks ()
1263 auto temps
= temp_watermark ();
1264 unsigned int num_bb_indices
= last_basic_block_for_fn (m_fn
);
1266 build_info
bi (m_num_regs
, num_bb_indices
);
1268 // ??? There is no dominance information associated with the exit block,
1269 // so work out its immediate dominator using predecessor blocks.
1270 for (edge e
: EXIT_BLOCK_PTR_FOR_FN (m_fn
)->preds
)
1271 if (bi
.exit_block_dominator
)
1272 bi
.exit_block_dominator
1273 = nearest_common_dominator (CDI_DOMINATORS
,
1274 bi
.exit_block_dominator
, e
->src
);
1276 bi
.exit_block_dominator
= e
->src
;
1278 calculate_potential_phi_regs (bi
);
1281 bb_walker (this, bi
).walk (ENTRY_BLOCK_PTR_FOR_FN (m_fn
));
1282 populate_phi_inputs (bi
);
1286 // The definition stack should be empty and all register definitions
1287 // should be back in their original undefined state.
1288 gcc_assert (bi
.def_stack
.is_empty ()
1289 && bi
.old_def_stack_limit
.is_empty ());
1290 for (unsigned int regno
= 0; regno
< m_num_regs
; ++regno
)
1291 gcc_assert (!bi
.last_access
[regno
+ 1]);
1295 // Print a description of CALL_CLOBBERS to PP.
1297 rtl_ssa::pp_ebb_call_clobbers (pretty_printer
*pp
,
1298 const ebb_call_clobbers_info
*call_clobbers
)
1301 pp_string (pp
, "<null>");
1303 call_clobbers
->print_full (pp
);
1306 // Print a description of BB to PP.
1308 rtl_ssa::pp_bb (pretty_printer
*pp
, const bb_info
*bb
)
1311 pp_string (pp
, "<null>");
1313 bb
->print_full (pp
);
1316 // Print a description of EBB to PP
1318 rtl_ssa::pp_ebb (pretty_printer
*pp
, const ebb_info
*ebb
)
1321 pp_string (pp
, "<null>");
1323 ebb
->print_full (pp
);
1326 // Print a description of CALL_CLOBBERS to FILE.
1328 dump (FILE *file
, const ebb_call_clobbers_info
*call_clobbers
)
1330 dump_using (file
, pp_ebb_call_clobbers
, call_clobbers
);
1333 // Print a description of BB to FILE.
1335 dump (FILE *file
, const bb_info
*bb
)
1337 dump_using (file
, pp_bb
, bb
);
1340 // Print a description of EBB to FILE.
1342 dump (FILE *file
, const ebb_info
*ebb
)
1344 dump_using (file
, pp_ebb
, ebb
);
1347 // Debug interfaces to the dump routines above.
1348 void debug (const ebb_call_clobbers_info
*x
) { dump (stderr
, x
); }
1349 void debug (const bb_info
*x
) { dump (stderr
, x
); }
1350 void debug (const ebb_info
*x
) { dump (stderr
, x
); }