gcc/tree-nrv.c

   1 /* Language independent return value optimizations
   2    Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 3, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tm.h"
  25 #include "tree.h"
  26 #include "function.h"
  27 #include "basic-block.h"
  28 #include "tree-pretty-print.h"
  29 #include "tree-flow.h"
  30 #include "timevar.h"
  31 #include "tree-dump.h"
  32 #include "tree-pass.h"
  33 #include "langhooks.h"
  34 #include "flags.h"      /* For "optimize" in gate_pass_return_slot.
  35                            FIXME: That should be up to the pass manager,
  36                            but pass_nrv is not in pass_all_optimizations.  */
  37
  38 /* This file implements return value optimizations for functions which
  39    return aggregate types.
  40
  41    Basically this pass searches the function for return statements which
  42    return a local aggregate.  When converted to RTL such statements will
  43    generate a copy from the local aggregate to final return value destination
  44    mandated by the target's ABI.
  45
  46    That copy can often be avoided by directly constructing the return value
  47    into the final destination mandated by the target's ABI.
  48
  49    This is basically a generic equivalent to the C++ front-end's
  50    Named Return Value optimization.  */
  51
  52 struct nrv_data
  53 {
  54   /* This is the temporary (a VAR_DECL) which appears in all of
  55      this function's RETURN_EXPR statements.  */
  56   tree var;
  57
  58   /* This is the function's RESULT_DECL.  We will replace all occurrences
  59      of VAR with RESULT_DECL when we apply this optimization.  */
  60   tree result;
  61   int modified;
  62 };
  63
  64 static tree finalize_nrv_r (tree *, int *, void *);
  65
  66 /* Callback for the tree walker.
  67
  68    If TP refers to a RETURN_EXPR, then set the expression being returned
  69    to nrv_data->result.
  70
  71    If TP refers to nrv_data->var, then replace nrv_data->var with
  72    nrv_data->result.
  73
  74    If we reach a node where we know all the subtrees are uninteresting,
  75    then set *WALK_SUBTREES to zero.  */
  76
  77 static tree
  78 finalize_nrv_r (tree *tp, int *walk_subtrees, void *data)
  79 {
  80   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
  81   struct nrv_data *dp = (struct nrv_data *) wi->info;
  82
  83   /* No need to walk into types.  */
  84   if (TYPE_P (*tp))
  85     *walk_subtrees = 0;
  86
  87   /* Otherwise replace all occurrences of VAR with RESULT.  */
  88   else if (*tp == dp->var)
  89     {
  90       *tp = dp->result;
  91       dp->modified = 1;
  92     }
  93
  94   /* Keep iterating.  */
  95   return NULL_TREE;
  96 }
  97
  98 /* Main entry point for return value optimizations.
  99
 100    If this function always returns the same local variable, and that
 101    local variable is an aggregate type, then replace the variable with
 102    the function's DECL_RESULT.
 103
 104    This is the equivalent of the C++ named return value optimization
 105    applied to optimized trees in a language independent form.  If we
 106    ever encounter languages which prevent this kind of optimization,
 107    then we could either have the languages register the optimization or
 108    we could change the gating function to check the current language.  */
 109
 110 static unsigned int
 111 tree_nrv (void)
 112 {
 113   tree result = DECL_RESULT (current_function_decl);
 114   tree result_type = TREE_TYPE (result);
 115   tree found = NULL;
 116   basic_block bb;
 117   gimple_stmt_iterator gsi;
 118   struct nrv_data data;
 119
 120   /* If this function does not return an aggregate type in memory, then
 121      there is nothing to do.  */
 122   if (!aggregate_value_p (result, current_function_decl))
 123     return 0;
 124
 125   /* If a GIMPLE type is returned in memory, finalize_nrv_r might create
 126      non-GIMPLE.  */
 127   if (is_gimple_reg_type (result_type))
 128     return 0;
 129
 130   /* If the front end already did something like this, don't do it here.  */
 131   if (DECL_NAME (result))
 132     return 0;
 133
 134   /* If the result has its address taken then it might be modified
 135      by means not detected in the following loop.  Bail out in this
 136      case.  */
 137   if (TREE_ADDRESSABLE (result))
 138     return 0;
 139
 140   /* Look through each block for assignments to the RESULT_DECL.  */
 141   FOR_EACH_BB (bb)
 142     {
 143       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 144         {
 145           gimple stmt = gsi_stmt (gsi);
 146           tree ret_val;
 147
 148           if (gimple_code (stmt) == GIMPLE_RETURN)
 149             {
 150               /* In a function with an aggregate return value, the
 151                  gimplifier has changed all non-empty RETURN_EXPRs to
 152                  return the RESULT_DECL.  */
 153               ret_val = gimple_return_retval (stmt);
 154               if (ret_val)
 155                 gcc_assert (ret_val == result);
 156             }
 157           else if (gimple_has_lhs (stmt)
 158                    && gimple_get_lhs (stmt) == result)
 159             {
 160               tree rhs;
 161
 162               if (!gimple_assign_copy_p (stmt))
 163                 return 0;
 164
 165               rhs = gimple_assign_rhs1 (stmt);
 166
 167               /* Now verify that this return statement uses the same value
 168                  as any previously encountered return statement.  */
 169               if (found != NULL)
 170                 {
 171                   /* If we found a return statement using a different variable
 172                      than previous return statements, then we can not perform
 173                      NRV optimizations.  */
 174                   if (found != rhs)
 175                     return 0;
 176                 }
 177               else
 178                 found = rhs;
 179
 180               /* The returned value must be a local automatic variable of the
 181                  same type and alignment as the function's result.  */
 182               if (TREE_CODE (found) != VAR_DECL
 183                   || TREE_THIS_VOLATILE (found)
 184                   || DECL_CONTEXT (found) != current_function_decl
 185                   || TREE_STATIC (found)
 186                   || TREE_ADDRESSABLE (found)
 187                   || DECL_ALIGN (found) > DECL_ALIGN (result)
 188                   || !useless_type_conversion_p (result_type,
 189                                                  TREE_TYPE (found)))
 190                 return 0;
 191             }
 192           else if (gimple_has_lhs (stmt))
 193             {
 194               tree addr = get_base_address (gimple_get_lhs (stmt));
 195                /* If there's any MODIFY of component of RESULT,
 196                   then bail out.  */
 197               if (addr && addr == result)
 198                 return 0;
 199             }
 200         }
 201     }
 202
 203   if (!found)
 204     return 0;
 205
 206   /* If dumping details, then note once and only the NRV replacement.  */
 207   if (dump_file && (dump_flags & TDF_DETAILS))
 208     {
 209       fprintf (dump_file, "NRV Replaced: ");
 210       print_generic_expr (dump_file, found, dump_flags);
 211       fprintf (dump_file, "  with: ");
 212       print_generic_expr (dump_file, result, dump_flags);
 213       fprintf (dump_file, "\n");
 214     }
 215
 216   /* At this point we know that all the return statements return the
 217      same local which has suitable attributes for NRV.   Copy debugging
 218      information from FOUND to RESULT if it will be useful.  But don't set
 219      DECL_ABSTRACT_ORIGIN to point at another function.  */
 220   if (!DECL_IGNORED_P (found)
 221       && !(DECL_ABSTRACT_ORIGIN (found)
 222            && DECL_CONTEXT (DECL_ABSTRACT_ORIGIN (found)) != current_function_decl))
 223     {
 224       DECL_NAME (result) = DECL_NAME (found);
 225       DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
 226       DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
 227     }
 228
 229   TREE_ADDRESSABLE (result) |= TREE_ADDRESSABLE (found);
 230
 231   /* Now walk through the function changing all references to VAR to be
 232      RESULT.  */
 233   data.var = found;
 234   data.result = result;
 235   FOR_EACH_BB (bb)
 236     {
 237       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
 238         {
 239           gimple stmt = gsi_stmt (gsi);
 240           /* If this is a copy from VAR to RESULT, remove it.  */
 241           if (gimple_assign_copy_p (stmt)
 242               && gimple_assign_lhs (stmt) == result
 243               && gimple_assign_rhs1 (stmt) == found)
 244             {
 245               unlink_stmt_vdef (stmt);
 246               gsi_remove (&gsi, true);
 247               release_defs (stmt);
 248             }
 249           else
 250             {
 251               struct walk_stmt_info wi;
 252               memset (&wi, 0, sizeof (wi));
 253               wi.info = &data;
 254               data.modified = 0;
 255               walk_gimple_op (stmt, finalize_nrv_r, &wi);
 256               if (data.modified)
 257                 update_stmt (stmt);
 258               gsi_next (&gsi);
 259             }
 260         }
 261     }
 262
 263   SET_DECL_VALUE_EXPR (found, result);
 264   DECL_HAS_VALUE_EXPR_P (found) = 1;
 265
 266   /* FOUND is no longer used.  Ensure it gets removed.  */
 267   clear_is_used (found);
 268   return 0;
 269 }
 270
 271 static bool
 272 gate_pass_return_slot (void)
 273 {
 274   return optimize > 0;
 275 }
 276
 277 struct gimple_opt_pass pass_nrv =
 278 {
 279  {
 280   GIMPLE_PASS,
 281   "nrv",                                /* name */
 282   gate_pass_return_slot,                /* gate */
 283   tree_nrv,                             /* execute */
 284   NULL,                                 /* sub */
 285   NULL,                                 /* next */
 286   0,                                    /* static_pass_number */
 287   TV_TREE_NRV,                          /* tv_id */
 288   PROP_ssa | PROP_cfg,                          /* properties_required */
 289   0,                                    /* properties_provided */
 290   0,                                    /* properties_destroyed */
 291   0,                                    /* todo_flags_start */
 292   TODO_ggc_collect                      /* todo_flags_finish */
 293  }
 294 };
 295
 296 /* Determine (pessimistically) whether DEST is available for NRV
 297    optimization, where DEST is expected to be the LHS of a modify
 298    expression where the RHS is a function returning an aggregate.
 299
 300    DEST is available if it is not clobbered or used by the call.  */
 301
 302 static bool
 303 dest_safe_for_nrv_p (gimple call)
 304 {
 305   tree dest = gimple_call_lhs (call);
 306
 307   dest = get_base_address (dest);
 308   if (! dest)
 309     return false;
 310
 311   if (TREE_CODE (dest) == SSA_NAME)
 312     return true;
 313
 314   if (call_may_clobber_ref_p (call, dest)
 315       || ref_maybe_used_by_stmt_p (call, dest))
 316     return false;
 317
 318   return true;
 319 }
 320
 321 /* Walk through the function looking for GIMPLE_ASSIGNs with calls that
 322    return in memory on the RHS.  For each of these, determine whether it is
 323    safe to pass the address of the LHS as the return slot, and mark the
 324    call appropriately if so.
 325
 326    The NRV shares the return slot with a local variable in the callee; this
 327    optimization shares the return slot with the target of the call within
 328    the caller.  If the NRV is performed (which we can't know in general),
 329    this optimization is safe if the address of the target has not
 330    escaped prior to the call.  If it has, modifications to the local
 331    variable will produce visible changes elsewhere, as in PR c++/19317.  */
 332
 333 static unsigned int
 334 execute_return_slot_opt (void)
 335 {
 336   basic_block bb;
 337
 338   FOR_EACH_BB (bb)
 339     {
 340       gimple_stmt_iterator gsi;
 341       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 342         {
 343           gimple stmt = gsi_stmt (gsi);
 344           bool slot_opt_p;
 345
 346           if (is_gimple_call (stmt)
 347               && gimple_call_lhs (stmt)
 348               && !gimple_call_return_slot_opt_p (stmt)
 349               && aggregate_value_p (TREE_TYPE (gimple_call_lhs (stmt)),
 350                                     gimple_call_fndecl (stmt)))
 351             {
 352               /* Check if the location being assigned to is
 353                  clobbered by the call.  */
 354               slot_opt_p = dest_safe_for_nrv_p (stmt);
 355               gimple_call_set_return_slot_opt (stmt, slot_opt_p);
 356             }
 357         }
 358     }
 359   return 0;
 360 }
 361
 362 struct gimple_opt_pass pass_return_slot =
 363 {
 364  {
 365   GIMPLE_PASS,
 366   "retslot",                            /* name */
 367   NULL,                                 /* gate */
 368   execute_return_slot_opt,              /* execute */
 369   NULL,                                 /* sub */
 370   NULL,                                 /* next */
 371   0,                                    /* static_pass_number */
 372   TV_NONE,                              /* tv_id */
 373   PROP_ssa,                             /* properties_required */
 374   0,                                    /* properties_provided */
 375   0,                                    /* properties_destroyed */
 376   0,                                    /* todo_flags_start */
 377   0                                     /* todo_flags_finish */
 378  }
 379 };