gcc/gimple-range.cc

/* Code for GIMPLE range related routines.
   Copyright (C) 2019-2020 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 "insn-codes.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
#include "gimple-iterator.h"
#include "optabs-tree.h"
#include "gimple-fold.h"
#include "tree-cfg.h"
#include "fold-const.h"
#include "tree-cfg.h"
#include "wide-int.h"
#include "fold-const.h"
#include "case-cfn-macros.h"
#include "omp-general.h"
#include "cfgloop.h"
#include "tree-ssa-loop.h"
#include "tree-scalar-evolution.h"
#include "dbgcnt.h"
#include "alloc-pool.h"
#include "vr-values.h"
#include "gimple-range.h"


// Adjust the range for a pointer difference where the operands came
// from a memchr.
//
// This notices the following sequence:
//
//	def = __builtin_memchr (arg, 0, sz)
//	n = def - arg
//
// The range for N can be narrowed to [0, PTRDIFF_MAX - 1].

static void
adjust_pointer_diff_expr (irange &res, const gimple *diff_stmt)
{
  tree op0 = gimple_assign_rhs1 (diff_stmt);
  tree op1 = gimple_assign_rhs2 (diff_stmt);
  tree op0_ptype = TREE_TYPE (TREE_TYPE (op0));
  tree op1_ptype = TREE_TYPE (TREE_TYPE (op1));
  gimple *call;

  if (TREE_CODE (op0) == SSA_NAME
      && TREE_CODE (op1) == SSA_NAME
      && (call = SSA_NAME_DEF_STMT (op0))
      && is_gimple_call (call)
      && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
      && TYPE_MODE (op0_ptype) == TYPE_MODE (char_type_node)
      && TYPE_PRECISION (op0_ptype) == TYPE_PRECISION (char_type_node)
      && TYPE_MODE (op1_ptype) == TYPE_MODE (char_type_node)
      && TYPE_PRECISION (op1_ptype) == TYPE_PRECISION (char_type_node)
      && gimple_call_builtin_p (call, BUILT_IN_MEMCHR)
      && vrp_operand_equal_p (op1, gimple_call_arg (call, 0))
      && integer_zerop (gimple_call_arg (call, 1)))
    {
      tree max = vrp_val_max (ptrdiff_type_node);
      wide_int wmax = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
      tree expr_type = gimple_expr_type (diff_stmt);
      tree range_min = build_zero_cst (expr_type);
      tree range_max = wide_int_to_tree (expr_type, wmax - 1);
      int_range<1> r (range_min, range_max);
      res.intersect (r);
    }
}

// This function looks for situations when walking the use/def chains
// may provide additonal contextual range information not exposed on
// this statement.  Like knowing the IMAGPART return value from a
// builtin function is a boolean result.

// We should rework how we're called, as we have an op_unknown entry
// for IMAGPART_EXPR and POINTER_DIFF_EXPR in range-ops just so this
// function gets called.

static void
gimple_range_adjustment (irange &res, const gimple *stmt)
{
  switch (gimple_expr_code (stmt))
    {
    case POINTER_DIFF_EXPR:
      adjust_pointer_diff_expr (res, stmt);
      return;

    case IMAGPART_EXPR:
      {
	tree name = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
	if (TREE_CODE (name) == SSA_NAME)
	  {
	    gimple *def_stmt = SSA_NAME_DEF_STMT (name);
	    if (def_stmt && is_gimple_call (def_stmt)
		&& gimple_call_internal_p (def_stmt))
	      {
		switch (gimple_call_internal_fn (def_stmt))
		  {
		  case IFN_ADD_OVERFLOW:
		  case IFN_SUB_OVERFLOW:
		  case IFN_MUL_OVERFLOW:
		  case IFN_ATOMIC_COMPARE_EXCHANGE:
		    {
		      int_range<1> r;
		      r.set_varying (boolean_type_node);
		      tree type = TREE_TYPE (gimple_assign_lhs (stmt));
		      range_cast (r, type);
		      res.intersect (r);
		    }
		  default:
		    break;
		  }
	      }
	  }
	break;
      }

    default:
      break;
    }
}

// ------------------------------------------------------------------------

// This function will calculate the "constant" range on edge E from
// switch SW returning it in R, and return the switch statement
// itself.  This is currently not very efficent as the way we
// represent switches in GIMPLE does not map well to this calculation.

static gimple *
calc_range_for_switch_on_edge (irange &r, gswitch *sw, edge e)
{
  unsigned x, lim;
  lim = gimple_switch_num_labels (sw);
  tree type = TREE_TYPE (gimple_switch_index (sw));

  // ADA and FORTRAN currently have cases where the index is 64 bits
  // and the case arguments are 32 bit, causing a trap when we create
  // a case_range.  Until this is resolved
  // (https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87798) punt on
  // these switches.  Furthermore, cfamily fails during a bootstrap
  // due to a signed index and unsigned cases.  So punting unless
  // types_compatible_p () for now.
  tree case_type = TREE_TYPE (CASE_LOW (gimple_switch_label (sw, 1)));
  if (lim > 1 && !types_compatible_p (type, case_type))
    return NULL;

  edge default_edge = gimple_switch_default_edge (cfun, sw);
  if (e != default_edge)
    {
      r.set_undefined ();
      // Union all the ranges for each switch edge, ignoring the
      // default edge.
      for (x = 1; x < lim; x++)
	{
	  if (gimple_switch_edge (cfun, sw, x) != e)
	    continue;
	  tree low = CASE_LOW (gimple_switch_label (sw, x));
	  tree high = CASE_HIGH (gimple_switch_label (sw, x));
	  if (!high)
	    high = low;
	  int_range<1> case_range (low, high);
	  r.union_ (case_range);
	}
    }
  else
    {
      r.set_varying (type);
      // Loop through all the switches edges, ignoring the default
      // edge, while intersecting the ranges not covered by the case.
      for (x = 1; x < lim; x++)
	{
	  // Some other edge could still point to the default edge
	  // destination.  Ignore it.
	  if (gimple_switch_edge (cfun, sw, x) == default_edge)
	    continue;
	  tree low = CASE_LOW (gimple_switch_label (sw, x));
	  tree high = CASE_HIGH (gimple_switch_label (sw, x));
	  if (!high)
	    high = low;
	  int_range<1> case_range (low, high, VR_ANTI_RANGE);
	  r.intersect (case_range);
	}
    }
  return sw;
}


// If there is a range control statment at the end of block BB, return it.

gimple_stmt_iterator
gsi_outgoing_range_stmt (basic_block bb)
{
  gimple_stmt_iterator gsi = gsi_last_nondebug_bb (bb);
  if (!gsi_end_p (gsi))
    {
      gimple *s = gsi_stmt (gsi);
      if (is_a<gcond *> (s) || is_a<gswitch *> (s))
	return gsi;
    }
  return gsi_none ();
}


// If there is a range control statment at the end of block BB, return it.

gimple *
gimple_outgoing_range_stmt_p (basic_block bb)
{
  // This will return NULL if there is not a branch statement.
  return gsi_stmt (gsi_outgoing_range_stmt (bb));
}


// Calculate the range forced on on edge E by control flow, return it
// in R.  Return the statment which defines the range, otherwise
// return NULL

gimple *
gimple_outgoing_edge_range_p (irange &r, edge e)
{
  // Determine if there is an outgoing edge.
  gimple *s = gimple_outgoing_range_stmt_p (e->src);
  if (!s)
    return NULL;

  if (is_a<gcond *> (s))
    {
      if (e->flags & EDGE_TRUE_VALUE)
	r = int_range<1> (boolean_true_node, boolean_true_node);
      else if (e->flags & EDGE_FALSE_VALUE)
	r = int_range<1> (boolean_false_node, boolean_false_node);
      else
	gcc_unreachable ();
      return s;
    }

  gcc_checking_assert (is_a<gswitch *> (s));
  gswitch *sw = as_a<gswitch *> (s);
  tree type = TREE_TYPE (gimple_switch_index (sw));

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

  return calc_range_for_switch_on_edge (r, sw, e);
}


// Return a range in R for the tree EXPR.  Return true if a range is
// representable.

bool
get_tree_range (irange &r, tree expr)
{
  tree type;
  if (TYPE_P (expr))
    type = expr;
  else
    type = TREE_TYPE (expr);

  // Return false if the type isn't suported.
  if (!irange::supports_type_p (type))
    return false;

  switch (TREE_CODE (expr))
    {
      case INTEGER_CST:
	r.set (expr, expr);
	return true;

      case SSA_NAME:
	r = gimple_range_global (expr);
	return true;

      case ADDR_EXPR:
        {
	  // Handle &var which can show up in phi arguments.
	  bool ov;
	  if (tree_single_nonzero_warnv_p (expr, &ov))
	    {
	      r = range_nonzero (type);
	      return true;
	    }
	  break;
	}

      default:
        break;
    }
  r.set_varying (type);
  return true;
}

// Fold this unary statement using R1 as operand1's range, returning
// the result in RES.  Return false if the operation fails.

bool
gimple_range_fold (irange &res, const gimple *stmt, const irange &r1)
{
  gcc_checking_assert (gimple_range_handler (stmt));

  tree type = gimple_expr_type (stmt);
  // Unary SSA operations require the LHS type as the second range.
  int_range<1> r2 (type);

  return gimple_range_fold (res, stmt, r1, r2);
}


// Fold this binary statement using R1 and R2 as the operands ranges,
// returning the result in RES.  Return false if the operation fails.

bool
gimple_range_fold (irange &res, const gimple *stmt,
		   const irange &r1, const irange &r2)
{
  gcc_checking_assert (gimple_range_handler (stmt));

  gimple_range_handler (stmt)->fold_range (res, gimple_expr_type (stmt),
					   r1, r2);

  // If there are any gimple lookups, do those now.
  gimple_range_adjustment (res, stmt);
  return true;
}

// Return the base of the RHS of an assignment.

tree
gimple_range_base_of_assignment (const gimple *stmt)
{
  gcc_checking_assert (gimple_code (stmt) == GIMPLE_ASSIGN);
  tree op1 = gimple_assign_rhs1 (stmt);
  if (gimple_assign_rhs_code (stmt) == ADDR_EXPR)
    return get_base_address (TREE_OPERAND (op1, 0));
  return op1;
}

// Return the first operand of this statement if it is a valid operand
// supported by ranges, otherwise return NULL_TREE.  Special case is
// &(SSA_NAME expr), return the SSA_NAME instead of the ADDR expr.

tree
gimple_range_operand1 (const gimple *stmt)
{
  gcc_checking_assert (gimple_range_handler (stmt));

  switch (gimple_code (stmt))
    {
      case GIMPLE_COND:
	return gimple_cond_lhs (stmt);
      case GIMPLE_ASSIGN:
	{
	  tree base = gimple_range_base_of_assignment (stmt);
	  if (base && TREE_CODE (base) == MEM_REF)
	    {
	      // If the base address is an SSA_NAME, we return it
	      // here.  This allows processing of the range of that
	      // name, while the rest of the expression is simply
	      // ignored.  The code in range_ops will see the
	      // ADDR_EXPR and do the right thing.
	      tree ssa = TREE_OPERAND (base, 0);
	      if (TREE_CODE (ssa) == SSA_NAME)
		return ssa;
	    }
	  return base;
	}
      default:
	break;
    }
  return NULL;
}


// Return the second operand of statement STMT, otherwise return NULL_TREE.

tree
gimple_range_operand2 (const gimple *stmt)
{
  gcc_checking_assert (gimple_range_handler (stmt));

  switch (gimple_code (stmt))
    {
    case GIMPLE_COND:
      return gimple_cond_rhs (stmt);
    case GIMPLE_ASSIGN:
      if (gimple_num_ops (stmt) >= 3)
	return gimple_assign_rhs2 (stmt);
    default:
      break;
    }
  return NULL_TREE;
}



// Calculate what we can determine of the range of this unary
// statement's operand if the lhs of the expression has the range
// LHS_RANGE.  Return false if nothing can be determined.

bool
gimple_range_calc_op1 (irange &r, const gimple *stmt, const irange &lhs_range)
{
  gcc_checking_assert (gimple_num_ops (stmt) < 3);
  // An empty range is viral, so return an empty range.

  tree type = TREE_TYPE (gimple_range_operand1 (stmt));
  if (lhs_range.undefined_p ())
    {
      r.set_undefined ();
      return true;
    }
  // Unary operations require the type of the first operand in the
  // second range position.
  int_range<1> type_range (type);
  return gimple_range_handler (stmt)->op1_range (r, type, lhs_range,
						 type_range);
}


// Calculate what we can determine of the range of this statement's
// first operand if the lhs of the expression has the range LHS_RANGE
// and the second operand has the range OP2_RANGE.  Return false if
// nothing can be determined.

bool
gimple_range_calc_op1 (irange &r, const gimple *stmt,
		       const irange &lhs_range, const irange &op2_range)
{
  // Unary operation are allowed to pass a range in for second operand
  // as there are often additional restrictions beyond the type which
  // can be imposed.  See operator_cast::op1_range.()
  tree type = TREE_TYPE (gimple_range_operand1 (stmt));
  // An empty range is viral, so return an empty range.
  if (op2_range.undefined_p () || lhs_range.undefined_p ())
    {
      r.set_undefined ();
      return true;
    }
  return gimple_range_handler (stmt)->op1_range (r, type, lhs_range,
						 op2_range);
}


// Calculate what we can determine of the range of this statement's
// second operand if the lhs of the expression has the range LHS_RANGE
// and the first operand has the range OP1_RANGE.  Return false if
// nothing can be determined.

bool
gimple_range_calc_op2 (irange &r, const gimple *stmt,
		       const irange &lhs_range, const irange &op1_range)
{
  tree type = TREE_TYPE (gimple_range_operand2 (stmt));
  // An empty range is viral, so return an empty range.
  if (op1_range.undefined_p () || lhs_range.undefined_p ())
    {
      r.set_undefined ();
      return true;
    }
  return gimple_range_handler (stmt)->op2_range (r, type, lhs_range,
						 op1_range);
}


// 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.  If a range cannot
// be calculated, return false.

bool
gimple_ranger::calc_stmt (irange &r, gimple *s, tree name)
{
  bool res = false;
  // If name is specified, make sure it is a LHS of S.
  gcc_checking_assert (name ? SSA_NAME_DEF_STMT (name) == s : true);

  if (gimple_range_handler (s))
    res = range_of_range_op (r, s);
  else if (is_a<gphi *>(s))
    res = range_of_phi (r, as_a<gphi *> (s));
  else if (is_a<gcall *>(s))
    res = range_of_call (r, as_a<gcall *> (s));
  else if (is_a<gassign *> (s) && gimple_assign_rhs_code (s) == COND_EXPR)
    res = range_of_cond_expr (r, as_a<gassign *> (s));
  else
    {
      // If no name is specified, try the expression kind.
      if (!name)
	{
	  tree t = gimple_expr_type (s);
	  if (!irange::supports_type_p (t))
	    return false;
	  r.set_varying (t);
	  return true;
	}
      // We don't understand the stmt, so return the global range.
      r = gimple_range_global (name);
      return true;
    }
  if (res)
    {
      if (r.undefined_p ())
	return true;
      if (name && TREE_TYPE (name) != r.type ())
	range_cast (r, TREE_TYPE (name));
      return true;
    }
  return false;
}

// Calculate a range for range_op statement S and return it in R.  If any
// If a range cannot be calculated, return false.

bool
gimple_ranger::range_of_range_op (irange &r, gimple *s)
{
  widest_irange range1, range2;
  tree type = gimple_expr_type (s);
  gcc_checking_assert (irange::supports_type_p (type));

  tree op1 = gimple_range_operand1 (s);
  tree op2 = gimple_range_operand2 (s);

  if (range_of_non_trivial_assignment (r, s))
    return true;

  if (range_of_expr (range1, op1, s))
    {
      if (!op2)
	return gimple_range_fold (r, s, range1);

      if (range_of_expr (range2, op2, s))
	return gimple_range_fold (r, s, range1, range2);
    }
  r.set_varying (type);
  return true;
}


// Calculate the range of a non-trivial assignment.  That is, is one
// inolving arithmetic on an SSA name (for example, an ADDR_EXPR).
// Return the range in R.
//
// If a range cannot be calculated, return false.

bool
gimple_ranger::range_of_non_trivial_assignment (irange &r, gimple *stmt)
{
  if (gimple_code (stmt) != GIMPLE_ASSIGN)
    return false;

  tree base = gimple_range_base_of_assignment (stmt);
  if (base && TREE_CODE (base) == MEM_REF
      && TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
    {
      widest_irange range1;
      tree ssa = TREE_OPERAND (base, 0);
      if (range_of_expr (range1, ssa, stmt))
	{
	  tree type = TREE_TYPE (ssa);
	  range_operator *op = range_op_handler (POINTER_PLUS_EXPR, type);
	  int_range<1> offset (TREE_OPERAND (base, 1), TREE_OPERAND (base, 1));
	  op->fold_range (r, type, range1, offset);
	  return true;
	}
    }
  return false;
}


// Calculate a range for phi statement S and return it in R.
// If a range cannot be calculated, return false.

bool
gimple_ranger::range_of_phi (irange &r, gphi *phi)
{
  tree phi_def = gimple_phi_result (phi);
  tree type = TREE_TYPE (phi_def);
  widest_irange phi_range;
  unsigned x;

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

  // And start with an empty range, unioning in each argument's range.
  r.set_undefined ();
  for (x = 0; x < gimple_phi_num_args (phi); x++)
    {
      widest_irange arg_range;
      tree arg = gimple_phi_arg_def (phi, x);
      edge e = gimple_phi_arg_edge (phi, x);

      range_on_edge (arg_range, e, arg);
      r.union_ (arg_range);
      // Once the value reaches varying, stop looking.
      if (r.varying_p ())
	break;
    }

  return true;
}


// Calculate a range for call statement S and return it in R.
// If a range cannot be calculated, return false.

bool
gimple_ranger::range_of_call (irange &r, gcall *call)
{
  tree type = gimple_call_return_type (call);
  tree lhs = gimple_call_lhs (call);
  bool strict_overflow_p;

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

  if (range_of_builtin_call (r, call))
    ;
  else if (gimple_stmt_nonnegative_warnv_p (call, &strict_overflow_p))
    r.set (build_int_cst (type, 0), TYPE_MAX_VALUE (type));
  else if (gimple_call_nonnull_result_p (call)
	   || gimple_call_nonnull_arg (call))
    r = range_nonzero (type);
  else
    r.set_varying (type);

  // If there is a lHS, intersect that with what is known.
  if (lhs)
    {
      value_range def;
      def = gimple_range_global (lhs);
      r.intersect (def);
    }
  return true;
}


void
gimple_ranger::range_of_builtin_ubsan_call (irange &r, gcall *call,
					    tree_code code)
{
  gcc_checking_assert (code == PLUS_EXPR || code == MINUS_EXPR
		       || code == MULT_EXPR);
  tree type = gimple_call_return_type (call);
  range_operator *op = range_op_handler (code, type);
  gcc_checking_assert (op);
  widest_irange ir0, ir1;
  tree arg0 = gimple_call_arg (call, 0);
  tree arg1 = gimple_call_arg (call, 1);
  gcc_assert (range_of_expr (ir0, arg0, call));
  gcc_assert (range_of_expr (ir1, arg1, call));

  bool saved_flag_wrapv = flag_wrapv;
  /* Pretend the arithmetics is wrapping.  If there is
     any overflow, we'll complain, but will actually do
     wrapping operation.  */
  flag_wrapv = 1;
  op->fold_range (r, type, ir0, ir1);
  flag_wrapv = saved_flag_wrapv;

  /* If for both arguments vrp_valueize returned non-NULL,
     this should have been already folded and if not, it
     wasn't folded because of overflow.  Avoid removing the
     UBSAN_CHECK_* calls in that case.  */
  if (r.singleton_p ())
    r.set_varying (type);
}


