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