tree
aff_combination_to_tree (aff_tree *comb)
{
  tree type = comb->type;
  tree expr = NULL_TREE;
  unsigned i;
  double_int off, sgn;
  tree type1 = type;
  if (POINTER_TYPE_P (type))
    type1 = sizetype;

  gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);

  for (i = 0; i < comb->n; i++)
    expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef,
			    comb);

  if (comb->rest)
    expr = add_elt_to_tree (expr, type, comb->rest, double_int_one, comb);

  /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
     unsigned.  */
  if (double_int_negative_p (comb->offset))
    {
      off = double_int_neg (comb->offset);
      sgn = double_int_minus_one;
    }
  else
    {
      off = comb->offset;
      sgn = double_int_one;
    }
  return add_elt_to_tree (expr, type, double_int_to_tree (type1, off), sgn,
			  comb);
}

static tree
adjust_return_value_with_ops (enum tree_code code, const char *label,
			      tree acc, tree op1, gimple_stmt_iterator gsi)
{

  tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
  tree result = make_temp_ssa_name (ret_type, NULL, label);
  gassign *stmt;

  if (POINTER_TYPE_P (ret_type))
    {
      gcc_assert (code == PLUS_EXPR && TREE_TYPE (acc) == sizetype);
      code = POINTER_PLUS_EXPR;
    }
  if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))
      && code != POINTER_PLUS_EXPR)
    stmt = gimple_build_assign (result, code, acc, op1);
  else
    {
      tree tem;
      if (code == POINTER_PLUS_EXPR)
	tem = fold_build2 (code, TREE_TYPE (op1), op1, acc);
      else
	tem = fold_build2 (code, TREE_TYPE (op1),
			   fold_convert (TREE_TYPE (op1), acc), op1);
      tree rhs = fold_convert (ret_type, tem);
      rhs = force_gimple_operand_gsi (&gsi, rhs,
				      false, NULL, true, GSI_SAME_STMT);
      stmt = gimple_build_assign (result, rhs);
    }

  gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
  return result;
}

tree
cp_ubsan_maybe_instrument_downcast (location_t loc, tree type,
				    tree intype, tree op)
{
  if (!POINTER_TYPE_P (type)
      || !POINTER_TYPE_P (intype)
      || !POINTER_TYPE_P (TREE_TYPE (op))
      || !CLASS_TYPE_P (TREE_TYPE (TREE_TYPE (op)))
      || !is_properly_derived_from (TREE_TYPE (type), TREE_TYPE (intype)))
    return NULL_TREE;

  return cp_ubsan_maybe_instrument_vptr (loc, op, TREE_TYPE (type), true,
					 TREE_CODE (type) == POINTER_TYPE
					 ? UBSAN_DOWNCAST_POINTER
					 : UBSAN_DOWNCAST_REFERENCE);
}

tree
chrec_convert_aggressive (tree type, tree chrec)
{
  tree inner_type, left, right, lc, rc, rtype;

  if (automatically_generated_chrec_p (chrec)
      || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
    return NULL_TREE;

  inner_type = TREE_TYPE (chrec);
  if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
    return NULL_TREE;

  /* If we cannot perform arithmetic in TYPE, avoid creating an scev.  */
  if (avoid_arithmetics_in_type_p (type))
    return NULL_TREE;

  rtype = POINTER_TYPE_P (type) ? sizetype : type;

  left = CHREC_LEFT (chrec);
  right = CHREC_RIGHT (chrec);
  lc = chrec_convert_aggressive (type, left);
  if (!lc)
    lc = chrec_convert (type, left, NULL_TREE);
  rc = chrec_convert_aggressive (rtype, right);
  if (!rc)
    rc = chrec_convert (rtype, right, NULL_TREE);
 
  return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
}

tree 
reset_evolution_in_loop (unsigned loop_num,
			 tree chrec, 
			 tree new_evol)
{
  struct loop *loop = get_loop (loop_num);

  if (POINTER_TYPE_P (chrec_type (chrec)))
    gcc_assert (sizetype == chrec_type (new_evol));
  else
    gcc_assert (chrec_type (chrec) == chrec_type (new_evol));

  if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
      && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
    {
      tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
					   new_evol);
      tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
					    new_evol);
      return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
		     build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
		     left, right);
    }

  while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
	 && CHREC_VARIABLE (chrec) == loop_num)
    chrec = CHREC_LEFT (chrec);
  
  return build_polynomial_chrec (loop_num, chrec, new_evol);
}

