1/* Language independent return value optimizations
2   Copyright (C) 2004-2015 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 3, 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 COPYING3.  If not see
18<http://www.gnu.org/licenses/>.  */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "tm.h"
24#include "hash-set.h"
25#include "machmode.h"
26#include "vec.h"
27#include "double-int.h"
28#include "input.h"
29#include "alias.h"
30#include "symtab.h"
31#include "wide-int.h"
32#include "inchash.h"
33#include "tree.h"
34#include "fold-const.h"
35#include "hard-reg-set.h"
36#include "input.h"
37#include "function.h"
38#include "predict.h"
39#include "dominance.h"
40#include "cfg.h"
41#include "basic-block.h"
42#include "tree-pretty-print.h"
43#include "tree-ssa-alias.h"
44#include "internal-fn.h"
45#include "gimple-expr.h"
46#include "is-a.h"
47#include "gimple.h"
48#include "gimple-iterator.h"
49#include "gimple-walk.h"
50#include "gimple-ssa.h"
51#include "stringpool.h"
52#include "tree-ssanames.h"
53#include "tree-pass.h"
54#include "langhooks.h"
55#include "flags.h"	/* For "optimize" in gate_pass_return_slot.
56			   FIXME: That should be up to the pass manager,
57			   but pass_nrv is not in pass_all_optimizations.  */
58
59/* This file implements return value optimizations for functions which
60   return aggregate types.
61
62   Basically this pass searches the function for return statements which
63   return a local aggregate.  When converted to RTL such statements will
64   generate a copy from the local aggregate to final return value destination
65   mandated by the target's ABI.
66
67   That copy can often be avoided by directly constructing the return value
68   into the final destination mandated by the target's ABI.
69
70   This is basically a generic equivalent to the C++ front-end's
71   Named Return Value optimization.  */
72
73struct nrv_data_t
74{
75  /* This is the temporary (a VAR_DECL) which appears in all of
76     this function's RETURN_EXPR statements.  */
77  tree var;
78
79  /* This is the function's RESULT_DECL.  We will replace all occurrences
80     of VAR with RESULT_DECL when we apply this optimization.  */
81  tree result;
82  int modified;
83};
84
85static tree finalize_nrv_r (tree *, int *, void *);
86
87/* Callback for the tree walker.
88
89   If TP refers to a RETURN_EXPR, then set the expression being returned
90   to nrv_data->result.
91
92   If TP refers to nrv_data->var, then replace nrv_data->var with
93   nrv_data->result.
94
95   If we reach a node where we know all the subtrees are uninteresting,
96   then set *WALK_SUBTREES to zero.  */
97
98static tree
99finalize_nrv_r (tree *tp, int *walk_subtrees, void *data)
100{
101  struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
102  struct nrv_data_t *dp = (struct nrv_data_t *) wi->info;
103
104  /* No need to walk into types.  */
105  if (TYPE_P (*tp))
106    *walk_subtrees = 0;
107
108  /* Otherwise replace all occurrences of VAR with RESULT.  */
109  else if (*tp == dp->var)
110    {
111      *tp = dp->result;
112      dp->modified = 1;
113    }
114
115  /* Keep iterating.  */
116  return NULL_TREE;
117}
118
119/* Main entry point for return value optimizations.
120
121   If this function always returns the same local variable, and that
122   local variable is an aggregate type, then replace the variable with
123   the function's DECL_RESULT.
124
125   This is the equivalent of the C++ named return value optimization
126   applied to optimized trees in a language independent form.  If we
127   ever encounter languages which prevent this kind of optimization,
128   then we could either have the languages register the optimization or
129   we could change the gating function to check the current language.  */
130
131namespace {
132
133const pass_data pass_data_nrv =
134{
135  GIMPLE_PASS, /* type */
136  "nrv", /* name */
137  OPTGROUP_NONE, /* optinfo_flags */
138  TV_TREE_NRV, /* tv_id */
139  ( PROP_ssa | PROP_cfg ), /* properties_required */
140  0, /* properties_provided */
141  0, /* properties_destroyed */
142  0, /* todo_flags_start */
143  0, /* todo_flags_finish */
144};
145
146class pass_nrv : public gimple_opt_pass
147{
148public:
149  pass_nrv (gcc::context *ctxt)
150    : gimple_opt_pass (pass_data_nrv, ctxt)
151  {}
152
153  /* opt_pass methods: */
154  virtual bool gate (function *) { return optimize > 0; }
155
156  virtual unsigned int execute (function *);
157
158}; // class pass_nrv
159
160unsigned int
161pass_nrv::execute (function *fun)
162{
163  tree result = DECL_RESULT (current_function_decl);
164  tree result_type = TREE_TYPE (result);
165  tree found = NULL;
166  basic_block bb;
167  gimple_stmt_iterator gsi;
168  struct nrv_data_t data;
169
170  /* If this function does not return an aggregate type in memory, then
171     there is nothing to do.  */
172  if (!aggregate_value_p (result, current_function_decl))
173    return 0;
174
175  /* If a GIMPLE type is returned in memory, finalize_nrv_r might create
176     non-GIMPLE.  */
177  if (is_gimple_reg_type (result_type))
178    return 0;
179
180  /* If the front end already did something like this, don't do it here.  */
181  if (DECL_NAME (result))
182    return 0;
183
184  /* If the result has its address taken then it might be modified
185     by means not detected in the following loop.  Bail out in this
186     case.  */
187  if (TREE_ADDRESSABLE (result))
188    return 0;
189
190  /* Look through each block for assignments to the RESULT_DECL.  */
191  FOR_EACH_BB_FN (bb, fun)
192    {
193      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
194	{
195	  gimple stmt = gsi_stmt (gsi);
196	  tree ret_val;
197
198	  if (greturn *return_stmt = dyn_cast <greturn *> (stmt))
199	    {
200	      /* In a function with an aggregate return value, the
201		 gimplifier has changed all non-empty RETURN_EXPRs to
202		 return the RESULT_DECL.  */
203	      ret_val = gimple_return_retval (return_stmt);
204	      if (ret_val)
205		gcc_assert (ret_val == result);
206	    }
207	  else if (gimple_has_lhs (stmt)
208		   && gimple_get_lhs (stmt) == result)
209	    {
210              tree rhs;
211
212	      if (!gimple_assign_copy_p (stmt))
213		return 0;
214
215	      rhs = gimple_assign_rhs1 (stmt);
216
217	      /* Now verify that this return statement uses the same value
218		 as any previously encountered return statement.  */
219	      if (found != NULL)
220		{
221		  /* If we found a return statement using a different variable
222		     than previous return statements, then we can not perform
223		     NRV optimizations.  */
224		  if (found != rhs)
225		    return 0;
226		}
227	      else
228		found = rhs;
229
230	      /* The returned value must be a local automatic variable of the
231		 same type and alignment as the function's result.  */
232	      if (TREE_CODE (found) != VAR_DECL
233		  || TREE_THIS_VOLATILE (found)
234		  || !auto_var_in_fn_p (found, current_function_decl)
235		  || TREE_ADDRESSABLE (found)
236		  || DECL_ALIGN (found) > DECL_ALIGN (result)
237		  || !useless_type_conversion_p (result_type,
238						 TREE_TYPE (found)))
239		return 0;
240	    }
241	  else if (gimple_has_lhs (stmt))
242	    {
243	      tree addr = get_base_address (gimple_get_lhs (stmt));
244	       /* If there's any MODIFY of component of RESULT,
245		  then bail out.  */
246	      if (addr && addr == result)
247		return 0;
248	    }
249	}
250    }
251
252  if (!found)
253    return 0;
254
255  /* If dumping details, then note once and only the NRV replacement.  */
256  if (dump_file && (dump_flags & TDF_DETAILS))
257    {
258      fprintf (dump_file, "NRV Replaced: ");
259      print_generic_expr (dump_file, found, dump_flags);
260      fprintf (dump_file, "  with: ");
261      print_generic_expr (dump_file, result, dump_flags);
262      fprintf (dump_file, "\n");
263    }
264
265  /* At this point we know that all the return statements return the
266     same local which has suitable attributes for NRV.   Copy debugging
267     information from FOUND to RESULT if it will be useful.  But don't set
268     DECL_ABSTRACT_ORIGIN to point at another function.  */
269  if (!DECL_IGNORED_P (found)
270      && !(DECL_ABSTRACT_ORIGIN (found)
271	   && DECL_CONTEXT (DECL_ABSTRACT_ORIGIN (found)) != current_function_decl))
272    {
273      DECL_NAME (result) = DECL_NAME (found);
274      DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
275      DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
276    }
277
278  TREE_ADDRESSABLE (result) |= TREE_ADDRESSABLE (found);
279
280  /* Now walk through the function changing all references to VAR to be
281     RESULT.  */
282  data.var = found;
283  data.result = result;
284  FOR_EACH_BB_FN (bb, fun)
285    {
286      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
287	{
288	  gimple stmt = gsi_stmt (gsi);
289	  /* If this is a copy from VAR to RESULT, remove it.  */
290	  if (gimple_assign_copy_p (stmt)
291	      && gimple_assign_lhs (stmt) == result
292	      && gimple_assign_rhs1 (stmt) == found)
293	    {
294	      unlink_stmt_vdef (stmt);
295	      gsi_remove (&gsi, true);
296	      release_defs (stmt);
297	    }
298	  else
299	    {
300	      struct walk_stmt_info wi;
301	      memset (&wi, 0, sizeof (wi));
302	      wi.info = &data;
303	      data.modified = 0;
304	      walk_gimple_op (stmt, finalize_nrv_r, &wi);
305	      if (data.modified)
306		update_stmt (stmt);
307	      gsi_next (&gsi);
308	    }
309	}
310    }
311
312  SET_DECL_VALUE_EXPR (found, result);
313  DECL_HAS_VALUE_EXPR_P (found) = 1;
314
315  return 0;
316}
317
318} // anon namespace
319
320gimple_opt_pass *
321make_pass_nrv (gcc::context *ctxt)
322{
323  return new pass_nrv (ctxt);
324}
325
326/* Determine (pessimistically) whether DEST is available for NRV
327   optimization, where DEST is expected to be the LHS of a modify
328   expression where the RHS is a function returning an aggregate.
329
330   DEST is available if it is not clobbered or used by the call.  */
331
332static bool
333dest_safe_for_nrv_p (gcall *call)
334{
335  tree dest = gimple_call_lhs (call);
336
337  dest = get_base_address (dest);
338  if (! dest)
339    return false;
340
341  if (TREE_CODE (dest) == SSA_NAME)
342    return true;
343
344  if (call_may_clobber_ref_p (call, dest)
345      || ref_maybe_used_by_stmt_p (call, dest))
346    return false;
347
348  return true;
349}
350
351/* Walk through the function looking for GIMPLE_ASSIGNs with calls that
352   return in memory on the RHS.  For each of these, determine whether it is
353   safe to pass the address of the LHS as the return slot, and mark the
354   call appropriately if so.
355
356   The NRV shares the return slot with a local variable in the callee; this
357   optimization shares the return slot with the target of the call within
358   the caller.  If the NRV is performed (which we can't know in general),
359   this optimization is safe if the address of the target has not
360   escaped prior to the call.  If it has, modifications to the local
361   variable will produce visible changes elsewhere, as in PR c++/19317.  */
362
363namespace {
364
365const pass_data pass_data_return_slot =
366{
367  GIMPLE_PASS, /* type */
368  "retslot", /* name */
369  OPTGROUP_NONE, /* optinfo_flags */
370  TV_NONE, /* tv_id */
371  PROP_ssa, /* properties_required */
372  0, /* properties_provided */
373  0, /* properties_destroyed */
374  0, /* todo_flags_start */
375  0, /* todo_flags_finish */
376};
377
378class pass_return_slot : public gimple_opt_pass
379{
380public:
381  pass_return_slot (gcc::context *ctxt)
382    : gimple_opt_pass (pass_data_return_slot, ctxt)
383  {}
384
385  /* opt_pass methods: */
386  virtual unsigned int execute (function *);
387
388}; // class pass_return_slot
389
390unsigned int
391pass_return_slot::execute (function *fun)
392{
393  basic_block bb;
394
395  FOR_EACH_BB_FN (bb, fun)
396    {
397      gimple_stmt_iterator gsi;
398      for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
399	{
400	  gcall *stmt;
401	  bool slot_opt_p;
402
403	  stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
404	  if (stmt
405	      && gimple_call_lhs (stmt)
406	      && !gimple_call_return_slot_opt_p (stmt)
407	      && aggregate_value_p (TREE_TYPE (gimple_call_lhs (stmt)),
408				    gimple_call_fndecl (stmt)))
409	    {
410	      /* Check if the location being assigned to is
411		 clobbered by the call.  */
412	      slot_opt_p = dest_safe_for_nrv_p (stmt);
413	      gimple_call_set_return_slot_opt (stmt, slot_opt_p);
414	    }
415	}
416    }
417  return 0;
418}
419
420} // anon namespace
421
422gimple_opt_pass *
423make_pass_return_slot (gcc::context *ctxt)
424{
425  return new pass_return_slot (ctxt);
426}
427