gimplify.c

/* Tree lowering pass.  This pass converts the GENERIC functions-as-trees
   tree representation into the GIMPLE form.
   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011,
   2012 Free Software Foundation, Inc.
   Major work done by Sebastian Pop <s.pop@laposte.net>,
   Diego Novillo <dnovillo@redhat.com> and Jason Merrill <jason@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 "tm.h"
#include "tree.h"
#include "gimple.h"
#include "tree-iterator.h"
#include "tree-inline.h"
#include "tree-pretty-print.h"
#include "langhooks.h"
#include "tree-flow.h"
#include "cgraph.h"
#include "timevar.h"
#include "hashtab.h"
#include "flags.h"
#include "function.h"
#include "output.h"
#include "ggc.h"
#include "diagnostic-core.h"
#include "target.h"
#include "pointer-set.h"
#include "splay-tree.h"
#include "vec.h"
#include "gimple.h"
#include "tree-pass.h"

#include "langhooks-def.h"	/* FIXME: for lhd_set_decl_assembler_name.  */
#include "expr.h"		/* FIXME: for can_move_by_pieces
				   and STACK_CHECK_MAX_VAR_SIZE.  */

enum gimplify_omp_var_data
{
  GOVD_SEEN = 1,
  GOVD_EXPLICIT = 2,
  GOVD_SHARED = 4,
  GOVD_PRIVATE = 8,
  GOVD_FIRSTPRIVATE = 16,
  GOVD_LASTPRIVATE = 32,
  GOVD_REDUCTION = 64,
  GOVD_LOCAL = 128,
  GOVD_DEBUG_PRIVATE = 256,
  GOVD_PRIVATE_OUTER_REF = 512,
  GOVD_DATA_SHARE_CLASS = (GOVD_SHARED | GOVD_PRIVATE | GOVD_FIRSTPRIVATE
			   | GOVD_LASTPRIVATE | GOVD_REDUCTION | GOVD_LOCAL)
};


enum omp_region_type
{
  ORT_WORKSHARE = 0,
  ORT_PARALLEL = 2,
  ORT_COMBINED_PARALLEL = 3,
  ORT_TASK = 4,
  ORT_UNTIED_TASK = 5
};

struct gimplify_omp_ctx
{
  struct gimplify_omp_ctx *outer_context;
  splay_tree variables;
  struct pointer_set_t *privatized_types;
  location_t location;
  enum omp_clause_default_kind default_kind;
  enum omp_region_type region_type;
};

static struct gimplify_ctx *gimplify_ctxp;
static struct gimplify_omp_ctx *gimplify_omp_ctxp;


/* Formal (expression) temporary table handling: multiple occurrences of
   the same scalar expression are evaluated into the same temporary.  */

typedef struct gimple_temp_hash_elt
{
  tree val;   /* Key */
  tree temp;  /* Value */
} elt_t;

/* Forward declaration.  */
static enum gimplify_status gimplify_compound_expr (tree *, gimple_seq *, bool);

/* Mark X addressable.  Unlike the langhook we expect X to be in gimple
   form and we don't do any syntax checking.  */

void
mark_addressable (tree x)
{
  while (handled_component_p (x))
    x = TREE_OPERAND (x, 0);
  if (TREE_CODE (x) == MEM_REF
      && TREE_CODE (TREE_OPERAND (x, 0)) == ADDR_EXPR)
    x = TREE_OPERAND (TREE_OPERAND (x, 0), 0);
  if (TREE_CODE (x) != VAR_DECL
      && TREE_CODE (x) != PARM_DECL
      && TREE_CODE (x) != RESULT_DECL)
    return;
  TREE_ADDRESSABLE (x) = 1;
}

/* Return a hash value for a formal temporary table entry.  */

static hashval_t
gimple_tree_hash (const void *p)
{
  tree t = ((const elt_t *) p)->val;
  return iterative_hash_expr (t, 0);
}

/* Compare two formal temporary table entries.  */

