gcc/tree-nrv.c

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