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