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