bool
gimple_ranger::range_of_builtin_call (irange &r, gcall *call)
{
  combined_fn func = gimple_call_combined_fn (call);
  if (func == CFN_LAST)
    return false;

  tree type = gimple_call_return_type (call);
  tree arg;
  int mini, maxi, zerov, prec;
  scalar_int_mode mode;

  switch (func)
    {
    case CFN_BUILT_IN_CONSTANT_P:
      if (cfun->after_inlining)
	{
	  r.set_zero (type);
	  // r.equiv_clear ();
	  return true;
	}
      arg = gimple_call_arg (call, 0);
      if (range_of_expr (r, arg, call) && r.singleton_p ())
	{
	  r.set (build_one_cst (type), build_one_cst (type));
	  return true;
	}
      break;

    CASE_CFN_FFS:
    CASE_CFN_POPCOUNT:
      // __builtin_ffs* and __builtin_popcount* return [0, prec].
      arg = gimple_call_arg (call, 0);
      prec = TYPE_PRECISION (TREE_TYPE (arg));
      mini = 0;
      maxi = prec;
      gcc_assert (range_of_expr (r, arg, call));
      // If arg is non-zero, then ffs or popcount are non-zero.
      if (!range_includes_zero_p (&r))
	mini = 1;
      // If some high bits are known to be zero, decrease the maximum.
      if (!r.undefined_p ())
	{
	  wide_int max = r.upper_bound ();
	  maxi = wi::floor_log2 (max) + 1;
	}
      r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
      return true;

    CASE_CFN_PARITY:
      r.set (build_zero_cst (type), build_one_cst (type));
      return true;

    CASE_CFN_CLZ:
      // __builtin_c[lt]z* return [0, prec-1], except when the
      // argument is 0, but that is undefined behavior.
      //
      // On many targets where the CLZ RTL or optab value is defined
      // for 0, the value is prec, so include that in the range by
      // default.
      arg = gimple_call_arg (call, 0);
      prec = TYPE_PRECISION (TREE_TYPE (arg));
      mini = 0;
      maxi = prec;
      mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
      if (optab_handler (clz_optab, mode) != CODE_FOR_nothing
	  && CLZ_DEFINED_VALUE_AT_ZERO (mode, zerov)
	  // Only handle the single common value.
	  && zerov != prec)
	// Magic value to give up, unless we can prove arg is non-zero.
	mini = -2;

      gcc_assert (range_of_expr (r, arg, call));
      // From clz of minimum we can compute result maximum.
      if (r.constant_p ())
	{
	  maxi = prec - 1 - wi::floor_log2 (r.lower_bound ());
	  if (maxi != prec)
	    mini = 0;
	}
      else if (!range_includes_zero_p (&r))
	{
	  maxi = prec - 1;
	  mini = 0;
	}
      if (mini == -2)
	break;
      // From clz of maximum we can compute result minimum.
      if (r.constant_p ())
	{
	  mini = prec - 1 - wi::floor_log2 (r.upper_bound ());
	  if (mini == prec)
	    break;
	}
      if (mini == -2)
	break;
      r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
      return true;

    CASE_CFN_CTZ:
      // __builtin_ctz* return [0, prec-1], except for when the
      // argument is 0, but that is undefined behavior.
      //
      // If there is a ctz optab for this mode and
      // CTZ_DEFINED_VALUE_AT_ZERO, include that in the range,
      // otherwise just assume 0 won't be seen.
      arg = gimple_call_arg (call, 0);
      prec = TYPE_PRECISION (TREE_TYPE (arg));
      mini = 0;
      maxi = prec - 1;
      mode = SCALAR_INT_TYPE_MODE (TREE_TYPE (arg));
      if (optab_handler (ctz_optab, mode) != CODE_FOR_nothing
	  && CTZ_DEFINED_VALUE_AT_ZERO (mode, zerov))
	{
	  // Handle only the two common values.
	  if (zerov == -1)
	    mini = -1;
	  else if (zerov == prec)
	    maxi = prec;
	  else
	    // Magic value to give up, unless we can prove arg is non-zero.
	    mini = -2;
	}
      gcc_assert (range_of_expr (r, arg, call));
      if (!r.undefined_p ())
	{
	  if (r.lower_bound () != 0)
	    {
	      mini = 0;
	      maxi = prec - 1;
	    }
	  // If some high bits are known to be zero, we can decrease
	  // the maximum.
	  wide_int max = r.upper_bound ();
	  if (max == 0)
	    break;
	  maxi = wi::floor_log2 (max);
	}
      if (mini == -2)
	break;
      r.set (build_int_cst (type, mini), build_int_cst (type, maxi));
      return true;

    CASE_CFN_CLRSB:
      arg = gimple_call_arg (call, 0);
      prec = TYPE_PRECISION (TREE_TYPE (arg));
      r.set (build_int_cst (type, 0), build_int_cst (type, prec - 1));
      return true;
    case CFN_UBSAN_CHECK_ADD:
      range_of_builtin_ubsan_call (r, call, PLUS_EXPR);
      return true;
    case CFN_UBSAN_CHECK_SUB:
      range_of_builtin_ubsan_call (r, call, MINUS_EXPR);
      return true;
    case CFN_UBSAN_CHECK_MUL:
      range_of_builtin_ubsan_call (r, call, MULT_EXPR);
      return true;

    case CFN_GOACC_DIM_SIZE:
    case CFN_GOACC_DIM_POS:
      // Optimizing these two internal functions helps the loop
      // optimizer eliminate outer comparisons.  Size is [1,N]
      // and pos is [0,N-1].
      {
	bool is_pos = func == CFN_GOACC_DIM_POS;
	int axis = oacc_get_ifn_dim_arg (call);
	int size = oacc_get_fn_dim_size (current_function_decl, axis);
	if (!size)
	  // If it's dynamic, the backend might know a hardware limitation.
	  size = targetm.goacc.dim_limit (axis);

	r.set (build_int_cst (type, is_pos ? 0 : 1),
	       size
	       ? build_int_cst (type, size - is_pos) : vrp_val_max (type));
	return true;
      }

    case CFN_BUILT_IN_STRLEN:
      if (tree lhs = gimple_call_lhs (call))
	if (ptrdiff_type_node
	    && (TYPE_PRECISION (ptrdiff_type_node)
		== TYPE_PRECISION (TREE_TYPE (lhs))))
	  {
	    tree type = TREE_TYPE (lhs);
	    tree max = vrp_val_max (ptrdiff_type_node);
	    wide_int wmax
	      = wi::to_wide (max, TYPE_PRECISION (TREE_TYPE (max)));
	    tree range_min = build_zero_cst (type);
	    // To account for the terminating NULL, the maximum length
	    // is one less than the maximum array size, which in turn
	    // is one less than PTRDIFF_MAX (or SIZE_MAX where it's
	    // smaller than the former type).
	    // FIXME: Use max_object_size() - 1 here.
	    tree range_max = wide_int_to_tree (type, wmax - 2);
	    r.set (range_min, range_max);
	    return true;
	  }
      break;
    default:
      break;
    }
  return false;
}




