[thirdparty/gcc.git] / gcc / tree-nrv.c

/* Language independent return value optimizations
   Copyright (C) 2004, 2005, 2007 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 "tm.h"
#include "tree.h"
#include "rtl.h"
#include "function.h"
#include "basic-block.h"
#include "expr.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "timevar.h"
#include "tree-dump.h"
#include "tree-pass.h"
#include "langhooks.h"

/* This file implements return value optimizations for functions which
   return aggregate types.

   Basically this pass searches the function for return statements which
   return a local aggregate.  When converted to RTL such statements will
   generate a copy from the local aggregate to final return value destination
   mandated by the target's ABI.

   That copy can often be avoided by directly constructing the return value
   into the final destination mandated by the target's ABI.

   This is basically a generic equivalent to the C++ front-end's 
   Named Return Value optimization.  */

struct nrv_data
{
  /* This is the temporary (a VAR_DECL) which appears in all of
     this function's RETURN_EXPR statements.  */
  tree var;

  /* This is the function's RESULT_DECL.  We will replace all occurrences
     of VAR with RESULT_DECL when we apply this optimization.  */
  tree result;
};

static tree finalize_nrv_r (tree *, int *, void *);

/* Callback for the tree walker.

   If TP refers to a RETURN_EXPR, then set the expression being returned
   to nrv_data->result.

   If TP refers to nrv_data->var, then replace nrv_data->var with
   nrv_data->result.

   If we reach a node where we know all the subtrees are uninteresting,
   then set *WALK_SUBTREES to zero.  */

static tree
finalize_nrv_r (tree *tp, int *walk_subtrees, void *data)
{
  struct nrv_data *dp = (struct nrv_data *)data;

  /* No need to walk into types.  */
  if (TYPE_P (*tp))
    *walk_subtrees = 0;

  /* Otherwise replace all occurrences of VAR with RESULT.  */
  else if (*tp == dp->var)
    *tp = dp->result;

  /* Keep iterating.  */
  return NULL_TREE;
}

/* Main entry point for return value optimizations.

   If this function always returns the same local variable, and that
   local variable is an aggregate type, then replace the variable with
   the function's DECL_RESULT.

   This is the equivalent of the C++ named return value optimization
   applied to optimized trees in a language independent form.  If we
   ever encounter languages which prevent this kind of optimization,
   then we could either have the languages register the optimization or
   we could change the gating function to check the current language.  */
   
static unsigned int
tree_nrv (void)
{
  tree result = DECL_RESULT (current_function_decl);
  tree result_type = TREE_TYPE (result);
  tree found = NULL;
  basic_block bb;
  block_stmt_iterator bsi;
  struct nrv_data data;

  /* If this function does not return an aggregate type in memory, then
     there is nothing to do.  */
  if (!aggregate_value_p (result, current_function_decl))
    return 0;

  /* Look through each block for assignments to the RESULT_DECL.  */
  FOR_EACH_BB (bb)
    {
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
	{
	  tree stmt = bsi_stmt (bsi);
	  tree ret_expr;

	  if (TREE_CODE (stmt) == RETURN_EXPR)
	    {
	      /* In a function with an aggregate return value, the
		 gimplifier has changed all non-empty RETURN_EXPRs to
		 return the RESULT_DECL.  */
	      ret_expr = TREE_OPERAND (stmt, 0);
	      if (ret_expr)
		gcc_assert (ret_expr == result);
	    }
	  else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
		   && GIMPLE_STMT_OPERAND (stmt, 0) == result)
	    {
	      ret_expr = GIMPLE_STMT_OPERAND (stmt, 1);

	      /* Now verify that this return statement uses the same value
		 as any previously encountered return statement.  */
	      if (found != NULL)
		{
		  /* If we found a return statement using a different variable
		     than previous return statements, then we can not perform
		     NRV optimizations.  */
		  if (found != ret_expr)
		    return 0;
		}
	      else
		found = ret_expr;

	      /* The returned value must be a local automatic variable of the
		 same type and alignment as the function's result.  */
	      if (TREE_CODE (found) != VAR_DECL
		  || TREE_THIS_VOLATILE (found)
		  || DECL_CONTEXT (found) != current_function_decl
		  || TREE_STATIC (found)
		  || TREE_ADDRESSABLE (found)
		  || DECL_ALIGN (found) > DECL_ALIGN (result)
		  || !useless_type_conversion_p (result_type,
					        TREE_TYPE (found)))
		return 0;
	    }
	  else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
	    {
	      tree addr = get_base_address (GIMPLE_STMT_OPERAND (stmt, 0));
	       /* If there's any MODIFY of component of RESULT, 
		  then bail out.  */
	      if (addr && addr == result)
		return 0;
	    }
	}
    }

  if (!found)
    return 0;

  /* If dumping details, then note once and only the NRV replacement.  */
  if (dump_file && (dump_flags & TDF_DETAILS))
    {
      fprintf (dump_file, "NRV Replaced: ");
      print_generic_expr (dump_file, found, dump_flags);
      fprintf (dump_file, "  with: ");
      print_generic_expr (dump_file, result, dump_flags);
      fprintf (dump_file, "\n");
    }

  /* At this point we know that all the return statements return the
     same local which has suitable attributes for NRV.   Copy debugging
     information from FOUND to RESULT.  */
  DECL_NAME (result) = DECL_NAME (found);
  DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
  DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
  TREE_ADDRESSABLE (result) = TREE_ADDRESSABLE (found);

  /* Now walk through the function changing all references to VAR to be
     RESULT.  */
  data.var = found;
  data.result = result;
  FOR_EACH_BB (bb)
    {
      for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
	{
	  tree *tp = bsi_stmt_ptr (bsi);
	  /* If this is a copy from VAR to RESULT, remove it.  */
	  if (TREE_CODE (*tp) == GIMPLE_MODIFY_STMT
	      && GIMPLE_STMT_OPERAND (*tp, 0) == result
	      && GIMPLE_STMT_OPERAND (*tp, 1) == found)
	    bsi_remove (&bsi, true);
	  else
	    {
	      walk_tree (tp, finalize_nrv_r, &data, 0);
	      bsi_next (&bsi);
	    }
	}
    }

  /* FOUND is no longer used.  Ensure it gets removed.  */
  var_ann (found)->used = 0;
  return 0;
}