static int
gimple_tree_eq (const void *p1, const void *p2)
{
  tree t1 = ((const elt_t *) p1)->val;
  tree t2 = ((const elt_t *) p2)->val;
  enum tree_code code = TREE_CODE (t1);

  if (TREE_CODE (t2) != code
      || TREE_TYPE (t1) != TREE_TYPE (t2))
    return 0;

  if (!operand_equal_p (t1, t2, 0))
    return 0;

#ifdef ENABLE_CHECKING
  /* Only allow them to compare equal if they also hash equal; otherwise
     results are nondeterminate, and we fail bootstrap comparison.  */
  gcc_assert (gimple_tree_hash (p1) == gimple_tree_hash (p2));
#endif

  return 1;
}

/* Link gimple statement GS to the end of the sequence *SEQ_P.  If
   *SEQ_P is NULL, a new sequence is allocated.  This function is
   similar to gimple_seq_add_stmt, but does not scan the operands.
   During gimplification, we need to manipulate statement sequences
   before the def/use vectors have been constructed.  */

void
gimple_seq_add_stmt_without_update (gimple_seq *seq_p, gimple gs)
{
  gimple_stmt_iterator si;

  if (gs == NULL)
    return;

  if (*seq_p == NULL)
    *seq_p = gimple_seq_alloc ();

  si = gsi_last (*seq_p);

  gsi_insert_after_without_update (&si, gs, GSI_NEW_STMT);
}

/* Shorter alias name for the above function for use in gimplify.c
   only.  */

static inline void
gimplify_seq_add_stmt (gimple_seq *seq_p, gimple gs)
{
  gimple_seq_add_stmt_without_update (seq_p, gs);
}

/* Append sequence SRC to the end of sequence *DST_P.  If *DST_P is
   NULL, a new sequence is allocated.   This function is
   similar to gimple_seq_add_seq, but does not scan the operands.
   During gimplification, we need to manipulate statement sequences
   before the def/use vectors have been constructed.  */

static void
gimplify_seq_add_seq (gimple_seq *dst_p, gimple_seq src)
{
  gimple_stmt_iterator si;

  if (src == NULL)
    return;

  if (*dst_p == NULL)
    *dst_p = gimple_seq_alloc ();

  si = gsi_last (*dst_p);
  gsi_insert_seq_after_without_update (&si, src, GSI_NEW_STMT);
}

/* Set up a context for the gimplifier.  */

void
push_gimplify_context (struct gimplify_ctx *c)
{
  memset (c, '\0', sizeof (*c));
  c->prev_context = gimplify_ctxp;
  gimplify_ctxp = c;
}

/* Tear down a context for the gimplifier.  If BODY is non-null, then
   put the temporaries into the outer BIND_EXPR.  Otherwise, put them
   in the local_decls.

   BODY is not a sequence, but the first tuple in a sequence.  */

void
pop_gimplify_context (gimple body)
{
  struct gimplify_ctx *c = gimplify_ctxp;

  gcc_assert (c && (c->bind_expr_stack == NULL
		    || VEC_empty (gimple, c->bind_expr_stack)));
  VEC_free (gimple, heap, c->bind_expr_stack);
  gimplify_ctxp = c->prev_context;

  if (body)
    declare_vars (c->temps, body, false);
  else
    record_vars (c->temps);

  if (c->temp_htab)
    htab_delete (c->temp_htab);
}

/* Push a GIMPLE_BIND tuple onto the stack of bindings.  */

static void
gimple_push_bind_expr (gimple gimple_bind)
{
  if (gimplify_ctxp->bind_expr_stack == NULL)
    gimplify_ctxp->bind_expr_stack = VEC_alloc (gimple, heap, 8);
  VEC_safe_push (gimple, heap, gimplify_ctxp->bind_expr_stack, gimple_bind);
}

/* Pop the first element off the stack of bindings.  */

static void
gimple_pop_bind_expr (void)
{
  VEC_pop (gimple, gimplify_ctxp->bind_expr_stack);
}

/* Return the first element of the stack of bindings.  */

gimple
gimple_current_bind_expr (void)
{
  return VEC_last (gimple, gimplify_ctxp->bind_expr_stack);
}

/* Return the stack of bindings created during gimplification.  */

