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