/* Convert CHREC for the right hand side of a CREC.
   The increment for a pointer type is always sizetype.  */
tree 
chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
{
  if (POINTER_TYPE_P (type))
   type = sizetype;
  return chrec_convert (type, chrec, at_stmt);
}

tree
aff_combination_to_tree (aff_tree *comb)
{
  tree type = comb->type, base = NULL_TREE, expr = NULL_TREE;
  unsigned i;
  poly_widest_int off;
  int sgn;

  gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE);

  i = 0;
  if (POINTER_TYPE_P (type))
    {
      type = sizetype;
      if (comb->n > 0 && comb->elts[0].coef == 1
	  && POINTER_TYPE_P (TREE_TYPE (comb->elts[0].val)))
	{
	  base = comb->elts[0].val;
	  ++i;
	}
    }

  for (; i < comb->n; i++)
    expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef);

  if (comb->rest)
    expr = add_elt_to_tree (expr, type, comb->rest, 1);

  /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is
     unsigned.  */
  if (known_lt (comb->offset, 0))
    {
      off = -comb->offset;
      sgn = -1;
    }
  else
    {
      off = comb->offset;
      sgn = 1;
    }
  expr = add_elt_to_tree (expr, type, wide_int_to_tree (type, off), sgn);

  if (base)
    return fold_build_pointer_plus (base, expr);
  else
    return fold_convert (comb->type, expr);
}

void
aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in)
{
  unsigned i;
  tree type;

  widest_int scale = wide_int_ext_for_comb (scale_in, comb->type);
  if (scale == 0)
    return;

  for (i = 0; i < comb->n; i++)
    if (operand_equal_p (comb->elts[i].val, elt, 0))
      {
	widest_int new_coef
	  = wide_int_ext_for_comb (comb->elts[i].coef + scale, comb->type);
	if (new_coef != 0)
	  {
	    comb->elts[i].coef = new_coef;
	    return;
	  }

	comb->n--;
	comb->elts[i] = comb->elts[comb->n];

	if (comb->rest)
	  {
	    gcc_assert (comb->n == MAX_AFF_ELTS - 1);
	    comb->elts[comb->n].coef = 1;
	    comb->elts[comb->n].val = comb->rest;
	    comb->rest = NULL_TREE;
	    comb->n++;
	  }
	return;
      }
  if (comb->n < MAX_AFF_ELTS)
    {
      comb->elts[comb->n].coef = scale;
      comb->elts[comb->n].val = elt;
      comb->n++;
      return;
    }

  type = comb->type;
  if (POINTER_TYPE_P (type))
    type = sizetype;

  if (scale == 1)
    elt = fold_convert (type, elt);
  else
    elt = fold_build2 (MULT_EXPR, type,
		       fold_convert (type, elt),
		       wide_int_to_tree (type, scale));

  if (comb->rest)
    comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest,
			      elt);
  else
    comb->rest = elt;
}

int
cxx_types_compatible_p (tree x, tree y)
{
  if (same_type_ignoring_top_level_qualifiers_p (x, y))
    return 1;

  /* Once we get to the middle-end, references and pointers are
     interchangeable.  FIXME should we try to replace all references with
     pointers?  */
  if (POINTER_TYPE_P (x) && POINTER_TYPE_P (y)
      && TYPE_MODE (x) == TYPE_MODE (y)
      && TYPE_REF_CAN_ALIAS_ALL (x) == TYPE_REF_CAN_ALIAS_ALL (y)
      && same_type_p (TREE_TYPE (x), TREE_TYPE (y)))
    return 1;

  return 0;
}

