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 void
 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;
 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;
 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;
 165             }
 166         }
 167     }
 168
 169   if (!found)
 170     return;
 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 }
 215
 216 struct tree_opt_pass pass_nrv =
 217 {
 218   "nrv",                                /* name */
 219   NULL,                                 /* gate */
 220   tree_nrv,                             /* execute */
 221   NULL,                                 /* sub */
 222   NULL,                                 /* next */
 223   0,                                    /* static_pass_number */
 224   TV_TREE_NRV,                          /* tv_id */
 225   PROP_cfg,                             /* properties_required */
 226   0,                                    /* properties_provided */
 227   0,                                    /* properties_destroyed */
 228   0,                                    /* todo_flags_start */
 229   TODO_dump_func | TODO_ggc_collect,                    /* todo_flags_finish */
 230   0                                     /* letter */
 231 };
 232
 233 /* Walk through the function looking for MODIFY_EXPRs with calls that
 234    return in memory on the RHS.  For each of these, determine whether it is
 235    safe to pass the address of the LHS as the return slot, and mark the
 236    call appropriately if so.
 237
 238    The NRV shares the return slot with a local variable in the callee; this
 239    optimization shares the return slot with the target of the call within
 240    the caller.  If the NRV is performed (which we can't know in general),
 241    this optimization is safe if the address of the target has not
 242    escaped prior to the call.  If it has, modifications to the local
 243    variable will produce visible changes elsewhere, as in PR c++/19317.  */
 244
 245 static void
 246 execute_return_slot_opt (void)
 247 {
 248   basic_block bb;
 249
 250   FOR_EACH_BB (bb)
 251     {
 252       block_stmt_iterator i;
 253       for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i))
 254         {
 255           tree stmt = bsi_stmt (i);
 256           tree call;
 257
 258           if (TREE_CODE (stmt) == MODIFY_EXPR
 259               && (call = TREE_OPERAND (stmt, 1),
 260                   TREE_CODE (call) == CALL_EXPR)
 261               && !CALL_EXPR_RETURN_SLOT_OPT (call)
 262               && aggregate_value_p (call, call))
 263             {
 264               def_operand_p def_p;
 265               ssa_op_iter op_iter;
 266
 267               /* We determine whether or not the LHS address escapes by
 268                  asking whether it is call clobbered.  When the LHS isn't a
 269                  simple decl, we need to check the VDEFs, so it's simplest
 270                  to just loop through all the DEFs.  */
 271               FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_ALL_DEFS)
 272                 {
 273                   tree def = DEF_FROM_PTR (def_p);
 274                   if (TREE_CODE (def) == SSA_NAME)
 275                     def = SSA_NAME_VAR (def);
 276                   if (is_call_clobbered (def))
 277                     goto unsafe;
 278                 }
 279
 280               /* No defs are call clobbered, so the optimization is safe.  */
 281               CALL_EXPR_RETURN_SLOT_OPT (call) = 1;
 282               /* This is too late to mark the target addressable like we do
 283                  in gimplify_modify_expr_rhs, but that's OK; anything that
 284                  wasn't already addressable was handled there.  */
 285
 286               unsafe:;
 287             }
 288         }
 289     }
 290 }
 291
 292 struct tree_opt_pass pass_return_slot =
 293 {
 294   "retslot",                            /* name */
 295   NULL,                                 /* gate */
 296   execute_return_slot_opt,              /* execute */
 297   NULL,                                 /* sub */
 298   NULL,                                 /* next */
 299   0,                                    /* static_pass_number */
 300   0,                                    /* tv_id */
 301   PROP_ssa | PROP_alias,                /* properties_required */
 302   0,                                    /* properties_provided */
 303   0,                                    /* properties_destroyed */
 304   0,                                    /* todo_flags_start */
 305   0,                                    /* todo_flags_finish */
 306   0                                     /* letter */
 307 };