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 namespace {
 117
 118 const pass_data pass_data_nrv =
 119 {
 120   GIMPLE_PASS, /* type */
 121   "nrv", /* name */
 122   OPTGROUP_NONE, /* optinfo_flags */
 123   true, /* has_execute */
 124   TV_TREE_NRV, /* tv_id */
 125   ( PROP_ssa | PROP_cfg ), /* properties_required */
 126   0, /* properties_provided */
 127   0, /* properties_destroyed */
 128   0, /* todo_flags_start */
 129   0, /* todo_flags_finish */
 130 };
 131
 132 class pass_nrv : public gimple_opt_pass
 133 {
 134 public:
 135   pass_nrv (gcc::context *ctxt)
 136     : gimple_opt_pass (pass_data_nrv, ctxt)
 137   {}
 138
 139   /* opt_pass methods: */
 140   virtual bool gate (function *) { return optimize > 0; }
 141
 142   virtual unsigned int execute (function *);
 143
 144 }; // class pass_nrv
 145
 146 unsigned int
 147 pass_nrv::execute (function *fun)
 148 {
 149   tree result = DECL_RESULT (current_function_decl);
 150   tree result_type = TREE_TYPE (result);
 151   tree found = NULL;
 152   basic_block bb;
 153   gimple_stmt_iterator gsi;
 154   struct nrv_data data;
 155
 156   /* If this function does not return an aggregate type in memory, then
 157      there is nothing to do.  */
 158   if (!aggregate_value_p (result, current_function_decl))
 159     return 0;
 160
 161   /* If a GIMPLE type is returned in memory, finalize_nrv_r might create
 162      non-GIMPLE.  */
 163   if (is_gimple_reg_type (result_type))
 164     return 0;
 165
 166   /* If the front end already did something like this, don't do it here.  */
 167   if (DECL_NAME (result))
 168     return 0;
 169
 170   /* If the result has its address taken then it might be modified
 171      by means not detected in the following loop.  Bail out in this
 172      case.  */
 173   if (TREE_ADDRESSABLE (result))
 174     return 0;
 175
 176   /* Look through each block for assignments to the RESULT_DECL.  */
 177   FOR_EACH_BB_FN (bb, fun)
 178     {
 179       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 180         {
 181           gimple stmt = gsi_stmt (gsi);
 182           tree ret_val;
 183
 184           if (gimple_code (stmt) == GIMPLE_RETURN)
 185             {
 186               /* In a function with an aggregate return value, the
 187                  gimplifier has changed all non-empty RETURN_EXPRs to
 188                  return the RESULT_DECL.  */
 189               ret_val = gimple_return_retval (stmt);
 190               if (ret_val)
 191                 gcc_assert (ret_val == result);
 192             }
 193           else if (gimple_has_lhs (stmt)
 194                    && gimple_get_lhs (stmt) == result)
 195             {
 196               tree rhs;
 197
 198               if (!gimple_assign_copy_p (stmt))
 199                 return 0;
 200
 201               rhs = gimple_assign_rhs1 (stmt);
 202
 203               /* Now verify that this return statement uses the same value
 204                  as any previously encountered return statement.  */
 205               if (found != NULL)
 206                 {
 207                   /* If we found a return statement using a different variable
 208                      than previous return statements, then we can not perform
 209                      NRV optimizations.  */
 210                   if (found != rhs)
 211                     return 0;
 212                 }
 213               else
 214                 found = rhs;
 215
 216               /* The returned value must be a local automatic variable of the
 217                  same type and alignment as the function's result.  */
 218               if (TREE_CODE (found) != VAR_DECL
 219                   || TREE_THIS_VOLATILE (found)
 220                   || DECL_CONTEXT (found) != current_function_decl
 221                   || TREE_STATIC (found)
 222                   || TREE_ADDRESSABLE (found)
 223                   || DECL_ALIGN (found) > DECL_ALIGN (result)
 224                   || !useless_type_conversion_p (result_type,
 225                                                  TREE_TYPE (found)))
 226                 return 0;
 227             }
 228           else if (gimple_has_lhs (stmt))
 229             {
 230               tree addr = get_base_address (gimple_get_lhs (stmt));
 231                /* If there's any MODIFY of component of RESULT,
 232                   then bail out.  */
 233               if (addr && addr == result)
 234                 return 0;
 235             }
 236         }
 237     }
 238
 239   if (!found)
 240     return 0;
 241
 242   /* If dumping details, then note once and only the NRV replacement.  */
 243   if (dump_file && (dump_flags & TDF_DETAILS))
 244     {
 245       fprintf (dump_file, "NRV Replaced: ");
 246       print_generic_expr (dump_file, found, dump_flags);
 247       fprintf (dump_file, "  with: ");
 248       print_generic_expr (dump_file, result, dump_flags);
 249       fprintf (dump_file, "\n");
 250     }
 251
 252   /* At this point we know that all the return statements return the
 253      same local which has suitable attributes for NRV.   Copy debugging
 254      information from FOUND to RESULT if it will be useful.  But don't set
 255      DECL_ABSTRACT_ORIGIN to point at another function.  */
 256   if (!DECL_IGNORED_P (found)
 257       && !(DECL_ABSTRACT_ORIGIN (found)
 258            && DECL_CONTEXT (DECL_ABSTRACT_ORIGIN (found)) != current_function_decl))
 259     {
 260       DECL_NAME (result) = DECL_NAME (found);
 261       DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
 262       DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
 263     }
 264
 265   TREE_ADDRESSABLE (result) |= TREE_ADDRESSABLE (found);
 266
 267   /* Now walk through the function changing all references to VAR to be
 268      RESULT.  */
 269   data.var = found;
 270   data.result = result;
 271   FOR_EACH_BB_FN (bb, fun)
 272     {
 273       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 274         {
 275           gimple stmt = gsi_stmt (gsi);
 276           /* If this is a copy from VAR to RESULT, remove it.  */
 277           if (gimple_assign_copy_p (stmt)
 278               && gimple_assign_lhs (stmt) == result
 279               && gimple_assign_rhs1 (stmt) == found)
 280             {
 281               unlink_stmt_vdef (stmt);
 282               gsi_remove (&gsi, true);
 283               release_defs (stmt);
 284             }
 285           else
 286             {
 287               struct walk_stmt_info wi;
 288               memset (&wi, 0, sizeof (wi));
 289               wi.info = &data;
 290               data.modified = 0;
 291               walk_gimple_op (stmt, finalize_nrv_r, &wi);
 292               if (data.modified)
 293                 update_stmt (stmt);
 294               gsi_next (&gsi);
 295             }
 296         }
 297     }
 298
 299   SET_DECL_VALUE_EXPR (found, result);
 300   DECL_HAS_VALUE_EXPR_P (found) = 1;
 301
 302   return 0;
 303 }
 304
 305 } // anon namespace
 306
 307 gimple_opt_pass *
 308 make_pass_nrv (gcc::context *ctxt)
 309 {
 310   return new pass_nrv (ctxt);
 311 }
 312
 313 /* Determine (pessimistically) whether DEST is available for NRV
 314    optimization, where DEST is expected to be the LHS of a modify
 315    expression where the RHS is a function returning an aggregate.
 316
 317    DEST is available if it is not clobbered or used by the call.  */
 318
 319 static bool
 320 dest_safe_for_nrv_p (gimple call)
 321 {
 322   tree dest = gimple_call_lhs (call);
 323
 324   dest = get_base_address (dest);
 325   if (! dest)
 326     return false;
 327
 328   if (TREE_CODE (dest) == SSA_NAME)
 329     return true;
 330
 331   if (call_may_clobber_ref_p (call, dest)
 332       || ref_maybe_used_by_stmt_p (call, dest))
 333     return false;
 334
 335   return true;
 336 }
 337
 338 /* Walk through the function looking for GIMPLE_ASSIGNs with calls that
 339    return in memory on the RHS.  For each of these, determine whether it is
 340    safe to pass the address of the LHS as the return slot, and mark the
 341    call appropriately if so.
 342
 343    The NRV shares the return slot with a local variable in the callee; this
 344    optimization shares the return slot with the target of the call within
 345    the caller.  If the NRV is performed (which we can't know in general),
 346    this optimization is safe if the address of the target has not
 347    escaped prior to the call.  If it has, modifications to the local
 348    variable will produce visible changes elsewhere, as in PR c++/19317.  */
 349
 350 namespace {
 351
 352 const pass_data pass_data_return_slot =
 353 {
 354   GIMPLE_PASS, /* type */
 355   "retslot", /* name */
 356   OPTGROUP_NONE, /* optinfo_flags */
 357   true, /* has_execute */
 358   TV_NONE, /* tv_id */
 359   PROP_ssa, /* properties_required */
 360   0, /* properties_provided */
 361   0, /* properties_destroyed */
 362   0, /* todo_flags_start */
 363   0, /* todo_flags_finish */
 364 };
 365
 366 class pass_return_slot : public gimple_opt_pass
 367 {
 368 public:
 369   pass_return_slot (gcc::context *ctxt)
 370     : gimple_opt_pass (pass_data_return_slot, ctxt)
 371   {}
 372
 373   /* opt_pass methods: */
 374   virtual unsigned int execute (function *);
 375
 376 }; // class pass_return_slot
 377
 378 unsigned int
 379 pass_return_slot::execute (function *fun)
 380 {
 381   basic_block bb;
 382
 383   FOR_EACH_BB_FN (bb, fun)
 384     {
 385       gimple_stmt_iterator gsi;
 386       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 387         {
 388           gimple stmt = gsi_stmt (gsi);
 389           bool slot_opt_p;
 390
 391           if (is_gimple_call (stmt)
 392               && gimple_call_lhs (stmt)
 393               && !gimple_call_return_slot_opt_p (stmt)
 394               && aggregate_value_p (TREE_TYPE (gimple_call_lhs (stmt)),
 395                                     gimple_call_fndecl (stmt)))
 396             {
 397               /* Check if the location being assigned to is
 398                  clobbered by the call.  */
 399               slot_opt_p = dest_safe_for_nrv_p (stmt);
 400               gimple_call_set_return_slot_opt (stmt, slot_opt_p);
 401             }
 402         }
 403     }
 404   return 0;
 405 }
 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 }