// Calculate a range for COND_EXPR statement S and return it in R.
// If a range cannot be calculated, return false.

bool
gimple_ranger::range_of_cond_expr  (irange &r, gassign *s)
{
  widest_irange cond_range, range1, range2;
  tree cond = gimple_assign_rhs1 (s);
  tree op1 = gimple_assign_rhs2 (s);
  tree op2 = gimple_assign_rhs3 (s);

  gcc_checking_assert (gimple_assign_rhs_code (s) == COND_EXPR);
  gcc_checking_assert (useless_type_conversion_p  (TREE_TYPE (op1),
						   TREE_TYPE (op2)));
  if (!irange::supports_type_p (TREE_TYPE (op1)))
    return false;

  gcc_assert (range_of_expr (cond_range, cond, s));
  gcc_assert (range_of_expr (range1, op1, s));
  gcc_assert (range_of_expr (range2, op2, s));

  // If the condition is known, choose the appropriate expression.
  if (cond_range.singleton_p ())
    {
      // False, pick second operand
      if (cond_range.zero_p ())
	r = range2;
      else
	r = range1;
    }
  else
    {
      r = range1;
      r.union_ (range2);
    }
  return true;
}



bool
gimple_ranger::range_of_expr (irange &r, tree expr, gimple *stmt)
{
  if (!gimple_range_ssa_p (expr))
    return get_tree_range (r, expr);

  // If there is no statement, just get the global value.
  if (!stmt)
    {
      if (!m_cache.m_globals.get_global_range (r, expr))
        r = gimple_range_global (expr);
      return true;
    }

  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)
    gcc_assert (range_of_stmt (r, def_stmt, expr));
  else
    // Otherwise OP comes from outside this block, use range on entry.
    range_on_entry (r, bb, expr);

  // No range yet, see if there is a dereference in the block.
  // We don't care if it's between the def and a use within a block
  // because the entire block must be executed anyway.
  // FIXME:?? For non-call exceptions we could have a statement throw
  // which causes an early block exit.
  // in which case we may need to walk from S back to the def/top of block
  // to make sure the deref happens between S and there before claiming
  // there is a deref.   Punt for now.
  if (!cfun->can_throw_non_call_exceptions && r.varying_p () &&
      m_cache.m_non_null.non_null_deref_p (expr, bb))
    r = range_nonzero (TREE_TYPE (expr));

  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)
{
  widest_irange entry_range;
  gcc_checking_assert (gimple_range_ssa_p (name));

  // Start with any known range
  gcc_assert (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);
}