static bool
graphite_can_represent_scev (tree scev)
{
  if (chrec_contains_undetermined (scev))
    return false;

  /* We disable the handling of pointer types, because it’s currently not
     supported by Graphite with the ISL AST generator. SSA_NAME nodes are
     the only nodes, which are disabled in case they are pointers to object
     types, but this can be changed.  */

  if (POINTER_TYPE_P (TREE_TYPE (scev)) && TREE_CODE (scev) == SSA_NAME)
    return false;

  switch (TREE_CODE (scev))
    {
    case NEGATE_EXPR:
    case BIT_NOT_EXPR:
    CASE_CONVERT:
    case NON_LVALUE_EXPR:
      return graphite_can_represent_scev (TREE_OPERAND (scev, 0));

    case PLUS_EXPR:
    case POINTER_PLUS_EXPR:
    case MINUS_EXPR:
      return graphite_can_represent_scev (TREE_OPERAND (scev, 0))
	&& graphite_can_represent_scev (TREE_OPERAND (scev, 1));

    case MULT_EXPR:
      return !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 0)))
	&& !CONVERT_EXPR_CODE_P (TREE_CODE (TREE_OPERAND (scev, 1)))
	&& !(chrec_contains_symbols (TREE_OPERAND (scev, 0))
	     && chrec_contains_symbols (TREE_OPERAND (scev, 1)))
	&& graphite_can_represent_init (scev)
	&& graphite_can_represent_scev (TREE_OPERAND (scev, 0))
	&& graphite_can_represent_scev (TREE_OPERAND (scev, 1));

    case POLYNOMIAL_CHREC:
      /* Check for constant strides.  With a non constant stride of
	 'n' we would have a value of 'iv * n'.  Also check that the
	 initial value can represented: for example 'n * m' cannot be
	 represented.  */
      if (!evolution_function_right_is_integer_cst (scev)
	  || !graphite_can_represent_init (scev))
	return false;
      return graphite_can_represent_scev (CHREC_LEFT (scev));

    default:
      break;
    }

  /* Only affine functions can be represented.  */
  if (tree_contains_chrecs (scev, NULL)
      || !scev_is_linear_expression (scev))
    return false;

  return true;
}

static tree
prepare_instrumented_value (gimple_stmt_iterator *gsi, histogram_value value)
{
  tree val = value->hvalue.value;
  if (POINTER_TYPE_P (TREE_TYPE (val)))
    val = fold_convert (sizetype, val);
  return force_gimple_operand_gsi (gsi, fold_convert (gcov_type_node, val),
				   true, NULL_TREE, true, GSI_SAME_STMT);
}