VEC(gimple, heap) *
gimple_bind_expr_stack (void)
{
  return gimplify_ctxp->bind_expr_stack;
}

/* Return true iff there is a COND_EXPR between us and the innermost
   CLEANUP_POINT_EXPR.  This info is used by gimple_push_cleanup.  */

static bool
gimple_conditional_context (void)
{
  return gimplify_ctxp->conditions > 0;
}

/* Note that we've entered a COND_EXPR.  */

static void
gimple_push_condition (void)
{
#ifdef ENABLE_GIMPLE_CHECKING
  if (gimplify_ctxp->conditions == 0)
    gcc_assert (gimple_seq_empty_p (gimplify_ctxp->conditional_cleanups));
#endif
  ++(gimplify_ctxp->conditions);
}

/* Note that we've left a COND_EXPR.  If we're back at unconditional scope
   now, add any conditional cleanups we've seen to the prequeue.  */

static void
gimple_pop_condition (gimple_seq *pre_p)
{
  int conds = --(gimplify_ctxp->conditions);

  gcc_assert (conds >= 0);
  if (conds == 0)
    {
      gimplify_seq_add_seq (pre_p, gimplify_ctxp->conditional_cleanups);
      gimplify_ctxp->conditional_cleanups = NULL;
    }
}

/* A stable comparison routine for use with splay trees and DECLs.  */

static int
splay_tree_compare_decl_uid (splay_tree_key xa, splay_tree_key xb)
{
  tree a = (tree) xa;
  tree b = (tree) xb;

  return DECL_UID (a) - DECL_UID (b);
}

/* Create a new omp construct that deals with variable remapping.  */

static struct gimplify_omp_ctx *
new_omp_context (enum omp_region_type region_type)
{
  struct gimplify_omp_ctx *c;

  c = XCNEW (struct gimplify_omp_ctx);
  c->outer_context = gimplify_omp_ctxp;
  c->variables = splay_tree_new (splay_tree_compare_decl_uid, 0, 0);
  c->privatized_types = pointer_set_create ();
  c->location = input_location;
  c->region_type = region_type;
  if ((region_type & ORT_TASK) == 0)
    c->default_kind = OMP_CLAUSE_DEFAULT_SHARED;
  else
    c->default_kind = OMP_CLAUSE_DEFAULT_UNSPECIFIED;

  return c;
}

/* Destroy an omp construct that deals with variable remapping.  */

static void
delete_omp_context (struct gimplify_omp_ctx *c)
{
  splay_tree_delete (c->variables);
  pointer_set_destroy (c->privatized_types);
  XDELETE (c);
}

static void omp_add_variable (struct gimplify_omp_ctx *, tree, unsigned int);
static bool omp_notice_variable (struct gimplify_omp_ctx *, tree, bool);

/* Both gimplify the statement T and append it to *SEQ_P.  This function
   behaves exactly as gimplify_stmt, but you don't have to pass T as a
   reference.  */

void
gimplify_and_add (tree t, gimple_seq *seq_p)
{
  gimplify_stmt (&t, seq_p);
}

/* Gimplify statement T into sequence *SEQ_P, and return the first
   tuple in the sequence of generated tuples for this statement.
   Return NULL if gimplifying T produced no tuples.  */

static gimple
gimplify_and_return_first (tree t, gimple_seq *seq_p)
{
  gimple_stmt_iterator last = gsi_last (*seq_p);

  gimplify_and_add (t, seq_p);

  if (!gsi_end_p (last))
    {
      gsi_next (&last);
      return gsi_stmt (last);
    }
  else
    return gimple_seq_first_stmt (*seq_p);
}

/* Strip off a legitimate source ending from the input string NAME of
   length LEN.  Rather than having to know the names used by all of
   our front ends, we strip off an ending of a period followed by
   up to five characters.  (Java uses ".class".)  */

static inline void
remove_suffix (char *name, int len)
{
  int i;

  for (i = 2;  i < 8 && len > i;  i++)
    {
      if (name[len - i] == '.')
	{
	  name[len - i] = '\0';
	  break;
	}
    }
}

