/* Support routines for Value Range Propagation (VRP).
   Copyright (C) 2005-2018 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/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
#include "cfganal.h"
#include "gimple-fold.h"
#include "tree-eh.h"
#include "gimple-iterator.h"
#include "tree-cfg.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
#include "tree-ssa-propagate.h"
#include "alloc-pool.h"
#include "domwalk.h"
#include "tree-cfgcleanup.h"
#include "vr-values.h"
#include "gimple-ssa-evrp-analyze.h"

evrp_range_analyzer::evrp_range_analyzer () : stack (10)
{
  edge e;
  edge_iterator ei;
  basic_block bb;
  FOR_EACH_BB_FN (bb, cfun)
    {
      bb->flags &= ~BB_VISITED;
      FOR_EACH_EDGE (e, ei, bb->preds)
        e->flags |= EDGE_EXECUTABLE;
    }
  vr_values = new class vr_values;
}

/* Push an unwinding marker onto the unwinding stack.  */

void
evrp_range_analyzer::push_marker ()
{
  stack.safe_push (std::make_pair (NULL_TREE, (value_range *)NULL));
}

/* Analyze ranges as we enter basic block BB.  */

void
evrp_range_analyzer::enter (basic_block bb)
{
  if (!optimize)
    return;
  push_marker ();
  record_ranges_from_incoming_edge (bb);
  record_ranges_from_phis (bb);
  bb->flags |= BB_VISITED;
}

/* Find new range for NAME such that (OP CODE LIMIT) is true.  */
value_range *
evrp_range_analyzer::try_find_new_range (tree name,
				    tree op, tree_code code, tree limit)
{
  value_range vr = VR_INITIALIZER;
  value_range *old_vr = get_value_range (name);

  /* Discover VR when condition is true.  */
  vr_values->extract_range_for_var_from_comparison_expr (name, code, op,
							 limit, &vr);
  /* If we found any usable VR, set the VR to ssa_name and create a
     PUSH old value in the stack with the old VR.  */
  if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
    {
      if (old_vr->type == vr.type
	  && vrp_operand_equal_p (old_vr->min, vr.min)
	  && vrp_operand_equal_p (old_vr->max, vr.max))
	return NULL;
      value_range *new_vr = vr_values->allocate_value_range ();
      *new_vr = vr;
      return new_vr;
    }
  return NULL;
}

/* For LHS record VR in the SSA info.  */
void
evrp_range_analyzer::set_ssa_range_info (tree lhs, value_range *vr)
{
  /* Set the SSA with the value range.  */
  if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
    {
      if ((vr->type == VR_RANGE
	   || vr->type == VR_ANTI_RANGE)
	  && (TREE_CODE (vr->min) == INTEGER_CST)
	  && (TREE_CODE (vr->max) == INTEGER_CST))
	set_range_info (lhs, vr->type,
			wi::to_wide (vr->min),
			wi::to_wide (vr->max));
    }
  else if (POINTER_TYPE_P (TREE_TYPE (lhs))
	   && ((vr->type == VR_RANGE
		&& range_includes_zero_p (vr->min,
					  vr->max) == 0)
	       || (vr->type == VR_ANTI_RANGE
		   && range_includes_zero_p (vr->min,
					     vr->max) == 1)))
    set_ptr_nonnull (lhs);
}

/* Return true if all uses of NAME are dominated by STMT or feed STMT
   via a chain of single immediate uses.  */

static bool
all_uses_feed_or_dominated_by_stmt (tree name, gimple *stmt)
{
  use_operand_p use_p, use2_p;
  imm_use_iterator iter;
  basic_block stmt_bb = gimple_bb (stmt);

  FOR_EACH_IMM_USE_FAST (use_p, iter, name)
    {
      gimple *use_stmt = USE_STMT (use_p), *use_stmt2;
      if (use_stmt == stmt
	  || is_gimple_debug (use_stmt)
	  || (gimple_bb (use_stmt) != stmt_bb
	      && dominated_by_p (CDI_DOMINATORS,
				 gimple_bb (use_stmt), stmt_bb)))
	continue;
      while (use_stmt != stmt
	     && is_gimple_assign (use_stmt)
	     && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
	     && single_imm_use (gimple_assign_lhs (use_stmt),
				&use2_p, &use_stmt2))
	use_stmt = use_stmt2;
      if (use_stmt != stmt)
	return false;
    }
  return true;
}

