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