/* Create a new temporary name with PREFIX.  Return an identifier.  */

static GTY(()) unsigned int tmp_var_id_num;

tree
create_tmp_var_name (const char *prefix)
{
  char *tmp_name;

  if (prefix)
    {
      char *preftmp = ASTRDUP (prefix);

      remove_suffix (preftmp, strlen (preftmp));
      clean_symbol_name (preftmp);

      prefix = preftmp;
    }

  ASM_FORMAT_PRIVATE_NAME (tmp_name, prefix ? prefix : "T", tmp_var_id_num++);
  return get_identifier (tmp_name);
}

/* Create a new temporary variable declaration of type TYPE.
   Do NOT push it into the current binding.  */

tree
create_tmp_var_raw (tree type, const char *prefix)
{
  tree tmp_var;

  tmp_var = build_decl (input_location,
			VAR_DECL, prefix ? create_tmp_var_name (prefix) : NULL,
			type);

  /* The variable was declared by the compiler.  */
  DECL_ARTIFICIAL (tmp_var) = 1;
  /* And we don't want debug info for it.  */
  DECL_IGNORED_P (tmp_var) = 1;

  /* Make the variable writable.  */
  TREE_READONLY (tmp_var) = 0;

  DECL_EXTERNAL (tmp_var) = 0;
  TREE_STATIC (tmp_var) = 0;
  TREE_USED (tmp_var) = 1;

  return tmp_var;
}

/* Create a new temporary variable declaration of type TYPE.  DO push the
   variable into the current binding.  Further, assume that this is called
   only from gimplification or optimization, at which point the creation of
   certain types are bugs.  */

tree
create_tmp_var (tree type, const char *prefix)
{
  tree tmp_var;

  /* We don't allow types that are addressable (meaning we can't make copies),
     or incomplete.  We also used to reject every variable size objects here,
     but now support those for which a constant upper bound can be obtained.
     The processing for variable sizes is performed in gimple_add_tmp_var,
     point at which it really matters and possibly reached via paths not going
     through this function, e.g. after direct calls to create_tmp_var_raw.  */
  gcc_assert (!TREE_ADDRESSABLE (type) && COMPLETE_TYPE_P (type));

  tmp_var = create_tmp_var_raw (type, prefix);
  gimple_add_tmp_var (tmp_var);
  return tmp_var;
}

/* Create a new temporary variable declaration of type TYPE by calling
   create_tmp_var and if TYPE is a vector or a complex number, mark the new
   temporary as gimple register.  */

tree
create_tmp_reg (tree type, const char *prefix)
{
  tree tmp;

  tmp = create_tmp_var (type, prefix);
  if (TREE_CODE (type) == COMPLEX_TYPE
      || TREE_CODE (type) == VECTOR_TYPE)
    DECL_GIMPLE_REG_P (tmp) = 1;

  return tmp;
}

/* Create a temporary with a name derived from VAL.  Subroutine of
   lookup_tmp_var; nobody else should call this function.  */

static inline tree
create_tmp_from_val (tree val)
{
  /* Drop all qualifiers and address-space information from the value type.  */
  return create_tmp_var (TYPE_MAIN_VARIANT (TREE_TYPE (val)), get_name (val));
}

/* Create a temporary to hold the value of VAL.  If IS_FORMAL, try to reuse
   an existing expression temporary.  */

static tree
lookup_tmp_var (tree val, bool is_formal)
{
  tree ret;

  /* If not optimizing, never really reuse a temporary.  local-alloc
     won't allocate any variable that is used in more than one basic
     block, which means it will go into memory, causing much extra
     work in reload and final and poorer code generation, outweighing
     the extra memory allocation here.  */
  if (!optimize || !is_formal || TREE_SIDE_EFFECTS (val))
    ret = create_tmp_from_val (val);
  else
    {
      elt_t elt, *elt_p;
      void **slot;

      elt.val = val;
      if (gimplify_ctxp->temp_htab == NULL)
        gimplify_ctxp->temp_htab
	  = htab_create (1000, gimple_tree_hash, gimple_tree_eq, free);
      slot = htab_find_slot (gimplify_ctxp->temp_htab, (void *)&elt, INSERT);
      if (*slot == NULL)
	{
	  elt_p = XNEW (elt_t);
	  elt_p->val = val;
	  elt_p->temp = ret = create_tmp_from_val (val);
	  *slot = (void *) elt_p;
	}
      else
	{
	  elt_p = (elt_t *) *slot;
          ret = elt_p->temp;
	}
    }

  return ret;
}

