gcc/tree-nrv.c

   1 /* Language independent return value optimizations
   2    Copyright (C) 2004, 2005, 2007 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 "rtl.h"
  26 #include "function.h"
  27 #include "basic-block.h"
  28 #include "expr.h"
  29 #include "diagnostic.h"
  30 #include "tree-flow.h"
  31 #include "timevar.h"
  32 #include "tree-dump.h"
  33 #include "tree-pass.h"
  34 #include "langhooks.h"
  35
  36 /* This file implements return value optimizations for functions which
  37    return aggregate types.
  38
  39    Basically this pass searches the function for return statements which
  40    return a local aggregate.  When converted to RTL such statements will
  41    generate a copy from the local aggregate to final return value destination
  42    mandated by the target's ABI.
  43
  44    That copy can often be avoided by directly constructing the return value
  45    into the final destination mandated by the target's ABI.
  46
  47    This is basically a generic equivalent to the C++ front-end's
  48    Named Return Value optimization.  */
  49
  50 struct nrv_data
  51 {
  52   /* This is the temporary (a VAR_DECL) which appears in all of
  53      this function's RETURN_EXPR statements.  */
  54   tree var;
  55
  56   /* This is the function's RESULT_DECL.  We will replace all occurrences
  57      of VAR with RESULT_DECL when we apply this optimization.  */
  58   tree result;
  59 };
  60
  61 static tree finalize_nrv_r (tree *, int *, void *);
  62
  63 /* Callback for the tree walker.
  64
  65    If TP refers to a RETURN_EXPR, then set the expression being returned
  66    to nrv_data->result.
  67
  68    If TP refers to nrv_data->var, then replace nrv_data->var with
  69    nrv_data->result.
  70
  71    If we reach a node where we know all the subtrees are uninteresting,
  72    then set *WALK_SUBTREES to zero.  */
  73
  74 static tree
  75 finalize_nrv_r (tree *tp, int *walk_subtrees, void *data)
  76 {
  77   struct nrv_data *dp = (struct nrv_data *)data;
  78
  79   /* No need to walk into types.  */
  80   if (TYPE_P (*tp))
  81     *walk_subtrees = 0;
  82
  83   /* Otherwise replace all occurrences of VAR with RESULT.  */
  84   else if (*tp == dp->var)
  85     *tp = dp->result;
  86
  87   /* Keep iterating.  */
  88   return NULL_TREE;
  89 }
  90
  91 /* Main entry point for return value optimizations.
  92
  93    If this function always returns the same local variable, and that
  94    local variable is an aggregate type, then replace the variable with
  95    the function's DECL_RESULT.
  96
  97    This is the equivalent of the C++ named return value optimization
  98    applied to optimized trees in a language independent form.  If we
  99    ever encounter languages which prevent this kind of optimization,
 100    then we could either have the languages register the optimization or
 101    we could change the gating function to check the current language.  */
 102
 103 static unsigned int
 104 tree_nrv (void)
 105 {
 106   tree result = DECL_RESULT (current_function_decl);
 107   tree result_type = TREE_TYPE (result);
 108   tree found = NULL;
 109   basic_block bb;
 110   block_stmt_iterator bsi;
 111   struct nrv_data data;
 112
 113   /* If this function does not return an aggregate type in memory, then
 114      there is nothing to do.  */
 115   if (!aggregate_value_p (result, current_function_decl))
 116     return 0;
 117
 118   /* Look through each block for assignments to the RESULT_DECL.  */
 119   FOR_EACH_BB (bb)
 120     {
 121       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 122         {
 123           tree stmt = bsi_stmt (bsi);
 124           tree ret_expr;
 125
 126           if (TREE_CODE (stmt) == RETURN_EXPR)
 127             {
 128               /* In a function with an aggregate return value, the
 129                  gimplifier has changed all non-empty RETURN_EXPRs to
 130                  return the RESULT_DECL.  */
 131               ret_expr = TREE_OPERAND (stmt, 0);
 132               if (ret_expr)
 133                 gcc_assert (ret_expr == result);
 134             }
 135           else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 136                    && GIMPLE_STMT_OPERAND (stmt, 0) == result)
 137             {
 138               ret_expr = GIMPLE_STMT_OPERAND (stmt, 1);
 139
 140               /* Now verify that this return statement uses the same value
 141                  as any previously encountered return statement.  */
 142               if (found != NULL)
 143                 {
 144                   /* If we found a return statement using a different variable
 145                      than previous return statements, then we can not perform
 146                      NRV optimizations.  */
 147                   if (found != ret_expr)
 148                     return 0;
 149                 }
 150               else
 151                 found = ret_expr;
 152
 153               /* The returned value must be a local automatic variable of the
 154                  same type and alignment as the function's result.  */
 155               if (TREE_CODE (found) != VAR_DECL
 156                   || TREE_THIS_VOLATILE (found)
 157                   || DECL_CONTEXT (found) != current_function_decl
 158                   || TREE_STATIC (found)
 159                   || TREE_ADDRESSABLE (found)
 160                   || DECL_ALIGN (found) > DECL_ALIGN (result)
 161                   || !useless_type_conversion_p (result_type,
 162                                                 TREE_TYPE (found)))
 163                 return 0;
 164             }
 165           else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
 166             {
 167               tree addr = get_base_address (GIMPLE_STMT_OPERAND (stmt, 0));
 168                /* If there's any MODIFY of component of RESULT,
 169                   then bail out.  */
 170               if (addr && addr == result)
 171                 return 0;
 172             }
 173         }
 174     }
 175
 176   if (!found)
 177     return 0;
 178
 179   /* If dumping details, then note once and only the NRV replacement.  */
 180   if (dump_file && (dump_flags & TDF_DETAILS))
 181     {
 182       fprintf (dump_file, "NRV Replaced: ");
 183       print_generic_expr (dump_file, found, dump_flags);
 184       fprintf (dump_file, "  with: ");
 185       print_generic_expr (dump_file, result, dump_flags);
 186       fprintf (dump_file, "\n");
 187     }
 188
 189   /* At this point we know that all the return statements return the
 190      same local which has suitable attributes for NRV.   Copy debugging
 191      information from FOUND to RESULT.  */
 192   DECL_NAME (result) = DECL_NAME (found);
 193   DECL_SOURCE_LOCATION (result) = DECL_SOURCE_LOCATION (found);
 194   DECL_ABSTRACT_ORIGIN (result) = DECL_ABSTRACT_ORIGIN (found);
 195   TREE_ADDRESSABLE (result) = TREE_ADDRESSABLE (found);
 196
 197   /* Now walk through the function changing all references to VAR to be
 198      RESULT.  */
 199   data.var = found;
 200   data.result = result;
 201   FOR_EACH_BB (bb)
 202     {
 203       for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 204         {
 205           tree *tp = bsi_stmt_ptr (bsi);
 206           /* If this is a copy from VAR to RESULT, remove it.  */
 207           if (TREE_CODE (*tp) == GIMPLE_MODIFY_STMT
 208               && GIMPLE_STMT_OPERAND (*tp, 0) == result
 209               && GIMPLE_STMT_OPERAND (*tp, 1) == found)
 210             bsi_remove (&bsi, true);
 211           else
 212             {
 213               walk_tree (tp, finalize_nrv_r, &data, 0);
 214               bsi_next (&bsi);
 215             }
 216         }
 217     }
 218
 219   /* FOUND is no longer used.  Ensure it gets removed.  */
 220   var_ann (found)->used = 0;
 221   return 0;
 222 }
 223
 224 struct tree_opt_pass pass_nrv =
 225 {
 226   "nrv",                                /* name */
 227   NULL,                                 /* gate */
 228   tree_nrv,                             /* execute */
 229   NULL,                                 /* sub */
 230   NULL,                                 /* next */
 231   0,                                    /* static_pass_number */
 232   TV_TREE_NRV,                          /* tv_id */
 233   PROP_cfg,                             /* properties_required */
 234   0,                                    /* properties_provided */
 235   0,                                    /* properties_destroyed */
 236   0,                                    /* todo_flags_start */
 237   TODO_dump_func | TODO_ggc_collect,                    /* todo_flags_finish */
 238   0                                     /* letter */
 239 };
 240
 241 /* Determine (pessimistically) whether DEST is available for NRV
 242    optimization, where DEST is expected to be the LHS of a modify
 243    expression where the RHS is a function returning an aggregate.
 244
 245    We search for a base VAR_DECL and look to see if it, or any of its
 246    subvars are clobbered.  Note that we could do better, for example, by
 247    attempting to doing points-to analysis on INDIRECT_REFs.  */
 248
 249 static bool
 250 dest_safe_for_nrv_p (tree dest)
 251 {
 252   subvar_t subvar;
 253
 254   while (handled_component_p (dest))
 255     dest = TREE_OPERAND (dest, 0);
 256
 257   if (! SSA_VAR_P (dest))
 258     return false;
 259
 260   if (TREE_CODE (dest) == SSA_NAME)
 261     dest = SSA_NAME_VAR (dest);
 262
 263   if (is_call_clobbered (dest))
 264     return false;
 265   for (subvar = get_subvars_for_var (dest); subvar; subvar = subvar->next)
 266     if (is_call_clobbered (subvar->var))
 267       return false;
 268   return true;
 269 }
 270
 271 /* Walk through the function looking for GIMPLE_MODIFY_STMTs with calls that
 272    return in memory on the RHS.  For each of these, determine whether it is
 273    safe to pass the address of the LHS as the return slot, and mark the
 274    call appropriately if so.
 275
 276    The NRV shares the return slot with a local variable in the callee; this
 277    optimization shares the return slot with the target of the call within
 278    the caller.  If the NRV is performed (which we can't know in general),
 279    this optimization is safe if the address of the target has not
 280    escaped prior to the call.  If it has, modifications to the local
 281    variable will produce visible changes elsewhere, as in PR c++/19317.  */
 282
 283 static unsigned int
 284 execute_return_slot_opt (void)
 285 {
 286   basic_block bb;
 287
 288   FOR_EACH_BB (bb)
 289     {
 290       block_stmt_iterator i;
 291       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 292         {
 293           tree stmt = bsi_stmt (i);
 294           tree call;
 295
 296           if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
 297               && (call = GIMPLE_STMT_OPERAND (stmt, 1),
 298                   TREE_CODE (call) == CALL_EXPR)
 299               && !CALL_EXPR_RETURN_SLOT_OPT (call)
 300               && aggregate_value_p (call, call))
 301             /* Check if the location being assigned to is
 302                call-clobbered.  */
 303             CALL_EXPR_RETURN_SLOT_OPT (call) =
 304               dest_safe_for_nrv_p (GIMPLE_STMT_OPERAND (stmt, 0)) ? 1 : 0;
 305         }
 306     }
 307   return 0;
 308 }
 309
 310 struct tree_opt_pass pass_return_slot =
 311 {
 312   "retslot",                            /* name */
 313   NULL,                                 /* gate */
 314   execute_return_slot_opt,              /* execute */
 315   NULL,                                 /* sub */
 316   NULL,                                 /* next */
 317   0,                                    /* static_pass_number */
 318   0,                                    /* tv_id */
 319   PROP_ssa | PROP_alias,                /* properties_required */
 320   0,                                    /* properties_provided */
 321   0,                                    /* properties_destroyed */
 322   0,                                    /* todo_flags_start */
 323   0,                                    /* todo_flags_finish */
 324   0                                     /* letter */
 325 };