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