struct tree_opt_pass pass_nrv = 
{
  "nrv",				/* name */
  NULL,					/* gate */
  tree_nrv,				/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_NRV,				/* tv_id */
  PROP_cfg,				/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_dump_func | TODO_ggc_collect,			/* todo_flags_finish */
  0					/* letter */
};

/* Determine (pessimistically) whether DEST is available for NRV
   optimization, where DEST is expected to be the LHS of a modify
   expression where the RHS is a function returning an aggregate.

   We search for a base VAR_DECL and look to see if it, or any of its
   subvars are clobbered.  Note that we could do better, for example, by
   attempting to doing points-to analysis on INDIRECT_REFs.  */

static bool
dest_safe_for_nrv_p (tree dest)
{
  subvar_t subvar;

  while (handled_component_p (dest))
    dest = TREE_OPERAND (dest, 0);

  if (! SSA_VAR_P (dest))
    return false;

  if (TREE_CODE (dest) == SSA_NAME)
    dest = SSA_NAME_VAR (dest);

  if (is_call_clobbered (dest))
    return false;
  for (subvar = get_subvars_for_var (dest); subvar; subvar = subvar->next)
    if (is_call_clobbered (subvar->var))
      return false;
  return true;
}

/* Walk through the function looking for GIMPLE_MODIFY_STMTs with calls that
   return in memory on the RHS.  For each of these, determine whether it is
   safe to pass the address of the LHS as the return slot, and mark the
   call appropriately if so.

   The NRV shares the return slot with a local variable in the callee; this
   optimization shares the return slot with the target of the call within
   the caller.  If the NRV is performed (which we can't know in general),
   this optimization is safe if the address of the target has not
   escaped prior to the call.  If it has, modifications to the local
   variable will produce visible changes elsewhere, as in PR c++/19317.  */

static unsigned int
execute_return_slot_opt (void)
{
  basic_block bb;

  FOR_EACH_BB (bb)
    {
      block_stmt_iterator i;
      for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
	{
	  tree stmt = bsi_stmt (i);
	  tree call;

	  if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
	      && (call = GIMPLE_STMT_OPERAND (stmt, 1),
		  TREE_CODE (call) == CALL_EXPR)
	      && !CALL_EXPR_RETURN_SLOT_OPT (call)
	      && aggregate_value_p (call, call))
	    /* Check if the location being assigned to is
	       call-clobbered.  */
	    CALL_EXPR_RETURN_SLOT_OPT (call) =
	      dest_safe_for_nrv_p (GIMPLE_STMT_OPERAND (stmt, 0)) ? 1 : 0;
	}
    }
  return 0;
}

