gcc/tree-nrv.c

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