gcc/tree-nrv.c

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