tree
c_finish_omp_atomic (location_t loc, enum tree_code code, tree lhs, tree rhs)
{
  tree x, type, addr;

  if (lhs == error_mark_node || rhs == error_mark_node)
    return error_mark_node;

  /* ??? According to one reading of the OpenMP spec, complex type are
     supported, but there are no atomic stores for any architecture.
     But at least icc 9.0 doesn't support complex types here either.
     And lets not even talk about vector types...  */
  type = TREE_TYPE (lhs);
  if (!INTEGRAL_TYPE_P (type)
      && !POINTER_TYPE_P (type)
      && !SCALAR_FLOAT_TYPE_P (type))
    {
      error_at (loc, "invalid expression type for %<#pragma omp atomic%>");
      return error_mark_node;
    }

  /* ??? Validate that rhs does not overlap lhs.  */

  /* Take and save the address of the lhs.  From then on we'll reference it
     via indirection.  */
  addr = build_unary_op (loc, ADDR_EXPR, lhs, 0);
  if (addr == error_mark_node)
    return error_mark_node;
  addr = save_expr (addr);
  if (TREE_CODE (addr) != SAVE_EXPR
      && (TREE_CODE (addr) != ADDR_EXPR
	  || TREE_CODE (TREE_OPERAND (addr, 0)) != VAR_DECL))
    {
      /* Make sure LHS is simple enough so that goa_lhs_expr_p can recognize
	 it even after unsharing function body.  */
      tree var = create_tmp_var_raw (TREE_TYPE (addr), NULL);
      DECL_CONTEXT (var) = current_function_decl;
      addr = build4 (TARGET_EXPR, TREE_TYPE (addr), var, addr, NULL, NULL);
    }
  lhs = build_indirect_ref (loc, addr, RO_NULL);

  /* There are lots of warnings, errors, and conversions that need to happen
     in the course of interpreting a statement.  Use the normal mechanisms
     to do this, and then take it apart again.  */
  x = build_modify_expr (input_location, lhs, NULL_TREE, code,
      			 input_location, rhs, NULL_TREE);
  if (x == error_mark_node)
    return error_mark_node;
  gcc_assert (TREE_CODE (x) == MODIFY_EXPR);
  rhs = TREE_OPERAND (x, 1);

  /* Punt the actual generation of atomic operations to common code.  */
  x = build2 (OMP_ATOMIC, void_type_node, addr, rhs);
  SET_EXPR_LOCATION (x, loc);
  return x;
}

tree
convert (tree type, tree expr)
{
  tree intype;

  if (type == error_mark_node || expr == error_mark_node)
    return error_mark_node;

  intype = TREE_TYPE (expr);

  if (POINTER_TYPE_P (type) && POINTER_TYPE_P (intype))
    {
      expr = decl_constant_value (expr);
      return fold (build1 (NOP_EXPR, type, expr));
    }

  return ocp_convert (type, expr, CONV_OLD_CONVERT,
		      LOOKUP_NORMAL|LOOKUP_NO_CONVERSION);
}

void
set_nonzero_bits (tree name, const wide_int_ref &mask)
{
  gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
  if (SSA_NAME_RANGE_INFO (name) == NULL)
    set_range_info (name, VR_RANGE,
		    TYPE_MIN_VALUE (TREE_TYPE (name)),
		    TYPE_MAX_VALUE (TREE_TYPE (name)));
  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
  ri->set_nonzero_bits (mask);
}

void
pp_c_space_for_pointer_operator (c_pretty_printer *pp, tree t)
{
  if (POINTER_TYPE_P (t))
    {
      tree pointee = strip_pointer_operator (TREE_TYPE (t));
      if (TREE_CODE (pointee) != ARRAY_TYPE
	  && TREE_CODE (pointee) != FUNCTION_TYPE)
	pp_c_whitespace (pp);
    }
}

static void
initialize_handler_parm (tree decl, tree exp)
{
  tree init;
  tree init_type;

  /* Make sure we mark the catch param as used, otherwise we'll get a
     warning about an unused ((anonymous)).  */
  TREE_USED (decl) = 1;
  DECL_READ_P (decl) = 1;

  /* Figure out the type that the initializer is.  Pointers are returned
     adjusted by value from __cxa_begin_catch.  Others are returned by
     reference.  */
  init_type = TREE_TYPE (decl);
  if (!POINTER_TYPE_P (init_type))
    init_type = build_reference_type (init_type);

  choose_personality_routine (decl_is_java_type (init_type, 0)
			      ? lang_java : lang_cplusplus);

  /* Since pointers are passed by value, initialize a reference to
     pointer catch parm with the address of the temporary.  */
  if (TREE_CODE (init_type) == REFERENCE_TYPE
      && TYPE_PTR_P (TREE_TYPE (init_type)))
    exp = cp_build_addr_expr (exp, tf_warning_or_error);

  exp = ocp_convert (init_type, exp, CONV_IMPLICIT|CONV_FORCE_TEMP, 0,
		     tf_warning_or_error);

  init = convert_from_reference (exp);

  /* If the constructor for the catch parm exits via an exception, we
     must call terminate.  See eh23.C.  */
  if (TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (decl)))
    {
      /* Generate the copy constructor call directly so we can wrap it.
	 See also expand_default_init.  */
      init = ocp_convert (TREE_TYPE (decl), init,
			  CONV_IMPLICIT|CONV_FORCE_TEMP, 0,
			  tf_warning_or_error);
      /* Force cleanups now to avoid nesting problems with the
	 MUST_NOT_THROW_EXPR.  */
      init = fold_build_cleanup_point_expr (TREE_TYPE (init), init);
      init = build_must_not_throw_expr (init, NULL_TREE);
    }

  decl = pushdecl (decl);

  start_decl_1 (decl, true);
  cp_finish_decl (decl, init, /*init_const_expr_p=*/false, NULL_TREE,
		  LOOKUP_ONLYCONVERTING|DIRECT_BIND);
}

