path: root/gcc/tree-assume.cc

/* Support for C++23 ASSUME keyword functionailty.
   Copyright (C) 2023-2025 Free Software Foundation, Inc.
   Contributed by Andrew MacLeod <amacleod@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 "basic-block.h"
#include "bitmap.h"
#include "options.h"
#include "function.h"
#include "cfg.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-iterator.h"
#include "gimple-range.h"
#include "tree-dfa.h"
#include "tree-cfg.h"
#include "gimple-pretty-print.h"

// An assume query utilizes the current range query to implement the assume
// keyword.
// For any return value of 1 from the function, it attempts to determine
// which paths lead to a 1 value being returned. On those paths, it determines
// the ranges of any ssa_names listed in bitmap P (usually the parm list for
// the function), and combines them all.
// These ranges are then set as the global ranges for those parms in this
// function.
// Other functions which refer to this function in an assume builtin
// will then pick up these ranges for the parameters via the inferred range
// mechanism.
//   See gimple-range-infer.cc::gimple_infer_range::check_assume_func ()
//
// my_func (int x)
// {
//   <...>
//   assume [[(x == 1 || x ==4))]]
//   if (x ==3)
//
// a small temporary assume function consisting of
// assume_f1 (int x) { return x == 1 || x == 4; }
// is constructed by the front end, and optimized, at the very end of
// optimization, instead of generating code, we instead invoke the assume pass
// which uses this query to set the the global value of parm x to [1,1][4,4]
//
// Meanwhile., my_func has been rewritten to be:
//
// my_func (int x_2)
// {
//   <...>
//   assume_builtin_call  assume_f1 (x_2);
//   if (x_2 == 3)
//
// When ranger is processing the assume_builtin_call, it looks up the global
// value of the parameter in assume_f1, which is [1,1][4,4].  It then registers
// and inferred range at this statement setting the value x_2 to [1,1][4,4]
//
// Any uses of x_2 after this statement will now utilize this inferred range.
//
// When VRP processes if (x_2 == 3), it picks up the inferred range, and
// determines that x_2 can never be 3, and will rewrite the branch to
//   if (0 != 0)

class assume_query
{
public:
  assume_query (function *f, bitmap p);
protected:
  inline void process_stmts (gimple *s, vrange &lhs_range)
  {
    fur_depend src (s, get_range_query (m_func));
    calculate_stmt (s, lhs_range, src);
    update_parms (src);
  }
  void update_parms (fur_source &src);
  void calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src);
  void calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src);
  void calculate_phi (gphi *phi, vrange &lhs_range);

  ssa_lazy_cache m_path;   // Values found on path
  ssa_lazy_cache m_parms;  // Cumulative parameter value calculated
  bitmap m_parm_list;	   // Parameter ssa-names list.
  function *m_func;
};

// If function F returns a integral value, and has a single return
// statement, try to calculate the range of each value in P that leads
// to the return statement returning TRUE.

assume_query::assume_query (function *f, bitmap p) : m_parm_list (p),
						     m_func (f)
{
  basic_block exit_bb = EXIT_BLOCK_PTR_FOR_FN (f);
  // If there is more than one predecessor to the exit block, bail.
  if (!single_pred_p (exit_bb))
    return;

  basic_block bb = single_pred (exit_bb);
  gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
  if (gsi_end_p (gsi))
    return;
  gimple *s = gsi_stmt (gsi);
  if (!is_a<greturn *> (s))
    return;

  // Check if the single return value is a symbolic and supported type.
  greturn *gret = as_a<greturn *> (s);
  tree op = gimple_return_retval (gret);
  if (!gimple_range_ssa_p (op))
    return;
  tree lhs_type = TREE_TYPE (op);
  if (!irange::supports_p (lhs_type))
    return;

  // Only values of interest are when the return value is 1.  The definition
  // of the return value must be in the same block, or we have
  // complicated flow control we don't understand, and just return.
  unsigned prec = TYPE_PRECISION (lhs_type);
  int_range<2> lhs_range (lhs_type, wi::one (prec), wi::one (prec));

  gimple *def = SSA_NAME_DEF_STMT (op);
  if (!def || gimple_get_lhs (def) != op || gimple_bb (def) != bb)
    return;

  // Determine if this is a PHI or a linear sequence to deal with.
  if (is_a<gphi *> (def))
    calculate_phi (as_a<gphi *> (def), lhs_range);
  else
    process_stmts (def, lhs_range);

  if (dump_file)
    fprintf (dump_file, "\n\nAssumptions :\n--------------\n");

  // Now export any interesting values that were found.
  bitmap_iterator bi;
  unsigned x;
  EXECUTE_IF_SET_IN_BITMAP (m_parm_list, 0, x, bi)
    {
      tree name = ssa_name (x);
      tree type = TREE_TYPE (name);
      value_range assume_range (type);
      // Set the global range of NAME to anything calculated.
      if (m_parms.get_range (assume_range, name) && !assume_range.varying_p ())
	set_range_info (name, assume_range);
    }

  if (dump_file)
   {
     fputc ('\n', dump_file);
     gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
   }
}

// This function will update all the current values of interesting parameters.
// It tries, in order:
//    a) a range found via path calculations.
//    b) range of the parm at SRC point in the IL. (either edge or stmt)
//    c) VARYING if those options fail.
//  The value is then unioned with any existing value, allowing for the
//  cumulation of all ranges leading to the return that return 1.

void
assume_query::update_parms (fur_source &src)
{
  if (dump_file && (dump_flags & TDF_DETAILS))
    fprintf (dump_file, "\nupdate parameters\n");

  // Merge any parameter values.
  bitmap_iterator bi;
  unsigned x;
  EXECUTE_IF_SET_IN_BITMAP (m_parm_list, 0, x, bi)
    {
      tree name = ssa_name (x);
      tree type = TREE_TYPE (name);

      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "PARAMETER ");
	  print_generic_expr (dump_file, name, TDF_SLIM);
	}
      value_range glob_range (type);
      // Find a value from calculations.
      // There will be a value in m_path if GORI calculated an operand value.
      if (m_path.get_range (glob_range, name))
	{
	  if (dump_file && (dump_flags & TDF_DETAILS))
	    {
	      fprintf (dump_file, "\n  Calculated path range:");
	      glob_range.dump (dump_file);
	    }
	}
      // Otherwise, let ranger determine the range at the SRC location.
      else if (src.get_operand (glob_range, name))
	{
	  if (dump_file && (dump_flags & TDF_DETAILS))
	    {
	      fprintf (dump_file, "\n  Ranger Computes path range:");
	      glob_range.dump (dump_file);
	    }
	}
      else
	glob_range.set_varying (type);

      // Find any current saved value of parm, and combine them.
      value_range parm_range (type);
      if (m_parms.get_range (parm_range, name))
	glob_range.union_ (parm_range);

      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "\n  Combine with previous range:");
	  parm_range.dump (dump_file);
	  fputc ('\n', dump_file);
	  print_generic_expr (dump_file, name, TDF_SLIM);
	  fprintf (dump_file, " = ");
	  glob_range.dump (dump_file);
	  fputc ('\n', dump_file);
	}
      // Set this new value.
      m_parms.set_range (name, glob_range);
    }
  // Now reset the path values for the next path.
  if (dump_file && (dump_flags & TDF_DETAILS))
    fprintf (dump_file, "---------------------\n");
  m_path.clear ();
}


// Evaluate PHI statement, using the provided LHS range.
// Only process edge that are taken and return the LHS of the PHI.

void
assume_query::calculate_phi (gphi *phi, vrange &lhs_range)
{
  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "Processing PHI feeding return value:\n");
      print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
    }
  for (unsigned x= 0; x < gimple_phi_num_args (phi); x++)
    {
      tree arg = gimple_phi_arg_def (phi, x);
      value_range arg_range (TREE_TYPE (arg));
      edge e = gimple_phi_arg_edge (phi, x);
      value_range edge_range (TREE_TYPE (arg));
      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "\nArgument %d (bb%d->bb%d): ", x, e->src->index,
		   e->dest->index);
	  print_generic_expr (dump_file, arg, TDF_SLIM);
	  fputc ('\n', dump_file);
	}
      // If we can't get an edge range, be conservative and assume the
      // edge can be taken.
      if (get_range_query (m_func)->range_on_edge (edge_range, e, arg))
	{
	  if (gimple_range_ssa_p (arg))
	    {
	      arg_range = lhs_range;
	      range_cast (arg_range, TREE_TYPE (arg));

	      // An SSA_NAME arg will start with the LHS value.
	      // Check the range of ARG on the edge leading here.  If that range
	      // cannot be any value from the LHS of the PHI, then this branch
	      // will not be taken to return the LHS value and can be ignored.
	      arg_range.intersect (edge_range);
	      if (arg_range.undefined_p ())
		{
		  if (dump_file && (dump_flags & TDF_DETAILS))
		    {
		      fprintf (dump_file, "  IGNORE edge :  LHS range :");
		      lhs_range.dump (dump_file);
		      fprintf (dump_file, " Edge produces : ");
		      edge_range.dump (dump_file);
		      fputc ('\n', dump_file);
		    }
		  continue;
		}

	      // If the def is in the immediate preceeding block, process it
	      // with GORI to determine what values can produce this
	      // argument value.  Otherwise there is more CFG flow, so query
	      // the edge for parm ranges.  This is conservative.
	      gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
	      if (def_stmt && gimple_get_lhs (def_stmt) == arg
		  && gimple_bb (def_stmt) == e->src)
		{
		  process_stmts (def_stmt, arg_range);
		  continue;
		}
	      // Fall through to process the parameter values on the edge.
	    }
	  else
	    {
	      // If this is a constant value that differs from LHS, this
	      // edge cannot be taken and we can ignore it. Otherwise fall
	      // thorugh and process the parameters on the edge.
	      edge_range.intersect (lhs_range);
	      if (edge_range.undefined_p ())
		{
		  if (dump_file && (dump_flags & TDF_DETAILS))
		    fprintf (dump_file, "  IGNORE : const edge not taken\n");
		  continue;
		}
	      if (dump_file && (dump_flags & TDF_DETAILS))
		fprintf (dump_file,
			 "  Const edge executed, compute incoming ranges.\n");

	    }
	}
      // The parameters on the edge now need calculating.
      fur_edge src (e, get_range_query (m_func));
      update_parms (src);
    }
}

// Evaluate operand OP on statement S, using the provided LHS range.
// If successful, set the range in path table, then visit OP's def stmt
// if it is in the same BB.

void
assume_query::calculate_op (tree op, gimple *s, vrange &lhs, fur_source &src)
{
  basic_block bb = gimple_bb (s);
  value_range op_range (TREE_TYPE (op));
  if (src.gori () &&
      src.gori ()->compute_operand_range (op_range, s, lhs, op, src)
      && !op_range.varying_p ())
    {
      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "  Operand ");
	  print_generic_expr (dump_file, op, TDF_SLIM);
	  fprintf (dump_file, " calculated as ");
	  op_range.dump (dump_file);
	}
      // Set the global range, merging if there is already a range.
      m_path.merge_range (op, op_range);
      m_path.get_range (op_range, op);
      if (dump_file && (dump_flags & TDF_DETAILS))
	{
	  fprintf (dump_file, "  New path range :");
	  op_range.dump (dump_file);
	  fputc ('\n', dump_file);
	}
      gimple *def_stmt = SSA_NAME_DEF_STMT (op);
      // Terminate if the pathway leads to a different block as we
      // are not dealing with flow. Ranger will make those queries.
      if (def_stmt && gimple_get_lhs (def_stmt) == op
	  && gimple_bb (def_stmt) == bb)
	calculate_stmt (def_stmt, op_range, src);
    }
}

// Evaluate statement S which produces range LHS_RANGE.  Use GORI to
// determine what values the operands can have to produce the LHS,
// and set these in the M_PATH table.

void
assume_query::calculate_stmt (gimple *s, vrange &lhs_range, fur_source &src)
{
  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "  Processing stmt with LHS = ");
      lhs_range.dump (dump_file);
      fprintf (dump_file, " : ");
      print_gimple_stmt (dump_file, s, 0, TDF_SLIM);
    }
  gimple_range_op_handler handler (s);
  if (handler)
    {
      tree op = gimple_range_ssa_p (handler.operand1 ());
      if (op)
	calculate_op (op, s, lhs_range, src);
      op = gimple_range_ssa_p (handler.operand2 ());
      if (op)
	calculate_op (op, s, lhs_range, src);
    }
}

namespace {

const pass_data pass_data_assumptions =
{
  GIMPLE_PASS, /* type */
  "assumptions", /* name */
  OPTGROUP_NONE, /* optinfo_flags */
  TV_TREE_ASSUMPTIONS, /* tv_id */
  PROP_ssa, /* properties_required */
  PROP_assumptions_done, /* properties_provided */
  0, /* properties_destroyed */
  0, /* todo_flags_start */
  0, /* todo_flags_end */
};


