gcc/tree-nrv.c

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