1/* Language independent return value optimizations
2   Copyright (C) 2004, 2005 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify
7it under the terms of the GNU General Public License as published by
8the Free Software Foundation; either version 2, or (at your option)
9any later version.
10
11GCC is distributed in the hope that it will be useful,
12but WITHOUT ANY WARRANTY; without even the implied warranty of
13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14GNU General Public License for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING.  If not, write to
18the Free Software Foundation, 51 Franklin Street, Fifth Floor,
19Boston, MA 02110-1301, USA.  */
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
51struct 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
57  /* This is the function's RESULT_DECL.  We will replace all occurrences
58     of VAR with RESULT_DECL when we apply this optimization.  */
59  tree result;
60};
61
62static 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
75static tree
76finalize_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;
83
84  /* Otherwise replace all occurrences of VAR with RESULT.  */
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
104static unsigned int
105tree_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;
111  block_stmt_iterator bsi;
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))
117    return 0;
118
119  /* Look through each block for assignments to the RESULT_DECL.  */
120  FOR_EACH_BB (bb)
121    {
122      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
123	{
124	  tree stmt = bsi_stmt (bsi);
125	  tree ret_expr;
126
127	  if (TREE_CODE (stmt) == RETURN_EXPR)
128	    {
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	    }
136	  else if (TREE_CODE (stmt) == MODIFY_EXPR
137		   && TREE_OPERAND (stmt, 0) == result)
138	    {
139	      ret_expr = TREE_OPERAND (stmt, 1);
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)
149		    return 0;
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))
164		return 0;
165	    }
166	  else if (TREE_CODE (stmt) == MODIFY_EXPR)
167	    {
168	      tree addr = get_base_address (TREE_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	    }
174	}
175    }
176
177  if (!found)
178    return 0;
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    {
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.  */
208	  if (TREE_CODE (*tp) == MODIFY_EXPR
209	      && TREE_OPERAND (*tp, 0) == result
210	      && TREE_OPERAND (*tp, 1) == found)
211	    bsi_remove (&bsi, true);
212	  else
213	    {
214	      walk_tree (tp, finalize_nrv_r, &data, 0);
215	      bsi_next (&bsi);
216	    }
217	}
218    }
219
220  /* FOUND is no longer used.  Ensure it gets removed.  */
221  var_ann (found)->used = 0;
222  return 0;
223}
224
225struct 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 */
238  TODO_dump_func | TODO_ggc_collect,			/* todo_flags_finish */
239  0					/* letter */
240};
241
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
250static bool
251dest_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
275/* Walk through the function looking for MODIFY_EXPRs with calls that
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
287static unsigned int
288execute_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
300	  if (TREE_CODE (stmt) == MODIFY_EXPR
301	      && (call = TREE_OPERAND (stmt, 1),
302		  TREE_CODE (call) == CALL_EXPR)
303	      && !CALL_EXPR_RETURN_SLOT_OPT (call)
304	      && aggregate_value_p (call, call))
305	    /* Check if the location being assigned to is
306	       call-clobbered.  */
307	    CALL_EXPR_RETURN_SLOT_OPT (call) =
308	      dest_safe_for_nrv_p (TREE_OPERAND (stmt, 0)) ? 1 : 0;
309	}
310    }
311  return 0;
312}
313
314struct 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};
330