void
reset_flow_sensitive_info (tree name)
{
  if (POINTER_TYPE_P (TREE_TYPE (name)))
    {
      /* points-to info is not flow-sensitive.  */
      if (SSA_NAME_PTR_INFO (name))
	mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name));
    }
  else
    SSA_NAME_RANGE_INFO (name) = NULL;
}

void
set_nonzero_bits (tree name, double_int mask)
{
  gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name)));
  if (SSA_NAME_RANGE_INFO (name) == NULL)
    set_range_info (name, VR_RANGE,
		    tree_to_double_int (TYPE_MIN_VALUE (TREE_TYPE (name))),
		    tree_to_double_int (TYPE_MAX_VALUE (TREE_TYPE (name))));
  range_info_def *ri = SSA_NAME_RANGE_INFO (name);
  ri->nonzero_bits
    = mask & double_int::mask (TYPE_PRECISION (TREE_TYPE (name)));
}

static tree
handle_malloc_attribute (tree *node, tree ARG_UNUSED (name),
			 tree ARG_UNUSED (args), int ARG_UNUSED (flags),
			 bool * ARG_UNUSED (no_add_attrs))
{
  if (TREE_CODE (*node) == FUNCTION_DECL
      && POINTER_TYPE_P (TREE_TYPE (TREE_TYPE (*node))))
    DECL_IS_MALLOC (*node) = 1;
  else
    gcc_unreachable ();

  return NULL_TREE;
}

void
aff_combination_scale (aff_tree *comb, double_int scale)
{
  unsigned i, j;

  scale = double_int_ext_for_comb (scale, comb);
  if (double_int_one_p (scale))
    return;

  if (double_int_zero_p (scale))
    {
      aff_combination_zero (comb, comb->type);
      return;
    }

  comb->offset
    = double_int_ext_for_comb (double_int_mul (scale, comb->offset), comb);
  for (i = 0, j = 0; i < comb->n; i++)
    {
      double_int new_coef;

      new_coef
	= double_int_ext_for_comb (double_int_mul (scale, comb->elts[i].coef),
				   comb);
      /* A coefficient may become zero due to overflow.  Remove the zero
	 elements.  */
      if (double_int_zero_p (new_coef))
	continue;
      comb->elts[j].coef = new_coef;
      comb->elts[j].val = comb->elts[i].val;
      j++;
    }
  comb->n = j;

  if (comb->rest)
    {
      tree type = comb->type;
      if (POINTER_TYPE_P (type))
	type = sizetype;
      if (comb->n < MAX_AFF_ELTS)
	{
	  comb->elts[comb->n].coef = scale;
	  comb->elts[comb->n].val = comb->rest;
	  comb->rest = NULL_TREE;
	  comb->n++;
	}
      else
	comb->rest = fold_build2 (MULT_EXPR, type, comb->rest,
				  double_int_to_tree (type, scale));
    }
}