/* Return true if T is a CALL_EXPR or an expression that can be
   assigned to a temporary.  Note that this predicate should only be
   used during gimplification.  See the rationale for this in
   gimplify_modify_expr.  */

static bool
is_gimple_reg_rhs_or_call (tree t)
{
  return (get_gimple_rhs_class (TREE_CODE (t)) != GIMPLE_INVALID_RHS
	  || TREE_CODE (t) == CALL_EXPR);
}

/* Return true if T is a valid memory RHS or a CALL_EXPR.  Note that
   this predicate should only be used during gimplification.  See the
   rationale for this in gimplify_modify_expr.  */

static bool
is_gimple_mem_rhs_or_call (tree t)
{
  /* If we're dealing with a renamable type, either source or dest must be
     a renamed variable.  */
  if (is_gimple_reg_type (TREE_TYPE (t)))
    return is_gimple_val (t);
  else
    return (is_gimple_val (t) || is_gimple_lvalue (t)
	    || TREE_CODE (t) == CALL_EXPR);
}

/* Helper for get_formal_tmp_var and get_initialized_tmp_var.  */

static tree
internal_get_tmp_var (tree val, gimple_seq *pre_p, gimple_seq *post_p,
                      bool is_formal)
{
  tree t, mod;

  /* Notice that we explicitly allow VAL to be a CALL_EXPR so that we
     can create an INIT_EXPR and convert it into a GIMPLE_CALL below.  */
  gimplify_expr (&val, pre_p, post_p, is_gimple_reg_rhs_or_call,
		 fb_rvalue);

  t = lookup_tmp_var (val, is_formal);

  if (is_formal
      && (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
	  || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE))
    DECL_GIMPLE_REG_P (t) = 1;

  mod = build2 (INIT_EXPR, TREE_TYPE (t), t, unshare_expr (val));

  SET_EXPR_LOCATION (mod, EXPR_LOC_OR_HERE (val));

  /* gimplify_modify_expr might want to reduce this further.  */
  gimplify_and_add (mod, pre_p);
  ggc_free (mod);

  /* If we're gimplifying into ssa, gimplify_modify_expr will have
     given our temporary an SSA name.  Find and return it.  */
  if (gimplify_ctxp->into_ssa)
    {
      gimple last = gimple_seq_last_stmt (*pre_p);
      t = gimple_get_lhs (last);
    }

  return t;
}

/* Return a formal temporary variable initialized with VAL.  PRE_P is as
   in gimplify_expr.  Only use this function if:

   1) The value of the unfactored expression represented by VAL will not
      change between the initialization and use of the temporary, and
   2) The temporary will not be otherwise modified.

   For instance, #1 means that this is inappropriate for SAVE_EXPR temps,
   and #2 means it is inappropriate for && temps.

   For other cases, use get_initialized_tmp_var instead.  */

tree
get_formal_tmp_var (tree val, gimple_seq *pre_p)
{
  return internal_get_tmp_var (val, pre_p, NULL, true);
}

/* Return a temporary variable initialized with VAL.  PRE_P and POST_P
   are as in gimplify_expr.  */

tree
get_initialized_tmp_var (tree val, gimple_seq *pre_p, gimple_seq *post_p)
{
  return internal_get_tmp_var (val, pre_p, post_p, false);
}

/* Declare all the variables in VARS in SCOPE.  If DEBUG_INFO is true,
   generate debug info for them; otherwise don't.  */