struct tree_opt_pass pass_return_slot = 
{
  "retslot",				/* name */
  NULL,					/* gate */
  execute_return_slot_opt,		/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  0,					/* tv_id */
  PROP_ssa | PROP_alias,		/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  0,					/* todo_flags_finish */
  0					/* letter */
};
Commit	Line	Data
4ee9c684	1	/* Language independent return value optimizations
8c4c00c1	2	Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc.
4ee9c684	3
	4	This file is part of GCC.
	5
	6	GCC is free software; you can redistribute it and/or modify
	7	it under the terms of the GNU General Public License as published by
8c4c00c1	8	the Free Software Foundation; either version 3, or (at your option)
4ee9c684	9	any later version.
	10
	11	GCC is distributed in the hope that it will be useful,
	12	but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	GNU General Public License for more details.
	15
	16	You should have received a copy of the GNU General Public License
8c4c00c1	17	along with GCC; see the file COPYING3. If not see
8c4c00c1	18	<http://www.gnu.org/licenses/>. */
4ee9c684	19
	20	#include "config.h"
	21	#include "system.h"
	22	#include "coretypes.h"
	23	#include "tm.h"
	24	#include "tree.h"
	25	#include "rtl.h"
	26	#include "function.h"
	27	#include "basic-block.h"
	28	#include "expr.h"
	29	#include "diagnostic.h"
	30	#include "tree-flow.h"
	31	#include "timevar.h"
	32	#include "tree-dump.h"
	33	#include "tree-pass.h"
	34	#include "langhooks.h"
	35
	36	/* This file implements return value optimizations for functions which
	37	return aggregate types.
	38
	39	Basically this pass searches the function for return statements which
	40	return a local aggregate. When converted to RTL such statements will
	41	generate a copy from the local aggregate to final return value destination
	42	mandated by the target's ABI.
	43
	44	That copy can often be avoided by directly constructing the return value
	45	into the final destination mandated by the target's ABI.
	46
	47	This is basically a generic equivalent to the C++ front-end's
	48	Named Return Value optimization. */
	49
	50	struct nrv_data
	51	{
	52	/* This is the temporary (a VAR_DECL) which appears in all of
	53	this function's RETURN_EXPR statements. */
	54	tree var;
	55
365db11e	56	/* This is the function's RESULT_DECL. We will replace all occurrences
4ee9c684	57	of VAR with RESULT_DECL when we apply this optimization. */
	58	tree result;
	59	};
	60
	61	static tree finalize_nrv_r (tree , int , void *);
	62
	63	/* Callback for the tree walker.
	64
	65	If TP refers to a RETURN_EXPR, then set the expression being returned
	66	to nrv_data->result.
	67
	68	If TP refers to nrv_data->var, then replace nrv_data->var with
	69	nrv_data->result.
	70
	71	If we reach a node where we know all the subtrees are uninteresting,
	72	then set WALK_SUBTREES to zero. /
	73
	74	static tree
	75	finalize_nrv_r (tree tp, int walk_subtrees, void *data)
	76	{
	77	struct nrv_data dp = (struct nrv_data )data;
	78
	79	/* No need to walk into types. */
	80	if (TYPE_P (*tp))
	81	*walk_subtrees = 0;
15a9f039	82
2c763ed4	83	/* Otherwise replace all occurrences of VAR with RESULT. */
4ee9c684	84	else if (*tp == dp->var)
	85	*tp = dp->result;
	86
	87	/* Keep iterating. */
	88	return NULL_TREE;
	89	}
	90
	91	/* Main entry point for return value optimizations.
	92
	93	If this function always returns the same local variable, and that
	94	local variable is an aggregate type, then replace the variable with
	95	the function's DECL_RESULT.
	96
	97	This is the equivalent of the C++ named return value optimization
	98	applied to optimized trees in a language independent form. If we
	99	ever encounter languages which prevent this kind of optimization,
	100	then we could either have the languages register the optimization or
	101	we could change the gating function to check the current language. */
	102