void
evrp_range_analyzer::record_ranges_from_incoming_edge (basic_block bb)
{
  edge pred_e = single_pred_edge_ignoring_loop_edges (bb, false);
  if (pred_e)
    {
      gimple *stmt = last_stmt (pred_e->src);
      tree op0 = NULL_TREE;

      if (stmt
	  && gimple_code (stmt) == GIMPLE_COND
	  && (op0 = gimple_cond_lhs (stmt))
	  && TREE_CODE (op0) == SSA_NAME
	  && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))
	      || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))))
	{
	  if (dump_file && (dump_flags & TDF_DETAILS))
	    {
	      fprintf (dump_file, "Visiting controlling predicate ");
	      print_gimple_stmt (dump_file, stmt, 0);
	    }
	  /* Entering a new scope.  Try to see if we can find a VR
	     here.  */
	  tree op1 = gimple_cond_rhs (stmt);
	  if (TREE_OVERFLOW_P (op1))
	    op1 = drop_tree_overflow (op1);
	  tree_code code = gimple_cond_code (stmt);

	  auto_vec<assert_info, 8> asserts;
	  register_edge_assert_for (op0, pred_e, code, op0, op1, asserts);
	  if (TREE_CODE (op1) == SSA_NAME)
	    register_edge_assert_for (op1, pred_e, code, op0, op1, asserts);

	  auto_vec<std::pair<tree, value_range *>, 8> vrs;
	  for (unsigned i = 0; i < asserts.length (); ++i)
	    {
	      value_range *vr = try_find_new_range (asserts[i].name,
						    asserts[i].expr,
						    asserts[i].comp_code,
						    asserts[i].val);
	      if (vr)
		vrs.safe_push (std::make_pair (asserts[i].name, vr));
	    }

	  /* If pred_e is really a fallthru we can record value ranges
	     in SSA names as well.  */
	  bool is_fallthru = assert_unreachable_fallthru_edge_p (pred_e);

	  /* Push updated ranges only after finding all of them to avoid
	     ordering issues that can lead to worse ranges.  */
	  for (unsigned i = 0; i < vrs.length (); ++i)
	    {
	      push_value_range (vrs[i].first, vrs[i].second);
	      if (is_fallthru
		  && all_uses_feed_or_dominated_by_stmt (vrs[i].first, stmt))
		{
		  set_ssa_range_info (vrs[i].first, vrs[i].second);
		  maybe_set_nonzero_bits (pred_e, vrs[i].first);
		}
	    }
	}
    }
}

void
evrp_range_analyzer::record_ranges_from_phis (basic_block bb)
{
  /* Visit PHI stmts and discover any new VRs possible.  */
  bool has_unvisited_preds = false;
  edge_iterator ei;
  edge e;
  FOR_EACH_EDGE (e, ei, bb->preds)
    if (e->flags & EDGE_EXECUTABLE
	&& !(e->src->flags & BB_VISITED))
      {
	has_unvisited_preds = true;
	break;
      }

  for (gphi_iterator gpi = gsi_start_phis (bb);
       !gsi_end_p (gpi); gsi_next (&gpi))
    {
      gphi *phi = gpi.phi ();
      tree lhs = PHI_RESULT (phi);
      if (virtual_operand_p (lhs))
	continue;

      value_range vr_result = VR_INITIALIZER;
      bool interesting = stmt_interesting_for_vrp (phi);
      if (!has_unvisited_preds && interesting)
	vr_values->extract_range_from_phi_node (phi, &vr_result);
      else
	{
	  set_value_range_to_varying (&vr_result);
	  /* When we have an unvisited executable predecessor we can't
	     use PHI arg ranges which may be still UNDEFINED but have
	     to use VARYING for them.  But we can still resort to
	     SCEV for loop header PHIs.  */
	  struct loop *l;
	  if (scev_initialized_p ()
	      && interesting
	      && (l = loop_containing_stmt (phi))
	      && l->header == gimple_bb (phi))
	  vr_values->adjust_range_with_scev (&vr_result, l, phi, lhs);
	}
      vr_values->update_value_range (lhs, &vr_result);

      /* Set the SSA with the value range.  */
      set_ssa_range_info (lhs, &vr_result);
    }
}

/* Record ranges from STMT into our VR_VALUES class.  If TEMPORARY is
   true, then this is a temporary equivalence and should be recorded
   into the unwind table.  Othewise record the equivalence into the
   global table.  */