// 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));

  gimple *s = last_stmt (bb);
  // If there is no statement in the block and this isn't the entry
  // block, go get the range_on_entry for this block.  For the entry
  // block, a NULL stmt will return the global value for NAME.
  if (!s && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
    range_on_entry (r, bb, name);
  else
    gcc_assert (range_of_expr (r, name, s));
  gcc_checking_assert (r.undefined_p ()
		       || types_compatible_p (r.type(), TREE_TYPE (name)));
}

// Calculate a range for NAME on edge E and return it in R.

void
gimple_ranger::range_on_edge (irange &r, edge e, tree name)
{
  widest_irange edge_range;
  gcc_checking_assert (irange::supports_type_p (TREE_TYPE (name)));

  // PHI arguments can be constants, catch these here.
  if (!gimple_range_ssa_p (name))
    {
      gcc_assert (range_of_expr (r, name));
      return;
    }

  range_on_exit (r, e->src, name);
  gcc_checking_assert  (r.undefined_p ()
			|| types_compatible_p (r.type(), TREE_TYPE (name)));

  // Check to see if NAME is defined on edge e.
  if (m_cache.outgoing_edge_range_p (edge_range, e, name))
    r.intersect (edge_range);
}

// 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.

bool
gimple_ranger::range_of_stmt (irange &r, gimple *s, tree name)
{
  // If no name, simply call the base routine.
  if (!name)
    name = gimple_get_lhs (s);

  if (!name)
    return calc_stmt (r, s, NULL_TREE);

  gcc_checking_assert (TREE_CODE (name) == SSA_NAME &&
		       irange::supports_type_p (TREE_TYPE (name)));

  // If this STMT has already been processed, return that value.
  if (m_cache.m_globals.get_global_range (r, name))
    return true;
 
  // Avoid infinite recursion by initializing global cache
  widest_irange tmp = gimple_range_global (name);
  m_cache.m_globals.set_global_range (name, tmp);

  gcc_assert (calc_stmt (r, s, name));

  if (is_a<gphi *> (s))
    r.intersect (tmp);
  m_cache.m_globals.set_global_range (name, r);
  return true;
}


