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