void
declare_vars (tree vars, gimple scope, bool debug_info)
{
  tree last = vars;
  if (last)
    {
      tree temps, block;

      gcc_assert (gimple_code (scope) == GIMPLE_BIND);

      temps = nreverse (last);

      block = gimple_bind_block (scope);
      gcc_assert (!block || TREE_CODE (block) == BLOCK);
      if (!block || !debug_info)
	{
	  DECL_CHAIN (last) = gimple_bind_vars (scope);
	  gimple_bind_set_vars (scope, temps);
	}
      else
	{
	  /* We need to attach the nodes both to the BIND_EXPR and to its
	     associated BLOCK for debugging purposes.  The key point here
	     is that the BLOCK_VARS of the BIND_EXPR_BLOCK of a BIND_EXPR
	     is a subchain of the BIND_EXPR_VARS of the BIND_EXPR.  */
	  if (BLOCK_VARS (block))
	    BLOCK_VARS (block) = chainon (BLOCK_VARS (block), temps);
	  else
	    {
	      gimple_bind_set_vars (scope,
	      			    chainon (gimple_bind_vars (scope), temps));
	      BLOCK_VARS (block) = temps;
	    }
	}
    }
}

/* For VAR a VAR_DECL of variable size, try to find a constant upper bound
   for the size and adjust DECL_SIZE/DECL_SIZE_UNIT accordingly.  Abort if
   no such upper bound can be obtained.  */

static void
force_constant_size (tree var)
{
  /* The only attempt we make is by querying the maximum size of objects
     of the variable's type.  */

  HOST_WIDE_INT max_size;

  gcc_assert (TREE_CODE (var) == VAR_DECL);

  max_size = max_int_size_in_bytes (TREE_TYPE (var));

  gcc_assert (max_size >= 0);

  DECL_SIZE_UNIT (var)
    = build_int_cst (TREE_TYPE (DECL_SIZE_UNIT (var)), max_size);
  DECL_SIZE (var)
    = build_int_cst (TREE_TYPE (DECL_SIZE (var)), max_size * BITS_PER_UNIT);
}

/* Push the temporary variable TMP into the current binding.  */

void
gimple_add_tmp_var (tree tmp)
{
  gcc_assert (!DECL_CHAIN (tmp) && !DECL_SEEN_IN_BIND_EXPR_P (tmp));

  /* Later processing assumes that the object size is constant, which might
     not be true at this point.  Force the use of a constant upper bound in
     this case.  */
  if (!host_integerp (DECL_SIZE_UNIT (tmp), 1))
    force_constant_size (tmp);

  DECL_CONTEXT (tmp) = current_function_decl;
  DECL_SEEN_IN_BIND_EXPR_P (tmp) = 1;

  if (gimplify_ctxp)
    {
      DECL_CHAIN (tmp) = gimplify_ctxp->temps;
      gimplify_ctxp->temps = tmp;

      /* Mark temporaries local within the nearest enclosing parallel.  */
      if (gimplify_omp_ctxp)
	{
	  struct gimplify_omp_ctx *ctx = gimplify_omp_ctxp;
	  while (ctx && ctx->region_type == ORT_WORKSHARE)
	    ctx = ctx->outer_context;
	  if (ctx)
	    omp_add_variable (ctx, tmp, GOVD_LOCAL | GOVD_SEEN);
	}
    }
  else if (cfun)
    record_vars (tmp);
  else
    {
      gimple_seq body_seq;

      /* This case is for nested functions.  We need to expose the locals
	 they create.  */
      body_seq = gimple_body (current_function_decl);
      declare_vars (tmp, gimple_seq_first_stmt (body_seq), false);
    }
}

/* Determine whether to assign a location to the statement GS.  */

static bool
should_carry_location_p (gimple gs)
{
  /* Don't emit a line note for a label.  We particularly don't want to
     emit one for the break label, since it doesn't actually correspond
     to the beginning of the loop/switch.  */
  if (gimple_code (gs) == GIMPLE_LABEL)
    return false;

  return true;
}

/* Return true if a location should not be emitted for this statement
   by annotate_one_with_location.  */

static inline bool
gimple_do_not_emit_location_p (gimple g)
{
  return gimple_plf (g, GF_PLF_1);
}

