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_t
  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_t *dp = (struct nrv_data_t *) 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_t 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_return return_stmt = dyn_cast <gimple_return> (stmt))
 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 (return_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                   || !auto_var_in_fn_p (found, current_function_decl)
 220                   || TREE_ADDRESSABLE (found)
 221                   || DECL_ALIGN (found) > DECL_ALIGN (result)
 222                   || !useless_type_conversion_p (result_type,
 223                                                  TREE_TYPE (found)))
 224                 return 0;
 225             }
 226           else if (gimple_has_lhs (stmt))
 227             {
 228               tree addr = get_base_address (gimple_get_lhs (stmt));
 229                /* If there's any MODIFY of component of RESULT,
 230                   then bail out.  */
 231               if (addr && addr == result)
 232                 return 0;
 233             }
 234         }
 235     }
 236
 237   if (!found)
 238     return 0;
 239
 240   /* If dumping details, then note once and only the NRV replacement.  */
 241   if (dump_file && (dump_flags & TDF_DETAILS))
 242     {
 243       fprintf (dump_file, "NRV Replaced: ");
 244       print_generic_expr (dump_file, found, dump_flags);
 245       fprintf (dump_file, "  with: ");
 246       print_generic_expr (dump_file, result, dump_flags);
 247       fprintf (dump_file, "\n");
 248     }
 249
 250   /* At this point we know that all the return statements return the
 251      same local which has suitable attributes for NRV.   Copy debugging
 252      information from FOUND to RESULT if it will be useful.  But don't set
 253      DECL_ABSTRACT_ORIGIN to point at another function.  */
 254   if (!DECL_IGNORED_P (found)
 255       && !(DECL_ABSTRACT_ORIGIN (found)
 256            && DECL_CONTEXT (DECL_ABSTRACT_ORIGIN (found)) != current_function_decl))
 257     {
 258       DECL_NAME (result) = DECL_NAME (found);
 259       DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
 260       DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
 261     }
 262
 263   TREE_ADDRESSABLE (result) |= TREE_ADDRESSABLE (found);
 264
 265   /* Now walk through the function changing all references to VAR to be
 266      RESULT.  */
 267   data.var = found;
 268   data.result = result;
 269   FOR_EACH_BB_FN (bb, fun)
 270     {
 271       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 272         {
 273           gimple stmt = gsi_stmt (gsi);
 274           /* If this is a copy from VAR to RESULT, remove it.  */
 275           if (gimple_assign_copy_p (stmt)
 276               && gimple_assign_lhs (stmt) == result
 277               && gimple_assign_rhs1 (stmt) == found)
 278             {
 279               unlink_stmt_vdef (stmt);
 280               gsi_remove (&gsi, true);
 281               release_defs (stmt);
 282             }
 283           else
 284             {
 285               struct walk_stmt_info wi;
 286               memset (&wi, 0, sizeof (wi));
 287               wi.info = &data;
 288               data.modified = 0;
 289               walk_gimple_op (stmt, finalize_nrv_r, &wi);
 290               if (data.modified)
 291                 update_stmt (stmt);
 292               gsi_next (&gsi);
 293             }
 294         }
 295     }
 296
 297   SET_DECL_VALUE_EXPR (found, result);
 298   DECL_HAS_VALUE_EXPR_P (found) = 1;
 299
 300   return 0;
 301 }
 302
 303 } // anon namespace
 304
 305 gimple_opt_pass *
 306 make_pass_nrv (gcc::context *ctxt)
 307 {
 308   return new pass_nrv (ctxt);
 309 }
 310
 311 /* Determine (pessimistically) whether DEST is available for NRV
 312    optimization, where DEST is expected to be the LHS of a modify
 313    expression where the RHS is a function returning an aggregate.
 314
 315    DEST is available if it is not clobbered or used by the call.  */
 316
 317 static bool
 318 dest_safe_for_nrv_p (gimple_call call)
 319 {
 320   tree dest = gimple_call_lhs (call);
 321
 322   dest = get_base_address (dest);
 323   if (! dest)
 324     return false;
 325
 326   if (TREE_CODE (dest) == SSA_NAME)
 327     return true;
 328
 329   if (call_may_clobber_ref_p (call, dest)
 330       || ref_maybe_used_by_stmt_p (call, dest))
 331     return false;
 332
 333   return true;
 334 }
 335
 336 /* Walk through the function looking for GIMPLE_ASSIGNs with calls that
 337    return in memory on the RHS.  For each of these, determine whether it is
 338    safe to pass the address of the LHS as the return slot, and mark the
 339    call appropriately if so.
 340
 341    The NRV shares the return slot with a local variable in the callee; this
 342    optimization shares the return slot with the target of the call within
 343    the caller.  If the NRV is performed (which we can't know in general),
 344    this optimization is safe if the address of the target has not
 345    escaped prior to the call.  If it has, modifications to the local
 346    variable will produce visible changes elsewhere, as in PR c++/19317.  */
 347
 348 namespace {
 349
 350 const pass_data pass_data_return_slot =
 351 {
 352   GIMPLE_PASS, /* type */
 353   "retslot", /* name */
 354   OPTGROUP_NONE, /* optinfo_flags */
 355   TV_NONE, /* tv_id */
 356   PROP_ssa, /* properties_required */
 357   0, /* properties_provided */
 358   0, /* properties_destroyed */
 359   0, /* todo_flags_start */
 360   0, /* todo_flags_finish */
 361 };
 362
 363 class pass_return_slot : public gimple_opt_pass
 364 {
 365 public:
 366   pass_return_slot (gcc::context *ctxt)
 367     : gimple_opt_pass (pass_data_return_slot, ctxt)
 368   {}
 369
 370   /* opt_pass methods: */
 371   virtual unsigned int execute (function *);
 372
 373 }; // class pass_return_slot
 374
 375 unsigned int
 376 pass_return_slot::execute (function *fun)
 377 {
 378   basic_block bb;
 379
 380   FOR_EACH_BB_FN (bb, fun)
 381     {
 382       gimple_stmt_iterator gsi;
 383       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 384         {
 385           gimple_call stmt;
 386           bool slot_opt_p;
 387
 388           stmt = dyn_cast <gimple_call> (gsi_stmt (gsi));
 389           if (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 }