// This routine will export whatever global ranges are known to GCC
// SSA_RANGE_NAME_INFO fields.

void
gimple_ranger::export_global_ranges ()
{
  unsigned x;
  widest_irange r;
  if (dump_file)
    {
      fprintf (dump_file, "Exported global range table\n");
      fprintf (dump_file, "===========================\n");
    }

  for ( x = 1; x < num_ssa_names; x++)
    {
      tree name = ssa_name (x);
      if (name && !SSA_NAME_IN_FREE_LIST (name)
	  && gimple_range_ssa_p (name)
	  && m_cache.m_globals.get_global_range (r, name)
	  && !r.varying_p())
	{
	  // Make sure the new range is a subset of the old range.
	  widest_irange old_range;
	  old_range = gimple_range_global (name);
	  old_range.intersect (r);
	  /* Disable this while we fix tree-ssa/pr61743-2.c.  */
	  //gcc_checking_assert (old_range == r);

	  // WTF? Can't write non-null pointer ranges?? stupid set_range_info!
	  if (!POINTER_TYPE_P (TREE_TYPE (name)) && !r.undefined_p ())
	    {
	      value_range vr = r;
	      set_range_info (name, vr);
	      if (dump_file)
		{
		  print_generic_expr (dump_file, name , TDF_SLIM);
		  fprintf (dump_file, " --> ");
		  vr.dump (dump_file);
		  fprintf (dump_file, "\n");
		  fprintf (dump_file, "         irange : ");
		  r.dump (dump_file);
		  fprintf (dump_file, "\n");
		}
	    }
	}
    }
}


