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