void
evrp_range_analyzer::record_ranges_from_stmt (gimple *stmt, bool temporary)
{
  tree output = NULL_TREE;

  if (!optimize)
    return;

  if (dyn_cast <gcond *> (stmt))
    ;
  else if (stmt_interesting_for_vrp (stmt))
    {
      edge taken_edge;
      value_range vr = VR_INITIALIZER;
      vr_values->extract_range_from_stmt (stmt, &taken_edge, &output, &vr);
      if (output)
	{
	  /* Set the SSA with the value range.  There are two cases to
	     consider.  First (the the most common) is we are processing
	     STMT in a context where its resulting range globally holds
	     and thus it can be reflected into the global ranges and need
	     not be unwound as we leave scope.

	     The second case occurs if we are processing a statement in
	     a context where the resulting range must not be reflected
	     into the global tables and must be unwound as we leave
	     the current context.  This happens in jump threading for
	     example.  */
	  if (!temporary)
	    {
	      /* Case one.  We can just update the underlying range
		 information as well as the global information.  */
	      vr_values->update_value_range (output, &vr);
	      set_ssa_range_info (output, &vr);
	    }
	  else
	    {
	      /* We're going to need to unwind this range.  We can
		 not use VR as that's a stack object.  We have to allocate
		 a new range and push the old range onto the stack.  We
		 also have to be very careful about sharing the underlying
		 bitmaps.  Ugh.  */
	      value_range *new_vr = vr_values->allocate_value_range ();
	      *new_vr = vr;
	      new_vr->equiv = NULL;
	      push_value_range (output, new_vr);
	    }
	}
      else
	vr_values->set_defs_to_varying (stmt);
    }
  else
    vr_values->set_defs_to_varying (stmt);

  /* See if we can derive a range for any of STMT's operands.  */
  tree op;
  ssa_op_iter i;
  FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
    {
      tree value;
      enum tree_code comp_code;

      /* If OP is used in such a way that we can infer a value
         range for it, and we don't find a previous assertion for
         it, create a new assertion location node for OP.  */
      if (infer_value_range (stmt, op, &comp_code, &value))
	{
	  /* If we are able to infer a nonzero value range for OP,
	     then walk backwards through the use-def chain to see if OP
	     was set via a typecast.
	     If so, then we can also infer a nonzero value range
	     for the operand of the NOP_EXPR.  */
	  if (comp_code == NE_EXPR && integer_zerop (value))
	    {
	      tree t = op;
	      gimple *def_stmt = SSA_NAME_DEF_STMT (t);
	      while (is_gimple_assign (def_stmt)
		     && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
		     && TREE_CODE
			  (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
		     && POINTER_TYPE_P
			  (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
		{
		  t = gimple_assign_rhs1 (def_stmt);
		  def_stmt = SSA_NAME_DEF_STMT (t);

		  /* Add VR when (T COMP_CODE value) condition is
		     true.  */
		  value_range *op_range
		    = try_find_new_range (t, t, comp_code, value);
		  if (op_range)
		    push_value_range (t, op_range);
		}
	    }
	  /* Add VR when (OP COMP_CODE value) condition is true.  */
	  value_range *op_range = try_find_new_range (op, op,
						      comp_code, value);
	  if (op_range)
	    push_value_range (op, op_range);
	}
    }
}

/* Unwind recorded ranges to their most recent state.  */

void
evrp_range_analyzer::pop_to_marker (void)
{
  gcc_checking_assert (!stack.is_empty ());
  while (stack.last ().first != NULL_TREE)
    pop_value_range (stack.last ().first);
  stack.pop ();
}

/* Restore/pop VRs valid only for BB when we leave BB.  */

void
evrp_range_analyzer::leave (basic_block bb ATTRIBUTE_UNUSED)
{
  if (!optimize)
    return;
  pop_to_marker ();
}


/* Push the Value Range of VAR to the stack and update it with new VR.  */

void
evrp_range_analyzer::push_value_range (tree var, value_range *vr)
{
  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "pushing new range for ");
      print_generic_expr (dump_file, var);
      fprintf (dump_file, ": ");
      dump_value_range (dump_file, vr);
      fprintf (dump_file, "\n");
    }
  stack.safe_push (std::make_pair (var, get_value_range (var)));
  vr_values->set_vr_value (var, vr);
}

/* Pop the Value Range from the vrp_stack and update VAR with it.  */

value_range *
evrp_range_analyzer::pop_value_range (tree var)
{
  value_range *vr = stack.last ().second;
  gcc_checking_assert (var == stack.last ().first);
  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "popping range for ");
      print_generic_expr (dump_file, var);
      fprintf (dump_file, ", restoring ");
      dump_value_range (dump_file, vr);
      fprintf (dump_file, "\n");
    }
  vr_values->set_vr_value (var, vr);
  stack.pop ();
  return vr;
}