2a1990e9	103	static unsigned int
4ee9c684	104	tree_nrv (void)
	105	{
	106	tree result = DECL_RESULT (current_function_decl);
	107	tree result_type = TREE_TYPE (result);
	108	tree found = NULL;
	109	basic_block bb;
84ef41be	110	block_stmt_iterator bsi;
4ee9c684	111	struct nrv_data data;
	112
	113	/* If this function does not return an aggregate type in memory, then
	114	there is nothing to do. */
	115	if (!aggregate_value_p (result, current_function_decl))
2a1990e9	116	return 0;
4ee9c684	117
84ef41be	118	/* Look through each block for assignments to the RESULT_DECL. */
4ee9c684	119	FOR_EACH_BB (bb)
4ee9c684	120	{
84ef41be	121	for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4ee9c684	122	{
84ef41be	123	tree stmt = bsi_stmt (bsi);
	124	tree ret_expr;
	125
	126	if (TREE_CODE (stmt) == RETURN_EXPR)
4ee9c684	127	{
84ef41be	128	/* In a function with an aggregate return value, the
	129	gimplifier has changed all non-empty RETURN_EXPRs to
	130	return the RESULT_DECL. */
	131	ret_expr = TREE_OPERAND (stmt, 0);
	132	if (ret_expr)
	133	gcc_assert (ret_expr == result);
	134	}
35cc02b5	135	else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
35cc02b5	136	&& GIMPLE_STMT_OPERAND (stmt, 0) == result)
84ef41be	137	{
35cc02b5	138	ret_expr = GIMPLE_STMT_OPERAND (stmt, 1);
84ef41be	139
	140	/* Now verify that this return statement uses the same value
	141	as any previously encountered return statement. */
	142	if (found != NULL)
	143	{
	144	/* If we found a return statement using a different variable
	145	than previous return statements, then we can not perform
	146	NRV optimizations. */
	147	if (found != ret_expr)
2a1990e9	148	return 0;
84ef41be	149	}
	150	else
	151	found = ret_expr;
	152
	153	/* The returned value must be a local automatic variable of the
	154	same type and alignment as the function's result. */
	155	if (TREE_CODE (found) != VAR_DECL
	156	\|\| TREE_THIS_VOLATILE (found)
	157	\|\| DECL_CONTEXT (found) != current_function_decl
	158	\|\| TREE_STATIC (found)
	159	\|\| TREE_ADDRESSABLE (found)
	160	\|\| DECL_ALIGN (found) > DECL_ALIGN (result)
c8ca3ee7	161	\|\| !useless_type_conversion_p (result_type,
c8ca3ee7	162	TREE_TYPE (found)))
2a1990e9	163	return 0;
4ee9c684	164	}
fdf6266d	165	else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
	166	{
	167	tree addr = get_base_address (GIMPLE_STMT_OPERAND (stmt, 0));
	168	/* If there's any MODIFY of component of RESULT,
	169	then bail out. */
	170	if (addr && addr == result)
	171	return 0;
	172	}
4ee9c684	173	}
	174	}
	175
	176	if (!found)
2a1990e9	177	return 0;
4ee9c684	178
	179	/* If dumping details, then note once and only the NRV replacement. */
	180	if (dump_file && (dump_flags & TDF_DETAILS))
	181	{
	182	fprintf (dump_file, "NRV Replaced: ");
	183	print_generic_expr (dump_file, found, dump_flags);
	184	fprintf (dump_file, " with: ");
	185	print_generic_expr (dump_file, result, dump_flags);
	186	fprintf (dump_file, "\n");
	187	}
	188
	189	/* At this point we know that all the return statements return the
	190	same local which has suitable attributes for NRV. Copy debugging
	191	information from FOUND to RESULT. */
	192	DECL_NAME (result) = DECL_NAME (found);
	193	DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
	194	DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
	195	TREE_ADDRESSABLE (result) = TREE_ADDRESSABLE (found);
	196
	197	/* Now walk through the function changing all references to VAR to be
	198	RESULT. */
	199	data.var = found;
	200	data.result = result;
	201	FOR_EACH_BB (bb)
	202	{
84ef41be	203	for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
	204	{
	205	tree *tp = bsi_stmt_ptr (bsi);
	206	/* If this is a copy from VAR to RESULT, remove it. */
35cc02b5	207	if (TREE_CODE (*tp) == GIMPLE_MODIFY_STMT
	208	&& GIMPLE_STMT_OPERAND (*tp, 0) == result
	209	&& GIMPLE_STMT_OPERAND (*tp, 1) == found)
f2428b62	210	bsi_remove (&bsi, true);
84ef41be	211	else
	212	{
	213	walk_tree (tp, finalize_nrv_r, &data, 0);
	214	bsi_next (&bsi);
	215	}
	216	}
4ee9c684	217	}
	218
	219	/* FOUND is no longer used. Ensure it gets removed. */
	220	var_ann (found)->used = 0;
