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

/* Language independent return value optimizations
   Copyright (C) 2004, 2005 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 2, 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 COPYING.  If not, write to
the Free Software Foundation, 51 Franklin Street, Fifth Floor,
Boston, MA 02110-1301, USA.  */

#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)
		  || !lang_hooks.types_compatible_p (TREE_TYPE (found), 
						     result_type))
		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)
{
  switch (TREE_CODE (dest))
    {
      case VAR_DECL:
	{
	  subvar_t subvar;
	  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;
	}
      case ARRAY_REF:
      case COMPONENT_REF:
	return dest_safe_for_nrv_p (TREE_OPERAND (dest, 0));
      default:
	return false;
    }
}

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