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