2a1990e9	221	return 0;
4ee9c684	222	}
	223
	224	struct tree_opt_pass pass_nrv =
	225	{
	226	"nrv", /* name */
	227	NULL, /* gate */
	228	tree_nrv, /* execute */
	229	NULL, /* sub */
	230	NULL, /* next */
	231	0, /* static_pass_number */
	232	TV_TREE_NRV, /* tv_id */
	233	PROP_cfg, /* properties_required */
	234	0, /* properties_provided */
	235	0, /* properties_destroyed */
	236	0, /* todo_flags_start */
0f9005dd	237	TODO_dump_func \| TODO_ggc_collect, /* todo_flags_finish */
0f9005dd	238	0 /* letter */
4ee9c684	239	};
ea523851	240
166cf564	241	/* Determine (pessimistically) whether DEST is available for NRV
	242	optimization, where DEST is expected to be the LHS of a modify
	243	expression where the RHS is a function returning an aggregate.
	244
	245	We search for a base VAR_DECL and look to see if it, or any of its
	246	subvars are clobbered. Note that we could do better, for example, by
	247	attempting to doing points-to analysis on INDIRECT_REFs. */
	248
	249	static bool
	250	dest_safe_for_nrv_p (tree dest)
	251	{
fbb5d9ac	252	subvar_t subvar;
	253
	254	while (handled_component_p (dest))
	255	dest = TREE_OPERAND (dest, 0);
	256
	257	if (! SSA_VAR_P (dest))
	258	return false;
	259
	260	if (TREE_CODE (dest) == SSA_NAME)
	261	dest = SSA_NAME_VAR (dest);
	262
	263	if (is_call_clobbered (dest))
	264	return false;
	265	for (subvar = get_subvars_for_var (dest); subvar; subvar = subvar->next)
	266	if (is_call_clobbered (subvar->var))
	267	return false;
	268	return true;
166cf564	269	}
166cf564	270
35cc02b5	271	/* Walk through the function looking for GIMPLE_MODIFY_STMTs with calls that
ea523851	272	return in memory on the RHS. For each of these, determine whether it is
	273	safe to pass the address of the LHS as the return slot, and mark the
	274	call appropriately if so.
	275
	276	The NRV shares the return slot with a local variable in the callee; this
	277	optimization shares the return slot with the target of the call within
	278	the caller. If the NRV is performed (which we can't know in general),
	279	this optimization is safe if the address of the target has not
	280	escaped prior to the call. If it has, modifications to the local
	281	variable will produce visible changes elsewhere, as in PR c++/19317. */
	282
2a1990e9	283	static unsigned int
ea523851	284	execute_return_slot_opt (void)
	285	{
	286	basic_block bb;
	287
	288	FOR_EACH_BB (bb)
	289	{
	290	block_stmt_iterator i;
	291	for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
	292	{
	293	tree stmt = bsi_stmt (i);
	294	tree call;
	295
35cc02b5	296	if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
35cc02b5	297	&& (call = GIMPLE_STMT_OPERAND (stmt, 1),
ea523851	298	TREE_CODE (call) == CALL_EXPR)
	299	&& !CALL_EXPR_RETURN_SLOT_OPT (call)
	300	&& aggregate_value_p (call, call))
166cf564	301	/* Check if the location being assigned to is
	302	call-clobbered. */
	303	CALL_EXPR_RETURN_SLOT_OPT (call) =
35cc02b5	304	dest_safe_for_nrv_p (GIMPLE_STMT_OPERAND (stmt, 0)) ? 1 : 0;
ea523851	305	}
ea523851	306	}
2a1990e9	307	return 0;
ea523851	308	}
	309
	310	struct tree_opt_pass pass_return_slot =
	311	{
	312	"retslot", /* name */
	313	NULL, /* gate */
	314	execute_return_slot_opt, /* execute */
	315	NULL, /* sub */
	316	NULL, /* next */
	317	0, /* static_pass_number */
	318	0, /* tv_id */
	319	PROP_ssa \| PROP_alias, /* properties_required */
	320	0, /* properties_provided */
	321	0, /* properties_destroyed */
	322	0, /* todo_flags_start */
	323	0, /* todo_flags_finish */
	324	0 /* letter */
	325	};