// Print the known table values to file F.

void
gimple_ranger::dump (FILE *f)
{
  basic_block bb;

  FOR_EACH_BB_FN (bb, cfun)
    {
      unsigned x;
      edge_iterator ei;
      edge e;
      widest_irange range;
      fprintf (f, "\n=========== BB %d ============\n", bb->index);
      m_cache.m_on_entry.dump (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.m_globals.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 && m_cache.outgoing_edge_range_p (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 (range, bb, name, false) ||
		      m_cache.block_range (range, e->dest, name, false))
		    {
		      range_on_edge (range, e, name);
		      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");
			}
		    }
		}
	    }
	}
    }

  m_cache.m_globals.dump (dump_file);
  fprintf (f, "\n");

  if (dump_flags & TDF_DETAILS)
    {
      fprintf (f, "\nDUMPING GORI MAP\n");
      m_cache.dump (f);
      fprintf (f, "\n");
    }
}


// loop_ranger implementation.

loop_ranger::loop_ranger ()
{
  m_vr_values = new vr_values;
}

loop_ranger::~loop_ranger ()
{
  delete m_vr_values;
}

void
loop_ranger::range_of_ssa_name_with_loop_info (irange &r, tree name,
					       class loop *l, gphi *phi)
{
  gcc_checking_assert (TREE_CODE (name) == SSA_NAME);
  value_range_equiv vr;
  vr.set_varying (TREE_TYPE (name));
  m_vr_values->adjust_range_with_scev (&vr, l, phi, name);
  vr.normalize_symbolics ();
  r = vr;
}

