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 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 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 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 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 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