/* Mark statement G so a location will not be emitted by
   annotate_one_with_location.  */

static inline void
gimple_set_do_not_emit_location (gimple g)
{
  /* The PLF flags are initialized to 0 when a new tuple is created,
     so no need to initialize it anywhere.  */
  gimple_set_plf (g, GF_PLF_1, true);
}

/* Set the location for gimple statement GS to LOCATION.  */

static void
annotate_one_with_location (gimple gs, location_t location)
{
  if (!gimple_has_location (gs)
      && !gimple_do_not_emit_location_p (gs)
      && should_carry_location_p (gs))
    gimple_set_location (gs, location);
}

/* Set LOCATION for all the statements after iterator GSI in sequence
   SEQ.  If GSI is pointing to the end of the sequence, start with the
   first statement in SEQ.  */

static void
annotate_all_with_location_after (gimple_seq seq, gimple_stmt_iterator gsi,
				  location_t location)
{
  if (gsi_end_p (gsi))
    gsi = gsi_start (seq);
  else
    gsi_next (&gsi);

  for (; !gsi_end_p (gsi); gsi_next (&gsi))
    annotate_one_with_location (gsi_stmt (gsi), location);
}

/* Set the location for all the statements in a sequence STMT_P to LOCATION.  */

void
annotate_all_with_location (gimple_seq stmt_p, location_t location)
{
  gimple_stmt_iterator i;

  if (gimple_seq_empty_p (stmt_p))
    return;

  for (i = gsi_start (stmt_p); !gsi_end_p (i); gsi_next (&i))
    {
      gimple gs = gsi_stmt (i);
      annotate_one_with_location (gs, location);
    }
}

/* This page contains routines to unshare tree nodes, i.e. to duplicate tree
   nodes that are referenced more than once in GENERIC functions.  This is
   necessary because gimplification (translation into GIMPLE) is performed
   by modifying tree nodes in-place, so gimplication of a shared node in a
   first context could generate an invalid GIMPLE form in a second context.

   This is achieved with a simple mark/copy/unmark algorithm that walks the
   GENERIC representation top-down, marks nodes with TREE_VISITED the first
   time it encounters them, duplicates them if they already have TREE_VISITED
   set, and finally removes the TREE_VISITED marks it has set.

   The algorithm works only at the function level, i.e. it generates a GENERIC
   representation of a function with no nodes shared within the function when
   passed a GENERIC function (except for nodes that are allowed to be shared).

   At the global level, it is also necessary to unshare tree nodes that are
   referenced in more than one function, for the same aforementioned reason.
   This requires some cooperation from the front-end.  There are 2 strategies:

     1. Manual unsharing.  The front-end needs to call unshare_expr on every
        expression that might end up being shared across functions.

     2. Deep unsharing.  This is an extension of regular unsharing.  Instead
        of calling unshare_expr on expressions that might be shared across
        functions, the front-end pre-marks them with TREE_VISITED.  This will
        ensure that they are unshared on the first reference within functions
        when the regular unsharing algorithm runs.  The counterpart is that
        this algorithm must look deeper than for manual unsharing, which is
        specified by LANG_HOOKS_DEEP_UNSHARING.

  If there are only few specific cases of node sharing across functions, it is
  probably easier for a front-end to unshare the expressions manually.  On the
  contrary, if the expressions generated at the global level are as widespread
  as expressions generated within functions, deep unsharing is very likely the
  way to go.  */

/* Similar to copy_tree_r but do not copy SAVE_EXPR or TARGET_EXPR nodes.
   These nodes model computations that must be done once.  If we were to
   unshare something like SAVE_EXPR(i++), the gimplification process would
   create wrong code.  However, if DATA is non-null, it must hold a pointer
   set that is used to unshare the subtrees of these nodes.  */

