blob: 6eb3f71bbd37ac645494bb17b26e4387c1ace204 [file] [log] [blame]
/* Code for GIMPLE range related routines.
Copyright (C) 2019-2021 Free Software Foundation, Inc.
Contributed by Andrew MacLeod <amacleod@redhat.com>
and Aldy Hernandez <aldyh@redhat.com>.
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/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "fold-const.h"
#include "tree-cfg.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
#include "gimple-range.h"
gimple_ranger::gimple_ranger () :
non_executable_edge_flag (cfun),
m_cache (non_executable_edge_flag),
tracer ("")
{
// If the cache has a relation oracle, use it.
m_oracle = m_cache.oracle ();
if (dump_file && (param_evrp_mode & EVRP_MODE_TRACE))
tracer.enable_trace ();
// Ensure the not_executable flag is clear everywhere.
if (flag_checking)
{
basic_block bb;
FOR_ALL_BB_FN (bb, cfun)
{
edge_iterator ei;
edge e;
FOR_EACH_EDGE (e, ei, bb->succs)
gcc_checking_assert ((e->flags & non_executable_edge_flag) == 0);
}
}
}
bool
gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
{
unsigned idx;
if (!gimple_range_ssa_p (expr))
return get_tree_range (r, expr, stmt);
if ((idx = tracer.header ("range_of_expr(")))
{
print_generic_expr (dump_file, expr, TDF_SLIM);
fputs (")", dump_file);
if (stmt)
{
fputs (" at stmt ", dump_file);
print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
}
else
fputs ("\n", dump_file);
}
// If there is no statement, just get the global value.
if (!stmt)
{
if (!m_cache.get_global_range (r, expr))
r = gimple_range_global (expr);
}
// For a debug stmt, pick the best value currently available, do not
// trigger new value calculations. PR 100781.
else if (is_gimple_debug (stmt))
m_cache.range_of_expr (r, expr, stmt);
else
{
basic_block bb = gimple_bb (stmt);
gimple *def_stmt = SSA_NAME_DEF_STMT (expr);
// If name is defined in this block, try to get an range from S.
if (def_stmt && gimple_bb (def_stmt) == bb)
{
range_of_stmt (r, def_stmt, expr);
m_cache.m_non_null.adjust_range (r, expr, bb, true);
}
// Otherwise OP comes from outside this block, use range on entry.
else
range_on_entry (r, bb, expr);
}
if (idx)
tracer.trailer (idx, "range_of_expr", true, expr, r);
return true;
}
// Return the range of NAME on entry to block BB in R.
void
gimple_ranger::range_on_entry (irange &r, basic_block bb, tree name)
{
int_range_max entry_range;
gcc_checking_assert (gimple_range_ssa_p (name));
unsigned idx;
if ((idx = tracer.header ("range_on_entry (")))
{
print_generic_expr (dump_file, name, TDF_SLIM);
fprintf (dump_file, ") to BB %d\n", bb->index);
}
// Start with any known range
range_of_stmt (r, SSA_NAME_DEF_STMT (name), name);
// Now see if there is any on_entry value which may refine it.
if (m_cache.block_range (entry_range, bb, name))
r.intersect (entry_range);
m_cache.m_non_null.adjust_range (r, name, bb, true);
if (idx)
tracer.trailer (idx, "range_on_entry", true, name, r);
}
// Calculate the range for NAME at the end of block BB and return it in R.
// Return false if no range can be calculated.
void
gimple_ranger::range_on_exit (irange &r, basic_block bb, tree name)
{
// on-exit from the exit block?
gcc_checking_assert (bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
gcc_checking_assert (gimple_range_ssa_p (name));
unsigned idx;
if ((idx = tracer.header ("range_on_exit (")))
{
print_generic_expr (dump_file, name, TDF_SLIM);
fprintf (dump_file, ") from BB %d\n", bb->index);
}
gimple *s = SSA_NAME_DEF_STMT (name);
basic_block def_bb = gimple_bb (s);
// If this is not the definition block, get the range on the last stmt in
// the block... if there is one.
if (def_bb != bb)
s = last_stmt (bb);
// If there is no statement provided, get the range_on_entry for this block.
if (s)
range_of_expr (r, name, s);
else
range_on_entry (r, bb, name);
gcc_checking_assert (r.undefined_p ()
|| range_compatible_p (r.type (), TREE_TYPE (name)));
if (idx)
tracer.trailer (idx, "range_on_exit", true, name, r);
}
// Calculate a range for NAME on edge E and return it in R.
bool
gimple_ranger::range_on_edge (irange &r, edge e, tree name)
{
int_range_max edge_range;
gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name)));
unsigned idx;
if ((idx = tracer.header ("range_on_edge (")))
{
print_generic_expr (dump_file, name, TDF_SLIM);
fprintf (dump_file, ") on edge %d->%d\n", e->src->index, e->dest->index);
}
// Check to see if the edge is executable.
if ((e->flags & non_executable_edge_flag))
{
r.set_undefined ();
if (idx)
tracer.trailer (idx, "range_on_edge [Unexecutable] ", true,
name, r);
return true;
}
bool res = true;
if (!gimple_range_ssa_p (name))
res = range_of_expr (r, name);
else
{
range_on_exit (r, e->src, name);
gcc_checking_assert (r.undefined_p ()
|| range_compatible_p (r.type(), TREE_TYPE (name)));
// Check to see if NAME is defined on edge e.
if (m_cache.range_on_edge (edge_range, e, name))
r.intersect (edge_range);
}
if (idx)
tracer.trailer (idx, "range_on_edge", res, name, r);
return true;
}
// fold_range wrapper for range_of_stmt to use as an internal client.
bool
gimple_ranger::fold_range_internal (irange &r, gimple *s, tree name)
{
fold_using_range f;
fur_depend src (s, &(gori ()), this);
return f.fold_stmt (r, s, src, name);
}
// Calculate a range for statement S and return it in R. If NAME is
// provided it represents the SSA_NAME on the LHS of the statement.
// It is only required if there is more than one lhs/output. Check
// the global cache for NAME first to see if the evaluation can be
// avoided. If a range cannot be calculated, return false and UNDEFINED.
bool
gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
{
bool res;
r.set_undefined ();
unsigned idx;
if ((idx = tracer.header ("range_of_stmt (")))
{
if (name)
print_generic_expr (dump_file, name, TDF_SLIM);
fputs (") at stmt ", dump_file);
print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
}
if (!name)
name = gimple_get_lhs (s);
// If no name, simply call the base routine.
if (!name)
res = fold_range_internal (r, s, NULL_TREE);
else if (!gimple_range_ssa_p (name))
res = false;
// Check if the stmt has already been processed, and is not stale.
else if (m_cache.get_non_stale_global_range (r, name))
{
if (idx)
tracer.trailer (idx, " cached", true, name, r);
return true;
}
else
{
// Otherwise calculate a new value.
int_range_max tmp;
fold_range_internal (tmp, s, name);
// Combine the new value with the old value. This is required because
// the way value propagation works, when the IL changes on the fly we
// can sometimes get different results. See PR 97741.
r.intersect (tmp);
m_cache.set_global_range (name, r);
res = true;
}
if (idx)
tracer.trailer (idx, "range_of_stmt", res, name, r);
return res;
}
// This routine will export whatever global ranges are known to GCC
// SSA_RANGE_NAME_INFO and SSA_NAME_PTR_INFO fields.
void
gimple_ranger::export_global_ranges ()
{
/* Cleared after the table header has been printed. */
bool print_header = true;
for (unsigned x = 1; x < num_ssa_names; x++)
{
int_range_max r;
tree name = ssa_name (x);
if (name && !SSA_NAME_IN_FREE_LIST (name)
&& gimple_range_ssa_p (name)
&& m_cache.get_global_range (r, name)
&& !r.varying_p())
{
bool updated = update_global_range (r, name);
if (!updated || !dump_file || !(dump_flags & TDF_DETAILS))
continue;
if (print_header)
{
/* Print the header only when there's something else
to print below. */
fprintf (dump_file, "Exported global range table:\n");
fprintf (dump_file, "============================\n");
print_header = false;
}
value_range vr = r;
print_generic_expr (dump_file, name , TDF_SLIM);
fprintf (dump_file, " : ");
vr.dump (dump_file);
fprintf (dump_file, "\n");
int_range_max same = vr;
if (same != r)
{
fprintf (dump_file, " irange : ");
r.dump (dump_file);
fprintf (dump_file, "\n");
}
}
}
}
// Print the known table values to file F.
void
gimple_ranger::dump_bb (FILE *f, basic_block bb)
{
unsigned x;
edge_iterator ei;
edge e;
int_range_max range, tmp_range;
fprintf (f, "\n=========== BB %d ============\n", bb->index);
m_cache.dump_bb (f, bb);
::dump_bb (f, bb, 4, TDF_NONE);
// Now find any globals defined in this block.
for (x = 1; x < num_ssa_names; x++)
{
tree name = ssa_name (x);
if (gimple_range_ssa_p (name) && SSA_NAME_DEF_STMT (name) &&
gimple_bb (SSA_NAME_DEF_STMT (name)) == bb &&
m_cache.get_global_range (range, name))
{
if (!range.varying_p ())
{
print_generic_expr (f, name, TDF_SLIM);
fprintf (f, " : ");
range.dump (f);
fprintf (f, "\n");
}
}
}
// And now outgoing edges, if they define anything.
FOR_EACH_EDGE (e, ei, bb->succs)
{
for (x = 1; x < num_ssa_names; x++)
{
tree name = gimple_range_ssa_p (ssa_name (x));
if (name && gori ().has_edge_range_p (name, e)
&& m_cache.range_on_edge (range, e, name))
{
gimple *s = SSA_NAME_DEF_STMT (name);
// Only print the range if this is the def block, or
// the on entry cache for either end of the edge is
// set.
if ((s && bb == gimple_bb (s)) ||
m_cache.block_range (tmp_range, bb, name, false) ||
m_cache.block_range (tmp_range, e->dest, name, false))
{
if (!range.varying_p ())
{
fprintf (f, "%d->%d ", e->src->index,
e->dest->index);
char c = ' ';
if (e->flags & EDGE_TRUE_VALUE)
fprintf (f, " (T)%c", c);
else if (e->flags & EDGE_FALSE_VALUE)
fprintf (f, " (F)%c", c);
else
fprintf (f, " ");
print_generic_expr (f, name, TDF_SLIM);
fprintf(f, " : \t");
range.dump(f);
fprintf (f, "\n");
}
}
}
}
}
}
// Print the known table values to file F.
void
gimple_ranger::dump (FILE *f)
{
basic_block bb;
FOR_EACH_BB_FN (bb, cfun)
dump_bb (f, bb);
m_cache.dump (f);
}
void
gimple_ranger::debug ()
{
dump (stderr);
}
/* Create a new ranger instance and associate it with function FUN.
Each call must be paired with a call to disable_ranger to release
resources. */
gimple_ranger *
enable_ranger (struct function *fun)
{
gimple_ranger *r;
r = new gimple_ranger;
fun->x_range_query = r;
return r;
}
/* Destroy and release the ranger instance associated with function FUN
and replace it the global ranger. */
void
disable_ranger (struct function *fun)
{
delete fun->x_range_query;
fun->x_range_query = &global_ranges;
}