gcc/tree-nrv.c

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