static tree
mostly_copy_tree_r (tree *tp, int *walk_subtrees, void *data)
{
  tree t = *tp;
  enum tree_code code = TREE_CODE (t);

  /* Do not copy SAVE_EXPR, TARGET_EXPR or BIND_EXPR nodes themselves, but
     copy their subtrees if we can make sure to do it only once.  */
  if (code == SAVE_EXPR || code == TARGET_EXPR || code == BIND_EXPR)
    {
      if (data && !pointer_set_insert ((struct pointer_set_t *)data, t))
	;
      else
	*walk_subtrees = 0;
    }

  /* Stop at types, decls, constants like copy_tree_r.  */
  else if (TREE_CODE_CLASS (code) == tcc_type
	   || TREE_CODE_CLASS (code) == tcc_declaration
	   || TREE_CODE_CLASS (code) == tcc_constant
	   /* We can't do anything sensible with a BLOCK used as an
	      expression, but we also can't just die when we see it
	      because of non-expression uses.  So we avert our eyes
	      and cross our fingers.  Silly Java.  */
	   || code == BLOCK)
    *walk_subtrees = 0;

  /* Cope with the statement expression extension.  */
  else if (code == STATEMENT_LIST)
    ;

  /* Leave the bulk of the work to copy_tree_r itself.  */
  else
    copy_tree_r (tp, walk_subtrees, NULL);

  return NULL_TREE;
}

/* Callback for walk_tree to unshare most of the shared trees rooted at *TP.
   If *TP has been visited already, then *TP is deeply copied by calling
   mostly_copy_tree_r.  DATA is passed to mostly_copy_tree_r unmodified.  */

static tree
copy_if_shared_r (tree *tp, int *walk_subtrees, void *data)
{
  tree t = *tp;
  enum tree_code code = TREE_CODE (t);

  /* Skip types, decls, and constants.  But we do want to look at their
     types and the bounds of types.  Mark them as visited so we properly
     unmark their subtrees on the unmark pass.  If we've already seen them,
     don't look down further.  */
  if (TREE_CODE_CLASS (code) == tcc_type
      || TREE_CODE_CLASS (code) == tcc_declaration
      || TREE_CODE_CLASS (code) == tcc_constant)
    {
      if (TREE_VISITED (t))
	*walk_subtrees = 0;
      else
	TREE_VISITED (t) = 1;
    }

  /* If this node has been visited already, unshare it and don't look
     any deeper.  */
  else if (TREE_VISITED (t))
    {
      walk_tree (tp, mostly_copy_tree_r, data, NULL);
      *walk_subtrees = 0;
    }

  /* Otherwise, mark the node as visited and keep looking.  */
  else
    TREE_VISITED (t) = 1;

  return NULL_TREE;
}

/* Unshare most of the shared trees rooted at *TP.  DATA is passed to the
   copy_if_shared_r callback unmodified.  */

static inline void
copy_if_shared (tree *tp, void *data)
{
  walk_tree (tp, copy_if_shared_r, data, NULL);
}

/* Unshare all the trees in the body of FNDECL, as well as in the bodies of
   any nested functions.  */

static void
unshare_body (tree fndecl)
{
  struct cgraph_node *cgn = cgraph_get_node (fndecl);
  /* If the language requires deep unsharing, we need a pointer set to make
     sure we don't repeatedly unshare subtrees of unshareable nodes.  */
  struct pointer_set_t *visited
    = lang_hooks.deep_unsharing ? pointer_set_create () : NULL;

  copy_if_shared (&DECL_SAVED_TREE (fndecl), visited);
  copy_if_shared (&DECL_SIZE (DECL_RESULT (fndecl)), visited);
  copy_if_shared (&DECL_SIZE_UNIT (DECL_RESULT (fndecl)), visited);

  if (visited)
    pointer_set_destroy (visited);

  if (cgn)
    for (cgn = cgn->nested; cgn; cgn = cgn->next_nested)
      unshare_body (cgn->decl);
}

/* Callback for walk_tree to unmark the visited trees rooted at *TP.
   Subtrees are walked until the first unvisited node is encountered.  */

static tree
unmark_visited_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
{
  tree t = *tp;

  /* If this node has been visited, unmark it and keep looking.  */
  if (TREE_VISITED (t))
    TREE_VISITED (t) = 0;

  /* Otherwise, don't look any deeper.  */
  else
    *walk_subtrees = 0;