path: root/gcc/gimple-range-path.cc

/* Basic block path solver.
   Copyright (C) 2021 Free Software Foundation, Inc.
   Contributed by 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 "cfganal.h"
#include "value-range.h"
#include "gimple-range.h"
#include "tree-pretty-print.h"
#include "gimple-range-path.h"
#include "ssa.h"

// Internal construct to help facilitate debugging of solver.
#define DEBUG_SOLVER (0 && dump_file)

path_range_query::path_range_query (gimple_ranger &ranger)
  : m_ranger (ranger)
{
  m_cache = new ssa_global_cache;
  m_has_cache_entry = BITMAP_ALLOC (NULL);
  m_path = NULL;
}

path_range_query::~path_range_query ()
{
  BITMAP_FREE (m_has_cache_entry);
  delete m_cache;
}

// Mark cache entry for NAME as unused.

void
path_range_query::clear_cache (tree name)
{
  unsigned v = SSA_NAME_VERSION (name);
  bitmap_clear_bit (m_has_cache_entry, v);
}

// If NAME has a cache entry, return it in R, and return TRUE.

inline bool
path_range_query::get_cache (irange &r, tree name)
{
  if (!gimple_range_ssa_p (name))
    return get_global_range_query ()->range_of_expr (r, name);

  unsigned v = SSA_NAME_VERSION (name);
  if (bitmap_bit_p (m_has_cache_entry, v))
    return m_cache->get_global_range (r, name);

  return false;
}

// Set the cache entry for NAME to R.

void
path_range_query::set_cache (const irange &r, tree name)
{
  unsigned v = SSA_NAME_VERSION (name);
  bitmap_set_bit (m_has_cache_entry, v);
  m_cache->set_global_range (name, r);
}

void
path_range_query::dump (FILE *dump_file)
{
  if (m_path->is_empty ())
    return;

  unsigned i;
  bitmap_iterator bi;
  extern void dump_ranger (FILE *, const vec<basic_block> &);

  fprintf (dump_file, "Path is (length=%d):\n", m_path->length ());
  dump_ranger (dump_file, *m_path);

  fprintf (dump_file, "Imports:\n");
  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
    {
      tree name = ssa_name (i);
      print_generic_expr (dump_file, name, TDF_SLIM);
      fprintf (dump_file, "\n");
    }

  m_cache->dump (dump_file);
}

void
path_range_query::debug ()
{
  dump (stderr);
}

// Return the range of NAME at the end of the path being analyzed.

bool
path_range_query::internal_range_of_expr (irange &r, tree name, gimple *stmt)
{
  if (!irange::supports_type_p (TREE_TYPE (name)))
    return false;

  if (get_cache (r, name))
    return true;


  basic_block bb = stmt ? gimple_bb (stmt) : exit_bb ();
  if (stmt && range_defined_in_block (r, name, bb))
    {
      if (TREE_CODE (name) == SSA_NAME)
	r.intersect (gimple_range_global (name));

      set_cache (r, name);
      return true;
    }

  r.set_varying (TREE_TYPE (name));
  return true;
}

bool
path_range_query::range_of_expr (irange &r, tree name, gimple *stmt)
{
  if (internal_range_of_expr (r, name, stmt))
    {
      if (r.undefined_p ())
	m_undefined_path = true;

      return true;
    }
  return false;
}

bool
path_range_query::unreachable_path_p ()
{
  return m_undefined_path;
}

// Return the range of STMT at the end of the path being analyzed.

bool
path_range_query::range_of_stmt (irange &r, gimple *stmt, tree)
{
  tree type = gimple_range_type (stmt);

  if (!irange::supports_type_p (type))
    return false;

  if (!fold_range (r, stmt, this))
    r.set_varying (type);

  return true;
}

// Initialize the current path to PATH.  The current block is set to
// the entry block to the path.
//
// Note that the blocks are in reverse order, so the exit block is
// path[0].

void
path_range_query::set_path (const vec<basic_block> &path)
{
  gcc_checking_assert (path.length () > 1);
  m_path = &path;
  m_pos = m_path->length () - 1;
  bitmap_clear (m_has_cache_entry);
}

// Return the range of the result of PHI in R.

void
path_range_query::ssa_range_in_phi (irange &r, gphi *phi)
{
  tree name = gimple_phi_result (phi);
  basic_block bb = gimple_bb (phi);

  // We experimented with querying ranger's range_on_entry here, but
  // the performance penalty was too high, for hardly any improvements.
  if (at_entry ())
    {
      // Try fold just in case we can resolve simple things like PHI <5(99), 6(88)>.
      if (!fold_range (r, phi, this))
	r.set_varying (TREE_TYPE (name));

      return;
    }

  basic_block prev = prev_bb ();
  edge e_in = find_edge (prev, bb);
  unsigned nargs = gimple_phi_num_args (phi);

  for (size_t i = 0; i < nargs; ++i)
    if (e_in == gimple_phi_arg_edge (phi, i))
      {
	tree arg = gimple_phi_arg_def (phi, i);

	if (!get_cache (r, arg))
	  r.set_varying (TREE_TYPE (name));

	return;
      }
  gcc_unreachable ();
}

// If NAME is defined in BB, set R to the range of NAME, and return
// TRUE.  Otherwise, return FALSE.

bool
path_range_query::range_defined_in_block (irange &r, tree name, basic_block bb)
{
  gimple *def_stmt = SSA_NAME_DEF_STMT (name);
  basic_block def_bb = gimple_bb (def_stmt);

  if (def_bb != bb)
    return false;

  if (gimple_code (def_stmt) == GIMPLE_PHI)
    ssa_range_in_phi (r, as_a<gphi *> (def_stmt));
  else if (!range_of_stmt (r, def_stmt, name))
    r.set_varying (TREE_TYPE (name));

  if (bb)
    m_non_null.adjust_range (r, name, bb);

  if (DEBUG_SOLVER && (bb || !r.varying_p ()))
    {
      fprintf (dump_file, "range_defined_in_block (BB%d) for ", bb ? bb->index : -1);
      print_generic_expr (dump_file, name, TDF_SLIM);
      fprintf (dump_file, " is ");
      r.dump (dump_file);
      fprintf (dump_file, "\n");
    }

  // We may have an artificial statement not in the IL.
  if (!bb && r.varying_p ())
    return false;

  return true;
}

// Precompute ranges defined in the current block, or ranges
// that are exported on an edge to the next block.

void
path_range_query::precompute_ranges_in_block (basic_block bb)
{
  bitmap_iterator bi;
  int_range_max r, cached_range;
  unsigned i;

  // Force recalculation of any names in the cache that are defined in
  // this block.  This can happen on interdependent SSA/phis in loops.
  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
    {
      tree name = ssa_name (i);
      gimple *def_stmt = SSA_NAME_DEF_STMT (name);
      basic_block def_bb = gimple_bb (def_stmt);

      if (def_bb == bb)
	clear_cache (name);
    }

  // Solve imports defined in this block.
  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
    {
      tree name = ssa_name (i);

      if (range_defined_in_block (r, name, bb))
	set_cache (r, name);
    }

  if (at_exit ())
    return;

  // Solve imports that are exported to the next block.
  edge e = find_edge (bb, next_bb ());
  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
    {
      tree name = ssa_name (i);
      gori_compute &g = m_ranger.gori ();
      bitmap exports = g.exports (bb);

      if (bitmap_bit_p (exports, i))
	{
	  if (g.outgoing_edge_range_p (r, e, name, *this))
	    {
	      if (get_cache (cached_range, name))
		r.intersect (cached_range);

	      set_cache (r, name);
	      if (DEBUG_SOLVER)
		{
		  fprintf (dump_file, "outgoing_edge_range_p for ");
		  print_generic_expr (dump_file, name, TDF_SLIM);
		  fprintf (dump_file, " on edge %d->%d ",
			   e->src->index, e->dest->index);
		  fprintf (dump_file, "is ");
		  r.dump (dump_file);
		  fprintf (dump_file, "\n");
		}
	    }
	}
    }
}

// Adjust all pointer imports in BB with non-null information.

void
path_range_query::adjust_for_non_null_uses (basic_block bb)
{
  int_range_max r;
  bitmap_iterator bi;
  unsigned i;

  EXECUTE_IF_SET_IN_BITMAP (m_imports, 0, i, bi)
    {
      tree name = ssa_name (i);

      if (!POINTER_TYPE_P (TREE_TYPE (name)))
	continue;

      if (get_cache (r, name))
	{
	  if (r.nonzero_p ())
	    continue;
	}
      else
	r.set_varying (TREE_TYPE (name));

      if (m_non_null.adjust_range (r, name, bb))
	set_cache (r, name);
    }
}

// Precompute the ranges for IMPORTS along PATH.
//
// IMPORTS are the set of SSA names, any of which could potentially
// change the value of the final conditional in PATH.

void
path_range_query::precompute_ranges (const vec<basic_block> &path,
				     const bitmap_head *imports)
{
  set_path (path);
  m_imports = imports;
  m_undefined_path = false;

  if (DEBUG_SOLVER)
    {
      fprintf (dump_file, "\npath_range_query: precompute_ranges for path: ");
      for (unsigned i = path.length (); i > 0; --i)
	{
	  basic_block bb = path[i - 1];
	  fprintf (dump_file, "BB %d", bb->index);
	  if (i > 1)
	    fprintf (dump_file, ", ");
	}
      fprintf (dump_file, "\n");
    }

  while (1)
    {
      basic_block bb = curr_bb ();

      precompute_ranges_in_block (bb);
      adjust_for_non_null_uses (bb);

      if (at_exit ())
	break;

      move_next ();
    }

  if (DEBUG_SOLVER)
    dump (dump_file);
}