// If NAME is either a PHI result or a PHI argument, see if we can
// determine range information by querying loop info.  If so, return
// TRUE and set the range in R.

bool
loop_ranger::range_with_loop_info (irange &r, tree name)
{
  if (!scev_initialized_p ())
    return false;

  gimple *def = SSA_NAME_DEF_STMT (name);
  class loop *l = loop_containing_stmt (def);
  if (!l)
    return false;

  basic_block header = l->header;
  for (gphi_iterator iter = gsi_start_phis (header);
       !gsi_end_p (iter); gsi_next (&iter))
    {
      gphi *phi = iter.phi ();
      if (PHI_RESULT (phi) == name)
	{
	  range_of_ssa_name_with_loop_info (r, name, l, phi);
	  return true;
	}
      for (size_t i = 0; i < gimple_phi_num_args (phi); ++i)
	if (PHI_ARG_DEF (phi, i) == name)
	  {
	    range_of_ssa_name_with_loop_info (r, name, l, phi);
	    return true;
	  }
    }
  return false;
}

bool
loop_ranger::range_of_stmt (irange &r, gimple *stmt, tree name)
{
  // If there is no global range for a PHI, start the party with
  // whatever information SCEV may have.
  if (gphi *phi = dyn_cast<gphi *> (stmt))
    {
      tree phi_result = PHI_RESULT (phi);
      if (!POINTER_TYPE_P (TREE_TYPE (phi_result))
	  && !m_cache.m_globals.get_global_range (r, phi_result)
	  && range_with_loop_info (r, phi_result))
	{
	  value_range loop_range;
	  get_range_info (phi_result, loop_range);
	  r.intersect (loop_range);
	  if (!r.varying_p ())
	    set_range_info (phi_result, r);
	}
    }
  return super::range_of_stmt (r, stmt, name);
}

void
loop_ranger::range_on_edge (irange &r, edge e, tree name)
{
  super::range_on_edge (r, e, name);

  if (TREE_CODE (name) == SSA_NAME)
    {
      value_range loop_range;
      if (range_with_loop_info (loop_range, name))
	r.intersect (loop_range);
    }
}