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