blob: 3a57e95cbcf9736201b83e303d948389792a7b63 [file] [log] [blame]
// Implementation of basic-block-related functions for RTL SSA -*- C++ -*-
// Copyright (C) 2020-2021 Free Software Foundation, Inc.
//
// This file is part of GCC.
//
// GCC is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 3, or (at your option) any later
// version.
//
// GCC is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License
// along with GCC; see the file COPYING3. If not see
// <http://www.gnu.org/licenses/>.
#define INCLUDE_ALGORITHM
#define INCLUDE_FUNCTIONAL
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "df.h"
#include "rtl-ssa.h"
#include "rtl-ssa/internals.h"
#include "rtl-ssa/internals.inl"
#include "cfganal.h"
#include "cfgrtl.h"
#include "predict.h"
#include "domwalk.h"
using namespace rtl_ssa;
// Prepare to build information for a function in which all register numbers
// are less than NUM_REGS and all basic block indices are less than
// NUM_BB_INDICES
function_info::build_info::build_info (unsigned int num_regs,
unsigned int num_bb_indices)
: current_bb (nullptr),
current_ebb (nullptr),
last_access (num_regs + 1),
ebb_live_in_for_debug (nullptr),
potential_phi_regs (num_regs),
bb_phis (num_bb_indices),
bb_mem_live_out (num_bb_indices),
bb_to_rpo (num_bb_indices)
{
last_access.safe_grow_cleared (num_regs + 1);
bitmap_clear (potential_phi_regs);
// These arrays shouldn't need to be initialized, since we'll always
// write to an entry before reading from it. But poison the contents
// when checking, just to make sure we don't accidentally use an
// uninitialized value.
bb_phis.quick_grow (num_bb_indices);
bb_mem_live_out.quick_grow (num_bb_indices);
bb_to_rpo.quick_grow (num_bb_indices);
if (flag_checking)
{
// Can't do this for bb_phis because it has a constructor.
memset (bb_mem_live_out.address (), 0xaf,
num_bb_indices * sizeof (bb_mem_live_out[0]));
memset (bb_to_rpo.address (), 0xaf,
num_bb_indices * sizeof (bb_to_rpo[0]));
}
// Start off with an empty set of phi nodes for each block.
for (bb_phi_info &info : bb_phis)
bitmap_initialize (&info.regs, &bitmap_default_obstack);
}
function_info::build_info::~build_info ()
{
for (bb_phi_info &info : bb_phis)
bitmap_release (&info.regs);
}
// A dom_walker for populating the basic blocks.
class function_info::bb_walker : public dom_walker
{
public:
bb_walker (function_info *, build_info &);
virtual edge before_dom_children (basic_block);
virtual void after_dom_children (basic_block);
private:
// Information about the function we're building.
function_info *m_function;
build_info &m_bi;
// We should treat the exit block as being the last child of this one.
// See the comment in the constructor for more information.
basic_block m_exit_block_dominator;
};
// Prepare to walk the blocks in FUNCTION using BI.
function_info::bb_walker::bb_walker (function_info *function, build_info &bi)
: dom_walker (CDI_DOMINATORS, ALL_BLOCKS, bi.bb_to_rpo.address ()),
m_function (function),
m_bi (bi),
m_exit_block_dominator (nullptr)
{
// ??? There is no dominance information associated with the exit block,
// so work out its immediate dominator using predecessor blocks. We then
// walk the exit block just before popping its immediate dominator.
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (m_function->m_fn)->preds)
if (m_exit_block_dominator)
m_exit_block_dominator
= nearest_common_dominator (CDI_DOMINATORS,
m_exit_block_dominator, e->src);
else
m_exit_block_dominator = e->src;
// If the exit block is unreachable, process it last.
if (!m_exit_block_dominator)
m_exit_block_dominator = ENTRY_BLOCK_PTR_FOR_FN (m_function->m_fn);
}
edge
function_info::bb_walker::before_dom_children (basic_block bb)
{
m_function->start_block (m_bi, m_function->bb (bb));
return nullptr;
}
void
function_info::bb_walker::after_dom_children (basic_block bb)
{
// See the comment in the constructor for details.
if (bb == m_exit_block_dominator)
{
before_dom_children (EXIT_BLOCK_PTR_FOR_FN (m_function->m_fn));
after_dom_children (EXIT_BLOCK_PTR_FOR_FN (m_function->m_fn));
}
m_function->end_block (m_bi, m_function->bb (bb));
}
// See the comment above the declaration.
void
bb_info::print_identifier (pretty_printer *pp) const
{
char tmp[3 * sizeof (index ()) + 3];
snprintf (tmp, sizeof (tmp), "bb%d", index ());
pp_string (pp, tmp);
if (ebb_info *ebb = this->ebb ())
{
pp_space (pp);
pp_left_bracket (pp);
ebb->print_identifier (pp);
pp_right_bracket (pp);
}
}
// See the comment above the declaration.
void
bb_info::print_full (pretty_printer *pp) const
{
pp_string (pp, "basic block ");
print_identifier (pp);
pp_colon (pp);
auto print_insn = [pp](const char *header, const insn_info *insn)
{
pp_newline_and_indent (pp, 2);
pp_string (pp, header);
pp_newline_and_indent (pp, 2);
if (insn)
pp_insn (pp, insn);
else
pp_string (pp, "<uninitialized>");
pp_indentation (pp) -= 4;
};
print_insn ("head:", head_insn ());
pp_newline (pp);
pp_newline_and_indent (pp, 2);
pp_string (pp, "contents:");
if (!head_insn ())
{
pp_newline_and_indent (pp, 2);
pp_string (pp, "<uninitialized>");
pp_indentation (pp) -= 2;
}
else if (auto insns = real_insns ())
{
bool is_first = true;
for (const insn_info *insn : insns)
{
if (is_first)
is_first = false;
else
pp_newline (pp);
pp_newline_and_indent (pp, 2);
pp_insn (pp, insn);
pp_indentation (pp) -= 2;
}
}
else
{
pp_newline_and_indent (pp, 2);
pp_string (pp, "none");
pp_indentation (pp) -= 2;
}
pp_indentation (pp) -= 2;
pp_newline (pp);
print_insn ("end:", end_insn ());
}
// See the comment above the declaration.
void
ebb_call_clobbers_info::print_summary (pretty_printer *pp) const
{
pp_string (pp, "call clobbers for ABI ");
if (m_abi)
pp_decimal_int (pp, m_abi->id ());
else
pp_string (pp, "<null>");
}
// See the comment above the declaration.
void
ebb_call_clobbers_info::print_full (pretty_printer *pp) const
{
print_summary (pp);
pp_colon (pp);
pp_newline_and_indent (pp, 2);
auto print_node = [](pretty_printer *pp,
const insn_call_clobbers_note *note)
{
if (insn_info *insn = note->insn ())
insn->print_identifier_and_location (pp);
else
pp_string (pp, "<null>");
};
print (pp, root (), print_node);
pp_indentation (pp) -= 2;
}
// See the comment above the declaration.
void
ebb_info::print_identifier (pretty_printer *pp) const
{
// first_bb is populated by the constructor and so should always
// be nonnull.
auto index = first_bb ()->index ();
char tmp[3 * sizeof (index) + 4];
snprintf (tmp, sizeof (tmp), "ebb%d", index);
pp_string (pp, tmp);
}
// See the comment above the declaration.
void
ebb_info::print_full (pretty_printer *pp) const
{
pp_string (pp, "extended basic block ");
print_identifier (pp);
pp_colon (pp);
pp_newline_and_indent (pp, 2);
if (insn_info *phi_insn = this->phi_insn ())
{
phi_insn->print_identifier_and_location (pp);
pp_colon (pp);
if (auto phis = this->phis ())
{
bool is_first = true;
for (const phi_info *phi : phis)
{
if (is_first)
is_first = false;
else
pp_newline (pp);
pp_newline_and_indent (pp, 2);
pp_access (pp, phi, PP_ACCESS_SETTER);
pp_indentation (pp) -= 2;
}
}
else
{
pp_newline_and_indent (pp, 2);
pp_string (pp, "no phi nodes");
pp_indentation (pp) -= 2;
}
}
else
pp_string (pp, "no phi insn");
pp_indentation (pp) -= 2;
for (const bb_info *bb : bbs ())
{
pp_newline (pp);
pp_newline_and_indent (pp, 2);
pp_bb (pp, bb);
pp_indentation (pp) -= 2;
}
for (ebb_call_clobbers_info *ecc : call_clobbers ())
{
pp_newline (pp);
pp_newline_and_indent (pp, 2);
pp_ebb_call_clobbers (pp, ecc);
pp_indentation (pp) -= 2;
}
}
// Add a dummy use to mark that DEF is live out of BB's EBB at the end of BB.
void
function_info::add_live_out_use (bb_info *bb, set_info *def)
{
// There is nothing to do if DEF is an artificial definition at the end
// of BB. In that case the definitino is rooted at the end of the block
// and we wouldn't gain anything by inserting a use immediately after it.
// If we did want to insert a use, we'd need to associate it with a new
// instruction that comes after bb->end_insn ().
if (def->insn () == bb->end_insn ())
return;
// If the end of the block already has an artificial use, that use
// acts to make DEF live at the appropriate point.
use_info *use = def->last_nondebug_insn_use ();
if (use && use->insn () == bb->end_insn ())
return;
// Currently there is no need to maintain a backward link from the end
// instruction to the list of live-out uses. Such a list would be
// expensive to update if it was represented using the usual insn_info
// access arrays.
use = allocate<use_info> (bb->end_insn (), def->resource (), def);
use->set_is_live_out_use (true);
add_use (use);
}
// Return true if all nondebug uses of DEF are live-out uses.
static bool
all_uses_are_live_out_uses (set_info *def)
{
for (use_info *use : def->all_uses ())
if (!use->is_in_debug_insn () && !use->is_live_out_use ())
return false;
return true;
}
// SET, if nonnull, is a definition of something that is live out from BB.
// Return the live-out value itself.
set_info *
function_info::live_out_value (bb_info *bb, set_info *set)
{
// Degenerate phis only exist to provide a definition for uses in the
// same EBB. The live-out value is the same as the live-in value.
if (auto *phi = safe_dyn_cast<phi_info *> (set))
if (phi->is_degenerate ())
{
set = phi->input_value (0);
// Remove the phi if it turned out to be useless. This is
// mainly useful for memory, because we don't know ahead of time
// whether a block will use memory or not.
if (bb == bb->ebb ()->last_bb () && all_uses_are_live_out_uses (phi))
replace_phi (phi, set);
}
return set;
}
// Add PHI to EBB and enter it into the function's hash table.
void
function_info::append_phi (ebb_info *ebb, phi_info *phi)
{
phi_info *first_phi = ebb->first_phi ();
if (first_phi)
first_phi->set_prev_phi (phi);
phi->set_next_phi (first_phi);
ebb->set_first_phi (phi);
add_def (phi);
}
// Remove PHI from its current position in the SSA graph.
void
function_info::remove_phi (phi_info *phi)
{
phi_info *next = phi->next_phi ();
phi_info *prev = phi->prev_phi ();
if (next)
next->set_prev_phi (prev);
if (prev)
prev->set_next_phi (next);
else
phi->ebb ()->set_first_phi (next);
remove_def (phi);
phi->clear_phi_links ();
}
// Remove PHI from the SSA graph and free its memory.
void
function_info::delete_phi (phi_info *phi)
{
gcc_assert (!phi->has_any_uses ());
// Remove the inputs to the phi.
for (use_info *input : phi->inputs ())
remove_use (input);
remove_phi (phi);
phi->set_next_phi (m_free_phis);
m_free_phis = phi;
}
// If possible, remove PHI and replace all uses with NEW_VALUE.
void
function_info::replace_phi (phi_info *phi, set_info *new_value)
{
auto update_use = [&](use_info *use)
{
remove_use (use);
use->set_def (new_value);
add_use (use);
};
if (new_value)
for (use_info *use : phi->nondebug_insn_uses ())
if (!use->is_live_out_use ())
{
// We need to keep the phi around for its local uses.
// Turn it into a degenerate phi, if it isn't already.
use_info *use = phi->input_use (0);
if (use->def () != new_value)
update_use (use);
if (phi->is_degenerate ())
return;
phi->make_degenerate (use);
// Redirect all phi users to NEW_VALUE.
while (use_info *phi_use = phi->last_phi_use ())
update_use (phi_use);
return;
}
// Replace the uses. We can discard uses that only existed for the
// sake of marking live-out values, since the resource is now transparent
// in the phi's EBB.
while (use_info *use = phi->last_use ())
if (use->is_live_out_use ())
remove_use (use);
else
update_use (use);
delete_phi (phi);
}
// Create and return a phi node for EBB. RESOURCE is the resource that
// the phi node sets (and thus that all the inputs set too). NUM_INPUTS
// is the number of inputs, which is 1 for a degenerate phi. INPUTS[I]
// is a set_info that gives the value of input I, or null if the value
// is either unknown or uninitialized. If NUM_INPUTS > 1, this array
// is allocated on the main obstack and can be reused for the use array.
//
// Add the created phi node to its basic block and enter it into the
// function's hash table.
phi_info *
function_info::create_phi (ebb_info *ebb, resource_info resource,
access_info **inputs, unsigned int num_inputs)
{
phi_info *phi = m_free_phis;
if (phi)
{
m_free_phis = phi->next_phi ();
*phi = phi_info (ebb->phi_insn (), resource, phi->uid ());
}
else
{
phi = allocate<phi_info> (ebb->phi_insn (), resource, m_next_phi_uid);
m_next_phi_uid += 1;
}
// Convert the array of set_infos into an array of use_infos. Also work
// out what mode the phi should have.
machine_mode new_mode = resource.mode;
for (unsigned int i = 0; i < num_inputs; ++i)
{
auto *input = safe_as_a<set_info *> (inputs[i]);
auto *use = allocate<use_info> (phi, resource, input);
add_use (use);
inputs[i] = use;
if (input)
new_mode = combine_modes (new_mode, input->mode ());
}
phi->set_inputs (use_array (inputs, num_inputs));
phi->set_mode (new_mode);
append_phi (ebb, phi);
return phi;
}
// Create and return a degenerate phi for EBB whose input comes from DEF.
// This is used in cases where DEF is known to be available on entry to
// EBB but was not previously used within it. If DEF is for a register,
// there are two cases:
//
// (1) DEF was already live on entry to EBB but was previously transparent
// within it.
//
// (2) DEF was not previously live on entry to EBB and is being made live
// by this update.
//
// At the moment, this function only handles the case in which EBB has a
// single predecessor block and DEF is defined in that block's EBB.
phi_info *
function_info::create_degenerate_phi (ebb_info *ebb, set_info *def)
{
access_info *input = def;
phi_info *phi = create_phi (ebb, def->resource (), &input, 1);
if (def->is_reg ())
{
unsigned int regno = def->regno ();
// Find the single predecessor mentioned above.
basic_block pred_cfg_bb = single_pred (ebb->first_bb ()->cfg_bb ());
bb_info *pred_bb = this->bb (pred_cfg_bb);
if (!bitmap_set_bit (DF_LR_IN (ebb->first_bb ()->cfg_bb ()), regno))
{
// The register was not previously live on entry to EBB and
// might not have been live on exit from PRED_BB either.
if (bitmap_set_bit (DF_LR_OUT (pred_cfg_bb), regno))
add_live_out_use (pred_bb, def);
}
else
{
// The register was previously live in to EBB. Add live-out uses
// at the appropriate points.
insn_info *next_insn = nullptr;
if (def_info *next_def = phi->next_def ())
next_insn = next_def->insn ();
for (bb_info *bb : ebb->bbs ())
{
if ((next_insn && *next_insn <= *bb->end_insn ())
|| !bitmap_bit_p (DF_LR_OUT (bb->cfg_bb ()), regno))
break;
add_live_out_use (bb, def);
}
}
}
return phi;
}
// Create a bb_info for CFG_BB, given that no such structure currently exists.
bb_info *
function_info::create_bb_info (basic_block cfg_bb)
{
bb_info *bb = allocate<bb_info> (cfg_bb);
gcc_checking_assert (!m_bbs[cfg_bb->index]);
m_bbs[cfg_bb->index] = bb;
return bb;
}
// Add BB to the end of the list of blocks.
void
function_info::append_bb (bb_info *bb)
{
if (m_last_bb)
m_last_bb->set_next_bb (bb);
else
m_first_bb = bb;
bb->set_prev_bb (m_last_bb);
m_last_bb = bb;
}
// Calculate BI.potential_phi_regs and BI.potential_phi_regs_for_debug.
void
function_info::calculate_potential_phi_regs (build_info &bi)
{
auto *lr_info = DF_LR_BB_INFO (ENTRY_BLOCK_PTR_FOR_FN (m_fn));
bool is_debug = MAY_HAVE_DEBUG_INSNS;
for (unsigned int regno = 0; regno < m_num_regs; ++regno)
if (regno >= DF_REG_SIZE (DF)
// Exclude registers that have a single definition that dominates
// all uses. If the definition does not dominate all uses,
// the register will be exposed upwards to the entry block but
// will not be defined by the entry block.
|| DF_REG_DEF_COUNT (regno) > 1
|| (!bitmap_bit_p (&lr_info->def, regno)
&& bitmap_bit_p (&lr_info->out, regno)))
{
bitmap_set_bit (bi.potential_phi_regs, regno);
if (is_debug)
bitmap_set_bit (bi.potential_phi_regs_for_debug, regno);
}
}
// Called while building SSA form using BI. Decide where phi nodes
// should be placed for each register and initialize BI.bb_phis accordingly.
void
function_info::place_phis (build_info &bi)
{
unsigned int num_bb_indices = last_basic_block_for_fn (m_fn);
// Calculate dominance frontiers.
auto_vec<bitmap_head> frontiers;
frontiers.safe_grow (num_bb_indices);
for (unsigned int i = 0; i < num_bb_indices; ++i)
bitmap_initialize (&frontiers[i], &bitmap_default_obstack);
compute_dominance_frontiers (frontiers.address ());
// In extreme cases, the number of live-in registers can be much
// greater than the number of phi nodes needed in a block (see PR98863).
// Try to reduce the number of operations involving live-in sets by using
// PENDING as a staging area: registers in PENDING need phi nodes if
// they are live on entry to the corresponding block, but do not need
// phi nodes otherwise.
auto_vec<bitmap_head> unfiltered;
unfiltered.safe_grow (num_bb_indices);
for (unsigned int i = 0; i < num_bb_indices; ++i)
bitmap_initialize (&unfiltered[i], &bitmap_default_obstack);
// If block B1 defines R and if B2 is in the dominance frontier of B1,
// queue a possible phi node for R in B2.
auto_bitmap worklist;
for (unsigned int b1 = 0; b1 < num_bb_indices; ++b1)
{
// Only access DF information for blocks that are known to exist.
if (bitmap_empty_p (&frontiers[b1]))
continue;
bitmap b1_def = &DF_LR_BB_INFO (BASIC_BLOCK_FOR_FN (m_fn, b1))->def;
bitmap_iterator bmi;
unsigned int b2;
EXECUTE_IF_SET_IN_BITMAP (&frontiers[b1], 0, b2, bmi)
if (bitmap_ior_into (&unfiltered[b2], b1_def)
&& !bitmap_empty_p (&frontiers[b2]))
// Propagate the (potential) new phi node definitions in B2.
bitmap_set_bit (worklist, b2);
}
while (!bitmap_empty_p (worklist))
{
unsigned int b1 = bitmap_first_set_bit (worklist);
bitmap_clear_bit (worklist, b1);
// Restrict the phi nodes to registers that are live on entry to
// the block.
bitmap b1_in = DF_LR_IN (BASIC_BLOCK_FOR_FN (m_fn, b1));
bitmap b1_phis = &bi.bb_phis[b1].regs;
if (!bitmap_ior_and_into (b1_phis, &unfiltered[b1], b1_in))
continue;
// If block B1 has a phi node for R and if B2 is in the dominance
// frontier of B1, queue a possible phi node for R in B2.
bitmap_iterator bmi;
unsigned int b2;
EXECUTE_IF_SET_IN_BITMAP (&frontiers[b1], 0, b2, bmi)
if (bitmap_ior_into (&unfiltered[b2], b1_phis)
&& !bitmap_empty_p (&frontiers[b2]))
bitmap_set_bit (worklist, b2);
}
basic_block cfg_bb;
FOR_ALL_BB_FN (cfg_bb, m_fn)
{
// Calculate the set of phi nodes for blocks that don't have any
// dominance frontiers. We only need to do this once per block.
unsigned int i = cfg_bb->index;
bb_phi_info &phis = bi.bb_phis[i];
if (bitmap_empty_p (&frontiers[i]))
bitmap_and (&phis.regs, &unfiltered[i], DF_LR_IN (cfg_bb));
// Create an array that contains all phi inputs for this block.
// See the comment above the member variables for more information.
phis.num_phis = bitmap_count_bits (&phis.regs);
phis.num_preds = EDGE_COUNT (cfg_bb->preds);
unsigned int num_inputs = phis.num_phis * phis.num_preds;
if (num_inputs != 0)
{
phis.inputs = XOBNEWVEC (&m_temp_obstack, set_info *, num_inputs);
memset (phis.inputs, 0, num_inputs * sizeof (phis.inputs[0]));
}
}
// Free the temporary bitmaps.
for (unsigned int i = 0; i < num_bb_indices; ++i)
{
bitmap_release (&frontiers[i]);
bitmap_release (&unfiltered[i]);
}
}
// Called while building SSA form using BI, with BI.current_bb being
// the entry block.
//
// Create the entry block instructions and their definitions. The only
// useful instruction is the end instruction, which carries definitions
// for the values that are live on entry to the function. However, it
// seems simpler to create a head instruction too, rather than force all
// users of the block information to treat the entry block as a special case.
void
function_info::add_entry_block_defs (build_info &bi)
{
bb_info *bb = bi.current_bb;
basic_block cfg_bb = bi.current_bb->cfg_bb ();
auto *lr_info = DF_LR_BB_INFO (cfg_bb);
bb->set_head_insn (append_artificial_insn (bb));
insn_info *insn = append_artificial_insn (bb);
bb->set_end_insn (insn);
start_insn_accesses ();
// Using LR to derive the liveness information means that we create an
// entry block definition for upwards exposed registers. These registers
// are sometimes genuinely uninitialized. However, some targets also
// create a pseudo PIC base register and only initialize it later.
// Handling that case correctly seems more important than optimizing
// uninitialized uses.
unsigned int regno;
bitmap_iterator in_bi;
EXECUTE_IF_SET_IN_BITMAP (&lr_info->out, 0, regno, in_bi)
{
auto *set = allocate<set_info> (insn, full_register (regno));
append_def (set);
m_temp_defs.safe_push (set);
bi.record_reg_def (set);
}
// Create a definition that reflects the state of memory on entry to
// the function.
auto *set = allocate<set_info> (insn, memory);
append_def (set);
m_temp_defs.safe_push (set);
bi.record_mem_def (set);
finish_insn_accesses (insn);
}
// Lazily calculate the value of BI.ebb_live_in_for_debug for BI.current_ebb.
void
function_info::calculate_ebb_live_in_for_debug (build_info &bi)
{
gcc_checking_assert (bitmap_empty_p (bi.tmp_ebb_live_in_for_debug));
bi.ebb_live_in_for_debug = bi.tmp_ebb_live_in_for_debug;
bitmap_and (bi.ebb_live_in_for_debug, bi.potential_phi_regs_for_debug,
DF_LR_IN (bi.current_ebb->first_bb ()->cfg_bb ()));
bitmap_tree_view (bi.ebb_live_in_for_debug);
}
// Called while building SSA form using BI. Create phi nodes for the
// current EBB.
void
function_info::add_phi_nodes (build_info &bi)
{
ebb_info *ebb = bi.current_ebb;
basic_block cfg_bb = ebb->first_bb ()->cfg_bb ();
// Create the register phis for this EBB.
bb_phi_info &phis = bi.bb_phis[cfg_bb->index];
unsigned int num_preds = phis.num_preds;
unsigned int regno;
bitmap_iterator in_bi;
EXECUTE_IF_SET_IN_BITMAP (&phis.regs, 0, regno, in_bi)
{
gcc_checking_assert (bitmap_bit_p (bi.potential_phi_regs, regno));
// Create an array of phi inputs, to be filled in later.
auto *inputs = XOBNEWVEC (&m_obstack, access_info *, num_preds);
memset (inputs, 0, sizeof (access_info *) * num_preds);
// Later code works out the correct mode of the phi. Use BLKmode
// as a placeholder for now.
phi_info *phi = create_phi (ebb, { E_BLKmode, regno },
inputs, num_preds);
bi.record_reg_def (phi);
}
bitmap_copy (bi.ebb_def_regs, &phis.regs);
// Collect the live-in memory definitions and record whether they're
// all the same.
m_temp_defs.reserve (num_preds);
set_info *mem_value = nullptr;
bool mem_phi_is_degenerate = true;
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, cfg_bb->preds)
{
bb_info *pred_bb = this->bb (e->src);
if (pred_bb && pred_bb->head_insn ())
{
mem_value = bi.bb_mem_live_out[pred_bb->index ()];
m_temp_defs.quick_push (mem_value);
if (mem_value != m_temp_defs[0])
mem_phi_is_degenerate = false;
}
else
{
m_temp_defs.quick_push (nullptr);
mem_phi_is_degenerate = false;
}
}
// Create a phi for memory, on the assumption that something in the
// EBB will need it.
if (mem_phi_is_degenerate)
{
access_info *input[] = { mem_value };
mem_value = create_phi (ebb, memory, input, 1);
}
else
{
obstack_grow (&m_obstack, m_temp_defs.address (),
num_preds * sizeof (access_info *));
auto *inputs = static_cast<access_info **> (obstack_finish (&m_obstack));
mem_value = create_phi (ebb, memory, inputs, num_preds);
}
bi.record_mem_def (mem_value);
m_temp_defs.truncate (0);
}
// Called while building SSA form using BI.
//
// If FLAGS is DF_REF_AT_TOP, create the head insn for BI.current_bb
// and populate its uses and definitions. If FLAGS is 0, do the same
// for the end insn.
void
function_info::add_artificial_accesses (build_info &bi, df_ref_flags flags)
{
bb_info *bb = bi.current_bb;
basic_block cfg_bb = bb->cfg_bb ();
auto *lr_info = DF_LR_BB_INFO (cfg_bb);
df_ref ref;
insn_info *insn;
if (flags == DF_REF_AT_TOP)
{
if (cfg_bb->index == EXIT_BLOCK)
insn = append_artificial_insn (bb);
else
insn = append_artificial_insn (bb, bb_note (cfg_bb));
bb->set_head_insn (insn);
}
else
{
insn = append_artificial_insn (bb);
bb->set_end_insn (insn);
}
start_insn_accesses ();
FOR_EACH_ARTIFICIAL_USE (ref, cfg_bb->index)
if ((DF_REF_FLAGS (ref) & DF_REF_AT_TOP) == flags)
{
unsigned int regno = DF_REF_REGNO (ref);
machine_mode mode = GET_MODE (DF_REF_REAL_REG (ref));
// A definition must be available.
gcc_checking_assert (bitmap_bit_p (&lr_info->in, regno)
|| (flags != DF_REF_AT_TOP
&& bitmap_bit_p (&lr_info->def, regno)));
m_temp_uses.safe_push (create_reg_use (bi, insn, { mode, regno }));
}
// Track the return value of memory by adding an artificial use of
// memory at the end of the exit block.
if (flags == 0 && cfg_bb->index == EXIT_BLOCK)
{
auto *use = allocate<use_info> (insn, memory, bi.current_mem_value ());
add_use (use);
m_temp_uses.safe_push (use);
}
FOR_EACH_ARTIFICIAL_DEF (ref, cfg_bb->index)
if ((DF_REF_FLAGS (ref) & DF_REF_AT_TOP) == flags)
{
unsigned int regno = DF_REF_REGNO (ref);
machine_mode mode = GET_MODE (DF_REF_REAL_REG (ref));
resource_info resource { mode, regno };
// We rely on the def set being correct.
gcc_checking_assert (bitmap_bit_p (&lr_info->def, regno));
// If the value isn't used later in the block and isn't live
// on exit, we could instead represent the definition as a
// clobber_info. However, that case should be relatively
// rare and set_info is any case more compact than clobber_info.
set_info *def = allocate<set_info> (insn, resource);
append_def (def);
m_temp_defs.safe_push (def);
bi.record_reg_def (def);
}
// Model the effect of a memory clobber on an incoming edge by adding
// a fake definition of memory at the start of the block. We don't need
// to add a use of the phi node because memory is implicitly always live.
if (flags == DF_REF_AT_TOP && has_abnormal_call_or_eh_pred_edge_p (cfg_bb))
{
set_info *def = allocate<set_info> (insn, memory);
append_def (def);
m_temp_defs.safe_push (def);
bi.record_mem_def (def);
}
finish_insn_accesses (insn);
}
// Called while building SSA form using BI. Create insn_infos for all
// relevant instructions in BI.current_bb.
void
function_info::add_block_contents (build_info &bi)
{
basic_block cfg_bb = bi.current_bb->cfg_bb ();
rtx_insn *insn;
FOR_BB_INSNS (cfg_bb, insn)
if (INSN_P (insn))
add_insn_to_block (bi, insn);
}
// Called while building SSA form using BI. Record live-out register values
// in the phi inputs of successor blocks and create live-out uses where
// appropriate. Record the live-out memory value in BI.bb_mem_live_out.
void
function_info::record_block_live_out (build_info &bi)
{
bb_info *bb = bi.current_bb;
ebb_info *ebb = bi.current_ebb;
basic_block cfg_bb = bb->cfg_bb ();
// Record the live-out register values in the phi inputs of
// successor blocks.
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, cfg_bb->succs)
{
bb_phi_info &phis = bi.bb_phis[e->dest->index];
unsigned int input_i = e->dest_idx * phis.num_phis;
unsigned int regno;
bitmap_iterator out_bi;
EXECUTE_IF_SET_IN_BITMAP (&phis.regs, 0, regno, out_bi)
{
phis.inputs[input_i]
= live_out_value (bb, bi.current_reg_value (regno));
input_i += 1;
}
}
// Add the set of registers that were defined in this BB to the set
// of potentially-live registers defined in the EBB.
bitmap_ior_into (bi.ebb_def_regs, &DF_LR_BB_INFO (cfg_bb)->def);
// Iterate through the registers in LIVE_OUT and see whether we need
// to add a live-out use for them.
auto record_live_out_regs = [&](bitmap live_out)
{
unsigned int regno;
bitmap_iterator out_bi;
EXECUTE_IF_AND_IN_BITMAP (bi.ebb_def_regs, live_out, 0, regno, out_bi)
{
set_info *value = live_out_value (bb, bi.current_reg_value (regno));
if (value && value->ebb () == ebb)
add_live_out_use (bb, value);
}
};
if (bb == ebb->last_bb ())
// All live-out registers might need live-out uses.
record_live_out_regs (DF_LR_OUT (cfg_bb));
else
// Registers might need live-out uses if they are live on entry
// to a successor block in a different EBB.
FOR_EACH_EDGE (e, ei, cfg_bb->succs)
{
bb_info *dest_bb = this->bb (e->dest);
if (dest_bb->ebb () != ebb || dest_bb == ebb->first_bb ())
record_live_out_regs (DF_LR_IN (e->dest));
}
// Record the live-out memory value.
bi.bb_mem_live_out[cfg_bb->index]
= live_out_value (bb, bi.current_mem_value ());
}
// Add BB and its contents to the SSA information.
void
function_info::start_block (build_info &bi, bb_info *bb)
{
ebb_info *ebb = bb->ebb ();
// We (need to) add all blocks from one EBB before moving on to the next.
bi.current_bb = bb;
if (bb == ebb->first_bb ())
bi.current_ebb = ebb;
else
gcc_assert (bi.current_ebb == ebb);
// Record the start of this block's definitions in the definitions stack.
bi.old_def_stack_limit.safe_push (bi.def_stack.length ());
// Add the block itself.
append_bb (bb);
// If the block starts an EBB, create the phi insn. This insn should exist
// for all EBBs, even if they don't (yet) need phis.
if (bb == ebb->first_bb ())
ebb->set_phi_insn (append_artificial_insn (bb));
if (bb->index () == ENTRY_BLOCK)
{
add_entry_block_defs (bi);
record_block_live_out (bi);
return;
}
if (EDGE_COUNT (bb->cfg_bb ()->preds) == 0)
{
// Leave unreachable blocks empty, since there is no useful
// liveness information for them, and anything they do will
// be wasted work. In a cleaned-up cfg, the only unreachable
// block we should see is the exit block of a noreturn function.
bb->set_head_insn (append_artificial_insn (bb));
bb->set_end_insn (append_artificial_insn (bb));
return;
}
// If the block starts an EBB, create the phi nodes.
if (bb == ebb->first_bb ())
add_phi_nodes (bi);
// Process the contents of the block.
add_artificial_accesses (bi, DF_REF_AT_TOP);
if (bb->index () != EXIT_BLOCK)
add_block_contents (bi);
add_artificial_accesses (bi, df_ref_flags ());
record_block_live_out (bi);
// If we needed to calculate a live-in set for debug purposes,
// reset it to null at the end of the EBB. Convert the underlying
// bitmap to an empty list view, ready for the next calculation.
if (bi.ebb_live_in_for_debug && bb == ebb->last_bb ())
{
bitmap_clear (bi.tmp_ebb_live_in_for_debug);
bitmap_list_view (bi.tmp_ebb_live_in_for_debug);
bi.ebb_live_in_for_debug = nullptr;
}
}
// Finish adding BB and the blocks that it dominates to the SSA information.
void
function_info::end_block (build_info &bi, bb_info *bb)
{
// Restore the register last_access information to the state it was
// in before we started processing BB.
unsigned int old_limit = bi.old_def_stack_limit.pop ();
while (bi.def_stack.length () > old_limit)
{
// We pushed a definition in BB if it was the first dominating
// definition (and so the previous entry was null). In other
// cases we pushed the previous dominating definition.
def_info *def = bi.def_stack.pop ();
unsigned int regno = def->regno ();
if (def->bb () == bb)
def = nullptr;
bi.last_access[regno + 1] = def;
}
}
// Finish setting up the phi nodes for each block, now that we've added
// the contents of all blocks.
void
function_info::populate_phi_inputs (build_info &bi)
{
auto_vec<phi_info *, 32> sorted_phis;
for (ebb_info *ebb : ebbs ())
{
if (!ebb->first_phi ())
continue;
// Get a sorted array of EBB's phi nodes.
basic_block cfg_bb = ebb->first_bb ()->cfg_bb ();
bb_phi_info &phis = bi.bb_phis[cfg_bb->index];
sorted_phis.truncate (0);
for (phi_info *phi : ebb->phis ())
sorted_phis.safe_push (phi);
std::sort (sorted_phis.address (),
sorted_phis.address () + sorted_phis.length (),
compare_access_infos);
// Set the inputs of the non-degenerate register phis. All inputs
// for one edge come before all inputs for the next edge.
set_info **inputs = phis.inputs;
unsigned int phi_i = 0;
bitmap_iterator bmi;
unsigned int regno;
EXECUTE_IF_SET_IN_BITMAP (&phis.regs, 0, regno, bmi)
{
// Skip intervening degenerate phis.
while (sorted_phis[phi_i]->regno () < regno)
phi_i += 1;
phi_info *phi = sorted_phis[phi_i];
gcc_assert (phi->regno () == regno);
for (unsigned int input_i = 0; input_i < phis.num_preds; ++input_i)
if (set_info *input = inputs[input_i * phis.num_phis])
{
use_info *use = phi->input_use (input_i);
gcc_assert (!use->def ());
use->set_def (input);
add_use (use);
}
phi_i += 1;
inputs += 1;
}
// Fill in the backedge inputs to any memory phi.
phi_info *mem_phi = sorted_phis.last ();
if (mem_phi->is_mem () && !mem_phi->is_degenerate ())
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, cfg_bb->preds)
{
use_info *use = mem_phi->input_use (e->dest_idx);
if (!use->def ())
{
use->set_def (bi.bb_mem_live_out[e->src->index]);
add_use (use);
}
}
}
}
}
// Return true if it would be better to continue an EBB across NEW_EDGE
// rather than across OLD_EDGE, given that both edges are viable candidates.
// This is not a total ordering.
static bool
better_ebb_edge_p (edge new_edge, edge old_edge)
{
// Prefer the likeliest edge.
if (new_edge->probability.initialized_p ()
&& old_edge->probability.initialized_p ()
&& !(old_edge->probability == new_edge->probability))
return old_edge->probability < new_edge->probability;
// If both edges are equally likely, prefer a fallthru edge.
if (new_edge->flags & EDGE_FALLTHRU)
return true;
if (old_edge->flags & EDGE_FALLTHRU)
return false;
// Otherwise just stick with OLD_EDGE.
return false;
}
// Pick and return the next basic block in an EBB that currently ends with BB.
// Return null if the EBB must end with BB.
static basic_block
choose_next_block_in_ebb (basic_block bb)
{
// Although there's nothing in principle wrong with having an EBB that
// starts with the entry block and includes later blocks, there's not
// really much point either. Keeping the entry block separate means
// that uses of arguments consistently occur through phi nodes, rather
// than the arguments sometimes appearing to come from an EBB-local
// definition instead.
if (bb->index == ENTRY_BLOCK)
return nullptr;
bool optimize_for_speed_p = optimize_bb_for_speed_p (bb);
edge best_edge = nullptr;
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
if (!(e->flags & EDGE_COMPLEX)
&& e->dest->index != EXIT_BLOCK
&& single_pred_p (e->dest)
&& optimize_for_speed_p == optimize_bb_for_speed_p (e->dest)
&& (!best_edge || better_ebb_edge_p (e, best_edge)))
best_edge = e;
return best_edge ? best_edge->dest : nullptr;
}
// Partition the function into extended basic blocks. Create the
// associated ebb_infos and bb_infos, but don't add the bb_infos
// to the function list yet.
void
function_info::create_ebbs (build_info &bi)
{
// Compute the starting reverse postorder. We tweak this later to try
// to get better EBB assignments.
auto *postorder = new int[n_basic_blocks_for_fn (m_fn)];
unsigned int postorder_num
= pre_and_rev_post_order_compute (nullptr, postorder, true);
gcc_assert (int (postorder_num) <= n_basic_blocks_for_fn (m_fn));
// Iterate over the blocks in reverse postorder. In cases where
// multiple possible orders exist, prefer orders that chain blocks
// together into EBBs. If multiple possible EBBs exist, try to pick
// the ones that are most likely to be profitable.
auto_vec<bb_info *, 16> bbs;
unsigned int next_bb_index = 0;
for (unsigned int i = 0; i < postorder_num; ++i)
if (!m_bbs[postorder[i]])
{
// Choose and create the blocks that should form the next EBB.
basic_block cfg_bb = BASIC_BLOCK_FOR_FN (m_fn, postorder[i]);
do
{
// Record the chosen block order in a new RPO.
bi.bb_to_rpo[cfg_bb->index] = next_bb_index++;
bbs.safe_push (create_bb_info (cfg_bb));
cfg_bb = choose_next_block_in_ebb (cfg_bb);
}
while (cfg_bb);
// Create the EBB itself.
auto *ebb = allocate<ebb_info> (bbs[0], bbs.last ());
for (bb_info *bb : bbs)
bb->set_ebb (ebb);
bbs.truncate (0);
}
delete[] postorder;
}
// Partition the function's blocks into EBBs and build SSA form for all
// EBBs in the function.
void
function_info::process_all_blocks ()
{
auto temps = temp_watermark ();
unsigned int num_bb_indices = last_basic_block_for_fn (m_fn);
build_info bi (m_num_regs, num_bb_indices);
calculate_potential_phi_regs (bi);
create_ebbs (bi);
place_phis (bi);
bb_walker (this, bi).walk (ENTRY_BLOCK_PTR_FOR_FN (m_fn));
populate_phi_inputs (bi);
if (flag_checking)
{
// The definition stack should be empty and all register definitions
// should be back in their original undefined state.
gcc_assert (bi.def_stack.is_empty ()
&& bi.old_def_stack_limit.is_empty ());
for (unsigned int regno = 0; regno < m_num_regs; ++regno)
gcc_assert (!bi.last_access[regno + 1]);
}
}
// Print a description of CALL_CLOBBERS to PP.
void
rtl_ssa::pp_ebb_call_clobbers (pretty_printer *pp,
const ebb_call_clobbers_info *call_clobbers)
{
if (!call_clobbers)
pp_string (pp, "<null>");
else
call_clobbers->print_full (pp);
}
// Print a description of BB to PP.
void
rtl_ssa::pp_bb (pretty_printer *pp, const bb_info *bb)
{
if (!bb)
pp_string (pp, "<null>");
else
bb->print_full (pp);
}
// Print a description of EBB to PP
void
rtl_ssa::pp_ebb (pretty_printer *pp, const ebb_info *ebb)
{
if (!ebb)
pp_string (pp, "<null>");
else
ebb->print_full (pp);
}
// Print a description of CALL_CLOBBERS to FILE.
void
dump (FILE *file, const ebb_call_clobbers_info *call_clobbers)
{
dump_using (file, pp_ebb_call_clobbers, call_clobbers);
}
// Print a description of BB to FILE.
void
dump (FILE *file, const bb_info *bb)
{
dump_using (file, pp_bb, bb);
}
// Print a description of EBB to FILE.
void
dump (FILE *file, const ebb_info *ebb)
{
dump_using (file, pp_ebb, ebb);
}
// Debug interfaces to the dump routines above.
void debug (const ebb_call_clobbers_info *x) { dump (stderr, x); }
void debug (const bb_info *x) { dump (stderr, x); }
void debug (const ebb_info *x) { dump (stderr, x); }