blob: a55cc8817a7742d4502c1aa9369c0e7199d33157 [file] [log] [blame]
// Implementation of access-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"
using namespace rtl_ssa;
// This clobber belongs to a clobber_group but m_group appears to be
// out of date. Update it and return the new (correct) value.
clobber_group *
clobber_info::recompute_group ()
{
using splay_tree = clobber_info::splay_tree;
// Splay this clobber to the root of the tree while searching for a node
// that has the correct group. The root always has the correct group,
// so the search always breaks early and does not install this clobber
// as the root.
clobber_info *cursor = m_parent;
auto find_group = [](clobber_info *node, unsigned int)
{
return node->m_group->has_been_superceded () ? nullptr : node->m_group;
};
clobber_group *group = splay_tree::splay_and_search (this, nullptr,
find_group);
gcc_checking_assert (m_parent);
// If the previous splay operation did anything, this clobber is now an
// ancestor of CURSOR, and all the nodes inbetween have a stale group.
// Since we have visited the nodes, we might as well update them too.
//
// If the previous splay operation did nothing, start the update from
// this clobber instead. In that case we change at most two clobbers:
// this clobber and possibly its parent.
if (cursor == m_parent)
cursor = this;
// Walk up the tree from CURSOR updating clobbers that need it.
// This walk always includes this clobber.
while (cursor->m_group != group)
{
cursor->m_group = group;
cursor = cursor->m_parent;
}
gcc_checking_assert (m_group == group);
return group;
}
// See the comment above the declaration.
void
resource_info::print_identifier (pretty_printer *pp) const
{
if (is_mem ())
pp_string (pp, "mem");
else
{
char tmp[3 * sizeof (regno) + 2];
snprintf (tmp, sizeof (tmp), "r%d", regno);
pp_string (pp, tmp);
}
}
// See the comment above the declaration.
void
resource_info::print_context (pretty_printer *pp) const
{
if (HARD_REGISTER_NUM_P (regno))
{
if (const char *name = reg_names[regno])
{
pp_space (pp);
pp_left_paren (pp);
pp_string (pp, name);
if (mode != E_BLKmode)
{
pp_colon (pp);
pp_string (pp, GET_MODE_NAME (mode));
}
pp_right_paren (pp);
}
}
else if (is_reg ())
{
pp_space (pp);
pp_left_paren (pp);
if (mode != E_BLKmode)
{
pp_string (pp, GET_MODE_NAME (mode));
pp_space (pp);
}
pp_string (pp, "pseudo");
pp_right_paren (pp);
}
}
// See the comment above the declaration.
void
resource_info::print (pretty_printer *pp) const
{
print_identifier (pp);
print_context (pp);
}
// Some properties can naturally be described using adjectives that attach
// to nouns like "use" or "definition". Print such adjectives to PP.
void
access_info::print_prefix_flags (pretty_printer *pp) const
{
if (m_is_temp)
pp_string (pp, "temporary ");
if (m_has_been_superceded)
pp_string (pp, "superceded ");
}
// Print properties not handled by print_prefix_flags to PP, putting
// each property on a new line indented by two extra spaces.
void
access_info::print_properties_on_new_lines (pretty_printer *pp) const
{
if (m_is_pre_post_modify)
{
pp_newline_and_indent (pp, 2);
pp_string (pp, "set by a pre/post-modify");
pp_indentation (pp) -= 2;
}
if (m_includes_address_uses)
{
pp_newline_and_indent (pp, 2);
pp_string (pp, "appears inside an address");
pp_indentation (pp) -= 2;
}
if (m_includes_read_writes)
{
pp_newline_and_indent (pp, 2);
pp_string (pp, "appears in a read/write context");
pp_indentation (pp) -= 2;
}
if (m_includes_subregs)
{
pp_newline_and_indent (pp, 2);
pp_string (pp, "appears inside a subreg");
pp_indentation (pp) -= 2;
}
}
// Return true if there are no known issues with the integrity of the
// link information.
inline bool
use_info::check_integrity ()
{
auto subsequence_id = [](use_info *use)
{
if (use->is_in_nondebug_insn ())
return 1;
if (use->is_in_debug_insn ())
return 2;
return 3;
};
use_info *prev = prev_use ();
use_info *next = next_use ();
if (prev && subsequence_id (prev) > subsequence_id (this))
return false;
if (next && subsequence_id (next) < subsequence_id (this))
return false;
if (m_is_last_nondebug_insn_use != calculate_is_last_nondebug_insn_use ())
return false;
if (!prev && last_use ()->next_use ())
return false;
if (!next)
if (use_info *use = last_nondebug_insn_use ())
if (!use->m_is_last_nondebug_insn_use)
return false;
return true;
}
// See the comment above the declaration.
void
use_info::print_location (pretty_printer *pp) const
{
if (is_in_phi ())
pp_access (pp, phi (), PP_ACCESS_INCLUDE_LOCATION);
else
insn ()->print_identifier_and_location (pp);
}
// See the comment above the declaration.
void
use_info::print_def (pretty_printer *pp) const
{
if (const set_info *set = def ())
pp_access (pp, set, 0);
else
{
pp_string (pp, "undefined ");
resource ().print (pp);
}
}
// See the comment above the declaration.
void
use_info::print (pretty_printer *pp, unsigned int flags) const
{
print_prefix_flags (pp);
const set_info *set = def ();
if (set && set->mode () != mode ())
{
pp_string (pp, GET_MODE_NAME (mode ()));
pp_space (pp);
}
pp_string (pp, "use of ");
print_def (pp);
if (flags & PP_ACCESS_INCLUDE_LOCATION)
{
pp_string (pp, " by ");
print_location (pp);
}
if (set && (flags & PP_ACCESS_INCLUDE_LINKS))
{
pp_newline_and_indent (pp, 2);
pp_string (pp, "defined in ");
set->insn ()->print_location (pp);
pp_indentation (pp) -= 2;
}
if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
print_properties_on_new_lines (pp);
}
// See the comment above the declaration.
void
def_info::print_identifier (pretty_printer *pp) const
{
resource ().print_identifier (pp);
pp_colon (pp);
insn ()->print_identifier (pp);
resource ().print_context (pp);
}
// See the comment above the declaration.
void
def_info::print_location (pretty_printer *pp) const
{
insn ()->print_identifier_and_location (pp);
}
// See the comment above the declaration.
void
clobber_info::print (pretty_printer *pp, unsigned int flags) const
{
print_prefix_flags (pp);
if (is_call_clobber ())
pp_string (pp, "call ");
pp_string (pp, "clobber ");
print_identifier (pp);
if (flags & PP_ACCESS_INCLUDE_LOCATION)
{
pp_string (pp, " in ");
insn ()->print_location (pp);
}
if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
print_properties_on_new_lines (pp);
}
// See the comment above the declaration.
void
set_info::print_uses_on_new_lines (pretty_printer *pp) const
{
for (const use_info *use : all_uses ())
{
pp_newline_and_indent (pp, 2);
if (use->is_live_out_use ())
{
pp_string (pp, "live out from ");
use->insn ()->print_location (pp);
}
else
{
pp_string (pp, "used by ");
use->print_location (pp);
}
pp_indentation (pp) -= 2;
}
if (m_use_tree)
{
pp_newline_and_indent (pp, 2);
pp_string (pp, "splay tree:");
pp_newline_and_indent (pp, 2);
auto print_use = [](pretty_printer *pp,
splay_tree_node<use_info *> *node)
{
pp_string (pp, "use by ");
node->value ()->print_location (pp);
};
m_use_tree.print (pp, m_use_tree.root (), print_use);
pp_indentation (pp) -= 4;
}
}
// See the comment above the declaration.
void
set_info::print (pretty_printer *pp, unsigned int flags) const
{
print_prefix_flags (pp);
pp_string (pp, "set ");
print_identifier (pp);
if (flags & PP_ACCESS_INCLUDE_LOCATION)
{
pp_string (pp, " in ");
insn ()->print_location (pp);
}
if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
print_properties_on_new_lines (pp);
if (flags & PP_ACCESS_INCLUDE_LINKS)
print_uses_on_new_lines (pp);
}
// See the comment above the declaration.
void
phi_info::print (pretty_printer *pp, unsigned int flags) const
{
print_prefix_flags (pp);
pp_string (pp, "phi node ");
print_identifier (pp);
if (flags & PP_ACCESS_INCLUDE_LOCATION)
{
pp_string (pp, " in ");
insn ()->print_location (pp);
}
if (flags & PP_ACCESS_INCLUDE_PROPERTIES)
print_properties_on_new_lines (pp);
if (flags & PP_ACCESS_INCLUDE_LINKS)
{
basic_block cfg_bb = bb ()->cfg_bb ();
pp_newline_and_indent (pp, 2);
pp_string (pp, "inputs:");
unsigned int i = 0;
for (const use_info *input : inputs ())
{
basic_block pred_cfg_bb = EDGE_PRED (cfg_bb, i)->src;
pp_newline_and_indent (pp, 2);
pp_string (pp, "bb");
pp_decimal_int (pp, pred_cfg_bb->index);
pp_colon (pp);
pp_space (pp);
input->print_def (pp);
pp_indentation (pp) -= 2;
i += 1;
}
pp_indentation (pp) -= 2;
print_uses_on_new_lines (pp);
}
}
// See the comment above the declaration.
void
set_node::print (pretty_printer *pp) const
{
pp_access (pp, first_def ());
}
// See the comment above the declaration.
void
clobber_group::print (pretty_printer *pp) const
{
auto print_clobber = [](pretty_printer *pp, const def_info *clobber)
{
pp_access (pp, clobber);
};
pp_string (pp, "grouped clobber");
for (const def_info *clobber : clobbers ())
{
pp_newline_and_indent (pp, 2);
print_clobber (pp, clobber);
pp_indentation (pp) -= 2;
}
pp_newline_and_indent (pp, 2);
pp_string (pp, "splay tree");
pp_newline_and_indent (pp, 2);
m_clobber_tree.print (pp, print_clobber);
pp_indentation (pp) -= 4;
}
// Return a clobber_group for CLOBBER, creating one if CLOBBER doesn't
// already belong to a group.
clobber_group *
function_info::need_clobber_group (clobber_info *clobber)
{
if (clobber->is_in_group ())
return clobber->group ();
return allocate<clobber_group> (clobber);
}
// Return a def_node for inserting DEF into the associated resource's
// splay tree. Use a clobber_group if DEF is a clobber and a set_node
// otherwise.
def_node *
function_info::need_def_node (def_info *def)
{
if (auto *clobber = dyn_cast<clobber_info *> (def))
return need_clobber_group (clobber);
return allocate<set_node> (as_a<set_info *> (def));
}
// LAST is the last thing to define LAST->resource (), and is where any
// splay tree root for LAST->resource () is stored. Require such a splay tree
// to exist, creating a new one if necessary. Return the root of the tree.
//
// The caller must call LAST->set_splay_root after it has finished with
// the splay tree.
def_splay_tree
function_info::need_def_splay_tree (def_info *last)
{
if (def_node *root = last->splay_root ())
return root;
// Use a left-spine rooted at the last node.
def_node *root = need_def_node (last);
def_node *parent = root;
while (def_info *prev = first_def (parent)->prev_def ())
{
def_node *node = need_def_node (prev);
def_splay_tree::insert_child (parent, 0, node);
parent = node;
}
return root;
}
// Search TREE for either:
//
// - a set_info at INSN or
// - a clobber_group whose range includes INSN
//
// If such a node exists, install it as the root of TREE and return 0.
// Otherwise arbitrarily choose between:
//
// (1) Installing the closest preceding node as the root and returning 1.
// (2) Installing the closest following node as the root and returning -1.
//
// Note that this routine should not be used to check whether INSN
// itself defines a resource; that can be checked more cheaply using
// find_access_index.
int
rtl_ssa::lookup_def (def_splay_tree &tree, insn_info *insn)
{
auto go_left = [&](def_node *node)
{
return *insn < *first_def (node)->insn ();
};
auto go_right = [&](def_node *node)
{
return *insn > *last_def (node)->insn ();
};
return tree.lookup (go_left, go_right);
}
// Search TREE for a clobber in INSN. If such a clobber exists, install
// it as the root of TREE and return 0. Otherwise arbitrarily choose between:
//
// (1) Installing the closest preceding clobber as the root and returning 1.
// (2) Installing the closest following clobber as the root and returning -1.
int
rtl_ssa::lookup_clobber (clobber_tree &tree, insn_info *insn)
{
auto compare = [&](clobber_info *clobber)
{
return insn->compare_with (clobber->insn ());
};
return tree.lookup (compare);
}
// Search for a definition of RESOURCE at INSN and return the result of
// the search as a def_lookup. See the comment above the class for more
// details.
def_lookup
function_info::find_def (resource_info resource, insn_info *insn)
{
def_info *first = m_defs[resource.regno + 1];
if (!first)
// There are no nodes. The comparison result is pretty meaningless
// in this case.
return { nullptr, -1 };
// See whether the first node matches.
auto first_result = clobber_group_or_single_def (first);
if (*insn <= *last_def (first_result)->insn ())
{
int comparison = (*insn >= *first->insn () ? 0 : -1);
return { first_result, comparison };
}
// See whether the last node matches.
def_info *last = first->last_def ();
auto last_result = clobber_group_or_single_def (last);
if (*insn >= *first_def (last_result)->insn ())
{
int comparison = (*insn <= *last->insn () ? 0 : 1);
return { last_result, comparison };
}
// Resort to using a splay tree to search for the result.
def_splay_tree tree = need_def_splay_tree (last);
int comparison = lookup_def (tree, insn);
last->set_splay_root (tree.root ());
return { tree.root (), comparison };
}
// Add DEF to the function's list of definitions of DEF->resource (),
// inserting DEF immediately before BEFORE. DEF is not currently in the list.
void
function_info::insert_def_before (def_info *def, def_info *before)
{
gcc_checking_assert (!def->has_def_links ()
&& *before->insn () > *def->insn ());
def->copy_prev_from (before);
if (def_info *prev = def->prev_def ())
{
gcc_checking_assert (*prev->insn () < *def->insn ());
prev->set_next_def (def);
}
else
m_defs[def->regno () + 1] = def;
def->set_next_def (before);
before->set_prev_def (def);
}
// Add DEF to the function's list of definitions of DEF->resource (),
// inserting DEF immediately after AFTER. DEF is not currently in the list.
void
function_info::insert_def_after (def_info *def, def_info *after)
{
gcc_checking_assert (!def->has_def_links ()
&& *after->insn () < *def->insn ());
def->copy_next_from (after);
if (def_info *next = def->next_def ())
{
gcc_checking_assert (*next->insn () > *def->insn ());
next->set_prev_def (def);
}
else
m_defs[def->regno () + 1]->set_last_def (def);
def->set_prev_def (after);
after->set_next_def (def);
}
// Remove DEF from the function's list of definitions of DEF->resource ().
void
function_info::remove_def_from_list (def_info *def)
{
def_info *prev = def->prev_def ();
def_info *next = def->next_def ();
if (next)
next->copy_prev_from (def);
else
m_defs[def->regno () + 1]->set_last_def (prev);
if (prev)
prev->copy_next_from (def);
else
m_defs[def->regno () + 1] = next;
def->clear_def_links ();
}
// Add CLOBBER to GROUP and insert it into the function's list of
// accesses to CLOBBER->resource (). CLOBBER is not currently part
// of an active group and is not currently in the list.
void
function_info::add_clobber (clobber_info *clobber, clobber_group *group)
{
// Search for either the previous or next clobber in the group.
// The result is less than zero if CLOBBER should come before NEIGHBOR
// or greater than zero if CLOBBER should come after NEIGHBOR.
int comparison = lookup_clobber (group->m_clobber_tree, clobber->insn ());
gcc_checking_assert (comparison != 0);
clobber_info *neighbor = group->m_clobber_tree.root ();
// Since HEIGHBOR is now the root of the splay tree, its group needs
// to be up-to-date.
neighbor->update_group (group);
// If CLOBBER comes before NEIGHBOR, insert CLOBBER to NEIGHBOR's left,
// otherwise insert CLOBBER to NEIGHBOR's right.
clobber_info::splay_tree::insert_child (neighbor, comparison > 0, clobber);
clobber->set_group (group);
// Insert the clobber into the function-wide list and update the
// bounds of the group.
if (comparison > 0)
{
insert_def_after (clobber, neighbor);
if (neighbor == group->last_clobber ())
group->set_last_clobber (clobber);
}
else
{
insert_def_before (clobber, neighbor);
if (neighbor == group->first_clobber ())
group->set_first_clobber (clobber);
}
}
// Remove CLOBBER from GROUP, given that GROUP contains other clobbers too.
// Also remove CLOBBER from the function's list of accesses to
// CLOBBER->resource ().
void
function_info::remove_clobber (clobber_info *clobber, clobber_group *group)
{
if (clobber == group->first_clobber ())
{
auto *new_first = as_a<clobber_info *> (clobber->next_def ());
group->set_first_clobber (new_first);
new_first->update_group (group);
}
else if (clobber == group->last_clobber ())
{
auto *new_last = as_a<clobber_info *> (clobber->prev_def ());
group->set_last_clobber (new_last);
new_last->update_group (group);
}
clobber_info *replacement = clobber_info::splay_tree::remove_node (clobber);
if (clobber == group->m_clobber_tree.root ())
{
group->m_clobber_tree = replacement;
replacement->update_group (group);
}
clobber->set_group (nullptr);
remove_def_from_list (clobber);
}
// Add CLOBBER immediately before the first clobber in GROUP, given that
// CLOBBER is not currently part of any group.
void
function_info::prepend_clobber_to_group (clobber_info *clobber,
clobber_group *group)
{
clobber_info *next = group->first_clobber ();
clobber_info::splay_tree::insert_child (next, 0, clobber);
group->set_first_clobber (clobber);
clobber->set_group (group);
}
// Add CLOBBER immediately after the last clobber in GROUP, given that
// CLOBBER is not currently part of any group.
void
function_info::append_clobber_to_group (clobber_info *clobber,
clobber_group *group)
{
clobber_info *prev = group->last_clobber ();
clobber_info::splay_tree::insert_child (prev, 1, clobber);
group->set_last_clobber (clobber);
clobber->set_group (group);
}
// Put CLOBBER1 and CLOBBER2 into the same clobber_group, given that
// CLOBBER1 occurs immediately before CLOBBER2 and that the two clobbers
// are not currently in the same group. LAST is the last definition of
// the associated resource, and is where any splay tree is stored.
void
function_info::merge_clobber_groups (clobber_info *clobber1,
clobber_info *clobber2,
def_info *last)
{
if (clobber1->is_in_group () && clobber2->is_in_group ())
{
clobber_group *group1 = clobber1->group ();
clobber_group *group2 = clobber2->group ();
gcc_checking_assert (clobber1 == group1->last_clobber ()
&& clobber2 == group2->first_clobber ());
if (def_splay_tree tree = last->splay_root ())
{
// Remove GROUP2 from the splay tree.
int comparison = lookup_def (tree, clobber2->insn ());
gcc_checking_assert (comparison == 0);
tree.remove_root ();
last->set_splay_root (tree.root ());
}
// Splice the trees together.
group1->m_clobber_tree.splice_next_tree (group2->m_clobber_tree);
// Bring the two extremes of GROUP2 under GROUP1. Any other
// clobbers in the group are updated lazily on demand.
clobber2->set_group (group1);
group2->last_clobber ()->set_group (group1);
group1->set_last_clobber (group2->last_clobber ());
// Record that GROUP2 is no more.
group2->set_first_clobber (nullptr);
group2->set_last_clobber (nullptr);
group2->m_clobber_tree = nullptr;
}
else
{
// In this case there can be no active splay tree.
gcc_assert (!last->splay_root ());
if (clobber2->is_in_group ())
prepend_clobber_to_group (clobber1, clobber2->group ());
else
append_clobber_to_group (clobber2, need_clobber_group (clobber1));
}
}
// GROUP spans INSN, and INSN now sets the resource that GROUP clobbers.
// Split GROUP around INSN and return the clobber that comes immediately
// before INSN.
clobber_info *
function_info::split_clobber_group (clobber_group *group, insn_info *insn)
{
// Search for either the previous or next clobber in the group.
// The result is less than zero if CLOBBER should come before NEIGHBOR
// or greater than zero if CLOBBER should come after NEIGHBOR.
int comparison = lookup_clobber (group->m_clobber_tree, insn);
gcc_checking_assert (comparison != 0);
clobber_info *neighbor = group->m_clobber_tree.root ();
clobber_tree tree1, tree2;
clobber_info *prev;
clobber_info *next;
if (comparison > 0)
{
// NEIGHBOR is the last clobber in what will become the first group.
tree1 = neighbor;
tree2 = tree1.split_after_root ();
prev = neighbor;
next = as_a<clobber_info *> (prev->next_def ());
}
else
{
// NEIGHBOR is the first clobber in what will become the second group.
tree2 = neighbor;
tree1 = tree2.split_before_root ();
next = neighbor;
prev = as_a<clobber_info *> (next->prev_def ());
}
// Use GROUP to hold PREV and earlier clobbers. Create a new group for
// NEXT onwards.
clobber_info *last_clobber = group->last_clobber ();
clobber_group *group1 = group;
clobber_group *group2 = allocate<clobber_group> (next);
// Finish setting up GROUP1, making sure that the roots and extremities
// have a correct group pointer. Leave the rest to be updated lazily.
group1->set_last_clobber (prev);
tree1->set_group (group1);
prev->set_group (group1);
// Finish setting up GROUP2, with the same approach as for GROUP1.
group2->set_first_clobber (next);
group2->set_last_clobber (last_clobber);
next->set_group (group2);
tree2->set_group (group2);
last_clobber->set_group (group2);
return prev;
}
// Add DEF to the end of the function's list of definitions of
// DEF->resource (). There is known to be no associated splay tree yet.
void
function_info::append_def (def_info *def)
{
gcc_checking_assert (!def->has_def_links ());
def_info **head = &m_defs[def->regno () + 1];
def_info *first = *head;
if (!first)
{
// This is the only definition of the resource.
def->set_last_def (def);
*head = def;
return;
}
def_info *prev = first->last_def ();
gcc_checking_assert (!prev->splay_root ());
// Maintain the invariant that two clobbers must not appear in
// neighboring nodes of the splay tree.
auto *clobber = dyn_cast<clobber_info *> (def);
auto *prev_clobber = dyn_cast<clobber_info *> (prev);
if (clobber && prev_clobber)
append_clobber_to_group (clobber, need_clobber_group (prev_clobber));
prev->set_next_def (def);
def->set_prev_def (prev);
first->set_last_def (def);
}
// Add DEF to the function's list of definitions of DEF->resource ().
// Also insert it into the associated splay tree, if there is one.
// DEF is not currently part of the list and is not in the splay tree.
void
function_info::add_def (def_info *def)
{
gcc_checking_assert (!def->has_def_links ()
&& !def->m_is_temp
&& !def->m_has_been_superceded);
def_info **head = &m_defs[def->regno () + 1];
def_info *first = *head;
if (!first)
{
// This is the only definition of the resource.
def->set_last_def (def);
*head = def;
return;
}
def_info *last = first->last_def ();
insn_info *insn = def->insn ();
int comparison;
def_node *root = nullptr;
def_info *prev = nullptr;
def_info *next = nullptr;
if (*insn > *last->insn ())
{
// This definition comes after all other definitions.
comparison = 1;
if (def_splay_tree tree = last->splay_root ())
{
tree.splay_max_node ();
root = tree.root ();
last->set_splay_root (root);
}
prev = last;
}
else if (*insn < *first->insn ())
{
// This definition comes before all other definitions.
comparison = -1;
if (def_splay_tree tree = last->splay_root ())
{
tree.splay_min_node ();
root = tree.root ();
last->set_splay_root (root);
}
next = first;
}
else
{
// Search the splay tree for an insertion point.
def_splay_tree tree = need_def_splay_tree (last);
comparison = lookup_def (tree, insn);
root = tree.root ();
last->set_splay_root (root);
// Deal with cases in which we found an overlapping live range.
if (comparison == 0)
{
auto *group = as_a<clobber_group *> (tree.root ());
if (auto *clobber = dyn_cast<clobber_info *> (def))
{
add_clobber (clobber, group);
return;
}
prev = split_clobber_group (group, insn);
next = prev->next_def ();
}
// COMPARISON is < 0 if DEF comes before ROOT or > 0 if DEF comes
// after ROOT.
else if (comparison < 0)
{
next = first_def (root);
prev = next->prev_def ();
}
else
{
prev = last_def (root);
next = prev->next_def ();
}
}
// See if we should merge CLOBBER with a neighboring clobber.
auto *clobber = dyn_cast<clobber_info *> (def);
auto *prev_clobber = safe_dyn_cast<clobber_info *> (prev);
auto *next_clobber = safe_dyn_cast<clobber_info *> (next);
// We shouldn't have consecutive clobber_groups.
gcc_checking_assert (!(clobber && prev_clobber && next_clobber));
if (clobber && prev_clobber)
append_clobber_to_group (clobber, need_clobber_group (prev_clobber));
else if (clobber && next_clobber)
prepend_clobber_to_group (clobber, need_clobber_group (next_clobber));
else if (root)
{
// If DEF comes before ROOT, insert DEF to ROOT's left,
// otherwise insert DEF to ROOT's right.
def_node *node = need_def_node (def);
def_splay_tree::insert_child (root, comparison >= 0, node);
}
if (prev)
insert_def_after (def, prev);
else
insert_def_before (def, next);
}
// Remove DEF from the function's list of definitions of DEF->resource ().
// Also remove DEF from the associated splay tree, if there is one.
void
function_info::remove_def (def_info *def)
{
def_info **head = &m_defs[def->regno () + 1];
def_info *first = *head;
gcc_checking_assert (first);
if (first->is_last_def ())
{
// DEF is the only definition of the resource.
gcc_checking_assert (first == def);
*head = nullptr;
def->clear_def_links ();
return;
}
// If CLOBBER belongs to a clobber_group that contains other clobbers
// too, then we need to update the clobber_group and the list, but any
// splay tree that contains the clobber_group is unaffected.
if (auto *clobber = dyn_cast<clobber_info *> (def))
if (clobber->is_in_group ())
{
clobber_group *group = clobber->group ();
if (group->first_clobber () != group->last_clobber ())
{
remove_clobber (clobber, group);
return;
}
}
// If we've created a splay tree for this resource, remove the entry
// for DEF.
def_info *last = first->last_def ();
if (def_splay_tree tree = last->splay_root ())
{
int comparison = lookup_def (tree, def->insn ());
gcc_checking_assert (comparison == 0);
tree.remove_root ();
last->set_splay_root (tree.root ());
}
// If the definition came between two clobbers, merge them into a single
// group.
auto *prev_clobber = safe_dyn_cast<clobber_info *> (def->prev_def ());
auto *next_clobber = safe_dyn_cast<clobber_info *> (def->next_def ());
if (prev_clobber && next_clobber)
merge_clobber_groups (prev_clobber, next_clobber, last);
remove_def_from_list (def);
}
// Require DEF to have a splay tree that contains all non-phi uses.
void
function_info::need_use_splay_tree (set_info *def)
{
if (!def->m_use_tree)
for (use_info *use : def->all_insn_uses ())
{
auto *use_node = allocate<splay_tree_node<use_info *>> (use);
def->m_use_tree.insert_max_node (use_node);
}
}
// Compare two instructions by their position in a use splay tree. Return >0
// if INSN1 comes after INSN2, <0 if INSN1 comes before INSN2, or 0 if they are
// the same instruction.
static inline int
compare_use_insns (insn_info *insn1, insn_info *insn2)
{
// Debug instructions go after nondebug instructions.
int diff = insn1->is_debug_insn () - insn2->is_debug_insn ();
if (diff != 0)
return diff;
return insn1->compare_with (insn2);
}
// Search TREE for a use in INSN. If such a use exists, install it as
// the root of TREE and return 0. Otherwise arbitrarily choose between:
//
// (1) Installing the closest preceding use as the root and returning 1.
// (2) Installing the closest following use as the root and returning -1.
int
rtl_ssa::lookup_use (splay_tree<use_info *> &tree, insn_info *insn)
{
auto compare = [&](splay_tree_node<use_info *> *node)
{
return compare_use_insns (insn, node->value ()->insn ());
};
return tree.lookup (compare);
}
// Add USE to USE->def ()'s list of uses. inserting USE immediately before
// BEFORE. USE is not currently in the list.
//
// This routine should not be used for inserting phi uses.
void
function_info::insert_use_before (use_info *use, use_info *before)
{
gcc_checking_assert (!use->has_use_links () && use->is_in_any_insn ());
set_info *def = use->def ();
use->copy_prev_from (before);
use->set_next_use (before);
if (use_info *prev = use->prev_use ())
prev->set_next_use (use);
else
use->def ()->set_first_use (use);
before->set_prev_use (use);
if (use->is_in_nondebug_insn () && before->is_in_debug_insn_or_phi ())
def->last_use ()->set_last_nondebug_insn_use (use);
gcc_checking_assert (use->check_integrity () && before->check_integrity ());
}
// Add USE to USE->def ()'s list of uses. inserting USE immediately after
// AFTER. USE is not currently in the list.
//
// This routine should not be used for inserting phi uses.
void
function_info::insert_use_after (use_info *use, use_info *after)
{
set_info *def = use->def ();
gcc_checking_assert (after->is_in_any_insn ()
&& !use->has_use_links ()
&& use->is_in_any_insn ());
use->set_prev_use (after);
use->copy_next_from (after);
after->set_next_use (use);
if (use_info *next = use->next_use ())
{
// The last node doesn't change, but we might need to update its
// last_nondebug_insn_use record.
if (use->is_in_nondebug_insn () && next->is_in_debug_insn_or_phi ())
def->last_use ()->set_last_nondebug_insn_use (use);
next->set_prev_use (use);
}
else
{
// USE is now the last node.
if (use->is_in_nondebug_insn ())
use->set_last_nondebug_insn_use (use);
def->first_use ()->set_last_use (use);
}
gcc_checking_assert (use->check_integrity () && after->check_integrity ());
}
// If USE has a known definition, add USE to that definition's list of uses.
// Also update the associated splay tree, if any.
void
function_info::add_use (use_info *use)
{
gcc_checking_assert (!use->has_use_links ()
&& !use->m_is_temp
&& !use->m_has_been_superceded);
set_info *def = use->def ();
if (!def)
return;
use_info *first = def->first_use ();
if (!first)
{
// This is the only use of the definition.
use->set_last_use (use);
if (use->is_in_nondebug_insn ())
use->set_last_nondebug_insn_use (use);
def->set_first_use (use);
gcc_checking_assert (use->check_integrity ());
return;
}
if (use->is_in_phi ())
{
// Add USE at the end of the list, as the new first phi.
use_info *last = first->last_use ();
use->set_prev_use (last);
use->copy_next_from (last);
last->set_next_use (use);
first->set_last_use (use);
gcc_checking_assert (use->check_integrity ());
return;
}
// If there is currently no splay tree for this definition, see if can
// get away with a pure list-based update.
insn_info *insn = use->insn ();
auto quick_path = [&]()
{
// Check if USE should come before all current uses.
if (first->is_in_phi () || compare_use_insns (insn, first->insn ()) < 0)
{
insert_use_before (use, first);
return true;
}
// Check if USE should come after all current uses in the same
// subsequence (i.e. the list of nondebug insn uses or the list
// of debug insn uses).
use_info *last = first->last_use ();
if (use->is_in_debug_insn ())
{
if (last->is_in_phi ())
return false;
}
else
last = last->last_nondebug_insn_use ();
if (compare_use_insns (insn, last->insn ()) > 0)
{
insert_use_after (use, last);
return true;
}
return false;
};
if (!def->m_use_tree && quick_path ())
return;
// Search the splay tree for an insertion point. COMPARISON is less
// than zero if USE should come before NEIGHBOR, or greater than zero
// if USE should come after NEIGHBOR.
need_use_splay_tree (def);
int comparison = lookup_use (def->m_use_tree, insn);
gcc_checking_assert (comparison != 0);
splay_tree_node<use_info *> *neighbor = def->m_use_tree.root ();
// If USE comes before NEIGHBOR, insert USE to NEIGHBOR's left,
// otherwise insert USE to NEIGHBOR's right.
auto *use_node = allocate<splay_tree_node<use_info *>> (use);
def->m_use_tree.insert_child (neighbor, comparison > 0, use_node);
if (comparison > 0)
insert_use_after (use, neighbor->value ());
else
insert_use_before (use, neighbor->value ());
}
// If USE has a known definition, remove USE from that definition's list
// of uses. Also remove if it from the associated splay tree, if any.
void
function_info::remove_use (use_info *use)
{
set_info *def = use->def ();
if (!def)
return;
// Remove USE from the splay tree.
if (def->m_use_tree && use->is_in_any_insn ())
{
int comparison = lookup_use (def->m_use_tree, use->insn ());
gcc_checking_assert (comparison == 0);
def->m_use_tree.remove_root ();
}
use_info *prev = use->prev_use ();
use_info *next = use->next_use ();
use_info *first = def->first_use ();
use_info *last = first->last_use ();
if (last->last_nondebug_insn_use () == use)
last->set_last_nondebug_insn_use (prev);
if (next)
next->copy_prev_from (use);
else
first->set_last_use (prev);
if (prev)
prev->copy_next_from (use);
else
def->set_first_use (next);
use->clear_use_links ();
gcc_checking_assert ((!prev || prev->check_integrity ())
&& (!next || next->check_integrity ()));
}
// Allocate a temporary clobber_info for register REGNO in insn INSN,
// including it in the region of the obstack governed by WATERMARK.
// Return a new def_array that contains OLD_DEFS and the new clobber.
//
// OLD_DEFS is known not to define REGNO.
def_array
function_info::insert_temp_clobber (obstack_watermark &watermark,
insn_info *insn, unsigned int regno,
def_array old_defs)
{
gcc_checking_assert (watermark == &m_temp_obstack);
auto *clobber = allocate_temp<clobber_info> (insn, regno);
clobber->m_is_temp = true;
return insert_access (watermark, clobber, old_defs);
}
// A subroutine of make_uses_available. Try to make USE's definition
// available at the head of BB. WILL_BE_DEBUG_USE is true if the
// definition will be used only in debug instructions.
//
// On success:
//
// - If the use would have the same def () as USE, return USE.
//
// - If BB already has a degenerate phi for the same definition,
// return a temporary use of that phi.
//
// - Otherwise, the use would need a new degenerate phi. Allocate a
// temporary phi and return a temporary use of it.
//
// Return null on failure.
use_info *
function_info::make_use_available (use_info *use, bb_info *bb,
bool will_be_debug_use)
{
set_info *def = use->def ();
if (!def)
return use;
if (is_single_dominating_def (def))
return use;
// FIXME: Deliberately limited for fwprop compatibility testing.
basic_block cfg_bb = bb->cfg_bb ();
bb_info *use_bb = use->bb ();
if (single_pred_p (cfg_bb)
&& single_pred (cfg_bb) == use_bb->cfg_bb ()
&& remains_available_on_exit (def, use_bb))
{
if (def->ebb () == bb->ebb () || will_be_debug_use)
return use;
resource_info resource = use->resource ();
set_info *ultimate_def = look_through_degenerate_phi (def);
// See if there is already a (degenerate) phi for DEF.
insn_info *phi_insn = bb->ebb ()->phi_insn ();
phi_info *phi;
def_lookup dl = find_def (resource, phi_insn);
if (set_info *set = dl.matching_set ())
{
// There is an existing phi.
phi = as_a<phi_info *> (set);
gcc_checking_assert (phi->input_value (0) == ultimate_def);
}
else
{
// Create a temporary placeholder phi. This will become
// permanent if the change is later committed.
phi = allocate_temp<phi_info> (phi_insn, resource, 0);
auto *input = allocate_temp<use_info> (phi, resource, ultimate_def);
input->m_is_temp = true;
phi->m_is_temp = true;
phi->make_degenerate (input);
if (def_info *prev = dl.prev_def ())
phi->set_prev_def (prev);
if (def_info *next = dl.next_def ())
phi->set_next_def (next);
}
// Create a temporary use of the phi at the head of the first
// block, since we know for sure that it's available there.
insn_info *use_insn = bb->ebb ()->first_bb ()->head_insn ();
auto *new_use = allocate_temp<use_info> (use_insn, resource, phi);
new_use->m_is_temp = true;
return new_use;
}
return nullptr;
}
// See the comment above the declaration.
use_array
function_info::make_uses_available (obstack_watermark &watermark,
use_array uses, bb_info *bb,
bool will_be_debug_uses)
{
unsigned int num_uses = uses.size ();
if (num_uses == 0)
return uses;
auto **new_uses = XOBNEWVEC (watermark, access_info *, num_uses);
for (unsigned int i = 0; i < num_uses; ++i)
{
use_info *use = make_use_available (uses[i], bb, will_be_debug_uses);
if (!use)
return use_array (access_array::invalid ());
new_uses[i] = use;
}
return use_array (new_uses, num_uses);
}
// Return true if ACCESS1 can represent ACCESS2 and if ACCESS2 can
// represent ACCESS1.
static bool
can_merge_accesses (access_info *access1, access_info *access2)
{
if (access1 == access2)
return true;
auto *use1 = dyn_cast<use_info *> (access1);
auto *use2 = dyn_cast<use_info *> (access2);
return use1 && use2 && use1->def () == use2->def ();
}
// See the comment above the declaration.
access_array
rtl_ssa::merge_access_arrays_base (obstack_watermark &watermark,
access_array accesses1,
access_array accesses2)
{
if (accesses1.empty ())
return accesses2;
if (accesses2.empty ())
return accesses1;
auto i1 = accesses1.begin ();
auto end1 = accesses1.end ();
auto i2 = accesses2.begin ();
auto end2 = accesses2.end ();
access_array_builder builder (watermark);
builder.reserve (accesses1.size () + accesses2.size ());
while (i1 != end1 && i2 != end2)
{
access_info *access1 = *i1;
access_info *access2 = *i2;
unsigned int regno1 = access1->regno ();
unsigned int regno2 = access2->regno ();
if (regno1 == regno2)
{
if (!can_merge_accesses (access1, access2))
return access_array::invalid ();
builder.quick_push (access1);
++i1;
++i2;
}
else if (regno1 < regno2)
{
builder.quick_push (access1);
++i1;
}
else
{
builder.quick_push (access2);
++i2;
}
}
for (; i1 != end1; ++i1)
builder.quick_push (*i1);
for (; i2 != end2; ++i2)
builder.quick_push (*i2);
return builder.finish ();
}
// See the comment above the declaration.
access_array
rtl_ssa::insert_access_base (obstack_watermark &watermark,
access_info *access1, access_array accesses2)
{
access_array_builder builder (watermark);
builder.reserve (1 + accesses2.size ());
unsigned int regno1 = access1->regno ();
auto i2 = accesses2.begin ();
auto end2 = accesses2.end ();
while (i2 != end2)
{
access_info *access2 = *i2;
unsigned int regno2 = access2->regno ();
if (regno1 == regno2)
{
if (!can_merge_accesses (access1, access2))
return access_array::invalid ();
builder.quick_push (access1);
access1 = nullptr;
++i2;
break;
}
else if (regno1 < regno2)
{
builder.quick_push (access1);
access1 = nullptr;
break;
}
else
{
builder.quick_push (access2);
++i2;
}
}
if (access1)
builder.quick_push (access1);
for (; i2 != end2; ++i2)
builder.quick_push (*i2);
return builder.finish ();
}
// See the comment above the declaration.
access_array
rtl_ssa::remove_note_accesses_base (obstack_watermark &watermark,
access_array accesses)
{
for (access_info *access : accesses)
if (access->only_occurs_in_notes ())
{
access_array_builder builder (watermark);
builder.reserve (accesses.size ());
for (access_info *access2 : accesses)
if (!access2->only_occurs_in_notes ())
builder.quick_push (access2);
return builder.finish ();
}
return accesses;
}
// Print RESOURCE to PP.
void
rtl_ssa::pp_resource (pretty_printer *pp, resource_info resource)
{
resource.print (pp);
}
// Print ACCESS to PP. FLAGS is a bitmask of PP_ACCESS_* flags.
void
rtl_ssa::pp_access (pretty_printer *pp, const access_info *access,
unsigned int flags)
{
if (!access)
pp_string (pp, "<null>");
else if (auto *phi = dyn_cast<const phi_info *> (access))
phi->print (pp, flags);
else if (auto *set = dyn_cast<const set_info *> (access))
set->print (pp, flags);
else if (auto *clobber = dyn_cast<const clobber_info *> (access))
clobber->print (pp, flags);
else if (auto *use = dyn_cast<const use_info *> (access))
use->print (pp, flags);
else
pp_string (pp, "??? Unknown access");
}
// Print ACCESSES to PP. FLAGS is a bitmask of PP_ACCESS_* flags.
void
rtl_ssa::pp_accesses (pretty_printer *pp, access_array accesses,
unsigned int flags)
{
if (accesses.empty ())
pp_string (pp, "none");
else
{
bool is_first = true;
for (access_info *access : accesses)
{
if (is_first)
is_first = false;
else
pp_newline_and_indent (pp, 0);
pp_access (pp, access, flags);
}
}
}
// Print NODE to PP.
void
rtl_ssa::pp_def_node (pretty_printer *pp, const def_node *node)
{
if (!node)
pp_string (pp, "<null>");
else if (auto *group = dyn_cast<const clobber_group *> (node))
group->print (pp);
else if (auto *set = dyn_cast<const set_node *> (node))
set->print (pp);
else
pp_string (pp, "??? Unknown def node");
}
// Print MUX to PP.
void
rtl_ssa::pp_def_mux (pretty_printer *pp, def_mux mux)
{
if (auto *node = mux.dyn_cast<def_node *> ())
pp_def_node (pp, node);
else
pp_access (pp, mux.as_a<def_info *> ());
}
// Print DL to PP.
void
rtl_ssa::pp_def_lookup (pretty_printer *pp, def_lookup dl)
{
pp_string (pp, "comparison result of ");
pp_decimal_int (pp, dl.comparison);
pp_string (pp, " for ");
pp_newline_and_indent (pp, 0);
pp_def_mux (pp, dl.mux);
}
// Dump RESOURCE to FILE.
void
dump (FILE *file, resource_info resource)
{
dump_using (file, pp_resource, resource);
}
// Dump ACCESS to FILE. FLAGS is a bitmask of PP_ACCESS_* flags.
void
dump (FILE *file, const access_info *access, unsigned int flags)
{
dump_using (file, pp_access, access, flags);
}
// Dump ACCESSES to FILE. FLAGS is a bitmask of PP_ACCESS_* flags.
void
dump (FILE *file, access_array accesses, unsigned int flags)
{
dump_using (file, pp_accesses, accesses, flags);
}
// Print NODE to FILE.
void
dump (FILE *file, const def_node *node)
{
dump_using (file, pp_def_node, node);
}
// Print MUX to FILE.
void
dump (FILE *file, def_mux mux)
{
dump_using (file, pp_def_mux, mux);
}
// Print RESULT to FILE.
void
dump (FILE *file, def_lookup result)
{
dump_using (file, pp_def_lookup, result);
}
// Debug interfaces to the dump routines above.
void debug (const resource_info &x) { dump (stderr, x); }
void debug (const access_info *x) { dump (stderr, x); }
void debug (const access_array &x) { dump (stderr, x); }
void debug (const def_node *x) { dump (stderr, x); }
void debug (const def_mux &x) { dump (stderr, x); }
void debug (const def_lookup &x) { dump (stderr, x); }