class pass_assumptions : public gimple_opt_pass
{
public:
  pass_assumptions (gcc::context *ctxt)
    : gimple_opt_pass (pass_data_assumptions, ctxt)
  {}

  /* opt_pass methods: */
  bool gate (function *fun) final override { return fun->assume_function; }
  unsigned int execute (function *fun) final override
    {
      // Create a bitmap of all the parameters in this function.
      // Invoke the assume_query to determine what values these parameters
      // have when the function returns TRUE, and set the global values of
      // those parameters in this function based on that.  This will later be
      // utilized by ranger when processing builtin IFN_ASSUME function calls.
      // See gimple-range-infer.cc::check_assume_func ().
      auto_bitmap decls;
      for (tree arg = DECL_ARGUMENTS (fun->decl); arg; arg = DECL_CHAIN (arg))
	{
	  tree name = ssa_default_def (fun, arg);
	  if (!name || !gimple_range_ssa_p (name))
	    continue;
	  tree type = TREE_TYPE (name);
	  if (!value_range::supports_type_p (type))
	    continue;
	  bitmap_set_bit (decls, SSA_NAME_VERSION (name));
	}
      // If there are no parameters to map, simply return;
      if (bitmap_empty_p (decls))
	return TODO_discard_function;

      enable_ranger (fun);

      // This assume query will set any global values required.
      assume_query query (fun, decls);

      disable_ranger (fun);
      return TODO_discard_function;
    }

}; // class pass_assumptions

} // anon namespace

gimple_opt_pass *
make_pass_assumptions (gcc::context *ctx)
{
  return new pass_assumptions (ctx);
}